М.А. Чичева
Быстрые алгоритмы
дискретного косинусного преобразования
Электронное учебное пособие
САМАРА
2010
2
Авторы:
ЧИЧЕВА Марина Александролвна,
В данном пособии рассмотрены быстрые алгоритмы дискретного косинусного
преобразования (ДКП) различных длин. <...> Показано применение ДКП в различных задачах
обработки изображений. <...> На ДКП основаны известные методы
компрессии изображений (стандарты JPEG, MPEG и др.), эффективные методы фильтрации,
методы извлечения признаков и т.д. <...> Широкое применение ДКП обусловлено уникальным
сочетанием его позитивных качеств. <...> Во-первых, базисные функции ДКП для многих
сигналов, описываемых моделями стационарных случайных процессов, близки к базисным
функциям преобразования Карунена-Лоэва (ПКЛ), т.е. позволяют описывать сигнал с
заданной точностью минимальным числом спектральных компонент. <...> Во-вторых, в отличие
от ПКЛ, для ДКП существуют быстрые алгоритмы вычисления. <...> В частности, ДКП длины N=8 является
базовым преобразованием для целого ряда современных стандартов кодирования
(JPEG,
MPEG,
ITU-T
[25,
31]). <...> Попытки построения
адаптивных алгоритмов кодирования на основе ДКП [13, 21, 22, 28] связаны, обычно,
с резким увеличением вычислительной сложности ДКП при возрастании длины
преобразования. <...> Это связано с тем, что быстрые алгоритмы (БА) ДКП при N>8
изучены в значительно меньшей степени, чем ДКП длины 8, которым посвящено
множество работ [1, 9, 20, 25, 29]. <...> Большинство из известных БА ДКП, синтезированных для преобразований
произвольных длин обладают относительно низкой асимптотической арифметической
сложностью, но не учитывают реализационной специфики "коротких" длин:
относительно небольшого числа различных значений базисных функций, высоких
требований к структурной простоте, которая при небольшой длине преобразования
является определяющей характеристикой быстродействия и т.д. <...> (1.3)
где
x (k )
при 0 ≤ k ≤ N − 1
y (k ) =
.
x ( 2 N − k − 1) при N ≤ k ≤ 2 N − 1
Вычисление преобразования (1.3) для N=8 и при использовании <...>
Быстрые_алгоритмы_дискретного_косинусного_преобразования.pdf
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ
УНИВЕРСИТЕТ имени академика С.П.КОРОЛЕВА
(НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)»
М.А. Чичева
Быстрые алгоритмы
дискретного косинусного преобразования
Электронное учебное пособие
САМАРА
2010
Стр.1
2
Авторы:
ЧИЧЕВА Марина Александролвна,
В данном пособии рассмотрены быстрые алгоритмы дискретного косинусного
преобразования (ДКП) различных длин. Показано применение ДКП в различных задачах
обработки изображений. Для полноты изложения приведены основные сведения из теории
быстрых алгоритмов дискретных преобразований. На ДКП основаны известные методы
компрессии изображений (стандарты JPEG, MPEG и др.), эффективные методы фильтрации,
методы извлечения признаков и т.д. Широкое применение ДКП обусловлено уникальным
сочетанием его позитивных качеств. Во-первых, базисные функции ДКП для многих
сигналов, описываемых моделями стационарных случайных процессов, близки к базисным
функциям преобразования Карунена-Лоэва (ПКЛ), т.е. позволяют описывать сигнал с
заданной точностью минимальным числом спектральных компонент. Во-вторых, в отличие
от ПКЛ, для ДКП существуют быстрые алгоритмы вычисления. В-третьих, так называемое
"четное периодическое" продолжение сигнала, предполагаемое в ДКП, позволяет устранить
вредные краевые эффекты при блочной обработке изображений.
Пособие предназначено для магистров по направлению 010400.68 “Прикладная
математика и информатика”, обучающихся по программе «Математические и компьютерные
методы обработки изображений и геоинформатики».
Стр.2
3
1. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ БЫСТРЫХ
АЛГОРИТМОВ ДИСКРЕТНЫХ ОРТОГОНАЛЬНЫХ ПРЕОБРАЗОВАНИЙ
1.1. Постановка задачи, основные идеи
Дискретное косинусное преобразование (ДКП):
( )
x m = λm ∑ ( )cos π + , (m = 0, ..., N-1),
⌢
N−1
x n
n 0
=
где mλ - нормирующие множители [1]:
λ =
m
(n m12
N
)
N при m
N при m
1 ,
2 ,
(1.1)
= 0,
(1.2)
≠ 0,
является одним из основных дискретных ортогональных преобразований (ДОП),
используемых в обработке изображений. В частности, ДКП длины N=8 является
базовым преобразованием для целого ряда современных стандартов кодирования
(JPEG, MPEG, ITU-T [25, 31]). Однако метод блочного кодирования с
преобразованием (на котором основываются перечисленные стандарты) не в полной
мере учитывает особенности конкретного изображения. Попытки построения
адаптивных алгоритмов кодирования на основе ДКП [13, 21, 22, 28] связаны, обычно,
с резким увеличением вычислительной сложности ДКП при возрастании длины
преобразования. Это связано с тем, что быстрые алгоритмы (БА) ДКП при N>8
изучены в значительно меньшей степени, чем ДКП длины 8, которым посвящено
множество работ [1, 9, 20, 25, 29].
Большинство из известных БА ДКП, синтезированных для преобразований
произвольных длин обладают относительно низкой асимптотической арифметической
сложностью, но не учитывают реализационной специфики "коротких" длин:
относительно небольшого числа различных значений базисных функций, высоких
требований к структурной простоте, которая при небольшой длине преобразования
является определяющей характеристикой быстродействия и т.д.
Стр.3