Search tips
Search criteria 


Logo of nihpaAbout Author manuscriptsSubmit a manuscriptHHS Public Access; Author Manuscript; Accepted for publication in peer reviewed journal;
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.4711962
PMCID: PMC2995284

Modeling Spatial Patterns of Shapes*


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.

Index Terms: configurations of shapes, spatial shape interaction

1. Introduction

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).

Fig. 1
Images displaying natural or man-made interactions of shapes leading to predictable patterns.

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.

2. Spatial Patterns of Shapes

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.

2.1. A Graph-Theoretic Representation

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.

2.2. Node Attributes

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 ρ [set membership] R+. (ii) Position: To represent the location of an object in an image, let the center of the curve, 12π02πβ(t)dt, be located at p [set membership] R2. (iii) Orientation: The average orientation of [beta with dot above](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)=β˙(t)|β˙(t)| and let An external file that holds a picture, illustration, etc.
Object name is nihms245082ig1.jpg be the set of all closed curves represented by their q functions. Several elements in An external file that holds a picture, illustration, etc.
Object name is nihms245082ig1.jpg 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 An external file that holds a picture, illustration, etc.
Object name is nihms245082ig2.jpg as the quotient space An external file that holds a picture, illustration, etc.
Object name is nihms245082ig1.jpg/(Γ × 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(q,v) denote a geodesic path, parameterized by time t, starting from q [set membership] An external file that holds a picture, illustration, etc.
Object name is nihms245082ig2.jpg in the direction v [set membership] Tq(An external file that holds a picture, illustration, etc.
Object name is nihms245082ig2.jpg). Tq(An external file that holds a picture, illustration, etc.
Object name is nihms245082ig2.jpg) is the tangent space at q. In summary, the attribute of a node is a quadruple (ρ, p, τ, q) [set membership] R+ × R2 × SO(2) × An external file that holds a picture, illustration, etc.
Object name is nihms245082ig2.jpg.

3. Graph Energies

In order to develop statistical models for capturing desired configurations of objects, we will define probability densities of the type π=1ZeE, 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.

3.1. Interaction Within Clusters

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:


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.

1. Shape Term

We can set Esw 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: Esw=1ni,jids(qi,qj)2, where ds denotes the geodesic distance in An external file that holds a picture, illustration, etc.
Object name is nihms245082ig2.jpg. The gradient of Es with respect to a shape qi is simply 1njvij where vij is the tangent vector at qi such that ψ1(qi, vij) = qj. (Recall that ψt is the notation for a geodesic path on the shape space An external file that holds a picture, illustration, etc.
Object name is nihms245082ig2.jpg.) Figure 2 uses some examples to demonstrate this idea, where single object evolves under the influence of its neighbors using the term Esw while the shapes of the neighbors are held fixed. Also, other parameters such as scale, positions, and orientation are held constant.

Fig. 2
Three examples where the object of focus changes its shape under the influence of its neighbors using Esw.

2. Position Term

We may emphasize the objects in a cluster are located as close to each other as possible, and a simple form of Epw that does that is trace(var({p1, …, pn})). Note that this term does not include any overlap penalty between objects which is studied by a separate term.

3. Scale Term

We may choose to force similar sizes of objects with in the same cluster by choosing the energy Escw=var(ρ1,,ρn).

4. Rotation Term

Seeking a rotational alignment of objects in a cluster we may set Erw=argminτ[set membership]S11=ndc(τ,τi)2, where τis are the individual orientations and dc denotes the shorter arc-length between two points on An external file that holds a picture, illustration, etc.
Object name is nihms245082ig3.jpg1. This term denotes the variance of orientation angles in An external file that holds a picture, illustration, etc.
Object name is nihms245082ig3.jpg1, and will force similar orientations of objects in a cluster. In case where exactly the opposite is preferred we can use Erw.

5. Overlap Term

We use Eow to penalize the amount of overlap between the regions occupied by objects. Let Rβ [subset or is implied by] R2 denote the region occupied by the curve β, then Eow(C)=[union or logical sum]i,j(|RβiRβj|), where | · | denotes the area of a set.

We present some examples of energy minimization using a combination of these energies. In Figure 3 we present an evolution using Epw+Eow+Escw+Erw, 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.

Fig. 3
Evolution of clusters according to gradient of Epw+Eow+Escw+Erw, and the bottom right show the corresponding changes in the total energy.

We will denote all the interactions within the same cluster by Ew, i.e. Ew=Epw+Esw+Escw+Erw+Eow.

3.2. Interaction Across Clusters

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.

4. Global Priors on Object Features

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: Epg=(p1,)=ilog(λ(pi)). Shown in Figure 4 is an example of changing object positions using the gradient of Epg, for an arbitrary chosen λ. The level curves of the function λ are also shown. This procedure requires computing the gradient [nabla]pEpg; 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 Epg in a larger system, Figure 5 shows the evolution of a configuration according to gradient of Ew+Epg. (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 Esg(q1,,qn)=i=1nds(qi,μ)2, where μ is the mean shape under the prior.

Fig. 4
Evolution of positions, initialized randomly, following the gradient of Epg. The level curves of log(λ) are drawn to help understand this evolution. The converging positions are the final locations of points.
Fig. 5
Evolution of clusters according to gradient of Ew+Epg.

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 Epw+Eow+EscwErw+Esg. Note the Erw is being used to maximally separate the orientations. We have used a petal shape as μ in the global shape prior Esg to generate the flower configuration.

Fig. 6
In each case the top left shows an image of a configuration that we want to model, the next panel shows the prior means μ, and the remaining panels show evolution of a random configuration under specifically designed energies.

5. Summary

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.

Contributor Information

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 Rn. IEEE CVPR. 2007 [PMC free article] [PubMed]