论文部分内容阅读
摘要：专利全文是专利数据中最重要的内容之一，全文中的示意图、化学式等图形对于专利用户快速了解专利内容具有重要意义，也是实现图形检索的基础。本文给出了一种应用RLSA（Run Length Smoothing Algorithm），Connected Component Labeling等算法检测专利全文中图形的方案。
关键词：图形检测，专利全文，RLSA，连通域分析，Connected Component
检测方法
算法流程如图1所示。主要思路文本字符经RLSA平滑处理后相互连接形成文本行。文本行相对于单个文本字符特征更明显，因此也更易检测。同时在试验中，我们发现RLSA的处理结果可能因专利全文图片中含有表格、分隔线等等直线干扰，因此在RLSA的基础上引入了直线检测和过滤步骤，以改善检测效果。
图1算法流程
* 预处理
一些较早的专利图片存在一定角度的倾斜，需在RLSA处理前进行倾斜检测和纠偏。霍夫变换（Hough Transform）是计算偏斜角度的常见方案，但其计算成本较高。W. Postl （1988）发现了一种速度很快且保持良好纠偏效果的算法，leptonica1提供该基于算法的一种实现。
另外，实验还发现专利全文图片页边的条码等内容，对文本/图片分类也会产生干扰，需提前移除。可分析专利图片在X轴（Y轴）投影直方图（Projection Profile Histogram），检测间断，进而完成页边内容的移除。
* 直线检测及RLSA
二值图像中，常用0，1代表白色和黑色像素，相邻的0（或1）称为一个游程（Run），0（或1）重复的次数称为游长（Run Length）。RLSA的转换规则是若中0的游长不大于给定阈值c，则将游程中的0转换成1。例，若c=5，则f：00110000001001110001100000100
被RLSA转换为g：11110000001111111111100000111
即RLSA的作用就是将两个间距不超过c的游程合并成一个连续的游程。
由于文档中的文本等元素在水平和垂直方向的间距不同，应为水平和垂直方向选择不同的参数c。由于参数选择的不同，有时RLSA将表格或其他相互连接的水平/垂直的直线也识别成图形，这并不是我们期望的结果，因此我们在RLSA步骤中增加直线检测以移除较长的直线，此外我们还加入了噪音过滤。改进后的步骤如下，
1.对原始图片P中的白色像素应用水平方向的RLSA，参数为CI1，得到的图片记为Pt1；
2.记P中垂直方向黑色像素的游长为RL1，若RL1>Cv1，则将Pt1中对应像素改为黑色；
3.从P中移除Pt1中的黑色像素；
4.对原始图片P中的黑色像素应用垂直方向的RLSA，参数为Cv，得到图片记为Pt2；
5.记P中水平方向白色像素的游长为RL，Pt2中水平方向白色像素的游长为RLt2：
若RL>C1，则将Pt中对应像素改为白色；
若RL│Ca，则将Pt中对应像素改为黑色；
若Ca 步骤2、3、4在实现时可以合并处理。若步骤4和步骤2得到的游程为
f=001110001
ft1=00011000
那么步骤3产生了新的游程
f│ft1=001000000
* 图片分段
图片分段（Segmentation）即把图片分成若干区域，把相近的像素放在同一个区域，产生的子区域也被称为块（Block）。在分段后即可根据每个区域的特征创建描述符。这些描述符帮助我们标记对应区域是属于文本、图形或是其他区域。本文应用分量分析（Connected Component Labeling）算法。连通区域分析是图像处理、模式识别中的常用基本方法，它将图像中具有相同像素值且位置相邻的前景像素点组成连通区域。根据相邻的定义，根据像素的相邻关系，又分为4连通区域分析和8连通区域分析；算法的实现根据需要扫描遍历像素的次数，又分为两边扫描（Two-Pass Scan）和单遍扫描（Single-Pass Scan）。
* 指标计算和区域分类
对于任意区域，定义以下参数，
>X-轴、Y-轴、宽度、高度，记为（xmin，ymin，│x，│y）。
>原图对应区域中的黑色像素数（N）。
>原图对应区域中水平方向白色│黑色像素切换的次数（TH）。
>原图对应区域中垂直方向白色│黑色像素切换的次数（TV）。
>原图中包含至少一个黑色像素的列的数量（δχ）。
计算指标如下，
>区域高度，H=│y
>宽高比，R=│x-│y
>面积，S=│x│y
>像素密度，
>单位宽度RLSA│转换次数，
>单位宽度RLSAv转换次数，
>单位高度RLSA│转换次数，
* 后处理
经过文本/图形检测分类之后的区域仍然需要进一步加工。主要目的是：
1. 通过区域大小、区域处在专利中的位置，从检测结果中排除Logo，条码等非目标图形。
2. 依据是区域间的距离将临近的图形区域合并。
本阶段的处理往往需要参考特定国家/专利局专利全文图片自身布局的特点，本文不做详细展开。
结束语
本文从专利检索的现实需求出发，构建了一种基于RLSA从专利全文中检测图形的方法。该算法容易理解，已使用Java实现。实验证明，本文算法计算快速，对多国专利图片都具有良好的适应性。
参考文献
[1]Frank Y. Shih， Image Processing and Pattern Recognition： Fundamentals and Technique
[2]Jaekyu Ha等， Recursive X-Y cut using bounding boxes of connected components
[3]http：//www.leptonica.com/local-sources.html
关键词：图形检测，专利全文，RLSA，连通域分析，Connected Component
检测方法
算法流程如图1所示。主要思路文本字符经RLSA平滑处理后相互连接形成文本行。文本行相对于单个文本字符特征更明显，因此也更易检测。同时在试验中，我们发现RLSA的处理结果可能因专利全文图片中含有表格、分隔线等等直线干扰，因此在RLSA的基础上引入了直线检测和过滤步骤，以改善检测效果。
图1算法流程
* 预处理
一些较早的专利图片存在一定角度的倾斜，需在RLSA处理前进行倾斜检测和纠偏。霍夫变换（Hough Transform）是计算偏斜角度的常见方案，但其计算成本较高。W. Postl （1988）发现了一种速度很快且保持良好纠偏效果的算法，leptonica1提供该基于算法的一种实现。
另外，实验还发现专利全文图片页边的条码等内容，对文本/图片分类也会产生干扰，需提前移除。可分析专利图片在X轴（Y轴）投影直方图（Projection Profile Histogram），检测间断，进而完成页边内容的移除。
* 直线检测及RLSA
二值图像中，常用0，1代表白色和黑色像素，相邻的0（或1）称为一个游程（Run），0（或1）重复的次数称为游长（Run Length）。RLSA的转换规则是若中0的游长不大于给定阈值c，则将游程中的0转换成1。例，若c=5，则f：00110000001001110001100000100
被RLSA转换为g：11110000001111111111100000111
即RLSA的作用就是将两个间距不超过c的游程合并成一个连续的游程。
由于文档中的文本等元素在水平和垂直方向的间距不同，应为水平和垂直方向选择不同的参数c。由于参数选择的不同，有时RLSA将表格或其他相互连接的水平/垂直的直线也识别成图形，这并不是我们期望的结果，因此我们在RLSA步骤中增加直线检测以移除较长的直线，此外我们还加入了噪音过滤。改进后的步骤如下，
1.对原始图片P中的白色像素应用水平方向的RLSA，参数为CI1，得到的图片记为Pt1；
2.记P中垂直方向黑色像素的游长为RL1，若RL1>Cv1，则将Pt1中对应像素改为黑色；
3.从P中移除Pt1中的黑色像素；
4.对原始图片P中的黑色像素应用垂直方向的RLSA，参数为Cv，得到图片记为Pt2；
5.记P中水平方向白色像素的游长为RL，Pt2中水平方向白色像素的游长为RLt2：
若RL>C1，则将Pt中对应像素改为白色；
若RL│Ca，则将Pt中对应像素改为黑色；
若Ca
f=001110001
ft1=00011000
那么步骤3产生了新的游程
f│ft1=001000000
* 图片分段
图片分段（Segmentation）即把图片分成若干区域，把相近的像素放在同一个区域，产生的子区域也被称为块（Block）。在分段后即可根据每个区域的特征创建描述符。这些描述符帮助我们标记对应区域是属于文本、图形或是其他区域。本文应用分量分析（Connected Component Labeling）算法。连通区域分析是图像处理、模式识别中的常用基本方法，它将图像中具有相同像素值且位置相邻的前景像素点组成连通区域。根据相邻的定义，根据像素的相邻关系，又分为4连通区域分析和8连通区域分析；算法的实现根据需要扫描遍历像素的次数，又分为两边扫描（Two-Pass Scan）和单遍扫描（Single-Pass Scan）。
* 指标计算和区域分类
对于任意区域，定义以下参数，
>X-轴、Y-轴、宽度、高度，记为（xmin，ymin，│x，│y）。
>原图对应区域中的黑色像素数（N）。
>原图对应区域中水平方向白色│黑色像素切换的次数（TH）。
>原图对应区域中垂直方向白色│黑色像素切换的次数（TV）。
>原图中包含至少一个黑色像素的列的数量（δχ）。
计算指标如下，
>区域高度，H=│y
>宽高比，R=│x-│y
>面积，S=│x│y
>像素密度，
>单位宽度RLSA│转换次数，
>单位宽度RLSAv转换次数，
>单位高度RLSA│转换次数，
* 后处理
经过文本/图形检测分类之后的区域仍然需要进一步加工。主要目的是：
1. 通过区域大小、区域处在专利中的位置，从检测结果中排除Logo，条码等非目标图形。
2. 依据是区域间的距离将临近的图形区域合并。
本阶段的处理往往需要参考特定国家/专利局专利全文图片自身布局的特点，本文不做详细展开。
结束语
本文从专利检索的现实需求出发，构建了一种基于RLSA从专利全文中检测图形的方法。该算法容易理解，已使用Java实现。实验证明，本文算法计算快速，对多国专利图片都具有良好的适应性。
参考文献
[1]Frank Y. Shih， Image Processing and Pattern Recognition： Fundamentals and Technique
[2]Jaekyu Ha等， Recursive X-Y cut using bounding boxes of connected components
[3]http：//www.leptonica.com/local-sources.html