ВЫЯВЛЕНИЕ "НЕЧЕТКИХ" ДУБЛИКАТОВ ИЗОБРАЖЕНИЙ С ПОМОЩЬЮ ТРОЕК СМЕЖНЫХ ОЦЕНЕННЫХ ПРИЗНАКОВ Российский патент 2017 года по МПК G06T7/00 G06K9/46 G06K9/52 G06K9/72 

ОБЛАСТЬ ТЕХНИКИ

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

УРОВЕНЬ ТЕХНИКИ

[0002] Проблема выявления «нечетких» дубликатов изображений может возникнуть в ряде областей. Количество изображений, которые могут храниться в обычной масштабной системе извлечения изображений, накладывает существенные ограничения на производительность в связи со способами выявления «нечетких» дубликатов изображений.

РАСКРЫТИЕ ИЗОБРЕТЕНИЯ

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

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

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

[0006] Настоящее изобретение иллюстрируется с помощью примеров, а не способом ограничения, и может быть лучше понято при рассмотрении приведенного ниже описания предпочтительных вариантов реализации в сочетании с чертежами, на которых:

[0007] На Фиг. 1 схематически иллюстрируется пример тройки смежных оцененных признаков (TARF) в соответствии с одним или более аспектами настоящего изобретения;

[0008] На Фиг. 2 схематически иллюстрируется пример записи индекса на основе дескриптора TARF, выявленного в заданном изображении, в соответствии с одним или более аспектами настоящего изобретения;

[0009] На Фиг. 3 схематически иллюстрируется блок-схема примера способа создания перечня дескрипторов TARF для заданного изображения в соответствии с одним или более аспектами настоящего изобретения;

[00010] На Фиг. 4 схематически иллюстрируется блок-схема примера способа создания записей индекса на основе TARF, выявленных в заданном изображении, в соответствии с одним или более аспектами настоящего изобретения;

[00011] На Фиг. 5 схематически иллюстрируется блок-схема примера способа выявления «нечетких» дубликатов изображений для заданного изображения-запроса в большой коллекции изображений в соответствии с одним или более аспектами настоящего изобретения; а также

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

ОПИСАНИЕ ПРЕДПОЧТИТЕЛЬНЫХ ВАРИАНТОВ РЕАЛИЗАЦИИ

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

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

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

[00016] Под особой точкой «пятно» (BLOB) далее понимается область изображения, имеющая отличающиеся от окружающих областей визуальные свойства, такие как яркость или цвет. Таким образом, определенные визуальные свойства являются постоянными или приблизительно постоянными для пятна, а все точки внутри пятна могут считаться аналогичными с точки зрения этих свойств.

[00017] Пятна (BLOB) могут быть выявлены в заданном изображении с помощью различных методов, например с помощью дескриптора SIFT (трансформация признака с инвариантным масштабом), который подразумевает определение ключевых областей с помощью функции разности гауссианов, при этом выполняется применение детальной модели для расположения каждого кандидата с целью определения расположения и масштаба, выбор особых точек на основе измерений их стабильности, присвоение одного или более направлений для каждой особой точки и создание дескрипторов особой точки путем измерения локальных градиентов изображения с выбранным масштабом в области вокруг каждой особой точки. Прочие методы выявления свойств точки типа BLOB включают детекторы SURF (ускоренные надежные признаки) и MSER (краевые максимально стабильные области).

[00018] Под особой точкой «угол» (CORNER) далее понимается область изображения, представляющая собой пересечение двух или более граней. Таким образом, вокруг особой точки CORNER могут быть обнаружены два или более различных доминирующих направления граней.

[00019] Углы (CORNER) могут быть выявлены в заданном изображении различными методами, например с помощью детектора BRISK (двоичные надежные инвариантные масштабируемые особые точки), который подразумевает выявление точек-кандидатов в изображении и размеры масштаба на основе критерия отличительных особенностей, а также создание дескрипторов основной точки, представленных двоичными строками, которые строятся за счет объединения результатов сравнительной проверки яркости в характерных направлениях для каждой особой точки.

[00020] В соответствии с одним или более аспектами настоящего изобретения на изображении может быть выявлен один или более TARF путем выявления одной или более особых точек типа «пятно» (BLOB) с последующим выявлением расположенных рядом угловых точек (CORNER) для каждой особой точки типа BLOB. На Фиг. 1 схематически представлен дескриптор TARF 100, включающий особую точку BLOB 110 с центром в точке О и две особые точки CORNER 120А-120В, центры которых расположены в точках C₁ и С₂ соответственно. Векторы C₁C₁' и С₂С₂' схематически показывают выявленные направления точек CORNER 120А-120В, соответственно. В различных иллюстративных примерах направление точки может быть представлено градиентом цвета, яркостью или другим визуальным свойством, связанным с особой точкой.

[00021] При этом нумерация всех возможных троек может привести к образованию большого количества комбинаций, большинство из которых не будет хорошо воспроизводиться, поскольку все три особые точки дескриптора TARF не обязательно будут представлены в изображении-дубликате. Таким образом, среди всех троек-кандидатов необходимо выбирать только тройки, имеющие большую вероятность воспроизведения в изображении-дубликате. Процесс выбора может быть основан на рейтинге (score) особых точек CORNER, который создается детектором особой точки CORNER и изменяется с учетом положений особых точек CORNER относительно особой точки BLOB. В иллюстративном примере измененный рейтинг может рассчитываться следующим образом

[00022]

[00023] где R_c - радиус особой точки CORNER, d - расстояние между центрами точек CORNER и BLOB, a S и S* - исходный и измененный рейтинг точек CORNER, соответственно.

[00024] Параметры d₀, σ_d, R₀ и σ_R могут быть определены и (или) изменены на основе экспериментальных данных. В иллюстративных примерах перечисленные выше параметры могут быть определены следующим образом:

[00025] d₀=0,5R_b, σ_d=0,15R_b, R₀=0,33R_b, и σ_R=0,15R_b,

[00026] где R_b - радиус особой точки BLOB.

[00027] В соответствии с одним или более аспектами настоящего изобретения измененный рейтинг может быть рассчитан по представленной выше формуле (1) для множества особых точек CORNER, расположенных рядом с каждой выявленной особой точкой BLOB. Для каждой выявленной особой точки BLOB может выбираться заданное число (например, n*=7) верхних точек CORNER, имеющих самый высокий рейтинг.

[00028] Затем может быть определен общий пороговый рейтинг S₀* для рейтингов особых точек CORNER, при этом создается N₀ троек путем выбора всех особых точек CORNER, измененный рейтинг S* которых не превышает общий пороговый рейтинг S₀*, т.е. рейтинг точек CORNER должен быть S*<S₀*:

[00029]

[00030] где сумма рассчитывается для всех выявленных особых точек BLOB, n_i - количество особых точек CORNER рядом с i-й особой точкой BLOB с измененным рейтингом S* ниже общего порогового рейтинга S₀*, a N₀ - параметр способа, которому в иллюстративном примере могут быть присвоены значения в диапазоне 2500…3000.

[00031] Для каждой особой точки BLOB может быть создан перечень из n_i<=n* верхних точек CORNER (т.е., точек CORNER, имеющих самый высокий измененный рейтинг). Могут быть выявлены различные сочетания точки BLOB и двух различных точек CORNER из соответствующего перечня верхних точек CORNER и добавлены в перечень TARF, связанных с заданным изображением.

[00032] Как указано выше, большая коллекция изображений может быть проиндексирована на основе геометрических свойств дескрипторов TARF, выявленных в каждом изображении. В определенных вариантах реализации для каждого дескриптора TARF, связанного с заданным изображением, могут быть определены три локальных дескриптора (d_b, d_c1, d_c2) в трех особых точках, составляющих TARF. В различных иллюстративных примерах могут использоваться различные дескрипторы, например три дескриптора BRISK, или дескриптор SIFT в особой точке BLOB и дескрипторы BRISK в двух точках CORNER.

[00033] Для каждого из трех дескрипторов может быть создано визуальное слово. В иллюстративном примере для обнаружения кластеров в пространстве дескрипторов может быть применен метод K-means, дескриптор может быть связан с одним из трех кластеров, а визуальное слово может быть получено из идентификатора кластера. В другом варианте реализации может быть реализован другой способ создания визуальных слов из дескрипторов. В определенных вариантах реализации три визуальных слова могут объединяться для создания единого целого числа.

[00034] Помимо визуальных слов каждый TARF может дополнительно характеризоваться определенными геометрическими свойствами. На Фиг. 1 геометрические свойства, которые могут быть определены для дальнейшего определения характеристик каждого TARF, могут включать:

[00035] угол α между векторами OC₁ и ОС₂;

[00036] угол β₁ между векторами OC₁ и C₁C'₁;

[00037] угол β₂ между векторами ОС₂ и С₂С'₂;

[00038] отношение ε₁ расстояния к расстоянию ;

[00039] отношение ε₂ расстояния к радиусу R_b особой точки BLOB; и (или)

[00040] отношение ε₃ расстояния к радиусу R_b особой точки BLOB, где С'' - средняя точка сегмента .

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

[00042] Для каждого изображения из коллекции изображений может быть создано множество записей индекса на основе TARF, выявленных в изображении. Каждая запись индекса может включать идентификатор изображения (например, название содержащего изображение файла), визуальные слова, полученные из трех локальных дескрипторов, связанных с TARF, и одно или более геометрических свойств, связанных с TARF. В примере, схематически представленном на Фиг. 2, запись индекса 200 содержит визуальные слова 210, идентификатор изображения 220, координаты центра TARF 230 и геометрические свойства 240.

[00043] В соответствии с одним или более аспектами настоящего изобретения индекс на основе TARF может использоваться для выявления «нечетких» дубликатов изображений заданного изображения-запроса в большой коллекции изображений. Может быть создан перечень дескрипторов TARF, связанных с изображением-запросом, что более подробно описано выше. Для каждого TARF изображения-запроса могут быть созданы соответствующие визуальные слова и геометрические свойства, что более подробно описано выше.

[00044] Может использоваться индекс на основе TARF для коллекции изображений для выявления в коллекции изображений кандидатов, у которых, по меньшей мере, один TARF соответствует дескриптору TARF из множества TARF, связанных с изображением-запросом. Два TARF считаются совпадающими, если их визуальные слова являются идентичными и их геометрические свойства аналогичны (например, отличия между соответствующими геометрическими свойствами попадают в соответствующие заданные пределы).

[00045] В определенных вариантах реализации выявленные изображения-кандидаты, имеющие обратную частоту документа (IDF) ниже определенного порога, могут не приниматься во внимание. Балл IDF изображения-кандидата может быть определен как сумма баллов IDF для TARF, соответствующих изображению-запросу. Балл IDF для TARF может быть определен как сумма баллов IDF для визуальных слов, связанных с TARF. Балл IDF визуального слова является логарифмически масштабируемой долей изображений, содержащих визуальное слово.

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

[00047] Примеры указанных выше методов описываются ниже со ссылками на блок-схемы на Фиг. 3-5.

[00048] На Фиг. 3 показана схема примера способа 300 создания перечня дескрипторов TARF для заданного изображении в соответствии с одним или более аспектами настоящего изобретения. Способ 300 и (или) каждая из его отдельных функций, стандартных программ, подпрограмм или операций может выполняться одним или более обрабатывающими устройствами общего и (или) особого назначения. Две или более функций, стандартных программ, подпрограмм или операций способа 300 могут выполняться параллельно или в порядке, который может отличаться от указанного выше. В некоторых вариантах реализации способ 300 может выполняться в одном потоке обработки. В качестве альтернативы, способ 300 может выполняться с использованием двух и более потоков обработки, при этом каждый поток выполняет одну или более отдельных функций, стандартных программ, подпрограмм или операций способа. В иллюстрирующем примере потоки обработки, реализующие способ 300, могут быть синхронизированы (например, с помощью семафоров, критических секций и (или) других механизмов синхронизации потоков). В качестве альтернативы, потоки обработки, реализующие способ 300, могут выполняться асинхронно по отношению друг к другу. В иллюстративном примере способ 300 может выполняться вычислительным устройством 1000, описанным ниже со ссылкой на Фиг. 6.

[00049] В блоке 310 обрабатывающее устройство, реализующее способ, может выявлять множество особых точек BLOB для заданного изображения. Как указано выше, особые точки BLOB могут быть выявлены различными способами, например, с помощью детекторов SIFT (трансформация признака с инвариантным масштабом), SURF (ускоренные надежные признаки) и MSER (краевые максимально стабильные области). Для каждой выявленной особой точки обрабатывающее устройство может выявить радиус особой точки.

[00050] В блоке 320 обрабатывающее устройство может выявлять множество особых точек CORNER изображения. Как указано выше, особые точки CORNER могут быть выявлены различными способами, например, с помощью детектора BRISK (двоичные надежные инвариантные масштабируемые особые точки). Для каждой выявленной особой точки обрабатывающее устройство может выявить радиус особой точки.

[00051] В блоках 330-370 обрабатывающее устройство может пронумеровать множество группировок выявленных особых точек с выявлением TARF, при этом каждый TARF включает одну особую точку BLOB и две расположенные рядом особые точки CORNER.

[00052] В блоке 330 обрабатывающее устройство может выявить множество расположенных рядом особых точек CORNER для каждой выявленной особой точки BLOB. В определенных вариантах реализации обрабатывающее устройство может выявить множество особых точек CORNER, расположенных в определенной близости от особой точки BLOB.

[00053] В блоке 340 обрабатывающее устройство может выявить заданное количество особых точек CORNER с самым высоким значением измененного рейтинга для каждой выявленной особой точки BLOB. В иллюстративном примере измененный рейтинг особой точки CORNER может быть определен с помощью представленной выше формулы (1).

[00054] В блоке 350 обрабатывающим устройством может быть определен общий пороговый рейтинг S₀* для рейтингов особых точек CORNER, при этом создается No троек путем выбора всех особых точек CORNER, измененный рейтинг S* которых не превышает общий пороговый рейтинг S₀*, т.е. рейтинг точек CORNER должен быть S*<S₀*, где N₀ определяется по представленной выше формуле (3).

[00055] В блоке 360 обрабатывающим устройством может быть создан перечень из n_i<=n* верхних точек CORNER (т.е. точек CORNER, имеющих самый высокий измененный рейтинг) для каждой особой точки BLOB, где n_i - количество особых точек CORNER рядом с i-й особой точкой BLOB с измененным рейтингом S* ниже общего порогового рейтинга S₀*.

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

[00057] На Фиг. 4 представлена схема примера способа 400 создания записей индекса на основе TARF, выявленных в заданном изображении, в соответствии с одним или более аспектами настоящего изобретения. Способ 400 и (или) каждая из его отдельных функций, стандартных программ, подпрограмм или операций может выполняться одним или более обрабатывающими устройствами общего и (или) особого назначения. Две или более функций, стандартных программ, подпрограмм или операций способа 400 могут выполняться параллельно или в порядке, который может отличаться от указанного выше. В некоторых вариантах реализации способ 400 может выполняться в одном потоке обработки. В качестве альтернативы, способ 400 может выполняться с использованием двух и более потоков обработки, при этом каждый поток выполняет одну или более отдельных функций, стандартных программ, подпрограмм или операций способа. В иллюстрирующем примере потоки обработки, реализующие способ 400, могут быть синхронизированы (например, с помощью семафоров, критических секций и (или) других механизмов синхронизации потоков). В качестве альтернативы, потоки обработки, реализующие способ 400, могут выполняться асинхронно по отношению друг к другу. В иллюстративном примере способ 400 может выполняться вычислительным устройством 1000, описанным ниже со ссылкой на Фиг. 6.

[00058] В блоке 410 обрабатывающим устройством, реализующим способ, для каждого дескриптора TARF, связанного с заданным изображением, могут быть определены три локальные дескриптора (d_b, d_c1, d_c2) в трех особых точках, составляющих TARF, что детально описано выше.

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

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

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

[00062] На Фиг. 5 представлена блок-схема примера способа 500 выявления «нечетких» дубликатов изображений для заданного изображения-запроса в большой коллекции изображений в соответствии с одним или более аспектами настоящего изобретения.

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

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

[00064] В блоке 520 обрабатывающее устройство может выявить визуальные слова и геометрические свойства, связанные с изображением-запросом, например, путем применения описанного выше примера способа 400.

[00065] В блоке 530 обрабатывающим устройством может использоваться индекс на основе TARF для коллекции изображений для выявления в коллекции изображений кандидатов, у которых, по меньшей мере, один TARF соответствует дескриптору TARF из множества TARF, связанных с изображением-запросом. Два TARF считаются совпадающими, если их визуальные слова являются идентичными и их геометрические свойства аналогичны (например, отличия между соответствующими геометрическими свойствами попадают в соответствующие заданные пределы), что более подробно описано выше.

[00066] В блоке (540) обрабатывающее устройство может отфильтровать выявленные изображения по баллам IDF. В иллюстративном примере выявленные изображения-кандидаты, имеющие балл IDF ниже определенного порога, могут быть отбракованы в соответствии с приведенным выше детальным описанием.

[00067] В блоке 550 обрабатывающее устройство может выполнить дополнительную фильтрацию выявленных изображений-кандидатов за счет применения геометрической модели преобразования изображения в соответствии с приведенным выше детальным описанием. Изображения-кандидаты, удовлетворяющие геометрической модели, могут быть названы «нечеткими» дубликатами изображения-запроса. После завершения описанных операций для блока 550 выполнение способа может завершиться.

[00068] На Фиг. 6 показано схематическое представление вычислительного устройства 1000, внутри которого имеется набор команд, который может заставить вычислительное устройство выполнить методы, описанные в данном документе. Вычислительное устройство 1000 может подключаться к другому вычислительному устройству по локальной сети, корпоративной сети, сети экстранет и (или) сети Интернет. Вычислительное устройство может работать в качестве сервера в сетевой среде клиент-сервер. Вычислительное устройство может быть представлено персональным компьютером (ПК), телевизионной приставкой (STB), сервером, сетевым маршрутизатором, коммутатором или мостом, или любым вычислительным устройством, способным выполнять набор команд (последовательно или иным образом), определяющих действия, которые должны быть выполнены этим вычислительным устройством. Кроме того, хотя показано только одно вычислительное устройство, термин «вычислительное устройство» также должен пониматься как включающий любую совокупность вычислительных устройств, которые отдельно или совместно выполняют один или более наборов команд для выполнения способов, описанных в настоящем документе.

[00069] Пример вычислительной системы 1000 может включать обрабатывающее устройство (например, процессор общего назначения) 1002, основную память 1004 (например, синхронную динамическую оперативную память (DRAM) или постоянное запоминающее устройство (ПЗУ)) и статическое запоминающее устройство 1006 (например, флэш-память и устройство хранения данных 1018), которые взаимодействуют друг с другом по шине 1030.

[00070] Обрабатывающее устройство 1002 может быть представлено одним или более универсальными устройствами обработки данных, например микропроцессором, центральным процессором и т.п. В иллюстративном примере обрабатывающее устройство 1002 может включать микропроцессор с полным набором команд (CISC), микропроцессор с сокращенным набором команд (RISC), микропроцессор с командными словами сверхбольшой длины (VLIW) или процессор, реализующий другой набор команд, или процессоры, реализующие комбинацию наборов команд. Обрабатывающее устройство 1002 также может включать одно или несколько обрабатывающих устройств специального назначения, таких как специализированная интегральная схема (ASIC), программируемая пользователем вентильная матрица (FPGA), процессор цифровых сигналов (DSP), сетевой процессор или т.п. Обрабатывающее устройство 1002 может быть настроено на исполнение модуля 1026 для выявления «нечетких» дубликатов изображений для заданного изображения-запроса путем реализации способов 300, 400 и (или) 500, в соответствии с одним или более аспектами настоящего изобретения с целью выполнения описанных операций и шагов.

[00071] Вычислительное устройство 1000 может дополнительно содержать устройство сетевого интерфейса 1008, взаимодействующее с сетью 1020. Вычислительное устройство 1000 также может содержать блок видео дисплея 1010 (например, жидкокристаллический дисплей (ЖК-дисплей) или электронно-лучевую трубку (ЭЛТ)), буквенно-цифровое устройство ввода 1012 (например, клавиатуру), устройство управления курсором 1014 (например, мышь) и устройство формирования звуковых сигналов 1016 (например, громкоговоритель). В одном из вариантов реализации изобретения блок видеодисплея 1010, буквенно-цифровое устройство ввода 1012 и устройство управления курсором 1014 могут быть объединены в один компонент или устройство (например, сенсорный экран ЖК-дисплея).

[00072] Устройство хранения данных 1018 может включать машиночитаемый носитель данных 1028, на котором может храниться один или более наборов команд, например команды модуля 1026 для выявления в большой коллекции изображений «нечетких» дубликатов изображений заданного изображения-запроса путем реализации способов 300, 400, и (или) 500, в соответствии с одним или более аспектами настоящего изобретения. Модуль реализации команд 1026 также может находиться полностью или по меньшей мере частично в основной памяти 1004 и (или) в обрабатывающем устройстве 1002 во время выполнения команд в вычислительном устройстве 1000, при этом оперативная память 1004 и обрабатывающее устройство 1002 также составляют машиночитаемый носитель данных. Команды также затем могут передаваться или приниматься по сети 1020 через устройство сетевого интерфейса 1008.

[00073] Хотя машиночитаемый носитель данных 1028 приведен в иллюстративном примере в виде одного носителя, термин «машиночитаемый носитель данных» также будет включать в себя один носитель или несколько носителей (например, централизованную или распределенную базу данных и (или) ассоциированную с ними кэш-память и серверы), которые содержат один или несколько наборов инструкций. Термин «машиночитаемый носитель данных» также может включать любой носитель, который может хранить, кодировать или содержать набор команд для выполнения машиной и который обеспечивает выполнение машиной методов настоящего изобретения. Соответственно, термин «машиночитаемый носитель данных» также включает, в частности, устройства твердотельной памяти, оптические и магнитные носители.

[00074] Если иное не указано, термины «обновление», «выявление», «определение», «отправка», «назначение» и т.п., относятся к действиям и процессам, выполняемым или реализуемым вычислительным устройством, которое работает с данными и преобразует данные, представленные в виде физических (электронных) величин в регистрах и памяти вычислительного устройства, в другие данные, аналогичным образом представленные в виде физических величин в памяти или регистрах вычислительного устройства, либо других подобных устройствах хранения, передачи или отображения информации. Помимо этого, термины «первый», «второй», «третий», «четвертый» и т.д., используемые в этом документе, используются в качестве меток для различения различных элементов и не обязательно имеют порядковое значение, соответствующее их цифровому обозначению.

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

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

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

Изобретение относится к технологиям выявления «нечетких» дубликатов изображений в большой коллекции изображений. Техническим результатом является повышение эффективности поиска и извлечения изображения из коллекции изображений. Предложен способ выявления нечетких дубликатов изображений. Способ содержит этап, на котором осуществляют выявление обрабатывающим устройством, на основании рейтинга особых точек CORNER, множества троек смежных оцененных признаков (TARF) для каждого из изображений-запросов, при этом каждый из TARF состоит из особой точки пятна (BLOB) и двух угловых особых точек (CORNER). Далее, согласно способу, выявляют с помощью записей индекса изображения из коллекции изображений, ассоциированного с, по меньшей мере, TARF из указанного множества, по меньшей мере, одного изображения-кандидата, которое содержит, по меньшей мере, один TARF, совпадающий с TARF из указанного множества TARF изображения-запроса. 3 н. и 19 з.п. ф-лы, 6 ил.

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

выявление обрабатывающим устройством, на основании рейтинга особых точек CORNER, множества троек смежных оцененных признаков (TARF) для каждого из изображений-запросов, при этом каждый из TARF состоит из особой точки пятна (BLOB) и двух угловых особых точек (CORNER);

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

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

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

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

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

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

6. Способ по п. 1, отличающийся тем, что выявление множества TARF для изображения-запроса дополнительно включает:

выявление множества особых точек BLOB в изображении-запросе;

выявление множества особых точек CORNER в изображении-запросе;

создание множества TARF, при этом каждый TARF включает особую точку BLOB из множества особых точек BLOB и две особые точки CORNER из множества особых точек CORNER.

7. Способ по п. 6, отличающийся тем, что создание множества TARF дополнительно включает:

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

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

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

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

11. Система выявления нечетких дубликатов изображения, содержащая:

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

процессор, оперативно связанный с данной памятью, причем этот процессор настроен на:

выявление, на основании рейтинга особых точек CORNER, множества троек смежных оцененных признаков (TARF) для каждого из изображений-запросов изображением-запросом, при этом каждый из TARF состоит из особой точки пятна (BLOB) и двух угловых особых точек (CORNER);

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

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

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

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

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

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

16. Система по п. 11, отличающаяся тем, что выявление множества TARF для изображения-запроса, дополнительно включает:

выявление множества особых точек BLOB в изображении-запросе;

выявление множества особых точек CORNER в изображении-запросе;

создание множества TARF, при этом каждый TARF включает особую точку BLOB из множества особых точек BLOB и две особые точки CORNER из множества особых точек CORNER.

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

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

выявление, на основании рейтинга особых точек CORNER, множества троек смежных оцененных признаков (TARF) для каждого из изображений-запросов, при этом каждый из TARF состоит из особой точки пятна (BLOB) и двух угловых особых точек (CORNER);

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

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

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

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

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

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