Как найти 4 точки рядом с пересечением двух линий

Question

Допустим, у меня есть некоторые растровые данные (черным цветом), по которым некоторые линии были нарисованы от руки в векторном формате (зеленым цветом).Линии примерно соответствуют форме растровых данных.В некоторых местах линии пересекаются.

Итак, что я пытаюсь сделать, зная положение пересечения зеленых линий, как я могу найти положение A, B, C и D?

См. Ниже некоторые примеры:

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

Answer 1

Самый простой подход, который я могу придумать, таков:

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

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

3. Снова отфильтруйте изображение, используя алгоритм обнаружения углов, такой как Детектор Харриса . Это даст вам четыре угла.

Примечания:

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

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

Answer 2

Полагаю, вы знаете, как получить координаты (x,y) (зеленого) пересечения векторной линии, поэтому я пропущу эту часть.

Начиная с пикселя, ближайшего к (x,y), постепенно переходите наружу по квадратной спирали (или по другому желаемому шаблону поиска) от пикселя к пикселю. На каждом шаге проверяйте, находитесь ли вы на черном пикселе с одним и только одним белым соседом Мура . Если это так, то место, где черный пиксель и его белый сосед касаются (возможно, общего угла), является одной из ваших точек (назовите это A). Продолжайте маршировать, пока не найдете еще три (B, C, D). Это будут четыре такие точки, расположенные ближе всего к зеленому пересечению - которые будут хорошо работать в четырех примерах, которые вы показываете в своем вопросе.

Однако этот алгоритм не будет работать, если зеленое пересечение является чем-то наполовину между двумя черными пересечениями; в этом случае он будет смешивать точки из обоих черных пересечений. Если вас это беспокоит, то, как только вы найдете точку А, заново запустите свою марширующую спираль, на этот раз с центром А, и продолжайте марш, пока не найдете B, C, D. Это будет действовать » привязка "к ближайшему черному перекрестку.

Вы можете добавить больше сообразительности, чтобы избежать поиска в одной и той же области дважды; перезапустите или переориентируйте ваш шаблон поиска, как только вы нашли B, и еще раз, когда вы нашли C, и т. д. ... Зависит от того, насколько вы хотите / нуждаетесь.

Answer 3

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

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

Answer 4

Самый простой способ - скелетонизация. Сначала разделите зеленое и черно-белое изображение. Запустите алгоритм скелета (довольно простая морфологическая операция, также в OpenCV) на обоих изображениях и определите точки пересечения (это можно сделать с помощью простого подсчета пикселей с 8 соседями в скелетных изображениях: то есть для каждого черного пикселя подсчитайте, сколько пиксели связаны по горизонтали, вертикали или диагонали, и если это значение> = 4, это пересечение). Теперь выполните сопоставление ближайшего соседа для этих скелетонизированных точек, и все готово.

Answer 5

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

1) преобразовать изображение в углы (см. Главу 4 приведенной выше ссылки). Затем вы можете использовать линейную интерполяцию угловых точек (глава 5.5) - вы бы изменили наш алгоритм, чтобы увидеть большие изменения наклона (~ 90 градусов) в больших отрезках линий.

2) вам не нужна зеленая линия. Вы можете использовать алгоритм скелетонизации, чтобы найти скелет черной части (см. Главу 5.4), и интерполировать этот скелет линиями (см. Главу 5.5 ссылки выше).

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

Answer 6

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

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

Это ответило на ваш вопрос? Или я что-то не так понял?

Если вам нужны только 4 угла, вам не нужна зеленая линия: просто возьмите границы из выделения ребер, затем сгладьте их с помощью фильтра Савицкого-Голея и вычислите точечную кривизну. Просто извлеките точки с максимальной кривизной.

Answer 7

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

Кстати, это как-то связано с дорогами?

Итак, пошли зеленые линии. После этого возьмите маленький квадрат, как любой из 4 пунктов выше, пока не пройдете все из них и поищите те, которые имеют максимальное черно-белое соотношение пикселей. Это должны быть "перекрестки". Сопоставляя эти черные пиксели, которые граничат с белыми пикселями, вы должны иметь границы дороги / поля. После этого определить эти точки должно быть очень легко.

Как я уже сказал, дикая догадка. Интересная проблема - интересно, что придумают знающие парни.