Рассчитать минимальное расстояние между двумя «пиксельными каплями» на холсте

Question

Я хочу рассчитать расстояние между двумя наборами пикселей - для иллюстрации, синим и красным множеством пикселей. Я хочу вычислить ближайшее расстояние в направлении x, направлении y и произвольном направлении (см. Три стрелки на изображении). В общем, пиксели одного цвета могут быть не связанными пятнами (например, красным в этом примере), но большую часть времени они будут связаны, хотя у них могут быть отверстия (например, синий в этом примере).

Существуют ли какие-либо библиотеки или алгоритмы, которые уже решают эту проблему разумным способом? Не очень сложно найти решение - расстояние x и y - это проблема O (n), но для произвольного расстояния наивный алгоритм грубой силы равен O (n²). У меня есть догадка, что есть лучшие подходы.

Answer 1

Вы можете вычислить карту полного расстояния вокруг сгустка произвольной формы (включая отключенный) за линейное время O (n), будь то Манхэттен или Евклид (где n обозначает размер изображения).

Когда вы иметь эту карту, для сканирования другого объекта (шариков), чтобы найти минимум, также потребуется не более O (n).

См. эту замечательную статью: http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf

Answer 2

Если ваши наборы не имеют специальной формы (например, отрезки), вы вряд ли найдете лучшее решение, чем O (n²).

Но вы можете добавить шаг предварительной обработки, чтобы уменьшить n . Удалите все внутренние точки наборов. Это (в зависимости от комплектов) может значительно уменьшить n . В вашем примере, по моим оценкам, размер n уменьшится вдвое.

Если ваш пример является типичным примером для ваших наборов, вы можете преобразовать наборы в набор отрезков и затем вычислить расстояния между ними.

Answer 3

ИСПОЛЬЗОВАНИЕ GPU

С помощью Canvas 2D API вы имеете ограниченный доступ к графическому процессору, который вы можете использовать в своих интересах.

Если два цвета - это отдельные каналы (как у вас красный и синий) и других цветов не существует, вы можете использовать графический процессор для уменьшения изображения, чтобы уменьшить начальный поиск.

Создать рабочий холст

const can = document.createElement("canvas");
var w = can.width = ctx.canvas.width;
var h = can.height = ctx.canvas.height;
const ctxW = can.getContext("2d");

Установить режим сглаживания и наложения copy

ctxW.imageSmoothingEnabled = true;
ctxW.globalCompositeOperation = "copy";

Уменьшить исходный холст на полшага

// first step move original to working canvas
w /= 2;
h /= 2;
ctxW.drawImage(ctx.canvas, 0, 0, w, h);

// Reduce again drawing onto its self
ctxW.drawImage(ctxW.canvas, 0, 0, w, h, 0, 0, w / 2, h / 2);
w /= 2;
h /= 2;
ctxW.drawImage(ctxW.canvas, 0, 0, w, h, 0, 0, w / 2, h / 2);

const imgData = ctxW.getImageData(0, 0, w / 2, h / 2); // 1/64th as many pixels 

На этом этапе уменьшенный холст имеет размер 1/8, еще лучше имеет 8 ² меньше пикселей для сжатия.

Масштабирование выполняется графическим процессором.

Затем вы можете искать эти пиксели с помощью метода грубой силы, создавая список кандидатов. Обратите внимание, что если красный и синий цвета ближе, чем 8 пикселей, они теперь будут занимать один и тот же пиксель в некоторых случаях.

Затем вернитесь к исходному холсту и уточните близость кандидатов, найденных в данных уменьшенного пикселя.

На самом деле не улучшение O (n ² ), а значительное увеличение производительности при использовании мощности параллельной обработки, которую обеспечивает графический процессор.

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