c++ - 从图片中检测最暗的固定大小正方形

Question

我有一张 2600x2600 的灰色图片。或者它可以看作是一个无符号短矩阵。我想找到最暗（或通过计算反向图片最亮）的正方形具有固定大小 N。N 可以参数化（如果有多个最暗的正方形，我想要全部）。

我使用opencv读取了图像中矩形明亮区域的检测， 但它需要一个我没有的阈值，此外我搜索一个固定大小。

有没有人可以在 c++ 或 python 中找到它？

Answer 1

For each row of the image,
    Add up the N consecutive pixels, so you get W - N + 1 pixels.
For each column of the new image,
    For each consecutive sequence of N pixels, (H - N + 1)
        Add them up and compare to the current best.

要将每个连续的像素序列相加，您可以减去最后一个像素，然后添加下一个像素。

如果可以修改，您还可以重用图像数组作为存储。如果没有，内存优化将只存储最新的列，并在第一个循环中的每个步骤中遍历它。

运行时间：O( w · h )

这是 C# 中的一些代码，用于演示这一点（忽略像素格式和任何潜在的溢出）：

List<Point> FindBrightestSquare(int[,] image, int N, out int squareSum)
{
    int width = image.GetLength(0);
    int height = image.GetLength(1);
    if (width < N || height < N)
    {
        return false;
    }

    int currentSum;
    for (int y = 0; y < height; y++)
    {
        currentSum = 0;
        for (int x = 0; x < width; x++)
        {
            currentSum += image[x,y];
            if (x => N)
            {
                currentSum -= image[x-N,y];
                image[x-N,y] = currentSum;
            }
        }
    }

    int? bestSum = null;
    List<Point> bestCandidates = new List<Point>();
    for (int x = 0; x <= width-N; x++)
    {
        currentSum = 0;
        for (int y = 0; y < height; y++)
        {
            currentSum += image[x,y];
            if (y >= N)
            {
                currentSum -= image[x, y-N];
                if (bestSum == null || currentSum > bestSum)
                {
                    bestSum = currentSum;
                    bestCandidates.Clear();
                    bestCandidates.Add(new Point(x, y-N));
                }
                else if (currentSum == bestSum)
                {
                    bestCandidates.Add(new Point(x, y-N));
                }
            }
        }
    }

    squareSum = bestSum.Value;
    return bestCandidates;
}

Answer 2

您可以增加阈值，直到找到一个正方形，然后使用 2D FSM 来检测正方形。

这将产生匹配O(width * height * bpp)（在可能的最低阈值上进行二进制搜索，假设是二次幂范围）：

- set threshold to its maximum value 
- for every bit of the threshold
  - clear the bit in the threshold
  - if there is a match
    - record the set of matches as a result
  - else
    - set the bit
- if there is no record, then the threshold is its maximum.

to detect a square:
- for every pixel:
  - if the pixel is too bright, set its line-len to 0
  - else if it's the first column, set its line-len to 1
  - else set its line-len to the line-len of the pixel to the left, plus one

  - if the pixel line-len is less than N, set its rect-len to 0
  - else if it's the first row, set its rect-len to 1
  - else set its rect-len to the rect-len of the pixel above, plus one

  - if the rect-len is at least N, record a match.

line-len表示足够暗的连续像素的数量。

rect-len表示足够长且对齐的连续暗像素行数。

对于视频捕获，将二进制搜索替换为从前一帧的阈值开始的线性搜索。

显然，你不可能比theta(width/N * height/N)最好的情况更好（因为你必须排除每个可能的位置以获得较暗的正方形）并且可以假设位深度是恒定的，所以这个算法对于固定的 N 是渐近最优的。它可能是作为输入的一部分，N 也是渐近最优的，因为（直观地）您必须考虑平均情况下的几乎每个像素。