A method for combining complementary techniques for document image segmentation

Image segmentation is a major task of handwritten document image processing. Many of the proposed techniques for image segmentation are complementary in the sense that each of them using a different approach can solve different difficult problems such as overlapping, touching components, influence of author or font style etc. In this paper, a combination method of different segmentation techniques is presented. Our goal is to exploit the segmentation results of complementary techniques and specific features of the initial image so as to generate improved segmentation results. Experimental results on line segmentation methods for handwritten documents demonstrate the effectiveness of the proposed combination method.     

一种基于Delaunay三角化的手写体文字细化方法

为了对手写体文字进行快速准确的识别，基于Delaunay三角化方法，提出了一种新的文字图象细化算法，该算法首先通过对文字图象边界的近似多边形进行Delaunay三角化，同时把其分成一系列保持拓扑关系的三角形，然后根据三角形的类型生成不同的局部骨架；最后连接生成整文字图象的骨架，由于该算法充分利用了图象的全局和局部信息，因此具有速度快，效果好等优点。     

Generalization of Frei and Chen's approach to extract the lines and edges of a digital image

This work proposes the generalization to any k dimension of the approach suggested by Frei and Chen for line and edge detection in a digital image with square masks. With the proposed algorithm we can obtain information about the image lines and edges without modifying the rest of the image. To test these results we have applied the algorithm to biomedical images and geophysical images of archaeological prospections achieving optimal results.     

On sorting triangles in a delaunay tessellation

In a two-dimensional Delaunay-triangulated domain, there exists a partial ordering of the triangles (with respect to a vertex) that is consistent with the two-dimensional visibility of the triangles from that vertex. An equivalent statement is that a polygon that is star-shaped with respect to a given vertex can be extended, one triangle at a time, until it includes the entire domain. Arbitrary planar triangulations do not possess this useful property which allows incremental processing of the triangles.This work was partially supported by the National Science Foundation's US-Italy Collaborative Research Program under Grant INT-8714578 and Information, Robotics, and Intelligent Research Grant IRI-8704781.     

一种基于映射法的散乱点云Delaunay三角剖分算法

针对直接在三维空间构建海量点云的Delaunay三角网格效率低下,提出一种新的基于映射法的Delau-nay三角网格构建算法.首先提出一种基于区域增长法的点云分片方法,能够保证对分片后的点云数据进行映射而不产生重叠;然后保持空间点云之间的距离特性,将三维点云映射到二维平面;在二维平面内进行Delaunay三角剖分,再将结果返回到三维空间内.实验结果表明,算法能够构建质量较好的三角网格.由于该算法将点云的三角剖分转换到低维空间,通过实验结果对比本算法与其他算法效果,证明该方法能够更快地完成重构.     

复杂版面的文本图像图文分割算法

为了满足办公自动化的实时性要求,本文提出了一种改进的自顶向下的图文分割算法。该方法利用文本行基线之间的距离自适应的确定结构元素的大小,克服自顶向下算法要求对页面有先验知识的缺点。实验表明,本文提出的算法分割准确,速度快。     

基于SLIC与Delaunay图割的交互式图像分割算法

针对现有的交互式图像分割算法在处理高分辨率图像时仍不够高效的问题,提出了一种基于简单线性迭代聚类（simple linear iterative clustering,SLIC）与Delaunay图割的交互式图像分割算法。使用一种简化但是高效的SLIC算法将图像分割为多个在感知上有意义的原子区域,并提取这些区域的代表像素点;对处在背景矩形框内的代表像素点进行Delaunay三角剖分,构建图结构;最后利用最小割最大流算法将图中的节点分为两部分,并将这些节点对应为相应的原子区域,达到将图像分割为前景和背景的目的。与其他交互式图像分割算法进行实验对比,结果表明所提算法在计算效率上有较大提升,并更为准确。     

Delaunay三角剖分在离群点检测中的应用

在传统的基于[K]近邻的算法中,需要为算法设置邻居参数[k]的值,只有具备相关的先验知识才能确定合适的参数值。为了减少参数对于离群点检测的影响,提出了一种无需参数的基于Delaunay三角剖分的离群点检测算法。Delaunay三角剖分是数值分析以及图形学中的重要基础理论,它的构建无需任何参数,在三角剖分图中的每个数据对象与它空间上相邻的点都存在边直接相连,因此可以形成一种有效的邻居关系。算法首先通过Delaunay三角剖分形成每个点的空间邻居集合,然后根据每个点与它们空间邻居之间的分布特征,计算它们的离群程度,根据离群程度的大小判断该点是否为离群点。通过实验与相关的算法比较,算法具有更好的效果。     

基于Delaunay三角剖分的印鉴识别算法

针对印鉴图像姿势纠正及印鉴匹配处理,引入计算几何中平面点集的三角剖分方法--Delaunay三角剖分方法和基于此的多边形三角剖分方法,并提出一种基于DT网格的印鉴识别方法.通过对两种细节点(基于线条的细节点和基于多边形的细节点)的拓扑结构进行DT三角划分,把空间上位置相近的细节点按照一定的规则相连,得到DT三角形网格,并基于该网格寻找若干参考点对,根据获得的参考点对将两幅印鉴图像进行姿势调整,使用获得的参考点对实现基于点模式的印鉴匹配.经分析该方法可以获得较多的参考点,确保了印鉴旋转、印鉴平移参数计算结果的准确性,有效地提高了最终的识别效果.     

Two algorithms for constructing a Delaunay triangulation

This paper provides a unified discussion of the Delaunay triangulation. Its geometric properties are reviewed and several applications are discussed. Two algorithms are presented for constructing the triangulation over a planar set ofN points. The first algorithm uses a divide-and-conquer approach. It runs inO(N logN) time, which is asymptotically optimal. The second algorithm is iterative and requiresO(N ²) time in the worst case. However, its average case performance is comparable to that of the first algorithm.This work was supported in part by the National Science Foundation under grant MCS-76-17321 and the Joint Services Electronics Program under contract DAAB-07-72-0259.     

An empirical measure of the performance of a document image segmentation algorithm

Document image segmentation is the first step in document image analysis and understanding. One major problem centres on the performance analysis of the evolving segmentation algorithms. The use of a standard document database maintained at the Universities/Research Laboratories helps to solve the problem of getting authentic data sources and other information, but some methodologies have to be used for performance analysis of the segmentation. We describe a new document model in terms of a bounding box representation of its constituent parts and suggest an empirical measure of performance of a segmentation algorithm based on this new graph-like model of the document. Besides the global error measures, the proposed method also produces segment-wise details of common segmentation problems such as horizontal and vertical split and merge as well as invalid and mismatched regions. Received July 14, 2000 / Revised June 12, 2001[-1mm]     

分布式Delaunay三角剖分在栅栏覆盖中的应用

提出了一种有效的双向边分布式造构Delaunay三角剖分拓扑图算法（MEDDEL）,该算法仅利用一跳邻居节点的信息,高效构造MEDDEL拓扑图,避免了大量通信代价和能量消耗。然后给出了MEDDEL拓扑图下支撑值计算的证明。最后在传感器能量模型和MEDDEL拓扑图下,利用分布式最佳覆盖路下的最短穿越和最小能耗算法（SMBCP）解决无线传感器网络中栅栏覆盖最佳路径的问题。仿真实验结果分析表明,与RNG、GG、PLDEL、UDEL、DEL相比较,在MEDDEL拓扑结构下寻找到路径支撑值最小的情况下,运行SMBCP算法能找到最佳覆盖路径下的最短穿越路径和最小能耗路径。     

Table form document analysis based on the document structure grammar

Structure analysis of table form documents is an important issue because a printed document and even an electronic document do not provide logical structural information but merely geometrical layout and lexical information. To handle these documents automatically, logical structure information is necessary. In this paper, we first analyze the elements of the form documents from a communication point of view and retrieve the grammatical elements that appear in them. Then, we present a document structure grammar which governs the logical structure of the form documents. Finally, we propose a structure analysis system of the table form documents based on the grammar. By using grammar notation, we can easily modify and keep it consistent, as the rules are relatively simple. Another advantage of using grammar notation is that it can be used for generating documents only from logical structure. In our system, documents are assumed to be composed of a set of boxes and they are classified as seven box types. Then the box relations between the indication box and its associated entry box are analyzed based on the semantic and geometric knowledge defined in the document structure grammar. Experimental results have shown that the system successfully analyzed several kinds of table forms.     

基于Delaunay三角剖分生成Voronoi图算法

针对Delaunay三角网生长算法和间接生成Voronoi图算法构网效率不高的问题,提出了一种Delaunay三角网生长法间接生成Voronoi图的改进算法。该算法以点集凸壳上一边快速生成种子三角形,定义了半封闭边界点的概念,在三角形扩展过程中动态删除封闭点及半封闭边界点,加快Delaunay三角网生成速度。然后又定义了有序目标三角形的概念,该算法能迅速查找点的有序目标三角形,生成无射线的Voronoi图;考虑凸壳上点的特性,借助三个无穷点生成带射线的Voronoi图。通过实验结果分析表明,改进的算法执行效率有了很大提高。     

基于图层分割的文档图像压缩方法

传统的图像压缩技术,大都基于图像空域和色度空间同质性的假定,在文档图像的压缩中并不能取得最好的压缩效果。针对文档图像的特点,提出了一种基于图层分割的文档图像压缩方法。该方法首先利用多尺度的2色聚类算法进行文档图像的图层分割,然后根据不同图层的特征,分别采用效果最佳的压缩技术,能够获得比传统的方法更好的压缩效果。     

一种基于Delaunay三角化的笔划分割算法

字符笔划在字符识别等领域中存在广泛的应用。针对字符图形的骨架化及笔划提取，本文提出了一种基于动态约束Delaunay三角割分的算法。该方法首先通过对字符的轮廓多边形进行三角剖分，生成一系列具有拓扑关系的三角形．再根据三角形的三种类型生成各三角形骨架，并连接为整个字符的骨架。然后定义了骨架的平滑度函数及分支长度阈值，消除了畸变分支，并根据得到的骨架进行笔划分割。实验结果表明，该算法具有快速稳定的特点且鲁棒性较好。     

Handwritten document image segmentation into text lines and words

Two novel approaches to extract text lines and words from handwritten document are presented. The line segmentation algorithm is based on locating the optimal succession of text and gap areas within vertical zones by applying Viterbi algorithm. Then, a text-line separator drawing technique is applied and finally the connected components are assigned to text lines. Word segmentation is based on a gap metric that exploits the objective function of a soft-margin linear SVM that separates successive connected components. The algorithms tested on the benchmarking datasets of ICDAR07 handwriting segmentation contest and outperformed the participating algorithms.     

基于Delaunay三角剖分密度度量的聚类算法

针对K-means聚类算法无法正确识别非凸形状簇的缺陷,提出一种基于Delaunay三角剖分密度度量的聚类方法,利用Delaunay三角剖分图的最近性、邻接性等优良特性来反映数据自身特点并进行密度度量,同时以混沌优化方法实现聚类目标函数的全局优化,达到全局最小解。实验结果证明,基于Delaunay三角剖分密度度量方式的聚类算法能发现任意非凸形状簇。     

一种基于Delaunay三角化的笔划分割算法

字符笔划在字符识别等领域中存在广泛的应用。针对字符图形的骨架化及笔划提取,本文提出了一种基于动态约束Delaunay三角剖分的算法。该方法首先通过对字符的轮廓多边形进行三角剖分,生成一系列具有拓扑关系的三角形,再根据三角形的三种类型生成各三角形骨架,并连接为整个字符的骨架。然后定义了骨架的平滑度函数及分支长度阈值,消除了畸变分支,并根据得到的骨架进行笔划分割。实验结果表明,该算法具有快速稳定的特点且鲁棒性较好。