Содержание к диссертации
Введение
ГЛАВА I. Задачи кусочно-линейной аппроксимации и анализа графических изображений 9
1.1. Задачи кусочно-линейной аппроксиглациїї графических изображений 10
1.2. Задачи структурного анализа графических изображений 17
ГЛАВА II. Кусочно-линейная аппроксшладия последовательностей точек на плоскости 28
2.1. Основные определения и постановка, задачи 29
2.2. Решение оптимизационной задачи 33
2.3. Алгоритмы оптимальной атгроксимации 39
2.4. Исследование алгоритмов 45
2.5. Быстродействующий однопроходный алгоритм кусочно- линейной атгроксимации последовательностей точек на плоскости 50
ГЛАВА III. Структурный анализ изображений с помощью звездных конструкций 60
3.1. Представление изображений звездочками 60
3.2. Звездные конструкции. Общее определение и постановка задачи анализа 69
3.3. Алгоритмы анализа изображений на основе звездных конструкций 76
3.4. Исследование алгоритмов 92
3.5. Разновидности звездных конструкций 97
ГЛАВА ІV. Решение практических задач обработки и анализа изображений 103
4.1. Система ввода и обработки графической информации 103
4.2. Практическая реализация однопроходного алгоритма кусочно-линейной аппроксимации (алгоритма 2.3) 112
4.3. Экспериментальная система анализа изображений блок-схем логических устройств... 124
ЗАКЛЮЧЕНИЕ 169
СПИСОК ЛИТЕРАТУРЫ 172
ПРИЛОЖЕНИЕ 184
- Задачи кусочно-линейной аппроксиглациїї графических изображений
- Основные определения и постановка, задачи
- Представление изображений звездочками
- Система ввода и обработки графической информации
Введение к работе
В последние годы методы автоматической обработки и анализа графических изображений находят широкое применение во многих областях науки, техники и производства. В число таких областей входят автоматизация проектирования, медицина, биология, робототехника, приборостроение и другие. Например, в системах автоматизированного проектирования изделий электронной техники применение методов обработки изображений позволяет заменить традиционные полуавтоматические устройства кодирования автоматическими, что ускоряет процесс ввода изображений проектируемых схем в ЭВМ в десятки раз и значительно уменьшает количество допускаемых при этом ошибок. Создание систем ввода и анализа изображений занимает центральное место в робототехнике - отрасли, развитию которой прида -ется большое значение в последних постановлениях партии и правительства.
Високая актуальность, а также большой чисто научный интерес обусловили бурный рост работ в области обработки графических изображений.
Одними из основных возникающих здесь задач являются задачи кусочно-линейной аппроксимации графических изображений и последующего их структурного анализа. Первая имеет своей целью получение представления изображения в виде прямолинейных отрезков на плоскости, а вторая - построене структурного описания полученного множества отрезков. На сегодняшний день в обоих налравле -ниях имеется достаточно много работ, в которых решаются различные конкретные прикладные задачи. Дальнейший рост количества этих работ вызывает необходимость в рассмотрении более общих постановок задач кусочно-линейной аппроксимации и структурного анализа графических изображений и разработке универсальных методов -.5-их решения. Наряду с этим, важным является также создание новых быстродействующих, эффективных алгоритмов аппроксимации и анализа графических изображений и их практическая реализация.
Таким образом, из вышеизложенного следует, что создание и практическая реализация новых методов кусочно-линейной аппроксимации и структурного анализа графических изображений является актуальной задачей.
Целью настоящей диссертационной работы является.
Постановка и точное решение оптимизационной задачи кусочно-линейной аппроксимации последовательностей точек на плоскости, а также разработка, исследование и практическая реализация быстродействующих алгоритмов аппроксимации.
Создание универсальной конструкции для анализа графических изображений, а также разработка, исследование и экспериментальная проверка соответствующих алгоритмов анализа.
Методика исследования. В диссертации используется аппарат теории множеств, методы динамического программирования, теории двумерных грамматик, а также экспериментальная проверка программ.
На защиту выносятся.
Новая постановка задачи кусочно-линейной аппроксимации графических изображений в виде двухкритериальной оптимизационной задачи.
Точное решение поставленной задачи методами динамического программирования.
Алгоритмы аппроксимации, реализующие полученное решение, и оценка их сложности.
Быстродействующий однопроходный алгоритм кусочно-линейной аппроксимации последовательностей точек на плоскости.
Практическая реализация алгоритма в системе ввода и об- работки графических изображений.
Универсальная конструкция для анализа графических изображений.
Эффективные алгоритмы анализа графических изображений на основе предложенной конструкции и оценка их сложности.
Практическая ценность работы. Предложенный в работе однопроходный алгоритм кусочно-линейной аппроксимации последовательностей точек на плоскости практически реализован в системе ввода и обработки графической информации, созданной в Институте кибернетики имени В.М.Глушкова АН УССР.
Алгоритм может быть использован в системах обработки изображений как средство для' выделения прямолинейных отрезков на пос -ледовательностях точек плоскости.
На основе разработанной в работе конструкции для анализа графических изображений создана экспериментальная система структурного анализа изображений блок-схем логических устройств. Универсальность конструкции позволяет ее использование при решении и других задач анализа изображений. К ним, например, относятся задачи распознавания рукописных письменных знаков, задачи анализа чертежно-графической информации и т.д. Система ввода и обра -ботки графической информации Института кибернетики имени В.М.Глушкова АН УССР, в которой реализованы результаты настоящей диссертационной работы, успешно прошла Государственные испытания и рекомендована к серийному производству. Система внедрена и эффективно эксплуатируется на ряде предприятий гг.Москвы и Киева, что подтверждается соответствующими актами, копии которых приведены в приложении.
Апробация работы. Основные результаты диссертации доложены на I Всесоюзной конференции "Автоматизированные системы обработ- ки изображений" ( АС0И3 - 81 ), г.Москва,1981г.; I Всесоюзной конференции "Методы и средства обработки сложноструктурированной, семантически насыщенной графической информации", г.Горький, 1983г.; У Всесоюзной конференции "Автоматизация ввода письменных знаков вШМ": г.Каунас, 1984г.; УІ Межреспубликанской школе-семинаре "Интерактивные системы", г.Батуми, 1984г., а также на заседаниях республиканского семинара "Распознавание обра -зов и конструирование читающих автоматов" Научного совета АН УССР по проблеме "Кибернетика" г.Киев, (1980-1984 гг.).
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из наименований и приложения. Объем работы 115 страниц основного текста, 58 страниц рисунков и 33 страниц приложения.
Публикации. Результаты диссертации опубликованы в работах [3] , [12] , [17] - [Зі] .
В первой главе, носящей вводный характер, дается краткий обзор основных результатов и выделяются основные направления работ в области кусочно-линейной аппроксимации и структурного анализа графических изображений. Указывается место настоящего исследования среди известных работ в этой области.
Во второй главе излагаются результаты по кусочно-линейной аппроксимации последовательностей точек на плоскости. Ставится и решается оптимизационная двухкритериальная задача кусочно-линейной аппроксимации.Описываются два алгоритма аппроксимации, реализующих полученное решение для незамкнутых и для замкнутых последовательностей.Приводится расчет сложности алгоритмов а также доказывается оптимальность решения задачи.Предлагается быстро- действующий однопроходный алгоритм аппроксимации, доказывается его оптимальность на одном классе последовательностей и описывается эвристическая процедура уменьшения отклонения при аппрок-оимапии.
В третьей главе приводится описание новой универсальной конструкции для анализа графических изображений. Описывается специфическое преобразование исходного изображения, представленного в віще прямолинейных отрезков в другое представление, пригодное для работы конструкции. Дается определение новой конструкции, названной звездной конструкцией и постановка задачи анализа. Описываются два алгоритма анализа, работающие на основе предложенной конструкции и приводится расчет их сложности. Предлагаются две разновидности звездной конструкции для использования при решении некоторых конкретных задач анализа.
В четвертой главе приводятся результаты решения практических задач обработки и анализа графических изображений. Описывается Система ввода и обработки графической информации Института кибернетики имени В.М.Глушкова Ж УССР. Приводятся иллюстрации работы в составе системы однопроходного алгоритма кусочно-линейной аппро-ксимации. Описывается созданная на основе звездных конструкций экспериментальная система анализа изображений блок-схем логических устройств.
В заключении приводятся основные выводы, полученные в диссертации.
Автор выражает глубокую благодарность своему научному руководителю, кандидату физико-математических наук М.И.Шлезингеру за руководство и внимание, оказанное во время работы над диссертацией, а также сотрудникам руководимого игл отдела за постоянную дружескую поддержку.
Задачи кусочно-линейной аппроксиглациїї графических изображений
Для уяснения смысла и надобности в кусочно-линейной аппроксимации графических изображений нагл придется коротко сказать о предшествующих этапах обработки.
Обычно обработка чертежно-графической информации состоит в том, что на множестве клеток дискретизованного изображения выделяются подашожества, соответствующие линиям на исходном изображении, и подмножества, не являющиеся линиями. Каждое подмножество первого типа заменяется осевой линией, которая, говоря нестрого, описывает путь, пройденный пишущим инструментом при рисовании линии. Точное определение осевой линии и алгоритмы построения осевых можно найти в работах ["23"], [75] , Г?б] и ДР»» их детальное рассмотрение выходит за рамки настоящей работы. Множества второго типа (их еще называют пятнами) описываются в виде совокупности их контуров [із] , [40J . Как осевые, так и контура задаются в виде некоторой конечной последовательностью точек на плоскости, соединенных прямолинейными отрезками. Однако эти отрезки еще далеки от тех, которые на изображении содержательно представляли из себя отрезки прямых. Причиной такого несоответствия является большое количество помех, образуемых при вводе изображения в ЭВМ, которые переходят в контура и осевые. Эти помехи вызваны неточностями рисования, спецификой работы устройства ввода и различными случайными причинами. Выделение осевых линий и контуров представляет из себя лишь экономную перекодировку графического изображения, которая сохраняет всю информацию об изображении, включая и ненужную, вызванную помехами. Для иллюстрации этого факта приведем простой, и в то лее время весьма наглядный пример. Пусть предъявлено изображение треугольника (Рис. 1а). Ясно, что вся информация о нем содержится в координатах трех его вершин. Однако после дискретизации и выделения контура в машину поступит информация не о трех, а о значительно большем числе точек, как, например, на Рис. I б.
Ясно, что хранение информации о треугольнике с помощью такого большого числа точек является не только неэкономным, но просто содержательно неправильным. И, естесственно, говорить о возможности построения какого-либо анализатора, который здесь угадал бы треугольник .бессмысленно. Единственным выходом является подвергнуть изображение специальной обработке, в результате чего вновь выделятся: три отрезка треугольника. Именно такую обработку и призвана осуществлять кусочно-линейная аппроксимация графических изображений.
Основные определения и постановка, задачи
Мы будем рассматривать конечные последовательности точек на плоскости. Могут быть два вида таких последовательностей: незамкнутые (см.Рис.За) и замкнутые, т.е. такие, у которых за последней точкой последовательности следует первая (см.Рис.36).
Для краткости мы их будем называть соответственно незамкнутыми кривыми. Как видно из рисунка, как одни, так и другие являются простыми кривыми, т.е. не содержат самопересечений. Таким об разом, простая незамкнутая кривая- это всякая конечная последо вательность точек плоскости вида .,
Число называется длиной кривой Т. Разбиением /jf при некотором натуральном К незамкнутой кривой / называется всякая ее
Число С называется длиной разбиения /д-. Интересно отметить два случая. При If-Jv разбиение совпадает с исходной кривой , а при У /? кривая Ж представляет из себя отрезок прямой, соединяющий начальную точку кривой / - точку i± с конечной точкой r r . Однако оба этих случая в задаче абсолютно равноправны со всеми промежуточными.
Представление изображений звездочками
Таким образом отношение связности является рефлексивным, симметричным (т.к. симметрично отношение соседства ) и транзитивным отношением на множестве точек Jr . Следовательно 1 3 оно является отношением эквивалентности на множестве точек и однозначно разбивает это множество на непересекающиеся подмножества, которые мы назовем его связными компонентами. При этом для любой пары точек, принадлежащих одной связной компоненте, справедливо отношение связности. Изображения, состоящие только из одной связной компоненты, называются связными изображениями, В дальнейшем для удобства изложения условимся рассматривать только связные изображения. Очевидно, что это не сужает объект, т.к. любые процедуры обработки, применимые к связным изображениям, без труда переносятся на произвольные несвязные изображения. Для этого достаточно лишь применить их последовательно на всех связных компонентах этих изображений. Пользуясь терминологией теории графов [32 J будем говорить, что всякий прямолинейный отрезок инцидентен двум точкам, которые он соединяет. Каждая точка, в свою очередь, инцидента всем отрезкам, соединяющим ее с другими, соседними с ней точками. Точка, вообще говоря, может быть инцидентна произвольному числу отрезков. Однако мы введем на это число, а также на углы наклона отрезков определенные ограничения. Перейдем к описанию средств задания этих ограничений, а также способа представления изображений, удовлеворяющих этим ограничениям. Отметим, что новое представление изображения содергшт в себе определенную избыточность, но переход к нему необходим с точки зрения последующего анализа. Здесь же будут введены часть средств предлагаемой конструкции для анализа изображений, полное определение которой дается в следующем параграфе.
Система ввода и обработки графической информации
В настоящем параграфе приводится краткое описание системы ввода и обработки графической информации, созданной в Институте кибернетики им.В.М.Глушкова АН ycCPJ34j
Система ввода и обработки графической информации предназначена для ввода в ЭШ чертежно-графических документов, представленных в виде чертежей, эскизов, графиков непосредственно на бумажном носителе, а также представлении этих документов в виде, удобном для их экономного хранения, дальнейшей обработки и отображения на графических дисплеях. Система создана для применения при автоматизации проектных, конструкторских, картографических работ, автоматизации создания банков чертежей, а также автоматизации научных исследований. Система представляет из себя аппаратурно-програшшый комплекс. Общий вид системы приведен на Рис. р\
В состав аппаратурного обеспечения системы "Теремки" входят следующие средства:
- УЖ СМ-4
- графический дисплей ЭПГ-СМ, или ЭПГ-400, или УТЗГИ
- планшетный графопостроитель АП-725І
- считывающая головка ЕОАК производства фирмы KARL-ZEFSS (ІДР, г.Йена).
- контролер считывающей головки.
Графопостроитель АЛ-725І предназначен для механического перемещения считывающей головки ЕОАК, укрепленной на траверсе графопостроителя. Рядом со считывающей головкой укреплена также световая указка, с помощью которой система по указанию оператора очерчивает место на изображении, подлежащее считыванию. При этом пишущая головка графопостроителя оставлена, что позволяет использовать графопостроитель по своему прямому назначению.
