東京工業大学 工学院 情報通信系 2019年8月実施 S3 積分画像と矩形領域の平均・分散

标签：

• TITech
• Dynamic-Programming-Principle

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

幅 $W$，高さ $H$ の2次元テーブル $I(x,y)$ を考える。左上が $(0,0)$，右が $x$ 正方向，下が $y$ 正方向であり，1次元配列には行優先順で格納する。矩形 $\operatorname{Rect}(x_0,y_0,a,b)$ は左上 $(x_0,y_0)$，幅 $a$，高さ $b$ で，範囲内にあるものとする。例のテーブルは

$$I=\begin{pmatrix} 6&7&5&6&2&7&1\\ 2&3&7&2&5&3&4\\ 5&5&7&6&4&6&6\\ 5&2&4&2&3&6&7\\ 2&6&1&7&6&3&1\\ 1&2&2&3&5&4&4\\ 4&4&2&4&4&1&4 \end{pmatrix}.$$

1. a) $\operatorname{Rect}(4,3,2,2)$ の総和を求めよ。 b) 行ごとに矩形を走査し s = s + I[i] と加算する RectSum1 の初期値 s=(1) と添字 i=(2) を埋めよ。
2. $K(x,y)=\sum_{q=0}^{y}\sum_{p=0}^{x}I(p,q)$ とする。 a) $K(0,5),K(3,3)$ を求めよ。 b) 下記 Convert の（3）～（6）を埋めよ。
3. $x_0,y_0\ge1$ とし，下記 RectSum2 の（7）～（10）を埋め，正しさを述べよ。$W=H=7,a=b=3$ のとき，加減算回数のみを数えると，前計算して RectSum2 を使う方が少なくなるのは何個以上の矩形を求めるときか。
4. 多数の矩形の平均と分散を少ない加減算で計算するための前処理と計算方法を述べよ。

Convert(I, W, H, K) {
    for (y = 0; y < H; y++) {
        s = /* 3 */;
        for (x = 0; x < W; x++) {
            i = /* 4 */;
            s = /* 5 */;
            if (y == 0) K[i] = s;
            else K[i] = /* 6 */;
        }
    }
}
RectSum2(K, W, H, x0, y0, a, b) {
    i0 = /* 7 */; i1 = /* 8 */;
    i2 = /* 9 */; i3 = /* 10 */;
    s = K[i0] + K[i1] - K[i2] - K[i3];
    return s;
}

题目描述

建立二维前缀和（积分图），用四个角值求矩形和，比较预处理与逐点求和的加减法次数，并扩展到区域均值和方差。

Kai

1)

対象は $3,6,6,3$ の4要素であるから総和は $\boxed{18}$。空欄は

$$\boxed{(1)=0,\qquad(2)=yW+x}.$$

2)

$$\boxed{K(0,5)=6+2+5+5+2+1=21},\qquad \boxed{K(3,3)=24+14+23+13=74}.$$

空欄	式
3	0
4	y * W + x
5	s + I[i]
6	s + K[i-W]

$s$ は現在行の $0$ 列から $x$ 列までの和であり，上の行までの累積和を足すことで $K(x,y)$ となる。

3)a)

$x_1=x_0+a-1$, $y_1=y_0+b-1$ とおけば

$$S=K(x_1,y_1)+K(x_0-1,y_0-1)-K(x_1,y_0-1)-K(x_0-1,y_1).$$

全体から上部と左部を引き，二重に引いた左上を戻す式である。したがって

空欄	式
7	(y0+b-1)*W + x0+a-1
8	(y0-1)*W + x0-1
9	(y0-1)*W + x0+a-1
10	(y0+b-1)*W + x0-1

3)b)

矩形の数を $r$ とする。RectSum1 は1矩形あたり9回なので $9r$ 回。 Convert は行累積の加算 $49$ 回と上の行との加算 $42$ 回で $91$ 回，RectSum2 は1矩形あたり3回。ゆえに

$$91+3r<9r\iff r>\frac{91}{6}.$$

したがって $\boxed{16\text{ 個以上}}$。

4)

$I$ の積分画像 $K_1$ に加え，要素を二乗した $I^2$ の積分画像 $K_2$ を前計算する。矩形の要素数を $n=ab$ とし，RectSum2 を各画像に適用して

$$S_1=\sum I,\qquad S_2=\sum I^2$$

を得れば

$$\boxed{\mu=\frac{S_1}{n},\qquad \operatorname{Var}=\frac{S_2}{n}-\left(\frac{S_1}{n}\right)^2}.$$

前処理は $O(WH)$，各矩形は $O(1)$。前処理後の加減算は二つの矩形和に6回，分散の差に1回の計7回となる。