INF2310 - Vår 2018

INF2310 vår 2018 - Løsningshint 5

Oppgave 1 - 1D-konvolusjon av to filtre

g = h * f = [1 2 1] * [1 3 4 3 4] = [1 5 11 14 14 11 4]

Oppgave 2 - 2D-konvolusjon

Ut-bildet g = h * f blir:

2 7 10 9 4 1
2 9 15 17 10 4
2 16 28 33 19 7
6 15 30 35 26 11
6 13 25 27 20 8
6 6 12 11 11 5

Oppgave 3 - Middelverdifiltrering

La oss betegne bildet som f og 3x3-middelverdifilteret som h.

  1. Siden konvolusjon er assosiativt er h*(h*f) = (h*h)*f. Altså vil filteret h*h gi samme resultat ved én konvolusjon, der h*h er 1/81 ganger:
    1 2 3 2 1
    2 4 6 4 2
    3 6 9 6 3
    2 4 6 4 2
    1 2 3 2 1
    Ja, filteret er separabelt. Ved bruk av at konvolusjon er kommutativt og assosiativt, så finner vi at filteret kan separeres i:

     
  2. En kombinasjon av separable filtre trenger ikke å være separabelt. Eksempelvis er summen av de to separable konvolusjonsfiltrene:
    0 0 0
    1 1 1
    0 0 0
    og
    0 1 0
    0 1 0
    0 1 0
    ikke separabelt.
    Konvolusjon av separable filtre gir derimot alltid et nytt filter som er separabelt. Dette kan vi skjønne ved å innse at fremgangsmåten i deloppgaven over er generelt gyldig for få finne to 1D-filtre som konvolvert gir konvolusjonen av to separable filtre.

Oppgave 4 - Bilderandproblemet

Fordelen med speilende indeksering er at det utvidede inn-bildet har en glatt overgang mellom det opprinnelige inn-bildet og den utvidede delen - faktisk er alle første pikselverdier i den utvidede delen akkurat de samme som pikselverdien til sin nærmeste nabo innenfor det opprinnelige inn-bildet. I tillegg vil et naboskap rundt et piksel langs den opprinnelige bilderanden inneholde samme pikselverdier på begge sider av randen - utvidelsen har altså ikke innført nye lokale pikselverdier eller en helt annen fordeling av lokale pikselverdier (sistnevnte vil bl.a. være tilfelle for utvidelse ved bruk av nærmeste pikselverdi).

Ulempen med sirkulær indeksering er at den kan innføre veldig skarpe intensitetskanter i overgangen mellom det egentlige inn-bildet og den utvidede delen. Detter skjer dersom høyre og venstre eller øvre og nedre kant i den opprinnelige bildet er veldig ulike. Dersom det ikke skal være noen overgang må pikselverdiene langs høyre kant være identiske som pikselverdiene langs venstre kant, og tilsvarende langs øvre og nedre kant.

PS: Senere i emnet vil vi se at sirkulær indeksering blir implisitt brukt når vi bruker Fourier-transformen til filtrering. Siden dette ofte ikke er ønskelig behandling av bilderandproblemet, vil vi da se at vi på bekostning av litt ekstraarbeidet kan få samme ut-bilde ved bruk av Fourier-transformen som uten, uavhengig av hvilken behandling av bilderandproblemet vi velger å bruke.

Oppgave 5 - Medianfiltrering

  1. Resultatet av 3x3-medianfiltreringen:
    0 0 0 0 0 0 0 0
    0 1 0 1 0 1 0 0
    0 1 0 0 0 0 0 0
    0 1 0 0 0 1 1 0
    0 0 0 0 0 0 0 0

    Bemerkning: Dette resultatet er rett og slett dårlig.

  2. Resultatet av 1x3-medianfiltreringen:
    0 1 1 1 1 1 1 0
    0 0 0 0 0 0 0 0
    0 1 0 0 0 0 0 0
    0 1 0 0 0 0 0 0
    0 0 0 1 1 1 1 1

    Bemerkning: Med et horisontalt naboskap behandles horisontale linjer godt, men vertikale linjer behandles dårlig.

  3. Resultatet av 3x1-medianfiltreringen:
    0 0 1 0 0 0 1 0
    1 0 1 0 0 0 1 0
    1 0 1 0 0 0 1 0
    1 0 1 0 0 0 1 0
    1 0 0 0 0 0 1 0

    Bemerkning: Med et vertikalt naboskap behandles vertikale linjer godt, men horisontale linjer behandles dårlig.

  4. Ettersom verken 3x1-medianfiltreringen av det 1x3-medianfiltrerte bildet i løsningen til deloppgave 2 eller 1x3-medianfiltreringen av det 3x1-medianfiltrerte bildet i løsningen til deloppgave 3 gir det 3x3-medianfiltrerte bildet i løsningen til deloppgave 1, så ser vi at 3x3-medianfilteret ikke kan separeres i 1x3-medianfilteret og 3x1-medianfilteret. Generelt er ikke medianfiltre separable, men man kan likevel lage hurtige implementasjoner av medianfiltrering, se side 49 i forelesning 6.

Oppgave 6 - Et smartere median-basert filter?

Det er enkelt å lage seg binære test-bilder av et hjørne, en tynn linje og kombinasjonen av de to:

  • Hjørne:
    0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0
    0 0 0 0 1 1 1 1
    0 0 0 0 1 1 1 1
    0 0 0 0 1 1 1 1
    0 0 0 0 1 1 1 1

     
  • Tynn linje:
    0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0
    1 1 1 1 1 1 1 1
    0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0

     
  • Kombinasjonen av et hjørne og en tynn linje:
    0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0
    0 0 0 0 1 1 1 1
    0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0

Dersom vi utfører den foreslåtte filtreringen på hvert av disse test-bildene ser vi at ut-bildet blir identisk som inn-bildet (dersom vi ser bort fra bilderandproblemet). Vi ser dermed at det foreslåtte 5x5-filteret bevarer både hjørner og tynne linjer, og til og med kombinasjonen av disse.

PS: Resultatet og konklusjonen hadde vært identisk dersom vi hadde brukt spissere eller flatere hjørner, eller om vi hadde brukt roterte hjørner eller linjer.

Implementasjonsbemerkning: Det foreslåtte filteret består tilsynelatende av mange operasjoner, men siden det er enkelt og raskt å beregne minimumene og maksimumene og medianen bare beregnes av 5 verdier, så vil filtreringen både være enkel å implementere og hurtig å eksekvere.

Publisert 27. feb. 2018 14:47 - Sist endret 27. feb. 2018 14:47
Del på e-post