Гонсалес Р., Вудс Р., Эддинс С. Цифровая обработка изображений в среде Matlab (2006) (1246139), страница 56
Текст из файла (страница 56)
8.3 показан результат процесса обработки вероятностей символов из табл. 8.1 и рис. 8.2, а). Рис. 8.3, б) и е) были получены при подстановке пары команд се1161вр(в); се11р1ос(в); между двумя последними исполняемыми строками основной программы )ш1йшвп. Функция МАТЬАВ се1181вр рекурсивно печатает содержимое смешанного массива, а графическая функция се11р1ое представляет смешанный массив в виде семейства вложенных прямоугольных блоков.
Обратите внимание на взаимно однозначное соответствие между элементами смешанного массива на рис. 8.3, б) и узлами дерева редуцированного источника. На рис. 8.3, а): (1) каждая пара разветвляющихся ветвей дерева (которая обозначает редуцирование источника) соответствует двухэлементному смешанному массиву в в; (2) каждый двухэлементный смешанный массив содержит индексы символов, которые были слиты в один символ в процессе редуцирования.
Например, объединение символов аз и а1 в основании дерева порождает двух- элементный смешанный массив вИН2г, где в~1Н2НО = 3 и в(1Н2Н2) = 1 (индексы аз и а1 соответственно). Корень дерева, расположенный сверху, образует двухэлементный смешанный массив в самого верхнего уровня. Последний шаг процесса построения кода (т. е. присвоение кодовых слов на основе редуцированного источника) осуществляется вызовом функции ша1гесобе(в, [ ] ) .
Это обращение инициирует рекурсивную процедуру присвоения кода, основанную на схеме рис. 8.2, б). Хотя рекурсивное задание не обеспечивает сохранение в памяти (поскольку стек обработанных величин должен где-то храниться) или увеличения скорости, оно имеет то преимущество, что код получается более компактным и его легче понять, особенно при работе с такой рекурсивно заданной структурой данных, как дерево. Любую функцию МАТЬАВ можно использовать рекурсивно, т. е.
она может вызывать сама себя явно или неявно. При использовании рекурсии каждый вызов функции порождает новое множество локальных переменных, которое не зависит от всех предыдущих подобных множеств. Внешняя функция ша)гесойе принимает два входные параметра; собеиогс(, массив из нулей и единиц, и вс, элемент смешанного массива редуцированного источника. Когда вс сам является смешанным массивом, он состоит из двух символов источника (или составных символов), которые были объединены в процессе редуцирования. Поскольку их необходимо кодировать раздельно, делается два рекурсивных обращения (к функции ша)гессене) наряду с двумя подходящим образом обновленными кодовыми словами (О и 1 добавляются к входному собеиога).
Когда вс не содержит смешанный массив, он является индексом символа изначального источника и ему присваивается двоичная кодовая последовательность, построенная по соаеиога с помощью операции СОРЕСвс1 = с)эаг('О' + соаеиота). Как отмечалось в 3 2.10.5, функция МАТ1,АВ с)эаг преобразует массив, содержащий положительные целые числа, представляющие коды символов в символьный массив МАТЬАВ (первые 127 кодов представляют собой стандартные АЯСП коды В.г. к д б ЗД9 символов). Значит, к примеру, сЬаг('0' е ~0 1 0]) породит символьнуюстроку '010', поскольку добавление 0 к АВСП коду нуля даст АБС11 '0', а прибавление 1 к АВС11 '0' даст АВСП код 1, а именно '1'. Таблица 8.2. Процесс назначения кодов для смешанного массива редуцированного исгоч- ника на рис. 8.3 Табл. 8.2 детализирует последовательность вызовов шакесобе, которые производятся в соответствии со смешанным массивом редуцированного источника на рис.
8.3. Чтобы закодировать 4 символа изначального источника,потребовалось 7 вызовов этой функции. Первый вызов (строка 1 в табл. 8.2) совершается из основной программы Ьп11шап. Он запускает процесс кодирования с присвоением входам собеиогб и вс, соответственно, пустой матрицы и смешанного массива в. В соответствии со стандартным обозначением МАТЮКАВ, 11х2 се11] обозначает смешанный массив из одной строки и двух столбцов. Поскольку вс почти всегда является смешанным массивом при первом вызове (исключение составляет источник, состоящий из одного элемента), совершаются два рекурсивных вызова (свь строки 2 и 7).
Первый из этих вызовов инициирует еще два вызова (строки 3 и 4), а второй инициирует два дополнительных вызова (строки 5 и 6). Во всех случаях, когда вс не является смешанным массивом, как это имеет место в строках 3, 5, 6 и 7 таблицы, дополнительные рекурсии не нужны; кодовая последовательность строится по соленого и назначается символу источника, чей индекс был передан как вс. 8.2.2. Кодирование Хаффмана Построение кодов Хаффмана само по себе не является сжатием. Чтобы получить эффект сжатия, заложенный в эти коды, символы соответствующего источника, независимо от их природы (уровни серых тонов, длины серий или выходы иных операций отображения уровней), необходимо преобразовать или трансформировать (т. е. закодировать) в соответствии с построенным кодом.
Пример 8.2. Отображение кодов переменной длины е МА77.АВ. Рассмотрим простое 16-ти байтовое изображение размерами 4х4: »12 = п1пс8(12 3 4 2; 3 2 4 4; 2 2 1 2; 1 1 2 2]) 12 = 2 3 4 2 3 2 4 4 2 2 1 2 1 1 2 2 » вЬов(>12>) Маше 81ве Вусев С1авв 12 4х4 16 пйпС8 аттау Стапб Сова1 1в 16 е1ешептв ие1п8 16 Ьутев Каждый пиксел в 12 является байтом, состоящим из 8 битов. Для представления всего изображения используется 16 байтов. Поскольку уровни серых тонов в 12 не являются равновероятными, коды переменной длины (как отмечалось в предыдущем параграфе) позволят сократить объем памяти, которая потребуется для хранения этого изображения. Функция Ьиттшап строит один из таких кодов; »с = Ьптхшап(Ывт(йов51е(х2(:)), 4)) '011' '1' '010' '00' Поскольку коды Хаффмана основаны на относительных частотах появления символов источника (но не на самих символах), которые требуется закодировать, код с идентичен коду, построенному для изображения из примера 8.1.
На самом деле, изображение 12 можно получить из 1 (пример 8.1) путем отображения уровней 107, 119, 123 и 168 в числа 1, 2, 3 и 4. Оба изображения имеют одинаковый вектор частот р = 10.1875 0.5 0.125 0.1875). Простейший путь кодирования 12 с помощью кода с заключается в совершении следующих операций: »Ы12 = с(12(: ) ) ' ЫХ2 = Со1ш~шв 1 сЬгоиЯЬ 9 >1 >010 1 >011»010»1»1»011»00> Со1вшпв 10 СЬтовЯЬ 16 '00' '011' '1' '1' '00' '1' '1' » вЬов(>Ы12') Маше Яйве Вусев С1авв Ы12 1х16 1530 се11 аттау Стапб Сова1 1в 45 е1ешепвв пв1п8 1530 Ьувев Здесь изображение 12 (двумерный массив класса (Лг>Т8) преобразован в смешанный массив Ы12 размерами 1 х 16 (операция транспонирования применена для экономии бумаги).
Элементами Ы12 являются символьные строки переменной длины, а соответствующие пикселы 12 расположены в порядке считывания сверху вниз и слева направо (т. е. по столбцам). Как видно из этой распечатки, закодированное изображение занимает 1530 байт, т. е. памяти требуется почти в 100 раз больше, чем при хранении самого изображения 12! д.д. К д д З~\~ Использование смешанного массива Ы12 вполне логично, поскольку это один из двух стандартных типов данных в МАТ[,АВ (см. 3 2.10.6) для представления разнородных данных. В случае с ЫС2 эта разнородность означает различие длин символьных строк, и платой за удобство обращения с ними посредством смешанного массива служит существенное увеличение требуемой памяти (присущее смешанным массивам), которое требуется для отслеживания положения элементов переменной длины. Этот излишний расход памяти можно устранить путем преобразования Ы12 в обычный двумерный символьный массив: »Ь212 = сЬаг[Ы12) ' Ь212 = 1010011000011011 1 11 1001 0 010 1 1 » яЬов['Ь212') Маше 31ве ВуСев 01авв Ь212 Зх16 96 сЬаг агтау Стапб СоСа1 1в 48 е1ешепсв ивйпб 96 Ьугев.
Здесь смешанный массив Ы12 преобразован в символьный массив Ь212 размерами 3х 16. Каждый столбец Ь212 соответствует пикселу в Х2 в порядке сканирования сверху вниз и слева направо (т. е. по столбцам). Отметим, что в массиве Ь212 вставлены символы пробелов для правильного соответствия битов по столбцам. Поскольку два байта требуется для каждого символа '0' или ' 1 ' кодовых слов, для хранения Ь212 требуется 96 байт — все еще в 6 раз больше, чем исходные 16 байт, необходимые для хранения 12.
Мы можем избавиться от вставки пустых символов с помощью операций » Ь212 = Ь212 [: ); » Ь212(Ь212 == ' ') = [); » яЬов[>Ь212>) Маше 31ве ВуСев 01авв Ь212 29х1 68 сЬаг атгау Сгапб СоСа1 1в 29 е1ешепсв пв1пя 68 ЬуСев Но требуемый объем памяти по-прежнему превосходит 16 байт для хранения 12. Чтобы по-настоящему сжать 12, код с должен проявиться на битовом уровне, когда несколько закодированных пикселов пакуются в один байт: »Ь312 = шаС2Ьпгг[12) Ь312 = в1яе: [4 4) шйп: 32769 Ывг: [3823) себе: [43867 1944) » и [>ЬЗ12>) Маше 31ве Вугев 01авв Ь312 1х1 618 вггпсС аггау Сгвпб Сота1 1в 13 е1ешептв пв1пи 618 Ьусев (312 Г В.
С бр Несмотря на то, что функция шаС2Ьиг т возвращает структуру Ь312, которой требуется для хранения 518 байт памяти, большая ее часть связана со служебной информацией о структурной переменной (напомним,что в 3 8.1 при обсуждении функции АшгаСАо сообщалось, что МАТВАВ использует 124 дополнительные байта на одно поле структуры), а также с тем, что шас2Ьитг генерирует некоторую информацию, облегчающую будущее декодирование. Пренебрегая этими излишками памяти, которые пренебрежимо малы при работе с практически значимыми изображениями (нормальных размеров), шаС2Ьитт сжимает 12 с коэффициентом 4: 1, а именно: 16 пикселов по 8 бит в 12 сжимаются до двух 16-ти битовых слов — элементов поля себе в Ь312: »Ьсобе = ЬЗС2.соце; »нпов('Ьсобе') Маше 81ге Вусев 01авв Ьсобе 1х2 4 и1пС16 агтау 0гапб Соса1 Ав 2 е1ешепСв ив1п8 4 Ьусев »бес2ЬАп1цоиЬ1е(Ьсобе)) 1010101101011011 0000011110011000 Отметим, что функция бес281п была использована для отображения индивидуальных битов в Ь312.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
