Конференции ИВТ СО РАН

Тезисы докладов

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

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

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

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

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

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск