Home | About | Journals | Submit | Contact Us | Français |

**|**HHS Author Manuscripts**|**PMC2995284

Formats

Article sections

- Abstract
- 1. Introduction
- 2. Spatial Patterns of Shapes
- 3. Graph Energies
- 4. Global Priors on Object Features
- 5. Summary
- References

Authors

Related links

Proc Int Conf Image Proc. Author manuscript; available in PMC 2010 December 1.

Published in final edited form as:

Proc Int Conf Image Proc. 2008 December 12; 2008: 1144–1147.

doi: 10.1109/ICIP.2008.4711962PMCID: PMC2995284

NIHMSID: NIHMS245082

Anuj Srivastava, Department of Statistics, Florida State University, Tallahassee, FL 32306;

We introduce a framework for modeling spatial patterns of shapes formed by multiple objects in an image. Our approach is graph-based where each node denotes an object and attributes of a node consist of that object's shape, position, orientation, and scale. Neighboring node are connected by edges, and they are allowed to interact in terms of their attributes/features. Similar to a Markov random field, but now applied to more sophisticated features space, the interactions are governed by energy functionals that can be internal or external. The internal energies, composed entirely of interactions between nodes, may include similarity between shapes and pose. The external energies, composed of outside influences, may include the data-likelihood term and the a-priori information about the shapes and the locations of the objects.

Although advanced geometrical tools have been derived for studying shapes of individual objects, models for studying collections or spatial configurations of shapes (in the same image) are lacking. We are interested in building models for describing configurations of objects in an image, where the objects are represented by contours of their boundaries. As a motivation, consider the problem of analyzing a city terrain, a building footprint, or a forest region, using a satellite or an aerial image. We anticipate objects of interest, such as roads, buildings, trees, and lakes, to occur more often in certain configurations. It is reasonable to expect similar objects to occur together, with positions and orientations that are defined relative to each other (see some examples in Figure 1).

What type of models can be used for analyzing such configurations of objects? Two questions are pertinent: How do we represent the variables of interest in a configuration, and what kinds of probability models capture the observed variability? We argue that a convenient approach is to extend ideas from classical *stochastic geometry* where one studies placements and interactions of simple objects as points, lines, and circles [1]. There is a significant literature on modeling occurrences of points, labeled or otherwise, in a certain region, e.g. a Strauss process or an area interaction process [2]. In applications to image analysis, Perrin et al. [3] have modeled locations of simple geometries (ellipses) in aerial images using Marked point processes. We are interested in studying more sophisticated objects, such as trees, airplanes or petals, and we associate more elaborate “features”, such as a shape, an orientation, and a scale, to each object. Furthermore, the model we seek shall allow interaction of these features, in addition to the locations, of neighboring objects. Similar to stochastic geometry, we use a graph-theoretic approach where each node denotes an object present in the plane. The attributes of the nodes are set to be the features associated with the objects: their shapes, position, scale, and orientations. The main difference from classical stochastic geometry is that rather than having Euclidean vectors for features, we have shapes of planar, closed curves that are elements of infinite-dimensional shape manifolds.

We are interested in statistically modeling patterns of objects present in an image, with a focus on their shapes, locations, and pose. The main hypothesis in our model is that objects that are close to each other, location wise or shape wise, interact with each other according to their features. To keep track of such interactions, we propose a graph theoretical representation which is described next.

In this representation, a collection of objects is represented by a graph where each object denotes a node on this graph. Objects that interact with each other are connected through edges; others are not. There are several possibilities to decide this interaction. One possibility is to use **partially-connected graphs**: In this case each node, or object, interacts only with its nearest neighbors. Together the nodes and the edges form a connected graph which can be analyzed using standard Markovian framework. For a given connectivity, the nodes can be interpreted as a Markov random field (MRF) (assuming that the number of objects is fixed). One can generate inferences for the whole graph using univariate conditional densities i.e. the Gibbs' sampler. The other possibility is to divide graph into **disjoint clusters**. This is a convenient when objects naturally divide themselves into smaller clusters and there is minimal interaction between elements across clusters. In this paper we have selected the cluster graphs as mechanisms for interactions between objects.

We want to extend the classical notion of spatial processes, that models only the random locations of points, by including shapes and pose as additional features. Shapes of simple closed curves have been studied rigorously in recent years by Klassen, Srivastava, Michor, Mio, their co-authors and several others. We choose the latest of these ideas presented in [4] although any of the other techniques can also be used.

Associated with each object, denoted by its contour *β*, are the following physical features. (i) **Length**: The length of *β* is denoted by *ρ* _{+}. (ii) **Position**: To represent the location of an object in an image, let the center of the curve,
$\frac{1}{2\pi}{\int}_{0}^{2\pi}\beta (t)dt$, be located at *p* ^{2}. (iii) **Orientation**: The average orientation of (*t*) with respect to the positive *x* axis is called the orientation of *β*; we will denote it by *τ*. Lastly, (iv) **Shape**: For a closed curve *β*, we are interested in mathematical representations that enable a study of its shape. As described in [4], we will represent each curve by its square-root velocity function
$q(t)=\frac{\dot{\beta}(t)}{\sqrt{\left|\dot{\beta}(t)\right|}}$ and let be the set of all closed curves represented by their *q* functions. Several elements in can denote the same shape due to different parameterizations and rotations of *β*. Thus, to obtain a unique representation of shape, one defines the shape space as the quotient space /(Γ × *SO*(2)), where Γ is the set of all reparameterizations of a unit length curve. An important tool in shape analysis is to construct geodesics between elements of shape space, to compare and analyze shapes [4]. For later purposes, let *ψ _{t}*(

In order to develop statistical models for capturing desired configurations of objects, we will define probability densities of the type
$\pi =\frac{1}{Z}{e}^{-E}$, where *E* will be the configuration energy defined according to the application and *Z* is a normalization constant. This is a density defined with respect to the Poisson measure on the image domain. Our model uses two types of energies: internal and external. Internal energies are used to model interactions between the nodes, while external energies are used to incorporate outside information, such as that from image data or a prior on some feature, in the model. In this section, we give some examples and study low-energy (or high probability) configurations.

Here we define energies associated with objects within individual clusters and demonstrate their role using gradients to update configurations. Let *C* denote a cluster consisting of *n* nodes (objects), each having an associated shape *q*, position *p*, orientation *τ*, and scale *ρ*. We propose a cluster energy to be:

$${E}^{w}(C)={E}_{s}^{w}({q}_{1},\dots ,{q}_{n}))+{E}_{p}^{w}({p}_{1},\dots ,{p}_{n})+{E}_{sc}^{w}({\rho}_{1},\dots ,{\rho}_{n})+{E}_{r}^{w}({\tau}_{1},\dots ,{\tau}_{n})+{E}_{o}^{w}(C),$$

(1)

where the superscript *w* underscores that these energies capture interactions within a cluster. Next we suggest some ideas for these individual terms although different applications will have different requirements.

We can set
${E}_{s}^{w}$ to be the variance associated with the shapes in that cluster. Another possibility, that is computationally more efficient, is to include only pairwise interactions between shapes. This can be accomplished using:
${E}_{s}^{w}=\frac{1}{n}{\sum}_{i,j\ne i}{d}_{s}{({q}_{i},{q}_{j})}^{2}$, where *d _{s}* denotes the geodesic distance in . The gradient of

We may emphasize the objects in a cluster are located as close to each other as possible, and a simple form of
${E}_{p}^{w}$ that does that is trace(var({*p*_{1}, …, *p _{n}*})). Note that this term does not include any overlap penalty between objects which is studied by a separate term.

We may choose to force similar sizes of objects with in the same cluster by choosing the energy ${E}_{sc}^{w}=var({\rho}_{1},\dots ,{\rho}_{n})$.

Seeking a rotational alignment of objects in a cluster we may set
${E}_{r}^{w}={\text{argmin}}_{\tau {\mathbb{\text{S}}}^{1}}$, where *τ _{i}*s are the individual orientations and

We use
${E}_{o}^{w}$ to penalize the amount of overlap between the regions occupied by objects. Let *R _{β}*

We present some examples of energy minimization using a combination of these energies. In Figure 3 we present an evolution using ${E}_{p}^{w}+{E}_{o}^{w}+{E}_{sc}^{w}+{E}_{r}^{w}$, while keeping the shapes fixed. In view of our choices for these energies, it is easy to understand the alignment of similar objects in placements, scales, and orientations.

Evolution of clusters according to gradient of
${E}_{p}^{w}+{E}_{o}^{w}+{E}_{sc}^{w}+{E}_{r}^{w}$, and the bottom right show the corresponding changes in the total energy.

We will denote all the interactions within the same cluster by *E ^{w}*, i.e.
${E}^{w}={E}_{p}^{w}+{E}_{s}^{w}+{E}_{sc}^{w}+{E}_{r}^{w}+{E}_{o}^{w}$.

The next level of interaction between objects can occur across clusters. For example, it may be useful to penalize the amount of regional overlap between any two clusters. Or, perhaps we may want to rotationally align two clusters. Mathematically, one way we can formulate this problem is by defining terms similar to the previous section but using averages values of location, shapes, scales, and orientations from each cluster.

An important strength of this framework is to be able to drive shape configurations using energies beyond simple interactions. We will call them *external energies*. One source of external energies is the prior knowledge that may favor a certain placements, orientations, or scalings of objects. Or, it may prefer a certain shapes of objects in given contexts. For example, an aerial view of an urban environment will favor cars and buildings while that of a rural environment will favor farms, plantations and forests. We introduce external energies terms to enforce such considerations: (i) **Spatial Intensities for Object Placement**: The locations of objects may be governed by a spatial process with an underlying intensity function *λ*(*p*). Densities of objects in a region will therefore be dictated by the values of *λ* in that region. This factor contributes to the energy term as:
${E}_{p}^{g}=({p}_{1},\dots )=-{\sum}_{i}log(\lambda ({p}_{i}))$. Shown in Figure 4 is an example of changing object positions using the gradient of
${E}_{p}^{g}$, for an arbitrary chosen *λ*. The level curves of the function *λ* are also shown. This procedure requires computing the gradient
${p}_{{E}_{p}^{g}}$; we compute it using a numerical technique that involves computing log(*λ*) at points that are not on the grid, and we use bilinear interpolation. To demonstrate the role of
${E}_{p}^{g}$ in a larger system, Figure 5 shows the evolution of a configuration according to gradient of
${E}^{w}+{E}_{p}^{g}$. (ii) **Preferred Rotational Alignment**: In some cases it is possible to have preferred orientation for objects present in the scene. For example, in images of humans walking on a road their contours are, with high probability, aligned vertically. (iii) **Preferred Shape As A Prior**: In case we are looking for objects of a specific shape class in an image, we can use a prior model on the shapes extracted from that image. One prior energy is to simply use
${E}_{s}^{g}({q}_{1},\dots ,{q}_{n})={\sum}_{i=1}^{n}{d}_{s}{({q}_{i},\mu )}^{2}$, where *μ* is the mean shape under the prior.

Evolution of positions, initialized randomly, following the gradient of
${E}_{p}^{g}$. The level curves of log(*λ*) are drawn to help understand this evolution. The converging positions are the final locations of points.

Using the energies defined above, we can demonstrate some low-energy configurations. Shown in Figure 6 are two examples of evolution of objects according to an appropriate energy term. For instance, in the first case we use
${E}_{p}^{w}+{E}_{o}^{w}+{E}_{sc}^{w}-{E}_{r}^{w}+{E}_{s}^{g}$. Note the
$-{E}_{r}^{w}$ is being used to maximally separate the orientations. We have used a petal shape as *μ* in the global shape prior
${E}_{s}^{g}$ to generate the flower configuration.

We have described a stochastic model for studying spatial patterns of multiple objects in an image, with regards to their shapes and other variables. Using a graph-theoretic framework, the objects configurations are governed by Gibbsian energies. Internal energies model interactions between the objects while external energies incorporate data likelihood and global priors.

^{*}This research was also supported in part by the grants ARO W911NF-04-1-0268, ARO W911NF-04-1-0113, and AFOSR FA9550-06-10324.

Anuj Srivastava, Department of Statistics, Florida State University, Tallahassee, FL 32306.

Wei Liu, Department of Statistics, Florida State University, Tallahassee, FL 32306.

Shantanu H. Joshi, Laboratory of Neuro-Imaging, UCLA School of Medicine, Los Angeles, CA 90095.

1. Stoyan D, Kendall WS, Mecke J. Stochastic Geometry and Its Applications. 2nd. John Wiley & Sons; 1995.

2. Baddeley AJ, Van Lieshout MNM. Area interaction point processes. Annals of Inst of Stat Math. 1995;47:601–619.

3. Perrin G, Descombes X, Zerubia J. ICIP. Genova, Italy: Sep, 2005. A marked point process model for tree crown extraction in plantations.

4. Joshi SH, Klassen E, Srivastava A, Jermyn IH. A novel representation for Riemannian analysis of elastic curves in *R*^{n}. IEEE CVPR. 2007 [PMC free article] [PubMed]

PubMed Central Canada is a service of the Canadian Institutes of Health Research (CIHR) working in partnership with the National Research Council's national science library in cooperation with the National Center for Biotechnology Information at the U.S. National Library of Medicine(NCBI/NLM). It includes content provided to the PubMed Central International archive by participating publishers. |