Алгоритмы цифровой компрессии изображений с использованием ортогональных преобразований. Дискретное косинусное преобразование сигналов изображения

Преобразования, которые используются для сжатия изображений должны быть быстрыми, и, по возможности, легко реализуемыми на компьютере. Это прежде всего предполагает, что такие преобразования должны быть линейными. То есть, преобразованные величины С{ являются линейными комбинациями (суммами с некоторыми множителями или весами) исходных величин (пикселов) dj, причем соответствующим множителем или весом служит некоторое число Wij (коэффициент преобразования). Значит, С{ - ]Г\- djWij, где г, j = 1,2,..., п. Например, при п = 4 это преобразование можно записать в матричной форме которая в общем случае примет следующий вид: С = W D. Каждый вектор-столбец матрицы W называется «базисным вектором».

Важной задачей является определение коэффициентов преобразования wij. Основное требование заключается в том, чтобы после преобразования величина с\ была бы большой, а все остальные величины С2,сз,... стали бы малыми. Основное соотношение С{ = Ylj djWij предполагает, что С{ будет большим, если веса Wij будут усиливать соответствующие величины dj. Это произойдет, например, если компоненты векторов wij и dj имеют близкие значения и одинаковые знаки. Наоборот, С{ будет малым, если веса избудут малыми, и половина из них будет иметь знак, противоположный знаку соответствующего числа dj. Поэтому, если получаются большие с*, то векторы W{j имеют сходство с исходным вектором dj, а малые С{ означают, что компоненты wij сильно отличаются от dj. Следовательно, базисные векторы wij можно интерпретировать как инструмент для извлечения некоторых характерных признаков исходного вектора.

На практике веса Wij не должны зависеть от исходных данных. В противном случае, их придется добавлять в сжатый файл для использования декодером. Это соображение, а также тот факт, что исходные данные являются пикселами, то есть, неотрицательными величинами, определяет способ выбора базисных векторов. Первый вектор, тот, который, порождает с\, должен состоять из близких, возможно, совпадающих чисел. Он будет усиливать неотрицательные величины пикселов. А все остальные векторы базиса должны наполовину состоять из положительных чисел, а на другую половину - из отрицательных. После умножения на положительные величины и их сложения, результат будет малым числом. (Это особенно верно, когда исходные данные близки, а мы знаем, что соседние пикселы имеют, обычно, близкие величины.) Напомним, что базисные векторы представляют собой некоторый инструмент для извлечения особенностей из исходных данных. Поэтому хорошим выбором будут базисные векторы, которые сильно различаются друг от друга и, поэтому, могут извлекать разные особенности. Это приводит к мысли, что базисные векторы должны быть взаимно ортогональными. Если матрица преобразования W состоит из ортогональных векторов, то преобразование называется ортогональным. Другое наблюдение, позволяющее правильно выбирать базисные векторы, состоит в том, что эти векторы должны иметь все большие частоты изменения знака, чтобы извлекать, так сказать, высокочастотные характеристики сжимаемых данных при вычислении преобразованных величин.

Первый базисный вектор (верхняя строка W) состоит из одних единиц, поэтому его частота равна нулю. Все остальные векторы имеют две +1 и две -1, поэтому они дадут маленькие преобразованные величины, а их частоты (измеренные количеством смен знаков в строке) возрастают. Эта матрица подобна матрице преобразования Адамара-Уолша (см. уравнение (3.11)). Для примера, преобразуем начальный вектор (4,6,5,2)

Результат вполне ободряющий, поскольку число с\ стало большим (по сравнению с исходными данными), а два других числа стали малыми. Вычислим энергии исходных и преобразованных данных. Начальная энергия равна 4 2 + б 2 + 5 2 + 2 2 = 81, а после преобразования энергия стала 17 2 + З 2 + (-5) 2 + I 2 - 324, что в четыре раза больше. Энергию можно сохранить, если умножить матрицу преобразования W на коэффициент 1/2. Новое произведение W-(4,6,5,2) т будет равно (17/2,3/2, -5/2,1/2). Итак, энергия сохраняется и концентрируется в первой компоненте, и она теперь составляет 8.5 2 /81 = 89% от общей энергии исходных данных, в которых на долю первой компоненты приходилось всего 20%.

Другое преимущество матрицы W состоит в том, что она же делает обратное преобразование. Исходные данные (4,6,5,2) восстанавливаются с помощью произведения W-(17/2,3/2, -5/2,1/2) т.

Теперь мы в состоянии оценить достоинства этого преобразования. Квантуем преобразованный вектор (8.5,1.5,-2.5,0.5) с помощью его округления до целого и получаем (9,1,-3,0). Делаем обратное преобразование и получаем вектор (3.5,6.5,5.5,2.5). В аналогичном эксперименте мы просто удалим два наименьших числа и получим (8. 5,0, -2.5,0), а потом сделаем обратное преобразование этого грубо квантованного вектора. Это приводит к восстановленным данным (3,5.5,5.5,3), которые также весьма близки к исходным. Итак, наш вывод: даже это простое и интуитивное преобразование является хорошим инструментом для «выжимания» избыточности из исходных данных. Более изощренные преобразования дают результаты, которые позволяют восстанавливать данные с высокой степенью схожести даже при весьма грубом квантовании.

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

,

которая в общем случае примет следующий вид: . Каждый вектор-столбец матрицы называется «базисным вектором».

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

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

Этим свойствам удовлетворяет следующая ортогональная матрица:

. (3.5)

Первый базисный вектор (верхняя строка ) состоит из одних единиц, поэтому его частота равна нулю. Все остальные векторы имеют две +1 и две -1, поэтому они дадут маленькие преобразованные величины, а их частоты (измеренные количеством смен знаков в строке) возрастают. Эта матрица подобна матрице преобразования Адамара Уолша (см. уравнение (3.11)). Для примера, преобразуем начальный вектор (4,6,5,2):

.

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

Другое преимущество матрицы состоит в том, что она же делает обратное преобразование. Исходные данные (4,6,5,2) восстанавливаются с помощью произведения .

Теперь мы в состоянии оценить достоинства этого преобразования. Квантуем преобразованный вектор (8.5,1.5,–2.5,0.5) с помощью его округления до целого и получаем (9,1,–3,0). Делаем обратное преобразование и получаем вектор (3.5,6.5,5.5,2.5). В аналогичном эксперименте мы просто удалим два наименьших числа и получим (8.5,0,–2.5,0), а потом сделаем обратное преобразование этого грубо квантованного вектора. Это приводит к восстановленным данным (3,5.5,5.5,3), которые также весьма близки к исходным. Итак, наш вывод: даже это простое и интуитивное преобразование является хорошим инструментом для «выжимания» избыточности из исходных данных. Более изощренные преобразования дают результаты, которые позволяют восстанавливать данные с высокой степенью схожести даже при весьма грубом квантовании.

Одни художники отображают солнце в желтое
пятно, а другие желтое пятно в солнце.
- Пабло Пикассо

«Изображение в полиграфии» - Специфика изображения в полиграфии. Главное свойство полиграфического изображения. Книга. Отличительная черта большинства изобразительных полиграфических произведений. Множественность Массовость Общедоступность. Соединение изображения с текстом. Искусство книги. Шрифт.

«Векторная и растровая графика» - Векторные примитивы задаются с помощью описаний. Принципы построения векторных и растровых изображений. Векторные изображения занимают относительно небольшой объём памяти. Виды компьютерной графики. Векторные изображения описываются десятками, а иногда и тысячами команд. Недостатки растровой графики.

«Компьютерная графика» - Основные проблемы при работе с растровой графикой. Виды компьютерной графики отличаются принципами формирования изображения. Компьютерная графика. Фрактальная графика. Виды компьютерной графики. Большие объемы данных. Пиксель. Сравнительная характеристика растровой и векторной графики. Каждая точка экрана может иметь лишь два состояния – «черная» или «белая».

«Создание графических изображений» - Границы полотна. Задание 4. Создать рисунок, состоящий из автофигур. Создание рисунка с помощью панели инструментов Рисование. Положение графического изображения в тексте. Вставить рисунок из коллекции в текст. Полотно. Сравнительная характеристика растровой и векторной графики. Особенности создания векторного изображения в среде Word 2003.

«Изображение головы человека» - Иные холодные, мертвые лица Закрыты решетками, словно темница. Другие - как башни, в которых давно Никто не живет и не смотрит в окно. Какие бывают портреты? Пропорции лица человека. Изображение черт лица. Лицо и эмоции человека. Н. Заболоцкий. Какие бывают лица? Рисунок головы человека. Поистине мир и велик и чудесен!

«Растровые изображения» - Выводы по эксперименту. Красный. Какие основные цвета использует ком-пьютер? Растровое кодирование графической информации. Растровое изображение. Пиксели разных цветов. Голубой (бирюзовый). Серый. Розовый. Палитра современных компьютеров. Все цвета можно пронумеровать, а каждый номер перевести в двоичный код.

Контрольная

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

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

2.4. Алгоритмы трансформирования исходных изображений на основе ортогональных преобразований (С какой целью могут использоваться алгоритмы трансформирования исходных изображений на основе ортогональных преобразований? Что общего и в чём различия между дискретным преобразованием Фурье и другими видами ортогональных преобразований?).

В некоторых случаях, для сокращения объёма данных или облегчения процедуры выделения признаков объектов на последующих этапах распознавания, целесообразно предварительно преобразовывать исходный двумерный массив [ Е i , j ] в массив значений коэффициентов [ F u , v ], имеющий такой же формат MxN, как и исходное изображение.

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

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

Секвентой называется величина, равная половине среднего числа пересечений нуля в единицу времени или на единицу длины.

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

Рис. 2. 3. Распределение энергии сигнала между отдельными элементами
в исходном массиве (а) и в трансформанте (б).

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

Рассмотрим некоторые наиболее распространённые виды ортогональных преобразований, применяемых при цифровой обработке изображений.

Здесь коэффициенты F u в общем случае являются комплексными числами

Дискретное преобразование Фурье

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

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

Преобразование Уолша (при M = N )

В свою очередь, коэффициенты b k (Z ) определяются следующим образом: b k (Z ) равен значению k -того разряда двоичного кода числа Z , состоящего из l двоичных разрядов. Если, например, Z = 10, т.е. 10 10 =1010 2 , то
b 0 = 0; b 1 = 1; b 2 = 0; b 3 = 1.

b k — определяются в соответствии с правилом их определения в преобразовании Уолша.

Преобразование Адамара (при M = N )

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

Пусть [Е i , j ] — массив исходного изображения форматом NxN , где j — номер строки, i — номер столбца элементов (номер элементов в строке); [ F u , v ] — трансформанта изображения, которая имеет тот же формат NxN , где u и v соответственно номер строки и номер столбца элементов трансформанты. Тогда, в общем случае, независимо от вида ортогонального преобразования, запишем

где a (i , j , u , v ) и b (i , j , u , v ) — базисные функции прямого и обратного преобразований соответственно.

С практической точки зрения важно отметить, что все рассмотренные выше виды ортогональных преобразований являются разделимыми по переменным. Таким образом, вычисление прямых и обратных двумерных ортогональных преобразований удаётся свести к последовательному выполнению одномерных преобразований

Здесь а стр (i , u ), b (i , u ) и a (j , v ), b (j , v ) — базисные функции прямого и обратного преобразований, соответственно вдоль направления строк и столбцов.

Для удобства записи и вычислений целесообразно использовать матричный аппарат

Здесь [А э ] и [ А стр ] — матрицы прямого преобразования; [ В э ] и [ В стр ] — матрицы обратного преобразования; [А стр ] т и [В стр ] т — матрицы, полученные в результате транспонирования матриц [ А стр ] и [ В стр ].

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

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

А также другие работы, которые могут Вас заинтересовать
7090.		Мировая экономика. Ответы на экзаменационные вопросы	255.04 KB
	Мировая экономика. Ответы на экзаменационные вопросы Сущность мировой экономики и мирового (всемирного) хозяйства Понятие мировая экономика в современной экономической литературе употребляется для обозначения как системы государств, так и эконо...
7091.		Религии мира. Учебное пособие	188.67 KB
	Введение Исследователь, прилетевший на нашу планету из космоса, мог бы сделать вывод, что мы страдаем от непристойной и очень загадочной болезни с удивительно большим спектром симптомов. Одних она заставляет безжалостно жечь, резать или бомбить свои...
7092.		Средневековая схоластика Ф. Аквинского	43.53 KB
	Средневековая схоластика Ф. Аквинского Характеристика Средних веков Эпоха средневековья длилась более тысячи лет. Ученые считают началом средних веков - падение Римской империи (V век н.э.), когда христианская религия окончательно утверди...
7093.		Маркетинговое обслуживание потребителей	49.99 KB
	Введение В условиях рыночной экономики многие проблемы товаропроизводителей не могут быть в полной мере решены с помощью традиционных методов управления. Требуется создавать систему менеджмента, обеспечивающую эффективность хозяйственной единицы в н...
7094.		Магнитометры на СКВИДах	108.5 KB
	Магнитометры на СКВИДах. Сверхпроводимость. Основные параметры сверхпроводников. Явление сверхпроводимости состоит в том, что при некоторой температуре, близкой к абсолютному нулю, электро сопротивление в некоторых материалах исчезает. Эта темпера...
7095.		Социолингвистика. Лекции. Социальная стратификация языка	190 KB
	Лекции по курсу Социолингвистика. Лекция 1. Предмет социолингвистики и методы социолингвистического анализа. Предметом изучения социолингвистики является проблема человек и общество. Непосредственным объектом социолингвистики является...
7096.		Технология эмульгированных мясопродуктов	65.69 KB
	Лекция 4. Технология эмульгированных мясопродуктов План АССОРТИМЕНТ КОЛБАСНЫХ ИЗДЕЛИЙ, СЫРЬЕ И МАТЕРИАЛЫ ДЛЯ ИХ ПРОИЗВОДСТВА Ассортимент колбасных изделий Характеристика сырья Колбасные оболочки Упаковочные и перевязочны...
7097.		Основы программирования на языке Паскаль	81.53 KB
	Краткий курс лекций. Основы программирования на языке Паскаль Введение. Прежде всего, следует напомнить, что изучение языка программирования представляет собой знакомство с формальными правилами записи алгоритмов для их последующего выполнения компьют...
7098.		Психосоматика. Курс лекций	279 KB
	Конспект лекций Психосоматика Психосоматика: определение понятия. Конверсионные симптомы. Функциональные синдромы. Психосоматозы Патогенез психосоматических расстройств Психосоматические теории и модели. Характерологически ориентированные направле...

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

Напомним, что функции x(t) и y(t) называются ортогональными на отрезке (t 1 , t 2), если их скалярное произведение равно нулю

Это определение может быть распространено на дискретные сигналы, представляемые последовательностями чисел. Дискретные сигналы х(п) и у(п), имеющие по N отсчетов, называются ортогональными, если выполняется условие

Одним из наиболее известных примеров применения ортогонального преобразования является разложение периодического сигнала х в ряд Фурье

где: ; Т - период повторения сигнала x(t).

Действительные коэффициенты ряда Фурье, определяются соотношениями

В комплексной форме разложение в ряд Фурье имеет вид:

Комплексные амплитуды гармоник;

j - мнимая единица.

В ряд Фурье может быть разложен не только периодический сигнал, имеющий период Т, но и сигнал, отличный от 0 только на интервале времени (-T/2, Т/2). В этом случае используется периодическое продолжение сигнала на всю ось времени с периодом Т.

Рассмотрим дискретный сигнал х(п), отличный от 0 при п = 0,1, …, N-1. Для такого сигнала также можно ввести разложение по базису синусоидальных функций. Так как частотный спектр дискретизируемого сигнала должен быть ограничен сверху в соответствии с условием теоремы Котельникова, в разложении дискретного сигнала остается конечное число частотных составляющих, представляющих собой дискретные комплексные гармонические функции. Такое разложение, называемое дискретным преобразованием Фурье (ДПФ), имеет вид

N=0, 1…N-1,(2.6)

где коэффициенты ДПФ X(k) определяются соотношением

K=0, 1…N-1,(2.7)

Напомним, что нахождение коэффициентов Х(k) по (2.7) обычно называют прямым ДПФ, а получение сигнала по этим коэффициентам в соответствии с (2.6) - обратным ДПФ.

В этих соотношениях вместо интегралов появились суммы, так как исходный сигнал не непрерывный, а дискретный. Частоте, используемой в разложении аналоговых сигналов и имеющей размерность рад/с, в ДПФ соответствует безразмерная величина, где k=0, 1…N-1. Отношение показывает, какую часть частоты дискретизации составляет частота данной дискретной гармоники.

Коэффициенты ДПФ Х(k) и экспоненциальные множители в (2.6), (2.7) являются комплексными числами. Каждое комплексное число запоминается в цифровом ЗУ в виде пары действительных чисел, представляющих его действительную и мнимую части. Сложение двух комплексных чисел требует выполнения двух операций сложения действительных чисел - отдельно складываются действительные и мнимые части. Умножение двух комплексных чисел требует выполнения четырех операций умножения и двух операций сложения действительных чисел. Таким образом, выполнение ДПФ в комплексной форме приводит к существенному увеличению необходимого объема ЗУ и времени вычислений.

Чтобы иметь дело только с действительными числами, обычно используют разложение с помощью дискретного косинусного преобразования (ДКП), описываемого соотношением:

где коэффициенты ДКП определяются по формулам

Как и в случае ДПФ, нахождение коэффициентов C(k) по (2.9) называется прямым ДКП, а представление сигнала в виде (2.8) называется обратным ДКП.

Аналогично можно записать соотношения для прямого и обратного ДПФ и ДКП в двумерном случае. Двумерный дискретный сигнал, например, отдельный кадр цифрового телевизионного сигнала, представляется матрицей значений х(т,п), где т = 0 ... М-1 - номер отсчета в строке, п = 0 .., N-1 - номер строки в кадре.

Прямое двумерное ДПФ имеет вид:

k=0…M-1, l=0…N-1,

где X(k,l) - комплексные коэффициенты ДПФ, отображающие пространственно-частотный спектр изображения.

Обратное двумерное ДПФ представляет разложение изображения по базисным функциям:

Коэффициенты двумерного прямого ДКП определяются по формулам:

Обратное двумерное ДКП имеет вид:

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

На рис. 2.3 показаны в виде полутоновых картинок базисные функции двумерного ДКП для М = 8, N = 8. Светлые участки соответствуют положительным значениям, а темные - отрицательным.

Рис. 2.3.

Показаны примеры:

• а) k = 1, l= 0; б) k = 0, l = 1; в) k = 1, l = 1;
• г) k = 0, l = 2; д) k = 1, l = 2; е) k = 2 ,l = 2;
• ж) k = 4, l = 2; з) k = 7, l = 1; и) k = 7, l = 7.

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

В соответствии с , в целом можно оценить затраты вычислительных ресурсов при выполнении прямого и обратного ДПФ, как пропорциональные N 2 . Аналогично можно показать, что вычисление двумерных прямого и обратного ДПФ требует выполнения количества операций, пропорционального N 2 М 2 .

Например, вычисление ДПФ для квадратного блока изображения, содержащего 8x8 элементов (пикселей), потребует выполнения примерно 16·10 3 операций умножения и сложения. А вычисление ДПФ черно-белого телевизионного кадра обычного стандарта разложения, содержащего 720x576 пикселей, потребует выполнения около 8·10 11 операций. Если вычисления производятся на компьютере, выполняющим 10 6 операций над действительными числами в секунду, время вычисления ДПФ составит 8·10 5 с или более 200 ч. Очевидно, что для вычисления ДПФ телевизионных изображений в реальном времени, т. е. за период кадровой развертки, необходимо искать пути сокращения количества требуемых операций.

Наиболее радикальный способ уменьшения объема вычислений заключается в применении открытых в 60-е годы быстрых алгоритмов ДПФ, называемых алгоритмами быстрого преобразования Фурье (БПФ). Подробно быстрые алгоритмы вычисления ДПФ описаны во многих литературных источниках и здесь не рассматриваются.

Двумерное БПФ может быть разложено на последовательность одномерных. Число требуемых операций оказывается пропорциональным. Для приведенного выше примера телевизионного кадра, состоящего из 720x576 пикселей, это значение оказывается равным примерно 8·10 6 , что в 10 5 раз меньше, чем число операций, требуемое для непосредственного вычисления ДПФ.

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

В современной аппаратуре, в том числе и для цифрового телевидения, ДПФ и ДКП, как правило, выполняются в реальном времени с применением цифровых процессоров обработки сигналов (ЦПОС) или специальных аппаратных средств, например, параллельных вычислительных устройств.

ДКП лежит в основе наиболее широко используемых в настоящее время методов кодирования JPEG, MPEG-1, MPEG-2, описание которых будет дано в п. 2.2.