Global Optimization of a Consistent Labeling

ABSTRACT

We prooose here a new def'ini t ion of con­ sistency, f'or relaxation-optimization labelin~ processes, which provides a natural way to de a 1 with the ·no-label problem, by eliminatin~ proba­ bility constraints. An essential characteristic is that the labelin~ solution of the problem is unique and may, for a lar~e family of world models, be found very efficiently. We focus here on the general case where consistency is a poly­ nomial function of the values of the labels.

I INTRODUCTHW

We assume in what follows that the reader is reasonnably famil i.ar with continuous relaxation processes[7]. Given a set of units U = lu , i=1 ·· N}, and a set of labels L = {(ti, i=1 ·· M}, pik mea11ures the value of label tk for unit u., which can be interpreted, depend in~ on the appl\cations, t'hs the probability for unit ui to belong to the k class, or as the similarity between u. and lk' etc ··· Let vector Pi= (pi 1 , ·· ,p ) and yector P = (P 1 , ·· ,PN): Pis a continuous H.beling. We assume, without loss of generality, the pik's are non-negative.

0 First, an initial labeling P is determined by separately classifying the units. Then a parallel and iterative procedure introduces con­ textual relations, known as the world model, yielding <y1 enhanced (i.e. more consistent) labeling P · We consider here a typica 1 world model:

l1i,k: Vik' set of (d-1)-tuples of labeled units v 1 , neighbours of ui for label lk, an element v J of V ik as!'iigns label rJ to unit uJ r . for r=1, ·· ,d-1 r

l1i,k,J: cikJ' bility or u assignment ot joint (or conditional) proba­ being labeled k for the local labels defined by vJ.

In that case, let Sophia-Anti polis

M. Berthed

It..!RIA

On'in'i Valbonne France

Thus the Otk's are polynomials of degree d-1 on the components of P. The corresponding vector 0 is called a compatibility vector. Obviously, for a consistent labeling, Oik and pik should be large or small at the samet1me.

Several updating schemes have been pro­ posed[7, 11 followin~~; this 11.ne, and mostly applied with d:2, (yielding linear Oik's). For all of them, the pi's are constrained ·to be pro­ bability vectors, i.e.:

This normali.zation is vita 1. nue to these many inequality and equalitv constraints, there are many fixe<b points (or extrema of a cri terJon), and thus P determines the final choice of P ·

The first problem, w 0 th thefe methods, is that the influence of P on* P is not well defined: io mav happen that P is located very far from P · More i.mportant 1 y, they do not han­ dle satisfyingly the no-label problem[ 4] which arises when a probabilistic interpretation is not relevant: one would like to allow some units not to have any label at all, mainly because no labeling would be significant for them, still finding a consistent labeling for the others.

We propose here to incorporate a measure of the confidence one may have in the labeling of any unit in a definition of consistency (semi­ consistency) which combines the world model and the observations, as in(1]. For a wide scope of applications, existence, uniqueness and easy com­ putability of a semi-consistent labeling may easily be proved.

IT DF:FINITION AND INTERPRETATION OF S~MI-CONSISTENCY ---

We define consistency as the inner product

between the labelin~ P and a compatibility vector

r. cand cJ'-'1) convenJ;ntly expressed hy: r(l() = A X where A rlenotes a d-wav matr i x (an entrv ~d)~ has d indices varving: r~om 1 to v), and X d occurrences or X. Tt can be proved then that r.(X) can always be exoressed hy[F,l

where Bd-l denotes a (d-1)-way matrix, and denotes the inner ororluct. This .iusti ries the equivalence mentioned earlier between svmmetric consistency and consistencv derined hy the inner product.

rl Actually, A may be applied to d different vectors x 1 , ·· , X · Thus r; meiy be p:eneralized also to these d di~rerent vectors.

d-1 Similarl y, B may be ~enera 1 ized to rl-1 d ifferent vectors exactly in the same way. A nice prooert~-~s that it is always possible in (4) to chose B such that the following property holds

ror any X 1 , ·· , Xd, and any permutation o- of the indices. The prooerty expresserl in (6) is merelv a P:eneralization of symmetry to d-wav matrices.

A. r.eneral r.onditl.ons for a Maximum

Let Sn denote the unit sphere of i.e. the set or X's such that: ~ = norder n, Jxl.l = 1 Let Ik h~ t\¥ k-w.,l unit operaior (~k), i.e.: ~i (I X )l. = xi.

tors of (~i: n* Let S be the (lli: xi > 0). non-negative xi > 0 :1 i: x . n suhsetn~f s of positive vecn Let S be the subset of S - 1 non-oositi.ve = O). vectors

ObviouslY, th~+ ~~;lobal maximum on Sn is reached for X inns · Besides, a necessary con­ dition for X in S to be an extremum is that the n ghadient of C at X bfi_ roftll~l) to S · A normal to s at X is p:iven by I X 'd~~d(~~r) p:radient, using (7), is proportional toR X ·

Thus, the condition is indeed:

B. Conditions negative extrema. for the positivity of non-

R, such that the Rik·s are not linear functions of the p 's in Vik' but more generally any polv­ nomial df- maximum dep:ree d-1. An essent i al dbfference with (1) is that the initial labeling P is incorporated l.n R; for example, usinp: Baye­ sian assumptions as inf1l sup:gests:

with fixed v 1 k"s. In graph match i ng (or Isomor­ phism), the v· k · s themselves are bu i 1 t from the observations. i

Thus, let C(P) be the consistency criterion: C(P) is a polynomial or de~r.ree d, on the N*M variables p k" This definition directly corresponds !o the support function prooosed in[5]. Another way to define a strict l y equivalent (as shown in the next section) con­ sistency is to start from the symmetric con­ sistency as prooosed inf1l.

Classic't} relaxation-optimization methods start from P and search for a local extremum of C meetin~ the constraints of (2). 'tie sug~~;est here to relax these constraints, and to repl ace them by a unique normalization constraint:

That is, we look for the extremum of C(P} on the positive unit sphere of order n.

* Now J-et P be the extremum, anrl lli )i = ~ Pik" ). may be i nterpreted as the conk 1 * fidence attached to P · If i t is small~ then no label is verv l ikeJ.J- for un i t u , wh l ch means that locally consistency is low. 1 On the con­ trary, if ) is large, then one, or may be several labets are hip:hlv cons i stent wl tJl the context, for unit u · Normalizinp: the P. 's bv the )i 's after converkence (and not, this i~ cru­ cial, after every iteration, as it was the case in standard relaxation) yields or course proba­ bility vectors for every ui if needed.

* In the special case where C(P) l.s quadratic, P is an eip:envector of the corresponding sym­ metrized matrix, and cond i tions for the existence, uniqueness, and computability or such a positive vector have been dealt with in[2]. In the ~eneral case considered here, we exhibi t similar conditions for existence and uniqueness of an extremum of c(p) , on a suitable unit sphere of order n, provided n>d, and C is a homo~~;eneous polynomia 1. Detailed proofs of the results p:i ven below are readily available, but beyond the scope of this paper.

III EXISTENCE AND TJNICTTY OF A POSITIVE SEMI-CON~TENT LABF.LTNG

For the sake of clarity, let v=N*M, and:

First of all, if any ent5y 1 in A is strictly positive, then any entry in B is also strictly positive, and

In most applications, this condition is (for­ tunately) not true. But we proved that a suffi­ cient (and easier to meet) condition for any non-negative extremum to be positive is that:

where Z(X) is the number of zero coordinates of X. Goin11; back to the interpretation of label­ ings, the underlyinl!; i.dea is roup;hly that any labelled unit (ui,k) indirectly influences at time any other one ( u , k) , by strinp; effect. It is p;enerally easy to ~et this condition.

C. llniqueness of the maximum.

Let Nn denote the operator li sc'A . n~~: any vector to the vector parallel on S · We proved that, prov.ided (8) holds, and n~d, for any small enoup;h Y:

thus, the only extrema in Sn minima, no saddle-points). are maxima (no

But, for n¥Y X in SnO, we know that the gra­ dient is in S Under these conditions, it can be proved that the existence of severa 1 maxima would involve at least a saddle-point or a minimum, which is not possible.

IV COMPUTATIONAL ASPECT

Classical optimization of a function is per­ formed by gradient or Newton-like methods. These ones work satisfyingly here as the maximum is unique. But it turns out (though we could not phoved ~a~ that replacing at everv step x by N (A X ) provides the fastest convergence. This is equivalent to followin~~; the ~~;radient to infinity before projection, and is a straightfor­ ward generalization of the well-known power method for finding the maximal eigenvector in the linear case.

VI CONCLUSION

The method described in this paper has only been applied so far in the quadratic case, for which uniqueness is much simpler to prove. It has given satisfying results on multispectral image segmentation[3]. Experimental validation in that case comes from the following; observa­ tion: when checkinp;, near convergence, the label­ ings P which are the most stable, i.e. for which t~e order of the p 's change the least ik - ' the ones with the largest confidence values (}i) are found. Moreover, there usually is for these units one label much hi~~;her than the others.