三項演算子が遅い？
ここ数日、検出器をActionScript3(AS3)へ移植する作業をしていました。OpenCV（の検出器）をAS3で使いたい！という向きにはMarilenaというライブラリが既にあるのですが、単純に勉強になるということと、細かいところまで自分で把握していたほうがカスタマイズしやすいという点を考えて、敢えてイチから書いています×
さて、物体検出というのはなかなか重い処理でして、識別器の適用処理（OpenCVのオリジナルコードでいうと cvRunHaarClassifierCascade関数）は、画像のサイズにもよりますが何万とか何十万とかいうオーダーで呼び出されます。AS3に移植するときは、ここが重くならないように気をつけなければいけません×
AS3の最適化においては（AS1/2でもそうですが）、メソッド呼び出しのオーバーヘッドが馬鹿にならないので、メソッド呼び出しを（涙を飲みつつ）インラインのべた書きに直していくという作業が主になります。ところが、メソッド呼び出し以外に、意外なところで高速化のポイントが見つかりました×
オリジナルのOpenCVのコードで言うと次の部分です×
a = classifier->alpha[0]; b = classifier->alpha[1]; stage_sum += sum < t ? a : b;
個々の弱識別機の適用結果を判定して、Stage全体のスコアを操作する処理です。Marilenaで該当する箇所は
val += (sum < feature.threshold * variance_norm_factor) ?
feature.left_val : feature.right_val;
ここです×
これをこう書くとどうでしょうか×
if (sum < feature.threshold * variance_norm_factor) val += feature.left_val; else val += feature.right_val;
三項演算子がif文になっただけです。これを計測すると以下のようになります
| 回 | 1 | 2 | 3 | avg | ratio |
|---|---|---|---|---|---|
| 三項演算子 | 2437(ms) | 2453 | 2437 | 2442.333333 | 1 |
| if文 | 1875 | 1891 | 1875 | 1880.333333 | 0.76989218 |
20%以上速くなりました。ふしぎ！ふしぎ！ X > _ < X
と、ここまで読んで「三項演算子って遅いんだ！三項演算子ヤバイ！超ヤバイ！」とか言って手持ちのコードを書き換えに行くのはちょっと待ってください。次のようなコードの場合は速度にはほとんど差がありません。
public static function cmp1(a:int, b:int):int { return (a<b) ? 2 : -2; } public static function cmp2(a:int, b:int):int { if (a<b) {return 2;} else {return -2;} }
上の例では、cmp1とcmp2で若干違うバイトコードが生成されますが、速度に有意差はありません。三項演算子が問題を起こすのは次のようなコードです
public static function cmp1(a:int, b:int):int { var c:int = 0; c += (a < b) ? 2 : -2; return c; } public static function cmp2(a:int, b:int):int { var c:int = 0; if (a < b) { c += 2; } else { c -= 2; } return c; }
三項演算子の結果を使って変数cの値を操作しています。OpenCVの問題の個所に近い処理です。これを20000000回まわすと以下のような結果になります×
| 回 | 1 | 2 | 3 | avg | ratio |
|---|---|---|---|---|---|
| 三項演算子 | 4453(ms) | 4375 | 4468 | 4432 | 1 |
| if文 | 3109 | 3093 | 3157 | 3119.666667 | 0.703895909 |
やはり三項演算子が格段に遅いです。生成されたABCを比較してみます×
↓三項演算子
0 getlocal0
1 pushscope
2 pushbyte 0
4 setlocal3
5 getlocal3
6 getlocal1
7 getlocal2
8 ifnlt L1
12 pushbyte 2
14 coerce_a
15 jump L2
L1:
19 pushbyte -2
21 coerce_a
L2:
22 add
23 convert_i
24 setlocal3
25 getlocal3
26 returnvalue ↓if文
0 getlocal0
1 pushscope
2 pushbyte 0
4 setlocal3
5 getlocal1
6 getlocal2
7 ifnlt L1
11 getlocal3
12 pushbyte 2
14 add
15 convert_i
16 setlocal3
17 jump L2
L1:
21 getlocal3
22 pushbyte 2
24 subtract
25 convert_i
26 setlocal3
L2:
27 getlocal3
28 returnvalue 三項演算子で書いた場合のみ、coerce_aが生成されています。この命令は、avm2の仕様書によると Any型( * )に値を変換する命令だそうです。これは重くなるわけです。尚、ここでは整数演算しかしてませんが、実数演算の場合も同様に三項演算子の方が遅いという結果が出ます×
というわけで、三項演算子を使わないほうがいい場面もあるという話でした。ABCアセンブリの生成には、id:nitoyonさんのabc抽出プログラム（d:id:nitoyon:20080401）とabcdump(http://iteratif.free.fr/blog/index.php?2006/11/15/61-un-premier-decompileur-as3)を使いました×
カスケード識別器の効率とか×
OpenCVのカスケード識別機の資料ですが、Intelのサイトにしっかりした解説がありました×
Learning-Based Computer Vision with Intel’s Open Source Computer Vision Library
積和画像の話なんかも載ってますし、最初からここを見ておけば楽でした X > _ < X
さて、識別機を複数のStageに分けて効率を上げるという話がありましたが、そのへんの記述もありますね×
In experiments, about 70-80% of candidates are rejected in the first two stages that use the simplest features
ということですが、実際どうなんでしょう。標準で付いてくる顔の識別機を使って調べてみました×
入力画像はこれ×
出力はこちら×
さすがの精度ですね。このとき、OpenCVが識別器を適用している様子をアニメーションにするとこんな感じです×
当然のことながら、画像に含まれる顔の大きさや位置はバラバラなので、OpenCVは識別器の大きさと位置をずらしながら検査します。このときの識別器の大きさと位置を Window といいます。上の画像では、各 Window の左上の角に長い柱が立っています。柱の足元にある四角い枠は、 Window の範囲です。また、すべての Window を同時に出すとさすがに画像が潰れてしまうので、Window の大きさごとにコマを割ってアニメーションしています×
柱の色は、各 Window がどの Stage まで進んだかを表しています。Stage 1,2 で棄却された Window は緑、そこから先で棄却されたものは黄、棄却されなかった（顔かもしれないと判定された）ものは赤で表示されています×
これで見ると…… なんか、結構な数が Stage 2 以降に進んでしまったように見えますが、実際の数字をみるとこうなります×
公称通り、70%程度が最初の2ステージで棄却されています。なんか上のアニメーションは失敗だったかもしれません X > _ < X
検出器のXMLを視る
OpenCVを使ったことがある方は、OpenCVの物体検出ライブラリが、XMLから何やらデータを読み込んで処理をしていることをご存知かと思います×
このXMLの中では、rect（rectangle = 矩形）をいくつか組み合わせて feature と呼ばれるものを定義しています×
「目」を検出してみるで作成した検出器のXMLの一部を以下に示します×
<feature> <rects> <_> 0 0 8 8 -1.</_> <_> 0 0 4 4 2.</_> <_> 4 4 4 4 2.</_> </rects> <tilted>0</tilted> </feature>
x, y, width, height, weight という形式で、3つの矩形が記述されています。これを図にするとこうなります×
これを3つ重ねると……
おっと。これは弱識別器関連の論文によく出てくるあれですね×
なんとなく、OpenCVのプログラムが何をやっているか見えてきましたね×
さて、せっかくなのでXML全体を図にしてみました。目の検出器はこんな感じです×
検出器がいくつかの「Stage」で構成されている点がポイント（らしい）です。Stageというのは、まさしくテレビゲームのステージのようなもので、入力画像を各Stageで判定して、合格すれば次のStageへ進めます。不合格ならそこでゲームオーバー。判定を打ち切ってしまいます。見込みのなさそうなものは早めに判定を打ち切って無駄な処理を省き、怪しいものは慎重に判定するという、なかなかうまい方法です×
ちなみに、標準で付いてくる顔の検出器（1MB以上ありましたね）は、こんな感じです×
これでもまだ一部です。高い精度を出すためにはこれぐらい必要ということでしょうか×
JSON + CanvasでVisual Code Reading(3)
一昨日の続きです。元画像の各ピクセルの積和を何に使うのかという話でしたが、ヒントになりそうな文献を調べてみました。日本語の文献だと、以下のものが参考になりそうです×
[PDF] 谷川昌司, 日高章理, 佐野夏樹, 西田健次, 栗田多喜夫: 矩形特徴による弱識別器のブースティングによる対象検出手法の汎化性能向上のための工夫と車載カメラの映像中の車の検出への応用, 第11回画像センシングシンポジウム講演論文集, E-10, pp.139-142. 2005.
英語の文献だともうちょっと詳しいのがあります×
[PDF] Andreas Nüchter, Hartmut Surmann, Joachim Hertzberg: Automatic Classification of Objects in 3D Laser Range Scans, In Proc. 8th Conf. on Intelligent Autonomous Systems, 2004
日本語のほうから引用します×
矩形特徴は図1 に示すような局所領域に含まれる画素の輝度の総和の組み合わせで表される。矩形特徴の強度は白い部分に含まれる画素の輝度値の平均と黒い部分に含まれる画素の輝度の平均の差として表される。つまり、白い部分の平均輝度から黒い部分の平均輝度を引いた値を計算する。
（中略）
この演算は、あらかじめ以下に示す積分イメージを求めておくことで、比較的簡単な演算の組み合わせで計算できる。
なるほど。平均というのは足して割ったものなので、「足す」計算を最初にやって画像に保存していたわけですね。わかってしまえば単純な話でした×
ところで、積分を微分すると元に戻るという話を学校で習いました。この画像も、積和ルーチンの逆の操作をすると元に戻すことができます。またCanvasに描いてみます×
var dest_pos = 0; var k, u, prv = 0; for (var i = source.width;i < len;i++) { k = source.data[i]; u = source.data[i-source.width]; k -= u; k = k - prv; prv = source.data[i] - u; if (k < 0) k = 0; if (k > 255) k = 255; buf.data[dest_pos++] = k; buf.data[dest_pos++] = k; buf.data[dest_pos++] = k; buf.data[dest_pos++] = 255; }
出てきました！積和画像には元の画像の情報が完全に保存されていることが分かります×
……ところで sqsum のほうは？ X > _ < X ＜ また今度
JSON + CanvasでVisual Code Reading(2)
きのうの続きです。きのうは、img という変数の中身をCanvasで視覚化して、元画像がそのまま格納されていることを確認しました×
今日は、残るsum と sqsum の中身も同様にしてレンダリングしてみました。こんな感じです×
← sum
← sqsum
実際はそれぞれ32bit int型、double型なので、256諧調の中にマップしています×
さて……なんでしょうコレ。この画像（らしきもの）を生成しているコードは以下のような感じです×
for( y = 0; y < size.height; y++, src += srcstep, \ sum += sumstep, sqsum += sqsumstep ) \ { \ sum[-1] = 0; \ sqsum[-1] = 0; \ \ for( x = 0, s = 0, sq = 0; x < size.width; x++ ) \ { \ worktype it = src[x]; \ sumtype t = cast_macro(it); \ sqsumtype tq = cast_sqr_macro(it); \ s += t; \ sq += tq; \ t = sum[x - sumstep] + s; \ tq = sqsum[x - sqsumstep] + sq; \ sum[x] = t; \ sqsum[x] = tq; \ } \ } \
行末に円マーク……じゃなくてバックスラッシュが付いているのは、これがマクロだからです。画像のピクセルの形式に合う関数をマクロでいくつも生成して、実行時にはそのうちの一つが呼び出されます。なので、残念ながらここにはデバッガで入ることができません（C++なんだからテンプレートを使えばいい気もしますが……）×
さて、実はこのマクロの中にさらにマクロが含まれています。それらを展開すると以下のような形になります×
for( y = 0; y < size.height; y++, src += srcstep, \ sum += sumstep, sqsum += sqsumstep ) \ { \ sum[-1] = 0; \ sqsum[-1] = 0; \ \ for( x = 0, s = 0, sq = 0; x < size.width; x++ ) \ { \ int it = src[x]; \ int t = it; \ double tq = icv8x32fSqrTab[(it)+128]; \ s += t; \ sq += tq; \ t = sum[x - sumstep] + s; \ tq = sqsum[x - sqsumstep] + sq; \ sum[x] = t; \ sqsum[x] = tq; \ } \ } \
これは要するに……ピクセルの輝度値を積算しながら、左上から走査しているわけですね。ただし、sum が単純な積算なのに対してsqsum は輝度値を二乗してから足しているようです（icv8x32fSqrTab は、二乗の計算を高速化するためのルックアップテーブルです）×
先ほどの画像と照らし合わせると……なるほど、左上から右下に向かって単調に輝度が増加していますね。sum と sqsum は、元画像の各ピクセルの輝度値の積和を記録した画像、という理解でよさそうです×
さて、問題は、こんな物を何に使うかということですが……
X / _ / X ＜ つづく
「目」を検出してみる
OpenCVには、物体検出の機械学習をするツールが付いてきます。これを使うと、顔以外の検出器を作ることができます。コードを読むのをちょっとお休みして、これを試してみました×
参考ページ: http://ugd555.blog1.fc2.com/blog-category-30.html
今回は「目」の検出に挑戦してみました。ポジティブイメージ（正解例）として、以下の9個を用意しました×
ネガティブイメージ（正解を含まない例）は以下の9個です×
「マトモな検出器を作るにはポジティブ7000例、ネガティブ3000例は必要」らしいので、全然足りてないんですが… まあ、とりあえずやってみましょう×
1個も検出できていません。うーん。さすがに無理がありますかね。ただ、顔の部分がちょっと小さすぎるかもしれません。もうちょっと大きな画像で試してみましょう×
おお！１箇所誤検出がありますが、なかなかの成績です。調子に乗って他のもいってみましょう×
おおお！さすが世界のダンコーガイさんですね！赤い眼鏡もステキです×
……と、随分とうまくいったように見えますが、実はちょっとズルをしています。OpenCVの物体検出器は、最終的な結果を出す一歩手前で、以下のような状態になっています×
水色の四角は、「ここが顔かもしれない」という候補です。又吉さんの顔の部分に大量に四角が重なっていますね。このように、同じ場所に候補が重なっているところを最終的な結果として残して、重複が少ないところを消してしまいます。その結果、以下のようなきれいな結果が出るわけですね×
ここでの「何個以上重複した部分を残すか」という閾値は、自由に変えることができます。閾値を下げれば「甘く」なるわけですね。水樹奈々ちゃんのときは４、ダンコーガイさんのときは２、と人為的に操作して、結果を良くしていたわけです（論文を書いたりするときにこんなことをしてはいけませんよ）。ちなみに、水樹奈々ちゃんの画像で閾値を２にすると、こんな感じになります×
眉毛まで検出しちゃってます。まあ、学習用の画像がたった9個ならこの程度でしょう×
余談ですが、3つ上の画像（重複を処理する前の結果）の画像も、JSONでダンプしてCanvasのstrokeRectで描画、という手順で作りました。便利ですね、Canvas×
JSON + CanvasでVisual Code Reading×
OpenCVってどうやって顔を見つけているのか気になりませんか。気になりますよね。というわけで、ちょっとソースを眺めてみました×
その結果……よくわかりません！そうですよね。学者さん達の研究の結晶ですからね。ぱっと見て分かるわけがありません×
やっぱり論文とか本とか読まなきゃいけないのかな。英語のは結構ネットで読めるけど、日本語のは図書館に行かないとなかなか……×
よし。図書館に行く前に、もうちょっと頑張ってプログラムを読んでみましょう。答えはここにあるわけですから×
データを視る
プログラムを読むのは、実に簡単ですよね。文字で書いてあるわけですから。あと、プログラムの動作の流れも、デバッガでステップ実行すれば簡単に分かります×
難しいのは……そう、データですね。確かにデバッガを使えば変数の値ぐらいは見えますけど、今扱っているのは画像ですから、変数の値がちょっと見えたぐらいではクソの役にも立ちません×
ハッカーの人たちは、もっと強力なツールを使ってるのかな？dddとか？でも、yunocchiは難しいツールの使い方はわからないし、商用の製品を買うお金もありません×
こんなとき、yunocchiはWebブラウザを使います。Webブラウザは、HTMLレンダラ、SVGレンダラ、そしてCanvasといった「視覚化ツール」を取り揃えています。これを使わない手はありません×
OpenCVで顔の認識をする場合、cvHaarDetectObjects という関数を使います。この関数を眺めると、sum と sqsum という2つの変数を使っていろいろ計算していることがわかります。どうやら、この2つの変数が入力画像と関係があるようです。――ええ、そうです。これらは入力画像そのものではないんですね。コードを眺めたところ、入力画像そのものは、img という変数に格納されているようです。まず、この事実を確認してみます×
printf("{\n"); printf(" \"name\" : \"img\",\n"); printf(" \"width\" : %d,\n", img->width); printf(" \"height\": %d,\n" , img->height); printf(" \"step\" : %d,\n" , img->step); printf(" \"data\" : ["); dumpData(img); puts("]"); printf("}\n\n"); fflush(stdout);
printfデバッグ！この時代に!!とか気になる人は……まあ、適当なロギングツールを使ってください。それより、printfしている中身です。これはJSONです。JSONでデータを吐いておけば、Webブラウザに容易に読み込ませることが出来ます。printfしてJavascriptのソースに貼り付けるだけで、ブラックボックスからデータを取り出すことが出来ます。もうちょっと複雑な構造のデータであっても、JSONならprintfで充分組み立てられます×
dumpData という関数は、JSON出力のために勝手に作った関数です。この関数は、img->data.ptr が指すバッファの中身をカンマ区切りで出力します×
さて、これを実行すると以下のようなJSONになります。
{ "name" : "img", "width" : 439, "height": 599, "step" : 440, "data" : [255,254,255,255,254,255 /* …長いので省略 */ ] }
width と height は、なんか妥当そうな値ですね。step というのは、バッファ中での１ラインあたりのバイト数です。これも問題なさそうです（今は、1byteのpaddingが入っている理由は放っておきます）問題はdataの中身です。これを並べると入力画像が再現されるはずです×
最新のWebブラウザ――たとえばFirefoxは、Canvasでラスタ画像を扱うことが出来ます。具体的に言うと、getImageData / putImageDataというAPIです。これらのAPIを使うと、Canvasの内容をラスタデータとして取得したり、ラスタデータを書き込んだりといったことができます。では、先ほどのJSONに本当に入力画像が含まれているか確認してみます×
/* source は、上記のJSONオブジェクトを保持しています */ var cv = document.getElementById('canvas'); var g = cv.getContext('2d'); var buf = g.getImageData(0, 0, source.width, source.height); var len = source.width * 200; var dest_pos = 0; var k = 0; for (var i = source.width;i < len;i++) { k = source.data[i]; buf.data[dest_pos++] = k; buf.data[dest_pos++] = k; buf.data[dest_pos++] = k; buf.data[dest_pos++] = 255; } g.putImageData(buf, 0, 0);
まず、getImageData で canvas の内容を取得します（もちろん真っ白ですが）。生のラスタデータは、返ってきたオブジェクトの data プロパティに配列として入っています。この配列は、R,G,B,A,R,G,B,A,R,G,B,A……というふうに、4つの要素で1つのピクセルを表しています。いま、入力画像はモノクロ8bitなので、R,G,Bに同じ値をセットして、Aには255を入れておきます。こうして書き換えたオブジェクトを putImageData で canvas に戻します×
さあ、どうでしょうか……
出ました！ これは確かに又吉さんのポスターです。これで img に入力画像が入っていることは確定しました。それでは、sum と sqsum ですが…
X / _ / X ＜ つづく
