nabbla (nabbla1) wrote,
nabbla
nabbla1

Category:

УТ БПФ - раздел 1, часть 1

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

В общем, нашел два преимущества, сейчас расскажу о первом - удобстве работы с действительными данными, а о втором, связанным с особенностями дискретизации непрерывного сигнала, напишу на днях. Если кратко, у частоты N/2 в БПФ по базису 2 совершенно неясный физический смысл. Это частота, которой в сигнале вообще быть не должно! И надо сказать, это весьма конкретные грабли, на которые народ не перестает наступать.
А потом еще придется все это дело скомпоновать как следует.

Курсивом обозначаются как бы пометки на полях - то, что я не знаю, как выразить строго. Итак,

Раздел 1. Преимущества уравновешенных преобразований в прикладных задачах

Определения
Одномерным дискретным преобразованием Фурье от N∈ комплексных чисел {x0,x1,…,xN-1} называют вектор {F,0,F1,…FN-1}, определяемый соотношениями
(1)

Назовем уравновешенным дискретным преобразованием Фурье от N=2T+1 (T∈) чисел {x-T,x-T+1,… xT} вектор {F-T,F-T+1,…,FT}, определяемый соотношениями
(2)

Уравновешенное дискретное преобразование Фурье можно ввести только для нечетного количества отсчетов. Хотя существует возможность при N=2T обозначить отсчеты дробными индексами (например, -3/2,-1/2,1/2,3/2) и найти разложение сигнала по соответствующим частотам, такое преобразование не имеет большого практического смысла и далее рассматриваться не будет. Хотя оно и является обратимым, то есть содержит всю необходимую информацию для восстановления исходного сигнала, но из-за отсутствия нулевой частоты постоянная составляющая сигнала сама будет разложена по гармоникам, из-за чего преобразованные данные сложно интерпретировать как спектр сигнала. По этой же причине не находит широкого применения дискретное синус-преобразование [Д. Сэломон - Сжатие данных, изображений и звука, М.: Техносфера, 2004].

Быстрым преобразованием Фурье называют семейство алгоритмов, позволяющих вычислить (1) за O(NlogN) операций. По аналогии будем называть уравновешенным троичным БПФ любой алгоритм, вычисляющий (2) за O(NlogN) операций.

Работа с действительными данными
Рассмотрим для начала одномерный случай: дискретное преобразование Фурье от действительного сигнала с четным количеством отсчетов. Полученные данные можно разделить на 4 части (рис 1).
Рис 1. а) ДПФ от действительных данных, серым обозначены избыточные данные;
б) вариант хранения в N/2 комплексных отсчетах;
в) в N действительных отсчетах

Нулевой отсчет представляет собой постоянную составляющую (DC, Direct Current) сигнала, поэтому мнимая часть нулевая – на рисунке это обозначено серым заполнением половины ячейки, т.е одно из значений избыточно. Отсчеты 1..N/2-1 – положительные частоты, произвольные комплексные числа. Отсчет N/2 – так называемая частота Найквиста (Nq, Nyquist). Поскольку фазовый множитель может принимать лишь значения ±1, то и этот отсчет имеет нулевую мнимую часть. Наконец, отсчеты с N/2+1 по N-1 представляют собой отрицательные частоты и являются комплексно сопряженными к соответствующим положительным.
Как можно заметить, для хранения ДПФ от действительного сигнала достаточно N действительных чисел, но мы должны оставить N/2+1 отсчет, с двумя нулевыми мнимыми частями. Можно поместить частоту Найквиста в мнимой части постоянной составляющей, но это усложняет индексацию массива, придется каждый раз проверять этот частный случай. Другой подход состоит в том, чтобы хранить все данные в массиве действительных чисел размером N, в положительных частотах размещая действительные части, а в отрицательных – мнимые. Но и такой метод приводит к усложнению работы.

Хуже обстоит дело с двумерным преобразованием Фурье от действительного изображения. На рис 2 изображена структура преобразованных данных, серым помечены избыточные области, которые необязательно вычислять и хранить.
Рис 2. Структура выходных данных двумерного ДПФ действительного сигнала, серым отмечены избыточные области

Отсчеты DC, Nq10, Nq01 и Nq11 – действительные. Остальные коэффициенты комплексные, но у каждого из них есть комплексно сопряженная пара. Есть множество вариантов, какие из них оставлять, а какие выкидывать. На рис 2 выкидываются все строки, начиная с N/2+1, как это сделано в [У. Прэтт, цифровая обработка изображений, том 1, М.: Мир, 1982], но можно было бы с тем же успехом выкинуть все столбцы, начиная с N/2+1. Но ни в одном варианте не удастся разместить все полезные данные в последовательных ячейках памяти, без «дыр».
Хотя для хранения данных хватает N2 действительных коэффициентов, для упрощения алгоритмов принято выделять область памяти под N*(N/2+1) комплексных величин, или N2+2N действительных. Именно так это сделано в библиотеке FFTW [M. Frigo, S. G. Johnson, “FFTW: An adaptive software architecture for the FFT”, Proc. ICASSP 1998 3, p. 1381].

Основная проблема заключается даже не в излишнем расходе памяти, а в сложности работы с подобными структурами. Библиотека FFTW, к примеру, не может выделять память самостоятельно – инициализировать массивы данных и позже обрабатывать их должен непосредственно программист. Необходимо держать в голове рис. 2.

Рис 3. Структура выходных данных УТ ДПФ от действительного сигнала. Серым обозначены избыточные области.
a) представление в виде комплексных отсчетов
b) вариант хранения в N действительных отсчетах

Структура выходных данных уравновешенного преобразования Фурье изображена на рис. 3. Частоты Найквиста здесь нет, есть только постоянная составляющая (DC), положительные и отрицательные частоты. В одномерном случае это не дает особенных преимуществ (кроме эстетического удовлетворения), но работа с двумерными данными серьезно упрощается. Как видно из рисунка, все необходимые данные можно хранить в памяти последовательно. Можно обойтись ровно N+1 действительными отсчетами при сохранении обычной адресации, а в некоторых случаях достаточно N последовательно расположенных отсчетов (для этого надо гарантировать, что при дальнейшей обработке не будет обращений к мнимой части постоянной составляющей).

Собственно, ради рис. 3 я и заварил в свое время эту кашу. Забегая вперед, могу добавить: если исходным изображением сделать апертуру телескопа, то преобразованное будет дифракционной картиной. (0;0) начальных данных - центр апертуры, оптическая ось, а (0;0) преобразованных - это центр экрана, или направление строго вдоль оптической оси. И все! Изначально все симметрично и не надо плясать с бубном.
Tags: математика, статьи, троичная система счисления, уравновешенное троичное БПФ
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 6 comments