Алгоритм вращения дискретного изображения с использованием двумерного алгоритма Блюстейна

Теория

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

Алгоритм Блюстейна, так же известен как эффективная реализация chirp-z преобразования, – это метод быстрого преобразования Фурье для дискретной сетки с произвольным шагом [3].

Одномерное chirp-z преобразование определено на комплексной последовательности длиной N как:

,

где α – любое комплексное число. Дискретное преобразование Фурье (ДПФ) на той же последовательности определено как:

.

Откуда не трудно заметить, что преобразование ДПФ является частным случаем с параметром Выразим и подставим в определение chirp-z преобразования:

Сумма в этом выражении – свертка последовательностей и , тогда алгоритм Блюстейна сводится к применению прямого преобразования Фурье и , их поэлементному перемножению, обратному преобразованию Фурье и умножению на , что с использованием алгоритма быстрого преобразования Фурье (БПФ, англ. FFT) может быть выполнено эффективнее прямой реализации chirp-z преобразования [4].

Определение двумерного преобразования chirp-z имеет вид:

,

перепишем степени экспонент следующим образом:

,

и подставим в исходное определение преобразования:

.

Введем вспомогательные обозначения:

В итоге двумерное chirp-z преобразование имеет вид:

.

Полученное выражение является сверткой дискретных изображений и , и может быть эффективно рассчитано посредством трех преобразований Фурье, аналогично одномерному случаю. Для выполнения поворота изображения необходимо связать параметры преобразования (α, β) с углом поворота (θ). Пусть p, q – координаты точки в декартовой системе координаты, тогда – координаты точки, в системе координат повернутой на угол θ относительно точки , тогда

Получение изображения в реальной области из изображения в области Фурье, определено как:

Значения в каждой точке может быть посчитано как:

где – это результат chirp-z преобразования последовательности с индексами p, q и

Численные эксперименты

В качестве примера было повернуто изображение топливного инжектора, используя представленный алгоритм и метод билинейной интерполяции, сравнивая результаты легко заметить, что chirp-z преобразование позволяет вращать изображения с минимальными потерями в качестве. В приведенном примере (Рис. 1) деталь была повернута на 360° путем 72 поворотов на 5°:

1. Оригинальное изображение;
2. Изображение, повернутое 72 раза на 5° используя описанный алгоритм;
3. Изображение, повернутое используя билинейную интерполяцию.

Рис. 1

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

Заключение

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

Список литературы

1. Ермолов И.Н., Останин Ю.Я. Методы и средства неразрушающего контроля качества: Учеб. пособие для инженерно-техн. спец. вузов.-М.: Высшая школа, 2003.
2. R. Tong and R.W. Cox “Rotating of NMR Images Using 2D Chirp-z Transform” // Magnetic Resonance in Medicine 1999 vol. 41 253-256.
3. L.I. Bluestein, “A linear filtering approach to the computation of the discrete Fourier transform” // Northeast Electronic Research and Engineering Meeting 1968 vol. 10 218-219.