Software & Systems

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

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

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

Математический подход наиболее часто сводит задачу к построению диаграммы Вороного [3]. Более эффективными алгоритмами построения скелетона считаются диаграммы Вороного, основанные на триангуляции Делоне, на основе вписывания окружностей с последующим соединением их центров, волновые алгоритмы. Все они требуют больших вычислительных затрат – порядка O(n log n), где n – число граничных точек фигуры, а также имеют ограничения по типу геометрических объектов (например, возникают сложности при обработке широкополосных объектов, где ширина сопоставима с длиной) [4–6].

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

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

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

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

Скелетизация растрового изображения

Пусть имеются замкнутая цепочка O = – граница фигуры, da < 0 – порог на величину отрицательного перегиба.

Требуется построить множество элементов скелетона ES = , где l – длина хорды фигуры в точке элемента скелетона.

Введем следующие два определения.

Определение 1. Положительный обход многоугольника – это последовательный обход его границы в таком порядке, что сумма приращений угла вектора равняется +2p, то есть вектор совершает полный поворот против часовой стрелки.

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

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

Представим алгоритм.

1. Цикл i по элементам границы

{Вычисление приращения delta угла вектора

Если delta < da

То {Поиск минимальной хорды фигуры;

Формирование границы сегмента;

Построение j-го элемента

скелетона, соединяющего конец  j–1-го элемента с серединой полученной хорды;

Запись es =

}

}

2. Формирование областей перекрестков.

3. Вычисление координат геометрических центров тяжести перекрестков.

4. Формирование разветвлений скелетона. Для построения разветвления в области перекрестка центр тяжести соединяется с серединами хорд ближайших сегментов.

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

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

Описание эксперимента

На первом этапе осуществляются выделение объектов растрового изображения путем тернарной цветовой сегментации и аппроксимация границ полученных цветовых сегмен- тов [10]. Затем включается вышеописанный алгоритм скелетизации. Результаты выдаются в виде файла текстового формата XML.

На рисунке 3 видно, как происходят разбиение фигуры на выпуклые сегменты и построение скелетона (изображение с сайта http:// zatochka36.ru/). Показаны автоматически построенные секущие хорды и отрезки, соединяющие их середины.

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

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

Заключение

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

Синтез скелетонов выполняется рекурсивно и зависит от желаемой степени детализации объекта.

Вычислительная сложность алгоритма скелетизации с помощью секущих хорд не превышает O(K2/2), где К – количество отрезков гра- ницы объекта, то есть прямо пропорциональна количеству отрезков границы. Как видим, на эффективность алгоритма существенно влияет качество аппроксимации границ отрезками прямых и дугами окружностей.

Литература

1.    Waleed Abu-Ain, Siti Norul Huda Sheikh Abdullah, Bilal Bataineh, Tarik AbuAin, and Khairuddin Omar. Skeletonization algorithm for binary images. Procedia Technology, 2013, vol. 11, pp. 704–709.

2.    Гонсалес Р., Вудс Р. Цифровая обработка изображений. М.: Техносфера, 2005. 1072 с.

3.    Федоров Р.К., Хмельнов А.Е., Бычков И.В. Об одном подходе к анализу топологии пространственно-распределенных данных с использованием логического вывода // Вычислительные технологии. 2005. Т. 10. № 1. С. 116–130.

4.    Болтенков В.А., Нгуен Гуи Кионг, Малявин Д.В. Анализ алгоритмов скелетизации бинарных изображений // Электротехнические и компьютерные системы. 2015. № 17. С. 102–109.

5.    Гудков В.Ю., Клюев Д.А. Скелетизация бинарных изображений и выделение особых точек для распознавания отпечатков пальцев // Вестн. ЮУрГУ. 2015. Т. 15. № 3. С. 11–17. DOI: 10.14529/ ctcr150302.

6.    Степура Л.В., Демин А.Ю. Обзор методов векторизации изображения // Технологии Microsoft в теории и практике программирования: сб. тр. XIII Всерос. науч.-практич. конф. Томск: Изд-во ТПУ, 2016. С. 184–186.

7.    Местецкий Л.М. Скелетизация многосвязной многоугольной фигуры на основе дерева смежности ее границы // Сиб. журн. вычисл. математики. 2006. Т. 9. № 3. С. 201–216.

8.    Местецкий Л.М. Непрерывная морфология бинарных изображений. Фигуры. Скелеты. Циркуляры. М.: Физматлит, 2009. 287 с.

9.    Кучуганов А.В. Когнитивный алгоритм построения геометрического остова невыпуклых фигур // Приволжский науч. журн. 2012. № 3. С. 84–89.

10. Kasimov D.R., Kuchuganov A.V., Kuchuganov V.N., Oskolkov P.P. Approximation of color images based on the clusterization of the color palette and smoothing boundaries by splines and arcs. Programming and Computer Software, 2018, vol. 44, no. 5, pp. 295–302. DOI: 10.1134/S0361768818050043.

References

1. Waleed Abu-Ain, Siti Norul Huda Sheikh Abdullah, Bilal Bataineh, Tarik AbuAin, Khairuddin Omar. Skeletonization algorithm for binary images. Procedia Technology. 2013, vol. 11, pp. 704–709.
2. Gonzales R., Woods R. Digital Image Processing. Мoscow, Tekhnosfera Publ., 2005, 1072 p.
3. Fedorov R.K., Khmelnov A.E., Bychkov I.V. On one approach to analisys of space distributed data topology using logic output. Computational Technologies. 2005, vol. 10, no. 1, pp. 116–130 (in Russ.).
4. Boltenkov V.A., Nguen G.K., Malyavin D.V. Analysis of binary image skeletonization algorithms. Electrotechnic and Computer Systems. 2015, no. 17, pp. 102–109 (in Russ.).
5. Gudkov V.Yu., Klyuev D.A. Skeletonization of binary images and finding of singular points for fingerprint recognition. Bulletin of the South Ural State Univ. Ser. Computer Technologies, Automatic Control & Radioelectronics. 2015, vol. 15, no. 3, pp. 11–17. DOI: 10.14529/ctcr150302.
6. Stepura L.V., Demin A.Yu.  An overview of image vectorization methods. Technologies Microsoft in programming theory and practice: Proc. 13th All-Russ. Sci. and Pract. Conf. for Students, Postgraduates and Young Scientists. A.V. Liepinsh (Ed.). Tomsk, TPU Publ., 2016, pp. 184–186 (in Russ.).
7. Mestetsky L.M. Skeletization of a multiply connected polygonal figure based on an adjacency tree of its border. Siberian J. of Computational Mathematics. Novosibirsk, 2006, vol. 9, no. 3, pp. 201–216 (in Russ.).
8. Mestetsky L.M. Continuous morphology of binary images. Figures. Skeletons. Circulars. Moscow, Fizmatlit Publ., 2009, 287 p.
9. Kuchuganov A.V. The cognitive algorithm of constructing of geometrical skeleton of nonconvex
   figures. Privolzhsky Scientific J. N. Novgorod, NNGASU Publ., 2012, no. 3, pp. 84–89 (in Russ.).
10. Kasimov D.R., Kuchuganov A.V., Kuchuganov V.N., Oskolkov P.P. Approximation of color images based on the clusterization of the color palette and smoothing boundaries by splines and arcs. Programming and Computer Software. Pleiades Publ., 2018, vol. 44, no. 5, pp. 295–302. DOI: 10.1134/S0361768818050043.