24. Основные методы сжатия изображений апк, кдс и код Хаффмена.

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

Следует иметь ввиду, что устранение избыточности ведет к ухудшению качества принимаемого изображения ( ухудшается помехоустойчивость). В осмысленных изображениях имеются сильные корреляционные связи между элементами. Именно поэтому изображения могут быть выделены на фоне даже сильных помех. Например, буква П передается телеграфным кодом МТК2. При наличии хотя бы одной ошибки, если передача осуществляется не избыточным кодом, будет принята другая буква. Если же буква П передается при помощи факсимильного аппарата, то одиночная ошибка не исказит структуру буквы П. Даже при наличии большого числа ошибок, приходящихся на одну букву, разрушить изображение буквы трудно – буква опознается. При устранении избыточности – помехоустойчивость уменьшается.

Оценка различных методов сжатия происходит по трем критериям: коэффициенту сжатия, помехоустойчивости и сложности алгоритма сжатия. Рассмотрим некоторые, получившие практическое применение, алгоритмы сжатия факсимильного изображения – КДС, АПК и код Хаффмена.

Кодирование длин серий ( КДС ).

При кодировании по этому методу двухуровневый факсимильный сигнал от каждой строки развертки разбивается на отдельные элементы – дискретизируется. Элементам белого приписывается значение - «0» , а черного – «1». При этом учитывается, что в среднем длины черных участков изображения много короче белых. Длины белых участков кодируются шестиэлементными кодовыми комбинациями ( до 63 элементов сигнала ), а отрезки черного – трехэлементными ( до 7 элементов сигнала). Кодирование строки всегда начинается с белого, для определения начала строки передается служебная комбинация из 9 нулей. При кодировании белого различают отрезки: меньше 63 элементов изображения; больше 63 элементов, но не кратные 63; равные или кратные 63 элементам. В первом случае отрезки кодируются шестиэлементными комбинациями ( комбинации 1, 3, 5 на рисунке). Во втором случае длина отрезка кодируется несколькими шестиэлементными комбинациями, причем все они кроме последней состоят из одних единиц. В третьем случае длина отрезка кодируется одной или несколькими шестиэлементными кодовыми комбинациями, состоящими из одних единиц, и для определения окончания белого передается служебная кодовая комбинация из шести нулей. При кодировании черного различают отрезки: меньше 7 элементов изображения; больше, но не кратные 7; равные или кратные 7. Они кодируются также, как и отрезки белого, но при этом используются трехэлементные кодовые комбинации.

Коэффициент сжатия при КДС, если длины серий кодируются равномерными кодами разной длины, вычисляется по формуле:

где :

-длина кода начала строки.

-длина кода яркости первого элемента.

-длина равномерных кодов, используемых для кодирования длин серий белого и черного соответственно.

N– числоэлементов изображения на строке.

Риз –вероятность новых значений.

Качественно для отдельной строки ( рисунок выше ) 73- элементный дискретный сигнал закодирован 24 двоичными элементами ( в 3 раза меньше ).

Метод КДС обладает низкой помехоустойчивостью. Неверно принятый код длины серии приводит так называемому «треку ошибок», поскольку декодер воспроизводит серию не той длины. Таким образом, даже одиночная ошибка за счет помехи в канале приводит к «разрушению» строки. Методы КДС и его разновидности работоспособны при вероятности ошибки в канале не хуже . Реальные каналы имеют вероятность ошибки на несколько порядков выше. Поэтому применять методы КДС без специальных мер по повышению помехоустойчивости нельзя.

Адресно-позиционное кодирование ( АПК ).

По сравнению с КДС метод АПК обладает большей помехоустойчивостью, но его эффективность ( коэффициент сжатия ) ниже. При кодировании штриховых изображений возможны новые значения: переход из белого в черное и переход из черного в белое. Координата элемента с новым значением яркости ( КНЗ ) отсчитывается относительно начала строки изображения. Для безошибочного восстановления изображения сжатым данным необходимо в начале кодограммы строки указать признак ( код ) ее начала и значение яркости первого элемента строки:

[код начала строки][код первого элемента][КНЗ][КНЗ]…..[КНЗ]

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

При АПК нельзя достичь высоких коэффициентов сжатия, если насыщенность изображения деталями высока, поэтому его целесообразно применять при кодировании изображений, для которых вероятность новых значений не превышает 0,2 – 0,3. Достоинством АПК является его низкая чувствительность к ошибкам. Поражение ошибкой кода координаты нового значения приводит к искажению небольшой группы элементов строки до следующего нового значения яркости. Повысить эффективность алгоритмов сжатия КДС и АПК можно, если кодирование длин серий (КДС) или координат ( АПК ) производить оптимальным кодом. В факсимильной аппаратуреМККТТ рекомендовано использовать метод КДС с кодированием длин серий модифицированным кодом Хаффмена. Эффективность сжатия повышается в 5-15 раз.

Код Хаффмена.

Является оптимальным неравномерным кодом ( ОНК ). Может использоваться для кодирования различных сообщений, в том числе и факсимильных. При кодировании двухградационных факсимильных изображений в качестве символов сообщений принимаются длины белых и черных серий. При построении кода учитывается статистика исходной последовательности, а именно , наиболее вероятные символы кодируются наиболее короткими кодовыми комбинациями, а наименее вероятные –наиболее длинными. В качестве примера приведен фрагмент кодовой таблицы.

Числа элементов в серии	Кодовые комбинации
	Белого	Черного
1 2 3 4 5 6 7 … 58 … 63 64 … 128	000111 0111 1000 1011 1100 1110 1111 … 0101101 … 00110100 11011 … 10010	010 11 10 011 0011 0010 00011 … 000001011001 … 000001100111 000001111 … 000011001000

К недостаткам ОНК относятся их чувствительность к изменению статистических характеристик источника и низкая помехоустойчивость.

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