Image and Video Segmentation

A. Eleftheriadis; A. Jacquin

Segmentation plays a crucial role in second-generation image and video coding schemes, as well as in content-based video coding. It is one of the most difficult tasks in image processing, and it often determines the eventual success or failure of a system.

Broadly speaking, segmentation seeks to subdivide images into regions of similar attribute. Some of the most fundamental attributes are luminance, color, and optical flow. They result in a so-called low-level segmentation, because the partitions consist of primitive regions that usually do not have a one-to-one correspondence with physical objects.

Sometimes, images must be divided into physical objects so that each region constitutes a semantically meaningful entity. This higher-level segmentation is generally more difficult, and it requires contextual information or some form of artificial intelligence. Compared to low-level segmentation, far less research has been undertaken in this field.

Both low-level and higher-level segmentation are becoming increasingly important in image and video coding. The level at which the partitioning is carried out depends on the application. So-called second generation coding schemes [1, 2] employ fairly sophisticated source models that take into account the characteristics of the human visual system. Images are first partitioned into regions of similar intensity, color, or motion characteristics. Each region is then separately and efficiently encoded, leading to less artifacts than systems based on the discrete cosine transform (DCT) [3, 4, 5]. The second-generation approach has initiated the development of a significant number of segmentation and coding algorithms [6, 7, 8, 9, 10], which are based on a low-level segmentation.

The new video coding standard MPEG-4 [11, 12], on the other hand, targets more than just large coding gains. To provide new functionalities for future multimedia applications, such as content-based interactivity and content-based scalability, it introduces a content-based representation. Scenes are treated as compositions of several semantically meaningful objects, which are separately encoded and decoded. Obviously, MPEG-4 requires a prior decomposition of the scene into physical objects or so-called video object planes (VOPs). This corresponds to a higher-level partition.

As opposed to the intensity or motion-based segmentation for the second-generation techniques, there does not exist a low-level feature that can be utilized for grouping pixels into semantically meaningful objects. As a consequence, VOP segmentation is generally far more difficult than low-level segmentation. Furthermore, VOP extraction for content-based interactivity functionalities is an unforgiving task. Even small errors in the contour can render a VOP useless for such applications.

This chapter starts with a review of Bayesian inference and Markov random fields (MRFs), which will be needed throughout this chapter. A brief discussion of edge detection is given in Section 1.2, and Section 1.3 deals with low-level still image segmentation. The remaining three sections are devoted to video segmentation. First, an introduction to motion and motion estimation is given in Sections 1.4 and 1.5, before video segmentation techniques are examined in Sections 1.6 and Section 5.1. For a review of VOP segmentation algorithms, we refer the reader to Chapter 5.

1.1 Bayesian Inference and Markov Random Fields

Bayesian inference is among the most popular and powerful tools in image processing and computer vision [13, 14, 15]. The basis of Bayesian techniques is the famous inversion formula

X|O=PO|XPXPO.

Although equation (1.1) is trivial to derive using the axioms of probability theory, it represents a major concept. To understand this better, let X denote an unknown parameter and O an observation that provides some information about X. In the context of decision making, X and O are sometimes referred to as hypothesis and evidence, respectively.

P(X|O) can now be viewed as the likelihood of the unknown parameter X, given the observation O. The inversion formula (1.1) enables us to express P(X|O) in terms of P(O|X) and P(X). In contrast to the posteriorprobability P(X|O), which is normally very difficult to establish, P(O|X) and the prior probability P(X) are intuitively easier to understand and can usually be determined on a theoretical, experimental, or subjective basis [13, 14]. Bayes’ theorem (1.1) can also be seen as an updating of the probability of X from P(X) to P(X|O) after observing the evidence O[14].

1.1.1 MAP Estimation

Undoubtedly, the maximum a posteriori (MAP) estimator is the most important Bayesian tool. It aims at maximizing P(X|O) with respect to X, which is equivalent to maximizing the numerator on the right-hand side of (1.1), because P(O) does not depend on X. Hence, we can write

X|O∝PO|XPX.

For the purpose of a simplified notation, it is often more convenient to minimize the negative logarithm of P(X|O) instead of maximizing P(X|O) directly. However, this has no effect on the outcome of the estimation. The MAP estimate of X is now given by

MAP=argmaxXPO|XPX=argminX–logPO|X–logPX.

From (1.3) it can be seen that the knowledge of two probability functions is required. The likelihood P(X) contains the information that is available a priori, that is, it describes our prior expectation on X before knowing O. While it is often possible to determine P(X) from theoretical or experimental knowledge, subjective experience sometimes plays an important role. As we will see later, Gibbs distributions are by far the most popular choice for P(X) in image processing, which means that X is assumed to be a sample of a Markov random field (MRF).

The conditional probability P(O|X), on the other hand, defines how well X explains the observation O and can therefore be viewed as an observation model. It updates the a priori information contained in P(X) and is often derived from theoretical or experimental knowledge. For example, assume we wanted to recover the unknown original image X from a blurred image O. The probability P(O|X), which describes the degradation process leading to O, could be determined based on theoretical considerations. To this end, a suitable mathematical model for blurring would be needed.

The major conceptual step introduced by Bayesian inference, besides the inversion principle, is to model uncertainty about the unknown parameter Xby probabilities and combining them according to the axioms of probability theory. Indeed, the language of probabilities has proven to be a powerful tool to allow a quantitative treatment of uncertainty that conforms well with human intuition. The resulting distribution P(X|O), after combining prior knowledge and observations, is then the a posteriori belief in X and forms the basis for inferences.

To summarize, by combining P(X) and P(O|X) the MAP estimator incorporates both the a priori information on the unknown parameter X that is available from knowledge and experience and the information brought in by the observation O[16].

Estimation problems are frequently encountered in image processing and computer vision. Applications include image and video segmentation [16, 17, 18, 19], where O represents an image or a video sequence and X is the segmentation label field to be estimated. In image restoration [20, 21, 22], X is the unknown original image we would like to recover and O the degraded image. Bayesian inference is also popular in motion estimation [23, 24, 25, 26], with X denoting the unknown optical flow field and O containing two or more frames of a video sequence. In all these examples, the unknown parameter X is modeled by a random field.

1.1.2 Markov Random Fields (MRFs)

Without doubt the most important statistical signal models in image processing and computer vision are based on Markov processes [27, 20, 28, 29]. Due to their ability to represent the...