При анализе изображения можно узнать значение тона (Hue) для каждого пикселя, кроме тех, где R=G=B.
Можно понятным образом вычислить «средний тон», для этого достаточно использовать mean of circular quantities, полученный угол покажет тон а радиус — его выраженность.
Вопрос такой: какой алгоритм поможет из списка тонов, скажем [15, 14, 13, 95, 72] вычислить что «основные тона» это [14, 95, 72] или [14, 83]?
При этом в реальном списке могут быть миллионы точек — O(n²)-алгоритмы не подойдут.
Можно строить гистограмму распределения Hue и искать на ней локальные максимумы. Требуется один проход по изображению (O(n)) и обработка гистограммы, сложность которой не зависит от размера картинки (O(1)).
Я наверное очень туплю, но как представлять в программе гистаграмму и как искать локальные максимумы? Для этого ведь как минимум нужна дискретизация шкалы тонов?
Значение тона и так дискретно. Для 8-битного Hue гистограмма будет содержать 256 отсчетов, для 16-битного — 65536 и т.д.
Насчет локальных максимумов: первое, что приходит в голову — пробежать по всей гистограмме скользящим окном (не забываем, что шкала Hue замкнута в кольцо!) и для каждого наложения окна проверить, не является ли значение по центру окна максимальным среди всех отсчетов, попадающих в окно. Среди всех найденных максимумов отобрать K самых больших.
Чем шире окно, тем сильнее будут «склеиваться» соседние пики.
Средний
Средний
