ディジタル画像における曲線検出,座標変換及び修復 に関する研究

九州大学学術情報リポジトリ

Kyushu University Institutional Repository

ディジタル画像における曲線検出,座標変換及び修復 に関する研究

小野, 直樹

https://doi.org/10.11501/3081245

出版情報：Kyushu University, 1994, 博士（工学）, 論文博士 バージョン：

権利関係：

ディジタル画像における曲線検出、

座標変換及び修復に関する研究

、1/成6年1 2月

小野直樹

日次

第1章 序論

4

1.1 研究の目的とその背景 . ^{• • • • • • • • • • • • • • • • • • • • • • • • • 4:}

1.2 論文の概要と構成 . ^{• • • • • • • • • • • • • • • • • • • • • • • • • • • • 10}

第2章 垂直2等分線群を用いた円の検出 13

2.1 まえがき . ^{• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 1 :3}

2.2 中心の検出 ^{• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 16}

2.2.1 データ点を両端とする線分の垂直2等分線とアキュムレータ

配列

2.2.2 組み合わせの制限 . ^{• • • • • • • • • • • • • • • • • • • • • • • • 19}

2.2.3 アキュムレータ配列の構成に要する時間について ^{• • • • • • • 26}

2.2.4 ピーク検出による中心座標の検出 . ^{• • • • • • • • • • • • • • • 28}

2.:3 半径の検出 ^{• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 2}

2.4 不正確な円の検出 . ^{• • • • • • • • • • • • • • • • • • • • • • • • • • • • 29}

2.5 実験 . ^{• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 30}

2.5.1 勾配を用いた方法との比較 . ^{• • • • • • • • • • • • • • • • • • • :30}

2.5.2 複数の円の検出

.

^{• • • • • • • • • • • • • • • • • • • • • • • • • 32}

2.6 むすび

.

^{• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 32}

第3章 点集合の2次曲線当てはめ

34

3.1 まえがき

.

^{• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • :3Ll}

3.2 同心円弧を表す点集合の同心円による当てはめ . ^{• • • • • • • • • • • • 37}

:3.2.1 当てはめの良さの評価式 . ^{• • • • • • • • • • • • • • • • • • • • 37}

3.2.2 同心円弧の中心と半径の推定のための公式 . ^{• • • • • • • • • • 40}

3.3 点集合の楕円、 双曲線による当てはめ ^{• • • • • • • • • • • • • • • • • 4:3}

3.3.1 問題設定. ^{• • • • • • • • • • • • • • • • • • • • • • • • • • • • • 43} 3. 3.2 最小2乗法による2次曲線近似 . ^{• • • • • • • • • • • • • • • • 45}

3.3.3 反復法による2次曲線のパラメータの決定 . ^{• • • • • • • • • • 4}

3.³

.

⁴ 惰円の標準形を基にした反復法 . ^{• • • • • • • • • • • • • • • • .5:3}

:3.3.5 実験 . ^{• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 55}

:3.4 むすび • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 63

第4章 ディジタル極座標変換

:1.1 まえがき .

1.2 極座標系における標本化の方法

A斗A 44ム

Fhυ

nO FO PO

L1.2.1 半径万向の分割 .• • • • • • • • • • • • • • • • • • • • • • • • • 67

<:1:.2.2 回転方向の分割

• • • • • • • • • • • • • • • • • • • • • • • • • 6

4.3 直角座標画素と極座標画素との対応付け • • • • • • • • • • • • • • • • 73

L1.3.1 4.:3.2

Ll.4 実験

4.4.1 4.4.2

直角座標から極座標への変換における対応付け 極座標から直角座標への変換における対応付け

うJ FO FO

勺i

ワ』

ワt

変換・逆変換に伴う画素の不一致 •

変換・逆変換に伴う雑音 ⁸²

4.4.3 回転不変処理に関する実験 . • • • • • • • • • • • • • • • • • • • 86

4.4.4 半径方向の分割rlJ高に関する実験 . ^{• • • • •} • • • • • • • • • • • 89 4.5 むすび . • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 91

第5章 反復法による画像の修復 ⁹²

.5.1 まえカtき . • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •

92 5.2 離散システムにおける画像修復のための逆フィルタ .

_{• • • •} • • • • •

95

.5.3

逆フィルタの正則化と雑首 .

_{• • • • • • • •} • • • • • • • • • • • • • • • 97 5.3.1 雑音とパラメータγとの関係 • • • • • • • • • • • • • • • • • 98

5.4

逆フィルタの正則化による濃度の低下 • • • • • • • • • • • • • • • • • 1₀₂

5.4.1 正則化による濃度の変化 ._{• • • •} • • • • • • • • • • • • • • • • 104

，5.4.2 濃度低下に関する実験 . • • • • • • • • • • • • • • • • • • • • • 105 5.5 濃度低下の補正を含む正則化逆フィルタ • • • • • • • • • • • • • • • • 107 5.6 修復実験 • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 111

5.6.1 横ブレ画像のPSF .. . _{. .} . . . _. . ₁₁1 5.6.2 横ブレ画像の修復実験 . • • • • • • • • • • • • • • • • • • • • • 111 .5.7 むすび . • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 119

第6章 回転ブレ画像の修復 ¹²⁰

2

6.1 まえがき . • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 120 6.2 回転ブレのPSFの推定 _{• • • • • • • • • • • • • • • • • • • • • • • •} 121

6.2.1 回転ブレのPSF. . . .

.

. . .

121

6.2.2 回転ブレのPSFを推定するための前処理 • • • • • • • • • • • 122 6.2.3 回転ブレによって生じた円弧の抽出 . _{• • • • • • • • • • • • • •} 123

6.2.4 中心座標の検出 • • • • • • • • • • • • • • • • • • • • • • • • • 124 6.2.5 ブレの角度の推定 . • • • • • • • • • • • • • • • • • • • • • • • • 125 6.3 回転ブレ画像の極座標変換 . • • • • • • • • • • • • • • • • • • • • • • • 126 6.3.1 ブレの中心を原点とするディジタル極座標変換 • • • • • • • • 126 6.3.2 ディジタル極座標におけるPSFの表現 . _{• • • • • • • • • • • •} 127 6.4 回転ブレ画像の修復アルゴリズム . • • • • • • • • • • • • • • • • • • • 129 6.5 回転ブレ画像の修復実験 • • • • • • • • • • • • • • • • • • • • • • • • 131 6.5.1 PSFの推定実験. • • • • • • • • • • • • • • • • • • • • • • • • • 1:31 6.5.2 極座標変換に伴う雑音に関する実験 . • • • • • • • • • • • • • • 140 6.5.3 画像の修復実験 . • • • • • • • • • • • • • • • • • • • • • • • • • lL15

6.6 むすび .

. 15:3

第7章 結論

154

謝辞

156

参考文献

157

第1章 序論

1.1 研究の目的とその背景

近年、 計算機を用いた画像処理に関する研究が盛んに行われている。 これは、 計 算機の進歩によって比較的容易に大量のデータを高速に処理できる環境が整ってき たためだけではなく、 画像を処理し解析するという要請が増えていることを表して いる。 画像処理は、 大きく三つの分野に分けることができる。 第1の分野は、 与え られた画像を劣化させている要因を取り除く画質改善や歪み補正に関する処理であ る[lJ。 この分野の処理は、 人工衛星から送られてくるいわゆるリモートセンシング 画像の処理を中心に発達したものであり、 主に濃度階調の修復や幾何学歪みの補正 などの変換処理からなる。 第2の分野は画像変換処理であり、 この種の処理として は画像の平行移動、 射影変換等がある。 第3の分野は、 画像の構造を分析して特徴 を抽出する処理である川。 この分野の処理は、 画像解析、 画像認識・理解と呼ばれ、

人工知能とも深く関わりながら種々の分野での応用が研究されている。 例えば、 3 次元情報の自動解析は、 コンビュータビジョンと呼ばれ、 画像解析、 画像認識に関 する種々の処理が必要となる典型的な例である。 コンビュータビジョンにおいては、

1に一枚の静止画像だけではなく、 動画像として処理することが必要となることも 多い。 しかしながら、 コンビュータビジョンの基本となるのは、 2次元の静止画像 に関する処理である。

画像は、 通常2次元の直角座標連続空間上に広がる2変数の実数関数である。 モ ノクロ画像の場合には、 この関数は画像の各点における濃度 〈輝度〉 値を表してい る。 一方、 カラー画像については、 色を例えば赤、 緑\ 青の光の3原色に分解すれ

4

ば、 それぞれの色の濃度値を表す3個の実数関数によって表現できる。

計算機を用いて画像を処理する際には、 直交する2つの方向に等間隔に画像を標 本化し、 更にそれぞれの標本点における濃度値を量子化したディジタル画像として 取り扱う[2][3]0 通常は、標本化は2つの方向とも等しい間隔で行われ、ディジタル 画像の最小単位は正方形画素である。 また、 濃度値が2イ直に量子化された画像は2 値画像と呼ばれ、 その値は0とlとしてよいので、 濃度値がlの画素の座標だけ で画像を表現できる。 例えば、 曲線を計算機によって処理する際には、 曲線を2値 画像として表現し曲線の通る座標点の集合として曲線を表す。 すなわち、 曲線を離 散点の座標の集合として記述する [4]0

|曲線を単に点の集合としてではなく、 適当な関数もしくは幾何学図形によって表 せば、曲線を認識する上で-も、データを保存する上でも都合がよい[5]0 この為、種々 の場面において曲線の関数近似が行われてきた [6][7]。 自然または、 人工物体の画像 中に最も頻繁に現れる幾何学図形は、 直線、 円及び楕円である。 従って、 計算機に よってこれらの図形に関する処理を行う機会は多い。 例えば、 乗り物の誘導、 工業 部品の検査及び分類の自動化、 医用X線写真の自動診断、生物学、 金属学における 組織標本の顕微鏡画像の自動解析などの分野においては、 これらの図形に関する処 理が不可欠である。 また、 これらの効率的な検出は、 パターン処理・認識・理解な といの基礎をなす重要な技術の一つで、あり、 ここに挙げた分野だけでなく、 画像処理 を利用する種々の分野において必要となる[8][9]。 ここでは、種々の情報が混復する 凹像の中から円や楕円などのある特定の図形を抽出し、 更にそれらの位置、 大きさ、

傾きといったノモラメータを推定するという一連の処理を検出と呼び、 抽出のみの処 理、 パラメータ推定のみの処理とは区別する。

計算機による種々の処理の中でも、 幾何学的な構造を有する情報を効率的に処理 するための手法を研究する分野は、 計算幾何学と呼ばれており、 画像に関する多く の処理と密接な関係がある[10][11]。計算幾何学の分野においても、 円を取り扱った 問題が例えば文献[12][13][14]に報告されている。 しかし、これらは、 与えられた点 集合を包含するできるだけ小さな円を求めてデータを分類する方法について論じた ものであり、画像中から円を検出する問題を扱ったものではない。 一般に、 計算幾 何学においては、 大規模なデータを処理するためのデータ構造や高速計算法に論点 がおかれている。

円状の物体は、硬貨、 ボタン、タイヤ、 薬など日常生活でも自にすることは多い。

また、機械部品や手書きの図面においては円状特徴が、画像を処理する仁でキーと なる。 すなわち、 円の検出は種々の応用面で重要である。 円以外に種々の情報を今 む画像中から円を精成している点のみを検出する方法は、かなり以前から研究され ており、その代表的なものに Hough変換がある。 Hough変換は、画像中の直線を パラメータ空間を用いて抽出する方法としてHough[L5] によって考案された。 そし て、計算機を用いた具体的な直線の抽出方法が、Rosenfelcl[16]によって示され、こ れは後に円や楕円さらに一般の図形検出のための方法として発展してきた。

Hough変換によってある特定の図形を検出する際には、与えられた画像が線画像 などの2値画像の場合を除き、先ず画像中のエッジを検出する必要がある。 つまり、

2値化されたエッジ画像の点座標データがHough変換の入力データとされる。 一般 にHough変換に要するメモリ量は、 図形を特徴付けるパラメータの数ηの指数関 数p/l(p>>1)に比例し、計算の手数(時間)はpn-l �こ比例する。 また、計算精度を ヒげるほどpは大きくなる[1 7][ 18]。 従って、Hough変換に関する研究の多くは、処 理に要するメモリと処埋時間とをいかに押さえるかが日標となっている[18][19][20]0 円は中心座標2個、半径l個からなる3個のパラメータを含むので、 上記のこと から円の検出のためには原理的には3次元配列を必要とし、パラメータを精度良く 推定するためのメモリ量が非常に大きい[21]。実際、N x JV画素からなる画像に今 まれている円のパラメータを1画素の精度で求めるためには、N3個の要素を蓄積 できる3次元配列が必要となる。 このため、N⁼ .512の画像に対しては、非常に大 きなメモリを持つ計算機が必要となる。

そこで、先ず2次元配列を用いて円の中心座標を求めることによって画像中の 全ての円を抽出し、次にそれぞれの中心座標について半径を求めるという方法が KÜ1111児[22]，

Illingworth[23] ，大和[24]らによって提案されている。しかし、Kinllne[22]，

Illingworth[23] の方法においては、 円の中心を抽出するためにエッジ画像の座標点 データ以外に画像の濃度勾配が用いられており、円を構成しているエッジ画素の近 傍に少しでも雑音があると、その抽出精度がかなり悪くなることがRisse[25] によっ て報告されている。 更に、線画などのエッジ点だけが与えられている画像からは円 を検出することができない。 また、大和[24]らの方法では、 欠損の大きい円の検出 が難しい。 この他にもいくつかの円の検出方法[26]が提案されているが、 円の検出 方法はまだ十分には確立されていない。

方、l個の円または円弧に近い点集合が与えられたとき、これらによく当ては

6

まる円のパラメータ決定方法は、 円検出の一つの行程としてだけではなし機械部 品を解析し検査する場合などに必要となる。 一般に、 関数によって曲線を近似する ときには、 入力曲線データと近似関数(曲線〉との距離の2乗和によって近似の良 さを評価することが多い[27]。 従って、 点集合に良く当てはまる円のパラメータも、

各点から近似曲線への距離の2乗和を最小化するように決めれば良いと考えられる。

しかし、 与えられたそれぞれの点と円との距離の2乗和を最小化する円のパラメー タは、 解析的には|湯に求まらない。

そこで、La.ndau[28] は、 距離の2乗誤差を最小化する円のパラメータを反復法に よって求める方法を提案した。 しかし、 この方法では反復計算に要するH寺聞が大き い。 また、 距離の2乗誤差を変形した評価式を最小化する方法がThOlnas[29] らに よって提案されたが、 その評価式の持つ意味が十分には説明されていない。 一方、

Cha.uclhuri [30] によって提案された方法は、 評価式の意味は明確にされているが、 こ れは閉曲線にその適用が限られる。 点集合を円によって近似する方法は、 近似の評 価方法を距離の2乗誤差との関係をふまえながら研究してし1く必要がある。

円と同様に、 与えられた点集合に良く当てはまる楕円のパラメータを求める方法 も、 先に述べたようにコンビュータビジョンや顕微鏡画像の解析などで必要となる。

これらで扱う画像においては、 ある程度の歪みを伴った楕円を対象とすることが多 い。 さらに、 標本化誤差などのために、 入力データは一般にあるIIJffiで楕円弧状に分 布する点集合となる。 楕円は、 長軸の長さ、 短軸の長さ、 中心座標、 傾きからなる 5個の幾何学ノマラメータによって表現できる。 しかし、 これらのパラメータをその まま用いて点集合をよく近似する楕円を求めるためには、 三角関数を含む非線形方 程式を解く必要があり、 これは陽に解くことが難しい。

Chauclhuri[31] は、 モーメン卜によって曲線の楕円当てはめを行っているが、 こ れは円の場合と同じく閉曲線に限られている。 楕円は、5個のパラメータを持つ2 次関数によって記述できる。 そこで、 点集合によく当てはまる惰円の幾何学的ノミラ メータを直接求めるのではなく、 2次曲線として代数的に求める方法がしばしば用 いられている[32][33] [34] [35]。 しかし、 一般に2次曲線としては双曲線、 放物線も 布り得るので、 点集合が当てはめられる2次曲線が必ずしも楕円であるとは限らな い。 従って、 点集合を惰円に当てはめる場合には、 2次曲線を楕円に制限するため の条件を同時に与える必要がある。 ところが、 2次曲線が楕円となるための条件は 非線形であるため線形方程式の中に直接組み込むことができない。

そこで、 反復法によって、 与えられた点集合に良く当てはまる楕円のパラメータ を求める方法がNa.gaね[:36] らによって報告されている。 しかし、 この方法では、 処 理の途中で楕円として収束するか否かを判断しており、 収束しないと判断されたと きには処理を打ち切るため、 楕円のパラメータが求められない場合も有り得る。 こ のように、 与えられた点集合によく当てはまる楕円を必ず求めることのできる方法 は示されていない。

画像は、 通常直角座標系で与えられる。 ところが、 対象物画像の回転、 拡大、 紡 小に依存しない認識システムを構築する際には、 一般に画像の極座標表示が必要と なる[:37][:38]

[:39] [40]

[41] [42]。 また、 対象物の回転角を求める際[4:3] [4'-1]にも処理を円 滑に進めるために画像を極座標系で表すことがしばしば必要となる。 直角座標系で ーえられたディジタル画像を極座標系で表示する極座標変換は、 概念的には簡単で ある。 しかし、 ディジタル画像においては、 直角座標画素と極座標画素との聞にア ナログ画像におけるような単純な1対1の対応がつかないので注意を要する。

従来、直角座標系で与えられたディジタル画像を極座標変換するときには、図1.1に 不すように、極座標系において回転方向に均一な標本化がなされていた[45][46][47]0

図1.1 :半径方向

、

回転方向ともに均一な極座標の標本化

しかし、 このような標本化では、 極座標系の中心座標から離れた直角座標画素の情 報を極座標変換後も保存しようとすると、 極座標の中心部分の標本化密度が非常に 大きくなってしまう。 つまり、 極座標系において均一な標本化を行うと、 画像の中 心部分の冗長性が高くなり、 逆に周辺部分の情報が失われ易い。 これらは、 座標変 換を伴う画像処理において画像の劣化や処理時間の増加につながる。 従って、 直角 座標における情報を漉とさず、 かつ冗長性の少ないディジタル画像の極座標変換及 び逆変換法を用意しておく必要がある。

はじめに述べたように、 画像の解析や認識のためばかりでなく、 劣化した画像の 画質を改善する目的でも画像処理が行われる。 この種の処理のーっとして画像修復 がある。 これは、 カメラの焦点ズレやブレなどによって劣化した画像を、 ボケのない はっきりとした画像に復元する処理である。 画像修復は、 古くから研究されており、

幽像の修復のための種々の方法についての解説書も多数出版されている [48][49][50]。

また、 画像修復を信号処理における逆問題として解説した文献[51 ][，52][53]もあり、

引庄でも活発に研究されている分野である。

画像の劣化系が線形であれば、劣化系の点拡がり関数(Point Spreacl Functjon:PSF) による逆畳み込みによって画像を修復できる [54]。 すなわち、 逆フィルタによる線 形演算によって画像を修復できる。 もちろん、 画像とPSFをフーリエ変換して、 周 波数領域で画像を修復することも可能であるが、 一般には劣化のPSFが位置によら ず不変で‘あるとは限らないので、 必ずしも周波数空間で処理できるとは限らない。

また、 雑音を含む劣化画像に対しては、 劣化系に対する逆フィルタよって処理する と、 得られる画像は雑音の強調された画質の悪いものとなる。 これは、 特異点など の逆フィルタの悪条件性(Ill-condition)によって引き起こされる。 従って、 画像修 復のためには逆フィルタの悪条件性に対処するために逆フィルタを正則化する必要 がある[55][56]0

雑音の付加された劣化画像を修復するための方法としてウィーナフィルタ[57][58]

が良く知られている。 また、 雑音を考慮した画像修復の方法は、 文献[48][49] [50]な どにいくつもあげられており、 画像復元の忠実さの評価方法と雑音抑制庁法とを提 案している。 しかしながら、 実際に修復の対象となる劣化画像は、 劣化の程度や雑 立がそれぞれ異なるため、 あらゆる画像に対して最適に修復できる方法は確立され ておらず、 画像修復には多くの問題が残っている。

画像修復の実際のモデ、ルとして、 一次元の劣化系について議論したものは多い。

特に横ブレや斜めのブレに対する修復方法については、 文献 [⁵⁹] [⁶⁰] [⁶け ^{に理論だけ} でなく詳しい手順も述べられている。 回転ブレ画像についても、 ブレの中心を原点 とする極座標系で劣化画像を表すことによって、 横ブレ画像と同様に一次元劣化画 像として修復できる。

実際、 回転ブレ画像を修復するためには、 先ず劣化画像のPSFとして、 ブレの中 心座標とその角度を求める必要がある。 次に、 ディジタル極座標変換が必要となる。

このとき、 用いる極座標変換によって処理に要するメモリや時聞が大きく左右され るため、 画像情報を落とさないことはもちろん、 できるだけ冗長性を押さえた極以l人 傑変換を用いるべきである。 さらに、 画像の量子化誤差や、 直角座標から極座標へ の変換の際の誤差は、 画像修復の過程において雑音として影響するので、 来日:音を考 慮、した修復方法を用いる必要がある。 このように、 回転ブレ画像の修復処理は、 主 にいくつかの画像処理を組み合わせるだけでなく、 各々の過程における処理目的と 次に続く処理とを十分考慮、して、 全体のシステムとして構成する必要がある。

1.2 論文の概要と構成

本論文は、 1.1で述べた種々の問題点に対し、 これに対処する方法の研究をまと めたものである。

以下に論文の構成と概要を示す。

第1章は、 序論であり本論文で扱っている問題の概要と論文の構成について述べ ている。

第2章では、 種々の図形ノミターンが含まれる画像中から複数の円を検出する方法 を提案している。 円の検出には、 先に述べたようにHough変換が有効であり、 本論 文で提案している方法も2次元配列を用いて円を検出するHough変換の一種であ る。 本論文で提案している方法は、 同一円上の2点を結んでできる線分の垂直2等 分線がその円の中心座標を通るという事実を利用している。 この方法は、 従来しば しば使われてきた画像の濃度勾配を用いたものに比べて、 雑音や量子化誤差による 影響を受けにくい。 また、 垂直2等分線を構成する際に組み合わせる点を制限する ことなどによって、 処理に要する時間の軽減も計っている。 この方法による円の検

出結果と従来の方法による結果との比較の実験も示す。

第3章では、 与えられた点集合に良く当てはまる円及び楕円のパラメータを求め

10

る方法について研究している。 先ず、 共通の中心を持つが、 半径の異なる円弧状の クラスターがある場合、 すなわち同心円弧を表す点の集合が与えられている場合に おける円のパラメータの推定方法を検討している。 そして、 与えられた円弧の共通 の中心の位置とそれぞれの半径を推定するための公式を与えている。 この万法では、

近似の評価の基準として距離の2乗誤差を変形したものを用いており、 同心円弧に 対してこの評価式を用いると全体の評価式は、 距離の2乗誤差に各円弧の半筏の2 乗の重み付けをしたものの和となることを示した。 従って、 この方法によると大き な半径を持つ円弧が小さな半径を持つ円弧よりも、 データにより近く当てはまるよ うな同心円弧の中心座標が求められる。 なお、 この性質は、 後に述べるように回転

ブレ画像の修復の際のPSFの推定に都合がよい。

楕円については、 惰円を5個のパラメータを持つ2次関数として表し、 この式を 用いて近似の良さの評価式を構成した。 本論文では、 点集合に楕円を当てはめるた めの反復法を提案している。 この方法においては、 2次曲線が惰円となるための非 線形な制約条件を考慮し、 反復の過程で楕円とならない2次曲線ノミラメータが求ま ると、 2次曲線が楕円となるようにパラメータを強制的に修正している。 また同様 に、 点集合を双曲線に当てはめる場合についても、 非線形な制約条件を含む問題と して取り上げ、 惰円の場合と同じく反復法による解法を示している。 点集合を楕PJ、

双曲線に当てはめた実験の結果についても示している。

第4章では、 ディジタル画像の極座標変換の方法について検討し、 ディジタル画 像の極座標変換のための方法を提案している。 この方法は、 極座標系における標本 化の方法と直角座標画素と極座標画素との対応付け方法とから成る。 本論文で提案 する極座標系の標本化方法は、 極座標原点からの距離が大きいほど回転方向の分割 数も大きくして回転方向の標本化密度を上げるものである。 そして、 直角座標から 極座標への変換における直角座標画素と極座標画素との対応付け方法と、 逆変換に おける直角座標画素と極座標画素との対応付け方法とを示している。 ここで提案し ている方法は、 回転方向を半径によらずに一定の角度で標本化する従来の極座標変 換に比べて、 変換による情報の欠落がなく、 かっ冗長な情報が生じにくいものであ る。 本論文で提案している方法を用いたときの極座標変換に伴う誤差と従来の極座 標変換を用いたときのそれとを雑音として評価し、 提案している方法が優れている ことを示す。 また、 両方法を用いて回転した画像の認識実験を行い、 極座標系にお ける画素(標本点〉の数が閉じ場合には、 従来方法に比べて認識率が良いことも碓

かめる。

第5章では、 線形劣化系によってぼけた画像の修復方法について検討し、 特に雑 音が付加されたボケ画像を修復するための復元フィル夕、 すなわち正則化された逆 フィルタの構成方法とその正則化による画像の濃度低下について考察している。 そ して、 雑青を強く抑制しようとするほど画像濃度が低下することを明らかにした。

また、 そのような濃度低下を考慮した正則化された逆フィルタを提案し、 そのフィ ルタ処理を実行するための画像空間における反復法を提案している。 このフィルタ には画質を制御するためのパラメータが含まれており、 このパラメータを大きくす ると修復画像の雑音を押さえることができ、 逆に小さくすると画像の細かい部分が 明確になる。 すなわち、 このパラメータは雑音に応じて与えるものであり、 その与 え方の目安も示す。

第6章では、 5章までの応用として、 比較的大きな回転ブレによって劣化した画 像を修復するための具体的な方法を提案した。 このシステムは、 上に述べた円の検 出、 極座標変換、 ボケ画像修復の方法を組み合わせることによって実現されている。

まず、 ブレの中心を推定する際に本論文で提案している同心円弧の中心座標を求め るアルゴリズムが有効であることを示した。 回転ブレ画像は、 ブレの中心を原点と する極座標系で表すことによって、 回転方向の一次元ブレ画像として修復すること ができる。 ここでは、 その変換のために先に提案したディジタル極座標変換を用い ている。 この極座標変換を用いると、 変換後の極座標における冗長な情報の発生を 抑制できるので、 ブレの修復で余分なデータを処理する必要がなく効果的である。

この結果、 回転ブレ画像修復システム全体が、 処理に要するメモリが比較的小さい 効率的なものとなっている。

第7章では、 結論を述べ今後の課題について論ずる。

12

第2章

垂直2等分線群を用いた円の検出

2.1 まえカてき

序論で述べたように、 円状の物体は日常生活で自にすることは多く、 コンビュー タビジョンの処理対象となることは多い。 また、 機械部品の分類、 組織標本の顕微 鏡写真の解析においても円の検出が必要となる。 図2.1(a.)(b)に本章で扱う画像の 例を示す。 これらの画像中から一般には複数個の円または円弧を検出することがし ばしば必要となる。 しかしながら、 それらの画像中には円以外の様々な図形ノぞター ンが含まれており、 更に図2.1(a.)のように円が部分的に隠れていることも多い。 ま た、 カメラによって画像を取り込む際の歪みや、 標本化誤差、 量子化誤差が画像に 伴っていることを考慮しておく必要がある。 このような画像中から円を検出するた めに、 Hough変換がしばしば使われる。

以下、 Hough変換の概要を先ず述べる。

Hough変換によって、 ある特定の対象を検出する際には、 与えられた画像が線凹 像などの2値画像の場合を除き、 先ず画像中のエッジを検出する必要がある。 つま り、 図2.2(a.)(b)に示すようなエッジ画像を形成する点座標データti ⁼ (九Yi)，i二 i‘乞 ..，Mが、Iおugh変換の入力データとされる。

ここで"' 12個の要素からなるパラメータベクトルc=

(行、C2i.

・，_{Cn)によって規定} される図形(曲線)

P(t，C)

= 0 を検出する場合を考えよう。 ここでt=(x)�ゲ)は2次 苅画像空間における点の座標を表す。1個の点座標データtiに対して、 P(ti，c) = 0 である全てのcを計算すると、 これらはn次元パラメータ空間において1個の超曲 面を形成する。 他の全てのエッジ画素についても同様に超曲面を構成し、 それらの

(a) (b)

図2.1:円検出の対象画像の例

足む ^[

市hu

図2.2:エッジ画像

14

交点を求めることによって目的とする図形を検出する方法がHough変換であるい8]0 例えば、 直線を検出する場合には、 直線を直線から座標原点に降ろした垂線の長 さ pと垂線とI軸とのなす角度0を用いて

P

=.1・cos

() + !J sin ()

(2.1 )

によって表現する。 すなわち、 この場合はC ⁼ ( p、0) であり、 このベクトルによっ て張られる空間はρ-()空間と呼ばれる。 画像空間中の1個の点が与えられたとき 式(2.1

)

を満たすp-oの組を求めると、 図2.:3(b)に示されるl本の曲線となる。こ の対応付けは、 画像空間におけるl点を p-()空間へ射影する事に等しい。L本の 直線上に仔在する点集合を式(2.1 )に従ってp-o空間に全て射影すると、 図2.3に 示すようにそれらの曲線は p-()空間においてl点で交わり、 その交点座標(P，()) が直線を規定するパラメータを表している。 一般に直線以外の点も画像中には含ま れているが、 p-()空間曲線は、 画像空間に存在する直線のパラメータに対応する 点で密に交わる。 従って、 パラメータ空間において射影曲線の密度の高い点を求め ることによって直線を検出できる。

計算機によって図形P(t，c) ⁼ 0を検出するためには、 先ず超曲面の次元すなわ ち対象を特徴づけるパラメータの数11に等しい次元の配列A(Cj)を用意し、 初期 値をoとしておく。 なお、cjはcの各要素を適当な大きさで量チ化したものであ り、 配列A(Cj)はアキュムレータ配列と呼ばれる。1個のエッジ画素の座標tiに対 して、 P(ti1c) ⁼ 0である全てのcを計算し、 それらを量子化したCJに関わるア キュムレータ配列要素にlを加算する。 これを全ての点座標データに対して行うこ

p

亡二二=土〉

。 。

(a.)画像空院 (b)p -()空間(ノミラメータ空間)

図2.3:画像空聞から p-()空間への射

とによって得られる配列Aの中から最大もしくは局所最大を持つ配列要素C.lを抽 出することによって、図形P(

t.c)

⁼ 0を検出する。 このときのCjが、 図形の位 や大きさなどの特徴を規定していることは言うまでもない。 Hough変換に要するメ モリ量は、 そのほとんどが配列Aの大きさに依存するので、パラメータの数11の 指数関数l/� (p ::ì> 1)に比例する。 また、 計算の手数(時間)はpn-1 �こ比例し、 計算 精度をとげるほどpは大きくなる[17][18] 0

円は、 中心座標を表すノぞラメータ2個と半径を表すノマラメータ1個の計3個のパ ラメータで規定されるので、 Hougb変換によって円を検出するためには、 一般に3 次元アキュムレータ配列が必要で‘あり大きなメモリを要する[21]。 そこで、 まず2

次元アキュムレータ配列を用いて円の中心を検出し、次に半径を求めるという2段 階処理による円検出の方法が提案されている[22][23] [24]。 これは、 高々2次元のア キュムレータ配列を用いるだけであり実行に要するメモリが非常に小さい。

上記の2段階処理による円検出の際、"円の法線は、 常に円の中心を通過する"と いう性質を用いるものがある。 従来の円の法線を用いた円検出においては、 法線を 求めるために各データ点における濃度勾配が用いられている[22][23]0 すなわち、通 常Hough変換の入力データとするエッジの座標データ以外にエッジ検出前の濃淡画 像の情報も使い、 円の内側と外側との濃度差を用いて法線の方向を決定している。

通常、 勾配の計算には、 大きさ3 xれまたは5 x 5のSobel等の微分処理を含むJn 所フィルタが用いられる。 従って、 雑音や標本化誤差、 量子化誤差の影響を大きく 受け易い[2.5]。 特に、 直線の方向に関する誤差は、計算した画素の近傍においては 微少であっても、 その画素から離れるのに従って、 大きな誤差となるので問題であ る。 また、 この方法では、2値の線画像などのように円周上の点座標のみが与えら れた画像からは円を検出することはできない。

本論文では、2個のデータ点を結ぶ線分の垂直2等分線を用いることによって、 円 の中心を検出する方法を提案する。 この方法と勾配を用いた方法とを比較し、 実験 からも本方法の有効性を示している。

2.2 中 心

^の

検 出

[63][64][65 ][66]

通常、画像は濃淡画像として与えられる。 そこで、 先ず画像中の輪郭を強調し、

エッジ点を検出する。 そして、検出されたこれらエッジ点の座標を入力データとす

16

る。 入力データの中には、 一般には複数個の円または円弧の他、 直線、 矩形などの 種々の図形及び雑音が含まれる。

このような画像データの中から円を検出する方法として、 ここでは図2.

Llに示す

ように、..同一円上の2点を結んでできる線分の垂直2等分線が、 円の中心座標を通 るーとしづ事実を用いる方法を提案する。 円が存在していれば\全ての入力データか ら選んだ2点の組み合わせによって垂直2等分線を構成すると、 |同司一円周上の2}

によつてでで .きる垂直2等分線が円の中心座襟を通るのでで ‘中J心 心座標における直線の寵密 ^f j皮変が高くなるO ここでは、 このような性質を用いて円を検出する。

図2.4:円上の2点の垂直2等分線と中心

2.2.1

データ点を両端とする線分の垂直2等分線とアキュムレータ

配列

入力画像は、 一般性を失うことなく一辺の長さがlの正方形画素N _x JV個から なるものとし、 この画像の中にM個のデータ点

Cri，Vi) (i=l，...，lVI) (2.2)

が与えられているとする。 更に、 別途2次元アキュムレータ配列を用意する。 その 大きさは、 画像と同じくJV _x

JVであり、 処理画像の画素と配列要素とを1対1に対

応づけておく。 こうすることによって、 入力画像の最小単位である画素の精度で円 を検出できる。

式(2.2)の中から選んだ2点(x，. :lJi)ゥ(.r.i， Y.i)を両端とする線分の垂直2等分線は、

。-弓吋(:lJ.i ^-Yi)

^=一

(

^1ー

ヰ斗 ⁽

^，l'.i

^{- J_'i) (2.:3)}

によって表される。 式(2.:3)によって表された垂直2等分線が通過する点に対応する 配列要素に1だけ加算する。 このとき、 直線が通過する画素に対応する全ての配列 要素に加算する方法や、 各画素に係る直線の長さに応じた重み付けをして加算する ノゴ法も考えられる。 しかし、 本論文では、 直線が通過する画素に対応する配列要素 の加算を処理時間の軽減のために以下のように行う。

まず、 直線の傾きが

| 先 I ^�

^{1のときには、}

ユ= 1.

2，

• • • ，1V

に対応するyの座標を

l

J -2 1 」(じ+

，1'.1

) ^(1'・j - l'd + (Y1' + y_i) (:I).i一Yi)

Y

= ー---1 十 (2.4)

'グ/ーグ1 2(め- :lJi)

によって計算し、 更に求められたyを四捨五入した結果によってlを加算すべき配 列を決める。 図2.5(a，)にこのときの直線と配列との対応関係を示す。 灰色で表した

配列〈画素)が加算する配列である。

方、

防1

>1のときには、

y = 1， 2，・" ， JV

に対応する;じの座標を

Y.i一Yi ^I

(Y

^{i +}

Y.i) (Y.i

^-

^{Y i)}

^{+ (れ + 円)}

⁽

^1:.1一向

⁾

= r1-ZI

Y+ 2( ;

り - ，(;・i) ..1 1 \ . 1 "/ (2.5)

によって計算し、 更に求められたz を四捨五入した結果によってlを加算すべき配 列を決める。 図2.5(b)にこのときの直線と配列との関係を示す。

以上の操作をあらゆる2点の組み合わせに対して行って、 アキュムレータ配列を 完成させる。 つまり、 アキュムレータ配列の各要素は、 通過した垂直2等分線の数 と等しい。

k

向付^回F

」♂..

白戸�/

v 1000""""

日�

�

l'

(

a.

) 〆tlE‘、 thu 、、EE，，J

図2.5:垂直2等分線と加算する配列との関係

2.2.2 組み合わせの制限

2.2.1項で述べたように、 M個の入力データのあらゆる点対聞の垂直2等分線を 描くとその数は

c =

1\1(N! - ₁₎ - 2

となり多すぎて実用とならないことが多い。 また、 実用上からも、 あらゆる組み合 わせを取る必要はないことが想像される。 そこで、 2点の対の取り方に制限を加え、

組み合わせの数を大l隔に減少させる。

先ず、 比較のために組み合わせを制限しない場合について示す。

2.2. 1項の方法に従って配列要素への加算をすると、 i本の垂直2等分線に対して ほとんどの場合N個の配列要素にlが加算され、 全ての配列要素の和はGNとな る。 従って、 各配列要素の平均値は

L" = G1V

_ 111/(M -1)

α 一 万2 _2N

である。

ここで、 m個の点からなるl個の円があるときこの円に関しては、

Cm ^171，

(

17' 1，

- 1)

rn

2

(2.6)

(2.7)

(2.8)

の垂直2等分線を描くことができ、 それらは円の中心座標において交わる。 一方、

全ての2点の対から、円周上の2点の対を除いた対の数は、

('7" =

(' - Cm (2.9)

であり、これらの対によってできる垂直2等分線は、一般に1点で交わることはな い。 例えば、l直線上に分布する点集合に関しては、配列要素の値が直線と垂直な方 [nJには一定となるため、 円周上の点による配列のように1点でピークを持つことは ない。 ここでは、 簡単のために円以外の点は一様に分布しているものと考える。 こ れらの点によってできる垂直2等分線による加算は、全ての配列要素に対してほぼ 様になされると考えられる。 すなわち、 円の中心座標に対応する配列要素以外の 各配列要素は、ほぼ

の値を有し、これにCmを加えた

LUI十「川二M(A1-1)十川777

^-1)(JV

-1)

2JV

(2.10)

(2.11)

が中心座標に対応する配列要素の値となる。 なお、J1!J > > 77ìのとき式(2.11)の値 はLα にCmを加えたものにほぼ等しい。

組み合わせる2画素聞の距離が小さすぎると、 標本化誤差によって、求められる 法線の方向が著しく限定されてしまう。 そこで、 組み合わせるデータは、 それらの 間の距離がある値d1よりも大きいものに制限する。 また、法線の数が少ないほど、

すなわちデータの組み合わせの数が小さいほど、 アキュムレータ配列を構成するの に要する時間は短くて済むので、組み合わせる2点聞の距離の最大値もの以下に 制限する。 なお、直径がめよりも小さい円は、この制限によって抽出できなくなる ため、d1としては抽出したい最小の円の直径より小さく与えておく必要がある。

このように制限したときに構成される円の垂直2等分線の数を調べよう。 半径γ の円が画像中にあるとき、この円に関して垂直2等分線を考える。 なお、ここでは 簡単のために円周に欠損や誤差がないものとする。

まず、2r・>d2の場合について考える。

円周上のある点POからの距離がd]以上かつの以下の円周上の点(画素〉の数 は、 図2.6に示すように、点POからの直線距離がd1である円周上の点P1と 点PO

20

からの直線距離がのである点ぬとを結ぶ円弧の長さんを2倍したものにほぼ等 しいと考えられる。 一方、 円周全体における点の数は、 円周の長さ27r7にほぼ等し いとみなせる。 従って、 この円に関して構成される垂直2等分線の数は、

fハつム一一

つム一

/ l k

一

2

介一円，L一一一

f (2.12)

となる。 なお、厳密には円を構成する画素の数は、 連続系において計算された値より も若干小さくなる。 特に、 半径が小さい円の場合には円周の長さと構成画素数との 誤差が大きくなるが、最も誤差が大きい場合でも円を構成する画素の数は、 式(2.12) の1//2倍であり、 半径が10程度の時には約0.88倍程度である。

円弧の長さ1cは、 長さのの弦に対応する円弧の長さんから、 長さd1の弦に対 応する円弧の長さんを差しヲ|し1たものに等しい。 すなわち、

lc二1'2 - 11

(2.13)

である。 一方、 弦の長さがdのとき、 その弦に対応する円弧の長さlは

l=bsin-1(t) _(2.14)

によって求めることができる。 従って、 点Plと点lhとを結ぶ円弧の長さんは、

日?(sin-1(討-s川ま)} _(2.15)

PO

川12.6:円周上の2点の組み合わせの数の推定

によって計算できる。

以仁のことから、 組み合わせる点の聞の距離をd]以上d2以下に制限したときに

は、 ある一つの円に対して構成される垂直2等分線の数に1を次の式によって求め ることができる。

、llkflj、、、‘‘，BEEt'''JJ d 一2

/fill--\

1i ''i 1i 臼 う d一 ， -f 14 一 \I1111ノ pδ

fIli--1\

-­ tEA ペノ旬 〆til-f、llt、 hh 'EA 一一 418ム π

、し 'EA

/t (2.16)

次に、 円の直径がのより小さい場合を考えよう。 そのような円においては、 組 み合わされる2点問の距離の最大値が 21、になるので、2点の組み合わせの数は式 (2.J6)ののをあに置き換えて、

Cc戸川{

1 - sin-1

(刊 _(2.17)

によって求められる。

上にも述べたように円周上の2点の組み合わせの数は、 正確には標本化による誤 差のために式(2.16)(2.L 7)による計算値よりも若干小さくなる。 ここでは、 さらに

円周が比較的粗な点集合によって構成されているものを考えよう。 すなわち、 半径 7・の円周上のデータ点の数17Lが、27r1よりかなり小さい場合である。 但し、 計算の 簡単のために円周上に均一な間隔で点が存在するものとする。

半径7・の円周上にm個の点が等間隔で並んでいるとき、 長さ/、 の円弧の上に並 ぶ点の数を1T1{とすると、 これは

J二 五戸 (2.18)

によって求めることができる。 従って、 この円における2点の組み合わせの数CcD は、 式(2.16)を用いて、

二千{

si

ぺ 引

- sin-1

削 ) _(2.19)

によって求めることができる。 もちろん、CcDは円の中心座標に対応する配列要素 の値に等しい。

22