Поиск похожих изображений. Сравнение изображений Вячеслав Колбасин. - презентация

1 Поиск похожих изображений. Сравнение изображений Вячеслав Колбасин

2 Зачем это нужно?

3 1. Фильтрация пользовательского контента (1) Востребована везде, где пользователи могут размещать свои изображения Востребована везде, где пользователи могут размещать свои изображения Особенно если владелец сайта отвечает за добавленное пользователями содержимое Особенно если владелец сайта отвечает за добавленное пользователями содержимое Надо проверять, что Надо проверять, что изображение не оскорбляет общественную мораль изображение не оскорбляет общественную мораль не содержит запрещенной законом символики не содержит запрещенной законом символики не нарушает политику сайта, авторские права и психическое здоровье пользователей сайта не нарушает политику сайта, авторские права и психическое здоровье пользователей сайта

4 Кулинарный форум вегетарианцев Есть кулинарный форум вегетарианцев с интернет- магазином Есть кулинарный форум вегетарианцев с интернет- магазином Пользователи могут оставлять рецепты и изображения получившихся блюд Пользователи могут оставлять рецепты и изображения получившихся блюд Задача – защитить ресурс от размещения рецептов и картинок, неподобающего содержания Задача – защитить ресурс от размещения рецептов и картинок, неподобающего содержания Тексты можно фильтровать по словам, но что делать с фотографиями?Тексты можно фильтровать по словам, но что делать с фотографиями? Что мы понимаем под неподобающим содержанием? Что мы понимаем под неподобающим содержанием? Фруктовый плов Для приготовления фруктового плова необходимы: - 2 стакана риса; грамм сухофруктов; ……………………………. Через 30 минут у меня получился замечательный продукт: Что здесь может быть неподобающего ?

5 Кулинарный форум вегетарианцев Фруктовый плов Для приготовления фруктового плова необходимы: - 2 стакана риса; грамм сухофруктов; ……………………………. Через 30 минут у меня получился замечательный продукт: Новый семинар: Проблемы и решения вывода денег в Нигерию в свете новинок законодательства Телефон для записи : СПАМ Есть кулинарный форум вегетарианцев с интернет- магазином Есть кулинарный форум вегетарианцев с интернет- магазином Пользователи могут оставлять рецепты и изображения получившихся блюд Пользователи могут оставлять рецепты и изображения получившихся блюд Задача – защитить ресурс от размещения рецептов и картинок, неподобающего содержания Задача – защитить ресурс от размещения рецептов и картинок, неподобающего содержания Тексты можно фильтровать по словам, но что делать с фотографиями?Тексты можно фильтровать по словам, но что делать с фотографиями? Что мы понимаем под неподобающим содержанием? Что мы понимаем под неподобающим содержанием?

6 Кулинарный форум вегетарианцев Фруктовый плов Для приготовления фруктового плова необходимы: - 2 стакана риса; грамм сухофруктов; ……………………………. Через 30 минут у меня получился замечательный продукт: Есть кулинарный форум вегетарианцев с интернет- магазином Есть кулинарный форум вегетарианцев с интернет- магазином Пользователи могут оставлять рецепты и изображения получившихся блюд Пользователи могут оставлять рецепты и изображения получившихся блюд Задача – защитить ресурс от размещения рецептов и картинок, неподобающего содержания Задача – защитить ресурс от размещения рецептов и картинок, неподобающего содержания Тексты можно фильтровать по словам, но что делать с фотографиями?Тексты можно фильтровать по словам, но что делать с фотографиями? Что мы понимаем под неподобающим содержанием? Что мы понимаем под неподобающим содержанием? 2. Неприемлемые картинки

7 Кулинарный форум вегетарианцев Фруктовый плов Для приготовления фруктового плова необходимы: - 2 стакана риса; грамм сухофруктов; ……………………………. Через 30 минут у меня получился замечательный продукт: Есть кулинарный форум вегетарианцев с интернет- магазином Есть кулинарный форум вегетарианцев с интернет- магазином Пользователи могут оставлять рецепты и изображения получившихся блюд Пользователи могут оставлять рецепты и изображения получившихся блюд Задача – защитить ресурс от размещения рецептов и картинок, неподобающего содержания Задача – защитить ресурс от размещения рецептов и картинок, неподобающего содержания Тексты можно фильтровать по словам, но что делать с фотографиями?Тексты можно фильтровать по словам, но что делать с фотографиями? Что мы понимаем под неподобающим содержанием? Что мы понимаем под неподобающим содержанием? 3. Неприемлемые объекты на картинках

8 1. Фильтрация пользовательского контента (2) Для каждого изображения надо проверить: Для каждого изображения надо проверить: Есть ли оно в базе запрещенных изображений Есть ли оно в базе запрещенных изображений Встречаются ли в нем запрещенные изображения Встречаются ли в нем запрещенные изображения Технически требуется Технически требуется Выделить на изображении ключевые объекты Выделить на изображении ключевые объекты Возможно придется сегментировать изображение Возможно придется сегментировать изображение Найти в базе запрещенных изображений картинки, похожие на ключевые объекты и на саму картинку Найти в базе запрещенных изображений картинки, похожие на ключевые объекты и на саму картинку

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

10 3. Приложения дополненной реальности Пользователь фотографирует на смартфон объект, например здание, и просит показать информацию по нему Пользователь фотографирует на смартфон объект, например здание, и просит показать информацию по нему Смартфон пересылает на сервер изображение и примерные координаты пользователя Смартфон пересылает на сервер изображение и примерные координаты пользователя Система по ключевым точкам ищет наиболее похожие фотографии в базе и возвращает информацию по ним Система по ключевым точкам ищет наиболее похожие фотографии в базе и возвращает информацию по ним Госпро́м (укр. Держпром) Дом Государственной промышленности, построенный на центральной площади города Харькова площади Дзержинского (с 1996 года площадь Свободы). Памятник архитектуры в стиле конструктивизм, символ данного стиля. (и далее описание из Wikipedia)

11 Другие применения Фотосток Фотосток Проверка авторства изображения Проверка авторства изображения Поиск по изображениям фотостока нет ли такого же изображения с иными пропорциями, удаленными частями, измененными цветами и другими изменениями Поиск по изображениям фотостока нет ли такого же изображения с иными пропорциями, удаленными частями, измененными цветами и другими изменениями Автоматическая классификация фотографий Автоматическая классификация фотографий Сравнение, на какое из типовых изображений больше всего похоже данное Сравнение, на какое из типовых изображений больше всего похоже данное Поиск похожего изображения, но с приемлемой лицензией Поиск похожего изображения, но с приемлемой лицензией Нужна фотография офиса визуально похожая на найденную в сети, но под свободной лицензией Нужна фотография офиса визуально похожая на найденную в сети, но под свободной лицензией Медицинские изображения Медицинские изображения По заданной рентгенограмме найти другие рентгенограммы, которые с диагностической точки зрения похожи на данную По заданной рентгенограмме найти другие рентгенограммы, которые с диагностической точки зрения похожи на данную То есть, имеющие аналогичные особенности То есть, имеющие аналогичные особенности

12 Что человек понимает под похожими изображениями? Изображения (сцены) определенных классов Изображения (сцены) определенных классов Фильтрация контента Фильтрация контента Изображения (сцены), содержащие объекты заданных классов Изображения (сцены), содержащие объекты заданных классов Фильтрация контента Фильтрация контента Медицинские изображения Медицинские изображения Изображения (сцены), содержащие объекты из заданного набора Изображения (сцены), содержащие объекты из заданного набора Дополненная реальность Дополненная реальность Обнаружение номеров машин Обнаружение номеров машин Визуально похожие изображения Визуально похожие изображения Поиск в интернет-магазине Поиск в интернет-магазине Поиск по фотостоку Поиск по фотостоку Идентичные изображения Идентичные изображения Фотосток, проверка дубликатов Фотосток, проверка дубликатов схожие по смыслу изображения визуально схожие изображения

13 Поиск дубликатов. (1) У одинаковых изображений отличие между точками мало У одинаковых изображений отличие между точками мало Выразим отличие как среднеквадратичное отклонение (СКО): Выразим отличие как среднеквадратичное отклонение (СКО): Причем СКО неоднозначная мера – эти изображения отличаются от оригинала примерно одинаково Причем СКО неоднозначная мера – эти изображения отличаются от оригинала примерно одинаково

14 Поиск дубликатов. (2) Что можно улучшить ? Что можно улучшить ? Дополнить СКО учетом Дополнить СКО учетом свойства маскировки свойства маскировки разной чувствительности глаза к разным частотам разной чувствительности глаза к разным частотам восприятие человеком цвета (пространство Lab) восприятие человеком цвета (пространство Lab) Изображения сравнили, а как насчет поиска? Изображения сравнили, а как насчет поиска? Сравниваем искомое изображение со всеми в базе! Сравниваем искомое изображение со всеми в базе! Поиск будет очень ресурсоемким и долгим Поиск будет очень ресурсоемким и долгим Какова будет релевантность поиска ? Какова будет релевантность поиска ? Что будет, если изображение в базе будет немного сдвинуто? Что будет, если изображение в базе будет немного сдвинуто? А если мы изменим его цвет? А если мы изменим его цвет? А если немного изменим пропорции? А если немного изменим пропорции?

15 Поиск дубликатов. (3) Чтобы повысить скорость сравнения можно уменьшить размер сравниваемых изображений Чтобы повысить скорость сравнения можно уменьшить размер сравниваемых изображений Но до какого предела? Но до какого предела? Человек приемлемо распознает Человек приемлемо распознает изображения размера 32*32 и 64*64 на черно-белых изображениях на черно-белых изображениях Что делаем: Что делаем: Переводим в градации серого Переводим в градации серого Яркость нормируем Яркость нормируем Все изображения Все изображения масштабируем к квадрату масштабируем к квадрату 1024 байт на изображение ? - все равно много! 1024 байт на изображение ? - все равно много! A. Torralba, R. Fergus, W. T. Freeman. 80 million tiny images: a large dataset for non-parametric object and scene recognition, 2008

16 Пирамиды изображений Будем постепенно увеличивать размер изображения Отберем изображения размера 4*4 Потом из них выберем самые похожие размера 8*8 И так далее Так быстрее, но все равно полный перебор ошибки при существенно изменении пропорций изображения метод непосредственно применим только для поиска дубликатов

17 Что человек понимает под похожими изображениями? Изображения (сцены) определенных классов Изображения (сцены) определенных классов Фильтрация контента Фильтрация контента Изображения (сцены), содержащие объекты заданных классов Изображения (сцены), содержащие объекты заданных классов Фильтрация контента Фильтрация контента Медицинские изображения Медицинские изображения Изображения (сцены), содержащие объекты из заданного набора Изображения (сцены), содержащие объекты из заданного набора Дополненная реальность Дополненная реальность Обнаружение номеров машин Обнаружение номеров машин Визуально похожие изображения Визуально похожие изображения Поиск в интернет-магазине Поиск в интернет-магазине Поиск по фотостоку Поиск по фотостоку Идентичные изображения Идентичные изображения Фотосток, проверка дубликатов Фотосток, проверка дубликатов схожие по смыслу изображения визуально схожие изображения

18 Визуально схожие изображения Изображения, из которых получили образец Изображения, из которых получили образец Изменены пропорции Изменены пропорции Часть изображения удалена Часть изображения удалена Изменен цвет Изменен цвет Изображения, похожие на образец Изображения, похожие на образец Картинка зрительно похожа, Картинка зрительно похожа, совпадение объектов на ней совпадение объектов на ней не проверяется не проверяется

19 Признаки изображения Сравнивать попиксельно – неэффективно, нужны общие признаки изображения Сравнивать попиксельно – неэффективно, нужны общие признаки изображения По ним и будем вести поиск По ним и будем вести поиск Что может быть признаком Что может быть признаком Яркость точек Яркость точек Цвет точек Цвет точек Типовые фрагменты изображения («слова») Типовые фрагменты изображения («слова») Локальные особенности изображения Локальные особенности изображения Как сравнивать признаки? Как сравнивать признаки? Сравнивать гистограммы признаков Сравнивать гистограммы признаков Сравнивать локализацию признаков на изображении Сравнивать локализацию признаков на изображении

20 Гистограммы яркостей Переводим изображения в градации серого и строим гистограмму яркостей точек Переводим изображения в градации серого и строим гистограмму яркостей точек Далее гистограммы квантуем для уменьшения числа столбцов и сравниваем между собой Далее гистограммы квантуем для уменьшения числа столбцов и сравниваем между собой

21 Гистограммы цветов Переводим изображения в цветовое пространство Lab и строим гистограмму распределения компонент а, b Переводим изображения в цветовое пространство Lab и строим гистограмму распределения компонент а, b Можно привести цвета изображения к палитре с малым числом цветов и строить гистограмму по ней Можно привести цвета изображения к палитре с малым числом цветов и строить гистограмму по ней

22 Гистограммы Для сравнения гистограмм можно Для сравнения гистограмм можно По столбцам вычесть одну гистограмму из другой По столбцам вычесть одну гистограмму из другой Посчитать сколько перемещений потребуется, чтобы превратить одну гистограмму в другую Посчитать сколько перемещений потребуется, чтобы превратить одну гистограмму в другую Недостатки гистограмм Недостатки гистограмм Признаки слишком общие и такие два изображения будут считаться одинаковыми Признаки слишком общие и такие два изображения будут считаться одинаковыми

23 Пирамиды гистограмм Чтобы добавить пространственного разрешения разделим изображение на части и будем для каждой из них строить гистограмму Чтобы добавить пространственного разрешения разделим изображение на части и будем для каждой из них строить гистограмму Уровень 0Уровень 1Уровень 2 А. Конушин. Лекции по компьютерному зрению МГУ

24 Метод выделения признаков «мешок слов» Адаптация метода анализа текстов, использующего набор слов текста, без учета синтаксических особенностей Адаптация метода анализа текстов, использующего набор слов текста, без учета синтаксических особенностей Как работает Как работает Выделяем на изображении типовые Выделяем на изображении типовые фрагменты фрагменты Считаем частоту их встречаемости Считаем частоту их встречаемости Это и есть дескриптор изображений Это и есть дескриптор изображений Что считать типовым фрагментом Что считать типовым фрагментом Часто зависит от обучающей выборки Часто зависит от обучающей выборки Как правило – получаются примитивы Как правило – получаются примитивы восприятия изображения восприятия изображения (Fei-Fei, Perona – 2005)

25 Локальные особенности Надо ли рассматривать все изображение для сравнения? Надо ли рассматривать все изображение для сравнения? Нет, обычно достаточно посмотреть на несколько хорошо различимых точек Нет, обычно достаточно посмотреть на несколько хорошо различимых точек Характеристические точки Характеристические точки Локальные особенности Локальные особенности Как определить эти области? Как определить эти области? Их должно быть меньше числа пикселей на изображении Их должно быть меньше числа пикселей на изображении Область должна быть локальной Область должна быть локальной Область должна быть значимой (при сдвиге области результат сравнения должен изменяться) Область должна быть значимой (при сдвиге области результат сравнения должен изменяться) Как сравнить изображения по областям? Как сравнить изображения по областям? Найти схожие области на двух изображениях Найти схожие области на двух изображениях Найти преобразование, которое их совмещает Найти преобразование, которое их совмещает Посмотреть, удалось ли эти точки совместить Посмотреть, удалось ли эти точки совместить Если да, сравнить содержимое точек Если да, сравнить содержимое точек

26 Углы как локальные особенности Что здесь можно выбрать как локальную особенность ? Что здесь можно выбрать как локальную особенность ? Где окно можно сдвинуть так, чтобы изображение внутри него осталось неизменным? Где окно можно сдвинуть так, чтобы изображение внутри него осталось неизменным? Окно анализа можем сдвигать в любом направлении Окно анализа можем сдвигать вдоль линии Окно анализа не можем сдвигать никуда Координаты углов можно определить детектором Харриса Координаты углов можно определить детектором Харриса C. Harris, M. Stephens A Combined Corner and Edge detector // Proc. of 4 th Alvey Vision Conference, p , 1988 C. Harris, M. Stephens A Combined Corner and Edge detector // Proc. of 4 th Alvey Vision Conference, p , 1988

27 Размер особенностей Особенности детектора Особенности детектора Нечувствителен к повороту изображения Нечувствителен к повороту изображения Частично чувствителен к изменению яркости Частично чувствителен к изменению яркости Чувствителен к изменению масштаба Чувствителен к изменению масштаба Угол в одном масштабе – линия в другом Угол в одном масштабе – линия в другом Как определить размер особенности? Как определить размер особенности? Выбрать радиус так, чтобы особенность помещалась целиком Выбрать радиус так, чтобы особенность помещалась целиком Обработать изображение фильтром, выделяющим края Обработать изображение фильтром, выделяющим края Выбрать масштаб, чтобы отклик фильтра от двух краев накладывался Выбрать масштаб, чтобы отклик фильтра от двух краев накладывался Source: S. Lazebnik

28 Размер особенностей (2) Свертываем изображение с фильтром разного масштаба Свертываем изображение с фильтром разного масштаба Смотрим, на каком масштабе будет максимум отклика Смотрим, на каком масштабе будет максимум отклика Можно ускорить используя метод Difference of Gaussian Можно ускорить используя метод Difference of Gaussian D. Lowe Distinctive image features from scale-invariant keypoints, 2004 D. Lowe Distinctive image features from scale-invariant keypoints, 2004 Выделение особенностей Выделение особенностей Выделяем точки детектором Харриса Выделяем точки детектором Харриса Находим размер методом Difference of Gaussian Находим размер методом Difference of Gaussian Source: S. Lazebnik

29 Дескриптор точки Дескриптор должен быть инвариантен к повороту Дескриптор должен быть инвариантен к повороту Используем градиенты пикселей Используем градиенты пикселей Для характеристической области Для характеристической области Определим доминантное направление градиента, Определим доминантное направление градиента, Повернем область так, чтобы градиент был направлен в одну сторону Повернем область так, чтобы градиент был направлен в одну сторону Приведем область к стандартному размеру Приведем область к стандартному размеру Строим дескриптор Строим дескриптор

30 Дескриптор SIFT Вычислим градиент в каждой точке Вычислим градиент в каждой точке Квантуем ориентации градиентов по 8-ми направлениям Квантуем ориентации градиентов по 8-ми направлениям Строим гистограмму направления градиентов Строим гистограмму направления градиентов Можем разделить область сеткой 4 х 4 для учета локальных особенностей Можем разделить область сеткой 4 х 4 для учета локальных особенностей Итого: Итого: 16 (4 х 4) ячеек 16 (4 х 4) ячеек В каждой гистограмма 8 В каждой гистограмма 8 напралений напралений = 128 элементов = 128 элементов D. Lowe. Distinctive Image Features from Scale-Invariant Keypoints, 2004

31 Применение SIFT Cравнение дескрипторов двух изображений Cравнение дескрипторов двух изображений Сравнение взаимного расположения дескрипторов на двух изображениях Сравнение взаимного расположения дескрипторов на двух изображениях Поиск зоны интереса на изображении Поиск зоны интереса на изображении Слесарев и др. Яндекс на РОМИП 2010: Поиск похожих изображений и дубликатов, 2010

32 Поиск изображений по базе Для ускорения поиска можно использовать Для ускорения поиска можно использовать kD-мерные деревья (kD-trees) kD-мерные деревья (kD-trees) Кластеризация + «инвертированный» индекс по дескриптору Кластеризация + «инвертированный» индекс по дескриптору Locality Sensitive Hashing Locality Sensitive Hashing Спектральное хеширование Спектральное хеширование Увы… не сегодня Увы… не сегодня

33 Реализация Библиотека OpenCV Библиотека OpenCV Де-факто стандарт в области обработки Де-факто стандарт в области обработки изображений и компьютерного зрения изображений и компьютерного зрения Свободная лицензия Свободная лицензия Написана на С++, но портирована на Java, C#, Python Написана на С++, но портирована на Java, C#, Python Ограничено поддерживает использование GPU Ограничено поддерживает использование GPU Очень хорошо документирована Очень хорошо документирована VLFeat VLFeat Более специализированная библиотека для анализа изображений Более специализированная библиотека для анализа изображений Написана на С++, есть интерфейс к Matlab Написана на С++, есть интерфейс к Matlab Нет поддержки работы с устройствами видеозахвата Нет поддержки работы с устройствами видеозахвата

34 Материалы Замечательные курсы по компьютерному зрению и обработке изображений МГУ им. Ломоносова Замечательные курсы по компьютерному зрению и обработке изображений МГУ им. Ломоносова Книга Richard Szeliski. Computer Vision: Algorithms and Applications. Richard Szeliski. Computer Vision: Algorithms and Applications. Материалы по OpenCV Материалы по OpenCV – Русский перевод книги Learning OpenCV – Русский перевод книги Learning OpenCV – сайт библиотеки – сайт библиотеки

35 Вопросы ?