INF2310 vår 2012 - Løsningshint 12

Oppgave 1 - Erosjon og avrunding

1. Resultatet blir:
   
2. Konkave og rettvinklede hjørner blir avrundet når vi eroderer med et rundt strukturelement, mens konvekse og rettvinklede hjørner forblir rettvinklet etter en slik erosjon.

Oppgave 2 - Region-fylling med dilasjon

1. Etter X5 skjer det ingen endring. Unionen av f og X5 er et binært bilde med en fylt region som har samme omriss som bildet f.
2. Etter X8 skjer det ingen endring. Denne gangen blir hele øvre, høyre hjørne utfylt, noe som ikke er ønskelig ettersom det er utenfor omrisset.
3. Grunnen til at dette skjer er at omrisset (i bildet f) bruker 8-naboskap, mens strukturelementet S2 antar at omrisset bruker 4-naboskap.

Oppgave 3 - Oppslagstabeller og "hit-or-miss"-transformasjonen

Siden "input-bildene" til "hit-or-miss"-transformasjonen er binære, vil hvert piksel kun ha to mulige tilstander (som er 0 eller 1). For en operasjon som utelukkende benytter et lokalt 3x3-område av et binært bilde, vil det dermed være maksimalt 2^3*3 = 2⁹ = 512 mulige "input-tilstander". Det vil derfor være mulig å beregne utverdien av denne operasjonen, som her er "hit-or-miss"-transformasjonen med et spesifikt strukturelement, for alle de 512 mulige "input-tilstandene", legge dem i en tabell, og kun benytte enkle oppslag i denne tabellen for å utføre operasjonen på et vilkårlig, binært bilde.

En teknisk detalj er hvordan man strukturerer oppslagstabellen for å lage en (helst beregningsmessig effektiv) overgang fra et 3x3-vindu med binære verdier til en indeks i oppslagstabellen. For dette kan vi velge en vilkårlig, men deretter fast, sortering av posisjonene i 3x3-vinduet, og nummerere disse posisjonene fra 0 til 8. F.eks. kan vi starte med første rad og gi disse tre posisjonene numrene 0 til 2 fra venstre til høyre, deretter gi de tre posisjonene i andre rad numrene 3 til 5 fra venstre til høyre, for til slutt å gi de tre posisjonene i tredje og siste rad numrene 6 til 8 fra venstre til høyre. Dersom vi kaller disse posisjonsnumrene for n, og de tilhørende verdiene i et konkret 3x3-vindu for c_n, vil en mulig strukturering av oppslagstabellen være å konvertere hvert konkrete 3x3-vindu med binære verdier til en indeks i oppslagstabellen ved følgende formel: c₀ * 2⁰ + c₁ * 2¹ + ... + c₈ * 2⁸. Dette gir indekser fra og med 0 til og med 511, men for å benytte én-indeksering er det bare å legge til +1 i indeksformelen i forrige setning. Denne overgangen/konverteringen vil være beregningsmessig effektiv (dersom man bruker bitskifting).

Det kan forøvrig nevnes at den foreslåtte overgangen/konverteringen fra forrige avsnitt kun er å velge en sortering av posisjonene i 3x3-vinduet, skrive hvert konkrete 3x3-vindu (med binære verdier) som et binært tall (i henhold til den sorteringen), for så å skrive dette binære tallet som et desimaltall. Dette desimaltallet brukes som indeksen i oppslagstabellen.

Oppgave 4 - Oppgaver fra læreboka

9.7a: Vi tenker oss at vi dilaterer med et strukturelement som ikke er en linje. Resultatet av gjentatte dilasjoner vil da være at objektene i bildet vokser uten noen grense (i en praktisk implementasjon vil man noen ganger begrense hvert dilasjonsresultat av bilderammen til bildet som ble benyttet, i et slikt tilfelle vil objektene vokse og fylle hele bildet). Dersom vi ser på spesieltilfellet at strukturelementet er en linje, vil gjentatte dilasjoner gjøre at objektene vokser uten noen grense (eventuelt fyller hele bildet) i linjens retning - dersom det finnes linjer med denne orienteringen som ikke har noen objektpiksler/forgrunnspiksler i det opprinnelige bildet, vil disse linjene forbli utelukkende bestående av bakgrunnspiksler etter den gjentatte dilasjonen.

9.7b: Et 1x1-bilde med én forgrunnspiksel. Det vil generelt holde for alle bilder så lenge det finnes minst én forgrunnspiksel i bildet.

9.8a: Resultatet av gjentatte erosjoner vil være den tomme mengden (eventuelt et bilde uten forgrunnspiksler, avhengig av den praktiske implementasjonen), altså akkurat omvendt som i oppgave 9.7a. Denne gangen trenger vi ikke spesialbehandle tilfellet der strukturelementet er en linje, så lenge strukturelementet ikke er det trivielle ettpunktselementet (som oppgaveteksten sier at vi skal anta det ikke er), blir resultatet av den gjentatte erosjonen det samme.

9.8b: Svaret vil alltid holde, uansett hvor lite eller stort bilde måtte være.

9.18: Objektene blir nøyaktig bevart fordi de har lik form/geometri som strukturelementet.

9.19: Bruker T-en med et én-piksels omriss av bakgrunnspiksler som strukturelement. Origo defineres til å være i midten av strukturelementet. Resultatet etter "hit-or-miss"-transformasjon av det oppgitte bildet vil da bestå av kun én objektspiksel/forgrunnspiksel, og denne vil ligge midt i bildet, som er midt i T-en i det opprinnelige bildet.

9.21a: Resultatet vil bli komplementet av omrisset, dvs. et bilde som består bakgrunnspiksler på omrisset og ellers bare forgrunnspiksler. (Dersom omrisset bruker 4-naboskap og vi benytter det plussformede strukturelementet av størrelse 3x3, kan vi i noen tilfeller få ett av to andre resultater; 1) hvis vi starter i et punkt der 4-naboene er enten omrisspiksler eller piksler på innsiden av omrisset, vil resultatet av region-fyllingen bli som ønskelig, og 2) hvis vi starter i et punkt der 4-naboene er enten omrisspiksler eller piksler på utsiden av omrisset, vil resultatet av region-fyllingen bli som i oppgave 9.21b, dvs. komplementet av unionen mellom omrisset og det region-fylte bildet.)

9.21b: Resultatet vil bli komplementet av unionen mellom omrisset og det region-fylte bildet. Det er akkurat dette vi benytter oss av i den helautomatiske hullfyllingsmetoden (se s. 35 i forelesningsnotatet), bare at denne metoden er rafinert slik at vi kan droppe antagelsen om at ingen av omrissets piksler ligger på bildekanten.

9.22a: Omrisset vil da kun være sammenhengende ved bruk av 8-naboskap, og ikke ved bruk av 4-naboskap slik det er når vi benytter strukturelementet i figur 9.13(b).

9.22b: Dette strukturelementet antar at omrisset bruker 4-naboskap. Dersom dette ikke er tilfelle vil region-fyllingen feile (se oppgave 2).

9.27: Med et én-piksels strukturelement der pikselen er en forgrunnspiksel, vil verken erosjon eller dilasjon endre bildet. Det eneste disse operasjonene eventuelt kan gjøre er å translatere bildet, og denne translasjonen vil være gitt ved avstanden mellom strukturelementets origo og den ene pikselen som strukturelementet består av.