Содержание к диссертации
Введение
ГЛАВА 1. Компьютерные методы сжатия цифровых изображений
1.1 Технология JPEG
1.2 Современные методики анализа цифровых изображений
1.3 Разложение Шмидта функции двух переменных
ГЛАВА 2. Задачи идентификации и полигармоническое разложение
2.1 Об инвариантах цифровых изображений в задачах идентификации
2.2 Выделение гармонической составляющей функции
2.3 Полигармоническое разложение
ГЛАВА 3. Алгоритм шмидта и сингулярный анализ
3.1 Метод максимизации столбцов матрицы, сингулярное разложение
3.2 Метод Шмидта (матричный метод, частный метод Шмидта)
3.3 Алгоритмы сглаживания
Заключение
Список использованной литературы
- Современные методики анализа цифровых изображений
- Разложение Шмидта функции двух переменных
- Выделение гармонической составляющей функции
- Метод Шмидта (матричный метод, частный метод Шмидта)
Введение к работе
Современный прогресс в развитии высоких технологий позволяет решать самые разнообразные задачи. В основном все они сводятся к реализации передачи, обмена, хранения, обработки и анализа различных классов цифровых данных. При этом необходимость увеличения объемов ресурсов стимулирует усовершенствование имеющихся и создание принципиально новых аппаратных и программных средств обработки цифрового массива, порождает новые требования к вопросам рационального использования технических возможностей вычислительных систем. Этим подтверждается актуальность проблемы хранения цифровых данных - при огромных потоках обрабатываемой информации, от грамотного и оптимального использования совокупного объема памяти ЭВМ зависит быстродействие программных продуктов, а значит, и производительность труда.
В поисках ответов на поставленные вопросы особого внимания требуют графические объекты, обрабатываемые вычислительными системами. Интерес к математическому анализу и алгоритмам компактного хранения изображений связан, во-первых, с удобством наглядности графической информации, и, во-вторых, с тем, что тексты и всевозможные программы для хранения и передачи по сетям требуют сравнительно небольших объемов памяти, тогда как оригинал изображения размером 640x480 может занимать почти 1 Мегабайт. Особую ценность представляет собою оптимизация цифровой обработки информации в системах охранного телевидения и видеонаблюдения, ставших востребованными в последнее время. Для режима реального времени типичное оцифрованное видео с высоким разрешением может потребовать 1312992 байт (=1282 Кбайт) для формирования одного полного телевизионного кадра без сжатия. Таким образом, для системы цветного телевидения PAL скорость передачи 25 кадров в секунду должна составлять приблизительно 250 Мбит/секунда
4 (аналогично и для NTSC) [22]. В реальности даже для современных стандартов такая скорость потока данных является очень высокой, а иногда и невозможной. Популярное сегодня использование сетевых видеосерверов, работающих по обычным компьютерным сетям Ethernet [37], накладывает определенные ограничения, которые сами по себе являются технически предельными.
Построение математического аппарата, отвечающего качественному решению прикладных задач цифровых технологий обработки информации, невозможно в рамках единственного выделенного научного направления. Так, сложившийся подход к проблемам оптимизации кодирования информации, в XX веке стал поводом для формирования не только отдельных научных теорий, но и целых наук, сформировав свои парадигмы. Как отметил Р.Е. Кричевский [32]: «...задача сжатия приобрела такую важность, что для рассмотрения различных ее вариантов возникла новая наука - теория информации...».
Весьма обширный спектр вопросов цифровой обработки изображений успешно разрешается в работах современных ученых. Существенный вклад в разработку методов и алгоритмов компрессии-декомпрессии внесли отечественные специалисты. В частности, труды в исследовании задачи о представлении функции двух переменных (И.В. Арнольд, Р.Д. Баглай, М.А. Кронрод, М.Р. Шара-Бура, Р.Е. Кричевский и других), послужили научной базой для многих современных математических методов. Особенно весомый вклад в отечественную науку внесла научная школа академика А.Н. Тихонова и ученых Московского государственного университета В.А. Морозова (решение двумерных интегральных уравнений типа свертки на плоскости с помехами в ядре и правой части уравнения, в частности, разработка проблемы восстановления смазанных и расфокусированных изображений), Ю. П. Пытьева (вопросы морфологического анализа цифровых изображений), В.В. Поспелова, А.В. Гончарского. Реализовав математические методы и собственные алгоритмы на базе вычислительных
5 лабораторий в сериях комплексных программных продуктов, они заложили не только технологическую базу, но и предоставили возможность использования своих результатов в учебном процессе. Труды отечественных ученых отвечают всем требованиям современности, а иногда и опережают технические возможности аппаратного обеспечения. Иностранные специалисты [например 56-58] предлагают свои весьма продуктивные алгоритмы, в основном ориентированные на современные параметры и производительность электронной и вычислительной техники.
Все известные современные методы сжатия ориентированы на удаление некоторой избыточности хранящейся информации. При этом под избыточностью обычно понимается частая повторяемость отдельных одинаковых участков информации или присвоение одинакового количества бит для кодировки всех элементов, независимо от того, как часто эти элементы могут быть использованы. При компрессии графических изображений в основном применяется устранение специфической избыточности, которая образуется за счет корреляции по цветности и яркости соседних пикселей.
Принципиально алгоритмы сжатия цифровой информации принято разделять на два типа: сжатие без потерь и сжатие с потерями информации.
В первом случае преобразование является обратимым и по сжатому образу информация может быть восстановлена с точностью до бита. Традиционно используются такие методы, как:
методы кодирования длин серий, например, RLE, когда последовательные элементы с одинаковым значением кодируются при помощи пары чисел, включающих длину серии и значение самих элементов;
факсимильное сжатие;
словарные методы, например LZW согласно этому алгоритму при сжатии данных ведется словарь, содержащий уже встречавшиеся последовательности значений элементов. Сжатый поток будет содержать коды, указывающие на элементы словаря [33].
Второй тип сжатия (с потерями) обычно используется при компрессии графической информации. Информация, не существенная при восприятии человеческим зрением, отбрасывается. Внешне картинка будет выглядеть как оригинал или несколько отличаться ухудшением качества изображения, но в целом такой результат может считаться вполне приемлемым. Такое сжатие обеспечит потребность в относительно небольшом объеме памяти для хранения информации. Но это преобразование всегда одностороннее, и по сжатому образу восстановить точную копию оригинального изображения не получится, - сжатая картинка будет скорее просто похожа на оригинал.
В данной работе исследуются алгоритмы компрессии, применяемые непосредственно к растровым изображениям, которые в цифровом виде обычно представляют собою двумерные массивы числовых данных, где каждый элемент является характеристикой отдельно взятого пиксела. При этом объем памяти, необходимый для хранения такой информации, фактически определяется цветовой насыщенностью картинки.
Для концептуального анализа основных принципов сжатия изображений, необходимо рассмотреть алгоритм их цифровой обработки. При этом определяется изначальная природа графического объекта, а затем способы хранения цифровой графики, исходя из формирования и передачи цвета при визуализации цифровых картинок. Часто компрессии предшествуют технологии предварительной цифровой обработки исходного графического оригинала.
В произвольном классе аналоговых изображений рассмотрим процесс дискретизации. В действии процедура дискретизации может быть описана как некая разовая обработка изображения, после которой графическому объекту сопоставится двумерный массив, элементами которого будут вещественные числа.
Следующей предваряющей процедурой цифровой обработки для оптимального использования возможностей оцифровывающих устройств [52, 54], и дальнейшей кодировки изображения, является квантование - это
7 процедура замены дискретного отсчета ближайшим значением из набора фиксированных величин (уровней квантования) [43, 45, 52, 55].
В общем случае данная операция может быть представлена как ступенчатая функция: если яркость х дискретного отсчета изображения заключена в числовом промежутке (tj, tj+\ ], то исходный отсчет заменяется
уровнем квантования kj. Квантованный сигнал принимает конечное число
значений (обычно из диапазона от 0 до 255), которые, как правило, совпадают по порядковому номеру с уровнем квантования [45].
Установлено, что человеческое зрение больше реагирует на изменение яркостного, нежели цветового тона в изображении [54], что объясняется функциональными особенностями зрения: глаз содержит особые нервные клетки, которые называются палочками (их количество преобладает) и колбочками - физиологический аппарат яркостного и цветового восприятия соответственно. Исходя из природы человеческого зрения и возможностей технических реализаций, появился ряд цветовых моделей, которые принципиально отличаются друг от друга способами формирования цветов при передаче изображений на устройства вывода информации. Далее рассмотрим наиболее популярные из них [10, 27].
RGB - в данной цветовой системе все цвета определяются как результат смешивания красной, зеленой и синей компонент. Данная модель представляет собою аддитивный синтез трех основных цветов и является аппаратно-зависимой, - цвета, которые реально могут быть получены, образуют «цветовой охват» устройства отображения. Недостатком в данном случае можно считать и тот факт, что не существует источников основных цветов, которые позволят получать все возможные цвета путем обозначенного выше способа смешения красного, зеленого и синего. В RGB для хранения картинки в электронном виде требуется 3 байта на каждый пиксел изображения только для того, чтобы сохранить информацию о цвете.
YCbCr - трехкомпонентное цветовое пространство: Y - компонента яркости, СЬ и Сг - компоненты, определяющие цветность. Значением СЬ
задается синева изображения, Сг - краснота. Такой подход к цветопередаче подобен цветовой модели, используемой в телевизионных приемниках. При этом Y сам по себе является полутоновым представлением цветного изображения.
В отличие от RGB, где все компоненты равнозначны, цветовая модель YCbCr концентрирует наиболее важную информацию в одном из компонентов, что позволяет добиться большего сжатия при компрессии изображения путем большего объема данных по компоненте яркости Y, чем по красноте и синеве.
Между цветовыми моделями RGB и YCbCr в компьютерном мониторе взаимосвязь выражается известными математическими уравнениями [25],
Y=0.299R+0.587G+0.114В
/~!t-_ А 1 f.QHTi (Л 'З'З 1 'З/^'ц.Л С OjO точность дискретизации/2
Cr=0.5R-0.4187G-0.0813B и, обратно,
R=Y+1.402Cr
pi_Y (Л 'T.AAlAfC^h О точность дискретизации/2\ А Н~\Д]Л((~*г О точность дискретизации/2\
т>_Л7'_1_1 Н^^Ґ(~^Y\ О точность дискретизации/2\
CMYK - является четырехкомпонентной цветовой моделью (Cyan, Magenta, Yellow, Black - голубой, пурпурный, желтый, черный), используемой чаще при цветной печати. В рассмотренных выше цветовых моделях компоненты добавляли цвет в изображение. Чем выше значение компоненты, тем ближе цвет к белому. Однако в CMYK большие значения компонент приближают цвет к черному. При равенстве значений С, М, и Y цвет представляет собой оттенок серого.
CMYK также может быть аппроксимирована через RGB, но представляет собой тот случай, когда между цветовыми пространствами не существует взаимнооднозначного соответствия - на одно и тоже значение RGB отображается множество значений CMYK.
При создании и хранении цифровых изображений современный пользователь может самостоятельно выбирать графические форматы, под которыми принято понимать определенные правила записи цифровых данных в файл. Графические форматы разрабатывались для того, чтобы эффективно организовывать, сохранять и восстанавливать графические данные. В основном, при работе с цифровыми картинками используют растровый, векторный или метафайловый форматы [28].
Растровые форматы рационально используются при хранении реальных изображений (видеоизображения, фотографии и т.п.) - они представляют собою «пиксельную карту изображения», по которой программа визуализации восстановит изображение на устройстве вывода информации.
Векторные форматы, в отличие от пиксельных, содержат математические описания элементов изображения, по которым программа визуализации реализует изображение. Хотя по своей структуре такой формат проще, чем большинство известных растровых, для реализации изображений в векторных форматах могут требоваться более обширные вычислительные ресурсы, и, соответственно, время.
Метафайловые форматы могут хранить как растровые, так и векторные данные.
Выбор формата обычно согласован с видом графики. Согласно [18, 19] по характерным отличительным чертам графическую информацию, обрабатываемую при помощи ЭВМ, можно условно классифицировать на:
1) изображения с небольшим количеством цветов (например, деловая
графика);
изображения с плавными переходами цветов, реализованные при помощи возможностей ЭВМ;
фотореалистичные изображения;
фотореалистичные изображения с наложением деловой графики (например, реклама) и т.д.
Становление различных графических форматов со временем стало сопровождаться внедренными алгоритмами компрессии. Сегодня большинство современных способов хранения изображений изначально содержат программные модули, позволяющие более компактно использовать ресурсы памяти ЭВМ при хранении цифровой графики [28, 52, 53].
Однако, не смотря на достижение существенных результатов в области цифровой обработки изображений, до сих пор не существует единственно универсального ответа на вопросы, касающиеся рационального использования ресурсов ЭВМ в совокупности с оптимальным быстродействием и максимальным сбережением качества информации. Принципиально же, основные направления подобных исследований фактически представляют собою либо одно из обозначенных ниже, либо их синтез.
1) Относительно новой можно назвать методику, когда решается
задача о выборе наиболее оптимального способа кодирования для
конкретного изображения. Данный подход обычно сопровождается
созданием и использованием соответствующих программных средств. При
решении подобных задач, например, можно выделять некоторые
«особенности» сжимаемых изображений, и с учетом такой информации
строить модель оценки максимально возможного коэффициента сжатия для
различных методов компрессии [31].
Используя алгоритмы анализа типа изображений, можно добиться оптимизации сжатия не более чем на 10 %. Для интерактивного режима работы в вычислительной сети такая оптимизация может быть вполне удовлетворительной, однако приведенный подход в основном реализуется за счет имеющихся алгоритмов сжатия, и, скорее направлен на обновление собственных версий, нежели реализацию новых алгоритмов компрессии.
2) Создание новых и совершенствование имеющихся алгоритмов
сжатия постоянно стимулирует интерес к проблеме установления
особенностей алгоритмов компрессии. На сегодняшний день уже выделяются
11 лидеры в данной области, применимость которых была внедрена и усовершенствуется уже не только алгоритмически, но и на технологическом уровне производства.
В данном диссертационном исследовании рассматривается один из наиболее популярных методов JPEG, востребованность которого на протяжении многих лет остается достаточно высокой.
Другой, не менее важной особенностью наглядной информации, является ее более простой анализ (в смысле количественных или качественных характеристик), сравнение и идентификация. Вопрос о принадлежности данного объекта к отдельному описанному классу представляет собою сущность отдельного подхода при работе с графическими изображениями, который в общем можно назвать теорией распознавания образов [4].
Существенный вклад в этой области внесли советские и российские ученые. В 40-х годах А.Н. Колмогоровым и А.Я. Хинчиным поставлена задача о разделении смеси двух распределений. Как отмечает Л.А. Белозерский [4]: «Наиболее плодотворными явились 50- 60-е годы XX века. В это время на основе массы работ появилась теория статистических решений. В результате этого появления найдены алгоритмы, обеспечивающие отнесение нового объекта к одному из заданных классов, что явилось началом планомерного научного поиска и практических разработок. В рамках кибернетики начало формироваться новое научное направление, связанное с разработкой теоретических основ и практической реализации устройств, а затем и систем, предназначенных для распознавания объектов, явлений, процессов».
Благодаря таким специалистам, как Ю.П. Пытьев, А.Н. Чуличков, российской науке стали доступны методы математической морфологии. Морфологический анализ изображений является мощным и принципиально важным подходом к вопросам выделения изменений в фиксированных сценах, за счет специальных алгоритмов построения форм и их анализа [46,
12 47]. Достижения в области распознавания образов уже довольно продолжительное время используются в медицине, деятельности правоохранительных органов, при дешифровании космических снимков, в большинстве промышленных сфер.
Таким образом, с началом применения достижений цифровых технологий в современном мире, вопросы распознавания и идентификации графических изображений стали важнейшими для большинства систем мониторинга. Это необходимо привело к тому положению, когда задача о визуализации информации, ее обработке, транспортировке через вычислительные сети и анализе стала одной из центральных среди всего разнообразия поставленных задач компактного и рационального хранения цифровой информации. Цифровые технологии сегодня занимают одно из привилегированных мест среди основных задач, с которыми приходится иметь дело современным специалистам практически во всех сферах деятельности. Глобальное внедрение вычислительной и компьютерной техники в системы диагностики, слежения и контроля напрямую связано с развитием высоких технологий в области цифровой обработки информации, чем объясняется неугасающий интерес к вопросам описания все более оптимальных методов компрессии медиаданных, значительную часть которых представляют отдельные классы цифровых изображений.
В данной диссертационной работе рассматриваются некоторые математические алгоритмы идентификации и алгоритмы сжатия изображений, предлагаются новые пути разрешения проблемы компрессии и анализа цифровых полутоновых изображений класса фото-анфас.
Алгоритмы сжатия-восстановления, рассматриваемые в диссертации, опираются на использование известного метода Шмидта разложения функции двух переменных, а так же метода сингулярного разложения матриц. В численных экспериментах для различных полутоновых черно-белых изображениях получен коэффициент сжатия, сравнимый с коэффициентом, который дает стандартная технология JPEG.
Решение задачи идентификации требует построения такой операции, которая разным функциям-прообразам ставит в соответствие разные образы, и объем информации для образов существенно меньше объема информации для прообразов, при этом такое соответствие должно быть взаимнооднозначным (по крайней мере для некоторых основных составляющих, основных проекций функций-прообразов и их образов).
Первая глава имеет общий характер. В разделе 1.1 кратко изложен традиционный алгоритм JPEG. Именно JPEG излагается почти во всех учебных и монографических изданиях, посвященных проблемам компрессии и декомпрессии цифровых изображений. Основным элементом его является дискретное косинус-преобразование Фурье (ДКП). Этот математический алгоритм дает основной эффект сжатия, достигаемый данной технологией. Большое число работ посвящено модификации и ускорению его основной составляющей - алгоритму ДКП.
Широко ведется разработка принципиально новых математических и компьютерных методов и алгоритмов для решения задачи сжатия-восстановления .
Одним из новых перспективных направлений в исследовании проблем сжатия и восстановления цифровых изображений, является морфологический анализ [46, 47]. Его некоторые аспекты приводятся в разделе 1.2. Также излагаются основы фрактального анализа [56, 58], как одного из новейших методов сжатия-восстановления.
В разделе 1.3 приведено изложение метода Шмидта разложения функции f(x,y\
f{x,y)eL2{Q), {x,y)eQ = {0,\)x{0,\).
Это разложение имеет вид [7, 11, 15, 16, 42]
f(x>y)= Т.лкак(х)ьк(у)+Рп+\(х>у)>
к=\
14 где функция Рп+1\Х'У) стремится к нулю при и—»о. Функции ак{х)
определяются как собственные функции для главного собственного числа Я^
* интегральных операторов А^ А^, где
1 п-\
^ки(х)=!/к(х'УИУ^У' fk(x>y) = f(x>y)- ЦЛтат(х)Ьт(у).
О т=\
ЕслиДх,_у), ак(х), Ъ^(у) - дискретные функции с растром h = M~ по х и по у, то коэффициент сжатия Я равен
Решение спектральной задачи является сложной компьютерной процедурой, использующей итерационные алгоритмы, что требует сравнительно большого времени. В диссертационной работе для этого используется новый метод решения алгебраической спектральной задачи, разработанный в последние годы - метод максимизации столбцов [9, 35]. Доказывается оценка погрешности рп+\ (х, у).
Главы 2 и 3 являются основными.
Важнейшим этапом анализа определенных классов изображений является исследование их инвариантов относительно некоторых преобразований для рассматриваемого класса изображений.
В разделе 2.1 главы 2 приводятся некоторые инварианты изображений, сохраняющиеся при сдвигах, поворотах и растяжениях. Для разных классов изображений могут быть различные инварианты. В общем случае к таковым можно отнести центр тяжести и главную ось инерции [14]. Приведение их в стандартное положение очень полезно для решения практических задач идентификации. Для класса изображений фото-анфас к инвариантам может быть также отнесен главный треугольник - равнобедренный треугольник, вершины которого находятся в глазах и в центре рта [20]. Здесь же, в 2.1 описаны алгоритмы определения перечисленных выше инвариантов.
Современные методики анализа цифровых изображений
По принципам реализации современные методы сжатия определяются как неадаптивные, адаптивные, и полуадаптивные [48].
Метод неадаптивного сжатия - принцип действия алгоритма сжатия исключает возможность изменять параметры своей работы в зависимости от входных данных. Алгоритмы данного метода качественно сжимают однотипные данные.
Метод адаптивного сжатия. Работа по сжатию осуществляется в два этапа. Сначала тестируются исходные данные, затем, в зависимости от результатов проверки, происходит подстраивание параметров исполнения алгоритма.
Метод полуадаптивного сжатия определяет исполнение алгоритмов компрессии как двухпроходных. На первом проходе по файлу аккумулируется статистика по сжимаемым входным данным; на втором прохождении исполняется сжатие с учетом полученной ранее информации.
Как было отмечено ранее, цифровая графика в непосредственном первоначальном виде может занимать большие объемы памяти. Обычное применение алгоритмов компрессии к графическим изображениям (особенно имеющим аналоговую природу) предварительно сопровождается несколькими предваряющими этапами цифровой обработки входящего сигнала [43, 54]. При этом качественной характеристикой результата компрессии является коэффициент сжатия, под которым принято понимать меру продуктивности конкретного алгоритма сжатия. Определим коэффициент сжатия К как отношение размера файла, полученного на выходе после применения сжатия, к размеру исходного «несжатого» файла к = , V у 2 здесь V\,V2 объемы памяти, необходимые для хранения соответственно выходного и исходного файлов.
Отсутствие компрессии будет очевидным при К = 1. Значения К, превосходящие единицу, свидетельствуют об ошибочном применении данного алгоритма к конкретному изображению - произойдет расширение. В некоторых случаях, помимо коэффициента сжатия, может быть определена обратная величина - фактор сжатия, которая представляет собою отношение размера исходного файла к размеру файла, полученного на выходе после применения процесса компрессии.
В ряде случаев изображения, обрабатываемые при помощи современных вычислительных систем, изначально представлены аналоговыми источниками. Их преобразование к цифровому виду является обязательным для дальнейшей возможности их обработки, хранения и передачи по вычислительным сетям. Таким образом, первичный аналоговый рисунок при оцифровке, необходимо подвергается дискретизации и квантованию, после чего к нему могут быть применены компьютерные программы анализа, компрессии-декомпрессии.
Дискретное cos-преобразование Фурье
В основе эффективного кодирования сигнала при оцифровке изображения заложен приведенный выше принцип устранения избыточности. В теории колебаний информационное содержание сигнала анализируется легче, если исходный сигнал можно разложить на частотные составляющие [53], что в определенном смысле можно рассматривать как процедуру анализа входящей информации. В данном случае устранение избыточности будет рассмотрено как отделение существенных информационных характеристик от менее значимых составляющих в смысле восстановления изображения. Благодаря удалению несущественной информации из сигнала, упрощается запоминание и уменьшается требуемый объем памяти. Приведенный подход составляет основу одного из важнейших в настоящее время методов сжатия растровых изображений - дискретного косинусного преобразования (ДКП), лежащего в основе таких стандартов сжатия, как JPEG и М-JPEG.
ДКП представляет собою обратимое отображение массива вещественных данных (в JPEG операция проводится над уже квантованными числовыми данными) в массив той же размерности, элементами которого будут коэффициенты косинусных функций с возрастающими частотами. Обычно для сжатия графики реализуется двумерное ДКП, которое в матричной форме может быть представлено следующим образом:
Вп =КПхВхКПт. В этом выражении В означает блок изображения, как правило, размером 8x8 элементов; Вп - блок после дискретного косинусного преобразования; КП - матрица косинусного преобразования; КП - соответствующая транспонированная матрица. Значения матрицы преобразования КП в классическом ДКП вычисляются с помощью выражения KITjj = —;=, если / = О 3 JN КПу = JyN cos[(lj +1)/ 2N], если і 0. В нашем случае N = 8, a / nj принимают значения от 0 до 7.
Разложение Шмидта функции двух переменных
Вместе с огромными темпами развития всей индустрии информационных технологий эволюционируют и ее составляющие. Так, хорошие перспективы прогнозируют новому стандарту сжатия JPEG-2000. Его основное отличие от классического JPEG заключается в том, что вместо ДКП при сжатии используется WAVELET-метод.
Сам термин "WAVELET" (метод элементарных волн или МЭВ-метод) появился сравнительно недавно; его ввели в середине 80-х годов в связи с анализом свойств сейсмических и акустических сигналов. В настоящее время семейство анализаторов, названных вейвлетами, начинает широко применятся при анализе изображений самой различной природы, в задачах распознавания образов, при обработке и синтезе различных сигналов, например, речевых, для изучения свойств турбулентных полей, для свертки (упаковки) больших объемов информации и во многих других случаях [1, 38, 57].
МЭВ-преобразование одномерного сигнала состоит в его разложении по базису, сконструированному из обладающей определенными свойствами солитоноподобной функции (волны) посредством масштабных изменений и переносов. Каждая из функций этого базиса характеризует как определенную пространственную (или временную) частоту, так и ее локализацию в физическом пространстве (или времени) [1, 38].
Таким образом, в отличие от традиционно применяемого для анализа сигналов преобразования Фурье, МЭВ-преобразование обеспечивает двумерную развертку исследуемого одномерного сигнала, при этом частота и координата рассматриваются как независимые переменные. Это дает возможность анализировать свойства сигнала одновременно в физическом (время, координата) и в частотном пространствах. Все эти суждения обобщаются на не одномерные сигналы или функции.
Большинство ограничений, накладываемых на вейвлет, связано с необходимостью иметь обратное преобразование. Выбор анализирующего вейвлета, как правило, определяется тем, какую информацию необходимо извлечь из сигнала. Каждый вейвлет имеет характерные особенности во временном и в частотном пространстве, поэтому иногда с помощью разных веивлетов можно полнее выявить и подчеркнуть те или иные свойства анализируемого сигнала.
Часто МЭВ-анализ называют "математическим микроскопом", имея в виду замечательное свойство метода, сохранять хорошее разрешение на разных масштабах. Данное свойство успешно используется в современных пакетах прикладных программ обработки изображений.
Одномерное преобразование Фурье дает также одномерную информацию об относительном вкладе (амплитудах) разных временных масштабов (частот). Результатом МЭВ-преобразования одномерного ряда является двумерный массив амплитуд МЭВ-преобразования. Распределение этих значений в пространстве дает информацию об эволюции относительного вклада компонент разного масштаба во времени и называется спектром коэффициентов МЭВ-преобразования, масштабно-временным спектром или МЭВ-спектром (time-scale spectram или wavelet spectrum в отличие от single spectram преобразования Фурье).
Если сравнить высокую степень компрессии при ДКП и WAVELET-методе, то, в первом случае, артефактом будет явная блочная структура изображения, во втором - вид ряби вблизи резких границ.
WAVELET-метод нашел широкое применение в цифровых системах видеонаблюдения, разрабатываются альтернативы существующим алгоритмам сжатия [22].
Фракталы - как альтернатива компрессии битовых матриц - изображений
В конце восьмидесятых годов Майклом Барнсли был описан метод, представляющий собой альтернативу методам сжатия изображений в виде битовых матриц. Само понятие фракталов и фрактальных множеств было введено Мандельбротом - им было предложено получать сложные изображения путем реализации простых алгоритмов. Одним из важнейших моментов данного подхода является то, что изображение в виде битовой матрицы может генерироваться с помощью нескольких формул [58]. Поэтому здесь можно говорить о некоторого рода аналогии между векторным изображением и изображением в виде битовой матрицы, с одной стоны, и фрактальным изображением и изображением в виде битовой матрицы - с другой. К примеру, пусть имеется черный прямоугольник на белом фоне размером 800x600 при глубине цвета 24 бит. Для записи такого изображения потребуется памяти 800x600x3 или, приблизительно, 1,3 Мегабайта. Если же записать только координаты прямоугольника вместе с толщиной линии и указанием цвета, потребуется всего несколько байт. По сути, в этом и состоит принцип фрактального сжатия. С помощью определенного алгоритма в изображении в виде битовой матрицы отыскиваются структуры, которые могут быть компактно записаны в виде математических выражений, то есть речь идет о нахождении подобия. Математический метод, используемый при фрактальном сжатии, совершенно иной, но результаты получаются сравнимыми.
Вместе с тем, данный метод не нашел широкого применения, даже не смотря на то, что основанная Майклом Барнсли фирма Inrected Systems за несколько лет довела фрактальный метод до реализации и предложила к продаже библиотеку функций, которые могут применяться для сжатия и восстановления изображений. Причина этого очевидна. Основным недостатком фрактального алгоритма является потребность в значительных вычислительных ресурсах при осуществлении компрессии изображения, в то время как разархивация происходит очень быстро. Большие ресурсы требуются для того, чтобы подобрать для каждого блока, на которые разбивается изображение, максимально подобный ему (с точностью до аффинного преобразования). Если изображение в виде битовой матрицы сжимается методом JPEG за время в пределах секунды, то для фрактального сжатия в лучшем случае требуется несколько минут. Хотя полученное изображение часто более высокого качества, огромные временные затраты оправдывают сжатие лишь в исключительных случаях. Таким исключением является мультимедиа продукт высокого качества, в котором содержится много изображений.
Выделение гармонической составляющей функции
После получения предельной матрицы можно поступать к процедуре квантования. Идея, лежащая в основе такого квантования, состоит в том, что информация должна превышать известный порог, чтобы составить важную часть всей информации о рассматриваемом фрагменте изображения. Установка границы задает качество изображения. Если выбрать порог относительно высоко, потеряется большая часть информации. Это позволит хорошо сжать видеоданные, естественно, ценой ухудшения качества, которое станет заметным на изображении после восстановления видеоинформации. Именно на этапе квантования происходит потеря качества изображения, ценой которых и достигается сжатие видеоданных. Для выполнения квантования строят матрицу делителей, на которые нужно будет поделить значения в частотной матрице. Алгоритм нахождения делителей можно выбрать в следующем простом виде for (і = 0; і п; і++) for j = 0;j n;j++) делитель [/][/] = 1 + ((1 + і +7) качество);
Путем выбора значения "качество" можно управлять величинами делителей и тем самым регулировать степень сжатия. После нахождения делителей их надо использовать для деления значений преобразованной матрицы. В результате получится матрица с большим количеством нулей. Эти значения можно экономично запомнить, применяя, например, кодирование по Хаффману или другие схемы кодирования целых чисел переменной длины вместе с кодированием длин серий для последовательности нулей. Для этих целей вначале изменяется порядок обхода квантованных элементов спектральной матрицы, чтобы получить как можно более длинные последовательности нулей; обычно применяется зигзагообразная форма обхода
Более «гладкое» изображение может быть подвергнуто более сильному сжатию при использовании обычных технологий сжатия. Далее рассмотрим предварительное сглаживание для технологии JPEG и технологии Шмидта.
Функцию-изображение f{x), xeQ R разложим на гармоническое и ортогональное слагаемые f(x)=g(x)+h(x), где g(x)er(Q),glh. Функция h{x)e N\Q) содержит все разрывы и особенности f\x). Вместо непосредственного сжатия этой функции произведем предварительно ее сглаживание, такое, что процедура сглаживания может быть обращена и операция обращения является достаточно простой.
Рассмотрим в области Q краевую задачу для уравнения Пуассона Ли(х) = h(x), х є Q (3.13) U(X)=0,XGS (3.14) Так как hyxjeNyQ), то по свойству 3) имеем: u{x)=\h(y)E{x-y)dy (3.15) Q
Обозначим через и \х) функцию, полученную в результате применения некоторой технологии сжатия. Обратным оператором для операции (3.15) является оператор Лапласа. По технологии Шмидта N к=\ Дискретные функции а \хх )и й {х2) могут быть эффективно высокоточно сглажены до включения в пространство С [a, b], и норма в С [ОД] погрешности будет мала. Обозначим полученные таким образом функции через а {хх) и Ък {х2), N _ и{хх ,x2)=Y.h k (х\ )Ък (х2 ) к=\ По построению получаем N Аи{хх,х2) Y,hak (x\)bk ( г)-к=\ Аналогично получим окончательно по модифицированной технологии Шмидта N f{xx,X2) g{xl,x2)+Y,hak (x\)bk fe) k=l
По технологии JPEG функция її{х) - ступенчатая функция-матрица. При высокочастотном представлении изображения растр h достаточно мал (h «10 ,т = 2.5;3). В данном случае в качестве обратной операции сглаживания может быть непосредственно применен дискретный оператор Лапласа Л, где Awkn = [Щ-\,п + Щ+1,п + Щ,п-\ + Щ,п+1 - 4wk,nl /г так как его погрешность (на достаточно гладких априорно функциях) имеет вид o[h2).
Метод Шмидта (матричный метод, частный метод Шмидта)
Последнее слагаемое рт может быть отброшено (без потери для визуализации), следовательно т . ( . \г f(x,y)=Fl(x,y) Y.b[ ul[vlf І-л N /=1 2/77 И коэффициент сжатия К равен К = —.
Используя метод Шмидта можно сжимать цифровые изображения, т.к. растровое изображение по сути есть прямоугольная матрица с целочисленными элементами - характеризующие интенсивность белого цвета пикселя (рассматриваемые изображения считаются черно-белыми). При этом в ряде ( ) отбрасывается остаток, который вносит малый относительный вклад в изображение. N ( ) 7=1
Но само по себе приведенное разложение не обеспечивает большую степень сжатия у (отношение размера исходного файла к сжатому), т.к. в матрице А элементы целочисленные и для распространенных форматов файлов изображений они занимает в 8 раз меньше места, чем вещественные числа в правой части рассматриваемого разложения. Т.е. N получается слишком маленьким при = 1.1 —1.3 — чтобы обеспечить хорошее качество восстановленного изображения.
В связи с изложенным выше, метод Шмидта используется вместе с процедурами квантования и префиксного кодирования Хаффмана. Рассмотрим процедуру квантования. Опыт показывает, что коэффициент Q на первых 3-6 итерациях алгоритма метода Шмидта быстро уменьшается и выполняется соотношение Q 10000при / 6. Это позволяет компоненты векторов иги Vj брать с точностью до 0.001 при / 6, что увеличивает у примерно в 8 раз. Изучая распределение уже квантованных значений компонент векторов UjH Vj по значениям легко заметить, что частоты соответствующие малым по модулю значениям очень велики, что делает возможным сжатие с использованием метода Хаффмана. Это позволяет увеличить ;кещё в 1.8-2.5 раза.
Приведённые результаты экспериментов по сжатию изображений доказывают состоятельность предлагаемого подхода к решению проблемы компрессии цифровых изображений.
Заключение к главе 3.
Решение спектральной задачи является сложной математической процедурой, требующей больших ресурсов памяти ЭВМ и времени исполнения. Для оптимизации решения задачи спектрального разложения интегрального оператора в главе 3 предлагается новый метод ортогональных преобразований - метод максимизации столбцов (МС - метод).
МС - метод применяется для получения SVD-представления исходной матрицы-изображения. В ходе численных экспериментов было установлено, что сингулярные числа для матриц-изображений полутоновых фото-анфас резко убывают почти с экспоненциальной скоростью. Первые несколько десятков главных сингулярных чисел зачастую содержат более 90 % всего информационного веса. Данный факт был положен в основу SVD-фильтрации, в результате которой отбрасываются все младшие сингулярные числа матрицы, представляющие незначительный вклад в изображении. Эффект сжатия в результате SVD-фильтрации для рассматриваемого класса изображений сравним с результатом работы известной технологии JPEG. Так, если изображение в растровом представлении является матрицей размера (MxN), то первый коэффициент сжатия \ (без кодирования методом Хаффмана, по к восстановленным старшим сингулярным числам) будет равен
Похожие диссертации на Математические алгоритмы анализа цифровых изображений
