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

あなたがしているのは、 Depth First Searchとして実装されたフラッド フィルです。

それを改善するには、次のことができます。

  • 幅優先検索として再コーディングします。
  • スタックを使用して深さ優先検索を実装します。これは同じ考え方ですが、再帰の代わりにスタックを使用すると、コードが高速になり、メモリの使用量が少なくなります。
于 2013-07-23T11:27:11.480 に答える