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

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

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

В данной работе рассматривается комплексный подход к выбору алгоритмов сжатия и помехоустойчивого кодирования для реализации в СФПЦИ. При этом предполагаем следующую модель формирования и преобразования передаваемой в канал связи информации. Пусть изображение формируется путем построчного сканирования. Строки изображения объединяются в кадры размером N х M пикселов. Кадры подвергаются компрессии с заданной степенью сжатия B_c независимо друг от друга. Далее сжатая информация делится на блоки длиной k бит, каждый из которых преобразуется АПК (при этом размер блока увеличивается до размера n >  к ) и передается в канал связи. Полагаем, что сбои (инвертирование) бит при передаче данных происходят независимо друг от друга и известна вероятность p ₀ сбоя одного бита.

Пусть Si событие, заключающееся в появлении i сбоев в массиве сжатой информации, P(Si) = Cip0 (1 - p0)n-1 - вероятность данного собы- тия. Несложно показать, что вероятность наличия сбоев P(S0) = 1 - P(S0) = 1 - (1 - p0)n в передаваемом блоке недопустима велика при значениях p0 > 10-7 (см. рис.1), что может привести к непредсказуемым последствиям, если сбои останутся неисправленными. Например, при передаче блока с размерами N = M = 128 пикселов в режиме Bc = 2 бит/пиксел (при p0 = 10-6) приблизительно каждый тридцатый блок окажется со сбоями.

Рис.1. Вероятности появления сбоев при передаче по каналу связи блока длиной n бит

Критерии выбора алгоритма сжатия и АПК

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

| P ( Q ( A ecc ) = 0 ) < P bl

| n( Aecc )^ min   ,

^                       Aecc где P(Q(Aecc ) = 0) - достоверность переданной информации, определяемая как вероятность безошибочного декодирования блока (потери информации отсутствуют), Pbl – требуемая достоверность передачи блока информации, n = nk _ избыточность помехоустойчивого кода.

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

| B ( A c ) < B c

Q ( A c ) ^ min

I               A c

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

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

B ( A c ) n ( A ecc ) < B fr

< P ( Q ( A c ) + Q ( A ecc ) < Q fr ) < P fr ,                 (1)

Q_fr ^ min

I                J       Ac, Aecc где B fr ,Pfr – требуемые степень сжатия и достоверность передачи всего кадра, Qfr – суммарные потери качества восстановленного кадра вследствие применения алгоритма сжатия и АПК (полагаем соответствующие искажения независимыми). Следует отметить, что согласно данному критерию допускаются небольшие потери качества и при помехоустойчивом кодировании.

Оценка влияния сбоев на качество выходной информации

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

Однако непосредственное моделирование сбоев с малой вероятностью (при p0BcNM << 1) требует большого количества вычислительных эксперимен- тов. Вместо этого предлагается проводить моделирование с априорно заданным количеством сбоев в массиве кодированной информации. Ограничиваясь при моделировании событиями {Si }I=1, можно построить гистограммы распределения выходного показателя качества и получить оценки условных вероятностей P(Q < Qfr I Si). При этом необходимое количество моделируемых событий l определяется из условия заданной точности

n

2 p (Si^<Б.

i = I + 1

Так, например, для моделирования сбоев в блоке длиной n = 2¹⁵ при p о = 10 — 5 достаточно ограничиться количеством I = 4, чтобы обеспечить погрешность менее 2 • 10 ^{- 5}.

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

f ( Q fr ) =£p ( Q <  Q fr i StY ( S ') .               (2)

i = 0

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

• 1)    Q =0 – изображение не содержит искажений,

• 2)    0 <  Q <  Q 1 - изображение содержит незначительные искажения (без потери визуального качества),

• 3)    Q i <  Q <  Q ₂ — изображение содержит существенные искажения, тем не менее, изображение может быть пригодно для использования в каких-либо целях,

• 4)    Q >  Q ₂ — изображение содержит искажения, которые делают информацию непригодной для дальнейшего использования.

Пусть Q 0 , Q 1 , Q ₂, Q ₃ - соответственно события, заключающиеся в попадании изображения в указанные выше классы. Тогда для сравнительного анализа алгоритмов сжатия и АПК можно использовать оценки вероятностей данных событий, легко рассчитываемые с помощью (2).

а) класс Q _o , б кв = 0       б) класс Q 1 , б _кв = 3 , 1

в) класс Q 2 , б _кв = 22 , 3 г) класс Q 3 , б кв = 84 , 6

Рис.2. Примеры изображений, различных классов (сверху – восстановленные после декомпрессии со сбоями; снизу - модули разностей изображений, восстановленных со сбоями типа S ₂ и без сбоев)

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

Повышение помехозащищенности сжатых изображений

В [3] предложен способ повышения помехозащищенности сжатых изображений, согласно которому информация разделяется на две части – растровую и служебную, включающую заголовок изображения, параметры алгоритмов и т.д. Доля служебной информации в кадре составляет не более 1%, но она обладает особой ценностью для восстановления изображения - ее повреждение приводит практически всегда к потере изображения. Следовательно, для защиты служебной информации необходимо использовать эффективные АПК (например, коды Боуза-Чоудхури-Хоквингема (БЧХ), Рида-Соломона [1]), обеспечивающие требуемую надежность передачи данных.

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

Дополнительные возможности по повышению помехозащищенности предоставляет иерархическая структура сжатых данных. Так, в методе сжатия на основе иерархической сеточной интерполяции (ИСИ-методе) [2] сжатые данные формируются последовательно по иерархическим уровням изображения, начиная со сжатия прореженного в 2 L - 1 изображения (где L – число иерархических уровней). Поскольку при переходе на очередной уровень объем данных увеличивается приблизительно в 4 раза, то также растет и вероятность наличия сбоев на очередном уровне. Однако даже при невозможности исправления сбоев на младшем уровне изображение не теряется полностью, а может быть получено путем интерполяции восстановленных старших уровней. На рисунках 3а-3в показаны примеры декомпрессированных изображений со сбоями (типа S ₂ - на младших иерархических уровнях l = 0 и l = 1), восстановленного до различных иерархических уровней l , а также разностные изображения (модули разностей изображений, восстановленных со сбоями и без). В случае невозможности устранения сбоев использование интерполяции позволяет восстановить изображение (рис.3д), хотя и с худшим разрешением.

а) l = 0 , е _кв = 64.5

б) l = 1 , е кв = 57.1

в) l = 2 , е кв = 0

г) е кв = 31,6

Рис .3. Использование интерполяционного восстановления при неустранимых сбоях (сверху – декомпрессированные восстановленные до l -го уровня изображения; снизу – разностные изображения)

Результаты исследований

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

• 1)    во внесении в служебную информацию контрольных признаков для каждого иерархического уровня;

• 2)    в выделении и кодировании служебной информации с помощью БЧХ-кодов.

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

На рис. 4 представлены зависимости вероятностей потери иерархических уровней изображения от вероятности сбоя одного бита (при B c NM = 2¹⁵ бит). При этом вероятность безошибочной передачи всего изображения составляет 1 - P loss ( о ) . Легко видеть, что вероятность потери старших уровней пренебрежимо мала.

Рис. 4. Оценка вероятностей потери данных иерархических уровней изображения в ИСИ-методе

На рис. 5, 6 представлены результаты исследования влияния сбоев на сжатые изображения для различных методов сжатия. При этом помехоустойчивое кодирование (за исключением кодирования служебной информации в ИСИ-методе) не применялось. Для сравнения помехоустойчивости сжатых данных приведены интегральные гистограммы показателя качества (среднеквадратичного отклонения е _кв) и зависимости вероятностей принадлежности декомпрессированного изображения к классам Q 0 и

Рис. 5. Интегральные гистограммы показателя качества (среднеквадратичного отклонения)

Рис. 6. Зависимости оценок качества выходной информации от вероятности сбоя одного бита

Результаты демонстрируют значительное превосходство ИСИ-метода по помехозащищенности данных. Так, с вероятностью 0,986 последствия сбоев в сжатой ИСИ-методом информации будут полностью устранены (при p0 = 10-6), а с вероятностью 0,997 погрешность восстановления не превысит 1, что соответствует классу Q1. Как показали исследования, влиянием сбоев на качество восстановленного изображения можно пренебречь на всем диапазоне p0 < 10-5.

Для известных методов JPEG и на основе вейв-лет-преобразования проблема помехозащищенности сжатых данных является весьма актуальной. С вероятностью не менее 0,5 восстановленные изображения будут неудовлетворительного качества, т.е. принадлежать классам Q 2 и Q 3 . Для того чтобы защитить изображения сжатые этими методами до уровня ИСИ-метода, необходимо путем помехоустойчивого кодирования ввести избыточность не менее 10%. Однако при фиксированной пропускной способности канала связи в этом случае применение АПК приведет к необходимости большего сжатия, что неизбежно ухудшит качество выходной информации.

Заключение

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

Работа выполнена при поддержке Министерства образования РФ, Администрации Самарской области и Американского фонда гражданских исследований и развития (CRDF Project SA-014-02) в рамках российско-американской программы «Фундаментальные исследования и высшее образование» (BRHE) и Российского фонда фундаментальных исследований (РФФИ), грант 04-01-96507.