積分画像の原理・計算式・高速化

この記事では、積分画像の基本原理や計算式・特徴・例題についてまとめました。

積分画像
積分画像による高速化
高速化の原理
定式化

積分画像

積分画像（Integral Image）は、注目画素とその左と上にある全ての画素値の和を求めた物です。

例えば、入力画像 $I$ が与えられた場合

(1) $\begin{eqnarray*} I= \left[ \begin{array}{ccccc} I(0,0) & I(1,0) & I(2,0)\\ I(0,1) & I(1,1) & I(2,1)\\ I(0,2) & I(1,2) & I(2,2)\\ \end{array} \right] \end{eqnarray*}$

積分画像 $I'$ の画素値は次のように計算します。

(2) $\begin{eqnarray*} I'= \left[ \begin{array}{ccccc} I'(0,0) & I'(1,0) & I'(2,0)\\ I'(0,1) & I'(1,1) & I'(2,1)\\ I'(0,2) & I'(1,2) & I'(2,2)\\ \end{array} \right] \end{eqnarray*}$

(3) $\begin{eqnarray*} I'(0,0)&=&I(0,0)\\ I'(1,0)&=&I(0,0)+I(1,0)\\ I'(2,0)&=&I(0,0)+I(1,0)+I(2,0)\\ I'(0,1)&=&I(0,0)+I(1,0)\\ I'(1,1)&=&I(0,0)+I(1,0)+I(0,1)+I(1,1)\\ I'(2,1)&=&I(0,0)+I(1,0)+I(0,1)+I(1,1)+I(2,0)+I(2,1)\\ I'(0,2)&=&I(0,0)+I(0,1)+I(0,2)\\ I'(1,2)&=&I(0,0)+I(0,1)+I(0,1)+I(1,0)+I(1,1)+I(1,2)\\ I'(2,2)&=&I(0,0)+I(0,1)+I(0,1)+I(1,0)+I(1,1)+I(1,2)\\ &+&I(2,0)+I(2,1)+I(2,2)\\ \end{eqnarray*}$

積分画像による高速化

積分画像は近傍画素の処理の高速化によく使われます。

例えば、注目画素と8近傍の計9画素の画素値の総和を求めたいとします。
普通に計算すると、「画素値の取り出し9回」と「加算8回」を行う必要があります。

ところが、あらかじめ積分画像を作っておけば、「画素値の取り出し4回」と「加算1回+減算2回」で済ませることができます。
その理由は、次の節で解説します。

高速化の原理

赤色領域（注目画素+8近傍の画素）にある画素値の総和 $S$ を求めます。

$S$ は以下の式で計算できます。

(4) $\begin{eqnarray*} S=S_1-S_2-S_3+S_4 \end{eqnarray*}$

$S_1$ から $S_2$ と $S_3$ を引き、引きすぎた分 $S_4$ を加算しています。
ここで、 $S_1, S_2, S_3, S_4$ は積分画像の画素値に等しくなります。

■積分画像 $I'$

(5) $\begin{eqnarray*} S_1=I'(3,3)\\ S_2=I'(0,3)\\ S_3=I'(3,0)\\ S_4=I'(0,0) \end{eqnarray*}$

よって、積分画像を先に作成しておけば、少ない計算回数（加算1回+減算2回）と画素へのアクセス回数(4回)で画素値の総和を計算できます。
それにより計算時間を大幅に抑えることができます。
近傍画素の個数が多くなったり、繰り返し回数が増えるほど、高速化の効果も大きくなります。

積分画像を使った高速化は、畳み込み演算や特徴量の計算などでよく利用されている重要なアルゴリズムです。

定式化

入力画像 $I$ とその積分画像 $I'$ があるとします。
このとき、左上座標 $(x, y)$ 、幅 $w$ , 高さ $h$ の矩形領域内にある画素値の総和 $S$ は次式で計算できます。

(6) $\begin{eqnarray*} S=I'(x+w,y+h)-I'(x,y+h)-I'(x+w, y)+I'(x,y) \end{eqnarray*}$

【関連記事】
【画像処理入門】アルゴリズム＆プログラミング