[OneShot]

Медод k-means, он же метод k-средних, используется для распределения объектов на кластеры. В этой статье описывается сам алгоритм и то, как его можно применить для нахождения доминирующих цветов (цветов, которые встречаются чаще всего) на картинке.

Те, кому не интересна суть метода, могут пролистать до части с кодом.

Кластер в нужном нам смысле — это группа объектов с близкими по значению свойствами. У объектов может быть одно свойство, а может быть и несколько. Кстати, эти свойства — числа. Задача состоит в том, чтобы разбить имеющиеся объекты на определённое количество кластеров так, чтобы сумма отклонений от центра кластеров была минимальна. В итоге получится нужное количество "кучек" объектов.

Для простоты рассмотрим пример с множество объектов с 2-мя свойствами. Эть свойства будем представлять как координаты x и y на плоскости. Пусть у нас будет заранее заданное множество точек.

Далее из текущего числа объектов случайно определим как центроиды (обозначены звёздами) столько точек, сколько надо выделить кластеров.

Теперь начинается цикл. Сначала для каждого объекта определяем ближайший к нему центроид, тем самым распределяем объекты по группам.

Далее для каждой группы объектов определяем центр масс и переносим туда центроид этой группы.

Цикл повторяется до тех пор, пока суммарный сдвиг центроидов в одном цикле не окажется меньше заранее заданной величины. В итоге текущие центроды и окажутся кластерами.


Применение метода для определение доминирующих цветов

Здесь всё очень просто :). В качестве объектов используются цвета пикселей, а свойства — значение красного, синего и зелёного канала цвета.

А вот и сам код:

Код:

// Функция, которая определяет "расстояние" между объектами
function getDistance($arr1, $arr2, $l) {
	// Определяется "расстояние машины такси" — так быстрее, но для более точного результата желательно использовать евклидому метрику
	$s = 0;
	for($i = 0; $i < $l; ++$i)
		$s += $arr1[$i] > $arr2[$i] ? ($arr1[$i] - $arr2[$i]) : ($arr2[$i] - $arr1[$i]);
	return $s;
}

/*
Сама функция, которая определяет доминирующие цвета
Значения, передаваемые функции:
	$url — путь к картинке на сервере
	$amount — количество цветов, которые надо определить
	$sort — сортировать ли цвета по убыванию встречаемости на картинке
	$maxPreSize — максимальный размер уменьшаемой картинки (подробнее чуть дальше)
	$epselon — минимальное суммарное отклонение, необходимое для выхода из цикла
*/
function getDominantColors($url, $amount = 1, $sort = true, $maxPreSize = 50, $epselon = 1) {
	// Определяем, существует ли указанный файл. Если нет, то выдаём ошибку.
	if(!file_exists($url))
		return false;
	// Определяем размер картинки, если это картинка.
	$size = getimagesize($url);
	if($size === false)
		return false;
	$width = $size[0];
	$height = $size[1];
	// Определяем формат изображения из заголовка файла и проверяем, есть ли функция, которая может это изображение открыть. Если нет, значит файл — не картинка, и выдаём ошибку.
	$format = strtolower(substr($size['mime'], strpos($size['mime'], '/') + 1));
	if($format == 'x-ms-bmp')
		$format = 'wbmp';
	$func = 'imagecreatefrom'.$format;
	if(!function_exists($func))
		return false;
	$bitmap = @$func($url);
	if(!$bitmap)
		return false;

	// Здесь мы уменьшаем исходную картинку, чтобы иметь дело не со всеми пикселями, а только с некоторыми. Это значительно увеличивает скорость алгоритма. Чем меньше размер — тем меньше точность.
	$newW = $width > $maxPreSize ? $maxPreSize : $width;
	$newH = $height > $maxPreSize ? $maxPreSize : $height;
	$bitmapNew = imagecreatetruecolor($newW, $newH);
	// Для большей точности надо использовать функцию imageCopyResambled, но она тратит очень много времени, поэтому используется быстрая и грубая функция imageCopyResized.
	imageCopyResized($bitmapNew, $bitmap, 0, 0, 0, 0, $newW, $newH, $width, $height);
	// Заносим цвета  всех пикселей в один массив
	$pixelsAmount = $newW * $newH;
	$pixels = Array();
	for($i = 0; $i < $newW; ++$i)
		for($j = 0; $j < $newH; ++$j) {
			$rgb = imagecolorat($bitmapNew, $i, $j);
			$pixels[] = Array(
				($rgb >> 16) & 0xFF,
				($rgb >> 8) & 0xFF,
				$rgb & 0xFF
			);
		}
	imagedestroy($bitmapNew);
	
	// Выбираем случайные пиксели для установки центроидов в них
	$clusters = Array();
	$pixelsChosen = Array();
	for($i = 0; $i < $amount; ++$i) {
		// Желательно не ставить несколько центроидов в одну точку
		do {
			$id = rand(0, $pixelsAmount - 1);
		} while(in_array($id, $pixelsChosen));
		$pixelsChosen[] = $id;
		$clusters[] = $pixels[$id];
	}
	
	$clustersPixels = Array();
	$clustersAmounts = Array();
	// Начинаем цикл
	do {
		// Обнуляем хранилище пикселей, принадлежащих текущему центроиду и их счётчик
		for($i = 0; $i < $amount; ++$i) {
			$clustersPixels[$i] = Array();
			$clustersAmounts[$i] = 0;
		}
		
		// Проходимся по всем пикселям и определяем ближайший к ним центроид	
		for($i = 0; $i < $pixelsAmount; ++$i) {
			$distMin = -1;
			$id = 0;
			for($j = 0; $j < $amount; ++$j) {
				$dist = getDistance($pixels[$i], $clusters[$j], 3);
				if($distMin == -1 or $dist < $distMin) {
					$distMin = $dist;
					$id = $j;
				}
			}
			$clustersPixels[$id][] = $i;
			++$clustersAmounts[$id];
		}
		
		// Перемещаем центроид в центр масс пикселей, принадлежащих ему, заодно вычисляем, насколько он сместился
		$diff = 0;
		for($i = 0; $i < $amount; ++$i) {
			if($clustersAmounts[$i] > 0) {
				$old = $clusters[$i];
				for($k = 0; $k < 3; ++$k) {
					$clusters[$i][$k] = 0;
					for($j = 0; $j < $clustersAmounts[$i]; ++$j)
						$clusters[$i][$k] += $pixels[$clustersPixels[$i][$j]][$k];
					$clusters[$i][$k] /= $clustersAmounts[$i];
				}
				// Будем сравнивать максимальное отклонение
				$dist = getDistance($old, $clusters[$i], 3);
				$diff = $diff > $dist ? $diff : $dist;
			}
		}
	} while($diff >= $epselon);
	
	// Сортировка получившихся кластеров (не помню как метод называется)
	if($sort and $amount > 1)
		for($i = 1; $i < $amount; ++$i)
			for($j = $i; $j >= 1 and $clustersAmounts[$j] > $clustersAmounts[$j - 1]; --$j) {
				$t = $clustersAmounts[$j - 1];
				$clustersAmounts[$j - 1] = $clustersAmounts[$j];
				$clustersAmounts[$j] = $t;
				
				$t = $clusters[$j - 1];
				$clusters[$j - 1] = $clusters[$j];
				$clusters[$j] = $t;
			}
	
	// Значение цвета — величина целая, поэтому её надо округлить
	for($i = 0; $i < $amount; ++$i)
		for($j = 0; $j < 3; ++$j)
			$clusters[$i][$j] = floor($clusters[$i][$j]);
	
	// Очищаем память
	imagedestroy($bitmap);
	
	// Возвращаем массив, который содержит доминирующие цвета. Каждый цвет — массив, состоящий из 3-х элементов — красный, зелёный и синий канал цвета.
	return $clusters;
}

$colors = getDominantColors('my_picture.jpg', 3);
if($colors === false)
	else 'Ошибка';
else
	foreach($colors as $color)
		echo '<div style="width: 50px; height: 40px; background-color: rgba($color[0], $color[1], $color[2], 1);"></div>';

[zatvorius]

эммм это помойму не хабра зачем это на форуме вебмастеров?
_http://zhyk.ru/forum/archive/index.php?t-580704.html отсюда взяли? Или с другого источника?