Математические алгоритмы анализа цифровых изображений тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Василенко, Вера Викторовна

• Василенко, Вера Викторовна
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Василенко, Вера Викторовна

ВВЕДЕНИЕ

ГЛАВА 1. КОМПЬЮТЕРНЫЕ МЕТОДЫ СЖАТИЯ ЦИФРОВЫХ ИЗОБРАЖЕНИЙ

1.1 Технология JPEG

1.2 Современные методики анализа цифровых изображений

1.3 Разложение Шмидта функции двух переменных

ГЛАВА 2. ЗАДАЧИ ИДЕНТИФИКАЦИИ И ПОЛИГАРМОНИЧЕСКОЕ РАЗЛОЖЕНИЕ

2.1 Выделение гармонической составляющей функции

2.2 Об инвариантах цифровых изображений в задачах идентификации

2.3 Полигармоническое разложение

ГЛАВА 3. АЛГОРИТМ ШМИДТА И СИНГУЛЯРНЫЙ АНАЛИЗ

3.1 Метод максимизации столбцов матрицы, сингулярное разложение

3.2 Метод Шмидта (матричный метод, частный метод Шмидта)

3.3 Алгоритмы сглаживания 83 ЗАКЛЮЧЕНИЕ 90 СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 91 ПРИЛОЖЕНИЕ

Введение диссертации (часть автореферата) на тему «Математические алгоритмы анализа цифровых изображений»

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

В поисках ответов на поставленные вопросы особого внимания требуют графические объекты, обрабатываемые вычислительными системами. Интерес к математическому анализу и алгоритмам компактного хранения изображений связан, во-первых, с удобством наглядности графической информации, и, во-вторых, с тем, что тексты и всевозможные программы для хранения и передачи по сетям требуют сравнительно небольших объемов памяти, тогда как оригинал изображения размером 640x480 может занимать почти 1 Мегабайт. Особую ценность представляет собою оптимизация цифровой обработки информации в системах охранного телевидения и видеонаблюдения, ставших востребованными в последнее время. Для режима реального времени типичное оцифрованное видео с высоким разрешением может потребовать 1312992 байт (=1282 Кбайт) для формирования одного полного телевизионного кадра без сжатия. Таким образом, для системы цветного телевидения PAL скорость передачи 25 кадров в секунду должна составлять приблизительно 250 Мбит/секунда (аналогично и для NTSC) [22]. В реальности даже для современных стандартов такая скорость потока данных является очень высокой, а иногда и невозможной. Популярное сегодня использование сетевых видеосерверов, работающих по обычным компьютерным сетям Ethernet [37], накладывает определенные ограничения, которые сами по себе являются технически предельными.

Построение математического аппарата, отвечающего качественному решению прикладных задач цифровых технологий обработки информации, невозможно в рамках единственного выделенного научного направления. Так, сложившийся подход к проблемам оптимизации кодирования информации, в XX веке стал поводом для формирования не только отдельных научных теорий, но и целых наук, сформировав свои парадигмы. Как отметил Р.Е. Кричевский [32]: «.задача сжатия приобрела такую важность, что для рассмотрения различных ее вариантов возникла новая наука - теория информации.».

Весьма обширный спектр вопросов цифровой обработки изображений успешно разрешается в работах современных ученых. Существенный вклад в разработку методов и алгоритмов компрессии-декомпрессии внесли отечественные специалисты. В частности, труды в исследовании задачи о представлении функции двух переменных (И.В. Арнольд, Р.Д. Баглай, М.А. Кронрод, М.Р. Шара-Бура, Р.Е. Кричевский и других), послужили научной базой для многих современных математических методов. Особенно весомый вклад в отечественную науку внесла научная школа академика А.Н. Тихонова и ученых Московского государственного университета В.А. Морозова (решение двумерных интегральных уравнений типа свертки на плоскости с помехами в ядре и правой части уравнения, в частности, разработка проблемы восстановления смазанных и расфокусированных изображений), Ю. П. Пытьева (вопросы морфологического анализа цифровых изображений), В.В. Поспелова, А.В. Гончарского. Реализовав математические методы и собственные алгоритмы на базе вычислительных лабораторий в сериях комплексных программных продуктов, они заложили не только технологическую базу, но и предоставили возможность использования своих результатов в учебном процессе. Труды отечественных ученых отвечают всем требованиям современности, а иногда и опережают технические возможности аппаратного обеспечения. Иностранные специалисты [например 56-58] предлагают свои весьма продуктивные алгоритмы, в основном ориентированные на современные параметры и производительность электронной и вычислительной техники.

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

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

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

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

- факсимильное сжатие;

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

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

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

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

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

Следующей предваряющей процедурой цифровой обработки для оптимального использования возможностей оцифровывающих устройств [52, 54], и дальнейшей кодировки изображения, является квантование - это процедура замены дискретного отсчета ближайшим значением из набора фиксированных величин (уровней квантования) [43, 45, 52, 55].

В общем случае данная операция может быть представлена как ступенчатая функция: если яркость л: дискретного отсчета изображения заключена в числовом промежутке (tj,ti+то исходный отсчет заменяется уровнем квантования ку. Квантованный сигнал принимает конечное число значений обычно из диапазона от 0 до 255), которые, как правило, совпадают по порядковому номеру с уровнем квантования [45].

Установлено, что человеческое зрение больше реагирует на изменение яркостного, нежели цветового тона в изображении [54], что объясняется функциональными особенностями зрения: глаз содержит особые нервные клетки, которые называются палочками (их количество преобладает) и колбочками - физиологический аппарат яркостного и цветового восприятия соответственно. Исходя из природы человеческого зрения и возможностей технических реализаций, появился ряд цветовых моделей, которые принципиально отличаются друг от друга способами формирования цветов при передаче изображений на устройства вывода информации. Далее рассмотрим наиболее популярные из них [10, 27].

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

YCbCr - трехкомпонентное цветовое пространство: Y - компонента яркости, СЬ и Сг - компоненты, определяющие цветность. Значением СЬ задается синева изображения, Сг - краснота. Такой подход к цветопередаче подобен цветовой модели, используемой в телевизионных приемниках. При этом Y сам по себе является полутоновым представлением цветного изображения.

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

Между цветовыми моделями RGB и YCbCr в компьютерном мониторе взаимосвязь выражается известными математическими уравнениями [27],

Y=0.299R+0.587G+0.114В Cb=-0.l687R-0.33l3G+0.5B+2mo4"ocmbduCKpem"m""/2 Cr=0.5R-0.4187G-0.0813B и, обратно,

R=Y+1.402Cr

Qy q 34414(СЬ 2 точ',ость дискретизации/2^ q у J 14(Cl" 2 точность дискретизации/2^ jj=y+ J 722(СЬ 2 точность дискретизации/2^

CMYK - является четырехкомпонентной цветовой моделью (Cyan, Magenta, Yellow, Black - голубой, пурпурный, желтый, черный), используемой чаще при цветной печати. В рассмотренных выше цветовых моделях компоненты добавляли цвет в изображение. Чем выше значение компоненты, тем ближе цвет к белому. Однако в CMYK большие значения компонент приближают цвет к черному. При равенстве значений С, М, и Y цвет представляет собой оттенок серого.

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

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

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

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

Метафайловые форматы могут хранить как растровые, так и векторные данные.

Выбор формата обычно согласован с видом графики. Согласно [18, 19] по характерным отличительным чертам графическую информацию, обрабатываемую при помощи ЭВМ, можно условно классифицировать на:

1) изображения с небольшим количеством цветов (например, деловая графика);

2) изображения с плавными переходами цветов, реализованные при помощи возможностей ЭВМ;

3) фотореалистичные изображения;

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

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

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

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

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

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

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

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

Существенный вклад в этой области внесли советские и российские ученые. В 40-х годах А.Н. Колмогоровым и А.Я. Хинчиным поставлена задача о разделении смеси двух распределений. Как отмечает JT.A. Белозерский [4]: «Наиболее плодотворными явились 50- 60-е годы XX века. В это время на основе массы работ появилась теория статистических решений. В результате этого появления найдены алгоритмы, обеспечивающие отнесение нового объекта к одному из заданных классов, что явилось началом планомерного научного поиска и практических разработок. В рамках кибернетики начало формироваться новое научное направление, связанное с разработкой теоретических основ и практической реализации устройств, а затем и систем, предназначенных для распознавания объектов, явлений, процессов».

Благодаря таким специалистам, как Ю.П. Пытьев, А.И. Чуличков, российской науке стали доступны методы математической морфологии. Морфологический анализ изображений является мощным и принципиально важным подходом к вопросам выделения изменений в фиксированных сценах, за счет специальных алгоритмов построения форм и их анализа [46, 47]. Подобные разработки и достижения в области распознавания образов уже довольно продолжительное время используются в медицине, деятельности правоохранительных органов, при дешифровании космических снимков, в большинстве промышленных сфер.

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

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

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

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

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

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

Одним из новых перспективных направлений в исследовании проблем сжатия и восстановления цифровых изображений, является морфологический анализ [46, 47]. Его некоторые аспекты приводятся в разделе 1.2. Также излагаются основы фрактального анализа [56, 58], как одного из новейших методов сжатия-восстановления.

В разделе 1.3 приведено изложение метода Шмидта разложения функции/^), f{x, у) е L2 (Q), (х, y)eQ = (ОД) х (0;l).

Это разложение имеет вид [7, 11, 15, 16, 42] N f(x> У) = ,Lh<*k(x)bk(y)+PN(x>y)> к=1 где функция р^{х,у) стремится к нулю при N оо. Функции ак(х) определяются как собственные функции для главного собственного числа Я^ инте* гральных операторов А^ А^, где

1 к ^ки(х) = \fk (х>y\(y)dy, /к(х>У) = f(x>У)~ Е Ajaj(x)bj(у). О У=1

Если j[x,y), b^iy) - дискретные функции с растром h-M~l пох и по у, то коэффициент сжатия Я равен

2 N

Решение спектральной задачи является сложной компьютерной процедурой, использующей итерационные алгоритмы, что требует сравнительно большого времени. В диссертационной работе для этого используется новый метод решения алгебраической спектральной задачи, разработанный в последние годы - метод максимизации столбцов [9, 35]. Доказывается оценка погрешности р^{х,у).

Главы 2 и 3 являются основными.

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

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

Раздел 2.2 посвящен первой из рассматриваемых задач анализа изображений - разложению функции-изображения на гармоническую составляющую и ортогональную к ней часть [34, 44]. Вначале приводится доказательство леммы Новикова о разложении пространства (Q) в прямую сумму

L2(Q) = r(Q)®N(Q), здесь r(Q) - подпространство гармонических в Q функций, а функция h(x) принадлежит N(Q) тогда и только тогда, когда h{y)ln\x - y\dy = 0, х = (xj, х^ Q+. Q

Далее доказывается лемма о полной в r(Q) системе функций: если ут(х) = Е\{т -х) xeQ, т-1,2,., где zm = [z™,z™) - базисная система точек в Q+ = Я2 1Q, то система функций {;ут{х)линейно независима и полна в Г (Q).

Аппроксимация gN {х) функции g{x)&r{Q), N g (*)= Y.cmrm{x), т=1 может быть определена как решение задачи минимизации функции F(c), c = (clt.,cN),

N I2

N m=\

Ll(Q)

Необходимое условие экстремума dF дср 0, p = \, 2,.,N приводит к невырожденной алгебраической системе с матрицей Грама. Указанный алгоритм используется далее для выделения гармонической составляющей.

В конце раздела 2.2 рассматриваются свойства решений уравнения Пуассона [6, 21, 40, 41]

Au{x) = v{x\ xeQ, где и{х) или v(x) принадлежит подпространству N(Q), а также решения соответствующих краевых задач. Эти свойства используются далее при построении алгоритмов идентификации.

Раздел 2.3 является основным во второй главе, в нем излагается алгоритм идентификации изображений.

В подразделе 2.3.1 рассматривается алгоритм полигармонической идентификации. Любая функция /(x)eZ,2((?) может быть как угодно точно аппроксимирована полигармонической функцией (например, многочленом двух переменных). Предполагается, что для функции-изображения f(x) существует « б -адекватное» изображение f£(x), и строится следующее разложение: f£(x) = Gi(x)+G2(x) + . + GN(x) + pN(x), где остаток /?дг (х) является малым,

AkGk(x)= О, Ak~lGk{x)*0 а полигармонические функции G^ix) являются взаимно ортогональными.

Алгоритм полигармонического разложения состоит в следующем: функциях*) может быть разложена согласно лемме Новикова f(x)=g lW + ^lW

Обозначим /q(x) = f(x), для k = \,2,.,N выполняется следующая рекуррентная процедура а- ): а к ) выделение гармонической составляющей fк-{(*) = gk(x)+hk(x), bfc ) вычисление лапласиана

Ah =• /*(*).

Пусть Ah\ (х) = /2 (•*) ■ Функция h\ (х) определяется по /2 (*) единственным образом как решение уравнения Пуассона из подпространства N(Q), что можно формально записать в виде h\{x)= A~l f2(x) xgQ.

Если обозначить через П оператор проецирования на /"(б), считать функции f{x), стоящие под знаком свертки, продолженными нулем вне Q, то получим

A-Xf{x) = n{h(y)*E(x -у)), где - фундаментальное решение уравнения Лапласа [36].

Далее полученная выше функция /2 (х) раскладывается согласно лемме Новикова.

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

Из равенств ак ) - Ък ) следует

К М = А"'Л М = W + hM (*)) и мы получаем разложение hx (х) = A~lg2 (х) + A~lh2 (х) = A-1 g2 (х) + А~2/2 (х) = A->g2 (х) + A~2g3 (х) + A~2h3 (х). В итоге получаем разложение iA-k+lgk(x)+A~N+lhk(x)= ZGk(x)+PN(x), к=1 к=1 где gk{x) гармонические функции, a = являются полигармоническими порядка строго к.

Можно доказать, что Gk{x), {к = 1,2,.,iV) и р^(х) взаимно ортогональны в Ь2(0).

Функция-изображение J{x) может быть адекватно заменена аппроксимирующей в норме L2{Q) полигармонической функцией fs(х), для которой получаем равенство

М= !<?*(*)• к=1

Действительно, остаток /?дг (х) является по построению малым по норме, а малые в норме Ь2 (£?) функции не различимы для глаза.

В процедуре ау-) - Ъстроятся аппроксимации g^(x) функций-оснований L £ ckin(x). i=l

Матрица коэффициентов С = (сд./) размера LxN полностью определяет функцию /£{х), то есть идентифицирует изображение fix). Если это изображение в числовом представлении является матрицей размера S х Т, то коэффициент сжатия в задаче идентификации имеет вид ST К = — .

LN

Доказана следующая оценка: где q <0,3 если Q = (0;l)x (0;l).

Отсюда вытекает косвенная оценка полигармонического слагаемого Gk(x) через его функцию gjt(x)>

По норме вычисленной функции можно определить величину и оценить слагаемые G^ix), а также возможность прекращения рекуррентной процедуры.

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

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

В разделе 3.1 приводится подробное изложение нового метода максимизации столбца [24, 35], который используется для определения главного собственного числа и вектора для матрицы АтА.

Для квадратной матрицы А = J порядка п обозначим ак = ip\k>a2k>--'ankY -ее£-тый столбец (Г-знак транспонирования), ajc,ap)= Y,aik •aip. /=1

Норму столбца будем обозначать ЦядЦ, \akf~ = {ак,ак). Предварительное преобразование состоит в том, чтобы первый столбец имел наибольшую норму, Цс^Ц >||аА|.

Через Up {а) = {ujj ) обозначаются матрицы элементарного поворота с элементами u\\=upp-c, - и\р - ii р\ - s, (с = cos a, s = sin а), остальные диагональные элементы равны единице, внедиагональные - нулю. Столбцы матрицы В = {by ), В = AUр имеют вид

Ъ\ = са\ + sap, bp = -sa\ + сар, Ь^=а^,кФ\,р. Очевидно равенство ц2

2 II ц2

ЬР =Ы1 + ар

Угол а = а определяется следующим правилом a) - J3): а) если р)если а, а,

71 О, то о.р = --sgn(ahap);

Ф 0, то угол а.р определяется равенством tg2ap =

2 [ahap)

2 II II2 Ы 2а„ е

С П ~2'2

Доказано следующее утверждение:

Лемма 3.1. Если ЦаЛ^Цо^Ц, то Ц^Ц>1^1, то есть первый столбец не меньше исходного старого, причем

МрН, то есть новые столбцы ортогональны).

Формируется матричная последовательность Ак = (я/у]:

АХ=А, Ак+х=Акир(к){ар(к)),., где р(к) = k[mod(n-l)] + 2, (£ = 0,1,2,.), при этом целочисленный индекс р = р(к) изменяется циклически от 2 до п.

Теорема 3.1. Матричная последовательность Ак, к = 1,2,. сходится.

Получаем предельное равенство

-^00 = Л. Vqo , где V0о = (у/у j - ортогональная матрица, а первый столбец аматрицы ортогонален остальным. Следовательно,

ATAV00=V00B, т здесь В = А00А00, то есть первый столбец Vj матрицы V^ является собственТ ным вектором матрицы А А с собственным числом Л Т ляется наибольшим для А А). оо ах 2 которое яв

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

В разделе 3.2 рассматривается метод Шмидта в классе ступенчатых функций с постоянным шагом по х1 и по х2. Интегральный оператор заменяется матричным оператором. Для определения главного собственного числа и его собственного вектора используется метод максимизации столбцов.

В последнем разделе 3.3 излагается алгоритм сглаживания. Перед применением технологии JPEG или метода Шмидта производится предварительное преобразование, соответствующее сглаживанию функции-изображения, и позволяющее обратное преобразование.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Василенко, Вера Викторовна

ЗАКЛЮЧЕНИЕ

В диссертации поставлены задачи и достигнуты цели исследования:

1. Разработан алгоритм полигармонического разложения функции, в частности, алгоритм выделения гармонической составляющей функции двух переменных /{x^&LjiQ). Гармоническая составляющая является проекцией функции на бесконечномерное подпространство, то1 есть содержит существенную часть исходной функции, при этом для запоминания гармонической функции требуется значительно меньше информации.

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

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

4. Метод Шмидта и сингулярное разложение, использованные вместе с методом Хаффмана, дают для полутоновых изображений результат сжатия, сравнимый с представляемым стандартной технологией JPEG.

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Василенко, Вера Викторовна, 2006 год

1. Астафьева Н.М. Вейвлет-анализ: основы теории и примеры применения //УФН.- 1996.-Т. 166.-№ 11.-С. 1145-1170.

2. Бахвалов Н. С., Жидков Н.П., Кобельков Г.М. Численные методы. М.: Лаборатория базовых знаний, 2001. - 632 е.: ил.

3. Беклемишев Д.В. Курс аналитической геометрии и линейной алгебры: Учеб. для вузов. М.: Физико-математическая литература, 2001. - 376 с.

4. Белозерский JI.A. Основы построения систем распознавания образов // Донецкий Государственный институт искусственного интеллекта. Курс лекций.-4.1.-1999.-100 с.

5. Быстрые алгоритмы в цифровой обработке изображений П.С.Хуанг, Дж.-О. Эклунд, Г. Дж. Нуссбаумер и др. / Под ред. Т.С. Хуанга. Пер. с англ. - М.: Радио и связь, 1984. - 224 е.: ил.

6. Василенко В.В. О решении уравнения Пуассона в ограниченной области // Сб. матер. 9-ой Всерос. конф. «Наука. Экология. Образование». -г. Краснодар, 2004. С. 195-196.

7. Василенко В.В. Об одном алгоритме сжатия цифровых изображений // Межвуз. сб. научн. трудов. № 5. Т. 1. - Краснодарский военный институт им. Штеменко С.М., г. Краснодар, 2004. - С. 172-174.

8. Василенко В.В. Сингулярное разложение матрицы и алгоритм сжатия изображения // Известия вузов. Северо-Кавказский регион. Технические науки. 2005. - Прил. №3. - С. 32-39.

9. Василенко В.В. Цветовые модели. Основные принципы и современный подход к хранению и передаче цифровых изображений // Всерос. научн.журнал «Общество и право». Вестник Краснодарской академии МВД России. 2004. - №1. - С. 54-56.

10. Василенко В.В. К задаче идентификации цифровых изображений // Информатизация и информационная безопасность правоохранительных органов: Сб. тр. XIV Международн. конф. 24-25 мая 2005. М., 2005. -С. 85-87.

11. Василенко В.В. Математические методы в системах слежения и обеспечения безопасности объектов // Современное общество: проблемы безопасности, преступности, терроризма: Тр. Всерос. научн.-практич. конф. 19-20 мая 2005 г. г. Краснодар, 2005. - С. 14-16.

12. Василенко В.В., Лежнев В.Г., Свидлов А.А. К проблеме анализа цифровых изображений // Известия вузов. Северо-Кавказский регион. Технические науки. 2005. - Прил. №3. - С. 13-22.

13. Василенко В.В., Лукьяненко В А. Сжатие и кодирование цифровой информации // Математические методы и информационно-технические средства: Тр. Всерос. научн.-практич. конф. 24 июня 2005 г. -г. Краснодар, 2005. С. 4-5.

14. Василенко Г.И., Тараторил A.M. Восстановление изображений. М.: Радио и связь, 1986. - 304 е.: ил.

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

16. Ватолин Д.С. Алгоритмы сжатия изображений: метод, пос. Изд. отд. факультета Вычислительной Математики и Кибернетики МГУ им. М.В. Ломоносова, 1997. - 76 с.

17. Вешвез В.П. Алгоритмы анализа изображения лица человека для построения интерфейса человек-компьютер: Автореф. . канд. физ.-мат. наук. М., 2004. - 24 с.

18. Владимиров B.C., Жаринов В.В. Уравнения математической физики: Учеб. для вузов. М.: Физико-математическая литература, 2000. - 400 с.

19. Владо Дамъяновски. Библия охранного телевидения. Пер. с англ. - М.: Ай-Эс-Эс Пресс, 2003. - 344 е.: ил.

20. Воронин А. В поисках золотой середины // Журнал информационных технологий CHIP Special. -2003. № 2. С. 29-33.

21. Голуб Дж., Ван Лоун Ч. Матричные вычисления. М.: МИР, 1999. -548 с.

22. Горелик А.Л., Скрипкин В.А. Методы распознавания: Учеб. пособие. -М.: Высш. шк., 2004. 261 е.: ил.

23. Деммелъ Дэю. Вычислительная линейная алгебра. М.: Мир, 2001. -429 с.

24. Дж. Миано. Форматы и алгоритмы сжатия изображений в действии: Учеб. пособие. М.: Триумф, 2003. - 363 е.: ил.

25. Дэюеймс Д. Мюррей, Уильям ван Райпер. Энциклопедия форматов графических файлов: Пер. с англ. Киев: BHV, 1997. - 672 с.

26. Ильин В.А., Лозняк Э.Г. Линейная алгебра: Учеб. для вузов. М.: ФИЗ-МАТЛИТ, 2001.-320 с.

27. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. -М.: ФИЗМАТЛИТ, 2004. 572 с.

28. Коршунова Н.П. Повышение эффективности применения методов сжатия цифровых изображений: Автореф. .канд. техн. наук. Тула, 2004. -20 с.

29. Кричевский Р.Е. Сжатие и поиск информации. М.: Радио и связь, 1989. 167 е., ил.

30. Куница А.В. Методы сжатия информации // Информационная безопасность при использовании средств вычислительной техники: Матер, меж-вуз. научн.-практич. конф. г. Краснодар, 2002. - С. 17-20.

31. Лежнев В.Г. Выделение гармонической составляющей // Численный анализ: теория, приложения, программы. М.: МГУ им. М.В. Ломоносова, 1999.

32. Лежнев В.Г., Нестеренко А.Г. Метод сингулярного разложения матрицы // Численные методы анализа. М.: МГУ им. М.В. Ломоносова, 1995. -С. 183- 189.

33. Лежнев В.Г., Чижиков В.И. К задаче геопотенциала // Образование и некорректно поставленные задачи: Тез. международн. научн. конф. М.: МГУ им. М.В. Ломоносова, 1986.

34. Локальные сети. Полное руководство / Под ред. В.В. Самойленко. Киев: Век+, СПб.: КОРОНА принт, 2004. - 400 с.

35. Мала С. Вейвлеты в обработке сигналов: Пер. с англ. М.: Мир, 2005. -671 е., ил.

36. Мастрюков М. Алгоритмы сжатия информации. Часть 7 // Монитор. -1994.-№6.-С. 12-20.

37. Михайлов В.П. Дифференциальные уравнения в частных производных. -М.: Наука, 1987.

38. Морозов В.А., Колос М.В., Колос КВ. Регуляризующий алгоритм решения задачи восстановления сигналов в системах с небелыми шумами в наблюдениях // Научный отчет № 5/99. МГУ им. М.В. Ломоносова: На-учно-исследоват. вычислит, центр, 1999.

39. Морозов В.А., Поспелов А.В. Математические методы обработки изображений. М.: МГУ им. М.В. Ломоносова, 1989. - 74 с.

40. Морозов В.А., Поспелов А.В. Цифровая обработка сигналов. М.: МГУ им. М.В. Ломоносова, 1986. - 81 с.

41. Новиков П.С. Об единственности решения обратной задачи потенциала // ДАН СССР. 1938.-Т. 18. -№3.

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

43. Пытьев Ю.П. Морфологический анализ изображений. // ДАН СССР. -1983. Т. 269. - № 5. - С. 1061-1064.

44. Пытьев Ю.П., Чуличков А.И. ЭВМ анализирует форму изображения // Математика и кибернетика. № 5 - М.: Знание, 1988.

45. Сэломон Д. Сжатие данных, изображений и звука. М.: Техносфера, 2004.-368 с.

46. Треногий В.А. Функциональный анализ: Учеб. М.: ФИЗМАТЛИТ, 2002. -488 с.

47. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. В 3-х томах. СПб.: Лань, 1997.

48. Фомин А.А. Основы сжатия информации: Метод, пос. Изд. СПбГТУ. -СПб, 1998. - 83 с.

49. Цифровая обработка изображений в информационных системах: Учеб. пособие / И.С. Грузман, B.C. Киричук и др. Новосибирск: НГТУ, 2002. -352 с.

50. Черноглазое А.Г. Исследование и разработка адаптивных методов и устройства цифрового сжатия и восстановления спектра телевизионных изображений: Автореф. . канд. техн. наук. М., 2004.

51. Шлихт Г.Ю. Цифровая обработка цветных изображений. М.: ЭКОМ, 1997.-336 е.: ил.

52. Ярославский Л.П. Введение в цифровую обработку изображений. М.: Сов. радио, 1979. - 312 е.: ил.

53. А.Е. Jacquin. Image coding based on a fractal theory of iterated contractive image transformations //IEEE Trans. Image Processing. 1992. V.l. P. 18-30.

54. Amara Graps. An Introduction to Wavelets.http://www.amara.com/IEEEwave/IEEEwavelet.html.

55. M. Barnsley, L. Hurd. Fractal Image Compression. AK Peters, 1993.

56. Сингулярные числа матриц-изображений класса фото-анфас

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

58. Оцифрованное изображение рассматривается как дискретная функция. Наи более простым является представление рисунка в Ьтр-формате. В таком виде изо бражению можно однозначно сопоставить цифровую матрицу.

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

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