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 23*3 = 29 = 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 cn, 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: c0 * 20 + c1 * 21 + ... + c8 * 28. 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.

Publisert 20. jan. 2014 08:47 - Sist endret 5. mai 2014 15:16