本发明提供了一种基于图像内容的关键词搜索方法和装置。该关键词搜索装置在所输入的文档图像中搜索并定位所输入的关键词，该关键词搜索装置包括：整体匹配单元，该整体匹配单元从所述文档图像中提取多个候选关键词图像区域，提取所述多个候选关键词图像区域的图像特征，将所述图像特征与所述关键词的特征进行匹配，以获得与所述多个候选关键词图像区域相对应的匹配距离；校验单元，该校验单元对匹配距离小的前N个候选关键词图像区域进行识别，计算识别候选和所述关键词之间的校验距离；过滤单元，该过滤单元计算所述匹配距离和所述校验距离的组合距离，并根据该组合距离滤除组合距离大的候选关键词图像区域。
1.一种基于图像内容的关键词搜索装置，该关键词搜索装置在所输入的文档图像中搜索并定位所输入的关键词，该关键词搜索装置包括：整体匹配单元，该整体匹配单元从所述文档图像中提取多个候选关键词图像区域，提取所述多个候选关键词图像区域的图像特征，将所述图像特征与所述关键词的特征进行匹配，以获得与所述多个候选关键词图像区域相对应的匹配距离；
校验单元，该校验单元对匹配距离小的前N个候选关键词图像区域进行识别，计算识别候选和所述关键词之间的校验距离；
过滤单元，该过滤单元计算所述匹配距离和所述校验距离的组合距离，并根据该组合距离滤除组合距离大的候选关键词图像区域。
2.根据权利要求1所述的关键词搜索装置，其中，所述整体匹配单元包括：
连通域分析单元，该连通域分析单元对所述文档图像进行分析，以确定所述文档图像中的连通域；
候选区域提取单元，该候选区域提取单元根据所述连通域从所述文档图像中提取所述候选关键词图像区域；
特征提取单元，该特征提取单元从所述候选关键词图像区域中提取特征；
特征合成单元，该特征合成单元根据所述关键词中的各个字符来合成关键词的特征；
匹配单元，该匹配单元将所提取的所述候选关键词图像区域的特征与所述关键词的合成特征进行比较，以获得所述匹配距离。
3.根据权利要求2所述的关键词搜索装置，其中，所述候选关键词图像区域包含满足以下条件的相邻连通域：(1)连通域的数量在CCmin到CCmax之间，其中，CCmax表示最大连通域数量，其为所述关键词中的所有字符的左右结构的偏旁部首的数量之和加上一给定的正的常数，CCmin表示最小连通域数量，并且CCmin＝max (l/2，1)，即l/2与1中的最大值，l为所述关键词中的字符的数量；
(2)所述候选关键词图像区域的宽高比小于所有连通域的平均宽度和平均高度之比与kl的乘积，即其中，k为给定的正的常数，大于1，avewidth为所有连通域的平均宽度，aveheight为所有连通域的平均高度，Candi表示第i候选关键词图像区域，Width(Candi)和Height(Candi)分别表示第i候选关键词图像区域的宽度和高度。
4.根据权利要求2所述的关键词搜索装置，其中，所述候选区域提取单元包括：
单字识别单元，该单字识别单元对所述文档图像中的各个连通域进行识别；以及区域确定单元，该区域确定单元判断所述单字识别单元的识别结果中是否存在所述关键字中的字符，如果存在，则将与该识别结果相对应的连通域的前n1个连通域和后n2个连通域的合并区域作为所述候选关键词图像区域，其中，n1被分别设置为i-1、i、i+1，并且n2被分别设置为l-i-1、l-i、l-i+1，其中l为所述关键词中的字符的数量，i表示所述单字识别单元的识别结果中存在所述关键字中的第i个字符，并且当n1或n2的值＜1时，将n1或n2的值设置为1，而当n1或n2的值＞l时，将n1或n2的值设置为l。
5.根据权利要求2所述的关键词搜索装置，其中，所述整体匹配单元还包括单字特征库，该单字特征库中存储有字符特征，并且其中所述特征合成单元使用所述单字特征库中存储的字符特征来合成所述关键词的特征。
6.根据权利要求2所述的关键词搜索装置，其中，所述匹配单元将所述候选关键词图像区域和合成特征图像划分成多个网格，使每个网格中的前景色点的密度一致，并通过以下公式获得所述候选关键词图像区域和所述合成特征图像的匹配距离， Cost(Pi，...，i+h，Qj，...，j+k)＝||average(Pi，...，Pi+h)，average(Qj，...，Qj+k)||2Cdel(Pi，...，i+h)＝||average(Pi，...，Pi+h)||2Cdel(Qj，...，j+k)＝||average(Qj，...，Qj+k)||2
其中，N表示候选关键词图像区域的网格列的数量，M表示合成特征图像的网格列的数量，H(i，j)表示候选关键词图像区域的后i列网格与合成特征图像的后j列网格的匹配距离，Pi、Qj分别表示候选关键词图像区域的第i列网格和合成特征图像的第j列网格，||A，B||2表示向量A、B之间的欧氏距离，||A||2为||A，A||2的缩写，average(Pi，...，Pi+h)表示候选关键词图像区域的第i列至第i+h列网格列的特征的平均值，average(Qj，...，Qj+k)表示合成特征图像的第j列至第j+k列网格列的特征的平均值，Cost(Pi，...，i+h，Qj，...，j+k)表示候选关键词图像区域的第i列至第i+h列网格列的平均列与合成特征图像的第j列至第j+k列网格列的平均列之间的欧式距离，Cdel(Pi，...i+h)表示候选关键词图像区域的第i列至第i+h列网格列被认为是噪声网格列时被删除的代价，Cdel(Qj，...，j+k)表示合成特征图像的第j列至第j+k列网格列被认为是噪声网格列时被删除的代价。
7.根据权利要求1所述的关键词搜索装置，其中，所述校验单元包括：
候选字符区域获取单元，该候选字符区域获取单元对于每一个候选关键词图像区域，通过连通域分析来确定候选单一字符图像区域； 单字识别单元，该单字识别单元对由所述候选字符区域获取单元确定的每一个候选单一字符图像区域进行识别，对于每一个候选单一字符图像区域得到一系列识别候选，从而获得与所有候选单一字符图像区域相对应识别候选阵列；
编辑距离计算单元，该编辑距离计算单元计算所述识别候选阵列与所述关键词的编辑距离作为所述候选关键词图像区域的校验距离。
8.根据权利要求7所述的关键词搜索装置，其中，所述编辑距离计算单元通过以下公式计算所述编辑距离，其中，N为候选关键词图像区域的连通域的数量，M为关键词中的字符的数量，E(N，M)表示编辑距离，Ci(i＝1，...，N)、Kj(j＝1，...，M)分别表示第i个连通域和关键词中的第j个字符，Ci，...，i+h表示第i至第i+h个连通域的组合，Cdel表示一个连通域被认为是噪声连通域时被删除的代价，其为正常数，Cost(Ci，...，i+h，Kj)表示将第i个至第i+h个连通域的组合区域识别为Kj的代价，其可以通过以下公式获得，其中，W表示候选单一字符图像区域， 表示如果Kj出现在W的识别候选中，
则Kj在W的识别候选列表中按匹配距离由小到大排列的位置，MaxCand表示最大的识别候选数，Wk表示W的第k个识别候选。
9.根据权利要求1所述的关键词搜索装置，其中，所述过滤单元通过以下公式计算所述组合距离，Costcom(i)＝α*Ei/l+(1-α)*(Hi-H0)/H0
其中，Costcom(i)为组合距离，α为0到1之间的正的常数，Hj(i＝0，1…，m-1)为所述整体匹配单元计算的匹配距离，并且按匹配距离的大小进行排列，即，如果i＞j，则Hi＞Hj，Ei(i＝0，1…，m-1)为所述校验单元计算的校验距离，l为关键词中的字符的数量，m为候选关键词图像 区域的数量。
10.根据权利要求1所述的关键词搜索装置，该关键词搜索装置还包括单字识别单元，并且其中，所述校验单元通过所述单字识别单元对所述候选关键词图像区域进行识别。
11.根据权利要求2所述的关键词搜索装置，其中，该关键词搜索装置还包括单字识别单元，并且其中，所述候选区域提取单元通过该单字识别单元对所述文档图像中的各个连通域进行识别，并且所述候选区域提取单元包括：
区域确定单元，该区域确定单元判断所述单字识别单元的识别结果中是否存在所述关键字中的字符，如果存在，则将与该识别结果相对应的连通域的前n1个连通域和后n2个连通域的合并区域作为所述候选关键词图像区域，其中，n1被分别设置为i-1、i、i+1，并且n2被分别设置为l-i-1、l-i、l-i+1，其中l为所述关键词中的字符的数量，i表示所述单字识别单元的识别结果中存在所述关键字中的第i个字符，并且当n1或n2的值＜1时，将n1或n2的值设置为1，而当n1或n2的值＞l时，将n1或n2的值设置为l。
12.一种基于图像内容的关键词搜索方法，该关键词搜索方法在所输入的文档图像中搜索并定位所输入的关键词，该关键词搜索方法包括以下步骤：整体匹配步骤，从所述文档图像中提取多个候选关键词图像区域，提取所述多个候选关键词图像区域的图像特征，将所述图像特征与所述关键词的特征进行匹配，以获得与所述多个候选关键词图像区域相对应的匹配距离；
校验步骤，对匹配距离小的前N个候选关键词图像区域进行识别，计算识别候选和所述关键词之间的校验距离；
过滤步骤，计算所述匹配距离和所述校验距离的组合距离，并根据该组合距离滤除组合距离大的候选关键词图像区域。
13.根据权利要求12所述的关键词搜索方法，其中，所述整体匹配步骤包括以下步骤： 连通域分析步骤，对所述文档图像进行分析，以确定所述文档图像中的连通域；
候选区域提取步骤，根据所述连通域从所述文档图像中提取所述候选关键词图像区域；
特征提取步骤，从所述候选关键词图像区域中提取特征；
特征合成步骤，根据所述关键词中的各个字符来合成关键词的特征；
匹配步骤，将所提取的所述候选关键词图像区域的特征与所述关键词的合成特征进行比较，以获得所述匹配距离。
14.根据权利要求13所述的关键词搜索方法，其中，所述候选关键词图像区域包含满足以下条件的相邻连通域：(1)连通域的数量在CCmin到CCmax之间，其中，CCmax表示最大连通域数量，其为所述关键词中的所有字符的左右结构的偏旁部首的数量之和加上一给定的正的常数，CCmin表示最小连通域数量，并且CCmin＝max(l/2，1)，即l/2与1中的最大值，l为所述关键词中的字符的数量；
(2)所述候选关键词图像区域的宽高比小于所有连通域的平均宽度和平均高度之比与kl的乘积，即其中，k为给定的正的常数，大于1，avewidth为所有连通域的平均宽度，aveheieht为所有连通域的平均高度，Candi表示第i候选关键词图像区域，Width(Candi)和Height(Candi)分别表示第i候选关键词图像区域的宽度和高度。
15.根据权利要求13所述的关键词搜索方法，其中，所述候选区域提取步骤包括以下步骤：
单字识别步骤，对所述文档图像中的各个连通域进行识别；以及
区域确定步骤，判断所述单字识别单元的识别结果中是否存在所述关键字中的字符，如果存在，则将与该识别结果相对应的连通域的前n1个连通域和后n2个连通域的合并区域作为所述候选关键词图像区域，其中，n1被分别设置为i-1、i、i+1，并且n2被分别设置为l-i-1、l-i、l-i+1，其中l为所述关键词中的字符的数量，i表示所述单字识别单元的 识别结果中存在所述关键字中的第i个字符，并且当n1或n2的值＜1时，将n1或n2的值设置为1，而当n1或n2的值＞l时，将n1或n2的值设置为l。
16.根据权利要求13所述的关键词搜索方法，其中，所述特征合成步骤使用存储在单字特征库中的字符特征来合成所述关键词的特征。
17.根据权利要求13所述的关键词搜索方法，其中，所述匹配步骤将所述候选关键词图像区域和合成特征图像划分成多个网格，使每个网格中的前景色点的密度一致，并通过以下公式获得所述候选关键词图像区域和所述合成特征图像的匹配距离，Cost(Pi，...，i+h，Qj，...，j+k)＝||average(Pi，...，Pi+h)，average(Qj，...，Qj+k)||2Cdel(Pi，...，i+h)＝||average(Pi，...，Pi+h)||2Cdel(Qj，...，j+k)＝||average(Qj，...，Qj+k)||2
其中，N表示候选关键词图像区域的网格列的数量，M表示合成特征图像的网格列的数量，H(i，j)表示候选关键词图像区域的后i列网格与合成特征图像的后j列网格的匹配距离，Pi、Qj分别表示候选关键词图像区域的第i列网格和合成特征图像的第j列网格，||A，B||2表示向量A、B之间的欧氏距离，||A||2为||A，A||2的缩写，average(Pi，...，Pi+h)表示候选关键词图像区域的第i列至第i+h列网格列的特征的平均值，average(Qj，...，Qj+k)表示合成特征图像的第j列至第j+k列网格列的特征的平均值，Cost(Pi，...，i+h，Qj，...，j+k)表示候选关键词图像区域的第i列至第i+h列网格列的平均列与合成特征图 像的第j列至第j+k列网格列的平均列之间的欧式距离，Cdel(Pi，...，i+h)表示候选关键词图像区域的第i列至第i+h列网格列被认为是噪声网格列时被删除的代价，Cdel(Qj，...，j+k)表示合成特征图像的第j列至第j+k列网格列被认为是噪声网格列时被删除的代价。
18.根据权利要求12所述的关键词搜索方法，其中，所述校验步骤包括以下步骤：
候选字符区域获取步骤，对于每一个候选关键词图像区域，通过连通域分析来确定候选单一字符图像区域；
单字识别步骤，对由所述候选字符区域获取单元确定的每一个候选单一字符图像区域进行识别，对于每一个候选单一字符图像区域得到一系列识别候选，从而获得与所有候选单一字符图像区域相对应识别候选阵列；
编辑距离计算步骤，计算所述识别候选阵列与所述关键词的编辑距离作为所述候选关键词图像区域的校验距离。
19.根据权利要求18所述的关键词搜索方法，其中，所述编辑距离计算步骤通过以下公式计算所述编辑距离，其中，N为候选关键词图像区域的连通域的数量，M为关键词中的字符的数量，E(N，M)表示编辑距离，Ci(i＝1，...，N)、Kj(j＝1，...，M)分别表示第i个连通域和关键词中的第j个字符，Ci，...，i+h表示第i至第i+h个连通域的组合，Cdel表示一个连通域被认为是噪声连通域时被删除的代价，其为正常数，Cost(Ci，...，i+h，Kj)表示将第i个至第i+h个连通域的组合区域识别为Kj的代价，其可以通过以下公式获得，其中，W表示候选单一字符图像区域， 表示如果Kj出现在W的识别候选中，
则Kj在W的识别候选列表中按匹配距离由小到大排列的位 置，MaxCand表示最大的识别候选数，Wk表示W的第k个识别候选。
20.根据权利要求12所述的关键词搜索方法，其中，所述过滤步骤通过以下公式计算所述组合距离，Costcom(i)＝α*Ei/l+(1-α)*(Hi-H0)/H0
其中，α为0到1之间的正的常数，Hi(i＝0，1…，m-1)为所述整体匹配单元计算的匹配距离，并且按匹配距离的大小进行排列，即，如果i＞j，则Hi＞Hj，Ei(i＝0，1…，m-1)为所述校验单元计算的校验距离，l为关键词中的字符的数量，m为候选关键词图像区域的数量。
基于图像内容的关键词搜索方法和装置
技术领域
[0001] 本发明涉及一种快速并准确地从文档图像中搜索和定位关键词的装置和方法。更具体地说，涉及用于在用户输入了感兴趣的关键词(例如，“北京”等)时从文档图像中自动、准确地搜索并定位关键词的位置的装置和方法。
背景技术
[0002] 传统的在文档图像中定位关键词的方法通常是利用OCR(光学字符识别，Optical Character Recognition)技术来实现的。在传统的定位关键词的方法中，首先对文档图像进行分割，然后对分割出来的单一字符区域进行识别，将文档图像转换为文本，并且在识别出的文本中搜索关键词以进行定位。例如，在美国专利申请US 6470336中公开了这种传统的在文档图像中定位关键词的装置和方法。
[0003] 图1示出了基于OCR技术的传统装置的基本结构及操作流程的方框图。
[0004] 如图1所示，传统装置包括图像分割单元101、单字识别单元102以及结果搜索单元103。首先，图像分割单元101对所输入的文档图像进行版面分析和图像分割，以获得一系列的单一字符的图像区域。随后，单字识别单元102利用OCR技术对通过图像分割单元101获得的单一字符的图像区域进行识别，以获得各个图像区域的识别结果。结果搜索单元103在通过单字识别单元102获得的识别结果中搜索关键词，以确定关键词是否在识别结果中出现。如果出现则返回关键词的出现位置，并输出搜索定位的结果。
[0005] 这种传统的方法存在很多问题。首先，图像分割单元101很难准确地对所输入的文档图像进行分割。尤其是在手写文档图像的情况下，由于手写体字符本身存在笔画粘连，不同的人的书写风格也不一致，并且手写体字符没有固定的大小，因此很难界定单一字符区域，从而从手写文档图像中分割出单一字符的图像区域非常困难，这极大地影响了后续的单字识别的精度，传统OCR技术很难处理手写文档也主要是因为这个原因。其次，将所有的字符图像区域识别成单一字符的方法非常耗时。对于大字符集合(例如亚洲国家的语言，包括汉字、日文等)，字符的种类通常很多，例如汉字，一级汉字和二级汉字一共有6063种。对这种大类别的识别问题，由于字符的种类繁多，并且近似字符也很多，导致精度降低(尤其是对于手写体识别)。同时，由于需要对每个字符图像区域进行识别，导致识别速度进一步下降，从而使得系统的识别效果不是很好。
[0006] 另外，传统方法中还存在利用隐马尔科夫模型来自动分割文档图像并定位关键词的方法，例如美国专利申请US 5745600和US 5592568中所公开的方法。但是这些传统方法缺乏有效的校验措施，从而使得整体识别率较低。
发明内容
[0007] 鉴于上述传统技术中的问题而提出本发明。本发明的一个目的是提供一种高精度的基于图像内容的关键词搜索方法和装置。
[0008] 本发明的另一目的是提供一种快速的基于图像内容的关键词搜索方法和装置。
[0009] 为了实现本发明的目的，本发明提供了一种利用整体匹配技术来选择候选关键词图像区域并利用单一字符识别作为校验的方法。
[0010] 根据本发明的一个方面，本发明提供了一种基于图像内容的关键词搜索装置，该关键词搜索装置在所输入的文档图像中搜索并定位所输入的关键词，该关键词搜索装置包括：整体匹配单元，该整体匹配单元从所述文档图像中提取多个候选关键词图像区域，提取所述多个候选关键词图像区域的图像特征，将所述图像特征与所述关键词的特征进行匹配，以获得与所述多个候选关键词图像区域相对应的匹配距离；校验单元，该校验单元对匹配距离小的前N个候选关键词图像区域进行识别，计算识别候选和所述关键词之间的校验距离；过滤单元，该过滤单元计算所述匹配距离和所述校验距离的组合距离，并根据该组合距离滤除组合距离大的候选关键词图像区域。
[0011] 根据本发明的另一方面，在根据本发明的关键词搜索装置中，所述整体匹配单元包括：连通域分析单元，该连通域分析单元对所述文档图像进行分析，以确定所述文档图像中的连通域；候选区域提取单元，该候选区域提取单元根据所述连通域从所述文档图像中提取所述关键词候选图像区域；特征提取单元，该特征提取单元从所述关键词候选图像区域中提取特征；特征合成单元，该特征合成单元根据所述关键词中的各个字符来合成关键词的特征；匹配单元，该匹配单元将所提取的所述关键词候选图像区域的特征与所述关键词的合成特征进行比较，以获得所述匹配距离。
[0012] 根据本发明的另一方面，在根据本发明的关键词搜索装置中，所述校验单元包括：候选字符区域获取单元，该候选字符区域获取单元对于每一个候选关键词图像区域，通过连通域分析来确定候选单一字符图像区域；单字识别单元，该单字识别单元对由所述候选字符区域获取单元确定的每一个候选单一字符图像区域进行识别，对于每一个候选单一字符图像区域得到一系列识别候选，从而获得与所有候选单一字符图像区域相对应识别候选阵列；编辑距离计算单元，该编辑距离计算单元计算所述识别候选阵列与所述关键词的编辑距离作为所述候选关键词图像区域的校验距离。
[0013] 根据本发明的另一方面，本发明还提供了一种基于图像内容的关键词搜索方法，该关键词搜索方法在所输入的文档图像中搜索并定位所输入的关键词，该关键词搜索方法包括以下步骤：整体匹配步骤，从所述文档图像中提取多个候选关键词图像区域，提取所述多个候选关键词图像区域的图像特征，将所述图像特征与所述关键词的特征进行匹配，以获得与所述多个候选关键词图像区域相对应的匹配距离；校验步骤，对匹配距离小的前N个候选关键词图像区域进行识别，计算识别候选和所述关键词之间的校验距离；过滤步骤，计算所述匹配距离和所述校验距离的组合距离，并根据该组合距离滤除组合距离大的候选关键词图像区域。
[0014] 本发明的关键词搜索方法不对文档图像进行切分，而是利用连通域分析提取初步的候选关键词图像区域，并直接从候选关键词图像区域提取特征，然后与关键词的合成特征进行整体匹配，并对所有的候选关键词图像区域的匹配结果按照匹配距离由小到大进行排序，取前N个候选关键词图像区域作为候选关键词图像区域。本发明的方法不需对文档图像进行切分，从而避免了传统方法中的切分错误。另外，采用整体匹配的方法，而不是利用识别技术对每一个字符区域进行识别，将大类别的识别问题变成了简单的匹配问题，从而能够极大地提高处理的精度和速度。
[0015] 此外，本发明的关键词搜索方法在利用整体匹配方法得到候选关键词图像区域之后，利用单字识别技术对候选关键词图像区域进行校验。仅对数量极少的候选关键词图像区域进行校验，避免了对整个图像的切分识别，从而减少了切分错误的发生，并且极大地提高了处理的速度。
[0016] 此外，本发明的关键词搜索方法在整体匹配中，利用了动态规划的方法来匹配从图像中提取的特征和关键词的合成特征，从而保证了整体识别的效果，提高了处理的精度。
[0017] 此外，本发明的关键词搜索方法在利用单字识别技术对候选关键词图像区域进行校验的过程中，计算候选关键词图像区域的识别候选与关键词之间的编辑距离，有效地获得了校验距离，从而能够准确而快速地获得正确的关键词，因此极大地提高了处理的精度和速度。
[0018] 此外，本发明的关键词搜索方法在获得整体匹配的匹配距离和利用单字识别的校验距离之后，组合这两种距离，以获得组合距离。
[0019] 应当理解，以上总体说明和以下详细说明都是说明性和示例性的，并旨在提供对所要求的本发明的进一步说明。
附图说明
[0020] 所包含的附图用于提供对本发明的进一步理解，其被并入说明书并构成说明书的一部分，附图说明了本发明的实施方式，并与说明书一起用于解释本发明的原理。
[0021] 图1是基于OCR技术的传统装置的基本结构及操作流程的方框图；
[0022] 图2是根据本发明实施方式的关键词搜索装置的总体结构的方框图；
[0023] 图3是根据本发明实施方式的关键词搜索方法的总体流程图；
[0024] 图4是根据本发明实施方式的整体匹配单元的方框图；
[0025] 图5是根据本发明实施方式的候选区域提取单元的方框图；
[0026] 图6是根据本发明的文档图像特征与合成特征的匹配方法的示意图；
[0027] 图7是根据本发明实施方式的校验单元的方框图；
[0028] 图8是根据本发明实施方式的候选字符区域获取方法的示意图。
具体实施方式
[0029] 下面将参照附图详细说明根据本发明实施方式的关键词搜索方法和装置。
[0030] 参照图2和图3描述根据本发明实施方式的关键词搜索装置的总体结构和操作流程。
[0031] 图2是根据本发明实施方式的关键词搜索装置的总体结构的方框图。图3是根据本发明实施方式的关键词搜索方法的总体流程图。
[0032] 如图2所示，根据本发明的关键词搜索装置包括整体匹配单元201、校验单元202、过滤单元204。
[0033] 如图3所示，向整体匹配单元201输入文档图像和关键词(步骤S1)，整体匹配单元201根据所输入的文档图像和关键词来计算匹配距离，具体地说，整体匹配单元201从文档图像中提取候选关键词图像区域(步骤S2)，并提取这些候选关键词图像区域的图像特征(步骤S3)，与所输入的关键词的特征进行整体匹配，得到一系列的匹配距离，按由小到大顺序对所得到的匹配距离进行排列并输出(步骤S4)。校验单元202对匹配距离小的前N个关键词区域进行识别(步骤S5)，并计算识别候选和关键词之间的校验距离(步骤S6)。过滤单元204利用整体匹配单元201输出的匹配距离和校验单元202输出的校验距离，通过线性组合，计算出组合距离(步骤S7)，并根据该组合距离滤除组合距离较大的候选关键词区域(步骤S8)，最终输出搜索结果(步骤S9)。
[0034] 下面将详细说明根据本发明实施方式的关键词搜索装置的各个单元的具体结构和操作。
[0035] 首先，将参照图4对根据本发明实施方式的整体匹配单元201进行详细说明。
[0036] 图4是根据本发明实施方式的整体匹配单元201的方框图。
[0037] 如图4所示，整体匹配单元201包括连通域分析单元301、候选区域提取单元302、特征提取单元304、特征合成单元305、匹配单元307。此外，整体匹配单元201还包括单字特征库306。
[0038] 连通域分析单元301对所输入的文档图像进行分析，以确定文档图像中的连通域，连通域是图像前景色(通常为黑色)像素点的集合，在该集合中，任何两个像素点都能通过该集合内的像素点相连通。候选区域提取单元302根据连通域从所输入的文档图像中提取关键词候选图像区域。特征提取单元304从关键词候选图像区域中直接提取出特征(例如外围轮廓特征、或轮廓方向特征等，参见Q.D.Trier，A.K.Jain and T.Taxt，“Feature Extraction Methods for Character Recognition-a Survey”，Pattern Recognition，Vol.29，No.4，pp.641-662，1996以及F.Kimura，T.Wakabayashi，S.Tsuruoka and Y.Miyake，“Improvement of HandwrittenJapanese Character Recognition Using Weighted Direction Code Histogram”，Pattern Recognition，Vol.30，No.8，pp.1329-1337，1997)。特征合成单元305根据所输入的关键词中的各个字符，利用单字特征库306中所存储的相应字符特征来合成关键词的特征。匹配单元307通过将通过特征提取单元304提取的特征与通过特征合成单元305合成的关键词的合成特征进行比较，得到各个候选关键词图像区域的匹配距离，根据匹配距离的大小对这些匹配距离进行排序并输出。
[0039] 具体地说，连通域分析单元301通过连通域检测算法(参见Hypermedia Image Processing Reference，Bob Fisher，Simon Perkins，AshleyWalker and Erik Wolfart Department of Artificial Intelligence University ofEdinburgh，UK.http://homepages.inf.ed.ac.uk/rbf/HIPR2/)，标识出所输入的文档图像中的所有连通域，并根据标识出的连通域的大小、位置及其与相邻连通域之间的距离等信息，将相应的连通域合并为新的连通域。例如，假设所输入的文档图像为横向书写的文档图像，则当连通域A在连通域B上方时，连通域B和A应该属于同一字符，因此应当将连通域B和A合并为一新的连通域。具体地，连通域的合并可以参见美国专利申请US 6,535,619B1中的图11A、11B、11C及其说明。
[0040] 候选区域提取单元302从连通域分析单元301输出的连通域中提取关键词候选图像区域。
[0041] 在根据本发明的一个实施方式中，候选区域提取单元302通过以下的方法从连通域中提取关键词候选图像区域。
[0042] 在该实施方式中，候选区域提取单元302根据所输入的关键词中的字符的数量l，分析候选关键词图像区域中可能含有的最小连通域数量CCmin和最大连通域数量CCmax(确定CCmin和CCmax的方法将在后面进行说明)，并且将满足下列条件的相邻连通域的图像区域的组合判定为候选关键词图像区域：
[0043] (1)在该组合中，连通域的数量在CCmin到CCmax之间。
[0044] (2)该候选关键词图像区域的宽高比小于所有连通域的平均宽度和平均高度之比与kl的乘积，即：
[0045]
[0046] 其中，k为给定的正的常数，通常大于1，avewidth为所有连通域的平均宽度，aveheight为所有连通域的平均高度，Candi表示第i候选关键词图像区域，Width(Candi)和Height(Candi)分别表示第i候选关键词图像区域的宽度和高度。式(1)表示连通域的组合宽高比不能超过平均宽高比与关键词的长度的乘积太多。
[0047] 通过以下的方法来确定最小连通域数量CCmin和最大连通域数量CCmax。
[0048] 最大连通域数量CCmax为关键词中的所有字符的左右结构的偏旁部首的数量之和加上一个正的常数，该常数可以通过实验来确定，例如可以为l/2。
[0049] 最小连通域数量CCmin＝max(l/2，1)，即，l/2与1中的最大值。
[0050] 例如，当所输入的关键词为“北京”时，该关键词中的字符的数量l为2，关键词“北京”中的所有的左右结构的偏旁部首的数量为2(北)+1(京)＝3，然后将该数量加上l/2，得到最大连通域数量CCmax＝4。此外，最小连通域数量CCmin＝max(l/2，1)＝1。
[0051] 通过使用上述条件(1)和(2)来限定候选关键词图像区域，降低了需要检查和匹配的候选关键词图像区域的数量，从而可以极大地提高关键词搜索的处理速度。
[0052] 该实施方式的候选区域提取方法直接利用了连通域分析和关键词的偏旁部首分析，适合于只有少量关键词的检索的应用。
[0053] 当输入多关键词时，使用该实施方式的候选区域提取方法，候选关键词图像区域的数量会非常多。
[0054] 因此，本发明的另一实施方式使用了具有以下结构的候选区域提取单元302。
[0055] 图5示出了该候选区域提取单元302的方框图。
[0056] 如图5所示，该候选区域提取单元302包括单字识别单元302A和区域确定单元302B。单字识别单元302A对所输入的文档图像的各个连通域进行识别，并利用动态规划方法找出匹配距离最小的识别结果(参见R.G.Casey and E.Lecolinet.A Survey of Methods and Strategies inCharacter Segmentation.IEEE Trans.Pattern Analysis and MachineIntelligence.Vol 18，No 7，July 1996，PP.690-706)。然后，候选区域确定单元
302B判断单字识别单元302A的识别结果是否存在关键词中的字符，如果存在，则将在该单字区域前n1个字符区域和后n2个字符区域的合并区域作为候选关键词图像区域。
[0057] 其中，通过以下的过程来确定n1和n2。
[0058] 假设关键词中含有l个字符，并且第i个字符存在于所输入的文档图像的某一字符图像区域的单字识别候选中，则n1分别被设置为i-1、i、i+1，n2分别被设置为l-i-1、l-i、l-i+1。因此，候选关键词图像区域为最多9(3×3)个可能区域，分别对应于前n1和后n2个单字区域的9种合并区域。
[0059] 注意，在上面的过程中，当n1、n2的某些取值＜1时，则将其设置为1，而当取值＞l时，则将其设置为l。
[0060] 在该实施方式的候选区域提取单元302中，提前进行单字识别，利用与关键词中的字符和识别结果相关的信息，可以有效地减少候选关键词图像区域的数量。
[0061] 在候选区域提取单元302提取了候选关键词图像区域之后，特征提取单元304从候选关键词图像区域直接提取特征。由特征提取单元304进行的操作通常包括图像归一化处理和特征提取处理。在现有技术中，图像归一化存在很多种方法，例如在题为“Handwritten digit normalizationmethod(手写数字归一化方法)”的美国专利申请US5325447中所述的方法。特征提取单元304通过图像归一化处理将候选关键词图像区域归一化为指定宽度的图像，然后从归一化后的图像中提取特征，提取特征的方法也有很多，例如外围轮廓特征、轮廓方向特征等。
[0062] 特征提取单元304将所提取的特征输出到匹配单元307。
[0063] 此外，特征合成单元305根据所输入的关键词中所包含的各个字符，利用单字特征库306中所存储的相应字符特征，来合成关键词的特征。具体的合成方法也有很多，例如参见日本专利“特许第3879341号”和“特开平11-161740”中所公开的方法，或者通过直接排列各个字符特征来获得新的特征。
[0064] 特征合成单元305将所合成的关键词特征输出到匹配单元307。
[0065] 匹配单元307利用动态规划的方法，来计算特征提取单元304在候选关键词图像区域中提取的特征与特征合成单元305合成的关键词特征之间的匹配距离，以确定候选关键词图像区域与所输入的关键词之间的近似度，并对所有的关键词候选图像区域进行排序并输出。
[0066] 将参照图6对具体的匹配方法进行说明。图6是根据本发明的文档图像特征与合成特征的匹配方法的示意图。
[0067] 在图6中，假设所输入的关键词是“蔡斯家”。并且图6中的(a)为从候选关键词图像区域中提取的特征的示意图，图6中的(b)为合成特征的示意图。图6中的(c)可理解为单字特征库306中所存储的与关键词中的各个字符相对应的各个字符特征，即，图6中的(b)是由图6中的(c)合成的。
[0068] 为了清楚地说明匹配过程，采用根据线密度(参见F.Kimura，T.Wakabayashi，S.Tsuruoka and Y.Miyake，“Improvement of HandwrittenJapanese CharacterRecognition Using Weighted Direction Code Histogram”，Pattern Recognition，Vol.30，No.8，pp.1329-1337，1997以及H.Yamada，K.Yamamoto and T.Saito，“A Nonlinear Normalization Method for HandprintedKanji Character Recognition-Line Density Equalization”，PatternRecognition Vol.23，Nno.9，pp.1023-1029，1990)的方法来划分网格，以提取特征。即，根据线密度将图像划分为一定数量的网格，保证每个网格中的黑色点(前景色点)的密度一致。然后在每个网格中提取特征。为了使问题简化，假设候选关键字图像区域和合成特征图像被归一化为相同的高度L。匹配两个图像的问题实际上被转换成如何对应候选关键字图像区域和合成特征图像的每一个网格列的问题。由于两个图像之间可能存在比例拉伸，同时还可能存在一些噪声，所以各个网格列可能是噪声列，或者对应于另一图像中的多个网格列。两个图像的直接匹配问题实际上可以转换为一个动态规划的问题(参见E.Ukkonen，″OnApproximate String Matching″，Foundations of Computation Theory，1983，LNCS Vol.158，pp.487-495以及Needleman，S.B.& Wunsch，C.D.，“Ageneral method applicable to the search for similarities in the amino acidsequence of two proteins”，J.Mol.Biol.48，443-453，1970)。
[0069] 将两个图像的匹配距离定义为匹配代价H(N，M)(其中，N表示候选关键字图像区域的网格列的数量，M表示合成特征图像的网格列的数量)，则H(N，M)可以由以下的递归公式给出：
[0070]
[0071] Cost(Pi，...，i+h，Qj，...，j+k)＝‖average(Pi，...，Pi+h)，average(Qj，...，Qj+k)‖2[0072] Cdel(Pi，...i+h)＝‖average(Pi，...，Pi+h)‖2
[0073] Cdel(Qj，...，j+k)＝‖average(Qj，...，Qj+k)‖2
[0074] 在上面的公式中，H(i，j)表示候选关键字图像区域的后i列网格与合成特征图像的后j列网格的匹配距离。Pi、Qj分别表示候选关键字图像区域的第i列网格和合成特征图像的第j列网格。‖A，B‖2表示向量A、B之间的欧氏距离，‖A‖2为‖A，A‖2的缩写。average(Pi，...，Pi+h)表示候选关键字图像区域的第i列至第i+h列网格列的特征的平均值，average(Qj，...，Qj+k)表示合成特征图像的第j列至第j+k列网格列的特征的平均值，Cost(Pi，...i+h，Qj，...，j+k)表示候选关键字图像区域的第i列至第i+h列网格列的平均列与合成特征图像的第j列至第j+k列网格列的平均列之间的欧式距离，Cdel(Pi，...，i+h)表示候选关键字图像区域的第i列至第i+h列网格列被认为是噪声网格列时被删除的代价，Cdel(Qj，...，j+k)表示合成特征图像的第j列至第j+k列网格列被认为是噪声网格列时被删除的代价。
[0075] 在上面的公式中，限定一个图像的一列网格列与另一图像的网格列之间的匹配最多存在以下4种情况：
[0076] (1)该图像的该网格列与另一图像的一列网格列匹配；
[0077] (2)该图像的该网格列与另一图像的两列相邻的网格列匹配；
[0078] (3)该图像的该网格列与另一图像的三列相邻的网格列匹配；
[0079] (4)该图像的该网格列为噪声；
[0080] a)该网格列为噪声；
[0081] b)该网格列与下一相邻的网格列为噪声；
[0082] c)该网格列与下两列相邻的网格列为噪声。
[0083] 在以上公式中，公式(2)对应于(1)的情况；公式(3)(8)对应于(2)的情况；公式(4)(9)对应于(3)的情况；公式(5)(10)对应于(4)a)的情况；公式(6)(11)对应于(4)b)的情况；公式(7)(12)对应于(4)c)的情况。
[0084] 通过如上定义的匹配代价H(N，M)，可以利用动态规划的方法得到两个图像(或特征)之间的匹配距离。
[0085] 应当注意的是，上面的匹配过程可以很容易地被扩展为一个图像的每一网格列与另一图像的三列以上的相邻网格列的匹配情况。
[0086] 接下来，将参照图7说明根据本发明的关键词搜索装置的校验单元202的基本结构和操作。
[0087] 图7是根据本发明实施方式的校验单元202的方框图。
[0088] 如图7所示，校验单元202包括候选字符区域获取单元401、单字识别单元402以及编辑距离计算单元403。
[0089] 在图7中，候选字符区域获取单元401对于每一个候选关键词图像区域，利用连通域分析来确定候选单一字符图像区域。单字识别单元402利用单字识别引擎来识别由候选字符区域获取单元401确定的每一个候选单一字符图像区域，对于每一个候选单一字符图像区域得到一系列识别候选，因此所有的候选单一字符图像区域的识别候选构成了一个识别候选阵列。编辑距离计算单元403计算该识别候选阵列与关键词的编辑距离，并输出该编辑距离作为该候选关键词图像区域的校验距离。
[0090] 具体地说，候选字符区域获取单元401判断每一个连通域、每相邻的两个连通域、每相邻的三个连通域是否为候选字符图像区域。
[0091] 图8中的(a)-(d)示出了候选字符区域获取单元401进行的处理的示例。图8是根据本发明实施方式的候选字符区域获取方法的示意图。在图8中，假设所输入的候选关键词图像区域为“河北”。如图8中的(a)所示，首先从图像中得到连通域A、B、C、D。其中A由两个连通域合并而成。连通域的合并可以参见美国专利申请US 6,535,619B1中的图11A、11B、11C及其说明。考虑到汉字字符在横向上最多仅可以有三个独立结构，例如“树”由“木”、“又”、“寸”三个独立结构组成。如图8的(b)所示，相邻的两个连通域被组合作为候选单一字符图像区域，即，AB、BC、CD；如图8的(c)所示，相邻的三个连通域也被组合作为候选单一字符图像区域，即，ABC、BCD。
[0092] 在上面的连通域组合过程中，当组合后的连通域的宽度大于某一给定阈值Thc时，则不进行连通域的组合。如图8的(d)所示，ABC、BCD的宽度大于Thc，即Width(ABC)＞Thc，Width(BCD)＞Thc，则ABC、BCD不被判定为候选单一字符图像区域。因此，最终的候选单一字符图像区域为A、B、C、D、AB、BC和CD。
[0093] 单字识别单元402识别所有的候选单一字符图像区域。对每一个候选单一字符图像区域得到一识别候选列表。图8的(e)示出了所有候选单一字符图像区域A、B、C、D、AB、BC、CD的识别候选阵列。每一个识别候选旁边的数字代表该候选单一字符图像区域被识别为该识别候选的匹配距离。因为ABC、BCD不是候选单一字符图像区域，所以不对它们进行识别。
[0094] 编辑距离计算单元403利用动态规划的方法来计算通过单字识别单元402得到的候选识别结果阵列与关键词之间的最佳匹配路径，并输出匹配代价(即，编辑距离)作为校验距离。
[0095] 下面详细介绍编辑距离计算单元403进行的具体搜索操作。
[0096] 将所有候选单一字符图像区域的识别候选阵列定义为G，所输入的关键词为K，并且假设候选关键词的连通域的数量为N，关键词K中的字符的数量为M，则计算候选识别结果阵列与关键词之间的最佳匹配路径可以转换为计算最小代价E(N，M)，最小代价E(N，M)定义如下：
[0097]
[0098] 其中，Ci(i＝1，...，N)，Kj(j＝1，...，M)分别表示第i个连通域和K中的第j个字符。Ci，...，i+h表示第i个至第i+h个连通域的组合，例如图7中的AB，BC等。Cdel表示一个连通域被认为是噪声连通域，从而被删除的代价，可以将其设置为一个正常数，例如1。Cost(Ci，...，i+h，Kj)表示将第i个至第i+h个连通域的组合区域识别为Kj的代价。各个候选单一字符图像区域W与Kj的匹配代价被定义如下：
[0099]
[0100] 其中rankwi(kj)表示如果Kj出现在W的识别候选中，则Kj在W的识别候选列表中按匹配距离由小到大排列的位置。MaxCand表示最大的识别候选数。Wk表示W的第k个识别候选。
[0101] 通过定义匹配代价E(N，M)，上面的处理实际上被转换成典型的递归动态归化问题，因此可以有效地解决该问题。
[0102] 如图1所示，由整体匹配单元201计算的匹配距离以及由校验单元202计算的校验距离被输入到过滤单元204。
[0103] 假设存在m个候选关键词图像区域，由整体匹配单元201计算的每一个候选关键词图像区域的整体匹配距离为Hi，(i＝0，1…，m-1)，并且按整体匹配距离的大小进行排列，即，如果i＞j，则Hi＞Hj。由校验单元202计算出的校验距离为Ei，(i＝0，1…，m-1)，所输入的关键词的长度为l，则由过滤单元204计算的组合距离可以被定义为：
[0104] Costcom(i)＝α*Ei/l+(1-α)*(Hi-H0)/H0 (15)[0105] 其中，α为0到1之间的正的常数，其具体数值可以实验来确定。
[0106] 在计算出每一个候选关键词图像区域的组合距离之后，过滤单元204根据所计算出的组合距离来滤除组合距离较大的候选关键词图像区域，并最终输出搜索结果。
[0107] 根据以上对具体实施方式的描述，在根据本发明的关键词搜索装置中，校验单元202以及整体匹配单元201的候选区域提取单元302A分别包括单字识别单元402和单字识别单元302A。但是本发明不限于此，本发明的关键词搜索装置还可以包括由检验单元202和候选区域提取单元302A共用的单字识别单元203(如图2中的虚线部分所示)。
[0108] 根据本发明，仅对有限数量的候选关键词图像区域进行单字识别，而不用对整个图像进行识别，因此可以极大地提高系统的处理速度。同时，利用小范围的动态规划校验，可以进一步提高系统的处理精度。
[0109] 在上述实施方式中，仅针对单个关键字的搜索进行了说明，但是本发明不限于此，本发明还可以应用于对多关键词的搜索。
[0110] 此外，在本发明中使用匹配距离来判断相似程度，但是本发明不限于此，还可以使用匹配距离以外的方法来判断相似程度，例如使用特征向量之间的余弦夹角、特征向量之间的街区距离等。因此，本发明的匹配距离应作广泛的解释，是本领域技术人员所能想到的相似程度的定量表示。
[0111] 前面对本发明实施方式的描述是示例性和说明性的，并不是排他性的，也不是为了将本发明限制为所公开的确切形式。显然，对于本领域的普通技术人员，很多修改和变型是显而易见的。选择并说明这些实施方式是为了更好地说明本发明的原理及其实际应用。从而使得本领域的其他技术人员能够理解用于各种实施方式的本发明以及本发明适于特殊使用目的的变型。
