Konwersja palety obrazu

[Sauron]

Witam, potrzebuję sposobu/algorytmu na konwersję palety kolorów w obrazie. Chodzi mi o ograniczenie kolorów do danej liczby. Coś jak binaryzacja tylko że nie do 2 tylko 4, 16, itd. Oczywiście obraz ma być kolorowy (wyjątek: 2bpp). Kombinowałem już z 2-bitową paletą, coś z zakresami, itp. ale wyszło coś takiego:



Nie wiem czy takie coś jest w ogóle do przyjęcia, więc prosiłbym o pomoc.

[inż. Avallach]

Nie rozumiem problemu. O ile masz dostęp do odczytu i zapisu wartości poszczególnych pixeli, pozostają ci tylko dwie rzeczy do ustalenia:
 - to jakie kolory mają wchodzić w skład palety (takie z równymi "odległościami" między sobą, czy też wybrane optymalnie według dotychczasowego składu obrazu?)
 - to jak wybrać jaki kolor z palety ma zastąpić dany kolor z obrazu wejściowego (dość oczywiste: najbliższy mu)

[Sauron]

A co jakbym miał obraz w którym występują głównie 2 kolory np. krajobraz plaży (żółty i błękitny)? Chodzi mi o ograniczenie kolorów do najbardziej trafnych  (w tym przypadku 2).

[inż. Avallach]

No to musisz zrobić algorytm obliczający optymalną paletę. To już jest trudniejsza sprawa. Po pierwsze, będziesz musiał napisać funkcję obliczającą liczbowy wskaźnik "odległości" między kolorami, którego będziesz używał do oceniania która z propozycji jest trafniejsza w stosunku do danego pixela - powinien brać pod uwagę jasność, nasycenie i odcień. Pozostaje kwestia wyboru tych propozycji. Tutaj musiałbym się rozpisać, a nie mam za bardzo na to czasu. Proponuję ci na razie rozwiązać uproszczony problem i na jego podstawie przejść do tego dotyczącego kolorów. Otóż wyobraź sobie że masz zbiór losowych liczb naturalnych i masz obliczyć N nowych, tak że średnia różnica między każdą z liczb wejściowych, a najbliższą jej z nowych, będzie jak najmniejsza. 

[inż. Avallach]

Mój pomysł na szybko:
1. Tworzysz paletę N kolorów i tą samą ilość liczników (na razie wyzerowanych). Wszystkie kolory ustawiasz na średnią koloru wszystkich pixeli na obrazie.
2. Dla każdego pixela na obrazie (nazwijmy go x):
   2.1 Sprawdzasz który z kolorów z palety jest mu najbliższy (nazwijmy go a).
   2.2 Ustawiasz ten kolor w palecie na średnią ważoną tego koloru w palecie i sprawdzanego koloru na obrazie, gdzie wagą pierwszego jest jego licznik (nazwijmy go _a), a wagą drugiego jeden. Czyli a = (_a*a+x) / (_a+1). Zwiększasz licznik o 1 (czyli wywołujesz _a++).

W wyobraźni działa. Zakłada że masz metody pozwalające wirtualnie sumować kolory lub w inny sposób policzyć średnią ważoną (po prostu traktuj składowe jako liczby bez górnego ograniczenia). No i że, tak jak napisałem w poprzednim poście, jesteś w stanie zmierzyć "odległość" między dwoma kolorami. Najprostsza propozycja: r : różnica, j : jasność, n: nasycenie, b : barwa, a : kolor pierwszy, z : kolor drugi : r = j(a) - j(z) + n(a) - n(z) + b(a) - b(z)  - zakładając że funkcje j, n i b przyjmują ten sam zakres wartości (np 0-100).

Oczywiście zamiast na literkach robisz to na tablicach i dopisujesz odpowiednie metody.