PARP Research Group  Universidad de Murcia 
QVComponentTree Class Reference

Public Member Functions  
QVComponentTree (const QVImage< uChar, 1 > &image, bool inverseTree=false, bool useAlternative=false)  
Constructs a component tree set, from a grayscale image.  
bool  isInverseTree () const 
Returns whether this tree is inverted or not.  
uInt &  rootNode () 
Returns index for the root node in the image.  
uInt &  seedX (uInt index) 
Returns horizontal coordinate for the seed point of a node, given it's index.  
uInt &  seedY (uInt index) 
Returns vertical coordinate for the seed point of a node, given it's index.  
uChar &  firstThreshold (uInt index) 
Returns grayscale value of the points at the vertex of a node.  
uChar &  lastThreshold (uInt index) 
Returns grayscale value of the points at the base of a node.  
uInt &  numChilds (uInt index) 
Returns the number of child nodes for a node.  
uInt &  firstChild (uInt index) 
Returns the index for the first of the childs of a node.  
uInt &  nextSibling (uInt index) 
Returns the index for the next node in the list of childs, for a node.  
uInt *  area (uInt index) 
Returns the accumulative histogram of the graylevel values of the pixels, for a node.  
uInt  getNumNodes () const 
Gets the number of total nodes in the tree.  
uInt  getLeafNodes () const 
Gets the number of leaf nodes in the tree.  
uInt  getTotalPoints () const 
Gets the number of pixels processed by the tree construction. 
Image component tree data structure.
A level set in a grayscale image is a connected set of points (pixels) with a grayscale level above a given threshold. Component trees are built upon the inclusion relation of the level sets in an image.
They are a representation useful to obtain nonflat connected component filters, that may preserve connected components in the image, satisfying a given criterion. These trees are used in computer vision for task like image segmentation, filtering, scale and rotation invariant image feature extraction (like MSER, see [Matas]), amongst other.
For a wider explanation about component trees, you can read paper [Jones]. The former implementation of component trees is very efficient, so that it can be used with regular sized images (320x240 to 640x480, depending on the computer speed) in realtime programs. It is based in the algorithm described in the paper [Najman], which is supposed to obtain the component tree in quasilinear time.
There's a main difference between this implementation and that described in the paper. While the latter constructs a node for each graylevel in a level set, this implementation compacts every graylevel included in a same level set, in one node only. It will only be stored for every graylevel in the same node it's histogram area; thus, every nonleaf node in QVision's component tree will have more than one descendant, making smaller trees.
You can access the properties of a node by its index, using the functions seedX and seedY, firstThreshold, lastThreshold, and area. All of these accept as parameter the node index.
You can get the index of the different nodes of the tree by transversing it, using functions rootNode, numChilds, firstChild and nextSibling. A code example of use of these functions is the following
void processNode(QVComponentTree &componentTree, uInt nodeIndex) { std::cout << "Node seed: " << componentTree.seedX(nodeIndex) << ", " << componentTree.seedY(nodeIndex) << std::endl; for ( int childIndex = componentTree.firstChild(nodeIndex); childIndex != NULL_NODE; childIndex = componentTree.nextSibling(childIndex) ) processNode(componentTree, childIndex); } void processComponentTree(QVComponentTree &componentTree) { processNode(componentTree, componentTree.rootNode()); }
This code transverses the componenttree in a depthfirst preorder walk, and just shows the horizontal and vertical coordinate for each node's seed point.
Each node has a seed point, which is any of the points at the vertex of the node if it is a leaf node, or any of the points with graylevel value close to the child nodes if it is an internal node. You can get the seed point of a node with the functions seedX and seedY functions.
Also, every node saves information about the histogram areas of their graylevel values. With the functions firstThreshold and lastThreshold you can obtain the lowest and the highest of the graylevel values of the pixels in the node (if the tree is direct. If it is reversed, the highest and the lowest).
Definition at line 103 of file qvcomponenttree.h.
QVComponentTree::QVComponentTree  (  const QVImage< uChar, 1 > &  image,  
bool  inverseTree = false , 

bool  useAlternative = false  
) 
Constructs a component tree set, from a grayscale image.
By default the leaf nodes will represent low grayscale value areas in the image.
A reverse version of the tree can be created by setting the second parameter of the constructor ( inverseTree ) to true. In that case, leaf nodes will represent high grayscale valued areas in the image, and will increase to lower grayscale valued areas, as you transverse the tree to the root node.
image  image to create from the component tree.  
inverseTree  tells the function whether construct a direct or a reverse tree. 
Definition at line 30 of file qvcomponenttree.cpp.
bool QVComponentTree::isInverseTree  (  )  const [inline] 
Returns whether this tree is inverted or not.
Definition at line 123 of file qvcomponenttree.h.
uInt& QVComponentTree::rootNode  (  )  [inline] 
Returns index for the root node in the image.
Nodes in the component tree can be accessed by their index, that is a integer number. It is not assured that root node will have index zero for every component tree, so it's index should be obtained with this function.
Definition at line 131 of file qvcomponenttree.h.
uInt& QVComponentTree::seedX  (  uInt  index  )  [inline] 
Returns horizontal coordinate for the seed point of a node, given it's index.
The seed point of a component tree's node is one of the points (or the point if it is unique) of the vertex of the region it represents.
Given the index of a node in the component tree, this function returns first coordinate of that point.
index  index for a node. 
Definition at line 142 of file qvcomponenttree.h.
Referenced by getMSER().
uInt& QVComponentTree::seedY  (  uInt  index  )  [inline] 
Returns vertical coordinate for the seed point of a node, given it's index.
The seed point of a component tree's node is one of the points (or the point if it is unique) of the vertex of the region it represents.
Given the index of a node in the component tree, this function returns second coordinate of that point.
index  index for a node. 
Definition at line 153 of file qvcomponenttree.h.
Referenced by getMSER().
uChar& QVComponentTree::firstThreshold  (  uInt  index  )  [inline] 
Returns grayscale value of the points at the vertex of a node.
This function returns the minimal (or maximal, if the tree is inverted) grayscale value of the pixels contained in it.
node  index for a node. 
Definition at line 161 of file qvcomponenttree.h.
Referenced by getMSER().
uChar& QVComponentTree::lastThreshold  (  uInt  index  )  [inline] 
Returns grayscale value of the points at the base of a node.
This function returns the maximal (or minimal, if the tree is inverted) grayscale value of the pixels contained in it.
node  index for a node. 
Definition at line 169 of file qvcomponenttree.h.
Referenced by getMSER().
uInt& QVComponentTree::numChilds  (  uInt  index  )  [inline] 
Returns the number of child nodes for a node.
node  index for a node. 
Definition at line 174 of file qvcomponenttree.h.
uInt& QVComponentTree::firstChild  (  uInt  index  )  [inline] 
Returns the index for the first of the childs of a node.
node  index for a node. 
Definition at line 179 of file qvcomponenttree.h.
uInt& QVComponentTree::nextSibling  (  uInt  index  )  [inline] 
Returns the index for the next node in the list of childs, for a node.
node  index for a node. 
Definition at line 184 of file qvcomponenttree.h.
uInt* QVComponentTree::area  (  uInt  index  )  [inline] 
Returns the accumulative histogram of the graylevel values of the pixels, for a node.
Considering the grayscale values of the pixels of an image as indicator of a topological level or height, we can think of a node as a convex surface. That surface will have different areas for the different horizontal slides that we can think of.
Because heights in our topological image are discretized, we can store in a 256 integer array the number of pixels that get to a given level. That is what the array returned by this function gives, the area of the different slides, for the concave surface defined by the grayscale values of the pixels of the node.
Generally you will obtain valid values in the range of cells between firstThreshold and lastThreshold functions. There's an exception to that, when you find in that range cells containing the value zero, that means we have the keep the previous value in the array.
node  index for a node. 
Definition at line 203 of file qvcomponenttree.h.
Referenced by getMSER().
uInt QVComponentTree::getNumNodes  (  )  const [inline] 
Gets the number of total nodes in the tree.
Definition at line 207 of file qvcomponenttree.h.
Referenced by getMSER().
uInt QVComponentTree::getLeafNodes  (  )  const [inline] 
Gets the number of leaf nodes in the tree.
Definition at line 211 of file qvcomponenttree.h.
uInt QVComponentTree::getTotalPoints  (  )  const [inline] 
Gets the number of pixels processed by the tree construction.
This value should always equal cols x rows of the image fron which the tree was obtained.
Definition at line 217 of file qvcomponenttree.h.