UWAGA! Z rozmów z Państwem wynika, że potrzebne są pewne istotne wyjaśnienia:
1. Kwestia numeryki – spodziewane jest pojawianie się czasem problemów natury numerycznej spowodowanych złym uwarunkowaniem niektórych zadań interpolacji/aproksymacji. Trzeba to jakoś obsłużyć (wiadomość dla użytkownika, wykrywanie NAN/INF w wynikach, itp.) oraz opisać.
2. Nie interesują mnie porównania z efektywnością zapisu do plików (choć komentarze i rozważania n/t minimalnego narzutu na rozmiar pliku mogą być wartościowe). Kiedy piszę o “współczynniku kompresji” mam na myśli zmianę liczby bitów/bajtów potrzebnych do zapisu zestawu obrazków – tj. porównanie (liczby pikseli*liczba bitów reprezentacji piksela) vs. (liczba współczynników*liczba bitów reprezentacji współczynnika).
Nasze ostatnie i największe zadanie będzie łączyć tematykę aproksymacji i kompresji danych. Naszym celem będzie zaimplementowanie i przetestowanie prostego algorytmu do kompresji stratnej sekwencji podobnych obrazów.
Rozważmy przykładowy zestaw obrazów pochodzących z kamerki internetowej (wersja w osobnych plikach tutaj):
Widać na przykładzie, że jasność każdego piksela na określonej pozycji (x,y) zmienia się w czasie wg pewnego schematu. Będziemy chcieli wykorzystać przewidywalną zmienność jasności pomiędzy wartościami kolorów tego samego piksela na kolejnych obrazach do zmniejszenia wielkości plików.
Wykorzystamy w tym celu aproksymację wielomianami. W najprostszym przypadku, mamy do czynienia z obrazami w skali szarości, więc każdy piksel odpowiada jednej wartości od 0 do 255. Oznaczmy piksele na pozycji x,y w obrazie i-tym jako p[x,y,i]. W przypadku obrazów RGB, będziemy musieli każdą składową reprezentować oddzielnie. Rozważmy ciąg wartości jasności danego piksela w kolejnych obrazach p[x,y,:]. W naszym przypadku, kiedy mamy 60 obrazów, mamy 60 liczb do reprezentowania dla każdej pozycji x,y. Możemy ten ciąg wartości przybliżyć wielomianem stopnia k<60, przy czym dla k=59 będziemy mogli uzyskać wielomian, który reprezentuje dokładnie zadane wartości (bez straty). Jeśli użyjemy mniejszego k, np. 20, to będziemy mieli trzykrotnie mniej liczb do zapamiętania, ale będziemy też mieli pewien błąd aproksymacji.
Nasze zadanie polega na:
1. implementacji narzędzia do zakodowania zestawu obrazów (wszystkie w tym samym formacie, tej samej rozdzielczości, jak w przykładzie) jako wielomianów aproksymacyjnych określonego stopnia. Narzędzie powinno obliczać współczynniki wielomianów i zapisywać je do pliku (kompresja) oraz powinno mieć opcję odtworzenia plików graficznych (przybliżonych) wynikających z zapamiętanej zmniejszonej reprezentacji. pliki powinny nazywać się encode.py i decode.py i przyjmować parametr k i nazwy plików jako parametry wywołania (przetwarzane przy pomocy modułu Argparse lub podobnego)
2. Wykonanie testów tego narzędzia polegających na wykonaniu kompresji dla różnych k i zmierzeniu błędu średniokwadratowego dla przykładowego zestawu obrazów oraz dla zestawu losowych macierzy o tych samych wymiarach. Warto w porównaniu uwzględnić oczekiwany i uzyskiwany współczynnik kompresji.
3. Napisanie krótkiego raportu (w pdf, nie więcej niż 3 strony, może być z wykresami) opisującego przyjęte założenia w rozwiązaniu i wyniki.
Punktacja:
napisanie programów encode i decode – skomentowanych i działających – 16 pktów (10 pktów jeśli tylko dla skali szarości)
wykonanie testów – 3 punktów
napisanie dobrego raportu – 6 punktów.
Bonus – można dostać dodatkowe 5 punktów za rozszerzenie algorytmu o zachłanne łączenie reprezentacji sąsiadujących pikseli. Tzn: jeśli reprezentacja wielomianowa dwóch sąsiednich pikseli (np. na niebie) jest podobna, tzn. generuje niewiele większy błąd średniokwadratowy, to możemy ją zastąpić jedną reprezentacją (+ ewentualnie inna stała). Powinno to (kosztem dłuższego wyliczania encode i bardziej skomplikowanego formatu oraz nieco gorszego wyglądu obrazów) dawać sporo lepszą kompresję.
Rozwiązania nadsyłamy na mój adres e-mail do 2. czerwca z dopiskiem [ONA-3-2019] w tytule maila.