c++ - 画像から最も暗い固定サイズの正方形を検出

Question

グレーの 2600x2600 の写真があります。または、unsigned short の行列と見なすこともできます。最も暗い (または逆の画像を計算して最も明るい) 正方形を見つけたいと思いますが、固定サイズ 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)ます (2 のべき乗の範囲を想定して、可能な限り低いしきい値でのバイナリ検索)。

- 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 に対しても漸近的に最適です。