Level_Tree Class Reference
A tree of all the level sets in an Array or Slice.
More...
#include <level.set.h>
Descriptive Types
Routines
void |
Print_Level_Tree
(Level_Tree *t, int indent, int idwidth, int valwidth, FILE *file) |
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
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
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).
Return the Array or Slice (APart) that level tree t was made from.
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.
Return a pointer to the root of level set tree t.
Return the left-most child of level set r within tree t, returning NULL
if there is none.
Return the sibling immediately to the right of level set r within tree t, returning NULL
if there is none.
Return the number of pixels in level set r of tree t.
Return the level of level set r of tree t.
Return the peak or largest valued pixel within level set r of tree t.
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.
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.
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.
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.
|