- 上一篇：破碎机偏心速度英文文献和中文翻译
- 下一篇：模糊PID控制算法英文文献和中文翻译
These observations enable us to draw up a list of various segmentation errors: These some observations enable us to draw up a list of various segmentation errors: horizontal or vertical merging or splitting of text blocks or lines, text fusion or confusion with graphics or noise, bad detection of textual blocks or lines, text fusion or confusion with graphics or noise. The merging segmentation methods (progressive regrouping of connected components, RLSA, segmentation by scaling method of cumulated gradients) are more used by the bottom-up strategies [5] [6], whereas the methods of segmentation by splitting (profile projection [19][4], segmentation by spaces analysis, Hough’s transform [17]) are adapted to the top-down strategies. Other methods, known as hybrid, benefit from the two strategies at the same time [7]. The projection profile based technique detects the text lines by creating a histogram at each possible location [4]. Hough Transform is usually used for locating skewed text lines. It is applied on a set of selected angles along each angle straight lines are determined with a measurement for the fit. The best fit for the lines gives the skew angle and the location of the lines. Hough Transform can be applied on all black pixels, on reduced data from horizontal and vertical runlength computations [18] or only on the gravity centers of the connected components [17]. Another method uses the nearest neighbor clustering of connected components. It works by grouping small components satisfying several heuristic constraints into successively larger components to form lines then blocks of text. Basing in this principal, Déforges and Barba [6] presented a bottom-up generic method based on a multi-resolution description of the document image used in address-block localization. An almost similar structure was used by Wang [8] to distinguish the text blocks from graphic blocks, and to represent them in a structural model. Shi and Govindaraju [12] proposed an algorithm based on the application of "fuzzy directional run-length". A postal envelope segmentation method combining 2-D histogram and morphological clustering by watershed transform concepts was proposed by Yonekura and Facon [19]. The Segmentation task consists in detecting the 2- D histogram modes associated with homogeneous regions in envelope. The homogeneous modes in 2-D histogram are segmented through the morphological watershed transform. All the physical layout segmentation methods, mentioned above make use of complex data structures. The management of the criteria and knowledge becomes more difficult so it cannot control the great variability of envelopes to be sorted. Starting from these remarks, our proposal uses a mixed strategy of segmentation more adapted to the postal mails. The high level stages are based on a hierarchical graphs coloring, allowing to manage through a pyramidal data organization, the compound rules governing the interpretation of the decomposition into connected components of interest zones. Today, no other work in this context has made use of the powerfulness of this tool. 3. Formal aspects of the graph coloring Various practical classification problems can be modeled by the graph coloring. The general form of these applications requires the formation of a graph by the nodes (vertex) which represent the objects of interest and the edges (arcs) which define the relations between these objects. A natural question is then to determine: what is the minimum number of classes required to split a set of objects (connected components, lines and blocks) into several homogeneous subsets. This question can be modeled in terms of graph coloring as follows: One wants for example to group several connected components into homogeneous text lines without knowing their a priori number. In doing so, it is sufficient to represent each component c(i) by a node viand to add an edge E(vi,vj) between each pair of sufficiently different components. The finite graph G=(V, E) is defined by the finite set V = {v1, v2, ..., vn}(|V| = n) whose elements are called nodes, and by the finite set E= {e1, e2, ..., em} (|E| = m) whose elements are called edges. The coloring of the nodes of the graph G(V,E)consists in assigning to all nodes a color so that two adjacent (dissimilar) nodes do not carry the same color. These colors will correspond to the various text lines. Thus a coloring with k colors is a partition of the set of nodes in k homogeneous subsets. The number of colors used to color the graph G of n nodes is called chromatic number (G) n which represents the smallest integer k for which there is a partition of Vinto k homogeneous subsets [9]. On the graph G of figure 3, the set V of 11 various shapes is represented by the nodes {v1,...,v11}, four colors were needed to color the 11 nodes so that two adjacent nodes can not have the same color. The majority of the (G) evaluations come from coloring algorithms. Many of them exist, and so that not to drown ourselves with this question, we will limit ourselves to quoting the comparative study of Paschos [9]. In our study, we are particularly interested by the distributed algorithm of graph coloring proposed by Effantin et Kheddouci in [10], [11]. 4. Application of graph coloring to our problem The segmentation technique objective is based on its decision strategy which defines a best block extraction manner in order to recognize it by the block-address recognition module. The segmentation techniques cannot systematically produce uniform and good located blocks in complex environments (difficult envelopes). Consequently, the knowledge delivered by the descriptors of non-homogeneous blocks (containing parasitic elements) is less discriminating. The diagram of figure 5 represents the stages of our physical layout segmentation method. In order to improve the robustness and exactness of segmentation, it has been necessary to choose an even more advanced tool. The idea is to use a hybrid strategy of segmentation using the richness of pyramidal structure. Our method is mainly based on the powerfulness of graph coloring to regroup correctly the connected components into text lines then the lines into blocks.