Probabilistic Information Fusion for Multi-Modal Image Segmentation

1. A Probabilistic View of the SeiJDentation Problem

Represent an image aa a set of primitive elements S {st. ss, .. . , sN}. A segmentation w of the image with respect to a label set L = {11, 11, . .. , lq} ia a mapping from S to L. Let w; = w(s;) EL represent the label attached to I; in segmentation w. Let 0 be the set of all segmentations. The image segmenta­ tion problem with respect to L can be loosely described aa to find the w E 0 that "beat fits" the information collected subject to the limitation . of the computational resources. This section describes the uses of probability as the representation for vari­ ous kinds of information and the corresponding criteria for finding the "beat fit".

It is frequently desirable to organize segmentation labels aa a hierarchical tree (Figure 1). Each internal node in a tree of labela represents the disjunction of ita aona. Each cross-section is ~ mutually exclusive and exhaustive label set; i.e., a segmen­ tation problem can be defined with respect to a cross-section in a label tree. Using such a tree, we can represent a particular piece of knowledge about the labels at whatever level of abstrac­ tion that is appropriate. We use L to denote a set of mutually exclusive and exhaustive set of labels in a label tree H.

P ·primitive element, E ·edge, R · repon, PE- photometrical edge, GE . geometrical edge, PR · photometrical region, GR - geometrical region, TE- texture edge, HE -highlight edge, SE- alwlow edge, OE - orientation edge, DE -depth edge, HI- hishlight region, SH - alwlow "'gion, PL- planar region, SP- spherical region.

*This work was supported by the Air Force Systems Com­ mand, Rome Air Development Center, Grifliaa Air Force Base, New York 13441-5700, and the Air Force Ofti.ce of Scientific Research, Bolling AFB, DC 20332 under Contract No. F3060285-C-0008. This contract supports the Northeast Artificial Intel­ ligence Consortium (NAIC). This work was also supported by the U.S. Army Engineering Topographic Laboratories under Contract No. DACA 76-85-C-0001.

1.3. Posterior Probability and Bayesian Estimation

Following the Bayesian formalism, the goodness of a seg­ mentation can be evaluated in terms of its a posteriori expected loss,

where the P(fiOl denotes the posterior probability off given the observation 0 . Bayes' rule can then be used to derive the a pos­ teriori probability

From (1.1), observe that scaling all P<O, IO by a constant factor for fixed s does not change the posterior distribution in (1.3). This fact allows us to combine the likelihoods without having to normalize the results.

The choice for the loss function depends on the characteris­ tics of a particular application. In [Geman and Geman 84], the Maximum A Posteriori (MAP) estimation is used. A simulated annealing procedure with a stochastic sampler (Gibbs sampler) carries out the computation. In [Marroquin et al 85], the Max­ imizer of the Posterior Marginals (MPM) estimation is proposed. This approach, computing the a posteriori probabilities for the segmentations given the set of opinions from the early modules and the a priori probability distribution, can support both the MAP and MPM estimation methods as well as other Bayesian estimations.

2. Markov Random Fields

Markov Random Fields have been used for image modeling in many applications for the past few years [Geman and Geman 84] [Marroquin et al 85] [Derin and Cole 86]. One of the most successful applications of MRFs is to model the spatial interac­ tions of image features. In this section, we review the properties of MRFs and describe how to encode prior knowledge in this for­ malism.

2.1. Definition

Let X = {X, 8ES} be a set of random variables indexed by S and E a set of unordered 2-tuple (s., Sj)'s representing the con­ nections between the elements in S. The set E defines a neigh­ borhood system N = {N,IsES}, where N, is the neighborhood of 8 in the sense that

1. s fN,, and

Let w = {X, = w,,sES} be a configuration of X, w, EL, and 0 the set of all possible configurations. We say X is a Markov Random Field with respect toN and P , where Pis a probability function, if and only if

The conditional probabilities in the right-hand side of (2.2) are called the local characteristics that characterize the random field. An intuitive interpretation of (2.2) is that the contextual information provided by S- s to s is the same as the information provided by the neighbors of s. Thus the effects of members of the field upon each other is limited to local interaction as defined by the neighborhood. A very desirable property of MRFs that makes them attractive to scientists in many disciplines is the MRF-Gibbs equivalence described in the following theorem.

2.2. MRF-Gibbs Equivalence

Hammersley-Clifford Theorem: A random field X is an MRF with respect to the neighborhood system N if and only if there exists a function V such that

where

C is the set of totally connected subgraphs (cliques) with respect toN. Z is a normalizing constant, so that the probabilities of all realizations sum to one.

Several terminologies from Physics can provide intuition about the Gibbs measure - the right-hand side of (2.3). T is the temperature of the field that controls the ll.atness of the distribu­ tion of the configurations. A potential V is a way to assign a number V.(w) to every subconfiguration We of a configuration w, where cEC. U(w), the sum of the local potentials, is the energy of the configuration w . A system is in thermal equilibri~m when the probabilities of its configurations follows the Gibbs measure.

2.3. Encoding Prior Knowledge

For the image segmentation problem, we must choose an appropriate neighborhood system and a potential function for the random field X over the image S to represent prior knowledge about the image. The neighborhoods should be large enough to capture the interactions between the primitive elements but still small enough for a machine to carry out the computations required to make an estimation. The higher the energy measure of a configuration, the less likely it is to Occur.

3. Combining Opinions of Early Visual Modules

Most research on evidence combination has focused on updating the "belief' in a given hypothesis about an individual element when a piece of new evidence becomes available [Pearl 86]. This approach, however, is not suitable for our purpose. We believe that an information fusion mechanism should constantly maintain a representation of knowledge to rell.ect the total infor­ mation available, except possibly for transient periOds of time for aggregating evidence locally. Maintaining "marginal belief' requires the effects of updating local ''belief' to be spatially pro­ pagated, thus violating such a requirement.

In this section, we limit our attention to an individual ele­ ment 8 of S. We show how the opinions about s can be combined and provide the probabilistic justification for the proposed method. In Section 4 we show how the updating of this joint probability distribution given a new set of opinions about a set of primitive elements can be carried out with simple. operations.

3.1. Representations and Combination Rules

As in Pearl's construction [Pearl S6], we assume the seg­ mentation labels can be organized as a hierarchical tree H (e.g. Figure 1). Node l denotes the hypothesis that the corresponding primitive element is of label l, i.e., X, = l. The numbers main­ tained in our method indicate the degrees of hypothesis confirmation or disconfirmation provided by the collected evi­ dence.

Let ac denote the current degree of confirmation/ disconfirmation for node l . The probabilistic interpretations for the a's will be given in Section 3.2. Initially, ac is set to unity for every l indicating "neither confirmed nor disconfirmed". Besides a, each internal node l keeps one value, wf, for each son i. Initially, wf is set to the a priori probability of i given l. Obviously, the wf's of each node sum up to unity initially.

Suppose a module A reports ita opinion as a set of likeli­ hood ratios {AfllELA} where LA is a set of mutually exclusive labels contained in H as described in Section 1.2. The corresponding a's are updated according to the rule:

To maintain the coherence of the a's, the effect of this opinion has to be propagated throughout the label tree by the following process:

1. Every node l,lELA, sends a message, m=Af, to ita father and each of ita sons.
2. Any node II that receives a message m from ita father, passes m to all its sons and replaces a 4 by m a4 , that is,

1. Any node j that receives a message m from one of its sons (say i), updates w{ by mw{, i.e.,

and sends a mesaage m' to its father, where

then updates a 1 and all the wi·a according to

where the summation in (3.4) is taken over all the sons of j.

The combination and propagation procedures are commuta­ tive and associative, so their order is irrelevant.

3.2. Probabllistic Justification

The above method fits in the Bayesian formalism if we maintain two notions of conditional independence. First, evi­ dence OA that bears directly on a label l says nothing about the descendants of l:

Second, the observations of different modules are conditionally independent.

where the product on the right-hand side is over a set of modules and 0 is the union of their observation 0A's.

As suggested by Pearl, (3.6) states that when the observa­ tion oA is a unique property of l, common to all its descendants, once we know l is true/false, the identity of l; or 11 does not make oA more or leas likely. (3.7), implicitly used in Pearl's scheme, states that each piece of evidence observed by the early modules provides independent information about a label. We believe that the disparate types of image clues in vision applica­ tions satisfy this assumption.

We define consistent states of a's as the states in which for each available opinion, all of the a 's are either updated accord­ ing to rules (3.1) - (3.5), or none of the a's have been changed with respect to this opinion. We say that a set of opinions derives a consistent state if all opinions in this set, and no other opin­ ions, have been used to update the a's. The following theorem relates the a's to the likelihood probabilities at consistent states.

Theorem 1 [Chou and Brown 87]: Let a[ denote the a value for l at the consistent state t, and P(01jl) be the probability of 01 given the label l, where 01 denotes the union of those observations that form the set of opinions that derives the state t . If01oe0, then

where c1 is a constant depending only on t , given (3.6) and (3.7). Applying Theorem 1 and Bayes' rule, we have:

Corollary 1: Let al denote the a value for l at the con­ sistent state t . If P 0 is the prior p.d.f. of a set of mutually exclusive and exhaustive labels L, then the posterior probability P1(l) of l EL at the consistent state t is

To summarize: We have developed an evidence combination method for a hierarchy of hypotheses baaed on the notions of conditional independence given by (3.6) and (3.7). This .IICheme, besides having all the characteristics listed in [Pearl, 86], has the following advantages:

1. The computations involved are extremely simple. Simpler and fewer messages must be passed. Normalizations are never needed since relative degrees of confirmationldisconfirmation are maintained instead of pro­ babilities (Theorem 1).
2. This scheme decouples the notion of evidence and a priori belief. In the next section we show this characteristic is very helpful when the prior knowledge is represented as an MRF.

4. Combining Prior Knowledge wi&h Observations

In this section, we move our attention to the relationships of segments of the image S. Recall that in the last section, each primitive element is associated with a set of a's to maintain the opinions of the early visual modules. Let fJ, denote the set of a's associated with sES, and fJ,(l) be the a value for label l in fJ,. Define a global consistent state to be a state of the fJ'a at which each fJ, is in a consistent state.

Assume that the prior knowledge about the image is represented as an MRF X over S, X, E L - a mutually exclusive and exhaustive label set in H, with respect to a neighborhood system N. (1.1), Theorem 1, Bayes rule, and the Hammersley­ Clifford Theorem lead to the conclusion that the a posteriori Gibbs measure of a configuration w at a global consistent state t is

Only simple local operations are needed to update the energy measure and local characteristics as new opinions from the early visual modules become available. Therefore, MAP and MPM estimations can easily be implemented in the proposed framework (Section 5). We believe that baaed on this property, novel estimation algorithms can ultimately be designed that incrementally improve their estimations as more and more infor­ mation arrives. For now, the existing Bayesian estimation methods can be invoked at any global consistent state to provide the up-to-date estimations.

5. Experimental Results

We demonstrate the method using two images of overlap­ ping rectangular patches (Fig 2a, 3a). Each patch in the first image corresponds to a geometrically identical patch in the second. The intensities of the patches in each image are ran­ domly selected from the range [0, 255], with no intensity correla­ tion between images. Gaussian zero mean noise is added, with standard deviation 16 and 12 respectively. These two images can be considered as two different sources of information about the same set of rectangular objects.

A set of likelihood edge detectors, an early version of the detectors described in [Sher 86] , provides a set of likelihood ratios- {:c~~~~)li=1 ,2,3 ,4}- for each pixel given the 3X3 win­ dow of intensities centered at it, where NE denotes the hypothesis that the given pixel is not an edge element, and E; denotes the hypothesis that the given pixel is an edge of one of the four (horizontal, vertical, and two diagonal) orientations. The likelihoods are computed using a model for step edges and a Gaussian model for additive noise. Figure 2.b and 3.b show the Maximum Likelihood Estimation (MLE) for edges in Figure 2.a and 3.a respectively. That is, a pixel s is on if and only if mu /1,(1) > fJ ,(NE) . I

We use a homogeneous and isotropic MRF with a third order neighborhood system over the image lattice to encode a body of basic knowledge about edges. Cliques of size 3 are used to discourage parallel and competing edges, whereas cliques of size 2 are used to encourage line continuations, region homo­ geneity and to discourage breaks in the line forming process. The potential assignments for the cliques are chosen conserva­ tively in the sense that estimation methods based on (4.1) make as few false detections of edges as possible while maintaining reasonable detectability.

A software package has been implemented to study the behavior of various estimation criteria and schemes [Chou and Raman 87]. Here we show the results of using this package to perform MPM estimations based on the Monte Carlo procedure proposed in [Marroquin et al 85]. Figure 2.c and 3.c show the MPM estimations based on the statistics collected over 300 itera­ tions. Considering Figures 2.a and 3.a to provide only partial evidence to support the NE and E;'s hypotheses, Figure 4.a and 4.b show the MLE and the MPM estimations resulting from applying the upward propagation rule (3.3)-(3.5). Here the ini­ tial w0 = 0.75.

Alternatively we can consider that Figure 2.a and 3.a independently support the same set of hypotheses. By applying rule (3.1), we obtain Figure 5.a and 5.b representing the MLE and the MPM estimations based on the combined information. Observe the lines detected in the lower left quadrant of Figure 5.b that do not show up in either of Figure 2.c and 3.c, and the false detections in Figure 2.c and 3.c that are removed in Figure 5.b. These sorts of results can not be achieved by multi-modal segmenter& that rely on .Boolean operations to combine evidence.

6. Future Research

We are currently improving the MRF model to handle curved lines. One of our ultimate goals is to encode all kinds of geometrical and photometrical constraints in terms of local clique potentials in an MRF that has general connectivity. The stochastic estimation methods are computationally very expen­ sive. We are now designing a deterministic estimation algo­ rithm that incremently improves its estimation as new evidence arrives. We believe this method of information fusion can be applied to problems other than image segmentation as well.

Acknowledgements

We would like to thank Dave Sher for providing his likeli­ hood edge detectors, Rajeev Raman for designing and imple­ menting software for the experiments, and Henry Kyburg for providing many valuable suggestions.