使用多级图象数据结构的图象搜索方法

1.一种使用多级图象数据结构的图象搜索方法，这种数据结构 基于具有至少两个不同分级的图象栅格而表示，该方法包括以下步 骤：
确定参考图象和目标图象之间的颜色相似性，其中参考图象和目 标图象都由分级的栅格级表示；和
根据用户基于内容的查询来搜索图象。
2.根据权利要求1的方法，其中所述确定步骤包括：匹配参考 图象的栅格级中包含的单元和目标图象的栅格级中包含的单元。
3.根据权利要求1的方法，其中所述确定步骤包括：匹配参考 图象的栅格级和目标图象的各个栅格级；以及交叉匹配参考图象的栅 格级和目标图象的栅格级。
4.根据权利要求1的方法，其中所述确定步骤包括：匹配参考 图象和目标图象的栅格级之间的区域代表性颜色值。
5.根据权利要求1的方法，其中所述各图象栅格级中的每一个 都被分成多个单元，所述确定参考图象和目标图象之间的颜色相似性 的步骤包括如下步骤：
将与参考图象和目标图象的各栅格级中包含的单元之间的区域代 表性颜色的相似性相对应的颜色相似性值乘以一第一权数；
将所述颜色相似性值乘以一个代表所述单元之间的可靠性的相似 性的相似性值和一第二权数；和
计算加权平均值以归一化单元相似性。
6.根据权利要求5的方法，其中还包括：当比较了两个栅格并 计算出相似性时，基于通过根据由栅格级之间宽度和高度差得到的移 位量在水平和竖直方向移位所合计的总值，确定参考图象和目标图象 中的相同级栅格之间的相似性。
7.根据权利要求1的方法，其中还包括：基于按栅格级之间的 宽度和高度差在水平和竖直方向移位所合计的值，确定参考图象和目 标图象中的栅格之间的颜色相似性。
8.根据权利要求4的方法，其中在通过匹配区域代表性颜色相 似性值执行搜索的情况下，使用参考图象和目标图象中的栅格级之间 的单元相似性来搜索相同栅格级之间的相同位置和不同位置。
9.根据权利要求4的方法，其中，参考图象和目标图象的栅格 级之间进行区域代表性颜色值匹配的操作是在不同栅格级的相同位置 和不同位置上进行搜索。

技术领域\n本发明涉及使用多级图象数据结构的图象搜索方法，具体涉及相 对于与静止图象的空间颜色性质有关的一种颜色特征具有不同分级栅 格级结构的多级图象栅格数据结构，以及用于使用多级图象栅格数据 结构搜索图象的图象搜索方法。\n背景技术\n在常规图象搜索方法中，诸如颜色、形状、纹理等特征是以一级 的图象栅格数据结构表示的，并且使用一级的图象栅格数据搜索相同 结构的不同图象数据之间的相似性，从而搜索图象。\n在根据常规图象搜索方法搜索图象时，根据所要搜索的图象的特 性，每一特征的重要性是不同的。而且，即使仅对于一种特征，常规 图象栅格数据结构中每个单元的重要性也是不同的。例如，在使用由 n维结构形成的颜色直方图的图象搜索方法中，对于形成该n维结构 的每个元素，可以将反映每个元素的重要性的加权值确定为不同的 值。\n即，在使用一级的图象数据结构的常规图象搜索方法中，基于对 应的栅格来表示特征之间的重要性。但是，在这种情况下，并不考虑 某个特征的每一元素的重要性。为了解决该问题，另一种常规图象搜 索方法采用了计算某个特征中各元素的平均重要性的方法。\n但是，在上述常规图象搜索方法中，由于每个元素的重要性受目 标图象或参考图象影响，因此在图象搜索中某个特征的各元素的平均 重要性是无用的，即预先确定某个特征的各元素的平均值是无用的。\n而且，由于常规图象栅格数据结构仅形成为一级，因此常规图象 搜索方法中对图象中包含的目标(或目标图象)的搜索是不精确的。\n发明内容\n因此，本发明的一个目的是提供一种多极图象数据结构，其中通 过基于多级图象栅格表示一个特征、和表示每个单元的区域代表性颜 色和相对于区域代表性颜色的可靠性，由不同级的多级结构的单元来 表示每一级。\n本发明的另一个目的是提供一种图象搜索方法，能够在两个图象 栅格的同一级的单元、栅格的不同级、和颜色区域之间匹配，以对于 与不同图象对应的多级图象栅格执行颜色相似性检索。\n为了实现上述目的，根据本发明提供一种多级图象数据结构，其 中以具有多于两个不同级的分级图象栅格结构来表示一个图象的空间 颜色特征。\n为了实现上述目的，根据本发明提供一种使用多级图象数据结构 的图象搜索方法，这种数据结构基于具有至少两个不同分极的图象栅 格而表示，该方法包括以下步骤：确定参考图象和目标图象之间的颜 色相似性，其中参考图象和目标图象都由分级的栅格级表示；和根据 用户基于内容的查询来搜索图象。\n优选地，所述确定步骤包括：匹配参考图象的栅格极中包含的单 元和目标图象的栅格极中包含的单元。\n优选地，所述确定步骤包括：匹配参考图象的栅格极和目标图象 的各个栅格极；以及交叉匹配参考图象的栅格极和目标图象的栅格 极。\n优选地，所述确定步骤包括：匹配参考图象和目标图象的栅格极 之间的区域代表性颜色值。\n优选地，根据下列步骤来确定参考图象和目标图象的分极栅格极 中包含的单元之间的相似性：将与参考图象和目标图象的栅格极中包 含的单元之间的区域代表性颜色的相似性相对应的颜色相似性值乘以 一第一权数；将所述颜色相似性值与一个由代表参考图象和目标图象 的栅格极中包含的单元之间的可靠性的相似性的相似性值乘以一第二 权数得到的值相加；和归一化所得的单元相似性。\n优选地，当比较了两个栅格并计算出相似性时，基于通过根据由 栅格极之间宽度和高度差得到的移位量在水平和竖直方向移位所合计 的总值，确定参考图象和目标图象中的相同级栅格之间的相似性。\n优选地，基于按栅格极之间的宽度和高度差在水平和竖直方向移 位所合计的值，确定参考图象和目标图象中的栅格之间的颜色相似 性。\n优选地，在通过匹配颜色区域执行搜索的情况下，使用参考图象 和目标图象中的栅格极之间的单元相似性来搜索相同栅格极之间的相 同位置和不同位置。\n优选地，当搜索不同栅格极之间的颜色相似性时，在参考图象和 目标图象的栅格极之间的颜色区域匹配操作被用于在不同栅格极的相 同位置和不同位置进行搜索。\n本发明附加的优点、目的和特征可以从下面的说明中容易地得 到。\n附图说明\n通过以下的详细说明和附图可以更完整地理解本发明，附图中给 出的例子仅是说明性的，因此并不是对本发明的限制，其中：\n图1是根据本发明的多级图象栅格数据结构和3级图象栅格数据 结构的实施例的示意图；\n图2是根据本发明的使用多级图象栅格数据结构和3级图象栅格 数据结构间匹配结构的图象搜索方法的示意图；\n图3是根据本发明的使用多级图象栅格数据结构和3级图象栅格 数据结构中同级之间匹配结构的图象搜索方法的实施例的示意图；\n图4是根据本发明的使用多级图象栅格数据结构和3级图象栅格 数据结构的不同级之间匹配结构的图象搜索方法的实施例的示意图；\n图5A和5B是根据本发明的使用多级图象栅格数据结构的图象 搜索方法的实施例的示意图，其中图5A是两个相同图象栅格数据结 构的示意图，图5B是两个图象栅格数据结构的匹配过程的示意图。\n具体实施方式\n本发明涉及多级图象栅格数据结构和使用该数据结构的图象搜索 方法。下面将对根据本发明的用于产生多级图象栅格数据结构的方法 进行说明。\n在正方形图象的情况下，将其均匀地按高度和宽度划分，在非正 方形图象的情况下，根据图象宽度和高度的纵横比均匀地划分一边， 并按一边的单位均匀地划分另一边。即，按照相同单位划分具有相同 长度的水平和垂直边的规则正方形结构，而在具有不同长度的水平和 垂直边的矩形结构的情况下，一边(例如，较长边)被均匀划分，另 一边(例如，较短边)则按该一边的划分单位划分。\n因此与上述相似，在一个图象数据结构中，空间颜色特征被划分 为不同级的多级栅格，从而表示多级图象栅格的结构。\n此时，每个图象栅格是不同级的多级结构，每一级的分辨率被分 级划分。给每个栅格的单元分配两个值，这两个值是区域代表性颜色 (RRC)和与区域代表性颜色的精度有关的可靠性分值(S)。\n图1表示根据本发明的多级图象栅格数据结构和3级图象栅格数 据结构的实施例。即，一个图象被表示为第一级、第二级和第三级的 图象栅格级。\n在3级图象栅格数据结构的分辨率中，根据所划分的级，第一级 图象栅格分辨率最低，第二级图象栅格是中间级，第三级图象栅格分 辨率比第二级图象栅格高。\n第一级图象栅格被划分为包括与垂直边M和水平边N的纵横比 成比例的M1×N1个局部单元的图象区域。每个单元被表示为代表每 个区域的区域代表性颜色(RRC)，和对应于代表性颜色值的精度的 可靠性分值(S)。\n而且，根据划分状态，第二级图象栅格和第三级图象栅格被划分 为包括M2×N2个和M3×N3个局部单元的图象区域，每个单元具有 区域代表性颜色(RRC)和可靠性分值(S)。\n例如，当第一级图象栅格的最大垂直长度M和水平长度N是8 (＝8×8)个局部单元时，第二级图象栅格的最大垂直长度M2和水 平长度N2是16(＝16×16)个局部单元，第三级图象栅格的最大水 平长度M3和垂直长度N3是32(＝32×32)个局部单元。\n其中，第三级图象栅格的某个单元Cell(i，j)被表示为区域代表性 颜色和可靠性分值C3 ij，S3 ij。\n此时，第一级、第二级和第三级的每个图象级的划分数目是根据 图象的纵横比确定的，从而精确地表示包含在图象中的对象的位置。 即，在较长边的情况下，均匀地划分较长边，并以较长边的划分单位 划分较短边。\n在用于产生图象栅格的另一种方法中，为了提高处理速度和考虑 图象中包含的对象的近似位置信息，可以将垂直和水平长度设置为相 同。\n下面对使用多级图象栅格数据结构的图象搜索方法进行说明。\n划分为多级图象栅格的不同图象被表示为代表区域的代表性区域 颜色(RRC)和表示代表性颜色的精度的可靠性分值，一对代表性区 域颜色和可靠性分值与另一对匹配，并根据用户基于内容的查询来计 算单元相似性，从而执行图象搜索。\n通过比较包含在每级的图象栅格中的单元和代表每个单元的区域 颜色(RRC)，使用多级图象栅格数据结构计算两个图象之间的颜色 相似性。即，使用代表单元C1和单元C2之间区域代表性颜色值的相 似性的颜色相似性Color_Sim(RRC_C1，RRC_C2)计算两个单元之间的 颜色相似性。\n第一权数(α)乘以颜色相似性Color_Sim(RRC_C1，RRC_C2)， 将颜色相似性Color_Sim(RRC_C1，RRC_C2)和第二权数(β)和相对 于两个单元之间可靠性的相似性I的乘积与颜色相似性和第一权数的 乘积结果相加。所得到的相加值除以第一权数和第二权数然后被归一 化，从而得到两个单元C1，C2的单元相似性Cell_Sim(C1，C2)。上述 运算可以表示如下。\n$\mathrm{Cell}\_\mathrm{Sim}(C1,C2)=\frac{(\alpha +\beta \times I)\times \mathrm{Color}\_\mathrm{Sim}(\mathrm{PRC}\_C1,\mathrm{PRC}\_C2)}{(\alpha +\beta )}......\left(1\right)$\n其中，两个单元之间的可靠性(S1，S2)的相似性I是根据I＝1- |S1-S2|得到的。\n因此，相对于多级图象的相同级之间的部分和不同级匹配两个不 同多级图象栅格之间的单元相似性，并比较图象之间的特征。\n图2表示根据本发明的使用多级图象栅格数据结构的图象搜索和 具有3级图象栅格数据结构的两个图象I1和I2的栅格之间的基于相似 性的搜索的实施例。\n两个图象I1和I2包括第一级图象栅格G1_1st，G2_1st，第二级图象 栅格G1_2nd，G2_2nd，和第三级图象栅格G1_3rd，G2_3rd。\n对两个图象中包含的两个栅格级之间的相似性Grid_Sim(G1，G2)进 行级间比较。上述运算可以表示如下。\nGrid_Sim(G1，G2)＝w1×Sim_of_the_ExactG1_1st_and_G2_1st\n                   +w2×Sim_of_the_ExactG1_2nd_and_G2_2nd\n                   +w3×Sim_of_the_ExactG1_3rd_and_G2_3rd\n                   +w4×Sim_of_the_InterG1_1st_and_G2_2nd\n                   +w5×Sim_of_the_InterG1_2nd_and_G2_3rd  -----(2)\n                   +w6×Sim_of_the_InterG1_3rd_and_G2_1st\n                   +w7×Sim_of_the_InterG1_1st_and_G2_3rd\n                   +w8×Sim_of_the_InterG1_2nd_and_G2_1st\n                   +w9×Sim_of_the_InterG1_3rd_and_G2_2nd\n其中w1到w9代表对于各自颜色相似性的权数，Sim_of_the_Exact代 表相对于两个图象I1，I2在相同图象栅格级之间的相似性， Sim_of_the_Inter代表相对于两个图象I1，I2不同图象栅格级之间的相 似性。\n即，根据如图3所示的匹配得到两个不同图象I1和I2中包含的相 同图象栅格级之间的相似性Sim_of_the_Exact。而且，根据如图4所 示的匹配得到两个不同图象I1和I2中包含的不同图象栅格级之间的相 似性Sim_of_the_Inter。\n下面将参照图5A和5B对上述操作进行详细说明。\n将对应于两个不同图象的相同级的两个单元的相似性相加，并通 过在水平和竖直方向按纵横比移位，将两个单元的相似性加到所得的 总计值。\n此时，通过把两个图象的某级的纵横比的差的绝对值加一，计算 两个栅格的匹配的数目。\n例如，如图5A所示，假设图象I1的纵横比的栅格的数目是M× N，图象I2的纵横比的栅格的数目是O×P，两个栅格之间的匹配总数 是(|M-O|+1)×(|N-P|+1)。\n通过根据两个栅格的纵横比基于不同移位量匹配两个栅格，计算 对应于相同栅格级Max(M，N)＝Max(O，P)的两个单元之间的相似性。\n此时，根据以下公式3-1，3-2得到基于两个图象I1和I2的相同级 之间的匹配的相似性Sim_of_the_Exact。\nSim_of_the_Exact＝Max(Sim_bet_two_levels_given_cell_corres S(i，j))\nVi，0≤i≤|M-O|\nVj，0≤i≤|N-P|             ------(3-1)\nSim_bet_two_levels_given_cell_corres S(i，j)\n$=\frac{\underset{y=o}{\overset{\mathrm{Min}|N-P|-1}{\Sigma }}(\underset{x=o}{\overset{\mathrm{Min}|M-O|-1}{\Sigma }}\mathrm{Sim}\_\mathrm{of}\_\mathrm{corres}\_\mathrm{two}\_\mathrm{cells}(x,y,i,j)}{\mathrm{Min}(N,P)\times \mathrm{Min}(M,O)}.....(3-2)$\n当匹配相同级之间的相似性(Sim_of_the_Exact)时，上述公式\n$=\underset{y=o}{\overset{\mathrm{Min}|N-P|-1}{\Sigma }}(\underset{x=o}{\overset{\mathrm{Min}|M-O|-1}{\Sigma }}\mathrm{Sim}\_\mathrm{of}\_\mathrm{corres}\_\mathrm{two}\_\mathrm{cells}(x,y,i,j)$ 代表相对于两个对应单 元的水平和垂直边的匹配的总和。\n通过基于纵横比M∶N，O∶P适用公式404到公式4-1，可得到 两个单元之间的相似性Sim_of_corres_two_cells。\nSim(CellG1(x+i，y+j)，cellG2(x，y))，    if  (Min(N，P)＝P)  ⌒ (Min(M，O)＝O)…(4-1)\nSim(CellG1(x+i，y)，  cellG2(x，y+j))，  if  (Min(N，P)＝N)  ⌒ (Min(M，O)＝O)…(4-2)\nSim(CellG1(x，y+i)，  cellG2(x+i，y))，  if  (Min(N，P)＝P)  ⌒ (Min(M，O)＝M)…(4-3)\nSim(CellG1(x，y)，    cellG2(x+i，y+j))，if  (Min(N，P)＝N)  ⌒ (Min(M，O)＝M)…(4-4)\n其中，当P小于N且M小于O时应用公式4-1，当栅格G1的长度N 小于栅格G2的长度P且栅格G2的宽度O小于栅格G1的宽度M时应 用公式4-2。而且，当栅格G2的垂直长度P小于栅格G1的N且栅格 G1的水平长度M小于G2的O时应用公式4-3，当G1的N小于G2的 P其M小于O时应用公式4-4。\n此时，将相对于栅格G1和栅格G2的长度之间的长度差(|M-O|， |N-P|)的移位量(i，j)加到单元坐标(x，y)，并且每个开始点(i，i，x，y) 变成0。\n通过匹配两个不同图象栅格级计算不同栅格级(Max(M，N)≠ Max(O，P)之间的相似性Sim_of_the_Inter。该操作与栅格级相似性 Sim_of_the_Exact的搜索相似。\n此外，基于|M-O|+1)×(|N-P|+1)得到不同图象栅格级之 间的图象栅格的匹配的数目。\n执行颜色区域匹配操作，以搜索多级图象栅格之间的代表性颜色 值相似的区域。该搜索基于以下方法执行，一种方法是用于从相同大 小的栅格级(精确比例匹配)之间的变换位置和相对位置来搜索颜色 相似性，一种方法是用于从不同大小的栅格级(比例间匹配)之间的 变换位置和相对位置搜索颜色相似性。\n即，基于一种用于从目标图象搜索相同级的颜色区域的方法执行 相同大小的图象栅格级(精确比例匹配)之间的颜色区域匹配操作。 基于目标图象的相同图象栅格级将该位置与相对位置匹配，然后计算 颜色区域的相似性，并将该位置与目标图象的相同级的变换位置进行 匹配，从而计算颜色区域的相似性。\n基于一种用于在目标图象间搜索不同级颜色区域的方法执行不同 图象栅格级(比例间匹配)之间的颜色区域匹配操作，并在目标图象 的不同图象栅格级中计算相同级的颜色区域的相似性。\n在不同图象栅格级之间的颜色区域匹配方法中，通过将位置与在 目标图象的不同图象栅格级中的相同位置进行匹配，计算颜色区域的 相似性，并通过将位置与目标图象的另一级的变换位置进行匹配，计 算颜色区域的相似性。\n如上所述，在本发明中，一个图象栅格数据结构被分为多级栅格 数据结构。因此，在使用划分的多级栅格结构搜索基于内容的图象时， 有可能高效地响应用户的主观查询。此外，在一定条件下，图象搜索 速度快、精度高。\n虽然为了例示目的公开了本发明的优选实施例，但是本领域技术 人员应理解，在不偏离所附权利要求的范围和精神的条件下，可以进 行各种改进，添加和替换。