Jeśli chcesz w przyszłości zostać guru...

Co jakiś czas wertując różne nowości i ciekawostki ze świata nauki natrafia się na coś, co pachnie technologią przyszłości. Nie takiej za 50 czy sto lat. Takiej za 5 albo 10. Ostatnio mój kandydat numer jeden to technika tzw. compressed sensing rozwijana przez różne grupy zajmujace się przetwarzaniem sygnałów, głównie w USA, wsparte matematycznie przez taką sławę jak Terence Tao.

Zastosowania compressed sensing, które autorzy najczęściej podają, wiążą sie głównie z akwizycją i kompresowaniem obrazów, choć zastosowania potencjalne idą znacznie dalej. Postaram się w trzech słowach objaśnić co na razie z tego rozumiem.

Compreessed sensing jak wszystko co ma w nazwie "compressed" opiera sie na pewnej redundancji, czyli nadmiarowości w sygnale jakim w naszym przykładzie jest obraz. W klasycznym kodowaniu stratnym proces z grubsza wygląda tak:

(1) najpierw zbieramy dość dokładną informację o sygnale. Dokładność przekłada się zwykle na częstość próbkowania - na przykład w przypadku obrazu w aparacie cyfrowym na ilość elementów czułych w matrycy. Dostajemy pewien wektor w bazie, której każdy element przedstawia jeden piksel. Taka baza to zbiór wektorów postaci:

e_m,n(t,k) = 1 gdy t = m, k = n i 0 w innym wypadku.

W tej bazie obraz ma M na N pikseli ma przedstawienie:

OBRAZ = a_1,1 * e_1,1+...+a_M,N*e_M,N

gdzie a_m,n oznacza poziom jasności piksela. W tej bazie zwykle większość a_i,j jest sporych i nie możnaby łatwo ograniczyć się do części z nich by reprezentować obraz.

(2) Potem dokonujemy transformaty, czyli wyliczamy przedstawienie tego wektora w bazie transformaty.

W przypadku dyskretnej transformaty Fouriera będzie to baza postaci

F_m,n(t, k) = exp(2*pi*i*(t*m/M + n*k/N)).

W tej bazie, nasz wektor będzie miał przedstawienie:

OBRAZ = b_1,1 * F_1,1+...b_M,N*F_M,N.

Tu, zwykle okazuje się, że jest lepiej i pewna niewielka część współczynników dominuje ¹. Oczywiście możemy używać innych baz: np falek (wavelet) itp.

(3) Dokonujemy pewnych uproszczeń na sygnale korzystając z tej jego miłej cechy po przedstawieniu w bazie transformaty o której wspomniałem powyżej i dostajemy


OBRAZ' = b_1,1' * F_1,1+ ...b_M,N' *F_M,N



gdzie współczynniki primowane są bliskie nieprimowanych ale wiele z nich jest po prostu zerem. Wektor OBRAZ' jest bliski wektorowi OBRAZ.


(4) Na drugą stronę linii trzeba więc przekazać (względnie schować do pliku) indeksy i ich wartości tych niezerowych współczynników primowanych



(5) Odtwarzający (odpakowujący) odtwarza z tego co zapisane w punkcie (4) OBRAZ'.


Na ile dobrze to działa (modulo szczegóły techniczne, konkretne transformaty itp. bo zasada jest ta sama) możemy oglądać codziennie przeglądając obrazki na stronach WWW czy oglądając film na DVD.

A teraz wyobraźmy sobie, że nie musimy martwić się przekazywaniem informacji o tym podzbiorze ani o wartościach współczynników. Że zamiast mierzyć wszystkie piksele w kroku 1 mierzymy jedynie ich niewielką ale znaną część, że w ogóle pomijamy krok 2 i krok 3, i przesyłamy tylko wyniki tego pomiaru. Najpierw zalety: postępując w ten sposób mamy:

- mierzenie z kroku 1 staje się tańsze (bo mniej mamy punktów pomiarowych - np. w aparacie zamiast 5 mpx mamy tylko 1 mpx).

- pomijamy niezbyt może kosztowny w epoce FFT, ale mimo wszystko niedarmowy krok 2

- przesyłamy tylko wyniki pomiarów a nie dbmy o przesyłanie indeksów

- wciąż mamy sygnał skompresowany, bo choć przesyłamy wymniki pierwotnego pomiaru, to jest ich istotnie mniej niż w oryginalnym problemie

No dobrze: ale tym sposobem przesłaliśmy znacznie mniej informacji. Mniej jej wydobyliśmy z sygnału (mniej próbek) i nie dokonaliśmy żadnej analizy by wydobyć najcenniejszą jej część. Co zatem zyskaliśmy powyżej tracimy w postaci istotnego zaniku informacji. Nie ma darmowych obiadów... A jednak...

Przy pewnych założeniach, które wkrótce ostrożnie wypowiem (pamiętajcie, piszę co na razie sam z tego rozumiem) taka magia może mieć miejsce. Otóż:

Pomysł compressed sensing polega na tym, że jeżeli wiemy coś o sygnale ponad to co przesyła nam nadawca to coś może nam dać ową brakującą informację, której nikt nam nie przesłał i pozwolić na lepszą rekonstrukcję sygnału² Co to za magiczna wiedza ? Pisałem trochę wyżej, że kompresja się uda jeżeli sygnał będzie kombinacją liniową niewielu wektorów bazy transformaty. Zatem, jeżeli mamy dobrze dobraną do klasy sygnałów bazę i wiemy że sygnały z klasy którą rozważamy mają w niej przedstawienia rzadkie, możemy po stronie odbiorcy zapytać: jaki sygnał będący kombinacją liniową niewielu wektorów bazy transformaty da nam w bazie pomiarowej nasz wynik?

Okazuje się, że odpowiadając na to pytanie w wielu przypadkach jesteśmy w stanie zrekonstruować rzeczywisty sygnał, który tak niechlujnie pomierzyliśmy. W jeszcze większej ilości przypadków jesteśmy w stanie odtworzyć sygnał bliski temu wyjściowemu. Problem: jak to zrobić?

Sposób jest taki: sprowadzić zagadnienie do problemu optymalizacji. Więzy, czyli ograniczenia na sygnał zadane są przez początkowy pomiar. Jeżeli wektory pomiarowe oznaczymy przez e₁,...,e_K a wyniki naszego pomiaru (a więc współczynniki w rozkładzie rzutu wektora OBRAZ na podprzestrzeń generowaną zbiór pomiarowy) przez a₁,...,a_K ograniczenia na poszukiwany sygnał X dają się zapisać jako:

<e₁|X>=a₁, <e₂|X>=a₂,...<e_K|X>=a_K.

Teraz drugi warunek na X, który pozwoli nam wybrać jeden wektor z tej podprzestrzeni. Złym, choć naturalnie narzucającym się sposobem jest poszukiwać wprost wektora którego przedstawienie będzie najrzadsze w bazie transformaty. Złym bo prowadzącym do olbrzymiej, niewykonalnej w praktyce - ilości obliczeń. Pomysł wieć jest taki, żeby zminimalizować pewną normę na przstrzeni sygnału. Okazuje się jednak, że minimalizując (znowu narzucającą się) normę euklidesową | |₂ na ogół dochodzimy do wektora, który nie ma przedstawienia rzadkiego w bazie transformaty. Rozsądnym kompromisem pomiędzy obydwoma podejściami jest minimalizacja normy | |₁ powiązanej z bazą tranformaty

F_1,1, ..., F_M,N

tzn normy takiej, że:


|b_1,1 * F_1,1+ ...b_M,N *F_M,N|₁ = |b_1,1|+...+|b_M,N|


Taki problem jest zagadnieniem klasycznej optymalizacji wypukłej i sposoby jego rozwiązywania są dobrze znane.

Są dwa wybory, których trzeba tu dokonać. Pierwszy to - i jak mawiają Niemcy: hier liegt der hund begraben - wybór bazy transformaty. To ona musi być dobrana do klasy sygnału.
Drugi to wybór zbioru pomiarowego. Okazuje się, że rozmieszczenie wektorów którymi mierzymy sygnał "większość" jest dobra, tzn. można owe wektory wybrać praktycznie losowo. Natomiast ich ilość - aby dostać dobrą rekonstrukcję sygnału musi być rzędu A*log(B) gdzie A to rzadkość sygnału (a więć ilość elementów o niezerowych współczynnikach w przedstawieniu sygnału w bazie) a B to rozmiar tej bazy.

Podobno przykłady pokazują, że teoretyczne ograniczenia w poprzednim paragrafie w praktyce można jeszcze proprawić. Czyli jeśli empiria pokazuje, że jeśli mamy dobrą bazę, to sygnały spotykane w codziennym życiu nawet przy mniejszej ilości pomiarów dają się nieźle zrekonstruować.

Wydaje się, że wielki jest potencjał tych metod. Zarówno do przesyłania i transmisji sygnałów, jak i do rekonstrukcji - np. w obrazowaniu medycznym (choćby tomografia), itd. Zasosowanie do innych sygnałów niż obrazy - np mowy też może być ciekawe. Znowu przesyłanie jest ok, ale jeszcze ciekawsza może być rekonstrukcja z bardzo słabego albo silnie zniekształconego sygnału. Wydaje się, że od specyficznych zastosowań, np. obrazy twarzy itd. itd. można dobrać doskonale pasujące bazy i ich zastosowanie może dać ogromne, nieosiągalne dziś poziomy kompresji. Wydaje się też, że metoda może dać niezwykle tanie i energooszczędne a dokładnie obrazujące czujniki, kamery itp.

Słowem - matematyka w służbie ludzkości. Tak, stanowczo - jeśli chcecie zostać guru telekomunikacji, przetwarzania sygnałów itd. za lat 5-10 uczcie się o compressed sensing już dziś.




¹OK. W rzeczywistości wystarczy nam że sprowadzimy do takiego przedstawienia w bazie, które dobrze się pakuje kompresją bezstratną. "Rzadkość" przedstawienia (a więc duża ilość współczynników zerowych w przedstawieniu w bazie) daje możliwość dobrego upakowania. Dla dyskusji compressed sensing pozostanę przy tej cesze.



²Zupełnie jak paleontolog który z fragmentów kości dinozaura jest w
stanie zrekonstruować zwierzę, ponieważ wie, że rekonstruuje dinozaura.