6

私はopenCVを使用してブロックマッチングを行ってきましたが、差の二乗和のコードは、次のような単純なforループと比較して非常に高速であることに気付きました。

int SSD = 0;
for(int i =0; i < arraySize; i++)
    SSD += (array1[i] - array2[i] )*(array1[i] - array2[i]);

ソースコードを見て、重労働が発生する場所を確認すると、OpenCVの人々は、ループの各反復で一度に4つの2乗差分計算をforループで実行します。ブロックマッチングを行う関数は次のようになります。

int64
icvCmpBlocksL2_8u_C1( const uchar * vec1, const uchar * vec2, int len )
{
int i, s = 0;
int64 sum = 0;

for( i = 0; i <= len - 4; i += 4 ) 
{   
    int v = vec1[i] - vec2[i];
    int e = v * v;

    v = vec1[i + 1] - vec2[i + 1]; 
    e += v * v;
    v = vec1[i + 2] - vec2[i + 2];
    e += v * v;
    v = vec1[i + 3] - vec2[i + 3];
    e += v * v;
    sum += e;
}

for( ; i < len; i++ )
{
    int v = vec1[i] - vec2[i];

    s += v * v;
}

return sum + s;
}

この計算は、符号なし8ビット整数用です。これらは、この関数で32ビットフロートに対して同様の計算を実行します。

double
icvCmpBlocksL2_32f_C1( const float *vec1, const float *vec2, int len )
{
double sum = 0;
int i;

for( i = 0; i <= len - 4; i += 4 )
{
    double v0 = vec1[i] - vec2[i];
    double v1 = vec1[i + 1] - vec2[i + 1];
    double v2 = vec1[i + 2] - vec2[i + 2];
    double v3 = vec1[i + 3] - vec2[i + 3];

    sum += v0 * v0 + v1 * v1 + v2 * v2 + v3 * v3;
}
for( ; i < len; i++ )
{
    double v = vec1[i] - vec2[i];

    sum += v * v;
}
return sum;
}

このようにループを4つのチャンクに分割すると、コードが高速化されるのではないかと誰かが考えているのではないかと思いました。このコードではマルチスレッドが発生していないことを付け加えておきます。

4

2 に答える 2

4

私の推測では、これはループを展開する単純な実装です。ループの各パスで3つの追加と3つの比較が節約されます。これは、たとえば、チェックlenにキャッシュミスが含まれる場合に大幅に節約できます。欠点は、この最適化によってコードが複雑になることです（たとえば、長さが4で割り切れない場合は、残りのlen％4アイテムのループを終了するために、最後にforループを追加します）。もちろん、アーキテクチャに依存する最適化です。その改善の程度は、ハードウェア/コンパイラなどによって異なります。

それでも、ほとんどの最適化と比較して従うのは簡単であり、アーキテクチャに関係なく、おそらく何らかのパフォーマンスの向上をもたらすので、そこにそれを投入して最高のものを期待することはリスクが低いです。OpenCVは非常によくサポートされているコードのチャンクであるため、誰かがこれらのコードのチャンクをインストルメントし、あなた自身が行ったように、それらが十分に価値があることを発見したと確信しています。

于 2012-04-14T17:51:28.260 に答える
2

コードの明らかな最適化が 1 つあります。

int SSD = 0;
for(int i = 0; i < arraySize; i++)
{
    int v = array1[i] - array2[i];
    SSD += v * v;
}
于 2012-04-14T18:07:01.443 に答える