Обработка полусферических изображений: выделение и идентификация горизонтальных линий

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

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

Выделение горизонтальных линий на полусферических изображениях

Как было показано в работе [1], вертикальная линия на полусферическом изображении представляет собой радиальную линию, проходящую через центр изображения. Горизонтальная линия на полусферическом изображении представляет собой кривую, форма которой зависит от пространственного положения этой линии и аналитически не может быть определена. Поэтому выделение горизонтальных линий на полусферических изображениях является более трудной задачей по сравнению с выделением вертикальных линий.

Известно, что в полусферических камерах падающие оптические волны пересекают оптическую ось в разных точках [3]. На рис. 1 показана гистограмма координат точек пересечения падающих от горизонтальной линии оптических лучей и оптической оси полусферической камеры.

Рис. 1. Гистограмма координат точек пересечения падающих от горизонтальной линии оптических лучей и оптической оси полусферической камеры:
а) длина линии — 2 м;
б) длина линии — 5 м

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

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

Параметры модели окружности должны удовлетворять имеющимся исходным данным — содержать точки интереса изображения. В качестве точек интереса используются краевые точки, которые могут быть выделены с помощью известных алгоритмов выделения краев, например Собеля, Кэнни, Прэвитта. Результаты выделения краевых точек содержат и шумовые точки (рис. 2б). Качество исходных данных влияет на точность модели, поэтому необходимо использовать алгоритм, устойчивый к шумам и наличию среди правильных значительного количества ложных данных.

Рис. 2. Выделение горизонтальных линий на полусферическом изображении:
а) исходное полусферическое изображение;
б) выделение краевых точек;
в) выделение группы связных точек;
г) иллюстрация результата выделения образов горизонтальных линий

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

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

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

1. Выделяются краевые точки из входного полусферического изображения.
2. Из краевых точек выделяются группы связных точек.
3. Для каждой группы связных точек до завершения k итераций:

• равномерно и случайно из группы выбираются 3 точки;
• подбирается модель окружности по этим точкам;
• сравнивается расстояние от каждой оставшейся точки из группы до модели с порогом; если расстояние меньше T, точка считается близлежащей; рекомендуемая величина порога определена экспериментально и составляет 1–3 пикселя;
• если число близлежащих точек больше порогового значения N, то модель считается удачно подобранной; значение порога N выбирается в диапазоне 0,1–0,5 от общего количества точек группы;
• вычисляется число требуемых итераций:

k = log(z)/log(1–wⁿ),         (1)

где wⁿ — вероятность успешного подбора, равная отношению числа близлежащих к общему числу точек; z — вероятность плохого подбора, которая принимается равной 10^–3.

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

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

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

Идентификация горизонтальных линий на полусферических изображениях

Анализ полусферических изображений различных сцен показал, что кривизна изображений горизонтальных линий зависит от их положения относительно полусферической камеры, что значительно усложняет их идентификацию на последовательности полусферических изображений по сравнению с идентификацией вертикальных линий, рассмотренной в [1]. Поэтому кроме требований, которые были определены для дескриптора вертикальных линий [1], необходимо вводить дополнительное требование — дескриптор горизонтальной линии должен быть инвариантен к изменению формы изображения горизонтальной прямой.

Для обеспечения инвариантности дескриптора горизонтальной линии к повороту, линейному изменению освещенности и изменению формы модифицируем алгоритм выделения области интереса, рассмотренный в [1].

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

где (x_c, y_c) — координаты центра окружности, проходящей через точки изображения горизонтальной линии; j₁, j₂ — угловые координаты начальной и конечной точек изображения, принадлежащих к окружности; R — радиус окружности; D — ширина окрестности.

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

Рис. 3. К вопросу идентификации горизонтальных линий:
а) выделение области интереса горизонтальной линии;
б) преобразование области интереса в прямоугольный вид

Кривизна образа горизонтальной линии на полусферическом изображении затрудняет составление дескрипторов. Для преодоления данной проблемы предлагается преобразование окрестности горизонтальной линии в прямоугольный вид. Процедура выполняется следующим образом:

где (x’, y’) — координаты точек после преобразования.

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

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

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

Для исследования алгоритмов выделения и идентификации горизонтальных линий были использованы последовательности полусферических изображений различных сцен, в том числе последовательности изображений, подобранные из открытых библиотек изображений [5, 6] (рис. 4).

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

Исследование алгоритма выделения горизонтальных линий на полусферических изображениях

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

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

Анализ рис. 4 показывает, что для различных сцен, которые подвергаются воздействию различных факторов, образы горизонтальных линий с помощью предложенного алгоритма выделяются достаточно эффективно. В зависимости от четкости образов горизонтальных линий изменяется количество выделенных точек изображения. Для изображений сцен 5 и 6 низкая четкость образов горизонтальных линий приводит к тому, что выделяется только их небольшая часть. Для последовательностей сцен 1 и 2 повышение освещенности в некоторых местах приводит к разрыву образов горизонтальных линий.

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

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

Для оценки эффективности предложенного алгоритма проведено его сравнение с алгоритмом выделения горизонтальных линий на основе аппроксимации модели (ААМ), использованным в работах [7, 8, 9]. В указанном алгоритме полусферическая камера аппроксимируется моделью гиперболоидальной камеры, что позволяет использовать для обработки изображений известную эквивалентную математическую модель гиперболоидальной камеры. Согласно математической модели гиперболоидальной камеры, соотношение между трехмерной точкой и ее образом определяется уникальной точкой, находящейся на так называемой эквивалентной сфере проекции. Как показано в работе [10], точки на эквивалентной сфере проекции, соответствующие точкам изображения, принадлежащим образу горизонтальной линии, лежат на большой окружности данной сферы, что трансформирует задачу выделения горизонтальных линий в задачу выделения точек, принадлежащих большим окружностям эквивалентной сферы проекции.

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

ААМ включает следующие операции:

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

На рис. 5 показаны этапы обработки изображений ААМ.

Рис. 5. Этапы обработки изображений ААМ:
а) исходное изображение;
б) выделение краевых точек;
в) проецирование на эквивалентную сферу;
г) выделение точек, лежащих на большой окружности, и проецирование найденных точек на плоскость изображения

На рис. 6 представлены результаты выделения горизонтальных линий с помощью ААМ. Изображения, используемые для обработки, совпадают с исходными изображениями, представленными на рис. 4. Сравнение результатов обработки разными алгоритмами (рис. 4, 6) показывает выигрыш предложенного авторами алгоритма при выделении длинных горизонтальных линий по сравнению с ААМ. Кроме того, ААМ демонстрирует низкую способность выделять образы горизонтальных линий, находящихся вблизи внешней границы и центра изображения.

Рис. 6. Результаты выделения горизонтальных линий с помощью алгоритма на основе аппроксимации модели:
а) сцена 1;
б) сцена 2;
в) сцена 3;
г) сцена 4;
д) сцена 5;
е) сцена 6

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

На рис. 7 показана оценка повторяемости алгоритмов для шести различных сцен. Как видно, для всех сцен предложенный алгоритм показывает выигрыш по сравнению с ААМ не менее 20%.

Рис. 7. Повторяемость алгоритмов для последовательностей изображений 6 сцен

На рис. 8 даны зависимости повторяемости алгоритмов выделения горизонтальных линий от шума и перемещения.

Рис. 8. Зависимость повторяемости алгоритмов:
а) от шума;
б) от перемещения

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

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

Исследование алгоритма идентификации горизонтальных линий на последовательности полусферических изображений

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

Рис. 9. Зависимость вероятности верной идентификации:
а) от шума;
б) от перемещения

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

Заключение

Предложенные авторами в работах [1, 2] и настоящей статье методы и алгоритмы выделения, идентификации вертикальных и горизонтальных линий на полусферических изображениях позволяют получать информацию о перемещениях объектов — носителей полусферических камер и в дальнейшем реализовать систему ориентации на основе полусферических камер.