合計面積表
6×6行列（1. ）の合計面積表（2. ）を使用して、その値のサブ長方形を合計します。各色のスポットは、その色の長方形内の合計を強調表示します。

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

アルゴリズム

名前が示すように、合計領域テーブル内の任意の点（ x、  y ）の値は、（ x、  y）の上と左にあるすべてのピクセルの合計です。[ 3 ] [ 4 ] ここで、は（ x、y ）のピクセルの値です。 私（×、y）＝∑×′≤×y′≤y私（×′、y′）{\displaystyle I(x,y)=\sum _{\begin{smallmatrix}x'\leq x\\y'\leq y\end{smallmatrix}}i(x',y')}私（×、y）{\displaystyle i(x,y)}

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

合計面積表データ構造/アルゴリズムにおける合計計算の説明

合計面積テーブルが計算されると、任意の長方形領域における強度の合計を評価するには、領域のサイズに関わらず、正確に4つの配列参照が必要です。つまり、右図のA = ( x 0 , y 0 )、B = ( x 1 , y 0 )、C = ( x 0 , y 1 )、D = ( x 1 , y 1 )の表記において、 A、B、C 、 Dで囲まれた長方形領域におけるi ( x、y )の合計は次のようになります。 ∑×0<×≤×1y0<y≤y1私（×、y）＝私（D）+私（あ）−私（B）−私（C）{\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 ]長方形の角が の範囲内にある場合、長方形に含まれる画像値の合計は次式で計算される。 ここで はにおける積分画像であり、画像の次元である。この例では、表記は、、、に対応する。例えば、神経画像では、ボクセルまたはタイムスタンプ付きボクセル を使用する場合、画像の次元はまたはとなる。×p{\displaystyle x^{p}}p{\displaystyle p}{0、1}d{\displaystyle \{0,1\}^{d}}∑p∈{0、1}d（−1）d−‖p‖1私（×p）{\displaystyle \sum _{p\in \{0,1\}^{d}}(-1)^{d-\|p\|_{1}}I(x^{p})}私（×）{\displaystyle I(x)}×{\displaystyle x}d{\displaystyle d}×p{\displaystyle x^{p}}d＝2{\displaystyle d=2}あ＝×（0、0）{\displaystyle A=x^{(0,0)}}B＝×（1、0）{\displaystyle B=x^{(1,0)}}C＝×（1、1）{\displaystyle C=x^{(1,1)}}D＝×（0、1）{\displaystyle D=x^{(0,1)}}d＝3{\displaystyle d=3}d＝4{\displaystyle d=4}

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

ブロックの 分散または標準偏差を計算するには、2つの積分像が必要です。 分散は次のように与えられます 。ブロックのと の和をそれぞれ と とします。と は積分像によって簡単に計算できます。ここで、分散方程式を次のように操作します。 ここで、 と です。 私（×、y）＝∑×′≤×y′≤y私（×′、y′）{\displaystyle I(x,y)=\sum _{\begin{smallmatrix}x'\leq x\\y'\leq y\end{smallmatrix}}i(x',y')}私2（×、y）＝∑×′≤×y′≤y私2（×′、y′）{\displaystyle I^{2}(x,y)=\sum _{\begin{smallmatrix}x'\leq x\\y'\leq y\end{smallmatrix}}i^{2}(x',y')}ヴァール⁡（X）＝1n∑私＝1n（×私−μ）2。{\displaystyle \operatorname {Var} (X)={\frac {1}{n}}\sum _{i=1}^{n}(x_{i}-\mu )^{2}.}S1{\displaystyle S_{1}}S2{\displaystyle S_{2}}あBCD{\displaystyle ABCD}私{\displaystyle I}私2{\displaystyle I^{2}}S1{\displaystyle S_{1}}S2{\displaystyle S_{2}}ヴァール⁡（X）＝1n∑私＝1n（×私2−2μ×私+μ2）＝1n[∑私＝1n×私2−2∑私＝1nμ×私+∑私＝1nμ2]＝1n[∑私＝1n×私2−2∑私＝1nμ×私+nμ2]＝1n[∑私＝1n×私2−2μ∑私＝1n×私+nμ2]＝1n[S2−2S1nS1+n（S1n）2]＝1n[S2−S12n]{\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}}}μ＝S1/n{\displaystyle \mu =S_{1}/n}S2＝∑私＝1n×私2{\textstyle S_{2}=\sum _{i=1}^{n}x_{i}^{2}}

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

実装上の考慮事項

2ビットグレースケールピクセルアート（左半分）の積分画像（右半分）。視認性を高めるために正規化および拡大されている。

オーバーフローなしで予想される最大の合計値に対応するために、合計のデータ型は元の値のデータ型とは異なり、より大きくする必要があるかもしれません。浮動小数点データの場合、補正加算を使用することで誤差を減らすことができます。

参照

参考文献

  1. ^ Lewis, JP (1995).高速テンプレートマッチング. Proc. Vision Interface . pp.  120– 123.
  2. ^ a b Finkelstein, Amir; neeratsharma (2010). 「累積分布関数の値の合計による二重積分」 Wolframデモンストレーションプロジェクト.
  3. ^ Crow, Franklin (1984). 「テクスチャマッピングのための合計面積テーブル」 . SIGGRAPH '84: Proceedings of the 11th annual conference on Computer graphics and interactive techniques . pp.  207– 212. doi : 10.1145/800031.808600 .
  4. ^ Viola, Paul; Jones, Michael (2002). 「ロバストなリアルタイム物体検出」(PDF) . International Journal of Computer Vision .
  5. ^ BADGERATI (2010年9月3日). 「コンピュータビジョン – インテグラルイメージ」 . computersciencesource.wordpress.com . 2017年2月13日閲覧。
  6. ^ Tapia, Ernesto (2011年1月). 「高次元積分画像の計算に関する注記」. Pattern Recognition Letters . 32 (2): 197– 201. Bibcode : 2011PaReL..32..197T . doi : 10.1016/j.patrec.2010.10.007 .
  7. ^ a b Phan, Thien; Sohoni, Sohum; Larson, Eric C.; Chandler, Damon M. (2012年4月22日). 「パフォーマンス分析に基づく画質評価の高速化」. 2012 IEEE Southwest Symposium on Image Analysis and Interpretation (PDF) . pp.  81– 84. CiteSeerX 10.1.1.666.4791 . doi : 10.1109/SSIAI.2012.6202458 . hdl : 11244/25701 . ISBN  978-1-4673-1830-3. S2CID  12472935 .
  8. ^ Shafait, Faisal; Keysers, Daniel; M. Breuel, Thomas (2008年1月). Yanikoglu, Berrin A.; Berkner, Kathrin (編). 「積分画像を用いた局所適応閾値処理技術の効率的な実装」(PDF) . Electronic Imaging . Document Recognition and Retrieval XV. 6815 : 681510–681510–6. Bibcode : 2008SPIE.6815E..10S . CiteSeerX 10.1.1.109.2748 . doi : 10.1117/12.767755 . S2CID 9284084 .  

講義ビデオ

「 https://en.wikipedia.org/w/index.php?title=Summed-area_table&oldid=1317500496」より取得