Oppgave 1 - 1D-konvolusjon av to filtre
a)
\( f \stackrel{\text{full}}{\ast} w = \left[ \begin{array}{ccccccc} 1 & 5 & 11 & 14 & 14 & 11 & 4 \end{array} \right].\)
b)
\( f \stackrel{\text{valid}}{\ast} w = \left[ \begin{array}{ccccccc} 11 & 14 & 14 \end{array} \right].\)
c)
\( f \stackrel{\text{same}}{\ast} w = \left[ \begin{array}{ccccccc} 5 & 11 & 14 & 14 & 11 \end{array} \right].\)
Oppgave 2 - 2D-konvolusjon
a)
\( f \stackrel{\text{full}}{\ast} w = \left[ \begin{array}{cccccc} 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 \end{array} \right]. \)
b)
\(f \stackrel{\text{valid}}{\ast} w = \left[ \begin{array}{cc} 28 & 33 \\ 30 & 35 \end{array} \right].\)
c)
\(f \stackrel{\text{same}}{\ast} w = \left[ \begin{array}{cccc} 9 & 15 & 17 & 10 \\ 16 & 28 & 33 & 19 \\ 15 & 30 & 35 & 26 \\ 13 & 25 & 27 & 20 \\ \end{array} \right].\)
Oppgave 3 - Middelverdifiltrering
La f vere input bildet og w middelverdifilteret.
a)
Sidan konvolusjonsoperasjonen er assosiativ, s? er \(w \ast (w \ast f) = (w \ast w) \ast f\). Dette betyr at ein konvolusjon med \(w\ast w\) gir samme resultat som to separate konvolusjonar med \(w\)
\(w \ast w = \frac{1}{9} \left[ \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array} \right] \ast \frac{1}{9} \left[ \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array} \right] = \frac{1}{81} \left[ \begin{array}{ccccc} 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 \end{array} \right].\)
b)
Konvolusjonsoperatoren er assosiativ og kommutativ, s? filteret kan bli separert i
\(\begin{aligned} w \ast w = \frac{1}{9} \left[ \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array} \right] \ast \frac{1}{9} \left[ \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array} \right] &= \frac{1}{3} \left[ \begin{array}{c} 1 \\ 1 \\ 1 \end{array} \right] \ast \frac{1}{3} \left[ \begin{array}{ccc} 1 & 1 & 1 \end{array} \right] \ast \frac{1}{3} \left[ \begin{array}{c} 1 \\ 1 \\ 1 \end{array} \right] \ast \frac{1}{3} \left[ \begin{array}{ccc} 1 & 1 & 1 \end{array} \right] \\ &= \frac{1}{3} \left[ \begin{array}{c} 1 \\ 1 \\ 1 \end{array} \right] \ast \frac{1}{3} \left[ \begin{array}{c} 1 \\ 1 \\ 1 \end{array} \right] \ast \frac{1}{3} \left[ \begin{array}{ccc} 1 & 1 & 1 \end{array} \right] \ast \frac{1}{3} \left[ \begin{array}{ccc} 1 & 1 & 1 \end{array} \right] \\ &= \frac{1}{9} \left[ \begin{array}{c} 1 \\ 2 \\ 3 \\ 2 \\ 1 \end{array} \right] \ast \frac{1}{9} \left[ \begin{array}{ccccc} 1 & 2 & 3 & 2 & 1 \end{array} \right]. \end{aligned}\)
c)
Ein kombinasjon av separable filtre er generelt ikkje separable. T.d. er summen av filtra
\(w_1 = \left[ \begin{array}{ccc} 0 & 0 & 0 \\ 1 & 1 & 1 \\ 0 & 0 & 0 \end{array} \right] \)
og
\(w_2 = \left[ \begin{array}{ccc} 0 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \end{array} \right]\)
ikkje separabel.
d)
Resultatet av ein konvolusjon av to separable filter er alltid separabel.
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
a)
\( g = \left[ \begin{array}{cccccccccc} 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 \\ \end{array} \right]. \)
Dette resultatet er rett og slett d?rlig.
b)
\(g = \left[ \begin{array}{cccccccccc} 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 \\ \end{array} \right].\)
Med eit horisontalt filter, s? vert horisontale kanter behandla bra og vertikale kanter mindre bra.
c)
\( g = \left[ \begin{array}{cccccccccc} 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 \\ \end{array} \right].\)
Med eit vertikalt filter, s? vert vertikale kanter behandla bra og horisontale kanter mindre bra.
d)
Ettersom verken 3x1-medianfiltreringen av det 1x3-medianfiltrerte bildet i l?sningen til deloppgave b) eller 1x3-medianfiltreringen av det 3x1-medianfiltrerte bildet i l?sningen til deloppgave c) gir det 3x3-medianfiltrerte bildet i l?sningen til deloppgave a), 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, sj? 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:
a)
\(\begin{array}{|c|c|c|c|c|c|c|c|} \hline 0 & 0 & 0 & 0\\ \hline 0 & 0 & 0 & 0\\ \hline 0 & 0 & 1 & 1\\ \hline 0 & 0 & 1 & 1\\ \hline \end{array}\)
b)
\(\begin{array}{|c|c|c|c|c|c|c|c|} \hline 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 0 \\ \hline 1 & 1 & 1 & 1 \\ \hline 0 & 0 & 0 & 0 \\ \hline \end{array}\)
c)
\(\begin{array}{|c|c|c|c|c|c|c|c|} \hline 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 1 & 1 \\ \hline 0 & 0 & 0 & 0 \\ \hline \end{array}\)
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.