文档和/或图像检索方法、文档和/或图像存储设备和检索设备转让专利
申请号 : CN200680006968.9
文献号 : CN101133429B
文献日 : 2010-10-06
发明人 : 黄濑浩一 , 中居友弘 , 岩村雅一
申请人 : 公立大学法人大阪府立大学
摘要 :
一种文档和/或图像检索方法，比较基于所拍摄的数字图像的特征点所计算的特征量和基于存储在数据库中的各文档和/或图像的特征点所预先计算的特征量，从数据库检索与所拍摄的数字图像相对应的文档和/或图像。从所拍摄的数字图像提取特征点；对所提取的各特征点定义特征点的局部集合；从所定义的局部集合选择特征点以定义局部集合的特征点子集；对于子集中的特征点的组合，确定不变量值作为表征各所选子集的值，不变量值对于几何变换是不变的；通过组合所确定的不变量值计算特征量；以及基于预先计算的文档和/或图像的特征量对数据库中的文档和/或图像进行投票处理，从而从数据库检索与所拍摄的数字图像相对应的文档和/或图像。
权利要求 :
1.一种文档和/或图像检索方法，用于通过比较基于所拍摄的数字图像的特征点所计算的特征量与基于存储在数据库中的各文档和/或图像的特征点所计算的特征量，来从数据库检索与所拍摄的数字图像相对应的文档和/或图像，所述方法包括：从所述拍摄的数字图像提取所述特征点；
对所提取的各特征点定义特征点的局部集合，所述局部集合为距离所述特征点最近的n个特征点的集合；
从所定义的局部集合选择所有可能的包括m个特征点的子集，其中m＜n；
对于各所述子集中的所有可能的d个特征点的组合，确定不变量值作为表征各所选子集的值，其中，d不大于m，并且所述不变量值对于几何变换是不变的；
通过组合所确定的不变量值计算特征量；以及基于预先计算的文档和/或图像的特征量对所述数据库中的文档和/或图像进行投票处理；
从而从所述数据库检索与所述拍摄的数字图像相对应的文档和/或图像。
2.根据权利要求1所述的文档和/或图像检索方法，其特征在于，所述不变量值是交比。
3.根据权利要求1所述的文档和/或图像检索方法，其特征在于，所述不变量值对于仿射变换是不变的。
4.根据权利要求1所述的文档和/或图像检索方法，其特征在于，所述不变量值对于相似变换是不变的。
5.一种使计算机执行以下步骤的文档和/或图像存储方法：输入文档和/或图像；
向所述输入的文档和/或图像分配ID；
从所述输入的文档和/或图像提取定义图像配置的特征点；以及对所提取的各特征点进行预定处理；
所述预定处理包括以下步骤：
(1)选择距离感兴趣的特征点p最近的n个特征点；以及(2)对从所述选择的n个特征点所选择的m个特征点的所有可能的各集合进行预定处理，其中m＜n；
步骤(2)中的所述预定处理包括以下步骤：(a)确定从感兴趣的m个点的集合所选择的d个点的所有可能的集合的特征量，其中d是不大于预定数量m的数量；
(b)通过预定计算，基于所确定的特征量，确定散列表的索引；以及(c)将所述特征量与点ID和文档ID相关联存储在所述散列表中，其中，在步骤(a)中使用所确定的散列索引确定所述特征量，将所述点ID分配给所述特征点p，将所述文档ID分配给从中提取所述特征点p的文档和/或图像。
6.一种用于检索通过根据权利要求5所述的存储方法所存储的文档和/或图像的文档和/或图像检索方法，所述检索方法使计算机执行以下步骤：读取所拍摄的图像；
从所读取的图像提取定义图像配置的特征点；
对所提取的各特征点进行预定处理；
所述预定处理包括以下步骤：
(1)选择距离感兴趣的特征点p最近的n个特征点；以及(2)对从所选择的n个特征点所选择的m个特征点的所有可能的各集合进行预定处理，其中m＜n；
步骤(2)中的所述预定处理包括以下步骤：(a)确定从感兴趣的m个点的集合所选择的d个点的所有可能的集合的特征量，其中d是不大于预定数量m的数量；
(b)通过预定计算，基于所确定的特征量，确定散列表的索引；以及(c)基于所确定的散列索引从所述散列表获取预先输入的文档和/或图像的特征量，将在步骤(a)所确定的所述特征量和所获取的特征量进行比较，并且对具有匹配特征量的文档ID投票；以及在步骤(1)和(2)后，基于投票结果指定与所拍摄的图像相匹配的文档和/或图像的文档ID。
7.一种文档和/或图像存储设备，包括：
输入部，输入文档和/或图像；
特征点提取部，从所输入的文档和/或图像提取定义图像配置的特征点；
特征点选择部，选择距离所提取的感兴趣的特征点p最近的n个特征点；以及特征量存储部，对从所述所选择的n个特征点所选择的m个特征点的所有可能的各集合进行预定处理，其中m＜n；
所述预定处理包括以下步骤：
(a)确定从感兴趣的m个点的集合所选择的d个点的所有可能的集合的特征量，其中d是不大于预定数量m的数量；
(b)通过预定计算，基于所确定的特征量，确定散列表的索引；以及(c)将所述特征量与点ID和文档ID相关联存储在所述散列表中，其中，在步骤(a)中使用所确定的散列索引确定所述特征量，将所述点ID分配给所述特征点p，将所述文档ID分配给从中提取所述特征点p的文档和/或图像。
8.一种文档和/或图像检索设备，其检索存储在根据权利要求7所述的文档和/或图像存储设备中的文档和/或图像，该检索设备包括：读取部，读取所拍摄的图像；
特征点提取部，从所读取的图像提取定义图像配置的特征点；
特征点选择部，选择距离所提取的感兴趣的特征点p最近的n个特征点；以及投票部，对从所选择的n个特征点所选择的m个特征点的所有可能的各集合进行预定处理，其中m＜n；
所述预定处理包括如下步骤：
(a)确定从感兴趣的m个点的集合所选择的d个点的所有可能的集合的特征量，其中d是不大于预定数量m的数量；
(b)通过预定计算，基于所确定的特征量，确定散列表的索引；以及(c)基于所确定的散列索引从所述散列表获取预先输入的文档和/或图像的特征量，将在步骤(a)所确定的所述特征量和所获取的特征量进行比较，并且对具有匹配特征量的文档ID投票；以及文档ID指定部，基于通过与所述各特征点相对应的投票所确定的投票结果，指定与所拍摄的图像相匹配的文档和/或图像的文档ID。
说明书 :
技术领域
本发明涉及一种利用数字照相机或扫描器等的文档和/或图像检索方法及其程序，涉及一种文档和/或图像存储设备和检索设备。
背景技术
数字照相机的普及、多功能化和小型化在模式识别(patternrecognition)和媒体理解(media understanding)领域带来了新的可能。其中一个这种可能是将用户所获取的图像链接到任一各种服务。这类可能性在字符和文档的领域中毫无例外地存在。对于基于照相机的字符识别和文档和/或图像分析开展了深入研究(例如，参考非专利文献1和2)。特别地，利用装配到移动电话的数字照相机的接口是重要的，并且利用该接口的字符读取处理和翻译处理等多种处理现正在考虑中(例如，参考非专利文献3和4)。
用于检索基于图像的文档和/或图像数据，即，文档和/或图像的在先技术方法如下。在Kauniskangas方法中，将文档和/或图像均分成段落区域和图形区域，其中，分类段落区域和图形区域并以树形结构表示它们。为了检索，判断询问和数据库中的文档和/或图像的各区域的匹配程度，并且输出具有最高匹配度的图像作为检索结果(例如，参考非专利文献5)。Hull公开了一种基于各单词的字符的数量的文档索引方法和检索方法、以及一种利用不变量的图像索引方法。
还公开了这样一种方法，在该方法中，以词为单位分割文档的文本，并且通过各单词的字符数量的序列所定义的特征量表示该文档。预先计算数据库中的文档的各部分的特征量，并将其存储在散列表中。为了检索输入的图像，以相同方式计算输入的图像的特征量。通过基于输入图像的特征量访问散列并进行投票来实现该检索(例如，参考专利文献1和非专利文献6)。
上述方法处理平板扫描器等所获得的高分辨率正确方向图像(correct-orientation image)。因此，这些方法不能用于基于数字照相机的文档和/或图像检索，将通过本发明对它们进行处理。例如，hull方法基于假定：在输入的图像中字符是可分开的。在较低清晰度的图像或经过投影变换等几何变换的图像的情况下，不满足该假定，通过本发明处理该情况。
专利文献1：JP-A-7(1995)-282088
非专利文献1：D.Doermann，J.Liang and H.Li，“Progress inCamera-Based Document Image Analysis”，Proc.ICDAR’03，pp.606-616(2003)
非专利文献2：K.Kise，S.Omachi，S.Uchida，M.Iwamura，“Current status and Future Prospects of Camera-Based CharacterRecognition and Document Image Analysis”，Technichal Reportof the IEICE，PRMU2004-246(2005.3)
非专利文献3：K.Yamada，S.Senda，“UbiquitousInformation Interface Using Mobile Camera”，Infromationprocessing，45，9，pp.923-297(2004)
非专利文献4：Y.Watanabe，Y.Okada，Y-B.Kim，T.Takeda，“Translation Camera”，Proc.ICPR’98，pp.613-617(1998)
非专利文献5：K.Hannu，“Document Image Retrieval withImprovements in Database Quality”，Academic Dissertation ofUniversity of Oulu(1999)
非专利文献6：J.J.Hull，“Document Image Matching andRetrieval with Multiple Distortion-Invariant Descriptors”，Document Analysis Systems，pp.379-396(1995)
用于检索基于图像的文档和/或图像数据，即，文档和/或图像的在先技术方法如下。在Kauniskangas方法中，将文档和/或图像均分成段落区域和图形区域，其中，分类段落区域和图形区域并以树形结构表示它们。为了检索，判断询问和数据库中的文档和/或图像的各区域的匹配程度，并且输出具有最高匹配度的图像作为检索结果(例如，参考非专利文献5)。Hull公开了一种基于各单词的字符的数量的文档索引方法和检索方法、以及一种利用不变量的图像索引方法。
还公开了这样一种方法，在该方法中，以词为单位分割文档的文本，并且通过各单词的字符数量的序列所定义的特征量表示该文档。预先计算数据库中的文档的各部分的特征量，并将其存储在散列表中。为了检索输入的图像，以相同方式计算输入的图像的特征量。通过基于输入图像的特征量访问散列并进行投票来实现该检索(例如，参考专利文献1和非专利文献6)。
上述方法处理平板扫描器等所获得的高分辨率正确方向图像(correct-orientation image)。因此，这些方法不能用于基于数字照相机的文档和/或图像检索，将通过本发明对它们进行处理。例如，hull方法基于假定：在输入的图像中字符是可分开的。在较低清晰度的图像或经过投影变换等几何变换的图像的情况下，不满足该假定，通过本发明处理该情况。
专利文献1：JP-A-7(1995)-282088
非专利文献1：D.Doermann，J.Liang and H.Li，“Progress inCamera-Based Document Image Analysis”，Proc.ICDAR’03，pp.606-616(2003)
非专利文献2：K.Kise，S.Omachi，S.Uchida，M.Iwamura，“Current status and Future Prospects of Camera-Based CharacterRecognition and Document Image Analysis”，Technichal Reportof the IEICE，PRMU2004-246(2005.3)
非专利文献3：K.Yamada，S.Senda，“UbiquitousInformation Interface Using Mobile Camera”，Infromationprocessing，45，9，pp.923-297(2004)
非专利文献4：Y.Watanabe，Y.Okada，Y-B.Kim，T.Takeda，“Translation Camera”，Proc.ICPR’98，pp.613-617(1998)
非专利文献5：K.Hannu，“Document Image Retrieval withImprovements in Database Quality”，Academic Dissertation ofUniversity of Oulu(1999)
非专利文献6：J.J.Hull，“Document Image Matching andRetrieval with Multiple Distortion-Invariant Descriptors”，Document Analysis Systems，pp.379-396(1995)
发明内容
本发明要解决的问题
本发明旨在提供一种用于通过使用由数字照相机或扫描仪等所捕获的文档和/或图像作为询问、从文档和/或图像数据库检索文档和/或图像的方法。与此有关的问题如下：
(1)由数字照相机或扫描仪等所捕获的询问的文档和/或图像遭受由投影变换等几何变换所引起的变形，并且不必包含整个文档。而且，询问图像在分辨率和照明条件上与存储在数据库中的文档和/或图像有极大的不同。这更加使得该问题变得复杂。换句话说，由于摄影角度，通常识别的询问的文档和/或图像不同于存储在数据库中的文档和/或图像。这使得难以判断图像中的对象的同一性。因此，需要一种能够适应摄影角度的差异的方法。
(2)为了精确检查图像的特征量，应该从图像提取较大数量的元素以定义特征量。然而，由于较大数量的元素，判断同一性需要相当长的时间。因此，需要一种判断同一性不需要相当长时间的方法。
(3)在处理多种文档和/或图像的情况下，存在更大量的相似文档和/或图像。难以从相似的文档和/或图像提取正确匹配的图像。因此，需要一种能够高精度地判断从相似的文档和/或图像所提取的图像的同一性的方法。
用于解决该问题的方法
为了解决这些问题，本发明中引入以下想法。
(1)为了提供文档和/或图像的特征量而免受由于几何变换而引起的变形的影响，特征量的计算使用对于几何变换的不变量。在本发明中，不变量的一个例子就是交比(cross-ratio)。交比是基于共线的四个点或共面的5个点所计算的值，并且已知为对于投影变换的不变量，投影变换是一种类型的几何变换。在使用交比的情况下，通过点(特征点)定义感兴趣的文档和/或图像的特征量。在英文文档的情况下，例如，使用单词的重心作为用于计算交比的特征点。为了使可以利用图像的一部分进行检索，基于针对文档和/或图像的各部分所计算的交比计算特征量。除投影变换以外，还考虑仿射变换和相似变换。
(2)存在巨大量的特征点的可能组合，因此，考虑特征点的所有可能组合的对应关系是不现实的。因此，在本发明中，对于检索使用利用散列的投票处理，而无需特征点的外在对应关系。在存储中，基于从文档和/或图像提取的特征点计算特征量，并基于根据特征量所确定的索引将特征量存储在散列表中。在检索中，以相同方式确定特征点、特征量和询问的索引，并且为了向所存储的文档和/或图像投票访问散列表。对于文档和/或图像检索很少采用传统已知概念的投票处理。
(3)在基于交比的值检查图像的同一性的情况下，计算交比所基于的特征点应具有图像之间的对应关系。然而，当相互关联从各图像提取的N个点时，有N！个组合。为了确保充分的判断精度，应该使用足够大量的特征点。然而，这将导致过大的计算复杂度。
几何散列方法中的大的计算复杂度O(N3)是Hull的发明的动机之一。说明了使用三个或四个或更多个特征点(感兴趣的点)以提供对于旋转和缩放的不变量(后面说明的相似不变量)。然而，即使使用Hull方法，从O(N3)个不同组合中的N个特征点提取三个点，因此组合的数量基本与传统方法中的相等。因此，与传统方法相比，不能清楚将计算复杂度降低了多少。因而，需要一种与传统方法相比降低计算复杂度的方法。
这里，O(N)和O(N3)均表示该解决方案所需的近似计算复杂度。在指定N的情况下，O(N)表示计算复杂度不大于aN+b，而O(N3)表示计算复杂度不大于aN3+bN2+cN+d(其中，a、b、c、d是常数)。
根据本发明，定义围绕感兴趣的特定特征点的区域的特征量。也就是说，从该区域提取距离感兴趣的点最近的n个点。如果从n个点选择m个点(基于这m个点计算交比，4或5＜m＜n)，甚至在几何变换的情况下，在来自n个最近的点的某些作为结果的m个点的集合中可以发现匹配。因此，检查来自距离各特征点最近的n个点的所有可能的m个点的集合。通过适当选择数量n和m，可以避免巨大量的计算。在本发明中，在象在Hull方法中一样使用对于相似变换的不变量的情况下，将计算复杂度从O(N3)降低到了O(N)。在使用对于投影变换的不变量的情况下，将计算复杂度从O(N5)降低到了O(N)。在使用对于仿射变换的不变量的情况下，将计算复杂度从O(N4)降低到了O(N)。
在基于从m个点所选择的四个或五个点的集合计算交比的情况下，存在某些交比等于其它图像的交比的可能性，但是在所有交比中发现匹配是极少的。结果，可以高精确地判断同一性。
换句话说，本发明提供了一种使用不同于在先技术的识别处理的切实可行的检索方法。更具体地，部分或整个使用由数字照相机或扫描器等所捕获的文档和/或图像作为“询问”，并且从数据库检索包含询问的文档和/或图像。这样一种检索处理可用于与手边的打印后的材料相对应的电子文档的检索，或者作为用于提取打印后的材料中的注解的预处理。
利用数字照相机的文档和/或图像检索与在先技术的文档和/或图像检索显著的不同在于图像经受各种类型的变形。在在先技术中，由扫描器在理想条件下所获得的文档和/或图像所经受的几何变形是通常由相似变换引起的旋转变形。相反，由数字照相机所拍摄的文档和/或图像遭受由于投影变换而引起的变形。在利用扫描器捕获书籍等三维对象上的文档和/或图像的情况下，例如，至少图像的一部分遭受由于仿射变换或相似变换而引起的变形。考虑到数字照相机(尤其装配至移动电话的数字照相机)和小型扫描器的特性，希望还可以使用部分文档和/或图像作为用于检索的询问(可以基于图像的一部分的图像检索)。
最终，在本发明中包含上述两个想法。其中一个想法是对于索引文档和/或图像使用对于几何变换是不变量的交比。基于文档和/或图像的不同部分计算交比，并且用于索引，从而允许基于部分图像的检索。另一个想法是对于检索使用利用散列的投票处理。这使得可以相对高速地灵活进行检索，而无需外在相互关联特征点。
在计算机视觉的领域中，通常使用交比作为对于各种类型的变换的不变量。根据下面的公式计算图1所示的同一平面上的共线点ABCD的交比：
[公式1]
而且，可以针对从如图2所示的5个共面点所获得的线性排列的4个点计算交比。这里，计算点ABCDE的交比作为点A’B’C’D’的交比。而且，还已知如下表示的5个共面点的不变量。
[公式2]
这里，P(A，B，C)是由顶角A、B、C所定义的三角形的面积。在本发明中，基于这样的交比计算文档和/或图像唯一的特征量，并将其用于文档和/或图像的检索。
可以使用除交比以外的对于几何变换的不变量(几何不变量)。几何不变量即使在几何变换的情况下也保持不变，并且根据几何变换的种类有各种类型的几何不变量。
换句话说，基于根据f个共面点所确定的几何不变量计算特征量。计算几何不变量所需的点的数量f根据不变量的类型而不同。下面说明几何不变量的例子。
1.交比：如上所述，交比是对于投影变换的不变量，并且基于 5个共面点ABCDE(f＝5)的坐标计算为{P(A，B，C)P(A，D，E)/P(A，B，D)P(A，C，E)}。由于交比是投影不变量，因而即使由于投影变形因而点ABCDE的坐标发生改变，交比的值保持不变。
2.仿射不变量：仿射不变量是对于仿射变换的不变量。与投影变换相比，保持线的平行的仿射变换是更具限制性的。考虑到经过投影变换的平面上的有限局部区域，投影变换近似于仿射变换。因此，认为在基于局部排列的点的本发明的方法中可以代替交比使用仿射不变量。
例如，基于四个共面点ABCD(f＝4)的坐标计算仿射不变量为P(A，C，D)/P(A，B，C).
3.相似不变量：与仿射变换相比，仅基于缩放、旋转和转换的相似变换更具限制性。在相似变换中，线间所定义的角度、距离比、以及面积与距离的平方的比是不变量。例如，可以使用针对三个点ABC(f＝3)的计算为AC/AB的距离比。
基于图像中的特征点所获得的不变量值是连续的，并且为了进行索引应该离散化不变量值。在一个优选方法中，将不变量值量子化成k个水平，这是通过如下确定的：通过在预先实验中准备基于特征点所获得的不变量值的直方图，并根据直方图中的不变量值的出现频率向不变量值分配离散值。
基于上述想法，本发明提供了一种用于基于所拍摄的数字图像从存储文档和/或图像的数据库检索文档和/或图像的文档和/或图像检索方法该方法包括：从所拍摄的图像提取特征点；基于特征点的不变量值确定所拍摄的图像的特征量；以及通过对具有匹配该数字图像的特征量的特征量的文档和/或图像投票，根据存储在数据库中的文档和/或图像信息检索与该数字图像相对应的文档和/或图像。
特征点可以是重复出现在所拍摄的图像中的特定部分。
特征点可以是单词区域的重心。在文档是英语等语言的并包含相互分离的单词区域的情况下，通过使用单词区域的重心作为特征点，可以精确地识别文档的特征量。
特征点可以是后面说明的黑色像素的连结成分的重心。
特征点可以是日本汉字的闭锁空间。即使文档是日语等语言的并包含不能相互分开的单词区域，通过使用日本汉字的闭锁空间作为特征点，可以精确地识别文档的特征量。
不变量值可以是交比。通过使用交比，可以基于经过几何变换的图像检索原始图像。
可以使用利用数字摄像机或扫描器的数字照相方法。
特征量可以是基于为从各局部特征点集合所选择的一组特征点所计算的不变量值而计算的值。
因此，基于各局部特征点集合计算特征量，从而与为特征点的所有可能组合计算不变量值的情况相比，降低了计算复杂度。因此，减少了判断同一性所需的处理时间。由于特征量的计算是基于各局部特征点集合，因而可以基于部分图像进行检索。
可选地，特征量可以是基于分别为从各局部特征点集合所选择的多组特征点所确定的多个不变量值而计算的特征量，从而确保更高辨别力。利用该配置，使用交比集合作为特征量，这使得可以精确地判断相似文档和/或图像的同一性。
本发明提供了一种使计算机执行以下步骤的文档和/或图像存储方法：输入文档和/或图像；向输入的文档和/或图像分配ID；从输入的文档和/或图像提取定义图像配置的特征点；以及对所提取的各特征点进行预定处理；预定处理包括以下步骤：(1)选择距离感兴趣的特征点p最近的n个特征点；以及(2)对从所选择的n个特征点所选择的m个特征点(m＜n)的所有可能的各集合进行预定处理；步骤(2)中的预定处理包括以下步骤：(a)确定从感兴趣的m个点的集合所选择的d个点(其中，d是不大于预定数量m的数量(例如，4或5))的所有可能的集合的特征量；(b)通过预定计算，基于所确定的特征量，确定散列表的索引；以及(c)将特征量与点ID和文档ID相关联存储在散列表中，其中，在步骤(a)中使用所确定的散列索引确定特征量，将点ID分配给特征点p，而将文档ID分配给从其提取特征点的文档和/或图像。
在该存储方法中，将距离各特征点p最近的n个特征点定义为局部集合，并且为来自局部集合的m个点的集合的每一个计算特征量。因此，与从所有特征点选择m个点的情况相比，降低了为其计算特征量的m个点的集合的数量。因此，减少了计算所需时间。而且，该方法允许基于部分图像的检索。
由于为从m个特征点所选择的d个点的所有可能的集合确定特征量，因而提高了特征量的辨别力。
特征量可以由来自m个特征点的所有可能的5个点的各集合中的5个特征点的循环排列所确定的交比构成。
在步骤(b)中，可以根据下面的公式基于特征量计算散列索引：
[公式3]
其中crn(n＝0～4)是5个离散交比值，Vmax是离散交比值中最大的一个，而pat是分配给来自m个点的5个点的各集合的组合模式ID，并取值0～mC5-1。
在步骤(b)，可以根据下面的公式基于特征量计算散列索引：
[公式4]
其中，k是交比的量子化的水平的数量，Hsize是散列表的大小，而crn是来自m个点的5个点的集合的交比值。
本发明提供了一种用于检索通过上述存储方法所存储的文档和/或图像的检索方法，该检索方法使计算机执行以下步骤：读取所拍摄的图像；从所读取的图像提取定义图像配置的特征点；以及对所提取的各特征点进行预定处理；预定处理包括以下步骤：(1)选择距离感兴趣的特征点p最近的n个特征点；以及(2)对从所选择的n个特征点所选择的m个特征点(m＜n)的所有可能的各集合进行预定处理；步骤(2)中的预定处理包括以下步骤：(a)确定从感兴趣的m个点的集合所选择的d个点(其中，d是不大于预定数量m的数量(例如，4或5))的所有可能的集合的特征量；(b)通过预定计算，基于所确定的特征量，确定散列表的索引；以及(c)基于确定的散列索引从散列表获取预先输入的文档和/或图像的特征量，将在步骤(a)所确定的特征量和所获取的特征量进行比较，并且对具有匹配特征量的文档ID投票；以及在步骤(1)和(2)后，基于投票结果指定与所拍摄的图像相匹配的文档和/或图像的文档ID。
在该检索方法中，将距离各特征点p最近的n个特征点定义为局部集合，并且对来自局部集合的m个点的各集合计算特征量。因此，与从所有特征点选择m个点的情况相比，降低了计算其的特征量的m个点的集合的数量。因此，减少了计算所需时间。而且，该方法允许基于部分图像的检索。
由于为从m个特征点所选择的d个点的所有可能集合确定特征量，因而提高了特征量的辨别力。
特征量可以是为来自m个特征点的所有可能的5个点的各集合中的5个特征点的循环排列所确定的交比。
在步骤(b)中，可以根据下面的公式基于特征量计算散列索引：
[公式5]
其中crn(n＝0～4)是5个离散交比值，Vmax是离散交比值中最大的一个，而pat是分配给来自m个点的5个点的各集合的组合模式ID，并取值0～mC5-1。
在步骤(b)，可以根据下面的公式基于特征量计算散列索引：
[公式6]
其中，k是交比的量子化的水平的数量，Hsize是散列表的大小，而crn是来自m个点的5个点的集合的交比值。
例如，可以利用通用个人计算机实现文档和/或图像存储方法和文档和/或图像检索方法。
根据本发明的另一方面，提供了一种使计算机进行用于从存储文档和/或图像的数据库检索与所拍摄的图像相对应的文档和/或图像的处理的程序，该处理包括：从所拍摄的图像提取特征点；基于各特征点的不变量值确定图像的特征量；以及对数据库中具有匹配所确定的特征量的文档和/或图像投票。
本发明还提供了一种使计算机执行以下步骤的文档和/或图像存储程序：输入文档和/或图像；向所输入的文档和/或图像分配ID；从所输入的文档和/或图像提取定义图像配置的特征点；以及对所提取的各特征点进行预定处理；预定处理包括以下步骤：(1)选择距离感兴趣的特征点p最近的n个特征点；以及(2)对从所选择的n个特征点所选择的m个特征点(m＜n)的所有可能的各集合进行预定处理；步骤(2)中的预定处理包括以下步骤：(a)确定从感兴趣的m个点的集合所选择的d个点(其中，d是不大于预定数量m的数量(例如，4或5))的所有可能的集合的特征量；(b)通过预定计算，基于所确定的特征量，确定散列表的索引；以及(c)将特征量与点ID和文档ID相关联存储在散列表中，其中，在步骤(a)中使用所确定的散列索引确定特征量，将点ID分配给特征点p，而将文档ID分配给从其提取所述特征点的文档和/或图像。
本发明还提供了一种用于检索使用上述存储程序所输入的文档和/或图像的文档和/或图像检索程序，该检索程序使计算机执行以下步骤：读取所拍摄的图像；从所读取的图像提取定义图像配置的特征点；以及对所提取的各特征点进行预定处理；预定处理包括以下步骤：(1)选择距离感兴趣的特征点p最近的n个特征点；以及(2)对从所选择的n个特征点所选择的m个特征点(m＜n)的所有可能的各集合进行预定处理；步骤(2)中的预定处理包括以下步骤：(a)确定从感兴趣的m个点的集合所选择的d个点(其中，d是不大于预定数量m的数量(例如，4或5))的所有可能的集合的特征量；(b)通过预定计算，基于所确定的特征量，确定散列表的索引；以及(c)基于所确定的散列索引从散列表获取预先输入的文档和/或图像的特征量，将在步骤(a)所确定的特征量和所获取的特征量进行比较，并且对具有匹配特征量的文档ID投票；以及在步骤(1)和(2)后，基于投票结果指定与所拍摄的图像相匹配的文档和/或图像的文档ID。
例如，可以在通用个人计算机上执行文档和/或图像存储程序和文档和/或图像检索程序。
根据本发明的另一方面，提供了一种存储设备，包括：输入部，输入文档和/或图像；特征点提取部，从所输入的文档和/或图像提取定义图像配置的特征点；特征点选择部，选择距离所提取的感兴趣的特征点p最近的n个特征点；以及特征量存储部，对从所选择的n个特征点所选择的m个特征点(m＜n)的所有可能的各集合进行预定处理；预定处理包括以下步骤：(a)确定从感兴趣的m个点的集合所选择的d个点(其中，d是不大于预定数量m的数量(例如，4或5))的所有可能的集合的特征量；(b)通过预定计算，基于所确定的特征量，确定散列表的索引；以及(c)将特征量与点ID和文档ID相关联存储在散列表中，其中，在步骤(a)中使用所确定的散列索引确定特征量，将点ID分配给特征点p，而将文档ID分配给从其提取特征点的文档和/或图像。
文档和/或图像存储设备可以使用通用个人计算机作为硬件。在这种情况下，输入部包括与用于传送文档和/或图像数据的外部装置进行通信的通信I/F、和用于对于存储数据的记录介质进行读写的驱动器(例如，DVD驱动器或CD驱动器)、或者读取图像的扫描器。通过使个人计算机的CPU执行所安装的应用程序，进行特征点提取部、特征点选择部和特征量存储部的功能。可选地，可以利用使用DSP和ASIC的专用硬件执行这些功能。
而且，本发明提供了一种存储由该存储设备所存储的文档和/或图像的文档和/或图像存储设备。
该文档和/或图像存储设备使用通用文件服务器作为硬件。
本发明还提供了一种用于检索存储在上述文档和/或图像存储设备中的文档和/或图像的文档和/或图像检索设备，该检索设备包括：读取部，读取所拍摄的图像；特征点提取部，从所读取的图像提取定义图像配置的特征点；特征点选择部，选择距离所提取的感兴趣的特征点p最近的n个特征点；以及投票部，对从所选择的n个特征点所选择的m个特征点(m＜n)的所有可能的各集合进行预定处理；(a)确定从感兴趣的m个点的集合所选择的d个点(其中，d是不大于预定数量m的数量(例如，4或5))的所有可能的集合的特征量；(b)通过预定计算，基于所确定的特征量，确定散列表的索引；以及(c)基于所确定的散列索引从散列表获取预先输入的文档和/或图像的特征量，将在步骤(a)所确定的特征量和所获取的特征量进行比较，并且对具有匹配特征量的文档ID投票；以及文档ID指定部，基于通过与各特征点相对应的投票所确定的投票结果，指定与所拍摄的图像相匹配的文档和/或图像的文档ID。
文档和/或图像检索设备可以使用通用个人计算机作为硬件。在这种情况下，读取部包括用于接收所拍摄的图像的通信I/F、以及用于从其中记录所拍摄的图像的SD卡(注册商标)或存储器棒(注册商标)等记录介质读取数据的I/F。通过使个人计算机的CPU执行所安装的应用程序，执行特征点提取部、特征点选择部和投票部的功能。可选地，可以利用使用DSP和ASIC的专用硬件进行这些功能。
文档和/或图像检索设备可以具有与文档和/或图像存储设备一样的功能。可选地，文档和/或图像检索设备还可以用作文档和/或图像存储设备。文档和/或图像检索设备还可以用作文档和/或图像存储设备以及文档和/或图像存储设备。
这里的术语“文档”是指数据库中积累的和从数据库检索的文本信息。文档的例子包括合同文书和宣传册等商务文档、科学技术论文、报纸和目录册。这里将术语“图像”定义为拍摄的、被积累在数据库中和从数据库中检索的非文本模式信息。图像的例子包括图形、图画、照片和海报。文档和/或图像属于图像的范畴。
这里的术语“连结成分”是指图像中相互连结的一组像素。更具体地，在存在与一个像素垂直和横向成连结关系的像素的情况下，相互连结这些像素以形成连结成分。这里的术语“特征点”是指表示图像的特征量的各个点，并且通过图像处理提取特征点。这里的术语“不变量”是表示对于几何变换是不变的参量的通称。几何变换的一个例子是旋转。即使旋转图像，图像中的对象的面积也不会改变。因此，对象的面积是对于旋转的示例不变量。而且，边长比是对于缩放的示例不变量。除旋转和缩放等相似变换以外，几何变换的例子包括投影变换和仿射变换。
这里的术语“投票”是指在信息处理领域中用于计算部分证据(partial evidences)的处理。更具体地，在该处理中，基于所获取的证据给予可选项的得分，并且选择可选项之中具有最高累积得分的那个。大体而言，证据具有不同的得分。
而且，这里的术语“询问”是表示用户的检索请求的数据。在本发明中，用户输入图像作为询问。也就是说，用户输入询问图像，以从数据库检索匹配询问图像的图像。
本发明的效果
根据本发明，从由数字照相机或扫描器等所捕获的图像提取特征点，并且基于特征点计算用于文档和/或图像检索的不变量值。因此，可以精确地检索想要的文档和/或图像。
本发明旨在提供一种用于通过使用由数字照相机或扫描仪等所捕获的文档和/或图像作为询问、从文档和/或图像数据库检索文档和/或图像的方法。与此有关的问题如下：
(1)由数字照相机或扫描仪等所捕获的询问的文档和/或图像遭受由投影变换等几何变换所引起的变形，并且不必包含整个文档。而且，询问图像在分辨率和照明条件上与存储在数据库中的文档和/或图像有极大的不同。这更加使得该问题变得复杂。换句话说，由于摄影角度，通常识别的询问的文档和/或图像不同于存储在数据库中的文档和/或图像。这使得难以判断图像中的对象的同一性。因此，需要一种能够适应摄影角度的差异的方法。
(2)为了精确检查图像的特征量，应该从图像提取较大数量的元素以定义特征量。然而，由于较大数量的元素，判断同一性需要相当长的时间。因此，需要一种判断同一性不需要相当长时间的方法。
(3)在处理多种文档和/或图像的情况下，存在更大量的相似文档和/或图像。难以从相似的文档和/或图像提取正确匹配的图像。因此，需要一种能够高精度地判断从相似的文档和/或图像所提取的图像的同一性的方法。
用于解决该问题的方法
为了解决这些问题，本发明中引入以下想法。
(1)为了提供文档和/或图像的特征量而免受由于几何变换而引起的变形的影响，特征量的计算使用对于几何变换的不变量。在本发明中，不变量的一个例子就是交比(cross-ratio)。交比是基于共线的四个点或共面的5个点所计算的值，并且已知为对于投影变换的不变量，投影变换是一种类型的几何变换。在使用交比的情况下，通过点(特征点)定义感兴趣的文档和/或图像的特征量。在英文文档的情况下，例如，使用单词的重心作为用于计算交比的特征点。为了使可以利用图像的一部分进行检索，基于针对文档和/或图像的各部分所计算的交比计算特征量。除投影变换以外，还考虑仿射变换和相似变换。
(2)存在巨大量的特征点的可能组合，因此，考虑特征点的所有可能组合的对应关系是不现实的。因此，在本发明中，对于检索使用利用散列的投票处理，而无需特征点的外在对应关系。在存储中，基于从文档和/或图像提取的特征点计算特征量，并基于根据特征量所确定的索引将特征量存储在散列表中。在检索中，以相同方式确定特征点、特征量和询问的索引，并且为了向所存储的文档和/或图像投票访问散列表。对于文档和/或图像检索很少采用传统已知概念的投票处理。
(3)在基于交比的值检查图像的同一性的情况下，计算交比所基于的特征点应具有图像之间的对应关系。然而，当相互关联从各图像提取的N个点时，有N！个组合。为了确保充分的判断精度，应该使用足够大量的特征点。然而，这将导致过大的计算复杂度。
几何散列方法中的大的计算复杂度O(N3)是Hull的发明的动机之一。说明了使用三个或四个或更多个特征点(感兴趣的点)以提供对于旋转和缩放的不变量(后面说明的相似不变量)。然而，即使使用Hull方法，从O(N3)个不同组合中的N个特征点提取三个点，因此组合的数量基本与传统方法中的相等。因此，与传统方法相比，不能清楚将计算复杂度降低了多少。因而，需要一种与传统方法相比降低计算复杂度的方法。
这里，O(N)和O(N3)均表示该解决方案所需的近似计算复杂度。在指定N的情况下，O(N)表示计算复杂度不大于aN+b，而O(N3)表示计算复杂度不大于aN3+bN2+cN+d(其中，a、b、c、d是常数)。
根据本发明，定义围绕感兴趣的特定特征点的区域的特征量。也就是说，从该区域提取距离感兴趣的点最近的n个点。如果从n个点选择m个点(基于这m个点计算交比，4或5＜m＜n)，甚至在几何变换的情况下，在来自n个最近的点的某些作为结果的m个点的集合中可以发现匹配。因此，检查来自距离各特征点最近的n个点的所有可能的m个点的集合。通过适当选择数量n和m，可以避免巨大量的计算。在本发明中，在象在Hull方法中一样使用对于相似变换的不变量的情况下，将计算复杂度从O(N3)降低到了O(N)。在使用对于投影变换的不变量的情况下，将计算复杂度从O(N5)降低到了O(N)。在使用对于仿射变换的不变量的情况下，将计算复杂度从O(N4)降低到了O(N)。
在基于从m个点所选择的四个或五个点的集合计算交比的情况下，存在某些交比等于其它图像的交比的可能性，但是在所有交比中发现匹配是极少的。结果，可以高精确地判断同一性。
换句话说，本发明提供了一种使用不同于在先技术的识别处理的切实可行的检索方法。更具体地，部分或整个使用由数字照相机或扫描器等所捕获的文档和/或图像作为“询问”，并且从数据库检索包含询问的文档和/或图像。这样一种检索处理可用于与手边的打印后的材料相对应的电子文档的检索，或者作为用于提取打印后的材料中的注解的预处理。
利用数字照相机的文档和/或图像检索与在先技术的文档和/或图像检索显著的不同在于图像经受各种类型的变形。在在先技术中，由扫描器在理想条件下所获得的文档和/或图像所经受的几何变形是通常由相似变换引起的旋转变形。相反，由数字照相机所拍摄的文档和/或图像遭受由于投影变换而引起的变形。在利用扫描器捕获书籍等三维对象上的文档和/或图像的情况下，例如，至少图像的一部分遭受由于仿射变换或相似变换而引起的变形。考虑到数字照相机(尤其装配至移动电话的数字照相机)和小型扫描器的特性，希望还可以使用部分文档和/或图像作为用于检索的询问(可以基于图像的一部分的图像检索)。
最终，在本发明中包含上述两个想法。其中一个想法是对于索引文档和/或图像使用对于几何变换是不变量的交比。基于文档和/或图像的不同部分计算交比，并且用于索引，从而允许基于部分图像的检索。另一个想法是对于检索使用利用散列的投票处理。这使得可以相对高速地灵活进行检索，而无需外在相互关联特征点。
在计算机视觉的领域中，通常使用交比作为对于各种类型的变换的不变量。根据下面的公式计算图1所示的同一平面上的共线点ABCD的交比：
[公式1]
而且，可以针对从如图2所示的5个共面点所获得的线性排列的4个点计算交比。这里，计算点ABCDE的交比作为点A’B’C’D’的交比。而且，还已知如下表示的5个共面点的不变量。
[公式2]
这里，P(A，B，C)是由顶角A、B、C所定义的三角形的面积。在本发明中，基于这样的交比计算文档和/或图像唯一的特征量，并将其用于文档和/或图像的检索。
可以使用除交比以外的对于几何变换的不变量(几何不变量)。几何不变量即使在几何变换的情况下也保持不变，并且根据几何变换的种类有各种类型的几何不变量。
换句话说，基于根据f个共面点所确定的几何不变量计算特征量。计算几何不变量所需的点的数量f根据不变量的类型而不同。下面说明几何不变量的例子。
1.交比：如上所述，交比是对于投影变换的不变量，并且基于 5个共面点ABCDE(f＝5)的坐标计算为{P(A，B，C)P(A，D，E)/P(A，B，D)P(A，C，E)}。由于交比是投影不变量，因而即使由于投影变形因而点ABCDE的坐标发生改变，交比的值保持不变。
2.仿射不变量：仿射不变量是对于仿射变换的不变量。与投影变换相比，保持线的平行的仿射变换是更具限制性的。考虑到经过投影变换的平面上的有限局部区域，投影变换近似于仿射变换。因此，认为在基于局部排列的点的本发明的方法中可以代替交比使用仿射不变量。
例如，基于四个共面点ABCD(f＝4)的坐标计算仿射不变量为P(A，C，D)/P(A，B，C).
3.相似不变量：与仿射变换相比，仅基于缩放、旋转和转换的相似变换更具限制性。在相似变换中，线间所定义的角度、距离比、以及面积与距离的平方的比是不变量。例如，可以使用针对三个点ABC(f＝3)的计算为AC/AB的距离比。
基于图像中的特征点所获得的不变量值是连续的，并且为了进行索引应该离散化不变量值。在一个优选方法中，将不变量值量子化成k个水平，这是通过如下确定的：通过在预先实验中准备基于特征点所获得的不变量值的直方图，并根据直方图中的不变量值的出现频率向不变量值分配离散值。
基于上述想法，本发明提供了一种用于基于所拍摄的数字图像从存储文档和/或图像的数据库检索文档和/或图像的文档和/或图像检索方法该方法包括：从所拍摄的图像提取特征点；基于特征点的不变量值确定所拍摄的图像的特征量；以及通过对具有匹配该数字图像的特征量的特征量的文档和/或图像投票，根据存储在数据库中的文档和/或图像信息检索与该数字图像相对应的文档和/或图像。
特征点可以是重复出现在所拍摄的图像中的特定部分。
特征点可以是单词区域的重心。在文档是英语等语言的并包含相互分离的单词区域的情况下，通过使用单词区域的重心作为特征点，可以精确地识别文档的特征量。
特征点可以是后面说明的黑色像素的连结成分的重心。
特征点可以是日本汉字的闭锁空间。即使文档是日语等语言的并包含不能相互分开的单词区域，通过使用日本汉字的闭锁空间作为特征点，可以精确地识别文档的特征量。
不变量值可以是交比。通过使用交比，可以基于经过几何变换的图像检索原始图像。
可以使用利用数字摄像机或扫描器的数字照相方法。
特征量可以是基于为从各局部特征点集合所选择的一组特征点所计算的不变量值而计算的值。
因此，基于各局部特征点集合计算特征量，从而与为特征点的所有可能组合计算不变量值的情况相比，降低了计算复杂度。因此，减少了判断同一性所需的处理时间。由于特征量的计算是基于各局部特征点集合，因而可以基于部分图像进行检索。
可选地，特征量可以是基于分别为从各局部特征点集合所选择的多组特征点所确定的多个不变量值而计算的特征量，从而确保更高辨别力。利用该配置，使用交比集合作为特征量，这使得可以精确地判断相似文档和/或图像的同一性。
本发明提供了一种使计算机执行以下步骤的文档和/或图像存储方法：输入文档和/或图像；向输入的文档和/或图像分配ID；从输入的文档和/或图像提取定义图像配置的特征点；以及对所提取的各特征点进行预定处理；预定处理包括以下步骤：(1)选择距离感兴趣的特征点p最近的n个特征点；以及(2)对从所选择的n个特征点所选择的m个特征点(m＜n)的所有可能的各集合进行预定处理；步骤(2)中的预定处理包括以下步骤：(a)确定从感兴趣的m个点的集合所选择的d个点(其中，d是不大于预定数量m的数量(例如，4或5))的所有可能的集合的特征量；(b)通过预定计算，基于所确定的特征量，确定散列表的索引；以及(c)将特征量与点ID和文档ID相关联存储在散列表中，其中，在步骤(a)中使用所确定的散列索引确定特征量，将点ID分配给特征点p，而将文档ID分配给从其提取特征点的文档和/或图像。
在该存储方法中，将距离各特征点p最近的n个特征点定义为局部集合，并且为来自局部集合的m个点的集合的每一个计算特征量。因此，与从所有特征点选择m个点的情况相比，降低了为其计算特征量的m个点的集合的数量。因此，减少了计算所需时间。而且，该方法允许基于部分图像的检索。
由于为从m个特征点所选择的d个点的所有可能的集合确定特征量，因而提高了特征量的辨别力。
特征量可以由来自m个特征点的所有可能的5个点的各集合中的5个特征点的循环排列所确定的交比构成。
在步骤(b)中，可以根据下面的公式基于特征量计算散列索引：
[公式3]
其中crn(n＝0～4)是5个离散交比值，Vmax是离散交比值中最大的一个，而pat是分配给来自m个点的5个点的各集合的组合模式ID，并取值0～mC5-1。
在步骤(b)，可以根据下面的公式基于特征量计算散列索引：
[公式4]
其中，k是交比的量子化的水平的数量，Hsize是散列表的大小，而crn是来自m个点的5个点的集合的交比值。
本发明提供了一种用于检索通过上述存储方法所存储的文档和/或图像的检索方法，该检索方法使计算机执行以下步骤：读取所拍摄的图像；从所读取的图像提取定义图像配置的特征点；以及对所提取的各特征点进行预定处理；预定处理包括以下步骤：(1)选择距离感兴趣的特征点p最近的n个特征点；以及(2)对从所选择的n个特征点所选择的m个特征点(m＜n)的所有可能的各集合进行预定处理；步骤(2)中的预定处理包括以下步骤：(a)确定从感兴趣的m个点的集合所选择的d个点(其中，d是不大于预定数量m的数量(例如，4或5))的所有可能的集合的特征量；(b)通过预定计算，基于所确定的特征量，确定散列表的索引；以及(c)基于确定的散列索引从散列表获取预先输入的文档和/或图像的特征量，将在步骤(a)所确定的特征量和所获取的特征量进行比较，并且对具有匹配特征量的文档ID投票；以及在步骤(1)和(2)后，基于投票结果指定与所拍摄的图像相匹配的文档和/或图像的文档ID。
在该检索方法中，将距离各特征点p最近的n个特征点定义为局部集合，并且对来自局部集合的m个点的各集合计算特征量。因此，与从所有特征点选择m个点的情况相比，降低了计算其的特征量的m个点的集合的数量。因此，减少了计算所需时间。而且，该方法允许基于部分图像的检索。
由于为从m个特征点所选择的d个点的所有可能集合确定特征量，因而提高了特征量的辨别力。
特征量可以是为来自m个特征点的所有可能的5个点的各集合中的5个特征点的循环排列所确定的交比。
在步骤(b)中，可以根据下面的公式基于特征量计算散列索引：
[公式5]
其中crn(n＝0～4)是5个离散交比值，Vmax是离散交比值中最大的一个，而pat是分配给来自m个点的5个点的各集合的组合模式ID，并取值0～mC5-1。
在步骤(b)，可以根据下面的公式基于特征量计算散列索引：
[公式6]
其中，k是交比的量子化的水平的数量，Hsize是散列表的大小，而crn是来自m个点的5个点的集合的交比值。
例如，可以利用通用个人计算机实现文档和/或图像存储方法和文档和/或图像检索方法。
根据本发明的另一方面，提供了一种使计算机进行用于从存储文档和/或图像的数据库检索与所拍摄的图像相对应的文档和/或图像的处理的程序，该处理包括：从所拍摄的图像提取特征点；基于各特征点的不变量值确定图像的特征量；以及对数据库中具有匹配所确定的特征量的文档和/或图像投票。
本发明还提供了一种使计算机执行以下步骤的文档和/或图像存储程序：输入文档和/或图像；向所输入的文档和/或图像分配ID；从所输入的文档和/或图像提取定义图像配置的特征点；以及对所提取的各特征点进行预定处理；预定处理包括以下步骤：(1)选择距离感兴趣的特征点p最近的n个特征点；以及(2)对从所选择的n个特征点所选择的m个特征点(m＜n)的所有可能的各集合进行预定处理；步骤(2)中的预定处理包括以下步骤：(a)确定从感兴趣的m个点的集合所选择的d个点(其中，d是不大于预定数量m的数量(例如，4或5))的所有可能的集合的特征量；(b)通过预定计算，基于所确定的特征量，确定散列表的索引；以及(c)将特征量与点ID和文档ID相关联存储在散列表中，其中，在步骤(a)中使用所确定的散列索引确定特征量，将点ID分配给特征点p，而将文档ID分配给从其提取所述特征点的文档和/或图像。
本发明还提供了一种用于检索使用上述存储程序所输入的文档和/或图像的文档和/或图像检索程序，该检索程序使计算机执行以下步骤：读取所拍摄的图像；从所读取的图像提取定义图像配置的特征点；以及对所提取的各特征点进行预定处理；预定处理包括以下步骤：(1)选择距离感兴趣的特征点p最近的n个特征点；以及(2)对从所选择的n个特征点所选择的m个特征点(m＜n)的所有可能的各集合进行预定处理；步骤(2)中的预定处理包括以下步骤：(a)确定从感兴趣的m个点的集合所选择的d个点(其中，d是不大于预定数量m的数量(例如，4或5))的所有可能的集合的特征量；(b)通过预定计算，基于所确定的特征量，确定散列表的索引；以及(c)基于所确定的散列索引从散列表获取预先输入的文档和/或图像的特征量，将在步骤(a)所确定的特征量和所获取的特征量进行比较，并且对具有匹配特征量的文档ID投票；以及在步骤(1)和(2)后，基于投票结果指定与所拍摄的图像相匹配的文档和/或图像的文档ID。
例如，可以在通用个人计算机上执行文档和/或图像存储程序和文档和/或图像检索程序。
根据本发明的另一方面，提供了一种存储设备，包括：输入部，输入文档和/或图像；特征点提取部，从所输入的文档和/或图像提取定义图像配置的特征点；特征点选择部，选择距离所提取的感兴趣的特征点p最近的n个特征点；以及特征量存储部，对从所选择的n个特征点所选择的m个特征点(m＜n)的所有可能的各集合进行预定处理；预定处理包括以下步骤：(a)确定从感兴趣的m个点的集合所选择的d个点(其中，d是不大于预定数量m的数量(例如，4或5))的所有可能的集合的特征量；(b)通过预定计算，基于所确定的特征量，确定散列表的索引；以及(c)将特征量与点ID和文档ID相关联存储在散列表中，其中，在步骤(a)中使用所确定的散列索引确定特征量，将点ID分配给特征点p，而将文档ID分配给从其提取特征点的文档和/或图像。
文档和/或图像存储设备可以使用通用个人计算机作为硬件。在这种情况下，输入部包括与用于传送文档和/或图像数据的外部装置进行通信的通信I/F、和用于对于存储数据的记录介质进行读写的驱动器(例如，DVD驱动器或CD驱动器)、或者读取图像的扫描器。通过使个人计算机的CPU执行所安装的应用程序，进行特征点提取部、特征点选择部和特征量存储部的功能。可选地，可以利用使用DSP和ASIC的专用硬件执行这些功能。
而且，本发明提供了一种存储由该存储设备所存储的文档和/或图像的文档和/或图像存储设备。
该文档和/或图像存储设备使用通用文件服务器作为硬件。
本发明还提供了一种用于检索存储在上述文档和/或图像存储设备中的文档和/或图像的文档和/或图像检索设备，该检索设备包括：读取部，读取所拍摄的图像；特征点提取部，从所读取的图像提取定义图像配置的特征点；特征点选择部，选择距离所提取的感兴趣的特征点p最近的n个特征点；以及投票部，对从所选择的n个特征点所选择的m个特征点(m＜n)的所有可能的各集合进行预定处理；(a)确定从感兴趣的m个点的集合所选择的d个点(其中，d是不大于预定数量m的数量(例如，4或5))的所有可能的集合的特征量；(b)通过预定计算，基于所确定的特征量，确定散列表的索引；以及(c)基于所确定的散列索引从散列表获取预先输入的文档和/或图像的特征量，将在步骤(a)所确定的特征量和所获取的特征量进行比较，并且对具有匹配特征量的文档ID投票；以及文档ID指定部，基于通过与各特征点相对应的投票所确定的投票结果，指定与所拍摄的图像相匹配的文档和/或图像的文档ID。
文档和/或图像检索设备可以使用通用个人计算机作为硬件。在这种情况下，读取部包括用于接收所拍摄的图像的通信I/F、以及用于从其中记录所拍摄的图像的SD卡(注册商标)或存储器棒(注册商标)等记录介质读取数据的I/F。通过使个人计算机的CPU执行所安装的应用程序，执行特征点提取部、特征点选择部和投票部的功能。可选地，可以利用使用DSP和ASIC的专用硬件进行这些功能。
文档和/或图像检索设备可以具有与文档和/或图像存储设备一样的功能。可选地，文档和/或图像检索设备还可以用作文档和/或图像存储设备。文档和/或图像检索设备还可以用作文档和/或图像存储设备以及文档和/或图像存储设备。
这里的术语“文档”是指数据库中积累的和从数据库检索的文本信息。文档的例子包括合同文书和宣传册等商务文档、科学技术论文、报纸和目录册。这里将术语“图像”定义为拍摄的、被积累在数据库中和从数据库中检索的非文本模式信息。图像的例子包括图形、图画、照片和海报。文档和/或图像属于图像的范畴。
这里的术语“连结成分”是指图像中相互连结的一组像素。更具体地，在存在与一个像素垂直和横向成连结关系的像素的情况下，相互连结这些像素以形成连结成分。这里的术语“特征点”是指表示图像的特征量的各个点，并且通过图像处理提取特征点。这里的术语“不变量”是表示对于几何变换是不变的参量的通称。几何变换的一个例子是旋转。即使旋转图像，图像中的对象的面积也不会改变。因此，对象的面积是对于旋转的示例不变量。而且，边长比是对于缩放的示例不变量。除旋转和缩放等相似变换以外，几何变换的例子包括投影变换和仿射变换。
这里的术语“投票”是指在信息处理领域中用于计算部分证据(partial evidences)的处理。更具体地，在该处理中，基于所获取的证据给予可选项的得分，并且选择可选项之中具有最高累积得分的那个。大体而言，证据具有不同的得分。
而且，这里的术语“询问”是表示用户的检索请求的数据。在本发明中，用户输入图像作为询问。也就是说，用户输入询问图像，以从数据库检索匹配询问图像的图像。
本发明的效果
根据本发明，从由数字照相机或扫描器等所捕获的图像提取特征点，并且基于特征点计算用于文档和/或图像检索的不变量值。因此，可以精确地检索想要的文档和/或图像。
附图说明
图1是用于解释根据本发明的交比的例子的图；
图2是用于解释根据本发明的交比的另一例子的图；
图3是示出用于本发明中的文档和/或图像检索系统的框图；
图4是示出根据本发明的输入的图像的例子的说明图；
图5是示出根据图4的二值图像的说明图；
图6是通过处理图5的图像所获得的图像的说明图；
图7是通过进一步处理图6的图像所获得的图像的说明图；
图8是用于解释根据本发明的特征点的图；
图9是用于解释根据本发明的特征点的图；
图10是示出根据本发明的特征点和交比之间的关系的说明图；
图11是用于解释根据本发明的特征点的图；
图12是用于解释根据本发明(实施例1)的存储处理的过程的图；
图13是用于解释根据本发明(实施例1)的散列表的结构的图；
图14是用于解释根据本发明(实施例1)的检索处理的过程的图；
图15是用于解释根据本发明的一次投票表的图；
图16是用于解释根据本发明的二次投票表的图；
图17是示出根据本发明的数据库中的图像的说明图；
图18是示出根据本发明的数据库中的另一图像的说明图；
图19是示出本发明实验1中所使用的示例拍摄的图像的说明图；
图20是示出本发明实验1中所使用的另一示例拍摄的图像的说明图；
图21是示出本发明实验1中所使用的另一示例拍摄的图像的说明图；
图22是示出本发明实验1中所使用的另一示例拍摄的图像的说明图；
图23是示出本发明实验2中所使用的示例拍摄的图像的说明图；
图24是示出本发明实验2中所使用的另一示例拍摄的图像的说明图；
图25是示出本发明实验2中所使用的另一示例拍摄的图像的说明图；
图26是示出本发明实验2中所使用的另一示例拍摄的图像的说明图；
图27是示出本发明实验2中所使用的另一示例拍摄的图像的说明图；
图28是用于解释根据本发明(实施例2)的存储处理的过程的图；
图29是用于解释根据本发明(实施例2)的散列表的结构的图；
图30是用于解释根据本发明(实施例2)的检索处理的过程的图；
图31是用于解释根据本发明(实施例2)在投票处理中如何使询问中的特征点p与所存储的文档中的点相互关联的图；
图32是示出本发明实验3中所使用的示例拍摄的图像的说明图；
图33是示出本发明实验3中确定的存储在数据库中的页数和检索精度之间的关系的曲线图；
图34是示出本发明实验3中所使用的示例询问的说明图；
图35是示出本发明实验4中所确定的存储在数据库中的页数和检索所需时间之间的关系的曲线图；
图36是用于解释根据本发明的提取特征点的示例过程的流程图；
图37是示出将文档中的注解包括进电子文档的系统的示例结构的说明图；
图38是用于解释如何使得拍摄的图像成正确方向的图；
图39是示出根据本发明的文档和/或图像存储设备的结构的框图；
图40是示出根据本发明的文档和/或图像检索设备的结构的框图；
图41是用于解释来自n个点(n＝8)的所有可能的m个点的组合(m＝7)的图(实施例2)；
图42是用于解释m个点(m＝7)的排列的图，其中，通过f个点的组合所计算的不变量值定义每一个点(实施例2)；
图43是用于解释不同于图28所示的存储过程的图(实施例2)；
图44是解释不同于图30所示的检索过程的图(实施例2)；
图45是示出存储在数据库中的示例文档的说明图(实施例2的实验)；
图46是示出示例询问的说明图(另一实验)；
图47是示出摄影角度和检索精度之间的关系的曲线图(另一实验)；
图48是示出处理时间和作为处理时间的表示的T(n，m，l)之间的关系的曲线图(另一实验)；
图49是示出量子化水平的数量和检索精度之间的关系、以及量子化水平的数量和处理时间之间的关系的曲线图(另一实验)；
图50是示出所存储的页数和检索精度之间的关系的曲线图(另一实验)；
图51是示出导致失败检索的示例询问的说明图(另一实验)；
图52是示出所存储的页数和检索速度之间的关系、以及所存储的页数和列表长度之间的关系的曲线图(另一实验)；
图53是示出存储在数据库中的示例文档的说明图(另一实验)；
图54是示出示例询问的说明图(另一实验)；
图55是示出具有不同参数的摄影角度和检索精度之间的关系的曲线图(另一实验)；
图56是示出n个点(n＝3)中的m个点(m＝2)的位置关系的说明图(另一实验)；
图57是用于解释通过使用本发明的方法对非文本图像进行的示例处理的图(d＝16，n＝28，m＝1)(另一实验)。
附图标记的说明
1：文档和/或图像存储设备
3：检索设备
11：输入部
15：特征点提取部
17：特征点选择部
19：特征点存储部
21：读取部
23：特征点提取部
25：特征点选择部
27：投票部
29：ID指定部
31：文档和/或图像数据库
图2是用于解释根据本发明的交比的另一例子的图；
图3是示出用于本发明中的文档和/或图像检索系统的框图；
图4是示出根据本发明的输入的图像的例子的说明图；
图5是示出根据图4的二值图像的说明图；
图6是通过处理图5的图像所获得的图像的说明图；
图7是通过进一步处理图6的图像所获得的图像的说明图；
图8是用于解释根据本发明的特征点的图；
图9是用于解释根据本发明的特征点的图；
图10是示出根据本发明的特征点和交比之间的关系的说明图；
图11是用于解释根据本发明的特征点的图；
图12是用于解释根据本发明(实施例1)的存储处理的过程的图；
图13是用于解释根据本发明(实施例1)的散列表的结构的图；
图14是用于解释根据本发明(实施例1)的检索处理的过程的图；
图15是用于解释根据本发明的一次投票表的图；
图16是用于解释根据本发明的二次投票表的图；
图17是示出根据本发明的数据库中的图像的说明图；
图18是示出根据本发明的数据库中的另一图像的说明图；
图19是示出本发明实验1中所使用的示例拍摄的图像的说明图；
图20是示出本发明实验1中所使用的另一示例拍摄的图像的说明图；
图21是示出本发明实验1中所使用的另一示例拍摄的图像的说明图；
图22是示出本发明实验1中所使用的另一示例拍摄的图像的说明图；
图23是示出本发明实验2中所使用的示例拍摄的图像的说明图；
图24是示出本发明实验2中所使用的另一示例拍摄的图像的说明图；
图25是示出本发明实验2中所使用的另一示例拍摄的图像的说明图；
图26是示出本发明实验2中所使用的另一示例拍摄的图像的说明图；
图27是示出本发明实验2中所使用的另一示例拍摄的图像的说明图；
图28是用于解释根据本发明(实施例2)的存储处理的过程的图；
图29是用于解释根据本发明(实施例2)的散列表的结构的图；
图30是用于解释根据本发明(实施例2)的检索处理的过程的图；
图31是用于解释根据本发明(实施例2)在投票处理中如何使询问中的特征点p与所存储的文档中的点相互关联的图；
图32是示出本发明实验3中所使用的示例拍摄的图像的说明图；
图33是示出本发明实验3中确定的存储在数据库中的页数和检索精度之间的关系的曲线图；
图34是示出本发明实验3中所使用的示例询问的说明图；
图35是示出本发明实验4中所确定的存储在数据库中的页数和检索所需时间之间的关系的曲线图；
图36是用于解释根据本发明的提取特征点的示例过程的流程图；
图37是示出将文档中的注解包括进电子文档的系统的示例结构的说明图；
图38是用于解释如何使得拍摄的图像成正确方向的图；
图39是示出根据本发明的文档和/或图像存储设备的结构的框图；
图40是示出根据本发明的文档和/或图像检索设备的结构的框图；
图41是用于解释来自n个点(n＝8)的所有可能的m个点的组合(m＝7)的图(实施例2)；
图42是用于解释m个点(m＝7)的排列的图，其中，通过f个点的组合所计算的不变量值定义每一个点(实施例2)；
图43是用于解释不同于图28所示的存储过程的图(实施例2)；
图44是解释不同于图30所示的检索过程的图(实施例2)；
图45是示出存储在数据库中的示例文档的说明图(实施例2的实验)；
图46是示出示例询问的说明图(另一实验)；
图47是示出摄影角度和检索精度之间的关系的曲线图(另一实验)；
图48是示出处理时间和作为处理时间的表示的T(n，m，l)之间的关系的曲线图(另一实验)；
图49是示出量子化水平的数量和检索精度之间的关系、以及量子化水平的数量和处理时间之间的关系的曲线图(另一实验)；
图50是示出所存储的页数和检索精度之间的关系的曲线图(另一实验)；
图51是示出导致失败检索的示例询问的说明图(另一实验)；
图52是示出所存储的页数和检索速度之间的关系、以及所存储的页数和列表长度之间的关系的曲线图(另一实验)；
图53是示出存储在数据库中的示例文档的说明图(另一实验)；
图54是示出示例询问的说明图(另一实验)；
图55是示出具有不同参数的摄影角度和检索精度之间的关系的曲线图(另一实验)；
图56是示出n个点(n＝3)中的m个点(m＝2)的位置关系的说明图(另一实验)；
图57是用于解释通过使用本发明的方法对非文本图像进行的示例处理的图(d＝16，n＝28，m＝1)(另一实验)。
附图标记的说明
1：文档和/或图像存储设备
3：检索设备
11：输入部
15：特征点提取部
17：特征点选择部
19：特征点存储部
21：读取部
23：特征点提取部
25：特征点选择部
27：投票部
29：ID指定部
31：文档和/或图像数据库
具体实施方式
图3示出根据本发明的文档和/或图像检索系统的结构。通过特征点的提取将文档和/或图像转换成一组点。然后，将这一组点输入给用于存储的存储处理、或者输入给用于检索的检索处理。在存储处理中，基于特征点计算交比，并将其转换成索引，基于索引，将文档和/或图像存储在散列表中。另一方面，在检索处理中，以相同方式基于特征点计算索引，并且通过投票检索想要的文档和/或图像。
散列(hash)允许高速访问数据库中的数据。为将被存储在散列表中的数据定义关键字(key)，并且将数据存储在基于关键字所计算的位置(地址)处。更具体地，准备散列表，将数据列表的指针存储在散列表的各元素中，其中，散列表是通过这些关键字索引的数组的表。根据关键字计算散列表的索引，并参考散列表将数据存储在通过基于所计算的索引所确定的指针所定义的地址中。用于将关键字转换成散列表的索引的函数是散列函数。当检索所存储的数据时，根据散列函数，基于关键字确定散列表的索引，并且对于数据的检索，使用存储在基于所确定的索引所参考的散列表的元素中的指针。
以下说明该处理的步骤。
特征点的提取
对于特征点的提取重要的是特征点的再现性。也就是说，甚至在几何变换、噪声和较低分辨率的影响下，也应该完全一致地获得特征点。使用英文文档中的各个单词的重心(centroid)作为特征点以满足该要求。这是因为，在英文文档中的单词之间存在空格，这使得可以相对容易地分离单词。
利用例子简要说明特征点提取的过程。通过自适应二值化将输入的图像(图4)转换成二值图像(图5)。接着，以下面的方式从二值图像检测单词区域。首先，利用高斯滤波器平滑化(模糊)二值图像。此时，基于对字符大小的估计(连结成分的面积的模式值(mode value)的平方根)自适应地确定高斯滤波器的参数。平滑化后的图像再次经过自适应二值化以提供二值图像(图6)。该图像中的连结成分被当作为单词区域，并且将各单词区域的重心定义为特征点。从图6所示的图像获得图7所示的特征点。
接着，参考图36所示的流程图详细说明该过程。根据图36(a)的流程图处理输入的图像，以提供特征点的集合。
第一步骤是大小校正步骤。在其中，输入的图像是装配到移动电话的照相机所拍摄的图像，该图像的大小明显不同于普通图像大小。因此，对于大小校正，放大输入的图像。
接着，进行通过下面的公式所定义的自适应二值化步骤。
[公式7]
[公式8]
其中，I表示输入的图像(灰度图像)，F表示输出的图像(二值图像)，T表示通过上面的公式(2)自适应定义的阈值，b是用于确定阈值的所参考的块(block)的大小，而s是用于控制阈值的参数。公式(2)表示：使用通过从块的平均密度减去预定值s所获得的值作为阈值。
图36(b)示出预处理步骤。根据系统模式，即，用于将文档和/或图像存储在数据库中的数据库结构模式或用于检索与所拍摄的图像相对应的文档和/或图像的检索模式，以不同的方式进行预处理步骤。如果在系统模式不是数据库结构模式时，以普通检索模式进行检索操作，而不使用移动电话照相机，则消除(remove)各自具有较小面积的连结成分。另一方面，在数据库结构模式中，为了估计字符大小，确定连结成分的面积的模式值的平方根。为了确定用于平滑化的参数c，字符大小乘以HashScale。在平滑化中，根据下面的公式确定高斯滤波器的标准差σ：
[公式9]
σ＝(c/2-1)×0.3+0.8
然后，通过由该公式所定义的高斯滤波器平滑化图像，并通过自适应二值化将图像再次转换成二值图像。从而预处理图像。
参考图36(c)的流程图，预处理步骤随后的步骤是平滑化参数估计步骤。以与上述参数估计相同的方式进行该步骤。同样以与上述相同的方式进行下一平滑化步骤。在平滑化步骤后，再次通过自适应二值化将图像转换成二值图像。最后，从通过该处理所获得的二值图像提取连结成分，并将连结成分的重心确定为特征点。
用于索引的特征量的计算
用于存储和检索的关键字是如何基于交比计算散列表的索引。在详细说明存储和检索前，说明用于确定索引的特征量的计算。
基于图像中的特征点所计算的交比的值是连续值。为了用于确定索引，将交比值离散化成k个水平。为了吸收由于几何变换和摄影条件的改变而产生的误差，数量k适宜相对小。如果数值k过小，则降低了辨别力。因此，应该适当选择数量k。这里，所利用例子采用基于预先实验的结果所确定的k＝9，但是这不是限制性的。确定各特征点周围的局部区域的特征量以使得可以基于图像的一部分检索。
为围绕特征点的局部区域所定义的特征量的可能例子如下：
(1)距离特征点最近的5个点的交比；
(2)基于从距离特征点最近的n个点所选择的5个点的集合的交比；
(3)从距离特征点最近的n个点所选择的m个点的排列和基于从m个点所选择的5个点的集合的交比。
在本发明中，采用最复杂的特征量(3)。从最简单的一个开始说明这三个特征量。而且，将说明本发明中所采用的特征量和为什么使用最复杂的特征量的原因。
5个最近点的交比
基于围绕特征点的局部区域的交比定义特征量的容易想到的方法是计算距离特征点最近的5个点的交比。例如，如图8所示，选择距离特征点p最近的5个点1～5，并计算这5个点的交比，以采用其作为点p的特征量。
然而，在以图8和9所示的不同角度所拍摄的文档和/或图像中，最近的5个点可能变化。因此，该方法的问题在于从同一文档所获得的文档和/或图像不能提供同一特征点的相同特征量。
基于从n个最近点所选择的5个点的集合的交比
另一想到的方法是提取从n个最近点所选择的5个点的所有可能的集合，并基于各5个点的集合计算交比。
图8和9所示的文档和/或图像在5个最近点上是不一致的，但是在8个最近点中的7个点上是一致的。因此，n个最近点包括基本保持不变的m(＜n)个点。因此，在计算从n个点所选择的5个点的所有可能的集合的交比的情况下，推测在基于从共同的m个点所选择的5个点的集合所计算的交比是一致的。因此，采用基于从n个点所选择的5个点的所有可能的集合所计算的交比作为特征量。如果在比较步骤中，与基于来自共同的m个点的5个点的集合所计算的交比中的任何一个一致的交比的数量不小于预定数量，则认为文档和/或图像中感兴趣的特征点是相同的。
然而，实际检索中该特征量的使用经常导致不正确的检索结果。参考图10，例如，为了简单，这里假定：基于从距离各特征点最近的n个点所选择的点的集合，计算四个交比。还假定：为特征点A所计算的交比集合为(0.2，1.3，0.3，1.8)，而为特征点B所计算的交比集合为(1.2，1.6，0.1，0.2)。如果以步长0.5离散化这些交比，则特征点A和特征点B的离散化后的交比的集合分别为(0，2，0，3)和(2，3，0，0)。仅考虑交比的值，值0、2和3共同出现在特征点A和B的交比的集合中，因此判断特征点A和B是相同的。在以该方式对实际图像确定交比的情况下，这样的情况经常发生，结果导致失败检索。
从n个最近点所选择的m个点的排列和基于从m个点所选择的5个点的集合的交比
上述问题的解决方案是同时考虑交比的顺序。也就是说，在图10所示的例子中，交比组(0，2，0，3)区别于交比组(2，3，0，0)。
参考图11，更具体地，假定围绕从同一文档所获得的不同图像中的相应的点分别定义一组8个点ABCDEFGH和一组8个点IJKLMNOP。这两个8个点的组仅在一个点E、L是不一致的，而在其余7个点是一致的。因此，在从每一个8个点的组中的8个点选择7个点的所有可能的集合的情况下，一组点ABCDFGH与一组点IJKMNOP是相同的。因此，在通过在每一相同的7个点的集合中从共同的7个点以预定顺序选择5个点来定义有序的5个点的所有可能的集合的情况下，有序的5个点的集合是一致的。也就是说，在基于来自每一8个点的组中的共同的7个点的所有可能的有序的5个点的集合来计算交比的情况下，即，计算一组点ABCDF和一组点IJKMN的交比和一组点ABCDG和一组点IJKMO的交比等的情况下，作为结果的7个点的组的交比序列在交比的顺序和各交比的值上是相同的。很少有基于不同的7个点的集合所确定的交比序列在交比顺序和交比值上是相同的。因此，通过采用交比序列作为特征量可以解决上述问题。
概括地说，首先提取距离特定点最近的n个点，然后定义从n个点所选择的m个点的所有可能的集合。而且，定义从m个点按照预定顺序所选择的有序的5个点的所有可能的集合，并且顺序计算各有序的5个点的集合的交比。如果在交比序列中发现至少1个交比的值和位置一致，则判断这些交比序列具有相同特征量。
实施例1
存储
基于上述的准备处理说明存储处理。当将文档和/或图像存储在数据库中时，从文档和/或图像提取特征点，而且计算各特征点的特征量并将其与文档和/或图像相关联存储。在获取所拍摄的图像的数据时，计算图像数据的特征量，并且检查存储在数据库中的各文档和/或图像的特征量与所计算的特征量一致，从而从存储在数据库中的文档和/或图像检索与所拍摄的图像的数据相对应的文档和/或图像。
图12示出存储处理的示例过程。在该处理中，文档ID是分配给各文档的标识号。点ID是分配给每一文档中的各点的标识号，anCm模式ID是分配给从n个点所选择的m个点的各组的且取值0～nCm-1的标识号。相似地，amC5模式ID是分配给从m个点所选择的5个点的各组的且取值0～mC5-1的标识号。
图13示出散列表的结构，将文档和/或图像存储在散列表中。这里将术语“文档图像”定义为文档的图像。在存储处理中，重复处理序列，在其中，在行5～8确定散列表的索引，并且在行9使用索引将上述的ID存储在散列表中。
根据图12所示的过程进一步说明存储处理。在行5～7，基于一组5个的点计算5个交比。使用循环移位起始点所获得的5个点ABCDE的循环排列的ABCDE、BCDEA、CDEAB、DEABC和EABCD，获得5个交比。
在行8，根据下面的散列函数计算散列表的索引：
[公式10]
其中，crn(n＝0～4)是5个交比的离散值，Vmax是离散交比值的最大值，而pat是mC5模式ID。
在行9，使用索引将列表(文档ID、点ID、nCm模式ID)存储在散列表中。当发生冲突时，如图13所示，以列表形式另外存储数据。不仅将文档ID而且还将点ID和nCm模式ID存储在散列表中。这是因为，当在检索处理中比较特征量时，针对每一列表(文档ID、点ID和nCm模式ID)确定交比序列中的匹配的交比的数量。
检索
接着说明检索处理。图14示出检索处理的示例过程。在本发明中，参考图15所示的一次投票表，检查是否在交比序列中发现了至少预定数量l个交比匹配。如果发现了匹配，在图16所示的二次投票表中对相应的文档进行投票以提供检索结果。为了适当确定数量l，通过使用一些可能的数量l(l＜nCm)预先进行实验，并采用提供正确检索结果与错误检索结果的最高比的数量作为数量l。
以与存储处理相同的方式说明检索处理。在图14所示的检索处理中的行6～9，以与存储处理相同的方式确定散列表的索引，并在行10从散列表读取图13所示的列表。对于列表中的每一元素，对于一次投票表的相应单元格(cell)进行投票。
在重复这些步骤完成对来自m个点的所有5个点的集合的投票后，检查一次投票表的单元格。如果检测到了具有不少于1的投票数量的单元格，则对二次投票表中的相应的文档ID投票。
最后，最终确定二次投票表中具有最大投票数量的文档作为检索结果。
在行4，通过在点集Pm中移位起始点形成点集Pm的点的所有可能的循环排列{P’m}，并且以上述方式处理循环排列{P’m}。该步骤对应于用于从点集Pm形成m个循环排列{P’m}的处理。例如，从ABCDEFG，形成循环排列BCDEFGA和CDEFGAB等。该步骤是处理旋转图像所需要的。
实施例2-更高速的处理
将说明根据本发明的一种方法，在其中，与实施例1相比，减少了存储或检索所需的处理时间。
在说明改进的存储和检索方法前，给出对于特征量的计算的补充说明。
特征量的计算
1.特征量需要满足的条件
这里将特征量定义为表示文档图像中的各特征点的值。计算用于检索的询问的和将存储的文档的特征点的特征量，并且通过将询问的特征量与所存储的文档的每一个的特征量进行比较，判断询问是否匹配所存储的文档中的任何一个。
基于检索的准确度和检索所需的计算复杂度，估计特征量。认为使得可以准确且高速检索与询问相对应的所存储的文档的特征量是良好的。如下定义了为了准确度特征量需要满足的两个条件。
第一条件是：即使在各种类型的变形的影响下，为同一文档的相同点所计算的特征量应该保持不变。如果为询问和相应的所存储的文档计算不同的特征量，则在检索处理中不可能发现匹配的特征点。将该条件称为“特征量的稳定性”。
第二条件是：为不同点所计算的特征量应该不同。如果为不同的文档计算相同的特征量，则在检索处理中不仅检测匹配的特征点，而且还检测不相关的特征点。将这一条件称为“特征量的辨别力”。
而且，第三条件是：特征量的计算需要相对小的计算复杂度。当然难以使用需要巨大计算量的特征量，即使该特征量具有更高的稳定性和更高的辨别力。因此，除上述的针对准确度的两个条件以外，特征量应该满足为了较小计算复杂度的条件。
为了更高速和更高准确度的文档图像检索，特征量应该满足这三个条件。
2.特征量的稳定性
对于上述三个条件，首先说明特征量的稳定性。在如上所述的本发明的方法中，基于距离各特征点最近的点的不变量值，计算特征量。为了稳定提供特征量，即使由于透视变形而最近的点的坐标发生变化，计算特征量所使用的最近的点也应该保持不变。如图8和9所示，在透视变形的影响下，最近的点发生改变。因此，如果使用基于距离特征点p最近的f个点所计算的不变量值作为特征量，则对于同一特征点p不可能提供相同的特征量。
因此，在本发明中，定义从更大范围中的距离特征点最近的点所选择的多个点的集合，并且基于多个点的各个集合计算多个特征量。这是基于假定：即使在透视变形的影响下，图像中共同存在更大范围中的n个最近点(图8和9中的8个点)中m个点(图8和9中的7个点)。假定在图像中共同存在n个最近点中的m个点，则如图41所示，定义来自n个点的所有可能的m个点的集合Pm(0)、Pm(1)、...、Pm(nCm-1)，并且计算各点集的特征量。在这种情况下，为各特征点所计算的特征量至少包括一个共同的特征量。
3.特征量的辨别力
接着说明特征量的辨别力。在本发明的方法中，通过增加用于计算单个特征量的特征点的数量m提高特征量的辨别力。使用基于如图42所示的从m个点所选择的f个点的所有可能的集合所计算的不变量值序列cr(0)、cr(1)、...、cr(mCf-1)作为m个点的排列的表示方法，其中，cr(i)是等于具有相同值的cri的交比。随着数量m的增大，将计算的不变量值的数量增大。因此，降低了偶然重合的可能性。然而，如果数量m过大，则特征量的稳定性降低。这是因为，对于特征量的匹配，应该在所有不变量值中发现匹配，并且数量m的增大使得不变量值的数量mCf增大，从而增大了由于误差的影响而计算出不同的不变量值的可能性。
4.计算复杂度和存储容量
如上所述，数量n的增大使得可以计算更大范围的多个特征量，从而提高了特征量的稳定性。而且，数量m的增大使得可以基于更大数量的点计算各特征量，从而提高了特征量的辨别力。然而，如果过分增大这些参数的值，则会出现与计算复杂度相关的问题。也就是说，如果数量m和n过大，则不变量值的计算的计算复杂度增大。因此，存储和检索所需的处理时间相应增大。而且，为了存储所计算的特征量，存储器需要更大的存储容量。
5.不变量值的量子化水平
稳定性和辨别力不仅受参数n、m的影响，而且还受不变量值的量子化的水平的数量k的影响。如果数量k较大(精细离散化每一不变量值)，则由于误差的影响增大了以不同水平离散化基于f个点的相同集合所计算的不变量值的可能性，从而降低了稳定性。如果数量k较小(粗略离散化每一不变量值)，则增大了以相同水平离散化基于f个点的不同集合所计算的不变量值的可能性，从而降低了辨别力。因此，应该适当设置参数n、m和k以确保利用较小的存储容量、以更高的准确度更高速地进行检索处理。
存储
参考图28说明不同于实施例1的存储处理的另一示例过程。
在存储处理中，定义从将存储的文档中的距离各特征点最近的n个点所选择的m个点的所有可能的集合。然后，基于根据各个m个点的集合所计算的交比，确定索引，并将交比存储在图29所示的散列表中。以下根据图28所示的过程说明存储处理。在行1，从特征点的集合提取一个特征点p。在行2，顺时针顺序提取距离特征点p最近的n个点以提供点集Pn。在行3，从点集Pn提取m个点以提供点集Pm。在行5，计算从点集Pm所选择的5个点的所有可能的集合的交比值，并离散化交比值以提供交比cri。由于来自m个点的5个点的集合的数量是mC5，因而“i”取值0～mC5-1。
在行7，基于如此提供的交比cri，根据散列函数确定散列表的索引Hindex。在行8，基于散列索引Hindex将文档ID(将存储的文档的标识号)、点ID(点的标识号)和交比cri(i＝0，...，mC5-1)存储在散列表中。散列函数如下：
[公式11]
其中，k是交比的量子化水平的数量，Hsize是散列表的大小。在存储处理中发生冲突的情况下，以图29所示的列表添加数据。
图43示出存储处理的另一过程。给出对图43的说明。在存储处理中，定义从将存储的文档中的距离各特征点最近的n个点所选择的m个点的所有可能的集合。然后，基于根据各个m个点的集合所计算的不变量值确定索引，并将不变量值存储在图29所示的散列表中。
在图43的行1，从特征点的集合提取一个特征点p。在行2，提取距离特征点p最近的n个点以提供点集Pn。在行3，从点集Pn提取m个点以提供点集Pm。在行4，围绕点p顺时针排序点集Pm中的m个点以提供特征点序列Lm。在行5，通过从点序列Lm中的点按照预定顺序选择f个点，提供所有可能的特征点序列Lf，并按照词典顺序排列特征点序列Lf。
当m＝7且f＝5时，例如，提供特征点序列((p0，p1，p2，p3，p4)，(p0，p1，p2，p3，p5)，...，(p2，p3，p4，p5，p6))作为(Lf(0)，...，Lf(7C5-1))。在行7，以上述不变量计算公式将各特征点序列Lf(i)中的点取代为A、B、C...，从而计算和离散化不变量值以提供cr(i)。在行9，根据下面的散列函数(3)确定散列表的索引Hindex。在行10，基于索引Hindex将文档ID(将存储的文档标识号)、点ID(点的标识号)和不变量值cr(i)(i＝0，1，..，mCf-1)存储在散列表中。该实施例中所使用的散列函数如下：
[公式12]
其中，k是不变量值的量子化的水平的数量，而Hsize是散列表的大小。在存储处理中发生冲突的情况下，以图29所示的列表的形式添加数据。为了文档的存储对所有特征点p进行上述处理。
检索
接着说明检索处理。图30示出不同于实施例1的检索处理的示例过程。以与存储处理相同的方式说明检索处理。在该过程的行5～8，，以与存储处理中相同的方式确定散列表的索引。在行9，从散列表读取图29所示的列表。参考该列表中的元素检查询问的交比是否完全匹配所存储的交比，并且，如果发现匹配，则对文档ID的线性阵列的投票表的相应单元格投票。
这里的投票对应于用于将询问中的特征点p与所存储的文档中的特征点相关联的处理。如果特征点p与所存储的文档中的特征点独立相关联，则将询问中的一个特征点错误地与多个点相关联，从而提供了图31所示的错误对应关系A-A’，A-A”和B-A’。如果在投票的数量中包括基于错误对应关系的投票，则将相对地降低基于正确对应关系的投票的等级(rating)，从而导致失败检索。在该实施例中，记录询问中的点和所存储的文档中的点之间的对应关系，并对所记录的对应关系不投票。因此，抑制了基于错误对应关系的投票。
对于每一所存储的文档中的所有点进行该处理，并且将具有投票表中最大数量的投票的文档最终确定为检索结果。
在行4，通过移位点集Pm中的起始点定义所有可能的点集{P’m}，并且处理点集{P’m}。该步骤对应于用于定义点集Pm中的点ABCDEFG的m个循环排列{P’m}的处理，即，BCDEFGA和CDEFGAB等。该步骤是处理旋转图像所需要的。
可以根据图44所示的过程进行该处理。给出对于图44的说明。在行1～3，以与存储处理中相同的方式定义p、Pn和Pm。在行4和5，与存储处理中不同，通过将起始点p0移位至点集Pm中的各点，定义特征点序列{Lm}。由于在图43中的存储算法中，在行4仅存储由Pm形成序列{Lm}中的一个，而不考虑图像的旋转，因而需要这样。甚至在透视变形的情况下，围绕点p的特征点的顺时针序列是恒定的，虽然起始点是可移位的。也就是说，在考虑Lm的循环排列的情况下，存储处理中所使用的序列必然是循环排列中的一个。在行6～10，以与存储处理中相同的方式确定散列表的索引。在行11，从散列表读取如图29所示的列表。在行12～14，基于该列表的元素对所存储的文档ID中的相应的文档ID投票。这里，以下面的方式抑制了基于错误对应关系的投票。
使用下面的三个条件：(1)获得不变量的相同序列；(2)询问中的一个点不对应于所存储的文档中的多个点；和(3)所存储的文档中的一个点不对应于询问中的多个点。对于询问图像中的所有点，基于这些条件进行上述处理，以确定各个所存储的文档的投票数量。然而，如此所确定的投票的数量仍包括基于错误对应关系的投票。错误投票的数量一般与所存储的文档中所包含的特征点的数量成比例。因此，具有较大数量特征点的所存储的文档获得不合理地大量投票。为了校正由于错误投票而引起的错误，通过下面的公式(4)定义文档di的得分S(di)：
[公式13]
S(di)＝V(di)-cN(di) ...(4)
其中，V(di)是di的投票的数量，N(di)是文档di中所包含的特征点的数量；而c是特征点的数量和通过预先实验所确定的错误投票的数量之间的比例常数。最终将具有最高得分的文档确定为检索结果。
实施例1的示例实验
实验的概述
为了验证根据实施例1的方法的有效性，基于由普通数字照相机所拍摄的文档图像和由移动电话数字照相机所拍摄的文档图像，进行检索处理。使用具有EF-S 18-55mm USM镜头的CANON(注册商标)数字照相机EOS Kiss Digital(630万像素)作为普通数字照相机，而将装配给移动电话KYOCERA TK31的数字照相机(18万像素)用作移动电话数字照相机。
在文档图像数据库中，存储有通过转换单栏或双栏的英文论文的PDF文件所准备的50个文档图像。图17和18示出数据库中的文档图像的例子。在具有Pentium 4(注册商标)CPU(2.4GHz)和存储器(768MB)的计算机上进行实验。
实验1：使用普通数字照相机的实验
说明使用普通数字照相机的实验的结果。设置上述参数如下：n＝8，m＝7，k＝9，而l＝10。如上所述，k是为各特征点所计算的交比的值的离散化的水平的数量，而l是离散后的交比的数量，离散化的交比适于基于在一次投票中的投票数量判断各特征点的匹配，并且使用离散后的交比作为用于判断是否基于散列表的元素进行二次投票的投票数量的阈值。使用利用如图19～22所示的四个不同摄影范围拍摄通过拍摄10个不同的文档页所准备的总共40个图像，作为询问。摄影范围包括覆盖整个文档页的摄影范围A、覆盖整个文本区域的摄影范围B、覆盖一半文本区域的摄影范围C、以及覆盖四分之一文本区域的摄影范围D。斜拍摄文档页。如果正确的文档图像具有最大数量的投票，就认为检索是正确的。测量平均正确检索率和平均处理时间。
表1示出实验结果。不管摄影范围，从所有输入的图像获得正确的检索结果。随着摄影范围的缩小，处理时间缩短。这是因为减少了处理的特征点的数量。
表1
摄影范围 A B C D 正确检索率(％) 100 100 100 100 处理时间(sec) 231.6 173.1 157.6 118.1
实验2：使用移动电话数字照相机的实验
使用由移动电话数字照相机所拍摄的图23～27的文档图像作为用于检索的询问。图24～26的文档图像导致成功检索，而图23和27的文档图像导致失败检索。利用图23的文档图像的失败检索的原因是：由于过低的分辨率，因而不能相互分开输入的图像中的单词，使得不可能正确提取特征点。利用图27的文档图像的失败检索的原因是：图像的摄影范围过于小，使得不可能正确定义最近的点。即使使用具有更低分辨率的移动电话数字照相机，通过拍摄范围的必要调整，检索也是可以。
上述的实验示出通过以下的文档图像检索方法可以高精度地检索文档图像：使用由数字照相机所拍摄的文档图像作为询问，并采用使用交比和散列表的投票处理。还可以发现：虽然需要调整摄影范围，但是对于检索甚至可以使用由具有更低分辨率的移动电话数字照相机所拍摄的文档图像。
实施例2的示例实验
实验的概述
为了验证根据实施例2的有效性，确定检索精度和数据库大小之间的关系和数据库大小和检索速度之间的关系。利用具有EF-S 18-55mm USM镜头的CANON数字照相机EOS KissDigital(630万像素)通过如图32所示斜拍摄文档准备询问。询问的数量是50。另一方面，将通过转换各种英文论文的PDF文件所准备的10000个文档图像存储在文档图像数据库中。图17和18示出数据库中的文档图像的例子。在实验中，设置处理参数如下：n＝8，m＝7，k＝10，Hsize＝1.28×108。在实验中使用具有AMDOpteron(注册商标)CPU(1.8GHz)和存储器(4GB)的计算机。
实验3：检索精度
确定存储在数据库中的页数和检索精度之间的关系。图33示出实验的结果，该结果表示随着页数的增加精度降低。
在数据库中的页数为10000的情况下，利用50个询问中的49个询问所检索的正确文档图像每一均具有最大的投票数量。因此，检索精度为98％。利用其余询问所检索的正确文档图像具有第五最大投票数据。平均检索时间是137.7ms。图34示出导致失败检索的询问的图像，在失败检索中，正确文档图像不具有最大的投票数量。与该询问图像一样，几乎被表/图区域占据的且包括较小文本区域的询问图像导致失败检索。推测是因为：如果询问图像具有较小数量的特征点，那么将检索的正确文档图像不能获得足够数量的投票。
实验4：检索时间
接着确定所存储的页数如何影响检索时间。图35示出该结果，该结果表示：随着所存储的文档数量的增加，检索时间逐渐增加。图35还示出散列表中的平均列表长度。这里定义平均列表长度为散列表中所包含的非零列表长度的平均值。随着所存储的页数的增加而平均列表长度增大这一情况表示冲突的次数增加。推测其是检索时间增加的原因。
其它示例实验
A.利用交比的检索性能
为了精确估计利用交比和检索的文档图像索引的性能，通过不同地设置参数进行实验。
在实验中，使用通过转换如图45所示的英文论文的PDF文件所准备的文档图像的数据库和通过利用数字照相机拍摄打印后的文档所准备的询问。使用分别包含10个文档图像、100个文档图像、1000个文档图像和10000个文档图像的数据库A、B、C和D作为文档图像数据库。数据库C是数据库D所包含的一部分，而数据库B是是数据库C所包含的一部分。而且，数据库A是数据库B所包含的一部分。使用CVPR、ICPR和ICCV等具有相似版面的国际会议论文集的PDF文件作为PDF文件。
使用通过分别以约60、45和30度拍摄根据数据库B所打印的文档所准备的询问的图像1、2和3，作为询问。询问1、2、3的图像数量均为100个。图46示出询问的例子。使用具有EF-S18-55mm USM镜头的CANON EOS Kiss Digital(630万像素)准备询问图像。实验中所使用的散列表的大小为Hsize＝227-1。使用具有AMD Opteron CPU(1.8GHz)和存储器(6GB)的计算机。
实验1：参数n、m和性能之间的关系
本发明提供的性能根据确定计算特征量使用的特征点的集合的数量的参数n、m改变。通过不同地设置参数n、m组合，确定检索精度、处理时间和所需存储容量。在实验中，使用数据库B和询问1～3。表2～4示出基于不同摄影角度的实验的结果。
表2(摄影角度60度)
n m nCm mC5 k 精度(％) 处理时间 列表数量 l 6 6 1 6 30 90 18.7 6.7×104 1.38 7 6 7 6 40 79 53.4 4.7×105 1.82 7 1 21 5 100 28.3 6.7×104 1.15 8 6 28 6 150 53 133.2 1.9×106 1.11 7 8 21 12 100 122.9 5.3×105 1.02 8 1 56 5 99 53.3 6.7×104 1.00 9 6 84 6 240 10 372.0 5.6×106 1.11 7 36 21 24 100 502.2 2.4×106 1.02 8 9 56 8 99 366.0 6.0×105 1.00 9 1 126 5 74 111.4 6.7×104 1.00 10 6 210 6 120 5 1408.3 1.4×107 1.86 7 120 21 21 100 1662.1 8.0×106 1.05 8 45 56 6 100 1784.7 3.0×106 1.02 9 10 126 2 100 994.9 6.7×105 1.01 10 1 252 2 98 229.0 6.7×104 1.00
表3(摄影角度45度)
n m nCm mC5 k 精度(％) 处理时间 列表数量 l 6 6 1 6 30 28 18.8 6.7×104 1.38 7 6 7 6 40 12 53.8 4.7×105 1.82 7 1 21 8 80 27.9 6.7×104 1.03 8 6 28 6 180 8 131.7 1.9×106 1.08 7 8 21 14 99 123.8 5.3×105 1.01 8 1 56 5 70 53.7 6.7×104 1.00 9 6 84 6 90 6 542.1 5.6×106 1.83 7 36 21 24 100 506.4 2.4×106 1.02 8 9 56 5 99 368.4 6.0×105 1.00 9 1 126 5 22 112.4 6.7×104 1.00 10 6 210 6 150 7 1215.0 1.4×107 1.58 7 120 21 21 100 1673.8 8.0×106 1.05 8 45 56 6 100 1803.9 3.0×106 1.02 9 10 126 2 100 997.7 6.7×105 1.01 10 1 252 2 70 230.8 6.7×104 1.00
表4(摄影角度30度)
n m nCm mC5 k 精度(％) 处理时间 列表数量 l 6 6 1 6 40 5 20.6 6.7×104 1.18 7 6 7 6 40 3 60.3 4.7×105 1.82 7 1 21 8 7 31.3 6.7×104 1.03 8 6 28 6 180 4 147.7 1.9×106 1.08 7 8 21 15 12 138.1 5.3×105 1.01 8 1 56 9 6 60.1 6.7×104 1.00 9 6 84 6 90 5 611.0 5.6×106 1.83 7 36 21 22 25 566.6 2.4×106 1.02 8 9 56 5 20 413.3 6.0×105 1.01 9 1 126 5 1 125.6 6.7×104 1.00 10 6 210 6 210 4 1183.4 1.4×107 1.31 7 120 21 24 39 1885.0 8.0×106 1.04 8 45 56 6 45 2019.4 3.0×106 1.02 9 10 126 3 18 1115.3 6.7×105 1.00 10 1 252 2 4 258.1 6.7×104 1.00
这里将精度定义为每一匹配询问且具有最大投票数量的文档图像的数量的比率，而这里将处理时间定义为除特征点提取处理以外的检索处理所需的时间。将列表数量定义为存储在散列表中的列表的总数(每一列表包括一组文档ID、点ID和交比序列cr(0，...，cr(mC5-1)，如图29所示)，并且l是散列表中的非零列表长度的平均值。在表2～4中，示出了对n和m的各组合通过使用提供最高精度的k的值所获得的每一结果。作为参考，还示出了n和m的组合的数量nCm和mC5。首先，检查精度。
通常，随着摄影角度的缩小，精度降低。推测是因为更大的透视变形导致最近点的更大变化，因而使得不可能确保特征量的稳定性。然而，如图47所示，如果n和m之间的差更大，则抑制了精度的降低。这是因为差n-m等于可允许的错误的特征点的数量。接着，检查处理时间。考虑到图44所示的检索算法的结构，假定由计算特征量所需的时间、列表处理所需的时间和迭代次数确定处理时间。计算特征量所需的时间通常与特征量的交比mC5的数量成比例，而列表处理所需的时间与平均列表长度l成比例。迭代次数为nCm×m。因此，这里通过下面的公式(5)，基于参数n、m和平均列表长度l将处理时间定义为T(n，m，l)：
[公式14]
T(n，m，l)＝nCm·m·(mC5+αl) ...(5)
其中，α是对于特征量计算时间的列表处理时间的权重。
图48示出在α＝3时所获得的T(n，m，l)与处理时间的曲线图。从图48可以看出，T(n，m，l)通常与处理时间成比例。因此，推测处理时间受n、m、l的影响，如公式(5)所示。最后，检查所需的存储容量。在表2～4中，存储在散列表中的列表数量与nCm成比例。这是因为针对每一点存储特征量。如上所述，必须增大值n-m以确保更高的稳定性，但是这相应地增大了所需的存储容量。
实验2：量子化水平的数量和性能之间的关系
本发明的方法所提供的性能根据量子化水平的数量k而改变。通过使用数据库B和询问1，并将参数设置成n＝8和m＝7，来确定k和精度之间的关系、以及k和处理时间之间的关系。图49示出该结果。首先，检查精度。在k较小时精度较低，而随着k的增大精度急剧升高。推测这是因为当k较小时特征量的辨别力较低，因而不能确保匹配文档和非匹配文档之间的适当辨别。当k过大时，精度急剧下降。推测这是因为特征量的稳定性降低。接着，检查处理时间。处理时间首先随着k的增大而急剧减少，然后通常保持恒定。推测这是因为：在k较小时特征量的辨别力较低，并且在散列表中频繁发生冲突，从而导致检索处理中散列访问时间的增加。因此，为了确保更高速和更高精度的检索，应当适当设置数量k。
实验3：所存储的页数和检索精度之间的关系
通过使用数据库A～D在10～10000之间可变地设置所存储的页数，确定所存储的页数和检索精度之间的关系。使用询问l和2作为询问。对于这两个询问将参数设置成n＝8和m＝7。此时，如表2和3所示设置数量k。图50示出实验的结果。
随着页数的增加精度降低。推测这是因为：当数据库具有更大大小时，存储具有相同特征量的不同文档的可能性增大。利用询问2的检索的精度低于利用询问1的检索的精度。推测这是因为：由于更大的透视变形而明显改变了最近点，从而使得难以确保特征量的稳定性。图51示出导致失败检索的示例询问图像。象该询问图像一样，几乎被表/图区域占据的且包括较小文本区域的询问图像导致失败检索。推测这是因为所提取的特征点的数量较小，因此，在检索中匹配文档不能获取足够数量的投票。
实验4：所存储的页数和处理时间之间的关系
确定所存储的页数如何影响处理时间。使用数据库A～D和询问1，并且如下设置参数：n＝8，m＝7和k＝12。图52示出结果。随着所存储的文档的数量的增加，处理时间逐渐增大。如上所述，处理时间受参数n、m和平均列表长度l的影响。在该实验中，参数n、m是固定的。图52示出平均列表长度l。随着所存储的页数的增加平均列表长度增大，这表示散列表中频繁发生冲突。推测其是处理时间增加的原因。
B.相似变换
实验概述
为了验证本发明的相似不变量的有效性，针对检索精度和处理时间进行比较实验。在实验中，使用通过转换如图53所示的英文论文的电子文档所准备的文档图像的数据库和通过由数字照相机拍摄打印后的文档所获得的询问。使用分别包含100个文档图像、1000个文档图像和10000文档图像的数据库A、B和C作为文档图像数据库。数据库B是数据库C所包含的一部分，而数据库A是数据库B所包含的一部分。使用CVPR、ICPR和ICCV等具有相似版面的国际会议论文集的电子数据作为电子文档。使用通过对于纸张表面分别成约90度、约60度、约45度和约30度拍摄根据数据库A所打印的文档所准备的询问图像，作为询问。对于各摄影角度，询问图像的数量是100个。图54示出询问图像的例子。使用具有EF-S 18-55mm USM镜头的CANON EOS Kiss Digital(630万像素)准备询问图像。该实验中所使用的散列表的大小为Hsize＝227-1。使用具有AMD OpteronCPU(2.8GHz)和存储器(16GB)的计算机。
实验1：摄影角度和检索精度之间的关系
首先，当使用交比或相似不变量值计算特征量时，确定询问图像的摄影角度和检索精度之间的关系。在本发明的方法中，性能根据确定用于计算特征量的特征点的集合的数量的参数n、m的值和不变量值的量子化的水平数量k而改变。在该实验中，使用对于n和m的组合(n＝10，m＝10、9、8、7)提供最高精度的k的值。而且，使用具有90～30度的摄影角度的询问和包含100个文档图像的数据库A。
图55示出对于(a)交比和(b)相似不变量的n和m的各组合的摄影角度和检索精度之间的关系。从图55(a)(b)可以看出，随着角度的缩小精度通常降低。推测这是因为由于变形因而最近的特征点的排列发生变化，从而不能满足在n个最近点的m个点中发现匹配的条件，在n和m之间的差较大的情况下(例如，n＝10，m＝7)，精度的降低相对地小。
如图55所示，在(a)交比的情况下，由于角度的缩小的精度的降低较小，而在(b)相似不变量的情况下，由于角度的缩小的精度的降低较大。推测这是由于以下说明的不变量的性质。交比是投影不变量，因此，对于由于透视变形而产生的特征点的位置改变保持不变。然而，对于非透视变形所引起的变化，交比是不稳定的。在本发明的方法中，使用单词区域的重心作为特征点，并且，如果图像遭受了透视变形，则特征点的位置改变。因此，当图像经过极大的透视变形时，特征点的坐标改变，因此基于特征点所计算的交比的值发生改变，从而变得不稳定。
在变形近似于由于相似变换的变形的局部区域中，相似不变量是稳定的。然而，相似变换是过分限制性的，并且，如果透视变形是值得考虑的，则即使在局部区域中也不可能将透视变形近似于相似变形。值得考虑的透视变形降低了特征量的稳定性。
实验2：所存储的页数和检索精度之间的关系
接着，确定对于各不变量所存储的页数和检索精度之间的关系。将参数设置成n＝8和m＝7，并且使用在所存储的页数为100时提供最高精度的k的值。表5示出该结果。象在实验1中一样，随着摄影角度的缩小检索精度降低。而且，随着所存储的页数的增加精度降低。推测这是因为：随着所存储的页数的增加，存储具有相似点排列的文档的可能性增大。象在实验1中一样，使用交比的检索的精度较高，而使用相似不变量的检索的精度较低。
表5
所存储的页数 100 1.000 10.000 检索精度(％) 交比 90° 99 99 98 6O° 99 99 98 45° 98 97 72 30° 12 3 0 相似不变量 90° 100 99 98 60° 73 48 28 45° 3 1 0 30° 3 2 0 处理时间(msec) 交比 80.8 83.0 97.4 相似不变量 118.3 136.6 332.3
实验3：所存储的页数和处理时间之间的关系
对于各不变量确定所存储的页数和处理时间之间的关系。
这里将处理时间定义为：用于利用图44所示的各询问图像进行检索处理并排除预先特征点提取处理所需的时间的所需的时间。以与实验2中相似的方式设置参数。作为例子，表5示出利用每一均具有60度摄影角度的询问图像的检索所需的处理时间。
即使改变询问图像的摄影角度，处理时间一般是恒定的。大体来说，处理时间随着所存储的页数的增加而增加。推测这是因为存储在散列表中的更大量的数据导致更高的冲突率。在交比情况下处理时间相对短，而在相似不变量情况下相对长。推测这是由于用于计算特征量的不变量值的计算数量mCf的不同。在m＝7的情况下，数量mCf随着f的减小而增大。因此，与交比下的情况相比，在相似不变量的情况下利用f＝5的处理时间更长。在相似不变量的情况下，从10000个所存储的页的检索需要更加长的处理时间。推测这是因为：使用较少数量的点计算相似不变量，因此，倾向于将不变量值离散化成相同水平，因而在散列表中导致更大数量的冲突。
C.文档以外的图像
为了验证本发明的方法对文档以外的对象的适用性，通过使用通过由数字照相机拍摄海报和杂志的封面所获得的图像进行实验。
实验概述
与文档图像不同，对于特征点处理，通过下面的文献(例如，参考Y.Ke and R.Sukthankar，PCA-SIFT：representation for localimage descriptors，Proc.CVPR，Vol.2，pages 506-513，2004)中提出的PCA-SIFT方法处理这些对象的图像。
在PCA-SIFT方法中，从图像提取特征点，并且确定表现特征点特征的d维特征向量v＝(v1，...，vd)。通过PCA-SIFT所确定的特征点和特征向量是基于SIFT方法(例如，参考D.G.Lowe，Distinctive image features from scale invariant keypoints，International Journal of Computer Vision，Vol.60，No.2，pp.91-110，2004).
在该方法中，将通过PCA-SIFT方法所获得的实数的向量V变换成位向量w＝(w1，...，wd)备用。可以考虑各种变换方法。例如，可以使用这样的方法：如果vi≥0，则wi＝1，否则wi＝0。下面将说明该方法。
如在文档图像的处理中一样，该方法组合使用多个特征点。图56对此进行简要示出，在图56中，点p0是感兴趣的点，并且在点p0周围存在其它的点p1...。图5 6示出三个最近的点的两个点的组合(n＝3，m＝2)。在组合三个点p0、p1和p2的情况下，将各点的位向量表示为w0、w1和w2，并且以集合形式表示为wi＝(w1i，...，wdi)。在这种情况下，作为组合的结果所获得的特征向量w0’是3维位向量，表示如下：
w0’＝(w0，w1，w2)＝(w10，...，wd0，w11，...，wd1，w12，...，wd2)
象在文档图像的处理中一样，将该向量转换成散列表的索引。更具体地，根据下面的公式计算索引Hindex：
[公式15]
其中，r是将组合的特征点的数量，而Hsize是散列表的大小。
实验
为了验证该方法的有效性，进行实验。使用包括AMDOpteron(2.8GHz)和存储器(16GB)的计算机。SIFT的特征向量的维数是128，而PCA-SIFT的维数是36。在该方法中，为了产生位向量的组合，在范围9＜d＜36中可变地设置原始位向量wi的维数。这意味着：如果d＝9，则使用位向量wi1～wi9。对于点的组合，在范围5＜n＜30和1＜m＜3中可变地设置参数n、m。还考虑特殊情况，在其中，没有形成特征点的组合(n＝0，m＝0)。
在该实验中，使用40个平面物体。对象包括5个海报和35个名为Comm.Of the ACM的杂志的封面。通过照相机(630万像素)拍摄这些对象以提供均具有3042×2048大小的彩色图像。在该实验中，将这些彩色图像均转换成1024×683灰度图像。
准备以三个不同角度(45度、60度和75度)水平拍摄对象所获得的图像和通过正面拍摄对象所获得的且具有两种不同大小(较大大小和较小大小)的图像，作为询问图像。也就是说，为每一对象准备包括不同视图的5种类型的图像。除较大大小图像以外，每一图像包含整个对象图像。每一较大大小图像包含约50％的整个对象图像。由于以5种不同方式拍摄50个平面物体，因而使用总共200个图像作为询问图像。将通过以90度摄影角度拍摄对象所获得的且均具有中间大小的图像存储在数据库中。因此，存储在数据库中的图像不同于询问图像中的任何一个。
图57示出根据该方法的示例处理。图57(a)示出数据库中的一个图像；而图57(b)～(f)示出如何使询问图像(在上面)中的特征点与数据库中的特征点(在下面)相关联。在该例子中，从数据库中的40个图像成功检索正确图像。
在该实验中，还使用下面两种比较方法。
(1)一种方法，在该方法中，照原样采用通过SIFT方法所获得的128维实数向量，并且从该数据库的检索是基于最短欧几里得距离(以下将该方法称为“SIFT方法”)；以及
(2)另一方法，在该方法中，使用通过PCA-SIFT方法所获得的36维实数向量，并且该检索是基于欧几里得距离(以下将该方法称为“PCA-SIFT方法”)。
表6示出处理精度和处理时间。
表6
方法 精度(％) 时间/询问(msec) 平均 最大 最小 SIFT 100 2.0×105 1.2×106 1.8×104 PCA-SIFT 100 2.6×104 1.6×105 2.3×103 本发明的方法(d＝24，n＝0，m＝0) 89.0 26.3 170 ＜10 本发明的方法(d＝16，n＝28，m＝1) 90.5 61.2 380 10
SIFT方法和PCA-SIFT方法均提供100％的检索精度，但是需要巨大的处理时间。本发明的方法有力地减少了处理时间，同时提供约90％的处理精度。
在本发明的方法中，使用两种参数设置(d＝24，n＝0，m＝0)和(d＝16，n＝28，m＝1)。与不基于点的组合的检索处理的前一设置相比，基于点的组合的检索处理的后一设置提供提高的处理精度。
表7详细示出失败检索。
表7
d＝24，n＝0，m＝0 d＝16，n＝28，m＝1 失败检索中的匹配图像的平均 5.6 3.8 错误检索的图像的数量 45degrees 21 13 60degrees 1 0 75degrees 0 0 较大大小 0 0 较小大小 0 6 投票数量的平均比 成功检索 10.18 7.08 失败检索 1.14 1.18
与不基于点的组合的检索处理(左边的参数设置)相比，在基于点的组合的检索处理(右边的参数设置)中，失败检索中的匹配图像的平均等级较高。这表示：即使在失败检索中，也对正确图像赋予高的等级。在基于点的组合的检索处理中，三分之二的失败检索是由于具有较小摄影角度(45度)的询问图像，并且三分之一的失败检索是由于较小大小的询问图像。在实际应用中重要的以较大角度(60～75度)所拍摄的询问图像和较大大小的询问图像不发生错误检索。在表7中，还示出了最大数量的投票与第二最大数量的投票的平均比(投票数量的比)。
在成功检索中，最大数量的投票是大于第二最大数量的投票7倍。另一方面，在失败检索中，最大数量的投票仅稍稍大于第二最高投票计数。参考投票计数的比，可以预测是否检索正确图像。通过为该比适当设置阈值，可以消除处理错误。在上述情况下，通过设置阈值将处理精度增大至75％，从而消除所有错误。
设备的示例结构
将给出对于用于将文档和/或图像存储在文档和/或图像数据库中的本发明的文档和/或图像存储设备的示例结构的说明。还给出对于用于从文档和/或图像数据库检索文档和/或图像的本发明的文档和/或图像检索设备的示例结构的说明，其中，在文档和/或图像数据库中，由文档和/或图像存储设备存储文档和/或图像。
图39是示出本发明的文档和/或图像存储设备1的结构的框图。文档和/或图像存储设备1包括输入部11、特征点提取部15、特征点选择部17和特征点存储部19。输入部11是输入将存储的文档和/或图像的部。特征点提取部15是从文档和/或图像提取定义图像配置的多个特征点的部。特征点选择部17是距离所提取的特征点p最近的n个特征点的部。特征点存储部19是这样的部：为从所选择的n个特征点所选择的m个点(m＜n)的所有可能的集合中的每一个，根据实施例1或实施例2中所述的存储处理，计算散列表的索引，并将输入的文档和/或图像存储在文档和/或图像数据库31中。
图40是示出本发明的文档和/或图像检索设备的结构的框图。检索设备3包括读取部21、特征点提取部23、特征点选择部25、投票部27和ID指定部29。读取部21是读取所拍摄的图像的部。特征点提取部23是从所读取的图像提取定义图像配置的多个特征点的部，并对应于图39中的特征点提取部15。特征点选择部25是选择距离所提取的特征点p中每一个最近的n个特征点的部，并对应于图39中的特征点选择部17。投票部27是根据实施例1或实施例2所述的检索处理对具有匹配特征量的文档ID投票的部。ID指定部29是基于为各特征点投票的计数指定与所拍摄的图像相对应的文档和/或图像的文档ID的部。
工业可应用性
与物理对象的链接
根据本发明的图像检索方法，可以在物理对象(文档、宣传册、海报或布告板)和电子数据(因特网的主页等相关信息)之间建立链接，从而可以基于物理对象的图像检索与物理对象相关的电子数据。在将报纸和杂志文章等文本媒体存储在因特网上的服务器中的情况下，例如，用户可以访问因特网上的服务器以仅通过拍摄任一介质的图像来获取相关数据。因此，本发明在检索文本介质的图像中非常有效。
本发明还适用于在广告宣传册和因特网上的主页之间建立链接的目录购物系统。而且，本发明可以用于基于通过拍摄海报所获得的图像检索与海报的内容相关的信息的应用、或者用于基于通过拍摄街道上的布告板所获得的图像检索与该布告板相关的信息的应用。而且，本发明还可以用于检索包括附加给地图信息(简明地图)的信息的电子数据作为相关信息的应用。
在该链接中，除文本信息和图形信息以外，相关信息还可以包括音频信息和视频信息。
可以由提供服务的供应商建立链接，或者由个人用户私人建立链接。在用户想要使数据和文档相关联的情况下，例如，本发明使用户通过使用照相机在电子数据和文档之间建立链接。
而且，本发明的实时处理能力(高速处理能力)使得可以以与通过照相机实时查看的物理对象(文档、宣传册或海报)的图像成重叠关系，显示电子数据。这是信息处理的一种形式，倍称为“智能信息透镜”。
物理对象之间的链接
如上所述，可以在物理对象和电子数据之间建立链接。根据本发明的图像检索方法，还可以考虑在物理对象之间建立链接。具体的例子如下：
(1)当有两个相关文档时，根据需要记录这两个文档的关联。
(2)根据需要与物理对象(文档、宣传册或海报)相关联记录人或物(产品等)(根据需要通过拍摄文档检索人或物的照片)。这类信息处理被当作为用于通过照片在物理对象之间建立链接的处理。
注解提取系统的应用
而且，本发明的图像检索方法可以用于将在文档中经常做出的注解包含进电子文档中。
图37是示出用于将在文档中做出的注解包含进电子文档中的系统的示例结构的说明图。如图37所示，该系统配置如下：
(1)将没有注解的文档作为原始文档存储在数据库中。
(2)利用照相机拍摄有注解的文档，并且通过本发明的方法从数据库检索没有注解的文档。结果，将没有注解的文档中的特征点与有注解的文档中的特征点相关联。
(3)基于特征点相互关系，将通过利用照相机拍摄有注解的文档所获得的图像恢复成正向(从倾斜拍摄状态到正向)。图38是用于解释将图像恢复成正向的处理的图。
(4)通过从正确取向的图像减去没有注解的文档的图像，提取注解的图像。
(5)通过将所提取的注解图像添加给电子文档，将注解包含在电子文档中。
这使得可以利用相互无缝链接的纸质文档和电子文档。
本发明的注解提取系统不仅可以链接到连结数字照相机，而且还可以连结到复印机或扫描器。由复印机或扫描器所捕获的图像经过相似变换和仿射变换等几何变换，而不是仅经过照相机所拍摄的图像的通常经受的投影变换。
因此，可以配置注解提取系统以使用相似不变量和仿射不变量。由于与投影变换相比，仿射变换和相似变换限制性更强，因而可以提高注解提取的精度。
散列(hash)允许高速访问数据库中的数据。为将被存储在散列表中的数据定义关键字(key)，并且将数据存储在基于关键字所计算的位置(地址)处。更具体地，准备散列表，将数据列表的指针存储在散列表的各元素中，其中，散列表是通过这些关键字索引的数组的表。根据关键字计算散列表的索引，并参考散列表将数据存储在通过基于所计算的索引所确定的指针所定义的地址中。用于将关键字转换成散列表的索引的函数是散列函数。当检索所存储的数据时，根据散列函数，基于关键字确定散列表的索引，并且对于数据的检索，使用存储在基于所确定的索引所参考的散列表的元素中的指针。
以下说明该处理的步骤。
特征点的提取
对于特征点的提取重要的是特征点的再现性。也就是说，甚至在几何变换、噪声和较低分辨率的影响下，也应该完全一致地获得特征点。使用英文文档中的各个单词的重心(centroid)作为特征点以满足该要求。这是因为，在英文文档中的单词之间存在空格，这使得可以相对容易地分离单词。
利用例子简要说明特征点提取的过程。通过自适应二值化将输入的图像(图4)转换成二值图像(图5)。接着，以下面的方式从二值图像检测单词区域。首先，利用高斯滤波器平滑化(模糊)二值图像。此时，基于对字符大小的估计(连结成分的面积的模式值(mode value)的平方根)自适应地确定高斯滤波器的参数。平滑化后的图像再次经过自适应二值化以提供二值图像(图6)。该图像中的连结成分被当作为单词区域，并且将各单词区域的重心定义为特征点。从图6所示的图像获得图7所示的特征点。
接着，参考图36所示的流程图详细说明该过程。根据图36(a)的流程图处理输入的图像，以提供特征点的集合。
第一步骤是大小校正步骤。在其中，输入的图像是装配到移动电话的照相机所拍摄的图像，该图像的大小明显不同于普通图像大小。因此，对于大小校正，放大输入的图像。
接着，进行通过下面的公式所定义的自适应二值化步骤。
[公式7]
[公式8]
其中，I表示输入的图像(灰度图像)，F表示输出的图像(二值图像)，T表示通过上面的公式(2)自适应定义的阈值，b是用于确定阈值的所参考的块(block)的大小，而s是用于控制阈值的参数。公式(2)表示：使用通过从块的平均密度减去预定值s所获得的值作为阈值。
图36(b)示出预处理步骤。根据系统模式，即，用于将文档和/或图像存储在数据库中的数据库结构模式或用于检索与所拍摄的图像相对应的文档和/或图像的检索模式，以不同的方式进行预处理步骤。如果在系统模式不是数据库结构模式时，以普通检索模式进行检索操作，而不使用移动电话照相机，则消除(remove)各自具有较小面积的连结成分。另一方面，在数据库结构模式中，为了估计字符大小，确定连结成分的面积的模式值的平方根。为了确定用于平滑化的参数c，字符大小乘以HashScale。在平滑化中，根据下面的公式确定高斯滤波器的标准差σ：
[公式9]
σ＝(c/2-1)×0.3+0.8
然后，通过由该公式所定义的高斯滤波器平滑化图像，并通过自适应二值化将图像再次转换成二值图像。从而预处理图像。
参考图36(c)的流程图，预处理步骤随后的步骤是平滑化参数估计步骤。以与上述参数估计相同的方式进行该步骤。同样以与上述相同的方式进行下一平滑化步骤。在平滑化步骤后，再次通过自适应二值化将图像转换成二值图像。最后，从通过该处理所获得的二值图像提取连结成分，并将连结成分的重心确定为特征点。
用于索引的特征量的计算
用于存储和检索的关键字是如何基于交比计算散列表的索引。在详细说明存储和检索前，说明用于确定索引的特征量的计算。
基于图像中的特征点所计算的交比的值是连续值。为了用于确定索引，将交比值离散化成k个水平。为了吸收由于几何变换和摄影条件的改变而产生的误差，数量k适宜相对小。如果数值k过小，则降低了辨别力。因此，应该适当选择数量k。这里，所利用例子采用基于预先实验的结果所确定的k＝9，但是这不是限制性的。确定各特征点周围的局部区域的特征量以使得可以基于图像的一部分检索。
为围绕特征点的局部区域所定义的特征量的可能例子如下：
(1)距离特征点最近的5个点的交比；
(2)基于从距离特征点最近的n个点所选择的5个点的集合的交比；
(3)从距离特征点最近的n个点所选择的m个点的排列和基于从m个点所选择的5个点的集合的交比。
在本发明中，采用最复杂的特征量(3)。从最简单的一个开始说明这三个特征量。而且，将说明本发明中所采用的特征量和为什么使用最复杂的特征量的原因。
5个最近点的交比
基于围绕特征点的局部区域的交比定义特征量的容易想到的方法是计算距离特征点最近的5个点的交比。例如，如图8所示，选择距离特征点p最近的5个点1～5，并计算这5个点的交比，以采用其作为点p的特征量。
然而，在以图8和9所示的不同角度所拍摄的文档和/或图像中，最近的5个点可能变化。因此，该方法的问题在于从同一文档所获得的文档和/或图像不能提供同一特征点的相同特征量。
基于从n个最近点所选择的5个点的集合的交比
另一想到的方法是提取从n个最近点所选择的5个点的所有可能的集合，并基于各5个点的集合计算交比。
图8和9所示的文档和/或图像在5个最近点上是不一致的，但是在8个最近点中的7个点上是一致的。因此，n个最近点包括基本保持不变的m(＜n)个点。因此，在计算从n个点所选择的5个点的所有可能的集合的交比的情况下，推测在基于从共同的m个点所选择的5个点的集合所计算的交比是一致的。因此，采用基于从n个点所选择的5个点的所有可能的集合所计算的交比作为特征量。如果在比较步骤中，与基于来自共同的m个点的5个点的集合所计算的交比中的任何一个一致的交比的数量不小于预定数量，则认为文档和/或图像中感兴趣的特征点是相同的。
然而，实际检索中该特征量的使用经常导致不正确的检索结果。参考图10，例如，为了简单，这里假定：基于从距离各特征点最近的n个点所选择的点的集合，计算四个交比。还假定：为特征点A所计算的交比集合为(0.2，1.3，0.3，1.8)，而为特征点B所计算的交比集合为(1.2，1.6，0.1，0.2)。如果以步长0.5离散化这些交比，则特征点A和特征点B的离散化后的交比的集合分别为(0，2，0，3)和(2，3，0，0)。仅考虑交比的值，值0、2和3共同出现在特征点A和B的交比的集合中，因此判断特征点A和B是相同的。在以该方式对实际图像确定交比的情况下，这样的情况经常发生，结果导致失败检索。
从n个最近点所选择的m个点的排列和基于从m个点所选择的5个点的集合的交比
上述问题的解决方案是同时考虑交比的顺序。也就是说，在图10所示的例子中，交比组(0，2，0，3)区别于交比组(2，3，0，0)。
参考图11，更具体地，假定围绕从同一文档所获得的不同图像中的相应的点分别定义一组8个点ABCDEFGH和一组8个点IJKLMNOP。这两个8个点的组仅在一个点E、L是不一致的，而在其余7个点是一致的。因此，在从每一个8个点的组中的8个点选择7个点的所有可能的集合的情况下，一组点ABCDFGH与一组点IJKMNOP是相同的。因此，在通过在每一相同的7个点的集合中从共同的7个点以预定顺序选择5个点来定义有序的5个点的所有可能的集合的情况下，有序的5个点的集合是一致的。也就是说，在基于来自每一8个点的组中的共同的7个点的所有可能的有序的5个点的集合来计算交比的情况下，即，计算一组点ABCDF和一组点IJKMN的交比和一组点ABCDG和一组点IJKMO的交比等的情况下，作为结果的7个点的组的交比序列在交比的顺序和各交比的值上是相同的。很少有基于不同的7个点的集合所确定的交比序列在交比顺序和交比值上是相同的。因此，通过采用交比序列作为特征量可以解决上述问题。
概括地说，首先提取距离特定点最近的n个点，然后定义从n个点所选择的m个点的所有可能的集合。而且，定义从m个点按照预定顺序所选择的有序的5个点的所有可能的集合，并且顺序计算各有序的5个点的集合的交比。如果在交比序列中发现至少1个交比的值和位置一致，则判断这些交比序列具有相同特征量。
实施例1
存储
基于上述的准备处理说明存储处理。当将文档和/或图像存储在数据库中时，从文档和/或图像提取特征点，而且计算各特征点的特征量并将其与文档和/或图像相关联存储。在获取所拍摄的图像的数据时，计算图像数据的特征量，并且检查存储在数据库中的各文档和/或图像的特征量与所计算的特征量一致，从而从存储在数据库中的文档和/或图像检索与所拍摄的图像的数据相对应的文档和/或图像。
图12示出存储处理的示例过程。在该处理中，文档ID是分配给各文档的标识号。点ID是分配给每一文档中的各点的标识号，anCm模式ID是分配给从n个点所选择的m个点的各组的且取值0～nCm-1的标识号。相似地，amC5模式ID是分配给从m个点所选择的5个点的各组的且取值0～mC5-1的标识号。
图13示出散列表的结构，将文档和/或图像存储在散列表中。这里将术语“文档图像”定义为文档的图像。在存储处理中，重复处理序列，在其中，在行5～8确定散列表的索引，并且在行9使用索引将上述的ID存储在散列表中。
根据图12所示的过程进一步说明存储处理。在行5～7，基于一组5个的点计算5个交比。使用循环移位起始点所获得的5个点ABCDE的循环排列的ABCDE、BCDEA、CDEAB、DEABC和EABCD，获得5个交比。
在行8，根据下面的散列函数计算散列表的索引：
[公式10]
其中，crn(n＝0～4)是5个交比的离散值，Vmax是离散交比值的最大值，而pat是mC5模式ID。
在行9，使用索引将列表(文档ID、点ID、nCm模式ID)存储在散列表中。当发生冲突时，如图13所示，以列表形式另外存储数据。不仅将文档ID而且还将点ID和nCm模式ID存储在散列表中。这是因为，当在检索处理中比较特征量时，针对每一列表(文档ID、点ID和nCm模式ID)确定交比序列中的匹配的交比的数量。
检索
接着说明检索处理。图14示出检索处理的示例过程。在本发明中，参考图15所示的一次投票表，检查是否在交比序列中发现了至少预定数量l个交比匹配。如果发现了匹配，在图16所示的二次投票表中对相应的文档进行投票以提供检索结果。为了适当确定数量l，通过使用一些可能的数量l(l＜nCm)预先进行实验，并采用提供正确检索结果与错误检索结果的最高比的数量作为数量l。
以与存储处理相同的方式说明检索处理。在图14所示的检索处理中的行6～9，以与存储处理相同的方式确定散列表的索引，并在行10从散列表读取图13所示的列表。对于列表中的每一元素，对于一次投票表的相应单元格(cell)进行投票。
在重复这些步骤完成对来自m个点的所有5个点的集合的投票后，检查一次投票表的单元格。如果检测到了具有不少于1的投票数量的单元格，则对二次投票表中的相应的文档ID投票。
最后，最终确定二次投票表中具有最大投票数量的文档作为检索结果。
在行4，通过在点集Pm中移位起始点形成点集Pm的点的所有可能的循环排列{P’m}，并且以上述方式处理循环排列{P’m}。该步骤对应于用于从点集Pm形成m个循环排列{P’m}的处理。例如，从ABCDEFG，形成循环排列BCDEFGA和CDEFGAB等。该步骤是处理旋转图像所需要的。
实施例2-更高速的处理
将说明根据本发明的一种方法，在其中，与实施例1相比，减少了存储或检索所需的处理时间。
在说明改进的存储和检索方法前，给出对于特征量的计算的补充说明。
特征量的计算
1.特征量需要满足的条件
这里将特征量定义为表示文档图像中的各特征点的值。计算用于检索的询问的和将存储的文档的特征点的特征量，并且通过将询问的特征量与所存储的文档的每一个的特征量进行比较，判断询问是否匹配所存储的文档中的任何一个。
基于检索的准确度和检索所需的计算复杂度，估计特征量。认为使得可以准确且高速检索与询问相对应的所存储的文档的特征量是良好的。如下定义了为了准确度特征量需要满足的两个条件。
第一条件是：即使在各种类型的变形的影响下，为同一文档的相同点所计算的特征量应该保持不变。如果为询问和相应的所存储的文档计算不同的特征量，则在检索处理中不可能发现匹配的特征点。将该条件称为“特征量的稳定性”。
第二条件是：为不同点所计算的特征量应该不同。如果为不同的文档计算相同的特征量，则在检索处理中不仅检测匹配的特征点，而且还检测不相关的特征点。将这一条件称为“特征量的辨别力”。
而且，第三条件是：特征量的计算需要相对小的计算复杂度。当然难以使用需要巨大计算量的特征量，即使该特征量具有更高的稳定性和更高的辨别力。因此，除上述的针对准确度的两个条件以外，特征量应该满足为了较小计算复杂度的条件。
为了更高速和更高准确度的文档图像检索，特征量应该满足这三个条件。
2.特征量的稳定性
对于上述三个条件，首先说明特征量的稳定性。在如上所述的本发明的方法中，基于距离各特征点最近的点的不变量值，计算特征量。为了稳定提供特征量，即使由于透视变形而最近的点的坐标发生变化，计算特征量所使用的最近的点也应该保持不变。如图8和9所示，在透视变形的影响下，最近的点发生改变。因此，如果使用基于距离特征点p最近的f个点所计算的不变量值作为特征量，则对于同一特征点p不可能提供相同的特征量。
因此，在本发明中，定义从更大范围中的距离特征点最近的点所选择的多个点的集合，并且基于多个点的各个集合计算多个特征量。这是基于假定：即使在透视变形的影响下，图像中共同存在更大范围中的n个最近点(图8和9中的8个点)中m个点(图8和9中的7个点)。假定在图像中共同存在n个最近点中的m个点，则如图41所示，定义来自n个点的所有可能的m个点的集合Pm(0)、Pm(1)、...、Pm(nCm-1)，并且计算各点集的特征量。在这种情况下，为各特征点所计算的特征量至少包括一个共同的特征量。
3.特征量的辨别力
接着说明特征量的辨别力。在本发明的方法中，通过增加用于计算单个特征量的特征点的数量m提高特征量的辨别力。使用基于如图42所示的从m个点所选择的f个点的所有可能的集合所计算的不变量值序列cr(0)、cr(1)、...、cr(mCf-1)作为m个点的排列的表示方法，其中，cr(i)是等于具有相同值的cri的交比。随着数量m的增大，将计算的不变量值的数量增大。因此，降低了偶然重合的可能性。然而，如果数量m过大，则特征量的稳定性降低。这是因为，对于特征量的匹配，应该在所有不变量值中发现匹配，并且数量m的增大使得不变量值的数量mCf增大，从而增大了由于误差的影响而计算出不同的不变量值的可能性。
4.计算复杂度和存储容量
如上所述，数量n的增大使得可以计算更大范围的多个特征量，从而提高了特征量的稳定性。而且，数量m的增大使得可以基于更大数量的点计算各特征量，从而提高了特征量的辨别力。然而，如果过分增大这些参数的值，则会出现与计算复杂度相关的问题。也就是说，如果数量m和n过大，则不变量值的计算的计算复杂度增大。因此，存储和检索所需的处理时间相应增大。而且，为了存储所计算的特征量，存储器需要更大的存储容量。
5.不变量值的量子化水平
稳定性和辨别力不仅受参数n、m的影响，而且还受不变量值的量子化的水平的数量k的影响。如果数量k较大(精细离散化每一不变量值)，则由于误差的影响增大了以不同水平离散化基于f个点的相同集合所计算的不变量值的可能性，从而降低了稳定性。如果数量k较小(粗略离散化每一不变量值)，则增大了以相同水平离散化基于f个点的不同集合所计算的不变量值的可能性，从而降低了辨别力。因此，应该适当设置参数n、m和k以确保利用较小的存储容量、以更高的准确度更高速地进行检索处理。
存储
参考图28说明不同于实施例1的存储处理的另一示例过程。
在存储处理中，定义从将存储的文档中的距离各特征点最近的n个点所选择的m个点的所有可能的集合。然后，基于根据各个m个点的集合所计算的交比，确定索引，并将交比存储在图29所示的散列表中。以下根据图28所示的过程说明存储处理。在行1，从特征点的集合提取一个特征点p。在行2，顺时针顺序提取距离特征点p最近的n个点以提供点集Pn。在行3，从点集Pn提取m个点以提供点集Pm。在行5，计算从点集Pm所选择的5个点的所有可能的集合的交比值，并离散化交比值以提供交比cri。由于来自m个点的5个点的集合的数量是mC5，因而“i”取值0～mC5-1。
在行7，基于如此提供的交比cri，根据散列函数确定散列表的索引Hindex。在行8，基于散列索引Hindex将文档ID(将存储的文档的标识号)、点ID(点的标识号)和交比cri(i＝0，...，mC5-1)存储在散列表中。散列函数如下：
[公式11]
其中，k是交比的量子化水平的数量，Hsize是散列表的大小。在存储处理中发生冲突的情况下，以图29所示的列表添加数据。
图43示出存储处理的另一过程。给出对图43的说明。在存储处理中，定义从将存储的文档中的距离各特征点最近的n个点所选择的m个点的所有可能的集合。然后，基于根据各个m个点的集合所计算的不变量值确定索引，并将不变量值存储在图29所示的散列表中。
在图43的行1，从特征点的集合提取一个特征点p。在行2，提取距离特征点p最近的n个点以提供点集Pn。在行3，从点集Pn提取m个点以提供点集Pm。在行4，围绕点p顺时针排序点集Pm中的m个点以提供特征点序列Lm。在行5，通过从点序列Lm中的点按照预定顺序选择f个点，提供所有可能的特征点序列Lf，并按照词典顺序排列特征点序列Lf。
当m＝7且f＝5时，例如，提供特征点序列((p0，p1，p2，p3，p4)，(p0，p1，p2，p3，p5)，...，(p2，p3，p4，p5，p6))作为(Lf(0)，...，Lf(7C5-1))。在行7，以上述不变量计算公式将各特征点序列Lf(i)中的点取代为A、B、C...，从而计算和离散化不变量值以提供cr(i)。在行9，根据下面的散列函数(3)确定散列表的索引Hindex。在行10，基于索引Hindex将文档ID(将存储的文档标识号)、点ID(点的标识号)和不变量值cr(i)(i＝0，1，..，mCf-1)存储在散列表中。该实施例中所使用的散列函数如下：
[公式12]
其中，k是不变量值的量子化的水平的数量，而Hsize是散列表的大小。在存储处理中发生冲突的情况下，以图29所示的列表的形式添加数据。为了文档的存储对所有特征点p进行上述处理。
检索
接着说明检索处理。图30示出不同于实施例1的检索处理的示例过程。以与存储处理相同的方式说明检索处理。在该过程的行5～8，，以与存储处理中相同的方式确定散列表的索引。在行9，从散列表读取图29所示的列表。参考该列表中的元素检查询问的交比是否完全匹配所存储的交比，并且，如果发现匹配，则对文档ID的线性阵列的投票表的相应单元格投票。
这里的投票对应于用于将询问中的特征点p与所存储的文档中的特征点相关联的处理。如果特征点p与所存储的文档中的特征点独立相关联，则将询问中的一个特征点错误地与多个点相关联，从而提供了图31所示的错误对应关系A-A’，A-A”和B-A’。如果在投票的数量中包括基于错误对应关系的投票，则将相对地降低基于正确对应关系的投票的等级(rating)，从而导致失败检索。在该实施例中，记录询问中的点和所存储的文档中的点之间的对应关系，并对所记录的对应关系不投票。因此，抑制了基于错误对应关系的投票。
对于每一所存储的文档中的所有点进行该处理，并且将具有投票表中最大数量的投票的文档最终确定为检索结果。
在行4，通过移位点集Pm中的起始点定义所有可能的点集{P’m}，并且处理点集{P’m}。该步骤对应于用于定义点集Pm中的点ABCDEFG的m个循环排列{P’m}的处理，即，BCDEFGA和CDEFGAB等。该步骤是处理旋转图像所需要的。
可以根据图44所示的过程进行该处理。给出对于图44的说明。在行1～3，以与存储处理中相同的方式定义p、Pn和Pm。在行4和5，与存储处理中不同，通过将起始点p0移位至点集Pm中的各点，定义特征点序列{Lm}。由于在图43中的存储算法中，在行4仅存储由Pm形成序列{Lm}中的一个，而不考虑图像的旋转，因而需要这样。甚至在透视变形的情况下，围绕点p的特征点的顺时针序列是恒定的，虽然起始点是可移位的。也就是说，在考虑Lm的循环排列的情况下，存储处理中所使用的序列必然是循环排列中的一个。在行6～10，以与存储处理中相同的方式确定散列表的索引。在行11，从散列表读取如图29所示的列表。在行12～14，基于该列表的元素对所存储的文档ID中的相应的文档ID投票。这里，以下面的方式抑制了基于错误对应关系的投票。
使用下面的三个条件：(1)获得不变量的相同序列；(2)询问中的一个点不对应于所存储的文档中的多个点；和(3)所存储的文档中的一个点不对应于询问中的多个点。对于询问图像中的所有点，基于这些条件进行上述处理，以确定各个所存储的文档的投票数量。然而，如此所确定的投票的数量仍包括基于错误对应关系的投票。错误投票的数量一般与所存储的文档中所包含的特征点的数量成比例。因此，具有较大数量特征点的所存储的文档获得不合理地大量投票。为了校正由于错误投票而引起的错误，通过下面的公式(4)定义文档di的得分S(di)：
[公式13]
S(di)＝V(di)-cN(di) ...(4)
其中，V(di)是di的投票的数量，N(di)是文档di中所包含的特征点的数量；而c是特征点的数量和通过预先实验所确定的错误投票的数量之间的比例常数。最终将具有最高得分的文档确定为检索结果。
实施例1的示例实验
实验的概述
为了验证根据实施例1的方法的有效性，基于由普通数字照相机所拍摄的文档图像和由移动电话数字照相机所拍摄的文档图像，进行检索处理。使用具有EF-S 18-55mm USM镜头的CANON(注册商标)数字照相机EOS Kiss Digital(630万像素)作为普通数字照相机，而将装配给移动电话KYOCERA TK31的数字照相机(18万像素)用作移动电话数字照相机。
在文档图像数据库中，存储有通过转换单栏或双栏的英文论文的PDF文件所准备的50个文档图像。图17和18示出数据库中的文档图像的例子。在具有Pentium 4(注册商标)CPU(2.4GHz)和存储器(768MB)的计算机上进行实验。
实验1：使用普通数字照相机的实验
说明使用普通数字照相机的实验的结果。设置上述参数如下：n＝8，m＝7，k＝9，而l＝10。如上所述，k是为各特征点所计算的交比的值的离散化的水平的数量，而l是离散后的交比的数量，离散化的交比适于基于在一次投票中的投票数量判断各特征点的匹配，并且使用离散后的交比作为用于判断是否基于散列表的元素进行二次投票的投票数量的阈值。使用利用如图19～22所示的四个不同摄影范围拍摄通过拍摄10个不同的文档页所准备的总共40个图像，作为询问。摄影范围包括覆盖整个文档页的摄影范围A、覆盖整个文本区域的摄影范围B、覆盖一半文本区域的摄影范围C、以及覆盖四分之一文本区域的摄影范围D。斜拍摄文档页。如果正确的文档图像具有最大数量的投票，就认为检索是正确的。测量平均正确检索率和平均处理时间。
表1示出实验结果。不管摄影范围，从所有输入的图像获得正确的检索结果。随着摄影范围的缩小，处理时间缩短。这是因为减少了处理的特征点的数量。
表1
摄影范围 A B C D 正确检索率(％) 100 100 100 100 处理时间(sec) 231.6 173.1 157.6 118.1
实验2：使用移动电话数字照相机的实验
使用由移动电话数字照相机所拍摄的图23～27的文档图像作为用于检索的询问。图24～26的文档图像导致成功检索，而图23和27的文档图像导致失败检索。利用图23的文档图像的失败检索的原因是：由于过低的分辨率，因而不能相互分开输入的图像中的单词，使得不可能正确提取特征点。利用图27的文档图像的失败检索的原因是：图像的摄影范围过于小，使得不可能正确定义最近的点。即使使用具有更低分辨率的移动电话数字照相机，通过拍摄范围的必要调整，检索也是可以。
上述的实验示出通过以下的文档图像检索方法可以高精度地检索文档图像：使用由数字照相机所拍摄的文档图像作为询问，并采用使用交比和散列表的投票处理。还可以发现：虽然需要调整摄影范围，但是对于检索甚至可以使用由具有更低分辨率的移动电话数字照相机所拍摄的文档图像。
实施例2的示例实验
实验的概述
为了验证根据实施例2的有效性，确定检索精度和数据库大小之间的关系和数据库大小和检索速度之间的关系。利用具有EF-S 18-55mm USM镜头的CANON数字照相机EOS KissDigital(630万像素)通过如图32所示斜拍摄文档准备询问。询问的数量是50。另一方面，将通过转换各种英文论文的PDF文件所准备的10000个文档图像存储在文档图像数据库中。图17和18示出数据库中的文档图像的例子。在实验中，设置处理参数如下：n＝8，m＝7，k＝10，Hsize＝1.28×108。在实验中使用具有AMDOpteron(注册商标)CPU(1.8GHz)和存储器(4GB)的计算机。
实验3：检索精度
确定存储在数据库中的页数和检索精度之间的关系。图33示出实验的结果，该结果表示随着页数的增加精度降低。
在数据库中的页数为10000的情况下，利用50个询问中的49个询问所检索的正确文档图像每一均具有最大的投票数量。因此，检索精度为98％。利用其余询问所检索的正确文档图像具有第五最大投票数据。平均检索时间是137.7ms。图34示出导致失败检索的询问的图像，在失败检索中，正确文档图像不具有最大的投票数量。与该询问图像一样，几乎被表/图区域占据的且包括较小文本区域的询问图像导致失败检索。推测是因为：如果询问图像具有较小数量的特征点，那么将检索的正确文档图像不能获得足够数量的投票。
实验4：检索时间
接着确定所存储的页数如何影响检索时间。图35示出该结果，该结果表示：随着所存储的文档数量的增加，检索时间逐渐增加。图35还示出散列表中的平均列表长度。这里定义平均列表长度为散列表中所包含的非零列表长度的平均值。随着所存储的页数的增加而平均列表长度增大这一情况表示冲突的次数增加。推测其是检索时间增加的原因。
其它示例实验
A.利用交比的检索性能
为了精确估计利用交比和检索的文档图像索引的性能，通过不同地设置参数进行实验。
在实验中，使用通过转换如图45所示的英文论文的PDF文件所准备的文档图像的数据库和通过利用数字照相机拍摄打印后的文档所准备的询问。使用分别包含10个文档图像、100个文档图像、1000个文档图像和10000个文档图像的数据库A、B、C和D作为文档图像数据库。数据库C是数据库D所包含的一部分，而数据库B是是数据库C所包含的一部分。而且，数据库A是数据库B所包含的一部分。使用CVPR、ICPR和ICCV等具有相似版面的国际会议论文集的PDF文件作为PDF文件。
使用通过分别以约60、45和30度拍摄根据数据库B所打印的文档所准备的询问的图像1、2和3，作为询问。询问1、2、3的图像数量均为100个。图46示出询问的例子。使用具有EF-S18-55mm USM镜头的CANON EOS Kiss Digital(630万像素)准备询问图像。实验中所使用的散列表的大小为Hsize＝227-1。使用具有AMD Opteron CPU(1.8GHz)和存储器(6GB)的计算机。
实验1：参数n、m和性能之间的关系
本发明提供的性能根据确定计算特征量使用的特征点的集合的数量的参数n、m改变。通过不同地设置参数n、m组合，确定检索精度、处理时间和所需存储容量。在实验中，使用数据库B和询问1～3。表2～4示出基于不同摄影角度的实验的结果。
表2(摄影角度60度)
n m nCm mC5 k 精度(％) 处理时间 列表数量 l 6 6 1 6 30 90 18.7 6.7×104 1.38 7 6 7 6 40 79 53.4 4.7×105 1.82 7 1 21 5 100 28.3 6.7×104 1.15 8 6 28 6 150 53 133.2 1.9×106 1.11 7 8 21 12 100 122.9 5.3×105 1.02 8 1 56 5 99 53.3 6.7×104 1.00 9 6 84 6 240 10 372.0 5.6×106 1.11 7 36 21 24 100 502.2 2.4×106 1.02 8 9 56 8 99 366.0 6.0×105 1.00 9 1 126 5 74 111.4 6.7×104 1.00 10 6 210 6 120 5 1408.3 1.4×107 1.86 7 120 21 21 100 1662.1 8.0×106 1.05 8 45 56 6 100 1784.7 3.0×106 1.02 9 10 126 2 100 994.9 6.7×105 1.01 10 1 252 2 98 229.0 6.7×104 1.00
表3(摄影角度45度)
n m nCm mC5 k 精度(％) 处理时间 列表数量 l 6 6 1 6 30 28 18.8 6.7×104 1.38 7 6 7 6 40 12 53.8 4.7×105 1.82 7 1 21 8 80 27.9 6.7×104 1.03 8 6 28 6 180 8 131.7 1.9×106 1.08 7 8 21 14 99 123.8 5.3×105 1.01 8 1 56 5 70 53.7 6.7×104 1.00 9 6 84 6 90 6 542.1 5.6×106 1.83 7 36 21 24 100 506.4 2.4×106 1.02 8 9 56 5 99 368.4 6.0×105 1.00 9 1 126 5 22 112.4 6.7×104 1.00 10 6 210 6 150 7 1215.0 1.4×107 1.58 7 120 21 21 100 1673.8 8.0×106 1.05 8 45 56 6 100 1803.9 3.0×106 1.02 9 10 126 2 100 997.7 6.7×105 1.01 10 1 252 2 70 230.8 6.7×104 1.00
表4(摄影角度30度)
n m nCm mC5 k 精度(％) 处理时间 列表数量 l 6 6 1 6 40 5 20.6 6.7×104 1.18 7 6 7 6 40 3 60.3 4.7×105 1.82 7 1 21 8 7 31.3 6.7×104 1.03 8 6 28 6 180 4 147.7 1.9×106 1.08 7 8 21 15 12 138.1 5.3×105 1.01 8 1 56 9 6 60.1 6.7×104 1.00 9 6 84 6 90 5 611.0 5.6×106 1.83 7 36 21 22 25 566.6 2.4×106 1.02 8 9 56 5 20 413.3 6.0×105 1.01 9 1 126 5 1 125.6 6.7×104 1.00 10 6 210 6 210 4 1183.4 1.4×107 1.31 7 120 21 24 39 1885.0 8.0×106 1.04 8 45 56 6 45 2019.4 3.0×106 1.02 9 10 126 3 18 1115.3 6.7×105 1.00 10 1 252 2 4 258.1 6.7×104 1.00
这里将精度定义为每一匹配询问且具有最大投票数量的文档图像的数量的比率，而这里将处理时间定义为除特征点提取处理以外的检索处理所需的时间。将列表数量定义为存储在散列表中的列表的总数(每一列表包括一组文档ID、点ID和交比序列cr(0，...，cr(mC5-1)，如图29所示)，并且l是散列表中的非零列表长度的平均值。在表2～4中，示出了对n和m的各组合通过使用提供最高精度的k的值所获得的每一结果。作为参考，还示出了n和m的组合的数量nCm和mC5。首先，检查精度。
通常，随着摄影角度的缩小，精度降低。推测是因为更大的透视变形导致最近点的更大变化，因而使得不可能确保特征量的稳定性。然而，如图47所示，如果n和m之间的差更大，则抑制了精度的降低。这是因为差n-m等于可允许的错误的特征点的数量。接着，检查处理时间。考虑到图44所示的检索算法的结构，假定由计算特征量所需的时间、列表处理所需的时间和迭代次数确定处理时间。计算特征量所需的时间通常与特征量的交比mC5的数量成比例，而列表处理所需的时间与平均列表长度l成比例。迭代次数为nCm×m。因此，这里通过下面的公式(5)，基于参数n、m和平均列表长度l将处理时间定义为T(n，m，l)：
[公式14]
T(n，m，l)＝nCm·m·(mC5+αl) ...(5)
其中，α是对于特征量计算时间的列表处理时间的权重。
图48示出在α＝3时所获得的T(n，m，l)与处理时间的曲线图。从图48可以看出，T(n，m，l)通常与处理时间成比例。因此，推测处理时间受n、m、l的影响，如公式(5)所示。最后，检查所需的存储容量。在表2～4中，存储在散列表中的列表数量与nCm成比例。这是因为针对每一点存储特征量。如上所述，必须增大值n-m以确保更高的稳定性，但是这相应地增大了所需的存储容量。
实验2：量子化水平的数量和性能之间的关系
本发明的方法所提供的性能根据量子化水平的数量k而改变。通过使用数据库B和询问1，并将参数设置成n＝8和m＝7，来确定k和精度之间的关系、以及k和处理时间之间的关系。图49示出该结果。首先，检查精度。在k较小时精度较低，而随着k的增大精度急剧升高。推测这是因为当k较小时特征量的辨别力较低，因而不能确保匹配文档和非匹配文档之间的适当辨别。当k过大时，精度急剧下降。推测这是因为特征量的稳定性降低。接着，检查处理时间。处理时间首先随着k的增大而急剧减少，然后通常保持恒定。推测这是因为：在k较小时特征量的辨别力较低，并且在散列表中频繁发生冲突，从而导致检索处理中散列访问时间的增加。因此，为了确保更高速和更高精度的检索，应当适当设置数量k。
实验3：所存储的页数和检索精度之间的关系
通过使用数据库A～D在10～10000之间可变地设置所存储的页数，确定所存储的页数和检索精度之间的关系。使用询问l和2作为询问。对于这两个询问将参数设置成n＝8和m＝7。此时，如表2和3所示设置数量k。图50示出实验的结果。
随着页数的增加精度降低。推测这是因为：当数据库具有更大大小时，存储具有相同特征量的不同文档的可能性增大。利用询问2的检索的精度低于利用询问1的检索的精度。推测这是因为：由于更大的透视变形而明显改变了最近点，从而使得难以确保特征量的稳定性。图51示出导致失败检索的示例询问图像。象该询问图像一样，几乎被表/图区域占据的且包括较小文本区域的询问图像导致失败检索。推测这是因为所提取的特征点的数量较小，因此，在检索中匹配文档不能获取足够数量的投票。
实验4：所存储的页数和处理时间之间的关系
确定所存储的页数如何影响处理时间。使用数据库A～D和询问1，并且如下设置参数：n＝8，m＝7和k＝12。图52示出结果。随着所存储的文档的数量的增加，处理时间逐渐增大。如上所述，处理时间受参数n、m和平均列表长度l的影响。在该实验中，参数n、m是固定的。图52示出平均列表长度l。随着所存储的页数的增加平均列表长度增大，这表示散列表中频繁发生冲突。推测其是处理时间增加的原因。
B.相似变换
实验概述
为了验证本发明的相似不变量的有效性，针对检索精度和处理时间进行比较实验。在实验中，使用通过转换如图53所示的英文论文的电子文档所准备的文档图像的数据库和通过由数字照相机拍摄打印后的文档所获得的询问。使用分别包含100个文档图像、1000个文档图像和10000文档图像的数据库A、B和C作为文档图像数据库。数据库B是数据库C所包含的一部分，而数据库A是数据库B所包含的一部分。使用CVPR、ICPR和ICCV等具有相似版面的国际会议论文集的电子数据作为电子文档。使用通过对于纸张表面分别成约90度、约60度、约45度和约30度拍摄根据数据库A所打印的文档所准备的询问图像，作为询问。对于各摄影角度，询问图像的数量是100个。图54示出询问图像的例子。使用具有EF-S 18-55mm USM镜头的CANON EOS Kiss Digital(630万像素)准备询问图像。该实验中所使用的散列表的大小为Hsize＝227-1。使用具有AMD OpteronCPU(2.8GHz)和存储器(16GB)的计算机。
实验1：摄影角度和检索精度之间的关系
首先，当使用交比或相似不变量值计算特征量时，确定询问图像的摄影角度和检索精度之间的关系。在本发明的方法中，性能根据确定用于计算特征量的特征点的集合的数量的参数n、m的值和不变量值的量子化的水平数量k而改变。在该实验中，使用对于n和m的组合(n＝10，m＝10、9、8、7)提供最高精度的k的值。而且，使用具有90～30度的摄影角度的询问和包含100个文档图像的数据库A。
图55示出对于(a)交比和(b)相似不变量的n和m的各组合的摄影角度和检索精度之间的关系。从图55(a)(b)可以看出，随着角度的缩小精度通常降低。推测这是因为由于变形因而最近的特征点的排列发生变化，从而不能满足在n个最近点的m个点中发现匹配的条件，在n和m之间的差较大的情况下(例如，n＝10，m＝7)，精度的降低相对地小。
如图55所示，在(a)交比的情况下，由于角度的缩小的精度的降低较小，而在(b)相似不变量的情况下，由于角度的缩小的精度的降低较大。推测这是由于以下说明的不变量的性质。交比是投影不变量，因此，对于由于透视变形而产生的特征点的位置改变保持不变。然而，对于非透视变形所引起的变化，交比是不稳定的。在本发明的方法中，使用单词区域的重心作为特征点，并且，如果图像遭受了透视变形，则特征点的位置改变。因此，当图像经过极大的透视变形时，特征点的坐标改变，因此基于特征点所计算的交比的值发生改变，从而变得不稳定。
在变形近似于由于相似变换的变形的局部区域中，相似不变量是稳定的。然而，相似变换是过分限制性的，并且，如果透视变形是值得考虑的，则即使在局部区域中也不可能将透视变形近似于相似变形。值得考虑的透视变形降低了特征量的稳定性。
实验2：所存储的页数和检索精度之间的关系
接着，确定对于各不变量所存储的页数和检索精度之间的关系。将参数设置成n＝8和m＝7，并且使用在所存储的页数为100时提供最高精度的k的值。表5示出该结果。象在实验1中一样，随着摄影角度的缩小检索精度降低。而且，随着所存储的页数的增加精度降低。推测这是因为：随着所存储的页数的增加，存储具有相似点排列的文档的可能性增大。象在实验1中一样，使用交比的检索的精度较高，而使用相似不变量的检索的精度较低。
表5
所存储的页数 100 1.000 10.000 检索精度(％) 交比 90° 99 99 98 6O° 99 99 98 45° 98 97 72 30° 12 3 0 相似不变量 90° 100 99 98 60° 73 48 28 45° 3 1 0 30° 3 2 0 处理时间(msec) 交比 80.8 83.0 97.4 相似不变量 118.3 136.6 332.3
实验3：所存储的页数和处理时间之间的关系
对于各不变量确定所存储的页数和处理时间之间的关系。
这里将处理时间定义为：用于利用图44所示的各询问图像进行检索处理并排除预先特征点提取处理所需的时间的所需的时间。以与实验2中相似的方式设置参数。作为例子，表5示出利用每一均具有60度摄影角度的询问图像的检索所需的处理时间。
即使改变询问图像的摄影角度，处理时间一般是恒定的。大体来说，处理时间随着所存储的页数的增加而增加。推测这是因为存储在散列表中的更大量的数据导致更高的冲突率。在交比情况下处理时间相对短，而在相似不变量情况下相对长。推测这是由于用于计算特征量的不变量值的计算数量mCf的不同。在m＝7的情况下，数量mCf随着f的减小而增大。因此，与交比下的情况相比，在相似不变量的情况下利用f＝5的处理时间更长。在相似不变量的情况下，从10000个所存储的页的检索需要更加长的处理时间。推测这是因为：使用较少数量的点计算相似不变量，因此，倾向于将不变量值离散化成相同水平，因而在散列表中导致更大数量的冲突。
C.文档以外的图像
为了验证本发明的方法对文档以外的对象的适用性，通过使用通过由数字照相机拍摄海报和杂志的封面所获得的图像进行实验。
实验概述
与文档图像不同，对于特征点处理，通过下面的文献(例如，参考Y.Ke and R.Sukthankar，PCA-SIFT：representation for localimage descriptors，Proc.CVPR，Vol.2，pages 506-513，2004)中提出的PCA-SIFT方法处理这些对象的图像。
在PCA-SIFT方法中，从图像提取特征点，并且确定表现特征点特征的d维特征向量v＝(v1，...，vd)。通过PCA-SIFT所确定的特征点和特征向量是基于SIFT方法(例如，参考D.G.Lowe，Distinctive image features from scale invariant keypoints，International Journal of Computer Vision，Vol.60，No.2，pp.91-110，2004).
在该方法中，将通过PCA-SIFT方法所获得的实数的向量V变换成位向量w＝(w1，...，wd)备用。可以考虑各种变换方法。例如，可以使用这样的方法：如果vi≥0，则wi＝1，否则wi＝0。下面将说明该方法。
如在文档图像的处理中一样，该方法组合使用多个特征点。图56对此进行简要示出，在图56中，点p0是感兴趣的点，并且在点p0周围存在其它的点p1...。图5 6示出三个最近的点的两个点的组合(n＝3，m＝2)。在组合三个点p0、p1和p2的情况下，将各点的位向量表示为w0、w1和w2，并且以集合形式表示为wi＝(w1i，...，wdi)。在这种情况下，作为组合的结果所获得的特征向量w0’是3维位向量，表示如下：
w0’＝(w0，w1，w2)＝(w10，...，wd0，w11，...，wd1，w12，...，wd2)
象在文档图像的处理中一样，将该向量转换成散列表的索引。更具体地，根据下面的公式计算索引Hindex：
[公式15]
其中，r是将组合的特征点的数量，而Hsize是散列表的大小。
实验
为了验证该方法的有效性，进行实验。使用包括AMDOpteron(2.8GHz)和存储器(16GB)的计算机。SIFT的特征向量的维数是128，而PCA-SIFT的维数是36。在该方法中，为了产生位向量的组合，在范围9＜d＜36中可变地设置原始位向量wi的维数。这意味着：如果d＝9，则使用位向量wi1～wi9。对于点的组合，在范围5＜n＜30和1＜m＜3中可变地设置参数n、m。还考虑特殊情况，在其中，没有形成特征点的组合(n＝0，m＝0)。
在该实验中，使用40个平面物体。对象包括5个海报和35个名为Comm.Of the ACM的杂志的封面。通过照相机(630万像素)拍摄这些对象以提供均具有3042×2048大小的彩色图像。在该实验中，将这些彩色图像均转换成1024×683灰度图像。
准备以三个不同角度(45度、60度和75度)水平拍摄对象所获得的图像和通过正面拍摄对象所获得的且具有两种不同大小(较大大小和较小大小)的图像，作为询问图像。也就是说，为每一对象准备包括不同视图的5种类型的图像。除较大大小图像以外，每一图像包含整个对象图像。每一较大大小图像包含约50％的整个对象图像。由于以5种不同方式拍摄50个平面物体，因而使用总共200个图像作为询问图像。将通过以90度摄影角度拍摄对象所获得的且均具有中间大小的图像存储在数据库中。因此，存储在数据库中的图像不同于询问图像中的任何一个。
图57示出根据该方法的示例处理。图57(a)示出数据库中的一个图像；而图57(b)～(f)示出如何使询问图像(在上面)中的特征点与数据库中的特征点(在下面)相关联。在该例子中，从数据库中的40个图像成功检索正确图像。
在该实验中，还使用下面两种比较方法。
(1)一种方法，在该方法中，照原样采用通过SIFT方法所获得的128维实数向量，并且从该数据库的检索是基于最短欧几里得距离(以下将该方法称为“SIFT方法”)；以及
(2)另一方法，在该方法中，使用通过PCA-SIFT方法所获得的36维实数向量，并且该检索是基于欧几里得距离(以下将该方法称为“PCA-SIFT方法”)。
表6示出处理精度和处理时间。
表6
方法 精度(％) 时间/询问(msec) 平均 最大 最小 SIFT 100 2.0×105 1.2×106 1.8×104 PCA-SIFT 100 2.6×104 1.6×105 2.3×103 本发明的方法(d＝24，n＝0，m＝0) 89.0 26.3 170 ＜10 本发明的方法(d＝16，n＝28，m＝1) 90.5 61.2 380 10
SIFT方法和PCA-SIFT方法均提供100％的检索精度，但是需要巨大的处理时间。本发明的方法有力地减少了处理时间，同时提供约90％的处理精度。
在本发明的方法中，使用两种参数设置(d＝24，n＝0，m＝0)和(d＝16，n＝28，m＝1)。与不基于点的组合的检索处理的前一设置相比，基于点的组合的检索处理的后一设置提供提高的处理精度。
表7详细示出失败检索。
表7
d＝24，n＝0，m＝0 d＝16，n＝28，m＝1 失败检索中的匹配图像的平均 5.6 3.8 错误检索的图像的数量 45degrees 21 13 60degrees 1 0 75degrees 0 0 较大大小 0 0 较小大小 0 6 投票数量的平均比 成功检索 10.18 7.08 失败检索 1.14 1.18
与不基于点的组合的检索处理(左边的参数设置)相比，在基于点的组合的检索处理(右边的参数设置)中，失败检索中的匹配图像的平均等级较高。这表示：即使在失败检索中，也对正确图像赋予高的等级。在基于点的组合的检索处理中，三分之二的失败检索是由于具有较小摄影角度(45度)的询问图像，并且三分之一的失败检索是由于较小大小的询问图像。在实际应用中重要的以较大角度(60～75度)所拍摄的询问图像和较大大小的询问图像不发生错误检索。在表7中，还示出了最大数量的投票与第二最大数量的投票的平均比(投票数量的比)。
在成功检索中，最大数量的投票是大于第二最大数量的投票7倍。另一方面，在失败检索中，最大数量的投票仅稍稍大于第二最高投票计数。参考投票计数的比，可以预测是否检索正确图像。通过为该比适当设置阈值，可以消除处理错误。在上述情况下，通过设置阈值将处理精度增大至75％，从而消除所有错误。
设备的示例结构
将给出对于用于将文档和/或图像存储在文档和/或图像数据库中的本发明的文档和/或图像存储设备的示例结构的说明。还给出对于用于从文档和/或图像数据库检索文档和/或图像的本发明的文档和/或图像检索设备的示例结构的说明，其中，在文档和/或图像数据库中，由文档和/或图像存储设备存储文档和/或图像。
图39是示出本发明的文档和/或图像存储设备1的结构的框图。文档和/或图像存储设备1包括输入部11、特征点提取部15、特征点选择部17和特征点存储部19。输入部11是输入将存储的文档和/或图像的部。特征点提取部15是从文档和/或图像提取定义图像配置的多个特征点的部。特征点选择部17是距离所提取的特征点p最近的n个特征点的部。特征点存储部19是这样的部：为从所选择的n个特征点所选择的m个点(m＜n)的所有可能的集合中的每一个，根据实施例1或实施例2中所述的存储处理，计算散列表的索引，并将输入的文档和/或图像存储在文档和/或图像数据库31中。
图40是示出本发明的文档和/或图像检索设备的结构的框图。检索设备3包括读取部21、特征点提取部23、特征点选择部25、投票部27和ID指定部29。读取部21是读取所拍摄的图像的部。特征点提取部23是从所读取的图像提取定义图像配置的多个特征点的部，并对应于图39中的特征点提取部15。特征点选择部25是选择距离所提取的特征点p中每一个最近的n个特征点的部，并对应于图39中的特征点选择部17。投票部27是根据实施例1或实施例2所述的检索处理对具有匹配特征量的文档ID投票的部。ID指定部29是基于为各特征点投票的计数指定与所拍摄的图像相对应的文档和/或图像的文档ID的部。
工业可应用性
与物理对象的链接
根据本发明的图像检索方法，可以在物理对象(文档、宣传册、海报或布告板)和电子数据(因特网的主页等相关信息)之间建立链接，从而可以基于物理对象的图像检索与物理对象相关的电子数据。在将报纸和杂志文章等文本媒体存储在因特网上的服务器中的情况下，例如，用户可以访问因特网上的服务器以仅通过拍摄任一介质的图像来获取相关数据。因此，本发明在检索文本介质的图像中非常有效。
本发明还适用于在广告宣传册和因特网上的主页之间建立链接的目录购物系统。而且，本发明可以用于基于通过拍摄海报所获得的图像检索与海报的内容相关的信息的应用、或者用于基于通过拍摄街道上的布告板所获得的图像检索与该布告板相关的信息的应用。而且，本发明还可以用于检索包括附加给地图信息(简明地图)的信息的电子数据作为相关信息的应用。
在该链接中，除文本信息和图形信息以外，相关信息还可以包括音频信息和视频信息。
可以由提供服务的供应商建立链接，或者由个人用户私人建立链接。在用户想要使数据和文档相关联的情况下，例如，本发明使用户通过使用照相机在电子数据和文档之间建立链接。
而且，本发明的实时处理能力(高速处理能力)使得可以以与通过照相机实时查看的物理对象(文档、宣传册或海报)的图像成重叠关系，显示电子数据。这是信息处理的一种形式，倍称为“智能信息透镜”。
物理对象之间的链接
如上所述，可以在物理对象和电子数据之间建立链接。根据本发明的图像检索方法，还可以考虑在物理对象之间建立链接。具体的例子如下：
(1)当有两个相关文档时，根据需要记录这两个文档的关联。
(2)根据需要与物理对象(文档、宣传册或海报)相关联记录人或物(产品等)(根据需要通过拍摄文档检索人或物的照片)。这类信息处理被当作为用于通过照片在物理对象之间建立链接的处理。
注解提取系统的应用
而且，本发明的图像检索方法可以用于将在文档中经常做出的注解包含进电子文档中。
图37是示出用于将在文档中做出的注解包含进电子文档中的系统的示例结构的说明图。如图37所示，该系统配置如下：
(1)将没有注解的文档作为原始文档存储在数据库中。
(2)利用照相机拍摄有注解的文档，并且通过本发明的方法从数据库检索没有注解的文档。结果，将没有注解的文档中的特征点与有注解的文档中的特征点相关联。
(3)基于特征点相互关系，将通过利用照相机拍摄有注解的文档所获得的图像恢复成正向(从倾斜拍摄状态到正向)。图38是用于解释将图像恢复成正向的处理的图。
(4)通过从正确取向的图像减去没有注解的文档的图像，提取注解的图像。
(5)通过将所提取的注解图像添加给电子文档，将注解包含在电子文档中。
这使得可以利用相互无缝链接的纸质文档和电子文档。
本发明的注解提取系统不仅可以链接到连结数字照相机，而且还可以连结到复印机或扫描器。由复印机或扫描器所捕获的图像经过相似变换和仿射变换等几何变换，而不是仅经过照相机所拍摄的图像的通常经受的投影变换。
因此，可以配置注解提取系统以使用相似不变量和仿射不变量。由于与投影变换相比，仿射变换和相似变换限制性更强，因而可以提高注解提取的精度。