Непосредственное поэлементное кодирование изображений не может быть эффективным. Во второй главе уже было отмечено, что градации яркости элементов типовых изображений можно полагать приблизительно равновероятными. Здесь нет такого резкого различия между вероятностями символов, как например в буквенном алфавите. Первое приближение к энтропии G1, рассчитанное по вероятностям, с которыми встречаются градации яркости в изображениях, мало отличается от Hмакс. Статистической избыточностью в этом приближении можно пренебречь.
Реальная статистическая избыточность изображений определяется вероятностными взаимосвязями, корреляцией между элементами. Статистическое кодирование должно начинаться с устранения или хотя бы частичного уменьшения этих взаимосвязей, или, как еще говорят, с декорреляции изображений. Как указывает Оливер (Oliver, 1952), декорреляция сообщений, характеризующихся значительными статистическими связями, является первым основным этапом эффективного кодирования.
Имеется два основных метода декорреляции, которые могут быть применены в случае статистического кодирования изображений: метод укрупнения и метод предсказания.
Метод укрупнения состоит в том, что перед кодированием элементы изображения собирают в группы. Элементы изображения (исходные символы) могут быть равновероятны, но группы, составленные из них, имеют, вообще говоря, существенно различающиеся вероятности. Это уже обсуждалось во второй главе, и можно вновь сослаться на пример, показанный на рис. 31. Приближение к энтропии, получающееся для этого случая из формулы (36), может заметно отличаться от Hмакс даже тогда, когда группа состоит из двух элементов. Однако, как следует из данных статистики изображений, при малом числе v элементов в группе такой метод декорреляции недостаточно эффективен, так как при группировке остаются значительные статистические связи между элементами соседних групп. Статистические связи между группами перестают играть существенную роль только при v порядка нескольких десятков и даже сотен. Но при этом значительно возрастают технические трудности декорреляции. Потребовалась бы огромная емкость памяти для сохранения многочисленных образцов групп и сравнения их с группами, появляющимися в изображениях. Можно заранее предположить, что такой метод декорреляции существует на высоких уровнях зрительной системы и связан с механизмами восприятия зрительных образов.
Рис. 34. Пример (а—в) декорреляции предсказанием по предыдущему значению.
При декорреляции методом предсказания используют условные (переходные) вероятности. Зная группу предшествующих элементов, предполагают, что следующий элемент (или группа следующих элементов) будет иметь наиболее вероятное значение в этой ситуации.
В предыдущей главе уже была отмечена возможность эффективно предсказывать элемент изображения по соседнему на плоскости или предшествующему во времени. Знание еще одного или большего числа соседних или предшествующих элементов уточняет предсказание уже не столь существенно. Это иллюстрировано на рис. 33 ходом соответствующих приближений к энтропии Fv с увеличением v. Таким образом, мы уже многое знаем о последующем элементе, если известен соседний (или предшествующий во времени). Информация, которую в среднем несет последующий элемент, обычно невелика.
Наиболее вероятно, что последующий элемент будет иметь такую же яркость, как и соседний или предшествующий. Этим можно воспользоваться для передачи изображений.
Рис. 35. Схема декорреляции предсказанием последующего во
времени элемента по предыдущему, а — получение разностных изображений; б — получение новых значений.
Чтобы восстановить изображение на приемной стороне или записать его в накопителе, достаточно указать лишь на те его элементы, где предсказание не оправдывается.
Пусть, например, распределение яркости на какой-либо строке изображения В(х) будет, как на рис. 34, а. Для того чтобы передать эту строку изображения, нет необходимости передавать или записывать каждый из элементов Ах. Достаточно предсказать, что каждый элемент имеет такое же значение, как соседний слева, и передавать или записывать только ошибку предсказания, В(х+Δх) — В(х) (рис. 34, б), т. е. разность между предсказанным и действительным значением элемента. Для восстановления изображения понадобится только прибавить к предсказанному значению эту разность.
Можно представить изображение и в другой форме, указывая не ошибку предсказания, а истинное значение предсказываемого элемента там, где ошибка предсказания превосходит порог ограничения — градацию (рис. 34, в). Значения этих элементов принято называть новыми значениями. Верно предсказанные значения других элементов, лежащих между новыми значениями, находятся интерполированием (прерывистые линии на рис. 34, в).
Такие же рассуждения можно провести и применительно к предсказанию последующего во времени элемента В(t+Δt) по предшествующему В (t). Предсказание производится по схеме, показанной на рис. 35. Сигнал, соответствующий яркости данного элемента, задерживают на время Δt относительно исходного сигнала и вычитают задержанный сигнал из исходного. При этом получают декоррелированный (разностный) сигнал. Разностный сигнал можно подать вместе с исходным сигналом в схему совпадения, пропускающую в канал только те значения В (t), которые соответствуют элементам, где разностный сигнал превосходит по абсолютной величине порог ограничения е, т. е. где | В (t + Δt) — В (t) | > ε. Таким образом, получают сигнал новых значений.
Пример декоррелированного телевизионного изображения показан на рис. 36 (Арбузов, Берлин, Цуккерман, 1959). Это изображение получено путем вычитания телевизионного сигнала одного кадра из другого по схеме рис. 35, а с задержкой на период кадра. Сигнал изображения биполярный. На фотографии, сделанной с экрана телевизионного приемника, нулевому уровню разностного сигнала соответствует серый фон. Здесь последующий элемент (каждый элемент второго кадра) предсказывают по предшествующему во времени (по соответствующему элементу первого кадра). Декоррелированное изображение представляет собой ошибку предсказания.
Рис. 36. Пример декоррелированного телевизионного изображения.
а — предшествующий кадр; б — последующий кадр; в — разностное изображение.
Рис. 36. (Окончание).
Рис. 37. Пример декоррелированного телевизионного изображения.
а — исходный кадр; б — межэлементная разность.
Другой пример декоррелированного телевизионного изображения показан на рис. 37. Это изображение получено также по схеме рис. 35, а, но с задержкой на время одного элемента Нулевому уровню разностного биполярного сигнала соответствует серый фон на снимке. Здесь значение элемента предсказывают по значению соседнего с ним элемента на той же строке.
Декоррелированное изображение, как и в предыдущем случае, представляет собой ошибку предсказания.
Декоррелированные рассмотренным методом изображения несут ту же информацию; что и исходные, и по ним можно восстановить исходные изображения. Статистические связи между элементами здесь гораздо меньше, чем в исходных изображениях. Зато резко изменилось «одномерное» распределение вероятностей. В то время как в исходных изображениях градации были распределены приблизительно равновероятно, в декоррелированных изображениях вероятность нулевой градации (ей соответствует серый фон на снимках, сделанных с телевизионного экрана) значительно превышает вероятность каких-либо других градаций. В дальнейшем будет показано, как это может быть использовано для статистического кодирования.
Получение разностных изображений является частным случаем более общего метода линейного предсказания, представляющего собой линейную экстраполяцию случайной последовательности по определенной совокупности ее предшествующих элементов. Методы линейного предсказания изображений применительно к телевидению были экспериментально исследованы Гаррисоном (Harrison, 1952).