Home · Pages · Index · Overviews

Level_Tree Class Reference

A tree of all the level sets in an Array or Slice. More...

 #include <level.set.h>

Descriptive Types

  Level_Set : void
 

Routines

Level_Tree * Build_Level_TreeG (Pixel_APart *image I, boolean iscon2n)

void Print_Level_Tree (Level_Tree *t, int indent, int idwidth, int valwidth, FILE *file)

boolean Get_Level_Tree_Connectivity (Level_Tree *t)
Array * Get_Level_Tree_APart (Level_Tree *t)
void Set_Level_Tree_APart (Level_Tree *t, Pixel_APart *image I)

Level_Set * Level_Set_Root (Level_Tree *t)
Level_Set * Level_Set_Child (Level_Tree *t, Level_Set *r)
Level_Set * Level_Set_Sibling (Level_Tree *t, Level_Set *r)
int Level_Set_Size (Level_Tree *t, Level_Set *r)
int Level_Set_Level (Level_Tree *t, Level_Set *r)
int Level_Set_Peak (Level_Tree *t, Level_Set *r)
int Level_Set_LeftMost (Level_Tree *t, Level_Set *r)
int Level_Set_Background (Level_Tree *t, Level_Set *r)
int Level_Set_Id (Level_Tree *t, Level_Set *r)

void List_Level_Set (Level_Tree *t, Level_Set *r,
                           void *arg, void (*handler)(Indx_Type p, void *arg))

Detailed Description

A level set of level h is a maximal, connected set of pixels all of whose values are not less than h and at least one of which has value exactly h. A level set is maximal in that any pixels outside the set adjacent to a pixel in the set have a value less than h. Consider the set L of all level sets of all levels in an image. First observe that the number of sets is less than the number of pixels in the image as a level set of level h must have at least one pixel of value h unique to it. Second, observe that if A and B are two level sets (of any respective levels) then either A and B are disjoint or one is a subset of the other (the one of strictly greater level). This implies that the transitive reduction of the subset relationship over L is a tree, and this tree is called here the level tree for the image. To be more concrete, every node in a level tree represents one of the level sets of L. The root of the tree is the level set of level 0 (which is the entire image). Level set A is a child of level set B iff B is a subset of A and there is no level set C such that B is a subset of C and C is a subset of A. The level of B must clearly be greater than the level of A.

A Level_Tree object is built for a UINT8_TYPE or UINT16_TYPE array or slice of any dimensionality with respect to either (2n)- or (3n-1)-connectivity by the routine Build_Level_Tree. The connectivity and the array or slice from which it was built can be retrieved later with Get_Level_Tree_Connectivity and Get_Level_Tree_APart. A Level_Tree object can be read and written to a file, but it relies on a reference to the underlying array from which it was built, so when your read in a Level_Tree you must re-establish this reference with Set_Level_Tree_APart. One can also produce a diagnostic print out of a Level_Tree with Print_Level_Tree, but generally level trees are so large that this is only recommended for small debug situations.

Once you have a tree you can then traverse the nodes of the tree. A Level_Set is an opaque object representing a node in the tree. It does not have any class operators as its existence and access is strictly relative to a Level_Tree. All the traveral primitives operate upon a pointer to a Level_Set. You can get the root of a tree with Level_Set_Root and your can recursively traverse the tree with Level_Set_Child which takes you to the first child of a level set, and Level_Set_Sibling which then takes you to the next sibling of a level set. For example, the code snippet below traverses every node in a level set tree T:

 void Traverse_Tree(Level_Tree *t, Level_Set *p)
 { // Visiting p
   for (p = Level_Set_Child(t,p); p != NULL; p = Level_Set_Sibling(t,p))
     Traverse_Tree(t,p);
 }

 Traverse_Tree(T,Level_Set_Root(T));

For each level set you can get its level with Level_Set_Level, its size in pixels with Level_Set_Size, the value of the largest pixel in the level set with Level_Set_Peak, a representative left-most pixel in the level set (useful for flood fills, see the Connectivity module) with Level_Set_LeftMost, a unique integer id in the range [0,L-1] where L is the number of level sets in the tree with Level_Set_Id, and the background of a level set with Level_Set_Background. The background value of a level set is the value of the largest pixel adjacent to the level set, but not in it.


Descriptive Types Documentation

Level_Set: void

Void (opaque) object representing a node in a Level_Tree. Access to the contents of these objects, that can only be created by the tree object, is entirely through the routines below.


Routine Documentation

Level_Tree * Build_Level_TreeG (Pixel_APart *image I, boolean iscon2n)

Generate a level set tree object for UINT8_TYPE or UINT16_TYPE Array or Slice image with respect to 2n-connectivity if iscon2n it true, and (3n-1) connectivity otherwise. Note carefully that the routine creates a new reference to image which is held by the level set object. Building the level set tree takes 28A bytes where A is the size of image in pixels, where the level set tree object itself occupies 20A bytes. Because of this fairly large space overhead, a level set can only be built over AParts that have less than 231-1 pixels. For a detailed description of what a level tree is, see the introduction

void Print_Level_Tree (Level_Tree *t, int indent, int idwidth, int valwidth, FILE *file)

Produce a nested print out of level tree t. While the routine will work for any tree, it generally only makes sense to use it for small trees while debugging, because for a really big tree the nesting depth is so deep that the display will be unwiedly. The display is printed to file file and indented by indent spaces. You can control the display width of the numbers denoting id and size with idwidth, and the display width of numbers denoting background, level, and peak values with valwidth.

boolean Get_Level_Tree_Connectivity (Level_Tree *t)

Return true if and only if level tree t was built with respect to 2n-connectivity (as opposed to (3n-1)-connectivity).

Array * Get_Level_Tree_APart (Level_Tree *t)

Return the Array or Slice (APart) that level tree t was made from.

void Set_Level_Tree_APart (Level_Tree *t, Pixel_APart *image I)

Creates a new reference to image and sets it to be the image reference of t. The somewhat awkward need for this routine is to relink the level tree with its image in the event you read it in from a file. A level tree object can be written and later read, but writing the object does not write the image upon which it depends, so one must take care to write the image as well. Later when you read both the image and level tree from the file, one needs this routine link them back up.

Level_Set * Level_Set_Root (Level_Tree *t)

Return a pointer to the root of level set tree t.

Level_Set * Level_Set_Child (Level_Tree *t, Level_Set *r)

Return the left-most child of level set r within tree t, returning NULL if there is none.

Level_Set * Level_Set_Sibling (Level_Tree *t, Level_Set *r)

Return the sibling immediately to the right of level set r within tree t, returning NULL if there is none.

int Level_Set_Size (Level_Tree *t, Level_Set *r)

Return the number of pixels in level set r of tree t.

int Level_Set_Level (Level_Tree *t, Level_Set *r)

Return the level of level set r of tree t.

int Level_Set_Peak (Level_Tree *t, Level_Set *r)

Return the peak or largest valued pixel within level set r of tree t.

int Level_Set_LeftMost (Level_Tree *t, Level_Set *r)

Return a 'leftmost' pixel of level set r of tree t. A leftmost pixel is one that is guaranteed to be on the outer contour of the level set and so can be given to one of the Connectivity module routines if you wish to traverse all the pixels in a level set.

int Level_Set_Background (Level_Tree *t, Level_Set *r)

Return the background of level set r of tree t. The background value of a level set is the value of the largest pixel adjacent to the level set, but not in it.

int Level_Set_Id (Level_Tree *t, Level_Set *r)

Return the internal id level set r of tree t. This id is a unique integer in the range [0,L-1] where L is the number of level sets in the tree.

void List_Level_Set (Level_Tree *t, Level_Set *r,
                           void *arg, void (*handler)(Indx_Type p, void *arg))

Call the routine handler on every pixel in level set r of tree t. A pointer arg to an amorphous data package is passed through the routine to each call of handler along with a pixel p.