INF2310 vår 2014 - Løsningshint 12

Oppgave 1 - Erosjon og avrunding

1. Resultatet blir:
   
2. Konkave hjørner blir avrundet når vi eroderer med et sirkulært strukturelement, mens konvekse hjørner bevarer sin opprinnelige form 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 det vi betrakter som omrisset.
3. Omrisset (i bildet f) er kun lukket dersom vi bruker 8-tilkobling, mens strukturelementet S2 antar at omrisset er lukket ved bruk av 4-tilkobling.

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

Siden "input-bildene" til "hit-or-miss"-transformasjonen er binære, vil hver 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-naboskapet, 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 3x3-vindu for c_n, vil en mulig strukturering av oppslagstabellen være å konvertere hvert mulige 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 i forrige avsnitt kun er å velge en sortering av posisjonene i 3x3-naboskapet, skrive hvert mulige 3x3-vindu (med binære verdier) som et binært tall (i henhold til den sorteringen), for så å skrive dette binære tallet i titallsystemet. Dette desimale tallet brukes som indeksen i oppslagstabellen.

Oppgave 4 - Oppgaver fra læreboka

9.6:

9.7a: La oss først anta at vi dilaterer med et strukturelement som ikke er en linje (og selvsagt heller ikke et enkelt punkt ettersom dette står i oppgaveteksten). 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 en 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 inn-bildet måtte være.

9.17: (a) viser erosjonen av inn-bildet og strukturelementet, (b) viser dilasjonen av (a) og strukturelementet (som er åpningen av inn-bildet og strukturelementet), (c) viser dilasjonen av (b) og strukturelementet, og (d) viser erosjonen av (c) og strukturelementet (som er lukkingen av (b) og strukturelementet). Merk at den første erosjonen fjerner forgrunnstøypikslene (utenom deler av forgrunnstøypikslene som tilkoblet rektangelet), men krymper rektangelet, mens den etterfølgende dilasjonen gjenskaper rektangelets opprinnelige størrelse utenom at hjørnene (som er konvekse) blir avrundet. Den etterfølgende (den andre) dilasjonen fjerner bakgrunnstøypikslene, men utvider rektangelet (og avrunder forgrunnstøyen som er tilkoblet rektangelet), mens den etterfølgende (den andre) erosjonen gjenskaper rektangelets opprinnelige størrelse.

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-tilkobling 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-tilkobling, og ikke ved bruk av 4-tilkobling slik det er når vi benytter strukturelementet i figur 9.13(b) (se s. 12 i forelesningsnotatet).

9.22b: For at region-fyllingen skal bli som ønskelig må omrisset være lukket ved bruk av 4-tilkobling dersom vi benytter det kvadratiske 3x3-strukturelementet. Dersom dette ikke er tilfelle vil region-fyllingen feile (se oppgave 2).

9.27: Med et ett-punkts strukturelement der punktet er et element (har verdi 1), 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 forflytningsvektoren mellom strukturelementets origo og det ene punktet som strukturelementet består av.