Ортогональные преобразования. Изображение и его ортогональные преобразования

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

,

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

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

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

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

. (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), которые также весьма близки к исходным. Итак, наш вывод: даже это простое и интуитивное преобразование является хорошим инструментом для «выжимания» избыточности из исходных данных. Более изощренные преобразования дают результаты, которые позволяют восстанавливать данные с высокой степенью схожести даже при весьма грубом квантовании.

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

Преобразования, которые используются для сжатия изображений должны быть быстрыми, и, по возможности, легко реализуемыми на компьютере. Это прежде всего предполагает, что такие преобразования должны быть линейными. То есть, преобразованные величины С{ являются линейными комбинациями (суммами с некоторыми множителями или весами) исходных величин (пикселов) 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.114) ее абсолютным значением. Это преобразование необратимо.

Следует упомянуть также предложенные для кодирования изображений слэнт-преобразование , «слэнт-Хаар» преобразование и преобразование по дискретному базису .

Можно показать, что большинство используемых в настоящее время в обработке изображений унитарных преобразований может быть представлено в виде сумм кронекеровских произведений элементарных матриц матриц перестановки и некоторых других. Такое представление матриц Хаара, Адамара, Уолша, Уолша-Пэли, модифицированной матрицы Адамара, матрицы Адамара - Хаара, матрицы ДПФ, обобщенной матрицы Уолша показано в табл. 3.5 с использованием следующих обозначений:

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

(см. скан)

Продолжение табл. 3.5 (см. скан)

Это представление создает удобную основу для сравнения преобразований. Так, сравнивая представления для матрицы легко «заметить, что они отличаются инверсным порядком следования матриц в каждом слагаемом, матрица MHAD отличается от матрицы Адамара HAD тем, что она строится не на

А на и т. д. Для всех этих матриц существуют быстрые алгоритмы умножения их на вектор при выполнении преобразования. Этот факт самым непосредственным образом связан с возможностью представления матриц в виде сумм кронекеровских матриц (см. гл. 4).

На основе описанных одномерных преобразований могут быть построены соответствующие двумерные разделимые преобразования как двойные одномерные:

где М - одна из матриц преобразований, описанных выше; а - двумерный дискретный сигнал; а - его преобразование.

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

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

Применения унитарных преобразований в обработке изображений можно разбить на три группы:

Кодирование изображений;

Выделение признаков для препарирования и распознавания изображений;

Обобщенная фильтрация.

Кодирование изображений - основное в настоящее время применение преобразований (кроме ДПФ). Более того, некоторые из преобразований (например, слэнт-преобразование и преобразование по дискретному линейному базису и др.) были введены специально для использования при кодировании.

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

Использование унитарных преобразований для фильтрации сигналов основано на обобщении понятия фильтрации в частотной области дискретного преобразования Фурье. При фильтрации сигналов с использованием ДПФ выполняется следующее преобразование сигнала:

Матрицы перехода от преобразования Т к ДПФ и наоборот.

Такой подход был предложен в для обобщения оптимальной линейной (винеровской) фильтрации (см. также ).

В зависимости от вида преобразования Т и свойств требуемого фильтра сложность выполнения операции фильтраций (3.139), оцениваемая, скажем, количеством операций, может меняться. В частности, может оказаться, что вместо ДПФ выгоднее использовать более быстрое преобразование Уолша-Адамара несмотря на большую сложность умножения на недиагональную матрицу фильтра в этом случае (см. также § 6.5).

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

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

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

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

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

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