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

Введение

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

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

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

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

Предлагаемый алгоритм включает в себя следующие операции:

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

Рассмотрим подробно каждую операцию.

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

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

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

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

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

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

Решение поставленной задачи может быть выполнено с помощью алгоритма RANSAC (от англ. RANdom SAmple Consensus — соглашение по случайным выборкам).

Алгоритм RANSAC определяет наилучшую окружность на изображении, состоящем из N граничных точек, следующим образом [3]:

1. Случайно выбираются три граничные точки изображения.
2. По выбранным точкам строится окружность.
3. Для каждой граничной точки, не вошедшей в набор из трех выбранных точек, определяется расстояние от точки до построенной окружности и результат вычисления сравнивается с порогом ε. Если расстояние меньше значения ε, точка считается близлежащей, иначе — удаленной. Рекомендуемая величина порога ε определена экспериментально и составляет 1–3 пикселя.
4. Вычисляется количество близлежащих точек D.
5. Вычисляется относительное количество близлежащих точек:
   

   где D — количество близлежащих точек, N — общее число граничных точек.

6. Вычисляется требуемое число итераций:
   

   где wⁿ — вероятность одновременного выбора n близлежащих точек (в нашем случае n = 3); z — вероятность одновременного выбора удаленных точек. В соответствии с данными, полученными экспериментально, при z >10^–2 алгоритм обеспечивает быструю сходимость, но при этом уменьшается точность, при z<10^–4 алгоритм обеспечивает малую сходимость, но увеличивается точность. Оптимальным с точки зрения обеспечения точности и сходимости алгоритма является значение z = 10^–3.

7. Сравнивается текущий номер итерации со значением выражения (2). Если текущий номер итерации больше значения k, то вычисления останавливаются, выбранной считается окружность с максимальным числом близлежащих точек. Иначе выполняются пп. 1–7.
8. Вычисляются координаты центра изображения.

На рис. 1в показана выделенная внешняя граница и вычисленный центр изображения.

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

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

Теория преобразования Хафа

При решении задач выделения прямых на изображениях удобнее представить уравнение прямой с помощью параметров ρ и θ (рис. 2а):

где ρ — величина вектора от начала координат до ближайшей точки на прямой; θ — угол между этим вектором и осью координат.

Рис. 2. а) Параметризация прямой линии; б) пространство Хафа

Для каждой прямой параметры (ρ, θ) уникальны. При этом через любую точку прямой можно провести бесконечное число прямых, параметры которых определяются уравнением (3). Набор параметров (ρ, θ) для каждой точки образует синусоидальную кривую в пространстве Хафа (рис. 2б), которая, в свою очередь, уникальна для данной точки.

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

Рис. 3. Точки на прямой линии (а) и соответствующие им синусоидальные кривые (б)

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

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

Рис. 4. Дискретизация пространства Хафа на ячейки накопления

Дискретизация выполняется разбиением пространства Хафа на ячейки накопления [4]. Каждая отдельная ячейка (i,j) характеризуется параметрами (ρ_i, θ_j).

В ячейках (i,j) дискретного пространства Хафа накапливается число точек, соответствующих уравнению (3) с параметрами (ρ_i, θ_j). Число точек, накопленное в ячейке, показывает вероятность существования соответствующей прямой линии.

Выделение точек интереса

Очевидно, что анализ целого изображения оказывается избыточным при выделении прямых на основе алгоритма Хафа. Поэтому необходимы критерии выбора точек интереса. Известно, что прямая линия содержит точки изображения, яркость которых сильно отличается от соседних, при этом изменение яркости происходит скачкообразно. Такие точки согласно теории цифровой обработки изображений составляют так называемый край [5]. Поэтому для уменьшения количества обрабатываемых точек изображения следует выделить края на изображении.

Известные алгоритмы, в том числе реализованные в специализированных математических пакетах, при поиске края, как правило, используют два критерия: первый — производная яркости скачкообразно изменяется; второй — производная яркости имеет пересечение нулевого уровня [6, 7]. В результате выделения краев формируется бинарное изображение, ненулевые точки которого являются входными для алгоритма преобразования Хафа. На рис. 5 показан результат выделения краев с помощью стандартной функции edge среды MATLAB.

Рис. 5. Результаты выделения краев изображения средой MATLAB: а) исходное изображение; б) изображение с выделенными краями

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

Реализация данного подхода включает следующие этапы:

1. С помощью оператора Собеля (Sobel) для каждой точки изображения вычисляются ортогональные компоненты градиента яркости по направлению [4]:
   

   где (x,y) — координаты центрального пикселя маски (окна или ядра) оператора Собеля; I(x,y) — яркость пикселя (x,y); G_x(x,y), G_y(x,y) — горизонтальный и вертикальный градиент соответственно; Ф(x,y) — фаза градиента.

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

   где w — окрестность вокруг пикселя (x,y).

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

   где B — примитив; (A?kB) — обозначает k последовательных применений операции эрозии к множеству А; ° — обозначает операцию размыкания.

Поэтапные результаты обработки изображения представлены на рис. 6.

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

Предложенный градиентный подход позволяет подавлять шумовые точки и оставлять только точки интереса, принадлежащие радиальным линиям. По сравнению с изображением, полученным в результате выделения краев стандартными средствами (рис. 5), с помощью градиентного подхода можно сформировать изображение с меньшим (примерно 80%) количеством шумовых точек, при этом время обработки снижается в среднем на 50–75%.

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

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

Использование центра полусферического изображения как начала координат позволяет перейти к полярной системе, что значительно упрощает обработку по сравнению с декартовой системой. А для того чтобы противолежащие относительно оси симметрии точки не оказывали влияния на результат обработки, предлагается разделить изображение пополам. При этом процесс обработки проводится независимо для каждой части изображения, а потом результаты обработки складываются. Разделение полусферического изображения пополам ограничивает значения параметра θ пространства Хафа диапазоном [0: 180°].

Модифицированное преобразование Хафа, которое применяется для каждой части полусферического изображения, заключается в следующем:

1. Пространство Хафа разделяется на ячейки накопления с шагом 0,5. Первоначальные значения ячеек приравниваются к нулю.
2. Извлекаются точки интереса (краевые точки) с их координатами из бинарного изображения с использованием градиентного подхода.

Для каждой точки интереса:

1. Вычисляется значение параметра ρ_i по уравнению (3) для каждого дискретного значения параметра θ пространства Хафа.
2. Если значение параметра ρ_i находится в диапазоне [–5: 5], считается, что данная точка может принадлежать радиальной линии; иначе — данная точка не представляет интереса. Диапазон параметра ρ_i определяет «вертикальность» линий.
3. Значение параметра ρ_i округляется до ближайшего дискретного значения ρ пространства Хафа.
4. Значение соответствующей ячейки накопления увеличивается на единицу.

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

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

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

Заключение

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

Литература

1. Макарецкий Е. А., Овчинников А. В., Фан Чан Данг Хоа. Полусферические камеры прикладных телевизионных систем: получение и преобразование полусферических изображенийv// Компоненты и технологии. 2010. № 9.
2. Макарецкий Е. А., Овчинников А. В., Фан Чан Данг Хоа. Выделение и сопровождение движущихся объектов на полусферических изображениях // Компоненты и технологии. 2011. № 1.
3. http://cgm.computergraphics.ru/content/view/47
4. Гонсалес Р., Будс Р. Цифровая обработка изображений. М.: Техносфера, 2005.
5. Форсайт Д. А., Понс Ж. Компьютерное зрение. Современный подход. М.: ИД «Вильямс», 2004.
6. Методы компьютерной обработки изображений / Под ред. В. А. Сойфера. М.: Физматлит, 2001.
7. Дегтярева А., Вежневец В. Преобразование Хафа (Hough transform) // Компьютерная графика и мультимедиа. 2003. Вып. № 1–2.