г. Алматы, ул. Шевченко, 95, телефон/факс: 923397

 
 

Эффективное кодирование изображений

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

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

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

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

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

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

В случае равномерного кодирования, когда все кодовые комбинации одинаковой длины, и конечного алфавита сообщений минимальная длина кодовой комбинации п определяется из соотношения mn=N, где m — основание кода; N — число «букв» алфавита; n — длина кодовой комбинации. Например, при двоичном кодировании буквенного текста m = 2; N=32. Это соответствует принятому телеграфному коду МТК-2. Однако с точки зрения эффективности этот код является избыточным, так как в нем не учитывается статистика букв в русском языке: в данном коде все буквы при разной частоте их появления передаются одинаковыми по длине комбинациями. Эффективным является такой код, при котором часто встречающиеся буквы передаются более короткими комбинациями. Отсюда следует, что статистическое кодирование должно использовать неравномерные коды.

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

Общее правило нахождения эффективного кода неизвестно, однако предложены алгоритмы кодирования. Эти алгоритмы удовлетворяют следующим условиям:

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

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

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

Сигнал представляется сериями белого и черного: белому полю соответствует последовательность (серия) нулей, а черному — серия единиц. Суть способа состоит в кодировании длин серий. В канал передается номер длины данной серии.

Поскольку длины серий различны, длины кодовых комбинаций будут неодинаковыми. Этот способ будет наиболее эффективным, если использовать вышеупомянутые принципы кодирования, но при этом кодирующее устройство будет сложным. Ограничить количество длин серий (количество кодовых комбинаций) можно, используя статистические свойства серий. Например, для изображения метеокарт целесообразно белые серии кодировать шестиэлементными кодовыми комбинациями, а черные серии — трехэлементными. С помощью этих кодовых комбинаций можно закодировать все белые серии длиной от 1 до 63 элементов (26 = 64), а все черные серии длиной от 1 до 7 элементов (23 = 8). Если бы за каждой белой серией следовала черная, то последовательность кодовых комбинаций представляла бы собой регулярно сменяющие друг друга шести - и трехэлементные кодовые группы (рис. 9.1). Если же в изображении встречаются длины, большие чем 63 или 7 элементов (для черных серий), то регулярность чередования кодовых комбинаций нарушается и для правильного приема необходимо использовать служебные кодовые комбинации, которые разделяли бы соответствующие кодовые слова (рис. 9.2). При передаче метеокарт подобный способ кодирования практически позволил получить коэффициент сжатия до 80%, т. е. примерно на 80% уменьшить общее количество передаваемых двоичных чисел.

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

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

Рассмотренные методы сжатия обладают низкой помехоустойчивостью. Неверно принятый знак о номере длины серии приводит к так называемому треку ошибок, поскольку декодер воспроизведет серию не той длины (и не той градации яркости). Таким образом, даже одиночная ошибка за счет помехи в канале может вызвать поток ошибок при декодировании сигнала. В [70] пока дано, что методы КДС и его разновидности работоспособны при вероятности ошибки канала не хуже 10~6. Реальные каналы имеют вероятность ошибки на несколько порядков больше (10-3—10~4). Поэтому без специальных мер по повышению помехоустойчивости методы КДС применять нельзя.

В последнее время в связи с широким применением ЭВМ в задачах обработки изображений практический интерес вызвали методы кодирования с помощью различных линейных и нелинейных преобразований. Наиболее перспективными с точки зрения сжатия объема сигнала (а именно полосы частот) и помехоустойчивости являются преобразования Фурье, Адамара, Карунена — Лоэва. Появление алгоритмов быстрого преобразования Фурье привело к изучению методов кодирования, при которых вместо самого исходного изображения в канал передается его преобразование Фурье [65, 68]. Возможность сокращения полосы частот объясняется тем, что присущая исходным изображениям корреляция между соседними элементами вызывает концентрацию энергии в области нулевых пространственных частот преобразования изображения. Именно это свойство и позволяет сократить полосу частот.

Помехоустойчивость кодирования с помощью преобразований объясняется тем, что при преобразовании выполняется операция усреднения. Каждый элемент восстановленного изображения является взвешенной суммой всех исходных элементов. Поэтому одиночная ошибка распределена равномерно по всем элементам восстановленного изображения и мало заметна для глаза. Эксперименты показали, что при вероятности ошибки10-4 качество восстановленного изображения вполне удовлетворительное. Таким образом, в некоторых случаях не нужно применять специальные меры по повышению помехоустойчивости [65].

Как уже отмечалось, возможность сокращения полосы частот основывается на использовании определенной структуры распределения энергии изображения в плоскости преобразования. Представленные на рис. 9.3 графики характеризуют долю энергии в процентах, содержащуюся в пространственных частотах преобразования Фурье трех различных изображений. Для них около 95% энергии содержится менее чем в 1 % выборок пространственных частот. При таком распределении энергии очевидный способ сокращения полосы частот состоит в том, чтобы не передавать информацию о верхних пространственных частотах. Эта операция эквивалентна пропусканию изображения через низкочастотный пространственный фильтр.

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

Рассмотренные цифровые методы устранения избыточности не исчерпывают большого разнообразия существующих направлений и способов повышения пропускной способности каналов. Более детальные сведения о рациональном кодировании изображений изложены в [68].

.: НАВИГАЦИЯ :.
[X] Главная

[..] История

[..] Статьи

 
 

 

 
 

АЛМАТИНСКИЙ БИЗНЕС-КОЛЛЕДЖ