Сенсорные системы, 2020, T. 34, № 4, стр. 340-353

ВВЕДЕНИЕ

Задача поиска протяженных границ на изображении возникает во многих прикладных системах компьютерного зрения. Например, протяженной границей можно задать положение линии дорожной разметки на изображении дороги (Ding et al., 2017) (рис. 1, в), отдельной полосы автодороги из дорожной сети на данных дистанционного зондирования Земли (ДЗЗ) (Kunina et al., 2019) (а) или дислокации в кристалле (б).

Часто задачу поиска границ решают с помощью алгоритмов поиска краев, таких как детектор краев Кэнни (Canny, 1986) или других менее распространенных детекторов, например, приведенных в работах (Mousavi et al., 2019, Fan et al., 2019). Такой подход отражен в работах (Li et al., 2016; Ma et al., 2012). Если же граница является линией на изображении, то для поиска таких границ используют алгоритмы выделения хребтов (Lopez et al., 2005; Тропин и др., 2019).

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

Подходы, в основе которых лежат алгоритмы активных контуров (Wang et al., 2004; Anil et al., 2010), учитывают возможную кривизну границы, но качество таких подходов зависит от выбора контрольных точек (не всегда автоматического) и наличия априорной информации.

Еще один подход к решению таких задач – использование методов обучения машин (Kirthika et al., 2011; Xiao et al., 2016). Однако качество работы таких методов зависит от вариативности и размера обучающей выборки, что не подходит в условиях малого количества входных данных.

В данной работе предлагается алгоритм поиска протяженных границ на изображении, ограниченных по протяженности и углу излома. Алгоритм принимает на вход изображение с выделенными границами и выдает множество ломаных, удовлетворяющих заданным ограничениям. В основе алгоритма – предположение, что отдельный участок границы можно приблизить прямолинейным сегментом. Для поиска таких сегментов используется преобразование Хафа (ПХ) (Hough, 1962), другое название которого – дискретное преобразование Радона (Radon, 1917).

Преобразование Хафа представляет собой процедуру голосования в пространстве параметров, определяющих прямую, оценивая таким образом количество точек, лежащих на каждой прямой на изображении. На настоящий момент существует множество модификаций классического ПХ (Hough, 1962), обзор которых можно найти в работе (Mukhopadhyay et al., 2015).

В нашей работе использована одна из модификаций ПХ – быстрое преобразование Хафа (БПХ) в постановке Брейди (Brady et al., 1992). Несмотря на широкую известность классического ПХ, БПХ используется при решении множества разнообразных задач, таких как поиск точек схода (Sheshkus et al., 2020) и определение наклона шрифта (Limonova et al., 2017) в системах распознавания документов; создание панорамы из отдельных фотографий протяженного объекта прямоугольной формы (Limonova et al., 2018); быстрый подсчет лучевых сумм в вычислительной компьютерной томографии (Bulatov et al., 2020); прослеживание объектов, содержащих множество концентрических дуг, в видеопотоке (Котов и др., 2015) и другие.

Для поиска отрезков, которые будут локально приближать искомые границы, изображение обрабатывается скользящим окном. Затем при помощи БПХ в каждом новом положении окна ищется не более одной превалирующей прямой, которая задается границами рассматриваемого окна. Этот процесс мы и будем называть оконным преобразованием Хафа, идеи которого были заложены еще в 1959 г. в работе (Hough, 1959).

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

СХЕМА ДЕТЕКЦИИ ПРОТЯЖЕННЫХ ГРАНИЦ НА ИЗОБРАЖЕНИИ

Общая схема алгоритма приведена в виде псевдокода в Приложении (алгоритм 1). Алгоритму на вход подается изображение с нечетко выделенными границами: на рис. 2, а таким изображением является результат анализа формы структурного тензора в окрестности каждой точки изображения, а для б – результат применения морфологической операции “tophat” (вычитания из исходного изображения результата его размыкания). Выходом является набор ломаных, задающих на изображении положение протяженных границ. Поиск ломаных осуществляется в три этапа: ищутся отрезки при помощи БПХ; полученные отрезки группируются в неупорядоченные множества с учетом ограничения ломаных на угол излома; в каждой из групп определяется порядок обхода, группа аппроксимируется ломаной и проходит проверку на протяженность.

Далее мы подробно рассмотрим каждый из этапов алгоритма. Однако прежде, чем перейти к их описанию, изложим некоторые детали использования аппарата БПХ.

БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ХАФА

Быстрое преобразование Хафа вычисляет суммы значений пикселей вдоль прямых, которые аппроксимируются специальным дискретным паттерном – диадическим (Ershov et al., 2015). Самоподобная структура диадического паттерна и рекурсивная схема суммаций позволяют уменьшить вычислительную сложность подсчета Хаф-образа до $O({{n}^{2}}{\text{log}}(n))$), в то время как асимптотическая сложность стандартного ПХ для плотных изображений – $O({{n}^{3}})$, где n – сторона изображения. Более того, в 2018 г. в работе (Khanipov, 2018) было доказано, что данная вычислительная сложность является наименьшей достижимой.

При вычислении БПХ прямые на изображении задаются точками пересечения с противоположными краями изображения $\left( {s,0} \right)$ и $\left( {s + t,~n} \right)$, где s – целочисленный сдвиг паттерна, а t – целочисленный наклон. Такой прямой соответствует точка $\left( {s,~t} \right)$ в Хаф-образе, значение в которой равняется сумме значений пикселей вдоль соответствующего паттерна.

Допустим, что на изображении есть прямая, параметризованная через ${{s}_{0}}$ и ${{t}_{0}}$, значения пикселей вдоль которой велики, а по любой другой параллельной ей прямой – малы. Следовательно, сумма вдоль нее тоже будет велика, а суммы вдоль других параллельных прямых – малы. Тогда в строке ${{t}_{0}}$ Хаф-образа на профиле интенсивности будет наблюдаться резкий пик с вершиной в точке ${{s}_{0}}$ (рис. 3, б).

ПОИСК ОТРЕЗКОВ НА ИЗОБРАЖЕНИИ

Для поиска множества отрезков, покрывающих протяженные границы, изображение обрабатывается скользящим квадратным окном со стороной w. В каждом новом положении окна ищется одна превалирующая прямая при помощи БПХ. Сегмент, задаваемый граничными точками $\left( {s,0} \right)$ и $\left( {s + t,~w} \right)$ рассматриваемого окна, и будет искомым прямолинейным сегментом в пространстве исходного изображения.

Ввиду особенностей вычислений алгоритм Брейди вычисляет БПХ для прямых, угол наклона которых ограничен диапазоном в 45° (далее – квадрант). Ввиду того, что мы не накладываем ограничение на ориентацию отрезка в плоскости изображения, полученного Хаф-образа нам будет, очевидно, недостаточно. Для получения Хаф-образа для полного диапазона углов вычисляются четыре Хаф-образа, соответствующие следующим квадрантам: для горизонтальных линий с наклоном вправо в квадранте [–45°, 0°] и влево в квадранте [0°, 45°], для вертикальных линий с наклоном вправо в квадранте [45°, 90°] и влево в квадранте [90°, 135°], которые затем объединяются в один (Aliev et al., 2019).

Как было сказано выше, суммация вдоль прямой дает пик интенсивности в соответствующей строке Хаф-образа. Поэтому мы будем искать координаты пика в два последовательных этапа: сначала определимся со строкой, “пиковость” в которой максимальна, затем выберем максимальное значение в найденной строке.

Критерием для проверки строки на “пиковость” было решено выбрать дисперсию значений в строке. Это связано с тем, что в одном окне могут встретиться две линии с кардинально разным углом наклона. Например, такое характерно для снимков ДЗЗ, когда на изображении дорожной сети в сторону от главной трассы уходят боковые ответвления. В этом случае к превалирующей прямой должна приближаться главная трасса. Как правило, такая дорога отличается от соседних шириной и большим количеством образующих ее линий с близким углом наклона. На профиле интенсивности в соответствующей строке Хаф-образа это будет выражено в большем количестве пиков и их толщине. В этом случае дисперсия значений в строке, соответствующим направлению “главной” линии, будет больше, чем вдоль других линий (рис. 3).

Стоит заметить, что это не единственный возможный критерий. Так, например, в работе (Bezmaternykh et al., 2020) в качестве критерия берется сумма квадратов градиентов в строке.

Без потери общности далее будем говорить о поиске отрезков только в квадранте [45°, 90°]. Поиск в полном Хаф-образе аналогичен и отличается лишь обратным преобразованием точки $\left( {s,t} \right)$ в координаты сегмента на исходном изображении.

Общая схема поиска отрезков для одного квадранта приведена в Приложении (алгоритм 2).

Чтобы избавиться от размытых пиков и сохранить более резкие, можно дополнительно сгладить полученный Хаф-образ гауссовым фильтром вдоль оси $t$ и вычесть из исходного Хаф-образа полученный, оставив только неотрицательные значения.

ГРУППИРОВКА ОТРЕЗКОВ

Целью группировки отрезков является их соотнесение с той или иной границей. В основе группировки – попарный перебор отрезков. Пара отрезков $\left( {u,~v} \right)$ считаются принадлежащими одной границе, если выполняются два следующих условия:

1. Расстояние между отрезками меньше ${{l}_{{max}}}$;

2. Угол $\angle \left( {u,v} \right)$ между отрезками лежит в диапазоне $\left[ {{{\phi }_{{min}}},{{\phi }_{{max}}}} \right]$.

В данной работе расстояние между отрезками определяется как расстояние между ближайшими на отрезках $\left( {u,~v} \right)$ точками, а угол между отрезками – как угол между двумя лучами, выходящими из точки пересечения отрезков к их наиболее удаленным концам (рис. 4, а). Для непересекающихся отрезков такой угол доопределяется параллельным переносом отрезков до совпадения двух ближайших концов в одной вершине (б).

Пусть каждая такая пара отрезков, которая удовлетворяет условиям 1–2, образует ребро $e \in E = {\text{\{ }}\left( {u,~v} \right){\text{|}}u,v \in V\} $ в неориентированном графе $G = \left( {V,E} \right)$. Тогда группировку отрезков можно свести к поиску компонент связности в образованном графе G (Приложение, алгоритм 3).

АППРОКСИМАЦИЯ ГРУПП ОТРЕЗКОВ ЛОМАНЫМИ

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

Для случая приближения группы отрезков одиночным прямолинейным сегментом ищется пара наиболее удаленных точек среди всех концов отрезков в группе. Эта пара точек задает координаты концов сегмента. Далее для всех остальных концов отрезков в группе проверяется их близость до образованного сегмента через расстояние от конкретной точки до построенного сегмента. Если доля близких точек велика, то линия разметки считается прямолинейной, а полученный сегмент – ее аппроксимацией. Общая схема описанных вычислений и их порядок приведены в Приложении, алгоритм 5.

Если же приблизить группу прямолинейным сегментом не удается, то запускается аппроксимация группы отрезков ломаной (Приложение, алгоритм 6).

Для аппроксимации группы отрезков C' ломаной необходимо сначала задать порядок обхода этих отрезков в соответствующей компоненте связности C' графа G. Таким образом, при обходе отрезков для смежных отрезков будут выполняться условия 1–2, введенные в разделе “Группировка отрезков”. Однако этого все еще недостаточно для выстраивания ломаной, звенья которой также удовлетворяют условию 2.

Поясним на конкретном примере, приведенном на рис. 5, а. Допустим, на угол между парой отрезков наложены ограничения вида ${{\phi }_{{min}}} = 90^\circ $, ${{\phi }_{{max}}} = 180^\circ $, ${{l}_{{max}}} = 0$. Как мы видим из примера, выполнение ограничений для пар отрезков 1–2 и 1–3 не гарантирует соблюдения введенных ограничений при построении пути на отрезках 2–1–3 (такой путь обозначен пунктирной черной полилинией). Для контроля обхода таких отрезков будем дополнительно считать углы, образованные серединами троек отрезков (см. рис. 5(б)), которые мы будем называть переходными.

Переходным углом между отрезками $u,v$ и k будем называть угол $\angle \left( {u,v,k} \right)$, образованный двумя лучами, выходящими из середины отрезка $v$ к серединам отрезков u и k (рис. 6). Переходный угол также должен удовлетворять условию 2.

Для возможности обхода группы в случае отсутствия переходных углов в нужном диапазоне будем достраивать подграф C' следующим образом: если $\angle \left( {u,v,k} \right) \notin \left[ {{{\phi }_{{min}}},{{\phi }_{{max}}}} \right]$ и $\left( {u,~k} \right) \notin E$, но $\angle \left( {u,~k} \right) \in \left[ {{{\phi }_{{min}}},~{{\phi }_{{max}}}} \right]$, то пробуем построить ребро $(u,k$) в подграфе C'. Для этого должно выполняться следующее требование: $\exists ~u{\kern 1pt} ' \in V$, $\left( {u{\kern 1pt} ',u} \right) \in E$ и $\angle \left( {u{\kern 1pt} ',u,k} \right) \in \left[ {{{\phi }_{{min}}},{{\phi }_{{max}}}} \right]$ или $\left( {k,u{\kern 1pt} '} \right) \in E$ и $\angle \left( {u,k,u{\kern 1pt} '} \right) \in \left[ {{{\phi }_{{min}}},{{\phi }_{{max}}}} \right]$, то добавляем ребро $\left( {u,k} \right)$ в подграф C'.

Для поиска порядка обхода всех отрезков будем использовать алгоритм Флойда. Для этого присвоим вес каждому ребру ($u,v$), равный расстоянию между самыми удаленными концами отрезков $u,v$. Выходом алгоритма будет матрица кратчайших путей D между всеми парами вершин и матрица P, хранящая информацию о номерах фаз, на которых было получено кратчайшее расстояние между парами вершин. Далее из всех кратчайших путей выбирается путь, значение которого максимально. Если выбор максимального пути не однозначен (максимальные значения близки в пределах заданной погрешности), то выбирается максимальный путь с минимальным количеством пройденных вершин. Далее с использованием информации о фазах P восстанавливается обход вершин-отрезков.

Ввиду особенностей вычислений, описанный выше алгоритм ищет только разомкнутые прямолинейные и криволинейные границы. Результатом аппроксимации группы отрезков, покрывающих окружность, будет ломаная, соответствующая только половине окружности. Это связано с тем, что полный обход окружности будет иметь в полученной матрице D минимальное значение (так как кратчайшее расстояние между началом и концом будет равно нулю), а обход половины – максимальное. Поэтому из концов выбранного пути ищется альтернативный путь, используя предварительно подсчитанную матрицу Флойда. Если такой путь существует, и он не имеет общих вершин с предварительно найденным путем (за исключением начала и конца), то эти пути объединяются в один.

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

ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ КАЧЕСТВА РАБОТЫ ПРЕДЛАГАЕМОГО АЛГОРИТМА

Качество работы детектора протяженных границ оценивалось преимущественно на тестовом наборе данных, содержащем изображения дороги. Изображения были получены с фронтальной камеры БПТС при проезде по закрытой территории полигона “Калибр”. Дополнительно были проведены эксперименты на отдельных снимках ДЗЗ и топограмме дислокаций кристалла Si(111) (Zolotov et al., 2019) для проверки работоспособности алгоритма на разных моделях входных данных. На изображениях дороги протяженными границами задавались неширокие полосы дорожной разметки, на снимках ДЗЗ – дороги, на топограмме – дислокации.

Примеры входных данных приведены на рис. 1, демонстрация пошаговой работы детектора для всех трех типов данных приведена на рис. 7: а – на изображении дороги; б – на снимке ДЗЗ; в – на топограмме дислокаций в кристале Si(111). Для выделения дорожной разметки использовалась морфологическая операция “tophat” с квадратным окном, сторона которого бралась соразмерно с шириной полосы дорожной разметки, а для выделения дорог на данных ДЗЗ анализировалась форма структурного тензора в окрестности каждой точки изображения. Топограмма предварительной фильтрации не подвергалась.

Для получения численных результатов использовался только набор данных, собранный на полигоне “Калибр”. Истинные положения полос дорожной разметки были вручную отмечены в виде ломаных, а для сравнения ответов детектора и истинных ответов использовалась метрика из работы (Абрамов и др., 2019).

МЕТРИКА КАЧЕСТВА

Для численной оценки результата работы детектора были использованы точность (precision) и полнота (recall), для вычисления которых использовались количества ложноположительных (FP), ложноотрицательных (FN) и уникальных истинно положительных (UTP) ответов детектора. Общее количество истинно положительных (TP) срабатываний также подсчитывалось, однако из-за возможного множественного срабатывания детектора на отдельной полосе дорожной разметки для честного подсчета полноты и точности решено было использовать именно уникальные истинно положительные срабатывания.

Рассмотрим ломаную линию L, состоящую из N звеньев с координатами (x_i, y_i), i ∈ [0, N]. Введем понятие региона точности (Region of Precision, ROP):

где Ω_i – прямоугольник на изображении, заданный точками α_i – наклон i-го звена цепи L, образованного точками (x_i, y_i), (x_{i + 1}, y_{i + 1}), ω – параметр алгоритма, отвечающий за размер окрестности вокруг звена (ω = 14 пикселей) (рис. 8).

Тогда ответ детектора классифицируется как TP, FP или FN, если выполняется одно из условий 1–3:

1. ${{g}_{{{{e}_{i}}}}} = RO{{P}_{{{{L}_{{{{r}_{j}}}}}}}}(\omega ) \cap {{L}_{{{{e}_{i}}}}}$ – насколько хорошо i-я найденная ломаная сопоставилась c j-й истинной. Если ${{g}_{{{{e}_{i}}}}} = 0\forall j$, то ответ детектора – FP.

2. ${{g}_{{{{r}_{j}}}}} = RO{{P}_{{{{L}_{{{{e}_{i}}}}}}}}(\omega ) \cap {{L}_{{{{r}_{j}}}}}$ – насколько хорошо j-я истинная ломаная r_j сопоставилась c i-й найденной ломаной e_i. Если ${{g}_{{{{r}_{j}}}}} = 0\forall i$, то ответ детектора – FN.

3. Иначе $g = \min ({{g}_{{{{r}_{j}}}}},{{g}_{{{{e}_{i}}}}}) > 0$ и ответ детектора – TP.

Количество уникальных истинно положительных срабатываний считалось следующим образом:

ЧИСЛЕННЫЕ РЕЗУЛЬТАТЫ ТЕСТИРОВАНИЯ АЛГОРИТМА

Набор изображений, снятых на полигоне “Калибр”, состоял из 1597 изображений дороги. Из них 1132 изображения содержали прямолинейную дорожную разметку, 437 – криволинейную, 28 кадров не содержали дорожной разметки вовсе. Общее количество линий дорожной разметки – 5745.

Было найдено 10 861 линий дорожной разметки, из них истинно положительных – 5308 (уникальных – 4182), ложноположительных – 5553. Полнота детектирования на тестовом наборе составила 73%, точность – 43%.

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

В работе (Shipitko et al., 2018) приведены результаты экспериментов, которые демонстрируют уменьшение средней ошибки локализации БПТС в 8 раз при использовании предлагаемого алгоритма.

ДАЛЬНЕЙШИЕ ИССЛЕДОВАНИЯ

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

В будущем планируется оптимизировать поиск отрезков за счет однократного вычисления БПХ на области перекрытия соседних окон или исключить перекрытие окон вовсе, если это не скажется негативно на процедуре группировки отрезков. Кроме этого, представляет научный и практический интерес уточнить границы найденного прямолинейного сегмента в пределах ограничивающего его окна или найти его продолжение в соседнем окне с использованием быстрого вычисления сумм по произвольным отрезкам на изображении в так называемой БПХ-пирамиде (Soshin et al., 2020).

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

ЗАКЛЮЧЕНИЕ

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

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

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

Полученные качественные и количественные результаты экспериментов свидетельствуют о практической ценности предлагаемого алгоритма.

Исследование выполнено при частичной финансовой поддержке РФФИ в рамках научных проектов № 17-29-03161 и №18-29-26035.