Содержание к диссертации
Введение
ГЛАВА I. Математическая модель изображений ii
1.1. Модель бинарных изображений 12
1.2. Статистические свойства бинарных изображений 16
1.3. Модель многоградационных изображений 31
1.4. Статистические свойства изображений 37
1.5. Информационные свойства изображений 45
Выводы 51
ГЛАВА 2. Исследование статистики изображений 52
2.1. Корреляционная функция тестовых изображений . 52
2.2. Вычисление вероятностей в центре опорной четверки 59
2.3. Экспериментальное определение частот в центре опорной четверки 63
2.4. Оценка информационной емкости тестовых изображений 69
2.5. Формирование случайных изображений 77
Выводы 80
ГЛАВА 3. Сокращение избыточности 81
3.1. Алгоритмы блочного адаптивного кодирования 83
3.2. Алгоритмы последовательного сжатия 99
3.3. Оптимизация процесса обработки изображений . 115
Выводы 125
Заключение 126
Литература 129
- Модель бинарных изображений
- Статистические свойства бинарных изображений
- Корреляционная функция тестовых изображений
- Алгоритмы блочного адаптивного кодирования
Введение к работе
В диссертации рассматривается способ математического описания изображений. В рамках рассматриваемой модели изображений исследуются их статистические и информационные свойства, приводятся экспериментальные исследования статистики двух тестовых изображений, которая сравнивается с расчетной статистикой. В качестве приложения математической модели приведены два алгоритма сжатия изображений, предложенный автором диссертации. Алгоритмы имеют большой коэффициент сжатия (8-Ю раз при байтовом исходном представлении информации), высокую точность передачи при несложной аппаратной реализации. Кратко затронут вопрос использования статистической избыточности изображений при машинной обработке. Хотя модель применима как к цветным, так и к черно-белым изображениям (инвариантна к виду представленной информации), в целях экономии объема, работы, рассмотрены только черно-белые многоградационные изображения. При этом под термином "многоградационные" понимаем тот случай, когда величиной ///2 можно пренебречь, где ' /2 - число градаций.
Было бы естественным рассматривать изображения на непрерывном множестве точек, в работе они представлены как целочисленные функции целочисленного аргумента. В таком выборе проявилось желание максимально приблизиться к машинному представлению изображений.
Актуальность задачи. Обработка изображений и передача их по каналам связи связана с преобразованием большого объема информации. В цифровом телевидении простое кодирование исходных аналоговых сигналов по методу импульсно-кодовой модуляции создает цифровой поток объемом более сотни мегабит в секунду, что превышает пропускную способность каналов Единой автоматизированной системы связи |_13, 43j . Большие потоки информации создает фототелеграфная - 4 -связь, передача газет по каналам связи и т.п. Аналогичная ситуация сложилась и в проблеме изучения Земли из космоса. Здесь центры обработки аэрокосмической информации не в состоянии обработать поток поступающей информации |_:.1, 17 \ . Таким образом,проблема сокращения цифрового потока информации и проблема увеличения пропускной способности комплексов обработки аэрокосмической информации требуют своего незамедлительного решения.
Состояние вопроса. Указанные выше две проблемы решаются в настоящее время изолированно друг от друга. Увеличение пропускной способности обрабатывавших систем идет по двум направлениям.Первое направление - увеличение быстродействия ЭШ, их оперативной памяти и распараллеливание счета. Типичными примерами таких комплексов являются S YS ТЕМ -JOJ, EMT/tVJE W SfSTMSV5H flP—JBO (США.) [і] . Второе направление - разработка эффективных обрабатывающих алгоритмов типа широко известных алгоритмов быстрого преобразования Фурье, Адамара и т.д.
С задачей сокращения информационного потока при передаче изображений по каналам связи или сужение (сжатие) полосы частот столкнулись уже на первых этапах создания телевизионных систем. Первым эффективным техническим решением было введение черезстро-чного раетра, что позволило сократить полосу частот для широковещательного телевидения до б МГц(_31, 41 ] . Это стало возможным благодаря сильным межстрочным и межкадровым корреляционным связям. В микроструктуре энергетического спектра телевизионного сигнала обнаруживаются максимумы на частотах, кратных строчной и кадровой частоте. В аналоговых системах цветного телевидения это свойство позволило передать информацию о цвете [27, 39J .
Возможности аналоговых средств передачи изображений по каналам связи быстро иечершшали себя и дальнейший прогресс связан - 5 -с переходом к цифровым методам передачи сигналов, цифровому телевидению. Переход к цифровой форме представления сигнала позволил решать задачи, которые не реализуются аналоговыми средствами а также поставить ряд принципиально новых задач, связанных с коррекцией сигнала, фильтрацией и т.д., облегчить автоматизацию телевизионных центров, вплоть до включения ЭВМ в систему контроля [іЗ, 41, 43J . С другой стороны, как отмечалось выше, переход к цифровой форме потребовал значительно большую полосу частот, и как следствие повысились требования к быстродействию элементной базы. Проблема сжатия полосы частот выдвинулась на одно из первых мест [23, 24] , Решению этой задачи было уделено много внимания как в нашей стране, так и за рубежом.
Первые же исследования цифровых изображений, которые начались в 50-х годах, показали, что они обладают большой статистической избыточностью [10,20,21,49,54,59] , а именно, близко расположенные точки изображения обычно имеют близкие по яркости значения. Было обнаружено, что при переходе от сигнала к разностному сигналу У(6) = rf(t)'-/(-J) (здесь функция и аргумент могут принимать только целочисленные значения), энтропия определенная выражением п 1 где / - вероятность реализации С - ВО значение яркости, уменьшается примерно в два раза [54,59j . Используя это свойство, был построен дифференциальный квантователь [22,58] ,который нашел широкое применение при передаче изображений по каналам связи. Дальнейшей? сокращения избыточности можно добиться кодированием групп или блоков чисел соответствующих яркостям в близких друг к другу точках. Непосредственное изучение распределения различных комбинаций значений в группе для многоградационных изобра- жений невозможно из-за большого числа комбинаций даже при небольшой размерности группы. Эта задача может быть упрощена в предположении, что изображение может быть представлено какими либо интерполирующими функциями. Тогда вместо передачи отсчетов в точках изображения достаточно передать значения коэффициентов полиномов [іб,25,40,45,50,53] . При этом интерполяция проводится либо вдоль строки развертки, либо охватывает некоторую часть изображения, размеры которой, в случае адаптивного кодирования, могут изменяться в пределах одной реализации изображения.
Широкое распространение получили методы кодирования с преобразованием. В этих методах изображение подвергается какому-либо матричному преобразованию и кодируются коэффициенты,полученные в результате преобразования. Впервые для этих целей применялось преобразование Фурье |46,48,55] . Метод кодирования с преобразованием Фурье основан на том, что для изображений многие коэффициенты разложения Фурье можно отбросить за их малостью или потратить на их кодирование небольшое число разрядов. В том и другом случаях это приводит к небольшой потере точности. В целях сокращения числа вычислительных операций вместо преобразования Фурье можно воспользоваться преобразованием Адамара [29,52,56,60] и Хаара [47,57] . Внимание исследователей привлекло к себе преобразование Карунена-Лоэва [5l] ,которое обеспечивает минимальную среднеквадратическую ошибку, но требует знания статистических характеристик ансамбля кодируемых изображений, что затрудняет его реализации. Минимальная плотность кодирования, которая достигается в методах кодирования с преобразованием зависит от допускаемой среднеквадратической ошибки передачи информации и от применяемого преобразования и оценивается примерно двумя битами на кодируемый элемент при "приемлемом" качестве принятого изображения. - 7 -В работе [55] авторы считают достижимой плотность кодирования I бит на элемент, однако меньше 2 бит на элемент им получить не удалось.
Существенным недостатком методов кодирования с преобразованием является размывание контурной части изображения (как следствие отбрасывания "энергетически несущественных" высших гармоник),что вносит дискомфорт при восприятии изображения зрителем [43] и приводит к потере ихиетрических свойств. В работах [2,18,42,43] описан метод кодирования, который свободен от вышеуказанного недостатка. В методе группового кодирования, описанном в них, так же как и в методах кодирования с преобразованием, изображение разбивается на прямоугольные блоки. Исследуя типовые сюжеты, было показано, что примерно 1000 типовых блоков покрывают практически все изображение. В канал связи передается номер блока, закрепленный за ним в кодовой книге. В случае если блок отсутствует в кодовой книге, его значения передаются поточечно в исходном виде.При таком способе передачи удается получить плотность кодирования 1,8 бита на элемент.
Как методы кодирования с преобразованием, так и метод группового кодирования вносят свой специфический или методический шум "фрагментарности". На принятом изображении заметна блочная структура, при кодировании требуется принимать дополнительные меры [2, 18] . В работах [б,7] был предложен способ кодирования атаптив-ный к контурам изображения. Этот способ свободен от указанного недостатка, автор также указывает на возможность повышения коэффициента сжатия при улучшении качества изображения. Плотность кодирования, им полученная, равна 2,8 бит на элемент.
Выше отмеченные алгоритмы кодирования далеко не исчерпывают их полный список, не упомянуты алгоритмы сжатия бинарных и растро- - 8 -вых изображений. Подводя итог, можно сказать, что еще нет полного решения проблемы сжатия изображений для передачи их по каналам связи.
Пока нет теоретически обоснованной оценки достижимой плотности кодирования и в этом вопросе исследователи полагаются только на свою интуицию. Второе. Статистическая избыточность изображений практически не использовалась при решении задачи оптимальной обработки изображений, для повышения пропускной способности обрабатывающих вычислительных комплексов и снижению требований к элементной базе систем обработки работающих в реальном масштабе времени.
Цель работы и постановка задачи. При исследовании статистики изображений преследовались следующие цели:
Построить простой способ математического описания изображений, который бы позволял рассчитывать вероятности реализации значений в точках изображения при условии, что значения известны в некоторой произвольной системе точек.
Дать оценку количества информации, содержащейся в изображении.
Построить эффективную методику расчета коэффициента сжатия и погрешности передачи для заданных алгоритмов сжатия изображении.
4. Поиск путей использования статистической избыточности изоб ражения для сокращения затрат машинного времени при их обработке.
Содержание диссертации. В диссертации дается систематическое изложение исследований автора, опубликованных в работах [3,4,14, 15,28,34,36,37,38] .
В первой главе вводятся определения и аксиомы, предлагается способ описания статистики бинарных изображений разностным уравнением второго порядка. Изучаются свойства бинарных изображений, следующие из математической модели. Модель бинарных изображений - 9 -обобщается на многоградационные и рассматриваются свойства многоградационных изображений.
Во второй главе приводится сравнение статистических характеристик изображений, предсказанных моделью,со статистикой реальных изображений. В качестве тестовых изображений были выбраны портрет и аэрофотоснимок города. Предложен способ измерения информационной емкости изображений, рассчитан нижний теоретический предел плотности кодирования для тестовых изображений. Рассматривается возможность построения датчика случайных изображений с заранее заданными характеристиками.
В третьей главе рассмотрены два алгоритма сжатия изображений. Приводятся расчеты информационных потерь при кодировании, обсуждаются вопросы повышения коэффициента сжатия и коррекции изображения. Рассчитывается эффективность кодов, работа кодеров показана на тестовых изображениях. Обсуждается вопрос использования статистической избыточности изображений при их машинной обработке. Эффективность применения методов сжатия при их обработке показана на примере восстановления изображения по томограмме.
Научная новизна. Предложен способ математического описания изображений, заключающийся в следующем. Множество точек, составляющее изображение, разбивается на два подмножества SZ. и Si . Значение изображения в точках S1 считаются заданными. В этих точках значения либо взяты непосредственно с изображения, либо вычислены по какому-либо алгоритму. В точках множества J1 предсказываются значения вероятностей реализации градаций яркости изображения решением системы разностных уравнений, где значения в точках Si входят как граничные условия. В рамках математической модели вычисление значений условных вероятностей реализации значений в точках J2 приводит к несложным вычислениям при произволь- -ІО-ннх SL f что позволяет учитывать влияние большого числа реализовавшихся значений.
Предложен способ измерения информационной емкости изображений, то есть минимального числа битов необходимого для восстановления изображения. Способ позволяет оценить статистическую избыточность изображений и может быть применен при оценке отклонения алгоритмов сжатия изображений от оптимального.
Разработаны два алгоритма сжатия изображения, которые при простой аппаратной и алгоритмической реализации дают большой коэффициент сжатия при высокой точности передачи значений. Разработан способ оценки коэффициента сжатия и погрешностей передачи из заданных параметров класса передаваемых изображений.
Основные положения, выносимые на защиту.
Математическая модель изображений, в рамках которой возможна постановка задач сжатия, фильтрации, оптимальной обработки изображений и т.п. Возможность получения решения широкого класса задач в замкнутом виде простыми способами.
Метод информационной адаптации, в котором выбор алгоритма кодирования или обработки изображений производится в зависимости от меры ожидаемой информации.
Способ приближенного расчета алгоритмов сжатия изображений и оценки их информационной емкости.
Алгоритмы сжатия описания многоградационных изображений. - II -
Модель бинарных изображений
В этой главе рассматривается математическая модель изображений и показаны основные ее статистические и информационные свойства.
Под изображением будем понимать целочисленную функцию двух целочисленных аргументов fcK , где і и К могут принимать любые целые значения, иначе говоря, /v задана на сетке. Пару чисел /yj/fV будем называть точкой изображения. В памяти ЭВМ изображения задаются в виде матриц, поэтому далее не будем различать термины "точка изображения" и"элемент матрицы".
Функция /v/c может принимать одно из значений множества -Го, 1,2,..., /2. -I I , в этом случае будем говорить, что рассматриваются /2 - градационные изображения, а элементы этого множества назовем градациями.
В рассматриваемой ниже модели используется статистический способ описания изображений, где в каждой точке изображения определен вектор ЛА , Z о,1,2,..., /7 - і} , а каждая компонента вектора представляет собой вероятность реализации соответствующей градации. Представим себе автомат, который последовательно точка за точкой обращается к изображению и записывает его значения во внутреннюю память. Таким образом, в любой момент времени точки изображения разделяются на два множества. Множество Si -точки, к которым автомат уже обращался, в этих точках одна из компонент вектора грк равна единице, остальные нулю и, следовательно, неопределенность равна нулю. И множество Si - точки, к которым обращение еще не производилось. В этих точках неопределенность отлична от нуля. Предлагаемая ниже модель позволяет на каждом шаге обращения вычислить &)к на Л , зная которую можно построить оптимальную стратегию просмотра точек изображения. В настоящей главе систематизированы работы [15,28,34,35,36], на которые далее не ссылаемся.
Под бинарным изображением будем понимать такие изображения,в каждой точке которых может реализоваться I или 0. Точке изображения сопоставим пару чисел ( л к), где j и К целые числа, описывающие их место в матрице. Везде, если это не оговорено особо, будем рассматривать изображения на бесконечной квадратной сетке, тогда 4 и / могут принимать любые целые значения в интервале ( - оо , с о ). Четверку чисел \(f-i )jii pN , (V K-j)i (Jj К+і)т будем называть окрестностью (J, К )- й точки.
Пусть на множестве точек Л , которые будем называть опорным множеством, значения изображения СОрк заданы. Рассмотрим ансамбль бтгарных изображений такой, что для каждого изображения ЗС yv выполняется следующее условие XJjK = Щ,к,(/ ) «5 Л (I.I.I)
Здесь мы не накладываем никаких ограничений на S2. . В вырожденных случаях S2 0 - пустое множество и 2 совпадает с сеткой. Пусть имеется генератор случайных изображений, который по запросу выдает одно изображение из ансамбля, при этом всегда выполняется условие (I.I.I). Выскажем следующие утверждения:
Постулат I. Частота w /r » с которой реализуется единица в (j tfj -й точке изображения,стремится к своему пределу IJ\R ПРИ числе испытаний, стремящемуся к бесконечности,или Л/т? ij,K = Р/,н , (ІЛ-2) где РА к - вероятность реализации единицы ( J , / )-й точне. Постулат 2. Для всех (j, / ) =. SI , где SI -множество точек, дополняющее S2. до полной сетки, /у! к удовлетворяет разностному уравнению второго порядка.
Этот постулат был сформулирован из следующих соображений. По известным значениям на S2. находим функцию, которая интерполировала бы значения P/jrt на S2 , а уравнения второго порядка дают достаточно широкий .,абор решений и их нетрудно исследовать. Второй постулат естественно налагает ограничения на класс исследуемых изображений, которые выясняются в ходе дальнейших рассуждений.
Статистические свойства бинарных изображений
В этом разделе мы рассмотрим статистические свойства бинарных изображений, попутно нам придется рассмотреть свойства решений уравнений (І.І.6). Подстановкой = #л-4 (1-2Л) уравнение (І.І.б) приведем к виду Обозначим через Q/K решение уравнения (1.2.2) при следующих значениях на fy =y,{/j J=fe,sJ, (t.sj s . , (I,2 3)
Здесь в единственной точке опорного множества ( S) задано значение равное единице. В остальных точках Si & ,к = .Как нетрудно видеть, решение уравнения (1.2.2) при произвольных значениях сОл уК может быть представлено в виде
Нас будут интересовать только решения при COj,,к — ОУI Разобьем SX на два подмножества Qa и Sli таких, что тогда решение уравнения (І.І.б) выражается через функции g,f s в виде в чем нетрудно убедиться непосредственной подстановкой в (І.І.б). Сформулируем следующее свойство.
Свойство I. Для произвольных Я- сумма вероятностей реализации единицы на негативе и позитиве равна единице.
Если /7 априорная вероятность получения единицы для позитиви ва, то /? -/-/ есть априорная вероятность получения единицы для негатива. Учитывая это, запишем уравнение л. -\ АР КЛІР ІГ/? ) 0, (1.2.7) -л здесь Р/9А- - вероятность реализации единицы в негативе.Заметим, s что вместо Л мы должны были бы записать /\ , но, как будет показано ниже, /? = /I . При переходе от (1.2.7) к (1.2.2) h исчезает, далее заметим, что Q iS не зависит от значений на St . При переходе к негативу между множествами SiQ Si і и Slo j, Scx будут справедливы следующие соотношения и SZj- Sl0 тогда решение (1.2.7) запишется в виде: или, учитывая соотношения между Sl0 S2d и Sl0 S2S и между /j и /У , в виде что и требовалось доказать. Таким образом,если бинарное изображение представлено двумя кодами if и у/ , то его статистика описывается следующей парой разностных уравнений Подставляя вместо условных вероятностей (1.2.9) и (1.2.10) и, приведя подобные члены, получим выражение для корреляционной функции в окончательном виде
Теперь заметим, что корреляционная функция, вычисленная для негатива и позитива совпадает, поэтому совпадают и решения - л- , а следовательно, Д - fl Выражения (1.2.9) (1.2.II) дают связь между условными вероятностями и корреляционной функцией бинарного изображения. Свойство 2. Функция внутристрочной корреляции имеет экспоненциальный вид.
Мы обращаем внимание на это свойство, поскольку оно неоднократно было описано в литературе по исследованию статистики -изображений [30,43] .В одном случае ак определяется выражением (I.I.9) и, таким образом откуда непосредственно и следует это свойство. Подставляя (I.I.I4 в выражение корреляционной функции, получим
Воспользуемся известным разложением логарифма в показателе экспоненты в щц: и заметив, что всегда Ы J , отбросим все члены разложения выше первого порядка, получим
Средняя длина отрезка с получила новую физическую интерпретацию, она равна удвоенной подкасательной функции внутристрочной корреляции.
Свойство 3. Построчное считывание изображения есть марковский процесс. Это свойство непосредственно следует из одномерного уравнения (I.I.7). Если в строке было прочтено / -J точек, то для предсказания / -й, /-е-у-и и т.д. достаточно знать только / -j -ю точку, так как точки ей предшествующие на решение не влияют. Это свойство в литературе получило название марковости или описание строк марковским процессом.
Корреляционная функция тестовых изображений
Исследования статистики проводят, как правило, на типовых сюжетах, предполагая, что они достаточно хорошо представляют широкий класс изображений. К таким сюжетам относятся: портрет, пейзаж, группа людей, городской пейзаж и т.п. Следует особо подчеркнуть роль портрета. Изображение этого типа наиболее чувствительно ко всякого родя искажениям j_2j , здесь сказываются особенности нашего восприятия.
В этой главе исследуется статистика и проверяются предположения, высказанные в первой главе. В качестве тестовых снимков были выбраны аэрофотоснимок и портрет. На первый взгляд эти изображения являются как бы "полярными" тем не менее, как будет видно ниже, их статистика подчиняется общим закономерностям.
Изображение типа "портрет" показано на рис. 2.1а. Снимок в ЭВй представлялся в виде матрицы размерностью 1024 х 900 восьмиразрядных элементов. Контрольный вывод сделан растром 100 мк (разрешение 10 линий на мм, поэтому на рис. 2.1а растра не видно).
На рис. 2.16 показана гистограмма портрета. Из гистограммы видно, что из 256-ти градаций фактически используются только 128, т.е. изображение представляется cem-разрядным двоичным кодом.
На рис. 2.2а показан контрольный вывод аэрофотоснимка. В памяти ЭВМ аэрофотоснимок матрицей размерностью 2048 х 2048 восьмиразрядных элементов. Вывод сделан растром 50 мк или 20 линий на мм. Гистограмма аэрофотоснимка показана на рис. 2.26. Так же как и в случае портрета эффективно используется только семь разрядов кода.
При исследовании изображений была принята модель нормальных многоградационных изображений, статистика которых описывается системой уравнений (1.3.II). На изображениях 2.1а и 2.2а вычислялась функция внутристрочной корреляции по формуле Гдв Х - среднее значение изображения по строке, & - дисперсия, определяемая по формуле
Величина /v выбиралась для рортрета равная 860 и для аэрофотоснимка А/ = 1900. На рис. 2 _3а и 2.4а показаны реализации корреляционной функции для портрета и аэрофотоснимка соответственно. На рис. 2.36 и 2.46 корреляционная функция для портрета и аэрофотоснимка осредненная по 10-ти реализациям.
Согласно свойству Z функция внутристрочной корреляции есть решение одномерного разностного (1,1.7) при Р0- I и имеет следующий вид Прологарифмируем выражение (2.1.3), получим Функции jc для портрета и аэрофотоснимка показаны на рис. 2.5а и 2.56 соответственно. Из полученных графиков видно, что вплоть до значений К = 60 экспериментальные кривые хорошо приближаются к прямой. По углу наклона апроксимирукхцей прямой определяем ОС .Для портрета с =85 и для аэрофотоснимка oL =91.Коэффициенты /? согласно (I.I.4) равны 0,00055 и 0,00048 соответственно.
В рамках математической модели, рассмотренной в первой главе, можно вычислять распределение вероятностей реализации градаций в интересующих нас точках изображения по известным значениям в точках SZ . При этом для расчета И , (S2) достаточно знать только параметр
Рассмотрим решение системы уравнений (1.3.II) при заданных значениях на опорном множестве На опорной четверке точек 51 может наблюдаться семь комбинаций чисел, показанные в табл. 2.1. Комбинации не попавшие в таблицу, могут быть получены из перечисленных, исходя из сообра 2 жений симметрии. В этой же таблице показаны значения йк , которые следует задать на опорной четверке точек, при решении системы уравнений (1.3.II). Из табл. 2.J следует, что достаточно решить уравнение (І.І.4) для следующих пяти комбинаций нулей и единиц на 52 10 II 10 II II 9 9 9 9» \f (C Cs) 00 00 01 01 II t
Обозначим через решение уравнения (1.2.2) для значений на Я , соответствующих первой строке табл.1, и заметим, что все ; могут быть получены из fy . поворотом последнего вокруг начала координат. Тогда, согласно (1.2.6) решением (I.I.4) при ufo определенных (2.2.3) соответственно будут
Алгоритмы блочного адаптивного кодирования
Рассмотрим блок-схему алгоритма сжатия изображения, показанную на і ис.З.І. Последовательность чисел, представляющих изображение, подается в блок отбора опорных точек (БООТ) и на ветви кодирования К\ + Кь" . Перед поступлением очередного значения изображения Хркъ (j?K)-& точке, в БООТ определяется значение энтропии, в зависимости от значения которой,разрешается работа одной из ветвей кодирования Кх / ? . Коды с выходов Ki К? , длина которых теперь уже зависит от Xj, и //, , поступают в буферный накопитель БН и, по окончанию кодирования всего изображения, передаются из БН в канал связи.
В рассматриваемом алгоритме кодируемое изображение разбивается на блок/размером т т элементов. Для определенности будем считать /7? = 4, тоесть так как это и было реализовано в программе, моделирующей работу кодера. Значения в точках, образующих на изображений, квадратурную сетку с шагом 4 и отмеченные на РИС.3.2 кружками, передаются в БН в исходном (байтовом) виде. На ветки кодирования Не значения изображения подаются блоками по 15 чисел. Порядок следования чисел в блоке не имеет принципиального значения и может быть выбран из соображений удобств программирования. На Рйс.3.2 точки, образующие блок, заштрихованы. Оценка ; ...энтропии производится по 4-м ближайшим опорным точкам для точки,расположенной в центре опорной четверки и будем считать ее одинаковой для всех точек блока. Такая задача уже быланами рассмотрена в разделе 2.4 и энтропия была определена выражением (2.4.4).
Пусть изображение таково, что 2г = 0,25, в этом случае каждое значение точки блока совпадает с одним из значений опорной четверки чисел, вероятность несовпадения Рнс равна нулю и энтропия, определенная выражением (2.4.4), будет иметь следующую величину для различных реализаций чисел на опорной четверке точек
Каждому выражению (3.1.I) соответствует одна ветвь кодирования в алгоритме. Таким образом для коммутации ветвей следует распознать реализацию на опорной четверке точек путем сравнения четырех значений между собой.
Рассмотрим работу блоков / . Величина XJ,K сравнивается со значениями на опорной четверке точек, которая, учитывая замечание о том, что =0,25, с вероятностью единица совпадает с одним из них. В БН передадим номер опорного значения., с которым произошло -совпадение. Заметим, что для этого нам достаточно передать два бита. Такая схема кодирования будет оптимальной на первой ветви, то есть если все четыре значения опорной четверки попарно не равны друг другу. Естественно, что при кодировании реальных изображений мы не получим стопроцентного совпадения кодируемого значения с опорными, поэтому в алгоритме XJ,K заменяется на то значение опорвной четверки, которое дает с ним наименьшую по модулю разность. В том случае,когда все значения опорной четверки совпадают между собой, в БН запись не происходит или для единообразия можно сказать, что передается пустой код. Заметим, что такая ситуация при декодировании распознается однозначно.
Построение оптимального кода для остальных трех ветвей кодирования не представляет сложностей. В случае, когда одно значение на опорной четверке, для определенности будем считать,что это я , реализовалось два раза, принимаем следующий неравномерный код j,K-a- 0 Х к-i- JO; XJ, =C- 11, (3.1.2) при этом при декодарировании & и с не возникнет неоднозначности, если в кодере и декодере принято, например, следующее правило: меньшему из а. и в присвоить код 10, большему - II.
В том случае, когда на опорной четверке точек значение а. повторилось два раза и значение $ повторилось два раза, меньшее из двух кодируем нулем, большее-единицей или наоборот, если это удобнее в програмной реализации. В четвертом случае на опорной четверке точек значение Q_ реализовалось три раза и в одной точке реализовалось значение о .Вероятность реализации Хьк-CL равна 0,75 и с вероятностью -. Xj = о . Согласно (1.5.3) для кодирования О. следует выбрать код длиной Е.сw - = = 0,415 и для о код длиной 2 бита. Тогда средняя длина кода определится энтропией,равной 0,811 бит.
