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

На правах рукррыетгу

Василенко Вера Викторовна

МАТЕМАТИЧЕСКИЕ АЛГОРИТМЫ АНАЛИЗА ЦИФРОВЫХ ИЗОБРАЖЕНИЙ

05.13.18- математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Ставрополь - 2006

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

доктор физико-математических наук, профессор Лежнев Виктор Григорьевич

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

доктор физико-математических наук, профессор Наац Игорь Эдуардович

Ведущая организация Краснодарское высшее военное

училище имени генерала армии Штеменко С.М. (Военный институт)

Зашита состоится « 30 » июня 2006 г. в 12:00 часов на заседании диссертационного совета ДМ 212.256.05 в Ставропольском государственном университете по адресу: 355009, г.Ставрополь, ул. Пушкина, 1, ауд. 214.

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

Автореферат разослан мая 2006 г.

Научный руководитель

Официальные оппоненты

Ученый секретарь у-

диссертационного совета лгърг.^. Копыткова Л.Б.

Общая характеристика работы

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

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

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

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

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

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

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

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

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

Публикации. По теме диссертационного исследования опубликовано 10 статей.

Структура диссертационной работы

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

Научная новизна и результаты, выносимые на защиту,

состоят в следующем:

1) получен и исследован алгоритм полигармонического разложения функции двух переменных;

2) предложена и обоснована методика идентификации изображений, основанная на представлении функции-изображения ее полигармоническим разложением;

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

4) разработан алгоритм сжатия, основанный на применении метода максимизации столбцов для разложения Шмидта, а так же для применения БУО-разложения матрицы в задаче сжатия;

5) представлен допускающий обращение алгоритм сглаживания, предваряющий основной алгоритм компрессии; проведен численный эксперимент.

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

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

Апробация работы. Основные результаты диссертационной работы были представлены на конференциях: - 5-я и 7-я межвузовские научные конференции «Проблемы математического и компьютерного моделирования в научных исследованиях и образовательном процессе», Краснодар, Крас-

нодарское военное авиационное училище летчиков, 2003 и 2005 гг.

- Всероссийская научная конференция молодых ученых и студентов «Современное состояние и приоритеты развития фундаментальных наук в регионах», Краснодар, Кубанский государственный университет, 27-30 сентября 2004.

- 9-я всероссийская конференция «Наука. Экология. Образование», Анапа - Краснодар, 1-3 октября 2004.

- XIV Международная конференция «Информатизация и информационная безопасность правоохранительных органов» Москва, Академия управления МВД России, 2005.

- Всероссийская научно-практическая конференция «Математические методы и информационно-технические средства», Краснодар, Краснодарская академия МВД России, 24 июня 2005 г.

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

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

Диссертационное исследование являлось составной частью работы по проекту РФФИ № 03-01-96698 «Биоиндикаторы и математические алгоритмы анализа их хромограмм», 2003-2005 гг.

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

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

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

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

В разделе 1.3 приведено доказательство метода Шмидта для представления функции ./¡Ху)> f(x<y)s L2(Q), (х,у)е Q = {0;ï)x (0;l) в виде

N

fix, у) — LJ-k ак (у)+ Pu у).

/t=;

где функция pft{x,y) стремится к нулю при Nсо. функция a¿(jc) определяется как собственная функция для главного собственного числа Л^ интегрального оператора Лд Лд,где

1

¿к «(*) = / fk (*. y)*(y)dy>

О

к

/к(х-у)=/(х'у)~ 2 *-jCij(x)b¡{у). j=1

Ecswifipc.y), cifr (x), bfc (y) - дискретные функции с шагом h = Л/-' по* и noy, то для коэффициента сжатия X получаем

2 N

(при непосредственном сжатии без использования алгоритмов квантования и кодирования методом Хаффмана).

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

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

Раздел 2.1 посвящен первой из рассматриваемых задач анализа изображений - разложению функции-изображения Дх,у), {x,y)eQ, на гармоническую составляющую и ортогональную к ней часть. Пусть Q - ограниченная односвязная область с доста-

. у -

точно гладкой границей S, Q - R \Q . Вначале приводится до-

2

казательство для двумерного случая Q a R следующего утверждения (П.С.Новиков, ДАН СССР, 1938): пространство LjiQ) раскладывается в прямую сумму

L2(Q)=r(Q)®N(Q),

где r(Q) — подпространство гармонических в Q функций, а функция h(x) принадлежит N(Q) тогда и только тогда, когда

J h(y)lr,\x — y\dy = 0, х = (Xl ,х2 \ Q+. в V ^ Следовательно, функция /(х)е ¿2(Q) единственным образом представляется в виде

/(*) = «(*)+К*).

где g(x) — гармоническая функция, g(x) и h(x) ортогональны.

Пусть Е{х) — фундаментальное решение уравнения Лапласа

в В?", zm - базисная последовательность точек в Q+, т- 1,2,..., то есть последовательность, отделенная от границы области и удовлетворяющая условию единственности гармонических функций. Обозначим

ym{x)=E{zm-х\ xeQ, т = 1,2,.., где zm = (г*, z™ ) - базисная система точек в Q+.

Лемма 2.1. Система функций линейно незави-

сима и полна в подпространстве r{Q).

Аппроксимация g^{x) проекции на подпространство f(Q) функции /(х) представляется в виде

= Zcmrm(x)

т=1

и может быть определена как решение задачи минимизации функции F(c), с = (с|,...,сдг),

JV 2

F(c)= Лх)~ Zcmym(x) ,

m=1

через I • || в главе 2 обозначена норма в пространстве ¿2 (б)-Необходимое условие экстремума

— = Q,p = l,2....,N,

дср

приводит к невырожденной алгебраической системе с матрицей Грама.

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

В конце раздела 2.1 рассматриваются специальные свойства решений уравнения Пуассона

= (1)

Обозначим через П оператор проектирования в ¿2 (О) на подпространство Г(0). Практически он реализуется решением указанной выше вариационной задачи. Будем обозначать так же 1/(у)Е(х-у)с1у:=/*Е, Л2

предполагая /(у) продолженной нулем вне Q.

Лемма 2.2. Для любой v(.x:)e ¿2(2) решение уравнения (1) в подпространстве N(0) существует, единственно и представляется в виде

и(х)-=(1-Л)(у*Е).

В пространстве ¿2(6) определен оператор Л-1 со значениями в некотором плотном в N(0) подмножестве достаточно гладких функций и(х) - решениях уравнения (1).

Справедливы, в частности, следующие утверждения для решения уравнения Пуассона (1):

1) если N((2) и и(х)|5 = 0, то

^ =0, и(х) = у*Е;

оп ц

2) если = 0, то

\\и{х\\<\^\-Х-НхХ где ~ наименьшее по модулю собственное число оператора Лапласа в () (для первой краевой задачи); если Q = (0;1)х (0;1), то Ад = — 2/Т2.

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

Функция и(х) называется полигармонической порядка т в области Q, если

/Гк(х)= О,

Будем говорить, что и(х) — полигармоническая порядка строго т, если

Ати(х) = 0, Ат~1и(х)*0. Обозначим /~] (£>) — подпространство гармонических в ¿2 (2) функций,

Алгоритм полигармонического разложения состоит в следующем. Функция /(;е) может быть разложена согласно лемме Новикова

Обозначим /о 00 = /00 и для к = \,2,...,Ы реализуем следующую рекуррентную процедуру а^ ) - Ък ): ак ) выделение гармонической составляющей —

Л -1 (*) = £ А <*) + Мх),

Ь^ ) вычисление лапласиана-

ЛЧ =-' /к 00.

Из равенств ак ) - Ьк ^получаем

кк (х) = АГХ/к 00 = А'1 (х)+ Ик+1 (л:))

и, следовательно, имеем

= С*)+ 00+ Л~2Иъ (х).

Обозначая далее Ск 00 = (х) в итоге получаем разло-

жение

к=1 А=1

где ¿^(л) ~ гармонические функции, а /Г^"1)^ (х) яв-

ляются полигармоническими порядка строго к.

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

£2(0)) полигармонической функцией /е{х), для которой получаем равенство

/*(*) = ЪСк{х). к = 1

Будем говорить, что функция /е (х) есть «е -адекватное» изображение, если |/"(дс)- <

В процедуре ак) - ¿¿^ строятся аппроксимации функций-оснований

, £ /=1

Матрица коэффициентов С размера ЬхЫ полностью оп-

ределяет функцию /£(х), то есть идентифицирует изображение Дх). Если это изображение в растровом представлении является матрицей размера Т, то коэффициент сжатия К в задаче идентификации имеет вид

¿ЛГ

Если АИк (х) = f¡í {х), то функция И/С{х) определяется по /к(х) единственным образом как решение уравнения Пуассона из подпространства N(¡2), что можно формально записать в виде

Если П - оператор проектирования на Г(<2), и функция /(.х), стоящая под знаком свертки, продолжена нулем вне то Ик (х) =А~Х/к (х) = (/ - пХГк Ы * Е{х - у)).

Следовательно, может быть решена не только задача идентификации, но и задача восстановления «£- - адекватного» изображения.

В подразделе 2.3.3 доказана также оценка:

И/и»

Отсюда вытекает оценка поли-

Л 'Л*)

где <7 <0,3, если 2 = (0,1)х(0,Г гармонического слагаемого G^x) через его функцию g^C*),

||G,(х}\ = \rk*gk 1 £ qk~' lb II < |gA ||.

По норме вычисленной функции можно оценить сла-

гаемые Gjt(x), а также возможность прекращения рекуррентной процедуры а^) - bfc) задачи идентификации.

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

В дискретном случае функции-изображения это сводится к

*

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

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

Т

го собственного числа и вектора для матрицы А А.

Для квадратной матрицы А = [ctjj) порядка п обозначим

ак - (а\к>а2к' - 'апк)Т ~ ее столбец (Г - знак транспонирования),

(ак,ар)= Zaik-aip. »=1

Норму столбца будем обозначать ЦадЦ, ||«г&|| = [с>к>ак )•

Предварительное ортогональное преобразование матрицы А состоит в том, чтобы первый столбец имел наибольшую норму, ||oj|] > ||аА ||; полученную матрицу обозначим А\ .

Через Uр(сс)— {u¡j J обозначаются матрицы элементарного поворота с элементами щ\—ирр=с, -u\p=up\=s (с-cosa, s = sincc), остальные диагональные элементы равны единице, внедиагональные — нулю.

Столбцы матрицы В - {bjj), В = AUр, имеют вид

¿1 ~ca¡ +sap, bp=-sa\+cap, = a^.k р. Очевидно равенство

ы2+м2=ы2+Ы2-

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

2 i, .¡2 /j" а) если ||íí] I - |а р I =0,то ар =sgn(ax, а р

2 ii ii2

^)если|р]| * 0. то угол ар определяется равенством

2{а1,ар) ( к л

8 ^iTiMTFЬ'2

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

Лемма 3.1. Если |а]|| > Цо^Ц и используется правило а)-ß), то

\М>Н\, {Ьх,Ър)= 0.

Формируется матричная последовательность Ад = [afj

Ai =А, A2=A{U2{a2). -A+\ = ¿kVp{k){ap{k))>--->

где p{k) = k[mod(n-\)}+2, k = 0,1,2,...,

при этом целочисленный индекс р - р{к) изменяется циклически от 2 до п.

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

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

А оо — A Vqo,

где Уоо = Уоо = (у//) - ортогональная матрица, а первый

к

столбец О]0 матрицы А^ ортогонален остальным. Следовательно,

Л» Л» - УТ АТАУао, АГАУ00 =Уа0В.

<х>

т

Здесь В - Д» Ао, то есть первый столбец V] матрицы К«, являет-

т

ся собственным вектором матрицы А А с собственным числом

оо

а\

2 т (которое обычно является наибольшим для А А).

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

В разделе 3.2 рассматривается метод Шмидта в классе ступенчатых функций Дх), х = (xj,x2), с постоянным шагом по Х| и по х2. Интегральный оператор заменяется матричным оператором. Для определения главного собственного числа и его собственного вектора используется метод максимизации столбцов.

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

Для этого выделяется сначала гармоническая составляющая goW функции-изображения /(х),

Для слагаемого /7q(x)g N(q), содержащего все особенности изображения /(х), решается краевая задача:

Au(x) = h0{x) (х е Q), н(х)=0 (xeS). Из свойства 3) раздела 2.1.3 следует равенство

м(х) = hQ*E=\ h0 Су)Е(х - y)dy.

0

Далее для сглаженной функции и(х) применяется алгоритм Шмидта. Полученный сжатый образ обозначим и${х). Сжатым образом исходного изображения /(х) является совокупность (с), с2,...,сдг) и и$(х), где ск - это коэффициенты разложения по

Г к (*) Для Мо(х)-

Восстановление прообраза /(х) состоит, во-первых, в восстановлении £о(х) по коэффициентам во-вторых, в декомпрессии образа и$(х), и, в-третьих, в сложении полученных растровых функций.

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

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

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

Исходный рисунок 1. Размер 200x200 пикселей

Сингулярные числа:

44014,005 178,051 33.704 6,385 2.254 0,182

6709,44 169,943 33,304 6,259 2,141 0,166

3874,43 163,072 32,291 5,957 2,060 0,149

2504,95 156,423 30,474 5,944 1,984 0,136

1917,71 147,665 29,009 5,673 1,845 0,100

1630,161 140,432 27,666 5,557 1,773 0,089

1226,67 133,427 26,097 5,408 1,690 0,070

1189,54 124,233 25,180 5,263 1,588 0,058

952,377 115,851 24,129 5,150 1,529 0,049

822,772 114,293 23,155 4,962 1,474 0,039

783,806 108,692 22,178 4,758 1,437 0,029

686,209 98,497 21,463 4,579 1,289 0,026

627,530 96,124 20,558 4,365 1,235 0,020

581,038 89,711 20,050 4,270 1,143 0,015

568,987 86,611 19,324 4,226 1,109 0,006

524,967 84,157 17,871 4,080 1,074 0,005

465,123 79,866 16,924 3,900 0,983 0,002

439,930 77,199 16,132 3,802 0,934 0,001

408,018 74,418 14,482 3,670 0,916 0,001

366,214 72,416 13,643 3,538 0,807 0,000

348,062 67,766 13,482 3,475 0,781 0,000

336,561 65,363 12,549 3,414 0,699 0,000

313,774 62,745 12,028 3,353 0,620 0,000

295,474 59,065 11,313 3,197 0,594 0,000

282,217 57,068 10,990 3,147 0,529 0,000

275,523 52,968 10,482 3,088 0,501 0,000

261,286 51,459 9,286 2,849 0,477 0,000

246,048 49,345 8,807 2,717 0,441 0,000

235,283 45,235 8,370 2,657 0,394 0,000

215,338 43,624 7,852 2,588 0,338 0,000

206,302 41,692 7,637 2,519 0,305

195,914 40,447 7,485 2,410 0,304

191,864 37,790 7,377 2,332 0,289

184,756 35,201 6,890 2,302 . 0,216

2. Вычисление вклада первых к сингулярных чисел.

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

Исходное изображение, размер 200x200 Восстановлено по 50 сингулярным чис-пиксслей лам

' ч !

Восстановлено по 35 сингулярным чис- Восстановлено по 30 сингулярным числам лам

В таблицах 2.1 - 2.2 показан вклад первых к чисел в общую сумму диагонали сингулярных чисел (рассматриваются рисунки 1, 2) и указаны следующие данные:

к Г -

Р к

/=1

п

I

Ч/ = 1

(П.2.1)

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

по к сингулярным числам отмечено соответственно: «+» — хорошее, «-+» — удовлетворительное, «-» - плохое.

Пусть Х\ - первый коэффициент сжатия после БУО-разложения матрицы-изображения (без кодирования методом Хаффмана). Величина Л\ представляет собою отношение «общего объема» изображения {МхМ) к «объему» восстановленного по к сингулярным числам фото-анфас,

Л1 /к-{Мл-Ы)-Рисунок 1 Таблица 2.1.

к Рисунок l.bmp (200x200)

Рк Качество ¿1

1 0,55 - 100

2 0,65 - 50

3 0,70 : . ■ ■ : 33,(3)

5 0,75 - 20

8 0,80 12,5

12 0,85 ! 8,(3)

20 0,90 -+ 5

35 0,95 + | 2,86

3. Сравнение рисунков разных форматов.

Приведены результаты численных экспериментов с представленными в приложении рисунками 1 и 2.

Рассматривается отношение размеров каждого рисунка в двух разных форматах (Ьтр и Зре§) в непосредственном представлении и после БУВ-фильтрации. Для перевода рисунка из Ьтр-формата в jpeg использовался программный пакет для просмотра рисунков АСОБее.

Сравниваются размеры рисунка в двух форматах — Ьтр и jpeg (табл. 3.1). Черно-белый рисунок, как и цветной, в Ьтр-формате представляется тремя числовыми матрицами. В формате ]ре§ такие изображения фактически представлены одной числовой матрицей — файлом интенсивности, занимающей основной объем памяти.

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

Таблица 3.1.

Номер рисунка и количество старших s¡, отличных от Объем черно-белого Ьтр-изображения, Кб Объем jpeg-изображения, Кб Относительная величина компрессии Л]

нуля

l.bmp, объем 200x200 40,018 4,485 8,92

30 4,918 8,137

20 4,846 8,258

10 4,419 9,056

5 3,890 10,28

2.bmp, объем 220x220 48,418 4,620 10,48

70 5,161 9,38

20 5,429 8,92

10 4,987 9,71

5 4,342 11,15

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

Представлены результаты опытов по оценке вклада в общую сумму к первых чисел диагонали сингулярных значений для 15 черно-белых фотографий разных размеров. В ходе опыта по формуле П.2.1 определяется количество первых таких сингулярных чисел сумма которых составляет = р^-100% от суммы всех сингулярных чисел.

Как видно из таблицы 4.1, около 90 % общей суммы дают первые 30-40 старших сингулярных чисел.

Таблица 4.1.

п 220 220 220 200 200 300 300 300 300 512 512 512 220 200 220

N2 1 к 2 3 4 5 6 7 8 9 10 11 12 13 14 15

40% 1 1 1 1 , , 1 1 1 2 1 1 1 1 1

50% 2 2 3 2 3 2 3 4 2 3 3 3 2 2 3

60% 4 5 4 4 5 4 6 5 4 5 5 4 5 4 4

70% 8 9 7 8 7 9 10 1 1 II 12 14 13 8 7 9

80% 15 14 12 13 II 21 16 17 19 23 20 22 14 12 16

85% 21 22 20 18 19 33 24 26 30 32 30 34 22 20 21

90% 31 33 30 29 28 52 35 36 34 40 43 39 32 30 34

92% 40 41 39 37 39 64 45 44 49 53 52 59 39 41 40

94% 50 52 48 46 45 80 62 59 63 71 77 80 55 50 54

95% 56 61 57 59 53 91 78 84 88 94 97 98 60 58 61

96% 64 67 65 63 61 103 89 95 101 127 124 132 69 70 71

97% 75 80 79 82 85 120 101 1 12 123 165 157 181 79 83 88

98% 89 94 96 95 103 142 127 142 137 210 220 243 98 86 108

99% III 125 1 14 132 109 175 149 168 158 253 260 286 107 98 127

Характеристика пропорциональной зависимости между размером изображений в Ьтр и jpeg-фopмaтax представлена в таблице 4.2.

Таблица 4.2.

Номер рисунка Размер рисунка в пикселях Размер Ьтр, КЬ Ьтр1- черно-белые изображения Размер КЬ Х= Ьтр!/ ]Ре£

1 200x200 117 39 5,31 7,34

2 220x220 141 47 6,08 7,73

3 512x512 768 256 36,6 6,99

4 300x300 210 70 14,71 4,76

5 220x220 141 47 5,7 8,25

6 200x200 117 39 5,4 7,22

7 220x220 141 47 10,2 4,61

8 300x300 263 87,67 8,21 10,68

9 300x300 263 87,67 16,4 5,35

10 512x512 768 256 41,4 6,18

11 512x512 768 256 37,4 6,84

12 220x220 141 47 7,9 5,95

13 300x300 263 87,67 15,84 5,53

14 220x220 141 47 7,3 6,44

15 512x512 768 256 34,3 7,46

5. Получение контурного изображения.

Применение к дискретной функции-изображению дискретного оператора Лапласа Л^ с шагом И, выбранным соответствующим образом, может быть эффективно применено к выделению контурного изображения. Данная операция используется в задаче идентификации, если у функции к = 0,1,...,/^, выделя-

ется гармоническая составляющая g|c{x) (раздел 2.3). Ниже приведены результаты численного эксперимента для изображения № 3 с растром 0,00196, если /г=0,01.

4/4*) ¿2/С*)

Исходная функция-изображение /(дг) X = (Х), )

Основные выводы и результаты работы

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

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

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

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

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

Список работ, опубликованных по теме диссертации

1. Василенко В.В. Об одном алгоритме сжатия цифровых изображений // 9-я Всерос. конф. «Наука. Экология. Образование». - Краснодар, 2004. - С. 172-174.

2. Василенко В.В., Лазарев М.Ю. Об инвариантах цифровых изображений // Всерос. научн. конф. молодых ученых и студентов «Современное состояние и приоритеты развития фундаментальных наук в регионах». - Анапа-Краснодар, 2004. - Т.2. - С. 2223.

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

4. Василенко В.В. Об одном алгоритме сжатия цифровых изображений // Межвузовский сборник научных трудов / Красно-

дарский военный институт им. Штеменко С.М. -2004. - № 5. -Т.1.-С. 172-174.

5. Василенко В В. Один алгоритм анализа цифровых изображений // Тр. конф. «Проблемы математического и компьютерного моделирования в научных исследованиях и образовательном процессе» / Краснодарский военный авиационный институт. - 2003. - 4.2. - С. 93-96.

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

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

8. Василенко В В. Математические методы в системах слежения и обеспечения безопасности объектов // Тр. Всерос. науч-но-практич. конф. «Современное российское общество: проблемы безопасности, преступности, терроризма» / Краснодарская академия МВД России. - 2005. - С. 12-14.

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

10. Василенко В.В., Лукъяненко В.А. Сжатие и кодирование цифровой информации // Тр. Всерос. научно-практич. конф. «Математические методы и информационно-технические средства» / Краснодарская академия МВД России. - 2005. - С. 4-5.

ВАСИЛЕНКО Вера Викторовна

МАТЕМАТИЧЕСКИЕ АЛГОРИТМЫ АНАЛИЗА ЦИФРОВЫХ ИЗОБРАЖЕНИЙ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 25.05.2006 г. Формат 60х84ш<»-Уч.-изд. л. 1,46. Усл. печ. л. 1,63. Бумага Maestro. Печать трафаретная. Тираж 150 экз. Заказ № 6089.

Тираж изготовлен в типографии ООО «Просвещение-Юг»

с оригинал-макета заказчика. 350059 г. Краснодар, ул. Селезнева, 2. Тел./факс: 239-68-31.

ВВЕДЕНИЕ

ГЛАВА 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. Предложена методика сглаживания изображений, основанная на специальных решениях уравнения Пуассона.

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

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-разложения.