1

我目前正在研究一种算法，有时我必须遍历图像并将具有相同属性的像素分组。我从最左上角的像素开始并使用递归：从输入像素我可以获得高度相邻像素，如果第一个具有相同的属性，那么我通过将此像素作为输入像素传递来调用相同的函数。

这是一些代码（请记住，这仍在进行中）。基本调用者：

// R.A.G.
for( std::vector<Cell*>::iterator iterCell = cellVec.begin();
     iterCell != cellVec.end(); ++iterCell )
{
    Cell* mother = (*iterCell);

    if( mother->visited != true )
    {
        mother->visited = true;
    }
    CheckNeighbors( mother );
}

递归函数：

void
CheckNeighbors( Cell* mother )
{
    Cell* cell = nullptr;

    // Get the neighbours for the cell.
    //  5   6   7
    //  4   c   0
    //  3   2   1
    if( (cell=CheckCell( 1, 0, mother )) != mother )
    {
        mother = cell;
        CheckNeighbors( mother );
    }
    if( (cell=CheckCell( 1, 1, mother )) != mother )
    {
        mother = cell;
        CheckNeighbors( mother );
    }
    if( (cell=CheckCell( 0, 1, mother )) != mother )
    {
        mother = cell;
        CheckNeighbors( mother );
    }
    if( (cell=CheckCell( -1, 1, mother )) != mother )
    {
        mother = cell;
        CheckNeighbors( mother );
    }
    if( (cell=CheckCell( -1, 0, mother )) != mother )
    {
        mother = cell;
        CheckNeighbors( mother );
    }
    if( (cell=CheckCell( -1, -1, mother )) != mother )
    {
        mother = cell;
        CheckNeighbors( mother );
    }
    if( (cell=CheckCell( 0, -1, mother )) != mother )
    {
        mother = cell;
        CheckNeighbors( mother );
    }
    if( (cell=CheckCell( 1, -1, mother )) != mother )
    {
        mother = cell;
        CheckNeighbors( mother );
    }
}

我如何检查细胞：

Cell*
CheckCell( int x, int y, Cell* cell )
{
    // Here a cell is one pixel, but it depends on the size of the window we choose.
    // So for an image of 640*480, windowSize = 1, w = 640, h = 480
    x += cell->window.x()/windowSize;
    y += cell->window.y()/windowSize;

    // The cell at (x, y) coordinates is not in the map
    if( x < 0 || x >= w || y < 0 || y >= h ) return cell;

    // Get the neighbor cell in (x, y)
    // NB: cellVec has been filled up earlier and contains all the cells
    Cell* neighbor = cellVec.at( (y*w) + x );

    // The neighbor cell has already been visited
    if( neighbor->visited ) return cell;

    // The neighbor cell is of the same class as the mother cell
    if( neighbor->cClass != cell->cClass ) return cell;

    // Set the region number for the neighbor
    neighbor->visited = true;

    return neighbor;
}

所以这是我的问题：我确信这可以改进，但我想知道如何。我应该使用其他递归吗？如何改进这种递归？我阅读了这篇关于尾调用优化的文章，但由于我无法丢弃调用者的状态，因此无法应用。但是我可以使用其他技巧吗？

感谢您的回答，我希望我已经足够明确了。

注意：如果我有一个单色图像，大小为 640*480，单元格大小为 2*2 像素，我有 153765 个调用。当然还有一个单元格大小为 1*1 的段错误。我知道我可以增加堆栈的大小，但我更愿意找到另一种解决方案。

4

2 回答 2

2

你正在做的是一个Flood 填充，实现为Depth First Search。

要改进它，您可以：

  • 将其重新编码为广度优先搜索。
  • 使用堆栈实现深度优先搜索。这仍然是相同的想法，但是使用堆栈而不是递归应该会使您的代码更快并使用更少的内存。
于 2013-07-23T11:27:11.480 回答
1

使用迭代方法会更快，因为您已经将所有元素都包含在一个向量中，并且您可以线性地遍历它。这对缓存更加友好，并且您摆脱了所有抵消的东西

// Copy all elements starting from the selected cell pointed to by the iterator, if 
// they are equal to the cell
void checkAllCells(vector<Cell*> input, vector<Cell*>::iterator it; vector<Cell*> output)
{
    auto localIt = it;
    while( localIt != input.end())
    {
        if ((*localIt)->class == (*it)->class)
        {
            output.pushback(*it);
        }
    }
}

请注意，您不需要像visited等那样进行簿记，因为从第一个元素开始，您会发现所有其他元素都是平等的。如果你再考虑第二个元素，你知道，你已经考虑了前一个元素

于 2013-07-23T11:13:47.613 回答