Dane (ang. data, od łac. datum = to, co jest dane, l.mn data) - wszystko to co jest lub może być przetwarzane umysłowo lub komputerowo

(maszynowo) Dane przetwarzane przez komputer mają postać symboli - liczb, znaków, obrazów itp. Dane wchodzą w skład informacji (symbolom nadane jest znaczenie, np. wielkość fiz.) które z kolei składają się na wiedzę

Zbiór danych - zbiór pobranych z pewnego środowiska lub procesu Najprostszy przypadek zbioru danych - dysponujemy kolekcją m obiektów, przy czym dla każdego z nich dysponujemy n pomiarami. Reprezentacja - macierz o wymiarach m x n.

Analiza danych Poszukiwanie relacji w zbiorze danych Zbiór danych uzyskany wskutek przeprowadzonego eksperymentu - niewielka

liczba elementów lub prosta struktura zbioru - „klasyczne” metody analizy danych - analiza statystyczna. Zbiór danych uzyskany z przeprowadzonych obserwacji - bardzo duża liczba Zbiór danych uzyskany z przeprowadzonych obserwacji - bardzo duża liczba elementów, skomplikowana struktura zbioru - eksploracja danych (ang. data mining) - metody statystyczne są na ogół niewystarczające

Cele analizy danych:

1. Eksploracyjna analiza danych, wizualizacja danych - brak jakichkolwiek założeń, na temat tego czego szukamy - techniki interaktywne i wizualne (wykresy)Efektywne dla stosunkowo niewielkich, niskowymiarowych (2-4) zbiorów danych - np. techniki rzutowania

2. Modelowanie opisowe - model opisowy służy charakteryzacji wszystkich danych (a przez to procesu) - np. estymacja rozkładu rawdopodobieństwa danych, analiza skupień (dzielenie wielowymiarowej przestrzeni na grupy),

tworzenie modeli opisujących związki między rekordami

Segmentacja - np. stosowana powszechnie w badaniach marketingowych do

dzielenia osób na jednorodne grupy na podstawie rodzaju dokonywanych

zakupów i danych demograficznych,

Grupowanie danych - np. analiza długoterminowych zmian klimatycznych -

3. Modelowanie przewidujące (predykcyjne) - zbudowanie modelu na

podstawie którego można będzie przewidzieć (niekoniecznie w czasie) wartość

jednej zmiennej na podstawie znanych wartości innych zmiennych

4. Odkrywanie wzorców i reguł - zdobywanie wiedzy z danych poprzez poszukiwanie ukrytych wzorców

5. Wyszukiwanie według zawartości - wyszukiwanie na podstawie danego wzorca podobnych podzbiorów zbioru danych (który jest zazwyczaj bardzo duży) - np. wyszukiwanie treści w sieci Internet, wyszukiwanie obrazów podobnych do danego itp.

Wiele technik eksploracji danych (np. analiza skupień) używa miar opartych na

podobieństwie zbiorów danych.

Kryterium oceny podobieństwa - metryka:

Metryka euklidesowa:

Metryka (ogólnie):

Metody wizualne - odkrywanie ukrytych struktur danych przez człowieka, idealne do przeszukiwania danych w celu znalezienia nieoczekiwanych

zależności

Wizualizacja danych

Statystyki opisowe:

Wartość średnia:

Niech x(1) … x(n) stanowią zbiór n wartości danych

Wartość średnia: jest szacowana na podstawie próbki Wartość średnia próbki

ma tę własność, że jest wartością „środkową" - minimalizuje

sumę kwadratów różnic między nią a wartościami danych.

Mediana:

Jest to wartość mającą równą liczbę punktów danych nad i pod sobą. Jeśli n jest liczbą parzystą, mediana jest zwykle definiowana jako wartość leżąca w połowie drogi między dwoma środkowymi wartościami).

Moda:

Najczęściej występująca wartość w danych

Uwaga: Czasem rozkłady mają więcej niż jedną modę (na przykład może być 10 obiektów, które na pewnej zmiennej przyjmują wartość 3 i kolejne 10, które przyjmują wartość 7, wszystkie zaś pozostałe wartości są przyjmowane mniej niż 10 razy) i stąd

są zwane wielomodalnymi. są zwane wielomodalnymi.

Pierwszy kwartyl (lub kwantyl), dolny kwartyl:

Wartość większa niż jedna czwarta punktów danych.

Trzeci kwartyl, górny kwartyl

Wartość większa niż trzy czwarte punktów danych.

Drugi kwartyl -> mediana

W podobny sposób definiowane są decyle i centyle

Wariancja:

Wariancja to średnia kwadratów różnic między wartością średnią a pojedynczymi wartościami danych. Jest to przykład miary rozrzutu lub

zmienności.

Odchylenie standardowe:

Rozstęp międzykwartylowy:

Różnica między trzecim a pierwszym kwartylem

Współczynnik skośności (Skośność):

Miara asymetrii rozkładu.

Przyjmuje wartość 0, jeśli rozkład jest symetryczny,

wartości ujemne, jeśli rozkład jest lewostronny (wydłużone lewe wartości ujemne, jeśli rozkład jest lewostronny (wydłużone lewe

ramię rozkładu); dodatnie jeśli jest prawostronny

Kurtoza:

Miara spłaszczenia rozkładu.

Kurtoza przyjmuje wartość 0, jeśli spłaszczenie rozkładu jest jak dla rozkładu normalnego Kurtoza dodatnia - wartości cechy są bardziej skoncentrowane niż przy rozkładzie norm.

Kurtoza ujemna - wartości cechy są mniej skoncentrowane niż przy rozkładzie norm

Przedstawianie pojedynczych zmiennych

Histogram - pokazuje liczbę wartości danej zmiennej leżących w kolejnych

przedziałach

Przy małych zbiorach danych histogramy mogą być mylące: przypadkowe wahania wartości lub alternatywne wybory końców przedziałów mogą

doprowadzić do powstania bardzo różnych diagramów

Przy dużych zbiorach danych nawet ledwo uchwytne cechy histogramu mogą reprezentować rzeczywiste aspekty rozkładu

Histogram można wygładzić - estymacja jądrowa - wyrównanie histogramu wokół każdego z

punktów, wartość przypisana każdemu z punktów

przy czym K - funkcja jądrowa

h - szerokość f.j.

Zazwyczaj jest to funkcja jednomodalna z

wierzchołkiem w 0

Często jest to funkcja Gaussa

C - stała normująca

Wykres pudełkowy(box plot) - pojedyncza zmienna

Przedstawianie zaleznosci pomiędzy dwoma zmiennymi

Rozrzut(scatterplot) Bardzo duża liczba punktów.

Przesłanianie jednych punktów przez inne

Wykresy warstwicowe(box plot)

Wykres warstwicowy wymaga Wykres warstwicowy wymaga skonstruowania estymacji dwuwymiarowej gęstości -dwuwymiarowa funkcja jądrowa

Przedstawianie zależności więcej niż dwóch zmiennych Macierzowe wykresy rozrzutu

Dane wielowymiarowe są rzutowane na przestrzeń dwuwymiarową - definiowaną przez dwie z tych zmiennych Możliwe jest zatem badanie zależności pomiędzy parami zmiennych

Wykresy obrazkowe Wykresy obrazkowe

Wykresy gwiazdowe -promienie wychodzące w różnych kierunkach odpowiadają różnym

zmiennym - długości tych promieni odpowiadają ważności tych zmiennych

Wykresy kołowe Wykresy profili Twarze Chernoffa

Dane wielowymiarowe rzutowane są na przestrzeń dwuwymiarową

Analiza składowych głównych (Principal Component Analysis - PCA) Bardziej ogólny przypadek - rzutowanie wzdłuż dwóch różnych kierunków będących jakąkolwiek ważoną kombinację liniową zmiennych - np. 2x₁ + 3x₂ + x₃

Można spowodować, przeszukiwanie różnych kierunków projekcji - duży nakład mocy

obliczeniowej. PCA - metoda opracowana w 1933 przez Hotellinga.

Cel - znalezienie takich kombinacji liniowej zmiennych (2 - w przypadku dwuwymiarowym), aby wariancja zrzutowanych danych na taką płaszczyznę była maksymalna - zmniejszenie wymiarowości danych X - macierz danych o wymiarach n x p (wiersze - przypadki; kolumny - zmienne)

Każdy i-ty wiersz macierzy traktowany jest jako transpozycja wektora kolumnowego x^T

a - kolumnowy wektor rzutowania rozmiaru p x 1 (jeszcze nieznany) dający największą wariancję, gdy dane z macierzy X rzutowane są na a. Rzutowanie jakiegokolwiek wektora danych x jest kombinacją liniową

Rzutowanie wszystkich wektorów danych (czyli X) na a można zapisać jako Xa

Skalowanie wielowymiarowe (Multidimensional Scaling - MDS) PCA - rzutowanie wielowymiarowego zbioru danych na przestrzeń (często dwuwymiarową), w której dane mają maksymalny rozrzut. Może istnieć zakrzywanie

tak uzyskanej przestrzeni - wówczas PCA, może być nieefektywna. Inne kryterium niż maksymalizacja wariancji musi zostać wzięta pod uwagę -

odległość (lub niepodobieństwo). Można użyć innej miary odległości niż euklidesowa (nawet nie musi być to metryka). Można użyć innej miary odległości niż euklidesowa (nawet nie musi być to metryka).

Klasyczne skalowanie wielowymiarowe - minimalizacja wyrażenia

Odległość pomiędzy

elementami i oraz j w

przestrzeni p-wymiarowej Odległość pomiędzyelementami i oraz j w

przestrzeni 2-wymiarowej

Skalowaniu w dziedzinie czasu odpowiada odwrotne skalowanie w dziedzinie częstotliwości Jeżeli zmniejszymy skalę czasową („ściśniemy” sygnał) to będzie temu odpowiadać poszerzenie widma tego sygnału

Jeśli fmax jest maksymalną częstotliwością sygnału analogowego x(t), wówczas aby z

sygnału spróbkowanego odtworzyć sygnał oryginalny, częstotliwość próbkowania fp

musi musi być co najmniej dwa razy większa.

Próbkowanie sygnałów pasmowych

rekonstrukcja sygnału pasmowego z częstotliwością próbkowania mniejszą niż ω - inwersja częstotliwości

W praktyce nie jest możliwe zrealizowanie sumowania nieskończonej ilości składników, zatem

transformacie podlega tylko fragment sygnału

Transformowaniu ulega iloczyn sygnału i okna prostokątnego zatem w dziedzinie częstotliwości wyznaczany jest splot widma sygnału i okna prostokątnego

Transformata świergotowa (chirp transform)

Przeznaczona jest do obliczania widma Fouriera analizowanego sygnału w zadanym

zakresie częstotliwości z założoną rozdzielczością.

Transformata Wignera-Ville'a

R Reprezentacja czasowo-częstoliwościowa

R Idealnie odwzorowuje na płaszczyźnie czas-częstotliwość liniową zmianę częstotliwości

Reprezentacja VW posiada najlepszą koncentrację energii w przestrzeni czas- częstotliwość, ale występują pasożytnicze interferencje wzajemne o charakterze oscylacyjnym Konieczne jest redukcja interferencji - lokalne wygładzanie widma

• Rozdzielczość w dziedzinie czasu i częstotliwości jest ograniczona

• Im większa rozdzielczość w dziedzinie czasu (mniejsza szerokość okna w dziedzinie

czasu), tym mniejsza w dziedzinie częstotliwości (szersze okno w dziedzinie częstotliwości)

i na odwrót.

• Największa rozdzielczość w dziedzinie czasu i częstotliwości - najmniejsze pole kostki

Heisenberga- uzyskuje się dla okna Gaussa - transformata Gabora.

Transformata falkowa (wavelet transform)

Ciągła transformata falkowaAnalizowana funkcja powinna być całkowalna z kwadratem tzn:

Sygnał powinien charakteryzować się skończoną energią. Warunku tego nie spełnia np. zarówno sygnał stały, jaki i sinusoida zarówno sygnał stały, jaki i sinusoida

• Dla małych wartości skali s szerokość kostki Heisenbrga w dziedzinie czasu jest mała a

duża w dziedzinie częstotliwości

• Dla dużych wartości skali s szerokość kostki Heisenbrga w dziedzinie czasu jest duża a

mała w dziedzinie częstotliwości

• Jeżeli sygnał f(t) zostanie poddany przekształceniu falkowemu, to na płaszczyźnie

czasowo-częstotliwościowej zawarta jest informacja o zawartości wolno- i szybkozmiennych

składowych oraz ich lokalizacji w czasie z rozdzielczością zdeterminowaną przez kostkę

Heisenberga

Ortogonalność bazy falkowej zapewnia uniknięcie nadmiaru informacji o sygnale w jego

rozwinięciu falkowym - nie jest to bezwględnie wymagane wada rozwinięcia w szereg falkowy: brak tzw. niezmienności przesunięcia (shift invariance)

Dyskretna transformata falkowa

Ciągłe p.f. - ciągły sygnał, nieskończenie wiele falek

Rozwinięcie w szereg falkowy - sygnał dyskretny, nieskończenie wiele falek Realizacja praktyczna jest niemożliwa do osiągnięcia (w sensie przedstawionych zależności) Widmo falki - filtr pasmowoprzepustowy o szerokości zmieniającej się wraz ze zmianą skali Zwiększenie skali 2-krotne - 2 krotne zmniejszenie pasma falki i przesunięcie w stronę składowej stałej Wprowadzenie tzw. funkcji skalującej - filtr dolnoprzepustowy

Transformata Z jest przypadkiem ogólnym transformaty Fouriera ciągu x[n]

Obliczenie transformaty Z na okręgu jednostkowym →

transformata Fouriera

z=1 → ω=z

z=j → ω = π/2

z=-1 → ω =π

Zbiór takich z, że dla danego ciągu x[n] transformata Z jest zbieżna → obszar zbieżności Zbiór takich z, że dla danego ciągu x[n] transformata Z jest zbieżna → obszar zbieżności

warunek zbieżności transformaty Z

Transformata Z może być zbieżna dla ciągów, których transformata Fouriera nie jest zbieżna

np. skok jednostkowy x[n ]= u[n ] w ogólnym przypadku nie jest absolutnie sumowalny

ale gdy |r|>1 wówczas jest abs. Sumowalny

jest zbieżny dla |r|>1

Obszar zbieżności zależy tylko od z i zawiera wszystkie z dla których transformata Z istnieje

Obszarem zbieżności (OZ) jest pierścień

na płaszczyźnie zespolonej, którego

zewnętrzny promień może → ∞

Jeśli OZ zawiera okrąg jednostkowy,

wówczas istnieje transformata (dyskretna) Fouriera wielomian, miejsce zerowe - zera transformaty

Transformata Z zazwyczaj daje się wyrazić w postaci funkcji wymiernej:

Wielomiany w liczniku i mianowniku dają się rozłożyć na czynniki: W wielomianach występuje z-1

- kwestia przyjętej konwencji - zgodność z definicją

transformaty Z

γ_l l= 1...M pierwiastki licznika transformaty → zera transformaty

λ_l l= 1..N pierwiastki mianownika transformaty → bieguny transformaty

Właściwości obszaru zbieżności transformaty Z

1. OZ ma kształt dysku lub pierścienia ze środkiem w środku układu współrzędnych na płaszczyźnie zespolonej z

2. Transformata Fouriera ciągu x[n] jest bezwzględnie zbieżna wtedy i tylko wtedy,

jeśli OZ transformaty sygnału x[n] zawiera okrąg jednostkowy

3. OZ nie zawiera żadnych biegunów

4. Jeśli x[n] jest ciągiem skończonym wówczas OZ jest cała płaszczyzna zespolona oprócz punktu z=0 lub z=∞

5. Jeśli x[n] jest nieskończonym ciągiem prawostronnym, OZ jest obszar położony

na zewnątrz okręgu o promieniu równym modułowi największego bieguna Z{x[t]}

6. Jeśli x[n] jest nieskończonym ciągiem lewostronnym, OZ jest obszar położony

wewnątrz okręgu o promieniu równym modułowi najmniejszego bieguna Z{x[t]}

7. Jeśli x[n] jest nieskończonym ciągiem dwustronnym, OZ będzie pierścieniem ograniczony biegunami (nie zawiera oczywiście wewnątrz żadnych biegunów)

8. OZ jest obszarem spójnym

Odwrotne przekształcenie Z

Wyznaczenie ciągu x[n] na podstawie jego transformaty i informacji o obszarze zbieżności

Sposoby obliczania odwrotnej transformaty

• bezpośrednio ze wzoru

• metoda „długiego” dzielenia wielomianów

• metoda rozkładu na ułamki proste

• metoda residuów

Zysk obliczeniowy algorytmu radix-2

W każdym kroku algorytmu FFT wymagane jest przeprowadzenie N/2 mnożeń zespolonych

oraz N sumowań zespolonych Każdy dodatkowy współczynnik w potędze liczby 2 przy ilości N próbek wymaga przeprowadzenia osobnego kroku algorytmu FFT. Zatem zawsze mamy B =log₂N kroków w algorytmie FFT. W całym algorytmie przeprowadzanych jest N/2*log₂N mnożeń zespolonych oraz N*log₂N sumowań zespolonych.

OBRAZ - Pojęcia podstawowe

Obraz - rozkład irradiancji (strumień promieniowania padający na jednostkę powierzchni [W/m2] na płaszczyźnie funkcja dwuwymiarowa:f(x,y) , przy czym:x, y - współrzędne przestrzenne (na płaszczyźnie) 0<f(x,y)<∞

Cyfrowe przetwarzanie obrazu - (digital image processing) przetwarzanie obrazu

cyfrowego za pomocą maszyny cyfrowej (komputera)

Wartości w wyniku kwantyzacji przybierają wartości całkowite L,zazwyczaj takie, że: L = 2^k

[ 0,L-1] ---Zakres dynamiki obrazu

M*N*k Ilość bitów potrzebna do przechowania obrazu cyfrowego o

rozmiarach M x N

Kompresja pojęcia podstawowe

Kompresja danych - proces przekształcania pierwotnej reprezentacji (źródłowej) sekwencji danych w reprezentację o mniejszej liczbie bitów. Odwrotny proces rekonstrukcji oryginalnej reprezentacji danych na podstawie reprezentacji

skompresowanej nazywane jest dekompresją

Kompresja - pojęcia podstawowe skompresowanej nazywane jest dekompresją Kompresja - Wyznaczanie możliwie użytecznej w danym zastosowaniu reprezentacji przesyłanej lub gromadzonej informacji Kompresja bezstratna (odwracalna) - kodowanie - zrekonstruowany po

kompresji ciąg danych jest numerycznie identyczny z sekwencją źródłową z dokładnością do pojedynczego bitu Przykłady zastosowań: archiwizacja dokumentów tekstowych, historia

operacji finansowych na kontach bankowych, przechowywanie (niektórych) obrazów medycznych

Kompresja Kompresja -- pojęcia podstawowe pojęcia podstawowe Kompresja stratna (odwracalna) - nie jest możliwe odtworzenie danych źródłowych z dokładnością do pojedynczego bitu. Używane jest pojęcie tzw. wizualnej bezstratności. Eliminacji części informacji z obrazu może być niezauważalna, lub dopuszczalna dla obserwatora

Analiza obrazu pojęcia podstawowe

Analiza obrazu jest ściśle związana z konkretnym celem, który chcemy poprzez tą analizę osiągnąć.

Metod analizy jest stosunkowo Metod analizy jest stosunkowo mało, natomiast istnieje olbrzymia

ilość metod przetwarzania obrazów

Przetwarzanie obrazu - klasyfikacja metod

geometryczne(obrót,przesunięcie,odbicie,skalowanie

bezkontekstowe(punktowe)

kontekstowe(filtry medianowe,operacje splotu)

widmowe(z wykorzystaniem DFT,DWT,DCT,itp)

morfologiczne(dyletacje,erozje)

Operacje geometryczne:położenie piksela zmieniane jest zgodnie z zadaną relacją matematyczną.

Operacje arytmetyczne: nowa wartość intensywności piksela obliczana jest na podstawie jego poprzedniej wartości zgodnie z przyjętą relacją arytmetyczną

Segmentacja

Proces segmentacji obrazu jest czynnością spinającą poziom

wstępnego przetwarzania obrazu z programami analizy

poszczególnych obiektów.

Segmentacja jest techniką przetwarzania obrazu, umożliwiającą

wydzielenie obszarów obrazu spełniających pewne kryteria

jednorodności (kolor obszaru, poziom jasności, faktura, itp.) jednorodności (kolor obszaru, poziom jasności, faktura, itp.)

• segmentacja przez podział obszaru

• segmentacja przez rozrost obszaru

• segmentacja metodą wykrywania krawędzi

• segmentacja oparta na statystyce opisującej wnętrze regionów

Analiza obrazu, rozpoznawanie obrazu

Analiza obrazu, która może być przeprowadzona po segmentacji,przewiduje w pierwszej kolejności różne pomiary wykonywane na obiektach wydzielonych podczas procesu segmentacji.

Wynikiem analizy obrazu mogą być dane jakościwe I ilościowe, opisujące określone cechy obrazu

Przykład rozpoznawanie osób na podstawie twarzy

Algorytmy kompresji

Statyczne-jednakowe dla całej sekwencji danych o zbliżonym charakterze. Nie istnije koniecznośc dopisywania parametrów algorytmu w sekwencji wyjściowej

Póładaptacyjne- jednakowe dla całej sekwencji danych parametry alg kompresji wyznaczone na podstawie wstepnej analizy danych.Istnieje konieczność dopisywania parametrów algorytmu w nagłówku sekwencji wyjściowej

Adaptacyjne- zmienne,dostosowane dynamicznie do lokalnej statystyki danych źródłowych na podstawie analizy wejściwej sekwencji danych.Istnieje. Nie istnieje konieczność dopisywania parametrów algorytmu w sekwencji wyjściwej dla przyczynowej adaptacji wstecz. Konieczność dopisywania rzadziej zmienianych parametrów(adaptacja w przód)

KOMPRESJA BEZSTRATNA

Uzycie odpowiedni Przypisywanie ciągu skutecznych i predykcyjnych bitów(słów kodowych)

modeli statystycznych i poszczególnym danym

predykcyjnych, osczednego (poszczególnym

opisu lokalnych zaleznosci symbolom alfabetu

danych źródła informacji),calej

sekwencji danych wejściowych lub jej poszczególnym częścom

Faza modelowania: tworzona jest pośrednia reprezentacja cech, do

której dopasowuje się metodę binarnego kodowania sekwencji źródłowej. Możliwe jest to poprzez:

• przekształcenie danych z przestrzeni oryginalnej w inną z wykorzystaniem metrycznych zależności danych, określonego sposobu porządkowania danych lub zmiany wymiarowości oryginalnej dziedziny danych. oryginalnej dziedziny danych.

• utworzenie modelu deterministycznego, opisującego bezpośrednie (chwilowe, lokalne lub globalne) właściwości danych, np. ciagi jednakowych danych.

• utworzenie modelu probabilistycznego źródła informacji (przy założeniu stacjonarności i ergodyczności źródła) na podstawie określonego kontekstu wystąpienia danych.

Faza kodowania binarnego: polega na tworzeniu w sposób możliwie oszczędny wyjściowej sekwencji bitowej jednoznacznie reprezentującej lokalne dane

Możliwe rozwiązania stosowane w fazie modelowania:

1. Z uproszczonym modelem statystycznym w metodach:

# RLE (Run-Length Encoding - kodowanie długości serii) dla serii bitów (koder Z), bajtów (format PCX), bajtów (format PCX),

# Golomba (JPEG-LS),

# Huffmana (JPEG),

# kodowanie arytmetyczne w przypadku kodowania reszt predykcyjnych.

2. Z rozbudowanym dynamicznym modelem kontekstowym wyższych rzędów

3. Ze słownikiem (metody słownikowe) np. format GIF, PNG

4. Ze wstępną dekompozycją danych gdy tworzona jest reprezentacja pośrednia:

# metody predykcyjne i interpolacyjne,

# kodowanie map bitowych,

# skanowanie danych wg określonego porządku,

# całkowitoliczbowe kodowanie transformacyjne, (np. AVC)

# całkowitoliczbowe dekompozycje pasmowe i falkowe (np. JPEG2000)

Możliwe rozwiązania stosowane w fazie kodowania binarnego:

1. Przypisywanie słów kodowych pojedynczym symbolom alfabetu źródła - Metody

Huffmana, Shannona-Fano, Rice'a - kody o zmiennej długości słów

2. Przypisywanie słów kodowych (zazwyczaj o stałej długości) ciągom symboli wejściowych o zmiennej długości (RLE, kodowanie słownikowe). Modyfikacja tych metodo polega na użyciu adaptacyjnych koderów słownikowych o zmiennym rozmiarz

słownika (a więc i indeksów)

3. Utworzenie sekwencji kodowej w postaci jednego binarnego słowa kodowego wyznaczanegosukcesywnie dla całego ciągu wejściowego

Przegląd wybranych metod kodowania

Kod dwójkowy o stałej długości Poszczególne słowa kodu są dwójkową reprezentacją kolejnych liczb naturalnych

Zalety

- prosta budowa

-znany z góry współczynnik kompresji

Wady

- kompresja możliwa tylko wówczas gdy liczba kodowanych symboli jest mniejsz niż rozmiar alfabetu

Zastosowania

-niewielka liczba występujących symboli

-stosowany jako część składowa innych kodów

Kodowanie długości sekwencji (RLE - run length encoding) RLE-1, RLE-2

Kod strumieniowy, seria powtarzających się jednakowym symboli wejściowych

opisywana jest słowem kodowym określonej długości składającym się z reprezentacji

długości serii i symbolu

Przykład:

Niech będzie dany ciąg wejściowy:

25 znaków

W rozpatrywanym ciągu znak „a” powtarza się 3 razy, „b” powtarza się 7 razy, „c” - 4 razy, itd.

Informację o zapisie 3 znaków „a” można zapisać jako 3a, zapis 7 znaków „b” można zapisać jako 7b itd. Zatem ciąg wyjściowy będzie miał postać:

12 znakow

Może się zdarzyć, że w najgorszym przypadku (dane losowe) rozmiar sekwencji wyjściowej zwiększy się dwukrotnie RLE-2 pozwala nie zwiększać rozmiaru danych, w przypadku gdy w sekwencji wejściowej nie występuje ciąg jednakowych symboli

Wykorzystywany jest w tym celu specjalny symbol, który sygnalizuje pojawienie się pary (długość ciągu, symbol).Tylko ciągi o długości większej niż wartość progowa (zazwyczaj 2) zamieniane są na pary (długość ciągu, symbol). na pary (długość ciągu, symbol).

Przykład:

Niech będzie dany ciąg wejściowy:

Ciąg wyjściowy będzie miał postać:

Zastosowanie RLE:

Dokumenty, w których dominuje białe tło, np. fax

Formaty zapisu obrazu PCX, BMP, TGA

Jako filtr w dokumentach formatu PostScript i PDF

2D RLE - dwuwymiarowa wersja RLE

# Wersja dwuwymiarowa algorytmu uwzględnia wzajemne relacje # Wersja dwuwymiarowa algorytmu uwzględnia wzajemne relacje

między pikselami w płaszczyźnie obrazu.

# Inaczej zdefiniowane jest sąsiedztwo wystąpienia jednakowych symboli

# Obok bezpośredniego sąsiedztwa kolejno kodowanych pikseli (oprócz pierwszego piksela w serii jest to sąsiedztwo z lewej strony) uwzględnia się sąsiedztwo z góry i góra-skos

Przykład:

Niech będzie dany fragment obrazu z wyszczególnionymi wartościami pikseli: 2D RLE

Wynik modelowania:

Wynik kodowania binarnego - PCX - w kodzie liczby powtórzeń dwa najstarsze bity

wskazują na rodzaj sąsiedztwa, pozostałe sześć oznaczają liczbę powtórzeń wartości

pikseli w danym sąsiedztwie

Kod Shannona-Fano

Jest to historycznie najstarsza metoda kodowania oparta na prawdopodobieństwie kumulatywnym.

1. Słowa kodowe przyporządkowywane są pojedynczym symbolom i mają różną liczbę bitów

2. Słowa symboli o większym prawdopodobieństwie wystąpienia na wejściu są krótsze - długość słów jest proporcjonalna do ilości Do konstrukcji kodu stosowana jest struktura drzewa binarnego

wejściu są krótsze - długość słów jest proporcjonalna do ilości informacji związanej z danym wydarzeniem

3. Kod jest przedrostkowy, czyli jednoznacznie dekodowalny

Do konstrukcji kodu stosowana jest struktura drzewa binarnego

Schemat budowy drzewa binarnego w kodzie Shannona-Fano:

1. Określane jest prawdopodobieństwo wystąpienia wszystkich symboli

alfabetu na podstawie częstości wystąpień w kodowanym ciągu danych

2. Symbole alfabetu są szeregowane w nierosnącym porządku wag.

Posortowany zbiór symboli traktowany jest jako grupa początkowa.

3. Otrzymana grupa dzielona jest na dwie części o możliwie równej sumie wag symboli z zachowaniem porządku listy (o częściej i występujących symbolach i o rzadziej występujących).

4. Symbolom z jednej podgrupy przyporządkowywane jest logiczne 0 (np. symbolom o większej wadze), a drugiej - logiczna 1.

5. Kroki 3 i 4 są powtarzane rekursywnie dla utworzonych podgrup o przynajmniej dwóch symbolach, czyli aż grupy będą jednoelementowe

6. Kolejnym symbolom z listy przypisywane są słowa kodowe, składające się z bitów kolejno przyporządkowanych grupom.

Przykład2

Kod Huffmana

Przedstawiona wersja kodu Huffmana jest statyczna -prawdopodobieństwa wystąpienia poszczególnych symboli w sekwencji wejściowej są stałe.

Póładaptacyjny (semiadaptacyjny) kod Huffmana

Statyczny kod Huffmana zakłada stacjonarność kodowanego źródła - w praktyce ten warunek nigdy nie jest spełniony Kodowanie Huffmana wymaga znajomości częstości występowania każdego symbolu nad alfabetem Drzewo Huffmana lub częstości występowania symboli musi być

dodane do danych wyjściowych (zazwyczaj w nagłówku

Adaptacyjny kod Huffmana

Stosowany, gdy charakterystyka danych jest zmienna Drzewo Huffmana jest modyfikowane po zakodowaniu każdego nowego znaku. Rozpoczęcie z drzewem pustym lub rozkładem

jednolitym Lepsza efektywność, ale wolniejsze działanie Zastosowanie kodowania Huffmana:

Kompresja JPEG - kodowanie skwantowanych współczynników DCT ; Wykorzystywane w algorytmie LZ77/LZSS (gzip, PKZip, ARJ, LHArc), MPEG.

Zalety

-prostota

-brak ograniczeń patentowych

-brak konieczności przesylania do dekodera informacji o modelu

-dobry współczynnik kompresji

Wady:

- powolne uaktualnianie drzewa Huffmana po zakodowaniu każdego symbolu (kodowanie danych o nieznanej statystyce),

-problemy implementacyjne - możliwe przepełnienie drzewa.

Przykład3

Przykład: jeśli dany jest alfabet o długości n = 6, wówczas:

Dwa pierwsze symbole alfabetu otrzymują dwubitowe słowa kodowe,

pozostałe zaś - trzybitowe

Można udowodnić, że jeśli rozkład prawdopodobieństwa symboli Można udowodnić, że jeśli rozkład prawdopodobieństwa symboli

danego źródła jest zrównoważony

(suma dwóch najmniejszych prawdopodobieństw jest większa od prawdopodobieństwa największego),

oraz uporządkowany zgodnie z nierosnącym prawdopodobieństwem kolejnych symboli alfabetu, wówczas kod dwójkowy prawie stałej długości jest optymalnym kodem symboli.

Kod Golomba

Stosowany w przypadkach, gdy nieznana jest statystyka źródła albo w przypadkach, kiedy jest ona na tyle znana, że proces kodowania

może zostać uproszczony Jest to kod symboli, szczególny przypadek kodów przedziałowych

(alfabet jest dzielony na przedziały). Wykorzystywany jest kod dwójkowy prawie stałej długości i kod

unarny Dla kodu o n-elementowym alfabecie pierwszym r symbolom przypisywane są słowa bitowe, bitowe. a pozostałym k+1

Można udowodnić, że jeśli rozkład prawdopodobieństwa symboli Można udowodnić, że jeśli rozkład prawdopodobieństwa symboli

danego źródła jest zrównoważony

(suma dwóch najmniejszych prawdopodobieństw jest większa od

prawdopodobieństwa największego),

oraz uporządkowany zgodnie z nierosnącym prawdopodobieństwem

kolejnych symboli alfabetu, wówczas kod dwójkowy prawie stałej długości jest optymalnym kodem symboli.Kod Golomba jest kodem sparametryzowanym, przy czym parametr m > 0 W kodzie Golomba z parametrem m, liczba całkowita n jest eprezentowana za pomocą dwóch liczb q i r, takich, że:

Czyli ilorazu i reszty z dzielenia n przez m

q może przyjmować wartości 0, 1, 2, … i jest reprezentowany za

pomocą kodu unarnego

r może przyjmować wartości 0, 1, 2, … m - 1.

Kodowania słownikowe

Metody słownikowe - polegają na utworzeniu listy najczęściej występujących wzorców i zakodowaniu ich wystąpienia w sekwencji wejściowej za pomocą indeksów na liście

Słownik - lista często występujących wzorców w sekwencji wejściowej, tworzona statycznie lub dynamicznie. Metody słownikowe - polegają na utworzeniu listy najczęściej występujących wzorców i zakodowaniu ich wystąpienia w sekwencji wejściowej za pomocą indeksów na liście Słownik statyczny - słownik jest zawsze taki sam - rozwiązanie Słownik statyczny - słownik jest zawsze taki sam - rozwiązanie optymalne jeżeli kodowana sekwencja wejściowa jest znana (albo gdy kolejne wyrazy w sekwencji wejściowej zależą od poprzednich).

Przykłady zastosowań

- lista osób - niektóre imiona (i nazwiska) powtarzają się.

- program w postaci kodu źródłowego - słowa kluczowe tworzą znany i stały zestaw.

Słownik dynamiczny - tworzony jest na bieżąco podczas kodowania

- dostosowuje się do charakteru danych

algorytmy kodowania wykorzystujące słownik dynamiczny

wykorzystują metody opracowane przez Jacoba Ziva i Abraham Lempela w:

R 1977 roku (LZ77)

R 1978 roku (LZ78)

Dekoder pozwala na odtworzenie sekwencji wejściowej na podstawie odkodowanej części danych (słownik nie musi być dołączany do sekwencji kodowej)

LZ77 - kodowanie:

1. Ustawienie struktury okna na początku czytanego strumienia danych wejściowych

2. Poszukiwanie najdłuższego łańcucha danych w buforze kodowania (zaczynającego się od danej znajdującej się na pierwszej pozycji w

buforze), który ma swój dokładny odpowiednik w słowniku

3. Tworzenie sekwencji kodowej tego łańcucha składającej się ze wskaźnika jego położenia w słowniku, długości oraz pierwszego symbolu w buforze występującego bezpośrednio po kodowanej

frazie

4. Przesunięcie okna wzdłuż sekwencji wejściowej o długość zakodowanej frazy

5. Powtarzanie pkt. 2, 3, 4 aż do zakodowania ostatniego symbolu ze zbioru danych wejściowych

LZ77 - przykład kodowania

Długość okna - 13 Rozmiar bufora kodowania - 6

Jeden znak został zakodowany - okno przesuwane jest o 1 pozycję. W buforze kodowania szukany jest, poczynając od końca symbol d. Ponieważ nie istnieje żadne dopasowanie, zwracana jest trójka liczb: (0,0,kod(d))

Założenia:

Długość okna - 13 Rozmiar bufora kodowania - 6 Założenia:

Przesuwając się od końca przez bufor słownikowy, trafiamy na dopasowanie dla a,

z przesunięciem 4,

z przesunięciem 7,

z przesunięciem 2 o długości 1, ale także

Długość dopasowania wynosi w tym przypadku 4

Ciąg abra kodowany jest za pomocą trójki liczb: (7,4,kod(r))

Długość okna - 13 Rozmiar bufora kodowania - 6 Założenia:

Zatem okno przesuwane jest o 5 pozycji

Przesuwając się od końca przez bufor słownikowy, trafiamy na dopasowanie z przesunięciem 3 o długości 3, Długość dopasowania może być jednak rozszerzona do 5, Dlatego wygenerowany ciąg ma postać: (3,5,kod(d))

LZ77 - odkodowanie

Warunki początkowe: odkodowany ciąg ma postać

Odebrane trójki: (0,0,kod(d)), (7,4,kod(r)), (3,5,kod(d))

1 trójka (0,0,kod(d)) wskazuje na brak dopasowania

2 trójka (7,4,kod(r)) wskazuje na przesunięcie wskaźnika kopiowania i ilość skopiowanych znaków

3 trójka (3,5,kod(d)) wskazuje na przesunięcie wskaźnika kopiowania i ilość skopiowanych znaków

Na końcu dopisany jest odkodowany znak r - kod(r)

Na końcu dopisany jest odkodowany znak d - kod(d)

LZ77 - możliwe usprawnienia, zastosowania

Zamiast 3 liczb można wysyłać tylko 2 - kopiowany ciąg (bez kodu ostatniej litery) lub 0 i kod nowej litery - (LZSS)Wykorzystanie adaptacyjnej wersji algorytmu Huffmana na sekwencji

kodowej LZ&&Zastosowanie: zip, gzip, png, ARJ, rar, PKZip, LHarc

LZ77 - wady

Jeśli kodowany ciąg jest periodyczny, ale długość okresu jest większa niż bufor słownikowy - długość sekwencji kodowej jest dłuższa niż sekwencji wejściowej

LZ78 - właściwości

Zamiast okna przesuwanego wzdłuż strumienia danych wejściowych, stosowany jest słownik budowany jako zupełnie osobna, nieprzesuwna struktura Słownik modyfikowany jest na bieżąco; kolejno odnajdywane w trakcie kodowania frazy ze słownika, odpowiadające sekwencjom

wejściowym, wchodzą w skład nowych fraz uzupełnione o symbol wchodzący w skład kodu łańcucha.Nowe frazy są umieszczane na kolejnych pozycjach w słowniku, który jest w ten sposób dynamicznie rozbudowywany. Rozmiar słownika może rosnąć w sposób nieograniczony !.

LZ78 - kodowanie

Przykład: zakodować następującą sekwencję wejściową za pomocą LZ78

Inicjalizacja: na pierwszej pozycji słownika wpisywana jest fraza NULL, oznaczająca nieobecność w słowniku szukanej frazy albo

pustą zawartość słownika pustą zawartość słownika

Słownik jest przeszukiwany w celu znalezienia najdłuższej frazy z kolejno czytanych symboli wejściowych Zapisywany jest indeks najdłuższej frazy oraz występującego bezpośrednio po niej symbolu, jako sekwencji kodowej

LZ78 - możliwe usprawnienia

Rezygnacja z drugiego elementu pary - koder wysyła tylko indeks kodowanego elementu słownika (Welch)Aby było to możliwe, potrzebny słownik początkowy, zawierający wszystkie używane litery

Konstrukcja słownika jak w klasycznym LZ78 Konstrukcja słownika jak w klasycznym LZ78

LZW - Lampel Ziv Welch

LZW - kodowanie

Przykład: zakodować następującą sekwencję wejściową za pomocą LZ78

Dana jest początkowa wartość słownika

KOMPRESJA STRATNA

Źródło danych użytkownika

(zmienna losowa) praeksztalcenie operacja

zmiana danych danych skompreso odwrotna do

wejsciowych w -wanych np. wykorz kodowania

wersje -ystanie niedoskona

skompresowana -losci zmyslu sluchu,

wzroku

KOMPRESJA STRATNA -- KRYTERIA OCENY

Różnica pomiędzy danymi oryginalnymi - {x} a danymi uzyskanymi w wyniku

rekonstrukcji - {y}, (x-y)² |x-y|

Błąd średniokwadratowy (średnia arytmetyczna z kwadratów błędów poszczególnych elementów ciągu) ang. mean squared error - σ_d² σ²

Stosunek sygnału do szumu, ang. Signal to Noise Ratio, błąd średniokwadratowy odniesiony do poziomu amplitudy danych oryginalnych - SNR

KOMPRESJA STRATNA - KRYTERIA OCENY c.d.

Szczytowy stosunek sygnału do szumu, ang. Peak Signal to Noise Ratio, błąd średniokwadratowy odniesiony do maksymalnej amplitudy danych oryginalnych -PSNR

Średnia wartość błędu bezwzględnego

Maksymalna wartość błędu bezwzględnego

JPEG

Standard Digital Compression and Coding Continuous-Tone Still Images znany jako JPEG

(Joint Photographic Experts Group) od nazwy organizacji, która go opracowała(późne lata '80)

Dobrz spełnia swe zadania w przypadku obrazów fotograficznych o płynnych przejściach między barwami.Osiąga natomiast gorsze wyniki w przypadku kodowania prostych rysunków o ostrych konturach, takich jak na przykład kadry pochodzące z filmów rysunkowych.

Standard opisuje metody :

-stratna, której podstawą jest dyskretna tranformata kosinusowa(DTC)

-bezstratna (obecnie mało popularna ze względu na niską wydajnośc)

JPEG - charakterystyka formatu

1. Obsługa obrazów w odcieniach szarości (8 bitów na piksel) i RGB (24 bity na piksel).

2. Wykorzystanie dwóch niedoskonałości ludzkiego wzroku: R mniejszą rozdzielczość widzenia kolorów niż jasności,R małą wrażliwość na amplitudę szybkich zmian jasności.

3. Rozbudowane środki informowania o absolutnej przestrzeni barw obrazu (możliwość umieszczenia profilu koloru w pliku).

4. Obsługa wyświetlania progresywnego (zwiększanie rozdzielczości obrazka w miarę napływania nowych danych).

5. JPEG jest przystosowany do transmisji w sieci - może być dekodowany przy sekwencyjnym dostępie do danych.

JPEG - schemat kompresji

Transformacja koloru RGB do YCbCr i obniżenie rozdzielczości

Y (Luminancja) = 0,299SR + 0,587SG + 0,114SB

Cr (Składowa antyczerwona)

Cb (Składowa antyniebieska) = 128 + 0,5SR - 0,418688SG - 0,081312SB

= 128 - 0,168736SR - 0,331264SG + 0,5SB

Składowe chrominancyjne mogą zostać poddane próbkowaniu ze zmniejszoną

rozdzielczością.

W zależności od wymaganej jakości, składowe chrominancyjne mogą zostać:

1.Pozostawione bez zmian, tzw. format 4:4:4.

2.Rozdzielczość pozioma jest zmniejszana o połowę (format 4:2:2).

3.Rozdzielczość pozioma i pionowa jest zmniejszana o połowę (format 4:2:0).

Podzia obrazu na bloki

Każda ze składowych jest oddzielnie dzielona na bloki o rozmiarach 8 x 8 pikseli.Jeżeli składowe Cr i Cb były przeskalowane, bloki tych składowych obejmują obszar 16 x 8 lub 16 x 16 oryginalnego obrazka.Problem powstaje, jeżeli rozmiary obrazu nie są wielokrotnością 8.Najgorszym rozwiązaniem jest uzupełnienie zerami, Najgorszym rozwiązaniem jest uzupełnienie zerami, lepszym - kolorem ostatniego piksela.Najlepsze jest dodanie takich pikseli, aby odwrotna transformata cosinusowa

odtworzyła piksele należące do obrazka jak najbardziej zbliżone wartościami do oryginalnych.

W praktyce wykonuje się to najczęściej dla trzech pierwszych współczynników transformaty.

DCT - właściwości

Określona na zbiorze liczb rzeczywistych - założona jest parzystość transformowanego sygnału

Po lewej stronie badanego przedziału nie ma nieciągłości, więc amplitudy cosinusów o wyższych częstotliwościach są małe.

Transformata cosinusowa ma w sumie 8 wariantów wynikających znastępujących możliwości:

- po prawej może nastąpić odbicie tylko po osi Y, albo po obu osiach.

- symetria po lewej może być ustawiona na pierwszej próbce sygnału, albo w połowie między pierwszą próbką a jej lustrzanym odbiciem.

- symetria po prawej też może być ustawiona na próbce lub między próbkami.

JPEG : odbicie po prawej tylko w osi Y, symetria po obu stronach między próbkami.Podobnie jak algorytm FFT dla obliczania DFT istnieje wersja szybka dla DCT

Kwantyzacja współczynników DCT, zbieranie danych zygzakiem

Dwuwymiarowa DCT na kwadracie 8-bitowych pikseli o rozmiarach 8 x 8,Wynik: macierz 16-bitowych współczynników, o rozmiarach 8 x 8 Kwantyzacja liniowa: podzielenie przez pewną liczbę i odrzuceniu części ułamkowej.Współczynniki DCT zbierane są w

kolejności zygzakowatej.Największe współczynniki znajdują się na początku, na końcu z reguły występuje dużo zer - zastępowane są odpowiednim

znakiem („zera do końca”)Otrzymany strumień kompresowany jest z użyciem kodowania Huffmana -słownik dynamiczny lub predefiniowany

Geneza standardu - niedoskonałości JPEG

-Zniekształcenia obrazów z kompresją JPEG są nie do zaakceptowania przy niskich przepływnościach,

- Potrzeba standardu, który zapewniałby stratną i bezstratną kompresję w jednym strumieniu bitowym,

-JPEG nie obsługuje obrazów wielkoformatowych (powyżej 64x64K) - np. zdjęcia lotnicze, satelitarne

- JPEG posiada wiele sposobów implementacji (44), wiele z nich są specyficzne i zależą od sposobu zaimplementowania - problem z kompatybilnością dekoderów

- JPEG jest wrażliwy na błędy bitowe (np. powstałe przy transmisji)

-JPEG jest optymalizowany dla obrazów naturalnych - obrazy wygenerowane sztucznie (np.komputerowo) po skompresowane JPEG-em wyglądają nieszczególnie,

Geneza standardu - niedoskonałości JPEG

- JPEG jest wysoce nieefektywny przy kompresji obrazów binarnych (np. tekstu)

Powyższe przesłanki skłoniło grupę roboczą, która zajmowała się standardem

JPEG do opracowania nowego standardu kompresji obrazów

Co zatem powinien nowy standard zapewniać?

Efektywną kompresję obrazów nieruchomych z użyciem jednego zestawu

lgorytmów (enkoder-dekoder),

w odcieniach szarości, kolorowych…

o różnej zawartość(obrazy naturalne, naukowe, medyczne, itp.)

w różnych trybach pracy (klient-serwer, czasu rzeczywistego)

JPEG 2000

Ogólne właściwości:

- Jeden enkoder - wiele sposobów (możliwości) odkodowania

-Bardzo dobra jakość skompresowanych obrazów (nawet przy cr ok. 1:80)

-Wykorzystanie dwuwymiarowej dyskretnej transformaty falkowej (DWT) zamiast DCT

1996 - RICOH - zainicjowanie prac

Listopad 1997: 24 propozycji nowego standardu kompresji obrazów

Styczeń 2001 - IS 15444-1

JPEG 2000 - schemat kompresji - dekompresji

Preztwarzanie wstępne

1. Obraz źródłowy podlega rozłożeniu na 1-256(max) części składowe (obraz może nie zmieścić się w pamięci przydzielonej koderowi

2. Każda składowa rozkładana jest na prostokątne części (kafelki) (64x64, 128x128,…), które są podstawowymi elementami obrazu podlegające dalszemu przetwarzaniu - mogą być kompresowane niezależnie.Im mniejsze kafelki tym większe zniekształcenia (artefakty) obrazu

3. Zmiana zakresu zmian amplitudy z (0 - 255) na (-128 - 128) (dla 8 bitowego obrazu).

4. RGB YCrCb podobnie jak w JPEG , zmniejszenie korelacji pomiędzy pikselami - efektywniejsza kompresja Transformacja RGB w YCrCb może być odwracalna (typ integer, DTF -

całkowitoliczbowa) lub nieodwracalna (typ float, DTF - zmiennoprzecinkowa)

Tak uzyskany element podstawowy jest transformowany za pomocą dwuwymiarowej dyskretnej transformaty falkowej (2D DTF) - zespół filtrówcyfrowych o współczynnikach zmienno- lub stałopozycyjnych.

2D transformata falkowa:

Współczynniki transformaty odpowiadające poszczególnym pasmom częstotliwości (przestrzennej) zgrupowane w tzw. poziomach dekompozycji - w obrębie każdej przetwarzanej części obrazu

Predykcyjna transformata falkowa - algorytm obliczeniowo szybszy, mniej zmiennych pomocniczych - oszczędność pamięci pamięci.

1. Podział - próbki dzielone są na dwie grupy nazywane parzystymi i nieparzystymi

2. Obliczenie aproksymacji i detali:

3. Skalowanie aproksymacji i detali

Kwantyzacja

Współczynniki transformaty falkowej są kwantyzowane za pomocą kwantyzatora ze martwą strefą. Dla każdego podpasma b używany jest ten sam rozmiar kwantyzacji ∆b, wg zależności:

Całkowe przekształcanie Fouriera

Definicja

proste przechowanie odwrotne prezekształcenir

całka Fouriera jest miarą „zawartości” oscylacji o pulsacji ω w funkcji x(t)

Warunkiem istnienia transformaty Fouriera jest spełnienie przez x(t) warunków Dirichleta:

1.

2.

x(t) posiada skończone wartości maksimów i minimów w każdym skończonym przedziale

3.posiada skończoną liczbę punktów nieciągłości w każdym skończonym przedziale

Podstawowe własności przekształcenia Fouriera

Liniowość

D: Własność ta wynika bezpośrednio z liniowości operacji całkowania

Symetria

Skalowanie

Skalowaniu w dziedzinie czasu odpowiada odwrotne skalowanie w dziedzinie częstotliwośc

Jeżeli zmniejszymy skalę czasową („ściśniemy” sygnał) to będzie temu odpowiadać

poszerzenie widma tego sygnału

Przesunięcie w dziedzinie czasu

Przesunięcie sygnału w dziedzinie czasu odpowiada przesunięciu w fazie jego transformaty Fouriera. Moduły dowolnego (spełniającego warunki transf.) sygnału i sygnału przesuniętego są sobie równe.

Przesunięcie w dziedzinie częstotliwości (modulacja zespolona)

Modulacja rzeczywista

Iloczyn sygnałów

Splot sygnałów

Pochodna sygnału

Całka sygnału

Korelacja sygnału

Równość Parservala

---