PARP Research Group
| 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 gray-scale 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 gray-scale value of the points at the vertex of a node. | |
| uChar & | lastThreshold (uInt index) |
| Returns gray-scale 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 gray-level 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 gray-scale image is a connected set of points (pixels) with a gray-scale 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 non-flat 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 real-time programs. It is based in the algorithm described in the paper [Najman], which is supposed to obtain the component tree in quasi-linear time.
There's a main difference between this implementation and that described in the paper. While the latter constructs a node for each gray-level in a level set, this implementation compacts every gray-level included in a same level set, in one node only. It will only be stored for every gray-level in the same node it's histogram area; thus, every non-leaf 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 component-tree in a depth-first pre-order 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 gray-level 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 gray-level values. With the functions firstThreshold and lastThreshold you can obtain the lowest and the highest of the gray-level 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 gray-scale image.
By default the leaf nodes will represent low gray-scale 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 gray-scale valued areas in the image, and will increase to lower gray-scale 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 gray-scale value of the points at the vertex of a node.
This function returns the minimal (or maximal, if the tree is inverted) gray-scale 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 gray-scale value of the points at the base of a node.
This function returns the maximal (or minimal, if the tree is inverted) gray-scale 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 gray-level values of the pixels, for a node.
Considering the gray-scale 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 gray-scale 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.