DCT или Вниз по кроличьей норе (часть вторая, ортогональная)

«Подумать только, что из-за какой-то вещи

можно так уменьшиться, что превратиться в ничто»

Льюис Кэрролл, «Алиса в стране чудес»



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



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



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





Примечание.

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



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



Рассматривают преимущественно ортогональные преобразования. Вспомним, что требования предъявляемые к преобразованию включают его эффективность, с точки зрения потребления памяти, числа арифмитеческих операций и легкости аппаратной реализации. А значит преобразование должно быть линейным. То есть преобразованные значения b(i) получаются путем линейной комбинации исходных значений a(i) и коэффицентов преобразования d(i,j):





Но линейность не определяет ортогональное преобразование, а является одним из его свойств. Для того, чтобы преобразование было ортогональным, необходимо, чтобы его матрица преобразования состояла из взаимно ортогональных векторов. Зачем нам это нужно? Обратимся к еще одному примеру.



Рассмотрим блок сэмплов яркости размерностью 4x4. Назовем его A.






Примечание
В видеокодировании принято оперировать блоками 8x8. Для упрощения примера я взял размер в четыре раза меньше. Почему 8x8 и не больше? А может лучше сразу брать 64x64 блок? Вопрос на приз.



Прислушиваясь к сигналам из космоса выберем в качестве матрицы преобразования следующую матрицу:






Примечание
Что за дела? Откуда ½? А этого требует закон сохранения энергии. ;) Объясните – получите приз.



Применим преобразование для текущего блока (A):







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





Мы добились нужного результата, сосредоточив всю энергию в первом элементе. При этом преобразование обратимо, то есть мы всегда можем получить первоначальные значения.



Любителям градиентов понравится картинка (до и после):





Так из каких же соображений выбирается матрица?



Преимущественно из логических предпосылок. Мы знаем, что хотим получить – матрицу с особым распределением энергии, сосредоточенной в верхнем левом блоке.



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



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



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



Таким образом, мы построили преобразование, которое отвечает всем вышеобозначенным требованиям.



Внимательный читатель давно заметил аббревиатуру DCT в заголовке. Что это? Да я и сам не знаю Об этом в следующий раз.


For more complete information about compiler optimizations, see our Optimization Notice.
Categories: