22.2. СТАТИСТИЧЕСКИЕ МЕТОДЫ КОДИРОВАНИЯ

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

.                                             (22.2.1)

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

.                           (22.2.2)

Для кодирования изображений в системах ИКМ количество уровней квантования

                                                (22.2.3)

выбирается обычно так, чтобы b было целым числом (от 6 до 8). В результате система ИКМ затрачивает в общей сложности

                                          (22.2.4)

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

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

Рассмотрим следующую схему прямого решения задачи оптимального кодирования. Пусть изображению с большой вероятностью появления  ставится в соответствие относительно короткое кодовое слово, а длинные кодовые слова сопоставляются изображениям с более низкой вероятностью появления. Существует процедура оптимального кодирования, приводящая к кодам (известным как коды Хаффмена [17]), средняя длина слова которых весьма близко подходит к нижней границе, определяемой нормированной величиной энтропии . Предположим, что все слова такого кода могут быть собраны для хранения в кодовой книге. В таком случае, когда предъявляется конкретное изображение, процедура кодирования сводится просто к извлечению соответствующего кодового слова из полного перечня изображений. Декодер такой системы должен произвести обратную операцию — найти переданное кодовое слово в книге и отобрать изображение, подлежащее воспроизведению. И хотя такая непосредственная процедура кодирования оптимальна, ее осуществление связано с чрезвычайно большим объемом операций. Пусть, например, изображение содержит 256x256 элементов, а яркость каждого элемента квантована на 256 уровней. Тогда общее число возможных изображений равно  Понятно, что просмотр кодовой книги такого объема находится за пределами практических возможностей. Можно, конечно, попытаться разделить изображение на малые блоки размерам, скажем, 4x4 элементов. Однако даже в этом случае число различных блоков приближается к , что также не оставляет надежд на практически выполнимую процедуру поиска в кодовой книге. Но имеется и другое существенное препятствие для кодирования с помощью подобной процедуры: чтобы составить подходящий код, необходимо знать вероятности  появления каждого из возможных изображений. Практическое измерение или оценка необходимых априорных вероятностей представляет собой очень сложную задачу. Отсутствие надежных вероятностных данных обычно резко снижает эффективность работы кодирующей системы.

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