画像処理論 第6回 佐藤 洋一 生産技術研究所 情報理工学系研究科電子情報学専攻／情報学環 http://www.hci.iis.u-tokyo.ac.jp/~ysato/ 前回講義内容の復習 ハフ変換 一般化ハフ変換 幾何学的ハッシング エッジ点からの直線の検出 ハフ変換（Hough transform）が良く用いられる パラメータ空間への投票により直線を検出 パラメタ空間における投票 画像中の各エッジ点ごとにパラメタ空間で直線を追加 画像中の直線に対応するパラメタ(m,c)にピーク →ハフ変換の基本的な考え方 c y c = − xm + y (x,y) c = − x′m + y′ (x’,y’) x m 直線を表すパラメタ空間 一般化ハフ変換 1. 各エッジ点（x,y）において、gradientからエッジ方向θを計算 2. 形状定義表を参照し、基準点の候補位置Qに投票 3. 全ての投票後に、候補位置Qにピークがあれば、対象物体を その位置に検出 Q xQ = x + r (θ ) cos[α (θ )] Q yQ = y + r (θ ) sin[α (θ )] 回転・スケールの考慮 1. 各エッジ点（x,y）において、gradientからエッジ方向θを計算 2. 全ての回転Φ・スケール S に対して、式(1)と形状定義表を 参照し、基準点の候補位置Qに投票 3. 形状定義表のインデックスとなるエッジ方向は θ − Φ 最後に、パラメタ空間 ( x, y, S , Φ )においてピークを検出する Pi ( x, y ) Sri Q αi + Φ θ = θi + Φ θ −Φ 幾何学的ハッシング 一般化ハフ変換と似た物体検出法 モデル準備： 姿勢に対する不変特徴をハッシュテーブルに記録 幾何学的ハッシング モデル検出： 画像中特徴点から2点を基底として選択 各特徴点について、ハッシュテーブルのエントリに投票 最高得点のモデル・基底を検証 y 画像中特徴点 A１，４ A６，５ A１，４ A６，5 ３ ５ １ ６ ５ A１，４ A６，５ ４ １ １ A１，４ A６，５ ２ ３ A１，４ A１，４ ４ ２ A６，５ ５ モデルA x ４ ３ ２ 基底1-3の時、（A, 1-4)で最高得点 本日の講義の内容 RANSAC 対象領域の抽出 画像の2値化 Deformable contours RANSAC（RANdom SAmple Consensus） データ点からモデルをロバストにもとめる推定法 ポイントは出来るだけ少ない観測点からの推定 点組のランダムなサンプリングとサポートの検証の繰り返し 真の直線 外乱により影響を受けた直線 特長：外乱(outlier)に対してロバスト M. Fischler and R. Bolles, “Random sample consensus: a paradigm for model fitting with applications to image analysis and automatic cartography”, Communications of the ACM, vol. 24, no. 6, 1981. RANSAC for Image Mosaic RANSAC for 2D Homography xl = Hxr ここで、xは同次座標表現、Hは3x3行列 wx x x wy ≈ y ⇔ y w 1 RANSAC for 2D Homography xl = Hxr ここで、xは同次座標表現、Hは3x3行列 wx x x wy ≈ y ⇔ y w 1 4点のペアからHが決定される→RANSACによるHの推定 Creating Panoramas Creating Panoramas Creating Panoramas 基本手順 S個の点により定義されるモデルの場合 １．ランダムなサンプリング データ点からS点をランダムに選択 選択したS点からモデルパラメタを計算 ２．サポートの検証 データ点のうち、モデルに十分近い点（サポート）を選択 十分なサポートがあれば終了、or 以上の手順を十分な回数繰り返し ３．終了処理 モデルパラメタのサポート点を用いて、モデルパラメタを再推定 サポート判定のための閾値 モデルにどれだけ近ければサポートとするか？ 一般には経験的に閾値を調整 誤差が正規分布する場合には統計モデルにもとづいて計 算可能 ⇒資料参照(Hartley 4.7.1) 繰り返し回数に対する閾値 ランダムなサンプリングを何回繰り返せば十分か？ 正しいデータ点の確率が w で、確率 p で正解モデルを見つ けるのに必要な回数 N log(1 − p ) (1 − w ) = 1 − pより、N = log(1 − w S ) S N 例）2個の外乱を含む12点からp=0.99で直線を見つけるには N=4 log(1 − 0.99) ≈ 3.9 N= 2 log(1 − (10 / 12) ) サポート点数に対する閾値 どれだけのサポート点が得られれば十分か？ 経験的には、サポート点数／データ点数が確率 w に近くな るように設定 例）w=0.8の場合、12×0.8=約10個 確率wが未知の場合の工夫 実際には w が予め分かっている場合は稀 控え目な見積もりから徐々に絞り込む 低めのwで推定し、求められたモデルに対するサポート点の割合 を元にwとNを更新し、再度推定を繰り返す N回繰り返された段階で終了 具体的な手順 １．N=∞, w=0.5 に初期化 ２．繰り返し回数が N 回に達するまで以下を繰り返す S点をランダムに選び、モデルパラメタの推定＋サポート点の判定 w=サポート点数／データ点数 に更新 新しい w と一定の確率pをもとに N を再計算 対象領域の抽出 2値画像 前景（foreground、対象物）と背景（background） 例）文書画像における文字領域と、顕微鏡画像における細胞領域 画像の2値化 画像の輝度値や色度値などに閾値処理 I (i, j ) ≥ T 1 B(i, j ) = I (i, j ) < T 0 大局的閾値法 画像全体に同一の閾値 局所的閾値法 局所領域ごとに閾値を変更（可変閾値法） ヒストグラム 画素値の分布をヒストグラムにより表現 横軸が画素値、縦軸は度数（頻度、カウント値） ヒストグラムと閾値 いかにして適当な閾値を設定するか？ G画像 http://www.dai.ed.ac.uk/CVonline/LOCAL_COPIES/MARBLE/medium/bina ry/histograms.html p-タイル法 対象物の面積の割合が既知の場合に利用 ヒストグラムの累積値（累積ヒストグラム）がpになる画素値 が閾値 1-p T モード法 ヒストグラムが双峰性（bimodal）を持つ場合に利用 閾値を谷の底に設定 1. 2. 3. 局所的最大値を与える画素値t1, t2を求める t1とt2の間で局小値を与えるtを求める 次の条件を満たせば閾値として採用 f (t ) t 2 − t1 > C1 かつ < C2 min[ f (t1 ), f (t 2 )] C1,C2の調整が必要 Otsu’s method ２つのクラス間の分離を最大化する閾値を計算 p-タイル法やモード法と違いパラメタの調整が不要 ヒストグラムが双峰性でなくとも適用可能 →しかし、必ずしも適当な閾値とは限らない Nobuyuki Otsu (1979). "A threshold selection method from gray-level histograms". IEEE Trans. Sys., Man., Cyber. 9 (1): 62–66 分離度の最大化 閾値Tにより全画素がクラスC1とC2に分離 クラス内分散 σ W 2 クラス間分散 σ B 2 ω1σ 12 + ω2σ 2 2 = ω1 + ω2 ω1 ( µ1 − µ ) 2 + ω2 ( µ 2 − µ ) 2 = ω1 + ω2 ただし、µ1とµ 2 , σ 1とσ 2 , ω1とω2は各クラスの平均、分散、画素数 これらの比により定義される分離度を最大化 σ B (T ) ) T = arg max( 2 T σ W (T ) 2 分散比の例 濃度値のヒストグラム Tに対する分散比の変化 閾値処理では扱えないケース 画素値だけでは分離が困難な場合も多い Deformable Contoursの利用 大動脈部抽出の例 Deformable Contours 対象領域を抽出するアプローチの一つ Active Contoursとも呼ばれる Snakeが最も有名 Think of a snake as an elastic band: of arbitrary shape sensitive to image gradient that can wiggle in the image represented as a necklace of points “Original” SNAKES [Kass87] Snakes: Active contour models, M. Kass, A. Witkin, D. Terzopoulos, International Journal of Computer Vision, 1(4), 1987 エネルギー関数 エネルギー関数の最小化により輪郭を決定 エネルギーは輪郭の場所と形に依存 どのようにエネルギー関数を定義するか？ 3種類の力を考慮し、頂点位置を更新 Edge attraction Continuity Smoothness External force It needs to be attracted to contours: Edge pixels must “pull” the snake points. The stronger the edge, the stronger the pull. The force is proportional to |∇ I| Edge attraction Continuity Smoothness Internal force (continuity) The snake should not break apart! The farther the neighbors, the stronger the force The force is proportional to the distance |Pi – Pi-1| Edge attraction Continuity Smoothness Internal force (smoothness) The snake should avoid “oscillations” Penalize high curvature Force proportional to snake curvature Edge attraction Continuity Smoothness Contour Parametrization Consider a contour parameterization p=p(s) where s is the “arc length” s p(s) Snake Energy Functional Energy Functional is defined as: E= ∫ (a ( s ) Econt ( s ) + b( s ) Esmooth( s ) +c( s ) Eedge ( s )) ds 2 2 2 dp d p = ∫ (a( s) + b( s ) 2 +c( s )( − ∇I ( p ) )) ds ds ds internal external where a,b,c are “weights” to control influence. Edge attraction Continuity Smoothness In discrete form Given a snake with N points p1,p2,…,pN, E is simplified into: E= ∑ ai Econt ( pi ) + bi Esmooth ( pi ) + ci Eedge ( pi ) N i =1 Econt ( pi ) = (d − pi − pi −1 ) 2 Esmooth ( pi ) = pi −1 − 2 pi + pi +1 Eedge ( pi ) = − ∇I ( pi ) 2 Edge attraction Continuity Smoothness Minimization by Greedy Algorithm • Each point p moves within a small window to minimize the energy Neighbors U(p) p • Compute the new energy for each candidate location • Move the point to the one with the minimum value Keeping corners … Before starting a new iteration: Search for “corners”: max curvature large gradient Corner points should not contribute to the energy (set bi = 0) Snake Algorithm Input: Gray scale image I A chain of points p1,p2,…,pN f is the fraction of points that must move to start a new iteration U(p) is a neighborhood around p d is the average distance between snake points. Snake Algorithm (continued) While the fraction of moved points > f For i=1,2,…,N Find a point in U(pi) s.t. the energy is minimum, Move pi to this location For i=1,2,…,N Estimate the curvature k=|pi-1–2pi+pi+1| Look for local max, and set bmax = 0 Update d Applications Examples Segmentation Tracking 本日の講義内容のまとめ RANSAC 対象領域の抽出 画像の2値化 Deformable contours 参考資料 谷口 5.1-5.2章 Hartley 4.7.1 RANSAC論文 Trucco&Verri 5.4章
© Copyright 2024 ExpyDoc
