CN1329730A

CN1329730A - 从一个集合的图象对象识别相互关联的图象对象的子集的方法和设备

Info

Publication number: CN1329730A
Application number: CN99814278A
Authority: CN
Inventors: 阿伦·楚－I·杨
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1998-12-09
Filing date: 1999-12-07
Publication date: 2002-01-02
Anticipated expiration: 2019-12-07
Also published as: US6512850B2; IL141962A0; JP2002532786A; PL347828A1; KR100491801B1; TWI237776B; EP1141865A1; AU1577400A; KR20010089462A; WO2000034893A1; US20020097914A1; CN100437558C

Abstract

在给出的一个例子中,从一个输入装置接收用于识别一个集合的图象对象的图象对象之间的相互关联的一个查询。把该集合的所有图象对象之间的多个相似度值与来自该查询的阈值标准相比较。根据比较产生并在一个可视输出装置上可视地显示图象对象标识符的簇。

Description

从一个集合的图象对象识别相互关联的图象对象的子集的方法和设备

本发明一般地说涉及识别一组图象对象中的图象对象，且更具体地说涉及从一个集合的图象对象中识别彼此相关的图象对象。

按照图象内容的查询(QBIC)是一种有用的技术，它允许客户根据诸如平均颜色、颜色分布、颜色布局、以及组构的视在特性，来查询一个图象的集合。已经有若干描述QBIC的出版物；例如，纽约Armonk的IBM公司提供的“图象研究客户指南和参考”(Image Search User′s Guide and Reference，Version2.0.1(1997)，以及1996年11月26日颁布给Barber等人的美国专利第5,579,471号“图象查询系统和方法”。

在采用QBIC技术的一个系统中，可用于搜索的图象对象的数目可能是非常大的，使得难于确认和理解集合的整个内容。不幸的是，传统技术还未提供一种适当的装置来分析一个图象的集合以理解这些图象的分类。即，传统的图象查询本身所提供的(如果有的话)“视在发掘”能力非常小。形成一组图象之间的相互关系的能力，对于某些行业，诸如广告代理机构、动画制作公司等，是非常重要的。

因此，希望提供用于以一种解析的方式对图象进行簇合(cluster)从而理解它们内在的性质的装置。

在此描述的一种方法和设备提供了用于从一个集合的图象对象识别相互关联的图象对象的一个子集的一种装置。在一个例子中，用于识别一个集合的图象对象的图象对象之间的相互关联性的一个查询得到接收。该集合的图象对象之间的多个相似度值的每一个都与来自查询的阈值标准进行比较。根据比较可生成图象对象标识符的若干个簇。

本专利的文件包含了以彩色执行的至少一个图(图8-13)。带有彩色附图的本专利的复本可以在提出请求并支付了所需的费用之后从专利与商标局获得。

图1是包括一个客户、一个库服务器、以及一个对象服务器的一个计算机系统的框图。

图2是图1的计算机系统中包括的图象搜索服务器的框图。

图3是用于从一个集合的图象对象识别相互关联的图象对象子集的一种设备的框图。

图4是描述从一个集合的图象对象识别相互关联的图象对象的子集的一种方法的流程图。

图5A是簇合图象对象标识符的一种优选方法的一个第一流程图，该第一流程图更为具体地描述了一种簇初始过程。

图5B是优选的簇合方法的一个第二流程图，该第二部分更为具体地描述了一种初级比较过程。

图5C是优选的簇合方法的一个第三流程图，该第三部分更为具体地描述了一种次级或扩展比较过程。

图6是根据33个图象对象的一个具体集合产生的一个相似度矩阵的一个例子。

图7是一个表，显示了根据图5A、5B和5C的关系中描述的优选方法和图6的相似度阵列而生成的用于给定的阈值标准的图象对象标识符的簇。

图8是采用的33个图象对象的第八个图象对象的一种颜色显示，该第八个对象是以与图7的表中的阈值等级90相关的第一号簇标明的。

图9是采用的33个图象对象的第十个图象对象的一种颜色显示，该第十个对象是以与图7的表中的阈值等级90相关的第一号簇标明的。

图10是采用的33个图象对象的第27个图象对象的一种颜色显示，该第27个对象是以与图7的表中的阈值等级90相关的第一号簇标明的。

图11是采用的33个图象对象的第30个图象对象的一种颜色显示，该第30个对象是以与图7的表中的阈值等级90相关的第四号簇标明的。

图12是采用的33个图象对象的第31个图象对象的一种颜色显示，该第31个对象是以与图7的表中的阈值等级90相关的第四号簇标明的。

图13是采用的33个图象对象的第32个图象对象的一种颜色显示，该第32个对象是以与图7的表中的阈值等级90相关的第四号簇标明的。

图14是采用的33个图象对象的第13个图象对象的一种颜色显示，该第13个对象不是以与图7的表中的阈值等级90相关的第一或四号簇标明的。

图1是具有一个客户102、一个库服务器104、以及一个对象服务器106的计算机系统100的框图。在所示的实施例中，计算机系统100是基于IBM公司提供的数字库(DL)布局的。DL目前是基于一种三角客户/服务器模型的，该模型包括库服务器104、一或多个诸如对象服务器106的对象服务器、以及诸如客户102的一或多个用户。IBM的DL在IBM公司提供的Image Search User′s Guide andReference，Version2.0.1(1997)中得到了描述，该参考文献在此被引用。

回顾在这样的环境下的某些传统方面，客户102通常包括一个处理器108和一个用户界面110。用户界面110包括用于向处理器108传送数据(诸如指令和用户数据)的一个输入装置112；用户可在输入装置112输入图象查询。用户界面110还包括一个可视输出装置114，用于通过处理器108并响应于来自用户界面110的指令和/或查询而可视地显示诸如存储在对象服务器106中的图象对象的数据。客户102可以是传统的桌面计算机，其中输入装置112包括一个计算机键盘，且可视输出装置114包括一个视频显示监视器。输入装置112还可包括一个计算机鼠标器和该视频显示监视器，用于输入指令和用户数据。

库服务器104管理DL目录信息、利用各种搜索技术来定位存储的对象、提供对集合中的对象的安全访问、并与诸如对象服务器106的对象服务器进行通信。库服务器104利用一种相关数据库来管理数字对象，并通过保持索引信息和控制对存储在对象服务器上的对象的访问而提供数据的完整性。该数据库可以是例如由IBM公司提供的IBM DB2通用数据库，或由Oracle公司提供的Oracle。库服务器104可在例如IBM提供的Advanced Interactive excutive(AIX)或微软公司提供的视窗或IBM公司提供的OS/2上运行。

对象服务器106是用于存储计算机系统100中的图象对象的存储部分。用户通过由库服务器104路由的请求，对象服务器106存储和从其获取图象对象。对象服务器106根据通过一种系统管理程序而定义的存储管理实体(诸如容积)，而管理存储的资源。对象服务器106上的一个数据库包含有关各个对象的准确位置的数据。该数据库可以是例如IBM DB2通用数据库或Oracle。

现在参见图2，一个图象搜索服务器202采用了传统的“按照图象内容查询”(QBIC)技术来帮助借助一定的视在性质(诸如颜色和组构)而在图象对象上进行搜索。图象搜索服务器202可在例如AIX或Windows NT上运行。图象搜索服务器202分析图象并把图象信息存储在多个图象搜索数据库204中，诸如图象搜索数据库206。诸如图象搜索数据库206的各个图象搜索数据库都保持有多个图象搜索目录208。诸如图象搜索目录210的各个图象搜索目录存储与图象的一个集合的视在特征(诸如视在特征212)相应的数据。

多个图象搜索目录208中的每一个都存储有关四个图象搜索特征中的一或多个特征的信息：(1)平均颜色；(2)直方图颜色；(3)定位颜色；以及(4)组构。平均颜色是被图象中的象素数目所除的一个图象中的所有象素的颜色值之和。具有类似的主导颜色的图象具有类似的平均颜色。例如，包含相等的红和黄部分的图象将具有橙色的平均颜色。直方图颜色对一个图象的颜色分布的百分比进行度量，且直方图分析分别度量了一个图象中的不同的颜色。例如，乡村的图象具有呈现出高频率的蓝、绿和灰的直方图。定位颜色度量在图象的一个指定区域中的可能的平均颜色值。组构度量图象的粗糙度、对比度、以及方向性。粗糙度表示了一个图象中重复的项的尺寸；对比度标明了图象中的亮度变化；且方向性表示了方向在一个图象中是否占据主导。例如，一个木材纹理图象与包含木材纹理的其他图象具有类似的组构。

图1的客户102的用户能够利用图象的视在性质而执行传统的图象查询，以匹配颜色、组构、和它们的位置，而不需要用词汇来描述它们。基于内容的查询能够与用于图象和多媒体数据库的有用获取方法的文本和关键字相结合。一个图象查询包括了一个字符串，该字符串指定了一个图象搜索的搜索标准。该搜索标准通常包括(1)一个特征名，它指定了搜索中将要使用的特征；(2)一个特征值，它对应于采用的特征的值；(3)一个特征权，它表示了当计算评分和返回结果时对该特征的强调；以及(4)一个所希望的结果的最大数。

图象搜索服务器202被用作用于发现这些图象的搜索引擎。图象搜索客户应用产生图象查询，运行它们，并随后评价图象搜索服务器202送回的信息。在一个应用能够借助内容而搜索图象之前，该图象必须在多个目录208中的一个中被编入索引，且该内容信息必须被存储在这些数据库之一中。通常，客户102把一个请求送到库服务器104，而库服务器104把该请求送到对象服务器106并响应于该顾客的该请求。对象服务器106随后响应库服务器104的该请求，并把请求的数字数据对象送给客户102。

更具体地说，客户102建立一个QBIC查询串并将它送到图象搜索服务器202。图象搜索服务器202接收该查询串并搜索目录中的图象以寻找匹配。客户102接收以标识符和等级的一个列表的形式的匹配。用于各个匹配图象的这些标识符可由一个项ID、一个部分号、以及一个RepType组成。随后，客户102从库服务器104请求该图象部分。库服务器104请求对象服务器106把指定的图象部分送到客户102。对象服务器106传送这些图象部分，且客户102确认对它们的接收。客户102随后可把一个图象显示在可视输出装置114上。

图3显示了用于从一个集合的图象对象识别相互关联的图象对象的子集的一种设备300的软件和硬件组件的的框图。优选地，设备300被包括在上述传统的环境中。设备300一般包括上述的用户界面110、一个(或多个)存储器302、以及一个(或多个)处理器304。图象数据306和与图象数据306对应的图象特征数据308被存储在存储器302中。图象数据306包括一个集合的图象对象，且图象特征数据308包括各个图象对象的图象特征的一个集合。图象对象可以是例如用于产生视频图象的数据文档。该集合的图象对象通常包括大量的图象对象(10、100、1000个等)；然而，该集合也可包括较少的数目，诸如至少四个图象对象。

处理器304用于执行计算机软件编码，该编码在此包括一种相似度矩阵发生器316和一种簇发生器318。相似度矩阵发生器316包括一种图象特征比较器317，它可把各个图象对象的图象特征数据308与存储在图象数据306中的所有其他图象对象的图象特征数据308进行比较。优选地，图象特征比较器316可响应于在输入装置112处的一种专门的查询而进行操作。图象特征比较器316产生相似度矩阵数据310，该数据包括多个相似度值或相似度等级。因此，相似度矩阵发生器316可被称为相似度值发生器或相似度等级发生器。多种相似度值包括各个图象对象的图象特征与该集合中的所有其他图象对象之间的相似度。

簇发生器318包括一个数据比较器320和一个簇分配器322。数据比较器320具有一个接收来自相似度矩阵310的多个相似度值的一个第一数据输入端和用于接收阈值标准数据312的一个第二数据输入端。数据比较器320把相似度矩阵310的多个相似度值中的每一个与阈值标准数据312进行比较，优选地是以以下所述的方式进行比较。

簇分配器322用于与数据比较器320相关地产生簇数据314。簇数据314包括图象对象标识符的至少一个簇，该簇可对应于图象数据306的图象对象的一个子集。优选地，簇分配器322以这样的方式产生簇，即一个簇中的各个图象对象标识符与具有这样一个相似度值的一个图象对象相关，即该相似度值相对于该簇中识别的至少一个其他的图象对象满足了阈值标准数据312。簇数据314可被可视地显示在可视输出装置114上。借助这种信息，与一或多个簇中的图象对象标识符对应的图象对象随后可被方便地获取和可视显示在可视输出装置114上。

图4是一个流程图，它描述了从一个集合的图象对象识别相互关联的图象对象的子集的一种方法。以下结合地参见图3和4。在一个起始框400，作为一种专门查询的一部分而从输入装置112接收用户数据或输入(步骤402)。该用户数据包括阈值标准数据312，或者阈值标准数据312至少以某些适当的方式对应于用户数据，或者阈值标准数据312从用户数据导出或获得。用户数据或阈值标准数据312可以是或包括例如一种阈值等级或一种阈值等级范围。例如，一种专门查询可以得到执行，该专门查询在实质上查询“集合的哪些图象对象足够地类似从而满足90-100的阈值等级范围？”。作为另一个例子，一种专门查询可得到执行，它在与这样的查询对应的阈值标准数据312被预定(例如90-100或80-100)的情况下在实质上查询“哪些图象对象具有非常类似的视在特征？”。

用户数据还可包括从可获得的图象特征的整个集合中选出的图象特征。例如，该专门查询可在实质上查询“哪些图象对象只相对于平均颜色和组构特征具有彼此之间的90-100的阈值等级范围？”

响应于对该查询和用户数据的接收，图象特征比较器317把与各个图象对象相关的图象特征数据308同与该集合的所有其他图象对象相关的图象特征数据308进行比较(步骤404)。优选地，对与这些图象对象相关的至少两种特征进行比较，这些特征可以是用户选定的特征。根据这些比较，相似度矩阵数据310得到产生(步骤406)。相似度矩阵数据310的各个相似度值对应于该集合的每两个图象对象的图象特征之间的一个比较。优选地，步骤404和406通过利用适当的或选定的图象特征为每一个图象对象执行一种传统的图象查询陈述(statement)，而得到进行。

随后，数据比较器320把相似度矩阵310的各个相似度值与阈值标准数据312进行比较(步骤408)。相似度矩阵数据310的各个相似度值要么满足阈值标准数据312，要么不满足它。根据这样的结果，簇分配器322把图象对象标识符逻辑关联或组合成簇(步骤410)。优选地，簇发生器318产生簇，从而使各个簇的图象对象标识符对应于这样的图象对象，即这些图象对象相对该簇中的至少一个其他的图象对象标识符满足该阈值标准。还优选的是，各个图象对象标识符唯一地与一个单个的簇相关(或不与任何簇相关)。

最后，图象对象标识符的簇被可视地显示在可视输出装置114上(步骤412)。显示的图象对象标识符可以是对相关的图象对象的任何适当的标识，诸如文档名、文档号、图象ID、或者甚至是图象本身。优选地，各个簇的图象对象标识符以密切物理相关的方式被一起显示在可视输出装置114上，以便于识别各个簇。该流程图结束于一个结束框414，表明该具体查询和查询响应的结束。该方法优选地在步骤402继续，在那里输入另一专门查询的用户数据。

现在参见图6，其中以矩阵形式显示了根据33个选定的图象对象的一个集合的所有四个视在特征而产生一个相似度矩阵600的一个例子。这33个图象对象中的一些在图8-14中得到表示(并在以下得到描述)，并被具体选出以有助于进行描述。为了清楚起见，由于所分析的图象的数目较大，没有显示所有33个图象对象。为分析而选出的这33个图象对象每一个都提供了一或多只花的不同的图象。

如图6所示，相似度矩阵600未被可视地显示为具有N＝M×M个相似度值的一个完全的M乘M矩阵。相反地，相似度矩阵600由一个集合的M个图象对象之间的非冗余相似度值组成。换言之，只为该集合的两图象对象的各个唯一的组合产生相似度值。图4中还显示了相同的图象对象之间的无用的相似度值(每一个都具有值“100”)，它们只是矩阵中的占位符。虽然这样的矩阵尽量地减少了数据和执行，应该理解的是，可以产生和执行冗余和/或无用的相似度值(并随后用软件例如忽略或“过滤”它们)。然而，优选地，在步骤304不进行冗余的比较，在步骤306不产生冗余的相似度值，且在步骤304和306不执行冗余的图象查询。因此，为一个集合的M个图象对象产生的相似度值的数目优选地是N＝M！/(2×(M－2)！)＝M×(M－1)/2，或者至少是该数目。例如，如图3(其中M＝33)所示，产生了至少528个相似度值(M×(M－1)/2＝33×(33－1)/2＝528)。

现在参见图7，其中显示了相对于各种阈值标准的基于图6的相似度矩阵600的一种簇表700。簇表700中的簇根据结合图5A、5B和5C而描述的簇合方法而产生，这将在以下进行详细描述。与90-100的阈值范围相关的四个簇包括簇1(图象对象标识符8、10和27)、簇2(图象对象标识符15和19)、簇3(图象对象标识符25和33)、以及簇4(图象对象标识符30、31和32)。另外，例如与80-100的阈值范围相关的一个簇由图象对象标识符6、17、22和23组成。对于各个簇，可产生并与各个簇相关地可视显示如图7中所示的一种连结指标(cohesion index)(它在此是与簇中的图象对应的相似度值的一个平均值)。

虽然可响应于请求图象对象之间的所有关系的一种专门查询而产生并可视显示诸如簇表700的簇表的全部或部分，优选的是只产生并显示满足一种具体的阈值范围的簇(例如与查询的阈值范围90-100相关的簇1至4)。

如以上较早时描述的，图8-14显示了所用的33个图象对象的某些图象对象的彩色图象。目前，这些图象对象(它们具有文档名flower01.jpg，flower02.jpg等)可从因特网上的网址http：//wwwqbic.almaden.ibm.com下载。为了使读者能够适应图8-14的黑白复本，提供了按照以下的颜色关键字大体指示图象中的颜色区的标号：

标号	颜色
标号	颜色	802	白
804	黄	802	白
804	黄	806	红
808	粉	806	红
808	粉	810	橙
812	绿	810	橙
812	绿	814	兰
816	褐	814	兰
816	褐	818	灰
820	黑	818	灰

图8、9和10分别表示了与图7的簇表700中的第一号簇(阈值＝90)的图象对象标识符8、10、和27分别对应的图象对象。请注意图8-10中表示的图象对象的视在特征之间的相似度(例如平均颜色、定位颜色等)。

图11、12和13表示了与图7的簇表700中的第四号簇的图象对象标识符30、31和32分别对应的图象对象。请注意图11-13中表示的图象对象的视在特征之间的相似度。还请注意图11-13所示的簇4的视在特征与图8-10的簇1的视在特征之间的不相似性。

图14是与一个图象对象标识符13对应的一个图象对象，它未在图7的簇表700的簇1(具有分别相对于图象对象标识符8、10和27的相似度值0、0和0，如图6所示)或簇4(具有分别相对于图象对象标识符30、31和32的相似度值6、11和6，如图6所示)中得到标识。请注意图14的与图8-10和图11-13的各个子集之间的视在特征的不相似性。

以下以C++编程语言的形式描述产生一种相似度矩阵(诸如图6所示的)的一种优选且更为具体的实施方式。这种具体的实施方式可被用在图4的步骤404和406。虽然文档名和文档号等是以“硬编码”(hardcoded)的形式显示的，应该理解且优选的是，它们可以是各种形式的。

在把该相似度矩阵公式化的准备中，可采用诸如或类似于以下的编码，为每一个图象对象起始一个集合的传统的查询：

 　　cmd[0]＝″QbColorFeatureClass file＝
＜client，\″e:\\usr\\local\\qbic\\html\\images\\ibm\\flower01.jpg\″＞″；

　　 cmd[0]＝cmd[0]+″and QbTextureFeatureClass file＝
＜client，\″e:\\usr\\local\\qbic\\html\\images\\ibm\\flower01.jpg\″＞″；

　　 cmd[0]＝cmd[0]+″and QbDrawFeatureClass file＝
＜client，\″e:\\usr\\local\\qbic\\html\\images\\ibm\\flower01.jpg\″＞″；

　　 cmd[0]＝cmd[0]+″and QbColorHistogramFeatureClass file＝
＜client，\″e:\\usr\\local\\qbic\\html\\images\\ibm\\flower01.jpg\″＞″；

　　 cmd[1]＝″QbColorFeatureClass file＝
＜client，\″e:\\usr\\local\\qbic\\html\\images\\ibm\\flower02.jpg\″＞″；

　　 cmd[1]＝cmd[1]+″and QbTextureFeatureClass file＝
＜client，\″e:\\usr\\local\\qbic\\html\\images\\ibm\\flower02.jpg\″＞″；

　　 cmd[1]＝cmd[1]+″and QbDrawFeatureClass file＝
＜client，\″e:\\usr\\local\\qbic\\html\\images\\ibm\\flower02.jpg\″＞″；

　　 cmd[1]＝cmd[1]+″and QbColorHistogramFeatureClass file＝
＜client，\″e:\\usr\\local\\qbic\\html\\images\\ibm\\flower02.jpg\″＞″；

等等。各个图象对象相对该集合的所有其他图象的相似度值的比较和产生，可以结合传统的查询，而以如下的方式得到执行：

for (i＝0；i＜33；i++)
{
   pCur＝dsQBIC->execute(cmd[i])；
   cout＜＜″qbic query[″＜＜I＜＜″]done...″＜＜endl；
   while(pCur->isValid())
   {

　　  item＝pCur->fetchNext()；

　　  if(item ！＝0)

　　  {

　　     for(j＝l；j＜＝item->dataCount()；j++)

　　     {

　　        a＝item->getData(j)；

　　        strDataName＝item->getDataName(j)；

　　        switch(a.typeCode())

　　        {

　　           case DKAny：：tc_string：

　　           {

　　              strData＝a；

                //cout ＜＜″Attribute name：″＜＜strDataName＜＜″
Value：″＜＜strData＜＜endl；

               break；

            }

            case DKAny：：tc_long：

            {

               long lVal＝a；

               strData＝DKString(lVal)；

               //cout ＜＜″Attribute name：″＜＜strDataName＜＜″
Value：″＜＜strData＜＜endl；

               if(strDataName＝＝DKString(″DKPartNo″))

                 id＝strData.asUnsigned()；

                 if(strDataName＝＝DKString(″DKRank″))

                   rank＝strData.asUnsigned()；

                break；

             }

          }

       }

       S[id-10][i]＝rank；delete item；

    }
   }
   delete pCur；
}

图5A、5B和5C是描述采用一种优选的相似度矩阵的图象对象标识符簇合方法的流程图。该优选方法可被用于图4的流程图的步骤408和410。图5A描述了一种簇起始处理过程；图5B描述了采用一种“初级”比较的簇合处理；且图5C描述了采用一种“次级”或“扩展”比较的簇合处理。

在分析与图5A、5B和5C相关的流程图之前，最好先以用于形成单个的簇的简短且一般化的例子，描述优选的初级和扩展的比较处理。响应于一个专门查询，对该阈值标准与一个第一图象对象与一个第二图象对象之间的一个相似度值进行一个初级比较。如果该相似度值未达到该阈值标准，则进行之间该阈值标准与第一图象对象与另一个图象对象之间的一个相似度值的下一个初级比较。如果在该初级比较中该相似度值达到了该阈值标准，与第一图象对象和第二图象对象相关的图象对象标识符被组合成一个第一簇，且发生了一种扩展比较。该扩展比较是在该阈值标准与第二图象对象与一个第三图象对象之间的一个相似度值之间进行的。如果在该扩展比较中该相似度值未达到该阈值标准，则进行该阈值标准与第二图象对象与另一图象对象之间的一个相似度值之间的下一个扩展比较。如果在该扩展比较中该相似度值达到该阈值标准，则与第三图象对象相关的一个图象对象标识符与其他图象对象标识符被组合成第一簇。在与第二图象对象(以及潜在的其他图象对象)相关的扩展比较被完成之后，与第一图象对象相关的初级比较被继续进行至完成，直到完全形成了第一簇。

现在参见图5A，簇初始化处理可以用以下逻辑描述(其中M＝该集合中的图象对象的数目)：对于各个图象对象J，其中J＝1至M

把与一个图象对象J相关的一个图象对象标识符分配给一个簇J

图5B中所示的该初级比较簇合处理可由以下逻辑表示(注意该逻辑描述不包括与框550或框B(它与扩展比较相关)对应的处理)：对于各个图象对象J，其中J＝1至M：

对于图象对象J与一个图象对象I之间的各个相似度值，其中I＝

J＋1至M：

把图象对象I与J之间的相似度值同阈值标准进行比较。

如果图象对象I与J之间的相似度值达到该阈值标准：

把与一个簇I相关的任何图象对象标识符分配给簇J。

在分配之后，把该簇I置于一个空的集合。

图5C所示的该扩展比较簇合处理可用以下的逻辑描述：如果图象对象I与J之间的相似度值满足了阈值标准：

对于图象对象I与一个图象对象K之间的各个相似度值，其中K

＝1至M但不是K＝J或K＝I：

把图象对象I与K之间的相似度值与该阈值标准进行比较。

如果图象对象I与K之间的相似度值满足该阈值标准：

把与一个簇K相关的任何图象对象标识符分配给簇J。

在分配之后，把簇K置于一个空的集合。

图5A、5B和5C的流程图优选地被结合，并形成了用于簇合的单个的方法。另外，与图5A、5B和5C相结合地描述的方法可被具体应用于一种优选的相似度矩阵构造，诸如图6中的相似度矩阵600所示的，其中以如下方式利用了一种行/列方式(其中M＝集合中的图象对象数目，T＝一个阈值等级，且S是与一个行和一个列相关的两个图象对象之间的一个相似度值(诸如与行I和列J相关的两个图象对象之间的SI、J))：对于J＝1至M

把图象IJ分配给簇CJ，或CJ＝{IJ}结束对于J＝1至M

对于I＝(J＋1)至M

(识别与图象IJ类似的图象II，其中SI、J＞＝T)

如果SI、J＞＝T (初级比较)

则

把CJ和CI合并到CJ中，或CJ＝CJ＋CI

把CI置于一个空集合，或CI＝{}

对K＝(I＋1)至M

(识别与图象II相似的图象IK，其中SK、I＞＝T)

如果SK、I＞＝T (扩展比较A)

则

把CJ和CK合并到CJ中，或CJ＝CJ＋CK

把CK置于一个空的集合，或CK＝{}

结束

对K＝1至(I－1) (扩展比较B)

(识别与图象II相似的图象IK，其中SI、K＞＝T)

如果(K＜＞J且SI，K＞＝T)

则

把CJ和CK合并成CJ，或CJ＝CJ＋CK

把CK置于一个空集合，或CK＝{}

结束

结束结束

与图5、5B和5C结合地描述的优选方法由图3的簇发生器318执行。通过执行这种方法，簇发生器318以这样的方式产生簇，即各个簇中的各个图象对象标识符对应于一种图象对象-该图象对象相对于在同一簇中识别的至少一个其他的图象对象达到了该阈值标准。另外，各个图象标识符只与一个簇唯一地相关，或者不与任何簇相关。簇合处理可能不产生相互关联的图象对象的簇(一个空集合)，当图象对象彼此非常不同和/或阈值标准非常大或特殊时就可能发生这种情况。各个簇中的某些图象对象标识符可能对应于相对该集合中识别的其他图象对象不满足该阈值标准的图象对象。例如，一个簇中的一个第一图象对象可能相对于该簇中的一个第二图象对象而满足该阈值标准，该第二图象对象可能相对于该簇中的一个第三图象对象而满足该阈值标准，但第一和第三图象对象相对于彼此可能不满足该阈值标准。

很多其他适当的簇合方法是容易理解和显而易见的。例如，虽然与一个单个的扩展比较结合的一个初级比较是优选的，簇合也可利用一个初级比较和多个扩展比较(甚至多至一个最大极限)或只利用一个初级比较而得到执行。例如，在另一替换实施例中，簇是这样产生的，即使得各个簇的各个图象对象标识符相对于在同一簇中识别的所有其他图象对象满足了该阈值标准。

再参见图6，在相似度矩阵600中，与根据90-100的一个阈值值范围产生的四个簇相关的四个相似度值组得到了识别。一个相似度值组602(它包括相似度值90、92和93)与由图象对象标识符8、10和27组成的一个簇(与图7中的阈值＝90和图8、9和10中的图象对应的簇1)相关；一个相似度值组604(它包括一个相似度值91)与由图象对象标识符15和19组成的一个簇(图7中的与阈值＝90对应的簇2)相关；一个相似度值组606(它包括一个相似度值90)与由图象对象标识符25和33组成的一个簇(图7中的与阈值＝90对应的簇3)相关；且一个相似度值组608(它包括相似度值91、92和91)与由图象对象标识符30、31和32组成的一个簇(图11、12和13中的和图7中的与阈值90对应的簇4)相关。

与不同的阈值范围(阈值范围＝80-100)相关地，一个相似度值组610(它包括相似度值81、83和89)与由图象对象标识符6、17、22和23组成的一个簇(图7中的与阈值80对应的簇4)相关。对于这种簇4，注意图象对象标识符23具有相对于各个图象对象标识符17和22(相似度值分别为83和89)超过了80的一个阈值，但相对于图象对象标识符6(相似度值75)则不是这样。然而，图象对象标识符22相对于图象对象标识符6(相似度值为81)则具有超过该阈值的相似度值。

与对应于相似度值组602、604、606、608和610的上述簇相关的图象对象标识符，根据图5B的初级比较处理的执行，而得到簇合，且在某些情况下根据图5B和5C的初级和扩展比较处理而得到簇合。

本发明人理解到，且本领域的技术人员应该理解的是，在权利要求书所限定的本发明的范围之内，在此描述的方法和设备能够以各种方式得到修正。例如，虽然在此具体应用中描述了图象对象，其他复杂的数据对象(声频、视频等)也可按照相同或类似的方式得到处理。作为另一个例子，在此描述的图象特征之外的图象特征可被加到与图象对象相关的已有的特征集合中，并被用于本发明中。

作为再一个例子，一或多个相似度矩阵(每一个用于图象特征的整个集合和各个不同的子集)可得到产生并在一个给定的查询之前被存储在存储器中。类似地，一个簇表或多个簇表(诸如图7的簇表700)可得到产生并在该给定查询被存储在存储器中。在此，这样的矩阵和/或簇表的更新和保持，可在一个图象对象的每一个新输入项被输入到数据库之后进行。这种保持可以手动或由系统自动进行。例如，系统可响应于新的输入项而立即进行保持，或者以预定的周期进行保持，或者在已经进行了新的输入时以预定的周期进行。即，这样的矩阵和/或簇表可响应于不同于查询请求的一个单个的请求(例如一个管理维护请求)而得到产生。

因此，对传统图象查询技术的这种图象簇合的改进，大大地改善了“视频发掘”能力。本发明优选地提高了IBM的数字库(DL)产品提供的QBIC技术的已经非常强大的能力。这种提高对于数字形象化是非常实用的；它帮助用户理解图象的一个集合之间的相互关联。查询这样的相互关联的能力，在诸如广告代理商、动画制作公司等的某些种类的商业中是非常重要的。

根据本发明，用于从一个集合的图象对象识别相互关联的图象对象的子集的一种方法包括：把该集合的各个图象对象的图象特征与该集合的所有其他图象对象的图象特征进行比较；对各个比较产生一个相似度值；以及，识别该集合的相互关联的图象对象的子集，其中在一个子集中识别的各个图象对象具有相对于同一子集中识别的至少一个其他图象对象来说满足了阈值标准的一个相似度值。

上述实施例可进一步包括：把该阈值标准与每一个相似度值相比较。

上述方法可进一步包括：接收与该阈值标准相关的用户输入；以及，可视地显示相互关联的图象对象的子集的标识。

在上述实施例中，比较的图象特征可响应接收该用户输入。

根据上述的一种设备，进一步包括：存储器，用于存储该集合的图象对象以及与其相关的图象特征；一个输入装置，用于接收用于从该集合的图象对象识别至少一个子集的相互关联的图象对象的该查询；以及，一个可视输出装置，用于可视地显示与该至少一个子集的相互关联的图象对象对应的至少一个子集的图象对象标识符。

一种图象对象标识符的簇合方法，包括：(a)把阈值标准与第一组多个相似度值中的每一个进行比较，该第一组多个相似度值是一个第一图象对象与一个集合的其他图象对象之间的；(b)响应于(a)中的比较产生的该第一图象对象与一个第二图象对象之间的一个相似度值满足了该阈值标准的判定，把该阈值标准与一个第二组多个相似度值中的每一个进行比较，该第二组多个相似度值是该第二图象对象与该集合的其他图象对象之间的；以及

(c)响应于(b)中的比较所产生的该第二图象对象与一个第三图象对象之间的一个相似度值满足了该阈值标准的判定，把与该第一、第二、和第三图象对象相关的图象对象标识符逻辑组合成一个簇。

上述方法可进一步包括：

(d)接收来自一个输入装置的查询，该查询与该阈值标准相关；以及

(e)在一种可视输出装置上可视地显示该这些图象对象标识符的该逻辑组合。

在上述方法中，(a)中的比较响应于(d)中对查询的接收。

上述方法进一步包括：响应于(d)中对查询的接收产生该第一和第二组多个相似度值。

一种计算机软件产品，包括：相似度值发生器编码，所述相似度值发生器编码可得到执行而响应于一个单个的请求而为至少四个图象对象组成的一个集合的每一个图象对象和所有其他的图象对象产生一个相似度值。

上述计算机软件产品可进一步包括：一种簇发生器编码，所述簇发生器编码可得到执行以根据该相似度值和阈值标准而产生图象对象标识符的至少一个簇。

上述计算机软件产品可进一步包括：所述相似度值发生器编码的图象特征比较器编码。

上述计算机软件产品可进一步包括：所述簇发生器编码的数据比较器编码，所述数据比较器编码可得到执行以比较该相似度值和阈值标准；以及，所述簇发生器编码的簇分配编码，所述簇分配编码可以与所述数据比较器编码相联系地得到执行。

在上述计算机软件产品中，该相似度值发生器编码包括一种编码，该编码可得到执行以对于各个图象对象相对于该集合的所有其他图象对象而产生一种图象查询。

Claims

1.一种设备，包括：

一个相似度值发生器(316)，用于产生一个集合的图象对象的所有图象对象的图象特征之间的相似度值；以及

一个簇发生器(318)，用于根据该相似度值和与一个查询相关的阈值标准产生至少一个子集的图象对象标识符。

2.用于从一个集合的图象对象识别相互关联的图象对象的子集的一种方法，包括：

把该集合的各个图象对象的图象特征与该集合的所有其他图象对象的图象特征相比较(404)；

为各个比较产生一个相似度值(406)；以及

识别该集合的相互关联的图象对象的子集(410)，其中在一个子集中识别的各个图象对象具有相对于在同一子集中识别的至少一个其他图象对象满足阈值标准的一个相似度值(408)。

3.簇合图象对象标识符的一种方法，包括：

(a)把阈值标准(312)与第一组多个相似度值(310)中的每一个进行比较(320)，该第一组多个相似度值是一个第一图象对象与一个集合中的其他图象对象之间的；

(b)响应于来自(a)的比较的该第一图象对象与一个第二图象对象之间的一个相似度值(310)满足该阈值标准的判定，把该阈值标准与一个第二组多个相似度值中的每一个进行比较，该第二组多个相似度值是在该第二图象对象与该集合中的其他图象对象之间的；以及

(c)响应于来自(b)的该第二图象对象与一个第三图象对象之间的一个相似度值满足该阈值标准的判定，把与该第一、第二、和第三图象对象相关的图象对象标识符逻辑组成(318)一个簇(314)。

4.用于产生图象对象标识符的簇的软件，包括：

初级比较软件，它可得到执行以把阈值标准与一个第一组多个相似度值中的每一个相比较，该第一组多个相似度值是在一个第一图象对象与该集合中的其他图象对象之间的；以及

次级比较软件，它可响应于来自所述初级比较软件的该第一图象对象与一个第二图象对象之间的一个相似度值满足了该阈值标准的判定而得到执行，所述次级比较软件可得到执行以把该阈值标准与一个第二组多个相似度值中的每一个进行比较，该第二组多个相似度值(310)是在该第二图象对象与该集合中的其他图象对象之间的。

5.一种计算机软件产品，包括：

相似度值发生器编码，它可得到执行以响应于一个单个的请求而为至少四个图象对象组成的一个集合中的每一个图象对象和所有其他图象对象产生一个相似度值。

6.用于簇合与一个集合的M个图象对象相关的图象对象标识符的一种方法，包括：

对于每一个图象对象J，其中J＝1至M：

把与一个图象对象J相关的一个图象对象标识符分配给一个簇J；

对于每一个图象对象J，其中J＝1至M：

对于该图象对象J与一个图象对象I之间的各个相似度等级，其中I＝J＋1至M：

把图象对象I与J之间的该相似度等级与阈值标准相比较；

如果图象对象I与J之间的该相似度等级满足了该阈值标准：

把与一个簇I相关的所有图象对象标识符分配给一个簇J；以及

在分配之后，把簇I置于一个空集合。

7.根据权利要求1的一种设备，进一步包括：

存储器(302)，用于存储该集合的图象对象和与其相关的图象特征；

一个输入装置(112)，用于接收识别该集合的图象对象中的至少一个子集的相互关联的图象对象的查询；以及

一个可视输出装置(114)，用于可视地显示与该至少一个子集的相互关联的图象对象对应的至少一个子集的图象对象标识符。

8.根据权利要求1的设备，进一步包括：

所述簇发生器(318)的一个数据比较器(320)，所述数据比较器用于接收该阈值标准(312)和来自所述相似度值发生器(310)的相似度值；以及

所述簇发生器的一个簇分配器(322)，所述簇分配器与所述数据比较器相关地进行工作。

9.根据权利要求1的设备，包括：

所述相似度值发生器(316)的一个图象特征比较器(317)。

10.根据权利要求19的方法，进一步包括：

如果图象对象I与J之间的相似度等级满足了该阈值标准：

对于图象对象I与一个图象对象K之间的各个相似度等级，其中K＝1至M但K＝J或K＝I除外；

把图象对象I与K之间的相似度等级同该阈值标准进行比较；

如果图象对象I与K之间的相似度等级满足了该阈值标准：

把与一个簇K相关的所有图象对象标识符都分配给簇J；且

在分配之后，把簇K置于一个空集合。