Optimization Approaches to the Problem of Edge Linking With a Focus on Parallel Processing

OPTIMIZATION APPROACHES TO THE PROBLEM OF EDGE LINKING · WITH A FOCUS ON PARALLEL PROCESSING

M. D. Diamond, N. Narasimhamurthi, and S. Ganapathy

""

Department of Electrical and Computer Engineering University of Michigan Ann Arbor, Ml 48109

Unfortunately, the problem appears to be as difficult as It is important. Although, the inherent difficulty does not appear to be so much in the conceptual problem of finding a good model to represent the contour or signal, in the presence of noise, but rather with the computational complexity of the algorithms which extract it. For example, In one model based system, the edge extraction and linking required approximately 99% percent of the overall computational effort (Perkins, 1979). In fact, most current edge linking approaches are based on combinatorial search or tracking algorithms wherein the points In the state space correspond to pixels in the image (Ballard and Brown, 1 982). The search is usually guided by an evaluation function which Is in some manner related to the over all length or strength of the contour in the original edge map.

It is not surprising that computational difficulties arise in conjunction with a search defined on a space the size of a typical image. If it is assumed, therefore, that edge linking is inherently a problem in combinatorial optimization, and on the other hand, a fundamental problem in computer vision, then research into means by which the search can be implemented In a highly parallel manner, despite the implications for the cost of the supporting hardware, is justified. Another basic problem with existing strategies is that they may encounter difficulties If, for example, the search is incorrectly rooted, as will occur if the starting point happens to be a noise point, or if, because of some ancillary feature in the image, the search continues down a strong, but false path. The focus of the work described below is in addressing these basic Issues.

B. Dual Approaches to Combinatorial Search Problems

Because it does not appear that existing graph searching methods can be implemented in a parallel manner, the approach proposed here is to perform the search in an associated dual space. In order to do so, the problem is first formulated as an integer programming problem. A Lagrange dual (Bazaraa and Shetty, 1979) realization of the problem is then presented. In accordance with price directed decomposition theory (Shapiro, 1979), the particular form used will allow for the decentralized computation of the solution, at least in the initial stages of the process. Although graph searching problems occur in almost every area of artificial intelligence, the techniques presented here are particularly suited to those combinatorial search problems where the entire state space is known in advance. A graph labeling problem, where the graph is defined with respect to an image raster, is an example of this situation.

ABSTRACT

An important problem in computer vision, that of edge linking for contour or line drawing extraction, is approached from the point of view of a graph labeling problem. A Lagrange dual approach to an integer programming formulation of this problem will be presented. Although the inherent complexity of the problem will not be reduced, the techniques presented below will allow for a partial decomposition of the solution algorithm. Furthermore, the approach which will be presented appears to have certain advantages over existing line tracking and graph searching

algorithms.

INTRODUCTION

Two basic ideas will be pursued in the following discussion: The first involves an approach to the problem of edge linking. The second involves an introduction to the use of dual methods for combinatorial optimization problems relevant to issues of artificial intelligence. In order to relate these two concepts, edge linking will be modeled in terms of a graph labeling problem which will then allow for the direct application of the proposed dual methods.

A. The Problem of Edge Linking in Computer Vision

The derivation of contours describing the outlines and the salient features of objects is an essential component of most model based systems. Once these outlines have been derived, well established classification techniques, such as syntactic pattern recognition based spline primitives (Perkins, 1979, Fu 197 4), Fourier shape descriptors (Zahn and Roskies, 1972), or generalized Hough transforms (Ballard, 1981 ), can be used to recognize the object from a set of known models. It is well known, however, that the edge detection process Is not in itself sufficient to describe the required contours, as a primitive edge map will almost always contain broken contours or spurious edges. It is for this reason that edge linking is considered to be one of the most basic problems in computer vision (Marr, 1975).

. This work was supported In part by the Robotics Research Laboratory, and In part by the Ultrasonics Imaging Laboratory, both In the Depart­ ment of Electrical and Computer Engineering. University of Michigan

··current address : Computer Systems Research laboratory, Bell Tele­ phone Laboratories, Holmdel, New Jersey

C. Graph labeling and the edge linking problem

A graph labeling problem Is one in which a unique label ;~,. 1 from some set, A, of labels must be assigned to each vertex of a graph, G = (V,E), with vertex set v = !v1 , v2, · · ·, Vn!· and an edge set E c V x V. In the application example of section IV, the graph is defined in terms of an image with · each pixel considered to be adjacent to its eight immediate neighbors. The label set in this case corresponds to the assertion of the existence of scene events, which may include line segments, elbows, and comers at various orientations at each pixel, as shown in figure 1. A constraint network (Montanari, 1 97 4, Mackworth, 1977, Freuder, 1 978) 1s constructed from the graph G by associating with each edge V;V;· E: E a binary relation, R11., known as a constraint relation, defined on the label set, RIJ c A x A. A pair of labels (;>,.j,Aj') on adjacent vertices v1 and v1· are consistent if (;>,.j,Aj ') E: A, and Inconsistent otherwise. For this application, a pair of labels is consistent if and only if an edge segments is not broken across a pixel boundary as given, for example, in Diamond et al. (1982). A ltJbeling :>; = ;>,. 1 ;>,. 2 ···;>,."which assigns label ;>,. 1 to vertex v1 is consistent if every pair of labels on adjacent vertices is consistent. Note that within the context of this application, a labeling will be consistent if and only if it describes a smooth contour. Associated with each label ;~,. 1 on each vertex v1 is an initial labeling value, or merit figure, c11 . For this application, the merit figures are assumed generated by feature detectors sensitive to the various scene events as shown in figure 1 .

GO

Figure 1 : primitive features corresponding to labels for the edge linking application.

Although several viewpoints on the continuous graph labeling problem have been presented (Rosenfeld et al. 1976, Ullman 1979, and Davis and Rosenfeld 1 976), in the definition used here, the problem will be to find that consistent labeling such that the sum of the initial labeling value Is maximum. This definition of the problem is attractive because a solution can be extended to many established classification rules (Diamond et al ., 1 982) . Finally, in the same spirit as Ulimans "simple local processes," (Ullman, 1 979) we will be interested in developing decentralized algorithms which can be Implemented on an SIMD or "cellular" architecture.

As defined above, continuous graph labeling is easily shown to be NP-complete. The combinatorial nature of the problem will preclude, therefore, the derivation of a local or cooperative algorithm which guarantees a globally consistent labeling in the general case. This, then is the major difficulty of the edge linking strategy proposed here. However, as will be demonstrated, the technique described b.elow t:an be used to significantly improve an initial, noisy edge map, and if a globally consistent labeling is required, the dual approaches suggested below may be used as a front end for further processing. In this sense, these techniques may be thought of in the same vein as the discrete relaxation processes (Rosenfeld et al., 1976, Waltz, 1 975) extended to the continuous domain, which serve to reduce the combinatorial search space but do not necessarily guarantee a globally consistent labeling.

II A Lagrange Dual Approach to the Graph Labeling Problem

A. General Formulation

For the purpose of the following discussion, it is assumed that the graph labeling problem is defined with respect to a graph with n vertices, IV I = n, and a label set with m labels, IAI = m. Indices such as j and j' will always be used in conjunction with labels, and ;~,. 1 and AJ' will denote elements of the label set A. In a similar manner, indices such as I and I' will always be used in conjunction with vertices, and v1 and v1· will denote elements of the vertex set V. Let c 11 E: R be the initial strength measure or merit figure associated with label ;~,. 1 on vertex v1· The integer programming formulation of the continuous graph labeling problem is then given by:

Maximize:

Subject to:

for every Inconsistent pair of labels (;>,. 1 ,;~,.r) on adjacent vertices v1 and v1 ··

As given by constraint (2.4), x1j is a zero-one decision variable associated with label .>..j on vertex v1· In the solution, Xij = 1, if label .>..j Is to be selected for vertex v;. Thus, constraint (2.2) serves to guarantee that exactly one label is assigned to each vertex and constraint (2.3) serves to specify that for adjacent vertices v1 and v1· a pair of labels .>..i and .>..r are not simultaneously assigned to these vertices if they are not consistent.

Let

be the vector of decision variables. Furthermore, let /.1. be the set of all four-tuples iji'j' corresponding to invalid pairs of labels (.>..i,.>..r) on adjacent vertices v1 and v1·· The dual will be defined with respect to a vector u, which consists of components Uiji'f· one such component for each iji'j' E /.1.· According to the theory, the primal vector x and dual vector u are used in the definition of an auxiliary function:

By simple algebraic manipulation, ~P(x,u) Is seen to have the form

where

Is the current merit figure or labeling value, relative to the dual vector u. Also, J.l.(i,j) c /.1. is the set of all 4- tuples corresponding to invalid pairs of labels, In which the label .>..i on vertex v1 participates. The Lagrange dual form of the original problem is then defined to be:

Minimize: e(u), u;;.,O

Where:

Here, X is the set of all 0-1 vectors x , which correspond to (unambiguous) labelings, that is, constraint (2.2) is satisfied by every x E X. Note, however, that x E X need not be a consistent labeling. Thus x need not necessarily satisfy constraints (2.3).

The form of the dual given by equations (2.8) allows for local determination of those x E X at which the maximum value of 9'(x,u) occurs, for a given u. This Is because the r 1i can be computed on a local basis, and L;u1JiT is independent of x . Thus deriving the primal values associated with a given u Is equivalent to choosing a label, .>..J at each vertex such that the current labeling value r1i Is maximal, a process often referred to as local maxima selection (Zucker et al., 1 978).

B. Example Problem

A simple ·example to Illustrate the formulation and notation used above Is given In figures 2a, and 2b. Figure 2a is a IV I x I AI product graph gives each label on each vertex explicitly, as well as the pairs of consistent labels by connecting them with a solid line. Figure 2b shows the complement of this graph, In which inconsistent pairs of labels are connected by dotted lines. Because of the definition of the dual function, it becomes more important to concentrate on the complement graph.

The primal statement of this problem becomes :

Maximize:

Subject to:

The Lagrange dual formulation Is:

Minimize:

Figure 2a product graph for the constraint network of the example.

In view of equation (2.1 0), the definition of 9'(x,u), and figure 2b it can be seen that there is a dual variable associated with each such edge between invalid pairs of labels. The current labeling value associated with each label on each vertex is the the Initial labeling value minus the sum of all dual values associated with edges in the dual graph.

C. PMI Sets

The continuous graph labeling problem can be reformulated by combining constraints, to the extent possible on a local basis. For example equation (2.1 0) of the example In section 2.2, can be replaced by

Note that the set consisting of labels ilq and )1.2 on vertex v 1 and label )1.1 on vertex v2 has the property that

Figure 2b: complement graph for the constraint network of the example.

only one of these labels can be chosen at once. The same holds for the set consisting of label A1 on vertex v, and labels )1.1 and )..z on vertex Vz. Such constraints will be referred to as pairwise maximally inconsistent (PMI) sets of labels. The PMI sets can be determined, in general, by considering the product graph with the addition of edges connecting every label on a given vertex with every other label on that vertex. The PMI sets then corre~ond to the maximal cliques of this graph (refer to figure 3 ) . .

In the problem formulated In terms of PMI set constraints, there is a dual variable associated with each PMI set. In general there will be fewer PMI sets than pairs of invalid labels between a given pair of vertices. Therefore, by restructuring the problem in this manner, there will also be fewer dual variables, and this will reduce the amount of memory required for a given application. An advantage in computation can also be gained as will be discussed below. Finally, with this formulation, a relationship exists between this problem and the discrete relaxation processes, which can be used to understand the behavior of the solution algorithms.

Ill MINIMIZING THE DUAL

We present below an outline of the algorithm used to minimize the dual function. Further details are available in a preliminary report (Diamond, 1983), although work on certain aspects of this approach is still in progress.

..\3 ·

· ..\3

Figure 3 : augmented complement graph showing maxi­ mal cliques. Edges exist between label )1.1 and ~ on vertex v1 and AI and ~ on vertex v2 but are not shown.

·Note that there will always be a maximal clique associated with the oet of all labels at a given vertex. The resulting constraint: I; Xtj ,.;; 1 Ia redundant, In view of equation· (2 .2). ~EA

A. The Descent Algorithm

Each iteration of the descent procedure involves one "pass" over the image. A pass involves considering all possible pairs of adjacent vertices, or equivalently, edges in the graph. Any set of disjoint pairs of vertices (or edges) can be considered simultaneously, hence the partial decomposition of the algorithm. In considering any such pair, say vertex v; and vertex v;' the following procedure is used:

1. Calculate the current labeling values, rti· for all labels on vertex v; and v1'.
2. Let m1 be the maximum of all current labeling values associated with labels on vertex v;. Likewise, let m;' be the maximum of all current labeling values associated with labels on vertex v;'.
3. Define the set M; to be the set of labels on vertex V; whose current labeling value is equal to m1· Likewise, define the set M;' to be the set of labels on vertex v;' whose current labeling value is equal to m1'.
4. [ 4] If the sets of labels, M; and M; ' are not contained in a PMI set, then no local descent direction exists, otherwise,
5. Let L; be the set of labels in a covering PMI set associated with vertex v; and L;' be the set of labels in that set associated with vertex v 1'. Let

[6] Define

[7] Define

and finally,

1. The descent step is impiemented by adding 6 to the dual variable associated with the covering PMI set constraint.

An interpretation of this algorithm can be given as follows : Initially, one chooses that label at each vertex with the greatest associated labeling value, that is, according to the local maxima selection process. If the resulting labeling is consistent then the original problem has been solved, that is, the resulting labeling is that globally consistent labeling such the sum of the initial labeling values is maximum. Otherwise, the strategy involved is to "penalize" the labeling values associated with invalid pairs of labels across adjacent vertices in the graph. This penalty is implemented through equations (2.7) by Increasing the value of the associated dual variable. The hope Is, that reducing the values of the labels which participate in Inconsistent labeling pairs will, at the next Iteration, result in different labels being chosen at the respective vertices. This process will then reduce the overall number of inconsistent labeling pairs.

Although the algorithm appears on the surface to be quite detailed, in fact it is very easy and efficient to Implement. By bit encoding the labels at each vertex participating in a given operation (e. g., sets M; and M;') as well as the labels in a given PMI set, the processing required for a given pair of vertices can be reduced to a couple dozen machine instructions per vertex pair per iteration. For the label set discussed in the introduction, only 8 PMI sets are required to cover all the constraints between a given pair of vertices, so the search required to find a cover is minimal. Finally, from the basic operations Involved it can be estimated that this algorithm will run well over 1 00 times faster than any of the algorithms associated with the so called " relaxation labeling" processes.

B. Spacer Steps

One of the immediate drawbacks with the algorithm given above is that it will generate fixed points with 2 or more labels with associated labeling values tied for the greatest value at each vertex in the graph. When this happens, and when the resulting sets of chosen labels cannot be covered by a PMI set at any vertex, then the dual can not be minimized any further on a local basis. In this case, it is not possible, in general, to choose a label from among those which are tied with the best current labeling value except on the basis of informal heuristics. For this reason a "spacer step" will be used after every iteration of the descent algorithm given above. In the experiments described below the spacer step consists of an iteration of the "average-max" updating rule (Diamond, 1 983) which updates the current labeling value c3 of a label Aj on vertex v1 by:

Where N(i) is the set of vertices adjacent to vertex v;, ril'(;>...j,>..r) is one If label Aj on vertex v; Is consistent with label >..r on vertex v;· and zero otherwise, and N = I N(i) I· Thus, a processor performing the updating for label Xj on vertex v1 would generate N values to be averaged (along with the current labeling value c;}), one such value corresponding to each vertex in the neighborhood, by taking the maximum of the current labeling values associated with labels consistent with Xj on vertex v ;.

• If >;:t is the current labeling chosen by the local maxima selection process and c(X~ is the sum of the associated current labeling values, then the average-max updating rule can be shown to have the following properties:
• If it is not a consistent labeling, then the sum of the current labeling values with xt will have decreased after the next Iteration, that is c(Xt+ 1 ) < c(Xt).
• If xt is consistent then c(Xt+ 1 ) = c(Xt) and the labeling selected at each iteration t ' ~ t will be the same.
• From [1] and [2] the value c(Xt) is a non-increasing function of t . Furthermore, it can be shown that the value associated with a consistent labeling will increase at each iteration, if that labeling is not the one selected by the local maxima selection process.

IV EXPERIMENTS

Figure 4a shows a scene taken from the General Motors, "Bin of parts" database after the application of feature detectors sensitive to each of the scene events shown in figure 1. Those labels at each pixel such that the corresponding feature detector outputs are maximal are shown in this figure. Figures 4b and 4c are the results of choosing the best labels at each pixel after 8 and 20 iterations of the procedure described above. In the case of labels tied for the best at each vertex, preference was given to the label corresponding to the blank pixel. Otherwise, that label which was consistent with the greatest number of labels on vertices in the neighborhood was chosen. Beyond this, ties are broken arbitrarily.

V DISCUSSION

We have described an approach to the problem of edge linking which is based on the graph labeling model. A Lagrange dual approach to the integer programming formulation of the associated continuous graph labeling problem has been discussed. Obviously much detail has been left out as the intention here has been to limit this presentation to an overview of current results related to an ongoing research effort.

The approach described here, as is the case with many of the other cooperative algorithms applied to problems in computer vision, the relaxation labeling processes in particular, is heuristic in nature. Nonetheless, the existence of an underlying problem definition as well as the direct relationship between the model and the application is a major advantage which this approach has over the relaxation labeling algorithms. In the latter case such a definition is not present. There are other advantages. For example, because the dual function is convex, one can with certain preca4tions, guarantee that the descent algorithm converges. Although we can offer no theoretical limit on the convergence time (i.e. the number of iterations required before the labeling chosen by a local maxima selection process does not change), it has been observed that the algorithms described here will converge on the order of 1 6 to 20 iterations for the examples given above. These figures appear to be independent of the particular problem.

However, there are also problems in using heuristic techniques to solve a combinatorial optimization problem in a decentralized manner. For example, these algorithms will almost always result in a fixed point with multiple labels tied for the maximum value. As noted previously, in this case there is no basis on which to make an intelligent labeling choice in a purely local manner even though there may exist a globally consistent labeling among the labels tied for the best value. Finally, the process is somewhat sensitive to the amount of noise in the image, and very sensitive to the way in which the initial labeling values are derived.

If the main interest is in the application itself, then a more sensible approach would be to relax the requirement of a totally decentralized solution, that is, to incorporate some form of an enumerative scheme as with the graph searching methods described in the introduction. Even s<J, the graph labeling model of the edge linking application offers an advantage since many aspects of a branch and bound approach can then be implemented in a decentralized manner. For example, a variation of the Lagrange dual algorithm presented here could be used as a means for generating bounds in a branch and bound approach (Geoffrion, 1974), and the discrete relaxation process (Rosenfeld et al., 1976) could be used as part of a feasibility test of a given candidate subproblem.

Furthermore, th1s model offers the potential of adapting techniques from other classes of 0-1 integer programs to the edge linking application . The graph labeling problem, as defined here, is a special case of the well established set partitioning problem (Balas and Padberg, 1974). It is also easily transformed to the vertex and set packing problems , as well as the set covering problem, for which heuristic algorithms to handle large scale situations exist .

In order to make the general model more useful, a better understanding of the graph labeling problem is needed. Current efforts towards a formal understanding of this problem involves both an investigation into the nature of its linear programming relaxation, which is the problem of section 2 .1 with equation (2.4} replaced by:

and the relationship between the Lagrange dual and this relaxation. Although, aspects of the algorithm presented above are still not understood, the results from the application of these techniques to real world scenes, for example, the industrial scenes shown in section 4, are encouraging. Finally, some effort is being directed towards developing techniques for solving the problem when the underlying graph has a particular regular structure such as that corresponding to an image, which has pronounced rows and columns. When this occurs, a bidirectional dynamic programming approach (Diamond, 1983) can be combined with the integer programming algorithms described here to derive more robust algorithms.