JP3272381B2 - Region boundary point extraction method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a region in image data (a connected component of pixels having the same pixel value or the same label).
And an area boundary point extraction method for extracting the boundary points of the region along with the context of the boundary points.

[0002]

2. Description of the Related Art In a character recognition device, a drawing recognition device, a document image (mixed character / chart) recognition device, a grayscale image / color image recognition device, etc., a connected component having the same pixel value (or label) in an image is used. Consider a region, detect a boundary point belonging to the boundary of the region (but inside the region), and, for example,
When boundary point tracking is performed so that the inside of the area is viewed on the left hand, it is often necessary to perform an area boundary point extraction process of giving an adjacent boundary point a context. The processing on the boundary point of the black pixel connected component in the binary image corresponds to the special case. Conventionally, such region boundary point extraction is a method based on sequential processing (for example, “Digital Image Processing” translated by Shin Nagao, Modern Science Co., pp.353-361).

[0003]

However, the conventional sequential processing method has a problem that a long time is required for the processing. SUMMARY OF THE INVENTION It is therefore an object of the present invention to provide a method for easily performing parallel processing and extracting a region boundary point at high speed.

[0004]

A problem in parallelizing the process of extracting area boundary points is that the number of boundary points corresponding to one pixel is not always one (up to four). For example, if a 3 × 3 pixel pattern centered on a certain pixel is the fifth eye pattern of the die, four boundary points corresponding to the pixel are required (however, in the case of eight connections). As described above, in a situation where there are a plurality of boundary points corresponding to one pixel, there is a problem that it is not easy to uniquely determine the context of the boundary points.

In order to solve this problem, the present invention focuses on a local traveling direction corresponding to a boundary point tracking direction, and furthermore, it is necessary to correspond to each pixel so as to determine the context of the boundary point. Prepare a table like

The basic structure of this table has a maximum of eight entries, and each entry has three sets of information, ie, [boundary point number (id), backward code, forward code].
Represents Here, [boundary point number] means a number for identifying the boundary point, [backward code] is a direction code indicating the traveling direction when entering the boundary point, and [forward direction code] is This is a direction code representing the traveling direction when the vehicle leaves the boundary point.

According to the first aspect of the present invention, a boundary point is detected by observing a 3 × 3 pixel pattern centered on a pixel of interest using the pixel correspondence table having such a basic structure. A set of the boundary point number, the backward code and the forward code is set in one entry of the table. Then, by referring to the table of neighboring pixels using the direction code as a key, the context is determined.

The determination of the context of the boundary point by referring to the table can be performed for the pixels for which the table of the peripheral pixels is set, and can be simultaneously executed for a plurality of pixel positions satisfying this condition. It is independent of the table setting process by pattern observation. Therefore, the processing of pattern observation and table setting can be performed simultaneously for a plurality of pixel positions. That is, the boundary point extracting method of the present invention is essentially easy to perform parallel processing.

Attention is paid to such essential features.
The invention uses a plurality of means for observing a 3 × 3 pixel pattern and setting a table, and a plurality of means for determining the anterior-posterior relationship of a boundary point with reference to the table, to parallelize the processing. The invention according to claim 3 uses a unit for buffering pixel values for three rows and a unit for buffering a table corresponding to pixels for three rows, and uses 3 ×
The processing for observing the three-pixel pattern and setting the table and the processing for determining the anteroposterior relationship of the boundary points with reference to the table are pipelined to parallelize the processing.

According to a fourth aspect of the present invention, the processing is of a scanning type.
That is, the target pixel is selected and processed in the scanning order of the image data. In the case of the scanning type processing, since some pixels in the peripheral pixels of the target pixel have already been processed and the table has been set,
The relationship between the boundary points of these pixels and the boundary point of the position of the target pixel can be determined by referring to the table. Therefore, only the information (direction code) related to the unprocessed pixel in the surrounding pixels is set in the target pixel table. When performing main scanning from left to right and sub-scanning from top to bottom,
Only information related to the lower left, lower, and lower right pixels is set in the table.

According to a fifth aspect of the present invention, in the method of the fourth aspect, the forward code and the backward code are treated in a unified manner (the forward code and the backward code are non-overlapping codes). A set of the direction code and the boundary point number is one entry of the table.

[0012] There are code combinations that cannot occur at the same time for both backward and forward codes. According to a sixth aspect of the present invention, in the method of the fourth aspect, such a set of non-simultaneous codes (a pattern group described later in relation to the embodiment) is assigned to each entry of the table, and only the boundary point number is assigned. Is set in the table. That is,
Only the boundary point number is one entry.

The invention of claim 7 is the invention of claim 4, 5 or 6.
In the method of the present invention, a 3 × 3 pixel pattern is observed and a table is set by using means for buffering pixel values for three rows and means for buffering a table corresponding to pixels for two rows. The process and the process of referring to the table to determine the context of the boundary point are pipelined.

According to an eighth aspect of the present invention, in the method according to any one of the first to seventh aspects, the image data is main-scanned from left to right and sub-scanned from top to bottom. The pixel value of the lower pixel is equal, and the pixel value of the target pixel and the pixel immediately below it are not equal, and the pixel value of the pixel immediately below the target pixel and the pixel to the left of the target pixel are not equal, If the pixel value of the pixel of interest is equal to the pixel value of the two pixels, noise removal processing for changing the pixel immediately below the pixel of interest to the pixel value of the pixel of interest is performed. The table is set based on the pixel pattern. Further, in the noise removal processing according to the invention of claim 8 which targets binary image data, the pixel value of the target pixel is equal to the pixel value of the lower left and lower right pixels, and the pixel of interest is equal to the pixel value of the target pixel. If the pixel value of the pixel below is not equal and the pixel value of the pixel of interest is equal to the pixel value of the two pixels, the pixel below the pixel of interest is changed to the pixel value of the pixel of interest. Simplified.

[0015]

As described above, according to the first aspect of the present invention, the parallel processing of boundary point extraction is essentially facilitated.

According to the second, third or seventh aspect of the present invention, the parallelization of the processing makes it possible to remarkably increase the speed of boundary point extraction and to perform real-time processing. Further, according to the third or seventh aspect of the present invention, the amount of memory required for storing the table is small, and it is possible to achieve both high-speed processing and effective memory utilization.

According to the fourth aspect of the present invention, the required table size can be reduced as compared with the method of setting information on all the surrounding pixels in the table, and the waste of the table reference processing is reduced, thereby improving the processing efficiency. It is also effective in terms of aspects.

According to the fifth aspect of the present invention, by adopting the above-described table structure, compared with a table structure having a set of [boundary point number, backward code and forward code] as one entry, , [Boundary point, backward code]
The table size can be further reduced as compared with a table structure in which one boundary point information is stored by a pair of the entry of [boundary point and forward code]. According to the invention of claim 6, the table size can be further reduced.

According to the eighth or ninth aspect of the present invention, an area (noise) of one size completely contained in another area in the image can be excluded from the target of the boundary point extraction processing, and the processing amount can be reduced. Can contribute.

[0020]

Embodiments of the present invention will be described below with reference to the drawings.

Embodiment 1 FIG. 1 is a block diagram showing an example of a system configuration for executing an area boundary point extracting process according to the present invention. Reference numeral 10 denotes an image memory for storing binary image data to be processed, 11 denotes a central processing unit for executing an area boundary point extraction process on the binary image data in the image memory 10, and 12 denotes an image memory for the processing. This is a program memory that stores programs. Reference numeral 13 denotes a data memory that provides a working storage area for processing, in which a table corresponding to pixels, a final result (specific examples are described in detail), and the like are stored.

Although such a configuration using software has general versatility, it has great limitations in terms of high-speed performance. Therefore, a configuration in which necessary functions are realized by hardware or firmware is naturally possible. FIG. 2 shows an example of such a system configuration, in which reference numeral 20 denotes an image memory for storing image data, 21 a table memory for storing a pixel correspondence table (described later), and 22 a final result. The data memory 23 performs a pattern observation and a direction code determination described later to set a pixel correspondence table on the table memory 21, and a required number of boundary point structures (described later) on the data memory 22. A decision unit 24 is a context setting unit for referring to the context of the boundary point structure on the data memory 22. In the configuration shown in FIG. 1, the direction code determiner 23 and the context setting unit 24
This is realized by the first function. In the following description, the configuration of FIG. 1 will be referred to.

Next, the contents of the processing will be described. Binary image data is input to the image memory 10 from an external image scanner or the like. FIG. 7 shows the boundary point extraction processing.
As shown in the flow chart of FIG. 5, the processing comprises two processing steps A and B. This processing is performed after the input of the image data is completed, or is executed in parallel with the input.

A table corresponding to each pixel in the image data is prepared on the data memory 13. As described above, this table stores up to eight entries representing [boundary point number], [backward code], and [forward code].
The table has entries, and the specific structure will be described later.

Processing stage A A 3 × 3 pixel pattern centered on each pixel in the binary image data is observed for each pixel in the binary image data, and a boundary point is detected and registered. Are set, and a required number of boundary point structures are created in the data memory 22.

That is, when a pixel pattern centered on a certain pixel of interest matches one or more of the patterns shown in FIG. 3, the number of matching points is registered and the number of matching points in the corresponding table is determined. Entry with the boundary point number,
A backward code (a direction code corresponding to the matching pattern in FIG. 3) and a forward code obtained from FIG. 6 corresponding to the backward code are set. The correspondence between the forward direction code and the pixel pattern is as shown in FIG. The correspondence between the direction code and the direction is as shown in FIG.

Referring now to FIG. For example,
When the backward code of a certain boundary point is 1, it is assumed that the 3 × 3 pixel pattern matches any of the forward code 3 pattern and the forward code 5 pattern shown in FIG.
In this case, since the forward code 3 is shown on the left side of the forward code 5 in the row of the backward code 1 in FIG. 6, the forward code 3 is selected and set in the table.

FIG. 8 shows an example of the structure of the pixel correspondence table. Reference numerals 31, 32, and 33 denote one entry of the table, respectively, and include three fields of a boundary point number, a backward code, and a forward code. In the case of such a structure, up to four entries are required for one pixel. For the pixel (boundary point) 35 shown in the left part of FIG. 8, the corresponding entry 31 corresponding to the pixel is set to the content as shown. Pixel 36 (boundary point)
For the two entries 32,
33 is set as shown in the figure.

FIG. 9 shows another example of the structure of the pixel correspondence table. Reference numeral 41 denotes eight entries corresponding to the pixel 43 (corresponding to the pixel 35 in FIG. 8), and reference numeral 42 denotes eight entries corresponding to the pixel 44 (corresponding to the pixel 36 in FIG. 8). The order of each entry corresponds to the backward code. That is, this example has a structure in which the backward code of each entry is fixed, and each entry is made up of a boundary point number and a field of a forward code. In the case of pixels 43 and 44, the settings are as shown in the figure.

It is also possible to adopt a structure in which the forward code of each entry is fixed, and the boundary point number and backward code fields are set.

FIG. 10 shows an example of a boundary point structure created in the data memory 22. However, this shows the state after the context is referenced. In this example, 51 is the structure of the boundary point a at the coordinates (3, 4), 52 is the structure of the boundary point b at the coordinates (4, 5), 5
Reference numeral 3 denotes a structure of the boundary point c at the coordinates (4, 6).

After or at the same time as the processing at the processing stage B or more, the reference setting of the boundary points based on the contents of the table, that is, the determination of the context is performed by the context setting unit 24. For a pixel,
If a table corresponding to all the pixels in the vicinity of the 3 × 3 pixels is set, it is possible to determine the order of the boundary points.

Therefore, the boundary point number (id) registered for the target pixel, the backward direction code and the forward direction code are read from the entry of the table of the target pixel. A table (reference table) to be referred to is determined in accordance with the forward direction code, an entry to be referenced is obtained from the reference table using the read backward direction code as a key, and a boundary point id in this entry is read to obtain a boundary point. Are referred to each other.

For example, if the entry content of the boundary point registered for the pixel of interest is (m, 2, 1) (corresponding to the boundary point of boundary point number m in FIG. 8 or FIG. 9), Since the code is 1, which is the direction code indicating the upper right direction from FIG. 5, a table corresponding to the upper right pixel from the target pixel (corresponding to the pixel 36 in FIG. 8 or the pixel 44 in FIG. 9) is referred to.

In the referenced table, there is always only one boundary point of the entry for which the backward code is set to 1. If the content of this entry is (n, 1, 3), this boundary point (boundary point number n in FIG. 8 or FIG. 9)
) Are located in front of the boundary point, and the two boundary points (m) and (n) are related before and after. That is,
The boundary point number of the boundary point (n) is set in the “backward boundary point number (id)” of the structure of the boundary point (m) of the structure as shown in FIG. The boundary point number of the boundary point (m) is set in the “front boundary point number” of the body. Also, since the backward code is 2, the entry (m, 2, 1) of the target pixel is referred to in the process of processing the lower adjacent pixel as can be seen from FIG.

In the case of the example of FIG. 10, if the relationship is such that the boundary is traced leftward and the traces are traced in the order of c, b, and a, the context is referenced as indicated by the arrow. Will be done. That is, the structure 53 at the boundary point c
Is set to the boundary point number of the boundary point b, and the boundary point number of the boundary point c is set to the “backward boundary point number” of the structure 52 of the boundary point b. No., the boundary point number of the boundary point a is set, and the boundary point a
The boundary point number of the boundary point b is set in the “backward boundary point number” of the structure 51. The boundary point structure referred to in such a context is the final result data.

The above-described processing is easy to perform completely in parallel, and by preparing a pixel value buffer for three rows and a buffer for a table for three rows, parallel processing by pipeline processing is also possible. With such parallelization, it is also possible to extract a region boundary point almost in real time (time for inputting an image from a scanner).

Although the forward code is determined based on the backward code, it is obvious that the backward code may be determined based on the forward code. This is the same not only in this embodiment but also in other embodiments described later.

Embodiment 2 In this embodiment, as shown in FIG. 11, a boundary code extraction unit 61 and a context setting unit group 62 are provided to execute boundary point extraction by parallel processing. Direction code determiner group 61
Is a set of a plurality of direction code determiners operating in parallel,
Each direction code determiner is the direction code determiner 23 in FIG.
Is similar to The context setting device group 62 is a set of a plurality of context setting devices that operate in parallel, and each context determination device is the same as the context setting device 24 in FIG. Other configurations are the same as those in FIG.

The first half of the boundary point extraction, that is, the processing corresponding to the processing stage A shown in FIG.
0, the direction code determiner group 61, the table memory 21, and the data memory 22 are involved. The contents of the image memory 20 are observed by the direction code determiner group 61. For complete parallel processing, the data of the pixel to be observed is stored in a normal RA.
It is stored in a flip-flop instead of M. Each direction code determiner of the direction code determiner group 61 observes a 3 × 3 pixel pattern centered on the corresponding pixel, registers the detected boundary point in a pixel correspondence table (on the table memory 21), and The creation of the boundary point structure (on the data memory 22) is executed in parallel for a plurality of pixels. Except that a plurality of pixels are processed at the same time, the processing content by each direction code determiner is the same as that of the first embodiment, and the pixel correspondence table and the structure of the boundary point structure, the pixel pattern and the backward code The rules for correspondence, backward code and forward code are the same as in the first embodiment.

The latter half of the boundary point extraction, that is, the processing corresponding to the processing stage B shown in FIG.
1, the context setting unit group 62 and the data memory 22 are related. Each of the context setting devices of the context setting device group 62 determines the context of the boundary point in accordance with the contents of the 3 × 3 pixel table (on the table memory 21) centered on the corresponding pixel, and determines the boundary point structure. A “backward boundary point number” and a “forward boundary point number” in (on the data memory 22) are set and referenced. Such processing is the same as in the first embodiment except that the processing is parallel processing.

Embodiment 3 In this embodiment, processing is parallelized by pipeline processing, and FIG. 12 shows an example of the system configuration.

In FIG. 12, reference numeral 71 denotes a pixel value buffer for buffering pixel values of three lines (lines) of input image data. 3 × 3 pixel pattern is stored in the 3 × 3 pixel pattern register 72 at the time of output from the pixel 71). 73 is a direction code determiner,
This is done by observing the pattern on the 3 × 3 pixel pattern register 72, detecting the boundary points in the same manner as the direction code determiner 23 of FIG.
And a pixel correspondence table is created. This table is buffered in a table buffer 75 for three rows. When writing the table buffer 75,
A table of 3 × 3 pixels is buffered in a 3 × 3 table register 76.

Reference numeral 77 denotes a context setting device similar to the context setting device 24 of FIG. 2, which operates simultaneously with the direction code decision device 73, and stores the contents of the table buffered in the 3 × 3 table register 76. The context of the boundary point is determined with reference to the boundary point structure on the data memory 74, and the context of the boundary point is referenced. Thus, the final result is obtained in the data memory 74. The rules for the structure of the boundary point structure and the pixel correspondence table, the 3 × 3 pixel pattern, the backward code, and the forward code are the same as in the first embodiment.

According to such a configuration of the pipeline processing, it is possible to speed up the processing only by providing one direction code judging unit 73 and one context setting unit 77, and it is possible to perform the processing with the image input. Real-time processing can also be easily realized.

Embodiment 4 The system configuration of this embodiment can be shown in FIG. 2, but as will be described later, there are differences in the processing contents of the direction code decision unit 23 and the context setting unit 24 and the structure of the pixel correspondence table. is there.

In this embodiment, scanning of image data (main scanning from left to right, raster scanning for sub-scanning from top to bottom)
In this order.
The above embodiments do not have such a limitation. Although the number of boundary points is limited to eight, this is the same as in the above embodiments.

In the case of such a scanning type process, the upper left, upper, upper right and left pixels among the peripheral pixels of the target pixel have been processed (the boundary points corresponding to the pixel have been created). , Unprocessed pixels are pixels on the right, lower left, lower, lower right. Thus, in the present embodiment, a required number of boundary points are created by observing a 3 × 3 pixel pattern centered on the target pixel extracted in the scanning order, and the already processed left, upper left, upper, and upper right The context with the boundary point corresponding to a certain pixel is determined from the information and set in the boundary point structure. At this time, the table corresponding to the pixel of interest contains information relating to the ingress and egress between the unprocessed peripheral pixel position and the boundary point of the current pixel position at the time of processing of those peripheral pixels. Only the information necessary for the decision). By doing so, it is possible to reduce the size of the pixel correspondence table for storing information on the boundary points.

FIG. 13 is an encoding of a local pattern that can occur within a 3 × 3 pixel pattern. Assuming that the inside of the area is tracked as seen to the left, among the pattern codes 0 to 15 and -1 shown, 0 to 7 are codes representing the direction of the boundary point sequence entering the central pixel, that is, the backward code described above. is there. Numerals 8 to 15 are codes indicating the direction of the boundary point sequence exiting from the central pixel, that is, the above-mentioned forward code. In this way, the backward code and the forward code are unified and treated as a pattern code (direction code) without distinction. -1 is a code indicating that the central pixel is an isolated point.

Regarding the pattern codes 0, 1, 2, 3, 4, 5, and 6 and 7 corresponding to the backward code, it is impossible that each pattern is observed simultaneously for one pixel. Similarly, pattern codes 8, 9, 10, and 11, 12 and 13, and 14 and 15 corresponding to the forward code are not observed simultaneously for one pixel. Thus, in the present embodiment, such sets of patterns that do not appear at the same time are grouped as follows (see FIG. 13). Pattern group A (pattern code 0, 1): pattern entering from lower left or lower boundary point Pattern group B (pattern code 2, 3): pattern entering from lower right or right boundary point Pattern group C (pattern code 4, 5) ): Pattern entering from upper right or upper boundary point Pattern group D (Pattern code 6, 7): Pattern entering from upper left or left boundary point Pattern group E (Pattern code 8, 9): Exiting at upper right or upper boundary point Pattern Pattern group F (Pattern code 10, 11): Pattern appearing at the upper left or upper boundary point Pattern group G (Pattern code 12, 13): Pattern appearing at the lower left or lower boundary point Pattern group H (Pattern code 14, 15) ): Pattern that appears at the lower right or right boundary point

Here, in this embodiment, the information stored in the boundary point table includes the pixel of interest, its lower left,
Only information relating to entry and exit from the boundary points that may be formed at pixel positions adjacent to the lower, lower right and left sides. That is, it is only information on the pattern groups A, B, E, and H. This is because, for the other pattern groups C, D, E, and F, it is possible to determine the context of the target pixel position with respect to the boundary point based on the information stored in the table for the processed adjacent pixels.

Hereinafter, the processing contents will be described. FIG. 14 is a schematic flowchart of the process.

The direction code determiner 23 takes out the pixels from the image memory 20 in the scanning order (step 80), observes the pattern of 3 × 3 pixels centering on the pixel of interest, and detects a pattern group pair (step 84). ). The detection of this pattern group pair is as follows.

For the observed pattern codes (backward codes) of the pattern groups A to D, a pattern group determined as follows is detected as a pair. a) (code of) pattern group A, H, E, F,
The first of the matched pattern groups in this order, in any of G (For example, if the pattern matches both the patterns E and F, E and A are detected as a pair of pattern groups since E is first in the order of H, E, F, and G. The same applies hereinafter). b) (code of) pattern group B, E, F, G,
The first of the matched pattern groups in this order, in any of H. c) (code of) pattern group C, F, G, H,
E (the code of) the earliest matched pattern group in this order, in any of E. d) (code of) pattern group D, G, H, E,
F (the code of) the first matched pattern group in this order in any of F.

The observed pattern groups E to H
With respect to the pattern code (forward code), a pair may be detected as follows. e) (code of) pattern group E, B, A, D,
C, the (first code) of the first matching pattern group in this order. f) (code of) pattern group F, C, B, A,
D, (the code of) the first matched pattern group in this order in this order. g) (code of) pattern group G, D, C, B,
A (the code of) the first matching pattern group in this order in any of A. h) (code of) pattern group G, A, D, C,
B (the code of the first matched pattern group in this order).

The direction code determiner 23 creates one boundary point for each pair of such pattern groups, that is, creates one boundary point structure in the data memory 22 (step 90). . However, when the observed pattern code is -1, only one boundary point is created.

As described above, only the information of A, B, G, and H need be stored in the table. Therefore, the direction code determiner 23 determines whether the backward code of each pattern group pair is 4, 5, 6, or 7 (C or D in the pattern group), or 0, 1, 2, or 3 (A or B). Is checked (step 92). If the backward code is 0,1,
In the case of 2 or 3, the direction code determiner 23 then registers the direction code together with the boundary point number in the corresponding table on the table memory 21 (step 94). If the backward direction code is 4, 5, 6 or 7, it is not registered in the table, and the context setting unit 24 refers to the table corresponding to the pixel at the left, upper left, upper or upper right of the target pixel, and The upper boundary point structure is referenced before and after (step 96).

Next, the direction code determiner 23 determines whether the forward code of the pattern group pair is 12, 13, 14 or 15 (G or H), 8, 9, 10 or 1
Check if it is 1 (E or F). And 12,1
In the case of 3, 14, or 15, the code is registered in the table (step 100). Otherwise, the forward code is not registered in the table, and the context setting unit 24 refers to the table corresponding to the left, upper left, upper, and upper right pixel positions of the target pixel, and moves the boundary point structure forward and backward. Reference is made (step 102).

Such processing is performed for all pattern codes
By being executed for the pair, the data memory 22
The boundary point structure to which the context is referred to above is obtained as an extraction result.

FIG. 15 shows an example of the structure of a table corresponding to pixels.
Shown in In this embodiment, since the backward code and the forward code do not overlap as shown in FIG. 13, the forward code and the backward code are unified as unreferenced direction codes, and this and the boundary point number are stored in the table. Set for one entry. In this example, 110 is a pixel 111 shown in the left part.
Is the only pattern group pair detected for this pixel in one entry of the table corresponding to A-E (backward code 0-forward code 9), and E (9)
Does not need to be stored in the table, so backward code 0
Only will be set. Reference numeral 112 denotes two entries of the table corresponding to the pixel 113. In this case, the backward code 1 and the forward code 12 are set in each entry together with the boundary point number. According to such a table structure, it is needless to say that the table size is reduced as compared with the case where a set of (boundary point number, forward code, backward code) is one entry, and one set of (boundary point Number, backward code, forward code) as two sets of (boundary point number and forward code) and (boundary point number and backward code), each of which is a single entry in the table. The table size is half.

Fifth Embodiment This embodiment is an improvement of the fifth embodiment. The system configuration may be the same as that of the fifth embodiment, and the processing is basically the same as that of the sixth embodiment. This can be represented in FIG. The main difference between the present embodiment and the fourth embodiment relates to the table structure. This difference will be described below.

In this embodiment, a table corresponding to one pixel includes four entries, and each entry is
It is assigned to two specific pattern codes that cannot occur at the same time. That is, one table has entries for pattern groups A or E, B or F
Entry for G, entry for G or C,
Consists of entries for H or D. Thus, the number of entries in the table is reduced to half, that is, four. Furthermore, there is a unique relationship between the order of entries and the pattern groups assigned to them.
In other words, the order of entries has meaning. However, this order is an example. As a result of specifying the pattern group (direction code) according to the order of the entries as described above, only the boundary point number needs to be set for each entry, the size of each entry is minimized, and the required table size is set as described in the above. It will be much smaller than in Example 4. However, only the pattern code of one of the pattern groups A, B, G, and H is set in the table, and if the pattern code is subsequently referred to, it is set as one of the pattern groups E, F, C, and D. Will be referenced.

The processing will be described. If the pattern group pair is AE (0-9 in the pattern code), A
Since (backward code 0) is information to be stored, the boundary point number is set in the first entry of the corresponding table in step 94 (FIG. 14). E
Regarding (9), this is not set in the table because it does not need to be stored. This is because in step 102, the boundary point number can be extracted from the first entry of the table corresponding to the pixel above the target pixel to determine the context.

FIG. 16 shows an example of a pixel pattern and setting contents of a table. Reference numeral 120 denotes a table corresponding to the pixel 122 shown in the left part. Reference numeral 121 denotes a table corresponding to the pixel 123. In this example, the pattern group E detected for the pixel 122 is not stored in the table 120, but the context is determined by referring to the first entry of the table 121 when processing the lower left pixel 123. You will understand that.

Embodiment 6 In each of Embodiments 4 and 5, processing can be parallelized by pipeline processing. The present embodiment is an example of parallelization by pipeline processing, and the system configuration is shown in FIG. The contents of the processing are the same as those of the fifth and sixth embodiments except that the processing is a pipeline processing, and the flowchart is shown in FIG.

In FIG. 17, reference numeral 131 denotes a pixel value buffer for buffering pixel values of three lines (lines) of input image data. At the time of input to the pixel value buffer 131 (or at the time of output from the pixel value buffer 131), the pixel value is set to the 3 × 3 pixel pattern register 132.
, The 3 × 3 pixel pattern is stored in the 3 × 3 pixel pattern register 72.

Reference numeral 133 denotes a direction code judging unit (pattern group / pair judging unit) which observes the pattern on the 3 × 3 pixel pattern register 132 and, as described in the fourth or fifth embodiment, determines the pattern group / pair. The pairs are detected, and boundary point structures are created on the data memory 134 by the number of detected pairs. At this time, if the pattern group of the pair is any of A, B, G, and H, the boundary point number is set in the corresponding entry of the table corresponding to the target pixel (the central pixel of the observed 3 × 3 pixel pattern). I do. Here, the table structure is described as having the same pattern group and entry order as in the fifth embodiment, but may be the same as in the fourth embodiment.

Reference numeral 135 denotes a table buffer for buffering two rows of the pixel correspondence table created by the direction code determiner 133. When the table buffer 135 is written, the table is buffered in the table register 136, so that the target pixel of the direction code determiner 133 and a table of a total of five pixels on the left, upper left, upper, and upper right are stored in the table register 136. 136. Reference numeral 137 denotes an in-context relation setting unit, which is used to determine whether a pattern group detected from the target pixel is C, D,
If it is any of E and F, the context of the boundary point is determined by referring to the table of the processed peripheral four pixels on the table register 136, and the context of the boundary point structure on the data memory 134 is determined. Make a reference.

According to such a configuration of the pipeline processing, real-time processing with image input can be easily realized.
Further, the table size may be smaller than that of the third embodiment, so that the capacity of the table buffer 135 and the table register 136 can be reduced.

Embodiment 7 In this embodiment, as preprocessing for the direction code determination in each of the above embodiments, a region having a size of one pixel in the sense of four connections and completely included in another region is regarded as noise. Then, a process for removing most of them is performed. The function of the noise removal processing can be incorporated in the direction code determiner, may be added as an independent circuit before the direction code determiner, and may be implemented by software processing as shown in FIG. In the case of a system configuration, the noise removal processing can be incorporated in a program for the direction code determination processing, or can be added as an independent preprocessing program.
Therefore, description of a specific example of the system configuration is omitted, and the content of the noise removal processing will be described below.

FIG. 18 is a flowchart of the noise removal processing. FIG. 19 is a pattern diagram for explaining noise to be removed.

In step 150, a 3 × 3 pixel pattern centering on the pixel of interest is observed. In the next step 152, if all the peripheral pixels of the target pixel have the same pixel value, the pixel value of the target pixel is changed to the pixel value of the peripheral pixel. That is, the 3 × 3 pixel pattern 161 shown in FIG. 19 is converted like the pattern 163 as a result of removing the central pixel 162 as noise.

In step 154, "the pixel value of the pixel of interest is equal to the pixel value of the lower left and lower right pixels", "the pixel value of the pixel of interest is not equal to the pixel value of the pixel immediately below it", and When the pixel value of the pixel immediately below the pixel and the pixel to the left of the pixel of interest are not equal, the pixel value of the pixel two pixels below the pixel of interest is checked, and when this pixel value is equal to the pixel of interest, The pixel immediately below the target pixel is changed to the pixel value of the target pixel. That is, the pattern 164 shown in FIG.
Is converted as a pattern 167 as a result of the pixel 166 immediately below the pixel of interest 165 being regarded as noise.

In the case of extracting the boundary of only the black pixel area of the black and white binary image, step 154 is simplified as follows.
That is, "the pixel value of the pixel of interest and the lower left and lower right pixels thereof are equal" and "the pixel value of the pixel of interest and the pixel immediately below it are not equal" are two pixels below the pixel of interest. The pixel value of the pixel is checked, and if this pixel value is equal to the pixel value of the pixel of interest, the pixel immediately below the pixel of interest is changed to the pixel value of the pixel of interest. That is, the pattern 16 shown in FIG.
8 is converted as a pattern 171 as a result of removing the pixel 170 immediately below the target pixel 169 as noise.

When such noise processing is performed, the generation of useless boundary points can be reduced by removing the area of size 1 as noise, and thus the effect of reducing the processing amount of boundary point extraction can be obtained.

[0076]

As is apparent from the above detailed description, the following effects can be obtained according to the present invention. (1) According to the first aspect of the present invention, parallel processing of boundary point extraction becomes extremely easy. (2) According to the second aspect of the present invention, extremely high-speed boundary point extraction can be performed by complete parallel processing. (3) According to the third or seventh aspect of the invention, the boundary point extraction processing can be parallelized and speeded up, and the amount of memory for buffering the table and pixel values can be reduced. (4) According to the invention of claim 4, 5 or 6, the table size can be reduced. (5) According to the eighth or ninth aspect of the present invention, noise having a magnitude of 1 completely included in another region can be excluded from boundary point extraction targets, and an increase in processing amount due to noise can be avoided.

[Brief description of the drawings]

FIG. 1 is a block diagram illustrating an example of a system configuration according to a first embodiment.

FIG. 2 is a block diagram illustrating another example of the system configuration according to the first embodiment.

FIG. 3 is a pattern diagram illustrating a 3 × 3 pixel pattern and a backward code.

FIG. 4 is a pattern diagram illustrating a 3 × 3 pixel pattern and a forward code.

FIG. 5 is an explanatory diagram of a direction code.

FIG. 6 is an explanatory diagram of a priority order of selection of a backward code and a corresponding forward code.

FIG. 7 is a processing flowchart of the first embodiment.

FIG. 8 is an explanatory diagram of an example of the structure of a pixel correspondence table.

FIG. 9 is an explanatory diagram of another example of the structure of the pixel correspondence table.

FIG. 10 is an explanatory diagram of an example of a boundary point structure.

FIG. 11 is a block diagram illustrating a system configuration according to a second embodiment.

FIG. 12 is a block diagram illustrating a system configuration according to a third embodiment.

FIG. 13 is a pattern diagram illustrating a pattern code and a pattern group.

FIG. 14 is a processing flowchart of the fourth embodiment.

FIG. 15 is an explanatory diagram of a structure of a pixel correspondence table according to the fourth embodiment.

FIG. 16 is an explanatory diagram of a structure of a pixel correspondence table according to the fifth embodiment.

FIG. 17 is a block diagram illustrating a system configuration according to a sixth embodiment.

FIG. 18 is a processing flowchart of noise removal.

FIG. 19 is a pattern diagram for explaining noise removal.

[Explanation of symbols]

 20 Image memory 21 Table memory 22,74,134 Data memory 23,73,133 Direction code determiner 24,77,137 Pre / post relation setting unit 61 Direction code judgment group 62 Pre / post relation setting group 71,131 Pixel value buffer 72,132 3 × 3 pixel pattern register 75,135 Table Buffer 76 3 × 3 table register 136 table register

Continuation of the front page (58) Field surveyed (Int.Cl. ⁷ , DB name) G06T 7/60 JICST file (JOIS)

Claims (9)

(57) [Claims] 1. An area boundary point extraction method for detecting a boundary point of an area in image data and obtaining the context of the boundary point, a number for identifying the boundary point, and a progress when entering the boundary point. A table of up to eight entries is prepared for each pixel, in which a set of a backward code indicating a direction and a forward code indicating a traveling direction when the vehicle goes out of the boundary point is prepared as one entry, and a table including a target pixel as a center is provided. 3x3
An area boundary point extraction method, wherein the contents of a table corresponding to a target pixel are set by observing a pixel pattern, and the order of the boundary points is determined by referring to the table using a direction code as a key. 2. A plurality of means for observing a 3 × 3 pixel pattern and setting a table and a plurality of means for determining the anteroposterior relationship of a boundary point with reference to the table are used, and the processing is performed in parallel for a plurality of pixel positions. 2. The method according to claim 1, wherein the method is executed in the following manner. 3. A process for observing a 3 × 3 pixel pattern and setting a table using a means for buffering pixel values for three rows and a means for buffering a table corresponding to pixels for three rows. 2. A region boundary point extraction method according to claim 1, wherein a process of determining the context of the boundary points with reference to a table is performed by pipeline processing. 4. A target pixel is selected in the scanning order of the image data,
2. The area boundary point extracting method according to claim 1, wherein only information relating to an unprocessed pixel among its surrounding pixels is set in a table corresponding to the target pixel. 5. The region boundary point extraction according to claim 4, wherein the forward code and the rearward code are treated in a unified manner, and a set of one direction code and a boundary point number is made one entry of a table. Method. 6. The area boundary point extracting method according to claim 4, wherein a plurality of specific direction codes that cannot occur at the same time are assigned to each entry of the table, and only the boundary point number is used as one entry of the table. . 7. A process for observing a 3 × 3 pixel pattern and setting a table using a means for buffering pixel values for three rows and a means for buffering a table corresponding to pixels for two rows. 7. The area boundary point extracting method according to claim 4, wherein the processing of determining the anteroposterior relationship of the boundary points by referring to the table is performed by pipeline processing. 8. Assuming that image data is main-scanned from left to right and sub-scanned from top to bottom, the pixel value of the target pixel is equal to the pixel value of the lower left and lower right pixels, and the pixel of interest is The pixel value of the lower pixel is not equal, and the pixel value of the pixel immediately below the target pixel and the pixel to the left of the target pixel are not equal,
If the pixel value of the pixel of interest is equal to the pixel value of the two pixels, noise removal processing for changing the pixel immediately below the pixel of interest to the pixel value of the pixel of interest is performed. The method according to any one of claims 1 to 7, wherein the table is set based on the pixel pattern. 9. Assuming that image data is binary data, main scanning is performed from left to right and sub-scanning is performed from top to bottom, the pixel value of the target pixel and its lower left and lower right pixels are equal, and If the pixel value of the pixel and the pixel immediately below it are not equal and the pixel value of the pixel of interest and the two pixels below it are equal, change the pixel immediately below the pixel of interest to the pixel value of the pixel of interest 8. The method according to claim 1, wherein a noise removal process is performed, and a table is set based on the 3 × 3 pixel pattern after the noise removal process.