Исследование параметров моделей пространственного взаимодействия вейвлет коэффициентов

Исследование параметров моделей пространственного взаимодействия вейвлет коэффициентов

Гай В.Е., Жизняков А.Л.
Муромский институт (филиал) Владимирского государственного университета
Введение

Обычно, в основе различных алгоритмов обработки изображений лежит математическая модель изображения. Одним из наиболее известных способов описания изображения является описание с использованием моделей пространственного взаимодействия [1]. Такой способ использует предположение о том, что каждая точка изображения зависит от своей локальной области: , - рассматриваемая точка, - точки, принадлежащие локальной области элемента . Модели пространственного взаимодействия, определяемые на двумерной решётке описываются набором соседних элементов для рассматриваемого элемента и взаимосвязями, существующими между ними. Как правило, в качестве структуры локальной области для каждого элемента изображения рассматривается его восьмиэлементная окрестность [1].

С появлением вейвлет преобразования и многомасштабного подхода к представлению изображений стали использоваться многомасштабные случайные поля, при этом, как и в классическом случае использовалась фиксированная структура локальной области каждого вейвлет коэффициента. При этом, указывается на возможность использования адаптивного подхода к выбору структуры локальной области [2]. Вейвлет преобразование позволяет разложить изображение на несколько частотных диапазонов, в каждом из которых находятся различные характерные особенности изображения ("вертикальные", "горизонтальные", "диагональные"). Следовательно, для описания связей между вейвлет коэффициентами на одном уровне разложения для каждого частотного диапазона более эффективно было бы использовать локальные области, адаптивные к свойствам частотных диапазонов.

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

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

Обзор существующих подходов к поиску оптимальной локальной области

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

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

В настоящее время для решения данной задачи существует большое число подходов. Например, подход на основе критерия AIC (Akaike's information criterion) [3], подход, использующий байесово решающее правило [4], подход на основе MDL критерия (minimum description length) [5]. Общим недостатком данных подходов к решению задачи является то, что они используют априорно заданный набор локальных областей.

В [6] предлагается метод построения карт корреляции вейвлет коэффициентов. Полученные карты в дальнейшем могут быть использованы для вычисления структуры локальной области. Однако, данный метод требует больших затрат памяти. Так, для оценки структуры локальной области для изображения размером точек, требуется построение матрицы размером (для изображения размером матрица будет занимать в памяти 1024 Мб).

Подход к поиску структуры локальной области на основе взаимной информации

При поиске структуры локальной области в качестве критерия оптимальности можно воспользоваться величиной взаимной информации . Величина взаимной информации показывает сколько информации в наборе данных содержится о наборе данных [7].

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

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

Полученная матрица величин взаимной информации может быть использована для определения оптимальной структуры локальной области. Для этого можно применить процедуру отсечения по порогу:

, где - порог, определяемый экспериментальным путём.

Порог и структура локальной области выбирается на основе взаимной информации следующим образом:

1. 
   устанавливается и выбирается структура локальной области ;
   
2. 
   вычисляется взаимная информация между точкой и локальной областью ;
   
3. 
   уменьшается порог , выбирается новая структура локальной области на основе данного порога;
   
4. 
   вычисляется взаимная информация между точкой и локальной областью ;
   
5. 
   если , то рассматривается как оптимальная структура локальной области и осуществляется переход на шаг 2;
   
6. 
   если , то структура рассматривается как оптимальная и алгоритм прекращает работу.
   

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

На Рис. 1.б.в чёрным цветом отмечены точки, отнесённые к вычисленной структуре локальной области.

а.

б.

Рис. 1. Вычисленные структуры локальных областей для изображения типа "портрет"
а) вычисленная структура локальной области для НЧВЧ диапазона; б) вычисленная структура локальной области для ВЧНЧ диапазона

Как видно из рис. 1 для НЧВЧ диапазона (рис. 1.а), который содержит выделенные горизонтальные особенности изображения, структура локальной области соответствует особенностям изображения, содержащимся в рассматриваемом частотном диапазоне. Такая же ситуация наблюдается и для ВЧНЧ диапазона (рис. 1.б).

Заключение

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

Литература

1. Белокуров А., Сечко В. Стохастические модели в задачах анализа и обработки изображений. – Зарубежная радиоэлектроника, 1994, №2

2. R.W. Buccigrossi, E.P. Simoncelli Image compression via joint statistical characterization in the wavelet domain, ICASSP, Munich, Germany, April 1997

3. H.Akaike "Maximum likelihood identification of Gaussian autoregressive moving average models", Biometrika, vol. 60, pp. 255-265, 1974

4. J. Rissanen "Modeling by shortest data description", IEEE Transaction on Information Theory, vol. 14, pp. 465-471, 1978

5. R.L. Kashyap, R.Chellappa "Estimation and choice of neghbors in spatial-interaction models of images" vol. IT-29, pp. 60-72, 1983

6. Z.Azimifar, P.Feiguth, J.Jernigan "Hierarchical multiscale modeling of wavelet – based correlations" Proceedings of the 9^th SSPR, 2002

7. J. Liu, P.Moulin "Information-Theoretic analysis of interscale and intrascale dependencies between image wavelet coefficients" IEEE Transaction on image processing, vol. 10, no. 11. pp. 1647-1658, 2001



parameters research of Spatial interaction models of wavelet coefficients

Gai V., Giznyakov A.

Murom institute of the Vladimir state university
Using spatial interaction models requires taking next assumption: every image pixel are defined by its neighborhood: , - current pixel, - neighborhood of . As a rule in standard case uses fixed structure of local area, that consists of eight nearest pixels. Wavelet transform ant multiscale image representation are connected with multiresolution spatial interaction models of wavelet coefficients. Spatial interaction models which are defined on two dimensional lattice are described using neighbor set and links between them. As rule, neighbor set consists eight nearest pixels. At the same time some researches are pointed on possibility of using adaptive approach to local neighbor set selection. Wavelet transform forms frequency components of image, which contains different image features. Thus, for more efficient using properties of wavelet coefficients it is necessary to research local interaction properties of wavelet coefficients. Existed approaches to synthesis of wavelet coefficient local structure are based on solving optimization tasks or on method of exhaustive search. In this article an approach to synthesis structure of local area based on mutual information criterion are proposed.

The purpose of the work is to develop an approach to optimal structure of local area of image pixel calculation, which are adapted to characteristic image properties.

In process of synthesis the structure for local area as optimality criterion can be used magnitude of mutual information . Mutual information magnitude shows how many information in dataset are contained in dataset .

Proposed approach are based on calculation of mutual information magnitude for each element of local area with size , which center are located in the point , where - odd number.

Suppose, it is necessary to calculate mutual information magnitude between center element and element with position data, relative local area. To calculate it perfome cyclical shift of source set of wavelet coefficients in such way that element with position data will be moved into local area center. Next, calculate magnitude of mutual information between source and shifted sets of wavelet coefficients. Derived magnitude is a magnitude of mutual information between element with position data relative local area and center element of local area. Obtained matrix of mutual information magnitudes can be used for synthesis optimal structure of local area. It can be performed using next threshold operation: , where - threshold, which can be calculated during experiment. Threshold are selected using mutual information.

Proposed approach to synthesis structure of local area of wavelet coefficient allows simultaneously perfome the task of computing of weight ratio for each local area element. Mutual information magnitude of elements of selected local area structure after normalization can be used as weight ratio for each local area element.

Research results shows an possibility of application of proposed approach for solving the task of synthesis structure of local area for wavelet coefficient. Proposed algorithm can be used to perfome characterization of spatial interaction models, as well as in different digital image processing tasks in wavelet domain.


Модификация алгоритма SPIHT на основе вейвлет-пакетного базиса
Волохов В.А.

Ярославский государственный университет им. П.Г. Демидова
150000, Россия, Ярославль, ул. Советская, 14, Тел. (0852) 79-77-75. E-mail: [email protected]
Цифровые изображения занимают все большую часть информационного пространства. Развитие Интернета, наряду с доступностью все более мощных компьютеров и прогрессом в технологии производства цифровых камер, сканеров и принтеров, привели к широкому использованию цифровых изображений. Отсюда постоянный интерес к улучшению алгоритмов сжатия данных, представляющих изображения. Сжатие данных важно как для скорости передачи, так и эффективности хранения.

Работа посвящена рассмотрению нестандартизованного, но достаточно эффективного алгоритма SPIHT (Set Partition in Hierarchical Trees – “Разбиение множества в иерархические деревья”) [1, 2, 3, 4] и его расширенной модификации [5], основанных на вейвлет-преобразовании и предназначенных для сжатия и прогрессивной передачи изображений.

Кратко рассмотрим основные особенности классического алгоритма SPIHT, которые присущи и его модифицированной версии.

Во-первых, это прогрессивная передача, основная цель которой состоит в скорейшей передаче самой важной части информации об изображении. Это дает самое большое сокращение расхождения исходного изображения и реконструированного образа. Количественно данное расхождение может быть оценено через среднеквадратическую ошибку (MSE): , где – общее число пикселей, и – это пиксели исходного и восстановленного изображений соответственно.

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

Основные шаги кодера алгоритма SPIHT следующие (предполагается, что коэффициенты отсортированы до начала цикла):

Шаг 1. Для заданного сжимаемого изображения вычислить его вейвлет-преобразование, используя подходящие вейвлет-фильтры, разложить его на коэффициенты преобразования C[i,j] и представить их в виде целых чисел фиксированной разрядности.

Шаг 2. Передача – количество разрядов (считая от нуля), занимаемых максимальным отсчетом разложения, то есть (округление вниз).

Шаг 3. Инициализация списка значимых коэффициентов – пустое множество.

Шаг 4. Сортировка. Передать число l коэффициентов C[i,j], которые удовлетворяют неравенству . Затем передать l пар координат и l знаков этих коэффициентов.

Шаг 5. Поправка. Передать (n-1)-вые старшие биты всех коэффициентов, удовлетворяющих неравенству . Эти коэффициенты были выбраны на шаге сортировки предыдущей итерации цикла.

Шаг 6. Итерация. Уменьшить n на 1. Если необходимо сделать еще одну итерацию, пойти на Шаг 4.

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

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

Описанный выше алгоритм очень прост, так как в нем предполагается, что коэффициенты были отсортированы (упорядочены) до начала цикла. В принципе изображение может состоять из очень большого числа пикселов, в нем может быть более миллиона коэффициентов, их сортировка может оказаться весьма медленной процедурой. Вместо сортировки коэффициентов алгоритм SPIHT использует тот факт, что сортировка делается с помощью сравнения в каждый момент времени двух элементов, а каждый результат сравнения – это просто ответ: “да” или “нет”. Поэтому если кодер и декодер используют один и тот же алгоритм сортировки, то кодер может просто послать декодеру последовательность результатов сравнения “да” или “нет”, а декодер будет дублировать работу кодера.

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

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

Кодирование коэффициентов заключенных в структуру пространственно ориентированного дерева осуществляется за счет трех списковых субструктур LIS, LIP, LSP [1, 4, 6]:

1. LIS – список не значащих множеств (list of insignificant sets);

2. LIP – список незначащих точек (list of insignificant pixels);

3. LSP – список значащих точек (list of significant pixels).

Последовательный анализ указанных структур выявляет значимые и не значимые коэффициенты и множества на каждой итерации.

Для оценки качества восстановленного изображения на выходе рассматриваемого алгоритма, можно воспользоваться величиной, получившей название, пиковое отношение сигнала к шуму (PSNR), измеряемой в децибелах. Для полутоновых изображений, которые и рассматривались в данной работе, используется следующее выражение:

Для рассмотрения сравнительных результатов, полученных в двух алгоритмах необходимо отметить основную особенность модифицированного алгоритма SPIHT, которая заключается в использовании на этапе преобразования вейвлет-пакетного базиса [7, 8, 9]. Основные проблемы использования данного обобщения алгоритма SPIHT состоят в решении родительских конфликтов в вейвлет-дереве и нахождения наиболее оптимального разложения вейвлет-плоскости, которое напрямую связано с проблемой нахождения оптимального критерия обеспечивающего данное разложение.

На рис. 1 представлены сравнительные тесты обычного алгоритма SPIHT и его модифицированной версии для тестового изображения Барбара. Как видно из рис.1. улучшения в работе модифицированного алгоритма есть, но не значительные, похожие результаты работы данного алгоритма были получены и для других тестовых изображений (Лена, Золотой Холм, Перцы и др.).

Особый выигрыш, модифицированный алгоритм SPIHT дает на так называемых искусственных изображениях (текстурах). Пример такой текстуры приведен на рис. 3а. Результаты применения обычного алгоритма SPIHT и его модификации для данной текстуры представлены на рис. 2, рис. 3б и рис. 3в.

Рис. 1. Сравнительные зависимости PSNR(bpp) для обычного алгоритма SPIHT и его модифицированной версии (изображение Барбара )	Рис. 2. Текстура D49: сравнение зависимостей PSNR(bpp) для SPIHT и модифицированного SPIHT

Для текстур подобных D49 диадное вейвлет-преобразование хуже концентрирует энергию образа в малом количестве коэффициентов, поэтому вейвлет-пакеты, являющиеся некотором обобщением вейвлет-преобразования, дают в данном случае значительный выигрыш. Все же нужно еще раз отметить, что для естественных изображений (подобных изображениям Барбара, Лена, Золотой Холм) использование модифицированного алгоритма SPIHT не дает значительных улучшений качества восстановленного изображения. Поэтому не всегда оправдано использовать данное расширение, так как сложность алгоритма сильно увеличивается. В данной работе расширенный алгоритм SPIHT введен, прежде всего, с той целью, чтобы показать, что обычный метод кодирования изображений SPIHT может быть обобщен на общий случай вейвлет-пакетной декомпозиции.

Кроме этого необходимо отметить, что работа модифицированного алгоритма SPIHT сильно зависит от глубины вейвлет-пакетного дерева коэффициентов.

Глубина вейвлет-пакетного дерева – это величина, определяющая количество уровней разложения множеств вейвлет-коэффициентов (полученных на первой итерации вейвлет-преобразования), которые несут в себе детали об изображении. Множество аппроксимирующих вейвлет-коэффициентов (полученных на первой итерации вейвлет-преобразования) разбивается так же, как и в классическом алгоритме SPIHT, а именно до тех пор, пока в низкочастотной области ни останется всего лишь один вейвлет-коэффициент. Последнее делается с целью получения максимально возможного качества изображения при декодировании [6].

Такие алгоритмы как SPIHT на данный момент могут иметь большой практический интерес по следующим причинам:

1. На любом этапе декодирования качество отображаемой в этот момент картинки является наилучшим для введенного объема информации о данном образе.

2. Использование вложенного кодирования.

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

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

Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (грант №06-02-17195).

а)	б)	в)
Рис. 3. Текстура D49: a) оригинал, б) SPIHT, bpp=0.25, PSNR=14.8, в) модифицированный SPIHT, bpp=0.25, PSNR=26.1

Литература

1. 
   Черников А.В., Чобану М.К. Сжатие изображений на базе вейвлет-преобразования и иерархического алгоритма кодирования // Цифровая обработка сигналов. 2005. № 2. C. 40-49.
   
2. 
   Lewis A.S. and Knowles G. Image compression using the 2-D wavelet transform // IEEE Trans. Image Proc., 1992. V. 1, P. 244-250.
   
3. 
   Shapiro J.M. Embedded image coding using zero-trees of wavelet coefficients // IEEE Trans. Signal Proc., 1993. V. 41, P. 3445-3462.
   
4. 
   Said A. and Pearlman W. A new, fast, and efficient image codec based on set partitioning in hierarchical Trees // IEEE Trans. on Circ. and Syst. for Video Tech. 1996. V. 6, P. 243-250.
   
5. 
   Sprljan N., Grgic S., Grgic M. Modified SPIHT algorithm for wavelet packet image coding // IEEE Video/Image Proc. and Multimedia Communication, 2002. P. 189-194.
   
6. 
   Волохов В.А., Моисеев А.А., Новоселов С.А., Приоров А.Л. Оценка качества цифровых изображений полученных в алгоритме иерархического кодирования // Докл. 8-й междунар. конф. «Цифровая обработка сигналов и ее применение». Москва, 2006. Т. 2, С. 406-409.
   
7. 
   Daubechies I. Ten Lectures on Wavelets. SIAM, Philadelphia, PA, 1992.
   
8. 
   Chui C.K., editor. An Introduction to Wavelets. Academic Press, New York, 1992.
   
9. 
   Воробьев В.И., Грибунин В.Г. Теория и практика вейвлет-преобразования. – СПб.: ВУС, 1999.
   



Modification of the spiht algorithm on the base of wavelet packet basis

Volohov V.

Yaroslavl State University
14 Sovetskaya st., Yaroslavl, Russia 150000. Phone: 7-4852-797775. E-mail: [email protected]
Digital images occupy more and more part of informational space. The development of Internet with the accessibility of the more powerful computers and with progress in technology of producing digital cameras, scanners and printers lead to the wide using of digital images. Hence the permanent interest to improvement of algorithms of compressing data, which are presented images. Compressing data is important as for the speed of transfer as for effectiveness storage.

This work is devoted to algorithm SPIHT (Set Partition in Hierarchical Trees) [1] and its expanded modification, which are not standard, but it’s very effective. These algorithms are based on the wavelet-transform and intend for the compression and progressive transfer of images. On the base of simplify model of this algorithm, the estimation of image quality of transfer information.

Let briefly review main features of the classical algorithm SPIHT and its modification.

Firstly, its progressive transmission the main aim of which consist in the steepest transmit of the most significant part of information about image. It gives the much reducing difference between initial image and reconstructed pattern. Quantitive this difference may be estimate through mean square error (MSE): where – common number of pixels, and – pixels of initial image and reconstructed image.

Two main principles of the SPIHT algorithm are used during progressive transmission consists in following: firstly, encoder must transmit the biggest coefficients (by absolute value) in first order, secondly, the most significant bits (at binary representation) because they carry the information much reducing the difference between initial image and reconstructed pattern.

Secondly, its effective sorting of wavelet coefficients needed for realization of progressive transmission. Algorithm that is used by SPIHT method is based on the fact that there is no necessity to sort all coefficients simultaneously. The main task of the stage of sorting pass at every iteration is the revelation of coefficient lied in some given threshold interval limits of which are changing at every passage of the cycle.

To estimate how image quality depends from numbers of bit plane value of PSNR (Peak Signal-to-Noise Ratio) can be used. , where MSE – mean square error, – maximal pixel of initial image.

References

1. 
   Said A. and Pearlman W. A new, fast, and efficient image codec based on set partitioning in hierarchical Trees // IEEE Trans. on Circ. and Syst. for Video Tech. 1996. V. 6, P. 243-250.
   



Применение согласованных вейвлет-фильтров для оценки анизотропности изображений

Кобелев В.Ю., Приоров А.Л.
Ярославский государственный университет им. П.Г. Демидова
150000, Россия, Ярославль, ул. Советская, 14, Тел. (0852) 79-77-75. E-mail: [email protected]
В последнее десятилетие наблюдается возросший интерес к методам вейвлет-обработки, обусловленный значительным развитием мощности вычислительных устройств, активным развитием практических приложений, связанных с передачей и хранением больших объемов информации [1-2]. В связи с этим актуальными являются разработки в области вейвлетов, направленные на оптимизацию имеющихся алгоритмов обработки как в области проектирования непосредственно вейвлет-функций с заданными свойствами, так и в области совершенствования структур алгоритмов.

В работах [3-5] проведено исследование с целью поиска вейвлет-фильтра, обеспечивающего безошибочное восстановление изображения с использованием только низкочастотных коэффициентов вейвлет-разложения (при полном отбрасывании высокочастотных коэффициентов). Пусть - есть исходное изображение, - квадрат модуля его Фурье-спектра, - квадрат АЧХ низкочастотного вейвлет-фильтра. Получено в работе [3], что если удовлетворяет выражению:

, (1), то вейвлет-функция, полученная после процедуры восстановления, может быть использована для разложения изображения, причем восстановленное с использованием только низкочастотных вейвлет-коэффициентов изображение будет идентичным первоначальному. Реализация процедуры восстановления импульсной характеристики вейвлет-фильтра по известному квадрату АЧХ этого фильтра рассмотрена в работе [3] (алгоритм восстановления есть модифицированный алгоритм Герберха решения фазовой задачи [6]).

Вейвлет-фильтр , амплитудный спектр которого удовлетворяет выражению (1), получен из соотношения исходного неискаженного изображения и изображения, искаженного сжатием. Он обеспечивает максимально возможное отношение сигнал/шум для восстановленного изображения. Поэтому в работе для обозначения двумерного вейвлет-фильтра с амплитудным спектром (1), предлагается применять термин “согласованный двумерный вейвлет-фильтр”.

Конечно, основное применение выражение (1) нашло в задаче синтеза как согласованных вейвлет-фильтров, так и близких к ним (обозначенные как “оптимизированные вейвлет-фильтры” [3]). Однако, дальнейший анализ полученной поверхности (1) показал, что она может быть использована и для оценки свойств анизотропности обрабатываемых изображений.

Под анизотропностью изображения понимается наличие в текстуре изображения одного или нескольких преобладающих направлений. Рассмотрим примеры подобных изображений. Изображение “Барбара” – преобладающее направление задают полоски на одежде; изображение “Фотограф” – преобладающее направление определяет тренога фотоаппарата, представленная ярко выраженными черными наклонными линиями; изображение “Корабли” – преобладающее направление определяют мачты кораблей. На рис. 1 приведен пример с изображением “Фотограф”.

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

Рассмотрим свойства квадрата АЧХ согласованного вейвлет-фильтра в части оценки анизотропности изображения:

• 
  преобладающее направление изображения определяется суммарной мощностью линий заданного направления на изображении (отметим, что кругам, дугам и прочие кривым линиям на поверхности соответствует образы, составленные множеством прямых линий с углом наклона определяемой производными в каждой точке кривой, по этой причине алгоритм не позволяет корректно выделять кривые линии);
  
• 
  между углами наклона линий изображения и поверхности существует однозначное соответствие: если - есть угол наклона линий на изображении, то - есть угол наклона линий на поверхности;
  
• 
  вне зависимости от местоположения линии на изображении, на поверхности соответствующий образ приводится к началу координат (к точке на частотной плоскости с координатами , ).
  

а)	б)
Рис. 1. Пример анизотропного изображения (а) и расчет соответствующего квадрата АЧХ согласованного вейвлет-фильтра (б)

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

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

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

Применительно к задаче векторизации растровых изображений метод может быть использован для автоматизации поиска прямых линий на изображениях инженерно-технического класса (чертежи, схемы и т.п.). За основу выделения прямых линий взято то свойство согласованных вейвлет-фильтров, что вне зависимости от фактического местоположения линии на чертеже, соответствующий образ на поверхности приводится к началу координат (точка на плоскости с координатами , ), а угол наклона образа однозначно соответствует углу наклона линии. Отметим, что из-за специфичности метода оценки анизотропности, алгоритм выделения линий работает только с прямыми линиями. Для более достоверного выявления прямых линий рекомендуется обрабатываемое изображение разбивать на блоки (например, размером пикселей), размер которых определяется детальностью чертежа, и для каждого блока выполнять обработку. Рассмотрим основные этапы алгоритма (алгоритм приводится с некоторыми упрощениями). Отдельные этапы поиска показаны на рис. 2.

• 
  Шаг 1: берем блок №1, размером пикселей (рис. 2а).
  
• 
  Шаг 2: рассчитываем (рис. 2б).
  
• 
  Шаг 3: строим функцию углового распределения интенсивности поверхности (рис. 2в).
  
• 
  Шаг 4: определяем приоритетные направления, соответствующие локальным максимумам , превышающие максимальный уровень фона (например, определили, что в блоке №1 присутствует прямая линия с наклоном ).
  
• 
  Шаг 5: Синтезируем прямую линию с углом наклона (модельная линия) и путем параллельного переноса в плоскости изображения, находим максимальные значения функции корреляции модельной линии и изображения, соответствующие реальным положениям линии с углом наклона на изображении.
  
• 
  Шаг 6: Определяем начало и конец обнаруженной линии.
  

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

Дополнительно рассмотрена работа алгоритма векторизации и в случае сильно зашумленного изображения. В качестве оценки достоверности обнаружения прямых линий на сильно зашумленном изображении в работе использовалась усредненная величина превышения пиков круговой функции распределения (рис. 2в) над средним уровнем фона (величина на рис. 2г). Получено, что алгоритм позволяет с довольно высокой достоверностью выявлять прямые линий растрового изображения с низким отношением С/Ш (порядка 4-5 дБ). С целью повышения достоверности обнаружения линий в работе дополнительно рассмотрена реализация алгоритма при формировании квадрата АЧХ согласованного вейвлет-фильтра с повышенным разрешением (например, пикс., хотя разрешение обрабатываемого блока составляет пикс.). Это позволяет с высокой достоверностью работать с изображениями, отношение С/Ш которых составляет всего 1-2 дБ (рис. 2г – кривая, помеченная звездочками).

а)	б)
в)	г)
Рис. 2. Этапы поиска прямых линий на изображении: а) – тестовое изображение, б) – квадрат АЧХ согласованного вейвлет-фильтра , в) – функция углового распределения для поверхности , г) – зависимость превышения выделяемого всплеска над средним уровнем фона от степени зашумленности изображения и разрешения

Литература

1. 
   Добеши И. Десять лекций по вейвлетам. – Москва-Ижевск: НИЦ “Регулярная и хаотичная динамика”, 2004. - 464 с.
   
2. 
   Воробьёв В.П., Грибунин В.Г. Теория и практика вейвлет-преобразования. – СПб.: Военный университет связи, 1999. - 204 c.
   
3. 
   Кобелев В.Ю., Приоров А.Л. Применение неразделимых вейвлет-фильтров в задачах сжатия изображений // Цифровая обработка сигналов. 2006. №2. С. 21-26.
   
4. 
   Кобелев В.Ю., Приоров А.Л. Синтез оптимизированных двумерных неразделимых вейвлет-фильтров для сжатия изображений // Телекоммуникации. 2006. №9. С. 7-12.
   
5. 
   Кобелев В.Ю., Моисеев А.А., Волохов В.А., Смоляков А.В. Синтез двумерных неразделимых вейвлет-фильтров с перестраиваемыми коэффициентами // Докл. 8-ой междунар. конф. “Цифровая обработка сигналов и ее применение” (DSPA’06). Москва. 2006. Т. 2, С. 389-392.
   
6. 
   Прэтт. У. Цифровая обработка изображений. - М.: Мир, 1982. Т. 1, - 312 с.
   



7.