ロボットビジョン特論

画像特徴（点、直線、領域）の検出と識別-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
モデルの登録
Ｎ個の点によって表されたモデル
M  {P1 , P2  , PN )から、2点Pi , Pjを選択
点i,jを基底とする場合
する。これらの 2点から、
Pj  Pi
X ij 
 ( xij , yij ), Yij  ( yij , xij )
2
Pj  Pi
点j,kを基底とする場合
となる直交基底を生成する。この基底
で表された各特徴点の座標値を求める
ことにより、図に示す
不変特徴の集合
{( x f , y f )}  {( X ij  (Pk  Pi ), Yij  (Pk  Pi )}　が得られる。この
{( x f , y f )}はもとの点
集合{Pi }が平行移動や回転、拡大など
の座標変換を受けても変化しないとい
う性質を持っている
Basis Geometric
Hashing
全ての２点の組合せから
生成される基底に対して
それぞれ不変特徴を求め、
それらを全てHash Tableに
登録しておく
Wolfson and Rigoutsos, Geometric Hashing, an Overview, 1997
Basis Geometric Hashing
4
3
1
5
2
モデルの多重記述により、モデルと相似な図形が与えられたとき、
この図形に含まれる任意の2点から求められる不変特徴とHash Table
上に記録された（モデル、基底）の組のどれかが一致することが保証
Wolfson and Rigoutsos, Geometric Hashing, an Overview, 1997
Wolfson and Rigoutsos, Geometric Hashing, an Overview, 1997
Geometric Hashing
対象とするモデルの全てに関して同様に記述
を行っておくことにより、複数のモデルを同時
に扱うことが可能となる
Geometric Hashingの投票と識別１
1. Hash Tableの各要素に対する投票数を０にする
2. 画像からまだ選択されていない任意の2点を選択
し、基底を求める
3. この基底に対して画像上の全ての点の不変特徴
を計算し、対応するHash Table中の要素の投票
度数を各々１増加させる
4. 投票終了後、（モデル、基底）の組ごとに投票度
数を集計し、予め与えた閾値を越えるものがある
かどうかを調べる。閾値を越えた投票が得られた
ものがなければ、1．の処理に戻る
Geometric Hashingの投票と識別２
5．高い投票が得られた（モデル、基底）組の基底と、
画像から求められた基底を対応付ける座標変換を
求める
6．求められた変換を用いてモデルを画像上に写像し、
モデルにマッチする特徴点が十分存在することを確
認する。特徴点が十分存在すれば終了し、そうでな
ければ1．の処理に戻る
画像中に存在する複数の対象を識別、検出する場
合には、モデルにマッチする特徴点集合を取り除き
ながら、上記の手続きを繰り返し行う
Geometric Hashingの意味
1. Hash Tableに登録された形状モデ
ルは、不変特徴によって記述され
た形状の「テンプレート」と見なす
ことができる
2. Geometric Hashingにおいて、
“ポーズを固定する”ということは、
画像から不変特徴を求める際に１
つの基底を用いることを意味
Geometric Hashingの性質
「基底によって画像を不変特徴に変換し、Hash Table
上で複数のテンプレートとのマッチングを行う」という
処理を様々な基底について繰り返す
投票と多数決に基づくアルゴリズム
の特長（安定性）
• より多くの証拠情報によって支持される仮説を求め
るという多数決原理に基づく手法であり、雑音など
によって生じる偽の特徴点が含まれる場合でも安定
に動作する
• 局所的な特徴のみを用い、特徴点間の連結性を用
いないため、遮蔽などによって特徴点が欠落した場
合でも対象の検出・認識が可能である
投票と多数決に基づくアルゴリズム
の特長（拡張性）
• 任意形状の検出・認識に適用できる。特に
Geometric Hashingでは、画像から3次元物体の識
別を行ったり、アフイン変換に対する不変特徴を用
いるなどの拡張も比較的容易に実現できる
• 投票計算が各特徴点ごとに独立に行われるため、
計算の並列化が容易である
投票と多数決に基づくアルゴリズム
の問題点（精度）
• 画像中に複数の図形が含まれる場合、異なる図形
からの投票が投票空間上で重畳する
• 特徴点の誤差（位置の変動）により、投票空間中で
の投票位置がずれてしまう
• 投票空間の標本化が不適切な場合、Aliasingが生
じ、投票数に偏りが生じる
エイリアシング（Aliasing）：ぎざぎざ
投票と多数決に基づくアルゴリズム
の問題点（計算コスト）
• Hough変換において、パラメータ空間中のセルを表
現するために用いられるメモリは、空間の次元数に
対して指数関数的に増加する
• 投票に要する計算は、投票軌跡の次元数に対して
指数関数的に増加する
• Geometric Hashingでは、同一の図形に含まれる複
数の点から基底を選択する必要があるため、基底
の選択を何回も繰り返さなければならない
• 投票数の集計を（モデル、基底）の組毎に行わなけ
ればならない
現状のアルゴリズムの限界
弾性輪郭モデル
（Snakes）動的輪郭モデル
Snakes収束の例
今後の展望
• 具体的な表現が与えられていない対象に関しても
適用可能な「投票と多数決に基づく対象の検出・認
識アルゴリズム」の開発
解決の方針としては、
• 特徴点の座標値のような定量的特徴ではなく、定性
的特徴を用いる
• 統計的パターン認識手法を併用する
などが考えられる
出席チェック
投票と多数決原理に基づく図形の検出・識別法は何
種類がある？それぞれの名前と機能を記入してくだ
さい。
学籍番号と名前を記入してください。
カラー情報の表現と解析
参考書：
●南敏、中村納
画像工学(増補)―画像のエレクトロニクス―
コロナ社
●松山隆司、久野義徳、井宮淳：
コンピュータビジョン --技術評論と将来展望-新技術コミュニケーションズ、1998
色に関するCV研究の歴史1
●色の知覚は形，色，動さというhuman visionの3要素
の一つで，これの解明にはニュートンにはじまる長い歴
史が視覚研究において存在する
●CVに色の情報が利用され始めたのは歴史的に見て
浅く，カラー映像機器の普及とともにカラー画像の利用
は盛んになった
●カラー画像処理の初期のレベルでは，白黒画像の処
理技術を単に3次元的に拡張することが多く，色情報の
有効な利用にはほど遠かった
●1980年代後半から人間の色の知覚を考慮したCV研
究が盛んになり，色覚の機能の一部を機械で実現する
ためのアルゴリズムの研究が増えてきた
色に関するCV研究の歴史2
●与えられたカラー画像の色彩情報処理にと
どまらず，画像から照明光を推定したり，対象
物体の材質を予測したりすることまで研究
●この流れは，色を物体表面に付属した性質
（属性）としてのみ捕えるべきでなく，心理物理
現象を通じて知覚されたものとしてとらえるべき
であることを意味
色の知覚をどのように表現するかはカラー画像
を取り扱ううえでまず重要となる
色知覚とカラーの基礎
色知覚：
我々が物を見る時、色々な色を持っていることを感ずる
対象物からの放射エネルギーの分布と、観測者の視知
覚の特性によって定まる
カラーの3要素：光源，物体，視覚系
●物理学
・照明
・反射
●知覚
・精神生理学
・知覚生理学
Electromagnetic Spectrum
電磁スペクトル
可視光はほんの僅か！
nm: 10^-9 ナノメールト
Visible Light
可視光
Wavelength  in nanometer
Colored light is electromagnetic energy
between 400 and 750nm
White Light

太陽、電球は可視光の全ての周波数を発射

人間はそれを“white light”として知覚する
赤
紫
Sunlight Spectrum
太陽光のスペクトルは、可視光の波長範囲とほぼ同じ
放射光のパワーもほぼ平坦
Light Spectrum of Fluorescent Light
From Osram
蛍光灯のスペクトルは、可視光の波長範囲とほぼ同じ
しかし、放射光のパワーが平坦ではない
White Light and Color

白色の光が物体に入射
されると、表面からの反
射と物体の中に入ってか
らの反射がある

人間が知覚された物体
の色はこの反射コンビの
周波数より決定される
Hue（色）

Hue（色）：支配波長
• 色のintensityは全ての可視光のエネルギー
の積と比例
Saturation（彩度）

色の濃さ
• 支配の光と“white light”のエネルギーの比より寄与
薄い色の場合
濃い色の場合
Intensity vs. Brightness（明るさ）

Intensity: 光源から発射された単位時間・角度・
面積の放射エネルギー
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）
●代表:カラーコンスタンシ(色恒常性)を実現する研究
●人間の色の知覚の重要な性
質：照明光の色が変化しても人
間にとって色の見え方は大きく
変わらない
●屋外シーンでの物体認識に
はこの性質が有効となる

Download Report