Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,749

ПОИСК ГРАНИЦ ОБЪЕКТОВ ПРЯМОУГОЛЬНОЙ ФОРМЫ НА ИЗОБРАЖЕНИЯХ С КОНТУРНЫМ ФОРМАТОМ ПРЕДСТАВЛЕНИЯ

Патрушев А.О. 1 Осипов М.П. 1
1 Институт информационных технологий математики и механики Нижегородский государственный университет имени Н.И. Лобачевского
В работе представлен алгоритм обработки контурных описаний изображений с целью повышения эффективности выявления объектов прямоугольной формы, чья внешняя граница на изображении распалась на несколько цветовых сегментов либо прерывается другими объектами. В процессе работы алгоритма контуры объединяются в специальную единую графовую структуру, в которой точки различных контуров находящиеся в непосредственной близости друг к другу объединяются, а точки, расположенные поблизости с линиями контуров, проецируются на контур и включаются в него. На полученном графе осуществляется поиск четырёхугольных структур. При этом учитывается возможность наличия промежуточных точек на линиях искомого четырехугольника и их отклонения в пределах некоторой окрестности. Предложены подходы для ускорения работы алгоритма. Алгоритм эффективно обнаруживает объекты на изображении, представляющие собой плоские прямоугольные области в пространстве. В частности, предложенный алгоритм может быть использован в задаче автономной навигации в закрытых помещениях для поиска информационных объектов помещения прямоугольной формы, таких как названия и номера помещений, знаки пожарной безопасности, планы эвакуации и т.п.
компьютерная графика
обработка изображений
выделение контуров
1. Suzuki S., Abe K. Topological Structural Analysis of Digitized Binary Images by Border Following // Computer Vision Graphics and Image Processing. – 1985. – Vol. 30, Issue 1. – Р. 32–46.
2. David Douglas, Thomas Peucker. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature // The Canadian Cartographer. – 1973. – Vol. 10, no. 2. – Р. 112—122.
3. Vasin Yu.G., Osipov M.P., Egorov A.A., Yasakov Yu.V. Autonomous Indoor 3D Navigation // Pattern Recognition and Image Analysis. – 2015. – Vol. 25, No. 3. – Р. 373–377.
4. Vasin Yu.G., Osipov M.P., Egorov A.A., Kustov E.A., Yasakov Yu.V. Autonomous indoor navigation based on 3D modeling, Proceedings of the 11-th International Conference «Pattern recognition and image analysis: new information technologies» (PRIA-11-2013), 2013. – Vol. 2. – Р. 476–478.
5. Осипов М.П., Патрушев А.О. Методы корректировки местоположения в задаче автономной навигации в закрытых помещениях / М.П. Осипов, А.О. Патрушев // Труды 26-ой Международной конференции по компьютерной графике и зрению. – 2016. – С. 417–419.
6. Осипов М.П., Патрушев А.О. Повышение надежности позиционирования в задаче автономной навигации в закрытых помещениях / М.П. Осипов, А.О. Патрушев // SCVRT1516 Труды Международной научной Школы-семинара, ИФТИ, Москва – Протвино, 2016. – С. 15–18.
7. Somayeh Shahrabadi, Joao M.F. Rodrigues, J.M. Hans du Buf. Detection of Indoor and Outdoor Stairs. IbPRIA 2013: Pattern Recognition and Image Analysis. – 2013. – Р. 847–854.
8. Serrаob M., Rodriguesa J.M.F., Rodriguesc J.I., J.M.H. du Bufa. Indoor localization and navigation for blind persons using visual landmarks and a GIS // Proceedings of the 4th International Conference on Software Development for Enhancing Accessibility and Fighting Info-exclusion (DSAI 2012). – 2012. – Р. 65–73.
9. Harlan Hile and Gaetano Borriello. Information Overlay for Camera Phones in Indoor Environments. LoCA 2007: Location- and Context-Awareness. – Р. 68–84.
10. Jos´e J., J.M.H. du Buf, J.M.F. Rodrigues. Visual navigation for the blind. Path and Obstacle Detection. ICPRAM 2012 – International Conference on Pattern Recognition Applications and Methods. – 2012. – Р. 515–519.
11. Duda R.O., Hart P.E. Use of the Hough Transform to Detect Lines and Curves in Pictures // Communications of the ACM. – 1972. – Vol 15, no. 1. – Р. 11–15.

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

Для наглядности основные возможные сложности для алгоритма, ищущего прямоугольные объекты на изображении, собраны в одном синтезированном изображении и пронумерованы (рис. 1).

Варианты расположения объекта на изображении:

1. Контакт с областью другого цвета.

2. Небольшой заслоняющий объект.

3. Разделение объекта на несколько независимых контуров вследствие перекрытия другим объектом.

4. Выход за пределы изображения.

5. Общая грань с областью другого цвета.

6. Небольшой размер (область слишком мала для надежного распознания).

7. Общая грань с областью другого цвета.

8. Контакт с другой областью того же цвета.

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

Цель исследования

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

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

Контуры объектов на изображении находятся с помощью алгоритма Сузуки [1] и аппроксимируются методом Дугласа – Пекера [2]. Результат работы этих алгоритмов представлен на рис. 2.

Алгоритм выделения контуров изображения определил отдельно области 6, 5 (рис. 1), но при этом описал их два раза, по внешнему и по внутреннему краю контура. Объединил в один объект области 1 и 2 (рис. 1), при этом у области 1 остался четырехугольный внутренний контур, а на области 2 образовался набор лишних контуров. Области же 7, 8 (рис. 1) не образовали замкнутого внешнего контура вообще.

patr1.tif

Рис. 1. Возможные комбинации положения прямоугольных объектов по отношению друг к другу

patr2.tif

Рис. 2. Результат работы алгоритмов выделения контуров на синтезированном изображении

patr3a.tif

а)

patr3b.tif

б)

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

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

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

patr4.tif

Рис. 4. Результат объединения цепочки контуров

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

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

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

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

Пример прохода алгоритма изображен на рис. 3, б. Начав из нижней левой, алгоритм пройдет к первой вершине (стрелка 1) и добавит ее в стек. Обнаружив единственную дополнительную вершину, связанную с текущей, алгоритм перейдет к ней (стрелка 2), при этом будет зафиксировано направление угла поворота. От следующей вершины отходят три дополнительных ребра. Два из них (стрелки 3 и 4) отклоняются в сторону противоположную необходимой и не смогут образовать выпуклый четырёхугольник. Оставшееся ребро идет почти параллельно ребру, по которому алгоритм пришел в эту точку (стрелка 5), и поэтому переход будет осуществлен, при этом точка записана не будет. Таким же образом алгоритм проследует по шестой стрелке, упрется в тупик, проследовав по стрелке 7, и, вернувшись назад через стрелки 8 и 9, доберется до изначальной вершины, замкнув круг (рис. 3, б).

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

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

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

patr5.tif

Рис. 5. Визуализация принятия решения при поиске контура

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

Предложенный алгоритм может эффективно использоваться для поиска «информационных объектов» помещения в задаче автономной навигации в закрытых помещениях [3–6]. Это могут быть названия и номера помещений, планы эвакуации, знаки пожарной безопасности и т.д. Все эти объекты представляют собой плоские прямоугольные области в пространстве. Аналогичным образом можно производить поиск треугольных табличек. Например, знаков, предупреждающих о высоком напряжении.

Получившийся в процессе работы граф можно использовать для анализа других объектов в задаче навигации. Например, с его помощью можно существенно облегчить поиск на изображении таких объектов, как лестницы [7], коридоры и двери [8–10]. Алгоритмы поиска таких объектов, как правило, базируются на детектировании линий с использованием преобразования Хафа [11]. При этом изначально не учитывается физическое расположение линий на изображении, разрывы, препятствия, что вызывает ложные срабатывания или затрудняет детектирование. В то время как наличие уже найденных линий на изображении позволит упростить поиск этих объектов. Граф позволяет задать поиск в глубину или поиск по всем объектам с настраиваемыми фильтрами для выделения необходимых объектов, будь то линии или геометрические фигуры.

Заключение

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

Работа была выполнена при поддержке гранта РФФИ № 16-07-01214 А.


Библиографическая ссылка

Патрушев А.О., Осипов М.П. ПОИСК ГРАНИЦ ОБЪЕКТОВ ПРЯМОУГОЛЬНОЙ ФОРМЫ НА ИЗОБРАЖЕНИЯХ С КОНТУРНЫМ ФОРМАТОМ ПРЕДСТАВЛЕНИЯ // Фундаментальные исследования. – 2017. – № 12-1. – С. 91-96;
URL: https://fundamental-research.ru/ru/article/view?id=41985 (дата обращения: 17.10.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074