2010-06-13
サルでもわかる顔検出の原理
顔検出機能はここ数年で急激に普及してデジカメとかケータイとかにフツーに入るようになったり、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
Permalink | コメント(2) | トラックバック(2) | 22:49 
そして「アテネの学堂」
そして何よりすごいのが、こういう論文がネットには転がっていて、その気になればおいらみたいな門外漢がアクセスできてしまうという事。
まあ、実際は仕事でしょうがなく調べたんだけど。*9
で、思ったんだけど、これってちょっと頭が良い高校生くらいなら、簡単に調べて実現できてしまうよねぇ。*10
――というのが、今日の二つ目の主題。
上で解説しなかったadaBoostは数学的にちょっとややこしい面もあるんだけど、アルゴリズム自体は簡単。
Integral-Imageにいたってはすげー簡単。名前をつけずに発明しちゃってた人が世界中にたくさんいるんじゃないかなというくらい簡単。
論文に出てくる数学記号のいくつかは高校では間違いなく習わないし、英語論文の数学的言い回し（「ここでXXはOO」とか「XXという条件で」とか）も難しい。だけど「数学記号」とか「数学英語」でぐぐれば簡単に調べられる。
そしてViola-Jonesの上記論文は山のような派生論文を生んだけど、確かにあまりにもシンプルすぎて工夫の余地がいっぱいあるんだよね。
OpenCVで採用されてるLienhart & Jochenの論文*11もそうだし。おいらも、仕事でいくつか改良した。（仕事だから書けないけど）
ひところ盛り上がった（炎上した？）"日本のWebは「残念」"を"Tech Mom from Silicon Valley"経由で見た時に最初に思ったのがこの件なんだ。
OpenCVの顔認識をそのまま使ったコンテンツなんかは「ニコニコ動画」にいくつもある。
そのまま使ってるとはいえアイディアいっぱい。おいらが調べた4年前にはちょっと考えられなかった状況。
で、こないだ見つけてしまいました。ちゃんと応用＆発展させている例：
"Perlでアニメ顔を検出＆解析するImager::AnimeFace - デー"
このブログをざっとみたかんじでは論文が何本も書けそうなオリジナルな発展がなされているように思える。
ところがこの人は、趣味でやってるっていうんだよね。
こういう発展がWeb上でまさに行われているということは軽視しちゃいけないんじゃないだろか？
問題は我々の社会のリスペクト力の弱さというか、リスペクトを社会化する力の無さ加減なんではないかと思う。
とりあえず、上の動画の「踊る男」を見てのおいらの感想は、「バカだろこいつ」だな（笑）。
下の動画の解説で「権威づけられる」までは。
日本人ってのはなんでくさすのが得意なのかね？
おいらのまわりだけかしら？
人間の認識機構もろくに判ってない状態で「顔認識」なんてのはかなり「スジが悪い」技術だと思うんだよね。
だからそちら方向の応用を目指すという話が出れば、当然見込みがありそうなのか議論する。
その過程で当然マイナス要因をあげつらう。
それは当然必要な作業だと思う。
問題は「あげつらう」だけで終わっちゃうことだよな。
いったん「あげつらう」と、あげつらった人間を否定せずに話を納める先は「じゃあやらない」という選択肢しか残らないというか。
建設的な議論がそもそも訓練できてないというか。
どうなんだろ？
英語圏ネット空間は地に着いてそういうところがありますからね。英語圏の空間というのは、学術論文が全部あるというところも含めて、知に関する最高峰の人たちが知をオープン化しているという現実もあるし。途上国援助みたいな文脈で教育コンテンツの充実みたいなのも圧倒的だし。頑張ってプロになって生計を立てるための、学習の高速道路みたいなのもあれば、登竜門を用意する会社もあったり。そういうことが次々起きているわけです。
SNSの使われ方も全然違うし。もっと人生にとって必要なインフラみたいなものになってるわけ。
――日本のSNSは、人生に必要なインフラになっていない、という意味でしょうか。
なってないんじゃないんですか？ 職を探すとか……。人生のインフラ、学習、生計を立てる、キャリアを構築する、みたいな。
――上に上がるためのインフラにはなっていない、と。
上に上がるため、自分を高めていくため、という流れがあるかというと、部分的にはあるかもしれないけれど、比較論で言えば英語圏と日本語圏とずいぶん違うと思いますけどね。
――英語圏のそういったあり方が方が好き、という、好き嫌いの問題だということでしょうか。どっちが優劣、といった意識はあるんでしょうか。
好きだというのはあるよ。人間だからね。ただ、客観的に見て違うよね。ここはどうだろう。そこについて「事実認識が間違っている」という論は立たないんじゃないかな。
――その「違い」に対して、日本のネット空間にはある種、がっかりしたと。
アメリカにだってダメなところはいっぱいあるけれど。
ネットはすごくニュートラルなものでしょ。道具だから。上から下まで正規分布みたいになるよね、普通。ニュートラルなものって。
ニュートラルなものって相対化されるじゃない。いいことから悪いことまで全部出てきて、悪いところは相対化されるじゃない。いいとこもあれば悪いところもあるよね。
日本のネット空間もそうなんだけど。その比率がずいぶん違う感じがするなあ。
(略)
ただ、素晴らしい能力の増幅器たるネットが、サブカルチャー領域以外ではほとんど使わない、“上の人”が隠れて表に出てこない、という日本の現実に対して残念だという思いはあります。そういうところは英語圏との違いがものすごく大きく、僕の目にはそこがクローズアップされて見えてしまうんです。
Permalink | コメント(0) | トラックバック(0) | 22:49
*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画素毎とかでスキャンしていけば良い
*9：といっても4年前の話
*10：おいらは高校（理数科）の物理の課題研究で「逆立ち独楽」の原理をやろうとして、図書館で文献を調べてて出てきた偏微分係数ごときで挫折したけど。習ってないから。当時ネットがあればどうだったかなあ。やっぱだめかな
*11：Rainer Lienhart and Jochen Maydt. An Extended Set of Haar-like Features for Rapid Object Detection. IEEE ICIP 2002.
