複雑形状を有する平面図形や空間図形に対する
形状認識への複素関数論の応用
東京理科大学理工学部情報科学科 明石重男 1 研究の経緯 『めがねや3日月のようなくぼみのある図形』に代表される複雑な2次元平 面図形、 さらに『浮き輪やビール瓶やヒトデのような中空個所を有する図形』 に代表される複雑な3次元立体図形に対して、 計算機に形状を把握させること は、難解な問題であるにも関わらず、現代の画像認識の領域ではかなりの程度 まで実現されている。 具体的に述べるならば、 既存の画像認識システムは、円 柱や球や多面体などの凸面を有する立体図形、 もしくは (凹面と呼ばれるくぼ んだ部分を実現するために) これらを張り合わせることによって構成される立 体図形における形状認識は成功している。 しかし–般に、単純形状の図形を組 み合わせて表現できない立体の認識や、 仮に計算機が認識できた図形の中にお いて、新たなる観測点の位置を認識すること、即ち、観測点に存在するか内部 に存在するかを把握することは、 さらに困難な作業として残された問題である。 本原稿では、「くぼみやへこみなどの凹凸形状を有する画像」や「空洞や中空 個所を有する画像」などの「複雑形状を有する図形に対して、 計算機に形状の 定量的類似性を判断させること」 を「計算機に画像認識をさせること」 と呼ぶ ことにします。さらに「複雑形状を有する図形の内部と外部を識別させること、 もしくは相異なる 2 個の観測点を結ぶ線分が、与えられた図形と交差する回数 を求めること」 を「計算機に平面把握もしくは空間把握をさせること」 と呼ぶ ことにする。 そして非線形解析と複素関数論を応用した画像認識と空間把握の 方法を解説する。 本稿に関連した簡単な古典的問題として、「立体の陰線消去問題」 がある。 こ れは与えられた多面体と観測地点を空間に配置した場合に、観測者から見える 線分と見えない線分を餓擁する問題である。 これらの研究結果は、最近のコン ピューターグラフィクスの発達に伴う成果である 「仮想現実」 に応用されて いる。2 画像認識および空間把握の方法 以下では、平面図形を対象とした解説を行う。 与えられた図形に対する形状 認識のためのデータを構成する作業は以下の通りである。 ‘ 力されたメッシ$=$
.
の分割幅を–辺に持つ正方形メッシュの方眼用紙を作 製する。 仂櫃箸覆訖涎舛髻上記方眼用紙の上に置く。具体的には、対象となる図形 の輪郭となる曲線を構成する点列を左回りに入力する。但し、空洞を表す内 部図形の輪郭となる曲線を構成する点列は右回りに入力するものとする。 Ｊ 眼紙を構成する各格子点が、設置された形状の内部に存在するか外部に存 在するかを判定する 「空間把握作業」 を行う。 なお、 2個の図形の類似性を把握する作業 ね燭┐蕕譴2個の図形にに対応する上記データからそれぞれの図形に対応 する内部格子点を選び出し、Hausdorff
距離を計算する。 註1. Aと $\mathrm{B}$ を2次元平面内(もしくは3次元空間内)の境界線を含む有界な集合とする。 今、 $\mathrm{x}$ A かつ $\mathrm{y}$ $\mathrm{B}$ としたとき、$\mathrm{d}(\mathrm{x}, \mathrm{B})=\min\{\mathrm{d}(\mathrm{x}, \mathrm{y});\mathrm{y} \mathrm{B}\}$, $\mathrm{d}\phi,$$\mathrm{A})=\min\{\mathrm{d}(\mathrm{x}, \mathrm{y});\mathrm{x} \mathrm{A}\}$,
6
(A. $\mathrm{B}$) $= \max\delta\{\mathrm{d}(\mathrm{x}, \mathrm{B});\mathrm{x} \mathrm{A}\}$, $\delta(\mathrm{B}, \mathrm{A})=\max\delta\{\mathrm{d}(\mathrm{y}, \mathrm{A});\mathrm{y} \mathrm{B}\}$,$\mathrm{H}(\mathrm{A}, \mathrm{B})=\max$
{
$\delta$ (A B), $\delta(\mathrm{B},$$\mathrm{A})$}
として定義される距離を、
Hausdorff
の距離という。 註2. $\mathrm{C}$を複素平面上の閉じた曲線 (もしくは折れ線) とする。 さらに点 $\mathrm{W}$ を、 閉曲線$\mathrm{C}$上に存在しない複素平面上の 1 点としたとき、 $\int \mathrm{C}1/(\mathrm{z}-\mathrm{w})$dz
の値は、Wが$\mathrm{C}$の外部に存在する場合に$0$ となり、Wが$\mathrm{C}$の内部に存在する場 合に2 $\pi \mathrm{i}$ となる。 この結果を Cauchy の積分定理という。3
ベクトル解析的形状把握と複素関数論的形状把握との比較前節の 能劼戮 「方眼紙を構成する格子点に対する内部外部所属判定」 を
複雑形状で実行するために、従来から用いられている 「外積計算」 による方法
一般的に、外積計算による判定法は、「くぼみや穴などを有する形状に対する 内部外部所属判定には不利」 であり 「複雑形状の図形では、 境界線から離れた 内部で判定が困難」 という特徴を有する。 -方、Cauchy の積分定理による判定 法では、「\langle ぼみや穴などを有する形状に対する内部外部所属判定には有利」 で あるが「複雑形状の図形では、境界線付近で判定が困難」 という特徴を有する。 以上の結果から、 両判定法を組み合わせた以下の方法を採用することがもっと も有効であると考えられる。具体的アルゴリズムは以下の通りである。 $[egg1]$ 与えられた方眼紙上の格子点を 1 個選ぶ。 \copyright 内部外部の所属判定を行う前に、格子点と境界線との距離を計算し「境 界線付近」 と判定された場合は 愎覆漾「境界線から離れている」 と 判定された場合は、 い愎覆燹 $[egg3]$ 境界線付近と判定された格子点に対して、 外積計算を行い、 内部外部 の所属判定を行う。 終了後 イ愎覆燹 $[egg4]$ 境界線から離れていると判定された格子点に対して、Cauchy の経路積 分を計算し、 内部外部の所属判定を行う。 終了後 イ愎覆燹 $[egg5]$ 未調査の格子点があれば、 ，慳瓩襦 全ての格子点の調査が終了した 場合には作業終了。
誤判定を引き起 境界線から離れて内部に存 境界線付近に存在する格子点 こす可能性の高 在する格子点 い格子点の存在 領域 上記の比較表に基づいて、両刃定法による格子点の内部外部所属判定の有効 領域を図示すると次のようになる。 ここでは、「入力された境界線外部は、緑色 系統の領域」 であるものとし、「入力された境界線外部は、 青色系統の領域」で あるものとする。 また、境界線から離れるほど緑色もしくは青色の色彩が濃く なるものと仮定する。 なお下の図において、境界線が円周形状であることには 意味がないものとします。 上記イメージ図からも分かるように、境界線付近の領域では外積計算による方 法 (V法)が有効であることが分かり、境界線を離れた領域では積分定理による方 法 (C 法) が有効であることが分かる。このような理由で、方眼紙を構成する全て の格子点に関して、 まず「境界線との距離関係」 を判定した後、「境界線付近と 判断された格子点」 に対しては、
