Image analysis – Pattern recognition – Feature extraction
Reexamination Certificate
1993-12-03
2002-06-11
Chang, Jon (Department: 2623)
Image analysis
Pattern recognition
Feature extraction
C382S199000
Reexamination Certificate
active
06404921
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a method and apparatus for extracting contour lines of a binary image stored in the sequence of raster scanning.
2. Description of the Related Art
Heretofore, when, for example, forming an outline font from a binary dot pattern, contour lines of a binary image character pattern are extracted and stored in the form of vector information, and an outline font of a character is formed from the stored information. Such extraction of contour lines by a binary image is started from finding the start point for tracking a contour line of the binary image. When the start point for tracking has been found, a contour of the image is sequentially tracked from the start point, and tracking is continued while successively providing tracked contour points with marks indicating the completion of tracking. One contour point string (a contour line) is obtained when a loop is formed as a result of tracking. By repeating such a procedure, all the contour lines of the image can be extracted.
FIG. 2
shows an example of the procedure of a well-known contour tracking operation using 8 adjacent pixels. In
FIG. 2
, a binary image pattern
201
includes a blank portion
202
in an inner portion thereof. A case of extracting contour lines of this pattern will be explained. In
FIG. 2
, one section represents one dot (pixel (picture element)).
(1) The binary image pattern
201
is subjected to raster scanning from a reference point (0, 0) of the picture surface.
(2) If the raster scanning hits a point (for example, dot
203
) not having a mark indicating the completion of tracking, contour tracking of the dot pattern is started from that point P
0
. If such a point P
0
is absent in the entire picture surface, the procedure is terminated.
(3) Tracking is started in the sequence shown in
FIG. 3
in the directions of 8 pixels adjacent to the start point P
0
. A point where a pixel is first met (dot
204
in the case of
FIG. 2
) is made to be the next contour point P
1
. If no adjacent point is present, the point is made to be an isolated point, and the process returns to procedure (2).
(4) After marking a contour point P
i
in the above-described manner, the next contour point P
i+1
is extracted from among 8 pixels adjacent to the point P
i
, as shown in FIG.
4
. In searching if any dot is present in the counterclockwise direction around the point P
i
(dot
402
) starting from a point
401
which has just been marked, a point where a pixel is first met is made to be the next contour point P
i+1
.
(5) Subsequently, contour points are successively obtained by repeating the above-described procedure (4).
If P
n+1
=P
1
and P
n
=P
0
, the contour line string of one region is formed by points P
0
, P
1
, . . . , P
n−1
, and the process proceeds to procedure (6).
(6) The process returns to procedure (2) in order to obtain the contour line string of another image region.
Thus, contour tracking is completed. In
FIGS. 3 and 4
, point represents a target point, and point ⊙ (
401
) represents a point which has just been marked. Numerals shown in
FIGS. 3 and 4
indicate the sequence of searching the presence of a pixel (dot).
In the above-described conventional approach, however, since tracking along a contour line is performed after determining the start point for contour tracking, processing of extracting the contour line must be started after receiving the entire image in a memory. Accordingly, the needed capacity of the memory is increased, causing, for example, an increase in the production cost and processing time.
Furthermore, since the start point for the next contour is detected by another raster scanning after extracting one contour point string, pixels which have already been searched are searched again, causing an increase in the amount of calculation of image data, and a decrease in processing speed.
In the above-described conventional approach, a contour is tracked along a center of a pixel (dot), not along sides of a pixel (dot) as shown in FIG.
2
. Hence, if a dot pattern having a width of one dot is tracked, the width of the detected contour line is reduced to zero width rather than a one dot width.
SUMMARY OF THE INVENTION
The present invention has been made in consideration of the above-described problems.
It is an object of the present invention to provide a contour extraction apparatus and method which can extract all contours contained in an image with one raster scanning by performing raster scanning of the image, extracting a contour while moving the position of a target pixel, determining the position of the target pixel and the presence of black points in pixels adjacent to the target pixel, extracting candidates for the start points and the end points of vectors on a contour vector string in accordance with the state of the black points, and determining the start point and the end point connected to these candidates.
It is a further object of the present invention to provide a contour extraction apparatus comprising hold means (e.g., latches) for holding states of target pixels and pixels adjacent to the respective target pixels in image data, detection means for taking out the target pixel in the sequence of raster scanning, and detecting a pixel arranging vector in the horizontal direction and in the vertical direction according to the state of the target pixel and pixels adjacent to the target pixel, determination means for determining a state of connection between the pixel arrangement vectors, and extraction means for extracting a contour of the image data according to the state of connection between the pixel arrangement vectors determined by the determination means.
It is a still further object of the present invention to provide a contour extraction method comprising the steps of selecting a point in the image data according to a state of a target pixel and pixels adjacent to the target pixel a point constituting a contour line and determining a direction of connection of points of the contour line according to a state of the adjacent pixels, determining a state of connection between the point constituting the contour line and another point of the contour line, and setting the position of the target pixel in image data in the sequence of raster scanning and extracting a contour point by executing the above-described steps according to the state of adjacent pixels for every target pixel.
It is still another object of the present invention to provide a contour extraction method which holds states of target pixels and pixels adjacent to the respective target pixels in image data, takes out the target pixel in the sequence of raster scanning, detects a pixel arranging vector in the horizontal direction and in the vertical direction according to the state of the target pixel and pixels adjacent to the target pixel, determines a state of connection between the pixel arranging vectors, and extracts a contour of the image data according to the determined state of connection state between the pixel arranging vectors.
REFERENCES:
patent: 4368462 (1983-01-01), Crawley
patent: 4524454 (1985-06-01), Ejiri
patent: 4777651 (1988-10-01), McCann et al.
patent: 4956869 (1990-09-01), Miyatake et al.
patent: 4961231 (1990-10-01), Nakayama et al.
patent: 5091976 (1992-02-01), Murayama
patent: 5228097 (1993-07-01), Kumagai
patent: 2201562 (1986-09-01), None
patent: 1-277976 (1989-08-01), None
patent: 2-171875 (1990-07-01), None
“Fast Binary-Image Boundary Extraction”, W.H.H.J. Lunscher, et al., Computer Vision Graphics And Image Processing, vol. 38, No. 3, Jun. 1987 pp. 229-257.
“An Improved Algorithm For The Sequential Extraction Of Boundaries From A Raster Scan”, David W. Capson, Computer Vision Graphics And Image Processing, vol. 28, No. 1, Oct. 1984, pp. 109-125.
LandOfFree
Contour extracting method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Contour extracting method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Contour extracting method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2962251