JPS6242315B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a labeling processing circuit for an image processing apparatus, and more particularly to a labeling processing circuit for an image processing apparatus suitable for labeling independent elements present in a binary image.

Conventionally, the labeling processing circuit of this type of image processing apparatus has been used to detect an independent label "1" existing in a binary image of m width and n length, as shown in FIG. 1a.
_{As shown in FIG} .
It is well known that this circuit performs a process of attaching labels (numbers) such as 2, 3, . . . and storing them in a label storage memory. Therefore, FIG. 1b shows the principle storage form of the label storage memory used in the processing circuit, and the symbols m and n correspond to the images in FIG. 1a, and The code l indicates the number of images to be stored.

FIG. 2 is a block diagram showing a specific configuration of the labeling processing circuit of the image processing apparatus. As shown in this figure, the labeling processing circuit 10 includes two
Binary image data 1 read from value image memory 12
00 for multiple rasters and stores nearby image data 102.
2 based on the line buffer 14 to be output as
A label information generating section 16 generates label information 106 for a point of interest in order to label independent elements existing in a value image, and a label information generating section 16 stores one raster of the label information 106 from this label information generating section 16. , and a labeling external control section 20 that causes the label information generation section 16 to output previous raster label information 104 in correspondence with the neighboring image data 102 read out during the next raster scan.

Labeling processing circuit 10 configured in this way
According to, for example, neighboring image data 102A from a line buffer 14 storing a plurality of rasters of binary image data 100 read from a binary image memory 12 storing binary images as shown in FIG.
(see FIG. 5a) and supplies it to the label information generating section 16, where the label information generating section 16 generates the data as shown in FIG. b
As shown in the figure, independent elements WL ₁ to _{WL 5} are labeled and stored in the label storage memory 18.

FIG. 3 is a block diagram showing the detailed configuration of the label information generating section in the conventional labeling processing device. As shown in the figure, neighboring image data x ₀ ~
x ₄ into the decoder 22, and the decoder 22
The point of interest x ₀ is the first logic (hereinafter referred to as logic “1”), and the connected data x ₁ , x ₂ , x ₃ and x ₄ are the second logic (hereinafter referred to as “0”). It is configured to send an output 108 if determined. The counter 24 that receives the output signal 108 from the decoder 22 is configured to start counting in response to the output signal 108. In this case, the selector 26 is configured to select the count value 110 from the counter 24 based on the output signal 108 from the decoder 22 and supply it to an AND circuit (hereinafter referred to as an AND circuit) 30. . This AND circuit 30 adds the signal of the point of interest x ₀ to the other input terminal and outputs the signal 112 from the selector 26 as the label information 106, thereby attaching a new label to the point of interest x ₀ . It is composed of Further, the shift registers 32, 34 and 36 are connected as shown in the figure, and label information 104A already labeled corresponding to neighboring image data x ₃ , x ₂ and x ₁ , that is, label information L in the previous raster ₁ , ^L2 and _L3 are stored. Also, the output 1 of the AND circuit 30
12 is stored in the shift register 38. The respective label information SL ₁ output from the shift registers 32, 34, 36 and 38,
SL ₂ , SL ₃ and SL ₄ are adapted to be supplied to a comparator 40 . This comparator 40 is configured to detect the maximum value (or the minimum value other than "0") among the input label information SL ₁ , SL ₂ , SL ₃ and SL ₄ and send it to the selector 26 has been done. This selector 26 is configured so that the maximum value (minimum value) 114 of the label information sent from the comparator 40 can be supplied to the selector 26 . The selector 26 is
When the output signal 108 from the decoder is at logic "0", the comparator 40 is selectively controlled and the signal 114 is output to the AND circuit 30 as the selector output 112. This AND circuit 30 performs a logical _AND operation between the point of interest
The output signal 112 of is sent out as label information 106.

Label information generation unit 16 configured as described above
Explain the operation. In particular, the states of the point of interest x ₀ and the connected data x ₁ to x ₄ of the neighboring image data 102 taken in from the line buffer 14 will be explained by case.

First, in the first case, x ₀ is logic “1” and x ₁ to _{x 4}
This is the case when all of the values are logic "0". in this case,
Output signal 108 from decoder 22 is logic “1”
It is thought that. Therefore, the counter 24 is
It starts counting and outputs the counting completion value as an output signal 110. At this time, the selector 26 outputs the output signal 1
08, the counter 24 side is selected, and the output signal 112 of the selector 26 is the count end value 110 of the counter 24. Therefore, the label information 106 output from the AND circuit 30 is
Since x ₀ =“1”, the count end value 110 of the counter 24 will be outputted.

Next, in the second case, x ₀ is logic “1”, x ₁ ~ _{x 4}
This is the case when one or more of them is logic "1".

In this case, the output signal 108 from the decoder 22
may be considered to be logic "0". Therefore, the counter 24 stops counting. Also, at this time, the output signal 108 causes the selector 26 to output the output signal 114 from the comparator 40 as its output signal 112. This comparator 40 is connected to the shift register 3
Output signals SL ₁ from 2, 34, 36 and 38,
Among the signals SL ₂ , SL ₃ and SL ₄ , for example, the maximum value is output as the output signal 114 . Therefore, the signal output from the AND circuit 30 as the label information 106 is the label information for the previous raster.

The third case is a case where the point of interest x ₀ is logic "0".

In this case, the output signal 108 output from the decoder 22 may be set to logic "0".
The counter 24 is of course prohibited from counting, and the output signal 114 from the comparator 40 is selected as the output signal 112 from the selector 26. However, the AND circuit 30 does not output the label information 106 because x ₀ is logic "0".

The label information generating section 16 operates as described above.

FIG. 4 is an explanatory diagram shown for explaining labeling processing according to a conventional example. 120 in the figure
is an example of binary image data 100 taken out from the binary image memory 12, and the label information generation unit 16
This is the label information memory 124 of the label information 106 that has been subjected to the labeling process 122 and stored in the label storage memory 18. In the case of a step-like figure as shown in Figure 4, the point marked with an
The sequential counter 24 counts up (counts up) the pixels 126 labeled Y ₁ , Y ₂ , . . . , Y ⁷ and stores them in the label storage memory 1 as shown in the figure.
6 are stored as labels 1, 2, . . . , 7. In this way, a large number of labels are attached to the same pixel 126, and since the number of bits in the counter 24 is finite in this case, it may overflow beyond this maximum value. For example, if the number of bits in the counter is l, the maximum count value is 2 ^l -1. Therefore, when a large number of graphics as shown in FIG. 4 exist as elements in one screen, there is a particularly strong possibility that overflow will occur as described above.

Furthermore, to explain in detail, when labeling the point of interest x ₀ , the information that determines the label value is the neighboring image data x ₁ to x ₄ shown in FIG. This is label information L ₁ to L ₄ (see FIG. 5b) allocated corresponding to image data x ₁ to x ₄ . When labeling with this much data, as shown in Figure 4, for example, if the interval between the symbols Y ₁ and Y ₂ in the figure in the raster direction (in this case, the horizontal direction) is two or more pixels apart. As a result, the labeling counter 24 counts up frequently, resulting in an inevitable overflow of the counter.

The reason why this phenomenon occurs is that when labeling the point of interest x ₀ , the point of interest x ₀ in the previous raster direction
This is because the label data attached to the image data that is not connected to the image data is ignored.

SUMMARY OF THE INVENTION An object of the present invention is to provide a labeling processing circuit for an image processing apparatus that eliminates the drawbacks of the prior art described above and reduces the probability of overflow of a labeling counter.

In order to achieve the above object, the present invention provides that a point of interest among neighboring image data is a first logic (for example, logic "1"), and connected image data and previous raster extended image data connected to this point of interest are In the case of the second logic (for example, logic "0"), a counter that generates labeled information is counted, and the counting completion value is output as label information, and when the point of interest is the first logic, neighboring image data and If any one of the previous raster extended image data is the first logic, the counter is prohibited from counting, and the raster extended image data including the point of interest is the first logic that is continuous from the point of interest. The extended image data is detected and label information formed based on previous raster label information including previous raster extended label information corresponding to the detected extended image data is output.

Hereinafter, one embodiment of the present invention will be described based on the drawings.

First, the principle of the present invention will be explained. In the present invention,
The conditions for counting up are further made stricter by taking in the previous raster extended image data x ₁ '' to x _N '' as information as a condition for counting the labeled counter. In other words, it is the previous raster direction extended image information in addition to the conditions of x ₀ = “1” and x ₁ to _{x 4} = “0”.
In addition to causing the counter to count only when all the conditions x ₁ ″ to x _N ″ = “0” are satisfied,
The extended image data from x ₁ ' to x' _N+1 is processed by AND circuits 42X ₁ , 42X ₂ , 42 as shown in FIG.
By connecting _XN , the position where logic "1" continues is detected, and the output signal of that logic " ₁ " _is
Output. Further, the previous raster extended label information L' 1 to L' _N allocated corresponding to the previous raster extended image data x'' ₁ and x'' _N existing in the previous raster n- ₁ and the corresponding output signals X ₁ to _{X N} AND circuit 44X ₁ , 44X ₂ , 44
The label information connected to x ₀ is extracted from _{the previous raster extended label information L' 1 to L' N by performing a} logical product on each of will be supplied.
The principle shown here is the concept of 4-connection.
It is based on the idea that pixels of 2 are considered to be connected. On the other hand, there is the idea of 8-connection, in which the pixel of interest is considered to be a connection of "1" pixels that are connected vertically, horizontally, and diagonally, but it goes without saying that the principle is basically the same. . In other words, it is only necessary to extract to what extent pixels of "1" are connected to the point of interest within the range of the expanded image data. By doing this, the probability that the labeling counter will overflow can be significantly reduced.

It is known from simulation results that the labeling circuit operates with the highest efficiency when the number of subscripts N is between N=1 and N=5.

FIG. 7 is a block diagram showing one embodiment of the present invention, in which the subscript N is 8 when N=1.
This is an example of a circuit that performs labeling by concatenation. In the embodiment shown in FIG. 7, the same components as those shown in FIG. 3 are designated by the same reference numerals, and the description thereof will be omitted. The embodiment of FIG. 7 differs from the configuration of FIG. 3 in that the decoder 46 is configured such that the point of interest x ₀ is logic "1" and the connected image data x ₁ to x ₄ and the previous raster extended image data x'' ₁ For example, when both are logic "0", an output signal 108 of logic "1" is output, and for other conditions, for example, logic "0" and output signal 108 are output.
is configured so that it is output, and the point of interest x ₀ and
_{The signal SX 1 from the} AND circuit 42
The AND circuit 44 inputs the previous raster extended label information signal SL ₁ ' from the shift register 48 that is input to one input terminal of the X ₁ and stores the previous raster extended label information L' ₁ of the previous raster label information 104.
X ₁ is inputted to the other input terminal, and the logical product output signal SSL' ₁ of the previous two signals SX ₁ and SL' ₁ in the AND circuit 44X ₁ is supplied to the comparator 40 as one piece of labeled information. At the point.

The operation of this embodiment configured in this manner will be described below. In the figure, a decoder 46 receives neighboring image data 102 from the line buffer 14.
is the counter 24 from the neighboring data x ₀ to x ₄ and x″ ₁
Determine the condition for counting up and output signal 1.
Send 08. In this embodiment, the decoder 46 receives the attention point x ₀ =“1” and the connected image data x ₁ to _{x 4}
=" ₀ " and previous raster _{extended image} data Similarly, the shift registers 34, 32, 38 and 48 have label information L ₂ , L ₁ , L ₄ and L assigned to the image data x ₂ , x ₁ , x ₄ and x″ ₁ , respectively. ′ ₁ is stored. Also, OR circuit 45X ₁ and AND circuit 42X ₁
detects that the point of interest x ₀ is connected to x ₂ ″ in an 8-connection based on x ₁ , extended image data x ₁ ′, and previous raster extended data x ₁ ″, and sends out an output signal SX ₁ do. When this signal SX ₁ is sent to the AND circuit 44X ₁ , label information assigned to the previous raster extended image data x″ ₁ stored in the shift register 48
Assuming that L″ ₁ is connected to the point of interest x ₀ , selector 4
0. That is, AND circuit 44X ₁
In this case, when the label information L' ₁ and the point of interest x ₀ are connected, the label information L' ₁ stored in the shift register 48 is valid, and when they are not connected, the control becomes invalid. It is done. Then, in the comparator 40, the shift registers 32, 34, 3
Label information stored in 6, 38 and 48
The maximum (or minimum other than "0") value 114 is extracted from L ₁ , L ₂ , L ₃ , L ₄ and L' ₁ and sent to the selector 2.
Supply to 6. Output signal 114 of this comparator 40
and the output signal 110 of the counter 34 are the selector 20
The selector 26 is controlled by the output signal 108 of the decoder 46 to select one of the signals, and the output signal 112 is sent to the AND circuit 30. In this case signal 108
is being sent out (for example, a logic "1"), the output signal 110 of the counter 24 is selected as the output signal 112, and when the signal 108 is not being sent out (for example, a logic "0"), the output signal 110 of the counter 24 is selected as the output signal 112. The output signal 114 of is selected as the output signal 112. The AND circuit 30 performs control that is valid only when the point of interest x ₀ is "1 _" by ANDing the output signal 112 of the selector 26 and the point of interest x 0 . At this time, the signal 106 sent from the AND circuit 30
is the label information for the point of interest x ₀ .

As described above, in the present invention, the conditions for determining the label when performing the labeling process for the point of interest x ₀ are expanded compared to the conventional example, so that the number of times the counter 24 should be counted It was possible to reduce the probability that the counter 24 would overflow.

In short, in this embodiment, when labeling the point of interest x ₀ , image data other than the connected image data x ₁ to x ₄ connected to the point of interest x ₀ , that is, the point of interest
The label of the previous raster is expanded to the previous raster extended image data x″ ₁ which is two or more pixels away from x ₀ , and is used to determine the labeling, and is connected to the point of interest x ₀ with a continuous “1”. This allows the information to be reflected in the labeling of x _0. This reduces the number of times the labeling counter needs to be counted up and reduces the probability of counter overflow. Furthermore, since conventional processing can be performed simultaneously to determine the connectivity of expanded image data, the processing time does not increase.

It goes without saying that the above embodiment may be constructed using negative logic.

As described above, according to the present invention, since the labeling counter does not overflow, reliability can be improved.

[Brief explanation of the drawing]

Fig. 1 is an explanatory diagram for explaining the outline of labeling processing, Fig. 2 is a block diagram showing the overall configuration of a labeling processing circuit of an image processing device, and Fig. 3 is a label information generation in a conventional labeling processing circuit. 4 is an explanatory diagram for explaining the conventional labeling operation, and FIG. 5 is a block diagram showing the 3rd section.
FIG. 6 is a block diagram showing the basic principle of the present invention, and FIG. 7 is a block diagram showing an embodiment of the present invention. 14... Line buffer, 16... Label information generation section, 18... Label storage memory, 20... Labeling external control section, 24... Labeling counter, 26...
Selector, 32, 34, 36, 38 and 48...Shift register, 40...Comparator, 30, 42 and 44
...AND circuit, 46...decoder, x ₀ ...point of interest, x ₁
~x ₄ ...Concatenated image data, L ₁ ~ _{L 4} ...Previous raster label data, x' ₁ ~x' _x+1 ...Extended image data, x'' ₁ ~ x'' _N
...Previous raster extended image data.

Claims (1)

[Claims] 1 Neighboring image data x i _-1,j-1 which is image data adjacent to the point of interest x _i,j among the image data stored in multiple rasters from the binary image data from the binary image memory and raster scanned. , x _i,j-1 , x _i+1,j-
1 , a line buffer outputting as x _i-1,j ,
a label information generation unit that generates label information for the point of interest x _i,j based on the neighboring image data from this line buffer and previous raster label information; and a label information generation unit that stores the label information from the label information generation unit for the entire screen. A label storage memory stores one raster worth of label information from the label information generating section, and supplies the label information corresponding to neighboring image data read out during the next raster scan to the label information generating section. In the labeling processing circuit of an image processing device configured to include a labeling external control section, the label information generation section is configured such that a point of interest x _i,j of neighboring image data from the line buffer is a first logic; This point of interest x _i,j
Connected image data x _i-1,j-1 , x _i,j-1 ,
x _i+1,j-1 , x _i-1,j , x _i,j and raster extended image data x _{i+2,j-1 ,} x _i+3,j-1 , x _{i+4,j -1} ,...
If x _i+o,j-1 is the second logic, it is output as new label information, and the point of interest x _i,j is the first logic, and it is either the neighboring image data or the previous raster extended image data. If one of them is the first logic, detect the extended image data that is the first logic consecutively from the point of interest x _i,j in the extended image data of the raster including the point of interest x _i,j , and 1. A labeling processing circuit for an image processing apparatus, characterized in that the labeling processing circuit is configured to output label information formed based on previous raster label information including corresponding previous raster extended label information.