基于分层特征和遗传规划相关反馈的图像检索方法

摘要

本发明公开了一种基于分层特征和遗传规划相关反馈的图像检索方法，包括以下步骤：（1）对用户提交的检索图像进行自适应分割，得到分割区域；（2）对检索图像提取全局特征；分割区域提取局部底层特征；（3）对于标准图像库中的每一幅图像计算对应于分割区域的最优区域；（4）构建全局-最优区域相似度匹配模式；（5）通过赋予相似度匹配模式中各种相似度以平均权重来计算检索图像和标准图像库中每一幅图像的相似度；根据相似度进行排序得到初始检索结果并把与用户最相似的前若干幅图像返回用户端；（6）用户参与反馈，直到检索出满意的图像。能够更接近用户的检索意图，可以有效地提取图像的内容特征，并能快速有效地完成检索过程。

说明书

技术领域

本发明涉及图像检索领域，尤其涉及一种基于分层特征和遗传规划相关反馈的图像检索方法。

背景技术

目前, 随着多媒体和互联网技术的快速发展，人们接触到越来越多的各种信息。图像作为一种内容丰富和表现直观的多媒体信息，长期以来受到人们的青睐。如何快速并且有效的搜寻到自己需要的信息? 20世纪90年代出现了基于内容的图像检索(Content Based Image Retrieval，CBIR)，其从可视化角度对图像检索进行探讨。所谓CBIR，就是通过提取图像的底层特征，比如颜色、纹理等特征来表示图像内容，图像之间的匹配是图像特征的匹配。

对图像内容的描述包括全局描述子和局部描述子。常见的全局描述子有局部二值模式(Local Binary Pattern，LBP), 梯度方向直方图(Histogram of Oriented Gradients，HOG)以及颜色直方图等。全局描述子的鲁棒性较强，受噪声的影响较小。然而,在检索的过程中,根据人眼视觉感知特性, 用户常常对图像中的某一目标感兴趣, 提取图像的全局特征往往不能满足用户的检索需求。相对于全局特征而言, 局部特征，如尺度不变特征变换，对单一目标的描述更为有力。基于区域的图像检索首先将图像分割成区域, 通过区域间的匹配完成图像间的匹配, 在一定程度上克服了基于全局特征的图像检索的缺陷。由于分割技术至今仍然是计算机视觉的一大难题, 图像中的一个目标常常被分割成好几个区域，或者分割的每个区域并不代表一个明确的目标, 因此，基于区域的图像检索也有自身的局限性. 如何结合全局和区域特征各自的优点来表达图像的内容是个有趣的问题。

图像所蕴含的丰富内容是底层视觉特征远远不能表达的, 如何减少图像的底层特征和高层语义之间的“语义鸿沟”是CBIR的重要研究课题。相关反馈是减小语义鸿沟的一种有效的方法, 首先在信息检索中提出，20世纪90年代引入图像检索, 并且证明能够很好的提高检索性能。相关反馈包括四个部分: (1) 系统将初始检索结果中的最相似的前若干幅图像返回给用户；(2) 用户标注正例和负例；(3) 通过用户标注的正例和负例来学习用户的检索需求；(4) 将图像库的图像重新排序。

常见的相关反馈方法包括权重更新法, 概率模型法，机器学习法以及基于知识的方法。其中权重更新法由于其策略简单，实时性强，受到了广泛的关注和显著的发展。这种方法通过用户的标注学习更新特征权重从而在一定程度上满足用户的检索主观性。但是这些策略只是通过线性结合单独特征，很难表达用户的视觉特性。Cristiano Dalmaschio Ferreira等人首先将遗传规划(Genetic Programming，GP)引入到相关反馈。GP是一种进化式机器学习方法, 试图通过某种方式模拟进化过程的内在机制, 并通过随机扰动或突变, 通过定义一个适应度函数来进行评估, 进而获取适应度最大的解, 常用于信息检索等。实验结果表明, 借助GP获取特征的非线性组合在一定程度上能够更接近用户的检索意图。然而,它们分别是基于全局特征的相关反馈和基于均匀分割区域的相关反馈，提出的检索模式不适用于一般的分割结果。

发明内容

本发明的目的是提供一种基于分层特征和遗传规划相关反馈的图像检索，提出的检索模式适用于一般的分割结果，能够有效地检索相关图像。

本发明采用下述技术方案：一种基于分层特征和遗传规划相关反馈的图像检索方法，包括以下步骤：

（1）、对用户提交的检索图像                                               进行自适应分割，得到分割区域；

（2）、对检索图像提取全局特征；分割区域提取局部底层特征；

（3）、对于标准图像库中的每一幅图像，，计算对应于分割区域，的最优区域，其中是标准图像库中的图像数量；

（4）、构建全局-最优区域相似度匹配模式；

（5）、通过赋予全局-最优区域相似度匹配模式中的所有相似度以平均权重来计算检索图像和标准图像库中每一幅图像的相似度；根据对进行排序，得到初始检索结果并把与用户最相似的前若干幅图像返回用户端；

（6）、用户参与反馈，直到检索出满意的图像。

所述的步骤（1)中的自适应分割的具体方法如下所述：（11）、将图像进行均值漂移分割；

（12）、将分割区域作为该图像的节点，对该图像用规范割进行聚类；

（13）对聚类后的每个分割区域分别提取R、G、B颜色通道的平均像素值作为该区域的三维特征；

（14）将聚类数目初始化为2；

（15）随机选择个分割区域的特征向量作为初始类别中心，将所有分割区域归并到最近的类别中，并重新计算类别中心；

（16）、计算准则函数，其中是个类别，是类别中心，是属于类别的区域的特征向量，如果大于等于预先设定的阈值，，转到(15)；如果小于预先设定的阈值，则停止迭代。

所述的步骤（2）中的全局特征包括颜色和纹理特征，全局特征中的颜色特征为颜色直方图256维、颜色矩9维；全局特征中的纹理特征为：边界/内部像素分类（Border/Interior pixel Classification，BIC）特征128维、Gabor小波变换特征48维；

    所述的步骤（2）中的底层特征包括颜色、纹理和形状特征；

    区域局部底层特征包括颜色、纹理和形状特征，其中颜色特征为：将图像由RGB颜色空间转换到L*u*v*空间，提取L*，u*，v*区域平均颜色作为每一个区域的3维颜色特征；其中形状特征：区域的1维密度比、2维质心、4维矩形盒子、7维不变矩作为14维形状特征；其中纹理特征：计算区域的共生矩阵，提取能量、惯性、熵、匀度四个统计特性作为16维纹理特征。

所述的步骤（3）中对于标准图像库中的每一幅图像，，计算对应于分割区域，的最优区域，其中是标准图像库中的图像数量。

所述的步骤（4）全局-最优区域相似度匹配模式是将检索图像与标准图像库里的每一幅图像的全局特征和最优区域特征的相似度组合起来的一种模式。

所述的步骤（5）初始检索结果是按照将全局-最优区域相似度匹配模式中的所有相似度加权平均得到的线性相似度对标准图像库进行排序的结果。

所述的步骤（6）包括以下步骤：

（61）、如果用户对检索结果满意，则停止检索，否则进入步骤（62）；

（62）、用户标注系统返回的检索结果为正例或反例；

（63）、根据适应度函数选择个体，然后进行复制、交叉和变异操作，借助遗传规划算法学习最优的特征相似度结合非线性方式；

（64）、按照非线性相似度重新计算和的相似度，对图像库中的所有图像重新排序，并输出前若干幅最相似图像；

（65）、反复进行（62）-（64），直到检索到令用户比较满意的图像。

本发明的有益效果：本发明提供图像的一种分层特征表示方法，并借助遗传规划算法获取特征的非线性组合，利用非线性特征检索图像在一定程度上能够更接近用户的检索意图，可以有效地提取图像的内容特征，并能快速有效地完成检索过程。 

附图说明

图1 本发明的方法流程图；

图2 为图库中的例图；

图3 全局-最优区域相似度匹配模式图；

图4 遗传规划个体的一个例子图；

图5 相关反馈的比较图（基于正例和基于正负例）； 

图6 各种方法相关反馈结果的比较图；

图7 用户标注的图像数目不同时对应的平均查准率 (Average Precision, AP)示意图；

图8 基于最优区域和基于全部区域的图像检索结果的比较图；

图9 系统初始检索的鲁棒性测试图。

具体实施方式

如图1所示，本发明公开的一种基于分层特征和遗传规划相关反馈的图像检索方法，具体包括以下步骤：

（1）、对用户提交的检索图像进行自适应分割，得到分割区域；

    均值漂移 (Mean Shift,MS) 和规范割 (Normalized Cuts, NC) 是两种常用的图像分割方法，但是MS易产生过分割，NC计算复杂度太高。Wenbin Tao等人将MS和NC结合，提出了一种新的图像分割方法，MS-Ncut，即将MS和NC结合，在一定程度上缓解了过分割和计算复杂度，先用均值漂移分割方法对图像进行分割；然后在前一步所得到的过分割的图像基础上用规范切的方法进行区域合并。但是MS-Ncut方法需要预先设置分割数目来结束合并过程。本发明是一种基于MS-Ncut并且能自动确定分割数的分割方法，即自适应MS-Ncut方法，具体方法如下所述：

（11）、将图像进行均值漂移分割；

（12）、考虑到图理论中图的定义，，其中是图的顶点，是顶点与顶点之间的权重，将该图像看作是图理论中的图，将分割区域作为该图像的节点，对该图像用规范割进行聚类；

（13）对聚类后的每个分割区域分别提取R、G、B颜色通道的平均像素值作为该区域的三维特征；

（14）将聚类数目初始化为2；

（15）随机选择个分割区域的特征向量作为初始类别中心，将所有分割区域归并到最近的类别中，并重新计算类别中心； 

（16）计算准则函数，其中是个类别，是类别中心，是属于类别的区域的特征向量，如果大于等于预先设定的阈值，，转到(15)；如果小于预先设定的阈值，则停止迭代。

（2）、对检索图像提取全局特征；分割区域提取局部底层特征；

所述的全局特征包括颜色和纹理特征，全局特征中的颜色特征为：颜色直方图256维、颜色矩9维（3个颜色分量，每个分量上3个低阶矩）；全局特征中的纹理特征为：边界/内部像素分类（Border/Interior pixel Classification，BIC）特征128维、Gabor小波变换特征48维；

所述的区域局部底层特征包括颜色、纹理和形状特征，其中颜色特征为：将图像由RGB颜色空间转换到L*u*v*空间，提取L*，u*，v*区域平均颜色作为每一个区域的3维颜色特征；其中形状特征：区域的1维密度比、2维质心、4维矩形盒子、7维不变矩作为14维形状特征；其中纹理特征：计算区域的共生矩阵，提取能量、惯性、熵、匀度四个统计特性作为16维纹理特征。

（3）、对于标准图像库中的每一幅图像，，计算对应于分割区域，的最优区域，其中是标准图像库中的图像数量，具体计算最优区域的步骤如下，首先给出最优区域的定义：

若把图像自身看作0层分割，自适应分割结果看作1层分割，则结合全局特征和区域特征可以建立一种图像的层描述，借助全局特征和局部特征优势互补来表示图像的内容。更进一步地，在所有分割区域中选取具有最具有代表性的区域进行匹配，不仅能减少检索的时间，而且能提高检索的有效性。对于基于全局特征的图像, 把原图看作这里的最优区域即可。基于此，提出最优区域的定义。

定义1 (最优区域, Optimal Region, OR) 设两幅图像和， 其中和分别为两幅图像对应的分割区域。如果用表示基于特征描述子计算的区域之间的相似度（相似度是距离的负指数函数，即，其中是距离），则区域的最优区域为, 如果满足

,           (1)

对应的相似度为称为最优区域相似度，记为。

下面的例子进一步阐述了最优区域的概念。如图2所示，以Corel图像库中的两幅图像(a)和(b)为例。用自适应MS-Ncut算法对两幅图像进行分割，分别得到四个区域，表示为和，提取步骤（2）中所述的区域颜色特征，两幅图像区域间的距离矩阵为

其中表示区域和的距离。取相似度是距离的负指数函数，根据定义1，基于该颜色特征描述子，区域的最优区域为。因为, 即。同理，区域的最优区域为，区域的最优区域为，区域的最优区域为。

若提取步骤（2）中的区域形状特征，则图像和的区域距离矩阵为

，

则基于该纹理特征描述子，的最优区域都是，的最优区域都是，的最优区域都是，的最优区域是。

     由定义1和上面的实例说明，最优区域具有以下特征：1) 是在特征描述子指定的前提下，对图像中的某个区域而言的；2) 在特征描述子指定的前提下，图像的某个区域的最优区域是图像中和该区域相似度最大的区域；3）一幅图像的最优区域个数是，其中是图像的分割区域数目，是提取图像特征的描述子的数目。由最优区域的定义和以上特征知，图像的每个区域的最优区域数目图像的区域数目，减少了和的相似度匹配的计算复杂度；同时由于参与匹配的是相似度最大的区域，抓住了图像内容的重点。

（4）、构建全局-最优区域相似度匹配模式；全局-最优区域相似度匹配模式(Global-Optimal Regions Similarity Pattern, GORSP)是将检索图像与图像库的每一幅图像的全局特征和最优区域特征的相似度组合起来的一种模式。

首先给出要用到的简单相似度描述子定义：

  定义2 (简单相似度描述子) 简单相似度描述子定义为, 其中是特征提取函数, 将图像映射为特征空间中的一个点 (的特征向量)。是相似度函数，用来计算两幅图像的相似度。

    定义3 (全局-最优区域相似度描述子) 全局-最优区域相似度描述子定义为, 其中,是个简单全局相似度描述子的集合， 是个简单区域相似度描述子的集合，是全局-最优区域相似度结合函数，结合由和计算得到的相似度值和，用以计算两幅图像的相似度。

把基于全局-最优区域相似度描述子求取两幅图像相似度的方式称为GORSP。图2给出GORSP的例子：首先用和获得图像和的特征向量，然后用计算两幅图像的全局相似度，用计算两幅图像的最优区域相似度，最后用来结合这些相似度以计算得到两幅图像和的最终相似度。需要说明的是对于不同的检索图像，由于其分割区域数目不同，得到的最优区域相似度个数是不同的。

根据人眼视觉特性，用户对图像中的不同区域的关注度和敏感度不同。同时，用户不仅仅关注某一个目标，而且关注这个目标所处的背景，最优区域就是在视觉相似度上和用户提供的检索图像区域接近的区域，因此会被用户更多的关注。另外，区域与区域之间并不是独立的，而是相互联系的，提取图像的全局特征有助于将不同的区域联系起来，因此，GORSP是基于人眼视觉特性而提出来的。

（5）、通过赋予全局-最优区域相似度匹配模式中的所有相似度以平均权重来计算检索图像和标准图像库中每一幅图像的相似度；根据对进行排序，得到初始检索结果并把与用户最相似的前若干幅图像返回用户端；

初始检索结果是按照将全局-最优区域相似度匹配模式中的所有相似度加权平均得到的线性相似度对标准图像库进行排序的结果。按照式(2)给出初始检索结果：

,            (2)

由式(2)知，图像和的相似度定义为全局和最优区域相似度的线性组合，其中线性权重简单取为均值。

（6）、用户参与反馈，直到检索出满意的图像；

此处介绍两种基于遗传规划的相关反馈策略，一种检索框架中只包括用户标注的正例, 记为Global-optimal regions ，另一种则不仅包括正例, 同时还包括负例，记为Global-optimal regions。

对于Global-optimalregions ，实现的具体步骤为：

（61）、如果用户对检索结果满意，则停止检索，否则进入步骤（62）；

（62）、用户标注系统返回的检索结果为正例或反例；

    设和是用户从参与检索到找到满意检索结果所标记的所有正例和负例图像的集合。同时设是从正例中随机选择的子集(, , , 不失一般性，取)，则可构造基于正例的检索模式: ；

（63）、根据适应度函数选择个体，然后进行复制、交叉和变异操作，借助遗传规划算法学习最优的特征相似度结合非线性方式；

具体包括以下过程：

（63-1）、确定个体的表达形式，即确定终端集和函数集：

遗传规划的个体是以全局和最优区域简单描述子相似度为叶节点的树状结构，如图3。此个体的表达式为：，以为终端，以为函数；

（63-2）、随机生成初始种群：

种群规模控制种群中个体的数量，规模大能提供遗传进化的多样性，但同时带来较大的计算时间，反之亦然。通常，对于难度较大的问题，适当增加种群规模，以加大问题搜索空间。这里采用的初始种群的个数为60，随机产生初始种群。所采用的GP算法的初始种群是60个具有类似图4结构的个体构成的。但是图4中的终端和函数只是采用的一部分，采用的树的叶节点集合为全局和最优区域简单描述子相似度，函数集合为；

为了保证初始种群中树的结构和规模保持多样性，第一代种群采用满树和生长树混合的生长方式(Ramped half and half)产生程序树，每一个深度的生成树，满树和生长树生成方式各占50%。这里限定程序树的深度为5，初始种群中树的深度为2到5的各占25%。初始种群随机产生，是简单描述子和运算符的随机组合，并没有特意把初始结果的相似度特征函数作为初始个体之一；

（63-3）计算种群中个体的适应度：

首先给出所用的训练集； 

设是训练集, , 的个数是的数据库图像，本文取。分别从，和未标注图像中随机选取，其中的个数，的个数，的个数；

给定一个种群个体, 图像和检索模式的相似度定义为

                      (3)

将训练集中的图像按照公式(3)计算与的相似度，并按照从大到小的顺序形成有序序列，的适应度函数选取

,                   (4)

其中是有序序列的第个图像, 如果是正例图像，则, 否则；

（63-4）、根据适应度选择个体执行遗传操作，即复制、交叉和变异，生成下一代：根据个体的适应度函数采用规模为2的锦标赛方法对个体进行选择，对选择后的个体进行复制、交叉和变异的遗传操作，得到新一代个体。其中复制采用适应度优先法，从父代个体中根据适应度选择优秀个体放进交配池，以备交叉变异产生下一代；交叉采用子树交换的方式，随机选择两个父代个体的节点进行交换以产生两个新的个体，这里采用的交叉概率为0.8；变异时用随机产生的子树代替个体中任意选择的一个子树，以产生新种群里的后代，这里采用的变异概率为0.2；

（63-5）、循环执行(63-3)和(63-4)，直到满足预先设定的适应度值或培养的代数的终止条件；

（64）、按照得到的最优非线性相似度重新计算和的相似度，对图像库中的所有图像重新排序，并输出前若干幅最相似图像；

（65）、反复进行（62）-（64），直到检索到令用户比较满意的图像。

    对于Global-optimal regions ，实现的具体步骤为：

    在(61)-(65)中，将(62)中的检索模式更改为：基于正例和负例的检索模式构造为，其中，，，，是常数，本文中我们取；

并且，(63-3)中更改为

.                    (5)

本发明的方法可以用仿真实验给予进一步的展示：

1 仿真内容：对常用的图像检索实验数据库Corel 5000进行实验。该图像库包括50类，每类100幅，每幅图像的大小是或者。实验从相关反馈性能、最优区域的有效性、算法的鲁棒性以及时间复杂度4个方面验证本文检索框架的有效性，应用本发明方法和基于均匀分块的方法、基于全局特征的方法、基于最优区域的方法和基于粒子群的方法进行比较。五种比较的方法分别记做本文的五种对比方法分别记为：Global-optimal regions、Uniform segmentation  、Global 、Optimal regions 、PSO。 

2 仿真结果：在给出仿真结果之前，先介绍评估检索结果好坏的客观指标：第一个客观指标是采用前幅最相似图像的平均查准率, 即对所有检索示例图像的前幅最相似图像的查准率求平均，

,                       (6)

其中表示对于检索示例图像返回前幅最相似图像的查准率,即返回的相关图像的个数与的比值；是检索示例图像集的个数. 我们在每类中随机选择30幅作为检索示例图像，共有1500幅检索示例图像。与检索示例图像属于同一类的图像称为相关图像，否则称为不相关图像。为避免随机选择带来的偏差，我们将实验多次得到的求平均作为最终的结果。

    曲线图是衡量CBIR系统的另一个常用的客观指标。不仅包含相关图像的多少，而且反映了相关图像的排序。

A 相关反馈性能

相关反馈性能从三个侧面进行了测试，首先考察了正例图像与正负例图像分别参与反馈时的相关反馈性能的比较；其次在同等平台下比较了我们提出的两种方法与其他三种方法，给出了和曲线图等客观指标的比较结果；最后评价了用户标注图像的数量对我们算法的影响，即考虑了用户的标注负担的问题。

图5给出了前4种方法自身和的比较结果。可以看出，10次反馈中优于。这说明在基于GP的反馈策略中，用户标注的负例对反馈检索是有一定贡献的。鉴于这个结果，在下面的实验中，基于均匀分块的方法、基于全局特征的方法、基于最优区域的方法只有策略参与比较。

图6(a)是从初始检索到10次反馈的不同方法的的比较，图6(b)是反馈5次后的曲线图。图6(a)考察了反馈1次至10次的检索性能，然而在实际应用中考虑到用户的耐性以及时间的有限性，我们在图6(b)中给出反馈5次后的曲线图。从图6(a)可以看出，反馈10次后我们基于正例的方法Global-optimal regions的分别高于PSO，Global ，Uniform segmentation ，Optimal regions  0.2%，11.12%，11.74%，19.99%。我们基于正负例的方法Global-optimal regions的分别比这四种方法高9.8%，20.72%，21.34%，29.59%。优于Global ，Uniform segmentation两种方法突出了我们提出的检索模式对一般分割方法的普遍适用性以及优势。优于PSO方法说明了我们本文提出的检索框架式有效的。图6(b)表明在返回前10幅到前80幅相关图像，我们的基于正负例的方法是占有优势的，返回前90幅和返回前100幅两种情况下，Global 是最好的。考虑到在实际应用中，用户所需要的相关图像的有限性，我们的方法还是比较有竞争力的，返回的相关图像不仅多，而且排序靠前。

此外还考察了用户的标注对我们的方法产生的影响，即用户在每次反馈过程中标注的图像数量对检索结果的影响。以方法Global-optimal regions为例，图7考察了当用户标记幅图像时反馈1-10次对应的平均查准率 (AP )，本实验中，分别取5，10，20，30，50。图7表明，时，检索结果最好，即用户每次反馈过程中标注5幅图像检索结果最好。实验结果说明在用户能承受的负担内，我们的方法能产生比较理想的检索结果。分析其原因是，我们的正例图像集合和负例图像集合是一个用户从参与检索到找到满意检索结果所标记的所有正例和负例图像的集合，因此积累了足够的标注图像。

B 最优区域的有效性

提取图像的最优区域进行检索可以提高检索的有效性和减少检索时间。这部分，我们把基于最优区域的图像检索(Optimal regions , Optimalregions )和基于全部区域的图像检索(All regions , Allregions )作比较。

两种方法的初始检索和反馈的对比结果见图8。图8表明，初始检索阶段，基于最优区域的图像检索比基于全局区域的图像检索高出10.77%。五次反馈后，基于正负例的最优区域方法比基于正负例的全部区域的方法高出4.06%，基于正例的最优区域方法比基于正例的全部区域方法高出7.53%。因此，和全部区域参与检索的方法相比，基于最优区域的检索方法更有优势。

然而也注意到，基于最优区域的图像检索方法在第一次反馈后下降了大约1%，这是由于基于区域的图像检索本身的缺点所致，比如分割结果的不尽人意等。因此，只有将基于全局特征和基于最优区域特征的方法结合起来，优势互补，才能提高检索结果（见图5）。

C 鲁棒性

图9给出我们提出的检索系统的鲁棒性测试结果。第一行给出了当目标图像变亮、变暗程度不断加大, 滤波窗口的尺寸变大和旋转角度的加大后, 相似度匹配后目标图像在图像库中的排序。 第二行给出了变化后的目标图像和目标图像的距离。从图9的实验结果可以看出, 在对目标图像进行一定范围的变化下，目标图像的排序以及和改变后的目标图像的距离变化不大。因此，该实验说明我们的方法有较强的鲁棒性。

D 时间复杂度

对每幅检索图像进行分割，提取全局特征和区域特征，计算最优区域以及在图像库中进行匹配排序的平均时间是0.4355s。基于正例的相关反馈和基于正负例的相关反馈平均一次反馈的时间分别为0.8032s和0.9116s。因此，适用于实时的图像检索系统。

根据算法的各步骤分析，该算法的时间复杂度由对用户提交的检索示例图像进行图像分割、提取特征，计算最优区域、对图像库图像进行排序和相关反馈的时间复杂度组成。其中图像分割的时间复杂度是,其中和分别是图像的宽度和高度；提取特征的时间复杂度是，其中是对检索示例图像进行自适应MS-Ncut分割得到的区域数；计算检索示例图像相对于图像库图像的最优区域的时间复杂度是，其中是图像库中图像的数量；对图像库图像进行排序的时间复杂度是；相关反馈的时间复杂度是GP算法的复杂度+。对于更大的图像库(10000幅以上)，可以考虑使用快速近邻法进行匹配，即首先将图像库图像分级，构造成树状结构，然后通过一定的规则将用户提交的检索示例图像和树状结构的某一分枝进行比较来减少计算量。

E 其他说明

由定义3知，即使不同图像的分割数目不同，同一幅检索图像在和不同图像匹配时，最优区域相似度描述子的个数是相同的，因此，在进行GP进化时，种群个体的树状结构的终端集合不需要改变。所以，算法的复杂度不会因为不同图像分割区域数目的不同而增加。

另外，系统是开放的系统，现有的任何一种合适的分割方法都可以嵌入到本发明的图像检索系统中，例如，Jifeng Ning，Pablo Arbeláez提出的分层分割和自适应分割方法。综合考虑时间复杂度和分割效果，本发明的检索系统中采取了自适应MS-Ncut分割方法。

由上述具体实施方法可见，本发明提出了一种有用户参与的交互式图像检索方法，该方法通过遗传规划学习相似度的非线性结合来实现的：(1) 给出了一种快速的自适应图像分割算法；(2) 定义了最优区域的概念, 只基于最优区域参与图像间的匹配检索, 既减小了时间复杂度又增加了图像匹配的有效性；(3) 构建了一种全局-最优区域相似度检索模式，在保持了图像检索的鲁棒性的同时更加符合人眼视觉特性；(4) 在图像自适应分割的基础上，基于全局-最优区域相似度模式进行基于遗传规划的相关反馈。