合計面積表

合計領域テーブルは、グリッドの長方形のサブセット内の値の合計を迅速かつ効率的に生成するためのデータ構造とアルゴリズムです。画像処理分野では、積分画像とも呼ばれます。 1984年にフランク・クロウによってミップマップで使用するためにコンピュータグラフィックスに導入されました。コンピュータビジョンでは、ルイス^[1]によって普及し、「積分画像」という名前が付けられ、 2001年にビオラ・ジョーンズの物体検出フレームワークで広く使用されました。歴史的に、この原理は多次元確率分布関数の研究、つまりそれぞれの累積分布関数から2D（またはND）確率（確率分布の下の領域）を計算する際に非常によく知られています。^[2]

名前が示すように、合計面積表の任意の点（ x、  y ）の値は、（ x、  y）の上と左にあるすべてのピクセルの合計です。^{[3] [4]} ここで、は（ x、y） のピクセルの値です。$${\displaystyle I(x,y)=\sum _{\begin{smallmatrix}x'\leq x\\y'\leq y\end{smallmatrix}}i(x',y')}$$${\displaystyle i(x,y)}$

合計面積表は、画像上の1回のパスで効率的に計算できます。合計面積表の（ x、  y）の値は次のように表されます。 ^[5] （合計行列は左上隅から計算されることに注意してください） $${\displaystyle I(x,y)=i(x,y)+I(x,y-1)+I(x-1,y)-I(x-1,y-1)}$$

合計面積テーブルが計算されると、任意の長方形領域上の強度の合計を評価するには、領域のサイズに関係なく、正確に 4 つの配列参照が必要になります。つまり、右の図の表記では、A = ( x ₀ , y ₀ )、B = ( x ₁ , y ₀ )、C = ( x ₀ , y ₁ )、D = ( x ₁ , y ₁ )であり、 A、B、C 、およびDで囲まれた長方形上のi ( x、y )の合計は次のようになります。 $${\displaystyle \sum _{\begin{smallmatrix}x_{0}}x\leq x_{1}\\y_{0}}y\leq y_{1}\end{smallmatrix}}i(x,y)=I(D)+I(A)-I(B)-I(C)}$$

この方法は連続領域にも自然に拡張される。^[2]

この方法は高次元画像にも拡張できます。^[6]長方形の角が内にある場合、長方形に含まれる画像値の合計は、 における積分画像、画像の次元 である式で計算されます。この例では、表記は、、、に対応します。たとえば、神経画像処理では、ボクセルまたはタイムスタンプ付きボクセルを 使用する場合、画像の次元はまたはになります。${\displaystyle x^{p}}$${\displaystyle p}$${\displaystyle \{0,1\}^{d}}$$${\displaystyle \sum _{p\in \{0,1\}^{d}}(-1)^{d-\|p\|_{1}}I(x^{p})}$$${\displaystyle I(x)}$${\displaystyle x}$${\displaystyle d}$${\displaystyle x^{p}}$${\displaystyle d=2}$${\displaystyle A=x^{(0,0)}}$${\displaystyle B=x^{(1,0)}}$${\displaystyle C=x^{(1,1)}}$${\displaystyle D=x^{(0,1)}}$${\displaystyle d=3}$${\displaystyle d=4}$

^{この方法は、Phanらの研究[7]}のように高次積分画像に拡張されており、画像内の局所ブロックの標準偏差（分散）、歪度、尖度を迅速かつ効率的に計算するために2つ、3つ、または4つの積分画像を提供している。詳細は以下に示すとおりである。

ブロックの 分散または標準偏差を計算するには、次の 2 つの積分画像が必要です。 分散は次のように求められます 。ブロックのとの合計をそれぞれ およびとし ます。およびは、積分画像によって簡単に計算されます。次に、分散方程式を次のように操作します。 ここで、 および です。 $${\displaystyle I(x,y)=\sum _{\begin{smallmatrix}x'\leq x\\y'\leq y\end{smallmatrix}}i(x',y')}$$ $${\displaystyle I^{2}(x,y)=\sum _{\begin{smallmatrix}x'\leq x\\y'\leq y\end{smallmatrix}}i^{2}(x',y')}$$$${\displaystyle \operatorname {Var} (X)={\frac {1}{n}}\sum _{i=1}^{n}(x_{i}-\mu )^{2}.}$$${\displaystyle S_{1}}$${\displaystyle S_{2}}$${\displaystyle ABCD}$${\displaystyle I}$${\displaystyle I^{2}}$${\displaystyle S_{1}}$${\displaystyle S_{2}}$$${\displaystyle {\begin{aligned}\operatorname {Var} (X)&={\frac {1}{n}}\sum _{i=1}^{n}\left(x_{i}^{2}-2\mu x_{i}+\mu ^{2}\right)\\[1ex]&={\frac {1}{n}}\left[\sum _{i=1}^{n}x_{i}^{2}-2\sum _{i=1}^{n}\mu x_{i}+\sum _{i=1}^{n}\mu ^{2}\right]\\[1ex]&={\frac {1}{n}}\left[\sum _{i=1}^{n}x_{i}^{2}-2\sum _{i=1}^{n}\mu x_{i}+n\mu ^{2}\right]\\[1ex]&={\frac {1}{n}}\left[\sum _{i=1}^{n}x_{i}^{2}-2\mu \sum _{i=1}^{n}x_{i}+n\mu ^{2}\right]\\[1ex]&={\frac {1}{n}}\left[S_{2}-2{\frac {S_{1}}{n}}S_{1}+n\left({\frac {S_{1}}{n}}\right)^{2}\right]\\[1ex]&={\frac {1}{n}}\left[S_{2}-{\frac {S_{1}^{2}}{n}}\right]\end{aligned}}}$$${\displaystyle \mu =S_{1}/n}$${\textstyle S_{2}=\sum _{i=1}^{n}x_{i}^{2}}$

平均 ( ) と分散 ( ) の推定と同様に、それぞれ画像の 1 乗と 2 乗の積分画像 (つまり) が必要ですが、上記と同様の操作を画像の 3 乗と 4 乗 (つまり) に対して行うことで、歪度と尖度を取得できます。^{[7]ただし、F Shafait ら[8} ] が述べているように、上記の方法では、32 ビット整数を使用する場合に高次の積分画像で整数オーバーフローが発生するという重要な実装の詳細 に留意する必要があります。${\displaystyle \mu }$${\displaystyle \operatorname {Var} }$${\displaystyle I,I^{2}}$${\displaystyle I^{3}(x,y),I^{4}(x,y)}$

オーバーフローなしで予想される最大の合計に対応するために、合計のデータ型は元の値に使用されたデータ型とは異なっており、それよりも大きい必要がある場合があります。浮動小数点データの場合、補正された合計を使用してエラーを減らすことができます。

• プレフィックス合計

• 物体検出における合計テーブルの実装

• 積分画像アルゴリズムの理論の紹介
• Wolfram Demonstrations Project による積分画像アルゴリズムの連続バージョンのデモンストレーション