Lei Zhang






Description: Description: D:\Lei Zhang\MyWebpage\index_files\byline.gif

An Extended Chain Graph and its Applications in Computer Vision


Both undirected graphical models (e.g., MRFs, CRFs) and directed acyclic graphical models (e.g., BNs, DBNs, HMMs) have limited modeling power and expressiveness. They cannot model heterogeneous relationships among random variables. For example, undirected graphical models cannot model "explaining-away" type of relationships, while directed graphical models cannot effectively model mutual dependence with a loop. In contrast, Chain Graph subsumes both undirected graphical models and directed graphical models and is therefore expressive enough for modeling extremely complex and heterogeneous relationships in probabilistic modeling. Unfortunately, the utility of Chain Graph in real application is still very limited due to some reasons including the difficulty of learning a Chain Graph with very general topology and lacking an efficient way to perform probabilistic inference in Chain Graph to  solve complex problems. Existing Chain Graphs ever used in real applications typically have simplified structures, therefore could not fully leverage the beauty and power of Chain Graph. 

An Extended Chain Graph Model:

To push the utility of Chain Graph in real world applications, we developed an extended Chain Graph modeling theory and successfully demonstrated its usefulness in solving two challenging computer vision and image analysis problems: human activity recognition and image segmentation. Specifically, we developed a suite of methods for constructing, learning, and inference in the extended Chain Graph model:

§  We construct the Chain Graph structure according to the nature and semantic meaning of the relationships between different variables (i.e., entities). We parameterize different types of links in the graph by taking into account the nature (e.g., causality or correlation) of these links and the difficulty of learning and inference.

§  Once the Chain Graph is constructed and the links are parameterized with appropriate potential functions or conditional probability distributions (CPDs), we derive the joint probability distribution (JPD) of all random variables based on the Global Markov Property in Chain Graph and using the idea of Master Graph and Component Subgraphs

§  To learn the model, we developed a joint parameter learning method that combines an analytical learning and a contrastive divergence (CD) based numerical learning to learn different modeling parts of the model. This method maximally leverages the factorization of the JPD into different local functions (i.e., factors).

§  We finally convert the extended Chain Graph into a Factor Graph representation based on the factored JPD. We leverage principled inference methods developed for Factor Graphs, such as Sum-Product algorithm or Max-Product algorithm, to perform probabilistic inference and solve the problem.

Below is a (relatively simple) example to illustrate the extended Chain Graph model and its factored joint probability distribution. 

Description: Description: D:\Lei Zhang\MyWebpage\index_files\CG_example.jpgDescription: Description: D:\Lei Zhang\MyWebpage\index_files\CG_exampleEqn.JPG

Figure 1. An extended Chain Graph model (left) for illustration of the concept and its represented joint probability distribution (right)



We have successfully applied the extended Chain Graph model to solve two challenging computer vision problems: multi-subject human activity recognition and 2D image segmentation. We also believe this model should be applicable to many computer vision and image analysis problems that require modeling of the heterogeneous relationships among different entities.


Example results:

I) Here are the extended Chain Graph model for image segmentation and some image segmentation results on different datasets.

Description: Description: D:\Lei Zhang\MyWebpage\index_files\CG_segmentation.JPG

Figure 2. An oversegmentation of the input image (a), a part of the edge map for illustration (b) and an extended Chain Graph segmentation model (c) that corresponds to the part (b)

Description: Description: D:\Lei Zhang\MyWebpage\index_files\Weizmann_seg.JPGDescription: Description: D:\Lei Zhang\MyWebpage\index_files\VOC2006_seg.JPG

Figure 3. Example image segmentation results. In each group the first row is the raw images; the second row the edge map of oversegmentation; and the third row the segmentation masks. The left side shows examples for the Weizmann horse dataset and the right side shows examples for the VOC2006 cow images.

Description: Description: D:\Lei Zhang\MyWebpage\index_files\Caltechcars_seg.JPG

Figure 4. Examples of image segmentation results for Caltech Cars (1999) dataset

Description: Description: D:\Lei Zhang\MyWebpage\index_files\MSRC2_seg.JPG

Figure 5. Examples of image segmentation results for MSRC2 dataset. The third row corresponds to the groundtruth labeling, where the dark color corresponds to areas without groundtruth labeling and therefore not considered for evaluation.


II) Here are the extended Chain Graph (both the static model and the dynamic model) for human activity recognition and some quantitative comparison with two Dynamic Bayesian Network (DBN) models and the static model. Please see our recent publication "Probabilistic Image Modeling with an Extended Chain Graph for Human Activity Recognition and Image Segmentation" on IEEE Transactions on Image Processing for more details.

Description: Description: D:\Lei Zhang\MyWebpage\index_files\CG_activity.JPG

Figure 6. The static Chain Graph model (top) and its dynamic extension, i.e. the dynamic Chain Graph model (bottom), for multi-subject human activity recognition

Description: Description: D:\Lei Zhang\MyWebpage\index_files\CG_activityresults.JPG

Table 1. Quantitative comparison between the dynamic Chain Graph model, two DBN models, and the static Chain Graph model for human activity recognition


Related publications:

  • Lei Zhang, Zhi Zeng and Qiang Ji, Probabilistic Image Modeling with an Extended Chain Graph for Human Activity Recognition and Image Segmentation, IEEE Transactions on Image Processing (TIP), pages 2401-2413, Vol. 20, No. 9, September 2011.  
  • Lei Zhang and Qiang Ji, "Image Segmentation with a Unified Graphical Model", IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), vol. 32, no. 8, pp. 1406-1425, July 2010
  • Lei Zhang, Yan Tong, and Qiang Ji, " Probabilistic Graphical Models and Their Applications in Computer Vision", Handbook of Pattern Recognition and Computer Vision (4th edition), Editor Chi Hau Chen, World Scientific Publishing, pp. 129-156, Oct. 2009. (Invited book chapter)
  • Cassio P. de Campos, Lei Zhang, Yan Tong, and Qiang Ji. "Semi-Qualitative Probabilistic Networks in Computer Vision Problems", Journal of Statistical Theory and Practice, special Issue on Imprecision, Vol. 3, no. 1, pp. 197-210, 2009 
  • Lei Zhang and Qiang Ji, "A Multiscale Hybrid Model Exploiting Heterogeneous Contextual Relationships for Image Segmentation", in IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 2009.



Description: Description: D:\Lei Zhang\MyWebpage\index_files\byline.gif