Quadtree

[geist]

Hallo,
i am trying to build quadtree for a depth image (each pixels have 16 bits) and then i want to encode this image using arithmetic coding .how can i start ?

thanx in advance

[Alvaro]

You can start by explaining what you have tried and what problems you are having, as usual.

[geist]

You can start by explaining what you have tried and what problems you are having, as usual.

thanx for reply,
i have a depth image 300*400 pixels ,i wish to build a quadtree for this image , so that we stop when the difference between the pixels' values inside one node i less than specific value(threshold).
i have started with this code to define the node class and the pixels of the image:

#include<vector>

struct Point // the location of the pixel with the its value
{
int x;
int y;
int value;
};

// a node in the tree which contains many of pixels ,that //the difference among its //value less than specified value(threshold)

class Node
{
public:
Node(int x, int y, int w, int h);
int posX;
int posY;
int width;
int height;
bool leaf;
Node* child[4];
std::vector<Point> pointArray;
};


// CONSTRUCTOR
Node::Node(int x, int y, int w, int h)
{
posX = x;
posY = y;
width = w;
height = h;
leaf=false;
}

[ventsyv]

So far so good. What seems to be the problem ??

Next step will be to implement a insert function that you'll later use to build the tree.

[geist]

So far so good. What seems to be the problem ??

Next step will be to implement a insert function that you'll later use to build the tree.

thanx for your reply

this is the function for building the tree::

Code: Select all


Node* BuildNode(Node* n, Node* nParent, int index)
{
    cout << "Building node: " << index << endl;

   
    /*
    Position of the child node, is determined in this order ,dependeng on the index:
    | 0 | 1 |
    | 3 | 2 |
    */
    n = new Node(0, 0, 0, 0);

    switch(index)
    {
    case 0: // Top left
        n->posX = nParent->posX;
        n->posY = nParent->posY;
        break;
    case 1: // Top right
        n->posX = nParent->posX + (nParent->width / 2);
        n->posY = nParent->posY;
        break;
    case 2: // Bottom right
        n->posX = nParent->posX + (nParent->width / 2);
        n->posY = nParent->posY + (nParent->height / 2);
        break;
    case 3: // Bottom left
        n->posX = nParent->posX;
        n->posY = nParent->posY + (nParent->height / 2);
        break;
    }

    // Width and height of the child node is  1/2 of the parent node's width and height
    n->width = nParent->width / 2;
    n->height = nParent->height / 2;

    // The points within the child node are also based on the index, similiarily to the position
    const int numParentPoints = nParent->pointArray.size();
    switch(index)
    {       
    case 0: // Top left
        for(int i = 0; i < numParentPoints; i++)
        {
            // Check all parent points and determine if it is in the top left quadrant
            if( (nParent->pointArray[i].x >=nParent->posX ) && (nParent->pointArray[i].x < (nParent->posX + nParent->width / 2) ) )
            if( (nParent->pointArray[i].y >= nParent->posY )&&( nParent->pointArray[i].y < (nParent->posY + nParent->height / 2) ) )
            {
                // Add the point to the child node's point array
                n->pointArray.push_back(nParent->pointArray[i]);
            }
        }
        break;
    case 1: // Top right
        for(int i = 0; i < numParentPoints; i++)
        {
            // Check all parent points and determine if it is in the top right quadrant
            if( (nParent->pointArray[i].x >=(nParent->posX+nParent->width/2)) && (nParent->pointArray[i].x < (nParent->posX + nParent->width) ) )
            if( (nParent->pointArray[i].y >= nParent->posY )&&( nParent->pointArray[i].y < (nParent->posY + nParent->height / 2) ) )
            {
                // Add the point to the child node's point array
                n->pointArray.push_back(nParent->pointArray[i]);
            }
        }
        break;
    case 2: // Bottom right
        for(int i = 0; i < numParentPoints; i++)
        {
            // Check all parent points and determine if it is in the bottom right quadrant
            if( (nParent->pointArray[i].x >=(nParent->posX+nParent->width/2) ) && (nParent->pointArray[i].x < (nParent->posX + nParent->width) ) )
            if( (nParent->pointArray[i].y >=( nParent->posY+nParent->height/2) )&&( nParent->pointArray[i].y < (nParent->posY + nParent->height) ) )
            {
                // Add the point to the child node's point array
                n->pointArray.push_back(nParent->pointArray[i]);
            }
        }
        break;
    case 3: // Bottom left
        for(int i = 0; i < numParentPoints; i++)
        {
            // Check all parent points and determine if it is in the bottom left quadrant
          if( (nParent->pointArray[i].x >=nParent->posX ) && (nParent->pointArray[i].x < (nParent->posX + nParent->width / 2) ) )
            if( (nParent->pointArray[i].y >=( nParent->posY+nParent->height/2) )&&( nParent->pointArray[i].y < (nParent->posY + nParent->height) ) )
            {
                // Add the point to the child node's point array
                n->pointArray.push_back(nParent->pointArray[i]);
            }
        }
        break;
    }

    return n;
}

void BuildQuadTree(Node* n,int threshold)
{
   if(n->pointArray.size()>1)
   {
   int maximum=MaxVal(n);
   int   minimum=MinVal(n);
   
    if((maximum-minimum) >threshold)
    {
        for(int i = 0; i < 4; i++)
        {
            Node* nodeIn = new Node(0, 0, 0, 0);
            nodeIn = BuildNode(n->child[i], n, i);
            n->child[i]=nodeIn;
            BuildQuadTree(nodeIn,threshold);
         
        }
      
    }
   else
   {
      NumofLeaves++;
       n->leaf=true;
   }
   }
   else
   {
      NumofLeaves++;
       n->leaf=true;
   }
      
}