«САНКТ-ПЕТЕРБУРГСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ Тропченко А.Ю. МЕТОДЫ ВТОРИЧНОЙ ОБРАБОТКИ И РАСПОЗНАВАНИЯ ИЗОБРАЖЕНИЙ Учебное пособие по дисциплине Методы ...»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

САНКТ-ПЕТЕРБУРГСКИЙ НАЦИОНАЛЬНЫЙ

ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ

Тропченко А.Ю.

МЕТОДЫ ВТОРИЧНОЙ ОБРАБОТКИ И

РАСПОЗНАВАНИЯ ИЗОБРАЖЕНИЙ

Учебное пособие по дисциплине "Методы обработки и распознавания изображений" Санкт-Петербург 2012 2 Тропченко А.Ю. МЕТОДЫ ВТОРИЧНОЙ ОБРАБОТКИ ИЗОБРАЖЕНИЙ И РАСПОЗНАВАНИЯ ОБЪЕКТОВ. Учебное пособие. – СПб: СПбГУ ИТМО, 2012. – 52 с.

Учебное пособие охватывает основные методы теории цифровой обработки сигналов, используемые при вторичной обработке изображений, а также основы теории распознавания образов. Материал пособия разбит на 4 раздела и введение. В каждом разделе, кроме введения, приведены краткие теоретические сведения об используемых для решения соответствующих задач математических методах. Пособие может быть использовано при подготовке магистров по направлению 231000.68 «ПРОГРАММНАЯ ИНЖЕНЕРИЯ», 2301100.68 ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА, а также инженеров и аспирантов.

В 2009 году Университет стал победителем многоэтапного конкурса, в результате которого определены 12 ведущих университетов России, которым присвоена категория «Национальный исследовательский университет».

Министерством образования и науки Российской Федерации была утверждена программа его развития на 2009–2018 годы. В 2011 году Университет получил наименование «Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики».

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, А.Ю. Тропченко

СОДЕРЖАНИЕ

Введение………………………………………………………………………… 1. МЕТОДЫ ВТОРИЧНОЙ ОБРАБОТКИ ИЗОБРАЖЕНИЙ…………… 1.1. Задача сегментации изображений……………………………………….

1.2. Методы сегментации изображения (локализации объекта)………… 1.2.1. Метод порогового ограничения………………………………………….

1.2.2.Операции над бинарными изображениями……………………………...

1.2.3. Сегментация с адаптивным выбором порога…………………………… 1.2.4. Метод наращивания областей…………………………………………….

1.3. Методы выделения границ объектов…………………………………… 1.3.1. Градиентный метод ………………………………………………………..

1.3.2. Выделение контуров……………………………………………………….

1.3.3. Градиентная обработка при линейной фильтрации……………………...

1.4. Описание контура объекта………………………………………………..

1.5. Скелетизация объекта……………………………………………………… 1.6. Выделение характерных точек объекта…………………………………..

2. ПРИКЛАДНЫЕ ЗАДАЧИ ОБРАБОТКИ ИЗОБРАЖЕНИЙ…………….

2.1. Сжатие цифровых изображений…………………………………………… 2.1.1. Представление цифровых изображений

2.1.2. Классификация методов сжатия. Основные характеристики..................

2.1.3. Алгоритмы сжатия изображений без потерь

2.1.3.1. Сжатие способом кодирования серий (RLE)

2.1.4. Алгоритмы сжатия с потерями

2.1.4.1. Метод усеченного блочного кодирования (УБК)

2.1.4.2. Сжатие по стандарту JPEG

2.1.4.3. Сжатие по методу WIC (Wavelet Image Compression)

2.1.4.4. Фрактальное сжатие изображений

2.2. Стандарты сжатия видеоданных

2.2.1. Особенности сжатия видеоданных

2.2.2. Основные процедуры сжатия видеоданных

2.2.3. Цветовые пространства и их преобразование

2.2.4. Форматы семплирования

2.2.5. Устранение пространственной статистической избыточности...............

2.2.6. Модель DPCM/DCT видеокодека

2.2.7. Анализ возможностей современных стандартов сжатия видеоданных

2.3.Методы маркирования цифровых изображений………………………..

2.3.1.Анализ технологий обеспечения безопасности мультимедиа информации ………………………………………………………...

2.3.2. Основные понятия технологии сокрытии информации ………………… 2.3.3. Основные требования к технологии сокрытия информации……………..

2.3.4. Области применения технологий сокрытия информации и их классификация……………………………………………………………..

2.3.5. Анализ технологий цифрового маркирования………………………… 2.3.5.1. Структура системы маркирования изображений цифровыми водяными знаками…………….………………………………… 2.3.5.2. Математическая модель стегосистемы ……………………………….

2.3.5.3. Классификация и свойства цифровых водяных знаков……………….

2,3.3.6. Особенности цифрового маркирования неподвижных изображений……………………………………………………………………… 2.3.6.1. Свойства СЧЗ, учитываемые при разработке алгоритмов маркирования изображений……………………………………………………… 2.3.6.2. Учет особенностей алгоритмов сжатия цифровых изображений ……………….……………………………………………………… 2.3.7. Алгоритмы маркирования изображений в пространственной области ………..………………………………………..… 2.3.7.1. Маркирование изображений по методу Corvi …………………………..

2.3.7.2 Встраивание ЦВЗ по алгоритму Bruyndonckx …………………………...

2.3.7.3. Исследование устойчивости алгоритма Bruyndonckx …………………..

2.3.8. Встраивание ЦВЗ в области преобразования..…………………………….

2.3.8.1. Выбор преобразования для встраивания ЦВЗ…………………………… 2.3.8.2. Алгоритмы встраивания ЦВЗ в коэффициенты дискретного косинусного преобразования………………………………………..

2.3.8.3. Алгоритм маркирования Fridrich ………………………………………...

2.3.8.4. Алгоритм встраивания логотипа в коэффициенты ДКП (Benham) ……..

3. ОСНОВЫ ТЕОРИИ РАСПОЗНАВАНИЯ ОБРАЗОВ………………………..

3.1. Методы распознавания на основе сравнения с эталоном…………………….

2.2. Методы, основанные на понятии пространства признаков………………….

3.3. Построение решающих функций для двоичных наборов параметров……… 3.4. Определение расстояния между описаниями объектов……………………… 3.5. Вероятностный подход к распознаванию……………………………………… 3.6. Синтаксическое распознавание………………………………………………… 3.7. Распознавание на основе анализа двумерных гистограмм…………………… 4. ПРИКЛАДНЫЕ ЗАДАЧИ РАСПОЗНАВАНИЯ ИЗОБРАЖЕНИЙ………..

4.1. Классификация и применение искусственных нейронных сетей………..

4.1.1. Основные классы решаемых задач при распознавании человека по изображению лица …………………………………………………….

4.1.2. Поиск изображения в больших базах данных ……………………………….

4.1.3. Задача контроля доступа ……………………………………………………...

4.1.4. Задача контроля фотографии в документах ………………………………… 4.1.5. Нейросетевые методы распознавания человека по изображению лица …...

4.1.6. Модель искусственного нейрона……………………………………………...

4.1.7. Классификация нейронных сетей……………………………………………..

4.2. Разделение пространства признаков на области ………………………….

и извлечение ключевых признаков ……………………………………………… 4.2.1. Многослойные нейронные сети ……………………………………………… 4.2.2. Нейронные сети высокого порядка и моментные НС ……………………… 4.2.3. Радиально-базисные нейронные сети ………………………………………..

4.3. Топологически упорядоченное преобразование пространства ………….

4.4. Распознавание с учтом топологии пространства ………………………… 4.4.1. Когнитрон ……………………………………………………………………...

4.4.2. Неокогнитрон…………………………………………………………………..

4.4.3. Сврточные нейронные сети ………………………………………………….

4.5. Достоинства и недостатки нейросетевых методов распознавания……… 4.6. Применение ИНС для извлечения ключевых характеристик…………… 4.6.1. Применение ИНС для извлечения ключевых характеристик лица………… 4.7. Применение ИНС для классификации образов …………………………...

4.7.1. Применение ИНС для классификации напрямую по входным сигналам………………………………………………………………...

4.7.2. Применение ИНС для классификации по заранее извлеченным признакам………………………………………………… 4.7.2.1. Метод собственных фильтров для распознавания лица………………….

4.7.2.2. Метод сравнения эластичных графов на основе вейвлетов Габора……… 4.7.2.3 Методы распознавания на основе Скрытых Марковских моделей……….

4.7.2.4.Эксперименты по распознаванию лица……………………………………..

4.8. Аппаратные и программные средства реализации ИНС………………….

4.8.1 Программное обеспечение для моделирования ИНС………………………..

4.8.2. Аппаратная реализация нейронных сетей…………………………………… 4.8.3. Принципы построения нейросистем на базе нейрочипа…………………….

Заключение…………………………………………………………………………..

Литература…………………………………………………………………………...

В развитии систем технического зрения наметилось два направления.

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

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

Назначение таких систем — исследование и испытание алгоритмов обработки изображений для различных технологических ситуаций, а также автоматизированное проектирование архитектур и схемотехники вычислителей, реализующих полученные алгоритмы [1,7,13].

Второе направление — создание специализированных систем технического зрения для конкретных роботов [39]. Исходной информацией при этом могут служить результаты предварительного моделирования системы на универсальном комплексе либо априорные сведения о характере входных изображений и эвристические соображения об алгоритмах их обработки.

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

Повышение качества изображений достигается двумя видами обработки изображений: реставрацией (исправлением) изображений и их улучшением [13]. Под реставрацией обычно понимают процедуру восстановления или оценивания элементов изображения, целью которой является коррекция искажений и наилучшая аппроксимация идеального неискаженного изображения. Для улучшения изображений используется комплекс операций, призванных улучшить восприятие изображения наблюдателем или же преобразовать его в другое изображение, более удобное для машинной обработки.

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

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

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

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

Центральное место среди названных понятий занимает задача распознавания образов [14,25,38]. Решение ее техническими средствами может быть осуществлено путем моделирования операций, выполняемых живыми организмами в процессе коммуникации и восприятия окружающего мира. Эти способности достаточно хорошо изучены на различных животных (киты, дельфины, летучие мыши, некоторые приматы). Однако наиболее естественно положить в основу модели распознавания способности человека и его реакции на окружающую действительность.

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

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

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

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

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

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

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

отделение символьной информации от графической и визуальной информации;

распознавание и интерпретация каждого символа.

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

О сложности распознавания рукописных знаков свидетельствует тот факт, что даже человек, читая их при отсутствии контекста, делает около 4 % ошибок [14]. Причины ошибок кроются в бесконечном разнообразии вариаций формы знаков, которые обусловлены наличием ограничений в начертании знаков и символов или их отсутствием, стилем, образованием, опытом, настроением, здоровьем и другими характеристиками пишущего, а также в качестве пишущего инструмента и поверхности, на которой пишут, методах считывания и алгоритмах распознавания.

1. МЕТОДЫ ВТОРИЧНОЙ ОБРАБОТКИ ИЗОБРАЖЕНИЙ

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

снятие информации, предварительная обработка информации, сегментация, описание, распознавание, интерпретация [14].

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

Распознавание представляет собой процесс идентификации объектов.

Интерпретация выявляет принадлежность к группе распознаваемых объектов.

Таким образом, обработка изображений является многоэтапной процедурой, причем каждому этапу соответствует изображение того или иного вида (см. рис.1.1).

Все подлежащие обработке изображения могут быть подразделены на типа [6,7]:

1 - многоуровневые или полутоновые изображения;

2 - бинарные изображения или битовые карты изображений;

3 - изображения характерных линий контуров или скелетов объектов на изображении;

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

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

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

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

Преобразование Используемые процедуры 1.1. Задача сегментации изображений Объект изображения (образ) можно рассматривать как совокупность областей интенсивности. Для выделения области интенсивности на изображении можно использовать не только методы распознавания образов, но и методы разбиения изображений или методы сегментации областей. Алгоритмы сегментации можно рассматривать как формализацию понятия выделяемости объекта из фона.

Сегментацией называется процесс подразделения сцены на составляющие части или объекты. Сегментация является одним из основных элементов работы автоматизированной системы технического зрения, т.к. именно на этой стадии обработки объекты выделяются из сцены для дальнейшего распознавания и анализа. Сегментация изображения представляет собой разделение или разбиение изображения на области по сходству свойств их точек [1,13,30]. Наиболее часто сегментацию проводят по яркости для одноцветного изображения и цветовым координатам для цветного изображения.

Конечной целью сегментации изображений является разбиение поля зрения D на области объектов D1,..., Ds и область фона Dф.

1.2. Методы сегментации изображения (локализации объекта) Методы и алгоритмы сегментации можно рассматривать как формализацию понятия выделяемости объекта из фона.

Надежность алгоритмов сегментации зависит от того, насколько точно и полно при этом учтена дополнительная информация, которая в основном состоит из следующих сведений [13,14]:

число объектов S;

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

оценки яркостного перепада при переходе из области фона в область объектов;

форма объекта;

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

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

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

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

Бинаризация по порогу. Одним из путей отделения объектов от фона является выбор порогового значения P. Тогда любая точка (x,y), для которой интенсивность f(x,y)>T, принадлежит объекту, в противном случае - фону.

Пороговое изображение получается путем определения где P - порог чувствительности; bij - пиксел исходного изображения; Bij - бит с теми же координатами выходного изображения.

Таким образом, на изображении В(х,у) пиксели со значением относятся к объектам, в то время как пиксели со значением 0 относятся к фону.

Бинаризация по диапазону. Наиболее просто пороговая обработка осуществляется в случае, когда заранее известно, что изображение состоит из одного объекта и фона, причем яркость точек объекта находится в пределах {P0,P1}, а точек фона либо меньше P0, либо больше P1 [13].

При бинаризации в целях выделения сегментов может быть произведено выделение пустых строк и пустых столбцов:

1.2.2.Операции над бинарными изображениями.

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

(заметим, что инверсия соответствует получению негатива бинарного изображения) Кроме того над бинарным изображением могут быть выполнены так называемые морфологические операции [13]:

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

1.2.3. Сегментация с адаптивным выбором порога Рассмотренные выше классические методы сегментации основаны на использовании порога интенсивности. Главная трудность заключается в выборе этого порога.

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

Допустим, что известно некоторое соотношение, связывающее яркость точки фона и объектов, например:

для любых точек (m,n), принадлежащих фону и (u,v), принадлежащих объектам сцены.

В этом случае можно заключить, что для любой точки (u,v) любого объекта выполнено условие Найдем теперь глобальный максимум части гистограммы - в области [а, b max - T]. Пусть он достигается в точке b1max. Следует ожидать, что b1max яркость наиболее встречающаяся в точках объектов. Таким образом можно заключить, что для любой точки (m,n) области фона выполнено условие Два последних соотношения дают пороги яркости для точек объектов и фона.

Аналогичные рассуждения имеют место и в случае, когда мы располагаем неравенством где Q > 1 - известный коеффициент.

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

Пусть известно, что где < 1 - известный коэффициент; S(E) - число точек области E.

Введем зависимость число точек растра. Эта априорная информация позволяет заключить, что число точек Поэтому можно сделать вывод, что яркость фона заключена в пределах [b0max-*, b0max+*], где * - решение уравнения Точное решение уравнения обычно не представляется возможным, поэтому в качестве * следует выбрать такое значение, чтобы где h - шаг изменения.

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

В случае существенного разброса яркости объектов методы обработки гистограммы малоприменимы.

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

Алгоритмы наращивания областей используют информацию о связности объектов и основаны на рекуррентном способе разметки точек.

На шаге k размечаются те и только те точки, которые имеют соседей из числа размеченных на предыдущем шаге (k-1). Разметка точек осуществляется согласно некоторому критерию однородности.

Конкретные алгоритмы различаются выбором критерия однородности, способом просмотра точек и выбором начальных "стартовых" точек, размечаемых на нулевом шаге.

Известно два основных подхода к стратегии выбора стартовых точек и порядка просмотра остальных: центроидное связывание и слияниерасщепление объекта [13,39].

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

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

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

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

Выбор стартовых точек - нулевой шаг алгоритмов центроидного связывания. Переход от шага с номером k к шагу с номером (k+1) осуществляется следующим образом. Пусть Sk - множество точек, размеченных после реализации шага с номером k. На очередном, (k+1)-м, шаге разметке подлежат точки, примыкающие к Sk, т.е. не принадлежащие Sk, но имеющие хотя бы одного соседа из Sk. Пусть A - одна из таких точек.

Через 1, …, p обозначим метки, используемые для разметки точек из Sk.

Рассмотрим два возможных случая.

Все размеченные соседи A имеют одну и ту же метку j. В этом случае точка A размечается либо меткой, либо меткой, т.е. еще не использованной. Первый вариант осуществляется при выполнении некоторого условия однородности. Обычно оно имеет вид |B(A) -Bj| < T, где B(A) - яркость в точке A; Bj - средняя яркость точек с меткой j; T выбранный порог.

Соседние A точек из Sk имеют различные метки 1, …, l. В этом случае проверяется условие |B(A) -Bi| < T при каждом i=1,…, l. Если оно выполнено для единственного i=i0, то точка A получает метку i0. Если же условие не выполнено ни при каком i=1,…, l, то точка A получает новую метку p+1. В наиболее сложном случае условие справедливо для нескольких значений, например для i=1 и i=2. В этом случае сливаются две области - области точек с метками 1 и 2 соответственно. Под слиянием понимается переход от меток 1, 2 к единой метке min (1, 2).

В случае слияния областей меняется частичная разметка, полученная на шаге k. Поэтому анализ большинства точек изображения следует провести заново. Конечно, необходимость повторных проходов по полю изображения резко увеличивает время реализации алгоритма. Слияние областей - наиболее ответственные моменты алгоритмов центроидного связывания. Чем меньшее число раз возникает вопрос о слиянии областей, тем выше надежность алгоритма, тем меньше время, необходимое для его реализации. Число слияний областей зависит от правильности выбора порога T и стартовых точек.

Результаты сегментации в алгоритмах центроидного связывания зависят и от порядка просмотра точек. Технически наиболее просто осуществляется сканирование поля зрения по строкам. Однако для сложных изображений более надежным является "волновой" способ просмотра точек. Для каждой метки 1, …, s, соответствующей некоторой стартовой точке, строится "волна". Волной называется набор множеств точек, называемых фронтами (они обозначаются индексами 0,1,2,…).

Нулевой фронт F0(i), соответствующий метке i, есть просто подмножество стартовых точек с этой меткой. Фронт Fk+1(i) определяется как множество точек, которые не принадлежат Fk(i), но имеют соседей из Fk(i).

Порядок просмотра точек определим теперь следующим образом.

Сначала обрабатываются точки первого фронта всех волн, соответствующих меткам 1, …, s, затем - точки второго фронта и т.д.

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

Основными недостатками метода центроидного связывания являются:

отсутствие правила для выбора порога, фигурирующего в критерии однородности области;

необходимость повторных проходов в случае слияния областей.

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

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

Будем считать, что поле зрения D является растром размером mm, причем m = 2k. Отдельные точки растра (пиксели) назовем областями нулевого уровня и обозначим их S0ij, i,j = 1,…, 2k. Определим теперь области первого уровня как объединения четырех смежных областей нулевого уровня, а именно:

причем i,j = 1,2,…, 2k-1.

При произвольном p k определим теперь области p-го уровня в виде объединения областей (p-1)-го уровня:

Spi,j = Sp-12i-1,2j-1 Sp-12i-1,2j Sp-12i,2j-1 Sp-12i,2j, i,j = 1,2,…, 2k-p. Последний уровень имеет номер k. Для k-го уровня есть только одна область, совпадающая с растром D.

Отметим основные свойства указанных разбиений:

число областей уровня p, 0 p k, равно 22(k-p);

объединение областей любого уровня есть растр D;

каждая область уровня p состоит из 22p точек растра;

каждая область уровня (p+1) есть объединение четырех смежных областей уровня p.

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

На следующем шаге рассматриваются области 2-го уровня, но не все, а только такие области S2i,j, для которых соблюдается условие: для каждой из областей S12i-1,2j-1, …, S12i,2j выполнен критерий однородности (это проверяется на предыдущем шаге), т.е. они уже представляют собой один элемент изображения. Теперь критерий однородности проверяется для набора S12i-1,2j-1, …, S12i,2j, т.е. вычисляется разброс четырех значений яркости, соответствующих этим областям (теперь уже - элементам изображения). При выполнении условия однородности указанные области сливаются в единый элемент изображения с усредненной яркостью.

Такая процедура осуществляется последовательно на 1-, 2-,…, l-м уровнях. Заканчивается она на некотором уровне l, когда выполнено следующее условие: для любой области Sli,j, либо ни одна из областей SlSl-12i,2j, не является единым элементом изображения 2i-1,2j-1, (информация об этом имеется после анализа (l-1)-го уровня), либо те из этих областей, которые являются едиными элементами изображения, не удовлетворяют условию однородности, т.е. не могут быть слиты.

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

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

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

Понятие границы объекта так же, как и понятие самого объекта, невозможно точно формализовать в терминах цифрового изображения B(i,j). Из эвристических соображений граничные точки ищут как точки резкого перепада функции яркости.

Если представить изображение растра D как функцию B(x,y) в плоскости (x,y), и считать, что B(x,y) - дифференцируемая функция своих аргументов, то перепад яркости в точке (x0,y0) определяется как норма градиента функции B(x,y) в точке (x0,y0), т.е. норма вектора норму вектора можно определить различными способами.

Однако в силу дискретности поля зрения D непосредственное дифференцированием для определения перепада яркости в точке, необходимо выбрать один из двух путей [6]:

с помощью интерполяции перейти от функции B(i,j) к функции B(x,y), заданной в прямоугольной области плоскости (x,y), содержащей все точки растра D;

воспользоваться методами численного дифференцирования, т.е.

дифференцирования таблично заданной функции.

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

Градиент изображения f(х,у) в точке (х,у) определяется как двумерный вектор:

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

Для цифрового изображения это можно сделать несколькими путями.

Один из подходов состоит в использовании разности между соседними пикселами:

Несколько более сложный способ включает пикселы в окрестности размерностью 3х3 с центром в точке (х,у).

Существует множество способов формирования выходного изображения g(x,y), основанных на вычислении градиента. Простейшим способом является задание функции g в точке (x,y) значения, равного величине градиента входного изображения f в этой точке.

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

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

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

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

При таком анализе для установления подобия пикселов контура необходимо определить[13]:

1. Величину градиента, требуемого для построения контурного пиксела G[f(x,y)];

2. Направление градиента.

Таким образом, пиксел контура с координатами (х,у) подобен по величине в определенной ранее окрестности (х,у) пикселу с координатами (х,у), если справедливо неравенство где Т - пороговое значение.

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

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

1.3.3. Градиентная обработка при линейной фильтрации Для выделения контуров объектов на изображении может быть использован метод линейной фильтрации, основанный на вычислении апериодической свертки фрагмента изображения со специальным ядром в пространственной области. Соответственно, используемое для вычислений ядро будет определять тип линейного фильтра. Для выделения контуров методом линейной фильтрации наиболее часто используют следующие виды фильтров [13]:

1. разностный амплитудный фильтр 2. максимальный разностный амплитудный фильтр 3. фильтр Робертса На практике описание выделенного контура достатоточно просто производится при использовании цепного кода Фримана [14]. Такой подход позволяет от двумерных объектов перейти к их одномерному (векторному) описанию, т.е. построение цепного кода может рассматриваться и как процедура векторизации изображения.

При выполнении кодирования цепным кодом строится так называемая матрица направлений или матрица связности центральной точки локальной окрестностиразмера 3 х 3 со всеми возможными соседними точками:

Каждое из 8-ми возможныых направлений перехода от точки B ij к точке B i 1, j 1 кодируется трехбитным кодом.

Затем адается начальная точка, с которой начинают обход выделенного контура - пусть это будет крайняя левая верхняя точка (рис.2.3).

Рис.1.2. Описание контура объекта цепным кодом Фримена В нашем случае это точка A0 (13) Тогда контур может быть описан как:

A0 (13) 0;0;710;7;7;0;0;0;7;5;4;4;4;4;4;3;4;4;5;5;4;3;2; Под скелетизацией или утоньшением будем понимать преобразование изображения, удовлетворяющее следующим условиям:

после преобразования все линии имеют толщину в 1 элемент;

преобразование не нарушает топологию символа;

преобразование не нарушает размеров символа.

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

Вначале определим признаки характерных точек локальной окрестности (окна) при скелетизации объекта.

Признак того, что элемент является верхним в окне:

Признак того, что элемент является левым в окне:

Признак того, что элемент является правым в окне:

Признак того, что элемент является нижним в окне:

При скелетизациии необходимо удалять (стирать) отдельные элементы изображения объекта в окне сканирования. Условия стирания могут быть определены с учетом полученных признаков характерных точек окна:

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

Процесс продолжается до тех пор, пока все функции (1) - (4) не обратятся в единицу. Если одна из функций обратилась в единицу, то по этому направлению утоньшение прекращается.

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

1.6. Выделение характерных точек объекта К характерным точкам объекта относится, в частности, центр тяжести (центр масс объекта). Определение его координат оказывается важным при отслеживании траектории перемещения объекта [1,7,14].

1. Определение координат центра масс объекта С учетом "веса" отсчетов для многоуровневых ("трехмерных") изображений 2. Заполнение контура (алгоритм штриховки или заливки) а) по критерию четности;

б) по критерию "связности";

3. Определение координат центра тяжести объемного объекта:

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

Схематически такой процесс представлен на рис. 1.4.

Рис.1.4. Переход от изображения к набору признаков при распознавании

2. ПРИКЛАДНЫЕ ЗАДАЧИ ОБРАБОТКИ ИЗОБРАЖЕНИЙ

телекоммуникационных систем, предназначенных для приема и передачи видеоданных.

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

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

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

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

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

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

Для простоты рассмотрим сначала монохромные изображения.

Интенсивность излучаемой световой энергии с единицы поверхности в точке с координатами (, ) изображения можно представить некоторым числом B(, ). Единичный элемент изображения, характеризуемый определенным значением (, ), называется пикселем, а величина z f (,) - яркостью [1].

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

Рис.2.1. Технические средства телекоммуникационной системы для передачи видеоданных и их функциональное назначение.

С математической точки зрения, изображения в градациях серого можно представить как вещественную функцию I двух вещественных переменных x и y. Функция I(x,y) изображения в общем случае определяется в прямоугольной области, но для удобства исследований в работе все изображения определяются в квадратных областях,.т.е x[0;W], а y[0;H], где W – ширина изображения, а H – высота изображения и W=H.

Все изображения можно подразделить на две группы: с палитрой и без не. У изображений с палитрой в пикселе (одном из отчтов изображения – значение функции I(x,y) для конкретного xi и yi) храниться число – индекс в некотором одномерном векторе цветов, называемом палитрой. Палитры обычно бывают 8, 16 и 256 – цветов[13].

Изображения без палитры обычно бывают в определенной системе цветопредставления или в градациях серого. В градациях серого значения каждого из пикселей определяется как яркость точки. Наиболее часто встречаются изображения с 2-мя, 16-ю и 256-ю уровнями серого.

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

Наиболее распространнной системой цветопредставления, используемой в электронных и компьютерных системах, является система RGB. В этой системе цвет определяется как комбинация красного, зелного и синего цвета. И на каждую из составляющих приходиться по одному байту. Существуют и другие системы цветопредставления, такие как CMYK, CIE, YUU и YCrCb [13, 30].

Для того чтобы корректнее оценивать степень сжатия изображения, и применимости того или иного алгоритма сжатия к данному изображению вводится понятие класса изображения [13].

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

Условно можно выделить следующие классы изображений:

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

изображения с плавными переходами цветов, построенные на компьютере:

графика презентаций и виртуальные модели;

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

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

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

высокая степень компрессии;

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

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

высокая скорость декомпрессии (данное требование актуально почти для всех приложений).

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

учт специфики изображения (данное требование реализуют алгоритмы сжатия, основанные на определении «области особого назначения» (ROI – regions of interest)).

2.1.2. Классификация методов сжатия. Основные характеристики Все методы сжатия информации основаны на том простом предположении, что набор данных всегда содержит избыточные элементы.

Сжатие достигается за счет поиска и кодирования избыточных элементов [4,31].

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

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

Зная эти частоты, строят таблицу кодов, обладающую следующими свойствами:

различные коды могут иметь различное количество бит;

коды символов с большей частотой встречаемости, имеют меньше бит, чем коды символов с меньшей частотой;

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

Этими свойствами обладает известный алгоритм Хаффмана [4].

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

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

До сих пор не существует простой и адекватной модели визуального восприятия изображений, пригодной для оптимизации их кодирования [4].

Задача сжатия изображения состоит из двух основных частей:

кодирование и декодирование. Если декодированное изображение всегда в точности соответствует кодируемому изображению, то такой алгоритм кодирования-декодирования называется алгоритмом сжатия без потерь. Если декодированное изображение отличается от кодированного, то подобный алгоритм называют алгоритмом сжатия с потерями. Общая схема процесса сжатия изображения представлена на рис. 2.2 [4].

Рассмотрим этапы процедуры сжатия данных в общем виде. Любой метод сжатия реализует три основных этапа (рис. 2.2):

кодирование или первичное сжатие;

вторичное сжатие;

декодирование или восстановление изображения.

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

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

Существует несколько различных подходов к проблеме сжатия информации. Одни имеют весьма сложную теоретическую математическую базу, другие основаны на свойствах информационного потока и алгоритмически достаточно просты. Любой способ, реализующий сжатие данных, предназначен для снижения объема выходного потока информации помощи обратимого или необратимого преобразования. Поэтому все способы сжатия можно разделить на две категории: обратимое и необратимое сжатие [3,7]. Методы сжатия цифровых изображений можно классифицировать по их основным характеристикам, таким как: точность восстановления, симметричность основного преобразования и тип используемого преобразования [7].

Исходное изображение Исходное изображение Преобразованное изображение Матрица пикселов Набор коэффициентов преобразования ( значения интенсивности) ( фрактальное сжатие) Классификация наиболее распространенных методов сжатия приведена на рис.2.3.

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

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

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

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

Без потери качества изображения С потерей качества изображения

JBIG WIC

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

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

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

1. Коэффициент сжатия (Ксж).

Этот параметр определяет во сколько раз файл, хранящий сжатое изображение, меньше файла, хранящего исходное изображение. Величины V и V2 выражаются в байтах. Ксж – величина безразмерная.

2. Оценка качества декодированного изображения.

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

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

Пусть есть два изображения: f ( x, y ) - оригинал, и f ( x, y ) восстановленное изображение размером MxN, тогда одним из простых критерием оценки потери качества является среднеквадратическое отклонение значений пикселей сжатого изображения от оригинала:

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

Другим критерием является максимальное отклонение от оригинала:

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

На практике используемой мерой качества изображения является критерий соотношения сигнал/шум (PSNR).

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

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

К другим наиболее употребляемым критериям оценки качества изображения относятся:

Средняя разность:

Коэффициент кросс-корреляции:

Верность изображения (image fidelity):

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

3. Время преобразования Различают две величины – время сжатия (tсж) и время восстановления (tвосст).

Время сжатия состоит из времени работы основного преобразования (tоп) и времени упаковки (tуп). Время восстановления состоит из времени распаковки (tрасп) и времени работы обратного преобразования (tоб) :

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

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

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

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

потери качества (у большинства алгоритмов сжатия с потерей информации существует возможность изменения коэффициента сжатия);

характерные особенности алгоритма и изображений, к которым его применяют.

2.1.3. Алгоритмы сжатия изображений без потерь Сжатие способом кодирования серий (RLE). Наиболее известный и простой алгоритм сжатия информации обратимым путем - это кодирование серий последовательностей (Run Length Encoding - RLE) [4,31]. Суть данного подхода состоит в замене цепочек или серий повторяющихся байтов или их последовательностей на один кодирующий байт и счетчик числа их повторений. Проблема всех аналогичных методов заключается лишь в определении способа, при помощи которого распаковывающий алгоритм мог бы отличить в результирующем потоке байтов кодированную серию от других - некодированных последовательностей байтов. Решение проблемы достигается обычно простановкой меток вначале кодированных цепочек.

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

Лучший, средний и худший коэффициенты сжатия - 1/32, 1/2, 2/1.

Данные методы, как правило, достаточно эффективны для сжатия растровых графических изображений (BMP, PCX, TIFF), т.к. последние содержат достаточно длинных серий повторяющихся последовательностей байтов.

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

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

Применительно к сжатию изображений в основе такого метода лежит учет частоты появления одинаковых байт в изображении. При этом пикселам исходного изображения, которые встречаются большее число раз, сопоставляется код меньшей длины, а встречающимся редко - код большей длины (т.е. формируется префиксный код переменной длины). Для сбора статистики требуется два прохода по файлу - один для просмотра и сбора статистической информации, второй - для кодирования [31]. Коэффициенты сжатия: 1/8, 2/3, 1.

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

Методы Хаффмана дают достаточно высокую скорость и умеренно хорошее качество сжатия.

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

Алгоритм Лемпеля-Зива (LZ-compression). Суть данного алгоритма состоит в следующем: упаковщик постоянно хранит некоторое количество последних обработанных символов в буфере. По мере обработки входного потока вновь поступившие символы попадают в конец буфера, сдвигая предшествующие символы и вытесняя самые старые. Размеры этого буфера, называемого также скользящим словарем, варьируются в разных реализациях кодирующих систем. Затем, после построения хеш-таблиц, выделяют (путем поиска в словаре) самую длинную начальную подстроку входного потока, совпадающую с одной из подстрок в словаре, и выдают на выход пару (length, distance), где length - длина найденной в словаре подстроки, а distance расстояние от нее до входной подстроки (то есть фактически индекс подстроки в буфере, вычтенный из его размера). Если такая подстрока не найдена, в выходной поток просто копируется очередной символ входного потока [4].

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

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

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

К достоинствам LZ можно отнести чрезвычайную простоту алгоритма декомпрессии.

Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch -LZW). Данный алгоритм отличают высокая скорость работы как при упаковке, так и при распаковке, достаточно скромные требования к памяти и простая аппаратная реализация. Недостаток - низкая степень сжатия по сравнению со схемой двухступенчатого кодирования. Алгоритм преобразует поток символов на входе в поток индексов ячеек словаря на выходе. Существует довольно большое семейство LZW - подобных алгоритмов, различающихся, например, методом поиска повторяющихся цепочек [4].

Коэффициенты сжатия: 1/1000, 1/4, 7/5. Коэффициент 1/ достигается только на одноцветных изображениях размером больше 4 Мб.

Ситуация, когда алгоритм увеличивает изображение, встречается крайне редко.

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

LZW универсален - именно его варианты используются в обычных архиваторах. Он реализован в форматах GIF, TIFF и TGA.

Алгоритм JBIG. Алгоритм разработан группой экспертов ISO (Joint Bilevel Experts Group) специально для сжатия однобитных черно-белых изображений (например, для факсов или отсканированных документов). В принципе может применяться и к 2-х, и к 4-х битовым картинкам. При этом алгоритм разбивает их на отдельные битовые плоскости. JBIG позволяет управлять такими параметрами, как порядок разбиения изображения на битовые плоскости, ширина полос в изображении, уровни масштабирования.

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

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

Распаковываться изображение на экране будет постепенно, как бы медленно "проявляясь". При этом человек начинает анализировать картинку задолго до конца процесса разархивации. Алгоритм построен на базе Q-кодировщика, патентом на который владеет IBM. Q- кодер также, как и алгоритм Хаффмана, использует для чаще появляющихся символов короткие цепочки, а для реже появляющихся длинные. Однако, в отличие от него, в алгоритме используются и последовательности символов. Характерной особенностью JBIG является резкое снижение степени сжатия при повышении уровня шумов исходного изображения [3,7].

Алгоритм Lossless JPEG. Этот алгоритм разработан группой экспертов в области фотографии (Joint Photographic Expert Group). В отличие от JBIG, Lossless JPEG ориентирован на полноцветные 24-битные изображения [4,31,37].

Коэффициенты сжатия: 1/20, 1/2, 1.

Стандарт сжатия изображений JPEG включает два способа сжатия:

первый предназначен для сжатия без потерь, второй – сжатия с потерей качества. Метод сжатия без потерь, используемый в стандарте lossless JPEG основан на методе разностного (дифференциального) кодирования. Основная идея дифференциального кодирования состоит в следующем. Обычно изображения характеризуются сильной корреляцией между точками изображения. Этот факт учитывается при разностном кодировании, а именно, вместо сжатия последовательности точек изображения x1,x2,....xN, сжатию подвергается последовательность разностей yi=xi-xi-1, i=1,2,...N, x0=0. Числа yi называют ошибками предсказания xi. В стандарте losslessJPEG предусмотрено формирование ошибок предсказания с использованием предыдущих закодированных точек в текущей строке и\или в предыдущей строке.

Lossless JPEG рекомендуется применять в тех приложениях, где необходимо побитовое соответствие исходного и разархивированного изображений.

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

В то же время сжатия с потерями оперируют с коэффициентами 10-200 раз.

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

2.1.4.1. Метод усеченного блочного кодирования (УБК) Название метода отражает тот факт, что изображение разбивается на небольшие прямоугольные куски одинакового размера, называемые блоками.

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

Базовый алгоритм УБК строится следующим образом [4]. Изображение, представленное M N - матрицей bij яркостей пикселей, разбивается на небольшие прямоугольные блоки m n элементов. Каждый такой блок обрабатывается независимо от других, поэтому опишем алгоритм обработки одного блока.

Обработка блока начинается с вычисления порога и двух уровней квантования, затем проводится квантование блока на два уровня, после чего следует упаковка проквантованного блока. Для определения уровней квантования сначала вычисляются два первых выборочных момента - среднее значение C и средний квадрат E :

(где суммируются элементы изображения в пределах блока) и дисперсия Пороговая величина квантователя d полагается равной среднему C.

Верхний a и нижний b уровни квантования вычисляются по следующим формулам:

где p m n - число элементов блока, q - число элементов, превышающих порог d.

Квантование проводится по правилу:

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

После квантования получается блок, содержащий только уровни a и b.

Нетрудно показать, что среднее значение и средний квадрат исходного и проквантованного блоков совпадают. Практически для удобства последующей упаковки вместо a записывается нуль, вместо b - единица. Уровни a и b записываются отдельно.

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

Восстановление закодированного изображения также проводится поблочно и состоит в распаковке и обратной подстановке.

Из алгоритма видно, что степень сжатия непосредственно зависит от размеров блока. Наиболее удовлетворительные результаты, как по степени сжатия, так и по качеству восстановленного изображения были получены при использовании блоков размером 4 4 [4,31].

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

JPEG - один из самых распространенных и достаточно мощных алгоритмов, представляет собой метод сжатия изображений, реализуемый различными способами [4,31,33]. Работает он как на черно-белых, так и на полноцветных изображениях.

Стандарт JPEG (Joint Photographic Experts Group - Объединенная экспертная группа по фотографии) - формат хранения фотографических изображений, отличающийся хорошим качеством восстановленного изображения. Процесс сжатия изображения JPEG достаточно сложен и часто для достижения приемлемой производительности требует специальной аппаратуры. Схема процедуры сжатия изображений по стандарту JPEG приведена на рис.2.4.

изображение Рис.2.4. Основные этапы процедура сжатия по стандарту JPEG Кодирование изображений по стандарту JPEG обычно начинается с преобразования цветового пространства из RGB в YUV (известное также под названием YCbCr). Цветное изображение традиционно может рассматриваться как результат сложения трех компонент:

В этом выражении a1, a2, a3 - калориметрические коэффициенты.

В типичных изображениях в формате RGB имеется существенная корреляция между цветными компонентами и с точки зрения сжатия изображения этот формат является заведомо избыточным. Как известно, в стандартах телевизионного вещания используется другое представление изображений, при котором также используются 3 компоненты сигнала, но при этом эти компоненты почти некоррелированы друг с другом. Компоненты R,G и B преобразуются в яркостную компоненту Y и две цветоразностных компоненты U и V, формата YUV.

Преобразование форматов выполняется по формулам:

для преобразования RGBYUV и для преобразования YUVRGB В формате YUV компоненты слабо коррелированны. Более того, так как большая часть информации сосредоточена в яркостной компоненте, то будет потеряно мало информации, если выполнить децимацию (прореживание) компонент U и V с коэффициентом 2. При таком прореживании 4 соседние точки (квадрат 2х2) описываются 4 значениями компонент Y и по одному значению компонент U и V.

Результатом является стандартный формат YUV 4:1:1, который, как правило, является входным для большинства видеокодеров. Таким образом, получается сжатие в 2 раза без сколько-нибудь заметного искажения изображения.

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

Далее исходное изображение разбивается на матрицу клеток одинакового размера (чаще всего 88 пикселов).Такой размер выбран по следующим причинам [7]:

С точки зрения аппаратной и программной реализации размер блока 8х8 не накладывает существенных ограничений на размер требуемой памяти.

Вычислительная сложность ДКП для блока 8х8 также является приемлемой для большинства вычислительных платформ.

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

Выбор ДКП в качестве стандартного решения диктуется следующими причинами:

Для изображений с сильно коррелированными отсчетами (коэффициент корреляции >0,7) эффективность ДКП в смысле компактности представления данных близка к преобразованию Карунена-Лоэва (это преобразование является оптимальным в том смысле, что оно ортонормированно и гарантирует некоррелированность коэффициентов преобразования – элементов Y).

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

Обработка каждой клетки выполняется независимо и заключается в выполнении ДКП по строкам и столбцам клетки, которое имеет вид:

В выражении (1.13) множитель C(u,v) является нормирующим и равен 1/2 при u=0 или v=0 и равен единице для остальных значений индексов.

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

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

(где cas[...] = cos[....] + sin[...]), которое может быть вычислено по быстрому алгоритму; после чего выполняются дополнительные вычисления с элементами вектора результатов преобразования Хартли:

где k = [1,...,N-1], причем c^ 0 H0.

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

К неудобствам косинусного преобразования следует отнести:

неразделимость ядра преобразования для двумерного варианта;

негибкие алгоритмы для различного размера ядра;

несимметричный алгоритм обратного косинусного преобразования.

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

В результате выполнения ДКП формируется 64 частотных компоненты фрагмента (или, что тоже, коэффициентов ДКП). В результате исходный фрагмент представлен в области пространственных частот. Этот шаг еще не приводит к сжатию изображения. Однако, при его выполнении полагается, что в подавляющем большинстве изображений близкие по своим координатам пикселы имеют и близкие значения. Поэтому, при переходе от фрагмента к его частотному представлению большая часть энергии сигнала сосредотачивается в области низких частот, т.е. компоненты с меньшим значением индекса k в выражении (2.11) имеют большие значения (см. рис. 2.5).

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

То есть, большая часть информации исходной матрицы 8х8 пикселов представляется первым элементом матрицы, преобразованной по способу ДКП.

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

Рис.2.5. Спектр ДКП отдельного фрагмента изображения Преобразованная матрица из 64 пикселов затем проходит операцию квантования, которая применяется для сокращения разрядности коэффициентов. Процесс квантования, который ведет к сжатию коэффициентов ДКП, выражается следующим образом [11]:

zkl=round(ykl/qkl)=(yklqkl/2 )/qkl, k,l=0,1,...,7, (2.16) где qkl - весовой множитель матрицы квантования Q размера 8х8 с номером kl (xобозначает наибольшее целое меньшее или равное x).

Иногда для формирования матрицы квантования может использоваться специальная весовая функция, позволяющая сформировать коэффициенты квантования, обращающие в 0 наибольшее число высоко и средне частотных коэффициентов. Согласно литературе [4,37], элементы матрицы Q линейно возрастают пропорционально сумме индексов элемента матрицы, например:

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

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

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

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

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

Далее обычно применяется метод однопроходного кодирования Хаффмана. Сначала анализируется вся последовательность символов. Часто повторяющимся сериям бит присваиваются короткие обозначения (маркеры).

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

Рис.2.6. Диагональное «зиг-заг» сканирование спектральных компонент Восстановление. При восстановлении изображений перечисленные выше шаги выполняются в обратном порядке. Декодирование начинается с восстановления из полученного битового потока закодированных неравномерным кодом длин серий нулей и значащих элементов матрицы Z.

Восстановление коэффициентов разложения Y^ по квантованным значениям Z выполняется по формуле Далее выполняется обратное ДКП:

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

Коэффициент архивации в JPEG может изменятся в пределах от 2 до раз (на практике коэффициент сжатия не превосходит 20-25) [4].

Как и любого другого алгоритма с потерями, у JPEG есть свои особенности. Наиболее известны "эффект Гиббса" и дробление изображения на квадраты 8х8. Первый проявляется около резких границ предметов, образуя своеобразный "ореол" [4]. Разбиение на квадраты происходит, когда задается слишком большой процент архивации для данной конкретной картинки.

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

2.1.4.3. Сжатие по методу WIC (Wavelet Image Compression) Под wavelet-преобразованием подразумевают множество базисных функций, которые формируют компактное описание видеосигнала. Анализ изображений, построенных на таких базисах, осуществляется по двум переменным - масштабу и сдвигу [2]. Это позволяет разделить крупные и мелкие детали изображений, одновременно локализуя их на временной шкале.

Таким образом, учитывается важное для практики обстоятельство:

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

Несомненное преимущество применения этого преобразования возможность представлять быстро изменяющиеся сигналы в компактной форме. Подобно широко используемому быстрому преобразованию Фурье (БПФ), wavelet-преобразование (DWT) обратимо и может служить инструментом анализа характеристик сигналов (спектральный анализ и др.). В отличие от БПФ (где базисными функциями служат синусы и косинусы) wavelet-преобразования формируют родительские функции более сложной формы. Их исходный набор обеспечивает получение бесконечного числа новых форм функций. Поскольку wavelet-функции ограничены в пространстве, с их помощью можно локализовать пространственный объект с высокой степенью точности [1].

Непрерывное вейвлет-преобразование одномерного сигнала определяется следующим образом [1]:

Результат преобразования - функция, зависящая от двух переменных: от координаты - x и масштаба - a. Используемая здесь функция w(x) является базисной. На каждом масштабе первоначальный базис w растягивается по горизонтали и сжимается по вертикали. Затем он сдвигается в точку x исследуемой функции и свертывается с ней. В литературе данный метод часто называют многомасштабным анализом [6].

Первоначальная функция f (t ) может быть восстановлена с помощью формулы:

где C - норма базисной функции w Восстановление сигнала возможно, если норма определена.

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

Простейший всплеск – функция, на основе которой строится базис Хаара [2]:

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

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

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

Так два числа a2i и a2i+1 можно представить в виде: b1i=( a2i+ a2i+1)/2 и b2i=(a2i - a2i+1)/2, аналогично последовательность ai может быть попарно переведена в последовательность b1,2i. Данное преобразование можно применять последовательно несколько раз к результатам предыдущего преобразования.

Для двух мерного случая (квадрата из 4-х точек с яркостями a2i,2j, a2i,2j+1, a2i+1,2j, a2i+1,2j+1) наипростейшим преобразованием может быть преобразование следующего вида:

Таким образом, используя данное преобразование, исходное изображение преобразуется в 4 субизображения, к каждому из которых, в принципе, данное преобразование можно применить повторно.

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

При выполнении двумерного вейвлет-анализа с использованием преобразования Хаара (выражение 2.21) для разложения изображения вначале выполняется разложение по строкам, а затем по столбцам. Результатом разложения являются 4 матрицы HH0, HL0, LH0, LL0, соответствующие фильтрации фильтром h1(n) по строкам и столбцам, фильтром h1(n) по строкам и фильтром h0(n) по столбцам, фильтром h0(n) по строкам и фильтром h1(n) по столбцам, и фильтром h0(n) по строкам и столбцам. Далее низкочастотная матрица LL0 подвергается вейвлет разложению. Его результатом являются матрицы HH1, HL1, LH1, LL1:. Такое разложение повторяется r раз, как показано на рис.2.8. Результатом разложения является набор из 3r+1 матриц уменьшающейся размерности. Каждая матрица подвергается скалярному или векторному квантованию и последующему кодированию. Выбор числа уровней квантования или шага квантования производится исходя из требуемого сжатия и соответствующего распределения битов между матрицами.

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

Низкочастотные матрицы непосредственно кодируются кодом Хаффмана.

При дискретном вейвлет-преобразовании (ДВП) анализируется сигнал с помощью блока анализа, направляющего входной сигнал x на два фильтра с импульсными откликами h (низкочастотный) и g (высокочастотный) соответственно. После прохождения фильтров сигналы прореживаются вдвое, т.е. сигнал, содержащий N элементов, преобразуется в N / 2 – элементные выходы двух каналов. Блок анализа осуществляет один уровень прямого вейвлет преобразования.

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

Удлиненные таким образом вдвое сигналы поступают на фильтры с импульсными откликами u и v, а затем складываются. Два канала, содержащие по N / 2 элементов каждый, объединяется в один сигнал, состоящий из N элементов. Блок синтеза осуществляет один уровень обратного вейвлет преобразования. Низкочастотный фильтр задает скейлинг-функцию (масштабирующую функцию), а высокочастотный фильтр определяет всплеск.

Результатом М-кратного пропускания коэффициентов фильтра u / v через верхний канал блока синтеза будет вейвлет или скейлинг-функция на масштабном уровне M. Схема такого процесса представлена на рис.1.9.

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

Например, для сжатия важно представить сигнал небольшим числом коэффициентов разложения [2,6].

Алгоритм быстрого пирамидального иерархического разложения сигнала в векторы данных половинной длины позволяет получить множество коэффициентов разложения (для разрешения 1/2, 1/4, 1/8 и т. д.) [4]. Cтепень сжатия при wavelet-преобразовании зависит от необходимого разрешения.

Сегодня у специалистов не вызывает сомнения, что эти алгоритмы кодирования обладают рядом преимуществ по сравнению с алгоритмами, построенными на основе дискретного косинусного преобразования Фурье, которое используется в кодеках JPEG, MPEG-1, MPEG-2 [4]. В частности, подобное разложение применяется в новых стандартах сжатия JPEG2000 и WIC [4,31,37,54].

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

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

Например, в изображении кроны дерева, фрактал - изображение листа.

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

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