Рассматриваются вопросы поиска изображений по визуальному образцу. Предлагается методика разработки алгоритма оценки визуальной близости пары изображений на основе машинного обучения. Анализируются признаки изображений, которые могут применяться в алгоритмах поиска. Решается проблема выбора из них ключевых.
Целью работы является рассмотрение вопросов построения системы поиска по визуальному образцу в относительно больших (десятки тысяч) коллекциях изображений. 2 Текущее состояние проблемы
Поиск изображений по визуальному образцу
является интереснейшей задачей, решению которой
посвящено множество работ. Достаточно подробные
обзоры приведены в [
Свойства оцениваются алгоритмами вычисления
значений важных численных величин и называются
признаками. Подобных признаков можно выделить
достаточно много. В общем случае они разделяются
на две группы: глобальные и локальные. К
глобальным признакам можно отнести основные
цвета, текстуры, формы, значимые элементы всего
изображения. Локальные признаки высчитываются
для небольших частей (блоков) изображения [
При поиске изображений по образцу анализируются не отдельные экземпляры, а пары изображений, которые сопоставляются друг другу. Поэтому в отличие от других задач анализа в текущей проблеме от признаков изображений переходят к признакам пар, значения которых находятся как абсолютные разности значений соответствующих признаков каждого из изображений пары. Такая несложная формула позволяет моментально их рассчитать для проиндексированных изображений и реализовать на практике поиск с приемлемыми временными характеристиками. 3 Существующие признаки изображений
Системы, осуществляющие поиск по визуальному образцу, активно используют различные признаки изображений. Эти признаки отличаются большим разнообразием.
Вопросы использования цветовых характеристик
обсуждаются в [
Работа [
В [
В работе [
Достаточно интересны работы, выполненные в рамках Российского семинара по оценке методов информационного поиска (РОМИП). Начиная с 2008 года на семинаре проводятся дорожки (секции, посвященные конкретным проектам) поиска изображений по образцу.
В работе [14] предложен алгоритм поиска изображений на основе нечетких цветовых гистограмм, вычисляемых в пространстве CIE L*a*b*. Предлагается кроме главной использовать набор дополнительных гистограмм, построенных для определенных участков изображения.
В работе [
В [16] используются уменьшенные копии изображений для поиска похожих снимков. В основу работы положен тот факт, что человеческое восприятие позволяет с хорошей точностью понимать содержание изображений с маленьким разрешением. Для цветных изображений человеку достаточно разрешения 32х32, чтобы достичь точности распознавания сцен превышающей 80%.
В работе [
В работе [
Таким образом, существует достаточно большое количество признаков, которые могли бы использоваться в задачах поиска изображений по визуальному образцу. Тем не менее, большинство работ включают лишь часть существующих признаков изображений, комбинируя их и разрабатывая на их основе сигнатуры. В связи с тем, что многие признаки могут быть взаимосвязаны между собой, важной задачей является их рациональный отбор. 4 Методика проведения исследования
Схематично предлагаемая методика работ для построения алгоритма определения визуального подобия изображений на основе машинного обучения показана на рисунке 1. Ее можно представить в виде следующих этапов, которые должны быть последовательно выполнены:
Этап 1. Из коллекции изображений формируется обучающая выборка. Она состоит из множества прецедентов, каждый из которых включает в себя пару изображений и степень их близости, оцененную экспертом.
Этап 2. Программно реализуются (при необходимости и разрабатываются) алгоритмы вычисления всевозможных признаков на изображениях.
Этап 3. Для каждой пары вычисляются значения всех признаков.
изображений Этап 4. Проводится факторный анализ признаков, в результате которого определяются главные признаки, значения которых будут использоваться в обучении нейронной сети и алгоритмы вычисления которых станут частью конечного алгоритма оценки визуального подобия изображений.
Этап 5. Обучается нейронная сеть. По завершению этого процесса запоминаются данные, характеризующие величины ошибок нейронной сети относительно входной выборки. Эти показатели преобразуются в полноту и точность — целевые значения оценки качества выполняемой работы. Отбор изображений Изображения Выбор признаков,
которые можно использовать для оценки тематической близости Формирование обучающей выборки Признаки Формирование тестовой выборки Экспертны е оценки
степени близости каждой пары Пары изображений Вычисление признаков
изображений Значения признаков Факторный анализ признаков и анализ временных характеристик
их вычисления Значения ключевых признаков Ключевые признаки Параметры
сети Обучение нейронной сети
Показатели качества оценки на обучающей
выборке Требование к расширению обучающей выборки Отбор изображений
Изображения Пары изображений Вычисление признаков изображений
Оценки асессоро в степени близости каждой
пары Значения ключевых признаков Прогон нейронной сети Показатели качества оценки на тестовой выборке Сопоставление результатов. Вывод о репрезентативности
обучающей выборки Рис. 1 Методика проведения работ для построения алгоритма определения визуального подобия изображений на основе машинного обучения Этап 6. Из коллекции изображений формируется тестовая выборка. Ее структура и характеристики (объем, соотношение близких и неблизких пар) должны соответствовать структуре и характеристикам обучающей выборки.
Этап 7. Вычисляются значения ключевых признаков всех изображений, входящих в тестовую выборку.
Этап 8. Прогоняется нейронная сеть на тестовой выборке с определением полноты и точности.
Этап 9. Сравниваются полнота и точность анализа нейронной сетью изображений обучающей выборки с полнотой и точностью анализа нейронной сетью изображений тестовой выборки. При приблизительно одинаковых значениях соответствующих показателей работа считается завершенной.
По завершению пятого этапа, на котором выполняется машинное обучение, может быть уже достигнута цель — получены все данные для их сборки в алгоритм определения подобия пары произвольных изображений. На дальнейших этапах проводится анализ полученного результата и, при необходимости, принимается решение о возврате на предыдущие этапы работы. По завершении всего цикла становятся известными основные численные характеристики, отражающие качество полученного алгоритма: полнота и точность.
Применительно к решаемой задаче полнота (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, и вектор где a – последовательность значений a1,a2, …, aI.
То есть csk,l – корреляция между k-м и l-м признаками, а caj – корреляция между j-м признаком и степенью подобия изображений в паре.
Анализируя матрицу Cs, можно найти признаки, которые имеют сильную статистическую взаимосвязь с другими. Эти признаки будем называть избыточными. Анализируя вектор Ca, можно найти признаки, которые статистически никак не связаны со степенью близости пары и, соответственно, не могут применяться для ее оценки. Эти признаки будем называть бесполезными. Признаки, требующие большое количество времени на их вычисление tj, будем называть трудоемкими.
Чтобы оценить степень избыточности каждого признака, определим вектор собственных значений матрицы Cs. В теории анализа данных эта процедура используется в факторном анализе, являющимся разделом многомерного статистического анализа и позволяющего сократить размерность данных. Пусть X=(xj) — вектор собственных значений корреляционной матрицы. Значение xj определяет степень статистической независимости jго признака от других. В факторном анализе пороговой обработкой этой величины определяются главные признаки. Авторами предлагается в качестве подобной меры использовать выражение
.
В этой формуле агрегируются три важных показателя, которые необходимо учитывать при отборе ключевых признаков: избыточность по отношению к другим признакам, корреляция с результатом и время вычисления. Если ранжированные значения hj отложить на графике, получаем аналог графика “Каменистая осыпь” из теории факторного анализа. Отметим, что он имеет подобный ему вид (рисунок 2).
Типовой процедурой по критерию Кайзера или визуально на графике отсеиваются не ключевые признаки, оставляя те, которые будут использоваться в дальнейшей работе. 6 Результаты исследований
В проведенном исследовании мы остановились на работе с 25 признаками, наиболее часто используемыми в задачах анализа изображений.
В связи с тем, что поиск может осуществляться в больших коллекциях изображений, в качестве признаков мы рассматривали только те, которые можно просчитать для изображений заранее и занести в некое подобие поискового индекса. По этой причине, нами не рассматривались те признаки, которые необходимо рассчитывать по парам изображений непосредственно при осуществлении поиска. Из 25 признаков на этапе выбора главных часть была отсеяна. Таким образом, к ключевым признакам были отнесены следующие: Средние значения компонент R, G, B изображения в цветовой модели RGB; Медиана яркости; Детализованность; Признак симметрии изображения; Признак наличия текстур; Пропорции сторон; Наличие лиц на изображении; Нормированные 16-ти уровневые гистограммы по компонентам Y (яркости), U, V изображения в цветовой модели YUV; Среднеквадратичное отклонение яркостей уменьшенных копий (размером 32х32 пикселя) образца и рассматриваемого изображения.
В качестве набора исходных данных
использовалась коллекция Flickr семинара
РОМИП [
Для формирования выборок и обучения
нейронной сети применялся нейроимитатор
Сигнейро [
Для осуществления поиска изображений по визуальному подобию на основе полученной нейронной сети была разработана программная оболочка Axioma. В процессе поиска она извлекает данные сигнатур (значения признаков) из поискового индекса, осуществляет вычисление меры близости образца к изображениям коллекции и ранжирует результаты поиска.
График полнота-точность полученного нейросетевого алгоритма приведен на рисунке 4. На этом графике виден выступ, крайняя точка которого соответствует решению, полученному нейронной сетью. Однако, более объективными можно считать данные работы асессоров, отраженные на рисунке 5 и представленные в сравнении с результатами других исследователей (в рамках семинара РОМИП в дорожке поиска изображений по визуальному подобию). 0,010 0,005 0,000 Полнота (recall) Рис. 3. Структура нейронной сети Рис. 4. График полнота-точность Точность (precision) 0,25 0,2 0,15 0,1 0,05 0 Точность(10) / Precision(10)
Полнота / Recall Средняя точность / Average precision Точность / Precision
Система 1 Система 2
Axioma
2. Вошедшая в оптимизационный критерий временная характеристика позволила минимизировать трудоемкость итогового алгоритма, который обладает линейным порядком временной сложности.
3. В дальнейшем, при увеличении объемов обучающей и тестовой выборок, качественный показатель может быть улучшен и даже превзойден значения аналогов, так как на данный момент имеются расхождения в показателях обучающей и тестовой выборок. Литература Machine learning of visually similar images search
In this paper we consider the problem of image retrieval by visual similarity. We offer a method of developing the algorithm for determining similar visual images based on machine learning. We analyze the key features of images that can be used in the search. We solve the problem of selecting features that are used for machine learning search of visually similar images.