Сжатие видео: что такое дискретное косинусное преобразование?

Я реализовал технику преобразования изображения / видео под названием дискретное косинусное преобразование. Этот метод используется в кодировании видео MPEG. Я основал свой алгоритм на идеях, представленных по следующему URL:

http://vsr.informatik.tu-chemnitz.de/~jan/MPEG/HTML/mpeg_tech.html

Теперь я могу преобразовать черно-белое изображение размером 8x8, например:

0140 0124 0124 0132 0130 0139 0102 0088  
0140 0123 0126 0132 0134 0134 0088 0117  
0143 0126 0126 0133 0134 0138 0081 0082  
0148 0126 0128 0136 0137 0134 0079 0130  
0147 0128 0126 0137 0138 0145 0132 0144  
0147 0131 0123 0138 0137 0140 0145 0137  
0142 0135 0122 0137 0140 0138 0143 0112  
0140 0138 0125 0137 0140 0140 0148 0143 

В это изображение со всей важной информацией в правом верхнем углу. Преобразованный блок выглядит так:

1041 0039 -023 0044 0027 0000 0021 -019  
-050 0044 -029 0000 0009 -014 0032 -010  
0000 0000 0000 0000 -018 0010 -017 0000  
0014 -019 0010 0000 0000 0016 -012 0000  
0010 -010 0000 0000 0000 0000 0000 0000  
-016 0021 -014 0010 0000 0000 0000 0000  
0000 0000 0000 0000 0000 0000 0000 0000  
0000 0000 -010 0013 -014 0010 0000 0000  

Теперь мне нужно знать, как я могу воспользоваться этим преобразованием? Я хотел бы обнаружить другие блоки 8x8 на том же изображении (или другом изображении), которые представляют хорошее совпадение.

Кроме того, что дает мне это преобразование? Почему информация, хранящаяся в правом верхнем углу преобразованного изображения, важна?

7.08.2008 11:04:37
6 ОТВЕТОВ

Если я правильно помню, эта матрица позволяет сохранять данные в файл со сжатием.

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

Количество выбрасываемых значений увеличивает сжатие за счет точности изображения.

Но я уверен, что кто-то другой может дать вам лучшее объяснение.

1
7.08.2008 11:08:21

Результатом DCT является преобразование исходного источника в частотную область. В верхнем левом элементе хранится «амплитуда», «базовая» частота, а частота увеличивается как по горизонтальной, так и по вертикальной осям. Результатом DCT обычно является набор амплитуд на более обычных более низких частотах (верхний левый квадрант) и меньшее количество входов на более высоких частотах. Как упоминал lassevk, обычно эти высокие частоты просто обнуляют, так как они обычно составляют очень незначительные части источника. Однако это приводит к потере информации. Для завершения сжатия обычно используется сжатие без потерь по сравнению с источником DCT. Здесь происходит сжатие, так как все эти серии нулей упаковываются практически до нуля.

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

Надеюсь это поможет

14
9.08.2008 01:03:18

Я бы порекомендовал взять копию Digital Video Compression - это действительно хороший обзор алгоритмов сжатия изображений и видео.

1
10.08.2008 01:39:42

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

4
12.08.2008 08:28:06

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

С точки зрения использования DCT для сравнения изображений, я предполагаю, что единственное реальное преимущество заключается в том, что вы обрезаете данные с более высокой частотой и, следовательно, имеете меньший набор данных для поиска / сопоставления. Что-то вроде вейвлетов Харра может дать лучшие результаты сопоставления изображений.

1
27.08.2008 11:33:54

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

В реальном мире нет прямоугольных волн. Ничего не происходит в нулевое время. Звуковые сигналы, например, занимают диапазон от 20 Гц до 20 кГц, где Гц равен 1 / время. Такие вещи можно представить конечными рядами ».

Для изображений математика одинакова, но две вещи разные. Во-первых, это двухмерное. Во-вторых, понятие времени не имеет смысла. В одномерном смысле прямоугольная волна - это просто функция, которая дает некоторое числовое значение для аргумента, который мы назвали временем. (Статическое) изображение - это функция, которая выдает числовое значение для каждой пары строк и столбцов. Другими словами, изображение является функцией 2D-пространства, представляющего собой прямоугольную область. Такая функция может быть представлена ​​в терминах ее пространственной частоты. Чтобы понять, что такое пространственная частота, рассмотрим 8-битное изображение уровня серого и пару смежных пикселей. Самое резкое изменение, которое может произойти на изображении, происходит от 0 (скажем, черный) до 255 (скажем, белый) на расстоянии 1 пиксель.

Двумерное преобразование Фурье (или косинус) изображения приводит к массиву значений того же размера, что и изображение, представляя ту же информацию не как функцию пространства, а функцию 1 / пространство. Информация упорядочена от самой низкой до самой высокой частоты по диагонали от самой высокой строки и столбца начала координат. Пример здесь .

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

Еще один способ взглянуть на это - уменьшить изображение до меньшего размера. Если, например, вы попытаетесь уменьшить размер изображения, отбрасывая три из каждых четырех пикселей подряд и три из каждых четырех строк, у вас будет массив размером 1/4, но изображение будет выглядеть ужасно. В большинстве случаев это достигается с помощью 2D-интерполятора, который создает новые пиксели путем усреднения прямоугольных групп пикселей большего изображения. При этом интерполяция имеет эффект, аналогичный выбрасыванию последовательных членов в частотной области, только вычисление происходит намного быстрее.

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

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

2
31.12.2013 23:41:29