Efficient computation of Contour Trees
The contour tree is a structure that summarizes all possible contours on a map. I didn't invent it: it was used in the 1950's by Boyell and Ruston for contours, and by many people since then. Until recently, contour trees haven't been used in 3-D datasets, because of a lack of efficient algorithms.
My Master's thesis gave an efficient algorithm for computing the contour tree in any number of dimensions, with particular focus on 3-D data sets such as X-ray crystallography. A journal version of the principal results can be found in Computational Geometry: Theory and Applications.
Hunh? What the heck is a contour tree?
To illustrate the contour tree, and the algorithm for its construction, I will work through a 2-D example. For data, I will start with a DEM (digital elevation map) of Vancouver, taken from the USGS GTOPO30 dataset. In the grid shown, measurements are spaced approximately 1 km (30 arc-seconds) apart: the measurements represent height above sea level.
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 18 26 21
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 36 4 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 35 30 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 3 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 34 30 22 1
0 0 0 6 9 6 3 1 1 0 0 0 0 0 0 1 1 23 30 17 1
0 0 30 39 46 42 34 35 27 16 7 7 5 20 26 14 3 1 1 2 4
0 0 30 53 60 60 55 57 55 47 28 22 24 28 30 32 31 30 19 21 25
0 0 0 30 56 53 52 60 64 85 86 46 30 30 37 49 57 60 47 47 53
0 0 0 0 0 17 30 47 60 69 82 67 61 30 40 60 89 72 63 61 61
0 0 0 0 0 0 0 19 27 33 43 56 60 60 60 80 91 85 69 63 71
0 0 0 0 0 0 1 0 11 14 19 25 33 42 54 66 79 90 75 64 62
0 0 0 0 0 0 0 1 1 1 1 8 11 18 30 42 60 61 58 40 32
0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 18 30 33 29 16 13
0 0 0 0 0 0 0 0 1 4 4 4 4 4 1 1 6 6 1 1 1
0 0 0 0 0 0 0 0 3 4 4 4 4 4 4 4 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1 2 3 4 4 2 1 1 1 2 3 3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 3 4 4
One way of looking at this information is as an image:
Image of Vancouver
Alternately, we can construct a series of contours from the data:
Contour Map of Vancouver
If we look closely, we can see that the contours nest inside each other. We can exploit this by drawing a diagram that represents the way the contours nest. One way to do this is to draw a set of paths that cross every contour exactly once:
Contours & Contour Tree
The diagram we get is called the contour tree. If we straighten out this tree so that the highest hills are at the top, and the lowest points at the bottom, we get this:
Contour Tree
This gives a convenient abstract representation of the input data that we can use for a number of purposes, starting with accelerated extraction of the contours.
How do you construct the contour tree?
There are actually a couple of ways of doing it. Here's how I do it:
Start at the highest peak (point A), and add points one at a time in order of height. As we do so, we see blobs grow in the image:
Blobs growing to find Join Tree
When we see two blobs join together, we know that we have found a saddle, or pass, between two peaks. We draw two lines connecting the peaks to the saddle. After that, we treat the two (connected) peaks as one: if we need to draw a line from the combined peak, we do it from the saddle. When we are done, we straighten out the diagram we have drawn, and get what I call the join tree: note that all "upward" forks in the final contour tree show up in this tree.
The Join Tree
If we grow blobs from the bottom up, we get the "split tree", in which the "downward" forks show up:
Blobs growing to find the Split Tree
The Split Tree
When we have constructed the join and split trees, we merge them together to get the contour tree. If you want details, check out the paper.
For those of you who are curious, the labelled points are (very roughly):
| A |
Queen Elizabeth Park |
B |
Dunbar |
C |
Metrotown |
| D |
Fraser |
E |
Kerrisdale |
F |
University Hill (UBC) |
| G |
Blanca |
H |
Stanley Park |
I |
Downtown |
| J |
North Vancouver |
K |
Lost Lagoon |
L |
False Creek |
| M |
Sea Island |
N |
First Narrows |
O |
North Arm |
| P |
Burrard Inlet |
Q |
Georgia Strait |