0

我正在尝试构建一个四叉树,并且遇到了一些困难。它旨在读取二进制图像(在其他地方处理)并执行各种操作。但是,当然,首先必须构造四叉树。为了方便操作,我希望继续细分树,直到所有像素都是一种纯色(黑色或白色)。

我有以下函数,它只是调用一个辅助函数来处理构建树的冗长递归过程。

void Quadtree::constructQuadtree(Image* mImage){

    if (mImage->imgPixels == 0) {
        return;
    }

    root = new QTNode(); 


    this->root = buildQTRecur(mImage, 0, 0, mImage->rows);

}

这是处理大部分树构建的辅助函数:

QTNode* Quadtree::buildQTRecur(Image* mImage, int startRow, int startCol, int subImageDim) {

if (this->root == NULL) {
    return this->root;
}


 if (subImageDim >= 1) {

  int initialValue = 0;

  bool uniform = false;

  // Check to see if subsquare is uniformly black or white (or grey)

  for (int i = startRow; i < startRow + subImageDim; i++)
  {
     for (int j = startCol; j < startCol + subImageDim; j++)
     {
        if ((i == startRow) && (j == startCol))

           initialValue = mImage->imgPixels[i*mImage->rows+j];

        else {

           if (mImage->imgPixels[i*(mImage->rows)+j] != initialValue) {
              uniform = true;

              break;

           }
        }
     }
  }

  // Is uniform

  if (uniform) {

    this->root->value = initialValue; 

    this->root->NW = NULL;
    this->root->SE = NULL;
    this->root->SW = NULL;
    this->root->NE = NULL;

    return this->root;

   }

  else { // Division required - not uniform

     this->root->value = 2; //Grey node

     this->root->NW = new QTNode();
     this->root->NE = new QTNode();
     this->root->SE = new QTNode();
     this->root->SW = new QTNode();

     // Recursively split up subsquare into four smaller subsquares with dimensions half that of the original.

     this->root->NW = buildQTRecur(mImage, startRow, startCol, subImageDim/2); 
     this->root->NE = buildQTRecur(mImage, startRow, startCol+subImageDim/2, subImageDim/2); 
     this->root->SW = buildQTRecur(mImage, startRow+subImageDim/2, startCol, subImageDim/2); 
     this->root->SE = buildQTRecur(mImage, startRow+subImageDim/2, startCol+subImageDim/2, subImageDim/2); 

  }

 }

 return this->root;

}

当我尝试运行它时,我陷入了无限循环。请让我知道查看其他内容是否会有所帮助,例如我的节点构造函数或任何其他帮助信息!

谢谢你。

4

1 回答 1

0

我在您的代码中看到了几个问题:

  • 谁负责创建子节点?如果你同时写

    this->root->NW = new QTNode();
    this->root->NW = buildQTRecur(mImage, startRow, startCol, subImageDim/2);
    

    然后你首先分配一个新的四叉树然后覆盖它。

  • 你得到了计算统一反转的逻辑。

  • 如果你找到两个不同的像素,那么你做一个break. 但它只脱离了内循环。你应该考虑把它放在一个辅助函数中,并在return此处执行一次以立即退出两个循环。
  • 出于效率原因,您不应该写

    if ((i == startRow) && (j == startCol))
         initialValue = mImage->imgPixels[i*mImage->rows+j];
    

    就放

    initialValue = mImage->imgPixels[startRow*mImage->rows+startCol];
    

    循环之前

于 2013-07-22T22:23:56.670 回答