Мультимедийные технологии

 

Рис.2.5.

A₃, A₄, A₅, A₆ и приведены вероятности, с которыми они появляются. Построение кодовой таблицы начинается с того, что два символа с наименьшими вероятностями объединяются в узел кодового дерева, которому приписывается их суммарная вероятность. Речь идет о символах A₅ и A₆, суммарная вероятность которых равна 0,14. Далее объединяются следующие символы или узлы с наименьшей вероятностью, как это показано на рисунке. Этот процесс продолжается до тех пор, пока ветви кодового дерева не сойдутся к одному узлу, расположенному в вершине. После этого ветви дерева в зависимости от того, в какую сторону они расходятся от узла, обозначаются нулями или единицами (на рис. 2.5 правые ветви обозначены нулями, а левые единицами). Для того, чтобы найти значение кодового слова, которое следует приписать каждому символу, необходимо идти от вершины кодового дерева к данному символу, записывая нули или единицы, которыми обозначены пройденные ветви.

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

8 ПРИНЦИПЫ КОДИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ

ОРТОГОНАЛЬНЫХ ПРЕОБРАЗОВАНИЙ

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

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

      Рис. 3.1.

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

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

      

,

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

      

,

где - ядро обратного преобразования. Если преобразование разделимо, т.е. если

      

, ,

а нас  будут интересовать разделимые преобразования, то оно может быть выполнено в два этапа, вначале по всем столбцам, а затем по всем строкам

       ,                             (3.5)

и соответственно

       .                          (3.6)

      Для удобства записи и вычислений используют матричный аппарат. В матричной форме разделимые ортогональные преобразования записываются следующим образом

       ,     ,                               (3.7)

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

      

,

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

      

.

      Учитывая, что  , , а также соотношения и , справедливые для ортогональных матриц, имеем

       ,                                  (3.8)

где , - матрицы, полученные в результате обращения матриц .

      Базисные  функции , , , в формулах (3.5) и (3.6) (или, что - то же самое, ортогональные матрицы в формулах (3.7) и (3.8)) определяются применяемым ортогональным преобразованием. Так, например, в случае двумерного дискретного преобразования Фурье (ДПФ) базисные функции представляют собой комплексные экспоненты, а сами ортогональные преобразования имеют вид

      

,

      

,

в этих формулах множитель  имеет смысл пространственной частоты,  .

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

      Ортогональные преобразования изображений допускают  ряд следующих интерпретаций.

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

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

      Спектральные  коэффициенты можно также рассматривать  и как функции взаимной корреляции между преобразуемым изображением и соответствующими базисными изображениями.

      И, наконец, ортогональные преобразования можно рассматривать как такой поворот N – мерной системы координат ( ), в которой преобразуемое изображение, состоящее из N отсчетов, представляется N – мерным вектором, при котором корреляция между его компонентами сводится к минимуму.

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

9  ДИСКРЕТНОЕ КОСИНУСНОЕ ПРЕОБРАЗОВАНИЕ

 

      Двумерное дискретное косинусное преобразование является разделимым и может быть выполнено по формулам

       ,       (3.9)

       ,     (3.10)

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

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

      

      Рис. 3.2.  

      Учитывая, что все изображение содержит блоков, находим количество вычислительных операций, которые необходимо выполнить, чтобы осуществить преобразование всего изображения , т.е. в раз меньше, чем без разбиения на блоки. Поясним изложенное примером. Предположим, что исходное изображение имеет размер отсчетов, а размер блока составляет отсчетов.  Тогда в соответствии с приведенными выше рассуждениями без разбиения изображения на блоки потребовалось бы 171992678400 вычислительных операций, при разбиении же изображения на блоки потребуется всего лишь 106168320, т.е. в 1620 раз меньше, чем в первом случае. Из этого следует, что чем более мелкими будут блоки, тем большим будет их число и тем большим будет сокращение числа операций, необходимых для выполнения ортогонального преобразования, в данном случае ДКП. Однако, как показывает детальный анализ этой проблемы, делать блоки меньшими, чем , или в крайнем случае отсчетов, не следует, так как корреляционные связи в изображении распространяются примерно на этот интервал и дальнейшее уменьшение размеров блоков  повлечет за собой  увеличение амплитуд спектральных коэффициентов с большими индексами , и, как следствие, уменьшение сжатия данных.