Разработка программно-математического обеспечения корреляционного совмещения изображений с использованием быстрого преобразования Фурье
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
В±ок округления при умножении и сложении. Однако данный эффект оказывает сколь-нибудь существенное влияние при арифметике с фиксированной точкой и представлении чисел с количеством разрядов менее 8-ми. При представлении чисел с плавающей точкой или 8-ми или большей разрядности данным эффектом можно пренебречь, так как он практически не повлияет на точность расчета спектра.
4. Разработка программно-математического обеспечения
.1 Разработка алгоритмов
Исходя из поставленной задачи, разрабатываемый программный стенд должен содержать следующие блоки:
ввод исходного изображения для Фурье-преобразования;
Фурье-преобразование изображения;
выполнение геометрических искажений изображения;
4.1.1 Нахождение Фурье-образа изображения
В данной работе был применен алгоритм Фурье-преобразования, состоящий из следующих этапов:
) Предварительная перестановка элементов;
) Основной цикл алгоритма Фурье-преобразования, сводящийся непосредственно к нахождению Фурье-образа изображения.
На первом шаге четные элементы с номером n переместились в позицию n/2, а нечетные из позиции в позицию N/2+(n-1)/2. Где n=0,1,тАж,N-1. Таким образом, новая позиция вычисляется из старой позиции с помощью функции:
(n,N) = [n/2] + N{n/2}
Здесь [x] означает целую часть числа, а {x} - дробную.
В ассемблере эта операция называется циклическим сдвигом вправо (ror), если N - это степень двойки. Название операции происходит из того факта, что берется двоичное представление числа n, затем все биты, кроме младшего (самого правого) перемещаются на 1 позицию вправо. А младший бит перемещается на освободившееся место самого старшего (самого левого) бита.
Рисунок 4.1 - Схема циклического сдвига вправо
Дальнейшие разбиения выполняются аналогично. На каждом следующем шаге количество последовательностей удваивается, а число элементов в каждой из них уменьшается вдвое. Операции ror подвергаются уже не все биты, а только несколько младших (правых). Старшие же j-1 битов остаются нетронутыми (зафиксированными), где j - номер шага:
Рисунок 4.2 - Схема разбиения на шаге j
На рисунке 4.3 проиллюстрирован второй этап вычисления ДПФ. Линиями сверху вниз показано использование элементов для вычисления значений новых элментов. Очень удобно то, что два элемента на определенных позициях в массиве дают два элемента на тех же местах. Только принадлежать они будут уже другим, более длинным массивам, размещенным на месте прежних, более коротких. Это позволяет обойтись одним массивом данных для исходных данных, результата и хранения промежуточных результатов для всех T итераций.
Рисунок 4.3 - Схема второго этапа вычисления ДПФ
Схема алгоритма второго шага преобразования Фурье представлена на рисунке 4.4.
Рисунок 4.4 - Схема алгоритма вычисления второго этапа ДПФ
Внешний цикл - это основные итерации. На каждой из них 2Nmax/N ДПФ (длиной по N/2 элементов каждое) преобразуются в Nmax/N ДПФ (длиной по N элементов каждое).
Следующий цикл по k представляет собой цикл синхронного вычисления элементов с индексами k и k + N/2 во всех результирующих ДПФ.
Самый внутренний цикл перебирает Nmax/N штук ДПФ одно за другим.
4.1.2 Восстановление исходного изображения по его Фурье-образу
Восстановление исходного изображение на основе его Фурье-образа производится аналогично поиску самого Фурье-образа. Отличием является то, что в качестве аргумента для вычислений используются значения Фурье-коэффициентов, найденных ранее, а не значение яркостей пикселей изображения. После завершения трех основных циклов алгоритма, необходимо произвести нормирование найденных значений. Это производится iелью корректного графического отображения полученных значений.
Схема алгоритма нахождения исходного изображения по его Фурье-образу представлена на рисунке 4.5.
Рисунок 4.5 - Схема алгоритма нахождения исходного изображения по его Фурье-образу
4.2 Разработка программного обеспечения
совмещение изображение корреляционный фурье
Требования к программной системе (или же отдельной программе) принято классифицировать как функциональные, нефункциональные и требования предметной области.
. Функциональные требования. Это перечень сервисов, которые должна выполнять система, причем должно быть указано, как система реагирует на те или иные входные данные, как она ведет себя в определенных ситуациях и т.д. В некоторых случаях указывается, что система не должна делать.
. Нефункциональные требования. Описывают характеристики системы и ее окружения, а не поведение системы. Здесь также может быть приведен перечень ограничений, накладываемых на действия и функции, выполняемые системой. Они включают временные ограничения, ограничения на процесс разработки системы, стандарты и т.д.
. Требования предметной области. Характеризуют ту предметную область, где будет эксплуатироваться система. Эти требования могут быть функциональными и нефункциональными.
Для выполнения поставленной в данном дипломном проекте задачи программный стенд должен обеспечивать выполнение следующих функций:
)выбор и загрузка рабочего изображения из файла. Данное изображение должно представлять собой растровое изображение в формате битовой карты (BMP) с 256 градациями яркости серого цвета (если изображение не соответствует указанным требованиям, возможно его преобразован