彩色文档图像的分层方法和装置

摘要

提供了一种彩色文档图像的分层装置和方法。本发明的彩色文档图像分层装置执行如下处理：确定所述文档图像的背景色；将所述文档图像中的每个像素点映射到以所述背景色为原点的RGB空间中，构建反映了所述文档图像的像素点在所述RGB空间中的分布的特征平面；基于所述特征平面中的密度分布将所述特征平面分割为一个以上的区域；基于所述分割结果，将所述文档图像划分为一个以上的图层。

权利要求

1.一种彩色文档图像的分层方法，其特征在于，该方法包括如下步骤：确定所述文档图像的背景色；

将所述文档图像中的每个像素点映射到以所述背景色为原点的RGB空间中，构建反映了所述文档图像的像素点在所述RGB空间中的分布的特征平面；

基于所述特征平面中各点的特征值的分布将所述特征平面分割为一个以上的区域；

基于所述分割结果，将所述文档图像划分为一个以上的图层。

2.如权利要求1所述的彩色文档图像的分层方法，其特征在于，在所述构建特征平面的步骤中，同时考虑所述文档图像中的每个像素点与背景色之间的距离、以及所述特征平面中的每个点所对应的像素分布密度。

3.如权利要求2所述的彩色文档图像的分层方法，其特征在于，在构建特征平面的步骤中，将所述RGB空间中的每个点转换为极坐标系中的向量，并将所述向量映射到以所述极坐标系的角度为坐标轴的平面坐标系中。

4.如权利要求1所述的彩色文档图像的分层方法，其特征在于，在所述确定背景色的步骤中，选择RGB彩色直方图中最大值所对应的颜色作为所述背景色。

5.如权利要求1所述的彩色文档图像的分层方法，其特征在于，在所述分割特征平面的步骤中，将所述特征平面分割为与该特征平面内的各点的特征值的分布的峰值数量一样多的区域。

6.一种对彩色文档图像进行分层的装置，其特征在于，该装置包括：背景色确定单元，其确定所述文档图像的背景色；

映射单元，其将所述文档图像中的每个像素点映射到以所述背景色为原点的RGB空间中，特征平面构建单元，其构建反映了所述文档图像的像素点在所述RGB空间中的分布的特征平面；

特征平面分割单元，其基于所述特征平面中的各点的特征值的分布将所述特征平面分割为一个以上的区域；

图层划分单元，其基于所述分割结果，将所述文档图像划分为一个以上的图层。

7.如权利要求6所述的装置，其特征在于，所述特征平面构建单元同时考虑所述文档图像中的每个像素点与背景色之间的距离、以及所述特征平面中的每个点所对应的像素分布密度，来构建所述特征平面。

8.如权利要求7所述的装置，其特征在于，所述特征平面构建单元将所述RGB空间中的每个点转换为极坐标系中的向量，并将所述向量映射到以所述极坐标系的角度为坐标轴的平面坐标系中，以构建所述特征平面。

9.如权利要求6所述的装置，其特征在于，所述背景色确定单元选择RGB彩色直方图中最大值所对应的颜色作为所述背景色。

10.如权利要求6所述的装置，其特征在于，所述特征平面分割单元将所述特征平面分割为与该特征平面内的各点的特征值的分布的峰值数量一样多的区域。

说明书

彩色文档图像的分层方法和装置

技术领域

[0001] 本发明涉及彩色文档图像的分层方法和装置，更具体地，涉及具有单一背景色的彩色文档图像的分层方法和装置。

背景技术

[0002] 光学字符识别(OCR)是一种通过计算机自动识别点阵形式文档图像的内容的技术，目前已经被成功的应用于日常生活及办公等领域中。

[0003] 一般来说，一幅文档图像的识别包括版面分析和字符识别两个步骤，前者是指将图像分割为各个语义结构，包括段落、行、字、图片等，后者是将单个字符的信息输入至识别器中进行处理。版面分析的结果直接将直接影响最终的识别准确率。

[0004] 人眼在灰度图像上只能识别出几十种灰度等级，却能从彩色图像中识别出成千上万种色彩，因此彩色图像相对灰度图像而言，能够提供更多的信息。近十几年来，随着计算机和光学等科技的发展，彩色图像的打印、扫描、存储和传输能力得到了极大的提高，使得我们日常使用的文档也逐渐的从灰度图像转变到彩色图像。通常在一副彩色文档图像中，不同的内容(包括预打印的表格、后打印的内容、手写的内容，以及印章等)用不同的颜色来表示，以便于人们阅读。

[0005] 如果我们能根据颜色特征将彩色文档图像分解为若干层，使得每层对应于文档中某一特定内容，然后分别对各层进行处理和识别，那么该输入文档的识别过程将会得到有效的简化，识别的准确率也能大大提高。

[0006] 在非专利文献1中公开了一种直接对各像素颜色中红、绿、蓝分量进行线性计算的分类方法。该方法首先预定义若干种颜色，然后通过实验归纳总结出根据各颜色分量进行线性计算来分类的准则。这种方法的优点是简单、快速，但是适用范围太窄，往往需要针对不同的文档、不同的扫描仪设置不同的分类准则。

[0007] 非专利文献2和3公开了基于在RGB颜色空间上进行聚类的分类方法。该方法将每一个采样点的颜色视为RGB颜色空间中的一个样本，然后用一些常用的聚类算法，例如k-均值算法、图聚类算法等，对其进行分类。这种方法原理非常直观，但是没有考虑彩色文档图像中颜色分布的产生原因，而用一种通用的三维数据分类算法进行处理，在应用上受到一些条件的局限：某些算法需要事先设定类别数量等先验知识，而且各类样本在空间中符合某一特定的分布特征，而通常这些条件是不满足的。

[0008] 专利文献1和2公开了基于在亮度分量上进行分类的方法。这类方法首先将输入彩色文档图像从RGB颜色空间转化到亮度-色度形式的颜色空间，然后仅仅根据亮度分量进行分层的处理，类似于对灰度图像进行分层。通常这类算法将亮度图像分割为文字、线、普通图片、半调色图片等属性的区域，然后再根据各区域的不同属性进行不同的处理。由于这些算法仅仅考虑了亮度信息，没有利用颜色信息，造成了信息缺失，因此导致其适用范围受到了很大的限制。

[0009] 非专利文献4公开了基于在RGB颜色空间上进行线型聚类的分类方法。观察结果表明，彩色文档图像在RGB颜色空间中表现为一系列线段型的聚类，其中每一条线段的两个端点分别为该层的背景色和理想情况下的前景色。因此，该方法首先根据颜色空间中样本分布密度的大小来选择一系列背景色和前景色的候选，然后找出这些背景色和前景色所构成的线段，并对其进行合并、排除等操作，最终将所得到的一系列线段作为分类结果，并对输入图像进行分层。该方法较以上两类方法而言，充分考虑了彩色文档图像的形成机理及其在颜色空间的分布特征，提高了分层结果的正确，并且可以处理多背景区域的彩色文档。其缺点在于在候选颜色的选取以及对线段进行分析的过程中，需要预定义多个参数，参数设置将直接影响分层效果；并且，由于在选择候选颜色时只考虑了样本在颜色空间中的分布密度，使得一些像素数量很小的图层很可能会被忽略。

[0010] 非专利文献1：Tony Allen，Nasser Sherkat，Seong Wong，“Use of colourfor hand-filled form analysis and recognition”，Pattern Analysis &Applications，v.8，n.1，pp.163-180，2005.

[0011] 非 专 利 文 献 2：J.Zhou and D.Lopresti，“Extracting Text from WWWImages，”Proceedings of the 4th ICDAR，Ulm，Germany，v.1，pp.248-252，1997.[0012] 非专利文献3：Sobottka，H.Bunke，and H.Kronenberg，“Identificationof text on colored book and journal covers，”In ICDAR’99，v.1，pp.57-60，1999.[0013] 非专利文献4：M.Worring and L.Todoran，“Segmentation of colordocuments thby line oriented clustering using spatial information，”Proceedingsof the 5 ICDAR，pp.67-70，1999.

[0014] 专利文献1：美国专利第7,065,254号，发明人为Kristine E.Matthews，名称为“Multilayered image file”.

[0015] 专利文献2：美国专利5,341,226号，发明人为Jeng-Nan Shiau，名称为“Automatic image segmentation for color documents”.

发明内容

[0016] 本发明就是鉴于上述现有技术的缺点和不足而提出的，其目的在于提供能够高效、准确地对彩色文档图像进行分层的设备、方法和程序等。

[0017] 在一幅理想的彩色文档图像中，不同的内容被设计为不同的颜色，但是每层所包含的所有像素都具有同一个颜色，即该层的理想色。但是由于经过打印、扫描等操作之后，必然会包含噪声；而且，在打印或者手写的过程中，所得到的颜色是纸张颜色和输入颜色的一种混合，或者下一图层颜色(背景色)和本图层颜色(前景色)的混合。由于这些因素的影响，得到的图像中各层并不仅包含单一一种颜色，而是一系列颜色组成的颜色空间分布。实验表明，各层像素的颜色在RGB空间中表现为一个线段型的分布，线段的两端分别为前景色和背景色。

[0018] 由于日常使用的彩色文档一般都是用单色纸张的，即单一背景色的。在单一背景色文档中，不同内容所对应的图层分别在RGB空间中表现为若干条相交于该背景色的线段型聚类。

[0019] 本发明基于单一背景色文档图像的上述特点，考虑到彩色文档图像中颜色分布的产生原因，提出了以下的技术方案。

[0020] 发明1、一种彩色文档图像的分层方法，其特征在于，该方法包括如下步骤：

[0021] 确定所述文档图像的背景色；

[0022] 将所述文档图像中的每个像素点映射到以所述背景色为原点的RGB空间中，[0023] 构建反映了所述文档图像的像素点在所述RGB空间中的分布的特征平面；

[0024] 基于所述特征平面中的密度分布将所述特征平面分割为一个以上的区域；

[0025] 基于所述分割结果，将所述文档图像划分为一个以上的图层。

[0026] 发明2、发明1的彩色文档图像分层方法，其特征在于，在所述构建特征平面的步骤中，同时考虑所述文档图像中的每个像素点与背景色之间的距离、以及所述特征平面中的每个点所对应的像素分布密度。

[0027] 发明3、发明2的彩色文档图像分层方法，其特征在于，在构建特征平面的步骤中，将所述RGB空间中的每个点转换为极坐标系中的向量，并将所述向量映射到以所述极坐标系的角度为坐标轴的平面坐标系中。

[0028] 发明4、发明1的彩色文档图像分层方法，其特征在于，在所述确定背景色的步骤中，选择RGB彩色直方图中最大值所对应的颜色作为所述背景色。

[0029] 发明5、发明1的彩色文档图像分层方法，其特征在于，在所述分割特征平面的步骤中，将所述特征平面分割为与该特征平面内的峰值数量一样多的区域。

[0030] 发明6、一种对彩色文档图像进行分层的装置，其特征在于，该装置包括：

[0031] 背景色确定单元，其确定所述文档图像的背景色；

[0032] 映射单元，其将所述文档图像中的每个像素点映射到以所述背景色为原点的RGB空间中，

[0033] 特征平面构建单元，其构建反映了所述文档图像的像素点在所述RGB空间中的分布的特征平面；

[0034] 特征平面分割单元，其基于所述特征平面中的密度分布将所述特征平面分割为一个以上的区域；

[0035] 图层划分单元，其基于所述分割结果，将所述文档图像划分为一个以上的图层。

[0036] 发明7、发明6的装置，其特征在于，所述特征平面构建单元同时考虑所述文档图像中的每个像素点与背景色之间的距离、以及所述特征平面中的每个点所对应的像素分布密度，来构建所述特征平面。

[0037] 发明8、发明7的装置，其特征在于，所述特征平面构建单元将所述RGB空间中的每个点转换为极坐标系中的向量，并将所述向量映射到以所述极坐标系的角度为坐标轴的平面坐标系中，以构建所述特征平面。

[0038] 发明9、发明6的装置，其特征在于，所述背景色确定单元选择RGB彩色直方图中最大值所对应的颜色作为所述背景色。

[0039] 发明10、发明6的装置，其特征在于，所述特征平面分割单元将所述特征平面分割为与该特征平面内的峰值数量一样多的区域。

[0040] 发明11、一种使信息处理设备对彩色文档图像进行分层的程序，其特征在于，该程序使信息处理设备执行如下步骤：

[0041] 确定所述文档图像的背景色；

[0042] 将所述文档图像中的每个像素点映射到以所述背景色为原点的RGB空间中，[0043] 构建反映了所述文档图像的像素点在所述RGB空间中的分布的特征平面；

[0044] 基于所述特征平面中的密度分布将所述特征平面分割为一个以上的区域；

[0045] 基于所述分割结果，将所述文档图像划分为一个以上的图层。

[0046] 发明12、发明11的程序，其特征在于，该程序使信息处理设备：

[0047] 在所述构建特征平面的步骤中，同时考虑所述文档图像中的每个像素点与背景色之间的距离、以及所述特征平面中的每个点所对应的像素分布密度。

[0048] 发明13、发明12的程序，其特征在于，该程序使信息处理设备：

[0049] 在构建特征平面的步骤中，将所述RGB空间中的每个点转换为极坐标系中的向量，并将所述向量映射到以所述极坐标系的角度为坐标轴的平面坐标系中。

[0050] 发明14、发明11的彩色文档图像分层方法，其特征在于，该程序使信息处理设备：

[0051] 在所述确定背景色的步骤中，选择RGB彩色直方图中最大值所对应的颜色作为所述背景色。

[0052] 发明15、发明11的程序，其特征在于，该程序使信息处理设备：

[0053] 在所述分割特征平面的步骤中，将所述特征平面分割为与该特征平面内的峰值数量一样多的区域。

[0054] 发明16、存储了发明11～16中任意一项的程序的计算机可读介质。

[0055] 根据本发明，考虑了彩色文档图像中颜色分布的产生原因和分布的线型特征，能够显著地提高彩色文档图像分层的准确性。

附图说明

[0056] 图1为彩色文档图像的分层结构的示意图；

[0057] 图2为彩色文档图像在RGB颜色空间中的分布的示意图；

[0058] 图3为本发明第一实施例的彩色文档图像分层装置的示意性结构框图；

[0059] 图4示出了彩色文档图像中的像素点在以背景色为原点的RGB空间中的分布的一个示例；

[0060] 图5是特征平面构建单元所构建的特征平面的一个示例；

[0061] 图6为第一实施例中的特征平面分割单元所执行的处理的概略流程图；

[0062] 图7为第一实施例中采用的基于等高线的非监督式分类方法的示意图；

[0063] 图8为图7所示一维数据进行分类所得到的树形结构；

[0064] 图9为根据图8所示的分类树对输入的数据区域进行分割的示意图；

[0065] 图10为图5所示的特征平面对应于第一个高度的等高线图；

[0066] 图11为图5所示的特征平面对应于第一个和第二个高度的等高线图；

[0067] 图12为根据图11所示的等高线对图5所示的特征平面进行分类所得到的树形结构；

[0068] 图13为根据图12所示的树形结构的第一层对图5所示的特征平面进行分割的示意图；

[0069] 图14为根据图12所示的树形结构的第二层对图13所示的特征平面分割结果进行进一步分割的示意图；

[0070] 图15为第二实施例中的特征平面分割单元所执行的处理的示意流程图；

[0071] 图16为第二实施例中对一维数据区域进行分割的示意图；

[0072] 图17是根据图5所示的特征平面计算所得的等深度水池的示意图；

[0073] 图18是根据图17所示的等深度水池进行扩散后，对图5所示的特征平面进行分类后所得到的分割结果。

具体实施方式

[0074] 以下参照实施例及附图详细说明根据本发明的彩色文档图像的分层方法和装置。

[0075] 如图1所示，输入的彩色文档按照内容划分可分为三个图层：表格、文字及图章。一般而言这三层是用不同的三种颜色来表示的。本发明的彩色文档图像的分层方法的目标就是将这三个图层根据颜色信息分解开来，即得到图1右侧所示的三幅图像。

[0076] 如图2所示，输入的单一背景且包含三个图层的彩色文档图像，在RGB颜色空间中符合一定的分布：每层所有像素的颜色分布为一个线型的聚类，且该线型的两个端点分别为背景色和该层理想色。因此，输入的彩色文档图像在RGB空间中分布为三个线型的聚类，且三条线段有一个共同的端点，即图像背景色；每条线段的另一端点为该层的理想色。

[0077] 【实施例1】

[0078] 图3示出了本发明的实施例1的彩色文档图像分层装置1的结构框图。该彩色文档图像分层装置1输入例如通过扫描仪得到的彩色文档图像，输出作为分层结果的一个以上的图层图像。如图3所示，彩色文档图像分层装置1包括背景色提取单元10、映射单元20、特征平面构建单元30、特征平面分割单元40和图层划分单元50。背景色提取单元10确定文档图像的背景色。映射单元20将文档图像中的每个像素点映射到以该背景色为原点的RGB空间中。特征平面构建单元30构建反映了该文档图像的像素点在所述RGB空间中的分布的特征平面。特征平面分割单元40基于所述特征平面中的密度分布将所述特征平面分割为一个以上的区域。图层划分单元50基于特征平面分割单元40的分割结果，将所述文档图像划分为一个以上的图层。

[0079] 下面按照彩色文档图像分层装置1对输入的彩色文档图像进行分层时的处理顺序对其各个部分的工作进行详细的说明。

[0080] 首先，背景色提取单元10确定文档图像的背景色。具体而言，背景色提取单元10建立输入图像在RGB颜色空间中的颜色直方图，然后由该颜色直方图确定输入图像的背景色(Rb，Gb，Bb)。计算直方图即计算在RGB颜色空间中，输入图像中每个颜色所对应的像素数量。一般而言，图像的背景所包含的像素数量最多，因此作为一例，可以把像素数量最多的颜色确定为背景色。当然，这仅仅是一个示例，也可以根据情况采用不同的背景色确定标准。另外，本实施例中通过颜色直方图来确定图像背景色的方式仅仅是一个示例，本发明不限于此，只要能够确定彩色文档图像的背景色即可，背景色的确定方式并不影响本发明的实施。

[0081] 在确定了彩色文档图像的背景色之后，映射单元20将文档图像中的每个像素点映射到以该背景色(Rb，Gb，Bb)为原点的RGB空间中。具体而言，映射单元20首先将原点为(0，0，0)的RGB坐标系C0的原点平移至背景色(Rb，Gb，Bb)，得到新的RGB坐标系C′。对于彩色文档图像中的每个像素点(Ri，Gi，Bi)，按照下式1计算其在坐标系C′中的位置(Ri′，Gi′，Bi′)。

[0082] Ri′＝Ri-Rb

[0083] Gi′＝Gi-Gb (1)

[0084] Bi′＝Bi-Bb

[0085] 即3个坐标分别为像素颜色的R、G、B分量数值与背景色的R、G、B分量数值之差。其中，i为像素点的索引。

[0086] 由此，把彩色文档图像中的每个像素点映射到以背景色为原点的RGB空间中。图4示出了彩色文档图像中的像素点在以背景色为原点的RGB空间中的分布的一个示例。

[0087] 接下来，特征平面构建单元30构建反映了该文档图像的像素点在RGB空间C′中的分布的特征平面。

[0088] 具体而言，对于坐标系C′中的一点(Ri′，Gi′，Bi′)，从原点至该点的向量为ViT＝[Ri′，Gi′，Bi′]，在极坐标系中该点表示为(Disi，αi，βi)，其中Disi为向量Vi的长度，αi和βi分别为极坐标系中的角度。Disi，αi和βi分别计算如下

[0089]

[0090] αi＝arctan(Gi′/Ri′) (2)

[0091]

[0092] 然后，以α和β为坐标，构造一个二维平面，输入的彩色文档图像中每一像素都对应于该平面上的一个点。对于该平面上的每个点，计算特征值F(α，β)：

[0093] F(α，β)＝Dis(α，β)+λDen(α，β) (3)

[0094] 其中Dis(α，β)为对应于点(α，β)的所有向量的最大长度，Den(α，β)为对应于点(α，β)的向量归一化分布密度。即假设对应于(α，β)的向量集合为{Vi，i＝1，2，...，N(α，β)}，其中N(α，β)为向量的数量，则：

[0095] Dis(α，β)＝max{‖Vi‖，i＝1，2，...，N(α，β)} (4)[0096] Den(α，β)＝N(α，β)/max{N(α，β)} (5)[0097] λ为预定的正实数，用于控制长度和密度之间的权重，例如可取为1.0。

[0098] 对于每个点计算特征值，由此构建了反映了该文档图像的像素点在RGB空间C′中的分布的特征平面。图5示出了特征平面的一个示例，其中纵坐标为特征平面中的点的特征值大小。

[0099] 需要说明的是，对于特征平面中各个点的特征值的运算，可以采用其他的计算方式，只要能够反映文档图像的像素点在RGB空间C′中的分布。例如，作为另一例，可以仅采用分布密度Den(α，β)来作为该点的特征值，如下式6所示。

[0100] F(α，β)＝Den(α，β) (6)

[0101] 此后，特征平面分割单元40基于该特征平面中的特征值的分布将特征平面分割为一个以上的区域(分类)。在本实施例中，采用基于等高线的非监督式分类算法进行该处理。下面进行具体的说明。

[0102] 形象来说，特征平面F(α，β)可以视为一个地形表面，如图5所示，其中每一类都对应于地形表面上一座山峰。特征平面分割单元40的作用是将整个地形表面分割得到每一山峰所占据的区域。类似于图像分割中的分水岭算法，分水岭和积水盆地是地形学中的概念，分水岭是指水面下各个积水盆地之间的邻接线，它们分开了每个积水盆地。如果将分水岭中的地形反过来，则可视为分水岭分开了每个山峰，也即找到了分水岭就达到了将特征平面进行分割的目的。

[0103] 在本实施例中采用一种非监督式的数据分类算法，该算法借鉴了分水岭算法，通过选择若干个适当的等高线来对输入的地形表面进行分级式的分割，分割结果可以用一个树形结构(以下简称为分类树)来记录，然后可以根据该树形结果逐次将该地形表面分割为若干互不重叠的区域。

[0104] 图6是特征平面分割单元40所进行的特征平面分割处理的具体流程图。

[0105] 大体上说，首先输入特征平面(S61)。在步骤S62中，根据输入的特征平面计算出等高线的范围，其中最大值和最小值分别为该特征平面上各点数值的最大值和最小值，并且初始化分类树。然后，在步骤S63中，根据上述等高线的最小值来计算相应的等高线。在步骤S64中，判断能否更新分类树，如果当前分类树中某一节点所对应的封闭曲线CP包含两条或两条以上的当前的封闭的等高线CC1，CC2，...，和CCN，则判断为可以更新分类树。若判断结果是肯定的，则进入步骤S65，更新分类树，从CP对应节点处延伸出N个子节点，分别对应于CC1至CCN。然后进入S67，判断是否满足结束条件，即当前等高线的高度是否超出该特征平面上各点数值的最大值。如果满足，则输出分类树(S68)并结束此处理。如果不满足结束条件，则进入步骤S66，增加等高线的高度，回到步骤S64，判断能否更新分类树。另一方面，如果S64的判断结果是否定的，则进入步骤S67，判断是否满足结束条件。最后，在步骤S69中，根据该分类树对输入的特征平面进行分割。

[0106] 为便于说明、并便于理解本发明，以下先用一维的分水岭数据为例详细描述整个过程。需要注意的是，实际上待分类的特征平面是二维平面，而且其高度与分水岭算法中的意义相反：本发明中待分类数据中每个山峰(地势高)对应于一类，而分水岭中每个积水盆地(地势低)对应于一类。因此，在基于等高线的分类算法中，初始设置一个最高的等高线高度，然后逐渐降低等高线高度；而在本实施例中，初始设置一个最低的等高线高度，然后逐渐提高等高线高度。

[0107] 图7、图8和图9是将基于等高线的分水岭算法应用于一维数据时的实例。如图7(a)所示，输入数据为一个一维的高度数据H，定义域中每一个位置x对应有一个高度H(x)，可以看出一共包含三个低谷，即三个积水盆地。图7(b)有一条用横虚线表示的等高线，高度为h1。统计低于该等高线的区域SR1＝{x|H(x)＜h1}，如果再降低等高线高度超过h1，就可将SR1分成两个线段r1和r2，即根据该等高线h1能够低于该等高线的区域分割为两个子区域，用分别r1和r2表示。类似的，逐渐降低等高线高度，直到如图7(c)中用一条横虚线表示的高度为h2的等高线时，低于该等高线的区域又被该等高线分割为两个子区域，分别用r3和r4表示。图8是图7所示的将该一维数据用本发明提出的基于等高线的分类方法进行分类所得到的树形结构。根节点为整个数据区域；首先，根据第一条等高线，低于等高线的区域被分割为“r1”和“r2”这两个子区域；然后，根据第二条等高线，低于等高线的区域“r2”被分割为“r3”和“r4”这两个子区域。

[0108] 图9是根据图8所示的分类树对输入的数据区域进行分割的示意图。分类依据为最近邻准则，区域上某点x与某个区域r＝{xi，i＝1，2，...，N}之间的距离d(x，r)定义为：

[0109] 如果x属于r，则d(x，r)＝0；

[0110] 如果x不属于r，则d(x，r)＝min{|x-xi|，i＝1，2，...，N}。

[0111] 根据分类树可以通过两次对输入数据进行分类。其一，如图9(a)所示，根据该树的第一层两个节点r1和r2，将整个数据区域分割为R1和R2两个区域；其二，如图9(b)所示，根据该树的第二层，即r2的两个子节点r3和r4将区域R2又分解为R3和R4两个子区域。至此，整个数据区域被分割为R1、R3和R4这三个区域，即数据被分为三类，各类的范围分别为R1、R3和R4。

[0112] 下面以二维的特征平面为例对该分类方法进行说明。图5示出了特征平面的一例。如图5所示，该特征平面上有四个峰谷，分别对应于特征平面应被划分的四个类。图10至图14显示了用上述基于等高线的非监督数据分类方法对特征平面进行分割的过程。

[0113] 首先，选择第一个适合的高度并计算等高线，如图10所示，该等高线包括三条封闭的曲线，分别为c1、c2和c3。然后，选择第二个适合的高度并计算等高线，如图11所示，新的等高线包括四条封闭的曲线，其中上一等高线所包含的封闭曲线中，只有c2所在区域包含两条当前的等高线对应的封闭曲线，分别为c4和c5。

[0114] 因此，根据上述等高线可以构造出如图12所示的用于特征平面分割的树形结构。最后，根据该树形结构对特征平面进行分割。图13显示了根据树形结构第一层进行分割的结果，该特征平面可被分解为c1、c2和c3三条曲线对应的区域，分别为C1、C2和C3；图14显示了根据树形结构第二层对图13再次进行分割的结果，曲线c2对应区域C2被继续分解为c4和c5两条曲线对应的区域，分别为C4和C5。

[0115] 至此，整个特征平面被分割为4个互不重叠的区域C1、C2、C4和C5，根据该分割结果可将输入彩色文档图像分解为四个图层。

[0116] 在特征平面分割单元40对特征平面进行分割之后，将分割结果传送给图层划分单元50。图层划分单元50根据该分割结果、以及文档图像中各个像素点与特征平面中的点之间的对应关系，将输入文档图像上每一像素分类至对应的图层。与特征平面分割结果中的一个区域对应的像素被归为一类，而对应于特征平面分割结果中不同区域的像素被归为不同的类别。由此，根据文档图像中的像素的分类结果，将每一类像素划分为彩色文档图像中的一层。

[0117] 如上所述，在本发明的第一实施例中，首先确定输入文档图像的背景色，将该文档图像中的每个像素点映射到以背景色为原点的RGB空间中，构建反映了该文档图像的像素点在以背景色为原点的RGB空间中的分布的特征平面，基于该特征平面中的密度分布将该特征平面分割为一个以上的区域，基于分割结果，将文档图像划分为一个以上的图层。根据第一实施例，充分利用了单一背景色的彩色文档图像中的颜色分布特性，能够准确地对彩色文档图像进行分层。

[0118] 【第二实施例】

[0119] 第二实施例的彩色文档图像分层装置的结构与上述第一实施例的彩色文档图像分层装置1基本上相同，包括将文档图像中的每个像素点映射到以该背景色为原点的RGB空间中的映射单元；构建反映了该文档图像的像素点在所述RGB空间中的分布的特征平面的特征平面构建单元；基于所述特征平面中的密度分布将所述特征平面分割为一个以上的区域的特征平面分割单元；基于特征平面分割单元的分割结果将所述文档图像划分为一个以上图层的图层划分单元。不同之处在于特征平面分割单元进行的处理。在第二实施例中，特征平面分割单元采用基于梯度方向和等深度水池的分水岭算法来对特征平面进行分割。

[0120] 下面以这个不同点为中心对第二实施例进行说明，对于与第一实施例相同的部分则不再复述。

[0121] 图15是第二实施例中的特征平面分割单元40所进行的处理的概略流程图。大体上说，在步骤S151中，从特征平面构建单元30输入特征平面。在S152中，根据输入的特征平面找出各山峰对应的初始区域，然后在S153中，对初始区域进行扩散，以将整个特征平面分割为若干区域，在S154中，将该分割结果输出给图层划分单元50。

[0122] 为简单起见，以下仍用一维的分水岭数据为例详细描述整个过程。同样需要注意的是，在本发明的彩色文档图像的分层方法中，待分类数据是二维平面，而且其高度与分水岭算法中的意义相反：本发明中待分类数据中每个山峰(地势高)对应于一类，而分水岭中每个积水盆地(地势低)对应于一类。

[0123] 图16是将此方法应用于一维数据时的实例。图16(a)是输入的一维数据。图16(b)显示了各积水盆地所对应的初始区域，首先计算各局部极小值点作为积水盆地的谷点，然后搜索该谷点所在邻域以获得一个连通域来作为该积水盆地的初始区域(S152)，使得连通域中所有点对应高度均低于该局部极大值加上常量δ。常量δ的取值可根据经验设定，例如，一般情况下可设为0.1。该实例中共获得了三个谷点，对应于三个积水盆地，经过搜索共得到了三个积水盆地所对应的初始区域r1、r2和r3。对各初始区域中的点进行标注，使得对应于同一积水盆地的各点标签相同，而对应于不同积水盆地的各点标签不同；
然后对已标注点的相邻未标注点进行标注，使得该相邻未标注点的标签与该已标注点的标签相同，如果某一未标注点同时与多个已标注点相邻，则按照高度最低的已标注点来进行标注(对应于S154)。经过扩散，获得了三个积水盆地的具体区域R1、R2和R3，如图16(c)所示。

[0124] 关于基于梯度方向和等深度水池的分水岭算法，例如可以参考以下文献：

[0125] Feng-Yang Hsieh，and Kuo-Chin Fan，“An unsupervised watershedclassifier based on gravity-space image”，8th IASTED Inter.Conf.on Signaland Image Processing 2006.

[0126] 下面采用二维的真实数据为例对该分类方法进行说明。图5是对一幅实际图像进行背景色估计以及映射所得到的特征平面。如图所示，特征平面上有四个峰谷，分别对应于特征平面应被划分的四个类。图17和图18显示了用上述基于梯度方向和等深度水池的分水岭算法对特征平面进行分割的过程。

[0127] 首先，计算该特征平面上各局部极小值点作为积水盆地的谷点，然后搜索该谷点所在邻域以获得一个连通域来作为该积水盆地的初始区域，如图17所示。共获得四个积水盆地的初始区域，分别以CDP1、CDP2、CDP3和CDP4表示。

[0128] 然后，对各积水盆地的初始区域进行扩散。第一步，对各初始区域中的点进行标注，使得对应于同一积水盆地的各点标签相同，而对应于不同积水盆地的各点标签不同；第二步，对已标注点的相邻未标注点进行标注，使得该相邻未标注点的标签与该已标注点的标签相同，如果某一未标注点同时与多个已标注点相邻，则按照高度最低的已标注点来进行标注。经过扩散，获得了四个积水盆地的具体区域C1、C2、C3和R4，如图18所示。

[0129] 接下来与上述第一实施例同样，图层划分单元50根据该特征平面分割单元40的分割结果、以及文档图像中各个像素点与特征平面中的点之间的对应关系，将输入文档图像上每一像素分类至对应的图层。与特征平面分割结果中的一个区域对应的像素被归为一类，而对应于特征平面分割结果中不同区域的像素被归为不同的类别。由此，根据文档图像中的像素的分类结果，将每一类像素划分为彩色文档图像中的一层。

[0130] 根据第二实施例，与上述第一实施例一样首先确定输入文档图像的背景色，将该文档图像中的每个像素点映射到以背景色为原点的RGB空间中，构建反映了该文档图像的像素点在以背景色为原点的RGB空间中的分布的特征平面，基于该特征平面中的密度分布将该特征平面分割为一个以上的区域，基于分割结果，将文档图像划分为一个以上的图层。同样地，充分利用了单一背景色的彩色文档图像中的颜色分布特性，能够准确地对彩色文档图像进行分层。

[0131] 如上所述，本发明的要点是，在彩色文档图像的分层中，确定所述文档图像的背景色；将所述文档图像中的每个像素点映射到以所述背景色为原点的RGB空间中；构建反映了所述文档图像的像素点在所述RGB空间中的分布的特征平面；基于所述特征平面中的密度分布将所述特征平面分割为一个以上的区域；基于所述分割结果，将所述文档图像划分为一个以上的图层。除此之外的各种细节并不构成对本发明的限制。

[0132] 例如，在上述的第一和第二实施例中，分别采用基于等高线的非监督式分类算法和基于梯度方向和等深度水池的分水岭算法来对特征平面进行分割。但是，本发明并不限于这些方法。实际上，对特征平面进行分割的具体方法并不是本发明的要点，可以采用各种方法来对特征平面进行分割。

[0133] 又例如，在上述第一和第二实施例中，在构建特征平面的过程中，通过将RGB空间中的每个点转换为极坐标系中的向量，并将该向量映射到以该极坐标系的角度为坐标轴的平面坐标系中，从而构建特征平面。但是本发明不限于此，也可以通过任何其他的方法来构建特征平面，只要该特征平面能够反映文档图像的各个像素点在RGB空间中的分布即可。

[0134] 另外，在上面的第一和第二实施例中，以彩色文档图像分层装置为中心对本发明进行了说明。但是本发明不限于该彩色文档图像分层装置，也可以实施为上述彩色文档图像分层装置所执行的彩色文档图像分层方法、使计算机等的信息处理设备执行该分层方法的程序、以及记录了该程序的存储介质。

[0135] 另外，在上述的说明中，各个单元被描述成单独的模块。但是，在物理上这些单元无需是相互分离的。此外可以通过任何方式来构建这些单元，例如，可以通过运行上述本发明的程序的计算机来实现本发明的彩色文档图像分层装置的各个单元。