Boundary And Object Detection In Real World Images

I. Introduction

A substantial amount of research has been done in developing techniques for locating objects of interest automatically in digitized pictures. Drawing the boundaries around objects is essen­ tial for pattern recognition, tracing of objects in sequence of pictures for control systems, image enhancement, data reduction , and various other applications. References 1, 2, and 3 comprise a good survey of research and applications in image processing and picture analysis.

Most researchers of picture analysis asswned tha t ( 1) the image of an object is more or less uniform or smooth in its local properties (that is, illumination, color, and local texture are smoothly changing inside the image of an object) and (2) there is detectable discontinuity in local properties between images of two different ob­ jects. We will adopt these two assumptions in this paper and assume no textural image (see Ref. 4 for an example of texture image analysis which does not make these assumptions).

The work on automatic· location of objects in digitized images has split into two approaches: ( 1) edge detection and edge following vs (2) region growing . Edge detection meant applying in dif­ ferent points over the picture local independent ope rators to detect edges and then using algo­ rithms to trace the boundaries by following the l ocal edge detected. A recent survey of litera­ t u r e in this area is given in Ref. 5. The region gr owin g approach was to use various clustering a l gor ithms to grow regions of almost uniform local pr operties in the image. (See Refs. 6-9 for typic al a pplic ations.) More detailed references will be given later.

In this paper the two approaches are c ombined to complement each other. The end result is a more powerful mechanism to do the job of seg­ mentation pictures into objects. We developed a new edge detector and combined it with new re­ g ion growing techniques to locate objects and t he r e by resolved the confusion that has resulted fo r r egular edge following when more than one isolated object on a uniform background is in the s c ene (see Ref. 1 0).

1. A new and "optimal" (given certain assumptions) edge detector is presented.
2. A simple one-pass region growing algo­ rithm which was implemented on a mini-computer. It utilizes the edge detector output.
3. ( 3) The application of path generator algo­ rithms and "shortest path algorithms" to do the boundary following so as to close open edge lines into boundaries around regions.
4. Special-purpose region growing intended to close open edges (cracks).
5. A special clustering algorithm which sim­ plifies the region structure resulting from appli­ cation of (1) ·through (4).

II. Definition of Terms

_ The input is expected to be in matrix foj"m V(i,j) i = 1, ·.. , N j =I, ..· ,M, where Vis a vector in Rn, n is a function of the sensory sys­ tem, usually 1 (gray level picture), or 3 (color or x, y, z coordinates of surface in the scanning direction), or 6 (color and 3-D information). An edge unit separates two adjacent matrix points; that is, an edge unit is between (i, j) and (i + 1, j) or between (i,j) and (i,j + 1) for some i , j, (see Fig. 1).

An edge unit is usually adjacent on both ends to other edge units. There are 64 combinations of edge units continuing an edge unit since each of the edge units e1, e2, e3, e1 1, e21, e31 in Fig . 1 may exist or not.

Two points on the grid (I, J) and (K, L) are said to be in the same region if there is a path se­ quence (il,jl), ..· , (in,jn) such that i} =I, j 1 = J, in = K and jn = L , where (im, jml is adja­ cent to (im+l· jm+ll form = 1, . . . n- 1 and there i s no edge unit between the two. A region will be a maximum set of points satisfying that property.

An edge-line (or an edge) between region R1 and region R2 is the maximal sequence of adja­ cent edge units such that each edge unit in the sequence is between two matrix points , one be­ longing to R1 and the othe r to Rz. It is possible that an edge line is inside a re gion (R} = Rz).

An edge line which is between two different regions is called a boundary. An edge line which i s inside a region is called a ~ac k. An open crack is a crack in which at leas t one end termi­ nates without connecting to any edge line. A

closed crack is one which terminates at both ends on another edge line . For instance, cracks will appear when an object is smoothly disappearing into the background on one side and has detec­ able dis continuity on the other side (Fig. 2).

Using the above definitions, this report pre­ sents an edge detector which detects edge units in parallel locally on the whole image. Then a re ­ gion grower which results in the g rouping of matrix points into regions and edge units into boundaries and cracks is presented. A local re­ gion grower which tries to break a region with a c rack in it into two regions for which the crack is part of the common boundary is then presented . Alternatively, an open-crack- e xtending algorithm is suggested to connect the open edge unit of the crack to another edge line.

III. The Loc al Edge Detec tor

The edge operator is a detector of local dis­ continuity in an image. When applied between two adjacent points such as (i , j) and (i + 1, j). it should return a value which will measure the confidence that there is an edge between (i , j) and (i + l,j). Since we work with noisy input to achieve reliabil­ ity, the operator must look at two 2-dimensional (2-D) neighborhoods N j a nd N2 to obtain a reliable value. Ne ighborhood N 1 will include (i, j) and a few adjacent points; N2 includes ( i + 1, j) and a few adjacent points; and N1 (\ N2 = 0. As a result the value return ed will measure the confidence that the nei ghborhoods belong to images of differ­ ent objects.

Edge detection is actually composed of three components: (l) choosing the proper neighbor­ hoods, (2) the measurements of differences be­ tween image structures in the two neighborhoods, and (3) locking on the exact position of the edge. Discussion of each of these steps follows.

rv. Measuring Differences in Structure Between Two Neighborhoods

Any techniqu e which measure structural dif­ ferences must make some assumption (explicitly or implicitly) on the structure of an edge vs the area inside a region. Binford and Hershkovitz (Ref. 22) suggested three possible ideal edges defined by the intensity profile on a normal-to­ the-edge line (Fig. 3).

All of these idealized edges are in reality washed with gaussian noise on both sides, where the noise is the result of both hardware noise and surface irregularities. Basically, the decision needed to be made is between two hypotheses:

Ho: The readings in N 1 and N2 are taken from the same object.

Ht: The readings in NI are taken from one object and in N2 from another object.

Neighborhoods N1 and N2 are the neighborhoods tnentiuned in the previous section, and the deci­ sion ;~s t o how to choose them will be described in lh<' next section.

An optimal (best for its size) decision between llo and Ilj will utilize the maximum like l ihood ratio as follows: Let Po be the maximum like li ­ hood estimate of the structure (reading in N 1 and N2). given that Ho is true, and let P1 be the max ­ imum likelihood estimate of the structure , assuming H1 is true. Then,

This decision will be optimal for its size (see the Neyman-Pearson Test in Ref. Il, pg. 55); hence, if our assumptions are valid, we have an ideal edge detector, given only readings in N 1 and N2. (We will deal with gaussian probabil­ ities; hence we will ignore P1/Po = K . ) The conclusion is that P 1 /Po is the best measure of the edge strength. Following are two examples of applying these principles to edges of types (a) and (b) in Fig. 3.

EXAMPLE I

Assume that the edges and surfaces will be of type A, with added white noise which is object­ dependent. Then Ho and H 1 will become

Ho: The readings in both N1 and N2 are independently taken from the same normal distribution N(fJ.o, O"o) with unknown fJ.O, ""O·

The readings on N 1 are independent! y taken from normal distribution N(fJ.I. O"I ); and the readings on N2 are taken from normal distribution N(fJ.2 . 0"2); (fJ.l, O"l) need not be equal to (fJ.2' 0"2).

To apply the maximum likelihood ratio prin­ ciple we need to find a maximum likelihood esti ­ mate for (fJ.O, O"O) (fJ.l, 0"1) and (fJ.2, 0"2). Given (xl, · · · , xn) readings taken from a normal dis­ tribution with unknown (fJ., a- ), the maximum likelihood estimates are

Let Pmax the probability of getting those r e adings assuming they are taken independently from normal distribution N(fj:, ~)then

Hence, if the readings on N 1 are (xl , · · · , xml and on N2 (YI, · · · , Ynl· then, on N1,

On N 2 ,

and on NI combined with N2,

Here we assume that when assumption H1 holds the readings on the two neighborhoods are independent. That is, the maximum probability assuming HI is the product of P1 and P2. To save computation of square roots we work with 2 instead of the

Note that the edge value suggested is self­ scaling with respect to noise and texture: In areas where <Tl ~ <T2 ~<TO » 0 (highly textured areas or the result of noisy hardware), the edge value will be low, near 1, while any small steps in almost uniform areas will be recognized easily. In practice, we computed the variance of noise in the hardware by sampling over time the same points in static scenes . All variances were forced to be at least the hardware noise so as to prevent divisions by zero in pathological cares .

At this point it may be worthwhile to compare our approach with that of Ref. 12 . Both try to use a maximum likelihood ratio to compute scores for an edge. But while we have a simple model and a practical way of computing the con­ fidence, Ref. 12 assumes a priori deterministic classification of all possible idealized noise-free structures to edges and no edges . Then, for a given reading structure, the noise assumption is used to compute the probability of all idealized structures that could have caused the readings. These probabilities are used to decide whether or not the readings represent on edge .

It should be mentioned that other statistical techniques were used for edge detection as in Ref. 22 and Ref. 18, but none of the edge detec­ tors which appeared in the literature used the maximum likelihood test for edge value .

EXAMPLE 2

Hen! we assume that each matrix point V(i, j) is a 3-dimensional vector (x, y, z). Actually the raw readings are just distance R(i,j), but to avoid a strong dependency on the sensory posi­ tion, (i,j,R) are used to compute (x,y,z) . This is the form of input read from a device which measures distances to surface (such as radar or devices which measure the time of flight of laser beams to an object). The i,j corresponds to ver­ tical and horizontal steps in the scanning angle. The two adjacent neighborhoods on the matrix Nl and NZ have readings (xi, yl, z1), · · · , (xn,yn,zn) in N1 and (x11,y1l,z11), , (xml, yml, zml) in NZ. We assume that objects are almost planar locally with added white noise with mean to position readings. That is, if we read (xl, yl, zl), · · · , (xn, Yn. zn) in a small neighborhood on an object we have a, b, c, d, cr such that and

With this assumption the edge detection decision will be a choice between Ho and H1 .

Ho: The readings in the two neighborhoods are taken from the same plane. That is the readings on both N 1 and N2 satisfy for some (ao, bo, co, do, uo)

where

for all (x, y, z) readings in N 1 and N2 .

There are two not necessarily equal planar fits for the readings on N1 and on N2. That is, there are (al> b1> c1, d 1, ITl) for N1 and (az, b2, c2, d2·, IT2) for N2 such that

To apply the Neyman-Pearson principle for this case we want to find maximum likelihood estimates . Maximum likelihood estimates a1, b1, c1, d1 will be

and Solving for the optilnal (a}, b}, C}, dl) is a relatively straightforward process . Once they are found, the maximum likelihood estimate for N1 will be

Hence, we have the expression which tests for an edge . It is of the following form: If

decide for H1, otherwise Ho.

Note that (x, y, z) may be replaced by (i, j, g) in regular black and white pictures, in which case we will have a regular picture edge operation which will be able to handle edges of type B in Fig . 3. Somewhat similar applications were re­ ported in Ref. 20 and Ref. 22 for dection of gra­ dient edges Fig. 3(b). This edge operator has not yet ilnplemented on our system.

V. Locking on a Detected Edge

Computing the edge value is not usually suffici­ ent to decide where to put the edges. The values that are computed usually look like the ones in Fig. 6 .

One way of forcing the edge to be well defined is to constrain it to be a local maximum in addi­ tion to having a confidence value higher than a certain threshold. This is, of course, extremely important for locking on the center of the edge (see Ref. 23, page 382). Usually there is still some local ambiguity on the location of the edge, and for many practical reasons it is better to treat the area around an edge as ambiguous . The source of problems here is that, because of cotn­ puting tilne constraints, it was impossible to find a global optilnum for edge lines using all avail­ able data, and it was necessary to use only local information for evaluating the edge units in this level. In our system, the decision as to where exactly to put the edge was left for the region grower (see below) . To demonstrate the possible 2-D ambiguity, see Fig. 7.

The search for a maximum may be used for special-purpose edge detection. For instance, if we look only for one dark stripe crossing a white background, forcing the edge to be the absolute maximum or minilnum on a horizontal line in the image (keeping track of the direction of the change) will supply the appropriate pair of edges .

VI. Region Growing

The output of an application of an edge detec­ tor results in two new matrices in addition to the matrix V(i, j) of raw data . The first is EV(i, j), which is the measure of the confidence that there is an edge unit between (i,j) and (i,j + 1); the second is EH(i, j), which measures the confidence that there is an edge unit between (i, j) and (i + 1, j). EV(i, j) and EH(i, j) may include extra bits as determined by the direction of the change on that suggested edge unit.

This output as it stands is not sufficient for application of pattern recognition and various pic­ ture quantitative analysis tasks. Outlines of ob­ jects are needed in order to recognize features. One way of achieving that is to use a region grower which will outline objects by clustering points into regions. This approac<h was used in the past fo;r picture analysis. Recent works along that line are Refs. 6, 7, 8, and 9. The basic conclusion of those works is that without using semantic information, which is the knowl­ edge on the subject of the picture, clustering can­ not create perfect outlines. More recent work, Ref . 24 and 11, pg. 324, introduced new tech­ niques of clustering which provide more flexibil­ ity and may upgrade clustering performance for images .

Here we introduce a new algorithm for clus­ tering based on search for "valleys" of edge values in a picture . If random access is allowed, a relatively simple algorithm which starts from local minima of edge values and climb up can be implemented. Due to lack of storage capacity on our mini-computer, and in an attempt to use data as it digitized from the video signal sequentially, a one-pass algorithm to generate regions corres­ ponding to valleys was implemented . To our knowledge, this is the first time that this ap­ proach is used. Most works on region growing (ours included) lack the capacity to make use of the shape of the growing object. An alternative approach to region growing is "edge following" which was used in various works like Refs. 10, 16, 19, and 21. The basic idea in edge following is to detect a discontinuity and trace it and this way define edge lines. Unfortunately, the works in edge following suffers from lack of an effective way of tying regions properties into their decision processes and output.

Let us start by describing a one-pass algo­ rithm which the edge data into data structures of regions, boundaries, closed cracks and open cracks, and creates, as byproducts, two arrays, FH(i, j) and FV(i, j), where FH(i, j) means that the program puts an edge unit between (i - 1, j) and (i, j), and FV(i, j) means an edge unit between (i, j) and (i, j - 1) .

To ease the description of the decision mecha­ nism for placing edges, we need to define a few new terms . Let T > 0 be the edge confidence threshold; then,

• ( 1) 1 d 1 is the distance between two adjacent grid points. It will be

1. Reg(i, j) will be the region to which the point (i, j) belong. (Reg(i, j) is not defined to all points until the program is finished.)

• This value will be +"' if {i, j) is the only

point in its region .

• {5) A point P will be the minimum point for its region if

The algorithm is designed so that at each state there is always a non-decreasing edge distance value path from each minimum of any region to any other point in the region and the path enters that point from its minimum direction.

That is, if P and Q are two points such that

Reg{P) = Reg(Q\ and Val{P) = Val(Reg(P)), then there is a path {xl, xz, · · · , Xnl such that

We say if such a path exists that Q is reachable from P .

That is, two points are in the same region if you can get from one to the other in a path which does not cross a ridge of edge values.

VII. Algorithm Description

The program scans the image from left to right, line by line . That is, the scanning is such that when point (i,j) is processed, the program already worked on all points ( i 1. h) such that 01< j) or (j =hand il<i) .

Assume the program is processing point {i, j) .

Let D1 be a Boolean variable set to true if this program is not going to put an edge unit between (i, j) and (i, j-1); and false otherwise, and let D2

be a Bool .. an variable set to true if the program is not going to put an edge unit between (i, j) and (i - 1. j), and false otherwise. Let R1 = Reg(i,j-1) and Rz = Reg(i-l,j) (see Fig. 8).

The decision on the values of D1 and Dz is described by the following ALGOL-like program:

Begin

Boolean Good-Down1, Bad-Downl, Upl, Good-Down 2 , Bad-Down 2 , Upz; Good-Down1-(d((i, j), (i, j-1) :5 Val(i, j-1))1\ ((Val(i, j-1) :5 Val(R 1 ))

Comment: Good-Down 1 is true if point (i, j) is going to become a new minimum for R 1 (the region above), and it is adjacent to an old minimum; hence, any point of R 1 reachable from the old adjacent minimum will be reachable from the new;

Bad-Down1 -(d((i,j). (i,j-1)) < Val{i,j-l))A ((Val(i,j-1) > Val(RJ)))

- -Comment: This variable is true if (i, j) ·is not reachable from all minima of R 1 going through (i, j -1);

Upl- d((i, j), (i, j-1)) ~ Val(i, j-1)

Comment: This variable is true if point (i, j) is reachable from any minimum of R 1 by con­ tinuing the path that leads from that minimum to (i,j-1);

Good-Downz- (d((i,j), (i-l,j)) :5 Val(i-l,j)) /\ ((Val(i-l,j) 5 Val(Rz)))

Comment: This variable is true if point (i, j) is going to be a new minimum for Rz (the region minimum, to the side) and is adjacent to an old minimum of Rz; hence any point reachable from the adjacent old minimum will be reachable from (i, j);

Bad-Downz- (d((i, j), (i-1, j)) < Val(i-1, j))l\ (Val(i-1, j) > Val(Rz))

Comment: This variable is true if (i, j) is not reachable from all minima of Rz through (i-1' j);

Upz- d(i, j). (i-1, j) ~ Val(i-1, j)

Comment: This variable is true if point (i, j) is r eachable from any minima of Rz by con­ tinuing the path that leads from that minimum to (i-1, j);

If Good-Down 1 /\ Good-Downz then D1 - Dz- true else If Good-Down 1 11. Bad-Downz then begin D1- true; Dz- false; end else if Good-Down1 II. Upz then begin

if d((i, j), (i, j-1)) ~ d(i(i, j), (i-1, j)) the n 0 1 - Dz- true else begin D 1 - true; Dz- false; end; end

else if Bad-Down 1 then begin if Good-Downz V Upz then begin

D1 - false

D2 - true

end

else begin

D1 - false

Dz- false; end

end

else if Up1 II. Good-Downz then begin

if d((i. j). (i-1, j)) ~ d((i. j). (i, j-1)) then D1 - D 2 - true else begin Dz- true; D1 - false; end end

else if Up1 !\. Upz then, if R 1 = Rz then D1 - D2 - true else

if d((i. j). (i-1. j)) ~ d((i, j), (i. j-1))

then begin D1 - true; Dz- false; end

else begin D1- false; Dz- true; end

end Comment: In that ca~e we must force that only one of D 1 and D 2 can be true; other':"'i.se we cannot guarantee entrance through m1n1mum value from all minima of both R1 and Rz;

else if Up 1 t\ Bad-Downz then begin D1 - true; Dz- false; end

Val(i, j)- CXl; if D~ then begin Val(1, j-1)- Min(d((i, j), (i, j-1)), Val(i. j-1)); Val(i, j)- d((i. j), (i, j-1)); Va1(R1)- Min(Val(R1), Val(i, j)); end; if D~ then begin Val(1-1, j)- Min(d((i, j), (i-1, j)), Va1(i-1, j)); Val(i, j)- Min(Val(i, j), d((i, j), (i-1, j))); Val(Rz)- Min(Val(Rz)), Val(i, j)); end; If not (D 1 V Dz) then Val(Reg(i,j))- CXl;

The e 1 and ez (see Fig. 8) may exist or not, and as a result there are four starting conditions. The program may put D1, Dz. D 1 and D? or none of them, and hence, there are 16 cases m a point . (See Fig. 9 for a brief description of the different cases.)

Merging of two regions may always result in transformation into a crack of a previously com­ mon boundary of the two regions. In general, each operation of the region grower is fairly elaborate: more than meets the eye. The data structure used is not described in this paper, but it is essentially the same data structure described in Ref. 9, with slight modification to include edge line representation through chain encoding .

This one-pass algorithm is local and requires relatively small core resident data. However, it does not create maximal regions with respect to our criteria of path connectivity and reachability . The reason is the possible directionality of the region growing. On the other hand, it is rela­ tively simple and fast when other algorithms are considered. The maximality problem may be easily corrected if backup is allowed. Note also that, in fact, the threshold T plays a very small role in defining the output of the algorithm.

VIII. Simplification of the Result of Basic Region Growing

There are two straightforward options for simplifying the output of the one-pass region grower: (1) take all regions that are too small to be interesting and melt them into their closest neighbor (the distance between two regions will be defined later in the paper); (Z) take all short cracks which are weak (strength of the edge line will be defined later) and delete them. Of course, the threshold below which a crack is weak and a region is small is a function of how much we want to elaborate the task of the image analysis and is defined heuristically. In fact, in the current implementation all cracks are deleted since the edge operator was sensitive enough for our purposes .

IX. Merging Regions

The basic region grower utilized local detection procedures. Better decisions are achievable (at least theoretically) by using more global information. The problem is how to allow this additional information and still keep the program lean and fast. Research in that area was reported (Ref. 9). Basically, our approach is to be oversensitive on the local pass and as a result to oversegment the picture. But then we take the output data (which is simple relative to original picture) and simplify it. We take pairs of regions with common boundaries and merge them into one . In order to do that reliably, a confidence value which measures the confidence that the pair of regions are different is com­ puted . Then, iteratively we pick the pair of regions with the lowest confidence of being dif­ ferent in the current structure, merge them, and update the structure. The confidence is depen­ dent on two factors: ( 1) the magnitude of the change across the boundary and (Z) the difference of the properties inside the two regions. Both of these values are computed on the basis of assumptions similar to those used in the edge confidence evaluation. For instance, if we assume gray level readings, then let Xi i = 1, n be the readings on one region and xi ' i = 1, m be the readings at the other, then the second factor will be:

where

Results using only this factor are shown below. In Ref. 9, the local boundary properties are used to compute the edge values. The merging is stopped when weakest boundary strength is more than a given threshold.

Results

The suggested one-pass region growing algorithm driven by edge values was implemented on G.A. SPC-16/75 mini-computer of the Jet Propulsion Laboratory robotics lab . The input picture is digitized from black and white video signal of Cohu camera. The signal is digitized into 256 gray levels. The noise variance as measured from repetitious readings of the same point in a sequence of images is 2. A Ramtek display unit is interfaced to the mini-computer and is used to display the digitized picture in green. Boundary lines of regions are displayed in red over the original picture for performance evaluation.

All cracks are currently ignored. The threshold below which the edge value is truncated to 0 was fixed to 2000 in all the examples below. A system to set the threshold automatically so as to allow only 5 percent of the points of the ima~e to have value over the threshold was scrapped 1n favor of fixed absolutely threshold.

The output of the first pass is then pas sed to a region merger which reduces the number of regions also with default fixed threshold (merge till log (confidence) ~ 20) . The compute time for a 200 x 200 picture is approximately a minute for a program which is highly inefficient because of debugging aids .

The results which are shown below are encouraging . We believe that use of planar fits (gradient edge detector instead of the step edge detector) and using features of region dynamically as they grow to upgrade performance of the region grower will result even better perform­ ance . We found the region growing algorithm as an important task to scene analysis (Ref . 25) and look forward improving its performance.