Instrukcja będzie rozłożona na dwa zajęcia. Skupiać się ona będzie na stosowaniu różnych algorytmów w dokonania kompresji bezstratnej danych. Będziemy zajmowali się dwoma algorytmami, które realizują to zadanie — Kompresję strumieniową (RLE (Run-Length Encoding), ByteRun) oraz drzewem czwórkowym (Quad Tree). Drzewo Czwórkowe może służyć również do innych celów, ale w ramach instrukcji będziemy skupiać się tylko na elemencie kompresji.

Uwagi ogólne do zadań i zapisywania danych w pamięci

Python nie jest środowiskiem, w którym łatwo oszacować ile miejsca w pamięci zajmują konkretne zmienne. Całość jest przechowywana w sposób dynamiczny i niektóre typy danych złożonych posiadają duży narzut pamięci (np. tablice). DO sprawdzenia rozmiaru w pamięci najlepiej wykorzystać funkcję get_size opisaną kawałek dalej. Dodatkowym utrudnieniem może być fakt, że domyślnymi typami danych są int32 i float64 (lub w niektórych przypadkach 32/64-bitowe), a obrazy przechowywane w tablicach NumPy, są na przykład uint8. Dlatego porównanie ich rozmiaru w pamięci może również być zaburzone. Dlatego dla rzetelności warto nasz obraz oryginalny przerzutować do domyślnego typu w waszym środowisku:

img=img.astype(int)

Domyślnie pamiętajcie, że dla każdego z algorytmów tworzycie dwie funkcje — kodującą i dekodującą. Funkcja kodująca będzie przyjmowała na wejściu domyślnie np.array dowolnego rozmiaru (nie musi być to obraz, może być to wektor wartości). Funkcja dekodująca powinna przyjąć jedną zmienną zwróconą z funkcji kodującej i na jej podstawie odtworzyć oryginalne dane. Czyli informacja na temat rozmiaru oryginału powinna również być tam umieszczona. Przykładowo pierwsza wartość skompresowanej informacji może zawierać informację o ilości wymiarów oryginału.

Jeżeli planujecie tworzyć własne struktury danych, to starajcie się pilnować objętości zmiennych w pamięci i ich narzutu. Przykładowo krotka (tuple) () zajmuje mniej miejsca w pamięci niż tablica (zwykła nie NumPy) [], ponieważ umożliwia tylko odczyt danych. Z kolei dla większych obiektów tablica NumPy może wykorzystywać dodatkowe zaimplementowane wewnątrz algorytmy optymalizacji pamięci.

Praca z danymi wielowymiarowymi

W jaki sposób zapisać informację na temat dowolnej wymiarowości danych wykorzystując tylko \(N+1\) wartości (N to ilość wymiarów)? Podpowiedź:

# wersja python list
x=[len(data.shape)] #informatcja na temat ilości wymiarów
x+=list(data.shape)
# wersja NumPy
x=np.array([len(data.shape)])
x=np.concatenate([x,data.shape])

W jaki sposób przekształcać dane do i z jednego wymiaru?

Array1D=ArrayND.flatten() # spłaszczanie
ArrayND=Array1D.reshape(OG_Shape) # odtwarzanie

Sprawdzanie rozmiaru danych w Pythonie

Dla typów prostych łatwo policzyć rozmiar zajmowanych bitów pamięci (ilość elementów pomnożona przez ilość bitów dla pojedynczego obiektu tego typu lub funkcja sys.getsizeof(obj)), jednak dla typów złożonych nie jest to takie proste. To otrzymania w dość dokładnej estymacji zajętości pamięci można wykorzystać poniższą funkcję, która w sposób rekurencyjny pozwala nam określić, jak dużo miejsca w pamięci zajmują nasze dane.

import sys

def get_size(obj, seen=None):
    """Recursively finds size of objects"""
    size = sys.getsizeof(obj)
    if seen is None:
        seen = set()
    obj_id = id(obj)
    if obj_id in seen:
        return 0
    # Important mark as seen *before* entering recursion to gracefully handle
    # self-referential objects
    seen.add(obj_id)
    if isinstance(obj,np.ndarray):
        size=obj.nbytes
    elif isinstance(obj, dict):
        size += sum([get_size(v, seen) for v in obj.values()])
        size += sum([get_size(k, seen) for k in obj.keys()])
    elif hasattr(obj, '__dict__'):
        size += get_size(obj.__dict__, seen)
    elif hasattr(obj, '__iter__') and not isinstance(obj, (str, bytes, bytearray)):
        size += sum([get_size(i, seen) for i in obj])
    return size

Jak zrobić konsolowy pasek postępu w Pythonie

Słów kilka o pakiecie tqdm i o tym, jak można go wykorzystywać. Służy on do generowania pasków postępu dla wykonywanych pętli. Można go stosować, aby wizualizować postęp programu i nie zastanawiać się nad tym, czy program się nie zawiesił lub ile czasu jeszcze to zajmie. Zakładamy jednak, że znamy jakąś skończoną maksymalną ilość iteracji, w ramach której pętla skończy się wykonywać. Przykładowo dla przejścia pętli po wektorze, maksymalna ilość iteracji będzie równa jego długości. Możemy wyróżnić dwa wywołania:

1. W sposób automatyczny dla pętli for o stałym kroku. Dodajemy ją podczas definiowania pętli for jako kontener otaczający zakres wywołania naszej pętli.

   from tqdm import tqdm
   for i in tqdm(range(0,1110)):
       #do something

2. Dla pozostałych przypadków — sterowne ręcznie. Na początku deklarujemy nasz pasek postępu (w przykładzie jako pbar), wraz z maksymalną ilością kroków (parametr total). Następnie podczas każdej iteracji pętli musimy ręcznie przesunąć licznik o ilość kroków, o którą przesunęliśmy się z naszymi obliczeniami.

   from tqdm import tqdm
   with tqdm(total=max_steps) as pbar:
       while(...):
           #do something
           pbar.update(step)

Uwaga wywoływania funkcji print wewnątrz pętli może powodować problemy wizualne w konsoli.

Przypadki testowe

1. Dla kompresji strumieniowej:

   np.array([1,1,1,1,2,1,1,1,1,2,1,1,1,1])
   np.array([1,2,3,1,2,3,1,2,3])
   np.array([5,1,5,1,5,5,1,1,5,5,1,1,5])
   np.array([-1,-1,-1,-5,-5,-3,-4,-2,1,2,2,1])
   np.zeros((1,520))
   np.arange(0,521,1)

2. Dane testowe dla drzewa czwórkowego i kompresji strumieniowej:

   np.eye(7)
   np.dstack([np.eye(7),np.eye(7),np.eye(7)])

Zadania

1. Znaleźć 3 obrazy do przeprowadzanie analizy skuteczności kompresji (Rozmiar minimalny 800x600 mogą być większe.), każdy ma reprezentować jedną z kategorii (0,2 pkt):
   1. Rysunek techniczny,
   2. Wzór dokumentu, formularza lub innego dokumentu tekstowego zawierającego tekst, tabele, wykresy itd.,
   3. Kolorowe zdjęcie.
2. Napisać samodzielnie kod dokonujący kompresji strumieniowej dla omawianych metod w formie koder i dekoder. Koder powinien przyjmować jako wejście pojedynczą zamienną tablicową NumPy, a dekoder powinien zwracać zmienną w oryginalnym kształcie z identyczną zawartością danych. Pomiędzy dekoderem a koderem przekazujemy tylko jedną zmienną. Ma ona zawierać wszystkie informacje potrzebne do odtworzenia danych wejściowych (dane, kształt itd.). Kod, który będzie przekazywał te dane w inny sposób lub odtwarzał kształt poza funkcją dekodującą będzie traktowany jako źle wykonany. Do wykonania:
   • RLE (0,4 pkt),
   • ByteRun (0,4 pkt).
3. Napisać kod kompresji QuadTree rodzajów kompresji w formie koder i dekoder. Koder powinien zwracać pojedynczą zmienną, która zawiera również informację o oryginalnym rozmiarze kompresowanej informacji. Dekoder powinien przyjmować tą zmienną i zwracać oryginalną informację. Każdy kod, który będzie to realizował poza funkcją dekodującą lub przekazywał dodatkowe informacje, będzie oceniany negatywnie. Zakładamy, że na wejściu dostajemy obraz kolorowy lub w skali odcieni szarości. Kodujemy wszystkie warstwy naraz, więc kodowanie jest niezależnie od ich ilości, tylko sam kolor będzie miał tyle wartości, ile jest warstw obrazu. (0,6 pkt)
4. Krótkie sprawozdanie/raport z prac na podstawie obu zaimplementowanych algorytmów. (0,4 pkt)
   1. Proszę poświęcić paragraf sprawozdania i opisać sposób wykorzystania pamięci przez wasze implementacje. Gdzie przechowywanych jest informacja na temat rozmiaru obrazu od odtworzenia. Jakie struktury danych wykorzystuje drzewo czwórkowe.
   2. Zaprezentować poprawność kodowania poszczególnych metod na danych testowych. Upewnić się, że dane kompresują i dekompresują się w sposób poprawny.
   3. Dla każdego z przygotowanych obrazów testowych przeprowadzić kompresję i dekompresję, każdą z metod. Udowodnić poprawność (identyczność) danych po dekompresji z danymi źródłowymi. Sprawdzić skuteczność kompresji — zarówno jako jej stopień, jak i jaki \(%\) oryginalnego obrazu stanowi obraz po kompresji.

Do oddania

• kod źródłowy (jeden plik .py),
• obrazy wybrane do testów,
• krótkie sprawozdanie z obserwacjami i wynikami (format PDF).