Sprzętowe wdrożenie algorytmu kodowania obrazów SPIHT w urządzenia FPGA

Set Partitioning in Hierarchical Trees (SPIHT) jest wydajną technologią kodowania obrazów, bazującą na EZW (Embedded Zerotree Wavelet) i dyskretnej transformacie falkowej (DWT) opracowaną przez Amir’a Said’a i William’a Pearlman’a w 1996. Algorytm sortuje współczynniki transformaty falkowej używając struktury drzewa hierarchicznego. Zwiększa wydajność i czas wykonania kodowania w porównaniu do EZW.
Największą wadą kodowania SPIHT jest użycie (teoretycznie) trzech dynamicznych list zawierających informację o porządku sortowania współczynników transformaty falkowej. Jednak we wszystkich dostępnych opracowaniach używane były cztery dynamiczne listy – 3 wynikające z założeń kodowania i 1 tymczasowa lista do zaawansowanego sortowania drzewa hierarchicznego. Algorytm w tej postaci był niewdrażalny w urządzenia FPGA (Field Programmable Gate Array) ze względu na pamięć potrzebną do jego wykonania. Podstawowym celem tej pracy była modyfikacja bazowego schematu w celu maksymalnego zredukowania wykorzystania pamięci.
Do optymalizacji algorytmu wykorzystana była technologia Java. W związku ze swoją specyfikacją nie jest to najlepszy język do aplikacji bazujących na przetwarzaniu sygnałów, ale do przedstawienia różnic pomiędzy oryginalnym i zmodyfikowanym algorytmem nadaje się znakomicie. Wdrożenie w urządzenie FPGA zostało wykonane w oparciu o środowisko projektowo-symulacyjne firmy Xilinx.
Rozdział pierwszy zawiera opis kodowania SPIHT wraz ze wszystkimi informacjami wstępnymi niezbędnymi do zrozumienia tego kodowania. Po kolei przedstawione są: falki, transformaty falkowe, progresywne kodowanie obrazów, EZW i SPIHT. Załączone są kody źródłowe wykorzystania praktycznego algorytmu.
Rozdział drugi odnosi się do FPGA. Pokazana jest ich architektura wraz z porównaniem do innych podobnych urządzeń.
W rozdziale trzecim przedstawiony jest zestaw rozwiązań ograniczających rozmiar list dynamicznych lub eliminujących je całkowicie. Po wprowadzeniu zmian zużycie pamięci spadło o 61 %. Dodatkowo pokazany jest wpływ zmian na jakość kodowania. Czas kompresji uległ znacznemu skróceniu bez żadnej straty jakości. Załączone są kody źródłowe zmodyfikowanego kodowania.
Rozdział czwarty opisuje wdrożenie zmodyfikowanego algorytmu w urządzenie FPGA.