|
УДК 004.932.2
Алгоритм автоматической идентификации площадных объектов на
бинарных растровых изображениях
С.В. Москаленко, Ю.А. Гатчин
The article presents an algorithm for identification of
polygon objects in binary raster images with following stage
of vectorization. Proposed algorithm uses circular waves
generations to speed up the analysis of image data and to
save the connectivity of polygons with the rest objects in
the image, while retaining the original layout.
В статье представлен новый
алгоритм для идентификации и параметризации площадных
объектов на бинарных растровых изображениях. Применяемый
метод сферических волн обеспечивает высокую скорость анализа
графических данных и позволяет сохранить связность площадных
объектов с другими объектами изображения, сохраняя исходную
топологию.
Ключевые слова:
распознавание графических образов, векторизация, площадной
объект, сегментация, связность.
Keywords:
graphic images recognition, vectorization, polygon object,
segmentation, connectivity
Введение
Одной из актуальных проблем в современных САПР является
проблема преобразования графических данных из традиционных
источников бумажных носителей (машиностроительные чертежи,
приборостроительные схемы) в электронную форму. Суть
проблемы заключена в том, что на данный момент не
разработано полностью автоматических систем приведения
оцифрованных данных к электронной векторной форме. Векторная
форма является весьма удобным и часто используемым
представлением в современных САПР, которая являет собой
структуру данных из некоторого упорядоченного набора точек,
прямых, ломаных, полигонов.
В общем виде задача векторизации представляет собой
совокупность автоматизированных процедур синтеза графических
объектов представленных в векторной форме. Синтез объектов
начинается с этапа первичной векторизации. Данный этап
является предметом исследования в областях анализа и
распознавания изображений уже многие годы, однако, не смотря
на это, анализ существующих решений выявил недостаточную их
надежность с точки зрения выходных характеристик:
быстродействие, уровень сохранения топологической связности
с исходным изображением. Задача первичной векторизации
распадается на несколько подзадач, первая из которых
сегментация (идентификация). Под сегментацией
подразумевается определение типа объекта: текст или графика,
площадной объект или линейный, разделение на тонкие или
основные линии. В статье основное внимание уделено вопросу
идентификации площадных объектов. За идентификацией следует
подзадача параметризации, которая в классическом
представлении должна служить выявлению необходимых атрибутов
объектов (например, координатную привязку). Во время
параметризации происходит выделение границ площадных
объектов в виде цепочек пикселей растра.
Завершает этап первичной векторизации процедура линейной
аппроксимации, когда множества цепочек пикселей
минимизируются по критерию информативности. Происходит
отбрасывание некритичных точек из множеств, тем самым
избыточность данных сокращается. В результате формируется
модель изображения в виде набора вершин, полилиний и
множества некоторых атрибутов. Эта процедура является
достаточно проработанной в литературе [1,2], и в данной
статье этап первичной векторизации ограничен лишь описанием
подзадач сегментации и параметризации.
На основе анализа существующих решений идентификации и
параметризации площадных объектов предложен новый
эффективный алгоритм. Данный алгоритм получает на выходе
минимизированный набор данных, который может быть
использован на последующих этапах анализа изображения
(например, на этапе высокоуровневого распознавания
графических образов).
Анализ существующих решений
Площадным объектом называется тот объект, геометрическим
описанием которого является полигон, т.е. многоугольник.
Внутренняя область данных объектов задается цветом. В
представленной статье площадные объекты рассматриваются в
контексте бинарных изображений, поэтому площадной объект
задается черным цветом. Данные объекты могут иметь дыры
(полигоны белого цвета, лежащие во внутренней области
площадных объектов). Линейным же объектом называется объект,
геометрическое описание которого прямой отрезок или
ломаная прямая.
В большинстве подходов критерием принадлежности классу
линейного либо площадного объекта является некоторое
значение Δ [3]. Если толщина объекта по всей его длине
больше Δ, значит, объект принадлежит площадному классу. Если
толщина объекта по всей его длине меньше Δ объект
принадлежит линейному классу. Здесь толщина
w
объекта в точке (i,j)
равна сумме расстояния d от
точки (i,j)
до ближайшей фоновой точки и расстояния g от (i,j)
до ближайшей точки средней линии: w
= d +
g
(рис.1). Также вместо простого порогового значения Δ
рекомендуется использовать двухпороговую гистерезисную
классификацию, когда объекты относят к площадным, все
толщины которых больше δ, причем в области есть хотя бы одна
толщина со значением большим Δ [4]. Однако остается вопрос о
выборе данных пороговых значений Δ и δ. Большинство систем
векторизации являются полуавтоматическими [4, 5], где
упомянутые пороги задаются оператором.
Рис. 1. Представление толщины (w)
линейного объекта
Также во многих существующих подходах уделяется мало
внимания сохранению межобъектной топологической связности.
Связность - довольно важная характеристика работы этапа
первичной векторизации т.к. сохранение связей между
объектами упрощает задачу анализа изображения на более
высоких уровнях. Связность может характеризоваться
следующими отношениями: соседство объектов, привязка к точке
объекта, зависимость по существованию. В подходе [6] опущен
анализ на предмет связности, что приводит к отсутствию
отношений между сопряженными объектами в результирующем
атрибутивном наборе.
Реализация алгоритма
Автоматизм представленного алгоритма обеспечивается
предварительным анализом входного растра подходом, описанным
в [7], в результате работы которого имеем выборку всех
линейных объектов изображения с соответствующими параметрами
(количество объектов, ширина линии, и др.). На основании
статистических данных этой выборки можно вывести различные
пороговые значения такие, как Δ и δ (см. выше). Упомянутый
подход [7] является автоматическим, что позволяет отнести
предлагаемую в данной работе систему к классу полностью
автоматических.
Работа представленного алгоритма начинается с побитового
сканирования изображения на наличие черных точек растра
c интервалом в 10 пикселей. После
получения исходной точки, от нее в основных направлениях
строится циклическая гистограмма по черным пикселям до
первого белого. Гистограмма строится для определения типа
обнаруженного объекта и выдвижения гипотезы о причастности
объекта классу площадных [7]. Алгоритм, выдвигая данную
гипотезу, также берет во внимание величину порогового
значения Δ.
После подтверждения гипотезы происходит запуск процедуры
выявления границ объекта. Типовой метод проверки на
причастность точки (пискселя) границе области для бинарных
изображений таков: точка с координатами (i,
j) считается граничной, если
fij = 1; и в
8-окрестностях точки (i,
j) имеются как объектные, так
и фоновые точки. Здесь fij
функция определения цвета в точке с координатами (i,
j), fij
= 1 для черного пикселя, fij
= 0 для белого. Трудоемкость работы метода
пропорциональна объему растра (~M*N).
Используя данный метод можно выделять граничные пиксели (контуры)
на растре, формируя из них последовательные цепочки. У
представленного типового метода есть ряд недостатков исходя
из контекста проблемы определения площадных объектов.
Во-первых, его трудоемкость достаточно велика, можно вместо
попиксельного сканирования растра ограничиться разреженной
выборкой. Во-вторых, отсутствует проверка на корректность
направления следования: после обнаружения очередной точки
контура ее принадлежность площадному объекту не
подтверждается. Ведь существует возможность, когда процедура
отслеживания контура может начать включать некорректные
граничные точки линейного объекта в состав площадного. К
примеру, на рис. 2 для площадного объекта треугольник,
пересекаемого линейным объектом отрезок, произойдет
именно такая ситуация.
Рис. 2. Пример работы процедуры выявления границ
В-третьих, отсутствует функционал по выявлению межобъектной
связности. Так, например, на рис. 2 можно было бы выявить
отношение соседства объектов (фигура отрезок располагается
довольно близко к фигуре треугольник) и отношение привязки
одного объекта к другому (координаты привязки).
Для исключения продвижения отслеживающей процедуры в ложных
направлениях необходим углубленный и разреженный (выборочный)
анализ растра. Данные требования реализованы в волновом
методе определения границ объектов. Суть его заключается в
последовательном построении вдоль границ объекта сферических
волн, радиусом большим Δ и центром каждой новой волны,
совпадающим с последней найденной точкой пересечения
предыдущей волны с контуром площадного объекта. Построение
сферической волны обеспечивает тщательное отслеживание
ответвлений (переходов на другие объекты) от рассматриваемой
области, обладая при этом разреженным анализом растра. При
пересечении волной контура один раз, происходит занесение
найденной точки пересечения в массив точек контура и задание
координат центра следующей волны (центр следующей волны
совпадет с последней найденной точкой). При пересечении
волной контура более чем один раз, возникает сомнительная
ситуация: обнаружилось ли ветвление или же волна все еще
следует верному направлению следования, а возмущение вызвано
шумами на изображении. Для разрешения данной ситуации
строится циклическая гистограмма от последней контурной
точки, занесенной в массив. Если анализ гистограммы
определил ветвление, то происходит сохранение координат
касания площадного и линейного объекта, а также задание
направления дальнейшего следования именно вдоль контура
текущего площадного объекта. Тем самым уже на этапе
выявления границ сохраняется информация об отношениях
межобъектной связности. Процедура выявления контура будет
продолжать свою работу до тех пор, пока не будет обнаружена
точка, замыкающая контур.
На рис. 3 изображен пример следования процедуры выделения
границ площадного объекта. Во время построения новой волны
происходит подсчет количества пересечений окружности волны с
границами объектов, где каждое пересечение будет являться
граничной точкой. В случае, изображенном на рис. 3, будут
обнаружены примитивы: площадной объект и линейный.
Рис. 3. Иллюстрация
построения генераций волн для определения границ
На рис. 4 представлена блок-схема, изображающая обобщенный
алгоритм работы системы идентификации площадных объектов на
растре.
Рис. 4. Схема
алгоритма идентификации площадных объектов на растровом
изображении
Заключение
Разработанный авторами алгоритм, предназначенный для
обработки и отображения графических данных, обладает
повышенной эффективностью, причем под эффективностью
понимается повышенное быстродействие алгоритма, и улучшенное
качество получаемого решения, когда полученная векторная
модель наиболее точно соответствует топологии входного
растра. Эта эффективность обусловлена использованием
последовательностей сферических волн во время поиска границ
площадных объектов. Разреженный просмотр растра, который
вовлекается как оптимизационный момент, обеспечивает
обнаружение ответвлений и соответственно сохраняет отношения
межобъектной связности. К тому же наличие предварительного
этапа сбора статистических данных позволяет добиться
автоматической работы алгоритма без вмешательства человека.
Также данный алгоритм показал высокую помехоустойчивость.
Эффективное преобразование изображения к векторному виду
является важным шагом в процессе обработки изображения. И от
результатов его работы будут зависеть процедуры анализа
более высокого уровня, такие как распознавание графических
образов. Реализованный алгоритм обладает всеми необходимыми
характеристиками для успешной реализации в этапах,
предшествующих процедурам высокого уровня.
Литература
1. Sklansky, J., Gonzalez, V.: Fast
Polygonal Approximation of Digitized Curves. // Pattern
Recognition, Vol.12 (1980), pp.327-331.
2. Douglas, D., Peucker, Th.: Algorithm
for the reduction of the number of points required to
represent a digitized line or its caricature // The Canadian
Cartographer, Vol.10, #2 (1973), pp.112-122.
3. Москаленко С.В., Гатчин Ю.А. Волновой алгоритм
векторизации линейных растровых изображений //
Научно-технический вестник СПбГУ ИТМО. 2008. №51.
4. Новиков Ю.Л. Эффективные алгоритмы векторизации растровых
изображений и их реализация в геоинформационной системе:
Автореф. дис. канд. техн. наук. М., 2002 С.8.
5. Крылов А. Б., Способ выбора растровых объектов на
монохромном изображении с автоматическим вычислением
геометрических параметров. // Интеллектуальные технологии и
системы - Моск. гос. техн.
ун-т им. Н.Э.Баумана 2001.
Вып.5 С.34-42.
6.
F. K. H. Quek. An algorithm for
the rapid computation of boundaries of run length encoded
regions. //Pattern Recognition Journal, 33 2000 -
C.16371649.
7. Москаленко С.В., Гатчин Ю.А.,
Помехоустойчивый волновой алгоритм векторизации
линейных растровых объектов. // Вестник компьютерных и
информационных технологий М., Машиностроение - 2009, 5.
go to published works page ->
|
