ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

2
Publication date:
16 June 2024

A simplified method for skeletonization of non-convex figures

Date of submission article: 19.02.2019
UDC: 004.81 (004.9)
The article was published in issue no. № 3, 2019 [ pp. 384-388 ]
Abstract:The approximation of graphic information through the skeletonization of object images is a way to re-place objects with simpler and more convenient representations in semantic analysis problems and im-age recognition. Skeletons are widely used in technical vision systems, content image search, in geo-metric modeling and visualization. The most popular approaches: based on “erosion” (removal of ob-ject boundary points) and mathematical (based on Voronoi diagrams formed by Delaunay triangula-tion, inscribing circles or using the wave method). A common disadvantage of the existing skeleton building algorithms is the loss of information about the width of the original figure sections, which is often necessary in image recognition and description tasks. The paper proposes an approach that follows the previously published method of skeletalization based on heuristic rules and consists in the sequential cutting off of figure segments with minimal chords in places where the border of the figure has a negative inflection when it is counterclockwise. Then segments are constructed connecting the midpoints of the chords of adjacent segments. The seg-ments are combined into chains that form a nonconvex figure skeleton. In this case, the lengths of the obtained chords carry information about a figure width in the corresponding sections. The experiments were related to two subject areas: processing scanned archival drawings of parts of a general engineering application to use previously gained experience in designing new products and reducing the overall design time and technological preparation of production, as well as the problem of recognizing a continuous handwritten text in the off-line mode.
Аннотация:Аппроксимация графической информации путем скелетизации изображений объектов применяется для замены объектов более простыми и удобными представлениями в задачах семантического анализа и распознавания изображений. Скелетоны широко используются в системах технического зрения, контентного (содержательного) поиска изображений, в геометрическом моделировании, визуализации. Наиболее популярные подходы: на основе эрозии – удаления краевых точек объекта и математический – на основе диаграмм Вороного, формируемых путем триангуляции Делоне, вписывания окружностей или с помощью волнового метода. Общий недостаток существующих алгоритмов построения скелетона – потеря информации о ширине участков исходной фигуры, которая часто бывает необходима в задачах распознавания и описания изображений. В работе предлагается подход, который является развитием метода скелетизации на основе эвристических правил и заключается в последовательном отсечении сегментов фигуры минимальными хордами в таких местах, где граница фигуры имеет отрицательный перегиб при обходе ее против часовой стрелки. Строятся отрезки, соединяющие середины хорд соседних сегментов. От-резки объединяются в цепочки, которые и образуют скелетон невыпуклой фигуры. При этом длины полученных хорд несут информацию о ширине фигуры на соответствующих участках. Эксперименты проводились в двух предметных областях: при обработке сканированных архивных чертежей деталей общемашиностроительного применения с целью использования ранее накопленного опыта при проектировании новых изделий и сокращения общего времени проектирования и технологической подготовки производства, а также в задаче распознавания слитного рукописного текста в автономном режиме.
Authors: A.V. Kuchuganov (Aleks_KAV@udm.ru) - Kalashnikov Izhevsk State Technical University (Associate Professor), Izhevsk , Russia, Ph.D
Keywords: skeleton, secant chord, nonconvex polygon, border, color segmentation, raster image
Page views: 3888
PDF version article

Font size:       Font:

Аппроксимация графической информации путем скелетизации применяется для замены объектов более простыми и удобными представлениями в задачах семантического анализа и распознавания. Скелетоны широко используются в системах технического зрения, в геометрическом моделировании, визуализации. На сегодняшний день известны более 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). Вначале секущие строятся в местах, где имеется  

Рис. 2. Увеличение степени детализации

Fig. 2. Increasing the level of detail
существенный отрицательный перегиб границы, например, более 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.

Permanent link:
http://swsys.ru/index.php?page=article&id=4614&lang=en
Print version
The article was published in issue no. № 3, 2019 [ pp. 384-388 ]

Perhaps, you might be interested in the following articles of similar topics: