Поиск изображений с использованием вейвлетов

Рассмотрим изображение на разных уровнях разложения. Для разложения нужно использовать ортогональные вейвлеты скомпактным носителем.≪Дочерние≫ коэффициенты представляют изменениенекоего подмножества точек вышеупомянутогонабора точек. Наиболее ≪особым≫ множествомявляется то, которое соотвествует максимальному поабсолютному значению коэффициенту напредыдущем уровне j. Рассмотрим данный максимуми возьмем его максимальный ≪дочерний≫. Повторяяданный процесс, мы доберемся до уровня ., который представляет последний уровеньперед изображением. У нас будут отобраны некоторые коэффициенты, представляющиемножества точек изображения. Среди данных точек мы выберем точку с наибольшимградиентом.

Точка, в которой происходит некое глобальное изменение будет иметь большоезначение ≪особенности≫, поскольку в него внесли вклад большие коэффициенты. Менеезначительное изменение также приведет к извлечению точки, но с меньшим значением≪особенности≫.Для простоты изложения и понимания выше изложен одномерный случайизвлечения особых точек. В двумерном случае в нашем распоряжении имеется триподдиапазона уточняющих коэффициентов, обозначаемых в разных источниках как HL, LH, HH, или H, V, D. Рассмотрим отбор по разным диапазонам. Естественное изображение —изображение природного объекта, например ландшафт, цветок, животное. Изображение, например, строений, таковым не является. Рисунок62.

6 Замечание к выбору цветового пространства.

Выбор цветового пространства является достаточно важным параметром, влияющим на работу алгоритма. Следующие иллюстрации и графики аргументируют впользу пространства HSV. Цветовое пространство практически не влияет на выборособых точек при условии хорошей контрастности картинки (рис. 8), однако достаточносильно влияет при условии плохой контрастности изображения (рис. 7).Рисунок 7≪Проблемная≫ картинка (правыйверхний помидор красного цвета, остальные — зеленого).Графики, демонстрирующие значения ≪особенности≫ для рисунка 7, более ровныеи в целом возрастают более быстро ближе к правой границе графика, где и располагаютсянаиболее ≪особенные≫ точки.

2.7 Особенности формы.

Форма объекта также является достаточно важным параметром отбораизображений. Используя координаты особых точек изображения, мы можем произвестииндексацию изображений также по схожести формы. Рассмотрим две картинки —запроси потенциальный результат. Расстояния между наборами ≪особых≫ точек можнопосчитать как сумму расстояний от каждой точки до ближайшей точки другой карты. Безусловно, данная сумма не является метрикой в строгом смысле этого слова —данная≪метрика≫ не является симметричной. Тем не менее, она достаточно хорошо сравниваеткартинки с объектами схожей формы. Рассмотрим устойчивость относительно поворота, как одного из видов искажений. Для этого сравним изображение исходное и его копию, повернутую на небольшой угол. Левый столбец содержит изображения, исходное и модифицированное.

Правый столбецсодержит карты особых точек и графики расстояний от каждой точки первой картинки доближайшей ≪особой≫ точки другой картинки. Можно извлекать несколько ≪уровней≫ данной особенности. Первая и главная — это непосредственно расстояние. Оно показывает, насколько сильно две карты особыхточек отличаются ≪в общем≫. Вторым параметром можно взять достаточно показательныйпараметр —число точек, оставшихся вне расчета. Третьим, четвертым и пятымпараметров можно взять значения mean, var, skewness. Данные значения такжехарактеризуют расстояние.

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

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

Введение

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

2.9Формирование запроса.

Этап формирования запроса начинается с вычисления ≪особых≫ точекизображения. Далее для каждой ≪особой≫ точки рассчитываются цветовые особенности. После происходит инициализация массива оценок нулями. В основном цикле запросасчитается расстояние до каждой картинки как.

Исходный код.

Ниже приведена наиболее существенная часть программы запроса изображения (синтаксис MATLAB, использован Wavelet Toolbox).disp ('decomposing query…');%decompose queryimg=imread (QueryFileName);%resize to thumbnailimg=imresize (img, [ThSize ThSize]);%extract pointssalIdx=ExtractSalientPoints (img, salPtsCount);%convert to HSVimg=rgb2hsv (img);features=zeros (salPtsCount, 9);%for each point extract color momentsfor j=1:length (salIdx)%compute neightbour indices[r, c]=ind2sub ([ThSize, ThSize], salIdx (j));r=[(r-1)*ones (1,3), r*ones (1,3), (r+1)*ones (1,3)]; c=[c-1, c, c+1]; c=[c, c, c]; r (r>256)=r (r>256)-256;r (r<1)=r (r<1)+256;c (c>256)=c (c>256)-256;c (c<1)=c (c<1)+256;ind=sub2ind ([ThSize, ThSize], r, c);for k=1:3colorPlane=img (, k);features (j, 3*(k-1)+1) = mean (colorPlane (ind));features (j, 3*(k-1)+2) = var (colorPlane (ind));features (j, 3*(k-1)+3) = skewness (colorPlane (ind));end;end;scores=zeros (5, filesCount);disp ('scoring…');for i=1:filesCountdisp ([num2str (i), ' of ', num2str (filesCount)]);for j=1:salPtsCountdist=features (j:)-squeeze (Index.features (i, j:))';dist=dist*dist';scores (1,i)=scores (1,i)+dist;end;[dist, unused, m, v]=MapDistance (salIdx, Index. salP (i:), ThSize);scores (2,i)=dist;scores (3,i)=unused;scores (4,i)=m;scores (5,i)=v;end;%scale every score and compose themsingleScores=zeros (1, filesCount);for i=1:length (Weights)scores (i:)=scores (i:)/max (scores (i:));singleScores=Weights (i)*scores (i:);end;203.

1Тестирование.

Для тестирования данного алгоритма была составлена база картинок в количестве213 штук, которая состояла из кластеров изображений —группизображений, похожихдруг на друга, каждый кластер представлял разный класс изображений. В качестве запросабралась одна картинка из базы. В силу небольшого размера базы каждый запрос содержитнекоторое количество (часто до половины) не релевантных изображений. Рисунок 9Рисунок 9 иллюстрирует запрос к базе данных. В качестве запроса выступилоизображение с весьма четко выделяемой формой. Алгоритм выбрал и правильноранжировал все изображения данного кластера. Изображения искажены в связи снебольшим размером эскизов (thumbnail), сохраненных в базе данных и принудительнымрастягиванием в MATLAB на этапе построения графика. Рисунок 10Рисунок 10 иллюстрирует запрос с достаточно хорошо выделяемой формой, но ужес присутствием текстурированного фона. В данном случае алгоритм также правильновыбрал все изображения кластера, правильно их ранжировав.

Заключение

.

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

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

Вашингтона, либо описываемому в [13].  Принципиально иная визуализация результата, подобно методике, описанной в [14].  Оптимизация алгоритма с целью увеличения скорости расчетов.Разработка и применение более объективной методики оценкирелевантности результатов поиска [15,16]. .

Более строгое исследование влияния начального уровня и вейвлета накачество особых точек.Рассмотрение текстурных особенностей.Расширенное исследование влияния цветового пространства на качество≪особых≫точек [17]. Списокиспользуемойлитературы1. D igital Libraries, Value, and Productivity. Go Wiederhold.

http://www.cacr.caltech.edu/~slombey/work/KB/libs/2. Content-Based Image Retrieval Systems. Peter L. Stanchev.

3. Content-Based Image Retrieval Systems: A Survey. R emco C. V eltkamp4. S tate-of-the-Art in Shape Matching. R.

emco C. V eltkamp, Michiel Hagedoorn5. F.

ast Multiresolution Image Querying. C.E. J acobs, A. Finkelstein, D.H. Salesin.

6. Вейвлеты в компьютерной графике. Э. Столниц, Т. ДеРоуз, Д. Салезин7. T he QBIC project: Querying images by content using color, texture and shape.W. Niblack, R.

B arber, W. E quitz, M.

F lickner, E. G lasman, D. P.

etkovic, P. Yanker, C. F aloutsos, G. Taubin.

8.

http://www.jpeg.org/jpeg2000/9. An Introduction to Wavelets. Charles K. Chui.

10. C ontent-Based Image Retrieval Using Wavelet-based Salient Points. Q. T.

ian, N. Sebe, M.S. Lew, E. L oupias, T.S. Huang11. L ocal grayvalue invariant for image retrieval. C. S hmid, R. M.

ohr12. A n Efficient Color Representation for Image Retrieval. Y. D eng, B.S. Manjunath, C. K enney, Michael S.

Moore, Hyundoo Shin.

13. S calable Color Image Indexing And Retrieval Using Vector Wavelets. E lifAlbuz, Erturk Kocalar, Ashfaq A.

K hokhar14. S patial Visualization for Content-Based Image Retrieval.

B aback Moghaddam, Qi Tian, Thomas Huang15. M ulti-class relevance feedback content-based image retrieval. J ing Peng16. R.

elevance Feedback Techniques in Interactive Content-Based Image Retrieval. Yong Rui, Thomas S. H uang, and Sharad Mehrotra17. A n Efficient Color Representation for Image Retrieval.

Y ining Deng, B. S. M anjunath, Charles Kenney, Michael S. Moore and Hyundoo Shin25.