РАЗДЕЛ 2
РАЗРАБОТКА АЛГОРИТМА ПОИСКА ИЗОБРАЖЕНИЙ В БАЗЕ ДАННЫХ ПО ХАРАКТЕРИСТИКАМ ИХ
СОДЕРЖИМОГО
Как было сказано в разделе 1, современные исследования в области контекстного
поиска изображений направлены на разработку новых способов представления
содержимого изображений и сравнения характеристик этого содержимого по причине
недостаточно высокого качества поиска с помощью существующих средств.
2.1. Общее описание предлагаемого алгоритма
Используемые в настоящее время метрики для сравнения гистограммных признаков
(наиболее адекватно характеризующих содержимое изображения) обладают рядом
недостатков. Проанализируем приведенные в таблице 1.2 формулы для вычисления
конъюнкции цветовых и текстурных гистограмм, евклидова, косинусного и
квадратичного расстояний, и определим область значений для каждой из этих
величин [3] (таблица 2.1).
Легко увидеть, что максимальное значение расстояния между гистограммами
определяется числом их элементов. При использовании же ненормализованных
гистограмм значения этих величин сверху практически не ограничены. По этой
причине расстояния сами по себе не отражают степень сходства изображений, для
которых вычислены; они имеют значение только при сравнении с другими
аналогичными величинами. Именно этим обусловлена черта, являющаяся общей для
всех современных систем контекстного поиска: в качестве результатов поиска
пользователю предъявляются все изображения из БД, отсортированные по убыванию
сходства с образцом.
Таблица 2.1
Область значений различных метрик для сравнения гистограммных признаков
Метрика
Область значений при использовании нормализованных цветовых гистограмм
Область значений при использовании нормализованных текстурных гистограмм
Конъюнкция гистограмм (D1)
Евклидово расстояние (D2)
Косинусное расстояние (D3)
Квадратичное расстояние (D4)
Предлагаемый алгоритм поиска использует в качестве критерия для сравнения
гистограммных характеристик содержимого изображений коэффициент их корреляции,
вычисляемый следующим образом [9]:
, (2.1)
где cov(H1,H2)– ковариация гистограмм H1 и H2,
у(H2), у(H2) – среднеквадратичное отклонение гистограмм H1и H2 соответственно.
Среднеквадратичное отклонение гистограммы вычисляется по формуле [9]:
, (2.2)
где D(H)–дисперсия, и м(H)– математическое ожидание элементов гистограммы:
. (2.3)
Ковариация двух гистограмм [9]:
(2.4)
Показано [9], что коэффициент корреляции обладает следующими свойствами:
-1<=с(H1,H2)<=1;
Если с(H1,H2)=0, значит, гистограммы H1 и H2 никак не связаны.
Если с(H1,H2)<0, значит, между гистограммами H1 и H2 существует отрицательная
корреляция, то есть малые значения одной гистограммы связаны с большими
значениями другой.
Если с(H1,H2)>0, значит, большие значения одной гистограммы связаны с большими
значениями другой (положительная линейная корреляция), причем, чем больше
значение с, тем сильнее зависимость H1 и H2.
Очевидно, что коэффициент корреляции не удовлетворяет свойствам идентичности,
неотрицательности и неравенства треугольника, перечисленным в разделе 1. Однако
его использование позволяет ограничить число изображений, выводимых в качестве
результатов поиска, включая в набор результатов только те, для которых с>0.
Более того, данный подход позволяет пользователю задавать минимально допустимую
степень сходства образца и результатов поиска.
Рассмотрим возможность применения данного подхода при поиске изображений по
гистограммным признакам их текстурного и цветового содержимого.
При использовании гистограммных признаков для представления содержимого
изображения контекстный поиск выполняется в виде последовательности следующих
этапов:
Дискретизация признака (Q- quantization) – приведение к базовому набору цветов
или яркостей путем замены исходных данных наиболее близкими значениями из
базового набора.
Построение гистограммного признака (H – histograming).
Сравнение гистограммных признаков (C – comparoson). На данном этапе вычисляется
характеристика сходства гистограммных признаков всех изображений базы данных с
признаком изображения- образца.
Сортировка изображений (S - sorting) по убыванию сходства с образцом.
При занесении нового изображения в базу данных для него последовательно
выполняются этапы Q и H. При поиске, когда в качестве образца поиска
используется изображение из БД, выполняются этапы C и S. Если же образцом
поиска является новое изображение, то выполняются этапы Q, H, C и S. Данный
алгоритм может быть проиллюстрирован блок- схемой, приведенной на рис. 2.1.
2.2. Описание алгоритма поиска по различным критериям
2.2.1. Поиск изображений в базе данных по текстурным признакам
Прежде чем приступить к решению указанной задачи, отметим, что в данном случае
рассматриваются изображения однородных текстур, представленных в градациях
серого (grayscale), аналогичные приведенным на рис. 1.6. Изображения цветных
текстур (как на рис. 1.7) будут рассмотрены далее, в разделе 2.2.3.
Рис. 2.1. Блок- схема алгоритма контекстного поиска с использованием
гистограммных признаков
Для grayscale – изображений определяющей характеристикой точки является ее
яркость, воспринимаемая человеческим глазом. Поскольку в современных мониторах
для воспроизведения точек (равно как и при хранении растровых изображений в
различных форматах) используется аддитивная RGB – система, то для выделения
яркостной составляющей не обходимо преобразование цвета, заданного в системе
RGB, в одно из цветовых пространств, использующих яркость (или, по- другому,
светлоту) в качестве одной из компонент, например, HSV, HLS. Поскольку нам
необходима только яркостная составляющая, рассмотрим, как она определяется при
переходе к этим цветовым простр
- Київ+380960830922