Faculty of Informatics Vienna University of Technology Institute of Computer Aided Automation PRIP Home PRIP Home
Personal tools
You are here: Home Research Research Areas Structure & Topology Graphs in Image Analysis Representing Images by Graphs Introduction to Minimal Spanning Trees

Introduction to Minimal Spanning Trees

mst_example.gif

In this demonstration we first define the minimal spanning tree (MST) and list its most important properties. We also present applications of the MST.

 

Definition and Properties of the Minimal Spanning Tree

Graph theoretical Definitions

  • Cost of an edge of a graph: absolute distance between the gray level values of the two cells it joins.
  • Spanning tree: tree that covers all vertices of a graph.
  • A minimal spanning tree is a spanning tree of a graph, such that the sum of all edge costs is minimal.

Properties of the Minimal Spanning Tree

  • In general, the minimal spanning tree of an image graph is not unique.
  • The minimal spanning tree can be implemented for image graphs with 4- or 8-neighborhood.
  • The implementation can be done using a greedy algorithm.

ex50-3.gif ex50-3r.gif
A gray level image and its MST

Applications for the Minimal Spanning Trees

A major application for the minnimal spanning trees in pattern recognition is segmentation. Minimal spanning trees are used to

  • find noisy pixels,
  • detect and separate regions of the image,
  • calculate an image pyramid based on a minimal spanning tree.

Finding noisy Pixels


May the central (black) pixel below be a noisy pixel.
noisy3.gif   noisy3r.gif
The corresponding vertex of an image pixel like that is always represented by a dead end of the minimal spanning tree. Thus endings of the minimal spanning tree with high costs to their adjacent vertices are detected as noisy pixel.

The algorithm easily leads to success on real images as shown below.

noisy15.gif   noisy15r.gif

 

Detecting Regions


Regions with large differences in the gray level between each other are linked with a single edge of the minimal spanning tree (see below). The MST can be split up on high cost edges to receive several trees that cover the different regions.

regio10.gif   regio10r.gif

regio30.gif mst_example.gif regio30rc.gif

 

Image Pyramids based on Minimal Spanning Trees


In order to build the first level of a graph pyramid, a 4- or 8-connected image graph is constructed. Every vertex corresponds to a pixel and every edge represents a neighborhood of two pixels (A).
By choosing the minimal spanning tree as the initial graph, the result of a segmentation can be improved (B).
mst_pyr.gif
(adapted from Christoph E. Mathieu and Isabelle E. Magnin, "On the Choice of the first Level on Graph Pyramids", Journal of Mathematical Imaging and Vision, Vol 6, pp 85-96, 1996.

A different approach is to build the pyramid by using the idea of the Boruvka's MST algorithm.