Гонсалес Р., Вудс Р., Эддинс С. Цифровая обработка изображений в среде Matlab (2006) (1246139), страница 54
Текст из файла (страница 54)
Поскольку процедура квантования не является обратимой, блок обратного квантователя отсутствует в общей схеме декодера. 8.2. Кодовая избыточность Пусть дискретная случайная величина гь при )с = 1,2,...,/ с вероятностями р„[гь) соответствует распределению уровней полутонового изображения, общее число которых равно Е. Как и в гл. 3, предполагается, что г1 соответствует нулевому уровню (напомним, что индексы массивов в МАТ?,АВ начинаются с 1, а не с О). Пусть также ~~~300 Глава 8. Сокатие изобраокения где иь равно числу появлений на изображении пикселов 14-го уровня серого цвета, а и — общее число пикселов изображения.
Если число битов, используемых в цифровом представлении каждой величины гы равно 1(гь), то среднее число битов, необходимое для представления каждого пиксела, равно Таким образом, средняя длина кодовых слов, назначаемых различным значениям уровней серого цвета, находится суммированием произведений числа битов представления каждого уровня на вероятность появления этого уровня. Значит, общее число битов для кодирования изображения размерами МхХ равно МЖТ, Таблица 8.1. Иллюстрация кодовой избмточиости: Ь „= 2 для Кода 1 и Ь „1.81 для Кода 2 Если все уровни изображения представлены обычным тп-битовым двоичным кодом, то правая часть последнего равенства, очевидно, сводится к т битам.
В самом деле, 1(гь) = т для любого гю и этот множитель выносится за знак суммирования, а сумма всех р„(гь) равна 1, и в итоге Ь, = т. Из табл. 8.1 следует, что кодовая избыточность почти всегда присутствует, когда уровни градации серого цвета кодируются обычными двоичными кодами фиксированной длины. В этой таблице даны обе схемы кодирования пикселов четырехуровневого изображения, распределение уровней которого дано во втором столбце. Кодирование каждого уровня двумя битами (Код 1 в третьем столбце таблицы) дает среднюю длину кодового слова, равную 2 битам. А средняя длина кода пиксела при кодировании Кодом 2 (пятый столбец таблицы) равна 4 1а,я = ~ Ить)р (~я) = 3 0.1875+ 1. 0.5+ 3 0.125+ 2.
1,875 = 1,8125, и достигнутый коэффициент сжатия равен Сн = 2!1.8125 = 1.103. Эффект сжатия при использовании Кода 2 достигается за счет того, что кодовые слова имеют переменную длину, и это позволяет назначать короткие коды значениям пикселов, чаще других появляющимся на изображении. Тогда возникает естественный вопрос: сколько битов требуется для оптимального представления уровней пикселов изображения? Иными словами, какой минимальный объем данных является достаточным для полного описания изображения без потери информации? С математической точки зрения, ответы на подобные вопросы дает наука теория информации. Основная посылка этой теории заключается в том, что информационный поток можно моделировать в виде вероятностного процесса, измерение которого хорошо согласуется с нашей интуицией. .. К д 1 30~~1) В соответствии с этим положением можно считать, что случайная величина Е, наблюдаемая с вероятностью Р(Е), несет 1(Е) =!ой = — )оя Р(Е) 1 единиц информации.
Если Р(Е) = 1 (событие всегда наступает), то /(Е) = О и здесь нет никакой информации. В самом деле, в этом случае нет неопределенности в наступлении данного события, и поэтому нет необходимости сообщать или передавать информацию о том, что событие имело место. При таком подходе, чем реже наступает событие, тем оно «ценнее» и, следовательно, несет в себе ббльшую информацию. Имея источник случайных событий из дискретного семейства возможных исходов (ам аз,..., аз) и соответствующий набор вероятностей этих исходов (Р(а~), Р(аз),..., Р(аЯ), средняя информация, приходящаяся на один выход источника, называемая энтропией этого источника, вычисляется по формуле Н = — ~ Р(а ) )он Р(а ). Если интерпретировать изображение как выборку, порождаемую некоторым «полутоновым источником», то можно моделировать вероятности символов этого источника с помощью гистограммы наблюдаемого полутонового изображения.
Тогда строится число, называемое оценкой первого порядка Н для энтропии источника: Н = — ~~~ рт(ть) )обр„(ть). Эту оценку можно вычислять с помощью следующей М-функции в предположении, что каждый уровень серого цвета кодируется независимо от других. В этом случае в теории информации доказано, что энтропия задает нижнюю границу сжатия, которую можно достигнуть путем удаления кодовой избыточности.
1ппсе1оп Ь = епегору(х, и) %ЕМТКОРУ Сошрпгев а 11гвг-огоег евс1шасе о1 ГЬе епсгору о1 а шагг1х. % Н = ЕНТНОРУ(Х, М) геспгпв СЬе 11гвг-огйег евсгшасе о1 шасг1х Х % вггЬ М вушЬо1в (М = 256 11 ош1гсео) ма ьгсв/вушЬо1. ТЬе вес%шаге % аввишев а всаг1вггса11у 1пйерепоепс воигсе сЬагассег1хео Ьу сЬе % ге1ас1не Тгеопепсу о1 осспггепсе оТ ГЬе е1ешепсв 1п Х. еггог(пагясЬК(1, 2, пагймт)); % СЬесЬ 1прпг ягяишепсв 11 пяг61п ( 2 и = 256; % Ое1ап1с Тот и. епо х = йопЬ1е(х); % Ма1«е 1прпс йопЬХе хЬ = Ь1вс(х(:), и); % Сошрпсе М-Ь1п Ьгвсойгаш хЬ = хЬ / вша(хЬ(:)); % Сошрпге ргоЬаЬШг1ев % МаХе шавЬ Го е11ш1паге О'в в1псе 1оя2(0) = -1п1. ~~бб б б.
б б 1 = т1па(хЬ); Ь = -вшп(хЬ(1) .ь 1о82(хЬ(1))); % Саврасе епсгору Обратите внимание на употребление функции 11пд из МАТЬАВ для нахождения индексов ненулевых элементов гистограммы хЬ. Оператор 11па(х) эквивалентен команде 11па(х "= 0). Функция еппгору использует 11па при построении индексного вектора 1 гистограммы хЬ, который будет использоваться в дальнейшем для удаления всех нулевых значений из формулы для вычисления энтропии в последней строке функции. Если не сделать этого, функция 1о82 выдаст для Ь значение 1бай (результатом команды Оэ-1п1 является не число), когда вероятность символа равна нулю.
Пример 8.1. Вычисление оценки первого порядка для энтропии, Рассмотрим простое изображение 4 х4, гистограмма которого (см. вектор р в сле- дующем программном фрагменте) моделирует вероятности символов из табл. 8.1. Следующая последовательность команд строит одно такое изображение и вычис- ляет оценку первого порядка для его энтропии.
1 = 1119 123 168 119~ 123 119 168 168); [1; 119 119 107 119~ 107 107 119 119) » » 119 123 168 123 119 168 119 119 107 107 107 119 Ь1вс (1 (: ), 8); р I вшп(р) 119 168 119 119 Р = Р = Р = 0.1875 0.6 0.126 0 0 0 0 0.1876 Ь = еппгору(1) 1.7806 8.2.1. Коды Хаффмана При кодировании уровней полутонового изображения или выхода некоторой операции полутонового отображения (разности пикселов, длин серий и т.д.) коды Хоффмана назначают символам источника наименьшее возможное число кодовых символов (например, битов) при условии, что символы источника (например, пикселы) кодируются по отдельности.
Первый шаг метода Хаффмана состоит в построении серии редуцированных источников путем упорядочивания вероятностей символов данного источника и Код 2 из табл. 8.1 имеет среднюю длину Ь и 1.81, которая приближает оценку первого порядка для энтропии, равной минимальной длине двоичного кода для изображения 1. Заметим, что уровень 107 соответствует элементу г1 и имеет двоичный код 011п в табл. 8.1, 109 — это гп с двоичным кодом 1п, а 123 и 168 имеют коды 010п и 00п соответственно. П В. О. К д б Мф объединения символов с наименьшими вероятностями в один символ, который будет их замещать в редуцированном источнике следующего уровня.
Этот процесс проиллюстрирован на рис. 8.2, а) для распределения уровней нз табл. 8.1. В двух левых колонках исходный набор символов источника и их вероятности упорядочены сверху вниз по убыванию вероятностей. Для формирования первой редукции источника два символа с наименьшими вероятностями — в данном случае это ат и аэ с вероятностями 0.125 и 0.1875 — объединяются в один «составной символа с суммарной вероятностью 0.3125.
Этот составной символ и связанная с ним вероятность помещаются в список первого редуцированного источника, который также упорядочивается от наибольшей вероятности к наименьшей [см. третью колонку рис. 8.2, аЯ. Этот процесс повторяется до тех пор, пока не образуется редуцированный источник всего с двумя символами )самая правая колонка на рис.
8.2, аЯ. а) б) Рис. 8.2. метод кодирования хаффыана: а) Редуцирование источника; б1 назначение кодовых слов Второй шаг процедуры Хаффмана состоит в кодировании каждого редуцированного источника, начиная с источника с наименьшим числом символов и двигаясь к исходному источнику. Наименьший двоичный код для источника с двумя символами состоит, конечно, из символов 0 и 1. Как показано на рис.
8.2, б), эти символы приписываются к двум символам источника справа (порядок присвоения не имеет значения — перестановка 0 и 1 даст абсолютно тот же результат). Поскольку второй символ редуцированного источника с вероятностью 0.5 был получен объединением двух символов предыдущего редуцированного источника (расположенного слева от него), кодовый символ 0 приписывается каждому из объединенных символов, после чего коды этих символов дополняются слева символами 0 и 1 (в произвольном порядке) для отличия их друг от друга. Затем эта ~304 Г В. С б Ы операция повторяется для редуцированных источников всех уровней вплоть до исходного источника. Окончательные коды для символов исходного источника приведены в третьей колонке на рис.
8.2, б). Код Хаффмана на рис. 8.2, б) (и из табл. 8.1) является мгновенно и однозначно декодируемым блоковым кодом. Код называется блоковым, поскольку каждый символ источника отображается в фиксированную последовательность кодовых символов. Он является мгновенно декодируемым, так как каждое кодовое слово в закодированной последовательности можно декодировать независимо от последующих кодовых символов. Это связано с тем, что в любом коде Хаффмана каждое кодовое слово не является префиксом (началом) никакого другого кодового слова. По этой же причине код Хаффмана является однозначно декодируемым, так как любая последовательность, состоящая из кодовых слов кода Хаффмана, может быть декодирована единственным способом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
