画像特徴（点、直線、領域）の検出と識別-3 Hough変換 投票と多数決原理に基づく幾何学的対象の検出と識別 呉海元＠和歌山大学 参考書： 松山隆司、久野義徳、井宮　淳、 　　　　　　コンピュータビジョン　ー技術評論と将来展望ー 　　　　　　新技術コミュニケーションズ

投票と多数決原理に基づく図形の検出・識別法 　投票と多数決原理に基づく図形の検出・識別法 Hough変換（P.V.C.Hough、1962) 2値画像から、直線の検出 Hough変換（R.O.Duda and P.E.Hart、1972) 2値画像から、円、楕円の検出 一般化Hough変換（D.H.Ballard、1981) 2値画像から、平行移動、回転、拡大などの変換を受けた任意形状の図形の検出 Geometric Hashing（Y.Lamdan et al.、1988) 2値画像から、予め与えた複数の図形集合の検出・識別

ポーズが固定 形状に投票/多数決

Geometric Hashing 不変特徴を計算 Hash Table中の対応要素に “モデル、記述に用いた基底” の組を登録 Compute invariants 不変特徴を計算 List of objects Verify Hash Table中の対応要素に “モデル、記述に用いた基底” の組を登録

Basis Geometric Hashing 拡大 縮小 回転 平行移動 点4と点1から生成された基底に基づいて、 Hash Tableにモデルを登録するイメージ Wolfson and Rigoutsos, Geometric Hashing, an Overview, 1997

モデルの登録 点i,jを基底とする場合 点j,kを基底とする場合

Basis Geometric Hashing 全ての２点の組合せから 生成される基底に対して それぞれ不変特徴を求め、 それらを全てHash Tableに 登録しておく Wolfson and Rigoutsos, Geometric Hashing, an Overview, 1997

Basis Geometric Hashing 3 4 1 2 5 モデルの多重記述により、モデルと相似な図形が与えられたとき、 この図形に含まれる任意の2点から求められる不変特徴とHash Table 上に記録された（モデル、基底）の組のどれかが一致することが保証 Wolfson and Rigoutsos, Geometric Hashing, an Overview, 1997

Wolfson and Rigoutsos, Geometric Hashing, an Overview, 1997

Geometric Hashing 対象とするモデルの全てに関して同様に記述 を行っておくことにより、複数のモデルを同時 に扱うことが可能となる

Geometric Hashingの投票と識別１ Hash Tableの各要素に対する投票数を０にする 画像からまだ選択されていない任意の2点を選択し、基底を求める この基底に対して画像上の全ての点の不変特徴を計算し、対応するHash Table中の要素の投票度数を各々１増加させる 投票終了後、（モデル、基底）の組ごとに投票度数を集計し、予め与えた閾値を越えるものがあるかどうかを調べる。閾値を越えた投票が得られたものがなければ、1．の処理に戻る

Geometric Hashingの投票と識別２ 5．高い投票が得られた（モデル、基底）組の基底と、画像から求められた基底を対応付ける座標変換を求める 6．求められた変換を用いてモデルを画像上に写像し、モデルにマッチする特徴点が十分存在することを確認する。特徴点が十分存在すれば終了し、そうでなければ1．の処理に戻る 　画像中に存在する複数の対象を識別、検出する場合には、モデルにマッチする特徴点集合を取り除きながら、上記の手続きを繰り返し行う

Geometric Hashingの意味 Hash Tableに登録された形状モデルは、不変特徴によって記述された形状の「テンプレート」と見なすことができる Geometric Hashingにおいて、“ポーズを固定する”ということは、画像から不変特徴を求める際に１つの基底を用いることを意味

Geometric Hashingの性質 　「基底によって画像を不変特徴に変換し、Hash Table上で複数のテンプレートとのマッチングを行う」という処理を様々な基底について繰り返す

投票と多数決に基づくアルゴリズムの特長（安定性） より多くの証拠情報によって支持される仮説を求めるという多数決原理に基づく手法であり、雑音などによって生じる偽の特徴点が含まれる場合でも安定に動作する 局所的な特徴のみを用い、特徴点間の連結性を用いないため、遮蔽などによって特徴点が欠落した場合でも対象の検出・認識が可能である

投票と多数決に基づくアルゴリズムの特長（拡張性） 任意形状の検出・認識に適用できる。特にGeometric Hashingでは、画像から3次元物体の識別を行ったり、アフイン変換に対する不変特徴を用いるなどの拡張も比較的容易に実現できる 投票計算が各特徴点ごとに独立に行われるため、計算の並列化が容易である

投票と多数決に基づくアルゴリズムの問題点（精度） 画像中に複数の図形が含まれる場合、異なる図形からの投票が投票空間上で重畳する 特徴点の誤差（位置の変動）により、投票空間中での投票位置がずれてしまう 投票空間の標本化が不適切な場合、Aliasingが生じ、投票数に偏りが生じる 　　　　　　　　　　　　　　　　　エイリアシング（Aliasing）：ぎざぎざ

投票と多数決に基づくアルゴリズムの問題点（計算コスト） Hough変換において、パラメータ空間中のセルを表現するために用いられるメモリは、空間の次元数に対して指数関数的に増加する 投票に要する計算は、投票軌跡の次元数に対して指数関数的に増加する Geometric Hashingでは、同一の図形に含まれる複数の点から基底を選択する必要があるため、基底の選択を何回も繰り返さなければならない 投票数の集計を（モデル、基底）の組毎に行わなければならない

現状のアルゴリズムの限界

弾性輪郭モデル （Snakes）動的輪郭モデル

今後の展望 具体的な表現が与えられていない対象に関しても適用可能な「投票と多数決に基づく対象の検出・認識アルゴリズム」の開発 解決の方針としては、 特徴点の座標値のような定量的特徴ではなく、定性的特徴を用いる 統計的パターン認識手法を併用する などが考えられる

出席チェック 学籍番号と名前を記入してください。 　投票と多数決原理に基づく図形の検出・識別法は何種類がある？それぞれの名前と機能を記入してください。 　学籍番号と名前を記入してください。

カラー情報の表現と解析 参考書： ●南 敏、中村 納 画像工学(増補)―画像のエレクトロニクス― コロナ社 ●松山隆司、久野義徳、井宮淳： ●南　敏、中村　納 　画像工学(増補)―画像のエレクトロニクス― 　コロナ社 ●松山隆司、久野義徳、井宮淳： 　コンピュータビジョン --技術評論と将来展望-- 　新技術コミュニケーションズ、1998

色に関するCV研究の歴史1 ●色の知覚は形，色，動さというhuman visionの3要素の一つで，これの解明にはニュートンにはじまる長い歴史が視覚研究において存在する ●CVに色の情報が利用され始めたのは歴史的に見て浅く，カラー映像機器の普及とともにカラー画像の利用は盛んになった ●カラー画像処理の初期のレベルでは，白黒画像の処理技術を単に3次元的に拡張することが多く，色情報の有効な利用にはほど遠かった ●1980年代後半から人間の色の知覚を考慮したCV研究が盛んになり，色覚の機能の一部を機械で実現するためのアルゴリズムの研究が増えてきた

色に関するCV研究の歴史2 ●与えられたカラー画像の色彩情報処理にとどまらず，画像から照明光を推定したり，対象物体の材質を予測したりすることまで研究 ●この流れは，色を物体表面に付属した性質（属性）としてのみ捕えるべきでなく，心理物理現象を通じて知覚されたものとしてとらえるべきであることを意味 色の知覚をどのように表現するかはカラー画像を取り扱ううえでまず重要となる

色知覚とカラーの基礎 色知覚： 我々が物を見る時、色々な色を持っていることを感ずる 　我々が物を見る時、色々な色を持っていることを感ずる 　対象物からの放射エネルギーの分布と、観測者の視知覚の特性によって定まる カラーの3要素：光源，物体，視覚系 ●物理学 　　・照明 　　・反射 ●知覚 　　・精神生理学 　　・知覚生理学

Electromagnetic Spectrum 電磁スペクトル 可視光はほんの僅か！ nm: 10^-9 ナノメールト

Visible Light 可視光 Colored light is electromagnetic energy Wavelength  in nanometer Colored light is electromagnetic energy between 400 and 750nm

White Light 太陽、電球は可視光の全ての周波数を発射 人間はそれを“white light”として知覚する 赤 紫

Sunlight Spectrum 太陽光のスペクトルは、可視光の波長範囲とほぼ同じ 放射光のパワーもほぼ平坦

Light Spectrum of Fluorescent Light Other representation of light spectrum Osram Biolux 6500K Daylight From Osram 蛍光灯のスペクトルは、可視光の波長範囲とほぼ同じ しかし、放射光のパワーが平坦ではない

White Light and Color 白色の光が物体に入射されると、表面からの反射と物体の中に入ってからの反射がある 人間が知覚された物体の色はこの反射コンビの周波数より決定される

Hue（色） Hue（色）：支配波長 色のintensityは全ての可視光のエネルギーの積と比例

Saturation（彩度） 色の濃さ 支配の光と“white light”のエネルギーの比より寄与 薄い色の場合 濃い色の場合

Intensity vs. Brightness（明るさ） Brightness: 知覚された光のIntensity 区別しない場合が多い

視覚生理学(Physiology of Vision) 網膜（retina） 桿状体(rods) 錐体(cones) color! 人が光源を見る時 Hue Saturation Brightness に対して反応

目から見た三色（RGB） 三種類の錐(状)体がある L or R, most sensitive to red light (610 nm) M or G, most sensitive to green light (560 nm) S or B, most sensitive to blue light (430 nm) 色盲の理由：ある種類の錐(状)体に問題がある

色恒常性（Color Constancy） ●代表:カラーコンスタンシ(色恒常性)を実現する研究 ●人間の色の知覚の重要な性質：照明光の色が変化しても人間にとって色の見え方は大きく変わらない ●屋外シーンでの物体認識にはこの性質が有効となる