СПОСОБ ОБРАБОТКИ ИЗОБРАЖЕНИЯ, СПОСОБ СОЗДАНИЯ ИНДЕКСА ИЗОБРАЖЕНИЯ, СПОСОБ ОБНАРУЖЕНИЯ СООТВЕТСТВИЯ ИЗОБРАЖЕНИЮ ИЗ ХРАНИЛИЩА ИЗОБРАЖЕНИЙ И СЕРВЕР (ВАРИАНТЫ) Российский патент 2016 года по МПК G06K9/46 G06K9/62 G06T1/00 G06F17/30 

Область техники

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

Уровень техники

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

Например, может быть необходимо найти изображения одного и того же ландшафта с разных ракурсов. Как правило, это называется - поиск "изображения по тексту". Возможны несколько вариантов. Например, пользователь конкретно ищет изображения Ниагарского водопада. Пользователь получает доступ к поисковой системе, например, к поисковой системе Yandex™, располагающейся по адресу www.yandex.ru (или любой другой коммерчески доступной или собственной поисковой системе), и вводит свой поисковый запрос - "Ниагарский водопад". В ответ на поисковый запрос (в зависимости от конкретного варианта осуществления поисковой системы), поисковая система выводит набор изображений, соответствующих поисковому запросу (обычно, если поисковая система реализована как вертикальная поисковая система или если пользователь выполняет вертикальный поиск в рамках обычной поисковой системы), или же выводит сочетание результатов в виде изображений и других веб-ресурсов, которое соответствует поисковому запросу пользователя.

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

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

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

Запрос на получение изображения обычно выполняется в два этапа: поиск и пост-обработка. На этапе поиска похожие изображения извлекаются из большой базы данных и происходит первичное ранжирование. Наиболее популярным подходом является индексирование изображений с помощью инвертированных файлов для ускорения получения доступа к изображениям, обладающим общими визуальными словами. На этапе пост-обработки происходит более точное ранжирование полученных изображений, обычно с помощью пространственной проверки.

Раскрытие изобретения

Задачей предлагаемой технологии является устранение по меньшей мере некоторых недостатков, присущих известному уровню техники.

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

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

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

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

В некоторых вариантах осуществления способа, информация о соотношении содержит информацию о пространственном соотношении между первой локальной областью и второй локальной областью.

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

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

В некоторых вариантах осуществления способа информация о соотношении содержит по меньшей мере одно из следующего: (i) информацию о пространственном соотношении между первой локальной областью и второй локальной областью и (ii) информацию о визуальном соотношению между первой локальной областью и второй локальной областью.

В некоторых вариантах осуществления способа он дополнительно включает получение изображения через сеть передачи данных.

В некоторых вариантах осуществления способа идентификация выполняется на случайной основе.

В некоторых вариантах осуществления способа идентификация выполняется на основе заранее определенного алгоритма.

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

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

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

В некоторых вариантах осуществления способа, упомянутая часть включает первое визуальное слово и второе визуальное слово.

В некоторых вариантах осуществления способа, упомянутая часть включает квантованные первое визуальное слово и второе визуальное слово.

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

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

В некоторых вариантах осуществления способа упомянутая часть включает первое визуальное слово и второе визуальное слово и сочетание:

(i) квантованного параметра пространственного соотношения между первой областью и второй областью и

(ii) квантованного параметра визуального соотношения между первой областью и второй областью.

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

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

Еще одним объектом настоящей технологии является способ обнаружения соответствия изображению из хранилища изображений, причем хранилище изображений содержит множество изображений способ выполняется на сервере и включает: получение указания на изображение; определение для искомого изображения композитного параметра визуальных характеристик, соответствующего изображению; проведение многостадийного поиска, включающего следующие этапы: выбор изображений-кандидатов из множества изображений, причем выбор осуществляется с помощью получения доступа к индексу, который коррелирует с данным композитным параметром визуальных характеристик для изображений, содержащихся в рамках множества изображений, и который соответствует параметру изображений, содержащихся в рамках множества изображений; проверка изображений по отношению к искомому изображению по одному с использованием соответствующих локальных дескрипторов. В некоторых вариантах осуществления технологии, проверка предполагаемых изображений выполняется в виде географической проверки или в виде проверки с использованием соответствующих локальных дескрипторов и их положения в рамках изображений-кандидатов (и, соответственно, искомого изображения).

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

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

В некоторых вариантах осуществления способа, информация о соотношении содержит информацию о пространственном соотношении между первой локальной областью и второй локальной областью.

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

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

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

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

В некоторых вариантах осуществления способа соответствующий композитный параметр визуальных характеристик дополнительно содержит информацию о соотношении между первой локальной областью и второй локальной областью.

В некоторых вариантах осуществления способа информация о соотношении содержит информацию о пространственном соотношении между первой локальной областью и второй локальной областью.

В некоторых вариантах осуществления способа информация о соотношении содержит информацию о визуальном соотношении между первой локальной областью и второй локальной областью.

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

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

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

Еще одним объектом настоящей технологии является сервер, включающий постоянный машиночитаемый носитель, хранящий машиночитаемые инструкции, при выполнении которых сервер, выполняет обработку изображения, позволяющую индексировать и сравнивать изображение с другими изображениями, при этом обработка включает: идентификацию первой локальной области изображения и второй локальной области изображения; определение первого визуального слова, связанного с первой локальной областью изображения, и второго визуального слова, связанного со второй областью изображения; определение композитного параметра визуальных характеристик, связанного с изображением, причем композитный параметр визуальных характеристик содержит первое визуальное слово и второе визуальное слово.

Еще одним объектом настоящей технологии является сервер, включающий постоянный машиночитаемый носитель, хранящий машиночитаемые инструкции, при выполнении которых сервер, выполняет создании индекса изображений, причем индекс изображений позволяет сравнивать изображение с другими изображениями, и включает: определение, по меньшей мере, одного ключа для индекса, причем, по меньшей мере, один ключ содержит, по меньшей мере, часть композитного параметра визуальных характеристик, связанных с индексируемым изображением, причем композитный параметр визуальных характеристик был определен при выполнении следующих этапов: идентификации первой локальной области изображения и второй локальной области изображения; определения первого визуального слова, связанного с первой локальной областью изображения, и второго визуального слова, связанного со второй областью изображения; определения композитного параметра визуальных характеристик, связанного с изображением, причем композитный параметр визуальных характеристик содержит первое визуальное слово и второе визуальное слово; сохранения указания на изображение, соответствующего композитному параметру визуальных характеристик в списке словопозиций, связанного, по меньшей мере, с одним ключом.

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

В контексте настоящего описания «сервер» подразумевает под собой компьютерную программу, работающую на соответствующем оборудовании, которая способна получать запросы (например, от клиентских устройств) по сети и выполнять эти запросы или инициировать выполнение этих запросов. Оборудование может представлять собой один физический компьютер или одну физическую компьютерную систему, но ни то, ни другое не является обязательным для данной технологии. В контексте настоящей технологии использование выражения «сервер» не означает, что каждая задача (например, полученные инструкции или запросы) или какая-либо конкретная задача будет получена, выполнена или инициирована к выполнению одним и тем же сервером (то есть одним и тем же программным обеспечением и/или аппаратным обеспечением); это означает, что любое количество элементов программного обеспечения или аппаратных устройств может быть вовлечено в прием/передачу, выполнение или инициирование выполнения любого запроса или последствия любого запроса, связанного с клиентским устройством, и все это программное и аппаратное обеспечение может быть одним сервером или несколькими серверами, оба варианта включены в выражение «по меньшей мере один сервер».

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

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

В контексте настоящего описания «информация» включает любую информацию, которая может храниться в базе данных. Таким образом, информация включает, среди прочего, аудиовизуальные произведения (изображения, видео, звукозаписи, презентации и т.д.), данные (данные о местоположении, цифровые данные и т.д.), текст (мнения, комментарии, вопросы, сообщения и т.д.), документы, таблицы и т.д.

В контексте настоящего описания «компонент» подразумевает программное обеспечение (соответствующее конкретному аппаратному контексту), которое является необходимым и достаточным для выполнения конкретной(ых) указанной(ых) функции(й).

В контексте настоящего описания «используемый компьютером носитель компьютерной информации» подразумевает носитель абсолютно любого типа и характера, включая ОЗУ, ПЗУ, диски (компакт диски, DVD-диски, дискеты, жесткие диски и т.д.), USB флеш-накопители, твердотельные накопители, накопители на магнитной ленте и т.д.

В контексте настоящего описания слова «первый», «второй», «третий» и и т.д. используются в виде прилагательных исключительно для того, чтобы отличать существительные, к которым они относятся, друг от друга, а не для целей описания какой-либо конкретной связи между этими существительными. Так, например, следует иметь в виду, что использование терминов "первый сервер" и "третий сервер " не подразумевает какого-либо порядка, отнесения к определенному типу, хронологии, иерархии или ранжирования (например) серверов/между серверами, равно как и их использование (само по себе) не предполагает, что некий "второй сервер" обязательно должен существовать в той или иной ситуации. В дальнейшем, упоминание "первого" элемента и "второго" элемента не исключает возможности того, что это один и тот же фактический реальный элемент. Так, например, в некоторых случаях, "первый" сервер и "второй" сервер могут являться одним и тем же программным и/или аппаратным обеспечением, а в других случаях они могут являться разным программным и/или аппаратным обеспечением.

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

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

Краткое описание чертежей

Для лучшего понимания настоящей технологии, а также других ее аспектов и характерных черт сделана ссылка на следующее описание, которое должно использоваться в сочетании с прилагаемыми чертежами, где:

На Фиг. 1 представлена система 100, выполненная с возможностью реализовать различные варианты осуществления настоящей технологии.

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

На Фиг. 3 представлен не ограничивающий вариант осуществления индекса 300, находящегося на сервере системы 100, показанной на Фиг. 1.

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

На Фиг. 5 представлена блок-схема способа 500, реализованного в соответствии с вариантами осуществления настоящей технологии, не ограничивающими ее объем.

На Фиг. 6 представлена блок-схема способа 600, реализованного в соответствии с вариантами осуществления настоящей технологии, не ограничивающими ее объем.

На Фиг. 7 представлена блок-схема способа 700, реализованного в соответствии с вариантами осуществления настоящей технологии, не ограничивающими ее объем.

На Фиг. 8 представлен пример изображения, демонстрирующего определение композитного параметра в соответствии с вариантом осуществления настоящей технологии.

Осуществление изобретения

На Фиг. 1 представлена система 100, реализованная в соответствии с вариантами осуществления настоящей технологии. Важно иметь в виду, что нижеследующее описание системы 100 представляет собой описание иллюстративных вариантов осуществления настоящей технологии. Таким образом, все последующее описание представлено только как описание иллюстративного примера настоящей технологии. Это описание не предназначено для определения объема или установления границ настоящей технологии. Некоторые полезные примеры модификаций системы 100 также могут быть охвачены нижеследующим описанием. Целью этого является также исключительно помощь в понимании, а не определение объема и границ настоящей технологии. Эти модификации не представляют собой исчерпывающий список, и специалистам в данной области техники будет понятно, что возможны и другие модификации. Кроме того, это не должно интерпретироваться так, что там, где это еще не было сделано, т.е. там, где не были изложены примеры модификаций, никакие модификации невозможны, и/или что то, что описано, является единственным вариантом осуществления этого элемента настоящей технологии. Как будет понятно специалистам в данной области техники, это, скорее всего, не так. Кроме того, следует иметь в виду, что система 100 представляет собой в некоторых конкретных проявлениях достаточно простой вариант осуществления настоящей технологии, и в подобных случаях представлен здесь с целью облегчения понимания. Как будет понятно специалистам в данной области техники, многие варианты осуществления настоящей технологии будут обладать гораздо большей сложностью.

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

Варианты электронного устройства 102 конкретно не ограничены, но в качестве примера электронного устройства 102 могут использоваться персональные компьютеры (настольные компьютеры, ноутбуки, нетбуки и т.п.), устройства беспроводной связи (мобильные телефоны, смартфоны, планшеты и т.п.), а также сетевое оборудование (маршрутизаторы, коммутаторы или шлюзы). На Фиг.1 электронное устройство 102 реализовано в виде персонального компьютера (настольного компьютера).

Электронное устройство 102 включает в себя аппаратное и/или прикладное программное, и/или системное программное обеспечение (или их комбинацию), как известно в данной области техники, для использования поискового приложения 104. В общем случае, целью поискового приложения 104 является предоставление возможности пользователю (не показан) выполнять поиск, например, сетевой поиск с помощью вышеупомянутой поисковой системы.

Реализация поискового приложения 104 никак конкретно не ограничена. Один из примеров поискового приложения 104 может быть реализован в виде вызова пользователем веб-сайта, соответствующего поисковой системе, для получения доступа к поисковому приложению 104. Например, поисковое приложение может быть вызвано путем ввода URL, связанного с поисковой системой Yandex www.yandex.ru. Важно иметь в виду, что поисковое приложение 104 может быть вызвано с помощью любой другой коммерчески доступной или собственной поисковой системы.

В других вариантах осуществления настоящей технологии, не ограничивающих ее объем, поисковое приложение 104 может представлять собой браузерное приложение на портативном устройстве (например, беспроводном устройстве связи). Для тех случаев (но не только), когда электронное устройство 102 является портативным устройством, таким как, например, Samsung™ Galaxy™ SIII, электронное устройство может использовать приложение Яндекс браузер. Важно иметь в виду, что любое другое коммерчески доступное или собственное браузерное приложение может быть использовано для реализации вариантов осуществления настоящей технологии, не ограничивающих ее объем.

Электронное устройство 102 соединено с сетью связи 114 через линию связи 112. В некоторых вариантах осуществления настоящей технологии, не ограничивающих ее объем, сеть связи 114 может представлять собой Интернет. В других вариантах осуществления настоящей технологии, сеть связи 114 может быть реализована иначе - в виде глобальной сети связи, локальной сети связи, частной сети связи и т.п.

Реализация линии связи 112 не ограничена, и будет зависеть от того, какое устройство связи 102 используется. В качестве примера, но не ограничения, в данных вариантах осуществления настоящей технологии когда электронное устройство 102 представляет собой беспроводное устройство связи (например, смартфон), линия связи 102 представляет собой беспроводную сеть связи (например, среди прочего, линия связи сети 3G, линия связи сети 4G, беспроводной интернет Wireless Fidelity или сокращенно WiFi®, Bluetooth® и т.п.). В тех примерах, где средство связи 102 представляет собой портативный компьютер, линия связи может быть как беспроводной (беспроводной интернет Wireless Fidelity или сокращенно WiFi®, Bluetooth® и т.п) так и проводной (соединение на основе сети Ethernet).

Важно иметь в виду, что варианты осуществления воплощения электронного устройства 102, линии связи 112 и сети связи 114 даны исключительно в иллюстрационных целях. Таким образом, специалисты в данной области техники смогут понять подробности других конкретных вариантов осуществления электронного устройства 102, линии связи 11 и сети связи 114. То есть, представленные здесь примеры не ограничивают объем настоящей технологии.

К сети связи также присоединен сервер 116. Сервер 116 может представлять собой обычный компьютерный сервер. В примере варианта осуществления настоящей технологии, сервер 116 может представлять собой сервер Dell™ PowerEdge™, на котором используется операционная система Microsoft™ Windows Server™. Излишне говорить, что сервер 116 может представлять собой любое другое подходящее аппаратное и/или прикладное программное, и/или системное программное обеспечение или их комбинацию. В представленном варианте осуществления настоящей технологии, не ограничивающем ее объем, сервер 116 является одиночным сервером. В других вариантах осуществления настоящей технологии, не ограничивающих ее объем, функциональность сервера 116 может быть разделена, и может выполняться с помощью нескольких серверов.

В некоторых вариантах осуществления настоящей технологии, сервер 116 находится под контролем и/или управлением поставщика поисковой систем, такого, например, как оператор поисковой системы Yandex. Как вариант, сервер 116 может находиться под контролем и/или управлением поставщика сервиса.

Также предусмотрено хранилище 118 изображений. В некоторых вариантах осуществления настоящей технологии хранилище 118 изображений может быть реализовано как хранилище множества электронных файлов изображений. В других вариантах осуществления настоящей технологии хранилище 118 изображений может быть реализовано как распределенный субъект, содержащий множество файлов электронных изображений. Например, хранилище 118 изображений может представлять собой набор нескольких или всех файлов электронных изображений, доступных на различных серверах (не показаны) в рамках сети 114 передачи данных. Как вариант, хранилище 118 изображений может представлять собой набор файлов электронных изображений, доступных в конкретном субъекте, например, в библиотеке или научно-исследовательском учреждении. Другими словами, варианты осуществления настоящей технологии могут быть полезны для индексирования и поиска изображений, хранящихся на компьютерном устройстве (жестком диске, сервере и т.п.), удаленном компьютерном устройстве (сервере и т.п.) или распределенном хранилище (хранилище изображений, распределенном по нескольким серверам и т.п.).

Сервер 116 выполнен с возможностью запускать приложение 120 для управления изображениями. Функциональность приложения 120 для управления изображениями будет подробно описана ниже. Пока достаточно упомянуть, что приложение 120 для управления изображениями выполнено с возможностью выполнять, по меньшей мере, одно из следующего: (i) получить файл изображения; (ii) разобрать содержащееся в файле изображение на визуальные слова; (iii) создать композитный параметр визуальных характеристик для изображения; (iv) создать индекс с использованием композитного параметра визуальных характеристик. Сервер 116 также может быть выполнен с возможностью выполнять поиск на основе индекса, созданного на этапе (iv), что будет подробно описано ниже.

Со ссылкой на Фиг. 2, работа приложения 120 для управления изображениями, происходящая на сервере 116 в контексте выполнения индексирования файла, будет подробно описана ниже.

ПОЛУЧЕНИЕ ФАЙЛА ИЗОБРАЖЕНИЯ

Приложение 120 для управления изображениями выполнено с возможностью получить файл 202 изображения. В некоторых вариантах осуществления настоящей технологии сервер 116 может получить файл 202 изображения из хранилища 118 изображений. В рамках этих вариантов осуществления файл 202 изображения может представлять собой изображение для индексирования. Например, файл 202 изображения может представлять собой один из множества файлов изображений в хранилище 118 изображений, которые требуют индексирования.

Как вариант, сервер 116 может получить файл 202 изображения от электронного устройств 102. В рамках этих вариантов осуществления файл 202 изображения может представлять собой файл изображения, который пользователь электронного устройства 102 хочет использовать в качестве поискового запроса.

РАЗБОР ФАЙЛА ИЗОБРАЖЕНИЯ НА ВИЗУАЛЬНЫЕ СЛОВА

Приложение 120 для управления изображениями дополнительно выполнено с возможностью разбивки на части изображение, содержащееся в файле 202 изображения, для определения визуальных слов, связанных с различными частями (т.е. различными локальными областями) изображения, содержащегося в файле 202 изображения. В конкретном примере приложение 120 для управления изображениями выполнено с возможностью разбивки изображения, содержащегося в файле 202 изображения, на различные области (также могут быть выбраны важные области на основе алгоритма, описанного ниже), соответствующие каждой из областей с соответствующим визуальным словом, схематически представленным на Фиг. 2 в виде позиции 204.

Конкретнее, приложение 120 для управления изображениями определяет локальные дескрипторы. Локальные дескрипторы описывают конкретную область изображения, содержащегося в файле 202 изображения. Например, локальные дескрипторы могут быть основаны на алгоритме преобразования масштабно-инвариантных характеристик (SIFT). Естественно, может быть использован любой другой подходящий алгоритм.

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

В качестве иллюстрации, приложение 120 для управления изображениями определяет визуальное слово 204а, визуальное слово 204b, визуальное слово 204с, визуальное слово 204d, визуальное слово 204е, визуальное слово 204f, визуальное слово 204д и визуальное слово 204h. Проще говоря, каждое из визуальных слов 204а, 204b, 204с, 204d, 204е, 204f, 204g и 204h представляет соответствующий локальный дескриптор изображения 202.

ИНДЕКСИРОВАНИЕ ИЗОБРАЖЕНИЯ ДЛЯ КОМПОЗИТНОГО ПАРАМЕТРА ВИЗУАЛЬНЫХ ХАРАКТЕРИСТИК

Также приложение 120 для управления изображениями выполнено с возможностью индексировать изображение 202 с помощью "композитного параметра визуальных характеристик". В некоторых вариантах осуществления настоящей технологии композитный параметр визуальных характеристик или "КПВХ" является набором локальных дескрипторов, выбранных по меньшей мере из двух областей изображения. В других вариантах осуществления настоящей технологии, КПВХ является набором по меньшей мере двух дескрипторов (из двух соответствующих областей изображения) и параметром соотношения областей характеризующим соотношение между двумя соответствующими областями изображения.

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

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

Например, приложение 120 для управления изображениями использует визуальные слова 204а, 204b, 204с, 204d, 204е, 204f, 204g и 204h; а также информацию о пространственном соотношении между соответствующими из визуальных слов 204а, 204b, 204с, 204d, 204е, 204f, 204g и 204h для создания композитного параметра визуальных характеристик. Композитный параметр визуальных характеристик также можно рассматривать как "визуальную фразу" или "визуальную характеристику высокого порядка".

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

Следовательно, можно сказать, что композитный параметр визуальных характеристик, созданный сервером

116 представляет (i), по меньшей мере, два локальных дескриптора, связанных с соответствующими областями изображения и (ii) характеристику визуального соотношения, по меньшей мере, двух соответствующих областей в рамках изображения 202.

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

В качестве иллюстрации процесса создания КПВХ будет сделана краткая ссылка на Фиг. 8, на которой представлен не ограничивающий пример изображения 802, которое анализируется для создания КПВХ. Для иллюстрации, в качестве двух локальных областей были выбраны первая локальная область 804 и вторая локальная область 806. Первая локальная область 804 и вторая локальная область 806 связаны с соответствующими параметрами 808, 810, которые включают в себя, например, координаты и масштабы. В качестве иллюстрации, КПВХ может быть основан на двух соответствующих локальных дескрипторах, связанных соответственно с первой локальной областью 804 и второй локальной областью 806. Как вариант, КПВХ может быть основан на двух локальных дескрипторах, связанных соответственно с первой локальной областью 804 и второй локальной областью 806 (причем локальные дескрипторы могут быть основаны, по меньшей мере, частично, на параметрах 808, 810), параметр 810 геометрического и/или визуального соотношения между первой локальной областью 804 и второй локальной областью 806 (или, как вариант, параметр 810 соотношения может соответствовать визуальным характеристикам другим областям изображения или целому изображению). В некоторых вариантах осуществления технологии, параметр соотношения может быть вычислен, по меньшей мере, частично, на основе величины угла φ, причем угол φ представляет собой угол между гипотетической горизонтальной линией и линией (показана на Фиг. 8 под номером 816), проходящей через центральную точку первой локальной области 804 и второй локальной области 806. Дополнительно или альтернативно, параметр соотношения может быть вычислен, по меньшей мере, частично, на основе величины угла ? между соответственными доминантными векторами 812 и 814 первой локальной области 804 и второй локальной области 806.

Возвращаясь к описанию Фиг. 2, следует отметить, что процесс получения, разбора и индексирования может быть повторен для множества изображений. В рамках данной иллюстрации, продолжая обращаться к Фиг. 2, приложение 120 для управления изображениями выполнено с возможностью повторять этапы получения, обработки и индексирования каждого из изображений 206, 208, 210, 212, 214 и 216.

СОЗДАНИЕ ИНДЕКСА

Далее, приложение 120 для управления изображениями выполнено с возможностью создать индекс, вариант реализации этого представлен на Фиг. 3 под номером 300. В рамках рассматриваемого варианта осуществления технологии, индекс 300 соответствует каждому композитному параметру визуальных характеристик (или их части, как будет описано ниже) как ключ к индикации изображений из списка индексированных изображений (т.е. изображений 206, 208, 210, 212, 214 и 216), в которых присутствует конкретный композитный параметр визуальных характеристик. Следует иметь в виду, что в некоторых вариантах осуществления настоящей технологии, каждый компонент композитного параметра визуальных характеристик является квантованным. В некоторых вариантах осуществления каждый компонент квантуется независимо.

Индикация того, какому из изображений 202, 206, 208, 210, 212, 214 и 216 соответствует данный ключ, может быть названа "список словопозиций".

Например, индекс 300 соответствует <ключ КПВХ 1> 304 изображения 212 и изображения 214. Также индекс 300 соответствует <ключ КПВХ 2> 306 изображений 204, 206, 218 и 216. Также индекс 300 соответствует <ключ КПВХ 3> 308 изображений 208, 210, 214 и 216. Наконец, индекс 300 соответствует <ключ КПВХ 4> 310 изображения N, которое обозначает другие возможные соответствия, возможные в рамках индекса 300.

В соответствии с вариантами осуществления настоящей технологии, реализации <ключ КПВХ 1> 304, <ключ КПВХ 2> 306, <ключ КПВХ 3> 308 и <ключ КПВХ 4> 310 могут быть следующими.

Например, <ключ КПВХ 1> 304, <ключ КПВХ 2> 306, <ключ КПВХ 3> 308 и <ключ КПВХ 4> 310 могут быть реализованы как вышеупомянутый композитный параметр визуальных характеристик или "визуальные фразы". В других вариантах осуществления настоящей технологии <ключ КПВХ 1> 304, <ключ КПВХ 2> 306, <ключ КПВХ 3> 308 и <ключ КПВХ 4> 310 могут быть реализованы как квантованный элемент вышеупомянутого композитного параметра визуальных характеристик. Например, в некоторых вариантах осуществления настоящей технологии <ключ КПВХ 1> 304, <ключ КПВХ 2> 306, <ключ КПВХ 3> 308 и <ключ КПВХ 4> 310 могут быть реализованы как части квантованных локальных дескрипторов композитного параметра визуальных характеристик. Как вариант, <ключ КПВХ 1> 304, <ключ КПВХ 2> 306, <ключ КПВХ 3> 308 и <ключ КПВХ 4> 310 могут быть реализованы как части квантованных локальных дескрипторов и часть связанной информации о соотношении между соответствующими областями композитного параметра визуальных характеристик.

В этих вариантах осуществления, где в качестве части композитного параметра визуальных характеристик используются <ключ КПВХ 1> 304, <ключ КПВХ 2> 306, <ключ КПВХ 3> 308 и <ключ КПВХ 4> 310, остальные композитные параметры визуальных характеристик могут быть сохранены в соответствующих списках словопозиций. В этих вариантах осуществления технологии остальные композитные параметры визуальных характеристик, сохраненные в соответствующих списках словопозиций, могут быть использованы в качестве дополнительного инструмента при выборе изображений-кандидатов из списка изображений, сохраненных в данном списке словопозиций (будет подробнее описано ниже).

Другими словами, суммируя, <ключ КПВХ 1> 304, <ключ КПВХ 2> 306, <ключ КПВХ 3> 308 и <ключ КПВХ 4> 310 могут быть реализованы в виде, по меньшей мере, части композитного параметра визуальных характеристик. В качестве примера, по меньшей мере, часть композитного параметра визуальных характеристик может представлять собой:

- пару визуальных слов

- по меньшей мере, два визуальных слова;

- по меньшей мере, два визуальных слова и связанный квантованный параметр пространственного соотношения;

- по меньшей мере, два визуальных слова и связанный квантованный параметр визуального соотношения;

- по меньшей мере, два визуальных слова и комбинацию из: (i) связанного квантованного параметра пространственного соотношения и (ii) связанного квантованного параметра визуального соотношения.

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

Специалисты в данной области техники оценят тот факт, что чем большая часть композитного параметра визуальных характеристик будет использоваться для <ключ КПВХ 1> 304, <ключ КПВХ 2> 306, <ключ КПВХ 3> 308 и <ключ КПВХ 4> 310, тем более дискриминационными будут <ключ КПВХ 1> 304, <ключ КПВХ 2> 306, <ключ КПВХ 3> 308 и <ключ КПВХ 4> 310. Аналогично, чем более дискриминационными будут являться <ключ КПВХ 1> 304, <ключ КПВХ 2> 306, <ключ КПВХ 3> 308 и <ключ КПВХ 4> 310, тем короче будут связанные списки словопозиций. Чем короче список словопозиций, тем эффективней будет поиск по спискам словопозиций (описано ниже). Поэтому специалисты в данной области техники, обладающие преимуществом от прочтения описания настоящей технологии, будут способны выбрать необходимый вариант осуществления <ключа КПВХ 1> 304, <ключа КПВХ 2> 306, <ключа КПВХ 3> 308 и <ключа КПВХ 4> 310 на основе конкретных требований к эффективности поиска по спискам вхождений.

Сервер 116 также может быть выполнен с возможностью производить поиск на основе индекса 300. Следует отметить, что упомянутый поиск может быть выполнен с помощью приложения 120 для управления изображениями или другим модулем или процедурой, выполняемой сервером 116. Также следует отметить, что сервер 116 может выполнять поиск от имени другого элемента, например, поисковой системы. Кроме того, отдельный элемент (например, поисковая система) может использовать индекс 300 для выполнения поиска, как будет описано ниже.

Используя в качестве примера Фиг. 2, целью выполняемых поисков является определение того, какие из изображений - первое подходящее изображение 220, второе подходящее изображение 222 и третье подходящее изображение 224 - идентичны или наиболее похожи на изображение 202. Другой целью может быть ранжирование первого соответствующего изображения 220, второго соответствующего изображения 222 и третьего соответствующего изображения 224 на основе степени похожести на изображения 202.

В некоторых вариантах осуществления сервер 116 выполняет мульти-этапный поиск. В общем случае, все еще опираясь в качестве примера на Фиг. 2, первая стадия реализована в виде выбора кандидатов, т.е. выбора конкретных изображений из первого соответствующего изображения 220, второго соответствующего изображения 222 и третьего соответствующего изображения 224 на основе степени их соответствия изображению 202 из изображений 202, 206, 208, 210, 212, 214, 216 (первое соответствующее изображение 220, второе соответствующее изображение 222 и третье соответствующее изображение 224 были выбраны как кандидаты на основе степени совпадения их композитных параметров визуальных характеристик тому же параметру изображения 202).

На второй стадии (i) конкретное(ые) изображение(я) из: первого соответствующего изображения 220, второго соответствующего изображения 222 и третьего соответствующего изображения 224 на основе степени его похожести на изображение 202 выбирается(ются) в качестве подходящих искомому изображению.

Для целей настоящего описания предполагается, что пользователь желает произвести поиск, используя изображение 402, представленное на Фиг. 4, как поисковый запрос.

Также следует иметь в виду, что хранилище 118 содержит множество изображений 404, множество изображений включает в себя подгруппу выбранных изображений 406, которая включает в себя первое изображение 408, второе изображение 410, третье изображение 412, четвертое изображение 414, пятое изображение 416, шестое изображение 418 и седьмое изображение 420.

Сначала сервер 116 анализирует изображение 402. В соответствии с вариантами осуществления настоящей технологии, сервер 116 анализирует изображение 402 способом, аналогичным тому, который был описан выше в связи с изображением 202. Поэтому сервер 116 может определить один или несколько композитных параметров визуальных характеристик, связанных с изображением 402. Композитные параметры визуальных характеристик, связанные с изображением 402, будут обозначены как "композитные параметры визуальных характеристик искомого изображения".

Стадия 1 - выбор кандидата

На первой стадии сервер 116 может выполнить выбор кандидата с использованием индекса 300. Конкретнее, сервер 116 получает доступ к индексу 300 для того, чтобы определить, какие из проиндексированных и сохраненных сообщений связаны с композитным параметром визуальных характеристик, который соответствует композитному параметру визуальных характеристик искомого изображения. Эти изображения будут обозначены как "изображения-кандидаты".

В некоторых вариантах осуществления сервер получает доступ к индексу 300 для того, чтобы извлечь изображения-кандидаты на основе, по меньшей мере, двух композитных параметров визуальных характеристик. В практическом плане и с использованием Фиг. 4 в качестве примера, сервер определяет подгруппу 406 выбранных изображений из множества 404 изображений на основе соответствия, по меньшей мере, двух композитных параметров визуальных характеристик.

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

Конкретнее, сервер 116 может использовать композитный параметр визуальных характеристик изображения 402 для сравнения его с композитным параметром визуальных характеристик каждого из подгруппы 406 выбранных изображений. Чем выше число соответствующих композитных параметров визуальных характеристик изображения 402, которые совпадают с композитным параметром визуальных характеристик рассматриваемого изображения из подгруппы 406 выбранных изображений, тем более высокий ранг может быть назначен рассматриваемому изображению из подгруппы 406 выбранных изображений.

Исключительно для иллюстрации этого этапа предполагается, что сервер 116 определил, что композитный параметр визуальных характеристик искомого изображения является <ключ КПВХ 1>. Сервер 116 может затем получить доступ к индексу 300 и определить, что изображениями-кандидатами, соответствующими композитному параметру визуальных характеристик искомого изображения, являются изображение 212 и изображение 214 (т.е. изображения, хранящиеся в списке словопозиций, связанном с изображения является <ключ КПВХ 1>.

Следовательно, используя данный пример, сервер 116 получает доступ к индексу 300 и определяет, что подгруппа 406 выбранных изображений включает в себя первое изображение 408, второе изображение 410, третье изображение 412, четвертое изображение 414, пятое изображение 416 и шестое изображение 418. Как можно видеть на Фиг. 4, первое изображение 408, второе изображение 410, третье изображение 412, четвертое изображение 414, пятое изображение 416 и шестое изображение 418 являются "почти идентичными" копиями изображения 402. Почти идентичные - значит, похожие, но не одинаковые. Почти идентичные изображения, конечно, могут включать в себя изображения, полностью совпадающие с искомым изображением. Например, изображение 408 является частично кадрированной версией изображения 402. Изображение 410 является размытой версией изображения 402. Изображение 414 является версией изображения 402 с низким разрешением. Изображение 412 является другой версией изображения 402 с низким разрешением, на изображении 412 много "шумов". Изображение 416 представляет собой изображение, в которое изображение 402 включено в виде его части. Изображение 418 является версией изображения 402, причем у изображения 418 и изображения 402 есть общая часть. Изображение 420 содержит часть изображения 402, снятую с другого ракурса или, другими словами, обладающую другим 3D-ракурсом.

Причины, по которым подгруппа 406 выбранных изображений является почти идентичными (или одинаковыми) по отношению к изображению 402, должны быть ясны. Возвращаясь к тому факту, что выбор кандидатов выполняется с использованием индекса 300, и тому факту, что индекс 300 был создан, по меньшей мере, частично, с помощью композитного параметра визуальных характеристик в качестве ключа, для того, чтобы данное изображение "попало в" подгруппу 406 выбранных изображений, ему необходимо обладать по меньшей мере одним композитным параметром визуальных характеристик.

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

В некоторых вариантах осуществления настоящей технологии, на стадии 1 сервер 116 проверяет все записи в индексе 300. В других вариантах осуществления технологии сервер 116 может выполнять стадию 1 с помощью выбранных записей в индексе 300. Например, сервер 116 может определять, что часть искомого изображения 402 связана с некоторыми из <ключ КПВХ 1> 304, <ключ КПВХ 2> 306, <ключ КПВХ 3> 308 и <ключ КПВХ 4> 310. Сервер 116 дополнительно может определять, что одна подгруппа некоторых из <ключ КПВХ 1> 304, <ключ КПВХ 2> 306, <ключ КПВХ 3> 308 и <ключ КПВХ 4> 310 является более дискриминационной по сравнению с другой подругой некоторых из <ключ КПВХ 1> 304, <ключ КПВХ 2> 306, <ключ КПВХ 3> 308 и <ключ КПВХ 4> 310. Определение более дискриминационной подгруппы из <ключ КПВХ 1> 304, <ключ КПВХ 2> 306, <ключ КПВХ 3> 308 и <ключ КПВХ 4> 310 может быть осуществлено, например, на основе частотности каждого из <ключ КПВХ 1> 304, <ключ КПВХ 2> 306, <ключ КПВХ 3> 308 и <ключ КПВХ 4> 310. В рамках этих вариантов осуществления технологии, сервер 116 может выполнять стадию 1 на основе более дискриминационной подгруппы из <ключ КПВХ 1> 304, <ключ КПВХ 2> 306, <ключ КПВХ 3> 308 и <ключ КПВХ 4> 310. Конкретный технический эффект от этих вариантов осуществления технологии включает в себя повышение эффективности процесса выбора кандидатов.

Стадия 2 - проверка и ранжирование

Далее на стадии 2 сервер 116 выполняет проверку и ранжирование (или вторичное ранжирование изображений-кандидатов, которые были опционально ранжированы на стадии 1, как описано выше) изображений из подгруппы 406 выбранных изображений.

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

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

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

Для выполнения геометрической проверки может быть использовано несколько алгоритмов. В некоторых вариантах осуществления настоящей технологии сервер 116 использует алгоритм RANSAC. В других случаях сервер 116 может использовать алгоритм "Кластеризация с преобразованием Хафа".

Используя результаты геометрической проверки, сервер 116 ранжирует (или вторично ранжирует изображения-кандидаты, которые были опционально ранжированы на стадии 1, как описано выше) эти изображения-кандидаты из подгруппы 406 выбранных изображений, которые были проверены как изображения-кандидаты с помощью геометрической проверки. Конкретнее, сервер 116 может использовать в качестве индикатора для ранжирования ряд локальных характеристик, постоянно находящихся между изображением 402 и изображениями-кандидатами из подгруппы 406 выбранных изображений.

Дополнительно или альтернативно может выполняться этап проверки миниатюр. Другими словами, сервер 116 может дополнительно или альтернативно проверять данные выбранные кандидаты из подгруппы 406 выбранных изображений по отношению к изображению 402 с помощью соответствующих миниатюр данных выбранных кандидатов из подгруппы 406 выбранных изображений и изображения 402. В некоторых вариантах осуществления технологии проверка миниатюр выполняется в режиме сравнения "попиксельно". В некоторых вариантах осуществления технологии сервер 116 может дополнительно использовать пространственную информацию от соответствующих областей данных выбранных кандидатов из подгруппы 406 выбранных изображений и изображения 402.

При использовании описанных подходов сервер 116 может определять, что одно из изображений - пятое изображение 416 или шестое изображение 418 - наиболее соответствует искомому изображению 402. Как вариант, сервер 116 может определять, что оба изображения - пятое изображение 416 и шестое изображение 418 соответствуют искомому изображению, и предоставляет их пользователю в порядке, ранжированном в соответствии с их релевантностью для искомого изображения 402. Дополнительно сервер 116 может представлять в виде ранжированного списка другие изображения из подгруппы 406 выбранных изображений, даже если они менее релевантны.

В некоторых вариантах осуществления настоящей технологии некоторые процессы стадии 1 и/или стадии 2 могут выполняться "в автономном режиме", то есть выполняться до того, как пользователь попытается выполнить поиск по конкретному изображению. В других вариантах осуществления настоящей технологии некоторые шаги стадии 2 могут быть выполнены в автономном режиме для того, чтобы сократить длину списков словопозиций, созданных на стадии 2. Например, сервер 116 может анализировать изображение, содержащееся в списках словопозиций, и определять почти идентичные ему изображения. Сервер 116 может далее выбирать соответствующее изображение из каждой группы почти идентичных изображений и сохранять в списках словопозиций индекса 300 только указание на соответствующее изображение из каждой группы почти идентичных изображений. Естественно, полный список почти идентичных изображений для каждого из соответствующих изображений может быть сохранен в отдельной базе данных и получен позднее. Создавая эту необязательную репрезентативную выборку, сервер 116 может еще сильнее сократить время, необходимое для выбора кандидатов при выполнении стадии 1 в режиме он-лайн, или, другими словами, когда пользователь выполняет поиск по изображению с помощью сервера 116.

Соответственно, данные варианты осуществления настоящей технологии позволяют выполнять способ обработки изображения, позволяющий индексировать и сравнивать изображение с другими изображениями. На Фиг. 5 представлена блок-схема этапов способа 500. Способ 500 может выполняться на сервере 116. Для этого сервер 116 включает постоянный носитель компьютерной информации, хранящий компьютерные инструкции, при выполнении которых сервер 116 выполняет этапы способа 500.

Этап 502 - идентификация первой локальной области изображения и второй локальной области изображения

Способ 500 начинается на этапе 502, на котором сервер 116 идентифицирует первую локальную область изображения и вторую локальную область изображения.

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

Способ 500 далее переходит к выполнению этапа 504.

Этап 504 - определение первого визуального слова, связанного с первой локальной областью изображения, и второго визуального слова, связанного со второй локальной областью изображения

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

Способ 500 далее переходит к выполнению этапа 506.

Этап 506 - определение композитного параметра визуальных характеристик, связанного с изображением, композитный параметр визуальных характеристик содержит первое визуальное слово и второе визуальное слово

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

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

Выполнение способа 500 затем может быть завершено или повторено для другого изображения.

В других не ограничивающих вариантах осуществления технологии может быть выполнен способ создания индекса изображений, причем индекс изображений позволяет сравнивать изображения друг с другом. На Фиг. 6 представлена блок-схема этапов способа 600. Способ 600 может выполняться на сервере 116. Таким образом, сервер 116 может включать в себя машиночитаемый носитель, хранящий машиночитаемые инструкции, которые при их выполнении сервером 116 исполняют этапы способа 600.

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

В рамках вариантов осуществления способа 600 на этапе 602 сервер 116 определяет, по меньшей мере, один ключ для индекса, причем, по меньшей мере, один ключ включает в себя часть композитного параметра визуальных характеристик, связанного с изображением, которое необходимо проиндексировать. В рамках способа 600 композитный параметр визуальных характеристик был определен при выполнении следующих этапов: идентификация первой локальной области изображения и второй локальной области изображения; определение первого визуального слова, связанного с первой локальной областью изображения, и второго визуального слова, связанного со второй областью изображения; определение композитного параметра визуальных характеристик, связанного с изображением, причем композитный параметр визуальных характеристик содержит первое визуальное слово и второе визуальное слово.

Затем способ 600 переходит к выполнению этапа 604.

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

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

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

В других не ограничивающих вариантах осуществления технологии может быть выполнен способ нахождения подходящего изображения из хранилища изображений, которое содержит множество изображений. На Фиг. 7 представлена блок-схема этапов способа 700. Способ 700 может выполняться на сервере 116. Для этого сервер 116 содержит постоянный носитель компьютерной информации, хранящий компьютерные инструкции, при выполнении которых сервер 116 выполняет этапы способа 700.

Этап 702 - получение индикации изображения

Способ 700 начинается с выполнения этапа 702, на котором сервер 116 получает индикацию искомого изображения. В рамках вариантов осуществления настоящей технологии сервер 116 может оценивать искомое изображение посредством выполнения пользователем поиска по изображению и загрузки искомого изображения, например, в интерфейс поисковой системы.

Затем способ 700 переходит к выполнению этапа 704.

Этап 704 - определение композитного параметра визуальных характеристик, связанного с искомым изображением

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

Затем способ 700 переходит к выполнению этапа 706.

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

Далее, на этапе 706 сервер 116 проводит многостадийный поиск, включающий следующие этапы: выбор изображений-кандидатов из множества изображений, причем выбор осуществляется с помощью получения доступа к индексу, который коррелирует с данным композитным параметром визуальных характеристик для изображений, содержащихся в рамках множества изображений, и который соответствует параметру изображений, содержащихся в рамках множества изображений; проверка изображений по отношению к искомому изображению по одному с использованием соответствующих локальных дескрипторов.

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

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

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

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

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

2. Способ по п. 1, в котором композитный параметр визуальных характеристик дополнительно включает информацию о соотношении.

3. Способ по п. 2, в котором информация о соотношении содержит информацию о пространственном соотношении между первой локальной областью и второй локальной областью.

4. Способ по п. 2, в котором упомянутая информация о соотношении содержит информацию о визуальном соотношении, связанную с по меньшей мере одним из следующего: (i) первой локальной областью и второй локальной областью, (ii) другими областями изображения; (iii) изображением в целом.

5. Способ по п. 4, в котором информация о визуальном соотношении включает по меньшей мере одно из следующего: соответствующее соотношение масштабов, соответствующее соотношение цвета и соответствующее соотношение контраста.

6. Способ по п. 2, в котором упомянутая информация о соотношении содержит по меньшей мере одно из следующего: (i) информацию о пространственном соотношении между первой локальной областью и второй локальной областью, (ii) информацию о визуальном соотношении между первой локальной областью и второй локальной областью; (iii) пространственную информацию, связанную с другими областями изображения; (iv) визуальную информацию, связанную с другими областями изображения.

7. Способ по п. 1, дополнительно включающий получение изображения через сеть передачи данных.

8. Способ по п. 1, в котором упомянутая идентификация выполняется на случайной основе.

9. Способ по п. 1, в котором упомянутая идентификация выполняется по заранее определенному алгоритму.

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

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

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

13. Способ по п. 12, в котором упомянутая часть включает первое визуальное слово и второе визуальное слово.

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

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

16. Способ по п. 12, в котором упомянутая часть включает первое визуальное слово и второе визуальное слово и сочетание: (i) квантованного параметра пространственного соотношения между первой областью и второй областью и (ii) квантованного параметра визуального соотношения между первой областью и второй областью.

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

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

19. Способ по п. 12, дополнительно включающий в себя сохранение остальной части композитного параметра визуальных характеристик в списке словопозиций.

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

21. Способ по п. 20, в котором упомянутые композитные параметры визуальных характеристик искомого изображения содержат первое визуальное слово, связанное с первой областью искомого изображения, и второе визуальное слово, связанное со второй областью искомого изображения.

22. Способ по п. 20, в котором упомянутый композитный параметр визуальных характеристик искомого изображения дополнительно содержит информацию о соотношении между первой локальной областью и второй локальной областью.

23. Способ по п. 22, в котором информация о соотношении содержит информацию о пространственном соотношении между первой локальной областью и второй локальной областью.

24. Способ по п. 22, в котором упомянутая информация о соотношении содержит информацию о визуальном соотношении, связанную с по меньшей мере одним из следующего: (i) первой локальной областью и второй локальной областью, (ii) другими областями изображения; (iii) изображением в целом.

25. Способ по п. 24, в котором информация о визуальном соотношении включает по меньшей мере одно из следующего: соответствующее соотношение масштабов, соответствующее соотношение цвета и соответствующее соотношение контраста.

26. Способ по п. 22, в котором упомянутая информация о соотношении содержит по меньшей мере одно из следующего: (i) информацию о пространственном соотношении между первой локальной областью и второй локальной областью, (ii) информацию о визуальном соотношении между первой локальной областью и второй локальной областью; (iii) пространственную информацию, связанную с другими областями изображения; (iv) визуальную информацию, связанную с другими областями изображения.

27. Способ по п. 20, в котором соответствующий композитный параметр визуальных характеристик, связанный с соответствующим параметром изображений, содержит первое визуальное слово, связанное с первой областью искомого изображения, и второе визуальное слово, связанное со второй областью искомого изображения.

28. Способ по п. 27, в котором соответствующий композитный параметр визуальных характеристик искомого изображения дополнительно содержит информацию о соотношении между первой локальной областью и второй локальной областью.

29. Способ по п. 28, в котором информация о соотношении содержит информацию о пространственном соотношении между первой локальной областью и второй локальной областью.

30. Способ по п. 28, в котором информация о соотношении содержит визуальную информацию между первой локальной областью и второй локальной областью.

31. Способ по п. 30, в котором информация о визуальном соотношении включает по меньшей мере одно из следующего: соответствующее соотношение масштабов, соответствующее соотношение цвета и соответствующее соотношение контраста.

32. Способ по п. 28, в котором упомянутая информация о соотношении содержит по меньшей мере одно из следующего: (i) информацию о пространственном соотношении между первой локальной областью и второй локальной областью и (ii) информацию о визуальном соотношении между первой локальной областью и второй локальной областью.

33. Способ по п. 20, дополнительно включающий до упомянутого этапа получения, заполнение индекса с использованием композитного параметра визуальных характеристик изображения.

34. Сервер, включающий постоянный машиночитаемый носитель, хранящий машиночитаемые инструкции, при выполнении которых сервер выполняет обработку изображения, позволяющую индексировать и сравнивать изображение с другими изображениями, согласно способу по любому из пп. 1-11.

35. Сервер, включающий постоянный машиночитаемый носитель, хранящий машиночитаемые инструкции, при выполнении которых сервер выполняет создание индекса изображений, позволяющий сравнивать изображение с другими изображениями, согласно способу по любому из пп. 12-19.

36. Сервер, включающий постоянный машиночитаемый носитель, хранящий машиночитаемые инструкции, при выполнении которых сервер обнаруживает соответствия изображению из хранилища изображений, содержащего множество изображений, согласно способу по любому из пп. 20-32.