JPS6329304B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Application of the Invention] The present invention relates to an image processing apparatus that processes raindrop images, particle images, blood cell images, and the like.

[Background of the invention]

FIG. 1 shows a case where an image having a relatively dense pattern is binarized using an appropriate threshold value and divided into a pattern part P and the other part, that is, a non-pattern part. When processing such a binary image, the pattern part P has 1 incomplete object Q over the edge of the image 2 multiple objects O _i (object), and the non-pattern part has 1 object O There is an area outside _i , that is, background B (back) 2 and an area surrounded by object O _i , that is, hole H, and it is necessary to distinguish between these. For example, it is necessary to convert a binary pattern (P,) to a multi-value pattern (O ₁ , O ₂ , O ₃ , H, B).
However, an effective and simple method for performing such processing using a raster scan method has not yet been proposed.

[Purpose of the invention]

SUMMARY OF THE INVENTION The present invention aims to provide a device that can rapidly propagate the same label over the entire area of independent patterns in an image, and is capable of processing such as multi-value conversion of a binary image as described above. It provides a solution.

[Summary of the invention]

The present invention provides a means for sequentially propagating information to adjacent pixels according to a predetermined propagation rule, detecting incomplete objects in contact with the periphery, detecting holes in the object, and labeling separated objects. This is what we provide.

FIG. 2 is a diagram for explaining the principle of sequentially propagating information to adjacent sections. First, scan the mask (indicating the range of sections related to processing) from the top left, right, bottom right, bottom,
The information is successively propagated in the lower left direction. In this case, the information propagated to the target partition M (i, j) is, for example, the information propagated to the partition M (i, j) and the adjacent partition M (i-1,
j-1), M(i, j-1), M(i+1, j-1),
Five pieces of information x, a, b, c, M(i-1, j)
Determined by d. Next, the mask is scanned in the reverse direction (scan) from the lower right, and information is sequentially propagated in the left, upper left, upper, and upper right directions, and the target section (i, j) is
For example, the information to be propagated to the partition M(i, j) and the adjacent partitions M(i+1, j+1), M(i, j+
1), M(i-1, j+1), M(i+1, j) 5
It is determined based on the following information x′, a′, b′, c′, and d′. By performing these two processes in the forward and reverse directions, the information of any partition M(i,
−1, j−1), M(i, j−1), M(i+1, j
-1), M(i-1, j), M(i+1, j), M(i
-1, j+1), M(i, j+1), M(i+1, j
+1) can be propagated sequentially without any flexibility. Furthermore, when the target has a complex shape, these operations are performed using the propagation information and the information before propagation processing of the target section (x or
x') can eliminate all contradictions by repeating it until it becomes the same over the entire area.

In addition, as a publicly known example similar to the present invention, JP-A-Sho
No. 50-68039 can be mentioned. this is,
Using two binarization patterns that are binarized using different thresholds, the two binarization patterns are used to re-binary information using information from adjacent sections for different sections of information, that is, sections of intermediate density. In performing the conversion, a forward scan and a reverse scan are performed sequentially.

FIG. 3 is a diagram showing an example of the process and result of label propagation for a binary image with two objects.
First, in the forward scan, a new label (numeric value) is assigned to the section M (i, j) where the information x is the object and the adjacent information a, b, c, and d are all background. Information a, b, c,
If d contains an object, the smallest label already attached is propagated. Next, in the reverse scan, the labels of each section already attached by the above scan are checked, and the smallest label among the neighboring information a', b', c', and d' is propagated. By this operation, the minimum value of the label given by the scan is propagated to the entire area of the object, and each object is given a different label, making it possible to distinguish the objects.

By appropriately defining such propagation rules, it is possible to (1) detect surrounding objects, (2) detect holes in objects, and (3) label objects. In other words, assuming that the binarized pattern is an object and a background, (1) Detection of incomplete (peripheral) objects Information on the "edge" of the processing range is used to detect "objects" that are in contact with the edges. ” (object),
Incomplete objects are detected by replacing the desired "object" with an "edge." In other words, scan x=edge Either d′ is an edge: Other cases (2) Hole detection in the object The information on the “edge” of the processing range is successively propagated to the “background” that is in contact with the edge, and the true “background” is detected. ” (back) is replaced with “edge”, and the part “hole” that remains as the “background” (back)
(hole). In other words, scan x = edge x: x = back and one of a, b, c, d is edge: otherwise scan x' = edge ′ is edge: Other cases (3) Labeling of object Scan x = New.label Min (a, b, c, d) x: x = object and a = b = c = d = back: x = object and one of a, b, c, d is label : x = back Scan x' = Min (a', b', c', d') x': x' = label : x' = back Here, labels are attached in ascending order.
Although it is possible to attach these labels in descending order, the above is representative here.

[Embodiments of the invention]

FIG. 4 is a diagram showing an embodiment of the present invention. The input image is converted into an electrical signal S as image information of a plurality of mesh sections by an image input device such as a photographic tube or a flying spot scanner. This electric signal S is quantized using an A/D converter 1 to obtain a digital signal S _A. this signal
S _A is supplied to the switch 2 . This switch 2 is supplied with the output signal S ₀ of the image memory 5, and the value m ₁ of the latch 21 causes the signal S _A ,
Either one of S ₀ is output. This output signal S _B
is supplied to the binarization circuit 3. Now, if the above m ₁ is set so that the above signal S _A becomes the above signal S _B , then
A signal S _A is supplied to the binarization circuit 3 .

The configuration of the binarization circuit 3 is shown in FIG. The input signal S _B is fed to a comparator 31 and compared with a threshold T set in a latch 34 . This comparator 3
The output of 1 is supplied to the gate circuit 32 or 33,
If the above signal S _B is above the threshold value T, the latch 35
The value P _U set in passes through the gate circuit 32,
If it is less than the threshold value T, the value P _L set in the latch 36 passes through the gate circuit 33. However,
The input signal S _B is converted into a value P _U and a value P _L by the binarization circuit 3.
The signal S _C is binarized into .

The signal S _C is supplied to the switch 4. This switch 4 is supplied with the signal S' ₀ from the arithmetic circuit 9, and depending on the value m ₂ of the latch 41, one of the signals S _C and S' ₀ is output. This output signal S _D is supplied to the input terminal IN of the image memory 5. Now, when the value m ₂ is set so that the signal _SC becomes the signal _SD , the memory 5 is supplied with the signal _SC , that is, a signal binarized into a value P _U and a value _PL . The image memory 5 has two-dimensional addresses corresponding to the width I and the height J of the input image, and has lower addresses.
A _L is a horizontal address i, and an upper address A _U is a vertical address j, which corresponds to the real address of the input image. Writing into the memory 5 is performed by sequentially updating the addresses A _L (horizontal address i) and A _U (vertical address) by the address control circuit 6.

The configuration of the address control circuit 6 is shown in FIG. The address control circuit is composed of two address counters 61 and 62, and the carry terminal C and borrow terminal B of the counter 61 are connected to the addition terminal CU and subtraction terminal CD of the counter 62, respectively. The output of the counter 61 is the lower address of the memory 5.
A _L , and the output of counter 62 is the upper address
It becomes A _U. To sequentially write the input signal S _D of the memory 5 to the memory 5, the value F of the latch 72 indicating the forward direction is set to "1" to open the AND gate 70, and the synchronization signal S D generated by the control circuit 10 is opened. The signal φ is supplied to the addition terminal CU of the counter 61.
The counters 61 and 62 count the number of pulses of the synchronization signal φ, and sequentially output the respective values. Thus, the signal S _D is sequentially stored in the memory 5 with the value of the counter 61 corresponding to the horizontal address i and the value of the counter 62 corresponding to the vertical address j.

According to the above explanation, the electrical signal S obtained from each section of the input image is stored in the image memory 5 at the above value.
It is stored as a binary image of P _U and P _L.

Next, the stored contents (binary image) of the memory 5 are read out in the forward direction and forward processing is performed. This reading is performed by the address control circuit 6 shown in FIG. That is, in FIG.
2 opens the AND gate 70 and outputs the synchronizing signal φ
is supplied to the addition terminal CU of the counter 61 to sequentially increase the values i and j of the counters 61 and 62, thereby sequentially updating the address of the image memory 5, and inputting each section M(i, j) Read out the memory contents S ₀ (i, j) sequentially. Further, the value i of the counter 61 is supplied to comparators 63 and 64. The comparator 63 uses the above value i and the value of the latch 75.
When i≧ _IL , a signal is supplied from the comparator 63 to _the AND gate 67. The comparator 64 compares the value i with the value I _U of the latch 76 , and if i≦I _U , a signal is supplied from the comparator 64 to the AND gate 67 . On the other hand, the value j of the counter 62 is supplied to comparators 65 and 66. The comparator 65 uses the above value j and the value J _L of the latch 77.
When j≧J _L , a signal is supplied from the comparator 65 to the AND gate 68. Comparator 6
In step 6, compare the above value j and the value J _U of latch 78,
When j≦J _U , the signal from this comparator 66 is
Supplied to AND gate 68. The outputs of the AND gates 67 and 68 are supplied to an AND gate 69. Here, the above values I _L , I _U , J _L , and J _U are used to set the effective range of the width I and height J of the image, where the value I _L is the lower limit of the width I, and the value L _U is the width. The upper limit of I,
The value J _L indicates the lower limit of the vertical width J, and the value J _U indicates the upper limit of the vertical width J. With this configuration, I _L ≦i≦
Only when I _U and J _L ≦j≦J _U , a signal e is output from the AND gate 69 and supplied to the arithmetic circuit 9.
Further, a value K indicating the first scan is set in the latch 74, and a signal k indicating this value is sent to the arithmetic circuit 9.
supply to.

As mentioned above, the signal S ₀ read out from the image memory 5 according to the address control circuit 6 is supplied to the switch 2 and the arithmetic register circuit 8 . Now, the signal read out by the address control circuit 6 is
Let it be a signal S ₀ (i, j) of a certain section M (i, j).

The configuration of the arithmetic register circuit 8 is shown in FIG. The register 85 receives the signal S ₀ (i, j) from the memory 5.
is supplied. In addition, the delay circuit 80 and the register 8
4 is supplied with the signal S' ₀ obtained as a result of processing one section before by the arithmetic circuit 9. The above delay circuit 8
0 is means for storing signals of (I-1) partition groups, and can be realized using a shift register, RAM, or the like. This delay circuit 80 is a common means for mask calculation in image processing. The above signal S′ ₀ is
By the delay circuit 80, it is sent to register 83 with a delay of (I-1) sections, and then to register 8 with a delay of one section.
2, it is further shifted to register 81 with a delay of one block. By having the above configuration,
The five registers 81, 82, 83, 84, and 85 have signals S' ₀ (i-1, j-1) and S' ₀ (i,
j-1), S' ₀ (i+1, j-1), S' ₀ (I-1,
j), S ₀ (i, j) are stored. Here, the above 5
The contents of the three registers 81, 82, 83, 84, and 85 correspond to the aforementioned information a, b, c, d, and x in that order. These a, b, c, d, x are sent to the control circuit 10 every time information x of each section is supplied from the memory 5.
The arithmetic circuit 9 synchronizes with the synchronization signal generated from the
supplied to

In the arithmetic circuit 9, predetermined processing is performed based on the above five pieces of information, and the signal obtained as a result of the processing is
S′ ₀ (i, j) is the calculation register 8 and switch 4
supplied to In the arithmetic register 8, the signal S' ₀ (i, j) is supplied to the register 84 and the delay circuit 80 as described above, and the signal S' ₀ (i, j) is supplied to the register 84 as described above.
(i, j) are stored. On the other hand, the signal S' ₀ (i, j) supplied to the switch 4 is applied to the input terminal IN of the image memory 5 and written into the section M (i, j). Next, the address is updated by the address control circuit 6, and the signal S ₀ (i
+1, j) is read out and subjected to the same processing as described above, and the resulting signal S' ₀ (i+1, j) is written into the image memory 5. These processes are sequentially performed for all the partitions, and the first forward process is completed.

Next, the value F of the latch 72 of the address control circuit shown in FIG. 6 is set to "0" to close the AND gate 70, and the value R of the latch 73 indicating backward scanning is set to "1". Then, the AND gate 71 is opened and the synchronizing signal φ is supplied to the subtraction terminal CD of the counter 61 to sequentially decrease the address.
At this time, the value K indicating the first scan of the latch 74 is set to another value. The same processing as the forward scanning is performed for this backward scanning.
That is, the contents of the image memory 5 are sequentially read in the reverse direction, and among the information in the calculation register 8, the registers 81,
Information a′, b′, c′, which is the content of 82, 83, 84,
d' and the information newly written to register 85
A predetermined process is performed in the arithmetic circuit 9 using x', and the result is written into the image memory 5.

Next, the configuration of the arithmetic circuit 9 is shown in FIG. Information a, b, c, and d from the arithmetic register 8 are supplied to a minimum value detection circuit 90, and the minimum value m is determined.
This minimum value m is supplied to comparators 91 and 93 and gate circuit 97. On the other hand, information x from the arithmetic register 8 is supplied to comparators 92 and 93 and a gate circuit 98. In the comparator 91, the value C ₁ of the latch 94
The relationship α ₁ of m to is determined. Comparator 92 determines the relationship α ₂ of x to the value C ₂ of latch 95. Further, the comparator 93 determines the relationship α ₃ of x to m. Gate circuits 97 and 98 are opened by gate signals β ₁ and β ₂ , respectively, and m, x
is supplied to the AND gate 100. A counter 96 counts the number of gate signals β ₃ of the gate circuit 99 and supplies its output L to the gate circuit 100 via the gate circuit 99. Further, k is a signal from the address control circuit 6 and indicates a scan state. Note that the gate circuits 97, 98 and 9
Only one of gates 9 is opened by gate signals β ₁ , β ₂ , and β ₃ and supplies one of m, x, and E, x ^* , to the gate circuit 100 . This gate circuit 100 is supplied with a signal e from the address control circuit 6. Further, the above e is connected to the gate circuit 1 through the inverter 102.
01. This gate circuit 101 is supplied with a signal from a latch 103 having a value P _E indicating an invalid region. Therefore, either x ^* or P _E is outputted from x ^* depending on the presence or absence of the signal e. This output signal S' ₀ is supplied to the arithmetic register 8 and the image memory 5 via the switch 4 as described above. Note that this arithmetic circuit has initial values (object, back, hole, edge, C ₁ , C ₂ ) as shown in FIG. 9 depending on the target processing.
This is executed by setting the gate signals (β ₁ , β ₂ , β ₃ ) according to the conditions (k, α ₁ , α ₂ , α ₃ ).

FIG. 9 is a diagram illustrating initial values, conditions, and gate signals of the target processing.

First, detection of an incomplete object adjacent to the periphery, that is, a peripheral object Q will be described. Slice the signal S from the input image with an appropriate threshold T,
It is binarized into P _U =“2” and P _L =“1” and stored in the image memory 5. Here, "2" is (object),
“1” corresponds to (hole) and (back). Next, I _L , I _U , J _L and J _U are respectively "2" and "I-
1", "2", and "J-1", and set the effective range of the image to the inside of one section. Then, for the non-effective area by setting P _E = "0", the arithmetic circuit 9 sends S' Output "0" as ₀ and set it as (edge). Also, for the effective area, C ₁ = "0", that is, (edge), C ₂ =
As “2” (object), three relationships α ₁ , α ₂ ,
α ₃ is determined, and x ^* is determined in the arithmetic circuit 9 according to the conditions and outputs shown in FIG. For example, when the minimum value m of a, b, c, d is "0" (edge) and x is "2" (object), the gate circuit 97 is opened by the gate signal β ₁ , and ^x It outputs "0", ie (edge), opens the gate circuit 100 with the signal e, and outputs x ^* , ie "0" to _S'0 . In this way, by scanning in the forward and reverse directions under the conditions shown in FIG. 9, the peripheral object Q becomes "0", that is, an edge. This results in “2”
(object), “1” (back) and (hole), “0”
(edge) ternary image is obtained.

Next, detection of the hole H in the object will be explained. For example, the above ternary image is read out from the image memory 5 and passed through the switch 2 to the binarization circuit 3.
supply to. In this binarization circuit 3, threshold value T=
It is binarized into P _U = "2" and P _L = "1" as "2" and stored in the image memory 5. Here, "2" corresponds to (object), and "1" corresponds to (back) and (hole). The contents of the image memory 5 are sequentially read out in the forward and reverse directions, and the same processing as that for detecting the peripheral object described above is performed. This process follows the hole detection process shown in FIG. The only difference from peripheral object processing is the condition of _C1 . With this process,
(object) is “2”, (hole) is “1”, and (back) is “0”.

Next, labeling of objects will be explained.
For example, the ternary image obtained in the hole detection process described above is read out from the image memory 5 and supplied to the binarization circuit 3 via the switch 2. This binarization circuit 3
Then, assuming the threshold T = “1”, P _U = “254” and P _L =
It is binarized into "255" and stored in the image memory 5.
Here, “254” is (object) and “255” is (back)
corresponds to

Note that these values "254" and "255" are values when the depth direction of the image memory 5 is set to 8 bits.
The contents of the memory 5 are sequentially read out in forward and reverse directions and processed. In other words, for the ineffective area (edge), set P _E = “255” (back)
Write. On the other hand, for the effective area, C ₁
= "255" or (back), C ₂ = "254" or (object), and the arithmetic circuit 9 calculates x ^* according to the conditions and outputs shown in FIG. At this time, k is set to "0" for the first forward scan, and k is set to "1" for the other scans. For example, if k=“0”,
Minimum value m = “255” (back) and x = “254”
That is, in the case of the condition (object), the gate signal β ₃ is added to the counter 96, and the gate circuit 99
and output the value of the counter 96 as x ^* . Through this process, different values (labels) are written for different objects.

Note that switching between the three types of processing described above can be done by setting one of the three types of processing shown in Fig. 9 to the flag (Fig. 4,
MD). The opening/closing of the output gate for each condition in each processing mode is performed using each process and condition in Figure 9 as an address, and the contents of the corresponding outputs β ₁ , β ₂ , β ₃ as output signals.
This can be easily done using ROM. Further, each initial value can be easily set using a computer or the like.

〔Effect of the invention〕

As described above, the apparatus according to the present invention can be used to detect incomplete objects adjacent to the edges of the processing area, to detect holes in the objects, and to label separated objects using only raster scanning. This can be done simply and efficiently using

[Brief explanation of the drawing]

Figure 1 shows an example of a binarization pattern, Figure 2 shows an example of a binarization pattern.
The figures are diagrams for explaining the principle of sequential propagation according to the present invention, Figure 3 is a diagram showing an example of label propagation, and Figure 4 is a diagram for explaining the principle of sequential propagation according to the present invention.
5 shows details of the binarization circuit shown in FIG. 4, FIG. 6 shows details of the address control circuit shown in FIG. 4, and FIG. The figure shows the details of the arithmetic register circuit in Fig. 4, Fig. 8 shows the details of the arithmetic circuit in Fig. 4, and Fig. 9 explains the initial values, conditions, and output gates of the target processing. It is a diagram.

Claims (1)

[Claims] 1. In a device that processes an image by dividing it into a finite number of mesh-like sections, the density signal obtained from each section is converted into a signal Pu of a section recognized to be an object.
means for storing in an image memory as a binarized pattern divided into signals _Pu and P _L of other sections, and means for sequentially reading out the image memory in the forward direction, a first process of propagating the label forward in the pattern by determining and writing a label using information of adjacent compartments that has already been read for the compartment;
The above image memory is sequentially read in the reverse direction, and when a label has been attached to the read out section, a new label is obtained from the label information of the adjacent section that has already been read out, and is written to the concerned section, thereby creating the label. An image processing device characterized by comprising a control/arithmetic means for performing a second process of propagating a label in a backward direction within a pattern by determining the label and writing it in the section. 2 The above control/calculation means sequentially increases the value each time the information of the section read in the first process is Pu and the adjacent section that has already been read is not labeled. with a label that
Furthermore, the propagation of the label in the first and second processing is performed by writing a label with a minimum value among the labels of the partitions that have already been read into the partition concerned. The image processing device described. 3. The image processing device according to claim 1, wherein the control/calculation means repeats the first and second processing until the information in each binarization pattern becomes the same. . 4. The control/calculation means attaches a specific label indicating the edge when the section read out at the edge of the image is Pu, and the section read out at the edge other than the edge of the image is Pu. A patent characterized in that, when the specific label is attached to any of the adjoining sections that have already been read out, an incomplete object pattern is detected by attaching the specific label to the section as well. An image processing device according to claim 1. 5 The above control/calculation means attaches a specific label indicating the edge when the section read out at the edge of the image is P _L , and attaches a specific label indicating the edge when the section read out at the edge of the image is P _L. If the above-mentioned specific label is attached to any of the adjoining sections that have already been read out, by attaching the above-mentioned specific label to that section as well, the background to the object pattern and the information within the object pattern can be distinguished. The image processing device according to claim 1, wherein the image processing device distinguishes between holes.