5

我试图通过比较源图像和图案图像中像素的平均颜色来解决图像匹配问题。我已将此问题简化为子数组求和问题，但无法找到解决方法。

假设我有一个所有正整数的二维数组 ARR。我有一个数字 x（这是小图案图像中像素颜色的平均值）。我只需要在 ARR 中找到任何具有确切总和 x 的子数组。我发现了一个类似的问题，可以在这里用动态编程解决。

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 回答