Dominerende farver med k-means clustering

Her er en hurtig og simpel implementering af k-means clustering, der bruges til at finde en palette af dominerende farver i et billede.

Koden er hostet i en Observable notebook.

Lad os tage et billede

Lad os for eksempel tage dette flotte farverige foto taget af Jacek Dylag på Unsplash:

For at spare på ydeevnen (husk, vi kører denne kode i browseren) tager vi en stikprøve på 1000 tilfældige pixels fra billedet:

Det er næsten umuligt at gætte det originale billede ud fra disse prikker, men fordi de er tilfældigt udvalgt, kan vi bruge dem som stikprøvedata.

Fotoets størrelse er 600*399, hvilket giver os 239.400 pixels. Hver pixel har 3 dimensioner: rød, grøn og blå (RGB) og kan repræsenteres som en vektor:

pixel = [R,G,B]

Lad os visualisere stikprøvens punkter ved at tegne 2D-projektioner af det 3D RGB-farverum:

K er for cluster

k-means clustering er en metode til vektorkvantisering, der oprindeligt stammer fra signalbehandling og er populær til klyngeanalyse i data mining. k-means clustering sigter mod at opdele n observationer i k klynger, hvor hver observation tilhører den klynge med det nærmeste gennemsnit, som fungerer som en prototype for klyngen. Wikipedia

Den klassiske k-means-algoritme består af følgende trin:

1. Tag tilfældige k punkter (kaldet centroider) fra et rum dannet af vores datapunkter (dvs. vektorer).
2. Tildel hvert datapunkt til den nærmeste centroid. Hver centroid med tilknyttede datapunkter kalder vi en klynge.
3. Find en ny centroid for hver klynge ved at beregne midtpunktet mellem alle datapunkter i klyngen.
4. Gentag trin 2 og 3, så længe centroidernes koordinater ændrer sig.

Nemt som en leg, ikke? Ja, men der er nogle nuancer.

Ydeevne

Lad os sige, at k er antallet af klynger (samt centroider), n er antallet af datapunkter, d er antallet af dimensioner (vektorlængde), og i er antallet af iterationer (hvor mange gange trin 2 og 3 skal køres). Groft sagt vil kompleksiteten være:

O(k * n * d * i)

Det kan være ret langsomt, og her er nogle simple måder at gøre det hurtigere:

1. Find de endelige centroider på stikprøvedataene, og kør derefter den sidste iteration på det fulde datasæt. Normalt reducerer dette antallet af iterationer på det fulde datasæt betydeligt.
2. Sæt en øvre grænse for antallet af iterationer, så metoden ikke fryser for evigt.
3. Sæt en minimal afstand, hvor centroider betragtes som ens. I min kode sparede dette 3–5 iterationer, når afstanden er mindre end en, men stadig lidt større end nul.
4. Hvis du bruger euklidisk afstand, behøver du ikke beregne roden — den kvadrerede afstand er tilstrækkelig.

Afstand og skala

1. Kvadreret euklidisk afstand er den simpleste, men den er måske ikke ideel til at beregne farveforskelle.
2. RGB-farverummet er meget simpelt, men hvis man virkelig har brug for at beregne farveforskellen præcist, bør man bruge Lab og CIEDE2000.

Det optimale antal k

For at finde det optimale k finder jeg den gennemsnitlige varians for hver klynge på stikprøvedataene. Kort sagt er en klynges varians den gennemsnitlige afstand mellem dens centroid og hvert punkt i klyngen. Den gennemsnitlige varians for et givet k er altså den gennemsnitlige varians for alle dets klynger. Hvis vi tegner et diagram, hvor variansen er på y-aksen og k er på x-aksen, ser vi, at variansen falder, men på et tidspunkt aftager hældningen markant, og efter denne værdi af k kan man endda observere en stigning i variansen:

Lad os nu sætte det hele sammen:

1. Tag et stikprøvedatasæt.
2. Find centroider for forskellige k på stikprøvedatasættet.
3. Find ud af, fra hvilket k variansen bremser sit fald.
4. Kør k-means clustering med de givne initiale centroider på det fulde datasæt.

Voila:

De store cirkler repræsenterer centroider. Jo større en cirkel er, jo flere datapunkter er tildelt denne centroid.

Og det posteriserede billede: