从图片中检测最黑的固定尺寸的方块

Question

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

我读detection-of-rectangular-bright-area-in-a-image-using-opencv 但它需要一个我没有的阈值，此外我搜索一个固定的大小。

任何人都可以用C++或python找到它吗？

Answer 1

您可以增加阈值，直到找到方形，并使用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作为输入的一部分，因为（直观地）你必须考虑平均情况下的几乎每个像素。

Answer 2

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（瓦特＆middot; ħ）

这里是在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; 
}