読者です 読者をやめる 読者になる 読者になる

のんびりしているエンジニアの日記

ソフトウェアなどのエンジニア的な何かを書きます。

画像処理 Integral Image(積分画像)

Sponsored Links

皆さんこんにちは
お元気ですか。私は元気です。

今日は画像処理で使われるアルゴリズムIntegral Imageをご紹介します。
微分画像と異なって、イメージ図を出すことはできません。

Integral Imageとは?

説明するより見せて説明するのが楽です。
・通常の画像

1 2 4 3
3 10 10 4
5 5 2 3

・積分画像

1 3 7 10
4 16 30 37
9 26 42 52

画像の座標の左と上と自身のピクセルを足したものをその座標のピクセルの値とする感じです。
例えば、積分画像の左から2番目、上から2番めのピクセル(積分画像:16)を求めるには

16 = 1 + 2 + 3 + 10です。

積分画像を求めることに何かいいことあるの?

f:id:tereka:20141116000642p:plain

この中でA4のピクセルの合計を求めたいとします。
積分画像を用いると定数倍で求めることができます

どういうことかといいますと、通常だとH x Wの回数だけの加算が必要です。
これをかなりの回数必要となるとさらにN回かける必要があり、時間が必要となる計算となります。

Integral Imageを利用とすると
A4 = A4 - A3 + A2 - A1の計算をすることで求めることができます。
ということはN * K(A4計算)回数で求めることができます。

もちろん、Integral Image計算のことは何も考えていませんが・・・

因みに二乗和とかでも計算は可能なので、目的に応じて変更してみましょう

Algorithm

積分画像を求めてみましょう。
f:id:tereka:20141116210729p:plain

画像上の(X,Y)を求めるには、A2部分とA3部分そしてA1と自分自身を足せば良いことになります。
自分の一つ上と自分の左を足し、かぶっているA1部分を引き、自分自身を足すことで完成します。

積分画像(X-1,Y) + 積分画像(X,Y-1)ー積分画像(X-1,Y-1)+画像(X,Y)を計算することによって算出できます。

ソースコード

#include <iostream>
#include <opencv2/opencv.hpp>
#include <opencv2/highgui/highgui.hpp>

using namespace std;
using namespace cv;

Mat calcIntegralImage(Mat &image){
	Mat IntegralImage = Mat::zeros(3, 3,CV_64FC1);

	for(int h = 0; h < image.rows; h++){
		for(int w = 0; w < image.cols; w++){
			/**
			Integral Imageの計算
			**/
			//一番左上の時
			int nh = h - 1;
			int nw = w - 1;
			int integral_pixel = 0;
			//エリア内に入っている
			cout << IntegralImage.at<double>(h,w) << endl;
			if(nh >= 0 && nw >= 0){
				IntegralImage.at<double>(h,w) -= IntegralImage.at<double>(nh,nw);
			}

			if(nh >= 0){
				IntegralImage.at<double>(h,w) += IntegralImage.at<double>(nh,w);
			}

			if(nw >= 0){
				IntegralImage.at<double>(h,w) += IntegralImage.at<double>(h,nw);
			}

			IntegralImage.at<double>(h,w) += image.at<double>(h,w);
		}
	}
	return IntegralImage;
}

int main(int argc, char const *argv[])
{
	double data[3][3] = { {1.0, 2.0, 3.0}, {3.0, 1.0, 5.0}, {2.0, 6.0, 9.0} };
	Mat m3(3,3,CV_64FC1,data);
	cout << m3 << endl;
	cout << calcIntegralImage(m3) << endl;
	return 0;
}
広告を非表示にする