Schneller Algorithmus zum Erkennen von Hauptfarben in einem Bild?

Question

Kennt jemand einen schnellen Algorithmus, um Hauptfarben in einem Bild zu erkennen?

Ich verwende derzeit K-Means, um die Farben zusammen mit Python PIL zu finden, aber es ist sehr langsam. Ein 200 x 200-Bild dauert 10 Sekunden. Ich habe mehrere hunderttausend Bilder.

Answer 1

Eine schnelle Methode wäre, den Farbraum einfach in Bins aufzuteilen und dann ein Histogramm zu erstellen. Es ist schnell, weil Sie nur eine kleine Anzahl von Entscheidungen pro Pixel benötigen, und Sie brauchen nur einen Durchlauf über das Bild (und einen Durchlauf über das Histogramm, um das Maximum zu finden).

Update: Hier ist ein grobes Diagramm, um zu erklären, was ich meine.

Auf der X-Achse ist die Farbe in einzelne Bins unterteilt. Die Y-Achse zeigt den Wert jedes Fachs an. Dies ist die Anzahl der Pixel, die dem Farbbereich dieses Fachs entsprechen. Es gibt zwei Hauptfarben in diesem Bild, die durch die zwei Spitzen angezeigt werden.

Answer 2

K-Mittel ist eine gute Wahl für diese Aufgabe, weil Sie Anzahl der Hauptfarben vorher wissen. Sie müssen K-Means optimieren. Ich denke, Sie können Ihre Bildgröße reduzieren, skalieren Sie sie einfach auf 100x100 Pixel oder so. Finden Sie die Größe, auf der Ihr Algorithmus mit akzeptabler Geschwindigkeit arbeitet. Eine andere Option ist die Dimensionalitätsreduktion vor dem k-Means-Clustering.

Und versuchen Sie, schnelle K-Means-Implementierung zu finden. Solche Dinge in Python zu schreiben ist ein Missbrauch von Python. Es sollte nicht so benutzt werden.

Answer 3

Mit ein wenig Bastelei, this code (was ich Sie vermuten, dass vielleicht schon gesehen haben!) Beschleunigt werden kann, um knapp unter einem zweiten

Wenn Sie den kmeans(min_diff=...) Wert auf etwa 10 erhöhen, produziert sie sehr ähnliche Ergebnisse in 900ms, aber läuft (im Vergleich zu etwa 5000-6000ms mit min_diff=1)

Weiterhin ist die Größe der Vorschaubilder zu 100x100 Abnahme scheint nicht die Ergebnisse viel entweder zu beeinflussen, und nimmt die Laufzeit etwa 250 ms

Hier ist eine leicht abgewandelte Version des Kabeljaus e, die nur parametrisiert den min_diff Wert und enthält einen schrecklichen Code, um eine HTML-Datei mit den Ergebnissen/Timing

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)