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

На правах рукописи

РГ5 ОД

1 з т гзоз

ГОРЛОВ СЕРГЕЙ КУЗЬМИЧ

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

Специальность 05.13.16 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Воронеж 2000

Работа выполнена на кафедре теоретических и прикладных математических дисциплин Воронежского института МВД России

Научный руководитель: доктор физико-математических наук,

профессор В. А. Родин

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

доктор технических наук, профессор В. В. Сысоев доктор технических наук,; профессор О. Я. Кравец

Ведущая организация: Государственное учреждение

научно-производственное объединение «Специальная техника и связь» МВД РФ (г. Москва)

Защита состоится «ии» июня 2000 г.

в У.%°^часов на заседании диссертационного совета К 052.17.01 при Воронежском институте МВД России по адресу: 394065, г. Воронеж, пр. Патриотов, 53.

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

Автореферат разослан « 19» мая 2000 г.

Ученый секретарь диссертационного совета кандидат физико-математических наук "/дсЛ? С. В. Ролдугин

&Р

1Ш& -оШ-м?*. и*, о

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Диссертационная работа выполнена в соответствии с «Концепцией развития системы информационного обеспечения органов внутренних дел в борьбе с преступностью» (Приказ № 229 МВД РФ от 12 мая 1993 г.) на кафедре теоретических и прикладных математических дисциплин Воронежского института МВД РФ в рамках исследований, проводившихся согласно тематическому плану НИР института по теме «Компьютерное сжатие изображений» (№ госрегистрации 01.9.80 0 02337) и в рамках Договора № 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.3-2.5), полученных совместно с научным руководителем. Все представленные в диссертационной работе результаты включены в диссертацию с согласия соавторов.

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

Публикации. Результаты диссертации опубликованы в 14 печатных работах. В том числе 4 статьи в сборниках, тезисы 9 докладов и публикация в

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

В п. 2.1 рассматривается математическая модель статического растрового полутонового изображения. В соответствии с принятой моделью изображение задается функцией яркости /(*,>') в области 0 й г,_у < 1. После аналого-цифрового преобразования информация об изображении определяется растром, т.е. матрицей отсчетов функции яркости = i,j = l,2,...,N. Такое изображение определено на решетке N хЫ пикселей, значения которых соответствуют различным уровням серого цвета и образуют дискретную шкалу.

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

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

Теорема 2.5. Оператор (¿'*/){х) = зир|^|/|)(х)| имеет слабый тип

где С - абсолютная константа.

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

^1, ¿1п+£), т.е. для любого у > 0 справедливо неравенство

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

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

Третья глава посвящена построению математической модели процесса сжатия изображений на основе дискретного преобразования Хаара (п. 3.1) и разработке на ее основе компьютерной системной модели (п .3.2).

Функция яркости f{x, у) в области 0 < < 1 представляется в виде двумерного ряда Фурье по системе Хаара

Л*,у) = Х1>Ух,(*)хУМ •

i=i j=i

Коэффициенты Фуръе-Хаара вычисляются по формуле:

11

ач = Ц/{*,у)х.,(х)х.Ау)'Щ> ■

о о

Для конечного множества пар индексов М рассмотрим в качестве приближения к функции / сумму

/к =

М ем

С учетом равенства Парсеваля ^^я^ = |/jf ошибка в метрике^ равна

;=1 у=1

f \т

К ~

K(<,j)*M У

Минимальная ошибка аппроксимации / полиномом fM, содержащим К слагаемых, есть

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

Ег{К,/)4 ¿ЮТ2-

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

Для функции яркости имеют место неравенства А</{х,у)<Н, где /г

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

допустимого диапазона. Строгое математическое обоснование малости меры множества, на котором происходят такие «выбросы», для полиномов по двумерной системе Хаара получено впервые (теоремы 2.3-2.5 в п. 2.3) и является развитием математической модели в сторону обеспечения ее адекватности. Малость меры множества, на котором значения полинома наилучшего приближения в метрике выходят за границы заданного диапазона, означает, что связанные с этими «выбросамт> дефекты изображения будут иметь локальный характер и дает основание для использования коррекции полиномов по двумерной системе Хаара в смысле срезки их по заданным уровням Л и // . А именно, в качестве приближения к функции яркости / мы вынуждены брать не сам полином /м, а функцию

Н, если /м(х,у)>Н, /'АХ,У) = - К если /м(х,у)<И,

/м, если И </м(х,у)< Н.

Процесс сжатия графической информации в рамках изложенной математической модели сводится к тому, что функция яркости / исходного

изображения аппроксимируется более «простой» функцией /А/ - полиномом по двумерной системе Хаара, заданным своими коэффициентами, так что информацию о /м можно передать меньшим количеством данных, чем об исходной функции /. Восстановленное изображение определяется уже не функцией /и , а полученной из нее путем коррекции функцией /'ы .

В дискретном случае получаем прямое

и

N N

и обратное

// лг

/н = ХЕяД-МхДд',), *,/= 1,2,...,ЛГ, .=1

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

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

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

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

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

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

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

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

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

Описанию инструментальных программных средств посвящен п. 4.2. Они реализованы на языке С в виде пакета программ «Компрессор графических файлов», предназначенного для работы с растровыми полутоновыми изображениями в графическом режиме 13Ь(УСА), обеспечивающем разрешение 320x200 пикселей и палитру из 64 градаций серого цвета (от черного до белого включительно). Задача создания инструментальных средств продиктована практическими нуждами подразделений ОВД. Отличительными особенностями данных программных средств по отношению к имеющимися коммерческими пакетами аналогичного назначения являются минимальные требования к аппаратным средствам, специализация и возможность интеграции в другие программные средства.

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

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

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

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

В заключении изложены основные результаты диссертационной работы.

В приложении 1 приводятся исходные тексты программного продукта «Компрессор графических файлов» на языке С.

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

В приложении 3 представлены документы по внедрению результатов диссертационной работы на ИЦ УВД Воронежской области и в учебный процесс ВИ МВД России.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Научные статьи и доклады на НТК

1. Одна реализация метода сжатия изображений с помощью нелинейной аппроксимации сумм Фурье-Хаара // Теория функций и приближений: Сб. науч. тр. 7-й Саратовской зимней математической школы им. А.А.Привалова. 4.2. Саратов: Изд-во Саратовского ун-та, 1995. С. 117-122 / Соавт.: Корыстен A.B., Родин В.А.

2. Об одном алгоритме равномерной передачи видеоданных // Сб. научн. тр. ВВШ МВД РФ. Вып.4. Воронеж: Изд-во ВВШ МВД РФ, 1997. С. 140-142.

3. О коррекции нелинейной аппроксимации двумерных рядов Хаара для сжатия информации // Вестник ВВШ МВД РФ. Воронеж: Изд-во ВВШ МВД РФ, 1998. № 2, С. 41-45 / Соавт.: Родин В.А.

4. Двоичное разложение двумерного пространства ВМО // Сб. науч. тр. матем. ф-та ВГУ Воронеж: Изд-во ВГУ, 1998. Вып.З. С. 44-48 / Соавт/. Родин В.А.

Тезисы докладов на НТК

5. Об одной реализации метода сжатия изображений с помощью нелинейной аппроксимации сумм Фурье-Хаара П Тез. докл. науч.-практ. ионф. ВВШ МВД РФ. Воронеж: Изд-во ВВШ МВД РФ, 1994. С. 8-9 / Соавт.: Корыстен A.B., Родин В.А.

6. О рядах с положительными частными суммами по мультипликативным системам функций // Тез. докл. науч.-практ. конф. ВВШ МВД РФ. Воронеж: Изд-во ВВШ МВД РФ, 1995. С. 7-8.

7. О рядах с положительными частными суммами по системе Уолша // Алгебраические, вероятностные, геометрические, комбинаторные и функциональные методы в теории чисел: Тез. докл. П Международ, науч. конф. Воронеж: Изд-во ВГУ, 1995. С. 44.

8. О практической реализации метода сжатия графической информации // Тез. докл. науч-практ. конф. ВВШ МВД РФ. 4.2. Воронеж: Изд-во ВВШ МВД РФ, 1996. С. 74 / Соавт.: Родин В.А.

9. Моделирование на ЭВМ передачи данных методом "стопка книг" // Современные проблемы информатизации: Тез. докл. П Респубя. электронной науч. конф. Воронеж: Изд-во ВПУ, 1997. С. 134-135.

10. Использование двумерных рядов по системе Хаара для представления и обработки видеоданных // Тез. докл. науч.-практ. конф. ВВШ МВД РФ. 4.2. Воронеж: Изд-во ВВШ МВД РФ, 1997. С. 6-7.

11. К вопросу о коррекции искажений при сжатии графической информации И Тез. докл. науч.-практ. шнф. ВВШ МВД РФ. 4.2. Воронеж: Изд-во ВВШ МВД РФ, 1997. С. 92.

12.0 возможности использования нормы пространства ВМО для оценки степени сжатия информации // Тез. докл. науч.-практ. конф. ВВШ МВД РФ. 4.2. Воронеж: Изд-во ВВШ МВД РФ, 1998. С. 7-8.

13.0 коррекции полиномов Хаара, связанных с обработкой графической информации // Современные проблемы теории функций и их приложения: Тез. докл. 10-й Саратовской зимней школы. Саратов: Изд-во Саратовского ун-та, 2000. С. 35 / Соавт.: Родин В. А.

Другие публикации

14. Компьютерное сжатие изображений (Прикладная НИР) // Аннотированный информационный бюллетень о научно-исследовательских и опыгно-конструхторских работах, проведенных в Министерстве внутренних дел Российской Федерации. Вып.З. М.: НПО "Техника", 1998.

ЛР № 020728 от 09.02.98. Подписано к печати 19.05.2000 Усл. печ. л. 1,0. Тираж 100 экз. Заказ № Л 5 5.

Воронежский институт МВД России 394065 Воронеж. Проспект Патриотов, 53

Введение.

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

1.1. Основные направления цифровой обработки изображений.

1.2. Методы сжатия графической информации.

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

1.4. Выводы и задачи исследования.

Глава 2. Развитие теоретических подходов к построению математической модели процесса сжатия графической информации.

2.1. Математическая модель растрового полутонового изображения

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

2.3. Обоснование возможности коррекции полиномов Хаара при сжатии графической информации.

2.4. Получение условий для двоичного разложения двумерного пространства ВМО.

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

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

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

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

АЛ. Разработка алгоритмов сжатия и восстановления графической информации на основе преобразования Хаара.

4.2. Состав и назначение программного пакета «Компрессор графических файлов».

4.3. Экспериментальное исследование возможностей компьютерной модели и подтверждение теоретических основ математической модели процесса сжатия графической информации.

4.4. Моделирование передачи данных методом «стопка книг».

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

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

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

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

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

РФ в рамках исследований, проводившихся согласно тематическому плану НИР института по теме «Компьютерное сжатие изображений» (№ госрегистрации 01.9.80 0 02337) и в рамках Договора № 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) При больших степенях сжатия изображение имеет блочную структуру, что связано как с разрывностью самих функций Хаара, так и с тем фактом, что в соответствии с алгоритмом изображение разбивается на блоки 8x8 пикселей (по аналогии с JPEG), каждый из которых сжимается независимо. Даже использование одномасштабных всплесков Хаара вместо прямого произведения одномерных систем Хаара и переход от независимого сжатия отдельных блоков к сжатию всего изображения в целом не избавляет от мозаичности. Для устранения мозаичности в методе JPEG используются процедуры сглаживания на границах блоков. Лучшее решение этой проблемы состоит в отказе от всплесков Хаара в пользу «гладких» всплесков.

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

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

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

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

91

1. Александров В.В., Горский Н.Д. Представление и обработка изображений: Рекурсивный подход. Л.: Наука, 1985. 192 с.

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

3. Ахмед Н, Pao K.P. Ортогональные преобразования при обработке цифровых сигналов. М: Связь, 1980. 248 с.

4. БариН.К. Тригонометрические ряды. М.: Физматгиз, 1961. 936 с.

5. Бахвалов Н.С. Численные методы. Т. 1. М.: Наука, 1973. 631 с.

6. Бердышев В.И., Петрак Л.В. Аппроксимация функций, сжатие численной информации, приложения. Екатеринбург: УрО РАН, 1999. 298 с.

7. Боуз Р.К., Рой-Чоудхури Д.К. Об одном классе двоичных групповых кодов с исправлением ошибок // Кибернетический сборник. № 2. М.: ИЛ, 1961.

8. Быков В., Биркмайер С. Основные положения кодирования видеосигнала по стандарту MPEG-2 // Техника кино и телевидения. 1996. № 12.

9. Гарнет Дж. Ограниченные аналитические функции. М.: Мир, 1984. 469 с.

10. Гинзбург В.М. Формирование и обработка изображений в реальном времени: Методы быстрого сканирования. М.: Радио и связь, 1986. 232 с.

11. Голубов Б.И., Ефимов A.B., Скворцов В.А. Ряды и преобразования Уолша: Теория и применения. М.: Наука, 1987. 344 с.

12. Горлов С.К., Корыстин A.B., Родин В.А. Об одной реализации метода сжатия изображений с помощью нелинейной аппроксимации сумм Фурье-Хаара // Тез. докл. науч.-практ. конф. ВВП! МВД РФ. Воронеж: Изд-во ВВШ МВД РФ, 1994. С. 8-9.

13. Горлов С.К. О рядах с положительными частными суммами по мультипликативным системам функций // Тез. докл. науч.-практ. конф. ВВШ МВД РФ. Воронеж: Изд-во ВВШ МВД РФ, 1995. С. 7-8.

14. Горлов С.К. О рядах с положительными частными суммами по системе Уолша // Алгебраические, вероятностные, геометрические, комбинаторные и функциональные методы в теории чисел: Тез. докл. II Международ, науч. конф. Воронеж: Изд-во ВГУ, 1995. С. 44.

15. Горлов С.К., Родин В.А. О практической реализации метода сжатия графической информации // Тез. докл. науч.-практ. конф. ВВШ МВД РФ. 4.2. Воронеж: Изд-во ВВШ МВД РФ, 1996. С. 74.

16. Горлов С.К. Моделирование на ЭВМ передачи данных методом "стопка книг" // Современные проблемы информатизации: Тез. докл. II Республ. электронной науч. конф. Воронеж: Изд-во ВПУ, 1997. С. 134-135.

17. Горлов С.К. Об одном алгоритме равномерной передачи видеоданных // Сб. науч. тр. ВВШ МВД РФ. Вып.4. Воронеж: Изд-во ВВШ МВД РФ, 1997.

18. Горлов С.К. Использование двумерных рядов по системе Хаара для представления и обработки видеоданных // Тез. докл. науч.-практ. конф. ВВШ МВД РФ. 4.2. Воронеж: Изд-во ВВШ МВД РФ, 1997. С. 6-7.

19. Горлов С.К. К вопросу о коррекции искажений при сжатии графической информации // Тез. докл. науч.-практ. конф. ВВШ МВД РФ. 4.2. Воронеж: Изд-во ВВШ МВД РФ, 1997. С. 92.

20. Горлов С.К. О возможности использования нормы пространства ВМО для оценки степени сжатия информации // Тез. докл. науч.-практ. конф. ВВШ МВД РФ. 4.2. Воронеж: Изд-во ВВШ МВД РФ, 1998. С. 7-8.

21. Горлов С.К., Родин В.А. О коррекции нелинейной аппроксимации двумерных рядов Хаара для сжатия информации // Вестник ВВШ МВД РФ. Воронеж: Изд-во ВВШ МВД РФ, 1998. № 2, С. 41-45.

22. Горлов С.К., Родин В.А. Двоичное разложение двумерного пространства ВМО // Сб. науч. тр. математического факультета ВГУ. Воронеж: Изд-во ВГУ, 1998. Вып.З. С. 44-48.

23. Горлов С.К., Родин В.А. О коррекции полиномов Хаара, связанных с обработкой графической информации // Современные проблемы теории функций и их приложения: Тез. докл. 10-й Саратовской зимней школы. Саратов: Изд-во Саратовского ун-та, 2000. С. 35.

24. Горшков A.C. Быстрый теоретико-числовой метод для синтеза и сжатия изображений //Программирование. 1992. № 4. С. 72-78.

25. ГОСТ 26320. Оборудование телевизионное студийное и внестудийное. Методы субъективной оценки качества цветных телевизионных изображений.

26. Ефимов A.B., Поспелов A.C., Умняшкин C.B. Применение преобразований Крестенсона-Леви в задачах цифровой обработки информации // Функциональные пространства, теория приближений, нелинейный анализ: Тез. докл. Международ, науч. конф. М., 1995. С. 125-126.

27. Ефимов A.B., Поспелов A.C., Умняшкин C.B. Некоторые свойства мультипликативных ортонормированных систем, используемые в цифровой обработке сигналов // Труды математического института им. В.А.Стеклова РАН. Т. 219. 1997. С. 137-182.

28. Залманзон JI.A. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. М.: Наука. 1989. 493 с.

29. Зигмунд А. Тригонометрические ряды. М.: Мир, 1965. Т. 1. 524 с.

30. Зигмунд А. Тригонометрические ряды. М.: Мир, 1965. Т. 2. 537 с.

31. Игнатьев Н.К. К доказательству теоремы Котельникова / Сб. трудов Гос. НИИ Мин. Связи СССР, 1960. Вып. 2 (20). С. 3-5.

32. Кашин Б.С., Саакян A.A. Ортогональные ряды. М.: Наука. Главная редакция физико-математической литературы, 1984. 496 с.

33. Коллатц JI. Функциональный анализ и вычислительная математика. М: Мир, 1969. 448 с.

34. Колмогоров А.Н., Фомин C.B. Элементы теории функций и функционального анализа. М: Наука. Главная редакция физико-математической литературы, 1972. 496 с.

35. Котельников В.А. Теория потенциальной помехоустойчивости. М.: ГЭИ, 1956.

36. Красносельский М.А., Рутицкий Я.Б. Выпуклые функции и пространства Орлича. М.: Государственное издательство физико-математической литературы, 1958. 272 с.

37. Кричевский P.E. Сжатие и поиск информации. М.: Радио и связь, 1989. 168 с.

38. Лабунец В.Г. Алгебраическая теория сигналов и систем: Быстрое многомерное преобразование Фурье. Свердловск: Изд-во Уральского ун-та, 1989. 195 с.

39. Лебедев Д.С., Пийль Е.И. Экспериментальное исследование статистики телевизионных сообщений // Техника кино и телевидения. 1959. № 3. С. 37.

40. Люстерник Л.А., Соболев В.И. Элементы функционального анализа. М: Наука. Главная редакция физико-математической литературы, 1965. 520 с.

41. Марчук Г.И. Методы вычислительной математики. М.: Наука, 1989. 608 с.

42. МККР. Метод субъективной оценки качества телевизионных изображений. Рекомендация 500-1. Киото, 1978.

43. МККР Субъективная оценка качества телевизионных изображений. Отчет 405-2. Киото, 1978.

44. Моделирование методов группового кодирования изображений / Б.М.Кац, Л.И.Миркин, С.В.Сардыко, И.И.Цуккерман // Техника средств связи. Сер. Техника телевидения. 1977. Вып. 4. С. 61-70.

45. Мультипликативные системы функций и гармонический анализ на нульмерных группах / Г.Н.Агаев, Н.Я.Виленкин, Г.М.Джафарли, А.И.Рубинштейн. Баку: Элм, 1981.

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

47. Натансон И.П. Теория функций вещественной переменной. М.: Наука, 1974. 480 с.

48. Новиков И.Я., Стечкин С.Б. Основные конструкции всплесков // Фундаментальная и прикладная математика. 1997. Т. 3. № 4. С. 999-1028.

49. Овсепян Р.И. О представлении функций ортогональными рядами // Айкакан ССР Гитутюннери Академиа. Зейкуцнер: Докл.АН АрмССР. 1973. Т. 57. № 1. С. 3-8.

50. Певзнер Б.М. Качество цветных телевизионных изображений. М.: Радио и связь, 1988. 222 с.

51. Перов В.П. Прикладная спектральная теория оценивания. М.: Наука. Главная редакция физико-математической литературы, 1982. 432 с.

52. Прэтт У. Цифровая обработка изображений. Т. 1, Т. 2. М.: Мир, 1982.

53. Родин В. А. Сильные средние и осцилляция рядов Фурье по мультипликативным системам//Математические заметки. 1998. Т. 63. Вып. 4. С. 607-616.

54. Романов В.Ю. Популярные форматы файлов для хранения графических изображений на ЮМ PC. М.: Унитех, 1992. 156 с.

55. Рябко Б.Я. Сжатие данных с помощью стопки книг // Проблемы передачи информации. 1980. Т. 16. № 4. С. 16-21.

56. Самарский A.A., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978. 592 с.

57. Скляров B.C. Математические модели информационных систем. Учебник. Харьков, 1989. 480 с.

58. Соболь И.М. Точки, равномерно заполняющие многомерный куб. М.: Знание, 1985. 32 с.

59. Соболь И.М. Многомерные квадратурные формулы и функции Хаара. М.: Наука, 1969. 288 с.

60. Старовойтов В.В. Локально-геометрические методы цифровой обработки видеоданных: Автореф.дис. . д-ра техн.наук / Минск, 1999. 44 с.

61. Стейн И. Сингулярные интегралы и дифференциальные свойства функций. М.: Мир, 1973. 342 с.

62. Умняшкин С.В. Алгоритм кластеризации коррелированных данных // VII Международ, конф. Математика. Экономика. Экология. Образование. Международ, симпозиум. Ряды Фурье и их приложения: Тез. докл. / Рост.гос. эконом.акад. Ростов н/Д., 1999. С. 211-212.

63. Федер Е. Фракталы: Пер. с англ. М.: Мир, 1991. 260 с.

64. Федунин В. Сжатие видеоинформации в цифровых системах телевизионного вещания //Радио. 1998. № 10. С.94-96.

65. Фомин А.Ф. Анализ методов и международных рекомендаций по сжатию изображений: Обзор. Электросвязь. № 5. 1994. С. 16-19.

66. Хэмминг Р. Коды с обнаружением и исправлением ошибок. М.: ИЛ, 1956.

67. Цифровая обработка телевизионных и компьютерных изображений / Под ред. Ю.Б. Зубарева и В.П. Дворковича. М., 1997. 216 с.

68. Цифровое кодирование телевизионных изображений / И.И.Цуккерман, Б.М.Кац, Д.С. Лебедев и др.; Под ред. И.И. Цуккермана. М.: Радио и связь, 1981.240 с.

69. Цифровое телевидение / Под ред. М.И.Кривошеева. М.: Связь, 1980. 263 с.

70. Шеннон К. Математическая теория связи // Работы по теории информации и кибернетике: Пер. с англ. / Под ред. Р.Д.Добрушина и С.Б.Лупанова. М.: Л.:, 1963. С. 243-332.

71. Юдин В.А. О тригонометрических рядах с положительными частными суммами//Математические заметки. 1993. Т. 53. Вып.З. С. 149-152.

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

73. Brislawn С. Fingerprints Go Digital // Notices of the AMS. 1995. Vol. 42. № 11. P. 1278-1283.

74. Chui C.K. An introduction to wavelets. New York: Academic Press, 1992. 290 p.

75. Chui C.K., Stocker J., Ward J.D. Compactly supported Box-Spline wavelets // Approxim. Theory and Its Appl. 1992. Vol. 8, № 3, P. 77-100.

76. ISO/IEC DIS 10918-1. Information Technology Digital Compression and Coding of Continuous-tone Still Images. Part 1: Requirements and Guidelines/Ed. 1, JTS 1/ SC 29, 1994.

77. ISO/IEC DIS 10918-2. Information Technology Digital Compression and Coding of Continuous-tone Still Images. Part 2: Compliance Testing/Ed. 1, JTS 1/ SC 29, 1994.

78. ISO/IEC DIS 10918-3. Information Technology Digital Compression and Coding of Continuous-tone Still Images. Part 3: Extensions/Ed. 1, JTS 1/ SC 29, 1994.

79. Fefferman Ch. Hp space of several variables//Acta Math. 1972. Vol. 129. № 3-4. P. 137-193.

80. Fractal Image Compression. Theory and Application / Ed. Y. Fisher. New York: Springer-Verlag, 1995.

81. Frazier M., Jawerth B., Weiss G. Littlewood-Paley Theory and the Study of Function Spaces // CBMS Reg. Conf. Ser. Math. 1991. № 79. 132 p.

82. Haar A. Zur Theorie der orthogonalen Funktionen-systeme // Math. Ann. 1910. Vol. 69. P. 331-371.

83. Katznelson Y. Trigonometrie series with positive partial sums //Bull. Amer. Math. Soc. 1965. Vol. 71. P. 718-719.

84. Mallat S. Multiresolution approximation and wavelet orthonormal bases of L2(R) //Trans. Amer. Math. Soc. 1989. V. 315. P. 69-87.

85. Massopust PR. Fractal Functions, Fractal Surfaces and Wavelets. New York: Academic Press, 1994.

86. MPEG: A Video Compression Standard for Multimedia Applications / Didier Le Gall. Communications of the ACM. 1991. Vol. 34. № 4.

87. Netravali A.N., Haskell B.G. Digital Pictures: Representation and Compression. New York: Plenum Press, 1988.

88. Pal L.G., Schipp F. On Haar and Schauder series //Acta. sei. math. 1970. Vol. 31. № 1-2. P. 53-58.

89. Shipp F. Uber Walsh-Fourierreihen mit nichtnegativen Partialsummen //Ann. Univ. scient, budapest. Sec. math. 1969. Vol. 12. P. 43-48.

90. The JPEG Still Picture Compression Standard / Communications of the ACM. 1991. Vol. 34, №4.

91. Video codec for audio visual services at p x 64 kbits/s. CCITT Recomendation H.261. 1990.

92. Преобразование палитры в оптимизированную "градации серого" */1. Файл GRAYUP.C */include "video.h"void main(int argc, char *argv.) {

93. PCXHEADER pcxheader; unsigned char m 1 ,m2=0x 13, b,p=0, c,c0-0xC0, count 1=0; FILE *pictl, *pict2; char * fnamel,fname2256., *cur;unsigned char line800.,pal768.; unsigned long 1, count2=0L; unsigned int i=0,k,n,tail;printf(

94. Grayscale Palette Optimizer for Pictures Saved as PCX Files\n"); printf(

95. Data Compressor for 320x200 GrayScale Pictures Saved as PCX Files\n"); printf(

96. Copyright by Gorlov S.K., Voronezh, Russia, 1998 ***\n"); printf("\n"); if (arge < 3) printf(

97. GetNxNScr(l*N,k*N); /*Считывание в массив f строки */пикселов из клетки (1,к) */ CalcHaarCoef(eps); CalcHaarSum(c,f); PutNxNScr(l*N,k*N);

98. Прямое и обратное преобразования Фурье-Хаара */1. Файл HLAAR. H */void CalcHaarCoef(unsigned long eps);char Quant(long cO, unsigned long level);void CalcHaarSum(char c.[N], unsigned char f[][N]);