JPH06103379A - Image processing method and apparatus thereof - Google Patents

Abstract

(57) [Abstract] [PROBLEMS] To provide an image processing method and apparatus capable of reducing the amount of memory for storing the connection relation of each contour vector when the contour vector is extracted. [Structure] An image is input in a band-divided unit, contour pixels are traced in the input band-shaped image unit, horizontal and vertical vectors are extracted, and stored in a memory. Then, a vertical vector connected to each of the extracted horizontal vectors and a horizontal vector connected to each of the vertical vectors are searched for, and the connection of these horizontal and vertical vectors is made clear. Extract the vector.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an image processing method and an apparatus thereof, and more particularly to an image processing method and an apparatus thereof for extracting a contour line of a binary image input in a raster scanning order.

[0002]

2. Description of the Related Art When an outline font is created from a binary dot pattern, the outline of a binary image character pattern is extracted and the outline is stored in a vector information format to create the outline font of that character. . Extracting the contour line from such a binary image can be started by first finding a tracking start point for contour line tracking in the binary image. Then, when this tracking start point is found, the contour of the image is traced in order from this tracking start point, and the tracking is continued while marking the traced points one after another. To do. Thus
One contour point sequence (contour line) is obtained at the time when this tracking has completed one cycle. By repeating such a procedure, all the contour lines in the image can be extracted.

FIG. 2 shows an example of a procedure for tracking contours of eight connections. In FIG. 2, reference numeral 201 denotes a binary image pattern including a blank portion 202 inside, and a case where this contour line is extracted will be described. However, one square in FIG. 2 represents one dot (pixel).

(1) The binary image pattern 201 is raster-scanned from a reference point (0,0) on the screen.

(2) If a point at which a pixel (for example, a dot 203) without a traced mark exists is hit, the point is set to P _{0 and} the contour tracing of the dot pattern is started. If the point P ₀ does not exist even when searching for all screens, the procedure ends.

(3) The search is started in the order of the neighboring pixels in the eight directions adjacent to the starting point P ₀ in the order shown in FIG. Then, the point where the first encountered pixel exists (dot 204 in the case of FIG. 2) is set as the next contour point P ₁ . At this time,
When there is no adjacent point, the point is regarded as an isolated point and the procedure returns to step (2).

[0007] (4) This performs the marking P _i in the extraction as shown in FIG. 4, with respect to eight directions neighboring pixels adjacent to the P _i, the next contour point P _{i + 1} To do. This is to search for a dot in the counterclockwise direction centered on P _i (dot 204) from the point 401 marked immediately before, and find the point where the first encountered pixel exists in the next contour. The point is P _{i + 1} .

(5) Thereafter, the procedure (4) is repeated to successively obtain contour points. However, if P _{n + 1} = P ₁ and P _n = P ₀ , then P ₀ , P ₁ , ..., P _n-1 are set as the contour point sequence of one region, and the procedure (6) Go to.

(6) The procedure returns to step (2) in order to obtain the outline point sequence of another image area.

That is all.

In FIGS. 3 and 4, the central portion shows the point of interest, and ⊚ (401) shows the point where the mark was made immediately before. Also, the numbers shown in the figure are pixels (dots)
Represents the order of searching for the presence or absence of.

However, in the above example, after the start point of contour tracking is determined, tracking along the contour line is performed,
The outline extraction process must be started after all the images have been stored in the memory. Therefore, there is a problem that the required memory capacity becomes large and the cost is increased and the processing time is delayed.

On the other hand, in order to reduce the memory capacity, the applicant of the present application has proposed a method of capturing an image in the raster scanning order and extracting contour points according to the states of the pixel of interest and pixels in the vicinity thereof. In this method, there is a connection information table that holds the connection state of contour lines in pixel units, and at the stage where the contours have been extracted for all pixels in the image,
The connection information table is scanned again to obtain the final total number of contour vector loops, the number of contour points forming each loop, the coordinate values of the contour points forming each loop, and the like.

[0014]

However, even in this case, when the contour (coarse contour) vectors have been extracted for all the pixels in the image, the connection information table is scanned again to determine the final contour vector. Since the total number of loops, the number of contour points that make up each loop, and the coordinate values of the contour points that make up each loop are obtained, all connection information for contour points in the image must be stored. It was found that the capacity of the information table becomes large and the search speed of the table tends to decrease.

[0015]

SUMMARY OF THE INVENTION The present invention has been made in view of the above problems, and it is an object of the present invention to reduce the amount of memory for storing the connection relation of each contour vector when the contour vector is extracted. It is an object of the present invention to provide an image processing method and apparatus that enables the image processing.

In order to solve this problem, the image processing method of the present invention comprises the following steps. That is, in the image processing method of extracting the contour vector of the input image from the image, the process of dividing the image into a plurality of strip images and inputting the image,
A contour extraction process for extracting each contour vector for each input strip image.

The image processing apparatus of the present invention has the following configuration.

In the image processing apparatus for extracting the contour vector of the input image from the image, the input means for dividing the image into a plurality of strip-shaped images and inputting the same, and the contour extraction for extracting each contour vector for each input strip-shaped image unit And means.

Further, in addition to the above object, another invention is to provide an image processing method and an apparatus therefor capable of outputting a high definition image when reproducing a binary image.

In order to achieve this object, the image processing method of the present invention comprises the following steps. That is, in the image processing method of extracting the contour vector of the input image from the image, a step of dividing the image into a plurality of band-shaped images and inputting the same, and a contour extraction step of extracting each contour vector for each input band-shaped image unit. And a smoothing step for smoothing the contour vector of each extracted strip-shaped image.

The image processing apparatus of the present invention has the following structure.

In an image processing apparatus for extracting a contour vector of the input image from an image, input means for dividing the image into a plurality of strip-shaped images and inputting the same, and contour extraction for extracting each contour vector for each input strip-shaped image Means and a smoothing means for smoothing the contour vector of each extracted strip-shaped image.

A further object of the present invention is to reduce the amount of memory for storing the connection relation of each contour vector in the case of extracting the contour vector, and to reduce the amount of memory between the contour vectors extracted from the individual band images. An object of the present invention is to provide an image processing method and a device for improving the connection state.

In order to achieve this object, the image processing method of the present invention comprises the following steps. That is, in the image processing method of extracting the contour vector of the input image from the image, a step of dividing the image into a plurality of band-shaped images and inputting the same, and a contour extraction step of extracting each contour vector for each input band-shaped image unit. And a step of integrating the contour vectors of the extracted strip-shaped image.

The image processing apparatus of the present invention has the following configuration.

In the image processing apparatus for extracting the contour vector of the input image from the image, input means for dividing the image into a plurality of strip-shaped images and inputting the same, and contour extraction for extracting the respective contour vectors for each input strip-shaped image unit Means and integrating means for integrating the contour vector of the extracted strip image.

[0027]

In the structure of the present invention, for example, the entire image is divided and input as a strip image, and the contour vector is extracted for each input strip image. Therefore, the amount of storing the connection relation of the contour vectors obtained from the band-shaped image here is small, and the number of objects for searching the connection relation of each other is small, resulting in high speed.

[0028]

Embodiments of the present invention will now be described in detail with reference to the accompanying drawings.

<First Embodiment> In the present embodiment, as shown in FIG. 1, an input image is divided into stripes, and a pixel of interest (101) and a state of eight pixels in the vicinity are divided for each stripe. The processing is proceeded by looking at, the target pixel is raster-scanned, and the processing of the entire image is sequentially performed while shifting the position of each pixel.

In FIG. 1, reference numeral 101 is a pixel of interest, and the positions indicated by "0" and "2" are at the same positions as the pixel of interest 101 in the main scanning direction, and each raster is one raster before in the sub-scanning direction. Pixel (0) and pixel (2) one raster ahead. The positions indicated by "1" and "3" are on the same raster as the pixel of interest 101 and indicate the pixel (3) one pixel before and the pixel (1) one pixel ahead, respectively. Further, "A" and "B" indicate pixels located one pixel ahead in the main scanning direction, respectively, one raster before and one raster ahead, and "C" and "D" indicate main scanning direction. Pixels at the position one pixel before the pixel of FIG.

FIG. 5 is a block diagram showing an example of the hardware configuration for detecting the contour of this embodiment.

Reference numeral 501 denotes an input control (interface) unit for exchanging image data input via the signal line 500, and binary image data is sequentially input from the signal line 500 in a raster scanning format. come. Reference numeral 502 is a latch that holds the image data input from the 501 while sequentially updating the image data pixel by pixel in synchronization with a pixel synchronization clock (not shown). Latch 50 at the next pixel sync clock
2 inputs the next pixel data from the input control circuit 501. At this time, the pixel data already held is latched and held in the latch 503 in synchronization with the pixel clock. Similarly, the pixel data held in the latch 503 is transferred to the latch 50 at the next pixel synchronization clock.
Held at 4.

Reference numerals 505 and 503 denote FIFOs (first-in first-out memory) for holding pixel data for one raster. The FIFO 505 sequentially takes in the output of the latch 504 in synchronization with the pixel synchronization clock and outputs the data of one raster before to the latch 507. Similarly, the FIFO 506 also takes in the output of the latch 509 and outputs the pixel data of one raster before to the latch 510. Latches 507, 508, 509 and latch 51
0, 511, 512 are the latches 502, 503,
It operates exactly like 504.

According to the above configuration, the latches 502, 50
3, 504, 507, 508, 509, 510, 511
In and 512, data of 3 × 3 pixels, that is, pixel data of a certain area is always stored. Here, when the pixel data held in the latch 508 is viewed as a target pixel position (reference numeral 101 in FIG. 1), the pixel positions “B”, “2”, “in FIG.
The data of C "," 1 "," 3 "," A "," 0 "," D "will be held.

Both 513 and 514 are input ports, and the input port 513 is a latch 510, 502, 504, 51.
2 data, that is, "A" and "" in FIG. 1, respectively
The data at the positions of B "," C ", and" D "are supplied to the CPU 519. Similarly, the input port 514 has the latch 511,
The data of 507, 503, 509, and 508, that is, "
The data of 0 ”,“ 1 ”,“ 2 ”,“ 3 ”and the pixel position of interest are supplied to the CPU 519.

Reference numeral 515 is a main scanning counter which indicates a pixel position in the main scanning direction, which is reset by a sub scanning synchronizing signal (not shown) and counts up by the pixel synchronizing signal.
A sub-scanning counter 516 indicates a pixel position in the sub-scanning direction, which is reset by a page sync signal (not shown) and counted up by the sub-scan sync signal. Reference numeral 517 denotes an input / output port for input / output control, which is an input / output control circuit 50.
1 holds a signal for instructing execution and suspension of pixel data input, a signal for notifying the CPU 519 of pixel data update from the input / output control circuit 501, and the like. Reference numeral 521 is an input / output control device for the hard disk 522.

These input / output control port 517, main scanning counter 515, sub-scanning counter 516 and input port 51.
3, 514, the memory 520, and the disk I / O 521 are connected to the CPU 519 via the bus 518.

In this way, the CPU 519 updates the pixel data via the input / output control port 517, and can know the pixel position (i, j) of the target pixel via the main scanning counter 515 and the sub-scanning counter 516. it can. Also,
Through the input ports 513 and 514, it is possible to know the states of the pixel of interest and the pixels in the eight directions in the vicinity thereof.

When the processing of the pixel of interest is completed in this way, the CPU 519 sends a 9-bit image through the input / output control port 517.
Instructing to update the pixel data stored in the individual latches, at the same time clearing the pixel data update instruction signal, and updating the pixel data latched in the subsequent latches,
When this update is completed, an update completion signal is output to the input / output control port 517.

The CPU 519 monitors the input of the update completion signal from the input / output control port 517 after outputting the update instruction. When this update completion signal is input,
The process relating to the pixel data newly stored in the nine latches is executed, and the same is repeated thereafter.

Incidentally, although the description goes back and forth, the CPU 519
An RA used as a work area and a ROM that stores the operation processing procedure of the CPU 519 (details will be described later).
Built in M.

Further, the input control circuit 501 outputs an end signal to the input / output control port 517 when the last pixel of the image area is processed as the target pixel.

Next, the processing in each case according to the states of the target pixel and the eight pixels in the vicinity thereof will be described.

If the pixel of interest is a white pixel, that pixel is not a part of the outline, so the processing is terminated, the raster scanning is advanced by one pixel, and the pixel of interest position is updated.

When the pixel of interest is a black pixel, the following processing is performed depending on the states of neighboring pixels. 6 to 21 show the processing contents in each state.

Here, in the pixel matrix 61 of FIG. 8, "d" is "do not care", that is, "d".
This means that the pixel at the position indicated by d ″ may be either a white pixel or a black pixel. This is the same in the following figures. Further, in the pixel matrix 62 of FIG. ) Represents the start point of the vector and the end point of the vertical (vertical) direction vector, and the triangle marks represent the start point of the vertical direction vector and the end point of the horizontal direction vector, and the solid line arrow 62 in FIG. Decided together,
The contour vector in the direction of the arrow is represented, and the dotted arrow as shown in FIG. 7 represents the contour vector in the direction of the arrow when only one of the start point and the end point is determined (one is not determined). . The meanings of these circles, triangles, solid arrows and dotted arrows are the same in the following figures. In addition, ● indicates a black pixel, and white pixel is indicated by a dotted circle ○ only when it is desired to clearly indicate the position, and is not indicated otherwise.

The start and end positions of these contour vectors are
It is assumed that both the main scanning direction and the sub-scanning direction are at the positions between pixels. Further, in both the main scanning direction and the sub scanning direction, the position where the pixel is present is indicated by a positive integer, and the pixel position is 2
Express in dimensional coordinates. For example, the pixel of interest 63 in FIG.
Is [(3,7): third pixel position of the seventh raster], the four vectors indicated by 62 in FIG. 6 are points 64 (2.5, 6.5), respectively. , Point 65 (3.5,
6.5), point 66 (3.5, 7.5), point 67 (2.
5 and 7.5) are represented as four continuous vectors having a start point and an end point.

If these vectors are represented by (coordinates of start point and coordinates of end point), the four vectors in FIG. 6 are [(2.5, 6.5), (3.5, 6.5), respectively. ] [(3.5, 6.5), (3.5, 7.5)] [(3.5, 7.5), (2.5, 7.5)] [(2.5, 7) .5), (2.5, 6.5)].

Therefore, in order to avoid a small number of representations, the pixel positions thereafter are represented by only even numbers, and the positions of the start point and the end point are represented by odd integers. That is, an image of m pixels × n pixels is represented by a coordinate expression of 2m × 2n positive even numbers (integers). Thus, in the example of FIG. 6 described above, the pixel position of interest is expressed as (6, 14), and the four end points and the start points are (5, 1), respectively.
3), (7,13), (7,15), (5,15). As a result, the four vectors in FIG. 6 are [(5,13), (7,13)] [(7,13), (7,15)] [(7,15), (5,15) ] [(5,15), (5,13)].

Thereafter, the binary image is assumed to be m × n pixels (m and n are positive integers) composed of n rasters each having m pixels, and the i-th raster of the j-th raster. The pixel position is (2i, 2j) (i, j is a positive integer, and i ≦
m, j ≦ n).

<Description of Contour Extraction Processing> FIG. 22 is a flowchart showing the overall flow of the contour extraction processing by the CPU 519 of the apparatus of the embodiment.

First, in step S1, the initial setting of the process, that is, the input image is divided into stripes as shown in FIG. 1, and the target stripe is set to the leading stripe of the image. The number of lines in each stripe when dividing the input image may be the same or different. Further, the number of lines of each stripe may be set to a predetermined number or may be arbitrarily set by an external setting means.

In step S2, 2 in the target stripe
A vector string is extracted from the value image data, and the coordinates of the starting point of each vector and the vectors that flow into this vector (the coordinates of the starting point of the vector of interest are the end points) and flow out (of the ending point of the vector of interest) A vector whose coordinates are the starting point) is output in the form of a table (defined as a connection information table) shown in FIGS. 23 and 24.
FIG. 23 is a diagram showing horizontal vectors, and FIG. 24 is a diagram showing vertical vectors. As described above, in the embodiment, the contour of the binary image is decomposed into vertical and horizontal vectors to extract the contour (first-stage contour). The point to note here is that the contours of all binary images have indefinite vector lengths, but horizontal / vertical vectors → horizontal vectors → vertical vectors → ... Expressed.

Now, in step S3, as shown in FIGS.
By tracing the inflow and outflow vector item numbers from the table shown in FIG. 4, the total number of contour lines in the image as shown in FIG. 25, the total number of contour lines for each contour line, and the x of each point in the contour line. Create a table that stores coordinates and y coordinates.

Next, in step S4, the disk I / O
This table information is stored in the disk 522 in a file format via 521, and the contents of the tables of FIGS. 23 and 24 are cleared.

Then, in step S5, it is determined whether the target stripe is the final stripe of the input image,
If it is not the final stripe, the process proceeds to S6, and if it is the final stripe, the process ends. In step S6, the target stripe is moved to the next stripe and the process returns to step S2.

As described above, the input image is divided into one or more stripes, and the outline extraction / alignment / file output processing is performed for each stripe.
The capacity of the table indicated by can be reduced.

Here, the contents of the vector string extraction processing in step S22 will be described with reference to the flowchart of FIG.

First, in step S11, the input port 51
By observing bit 4 (pixel of interest) of 4, it is determined whether the pixel of interest is a white pixel or a black pixel. If it is a white pixel, the process proceeds to step S13, and if it is a black pixel, the process proceeds to step S12. In step S12, the state of the eight pixels surrounding the target pixel is checked, and an appropriate processing routine corresponding to the state is called.

In step S13, the pixel position update is instructed via the input / output control port 517 as described above. When the update completion signal is input from the input / output control port 517, the process proceeds to step S14, and the input / output control port 51
7, it is determined whether or not the processing for the final pixel is completed. If not completed, the process returns to step S11, the next target pixel is similarly processed, and if completed, the original routine is returned to. To return.

FIG. 27 is a flow chart showing the processing executed by the state of the surrounding pixels shown in step S12 of FIG.

In step S21, the register of the CPU 519 is initialized to "0". Next, the process proceeds to step S22, and if the state of the pixel at the position indicated by "0" in FIG. 1 (hereinafter expressed by f (0)) is a black pixel (hereinafter expressed by "1"), step S23. Proceed to and white pixels (hereinafter,
If it is "0"), step S23 is skipped and the process proceeds to step S4. In step S23, "1" is added to the contents of the register. That is, bit 0 of that register is set to "1".

Next, in step S24, "1" in FIG.
If the state of the pixel at the position is a black pixel (f (1) = 1)
In step S25, 2 is added to the contents of the register (bit 1 is set to "1"). Also, f (1)
If = 0, step S25 is skipped.

When the process proceeds to step S26, it is similarly checked whether or not the pixel at the position "2" in FIG. 1 is a black pixel. If f (2) = 1 (black pixel), the process proceeds to step S27, and 4 is added to the contents of the register (bit 2 is set to "1"). If f (2) = 0, step S27 is skipped.

At step S28, attention is paid to the pixel at the position of "3" in FIG. 1. If f (3) = 1, the process proceeds to step S29 and 8 is added to the contents of the register (bit 3 is set to "1"). To). If not, the process of step S29 is skipped and the process proceeds to step S30.

As a result of the above, "0" shown in FIG.
Depending on the state of each pixel at the pixel positions of "1", "2", and "3", any value of 0 to 15 is held in the register. In step S30, the routine of the processing number of the value held in this register is called.

The processing (cases 0 to 15) corresponding to the values 0 to 15 held in the register will be described below. The relationship between these cases 0 to 15 and the pixel of interest and its peripheral pixels is as follows.
You can understand that it is as follows. That is, Case 0 corresponds to FIG. 6, Case 1 is FIG. 7, Case 2 is FIG. 8, Case 3 is FIG. 9, Case 4 is FIG. 10, Case 5 is FIG. 11, Case 6 is FIG. 12, Case 7 is FIG. 13, case 8
14, case 9 corresponds to FIG. 15, case 10 corresponds to FIG. 16, case 11 corresponds to FIG. 17, case 12 corresponds to FIG. 18, case 13 corresponds to FIG. 19, case 14 corresponds to FIG. 20, and case 15 corresponds to FIG.

The processing contents of each state will be described in detail below.

In step S30 of FIG. 27, if the register value is "0", the process shown in FIG. 28 is called. FIG. 28 is a routine for processing the state (case 0) shown in FIG. 6 as pointed out above. After that, the target pixel 63
The coordinates will be described as (2i, 2j).

<Description of Processing in Case 0 (FIGS. 6 and 2)
3, FIG. 24, FIG. 28)> In step S31 of FIG. 28, (2i-1,2j-1) is registered as the starting point of the horizontal vector. That is, the horizontal vector counter 23 shown in FIG.
(2i-1) is stored in the column (231 in FIG. 23) of the horizontal vector start point (64 in FIG. 6) indicated by 0, and the column of the horizontal vector start point y coordinate table (see FIG. 2) is also stored.
(2j-1) is stored in 232) of 3. The original vertical vector flowing into this horizontal vector is shown in FIG.
The vertical vector counter 240 of 4 is the vector stored at the position next to the position in the starting point coordinate table of the vertical vector pointed at this time, and the vertical vector to which this horizontal vector flows is At this point, the vertical vector counter 240 is at the position of the vertical vector start point coordinate table pointed to by the vertical vector counter 240.

That is, in the horizontal vector inflow vector item number column shown in FIG. 23, the horizontal vector counter 2
A value obtained by adding 1 to the value of the vertical vector counter 240 is stored in the position indicated by 30 (233 in the example of FIG. 23).
Also, in the column of the outflow vector item number of the horizontal vector,
The value of the vertical vector counter 240 is stored at the position indicated by the horizontal vector counter 230 (234 in the example of FIG. 23).

Next, in step S32, similarly (2i +
1, 2j-1) is registered as the start point of the vertical vector (65 in FIG. 6). The horizontal vector flowing into this vertical vector is the horizontal vector registered in step S31, and the horizontal vector flowing out of this vertical vector is stored at the position next to the horizontal vector registered in step 31 of the horizontal vector starting point coordinate table. Register it as a horizontal vector.

That is, referring to FIG. 24, column 2
41 is (2i + 1), and column 242 is (2j-1).
However, the value of the horizontal vector counter 230 at this time is stored in the column 243, and the value obtained by adding 1 to the value of the horizontal vector counter 230 at this time is stored in the column 244.

Next, in step S33, the content of the horizontal vector counter 230 is incremented by one. In step S24, (2i + 1,2j + 1) is registered as the starting point (67 in FIG. 6) of the horizontal vector, and the vertical vector flowing into this horizontal vector is registered as the vector registered in step S32, and this horizontal vector is registered. The vertical vector outflowing the vector is registered as the vertical vector stored at the next position in the vertical vector start point coordinate table of the vertical vector registered in step S32 (the vector connecting the points 66 and 64 in FIG. 6). To do.

In step S35, the content of the vertical vector counter 240 is incremented by 1, and in step S36, (2i
-1,2j + 1) is registered as the starting point coordinates of the vertical vector, and the horizontal vector flowing into this vertical vector is registered as the horizontal vector registered in step S34. The horizontal vector from which this vertical vector flows is registered as the horizontal vector registered in step S31. Thus, finally, in step S37, the horizontal vector counter 230 and the vertical vector counter 24
0 is added to +1 and the process ends.

The result of this processing is, as shown by 62 in FIG. 6, a horizontal vector connecting points 64 and 65, two horizontal vectors connecting points 67 and 66, and points 65 and 6
7 and two vertical vectors connecting the points 66 and 64 are combined and extracted as a state in which one loop in which four vectors circulate is formed.

The case 0 has been described above. However, in brief, if one horizontal vector is found,
Since there is always a vertical vector whose end point is the start point of the horizontal vector, a number specifying the vertical vector (found from the vertical vector table of FIG. 24) is written in the inflow vector item number column. Also, since the vertical vector is always connected to the end point position of the horizontal vector of interest, the number identifying the vertical vector (found from the vertical vector table in FIG. 24).
Is written in the field of the outflow vector item number. The same processing is performed on the vertical vector table based on the same principle. This is exactly the same for Cases 1 to 15 shown below.

<Description of Case 1 (FIGS. 7, 23 and 2)
4, FIG. 29)> FIG. 29 is a case 1 called when the value held in the register is 1 in step S30 of FIG.
It is a flowchart which shows the process of.

First, in step S41, (2i + 1,2j
+1) is set as the starting point of the horizontal vector, and is registered in the x and y coordinates of the starting point coordinates in the table shown in FIG. Also, the number of the vertical vector from which this horizontal vector flows (column 234).
Is the value of the vertical vector counter 240 registered in step S43 described later. Next, proceeding to step S42, the vertical vector flowing into the horizontal vector registered at step S41 is searched for from the vertical vector table 341 whose outflow destination shown in FIG. The content of the process of step S42 is shown in the flowchart of FIG.

In step S51, the value of the outflow vector undetermined vertical vector counter 340, which holds the number of vertical vectors whose outflow destination is undetermined, registered in the table 341 is set in the variable k. In step S52, it is determined whether or not the column of the x coordinate of the starting point of the vertical vector indicated by the value of the item number (k-1) registered in the vertical vector outflow vector undecided item number table 341 is (2i + 1). . If it is not (2i + 1), the value (k) of the variable k is decremented by 1, and step S52 is executed again. Step S
If the x coordinate of the starting point is (2i + 1) at 52, step S
Proceed to 54.

In step S54, the vertical vector whose item number in the table 341 is (k-1) is the inflow source vector of the horizontal vector registered in step S41, and the horizontal vector registered in step S41 is
This is the outflow vector of this vertical vector.
Therefore, in the inflow vector item number column of the horizontal vector designated by the horizontal vector counter 230 of FIG. 23, the vertical vector number whose item number of the table 341 is (k−1) and the outflow item of the vertical vector of FIG. In the number column,
The value of the horizontal vector counter 230 in step S41 is stored.

In step S55, the vector whose outflow destination is determined in steps S53 and S54 is deleted from the outflow destination undetermined vector table 341, and the empty portion of the table is filled. Next, in step S56,
The value of the outflow vector undetermined vertical vector counter 340 is set to 1.
The vertical vector outflow table undecided item number table 341 is updated to the effect that the number of outflow destination undetermined vertical vectors has decreased by 1, and the process returns to the original routine. . In this way, the process of step S42 in FIG. 29 ends and the process proceeds to step S43. In step S43, (2i-
1, 2j + 1) is registered as the starting point of the vertical vector, and the horizontal vector flowing into this vertical vector is the horizontal vector registered in step S41. Next, in step S44, the horizontal vector to which the vertical vector registered in step S43 flows out is searched from the inflow source vector undetermined table 311 shown in FIG. 31 and registered. The processing content of step S44 is shown in the flowchart of FIG.

This is executed in exactly the same way as the processing shown in FIG. That is, the vector to which the vertical vector registered in step S43 flows out is registered in the outflow vector item field of FIG. 24, and the value of the vertical vector counter 240 is entered in the inflow destination vector item number field of the horizontal vector flowing out to this vertical vector. Is set and is registered as this vertical vector. As a result, the table 311 shown in FIG. 31 is updated.

Next, in step S45, the horizontal vector counter 230 is incremented by 1, and in step S46, the vertical vector counter 240 is incremented by 1, and the original processing is returned to.

<Explanation of Processing for Case 2 (FIG. 8, FIG. 23, FIG. 24, FIG. 33, FIG. 36)> In step S30 of FIG. 27, if the value held in the register is “2”, FIG.
The process shown in is executed. The process shown in FIG. 36 is a routine for processing the state shown in FIG.

First, in step S71, the start point of the vertical vector indicated by the vertical vector counter 240 in FIG.
i−1, 2j + 1), and the horizontal vector from which this vertical vector flows is the horizontal vector registered in step S73. In step S72, step S
The vertical vector registered in 71 is registered in the unused area immediately next to the used area of the inflow vector undetermined vertical vector table 331 shown in FIG. 33 as a vector whose horizontal vector flowing into it is undetermined, The vector undetermined vertical vector counter 330 is incremented by one. Next, in step S73, the counter 23 in the table shown in FIG.
The starting point of the horizontal vector of the column indicated by 0 is (2i-1, 2,
j-1), and the inflow source vertical vector in this table is registered as the vertical vector registered in step S71.

In step S74, the horizontal vector registered in step S73 is set as an undetermined vertical vector to which the horizontal vector flows, and the unused vector immediately next to the unused area in the outflow vector undetermined horizontal vector table 321 shown in FIG. Register in the area and increment the outflow destination vector undetermined horizontal vector counter 320 by one. In step S75, the horizontal vector counter 230 and the vertical vector counter 2
Both 40 are incremented by 1, and the process returns to the original process.

<Description of Case 3 (FIG. 9, FIG. 23, FIG. 2)
4, FIG. 37) In step S30 of FIG. 27, if the value of the register is “3”, the processing shown in FIG. 37 is executed. The process shown in the figure is a routine for processing the state shown in FIG.

In step S81, (2i-1,2j +
1) is registered as the starting point of the vertical vector 91 (FIG. 9). Next, the process proceeds to step S82 and the above-mentioned step S44.
Similarly, the horizontal vector to which the vertical vector registered in step S81 flows out is obtained. Then step S
At 83, the value of the vertical vector counter 240 is set in the table 331 designated by the counter 330, and the value of the counter 330 is incremented by one. Next, in step S85, the content of the vertical vector counter 240 is incremented by 1, and in step S85, the process of case A is performed. This process is shown in the flowchart of FIG.

Explaining the flowchart of FIG. 38, it is checked in step S91 if the pixel A of FIG. 9 is white "0", and if it is not white, nothing is done and the process ends. This is indicated at 93 in FIG.

If the pixel A is white, the flow advances to step S92 to set the start point of the horizontal vector 94 (FIG. 9) to (2i + 1,2).
j-1). Next, in step S93, a vertical vector flowing into this horizontal vector is searched. Next, proceeding to step S94, assuming that the outflow vector of this horizontal vector is undecided, the number of this horizontal vector is set in Table 3.
Set to 21. Then, in step S95, the horizontal vector counter 230 is incremented by 1, and the process ends.

<Description of Case 4 (FIGS. 10, 23 and 2)
4, FIG. 31 to FIG. 34, FIG. 39)> Step S3 of FIG.
If the register value is "4" at 0, the routine shown in FIG. 39 is called. This routine is shown in FIG.
This is a routine for processing case 4 shown in FIG.

In step S101, (2i-1,2j-
1) is registered as the starting point of the horizontal vector 102, and the vector to which this vector flows out is the vertical vector registered in step S103, and the value of the vertical vector counter 240 at this time is the outflow vector item number in FIG. Set in the field. In step S102, step S
Assuming that the vector flowing into the vector registered in 101 is undecided, the value of the counter 230 is registered in the table 311 shown in FIG. 31, and this table 311 is updated. In step S103, (2i + 1,2j-1) is defined as the starting point of the vertical vector 103 (FIG. 10), and the vector flowing into this vector is step S101.
Assuming that the horizontal vector 102 is registered in step 2, the value of the horizontal vector counter 230 is set in the inflow vector item number column of the table shown in FIG. In step S104, the value of the vertical vector counter 240 is set in the column of the table 341 designated by the counter 340 in FIG. 34, assuming that the vector outflowing the vertical vector 103 registered in step S103 is undecided. Next, step S1
At 05, the horizontal vector counter 230 and the vertical vector counter 240 are respectively incremented by 1, and the original processing is returned to.

<Description of Case 5> Step S3 of FIG.
If the register is "5" at 0, the routine shown in FIG. 40 is called. The routine shown in FIG. 40 is called in the state shown in FIG. 11, and returns without doing anything.

<Description of Case 6 (FIGS. 12, 23 and 2)
4, FIG. 31 to FIG. 34, FIG. 41, FIG. 42)> In step S30 of FIG. 27, if the register value is “6”,
The routine shown in the flowchart of FIG. 41 is called. This is the processing of case 6 shown in FIG.

First, in step S111, the horizontal vector 122 designated by the counter 230 of FIG. 23 (FIG. 12).
The starting point of is registered as (2i-1,2j-1). Next, in step S112, regarding the horizontal vector 122 registered in step S111, the outflow destination vector is undecided, and the outflow destination vector undetermined horizontal vector table 3 shown in FIG.
21 is registered in the same manner as in step S94 of FIG. In step S113, assuming that the original vector flowing into the horizontal vector 122 registered in step S111 is undetermined, as in step S102 of FIG. 39,
It is registered in the inflow source vector undetermined horizontal vector table 311 shown in FIG. Next, in step S114, the horizontal vector counter 230 is incremented by one. In step S115, it is determined whether the pixel at the position (B) is a white pixel or a black pixel. If the pixel is a white pixel, as indicated by 120 in FIG. 12, (2i
+1, 2j + 1) is registered as the starting point of the vertical vector 124, and in the case of a black pixel, the process is terminated as indicated by 121 in FIG.

Details of the processing in step S115 are shown in FIG.
As shown in 2.

In step S121, the pixel B (see the drawing)
Is a white pixel or a black pixel, and if it is a black pixel, the process directly returns. If it is a white pixel, the process proceeds to step S122. In step S122, (2i + 1,2j + 1) is registered as the starting point of the vertical vector 124. In step S123, similarly to step S104 of FIG. 39, it is registered in the table 341 of FIG. 34 that the vector to which the vertical vector 124 flows is an undetermined vertical vector.
Further, in step S124, similarly to step S72 of FIG. 36 described above, it is set in the table 331 of FIG. 33 on the assumption that the original vector flowing into the vertical vector 124 registered in step S122 is undecided. In step S125, the vertical vector counter 240 is incremented by 1, and the process returns to the original routine.

<Description of Case 7 (FIGS. 13, 38 and 4)
2, FIG. 43)> In step S30 of FIG. 27, if the register value is "7", the routine shown in the flowchart of FIG. 43 is executed. This routine performs the processing of case 7 shown in FIG.

In step S131, similar to step S85 in FIG. 38, the process corresponding to the state of the pixel A is performed. Next, in step S132, step S115 of FIG.
Similarly to the above, the processing according to the state of the pixel B is performed, and the process returns to the original routine.

Incidentally, in FIG. 13, reference numeral 130 indicates that both the pixel at the position (A) and the pixel at the position (B) are white pixels.
131 shows a case where only (A) is a black pixel, 132 is a case where only (B) is a black pixel, and 133 is a case where both are black pixels.

<Description of Case 8 (FIGS. 14 and 44 to 4)
6)> In step S30 of FIG. 27, if the register value is "8", the processing routine shown in FIG. 44 is called. This routine performs the processing of case 8 shown in FIG.

In step S133, the vertical vector 141 designated by the vertical vector counter 240 (FIG. 14).
24 is registered in the table of FIG. 24 as (2i + 1,2j−1), and the horizontal vector to which this vector flows is a vector registered in subsequent S135,
The value of the counter 230 is registered in the outflow vector item number column. In step S134, the original horizontal vector flowing into the vertical vector 141 registered in step S133 is obtained using the table 321 shown in FIG. 32 in the procedure shown in FIG.

The process of FIG. 45 is exactly the same as the process shown in FIG. 30 and FIG.
The original horizontal vector flowing into the vertical vector 141 registered in 33 is registered, and the vertical vector to which this horizontal vector flows out is registered as the vertical vector 141 registered in step S133 (S145). Then, in step S146, the gap of the table 321 is filled,
In step S147, the counter 320 is decremented by 1 and the counter shown in FIG.
The table 321 shown in is updated.

In step S135 of FIG. 44, the horizontal vector 142 designated by the horizontal vector counter 230 is indicated.
The starting vertical point of (FIG. 14) is registered as (2i + 1, 2j + 1), and the original vertical vector flowing into this vector 142 is the vertical vector 14 registered in step S133.
Register to be 1. 33. In step S136, the vertical vector to which the horizontal vector 142 registered in step S135 flows is output according to the procedure shown in FIG.
It is obtained using the table 331 shown in FIG.

The processing of FIG. 46 is exactly the same as the processing shown in FIGS. 30, 35 and 45 described above, and the processing of FIG.
The vertical vector to which the horizontal vector 142 registered in step S135 of 4 flows out is registered, and the original vector flowing into this vertical vector is registered as the horizontal vector 142 registered in step S135 (step of FIG. 46). In S154), steps S155 and S156, the table 331 shown in FIG. 33 is updated.

Returning again to FIG. 44, the horizontal vector vector counter 230 and the vertical vector counter 240 are both incremented by 1 in step S137, and the process returns.

<Description of Case 9 (FIGS. 15 and 47)> In step S30 of FIG. 14, the register value is "9".
In this case, the routine shown in FIG. 47 is called. This routine processes case 9 shown in FIG.

First, in step S161, (2i + 1,
2j + 1) is registered as the starting point of the horizontal vector 151 (FIG. 15). Next, in step S162, in the same way as the procedure shown in FIG.
The vertical vector flowing into 51 is the table 341 in FIG.
Use to search and register. Further, the horizontal vector from which the searched vertical vector flows out is the step S1.
The horizontal vector registered at 61 is registered in the table shown in FIG. In this way, the table 341 of FIG. 34 is updated.

In step S163, the process shown in FIG.
Similarly to the procedure shown in FIG. 6, the horizontal vector 151 registered in step S161 is searched for and registered with the vertical vector to which the horizontal vector 151 flows out using the table shown in FIG. 33, and the original vector flowing into this vertical vector is the step. S16
The horizontal vector 151 registered in 1 is registered, and the table 331 shown in FIG. 33 is updated.

In step S164, the horizontal vector counter 230 is incremented by 1, and in step S165 it is determined whether the pixel at the position (D) is a white pixel or a black pixel. If the pixel is a white pixel, it is indicated by 152 in FIG. , (2i-1,2
j-1) is registered as the starting point of the vertical vector 154, and in the case of a black pixel, the processing is terminated (15 in FIG. 15).
3).

FIG. 48 shows the contents of the process of step S165 (case D).

In step S171, it is determined whether the position (D) is a white pixel or a black pixel, and if it is a black pixel, the process directly returns. If it is a white pixel, the process proceeds to step S172, and (2i
-1, 2j-1) is registered as the starting point of the vertical vector 154. Next, the process proceeds to step S173, and FIG.
Process. That is, the original horizontal vector flowing into the vertical vector 154 registered in step S172 is registered, and the vertical vector to which this horizontal vector flows in is registered as the vertical vector 154 registered in step S172. The table 321 shown in FIG. 32 is updated.

Next, in step S174, the above-described processing shown in FIG. 35 is performed. That is, the horizontal vector to which the vertical vector 154 registered in step S172 flows out is registered, and the original vector flowing into this horizontal vector is the vertical vector 154 registered in step S172.
Is registered and the table 311 shown in FIG. 31 is updated. In step S175, the vertical vector counter 2
40 is incremented by 1 and the process is returned.

<Process of Case 10> Step S of FIG.
In FIG. 49, when the register value is “10” in FIG.
The routine shown in is called. This routine is shown in FIG.
The case 10 shown in FIG. When the routine of FIG. 49 is called, it returns as it is.

<Description of Case 11> Step S of FIG.
When the register value is “11” in FIG.
The routine shown in 0 is called. This routine processes the case 11 shown in FIG.

First, in step S176, step S1
Similar to 65, the processing shown in the flowchart of FIG. 48 described above is performed according to the state of the pixel at the position (D). Next, in step S177, steps S85 and S
Similar to 131, depending on the state of the pixel at the position (A),
The processing shown in FIG. 38 described above is performed.

It is to be noted that the case where both the pixel at the position (D) and the pixel at the position (A) in FIG. 17 are white pixels is indicated by 170, and when only (A) is a black pixel is indicated by 171 and (D). 172 shows the case where only black pixels are present, and 173 shows the processing result when both (A) and (D) are black pixels.

<Description of Case 12 (FIG. 18, FIG. 23, FIG. 24, FIG. 51, FIG. 52)> In step S30 of FIG. 27, if the register value is “12”, the routine shown in FIG. 51 is called. To be done. This routine processes the state of case 12 shown in FIG.

In step S181, (2i + 1,2j-1) is added to the vertical vector 181 in the table shown in FIG.
Register as the starting point of (FIG. 18). In step S182, similar to step S134 of FIG. 44 described above,
The original horizontal vector 182 flowing into the vertical vector 181 registered in step S181 is searched and registered by the procedure shown in FIG. In addition, by registering the vertical vector 181 registered by the horizontal vector 182,
The table 321 shown in is updated.

Next, in step S183, step S
The fact that the outflow destination vector of the vertical vector 181 registered in 181 is undecided is registered in the table 341 shown in FIG. 34, and the counter 340 is updated. Next in step S18
At 4, the vertical vector counter 240 is incremented by 1. Then, in step S185, it is determined whether the pixel at the position C is a white pixel or a black pixel.
5 is registered as the starting point, and if it is a black pixel, 1 in FIG.
As indicated by 84, the processing is finished as it is.

The contents of the processing in step S185 are shown in FIG.
This is shown in the flowchart of FIG.

In step S191, it is determined whether the position of C is a white pixel or a black pixel, and if it is a black pixel, the process directly returns. If it is a white pixel, the process proceeds to step S192, and in step S192, (2i−1,2j + 1) is registered as the starting point of the horizontal vector 185. Next, in step S193, the process shown in the flowchart of FIG. 46 described above is performed to register the vertical vector to which the horizontal vector 185 registered in step S192 flows out. And the original vector flowing into this vertical vector is
If it is the horizontal vector 185 registered in step S192, it is registered in the table of FIG. 24 and the table 331 shown in FIG. 33 is updated.

In step S194, step S192
31 that the original vertical vector 186 flowing into this is the undetermined horizontal vector 185 registered in FIG.
Inflow source vector undetermined horizontal vector table 311 shown in FIG.
And the counter 310 is incremented by one. Then step S
In step 195, the horizontal vector counter 230 is incremented by 1, and the process returns to the original process.

<Description of Case 13 (FIGS. 19 and 53)>
In step S30 of FIG. 27, the register value is "1".
In the case of 3 ", the routine shown in FIG. 53 is called.
This routine is a processing of case 13 in FIG.

In step S196, similar to step S165 of FIG. 47 and step S176 of FIG. 50, the processing shown in the flowchart of FIG. 48 described above is performed according to the state of the pixel at the position D.

In step S197, similar to step S185 of FIG. 51, the processing shown in the flowchart of FIG. 52 described above is performed according to the state of the pixel at the position C. 190 is a processing result when both the pixel at the D position and the pixel at the C position are white pixels, 191 is a black pixel only for C, 192 is a black pixel only for D, and 193 is a processing result when both C and D are black pixels Are shown respectively.

<Description of Case 14> Step S of FIG.
If the register value is “14” in FIG.
The routine shown in 4 is called. This routine is shown in Figure 2.
The state of case 14 indicated by 0 is processed.

In step S201 of FIG. 54, similar to step S185 of FIG. 51 and step S197 of FIG. 53, depending on the state of the pixel at the position C, the above-described FIG.
The processing of case C shown by 2 is performed. Then step S2
In 02, as in step S115 of FIG. 41 and step S132 of FIG. 43, according to the state of the pixel at the position B,
The processing of case B shown in FIG. 42 described above is performed.

If 201 is a white pixel for both the pixel at the C position and the pixel at the B position, 202 is a black pixel for B only, 203
Indicates a processing result when C is a black pixel and 204 is a black pixel.

<Description of Case 15> Step S of FIG.
In the case where the register value is “15” in FIG.
The routine shown in 5 is called. This routine is shown in Figure 2.
The state of the case 15 shown by 1 is processed.

In step S203, the aforementioned step S
As in the case of 165 or the like, depending on the state of the pixel at the position D, the case D shown in the flowchart of FIG.
Process. Next, in step S204, the process of case A shown in FIG. 38 described above is performed according to the state of the pixel at the position A as in steps S85 and S131 described above. In step S205, the above-mentioned step S1
Similar to 85 and the like, the processing of the case C shown in FIG. 52 described above is performed according to the state of the pixel at the position C. Further, in step S206, similar to step S115 of FIG. 41 and the like, the processing of case B shown in FIG. 42 described above is performed according to the state of the pixel at the position B.

As a result, 210 in FIG. 21 shows the processing result when the pixel at the position D, the pixel at the position A, the pixel at the position C, and the pixel at the position B are all white pixels.
1 is a case where only A is a black pixel, 212 is a case where only B is a black pixel, 213 is a case where only C is a black pixel,
When 214 is a black pixel only for D, 215 is A and B
If 216 is a black pixel only, 216 is a case where only B and C are black pixels, 217 is a case where only C and D are black pixels, and 218 is a case where only D and A are black pixels.
20 is a case where only A and C are black pixels, 221 is a case where only D is a white pixel, 222 is a case where only C is a white pixel, 223 is a case where only B is a white pixel, and 224 is A
Only a white pixel is shown, and 225 shows a processing result when all are black pixels.

According to the procedure described above, a series of processes for vector string extraction in step S2 of FIG. 22 is executed.

<Outline Vector Sequence Alignment Processing> FIGS. 56 and 57 show the outline vector sequence alignment processing in step S3 of FIG. The flow charts of FIGS. 56 and 57 are the table group (FIG. 23) relating to the horizontal vector created in step S2 of FIG.
It operates using the table group relating to the vertical vector (FIG. 24) and the table group of FIG. 58 described later.

First, in step S211, necessary items in the table group shown in FIG. 58 are initialized. The processing contents of this step S211 are shown in detail in the flowchart of FIG.

In step S231, the variable t (starting point item number) that temporarily holds the starting point item number is set to zero. Next, in step S232, the variable i is set to "0", and in step S233, the i-th item in the start point candidate table 571 is set to "1". Step S23
In step 4, the variable i is incremented by 1, and in step S235, it is determined whether or not the variable i has a value smaller than the value of the horizontal vector counter 230. If the value is small, the process returns to step S233.

If the value is larger than the value of the horizontal vector counter 230, the process proceeds to step S236, and the loop number counter 572 is reset to "0". Next in step S23
The variable k is reset to "0" at 7 and the process returns to the original routine. As a result, all "1" s are set in the 0th (horizontal vector counter 230-1) th column of the start point candidate table 571.

When step S211 is completed in this way, the process proceeds to step S212, it is determined whether the variable k is equal to twice the value of the horizontal vector counter 230, and if they are equal, the process directly returns, but if they are not equal, the process proceeds to step S213. . In step S213, the value held in the variable t is stored in the item position of the starting point item number table 574, which indicates the value held by the loop number counter 572. In S214, the value stored in the item indicated by the value of the loop number counter 572 of the starting point item number table 574 (that is, the value stored in step S213) is set in the variable h. Then, in step S215, the variable j
Is reset to 0.

Here, the loop number counter 572 indicates the number of the contour currently being arranged, and the starting point item number table 57
The item number column designated by the loop counter 572 of No. 4 stores the item number having the starting point of the contour currently being arranged. The variable k holds the total number of processed and processed points in the processed and processed contours up to the present, and j
Holds the number of processed points in the contour currently being organized. The variable h indicates the item number of the horizontal vector to be processed next.

Next, in step S216, the item number designated by the value of the variable h in the start point candidate table 571 is reset to "0". Next, proceeding to step S217, the values held at the item positions of the horizontal vector start point x coordinate (FIG. 23) and horizontal vector start point y coordinate (FIG. 23) pointed to by the value of the variable h are set to the x coordinate table 575 and It is stored in the item position designated by the variable k in the y-coordinate table 576. At the same time, the value held at the item position of the horizontal vector outflow vector item number (FIG. 23) pointed to by the value of the variable h is set to the variable ν. This variable ν indicates the item number of the vertical vector to be processed next. In step S218, the values held by the variables k and j are incremented by +1.

Next, in step S219, the value held at the item position of the vertical vector start point (FIG. 24) and the vertical vector start point y coordinate (FIG. 24) indicated by the value of the variable ν is set to the x coordinate. Table 575 and y coordinate table 57
It is stored in the item position indicated by the value of the variable k in 6. At the same time, the value held in the item position of the vertical vector outflow destination vector item number (FIG. 24) pointed to by the value of the variable ν is set in the variable h. As a result, the item number of the horizontal vector flowing out from this vertical vector is set in the variable h. In step S220, the values held by the variables k and j are incremented by one.

Next, in step S221, the value of the variable h holds the item number of the starting point of the contour currently being arranged 573.
It is determined whether or not it is equal to the value of (variable t), and if it is not equal, the process returns to step S216 to continue processing the next point as one point of the same contour point, but if equal, step S222.
Then, the processing of the contour currently being arranged is completed. In step S222, the loop number counter 57 of the point table 577 that holds the number of points included in each contour, with the value held by the variable j as the number of points included in the contour currently being processed.
Store in the item position indicated by 2. Step S223
Then, the loop number counter 57 indicating the number of the contour being arranged
Increment 2 by 1.

Next, in step S224, the number of already processed points held by the variable k and the horizontal vector counter 23
It is determined whether or not the number of points held in the horizontal vector table held at 0 is twice. If they are equal, the process is terminated and the process returns. If not equal, step S
In step 225, the value of the starting point item number 573 is incremented by 1.
Then, in step S226, the starting point item number 573
It is determined whether or not the value held in the item of the start point candidate table 571 designated by the value of is "1", and if it is not "1", the process returns to step S225 and the search for the start point candidate is continued again. On the other hand, if the value is "1", the process returns to step S213 to start sorting the points within the next contour.

As described above, by the processing of step S3 of FIG. 22, the starting point data of the vectors shown in FIGS. 23 to 25 are arranged in the table shown in FIG. 58 as a coordinate sequence of points arranged in order for each contour loop. It

<Output of Vector Sequence Table> Next, FIG.
The output processing of the vector sequence table file in step S4 of FIG. 22 will be described with reference to the flowchart of FIG.

In step S241, the variable k is reset to "0". Next, in step S242, the output file is opened on the disk 522. Step S2
In 43, the value held in the loop number counter 572 is output to the file opened in step S242. In step S244, it is determined whether or not the value of the variable k is equal to the value held in the loop number counter 572, and if equal, the process proceeds to step S245 and the counters 230, 2
The values of 40, 310, 320, 330, and 340 are reset (values are set to 0), and the original processing is returned to.

On the other hand, if they are not equal in step S244, the flow advances to step S246 to output the value stored in the item position pointed to by the value of the variable k in the contour loop inner score table 577 to the disk 522. In step S247, the value stored in the item position indicated by the value of the variable k in the starting point item number table 574 is set in the variable m. Here, k holds the contour loop number currently being output, and m holds the item number in which the starting point of the point sequence in the contour loop currently being output is stored. Next, in step S248, the value of k is incremented by 1, and in step S249, the value of variable l is set to "0".
Reset to. This l is a variable that holds the number of already output points in the contour loop that is currently being output.

In step S250, it is determined whether or not the value of l is equal to the number of points in the contour loop currently being output. If they are equal, the process returns to step S244, and if they are not equal, the process proceeds to step S251. In step S251, the x coordinate table 575 and the y coordinate table 57 pointed to by the value of the variable m.
The value stored in the item position within 6 is output to the output file. Next, in step S252, the value of m is incremented by 1, and in step S253, the value of l is incremented by 1 and then step S25.
Return to 0.

When the processing of step S4 is completed, it is then determined in step S5 whether or not the target stripe that has been processed so far is the final stripe in the image. If it is the final stripe, the processing of FIG. 22 is completed. Otherwise, the process proceeds to step S6, the target stripe is moved to the next stripe, and the process returns to step S2.

According to the procedure described here, the so-called 4
The contour lines connected in the directions are extracted. However, the present invention is not limited to this, and can also be applied to the case of extracting contour lines that connect in eight directions.

As described above, the capacity of the table (connection information table) shown in FIGS. 23 and 24 has been required to be one page, but in the present invention, the input image is divided into stripes, Since the outline vector sequence is extracted independently for each stripe, the outline vector sequences are arranged, and the outline vector sequence table is output to the file, the table (connection information table) shown in FIG. 23 and FIG. The capacity can be reduced, which saves memory. Further, as the capacity of the table (connection information table) shown in FIG. 23 and FIG. 24 becomes smaller, the search range at the time of vector column alignment becomes narrower, and the processing speed can be increased.

<Second Embodiment> FIG. 61 is a block diagram of an apparatus for scaling an image in the embodiment. In the figure, reference numeral 401 denotes a digital binary image for which contour extraction / magnifying processing is performed, and outputs a binary image in raster scanning format 2
It is a value image acquisition means, and is composed of, for example, a known raster scanning type binary image output device which reads an image with an image reader, binarizes it, and outputs it in a raster scanning format.

Reference numeral 402 is an image dividing means for dividing the acquired binary image into one or more stripes, and the number of lines in each stripe can be arbitrarily set from the outside.

Reference numeral 403 denotes an outline extracting means for extracting a rough contour vector (outline vector before performing smoothing and scaling processing) for each divided stripe unit, which is the outline extracting means described in the first embodiment of the present invention. Is.

Reference numeral 404 denotes an outline smoothing / scaling means for smoothing and scaling the rough contour vector data in the form of vector data in units of divided stripes. Outline smoothing and scaling means, as well as Japanese Patent Application No. 3-345062 (1991) previously filed by the present applicant.
Application dated December 26, 2004). Briefly speaking, for example, when the vertical vector obtained by the above-described processing is two, the horizontal vector is two, and the vector lengths thereof are "1", the loop is formed. Existing vector groups (4 vectors),
If there is a protruding pixel of only one dot, that portion is removed, and the point recognized as a corner of the binary image is set as a fixed point (corner point), and points other than the corner point are set as floating points. This is a process in which a point is defined, and at a floating point of interest, weighting calculation is performed with respect to a plurality of corner points or floating points located in front of and behind, and the coordinate position is corrected. Further, when the horizontal vector and the vertical vector are continuous along a predetermined inclination, it includes a process of removing some points in the horizontal vector and vertical vector that are not affected by enlargement or reduction.

Numeral 405 is a binary image reproducing means for reproducing the binary image represented by the smoothed and scaled outline vector data as the binary image data of the raster scanning format in units of divided stripes. And, for example, Japanese Patent Application No.
It can be configured by the device described in No. 172098 (filed on July 12, 1991). Briefly described, it is a process of filling the inside of the contour (including the contour drawn by the enlargement processing) drawn based on the vector data obtained by the smoothing processing with black pixels.

Reference numeral 406 denotes a binary image output means for displaying binary image data of raster scanning type, making a hard copy, or outputting to a communication path.

FIG. 62 is a flow chart showing the flow of processing of the second embodiment.

First, in step S301, the input image is divided into stripes, and the target stripe is set as the leading stripe. When dividing the input image, the number of lines in each stripe can be arbitrarily set from the outside, or the input image is divided by a predetermined number of lines instead of being set from the outside. Good. Further, although the input image is divided by a predetermined number of lines, if a white line appears in the middle, it may be divided once at this position. For example, if the input image is 5
8 white lines when dividing each line into stripes
Suppose it appears on the line. At this time, the first stripe is composed of 5 lines, while the second stripe is composed of 3 lines. The third stripe is composed of 5 lines again from the 9th line unless a white line appears in the middle.
However, when two or more white lines are continuous, the entire continuous white line is regarded as one line for the sake of convenience and the processing is performed. That is, in the above example, when the white line continues from the 8th line to the nth line (including the 8th line), the second stripe is composed of (2 + n) lines. This is to prevent the unnecessary input image from being divided such that there is a stripe consisting of only white lines (it is meaningless because there is no figure). Here, the white line refers to a line that is entirely composed of white pixels.

The advantages of combining stripe division with a predetermined number of lines and stripe division when white lines appear will be described below.

Output of white line Since all the contour vector groups that have been extracted up to that point form a closed loop, the vector groups that have been extracted so far are aligned and output to the disk as an outline vector in the file format. It is possible to move to the processing of. However, if there are no white lines in the input image, all contour vectors must be held in the working memory, which requires a huge working memory. Therefore, as described above, combining stripe division with a predetermined number of lines and stripe division when white lines appear is very effective in reducing working memory.

Next, in step S302, the outline vector in the target stripe is extracted and aligned.
This is as described in the first embodiment. When the extraction and alignment of the outline vector in the target stripe are completed, the process proceeds to step S303, where the outline vector in the target stripe is smoothed and scaled.
In the processing here, the stripe of interest is regarded as the input image, and the smoothing and scaling processing described in Japanese Patent Application No. 3-345062 is performed as pointed out above. When the smoothing / scaling process of the target stripe is completed, the process proceeds to step S304, and 2 is calculated from the outline vector of the scaled target stripe.
Play and output the value image. The reproduction / output processing of a binary image is performed by the applicant of the present invention, which has been previously proposed by Japanese Patent Application No. 3-172.
It can be processed by the method and configuration described in No. 098. When the reproduction / output processing of the binary image is completed, the process proceeds to step S305, where it is determined whether or not the target stripe is the final stripe of the input image. If the final stripe is the final stripe, the processing ends, and if not, step S306. Moves to the next stripe, and the step S302 is performed.
Return to.

With the above configuration, an outline vector is extracted from the input image in stripe units, smoothed and scaled, and a binary image is reproduced and output. 1) A disk for extracting the outline vector Capacity or working memory capacity 2) Disk capacity for storing aligned outline vector data, or working memory capacity, 3) Disk capacity for smoothing and scaling of outline vector, or working memory capacity 4) A small disk capacity or a working memory capacity for reproducing / outputting a binary image from the outline vector is required.

<Third Embodiment> In the second embodiment,
When the outline vectors extracted and arranged in stripe units were smoothed and scaled, the divided stripes themselves were processed as independent input images. This processing has the advantage that all stripes can be processed in parallel without adding extra processing, but on the other hand, for example, in the example shown in FIG. 63 (a), the reproduced image is deteriorated due to smoothing. It turned out to be. That is, if the stripe division method of the second embodiment (divided into 5 lines) is used with FIG. 63 (a) as the input image, the first stripe is 5 lines and the second stripe is as shown in FIG. 63 (b). , The white line appears on the 4th line, so it is divided into 4 lines. Since the number of remaining lines of the input image is 5 lines or less, all the remaining (4 lines) are divided into the 3rd stripe. In this case, if the method and apparatus described in Japanese Patent Application No. 3-345062 are used, the concave portions (411, 412, 413) (white pixels)
Will be deleted by smoothing, and the portions corresponding to 411, 412, and 413 will be missing from the reproduced image after scaling.

In order to improve this, the following processing is secondly performed.
Add to the smoothing part of the example.

That is, when one figure originally has two or more stripes due to the stripe division, the line that becomes the boundary by the division (in FIG. 63 (b),
Although L _a and L _b are lines that are boundaries, only L _a satisfies the condition that one figure extends over two or more stripes due to division. ) The “starting point” and the ending point of the vector flowing out from above and the vector flowing in on the boundary line due to the division are “corner points” (corner points are corrected for their coordinate positions by smoothing processing as described above). It can be interpreted as a point that is literally located at a corner because there is no point). Fig. 63
In (b), 10 triangles and 10 circles are designated as corner points. When specified as a corner point, white pixels 411, 412, and 413 can be saved because they are excluded from smoothing, and deterioration of a reproduced image can be reduced.

<Fourth Embodiment> In the second and third embodiments, since smoothing, scaling, reproduction and output are performed in stripe units, there is an advantage that processing can be performed with a small memory amount. However, in the input image, what was originally one outline vector is divided into multiple parts and smoothed independently of each other. Therefore, the outline vector obtained when there is only one outline vector after smoothing is smoothed. There is also the problem that it will be slightly different from when it became. A method for solving this is shown below. In this method, outline vectors are extracted and aligned in a stripe-divided state, and when all extraction / alignment is completed, an outline vector that should originally be one is detected and integrated,
This can be achieved by checking and rearranging the vectors flowing out from the dividing boundary line and the vectors flowing into the dividing boundary line.

FIG. 64 is a flow chart when a part of the processing procedure of the second embodiment is changed.

First, in step S311, the input image is divided into stripes, and the target stripe is set as the leading stripe. This operation is step S in FIG.
Same as 301. Next, the process proceeds to step S312, and the outline vector in the target stripe is extracted and aligned. This is also the same operation as S302 in FIG. In step S313, it is determined whether the target stripe is the final stripe of the input image. If it is not the final stripe, the process proceeds to step S314, the target stripe is moved to the next stripe, and the process returns to step S312. If it is the final stripe, the process proceeds to step S315.

In step S315, the outline vector arranged for each stripe is divided into a plurality of contour vectors, and there is originally one outline vector (this outline vector is defined as a formal outline vector of the input image). Extract and align. The process of step S315 is shown in the example of FIG.

In order to simplify the description, the number of lines in the stripe division of the input image is three.
When the outline vector is extracted in the format of FIG. 25, FIG.
7 (the coordinates are expressed as integers as in the first embodiment). At this time, the Y coordinate of the boundary line of the stripe division is 7. In the example of FIG. 65, the outline vector is 4
It is extracted as one contour vector, but since this is originally one outline vector, integration is performed. This process is shown below.

First, the point where the Y coordinate is 7 (actually a multiple of 7) is obtained from FIG. 67 and expressed in the packet format as shown in FIG. That is, the data stored on the disk or the memory as shown in FIG. 67 is scanned. At this time, the third point of the first contour of the first stripe is obtained as the first point. The obtained points are expressed as shown in FIG. Here, the address in FIG. 66 represents the serial number attached to the point where the Y coordinate is 7. The X coordinate represents the X coordinate of a point whose Y coordinate is 7 obtained by scanning the data stored on the disk or the memory. The start point / end point is either a start point in the negative direction (negative start) or an end point in the negative direction (negative end) with respect to the horizontal vector, or a start point in the positive direction (positive start). Or the end point (positive end) in the positive direction. The stripe number indicates the stripe number of the obtained point, the contour number indicates which contour in the stripe the obtained point is, and the coordinate number indicates what number the obtained point is. Shows. Y obtained from FIG. 67
FIG. 68 shows a point whose coordinates are 7 in the format of FIG. When these are rearranged in ascending order of X-coordinate value, it becomes as shown in FIG. If the same value exists, arrange them in the order of positive start, negative start, negative end, positive end. Further, the rearranged packets are paired two by two from the head, and in each pair, the two packets are rearranged in the order of positive start, negative start, negative end, and positive end. In the figure, only the pair whose addresses are 5 and 6 do not satisfy this condition, so they are rearranged. When the processing is performed in this way, the contour vector has a connection relationship that the first packet continues to the next packet in each pair. That is, in each pair, the address of the next packet of the first packet stores the address of the next packet, and the address of the previous point stores nothing. Further, nothing is stored in the address of the next point of the next packet, and the address of the first packet is stored in the address of the previous point. This state is shown in FIG.
The final outline vector integration is shown in FIG. 67 and FIG.
0 is used. This is shown below.

First, scanning is started from the first point of the first contour of the first stripe in FIG. To simplify the description,
The εth point of the ω contour of the θth stripe is (θ−ω−ε)
And First, (1-1-1) is registered. Since this is not on the dividing line, the process moves to the next (1-1-2) and is registered. Since (1-1-2) is also not on the dividing line, the process moves to the next (1-1-3) and is registered. (1-1
-3) is on the boundary line of division, so refer to FIG. 70, check the point to be moved next, and move there. In this case, (1-
2-4) will be the next point. Register (1-2-4) and move to the next point. Although (1-2-4) is a point on the boundary line of the division, referring to FIG. 69, the destination to move to next is undecided, so move to (1-2-1) according to the order of FIG. 67.
Register (1-2-1). Continue (1-2-2),
(1-2-3) is registered, and (1-2-3) is on the dividing line, so refer to FIG. 69 and move to the next destination (2-2-2). At this time (1-2-3) and (2-
2-2) shows the same point, but if the same point is continuous in this way, neither is registered. (1-2-3)
Since it has already been registered, delete this.
Although (2-2-2) is on the boundary line of the division, referring to FIG. 70, the next destination is undecided, so the process moves to (2-2-3) according to the order of FIG. 67. Similarly, (2-2-3), (2-
2-4) and (2-2-1) continue registration. (2-2-
Since (1) is on the dividing line, refer to FIG. 70, and (2
Move to (1-2) and register (2-1-2). (2
-1-2) is a point on the boundary line of division, but referring to FIG. 70, since the destination is undecided, according to the order of FIG. 67, (2
-1-3), (2-1-4), and (2-1-1) are registered. Since (2-1-1) is a point on the boundary line of division, FIG.
Move to (1-1-4) and register (1-1-4). After (1-1-4), the scanning start point (1-1-1)
Therefore, the registration is terminated here, the number of registered points is checked, the total number of contour points is stored, and the total number of contour lines in the input image is stored.

The result of the above processing is shown in FIG.
If an unprocessed outline vector still exists, it is converted into a formal outline vector by the same process, and is registered following FIG. 71 so as to have the format shown in FIG. Further, outline vectors having no coordinate points on the division boundary line may be continuously registered in FIG. 71 as they are so that the format of FIG. 25 is obtained without any processing. At this time,
It is necessary to rewrite the total number of contour lines in the input image so as to represent the number of vector loops registered therein.

When all the above processing is completed, step S
Move to 316. In step S316, smoothing / magnifying processing is performed using the formal outline vector. This is as shown in the second embodiment. When step S316 ends, the process moves to step S317, and a binary image is reproduced and output from the scaled outline vector of the input image.
This is also as described in the second embodiment.

By performing the above-described processing, a formal outline vector of the input image can be obtained from the divided and extracted contour vector, and by smoothing and scaling this, a high quality reproduced image can be obtained. Is possible.

<Fifth Embodiment> As described above, the stripe division has the advantage that the amount of working memory required for outline extraction, smoothing, scaling, reproduction, and display is small. However, the stripe division process affects the smoothing of the outline vector, and affects the quality of the reproduced image to some extent. Therefore, we want to reduce the number of divisions as much as possible (to increase the stripe width). The method of reducing the division will be described below.

The purpose of the stripe division processing is to prevent the working memory from overflowing due to the outline extraction processing or the like, and stripe division is not necessary unless the working memory overflows. In other words, stripe division should be performed before the working memory overflows.

That is, the horizontal vector counter 230 or the vertical vector counter 2 shown in FIGS.
The address indicated by 40 is monitored by the CPU 519 of FIG. 5, and when this value exceeds a certain value (depending on the working memory capacity), a method such as stripe division on the line currently being processed can be taken. Good. In this case, it is possible to perform processing by designating the start point and the end point of the vector flowing in on the division boundary line and the vector flowing out from the division boundary line as the corner points as in the third embodiment. It is also possible to use the method shown in the fourth embodiment together.

<Sixth Embodiment> When a scaled image is to be obtained using the outline vector extracted according to the rule used in the first embodiment, a scaling process of low magnification of about 1 to 2 is performed. In this case, the pixel width of the thin line portion of the generated output image may become thick. This is because in the method shown in the first embodiment, the contour point is defined by defining the contour point at the pixel position just at the center of the white pixel and the black pixel, whereas the image regenerating unit does. , The obtained smoothness
Since the pixel itself indicated by the contour coordinate value of the scaled image is processed as a black pixel, at the time of low magnification as described above, the pixels on the contour line defined to surround the pixels of the original image are surrounded by the contour line as black pixels. This is because the black pixels in the area defined by the pixels tend to be larger than the areas defined by the white pixels as compared with the areas defined by the white pixels. .

On the other hand, when the outline vector is extracted from the binary image, the contour point is defined at a position close to the black pixel between the white pixel and the black pixel of the input image, and the black pixel area is divided into white pixels. By extracting the pixel on the contour line as a black pixel by extracting it narrower than the region, even if the image is regenerated with the black pixel in the region surrounded by the contour line, the low-magnification scaled image looks thick. The present invention has already been proposed by the applicant as Japanese Patent Application No. 4-169581.

Even if the method shown in Japanese Patent Application No. 4-169581 is used as the outline vector extraction method, the same discussion as in the first, second, third and fifth embodiments will be made. It is possible. However, Japanese Patent Application No. 4-1695
When the method of No. 81 is applied to the outline smoothing and scaling method of Japanese Patent Application No. 3-345062, Japanese Patent Application No. 3-3
Japanese Patent Application No. 45062 discloses a pattern of a combination of length and orientation of up to a total of 7 consecutive continuous edge vectors and up to 3 edge vectors before and after the target contour vector of the first smoothing disclosed in 45062. It may be changed according to the contour vector extracted by the method of No. 4-169581. That is, in Japanese Patent Application No. 4-169581, the extracted contour point is set at a position between the white pixel and the black pixel of the input image, which is, for example, a black line having a width of one pixel, A contour loop having a width of 1/2 is extracted, and a white line having a width of one pixel in the black area is extracted as a contour loop having a width of 1 + 1/2. Even if the input image has the same pixel width,
Concavity (concave) than protrusion (convex) in the black pixel area
Is extracted broader by 1. Compared with the outline extraction method used in the first embodiment, the protrusion (convex portion) of the black pixel region is extracted narrower by 1/2, and the dent (concave portion) is extracted.
Is extracted as wide as 1/2. Therefore, a combination of the length and direction of the side vector may be adjusted and used according to this difference. For other processes, Japanese Patent Application No. 3-34
Application is possible by following the example of No. 5062.

<Seventh Embodiment> By applying the method of Japanese Patent Application No. 4-169581 previously proposed by the applicant of the present application, outline vectors are extracted and aligned in stripe units, and When the alignment is over, these are originally 1
The following describes how to detect and integrate two outline vectors that should be combined.

Since the basic idea is the same as that of the fourth embodiment, step S315, which is largely different, will be described.

Similar to the fourth embodiment, the image shown in FIG. 65 is used as the input image. In order to avoid the decimal representation of the coordinates, the position of each pixel is (4m + 2,4n + 2) (where m = 0,
1, ..., 10, n = 0, 1, ..., 5), and rewrite as in FIG. 72 to use the image in the same figure as the input image. The number of lines in the stripe division is 12 (corresponding to 3 in the image of FIG. 65), and the outline vector is extracted in the format of FIG. 25, as shown in FIG. At this time, the Y coordinate of the stripe boundary line is 12.
In the example of FIG. 72, the outline vector is extracted as four contour vectors, but since this is originally one outline vector, integration is performed. This process is shown below.

First, the Y coordinate of a vector newly generated by stripe division is obtained. In this case, since the stripe division is performed with 12 lines, the Y coordinate of the vector newly generated by the stripe division is 11 or 13. Generally speaking, when the Y coordinate of the division boundary is λ, the y coordinates of the vector newly generated by the stripe division are (λ-1) and (λ + 1).

When the Y coordinate is obtained, the data stored on the disk or the memory is scanned as shown in FIG.
The coordinate value of the corresponding vector is expressed in a packet format such as 3. At this time, the third point of the first contour of the first stripe is obtained as the first point. The obtained points are expressed as shown in FIG. The address in FIG. 73 has a Y coordinate of 1
Indicates a serial number attached to a point that is 1 or 13.
The converted X coordinate (XX) indicates the X coordinate of the point obtained by the following conditional expression.

If (X coordinate value)% 4 = 3, XX = (X coordinate value) +1 (X coordinate value)% 4 = 1 if XX = (X coordinate value) −1 However,% is a calculation for calculating the remainder. Represents

In order to apply the method in the fourth embodiment, for convenience, the X coordinates of points existing between adjacent pixels show the same value. The X coordinate and the Y coordinate represent the X coordinate and the Y coordinate of a point whose Y coordinate is 11 or 13 obtained by scanning the data stored on the disk or the memory. The start point / end point is either a start point in the negative direction (negative start) or an end point in the negative direction (negative end) with respect to the horizontal vector, or a start point in the positive direction (positive start). Or the end point (positive end) in the positive direction. The stripe number indicates the stripe number of the obtained point, the contour number indicates which contour in the stripe the obtained point is, and the coordinate number indicates what number the obtained point is. Shows. The required Y coordinate is 11
73 is shown in the format of FIG. 73. This is rearranged in ascending order of XX (x coordinate). However, when the same value exists, arrange in the order of positive start, negative start, negative end, positive end --- Condition 1. For example, in this example, XX = 24 and XX
There are two = 36 packets. When arranged according to the condition 1, the result is as shown in FIG. In the case of XX = 24, since there are two, the negative end and the positive end, the negative end is virtually considered to be the younger number and arranged. At this time, a flag for performing special processing is set on contour points having the same XX value and different X coordinate values (Y indicates a flagged state, N indicates a flagged state). . Further, the rearranged packets are paired two by two from the beginning, and in each pair, the two packets are rearranged so that the order of the two packets is the order of condition 1. Here, only the pair whose addresses are 5 and 6 do not satisfy this condition, so they are rearranged. When the processing is performed in this way, the contour vector has a connection relationship that the first packet continues to the next packet in each pair. That is,
In each pair, the address of the next packet of the first packet stores the address of the next packet, and the address of the previous point stores nothing. Further, nothing is stored in the address of the next point of the next packet, and the address of the first packet is stored in the address of the previous point. This state is shown in FIG. The final integration of outline vectors is performed using FIGS. 74 and 77.

In the fourth embodiment, since the midpoint between the images is set as the contour, the vector becomes a horizontal vector even when connecting from address 4 to address 1 in FIG. 70, but this time the contour is shifted toward the black pixel. In such a case, the vector becomes an oblique direction. In order to avoid this adverse effect, the diagonal vector is expanded into a horizontal vector and a vertical vector using the following rules. First, cases are divided for vectors whose connection direction is oblique. If the vector is [(p, q), (r,
s)] (where (p, q) represents the coordinates of the start point and (r, s) represents the coordinates of the end point), (p, q) and (r, s)
Interpolate contour points between the following.

<Rule 1> A. When no special processing flag is set on either (p, q) or (r, s) (A-1) If r> p and s> q, then (p, q) →
(P, q + 2) → (r, s) (A-2) If r> p and s <q, then (p, q) →
(R, s + 2) → (r, s) (A-3) If r <p and s> q, then (p, q) →
(R, s-2) → (r, s) (A-4) If r <p and s <q, then (p, q) →
(P, q-2) → (r, s) (A-5) If s = q and r> p, then (p, q) →
(P, q + 2) → (r, s + 2) → (r, s) (A-6) If s = q and r> p, then (p, q) →
(P, q-2) → (r, s-2) → (r, s) (A-7) If p = r, then (p, q) → (r, s) B. When the special processing flag is set only in (p, q) (B-1) If r> p and s> q, (p, q) →
(P + 2, q) → (p + 2, q + 2) → (r, s) (B-2) If r <p and s <q, then (p, q) → (p
−2, q) → (p−2, q−2) → (r, s) (B−3) If s = q and r> p, then (p, q) → (p
+ 2, q) → (p + 2, q + 2) → (r, s + 2) →
(R, s) (B-4) If s = q and r <p, then (p, q) → (p
−2, q) → (p−2, q−2) → (r, s−2) →
(R, s) C.I. When the special processing flag is set only for (r, s) (C-1) If r> p and s <q, (p, q) → (r
−2, s + 2) → (r−2, s) → (r, s) (C−2) If r <p and s> q, then (p, q) →
(R + 2, s-2) → (r + 2, s) → (r, s) (C-3) If s = q and r> p, then (p, q) →
(P, q + 2) → (r-2, s + 2) → (r-2, s)
→ (r, s) (C-4) If s = q and r <p (p, q) →
(P, q-2) → (r + 2, s-2) → (r + 2, s)
→ (r, s) D. When a special processing flag is set in both (p, q) and (r, s) (D-1) If r> p, (p, q) → (p + 2, q)
→ (p + 2, q + 2) → (r-2, s + 2) → (r-
2, s) → (r, s) (D-2) If r <p (p, q) → (p-2, q)
→ (p-2, q-2) → (r + 2, s-2) → (r +
2, s) → (r, s) <Rule 2> The vectors forming the contour including the interpolated points are always alternating horizontal and vertical vectors.

The two or more continuous horizontal vectors and the two or more continuous vertical vectors are integrated into one horizontal vector and one vertical vector, respectively. Rule 1 and Rule 2
74 and 77, the outline vectors are integrated. First, the first of the first contours of the first stripe of FIG.
Scanning starts from the dot. To simplify the description, the θ
The εth point of the ωth contour of the stripe is represented as (θ−ω−ε), and the point related to the division boundary, that is, the point whose Y coordinate value is 11 or 13 is called a boundary point. . First, check (1-1-1). Since this is not a boundary point, it is registered and the process moves to the next (1-1-2). (1-1-
2) is not a boundary point either, so register it,
Move on to. Since (1-1-3) is a boundary point, refer to FIG. 77 and check the point to be moved next. In this case, (1-2
4) will be the next point. A vector whose starting point is (1-1-3) and whose ending point is (1-2-4) is (C-
Since it corresponds to 3), (15, 11) → (15, 13) →
The contour points are interpolated as (23,13) → (23,11) → (25,11). Next, Rule 2 is applied to combine continuous horizontal vectors and continuous vertical vectors.
It is the contour point immediately before (1-1-3) (1-1-2)
From the viewpoint of (15, 5) → (15, 11) → (1
5,13) → (23,13) → (23,11) → (2
5,11), and (15,5) → (15,11) and (15,11) → (15,13) are both vertical vectors, so they are integrated, and (15,5) → (15,13) → ( 23,
13) → (23,11) → (25,11). Then, (15, 13), (23, 13), (23, 11) are registered, and the point to move to next is obtained from FIG. (25,
Since 11) is the point indicated by (1-2-4), the next point is (1-2-1). (23,11) → (25,1)
1) is a horizontal vector, and (25,11) → (25,5) is a vertical vector. Since they are alternating, (25,1)
Register 1). Similarly, (1-2-1), (1-2
2) Register. Since (1-2-3) is a boundary point, the next moving point is (2-2-2) when calculated from FIG. Since this corresponds to rule 1 (A-7), (35, 11)
→ becomes (35, 13). Same as before (35, 1
Considering from the point (35, 5) immediately before 1), (35,
5) → (35,11) → (35,13), and since two vertical vectors continue, they are integrated and (35,11) is not registered. The next point of (35, 13) becomes (2-2-3), and since two vertical vectors continue (35, 5) → (35, 13) → (35, 15), (35, 13) )
Does not register. In this way, we constantly monitor the points that need to be changed, and
One or more continuous horizontal vectors and two or more continuous vertical vectors are integrated into one horizontal vector and one vertical vector, respectively, and a contour point is registered when the vertical vector and the horizontal vector alternate. The point to move to after (2-2-3) is (2-2-4), which is (35,5) → (3
Since the vertical vector and the horizontal vector alternate, such as (5,15) → (33,15), (2-2-3), that is, (35,15) is registered. When the processing is performed according to the rules 1 and 2 as described above, the table of FIG. 78 is finally obtained.

The processing contents of step S315 have been described above. When all the processing is completed, the process proceeds to step S316. In step S316, smoothing and scaling processing is performed using the formal outline vector. This is as shown in the sixth embodiment. When step S316 ends, the process moves to step S317, and a binary image is reproduced and output from the scaled outline vector of the input image.

By performing the processing as described above, the formal outline vector of the input image can be obtained from the divided and extracted contour vector, and a high-quality reproduced image can be obtained by smoothing and scaling it. Is possible.

<Eighth Embodiment> FIGS. 79, 80, and 81 are block diagrams showing the case in which the present embodiment is applied to a facsimile.

FIG. 79 is a block diagram in which this embodiment is applied to a facsimile on the receiving side. The code transmitted by the MH code or the like is decoded to create input binary image data, and the above outline processing is performed. The binary image regenerated by the outline processing unit is output to paper or the like by the recording device or displayed on the display or the like by a display device (not shown).

FIG. 80 is a configuration diagram in which this embodiment is applied to a facsimile on the transmission side. An image signal input by a scanner or the like is binarized, input image data is created, and outline processing is performed. 2 regenerated by the outline processing unit
The value image is stored in the image memory, converted into a code such as an MH code by the encoder, and transmitted.

FIG. 81 is a block diagram when this embodiment is applied to a facsimile for both transmission and reception. Although the above two examples are combined, the selector is controlled by the transmission / reception control circuit, and the input / output of the outline processing unit is determined by transmission / reception. Here, in particular, the reading unit may be selected as the binary image acquisition unit and the binary image output unit may be configured (or selected) as the recording device, but in this case, it has a scaling function. It is possible to realize a digital copying machine (or copy mode).

[0200]

As described above, according to the present invention, since the input image is divided into stripes, the working memory and disk capacity can be reduced and the memory can be saved. Further, since the working memory and the disk capacity are reduced, the search range in the outline alignment processing is narrowed, and the processing speed can be increased.

[0201]

[Brief description of drawings]

FIG. 1 is a diagram showing a target pixel and its neighboring pixels in the present embodiment,

FIG. 2 is a diagram for explaining the principle of outline extraction from a binary image up to now.

FIG. 3 is a diagram showing a direction of tracking processing in contour extraction.

FIG. 4 is a diagram showing a direction of tracking processing in contour extraction.

FIG. 5 is a diagram showing a schematic configuration of a contour extracting device in an embodiment.

FIG. 6 is a diagram showing a pixel state of case 0 in the contour vector extraction according to the embodiment.

FIG. 7 is a diagram showing a pixel state of case 1 in contour vector extraction according to the embodiment.

FIG. 8 is a diagram showing a pixel state of case 2 in contour vector extraction according to the embodiment.

FIG. 9 is a diagram showing a pixel state of case 3 in contour vector extraction according to the embodiment.

FIG. 10 is a case 4 in contour vector extraction according to the embodiment.
It is a figure which shows the pixel state of.

FIG. 11 is a case 5 in the contour vector extraction according to the embodiment.
It is a figure which shows the pixel state of.

FIG. 12 is a case 6 in contour vector extraction according to the embodiment.
It is a figure which shows the pixel state of.

FIG. 13 is a case 7 in contour vector extraction according to the embodiment.
It is a figure which shows the pixel state of.

FIG. 14 is a case 8 in the contour vector extraction according to the embodiment.
It is a figure which shows the pixel state of.

FIG. 15 is a case 9 in contour vector extraction according to the embodiment.
It is a figure which shows the pixel state of.

FIG. 16 is a case 1 in contour vector extraction according to the embodiment.
It is a figure which shows the pixel state of 0.

FIG. 17 is a case 1 in contour vector extraction according to the embodiment.
It is a figure which shows the pixel state of 1.

FIG. 18 Case 1 in contour vector extraction according to the embodiment
It is a figure which shows the pixel state of 2.

FIG. 19 is a case 1 in contour vector extraction according to the embodiment.
It is a figure which shows the pixel state of 3.

FIG. 20 Case 1 in contour vector extraction according to the embodiment
It is a figure which shows the pixel state of No. 4.

FIG. 21 is a case 1 in contour vector extraction according to the embodiment.
It is a figure which shows the pixel state of No. 5.

FIG. 22 is a flowchart showing the entire outline extraction processing in the embodiment.

FIG. 23 is a diagram showing a horizontal vector registration table in the embodiment.

FIG. 24 is a diagram showing a vertical vector registration table according to the embodiment.

FIG. 25 is a diagram showing a data format of a contour line in the example.

FIG. 26 is a flowchart showing the overall processing of vector string extraction processing in the embodiment.

FIG. 27 is a flowchart illustrating in more detail the content of processing when the pixel of interest in FIG. 26 is black.

28 is a case 0 in which the pixel of interest in FIG. 27 is a black pixel.
7 is a flowchart showing the processing contents in the case of supporting the.

FIG. 29 is a flowchart showing the processing contents of case 1 in the embodiment.

FIG. 30 is a flowchart showing a process of searching a vertical vector flowing into a horizontal vector.

FIG. 31 is a diagram showing a horizontal vector registration table for which an inflow vector has not been determined.

FIG. 32 is a diagram showing a registration table of horizontal vectors whose outflow vectors are undetermined.

FIG. 33 is a diagram showing a registration table of vertical vectors whose inflow vectors are undetermined.

FIG. 34 is a diagram showing a registration table of vertical vectors for which extraction vectors have not been determined.

FIG. 35 is a flow chart showing a process of searching a horizontal vector flowing out to a vertical vector.

FIG. 36 is a flowchart showing the processing contents of case 2 in the embodiment.

FIG. 37 is a flowchart showing the processing contents of case 3 in the example.

FIG. 38 is a flowchart showing the processing of case A in FIG. 37 and the like.

FIG. 39 is a flowchart showing the processing contents of case 4 in the example.

FIG. 40 is a flowchart showing the processing contents of case 5 in the embodiment.

FIG. 41 is a flowchart showing the processing contents of case 6 in the embodiment.

42 is a flowchart showing the processing of case B in FIG. 41 and the like.

FIG. 43 is a flowchart showing the processing contents of case 7 in the example.

FIG. 44 is a flowchart showing the processing contents of case 8 in the example.

45 is a flowchart of a process for searching a horizontal vector flowing into the vertical vector in FIG. 44 and the like.

46 is a flowchart of a process for searching a vertical vector from which the horizontal vector in FIG. 44 and the like flows.

FIG. 47 is a flowchart showing the processing contents of case 9 in the example.

48 is a flowchart showing the processing of case D in FIG. 47 and the like.

FIG. 49 is a flowchart showing the processing contents of case 10 in the example.

FIG. 50 is a flowchart showing the processing contents of case 11 in the example.

FIG. 51 is a flowchart showing the processing contents of case 12 in the embodiment.

52 is a flowchart showing the processing of case C in FIG. 51 and the like.

FIG. 53 is a flowchart showing the processing contents of case 13 in the embodiment.

FIG. 54 is a flowchart showing the processing contents of case 14 in the example.

FIG. 55 is a flowchart showing the processing contents of case 15 in the example.

FIG. 56 is a flowchart showing outline vector sequence alignment processing in the embodiment.

FIG. 57 is a flowchart showing outline vector sequence alignment processing in the embodiment.

FIG. 58 is a diagram for explaining a start point candidate table in the outline vector sequence alignment process in the example.

59 is a flowchart showing the contents of the table / variable initialization process in FIG. 56.

FIG. 60 is a flowchart showing a process of outputting a vector sequence table to a file.

FIG. 61 is a diagram showing an outline of a block configuration diagram of a second embodiment.

FIG. 62 is a flowchart showing a processing flow of the second embodiment.

FIG. 63 is a diagram for explaining the third embodiment.

FIG. 64 is a flowchart showing the flow of processing of the fourth embodiment.

FIG. 65 is a diagram showing an input image for explaining the fourth embodiment.

[Fig. 66] Fig. 66 is a diagram for describing a starting point and an ending point of a horizontal vector existing on a stripe division boundary line.

FIG. 67 is a diagram showing a coordinate table of outline vectors obtained by stripe division processing.

68 is a diagram showing coordinates on a division boundary line obtained by scanning the table in FIG. 67.

69 is a diagram in which the packets in FIG. 68 are rearranged by the X coordinate.

70 is a diagram in which the packet pairs of FIG. 69 are rearranged according to conditions.

FIG. 71 is a diagram showing a result of integrating and arranging outline vectors subjected to division processing.

FIG. 72 is a diagram showing an input image for explaining the seventh embodiment.

[Fig. 73] Fig. 73 is a diagram for describing a starting point and an ending point of a horizontal vector existing on a stripe division boundary line.

FIG. 74 is a diagram showing a coordinate table of outline vectors obtained by stripe division processing.

FIG. 75 is a diagram showing coordinates on a division boundary line obtained by scanning the table in FIG. 74.

76 is a diagram in which the packets in FIG. 75 are rearranged by the X coordinate.

77 is a diagram in which the pairs of packets in FIG. 76 are rearranged according to conditions.

[Fig. 78] Fig. 78 is a diagram illustrating a result of integrating and arranging outline vectors that have been divided.

[Fig. 79] Fig. 79 is a configuration diagram in which the present embodiment is applied to a receiving-side facsimile.

FIG. 80 is a configuration diagram in which the present embodiment is applied to a facsimile on the transmission side.

FIG. 81 is a configuration diagram in which the present embodiment is applied to a facsimile for both transmission / reception.

[Explanation of symbols]

 501 input control circuit 502 to 504, 507 to 512 latch 505 and 506 FIFO 513 and 514 input port 515 main scanning counter 516 sub scanning counter 517 input / output control port 519 CPU 520 memory 521 disk I / O 522 disk

Claims (26)

[Claims] 1. An image processing method for extracting a contour vector of an input image from an image, a process of dividing an image into a plurality of band-shaped images and inputting the contours, and a contour extracting each contour vector for each inputted band-shaped image unit. An image processing method comprising: an extraction step. 2. The image processing method according to claim 1, wherein the number of lines of the band-shaped image can be changed to a desired number of lines. 3. When the band-shaped image has one or more white lines, the band of the band-shaped image is set by a line in which black pixels before and after the white line group exist. The image processing method according to item 1. 4. The boundary position of the band-shaped image is a line at the time when the capacity of the memory for temporarily storing the input image is substantially full, or a line immediately before the time when the white line is detected. The image processing method according to claim 1, characterized in that 5. An image processing apparatus for extracting a contour vector of an input image from an image, inputting means for dividing an image into a plurality of strip-shaped images and inputting the same, and extracting each contour vector for each input strip-shaped image unit. An image processing apparatus comprising: a contour extracting unit. 6. The image processing apparatus according to claim 5, wherein the number of lines of the band-shaped image can be changed to a desired number of lines. 7. The band-shaped image boundary is set by a line in which black pixels before and after the white line group exist when one or more white lines are present in the band-shaped image. The image processing device according to item 5. 8. The boundary position of the band-shaped image is a line at the time when the capacity of the memory for temporarily storing the input image is substantially full, or a line immediately before the time when the white line is detected. The image processing apparatus according to claim 5, characterized in that 9. An image processing method for extracting a contour vector of an input image from an image, a step of dividing an image into a plurality of strip images and inputting the contour, and a contour extracting each contour vector for each input strip image. An image processing method comprising: an extraction process and a smoothing process for smoothing the contour vector of each extracted strip-shaped image. 10. The image processing method according to claim 9, further comprising the step of scaling the contour vector smoothed in the smoothing step to reproduce a binary image. 11. In the smoothing step, in a vector in the vicinity of the boundary between each of two continuous strip images, a significant vector coordinate position of a contour vector connected by the two strip images is to be smoothed. The image processing method according to claim 9, wherein the image processing method is excluded from. 12. An image processing apparatus for extracting a contour vector of an input image from an image, inputting means for dividing an image into a plurality of strip images and inputting the same, and extracting each contour vector for each input strip image. An image processing apparatus comprising: a contour extracting unit; and a smoothing unit that smoothes a contour vector of each extracted strip-shaped image. 13. The image processing apparatus according to claim 12, further comprising means for scaling a contour vector smoothed in a smoothing step to reproduce a binary image. 14. The smoothing means smoothes a coordinate position of a significant vector of a contour vector connected by the two strip-shaped images in a vector in the vicinity of a boundary between each of the two continuous strip-shaped images. 13. The image processing apparatus according to claim 12, further comprising means for excluding the above. 15. An image processing method for extracting a contour vector of an input image from an image, a process of dividing an image into a plurality of strip images and inputting the contour, and a contour extracting each contour vector for each input strip image. An image processing method, comprising: an extraction step and a step of integrating the contour vector of the extracted strip-shaped image. 16. The number of lines of the band-shaped image can be changed to a desired number of lines.
The image processing method according to item 5. 17. The band-shaped image boundary is set by a line in which black pixels before and after the white line group exist when one or more white lines exist in the band-shaped image. Item 15. The image processing method described in Item 15. 18. The boundary position of the band-shaped image is set to a line at the time when the capacity of the memory for temporarily storing the input image is substantially full, or a line immediately before the time when the white line is detected. The image processing method according to claim 15, characterized in that 19. The method according to claim 1, further comprising a smoothing step for smoothing the integrated contour vector.
The image processing method according to item 5. 20. The image processing method according to claim 19, further comprising the step of scaling the contour vector smoothed in the smoothing step to reproduce a binary image. 21. An image processing apparatus for extracting a contour vector of an input image from an image, wherein the input means divides the image into a plurality of strip-shaped images and is input, and each contour vector is extracted for each input strip-shaped image. An image processing apparatus comprising: a contour extracting means; and an integrating means for integrating the extracted contour vectors of the strip-shaped image. 22. The number of lines of the band-shaped image can be changed to a desired number of lines.
The image processing device according to item 1. 23. When one or more white lines are present in the band-shaped image, the band of the band-shaped image is set by a line in which black pixels before and after the white line group are present. The image processing device according to item 21. 24. The boundary position of the band-shaped image is a line at the time when the capacity of the memory for temporarily storing the input image is substantially full, or a line immediately before the time when the white line is detected. The image processing apparatus according to claim 21, characterized in that 25. The method according to claim 2, further comprising a smoothing step for smoothing the integrated contour vector.
The image processing device according to item 1. 26. The image processing apparatus according to claim 25, further comprising a step of scaling a contour vector smoothed in the smoothing step to reproduce a binary image.