Ooo, już nie będzie tak kolorowo jak przy poprzednich wpisach. Zapoznamy się z problemem wyszukiwania podobnego (najbliższego) koloru dla zadanego koloru, przy założeniu, że działamy w ograniczonej palecie (np. mamy do czynienia z paletą indeksowaną).
Być może nie miałeś w ogóle styczności z tym problemem i czytasz wpis tylko z czystej ciekawości (co mnie również bardzo cieszy), więc wyjaśnię Ci na początek czym jest paleta indeksowana.
Z tym rodzajem palety mamy do czynienia, kiedy przechowujemy tabelę zawierającą pod kolejnymi indeksami kolory użyte w pliku graficznym.
Nie ma więc tu sytuacji, że każdy element grafiki (załóżmy piksel) jest określony przez indywidualny kolor. Zakładając, że mamy do czynienia z trybem RGB (bez kanału alpha) i pikselem białym w prawym górnym rogu, jest on określony poprzez grupę bajtów 255, 255, 255, a kolor czarny na prawno od niego, określony jest jako 0,0,0. Jeśli trzeci piksel jest znów biały, to jego miejsce w pliku zajmuje grupa 255, 255, 255.
W przypadku grafiki opartej na palecie indeksowanej, kolor biały może być przechowywany pod indeksem 0 w tabeli palety, a kolor czarny pod indeksem 1 tejże tabeli. Kolejność przechowywania kolorów w tabeli palety nie ma żadnego znaczenia, tzn. kolory nie muszą być ustawione w kolejności jasności czy relatywnie do położenia na kole barw. Tu trzy piksele (biały, czarny, biały) grafiki, będą reprezentowane w pliku poprzez wartości 0, 1, 0, odpowiadając indeksom w tabeli palety, czyli de facto kolorom, ale nie w sposób bezpośredni.
Rezprezentacja w pamięci obrazu (3 piksele) opartego o paletę bezpośrednią:
| 255,0,0 | 0,255,0 | 255,255,0 | 255,0,0 |
Ten sam obraz przy użyciu palety indeksowanej jest reprezentowany w następujący sposób:
| 0 | 1 | 2 | 0 |
+
| indeks | kolor |
|---|---|
| 0 | 255,0,0 |
| 1 | 0,255,0 |
| 2 | 255,255,0 |
Szczególnym przypadkiem formatu z paletą indeksowaną, byłby format reprezentujący grafiki o bardzo dużej, różnorodnej liczbie kolorów. Byłby to format niepraktyczny, ponieważ moglibyśmy osiągnąć rozmiar pliku wyjściowego większy niż w przypadku użycia pełnej palety (nieindeksowanej). Paleta indeksowana ma więc sens jeśli nakłada jakieś ograniczenie możliwych do użycia kolorów. I tak właśnie jest. Najczęściej spotykaną paletą indeksowaną jest paleta złożona z 256 indeksów (kolorów).
Nie będę tu opisywać sposobu przekształcenia grafiki pełnopaletowej na grafikę z paletą indeksowaną, ale sposób na znalezienie odpowiedniego koloru z tej ograniczonej palety, np. przy efektach graficznych. Czyli wtedy kiedy choć potrzebujemy nowy kolor, to nie możemy wyjść poza pulę kolorów, która jest dostępna w palecie.
No, ale co dalej?
Jak samo określenie wskazuje, szukamy "najbliższego". Załóżmy, że kolor jest reprezentowany przez punkt. A kiedy coś jest najbliżej danego punktu? Jeśli dzieli go najmniejszy dystans spośród odległości pomiędzy tym punktem, a innymi. Czyli co? Linijka albo centymetr wystarczy? No...nie. Musimy skorzystać tu z uprzejmości matematyki. Ale jak punkt reprezentuje kolor? Skoro mamy do czynienia z kolorem złożonym ze składowych RGB, to tak jakby były to trzy współrzędne w trójwymiarowym układzie współrzędych. Skoro jeden kolor to punkt1 w układzie 3D, a drugi to punkt2, to wystarczy obliczyć pomiędzy nimi odległość, czyli nic innego jak długość wektora w przestrzeni 3D!
Jeśli nasza składowa R to punkt X, G to punkt Y, a B to punkt Z, 1 to kolor otrzymany, a 2 kolor porównywany, to wzór wygląda tak:
ODLEGLOSC = SQRT((R2-R1)^2+(G2-G1)^2+(B2-B1)^2)
Kiedy więc w wyniku naszej operacji graficznej na obrazie znaleźliśmy jakiś nowy kolor, to szukamy najmniejszej odległości między każdym kolorem palety, a tymże nowym kolorem. Kolor z palety, który spełni warunek możemy uznać za najbardziej podobny. Może się zdarzyć, że odległość wyniesie 0, co będzie oznaczać, że nowy kolor jest kolorem, który już mamy w palecie. Aby zapobiec takiej sytuacji warto najpierw przeszukać paletę pod kątem istnienia danego koloru, a jeśli go brak, wtedy zając się wyszukiwaniem najbliższego.
Powyższą formułę można jeszcze zoptymalizować. Nie jest nam potrzebna dokładna odległość, bo interesuje nas tylko czy jedna wartość jest większa lub mniejsza od innej, tak więc z równania można usunąć pierwiastek.