ついさっきまでMaxの話を書いていたわけですが、いまはプログラミング。
OpenCVで顔画像認識、というタイトルのエントリーを結構時間かけて、しかもスクリーンショットつきで書いていたのに、突然マウスごと止まった…。ハードディスク異常！
再起動すると、Ubuntuが起動し始めた…なんだろう？？
うーん、これってハードディスクが壊れたってことか…？ってゆか、このマシンにUbuntu入れた記憶無いんですけど…と思ったらUSBハードディスクからの起動だった。すごいなDELL Dimension 9100。
とりあえず無事再起動は終わったみたいなので、被害状況を確認。
...レンダリングは駄目っぽいなあ。
書きかけのBlogは消えた。わかってはいるがつらいな。
Google Docs使うか…。
Maxの文字が日本語化けしてて驚く。多分これはさっきコントロールパネルで「非Unicodeアプリの言語設定」を変更して、そのままずっと再起動してなかったせいだと思う。
…で気を取り直して、OpenCVのほうだけど、sampleのfacedetect.cを解析中。
基本的にリビルドとかは簡単。マルチプラットフォームなライブラリにしてはずいぶんと洗練されていると思う。ディレクトリ構成なんかもちょっと癖はあるけど慣れれば分かる。
サンプルは徹底してCだし（ライブラリ内部はC++）。pythonのサンプルもある。
このサンプルはあらかじめ用意されたHaar（ハール）のClassifier Cascadeファイルを読み込んでいる。
OpenCV\data\haarcascades\haarcascade_frontalface_alt2.xml
この841KBのファイルはXMLで、
「Tree-based 20x20 gentle adaboost frontal face detector.Created by Rainer Lienhart.」と書かれている。
よく見るとIntelの著作物でライセンス条文も書かれているので、勝手に製品に組み込んだりしたらまずいと思う（論文化されている）。
19のステージ、１０８のツリーがあって各ノードは<rects>２つ、<tilted>、< threshold>、<left_val>、<right_node>、< stage_threshold>といった構成になっている。
ウェーブレットや信号処理でよく出てくるHaar変換のパラメータ、閾値、カスケード（滝）分岐させてるためのノードという理解でいいと思う（間違ってたらごめん）。
ベクトル量子化に近い手法、キャリブレーションなしで回転や個々人の違いなどにロバストなのはすごい。
ちなみにhaarcascadesフォルダにはほかにも面白そうなプロファイルが転がっている。
以下、このファイルを元にアルゴリズムについて考察してみます。
まず「haarcascade_upperbody.xml」はETHスイスによるもので、以下の論文の実装と思われます。
「Fast and Robust Face Finding via Local Context」
この論文ではObject Centered DetectionとLocal Contextの比較を行っている。Object Centeredな顔画像認識は目→鼻→口→といった感じに認識分岐ステップをすすめていったうえで、個々の被写体に対しての処理を行うことが多いわけだけれども、提案手法はLocal Context、つまり近隣の領域との比較で認識の分岐木をすすめていく。分岐のノードは深くなるけれど、人間の顔を取り間違える可能性は低くなる。またそれぞれの人間を別に見分けることができる可能性がある。
基本的な手法は最初に挙げたRainer Lienhartの方法で「An Exteded Set of Haar-like Features for Rapid Object Detection」に書かれている。"Haar-Like"と言ってるだけにハール関数とはちょっと違う。Boosted Classifier Cascade、つまり判断結果をブーストして重み付けしていく手法。これは「Rapid Object Detection using a Boosted Cascade of Simple Features」でPaul Viola（当時MERL、現在Microsoft）がIEEE CVPR2001で報告した論文。Lienhartの方法は、同様にclassifier（クラス判別器）を、24x24、20x20といった処理ウインドウ内に収まる大量の映像で学習し（ポジティブ）、さらにまったく関係ない同サイズの背景画像などでネガティブ学習をする。Lienhartの方法は、近傍の片側に注目するEdge Features、両側に注目するLine Features、中央とその周辺に注目するCenter-surround Featuresの３種、それぞれに直交（Upright）、斜め45度（Rotated）のパターン、合計１４種のフィーチャープロトタイプを用意する。パターンは白黒で領域が分けられており、おのおのポジティブ/ネガティブのウェイトをもっている（ブーストするので+1/-1ではない）。
処理矩形領域の座標X,Y、長辺と短辺の長さをw,h、回転を４５度単位で表現するので、例えばあるフィーチャー「座標(5,3)にある高さ2、幅6のラインフィーチャー(2a)」は
feature_I = -1 * RectSum(5,3,6,2,0°) + 3 * RectSum(7,3,2,2,0°)
というように表現できる。また、あるウィンドウサイズ内における14種のフィーチャープロトタイプのパラメータ組み合わせは有限で、論文では24x24ウインドウで合計117,941種と報告されている。
…でxmlファイルに戻るわけだけど、上記のファイルに各ステージの比較領域２つ、スレッショルドと分岐木が用意されているというわけですね。
プログラムに戻ると、
CvHaarClassifierCascade構造体にxmlファイルからロードして、キャプチャからフレーム画像を取得。
検出ルーチンでは縮小スケール(1/1.3倍）して246x184pixelsの画像にして、BGR→Grayの色変換、さらにリサイズ、EqualizeHist（ヒストグラム平滑化）を処理している（毎フレームコールするぐらいならGPUで処理したいな…）。
で肝心の顔認識だけど、
CvSeq* faces = cvHaarDetectObjects( small_img, cascade, storage,
1.1, 2, 0/*CV_HAAR_DO_CANNY_PRUNING*/,
cvSize(30, 30) );
実装はOpenCV/cv/src/cvhaar.cppにある。
4番目の以降の引数はdouble scale_factor,int min_neighbors, int flags, CvSize min_sizeとなっていて、それぞれ検索窓の増分（この場合+10%ということ）、近傍ピクセルの最小値（2ピクセル以下は処理しない）、最小サイズ、となっている。flagはcanny pruningを使うかどうか、キャニーフィルターをつかった枝狩りが実装されているみたい。
コンソール画面に表示される処理速度はこの関数の実行前と実行後の間の時間。論文では320*240、全スケール検索、scale factor=1.2、Pentium4 2GHzの環境で5fpsと書かれているけれど、デフォルトのパラメータ（増分1.1、最小ピクセル2）で手元の環境では34msec出ていた。速度に関しては、例えば増分を1.2ぐらいにすると20msecを切る。CV_HAAR_DO_CANNY_PRUNINGの効果はいまいち分からなかった（深夜の研究室で一人でやってるからかも…背後に誰か検出されたら効果はあるかもしれないが、それはそれで怖いぞ）。まあ30msec出ている時点で 30FPS、16.6msec以下であれば60FPSが実現できるので、パラメータと用途によってはゲームインタフェースへの利用も可能だと思う。ともかく、この関数の場合は速度と精度を自由に設定できるのがすばらしいね。
最後にネガティブポイントを述べると、複数の顔については未検証（一人しかいないので）。でも周囲の雑音を「２人目」として検出していることもある。蛍光灯のせいもあるけど、オプティカルフローは使っていないので、複数人を検出したいなら、ほかの関数使って多少強化したらいいとおもう。そもそもグレースケールなので、顔画像なら色相-明度空間で処理すべきだ（HaarDetect自体は顔画像に限っていない）。それから「斜めの顔」は弱いと思う。アルゴリズム上45度単位でうまくとるかと思ったけど、45度を越えると、検出されないことが多い。これは学習させたデータベース（多分CMUの顔画像DB）にも関係があるのかも。AceSpeeder2モーション認識版のように頭で操作するようなアプリケーションのときは自然に±45度を越えてしまうことがあるのでカメラセットアップに注意が必要だね。あとは顔が大きく写る、精度が必要な用途には向いていないと思う。cvHaarDetectObjectsで個々の顔の粗位置を出して、そこからモーションフローを使うとよいのかもしれない。
それからGPUで実装することを考えると、いくつかやれることはあると思う。肝心の処理以前の前処理フィルタは当然として、 stage_classifierはこの場合でも19ステージ20x20程度なのであれば、もしかしたらGPU上に前処理でフィルタ化できるかもしれない。まあ思いつきで言っているところはあるけれど、処理ウィンドウが小さい処理と言うのはGPU向きなので。逆にフレーム全般において積分しまくらないといけない処理は不向きなんだけど。ふつうにフレームメモリ上にマッチングテンプレートを用意する方法よりはずっとエレガントかもしれない（ターゲット画像が与えられて、速度を重視するならその方法も否定できないけど）。