Пользователь
57,4
рейтинг
25 октября 2012 в 03:06

Разработка → Определение доминирующих цветов: Python и метод k-средних


Assorium

На Хабре публиковалось несколько статей с алгоритмами и скриптами для выбора доминирующих цветов на изображении: 1, 2, 3. В комментариях к тем статьям можно найти ссылки ещё на десяток подобных программ и сервисов. Но нет предела совершенству — и почему бы не рассмотреть способ, который кажется самым оптимальным? Речь идёт об использовании кластеризации методом k-средних (k-means).

Как и многие до него, американский веб-разработчик Чарльз Лейфер (Charles Leifer) использовал метод k-средних для кластеризации цветов на изображении. Идея метода при кластеризации любых данных заключается в том, чтобы минимизировать суммарное квадратичное отклонение точек кластеров от центров этих кластеров. На первом этапе выбираются случайным образом начальные точки (центры масс) и вычисляется принадлежность каждого элемента к тому или иному центру. Затем на каждой итерации выполнения алгоритма происходит перевычисление центров масс — до тех пор, пока алгоритм не сходится.

В результате получается примерно такая картина. Точки раскрашены, в зависимости от цвета кластера, чёрные точки отображают центры масс.



В применении к изображениям каждый пиксель позиционируется в трёхмерном пространстве RGB, где вычисляется расстояние до центров масс. Для оптимизации картинки уменьшаются до 200х200 с помощью библиотеки PIL. Она же используется для извлечения значений RGB.

Код

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):
    img = Image.open(filename)
    img.thumbnail((200, 200))
    w, h = img.size

    points = get_points(img)
    clusters = kmeans(points, n, 1)
    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

Примеры













Определение доминирующих цветов — довольно полезная вещь, которой всегда найдётся применение. Это выбор палитры для веб-сайта или некоторых элементов UI. Например, браузер Chrome использует метод k-средних для выбора доминирующего цвета с фавикона.

Анатолий Ализар @alizar
карма
751,5
рейтинг 57,4
Пользователь
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (17)

  • +3
    Очень напоминает практическое задание из курса Andrew Ng :)
    • +1
      А можно подробнее, что это за курсы? Именно по питону? Где найти/почитать?
      Спасибо!

      И вообще, вопрос для знатоков: подскажите пожалуйста интересные упражнения/задания/курсы/уроки. Python, C++, Perl, Java.
      • +2
        Machine Learning, Andrew Ng, Associate Professor
        Когда я проходил, использовался Octave (MatLab).
        • 0
          Это новый формат курсов, курс AndrewNG один из многих, полный список можно посмотреть тут coursera.org
  • +8
    Akira!
  • 0
    Средние цвета не очень, не сохраняют восприятие исходной картинки. Например в предпоследнем варианте нет синего, его мало, но без него плохо. Использование доминирующих цветов тоже считаю неполноценным. Удачные палитры получаются только на контрастных изображениях или когда цель именно в получении пастельных оттенков. Вот возьмем кусок градиента, получим средние цвета, которые неприменимы для повторения эффекта.

    Не знаете ли готовых решений составления палитр по изображению, так чтобы прямоугольники цветов были пропорциональны частоте использования цвета и упорядочены в соответствии с сочетаниями их в картинке?
  • +1
    Как ни странно, применение моему скрипту нашлось. =)
    И это не дизайнеры, а ребята наполнявшие свои сайты товаром, который можно фильтровать по цвету: косметика, плитка итд.
  • +1
    Мне кажется k-means не очень подходящий алгоритм кластеризации для данной задачи. Основная проблема при использовании k-means заключается в том, что нужно заранее определять сколько кластеров будет на выходе. Таким образом, если, например, картинка будет состоять из 7 полосок разного цвета, а мы задали кол-во кластеров равное 3 (как у вас), то на выходе мы получим цвета не соответствующие цветам этих полосок.
    • 0
      Например можно задать пороговое значение евклидового расстояния между точками (значение в пределах 1-360, RGB система), по которому определяется соответствие цвета той или иной группе (входит точка в шар радиусом равным этому расстоянию или нет, если нет — новая группа), но тогда заранее не будет известно сколько цветовых групп получится :)
      • 0
        Вот как раз поэтому в данном случае и нужно использовать другие алгоритмы кластеризации, в которых кол-во кластеров определяется в процессе работы алгоритма.
        • 0
          Тогда мой вариант подходит, там количество кластеров определяется в процессе работы алгоритма.
    • 0
      Можно, например запускать k-means с разными значениями числа кластеров, и выбирать наиболее подходящий результат. Остаётся, правда, вопрос, что такое наиболее подходящий результат. Для этого придётся понять, зачем делается кластеризация.
  • 0
    позавчера искал алгоритмы!
    спасибо :)
  • 0
    Интересно, как меняется результат при использовании других расстояний между двумя цветами. К сожалению, в этом случае придётся ещё думать, как правильно искать центр кластера.
  • 0
    У себя на сайте использую только средний цвет всей картинки, в том числе поиск. Если сделать 3 средних цвета то искать подобные картинки будет гораздо точнее.
    Сам сайт тоже на Python+PIL но так как больше 200 000 надо бы такой алгоритм на С переписать.

    А если ещё добавить кривезну контрастных участков то можно очень неплохо искать похожие картинки…
  • 0
    А вот если взять какой-нибудь алгоритм который понижает цветность картинки с уётом какого-нибудь качественного дизеринга, а потом взять результирующую палитру? Я конечно понимаю, что останется проблема подбора количества цветов, но резулььтат должен получиться удовлетворительный?
  • +1
    Хоть статья чисто для ознакомления с темой и на любителя, но все равно внесу свои две копейки.
    Во-первых, зачем писать на питоне чистые вычисления?
    Во-вторых, есть 2 реализации шага по методу к-средних: со сложностью N^2 и почти линейной (вычисляется центр масс на каждом шагу и находится ближайшая к нему точка).
    В-третьих, для оптимизации не нужно вычислять корень из расстояния, он не нужен и является очень долгой по времени операцией.
    Ну и в-четвертых, одного метода к-средних для данной задачи недостаточно. Есть целое семейство алгоритмов оптимального разбиения на классы, например, метод Максимина.
    Также для оптимизации, при распределении точек по классам на каждом шагу удобно создавать массив с индексами точек для каждого класса для дальнейшего анализа по к-средних (меморизация).
    Учитывая все вышеупомянутое, моя реализация (без распараллеливания) разбивает на классы миллион точек по максимину за 1-2 секунды, далее по к-средних в среднем по секунде на шаг на мобильном двухъядерном атлоне.
    Сам по себе комплекс теории называется «методы и алгоритмы принятия решений».

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.