5

ソース画像とパターン画像の両方に存在するピクセルの平均色を比較することで、画像マッチングの問題を解決しようとしています。この問題をサブ配列の合計の問題に減らしましたが、それを解決する方法を見つけることができません。

すべて正の整数の2D配列ARRがあるとします。私は数x(小さなパターン画像に存在するピクセルカラーの平均)を持っています。正確な合計がxであるサブ配列をARRで見つける必要があります。ここで動的計画法で解決できる同様の問題を見つけました。

http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/

しかし、それは、すでに与えられた合計ではなく、最大の合計を持つサブアレイを見つけることについて話します。

したがって、これが指定された配列の場合。

3 4 8 9 3
2 10 4 2 1
8 1 4 8 0
3 5 2 12 3
8 1 1 2 2

そして、与えられた合計が19の場合、このウィンドウを返す必要があります

3 4 8 9 3
2    10 4    2 1
8    1 4    8 0
3 5 2 12 3
8 1 1 2 2

そして、与えられた合計が23の場合、このウィンドウを返す必要があります

3 4 8    9 3 
2 10 4    2 1 
8 1 4    8 0
3 5 2 12 3
8 1 1 2 2
    

どうすればこれを効率的に見つけることができますか?ここで動的計画法を使用できますか?ここで私を助けてください。

4

1 に答える 1

4

同じ原理を使用しますが、より単純な問題に使用します。まず、配列の各列の累積合計を事前に計算します。つまり、A[i][j] += A[i-1][j] です。

次に、開始行と終了行の各ペア (i1、i2) を単一の配列 B[j] として扱います。つまり、B[j] = A[i2][j] - A[i1-1][ j]. 次に、正確な合計で部分配列を見つける必要があります。配列は正の数だけで構成されているため、O(n) で見つけることができます。

全体として、このアルゴリズムは O(n^3) です。

あなたが提供した値について、いくつかの追加配列を見つけることができました:

ターゲット = 19 の場合:

Found between (0,0) and (1,1)
Found between (0,3) and (2,4)
Found between (0,2) and (4,2)
Found between (1,1) and (2,2)
Found between (1,2) and (2,4)
Found between (2,0) and (4,0)
Found between (3,3) and (4,5)

ターゲット = 23:

Found between (0,2) and (1,3)
Found between (0,3) and (2,4)
Found between (2,0) and (3,2)
Found between (2,3) and (3,4)
Found between (3,1) and (4,4)

私が使用したコード:

public static void main(String[] args) {
    int[][] A = {
            {3, 4, 8, 9, 3},
            {2, 10, 4, 2, 1},
            {8, 1, 4, 8, 0},
            {3, 5, 2, 12, 3},
            {8, 1, 1, 2, 2},
    };

    int target = 19;

    for (int i = 1; i < A.length; i++)
        for (int j = 0; j < A[i].length; j++)
            A[i][j] += A[i - 1][j];


    for (int i1 = 0; i1 < A.length; i1++) {
        for (int i2 = i1 + 1; i2 < A.length; i2++) {
            int j1=0, j2=0, s=0;

            while(j2<A[i1].length) {
                while(s<target && j2<A[i1].length) {
                    s += A[i2][j2] - (i1 > 0 ? A[i1-1][j2] : 0);
                    j2++;
                    if (s==target)
                        System.out.println(String.format("Found between (%d,%d) and (%d,%d)", i1, j1, i2, j2-1));
                }
                while(s>=target) {
                    s -= A[i2][j1] - (i1 > 0 ? A[i1-1][j1] : 0);
                    j1++;
                    if (s==target)
                        System.out.println(String.format("Found between (%d,%d) and (%d,%d)", i1, j1, i2, j2));
                }
            }
        }
    }
}
于 2013-03-18T02:41:16.337 に答える