Algoritmus spočítání všech unikátních barev v bitmapě

Alikuj to pole dynamicky dle potreby. Nepotrebujes naalokovat vsehcny kombinace, protoze takovy JPG mit nebudes.
Naalokuj nejake rozumne mnozstvi - 10,000 a az se dostanes na konec, pridej polovinu. Az se dostanes na konec, pridej polovinu atd...

To je sice hezké, ale tím se podle mně hodně časově zesložití to vyhodnocování, pokud nebude to dynamicky alokované pole setříděné (což by taky zdržovalo), jak budeš hledat, jestli nějaká barva už tam byla, nebo se má přidat?

na truecolor ti bude stačit 3-rozměrné pole 256 bit x 256 bit x 256 bit alias 32kB paměti...

edit: je to blbost, zpětná rekonstrukce není možná.

edit2: nesmysl, rekonstrukce není třeba, funguje to, za předpokladu, že se použije ještě počitadlo. Pak stačí přičítat, když bude "v kostce" na daných souřadnicích nula (následně změněná na jedničku), jinak byla barva již zaznamenána.

edit3: jsem se trochu zamotal, ono není třeba ani to počitadlo, ale je to optimální řešení než to potom znova zbytečně procházet. Zároveň se tím ale vygenerují indexované barvy obrázku (takže JE to rekonstruovatelné - zapomněl jsem, že jednotlivé osy jsou jasně definovány jako R-G-B).

edit4: a připadne mi to i celkem efektivní, defacto se to bude dát řešit velmi jednoduše xorováním a orováním, tj. velmi nenáročné operace z hlediska výpočetního výkonu - jediné náklady na výpočty budou v okamžiku převodu bajtové hodnoty jednotlivých barvových kanálů na indexový bit.

256*256*256 bitov je 2MB.

no jo! Jak jsem došel k těm 32kB?

edit: no jo, já to počítal jako 32B^3

edit2: řekl bych, že tam máš chybu. je to 2 mega, ale 2 megabity ve 3D poli, takže pro přepočet na bajty bys měl dělit 8^3...

Teď jsem se do toho zamotal taky.
Teoreticky je třeba uložit 2^24 bitů, což jsou ty cca 2MB dat což odpovídá adresaci jednorozměrného pole v této velikosti.
U trojrozměrného pole by se tedy mělo uložit stejné množství bitů, jediný rozdíl je v adresaci ne?
Ale když si vemu každou složku jako index, přičemž každý ještě rozdělím po 8-mi, tzn 256/8=32B, pak ve třech rozměrech se opravdu zdá že 32B^3 je 32KB paměti, to je přece ale jen 262144 bitů???
Tak jak to teda je?
Abstraktní myšlení mi dnes nějak nejede už ani ve třech rozměrech
Na n-rozměrné prostory, ze kterých se mi točila hlava, když jsem si měl představit třeba kolmici, už raději ani nevzpomínám...

problém/vtip je právě v těch vyšších rozměrech..

A nemohl bys mi to prosím zkusit nějak vysvětlit? To trojrozměrné pole zabere v paměti 32768 Bajtů, neboli 262144 bitů. Takže maximální počet spočítatelných barev bude 262144 ne? Má jich teoreticky být ale 16777216!

máš tam taky chybu. Je to 3D- takže 32768B = 8^3 * 32768B = 16,7Mb

To je celé kouzlo.

Vzpomeň si, jak se přepočítávají kubické míry (vždy třetí mocnina) - 1m3 = 1x(10^3)^3 mm3 = 1 000 000 000 mm3 (viz index u kubíků)

O kubickom bajte (8 x 8 x 8 bitov) som este nepocul. Bajt nema 8 x 8 x 8, ale len 8 bitov.

Takze je to 256 x 256 x 256 bitov = 256 x 256 x 256 / 8 bajtov = 2MB.

Jo, taky to tak vidím...

ok. 32B x 32B 2D zabírá přesně 1KiB. pokud jich vytvořím 32, pak budou zabírat přesně 32KiB.

Maj pravdu oni, ze (proc 32B?), kaslete na nasobeni - je to 16mil barev a do dokaze reprezetovat 16mil 0/1 coz deleno 8mi dává pocet bajtu ktere je potřeba - 2mb, nezávisle na zvrhlickém násobení.

Edit: zádrhel bude tady:

Ale když si vemu každou složku jako index, přičemž každý ještě rozdělím po 8-mi,

Takhle to nefunguje...
Mám RGB 3 bajtové hodnoty, k nimž potřebuju někam uložit 1 bit. Kdybych měl to tebou navržené pole
rgb : array[0..31,0..31,0..31] of byte;
tak ten index musí vycházet z bytových hodnot RGB přičemž z každé z nich mi zbyde ještě hodnota 0-7, podle které musím zapsat do toho adresovaného byte 1 bit. Já tam mám ale jen 8 bitů, a potřebuju jich 8x8x8=512? A jsem zpátky na 16777216b neboli cca 2MB.

špatně.

- máš pole bitů o délce 256bit tj. 32byte, klidně reprezentované nějakým polem booleanů (podle toho co tvůj jazyk umí a podporuje - technicky to lze realizovat i jako 4xbyte nebo 2xinteger - jen budeš muset provést binární konverzi pořadí barvy a dohledání správného bitu ve správné pozici ve vyšším ordinálním typu napříč třemi dimenzemi).
- složky jakékoli barvy mají v RGB 3x256hodnot, od 0 do 256, tomu odpovídá "průsečík" pořadí bitů v každé "ose" R-G-B, tj. např. pro 100-120-255 bude zapsána logická jednička do pole 100,120,255)
- před zápisem jen zkontroluješ, zda už tam jednička je či není, pokud už jednička je, nic neřešíš a jdeš na další pixel (barvu). Pokud tam jednička není, zapíšeš jedničku a zvýšíš počitadlo o jednotku, protože jsi našel novou barvu.

Tvůj omyl je v tom, že pole stavíš na bajtech, přitom ti stačí nikoli číselná hodnota, ale prosté ano/ne na zjištění toho, zda se už objevila daná variace s opakováním pro tři čísla od 0 do 255.

edit: abych předešel hádkám: samozřejmě záleží na implementaci toho, jak je typ boolean, případně jeho pole v daném jazyku implementován(o) - zda je v paměti alokován opravdu jako bit, nebo jako byte (pak by samozřejmě toto snažení z hlediska přeloženého kódu bylo zbytečné, a proto výše zmiňuju "okliku" přes integer)

Bohužel nemám jazyk, který by uměl pole bitů nebo booleanů (Ty ano? To snad umí jen nějaké jednočipy, klasické procesory pokud vím adresují jenom bajty), tak jsem to chtěl obejít polem bajtů, jenže se mi nějak v představách pomíchaly adresy a hodnoty. Stále mi to nedochází, budu ještě zkoumat...

Já zase neznám žádný jazyk, který by nemuměl pole booleanu :D, i kdyby neuměl tak alokuješ 8xmenší pole a poradíš si rozumným hash algoritmem, jako například první dvakrát 256 do pole a pak OR bajtově do proměnné

Aha, špatně jsem se vyjádřil, pole booleanů ano, ale ty zabírají v paměti minimálně 1 bajt.

možná tvoje pole, ja kdyz chci bajt v paměti tak ho dostanu - v C++ určitě, v Delphi ktere ma integorovany ASM taky, ale urcite jak jsem psal vejš je 8x větší a tak se mi tam vejde 8x více informací. Například mam 24 bitovou barvuto je 111111111111111100000010 tak si alokuju pole o velikosti ten tvuj bajt krát x 2na16 tzn ty dvě mega: a uložim to takto:

POLE(1111111111111111):=POLE(1111111111111111) OR 000000010;

Print: POLE(1111111111111111):
2=00000010

1. vše záleží na "iteligenci" kompilátoru, jak se s tím popasuje. Logika věci říká, že "chytrý" kompilátor pole boolů zkompiluje do integeru a bude s ním interně pracovat efektivně

2. pokud je kompilátor blbý, je to na pogromátorovi, aby pogrom uspořádal podle svého

3. nenuťte mě, abych si po 20 letech nainstaloval zase nějaký "těžký" programovací jazyk, když už jsem se jednou zařekl, že pogromovat nebudu..

No tak nic... Jsem tě chtěl vyzvat, ať to napíšeš

A aký máš jazyk?
Tu máš niečo v jave: www.programmersheaven.com

Efektivnejsie sa ta 16 megabitova bitmapa (nemysim obrzaok, ale to 2MB pole) da ulozit do stromu.

Napr. 256 ukazovatelov, kazdy ukazuje na pole 256 ukazovatelov a tie uz budu ukazovat na pole 256 bitov. Na zaciatku bude vsetkych 256 poloziek nastavenych na null a alokovat sa budu podla potreby.

Jeden z odkazů od strejdy:
http://blogs.mathworks.com/steve/2008/01/31/counti ng-occurrences-of-image-colors/

kde jsou ti tipnci, co porád tvrdí, ze 4GB stačí každému? Asi staci, ale kdo se má srát s algoritmem kvuli trapným 2MB ram?

Problem totiz je - co vlastne chces, otazka je jestli to chces rychle nebo s ohledem na pamet, je mezitim jasnej trade-off.

Honza ma jednoznacne pravdu, ze muzes alokovat jen pole, které je nutné pro daný obrázek a pak ho zvětšovat dynamicky - a NE ROZHODNE to neovlivni slozitost (ne n krát, maximálně n logkrát a doví jestli).

Dalsi vec je, jak velky ten obrázek bude - kazdá barva jiná - 4000x4000+px, aby se alokovaly cele 2MB.
--
Dolni mez algoritmu (jak nejrychleji to asyptoticky teoreticky lze, omezeni daneho problemu) je dána výstupem a to je NxN a to jak pro paměti tak pro výpočetní složitost s tim nic neuděláš. A ty máš asyptoticky stejnou.
--

Pro specialni obtázky by se asi dal najít rychlejší algortmus, ale ne o moc.

A vubec neni to nahodou prace pro streamy na grafiku? Tohle by melo byt threadovato a pocitano na graficke karte ci VLIW nebo neco takoveho ;)

Problem totiz je - co vlastne chces

Chci si procvičit hlavu... přijít na co nejméně náročný algoritmus...