JPS607579A - Method and device for picture processing - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed description of the invention]

(7) Techniques The capital invention relates to an image processing method for extracting lines as chain codes from a binary image that should represent famous lines. The image to be processed by the present invention is a spatially discretized binary image in which lines are formed. Specifically, (1) A binary image obtained by photographing line drawings such as drawings with a television camera, etc. (2) A line drawing (binary image) obtained by performing various processing on an image (not a binary image) taken by a visual device such as an automated machine or a robot or a medical machine. It targets a wide range of binary images, such as A binary image means that it takes either white or black values. There are no intermediate (gray) shades. Discretization means dividing space into finite unit spaces,
In a unit space, a variable takes a single value. Here, the two-dimensional plane is further divided by vertical and horizontal straight lines. One unit of pixel is a small square or rectangle.
The vertical and horizontal dimensions are often the same. (b) When trying to have a drawing machine read line drawings such as explanatory drawings of the prior art and make some kind of judgment, the drawing is photographed with a television camera, etc., and it is binarized based on brightness and space. It is often input as a binary digital image that has been discretized. Further, in order to perform image processing in automated machines, robots, visual devices, medical equipment, etc., it is necessary to convert the image into a discretized binary digital image. "Object G" is not a line drawing, but a multi-gradation grayscale image or a color image is a binary line drawing. The line drawing obtained in this way is nothing more than a list of values of individual points (pixels). The thickness of the lines is not constant, and the direction of the lines is not known. Lines are not understood as a series of ordered points. Complex judgments cannot be made directly from this image. It is necessary to group each pixel and understand its order, line, position, direction, shape, length, mutual connection relationship, etc. This is called chain encoding. A chain code is a system in which the pixels that make up a line are traced one after another, starting from the end point, from one pixel to the next pixel adjacent to it (this is called tracing), and from one pixel at this time to the next pixel. The direction of movement to the pixel is arranged in order with signs and closing. For example, as shown in FIG. 1(a), from a certain pixel,
The movement directions of the eight adjacent pixels -2 are represented by codes from 0 to 7. Then, the chain code of the polygonal line in (b) becomes 767007565. Conventionally, the following two methods have been used to obtain chain codes. (1) Directly trace the given line drawing. (2) Perform line thinning processing on the given line drawing, and then perform tracking. In the case of (1), that is, the direct tracking method, one or several points on the line are given, and this is used as the starting point and the first few steps, and surrounding pixels are examined without considering the past direction of travel. Then, decide the next direction of travel. If the lines in a given image are thick, there is a possibility that the line will be shifted or lost within the width of the line. To prevent this, survey the surrounding area over a sufficiently large area and plan ahead several steps ahead.
Control the direction of travel by doing things such as u. This requires complex processing and refers to many pixels in an irregular order, which takes too much time both in terms of processing and storage. If the lines in the line image are sufficiently thin, these drawbacks can be significantly reduced. However, the original image is diverse and is not necessarily composed of thin lines. 47 (In fact, complex processing is still required to obtain the desired result. To avoid such problems, method (2) is used. There are various specific methods for thinning the wire. This is well known and will not be discussed here. In method (2), if line thinning is completely performed, the line connection relationships of the original line drawing will be preserved, and only the pixels necessary for this will be left. and other objects are removed from the line.As a result, only a relatively narrow range needs to be examined during tracking, which reduces the time loss associated with the tracking process.However, it is still possible to There are multiple possible directions in the vicinity, so it is necessary to appropriately decide which of these directions to choose or whether to branch at that pixel. This may create unnecessary loops as shown in Figure (a), or the connection relationships between lines may not be preserved as shown in Figures (b) and (C). , it is necessary to check a rather wide range, check whether each surrounding pixel has already been tracked, and if so, whether or not branching has been performed. In addition, whether it is directly tracked or tracked after JILI!, the method of determining the traveling direction during tracking is processing or multiple Mf (. Also, since it is necessary to check the surrounding pixels, Since many pixels are read out from memory in an irregular order, it is difficult to increase the speed. By thinning this, the patterns that can exist around the branch point are limited, and (2) without tracking, the connection of each pixel is determined individually only from surrounding information, and memory readout is regular. good)
, (3) The purpose is to quickly obtain a chain 't] that is free from unnecessary minute loops and that accurately reflects the connection relationships of the lines. The present invention relates to an image processing method for extracting chain codes from a binary image containing lines. The difference from the conventional method is that
This means that the line connections are determined without tracing. The image to be subjected to this processing is called a human image. The input image has two types of values (for example, bright and dark, white and black)
Pixels having one of these are arranged in a grid pattern. Since the pixels are arranged in a grid, they have already been discretized. The binarization process has also been completed. We start with this as the input image. A pixel having one of the two values is part of the line, and a pixel having the other value is part of the ground. In the following description, the value of a pixel belonging to a line is assumed to be "1", and the value of a pixel belonging to a ground is "0". One pixel has eight neighboring pixels. The four directions along the grid are called "top", "bottom", "left", and "right".
A direction having an angle of 45 degrees with these will be called "oblique". As shown in FIG. 4, the eight neighboring (adjacent) pixels of the pixel Po are Pl, P2, . . . counterclockwise from the right of the pixel Po.
...Set as P8. The value of pixel Pi is written as X engineering. With respect to Po, four pixels Pl, P3, P5, and P7, that is, adjacent pixels having odd subscripts, are located on the right, above, left, and below, and these are called four neighbors. The 8-neighborhood includes all of P1 to P8. The relationship between pixels and pixel B will be defined. If pixel A is near 4 (or 8) of pixel B, pixel B is 4 (or 8) near pixel B.
or 8) nearby. It is said that pixel person and B are 4 adjacent (or 8 adjacent). Also, regarding two pixels A and B having the same value, pixel A
Starting from pixel A, move to 4 adjacent (or 8 instantaneous contact) pixels that have the same value as pixel A, and repeat this one after another to move to pixel B.
When this can be achieved, pixels A and B are said to be 4-connected (or 8-connected). In other words, in a 4-connection, only pixels on the top, bottom, left and right sides are connected, and in an 8-connection, diagonal pixels are also considered to be connected. If an 8-connection (4-connection) concept is used for pixels with a value of 1, a 4-connection (8-connection) concept is used for pixels with a value of 0. This is because an area with a value of 0 surrounded by a connected area with a value of 1 should be considered to be separate from the outside (not connected). The value of pixel Pi is sometimes written as Xi, but to indicate that it is a characteristic function of pixel Pi, the value of Pi is written as a function f(Pi
) may not be expressed. f (Pi)=Xl(1), which is either 0, 1, or a binary value. Next, the number of connections, (4)1. Define (8). The former is called the number of connections when four connections are taken, and is defined as follows. (8) Number of connections N when 8 connections are taken. is defined by. This is pixel P. This value indicates how many areas are connected. X indicates negation of n. x = l - x. Since the number of 8 connections is more important, this will be briefly explained. (8) Number of connections N. is a certain pixel P. (XO=1) and the 8-neighborhood (
Among the pixels in Pl, P8), indicate how many pixels are Xj-1 and are separated from each other. (2j-1) 4 indicates an odd number. 2j-1' becomes 1 when there are odd-numbered neighbors, that is, 4 neighbors (top, bottom, left, and right) or O. If n of the 4 neighbors, that is, top, bottom, left, and right pixels, have the value O, then ΣX, is n However, the number of connections J-1 cannot be said to be n. Even if Xl-1, X3-1, the diagonal pixel X2 sandwiched by these is P2, P3, all O, X
・There is no pixel where = 1 exists here. Since there is no pixel separated by Xj-1, xi=:'l (that is, Xl-〇) does not result in newly connected pixels. However, if name = 1, ma, -1 and X2-1, then P2 and P. A connection is created between the two. In this way, x, = 0, X, = 0 and 2 lines 1
2j+1 also, if x, -1, the number of connections increases by one, and X, 202]
The number of connections from 2 units does not increase. Therefore, the second term Σx in equation (3),
Subtract x, x, from :2-x, which is 02
J-12323+1 23 The configuration of the present invention consists of the following four processes. (1) Hole filling process Holes of size 1 that exist in the input image are filled. (2) Thinning process Remove unnecessary pixels from a wide line, leaving only the minimum necessary pixels. The connectivity of the area with value 1 (8 connections) and the connectivity of the area with value 0 (4 connections) are preserved, and a single boundary point of the area with value 1 has only one pixel with value 1 adjacent to it. Make sure not to. (3) Connection determination process Each pixel is connected to adjacent pixels. A total of 9 bits of information is determined and stored, including the values of the 8 pixels surrounding the pixel and which of the 4 pixels at the diagonal position is the blockage point. (4) Tracing process Based on this result, trace the line to obtain a chain code. The four processes will be explained individually below. @-) Hole filling process This is a very simple process. A pixel of value O surrounded by pixels of value 1 on all sides,
Change the value to 1. This is a hole filling process. Figure 3 t'a) shows the necessary arrangement for hole filling processing. The center pixel O is surrounded by 1 pixels on the top, bottom, left and right. The value of the diagonal pixel (marked with an x) may be 0 or 1. At this time, change 0 to 1 and eliminate the hole. In other words, when Xo-0 is X, X3 X5 If it is 0, a loop will occur here. However, this loop may contain one pixel. Since such a small loop should not exist in an actual image, it can be determined that it is meaningless. The reason why it became Xo or 0 is considered to be due to the influence of some kind of noise. So I made an X to fill the hole in the center. =1. In this way, it is possible to prevent the occurrence of minute loops (with a size of 1) and, as a result, to limit the number of patterns generated at the branch portion. FIG. 3(a) shows the arrangement before the hole filling process, and FIG. 3(b) shows the arrangement after the hole filling process. (Strength) Line thinning process Removes unnecessary pixels from wide lines to minimize i
! ! This is a process that leaves only the iI element. As already mentioned, a known image processing method is one in which connections of pixels are traced after line thinning processing. There are several known methods for thinning the line.Thinning is a necessary process when carrying out the present invention, and there is no problem in using a known method for thinning the line.Thin line The general conditions required for the conversion process are as follows: (1) Leave the central part of the liIili wide line to prevent significant deformation or positional shift. (2) Preserve the connection relationship. ( 3) Minimize line length reduction. To meet this requirement, an off-site line thinning method is known. This method consists of sequential processing in raster scanning order, and is easy to implement. It is also efficient. The properties of the resulting thin line drawing are clear. An off-site method will be explained. The number of connections of 8 connections shown in equation (3) is used. For simplicity, the subscript (8) is used. The definition is the same, and regarding Po, it is written as No.Furthermore, the number of pixels N and G in the 8 neighborhood with the value 1 is defined as follows: Na(Pa)−1ΣX, (5) -11 Na is simply called the number of neighbors, and No is called the number of connections.The distinction between Na and N is extremely important.Since Na is from O to 8, it is an integer less than or equal to 4.8 neighbors To separate rings of pixels from each other, at least one pixel with value 0 (Xj = 0) is required per cut. = 1) is 8. Therefore, the number of connections must be 4 or less. (Variable P is omitted for simplicity) O≦Na≦8 (5) 0≦Ima.≦4 (6) Furthermore , a group of separated pixels with a value of 1 always includes one or more pixels with a value of 1, so Town ≧ No(7
). There are N separated pixels of value 1, but at least one pixel of X-0 is required for separation. Therefore, if there are at least N pixels of X=0, I(6 connections will not occur. If there are N0 or more pixels of
The pixels where X≦1 are (8-No) or less. That is, Na≦8−No(8). No. is called the number of connections, and is the number of groups of pixels with a value of 1 that are separated by removing that pixel. However, whether it is connected or not is determined depending on whether it is connected or not, so it depends on whether you are thinking of 8-connection or 4-connection. Furthermore, if a hole is created by removing that pixel, the number of connections is obtained by subtracting the number of holes. In reality, there can only be one hole, and creating a hole means that the pixel is surrounded by connected pixels with a value of 1, so the number of groups with a value of 1 can only be 1. . Therefore, when holes are formed, No is 0. Conversely, No-0 means that there is no pixel with a value of 1 in the vicinity (an isolated point), or that a hole is created by removing that pixel. Isolated points do not contribute to the line and are therefore not processed. here 8
Since they are connected, in order to have a hole (in other words, to be surrounded by connected pixels with a value of 1), at least
It is necessary that the four pixels on the two bottom left and right sides have the value I. Therefore, for N, -〇(P≦1), the pattern of Na≧4(9) may be targeted. The above equations (5)' to (9) represent Na and N. This is either a limitation caused by the definition of , or another limitation is added by the thinning process. This will be explained next. The thinning process outside the premises is performed by repeatedly performing the following three partial processes. (1) Classify pixels having a value of 1 (xo=i) into the following three types. A-[PolX3°X5=01 B=(po (x3, X5==l and X7.Xl
≦0 ) C other (x3x5x7x1=l ) (11
) Starting from the top left of the screen, first move to the right, and when you reach the right edge,
Next row, in order from left to right, PoEA and N
. Pixel P where (Po)=1 and Na(Po)+1. Change the value of to 0. Do this until you reach the bottom right corner of the screen. (In the reverse order of song (11), proceed from the bottom right corner of the screen to the left, and when there is excess on the left edge, go one line up from the right edge to the left edge, and then 2 more lines.) From the second right edge to the left edge... ) PoEB and N. (Po) = 1 and f om (Po) * t pixel P. value is 0.
will be changed to. Do this until you reach the top left corner of the screen. The above processes (I) to (it) are repeated until there are no more pixels whose values are changed in (II) and li). In this way, thinning is achieved. First, in the process (1), the pixel C is surrounded by pixels having a value of 1 on the left, right, top and bottom (If.-0). This is an internal point, and removing it will create a hole, so it is temporarily removed until it appears on the boundary in the following process. In A and B, either the top, bottom, left or right pixels have a value of 0. Among these, if the number of connections is 1 and the number of neighbors is 1 or more, this pixel and a neighboring pixel with a value of 1 form a group. Even if this pixel is excluded (even if the value is set to 0), the connection relationship between neighboring pixels is preserved. Therefore, in order to make the wire thinner, NC”
" 1, Na 'P L is changed to O. No. 1, Na = 1 is left as it is an end point. The reason why the processing order is different for A and B is because of the thinning process. This is to reduce the bias.Even if there are pixels that are equivalent (belonging to groups A and B, No.=1, Na41.), those that are processed first are likely to be removed, and those that are processed later are (Because the surrounding pixels with a value of 1 have already decreased), the number of G is removed. Therefore, outside the premises, the processing order is reversed for groups A and B. However, due to the difference in order, the value of 1 is There is no big difference in the pixels changed from 0 to 0.As a simple method, for both groups A and B, move from the top left of the screen to the right at the same time, and the next row also from left to right. In fact, the inventor believes that a simpler algorithm is more convenient because it reduces scanning errors.The partial processing is as follows: (1) Value Divide the pixel with 1 (XO=1) into the following two types: A-I Pol X3X5X7Xl = 0, )
C=! Po 1X3X5x7X1" 1 ] (11
) From the top left of the screen, first move to the right, then move the next line from the left to the right, and so on.
EA and Nc(Po)”-t and Na(Po)4
1 pixel P. Change the value of (continue) to 0 until you reach the bottom right corner of the screen. Repeat the partial processing of (1) and (11) in (11) until there are no more pixels whose values will be changed. Figure 11 shows an example of line thinning processing. (a) is a binary image before processing, and (b) is an image after line thinning processing using a simplified algorithm. In (a), Width is 21Jl
! What used to be I elements or 3 pixels are now all thin lines with a width of 1 pixel. (G) Connection determination processing (general principles) The core of the present invention is the connection determination processing. Pixels in a connected relationship are tracked and connections are determined by the arrangement of pixels in a 3×3 local area (Po to P8), which is significantly different from the conventional method. This processing is performed based on the following two properties of the image remaining as a result of hole filling and thinning processing. K property quality II value 0 is N. A point of −0 means that all neighboring pixels have a value of 0 (Na=0
). K property quality 2 blade value 1teN. The −1 point is always an end point (t'Ta = 1). Property 1 becomes like this because the hole filling process was performed. No
:0 means that either Pl, P3, P5, and P7 all have a value of 1, or all of the eight neighboring pixels P1 to P8 have a value of 0. The former case is impossible due to hole filling. Therefore, the value OteN. If it is -0, all neighboring pixels are 0. This is the "earth" part. Property 2 is due to the thinning process. For thinning, value 1 and No=1
, all points with Na=+1 were removed. With a value of 1, N0=1 and the only thing left is 1IJa-=i. Since only one of the neighboring pixels has the value 1, this is an end point. The remaining pixels with value 1 are as follows. (1) All of No=2.3.4 (2) N. −
1, I (a-1 (endpoint) (3) All the lines with No=o were thinned by removing all the lines with No=1 and NaN3, so the lines with N=0.2 and 3.4 remain. Several combinations are allowed for No1Na.As mentioned above, the inequalities (5), (6) to (9) must be satisfied, so the combinations of No, I(a) are limited. Isolated points (l- = o, Po = 1) are not initiated (even if they exist, they are ignored because they are not involved in the connection).
Therefore, Na1=Q is also omitted. FIG. 12 is a table showing impermissible combinations of Na and No. Prohibited combinations are indicated by diagonal lines. N laterally. The value of Na is taken in the vertical direction. The two columns on the right side are prohibited due to formula 7). The lower right column is prohibited because it is formula (8), and the top three columns on the left are prohibited because it is formula (9). The bottom 7 columns of No. 1 have been removed to make the lines thinner. The remaining combinations are Na=415+6,718I ma for N=Q.
For -1 ■Chi=1 N For -2 Na=2.8,4,5.6N =3
About 1? For a=3,4,5N=4
Na=4. Let's actually draw a 3x3 pixel pattern for these combinations. Po is the central pixel (value 1) and is indicated by a white circle, and other neighboring pixels (value 1) are indicated by black circles. Areas without circles have a value of 0. FIG. 13 shows specific pixel patterns for such permissible combinations, and No is used as the main classification. N laterally. The value of I is shown from top to bottom. One column is a 3×3 (PoN P8) pattern, and only one pattern that matches due to changes due to rotation or mirror image is shown as a representative. If the value is No or Na is increased by one, it is sufficient that the even numbered pixels (P2, P4, P6, P8) change from the value 0 to 1. Items with this kind of relationship are indicated by arrows pointing from top to bottom. In Figure 5, the number of neighbors Xqa is used for main classification, and the number of connections is N. The patterns are organized using the following for classification. The contents are the same as FIG. 13. In this way, there are only 32 types of patterns that can remain after the thinning process. Furthermore, the three patterns numbered α, β, and γ in the figures (FIGS. 5 and 13) cannot exist. When determining the values of surrounding pixels, a diagonal pixel (P2 P4 P6 P8) with a value of 0 will be surrounded by four pixels with a value of 1, so that the number 20 becomes P21, N ,
Since it becomes 0, it goes against Property 1. The pattern of α will be explained with reference to FIG. Instead of black circles and white circles, write 11. Figure 14(a) or α
This is the starting point pattern. P to the left of Pl. , below as P8 or X-1. In order for Pl not to be erased during line thinning, there must be a pixel with a value of 1 to the diagonal upper right of Pl. Otherwise N
. This is because it becomes -1, Na 4 t and is erased. Similarly, there must be a pixel with a value of 1 at the upper right corner of P3. Then, a peripheral pattern like the one shown in FIG. 14 must exist. In this case, the pixel of X2-〇 is N. = 0 and N is 40, that is, a hole remains. The holes have disappeared due to the hole filling process,
This is impossible because holes are not generated due to the 4111m extension. In other words, pattern α is a pattern that is not dried. β will be explained with reference to FIG. (a) is the starting pattern, black circles and white circles are represented by 1, and areas without circles are represented by 0. Similarly, in order for the pixels of Xi ``'' 1 and X3 = 1 to not disappear, there must be a pixel with a value of 1 diagonally to the upper right of each, and the distribution of surrounding pixels will be as shown in ('b). Then, X2=0 becomes a hole. Since no holes should occur, it turns out that the β pattern is not allowed after all. r is shown in FIGS. 16(a) and (b). The γ pattern is also not allowed for the same reason. Among the possible patterns of 32 Yufu, 3 are 5'1
Since the pattern is extinct, only 29 patterns remain. Among the 29 types of patterns, there are also a, b, and c. The six patterns d, e, and f are special. In the patterns a to r, four pixels with a value of 1 form a minute square. It is difficult to determine the connection of something like this. This will be discussed later. Connections can be easily determined for the remaining 23 patterns. The connection determination process is as follows.

[Conditions: January 11, 2019 There must be no contradiction in Mutsuma's decisions. In other words, if pixel A and pixel B are connected in a 3x3 pattern centered on pixel A, then a 3x3 pattern centered on pixel B is connected.
Even in the three patterns, pixel B must be connected to the pixel. K Condition 2) 1 The connection relationship must be preserved. That is, any two pixels belonging to one connected region with a value of 1 must be directly or indirectly connected to each other. K Condition 3) 1 No unnecessary loops should occur. That is, if the connections form a loop, there must be a hole (a region with a value of 0) inside the loop. In order to satisfy these three conditions, the following two principles can be established for the 23 types of patterns. Ikkou & Principle - ■Principle 1 Be sure to connect to the top, bottom, left and right pixels (value 1). K principle A pixel (value 1) located diagonally at position 1a is connected only when two pixels adjacent to that pixel among the four pixels on the top, bottom, left and right of the center pixel are both 0. Principle 1.2 is the center pixel P. It states that when connecting a pixel with a neighboring pixel having a value of 1, priority is given to the four neighboring pixels on the top, bottom, left and right. If there are 4 neighbors, the center pixel has 4 neighbors (
pl, p, , p5, p7). The diagonal pixel is connected to these four neighboring pixels by lines in the vertical and horizontal directions. In other words, Po is connected to Pl, and P is connected to P2. When there are four neighbors, the diagonal pixels and the center pixel are indirectly connected. When the 4-neighborhood is 0, diagonal pixels are directly connected to Po by a diagonal line. The reason why the four neighboring pixels on the upper, lower, left and right sides have priority over the four diagonal pixels is due to the necessity of satisfying condition 2. A diagonal connection can be constructed by combining two connections, top, bottom, left and right. However, the vertical and horizontal connections cannot be reconfigured no matter how many diagonal connections are combined. FIG. 6 shows connections determined by applying Principle 1.2 to 23 types of patterns. 3×3 like this
By considering only within the unit pattern, the central pixel P. The connection between the pixel and the neighboring pixel can be determined. In FIG. 6, connections between the central pixel (represented by a white circle) and neighboring pixels are shown by line segments. Connections between neighboring pixels are 3
After moving the center of the ×3 unit pattern to that pixel, it is considered and determined. Neighboring pixels that are not connected to the center pixel are not isolated points, but are connected to other nearby pixels that are connected to the center pixel. (shio) Connection determination processing (example outside) The six patterns a to f appearing in FIGS. 5 and 13 have small squares with a value of 1 (all 2×2 patterns have a value of 1). Applying principle 1.2 of the previous section to such a pattern will result in small square loops without holes. This cannot satisfy condition 3. Therefore, it is necessary to create an exception outer side for the pattern a-f. The 2×2 pattern, in which all values are 1, is only a part of the five patterns P1, P2, . . . , P5 shown in FIG. Only five patterns can remain after thinning. This is tentatively called a dense pattern. Pattern P1 will be explained. The upper right one of the four pixels with a value of 1 in 2×2 is set to 50. 51 to the right of pixel 50,
Let the upper right be 52 and the top be 53. 50 pixels due to thinning
In order for this not to disappear, there must be a pixel with a value of 1 or 9. If there is no pixel (value 1) in 51-53, pixel 50 is N
. -1, Na, and +1, so it should have disappeared by thinning. If there is a pixel with value 1 at 52 on the diagonal upper side, pixel 50 is N. Since =2, N, and 4=1, the pixel 5° can survive even after thinning. What if there is a pixel with value 1 in 51? If 52.53 is the value 0, then the pixel 50 is N. -1, Naki 1, so it disappears when the line is thinned. 51 and 53 have the value 1,
What if 52 is the value 0? In this case, since No=0, it will not disappear by thinning. What if all of 51, 52, and 53 have the value 1? In this case, in order for pixel 53 to survive, 59 on the diagonal upper left must have a value of 1. If so, 54 to the left of pixel 53
becomes a hole. This is denied because there is no way that holes would be created by thinning the wire. In the end, in order for pixel 50 to survive after thinning, 52 (
There are pixels with a value of 1 on the diagonal), or there are pixels with a value of 1 on the right 51 and top 53. In other words, the picture. For the three neighborhoods of prime 50, I (51, 52, 53) = (0, ■, 0) ■ (51
, 52, 53)=(, 1, 0, 1), the pixel 5o can exist even after thinning. Although pixel 50 is considered here as the upper right corner of a 2×2 square, the same is true for the other three pixels. Pattern P1 is four 2x21! i! In order to keep the I element alive, all four corner connections are made using TIFL. No.=2. Pattern P2 employs arrangement I for three and arrangement ■ for one. The three pixels survive although they are NO-2. Leave ■i8! ! The l element is N. It survives because it is -0. Pattern P3 adopts arrangement 1 (Nc = 2) for the two diagonal patterns among the 2×2 patterns with value 1, and arrangement II (N020) for the remaining two. . For pixels with a value of 1 in 2×2, no further connection mode exists. Next, let us consider a P4 pattern in which all 2×3 small patterns have a value of 1. Since we have already considered the four corner pixels of 2×3, let us consider the survival conditions for the central pixel 60 of the triplet. 61 to the right of 60, 62 to the upper right, 63 to the top,
Let the upper left be 64 and the left be 65. If the upper three pixels 62, 63, and 64 of 60 have a value of 0, then N for pixel 60. -1, Na~1, so it should have disappeared by thinning. If 63 or the value is 1, then N0=o for pixel 6o, so 60 can survive. In the end, the pattern P4 uses the above-mentioned arrangement I for the four pixels of the 3×2 dense pattern, and uses the arrangement I for the intermediate pixels. III (62, 63, 64) = (0, 1, 0) arrangement is adopted. Regarding 61.65 at the four corners, it should be possible to adopt the above-mentioned arrangement II. This pattern is pattern P5. In other words, in P4, 63 is set to 0, and instead of 68.6264.69 to the right, above, and left of 61.65.
Let be the value 1. Even in this case, 63 must have the value 1 (otherwise 60 will disappear). Then, in order to make 62.63.64 survive,
Three more pixels with a value of 1 are required, and the pattern P5 is obtained by adding these pixels. Pattern P5 includes 3×3 pixels with a value of 1. Place ■ for the four corners, place [ for the middle pixel
(2) is applied, and by setting N-2 and No=O, respectively, it is made to survive even after thinning. P5 is the largest dense pattern. There are no larger dense patterns.゛3×43×4 pixels with a value of 1 will not be crowded together. Assume that in P5, 71.75 is set to the value 1 to create a 3×4 pattern with the value 1. Then 70% of the neighbor 73
OrN. -], Na becomes 61 and disappears. In the end, there are only 4×4 patterns of P1 to P3, 4×5 patterns of P4, and 5×5 patterns of P5 for dense <turns in which small matrices of 2×2 or more have a value of 1. There are only five kinds of tsumari phrases. It can be seen that the six patterns a to f described above are only a part of the dense patterns 1P1 to P5. If desirable connections can be provided for the entire dense patterns P1 to P5, these partial patterns a to f
connections can be determined as part of it. You will come to a crossroads here. As mentioned in the previous section, for normal patterns (other than dense patterns), connections could be uniquely determined by looking at only 3x3 small areas. It is known that there is no dense pattern from P□ to P5. It is assumed that the desired connections of the dense pattern have already been given. The dimensions of the dense pattern are 4x4
There are sizes ranging from 5×5. One connection determination method can be stated as follows. 1. For a normal pattern, the connection is determined by looking at a 3×3 small area, and for a dense pattern, the connection is determined by looking at the entire dense pattern (4×4 to 5×5 area). ”. The present invention does not use such non-local methods. Another method is to determine the connection only from a 3x3 small area, no matter what the pattern is. By observation, we can determine the connections." The present invention adopts this local method. Therefore, it is necessary to consider more deeply the relationship between P1 to P5 and the patterns a to f. In order to create an exception for the connection a - f, let us define the following two procedures. K-move j1 1Σ Regarding the dense patterns P□ to P5 and their rotation, condition 1
-Determine the connections so that 3. At this time, the connections between pixels outside these patterns and adjacent pixels must also satisfy principle 1.2 (because condition 1 is not satisfied with the outside pixels). [Procedure 2Σ Concentrate patterns P1 to P5 into 3×3 partial patterns a to f
According to the result of step 1, the connection of center pixels a to f is determined. Among the dense patterns P1 to P5, connection 1 can be determined in advance. Since conditions 2 (preservation of connected relationships) and condition 3 (elimination of unnecessary loops) described in curve j are not satisfied, all pixels in the dense pattern must be directly or indirectly connected to avoid creating loops. . Furthermore, it is better to have a high S/J symmetry. For this purpose, it is better to concentrate the connections at one point. From this point, the connecting lines radiate out, creating no loops and creating a high level of symmetry. Based on these considerations, the connections of P1 to P5 were
Decide as shown. Pixels with a value of 1 are indicated by black circles. The connection of each pixel is represented by a line segment. Here, all rotating patterns are also expressed. Po and P5 have 4-fold symmetry, so only one is drawn. At P, four lines are concentrated at one point. There are no loops and mirror symmetry is maintained. There are other connections that do not have a loop and have two-fold symmetry, but the connection of Pl is determined in this way. Since P2 has no rotational symmetry, there are four rotational variations. However, all connections are the same. After P2, a double circle with a black circle surrounded by a white circle appears. This is a blockage point (N, = O) surrounded by a value of 1 on the top, bottom, left and right.
It shows. In P2, connections are concentrated at blockage points. Since P3 and P4 have two-fold symmetry, there are two rotational variations. The connections are the same. P3 has two occlusion points, which are diagonally opposite. A perpendicular bisector of the line segment connecting the occlusion points is drawn, and the connecting lines are concentrated at one pixel on this line. P4 has two occlusion points in the vertical, horizontal, and horizontal directions. P5 has five occlusion points. From the central blockage point, it connects radially to Baka. Consider which partial patterns a to f are included in patterns P1 to P5. Figure 8 or Figure 7 and Figure 5 or Figure 1
This can be investigated by comparing the three figures. Pl includes only partial pattern a. P2 includes three patterns a, b, and c. P3 includes two patterns b and e. P4 includes two patterns C-%d. P5 includes three patterns d, e, and f. The right column of FIG. 8 shows the affiliation of such patterns. Let's think from the opposite direction. Partial pattern a is included in Pl and P2. Pl, P
Even if 2 is divided into 3×3 small regions, Pl has no blockage point, and P2 has one blockage point. Therefore, it is possible to distinguish between Pl and P2 depending on the presence or absence of a blockage point. If it is known whether it is included in the partial pattern a, Pl, or P2, then it can be determined which part of the pattern P1 or P2 it is included in. Then, the connection of a can be determined by taking the predetermined connections of Pl and P2 as they are. Partial pattern b may be included in P2 and P3. P2 has one blockage point, and P3 has two blockage points. P2 and P3 are 4×
Since there are four patterns, even if this is divided into four 3x3 patterns, the occlusion point will appear in all the 3x3 patterns. Therefore, by looking at the 3×3 pattern, it is possible to know the number of blockage points and determine whether b belongs to P2 or P3. If this can be determined, P2, P3
The connection of pattern b can be determined from the connection of . Partial pattern d is included in P4 and P5. The blockage point of P4 is 2, and the blockage point of P5 is 5. However, P5 is 5×5
Since it has the dimensions, when cutting it into a 3x3 pattern,
Depending on how the cut is made, the number of occlusion points included is 3.4 or 5, which is not constant. Since it is not constant or is 3 or more, it can be distinguished from other patterns. In this way, when there is an exceptional partial pattern a to f, it is determined in which of the PINP5 this /g turn is included based on the number of pattern seven blockage points. If you know the dense connection Pl~P to which it should belong, the connection is P. It can be easily determined from the predetermined connections of ~P5. Partial processing before executing steps 1 and 2 will be described. ■Parts, E! 1jll each pixel P. It is determined whether the point is a blockage point or not. Vo ” Xo XI X3 Xs If X7 is 1'
This is the blockage point. If it is 0, there is no blockage point. K partial processing 2 swords each pixel P. , it is determined whether or not there is a blockage point at an oblique position. zo ” 3'2 + ,)'4 + '16+ '/
8 (+ means logical sum) K partial processing 3] For each pixel P, its own Z and surrounding X (zOP
The connection of that pixel is determined from the 9-bit information: FIG. 9 shows the connection of patterns a to f determined according to the above-described procedure and partial processing. Pattern S belongs to Pl or P2, and if there is a blockage point, P
It is 2. If it is Pl, the connection is determined in advance in Figure 8, so the connection (3x3 pattern) is made by this.
can be determined. If there is a blockage point, it belongs to P2, so the connection of the 3×3 portion can be determined by looking at the connection of P2 in FIG. Pl and P2 of pattern a indicate the same pixel arrangement on the upper and lower sides. However, it should be noted that the connections differ depending on the presence or absence of blockage points (black and white circles). The same is true for other patterns as well, with the same pixel arrangement on the top and bottom but only different occlusion points. It's different probably because of the blockage point. Moreover, the difference in the number of occlusion points always appears as a difference in whether pixels diagonal from the center pixel have occlusion points or not. This is important, and partial processing 2 utilizes this property. Let's look into Tsukutan b. The center pixel is the occlusion point. P2 does not have a diagonal blockage point, and P3 has a diagonal blockage point. Check out pattern C. In the case of P2, there is no diagonal blockage point. In the case of P, there is a 1%" [point diagonally. For pattern d, there can be either P4 or P5. There is no diagonal occlusion point in P4, and there are two in P5. The definition of z. Since it is a logical sum of diagonal blockage points, it becomes 2°-0 for P4 and 2°-1 for P5, which can be clearly distinguished in the same way.As for pattern f, there is only a corresponding one at the center of P5, so immediately The connection is determined. To reiterate, for the partial patterns a to f, it can be determined which one of a to f they are based on the central pixel and the values of the 8 neighbors (Xo to X8), and the presence or absence of diagonal blockage points can be determined. From 2°, P
1 to P5, and thus the connection can be established. (vi) Tracking processing Now that the hole filling, thinning, and connection determination processing has been performed, the final tracking processing is performed. The difference from tracing in conventional methods is that in the present invention, the connection has already been determined and can be traced simply by following the connection line.
That's what it means. Therefore, the tracking process is simply h4j, and there is no need to consider the arrangement of neighboring pixels in X=. The tracking process is executed by repeating the following five steps. (1) Starting from the end point or branching point, (2) Selecting one of the predetermined connection lines for that pixel and erasing it or recording that it has been used. , move to the connected pixel. (3) When moving, record the moving direction as the first code of the chain. (4) Among the connections of the pixel to which the pixel has been moved, the connection with the pixel before the movement is deleted or recorded as being used. (5) If it is an end point or a branch point, go to (1); otherwise, go to (2). It is sufficient to perform the above processing as many times as necessary. In the case of a simple loop, it is sufficient to start from any one pixel on the loop. (g) Apparatus of the present invention (sequential processing) The image processing method has been described in detail in the previous sections. Here, a device for image processing will be described. FIG. 10 is a block diagram of the image processing device. 1 is a hole filling processing circuit, 2a is a thinning classification circuit, 2b is a thinning circuit, 3 is a connection determination circuit, and 4 is a tracking circuit. 5
is the image memory, 6 is the A group memory, 7 is the 8 group memory, 8 is the connection encoding memory, 9 is the chain code memory, 10 is the control circuit, and 11 is the address! 1ilJ control circuit. (1) The binarized values of each pixel are stored in the image memory 5, read out sequentially, and provided to the hole-filling processing circuit 1. The hole-filling processing circuit 1 has an internal delay circuit so that for each pixel, the values of that pixel and 8 surrounding pixels (8 neighboring pixels) can be obtained simultaneously, and the hole-filling processing is performed using a simple processing circuit. , the result is returned to the image memory, and at the same time is given to the thinning classification circuit 2a. The thinning classification circuit 2a has a delay circuit like the hole filling processing circuit 1, and performs the above-described classification for thinning. Group A is x3°x5-0, group B is x3. x5=l and X7
It is a pixel of °Xl-0. (This is the case when using an off-site thinning method, but when using the simple algorithm, there is no need to separate groups A, B.) This result is
It is stored in the group memory 6 and the 8th group memory 7. When the above processing is performed for each pixel, the value of the pixel after the hole filling process is stored in the image memory 5. In the A group memory 6 and 8 group memory 7, each pixel is
, whether it belongs to group B or not is stored. (2) Next, sequentially read the pixel values from the image memory 5,
At the same time, information on whether each pixel exists in the A group is read from the A group memory 6 and given to the thinning circuit 2b.The thinning circuit 2b has a delay circuit and a thinning condition determination circuit. Then, the points of group A that satisfy the thinning conditions are deleted and returned to the image memory 5. (3) Reverse the order and perform the same process using the 8 group memory 1. At this time, the output of the thinning circuit 2b is given to the image memory 5, as well as the thinning classification circuit 2a and the connection determination circuit 3, to prepare for the next repetition of thinning and to determine the connection. The connection determination circuit 3 has a delay circuit, a blockage point detection circuit having the delay circuit, and a logic circuit (or ROM) that generates a code representing a connection from data from these circuits, and stores the connection code in a connection code memory 8. I'll let it happen. Further, the connection determining circuit 3 includes a thinning completion determination circuit, detects a pattern that can be further thinned, and notifies the control circuit 10 of the pattern. During the process of (3), the control circuit 10 monitors the signal from the thinning completion determination circuit, and if the thinning is not completed, after completing (3), returns to (2). Repeat thinning. On the other hand, if it is determined that 1) II slander has been completed,
Since the correct connection code has been stored in the connection code memory 8, the process proceeds to the next tracking process. (4) Read the connection code from the connection code memory 8 and provide it to the tracking circuit 4. The tracking circuit 4 includes a register that stores the previous direction of travel, a primary mask circuit that removes the connection corresponding to the previous direction of travel from the connection code, and a direction code generator that generates a code representing the next direction of travel from this result. The circuit has a secondary mask circuit which removes the connection corresponding to this direction from the connection code and provides the direction code to the chain code memory 9 and the address control circuit 11. At the same time, the connection code is corrected by two mask circuits and returned to the connection code memory 8. The address control circuit 11 changes the address of the connection code memory 8 based on the direction code, and moves the processing to the next pixel. In this way, tracking is performed and a chain code is created in the chain code memory 9. Q) Apparatus f of the present invention (Pipeline processing) In the previous section, the case where the image processing apparatus of the present invention performs simultaneous processing was explained. If pipeline processing is performed with the same configuration, there will be almost no time overhead for connection determination. In the processing up to determining the connection, reading and writing to the memory may be performed in a predetermined order, so it is possible to increase the speed of the memory. Furthermore, if a parallel processing type method is used for line thinning, processes other than tracking can be executed in parallel for each pixel, so it can be performed at extremely high speed. (The effect of There is no need to do this. Tracking is easy because the connection is determined in advance. The connection determination process is also based on the pixel values of a 3 x 3 small area and the 9-bit data, although there is a blockage point near the diagonal. The number of pixels to be read out is small. Therefore, dual-speed processing is possible. As described above, according to the present invention, a chain code that correctly reflects the continuity of a line can be created without unnecessary without creating a loop.
You can make 41 triples at high speed.

[Brief explanation of drawings]

The 11th item (a) shows an example of the definition of a chain code, 3×
3 pixel diagram. The arrow indicates the direction of movement, and the number is the chain code attached to this direction. (bJ is an image diagram showing an example of the distribution of pixels with value j and an arrow indicating the direction in which a chain code should be added. Figure 2 shows an example of excess or deficiency of connections at a branch point. (3
A meaningless little loop has been created. (The branch point that should be connected is not connected. (C) shows an example where the connection is insufficient. Figure 3 shows a 3x3 pixel diagram in which there is a hole of size l. Explain that hole filling is done.(a) is before hole filling.
■) shows after hole filling. FIG. 4 is an explanatory diagram showing the notation of the central pixel Po and the peripheral pixels P1 to P8. FIG. 5 is a diagram of 32 types of 3×3 pixel patterns remaining after thinning processing. The number of peripheral pixels (with value 1) Na is the main classification, and the number of connections is N. was used for image classification. The center pixel is a white circle, the periphery (value 1
) Pixels are indicated by black circles. FIG. 6 is a pattern diagram showing the connection side of a normal pattern that is not part of a 2×2 dense pattern. The number of peripheral pixels Na is used for main classification, and the number of connections N0 is used for image classification. The center pixel is shown as a white circle, and the peripheral (value 1) pixels are shown as black circles. The left two lines indicate end points, the middle four lines indicate continuation points, and the right two lines indicate branch points, and the number of connections from the center pixel is ■, 2.3, or 4, respectively. @7 Figure is a pixel diagram showing five possible patterns P, ~P5 of the 2×2 pixel of the Tsumari MS pattern. FIG. 8 is a connection diagram of dense patterns P1 to P5. The black and white double circles are occlusion points, and the right end of the diagram for P1 to P5 indicates partial patterns a to f that these patterns may include. FIG. 9 is a connection-side pixel diagram in which connection is to be determined based on the presence of blockage points of partial patterns a to f. FIG. 10 is a circuit configuration diagram of the image processing apparatus of the present invention. FIG. 11 is an image diagram showing an example of line thinning processing. (a) shows the pixel distribution before the thinning process, and (b) shows the pixel distribution after the thinning process. Figure 12 shows the connection @xqo and the ig prime number Na of the surrounding value I.
A diagram showing that some things are prohibited in combination with. Combinations marked with diagonal lines are prohibited. (7), (8),
e) indicates that it is prohibited by the corresponding inequality. The term "thinning" refers to what disappears through the thinning process. Figure 13 is the same as Figure 5, which is 32 that is allowed after the thinning process.
3x3 pixel Bakun diagram of types. The difference from Figure 5 is the number of connections N in the main classification. The point is that the number Na of neighboring pixels is used for image classification. The arrow indicates that the number of neighboring pixels is set to Na+1 by adding 1 to one pixel while maintaining the same number of connections. α to γ are patterns that are prohibited when considering the pixel pattern on the ILJ side. A to f are patterns that partially include a dense pattern in which all 2×2 pixels have a value of 1. FIG. 14 is a pixel layout diagram explaining that pattern α is prohibited. Pixels with a value of 1, which were indicated by black circles and white circles in FIGS. 5 and 13, are indicated by the number 1 here. The "ground" part was simply shown as a blank in Figures 5 and 13, or is shown here with the number 0. This is to emphasize the hole "0". (a) is a 3x3 small area of pattern α, (b) is a small area pixel showing that in order to maintain pattern α, 1 is required to the right of 0, and therefore hole r01 is generated. figure. FIG. 15 is a pixel layout diagram explaining that pattern β is prohibited. (a') is a 3x3 pixel diagram of β. ('b) is a pixel diagram including surrounding pixels, where hole "0" has occurred. FIG. 16 is a pixel layout diagram explaining that pattern γ is prohibited. (a) is a γ pattern diagram. ('b) is a pixel diagram including the periphery of the γ pattern. 1... Hole filling processing circuit 2a... Thinning classification circuit 2b...
・・・・・・ Thinning circuit 3 ・・・・・・・・・
Connection determination circuit 4 ...... Tracking circuit 5 ...... Image memory 6 ...... Group A memory 7 ...... B &'l memory 8...
・・・・・・ Connection code memory 9 ・・・・・・・・・
Chain memory 10... Control circuit 11-... Address control 1-1 road black circle.
(iti 1 pixel white circle)
Center pixel Po with value 1... Center pixels P1 to P8... Neighborhood I1. j! + element (la-
f...Partial patterns P1 to P5 including 2×2 pixels with a value of 1 Dense pattern D Φ °Oi − which partially includes a pattern including 2×2 pixels with a value of 1 0 0 1) -OU °C Φ →- Figure 11 (a) 439- Figure 12 Figure 14 (a). ! , (b) Procedural amendment sent) 6. Commissioner of the Japan Patent Office Kazuo Sugi 1. Indication of the case Patent application 1987-114917 2. Name of the invention Image processing method and device 3. Person making the amendment Related Patent Applicant Residence 5-15 Kitahama, Higashi-ku, Osaka Name (213) Representative President of Sumitomo Electric Industries, Ltd.
Satoshi Kawakami Department 4, Agent 537 Hitodumi Address 704 Mainichi Higashi Building, 3-15-16 Nakamichi, Higashinari-ku, Osaka Rai 06 (974) 6321 Contents of the 41Th+1 amendment to the "Detailed Description of the Invention" in the Specification After the 11th line of Akiri J, page 25, ``...Repeat until there is nothing left.'', add a new line and add the following sentence. "However, this simplified method causes problems with certain geometric patterns. For example, rectangles with an even number of pixels in width are erased by this simplified method. Therefore, it is guaranteed that such patterns do not exist. 1 above only if
The Hj strategy is effective, and more generally the exact algorithm described above should be used. ”A

Claims (6)

[Claims] (1) Digital binary value that represents a line consisting of a set of many pixels that are discretized in the vertical and horizontal directions and have a value of either 1 or 0 [■ Image processing method that extracts lines from an image as chain codes] In this case, there is a hole-filling process that fills a hole of size 1 pixel that exists in the image and is surrounded by pixels with a value of 1 on the top, bottom, left and right sides, and a connection number that gives the number of separated neighboring pixel groups with a value of 1. N0 or 1, the pixels with value 1 whose neighboring pixel number Na is 2 or more are sequentially changed to 0, and the thinning process is repeated until there are no pixels left to be changed, and the top, bottom, left and right are pixels with value 1. The surrounded pixel with value 1 is set as the occlusion point, and a 3×3 pattern is considered in the image after thinning processing, and the value of the center pixel Po, the values of the neighboring 8 pixels P1 to P8, and the occlusion point at the diagonal position of Po are calculated. According to the pixel P. A connection determination process that determines connections between and neighboring pixels P1 to P8, and an operation that starts from an end point or a branch point and traces pixels according to a predetermined connection to obtain a chain code, which is repeated until there are no unconnected pixels. An image processing method characterized by comprising processing. (2) Number of connections N. The image processing method according to claim 1, wherein is defined as (X9-Xl), where Xi is the negation of the value Xi of eight neighboring pixels Pi. (3) Number of connections N. However, depending on the value Xi of the 8 neighboring pixels,
An image processing method as defined in claim (1). (4) Connection determination processing connects the center pixel to the left, right, top, and bottom pixels for 3×3 patterns other than the dense partial pattern mill f in which all 2×2 patterns have the value ■, and diagonal pixels are connected to the adjacent left, right, top, and bottom The image processing method according to claim 2, wherein the image processing method is connected only when there is no pixel with a value of 1. (5) Connection determination processing is performed using partial patterns a to f in which all 2×2 patterns have a value of 1, or five possible dense patterns P.
1 to P5 is determined based on the values of the center pixel, neighboring pixels, and the presence or absence of obstructing points in the diagonal direction, and the partial patterns a to f are connected according to the connection of predetermined dense patterns P1 to P5. An image processing method according to claim (4), wherein: (6) An image memory 5 that stores the values of a large number of pixels that are discretized in the vertical and horizontal directions and have either the value 1 or the value 0, and the values of each pixel and neighboring pixels stored in the image memo J) 5. A hole-filling processing circuit 1 reads out the value 0, sets the value of the pixel surrounded by pixels with the value 1 on the top, bottom, left and right as 1, and stores it in the image memory 5.
and each pixel P. Improvement of neighboring pixels P3 and left P5 are both 0, and P3 and P5 are 1, but P7
A thinning classification circuit 2a that classifies pixels of the B group in which either P1 or Pl is 0, an A group memory 6 that stores the A group pixels, and an 8 group memory 7 that stores the B group pixels. The values of pixels and their neighboring pixels are read out sequentially from the image memory 5, the A group memory 6, and the 8 group memory 7, and if the number of neighboring pixels Na is 2 or more,
Thinning circuit 2 that changes the value of a pixel whose number of connections is 1 to 0
b, a blockage point detection circuit that detects a blockage point with a value of 1 surrounded by pixels with a value of 1 on the top, bottom, left and right sides, and a thinning completion determination circuit, and detects the values of the center pixel and neighboring pixels and the blockage points at diagonal positions. A connection determining circuit 3 determines the connection between the central pixel Po and neighboring pixels P1 to P8 based on the presence or absence, a connection code memory 8 stores a connection code for each pixel whose connection has been determined, and a thinning end determination circuit outputs a thinning end signal. A control circuit 10 that repeatedly functions the thinning circuit until the line is released, a register that stores the previous direction of movement, a primary mask circuit that removes the connection corresponding to the previous direction of movement from the connection code, and a next direction of movement based on this result. Direction code generation circuit that creates a code representing this direction, connected to the connection corresponding to this direction? Tracking circuit 4 that has a secondary mask circuit to remove from εt1 and reads the connection code from the connection code memory 8
Then, the chain code memory 9 for storing the direction code from the direction code generation circuit of the tracking circuit 4 and the address to be read from the connection code memory 8 are specified, and the connection code is sequentially given to the tracking circuit 4. An image processing device comprising an address control circuit 11 that corrects an address to the next pixel based on a signal.