显示或检索图像中的目标的方法及其装置、计算机程序、计算机系统和计算机可读存储媒体

摘要

一种通过处理与图像对应的信号来表示在静止图像或视频图像中出现的目标的方法，通过处理与图像对应的信号来表示在静止图像或视频图像中出现的目标的方法，包括从目标的轮廓上的任意的点开始导出与在轮廓上显现的特征相关的多个数值的步骤和对该值应用指定的分类而得到轮廓的显示的步骤。

说明书

本申请是申请人三菱电机株式会社于2000年7月3日提交的同名中国专利申请No.00801910.x的分案申请。

技术领域

本发明涉及以检索为目的的在多媒体数据库中保存的图像那样的静止图像或视频图像中出现的目标的显示，特别是使用这样的显示检索目标的方法和装置。

背景技术

在图像程序库的图像的应用程序中，进行视频图像或静止图像中出现的目标的轮廓及形状或目标的一部分的有效的显示和保存。在用于进行附加形状库的索引和检索的众所周知的方法中，可以使用曲率标度空间(CSS)显示。关于CSS的详细情况，可以在论文「利用曲率标度空间的坚固性附加有效的形状索引」(英国机器影像会报pp.53～62、爱丁堡、英国、1996年)和「利用使用诮标度空间的形状内容附加图像数据库的索引」(关于智能数据库的IEE专家会议报、伦敦、1996年)中找到。两篇论文都是Mokhtarian、S.Abbasi和J.Kittler撰写的，其内容在本说明书中是作为参考文献而引用的。

在CSS显示中，为了得到目标的轮廓，使用曲率函数，从轮廓上的任意的点开始进行显示。通过进行使形状平滑化的一连串的变形，将轮廓的形状展开，研究曲率函数。此外，具体而言，就是计算与高斯滤波器的族一起卷积的曲率函数的导函数的零交叉。作为曲率标度空间，如所周知，零交叉绘制在曲线图上。但是，x轴是曲线的正规化的弧长，y轴是展开参量，特别是应用滤波器的参量。曲线图上的点形成表示轮廓的特征的环。构成目标的轮廓的各凸状或凹状的部分，与CSS图像的环对应。在CSS图像中，最突起的环的尖峰的纵坐标用于进行轮廓的显示。

为了检索与输入目标的形状一致的数据库中的保存图像的目标，计算输入形状的CSS显示。通过使用匹配算法语言比较各CSS图像的尖峰的位置和高度，判断输入形状与保存形状间的类似度。

作为关于众所周知的CSS显示的问题，有指定的轮廓的尖峰基于从轮廓上的任意的点开始进行计算的曲率函数的问题。改变该开始点时，发生CSS图像的尖峰沿x轴周期地移位。因此，在计算类似度测定值时，必须考虑所有的可能的移位或至少必须考虑最容易发生的移位。结果，将增加检索手续和匹配手续的复杂性。

因此，本发明的目的旨在提供通过处理与图像对应的信号来表示出现在静止图像或视频图像中的目标的方法，该方法包括从轮廓上的任意的点开始导出与在目标的轮廓上显现的特征相关的多个数值的步骤和对上述值应用指定的分类而得到轮廓的显示的步骤。最好根据上述轮廓的CSS显示导出上述值，另外，上述值最好与CSS峰值对应。

作为本发明的结果，可以不显著地降低检索精度而大幅度地降低关于匹配程序的计算。

发明的内容

本发明的第1方面所述的显示图像中的目标的方法是通过处理与静止图像或视频图像对应的信号来表示在图像中出现的目标的方法，其特征在于：包括从目标的轮廓上的任意的点开始导出与在轮廓上显现的特征相关的多个数值的步骤和对该值应用指定的分类而得到轮廓的显示的步骤。

本发明的第2方面所述的显示图像中的目标的方法，其特征在于：作为结果而得到的显示与轮廓上的开始点无关地进行指定的分类。

本发明的第3方面所述的显示图像中的目标的方法，其特征在于：数值反映曲线上的弯曲点。

本发明的第4方面所述的显示图像中的目标的方法，其特征在于：通过使用平滑化参量σ按多个阶段将轮廓平滑而生成多个轮廓曲线和通过使用表示各轮廓曲线的曲率的最大值和最小值的值导出表示原来的轮廓的特征的曲线以及通过选择作为数值表示特征的曲线的尖峰的纵坐标，来得到轮廓的曲率标度空间的显示。

本发明的第5方面所述的显示图像中的目标的方法，其特征在于：表示特征的曲线的纵坐标与轮廓的弧长参量和平滑化参量对应。

本发明的第6方面所述的显示图像中的目标的方法，其特征在于：根据与平滑化参量对应的尖峰的高度的值将尖峰的纵坐标值进行分类。

本发明的第7方面所述的显示图像中的目标的方法，其特征在于：将数值从最大值开始进行分类。

本发明的第8方面所述的显示图像中的目标的方法，其特征在于：将数值按大小降低的顺序进行分类。

本发明的第9方面所述的显示图像中的目标的方法，其特征在于：将数值从最小值开始进行分类。

本发明的第10方面所述的显示图像中的目标的方法是通过处理与静止图像或视频图像对应的信号来表示在图像中出现的目标的方法，其特征在于：包括为了表示目标的轮廓而导出与在轮廓上显现的特征相关的多个数值的步骤和导出使用数值中的至少2个值间的关系表示显示的可靠性的系数的步骤。

本发明的第11方面所述的显示图像中的目标的方法，其特征在于：系数基于数值中的2个值间的比。

本发明的第12方面所述的显示图像中的目标的方法，其特征在于：上述比是2个最大值之比。

本发明的第13方面所述的显示图像中的目标的方法，其特征在于：通过使用平滑化参量σ按多个阶段将轮廓平滑而生成多个轮廓曲线和通过使用表示用于导出表示原来的轮廓的特征的曲线的各轮廓曲线的曲率的最大值和最小值的值以及通过选择作为数值表示特征的曲线的尖峰的纵坐标，来得到轮廓的曲率标度空间的显示。

本发明的第14方面所述的显示图像中的目标的方法，其特征在于：使用第1～9方面的任一方面所述的方法导出上述数值。

本发明第15方面所述的检索图像中的目标的方法是通过处理与静止图像或视频图像对应的信号来检索图像中的目标的方法，其特征在于：包括用2维的轮廓的形式输入查询的步骤、使用第1～9方面的任一方面所述的方法导出轮廓的描述符的步骤、取得使用第1～9方面的任一方面所述的方法导出的所保存的图像中的目标的描述符并将所保存的目标的各描述符与查询描述符进行比较的步骤和根据比较而选择显示与包含表示查询与目标间的类似度的程度的对象目标的图像对应的至少1个结果的步骤。

本发明第16方面所述的检索图像中的目标的方法，其特征在于：使用第10～12方面的任一方面所述的方法对于查询的轮廓和各保存的轮廓导出系数，仅使用指定的分类或使用指定的分类和与系数有关的某个其他分类进行比较。

本发明的第17方面所述的显示图像中的目标的方法，是通过处理与静止图像或视频图像对应的信号来表示在图像中出现的多个目标的方法，其特征在于：包括导出与在各目标的轮廓上显现的特征关联的多个数值的步骤和应用与表示各轮廓的值相同的指定的分类得到各轮廓的显示的步骤。

本发明的第18方面所述的显示或检索图像中的目标的装置，其特征在于：适合于执行第1～17方面的任一方面所述的方法。

本发明的第19方面所述的显示或检索图像中的目标的计算机程序，其特征在于：适合于执行第1～17方面的任一方面所述的方法。

本发明的第20方面所述的显示或检索图像中的目标的计算机系统，其特征在于：编程为按照第1～17方面的任一方面所述的方法而动作。

本发明的第21方面所述的计算机可读存储媒体，其特征在于：保存用于实现第1～17方面的任一方面所述的方法的计算机可以执行的处理。

本发明的第22方面所述的显示图像中的目标的方法，其特征在于：和参照附图在本说明书中说明的实际上相同，显示静止图像或视频图像中的目标。

本发明的第23方面所述的检索图像中的目标的方法，其特征在于：和参照附图在本说明书中说明的实际上相同，检索静止图像或视频图像中的目标。

本发明的第24方面所述的显示或检索图像中的目标的计算机系统，其特征在于：和参照附图在本说明书中说明的实际上相同。

附图的简单说明

图1是视频数据库系统的框图。

图2是目标的轮廓的图。

图3是表示图2的轮廓的CSS显示的图。

图4是表示检索方法的框图。

具体实施方式

下面，参照附图说明本发明的实施例。

实施例1.

图1表示本发明的实施例进行计算机处理的视频数据库系统。在该系统中，包括计算机形式的控制装置2、监视器形式的显示装置4、鼠标形式的指示装置6、包含保存的静止图像和视频图像的图像数据库8和保存在图像数据库8保存的图像中出现的目标或目标的几个部分的描述符的描述符数据库10。

表示在图像数据库的图像中出现的有兴趣的各目标的形状的描述符由控制装置2导出，保存导描述符数据库10中。控制装置2根据执行以下说明的方法的适当的程序的控制而动作，导出描述符。

第1，对于指定的目标的轮廓，导出该轮廓的CSS显示。

使用上述论文之一所描述的众所周知的方法进行该CSS显示。

此外，具体而言，就是利用映射表现Ψ＝{(x(u)，y(u)，u∈[0，1])}表示该轮廓(其中，u是正规化的弧长参量)。

该轮廓通过使用ID高斯核g(u，ρ)进行卷积(convolve)而平滑，对于ρ的变化，检查展开(evolving)曲线的曲率零交叉。零交叉使用表示曲率的下述公式进行特定。即

$$ >>k>>(>u>,>\sigma >)>>=>>>>X>u>>>>>(>u>,>\sigma >)>>>>Y>uu>>>(>u>,>\sigma >)>>->>X>uu>>>(>u>,>\sigma >)>>>Y>u>>>(>u>,>\sigma >)>>>{{{}^{}}^{}}^{}$$

其中，

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，σ)

在上述公式中，*表示卷积，脚标表示导函数。

曲率零交叉的数随ρ的变化而变化，ρ非常高时，Ψ成为零交叉的凸状的曲线。

零交叉点(u，ρ)描绘在作为CSS图像空间的曲线图上。结果，就形成表示原来的轮廓的特征的曲线。于是，特定表示该特征的曲线的尖峰，并抽出对应的纵坐标进行保存。通常，上述结果给出n个坐标对((x1，y1)、(x2，y2)、...(xn，yn))的组(其中，n是尖峰的数、xi是第i个尖峰的弧长的位置、yi是尖峰的高度)。

表示该特征的曲线的分类和位置以及对应的尖峰在CSS图像空间中出现时，与上述曲率函数的开始点有关。在本发明中，尖峰的纵坐标使用专用的分类函数进行再分类。

利用尖峰索引{1...n}与新的集合的索引{1...n}的1对1映射T进行分类。

在本实施例中，纵坐标的对通过考虑y纵坐标的尺寸进行分类。第1，选择最大尖峰。假定第k个尖峰最突起。这时，在数值进行了分类的集合中，(xk，yk)成为第1个坐标。换言之，就是T(k)＝1。同样，其他的尖峰的纵坐标按尖峰的高度的降低顺序进行再分类。在2个尖峰具有相同的高度时，具有与上述纵坐标对的x坐标最接近的x坐标的尖峰配置为第1。换言之，具有原来的索引i的各纵坐标对被分配给新的索引。但是，T(i)＝j，并且yj＞＝y(j+1)。另外，各值xi符合-xk的周期的移位。

作为特定的例子，从图2所示的轮廓可以得到图3所示的CSS图像的结果。CSS图像的曲线的尖峰的纵坐标的详细情况示于以下的表1。

表1

尖峰索引XY  1  0.124  123  2  0.68  548  3  0.22  2120  4  0.773  1001  5  0.901  678

这些尖峰使用上述分类方法进行分类。即，纵坐标按尖峰的高度降低的顺序进行分类。另外，x纵坐标都向零的方向咬与最大尖峰的原来的x纵坐标相等的量。结果，便形成示于以下表2中的进行了再分类的尖峰坐标。

表2

尖峰索引XY  1  0  2120  2  0.553  1001  3  0.681  678  4  0.46  548  5  0.904  123

利用这些进行了再分类的尖峰的纵坐标，对保存在数据10中的目标的轮廓形成描述符的数据库。在本实施例中，按表2所示的分类顺序保存尖峰的纵坐标。或者，也可以与表示新的分类顺序的关联的索引一起保存纵坐标。

实施例2.

下面，说明实施例2的表示目标的轮廓的代替方法。

表示轮廓的CSS显示按上述方式导出。但是，尖峰的纵坐标的分类与上述实施例1的分类不同。此外，具体而言，第1，选择最大尖峰。假定尖峰k是最突起的尖峰。这时，(xk，yk)在尖峰的分类集合中成为第1个尖峰。其后的尖峰对于原来的索引i的尖峰的纵坐标，成为T(i)＝J并且xj＜＝x(j+1)。另外，所有的值xi都向下方咬与原来的尖峰k的原来的x纵坐标相等的量xk。

换言之，在实施例2的方法中，选择最大尖峰，配置到第1位，然后，其余的尖峰按照从最大尖峰开始的原来的顺序进行配置。

以下的表3表示按照实施例2进行分类的表1的峰值的表。

表3

尖峰索引XY  1  0  2120  2  0.46  548  3  0.553  1001  4  0.681  678  5  0.904  123

在上述实施例1和2的展开中，可靠性系数(CF)与形状的各显示相关联。CF根据指定形状的第2最大峰值与最大峰值之比来计算。

对于图2所示的轮廓，CF值为CF＝1001/2120。在本例中，通过使CF最接近于0.1而进行量化处理，减少存储要件。因此，在本例中，CF＝0.5。

本例的CF值是显示的痂度即唯一性的反映。在本例中，接近于1的CF值意味着可靠性低，接近于零的CF值表示可靠性高。换言之，如果2个最大峰值越接近，显示正确的可能性就越小。

进行以下说明的匹配顺序时，CF值可以成为有益的数值。

实施例3.

下面，参照作为表示检索方法的框图的图4说明根据本发明的实施例检索图像中的目标的方法。

在本例中，在图1的系统的描述符数据库10中，与关联的CF值一起保存着按照上述第1分类方法导出的描述符。

用户使用指示装置通过在显示器上描绘目标的轮廓，开始进行检索(步骤410)。其次，控制装置2导出输入轮廓的CSS显示，按照与对数据库中的图像所使用的函数相同的分类函数进行尖峰的纵坐标的分类，得到表示输入轮廓的描述符(步骤420)。然后，控制装置2通过计算第2最大峰值与最大峰值的比率，来计算输入轮廓的CF值，并进行该结果的量化处理(步骤430)。

然后，控制装置2将输入轮廓的CF值与指定的阈值进行比较(步骤440)。在本例中，该阈值是0.75。表示对输入描述符的精度的相对的高的可靠性，在CF值比该阈值低时，下一个步骤就是考虑现在考虑中的模型(即保存在数据库中的图像)的CF值的步骤。在模型的CF仍然比阈值低时(步骤450)，仅使用指定的分类顺序的各描述符进行输入描述符与模型的比较(步骤460)。在输入描述符或模型的CF大于阈值时，通过将输入描述符中的纵坐标值的所有的可能的不同的分类顺序与数据库中的模型描述符进行比较，来进行匹配(步骤470)。

在数据库中，各描述符的类似度测定值使用作为结果而得到的适当的算法语言进行匹配比较。也可以使用在上述论文中说明的众所周知的匹配算法语言。下面，简单地说明该匹配顺序。

给定2个闭合的轮廓的形状、图像曲线Ψi和模型曲线Ψm和这些曲线的尖峰的设定值{(xi1，yi1)，(xi2，yi2)，..，(xin，yin)}和{(xm1，ym1)，(xm2，ym2)，..，(xmn，ymn)}，可以计算类似度测定值。类似度测定值定义为图像中的尖峰与模型中的尖峰的匹配的总代价。使总成本最小化的匹配使用动态程序设计进行计算。利用算法语言，从模型得到的尖峰反馈给从图像得到的尖峰进行匹配，进行这种匹配的各种代价的计算。可以使各模型的尖峰与唯一的图像尖峰进行匹配，也可以使各图像的尖峰与唯一的模型尖峰进行匹配。在模型和/或图像尖峰中有时也有仍然不匹配的尖峰，对于未匹配的尖峰，存在追加的损失代价。在2个尖峰的水平距离小于0.2时，可以使2个尖峰匹配。匹配的代价就是2个匹配的尖峰件的直线长度。未匹配的尖峰的代价是其高度。

更详细而言，就是算法语言通过作成并扩张与节点匹配的尖峰对应的树状的结构而前作用。

1.作成由图像(xik，yik)的最大值与模型(xir，yir)的最大值构成的开始节点。

2.对图像尖峰的最大值的80％以内的各其余的模型尖峰作成追加的开始节点。

3.将上述1和2作成的各开始节点的代价初始化为该开始节点与链接的图像尖峰和模型尖峰的y坐标之差的绝对值。

4.对上述3的各开始节点计算作为在该开始节点匹配的模型尖峰与图像尖峰的x(水平)坐标之差而定义的CSS移位参量α。移位参量对各节点是不同的。

5.对各开始节点作成模型尖峰的列表和图像尖峰的列表。在该列表中包含关于哪个尖峰还未匹配的信息。对于各开始节点，对于“已匹配的”，就给在该节点已匹配的尖峰加上标志，而对其他所有的尖峰则作为“未匹配的”也给加上标志。

6.反馈扩大最低代价的节点，直至满足下述8的条件(从在步骤1～6作成的各节点开始，各节点的子节点位于其后)。为了扩大节点，使用以下的步骤。

7.节点的扩大

在存在仍然未匹配的至少1个图像还1个模型尖峰时，选择未匹配的最大的标度图像曲线CSS的最大值(xip，yip)。将应用(在步骤4计算的)开始节点移位参量所选择的最大值映射导模型CSS图像上，选择的尖峰具有坐标(xip-alpha，yip)。决定未匹配的最近的模型曲线尖峰(xms，yms)。在2个尖峰间的水平距离小于0.2(即|xip-alpha-xms|＜0.2)时，就使2个尖峰匹配，作为2个尖峰间的直线的长度，定义匹配的代价。将匹配的代价加到该节点的总代价上。对于匹配的尖峰，通过作为“已匹配的”加上标志，从各列表中除去已匹配的尖峰。在2个尖峰间的水平距离大于0.2时，图像尖峰(xip，yip)就不能进行匹配。这时，就将图像尖峰的高度yip加到总代价上，通过给“已匹配的”尖峰加上标志，将尖峰(xip，yip)从图像尖峰表中除去。

在不满足上述条件(只存在未匹配的图像尖峰或只存在未匹配的模型尖峰)时，就置于仍然未匹配的状态。

作为未匹配的图像尖峰或模型尖峰的增高的高度，定义匹配的代价，并将尖峰从列表中除去。

8.在上述7扩大节点之后，在图像列表和模型列表中都不存在未匹配的尖峰时，就结束匹配处理。该节点的代价就是图像与模型曲线间的类似度测定值。在存在尖峰时，就返回到上述7，扩大最低代价的节点。

将图像曲线峰值与模型曲线峰值进行交换，反复进行上述步骤。最终匹配值是这2个峰值中的低的一方的值。

作为另一个例子，对于分类的顺序的各位置，计算输入的x值与和其对应的模型的x值间的距离和输入的y值与和其对应的模型的y值间的距离。计算所有位置的合距离，合距离越小，匹配的程度越接近。在输入轮廓与模型的尖峰的树不同时，在合距离中就包含其余的未匹配的峰值的高度。

对数据库的各模型反复进行上述步骤(步骤480)。

将匹配比较的结果而产生的类似度值进行分类(步骤490)，然后，在显示装置4上向用户显示与具有表示最近的匹配值(即，在本例中最低的类似度值)的类似度值的媒质符对应的目标(步骤500)。显示对象的目标树用户可以预先设定或选择。

在上述实施例中，在CF值大于阈值时，就考虑匹配时输入描述符值的所有的可能的顺序。但是，也可以不必考虑所有的可能的顺序，而代之以仅考虑原来的CSS显示的几个猴所有的周期的移位的几个可能的顺序。此外，在上述实施例中，阈值设定为0.75，但是，该阈值也可以设定为不同的电平。例如，在阈值设定为零时，就通过几个或所有的可能的顺序的分析进行所有的匹配。因此，与阈值大于零的情况相比，将增加必要的计算量，但是，尖峰已进行了分类，峰值的x坐标已对特定的开始点或目标旋转进行了调整，所以，与未进行这样的调整的原来的系统相比，所需要的计算量还是降低了。因此，通过将阈值设定为零，可以减少若干计算，检索性能和原来的系统完全相同。

或者，将阈值设定为1时，使用仅保存的顺序进行匹配。这时，检索精度只降低一点点，却可以显著地减少所需要的计算量。

对于上述实施例，可以进行各种各样的变更。例如，也可以利用其他的分类方法，取代实施例1和实施例2说明的CSS尖峰的总坐标值的分类。也可以按例如尖峰的高度升高的顺序配置总坐标值，取代按尖峰的高度降低的顺序进行配置。也可以在匹配步骤中进行分类，而取代将分类的值保存在数据库中。

产业上利用的可能性

本发明的系统，可以设置在例如图像程序库中。或者，数据库可以通过因特网那样的网络利用电话线的暂时的链接与控制装置连接，配置在距离系统的控制装置远的地方。例如，图像数据库和描述符数据库可以设置在永久存储装置或ROM及DVD那样的便携式的存储媒体中。

以上说明的系统的结构要素，可以用软件或硬件的形式进行设置。以上用计算机系统的形式说明了本发明，但是，本发明也可以使用专用芯片等用其他形式来实现。

以上给出了表示目标的2D形状的方法和计算表示2个形状间的类似度的值的方法的特定的例子，但是，同样也可以使用任意的适当的方法。

例如，为了确认的目的，进行目标图像的匹配或进行环形滤波也可以使用本发明。