Распознавание структуры графических изображений блок-схем
Разработана модель представления и алгоритм синтаксического анализа и распознавания структур графических изображений блок-схем. Обоснована целесообразность развития нейросетевых методов распознавания. Розроблена модель представлення та алгоритм синтаксичного аналізу та розпізнавання структур графічн...
Saved in:
| Published in: | Комп’ютерні засоби, мережі та системи |
|---|---|
| Date: | 2017 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2017
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/131513 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Распознавание структуры графических изображений блок-схем / Е.Н. Чичирин // Комп’ютерні засоби, мережі та системи. — 2017. — № 16. — С. 87-96. — Бібліогр.: 3 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859611843235938304 |
|---|---|
| author | Чичирин, Е.Н. |
| author_facet | Чичирин, Е.Н. |
| citation_txt | Распознавание структуры графических изображений блок-схем / Е.Н. Чичирин // Комп’ютерні засоби, мережі та системи. — 2017. — № 16. — С. 87-96. — Бібліогр.: 3 назв. — рос. |
| collection | DSpace DC |
| container_title | Комп’ютерні засоби, мережі та системи |
| description | Разработана модель представления и алгоритм синтаксического анализа и распознавания структур графических изображений блок-схем. Обоснована целесообразность развития нейросетевых методов распознавания.
Розроблена модель представлення та алгоритм синтаксичного аналізу та розпізнавання структур графічних зображень блок-схем. Обґрунтовано доцільність розвитку нейромережевих методів розпізнавання.
A model of representation and an algorithm for syntactic analysis and recognition of graphic block diagrams are developed. The expediency of development of neural network recognition methods is substantiated.
|
| first_indexed | 2025-11-28T12:08:55Z |
| format | Article |
| fulltext |
Комп’ютерні засоби, мережі та системи. 2017, № 16 87
E.N. Chichirin
RECOGNITION OF THE
STRUCTURE OF GRAPHIC
IMAGES OF BLOCK SCHEMES
A model of representation and an
algorithm for syntactic analysis and
recognition of graphic block diag-
rams are developed. The expediency
of development of neural network
recognition methods is substan-
tiated.
Key words: syntactic analysis,
recognition, neural networks.
Розроблена модель представлення
та алгоритм синтаксичного
аналізу та розпізнавання струк-
тур графічних зображень блок-
схем. Обґрунтовано доцільність
розвитку нейромережевих методів
розпізнавання.
Ключові слова: синтаксичний ана-
ліз, розпізнавання, нейромережі.
Разработана модель представле-
ния и алгоритм синтаксического
анализа и распознавания струк-
тур графических изображений
блок-схем. Обоснована целесооб-
разность развития нейросетевых
методов распознавания.
Ключевые слова: синтаксический
анализ, распознавание, нейросети.
Е.Н. Чичирин, 2017
УДК 004.932
Е.Н. ЧИЧИРИН
РАСПОЗНАВАНИЕ СТРУКТУРЫ
ГРАФИЧЕСКИХ ИЗОБРАЖЕНИЙ
БЛОК-СХЕМ
Введение. Работа с графическими изображе-
ниями является важным элементом практи-
чески любых современных систем автомати-
зированного проектирования, управления и
документооборота. Основные результаты,
полученные в области технического зрения и
нейросетевой, в том числе глубокой обработ-
ки изображений, связаны прежде всего с
улучшением их качественных характеристик
или распознаванием классов принадлежно-
сти присутствующих на них объектов.
За исключением многочисленных про-
грамм идентификации лиц освещаемые в от-
крытой печати работы редко затрагивают
исследования семантической составляющей
распознаваемых изображений, заключенной
в его структуре, т. е. взаимоотношениях
представленных на изображении объектов.
Сцены из реального мира требуют значи-
тельных затрат на разработку и реализацию
узкоспециализированных систем техниче-
ского зрения. Унификация и ускорение про-
ектирования подобных систем в последнее
время связано с применением глубоких ис-
кусственных нейронных сетей (ИНС), на-
пример, для автономных роботов и в качест-
ве автопилотов различных транспортных
средств.
Основные сложности в случае нейросете-
вого распознавания переносятся на подго-
товку обучающих и тестовых множеств при-
меров и частично на достаточно длительный
процесс машинного обучения. При этом рас-
познавание и локализация объектов произ-
водятся в рамках перемещаемого окна с
Е.Н. ЧИЧИРИН
Комп’ютерні засоби, мережі та системи. 2017, № 16 88
последующим анализом сцен одним из стохастических или синтаксических ме-
тодов. Причем, с увеличением площади окна затраты на обучение и реализацию
ИНС распознавания очень сильно возрастают, а на последующий анализ – уме-
ренно уменьшаются.
Применительно к автоматизированным системам обработки технической, в
том числе патентной документации анализ структур блок-схем (БС) возможен
на уровне отрезков линий и их соединений, или объектов-фигур, связывающих
их отрезков линий и их соединений. В силу ограниченности длины линий и ва-
риантов их соединений лишь размерами всего изображения количество выходов
и размер классифицирующей их ИНС, был бы нереально большим для совре-
менных технологий. Такие схемы человеческий мозг распознает по частям, а
потом "сшивает" и делает это медленнее, чем распознает сцены реального мира
из-за отсутствия профессионального и "эволюционного" опыта.
При этом схожий (радиально ориентированный) характер соединений от-
резков линий БС позволяет реализовать альтернативный обучаемому нейросете-
вому распознаванию таких узлов метод последовательного сравнения с набором
эталонных радиус-векторов. Данных подход предполагает более высокую ито-
говую производительность распознавания, а обучаемыми (адаптируемыми) па-
раметрами остаются, возможно, пороги сравнения с эталонами.
С другой стороны, развитие "правополушарных" нейросетевых методов
вскоре позволит применять их и на этапе "левополушарного" лингвистического
анализа, как это происходит в системах перевода от Google и Microsoft. Во вся-
ком случае, скорость и точность адаптации ИНС в новых областях приложений,
как минимум, сравнима с человеческой.
В конечном итоге, далее рассматриваются вариант выделения атомарных
структурных примитивов – узлов межсоединений отрезков линий путем сравне-
ния их с заранее сгенерированным эталонными векторами. По ходу изложения
указывается на возможность реализации этапа распознавания первичных прими-
тивов нейросетевыми методами. Окончательный синтаксический анализ итого-
вой структуры БС выполняется на основе общих для обоих подходов правил
грамматического разбора.
Постановка задачи и соглашения. В рамках настоящего исследования
ставится и решается задача локализации, и идентификации графических эле-
ментов (далее – фигур), их связей и приписанных им текстовых строк в изо-
бражениях блок-схем, необходимых для последующего адекватного семанти-
ческого анализа БС.
Источник исходных данных – двумерные изображения Image (x, y) или вы-
деляемые их части, отображаемые в произвольном графическом формате сис-
темными средствами на экране монитора компьютера:
- интернет файл или локальный файл с изображениями;
- внешняя программа захвата (capture) реальных изображений;
- синтезируемые (тестовые, обучающие) ненагруженные текстом скелетные
графы БС.
Выход – структурированный текстовой файл.
РАСПОЗНАВАНИЕ СТРУКТУРЫ ГРАФИЧЕСКИХ ИЗОБРАЖЕНИЙ БЛОК-СХЕМ
Комп’ютерні засоби, мережі та системи. 2017, № 16 89
Словарь базовых фигур БС включает основные автофигуры Microsoft Of-
fice и Visio: прямоугольник, ромб, параллелограмм, окружность, эллипс (овал)
и т. п.
Необходимыми и достаточными ограничениями на графическое изображе-
ние БС на входе детерминированной (не стохастической) процедуры распозна-
вания ее структуры являются:
- замкнутость выпуклых контуров фигур, отсутствие внутренних от них от-
водов и стрелок на контурных линиях;
- отсутствие циклов в линиях связи фигур и их объединениях;
- линии связи (со стрелками или без них) должны быть вертикальными или
горизонтальными, заканчиваться в вершинах ромбовидных фигур предикатов
или на сторонах остальных фигур и не являться прямолинейными продолже-
ниями сторон этих фигур;
- отсутствие разрывов в любых линиях и в точках их соединениях более за-
данного порога rS пикселей и расстояние между различными линиями не менее
1+rS пикселей.
Вышеперечисленные ограничения являются типовыми для начертания
БС алгоритмов. Более того, формально допускаются связи между фигурами
типа сходящихся и расходящихся деревьев (без образования сходящихся раз-
ветвлений) для отображения параллельных процессов, например, в электрон-
ных схемах.
Модель процесса распознавания. В силу конечности числа элементов изо-
бражения БС из-за очевидных ограничений на его размеры правила синтаксиче-
ского его разбора могут быть представлены регулярной грамматикой или конеч-
ным автоматом. Однако, учитывая специфику постановки задачи и чрезмерное
количество вариантов БС, для упрощения восстановления и восприятия алго-
ритма распознавания их структуры целесообразно использовать устоявшиеся
программные конструкции в виде стека (или даже динамического массива), т. е.
перейти к модифицированным контекстно-независимым грамматикам и реали-
зующим их магазинным программным автоматам [1, 2].
Программные грамматики отличаются тем, что дополнительно к списку
возможных правил подстановок содержат множество предикатов, определяю-
щих дополнительные условия применения этих правил.
Можно показать, что язык, порождаемый бесконтекстной программной
грамматикой, может быть языком непосредственно составляющих. Более того,
показано, что класс языков, порождаемых бесконтекстными программными
грамматиками, включает все бесконтекстные языки. При этом модифицирован-
ные программные грамматики позволяют описать алгоритм распознавания
структуры БС более привычными программными конструкциями [3].
Далее под синтаксической моделью (грамматикой) БС будем подразумевать
пятерку:
( N , T , J , P , 0N ), (1)
Е.Н. ЧИЧИРИН
Комп’ютерні засоби, мережі та системи. 2017, № 16 90
где N , T , J , P – соответственно конечные множества вспомогательных пе-
ременных (нетерминальных символов), терминальных графических символов,
меток предикатов и правил подстановки; NN ∈0 – начальный символ.
Множество T терминальных графических символов – это объединение ко-
нечных множеств непроизводных графических символов V , производных от
них символов фигур TF , связей между фигурами TC и ассоциированных с фи-
гурами и связями слов текста TW
TTT WCFVT ∪∪∪= . (2)
В процессе распознавания БС в ассоциированных с TF , TC , TW упорядо-
ченных множествах F , C , W сохраняются списки текстовых атрибутов, пред-
ставляющих порядковые (по ходу распознавания) номера соответственно фи-
гур, объединений линий связи и блоков слов, а также их тип, сигнатуры и про-
странственные координаты принадлежащих им узлов на плане Img(x, y) изо-
бражения БС. Большая часть текстовых атрибутов в виде отчета сохраняется в
выходном текстовом файле.
Множество V вспомогательных непроизводных графических символов вы-
бирается из условия простоты их выделения на изображении БС до начала соб-
ственно структурного анализа. С другой стороны, это множество должно обес-
печивать возможность (желательно наиболее простым способом) структурной
композиции из него множеств TF терминальных фигур и TC – связей между
ними. Применительно к БС в качестве V выбрано множество из k радиус-
векторов iR единичной (условно) длины с различной ориентацией на поле изо-
бражения, кратной постоянному шагу k/2π=ϕ∆ их угла поворота против ча-
совой стрелки относительно начального угла 0ϕ :
}1,0|{ −== kiRV i ,
kikii /360/2 ∗=∗π=ϕ , (3)
},,0|),{( ryxR iii == ννν
где rRyx iii ,1,),( =ν∈νν и ),( 00
ii yx – координаты r точек вектора относительно
центра вращения и очередного центра вращения в направлении луча iR .
Последовательное сканирование конкатенирующих цепочек (конфигураций)
элементарных отрезков (лучей) БС, сравнение их с эталонами из V и дальней-
шие морфологические преобразования позволяют получить их сигнатуры Z –
компактные представления о пространственном расположении, типе и связях
фигур из TF и объединений связей из TC , инвариантные при необходимости к
операциям масштабирования, сдвига и вращения.
При нейросетевом подходе последовательная классификация и локализация
точечных соединений элементарных отрезков, в том числе многолучевых, про-
РАСПОЗНАВАНИЕ СТРУКТУРЫ ГРАФИЧЕСКИХ ИЗОБРАЖЕНИЙ БЛОК-СХЕМ
Комп’ютерні засоби, мережі та системи. 2017, № 16 91
изводится с помощью сверточной ИНС, предварительно обученной на множе-
стве примеров таких соединений.
Множество TF терминальных символов составляют основные фигуры БС.
Полный текстовый эквивалент фигуры FFg ∈θ включает порядковый (по ходу
процесса распознавания) номер фигуры g , ее тип θ : 1 – прямоугольник, 2 –
ромб, 3 – параллелограмм, 4 – эллипс (овал) и т.п., адресные ссылки (координа-
ты на плане БС) на принадлежащие им узлы соединений контурных линий, а
также входные и выходные узлы линий связи с другими фигурами.
В множество TC терминальных символов по мере распознавания включа-
ются разнообразные конфигурации (от одиночных до разветвленных древовид-
ных) объединений линий связи фигур. Аналогично θ
gF атрибуты CCu ∈θ со-
держат их тип θ (одно- или двунаправленный), порядковый номер u и коорди-
наты узлов соединений линий связи внутри данного объединения и с контурны-
ми линиями фигур.
Множество TW ассоциированных с фигурами и связями слов текста пред-
ставляют вторую семантическую составляющую БС (после иерархии связей).
Координаты текста для дальнейшего его распознавания определяются по конту-
рам фигур и расположению выходных узлов предикатов.
Множество P правил подстановки – это множество продукций вида
β→α , ∈βα, N ∪ ∗
TF ∪ ∗
TC ∪ ∗
TW , (4)
где N ∪ ∗
TF ∪ ∗
TC ∪ ∗
TW – объединение конечных множеств всевозможных
цепочек символов соответственно из N , TF , TC , TW и α содержит по край-
ней мере один символ из N . Выражение (4) задает возможные варианты разви-
тия процесса последовательного дополнения правых частей β продукций до
финального графического ∗
TF ∪ ∗
TC ∪ ∗
TW и далее соответственно текстового
F , C , W описания БС в зависимости от его текущего состояния α .
Множество J номеров (меток) предикатов задают дополнительные к P ус-
ловия их применения, вычисления координат и других атрибутов элементов БС,
а также служат для организации эффективных, не переборных процедур алго-
ритма распознавания. Следует отметить, что реализация правил подстановки из
P на программном уровне выполняется теми же средствами, что и реализация
предикатов из J .
В итоге, совокупный анализ – распознавание структуры двумерного об-
раза БС с учетом грамматики его построения и для получения его формали-
зованного текстового описания F , C , W представляется в виде рекурсивной
процедуры обновления выходного предложения из терминальных символов
( ∗
NF , ∗
TF , ∗
TC ), вспомогательных переменных из N и атрибутов из F , C , W
Е.Н. ЧИЧИРИН
Комп’ютерні засоби, мережі та системи. 2017, № 16 92
путем применения к его текущему значению правил подстановки P и совокуп-
ности предикатов J .
( F , C , W , N , ∗
TF , ∗
TC , ∗
TW ) 1−t ⇒
JP,
( F , C , W , N , ∗
TF , ∗
TC , ∗
TW ) t . (5)
По своей сути, правила подстановки из P на каждом шаге рекурсивной
процедуры распознавания БС определяют возможные варианты ее дальнейшей
структуры, например, после контура фигуры могут идти линии связи с другими
фигурами, а потом контур этих фигур.
Таким образом, генеративные методы распознавания, к которым можно от-
нести структурное распознавание (структуры БС), на основании синтаксическо-
го анализа правильности построения последней позволяют разделить входные
изображения на "правильные " БС и "неправильные" БС. При сохранении соот-
ветствующего формализма структурных алгоритмов распознавания они могут, в
отличие от дискриминантных методов, использоваться для генерации множества
( например, обучающего) различных новых БС.
В то же время, в чистом виде без дополнительных средств фиксации прямых
и производных количественных, качественных параметров анализируемой или
генерируемой структуры эти методы не дают информации о ее конкретных ха-
рактеристиках и семантической составляющей. Именно расширение (4) до (5)
за счет введения атрибутов F , C , W и предикатов J для их обработки обеспе-
чивает эти возможности.
Алгоритм синтаксического разбора структуры блок-схем.
Предварительные определения и замечания.
1. Графическое изображение БС (возможно после удаления шумов, выделе-
ния контуров и т. п.) – это ориентированный (возможно частично) связный на-
груженный текстом граф ),( ΕΦΓБС с множеством вершин Φ и ребер Ε . В силу
принятых выше ограничений, ребра графа образуют замкнутые, возможно дуго-
образные контуры фигур gF БС и древовидные объединения uC линий связи
между контурами, вершины – узлы соединений линий контуров и линий связи.
2. Продвижение сканера по ребрам и узлам графа осуществляется по коор-
динатам очередных центров ),( 00
ii yxO кругового сканирования ),( 00
ii yx⊕ воз-
можных продолжений, поворотов и разветвлений (лучей), получаемых путем
сравнения (с заданным порогом δ ) локальной области БС с эталонными векто-
рами VRi ∈ с центром в текущей точке ),(* yxO . Если за направление вектора
0ϕ принять направление линии сканируемое из центра вращения, т. е. обратное
направлению продвижения по этой линии, то при 24=k возможны, например,
следующие варианты круговых диаграмм (здесь и далее для лучей линий изо-
бражения используются обозначения ближайших эталонных радиус-векторов):
- однолучевая 12R , 6R – начало и 0R окончание текущей линии;
РАСПОЗНАВАНИЕ СТРУКТУРЫ ГРАФИЧЕСКИХ ИЗОБРАЖЕНИЙ БЛОК-СХЕМ
Комп’ютерні засоби, мережі та системи. 2017, № 16 93
- двухлучевые: 120 , RR – продолжение текущей линии; 60 , RR – узел связи
текущей линии с другой линией под прямым углом; 310 , RR – возможное ис-
кривление текущей линии влево;
- трехлучевые: 1860 ,, RRR – узел соединения текущей линии с другой лини-
ей связи или фигуры под прямым углом; 1260 ,, RRR – узел объединения линий
связи или контура фигуры с отводом вправо; 1680 ,, RRR – узел соединения те-
кущей линии предположительно с вершиной фигуры предиката (ромба);
- четырехлучевые: 181260 ,,, RRRR – пересечение без соединения или кре-
стообразное соединение, в зависимости от принятых соглашений и наличия
стрелок на линиях связи;
- пятилучевые: 127650 ,,,, RRRRR – узел с входом стрелки справа и т. д.
3. Последовательность по возрастанию значений индексов лучей, в которой
вместо нулевого значения индекса при 0R , храниться его абсолютное значение
ϕ∆ϕ= /00i относительно оси X , будем называть сигнатурой узла ρ
ρ = iiizq ...10 ,
где ρ– количество лучей узла q . Сигнатура позволяет классифицировать узлы
по типам: вход, выход, поворот левый, правый, отвод и т. д. относительно ис-
ходных лучей 0R линий связи, и без 0i инвариантна к ориентации 0R . Для
классификации симметричных пар лучей стрелок, имеющих 4 возможные ори-
ентации, используется абсолютная сигнатура ρ
ρ iiizq ...10= , ϕ∆+= iii 0 .
4. Сканирование против часовой стрелки конкатенирующих цепочек линий
контуров фигур позволяет получить координаты узловых точек qυ , изменение
максимальных индексов maxi лучей в которых по сравнению с предыдущим уз-
лом *υ превышает пороговое значение iiii qq ∆>−+ *
0max0 . При записи контура
некоторой фигуры в виде цепочки из индексов maxi его узлов, начиная с крайне-
го верхнего левого узла )|( minmin yxqυ , получаемая сигнатура, например, ромба
– 162016204 =gZ , инвариантная к масштабированию и сдвигу фигуры, исполь-
зуется для сравнения с эталонными значениями или их вариантами.
Предлагаемый алгоритм синтаксического разбора структуры БС предпола-
гает рекурсивный обход по направлениям выделенных в узлах лучей всех вет-
вей дерева текущего объединения uC , включая его листья – замкнутые контуры
предполагаемых фигур gF .
С учетом принятых выше ограничений и замечаний алгоритм распознавания
структуры БС строится следующим образом.
Е.Н. ЧИЧИРИН
Комп’ютерні засоби, мережі та системи. 2017, № 16 94
0. Выполняется инициализация координат начального узла ),(0 yxq υυ =
0,0 == yx , указателей вершин стеков StI и StO , номера текущей фигуры
0=g и объединения связей 1=u , очищается память атрибутов F , C , W , ме-
ток 0=m и т. п. Алгоритм переводится в состояние 1=S поиска первого узла
объединения 1CCu = . Переход на п. 1.
1. Путем построчного анализа пикселей прошедшего предобработку плана
БС находится крайняя верхняя левая черная точка – центр первого узла для кру-
гового сканирования. Эта часть алгоритма имитирует продвижение по началь-
ной (виртуальной) линии связи 0L до узла ),(1 yxυ ее соединения с некоторой
линией 1L связи или контура фигуры. Переход на п. 2.
2. Выполняется круговое сканирование возможных направлений 1
iR для
дальнейшего продвижения сканера. Если текущий узел uq Cyx ∉),(υ , т. е.
umq ≠ ,.переход на п. 3, иначе сообщение "Цикл в uC !" и переход на п. 12.
3. Если 1−=qm , то узел ),( yxqυ попадает в uC и получает метку umq = .
Переход на п. 9, иначе – на п. 4.
4. Если 0=qm , то лучи ),( yxR q
q
i υ∈ с координатами узлов сохраняются в
C , получают метку umq = и ссылку на плане БС. Поиск по дереву uC осуще-
ствляется в глубину по узлам qυ , справа налево по возрастанию индексов qi
лучей (опционально, с выделением приоритетного прямого направления
12=di ). Соответственно, загрузка индексов в стек StI с ссылкой на их роди-
тельский узел – по убыванию значений qi с предварительным инкрементом ука-
зателя стека iqStI ,←+ . Лучи с симметричными индексами стрелок получают
метку "вход" и удаляются из дальнейшего рассмотрения. Индекс qimin использу-
ется для продолжения сканирования без его загрузки в стек. Переход на п. 5.
5. Необходимым условием (признаком) вхождения в стартовый узел sυ и
перехода на п. 6 – начало обхода контура предполагаемой фигуры gF является
его трехлучевая (после удаления стрелок) без прямого луча сигнатура
210
3 iiizq = , 3)12( szi ∉= , иначе возврат на п. 2.
6. Обход начинается с правого mini индекса узла sυ и продолжается против
часовой стрелки по левым maxi индексам последующих узлов. Выделяемые лучи
с координатами узлов контура сохраняются в F и C , получают метку 1−=m и
ссылку на плане БС. Индексы mini внешних правых отводов с ссылками на их
РАСПОЗНАВАНИЕ СТРУКТУРЫ ГРАФИЧЕСКИХ ИЗОБРАЖЕНИЙ БЛОК-СХЕМ
Комп’ютерні засоби, мережі та системи. 2017, № 16 95
родительские узлы помещаются в стек iqStO ,←+ . По вторым индексам сиг-
натур узлов формируется сигнатура контура q
gg iZZ 1+= . Переход на п. 7.
7. Так как ветви дерева связей uC имеют конечное число узлов и заканчи-
ваются листьями контуров фигур gF с конечным числом узлов, то при обходе
контура предполагаемой фигуры за число шагов maxηη ≤ , где maxη – макси-
мальное количество узлов у фигуры Tg FF ∈ или ветви дерева uC , возможны
следующие продолжения, достаточные для успешного завершения алгоритма:
- переход на п. 8 для классификации контура по gZ в случае попадания в
стартовый узел sq υυ = ;
- откат к узлу 1+= sq , umq = , )(Czz qq = и продолжение обхода дерева
uC начиная с п. 5 в случае попадания в узлы с сигнатурами: ρ
qz , 5≥ρ или
5
qz , 11 =i , 234 =i (недопустимая стрелка на линии контура), 3210
4 iiiizq = , (не-
допустимое пересечение контура другой линией), 210
3 iiizq = , 3)12( szi ∉= (не-
допустимый не горизонтальный и не вертикальный }18,12,6,0{)( min0 ∉+ ii , или
являющийся продолжением линии maxi контура 12minmax =− ii правый отвод
связи), 10
2 iizq = , ii ∆>1 (недопустимый не выпуклый с правым поворотом
контур), 0
0 izq = (недопустимый обрыв линии контура);
- выход из цикла распознавания контура с сообщением " maxηη > – нет кон-
тура, превышение длины линии" и переход на п. 12;
- иначе – переход на п. 6, продолжение сканирования контура.
8. Классификация контура выполняется путем сравнения формируемой по
его узлам сигнатуры gZ с возможными эталонными значениями (для фигур с
нелинейными очертаниями). В случае успеха, номер и тип фигуры с указанием
входов (со стрелками) и выходов сохраняются в F и переход на п. 9, иначе вы-
водится сообщение о недопустимом контуре в БС и переход на п. 12.
9. Если стек StI не пуст, из него выбирается отложенный индекс и ссылка
на родительский узел −← StIiq, для продолжения поиска ветвей и контуров
фигур-листьев uC с переходом на п. 2, иначе переход на п. 10.
10. Если стек StO не пуст, индекс первого с меткой 1−=m узла из StO
используется в качестве начального для распознавании очередного объединения
1+uC , −← StOiq, , 1+= uu , ,0=m и переход на п. 2, иначе – на п. 11.
11. Обработка атрибутов fFile ← ( F , C ,W ). Переход на п. 12.
12. Конец алгоритма.
Е.Н. ЧИЧИРИН
Комп’ютерні засоби, мережі та системи. 2017, № 16 96
Использование для накопления и отложенной обработки лучей текущего
объединения ui CR ∈ внутреннего стека StI , а для лучей ui CR ∉ , выделяе-
мых при обходе листьев контуров фигур – внешнего StO позволяет ранжиро-
вать и упростить последующую сортировку множеств F и C . Эффективная ор-
ганизация распознавания БС без применения стеков возможна за счет организа-
ции списковых структур непосредственно в памяти плана изображения.
Описанная последовательность шагов является алгоритмом распознавания
структур БС, удовлетворяющих ограничениям 1 – 4.
В силу определения (п. 1) графовой структуры изображения БС, использо-
вание классических процедур обхода деревьев связей uC в глубину – по стеку
StI и в ширину по стеку StO гарантирует перебор всех вершин (узлов) и ребер
(линий связи) графа БС. Возможные дублирования обходов контуров устраня-
ются с помощью механизма меток.
Правильная классификация контуров "правильной" БС (удовлетворяющей
принятым ограничениям) обеспечивается выполнением необходимых и доста-
точных шагов алгоритма (соответственно п. 5 и п. 7, 8), гарантирующих выход
из процесса распознавания псевдоконтура при первом же входе в настоящий
контур фигуры.
Классификация БС, как содержащая ошибки, сопровождается выдачей по-
ясняющих сообщений, кроме случая отказа от распознавания из-за лимита вре-
мени 10max ≈η , который также можно отнести к разряду "неправильной" БС.
Исключением, требующим повышенный лимит, может быть вхождение в длин-
ный псевдоконтур левоповоротной спирали возможно с правосторонними отво-
дами, что совершенно не характерно для реальных БС. Основные погрешности
в работу алгоритма могут вносить технологические особенности процессов ска-
нирования и отчасти, сигнатурной классификации криволинейных фигур.
Выводы. Построена расширенная модель представления и разработан ал-
горитм синтаксического анализа и распознавания структуры графических изо-
бражений блок-схем. Получены подтверждения эффективности и целесообраз-
ности дальнейшего исследования синтаксических методов распознавания струк-
тур БС. Отмечается недостаточная достоверность классификации первичных для
структурного анализа узлов связи прежде всего за счет сложности позициониро-
вания эталонов. Целесообразно проведение альтернативных исследований ре-
шения этой задачи обучаемыми нейросетевыми методами.
1. Палагин А.В., Семотюк М.В., Чичирин Е.Н., Сосненко К.П. Моделирующая среда для
создания и отладки систем цифровой обработки. УСиМ. 2013. № 1. С. 42–45.
2. Фу К. Структурные методы в распознавании образов. М.: Мир, 1977. 320 с
3. Хант Э. Искусственный интеллект. М.: Мир, 1978. 560 с.
Получено 05.09.2017
E.N. Chichirin
Е.Н. Чичирин
Алгоритм синтаксического разбора структуры блок-схем.
|
| id | nasplib_isofts_kiev_ua-123456789-131513 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1817-9908 |
| language | Russian |
| last_indexed | 2025-11-28T12:08:55Z |
| publishDate | 2017 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Чичирин, Е.Н. 2018-03-23T19:40:03Z 2018-03-23T19:40:03Z 2017 Распознавание структуры графических изображений блок-схем / Е.Н. Чичирин // Комп’ютерні засоби, мережі та системи. — 2017. — № 16. — С. 87-96. — Бібліогр.: 3 назв. — рос. 1817-9908 https://nasplib.isofts.kiev.ua/handle/123456789/131513 004.932 Разработана модель представления и алгоритм синтаксического анализа и распознавания структур графических изображений блок-схем. Обоснована целесообразность развития нейросетевых методов распознавания. Розроблена модель представлення та алгоритм синтаксичного аналізу та розпізнавання структур графічних зображень блок-схем. Обґрунтовано доцільність розвитку нейромережевих методів розпізнавання. A model of representation and an algorithm for syntactic analysis and recognition of graphic block diagrams are developed. The expediency of development of neural network recognition methods is substantiated. ru Інститут кібернетики ім. В.М. Глушкова НАН України Комп’ютерні засоби, мережі та системи Распознавание структуры графических изображений блок-схем Recognition of the structure of graphic images of block schemes Article published earlier |
| spellingShingle | Распознавание структуры графических изображений блок-схем Чичирин, Е.Н. |
| title | Распознавание структуры графических изображений блок-схем |
| title_alt | Recognition of the structure of graphic images of block schemes |
| title_full | Распознавание структуры графических изображений блок-схем |
| title_fullStr | Распознавание структуры графических изображений блок-схем |
| title_full_unstemmed | Распознавание структуры графических изображений блок-схем |
| title_short | Распознавание структуры графических изображений блок-схем |
| title_sort | распознавание структуры графических изображений блок-схем |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/131513 |
| work_keys_str_mv | AT čičirinen raspoznavaniestrukturygrafičeskihizobraženiiblokshem AT čičirinen recognitionofthestructureofgraphicimagesofblockschemes |