Image analysis – Image segmentation
Reexamination Certificate
2000-10-02
2004-09-07
Ahmed, Samir (Department: 2623)
Image analysis
Image segmentation
C382S177000, C382S180000
Reexamination Certificate
active
06788814
ABSTRACT:
TECHNICAL FIELD
This invention pertains to the field of image analysis in computer systems, and, in particular, to improvements in graphical image feature extraction and skeletal representation. Accordingly, the general objects of the invention are to provide novel methods and apparatus of such character.
BACKGROUND ART
In the field of image analysis, thinning is a technique frequently used to extract meaningful features from graphical images for classifying objects. In computer geometry or mathematical morphology, there are several theoretical definitions of thinned objects (skeletons). The purpose of such thinning procedures is mainly to produce a less complex figure that might be used as an archetype for classification purposes. The idea of reducing a graphical object, such as a character or a drawing, to thin lines so that information relating to the object's actual shape is separated from accidental production errors (e.g., printing, scanning, hand drawing, compression-decompression, etc.) is very appealing. Currently, thinning is not feasible for thick objects, where the object and its thinned skeleton representations are not closely related, because different geometric shapes may engender the same skeleton. Nonetheless, important classes of graphical objects such as printed characters, engineering drawings, graphs, diagrams, etc. are typically thin objects and, therefore, do lend themselves to thinning procedures.
The field of skeletal representation of graphical objects is also presently restricted to instances in which the inaccuracies due to spurious branches created by thinning processes can be neglected. The problem of spurious branches is due to counterintuitive effects of current definitions and extreme sensitivity to small changes in the original object image.
It is hard to find a theoretical definition of a skeleton that overcomes these deficiencies. Consider, for example, the skeletal representation of a rectangle defined by the well-known medial axis algorithm. This skeleton follows the axis of symmetry of the rectangle (in accordance with intuition), but then bifurcates unexpectedly at each of the line ends. Slight irregularities of the rectangle edges in real images make things worse by adding new and erroneous branches. Such problems arise from the topological nature of the definition, which does not take into account the geometric shape of the object.
There are a large number of applications, such as document analysis, where there is a preferred orientation of an image. In this kind of application, the ability to recognize an object in its preferred position may overcome the above-noted deficiencies. Therefore, thinning procedures theoretically could be used in these applications because they do not have to rely on topology and need not be affine-invariant.
In order to overcome the above-noted deficiencies of the related art, it would be desirable to have improved procedures and apparatus that reduce to thin lines graphic objects pictured by a set of strokes (i.e., line segments). These thin lines would preferrably keep the essential information about the geometric shape of the object, but do not have to be affine-invariant.
DISCLOSURE OF INVENTION
The present invention includes methods (
500
) and computer apparatus (
620
) for obtaining a skeletal representation (
400
A) of an image (
100
). Although the present invention is primarily described with reference to the processing of a single connected component (
110
) of an image (
100
), it can readily be extended to cover the processing an image (
100
) having multiple connected components (
110
and
120
) with exercise of ordinary skill in the art.
As shown in
FIG. 1
, a given connected component (
110
) of a multi-connected-component image (
100
) can be represented as a list of horizontal runs or slices (
300
), wherein each slice (
300
(i)) is represented by a node. An initial connected component graph (
305
) is produced by connecting with an edge (
330
) every two nodes (
320
and
340
) that represent slices (
300
(
1
) and
300
(
2
)) adjacent to each other in the connected component (
110
). This initial connected component graph (
305
) can be converted into a collapsed component graph or L-Graph (
305
C) by replacing each maximal line-subgraph (
368
)(each line-subgraph corresponding to a line segment (
112
) of the connected component (
110
)) within the connected component graph (
305
) by a collapsed edge (
368
C). The resulting collapsed component graph or L-Graph (
305
C) representation is used to efficiently store, manipulate and/or transmit topological information about the connected component (
110
).
In accordance with the present invention, the connected component (
110
) is “thinned,” i.e., converted into a skeletal representation, by (1) identifying a minimal bounding rectangle (MBR) (
112
A) of each line segment (
112
) in the connected component (
110
), (2) forming thin lines (
112
T,
410
and
420
) by connecting at least substantially centroid pixels of the slices within each MBR (
112
A), and (3) connecting disconnected thin lines (
410
and
420
) using additional pixels (
415
) to make a thin-lined connected graph (
400
A) having the same connectivity as the connected component (
110
).
REFERENCES:
patent: 5025479 (1991-06-01), Pastor
patent: 5067165 (1991-11-01), Nishida
patent: 5539840 (1996-07-01), Krtolica et al.
patent: 5583949 (1996-12-01), Smith et al.
patent: 5644648 (1997-07-01), Bose
patent: 0949579 (1999-10-01), None
Krtolica, “Box Connectivity Approach to Multifont Character Recognition”, Proceeding of SPIE—The International Society for Optical Engineering 1994, pp. 315-321.*
Li, “Skeletonizing by compressed line adjacency graph in two directions”, IEEE Signal Process. Soc, 1996, pp. 17-20 vol. 3.*
Krtolica, “Learning character recognition by localized interpretation of character-images”, IEEE Signal Process. Soc, 1997, pp. 292-295 vol. 3.*
Krtolica, “Two-Stage box Connectivity Algorithm for Optical Character Recognition”, IEEE Comput. Soc. Press, 1993, pp. 179-182.*
Author unknown, “Standardization of Group 3 Fascimile Terminals For Document Transmission”, International Telecommunication Union, Recommendation T.4, Apr. 1999.
Author unknown, “Facsimile Coding Schemes and Coding Control Functions for Group 4 Facsimile Apparatus”, International Telecommunication Union, Recommendation T.6, 1988, 1993.
Srihari, Sargur N., et al., “Pattern Recognition: A Survey”, The Encyclopedia of Computer Science and Engineering, 3rdEd., 1992.
Ahmed Samir
Canon Kabushiki Kaisha
Fitzpatrick ,Cella, Harper & Scinto
Le Brian Q
LandOfFree
Graph based thinning of graphical objects does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Graph based thinning of graphical objects, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph based thinning of graphical objects will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3245262