Есть массив цветов (rgb). Элементов — около миллиона. В массиве ищется наиболее близкий цвет к заданному (критерий близости- это близость точки rgb к точке r1g1b1, т.е. корень из суммы квадратов разниц каждой из трех компонентов цвета). Задача такая — осуществить поиск максимально быстро. Перебирать все элементы массива и для каждого искать близость к заданному цвету — слишком накладно (задача стоит заполнить новый массив еще на несколько миллионов элементов, для каждого делать полный перебор — долго). Как можно осуществить этот поиск? Может какие алгоритмы существуют?
Я когда-то использовал следующий алгоритм (у меня стояла правда задача не получить абсолютно близкое значение, а просто цвет из близкой зоны, но вдруг что почерпнешь и для себя):
1. Создается равномерный трехмерный массив (Р) в заданном пространстве с определенным шагом, к примеру 4. То бишь координаты в RGB у элементов будут 000, 400, 040, 440 и т.д.
2. Проходим по всем элементам исходного массива (А) цветов и заполняем на базе этих данных наш равномерный массив (Р). Если у нас к примеру в исходном массиве (А) есть цвет 511, то запоминаем эти данные для самого близкого элемента в массиве (Р): Р[400]=511 иначе оставляем Р[400]=0
3. Теперь нам достаточно при поиске ближайшего цвета (В) просто обратиться напрямую к ближайшему по сетке элементу массива (Р):
В[301] -> ближайший цвет в сетке 400 -> Р[400]=511 -> ближайший исходный цвет 511…
Миллион элементов из 16 миллионов элементов возможных позиций. Можно попробовать создать карту позиций, т.е. array[rgb] = 1 | 0.
Если каждая позиция описывается одним байтом, то это 16 Мб памяти. Не так уж и много, для современных то машин?
Довольно таки простая адресация, простой запрос, поэтому можно воспользоваться поиском вширь. Если поиск сделать двухуровневым, то скорость будет вполне приемлемой. (сначала поиск по областям 16х16х16, потом поиск по точкам внутри подходящих областей).
Если растояние между цветами в массиве одинаковое — то можно цвета хранить как 3-х мерный массив. И тогда поиск будет бинарным. Если нет — печаль, буду думать дальше…
Понимаю, что прошло уже много лет, но вдруг кому-то пригодиться позже :)
На самом деле ситуация с цветами - она простая, т.к. это дискретное пространство. Грубо говоря, у нас RGB - это координаты точки в трехмерном пространстве. У точки есть окрестности - сферы, неким радиусом. Точки, которые лежат на поверхности этой сферы - равноудалены от исходной точки на расстояние равное радиусу сферы. Задача свести поиск - к прямому поиску, т.е. берем сферу с радиусом 0 - есть точки, отличные от нашей - значит они ближайшие, нет - увеличиваем радиус на 1, есть точки - отлично, нашли, нет увеличиваем радиус дальше и т.п. Возможно, тут можно применять не прямой поиск, а деление пополам в заданном интервале - тут уже творческий момент :) Как все это дело реализовать (это будет хорошо работать как раз для ситуации выше, когда поиск по фиксированному набору надо выполнять очень много раз).
1. Создаем три массива [0..255]. Массивы R, G, B. Элементом массива является множество индексов элементов исходного массива точек. Т.е. пусть точка с цветом 100, 25, 250 имеет индекс в исходом массиве 200. Тогда мы должны сделать R[100].add(200); G[25].add(200); B[250].add(200);
2. Поскольку мы наполняем массивы последовательно, то каждый элемент массивов R,G,B уже будет упорядоченным множеством. Если, по каким-то причинам, это не так - то вторым шагом надо упорядочить каждое множество.
3. Строим три двумерных массива UR[0..255,0..255]. UG. UB. Где UR[i,j] = пересечение множеств R[i] и R[j]. Прелесть в том, что множества у нас уже упорядоченные и их пересечение строится довольно быстро. Можно подробней тут https://habrahabr.ru/post/250191/
На этом наша подготовительная работа закончилась. Она займет определенное время, но дальше поиск будет осуществляться очень быстро.
Итак, собственно сам поиск ближайшей точки до искомой прост. Для i=0 to 255. координаты искомой точки r, g, b. Берем множество значений UR[r-i, r+i] - объединяем в URi, так для каждого массива. Дальше смотрим пересечение множеств URi, UGi, UBi - если пусто, i++, иначе - любой (или множество - зависит от задачи) из найденных элементов - исходный. Конечно, тут надо следить, что бы не выйти за границы массивов и т.п., главное - идея - мы ищем ближайшие точки, как точки лежащие на поверхности сферы с центром в исходной точке, с наименьшим радиусом. А что бы не бегать каждый раз по массиву - мы подготовили три массива - с проекциями точек по каждой оси.
Можно было бы ограничится массивами R, G и B, но тогда при каждом поиске надо было бы находить пересечение - это, возможно, выгодней, для небольшого кол-ва итераций поиска. Для большого выгодней построить множества пересечений и искать по ним.
My<cod/>.net
