ЛММИИ на РОМИП-2009: Методы поиска изображений по визуальному подобию и детекции нечетких дубликатов изображений *

2 навигации среди этой массы информации, о быстром и точном поиске нужных пользователю данных. На сегодняшний день существует два основных подхода к поиску изображений: поиск на основе текстового запроса и поиск на основе визуального образца. Каждый из этих подходов имеет свои преимущества и недостатки и направлен на решение своих задач. Главным применением поиска по визуальному образцу являются те области, где сходство важнее, чем семантика: поиск в медицинских коллекциях, например, среди рентгеновских снимков; поиск в дизайнерских коллекциях, когда дизайнер ищет некоторое подходящее по цветовой гамме и текстуре изображение; поиск в архивах правоохранительных органов интересующих криминалистов лиц или объектов. Основной проблемой, затрудняющей эффективное и однозначное решение проблемы поиска в коллекции изображений, является так называемая проблема «семантического разрыва» отсутствия однозначной связи между низкоуровневыми характеристиками и семантикой изображения. Критерий сходства, вводимый на основании числовых значений пикселов изображений или полученных на их основе производных характеристик, не в состоянии уловить семантику запроса, подразумеваемую пользователем. Проблема состоит в разных семантических пространствах, в которых оперируют пользователь и система поиска изображений. Система оперирует низкоуровневыми характеристиками, такими как цвета, границы, текстуры. Пользователь же оперирует более высокоуровневыми, абстрактными и часто более субъективными понятиями. Хотя подход поиска по образцу, пытаясь решить проблему семантического разрыва, заставляет пользователя оперировать в большей степени понятиями своего, машинного, пространства понятий (общей цветовой гаммы, распределения цветов, текстур, контуров), тем не менее, здесь также остаѐтся большой простор для субъективных оценок. Одним людям для признания изображений визуально похожими достаточно наличия у них общей цветовой гаммы, другим требуются более жесткие условия, например, наличие похожих по форме объектов. Ещѐ одной трудностью, связанной с созданием баз изображений, является отсутствие общих, универсальных методов, подходящих для любых коллекций изображений. Разные коллекции и разные задачи требуют своих методов обработки и поиска. Так, например, коллекции рентгеновских снимков имеют свои специфичные особенности и не позволяют использовать методы, подходящие для 109

3 поиска любительских фотографий. В данной работе рассматриваются методы, направленные на поиск в реальной многопользовательской коллекции фотоснимков, что приводит к необходимости учитывать потребности пользователей и особенности восприятия изображений. Активная разработка методов поиска на основе визуального образца началась в начале 90-х годов. За это время было предложено множество различных методов выделения признаков изображений и сравнения полученных представлений. В качестве признаков предлагается брать цветовые характеристики [9] или текстурные характеристики [14], дескрипторы формы [16] или коэффициенты вейвлет-преобразования [12]. В качестве меры сходства или отличия чаще всего предлагается брать различные метрики или псевдометрики (сравнение мер расстояния, часто применяющихся для поиска изображений, проведено в [11]). В то же время существуют и подходы, основанные на других принципах, например баейсовских вероятностных моделях [3]. Представляет интерес подход, позволяющий использовать для поиска изображений техники, предложенные в области текстового поиска. Так, например, в работе [13] для поиска изображений по визуальному образцу предлагается использовать структуры данных инвертированных файлов и схемы определения весов признаков на основании частот встречаемости признаков в изображении-запросе и всей коллекции изображений. Другой задачей, также анализируемой в данной статье, является поиск нечетких дубликатов изображений. Большие коллекции изображений, например изображения Интернет, как правило, содержат достаточно большое количество таких изображений. Кластеризация нечетких дубликатов изображений на группы позволяет исключить из просмотра практически идентичные изображения, не представляющие интереса для пользователя, или удалять такие изображения из базы для экономии места. Существуют также и другие приложения поиска нечетких дубликатов, например, определение случаев нарушения авторских прав или детекция спама [15]. В зависимости от области применения понятие нечетких дубликатов изображений может различаться, и для нахождения таких изображений могут использоваться различные методы. Так, в качестве нечетких дубликатов могут пониматься изображения, отличающиеся разрешением или наличием шума, подвергшиеся небольшим фотометрическим преобразованиям, снимки одной и той же сцены, выполненные с небольшими изменениями ракурса камеры. Именно в таком смысле 110

4 нечеткие дубликаты изображений понимались при выполнении данной работы. Другим случаем определения нечетких дубликатов является поиск изображений, подвергшихся сильным искажениям, изображений, содержащих отдельные одинаковые сегменты [7] или снимков одного объекта с значительно различающихся позиций. 2. Поиск изображений по визуальному образцу Важнейшей задачей при построении любой системы поиска изображений является выбор наиболее информативного представления изображений. В данной статье производится анализ и сравнение методов выделения таких признаков, которые являются наиболее перспективными для сравнения изображений с точки зрения их визуального сходства, воспринимаемого человеком. Исследуются признаки, отвечающие за различные визуальные характеристики изображений: цветовые, текстурные, характеризующие распределение градиента изображения, наличие фона - и делаются выводы. 2.1 Цветовые автокоррелограммы Распределение цветов на изображении очень важная для зрительного восприятия человека характеристика. Эксперименты по изучению психофизиологических особенностей человеческого зрения [6] показали, что распределения цветов на изображении бывает достаточно для различения типов сцен и многих типов объектов. Одним из способов описания распределения цветов на изображении являются цветовые автокоррелограммы [5]. Цветовые коррелограммы описывают пространственную корреляцию цветов на изображении и строятся следующим образом. Пусть p ( x, y) точка изображения I. Расстояние между точками измеряется с помощью метрики d( p, p ) max< x x, y y >. Пусть все возможные цвета изображения квантуются на m уровней: c1, c2,, cm. Обозначим цвет точки p на изображении I как I( p ), а множество точек, имеющих цвет c, как Ic < p I( p) c>. Тогда коррелограмма для изображения I : ( k ) ( I) P ( p I p p k) c, c j p1 Ic 2 c j 1 2 p2 I 111

5 представляет собой трехмерную таблицу чисел, в которой ( k,, j ) значение определяет вероятность нахождения точки -го цвета на расстоянии k от точки j -го цвета. При использовании для вычисления кореллограммы дискретного количества s расстояния между точками, длина полученного вектора 2 признаков будет O( m s ). Автокоррелограмма определяет пространственную корреляцию между парами одинаковых цветов: ( k) ( k) ( I) ( I) и будет иметь длину O( ms ). c 112 c, c 2.2 Текстурные признаки изображений Текстура является очень важным с точки зрения восприятия и распознавания объектов человеком свойством изображений [10]. На многих изображениях она позволяет определять свойства областей, критически важные для корректного выполнения анализа содержания изображения. Свойства, отвечающие человеческому восприятию, имеет текстурный признак, введенный Hdeyuk Tamura в [14]. Введенный текстурный признак включает такие характеристики, как грубость (coarseness), контраст (contrast), направленность (drectonalty) текстуры. Признак, характеризующий грубость, неявно связан с размером примитивных элементов, формирующих текстуру. Расчет этого показателя делится на несколько этапов. Во-первых, в каждой точке ( xy, ) изображения рассчитываются шесть значений средней k k интенсивности пикселов в окне размером 2 2 : k k 1y x 1 1 Ak ( x, y) = g(, j), 2 2k = x 2 k 1 j= y 2 k 1 где k = 0,1,,5, g(, j ) значение интенсивности в точке (, j ) изображения. Затем для каждой точки ( xy, ) вычисляются абсолютные разности между парами средних интенсивностей, вычисленных в непересекающихся окнах, в горизонтальном и вертикальном направлениях относительно текущей точки, и находится значение k, которое максимизирует значения вертикальной и горизонтальной разностей. В качестве наилучшего размера окна для этой точки k берется значение S ( x, y ) = 2. best

6 Тогда значение признака грубости текстуры для изображения размером M N берется равным среднему значению наилучшего размера S best для всех точек изображения: M N F = S (, j). crs best =1 j=1 Признак, характеризующий контраст, является показателем того, как уровни серого q : q = 1, 2,, qmax варьируются в пределах изображения I и в какой степени их распределение смещено к белому или черному. Для вычисления контраста используются центральные моменты второго и четвертого 4 порядков гистограммы уровней серого изображения, и значение признака определяется как: 4 F con =, =, 1/4 4 Ещѐ одним признаком текстуры согласно Tamura является направленность. Этот признак вычисляется с использованием значений величин и направлений градиента интенсивности в точках изображения. Для этого строится гистограмма направлений градиента Hdr ( ), и в качестве признака затем используется либо сама эта гистограмма, либо вычисляется степень направленности, связанная с величинами пиков гистограммы: n peaks 2 F = 1 rn H ( ), dr peaks p dr p=1 w p где n peaks число пиков гистограммы, больших некоторого порога, p соответствующее p -му пику значение угла, w p некоторая окрестность p го пика, r нормализующий множитель. Признак F dr лучше использовать для изображений, содержащих одну текстуру, фотографии же различных сцен, для которых нужно получить текстурные характеристики, содержат, как правило, несколько типов текстур. Поэтому в качестве признака направленности для них было решено использовать вместо одного признака F dr гистограмму H dr. В экспериментах была использована гистограмма с 16 ячейками. 113

7 2.3 Гистограммы ориентаций градиентов В таком виде эти дескрипторы были впервые предложены и описаны исследователями Navneet Dalal и Bll Trggs в работах [1, 2]. Основанием рассматриваемого метода построения дескрипторов на основе HoG является то, что наличие и форма локальных объектов на изображении могут быть описаны распределением интенсивности градиентов. Изображение делится на малые регионы «клетки», для каждой клетки составляется гистограмма направлений градиентов точек этой клетки. Комбинация этих гистограмм и представляет собой дескриптор. Существует несколько типов дескрипторов, наиболее часто используемым является прямоугольный дескриптор R-HoG (Рис. 1). Использованный в эксперименте дескриптор имеет 3 3 клеток, 4 блока, включающих 4 клетки и 9 ячеек гистограммы. Рис. 1 Прямоугольный дескриптор R-HoG. Для улучшения качества детекции локальные гистограммы могут быть нормализованы по контрасту путем вычисления меры интенсивности по большему региону изображения, т.н. блоку, и использования этого значения для нормализации гистограмм всех клеток в блоке. Такая нормализация ведет к лучшей инвариантности относительно изменений освещенности и теням. Авторы, предлагающие дескрипторы HoG, подчеркивают преимущество этого подхода по сравнению с подобными подходами edge orentaton hstograms, scale-nvarant feature transform descrptors, shape contexts. 114

8 2.4 Характеристика однородности фона Для различения типов сцен также может быть полезен признак, характеризующий однородность изображения и его фон. Наличие так называемого фона областей компактно расположенных пикселей, обладающих примерно одинаковыми цветовыми признаками, причем относительная площадь этих областей весьма велика и достигает десятков процентов, является важной характеристикой, сильно влияющей на восприятие изображения. Для вычисления этого признака предлагается использовать комбинацию методов, предложенных в статьях [17, 18]. Признаком отсутствия у изображения фона можно считать равномерность его гистограммы. Рассмотрим цветное изображение I размером XI YI, имеющее R G B три цветовые компоненты I j, I j, I j, =1,, XI, j =1,, YI для R, G, B соответственно. Элементы этих компонент принимают значения из диапазона . В качестве численной оценки степени равномерности гистограмм цветовых компонент R H, G H, B H, = 0,, M можно использовать энтропию как меру информативности каждого из столбцов гистограммы: M x, =0 x E =, x = R, G, B, = 0,, M, где x 0, если H = 0, x x x, = H H x log, если H 0. X IYI X IYI На основании полученного значения энтропии определяется признак содержания фона в каждой из цветовых компонент изображения: x x E B = 1, x = R, G, B. log M и для всего изображения: R G B B = B B B. В [18] показано, что построенный таким образом признак будет инвариантным к конкретному цвету и интенсивности фона, а также к контрасту информативной части изображения по отношению к окружающему ее фону и будет изменяться в пределах от 0 до 1. Для достижения монотонного изменения признака относительно 115

9 процентного отношения пикселей, принадлежащих фону, для изображений, содержащих шум или подвергшихся сжатию, в процессе вычислительных экспериментов была использована предварительная обработка изображений медианным фильтром. Полученное в ходе эксперимента типичное значение признака для фотографий реальных сцен лежит в пределах Результаты эксперимента Программная реализация была выполнена с использованием свободных библиотек с открытым исходным кодом Apache Lucene и Lre [8], что позволило сосредоточить внимание на разработке методов анализа изображений, использовав имеющийся в этих библиотеках функционал для индексирования изображений с помощью индекса Lucene, хэширования, поиска по индексу, а также архитектуру библиотеки Lre, предназначенной для поиска по визуальному подобию. В рамках дорожки поиска по визуальному подобию было проведено три эксперимента: 1. поиск с использованием в качестве признаков изображений только гистограмм ориентаций градиентов и упорядочением результатов в порядке возрастания евклидова расстояния между векторами признаков найденных изображений и изображения-запроса (myrtle-3); 2. поиск с использованием признаков цветовых автокоррелограмм, текстурного признака Tamura и гистограмм ориентаций градиентов и упорядочением результатов в порядке возрастания сумм расстояний между соответствующими признаками (myrtle-1); 3. поиск с использованием всех перечисленных выше признаков, взвешенных с помощью признака однородности фона (myrtle-2). Результаты полноты и точности этого года (xxxx-1, myrtle-1, myrtle-2, myrtle-3) вместе с аналогичными результатами прошлого года приведены в следующих четырех таблицах (yyyy-1 лучший результат прошлого года, подробности по прогону jade-7 на основе вейвлет-разложения и прогону jade-2 на основе матрицы изменения яркостей можно посмотреть в нашей статье за прошлый год [4]). Приведенные оценки различаются по двум параметрам: уровню релевантности (учитывались только «сильно» релевантные или «сильно» и «слабо» релевантные изображения-ответы) и по способу объединения оценок асессоров ( and ответ верный, только если 116

10 оба асессора считают так, or ответ верный, если хотя бы один из асессоров считает так). Таблица 1. Strong relevance ( and metrc) Run ID xxxx-1 mrtle- mrtle- mrtle- yyyy-1 jade-7 jade-2 Metrc Precson(10) Bpref Bpref Recall Av. precson Precson R-precson Precson(5) Таблица 2. Strong relevance ( or metrc) Run ID xxxx-1 mrtle- mrtle- mrtle- yyyy-1 jade-7 jade-2 Metrc Precson(10) Bpref Bpref Recall Av. precson Precson R-precson Precson(5) Таблица 3. Weak relevance ( and metrc) Run ID xxxx-1 mrtle- mrtle- mrtle- yyyy-1 jade-7 jade-2 Metrc Precson(10) Bpref Bpref Recall Av. precson Precson R-precson

11 Precson(5) Таблица 4. Weak relevance ( or metrc) Run ID xxxx-1 mrtle- mrtle- mrtle- yyyy-1 jade-7 jade-2 Metrc Precson(10) Bpref Bpref Recall Av. precson Precson R-precson Precson(5) Из приведенных данных видно, что результаты данной дорожки этого года (лучшие значения каждого показателя выделены жирным шрифтом) сравнимы с результатами прошлого года (лучшие значения выделены курсивом). Интересен также тот факт, что использование только гистограмм ориентаций градиентов дало лучшие результаты, чем использование этого признака совместно с цветовыми и текстурными характеристиками. Это означает, что при оценке схожести изображений человек большее внимание уделяет закодированной в дескрипторе HoG информации о форме объектов, появляющихся на изображении и некоторых основных их цветовых характеристиках, чем корреляции цветов изображения и его текстурным характеристикам. 3. Поиск нечетких дубликатов изображений 3.1 Метод кластеризации изображений В рамках задачи поиска нечетких дубликатов изображений был продолжен подход прошлого года на основе использования в качестве признаков изображений матрицы изменений яркостей (Matrx of Brghtness Varaton MBV) [4]. Матрица изменений яркостей основана на вычислении знаков частных производных функции яркости изображения: I I M x, y sgn sgn x y 118 xy,.

12 Полученное таким образом представление устойчиво к строго монотонно возрастающим преобразованиям яркости изображений, а также обладает вычислительной простотой. В данной работе был использован иерархический подход к кластеризации групп нечетких дубликатов на основе MBV признаков: составление кластеров первого уровня производилось на основе признаков небольшой длины, дальнейшая кластеризация проводилась с использованием признаков довольно большой длины. На первом этапе признак MBV вычислялся для изображений в тонах серого, уменьшенных до размера 3 3. Этот признак будет представлять собой двоичный вектор из 8 компонент или некоторое соответствующее десятичное число. В начальные кластеры входят изображения с одинаковыми значениями построенного таким образом признака (для коллекции РОМИП было получено порядка 60 начальных кластеров). На втором этапе использовался MBV признак, построенный по цветному изображению размером и представляющий собой вектор длиной порядка Процедура кластеризации, применяемая для построения кластеров второго уровня, аналогична применяемой в прошлом году [15]: строятся кластеры из всех близких некоторому изображению картинок, затем те из них, которые имеют большую заданного порога мощность пересечения и меньшее другого порога расстояние между центрами, объединяются. 3.2 Результаты эксперимента В результате применения описанной выше иерархической кластеризации, а также использования программной архитектуры на основе библиотек Lre и Lucene удалось значительно ускорить работу алгоритмов, с нескольких дней до нескольких часов. Показатели качества предложенного метода (myrtle) вместе с соответствующими показателями других участников и результатами прошлого года (jade-1, jade-3 на основе MBV, jade-2 на основе вейвлет-преобразования, см. [4]) приведены в таблице 5. Таблица 5. Результаты поиска нечетких дубликатов. xxxx-1 jade-1 jade-2 jade-3 myrtle xxxx-6 xxxx-7 xxxx-8 xxxx-9 xxx10 FPR 2.7Е-4 3.9E-6 4.1E-4 2.1E E E-4 8.4E-5 5.8E-4 FNR Precson Recall