Autor Zpráva
Darker
Profil
Mám dostupný set barev (55) a chci do nich přvést jakýkoli obrázek. Potřebuji tedy v daném setu najít pro každý pixel vstupního obrázku nejbližší možnou variantu barvy.
Sestavil jsem následující skript, ale výsledky nejsou takové, jaké bych čekal:
   /*Testovaná barva je v proměnných r,g,b
                     Paleta dostupných barev je $this->colorsfull

                */
                 $difference=3*255+1;     //Větší o 1  než největší možný rozdíl
                 $best = -1;                      //ID nejlepší volby
                 for($i=4; $i<count($this->colorsfull); $i++) {
                   $rozdil = abs($r-$this->colorsfull[$i][0])+abs($g-$this->colorsfull[$i][1])+abs($b-$this->colorsfull[$i][2]);
                   if($rozdil<$difference) {
                     $best=$i;  
                     $difference=$rozdil;   
                   }          
                 }
                 $p=$best;
                 echo "Best match for ($r,$g,$b) is (".implode(",",$this->colorsfull[$p]).")";
Vrací například:
Best match for (0,255,0) is (0,124,0)
Když jsem se snažil testovat barvy odděleně, (proměnná difference byla polem o třech členech) dostával jsem taky špatné výsledky. (hnědá místo červené)


Podle mně by nejlepším řešením bylo převedení RGB na jedno číslo (to co mi vrací imagecolorat) a porovnávat pak tato čísla namísto polí. Nepovedlo se mi to ale dohledat, google vrací samá řešení převodu mezi webovým HEX vyjádřením čísel a složkovým.
margin
Profil *
Myslím si, že bys měl zjistit rozdíl jasové a barevné složky, něco, jako počítá třebas http://www.sovavsiti.cz/kontrast/, ale tebe bude zajímat, kdy je kontrast nejnižší.
Alphard
Profil
Ten nápad sčítat rozdíly není špatný, ale dělá se to se čtverci pod odmocninou. Navíc namícháním např. bílé barvy lze zesvětlit jinak plochu, takže pak nejde o jednotlivé pixely. Viz http://en.wikipedia.org/wiki/Color_quantization
mimochodec
Profil
Darker:
Podle mně by nejlepším řešením bylo převedení RGB na jedno číslo (to co mi vrací imagecolorat) a porovnávat pak tato čísla namísto polí.

To si nemyslím. Ta funkce to převádí na jedno číslo takovým způsobem, že v něm ty barvy mají váhu 256^2, 256, 1. Takže kdybys porovnával dvě barvy, kde se červená složka liší o 1, spočtená vzdálenost by byla 256x větší než kdyby rozdíl modrých složek byl maximální.

S algoritmem asi nepomůžu, jen dám tip, že ř. 9-12 můžeš nahradit jedním použitím funkce http://cz2.php.net/manual/en/function.min.php. Rychlost neznám, ale to určitě otestuješ.

A vůbec.. opravdu neexistuje funkce "najdi v poli polí trojici, která se od mé trojice bude lišit nejmíň"?
Keeehi
Profil
mimochodec:
ř. 9-12 můžeš nahradit jedním použitím funkce http://cz2.php.net/manual/en/function.min.php
To by nešlo.

opravdu neexistuje funkce
Pokud vyžaduješ funkci, tak by se k tomu dala využít usort, ovšem je to zbytečně výpočetně náročnější než to, jak to má Darker.



Pokud zakomponujeme Alphardovu poznámku
$rozdil = ($r-$this->colorsfull[$i][0])*($r-$this->colorsfull[$i][0])+($g-$this->colorsfull[$i][1])*($g-$this->colorsfull[$i][1])+($b-$this->colorsfull[$i][2])*($b-$this->colorsfull[$i][2]);



Alphard:
Navíc namícháním např. bílé barvy lze zesvětlit jinak plochu, takže pak nejde o jednotlivé pixely.
Tohle je jediné, co jsem snad nepochopil.



Ještě bych to trochu poupravil. Co když budou 2 barvy, které budou mít stejnou vzdálenost a zároveň by byly nejbližší? Pak se bude upřednostňovat ta, co je v poli dříve. Já bych z nich vybíral náhodně. A ta iniciace lze udělat také chytřeji. Takže to raději celé přepíšu:
                 // začínám také od indexu 4 jako v ukázce i když nevím proč
                 $difference= ($r-$this->colorsfull[4][0])*($r-$this->colorsfull[4][0])+($g-$this->colorsfull[4][1])*($g-$this->colorsfull[4][1])+($b-$this->colorsfull[4][2])*($b-$this->colorsfull[4][2]);
                 $best = array(4);
                 for($i=5; $i<count($this->colorsfull); $i++) {
                   $rozdil= ($r-$this->colorsfull[$i][0])*($r-$this->colorsfull[$i][0])+($g-$this->colorsfull[$i][1])*($g-$this->colorsfull[$i][1])+($b-$this->colorsfull[$i][2])*($b-$this->colorsfull[$i][2]);
                   if ( $rozdil<$difference ) {
                     $best=array($i);  
                     $difference=$rozdil;   
                   } elseif ( $rozdil == $difference ) {
                     $best[]=$i;  
                   }    
                 }
                 $p=$best[array_rand($best)];
                 echo "Best match for ($r,$g,$b) is (".implode(",",$this->colorsfull[$p]).")";
Alphard
Profil
Keeehi:
Tohle je jediné, co jsem snad nepochopil.
Asi jsem to blbě popsal, zmínil jsem to jen na okraj. Jde o skládání barev, když pro větší plochu není v paletě optimální barva, lze proložením určitého procenta pixelů jinou než nejbližší barvou vizuálně změnit odstín. Vedlejší efekt je, že to způsobí zrnitost.
mimochodec
Profil
Keeehi:
To by nešlo.

Aha, pravda. Přehlídl jsem to $i, pardon.
Darker
Profil
Tak se mi po dlouhé době povedlo zprovoznit internet...
Alphard
Navíc namícháním např. bílé barvy lze zesvětlit jinak plochu, takže pak nejde o jednotlivé pixely.
To si bohužel nemohu dovolit, výstup má 128*128 px.

Keeehi:
začínám také od indexu 4 jako v ukázce i když nevím proč
První čtyři jsou průhledné a mají složení 0,0,0. V sestavě barev nemám černou.

Nakonec se mi povedlo přijít na pythagorovské sčítání (sqrt(a*a+b*b+c*c)), nicméně to bohužel nestačilo. Pro počítač je nejtmavší barvou v mojí paletě tmavě zelená (0,87,0) nicméně místo černé bych raději viděl šedou (79,79,79). Tohle jsem vyřešil tak že k rozdílu přičítám rozdíl nejvyšší a nejnižší barevné hodnoty (max(rgb)-min(rgb)). Celý výpočet rozdílu tedy vypadá takto:
//$ss je výše uvedený rozdíl pro vstupní barvu - počítá se před započetím cyklu FOR
$rozdil=sqrt(pow(($r-$this->colorsfull[$i][0]),2)+
                                  pow(($g-$this->colorsfull[$i][1]),2)+
                                 pow(($b-$this->colorsfull[$i][2]),2)
)+
abs($ss-(max($this->colorsfull[$i])-min($this->colorsfull[$i])))/2;
Celý rozdíl maxima a minima ještě dělím dvěma - to je v podstatě jen náhodné číslo zmenšující význam tohohle faktoru. Ačkoliv to pořád nepřevede úplně všechno dokonale, po pár testech to beru jako dostačující. Pokud někdo ještě vymyslí nějaké vylešení (hlavně rychlostní, skript to počítá docela dlouho) budu vděčný.
Co se týče rychlosti, zajímalo by mě jestli Keeehiho řešení součinu ve čtverci je rychlejší než funkce pow, kterou jsem použil já.
Keeehi
Profil
Darker:
Co se týče rychlosti, zajímalo by mě jestli Keeehiho řešení součinu ve čtverci je rychlejší než funkce pow, kterou jsem použil já.
Je takový problém si udělat výkonnostní test? Funkce je univerzálnější, proto bude IMHO v nejlepším případě stejně rychlá. V mém příkladu se ten rozdíl musí počítat 2x, což funkce pow dělat nemusí takže v mém případě by to šlo ještě předpočítat do proměnných a ty pak jen násobit. Já vlastně ani nevím, jak se počítají odmocniny (vlastně možná nějak přes logaritmus), ale vím, že druhou mocninu je rozhodně lehčí vyočítat, než druhou odmocninu, proto ten výraz sqrt(A) + B bych upravil na A + B*B, to by to mělo podle mě zrychlit. Navíc se při tom zbavíte funkce abs (i když její náročnost nebude zase až tak vysoká)

Jinak k tomu času generování 128 * 128 = 16 384 pixelů, každý se porovnává s 50x, to je cca 800 000 porovnání a k tomu stejné množství výpočtů aby se mohlo porovnávat. Možná by pak stálo za to nalezené výsledky cachovat. Když se tedy pracně dobereme k tomu, že nejbližší k 0,25,12 je 0,87,0 tak si to poznamenáme a příště, až narazíme na 0,25,12 už to nemusíme znovu počítat. Toto se však nevyplatí u obrázků, kde je každý pixel jiný.
Alphard
Profil
Darker:
Je to zajímavé téma, nemůžeš zveřejnit aspoň tu paletu barev? Chvíli bych si s tím hrál, ale jsem líný vytvářet testovací podmínky.
Darker
Profil
Keeehi:
Je takový problém si udělat výkonnostní test?
Moc takovým testům nevěřím, zejména pokud se provádějí na počítači a ne na rychlém a výkonném serveru dávají často nerelevantní výsledky. Navíc, pokud se ptám na efektivní řešení chci i vědět proč tomu tak je abych příště podobný problém dokázal vyřešit úvahou a ne testem.

proto ten výraz sqrt(A) + B bych upravil na A + B*B
To zkusím.

Možná by pak stálo za to nalezené výsledky cachovat.
Uvažoval jsem o tom, ale zatím jsem se na to vykašlal. Pokud to ale budu dělat, chci nejdřív umět zjistit jak moc je obrázek fragmentovaný. Asi nejlepší by bylo pracovat s paletou obrázku a jednotlivým indexům palety rovnou přiřazovat dostupné barvy.

Alphard:
http://www.minecraftwiki.net/wiki/Map_Item_Format - vycházím z tohoto.
V třídě mám pouze 13 základních barev, jejich odstíny derivuji jen případě potřeby:
           private $colors = array(array(  0,  0,  0),array(127,178,56 ),array(247,233,163),array(167,167,167),array(255,  0,  0),
                         array(160,160,255),array(167,167,167),array(0,  124,  0),array(255,255,255),array(164,168,184),
                         array( 183,106,47),array(112,112,112),array(64, 64, 255),array(104, 83, 50)
           );     
Derivace vypadá asi takhle:
private $conversion = array(180,220,255,220);
/*$id je id v rámci plné palety (0-55)*/
             $basicid = floor($id/4);
             $offset = $id%4;
               $tmp = $this->colors[$basicid]; 
               for($i=0; $i<3; $i++) {
                 $tmp[$i] = round(($tmp[$i]*$this->conversion[$offset])/255);
               }
Pokusím se případně někam nahrát celou třídu, bohužel mám 5-10kb/s vytáčené připojení které soustavně vypadává, takže to asi potrvá.
Alphard
Profil
Darker:
Nakonec se mi povedlo přijít na pythagorovské sčítání (sqrt(a*a+b*b+c*c)), nicméně to bohužel nestačilo. Pro počítač je nejtmavší barvou v mojí paletě tmavě zelená (0,87,0) nicméně místo černé bych raději viděl šedou (79,79,79). Tohle jsem vyřešil tak že...
Pozoroval jsem podobný problém, po pár pokusech se jako použitelné řešení zdá nejen hledat minimální diferenci, ale i kontrolovat její absolutní hodnotu (konstantu pro porovnání jsem našel metodou pokus-omyl).
Když žádná barva nevyhoví podmínkám, upravím testovaný pixel (aby byl tmavší nebo světlejší, ale zachoval barevný odstín) a znovu zkusím najít blízkou barvu. Je-li to potřeba, iterativně opakuji, dokud se něco nenajde.

Výsledné obrázky se mi líbí, ale faktem je, že je to dost pomalé, určitě to půjde lépe, ale zatím jsem neměl moc čas se tomu věnovat . Jestli se k tomu někdy vrátím, možná i v jiném jazyce, napíši.

Vaše odpověď

Mohlo by se hodit


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm: