=Paper=
{{Paper
|id=None
|storemode=property
|title=Поиск визуально подобных изображений на основе машинного обучения
(Machine Learning of Visually Similar Images Search)
|pdfUrl=https://ceur-ws.org/Vol-934/paper20.pdf
|volume=Vol-934
|dblpUrl=https://dblp.org/rec/conf/rcdl/VarlamovS12
}}
==Поиск визуально подобных изображений на основе машинного обучения
(Machine Learning of Visually Similar Images Search)
==
https://ceur-ws.org/Vol-934/paper20.pdf
Поиск визуально подобных изображений на основе
машинного обучения
© А. Д. Варламов © Р. В. Шарапов
Владимирский государственный университет им. А. Г. и Н. Г. Столетовых
Муром
varlamov_aleks@mail.ru info@vanta.ru
существенных свойств изображений и построении
Аннотация на их основе сигнатур, используемых в дальнейшем
для сравнения пар изображений. В каждую пару
Рассматриваются вопросы поиска изображе-
ний по визуальному образцу. Предлагается всегда входит изображение из коллекции и
изображение-образец, подобное которому стремится
методика разработки алгоритма оценки
найти пользователь. Результатом сравнения явля-
визуальной близости пары изображений на
ется величина, называемая визуальным подобием
основе машинного обучения. Анализиру-
(иногда тематической близостью) изображений. С
ются признаки изображений, которые могут
точки зрения информационного поиска данная
применяться в алгоритмах поиска. Решается
проблема выбора из них ключевых. оценка, выполненная человеком-экспертом, будет
являться содержательной релевантностью, а
1 Введение рассчитанная в системе — релевантностью
формальной.
Развитие компьютерной техники и технологий Свойства оцениваются алгоритмами вычисления
привели к бурному росту количества цифровых значений важных численных величин и называются
изображений. Источников таких изображений признаками. Подобных признаков можно выделить
множество — цифровые фотоаппараты и видеока- достаточно много. В общем случае они разделяются
меры, видеорегистраторы, камеры видеонаблюде- на две группы: глобальные и локальные. К
ния, мобильные телефоны, сканеры и т. д. Появи- глобальным признакам можно отнести основные
лись цифровые архивы, содержащие миллионы цвета, текстуры, формы, значимые элементы всего
снимков. При таких объемах данных важное значе- изображения. Локальные признаки высчитываются
ние приобретает поиск нужных изображений. для небольших частей (блоков) изображения [2].
Существует несколько направлений поиска по Для обозначения значений признаков также
изображениям: поиск по содержанию (найти фото- употребляют термин дескриптор. Набор признаков
графию человека или изображение, к примеру, (иногда говорят вектор признаков), описывающий
берёзы), поиск по визуальному образцу (найти изображение для определенной задачи, называется
изображения, похожие на заданное), поиск по сигнатурой. Признаки, отобранные из множества
описаниям (найти изображение, помеченное как альтернативных для их применения в некоторой
«Совершенно секретно» или «Москва») и т. д. задаче анализа изображений и вошедшие в
Каждое из направлений поиска имеет свои особен- сигнатуру, называют ключевыми.
ности и сферы применения. При поиске изображений по образцу
Целью работы является рассмотрение вопросов анализируются не отдельные экземпляры, а пары
построения системы поиска по визуальному образцу изображений, которые сопоставляются друг другу.
в относительно больших (десятки тысяч) коллек- Поэтому в отличие от других задач анализа в
циях изображений. текущей проблеме от признаков изображений
переходят к признакам пар, значения которых
2 Текущее состояние проблемы находятся как абсолютные разности значений
соответствующих признаков каждого из изобра-
Поиск изображений по визуальному образцу жений пары. Такая несложная формула позволяет
является интереснейшей задачей, решению которой моментально их рассчитать для проиндексирован-
посвящено множество работ. Достаточно подробные ных изображений и реализовать на практике поиск с
обзоры приведены в [1, 2, 6, 7]. приемлемыми временными характеристиками.
Данный вид поиска заключается в извлечении
3 Существующие признаки изображений
Труды 14-й Всероссийской научной конференции Системы, осуществляющие поиск по визуаль-
«Электронные библиотеки: перспективные методы и ному образцу, активно используют различные
технологии, электронные коллекции» — RCDL-2012, признаки изображений. Эти признаки отличаются
Переславль-Залесский, Россия, 15-18 октября 2012 г. большим разнообразием.
113
Вопросы использования цветовых характеристик В работе [10] предлагается использовать
обсуждаются в [4]. Выделяются такие признаки, как цветовые признаки. Для этого строится цветовая
общий цвет, наиболее частотные цвета, регуляр- гистограмма, учитывающая пространственное
ность размещения цветов, сложность образов и т.д. расположение цветов, и вычисляются цветовые
Работа [8] посвящена использованию текстурных моменты. Для оценки подобия двух изображений
признаков. Авторы выделяют признаки контраст- сравниваются параметры распределения их цветов:
ности, грубости, направленности, линейных обра- математическое ожидание по каждому из цветовых
зов, регулярности и шероховатости текстур. каналов и попарные ковариации распределений
каналов.
В [9] рассматриваются различные признаки
формы: Фурье признаки (FD), признаки кривизны В работе [13] используются признаки цветовых
пространства (CSSD), признаки Церник-моментов автокоррелограмм, текстурный признак Tamura,
(ZMD) и сеточные признаки (GD). Анализируются гистограммы ориентаций градиентов.
слабые и сильные стороны указанных признаков Таким образом, существует достаточно большое
изображений. количество признаков, которые могли бы исполь-
В работе [5] для поиска изображений по зоваться в задачах поиска изображений по
содержанию предлагается использовать признак визуальному образцу. Тем не менее, большинство
однородности текстуры (Homogeneous Texture работ включают лишь часть существующих
Descriptor, HTD), признак граничной гистограммы признаков изображений, комбинируя их и разраба-
(Edge Histogram Descriptor, EHD), масштабируемый тывая на их основе сигнатуры. В связи с тем, что
признак цвета (Scalable Color Descriptor, SCD), многие признаки могут быть взаимосвязаны между
признак доминирующего цвета (Dominant Color собой, важной задачей является их рациональный
Descriptor, DCD). Эти признаки подробно описаны в отбор.
[3] и используются в различных системах.
4 Методика проведения исследования
Достаточно интересны работы, выполненные в
рамках Российского семинара по оценке методов Схематично предлагаемая методика работ для
информационного поиска (РОМИП). Начиная с 2008 построения алгоритма определения визуального
года на семинаре проводятся дорожки (секции, подобия изображений на основе машинного обуче-
посвященные конкретным проектам) поиска ния показана на рисунке 1. Ее можно представить в
изображений по образцу. виде следующих этапов, которые должны быть
В работе [14] предложен алгоритм поиска последовательно выполнены:
изображений на основе нечетких цветовых Этап 1. Из коллекции изображений формируется
гистограмм, вычисляемых в пространстве CIE обучающая выборка. Она состоит из множества
L*a*b*. Предлагается кроме главной использовать прецедентов, каждый из которых включает в себя
набор дополнительных гистограмм, построенных пару изображений и степень их близости,
для определенных участков изображения. оцененную экспертом.
В работе [11] рассматривается возможность Этап 2. Программно реализуются (при необходи-
цветовой модели HIS (Hue, Saturation, Intensity) при мости и разрабатываются) алгоритмы вычисления
поиске изображений по содержанию. HSI — это всевозможных признаков на изображениях.
цилиндрическое представление цветовой модели Этап 3. Для каждой пары изображений
RGB, состоящее из следующих компонент: цветовой вычисляются значения всех признаков.
тон, насыщенность и интенсивность. Автор также
предлагает использовать модель HLD (Hue Layout Этап 4. Проводится факторный анализ призна-
Descriptor). ков, в результате которого определяются главные
признаки, значения которых будут использоваться в
В [16] используются уменьшенные копии обучении нейронной сети и алгоритмы вычисления
изображений для поиска похожих снимков. В которых станут частью конечного алгоритма оценки
основу работы положен тот факт, что человеческое визуального подобия изображений.
восприятие позволяет с хорошей точностью
понимать содержание изображений с маленьким Этап 5. Обучается нейронная сеть. По заверше-
разрешением. Для цветных изображений человеку нию этого процесса запоминаются данные, характе-
достаточно разрешения 32х32, чтобы достичь ризующие величины ошибок нейронной сети
точности распознавания сцен превышающей 80%. относительно входной выборки. Эти показатели
преобразуются в полноту и точность — целевые
значения оценки качества выполняемой работы.
114
Коллекция изображений
Отбор изображений Выбор признаков, Отбор изображений
которые можно
Изображения использовать для оценки Изображения
тематической близости
Формирование обучающей Признаки Формирование тестовой
выборки выборки
Пары изображений Пары изображений
Вычисление признаков Вычисление признаков
изображений изображений
Экспертны
е оценки Значения Ключевые Оценки
степени признаков признаки асессоро
близости в степени
каждой Факторный анализ близости
пары признаков и анализ каждой
временных характеристик пары
их вычисления
Значения
Значения ключевых
ключевых признаков
признаков
Обучение нейронной сети Параметры
Прогон нейронной сети
сети
Показатели Показатели
качества оценки качества оценки
на обучающей на тестовой
выборке выборке
Сопоставление результатов.
Требование к
Вывод о репрезентативности
расширению
обучающей выборки
обучающей
выборки
Рис. 1 Методика проведения работ для построения алгоритма определения визуального подобия
изображений на основе машинного обучения
Этап 6. Из коллекции изображений формируется Этап 9. Сравниваются полнота и точность
тестовая выборка. Ее структура и характеристики анализа нейронной сетью изображений обучающей
(объем, соотношение близких и неблизких пар) выборки с полнотой и точностью анализа нейронной
должны соответствовать структуре и характеристи- сетью изображений тестовой выборки. При
кам обучающей выборки. приблизительно одинаковых значениях соответству-
Этап 7. Вычисляются значения ключевых ющих показателей работа считается завершенной.
признаков всех изображений, входящих в тестовую По завершению пятого этапа, на котором
выборку. выполняется машинное обучение, может быть уже
Этап 8. Прогоняется нейронная сеть на тестовой достигнута цель — получены все данные для их
выборке с определением полноты и точности. сборки в алгоритм определения подобия пары
115
произвольных изображений. На дальнейших этапах эвристически решить ее человеку не под силу,
проводится анализ полученного результата и, при поэтому требуется формальный подход. В основе
необходимости, принимается решение о возврате на метода сокращения количества признаков предла-
предыдущие этапы работы. По завершении всего гается использовать факторный анализ, широко
цикла становятся известными основные численные применяемый при многомерном статистическом
характеристики, отражающие качество полученного анализе для понижения размерности данных. За
алгоритма: полнота и точность. фактор будем принимать абсолютную разность
Применительно к решаемой задаче полнота значений одного и того же признака, рассчитанного
(recall) определяется как отношение числа правиль- для обоих изображений пары. Сокращая факторы,
но идентифицированных близких пар изображений, мы будем сокращать признаки, уменьшая сложность
к общему числу близких пар в выборке; точность вычислений.
(precision) определяется как отношение количества Факторный анализ предполагает анализ
найденных близких пар изображений к числу пар, корреляционной матрицы с построением графика
которые система посчитала тематически близкими. под названием “Каменистая осыпь”, на котором
Если на последнем этапе выявлено расхождение отражается значимость каждого фактора и на осно-
значений полноты или точности в выборках, то вании которого принимается решение о количестве
исходная выборка является нерепрезентативной. В и составе выделяемых (главных) факторов (в нашем
данном случае у обучающей выборки будут наблю- случае — признаков). В классическом варианте
даться более лучшие показатели, чем у тестовой. Но факторный анализ учитывает только взаимную
за счет неучастия тестовой выборки в процессе корреляцию факторов, исключая те, которые в боль-
машинного обучения она дает более объективные шей степени коррелируют с другими. Для решения
показатели, на которые следует ориентироваться. нашей оптимизационной задачи необходимо учиты-
вать также корреляцию значений факторов со
Репрезентативность определяет соответствие
степенью близости пар и временные сложности
характеристик выборки генеральной совокупности.
алгоритмов вычисления признаков, так как они
В нашем случае под генеральной совокупностью
различны.
понимается множество изображений, доступных в
сети интернет (или в коллекции, по которой ведется Этап выделения ключевых признаков является
поиск). Проще говоря, если выборка репрезен- одним из самых важных и составляет ту соль,
тативна, то ее целесообразно использовать при которая делает ее, с одной стороны, аккумулятором
обучении нейронной сети, полагая, что обобщенные лучших предложений от специалистов по вычис-
численные показатели результатов обучения будут лению свойств изображений; с другой стороны,
схожи с результатами работы с генеральной отфильтровывает избыточные, трудоемкие и потому
совокупностью. ненужные алгоритмические решения вычисления
признаков изображения.
Сделать выборку более репрезентативной можно
путём увеличения ее объема, то есть с возвратом на Следует отметить, что с введением этого этапа в
первый этап и, соответственно, повторением после- метод, стремление оптимизировать полноту-
дующих этапов работы. точность дополняется оптимизацией временных
характеристик. Опишем математически данную
5 Выбор ключевых признаков задачу.
Пусть si,j – значение j-го признака, вычисленное
Очевидно, что можно использовать очень для i-й пары изображений, i=1,..,I; j=1,..,J;
большое число признаков для анализа пар
изображений на визуальное подобие. Но такая I – количество пар изображений;
численность является крайне нежелательной. Во- J – количество признаков;
первых, время работы результирующего алгоритма tj – среднее время вычисления j-го признака на
напрямую зависит от количества признаков, так как изображении;
в данном случае велико количество величин,
ai – степень близости изображений в паре i. С
которые требуется рассчитать. Во-вторых, большее
учетом использования двузначной шкалы
число признаков усложняет архитектуру нейронной
принимает значение 1, если изображения пары
сети, что приводит к увеличению требований к
являются тематически близкими и 0 в противном
ресурсам, задействованным в процессе машинного
случае.
обучения, и времени самого обучения. И, самое
главное, — это избыточность признаков из-за их Положим C(k,l) – коэффициент корреляции
взаимной корреляции и потенциальное наличие между последовательностями чисел k и l. Тогда
признаков, которые могут не влиять не результат. возможно построить корреляционную матрицу
Поэтому необходимо сокращение числа ,
признаков, но проводимое не вслепую в ущерб
качества результата, а с обеспечением наибольшего где sjx – последовательность значений s1,jx, s2,jx, …,
снижение трудоемкости их вычисления при sI,jx, и вектор
наименьшей потери точности результата обучения.
Поставленная задача является оптимизационной, и .
116
где a – последовательность значений a1,a2, …, aI. часть была отсеяна. Таким образом, к ключевым
То есть csk,l – корреляция между k-м и l-м признакам были отнесены следующие:
признаками, а caj – корреляция между j-м признаком Средние значения компонент R, G, B изображе-
и степенью подобия изображений в паре. ния в цветовой модели RGB;
Анализируя матрицу Cs, можно найти признаки, Медиана яркости;
которые имеют сильную статистическую взаимо-
Детализованность;
связь с другими. Эти признаки будем называть
избыточными. Анализируя вектор Ca, можно найти Признак симметрии изображения;
признаки, которые статистически никак не связаны Признак наличия текстур;
со степенью близости пары и, соответственно, не Пропорции сторон;
могут применяться для ее оценки. Эти признаки
будем называть бесполезными. Признаки, требую- Наличие лиц на изображении;
щие большое количество времени на их вычисление Нормированные 16-ти уровневые гистограммы
tj, будем называть трудоемкими. по компонентам Y (яркости), U, V
Чтобы оценить степень избыточности каждого изображения в цветовой модели YUV;
признака, определим вектор собственных значений Среднеквадратичное отклонение яркостей
матрицы Cs. В теории анализа данных эта уменьшенных копий (размером 32х32 пикселя)
процедура используется в факторном анализе, образца и рассматриваемого изображения.
являющимся разделом многомерного статистичес- В качестве набора исходных данных
кого анализа и позволяющего сократить размер- использовалась коллекция Flickr семинара
ность данных. Пусть X=(xj) — вектор собственных РОМИП [12]. В ней содержится 20000 фотографий
значений корреляционной матрицы. Значение xj разного качества и без единой темы; имеются
определяет степень статистической независимости j- фотоснимки людей, пейзажи, городские сцены и т.д.
го признака от других. В факторном анализе Фотографии сделаны при разном освещении, в
пороговой обработкой этой величины определяются помещениях, на улице и т.д. Из данной коллекции в
главные признаки. Авторами предлагается в обучающую выборку были отобраны 500 пар, среди
качестве подобной меры использовать выражение которых 125 являются тематически близкими, а 375
. нет. Тестовой выборкой являлось специальное
задание дорожки семинара РОМИП с результатами
В этой формуле агрегируются три важных работы группы асессоров.
показателя, которые необходимо учитывать при Для формирования выборок и обучения
отборе ключевых признаков: избыточность по нейронной сети применялся нейроимитатор
отношению к другим признакам, корреляция с Сигнейро [15], специализирующийся на задачах
результатом и время вычисления. Если ранжиро- обработки и анализа изображений. Была сконстру-
ванные значения hj отложить на графике, получаем ирована двухслойная нейронная сеть, структура
аналог графика “Каменистая осыпь” из теории которой приведена на рисунке 3. Количество входов
факторного анализа. Отметим, что он имеет сети соответствует количеству ключевых признаков,
подобный ему вид (рисунок 2). выход сети — один.
Типовой процедурой по критерию Кайзера или Для осуществления поиска изображений по
визуально на графике отсеиваются не ключевые визуальному подобию на основе полученной
признаки, оставляя те, которые будут исполь- нейронной сети была разработана программная
зоваться в дальнейшей работе. оболочка Axioma. В процессе поиска она извлекает
данные сигнатур (значения признаков) из
6 Результаты исследований поискового индекса, осуществляет вычисление
В проведенном исследовании мы остановились меры близости образца к изображениям коллекции и
на работе с 25 признаками, наиболее часто ранжирует результаты поиска.
используемыми в задачах анализа изображений. График полнота-точность полученного
В связи с тем, что поиск может осуществляться в нейросетевого алгоритма приведен на рисунке 4. На
больших коллекциях изображений, в качестве этом графике виден выступ, крайняя точка которого
признаков мы рассматривали только те, которые соответствует решению, полученному нейронной
можно просчитать для изображений заранее и сетью. Однако, более объективными можно считать
занести в некое подобие поискового индекса. По данные работы асессоров, отраженные на рисунке 5
этой причине, нами не рассматривались те призна- и представленные в сравнении с результатами
ки, которые необходимо рассчитывать по парам других исследователей (в рамках семинара РОМИП
изображений непосредственно при осуществлении в дорожке поиска изображений по визуальному
поиска. Из 25 признаков на этапе выбора главных подобию).
117
0,020
0,015
0,010
0,005
0,000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Рис. 2 Ранжирование признаков по значимости
Рис. 3. Структура нейронной сети
Полнота
(recall)
Точность
(precision)
Рис. 4. График полнота-точность
118
0,25
0,2 Точность(10) / Precision(10)
Bpref
0,15
Полнота / Recall
Средняя точность / Average
0,1 precision
Точность / Precision
0,05 R-точность / R-precision
0
Система 1 Система 2 Axioma
Рис. 5. Сравнение результатов участников дорожки поиска изображений по визуальному подобию семинара
РОМИП (оценки «vote weak»)
Анализируя их и в целом проведенную работу, [5] Quack T., Monich U., Thiele L., Manjunath B.S.
можно сделать следующие выводы: Cortina: A System for Largescale, Contentbased
1. Полученные качественные характеристики Web Image Retrieval // MM’04, October 1016,
построенного алгоритма соответствуют современ- 2004, New York, USA.
ному уровню достижений науки в данной области. [6] Smeulders A. W., Worring M., Santini S., Gupta
2. Вошедшая в оптимизационный критерий A., Jain R. Contentbased image retrieval at the end
временная характеристика позволила минимизиро- of the early years. IEEE Trans. Pattern Analysis
вать трудоемкость итогового алгоритма, который and Machine Intelligence, 22(12):1349-1380,
обладает линейным порядком временной слож- 2000.
ности. [7] Snoek C. G. M., Worring M. Multimodal video
indexing: A review of the state-of-the-art.
3. В дальнейшем, при увеличении объемов
Multimedia Tools and Applications, 25(1):5-35,
обучающей и тестовой выборок, качественный
показатель может быть улучшен и даже превзойден 2005.
значения аналогов, так как на данный момент [8] Tamura H., Mori S., Yamawaki T. Texture
имеются расхождения в показателях обучающей и features corresponding to visual perception //
тестовой выборок. IEEE Transactions on System, Man and
Cybernatic. 1978, volume 8(6), pp. 460–473.
Литература [9] Zhang D., Lu G. Content-Based Shape Retrieval
Using Different Shape Descriptors: A
[1] Aigrain P., Zhang H., Petkovic D. Content-based Comparative Study // In IEEE International
representation and retrieval of visual media: A Conference on Multimedia and Expo, 2001, pp.
review of the state-of-the-art. Multimedia Tools 289-293.
and Applications, 3(3):179-202, 1996.
[10] Васильева Н., Гладышева Ю. Взвешенный
[2] Datta R., Joshi D., Li J., Wang J. Image Retrieval: CombMNZ для комбинирования результатов
Ideas, Influences, and Trends of the New Age // поиска изображений по цветовым признакам //
ACM Computing Surveys, Vol. 40, No. 2, pp. 1- Российский семинар по Оценке Методов
60. Информационного Поиска. Труды РОМИП
[3] Manjunath B. S., Salembier P., Sikora T. 2010. (Казань, 15 октября 2010г.) - Казань,
Introduction to MPEG7: Multimedia Content 2010. С. 98-108.
Description Language. 1st edition, 2002. [11] Волосных Д.Ф Использование визуальных
[4] Mojsilović R., Kovačević J., Hu J., Safranek R. J., особенностей восприятия компонент цветовой
Ganapathy S. K. Matching and retrieval based on модели HSI при поиске изображений по
the vocabulary and grammar of color patterns // содержанию // Российский семинар по Оценке
IEEE Trans. Image Processing, 2000, volume 9, Методов Информационного Поиска. Труды
pp. 38-54.
119
РОМИП 2010. (Казань, 15 октября 2010г.) - изображений и дубликатов // Российский
Казань, 2010. С.154-163. семинар по Оценке Методов Информацион-
[12] Коллекция изображений Flickr. 2008. ного Поиска. Труды РОМИП 2010. (Казань, 15
http://romip.ru/ru/collections/flickr.html октября 2010г.) - Казань, 2010. С. 148-153.
[13] Мельниченко А., Гончаров А. ЛММИИ на
РОМИП-2009: Методы поиска изображений по
визуальному подобию и детекции нечетких Machine learning of visually similar images
дубликатов изображений c.108-121 search
[14] Пименов В.Ю. Простые методы поиска
изображений по содержанию // Российский Alexey Varlamov, Ruslan Sharapov
семинар по Оценке Методов Информацион- In this paper we consider the problem of image
ного Поиска. Труды РОМИП 2010. (Казань, 15 retrieval by visual similarity. We offer a method of
октября 2010г.) - Казань, 2010. С.69-79. developing the algorithm for determining similar visual
[15] Сигнейро. Нейронные сети в обработке и images based on machine learning. We analyze the key
анализе изображений. http://www.signneuro.ru features of images that can be used in the search. We
[16] Слесарев А.В., Мучник И.Б., Михалев Д.К., solve the problem of selecting features that are used for
Крайнов А.Г., Котляров Д.И., Беляев Д.В. machine learning search of visually similar images.
Яндекс на РОМИП 2010: Поиск похожих
120