Lokalisering av type-skilt i anleggsbilder

(1)

(2)

Universitetet i Stavanger

MASTEROPPGAVE

Teknisk-naturvitenskaplig fakultet Institutt for data- og elektroteknikk

Av

Ole Ronny Andersen

Lokalisering av typeskilt i anleggsbilder

Veiledere: Kjersti Engan og Tom Ryen

(3)

Forord

Dette er den avsluttende oppgaven for masterstudiet til Ole Ronny Andersen ved Universitetet i Stavanger. Masteroppgaven tilsvarer 30 studiepoeng, og er gjennomført ved Universitetet i Sta- vanger i løpet av v˚aren 2012 i sammarbeid med Verico AS.

Prosjektet bygger p˚a videre p˚a et forprosjekt som ble p˚abegynt høsten 2011, sammen med Thomas Ivesdal-Tronstad.

Prosjektet har vært lærerikt, interresant og utfordrende. Valg av oppgave ble gjort ut fra interesse for de praktiske utfordringene med oppgaven, og generell interesse for bildebehandling.

Jeg vil takke veilederne Kjersti Engan og Tom Ryen ved Universitetet i Stavanger, for gode tilbakemeldinger og rettledninger underveis. Jeg vil ogs˚a takke medstudentene mine Thomas Ivesdal-Tronstad og Jan Heldal og for deres kunnskapsdeling. Og til slutt vil jeg takke Verico AS som har vært veldig imøtekommende og hjelpsomme.

Sammendrag

Denne rapporten tar for seg en algoritme som automatisk lokaliserer type-skilt i anleggsbilder.

Den store variasjonen i struktur, størrelse, form, farger, bakgrunner og vinkel bilder er tatt fra har gjort oppgaven utfordrende. Rapporten vil først g˚a gjennom noe grunnleggende nødvendig teori som ligger til grunn i den utviklede algoritmen. Videre vil algoritmen som er blitt utviklet presenteres og bli gjennomg˚att med noen foklaringer. Algoritmen vil s˚a bli testet p˚a tre forskjellige testsett, de resultatene som algoritmen ender opp med vil det bli m˚alt ytelsen til. Til slutt er det en konklusjon og forslag til videre arbeid.

(4)

Innhold

Innholdsfortegnelse 4

1 Introduksjon 7

2 Teori 8

2.1 Nedsampling . . . 8

2.2 Wiener filtrering . . . 9

2.3 Kontrastforbedring med imadjust.m . . . 11

2.4 Kantdeteksjon . . . 12

2.4.1 Sobel . . . 12

2.4.2 Colorgrad . . . 16

2.5 Morfologisk operasjon . . . 17

2.5.1 Dilasjon . . . 17

2.5.2 Erosjon . . . 18

2.5.3 Morfologisk lukking . . . 19

2.6 Linje deteksjon ved bruk av Hough Transform (HT) . . . 21

3 Andre om lokalisering av nummerskilt 23 4 Algoritmeutvikling 24 4.1 Forbehandling. . . 25

4.2 Parametersetting . . . 28

4.3 Kantdeteksjon og forbedring av gradient . . . 29

4.4 Gr˚askala Hough Transform . . . 29

4.5 Morfologi og fjerning av linjesegment basert p˚a deres lengde . . . 31

4.6 Beregning av krysningspunkt . . . 33

4.7 Fjerning av linjesegment basert p˚a deres krysningspunkt og lengde . . . 36

4.8 Finne fire potensielle hjørnekoordinater som inneholder type-skiltet. . . 37

5 Test av algoritmen 38 6 Vurdering av resultater. 38 6.1 Testsett 1: . . . 40

6.2 Testsett 2: . . . 46

6.3 Testsett 3: . . . 52

7 Konklusjon og diskusjon 57 8 Videre arbeid 58 Referanser 59 A Matlab-funksjoner brukt i oppgaven 61 A.1 Liste over Matlab-funksjoner som er blitt brukt: . . . 61

A.2 setParam.m . . . 62

Liste Over Figurer

1 Nedsampling . . . 8

2 Wiener-filter sammenlignet med Average-filter og Median-filter . . . 10

3 Imadjust med default parametre . . . 11

4 De ulike kontrast strekkings metodene til funksjonenimadjust [1] . . . 12

5 Eksempel p˚a Sobel filter-masker. . . 12

(5)

6 Bildet som skal gjøres Sobel-kantdeteksjon p˚a . . . 13

7 Sobel-maske til venstre og resultatgx til høyre . . . 14

8 Sobel-maske til venstre og resultatgy til høyre . . . 14

9 Resultat avg_x² ogg_y² . . . 15

10 Resultat av kantdeteksjonen ved bruk av Sobel . . . 15

11 Resultat av kantdeteksjonen ved bruk av Sobel og Colorgrad . . . 17

12 Illustrasjon av morfologisk dilasjon . . . 18

13 Illustrasjon av morfologisk erosjon . . . 19

14 Illustrasjon av morfologisk lukking . . . 20

15 Illustrasjon av Hough Transform(HT). . . 22

16 Enkelt blokkdiagram med piler som representerer flyten til algoritmen. . . 24

17 Illustrasjon som viser de forskjellige resultatene i forbehandlingen . . . 26

18 Illustrasjon over grense-verdiene som myKontrast.m beregner for kontrast strekking. Verdier utenfor grensene blir satt til 0 eller 255. . . 27

19 Illustrasjon som viser de tre forskjellige resultatene av kontrast prosessering gjort kun p˚a R-matrisen til orginalbildet. Disse endringen blir utført av m-filen: myKon- trast.m . . . 27

20 Illustrasjon over hva som avgjør valget av parametsersett1 og parametersett2 i set- Param.m funksjonen. St˚aende bilder har parametersett1 og liggende bilder har parametersett1. . . 28

21 Illustrasjon som viser de tre forskjellige Hough Transform resultatene, og nederst til venstre det totale resultatet ved ˚a legge sammen de tre øverste resultatene. . . 30

22 Illustrasjon av noen resultater fra de forskjellige stegene i funksjonen morph.m. . 31

23 Uinteressante linjesegment her markert med fargen magenta blir fjernet. . . 32

24 Resultat som sendes videre til blokknummer 11, etter prosessering av blokknummer 10. . . 33

25 Strukturelementene som brukes av morph.m, og som er blitt satt av setParam.m basert p˚a bildestørrelsen som prosessers. . . 33

26 Illustrasjon over krysningspunktet som blir funnet mellom vertikale- og et horisontale- linjesegment. . . 34

27 Minimum- og maksimum grensene funnet til et av de vertikale linjesegmentet. . . 35

28 Illustrasjon over de krysningspunktet som er igjen etter reduksjon. Totalt 43 krysningspunkt. . . 35

29 Illustrasjon av resultater produsert underveis og det endelige resultatet produsert i blokknummer 12 fra blokkdiagrammet. . . 36

30 De fire potensielle hjørnekoordinatene produsert automatisk av algoritmen . . . . 37

31 Omr˚adet automatisk detektert av algoritmen er markert med en stiplet linje med fargen cyan. Skiltet funnet manuelt er merket med stiplet linje med fargen magenta. 38 32 De fire utfallene en klassifisering kan ha markert med grønn.. . . 39

33 Bilde nr 1 til og med 12 fra Testsett 1. . . 43

Liste Over Tabeller

1 Data 1 for Testsett 1 . . . 41

(6)

7 Sammenligning av de tre testsettene. . . 57

(7)

1 Introduksjon

Hensikten med arbeidet i denne rapporten har vært ˚a produsere en algoritme for automatisk lokalisering av type-skilt i digitale bilder. Grunnen for at dette skal automatiseres er p˚a grunn av at Verico AS har en voksende database over anleggsbilder som skal klassifiseres, og en manuell klassifisering av en stor og voksende mengde bilder krever mye tid. Hensikten med lokaliseringen er for at en senere automatisk tekstgjenkjenning p˚a type-skiltene skal enklere kunne bli utført.

Denne prossesen med tekstgjenkjenningen er ikke en del av denne oppgaven.

Jeg vil videre anbefale ˚a ha pdf-versjonen tilgjengelig n˚ar rapporten blir gjennomg˚att. Dette er p˚a grunn av at det er en del figurer som er litt sm˚a i størrelse, men som kan forstørres opp en del.

(8)

2 Teori

Teori kapittelet presenterer grunnleggende metoder som blir brukt i den endelige algoritmen som blir presentert i kapittel4.

2.1 Nedsampling

Nedsampling kan brukes i bildebehandling hvis enn har veldig store bilder, det vil si bildet har stort antall piksler eller bildeelementer. Jo flere piksler jo mer m˚a prosesseres. En nedsampling p˚a 2 vil si at vi kaster hvert andre piksel i hver kolonne og rekke fra bildet. Resultatet av en nedsampling blir illustrert i et eksempel nedfor i figur1. Eksempelet viser en nedsamplingfaktor p˚a 6, det vil si at vi kun beholder hvert 6 piksel i kolonnene og rekkene til bildet.

(a) Orginalbildet (b) Orginalbildet zoomet litt inn

(c) Resultat etter nedsampling p˚a 6 (d) Nedsamplet bildet zoomet litt inn

Figure 1: Nedsampling

I figur1kan det observeres at nedsampling har en lignende virkning som en svak glatting har.

Denne svake glattingen vil reduserer høye frekvenser i bildet men den viktigste informasjonen i bildet blir bevart. I dette prosjektet har det blitt brukt nedsampling p˚a 4. Men ved nedsampling p˚a 6 eller mer kunne det forekomme at viktig informasjon ble mistet. Nedsamplingen har ikke hatt stor betydning p˚a selve sluttresultatet utenom at prosesseringstiden har g˚att betraktelig ned.

[2] [3]

(9)

2.2 Wiener filtrering

Et wiener-filter er et 2-Dimensjonalt adaptivt filter som brukes til ˚a fjerne støy med en bestem varians. Hvis det ikke oppgis en varians som skal fjernes beregner filteret selv variansen ut i fra nabopikslene til pikselen som skal prosesseres. I MATLAB heter denne funksjonenwiener2.[4] [5]

Middelverdi:

µ 1 M N

¸

m,nPW

fpm, nq (1)

• fpm, nqer gr˚askala verdi til piksel (m,n) i et gr˚askalabilde.

• W er det lokale vinduet som har størrelsen MxN.

Varians:

σ² 1 MN

¸

m,nPW

f²pm, nq µ² (2)

Verdi etter filtrering:

gpm, nq µ σ²v²

σ² rfpm, nq µs (3)

• gpm, nqer verdi ut etter filtrering

• v² er variansen til støyen. Hvis ikke vi har satt noen verdi p˚av² vil den settes til gjennomsnittet av alle lokale varianser til bildet.

Hvis v² settes lik gjennomsnittet av alle lokale varianser i bildet:

Hvis vi har for eksempel har et bilde hvor det er liten varians i store deler av bildet og stor varians i en mindre del av bildet vil gjennomsnittet til alle de lokale variansene bli lav. Det vil igjen føre til at de omr˚adene med lav varians blir glattet mer enn omr˚adet med høy varians. Dette blir illustrert i figur2 hvor Wiener-filteret ogs˚a blir sammenlignet med filtrene Median-filter og Average-filter.

Wiener-filteret beregnerv²ut fra alle lokale varianser selv.

(10)

(a) testbilde

(b) testbilde ’Wiener-filtert’ med 3x3-maske (c) testbilde ’Wiener-filtert’ med 7x7-maske

(d) testbilde ’Average-filtert’ med 3x3-maske (e) testbilde ’Average-filtert’ med 7x7-maske

(f) testbilde ’Median-filtert’ med 3x3-maske (g) testbilde ’Median-filtert’ med 7x7-maske

(11)

2.3 Kontrastforbedring med imadjust.m

En teknikk som kan brukes til ˚a forbedre kontrasten i et gr˚askala bilde er ˚a lage en ny ’mapping’

p˚a fordelingen til intensitets-verdiene til bildet som prosesseres slik at at minimum og maximum intensitets-verdier p˚a bildet blir satt til en ny minimum og maximum. I Matlab kalles denne funksjonenimadjust[1] [6]. Veddefault setterimadjustintensitetverdiene slik at 1% av pikslene i bildet settes til verdien ’0’ og en annen 1% av pikslene settes til verdien ’255’. Det er litt lettere

˚a illustrere hva som skjer ved ˚a se p˚a et enkelt eksempel som viser piksel intensitetsverdiene i et histogram,se figur3.

(a) Rød-matrisen før prosessering (b) Rød-matrisen etter prosessering medimadjust

(c) Histogram over intensitets-verdier til Rød- matrisen før prosessering

(d) Histogram over intensitets-verdier til Rød- matrisen etter prosessering medimadjust

Figure 3: Imadjust med default parametre

Ved ˚a studere histogrammet i figur 3 d) som er blitt prosessert med imadjust funksjonen i MATLAB med default parametre, kommer det frem at 1% av pikslene f˚att intensitet verdien ’0’.

Det er ogs˚a 1% av pikslene til bildet som har f˚att intesitetsverdien ’255’. Vi ser ogs˚a at dette tydelig har økt kontrasten ved ˚a studere bildene i figur3 a) og b). Figur3 d) viser ogs˚a at resten av verdiene har blitt strukket likt utover histogrammet. Det er fordi ved default gjøres det en linær ’mapping’ av intensitets-verdiene. Det trengs ikke ˚a bli utført linær kontrast strekking men det kan ogs˚a brukes logaritmisk kontrast strekking, dette er illustrert i figur4

(12)

(a) Logaritmisk vektet mot høye intensitets-verdier

(b) Linær (default) (c) Logaritmisk vektet mot lave intensitets-verdier

Figure 4: De ulike kontrast strekkings metodene til funksjonenimadjust[1]

2.4 Kantdeteksjon

Kantdeteksjon er den mest kjente metoden for ˚a detektere endring eller forskjell i intensitets-verdier i et bilde. Dette kan gjøres ved ˚a beregne gradienten som best˚ar av den deriverte i horisontale- og vertikale-retning. Jo større endring i intensitet jo større verdi f˚ar vi etter kantdeteksjon. Det finnes forskjellige metoder for ˚a tilnærme de deriverte. I denne oppgaven har brukes det en funksjon basert p˚a Sobels tilnærming oppdaget i forprosjekt arbeidet[2], som hetercolorgrad.mhentet fra [1].

2.4.1 Sobel

Sobel tilnærming til de deriverte g˚ar ut p˚a ˚a konvolvere en filter-maske vertikalt og horisontalt med bildet som vi ønsker ˚a finne kanter i. Vanligvis er størrelsen til filter-masken 33 det er standardvalget til MATLAB ogs˚a hvis ikke noe annet er spesifisert. I figur5vises den horisontale og vertikale Sobel masken.

(a) Horisontal filter-maske (b) Vertikal filter-maske

Figure 5: Eksempel p˚a Sobel filter-masker

Lengde og vinkel p˚a Sobel gradient:

Vi har et bilde som er et 2D-signal og derfor blir gradienten definert som en vektor∇f:

∇f g_x

gy

_Bf Bx Bf By

(4)

(13)

hvor,

gxBf

Bx og gy Bf

By (5)

Størrelsesordenen eller lengden til gradienten er definert som lengden av vektoren:

∇f rg²_x g²_ys¹² b

g²_x g_y² (6)

Vinkelen til gradienten er definert vinkelen mellomg_xogg_y: αpx, yq tan¹

g_y gx

(7)

Eksempel p˚a kantdeteksjon med Sobel-maske som har størrelsen 33:

I figur6er det bilde av en firkant som vi skal utføre en kantdeteksjon med Sobel-metoden. Til høyre i figuren er matrisen med piksel-verdiene til bildet.

(a) Testbilde (b) Pikselverdier til testbilde

Figure 6: Bildet som skal gjøres Sobel-kantdeteksjon p˚a

(14)

gx finnes ved ˚a konvolvere ’Testbildet’ med masken i figur 7:

Figure 7: Sobel-maske til venstre og resultat gxtil høyre

gy finnes ved ˚a konvolvere ’Testbildet’ med masken i figur8:

Figure 8: Sobel-maske til venstre og resultatgy til høyre

(15)

g_x² og g_y²:

(a)gx² (b)gy²

Figure 9: Resultat av g²_xogg_y²

Sluttresultat til gradienten ∇f b

g²_x g_y² ved Sobel-metoden:

(a) Sluttresultat vist i form av bilde (b) Sluttresultat vist i form av matrise-verdier

Figure 10: Resultat av kantdeteksjonen ved bruk av Sobel

I figur10ser vi en tydelig kantdeteksjon av firkantobjektet i ’Testbildet’ fra figur6.

(16)

2.4.2 Colorgrad

Den vanlige Sobel-metoden fra kapittel2.4.1finner bare gradient til gr˚askala- og binære-bilder, og krever dermed at vi m˚a gjøre om et farge-bilde om til gr˚askala-bilde for ˚a kunne prosessere bildet.

I dette prosjektet har vi veldig stor variasjon i bildene som skal prosesseres dermed viktig av vi beholder s˚a mye informasjon av betydning vi kan. Dermed kommer funksjonencolorgrad.msom er hentet fra [1] godt med. Denne funksjonen bygger videre p˚a Sobel-metoden og bruker Sobel- maskene.

Colorgrad.mg˚ar ut p˚a at gradienten blir beregnet for hver av de 3 matrisene(Rød Grønn Bl˚a) som et RGB-fargebilde best˚ar av. De tre gradient-resultatene for hver farge-matrise blir s˚a sl˚att sammen til et resultat.

Utvider gradient konseptet med 2 vektorfunksjoner som finner endringer i x- og y-retning for de tre fargeplanene og legger endringene sammen:

u BR Bxr BG

Bxg BB

Bxb (8)

og

vBR

Byr BG Byg BB

Byb (9)

Hvor r, g og b er enhetsvektorene til hendholdsvis Rød(1,0,0), Grønn(0,1,0) og Bl˚a(0,0,1) i RGB-rommet.

Finner lengden til til vektorene:

g_xxuuu^Tu BR

Bx ²

BG Bx

² BB

Bx

² (10)

gyy vvv^Tv BR

By ²

BG By

² BB

By

² (11)

gxyuvu^Tv BR Bx

BR By

BG Bx

BG By

BB Bx

BB

By (12) Kan ogs˚a her finne vinkel og lengde til gradient som vi kunne i Sobel-metoden.

Vinkelendring er definert som:

θpx, yq 1 2tan¹

2g_xy gxxgyy

(13)

Endring i lengden til gradienten er definert som:

F_θpx, yq

"

1

2rpg_xx g_yyq pg_xxg_yyqcos 2θpx, yq 2g_xysin 2θpx, yqs

*¹₂

(14)

(17)

(a) Testbildet (RGB-format) (b) Resultat av Colorgrad, med Ter- skling=0.08

(c) Testbildet (Gr˚askala-format) (d) Resultat avSobel, med Terskling=0.08

Figure 11: Resultat av kantdeteksjonen ved bruk av Sobel og Colorgrad

Ved ˚a studere figur11vises det en tydelig forskjell p˚a hvor mye informasjon vi har igjen etter

˚a ha brukt lik terskling p˚a kantdeteksjonen gjort av Colorgrad og Sobel.

2.5 Morfologisk operasjon

I bildebehandling brukes morfologi som et verktøy for ˚a hente ut bildekomponenter som kan være nyttige for ˚a representere eller beskrive formen til et omr˚ade. I de mofologiske funksjonene som blir gjennomg˚att her brukes et strukturelement. Et strukturelement er en binær matrise, og kan ha forskjellige former alt etter hvilken hensikt og effekt som er ønskelig p˚a bildet som prosesseres. I denne oppgaven vil det kun bli brukt morfologiske operasjoner for binær bilder, selv om det finnes morfologiske operasjoner for gr˚askala-bilder [1].

2.5.1 Dilasjon

Dilasjon er en morfologisk operasjon som utvider et objekt eller omr˚adet i et bilde. Størrelse og formen p˚a utvidelsen er avhengig av formen og størrelsen p˚a strukturelementet. Dilasjon er definert som:

A`B tz|pBˆqzXA Hu

(18)

hvor,

• ’`’ er symbolet for dilasjon.

• ’ ˆB’ er strukturelementet B reflektert.

• ’A’ er bildet som skal prosesseres.

I figur 12 er en illustrasjon som viser hvordan en morfologisk dilasjon operasjon fungerer.

Strukturelementet er vertikalt og har sitt origo i det midterste elementet markert med bl˚a farge.

Strukturelementet vil bli flyttet gjennom hele bildet i figur12b) og der som origo til strukturelementet overlapper en 1-er i bildet, settes alle piksler som blir dekket av hele strukturelementet til enere. De røde enerne i figur12e) er omr˚ader som har blitt satt til ener verdier ved dilasjon.

(a) Struk- turelementet

(b) Orginalbildet (c) Pikselverdiene til Orginalbildet

(d) Bildet etter dilasjon (e) Pikselverdiene etter dilasjon

Figure 12: Illustrasjon av morfologisk dilasjon

2.5.2 Erosjon

Erosjon er en operasjon som forminsker eller krymper et omr˚adet eller objekt. Dette gjøres ogs˚a med et strukturelement. Strukturelementet avgjør formen og hvor kraftig forminskningen blir.

Erosjon er definert som:

AaB tz|pBqzAu

(19)

hvor,

• ’a’ er symbolet for erosjon.

• ’B’ er strukturelementet.

I figur13er en illustrasjon som viser hvordan en morfologisk erosjon operasjon fungerer. Struk- turelementet er her det samme som ble brukt ved dilasjon. Strukturelementet vil bli flyttet gjennom hele bildet i figur13b) for ˚a se hvor og hvor hele strukturelementet passer inn i objektet. Objektet er her de omr˚adene som har pikselverdi lik 1. Alle de stedene hvor strukturelementet passet inn i objektet settes pikselverdien som overlappes av strukturelementets origo til 1. Resultatet av erosjon operasjonen er vist i figur13c) og d).

(b) Bilde før erosjon (c) Pikselverdiene før erosjon

(d) Bildet etter erosjon (e) Pikselverdiene etter erosjon

Figure 13: Illustrasjon av morfologisk erosjon

2.5.3 Morfologisk lukking

Morfologisk lukking er en kombinasjon av dilasjon og erosjon. Morfologisk lukking er definert som først en dilasjon av ’A’ med strukturelementet ’B’, etterfulgt av erosjon med det samme strukturelementet av resultatet fra dilasjonen. Det finnes andre kombinasjoner mellom dilasjon og erosjon, men de brukes ikke i denne oppgaven.

Morfologisk lukking er definert som:

AB pA`Bq aB

(20)

hvor,

• ’’ er symbolet for morfologisk lukking.

• ’B’ er strukturelementet.

Ved ˚a sammenligne figur14som viser en illustrasjon av morfologisk lukking med figurene 12 og13, kan det observeres at vi f˚ar samme resultat etter en lukking som ved en dilasjon etterfulgt av erosjon. Sluttresultatet i figur14d) viser samme resultat som i resultatet i figur13d) fordi den viser ersosjon av resultatet fra dilasjon illustrasjonen i figur12d) med samme strukturelement.

(b) Bilde før morfologisk lukking (c) Pikselverdiene før lukking

(d) Bildet etter lukking (e) Pikselverdiene etter lukking

Figure 14: Illustrasjon av morfologisk lukking

(21)

2.6 Linje deteksjon ved bruk av Hough Transform (HT)

Hough Transform er en teknikk som kan brukes til ˚a trekke ut karakteristiske trekk i bildebehandling p˚a en effektiv m˚ate. Typisk brukes Hough Transform til ˚a trekke ut rette linjer fra en kantdeteksjon. I praksis vil vi ha forskjellig støy i en kantdeteksjon som gjør at vi ikke har perfekte kanter. Dette kan føre til at vi har diskontinuerlige kanter, og for ˚a prøve ˚a knytte disse kantseg- mentene sammen til meningsfulle kanter brukes ofte Hough Transform etter en kantdeteksjon.

[1][7]

Vanligvis beskriver vi rette linjer med ligningen:

yax b (15)

Ved bruk av ligning15for ˚a beskrive rette linjer oppst˚ar det problemer fordi stigningstallet’a’

g˚ar mot uendelig n˚ar linjer nærmer seg vertikal-retning. Hough Transformasjon beskriver en linje ved bruk av normal representasjon av en linje, som unng˚ar dette problemet. Ligningen som bruker normal representasjon av linje er vist i ligning16.

ρxcosθ ysinθ (16)

hvor,

• ρlengden til den bl˚a stiplede linjen i figur15b). Og har rekkvidden: D¤ρ¤D.

• D = diagonalen til bildet i figur15b).

• θ= er vinkelen mellom den bl˚a stiplede linjen og den horisontale-aksen i figur15b). Og har rekkvidden: 90¤θ 90

• x = horisontale-aksen i figur15b).

• y = vertikale-aksen i figur15b).

Ved ˚a studere ligning17, kan vi se sammenhengen mellom ligning15og16:

ρxcosθ ysinθñy

cosθ sinθ

x

ρ sinθ

(17)

(22)

Eksempel p˚a Hough Transform:

I figur15vises et enkelt eksempel p˚a representasjon av en linje som g˚ar gjennom to punkt ved bruk at Hough Transform. De to hvite punktene i figur15a) representerer 2 piksler i en potensiell linje. Vi ønsker ˚a finne den røde rette linjen ved hjelp av Hough Transform. Den stiplede bl˚a linjen er vinkelrett p˚a den røde linjen som vi vil finne og brukes til ˚a beskrive den rette røde linjen.

Koordinatene til de to pikslene er for punkt1 = (5,45) og for punkt2 = (40,10).

Ved ˚a ta Hough Transform for kun et av punktene hver for seg vil vi f˚a resultatet i figur 15 c) og d) som viser en sinusformet bølge. Den totale Hough Transformen til begge punktene er det samme som ˚a kombinerer resultatetene fra figur15c) og d), og da f˚ar vi en topp eller en maksimum i Hough Transformen som kommer frem i figur15e) og f). Der hvor de to sinusformede bølgene krysser hverandre kalles en topp, og punktet til toppen har vi en potensiell rett linje som inkluderer begge pikslene. Ellers i figur15e) har vi ingen kontakt mellom de to sinus-bølgene og det betyr at vi ikke har en rett linje som inkluderer begge punktene ellers i Hough Transformen. Ved ˚a lese av verdiene til den horisontale- og vertikale-aksen i topp-punktet erρ34 ogθ45. Disse verdiene var de vi ønsket ˚a finne ifølge 15b) hvorρ33.9 og θ45. [1] [8]

(a) Eksempelbildet. (b) Den røde linjen vi ønsker ˚a detektere.

(c) Kun HT til punktet (5,45).

(d) Kun HT til punktet (40,10). (e) Totale HT. (f) Totale HT ,forstørret inn p˚a mak- simums omr˚adet.

Figure 15: Illustrasjon av Hough Transform(HT).

Hough Transform for gr˚askala bilder:

I Matlab er det en innebygget Hough Transform for svart-hvitt bilder. Men ved bruk av colorgrad.m mottar vi en kantdeteksjon som er gr˚askala format. Fra forprosjektet ble det observert at ˚a g˚a fra gr˚askala til svart-hvitt bilde for ˚a gjøre en Hough Transform p˚a svart-hvitt bilde, kunne det tapes viktig informasjon og støy kunne ogs˚a bli forsterket [2]. Videre ble det oppdaget en Hough Transform for gr˚askala bilder. Dermed unng˚as tersklingen i overgang til svart-hvitt bilder og vi kan bevare viktig informasjon.

Fra MATLAB’s fildelingside [9] ble den gr˚askala Hough Transformasjon funksjonen funnet.

(23)

Filen heter Hough Grd.m og har to parametre som kan justeres p˚a. Ved ˚a justere p˚a disse parametrene kan det resultere i at flere linjer blir detektert. De to parametrene er:

• Grdthres er terskling for intensiteten til en piksel som tilhører en linje

• Detsent er sensitiviteten til linjedeteksjonen

3 Andre om lokalisering av nummerskilt

Lokalisering av potensielle type-skilt i bilder er komplisert p˚a grunn av store variasjoner i struktur, størrelse, form, farge,bakgrunn og selve plasseringen av type-skiltet i bildet. Vinkelen som bildene er tatt fra kan ogs˚a skape problemer. Ulik lys fordeling som overeksponering eller kraftige skygger og refleksjoner kan skape problemer. I denne oppgaven skal det lokaliseres type-skilt i anleggsbilder, men de mest vanlige problemstillingene som har mange fellestrekk med problemstillingen i denne oppgaven er prosjekter basert p˚a automatisk lokalisering og gjenkjennelse av nummerskilt til biler (ALPR - Automatic License Plate Recognition).

ALPR-prosjekter er ofte delt opp i 3 deler:

• Lokalisering av nummerskilt

• Segmentering av data i skiltet

• Gjenkjenning av segmentert data

I denne oppgaven er det den første delen som g˚ar ut p˚a ˚a lokalisere nummerskiltet, som har vært av interesse. Denne delen g˚ar ut p˚a ˚a finne potensielle omr˚ader som inneholder nummerskiltet.

Denne lokaliseringsdelen beskrives som den mest utfordrende oppgaven [10] [11].

Det er vanlig at det brukes en kantdeteksjon som en del av lokaliserings algoritmen for ˚a finne standardiserte nummerskilt [10] [11] [12] [13] [14].

Etter kantdeteksjon er det noen disse tidligere arbeidene som lokaliserer omr˚ader med mange vertikale kanter som kandidat omr˚ader [10] [11] [12] [15]. I prosjekt [14] ble det videre etter kantdeteksjon brukt forskjellige morfologiske metoder i kombinasjon med Hough Transform slik at de sitter igjen med nummerplate kandidater. I prosjekt [13] ble det videre etter kantdeteksjon brukt en kombinasjon av Hough Transform og kontur (imcontour.m i matlab) for ˚a finne lukkede grenser til et objekt. Ellers er normalt ˚a utføre en Hough Transform p˚a kantdeteksjon-resultatet for ˚a finne vertikale- og horisontale grensene til et nummerskilt [14].

(24)

4 Algoritmeutvikling

I dette kapittelet vil algoritmen som er blitt utarbeidet v˚aren 2012 bli gjennomg˚att. Arbeidet ble utført Algoritmen bruker ogs˚a elementer fra forprosjektet [2] som ble utført høsten 2011. Program- vare som er blitt brukt i arbeidet med ˚a utvikle algoritmen er MATLAB. En forenklet oversikt over algoritmen blir vist i figur16. Ved ˚a studere blokkdiagrammet kan det observeres at blokkene har forskjellige nummer oppe helt til venstre i hver enkelt blokk. Numrene i blokkene vil bli brukt i beskrivelsen av algoritmen for ˚a gi en bedre oversikt og beskrivelse. I figur17 a) er et eksempel bilde som skal brukes gjennom forklaringen av den automatiske algoritmen i dette kapittelet.

Figure 16: Enkelt blokkdiagram med piler som representerer flyten til algoritmen.

(25)

4.1 Forbehandling

Blokknummer: 2, 4 og 5.

Etter at bilde som skal prosesseres er lastet inn, blir det gjort en forbehandling. Forbehandlingen best˚ar av blokkene med nummer 2, 4 og 5 i figur16:

• Nedsampling

• Wiener-filtrering

• Kontrast prosessering

I blokk nummer 3 settes parametre basert p˚a størrelsen til bildet som er blitt nedsamplet. Dette er ikke en del av forbehandlingen, men er bare satt inn i blokkdiagrammet i den rekkefølgen her for det er slik rekkefølgen er i m-filen for algoritmen.

Blokknummer 2, Nedsampling

Nedsampling ble presentert i forprosjektet [2], som en del av forbehandlingen i det videre arbeidet til masteroppgaven. Nedsamplingsfaktor ble ikke bestemt i forprosjektet. I arbeidet med masteroppgaven ble det derfor testet ut forskjellige nedsamplingsfaktorer p˚a forskjellige bilder. En nedsamplingsfaktor som gav tilfredsstillende resultater med tanke p˚a tid og bevaring av viktigste informasjon var ved bruk av nedsamplings faktor p˚a fire.

Blokknummer 4, Wiener-filtrering

Wiener-filtreret blir brukt til ˚a gjøre en adaptiv glatting i forbehandlingen for ˚a fjerne støy. Dette er for at videre kantdeteksjon og Hough Transform er begge sensitive for støy [14] [16]. De fleste bildene har et større omr˚ade med lav varians, og et mindre omr˚ade hvor skiltet befinner seg som vanligvis har en større varians enn bakgrunnen som passer bra med egenskapene til Wiener-filteret.

Wiener-filtreringen vil føre til liten glatting i omr˚ader med høy varians og en større glatting i omr˚ader med lav varians, forklart mer detaljert i kapittel 2.2. I figur17 b) vises resultatet etter en wiener filtrering. Resultatet vil oppfattes som om det har blitt veldig svakt glattet.

Blokknummer 5, Kontrast prosessering

Kontrast prosesseringen var først ikke en del av forbehandlingen. Grunnen til at den ble med etterhvert, var at til ˚a begynne med bestod treningssettet av 6 forskjellige bilder. Men etter ˚a ha økt treningssettet med 10 bilder til oppstod problemet at ikke alle kantene til skiltene blir detektert.

Det var forskjellige grunner til dette for eksempel: skygger over kantene til skiltet, maling over kanter eller grums som forkludret kantene til skiltet, bakgrunn har veldig lik farge og intensitet som selve skiltet og at noen omr˚ader av bilder var overeksponering samtidig som andre omr˚ader var mørke.

Etter ˚a ha prøvd kontrast forbedrings funksjonene til Matlab histeq.m, adapthisteq.m og imadjust.m opp mot hverandre, virket det som imadjust.m funksjonen var den mest robuste i forhold til de bildene som skulle prosesseres i denne oppgaven. Denne funksjonen er egentlig beregnet for gr˚askala bilder, men er her blitt brukt p˚a de tre gr˚askala matrisene som RGB-bildet best˚ar av.

Dette kan medføre til at farger i bildet blir endret, men det har ikke hatt betydning for resultatet ettersom farge-informasjonen ikke har blitt brukt til annet enn kantdeteksjon i denne oppgaven. I figur17c), d) og e) er de tre forskjellige resultatene av kontrast prosesseringen, og blir produsert av funksjonen myKontrast.m. De tre bildene som ble produsert av myKontrast.m blir det videre gjort kantdeteksjon p˚a. Derfor deles blokkdiagrammet i figur 16 etter blokk nummer 5, og g˚ar videre til blokk nummer 6a, 6b og 6c som mottar hvert sitt forskjellig kontrast prosesserte bilde som vises i figur17c), d) og e).

(26)

(a) Orginalbildet nedsamplet med 4 (b) Etter wiener-filtrering

(c) Konstrast prosessering 1, be- handles videre av blokknummer 6a i figur16.

(d) Konstrast prosessering 2, be- handles videre av blokknummer 6b i figur16

(e) Konstrast prosessering 3, be- handles videre av blokknummer 6c i figur16

Figure 17: Illustrasjon som viser de forskjellige resultatene i forbehandlingen myKontrast.m

myKontrast.m bruker den innebygde matlab funksjonen imadjust.m forklart i kapittel2.3. Imad- just.m bruker en funksjon som heter strechlim.m. Ved ˚a gi strechlim.m et gr˚askala gr˚askala bilde vil funksjonen returnere en vektor som inneholder øvre- og nedre-grense som kan brukes til kontraststrekking i imadjust.m funksjonen. Stretchlim.m kan ogs˚a brukes p˚a RGB-bilder men da gir den ut tre stk vektorer, en vektor for hver fargematrise som ogs˚a inneholder en øvre- og nedre-grense for kontraststrekking. Ved ˚a ta bruke stretchlim.m p˚a R-matrisen som har histogrammet vist i figur 18vil den gi nedre grense for at 1% av pikslene skal skal bli satt til intensitetsverdi lik 0, og en øvre grense for at 1% av pikslene skal bli satt til intensitetsverdi lik 255. Grense-verdiene mottat av stretchlim er verdier p˚a skalaen mellom 0 til 255. All kontraststrekking utført i myKontrast.m er linært strukket, som er illustrert i figur4b).

Grense nr 1som myKontrast bruker til histogram strekking:

Finnes ved ˚a ta verdiene gitt av stretchlim.m vist i figur18b) ,og legge til en verdi p˚a 5% av 255 p˚a den nedre grensen og trekke fra samme verdi p˚a den øvre grensen gitt av stretchlim.m produseres grensene i figur18c). Grensene er markert med rød.

Grense nr 2som myKontrast bruker til histogram strekking:

Finnes ved ˚a ta verdiene til grense nr 1 vist i figur18c) og regne ut differensen mellom de to grense- verdiene, for s˚a ˚a legge en fjerdedel av differensen til nedre grense-verdi og trekke fra samme verdien fra øvre grense-verdi produseres grensene i figur18d). Grensene er markert med rød.

Grense nr 3som myKontrast bruker til histogramstrekking:

Finnes ved ˚a ta de 5% første verdiene til histogrammet og sette de til intensitetsverdi lik 0. Og ta 5%

av verdiene i slutten av histogrammet til høyre og setter de til intensitetsverdi lik 255. Denne svake strekkingen gjøres fordi ofte er kontrasten i orginalbildet veldig bra i utgangspunktet.Grensene som grense nr 3 bruker til strekking er vist i figur18d). Grensene er markert med rød.

(27)

I figur19b), c) og d) vises resultat etter strekking med imadjust.m funksjonen med grensene 1,2 og 3 produsert av myKontrast.m

Det blir beregnet tre stk grenser p˚a samme m˚ate for hvert av de tre fargeplanene (RGB). P˚a grunn av at dette kan det oppst˚a ulike grenser i kontraststrekking for de ulike fargeplanene, som kan føre til at fargene i bildet blir endret.

(a) Histogram over intensitetsverdiene til R-matrisen til orginalbildet.

(b) Øvre og nedre grense gitt av stretchlim.m

(c) Grense nr. 1, som myKon- trast.m beregner

(d) Grense nr. 2, som myKon- trast.m beregner

(e) Grense nr. 3, som myKon- trast.m beregner

Figure 18: Illustrasjon over grense-verdiene som myKontrast.m beregner for kontrast strekking.

Verdier utenfor grensene blir satt til 0 eller 255.

For enkelhets skyld er det i figur19a) vist R-matrisen til orginalbildet og tilhørende historam.

Og i19b), c) og d) er resultatbildene og deres intenisitets histogram etter kontraststrekking. Figur 19b) har brukt grense nr 1 til kontrast strekking. Figur 19c) har brukt grense nr 2 til kontrast strekking. Figur19d) har brukt grense nr 3 til kontrast strekking. Den samme prosedyren gjort for R-matrisen blir gjort for alle de tre matrisene som fargebildet best˚ar av og satt sammen igjen til resultatet vist i figur17b).

(a) R-matrisen til orginalbildet og intensitest histogrammet.

(b) Konstrast prosessert 1. (c) Konstrast prosessert 2. (d) Konstrast prosessert 3.

Figure 19: Illustrasjon som viser de tre forskjellige resultatene av kontrast prosessering gjortkun p˚a R-matrisen til orginalbildet. Disse endringen blir utført av m-filen: myKontrast.m

Etter ˚a ha strekket de tre fargeplanene med tre forskjellige grenser og satt de sammen til tre bilder igjen har vi de tre resultat bildene vist i figur17c), d) og e).

(28)

4.2 Parametersetting

Blokknummer: 3.

Parametersetting kommer rett etter nedsamplingen fordi parameterene settes ut i fra størrelsen p˚a det nedsamplede bildet. Parametersetting er blokk nummer 3 i blokkdiagrammet i figur16.

Parametersett1 og Parametersett2:

Hvert bilde best˚ar av m x n piksler, hvor m representerer den vertikale- og n den horisontale- størrelsen til bildet. Har vi m¡n da har vi eksempel 1 i figur ??a) og da velges parametersett1, ellers hvis vi har m n da har vi eksempel 2 i figur ??b) og da velges parametersett2.

Videre n˚ar vi har bestemt hvilket parametersett som vil bli brukt vil parametrene i dette parame- tersettet bli beregnet basert p˚a antall piksler m og n som bildet best˚ar av. Dette kommer av at alle bildene som proseseres ikke har likt antall piksler. Formel for beregning av parametrene er blitt til under trening av treningssettet. Selve formelen for paramtrene kan sees ved ˚a studere m-filen setParam.m i vedleggA.2.

Det er totalt 21 parametre som settes og de settes av m-filen setParam.m. Hver enkelt parameter vil blir forklart nærmere i det blokknummeret hvor funksjonene som bruker de ulike parameterene blir tatt i bruk.

Funksjonene som bruker parametrene som blir satt av setParam.m listet her:

• myClearHLines.m: dH1, dH2, KH1, KH2, minH1 og minH2.

• myClearVLines.m: dV1, dV2, KV1, KV2, minV1 og minV2.

• morph.m: BH1, BH2, BV1 og BV2

• findSingleCorner.m: xDist og yDist

• VHLinjerTot.m: Vtol og Htol.

• grenserMinMax.m: Ratio.

(a) Eksempel 1 (m¡n), bruker Parameter- sett1.

(b) Eksempel 2 (m n), bruker Parameter- sett2.

Figure 20: Illustrasjon over hva som avgjør valget av parametsersett1 og parametersett2 i set- Param.m funksjonen. St˚aende bilder har parametersett1 og liggende bilder har parametersett1.

(29)

4.3 Kantdeteksjon og forbedring av gradient

Blokknummer: 6a, 6b, 6c og 7.

P˚a de tre kontrast forbedrede fargebildene produsert i forbehandlingen blir det gjort en kantdeteksjon og videre en kontrastprosessering p˚a kantdeteksjonen. Disse operasjonene gjøres i blokk nummer 6a, 6b, 6c og 7 i blokkdiagrammet fra figur 16. Til dette er det blitt laget m-filen myVG.m som bruker funksjonene colorgrad.m fra kapittel 2.4.2 og imadjust.m fra kapittel 2.3.

Funksjonen myVG.m utfører først kantdeteksjon for hvert av de tre bildene og bruker s˚a en linær kontraststrekking hvor 1% av de minimum-verdiene i kantdeteksjonen settes til verdi ’0’ og 1% av maximum-verdiene til ’255’. Etter kontraststrekkingen blir det videre utført en gammajustering p˚a kantdetksjonen vektet mot høyre del av intensitetshistogrammet illustrert i grafen til figur 4 a). Dette er for at de kantene som ikke har fullt s˚a stor intensitetsverdi som de med størst intensitetsverdi skal bli mer utlignet, slik at kantene lettere kan bli detektert av Hough Transformen i neste steg i blokkdiagrammet fra figur16. De tre kantdeteksjonene kan sees hvis en ser bort fra røde og grønne linjene i figur21a), b) og c). De røde og grønne linjene er linjer detektert av Hough Transformen og blitt plottet p˚a resultatet til kantdeteksjonen. B˚ade de kantdeteksjonene som ikke har f˚att kontrast prosessering, og de som har blitt kontrastprosessert blir det videre gjort Hough Transformasjon p˚a.

4.4 Gr˚ askala Hough Transform

Blokknummer: 8 og 9.

Etter blokknummer 7 i blokkdiagrammet fra figur 16 har vi tre stk kantdeteksjoner. Disse tre kantdeteksjon bildene blir det gjort Hough Transformasjon p˚a for ˚a finne rette linjer i bildet og linke sammen segmenter2.6. Dette gjøres fordi det antas at type-skiltet skal finnes er rektangulært og best˚ar av rette linjer. Det brukes en gr˚askala Hough Transform som ble funnet p˚a MATLAB’s internett side for deling av filer [9]. Valget av gr˚askala Hough Transformen er basert p˚a tidligere arbeid i forprosjektet [2] hvor det ble testet Hough Transform for gr˚askala bilder opp mot Hough Transform for svart-hvitt bilder. Hvor det virket som at den gr˚askala Hough Transformen var mer p˚alitelig i sin deteksjon av rette linjer.

Det er ikke alltid at en Hough Transform klarer ˚a detektere alle de rette linjene som er i et bilde, og ettersom at denne algoritmen krever at alle sidene til skiltet skal være detektert har det blitt laget m-filen VHLinjerTot.m. Denne filen ble laget under arbeidet av masteroppgaven, og er laget for at Hough Transformen lettere skal klare ˚a detektere flere rette linjer. Funksjonen deler bildet opp i mindre bildeblokker og utfører Hough Transform p˚a hver bildeblokk noe som øker deteksjonen av linjer. Det blir ogs˚a gjort flere Hough Transformer p˚a hver bildeblokk med forskjellige parametre p˚a grunn av at ikke alle linjer blir detektert med de samme parametrene.

VHLinjerTot.m:

Denne filen mottar de tre kantdeksjonene og utfører Hough Transform p˚a dem. Ved ˚a dele opp bildet av kantdeteksjonen i mindre blokker og utfører Hough Transformasjon p˚a hver blokk vil som sagt flere linjesegment blir detektert. Alle linjesegment som totalt blir funnet p˚a de tre kantdeteksjon-bildene blir til slutt lagt sammen. Ved ˚a studere figur 21 a), b) og c) ser vi linjesegmentene funnet for hver av de tre kantdeteksjonene. Dette tilsvarer de tre blokkene med blokknummer 8 i blokkdiagrammet fra figur16. Grunnen til at linjene er merket med forskjellige farger er for at VHLinjerTot.m filen ogs˚a utfører en sortering av horisontale og vertikale linjer etter at de er detektert.

VHLinjerTot.m funksjonen mottar ogs˚a de to parametrene Vtol og Htol satt i funksjonen set- Param.m fra kapittel4.2. Vtol og Htol er lik for begge parametersettene.

Vtol Vertikal vinkel toleranse, og er fast satt til 22 grader. Dette vil si at de vertikale

(30)

linjesegmentene kan variere 22 grader fra den vertikale-aksen som er 90 grader. Alts˚a m˚a vertikale linjersegment som skal bli beholdt være innenfor omr˚adet 70 til 110 grader.

Htol Horisontale vinkel toleranse, og er fast satt til 18 grader. Dette vil si at de horisontale linjesegmentene kan variere 18 grader fra den horisontale-aksen som er 0 grader. Alts˚a m˚a horisontale linjersegment som skal bli beholdt være innenfor omr˚adet fra -18 til 18 grader.

De linjesegmentene vist i figur 21 er linjesegmentene som er igjen etter at linjesegment med vinkel utenfor grensene satt av parametrene Vtol og Htol er fjernet.

For ˚a detektere mest mulig linjer med den gr˚askala Hough Transformasjonen funksjonen Hough Grd.m som har parameterene Grdtresh og Detsent 2.6, har det blitt funnet 7 faste parametersett. Med de 7 parametersettene har det blitt oppn˚add gode resultater for deteksjon av linjer med Hough Transformasjonen. Videre legges linjesegmentene som er blitt detektert med de forskjellige parametersettene sammen. Disse 7 parametersettene blir ikke satt av setParam.m funksjonen, men er kommet frem til ved testing p˚a treningsettet. Dermed n˚ar det blir gjort en Hough Transformasjon i denne oppgaven, s˚a menes det at det er blitt gjort med de 7 forskjellige faste paramatrene. Det er laget m-filen HT2012.m som utfører Houg Grd.m med de 7 paramte- trene og legger sammen resultatene fra de ulike Hough Transformene. Alle bilder/bildeblokker i denne oppgaven som det blir gjort en Hough Transformasjon p˚a for ˚a detektere linjer bruker filen HT2012.m. De ulike parametrene kan medføre at flere uønskede linjer blir detektert av Hough Transformasjonen, men det har totalt gitt flere ønskede linjer som er nødvendige videre for algoritmen.

(a) Hough Transform 1. (b) Hough Transform 2. (c) Hough Transform 3.

(d) Alle de tre Hough Transformene lagt sammen.

(e) Forstørret inn p˚a noen av linjedetek- sjonene gjort av Hough Transformen

Figure 21: Illustrasjon som viser de tre forskjellige Hough Transform resultatene, og nederst til venstre det totale resultatet ved ˚a legge sammen de tre øverste resultatene.

(31)

4.5 Morfologi og fjerning av linjesegment basert p˚ a deres lengde

Blokknummer: 10.

Denne blokken mottar de røde og grønne linjesegmentene vist i figur 21 d) fra blokknummer 9.

Ved ˚a studere figur21e) som er forstørret inn p˚a et omr˚ade av linjesegmentene kan det observeres at det er flere linjer som representerer samme linjen som er et resultat etter ˚a lagt sammen flere forskjellige Hough Transformasjoner. Ideelt er det ønskelig at alle linjesegmentene som representerer samme linje skal legges sammen til et linjesegment. Og ofte er det linjesegment som er deler av samme linje som ikke er i kontakt med hverandre.

Et forsøk p˚a ˚a legge sammen linjesegment som representerer samme linje gjøres ved ˚a lage et binært bilde av linjesegmentene, hvor linjesegmentene blir representert med logisk 1-ere. Videre er det da lett ˚a utføre morfologisk lukking p˚a binærbildet. Etter lukkingen har vi ikke helt ’perfekte’ linjer i binærbildet og det trengs derfor en funksjon for ˚a hente ut linjesegment fra 1-er gruppene dannet i binærbildet basert p˚a formen til 1-er gruppene som er dannet. Alt dette blir gjort i funksjonen morph.m.

morph.m:

I denne filen blir linjesegmentene gjort om til et binær bilde. Videre blir det utført en morfologisk lukking som er blitt beskrevet i kapittel2.5.3. For de horisontale linjesegmentene blir det brukt et horisontalt strukturelement kalt BH1 og BH2 i filen setParam.m. For de vertikale linjesegmentene blir det brukt et vertikalt strukturelement kalt BV1 og BV2 i filen setParam.m. Lengdene p˚a strukturelementene blir satt i setParam.m og er basert p˚a bildestørrelsen p˚a bildet som prosesseres, og om bildet er st˚aende eller liggende. Strukturelementet BH1 og BV1 blir brukt i først, mens strukturelementene BH2 og BV2 blir brukt senere i blokknummer 10. De fire strukturelementene som blir brukt er vist i figur25. Denne morfologiske lukkingen resulterer i at linjesegment som er nær hverandre blir koblet sammen alt ettersom hvor stort strukturelementet er. Denne koblingen av ulike elemnter vi f˚ar ved morfologisk lukking er en ønsket effekt. Ved ˚a studere figur22 a) og b) kan det sees at noen linjesegmenter som er nær hverandre har blitt lagt sammen.

Dette er den effekten som ble illustrert i eksempelet om morfologisk lukking i kapittel2.5.3. For denne oppgaven brukes kun binær morfologi og for ˚a kunne utføre morfologien m˚a vi ha linjene omgjort til et binær bilde. Dermed har det blitt laget en funksjon som heter lines2bw.m som lager et binær bilde hvor linjesegmentene blir representert som logisk 1, dette blir illustrert i figur22a).

Funksjonene er basert p˚a at de horisontale og vertikale linjesegmentene separert gjenneom denne prosessen. Etter morfologisk lukkingen har vi resultatet for de horisontale linjesegmentene vist i figur22b). Resultatet fra lukkingen vil vi ha gjort om til linjesegmenter igjen, og det utføres av funksjonen bw2lines.m som kalles i morph.m. Ved ˚a studere figur22c) ser vi det endelige resultatet etter funksjonen morph.m av de vertikal og horisontale linjesegmentene.

(a) De horisontale linjesegmentene gjort om til et binær bilde.

(b) De horisontale linjesegmentene etter morfologisk lukking med parameteren BH1.

(c) Resultat etter morph.m med parametrene BH1 og BV1.

Figure 22: Illustrasjon av noen resultater fra de forskjellige stegene i funksjonen morph.m.

(32)

myClearHlines.m og myClearVlines:

Videre er det ønskelig ˚a fjerne uinteressante linjsegment detektert av Hough Transformen. Ved

˚a studere resultatet etter morph.m22 c) kan det observeres at de minste linjesegmentene ofte er up˚alitelige og har somregel ikke noen sammenheng med andre linjesegment. For ˚a kunne utføre en kraftigere morfologisk lukking for ˚a koble linjesegmenter sammen m˚a de minste og ofte up˚alitelige linjesegmentene fjernes.

I begynnelsen av utviklingen av algoritmen ble det brukt MATLAB’s innebygde funksjon imclear- border.m som fjerner linjesegment i kontakt med rammen til bildet som prosesseres. Etterhvert ble det observert at linjesegment som var i kontakt med rammen kunne være deler av kanter til skiltet som skulle detekteres. For skilt som skal lokaliseres som befinner seg i nærheten av midten, m˚atte potensielle linjesegment til skiltet som er i kontakt med rammen ha en lengde p˚a nesten halvparten av bildestørrelsen. Det ble ogs˚a observert at noen skilt er plassert nær rammen til bildet, men de gangene selve skiltet er nær kanten s˚a virker det som om det er p˚a grunn av at skiltet er s˚a stor i forhold selve til bildet. Dette kan observeres ved ˚a se p˚a gjennom alle bildene som blir testet i denne oppgaven. Videre ble det laget to m-filer som heter myClearHlines.m og myClearVlines.m som er basert p˚a de observasjonene beskrevet.

myClearHlines.m og myClearVlines.m brukes to ganger i algoritmen. Første gangen er her i blokknummer 10 i figur16, etter at den første morfologiske lukkingen.

Form˚alet med funksjonene er som nevnt at de skal prøve ˚a fjerne forskjellige uinterssante linjesegment. For lettere ˚a kunne forklare funksjonene vil figur 23a) bli brukt. Ved ˚a studere figur23 a) kan det observeres to gule horisontale linjer og to grønne vertikale linjer. Dette er grenser satt av parametrene ’dH1’ og ’dH2’ satt i funksjonen setParam.m hvor de grønne vertikale grensene er

’dH1’ og de gule horisontale grensene er ’dH2’. Alle horisontale linjesegment som har pikselverdier innenfor disse grensene og som samtidig har en kortere euklidisk lengde enn ’KH1’ parameteren blir fjernet. Ellers for hele bildet brukes parameteren ’minH1’, som er en euklidisk lengde som horisontale linjesegmentene m˚a være lengre enn for ikke ˚a bli fjernet. De linjesegmentene med rød farge i figur23a) er linjesegmentene som er igjen etter funksjonen myClearHlines.m. De linjseg- mentene med fargen magenta er linjesegment som blir fjernet av myClearHlines.m. Det samme blir gjort i myClearVlines.m bare at den bruker parametrene ’dV1’, ’dV2’, ’KV1’ og ’minV1’, og resultatet ved bruk av den p˚a de vertikale linjesegmentene vises i figur23b).

(a) myClearHlines.m med grenser plottet (b) myClearVlines.m med grenser plottet

Figure 23: Uinteressante linjesegment her markert med fargen magenta blir fjernet.

Etter at myClearHlines.m og myClearVlines.m har blitt brukt er de linjesegmentene som er igjen mer p˚alitelige og vi kan dermed gjøre en ny morphologisk lukking p˚a linjesegmentene med funksjonen morph.m, men med de kraftigere parametre ’BH2’ og ’BV2’. Ved ˚a studere figur24

(33)

ser vi resultatet etter morfologisk lukking med parametrene BH2 og BV2. Dette er det endelige resultatet produsert i blokknummer 10 som sendes videre til blokknummer 11 i figur16.

(a) Resultat etter morph.m med parametrene BH2 og BV2

Figure 24: Resultat som sendes videre til blokknummer 11, etter prosessering av blokknummer 10.

(a) Stukturelement BH1 (b) Stuk- turele- ment BV1

(c) Stuk- turele- ment BV2

(d) Stukturelement BH2

Figure 25: Strukturelementene som brukes av morph.m, og som er blitt satt av setParam.m basert p˚a bildestørrelsen som prosessers.

4.6 Beregning av krysningspunkt

Blokknummer: 11.

I blokknummer 11 i blokkdiagrammet fra figur16 blir det først beregnet krysningspunkt mellom vertikale- og horisontale linjesegment som kan ha en sammenheng. Det blir ikke beregnet krysningspunkt mellom forskjellige vertikale linjesegment selv om de ogs˚a kan krysse hverandre. Alt som blir utført i blokknummer 11 er det funksjonen linjeGrense.m som utfører. Denne funksjonen starter med ˚a beregner alle mulige krysningspunkt mellom vertikale- og horisontale linjesegment.

(34)

Videre fjernes krysningspunkt som er blitt beregnet ut fra linjesegmenter som ikke kan ha sammenheng.

linjeGrense.m

funksjoner som brues av linjeGrense.m:

• linecrossings.m, finner krysningspunktet hvor to vektorer krysser hverandre. Linjesegmentene trenger ikke ˚a krysse hverandre men de blir forlenget slik at de treffer hverandre.

• linesegs2lines.m, lager et linje objekt av linjesegmenter som er p˚a formenrx1, y1, x2, y2s, hvor x₁ ogy₁ er koordinatene til start punktet til et linjesegment, ogx₂ogy₂ er koordinatene til sluttpunktet.

• newlines.m, lager et linjeobjekt ut i fra en vektor og et punkt som vektoren g˚ar gjennom.

• vectangle.m, beregner vinkelen mellom to vektorer.

• vectlength.m, beregner lengden til en vektor.

• linjeGrenseV.m, beregner en minimum- og maximum-grense for hvert vertikalt linjesegment som hvert krysningspunkt produsert av dette linjesegmentet m˚a være innenfor. De krysningspunktene utenfor grensene blir fjernet.

• linjeGrenseH.m, beregner en minimum- og maximum-grense for hvert horisontalt linjesegment som krysningspunkt produsert av dette linjesegmenet m˚a være innenfor. De krysningspunktene utenfor grensene blir fjernet.

• DistBetween2Segment.m, beregner minste mulige distanse mellom to linjesegment.

Ved ˚a sturere figur26a) ser vi en enkel illustrasjon over resultatet av beregning av kryssningspunk- tet mellom to linjesegment. Den bl˚a linjen er det vertikale linjesegmentet og den røde linjen er det horisontale linjesegmentet. De cyan-fargede stiplede linjene er forlengelsen av linjene, og det resulterende krysningspunktet er markert med fargen magenta.

Videre blir resultatet av ˚a beregne krysningspunktene mellom alle de vertikale- og horisontale- linjesegmentene f˚ar vi resultatet vist i figur 26b).

(a) Eksempel p˚a beregning av krysningspunkt mellom et vertikalt- og et horisontalt- linjesegment.

(b) Alle krysningspunkt beregnet mellom alle vertikale- og horisontale-linjesegment. Totalt 170 krysningspunkt.

Figure 26: Illustrasjon over krysningspunktet som blir funnet mellom vertikale- og et horisontale- linjesegment.

Videre i linjeGrense.m fjernes krysningspunkt som er usannsynlinge. De krysningspunktene som er usannsynlige er et resultat av det bare ble sett p˚a to linjesegment seperat om gangen ved

(35)

beregningene. Denne fjerningen av usannsynlige krysningspunkt blir forklart sammen med figur27, hvor det skal finnes grenser til de mulige krysningspunktene som det vertikale linjesegmentet med fargen magenta kan produsere med horisontale linjesegment. Den stiplede cyan fargede linjen viser forlengelsen av det vertikale linjesegmentet som det skal finnes grensene til. De røde horisontale linjesegmentene som er vist er kun de linjesegmentene som har en distanse mindre enn 5 piksler fra det vertikale linjesegmentet. Distansen p˚a 5 piksler er en fast parameter satt i funksjonen. Det er bare disse horisontale linjesegmentene som blir med i beregningen av minimum- og maksimum grense for det vertikale linjesegmentet med fargen magenta. Grensene som har blitt beregnet av funksjonen i dette eksempelet er vist i med grønne sirkler i figur27 a). Det er ogs˚a en fast parameter satt i funksjonen kalt ’overlapp’. Den er et tall p˚a hvor mangen piksler det magenta vertikale linjesegmentet ’er fysiskt videre forbi’ et horisontalt rødt linjesegment før forlengelsen overtar og treffer et rødt horisontalt linjesegment. Er ’overlappen’ mindre enn 4 piksler trekkes grensen tilbake til siste passerte horisontal rød linje. Er ’overlapp’ over 4 piskler som den er her i begge endene av det vertikale linjesegmentet blir grensene satt av første røde linjesegment som den stiplede forlengelsen møter. Dette er for at n˚ar vi fortsetter med den stiplede forlengelsen øker usikkerheten, da den ikke er et fysiskt linjesegment. Den neste horisontale røde linjen som som den stiplede forlengning møter vil ’sperre’ og sette en grense. Dette vises i figur27c) og d), og ved

˚a sammenligne figur c) og d) er ’overlapp-m˚alet’ til det magenta linjesegmentet markert med gul i figur27d). Dette prinsippet blir brukt for alle vertikale og horisontale linjesegment. Og resultatet av dette blir betraktelig mindre antall krysningspunkt som blir vist i figur28. Dette resultatet blir sendt videre til blokknummer 12 i vist figur16.

(a) Alle de røde linjesegmentene har avstand mindre enn fire piksler til det vertikale linjesegmentet.

(b) Maksimum-

grensen forstørret.

(c) Minimum-grensen forstørret.

(d) ’Overlapp’ markert med fargen gul.

Figure 27: Minimum- og maksimum grensene funnet til et av de vertikale linjesegmentet.

Figure 28: Illustrasjon over de krysningspunktet som er igjen etter reduksjon. Totalt 43 krysningspunkt.

(36)

4.7 Fjerning av linjesegment basert p˚ a deres krysningspunkt og lengde

Blokknummer: 12.

Her startes det med først ˚a fjerne linjesegment med funksjonene myClearHlines.m og myClearV- lines.m igjen, men med litt kraftigere parametre satt av setParam.m funksjonen. Etter eventuell fjerning av linjesegment fjernes de krysningspunktene som er beregnet av eventuelle linjesegment som fjernes. Grunnen til at disse kraftigere paramtrene ikke ble brukt første gang av funksjonene myClearHlines.m og myClearVlines.m var for at de linjesegmentene med en lengde opp til 25 piksler detektert av Hough Transformen er veldig up˚alitelige. Derfor m˚atte de fjernes før det ble utført et kraftige morfologisk lukking. Og dessuten kan linjesegmentene være til ’hjelp’ for funksjonene som blir utført i blokknummer 10 i blokkdiagrammet fra figur 16, hvor utregning av minimum- og maksimum-grensene til hvert linjesegment beregnes som er en veldig viktig del av algoritmen.

Derfor blir det ikke utført en kraftigere fjerning av linjer før her i blokknummer 12. Alt dette blir gjort av filen cleanCornerLines.m, som bruker funksjonene myClearHlines.m og myClearVlines.m.

Resultatet etter cleanCornerLines.m vises i figur29a).

(a) Resultat etter cleanCornerLines.m (b) Resultat etter findSingleCorner.m

Figure 29: Illustrasjon av resultater produsert underveis og det endelige resultatet produsert i blokknummer 12 fra blokkdiagrammet.

Videre etterfølges cleanCornerLines.m med funksjonen findSingleCorner.m som først ble utviklet for ˚a fjerne linjesegment som kun hadde blitt med i beregningen av et krysningspunkt. Men etterhvert ble funksjonen utviklet til ˚a fjerne linjesegment som hadde flere krysningspunkt, men kun p˚a en side av linjesegmentet. I og med at vi skal finne et rektanulært skilt kan ikke alle krysningspunktene befinne seg p˚a bare en side av linjesegmentet. Etter utviklingen av funksjonen kan funksjonsnavnet være litt missvisende.

Et annet krav var en minimumavstand mellom krysningspunktene produsert p˚a linjesegmentet inkludert ’forlengelsen’ som ble brukt ved utregning av krysningspunkt. Derfor er det satt noen faste parametre p˚a denne minimumavstanden i setParam.m som kalles ’xdist’ og ’ydist’. Hvor

’xdist’ er en minimum avstand som kreves mellom krysningspunktene p˚a en horisontal linje. Og

’ydist’ er en minimum avstand som kreves mellom krysningspunktene p˚a en vertikal linje. Disse parametrene blir dermed en minimum lengde som det tenkes at et type-skilt kan ha i vertikal og horisontal lengde. Ved ˚a studere figur29b) kan det observeres resultatet etter ˚a ha kjørt funksjonen findSingleCorner.m. Videre sendes resultatet fra findSingleCorner.m til funksjonen grenserMin- Max.m. Funksjonen har forløpig en fast parameter ’Ratio’ som er satt til 0.8. Funksjonen fjerner vertikale linjesegment som befinner seg mer enn parameteren ’Ratio’ utenfor øverste og nederste horisontale linjesegment. Det vil si at linjesegmentets piksler m˚a være 80% utenfor grensene for

˚a bli fjernet. Den fjerner ogs˚a horisontale linjesegment som befinner seg mer enn parameteren

’Ratio’ utenfor det vertikale linjesegmentet til høyre og venstre. I dette eksempelet vil dermed ikke denne funksjonen fjerne noen av de resterende linjesegmentene som var igjen etter funksjo-

(37)

nen findSingleCorner.m. Dermed sendes resultatet vist i figur29b) videre til blokknummer 13 i blokkdiagrammet fra figur16, hvor det skal bli funnet fire potensielle hjørnekordinater til type- skiltet.

4.8 Finne fire potensielle hjørnekoordinater som inneholder type-skiltet.

Blokknummer: 13.

Her skal det finnes fire potensielle hjørnekordinater som inneholder tupe-skiltet. Algoritmen skal resultere i fire potensielle hjørnekoordinater, og den gir ogs˚a ut den stiplede cyan linjen som er plottet mellom de fire hjørenkoordinatene i figur30. Resultatet som er vist i figur30 er beregnet av funksjonen finnROI.m.

finnROI.m:

Det første denne funksjonen gjør er ˚a finne det horisontale linjesegmentet som befinner seg øverste, og s˚a det horisontale linjesegmentet som befinner seg nederst i bildet. Og s˚a finnes de vertikale linjesegmentene som befinner seg lengst til høyre og venstre. Dette gjøres p˚a de linjesegmentene som var igjen etter blokknummer 12 i blokkdiagrammet fra figur16, som er vist i figur29b). Ut i fra de ytterste linjesegmentene funnet blir det søkt om det befinner seg et lengre linjesegmenet ved

˚a g˚a 20 piksler innover mot midten i det omr˚adet som de ytterste linjesegmentene funnet danner.

Dette gjelder for alle bilder som prosesseres. Hvis det finnes lengre linjesegment vil disse velges som den ytterste grensen til skiltet, fordi de lengste linjene har virket som de mest p˚alitelige linjene.

Vi har n˚a de fire ytterste linjesegmentene og beregner de fire potensielle hjørnekoordinatene til type-skiltet. De koordinatene som er blitt funnet blir sjekket at de er innenfor bildestørrelsen. Er de krysningspunktene innenfor bilde-rammen blir dette de fire resulterende hjørnekoordinatene, som det ble i dette eksempelet.

Figure 30: De fire potensielle hjørnekoordinatene produsert automatisk av algoritmen Hvis det viser seg at noen av hjørnekoordinatene funnet har koordinater som befinner seg utenfor rammen til bildet, vil det bli prøvd ˚a finne et linjesegment som erstatter det linjesegmentet som fører til at et koordinatet er utenfor rammen. Dette gjøres ved ˚a søke etter et nytt linjesegment lenger innover mot midten i omr˚adet som var omringet av de ytterste linjesegmentene. [2]

(38)

5 Test av algoritmen

For teste algoritmen har det blitt laget tre stk testsett med 30 forskjellige bilder i hvert sett som er plukket ut fra bilder tildelt av Verico AS. Dette gir totalt 90 ulike bilder som algoritmen testes p˚a.

For ˚a kjøre algoritmen automatisk p˚a alle tre settene med bilder er det laget funksjonen: testsett.m.

Denne funksjonen lagrer de fire koordinatene funnet av algoritmen i en tabell. Til slutt produserer testsett.m figurer av alle bildene med automatisk lokaliserte hjørnekoordinater og manuelt avleste hjørnekoordinater. Det blir ogs˚a plottet stiplede linjer mellom hjørnekoordinatene som gjør det lettere ˚a sammenligne resultatet med fasiten.

De hjørnekoordinatene som er produsert automatisk av algoritmen blir plottet med et bl˚att kryss og en liten gul sirkel for ˚a lettere kunne f˚a øye p˚a hjørnekoordinatene i forskjellige bilder. Det blir ogs˚a plottet en stiplet linje med fargen cyan mellom de automatisk produserte hjørnekoordinatene.

De hjørnekoordinatene som er manuelt avlest som er fasiten blir plottet med et rødt kryss og en liten cyan farget sirkel. Det blir ogs˚a plottet en stiplet linje med fargen magenta mellom de manuelt avleste hjørnekoordinatene.

I figur 31 er det vist et eksempel fra et av testsettene med resultat fra algoritmen plottet sammen med fasit.

Figure 31: Omr˚adet automatisk detektert av algoritmen er markert med en stiplet linje med fargen cyan. Skiltet funnet manuelt er merket med stiplet linje med fargen magenta.

Det vil ogs˚a bli beregnet en rekke verdier for testen. Disse verdiene blir forklart i kapittel 6 sammen med vurderingen av resultatene.

6 Vurdering av resultater.

For ˚a vurdere resultatene til algoritmen blir det beregnet en del verdier til hvert bilde som er blitt utført klassifisering p˚a. Hver piksel i bildet som prossesers kan ha fire utfall ved en klassifisering som blir illustrert med grønn farge i de fire bildene vist i figur 32. Det som i virkeligheten er rammen til skiltet er markert med den røde rammen. Den gule rammen er et eksempel laget for ˚a illustrere en klassifisering gjort av algoritmen, og for ˚a visualisere de fire verdiene TN, FN, FP og TP. Alle verdiene som blir beregnet i dette delkapittelet blir beregnet blir beregnet av funksjonen finnSTAT.m. [17] [18][19] [20]

(39)

• TP - Sanne positive. Dette er antall piksler som er klassifisert som skilt av algoritmen, og som i virkeligheten er det.

• TN - Sanne negative. Dette er antall piksler som er klassifisert som bakgrunn av algoritmen, og som i virkeligheten er bakgrunn.

• FN - Falske negative. Dette er antall piksler som er klassifisert som bakgrunn men som i virkeligheten er en del av skiltet.

• FP - Falske positive. Dette er antall piksler som er klassifisert som skilt, men som i virkeligheten er bakgrunn.

(a) TP, sanne positive (b) FP, falske positive (c) FN, falske negative (d) TN, sanne negative

Figure 32: De fire utfallene en klassifisering kan ha markert med grønn.

Videre ut i fra verdiene TN, FN, FP og TP beregnes seks verdier som kan brukes til ˚a m˚ale hvor god klassifiseringene som er blitt gjort er. Disse verdiene er:

• PPV - Positiv prediktiv verdi, er et tall p˚a antall sanne positive det er i forhold til antallet sanne positve og falske positive. Derfor er det ønskelig at dette forholdet er s˚a nær 1 som mulig. P P V _{T P}^{T P}_{F P}

• NPV - Negativ prediktiv verdi, er et tall p˚a antall sanne negative i forhold til antallet sanne negative og falske negative. Derfor er det ønskelig at dette forholdet er s˚a nær 1 som mulig.N P V _{F N}^{T N}_{T N}

• FDR - Falsk oppdagelse rate, er et tall p˚a antall falske negative det er i forhold til antallet sanne positive og falske positive. Derfor er det ønskelig at dette forholdet er s˚a nær 0 som mulig.F DR _{F P}^{F P}_{T P}

• Sensitivitet - Er et tall p˚a hvor mangen piksler som er blitt korrekt klassifisert til skilt som i virkeligheten er skilt. Derfor er det ønskelig at dette forholdet er s˚a nær 1 som mulig.

Sensitivitet _{T P}^{T P}_{F N}

• Spesifisitet - Er et tall p˚a hvor mangen piksler som er blitt korrekt klassifisert til bakgrunn i forhold til totalt antall piksler som i virkeligheten er bakgrunn. Derfor er det ønskelig at dette forholdet er s˚a nær 1 som mulig. Spesifisitet_{F P}^{T N}_{T N}

• ACC - er et tall p˚a hvor mangen av alle pikslene som er blitt korrekt klassifisert i forhold til totalt antall piksler. ACC m˚a ikke sees p˚a alene, men i sammenhenge med spesifisitet- og sensitivitet-verdiene, fordi ACC verdien kan være god uten at noe av skiltet er detektert i det hele tatt. Det er ønskelig at ACC verdien er s˚a nær 1 som mulig. ACC_p_{T P} ^p_{F N}^{T N} _{T N}^{T P}^q_{F P}_q.