Содержание к диссертации
Введение
Глава 1. Задачи моделирования и анализа пространственной структуры графических изображений и методы их решения 17
1.1. Графические изображения 17
1.2. Задачи моделирования и анализа структуры изображений 25
1.3. Модели и методы моделирования и анализа структуры изображений 28
1.4. Выводы и постановка цели и задач исследований 42
Глава 2. Структурно-графикационная модель изображений 46
2.1. Сигнатурно-кодовая карта изображения 46
2.2. Трансформационный анализ пространственной структуры изображений 51
2.3. Пространственно-структурные свойства изображений 62
2.4. Графикационная структура изображений 66
2.5. Полученные результаты и выводы. 69
Глава 3. Формирование растровых представлений пространственной структуры изображений и эффекты дискретизации 71
3.1. Точечные операторы формирования растра , 71
3.2. Линейные и планарные операторы формирования растра 88
3.3. Геометрические аберрации на растре 94
3.4. Полученные результаты и выводы. 96
Глава 4. Дискретно-планиметрическая модель гиперрастра 97
4.1. Толерантность точек плоскости, индуцированная растровой сеткой 97
4.2. Формирование гиперрастра 107
4.3. Структура и свойства гиперрастра. 109
4.4. Операторы формирования гиперрастра 111
4.5, Эффекты дискретизации на гиперрастре 113
4.6. Полученные результаты и выводы 115
Глава 5. Методы, алгоритмы, программное обеспечение и технология обработки графической информации 116
5.1. Сравнительный анализ результатов распознавания структурных элементов изображения на растре и на гиперрастре 116
5.2. Метод центроидной релаксации , 118
5.3. Алгоритмы, программное обеспечение и технология обработки графической информации 120
5.4. Экспериментальные данные и результаты 127
5.5. Полученные результаты и выводы 130
Заключение 133
Литература
- Задачи моделирования и анализа структуры изображений
- Пространственно-структурные свойства изображений
- Линейные и планарные операторы формирования растра
- Операторы формирования гиперрастра
Введение к работе
Актуальность темы. Массовая компьютеризация и информатизация всех отраслей знаний стимулировали разработку новых математических моделей исследуемых объектов в различных предметных областях. К числу таких объектов относятся изображения, предоставляющие большое количество информации об изображенных объектах в наглядной и образной форме. В то же время возможности извлечения полезной информации из изображений определяются их пространственной структурой. Поэтому задачи моделирования и анализа структуры изображений возникают в различных прикладных областях при решении самых разнообразных задач.
Одной из основных и первичных форм представления изображений является их дискретное представление в растровой форме. Влияние собственной пространственной структуры растра приводит к возникновению различных искажающих эффектов дискретизации при воспроизведении структуры изображений, что существенно осложняет их последующий анализ. Необходимы учет особенностей дискретной геометрии растра и систематический анализ эффектов дискретизации для реализации таких методов обработки графической информации, которые компенсировали бы влияние указанных эффектов. Это вызывает потребность разработки дискретно-планиметрических моделей пространственной структуры изображений для построения корректных и максимально точных методов их анализа.
Разработке и исследованию моделей изображений и методов их анализа и синтеза уделено большое внимание в работах отечественных и зарубежных ученых: Брезенхама Дж., БонгардаМ.М, Васина Ю.Г., Журавлева Ю.И., Ковалевского В.А., Лебедева Д.С., МарраД., Мучника И.Б., Нарасимхана Р., ПавлидисаТ., ПрэттаУ., Роджерса Д., Розенфельда А., СтокхэмаТ., Файла B.C., ФрименаХ., Фу К., Харалика P.M., Цуккермана И.И., Шермана Г, Ярославского Л.П, и др.
Однако достигнутые в настоящее время результаты не решают в полной мере проблему эффективного дискретно-планиметрического представления изображений в силу неполного учета особенностей дискретной геометрии растра и использования частных приемов компенсации искажений дискретизации, направленных на улучшение визуального восприятия растровых изображений, но при этом, ни в какой мере не способствующих улучшению показателей качества их автоматического анализа. Таким образом, актуальной является задача поиска такого эффективного представления для использования в системах обработки графической информации.
Целью работы является разработка новых эффективных дискретных представлений пространственной структуры графических изображений, их математических моделей и методов анализа, применение которых качественно повышает возможности решения практических задач распознавания изображений, а также реализация разработанных моделей и методов для решения различных прикладных задач, связанных с обработкой графической информации.
Для достижения поставленной цели в работе решаются следующие задачи: разработка метода анализа пространственной структуры изображений, обеспечивающего объективное построение полного и точного описания структуры графических изображений и выявляющего все существенные геометрико-топологические свойства, характеристики и взаимосвязи его структурных элементов; разработка математической модели пространственной структуры графических изображений, учитывающей пространственный план их построения и графические факторы их воспроизведения; исследование различных способов формирования дискретных растровых представлений пространственной структуры графических изображений и выявление возникающих на растре искажающих эффектов дискретизации структурных элементов изображений; анализ искажающих эффектов дискретизации структурных элементов изображений на растре для построения их дискретных представлений, обладающих минимальной неопределенностью; разработка и исследование дискретно-планиметрической модели изображений, обеспечивающей дискретное представление их пространственной структуры с минимальной неопределенностью; сравнительный анализ методов распознавания структурных элементов изображения в их различных дискретных представлениях; разработка метода обнаружения, распознавания и оценки дискретно представленных структурных элементов изображений; разработка эффективных вычислительных схем и алгоритмов формирования, преобразования и анализа дискретных представлений пространственной структуры графических изображений; разработка технологии и создание программного обеспечения обработки графической информации, реализующих разработанные средства и методы моделирования и анализа дискретных представлений пространственной структуры графических изображений; проведение экспериментальных исследований разработанных средств и методов для оценки их эффективности и возможностей использования при решении различных прикладных задач, связанных с обработкой графической информации.
Объектом исследования являются графические изображения, их особенности, свойства и характеристики, их пространственная структура, математические модели этой структуры и ее дискретных представлений, способы формирования и преобразования таких представлений и возможности их использования в системах обработки графической информации.
Предметом исследования являются методы моделирования и анализа пространственной структуры графических изображений, способы получения дискретно-планиметрических представлений этой структуры и построения их математических моделей, основанные на этих моделях методы обнаружения, распознавания и оценки структурных элементов изображений, реализующие эти методы алгоритмы, программы и технологии обработки графических изображений, а также оценки их эффективности и возможностей практической реализации при решении различных
8 прикладных задач, связанных с обработкой графической информации.
Методы исследования. В работе применялись теоретические и экспериментальные методы исследования.
Теоретические исследования основаны на использовании функционального анализа, топологии, аффинной и дифференциальной геометрии, теории графов, теории пространств толерантности, основ машинной графики и вычислительной геометрии, теории обработки и анализа изображений, распознавания образов.
В экспериментальных исследованиях разработанных моделей и алгоритмов использовались методы моделирования пространственных структур, системного анализа, цифровой обработки изображений и машинной графики, системного программирования.
Достоверность изложенных положений работы подтверждается результатами практического применения разработанных методов, алгоритмов, программных средств и технологии обработки графической информации, научными трудами и апробациями созданного научно-технического продукта на представительных научных форумах. Достоверность и обоснованность полученных в работе результатов и выводов подтверждается при их сравнительном анализе с известными результатами современных исследований и разработок.
Теоретические положения, установленные в работе, обосновываются адекватным выбором исходных посылок и последовательным применением математического аппарата при получении из них выводов, а также верификацией этих выводов данными систематического исследования полученных аналитических результатов.
Достоверность экспериментальных результатов подтверждается их согласованностью с теоретическими выводами, обоснованным выбором корректных критериев при построении алгоритмов обработки информации, воспроизводимостью результатов на больших объемах экспериментального материала при выполнении серий вычислительных экспериментов с большим количеством изменяемых значений влияющих параметров, наглядностью интерпретации по-
9 лученных практических результатов обработки информации.
На защиту выносятся результаты разработки и исследования математических моделей дискретных представлений пространственной структуры графических изображений, методов и алгоритмов их формирования, преобразования и анализа, а также результаты практической реализации этих моделей, методов и алгоритмов - технология и программные средства обработки изображений для решения различных прикладных задач, связанных с обработкой графической информации, в том числе: метод трансформационного анализа пространственной структуры изображений, реализующий схему восходящего анализа, обеспечивающий объективное построение полного и точного описания структуры графических изображений и выявляющий все существенные геометрико-топологические свойства, характеристики и взаимосвязи их структурных элементов; структурно-графикационная модель изображений, учитывающая пространственный план их построения и графические факторы их воспроизведения; результаты исследования различных способов формирования дискретных растровых представлений пространственной структуры графических изображений и выявления возникающих на растре искажающих эффектов дискретизации структурных элементов изображений; результаты анализа искажающих эффектов дискретизации структурных элементов изображений на растре на основе использования векторов принадлежности границ ячеек растровой сетки, необходимые для построения их дискретных представлений, обладающих минимальной неопределенностью; дискретно-планиметрическая модель гиперрастра, построенная на основе теории пространств толерантности и обеспечивающая дискретное представление пространственной структуры изображений с минимальной неопределенностью; результаты сравнительного анализа методов распознавания структурных элементов изображения в их растровом и гиперрастровом дискретных представлениях; метод центроидной релаксации, обеспечивающий обнаружение, распозна-
10 вание и оценку дискретно представленных структурных элементов изображений; эффективные вычислительные схемы и алгоритмы формирования, преобразования и анализа дискретных представлений пространственной структуры графических изображений; технология и программное обеспечение обработки графической информации, реализующие разработанные средства и методы моделирования и анализа дискретных представлений пространственной структуры графических изображений; результаты экспериментальных исследований разработанных средств и методов и оценки их эффективности и возможностей использования при решении различных прикладных задач, связанных с обработкой графической информации.
Научная новизна полученных результатов определяется впервые проведенными исследованиями, в результате которых разработаны новые модели дискретных представлений графических изображений в форме гиперрастра, а также разработаны методы, построены алгоритмы и созданы технология и программные средства обработки, преобразования и анализа дискретных гиперрастровых представлений изображений, что качественно повышает возможности решения практических задач распознавания изображений и, тем самым, вносит существенный вклад в решение задач создания интеллектуальных систем обработки графической информации, в ходе которых: - разработан метод трансформационного анализа пространственной струк туры изображений, реализующий схему восходящего анализа, обеспечивающий объективное построение полного и точного описания структуры графических изображений и выявляющий все существенные геометрико-топологические свойства, характеристики и взаимосвязи их структурных элементов на основе последовательного выделения инвариантов структуры изображений относитель но подгрупп группы аффинных преобразований (трансляций, движений и не рефлексных аффинных преобразований), что позволяет однозначно определить элементы структуры, их пространственные атрибуты и взаимосвязи; - построена структурно-графикационная модель изображений, учиты вающая пространственный план их построения и графические факторы их вос произведения и формирующая на основе трансформационного анализа описа- ниє структуры графического изображения в виде графа, образованного совокупностью структурных элементов, связанных бинарным пространственным отношением смежности; исследованы различные способы формирования дискретных растровых представлений пространственной структуры графических изображений и выявлены различные искажающие эффекты дискретизации структурных элементов изображений на растре; установлено, что при применении любого оператора формирования растра возникают необратимые искажения дискретизации, характер которых непостоянен и существенно зависит от способа формирования растра; проанализированы искажающие эффекты дискретизации структурных элементов изображений на растре; установлено, что различия в искажающих эффектах обусловлены различиями в определении векторов принадлежности границ ячеек растровой сетки, что позволило сформулировать условия, необходимые для построения дискретных представлений изображений, обладающих минимальной неопределенностью; на основе использования теории пространств толерантности разработана дискретно-планиметрическая модель гиперрастра, обеспечивающая дискретное представление пространственной структуры изображений с минимальной неопределенностью - с точностью, определяемой элементами порождающей растровой сетки - узлами, границами и внутренностями ячеек сетки; в результате сравнительного анализа методов распознавания структурных элементов изображения в их растровом и гиперрастровом дискретных представлениях установлена более высокая эффективность гиперрастрового представления, обусловленная характерными для гиперрастра отсутствием необратимых эффектов дискретизации и более высокой точностью представления структурных элементов изображений, в предельных случаях достигающей значений с нулевой погрешностью; разработан метод центроидной релаксации, обеспечивающий эффективное обнаружение, распознавание и оценку дискретно представленных на растре структурных элементов изображений и возможность преобразования их растровых представлений в гиперрастровые за счет получения субпиксельных
12 оценок пространственных атрибутов элементов; разработаны эффективные вычислительные схемы и алгоритмы формирования, преобразования и анализа дискретных представлений пространственной структуры графических изображений, обеспечивающие высокую производительность вычислительных процессов и существенное снижение используемых ресурсов памяти за счет дифференциального цепного кодирования изображений, формируемого на основе анализа результатов их центроидного преобразования, последующей сегментации цепных кодов и распознавания структурных элементов; предложена и обоснована технология обработки графической информации, создано программное обеспечение, реализующее эту технологию и использованное при выполнении экспериментальных исследований, результаты которых позволили определить оценки эффективности и возможностей применения разработанных средств и методов моделирования и анализа дискретных представлений пространственной структуры графических изображений при решении различных прикладных задач, связанных с обработкой графической информации.
Практическая ценность работы заключается в применении новых эффективных представлений, моделей и методов анализа пространственной структуры графических изображений.
Разработано программное обеспечение, реализующее методы и технологию обработки графической информации на основе формирования, преобразования и анализа дискретных гиперрастровых представлений пространственной структуры графических изображений.
Разработанный программный комплекс обеспечивает реализацию эффективных вычислительных схем и алгоритмов обнаружения, распознавания и оценки структурных элементов изображения в их растровом и гиперрастровом дискретных представлениях, взаимные преобразования этих представлений и поддержку растровых форматов графических данных, цепных кодов и структурных описаний изображений, что позволяет использовать этот комплекс совместно с существующими программными средствами обработки изображений для построения интеллектуальных систем и технологий обработки графической информации.
13 Использованное при создании программного обеспечения разработанное инструментальное технологическое программное средство - двухтактный интерпретатор Pilot, обеспечивая высокий уровень автоматизации работ по созданию исследовательского, технологического и специализированного программного обеспечения, в еще большей степени расширяет возможности интеграции разработанных средств и методов моделирования и анализа пространственной структуры изображений, что позволяет создавать программные и информационные продукты для многоцелевого использования и для создания автоматизированных систем обработки графической информации различного назначения.
Результаты экспериментальных исследований разработанных средств и методов и оценки их эффективности и возможностей использования при решении различных прикладных задач, а также опыт их внедрения и эксплуатации при создании программных и информационных продуктов в ряде организаций и предприятий подтверждают целесообразность их использования для качественного повышения возможностей решения практических задач, связанных с обработкой графической информации
Реализация и внедрение результатов работы. Полученные результаты использованы при выполнении 14 НИОКР, выполненных в ИжГТУ, Физико-техническом институте УрО РАН и Удмуртском государственном университете (УдГУ), и внедрены в ряде организаций и предприятий, где они используются для выполнения производственных, опытно-производственных, научно-исследовательских и учебно-методических работ: алгоритмы и комплекс программ автоматизированного дешифрирования изображений объектов местности на космических снимках земной поверхности; программное обеспечение многоцелевого высокоразрешающего анализатора фотоизображений СИН-5 (29 НИИ МО РФ); методики и программы моделирования, анализа и визуализации внутреннего строения пространственных структур сплошных сред (Физико-технический институт УрО РАН); программы технологической подготовки и обработки данных для создания базовых цифровых карт территорий; базовые цифровые карты г. Ижев- ска, г. Сарапула, г. Глазова (Госкомзем Удмуртской республики (УР)), базовая цифровая карта УР (Госкомэкология УР); система программного обеспечения технологической подготовки и документирования цифровых карт (ГУД АГП «Удмуртаэрогеодезия»); программные приложения ГИС Maplnfo 5.0, обеспечивающие функционирование геоинформационной системы «Монитор-Иж» для контроля оперативной обстановки на территории города (Штаб МВД УР); ис-торико-лингвистическая ГИС Камско-Вятского междуречья и экспертные системы мониторинга территориального распределения уровней заболеваемости населения г. Ижевска и Удмуртской республики (УдГУ); алгоритмы и программы обработки и кодирования графической информации (Тульский филиал ОАО «Центр Телеком»); инструментальное технологическое программное средство - двухтактный интерпретатор Pilot, обеспечивающее высокий уровень автоматизации работ по созданию исследовательского, технологического и специализированного программного обеспечения (ИжГТУ); учебно-методические материалы по дисциплинам «Компьютерная графика», «Интерактивные графические системы», «Человеко-машинное взаимодействие» (ИжГТУ).
Разработанные методики, алгоритмы и программы обеспечивают повышение качества выполняемых работ, повышение производительности труда, снижение себестоимости производимой продукции, позволяют создавать программные и информационные продукты для многоцелевого использования и для создания автоматизированных систем обработки графической информации различного назначения.
Апробация работы. Результаты работы докладывались на российских и международных научно-технических конференциях и конгрессах: VI и V Российских университетско-академических научно-практических конференциях (Ижевск, 1999, 2001); IV Международной научно-технической конференции «Информационные технологии в инновационных проектах» (Ижевск, 2003); VI Международном конгрессе по математическому моделированию (Нижний Новгород, 2004); XXXI и XXXII Международных конференциях «Информационные
15 технологии в науке, социологии, экономике и бизнесе» (Украина, Крым, Ялта-Гурзуф, 2004, 2006); V Международной научно-технической конференции «Проблемы техники и технологии телекоммуникаций» (Самара, 2004); VII Международной конференции «Цифровая обработка сигналов и ее применение» (Москва, 2005); Межрегинальной научно-практической конференции «Развитие информационного пространства». (Ижевск, 2005); Научной конференции «Теория управления и математическое моделирование» (Ижевск, 2006); Международной конференции «Информационные технологии в образовании» (Ижевск, 2006).
Публикации. Основные научные результаты по теме диссертации опубликованы в 34 научных работах, в том числе: 5 статей в списке, утвержденном ВАК, 2 статьи в научно-технических журналах и сборниках, 7 тезисов докладов на российских и международных научно-технических конференциях и конгрессах, 19 научно-технических отчетов по 14 НИОКР.
Объем и структура диссертационной работы. Диссертация содержит введение, 5 глав и заключение, изложенные на 148 с. машинописного текста, а также 4 приложения. В работу включены 51 рис., 12 табл., список литературы из 155 наименований. В приложениях представлен акт об использовании результатов работы.
В первой главе анализируются особенности, свойства и характеристики графических изображений, их пространственной структуры и ее графического воспроизведения. Формулируются задачи моделирования и анализа структуры графических изображений и проводится обзор моделей и методов анализа их пространственной структуры.
Во второй главе уточняется и формализуется понятие пространственной структуры графического изображения в ее непрерывном представлении. Основой формализации является анализ трансформаций структуры изображений, позволяющий выявить и определить их структурные элементы, геометрико-топологические свойства, характеристики и взаимосвязи этих элементов. Это позволяет построить математическую модель пространственной структуры графических изображений, учитывающую пространственный план их построения и графические факторы их воспроизведения.
В третьей главе анализируются процессы формирования дискретных растровых представлений пространственной структуры изображений и возникающие при этом эффекты дискретизации. Рассмотрены различные операторы формирования растра для различных типов структурных элементов изображений, возникающие при действии этих операторов искажения дискретизации, а также геометрические аберрации на растре - нарушения фундаментальных геометрических свойств и отношений структурных элементов, обусловленные дискретностью их представления.
В четвертой главе анализируются искажения дискретизации структурных элементов изображений на растре, обусловленные принятием решения об отнесении к ячейкам растра их границ. В результате анализа определяется индуцированное растровой сеткой отношение толерантности точек плоскости и формируется новая структура представления изображений - гиперрастр, составленный из ядер толерантности - ячеек, соответствующих внутренностям ячеек растра, их границам и узлам растровой сетки. Определены операторы формирования гиперрастра для различных типов структурных элементов изображений, обладающие минимальной неопределенностью дискретизации.
В пятой главе описаны разработанные методы, алгоритмы, программное обеспечение и технология обработки графической информации, основанные на использовании дискретных гиперрастровых представлений пространственной структуры графических изображений, а также результаты экспериментальных исследований разработанных средств и методов и оценки их эффективности и возможностей использования при решении различных прикладных задач, связанных с обработкой графической информации.
В заключении диссертационной работы сформулированы основные выводы и результаты выполненных исследований и намечены возможные перспективные направления их развития.
В приложениях помещены экспериментальные данные и результаты, а также акт о внедрении результатов диссертационной работы.
Задачи моделирования и анализа структуры изображений
Разграничение понятий структурного и функционального представлений изображений (см. разд. 1.1) позволяет сформулировать основные задачи моделирования и анализа ПС ГИ. При этом необходимо рассмотреть концептуальные основы теории и практики обработки, анализа, распознавания и синтеза изображений, сложившиеся в результате многочисленных исследований и разработок [3,5-7,9,10,12-14,17,21-23,25,29,30,32-34,37-44,46,47,49-59,74,75,82-86, 88,89,92,94-101,104,106-108,111-114,116-126,129,130,133-149,151-155].
В работе [88] выделяются три основных группы операций над изображе ниями и их структурными описаниями. Первая группа операций - распознавание изображений, состоит из преобразований изображений в их описания. Вторая группа - машинная графика, составлена из преобразований структурных описаний в изображения. Третья группа операций - обработка изображений, образована преобразованиями исходных изображений в их новые копии, которые в каком-либо смысле более предпочтительны для дальнейшего использования; к ним относятся операции улучшения качества изображений, преобразования их к заданной системе координат (трансформирование), эффективного кодирования для последующей передачи или хранения.
Эту классификацию операций над изображениями можно уточнить следующим образом.
1. Операции преобразования изображений в их описания в широком смысле следует понимать как операции анализа изображений, то есть выделе ния из них нужной информации об изображенных объектах. При этом необхо димо различать анализ в узком смысле, как получение формализованных опи саний изображений, и анализ в широком смысле, включающий интерпретацию - установление взаимосвязей этих описаний с семантическими характеристи ками изображенных объектов (собственно распознавание изображений). Со гласно предложенному в работе [96] подразделению процедур анализа (в узком смысле) на два вида, следует различать выделение признаков изображений с целью определения значений их параметров, обеспечивающих различение изо бражений (на основе характеристик их неполных структурных описаний), и собственно анализ, целью которого является получение полных и точных опи саний структуры изображений. При частичной утрате информации об объектах в их изображениях результатом анализа является только описание структуры наблюдаемых изображений и информативность анализа проявляется лишь в той мере, в которой процессы формирования изображений воспроизводят исход ную структуру объекта.
2. Операции формирования изображений по их описаниям следует пони мать как операции моделирования и синтеза изображений на основе их структурных описаний. Сами по себе задачи машинной графики не сводятся к визуализации изображений по их описаниям путем автоматической обработки данных по вполне определенным алгоритмам. Решение этих задач может заключать в себе достаточно сложные операции преобразования данных [9,21,23,55,56,74,75,86,89,92,94,97-99,113,114,124,129133,134].
3. Операции, в которых изображения являются и операндом и результатом, не обязательно сводятся к традиционным операциям обработки изображений; их можно рассматривать шире - как произвольные преобразования или трансформации изображений.
Отсюда следует подразделение групп операций над ПС изображений по соотношениям между изображениями, как реализациями их ПС, и моделями ПС - структурных описаний изображений. Это подразделение определяет следующие основные типы задач моделирования и анализа ПС изображений. 1. Задачи выделения признаков изображений (по характеристикам их ПС), обеспечивающих их различение. 2. Задачи формирования полных и точных структурных описаний ПС изображений, как совокупностей их взаимосвязанных СЭ. 3. Задачи интерпретации (распознавания) ПС изображений - установление взаимосвязи между семантическими характеристиками изображенных объектов и структурными описаниями изображений. 4. Задачи моделирования ПС и синтеза изображений по их структурным описаниям. 5. Задачи преобразования (трансформаций) ПС изображений.
Комбинирование перечисленных типов задач порождает все многообразие задач моделирования и анализа ПС изображений, возникающих в различных научных и практических приложениях, в зависимости от наличия необходимых исходных данных, возможностей наблюдения и регистрации изображений, априорных знаний об их строении, предъявляемых критериев информативности и качества результатов анализа.
Пространственно-структурные свойства изображений
Полученное структурное описание ПС ГИ можно представить не только в виде планарного графа (см. рис. 2,6 в), но и в более удобном для анализа виде -как топологически эквивалентный планерному графу трехслойный граф (см. рис. 2.7 и 2.8), в котором СЭ разделены по слоям размерности 2, 1 и 0, а вершинам графа приписаны соответствующие атрибуты: планиментам, линеаментам и пунктам - значения их КВО, линейным СЭ - значения их кривизны, а точечным СЭ - значения их координат (см. табл. 2.3).
Для анализа пространственно-структурных свойств ГИ, выражающихся в графе структурного описания их ПС, целесообразно ввести понятие порядка СЭ - ord(jS), где S - произвольный СЭ (в дальнейшем отношение смежности СЭ обозначается знаком , планарные СЭ - Р, линейные СЭ - L, границы - В, точечные СЭ - С, узлы - N): ord(c) - количество линейных СЭ L, смежных с С - L-C; ordfx) - количество точечных СЭ С, смежных с L - L-C; ord(P) - количество линейных СЭ L, смежных с Р - L P.
Следует также отметить, что отношение смежности антирефлексивно ( -n(S S) ), симметрично ( (Si S2) -(52 ) ) и, в общем случае, нетран зитивно, т.е. из S2 и S2 S2 не обязательно следует S} S3.
Кроме того, можно ввести в рассмотрение отношение сопряженности СЭ (ан-тирефлекивное, симметричное и, в общем случае, нетранзитивное; обозначается знаком = ): несмежные и различающиеся ( 5( Ф S2 ) элементы S] и S2 являются сопряженными - = 5 2, если существует элемент S, такой, что [S S]) и [S S2). Установлены следующие пространственно-структурные свойства ПС ГИ. Свойство 1. Любые два планарных СЭ несмежны - (Pl Р2).
При этом планарные СЭ могут быть сопряженными - Р\=Р2, если существует общий смежный посредник - точечный или линейный СЭ, Таким образом, планарные СЭ не могут контактировать друг с другом непосредственно, а их контактная близость может иметь вид касания (точечный посредник) или прилегания (линейный посредник).
Свойство 2. Любые два линейных СЭ несмежны (Ц -/ ) При этом линейные СЭ могут быть сопряженными - Ll=L2 если существует общий смежный посредник - точечный или планарный СЭ. Таким образом, линейные СЭ не могут контактировать друг с другом непосредственно, а их контактная близость может иметь вид смыкания (точечный посредник) или прилегания к одному и тому же планарному посреднику.
Здесь нужно отметить, что смежность точечных СЭ не исключается; в этом случае значения их координат равны.
Свойство 3 (межразмерная транзитивность). Если планарный СЭ Р смежен с линейным СЭ X - Р L, а тот в свою очередь смежен с точечным СЭ С - L С, то эти планарный и точечный СЭ смежны - Р С.
Указанные выше отношения сопряженности и транзитивное отношение смежности в свойстве 3 характеризуют топологическую близость [1-3] СЭвПСГИ.
Свойство 4. Порядок любого точечного СЭ - ord(c) есть неотрицательное целое число - ord(C) 0. При этом порядок принимает нулевое значение -ord(c) = 0 только на пунктах С, смежных с единственным планарным СЭ Р -С Р, а порядок любого узла ord(jV) есть положительное целое число - ord(Ar) 1.
Свойство 5. Порядок любого линейного СЭ ord(l) может принимать только значения 0, 1 и 2. При этом ord(l) = 0, если СЭ L замкнут и не существует точечных СЭ С, смежных с ним - -i(L С), ord(l) = 1, если СЭ L замкнут и существует единственный точечный СЭ С, смежный с ним - L С, и ord(i) - 2, если СЭ L незамкнут (имеет две концевых точки).
Свойство 6. Для всякого линейного СЭ L существуют в точности два планарных СЭ /j и Р2, смежных с ним - L - Р2.
Свойство 7. Порядок любого планарного СЭ ord(P) есть положительное целое число - ord(P) l. Если порядок планарного СЭ Р равен единице -ord(P)=l, то это означает, что он вложен внутрь другого планарного СЭ Р , а именно, существует единственный замкнутый линейный СЭ L , смежный с Р -Р Х , и такой, что не существует точечных СЭ С, смежных с ним - -,(L C), т.е.- ord(l J- 0, и существует единственный планарный СЭ Р ,смежныйс L Р - X и сопряженный с Р - Р Р .
Приведенные выше свойства пространственно-структурных описаний ПС ГИ позволяют определить все геометрические и топологические свойства, характеристики и отношения СЭ ГИ путем непосредственного считывания их в структурах пространственных данных (так, как это описано в комментариях к перечисленным свойствам ПС ГИ), либо с помощью логического вывода на этих структурах, а также производимых на них измерений и вычислений, и, тем самым, обеспечивают возможность анализа пространственных данных при решении различных прикладных задач, связанных с обработкой графической информации
Линейные и планарные операторы формирования растра
Для получения дискретных растровых представлений линейных и пла-нарных СЭ изображения необходимы линейные и планарные ОФР, отображающие эти элементы в определенные совокупности пикселов на растре, соответствующие многообразиям, определяющим СЭ. В зависимости от вида таких отображений могут быть получены различные ОФР, различия между которыми проявляются в выборе воспроизводящих СЭ пикселов с учетом принадлежности границ соответствующих ячеек растра.
При этом ОФР в формируемых на растре совокупностях пикселов должны воспроизводить (см. гл. 2) такие топологические характеристики многообразий как их размерность и связность (для линий - непрерывность), а также отношение их смежности, такие геометрических свойства линейных многообразий, как прямолинейность и дугообразность, а также значения их кривизны.
Если полагать, что каждой точке плоскости соответствует определенный пиксел на растре, то связность многообразия будет означать связность соответствующей совокупности пикселов, а смежность двух многообразий - наличие смежности хотя бы одной пары пикселов, принадлежащих этим двум совокупностям пикселов. Размерность 1 для растрового воспроизведения линий означает их минимальную толщину - 1 пиксел, а для планарных элементов - размерность 2 означает отсутствие этой минимальной толщины для всей совокупности пикселов.
На основе 8-связности и 4-связности можно построить эффективные представления линий на растре в виде простого цепного кода (ЦК - кода Фри-мена [141,143,144]; см. рис. 3.20), описывающего переходы по смежным пикселам линии как приращения пиксельных координат, и дифференциального цепного кода (ДЦК; см. рис 3.21), описывающего изменения в этих переходах как приращения изменений текущего направления перехода [88,96,141].
Характер представления об эффективности использования цепных кодов показан на рис. 3.22, где для линии, содержащей 3 точки излома, представлены коды ЦК-8, ДЦК-8/3 и ДЦК-8/5. Как видно из рисунка наибольшая эффективность кодирования обеспечивается использованием ДЦК-8/3 (2 бита на элемент),
Простой линейный ОФР L использует какой-либо точечный ОФР для каждой точки линии (х,у), определяя тем самым соответствующую совокупность пикселов. Необходимо заметить, что большинство разработанных алгоритмов линейных ОФР формирует дискретные представления редуцированных на растр линий с целочисленные значениями параметров [99,129,133]. А / J / Xі у S г S ? г 1 г В то же время при отсутствии такой редукции наблюдается эффект дифференциации - получения различных результатов ОФР. Так использование простого линейного ОФР L+ на основе точеч- а) отрезки А и В в) отрезок В ного квантования Cv+ для Рис. 3.23. Нередуцированные отрезки на растре двух отрезков, концевые точки которых совпадают на растре, дает различные совокупности пикселов (см. рис. 3.23). Как видно, при этом наблюдается также нерегулярный лестничный эффект, который проявляется также и на редуцированных отрезках (см. рис. 3.24). Кроме того проявляется эффект многовариантности - образования различных совокупностей пикселов при различном выборе направлений ВПГ (замена ОФР L+ на основе Cv+ на ОФР L" на основе ...и. і т А Важно отметить, что само по себе уширение линий на растре (лестничный эффект) нарушает условие их однопиксельной толщины и превращает каждую точку линии в точку излома (см. разд. 2.2; 2.3). Поэтому минимальным условием корректности дискретного представления любой линии является возможность ее кодирования с помощью ДЦК-8/3. Это условие обеспечивается путем прореживания пикселов с сохранением 8-связности формируемой совокупности пиксе Рис.3.25. Эффект лов за счет использования ОФР, построенных на осно- многовариантности ве алгоритма цифрового дифференциального анализатора (ЦДА) - Dg, и алгоритма Брезенхама - Вг [99,129,133,139,140] (см. рис. 3.26).
Как видно из рис. 3.26, наблюдаются эффекты инверсного несовпадения (при прямом и обратном прохождении линии - для ОФР Dg), одностороннего прилегания (для ОФР Br) и нулевых искажений (при переходе линии через начало координат - для ОФР Dg и Вг).
Кроме того, возникает неразрешимое при использовании растров противоречие между однопиксельной толщиной линий и отсутствием ширины (нулевой толщиной) границ планарных СЭ; это делает невозможным прокладывание линейных СЭ по границам ввиду неоднозначности их принадлежности граничащим планарным СЭ. В какой-то мере это противоречие разрешается за счет использования ОФР Ас, построенного на основе алгоритма центральной активации пиксела (ЦАП), который относит пиксел планарному СЭ, если центр пиксела принадлежит этому элементу [99,129,133]. В этом случае границей СЭ является связная совокупность крайних пикселов элемента, по которой можно проложить линейный СЭ. Анализ возникающих при применении ОФР Ас эффектов дискретизации дан в приложении 1, из которого видно, что проявление эффектов зубцов нарушает условие корректности дискретного представления линии.
Для соблюдения этого условия можно использовать ОФР Ch, построенный на основе алгоритма ДЦК-8/3, который в принципе не допускает проявления эффекта зубцов. При реализации ОФР Ch был использован выбор одного из трех возможных переходов на растре по максимуму близости к параметризованной кривой (окружности); результаты приведены в приложении 1, Однако и при применении ОФР Ch возникают искажающие эффекты - эффект зубца замыкания, эффект асимметрии и эффект аномального искажения.
Во всех рассмотренных случаях применения линейных и планарных ОФР искажающие эффекты дискретизации возникают, в конечном счете, в зависимости от решения по принадлежности ячейкам растровой сетки их границ и узлов (см. разд. 3.1). Наглядным примером проявления искажающих эффектов дискретизации могут служить дефекты функционирования программы Microsoft Paint (см. рис. 3.27 и 3.28; числовые значения на рисунке - габариты автофигур).
Операторы формирования гиперрастра
В отличие от многообразия ОФР операторы формирования гиперрастра (ОФГр) определяются единственным образом.
Точечный ОФГр определяет принадлежность точки плоскости единственной ячейке гиперрастра, соответствующей либо внутренности ячейки, либо ее границе, либо узлу растровой сетки (см. рис. 4.12). Тем самым обеспечивается минимальная неопределенность значений координат точки. В отличие от растра, где область неопределенности представляет собой ячейку с отнесенными к ней границами и узлами растровой сетки, в гиперрастре максимальная неопределенность (местоположение точки в ячейке) имеет место для внутренних точек (без границ и узлов - меньше, чем в растре), неопределенность граничных точек есть только по одной координате, а для узловых точек неопределенность отсутствует.
Линейный ОФГр определяет связную на гиперрастре совокупность ячеек, соответствующих границам ячеек растровой сетки; таким образом, линии на гиперрастре «не имеют толщины» в отличие линий на растре, для которых минимальная толщина составляет величину 1 пиксел. При этом необходимо учесть, что в эту совокупность должны быть включены все ячейки гиперрастра, соответствующие пересекаемым линией границам ячеек растровой сетки. Кроме того, необходимо учесть, что линейный СЭ в гиперрастровом представлении может являться границей планарного СЭ (отсутствие толщины делает это возможным, в отличие от растрового представления). Поэтому необходимо взаимное согласование представлений линейных и планарных ОФГр.
Планарный ОФГр определяет связную на гиперрастре совокупность ячеек, ограниченную замкнутой линией его контура; таким образом, в отличие от растра, на гиперрастре не образуются пересекающиеся по границам планарные СЭ и на смежных границах таких элементов могут размещаться линейные структурные элементы, не имеющие пересечения с ними, т.к. эти линейные элементы «не имеют толщины».
Поэтому для линейных СЭ в соответствующую совокупность пикселов необходимо включить все ячейки гиперрастра, соответствующие непересекае-мым линией границам ячеек растровой сетки, отнесенным к границам планарных СЭ. Для этого можно использовать схему центральной активации, аналогичную схеме ЦАП для растров. В результате линейные ОФГр имеют вид, показанный на рис. 4.13.
Необычные свойства линейных ОФГр проявляются в том случае, когда линия, пересекающая ячейку, проходит через ее центр. В этом случае симмет-рийное расположение планарных СЭ, для которых эта линия могла бы быть границей, вынуждает актуализировать на гиперрастре все ячейки, соответствующие границам данной ячейки растровой сетки. Если, кроме того, при этом линия проходит через узлы ячейки, то ОФГр актуализирует также ячейки, соответствующие двум противоположным узлам ячейки растровой сетки.
В отличие от эффектов дискретизации на растре (см. гл. 3), эффекты дискретизации на гиперрастре просты и однозначны.
Для точечных ОФГр никакие искажающие эффекты дискретизации не имеют места - точке плоскости соответствует единственная ячейка гиперрастра (соответствующая либо внутренности ячейки, либо ее границе, либо узлу растровой сетки; см. разд. 4.3) и для диагональных прямых эта ячейка периодически повторяется на гиперрастре в одном из двух диагональных направлений.
Для линейных ОФГр эффекты дискретизации весьма необычны (см. рис. 4.14). Первый эффект - эффект ветвей (см. рис. 4.14 а), проявляется в том, что линия на гиперрастре на некоторых своих участках сопровождается боковыми ответвлениями (ветвями), что связано с процедурой активации центрального пиксела, используемой в том случае, когда эта линия является границей планарных СЭ (см. рис. 4.13). Эффект ветвей проявляется всегда, за исключением случая горизонтального, вертикального или диагонального ориентирования прямой, проходящей через узлы растровой сетки. Второй эффект - эффект петель (см. рис. 4.14 б), проявляется в том, что для некоторых ячеек растровой сетки актуализируются ячейки гиперрастра, соответствующие всем ее границам; при этом на гиперрастре образуется петля, охватывающая внутренность ячейки растровой сетки (см. рис. 4.13). Третий эффект - фокусный эффект (см. рис. 4.14 е), проявляется в том, что линия, проходящая через узлы растровой сет у сетки (фокусы), актуализирует ячейки гиперрастра, соответствующие этим узлам (см. рис. 4.13). Существенно, что эффект петель и фокусный эффект проявляются не всегда
