ИСПОЛЬЗОВАНИЕ 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 2 меньше пикселей для сжатия.
Масштабирование выполняется графическим процессором.
Затем вы можете искать эти пиксели с помощью метода грубой силы, создавая список кандидатов. Обратите внимание, что если красный и синий цвета ближе, чем 8 пикселей, они теперь будут занимать один и тот же пиксель в некоторых случаях.
Затем вернитесь к исходному холсту и уточните близость кандидатов, найденных в данных уменьшенного пикселя.
На самом деле не улучшение O (n 2 ), а значительное увеличение производительности при использовании мощности параллельной обработки, которую обеспечивает графический процессор.
Также обратите внимание, что при уменьшая каждый шаг, у вас есть достаточно места на рабочем холсте, чтобы сохранить каждое сокращение, что означает, что вы можете работать с этими сокращениями по мере уточнения областей кандидатов, экономя еще больше времени.