Thuật toán nhanh để phát hiện màu chính trong hình ảnh?

Question

Có ai biết thuật toán nhanh để phát hiện màu chính trong ảnh không?

Tôi hiện đang sử dụng k-means để tìm các màu cùng với PIL của Python nhưng nó rất chậm. Một hình ảnh 200x200 mất 10 giây để xử lý. Tôi có hàng trăm nghìn hình ảnh.

Answer 1

Một phương pháp nhanh sẽ đơn giản là phân chia không gian màu thành các thùng và sau đó xây dựng một biểu đồ. Thật nhanh vì bạn chỉ cần một số lượng nhỏ các quyết định cho mỗi pixel và bạn chỉ cần một lượt vượt qua hình ảnh (và một lần vượt qua biểu đồ để tìm tối đa).

Cập nhật: đây là sơ đồ sơ đồ để giúp giải thích ý tôi.

Trên trục x là màu được chia thành các thùng riêng biệt. Trục y hiển thị giá trị của mỗi thùng, là số pixel phù hợp với phạm vi màu của thùng đó. Có hai màu chính trong hình ảnh này, được thể hiện bằng hai đỉnh.

Answer 2

K-means là một lựa chọn tốt cho nhiệm vụ này bởi vì bạn biết số màu sắc chính trước đó. Bạn cần tối ưu hóa K-means. Tôi nghĩ rằng bạn có thể giảm kích thước hình ảnh của bạn, chỉ cần quy mô nó xuống 100x100 pixel hoặc hơn. Tìm kích thước trên phù thủy thuật toán của bạn hoạt động với tốc độ chấp nhận được. Một lựa chọn khác là sử dụng giảm kích thước trước khi phân cụm k.

Và cố gắng tìm cách triển khai k-means nhanh. Viết những thứ như vậy trong python là việc lạm dụng python. Nó không phải được sử dụng như thế này.

Answer 3

Với một chút mày mò, this code (mà tôi nghi ngờ bạn có thể đã nhìn thấy!) Có thể được tăng tốc lên đến chỉ dưới một giây

Nếu bạn tăng giá trị kmeans(min_diff=...) đến khoảng 10, nó tạo ra kết quả rất giống nhau , nhưng chạy trong 900ms (so với khoảng 5000-6000ms với min_diff=1)

tiếp tục giảm kích thước của hình thu nhỏ để 100x100 dường như không ảnh hưởng đến kết quả gì nhiều, và phải mất thời gian chạy khoảng 250ms

Đây là một phiên bản hơi tinh chỉnh của cá tuyết e, mà chỉ parameterises giá trị min_diff, và bao gồm một số mã khủng khiếp để tạo ra một tập tin HTML với kết quả/thời gian

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)