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

ВВЕДЕНИЕ.

ГЛАВА. I. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ИЗОБРАЖЕНИЙ.II

1.1. Модель бинарных изображений

1.2. Статистические свойства бинарных изображений

1.3. Модель многоградационных изображений.

1.4. Статистические свойства изображений

1.5. Информационные свойства изображений

Выводы.

ГЛАВА 2. ИССЛЕДОВАНИЕ СТАТИСТИКИ ИЗОБРАЖЕНИЙ.

2.1. Корреляционная функция тестовых изображений

2.2. Вычисление вероятностей в центре опорной четверки

2.3. Экспериментальное определение частот в центре опорной четверки.

2.4. Оценка информационной емкости тестовых изображений

2.5. Формирование случайных изображений

Выводы.

ГЛАВА 3. СОКРАЩЕНИЕ ИЗБЫТОЧНОСТИ.

3.1. Алгоритмы блочного адаптивного кодирования.

3.2. Алгоритмы последовательного сжатия

3.3. Оптимизация процесса обработки изображений . . 115 Выводы.

В диссертации рассматривается способ математического описания изображений. В рамках рассматриваемой модели изображений исследуются их статистические и информационные свойства, приводятся экспериментальные исследования статистики двух тестовых изображений, которая сравнивается с расчетной статистикой. В качестве приложения математической модели приведены два алгоритма сжатия изображений, предложенные автором диссертации. Алгоритмы имеют большой коэффициент сжатия (8-10 раз при байтовом исходном представлении информации), высокую точность передачи при несложной аппаратной реализации. Кратко затронут вопрос использования статистической избыточности изображений при машинной обработке. Хотя модель применима как к цветным, так и к черно-белым изображениям (инвариантна к виду представленной информации), в целях экономии объему работы, рассмотрены только черно-белые многоградационные изображения. При этом под термином "многоградационные" понимаем тот случай, когда величиной ///г можно пренебречь, где ' /2 - число градаций.

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

Актуальность задачи. Обработка изображений и передача их по каналам связи связана с преобразованием большого объема информации. В цифровом телевидении простое кодирование исходных аналоговых сигналов по методу импульсно-кодовой модуляции создает цифровой поток объемом более сотни мегабит в секунду, что превышает пропускную способность каналов Единой автоматизированной системы связи [13, 4з] . Большие потоки информации создает фототелеграфная связь, передача газет по каналам связи и т.п. Аналогичная ситуация сложилась и в проблеме изучения Земли из космоса. Здесь центры обработки аэрокосмической информации не в состоянии обработать поток поступающей информации [~ .1, 17~\ . Таким образом,проблема сокращения цифрового потока информации и проблема увеличения пропускной способности комплексов обработки аэрокосмической информации требуют своего незамедлительного решения.

Состояние вопроса. Указанные выше две проблемы решаются в настоящее время изолированно друг от друга. Увеличение пропускной способности обрабатывавших систем идет по двум направлениям.Первое направление - увеличение быстродействия ЭВМ, их оперативной памяти и распараллеливание счета. Типичными примерами таких комплексов являются £ У Я Т£/У -М, Е/?/?ТЯУ/8 № /7Р 9/3 (США.) [I] . Второе направление - разработка эффективных обрабатывающих алгоритмов типа широко известных алгоритмов быстрого преобразования Фурье, Адамара и т.д.

С задачей сокращения информационного потока при передаче изображений по каналам связи или сужение (сжатие) полосы частот столкнулись уже на первых этапах создания телевизионных систем. Первым эффективным техническим решением было введение черезстро-чного растра, что позволило сократить полосу частот для широковещательного телевидения до 6 МГц ¡ 31, 41] . Это стало возможным благодаря сильным межстрочным и межкадровым корреляционным связям. В микроструктуре энергетического спектра телевизионного сигнала обнаруживаются максимумы на частотах, кратных строчной и кадровой частоте. В аналоговых системах цветного телевидения это свойство позволило передать информацию о цвете [27 , 39] .

Возможности аналоговых средств передачи изображений по каналам связи быстро исчерпшали себя и дальнейший прогресс связан с переходом к цифровым методам передачи сигналов, цифровому телевидению. Переход к цифровой форме представления сигнала позволил решать задачи, которые не реализуются аналоговыми средствами а также поставить ряд принципиально новых задач, связанных с коррекцией сигнала, фильтрацией и т.д., облегчить автоматизацию телевизионных центров, вплоть до включения ЭВМ в систему контроля [13, 41, 43J . С другой стороны, как отмечалось выше, переход к цифровой форме потребовал значительно большую полосу частот, и как следствие повысились требования к быстродействию элементной базы. Проблема сжатия полосы частот выдвинулась на одно из первых мест [23, 24] , Решению этой задачи было уделено много внимания как в нашей стране, так и за рубежом.

Первые же исследования цифровых изображений, которые начались в 50-х годах, показали, что они обладают большой статистической избыточностью [10,20,21,49,54,59] , а именно, близко расположенные точки изображения обычно имеют близкие по яркости значения. Было обнаружено, что при переходе от сигнала </■(£) » к разностному сигналу У (6) = ^- ^(£ -у) (здесь функция и аргумент могут принимать только целочисленные значения), энтропия определенная выражением где P¿ - вероятность реализации С - 20 значение яркости, уменьшается примерно в два раза [б4,59] . Используя это свойство, был построен дифференциальный квантователь [22,58] »который нашел широкое применение при передаче изображений по каналам связи. Дальнейшей? сокращения избыточности можно добиться кодированием групп или блоков чисел соответствующих яркостям в близких друг к другу точках. Непосредственное изучение распределения различных комбинаций значений в группе для многоградационных изображений невозможно из-за большого числа комбинаций даже при небольшой размерности группы. Эта задача может быть упрощена в предположении, что изображение может быть представлено какими либо интерполирующими функциями. Тогда вместо передачи отсчетов в точках изображения достаточно передать значения коэффициентов полиномов [16,25,40,45,50,53] . При этом интерполяция проводится либо вдоль строки развертки, либо охватывает некоторую часть изображения, размеры которой, в случае адаптивного кодирования, могут изменяться в пределах одной реализации изображения.

Широкое распространение получили методы кодирования с преобразованием. В этих методах изображение подвергается какому-либо матричному преобразованию и кодируются коэффициенты,полученные в результате преобразования. Впервые для этих целей применялось преобразование Фурье |46,48,55] . Метод кодирования с преобразованием Фурье основан на том, что для изображений многие коэффициенты разложения Фурье можно отбросить за их малостью или потратить на их кодирование небольшое число разрядов. В том и другом случаях это приводит к небольшой потере точности. В целях сокращения числа вычислительных операций вместо преобразования Фурье можно воспользоваться преобразованием Адамара [29,52,56,60] и Хаара [47,57] . Внимание исследователей привлекло к себе преобразование Карунена-Лоэва [51] »которое обеспечивает минимальную среднеквадратическую ошибку, но требует знания статистических характеристик ансамбля кодируемых изображений, что затрудняет его реализации. Минимальная плотность кодирования, которая достигается в методах кодирования с преобразованием зависит от допускаемой среднеквадратической ошибки передачи информации и от применяемого преобразования и оценивается примерно двумя битами на кодируемый элемент при "приемлемом" качестве принятого изображения.

В работе [55] авторы считают достижимой плотность кодирования I бит на элемент, однако меньше 2 бит на элемент им получить не удалось.

Существенным недостатком методов кодирования с преобразованием является размывание контурной части изображения (как следствие отбрасывания "энергетически несущественных" высших гармоник),что вносит дискомфорт при восприятии изображения зрителем [43] и приводит к потере ихиетрических свойств. В работах [2,18,42,43] описан метод кодирования, который свободен от вышеуказанного недостатка. В методе группового кодирования, описанном в них, так же как и в методах кодирования с преобразованием, изображение разбивается на прямоугольные блоки. Исследуя типовые сюжеты, было показано, что примерно 1000 типовых блоков покрывают практически все изображение. В канал связи передается номер блока, закрепленный за ним в кодовой книге. В случае если блок отсутствует в кодовой книге, его значения передаются поточечно в исходном виде.При таком способе передачи удается получить плотность кодирования 1,8 бита на элемент.

Как методы кодирования с преобразованием, так и метод группового кодирования вносят свой специфический или методический шум "фрагментарности". На принятом изображении заметна блочная структура, при кодировании требуется принимать дополнительные меры [2, 18] . В работах [б,7] был предложен способ кодирования атаптив-ный к контурам изображения. Этот способ свободен от указанного недостатка, автор также указывает на возможность повышения коэффициента сжатия при улучшении качества изображения. Плотность кодирования, им полученная, равна 2,8 бит на элемент.

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

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

Цель работы и постановка задачи. При исследовании статистики изображений преследовались следующие цели:

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

2. Дать оценку количества информации, содержащейся в изображении.

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

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

Содержание диссертации. В диссертации дается систематическое изложение исследований автора, опубликованных в работах [3,4,14, 15,28,34,36,37,38] .

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

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

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

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

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

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

Основные положения, выносимые на защиту.

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

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

3. Способ приближенного расчета алгоритмов сжатия изображений и оценки их информационной емкости.

4. Алгоритмы сжатия описания многоградационных изображений.

Основные выводы по диссертации.

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

Стоит упомянуть еще об одном интересном приложении метода. гго

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

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

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

1. Алексеев A.C., Кульков H.B., Пяткин В.П. Региональный центр автоматизированной обработки аэрокосмических изображений (концепция). - ВЦ. СО АН СССР: препринт № 94, 1978.

2. Алявдин М.С., Кац Б.М., Сардыко C.B. Исследование методов уменьшения заметности межблочной структуры при групповом кодировании. Техника средств связи. Сер. техника телевидения, вып. 6, 1980.

3. Белаго И.В., Киваев А.И., Старков М.А. К вопросу автоматизации фотограмметрических работ. Геодезия и картография, 1983, № 8.

4. Белаго И.В., Пинчук А.И., Старков М.А. Анализатор бинарных изображений. Автометрия, 1983, № 3.

5. Белаго И.В., Старков М.А. Анализатор изображений. Автометрия. (в печати).

6. Бокштейн И.М., Брауде-Золотарев Ю.М. Цифровая интерполяция при двумерном анализе и синтезе изображений. Труды НИИР, 1980, Р 4.

7. Брауде-Золотарев Ю.М. Способ анализа и синтеза телевизионных изображений. А. с. 120534 (СССР).

8. Бурый JI.B., Золотухин 10.Н., Иванов В.А. и др. Автоматизированный комплекс обработки изображений. Автометрия,1980,№3.

9. Бурый JI.B., Коронкевич В.П., Нестерихин Ю.Е. и др. Прецизионный фотограмметрический автомат. Автометрия,1974,№ 4.

10. Галицкая Е.И., Гаршман В.А., Лебедев Д.С. Применение счетно-аналитических машин для статистического анализа телевизионных сообщений. Радиотехника, 12, 1957, Ш 3.

11. Градштейн И.С. и Рыжик И.М. Таблицы интегралов,сумм,рядов и произведений. М.: Наука, 1971.

12. Иванов В.А., Пушной Б.М. Оптимизация времени построения простых изображений. Автометрия № 5, 1979.

13. Иванов В.Б., Цуккерман И.И. Перспективы развития цифровых методов в вещательном телевидении. Техника средств связи. Сер. Техника телевидения, вып. 6, i960.

14. Карпова О.М., Пинчук А.И., Старков М.А. К вопросу кодирования изображений. Автометрия, 1982, № 5,

15. Карпова О.М., Старков М.А. Информационные свойства изображений. Автометрия, 1982, № 2.

16. Кротман С.М. Сокращение избыточности как практический метод сжатия данных. ТИИЭР т.55, 1967, № 3.

17. Космические исследования земных ресурсов. Методы и средства измерения и обработки изображений. М.: Наука,1976.

18. Куликов С.А., Сардыко C.B. Повышение помехоустойчивости адаптивного группового кодирования без увеличения цифрового потока. Техника средств связи. Сер. Техника телевидения,вып.6, 1980.

19. Кунт М., Джонсер 0. Блочное кодирование графики. ТИИЭР, т.68, №7, июнь 1980.

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

21. Лебедев Д.С., Цуккерман И.И. Телевидение и теория информации. М.-Л.: Энергия,1965.

22. Методы передачи изображений. Сокращение избыточности, под ред. Прэтта У.К. М., Радио и связь, 1983.

23. МККР.Информация группы изучения ХУШ. МКТТ относительно цифровых систем передачи данных. Документ CMTT/I020-E. Х1У Пленарная Ассамблея (Киото, 1978).

24. МККР. Стандарт для телевизионных систем, использующих цифровую модуляцию. Документ ФРГ ( 11/353-Е, CMTT/I9I-E ). Период 1974-1978.

25. Нестерихин Ю.Е., Пушной Б.М. О системе автоматической обработки изображений. Автометрия, 1977, № 3.

26. Новаковский C.B. Стандартные системы цветного телевидения.-М.: Связь, 1976.

27. Пинчук А.И., Старков М.А., Цветков В.Я. Об информативности фотоизображений. В кн.: Тез.докл. X научно-техническая конференция молодых ученых и специалистов. Москва,ЦНИИГАЙК, 1978.

28. Прэтт У.К., Кэип Д., Эндрюс Д. Кодирование изображений посредством преобразования Адамара. ТИИЭР, т.57,1969,Pl.

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

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

31. Психология машинного зрения. Под ред. Уинстона П.-М.:Мир, 1978.

32. Розенфельд А. Распознавание и обработка изображений с помощью ЭВМ. М.: Мир,1972.

33. Старков М.А., Пинчук А.И. Эффективное кодирование изображений.- Техника средств связи. Сер.Техника телевидения, 1981, № 3.

34. Старков М.А. Статистическая модель бинарных изображений.--Автометрия, 1979, Р 5.

35. Старков М.А. Статистическая модель изображений.-Автометрия, 1981, № 6.

36. Старков M.А., Трофимов O.E. Применение методов сжатия изображений при решении задач томографии. В кн.: Тез.докл. Всесоюзный симпозиум по вычислительной томографии. Новосибирск, ВЦСОАНСССР, 1983.

37. Старков М.А., Трофимов O.E., Фризен Д.Г. Алгоритм для подсчета числа плоских объектов.-Автоматики и телемеханика, 1976, №6.

38. Телевидение. Под ред. Шмакова II.В.-М. : Связь, 1970.

39. Хочман Д., Кацман Г., Вебер Д. Сжатие полосы телевизионных сигналов за счет сокращения избыточности. ТИИЭР, т.56,1967, № 3.

40. Цифровое телевидение. Под ред.Кривошеева М.И.- М.: Радио и связь, 1980.

41. Цуккерман И.И. Избыточность телевизионных сообщений и проблемы эффективного кодирования в цифровом телевидении.-Техника средств связи. Сер. Техника телевидения,вып.6.,1980.

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

43. Шеннон К. Работы по теории информации и кибернетике. М.: И.Л., 1963.

44. Эндрюс С.А., Дэвис Д.М., Шварц Г.Р. Адаптивное сжатие данных. -ТИИЭР, т.55, 1967, № 3.

45. Anderson G.B., Huang T.S. Piecewise Fourier Transformation for Pieture Bandwidth Compression.- IEEE Trans.Commun., COB-20, 1972, June v.3.

46. Andrews H.C. Computer Techiques. In: Image Processing. Academic Press, New York, 1970.

47. Andrews H.C., Pratt W.K. Fouuier Transform Coding of Images, Hawaii International Conference on System Science,January,1968.

48. Capon F. Bounds to the entropy of television signals.-Res. Lab. of Electron., Mass. Inst. Technol., Cambridge, Tech. Rep. 296, 1955, May.

49. Gardenhire L.W. Redundancy Reduction, the Key to Adaptive Telemetry, National Telemetring Conference, Los Angeles. California, 1964.

50. Habihi A., Wintr P.A. Image Coding by Linear Transformation and Block Quantization. IEEE Trans.Commun.Tech.,C0M-19,1, 1971, Febr. p.50-6J.

51. Huang T.S. and Woods J.W. Picture bandwidth compression by • block quantization: presented at the Int.Symp.Information Theory, Ellenville, N.Y., Jan.1969: abstracht in IEEE Trans.Inform. Theory vol.11-16, Jan.1970.

52. Kortman C.M. Data Compression by Redundancy Reduction.-IEEE Spectrum, 1967, March, v.4.

53. Transformation to Bandwith Compression. In: Picture Bandwidth Compression, New York, 1972.

54. Rao K.R., Narasimhan M.A., Revuluri K. Image Data Processing by Hadamard. Haar Transforms. - IEEE Trans. Computers, 1975, c-23, N 9, p.888-896.

55. Sehreiber W.F. The mathematical foundation of the sguthetic highs sistem. Res.Lab. of Electron., Mass.Inst.Technol., Cambridge, Quart. Pog. Rep.68, 1963, Jan.