图案分离提取程序、图案分离提取装置和图案分离提取方法

具体实施方式

下面参照附图描述本发明的实施方式。

首先，描述根据本实施方式的计算机网络系统的硬件结构和软件结构。

图1是表示本实施方式的图案分离提取装置的结构的框图。

本实施方式的图案分离提取装置10是增加了图案分离提取功能的个人计算机。因此，图案分离提取装置10包括：显示装置10a，例如液晶显示器；输入装置10b，例如键盘和鼠标；以及这些装置10a和10b所连接到的主体。该主体包括存储装置10c、CPU(中央处理单元)10d和DRAM(动态随机存取存储器)10e。

存储装置10c存储各种应用程序和数据。CPU 10d是根据存储装置内的程序进行处理的处理单元。DRAM 10e是易失性存储装置，其缓存(cashed)程序，并且当CPU 10d进行处理时展开工作区。

将文件图像数据11和图案分离提取工具软件12安装到图案分离提取装置10的存储装置10c中。图1表示将文件图像数据11和图案分离提取工具软件12展开到DRAM10e上的状态。

文件图像数据11是用于显示文件图像的数据，并且是通过扫描仪对文件的内容进行数字化而生成的。文件是其上根据预定格式由标线形成有一些输入栏的一张纸。通过手写或印刷将字符和符号填入输入栏，或者在其中盖印图章。由个人向文件添加的诸如手写字符、复写字符或图章盖印的图案被称为后印刷图案。在个人添加后印刷图案之前在文件上印刷的诸如标线、字符或符号的图案被称为预印刷图案。

图2表示根据文件图像数据11的文件图像的示例。

如图2所示，在该实施方式中，文件图像包含多个印刷图案，这些印刷图案包括一个后印刷图案、以及一个或更多个后印刷图案和/或预印刷图案。这些图案彼此重叠。具体地说，该文件图像包含：第一印刷图案，其包括四个印刷日本汉字字符；以及第二印刷图案，其是包括矩形框和该框内的日本汉字字符的图章盖印。第一印刷图案的日本汉字字符表示姓名“山田太郎(Taro Yamada)”。第二印刷图案的日本汉字字符表示“印(seal)”。第二印刷图案被设置为使得该第二印刷图案的上半部分与第一印刷图案的最后一个日本汉字字符重叠。

图1的图案分离提取工具软件12根据如图2所示的文件图像，对每个印刷图案生成仅包括一个印刷图案的图像。以下描述由CPU10d根据图案分离提取工具软件12执行的处理的内容。

接下来，描述由该实施方式的图案分离提取装置10执行的处理的流程。

当操作者通过输入装置10b输入预定操作时，CPU10d启动图案分离提取工具软件12。然后，在图案分离提取装置10中开始图案分离提取处理。

图3是表示图案分离提取处理的流程图。

在图案分离提取处理的第一步骤S101中，CPU10d通过输入装置10b从操作者接受存储装置10c中的任何一条文件图像数据11的指定。

在下一步骤S102中，CPU10d根据在步骤S101中接受的指定所指定的文件图像数据11，将文件图像显示在显示装置10a上。步骤S102与上述显示功能相对应，执行步骤S102的CPU10d与显示部分相对应。然后，CPU10d使处理前进到步骤S103。

在步骤S103中，CPU10d通过输入装置10b从操作者接受指定，该指定用于选择在显示装置10a上显示的文件图像中的被拖动部分作为颜色样本。此时，操作者必须选择一部分，以使得从文件图像选择的部分包含背景颜色和背景颜色以外的仅一种颜色。

图4表示用于选择颜色样本的方法。

如图4所示，由于第二印刷图案不与第一印刷图案的第一字符重叠，所以操作者选择包括第一字符的部分作为第一颜色样本11a。因此，第一颜色样本11a仅包括背景颜色和第一印刷图案的字符的颜色。然后，操作者选择不与第一印刷图案的最后一个字符重叠的第二印刷图案的下半部分作为第二颜色样本11b。因此，第二印刷图案仅包括背景颜色和第二印刷图案的图章盖印的颜色。

在下一步骤S104中，CPU10d从文件图像数据11中裁剪在步骤S103中接受的指定所指定的部分，并将其作为颜色样本数据存储到DRAM12中。

在下一步骤S105中，CPU10d确定操作者是否指示结束颜色样本的指定。当操作者没有指示结束颜色样本的指定时，CPU10d从步骤S105对该处理进行分支，使该处理返回到步骤S103。另一方面，当操作者指示结束颜色样本的指定时，CPU10d执行第一处理循环L1。步骤S103到S105与上述接受功能相对应，执行步骤S103到S105的CPU10d与接受部分相对应。

在第一处理循环L1中，CPU10d进而对在步骤S103中接受的指定所指定的各个颜色样本执行步骤S106。

在步骤S106中，CPU10d执行前景颜色分布近似直线指定子例程。

图5是表示前景颜色分布近似直线指定子例程的流程图。

在前景颜色分布近似直线指定子例程的第一步骤S201中，CPU10d使用预定阈值对处理目标的颜色样本的各个像素的亮度级进行二值化，并生成二值图像。

在下一步骤S202中，CPU10d将在步骤S201中生成的二值图像的像素分为作为前景像素的二进制亮度级为“1”的像素组以及作为背景像素的二进制亮度级为“0”的像素组。

在下一步骤S203中，CPU10d通过计算文件图像中的所有背景像素的颜色分量的平均值，来指定背景典型颜色的分量值。

在下一步骤S204中，CPU10d在例如CIE1931标准比色(colorimetric)系统的颜色空间坐标系中，绘制在步骤S203中指定的背景典型颜色的坐标点，并建立以该坐标点为中心的单位球。

在下一步骤S205中，CPU10d将在步骤S204建立的单位球的球形表面分为预定数量的单位区域。

图6是其球形表面被分为预定数量的单位区域的单位球的示意图。

如图6所示，通过多面体近似将该单位球等分为多个单位区域(单位表面)。向每个单位区域赋予区域号，以单独地识别它们。此外，生成指定各个单位区域的位置的位置信息。该位置信息由单位区域的顶点的坐标或其质心坐标来定义。当在单位球上建立单位区域时，生成区域号和位置信息，并在第一工作表中对区域号和位置信息进行管理。

图7表示第一工作表的数据结构的示例。

如图7所示，第一工作表具有与在单位球上建立的单位区域一样多的记录。每条记录都具有“区域号”、“位置信息”和“频度”的字段。“区域号”字段存储单位区域的区域号。“位置信息”字段存储单位区域的位置信息。“频度”字段存储连接处理目标前景像素的颜色的坐标点与单位球的中心的直线当中的通过单位区域的直线的数量。

在步骤S205时，将第一工作表中的各条记录的“频度”字段初始化为0。

CPU10d在如图6所示的单位球上建立单位区域，并在DRAM10e上生成如图7所示的第一工作表。然后，CPU10d执行图5的第三处理循环L3。

在第三处理循环L3中，CPU10d进而对处理目标颜色样本的每一个前景像素执行步骤S206和S207。

在步骤S206中，CPU10d在颜色空间坐标系中，指定连接处理目标前景像素的颜色的坐标点与上述单位球的中心的直线所通过的单位区域。

在下一步骤S207中，CPU10d在图7的第一工作表中，使与在步骤S206中指定的单位区域像对应的记录的“频度”字段中的值递增。

因此，当CPU10d执行与处理目标颜色样本的所有前景像素相关的步骤S206和S207时，可以对在步骤S205中在单位球上建立的每个单位区域，对通过单位区域的直线的数量进行计数。

在执行第三处理循环L3之后，在下一步骤S208中，CPU10d指定图7的第一工作表中的“频度”字段中的值最大的记录。

在下一步骤S209中，CPU10d根据在步骤S204中建立的单位球的中心坐标和在步骤S208中指定的记录的“位置信息”字段中的值，来指定连接单位球与单位区域的中心的直线。具体地说，通过确定直线的方向向量和单位球的中心坐标，来指定直线。CPU10d计算(Xg-Xo，Yg-Yo，Zg-Zo)来指定方向向量，其中所指定的单位区域的质心坐标是(Xg，Yg，Zg)并且单位球的中心坐标是(Xo，Yo，Zo)。其后，CPU10d将由所指定的方向向量和单位球的中心坐标定义的直线用作处理目标颜色样本的所有前景像素的颜色的分布的近似直线。在指定与处理目标颜色样本的所有前景像素的分布相关的近似直线时，CPU10d将该近似直线的方向向量和单位球的中心坐标存储到第二工作表中。

图8表示第二工作表的数据结构的示例。

如图8所示，第二工作表具有与颜色样本一样多的记录。每条记录都具有“样本”、“方向向量”和“单位球的中心坐标”的字段。“样本”字段存储颜色样本号，该颜色样本号用于识别在步骤S103中接受的颜色样本。“方向向量”字段存储在步骤S209中计算的、与有关颜色样本相关的方向向量。“单位球的中心坐标”字段存储在步骤S204中建立的单位球的中心坐标。

在将在步骤S209中指定的直线的方向向量和单位球的中心坐标记录到如图8所示的第二工作表中之后，CPU10d结束图5的前景颜色分布近似直线指定子例程，并对有关处理目标颜色样本结束图3中的第一处理循环L1。

当CPU10d对在步骤S103中接受的指定所指定的所有颜色样本执行图3的步骤S106(图5的前景颜色分布近似直线指定子例程)时，分别对颜色样本指定颜色空间坐标系上的近似直线，并将与颜色样本相对应的记录存储到图8的第二工作表中。

这里，将描述近似直线的细节。当将印刷在纸上的诸如字符、图案和图章盖印的内容数字化为数字图像时，代表背景(纸本身)的像素的颜色和实际(solidly)填写的区域以高斯(Gaussian)分布进行分布。另一方面，代表诸如字符和图章盖印的线图案的像素的颜色以线性分布进行分布，由于墨水的不均匀性等，使得该线性分布的一个端点与背景的颜色分布的中心一致。L.Todoran和M.Worring在1999年的关于文件分析和识别的国际会议(International Conference on Document Analysis andRecognition(ICDAR))中报告了该现象。通过对线图案的线性颜色分布进行近似来获得近似直线。

图9A和图9B分别表示图4的第一颜色样本11a的前景像素的颜色分布以及第二颜色样本11b的前景像素的颜色分布。

如图9A和9B中的浅灰色的坐标点所示，在图像中代表背景的像素(背景像素)的颜色的坐标点表现出没有方向性的块状分布(massivedistribution)。另一方面，如图9A和9B中的深灰色的坐标点所示，代表诸如字符和盖印的线图案的像素(前景像素)的颜色的坐标点表现出线性分布，该线性分布的一个端点与块状分布的中心一致。在图9A和9B表示的颜色分布中，示出了通过对代表线图案的像素(前景像素)的颜色分布进行近似而获得的直线。

图10表示以背景典型颜色的坐标为中心的单位球与近似直线之间的关系。

如图10所示，近似直线的一个端点与单位球的中心一致，并且该近似直线穿过通过将像素的颜色坐标投影到单位球的球形表面上而形成的分布的顶点。图5的上述步骤S204到S208指定了通过将像素的颜色坐标投影到球形表面上而形成的分布的顶点。在该实施方式中，根据通过投影到球形表面上而形成的分布来指定近似直线。然而，也可以根据最小二乘法来指定近似直线。

在执行第一处理循环L1并获得与各个颜色样本相关的近似直线之后，CPU10d使处理前进到图3的步骤S107。第一处理循环L1与上述近似直线指定功能相对应，执行第一处理循环L1的CPU10d与近似直线指定部分相对应。

在步骤S107中，CPU10d通过使用预定阈值对文件图像的像素的亮度级进行二值化，来生成二值图像。

在下一步骤S108中，CPU10d从在步骤S107中生成的二值图像的像素中提取二进制亮度级为“1”的像素组作为前景像素。然后，CPU10d执行第二处理循环L2。

在第二处理循环L2中，CPU10d依次对文件图像中的每一个前景像素重复执行步骤S109。

在步骤S109中，CPU10d执行归属目标确定子例程。

图11是表示归属目标确定子例程的流程图。

在归属目标确定子例程的第一步骤S301中，CPU10d计算从处理目标前景像素到在步骤S106中指定的近似直线的距离，并将所计算的距离记录到第三工作表中，作为下述的归属度。

图12表示第三工作表的数据结构的示例。

如图12所示，第三工作表具有与前景像素一样多的记录。每一条记录都具有“前景像素号”、“坐标”、“归属度”、“归属”以及“到近似平面的距离”的字段。“前景像素号”字段存储前景像素号，该前景像素号用于从各个前景像素中单独地识别前景像素。“坐标”字段存储颜色空间坐标系中的前景像素的坐标。“归属度”字段存储与前景像素相关的对每个印刷图案的归属度的组合(下面说明)。“归属”字段存储与前景像素所属的印刷图案相对应的颜色样本的数量。“到近似平面的距离”字段存储包含两条近似直线的近似平面与有关前景像素之间的距离。存在与从所有近似直线中选择的两条近似直线的组合一样多的近似平面。“到近似平面的距离”字段存储与这些组合一样多的距离。

在执行步骤S301时，第三工作表中的与处理目标前景像素相对应的记录的“归属”字段是空白的。

图13表示用于计算归属度的方法。

图13表示从背景像素的典型颜色的坐标点(从上述单位球的中心)延伸的两条近似直线的示例。通常，前景像素的颜色的坐标点分布在近似直线的周围或它们之间。当前景像素的坐标点位于两条近似直线之间，并且假设前景像素的坐标点与第一近似直线之间的距离是d₁并且坐标点与第二近似直线之间的距离是d₂时，将前景像素对于颜色坐标点分布在第一近似直线附近的第一印刷图案的归属度m₁表示为1-{d₁/(d₁+d₂)}。

类似地，将前景像素对于颜色坐标点分布在第二近似直线附近的第二印刷图案的归属度m₂表示为1-{d₂/(d₁+d₂)}。根据这些公式可以看出，归属度位于0到1的范围内。

更一般地说，特定像素对于与第i近似直线相对应的印刷图案的归属度m由以下公式表示

m＝1-(d_i/∑d_i)

其中d_i(1≤i≤N)是第i近似直线与像素的颜色的坐标之间的距离，而N是近似直线的总数。

在对每条近似直线计算这种归属度m₁和m₂时，CPU10d将归属度的组合存储到与图12的第三表格中的处理目标前景像素相对应的记录的“归属度”字段。然后，CPU10d执行图11的第四处理循环L4。步骤S301与上述归属度计算功能相对应，执行步骤S302的CPU10d与归属度计算部分相对应。

在第四处理循环L4中，CPU10d对在步骤S301中对处理目标前景像素计算的每一个归属度执行步骤S302和S303。

在步骤S302中，CPU10d确定处理目标的归属度是否超过预定阈值。例如，该预定阈值是0.3。当处理目标的归属度小于预定阈值时，CPU10d从步骤S302对该处理进行分支，并结束第四处理循环L4中的针对处理目标的归属度的处理。另一方面，当处理目标的归属度等于或大于预定阈值时，CPU10d使处理前进到步骤S303。

在步骤S303中，CPU10d采用处理目标前景像素作为与处理目标归属度的近似直线相对应的图案图像的前景像素。即，CPU10d另外将与印刷图案相对应的颜色样本的编号登记到图12的第三工作表中的处理目标前景像素的记录的“归属”字段中。因此，当生成仅包括印刷图案的图像的数据时，采用处理目标前景像素作为构成图像的像素。然后，CPU10d结束第四处理循环L4中的针对处理目标的归属度的处理。

由于CPU10d对在步骤S301中计算的每一个归属度执行步骤S303和S304的处理，所以确定了处理目标前景像素所属的一个或更多个印刷图案。

在执行第四处理循环L4之后，CPU10d使处理前进到步骤S304。

在步骤S304中，CPU10d计算包含两条近似直线的近似平面与处理目标前景像素之间的距离。对从在步骤S106中指定的所有近似直线中选择的两条近似直线的组合中的每一个组合计算该距离。然后，CPU10d将所有计算出的距离记录到图12的第三工作表中的处理目标前景像素的记录的“到近似平面的距离”字段。

在下一步骤S305中，CPU10d确定在步骤S304中计算的所有距离是否超过预定阈值。

当在步骤S304中计算的所有距离超过预定阈值时，CPU10d使处理前进到步骤S306。

在步骤S306中，CPU10d取消处理目标前景像素在步骤S303中作为印刷图案的前景像素的应用。即，CPU10d从图12的第三工作表中的处理目标前景像素的记录的“归属(imputed)”字段中删除所有的值，并使该字段空白。

因此，如果到各近似平面的所有距离超过该阈值，则认为该处理目标前景像素是噪声，并且不再将其用于任何印刷图案。

在执行步骤S306之后，CPU10d结束与图11相关的归属目标确定子例程，并结束图3的第二处理循环L2中的对于处理目标前景像素的处理。

另一方面，当在步骤S305中，在步骤S304中计算的至少一个距离小于预定阈值时，CPU10d从步骤S305对该处理进行分支，并结束与图11相关的归属目标确定子例程，而不执行步骤S306。然后，CPU10d结束图3的第二处理循环L2中的对于处理目标前景像素的处理。

由于CPU10d对文件图像中的每一个前景像素执行图3的步骤S109的处理(图11的归属目标确定子例程)，所以确定了处理目标前景像素所属的一个或更多个印刷图案。第四处理循环L4与上述归属目标确定功能相对应，执行第四处理循环L4的CPU10d与归属目标确定部分相对应。

在执行第二处理循环L2之后，在下一步骤S110中，CPU10d根据图12的第三工作表，对文件图像中的每个印刷图案，生成包含属于该印刷图案的前景像素的图像的数据。因此，对每个印刷图案生成包括一个印刷图案的图像数据。步骤S110与上述生成功能相对应，执行步骤S110的CPU10d与生成部分相对应。

在下一步骤S111中，CPU10d输出在步骤S110中生成的印刷图案图像数据。将该数据输出到盘装置、显示装置10a、OCR(光学字符阅读器)、网络上的另一计算机等。在输出印刷图案图像数据时，CPU10d结束与图3相关的处理。步骤S111与上述输出功能相对应，执行步骤S111的CPU10d与输出部分相对应。

接下来，将描述该实施方式的图案分离提取装置10的操作和效果。

当图案分离提取装置10的操作者通过输入装置10b启动图案分离提取工具12时，例如在显示装置10a上显示输入画面。操作者可以通过该输入画面选择并指定存储装置10c内的任何其中一个文件图像数据(步骤S101)。

然后，将操作者选择的文件图像显示在显示装置10a上(步骤S102)。操作者可以在显示装置10a上显示的文件图像上通过拖动操作来选择并指定颜色样本(步骤S103)。并且如果操作者在指定一些颜色样本之后，通过输入装置10b输入结束指定颜色样本的指定，则图案分离提取装置10对操作者选择的文件图像中所包括的每个印刷图案生成并输出包括一个印刷图案的图像数据。

图14A表示第一印刷图案的一个示例，图14B表示第二印刷图案图像的一个示例。

如图14A和14B所示，分别提取出在重叠状态下包含在图2的文件图像中的第一印刷图案和第二印刷图案并将其显示为独立图像。

当生成与各个印刷图案相关的图像数据时，计算机将文件图像中的对于多个印刷图案具有高归属度的像素视为构成这些印刷图案的像素(步骤S303)。即，文件图像的像素可以不仅构成一个印刷图案，而且在某些情况下构成多个印刷图案。

例如，当阈值是0.3时，对于第一印刷图案和第二印刷图案的归属度的组合是(0.1，0.9)的前景像素仅属于第二印刷图案。然而，如果组合是(0.45，0.55)，则有关前景像素属于第一印刷图案和第二印刷图案两者。因此，可以将所生成的各个印刷图案图像用作OCR的字符识别处理的目标，而不受缺少具有高归属度的像素的影响等。

在本实施方式中，对于任何近似直线使用公共阈值来确定归属度。然而，本发明的范围不限于此。例如，可以与近似直线相对应地改变阈值。

在本实施方式中，如图13所示，根据前景像素的坐标点与各近似直线之间的距离d₁和d₂来计算归属度。然而，本发明的范围不限于此。例如，如图15所示，可以根据在连接前景像素的坐标点与背景像素的典型颜色的坐标点的直线与各近似直线之间形成的内角θ₁和θ₂，来计算归属度m₁和m₂。

即，将归属度m₁表示为1-{θ₁/(θ₁+θ₂)}，将归属度m₂表示为1-{θ₂/(θ₁+θ₂)}。

更一般地说，特定像素对于与第i近似直线相对应的印刷图案的归属度m由以下公式表示

m＝1-(θ_i/∑θ_i)，

其中θ_i(1≤i≤N)是在第i近似直线与连接背景颜色的坐标和像素的颜色的坐标的直线之间形成的内角，N是近似直线的总数。