サルでもわかる顔検出の原理
顔検出機能はここ数年で急激に普及してデジカメとかケータイとかにフツーに入るようになったり、Google画像検索のオプションに入ってたりして、すっかりコモディティ化しちゃってるけど、ちょっと前まではすごい困難で実用化に手を出すなんてとてもとてもな技術だったんだよね。
2001年のViola & Johnsの論文*1で超高速＆超正確な検出アルゴリズムが発表されるまでは。
これの画期的だった点は非力なパソコン（とか現在のケータイ内蔵CPUとか）で画像中からリアルタイムに顔を検出できたことなんだ。
キモは３点。
- Integral-ImageによるHaar-like検出器の高速演算
- AdaBoostによる検出能力の強化
- 多段フィルタ（cascade）による非顔領域の高速排除
具体的にどれがViolaらのオリジナルの仕事なのかはよく知らないけれど。
少なくとも一個目と三個目はそうな気がする。
Integral-Image（「積算画像」とでも訳せばよいかな）はen.wikipediaによると、もともとは“Summed area table”（「エリア総和テーブル」）と呼ばれる3Dグラフィックスでは一般的なmipmap画像を高速で生成するための技法だったみたいね。
で、これらを簡単に解説してみたい、というのが今日の最初の主題。
コンピュータには一切「判断力」というものはない。
単に計算結果を返すだけ。
そのコンピュータに例えば640×480画素*2の画像の中から顔の領域を見つけさせたい。
単なる計算のみで。
どうする？
例えば画像の中の64画素×64画素の領域をくりぬいて、それが顔なら１を出力する。
それが顔でないなら０を出力する。
そういう演算をおこなう関数を用意する。
そういうことができる関数はViolaら以前にも存在したけど、問題はその速度。
640×480画素の画像の中から64×64画素の窓を切り出すと、候補数は240609個。*3
この「顔判定」関数は１画素ずれただけで「顔ではない」と判定するかもしれない。
なんせただの計算で判定してるだけだから。
だから640×480画素の画像の端から64×64画素の窓を1画素づつスライドさせながら次々に「顔判定」関数にほおりこんでいくしかない。
そうすると候補数は簡単に20万個を越えてしまうわけ。
しかも、この「顔判定」関数は、顔の大きさがジャストフィットで無いと「顔ではない」と判定するかもしれない。
なんせただの計算で判定してるだけだから。
なので、顔の大きさがわからない場合は（普通わからないよね）、たとえば24×24画素の窓から始めて、480×480の窓まで次々に「顔判定」関数にほおりこんでいく必要が出てくる。（64×64画素の判定しかできない関数なら、ほおりこむまえに64×64画素に拡大縮小して大きさを合わせる）
これで、たった640×480画素の画像の「顔候補」の数は数百万個に膨れ上がってしまう。
干し草の山から針を見つける、というあれだ。
なんぼ高速演算の計算機でもこの課題は重すぎた。
- Haar-like検出器（Haar-like feature）
このHaarってのはHaarウェーブレットのHaarだと思う。
でもHaarウェーブレットに一見似てるけど違うから"Haar-like"。
ウェーブレットをAdaBoostで組み合わせる手法は先行論文があるみたいね。
ただ、これをよりシンプルなHaarウェーブレットにしてIntegral-Imageを組み合わせて高速化したところが画期的だったんだと思う。
人の顔の写真って目の回りをぼかして見ると、そのすぐ下の頬のあたりよりは暗い。
窓画像の中から目の辺りになる位置の上下に隣接する横長の長方形領域を切り出してそれぞれの領域の明度の平均をとる。上の領域が明るくて下の領域が暗かったら顔画像の候補にする。
鼻筋の天辺よりは鼻筋の両脇の明るさの平均*4のほうが小さいことが多い。
Viola&Jones CVPR2001 Figure.3より
これだけの判断基準で、上記の数百万個の「顔候補」が一気に半分に減ってしまうことにViolaらは気付いた。*5
そしてIntegral-Imageを使うと、その計算がたった数回の加減算でできてしまう。
窓サイズを変えるのもコントラストを調整する*6のも、それに数回の乗算を増やすだけの手間でよい。*7
数百万の候補数がやっと半分になっっただけ？
でもあとは、このやり方を繰り返していくだけなんだ。
そして繰り返していくだけで計算しなければならない候補数は急速に減っていく。
残り半分をHaar-like組み合わせ検出器（最初の検出器よりはHaar-like検出器の数が少し多い）にほおりこむと、さらに半分になる。
あとはねずみ算式を逆に辿って、10回目にはもとの千分の一にまで候補数が減っている。
20回目には百万分の一にまで減ってしまう。
つまり、これが
- 多段フィルタ（cascade）による非顔領域の高速排除
というわけ。
20数回分のHaar-like組み合わせ検出器をくぐらせて、残ったものが「顔」ということになる。
もちろん、後ろの段になるほど判定するのは困難になっていく。だから計算時間もそれなりにかかる。
だけど、難しくなる頃には最初に数百万もあった候補数はぐっと減ってきてるんだ。
よいアイディアだよねぇ。*8
*1:Paul Viola and Michael J. Jones. Rapid Object Detection using a Boosted Cascade of Simple Features. IEEE CVPR, 2001.
*2:大昔のパソコンの解像度�陬▲淵蹈庵肋綰肇謄譽咾硫鯀踣�
*3:（640-64+1）×（480-64+1）＝ 240609
*4:例えば左から光があたってれば鼻筋の左側は鼻筋中央より明るいけど、鼻筋右側は鼻筋中央より暗いから、鼻筋両脇の明るさの平均値は鼻筋中央より小さくなる事が多い
*5:実際には大量の学習画像を使ってHaar-like識別器候補からadaBoostアルゴリズムで選択させて、これらが残ったという話
*6:これには窓画像の明度分散を計算するために画素明度の二乗のIntegral-Imageを用意しておく
*7:しかもこれは判定毎におこなう必要は無く、各窓サイズで対象画像をスキャンする前段階でHaar-likeの位置オフセット（と明度差の閾値係数）に拡縮率を乗じて置けばよい
*8:顔画像を（Violaらが使った）24×24＝576画素を要素とした576次元の高次元ベクトルと考えると、Haar-likeフィルタはこの高次元空間を高次元超平面で区切る作用を持つ。あらゆる画像が存在する576次元空間の中の顔が占める部分だけを凸包で包む――正確にはadaBoostを使うことで凸でない超平面で包んでるけど。このシンプルさ――というかアバウトさ加減――がViolaらの方法の汎化能力（学習した顔以外の顔画像も顔として検出できる）の高さの秘密だと思う。もちろん超平面はHaar-likeフィルタで定義されるものよりはるかにたくさん存在するんだけど、Haar-likeフィルタという限定されたしかし効果的な超平面のみを使う事で実用的な学習時間で学習が収束する。しかもこの汎化能力の高さゆえ、窓位置やサイズが少しくらいずれてもちゃんと顔として判定してくれる。だから上に書いたような１画素毎のスキャンも要らない。1.2倍程度づつ窓サイズを変えながら（縮小後の画素座標で）1.5画素毎とかでスキャンしていけば良い
