画 像 情 報 処 理 論 及 び 演 習 I 第 8-9 回 講 義 水 曜 日 1 限 教 室 6218 情 報 処 理 実 習 室 情 報 デザイン 専 攻 - 領 域 抽 出 - ラべリング 吉 澤 信 shin@riken.jp, 非 常 勤 講 師 大 妻 女 子 大 学 社 会 情 報 学 部 今 日 の 授 業 内 容 www.riken.jp/brict/yoshizawa/lectures/lec08.pdf www.riken.jp/brict/yoshizawa/lectures/report02.doc 1 ラべリング 2 演 習 : ラべリング のプログラムを 動 かしてみる. 大 津 法 プログラミング. 第 2 回 のレポート(6/26 〆 切 )は 今 日 の 内 容 なので 頑 張 ってねーp(^^)q 前 回 の 復 習 : 閾 値 による 二 値 化 閾 値 閾 値 前 回 の 復 習 : 大 津 の 二 値 化 法 白 の 分 布 と 黒 の 分 布 の 分 離 度 が 大 きくなるように 閾 値 を 自 動 的 に 決 める. 分 離 度 :クラス 間 分 散 クラス 内 分 散. t 竹 本 RIKEN その 画 素 値 が 閾 値 (threshold)より 大 or 小 で 領 域 を 二 つに 分 ける. 0 255 黒 の 分 布 白 の 分 布 閾 値 : 64 閾 値 : 96 閾 値 : 128 閾 値 : 160 &ラべリング 二 値 化 後 の 典 型 的 処 理 として とラべリングがある. 二 値 化 ラべリング 前 回 の 復 習 :ラべリングとは? ラべリング(Labeling): 連 結 領 域 を 抽 出 する 事. 連 結 領 域 : 同 じ 画 素 値 の 繋 がった 領 域. - 4 連 結 : 左 右 上 下. - 8 連 結 :3x3の 領 域. S. Yoshizawa, RIKEN 二 値 化 多 値 化 ラべリング 1
4 連 結 VS 8 連 結 4 連 結 8 連 結 mikilab.doshisha.ac.jp ラべリングのアルゴリズム( 再 帰 ) 再 帰 関 数 で 書 くと 超 簡 単! bin[i][j]: 黒 or 白. out[i][j]: 出 力 のラベル. sx,sy: 画 像 サイズ. 多 値 へも 簡 単 に 拡 張 可 能. 1. main 関 数 の 中 で 黒 なら 再 帰 関 数 を 呼 び 出 す. 2. 再 帰 が 帰 ってきたらラベル を 変 えて 繰 り 返 し. 1. 再 帰 関 数 で8 連 結 の 周 りを 呼 び 出 しながら 同 じ 値 ならラベルを 付 けていく. 2. 同 時 に 黒 白. 重 要 :アルゴリズム(キュー or スタック) 残 念 ながら 再 帰 関 数 は 入 れ 子 ( 階 層 的 な 呼 び 出 し)の 回 数 がOS 毎 に 制 限 ( 高 々10-20 程 度 ). 定 理 : 再 帰 アルゴリズムは 繰 り 返 しアルゴリズム に 常 に 書 き 換 える 事 が 可 能. ラべリングのアルゴリズム(キュー or スタック)2 演 習 のlabel.h 初 期 Push Popのループ 再 帰 の 代 わりにキューやスタック 構 造 を 使 う. Queue f(f(f(f( )))) Push 再 帰 のmainとほぼ 同 じ. Put 関 数 再 帰 呼 び 出 し Pop Stack Pop 8 方 向 へPush. (thinning, 骨 格 化 :skeletonization) 領 域 抽 出 後 ( 二 値 化 )に 領 域 を 線 状 に 簡 略 化 する 事 ただ し 通 常 は の 二 値 画 像 と 同 位 相 の 形 状. 出 来 るだけ 中 心 に 細 く 端 点 でな い 境 界 画 素 を 削 除 していく. その2 同 位 相 : 連 続 変 形 で 変 換 可 能 である 事 : - 球 平 面 トーラス 等 はそれぞれ 異 なる 位 相. - 穴 ( 境 界 )の 数 ハンドル(トーラス)の 数 等 で 分 類. skullsinthestars.com T. Day et al., SIGGRAPH 08. danilnagy.wordpress.com 文 字 認 識 等 で 非 常 に よく 用 いられる! 異 なる 位 相 Wikipedia のコップと トーラスは 同 位 相 2
連結数 細線化その３ 連結数 境界線追跡をしたとき その画素を通過 する回数 消去で連結数が変わらない 同位相. N4 : 0 1 2 3 4 中心軸(Medial Axis)の近似である事が多い. 細線化後は線分の幾何特徴(長さや円形度等)を計算. 様々な方法 境界 連結数を変えない 端点を消去. - テンプレートを用いた繰り返し法 Stentiford法 Hilditch法(連結数を使う 少し複雑なのでskip 演習のthinning.hに実装) 田村法 Zhang-Suen法. 中心軸を用いる方法 etc. 4連結 8連結 中心軸(Medial Axis) 中心軸と距離場 定義: 接触円の中心の軌跡. 接触円 二点以上で境界に接している境界内の円. 中心軸は距離場の等高線が特異点となる点の集合 H. Blum, 1967. 境界 接触円 境界との 接点 x 中心軸 xでの厚み L. Liu et al. PG 10. www.cim.mcgill.ca/~friggi 接触円群 中心軸 math.berkeley.edu/~sethian 特異点 滑らか でない点 微分 出来ない点 勾 配が零. 境界 www.math.ucla.edu ボロノイ図(Voronoi Diagram) ２点間を結ぶ線分の垂直２等分線の一般化 ボロノイ図と中心軸 中心軸はボロノイ図の滑らかな曲線への一般化である 一般化Voronoi図 の部分集合 www.qhull.org 3
3D中心軸 中心軸の応用 多次元の中心軸もあり CGやCAD等で応用されている. 応用: 認識, 接触触判定, 曲面再構成, Meshing, 変形, ３Dの中心軸は面 孤立点と線の集合 N. Amenta et al., SIGGRAPH 98. B. Levy and Y. Liu, SIGGRAPH 10. S. Zhu and A. Yuille, IJCV, 20(3), 1996. M.-C. Chang and B. Kimia, CVPR 08. S. Yoshizawa et al., EG 07. G. Bradshaw and C. O Sullivan, ACM SCA 02. 演習 ラべリング 細線化をしてみよう 細線化の応用例 ベクトル化 www.riken.jp/brict/yoshizawa/lectures/ex04.zip 前回の続き+ラべリング 細線化 1. Alexandrina Orzan et al. SIGGRAPH 08. 2. 演習８ Ex04内に用意されたプログラム群を動かし て ラべリングと細線化を実行. ラべリングの閾値を 変えて実行してみましょう. (前回の続き)クラス間分散を計算して大津法のプロ グラムを作成(Lec07.pdfの演習７). レポート１ 再提出含む の採点結果を取りに来てください. 3. レポート２(６月２６日〆切)を解く. J. Sun et al., SIGGRAPH 2007. 演習プログラムの説明１ Ex04.zipをダウンロード 解凍. コンパイルは make 詳細はMakefileを見てください. LabelingRemoveSmall.cxx:(引数の数3) pgmを大津法 ラべリン グ(8連結) 第三引数以下の領域サイズを一つにまとめる(小さい 面積の領域を統合) ラベル毎に疑似カラーでppmで保存. 実行方法./LabelingRemoveSmall 入力pgm 出力ppm 削除 する領域の面積閾値(int) Thinning.cxx(引数の数2): 大津法 Hilditchの細線化. 実行方法:./Thinning 入力pgm 出力pgm 演習プログラムの説明２ ラべリングのIDを1づつ付けた場合に 各ラベルを輝度値としてグレー スケール画像に出力すると 連結領域が分かりにくい 疑似カラーで 表示. グレースケール:0,1,,255 疑似カラーマップ color.h 領域数３ - ヘッダーファイル otsu.h: 大津法 label.h: ラべリング color.h: 疑似カラー thinning.h: 細線化. 実装の細部に興味がある人は見てください. 入力 大津法二値化 ラべリング ID=輝度値 ラべリング疑似カラー 4
演 習 プログラムの 説 明 3 疑 似 カラーでも 領 域 数 が 多 いと 分 かりにくい. 領 域 の 面 積 ( 画 素 数 ) が 閾 値 より 小 さい 領 域 は 全 て 同 じラベル( 黒 )+ラベルの 振 りなおし. 領 域 数 627 領 域 数 46 領 域 数 31 領 域 数 26 演 習 プログラムの 実 行 例 領 域 抽 出 +ラべリングを 行 うと 表 示 の 綺 麗 さだけでなく 定 量 的 な 解 析 が 可 能 になる( 数 面 積 境 界 形 状 の 長 さや 曲 率 など). 領 域 数 220 領 域 数 19 領 域 数 14 領 域 数 9 閾 値 :0 閾 値 :30 閾 値 :60 閾 値 :120 領 域 数 627 閾 値 :0 閾 値 :30 閾 値 :60 閾 値 :120 領 域 数 220 大 津 法 二 値 化 ラべリング(ID= 輝 度 値 ) ラべリング 疑 似 カラー 大 津 法 二 値 化 ラべリング(ID= 輝 度 値 ) ラべリング 疑 似 カラー 演 習 プログラムの 実 行 例 2 は 幅 が1 画 素 の 線 になる. 線 あり: 黒 なし: 白 の 表 示. 演 習 プログラムの 実 行 例 3 後 期 でやるフィルタ 処 理 エッジ 強 調 と 組 み 合 わせると より 有 用. 大 津 法 二 値 化 大 津 法 二 値 化 エッジ( 勾 配 ) 強 度 スタイル 化 エッジ スタイル 化 エッジ 演 習 プログラムの 実 行 例 4 来 週 の 予 定 5