C++で黒いピクセルを囲む最小の長方形の面積を求める方法

問題の概要

ある画像が2値行列で表現されていると考えます。0は白ピクセル、1は黒ピクセルを表します。ここで、黒いピクセル同士は上下左右に連結しており、黒い領域はちょうど1つだけ存在するものとします。黒いピクセルのうち1つの座標 (x, y) が与えられたとき、すべての黒いピクセルを囲む最小の(軸に平行な)長方形の面積を求めるのが目的です。

例えば、入力が次のような場合を考えてみましょう。

このとき x = 0、y = 2 とすると、出力は 6 になります。

解き方の手順

この問題は二分探索を応用することで効率的に解けます。既知の黒ピクセル (x, y) を基準に、上・下・左・右それぞれの方向へ境界を二分探索で絞り込んでいくのがポイントです。具体的な手順は以下の通りです。

• 2次元配列 v を定義します。

• 関数 searchRows() を定義します。引数は i、j、left、right、one です。

• i < j の間、以下を繰り返します。

  • mid := i + (j - i) / 2

  • k := left

  • k < right かつ v[mid][k] が '0' である間、k を1ずつ増やします。

  • (k < right) が one と等しい場合、j := mid とします。

  • それ以外の場合は i := mid + 1 とします。

• i を返します。

• 関数 searchColumn() を定義します。引数は i、j、top、bottom、one です。

• i ≠ j の間、以下を繰り返します。

  • mid := i + (j - i) / 2

  • k := top

  • k < bottom かつ v[k][mid] が '0' である間、k を1ずつ増やします。

  • (k < bottom) が one と等しい場合、j := mid とします。

  • それ以外の場合は i := mid + 1 とします。

• i を返します。

• mainメソッドでは以下を実行します。

• v := image とします。

• n := image の行数、m := image の列数とします。

• top := searchRows(0, x, 0, m, true)

• bottom := searchRows(x + 1, n, 0, m, false)

• left := searchColumn(0, y, top, bottom, true)

• right := searchColumn(y + 1, m, top, bottom, false)

• (right - left) * (bottom - top) を返します。

まず、既知の座標より上側と下側をそれぞれ二分探索して黒ピクセルが存在する最も外側の行(top・bottom)を特定し、続いてその範囲内で左側と右側を二分探索して境界列(left・right)を求めます。最後に幅と高さを掛け合わせれば、最小の長方形の面積が得られます。

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector < vector <char> > v;
    int searchRows(int i, int j, int left, int right, bool one){
        while (i < j) {
            int mid = i + (j - i) / 2;
            int k = left;
            while (k < right && v[mid][k] == '0')
                k++;
            if (k < right == one) {
                j = mid;
            }
            else {
                i = mid + 1;
            }
        }
        return i;
    }
    int searchColumn(int i, int j, int top, int bottom, bool one){
        while (i != j) {
            int mid = i + (j - i) / 2;
            int k = top;
            while (k < bottom && v[k][mid] == '0')
                k++;
            if (k < bottom == one) {
                j = mid;
            }
            else {
                i = mid + 1;
            }
        }
        return i;
    }
    int minArea(vector<vector<char>>& image, int x, int y) {
        v = image;
        int ret = 0;
        int n = image.size();
        int m = image[0].size();
        int top = searchRows(0, x, 0, m, true);
        int bottom = searchRows(x + 1, n, 0, m, false);
        int left = searchColumn(0, y, top, bottom, true);
        int right = searchColumn(y + 1, m, top, bottom, false);
        return (right - left) * (bottom - top);
    }
};
main(){
    Solution ob;
    vector<vector<char>> v =
    {{'0','0','1','0'},{'0','1','1','0'},{'0','1','0','0'}};
    cout << (ob.minArea(v, 0, 2));
}

入力

{{'0','0','1','0'},{'0','1','1','0'},{'0','1','0','0'}}, 0, 2

出力

6

計算量について

このアルゴリズムの時間計算量は O(m log n + n log m)(nは行数、mは列数)です。すべてのピクセルを順に走査する O(n × m) の素朴な手法と比べ、画像サイズが大きい場合でも高速に動作する点が大きな利点です。