画像の自己相似性を高速化する

Question

画像を生成するプログラムを書いています。私が望む測定の1つは、「自己相似性」の量です。画像で。写真の各sizeWindow * sizeWindowウィンドウのcountBest-thベストマッチを探す次のコードを書きました：

double Pattern::selfSimilar(int sizeWindow, int countBest) {
    std::vector<int> *pvecount;

    double similarity;
    int match;
    int x1;
    int x2;
    int xWindow;
    int y1;
    int y2;
    int yWindow;

    similarity = 0.0;

    // (x1, y1) is the original that's looking for matches.

    for (x1 = 0; x1 < k_maxX - sizeWindow; x1++) {
        for (y1 = 0; y1 < k_maxY - sizeWindow; y1++) {
             pvecount = new std::vector<int>();

             // (x2, y2) is the possible match.
             for (x2 = 0; x2 < k_maxX - sizeWindow; x2++) {
                 for (y2 = 0; y2 < k_maxY - sizeWindow; y2++) {
                     // Testing... 
                     match = 0;

                     for (xWindow = 0; xWindow < sizeWindow; xWindow++) {
                         for (yWindow = 0; yWindow < sizeWindow; yWindow++) {
                             if (m_color[x1 + xWindow][y1 + yWindow] == m_color[x2 + xWindow][y2 + yWindow]) {
                                 match++;
                             }
                         }
                     }

                     pvecount->push_back(match);
                 }
             }

             nth_element(pvecount->begin(), pvecount->end()-countBest, pvecount->end());

             similarity += (1.0 / ((k_maxX - sizeWindow) * (k_maxY - sizeWindow))) *
                 (*(pvecount->end()-countBest) / (double) (sizeWindow * sizeWindow));

             delete pvecount;
        }
    }

    return similarity;
}

良いニュースは、アルゴリズムが私がやりたいことをするということです。それは、写真がどのように「自己相似」であるかについて0.0から1.0の値を返します。

悪いニュース-すでにお気づきだと思いますが-は、アルゴリズムが非常に遅いことです。実行には（k_maxX-sizeWindow）*（k_maxY-sizeWindow）*（k_maxX-sizeWindow）*（k_maxY-sizeWindow）* sizeWindow * sizeWindow のステップが必要です。

変数の典型的な値：

k_maxX = 1280
k_maxY = 1024
sizeWindow = between 5 and 25
countBest = 3, 4, or 5
m_color[x][y] is defined as short m_color[k_maxX][k_maxY] with values between 0 and 3 (but may increase in the future.)

今、pvecountのメモリフットプリントが気になりません。後で、countBestより小さい場合に別の要素を追加しない並べ替えられたデータセットを使用できます。アルゴリズムの速度だけが心配です。

これを高速化するにはどうすればよいですか

Answer 1

あなたの問題は、動き補償のために行わなければならない計算を強く思い出させます>ビデオ圧縮。たぶん、あなたはその領域で何が行われているのかを詳しく調べる必要があります。

rlbondがすでに指摘したように、ウィンドウ内の色が完全に一致するポイントの数を数えることは、写真を比較する際に通常行われることではありません。離散コサインまたはウェーブレット変換を使用するよりも概念的に簡単な方法は、差の二乗を追加することです

diff = (m_color[x1 + xWindow][y1 + yWindow] - m_color[x2 + xWindow][y2 + yWindow]);
sum += diff*diff;

そして、 match の代わりに sum を類似性の基準として使用します（現在は小さいほど良いことを意味します）。

あなたが本当に求めていたものに戻る：実行時間を2 / sizeWindowの係数（おそらく2乗？）で削減することは可能だと思いますが、少し厄介です。これは、比較する特定の正方形のペアがy1を1増やしてもほぼ同じであるという事実に基づいています。オフセットxOff = x2-x1とyOff = y2-y1が同じ場合、上部（rsp。下部）の垂直ストライプのみの正方形はもはや一致していません（rsp。今ではなく、以前）。オフセットxOff = x2-x1およびyOff = y2-y1でインデックス付けされた2次元配列で一致するために計算した値を保持する場合、y1のmatch [xOff] [yOff]の新しい値を1ずつ増加して計算できます。 x1は2 * sizeWindowの比較で同じままです：

for (int x = x1; x < x1 + sizeWindow; x++) {
    if (m_color[x][y1] == m_color[x + xOff][y1 + yOff]) {
        match[xOff][yOff]--; // top stripes no longer compared
    }

    if (m_color[x][y1+sizeWindow] == m_color[x + xOff][y1 + sizeWindow + yOff]) {
        match[xOff][yOff]++; // bottom stripe compared not, but wasn't before
    }
}

（yOffの可能な値が変更された-y1をインクリメントすることにより-間隔[y2-y1、k_maxY-sizeWindow-y1-1]から間隔[y2-y1-1、k_maxY-sizeWindow-y1-2] 2番目のインデックスyOff = k_maxY-sizeWindow-y1-1の一致を破棄し、2番目のインデックスyOff = y2-y1-1の一致を異なる方法で計算する必要があります。また、配列内のループ中にmatch [] []をどれだけ増減して値を保持して、別の2 / sizeWindowの高速化を実現することもできます。

Answer 2

まず、このアプローチはまったく安定していません。画像にランダムノイズを追加すると、2つの画像間の類似性が大幅に低下します。さらに重要なことは、画像処理の観点からは、効率的ではないか、特に優れているわけではありません。別のアプローチをお勧めします。たとえば、ウェーブレットベースのアプローチを使用します。画像に対して2次元DWTをいくつかのレベルで実行し、スケーリング係数を比較した場合、おそらくより良い結果が得られます。さらに、離散ウェーブレット変換はO（n）です。

欠点は、ウェーブレットが高度な数学的トピックであるということです。ウェーブレットとフィルターバンクに関するOpenCourseWareの優れたメモがいくつかありますこちら。