##### Personal tools
You are here: Home Introduction to Minimal Spanning Trees

# Introduction to Minimal Spanning Trees

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.

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

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

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

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