Mediansnitt
Mediansnitt är en algoritm för att sortera data av ett godtyckligt antal dimensioner i serier av uppsättningar genom att rekursivt klippa varje uppsättning data vid medianpunkten längs den längsta dimensionen. Mediansnitt används vanligtvis för färgkvantisering . Till exempel, för att reducera en 64k-färgsbild till 256 färger, används mediansnitt för att hitta 256 färger som matchar originaldatan väl.
Implementering av färgkvantisering
Anta att vi har en bild med ett godtyckligt antal pixlar och vill generera en palett med 16 färger. Lägg alla pixlar i bilden (det vill säga deras RGB-värden ) i en hink . Ta reda på vilken färgkanal (röd, grön eller blå) bland pixlarna i hinken som har störst räckvidd, och sortera sedan pixlarna enligt den kanalens värden. Till exempel, om den blå kanalen har det största omfånget, är en pixel med ett RGB-värde på (32, 8, 16) mindre än en pixel med ett RGB-värde på (1, 2, 24) , eftersom 16 < 24 . Efter att hinken har sorterats flyttar du den övre halvan av pixlarna till en ny hink. (Det är detta steg som ger median cut-algoritmen dess namn; hinkarna delas i två vid medianen av pixellistan.) Denna process kan upprepas för att ytterligare dela upp uppsättningen pixlar: välj en hink att dela (t.ex. , hinken med störst räckvidd i någon färgkanal) och dela den i två. Efter att önskat antal hinkar har producerats, snitta pixlarna i varje hink för att få den slutliga färgpaletten.