СПОСОБ, УСТРОЙСТВО, КОМПЬЮТЕРНАЯ ПРОГРАММА, КОМПЬЮТЕРНАЯ СИСТЕМА И СЧИТЫВАЕМОЕ КОМПЬЮТЕРОМ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО ДЛЯ ПРЕДСТАВЛЕНИЯ И ПОИСКА ОБЪЕКТА В ИЗОБРАЖЕНИИ Российский патент 2003 года по МПК G06T7/60 G06K9/48 

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

Уровень техники
В таких приложениях, как библиотеки образов или видеоизображений, желательно иметь эффективное представление и хранение контура или формы объектов или частей объектов, появляющихся в неподвижных изображениях или видеоизображениях. Известный метод, основанный на форме индексирования и поиска, использует представление масштабированного пространства кривизны (МПК) (CSS). Подробности представления МПК можно найти в статьях "Robust and Efficient Shape Indexing through Curvature Scale Space" (Устойчивое и эффективное индексирование формы посредством пространства с искривленным масштабом) Proc. British Machine Vision conference, pp. 53-62, Edinburgh, UK, 1996, и "Indexing an Image Database by Shape Content using Curvature Scale Space" (Индексирование базы данных изображений посредством контекста формы с помощью пространства с искривленным масштабом) Рrос. IEE Colloquium on Intelligent Databases, London 1996, обе написаны F. Mokhtarian, S. Abbasi and J. Kittler, библиографические данные которых приведены здесь в качестве ссылки.

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

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

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

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

Предмет настоящего изобретения состоит в том, чтобы ввести дополнительное средство описания формы для "формы контура-прототипа". Эта форма контура-прототипа определяется здесь как:
1) исходная форма, если в контуре нет выпуклостей или вогнутостей (т.е., например, в изображении МПК нет пиков), или
2) контур формы после сглаживания эквивалентен наивысшему пику в изображении МПК.

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

К примеру, форма контура-прототипа может быть описана посредством инвариантов, основанных на моментах области, как описано в статье "Visual Pattern Recognition by Moments Invariants" (Визуальное распознавание образов посредством моментных инвариантов), IEEE Transactions on Information Theory, Vol. IT-8, 179-187, 1962, написанной М.К. Нu, библиографические данные которой приведено здесь в качестве ссылки, либо с помощью дескрипторов Фурье, как описано в статье "On Image Analysis by the Methods of Moments" (Об анализе изображений посредством методов моментов), IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 10, No. 4, July 1988, написанной Cho-Huak The, библиографические данные которой приведены здесь в качестве ссылки, либо с помощью параметров, таких как эксцентриситет, округлость и т. п. В упомянутых выше известных способах эксцентриситет и округлость используются только в отношении исходной формы.

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

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

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

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

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

Дополнительный параметр может соответствовать эксцентриситету контура.

Дополнительный параметр может соответствовать округлости контура.

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

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

Дополнительный параметр может быть основан на дескрипторах Фурье.

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

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

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

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

По способу согласно третьему объекту изобретения мера подобия может быть основана на М, где М=a*GP-S+CSS-S, где GP-S - мера подобия между дополнительными параметрами контуров сравниваемых объекта, CSS-S - мера подобия между значениями МПК для контуров сравниваемых объектов, а - постоянная.

По способу согласно третьему объекту изобретения а может зависеть от числа и высоты пиков МПК.

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

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

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

Фиг.2 является рисунком контура объекта.

Фиг.3 является представлением МПК контура по фиг.2.

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

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

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

Конкретнее, контур выражается представлением Ψ={(х(u), y(u), u∈[0, 1]}, где u - параметр нормированной дуговой длины.

Контур сглаживают путем свертки Ψ с ядром g (u, σ) Гауссиана идентификатора. Пересечения нуля кривизны развертывающейся кривой проверяют по мере изменения σ. Пересечения нуля идентифицируют с помощью следующего выражения для кривизны:
,
где Х(u,σ)=х(u)*g(u,σ); Y(u,σ)=y(u)*g(u,σ);
Х_u(u,σ)=x(u)*g_u(u,σ); X_uu(u,σ)=х(u)*g_uu(u,σ).

В вышеприведенных выражениях * представляет свертку, а подстрочные знаки представляют производные.

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

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

В дополнение к представлению МПК дополнительные параметры связываются с данной формой для получения дескриптора формы. В данном выполнении дополнительными параметрами являются эксцентриситет и округлость "области прототипа" для данной формы, где "область прототипа" данной формы представляет собой контур этой формы после окончательного шага сглаживания, т.е. в точке, эквивалентной значению σ наивысшего пика. Для области прототипа могут выбираться и другие значения σ. В результате получается дескриптор формы для формы S в виде: {EPR, CPR, PEAK}, где EPR представляет эксцентриситет области прототипа, CPR - округлость области прототипа, a PEAK - представление МПК.

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

Здесь база 10 данных дескрипторов в системе по фиг.1 хранит дескрипторы формы, полученные согласно описанному выше способу.

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

Предположим, что входной контур, форма S1, сравнивается с запомненной формой S2, причем S1 и S2 являются соответствующими дескрипторами:
S1: {EPR1, CPR1, РЕАК1},
S2: {EPR2, CPR2, РЕАК2},
где EPR означает эксцентриситет области прототипа, CPR означает округлость области прототипа, a PEAK означают набор координат пиков в изображении МПК (этот набор может быть пустым). Мера подобия между двумя формами вычисляется следующим образом.

М=a*abs((EPR2-EPR1)/(EPR2+EPR1))+b*abs((CPR2-CPR1)/((CPR2+CPR1))+SM(PEAKS1, PEAKS2),
где а и b являются двумя коэффициентами, SМ - стандартная мера подобия, определенная на двух наборах пиков [1], a abs обозначает абсолютное значение. SM вычисляется с помощью известного алгоритма сопряжения, в качестве которого можно использовать алгоритмы, описанные в вышеупомянутых статьях. Эта процедура сопряжения вкратце описывается ниже.

При заданных двух замкнутых контурных формах, кривой Ψ_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-альфа-xms|<0,2), произвести сопряжение этих двух пиков и определить цену этого сопряжения как длину прямой линии между этими двумя пиками. Добавить цену этого сопряжения к общей цене этого узла. Удалить сопряженные пики из соответствующих списков, пометив их как "сопряженные". Если расстояние по горизонтали между этими двумя пиками больше чем 0,2, этот пик (xip,yip) изображения не может быть сопряжен. В этом случае добавить его высоту yip к общей цене и удалить только этот пик (xip,yip) из списка пиков изображения, пометив его как "несопряженный".

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

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

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

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

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

В альтернативном воплощении для описания формы "области прототипа" могут использоваться различные параметры. Например, можно использовать три коэффициента Фурье для кривой. Мера подобия может определяться следующим образом:
М=a*EUC(F1,F2)+SM(PEAKS1+PEAKS2),
где EUC - эвклидово расстояние между векторами F1 и F2, сформированными из трех основных коэффициентов Фурье для формы изображения и модели, а - постоянная, SM представляет меру подобия для пиков МПК, вычисленных с помощью способа, по существу описанного выше.

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

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

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

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

Изобретение относится к представлению объекта, появляющегося в изображении. Его использование при обработке изображений, запомненных в мультимедийной базе данных, позволяет обеспечить технический результат в виде повышения точности поиска объектов в изображениях. Этот технический результат достигается благодаря тому, что получают представление масштабированного пространства кривизны (МПК) для контура объекта путем сглаживания этого контура объекта, получают по меньшей мере один дополнительный параметр, отражающий распределение формы или массы сглаженного варианта исходной кривой, и связывают представление МПК и дополнительный параметр в качестве дескриптора формы объекта. Этот дополнительный параметр может соответствовать эксцентриситету или округлости контура, наивысшему пику в изображении в МПК, он может быть основан на дескрипторах Фурье или моментах Цернике и т.п. 5 с. и 12 з.п. ф-лы, 3 ил.

1. Способ представления объекта, появляющегося в изображении, посредством обработки сигналов, соответствующих изображению, согласно которому получают представление масштабированного пространства кривизны (МПК) для контура объекта путем сглаживания контура объекта, получают по меньшей мере один дополнительный параметр, отражающий распределение формы или массы сглаженного варианта исходной кривой, и связывают представление МПК и дополнительный параметр в качестве дескриптора формы объекта.2. Способ по п.1, в котором дополнительный параметр относится к сглаженному контуру, соответствующему пику в изображении в МПК.3. Способ по п.2, в котором дополнительный параметр относится к сглаженному контуру, соответствующему наивысшему пику в изображении в МПК.4. Способ по любому из пп.1-3, в котором дополнительный параметр соответствует эксцентриситету контура.5. Способ по любому из пп.1-4, в котором дополнительный параметр соответствует округлости контура.6. Способ по любому из пп.1-5, в котором по меньшей мере один дополнительный параметр использует основанное на области представление.7. Способ по п.6, в котором дополнительный параметр является моментным инвариантом области.8. Способ по п.6 или 7, в котором дополнительный параметр основан на дескрипторах Фурье.9. Способ по п.6, в котором дополнительный параметр основан на моментах Цернике для области, охваченной контуром.10. Способ представления множества объектов, появляющихся в изображении, посредством обработки сигналов, соответствующих изображениям, согласно которому для каждого контура объекта определяют, имеются ли в контуре объекта выпуклости и вогнутости, и если в кривизне в контуре объекта имеются выпуклости и вогнутости, то получают дескриптор формы с использованием способа по любому из пп.1-9, а если в кривизне в контуре объекта нет выпуклостей и вогнутостей, то получают дескриптор формы, включающий по меньшей мере упомянутый дополнительный параметр, отражающий форму контура объекта.11. Способ по п.10, в котором дополнительный параметр для контура объекта, не имеющего выпуклостей и вогнутостей, основан на моментных инвариантах областей, дескрипторах Фурье или моментах Цернике контура.12. Способ поиска объекта в изображении посредством обработки сигналов, соответствующих изображениям, согласно которому вводят запрос в виде двумерного контура, получают дескриптор упомянутого контура с использованием способа по любому из пп.1-9, сравнивают упомянутый запросный дескриптор с каждым дескриптором для запомненных объектов с помощью процедуры сопоставления, использующей значения МПК и дополнительные параметры для получения меры подобия, и выбирают и отображают по меньшей мере один результат, соответствующий изображению, содержащему объект, для которого сравнение указывает степень подобия между запросом и упомянутым объектом.13. Способ по п.12, в котором мера подобия основана на М, где М=a·GP-S+CSS-S, где GP-S есть мера подобия между дополнительными параметрами контуров сравниваемых объектов, CSS-S есть мера подобия между значениями МПК для контуров сравниваемых объектов, а а есть постоянная.14. Способ по п.13, в котором а зависит от числа и высоты пиков МПК.15. Способ по п.13 или 14, в котором а=1, когда нет пиков МПК, связанных с каким-либо контуром, и а=0, когда по меньшей мере один контур имеет пик МПК.16. Компьютерная система, запрограммированная работать согласно способу, согласно любому одному из пп.1-15.17. Считываемый компьютером носитель записи, хранящий этапы выполнимого на компьютере процесса для воплощения способа согласно любому одному из пп.1-15.