Probabilistic Models for Labeling Problems

Rui Shen


Many problems in image processing and analysis can be interpreted as labeling problems, which aim to find the optimal mapping from a set of sites to a set of labels. A site represents a certain primitive, such as a pixel, while a label represents a certain quantity, such as disparity in stereo correspondence. Considering this labeling interpretation, instead of solving different problems individually, a series of unified frameworks for labeling problems are introduced here.

Generalized Random Walks

In this Generalized Random Walks (GRW) model [3][4], we formulate a labeling problem from Markov chain random walk point of view, where probabilities are considered as transition probabilities of a random walker moving between nodes: When an image and labels are represented as a weighted graph, where a node/site can be either a pixel or a label, the weight associated with an edge (after normalization by the degree of an incident node) represents the probability that a random walker transits from one incident node/site to the other incident node/site in a single move. To emphasize similarity, as well as differences, to Markov random field model, we refer to the functions defining the edge weights as compatibility functions. This formulation allows compatibility functions to be defined in any form according to the need of a particular problem. In addition, it allows the inclusion of label nodes and pre-labeled scene nodes to be represented naturally in the current framework without altering the structure of the graph, i.e., the whole graph can still be represneted as a single Laplacian. GRW was applied to image fusion and stereo matching.

Multivariate Gaussian Conditional Random Field

In this Multivariate Gaussian Conditional Random Field (MGCRF) model [1][4], we show that GRW is a special case of the proposed MGCRF when the boundary condition is defined in a specific form and the precision matrix is an identity matrix. MGCRF considers random vectors (rather than random variables) defined on each node in a graph.

Hierarchical Random Walks and Hierarchical Multivariate Gaussian Conditional Random Field

These two models are hierarchical versions of GRW and MGCRF, respectively [1][4]. The basic idea is to accelerate the computation by constructing a hierarchy of fine-to-coarse graphs and using the result from a coarser graph to initiate the calculation on a finer graph.

Multiscale Random Walks

This is a multiscale version of GRW [2][4]. The objective is also to accelerate the computation. However, different from hierarchical random walks (HRW), multiscale random walks (MRW) constructs a fine-to-coarse hierarchy of the input data instead of a hierarchy of the graph. MRW was applied to form a cross-scale fusion rule for image fusion that can significantly enhance fusion quality even with simple multiscale decomposition methods.

Related Publications

[1]. Rui Shen, Irene Cheng, and Anup Basu. QoE-Based Multi-Exposure Fusion in Hierarchical Multivariate Gaussian CRF. IEEE Transactions on Image Processing, vol. 22, no. 6, pages 2469-2478, 2013. [MGCRF and HMGCRF and their application][Image Fusion Page]

[2]. Rui Shen, Irene Cheng, and Anup Basu. Cross-Scale Coefficient Selection for Volumetric Medical Image Fusion. IEEE Transactions on BioMedical Engineering, vol. 60, no. 4, pages 1069-1079, 2013. [MRW and its application][Image Fusion Page]

[3]. Rui Shen, Irene Cheng, Jianbo Shi, and Anup Basu. Generalized Random Walks for Fusion of Multi-Exposure Images. IEEE Transactions on Image Processing, vol. 20, no. 12, pages 3634-3646, 2011. [GRW and its application][Image Fusion Page][TIP11 Page]

[4]. Rui Shen. Probabilistic Methods for Discrete Labeling Problems in Digital Image Processing and Analysis. PhD Thesis, University of Alberta, 2012. [GRW, HRW, MRW, MGCRF, HMGCRF, and their applications][Image Fusion Page]


More to Come...