Содержание к диссертации
Введение
Глава 1. Представление и кодирование изображений 19
1.1. Способы получения и формы представления изображений . 19
1.2. Интеллектуальные телекоммуникационные системы и когнитивные модели данных 26
1.3. Модели и методы представления и кодирования изображений 29
1.4. Структурно-цветовой анализ изображений 33
1.5. Выводы и постановка цели и задач исследований 46
Глава 2. Геометрические свойства и характеристики графических изображений 47
2.1. Пространственный план и графикация изображения 47
2.2. Геометрические инварианты двумерных пространственных структур 50
2.3. Структурные элементы изображений 60
2.4. Пространственная структура изображения 66
2.5. Полученные результаты и выводы 69
Глава 3. Редукция структурных элементов изображения на дискретный растр 70
3.1. Точечная редукция 70
3.2. Линейная редукция 80
3.3. Цепные коды 83
3.4. Секторные цепные коды 85
3.5. Полученные результаты и выводы 88
Глава 4. Распознавание структурных элементов изображения на дискретном растре 89
4.1. Квантование значений геометрических атрибутов структурных элементов изображения 89
4.2. Секторно-косоугольная система координат 93
4.3. Нормализованные оценки геометрических характеристик редуцированных на растр структурных элементов изображения . 96
4.4. Распознавание редуцированных на растр структурных элементов 99
4.5. Полученные результаты и выводы 104
Глава 5. Графическая информация в интеллектуальных телеком муникационных системах 106
5.1. Алгоритмы, программное обеспечение и технология обработки графической информации 106
5.2. Сжатие графической информации 112
5.3. Экспериментальные данные и результаты 119
5.4. Полученные результаты и выводы 123
Заключение 124
Литература 127
Приложение 139
- Интеллектуальные телекоммуникационные системы и когнитивные модели данных
- Геометрические инварианты двумерных пространственных структур
- Нормализованные оценки геометрических характеристик редуцированных на растр структурных элементов изображения
- Сжатие графической информации
Введение к работе
Актуальность темы. Интенсивный прогресс в области развития систем телекоммуникаций резко расширил возможности передачи, получения, хранения и обработки информации в самых различных формах ее представления. Вместе с тем, при этом обозначились новые проблемы, а в ряде случаев, некоторые старые проблемы приобрели новую окраску. К числу таких проблем относится проблема эффективного представления и кодирования видеоинформации. С одной стороны, передача данных пользователю в виде изображений или графических образов является одной из наиболее удобных для него форм представления информации. С другой стороны, большая информационная емкость изображений существенно ограничивает возможности передачи видеоинформации по каналам связи. Увеличение ресурсов цифровой обработки информации не решает проблему в глобальном плане, т.к. рост потребностей в этой области всегда опережает достигнутые возможности.
Другой аспект проблемы обозначился в связи с возникновением и развитием интеллектуальных телекоммуникационных систем. Необходимым стало не только передать информацию пользователю в наглядной и образной форме, но и обеспечить такое ее представление, которое позволило бы автоматически анализировать содержание этой информации с помощью современных компьютерных технологий и при этом сразу и непосредственно использовать результаты анализа при решении различных практических задач. Это вызывает потребность разработки когнитивных моделей данных для представления изображений с целью их использования в телекоммуникационных системах.
Разработке эффективных моделей изображений, методов их обработки и кодирования уделено большое внимание в работах отечественных и зарубежных ученых: Журавлева Ю.И., Лебедева Д.С., Ярославского Л.П., Ковалевского В.А., Васина Ю.Г., Бонгарда М.М., Файна B.C., Цуккермана И.И., Мучника И.Б., Розенфельда А., Прэтта У., Фу К., Стокхэма Т., Марра Д., Харалика P.M., Павлидиса Т., Нарасимхана Р. и др.
Однако достигнутые в настоящее время результаты не решают в полной мере проблему эффективного представления изображений в силу указанных выше причин. Это делает задачу поиска такого эффективного представления для использования в ИТКС актуальной. Один из путей ее решения может быть основан на анализе дискретных представлений структуры изображений, как наиболее отвечающих цифровым средствам и методам обработки информации. Формирование когнитивных моделей данных на основе анализа и синтеза дискретных представлений изображений может повысить эффективность передачи и использования видеоинформации в ИТКС.
Целью работы является разработка эффективных дискретных представлений и методов кодирования графических изображений для интеллектуальных телекоммуникационных систем, применение которых качественно повышает возможности передачи и использования видеоинформации.
Для достижения поставленной цели в работе решаются следующие задачи:
определение свойств и характеристик графических изображений, учитывающих пространственный план их построения, степень подобия изображаемым объектам, цветотоновые шкалы и возможные искажения, и установление степени их адекватности когнитивным моделям данных в интеллектуальных телекоммуникационных системах;
разработка методики структурно-цветового анализа изображений, обеспечивающей высокую достоверность результатов предварительной обработки изображений при локализации и оценке их структурных элементов;
построение способа объективного выделения структурных элементов графических изображений и формирования полного и точного описания их пространственной структуры;
построение корректных неискажающих схем редукции структурных элементов изображений на дискретный растр и представление их дифференциальными и секторными цепными кодами;
получение нормализованных оценок геометрических характеристик ре-
7 дуцированных на растр структурных элементов изображений, соответствующих дискретно-планиметрическим условиям корректности операторов редукции;
разработка метода распознавания и оценки геометрических атрибутов редуцированных на растр структурных элементов изображений;
создание программного обеспечения средств анализа и синтеза дискретных представлений и методов кодирования графических изображений;
проведение экспериментальных исследований разработанных средств и методов для оценки их эффективности и возможностей использования в интеллектуальных телекоммуникационных системах.
Объектом исследования являются: графические изображения, их свойства и характеристики, способы их получения, формы представления и кодирования, их когнитивные модели и дискретные представления этих моделей; адаптивное цветотоновое и центроидное преобразования изображений; интеллектуальные телекоммуникационные системы.
Предметом исследования являются: методы моделирования, анализа, синтеза и кодирования графических изображений; структурно-цветовой анализ изображений; операторы редукции изображений на дискретный растр и их кодирование на основе цепных кодов; методы распознавания структурных элементов изображений; программные средства обработки графических изображений; технологии обработки графической информации в интеллектуальных телекоммуникационных системах.
Методы исследования. В работе применялись теоретические и экспериментальные методы исследования.
Теоретические исследования основаны на использовании функционального анализа, геометрии подобий и дискретной планиметрии, методов машинной графики, методов обработки, анализа и кодирования изображений, методов распознавания образов.
В экспериментальных исследованиях разработанных моделей и алгоритмов использовались методы моделирования пространственных структур, осно-
8 вы цифровой обработки изображений, системного программирования, цифровые методы кодирования и передачи информации.
Достоверность изложенных положений работы подтверждается результатами практического применения разработанных программных средств, методики и технологии обработки графической информации, научными трудами и апробациями созданного научно-технического продукта на представительных научных форумах. Достоверность и обоснованность полученных в работе результатов и выводов подтверждается при их сравнительном анализе с известными результатами современных исследований и разработок.
Теоретические положения, установленные в работе, обосновываются адекватностью выбора исходных посылок и последовательным применением аппарата математических выводов для получения аналитических выражений.
Достоверность экспериментальных результатов обеспечена их хорошей согласованностью с теоретическими выводами, выбором корректных критериев при построении алгоритмов обработки информации, а также хорошей воспроизводимостью экспериментальных данных.
На защиту выносятся результаты разработки моделей дискретных представлений и методов кодирования графических изображений, а также создания программных средств анализа и синтеза дискретных представлений и кодирования графических изображений в интеллектуальных телекоммуникационных системах, в том числе:
анализ свойств и характеристик графических изображений и возможностей построения их когнитивных моделей для интеллектуальных телекоммуникационных систем;
методика структурно-цветового анализа изображений, обеспечивающая высокую достоверность результатов предварительной обработки изображений с целью локализации и оценки их структурных элементов и высокую степень сжатия видеоданных;
способ объективного выделения структурных элементов графических
9 изображений и формирования полного и точного описания их пространственной структуры;
корректные неискажающие схемы редукции структурных элементов изображений на дискретный растр и представления их дифференциальными и секторными цепными кодами;
нормализованные оценки геометрических характеристик редуцированных на растр структурных элементов изображений;
метод распознавания и оценки геометрических атрибутов редуцированных на растр структурных элементов изображений;
создание программного обеспечения средств анализа и синтеза дискретных представлений и методов кодирования графических изображений;
результаты экспериментальных исследований разработанных средств и методов с целью оценки их эффективности и возможностей использования в интеллектуальных телекоммуникационных системах.
Научная новизна полученных результатов определяется впервые проведенными исследованиями, в результате которых разработаны модели дискретных представлений и основанные на них методы кодирования графических изображений, а также созданы программные средства анализа и синтеза дискретных представлений и кодирования графических изображений, что вносит существенный вклад в решение задач создания интеллектуальных телекоммуникационных систем, в ходе которых:
определены свойства и характеристики графических изображений -пространственный план их построения, степень подобия изображаемым объектам, цветотоновая шкала и возможные искажения, и установлена их адекватность когнитивным моделям данных в интеллектуальных телекоммуникационных системах;
разработана методика структурно- цветового анализа изображений на основе их адаптивного цветотонового и центроидного преобразований, обеспечивающая высокую достоверность локализации и оценки их структурных эле-
10 ментов и высокую степень сжатия видеоданных;
предложен способ объективного выделения структурных элементов графических изображений и формирования полного и точного описания их пространственной структуры, основанный на анализе геометрических инвариантов двумерных пространственных структур относительно группы преобразований нерефлексных подобий и ее подгрупп;
построены корректные неискажающие операторы редукции структурных элементов изображений на дискретный растр и установлена возможность представления результатов редукции дифференциальными и секторными цепными кодами
выведены нормализованные оценки геометрических характеристик редуцированных на растр структурных элементов изображений, соответствующие дискретно-планиметрическим условиям корректности операторов редукции;
разработан метод распознавания и оценки геометрических атрибутов редуцированных на растр структурных элементов изображений, построенный на основе нормализованных оценок их геометрических характеристик;
предложена и обоснована технологическая схема обработки графической информации, реализованная при выполнении экспериментальных исследований, результаты которых позволили определить условия эффективности и возможностей использования разработанных средств и методов в интеллектуальных системах телекоммуникаций.
Практическая ценность работы заключается в применении новых эффективных представлений и методов кодирования графических изображений.
Разработано и отлажено программное обеспечение, реализующее алгоритмы анализа и синтеза дискретных представлений и методов кодирования графических изображений для интеллектуальных телекоммуникационных систем.
Разработанный программный комплекс обеспечивает как автономное функционирование программ, так и работу их в интегрированном варианте под управлением интерпретатора CGI. Поддерживаются форматы данных растрового
изображения, цепных кодов и структурных описаний изображения. Функционирование программного комплекса реализует разработанную технологию обработки графической информации для телекоммуникационных систем.
Проведен анализ возможностей и получены оценки эффективности разработанных средств и методов представления и кодирования графической информации. Установлено, что разработанные модели дискретных представлений графических изображений и методы их кодирования позволяют добиться высокой степени сжатия видеоданных, высокой производительности процедур кодирования и декодирования, и обеспечивают возможность прямого и непосредственного использования данных в их когнитивной форме.
Реализация и внедрение работы. Полученные результаты использованы и апробированы для опытно-производственной эксплуатации системы обработки графической информации в Тульском филиале ОАО «ЦентрТелеком».
Созданные программные средства обработки графической информации позволили повысить эффективность функционирования цифровых каналов связи телекоммуникационных систем при передаче этой информации, обеспечили сокращение объемов памяти для цифрового представления графических изображений и увеличение скорости передачи информации.
Апробация работы. Результаты работы докладывались на российских и международных научно-технических конференциях и конгрессах: Международном Самарском симпозиуме телекоммуникаций для руководящих работников отрасли связи (1996- 2004); LI Научной сессии, посвященной Дню Радио (Москва, 1996); LII Научной сессии, посвященной Дню Радио (Москва, 1997); Международной конференции Internation Conference «Intelligent Networks Services and Standards» (Москва, 1999); Международной конференции Internation Conference «Intelligent Networks 2000: Services and Problems of Convergence» (Москва 2000); The 5th International congress on mathematical modelling (Dubna, 2002); XXXI Международной конференции «Информационные технологии в науке, образовании, телекоммуникациях и бизнесе» (Украина, Крым, Ялта - Гурзуф, 2004); Международном симпозиуме «Надежность и ка-
12 чество» (Пенза, 2004); VI Международном конгрессе по математическому моделированию (Нижний Новгород, 2004); XXXI Международной конференции «Информационные технологии в науке, социологии, экономике и бизнесе» (Украина, Крым, Ялта - Гурзуф, 2004); V Международной научно-технической конференции «Проблемы техники и технологии телекоммуникаций» (Самара, 2004).
Публикации. Основные научные результаты по теме диссертации опубликованы в 22 научных работах, в том числе: 3 монографии (250с, 272с. и 266с), 4 статьи в научно-технических журналах и сборниках; 15 тезисов докладов на научно-технических конференциях.
Объем и структура диссертационной работы. Диссертация содержит введение, 5 глав и заключение, изложенные на 138 с машинописного текста. В работу включены 43 рис., 14 табл., список литературы из 138 наименований и приложение, в котором представлен акт об использовании результатов работы.
СОДЕРЖАНИЕ РАБОТЫ
Введение содержит обоснование актуальности темы, формулировку цели и задач работы, основные положения, выносимые на защиту, и определяет содержание и методы выполнения работы.
В первой главе рассматривается содержание изображений, определяемое способностью воспроизведения пространственного строения изображенных объектов, как совокупности составляющих их взаимосвязанных элементов.
При этом выделяется графический способ получения изображений - последовательное нанесение структурных элементов. Графические изображения строятся в соответствии с априорно определенным планом их построения. По степени подобия изображаемым объектам они подразделяются на реалистически, геометрически и топологически подобные. Для них характерно также относительно малое число тонов и цветов, используемых при воспроизведении. Кроме того, могут иметь место искажения тоновых и цветовых шкал, пространственно-частотные искажения и нанесение на изображение шумов и помех.
При передаче изображений по каналам связи телекоммуникационных систем актуальными являются потребности повышения пропускной способности каналов связи и оперирования изображениями не только как с целостными объектами, а как со структурами данных для решения различных задач, т.е. необходимы определенный уровень «понимания» изображений информационной системой и возможность анализа их пространственной структуры. Это приводит к необходимости использования когнитивных моделей данных, что придает телекоммуникационным системам такое качество, как интеллектуальность.
Показано, что наибольший эффект сжатия информации достигается не за счет сжатия изображения, а за счет его распознавания с последующим сжатием. Кроме того, передача распознанного изображения позволяет системе использовать его сразу и непосредственно, анализируя его содержание для решения конкретных задач.
Сопоставление различных моделей структуры изображений показало, что векторные модели в большей степени проявляют когнитивный характер, нежели растровые, но их когнитивные свойства относительно невелики, не всегда отражают топологические взаимосвязи элементов, или не описывают явном виде объекты как целостные образования. При этом определение элементов и взаимосвязей носит субъективный и неоднозначный характер, что требует разработки объективного способа выделения элементов изображений.
При рассмотрении методов представления, анализа, синтеза и кодирования изображений, выделен метод структурно-цветового анализа изображений, обеспечивающий высокую достоверность их предварительной обработки с целью локализации и оценки структурных элементов и высокую степень сжатия видеоданных, основанный на использовании двух преобразований изображений -адаптивного цветотонового и центроидного. Методика заключается в обработке изображения фильтром, кластеризующим значения цветовых компонент, распознавании цвета пикселов, формировании слоев изображения по каждому кластеру и центроидном преобразовании каждого слоя При этом существенно подавля-
14 ются шумы, эффективно сжимаются графические данные, реализуются любые нелинейные преобразования для коррекции искажений и повышения цветото-новой контрастности. Кластерный анализ результатов адаптивного цветотоново-го и центроидного преобразований позволяет локализовать и оценить структурные элементы изображений.
Во второй главе рассматривается пространственная структура графических изображений в непрерывной форме. При этом выделяются пространственная компонента структуры - план построения изображения, и привязанная к ней графическая компонента. План представляет собой рисунок из точек и линий, имеющих смысл компактных элементов структуры, либо узлов, или линейных элементов, либо границ, соответственно. Смысловое различение элементов производится путем присвоения им кодов. Изображение формируется в результате графикации - присвоения кодам элементов графических параметров.
Объективизация процесса выделения структурных элементов производится на основе анализа инвариантов двумерных пространственных структур относительно группы преобразований нерефлексных подобий, определяющей все геометрические свойства, характеристики и отношения элементов, а также инвариантов относительно всех ее подгрупп.
Выделяются такие инварианты, как размерность, связность, смежность, прямолинейность, дугообразность, угол, направление, расстояние, кривизна и координаты. Структурные элементы определяются с помощью сигнатуры -списка кодов элементов в окрестности каждой точки, и эквивалентности точек, если они являются взаимно преобразуемыми вместе со своими окрестностями. Тогда структурные элементы образуются связными множествами эквивалентных точек. Так выявляются элементы постоянной кривизны - отрезки и дуги, а также линейные сегменты переменной кривизны. Для отрезков инвариантными атрибутами являются их длина и направление, для дуг - длина стягивающей хорды и кривизна дуги, для линейных сегментов переменной кривизны - функция текущей кривизны. Геометрическим атрибутом компактных элементов и узлов
15 являются их координаты, но структура изображения в окрестности достаточно сложна, т.к. к ним примыкают линейные и планарные элементы. Поэтому в описании отражается порядок их следования при обходе вокруг узла, что достигается за счет декомпозиции узла - разложения на структурные элементы в окрестности узла. В результате декомпозиции выделяются медиаторы - солигоны («одно-угольники») и аксиоиды («стрелки»). Инвариантный геометрический атрибут для солигона - величина угла, а для аксиоида - направление. Взаимосвязи структурных элементов устанавливаются инвариантным отношением смежности между ними.
Построенное таким образом структурное описание изображения является полным и точным, а его когнитивный характер заключается в возможности «понимания» системами автоматической обработки информации пространственного плана построения изображения.
В третьей главе определяются операторы редукции на дискретный растр, рассмотренных в гл. 2 непрерывных представлений структурных элементов изображения. Выделяются операторы точечной и линейной редукции.
Простейший оператор точечной редукции определяет целочисленные значения. При этом интервалы квантования различны, что приводит к разнотипности ячеек растра, его неоднородности и анизотропности. Поэтому возникают искажения структурных элементов изображения, и такой оператор некорректен. Более корректной является схема квантования с округлением координат, но, несмотря на выравнивание размеров интервалов, сохраняется их разнотипность, что также приводит к искажениям элементов. Корректный симметри-зованный оператор редукции дает однотипные интервалы квантования и ячейки растра и не приводит к искажениям.
Показано, что оператор редукции линейных структурных элементов, построенный на основе оператора точечной редукции, вызывает искажения линий ввиду того, что приводит, в основном, только к вертикальным и горизонтальным переходам на растре, создающим угловатость. Исключение этих переходов
реализовано в алгоритмах Брезенхама, в которых также могут возникать искажения, аналогичные действию оператора точечной редукции. Однако симметризация схемы подсчета инкремента и переход к однонаправленной системе направлений устраняют искажения и дают возможность обобщить оператор для произвольных кривых путем их сегментации по секторам направлений.
Линейные операторы редукции непосредственным образом связаны с простым и дифференциальным цепными кодами. При сопоставлении с цепочками пикселов, формирующихся в результате применения линейных операторов редукции Брезенхама, становятся возможными только два типа переходов (диагональные и осевые) в каждом из координатных секторов направлений. В этом случае для каждого гладкого односекторного сегмента произвольной линии может быть получен секторный цепной код. Для этого необходимо определить только координаты начальной точки сегмента и оценка информационной емкости линий на растре принимает значение 1 бит на элемент.
Применение корректных операторов редукции структурных элементов изображений на дискретный растр позволяет построить эффективное представление структуры изображения и при использовании цепных кодов получить экономную схему ее кодирования, что повышает эффективность передачи видеоданных по каналам связи телекоммуникационных систем.
В четвертой главе на основе обращения операторов редукции, рассмотренных в гл. 3, разрабатывается метод распознавания структурных элементов на растре. Для обращения операторов редукции необходим анализ влияния дискретизации на значения атрибутов элементов. Квантование координат точек элементов индуцирует квантование также и их характеристик. Схема квантования характеристик является более сложной, нежели схема квантования координат. Это приводит к тому, что такие характеристики отрезка как длина и направление, изменяются в широких пределах.
Формы и размеры ячеек квантования в координатах «длина-направление» существенно различны и определяются местоположением конечной точки от-
17 резка. С увеличением расстояния конечной точки от начала координат размеры ячеек уменьшаются и при достаточно больших расстояниях сливаются в сплошной континуум. Эта особенность позволяет утверждать, что при больших длинах отрезка все соотношения, характерные для непрерывной планиметрии, выполняются с достаточной точностью. В то же время, при малых длинах отрезка, величины погрешностей характеристик отрезка достигают значительных величин. Поэтому необходимо переопределение этих характеристик для ближней зоны начала координат на растре, что, по сути, означает построение специфичной дискретной планиметрии.
Цепные коды предоставляют возможность корректного определения геометрических характеристик элементов в дискретно-растровом представлении. Оценки могут быть получены как средневзвешенные значения между верхними и нижними пределами оценок по диагональным и осевым направлениям линии.
Анализ точности этих оценок показал, что в пределах ближней зоны в 250 пикселов оценка направления имеет погрешность не более одного градуса, а оценка длины в пределах 142 пикселов - не более 1 пиксела. Сами оценки легко могут быть получены по секторному цепному коду линий.
Поэтому, распознавание линий на растре производится за счет контроля направления и длины линии при последовательном перемещении вдоль линии с помощью переходов по соседним пикселам, т.е. отслеживания последовательных перемещений текущей точки линии по нерегулярным ячейкам в координатах «длина-направление».
В пятой главе описаны разработанные алгоритмы, программное обеспечение и технология обработки графической информации, а также результаты экспериментальных исследований разработанных средств и методов.
Алгоритмы анализа и синтеза дискретных представлений и методов кодирования графических изображений разработаны на основе результатов, полученных в гл. 3,4. При этом построены алгоритмы быстрой редукции структурных элементов на дискретный растр.
18 Проведенные экспериментальные исследования показали высокую эффективность разработанных средств и методов для использования в интеллектуальных телекоммуникационных системах. В экспериментах были проанализированы возможности адаптивного цветотонового и центроидного преобразований изображений для реализации методики структурно-цветового анализа. Результатом анализа явился вывод о высоком качестве обработки и распознавания графических изображений. Были выполнены эксперименты по оценке эффективности процессов синтеза и распознавания изображений, оценивались показатели кодирования и сжатия видеоданных и производительности процедур их обработки.
Разработанные технология обработки графической информации и программное обеспечение построены таким образом, что допускают возможность их использования как в автономном, так и в интегрированном режимах обработки данных. В интегрированным варианте обработки информации программы работают под управлением разработанного интерпретатора CGI. Формирующиеся в результате обработки структуры данных - растровые изображения, их представления в форме цепного кода и их структурные описания подвергаются кодированию и декодированию при передаче по каналам связи.
В заключении диссертационной работы сформулированы основные выводы и результаты.
Интеллектуальные телекоммуникационные системы и когнитивные модели данных
Проблема передачи изображений по цифровым каналам связи телекоммуникационных систем имеет двоякий характер. Во-первых, по прежнему сохраняется потребность в повышении пропускной способности каналов связи, причем не столько в плане количества передаваемых за единицу времени бит, сколько в плане количества передаваемых за единицу времени информационных единиц (изображений). Несмотря на высокую эффективность существующих методов сжатия видеоинформации [5,13], рост потребности здесь постоянно опережает достигнутые возможности. Второй аспект проблемы связан с необходимостью оперирования изображениями в информационных системах, не только сводящемуся к их визуализации и не только как с целостными объектами, а как со структурами данных для решения различных прикладных задач. Это предполагает определенный уровень «понимания» изображений информационной системой [27,60,77], что означает возможность анализа их пространственной структуры. Такое «понимание» вызывает необходимость использования когнитивных моделей данных, передаваемых по каналам связи, и специальных средств анализа и синтеза этих данных на терминалах каналов связи, что придает телекоммуникационным системам такое качество, как интеллектуальность.
Вообще, необходимо отметить, что в настоящее время понятие «интел лектуальность» применительно к системам автоматизированной обработки информации применяется в достаточно широком спектре значений - от решения сложных задач с большими объемами перебора вариантов при поиске решения, до систем, имитирующих процессы восприятия и мышления человека. В этом плане особый интерес представляет работа М. Минского [60], в которой обосновано смещение центра исследований по искусственному интеллекту в область систем представления знаний. Развитие работ в этом направлении привело к разработке технологии баз знаний и экспертных систем - систем, оперирующих знаниями в определенной предметной области, обладающих способностью понимания текущих ситуаций в этой области и способных находить решения при возникновении достаточно сложных ситуаций исходя из поставленной задачи [29,43,45,60,69,7274,76,88,94,96,113].
Применение таких технологий в сочетании с методами имитационного моделирования в области телекоммуникационных систем оказалось весьма эффективным [55,83]. Однако, как показывает анализ, проведенный в работе [54], эффективность здесь существенно зависит от видов и форм передаваемой по сетям информации, что определяется информационной емкостью передаваемых сообщений. В этом плане изображения, как объекты передачи, являются достаточно емкими, и потребность быстрой их передачи по каналам связи представляется по прежнему актуальной.
Поэтому, вполне естественным представляется прогноз дальнейшего развития моделей и методов представления и кодирования пространственных данных в направлении их преобразования к «распознанному» виду, т.е. к виду когнитивных моделей данных [27,44,57,60]. Помимо ожидаемого существенного снижения информационной емкости сообщений, это позволит использовать технологии баз знаний и экспертных систем не только для управления функционированием телекоммуникационных систем, но и для их интеграции с разнообразными системами обработки информации, придав им интеллектуальность в самом широком понимании.
Наглядный пример, демонстрирующий эффективность использования когнитивных моделей данных приведен на рис. 1.5 и в табл. 1.2.
Ключевым момен явление и исследованн виде соответствующих На рисунке показано изобра жение страницы текста и качество его распечатки на увеличенном ет отнести понятие пр фрагменте. Это качество обеспечи венная структура явл; вает безошибочное чтение текста объектов в широком щ\ программой Fine Reader. В таблице приведены объемы памяти изобра жения, результата его сжатия (в скобках - показатели для двухградационного
Результаты различных видов обработки изображения текста в наглядном виде представлены на рис. 1.6. Из рисунка видно, что наибольший эффект сжатия информации достигается не за счет сжатия изображения (в 3 раза за счет устранения функциональной избыточности изображения - Ф), а за счет распознавания текста (в 100 раз) с последующим сжатием (более чем в 700 раз за счет устранения структурной избыточности текста - С). Еще больший эффект дает деграфикация документа - сжатие более чем в 1000 раз, а при архивизации - более чем в 2000 раз.
Не менее важным здесь является то, что передача распознанного документа позволяет информационной системе использовать его сразу и непосредственно, анализируя его содержание для решения конкретных задач.
Проигрыш методов функционального сжатия изображений по сравнению с их распознаванием наглядно виден из рис. 1.6 - бинаризация изображения с последующим сжатием сокращает объем информации в 60 раз, но ухудшает качество изображения и приводит к ошибкам чтения текста программой Fine Reader. Это дает возможность визуализировать передаваемый документ, но не позволяет информационной системе оперировать с его содержанием.
Сопоставительный анализ различных моделей пространственной структуры изображений позволяет выделить два типа моделей. Модели первого типа разрабатывались для синтеза изображений по их структурным описаниям (машинная графика [38,70,71,111,112], системы автоматизированного проектирования (САПР) и геоинформационные системы (ГИС) [31,36,37,40,41,96]), а модели второго типа - для анализа и распознавания изображений, т.е. для получения этих структурных описаний [22,24,34,77,92,97]. Основное различие между этими моделями определяется тем, что в моделях первого типа структурные элементы (примитивы) и их взаимосвязи заданы заранее, а в моделях второго типа -должны быть выявлены в процессе анализа. В первом случае характер модели определяет возможности построения изображений, в то время как во втором случае - адекватность получаемых в результате анализа структурных описаний.
Наиболее развитые модели первого типа получили распространение в области геоинформационных систем и технологий [31,36,37,40,41,96], но в то же время наблюдается определенная интеграция моделей в различных областях: ГИС обычно содержат САПР-приложения, а САПР - ГИС-приложения, при этом обеспечивается возможность конвертации данных ГИС и САПР в системы машинной графики. В развитии систем машинной графики наблюдается также тенденция к поиску сетевых решений [1,86].
Геометрические инварианты двумерных пространственных структур
Согласно современным представления, развитым в геометрии, существует множество различных геометрий и топологий, каждая из которых определяется некоторой группой преобразований пространства (в двумерном случае -плоскости) [2,35]. При этом, предметом рассмотрения каждой такой геометрии или топологии являются свойства, характеристики и отношения подмножеств пространства, инвариантные относительно этой группы преобразований. Так, обычная геометрия плоскости (планиметрия) определяется группой преобразований подобия, которые представляют собой комбинации сдвигов (трансляций), поворотов (ротаций) и масштабных преобразований (гомотетий) плоскости [2]. Существуют также геометрии более жесткого типа, такие как геометрии наложений, движений, отражений и т.д., определяемые подгруппами группы подобий [2].
Таким образом, для определения геометрических свойств и характеристик ГИ необходимо рассмотреть группу преобразований подобия и различные подгруппы этой группы. Подобный подход был успешно применен к задачам обработки графической информации в работах [30,56,62,65] ;при этом рассматривались не только геометрические, но и топологические свойства и характеристики, однако была принята линейная структура семейства групп геометрических преобразований. Как будет видно из дальнейшего, эта структура имеет более сложный характер.
Сразу же следует заметить, что группу преобразований подобия необходимо ограничить, исключив из нее зеркальные отражения [2]. Это обусловлено тем, что сдвиг, поворот и масштабирование двумерной структуры сами по себе не приводят к получению ее зеркальной копии. Поэтому, для различения левосторонних и правосторонних структур необходимо рассматривать только нерефлексные (неотражающие) преобразования подобия [2].
Преобразования различных подгрупп группы нерефлексных подобий приведены в табл. 2.1. Каждое преобразование взаимно однозначно отображает точку плоскости (х,у) в ее образ (х ,у ), что означает также существование обратного преобразования, отображающего (х ,у ) в (х,у) [2,35].
В таблице даны названия групп преобразований, обозначения преобразований и групп преобразований, аналитические выражения этих преобразований и аналитические выражения для тех групп, которые являются прямыми произведениями образующих их подгрупп; для последних в явном виде записаны соответствующие прямые произведения.
Простейшая подгруппа G7 состоит из единственного элемента - тождественного преобразования Id , не зависящего от параметров. Далее следуют три простых группы параметризованных преобразований: - группа трансляций G1 - сдвигов Tr [cx, с ), параллельных осям координат; - группа центроаффинных ротаций (в дальнейшем для краткости - ротаций) GR - поворотов Rt(or) вокруг начала координат (поэтому - центроаффинных); - группа центроаффинных гомотетий (в дальнейшем для краткости - Ц гомотетий) GCH - масштабирований Ch(&) с центром в начале координат;
Следующие три группы параметризованных преобразований являются попарными прямыми произведениями перечисленных выше трех подгрупп и состоят из попарных суперпозиций соответствующих преобразований: - группа движений (нецентроаффинных ротаций [2]) GM - суперпозиций поворотов и сдвигов Mv[cx,c ,aJr[cx, с )Rt(a)[(x,y)] ; является прямым произведением групп ротаций и трансляций - GTGR; - группа гомотетий (нецентроаффинных) GH - суперпозиций масштабирований и сдвигов Нт(сх,с к)=Тг[сх, с )oCh(k); является прямым произведением групп Ц-гомотетий и трансляций - GT 8 GCH; - группа центроаффинных нерефлексных подобий (в дальнейшем для краткости - Ц-подобий) Gcs - суперпозиций поворотов и масштабирований является прямым произведением групп ротаций и Ц гомотетий - GCH 8 GR.
Как видно из таблицы, набор параметров преобразований каждой из перечисленных трех групп является объединением наборов параметров соответствующих преобразований, входящих в суперпозицию.
Нормализованные оценки геометрических характеристик редуцированных на растр структурных элементов изображения
Как было отмечено в разд. 4.1, в ближней зоне растра вариации оценок геометрических характеристик структурных элементов изображений могут быть настолько большими, что их дискретизированные значения соответствуют целой совокупности различающихся своим местоположением на растре структурных элементов, таких что, всем им соответствует одинаковое дискретное значение характеристики. Поэтому, для ближней зоны растра необходимо переопределить значения всех характеристик таким образом, чтобы их дискретизированные значения укладывались в соответствующие ячейки сетки, индуцированной квантованием координат. Кроме того необходимо, чтобы в пределах ближней зоны обращение этих дискретизиро-ванных значений не расходилось бы с обычными оценка этих характеристик в непрерывной декартовой системе координат на величину более чем размер одного пиксела. Из этого же условия становится возможным определение размеров ближней зоны для каждой характеристики.
Поскольку квантование координат приводит к достаточно сложному нелинейному квантованию всех прочих геометрических параметров, то одним из путей получения требуемых оценок характеристик является использование средневзвешенных значений между верхними и нижними их оценками. Так на рис. 4.2 показанный вектор по своему направлению ориентирован под углом между абсциссой и суммарным вектором диагональных переходов. С другой стороны очевидно, что длина этого вектора меньше суммарной длины всех векторов перехода, но меньше суммарной длины векторов диагональных переходов.
Поэтому, использование средних между указанными предельными значениями с соответствующими весами длин векторов осевых и диагональных переходов может дать оценки, достаточно точно приближающиеся к соответствующим дискретизированным значениям характеристики.
Поэтому в качестве оценки направления отрезка на растре может быть использована средневзвешенная оценка направления между диагональным и осевым направлением отрезка (для первого сектора; для всех остальных секторов аналогично): где а - количество осевых ходов цепного кода; d — количество диагональных ходов (координаты в СКСК).
В тоже время истинное значение направления выражается в следующем соотношении: a + d Если рассматривать количество диагональных и осевых ходов в относительном выражении при а=\, то преобразование выражений (4.3) и (4.4) даст соотношение: Тогда функция ошибки оценки направления отрезка на растре будет иметь вид:
Анализ этой функции показывает, что величина ошибки достигает экстремальных значений: максимума и минимума, - при определенных углах, равна нулю для осевого, диагонального и среднего между ними (я/8) направлений, а в точках экстремумов достигает значения по абсолютной величине 0,46. Тангенс этого угла составляет величину 0,008=1/125, что позволяет сделать вывод о том, что в пределах ближней зоны в 250 пикселов оценка точна с точностью до одного градуса.
В свою очередь средневзвешенная оценка длины отрезка имеет вид: где a - доля числа осевых ходов цепного кода; d - доля числа диагональных ходов; тогда принимаем, что a = 1 - d.
Отличие выражения (4.7) от аналогичных выражений (4.3) - (4.6) состоит в том, что в выражении (4.7) значения координат в СКСК из целочисленных значений переведены в относительные, т.е. произведено своеобразное масштабирование картины расположения вектора для соблюдения условия нормировки. При этом, нормируется не длина вектора, а суммарное количество диагональных и осевых переходов на дискретном растре.
Точное значение длины отрезка на растре определяется выражением: Тогда величина абсолютной погрешности оценки длины отрезка на растре имеет вид: а величина относительной погрешности определяется выражением:
Исходя из максимальных значений погрешностей, нетрудно определить размеры ближней зоны, в пределах которой погрешности оценок не превосходят величины одного пиксела и, соответственно, не приводят к переносу конечной точки отрезка в соседний пиксел. Эта величина составляет 142 пиксела для суммарной длины диагональных и осевых векторов переходов. Последнее условие определяет также и форму ближней зоны для длины редуцированного на дискретный растр отрезка.
Преобразовав оценки (4.3) и (4.7) к конечному виду, получим: - средневзвешенная оценка направления между диагональным и осевым направлением отрезка
Сжатие графической информации
Чрезвычайно большая информационная емкость изображений так или иначе ограничивает возможности их использования при решении различных научных и практических задач. Объемы обрабатываемой, передаваемой и хранимой современными информационными системами информации вызывают необходимость разработки методов эффективного безизбыточного кодирования или сжатия информации. Несмотря на то, что использование этих методов требует дополнительных затрат на кодирование и декодирование, а также приводит к некоторым потерям информации, свойственным отдельным методам, компрессия данных используется повсеместно, благодаря выигрышу, получаемому при хранении и передаче сжатых данных. Отдельное место в ряду методов сжатия данных занимают методы сжатия графической информации [5, 13].
Поскольку обработка графической информации происходит в несколько этапов, то уместно рассмотреть возможности ее сжатия на каждом из этапов.
Первым этапом обработки информации является адаптивное цветотоно-вое преобразование изображений. Как видно из рис. 1.8, 1.9, 1.13, 1.14, при этом происходит выравнивание тонов и цветов изображения. Кроме того, АЦТП позволяет произвести эквализацию текстур, что также приводит к образованию ровных однотонных и одноцветных областей на месте текстур исходного изображения. Таким образом, большая часть поля изображения оказывается заполненной ровными однотонными и одноцветными областями. Поэтому можно ожидать, что такие методы кодирования как кодирование длин серий (метод RLE [5,13]), приведет к существенному сжатию информации.
Непосредственное же применение метода кодирования длин серий к исходному изображению хотя и приводит к сжатию информации, но в незначительной степени. Причина этого в том, что при наличии шумов и помех, а также текстур на изображении, вариации цвета и тона настолько велики, что для большинства соседних пикселов изображения значения цветовых компонент не совпадают. Поэтому отсутствие повторений значений цветовых компонент для большинства соседних пикселов делает метод RLE малоэффективным.
Сказанное не означает, что выравнивание цветов после применения АЦТП, приводит к каким либо потерям информации. Более того, подавление шумов и помех даже улучшает качество изображения. Что касается возможных потерь информации на текстурных областях изображения, то следует иметь ввиду, что текстуры на графических изображениях применяются чаще всего для обеспечения визуального различения областей тогда, когда необходимо различать большое количество видов этих областей и простая цветовая палитра не обеспечивает уверенного их различения. Поэтому «стирание» текстур, во-первых, само по себе не приводит к потере информации, а во-вторых, может быть скомпенсировано заполнением этих областей соответствующими текстурами при последующем воспроизведении изображения.
Оценка возможной степени сжатия графической информации производилась экспериментально на выборе из нескольких десяткой графических изображений. После применение адаптивного цветотонового преобразования полученные изображения подвергались компрессии с помощью программы RAR. Степень сжатия информации оценивалась коэффициентом сжатия, который колебался на данной выборке от величины 70 до 180. Таким образом, полученные значения превосходят соответствующие показатели для большинства упакованных форматов растровых изображений (для которых эти величины составляют величину порядка 20-30). Исключение составляют такие форматы данных, как JPEG, которые при достижении сравнимых с АЦТП величин приводят к значительным потерям информации и чрезмерно заметному засорению изобра жений шумом. В то же время АЦТП, наоборот, подавляет шумы и улучшает качество исходного изображения. Применение же таких форматов данных как JPEG на уровне малых потерь информации (с малыми искажениями) дает на порядок более низкий уровень сжатия сравнительно с приведенными выше показателями.
Следует отметить, что вариации коэффициента сжатия определяются степенью сложности структуры графических изображений. Для простых изображений с малым количеством структурных элементов этот показатель достигает максимальных значений, а для высокодетальных изображений - принимает минимальное значение (около 70).
Однако, моделирование сжатия графической информации с помощью программы-архиватора RAR далеко не исчерпывает возможностей достижения предельных значений показателя сжатия. Поэтому был разработан алгоритм на основе преобразования Барроуза-Уилера (BWT) [5, 13] и написана соответствующая программа обработки изображений.
Метод сжатия информации на основе преобразования Барроуза-Уилера является блочно-сортирующим и поэтому долгое время не находил применения для задач сжатия изображений из-за необходимых дополнительных затрат памяти на буферы сортируемых символов.
Принципиальная схема методов на основе преобразования Барроуза-Уилера приведена на рис. 5.3.
