Блог

я где-то видел эту проблему с пересечениями линий и пытался ее решить.

Существует сетка размером 64×64 с 8 битными пикселями, на которой есть вертикальные и горизонтальные линии шириной 1 пиксель разных цветов. Все параллельные линии имеют по крайней мере один пробел между ними. Задача состоит в том, чтобы найти количество пересечений линий, которые совершает каждый набор цветных линий (например, все пересечения зеленых линий учитываются в одной сумме). И найдите, какой набор линий имел наименьшее количество пересечений. Кроме того, все вертикальные линии одного цвета имеют одинаковый размер, а все горизонтальные линии одного цвета имеют одинаковый размер.

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

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

Вот два примера. Обратите внимание, что между параллельными линиями всегда есть пробел.

На сетке с вашими линиями найдите 2 типа квадратов 3×3:

 1).a.  2).a.
  bab    bbb
  .a.    .a.
  

«.» представляет фон (всегда черный?), «a» и «b» представляют 2 разных цвета (также отличающихся от цвета фона). Если найдено, увеличьте на 1 количество пересечений линий a-цвета и пересечений линий b-цвета.

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

Основным техническим термином является «свертка» (см. http://en.wikipedia.org/wiki/Convolution ). Я думаю об этом как о своего рода взвешенной скользящей средней, хотя веса могут быть отрицательными. Анимации в Википедии показывают свертку с использованием довольно скучного импульса (он мог бы иметь более интересную форму) и на одномерном сигнале (например, звуковом), а не на 2D (изображении), но это очень общая концепция.

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

Вот некоторые конкретные причины, по которым это происходит быстро…

1. Он очень удобен для кэширования, поэтому эффективно обращается к памяти.
2. Это именно то, для чего предназначены векторные инструкции (MMX, SIMD и т. Д.).
3. В наши дни вы даже можете переложить работу на свою видеокарту.

Еще одним преимуществом является то, что вам нужно написать только одну функцию свертки для фильтрации изображений. Специфичная для приложения часть заключается в том, как вы определяете ядро фильтра, которое представляет собой просто сетку значений веса. На самом деле вам, вероятно, вообще не стоит писать эту функцию самостоятельно — различные библиотеки числового кода могут предоставить высокооптимизированные версии.

Для обработки разных цветов линий я бы просто сначала сгенерировал одно изображение в оттенках серого для каждого цвета, затем отфильтровал и проверил каждое отдельно. Опять же, думайте об этом как об оптимизации — попытка избежать создания отдельных изображений, скорее всего, приведет к увеличению объема работы, а не к уменьшению.

• Если подумать, я, возможно, понял это требование. Возможно, имеет смысл сгенерировать черно-белое изображение из черно-цветного, отфильтровать его и найти все пересечения по нему. Когда у вас будут точки пересечения, вернитесь к исходному черно-цветному изображению, чтобы классифицировать их для подсчета. Фильтрация и поиск пересечений остаются очень эффективными для каждого пикселя. Классификация не так эффективна для каждого пикселя, но выполняется только в нескольких точках.

Вы могли бы выполнить свертку, основанную на следующем ядре фильтра FIR…

 .*.
***
.*.
  

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

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

Ваш единственный ввод — сетка 64×64? Если это так, то вы смотрите на что-то с размером 64×64, поскольку другого способа убедиться, что вы обнаружили все линии, нет. Итак, я предполагаю, что вы говорите об оптимизации на операционном уровне, а не асимптотически. Кажется, я помню, что в старой серии «Graphics Gems» было много подобных примеров, с акцентом на сокращение количества команд. Я сам лучше разбираюсь в асимптотических вопросах, но вот несколько небольших идей:

Ячейки сетки обладают тем свойством, что сетка [i, j] является зеленым пересечением, если

 (grid[i,j] == green)
amp;amp;
(grid[i 1,j]==green || grid[i-1,j]==green)
amp;amp;
(grid[i,j 1]==green || grid[i, j-1]==green)
  

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

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

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

Даже если у вас нет чего-то вроде графического процессора, который позволяет вам И всей сетке, вы можете использовать эту идею, если количество цветов меньше половины вашего размера слова. Например, если у вас 8 цветов и 64-разрядная машина, то вы можете втиснуть 8 пикселей в одно целое число без знака. Итак, теперь вы можете выполнять операцию сравнения внешнего цикла для 8 ячеек сетки одновременно. Это может сэкономить вам столько работы, что стоит сделать два прохода, один для горизонтального внешнего цикла и один для вертикального внешнего цикла.

Простой способ найти прямое пересечение

 def straight_intersection(straight1, straight2):
    p1x = straight1[0][0]
    p1y = straight1[0][1]
    p2x = straight1[1][0]
    p2y = straight1[1][1]
    p3x = straight2[0][0]
    p3y = straight2[0][1]
    p4x = straight2[1][0]
    p4y = straight2[1][1]
    x = p1y * p2x * p3x - p1y * p2x * p4x - p1x * p2y * p4x   p1x * p2y * p3x - p2x * p3x * p4y   p2x * p3y * p4x   p1x * p3x * p4y - p1x * p3y * p4x
    x = x / (p2x * p3y - p2x * p4y - p1x * p3y   p1x * p4y   p4x * p2y - p4x * p1y - p3x * p2y   p3x * p1y)
    y = ((p2y - p1y) * x   p1y * p2x - p1x * p2y) / (p2x - p1x)
    return (x, y)