Algoritmo veloce per rilevare i colori principali in un'immagine?

Question

Qualcuno conosce un algoritmo veloce per rilevare i colori principali in un'immagine?

Attualmente sto usando k-means per trovare i colori insieme al PIL di Python ma è molto lento. Un'immagine 200x200 impiega 10 secondi per l'elaborazione. Ho diverse centinaia di migliaia di immagini.

Answer 1

Un metodo veloce sarebbe quello di suddividere semplicemente lo spazio colore in contenitori e quindi costruire un istogramma. È veloce perché hai bisogno solo di un piccolo numero di decisioni per pixel, e hai solo bisogno di un passaggio sull'immagine (e un passaggio sull'istogramma per trovare i massimi).

Aggiornamento: ecco un diagramma approssimativo per aiutare a spiegare cosa intendo.

Sull'asse x è il colore diviso in bin separati. L'asse y mostra il valore di ciascun contenitore, che corrisponde al numero di pixel corrispondenti all'intervallo di colori di quel contenitore. Ci sono due colori principali in questa immagine, mostrati dai due picchi.

Answer 2

K-means è una buona scelta per questo compito, perché si sa il numero di colori principali in anticipo. Devi ottimizzare K-means. Penso che tu possa ridurre le dimensioni dell'immagine, ridimensionandola a 100x100 pixel o giù di lì. Trova la dimensione su come funziona il tuo algoritmo con velocità accettabile. Un'altra opzione è usare la riduzione della dimensionalità prima di k-means clustering.

E cercare di trovare un'implementazione veloce di k-means. Scrivere cose simili in Python è un uso improprio di Python. Non dovrebbe essere usato in questo modo.

Answer 3

Con un po 'di ritocchi, this code (che ho il sospetto che si potrebbe avere già visto!) Può essere accelerato a poco meno di un secondo

Se si aumenta il valore kmeans(min_diff=...) a circa 10, che produce risultati molto simili , ma viene eseguito in 900ms (rispetto a circa 5000-6000ms con min_diff=1)

Ulteriori diminuendo la dimensione delle miniature a 100x100 non sembra influenzare i risultati molto neanche, e prende il runtime a circa 250ms

Ecco una versione leggermente modificata del cod e, che ha appena parameterises il valore min_diff, e include un codice terribile per generare un file HTML con i risultati/tempi

from collections import namedtuple 
from math import sqrt 
import random 
try: 
    import Image 
except ImportError: 
    from PIL import Image 

Point = namedtuple('Point', ('coords', 'n', 'ct')) 
Cluster = namedtuple('Cluster', ('points', 'center', 'n')) 

def get_points(img): 
    points = [] 
    w, h = img.size 
    for count, color in img.getcolors(w * h): 
     points.append(Point(color, 3, count)) 
    return points 

rtoh = lambda rgb: '#%s' % ''.join(('%02x' % p for p in rgb)) 

def colorz(filename, n=3, mindiff=1): 
    img = Image.open(filename) 
    img.thumbnail((200, 200)) 
    w, h = img.size 

    points = get_points(img) 
    clusters = kmeans(points, n, mindiff) 
    rgbs = [map(int, c.center.coords) for c in clusters] 
    return map(rtoh, rgbs) 

def euclidean(p1, p2): 
    return sqrt(sum([ 
     (p1.coords[i] - p2.coords[i]) ** 2 for i in range(p1.n) 
    ])) 

def calculate_center(points, n): 
    vals = [0.0 for i in range(n)] 
    plen = 0 
    for p in points: 
     plen += p.ct 
     for i in range(n): 
      vals[i] += (p.coords[i] * p.ct) 
    return Point([(v/plen) for v in vals], n, 1) 

def kmeans(points, k, min_diff): 
    clusters = [Cluster([p], p, p.n) for p in random.sample(points, k)] 

    while 1: 
     plists = [[] for i in range(k)] 

     for p in points: 
      smallest_distance = float('Inf') 
      for i in range(k): 
       distance = euclidean(p, clusters[i].center) 
       if distance < smallest_distance: 
        smallest_distance = distance 
        idx = i 
      plists[idx].append(p) 

     diff = 0 
     for i in range(k): 
      old = clusters[i] 
      center = calculate_center(plists[i], old.n) 
      new = Cluster(plists[i], center, old.n) 
      clusters[i] = new 
      diff = max(diff, euclidean(old.center, new.center)) 

     if diff < min_diff: 
      break 

    return clusters 

if __name__ == '__main__': 
    import sys 
    import time 
    for x in range(1, 11): 
     sys.stderr.write("mindiff %s\n" % (x)) 
     start = time.time() 
     fname = "akira_940x700.png" 
     col = colorz(fname, 3, x) 
     print "<h1>%s</h1>" % x 
     print "<img src='%s'>" % (fname) 
     print "<br>" 
     for a in col: 
      print "<div style='background-color: %s; width:20px; height:20px'>&nbsp;</div>" % (a) 
     print "<br>Took %.02fms<br> % ((time.time()-start)*1000)