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

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

введите описание изображения здесь

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

Всего 3 ответа


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

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

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


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

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

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


ИСПОЛЬЗУЙТЕ ГПУ

С 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 2 меньше пикселей для сжатия.

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

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

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

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

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


Есть идеи?

10000