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

Актуальность темы

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

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

Отметим актуальность научных исследований в области цифровой обработки телевизионных и компьютерных изображений для успешной деятельности подразделений ОВД и вневедомственной охраны в частности. В «Основных направлениях научных исследований в системе Министерства внутренних дел Российской Федерации до 2000 года» (Приложение 2 к приказу № 238 МВД РФ от 23 июня 1995 г.) уделялось большое внимание необходимости совершенствования информационного обеспечения деятельности органов внутренних дел и развития систем связи и передачи данных в органах внутренних дел (пп. 7.2, 7.4 вышеуказанного документа). Это сыграло определяющую роль при выборе темы диссертационных исследований.

Диссертационная работа выполнена в соответствии с «Концепцией развития системы информационного обеспечения органов внутренних дел в борьбе с преступностью» (Приказ № 229 МВД РФ от 12 мая 1993 г.) на кафедре теоретических и прикладных математических дисциплин Воронежского института МВД.

РФ в рамках исследований, проводившихся согласно тематическому плану НИР института по теме «Компьютерное сжатие изображений» (№ госрегистрации 01.9.80 0 2 337) и в рамках Договора № 2/95 о творческом содружестве между УВД Воронежской области и ВВШ МВД РФ.

Цель и задачи исследования

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

В соответствии с поставленной целью задачами исследования являются:

1) Проведение сравнительного анализа существующих методов сжатия графической информации.

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

— исследование рядов с неотрицательными частными суммами по мультипликативным системам функций;

— обоснование возможности коррекции полиномов по двумерной системе Хаара;

— получение двоичного разложения двумерного пространства ВМО (Bounded Mean Oscillation).

3) Построение математической модели процессов сжатия и восстановления графической информации на основе двумерного дискретного преобразования Хаара с учетом коррекции полиномов Хаара на этапе восстановления.

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

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

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

Научная новизна. На защиту выносятся следующие результаты, впервые достаточно подробно развитые или впервые полученные в настоящей работе:

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

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

— найдены ограничения на спектр коэффициентов, при которых ряд по мультипликативной системе функций, в частности, по системе Уолша, является рядом Фурье;

— получено двоичное разложение двумерного пространства ВМО, норму которого предполагается использовать для оценки и прогноза степени сжатия графической информации.

2) Построена математическая модель процессов сжатия и восстановления графической информации на основе двумерного дискретного преобразования Хаара с учетом коррекции полиномов Хаара на этапе восстановления.

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

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

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

— программная модель процесса сжатия графической информации на основе дискретного преобразования Хаара;

— программная модель передачи данных от источника к приемнику методом «стопка книг» по каналу без помех;

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

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

Дальнейшее практическое использование результатов исследования в деятельности подразделений ОВД возможно в двух направлениях:

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

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

Реализация и внедрение результатов работы. Реализованный на языке С программный комплекс «Компрессор графических файлов», предназначенный для сжатия и последующего восстановления с целью визуализации статических растровых полутоновых изображений, хранящихся в файлах формата PCX, используется в деятельности Информационного центра при УВД Воронежской области в качестве основы для построения системы рассылки ориентировок в ГРОВД области (Акт внедрения от 1 декабря 1998 г.).

Полученные в ходе диссертационных исследований результаты внедрены в учебный процесс Воронежского института МВД России в форме теоретического материала и компьютерных программ и используются при чтении лекций и проведении практических и лабораторных занятий по курсам «Численные методы» и «Средства и методы программирования» на радиотехническом факультете ВИ МВД России (Акт внедрения от 20 ноября 1999 г.).

Личный вклад автора в диссертационную работу. Диссертационные исследования проводились автором на кафедре теоретических и прикладных математических дисциплин Воронежского института МВД России под руководством доктора физико-математических наук профессора Родина В. А. Большая часть результатов, выносимых на защиту, получена лично автором, что подтверждается 8 единоличными публикациями. В работах с соавторами соискателю принадлежат основные теоретические результаты и алгоритмы, за исключением результатов п. 2.3 (теоремы 2.2−2.5), полученных совместно с научным руководителем. Все представленные в диссертационной работе результаты включены в диссертацию с согласия соавторов.

Апробация результатов работы. Основные результаты диссертационной работы докладывались, обсуждались и получили положительные оценки на 7-й Саратовской зимней математической школе им. A.A. Привалова (Саратов,.

1994 г.) — II Международной конференции «Алгебраические, вероятностные, геометрические, комбинаторные и функциональные методы в теории чисел» (Воронеж, 1995 г.) — II Республиканской электронной научной конференции «Современные проблемы информатизации» (Воронеж, 1997 г.): научно-практических конференциях BBIII МВД России (1996, 1997, 1998 гг.) — научных семинарах кафедры теоретических и прикладных математических дисциплин Воронежского института МВД России (1994;1999 гг.) — научном семинаре Воронежского научно-исследовательского института математики (1999 г.) — научном семинаре кафедры математического моделирования Воронежской государственной технологической академии (1999 г.).

Публикации. Результаты диссертации опубликованы в 14 печатных работах. В том числе 4 статьи в сборниках, тезисы 9 докладов и публикация в «Аннотированном информационном бюллетене о научно-исследовательских и опытно-конструкторских работах, проведенных в Министерстве внутренних дел Российской Федерации».

Структура диссертации. Диссертационная работа изложена на 131 странице машинописного текста, содержит 25 иллюстраций и состоит из Введения, четырех глав, Заключения, списка литературы из 96 наименований, Приложения 1 с исходными текстами программ, Приложения 2 с иллюстрациями результатов экспериментов с программными моделями и Приложения 3 с документами о внедрении результатов исследования.

Заключение

.

При выполнении диссертационного исследования получены следующие основные научные и практические результаты:

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

2) Развиты теоретические подходы к совершенствованию математической модели процесса сжатия графической информации, а именно:

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

— найдены ограничения на спектр коэффициентов, при которых ряд по мультипликативной системе функций, в частности, по системе Уолша, является рядом Фурье;

— получено двоичное разложение двумерного пространства ВМО, норму которого предполагается использовать для оценки и прогноза степени сжатия графической информации.

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

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

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

— программная модель процесса сжатия графической информации на основе дискретного преобразования Хаара;

— программная модель передачи данных от источника к приемнику методом «стопка книг» по каналу без помех;

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

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

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

1) Реализованные инструментальные средства в виде программного комплекса «Компрессор графических файлов», предназначенного для сжатия и последующего восстановления с целью визуализации статических растровых полутоновых изображений, хранящихся в файлах формата PCX, используются в деятельности Информационного центра при УВД Воронежской области в качестве основы для построения системы рассылки ориентировок в ГРОВД области (Акт внедрения от 1 декабря 1998 г.).

Полученные в ходе диссертационных исследований результаты внедрены в учебный процесс Воронежского института МВД России в форме теоретического материала и компьютерных программ и используются при чтении лекций и проведении практических и лабораторных занятий по курсам «Численные методы» и «Средства и методы программирования» на радиотехническом факультете ВИ МВД России (Акт внедрения от 20 ноября 1999 г.).

По результатам исследования можно сделать следующие выводы и замечания.

1) Дискретное преобразование Хаара имеет ряд преимуществ по сравнению с традиционно используемым ДКП:

• простота реализации на ЭВМ и возможность построения алгоритма в целочисленной арифметике;

• отсутствие эффекта Гиббса и связанных с ним артефактов;

• дискретное преобразование Хаара требует меньше элементарных операций при вычислении на ЭВМ (N против TVlogA" для ДКП, где N — число отсчетов функции).

2) При больших степенях сжатия изображение имеет блочную структуру, что связано как с разрывностью самих функций Хаара, так и с тем фактом, что в соответствии с алгоритмом изображение разбивается на блоки 8×8 пикселей (по аналогии с JPEG), каждый из которых сжимается независимо. Даже использование одномасштабных всплесков Хаара вместо прямого произведения одномерных систем Хаара и переход от независимого сжатия отдельных блоков к сжатию всего изображения в целом не избавляет от мозаичности. Для устранения мозаичности в методе JPEG используются процедуры сглаживания на границах блоков. Лучшее решение этой проблемы состоит в отказе от всплесков Хаара в пользу «гладких» всплесков.

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

4) Нелинейная аппроксимация, минимизирующая ошибку в метрике Z2, принята в качестве основы для квантования коэффициентов Фурье-Хаара из соображения простоты реализации и не учитывает особенностей человеческого зрения. Квантование в алгоритме JPEG основано на эмпирических таблицах, поскольку теоретическое обоснование алгоритма квантования является проблемой.

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

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