Патент на изобретение №2225034

(54) СПОСОБ И УСТРОЙСТВО, КОМПЬЮТЕРНАЯ ПРОГРАММА, КОМПЬЮТЕРНАЯ СИСТЕМА И СЧИТЫВАЕМАЯ КОМПЬЮТЕРОМ ПАМЯТЬ ДЛЯ ПРЕДСТАВЛЕНИЯ И ПОИСКА ОБЪЕКТА В ИЗОБРАЖЕНИИ

(57) Реферат:

Изобретение относится к представлению объекта, появляющегося в видеоизображении. Его использование для поиска объекта в изображении, хранящемся в мультимедийной базе данных, позволяет обеспечить технический результат в виде снижения сложности процедуры поиска и отождествления объекта. Этот технический результат достигается в способе представления объекта, появляющегося в изображении, путем обработки сигналов, соответствующих изображению, в котором на основе упомянутых сигналов получают множество значений координат для пиков контура объекта в масштабируемом пространстве кривизны и применяют масштабирующее или нелинейное преобразование к значениям координат, чтобы получить представление контура. При поиске вводят запрос в виде двумерного контура, получают представление этого контура, а затем и представление объекта в хранимых изображениях с использованием способа представления объекта, появляющегося в изображении, сравнивают это представление в виде запроса с каждым представлением для хранимого объекта, выбирают и отображают на дисплее по меньшей мере один результат, соответствующий изображению, содержащему объект, для которого сравнение указывает степень подобия между объектом в виде запроса и объектом. 4 с. и 13 з.п. ф-лы, 2 табл., 8 ил.

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

Уровень техники
В таких приложениях, как библиотеки изображений или видеотеки, желательно иметь эффективное представление и хранение контура или профиля объектов или частей объектов, появляющихся в неподвижных изображениях или видеоизображениях. В известном способе индексации и поиска на основе профиля используют представление в масштабированном пространстве кривизны (МПК-представление). Подробности МПК-представления можно найти в статьях “Робастное и эффективное индексирование профиля посредством масштабированного пространства кривизны” в сборнике “Труды Британской конференции по машинному зрению” (“Robust and Efficient Shape Indexing through Curvature Scale Space” Proc. British Machine Vision conference, c. 53-62, Эдинбург, Соединенное Королевство, 1966), и “Индексирование базы данных по составу профилей с использованием масштабированного пространства кривизны” в сборнике “Труды Коллоквиума Института инженеров-электриков по интеллектуальным базам данных” (“Indexing an Image Database by Shape Content using Curvature Scale Space” Proc. IEE Colloquium on Intelligent Databases, Лондон, 1966), причем авторами обеих статей являются Ф.Мохтарян, С.Аббаси и Дж.Киттлер (F. Mokhtarian, S.Abbasi and J.Kittler), а их библиографические данные упоминаются здесь в качестве ссылки.

В МПК-представлении используется функция кривизны для контура объекта, начиная с произвольной точки контура. Функцию кривизны исследуют по мере развертки профиля контура посредством ряда деформаций, которые сглаживают профиль. Более конкретно, вычисляют переходы через нуль производной функции кривизны, свернутой с семейством Гауссовских фильтров. Эти переходы через нуль отображают точками на графике, известном как масштабированное пространство кривизны, где ось x представляет нормализованную длину дуги кривой, а ось y – параметр развертки, в частности параметр применяемого фильтра. Точки на графике образуют петли, являющиеся характеристическими для контура. Каждая выпуклая или вогнутая часть контура объекта соответствует некоторой петле в изображении в МПК (МПК-изображении). Координаты пиков наиболее выпуклых петель в МПК-изображении используются в качестве представления контура.

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

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

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

Обнаружено, что путем применения преобразования, в частности, в значения в МПК (МПК-значения), как это сделано в настоящем изобретении, улучшается рабочая характеристика поиска объекта.

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

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

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

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

Особые точки могут быть также связаны с максимумами и минимумами кривизны кривых контура.

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

Согласно способу по второму объекту изобретения преобразование применяют к значениям координат, соответствующим параметру сглаживания в МПК-представлении.

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

Преобразование может являться масштабирующим преобразованием.

Преобразование может также являться нелинейным преобразованием.

Преобразование могут осуществлять в виде z’=apow(z, b)+с, где a, b и с – константы и pow(z, b) обозначает z в степени b;
b может быть больше нуля и меньше 1;
b может находиться в диапазоне 0,25b0,75;
b может быть равен 0,5.

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

Еще одним объектом изобретения является компьютерная система, которая запрограммирована для работы в соответствии с вышеупомянутыми способами.

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

Краткое описание чертежей
Фиг.1 изображает блок-схему базы видеоданных,
фиг.2 изображает чертеж контура объекта,
фиг.3 изображает МПК-представление контура, показанного на фиг.2,
фиг.4 изображает рисунок, иллюстрирующий представление профиля,
фиг.5 изображает чертеж профиля объекта,
фиг.6 изображает МПК-представление профиля, показанного на фиг.5,
фиг. 7 изображает преобразованное представление профиля, показанного на фиг.5,
фиг.8 изображает блок-схему, иллюстрирующую способ поиска.

Наилучший способ осуществления изобретения
Первый конкретный вариант осуществления
Фиг. 1 изображает компьютеризованную систему базы видеоданных в соответствии с конкретным вариантом осуществления изобретения. Система включает в себя блок 2 управления в виде компьютера, дисплей 4 в виде монитора, указательное устройство 6 в виде мыши, базу 8 данных изображений, включающую в себя хранимые неподвижные изображения и видеоизображения, и базу 10 данных описателей, хранящую описатели объектов или частей объектов, появляющихся в изображениях, хранимых в базе 8 данных изображений.

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

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

Более конкретно, контур выражают представлением =((х(u), y(u), u[0, 1] }, где u – параметр нормализованной длины дуги.

Контур сглаживают путем свертки с идентифицирующим Гауссовым ядром g(u, ), а переходы через нуль кривизны развертывающей кривой проверяют при изменениях . Переходы через нуль идентифицируют, пользуясь следующим выражением для кривизны:

где
X(u, ) = x(u, )*g(u, ),
Y(u, ) = y(u, )*g(u, ),
и
X_u(u, ) = x(u, )*g_u(u, ),
X_uu(u, ) = x(u, )*g_uu(u, ).
Здесь * обозначает свертку, а подстрочные индексы обозначают производные.

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

Точки переходов через нуль отображают в виде точек на графике, известном как пространство изображений в МПК (МПК-изображений). Это приводит к множеству характеристических кривых. Пики характеристических кривых идентифицируют, а соответствующие координаты выделяют и сохраняют. Вообще говоря, это дает набор из n пар координат: [(х1, y1), (х2, y2),…,(хn, yn)], где n – число пиков, a xi – положение длины дуги i-го пика и yi – высота этого пика.

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

Затем подвергают дополнительной обработке значения пиков или, иными словами, значения составляющей y для пиков. Более конкретно, значения y преобразуют, пользуясь таким преобразованием:
y’=apow(y,b)+c, (1)
где pow(y, b) обозначает y в степени b.

Это приводит к новому набору значений пиков: [(х’1, y’1), (х’2, y’2),… , (x’n, y’n)] , сохраняемых в базе данных описателей в качестве описателя контура.

В качестве конкретного примера отметим, что контур, показанный на фиг.2, приводит к МПК-изображению, показанному на фиг.3. Подробные значения координат пиков кривых в МПК-изображении приведены в табл. 1.

Затем применяют преобразование, заданное выше, при а=6, b=0,5 и с=0. Иными словами, извлекают корень квадратный из исходного значения у и умножают его на константу. Это приводит к значениям, приведенным в табл.2.

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

Второй конкретный вариант осуществления
Другой пример изображен на фиг.4.

Фиг. 5 изображает еще один пример профиля объекта, в этом случае – черепахи. Фиг. 6 изображает МПК-пики для профиля, показанного на фиг.5. Фиг.7 изображает пики, показанные на фиг.6 и преобразованные с использованием преобразования, заданного в уравнении (1), приведенном выше, при а=6,5, b=0,5 и с=0.

В целях поиска используют сохраняемые описатели. Пользователь инициирует поиск, делая чертеж контура объекта на дисплее с использованием указательного устройства (этап 510). После этого блок 2 управления создает МПК-представление вводимого контура (этап 520), а затем применяет вышеописанное преобразование к значениям y (этап 530). После этого получаемый описатель вводимого контура сравнивают с каждым сохраненным описателем в базе данных описателей, именуемых ниже описателями модели, с использованием известной процедуры отождествления (этап 540).

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

Задаваясь двумя профилями замкнутого контура: кривой i изображения и кривой m модели и соответствующими им наборами пиков: [(xi1, yi1), (xi2, yi2), …, (xin, yin)] и [(xm1, ym1), (xm2, ym2),…, (xmn, ymn)], вычисляют меру подобия. Меру подобия определяют как суммарную стоимость отождествления пиков в модели с пиками в изображении. Отождествление, которое минимизирует общую стоимость, определяют с использованием динамического программирования. Алгоритм обеспечивает рекурсивное отождествление пиков из модели с пиками из изображения и вычисление стоимости каждого такого отождествления. Каждый пик модели может быть отождествлен только с одним пиком изображения, а каждый пик изображения может быть отождествлен только с одним пиком модели. Какой-либо пик модели и/или изображения может остаться неотождествленным, и для каждого неотождествленного пика имеется дополнительная штрафная стоимость. Два пика можно отождествить, если горизонтальное расстояние между ними меньше 0,2. Стоимость отождествления – это длина прямой линии между этими двумя отождествленными пиками. Стоимостью неотождествленного пика является его высота.

Если говорить подробнее, то алгоритм работает, создавая и расширяя некоторую древовидную структуру, в которой узлы соответствуют отождествленным пикам:
1. Создают начальный узел, состоящий из наибольшего максимума изображения (xik, yik) и наибольшего максимума модели (xir, yir).

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

3. Инициализируют стоимость каждого начального узла, созданного на этапах 1 и 2, полагая ее равной абсолютной разности координаты y пиков изображения и модели, связанных этим узлом.

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

5. Для каждого начального узла создают список узлов модели и список узлов изображения. Список содержит информацию о том, какие пики еще нужно отождествить. Для каждого начального узла отмечают пики, отождествленные в этом узле как “отождествленные”, а все остальные пики – как “неотождествленные”.

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

7. Расширение узла.

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

Выбирают неотождествленный максимум (xip, yip) в МПК (МПК-максимум) кривой изображения в наибольшем масштабе. Применяют параметр сдвига начального узла (вычисленный на этапе 4) для преобразования выбранного максимума в изображение модели в МПК (МПК-изображение модели) и теперь выбранный пик имеет координаты (xip-альфа, yip). Устанавливают местонахождение (xms, yms) ближайшего пика кривой модели, который не отождествлен. Если горизонтальное расстояние между этими двумя пиками меньше 0,2 (т.е. |xip-альфа|<0,2), то отождествляют эти два пика и определяют стоимость отождествления как длину прямой линии между этими двумя пиками. Прибавляют стоимость согласования к суммарной стоимости такого узла. Удаляют отождествленные пики из соответствующих списков, отмечая их как “отождествленные”. Если горизонтальное расстояние между этими двумя пиками больше 0,2, то пик (xip, yip) модели отождествить нельзя. В этом случае прибавляют его высоту yip к суммарной стоимости и удаляют только пик (xip, yip) из списка пиков изображения, отмечая его как “отождествленный”.

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

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

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

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

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

Вышеупомянутые этапы повторяют для каждой модели в базе данных (этап 480).

Меры подобия, получаемые в результате сравнений при отождествлении, упорядочивают (этап 490), а затем объекты, соответствующие описателям, имеющим меры подобия, указывающие самое точное отождествление (т.е. в данном случае – наименьшие меры подобия), отображают для пользователя на дисплее 4 (этап 500). Число объектов, подлежащих отображению, может быть предварительно установлено или выбрано пользователем.

Третий конкретный вариант осуществления
Теперь будет описан альтернативный конкретный вариант осуществления. Этот конкретный вариант осуществления является таким же, как предыдущий конкретный вариант осуществления, за исключением того, что используется другое преобразование. Более конкретно, значения y преобразуются с использованием преобразования y’=а₀+a₁y.

Иными словами, применяется линейное масштабирующее преобразование.

Здесь а₀=41, a₁=0,19.

В одной вариации а₀=0, a₁=0,27.

Можно использовать и другие значения а₀ и а₁, если они подходят.

Процедура поиска и отождествления является, по существу, такой же, как описанная в предыдущем конкретном варианте осуществления.

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

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

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

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

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

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

Изобретение также можно применять для отождествления изображений или объектов в целях верификации или для фильтрации.

Формула изобретения

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

2. Способ по п.1, в котором упомянутые числовые значения, по существу, инвариантны к масштабу контура.

3. Способ по п.1 или 2, в котором число упомянутых числовых значений зависит от профиля контура.

4. Способ по любому предыдущему пункту, в котором масштабирующее или нелинейное преобразование не зависит от профиля контура.

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

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

7. Способ по п.6, в котором особые точки связаны с кривизной каждой кривой контура.

8. Способ по п.7, в котором особые точки связаны с максимумами и минимумами кривизны кривых контура.

9. Способ по любому из пп.1-8, в котором преобразование осуществляют в виде z’=a*pow(z, b) + с, где a, b и с – константы, и pow(z, b) обозначает z в степени b.

10. Способ по п.9, в котором b больше нуля и меньше 1.

11. Способ по п.10, в котором b находится в диапазоне 0,25b0,75.

12. Способ по п.11, в котором b=0,5.

13. Способ по п.11, в котором b=0,6.

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

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

16. Компьютерная система, запрограммированная для работы в соответствии со способом по любому из пп.1-14 представления объекта и/или способом по п.15 поиска объекта в изображении.

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

РИСУНКИ