22.3.1. КОДИРОВАНИЕ ДЛИН СЕРИЙ; ТЕОРЕТИЧЕСКОЕ РАССМОТРЕНИЕ [32-36]

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

,                                        (22.3.1)

где . Длина серии составляет в среднем

.                                                  (22.3.2)

Энтропия распределения вероятностей длин серий определяется как

.    (22.3.3)

Предположим теперь, что максимально возможная длина серий ограничена величиной  элементов. При этом распределение вероятностей длин серий примет следующий вид:

,      (22.3.4)

Средняя длина серий составит теперь

,            (22.3.5)

а энтропия распределения вероятностей длин серий будет равна

     (22.3.6)

Рис. 22.3.1. Средняя длина серий. ( — предел, установленный для длины серий.)

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

                                    (22.3.7)

На рис. 22.3.2 приведены графики зависимости этой относительной величины энтропии от вероятности появления контура при , а также при . Графики со всей очевидностью демонстрируют, сколь незначителен проигрыш, связанный с ростом относительной величины энтропии за счет ограничения длины серий. На рис. 22.3.2 представлена также графически величина

                                                                          (22.3.8)

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

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

.     (22.3.9)

Рис. 22.3.2. Эффективность кодирования длин серий для случая двухградационных изображений.

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

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

 .                                                                     (22.3.10)

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

Рис. 22.3.3. Эффективность кодирования длин серий при передаче одноцветных изображений:  — предел, установленный для длины серий;  — количество двоичных разрядов, отводимых на кодирование уровня серии.

Кодирование длин серий наиболее выгодно в случае изображений, допускающих грубую передачу полутонов. В случае факсимильного черно-белого изображения достаточно, указав предварительно уровень начального элемента строки, далее кодировать только расположение перепадов уровня. Относительная величина энтропии совпадает здесь с энтропией распределения вероятностей длин серий в соответствии с рис. 22.3.2. Если «черные» и «белые» серии при передаче черно-белых изображений существенно различаются по средней длине, то часто предпочтительно применить к ним различные коды. Коэффициент сокращения объема данных в факсимильных системах передачи черно-белых изображений с одномерным кодированием достигает по имеющимся сообщениям величины 5:1. Обобщения метода кодирования длин серий, связанные с переходом к двум пространственным переменным [37—39], доводят это отношение до 10: 1.