Discuss all kind of algorithms and data structures from their mathematical and programming sides.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard

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 ?

geist

Posts: 5
Joined: Mon Nov 10, 2008 9:22 am

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

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

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

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;
}
geist

Posts: 5
Joined: Mon Nov 10, 2008 9:22 am

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.

ventsyv

Posts: 2810
Joined: Mon Sep 22, 2003 5:25 pm
Location: MD USA

ventsyv wrote: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.

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;   }      }`
geist

Posts: 5
Joined: Mon Nov 10, 2008 9:22 am