画像処理工学
２値画像とその解析方法
画像の２値化
•
２値画像–
１画素あたり１ｂｉｔ（０か１）の情報を持つ画像–
表示のために０（黒）か２５５（白）とする•
２値画像の利用–
文字認識や形状認識で利用される–
画像を線図形化して解析処理を行う•
２値画像処理の利点–
画像のデータ量が少なくてすむ（画素数×１ｂｉｔ）–
データ量が少ないので，処理の高速化が図れる画像の２値化
•
多値画像から２値画像へ（画像の２値化）–
花の部分だけを抽出する多値画像 ２値画像
こちらの画像の白い部分についてのみ 解析処理を行う（形，大きさ，
etc...
）画像の２値化
•
画像の２値化処理–
しきい値（閾値；ｔｈｒｅｓｈｏｌｄ）を基準に，各画素の濃度 値を０か１に変換する•
固定しきい値処理–
ある濃度値をしきい値t
としてとする
–
実際には，ヒストグラムを見ながら試行錯誤的にt
の 値を決定する( )
( )
1 [ ][ ] [ ][ ]
0 [ ][ ] f i j t g i j
f i j t
≥
= < t f [i][j]
g [i][j]
z m 0
1
画像の２値化
•
固定しきい値処理による画像の２値化固定しきい値処理
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
入力画像：img[N][M]
結果画像：res_img[N][M]
入力画像img[][]の入力
for(y = 0; y < N; y++){
for(x = 0; x < M; x++){
img[y][x]がしきい値t以上であれば res_img[y][x]に255を代入
そうでなければres_img[y][x]に0を代入
}
}
結果画像res_img[][]の出力
画像の２値化
•
判別分析法–
しきい値をt
–
グループ（クラス）１ ： ０ ～t
－１ の濃度値を持つ画素–
グループ（クラス）２ ：t
～ ２５５ の濃度値を持つ画素–
それぞれのグループの濃度値の分散を求めるn f
( )
1 2
0 1 1 2
1 t
f f
n f f σ n
−
=
−
= ∑
( )
255 2
2 2 2
2 f t f
n f f σ = n
−
= ∑
グループ１の 濃度値の分散
グループ２の 濃度値の分散
： グループ
i
の画素数： 濃度値
f
の画素数： グループ
i
の濃度値 の平均値： グループ
i
の濃度値 の分散i 2
σ f i
n i
画像の２値化
•
判別分析法（続き）–
クラス内分散•
グループ内の値（データ）がどのくらいばらついているか–
クラス間分散•
グループ間がどのくらい離れているか( ) ( )
( ) ( )
{ } ( )
2 2 2
1 1 2 2 1 2
2 2
2 1 1 2 2 1 2
W
B F F
n n n n
n f f n f f n n
σ σ σ
σ
= + +
= − + − +
2 B 2
W
σ σ
が最大となるときのt
をしきい値とする クラス内分散クラス間分散
f
F ： 全画素の濃度値の平均値
クラス内分散が小さく（平均値に近い値に集中している），
クラス間分散が大きく（クラス間が離れている）なるように しきい値を決める
画像における連結性
•
４近傍および４連結–
ある画素を中心とし，その上下左右の画素を４近傍と いう–
４近傍中に中央の画素と同じ色（値）の画素が存在 する場合，それらの画素を４連結しているという： ４近傍画素 ４連結の例
画像における連結性
•
８近傍および８連結–
ある画素を中心とし，その周りの画素を８近傍という–
８近傍中に中央の画素と同じ色（値）の画素が存在する場合，それらの画素を８連結しているという
： ８近傍画素
８連結の例
画像における連結性
•
連結成分–
たがいに連結している同じ値を持つ画素の集まり•
図形成分–
２値画像における連結成分–
連結性の違い（４連結か８連結か）により，成分の数 が異なってくる４連結で見た場合の図形成分数 ： ３ ８連結で見た場合の図形成分数 ： １
画像における連結性
•
孔–
ある連結成分が他の色の連結成分を内部に含む孔
背景（白の画素）を８連結 で考えると，孔が外部と つながっていることになり 矛盾が生じる
図形を８連結で考えたら 背景は４連結で考える
２値画像における幾何学的性質
•
オイラー数–
連結成分の個数から孔の個数を引いた数１
V
： １の画素の総数E
：D
：１ １ １
１ １
１ １
T
：１ １
１
１ １ １
１ １ １ １
１ １
F
： １１ １ １
の配置の総数
の配置の総数
の配置の総数 の配置の総数
４連結の場合のオイラー数
G ( ) 4 = − + V E F
８連結の場合のオイラー数
G ( ) 8 = − − + − V E D T F
２値画像における幾何学的性質
•
距離–
画素間の遠近の程度を表す尺度•
ユークリッド距離•
４近傍距離（市街地距離）–
縦または横のみ移動できる条件での距離•
８近傍距離（チェス盤距離）–
８方向に移動できる条件での距離( i k − ) ( 2 + j l − ) 2
i k − + − j l
( )
max , i k − j l −
A[i][j]
，B[k][l]
間の 直線距離２値画像における幾何学的性質
•
各距離の違い–
中心画素からの距離を３つの距離で求める4 3 2 3 4 3 2 1 2 3 2 1 0 1 2 3 2 1 2 3 4 3 2 3 4
8 5 2 5 8
5 2 1 2 5
2 1 0 1 2
5 2 1 2 5
8 5 2 5 8
2 2 2 2 2
2 1 1 1 2
2 1 0 1 2
2 1 1 1 2
2 2 2 2 2
ユークリッド距離 ４近傍距離 ８近傍距離B
ラベリング
•
ラベリング–
２値画像上に点在している図形成分（連結成分）の それぞれに名前をつける処理–
図形成分の区別をしておけば，図形成分の個数や それぞれの特徴（面積など）を計算できるB B B B B B B B B
B C
C
B B B B
D D B
B B B
D D D
B D D
C B C B
B B
B
D B B
B B
B B
B B B
B B A
B B
B A A
B A
B B B A A A
B A A
B B
ラベリング
•
ラベリングのアルゴリズムの例–
８連結で考え，２回の走査を行う–
左上の画素から走査しながら，１の画素を見つける–
その画素f [i][j]
に隣接する画素のうちf [i
ｰ1][j
ｰ1]
，f [i
ｰ1][j]
，f [i
ｰ1][j+1]
，f [i][j
ｰ1]
の値とラベルを調べる
f [i][j ｰ 1]
f [i ｰ 1][j ｰ 1] f [i ｰ 1][j] f [i ｰ 1][j+1]
f [i][j]
ラベリング
•
ラベリングのアルゴリズムの例（続き）–
４つの画素すべてが０のとき，f [i][j]
に新しいラベル をつけて，次の画素を走査するすべて ０
ラベル ２ をつける
ラベリング
•
ラベリングのアルゴリズムの例（続き）–
４つの画素のうち，値が０のもの以外に１種類の ラベルがついている場合は，f [i][j]
に同じラベル をつけて，次の画素を走査する２
２
値が０でなく，ラベル２がついている
ラベル ２ をつける
２
ラベリング
•
ラベリングのアルゴリズムの例（続き）–
４つの画素のうち，値が０のもの以外に２種類以上 のラベルがついている場合は，その中で最も小さい ラベル番号をf [i][j]
につけるとともに，それらが同じ 連結成分であることを記憶しておき，次の画素を 走査する３
２ ２ ２ ２ ２ ２ ２
３ ３ ３ ３ ３
２
３
値が０でなく，ラベル２と３がついている
３ ２ ２
３ ２
ラベル 連結 関係
テーブルに記憶 ラベル ２ をつける
ラベリング
•
ラベリングのアルゴリズムの例（続き）–
最後まで走査が終わったら，左上から２回目の走 査を行い，ひとつの連結成分に対して同じラベル がつくように，ラベルをつけなおす３
２ ２ ２ ２ ２ ２ ２ ２
２ ２ ２
３ ３ ３ ３ ３ ３ ３ ３
３ テーブルを見ると
ラベル ３ は ラベル ２ と 同じ連結成分である
３
ラベル ２ につけなおす
２ ２ ３ ２
ラベル 連結 関係
•
膨張–
図形を外側に１画素分広げる処理–
拡張，伝播とも呼ばれる•
収縮–
図形を１画素分細くする処理–
侵食とも呼ばれる–
２値画像において，ノイズを除去する目的などに用い られる–
処理を何回行うかで結果が変わってくる（埋めてはいけない孔を埋めてしまうことがある）
膨張・収縮処理
•
膨張処理–
ある画素とその８近傍（または４近傍）のいずれかに 少なくともひとつの図形画素（１）がある場合，出力画素を１とする
膨張・収縮処理
1 : [ ][ ] [ ][ ]
0 : f i j g i j
=
あるいはその８近傍（または４近傍）
のいずれかが１のとき
膨張処理
その他のとき
•
収縮処理–
ある画素とその８近傍（または４近傍）のいずれかに 少なくともひとつの背景画素（０）がある場合，出力画素を０とする
膨張・収縮処理
0 : [ ][ ] [ ][ ]
1 : f i j g i j
=
あるいはその８近傍（または４近傍）
のいずれかが０のとき
収縮処理 １回
その他のとき
•
膨張処理と収縮処理の組み合わせ–
膨張→
収縮処理•
連結成分の小さな孔や幅の狭いくぼみの部分（亀裂や 分裂など）を埋める効果をもつ–
収縮→
膨張処理•
２値画像の小成分や幅の狭い部分（ひげなどのノイズ）を取り除く効果をもつ
膨張・収縮処理
•
境界（輪郭線）追跡–
広がりのある塊状図形の境界画素を抽出する–
図形の形状を解析するのに利用–
単に境界画素の集合を抽出するだけでなく，順序 付けられた画素の系列として抽出することができる境界追跡
A B
A B B
A B B
A B B
A A
A A
A A A A A A A A A A A
A A A A A A A
８連結で考えた場合の 境界追跡結果•
境界追跡のアルゴリズム（８連結）の例–
左上の画素から走査し，左側に０の画素が隣接する １の画素を見つけ，それを最初の境界画素とする–
すでに境界画素として認識されていたものであれば 無視する境界追跡
•
境界追跡のアルゴリズム（８連結）の例（続き）–
最初の境界画素を中心とする８近傍を，反時計回り に調べ，１の画素をみつける–
その画素を次の境界画素とする（下図の例では⑥の 画素）境界追跡
Ａ
③ ② ①
④
⑤
A
⑥
•
境界追跡のアルゴリズム（８連結）の例（続き）–
次の境界画素を見つけるときには，前の境界画素の（反時計回りに）隣りの画素から探索すればよい
境界追跡
A
Ａ①
A
②
③
A
④
② ①
A
③
④
A
⑤
A A
A
Ａ④ を次の 境界画素
とする
⑤ を次の 境界画素
とする
•
境界追跡のアルゴリズム（８連結）の例（続き）–
次の境界画素が，最初に認識された境界画素と一致 したときには追跡処理をやめて，次の走査を行う–
走査を行う上で，すでに境界画素とされているものは 無視していく境界追跡
A A A A
A A
A A
A A A A A A A A A A A
A A A A A A A
③ ② ①
A
A
A A
最初に境界画素として 認識された
次の走査を行う
•
境界追跡のアルゴリズム（８連結）の例（続き）–
外側の境界は，図形に対して反時計回りに追跡さ れる–
孔の部分の境界は，図形に対して時計回りに追跡 される境界追跡
A A B
A A
A A
A A
A A A A A A A A A A A
A A A A A A A
孔の部分の境界（Ｂ）は 時計回りに追跡される
直線の検出
•
直線の検出–
ノイズや対象物の重なりなどの影響で散在した点（画素）から，本来抽出したい直線を導き出す
点線の直線式を 導き出したい
•
ハフ（Ｈｏｕｇｈ）変換を用いた直線の検出–
ある１点（x 1
，y 1
）が与えられたとき，これを通る直線 は，傾きa
と切片b
のパラメータを用いてy = ax + b
と表される–
原点から直線に下ろした 垂線の長さρ
と，垂線がx
軸となす角度θ
のパラメータ を用いると，直線式はとも表すことができる
直線の検出
cos sin
x y
ρ = θ + θ
•
ハフ（Hough
）変換を用いた直線の検出–
点（x 1
，y 1
）を通るすべての直線をパラメータ（θ
，ρ
）で 表したとき，θ
の変化に対するρ
の変化をグラフ化する と下図のようになる直線の検出
ρ
2ρ
1ρ
3（
x 1
，y 1
）x y
θ
1θ
2θ
3•
ハフ（Hough
）変換を用いた直線の検出–
与えられたすべての点についても，同様に曲線を 求めると，下図のようになる直線の検出
•
ハフ（Hough
）変換を用いた直線の検出–
曲線が最も多く交わる点（θ 1
，ρ 1
）を見つければ１ 本の直線を検出することができる直線の検出
θ
1ρ
11 x cos 1 y sin 1
ρ = θ + θ
1 1
1 1
cos
sin sin
y θ x ρ
θ θ
= − +
•
ハフ変換の利点–
同時に複数の直線を検出することができる–
ノイズを含む２値画像からも直線を検出できる•
ハフ変換の欠点–
計算時間がかかる–
短い線分を多数含む図形には不向き直線の検出
