多媒体数据库检索系统

摘要

一种非询问的多媒体数据库检索方法,它结合根据每个用户反应推敲其回答的贝叶斯推理工具。用户反应的设置包括一系列显示和用户操作,并由比较简单的用户介面确定的。

说明书

本发明涉及在数据库内数据存贮和检索的领域，尤其是用于检索容纳在一数据库中的多媒体数据的方法。

多媒体数据库是容纳有图像、音乐和视频数字数据的数据库，并且根据调查，它在商业和娱乐业领域中的使用正在增长。然而，多媒体数据库的广泛使用增强了对开发更有效的检索这些数据库的方法的需求。

作为已有技术，数据库是相关的数据的集合。多数情况下，在数据库中数据组织结构为表、字段和记录。通常在数据库中每个记录具有一组属性，而用户可能会希望根据这些属性的一个或多个值检索数据库。例如，在一足球统计数据库中，人们可以检索在一个赛季中所有完成拦球一百以或更多次的后卫。

在进行这样的一个检索中，假设每个记录只有几个属性，而用户要求检索具有确定属性的确定值的记录。所需要的记录的说明称作询问，而且通常限定为下面三种形式中的一种：a)说明一特定属性的一特定值的简单询问；如，转换臂＝左；或转换臂＝右；b)说明一特定属性的特定范围值的一范围；例如，权值＜220或180＜权值＜220；及c)布尔符号，如((转换臂＝左)和(高度＞6′)和(完成＞99)。

可惜，基于这些方法的询问不能解决检索多媒体数据库的问题。这是因为：①多媒体数据通常不是用文本的属性说明作注释的，②说明用户询问所需要的词汇可能不存在，或者至少是用户所不知道的。从而使已有技术已显示出在开发在按照内容进行多媒体检索方面增大了关注。例如，由P.M.Kelly和T.M.Canon在科学和统计数据库管理第七届国际工作会议文集第252-258页(1994年发表的“导航数字图像数据库比较算法”以及由J.Barros，J.French，W.Martin，P.Kelly和J.M.White于1994年10月在华盛顿特区召开的第23届美国太平洋关系学会(AIPR)图像和信息系统讨论会文集中发表的“用于按照内容检索的多光谱图像索引”。

多数已有技术，按照内容进行的图像检索系统通过目视的实例利用询问的格式以方便于从数据库中进行一项图像检索。对于这样的一个系统，连续的询问是由前面一次检索出的一组图像中引伸出来的。这是相关反馈的一种原始形式，可惜它表示出不相适应。对一图像的每次检索对应于一特定的询问，而与任何或所有的在前的检索历史无关。在这些已有技术的系统中，例如Flickner等的文章“按图像和视频内容询问：QBIC系统”，登在1995年电气和电子工程师协会(IEEE)会刊计算机分删，28(9)，23-32页，和K.Hirata等的文章“通过目视实例询问，按照内容进行的图像检索”，它首先登在数据库技术进展-EDBT′92，springer-Verlag，柏林，1992。检索的能力完全是由所采用的相似性量度确定的。这些相似性量度典型地是一组特征的加权量，这加权量经常是由用户手动确定的。

已有技术，图像检索方法和系统，特别是按照内容进行图像检索的方法和系统，可能会表现出高的虚假正象和负象的检索率，它能在搜寻所要求的图像中引起长时间推延。

根据本发明的原理以通用的贝叶斯结构为基础的图像搜索器利用相关反馈引导检索的系统和方法解决了上述问题，并作出了超过已有技术的改进。这个系统维持着后验概率分布，即在多媒体数据库中每个图像是检索目标。这个分布用于选择下一个向用户显示的图像。并从与用户有关的显示图像中征求选择。然后通过一概率统计的用户模型把用户的选择引入后验分布中。描述了由一用户选择数据库建立一用户模型的方法学。这种结构的一个区别特征是，其它相关反馈方法推敲询问，而作为本发明主题的方法却推敲回答。

本发明的讲授通过下面结合附图进行的具体描述，能够轻易地理解。

图1是用于常规贝叶斯相关反馈法的伪码表；

图2是按照本发明的原理所用具有代表性的用户界面的屏幕图像；

图3是表示3个分别的图像选择频率的曲线图；

图4是当没有图像选择被忽略时，表示3个分别的图像选择频率的曲线图。

图5是用户模型的一伪码表；

图6是表示检索成功百分比作为检索长度函数的曲线图；

图7a-7d示出了一次单一检索的4个迭代屏幕图像；

图8是一初始化模块的伪码表；

图9是一计算模块的伪码表；

图10是按照本发明原理，当从数据库中选择一用于检索的条目时，执行各步骤的流程图。

结合附图现将描述本发明的一最佳实施例，在下面的描述过程中可能会同时参照几个附图进行。

在对本发明的主题按照内容进行检索的方法和装置作完整描述之前，必须确定几个定义，特别是至少可以确定检索的三个分类。

目标检索：目标检索是一种用户试图在其中寻找一特定图像的检索。例如，一位艺术史学生可能需要寻找一幅特定的油画，或是一位摄影艺术家可能寻找他以前曾看见过的一幅特定的照片。

类别检索：类别检索是一种用户从常规的分类如：“日落”，“鸟”，一特定种类的车”，或“埃菲尔铁塔的图片”中寻找图像的一种检索方法。类别检索是与目标检索截然不同的，因为它更着重于图像的语义内容并经常需要主现上的判断。

随意浏览：随意浏览的特点在于用户至多有一个他要寻找内容的不很清楚的想法。此外，在检索的过程中，用户可以反复地改变他的想法。举一个例子，一位内景制作人员可以在开始时心中有一布置方案，但是在看了设计数据库中的图像之后，又可以按不同的方案完成。随意浏览系统的精通的用户可以不考虑任何问题。他只乐于通过数据库浏览，并对他见至的内容作出反应。

以上的三种检索分类中的每一类别对于按照内容进行的检索方法来说都是重要的，但是对于类别检索和随意浏览来说，定量地确定正确的行为方法是困难的。因此，必须集中在目标检索上，为此就有了几个供检索有效性所用的清楚的量度。两个典型的量度是：1)寻找一个目标图像和用另外的目标图像替代所需的总时间，2)直到目标被找到为止所查过的图像总数。

根据考虑的这些量度，对一种图像检索方法和系统的有效性进行的一项测试是一用户从一个大数据库中寻找单个的随意选择目标图像所经受的平均难度(经过多次试验)。熟练的技术人员对这种测试的几种变化可能易于作出评价。例如，在检索期间目标图像可以显示在图像检索界面之外的计算机监视器上。或者是目标图像可以在检索开始前仅显示一短时间间隔，然后用户必须检索记住的图像。换句话说，目标图像可能是失真的，例如是，来自数据库中的真实图像的色彩失真的硬拷贝。后面的处理过程对确定检索中失真/特征哪个重要可能会是有用的。用户在寻找目标图像经历的难度可以用不同的方法定量，即用户所需的时间量或交互作用数量(即，鼠标敲击、迭代(翻页)检索，击键等)。

现在考虑一种情况，即用户通过一系列显示/迭代操作的方式检索数据库中的特定数据。具体地说让I表示数据库。在图像搜索器的方案中，I是一组图像，但是这里所开发的基本结构也同样适用其它类型的数据。

I_t∈是正在检索的数据.

U代表正在检索目标I_t的用户。

D_k是在k次迭代期间由系统显示的信息。在图像搜索器的方案中，它是一小组图像，然而如果另外的信息被显示出的话，这个结构仍然适用。

A表示用户根据每一显示可能进行的一组操作。

这是由用户界面确定的。假设A包括一些终止检索的操作。

a_k∈A是在k次迭代中进行的操作。

考虑到这些假设，产生出一个问题，即：“给出显示/动作对的历史，什么是一给定数据的概率，I_i∈I等于目标I_t吗？为了寻找这个概率，应用了贝叶斯(Baye’s)法则，如果目标就是I_i，用概率表示，那么用户将做出给出的系列操作：

P{I_i｜a_l…a_k，D_l…D_k，U}∝P{I_i｜D_l…D_k，U}P{a_l…a_k｜I_i，D_l…D_k，U}(1)

可以假设任何给定数据就是目标的概率不依赖于用户是谁或是进行了什么样的显示序列。因此，P{I_i｜D_l…D_k，U}＝P{I_i}只不过是I_i被选作目标的先验概率。

下面，假设在每次迭代中用户的操作仅依赖于目标和当前的显示，即，它和任何先前的迭代无关。

作出上述的两种假设，结果为： $>>P>\{>>I>i>>|>>a>l>>.>.>.>>a>k>>,>>D>l>>.>.>.>>D>k>>,>U>\}>\propto >P>\{>>I>i>>\}>>>\Pi >>>k>>P>\{>>a>k>>|>>I>i>>,>>D>k>>,>U>\}>->->->->>(>2>)>>>s>$

由式(2)随之而来的是，每次迭代之后，如果有一个用于估算每一次可能的用户操作概率的函数，则一给定数据就是目标的概率变化就可以计算出，并具体表示为：

P{a_k｜I_i，D_k，U}≈KS(a_k，I_i，D_k，U)   

                                     (3)

这里K是一任意常数。这样一个函数表示一个能被测试和经实验调节的用户行为的模型，超出了信息检索系统的范围。

参照图10，它示出了描述一次数据库检索/选择期间的处理过程流程图。详细说，处理过程根据所想找的条目1000开始。通常，数据库检索系统的用户将会考虑到一个想找的条目，而后与所想找的条目比较检索数据库。换句话说，用本发明作为指导，可将“目标”想找的条目显示给用户，而后由用户有选择地寻找与目标相对应的项目。

根据一组法则，即概率分布，处理过程在方框1010进行，产生一列显示条目。在条目列表是按照概率分布产生的情况下，条目是按照它们与所想找的条目紧密相关的概率加到条目列表中的。

在条目列表产生之后，在方框1020向用户显示条目。其后，在方框1030用户通过识别有或是没有想要找条目对显示的条目作出反应。如果想找的条目在1040显示出，则此条目就被找出，并作结束处理1050。反之，则在方框1060根据用户反应的结果重新计算概率分布，并回到方框1010处理。

图1是围绕一给定用户作为函数S建立的相关反馈方法的伪码表。图1所示的方法保持着当前数据库中的数据是检索目标的概率分布。在每次迭代检索中，向用户显示最可几的数据N，而后利用用户的反应修正概率分布。最初，概率分布是用一平坦的优先分布(常数值)预置的。然而，那些熟练的技术人员能够容易地鉴别出此概率分布可能正好是当用基于询问的系统时，从所用的一个明确的询问中计算出的分布轻易地预置成的。

在图1中所示的伪码表列是很普通的。为说明在实际程序中的伪码仅需要一组通过设计用户界面确定的可能的操作A和一个将被实现的合理的用户模型S。

对于多媒体图像检索系统，例如作为本发明的主题，希望保持用户界面尽可能简单，着重于智能利用由用户提供的信息。这个方法与由M.Flickner、H.Sawhney、W.Niblack、J.Ashley、O.Huang、B.Dom、M.Gorkani，J.Hafner、D.Lee、D.Petkovic、D.Steele和P.Yanker等在题为“根据图像和视频内容询问：QBIC系统”文章中的主张对照鲜明，该文章登在IEEE计算机，28(9)：23-32，1995，在其中作者试图设计一最大量信息的用户界面。

用对比的方式将图像搜索器的全部用户界面示于图2。在检索期间的任何给定时间，四幅图像显示在屏幕上并提供给用户。用户可以用鼠标点击它们选出一个或更多的显示图像。选择的图像用红框加以突出。图像可以通过再一次点击它们而取消选择。

在选择O或者图像之后，用户通过击“继续”钮提取下一组的四幅图像。用户继续选择图像并击“继续”钮直到目标出现。在这里，检索是通过选择那个图像和击“寻出”钮终止的。“放弃”钮用于在目标图像被发出之前终止检索。用户可能对显示图像作为反应的A组包括20个单元。16个可能的选择图像组合，加上4个可能的检索终止。

那些熟练的技术人员能够鉴别在于用户界面可以随着增加更丰富的控制得到增强，例如用户能够按压的那些按钮，用以独立指示一幅图像是否类似于目标的颜色、形状、结构或组成。例如，这个系统能够用一触摸屏来实现，并设在纺织品商店中以帮助顾客寻找织品的设计。不考虑采用特定的用户界面，这里采用的贝叶斯结构适用于任何特定的用户界面。

为开发用户模型，做了两个简化的假设。首先是假设所有的用户是等同的，所以U可以忽略。如果不是这样的话，那么这种方法可以用于单独的用户或相同用户层。其次，假设用户的行为将会与一小组图像特征值相关连。

在本发明中所用的特征组有限，但是那些熟练的技术人员可以在将来任何时间轻易地想出另外的特征。表1描述目前使用的18个特征。注释条目16^#为对此度，它具有1/3象素达不到的亮度值YO和2/3象素达不到的亮度值Y₁。此外，条目17是图像中边缘的数量，它的计算先是通过将图像变换为灰度标度，然后用简单3×3拉普拉斯滤波器将其滤光，然后在20％处限定。

    1作为数据库中最大宽度的一部分的图像宽度    2作为数据库中最大高度的一部分的图像高度   3-13落入HSV彩色空间下述范围的象素百分比    黑-V≤3％    灰-S≤15％，2％≤V≤85％    白-S≤15％，80％≤V    红-10％≤S，5％≤V，-70度≤H≤25度    橙-10％≤S，2％≤V，15度≤H≤50度    黄-10％≤S，8％≤V，25度≤H≤80度    绿-10％≤S，2％≤V，75度≤H≤185度    兰-2％≤S，2％≤V，175度≤H≤260度    紫-10％≤S，2％≤V，255度≤H≤300度    棕-5％≤S≤85％，1％≤V≤40％，-50度≤H≤80度    粉-10％≤5≤60％，2％≤V，-70度≤H≤25度   14    平均色饱和   15    平均亮度   16    对比度   17    图像中边缘的数量   18    与特征17相同，但限定在10％

表1：特征组说明

在计算数据库中每个图像的18个成分特征矢量后，进行一非正式试验以鉴别特征和用户操作之间的关系。在每次迭代试验中，主题(用户)表示为显示出在单个随机选择的“目标”图像旁边有四幅随机选择的图像。然后要求主题以最全面接近目标图像的显示中选择图像。如果在所有图像中没有一个似乎是接近的，主题就被允许放弃所有未选择的图像。如有两个或更多的图像似乎是同样接近，主题就被允许选择一个以上图像。想不到，与这个结果及其以后的实验相对应的竟是一个很简单的模型。这个简单的模型是基于若于非常简化的假设：

1、用户选择一给定图像的概率仅取决于目标图像和其它目前显示的图像的特征值。它和任何其它的选择图形无关。

2、用户的决定仅基于每个图像的一个特征，且这个选定的特征往往会完全对应于计算出的特征之一。

3、用户选出一给定特征的概率是恒定的。每个特征的概率用Wf显示，并称为特征的权量。

4、用户选择一图像的概率是在选出特征方面远离目标的其它显示图像数量的线性函数。

一旦作出了这些假设，一给定图像的被选择概率是一线性函数：

这里F是对应于计算出的图像特征的一组实数函数。为简化起见，V(D_i，I_t，D)被称作图像Di的“图像记分”。

图3示出了由3个不同主题选择的图像的相关频率，作为它们的图像记分的函数，它们的图像计分是用表1中的18个特征和Wf＝1计算出的。为了供比较，虚线表示完全是随机“用户”的特性曲线。图3清楚地说明了图像记分和选择频率间的相关性。

用户间的主要差别是他们完全没选择任何图像的频率。如果对所有没有图像被选择的试验不予考虑的话，那么三个主题的特性曲线是惊人的相似如图3所示出的。这样我们可以假定首先要对主题判断是否任何图像都应被选择，而不同的主题对这种判断来说有不同的界限。但是，一旦作出了选择一图像的决定，余下的过程就是根据公式4精确地做出模型。

使用“图像记分”并当没有图像选择时容许不使用模型，根据图5所示的伪码程序计算出函数S。当用户选择不出图像时，这个程序与它的输入无关返回到一恒定值，它将留下不变的数据库概率分布。当用户选择一个或更多图像时，该程序根据图像记分求出用户选择各个图像的概率，并返回到以所有选择的图像概率乘积乘一减所有未选择图像概率之后的乘积。

根据简化的假设，一个图像被选择的概率应该是它的记分的线性函数。然而，这样一个函数可能太多地信任模型了。如果使用了图像记分的线性函数，那么极端的图像记分会导致概率不得不被限制在0或1。然而，遗憾的是用户犯了错误。因此，极限的概率能够引起正确目标从检索中完全被消除。为避免这种情况，采用与实验数据相符的S形函数，在数据的范围内它接近线性，但它从未达到极端的概率。这个S形函数的参数M和σ是经手动置成，与数据合理地相符。

唯一留下的任务是为18个特征权数Wf选值，以使它们与实验数据相符得非常合理。为了给这一步搜集更多的数据，提供了一种所有权数均设为1的图像搜索器型式。然后进行若干次检索，并记录每个用户的操作。这种型式图像搜索器的测量性能的最佳型的性能稍差一点。

在检验了这些检索中的用户情况与图4中所示情况相符之后，这个数据与初始收集的数据相结合。

接下来，确定出记录选择和用我们的18个单独特征中的每个计算出的图像记分之间的相关系数。然后这些特征以相关递减的顺序分类，并以最高相关为特征设定权数为1，同时其它特征的权数预置为0。在相关递减的顺序中，每个连续特征的权数是在0和2的值之间通过试验100次权数并选出与我们的数据最相关的一个加以标记的，如表2所示。

W₁ 0.0223W₂ 0.1362W₃ 0.0469W₄ 0.0290W₅ 0.0290W₆ 0.0848W₇ 0.0625W₈ 0.0201W₉ 0.0603W₁₀ 0.1116W₁₁ 0.0647W₁₂ 0.0335W₁₃ 0.0112W₁₄ 0.0893W₁₅ 0.0826W₁₆ 0.0491W₁₇ 0.0134W₁₈ 0.0536

表2：特征权数

为测试图像搜索器，已获得一个在201压缩盘(CD′S)上有超过20,000幅存贮图像的商用数据库。4522个图像从128×192象素的分辨率转移到一硬盘上，而包括在表1中的18个特征是预先计算的。

图像搜索器通过进行若干次检索的几个主题在这个数据库上进行测试。第一个主题是本发明中请的一个发明人，且此第一组结果表示能被具有最全面专业知识的一用户-即：其行为几乎与S函数相符的一用户完成的作业。第二个主题是一名系统编程员，他与该系统的开发无关。这第二组结果表示在该系统的使用中没有特殊专门知识的一名计算机专家的作业。最后，该系统由8个其他的主题进行简短的测试，他们每人仅进行一项或二项检索。这第三组结果表示仅具有一般计算机读写知识而一点也不了解该系统的人的作业。

  专家用户  计算机专家计算机录入员检索次数    20    24    11找出目标的次数    20    19    6中值检索长度    22    65    234平均成功检索长度    53    57    75成功检索的标准偏差    78    40    86

表3：不同主题的测试结果

仅给了每位测试者只包括以下内容的最小量的指令：

1、通过点击选择与目标最接近的图像。选择的图像有个红框。

2、如果在两个或更多图像中你无法确定，你可选择一个以上的图像。

3、如果没有一个图像接近目标或是所有的看起来接近程度都相同，就不要选任何一个。

4、如果你改变了你认为最接近图像的想法，你可以通过再一次点击而撤消那些图像。

5、一旦你已选择了最好图像，点击“继续”键以得到下一组图像。

6、当目标图像出现时，选择它，然后击“寻出”。

当然，这些指令高度无信息的，而改变的指令将包括如何最好的用该系统工作的线索。所有测试的结果示于表3中。图6用曲线表示两个计算机专家的结果，示出在一给定迭代量中检索成功完成的百分比。虚线表示如果该数据库是被随机检索时，所期望的相应百分比。

来自两个计算机专家的结果清楚地示出，不考虑用户界面的简化和预先计算出的图像特征，该系统是一种超过随机检索的实质性改进。平均说来，图像是在超过55次迭代或是从4522幅图像看出220幅之后被成功地找出来的。用户界面的简化使得一名有经验的用户能够在每次迭代上仅花费一或两秒钟，所以平均检索仅持续几分钟。

来自第三组的结果不是很好。他们的检索仅有地是成功的，而成功检索的平均长度是75次迭代。尽管如此，它仍然明显比随机概率高。

第三组用户所遇困难的一个可能原因是该组往往将注意力集中在该系统未测量的特征上。例如，有这样一名用户，检索一幅火烈鸟的图像，为她所作的报告是按照她的选择是那些包含有与火烈鸟的颈部一致的曲线的图像。由于目前的特征组不包含任何曲线的测量，所以找不到这个图像是不奇怪的。一个更全面的特征组将可能会改善这些初级用户的效能。

如前面所陈述的，当前选用的用户界面要尽可能地简单。尤其是，系统显示一组图像(目前是4幅)和通过如鼠标这样的选择装置点击它们选择它们的子集。在这个界面易于为用户理解时，它向检索工具提供相对于用户来说是相当贫乏的信息，很容易设想，更复杂的界面使用户能够提供更准确的信息工具。

例如，对目前界面的简单扩展会使用户能够表示显示图像与他的目标相符的强度。另外，使得用户能够指出出现相符特征的方法可能会证明是有用的。对用户界面的更复杂的强化将使用户能够从所显示出的图像中有选择地标出那些最相关的部分。用户可以简单地点击相关的图像部分或可以用鼠标框住它们。这样的一种增强将使用户能够具有相当的专业本领，而不需要他们学习复杂的询问语言或绘图工具。

人们希望的是选择那些预期会因数据库概率分布的贝叶斯校正减小的平均信息量达到最大的显示。这相当于在用户操作和目标图像之间达到最大的交互信息。举例来说，如果T是目标图像，是由直到现在这一刻为止的检索所确定的分布中引出的，而A是用户的操作，是由预置的算法所确定的分布中引出的，人们所希望求出的达到最大化的D则为： $>>->>\Sigma >T>>P>\{>T>\}>log>P>\{>T>\}>+>->>\Sigma >A>>P>\{>A>|>D>\}>log>P>\{>A>|>D>\}>->>\Sigma >>T>,>A>>>P>\{>T>,>A>|>D>\}>log>P>\{>T>,>A>|>D>\}>>s>$

对于一个给定显示，交互信息可以是在操作和目标图像之间进行0(M×S_N)次计算出来的，这里M是数据库中图像的数量，S_N是估计用户在一个N图像显示上操作的概率的复杂度。

在交互信息的计算中，使用包括结束检索操作的所有可能的用户操作是很重要的。如果目标图像是该显示图像中的一个，那么用户有100％的终止操作的机会，而作其它操作的机会是0％。由此产生的效应是在终止操作之后贝叶斯校正将平均信息量减少到0以及自一给定显示产生的交互信息反映出包含目标图像的显示的概率。

遗憾的是，为找出给出最高交互信息的显示，一有力的通道将是0(M×S_N(M选定N))。因此，即使当M和N是无足轻重的小，一有力的逼近也是抑制的。

为了减少O(M选定N)部分，采用了一“贪婪的”渐进。首先，选择最好的单个图像显示。这将真正是具有是目标图像的最高概率。接下来，加上特定的一个图像。这就提供了最具有信息性的两幅图像显示。应注意到这一步需要0(M×M×S₂)计算，这是因为必须计算出数据库中每一图像的相互信息。重复N次得到N个图像，那么，用的时间量为O((∑_i＝1^NS_i)×M²)。同时更好的是，当M大时它仍然是抑制的，由于它将用在真正重要的任何数据库中。

为进入合理的复杂性范围，一些图像可以不考虑作为显示用的可能的选择。初看起来，似乎用于显示的选择仅应该是具有目标的最高概率的C图像，这里C是相当可控的不变量，但是最高值C图像往往相互很相像，由于比较的缘故，要获得有用的信息需要一或二个具有较低概率的图像显示。因此使用了最高值C₁图像，加上均匀相间通过剩下表目的C₂图像。仅考虑这些图像的显示给出其复杂性为0((∑_i＝1^NS_i)×(C₁+C₂)×M).

这可以通过使用一近似方法作进一步改善以估算相互信息。这个方法分为二步：复杂性0(M log M)的初始步骤和复杂性0(K×S_N)的计算步骤，这里K是为产生可接受精度的一个选择值。这初始阶段仅需要为一给定的T的分布计算一次。然后可以在不再进行初始化的情况下用各种可能的D估算I(T；A/D)。

参照图8，该方法选择一组K取样图像。目标图像是取样(j)和取样(j+1)两个相邻取样之间的一个图像，它的概率是1/K(“之间”在这里指为是在分类表t表中)。应意识到在取样表上概率高于1/K的图像可以多于一次的出现。

在图9所示的计算步骤中，假设取样表是所有可能图像的完整的表，而且每个图像具有1/K的概率。

使用这个相互信息的近似法，及上述的试探法，一组图像以O((∑_i＝1^NS_i)×(C₁+C₂)×K)时间量选择用于显示。由于C₁、C₂和K可以选择成比M小很多，所以这是一显著的改进。

在最佳实施例内容中已对本发明作了详细表示和描述，对于那些的技术人员熟练来说，显然在没有脱离本发明的原理和精神的情况下是可能进行变化和改进的，同时本发明仅是就检索图像数据库进行描述的，实际上所有的原理都是与其它媒体有关的。尤其是音频、视频数据库和三维(3-d)模型。因此，本申请的发明应该仅由所附权利要求的范围限定。