跳到主要内容

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

标签：

Author​

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

Description​

S3. 幅 WW，高さ HH（ともに1以上の整数）の2次元テーブルを考える。要素の場所は整数座標 (x,y)(x,y) で表し，左上隅を原点 (0,0)(0,0)，右を xx 正方向，下を yy 正方向とする。座標 (x,y)(x,y) の要素を I(x,y)I(x,y) とする。図 S3.1 は W=H=7W=H=7 の例であり，行が yy，列が xx に対応する。

I=(6756271237253455764665242367261763112235444422414).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&2&4&1&4 \end{pmatrix}.

例えば I(0,0)=6I(0,0)=6，I(3,4)=7I(3,4)=7 である。疑似コードの配列添字は0から始まる。疑似コード中の変数は立体で表し，式などに現れるその他の変数は斜体で表す。

  1. 矩形領域を，左上隅 (x0,y0)(x_0,y_0)，幅 aa，高さ bb の整数パラメータで定義し，Rect⁡(x0,y0,a,b)\operatorname{Rect}(x_0,y_0,a,b) と表す。図の斜線部分は Rect⁡(0,0,3,2)\operatorname{Rect}(0,0,3,2)，すなわち左上の3列2行である。矩形内の総和は

    S=∑y=y0y0+b−1∑x=x0x0+a−1I(x,y).(S3.1)S=\sum_{y=y_0}^{y_0+b-1}\sum_{x=x_0}^{x_0+a-1}I(x,y). \tag{S3.1}

    a) 図 S3.1 に対して Rect⁡(4,3,2,2)\operatorname{Rect}(4,3,2,2) 内の総和を求めよ。
    b) 次のアルゴリズム S3.2 の（1）（2）を埋めよ。テーブルは1次元配列に行優先順で格納する。すなわち原点から右へ走査し，端で下に1行進んで再び左端から右へ走査する。例の配列は 6,7,5,6,2,7,1,2,3,…,2,4,1,46,7,5,6,2,7,1,2,3,\ldots,2,4,1,4 となる。I は配列先頭のポインタ，I[i] は第 ii 要素，w,h は幅と高さ，x0,y0,a,b は矩形のパラメータである。矩形はテーブルの範囲内にある。

    RectSum1(I, w, h, x0, y0, a, b) {
        s = /* 1 */;
        for (y=y0; y<y0+b; y=y+1) {
            for (x=x0; x<x0+a; x=x+1) {
                i = /* 2 */;
                s = s + I[i];
            }
        }
        return s;
    }

  2. 次の変換によって矩形総和の計算量を削減することを考える。

    K(x,y)=∑q=0y∑p=0xI(p,q).(S3.2)K(x,y)=\sum_{q=0}^{y}\sum_{p=0}^{x}I(p,q). \tag{S3.2}

    a) 図 S3.1 について K(0,5),K(3,3)K(0,5),K(3,3) を求めよ。
    b) 次のアルゴリズム S3.3 の（3）～（6）を埋めよ。I,w,h は問1bと同じ意味で，変換後のテーブル K も同じ行優先順で1次元配列に格納する。

    Convert(I, w, h, K) {
        for (y=0; y<h; y=y+1) {
            s = /* 3 */;
            for (x=0; x<w; x=x+1) {
                i = /* 4 */;
                s = /* 5 */;
                if (y==0) { K[i] = s; }
                else { K[i] = /* 6 */; }
            }
        }
    }

  3. Convert で得た K を利用して矩形の総和を求める。x0,y0≥1x_0,y_0\ge1 とし，矩形は範囲内にある。

    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;
    }

    a) アルゴリズム S3.4 の（7）～（10）を埋め，この関数で総和が求まる理由を述べよ。
    b) RectSum1 の方法と，Convert と RectSum2 を組み合わせた方法を比較する。配列が関わる加減算の回数だけを数え，添字の計算，アクセス，代入は無視する。具体的には RectSum1 の s=s+I[i]，Convert の s=（5）と K[i]=（6），RectSum2 の総和式に注目する。c=d+e は1回，c=d+e-f-g は3回と数える。W=H=7,a=b=3W=H=7,a=b=3 のとき，何個以上の矩形の総和を計算すれば，Convert と RectSum2 の組合せの方が少ない加減算回数になるか。

  4. テーブル K を用いる方法を応用し，矩形内の要素の分散を求めるプログラムを作る。Convert と RectSum2 を変形して応用し，求める矩形が多いときに加減算の回数がなるべく少なくなる方法を簡潔に示せ。式を用いてよいが，疑似コードを示す必要はない。

题目描述​

宽 WW、高 HH 均为正整数。二维表左上角为 (0,0)(0,0)，向右为 xx 正方向，向下为 yy 正方向，元素记为 I(x,y)I(x,y)。图 S3.1 的完整7×7数据见上面的矩阵，行对应 yy，列对应 xx，例如 I(0,0)=6I(0,0)=6、I(3,4)=7I(3,4)=7。全部数组从0下标开始；伪代码中的变量用正体，公式等处的其它变量用斜体。

  1. Rect⁡(x0,y0,a,b)\operatorname{Rect}(x_0,y_0,a,b) 表示左上角为 (x0,y0)(x_0,y_0)、宽 aa、高 bb 的矩形，所有参数为整数。原图斜线区域为左上3列2行，即 Rect⁡(0,0,3,2)\operatorname{Rect}(0,0,3,2)。矩形和为 (S3.1)。
    a) 求 Rect⁡(4,3,2,2)\operatorname{Rect}(4,3,2,2) 的元素和。
    b) 补全 RectSum1 的（1）（2）。二维表按逐行从左至右的顺序存入一维数组；I 是首指针，I[i] 是第 ii 项，w,h 为宽、高，其余参数定义如上，且矩形不越界。
  2. 按 (S3.2) 定义从原点到 (x,y)(x,y) 的累积和 K(x,y)K(x,y)。
    a) 求例中的 K(0,5)K(0,5)、K(3,3)K(3,3)。
    b) 补全 Convert 的（3）～（6）。输出 K 也按相同的逐行顺序存入一维数组。
  3. 利用 K 求矩形和，另假设 x0,y0≥1x_0,y_0\ge1 且矩形不越界。
    a) 填写 RectSum2 的（7）～（10），解释为什么四项加减能够得到矩形和。
    b) 比较逐次调用 RectSum1 与先 Convert 再逐次调用 RectSum2。只计涉及数组的加减法次数，不计下标、访存和赋值；具体计数位置为上面所列四处语句，c=d+e 算1次，c=d+e-f-g 算3次。取 W=H=7,a=b=3W=H=7,a=b=3，求计算多少个及以上矩形时预处理方案的加减法次数更少。
  4. 扩展 Convert 与 RectSum2 的方法来计算矩形内元素的方差。对大量矩形，简要说明如何使加减法次数尽量少；可使用公式，无须写伪代码。

Kai​

1)​

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

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

2)​

K(0,5)=6+2+5+5+2+1=21,K(3,3)=24+14+23+13=74.\boxed{K(0,5)=6+2+5+5+2+1=21},\qquad \boxed{K(3,3)=24+14+23+13=74}.
空欄式
30
4y * w + x
5s + I[i]
6s + K[i-w]

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

3)a)​

x1=x0+a−1x_1=x_0+a-1, y1=y0+b−1y_1=y_0+b-1 とおけば

S=K(x1,y1)+K(x0−1,y0−1)−K(x1,y0−1)−K(x0−1,y1).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)​

矩形の数を rr とする。RectSum1 は1矩形あたり9回なので 9r9r 回。 Convert は行累積の加算 4949 回と上の行との加算 4242 回で 9191 回，RectSum2 は1矩形あたり3回。ゆえに

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

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

4)​

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

S1=∑I,S2=∑I2S_1=\sum I,\qquad S_2=\sum I^2

を得れば

μ=S1n,Var⁡=S2n−(S1n)2.\boxed{\mu=\frac{S_1}{n},\qquad \operatorname{Var}=\frac{S_2}{n}-\left(\frac{S_1}{n}\right)^2}.

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

本页目录