РАЗДЕЛ 2
РАЗРАБОТКА СПОСОБОВ ДВУМЕРНОГО
ПРЕОБРАЗОВАНИЯ ИЗОБРАЖЕНИЙ В БАЗИСЕ ХААРА
В разделе определяются недостатки существующих способов выполнения двумерного преобразования Хаара, разрабатывается способ двумерного преобразование Хаара, который позволяет выполнять преобразования за один этап и лишен недостатков существующих способов двумерного преобразования Хаара. Разрабатывается целочисленный базис Хаара, метод его получения и способ целочисленное преобразование Хаара, в котором исключены вещественные операции из процедуры преобразования.
2.1. Способы выполнения двумерных ортогональных преобразований
Использование ортогональных преобразований при цифровой обработке изображений сопряжено с рядом трудностей, которые определяются следующими свойствами изображений [2, 21, 22, 29, 41]:
1. Отсчеты изображений организованы в виде двумерных массивов с сильными статистическими взаимосвязями в обоих измерениях.
2. Массив отсчетов изображения характеризуется большим объемом данных, который определяется размерностью изображения и количеством бит, используемых для кодирования цветовых компонент.
Существующие способы выполнения двумерных ортогональных преобразований основываются на одномерных ортогональных базисах, что определяет их невысокую эффективность [1, 41, 99]. Рассмотрим их подробнее.
Развертка двумерного массива в одномерную последовательность. Двумерный массив отсчетов изображения с помощью различных видов разверток преобразуется в одномерную последовательность [1]. Полученная последовательность подвергается одномерному ортогональному преобразованию. Преобразование Хаара в этом случае определяется следующими матричными выражениями [5, 113]:
; (2.1)
, (2.2)
где N - количество элементов вектора отсчетов;
- нормирующий коэффициент;
- вектор-столбец отсчетов изображения;
- матрица дискретных значений базисных функций преобразования Хаара ();
- транспонированная матрица дискретных значений базисных функций;
- вектор коэффициентов преобразования.
Выражение (2.1) является прямым преобразованием Хаара, а выражение (2.2) - обратным преобразованием.
Матрица H(n) формируется в результате дискретизации N базисных функций преобразования Хаара (1.22) [39, 113]. Для N=8 матрица H(n) имеет вид
Основными недостатками описанного способа являются:
* невозможность получения и анализа двумерных спектров;
* возможность анализа только одномерных корреляционных взаимосвязей вдоль развертки.
Указанные недостатки ограничивают использование данного способа для цифровой обработки изображений.
Использование свойства разделимости ортогональных базисов. Возможность получения двумерных спектров предоставляют способы, основанные на свойстве разделимости ортогональных базисов. Это свойство позволяет использовать для выполнения двумерных ортогональных преобразований одномерные ортогональные базисы [5, 39, 87, 110]. Ортогональное преобразование двумерного массива размерности NxM в этом случае описывается следующими выражениями:
; (2.4)
, (2.5)
где - нормирующий коэффициент;
- исходный массив отсчетов изображения, размерности ;
- матрица коэффициентов преобразования (трансформанта) размерности .
Выражение (2.4) является прямым двумерным преобразованием Хаара, (2.5) - обратным двумерным преобразованием.
Из выражений (2.4) и (2.5) следует, что прямое и обратное преобразование выполняется в два этапа [5]:
1) на первом этапе выполняется одномерное ортогональное преобразование столбцов исходной матрицы, в результате которых формируется промежуточная матрица:
- первый этап прямого преобразования определяется выражением
, (2.6)
где - промежуточная матрица размерности NxM;
- первый этап обратного преобразования имеет вид
, (2.7)
где - промежуточная матрица размерности NxM;
2) на втором этапе выполняются одномерные ортогональные преобразования строк промежуточной матрицы. Результатом выполнения второго этапа при прямом преобразовании является матрица коэффициентов преобразования размерности NxM (дополнительно выполняется нормировка коэффициентов преобразования), при обратном преобразовании - матрица восстановленных отсчетов изображения:
- второй этап прямого двумерного преобразования Хаара определяется формулой
, (2.8)
- второй этап обратного преобразования определяется выражением
, (2.9)
Недостатками данного способа являются [14, 83]:
* необходимость выполнения преобразования в два этапа и невозможность выполнения процедур второго этапа преобразования до окончания выполнения всех процедур первого этапа;
* необходимость в дополнительной памяти для хранения промежуточной матрицы;
* накопление ошибок округления, что связанно с участием ошибок, сформированных на первом этапе преобразования, в операциях второго этапа;
* невозможность вычисления только определенной части коэффициентов преобразования;
* ограниченные возможности по распараллеливанию операций преобразования.
Количество арифметических операций, которые необходимо выполнить при использовании выражений (2.4) и (2.5) определяется следующими формулами:
; (2.10)
, (2.11)
где - количество операций сложения/вычитания при прямом преобразовании (2.4);
- количество операций сложения/вычитания при обратном преобразовании (2.5);
- количество операций умножения/деления при прямом преобразовании (2.4);
- количество операций умножения/деления при обратном преобразовании (2.5).
Как видно из выражений (2.10) и (2.11) сложность выполнения ортогонального преобразования в этом случае является кубической (). Так, для выполнения прямого и обратного преобразования Хаара в соответствии с выражениями (2.4) и (2.5) над изображением размерности 1024х1024 (M=N=1024) количество арифметических операций составит: , .
Кроме этого, при обработке изображений различных размерностей необходимо:
* рассчитывать матрицы дискретных значений базисных функций Хаара H(n) и H(m) для каждог