Кластеризация по различным функциям расстояния в пространстве Lab
Проблема: кластеризовать похожие цветные пиксели в CIE LAB, используя K.
Я хочу использовать CIE 94 для расстояния между 2 пикселями Формула CIE94
То, что я прочитал, было работой K means в "евклидовом пространстве", где позиционные кординаты минимизируются функцией стоимости, которая является (суммой квадратов разности). Причина, по которой не используется kmeans в пространстве, отличном от "евклидова", это алгоритм """, часто представляемый как объект назначения до ближайшего кластера по расстоянию. Стандартный алгоритм направлен на минимизацию цели суммы квадратов внутри кластера (WCSS) и, таким образом, присваивает "наименьшую сумму квадратов", что в точности эквивалентно назначению наименьшим евклидовым расстоянием. другая функция расстояния, отличная от (квадрат) евклидова расстояния, может помешать алгоритму сходиться ""(исходная вики)
Так как же использовать расстояние CIE 94 в LAB SPACE для аналогичной цветовой кластеризации?
Так как же подойти к проблеме? Какой должна быть здесь функция минимизации? КАК сопоставить евклидово пространство с лабораторным, если для работы k означает евклидову формулу? Любой другой подход здесь?
2 ответа
Причина, по которой CIE LAB часто используется для кластеризации, заключается в том, что он уменьшает цвет до 2 измерений (в отличие от RGB с 3 цветными каналами). Вы можете легко думать о цвете для каждого пикселя в декартовой системе координат вместо точек (x,y) у тебя есть очки (a,b) Отсюда вы просто выполняете 2-е kmeans.
Как именно вы реализуете kmeans, зависит от вас. Хорошая вещь о сокращении цветов до двухмерного пространства состоит в том, что мы можем представить данные в сетке, и теперь мы можем использовать любую обычную меру расстояния, которую мы хотим. Mahalonobis, евклидов, 1 норма, городской квартал и т. Д. Возможности здесь действительно безграничны.
Вам не нужно использовать CIELAB, вы также можете легко использовать YCbCr, YUV или любое другое цветовое пространство, которое представляет цвет в двух измерениях. Если вы хотите попробовать 3d kmeans, вы можете использовать rgb, hsv и т. Д. Одной из проблем с более высокой размерностью является разреженность кластеров (большая дисперсия) и, самое главное, увеличение времени вычислений.
Просто для забавы я включил два изображения, сгруппированных с использованием kmeans, одно в LAB и одно в YCbCr, вы можете видеть, что кластеризация почти идентична (за исключением того, что метки разные), просто доказывая, что точное цветовое пространство не имеет значения, основной Дело в том, чтобы сопоставить размерность ваших Kmeans с вашими данными
РЕДАКТИРОВАТЬ
Вы сделали несколько хороших замечаний в своих комментариях. Я просто демонстрировал, что, абстрагируя проблему, вы можете представить множество вариантов одного и того же базового алгоритма кластеризации. Но вы правы, есть преимущества использования CIELAB
Вернуться к измерению расстояния. У Kmeans есть два шага: назначение и обновление (это очень похоже на алгоритм максимизации ожидания). Это расстояние используется в шаге назначения k-средних. Вот некоторый код псевдо
for each pixel 1 to rows*cols
for each cluster 1 to k
dist[k] = calculate_distance(pixel, mu[k])
pixel_id = index k of minimum dist
вы бы создали функцию calculate_distance который использует delta_e расчет от cielab94. Эта формула использует все 3 канала для расчета расстояния. Надеюсь, это ответит на ваши вопросы
ПРИМЕЧАНИЕ. В моих примерах используются только 2 цветовых канала, игнорируя канал яркости. Я использовал эту технику, поскольку часто целью является группировка цветов, несмотря на неравномерность освещения (например, тени). delta_E мера не является инвариантом освещения. Это может или не может быть проблемой для вашего приложения, но об этом нужно помнить.
результаты с использованием квадратного евклидова расстояния
результаты с использованием расстояния города
Существуют вариации k-средних для других функций расстояния.
В частности, k-medoids (PAM) работает с произвольными функциями расстояния.