Гонсалес Р., Вудс Р., Эддинс С. Цифровая обработка изображений в среде Matlab (2006) (1246139), страница 55
Текст из файла (страница 55)
Таким образом, любую последовательность кодированных по Хаффману символов можно декодировать, анализируя ее слева направо. Изображение размером 4х4, рассмотренное в примере 8.1, кодируется по Хаффману в порядке строк сверху вниз и по столбцам слева направо с помощью кодов из рис. 8.2, б), в результате чего получается последовательность из 29 кодовых символов 10101011010110110000011110011. Поскольку мы использовали мгновенно и однозначно декодируемый блоковый код, нет необходимости ставить разделительные символы между закодированными пикселами. Анализ этой кодовой последовательности слева направо обнаруживает, что первым допустимым кодовым словом является 1, которое является кодом символа аз, отвечающего уровню серого цвета 109.
Следующее допустимое кодовое слово — это 010, которое соответствует уровню 123. Продолжая этот анализ, мы в итоге получим полностью декодированное изображение, которое эквивалентно изображению 1 из рассматриваемого примера. Построение редуцированных источников и назначение кодовых слов по описанной выше схеме реализованы в следующей М-функции, которую мы назвали Ьи11шап: 1зшсс1ои СОВЕ = Ьиуушап(р) '/НОРРМАМ Ви116в а чат1аЬ1е-1епЕсЬ Ни11шап соое 1от а вушЬо1 воитсе. '/ СОРЕ = НОРРМАМ(Р) тетитив а Ни11шап свае ав ЬАпату вст1пЕв 1п '/ се11 аттау СОРЕ 1от 1ирие вушЬо1 ртоЬаЬ111су чессот Р. ЕасЬ нотй Х зп СОВЕ соттевроиав со а вушЬо1 яЬове ртоЬаЬ111су Ав ас сЬе '/ соттевропа1иЕ 1ийех о1 Р. '/ '/ Вавес( оп Ьиттшапб Ьу Яеап РалаЬет, Уи1нетв1ту о1 МотСЬишЬт1а, Х Менсавс1е ОК.
Ана11аЬ1е ас сЬе МАТ1АВ Сеиста1 Р11е ЕхсЬапЕе: '/ СасеЯоту Сепета1 РЯР зп 818па1 Ртосевв1и8 ала Сошшип1сас1оив. '/ СЬесй сЬе 1прис атЯишепсв 1от теавоиаЬ1епевв. еттот(патЕсЬЬ(1, 1, иат81п)); 11 (ий1шв(р) = 2) ( (ш1и(в1ве(р)) ) 1) ! Автеа1(р) ) з.взшшетз.с(р) еттот('Р шиве Ье а теа1 иишет1с частот.'); еий '/ 01оЬа1 чат1аЬ1е витч1ч1иЕ а11 теситв1оив о1 1иисе1оп 'шайесоде' В.. К д б 30~~5) 81оЬа1 СОВЕ СООЕ = се11(1епЕСЫр), 1); % 1п1С СЬе 81оЬа1 се11 аттау 11 1епЕСЬ[р) > 1 % НЬеп шоте СЬап опе вушЬо1 р = р / виш(р); % Нотша11ве СЬе 1приС ргоЬаЬШСАев в = тедисе(р); % Оо Ниттшап воитсе вушЬо1 тедисС1опв ша)сесоде(з, П ); % Веситв1не1у Еепетате СЬе соде е1ве СОВЕ = ~'1')' епд; %-— -% йшсС1оп в = тедисе(р); % Сгеасе а Ниттшап воитсе тедисС1оп Стее 1п а МАТЮКАВ се11 встиссите % Ьу рет1отш1пЕ воитсе вушЬо1 тедисС1опв ипС11 СЬете ате оп1у Сво % тедисед вушЬо1в геша1п1п8 в = се11(1епЕСЬ(р), 1); % ОепетаСе а втатС1п8 Стее в1СЬ вушЬо1 подев 1, 2, 3, ...
Со % те1етепсе СЬе вушЬо1 ртоЬаЬШС1ев. 1от 1 = 1:1епЕСЬ(р) в(1) = 1; епд нЬ11е пише1(в) > 2 [р, 1] = зотС(р); % Ботс СЬе вушЬо1 ртоЬаЬШСАев Р(2) = Р(1) е Р(2); % МетЕе СЬе 2 1овезС ртоЬаЬ111САев р<1) = П; % апд ртипе СЬе 1овевС опе з = в(1); % Неотдет Стее 1от пен ртоЬа8111С1ев з(2) = Сз11), з~2)т; % апд шетЕе й рлше АСв подев в(1) = П; % Со шаСсЬ СЬе ртоЬа8111С1ез еш1 %- -% 1ипсС1оп ша)сесоде(вс, содеяотд) % Бсап СЬе подев о1 а Ниттшап воитсе тедисС1оп Стев геситв1че1у Со % Еепетасе СЬе Апд1сатед чат1а51е 1епЕСЬ соде вотдз. % 01оЬа1 нат1а51е витн1н1пЕ а11 теситв1че са11в 81оЬа1 СООЕ 11 Аза(зс, 'се11') % Рот се11 аттау подав, шаЬесоде(во~1), [содевотд 0]): % адд а 0 11 СЬе 1вС е1ешепС ша)сесоде(вс[2т, [содевотд 1]); % от а 1 11 СЬе 2пд е1ве % Рог 1еа1 [пишет1с) подев, СОВЕ(вс) = сЬат('0' е содеяотд); % стеасе а сЬат соде зст1пЕ епд % Е1ве, Ст1ч1а1 опе вушЬо1 саяе! » р = [0.1875 0.5 0.125 0.1875]; » с = Ьиттшап(р) Следующая последовательность команд использует кодирование Хаффмана для построения кодов рис.
8.2: 'Ьмб Г В. с б ю 011 \13 010 >00~ Отметим, что выходом служит массив, состоящий из строк переменной длины, в котором каждый элемент представляет собой строку из нулей и единиц, что является двоичным кодом соответствующего индексированного символа из р. Например, символьная строка '010' (в массиве имеет индекс 3) является кодом уровня серого цвета с вероятностью 0.125.
В первых строках функции Ьптгвап осуществляется проверка входного аргумента р (вектора вероятностей входных кодируемых символов) на предмет его корректности и производится инициализация глобальной переменной СОРЕ в виде смешанного массива МАТЬАВ (см. з 2.10,6), который имеет 1евятЬ(р) строк и один столбец. Все глобальные переменные МАТЬАВ должны быть продекларированы в функциях, которые будут их использовать, с помощью команды 61оЬа1 Х г' 2. Эта команда делает переменные Х, У и 2 доступными в тех функциях, в которых они будут продекларированы. Когда несколько функций декларируют одни и те же глобальные переменные, они используют одну и ту же копию этих переменных. В функции Ьиттшап основная программа, а также внешняя функция иаЬесос]е используют общую глобальную переменную СОВЕ.
Обратим ваше внимание на то, что общепринято писать имена глобальных переменных заглавными буквами. Неглобальные переменные являются локальными переменными, и их можно использовать лишь в тех функциях, где они объявлены (но не в других функциях или в основном рабочем пространстве). Имена локальных переменных принято писать строчными буквами. В Ьпттшвп переменная СОРЕ инициализируется с помощью функции се11, которая имеет следующий синтаксис: Х = се111т, и).
При исполнении этой команды строится массив тхп матриц, к элементам которых можно обращаться как к смешанному массиву или по содержимому. Круглые скобки «( )» используются для индексации смешанного массива; фигурные скобки «( )» используются для индексации содержимого.
Итак, команда Х(1) = ~) индексирует и удаляет элемент 1 из смешанного массива, в то врем как Х(1) = ) ] присваивает первому элементу массива пустую матрицу. То есть, Х(1) обращается к содержимому первого элемента (массива), а Х(1) обозначает сам этот элемент (а не его содержимое).
Поскольку смешанные массивы могут находиться внутри других смешанных массивов, синтаксис типа Х(1) (2) обращается ко второму Эквивалентное выражение имеет вид Х се11г1в, а]), Другие формы вызова отображаются командой » Ь«1р Ы д.д. к д д да~7 элементу смешанного массива, который является первым элементом смешанного массива Х. После инициализации переменной СОРЕ и нормирования входного вектора вероятностей 1по команде р = р / вша(р)1 код Хаффмана для нормированного вектора вероятностей р строится за два шага.
На первом шаге, который начинается оператором н = тес)псе(р) основной программы, вызывается внешняя функция тес(цсе, которая совершает редуцирование источника, проиллюстрированное на рис. 8.2, а). В подпрограмме тес)цсе элементы изначально пустого смешанного массива н редуцированного источника, размер которого согласован с СОРЕ, инициализируются своими индексными значениями. Т.е.
в(1) = 1, в(2) = 2 и т.д. После этого в цикле иЫ1е шпве1(н) > 2 создается двоичное дерево редуцированных источников, эквивалентное смешанному массиву. На каждом шаге цикла вектор р упорядочивается в восходящем порядке вероятностей. Это совершается функцией ноге, имеющей синтаксис (у, 5.) =иогт (х), где в выход у записывается вектор упорядоченных элементов вектора х, а индексный вектор 1 удовлетворяет соотношению у = х(1). После упорядочения вектора р две наименьшие вероятности сливаются путем помещения их суммы в р(2), а элемент р(1) выбрасывается. После этого смешанный массив редуцированного источника переупорядочивается, чтобы соответствовать р на базе ицдексного вектора 1 с помощью операции в = в(1). Наконец, в(2) заменяется смешанным массивом из двух элементов, в котором записаны индексы слившихся вероятностей по формуле в(2г = (а(1), в(2гг (пример индексирования по содержимому), а индексирование по массиву используется для удаления первого из двух слившихся элементов н(1) по правилу в(1) = [ ].
Процесс продолжается до тех пор, пока в н не останется только два элемента. 6) в) а) Корень Второе релуцироваиие источника в(1Н1) 4 а(1)(2)(1) З в(1Н2Н2) = 1 а(2) = 2 0.5- ---, . 05 - 0.1875 0.3125 Р 0.125 0.1875 ! Первое релуцирование источника Источник символов ддд ддд ад аг Рис. 8.3. Редупирование источника на рис. 8.2, а) с помощью функции Ьвккиаа: а) Эквивалентное двоичное дерево; б) Иэображение, построенное се11р1ос (в); в) Выход команды се1161вр(в) На рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
