5.26. Поиск линий и сегментов

Некоторые элементы сцены – это не связные области цвета, а ориентированные прямые границы: нарисованная линия на полу, шов между двумя поверхностями, сторона печатного прямоугольника, край дверного проёма. Просить детектор блобов найти их – неправильная постановка задачи: граница шириной в один пиксель, а алгоритм блобов хочет область-с-цветом, и ответ возвращается пустым или шумным.

Правильный детектор для ориентированных границ – это линейное преобразование Хафа. Модуль image предоставляет его в двух разновидностях: find_lines() возвращает бесконечные линии (каждая линия простирается через всё изображение); find_line_segments() возвращает конечные сегменты (у каждой линии есть концевые точки внутри кадра). Какой из них нужен приложению, зависит от того, непрерывны ли интересующие границы по всему кадру или охватывают лишь его часть.

5.26.1. Как работает преобразование Хафа

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

Линия параметризуется в пространстве Хафа двумя числами: theta – угол линии (0 – 179 градусов) и rho – перпендикулярное расстояние от начала координат изображения до линии (со знаком, в пикселях). Каждая линия, содержащаяся в изображении, – это одна точка в пространстве (theta, rho). Каждый пиксель границы на входе вносит один голос в каждую комбинацию (theta, rho), согласующуюся с его позицией, – концептуально это кривая через пространство Хафа. Там, где пересекается много таких кривых, много пикселей границы согласуются на одной и той же линии, и это пересечение является обнаружением.

Детектор возвращает локальные максимумы в пространстве Хафа, чьи суммы голосов превышают порог. Каждая возвращаемая Line несёт оба представления: x1, y1, x2, y2 для формы концевых точек (обрезанной по границам изображения для бесконечного случая), theta, rho для формы Хафа, а также length и magnitude для размера и числа голосов соответственно.

5.26.2. Бесконечные линии

find_lines() выполняет преобразование Хафа и возвращает самые сильные линии, каждая из которых протянута через всё изображение:

lines = img.find_lines(threshold=1500, theta_margin=25, rho_margin=25)

for l in lines:
    img.draw_line(l, color=(255, 0, 0))

threshold – это минимальная сумма голосов, чтобы линия была принята. Сумма голосов складывает величины границ Собеля каждого вносящего вклад пикселя, поэтому большие значения threshold требуют более длинных или более сильных границ для прохождения – что делает правильное значение зависящим от разрешения изображения (более длинная линия при более высоком разрешении накапливает больше голосов), а также от сцены, так что его приходится настраивать под конкретное приложение. В качестве грубых отправных точек для настройки: 1000 для умеренной линии на чистом изображении, 500 или ниже для слабого контраста или коротких линий, 2000 или больше для загромождённых сцен, где ложноположительные линии формируются через кластеры шума границ.

theta_margin и rho_margin управляют слиянием близких максимумов. Одна физическая граница порождает небольшой кластер бинов с высоким числом голосов вокруг её истинных (theta, rho), и детектор схлопывает каждый кластер до его пика перед возвратом. theta_margin=25 (градусов) сливает любые пики в пределах 25 градусов ориентации; rho_margin=25 (пикселей) сливает пики в пределах 25 пикселей расстояния. Значения по умолчанию разумны; их повышение возвращает меньше, более различимых линий, а их понижение возвращает больше, иногда дублирующихся линий.

x_stride и y_stride шагают по пикселям границ во время голосования так же, как они шагают по пикселям в find_blobs(). Значения по умолчанию 2 и 1 подходят для типичного случая; их повышение ускоряет поиск ценой разрешения. roi ограничивает поиск областью кадра, что одновременно сужает возвращаемые линии и уменьшает объём работы.

Каждая возвращаемая линия отрисовывается напрямую: объект Line передаётся прямо в draw_line(), который считывает поля концевых точек (x1, y1, x2, y2) с его начала. l.theta – это угол в градусах, который классифицирует линию как горизонтальную, вертикальную или диагональную одним сравнением. l.magnitude – это сумма голосов, которая сортирует возвращаемые линии от самой сильной к самой слабой.

5.26.3. Сегменты линий

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

segments = img.find_line_segments(merge_distance=5, max_theta_difference=10)

for s in segments:
    img.draw_line(s, color=(0, 255, 0))

Детектор сегментов прослеживает ориентированные пиксели границ напрямую, вместо голосования в пространстве Хафа, и результатом является набор коротких прямых отрезков. merge_distance задаёт максимальный зазор в пикселях, который два коллинеарных коротких отрезка могут охватить и всё ещё слиться в один возвращаемый сегмент; max_theta_difference задаёт, сколько градусов ориентации механизм слияния допускает между соседними отрезками. Щедрое слияние (merge_distance=10, max_theta_difference=15) возвращает небольшое число длинных сегментов ценой иногда соединения действительно отдельных границ; строгое слияние (merge_distance=0, max_theta_difference=5) возвращает много коротких сегментов и позволяет приложению разобраться с ними в Python.

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

5.26.4. Когда какой использовать

Выбор между двумя методами сводится к единственному вопросу: важно ли приложению, где линия заканчивается?

find_lines() – правильный инструмент, когда ответ – нет. Роботу, следующему по линии, нужно знать, в каком направлении идёт линия и где она пересекает нижнюю часть кадра; сама линия уходит к горизонту и за него. Детектору горизонта нужна самая сильная ориентированная граница на изображении; ему не нужно знать, где горизонт заканчивается.

find_line_segments() – правильный инструмент, когда ответ – да. Определение четырёх сторон печатного прямоугольника требует четырёх сегментов с известными концевыми точками. Отслеживание пальца, указывающего на дисплей, означает следование за коротким сегментом, чьи концевые точки – кончик и основание пальца. Измерение длины видимой царапины требует фактической протяжённости сегмента в пикселях.

Оба детектора разделяют общее ограничение: им нужен контраст. Фильтр границ Собеля, на котором они построены, реагирует на градиенты яркости; цветная граница на одинаково ярком фоне (красная линия на зелёной стене той же светлоты) не даёт ни градиента, ни обнаружения. Когда такой случай возникает на практике, решением является извлечение одного канала LAB как изображения в оттенках серого с нужным контрастом перед поиском – to_grayscale() с выбранным каналом b выделяет красное на зелёном там, где один лишь канал светлоты плоский, – и передача этого изображения канала детектору линий.