超出范围且复杂度恒定的数组中子集的平均值

Question

这是我上一期关于复杂度为 o(1) 的二维数组处理技术的后续问题。

即获取数组子集的平均值，但如果该子集超出数组边界，则将其视为零。这是一个二维数组。

实际上，数组可以达到 [2000][2000]，但为了简单起见，我们采用大小为 [4][4] 的二维数组。

array[4][4] = {0,  1,  2,  3
               4,  5,  6,  7
               8,  9,  10, 11
               12, 13, 14, 15}

现在假设我想得到 [2][2] 和 [3][3] 之间的数组之和，即加上 10 + 11 + 14 + 15 再除以四。这可以通过使用 'summed area table' 或 'integral image' 技术在 o(1) 解决方案中完成。

然而，我对如何保持这种 o(1) 复杂度感到困惑 providing/when:

数组子集扩展到实际数组之外
实际数组之外的数组索引取为零。
算法计算仍然是o(1)

例如，对于这个像素总和，我被要求得到 [2][2] 到 [4][4] 的总和。这有一个理论数组，实际之外的数字表示为 f（假）但被视为零：

array_theory[5][5] = {0,  1,  2,  3,  0f
                      4,  5,  6,  7,  0f
                      8,  9,  10, 11, 0f
                      12, 13, 14, 15, 0f
                      0f, 0f, 0f, 0f, 0f}

或在图像中：

所以现在 [2][2] 和 [4][4] 之间的平均值是 (10 + 11 + 0f + 14 + 15 + 0f + 0f + 0f + 0f)/ 9

我想我必须使用某种过滤器或图像处理技术，我似乎无法找到一个关键字来允许我 find/implement 它并在我的搜索结果中调情它。

如有任何帮助，我们将不胜感激！

Answer 1

要将其扩展到数组的更大边缘之外，只需将项限制为最大值：如果任何下标超出数组的最后一个有效索引，则将其替换为数组的最后一个有效索引。

我们可以定义一个辅助函数来访问sums:

/*  Return sums[i][j] from an array that is physically r rows and c columns
    but is conceptually extended infinitely on all four sides as if
    arrays[i][j] contained zeros for all elements outside the physical
    array.
*/
Type Sums(ssize_t r, ssize_t c, Type sums[r][c], ssize_t i, ssize_t j)
{
    if (i < 0 || j < 0) return 0;
    if (r <= i) i = r-1;
    if (c <= j) j = c-1;
    return sums[i][j];
}

那么从array[i0][j0]到array[i1][j1]的子数组元素之和就是Sums[i1][j1] - Sums[i1][j0-1] - Sums[i0-1][j1] + Sums[i0-1][j0-1]，平均当然是(Sums[i1][j1] - Sums[i1][j0-1] - Sums[i0-1][j1] + Sums[i0-1][j0-1]) / ((j1-j0+1) * (i1-i0+1)).

超出范围且复杂度恒定的数组中子集的平均值

Average of a subset in an array which is out of bounds with constant complexity

c

arrays

pixel