на тему: Основе любой системы распознавания изображений лежат, главным образом, два алгоритма: алгоритм

Введение

В основе любой системы распознавания изображений лежат, главным образом, два алгоритма: алгоритм формирования дескриптора (индекса) изображения (т.е. организованной совокупности признаков изображения) и алгоритм оценки степени сходства двух изображений по их дескрипторам [1].

Существующие методы распознавания поиска изображений в визуальных базах данных узко специализированы и используют, как правило, различные эвристические методы, соответствующие специфике практического применения [2,3]. В большинстве случаев для индексирования изображений используют цветовые характеристики изображений, в частности цветовые гистограммы, форму объектов и некоторые другие признаки [3,4]. Однако такого рода признаки становятся малоэффективными, если искомое и эталонное изображение достаточно сильно отличаются из-за помех, изменения масштаба, кадрирования или изменения яркости. В этой связи встает задача создания эффективных алгоритмов индексирования цветных (полутоновых) изображений и алгоритмов сравнения эталонных и предъявляемых изображений.

Поиск изображений в современных системах осуществляется на основе "сигнатур" или индексов изображений, которые формируются путем вычисления низкоуровневых характеристик изображений, в качестве которых обычно выступают цветовые, текстурные, и геометрические признаки.

За последние годы объем мультимедиаданных вырос в несколько раз. Все больше людей используют поиск изображений в сети Интернет для оформления своих презентаций, публикаций и просто для удовлетворения любопытства. При этом классифицированной является лишь незначительная часть этих изображений (в основном, это касается коммерческих баз данных).

1. Теоретическая часть

1.1. Алгоритм формирования дескриптора изображения

Предположим что имеется коллекция (произвольного объема) растровых неповторяющихся изображений произвольной тематики. Иными словами, имеется база данных изображений-эталонов. Каждое изображение может иметь произвольное пространственное разрешение (желательно не ниже 100x100 пикселей) и произвольную глубину цвета/битность (желательно не ниже 8 бит/пиксель). Каждое изображение коллекции может быть как цветным, так и не цветным. Изображения не содержат никакой сопутствующей информации (никаких ключевых слов, фраз на естественном языке или каких-либо иных метаданных). На изображения не нанесены водяные знаки. Каждое изображение базы формирует отдельный класс и является единственным представителем данного класса. Необходимо создать систему, на вход которой подается удовлетворяющее вышеприведенным ограничениям изображение, которое может, как принадлежать, так и не принадлежать коллекции. Подающееся на вход системы изображение из коллекции может быть искажено одним или несколькими следующими факторами:

- групповые помехи произвольной формы и размера,

- поворот,

- изменение масштаба,

- нелинейное изменение яркости,

- изменение разрешения,

- сдвиг,

- кадрирование/ декадрирование,

- зеркальное отображение.

Примеры некоторых из перечисленных искажений показаны на Рис. 1.

Рис.1. Примеры изображений-эталонов (левый столбец) и их искаженных версий (правый столбец). Соответствующие искажающие факторы (сверху-вниз): нелинейное изменение яркости, групповые помехи, кадрирование, сдвиг, изменение масштаба, декадрирование.

Система должна правильно классифицировать входное изображение, т.е., либо отнести его к одному из классов (естественно, верному) (результат работы - представитель этого класса), либо резюмировать, что входное изображение не принадлежит ни к одному классу.

Вследствие наличия искажающих факторов необходимо разрабатывать такие признаки изображения, каждый из которых будет малочувствителен хотя бы к одному из рассматриваемых факторов. По этой же причине разрабатываемые признаки изображения должны, по крайней мере, слабо корелировать, а лучше, если они будут иметь слабую статистическую взаимосвязь. Силу корреляционной взаимосвязи можно оценить посредством выборочной оценки коэффициента корреляции Пирсона [5]. Силу статистической взаимосвязи можно оценить посредством величины средней взаимной информации [6]. Соответственно, дескриптор изображения в нашем случае - это просто вектор признаков.

Разработанный дескриптор изображения состоит из трех групп признаков. Первая группа признаков получается следующим образом. Исходное изображение преобразуется в полутоновое, если изначально таковым не являлось. Далее, используя метод выделения локальных двоичных микроструктур (метод LBP), полученное полутоновое изображение приводится к LBP-изображению, т.е. к такому изображению, в котором яркость каждого пикселя суть LBP-код (Рис. 2).

Рис.2. Исходное 24-битное изображение (слева) и соответствующее ему 8-битное LBP-изображение (справа.)

Суть метода LBР заключается в следующем [7] (Рис. 3). Вокруг каждого пикселя изображения (gс) описывается окружность радиуса R (в нашем случае R=1). Далее определяются яркости (I) Р точек (у нас Р=8), равномерно распределенных по окружности. Если точка совпадает с пикселем изображения (точки g0, g2, g4 и g6), то яркость этой точки есть яркость пикселя. В противном случае (точки g1, g3, g5 и g7) яркость точки получают посредством интерполяции по 4 соседям. Выбрав одну из Р точек в качестве начальной (g0) и задав направление обхода (оба действия выполняются всегда единообразно), вычисляется величина, называемая LBP-кодом:

Рис. 3. Иллюстрация процесса получения LBP-кода для пикселя gс. Узлы сетки соответствуют пикселям изображения.

Предположим, что в качестве дескриптора исходного изображения выступает нормированная гистограмма соответствующего ему LBP-изображения, т.е. вектор размерности 256x1, каждый элемент которого есть частота появления соответствующего LBP-кода на LBP-изображении. Однако такой дескриптор не будет эффективным при решении поставленной задачипо крайней мере, из-за двух причин.

Первая причина состоит в слишком большой размерности пространства признаков. Пусть некоторому пикселю gi изображения поставлен в соответствие LBP-код LBP(gi) = 31. Повернув изображение на 900 против часовой стрелки, получим LBP(gi) = 124, а на 900 по часовой стрелке - LBP(gi) = 199. Получить устойчивость (но не инвариантность) к повороту изображения можно, если сгруппировать LBP-коды и вычислять не частоты появления отдельных LBP-кодов, а суммы частот появления LBP-кодов каждой группы. Для приведенного примера группа будет следующей: {31, 62, 124, 143, 199, 227, 241, 248}. Таким образом, 256 признаков исходного изображения "сжимаются" до 36. Однако и такой дескриптор изображения недостаточно эффективен вследствие второй причины, которая сводится к учету редко появляющихся LBR-кодов. Продемонстрируем это на следующем примере. Сформируем объемную (V = 40000 изображений) коллекцию растровых неповторяющихся изображений, применив к каждому из них метод LBP, и, построив в итоге совокупную нормированную гистограмму LBP-кодов (Рис. 4), мы увидим, что большинство LBP-кодов появляются достаточно редко. Необходимо объединить все "редкие" коды в одну группу, что ведет к "сжатию" 36 признаков исходного изображения до16. Итак, пока мы характеризуем исходное изображение 16 признаками - это предварительная

Рис.4. Совокупная нормированная гистограмма LBP-кодов

первая группа искомых признаков. Также формируются предварительные вторая и третья группы искомых признаков (о них - далее). Окончательные группы искомых признаков получаются следующим образом. Пусть исходное изображение характеризуется N = N1 + N2 + N3 признаками. Вычислив для каждого изображения вышеупомянутой коллекции (V = 40000) эти N признаков, получим матрицу объект-признак [8] размером 40000xN. Выбрав любые два столбца этой матрицы, и, воспользовавшись выборочным коэффициентом корреляции, можно оценить силу корреляционной взаимосвязи между соответствующими признаками. Если вместо выборочного коэффициента корреляции использовать среднюю взаимную информацию, то можно оценить силу статистической взаимосвязи между данными признаками. Построим две матрицы признак-признак размерами NxN. Каждый элемент первой матрицы - величина средней взаимной информации для соответствующих признаков. Каждый элемент второй матрицы - величина выборочного коэффициента корреляции для соответствующих признаков (т.н. корреляционная матрица). Совместный анализ обеих матриц определяет размерность и состав дескриптора исходного изображения (N' = N'1 + N'2 + N'3, N' < N). Предварительные вторая и третья группы искомых признаков получаются посредством дальнейшей обработки LBP-изображения (Рис. 2). При этом используется концепция линейно-симметрического изображения [9], введенная Джозефом Бигуном. На Рис. 5 приведены примеры линейно-симметрических (л-с) изображений. Упрощенно можно определить л-с изображение, как "полосатое", т.е. каждое такое изображение выглядит, как группа параллельных друг другу "прямых" полос в общем случае различных ширин и яркостей. Яркость в пределах полосы неизменна. Количество полос произвольно. Единичный вектор перпендикулярный всем полосам л-с изображения задает направление линейной симметрии этого изображения. Невырожденное л-с изображение имеет два и только два (противоположных друг другу) направления линейной симметрии.

Рис.5. (Верхняя строка) Два линейно-симметрических изображения (искусственные) (слева и в центре) и одно почти линейно-симметрическое изображение (реальное) (справа); Зеленые вектора задают направления линейной симметрии изображений. (Нижняя строка) - Амплитудные спектры приведенных изображений.

Л-с изображения обладают следующим замечательным свойством. Если и только если изображение является линейно-симметрическим, его Фурье-спектр (а также амплитудный и энергетический спектры) сконцентрирован в прямую линию, проходящую через начало координат (т.н. центральную прямую) и задающую направления линейной симметрии этого изображения. Можно получить два интересных признака изображения, аппроксимировав его л-с изображением. Процесс аппроксимации произвольного изображения л-с изображением эквивалентен процессу аппроксимации Фурье-спектра (или амплитудного спектра, или энергетического спектра) этого изображения центральной прямой. Задача аппроксимации - поиск такой ориентации центральной прямой, при которой ошибка аппроксимации будет минимальной (мы определяем ошибку посредством метода ортогональной регрессии [10]). Ориентация оптимальной (дающей наименьшую ошибку) центральной прямой (угол α) и обеспечиваемый ею показатель качества аппроксимации (С) есть искомые (интересные) признаки изображения.

Каждый пиксель LBP-изображения рассматривается вместе со своей окрестностью, как отдельное (маленькое) изображение, для которого вычисляются признаки α и С. Нормированные гистограммы признаков α и С анализируются подобно тому, как было рассмотрено ранее, и "сжимаются" в предварительные вторую и третью группы искомых признаков.

Степень сходства ρ изображений Im1 и Im2, характеризуемых векторами признаков D1 и D2 размерностью N', вычисляется следующим образом.

Здесь Δ - вектор допусков, определяемых экспериментально.

1.2. Методы поиска изображения на основе гистограмм в задачах обработки изображений

Экспериментальные исследования показали, что методы на основе сравнения гистограмм неустойчивы к сильным изменениям освещения сцены. Дополнительные сложности создаёт наличие световых бликов на изображении. Кроме того, разные камеры и фотоаппараты обладают разной цветопередачей, поэтому один и тот же цвет может выглядеть по-разному на изображениях с разных устройств.

Ряд методов был предложен для устранения этих недостатков.

EMD(Earth Mover's Distance) [11]. При изменениях освещенности сцены или интенсивности цветов координаты ячеек гистограммы для одинаковых цветов могут сдвигаться друг относительно друга. В таком случае простое сравнение гистограмм приведёт к некорректным результатам. Для преодоления подобных проблем был разработан алгоритм сравнения гистограмм Earth Mover's Distance. В данном методе гистограмма (или любое другое вероятностное распределение) представляется в виде набора кластеров {sj = (mj, wj)}. Кластер задаётся средним цветом mj и дисперсией wj. Подобное представление называется сигнатурой распределения. Для определения расстояния между распределениями решается транспортная задача. Для каждой пары кластеров из разных распределений вычисляется стоимость их совмещения, которая зависит от расстояния между кластерами (кластера, соответствующие похожим цветам, будут иметь низкую стоимость совмещения). Требуется найти такое сопоставление пар кластеров, при котором сумма стоимостей совмещения будет минимальна.

Color constant color indexing [12]. Данный метод был создан для повышения инвариантности методов на основе сравнения гистограмм к изменениям освещённости. Для каждого пикселя вычисляется Лапласиан Гауссиана в окрестности 3 на 3, берутся 4 частные производные по направлениям, каждой из комбинаций значений частных производных соответствует своя ячейка гистограммы. Данный алгоритм более устойчив к изменениям освещения и формы объектов на изображении.

Joint histograms [13]. Наряду с цветом используется набор локальных признаков для построения многомерной гистограммы. Каждая ячейка гистограммы содержит число пикселей изображения, описываемых соответствующим набором признаков. В качестве признаков могут использоваться цвет, плотность границ, магнитуда градиента, текстурированность (число пикселей в окрестности, яркость которых отличается от яркости данного пикселя больше, чем на определённую величину) и другие. Преимущество данного подхода состоит в том, что используется е только информация о цветах, но и другая важная информация.

Histogrambackprojection. Метод для поиска заданного объекта Т на изображении Ir. На этапе инициализации строится нормализованная цветовая гистограмма Н по изображению It искомого объекта Т. На этапе распознавания для каждого пикселя р изображения Ir, на котором мы пытаемся найти интересующий нас объект Т, определяется ячейка i гистограммы, соответствующая цвету данного пикселя. Затем значение цвета пикселяр исследуемого изображения Irзаменяется на значение Нi, содержащееся в найденной ячейке гистограммы i. После обработки всех пикселей изображения Irдля поиска заданного объекта Т можно воспользоваться алгоритмом кластеризации (например, CamShift), или обнулить те значения пикселей обработанного изображения Ir, которые меньше заданного порога, и затем найти максимальную компоненту связности на полученном изображении. Найденный максимум соответствует наиболее вероятной позиции искомого объекта Т на изображении Ir. Также известна версия данного алгоритма под названием patch-based backprojection, в которой с гистограммой искомого объекта сравнивается не отдельный пиксель, а окрестность пикселя в виде прямоугольника (используется метод "скользящего окна").

1.3. Алгоритм поиска изображений на основе гистограмм

С целью поиска всех копий изображения были выбраны методы позволяющие выполнить хеширование исходного изображения с последующим сравнением полученного хэша, с хэшами других изображений. Однако поскольку, похожие друг на друга изображения могут несколько отличатся в первую очередь по цветовой гамме, а также по ряду других показателей, то применение для этих целей таких средства как преобразование хэшириющими алгоритмами типа md5 и им подобным будет не эффективно. Это очевидно, так как похожие "на глаз" изображения, но отличающиеся по своим показателям, будут давать разные хеши и, следовательно, система будет обладать низкой обобщающей способностью. Необходим алгоритм построения хеша обладающего более высокой обобщающей способностью.

Данная работа посвящена алгоритм поиска всех копий картинки по ее содержанию основанный на гистограммных хешах.

Рассмотрим более детально алгоритм поиска всех копий картинки по ее содержанию основанный на гистограммах. В общем виде алгоритм сводится, во-первых, к построению гистограмм распределения цветов по осям x и у по каждой из r, g и b компонент в пространстве цветов RGB. Покажем, что такой метод может быть не чувствителен к изменению масштаба исходного изображения в широком диапазоне значений (от 2 до 64 раз), а также к повороту исходного изображения на определённый угол и зашумлению как случайным RGB шумом, так и посторонними изображениями (белыми и черными линиями).

Рассмотрим суть гистограмм используемых в алгоритме. По сути гистограммы являются нормированными (приведенными к единичному масштабу) функциями, распределения цветов по осям x и у по каждой из r, g и b компонент в пространстве цветов RGB. Рассмотри вид таких функций представленных на рис. 7 для тестового изображения на рис. 6.

Рис. 6. Тестовое изображение для демонстрации сути гистограмм алгоритма.

Рис. 7. Гистограммы, используемые в алгоритме полученные по тестовому изображению на рис.6.

Рассмотрим более детально графики гистограмм представленных на рис. 7. В левой части изображения на рис.2 представлены три графика функции распределения по каждой из r, g и b компонент в пространстве цветов RGB по оси x [14]. Масштаб по оси x для этих графиков полностью соответствует масштабу по оси x для изображения на рис.6. Рассмотрим, к примеру, график функции распределения для r компоненты по оси x исходного изображения на рис.6. Значения этого графика y(x(i)) показывает общую сумму всех значений r компоненты (r є [0...255]) по всей оси y исходного изображения в позиции x(i) для шкалы x исходного изображения.

Аналогично определяются графики для компонент g и b по оси x

В правой части изображения на рис.7 также представлены три графика функции распределения по каждой из r, g и b компонент в пространстве цветов RGB, но по оси y изображения. Физический смысл графиков аналогичен тем, которые описаны выше. Разница состоит лишь в том, что они рассчитаны для оси y, а не x.

Аналогично определяются графики для компонент g и b по оси y.

После расчета гистограмм их значения нормируются - то есть приводятся к единичному масштабу путем деления на максимальный элемент для каждой гистограммы.

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

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

После получения всех необходимых гистограмм исходного изображения, начинается этап их сравнения с гистограммами изображений среди которых могут находится копии исходного изображения. Сравнение происходит по всем функциям распределения r, g, и b компонент для x и y шкал. Лишь при совпадении всех шести функций распределения в каждой паре. Под парой подразумеваются две группа гистограмм. Первая группа состоит из 3-х гистограмм для x шкалы исходного изображения и 3-х гистограмм для x шкалы проверяемого изображения. В свою очередь, вторая группа состоит из 3-х гистограмм. Такой подход выбран для увеличения "помехозащищенности" по отношению к изображениям заведомо не похожим на исходное. Поскольку вероятность одновременного случайного совпадения гистограмм по всем компонентам r, g, и b на всех гистограммах у двух разных изображений значительно ниже чем, к примеру, вероятность одновременного случайного совпадения гистограмм по одной компоненте (либо по суммарной яркости).

Помимо прямого соответствия всех шести функций распределения ищется также соответствие между тремя функциями распределения по оси x

входного изображения и тремя "зеркальными" функциями по оси x и оси y сравниваемого изображения. Аналогично ищется также соответствие между тремя функциями распределения по оси y входного изображения и тремя "зеркальными" функциями по оси y и оси x сравниваемого изображения. Под "зеркальными" функциями подразумеваются исходные функции распределения, но симметричные относительно оси y. Операция сравнения гистограмм исходного изображения с "зеркальными" гистограммами сравниваемого изображения проводится для обеспечения инвариантности к поворотам на 90 и 180 градусов. В этом и заключается суть алгоритма или алгоритма поиска изображений на основе гистограмм.

В процессе тестирования алгоритма было показано, что он не чувствителен к изменению масштаба исходного изображения в широком диапазоне значений (от 2 до 64 раз), линейному искажению размеров исходного изображения в широком диапазоне, а так же к поворотам на углы 90 и 180 градусов как это показано на рис.8

Рис. 8. Изображения, подаваемые на вход алгоритма для проверки инвариантности к углам поворота на 90 и 180 градусам.

Также наблюдалась инвариантность к шумовым искажениям. Пример шумового искажения используемого для тестирования представлен на рис. 9б.

Рис.9. Изображение, подаваемое на вход алгоритма.

Изображение представленное на рис.9б было получено из изображения на рис.9а путем его зашумления случайно расположенными кривыми черного и белого цветов с последующим зашумлением "шумом RGB" и применением последовательно двух фильтра Гаусса с σ = 5 и σ = 10. После чего полученный результат повторно зашумлен "шумом RGB".

На рис. 10. представлены графики функций распределения исходного изображения рис.9а для осей х и у (два верхних графика). Графики функций распределения скаженного изображения рис.9б изображения подаваемого на вход данного алгоритма (два графика посередине) и графики разности между гистограммой исходного и уменьшенного изображений (два нижних графика). Последние два графика получены путем простого вычитания значения каждого элемента в гистограмме исходного изображения от соответствующего значения в гистограмме уменьшенного изображения.

Рис. 10. Гистограммы, полученные по изображению на рис.9.

Алгоритм хорошо зарекомендовал себя при работе с цветными изображениями, в которых нет явного преобладания одного из цветов или оттенков. В случае более монотонных изображений качество опознавания может быть ниже. Рассмотрим изображение представленное на рис.11а

Это пример монотонного изображения с преобладанием серого (или серебристого) цветов. Для этого изображения алгоритм нашел "похожие" результаты из базы данных представленные рис.11б

Рис. 11. Результат работа алгоритма на монотонных изображениях.

При этом стоит отметить, что неверный результат не обладал постоянством в том смысле, что при подаче на вход алгоритма исходного изображения (рис.11а) подвергнутого шумовым искажениям неверный результат (рис.11б) исчезал при одних параметрах шума, вновь возникая при других.

1.4. Рассмотрение аналогов разрабатываемой системы

В современном Интернете существует несколько способов поиска изображений.

Первый - универсальный поиск по косвенным признакам. Он в общем-то незначительно отличается от поиска веб-страниц, поскольку анализируются различные элементы: имена файлов, теги HTML-разметки, ссылки, подписи и тексты, находящиеся рядом с картинкой на веб-странице. Такой способ позволяет использовать накопленные индексные базы и обеспечивает широкий охват ресурсов. Поисковый запрос состоит из вводимых пользователем ключевых слов. Сравнительно ограниченные дополнительные возможности позволяют фильтровать изображения по размеру, цветности и другим подобным признакам. В то же время при таком поиске неизбежен значительный процент ошибок и информационного шума.

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

Третья основная технология индексирования и поиска изображений связана с попытками автоматического распознавания картинок. Общее ее наименование - контентный поиск изображений (Content Based Image Retrieval, CBIR). В ходе индексирования графики CBIR-система работает не с косвенными текстовыми признаками, о которых упоминалось выше, а непосредственно с характеристиками изображения. Индексируются цветовая гамма картинки и текстуры, распознаются и записываются очертания предметов и их расположение в кадре. Полученные данные используются для формирования запроса или же для сравнения картинок, чтобы выявить визуально похожие изображения.

Преимущество CBIR-поисковиков состоит в том, что автоматизированный процесс индексирования затрагивает визуальные характеристики изображения. Кроме того, данная технология предлагает пользователям оригинальные средства составления поисковых запросов. В то же время CBIR - не панацея, она имеет свои ограничения. Как следствие, лучшие CBIR-поисковики обычно предлагают комбинированные инструменты, объединяющие возможности нескольких технологий индексирования.

Заметим, что визуальные контентные алгоритмы уже давно работают в системах интернет-поиска в составе "семейных фильтров", однако в последнее время появилось несколько поисковиков, сделавших CBIR-технологии основным средством индексирования и составления запросов. Это привело к интересным результатам. Более того, стиль работы с подобными сервисами существенно отличается от привычного поиска картинок по ключевым словам. Именно такие поисковики, сгруппированные по способам составления запроса, и стали героями нашего обзора.

Финский поисковик Tiltomo - независимый экспериментальный проект, использующий в своей работе базу Flickr, точнее две тестовые выборки из этой базы, имеющие общий объем в несколько сотен тысяч фотографий. Первая представляет собой выборку снимков, загруженных на Flickr за последние сутки, вторая - фото из группы Catchy Colors. Именно в этой базе лучше всего работают инструменты анализа изображений. Переключаться между базами можно перед началом поиска.

Просмотр начинается либо с предлагаемого случайного набора снимков, либо с поиска по ключевому слову-тегу. Далее к полю ввода запроса можно не обращаться - Tiltomo работает как каталог, производя по требованию пользователя дополнительную фильтрацию выводимых фото. Все контентные инструменты фильтрации и сортировки собраны на странице выдачи. На ней выводятся три десятка снимков, соответствующих первоначальному запросу. Дальнейшее уточнение запроса происходит не привычным добавлением дополнительных ключевых слов к нему, а с помощью визуальных инструментов. Рядом с каждой миниатюрой появляются две ссылки: Find Similar by Theme ("Найти похожие по тематике") и Find Similar by Color/Texture ("Найти похожие по цвету и текстуре").

Первая из них проводит поиск по ключевым словам, которыми помечено выбранное изображение. Этот способ хорош для быстрой обработки синонимов, поскольку позволяет оставить в выдаче только тематические изображения. Вторая ссылка запускает собственно контентный анализ картинки. В результате будут получены визуально похожие на нее изображения. Цикл можно повторять, выбирая в выдаче понравившиеся картинки. К сожалению, эти два режима работают независимо друг от друга. Так что не удастся, например, сначала ограничить выдачу определенной темой и потом подобрать в ней изображения со схожим внешним видом - переключение к контентному анализу сбивает тематический фильтр, что не очень удобно.

Третий способ сортировки найденного - фильтр Show ONLY images from the reference photographer. Он переключает Tiltomo в режим поиска снимков конкретного автора. Здесь каких-либо инноваций нет, все работает в привычном по другим поисковикам стиле.

Разработчики ALIPR имеют богатый опыт работы с системами распознавания изображений. Именно они в свое время были авторами проекта WIRE, применявшегося для построения первых "семейных" веб-фильтров, и поисковика картинок SIMPLIcity. Система ALIPR, запущенная в 2006 г., является некоммерческим проектом. Пока доступен только обычный интерактивный пользовательский интерфейс, однако разработчики обещают выпустить готовый API для автоматического взаимодействия, как только это позволит сделать техническая база проекта.

Идея ALIPR заметно отличается от заложенных в других подобных проектах. Дело в том, что запросы здесь составляются обычным образом, с помощью ключевых слов. Однако индексная база этих ключевых слов формируется с применением технологии автоматического тегирования. Получив на входе фотоснимок, система проводит распознавание изображенных на нем предметов. Затем на основе проведенного анализа изображение автоматически помечается тематическими тегами, соответствующими объектам на снимке.

В качестве начального запроса используются только изображения. Картинку можно загрузить со своего компьютера. Если же она находится на веб-сайте, достаточно указать ее URL. На странице выдачи для каждой миниатюры предлагаются кнопки Related и Similar, работающие в качестве фильтров. Их действие аналогично рассмотренным выше инструментам Tiltomo. Кроме того, осуществляется поиск по автоматически присвоенным тегам.

Интересно, что доступны фильтры, относящиеся к эмоциональным оценкам, содержащимся в тегах. Соответствующие теги можно самостоятельно присвоить понравившейся фотографии. За удачные изображения предлагается проголосовать, и затем эти сведения будут учтены в работе системы. Как только вы отдадите свой голос за то или иное изображение, система выведет общий список присвоенных ему тегов, что позволяет быстрее и точнее найти похожие снимки. Благодаря работе всех названных инструментов качество подбора похожих изображений у ALIPR выше, чем у Tiltomo.

Кстати, предлагаемые технологии применяются не только на самом сайте ALIPR, но и на нескольких крупных веб-проектах. Их, в частности, используют фотопорталы Airliners.net и Terragaleria.com

Израильская компания Picitup предлагает сразу несколько онлайновых продуктов, как коммерческих, так и общедоступных. Среди последних в контексте нашего обзора наибольший интерес представляют ресурсы Picitup Visual Image Search и Picitup Celebrity Matchup, которые мы и рассмотрим.

Визуальный поиск работает с базами внешних сервисов - Yahoo!, Flickr и Picasa. К сожалению, вести метапоиск сразу по всем названным сервисам с помощью Picitup нельзя - можно только переключаться между результатами, полученными из различных источников. Соответствующая опция-переключатель доступна в интерфейсе поисковика. Количество результатов, выдаваемых Picitup за один поиск, ограничено пятью сотнями.

Поиск начинается обычным способом - вводом ключевых слов. Визуальные фильтры, скомпонованные на небольшой боковой панели, становятся доступны уже на странице выдачи результатов. Первая группа переключателей позволяет работать с сюжетами снимков. На основе анализа контента система может показать только портреты, общие планы или пейзажи. Следующий инструмент - выбор основной цветовой гаммы изображения с помощью предлагаемой палитры. Отдельный фильтр отвечает за формат (обычный или для широких экранов) и ориентацию изображения (книжная или альбомная). Кроме того, предлагается палитра простейших геометрических фигур, дающих возможность в определенной степени описать композиционные особенности нужных изображений. Названные инструменты позволяют задавать относительно точные параметры картинки, однако имеется и более простое средство - кнопка Similar Images, выводящаяся рядом с каждой миниатюрой. В этом случае система попытается самостоятельно определить необходимые параметры и подобрать похожие картинки.

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

Собственные технологии поиска похожих изображений демонстрирует сервис Xcavator. Этот поисковик ориентирован на профессиональное применение, поскольку ищет не по общедоступным источникам, а по нескольким крупным фотобанкам, в том числе по Fotolia и iStockphoto.

Приемы работы с Xcavator во многом подобны стилю работы с уже рассмотренными выше машинами. Поиск начинается вводом ключевого слова. Дальнейшее уточнение запроса можно вести с помощью CBIR-инструментов. Первый способ - простой щелчок на наиболее понравившемся снимке. После него страница выдачи перестраивается, и на нее попадают только те изображения, что визуально похожи на отобранное. Второй визуальный инструмент под названием Traces действует в окне активной миниатюры. Прямо на ней с помощью мыши можно сделать набросок нужной картинки. Правда, данная система работает лишь с точками и простыми линиями. Зато в ней присутствует расширенный поиск, позволяющий точно задать цветовую гамму изображения. В качестве вспомогательного инструмента выступает подробный текстовый перечень тегов, которыми помечена активная картинка. Он приводится под текстовой строкой поиска. Найденные изображения можно отобрать в мини-галерею. Работа с Xcavator заканчивается перенаправлением на сайты агентств, которым принадлежат права на выбранные снимки.

Австрийский проект Retrievr работает в двух режимах. Первый - уже знакомый нам поиск на сравнение (Search by Image). Пользователю предлагается загрузить фото или указать его адрес в Интернете, после чего Retrievr ведет поиск по собственной выборке из базы фотохостинга Flickr.

Второй режим, называемый Search by Sketch, гораздо интереснее. Он позволяет пользователю самостоятельно сделать эскиз нужного ему изображения. Для этого предлагается простой графический редактор, выполненный на базе технологии Flash. В нем имеются палитра выбора цвета, а также набор круглых кистей различного диаметра. С их помощью можно нарисовать свой запрос, работая одновременно и с цветом, и с формой. Лучше всего пока разбираются запросы с чистыми цветами, сделанные крупными мазками, - с мелкими деталями Retrievr справляется не очень уверенно. Результаты поиска немедленно подгружаются на страницу выдачи. Заметим, что, поработав некоторое время с поиском и приспособившись к его особенностям, удается получать довольно качественные результаты.

Поисковик Anaktisi работает с четвертью миллиона снимков, взятых из десятка внешних фотохостингов. Основной инструмент - кнопка Search Similar Images, расположенная рядом с миниатюрами на странице выдачи. В качестве дополнительного фильтра выступает выбор дескрипторов - вариантов расчета подобия изображений. Используются системы CEDD, FTCH и JCD, являющиеся разновидностями так называемых Compact Composite Descriptors (CCD) - средств компактного описания характеристик изображений. Система CEDD, основывающаяся на использовании фильтров MPEG-7, формирует на базе их данных описания текстурных областей картинок. А вот FTCH, в свою очередь, при решении аналогичной задачи полагается на вейвлет-преобразования Хаара. Таким образом, Anaktisi становится любопытным полигоном для тестирования качества и особенностей работы этих алгоритмов для различного типа изображений.

С точки зрения пользователя, поиск выполнен весьма удобно. Начинается он выбором одной из дюжины доступных баз изображений. Далее предлагается определиться с типом дескриптора и, наконец, составить сам запрос. Для выполнения этой задачи доступны практически все современные CBIR-средства. Можно просто начинать просмотр снимков, щелкать на понравившихся и тем самым уточнять свой запрос. Допустима загрузка на сервис в качестве графических запросов собственных изображений. Подобно Retrievr, данная система позволяет сделать запрос-набросок, правда, в качестве поиска она немного проигрывает австрийскому конкуренту. Кроме того, можно воспользоваться классическим поиском по ключевым словам. Все эти режимы доступны в виде закладок интерфейса поисковика.

1.5 .Вывод

В результате написания данной главы нами были рассмотрены различные алгоритмы поиска изображений на основе содержания, а также рассмотрены аналоги разрабатываемой системы.

На основе анализа алгоритмов нами в качестве реализуемого метода был выбран метод поиска на основе гистограмм, как наиболее устойчивый к помехам, а также наиболее просто реализуемый.

Оглавление

- Введение

- Выводы

- Список литературы

- Приложение

Список литературы

1. Синча Д.П. Принципы построения универсальной системы распознавания искаженных изображений // Труды XXVIII Межрегиональной научно-технической конференции, г. Серпухов, 2009 г., Серпуховский ВИ РВ, Сборник №3, с.149-151.

2. Н.С. Байгарова, Ю.А. Бухштаб, А.А. Воробьев, А.А. Горный Организация управления базами визуальных данных Препринт Института прикладной математики им. М.В. Келдыша РАН, 2000, N 6

4. Н.С. Байгарова, Ю.А. Бухштаб, А.А. Горный Методы индексирования и поиска визуальных данных. Препринт Института прикладной математики им. М.В. Келдыша РАН, 2000, N 7.

5. Кобзарь А.И. Прикладная математическая статистика // М:Физматлит, 2006, с.607.

6. Потапов А.С. Распознавание образов и машинное восприятие // СПб:Политехника, 2007, с.45.

7. Ojala Т., Pietikainen М., Maenpaa Т. Multiresolutiоn gray scale and rotatiоn invariant texture analysis with local binary patterns // IEEE Transactions оn Pattern Analysis and Machine Intelligence, 24(7):971- 987, 2002.

8. Большаков А.А., Каримов Р.Н. Методы обработки многомерных данных и временных рядов // М:Горячая линия - Телеком, 2007, с.20.

10. Дрейпер Н., Смит Г. Прикладной регрессионный анализ // М:Диалектика, 2007.

11. Rubner Y. А metric for distributions with applications tо image databases / Y. Rubner, С. Tomasi; L.J. Guibas // Proceedings ICCV - 1998. - Vol. 1- Р. 59-66.

12. Funt В.V. Color constant color indexing / В.V. Funt, G.D. Finlaysоn // Journal IEEE Transactions оn pattern analysis and machine intelligence - 1995. - Vol. 17 - Р. 522-529.

13. Pass G. Comparing images using joint histograms / G. Pass, R. Zabih // Journal Multimedia systems - special issue оn video content based retrieval 1999. - Vol. 7 - Р. 234 - 240.

14. Бабак В.П., Хандецкий В.С., Шлюфер Е. Обработка сигналов. - Киев, из-во "Лебедь",1999. - 493с.