JPH04579A - Method for extracting feature point of graphic - Google Patents

Abstract

PURPOSE:To rapidly vectorize a graphic by extracting the linear parts of four prescribed directions out of picture element strings constituting the outline of an image and setting up the end point of each linear part as a feature point. CONSTITUTION:The outline of binary image data inputted to an image input part 1 is traced by an outline tracing part 2 and its coordinates are outputted. Out of picture elements constituting the extracted outline, the end points of linear parts of the four prescribed directions are regarded as feature points and extracted by a feature point extracting part 3. A coordinate output part 4 outputs the coordinates of the feature points. In this method, only the coordinate points expressed by slashed squares are extracted as feature points, i.e. outline coordinates.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a method for extracting feature points of a figure by approximating the contour shape of a binary image by line segments.

[Background Art] In recent years, there has been an increasing demand for using character recognition devices, graphic recognition devices, and the like as input devices for computers and the like. Image recognition systems such as character recognition devices and graphic recognition devices need to extract feature points of the contour shape of an input image at high speed.

In a conventional figure recognition device, shape extraction from binary image data is performed by extracting the outline of the figure and converting the outline into vectors. The most common contour extraction method is to simply sequentially track the coordinate points in the 8 or 4 neighborhoods. This method will be explained below. Here, the entity of the figure is represented by black pixels, Assume that the background is represented by white pixels. First, the original image is raster scanned to find the tracking start point, and this point is called the point of interest. Next, as shown in Figure 4, the points near this point of interest are The pixels are examined in the order of 112.3 in a counterclockwise direction, and the point that changes from a white pixel to a black pixel for the first time is set as the contour point coordinate, and is set as the next point of interest.

By repeating these searches until the starting point coincides with the starting point, one contour line is found. FIG. 5(b) is the result of extracting the outline of FIG. 5(a) by 8 connections using this method, and the shaded area is the extracted outline.

Next, feature points are extracted from the coordinate string obtained by contour tracking. An example of the vectorization method will be explained using FIG. FIG. 6(a) shows a pixel sequence obtained by performing contour tracing, and let us consider vectorizing stiffness. First, draw a line segment AB connecting the starting point and the ending point. Calculate the distance between each pixel that makes up the contour and AB, and search for the point P that is the most different from AB (
Figure 6(b)). If this distance is larger than the allowable error, AB is divided into AP and PB, and the same process is repeated for each line segment (FIG. 6(C)). Vectorization of AB ends when all pixels fall within the tolerance (FIG. 6(d)).

[Problems to be Solved by the Invention] However, in the conventional configuration described above, vectorization is performed for all pixel columns obtained by simply tracing the contour, so the relationship between the line segment AB and each @contour pixel is All distances must be calculated. Therefore, there were problems in that the amount of calculation was large and the processing took a long time.

[Means for Solving the Problem] In order to solve this problem, the present invention extracts pixels constituting the contour of a stored image, and extracts straight line portions in four predetermined directions among them. The points of the extracted straight line portion are extracted as feature points.

[Operation] According to the present invention, with the above-described configuration, feature points of the outline of a figure can be extracted at high speed.

[Embodiment] FIG. 1 is a block diagram showing the configuration of an apparatus using the feature point T sunrise method of a figure in an embodiment of the present invention. In Fig. 1, 1 is an image input unit that inputs binary image data as an original image, 2 is a contour tracking unit that tracks the contour of the input binary image and outputs its coordinates, and 3 is a contour tracking unit that outputs the coordinates of the input binary image. 4 is a coordinate output unit that outputs the coordinates extracted by the feature point extraction unit 3;

The operation of the apparatus using the graphic feature point extraction method of this embodiment configured as described above will be described below with reference to the flowchart shown in FIG.

First, in step S1, the original image is scanned by Lascous scanning to find a starting point for contour tracking. In step s2, it is checked whether the starting point existed in step sl, and if the starting point exists, the process proceeds to the next step, and if it does not exist, the contour tracing ends. In step s3, it is checked whether the starting point obtained in step sl has been tracked or not. If the starting point has not been tracked, the process proceeds to the next step, and if it has been tracked, the process returns to step S1. In step s4, the starting point is stored in memory,
Adjacent contour points are determined in step s5. Next, in step s6, contour points adjacent to the previously determined contour point are determined.

In step s7, it is checked whether the direction code obtained last time and the direction code obtained this time are the same, and if they are different, proceed to step s8, and if they are the same, proceed to step s9. In step s8, the contour points found @ times are stored in the memory. In step s9, it is checked whether the contour point obtained this time is equal to the tracing start point. If not, the process returns to step s6 to continue tracing; if they are equal, the final point is stored in the memory in step slO, and the process returns to step sl. Find the point before the start of the next contour tracking.

FIG. 3 shows the results of this embodiment when the same diagram (FIG. 5(a)) used to explain the conventional example is input as the original image. In this embodiment, only the coordinates represented by diagonally lined squares in FIG. 3 are extracted as feature points (contour coordinates). In this example, the number of feature points is reduced from 54 in the conventional example (FIG. 5(b)) to 26. There is no problem at all even if the contour coordinates extracted in this embodiment are vectorized using a conventional method.

As described above, according to this embodiment, by reducing the amount of contour information, it is possible to vectorize contours at high speed. Also,
When contour information is stored in memory, memory capacity is also reduced.

C Effects of the Invention J As described above, the present invention reduces the number of calculations for extracting feature points, so it is possible to vectorize figures at high speed. Furthermore, the memory capacity for storing contour tracking results is also reduced.

[Brief explanation of drawings]

FIG. 1 is a block diagram of an apparatus using the feature point detection method of a figure according to an embodiment of the present invention, FIG. 2 is a flowchart showing the control procedure in this embodiment, and FIG. Figure 4 is a diagram showing the conventional contour tracking method, Figure 5 is an explanatory diagram of the conventional contour tracking process, and Figure 6 is the conventional vectorization method. This is a diagram. 1... Image input section, 2... Contour tracking section, 3... Vectorization section, 4... Coordinate output section

Claims (1)

[Scope of Claims] Storing the read image data, extracting pixel rows forming the outline of the stored image, extracting straight line portions in four predetermined directions from the extracted pixel rows, and extracting the extracted pixel rows. A feature point extraction method for a figure, characterized in that the end points of a straight line section are taken as feature points.