Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Pietrzak
Akwizycja
obrazów i
sygnałów Cyfrowe przetwarzanie sygnałów i obrazów
Dyskretyzacja i
kwantyzacja
Typy
transformacji
Grzegorz Pietrzak
obrazów
Histogram i
operacje na
histogramie Wydział Elektroniki Politechniki Wrocławskiej
Dyskretna
transformacja
Fouriera
09.11.2010
Filtry lokalne
Progowanie
Wykrywanie
krawędzi
Analiza ruchu
Outline
Cyfrowe
przetwarzanie
sygnałów i
1 Akwizycja obrazów i sygnałów
obrazów
Grzegorz
Pietrzak
2 Dyskretyzacja i kwantyzacja
Akwizycja
obrazów i
3 Typy transformacji obrazów
sygnałów
Dyskretyzacja i
kwantyzacja
4 Histogram i operacje na histogramie
Typy
transformacji
obrazów
5 Dyskretna transformacja Fouriera
Histogram i
operacje na
histogramie
6 Filtry lokalne
Dyskretna
transformacja
7 Progowanie
Fouriera
Filtry lokalne
8 Wykrywanie krawędzi
Progowanie
Wykrywanie
krawędzi
9 Analiza ruchu
Analiza ruchu
Petla sterowania
Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Pietrzak
Akwizycja
obrazów i
sygnałów
Dyskretyzacja i
kwantyzacja
Typy
transformacji
obrazów
Histogram i
operacje na
histogramie
Dyskretna
transformacja
Fouriera
Filtry lokalne
Progowanie
Wykrywanie
krawędzi
Rysunek: Pętla sterowania z wykorzystaniem systemu wizyjnego
Analiza ruchu
Definicja
Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Pietrzak
Akwizycja - przetworzenie obrazu obiektu fizycznego (f(x,y)) do
Akwizycja postaci zbioru danych dyskretnych (obraz cyfrowy) nadajÄ…cych
obrazów i
sygnałów się do dalszego przetwarzania. Elementy procesu akwizycji:
Dyskretyzacja i
Oświetlenie obrazu.
kwantyzacja
Typy
Formowanie obrazu (optyczne).
transformacji
obrazów
Detekcja obrazu.
Histogram i
operacje na
Formowanie wyjściowego sygnału z urządzenia (kamera,
histogramie
Dyskretna skaner)
transformacja
Fouriera
Obraz podczas tego procesu przyjmuje formy:
Filtry lokalne
optyczna -> elektryczna -> cyfrowa
Progowanie
Wykrywanie
krawędzi
Analiza ruchu
Dyskretyzacja
Cyfrowe
przetwarzanie
sygnałów i
Dyskretyzacja (próbkowanie, kwantyzacja w czasie) - proces
obrazów
Grzegorz tworzenia sygnału dyskretnego, reprezentującego sygnał ciągły
Pietrzak
za pomocą ciągu wartości nazywanych próbkami
Akwizycja
obrazów i Dyskretyzacja idealna
sygnałów
Dyskretyzacja i
kwantyzacja
f (v, w) = f (x, y)´(v - x, w - y)dxdy (1)
Typy
RxR
transformacji
obrazów
Gdzie RxR - siatka, w której węzłach pobieramy próbki
Histogram i
operacje na
histogramie Dyskretyzacja rzeczywista
Dyskretna
transformacja
Fouriera
f (v, w) = f (x, y)Å‚(v - x, w - y)dxdy (2)
Filtry lokalne
RxR
Progowanie
Wykrywanie Gdzie ł to funkcja próbkująca wynikająca z charakterystyki
krawędzi
urzÄ…dzenia
Analiza ruchu
Odtwarzanie sygnału ciągłego
Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Pietrzak
Twierdzenie Kotielnikowa-Shannona: Sygnał ciągły może być
Akwizycja
ponownie wiernie odtworzony z sygnału dyskretnego, jeśli był
obrazów i
sygnałów
próbkowany z częstotliwością co najmniej dwa razy większą od
Dyskretyzacja i
granicznej częstotliwości swego widma (tak zwany warunek
kwantyzacja
Nyquista).
Typy
transformacji
Inaczej: Sygnał x(t) jest równoważny zbiorowi swoich próbek
obrazów
1
odległych od siebie o stały przedział T d"
Histogram i
2fm
operacje na
histogramie Ém to taka czÄ™stotliwość, powyżej której widmo sygnaÅ‚u
Dyskretna
próbkowanego zanika (X (É) = 0 dla É > Ém)
transformacja
Fouriera
Jak widać, sygnał da się odpowiednio spróbować tylko wtedy, gdy
Filtry lokalne
jego widmo jest skończone.
Progowanie
Wykrywanie
krawędzi
Analiza ruchu
Aliasing
Cyfrowe
przetwarzanie Powyższy warunek nazywany jest warunkiem Nyquista
sygnałów i
obrazów Jeśli nie jest spełniony, może wystąpić zjawisko aliasingu -
Grzegorz
pojawiania się w sygnale składowych o błędnych
Pietrzak
częstotliwościach.
Akwizycja
obrazów i
sygnałów
Dyskretyzacja i
kwantyzacja
Typy
transformacji
obrazów
Histogram i
operacje na
histogramie
Dyskretna
transformacja
Fouriera
Filtry lokalne
Progowanie
Aby uniknąć tego zjawiska zwiększa się częstotliwość
Wykrywanie
krawędzi próbkowania lub ogranicza częstotliwość sygnału wejściowego za
Analiza ruchu
pomocą filtrów dolnoprzepustowych (o maksymalnie stromych
zboczach).
Kwantyzacja
Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Pietrzak
Kwantyzacja równomierna i nierównomierna
Akwizycja
obrazów i
Miary jakości kwantyzatora:
sygnałów
"
Dyskretyzacja i
Å›redniokwadratowy bÅ‚Ä…d kwantyzacji ´2 = (x - Q(x))f (x)dx,
kwantyzacja q
-"
Typy
gdzie Q(x) jest kwantyzatorem
transformacji
obrazów
(Å›rednia) dÅ‚ugość sÅ‚owa kodowego - przy zadanym ´2
q
Histogram i
m bi
operacje na
histogramie
R = l2 f (x)dx, l - długość słowa kodowego
i=1
bi -1
Dyskretna
transformacja
odpowiadającego i-temu przedziałowi (i-tej wartości
Fouriera
rekonstrukcji)
Filtry lokalne
Progowanie
Wykrywanie
krawędzi
Analiza ruchu
Typy transformacji obrazów
Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Pietrzak
Akwizycja
obrazów i
sygnałów
Typy transformacji obrazów
Dyskretyzacja i
kwantyzacja
punktowe
Typy
transformacji
lokalne
obrazów
Histogram i
globalne
operacje na
histogramie
Dyskretna
transformacja
Fouriera
Filtry lokalne
Progowanie
Wykrywanie
krawędzi
Analiza ruchu
Histogram
Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Pietrzak
Histogram jest to takie przedstawienie empirycznego rozkładu
Akwizycja
obrazów i
zmiennej, które dzieli wartości cechy na przedziały i
sygnałów
Dyskretyzacja i przyporządkowuje każdemu z tych przedziałów liczbę wystąpień
kwantyzacja
(ew. gęstość prawdopodobieństwa) wartości zmiennej w tym
Typy
transformacji
przedziale.
obrazów
Histogram i
-1
operacje na
Ogólnie histogram jest opisany wzorem H(z) = Çf dxdy
histogramie
Cechy Histogramu: średnia, dyspersja, asymetria, energia,
Dyskretna
transformacja
entropia
Fouriera
Filtry lokalne
Progowanie
Wykrywanie
krawędzi
Analiza ruchu
Operacje na histogramie
Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Pietrzak
H(z) - histogram, G(z) - histogram po transformacji T
Akwizycja
obrazów i
v = T (z) - funkcja transformujÄ…ca
sygnałów
Dyskretyzacja i 0 d" z d" 1, 0 d" v d" 1
kwantyzacja
dz
G(v) = [H(z) ]z=T -1
(v)
dv
Typy
transformacji
Przykładowe operacje:
obrazów
Histogram i RozciÄ…ganie histogramu
operacje na
histogramie
Normalizacja histogramu
Dyskretna
transformacja
Wyrównywanie histogramu (equalization)
Fouriera
Filtry lokalne
Progowanie
Wykrywanie
krawędzi
Analiza ruchu
Dyskretna transformacja Fouriera
Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Pietrzak
Dyskretna transformata Fouriera (DFT z ang. Discrete Fourier
Akwizycja
obrazów i
Transform) jest transformatą Fouriera wyznaczoną dla sygnału
sygnałów
próbkowanego, a więc dyskretnego. DFT przekształca skończony
Dyskretyzacja i
kwantyzacja
ciąg próbek sygnału (a0, a1, a2, . . . , aN-1), ai " R w ciąg
Typy
transformacji harmonicznych (A0, A1, A2, . . . , AN-1), Ai " C zgodnie ze wzorem:
obrazów
N-1
2Ä„
-kn
Histogram i
N
Ak = anwN , 0 k N - 1, wN = ei
operacje na
n=0
histogramie
N-1
Dyskretna
1 kn
Przekształcenie odwrotne: an = Ak wN , 0 n N - 1
transformacja
N
Fouriera
k=0
Filtry lokalne
Progowanie
Wykrywanie
krawędzi
Analiza ruchu
Przypadek dwuwymiarowy
Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Pietrzak
Akwizycja
obrazów i
sygnałów
Dwuwymiarowe przekształcenie Fouriera w punkcie (m,n):
Dyskretyzacja i N-1
-ny
M-1
-mx
kwantyzacja
V (m, n) = U(x, y)wN wM
x=0
Typy y=0
transformacji
Przekształcenie odwrotne:
obrazów
N-1 M-1
ny
Histogram i 1 mx
U(x, y) = V (m, n)wN wM
operacje na
NM
histogramie
n=0 m=0
Dyskretna
transformacja
Fouriera
Filtry lokalne
Progowanie
Wykrywanie
krawędzi
Analiza ruchu
FFT
Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Obliczanie DFT wg tego wzoru ma złożoność obliczeniową O(N2)
Pietrzak
Istnieje algorytm SzybkiejTransformacjiFouriera, który pozwala na
Akwizycja
obliczenie transformaty w czasie O(Nlog2N) Algorytmy (jak
obrazów i
sygnałów
algorytm Cooleya-Tukeya) obliczajÄ…ce szybkÄ… transformacjÄ™
Dyskretyzacja i
Fouriera bazują na metodzie dziel i zwyciężaj rekurencyjnie
kwantyzacja
Typy dzieląc transformatę wielkości N = N1N2 na transformaty
transformacji
obrazów wielkości N1 i N2 z wykorzystaniem O(N) operacji mnożenia.
Histogram i
NajpopularniejszÄ… wersjÄ… FFT jest FFT o podstawie 2. Jest to
operacje na
histogramie
bardzo efektywna operacja, jednak wektor próbek wejściowych
Dyskretna
(spróbkowany sygnał) musi mieć długość N = 2k , gdzie k to
transformacja
Fouriera
pewna liczba naturalna. Wynik otrzymuje siÄ™ na drodze
Filtry lokalne
schematycznych przekształceń, opartych o tak zwane struktury
Progowanie
motylkowe.
Wykrywanie
krawędzi
Analiza ruchu
Zastosowania DFT w filtracji
Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Pietrzak
Akwizycja
obrazów i
sygnałów
Za pomocą odpowiednich masek nałożonych na widmo sygnału i
Dyskretyzacja i
kwantyzacja
transformacji odwrotnej możemy wyciąć z obrazu pewne
Typy
składowe.
transformacji
obrazów
Filtry górno, dolno i pasmowo przepustowe pozwalają np. na
Histogram i
redukcję szumu czy wykrywanie krawędzi.
operacje na
histogramie
Dyskretna
transformacja
Fouriera
Filtry lokalne
Progowanie
Wykrywanie
krawędzi
Analiza ruchu
Splot
Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Pietrzak
Akwizycja
obrazów i
sygnałów
Splot jest to sposób łączenia 2 sygnałów w celu utworzenia
Dyskretyzacja i
kwantyzacja trzeciego
Typy
Ma on tÄ™ wÅ‚aÅ›ciwość, że f · g = f " g i f " g = f · g Wzór na splot
transformacji
obrazów
dyskretny w 2 wymiarach:
Histogram i
a[m, n] " h[m, n] = h[j, k]a[m - j, n - k]
operacje na
j k
histogramie
Dyskretna
transformacja
Fouriera
Filtry lokalne
Progowanie
Wykrywanie
krawędzi
Analiza ruchu
Filtry liniowe
Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Pietrzak
Filtr Gaussa
Akwizycja
îÅ‚ Å‚Å‚
obrazów i
ïÅ‚1 2 1śł
ïÅ‚
sygnałów 2r 2r
ïÅ‚ śł
(2r)! (2r)! ïÅ‚2 śł
ïÅ‚ śł
ïÅ‚ śł
g(i, j) = f (i + r - k, j + r - l) 4 2śł
Dyskretyzacja i ïÅ‚ śł
(2r-k)!k! (2r-l)!l! ïÅ‚ śł
ðÅ‚ ûÅ‚
kwantyzacja
k=0 l=0
1 2 1
Typy
transformacji
Filtr Laplace a
obrazów
g(i, j) = f (i 1, j) + f (i + 1, j) + f (i, j - 1) + f (i, j + 1) - 4f (i, j)
Histogram i
îÅ‚ Å‚Å‚-
operacje na
ïÅ‚0 1 0śł
histogramie ïÅ‚ śł
ïÅ‚ śł
ïÅ‚1 -4 1śł
ïÅ‚ śł
ïÅ‚ śł
Dyskretna ïÅ‚ śł
ïÅ‚ śł
ðÅ‚ ûÅ‚
transformacja
0 1 0
Fouriera
Filtry lokalne
Progowanie
Wykrywanie
krawędzi
Analiza ruchu
Filtry nieliniowe
Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Pietrzak
Akwizycja
obrazów i
sygnałów
Dyskretyzacja i
Lokalne minimum
kwantyzacja
Typy
Lokalne maksimum
transformacji
obrazów
Filtr medianowy
Histogram i
operacje na
histogramie
Dyskretna
transformacja
Fouriera
Filtry lokalne
Progowanie
Wykrywanie
krawędzi
Analiza ruchu
Rozplot
Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Pietrzak
Akwizycja
obrazów i
sygnałów
Algorytm rozplotu:
Dyskretyzacja i
kwantyzacja
gk+1 = gk + (f - gk " h); g0 = f
Typy
transformacji
obrazów
Rozplot pozwala np na korekcjÄ™ poruszonego obrazu, lub
Histogram i
operacje na
niedokładnego zogniskowania obiektywu
histogramie
Dyskretna
transformacja
Fouriera
Filtry lokalne
Progowanie
Wykrywanie
krawędzi
Analiza ruchu
Progowanie
Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Pietrzak
Akwizycja
obrazów i
sygnałów
Dyskretyzacja i
Progowanie jest globalnÄ… metodÄ… segmentacji
kwantyzacja
Typy
Progowanie podwójne
transformacji
obrazów
Progowanie zmienne (np. dla zacienionego obrazu)
Histogram i
operacje na
histogramie
Dyskretna
transformacja
Fouriera
Filtry lokalne
Progowanie
Wykrywanie
krawędzi
Analiza ruchu
Operator gradientu
Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Pietrzak
Akwizycja
obrazów i
sygnałów
Gradient jest to kierunek zmian funkcji. Pozwala wykryć
Dyskretyzacja i
krawędzie przedmiotów widoczne na obrazie.
kwantyzacja
Operatory Robertsa - filtry lokalne realizujące składowe gradientu
Typy
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
transformacji
ïÅ‚0 0 0 śł ïÅ‚0 0 0śł
ïÅ‚ śł śł
obrazów
ïÅ‚ śł ïÅ‚ śł
ïÅ‚0 1 -1śł ïÅ‚ 1 0śł
ïÅ‚0
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł ïÅ‚ śł
Histogram i ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł ïÅ‚ śł
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
operacje na
0 0 0 0 -1 0
histogramie
Dyskretna
transformacja
Fouriera
Filtry lokalne
Progowanie
Wykrywanie
krawędzi
Analiza ruchu
Laplasjan
Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Pietrzak
Akwizycja
Laplasjan dla obrazu 2D jest wyrażony wzorem:
obrazów i
"2f "2f
sygnałów
"2f = + Przykładowe maski realizujące operator Laplace a:
"x "y
îÅ‚ Å‚Å‚
Dyskretyzacja i
kwantyzacja ïÅ‚ 0 -1 0 śł
ïÅ‚ śł
ïÅ‚ śł
ïÅ‚-1 4 -1śł
ïÅ‚ śł
Typy ïÅ‚ śł
ïÅ‚ śł
ïÅ‚ śł
transformacji
ðÅ‚ ûÅ‚
obrazów
0 -1 0
îÅ‚ Å‚Å‚
Histogram i
ïÅ‚1 4 1śł
operacje na ïÅ‚ śł
ïÅ‚ śł
ïÅ‚4 -20 4śł
histogramie 1
ïÅ‚ śł
ïÅ‚ śł
ïÅ‚ śł
16 ïÅ‚ śł
ðÅ‚ ûÅ‚
Dyskretna
1 4 1
transformacja
Fouriera
Filtry lokalne
Progowanie
Wykrywanie
krawędzi
Analiza ruchu
Inne metody wykrywania krawędzi
Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Pietrzak
Akwizycja
obrazów i
sygnałów
Maski wykrywajÄ…ce konkretne wzorce (linie poziome,
Dyskretyzacja i
kwantyzacja pionowe, ukośne, narożniki)
Typy
Gradienty Sobela, Pewritta
transformacji
obrazów
Rozkład na kształty lokalne
Histogram i
operacje na
Analiza obrazu w bazie F-C
histogramie
Dyskretna
transformacja
Fouriera
Filtry lokalne
Progowanie
Wykrywanie
krawędzi
Analiza ruchu
Detekcja i analiza ruchu
Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Pietrzak
Problem polega na detekcji i analizie ruchu w sekwencji obrazów.
Akwizycja
obrazów i
Największe niedogodności przy jego rozwiązywaniu:
sygnałów
Dyskretyzacja i złożoność obliczeniowa
kwantyzacja
nadmiar informacji
Typy
transformacji
obrazów
problem szczelinowy
Histogram i
zmienne oświetlenie
operacje na
histogramie
zachodzenie obiektów na siebie
Dyskretna
transformacja
Fouriera
mały kontrast między obiektami a tłem
Filtry lokalne
Progowanie
Wykrywanie
krawędzi
Analiza ruchu
Pole ruchu
Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Pietrzak
Akwizycja
Pole ruchu (motion field) - rzut trójwymiarowych wektorów
obrazów i
sygnałów
ruchu na płaszczyznie obrazu; zawiera informacje o składowej
Dyskretyzacja i
wektora ruchu równoległej do płaszczyzny obrazu; brak informacji
kwantyzacja
Typy o składowej prostopadłej do płaszczyzny obrazu.
transformacji
obrazów Przepływ optyczny (optical flow) pole wektorowe zawierające
Histogram i
informacje umożliwiające przekształcenie jednego obrazu w drugi
operacje na
histogramie
przez przesunięcie obszarów z pierwszego obrazu w drugi; nie
Dyskretna
jest jednoznacznie określony.
transformacja
Fouriera
Filtry lokalne
Progowanie
Wykrywanie
krawędzi
Analiza ruchu
Metody detekcji i śledzenia ruchu
Cyfrowe
przetwarzanie
sygnałów i
obrazów
Grzegorz
Pietrzak
Akwizycja
różnicowe umożliwiające detekcję i śledzenie ruchu dzięki
obrazów i
sygnałów
różnicom pomiędzy następującymi klatkami,
Dyskretyzacja i
kwantyzacja korelacyjne przeszukujÄ…ce obraz w poszukiwaniu
Typy
dopasowania regionów,
transformacji
obrazów
gradientowe opierajÄ…ce siÄ™ na wyznaczeniu pochodnych
Histogram i
czasowych i przestrzennych obrazu,
operacje na
histogramie
częstotliwościowe oparte na filtrach operujących w
Dyskretna
transformacja
dziedzinie częstotliwości.
Fouriera
Filtry lokalne
Progowanie
Wykrywanie
krawędzi
Analiza ruchu