Haar-likeフィルタの効率性の幾何学的意味
今回は、単なる思考のメモ。
前回注釈で次のように書いた：
顔画像を（Violaらが使った）24×24＝576画素を要素とした576次元の高次元ベクトルと考えると、Haar-likeフィルタはこの高次元空間を高次元超平面で区切る作用を持つ。あらゆる画像が存在する576次元空間の中の顔が占める部分だけを凸包で包む――正確にはadaBoostを使うことで凸でない超平面で包んでるけど。このシンプルさ――というかアバウトさ加減――がViolaらの方法の汎化能力（学習した顔以外の顔画像も顔として検出できる）の高さの秘密だと思う。
この解像度24×24画素572次元の高次元ベクトル空間（画像状態空間）は、とてつもなく広い。
色深度8ビットであらわされるモノクロ空間でも(2^8)^572（≒1.4×10の1387乗）個の状態がありうる。
全宇宙のハドロンの総数なんかこれにくらべれば“塵芥（ちりあくた）”程度*1――というほどデカイ。
ただし、これらの状態のほとんどはホワイトノイズ。
アナログテレビの砂嵐のような画像。
「意味のある」画像空間はとてつもなく狭いだろう。
Violaらがアルゴリズムで生成した画像ではなく実際の非顔画像をネガティブサンプルに使用した理由はこれ。
「意味のある」現実の画像から切り出したネガティブサンプルには近接画素間になんらかの相関がある。
グラデーションとかエッジとか。エッジならエッジの延長方向に輝度値の連続性という相関があり、エッジの垂直方向に輝度差の相関がある。
それに対して、572次元の画像状態空間の大部分は相互に相関がないエントロピー極大の空間になるはずだ。
（この性質それ自体がまさしくエントロピー増大則をドライブする機構――というか幾何学的意味なワケだが）
そして前回注釈で書いた「もちろん超平面はHaar-likeフィルタで定義されるものよりはるかにたくさん存在するんだけど、Haar-likeフィルタという限定されたしかし効果的な超平面のみを使う事で実用的な学習時間で学習が収束する」というのは、この近接画素間の相関をHaar-likeフィルタが判定するという事を念頭においていたわけ。*2
ところで、adaBoostによる学習過程ではネガティブ・サンプルとして大量の非顔画像が必要になる。
顔を顔以外と識別する識別器を構成するために「顔以外」とは何かを学習アルゴリズムに与える必要があるから。*3
その際に与える非顔画像にはエントロピー極大なノイズ画像を用いる事は出来ない。Haar-likeフィルタは、適切なひとつを選べば、そのたった一つだけで易々とそれらと顔画像を分離してしまう。それらノイズ画像には画素間の相関がまったくないからね。
だから、状態空間上で顔画像が占める連結領域に近接しながら顔ではない画像（というか一般にカメラなどに写りこむ顔でない画像）をネガティブ・サンプルとして持ちいる必要がある。つまり近接画素間に相関がある「意味のある」画像を必要とする。
こういったあらゆる「意味のある」画像を生成するアルゴリズムを作るためには統計処理が必要になるだろう。
統計処理をおこなうためには多くの「意味のある」画像を収集する必要がある。たとえば5000枚の顔画像をポジティブサンプルとして30段のcascadeを構成する場合、ざっと2の(30+1)乗×5000≒10兆7374億枚のネガティブ・サンプルが必要になる。*4（各段の学習にポジティブ・サンプル（顔画像）と同数のネガティブ・サンプル（非顔画像）を用意するとすると、最初の段は5000枚のネガティブ･サンプルを用意するだけで良いが、二段目には、初段で5000枚程度が排除されるので、1万枚程度を用意しなければ有効な5000枚のネガティブサンプルを収集できない。同様にして３段目には2万枚、4段目には4万枚…）
だけど「顔検出」識別器の学習という目的に限るなら、収集した時点で（統計分析とかそれによるネガティブ画像の生成アルゴリズムの開発など行わなくとも）所期の目的は達成されてる。
その収集画像をネガティブ・サンプルに使えば良いんだから。
（OpenCVはアルゴリズムで生成した画像をネガティブ・サンプルに使ってるのかな？ だとするとどういう感じのアルゴリズムだろう？ 顔以外の学習にも使える汎用性のある画像が生成できるんだろうか？ OpenCVで学習させた事がないから知らないや…）
*1:Wikipediaの命数法に載ってる一番でかい「無料大数」が10の68乗。一番小さい「涅槃寂静」が10のマイナス24乗。こうしてみれば“塵芥”（「塵」＝10の-9乗）どころのさわぎではないね
*2:もちろん単純なHaar-likeフィルタのみが効率的だというわけではもちろんない。また近接画素のみが相関するわけでもない。例えば顔の左頬と右頬の明度差には明らかな相関がある。東芝の顔検出エンジン（PDFファイル）はこのあたり（共起性）を考慮するみたいね。選択候補の数が爆発してしまう（＝学習の際より多くのCPUパワーが必要になる）気がするけど。もちろん事前学習だから、いったん顔検出器を構成してしまえば、ユーザーが使用する際の検出速度には影響しない
*3:高次元ベクトルで考えれば、非顔領域と顔領域の境界になる超平面を決定するために必要になる。adaBoostとは直接関係ないけど、キーワード「SVM」で検索すると吉かも
*4:と書くと、とてもじゃないが用意することが不可能なほど巨大な数のように見えるけど、前回触れたように、そこそこの大きさの一枚のネガティブ画像（顔を含まない画像）から数百万から数千万のネガティブ・サンプルを抽出できる。そして、cascade後段の学習に必要なネガティブ・サンプルには、作りかけの顔検出器を通してみて、すり抜けてきた（＝顔と誤認識された）窓領域を使用すれば良い。
