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

ТОМСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ

2 3 ДПР На правах рукописи

Ульянов Владимир Николаевич

УДК 621.391.25:621.397.2

Виутрикадровое кодирование изображений в телевнзионио-вычислительиых системах

Специальность 05.12.17 - радиотехнические и телевизионные системы и

устройства

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата технических наук

Томск 1996

-2. Работа выполнена на кафедре телевизионных устройств Томской госу дарственной академии систем управления и радиоэлектроники.

Ведущее предприятие: ПИИ ОС, г. Новосибирск

Зашита состоится 28 мая 1996 г. в 9 часов на заседании днссертационнс го совета Д 063.05.02 Томской государственной академии систем управлени и радиоэлектроники (ТАСУР). (Адрес: 634050, г. Томск, пр. Ленина 40)

С диссертацией можно ознакомиться в библиотеке ТАСУР.

Автореферат разослан " М " 1996 г.

Ваши отзывы в двух экземплярах, заверенные печатью, просим напра] лять в адрес академии учёному секретарю.

Учёный секретарь диссертационного

Научные руководители: доктор технических наун

профессор Пустынскнн И.И кандидат технических наук, дс цент Курячий М.И.

Официальные оппоненты: доктор технических нау»

зав. лаб. СТЗ Сырямкин В.И кандидат физ.-мат. наук, в.н.( Института оптики атмосфер! СОРАННадеев А.И.

совета к.т.н., доцент

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

Актуальность работы. Изображение - самая естественная для человеку |юрма представления информации. Поэтому не удивительно, что сфера при-1енения изображений в различных предметных областях чрезвычайно ши-юка. Технология обработки изображений в своём быстром поступательном шижении с успехом преодолела множество препятствий, но один серьёзный >арьер пока остаётся - это огромные размеры файлов, содержащих изобра-кения. Так для хранения одног.о телевизионного кадра вещательного стан-юрта разложения требуется около 0,5 Мбайт, а цифровое изображение экра-ia монитора графической станции SUN SPARCstaiion занимает 3,8 Мбайт. Ещё большего объёма памяти требуют изображения, вводимые при помощи 1ветных сканеров. Для хранения цветной картинки размером 216 х 279 мм с разрешением 300 точек/дюйм требуется 25,4 Мбайт памяти. На передачу такого файла по каналу связи со скоростью 9600 бит/с потребуется более 5 lacoB.

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

В настоящее время крупные иностранные фирмы и государственные уч-эеждения (Intel, C-Cube Mycrosystem, Compuserve, Kodak, NASA, FBI и др.) :оздают собственные программные и аппаратные средства сжатия видеоинформации, а также организуются международные комитеты и группы (JPEG, MPEG) для разработки и внедрения эффективных методов компрессии ви-1еоинформации.

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

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

Теоретические основы кодирования изображений хорошо развиты и с лещены в многочисленных работах отечественных и зарубежных авторов, ним в первую очередь следует отнести работы H.H. Красильникова, М. Крипошеева, И.И. Цуккермана, А. Нетревали, А. Джайн, У. Прэтта.

Задача сжатия изображений решается или в пространстве оригинала и. в пространстве образа некоторого ортогонального преобразования. В пс вом случае метод сжатия называется кодированием с предсказанием, во вт ром - кодированием с преобразованием. Начиная с 80-х годов и по сег дняшний день, основные усилия в мире были направлены на развитие мет дов кодирования с преобразованием. Апробировались новые ортогональн преобразования - Карунена-Лоэва, Wavelet Transform.

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

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

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

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

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

Научная новизна результатов работы заключается в следующем:

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

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

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

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

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

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

Реалнзация и внедрение результатов исследовании. Результаты диссертационной работы использованы при создании пр граммного обеспечения для устройств ввода, обработки, передачи и xpai ния изображений, разработанных в ходе выполнения хоздоговорных и г< бюджетных работ, проводимых на кафедре "Телевизионные устройств ТАСУР. Полученные результаты и разработанные алгоритмы нашли при» нение и внедрение в научно-исследовательских работах и опыт! конструкторских разработках на предприятиях: ЦНПО "Комета" г. Mocki НПО "Астрофизика" г. Москва, НПО "Геофизика" г. Москва, Томен ГТРК, СМЭУ ГАИ Томского УВД. Результаты диссертационной работь инструментальные средства, созданные в ходе работы над диссертацн-использованы в учебном процессе в лекциях и лабораторно-практическ занятиях по дисциплинам "Цифровая обработка сигналов" "Телевизионно-вычислительные измерительные системы".

Апробация результатов. Основные положения диссертационной рабо докладывались и обсуждались на:

1. Всесоюзном совещании "Координатно-чувствительные фотоприёмник! оптико-электронные устройства на их основе". Барнаул, 1987.

2. XXX научно-технической конференции молодых учёных и специалист по телевизионной технике. Ленинград, 1989.

3. Республиканской научно-технической конференции "Телевизионные тоды и средства в науке и технике", Ужгород, 1989.

4. Международной конференции "Обработка изображений и дистанции ные исследования". Новосибирск, 1990.

5. Семинаре "Теория и практика создания систем технического зрени Москва, 1990.

6. Межреспубликанской научно-технической конференции "Обработка р тровых изображений в автоматических системах", Тула, 1991.

7. Международной конференции "Датчики электрических и неэлектрнчеа величин", Барнаул, 1993.

8. Международной конференции "CERA 94", Питсбург, США, 1994.

Публик-аини. По результатам диссертационной работы опубликован печатные работы, 10 тезисов докладов, сделанных на конференциях, пол> но 1 авторское свидетельство.

Структура и объём диссертации. Диссертационная работа состоит введения, пяти разделов, заключения, списка литературы, приложения и тоь ьнедрення. Она состоит из 139 страниц, включая 4 таблицы и 41 иллк рацию, а также список литературы из 73 наименований.

Оснопиме положении, представляемые к защите:

Рекуррентное выражение для расчёта интервалов квантования показательно распределённых отсчётов сигнала, применение которого, в отли--чие от квантователя Макса, не требует дополнительного описания границ интервалов.

Алгоритм дискретизации декоррслиронанных отсчётов изображения, не искажающий края достаточно контрастных деталей.

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

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

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

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

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

Содержание диссертационной работы.

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

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

Отмечено, что для изображений свойственны три вида избыточности, рошо поддающиеся анализу:

корреляционная избыточность, обусловленная линейной изотропной зависимостью соседних отсчётов;

2) избыточность, обусловленная анизотропными и нелинейными соста! ляющими изображений - текстуры, перепады яркости и контура;

3) избыточность, обусловленная неравномерностью распределения значен отсчётов.

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

На основании проведённого анализа ставятся задачи, подлежащие р работке.

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

Первичная (искажающая) часть алгоритма кодирования ' Управление качеством

\ /

Квантователь Дискретизация

Предсказатель

Рис. 1

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

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

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

4(М)

Рис. 2

Так как из случайной величины Вх,у вычитается детерминированная >х , множество значений разности {Д^} можно разместить в замкнутом в

эльцо множестве оригинала {Вху}. Тогда выражения для процедур декорре-¡шии и восстановления сигнала примут вид

При декорреляции изображения: При восстановлении изображения:

Д<А,) = Л/, м 2 ' В,,у = \вх,у + - ДтШ|Л/ + вт1п.

*е | А'| а, означает взятие по модулю Л/, а М = Втях - +1-еперь {д<« )} распределена в пределах от -МП до М/2.

Уровни квантования, обеспечивающие минимальную среднеквадратиче-<ую ошибку квантования, могут быть рассчитаны, используя итерационный пгоритм Макса. Алгоритм Макса требует дополнительные расходы для эхранения значений уровней квантования, большое количество итераций ля показательных распределений и сложен в реализации для дискретных аспределений. В разделе получено рекуррентное выражение для расчёта нтервалов квантования показательно распределённых отсчётов сигнала:

а \'а V«

где а параметр показательного распределения Р(д') = а-е'а х ■ Задавшись значением первого (наиболее вероятного) интервала квантован Д|, рассчитываются остальные. Последний (наименее вероятный) интерв квантования Д^ будет меньше либо равен оптимальному значению, что существенно ввиду малой вероятности попадания в этот интервал значен квантуемого отсчёта. Число интервалов N получается неопределённым, ч тоже вполне приемлемо при условии программной реализации дальнейше энтропийного кодирования.

Блок дискретизации прореживает (приравнивает к нулю) ошибки пр< сказания, модуль которых не превышает некоторого порога. На гладк участках изображения, где присутствует только линейная компонента, кол рование-декодирование выполняется полагаясь на работу пpeдcкaзaтeJ изредка подправляемого в узловых точках. При кодировании отсчёта, пр надлежащего контуру - нелинейной компоненте, модуль ошибки предска: ния превышает порог и в точке перепада формируется узел с точным зна1 нием изменения яркости. Таким образом, дискретизация осуществляете» неравномерным шагом адаптивно к содержимому изображения - внос искажения между достаточно контрастными деталями изображения и не I меняет их края.

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

(!4

к + 3„ .+ и'

.при <5К 0

8* »<0

п ри к*к„

Г"1 .ПР»

+ 3

тах в

¿к »<0

при к~кп

где &> - значение квантуемого отсчёта превысившего порог и-', к - чш пропущенных отсчётов, М - модуль кольца {&•}.

:им образом, кольцо возможных значений {&.} преобразуется в ираль" {г}, где каждый шаг "спирали" означает один пропущенный от-г, а модуль каждого витка спирали равен М - 2-н\

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

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

Вторичная (неискажающая) часть алгоритма кодирования

Рис. 3

После декорреляции и приведению к показательному распоеделению этировке) отсчёты представляют собой линейно независимые удвоец-: модули ошибок предсказания. После дополнительной дискретизации с авномерным шагом сигнал утрачивает связь с отсчётами из предыдущей оки изображения и становится одномерным. Последовательность отсчё-{£} следует рассматривать как одномерный, нестационарный показа-ьно распределённый процесс с переменной дисперсией, зависящей от рас-южения кодируемого отсчёта в растре

РЦк) = а(к)-е-а{к)*.

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

следовательность отсчётов можно рассматривать как цепь Маркова, пол стыо характеризуемую матрицей вероятностен переходов P(£k=i,4k-i=J) состояния j в состояние /'. Оптимальное кодирование цепи Маркова треб построения и передачи (или сохранения) набора кодовых таблиц для и возможных значений j предыдущего отсчёта. Об.ъём дополнительных рас дов, при этом, может превысить объём кодируемых данных.

В целом условные распределения /Ч&-' /&./=j) похожи на показатель! и друг на друга, за исключением некоторых несогласных элементов -кальных минимумов и максимумов. Эти несогласные с общим видом уел ного распределения элементы несут в себе информацию о нелинейной вза ной зависимости декоррелированных отсчётов изображения. Предло: алгоритм табличного преобразования Т„, который используя координ; несогласных элементов в матрице, нормализует условные распределе! преобразуя нелинейно взаимозависимые отсчёты в независимые. В резул! те условные распределения приобретают однообразный вид, нелиней взаимная зависимость исчезает, а обусловленная ею избыточность преоС зуется в энтропийную.

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

Д,„ /Ып2

—ш->-,

m tij

д„.

где —— - относительное изменение математического ожидания в результ;

m

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

Нормализованные условные распределения имеют близкую к пок тельной форму и отличаются друг от друга шириной и дисперсией. Ann; симация условных распределений фрагментом показательной функции зволяет избежать расходов на описание таблицы (или графа) кодов с г менной длиной. Малый объём (~4 бит) необходимый для задания пара ров аппроксимирующего распределения позволяет кодировать нормал ванную цепь Маркова несколькими таблицами, переключая их в завис! сти от значения предыдущего отсчёта, как это показано на рис 3.

Получена статистика над выборочным распределением, оптима] оценивающая параметр показательного аппроксимирующего распределе так что обеспечивается минимальная средняя длина кодовых слов, постр ных по аппроксимирующему распределению и применённых к выборочн«

!п

1+ «

Ч

тпроксимирующее распределение р можно записать в виде геометриче-ой прогрессии 1

I ( т

т +1 ч/н + 1

к

ыо

е т = Т/.Л = — - математическое ожидание аппроксимируемого распре-

I а .

ления {Р,}.

: всегда выгодно аппроксимировать условные распределения показатель-||м законом. В случае небольшого наклона (асимметрии) распределения или

0 малой ширины, для аппроксиммации целесообразно использовать рав->мсрное распределение. Распределение {/>,} аппроксимируется показатель-.1М распределением, если выполняется условие

З-Я-Р, <1 -1, где I - ширина распределения,

/

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

Для последовательностей, не обладающих свойством марковости - це-:й Маркова более чем первого порядка, следует применять методы группо->го кодирования, где исходный алфавит дополняется новыми символами, Зозначающимн группу исходных символов. Группу символов выгодно за-:нять новым символом лишь при достаточном числе повторений группы, олучен критерий целесообразности замены группы символов одним.

Отличительной особенностью цепей Маркова более чем первого поряд-

1 является нестационарность. Нестационарность проявляется з непостоян-зе не только дисперсии, но и степени и порядка зависимости данных. Не-"ационарность последовательностей мешает принимать статистически Зоснованные решения, что осложняет применение статистических методов эмпрессии. Решением этой проблемы может быть сегментация данных на эласти со схожими статистическими свойствами. Предложена структура

N

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

В четвёртом разделе приведены технические решения (приёмы програ мирования) обеспечивающие высокую производительность программы » дирования изображений. Высокая производительность достигается за с1 табулирования функциональных преобразований, использования высо1 производительных инструкций процессора, минимизации вероятности ве' лений и максимального использования конвейеризации и предварительн выборки команд процессора. Приведено распределение времени выполне» процедур, реализующих алгоритм кодирования изображений. Произво; тельность алгоритма в целом зависит от характеристик компьютера. 1 изображения 256 х 256 х 8 бит кодируются на компьютере с процессор ¡80286, 10 МГц за 4 - 6 секунд, а на компьютере с процессором ¡80486D менее чем за секунду.

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

Предложенный алгоритм квантования сравнивался с квантовате; Макса и квантователем с равномерной сеткой квантования. Получены за симости среднего квадрата ошибки квантования от энтропии квантован»! отсчётов для указанных методов.

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

Приведены сравнительные характеристики эффективности и произво тельности кодирования предлагаемого алгоритма и известных, таких i JPEG, HS1 JPEG и GIF в режиме кодирования без потерь. Часть сравните ных характеристик и изображения на которых они были получены приве ны на рис. 4 и 5, из которых видно, что в режиме кодирования без пот предложенный алгоритм сжимает реальные изображения в 1,25 + 1,8 плотнее чем алгоритм GIF, а в режиме кодирования с потерями при рав» среднеквадратических искажениях в области малых искажении (незамет» для (лаза) предложенный алгоритм всегда превосходит по коэффицие сжатия алгоритм JPEG на 20 + 30 %. Причем преимущество предложен»! алюритма теи значительнее, чем выше детальность кодируемого изобра

ПИЯ.

Кодируемые изображения

а) изображение "Портрет"

б) изображение "Отпечаток пальца" Рис. 4

Сравнение эффективности кодирования изображений

, -А'|>*

---ЛЧ.Ч

— • — • //Л/л-к,

А 07/

5 10 15 20 25 30 С (кгдмин киадрл искажений

5 10

Средний гкалрлт искаженин

а) для изображения "ИорфсГ'

б) для изображения "Отсчаюк пальца"

Рис. 5

Предложенный алгоритм кодирования изображений на рис. 5 обозначен КчИ.

^Заключении сформулированы основные результаты работы, приведён-ниже.

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

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

2. Получено рекуррентное выражение, которое позволяет рассчитать гр цы интервалов квантования отсчётов показательно распределённого нала. Эксперименты показали, что при равной энтропии квантова» отсчётов, среднеквадратическая ошибка квантования предложенной горитма на 20 + 40 % меньше ошибки квантователя с равномерной се и на 12+ 16% больше ошибки оптимального квантователя Макса.

3. Предложен алгоритм дискретизации декоррелированных отсчётов бражения не искажающий края достаточно контрастных деталей. / ритм прореживает отсчёты между деталями изображения, оставля; изменений края деталей. Применение дискретизации позволяет дос больших коэффициентов сжатия - в 10 + 20 раз, что было невозмо» классической схеме кодирования с предсказанием.

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

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

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

гшзация и кодирование несколькими таблицами декоррелнрованных изображении эффективней обычного энтропийного кодирования на 2 + 3 %. Для данных с более выраженными нелинейными свойствами преимущество предложенного алгоритма относительно кодирования одной таблицей может достигать 15 % и более.

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

Получена статистика над выборочным распределением, оптимально оце-1ивающая параметр показательного аппроксимирующею распределения, гак что обеспечивается минимальная средняя длина кодовых слов, покоенных по аппроксимирующему распределению и применённых к вы-5орочному. Аппроксимация строк нормализованной матрицы переходах вероятностей и малый объём данных 4 бит), необходимый для за-1ання параметров аппроксимирующего распределения, сделали возможем кодирование нормализованной цепи Маркова несколькими табли-1ами.

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

)бщий эффект от применения перечисленных выше теоретических и тех-шческих решений отражён в сравнительных характеристиках предложен-юго алгоритма кодирования изображений с известными. Проведённые на руппе разнородных реальных и искусственных изображениях испытания ¡оказали, что в режиме кодирования без потерь предложенный алгоритм жимает реальные изображения в 1,25 + 1,8 раз плотнее чем алгоритм GIF, на искусственных изображениях GIF превосходит предложенный алго-итм в 1,1 + 1,3 раза.

! режиме кодирования с потерями при равных среднеквадратических скажениях в области малых искажений (незаметных для глаза) предло-:енный алгоритм всегда превосходит по коэффициенту сжатия алгоритм PEG на 20 ч- 30 %. Причём преимущество предложенного алгоритма тем иачительнее, чем выше детальность кодируемого изображения, [оказано, что предложенный алгоритм более тщательно кодирует края еталей изображения за счёт менее точного представления фона и точнее эспропзводит исходное распределение значений яркости.

11.Сравнение производительности предложенного алгоритма с известш показало, что предложенный алгоритм кодирует без потерь в 1,8 раза стрее чем GIF, а с потерями в 1,7 раза быстрее чем JPEG. Декоди] предложенный алгоритм 1,1 раза быстрее чем GIF и в 2,6 раза быстрее JPEG.

12. Полученные результаты и разработанные алгоритмы нашли прнмен и внедрение в научно-исследовательских работах и опы конструкторских разработках, проводимых на кафедре "Телевизио! устройства" ТАСУР, на предприятиях: ЦНПО "Комета" г. Москва, I "Астрофизика" г. Москва, НПО "Геофизика" г. Москва, Томская П СМЭУ ГАИ Томского УВД. Результаты диссертационной работы и \ рументальные средства, созданные в ходе работы над диссертацией пользованы в учебном процессе в лекциях и лабораторно-практиче занятиях по дисциплинам "Цифровая обработка сигналов' "Телевизионно-вычислительные измерительные системы".

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

цель диссертационной работы достигнута.

По материалам диссертации опубликованы следующие работы:

1. Ильин А.Г., Костевич А.Г., Курьяновнч Е.Я., Ульянов В.Н. Сравни ная характеристика алгоритмов выделения малоразмерных объекте сложном фоне. - Томск, 1987, - 13 с. - Рукопись представлена Том институтом АСУ и радиоэлектроники. Деп. в ВНИИТР 24.01.87, Кя 2 87.

2. Курячий М.И., Курьянович Е.Я., Парыгии Ю.П., Ульянов В.Н. Вы производительные алгоритмы дискриминировать малоразмерных лей в телевизионном изображении. - В кн.: Тезисы докладов четвё] Всесоюзного совещания "Координатно-чувствительные фотоприёмн! оптико-электронные устройства на их основе". Барнаул, 1987, ч. II, < 40.

3. Ульянов В.Н. Алгоритмы измерения координат множества объек повышенной разрешающей способностью. - В кн.: Тез. докл. XXX но-технической копференции молодых учёных и специалистов по те зионной технике. Москва, 1989, с. 53 - 55.

4. Ульянов В.Н., Курячий М.И., Казанцев Г.Д. Межкадровая обра) видеоинформации с предварительным кодированием данных. - В кн докл. Республ. конф. "Телевизионные методы и средства в науке и з ке". Ужгород, 1989, с. 107-108.

5. Парыгин Ю.П., Епифанцев Л.П., Костевич А.Г., Курячий М.И., Ул В.Н. Моделирующие и стендовые средства для разработки и исследо телевизионных измерительных систем. - В кн.: Тез. докл. Междунар«

коиференции "Обработка изображений и дистанционные исследования". Новосибирск, СО АН СССР, I990, с. 169 -171.

Курячий М.И., Ульянов В.Й., Елнфаицев Л.П. Обнаружение деталей изображения и измерение их координат по децнмированной видеоинформации. В кн.: Материалы семинара "Теорий и Практика создания систем технического зрения". Москва, 1990, с. 37-41.

A. с. 1702401 СССР. Устройство для обработки изображений объектов. /

B.Л.Дмнтриенко, А.Г. Костевич, М.И. Курячий, В.Н.Ульянов. // Б.И. 1991. № 48.

Ульянов В.Н., Епифанцев Л.П., Костевич А.Г., Курячий М.И. Алгорит-мическо-программное обеспечение Телевизионных измерительных систем. // Тез. докл. Межреспубл. науч.-техн. конф. "Обработка растровых изображений в автоматических системах". Тула, 1991, с. 21-24. Дементьева Г.В., Костевич А.Г., Курячий М.И., ПусТынский И.Н., Ульянов В.Н. Исследование возможностей использования изображений радужной оболочки глаза для определения личностных характеристик. Деп. в ВИНИТИ' 22.06.93, Ks 1740-В93.

Карнющенко A.B., Костевич А.Г., Курячий М.И., Ульяной В.Н. Автоматизированное рабочее место для исследования алгоритмов распознавания номеров вагонов//Тез. докл. 1-ой Междунар. конф. "Датчики электрических и неэлектрических величин". Барнаул, 1993.4.II. Костевич А.Г., Курячий М.И., Ульянов В.Н. Система динамического моделирования элементов оптико-электронных следящих систем на ПЭВМ.' И Тез. докл. 1-ой Междунар. конф. "Датчики электрических и «¿электрических величин". Барнаул, 1993, Ч. II.

Костевич А.Г., Курячий М.И., Ульянов В.Н. Телевизионные программно-реализуемые координаторы для информационно-измерительных систем, используемых в аэрокосмической иромышленноста. - Информационный листок Междунар. выставки "Аэрокосмический салон", г. Жуковский, 1993,- 2 с.

Kuryatchy M.I., Ulyanov V.N. Dependent Data Compression. - Proc. of Int. Conf. on Concurrent Engineering Research and Application, Pittsburgh, Pennsylvania, 1994, pp. 467-469.

Ульянов В.Н. Кодирование изображений в технических приложениях. Томск, гос. академия систем упр. и радиоэлектроники. Деп. в ВИНИТИ 5.06.95 № 1662-В95.

Заказ 296 Тираж 100 Томск, пр. Ленина-, 40, ТАСУР.