Wiosną roku 2009, ekipa lekarzy ze Szpitala Uniwersyteckiego Stanford przygotowywała dwuletniego pacjenta do badania rezonansem magnetycznym. Chłopiec, nazwijmy go Bryce, wydawał się maleńki we wnętrzu przepastnego metalowego urządzenia. Pluszana małpka zwisająca z wejścia do skanera niezbyt rozweselała obrazek. Bryce nie mógł widzieć pluszaka - był pod wpływem ogólnego znieczulenia, z rurką wijącą się od jego gardła do respiratora znajdującego się obok skanera. Dziesięć miesięcy wcześniej chłopcu przeszczepiono część wątroby dawcy by zastąpić jego niewydolny organ. Przez jakiś czas czuł się dobrze. Ale ostatnie wyniki badań wykazały coś niepokojącego. Coś było nie tak - istniało niebezpieczeństwo, że drogi żółciowe były niedrożne. Shreyas Vasanawala, radiolog, nie był pewny, jaka była tego przyczyna i miał nadzieję, że rezonans magnetyczny ujawni odpowiedź. Vasanawala potrzebował idealnie dokładnego obrazu, ale by go uzyskać pacjent musiałby pozostać zupełnie nieruchomo. Jeżeli Bryce wziąłby oddech, obraz byłby zamazany. Rozwiązaniem było głębokie znieczulenie, które zatrzyma oddech. Wykonanie standardowego rezonansu zajęłoby dwie minuty, ale gdyby anestezjolodzy wstrzymali oddech dziecka na tak długo, jego niesprawna wątroba stałaby się najmniejszym z problemów.
Z tego względu Vasanawala i jego współpracownik, inżynier elektronik Michael Lustig, zamierzali użyć o szybszej metody skanowania. Maszyna do rezonansu magnetycznego, którą dysponowali stosowała eksperymentalny algorytm zwany oszczędnym próbkowaniem - który jest obecnie jednym z najgorętszych tematów w matematyce stosowanej. W przyszłości mógłby odmienić sposób, w jaki szukamy odległych galaktyk. Na dziś, jego zastosowanie oznacza, że lekarze potrzebowali jedynie 40 sekund by uzyskać nieskazitelny obraz wątroby Bryce'a.
Oszczędne próbkowanie to matematyczna metoda, która tworzy zbiory danych o wysokiej rozdzielczości z próbek o małej rozdzielczości. Może być wykorzystana by wskrzesić stare nagrania, wykryć sygnał radiowy wroga i generować obrazy rezonansu magnetycznego o wiele szybciej.
Oszczędne próbkowanie w akcji
| 1 Pobierz próbkę Kamera, lub inne urządzenie przechwytuje tylko niewielką, losowo wybraną część pikseli, które normalnie składają się na dany obraz. Pozwala to zaoszczędzić pamięć i czas. | 2 Uzupełnij luki Algorytm zwany minimalizacją I1 zaczyna od wybrania jednego z nieskończenie wielu sposobów uzupełnienia brakujących punktów. | 3 Dodaj kształty Algorytm zaczyna sukcesywnie modyfikować obraz, umieszczając kolorowe kształty na obrazie. Celem jest osiągnięcie "rzadkości", która jest miarą prostoty obrazka. | 4 Znajdź mniejsze kształty Algorytm umieszcza najmniejszą możliwą liczbę najprostszych kształtów, które pasują do oryginalnych pikseli. Na przykład, gdy wykryje cztery sąsiadujące ze sobą zielone piksele, zastąpi je zielonym prostokątem. | 5 Uzyskaj wyraźny obraz Iteracja po iteracji, algorytm dodaje coraz mniejsze kształty, dążąc do maksymalnego uproszczenia obrazu. Ostatecznie powstaje obraz, który jest prawie doskonałym odwzorowaniem obrazu o wysokiej rozdzielczości. |
Oszczędne próbkowanie działa mniej więcej tak: masz zdjęcie - nerki, prezydenta, nie ważne czego. Zdjęcie składa się z miliona pikseli. Przechwytując obraz tradycyjnie należy wykonać milion pomiarów. W oszczędnym próbkowaniu, zaledwie niewielką część - powiedzmy 100 000 losowo wybranych punktów z różnych części obrazka. Od tego momentu pozostaje ogromna, prawie nieskończona liczba sposobów, na które można wypełnić pozostałe 900 000 pikseli.
Kluczem do znalezienia jedynego prawidłowego rozwiązania jest idea rzadkości, matematyczny sposób wyrażenia prostoty obrazka, lub jej braku. Obraz składający się z kilku wyraźnych elementów - kolorowych prostokątów czy krętych linii jest rzadki. Obraz wypełniony losowymi, chaotycznymi kropkami nie jest. Okazuje się, że z mrowia możliwych rekonstrukcji obrazu, najprostsza, czyli najrzadsza, jest prawie zawsze właściwa.
Ale jak szybko przemielić liczby, które są potrzebne do znalezienia najprostszego obrazu? Analiza wszystkich możliwych kombinacji zajęłaby setki cennych godzin. Candes i Tao, wynalazcy tej metody, wiedzieli, że najprostszy obraz składa się z najmniejszej liczby elementów. Wiedzieli też, że mogą użyć minimalizacji l1 by go znaleźć i zrobić to szybko.
Aby tego dokonać, algorytm opierając się na niepełnym obrazie, próbuje wypełnić puste przestrzenie blokami koloru. Jeżeli wykryje grupę zielonych pikseli, może stworzyć zielony prostokąt, który je zawiera. Jeżeli znajdzie zbitkę żółtych punktów, zawrze je w dużym żółtym prostokącie. W obszarach, gdzie kolorowe punkty są wymieszane, umieści co raz mniejsze prostokąty lub inne kształty, które wypełnią przestrzenie między kolorami. Ostatecznie wynikiem przekształceń jest obraz składający się z najmniejszej możliwej liczby obszarów, w którym każdy z 1 miliona pikseli został wypełniony kolorem.
Matematycy Candes i Tao nie gwarantują, że otrzymany obraz jest najprostszy, lub że jest dokładnie tym obrazem, którego szukaliśmy. Ale udowodnili matematycznie, że prawdopodobieństwo pomyłki jest nieskończenie małe. Obliczenia mogą wymagać kilku godzin pracy procesora w przeciętnym laptopie, ale lepiej poczekać godzinę niż zatrzymać oddech dziecka na dodatkową minutę.
Oszczędne próbkowanie już zdążyło wywrzeć imponujący wpływ na naukę. Dzieje się tak, ponieważ każdy interesujący sygnał jest rzadki - należy tylko znaleźć sposób zdefiniowania jego rzadkości. Na przykład, dźwięk akordu fortepianowego jest kombinacją niewielkiego zbioru nut. Ze wszystkich możliwych częstotliwości, które mogłyby wybrzmiewać, tylko kilka jest aktywnych. A zatem algorytmu można użyć do odtworzenia pełnego brzmienia nagrań, w których brakuje dźwięków o pewnej częstotliwości. Wystarczy zastosować minimalizację l1 by wypełnić luki, a wynik prawie na pewno będzie brzmiał dokładnie jak oryginał.
Obecnie oszczędne próbkowanie już zmienia sposób, w jaki zbierane są informacje medyczne. Zespół z Uniwersytetu Wisconsin, z udziałem firmy GE, sprzęga oszczędne próbkowanie z technologiami zwanymi HYPR i VIPR by przyspieszyć niektóre badania rezonansem magnetycznym, w niektórych przypadkach nawet kilka tysięcy razy. Tymczasem maszyny rezonansu magnetycznego stosujące oszczędne próbkowanie są w stanie uzyskać obraz trzy razy szybciej niż konwencjonalne skanery.
Tak skrócony czas badania okazał się wybawieniem dla Bryce'a. Z pomieszczenia kontrolnego Vasanawala dał znak anastezjologom - podali pacjentowi zastrzyk i wyłączyli respirator. Vasanawala rozpoczął badanie, podczas gdy lekarze monitorowali pracę serca i poziom natlenienia krwi chłopca. Czterdzieści sekund później badanie było skończone, a Bryce nie ucierpiał z powodu niedoboru tlenu. Kilka godzin później algorytm wygenerował ostry obraz wątroby chłopca, wystarczająco wyraźny by zlokalizować na nim zatory w przewodach żółciowych. Umieszczając cieniutkie rurki w przewodach, udało się usunąć złogi i przywrócić ich prawidłową pracę. I w ten sposób - dzięki szczypcie matematyki i szczypcie medycyny - wyniki Bryce'a wróciły do normy.
Źródło obrazków i oryginalnego tekstu: wired.com
Jeżeli wiesz co nie co na temat oszczędnego próbkowania i widzisz błędy w tłumaczeniu - proszę o kontakt.
