3.5. Преобразование изображенийПонятие преобразования широко применяется в математике. С его помощью решаются многие задачи в различных областях науки. Основная идея состоит в изменении математической величины (числа, вектора, функции или другого объекта) с целью придания ей другой формы, в которой она имеет, возможно, непривычный вид, но имеет полезные свойства. Преобразованная величина используется при решении задачи или при совершении некоторых вычислений, после чего к результату применяется обратное преобразование для возврата к исходной форме. Простым иллюстративным примером могут служить арифметические операции над римскими числами. Древние римляне, по-видимому, знали, как оперировать с такими числами, однако, если требуется, скажем, перемножить два римских числа, то будет более удобно преобразовать их в современную (арабскую) форму, перемножить, а потом представить результат в виде римского числа. Вот простой пример:
Изображение можно сжать, преобразуя его пикселы (которые коррелированы) в представление, где они будут декоррелированными. Произойдет сжатие, если новые величины будут, в среднем, меньше исходных. Сжатие с потерей качества можно затем произвести с помощью квантования результата преобразования. Декодер читает сжатый файл и восстанавливает (точно или приближенно) исходные данные, применяя обратное преобразование. В этом параграфе рассматриваются ортогональные преобразования. В § 4.3 будет обсуждаться под диапазонное преобразование. Слово декоррелиронанные означает, что преобразованные величины являются статистически независимыми. В результате их можно кодировать независимо, что позволяет построить более простую статистическую модель. Образ можно сжать, если в нем имеется определенная избыточность. Избыточность проистекает от корреляции пикселов. Если перевести образ в представление, в котором пикселы декоррелированы, то одновременно произойдет удаление избыточности и образ будет полностью сжат. Начнем с простого примера, в котором образ сканируется растровым способом (то есть, строка за строкой) и группируется в пары прилегающих пикселов. Поскольку пикселы коррелированы, два пиксела
где матрица поворота
(Обращение ортогональных матриц делается с помощью простого транспонирования.) Рис. 3.17. Поворот облака точек. Очевидно, что большинство точек преобразованного «облака» будут иметь координату Поскольку координаты точек известны до и после преобразования, легко вычислить уменьшение корреляции. Сумма Следующий пример поясняет смысл этой величины. Повернем точки (5,5), (6,7), (12.1,13.2), (23,25) и (32,29) по часовой стрелке на 45° и вычислим перекрестную корреляцию до и после поворота. На рис. 3.19 приведена программы Matlab, вычисляющая координаты повернутых точек. Они равны (7.071,0), (9.19,0.7071), (17.9,0.78), (33.9,1.41), (43.13,–2.12) (заметьте, что координаты Теперь можно сжать образ, просто записав преобразованные координаты в выходной файл. Если допустима некоторая потеря информации, то можно сделать квантование всех пикселов, что даст малые значения пикселов. Можно также записывать в сжатый файл все нечетные пикселы (те, которые являются Легко показать, что полная дисперсия пикселов, которая определяется суммой Рис. 3.18. Распределение пикселов до и после поворота. Концентрирование энергии в одной координате имеет и другое преимущество. Можно делать квантование этой координаты более точным, чем квантование второй координаты. Такой способ квантования приводит к лучшему сжатию. Рис. 3.19. Поворот пяти точек. Следующий простой пример иллюстрирует возможности этого ортогонального преобразования. Начнем с точки (4,5) с близкими координатами. С помощью уравнения (3.3) эта точка переходит в
Это простое преобразование легко обобщить на случай любого числа измерений. Вместо пар, можно выбирать тройки точек, триплеты. Каждый триплет становится точкой трехмерного пространства, а все точки образуют «облако» вокруг прямой, проходящей через начало координат под углом 45° к каждой координатной оси. Если эту прямую повернуть так, что она ляжет на ось Этот метод легко распространить на более высокие размерности, с той лишь разницей, что получающиеся пространства уже нельзя будет представить зрительно. Однако, соответствующие матрицы преобразований легко выписываются. Единственно, что приходится учитывать, это то, что размерность не должна быть слишком большой, поскольку результат сжатия на основе поворота зависит от корреляции близких пикселов. Например, если объединять по 24 соседних пиксела в одну точку 24-мерного пространства, то полученные точки, вообще говоря, не будут лежать в малой окрестности «прямой под углом 45° к осям координат», поскольку не будет корреляции между пикселом и его дальним соседом. Поэтому после поворота, последние 23 координаты преобразованных точек уже не будут малыми. Наблюдения показывают, что корреляция пикселов сохраняется до размерности восемь, но редко дальше. Метод JPEG, описанный в § 3.7, делит изображение на блоки пикселов размера 8х8 и поворачивает каждый блок два раза с помощью уравнения (3.9), которое будет объяснено в § 3.5.3. Это двойное вращение дает множества, состоящие из 64 преобразованных величин, из которых первая, называемая «коэффициент DC», большая, а все остальные 63 («коэффициенты AС») - обычно маленькие. Таким образом, это преобразование концентрирует энергию в первой компоненте из 64. Далее множество коэффициентов DC и 63 множества коэффициентов АС следует квантовать раздельно (метод JPEG делает это немного иначе, см. § 3.7.4).
|