今回は画像特徴量の1つである高次局所自己相関特徴 (HLAC: Higher-order Local AutoCorrelation)について。
HLACは画像認識に対する基本的な要望としての位置不変性および加法性を満たすものであり、一次にとどまらない高次の相関に基づく統計的特徴量になっています。現在では様々なHLACの発展系が生まれていますが、今回はその基本となるアルゴリズムについて整理したいと思います。
基本アルゴリズム
自己相関関数を高次に拡張したN次の自己相関関数は、対象となる画像領域内の位置 r=(x, y) における画素値を f(r) とすると、その周りのN個の変位 a1, a2, …, aN に対して次式で定義されます。
基本的なHLAC特徴はこの関数に基づいた画像特徴で、実際には相関の次数を二次まで(3点相関)、変位も局所領域(3×3など)に限定して利用します。そのため変位のパターンは平行移動に関して等価なものを除くと35個のマスクパターンを用いて計算されます。ただし、HLACは2値画像(エッジ, シルエット画像等)を対象とすることも多いため、さらに等価なものを除くと以下の図に示す25パターンになります。HLACはこのパターンで示される画素値の積を画像全体で足し合わせるだけの簡単なアルゴリズムです。
このとき各パターンによる相関値も{0, 1}の2値となり、得られる特徴はパターンの生起頻度に一致します。これらのパターンはN + 1個の画素の共起パターンを示しているため、共起の方向や形状をパターン化してヒストグラムとして抽出する特徴量ということになります。つまり、一次相関(2点共起)では方向付けられた傾き、二次相関(3点共起)では方向付けられた曲率といった局所幾何学的特徴と解釈されます。
今回は基本的なHLACを試してみました。テスト画像(4枚)を以下に示します。
(クリックで原寸大、画像の番号 1,2,3,4 を振っておきます)
ブラウザ上で簡単に検証したかったので実装はJavaScriptで。テストデータと結果を保存しておくのにWeb Storageを、条件を変えることによって計算量が増えたときのためにWeb Workersが使えるのは便利です。いつもならActionScriptで書くところですが、問題を簡単に早く解ける方を僕は使っていくつもりです。全体のコードはgithubに上げておくのでもし興味があれば。
cvsandbox.js at master from wellflat/javascript-labs – GitHub
今回はサンドボックスパターンのモジュールとして書いたのでその部分を抜粋して載せます。Canvasの構造に依存する部分も入っているので注意してください。他の特徴量抽出法と比べると計算量は少ない部類に入りますね。
* HLAC: Higher-order Local AutoCorrelation
(Firefox 4, Chrome 11, Safari 5, Opera 11 で動作確認)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
/* features2d module */ CV.modules.features2d = function(self) { // HLAC self.hlac = function() { var p = self.constructor.prototype, w = p.bitmapData.width, // bitmapData: ImageData h = p.bitmapData.height, src = p.bitmapData.data, // CanvasPixelArray // mask patterns for HLAC (N:2, 3*3) mask = ['000010000','000011000','001010000','010010000','100010000', '000111000','001010100','010010010','100010001','001110000', '010010100','100010010','000110001','000011100','001010010', '010010001','100011000','010110000','100010100','000110010', '000010101','000011010','001010001','010011000','101010000'], len = mask.length, features = [], c, i, j, l, step, kstep, cmp = 0; // mask pattern, feature vector initialize for(var k=0; k<len; k++) { mask[k] = parseInt(mask[k], 2); features[k] = 0; } // product-sum operation for each mask pattern // CanvasPixelArray: [R0,G0,B0,A0,R1,G1,B1,A1, ...] for(k=0; k<len; k++) { for(var y=1; y<h-1; y++) { step = y*w; for(var x=1; x<w-1; x++) { i = (step + x) << 2; if(src[i] === cmp) continue; for(var ky=-1, l=8, c=1; ky<=1; ky++) { if(c === 0) break; kstep = ky*w; for(var kx=-1; kx<=1; kx++, l--) { j = (kstep + kx) << 2; if((mask[k] >> l & 1) && (src[i + j] === cmp)) { c = 0; break; } } } features[k] += c; } } } return features; }; }; |
まずはHLACの位置不変性を確認しました。位置情報を必要としないので以下のような結果になるはずです。
画像1の特徴ベクトル = 画像2の特徴ベクトル
類似度は25次元の特徴ベクトルに対するヒストグラムインターセクション(以下 HI)を使いました。正規化するので値は0から1の間、ヒストグラムが完全に一致した場合は1になります。実際に画像1と画像2の特徴ベクトルに対するHIは1になりました。まぁ当たり前なんですけど一応確認のため。
* Histogram Intersection
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
/* image histogram module */ CV.modules.histogram = function(self) { // draw histogram on the canvas self.drawHistogram = function(bins, context, style) { var h = context.canvas.height, max = self.getMax(bins), len = bins.length, step = context.canvas.width/len, k = 2; style = style || {}; context.globalAlpha = style['globalAlpha'] || 0.8; context.strokeStyle = style['strokeStyle'] || '#00cc66'; context.lineWidth = style['lineWidth'] || 4; for(var i=0; i<len; i++, k+=step) { context.beginPath(); context.moveTo(k, h); context.lineTo(k, Math.max(0.0, h - bins[i]*h/max)); context.stroke(); context.closePath(); } }; // calculate histogram intersection self.intersection = function(hist1, hist2) { if(hist1.length != hist2.length) { throw new Error('invalid histogram pair'); } var minsum = 0.0, len = hist1.length, min = 0, sum1 = 0, sum2 = 0; for(var i=0; i<len; i++) { min = (hist1[i] < hist2[i]) ? hist1[i] : hist2[i]; minsum += min; sum1 += hist1[i]; sum2 += hist2[i]; } return (sum1 > sum2) ? minsum/sum1 : minsum/sum2; }; |
次はHLACの加法性を確認しました。
画像3の特徴ベクトル + 画像4の特徴ベクトル = 画像1の特徴ベクトル (= 画像2の特徴ベクトル)
実際に計算してみるとHIはやはり1になりました。良かった。
ちなみに、画像1とそれを90度回転させた画像だとHIは0.996 … になりました。HLACは回転不変ではないですが、今回使ったテスト画像のような絵柄(家紋)だと似た値がでるみたいですね。全く関係ない画像だとHIは0に近い値がでます。
現在ではHLACで提案された局所自己相関の概念を応用して様々な発展系が提案されています。例えば画像勾配や色、Visual Wordを用いた特徴抽出などです。音(一次元)や動画像(三次元)へも既に展開されて幅広く応用されています。あと、HLACはここ数年の間によく聞くようになったなぁと思っていたのですが、最初に提案されたのはなんと30年以上前らしいのです(どの論文なのかわからなかったですが、大津先生の論文とのこと)。僕がまだ生まれてない時代ですね。
——————–
* 参考
[1] T. Kobayashi and N. Otsu, “Image feature extraction using gradient local auto-correlations”, European Conference on Computer Vision, 2008.
[2] T. Kobayashi and N. Otsu, “Color image feature extraction using color index local auto-correlations”, International Conference on Acoustics, Speech, and Signal Processing, 2009.
[3] 小林匠, 大津 展之, “画像特徴量 – 高次局所自己相関に着目した画像特徴量と画像認識への応用”, 電子情報通信学会誌, 2011
[4] 豊田崇弘, 長谷川修, ”高次局所自己相関特徴の拡張”, 画像電子学会誌, 2005
[5] 画像認識のための高次局所自己相関特徴