СПОСОБ ВЫБОРКИ ИЗОБРАЖЕНИЙ ИЗ БАЗЫ ИЗОБРАЖЕНИЙ Российский патент 2013 года по МПК G06T1/00 

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

Широко известны способы, реализованные в системах поиска, таких как TinEye http://www.tineye.com/, Google Images http://images.google.com/ (для браузера Google Chrome) и VIRaL http://viral.image.ntua.gr/upload.php.

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

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

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

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

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

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

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

1 - ввод исходного изображения в устройство обработки данных,

2 - визуализация этого изображения,

3 - автоматическое выделение всех его объектов,

4 - выделение одного из этих объектов особым способом,

5 - формирование запроса,

6 - поиск искомых изображений в их базе,

7 - выборка искомых изображений,

8 - визуализация искомых изображений,

9 - выделение на них искомых объектов,

A - устройство обработки данных,

B - устройство визуализации,

C - область визуализации исходного изображения,

D - особо выделенный объект (поисковый образец),

E - запрос (оператор),

F - элемент запроса - графические характеристики поискового образца,

G - элемент запроса - диапазон ожидаемых значений функции сходства искомых объектов с поисковым образцом,

H - база изображений,

K - область визуализации искомых изображений с выделенными на них искомыми объектами.

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

L, M - оси характеристического пространства,

G - диапазон ожидаемых значений функции сходства,

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

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

S - подвижный регулятор,

U - начальное состояние регулятора (точка захвата),

V - конечное состояние регулятора (точка останова),

X, Y, Z - точки промежуточных состояний регулятора.

Примеры осуществления способа

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

- считыванием графического файла или одного из видеокадров файла оцифрованного фильма с жесткого диска ЭВМ или с внешнего носителя информации, расположенного в корпоративной сети или в сети Интернет,

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

- загрузкой копии изображения или его части из электронного документа (электронной статьи, книги и т.д.).

Сразу после ввода (1) исходного изображения с помощью устройства визуализации (В) это изображение визуализируют (2) в область визуализации (С), автоматически одним и тем же визуальным способом выделяя (3) все его объекты заданного класса. Областью визуализации (С) исходного изображения может служить, например, экран монитора ЭВМ или дисплей мобильного устройства, например мобильного телефона или компьютерного планшета. Объектами заданного класса, например, могут быть все такие объекты изображения, площадь которых не меньше 10% его площади, или, например, все такие его объекты, средняя яркость которых не меньше некоторого фиксированного предела. Автоматическое выделение (3) объектов заданного класса с подобными параметрами может быть, например, имплементировано с помощью заранее созданной программы для ЭВМ или с помощью заранее созданных таких микросхем устройства (A) обработки данных, в которых имплементированы алгоритмы детектирования объектов на изображении вместе с фиксированными параметрами упомянутого выше типа. Способом визуального выделения всех объектов заданного класса может быть, например, их подсветка контурами или штрихами синего цвета.

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

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

Далее, с помощью устройства (A) обработки данных на основе графических характеристик исходного изображения формируют (5) поисковый запрос (E). Этими характеристиками в данном способе являются определенные, как описано выше, наборы (F) графических характеристик поисковых образцов (D). Каждый из этих образцов является частью исходного изображения, поэтому характеристики наборов (F) одновременно являются характеристиками этого изображения. Наряду с наборами (F) графических характеристик поисковых образцов в поисковый запрос (E) также включают соответствующие этим образцам (D) установленные диапазоны (G) ожидаемых значений функции сходства искомых объектов с этими образцами. Здесь о сходстве объектов и о диапазонах ожидаемых значений функции их сходства необходимо отметить следующее. Любому множеству таких объектов, для каждого из которых по заданному правилу может быть определен набор, состоящий из N его характеристик, соответствует N-мерное характеристическое пространство. Осями такого пространства являются оси этих характеристик. Образами объектов в их характеристическом пространстве являются точки, значения координат которых совпадают со значениями соответствующих характеристик этих объектов. Введение метрики в характеристическом пространстве объектов позволяет говорить о близости или удаленности их образов в этом пространстве, а также о функциях сходства или различия анализируемых объектов. Понятие функции сходства объектов широко используется в теории распознавания. Функцией сходства может быть, например, степень сходства/различия или мера сходства/различия. Функция сходства может определяться, например, метрикой характеристического пространства объектов. Диапазон (G) ожидаемых значений функции сходства искомых объектов с поисковым образцом (D) без ограничения общности показан на фиг.2, как пример для случая 2-мерного характеристического пространства объектов с осями (L) и (M). На примере, показанном на фиг.2, диапазон (G) определяет кольцо (Q), содержащее искомые объекты ожидаемого результирующего множества. Если диапазон (G) есть G=[0, W], то кольцо (Q) вырождается в область в виде круга с радиусом W. Если при этом W=0, то круг вырождается в точку, а запрос (Е) в этом случае предполагает точный поиск (6), т.е. поиск таких изображений, которые содержат объекты, в точности совпадающие с поисковым образцом (D).

После формирования запроса (Е) выполняют поиск (6) искомых изображений с параметрами этого запроса в базе (H), а также их выборку (7) порциями заданного размера, как это делается в любой поисковой системе.

Затем выбранные изображения визуализируют (8) с помощью устройства визуализации (B) в область визуализации (K), автоматически визуально выделяя, по меньшей мере, в одном из них те искомые объекты, которые удовлетворяют условиям запроса (E). Выделение в искомых изображениях искомых объектов необходимо для их сравнения с ранее выделенными поисковыми образцами (D).

После визуализации искомых изображений и визуального выделения в них объектов один или несколько раз изменяют хотя бы один из поисковых диапазонов (G). Эту операцию выполняют вручную, путем управления, по меньшей мере, одним таким подвижным регулятором (S) точности поиска, который в процессе изменения своего состояния, включая точку его останова (V), однократно или многократно инициирует цикл, который состоит из следующих уже описанных выше операций:

- формирование запроса (E) с прежними наборами (F) графических характеристик образцов и с новым набором поисковых диапазонов (G),

- поиск (6) изображений с параметрами нового запроса (E),

- выборка (7) искомых изображений,

- визуализация (8) этих изображений их первой выбранной порции,

- визуальное выделение (9) в них объектов, удовлетворяющих условиям запроса (E).

Схема процесса управления подвижным регулятором (S) точности поиска иллюстрируется на фиг.3, а суть этого процесса состоит в следующем. Путем захвата подвижного элемента регулятора, находящегося в состоянии (U), его перемещают, например, вправо до точки останова (V). В одном из вариантов описанный выше цикл инициируется один раз в состоянии (V) после освобождения захвата. В другом варианте этот цикл инициируется многократно, например, в состояниях (X), (Y), (Z) и (V) или, например, в 100 других состояниях в полуинтервале (U, V]. Здесь необходимо отметить, что поиск (6) искомых изображений и их выборка (7) выполняются за конечное время. При многократно инициируемых циклах в полуинтервале (U, V] это время суммируется, и в применении к большим базам (H) изображений оно может стать достаточно ощутимым. Поэтому для того чтобы второй из этих вариантов оставался эффективным, для организации описанных циклов базу (H) сначала необходимо проиндексировать. Одним из лучших способов для этого является создание многомерных индексов для базы (H), ключами каждого из которых являются характеристики наборов (F). Методы многомерных индексов широко известны и давно применяются на практике. Примером широко применяемого многомерного индекса является индекс kd-tree. Таким образом, показана возможность эффективного осуществления представляемого способа в обоих выше указанных вариантах. Однако если поиск (6) искомых изображений и их выборка (7) выполняются через коммуникационные сети, то загруженность трафика может, все-таки, повлиять на эффективность исполнения второго из этих вариантов. В этом случае рекомендуется использовать первый описанный вариант.

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

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

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

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

- для поиска и распознавания графических материалов, защищенных авторскими правами, например товарных знаков.

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

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

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