Как субпиксельное смещение изображения с использованием DFT действительно работает?

12

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

Я думал об использовании DFT + смещения в частотной области, и я не уверен, как это работает на самом деле по сравнению с явной интерполяцией изображения (с использованием билинейного, бикубического и т. Д.). Я уверен, что он не может генерировать идеально смещенное изображение , но я не могу указать на это. Сдвиг субпикселя с использованием ДПФ эквивалентен применению интерполяции и, если да, то какой? Каково смещение значений пикселей на изображениях, полученных с помощью этого метода? Благодарность!

РЕДАКТИРОВАТЬ: После обдумывания этого вопроса, я решил, что БПФ является приближением (даже более того, ДПФ) исходной функции с точки зрения гармоник (синусоидальных функций), что это будет равнозначно тригонометрической интерполяции. Я вспоминаю формулу «Интерполяция рядов Фурье» для дискретных данных, которая была тригонометрической интерполяцией, но я не уверен, что она подключена.

neuviemeporte
источник
Быстрое преобразование Фурье (БПФ) представляет собой алгоритм для дискретного преобразования Фурье. ДПФ - это не приближение исходной функции в терминах гармоник, а проекция сигнала на сложный экспоненциальный ортогональный базис.
Брайан
Хорошо, но сам сигнал является дискретизированным и квантованным приближением некоторого распределения интенсивности, и ДПФ ограничено по содержанию гармоник по сравнению с этим теоретическим распределением. Вы можете получить точный сигнал обратно из IDFT, но будет некоторая предвзятость, если вы сделаете что-то (например, смещение) до того, как IDFT вернет его обратно. Или я что-то упустил?
neuviemeporte
ДПФ действительно принимает дискретизированные входы, но не ограничивается квантованными входами. Что это за сигнал, не имеет значения. Как вы указали, вы можете получить точный сигнал обратно. Тем не менее, я не уверен, что вы подразумеваете под «сдвигом». Свойства сдвига в частотной области хорошо известны (сложное преобразование частоты во временной области). Если вы хотите сдвинуться во временную область, вам нужно подумать о двойном DFT из этого.
Брайан
1
Я имею в виду, что если я выполню некоторую операцию с ДПФ сигнала (как в моем случае - смещение субпикселя изображения в «пиксельной области» с использованием теоремы смещения Фурье), то IDFT вернет интерполированные результаты, как объяснено @ hotpaw2's ответ. Эта интерполяция несовершенна, потому что сигнал не ограничен по полосе, а сам ДПФ был рассчитан из конечного набора квантованных (0-255) выборок.
neuviemeporte

Ответы:

4

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

Если вы увеличите выборку в 2 раза (заполняйте нулями FFT, чтобы удвоить длину перед IFFT), то вы можете сделать сдвиг на полпикселя, используя интерполированные точки. 3X для сдвига третьего пикселя и т. Д. Для сдвига можно отбросить исходные точки и любые лишние интерполированные точки, чтобы получить желаемый размер.

hotpaw2
источник
5
@ hotpaw2: интерполяционное ядро ​​для DFT не является sinc () бесконечной степени, фактически DFT является дискретным, конечным преобразованием. Интерполяция с помощью DFT эквивалентна свертке с ядром Дирихле, которое некоторые авторы также называют периодическим sinc () : en.wikipedia.org/wiki/Dirichlet_kernel
Arrigo
@Arrigo: согласен. Отредактированный ответ, чтобы исправить.
hotpaw2
@ hotpaw2: когда я добавляю FFT в два раза больше, IFFT приведет к реконструкции в два раза больше. Не уверен, что делать с избытком? Спасибо
neuviemeporte
Выбросьте лишние баллы, которые вам не нужны. При увеличении в 2 раза каждый второй сдвигается, чередуясь с восстановленными исходными точками. При увеличении в 3 раза вы получаете 2 смещенные точки (на 1/3 и на 2/3), чередующиеся с оригиналами. И т.д. Чем больше вы повышаете, тем больше вы выбрасываете.
hotpaw2
7

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

Во-первых, теория Фурье: вероятно, сначала проще взглянуть на непрерывный (т.е. аналоговый) случай. Представьте, что у вас есть какая-то функция, назовите ее g (t). Для простоты предположим, что g (t) - это запись аналогового звука, поэтому это одномерная функция, которая является непрерывной и представляет мгновенное давление как функцию времени.

Теперь g (t) - это один из способов представления нашей аудиозаписи. Другой - это G (f). G (f) - преобразование Фурье от g (t). Итак, G (f) == FT (g (t)). G (f) имеет всю ту же информацию, что и g (t), но она представляет эту информацию в частотной области, а не во временной. Есть несколько придирчивых деталей о преобразованиях Фурье, которые я не буду упоминать.

Вы можете рассматривать G (f) как «распределение частот», содержащееся в g (t). Итак, если g (t) является синусоидальной волной (т. Е. Чистым тоном), то G (f) будет нулевым везде, кроме частоты этого тона. Вероятно, это хороший момент для упоминания того, что G (f) в общем случае является сложной функцией, то есть возвращает комплексные числа, о которых можно думать, что они имеют действительный и мнимый компонент или величину и фазу.

δ(w)δ

Хорошо, теперь у нас есть непрерывные FT под нашим поясом.

Вот второе понимание: дискретное преобразование Фурье относится к преобразованию Фурье, а дискретизированный сигнал - к аналоговому сигналу. В этом случае «дискретный» относится к квантованию области функции (времени или частоты), а не ее диапазона. (Сэмплированный цифровой сигнал, который вы получаете с вашей звуковой карты, квантуется как в области, так и в диапазоне.)

Цифровой поток байтов, который вы получаете со своей звуковой карты, содержит «образцы» исходного непрерывного (аналогового) сигнала от микрофона. Если мы возьмем ДПФ из нашей выборки g (t), мы все равно получим G (f). Помните, что G (f) - это просто другой способ представления информации, содержащейся в g (t). Если мы подчиняемся теореме Найквиста , дискретизированный сигнал g (t) содержит весь «интеллект» исходного непрерывного сигнала, поэтому наш дискретный G (f) должен содержать всю информацию из нашего исходного непрерывного сигнала. В скобках G (f) все еще является сложной функцией.

Вот тут-то и возникает магия субпиксельного смещения, но в этом случае я напишу о смещении аудиосигнала во времени менее чем на сэмпл, поскольку это одно и то же.

eiπ2

Это означает, что мы можем сдвинуть нашу аудиозапись во времени (на любую величину, которую мы выберем, включая долю времени выборки), просто изменив фазу G (t). На самом деле, это утверждение, пожалуй, слишком случайное. Для неквантованного дискретизированного сигнала фазу можно отрегулировать произвольно (это одна из причин, по которым я раньше проводил различие между квантованием области и диапазона). Однако для квантованного дискретизированного сигнала (например, нашего байтового потока аудио) размер шага квантования (т. Е. Количество битов) определяет разрешение, с которым мы можем регулировать фазу. Когда мы обратное преобразование Фурье G (f) (или DIFT его, для этого дискретизированного сигнала), новый набор выборок g '(t) = DIFT (G (F)) все будет сдвинут во времени на величину, которую мы выберем.

Применение этого к вашим пикселям просто означает использование 2-мерного FT вместо 1-мерного FT, обсужденного здесь.

ник г
источник