Мультимедийные технологии (стр. 5 из 7)
Ортогональные преобразования изображений допускают ряд следующих интерпретаций.
Во-первых, двумерное преобразование изображения можно рассматривать как его разложение в обобщенный двумерный спектр, а спектральные коэффициенты – как амплитуды соответствующих спектральных составляющих. В том случае, если применяются негармонические базисные функции, как, например, в случае преобразования Адамара, понятие частоты необходимо обобщить и пользоваться понятием секвенты. Напомним, что секвентой (ненормированной) называется величина, равная половине среднего числа пересечения нуля в единицу времени (на единицу длины).
Другая возможная интерпретация обусловлена тем, что матрица преобразуемого изображения и матрицы базисных изображений имеют одинаковые размеры, т.е. состоят из одного и того же числа строк и столбцов. Это дает возможность спектральные коэффициенты рассматривать как весовые коэффициенты, с которыми необходимо просуммировать базисные изображения, чтобы получить исходное изображение.
Спектральные коэффициенты можно также рассматривать и как функции взаимной корреляции между преобразуемым изображением и соответствующими базисными изображениями.
И, наконец, ортогональные преобразования можно рассматривать как такой поворот N – мерной системы координат (
), в которой преобразуемое изображение, состоящее из N отсчетов, представляется N – мерным вектором, при котором корреляция между его компонентами сводится к минимуму.Важным свойством ортогональных преобразований является сохранение метрики, благодаря этому свойству евклидово расстояние между изображениями равно евклидову расстоянию между их образами (спектральными отображениями).
9 ДИСКРЕТНОЕ КОСИНУСНОЕ ПРЕОБРАЗОВАНИЕ
Двумерное дискретное косинусное преобразование является разделимым и может быть выполнено по формулам
, (3.9) 
, (3.10)где функции
и 
определены следующим образом: 
, 
при 
. Как известно, вычисление двумерного дискретного косинусного преобразования по приведенным формулам требует для его выполнения 
операций умножения и сложения, что создает серьезную проблему, поскольку значения 
для реальных изображений составляют несколько сотен. В связи с этим были предприняты исследования, направленные на сокращение требуемого объема вычислений. В результате этих исследований были разработаны два, дополняющих друг друга метода.Первый метод заключается в том, что кодируемое изображение размером
отсчетов предварительно разбивается на отдельные блоки размером 
отсчетов, а затем независимо каждый из блоков подвергается дискретному косинусному преобразованию. Поскольку каждый блок содержит в 
раз меньше отсчетов, чем исходное изображение, то на его преобразование в соответствии с формулами (3.9, 3.10), потребуется уже не 
операций (в случае, когда 
потребовалось бы соответственно 
операций), а только 
вычислительных операций. 
Рис. 3.2.
Учитывая, что все изображение содержит
блоков, находим количество вычислительных операций, которые необходимо выполнить, чтобы осуществить преобразование всего изображения 
, т.е. в раз меньше, чем без разбиения на блоки. Поясним изложенное примером. Предположим, что исходное изображение имеет размер 
отсчетов, а размер блока составляет 
отсчетов. Тогда в соответствии с приведенными выше рассуждениями без разбиения изображения на блоки потребовалось бы 171992678400 вычислительных операций, при разбиении же изображения на блоки потребуется всего лишь 106168320, т.е. в 1620 раз меньше, чем в первом случае. Из этого следует, что чем более мелкими будут блоки, тем большим будет их число и тем большим будет сокращение числа операций, необходимых для выполнения ортогонального преобразования, в данном случае ДКП. Однако, как показывает детальный анализ этой проблемы, делать блоки меньшими, чем , или в крайнем случае 
отсчетов, не следует, так как корреляционные связи в изображении распространяются примерно на этот интервал и дальнейшее уменьшение размеров блоков повлечет за собой увеличение амплитуд спектральных коэффициентов 
с большими индексами 
, и, как следствие, уменьшение сжатия данных.Второй метод сокращения требуемого объема вычислений при выполнении дискретного косинусного преобразования состоит в применении быстрого алгоритма вычисления ДКП, при котором требуемый объем вычислений (умножений и сложений) сокращается с
до 
.Поясним эффективность этого метода на примере, полагая, что размер блока составляет
отсчетов изображения. При непосредственном вычислении спектральных коэффициентов по формулам (3.9, 3.10) потребовалось бы выполнить 65536 операций умножения и сложения. Используя же быстрый алгоритм, потребуется выполнить всего лишь 2048 операций, т.е. в 32 раза меньше, чем в первом случае.В настоящее время при выполнении ДКП используют оба описанные метода сокращения количества вычислительных операций, поскольку они, дополняя друг друга, позволяют существенно ускорить вычисления.
8 ОПТИМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ДВОИЧНЫХ ЕДИНИЦ КОДА МЕЖДУ СПЕКТРАЛЬНЫМИ КОЭФФИЦИЕНТАМИ
В методе, использующем ортогональные преобразования, сжатие данных достигается за счет того, что спектральные коэффициенты, энергия которых мала, квантуются на меньшее число уровней, а, следовательно, на их представление затрачивается меньшее число двоичных единиц кода, чем на представление спектральных коэффициентов с большой энергией.
Рассмотрим задачу распределения двоичных единиц кода между спектральными коэффициентами , при котором обеспечивается наименьший средний квадрат шума преобразования
, обусловленного квантованием (или отбрасыванием) спектральных коэффициентов. Будем считать, что сжимаемое изображение является черно-белым полутоновым, а также, что нам заданы: размер блока 
, требуемый коэффициент сжатия 
и значения средних квадратов спектральных коэффициентов 
.Решение задачи начнем с того, что определим вначале число двоичных единиц кода
, которым мы располагаем при заданном коэффициенте сжатия и которое нам предстоит распределить между спектральными коэффициентами блока. Исходя из того, что для представления каждого пиксела в блоке исходного черно-белого полутонового изображения требуется один байт, т.е. 8 двоичных единиц, найдем, что для представления всего блока без сжатия расходуется 
двоичных единиц кода. Отсюда следует, что при заданном значении коэффициента сжатия 
мы располагаем 
количеством двоичных единиц кода, которые и должны распределить между спектральными коэффициентами.