автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Моделирование и анализ пространственной структуры графических изображений на основе дискретно-планиметрической модели гиперрастра

На правах рукописи

ЛЕВИЦКАЯ Людмила Николаевы;»

УДК 004.921+004.932.2+004.932.72'1+519.673

МОДЕЛИРОВАНИЕ И АНАЛИЗ ПРОСТРАНСТВЕННОЙ СТРУКТУРЫ ГРАФИЧЕСКИХ ИЗОБРАЖЕНИЙ НА ОСНОВЕ ДИСКРЕТНО-ПЛАНИМЕТРИЧЕСКОЙ МОДЕЛИ ГИПЕРРАСТРА

Специальности:

05.13.18 — Математическое моделирование, численные методы

и комплексы программ 05.13.0} — Системный анализ, управление и обработка информации (машиностроение и вычислительная техника)

Автореферат диссертации на соискание ученой степени кандидата технических наук

Ижевск 2006

Работа выполнена в ГОУ ВПО «Ижевский государственный технический университет» (ИжГТУ)

Научный руководитель:

Заслуженный изобретатель Российской Федерации, доктор технических наук, профессор Лялин В.Е.

Официальные оппоненты:

доктор физико-математических наук, профессор Уварова Л.А. (ГОУ ВПО Московский государственный технологический университет (МГТУ) «Станкин»)

доктор технических наук, профессор Кучуганое В.Н. (ИжГТУ)

Ведущая организация:

ГОУ ВПО «Поеолясская государственная академия телекоммуникаций и информатики» (ПГАТИ, г. Самара)

Зашита состоится 24 ноября 2006 г. в 14.00 часов на заседании диссертационного совета Д 212.065.04 в ИжГТУ по адресу: 426069, г. Ижевск, ул. Студенческая, 7, корп. 1, ауд. 4.

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

С диссертацией можно ознакомиться в библиотеке ИжГТУ.

Автореферат разослан 21 октября 2006 г.

Ученый секретарь диссертационного совета, доктор технических наук, профессор

Б.Я. Бендерский

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Разработке и исследованию моделей изображений и методов их анализа и синтеза уделено большое внимание в работах отечественных и зарубежных ученых: Брезенхама Дж., Бонгарда М.М., Васина Ю.Г., Журавлева Ю.И., Ковалевского В. А., Лебедева Д.С., Марра Д., Мучника И.Б., Нарасимхана Р., ПавлидисаТ., ПрэттаУ., Роджерса Д., РозенфельдаА., Стокхэма Т., ФайнаВ.С., Фркмена X., Фу К., Харалика Р.М., Цуккермана И.И., Шермана Г, Ярославского Л.П. и др.

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

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

Дня достижения поставленной цели в работе решаются следующие задачи:

— разработка метода анализа пространственной структуры изображений, обеспечивающего объективное построение полного и точного описания структуры графических изображений и выявляющего все существенные геометрико-топологаческие свойства, характеристики и взаимосвязи его структурных элементов;

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

графические факторы их воспроизведения;

— исследование различных способов формирования дискретных растровых представлений пространственной структуры графических изображений и выявление возникающих на растре искажающих эффектов дискретизации структурных элементов изображений;

— анализ искажающих эффектов дискретизации структурных элементов изображений на растре для построения их дискретных представлений, обладающих минимальной неопределенностью;

— разработка и исследование дискретно-планиметрической модели изображений, обеспечивающей дискретное представление их пространственной структуры с минимальной неопределенностью;

— сравнительный анализ методов распознавания структурных элементов изображения в их различных дискретных представлениях;

— разработка метода обнаружения, распознавания и оценки дискретно представленных структурных элементов изображений;

— разработка эффективных вычислительных схем и алгоритмов формирования, преобразования и анализа дискретных представлений пространственной структуры графических изображений;

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

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

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

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

Методы исследования. В работе применялись теоретические и экспериментальные методы исследования.

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

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

Достоверность изложенных положений работ 1,1 подтверждается результатами практического применения разработанных методов, алгоритмов, про-

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

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

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

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

— метод трансформационного анализа пространственной структуры изображений, реализующий схему восходящего анализа, обеспечивающий объективное построение полного и точного описания структуры графических изображений и выявляющий все существенные геометрико-топологические свойства, характеристики л взаимосвязи их структурных элементов;

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

— результаты исследования различных способов формирования дискретных растровых представлений пространственной структуры графических изображений и выявления возникающих на растре искажающих эффектов дискретизации структурных элементов изображений;

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

— дискретно-планиметрическая модель гиперрастра, построенная на основе теории пространств толерантности и обеспечивающая дискретное представление пространственной структуры изображений с минимальной неопределенностью;

— результаты сравнительного анализа методов распознавания структурных элементов изображения в их растровом и шперрастровом дискретных представлениях;

— метод центроидной релаксации, обеспечивающий обнаружение, распознавание и оценку дискретно представленных структурных элементов изображений;

— эффективные вычислительные схемы и алгоритмы формирования, преобразования и анализа дискретных представлений пространственной структуры графических изображений;

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

кретных представлений пространственной структуры графических изображений;

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

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

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

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

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

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

- на основе использования теории пространств толерантности разработана дискретно-планиметрическая модель гнперрастра, обеспечивающая дискретное представление пространственной структуры изображений с минимальной неопределенностью — с точностью, определяемой элементами порождающей растровой сетки - узлами, границами и внутренностями ячеек сетки;

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

чений с нулевой погрешностью;

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

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

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

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

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

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

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

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

Реализация и внедрение результатов работы. Полученные результаты использованы при выполнении 14 НИОКР, выполненных в ИжГТУ, Физико-техническом институте УрО РАН и Удмуртском государственном университете (УдГУ), и внедрены в ряде организаций н предприятий, где они используются для выполнения производственных, опытно-производственных, научно-исследовательских и учебно-методических работ:

- алгоритмы и комплекс программ автоматизированного дешифрирования изображений объектов местности на космических снимках земной поверхности; программное обеспечение многоцелевого высокоразрешающего анализатора фотоизображений СИН-5 (29 НИИ МО РФ);

- методики и программы моделирования, анализа и визуализации внутреннего строения пространственных структур сплошных сред (Физико-технический институт УрО РАН);

- программы технологической подготовки и обработки данных для создания базовых цифровых карт территорий; базовые цифровые карты г. Ижевска, г. Сарапула, г. Глазова (Госкомзем Удмуртской республики (УР)), базовая цифровая карта УР (Госкомэкологии УР); система программного обеспечения технологической подготовки и документирования цифровых карт (ГУД ATTI «Уд-муртаэрогеодезия»); программные приложения ГИС Maplnfo 5.0, обеспечивающие функционирование геоинформационной системы «Монитор-Иж» для контроля оперативной обстановки па территории города (Штаб МВД УР); ис-торико-ли нгвистич еская ГИС Камско-Вятского междуречья и экспертные системы мониторинга территориального распределения уровней заболеваемости населения г. Ижевска и Удмуртской республики (УдГУ);

- алгоритмы и программы обработки н кодирования графической информации (Тульский филиал ОАО «Центр Телеком»);

- инструментальное технологическое программное средство — двухтактный интерпретатор Pilot, обеспечивающее высокий уровень автоматизащш работ по созданию исследовательского, технологического и специализированного программного обеспечения (ИжГТУ);

—учебно-методические материалы по дисциплинам «Компьютерная трафика», «Интерактивные графические системы», «Человеко-машинное взаимодействие» (ИжГТУ).

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

Апробация работы. Результаты работы докладывались на российских и международных научно-технических конференциях и конгрессах: VI и V Российских университетско-академических научно-практических конференциях (Ижевск, 1999, 2001); IV Международной научно-технической конференции «Информационные технологии в инновационных проектах» (Ижевск, 2003); VI Международном конгрессе по математическому моделированию (Нижний Новгород, 2004); XXXI и XXXII Международных конференциях «Информационные технологии в науке, социологам, экономике и бизнесе» (Украина, Крым, Ялта-Гурзуф, 2004,2006); V Международной научно-технической конференции «Проблемы техники и технологии телекоммуникаций» (Самара, 2004); VII Международной конференции «Цифровая обработка сигналов и ее применение» (Москва, 2005); Межрегинальной научно-практической конференции «Развитие информационного пространства». (Ижевск, 2005); Научной конференции «Теория управ-

ления и математическое моделирование» (Ижевск, 2006); Международной конференции «Информационные технологии в образовании» (Ижевск, 2006).

Публикации. Основные научные результаты по теме диссертации опубликованы в 34 научных работах, в том числе: 5 статей в списке, утвержденном ВАК, 2 статьи в научно-технических журналах и сборниках, 7 тезисов докладов на российских и международных научно-технических конференциях и конгрессах, 19 научно-технических отчетов по 14 НИОКР.

Объем и структура диссертационной работы. Диссертация содержит введение, 5 глав и заключение, изложенные на 148 с. машинописного текста, а также 4 приложения. В работу включены 51 рис., 12 табл., список литературы из 155 наименований. В приложениях представлен акт об использовании результатов работы.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе анализируются особенности, свойства и характеристики графических изображений (ГИ), их пространственной структуры (ПС) и ее графического воспроизведения. Формулируются задачи моделирования и анализа структуры П1 и проводится обзор моделей и методов анализа их ПС Устанавливается различие между функциональным и структурным представлениями изображений. В первом случае изображение — целостный объект — функция координат на плоскости, в то время как смысловое содержание изображения определяется его структурным представлением - двумерной пространственной структурой (ПС) — совокупностью взаимосвязанных структурных элементов (СЭ) изображения, описываемой в терминах их свойств, характеристик и отношений. Выделяется графический способ формирования изображений, реализуемый путем нанесения СЭ на плоскость изображения в соответствии с некоторым априорно определенным пространственным планом построения (ПП) изображения. Результатом являются разнообразные ГИ различных объектов, воспроизводящие их ПС: карты, плапы, схемы, чертежи, рисунки и т.д. ПП ГИ определяет априорно заданную структурную организацию в воспроизводимых изображениях.

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

Отличительными признаками ГИ являются их пространственная и графическая определенность. Пространственная определенность означает принадлежность каждой точки изображения единственному СЭ (объекту или части одного юга нескольких объектов), что реализует структурную обусловленность изображений их ПП, определяющим местоположение, смысловые характеристики я взаимосвязи СЭ. Графическая определенность — точное указание графической формы каждого СЭ, определяемой видом изображаемого объекта и его смысловыми характеристикам. Изображение составляется из таких форм в соответствии с некоторой заранее заданной их номенклатурой или легендой, предусматри-

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

Таким образом, каждое ГИ определяется двумя компонентами - пространственной, описывающей ПС изображения и представляемой его ПП, и графической, определяющей воспроизведение его структуры с использованием условных знаков и представляемой ЛГ изображений.

В зависимости от размерности СЭ подразделяются на пленарные (размерность 2), линейные (размерность 1) и точечные (размерность 0). При размещении в поле изображения совокупности их графических форм воспроизводится ПС ГИ. Графическая компонента — ЛГ изображений, вторична и не определяет ПС ГИ, но необходима для обеспечения зрительного интерфейса человека, воспринимающего их, в то время как пространственная компонента — ПП изображений, первична и полностью определяет их ПС.

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

Центральным моментом при моделировании и анализе ПС ГИ является возможность эффективного представления и воспроизведения СЭ и их взаимосвязей. Поэтому при анализе изображения возникают задачи объективного выделения СЭ ГИ и формирования полного и точного описания его ПС, а при синтезе изображения - задачи его качественного воспроизведения.

Анализ существующих моделей изображений позволяет выделить два основных первичных их класса и возможные их разновидности. Так представления растровых изображений подразделяются на кодовые, с характеристикой кода вида объекта (ЬСВО), и графические, характеристикой которых является тон или цвет. Последние, в свою очередь, могут быть сканометрическими, полученными сканированием аналогового гоображения, и синтетическими — синтезированными в цифровом представлении по описанию ПС изображения. Первые подвержены воздействию искажений и шумов, в то время как вторые свободны от них. На ПС всех разновидностей растровых изображений накладывается собственная структура растра. Отмечается, что функции растровых изображении в системах обработки графической информации не сводятся к их использованию в качестве растровой подложки.

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

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

и

те или иные характеристики его структуры. Полученное в результате производное (препарированное) изображение обычно анализируется глобальными методами, целиком выявляющими СЭ ГИ. Как вариант, глобальные методы могут быть построены так, чтобы определять СЭ ГИ по исходным изображениям. При оценке методов анализа в целом можно отметить; что локальные методы принципиально имеют низкую помехоустойчивость, что вызывает возникновение дефектов в описании структуры изображения, а глобальные методы обладают низкой чувствительностью к локальным переходам между СЭ, что снижает объективность определения СЭ ГИ и их взаимосвязей. Результативность анализа снижается при воздействии искажений и шумов, ио даже при их отсутствии, собственные искажения структуры растра, которые присутствуют даже в синтетических растровых изображениях, порождают проблемы объективизации выделения СЭ ГИ, т.к. значения характеристик СЭ необратимо искажаются на растре. Кроме того, на ПС ГИ накладывается вторичная графикационная структура, определяемая ЛГ изображения, которая, по существу, является маскировкой первичной компоненты — ГШ изображения, так что для устранения этой вторичной структуры требуются дополнительные процедуры ее распознавания.

Одним из перспективных путей разрешения указанных противоречий является использование разработанных и реализованных при участии автора метода цемро-идной фильтрации изображений и метода их адаптивного цветотоиового преобразования (АЦТП). Оба метода используют настраиваемые окна с заданными размерами и формой. Для пиксела с координатами (i,j) окно образуется совокупностью п пикселов в его окрестности w(i,y)={(í+it,^+у* ) | fc = 1.и}, где ik, — величины смещений пикселов окна относительно положения центрального пиксела (i,j).

Центроидное преобразование изображения l(f, j) в общем случае заключается s вычислении вектора центроида (i,j\Су (<\ j)) для каждого пиксела:

тМф\/} . s(/-y)i(i*,/)

, л , (1) , ZH' *j ) , ¿Л1 )

А (Л/Ну) (л/Ыи) . , ^

после чего формируется производное центроидное изображение Cy.^J. Для этого создается «пустое» изображение Z(i,_/)=0, которое затем модифицируется: C0{i,j)=Z(i,j)+1,если < = СД<М)), j = Cy(0fi), Cm+1(U)=CM(U)+1 .если i = ¿* + С,(i*,/), j = f + сДЛ/), (2) где индекс m = i+Mj нумерует пикселы изображения размера MxN, соответственно, i" =т—M — , j* = 1 ([а] - целая часть числа а).

L-A/J IAM

В частном случае окно w(/",/) может иметь вид строчного или столбцового интервала. На рис. 1 показан процесс формирования центроидного изображения при различных окнах для различных СЭ. № рисунка видно, что центроидное преобразование обладает отчетливо выраженными селективными свойствами по отношению к СЭ, проявляет при этом субпиксельные эффекты и позволяет обнаруживать линейные СЭ вне зависимости от их стиля.

Дальнейшая обработка центрондным фильтром заключается в пороговом выделении на центроидном изображении пикселов с высокой яркостью и вычислении для них величин диссипации H и экстента h (при этом возможна смена

а) интервал, шикарный СЭ

в) круг, плаиарный СЭ

б) интервал, линейный СЭ (стилевой)

Pue. 1. Протес формирования центронлного изображения размеров и формы окна; см рнс. 1а,б):

={ù£]kbàl_,__

pl-'V

hJi,j)=Jl2Hx(ij).

■ФЛ

г) круг,

линейный СЭ

(3)

(4)

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

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

Для достижения необходимых показателей качества обработки полутоновых изображений, а также для обеспечения возможности обработки цветных ГИ, разработан метод АД 111, который заключается в следующем.

Создается первичное «пустое» цветное изображение 2л>с>в(/,у)=0, затем цветовые компоненты 1с(/,у) изображения 1д о й (<',>) обрабаты-

ваются связно-кластерным фильтром:

ш-, яЛгА бьМ, ВвМ- (5)

Для каждого пиксела с координатами (/, ]) производится сравнение с порогом р;

Если (б) при всех 1

(¡'\у'*)е выполнено, то ZR G B(i,j) мод

6)

у) модифицируется:

Дальнейший анализ состоит в выделении в изображении связ-

ных цветовых областей (?],..., и определении характерных цветов:

S^fcA TZG(«V), д

jV„

(8)

где q = l,Q, Q - количество областей, Ng - количество пикселов в области Gq.

Обработка завершается созданием пакета «пустых» бинарных изображений Z|(f,_/)=0,Zg(i,y)=0 и их последующим заполнением:

^У)-1.«яи(!,у)еО,.- (9)

Результатом АЦТП является стратифицированное по характерным цветам изображение _ которое может быть подвергнуто послойной центроидной фильтрации с последующим пространственным анализом для формирования ПП ГИ.

Исследования АЦГП показали, что преобразование обладает высокой способностью шумоподавления, а при восстановлении цветного (полутонового) изображения может быть достигнуто более высокое качество воспроизведения по сравнению с исходным изображением за счет выравнивания цветовых (тоновых) контрастов.

Во второй главе уточняется и формализуется понятие ПС ГИ в ее непрерывном представлении. Основой формализации является анализ трансформаций структуры изображений, позволяющий выявить и определить их СЭ, гео-метрико-топологичес кие свойства, характеристики и взаимосвязи этих элементов. Это позволяет построить математическую модель ПС ГИ, учитывающую их ПП и графические факторы их воспроизведения,

На интуитивном уровне ПП изображения можно представить, как разметку поля изображения областями, линиями и точками, определяющими местоположение, соответственно, плаиарных, линейных и точечных СЭ (планиментов, ли-неаментов и пунктов). Семантика ПС определяется приписыванием этим областям, линиям и точкам соответствующих кодоввида объекта (КВО).

Такое представление не вполне корректно, т.к. не определяет принадлежность границ планиментов и узлов лииеамен-тов (см. рис. 2), оставляет неопределенными области фона и следы от устранения СЭ, а также не допускает возможность взаимного наложения СЭ.

ЩЗЙШ

а) границы планиментов 6) узлы линеаментов Рис. 2. Принадлежность краевых точек СЭ Корректность представления ПП изображений достигается при использовании понятия сигнатуры. Кодовой сигнатурой ПС изображения в точке (х, у) называется множество КВО всех точек, содержащихся в ее окрестности .у):

(10)

а зависимость значений сигнатуры ог координат на плоскости называется сиг-натурно-кодовой картой изображения. Сигнатура краевых точек СЭ содержит КВО всех примыкающих к ним элементов, фон определяется пустой сигнатурой — 0, следы от устранения СЭ исчезают и возможность взаимного наложения СЭ становится допустимой.

Использование сигнатур частично определяет топологические свойства и отношения СЭ, но эти определения не являются полными. Так на рис. 3 в первых

двух случаях сигнатуры внутренних и краевых точек планимента (1/51)5/,) одинаковы, в третьем случае — сигнатуры точек позиционирования пункта } одновременно на плани-Рис. 3. Различные виды сигнатур менте Н двух ликеамекгах

((Щ ПКА и^2)ПС1)и(9/5 Пй^ ГИХз ПС,)) одинаковы, няе зависимости от

Пример сигна-турно-кодовой карты ГИ показан на рис. 4, го которого видно, как различные сигнатуры образуются в результате различных сочетаний смежных СЭ различных размерностей, образуя своеобразную сигнатурную легенду изо-

Рис;. 4. Си гн ату р и о- ко да в а и карта ГИ бражения.

Метод формирования описаний ПС ГИ основан на анализе их трансформаций, описываемых группами преобразований. Определяется С -эквивалентность точек: две точки изображения С -эквивалентны ((? - группа преобразований), если существуют и е<7, взаимно преобразующие

их вместе с их окрестностями:

. )П ,^))=)Л )

Необходимым (но не достаточным) условием (/-эквивалентности точек является равенство их кодовых сигнатур.

Рассматривается последовательность основных групп преобразований, сформированных из образующих подгрупп преобразований (см. табл. 1): трансляции - Тг, движения — Му (трансляции — Тг и центроаффинные ротации — ЯО и нерефлексные аффинные преобразования - АГ (трансляции - Тг, центроаффинные ротаций - и центроаффинно-аксиалыше б «компрессии — Вс). Все эти группы — подгруппы группы аффинных преобразований и, следовательно, наследуют все ее инварианты, а группа аффинных преобразований -подгруппа группы всех непрерывных преобразований и наследует все ее инварианты. Поэтому для всех основных групп преобразований инвариантными будут такая характеристика многообразий как размерность, такое их свойство, как связность, и такое их отношение, как смежность.

Последовательность выполнения трансформационного анализа ПС ГИ следующая. На нервом этапе определяется Тг -эквивалентность и выявляются (склеиваются) связные (связность — инвариант) множества эквивалентных точек (см. рис. 5). При этом обнаруживаются все плалименты н области фона (размерность ~2), все прямолинейные (прямолинейность—инвариант) участки (отрезки)

принадлежности их внутренности или краю планимента

СИГНАТУРЫ!

1 О (с.) э Еф (ЧАЛ,)

1 □ Л) 19 ф ('..ц)

О Л! К в-

4 в ЛА} 11 л. (цл,)

ш Л) и

( — (Ь.) 14

Т — М и -А- ^.С,]

* Ы

линеаментов (в однотипном окру- Таблица!

жешш) и границ планиментов (ра> мерность— IX а также все пункты в часть узлов (размерность—0).

Затем определяются связные множества Му -эквивалентных точек (см. рис. 5). При этом выявляются все дугообразные (дуго-образность — инвариант) участки (дуги) линеаментов (в однотипном окружении) и границ планиментов (размерность - 1), а также часть узлов (размерность—0).

Далее выявляются связные множества АГ -эквивалентных точек (см. рис. 5) — участки ли-пеаментов (в однотипном окружении) и границ планиментов переменной но знакопостоянной кривизны (квазидуги — инвариант, размерность — 1), а также все оставшиеся

В том же порядке устанавливаются геометрические атрибуты выявленных СЭ. Геометрическими атрибутами точечных СЭ являются их координаты — (х,у) (инвариант относительно тождественного преобразования). Атрибутом-инвариантом линейных СЭ с геометрическим типом отрезков на уровне Тг-эквивалентности является их кривизна, сохраняющая нулевое значение — С = 0. Атрибут-инвариант линейных СЭ типа дуги на уровне Му -эквивалентности — их кривизна, сохраняющая свое значение — Рис. 5. Анализ трансформаций ГН С. Для получения однопараметрическойатрибутизации линейных СЭ типаква-квазндуги целесообразно разбить ее на небольшие участки (с точками сопряжения - квазиузлами), аппроксимируемые эллиптическим приближением; тогда их атрибутом-инвариантом на уровне АГ-эквивалентностн является их начальная кривизна— С0.

В результате трансформационного анализа выявляются СЭ ГИ всех типов, подтипов, видов и геометрических типов, а также геометрические атрибуты последних (см. табл. 2).

_Трансформация ГИ_

а) образующие подгруппы преобразований Трансляции:

Тг[а,б](л:,>>Н(дг+д,у+б)__

Центроаффинные ротации:

Ш[а]{д:, у) = (я соб а - у эт а, х б1п а + у соз а)

Цснтроаффинно-аксиальные бикомпрессии:

Вф] Л К*.^) = (V+к2У\> ОДг > 0

6} основные группы преобразовании Трапелящш:

Тг[а,б](х,у)__

Движения:

Му[о, а, Ь] = Тг[а,г>] ° Ш[а](х,.у)_

Нерефлекспые аффинные преобразования:

>0,^>0__

Таблица 2

Структурпие элементы и их атрибуты

ТнпСЭ размерность Подтип СЭ вид Геометрические атрибуты

Плая арные 2 Пяанимект ПСВО) -

Фон -

Линейные 1 ' Геометрический тип

Отрезок Дуга Квззидуга

Липеамент (КВО) Кривизна с=о Кривизна С Кривизна

Граница Кривизна С = 0 Кривизна С Начальная кривизна

Точечные о ■■■ " Пункт (КБО) Координаты (г, у)

Узел (квазиузел) Координаты (•£,>')

Поскольку смежность многообразий является наследственным инвариантом всех рассматриваемых трупп преобразований, то бинарное отношение смежности связывает всю совокупность выделенных в изображении СЭ с их атрибутами в структуру, в которой однозначно определены СЭ и все их существенные геометрнко-топсшогические свойства, характеристики и взаимосвязи и которая является объективным, полным и точным описанием ПС ГИ.

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

•—

2 г.

"'■¿•Ж

^^"Гг ? ' 27» ' **

К- I '•'т-Г--

к!-':'.-...

Ян

жш..

Рис. 6, Структурное описание ГИ Установлены следующие пространственно-структурные свойства ГИ {смежность обозначена знаком плаларные СЭ - Р, линейные — Ь, точечные — С): —для любых СЭ ->(/] —■{£] ~ ¿2) (несмежносгь однотипных СЭ); —если Р~Ь, а ¿ — С,то Р~С (межразмернаятранзитивность); -порядок любого узла я (С) £ 1, порядок любого пункта и(С)гО;

— порядок любого линейного СЭ 0 < «{/,) < 2; для всякого линейного СЭ Ь существуют только два пленарных СЭ /} и Р2, таких что ~ Р2\

— порядок любого планарного СЭ I.

Графикадионная структура ГИ также может быть распознана путем построения структурного описания (см. рис. 7).

I. с. ц ^ ц

Ц (., ц с, ц с, ь.

Рис. 7. Грзфикацноипаи структура линейного СЭ

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

Дискретное представление ПС ГИ формируется при квантовании координат хну точек плоскости, определении растровой сетку ячеек и индексации их целочисленными значениями / и j. Точечный ОФР отображает точечный СЭ с координатами (я, у) в пиксел с индексами (i,j). Различия точечных ОФР заключаются в принадлежности границ ячеек растра и узлов растровой сетки. Простейший ОФР - целочисленное квантование координат (см. рис. 8):

(12)

Интервалы квантования характеризуются вектором принадлежности границ (ВПГ), равным длине интервала и направлены ным на не принадлежащую интервалу границу. На рис. 8 внутренность ячеек выделена тоном, непринадлежность границ — светлыми полосами, а типы ячеек определяются ВПГ. Растр неоднороден -составлен из девяти типов ячеек, различного размера с различной принадлежностью их границ и узлов растровой сетки.

Искажения дискретизации оцениваются по диагональным прямым, которые должны образовывать диагональные цепочки ячеек на растре. Характер искажений таков, что в квадранте наибольшего сближения (КНС) с начало координат (НК) узловые прямые осциллируют в направлении к НК (лестничный эффект(ЛЭ) с уширением в направлении НК), за пределами КНС НК неузловые прямые осциллируют (ЛЭ), а в КНС НК осциллируют в направлении к НК (ЛЭ со смещением в направлении НК), и все искажения имеют необратимый и нерегулярный характер, обусловленный наличием в растре ячеек различного размера.

Различия в размерах ячеек устраняются ОФР квантованием с округлением: t = Cv*(jc)= Cv (х + 0.5 sign(*))j = Cv*(y)=Cv(y+0.5 sign (») (13)

Образующийся растр однороден по размеру ячеек, но неоднороден по принадлежности их границ и узлов растровой сетки, составлен из девяти типов ячеек (см. рис. 9) и также подвержен искажениям. В КНС НК узловые прямые осциллируют в направлении от НК (ЛЭ со смещением в направлении от НК), все неузловые прямые осциллируют (ЛЭ), и все искажения имеют необратимый характер, обусловленный наличием в растре ячеек с различной принадлежностью их границ и узлов растровой сетки.

Различия в типах ячеек устраняются одинаковой установкой их ВПГ на основе квантования с по-зитивизацией (негативизацией), поскольку для каждого числа z можно определить меньшее (большее) его по величине целое число:

i=Cv(*),^CvCy). г

о

[-I.+1] [±2,+1] [+1,+1] >

в

[-1Д2] [±2,±2] [М,±2]

| ф i

[-1,-1] [±2,-1] [+1,-1] Рис. 8. Ячейки растра [±2,±2]

т т Q т

[±1,+1] [+i,+i]

оЩ*

[±1ДЦ [+U1]

ш А 0 ш

и,-п [±1,-U [+1.-11

Рис. 9. Ячейки растра [±|,±1|

рог(г)=Су(г)-1,^(г)=0(г)+1, (14)

Позитивизация z - г+ = г-рог(г), ее квантование (13) и обратное преобразование определяет схему квантования с позитивизацией:

(V (г)»Су* (г+ )+ ро2 (г) (15)

что обеспечивает однотипность интервалов квантования по принадлежности их границ. Аналогичным образом: z~ = г-neg(z), Су'^^Су*^")*!^^).

Применение таких ОФР приводит к образованию четырех однородных растров с ячейками, однотипными по размерам и по принадлежности их границ и узлов (см. рис. 10), которые также подвержены искажениям.

Узловые прямые, ориентированные в направлении, (Щ Щ

ортогональном ВПГ, осциллируют в направлении ВПГ (ЛЭ с уширением в направлении ВПГ), все неузловые прямые осциллируют (ЛЭ), и все искажения имеют необратимый характер, обусловленный анизотропией, связанной с направлением ВПГ (см. рис. 11).

Возможно также использование ОФР на основе функции Антье С ' (г)=[г]=[г]+ и симметричной ей функции Су^(г)=[г]~, отличающихся ст ОФР СИ{г) и Су"(г) сдвигами интервалов квантования, а также их центрированных аналогов з*+} = [г]+ + 0.5 и = -0.5. Все эти однородные ОФР имеют идентичный характер искажений дискретизации. Возможны так-

а)[-1,+1] 6) [+1.+1]

однородных растров

/ ]

N

Рис. ¡1. А|«ютрсаня однородного растра

же неоднородные ОФР с ячейками, границы которых несмежны. При регулярном чередовании ячеек образуется квазиоднородный растр, однородный по

ШШ

нши

Ш5Щ

<0 ячейки б) растр в) квазиячейки Рис.12. Квазиоднородный растр (ОФР Су")

отношению к квазиячейкам (см. рис.12). Оператор Су порождает 8 типов растров, получаемых поворотами, кратными 90й и зеркальными отражениями. Все

. . |В-

Можно также построить нерегулярные растры за счет применения ОФР О1 на основе стохастического квантования, при котором принадлежность ячейкам гранш и узлов определяется выбором по заданному распределению вероятностей (см. рис. 13), для которых искажения имеют вид нерегулярных осцилляций (эффект зубцов и ЛЭ).

а) растр

6) искажения дискретизация Ас 11 Нсрау^я-й растр (ОФР С\3 )

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

Для линейных и планарных ОФР, построенных на основе различных модификаций алгоритмов Брезенхама и США, несмотря на их специфику, связанную с прореживаним пикселов ва линиях и границах, также характерны необратимые искажения дискретизации, обусловленные выбором ВПГ.

Кроме того, в результате дискретизации возникают многочисленные геометрические аберрации на растре — нарушения фундаментальных геометрических свойств и отношений СЭ, вплоть до аксиом геометрии. Например (см. рис. И), если отрезок а содержится в отрезке о, то все точки отрезка а являются точками отрезка Ь, в то время как на растре не все пикселы отрезка а являются пикселами от- М- Совмещенные отрезки

резка Ь и общие пикселы отрезков не образуют связной последовательности.

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

Возникающие на растре искажения дискретизации СЭ обусловлены факторами вырождения - утраты информации о значениях координат при их преобразования в целочисленные индексы, неоднородности растра, обусловленной различием в размерах ячеек растровой сстки в принадлежности их границ, и анизотропности растра, обусловленной выборов принадлежности границ ячейкам. Первый фактор принципиально неустраним, второй и третий факторы устраняются созданием однородных растров, а Произвольность выбора принадлежности границ ячейкам приводит к образованию нескольких равноценных растров с различной анизотропией. При отсутствии предпочтений выбор любого из них некорректен, т.к. возникающие искажения имеют необратимый и различный характер: осцилляции прямых (ЛЭ) и кривых (эффекты зубцов), асимметричность растровых представлений СЭ при различном порядке просмотра пикселов, аномальная сегментация СЭ, изломы в начале координат и т.д.

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

Толерантность на множестве ин- ^^ ГЦЦ

дуцнрует покрытие, элементы которо- Щ Щ ЦЩ §§3 [ВЙЙЩ го являются классами толерантности Ш1у

(см. рис. 15). Важным является поня- а) класс б) посгогассы

тие ядер толерантности О^'.л:1,...), Рис. 15. Классынпосткласситолерант-состоящих из элементов, входящих в иостн, индуцируемой растровой сеткой пересечение классов толерантности: К1, К2,.... Непустые ядра образуют разбиение множества и тем самым задают отношение эквивалентности на нем, индуцированное толерантностью (см. рис. 16а,б). Для всякого элемента х можно определить посткласс Тх - множество элементов, толерантных к л (см. рис. 156), что определяет отношение эквивалентности 0: леву, если Тх - Ту. а непустые ядра служат для б классами эквивалентности.

■ив

а) пересече- б) ядра ния классов толералт-толерашности ности Рис. 16. Формирование гиперрастра

в) ячейки гиперрястра

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

Так же как пространство толерантности обладает более богатыми свойствами по сравнению с эквивалентностью, так и гиперрастр проявляет новые, не присущие растру свойства. В частности, на гиперрастре существуют единственные операторы его формирования для каждого типа СЭ и соответствующие им эффекты дискретизации, использование которых при анализе ГИ дает значительные преимущества по сравнению с растром. Сравнение гиперрастровых представлений СЭ изображений на рис. 17а с их растровыми представлениями на рис. 176 показывает основное преимущество гиперрастра - отсутствие необратимых искажений

ом пршкда^юстид^ит^етефсам.

дискретизации, обусловленных выбо;

а) на гиперрастре 6) на растре

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

В пятой главе описаны разработанные методы, алгоритмы, программное обеспечение и технология обработки графической информации, основанные на использовании дискретных гиперрастровых представлений ПС ГИ, а также результаты экспериментальных исследований разработанных средств и методов и оценки их эффективности и возможностей использования при решении различных прикладных задач, связанных с обработкой графической информации.

При сравнительном анализе результатов распознавания СЭ на растре и на гиперрастре был использован метод наименьших квадратов (МНК), примененный для оценки прямых и дуг окружностей. Очевидно, что уменьшение степеней свобода на гиперрастре при варьировании параметров СЭ в МНК должно повысить точность оценок. Было установлено систематическое снижение погрешности на величину 35-70%. Кроме того, при наличии фокусных точек на гиперрастре величина погрешности может снижаться до нулевых значений.

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

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

"" Кроме того, исполь-

зование дифференциального цепного кодирования СЭ, формируемого на основе их центроидно-го преобразования,' последующей сегментации цепных кодов и распознавания СЭ позволило существенно снизить используемые ресурсы памяти.

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

Экспериментальным исследованиям были подвергнуты ГИ различного уровня сложности по количеству содержащихся в них СЭ, количеству видов СЭ и разновидностей их графических форм. В экспериментах варьировались параметры всех разработанных блоков обработки графической информации с целью их оптимальной настройки. Результаты экспериментов показали высокое качество анализа ПС ГИ, высокую производительность процедур обработки информа-

цин, а также высокую степень ее сжатия, вплоть до нескольких порядков.

В приложениях помещены экспериментальные данные и результаты по оценке искажений дискретизации для различных линейных и планарных ОФР, по всем стадиям обработки простых черно-белых линейчатых изображений и сложных многоцветных стилевых ГИ, а также акт об использовании результатов диссертационной работы.

ЗАКЛЮЧЕНИЕ

В работе получены следующие основные выводы и результаты.

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

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

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

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

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

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

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

8. Разработаны эффективные вычислительные схемы и алгоритмы формирования, преобразования и анализа дискретных представлений пространственной

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

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

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

11. Разработано инструментальное технологическое программное средство - двухтактный интерпретатор Pilot, использованный при создании программного обеспечения, который обеспечивает высокий уровень автоматизации работ по созданию исследовательского, технологического и специализированного программного обеспечения, что позволяет создавать программные и информационные продукты для многоцелевого использования и для создания автоматизированных систем обработки графической информации различного назначения.

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

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

НАУЧНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Захаров A.B., Мурынов А.И., Сапегина Л.Н. Микровекторизация картографических изображений // Тез.докл. IV Росс, унив.-акад. науч.-практ. конф, —

Ч. 2. — Ижевск, 1999.-С. 171-172.

2. Захаров A.B., Мурынов А.И., Сапегина JI.H. Алгоритмы и программное обеспечение центроидной векторизации растровых изображений Я Тез. докл. V Росс, унив.-акад. науч.-практ. конф. -Ч. 8, - Ижевск, 2001. С. 35-36.

3. Мурынов А.И. Сапегина JI.H. Анализ растровых изображений на основе центроидной фильтрации. // Тез. докл. V Росс, унив.-акад. науч.-практ. конф. — Ч. 8. - Ижевск, 2001. С. 39-40.

4. Микрюков A.B., Мурынов А.И., Сапегина JI.H., Телегина М.В. Разработка и применение новых технологий создания цифровых карт // Тез. докл. V Росс, унив.-акад. науч.-практ. конф.-Ч. 8,-Ижевск,2001. С.40-41.

5. Галичанин A.A., Мурынов А.И. Левицкая Л.Н. Обнаружение и распознавание элементов структуры изображения методом центроидной фильтрации // Тр. IV Между нар. науч.-техн. конф. «Информационные технологии в инновационных проектах». - 4.4.-Ижевск, 2003.-С. 111-114,

6. Галичанин A.A., Мурынов А.И., Лялин В.Е., Левицкая Л.Н., Телегина М.В. Адаптивное цветотоновое преобразование изображений // Математическое моделирование и интеллектуальные системы: Тем. сб. науч. тр. IV Между-нар. науч.-техн. конф. «Информационные технологии в инновационных проектах» - Ижевск Изд-во ИжГТУ, 2003 - С. 25-3 8.

7. Мурынов А.И., Левицкая Л.Н., Шибаева И.В. Дискретно-планиметрическая графикациокная модель структуры графического изображения. // Тез. докл. VI Междунар. конгресса по математическому моделированию. - Нижний Новгород, 2004. - С. 258.

8. Шибаева И.В., Лепихов Ю.Н., Левицкая Л.Н. Математическая модель редукции пространственной структуры изображений на дискретный растр и эффекты дискретизации // Материалы XXXI Междунар. конф. «Информационные технологии в науке, социологии, экономике и бизнесе» // Прилож. к журн. «Открытое образование».—2004.— С. 48-50.

9. Левицкая Л.Н., Мурынов А.И. Гиперрастровая модель изображений // Вестник Ижевского государственного университета. - 2006. - №. I, - С. 17-24.

10. Левицкая Л.Н. Точечные операторы формирования растровых представлений пространственной структуры изображений и эффекты дискретизации //Вестник Ижевского государственного университета. — 2006.— №.1. — С. 10-17.

11. Левицкая Л.Н. Искажающие эффекты дискретизации графических изображений на растре // Материалы XXXII Междунар. конф. «Информационные технологии в науке, социологии, экономике и бизнесе» // Прилож, к журн. «Открытое образование».— 2006.— С. 173-174.

12. Левицкая Л.Н., Лялин В.Е., Мурынов А.И. Гиперрастровое представление пространственной структуры графических изображений // Материалы XXXII Междунар. конф. «Информационные технологии в науке, социологии, экономике и бизнесе» // Прилож. к журн. «Открытое образование». - 2006. - С, 175-176.

Сдано в производство 18.10.2006. Формат 60x84 1/16. Отпечатано на ризографе. Уч -им. л, 2,13. Усл. печ. л. !,39 Заказ № 810/1. Тираж 100экэ. Издательство Института экономики УрО РАН 620014, Екатеринбург, ул. Московская, 29

Л.Н. Левицкая

Лицензия ЛР № 020764 от 29.04.98

Список сокращений.

Введение.

Глава 1. Задачи моделирования и анализа пространственной структуры графических изображений и методы их решения.

1.1. Графические изображения.

1.2. Задачи моделирования и анализа структуры изображений.

1.3. Модели и методы моделирования и анализа структуры изображений.

1.4. Выводы и постановка цели и задач исследований.

Глава 2. Структурно-графикационная модель изображений.

2.1. Сигнатурно-кодовая карта изображения.

2.2. Трансформационный анализ пространственной структуры изображений.

2.3. Пространственно-структурные свойства изображений.

2.4. Графикационная структура изображений.

2.5. Полученные результаты и выводы.

Глава 3. Формирование растровых представлений пространственной структуры изображений и эффекты дискретизации.

3.1. Точечные операторы формирования растра.

3.2. Линейные и планарные операторы формирования растра.

3.3. Геометрические аберрации на растре.

3.4. Полученные результаты и выводы.

Глава 4. Дискретно-планиметрическая модель гиперрастра.

4.1. Толерантность точек плоскости, индуцированная растровой сеткой.

4.2. Формирование гиперрастра.

4.3. Структура и свойства гиперрастра.

4.4. Операторы формирования гиперрастра.

4.5. Эффекты дискретизации на гиперрастре.

4.6. Полученные результаты и выводы.

Глава 5. Методы, алгоритмы, программное обеспечение и технология обработки графической информации.

5.1. Сравнительный анализ результатов распознавания структурных элементов изображения на растре и на гиперрастре.

5.2. Метод центроидной релаксации.

5.3. Алгоритмы, программное обеспечение и технология обработки графической информации.

5.4. Экспериментальные данные и результаты.

5.5. Полученные результаты и выводы.

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

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

Разработке и исследованию моделей изображений и методов их анализа и синтеза уделено большое внимание в работах отечественных и зарубежных ученых: Брезенхама Дж., Бонгарда М.М., Васина Ю.Г., Журавлева Ю.И., Ковалевского В.А., Лебедева Д.С., МарраД, Мучника И.Б., Нарасимхана Р., ПавлидисаТ., ПрэттаУ., Роджерса Д., Розенфельда А., СтокхэмаТ., ФайнаВ.С., ФрименаХ., Фу К., Харалика P.M., Цуккермана И.И., Шермана Г, Ярославского Л.П. и др.

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

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

Для достижения поставленной цели в работе решаются следующие задачи:

- разработка метода анализа пространственной структуры изображений, обеспечивающего объективное построение полного и точного описания структуры графических изображений и выявляющего все существенные геометрико-топологические свойства, характеристики и взаимосвязи его структурных элементов;

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

- исследование различных способов формирования дискретных растровых представлений пространственной структуры графических изображений и выявление возникающих на растре искажающих эффектов дискретизации структурных элементов изображений;

- анализ искажающих эффектов дискретизации структурных элементов изображений на растре для построения их дискретных представлений, обладающих минимальной неопределенностью;

- разработка и исследование дискретно-планиметрической модели изображений, обеспечивающей дискретное представление их пространственной структуры с минимальной неопределенностью;

- сравнительный анализ методов распознавания структурных элементов изображения в их различных дискретных представлениях;

- разработка метода обнаружения, распознавания и оценки дискретно представленных структурных элементов изображений;

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

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

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

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

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

Методы исследования. В работе применялись теоретические и экспериментальные методы исследования.

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

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

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

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

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

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

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

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

- результаты исследования различных способов формирования дискретных растровых представлений пространственной структуры графических изображений и выявления возникающих на растре искажающих эффектов дискретизации структурных элементов изображений;

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

- дискретно-планиметрическая модель гиперрастра, построенная на основе теории пространств толерантности и обеспечивающая дискретное представление пространственной структуры изображений с минимальной неопределенностью;

- результаты сравнительного анализа методов распознавания структурных элементов изображения в их растровом и гиперрасгровом дискретных представлениях;

- метод центроидной релаксации, обеспечивающий обнаружение, распознавание и оценку дискретно представленных структурных элементов изображений;

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

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

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

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

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

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

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

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

- на основе использования теории пространств толерантности разработана дискретно-планиметрическая модель гиперрастра, обеспечивающая дискретное представление пространственной структуры изображений с минимальной неопределенностью - с точностью, определяемой элементами порождающей растровой сетки - узлами, границами и внутренностями ячеек сетки;

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

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

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

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

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

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

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

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

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

Реализация и внедрение результатов работы. Полученные результаты использованы при выполнении 14 НИОКР, выполненных в ИжГТУ, Физико-техническом институте УрО РАН и Удмуртском государственном университете (УдГУ), и внедрены в ряде организаций и предприятий, где они используются для выполнения производственных, опытно-производственных, научно-исследовательских и учебно-методических работ:

- алгоритмы и комплекс программ автоматизированного дешифрирования изображений объектов местности на космических снимках земной поверхности; программное обеспечение многоцелевого высокоразрешающего анализатора фотоизображений СИН-5 (29 НИИ МО РФ);

- методики и программы моделирования, анализа и визуализации внутреннего строения пространственных структур сплошных сред (Физико-технический институт УрО РАН);

- программы технологической подготовки и обработки данных для создания базовых цифровых карт территорий; базовые цифровые карты г. Ижевска, г. Сарапула, г. Глазова (Госкомзем Удмуртской республики (УР)), базовая цифровая карта УР (Госкомэкология УР); система программного обеспечения технологической подготовки и документирования цифровых карт (ГУД АГП «Удмуртаэрогеодезия»); программные приложения ГИС Maplnfo 5.0, обеспечивающие функционирование геоинформационной системы «Монитор-Иж» для контроля оперативной обстановки на территории города (Штаб МВД УР); ис-торико-лингвистическая ГИС Камско-Вятского междуречья и экспертные системы мониторинга территориального распределения уровней заболеваемости населения г. Ижевска и Удмуртской республики (УдГУ);

- алгоритмы и программы обработки и кодирования графической информации (Тульский филиал ОАО «Центр Телеком»);

- инструментальное технологическое программное средство - двухтактный интерпретатор Pilot, обеспечивающее высокий уровень автоматизации работ по созданию исследовательского, технологического и специализированного программного обеспечения (ИжГТУ);

- учебно-методические материалы по дисциплинам «Компьютерная графика», «Интерактивные графические системы», «Человеко-машинное взаимодействие» (ИжГТУ).

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

Апробация работы. Результаты работы докладывались на российских и международных научно-технических конференциях и конгрессах: VI и V Российских университетско-академических научно-практических конференциях (Ижевск, 1999, 2001); IV Международной научно-технической конференции «Информационные технологии в инновационных проектах» (Ижевск, 2003); VI Международном конгрессе по математическому моделированию (Нижний Новгород, 2004); XXXI и XXXII Международных конференциях «Информационные технологии в науке, социологии, экономике и бизнесе» (Украина, Крым, Ялта-Гурзуф, 2004, 2006); V Международной научно-технической конференции «Проблемы техники и технологии телекоммуникаций» (Самара, 2004); VII Международной конференции «Цифровая обработка сигналов и ее применение» (Москва, 2005); Межрегинальной научно-практической конференции «Развитие информационного пространства». (Ижевск, 2005); Научной конференции «Теория управления и математическое моделирование» (Ижевск, 2006); Международной конференции «Информационные технологии в образовании» (Ижевск, 2006).

Публикации. Основные научные результаты по теме диссертации опубликованы в 34 научных работах, в том числе: 5 статей в списке, утвержденном ВАК, 2 статьи в научно-технических журналах и сборниках, 7 тезисов докладов на российских и международных научно-технических конференциях и конгрессах, 19 научно-технических отчетов по 14 НИОКР.

Объем и структура диссертационной работы. Диссертация содержит введение, 5 глав и заключение, изложенные на 148 с. машинописного текста, а также 4 приложения. В работу включены 51 рис., 12 табл., список литературы из 155 наименований. В приложениях представлен акт об использовании результатов работы.

Эти выводы также справедливы для

-2-10 1 б) [-1]

Рис. 3.10. Однородные разбиения [+1| и [-1J и их интервалы квантования

1 i >

0 а) И,+1] У б) [+1,+1] У всех четырех видов однородных растров представленных на рис. 3.11.

Таким образом, и в однородном растре v проявляются эффекты искажений дискретизации, хотя и более регулярного характера. Это обусловлено тем, что все четыре вида однородных растров обладают свойством анизотропии, связанной с направлением ВПГ ячеек растра и приводящей к возникновению искажений дискретизации.

Анизотропия проявляется в отсутствии искажений диагональных узловых прямых, ориентированных в направлении ВПГ, и наличии искажений (лестничный эффект) диагональных узловых прямых, ориентированных в направлении, ортогональном направлению ВПГ (см. рис. 3.13).

В связи с тем, что ОФР (3.10) и (3.12) порождают четыре равноценных растра возникает вопрос выбора одного из них. Поскольку отсутствуют какие-либо предпочтения, этот вопрос мог бы быть решен по соглашению, подобно сов) [-1,-1] О г) [+1,-1]

Рис. 3.11. Структура и ячейки однородных растров [-1,+1], [+1,+1|, [-1,-1] и |+1,-11 глашению об отсчете величин углов против часовой стрелки (например, выбором растра [+1,+1], обычно используемого по соглашению в машинной графике

Однако, в отличие от названного соглашения, для которого изменение его условия на противоположное (отсчет величин углов по часовой стрелке) фактически ничего не изменяет и является вполне обратимым, нали

Рис. 3.12. Искажения дискретизации диагональных прямых на растре [+1,+1] чие искажений дискретизации в любом из выбранных растров приводит к необратимости изменения подобного соглашения на противоположное.

Поворот изображения на 90°, 180° или 270° (обычная операция в машинной графике) изменяет характер возникающих искажений дискретизации (см. рис. 3.13). На рис. 3.14 показаны искажения дискретизации одной и той же диагональной прямой (пунктир) на растре [+1,+1] (сплошная линия) и на растре [-1,-1] (точечный г) [+1,-1] в) [-1,-1]

Рис. 3.13. Анизотропия однородных растров пунктир). Если учесть, что растр [-1,-1] может быть получен путем поворота растра [+1,+1] на 180°, то фактически наблюдается усиление искажений дискре

-1,-1]

Рис. 3.14. Совмещение растров

Cv^(z)=[z] = [z] + =< тизации. При многократном повторении по- [+!>+!] добных операций эти искажения могут достигать любой сколь угодно большой величины. Поэтому выбор по соглашению любого из четырех однородных растров, представленных на рис. 3.11, не является корректным решением.

Следует отметить, что во многих реализациях систем машинной графики [99,133] операция взятия целой части числа (функция Integer) понимается как функция Антье - [z], принимающая значение наибольшего целого числа, не превосходящего z:

Cv(z),z>0,

Cv(z),z<0,z = Cv(z), (3.13)

Cv(z)-l,z<0,z*Cv(z).

В этом случае интервалы квантования аналогичны позитивизированным интервалам на рис. 3.10 а, сдвинутым вправо на величину +0.5.

Совершенно равноценна также обычно не используемая на практике симметричная (3.13) схема квантования, для которой интервалы квантования аналогичны негативизированным интервалам на рис. 3.10 б, сдвинутым влево на величину -0.5:

Cv(z),z<0,

Cv(z),z>0,z = Cv(z), (3.14)

Cv(z)+1, z > 0,z Ф Cv(z).

Применение ОФР (3.13) и (3.14) также приводит к образованию четырех видов однородных растров с однотипными по размерам и по принадлежности границ ячейками, аналогичных растрам, показанным на рис. 3.11, но отличающихся от них сдвигами по абсциссе и ординате на величины ±0.5.

Для этих видов растров величина максимальной абсолютной погрешности квантования увеличивается, удовлетворяет соотношению (3.2) и не превосходит 1.

CvM(z)=[z]-=«

Очевидно, что характер возникающих искажений дискретизации для этих

-2 -1 1

84 i i+1

-1.5 -0.5 0.5 1.5 a) [+1]* -2-10 1 2 растров такой же, как на рис. 3.12.

Максимальная абсолютная погрешность квантования при использовании ОФР (3.13) и (3.14) может быть уменьшена до величины 0.5, если определить координаты центров интервалов квантования (и, соответственно, координаты центров ячеек растра и соответствующих им пикселов) не целыми числами, а величинами полусумм соседних целых чисел (так, как это реализовано в OpenGL [133]), что компенсирует сдвиги интервалов квантования и ячеек растра:

-1.5 -0.5 0.5 1.5 б) [-if

0.5 /-1 i i-0.5

Рис. 3.15. Однородные разбиения [+1] и [-1] и их интервалы квантования z(+)=[z]++0.5, z(-)=[z]~-0.5.

В этом случае интервалы квантования (см. рис. 3.15) полностью идентичны интервалам квантования на рис. 3.10, формирующиеся растры (см. рис. 3.16) полностью идентичны растрам на рис. 3.11, а возникающие искажения дискретизации такие же, как на рис. 3.12. Единственное отличие состоит в том, что ячейки растра не индексируются целыми числами, а координируются числами, дробная часть которых составляет величину 0.5 (показаны на рис. 3.16).

3.15)

1.5 0.5 о

-0.5 -1.5

-1.5 -0.5 я 0.5 1.5 а) [-l,+l]

1.5

0.5 о

-0.5 -1.5

0.5 о

-0.5 -1.5 X

-1.5 -0.5 q 0.5 1.5 в) [-1,-1]'

-1.5 -0.5 q 0.5 1.5 г) [+1,-1]*

Рис. 3.16. Структура однородных растров И,+1]*, [+1,+1]*, [-1,-1]* и [+1,-1]*

Во всех рассмотренных ОФР принадлежащими ячейке являлись две смежные ее стороны и замыкающий их узел растровой сетки. При этом ВПГ ячейки полностью определялся двумя ортогональными компонентами, которые в свою очередь определяли принадлежащий ячейке узел растровой сетки.

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

11

На рис. 3.17 показано, как в результате действия ОФР Cv образуется квазиоднородный растр, составленный из двух типов ячеек (рис. 3.17 а), чередующихся на растре в шахматном порядке. При этом образуются периодически повторяющиеся квазиячейки двух типов (рис. 3.17 в), составленные из четырех смежных ячеек растра. О

-к t t

А > \

1 1 1 ! а) ячейки растра б) растр в) квазиячейки растра jj

Рис. 3.17. Структура квазиоднородного растра (ОФР Cv ) ii

Оператор Cv порождает всего восемь типов растров - растр, показанный на рис. 3.17 б, три производных от него растра, получаемых поворотами на 90°, 180° и 270°, и четыре производных растра, получаемых зеркальными отражениями.

Все эти растры анизотропны и приводят к таким же искажениям дискретизации, какие возникают при фор

Рис. 3.18. Искажения дискретизации ОФР Cv* мировании однородных растров (см. рис. 3.18).

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

- каждая граница должна принадлежать одной и только одной из двух прилегающих к ней ячеек;

- каждый узел должен принадлежать одной и только одной из четырех прилегающих к нему ячеек.

Соблюдение этих условий может быть достигнуто за счет применения ОФР Cvs на основе стохастического квантования, при котором принадлежность ячейкам границ и узлов растровой сетки определяется выбором ячеек, прилегающих к каждой границе и к каждому узлу растровой сетки в соответствии с заданным распределением вероятностей (по жребию).

На рис. 3.19 а показан растр, полученный путем стохастического квантования с равными вероятностями выбора ячеек. Очевидно, что в таком растре образуется большое количество типов ячеек (всего 256 типов), различающихся по принадлежности прилегающих к ним границ и узлов растровой сетки. Так на рис. 3.19 все 25 ячеек изображенного фрагмента растра имеют различные типы и не повторяются.

Характер искажений дискретизации диагональных узловых прямых на растре, полученном путем стохастического квантования, показан на рис. 3.19 б. Как видно из рисунка, искажения имеют вид нерегулярных осцилляций - наблюдаются одиночные всплески (эффект зубцов) и группы подряд идущих всплесков (лестничный эффект). J □

1 ' \ 1 '

1 к .1 и а) растр б) искажения дискретизации

Рис. 3.19. Структура нерегулярного растра (ОФР Cvs) и искажения дискретизации на нем

Рассмотренные искажающие эффекты дискретизации точечных ОФР на диагональных прямых сведены в табл. 3.3, из которой можно сделать следующие выводы:

ЗАКЛЮЧЕНИЕ

В работе получены следующие основные выводы и результаты.

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

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

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

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

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

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

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

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

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

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

11. Разработано инструментальное технологическое программное средство - двухтактный интерпретатор Pilot, использованный при создании программного обеспечения, который обеспечивает высокий уровень автоматизации работ по созданию исследовательского, технологического и специализированного программного обеспечения, что позволяет создавать программные и информационные продукты для многоцелевого использования и для создания автоматизированных систем обработки графической информации различного назначения.

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

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

Результаты выполненных исследований позволяют сформулировать следующие возможные перспективные направления их развития.

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

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

3. Большой познавательный и научный интерес представляет возможность применения гиперрастровой модели для разработки дискретной гиперрастровой планиметрии на основе замены понятия конгруэнтности в непрерывной геометрии понятием толерантности в дискретной геометрии.

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

1. Александров А.Д., Нецветаев Н.Ю. Геометрия. - М.: Наука, 1990. - 672 с.

2. Александрян Р.А., Мирзаханян Э.А. Общая топология. М.: Высшая школа, 1979. - 336 с.

3. Анисимов Б.В., Курганов В.Д., Злобин В.К. Распознавание и цифровая обработка изображений. М.: Высшая школа, 1983. - 295 с.

4. Артюшенко В.М., Шелухин О.И., Афонин М.Ю. Цифровое сжатие видеоинформации и звука. М.: Дашков и К°, 2003. - 426 с.

5. Бакут П.А., Колмогоров П.С. Сегментация изображений: Методы выделения границ областей // Зарубежная радиоэлектроника. 1987. - № 10. - С. 25-46.

6. Бакут П.А., Колмогоров П.С., Варновицкий Н.Э. Сегментация изображений: методы пороговой обработки // Зарубежная радиоэлектроника. -1988. № 4. - С. 6-24.

7. Баранова Н.С., Бурцев В.А., Красильников И.Г. и др. Векторизация тексто-графических изображений // ГИС-обозрение. 1995. - № 1. - С. 17-19.

8. Бишоп Р.Л., Криттенден Р.Дж. Геометрия многообразий. -М.: Мир, 1967. 335 с.

9. Бобков В.А., Кислюк О.С., Хамидуллин А.В. Формирование растровых графических изображений пространственных объектов, построенных методом конструктивной геометрии // Программирование. 1989. -№ 3. - С. 88-92.

10. Бонгард М.М. Проблема узнавания. М.: Наука, 1967. - 320 с.

11. Брилинг Н.С. Черчение. М.: Стройиздат, 1989. - 420 с.

12. Бутаков Е.А., Островский В.И., Фадеев И.Л. Обработка изображений на ЭВМ. М.: Радио и связь, 1987. - 240 с.

13. Васин Ю.Г. Математические модели структурированного описания графических изображений // Автоматизация обработки сложной графической информации. Горький: Изд-во Горьк. ун-та, 1984. - С. 92-117.

14. Васин Ю.Г., Крахнов А.Д. Метод от общего к частному в задачах дискретной геометрии // Автоматизация обработки сложной графической информации. Горький: Изд-во Горьк. ун-та, 1986. - С. 67-80.

15. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. М.: ДИАЛОГ-МИФИ, 2003.-384 с.

16. Вендровский К.В., Вейцман А.И. Фотографическая структурометрия.- М.: Искусство, 1982. 270 с.

17. Виттих В.А., Сергеев В.В., Сойфер В.А. Обработка изображений в автоматизированных системах научных исследований. М.: Наука, 1982. - 214 с.

18. Всеобщая история искусств. Т. VI. - Искусство 20 столетия. - Кн. 1.- М.: Искусство, 1965. 480 с.

19. Гардан И., Люка М. Машинная графика и автоматизация проектирования. М.: Мир, 1988. - 300 с.

20. Гель Б.Ф., Комиссарчук А.А. Алгоритм поиска объектов на дис-кретизированном изображении // Тез. докл. II Всесоюз. конф. по автоматизированным системам обработки изображений. Львов, 1986. - С. 73-75.

21. Гилой В. Интерактивная машинная графика: структуры данных, алгоритмы, языки. М.: Мир, 1981. - 384 с.

22. Гильберт Д., Кон-Фоссен С. Наглядная геометрия. М.: Наука, 1981. - 344 с.

23. Голованов Н.Н. Геометрическое моделирование. М.: Наука, 2002. - 472 с.

24. Горелик С.А., Кац Б.М., Киврин В.И. Телевизионные измерительные системы. -М.: Связь, 1980. 189 с.

25. Гришин М.П. Автоматический ввод и обработка фотографическихизображений на ЭВМ. -М.: Энергия, 1976. 156 с.

26. Гуревич С.Б. Эффективность и чувствительность телевизионных систем. -M.-JL: Энергия, 1964. -344 с.

27. ДеМерс М.Н. Географические информационные системы. М.: Дата+, 1999.-507 с.

28. Денисов Д.А., Низовкин В.А. Сегментация изображений на ЭВМ // Зарубежная радиоэлектроника. 1985. - №10. - С. 5-31.

29. Джеймс Т. Теория фотографического процесса. JL: Химия, 1980. - 672 с.

30. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976.-512 с.

31. Журавлев Ю.И., Гуревич И.Б. Распознавание образов и анализ изображений // Искусственный интеллект. Кн. 2. - Модели и методы. - М.: Радио и связь, 1990.-304 с.

32. Завалишин Н.В., Мучник И.Б. Модели зрительного восприятия и алгоритмы анализа изображений. М.: Наука, 1974. - 344 с.

33. Захаров А.В., Мурынов А.И., Сапегина J1.H. Алгоритмы и программное обеспечение центроидной векторизации растровых изображений // Тез. докл. V Росс, унив.-акад. науч.-практ. конф. Ч. 8. - Ижевск, 2001. - С. 35-36.

34. Захаров А.В., Мурынов А.И., Сапегина JT.H. Микровекторизация картографических изображений // Тез.докл. IV Росс, унив.-акад. науч.-практ. конф. -Ч. 2.-Ижевск, 1999.-С. 171-172.

35. Казанцев И.Г. Выделение прямолинейных границ на цифровых изображениях с помощью преобразования Радона // Автоматизированная обработка визуальной информации. Новосибирск, 1989. - С. 29-39.

36. Казанцев Н.Н., Флейс М.Э, Яровых В.Б. Проекционные преобразования в геоинформационных системах // ГИС-обозрение. 1995. - № 2 (5). - С. 23-25.

37. Казанцев Н.Н., Флейс М.Э., Яровых В.Б. Использование разнородных пространственных данных в геоинформационных системах // ГИС-обозрение. -1994.-№ 1.-С. 22-24.

38. Кайнц В. Классификация моделей цифровых картографических данных // Картография. Вып. 4. - Геоинформационные системы. - М.: Картгео-центр-Геодезиздат, 1994.-С. 83-88.

39. Карасев А.А. Векторно-топологическое представление данных в цифровой картографии // Мир ПК. 1995. - № 12. - С. 3-8.

40. Касперович JI.B. Быстрый алгоритм оконтуривания объектов на изображениях // Автометрия. 1990. - № 1. - С. 11-16.

41. Кийко В.М., Шлезингер М.И. Алгоритм выделения отрезков осевых линий на графических изображениях. Киев: АН УССР, 1983. - 117 с.

42. Климов В.Е. Графические системы САПР. М.: Высшая школа, 1990. -142 с.

43. Кобаяси Ш., Номидзу К. Основы дифференциальной геометрии. -Т. 1.-М.: Наука, 1981.-344 с.

44. Ковалевский В.А. Методы оптимальных решений в распознавании изображений. М.: Наука, 1976. - 328 с.

45. Козлов В.Н. Способ оценки похожести изображений, основанный на преобразованиях подобия // ЖВМиМФ. Т. 40. - 2000. - № 5. - С. 797-808.

46. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. -М.: Наука, 1981. 544 с.

47. Кондратьев В.В., Утробин В.А. Основы теории активного восприятия изображений. Нижний Новгород: Вектор, 1997. - 249 с.

48. Коновалова Н.В., Капралов Е.Г. Введение в ГИС. М.: Библион, 1997. -160 с.

49. Королев Ю. Тенденции развития моделей данных в ГИС и их значения для ГИС-приложений // ArcReview: современные информационные технологии. 1997. - № 3. - С. 15; - 1997. - № 2. - С. 2.

50. Королев Ю.К. Модели данных геоинформационных систем // Инф. бюлл. ГИС-ассоциации. 1998. -№ 2 (14). - С. 70-72; -1998. - № 3 (15). - С. 68-69.

51. Королев Ю.К. О роли растровой информации в ГИС // ArcReview: современные информационные технологии. 1988. - № 1 (4). - С. 14-15.

52. Королев Ю.К. Общая геоинформатика. Ч. 1. - Теоретическая геоинформатика. Вып. 1. - М.: Дата+, 1998. - 119 с.

53. Корриган Дж. Компьютерная графика. М.: Энтроп, 1995. - 352 с.

54. Котов И.И., Полозов B.C., Широкова J1.B. Алгоритмы машинной графики. -М.: Машиностроение, 1977. 200 с.

55. Коулмэн Г.Б., Эндрюс Х.С. Сегментация изображения при помощи автоматической классификации // ТИИЭР. Т. 67. - 1979. - № 5. - С. 82-97.

56. Кошкарев А.В., Сорокин А.Д. Форматы и стандарты цифровой пространственной информации // ГИС-обозрение. 1995. - № 1. - С. 40-45.

57. Кошкарев А.В., Тикунов B.C. Геоинформатика М.: Картгеоцентр-Геодезиздат, 1993. - 213 с.

58. Левицкая Л.Н. Искажающие эффекты дискретизации графических изображений на растре // Материалы XXXII Междунар. конф. «Информационные технологии в науке, социологии, экономике и бизнесе» // Прилож. к журн. «Открытое образование». 2006. - С. 173-174.

59. Левицкая Л.Н. Точечные операторы формирования растровых представлений пространственной структуры изображений и эффекты дискретизации // Вестник Ижевского государственного университета. 2006. - №.1. - С. 10-17.

60. Левицкая Л.Н., Микрюков А.В., Мурынов А.И., Телегина М.В. Графическая информация в информационном пространстве // Тез. докл. Межрег. науч.-пракг. конф. «Развитие информационного пространства». Ижевск, 2005. - С. 187-189.

61. Левицкая Л.Н., Мурынов А.И. Гиперрастровая модель изображений // Вестник Ижевского государственного университета. 2006. - №.1. - С. 17-24.

62. Лепихов Ю.Н., Шибаева И.В. Формирование секторных цепных кодов линейных структурных элементов изображений // Тр. Междунар. симп. «Надежность и качество». Ч. II. - Пенза: 2004. - С. 470-474.

63. Либенсон М.Н., Хесин А.Я., Янсон Б.А. Автоматизация распознавания телевизионных изображений. М.: Энергия, 1975. - 160 с.

64. Лихтциндер Б.Я. Автоматизация расчета характеристик трафика в сетях ATM // Инфокоммуникационные технологии. Т. 1. - 2003. - № 1. - С. 47-53.

65. Лихтциндер Б.Я., Кузякин М.А., Росляков А.В., Фомичев С.М. Интеллектуальные сети связи. М.: Эко-Трендз, 2000. - 206 с.

66. Микрюков А.В., Мурынов А.И., Сапегина Л.Н. Историко-лингвистическая геоинформационная система Камско-Вятского междуречья // Тез. докл. V Росс, унив.-акад. науч.-практ. конф. Ч. 8. - Ижевск, 2001. - С. 34-35.

67. Микрюков А.В., Мурынов А.И., Сапегина Л.Н. Экспертная геоинформационная система для анализа территориального распределения уровня заболеваемости городского населения // Тез. докл. V Росс, унив.-акад. науч.-практ. конф. Ч. 8. - Ижевск, 2001. - С. 33-34.

68. Микрюков А.В., Мурынов А.И., Сапегина Л.Н., Телегина М.В. Разработка и применение новых технологий создания цифровых карт // Тез. докл. V Росс, унив.-акад. науч.-практ. конф. Ч. 8. - Ижевск, 2001. - С. 40-41.

69. Минаси М. Графический интерфейс пользователя. М.: Мир, 1996. - 160 с.

70. Михайленко В.Е., Кислицкий В.Н., Лященко А.А. и др. Геометрическое моделирование и машинная графика в САПР. Киев: «Выща школа», 1991. - 374 с.

71. Мураховский В.И. Компьютерная графика. -М.: АСТ-Пресс СКД, 202 с.

72. Мурынов А.И. Модель пространственной структуры для представления цифровой карты // Вестник Удмуртского университета. 1996. - № 3. - С. 151-159.

73. Мурынов А.И. Объектно-топологическая модель пространственных данных для ГИС // Тез.докл. IV Росс, унив.-акад. науч.-практ. конф.- Ч. 2.1. Ижевск, 1999.-С. 169-170.

74. Мурынов А.И. Объектный формат пространственных данных для ГИС // Материалы IV Всерос. форума «Геоинформационные технологии. Управление. Природопользование. Бизнес». М., 1997. - С. 124-126.

75. Мурынов А.И. Сапегина JI.H. Анализ растровых изображений на основе центроидной фильтрации. // Тез. докл. V Росс, унив.-акад. науч.-практ. конф. Ч. 8. - Ижевск, 2001. - С. 39-40.

76. Мурынов А.И., Вдовин A.M. Анализ пространственной структуры изображений методом центроидной фильтрации // Вестник Ижевского государственного университета. 2002. - Вып.З. - С. 3-11.

77. Мурынов А.И., Вдовин A.M., Лялин В.Е. Оценка геометрико-топологических параметров деталей изображений на основе метода центроидной фильтрации // Химическая физика и мезоскопия. Т.4. - 2002. - №2. - С. 161-177.

78. Мусин О.Р. Цифровые модели для ГИС // Инф. бюлл. ГИС-ассоциации. 1998. - № 4 (16). - С. 30-32; 1998. - № 5 (17). - С. 28-29.

79. Нарасимхан Р. Лингвистический подход к распознаванию образов // Автоматический анализ сложных изображений. М.: Мир, 1969. - С. 22-49.

80. Нарасимхан Р. Синтаксическая интерпретация классов изображений // Автоматический анализ сложных изображений. М.: Мир, 1969. - С. 50-64.

81. Никитаев В.Г., Шаронов С.Н. Метод преобразования координат для адаптивной сегментации изображения // Измерительная техника. 1990. № 12. - С. 9-10.

82. Ньюмен У., Спрулл Р. Основы интерактивной машинной графики. -М.: Мир, 1976.-562 с.

83. Оре О. Теория графов: М.: Наука, 1968. - 352 с.

84. Павлидис Т. Алгоритмы машинной графики и обработки изображений. М.: Радио и связь, 1986. - 400 с.

85. Петров МН, Молочков В.П Компьютерная графика. СПб.: Питер, 2002. - 736 с.

86. Пивоваров И.В. Эффективное кодирование цветных графических изображений для передачи по каналам связи телекоммуникационных систем // Ж.

87. АН Украины «Искусственный интеллект» 2005. - №3. - С. 641-648.

88. Позняк Э.Г., Шикин Е.В. Дифференциальная геометрия. М.: Изд-во МГУ, 1990.-384 с.

89. Пономаренко С.И. Пиксел и вектор. Принципы цифровой графики. -СПб.: БХВ-Петербург, 2002. 496 с.

90. Понтрягин JI.C. Непрерывные группы. М.: Наука, 1984. - 520 с.

91. Препарата Ф., Шеймос М. Вычислительная геометрия: М.: Мир, 1989. - 478 с.

92. Престон К., Дафф М. Дж. Б., Левьяльди С. и др. Основы клеточной логики с приложениями к обработке изображений // ТИИЭР. Т. 67. -1979. -№ 5. С. 149-184.

93. Прэтт У. Цифровая обработка изображений. Кн. 1. - М.: Мир, 1982. -312 е.;-Кн. 2.-М.: Мир, 1982.-480 с.

94. Райан Д. Инженерная графика в САПР. М. Мир, 1989. - 391 с.

95. Роджерс Д Алгоритмические основы машинной графики.-М: Мир, 1989.-512 с.

96. Роджерс Д., Адаме Дж. Математические основы машинной графики. -М.: Машиностроение, 1980. 240 с.

97. Розенфельд А. Распознавание и обработка изображений для цифровых вычислительных машин. М.: Мир, 1972. - 230 с.

98. Розенфельд А., Дейвис Л.С. Сегментация и модели изображения // ТИИЭР. Т. 67. - 1979. -№ 5. - С. 71-81.

99. Романычева Э.Т., Иванова А.К., Куликов А.С. и др. Разработка и оформление конструкторской документации радиоэлектронной аппаратуры. -М.: Радио и связь, 1989. 448 с.

100. Рудой Б.П., Горбачев В.Г., Власов М.Ю. Концептуальные топологические отношения в ГИС // Инф. бюлл. ГИС-ассоциации. -1996. № 5 (7). - С. 62-63.

101. Садыков С.С., Самандаров И.Р. Скелетизация бинарных изображений // Зарубежная радиоэлектроника. 1985. - № 11. - С. 30-37.

102. Салищев К.А. Картоведение. М.: Изд-во МГУ, 1982. - 408 с.

103. Скворцов А.В. Геоинформатика. Томск: Изд-во Том. ун-та, 2006. - 336 с.

104. Соболев Н.А. Общая теория изображений. М.: Архитекгура-С, 2004. - 672 с.

105. Собчук Т.В. Сегментация линейных объектов для автоматизированной генерализации // ГИС-обозрение. 1996. - № 3-4 (9). - С. 50-51.

106. Условные знаки для топографических планов масштабов 1:5000, 1:2000, 1:1000, 1:500.-М.: Недра, 1989.-286 с.

107. Условные знаки, образцы шрифтов и сокращения для топографических карт масштабов 1:200 000 и 1:500 000. -М.: ВТУ ГШ, 1963. 58 с.

108. Ш.Утробин В.А. Информационные модели системы зрительного восприятия для задач компьютерной обработки изображений. Нижний Новгород, Изд-во Нижегородского гос. тех. ун-та, 2001. - 234 с.

109. Файн B.C. Опознавание изображений. М.: Наука, 1970. - 296с .

110. Фокс А., Пратт М. Вычислительная геометрия. Применение в проектировании и на производстве. М.: Мир, 1982. - 304 с.

111. Фоли Дж., ван Дэм А. Основы интерактивной машинной графики. -Ч. 1.-М.: Мир, 1985.-436 е.;-Ч. 2.-М.:Мир, 1985.-564 с.

112. Фризер X. Фотографическая регистрация информации. -М: Мир, 1978. 670 с.

113. Фу К. Структурные методы в распознавании образов. М.: Мир, 1977. - 320 с.

114. Фурман Я.А., Кревецкой А.В. Передреев А.К. и др. Введение в контурный анализ и его приложения к обработке изображений и сигналов. М.: Физматлит, 2002. - 592 с.

115. Халугин Е.И., Жалковский Е.А., Жданов Н.Д. Цифровые карты. М.: Недра, 1992.-419 с.

116. ХруповС. Организация данных в ГИС // ГИС-обозрение. -1997. № 2. - С. 38-41.

117. Хюккель М. Оператор нахождения контуров на кодированных изображениях // Интегральные роботы. Вып. 1. - М.: Мир, 1973. - С. 225-240.

118. Цветков В.Я. Геоинформационные системы и технологии. М.: Финансы и статистика, 1998. - 288 с.

119. Чукин Ю.В. Графические информационные системы // Зарубежная радиоэлектроника. 1985. - № 10. - С. 31-55.

120. Чукин Ю.В. Структуры данных для представления изображений //

121. Зарубежная радиоэлектроника. 1983. - № 8. - С. 85-107.

122. Чэн Ш.-К. Принципы проектирования систем визуальной информации. М.: Мир, 1994. - 408 с.

123. Шаши Ш., Санжей Ч. Основы пространственных баз данных. М.: КУДИЦ-ОБРАЗ, 2004, - 336 с.

124. Шерман Г. Квазитопологический метод распознавания линейных изображений // Автоматический анализ сложных изображений. М.: Мир, 1969.-С. 11-21.

125. Шикин Е.В., Боресков А.В. Компьютерная графика. Динамика, реалистические изображения. М.: ДИАЛОГ-МИФИ, 1995. - 288 с.

126. Шлезингер М.И. Математические средства обработки изображений.- Киев: Наукова думка, 1989. 200 с.

127. Шрейдер Ю.А. Пространства толерантности // Кибернетика, 1970, № 2. С. 37-49.

128. Шрейдер Ю.А. Равенство, сходство, порядок. М.: Наука, 1971. - 257 с.

129. Эйнджел Э. Интерактивная компьютерная графика -М.: Вильяме, 2001. 592 с.

130. Энджел И. Практическое введение в машинную графику. М.: Радио и связь, 1984,- 136 с.

131. Эндрюс Г. Применение вычислительных машин для обработки изображений. -М.: Энергия, 1977. 160 с.

132. Ярославский Л.П. Цифровая обработка сигналов в оптике и голографии: Введение в цифровую оптику. -М.: Радио и связь, 1987. — 296 с.

133. Arcelli С., di Baja G.S. A one-pass two-operation process to detect the skeletal pixels the 4-distance transform // IEEE Trans, on Pattern Recogn. and Mach. Intell. V. 11.- 1989.-P. 411-414.

134. Ballard D. Generalizing the Hough transform to detect arbitrary shapes // Pattern Recogn.-V. 13. 1981. -№ 2. -P. 111-122.

135. Bresenham J.E. A Linear Algorithm for Incremental Digital Display of Circular Arcs // CASM. V. 20. -1977. - P. 100-106.

136. Bresenham J.E. Algorithm for Computer Control of a Digital Plotter // IBM System J. V. 4. - 1965. - P. 25-30.

137. Cederberg R. Chain-link coding and segmentation of raster scan devices // Сотр. Graph, and Image Proc. V. 10. - 1979. - № 2. - P. 224-234.

138. Fleck M.M. Local Rotational Symmetries // Tech. Rep. 852. MIT Press. - 1985.- 155 p.

139. Freeman H. On the encoding of arbitrary geometric configurations // IEEE Trans. Electron. Сотр. V. 10. - 1961. - № 2. - P. 260-268.

140. Freeman H. Shape description via nhe use of critical points // Pattern recogn.-V. 10.- 1978.-№3.-P. 159-169.

141. Furst M.A., Caines P.E. Edge Detection with Image Enhancement via Dynamic Programming // Сотр. Vision, Graph, and Image Proc. V. 33. -1986. - №3. - P. 263-279.

142. Gapson D.W. An improved algorithm for the sequentional extraction of boundaries from a raster scan // Сотр. Graph, and Image Proc. V. 28. -1984. - № 1. - P. 109-125.

143. Haralick R.M. Structural pattern recognition, homomorphisms and arrangements //Pattern Recogn. V. 10. - 1978.-№ 3.-P. 223-236.

144. Kittler J. and Paler K. An Absorption Edge Detector // Сотр. Graph. -1983. №8. - P.345-350.

145. Lam L., Lee S.-W. Thinning methodologies A comprehensive survey // IEEE Trans. Pattern Anal, and Mach. Intell. - V. 14. - 1992. - № 9. - P. 869-885.

146. Murynov A.I., Levitskaya L.N., Shibaeva I.V. The Model Discretely-Planimetry Graphic Structures of the Image Graphic // Book of Abstracts of the 6th International Congress on Mathematical Modelling. Nizhny Novgorod, 2004. - P. 258.

147. O'Gorman L. KxK thinning // Сотр. Vision, Graph, and Image Proc. -V. 51.- 1990,-№2.-P. 195-215.

148. Paven K., Deepak B. Pseudo one thinning algorithm // Pattern Recogn. -V. 12. 1991. -№ 9. -P. 543-555.

149. Pavlidis T. A thinning algorithm for discrete binary images // CGIP. -V.13. 1980. - P. 142-157.

150. Pavlidis Т., Horowitz S. Segmentation of plane curves / IEEE Trans. Сотр. V. 23. - 1974. - № 8. - P. 860-870.

151. Rosenfeld A. A characterization of parallel thinning algorithms // Information and Control. V. 29. - 1975. - P. 286-291.149