Tablica Podglądu LUT

Wstęp

Tablica Podglądu LUT pozwala przyśpieszyć przetwarzanie obrazów podczas operacji bezkontekstowych. Główną zaletą tego jest przygotowanie wszystkich możliwych wyników, a następnie ich jedynie odczytywaniu zamiast kolejnych obliczeń. W tym artykule zostanie przedstawiony przykład zastosowania tej metody.

Zastosowanie

Operacja bezkontekstowa polega na przekształceniu piksela obrazka niezależnie. Może ono polegać na wykonaniu pewnego działania na wartości piksela. Podczas przekształcania należy pamiętać, że piksel może mieć wartość od 0 do 255. Przykładowo dodanie do każdej wartości piksela 10 rozjaśni obrazek. Wykonywanie takiej operacji jest proporcjonalne do ilości pikseli w obrazku. Mogłoby się wydawać, że nie można tego przyśpieszyć...

Zauważmy jednak, że rozjaśnianie obrazka to co najmniej dwie operacje: zwiększenie wartości i wykonanie operacji modulo na tej wartości, aby nie wyjść poza zakres. (Można też zaimplementować dodawanie z nasyceniem, aby uniknąć przepełnienia zmiennej.) W przypadku bardziej skomplikowanych przekształceń liczba potrzebnych operacji drastycznie zwiększa się. Można tego uniknąć poprzez przygotowanie tablicy LUT (ang. lookup table).

Piksel może przyjmować wartość od 0 do 255, a więc w całym obrazku tylko te 256 wartości może wystąpić i dla każdej wartości można wyliczyć co jest wartością wynikową. Zużywamy wtedy bardzo mało dodatkowej ilości pamięci, ale nie musimy obliczać dla tej samej wartości przekształcenia wiele razy. Chcą przekształcić piksel wystarczy pobrać wartość piksela wynikowego z tablicy LUT. Dzięki temu uzyskujemy praktycznie taką samą złożoność algorytmu niezależnie od wykonywanego przekształcenia.

Przykładowa tablica LUT rozjaśniająca obrazek o 10 to:

Implementacja

Przekształcenie wartości

Przypuśćmy, że przekształcenia piksela wygląda następująco:

1. def Oblicz(a):
2.   return (2 * a + 1) % 256

Przekształcenie Obrazka

Bez używania tablicy LUT przekształcenie obrazka wyglądałoby następująco:

1. def Przeksztalc(macierz):
2.   for y in range(len(macierz)):
3.     for x in range(len(macierz[0])):
4.       macierz[y][x] = Oblicz(macierz[y][x])
5.   return macierz

Każdemu pikselowi przypisujemy wartość obliczoną przy pomocy wzoru podanego wyżej. Dla obrazka 1000 x 1000 wymaga 3000000 operacji arytmetycznych (dla każdego piksela wykonujemy operację mnożenia, dodawania oraz modulo).

Szybkie Przekształcenie Obrazka

Liczbę operacji zmniejszamy do absolutnego minimum poprzez przygotowanie wcześniej tablicy LUT jak w poniższym kodzie:

1. def Przeksztalc(macierz):
2.   lut = [Oblicz(x) for x in range(255)]
3.   for y in range(len(macierz)):
4.     for x in range(len(macierz[0])):
5.       macierz[y][x] = lut[macierz[y][x]]
6.   return macierz

Powyższy kod oszczędza liczbę operacji dla obrazka 1000 x 1000 do 1000768 (trzy operacje arytmetyczne dla każdej z 256 wartości i 1000000 operacji przepisania wartości z tablicy LUT). Innymi słowy algorytm działa w przybliżeniu prawie trzy razy szybciej. Główną zaletą jest jednak to, że dla tej wielkości obrazka liczba potrzebnych operacji się nie zwiększy, ale dla funkcji bez LUT będzie wprost proporcjonalne do złożoności przekształcenia.

Testowanie funkcji

Macierz wartości reprezentującą można wprowadzić do programu przy pomocy poniższego fragmentu kodu:

1. n = int(input("Podaj szerokość obrazka\n n = "))
2. m = int(input("Podaj wysokość obrazka\n n = "))
3. print("Podaj elementy macierzy:")
4. macierz = []
5. for i in range(m):
6.   tab = [int(x) for x in input().split()]
7.   macierz.append(tab)
9. macierz = Przeksztalc(macierz)
10. for y in range(len(macierz)):
11.   for x in range(len(macierz[0])):
12.     print(macierz[y][x], end=" ")
13.   print()

• Kod źródłowy Przekształcenie Obrazka
• Kod źródłowy Szybkie Przekształcenie Obrazka