JPH08138048A - ３次元図形認識方法 - Google Patents

Abstract

(57)【要約】 【目的】 ２次元上に描かれた３次元図形を認識する際
に拘束条件を補うことによって、一般的な立体図を容易
に３次元図形として認識できる３次元図形認識方法を提
供する。 【構成】 ２次元で表された図形データを３次元図形と
して認識する３次元図形認識方法であって、入力された
２次元の図形データの辺と頂点とを細線化により求め
（Ｓ２０１）、３次元図形としての拘束条件を逐次入力
し（Ｓ２００）、入力された拘束条件により前記図形デ
ータを３次元図形として認識する（Ｓ２０２）ことを特
徴とする。前記拘束条件は、空間座標系と図形全体の基
本拘束条件（Ｓ２０３）、更に捕捉的な部分的拘束条件
（Ｓ２０４）を含む。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は３次元図形認識方法、特
に２次元上に描かれた情報（例えば、紙に書かれた立体
図）より３次元の物体を認識する３次元図形認識方法に
関するものである。

【０００２】

【従来の技術】一般に３次元の物体をそれを表現する２
次元のデータ（特に立体図）から作り出すには、不確定
な情報を補う必要がある。例えば、図３のような立体図
がある場合、すべての辺は互いに並行または直角だとい
う情報と、頂点Ａが手前にあるという情報とを補わなけ
れば、この図が立体の一部を表わしていることは決定で
きない。

【０００３】現在、この様な比較的簡単な不確定情報を
ＡＩ等の技術を用いて補うことによって、２次元図形か
ら３次元図形を導出する３次元図形認識装置がある。

【０００４】

【発明が解決しようとする課題】しかし、多種多様な図
形に対応するためには広範囲な図形に対する知識が必要
であり、無限に多くの３次元図形に対処することは事実
上不可能である。例えば、図４のような立体図の場合、
人間はすぐにその３次元形状が思い浮かぶが、現在のＡ
Ｉ技術を用いてこのような情報処理をさせるには至難の
技である。

【０００５】また、図形によっては、人間が見ても（原
理的に）２次元情報から３次元情報を一意的に決定でき
ない場合が存在する。例えば、図３において、頂点Ａは
手前にあるのか奥にあるのかが分らなかったならば、こ
の図形が立方体の一部か重箱の隅かはわからない。本発
明は、前記従来の欠点を除去し、２次元上に描かれた３
次元図形を認識する際に拘束条件を補うことによって、
一般的な立体図を容易に３次元図形として認識できる３
次元図形認識方法を提供する。

【０００６】また、基本的だが図形全般の拘束条件では
指定し切れない条件を部分的に指定していくことによっ
て、更に複雑な立体図も認識できる３次元図形認識方法
を提供する。

【０００７】

【課題を解決するための手段】上述の課題を解決するた
めに、本発明の３次元図形認識方法は、２次元で表され
た図形データを３次元図形として認識する３次元図形認
識方法であって、入力された２次元の図形データの辺と
頂点とを細線化により求め、３次元図形としての拘束条
件を逐次入力し、入力された拘束条件により前記図形デ
ータを３次元図形として認識することを特徴とする。

【０００８】ここで、前記拘束条件は、空間座標系と図
形全体の基本拘束条件とを含む。また、前記図形全体の
基本拘束条件は、特定の頂点の凹凸を含む。また、前記
拘束条件は、更に捕捉的な部分的拘束条件を随時含む。
また、前記部分的拘束条件は、特定の面の法線ベクトル
を含む。

【０００９】

【実施例】以下、本発明の一実施例を添付図面を用いて
詳細に説明する。図１は本実施例に係る３次元図形認識
装置の構成を示すブロック図である。本実施例の３次元
図形認識装置は、座標入力装置１０１と、表示装置１０
２と、中央処理装置（ＣＰＵ）１０３と、メモリ１０４
とから構成される。

【００１０】座標入力装置１０１は、デジタイザとペン
とを有したオンライン型のものでも良いし、スキャナを
有したオフライン型のものでもよい。ともかく、座標入
力装置１０１は、入力される図形の座標データをＣＰＵ
１０３に渡す。表示装置１０２は、座標入力装置１０１
から入力された生の座標データやＣＰＵ１０３が認識し
た結果を表示する。ＣＰＵ１０３は、入力された図形の
認識を行ったり、すべての装置の制御を行ったりする。
メモリ１０４は、ＣＰＵ１０３が使用する認識プログラ
ム等を格納するＲＯＭや、入力された座標データ、認識
プログラムの使用する変数等を一時的に記録するＲＡＭ
からなる。

【００１１】次に本実施例の処理手順を図２から図１１
に基づき説明する。図２は本実施例の３次元図形認識装
置の動作を示すフローチャートである。 ＜細線化ステップＳ２０１＞先ずステップＳ２０１で
は、座標入力装置１０１によって入力された生の図形の
座標データが細線化される。細線化ステップＳ２０１
は、オフラインの場合とオンラインの場合とでは内容が
異なる。以下それぞれ説明する。

【００１２】（オフライン）入力された生の座標データ
は、何の構造をも持たないＸＹ座標からなる点列であ
る。そこで、この情報のどの部分が線でどの部分がその
端点なのかを、この細線化ステップＳ２０１で決定す
る。そのアルゴリズムとしては既知のものが使用され
る。例えば、黒点によって線が構成されている場合、上
下、左右のどちらか一方だけが白点で囲まれているよう
な点を優先的に間引いていく。このステップを何回か続
けると細い黒線が現れる。線が決定した後に、その端点
も既知の方法で決定される。

【００１３】（オンライン）通常、線情報（デジタイジ
ング区間）と端点情報（ペンダウン：始点＆ペンアッ
プ：終点）とは、ペンの入力情報として与えられる。よ
って、上記のような複雑な処理は必要ではない。しか
し、デジタイザの調子が悪いなどの理由で図形データの
中に余分な情報が入っている場合がある。こういった余
分なＸＹ座標は間引く。例えば、単位距離だけ離れた点
列のみを残す。

【００１４】また、異なるはずの２つの直線を続けて
（すなわち、ペンアップせずに）書いた場合、これを切
ることが必要になる。この方法も既知の技術を用いる。
例えば、最も簡単なのが、オンラインのデータをオフラ
インのデータとみなし、上記オフラインの場合の端点検
出アルゴリズムを使用する方法がある。こうして細線化
された座標データは、実際に書かれた線の太さや線同士
の続きに依存しないデータとなっている。

【００１５】以下この細線化された座標データのことを
図形データと呼ぶ。具体的には、入力された立体図が図
５（上図）に示した立方体の場合、頂点０から頂点６及
び辺０から辺８までが図形データとなる。尚、この頂点
と辺に付けた番号は適当に決定してよい。つまり、乱数
で振りあててもよいし、図５の上図のように左上から順
に振りあててもよい。

【００１６】また、コンピュータ上の表現としては、例
えば頂点０についていうと（図５の下図参照）、頂点の
座標記憶領域と、それに繋がる辺０，１，２へのポイン
タ（矢印）、そして、その辺の終末の頂点１，２，３へ
のポインタ（矢印）の組で表現する。このリスト構造を
すべての頂点（図５の場合、頂点０から頂点６まで）に
ついて保持する。なお、振りあてる頂点や辺の番号を入
れ換えても、このすべての頂点に関するリスト構造で表
現される図形データは本質的に一意である。

【００１７】＜拘束条件入力ステップＳ２００＞ステッ
プＳ２０２では、この細線化された図形データから、拘
束条件を手がかりとして３次元図形作成手段が認識結果
を導くが、この動きを説明するために、先ず、拘束条件
入力ステップＳ２００により、３次元図形認識に必要な
拘束条件の説明をする。図３を見てもわかるように、立
体図を見た時、その空間座標が設定されていればその理
解が速くなる。これは、一般にいえることで、立体図よ
り３次元図形を認識するには、空間座標の向きと単位長
さがと不可欠となる。

【００１８】＜基本拘束条件設定ステップＳ２０３＞こ
の動きを図６を用いて詳細に説明する。 （座標系の指定）空間座標系を決定するために、ＸＹＺ
座標それぞれの２次元投射方向（すなわち、立体図にお
ける空間座標方向）を指定する。更に、その空間座標単
位距離を指定する。この操作作業は、例えば以下のよう
に行う。

【００１９】まず、表示装置（ＣＲＴ）１０２に、図３
左下に書かれている空間座標系のＸＹＺ座標が表示され
ている。この座標の矢印の先端をマウス等のポインティ
ングデバイスでドラッグすることによって、入力された
立体図にマッチした座標系の指定を行う。なお、このと
き、上記座標方向と座標単位距離とが同時に決定され
る。この指定作業を省略した場合、デフォルトの空間座
標、すなわち初めに表示されたＸＹＺ座標がそのまま指
定される。

【００２０】（基準点の指定）次に、基準点となる点の
座標を指定する。これは例えば、図６で点Ａを原点
（０，０，０）と指定する。このとき注意することは、
基準点の座標を指定するためにはどの点を基準点にする
かがわからなければならず、必ず図形データの情報が必
要なことである。つまり、ストアされる基準点の空間座
標は頂点番号と座標とが組となっている。

【００２１】なお、この基準点の座標指定の手順が省略
されると、コンピュータが適当に基準点を指定する。例
えば、立体図の一番左上の点を原点（０，０，０）とす
る。 （フラグの設定）最後に、立体図に関する全般的知識と
してフラグが設定される。このフラグについて、図７を
用いて説明する。一般に、書かれた立体図が手前に凸か
奥に凹かを決定しないと、図形の形が決定しない。そこ
で、このような図形全体の構造に関する知識をフラグに
よって指定する。

【００２２】図７の（ａ）のように手前に凸とすると、
上記空間座標決定手順で指定された原点は手前になり、
図７の（ｂ）のように奥に凹とすると、上記空間座標決
定手順で指定された原点は奥になる。この原点と座標を
示す矢印の位置関係の指定で完全に立体図の向きが決定
し、立体図の表現する３次元図形が決定する。また、図
７の（ｃ），（ｄ）に示すように、空間座標系に平行な
直線しか含まないかどうかを示す等のフラグがあっても
よい。ともかく、空間座標系のみでは決定できない立体
図全体に関する知識をこのフラグで指定する。

【００２３】＜３次元図形作成ステップＳ２０２＞図２
のステップＳ２０２では、これまで説明してきた拘束条
件を用いて３次元図形作成手段が認識結果を導く。この
手順を図８のフローチャートを用いて説明する。３次元
認識過程は、基本的に図５の下図のリスト構造をたどり
ながらすべての頂点の座標と辺のベクトルとを決定して
いくことによって実行される。

【００２４】まず、ステップＳ３００で最初に基準点の
座標から出発し、ステップＳ３０１で、それに繋がる辺
の中で方向と距離（すなわち、ベクトル）の決定してい
ないものを探索する。もし未決定の辺が存在すれば、ス
テップＳ３０２で、その辺の方向と距離（ベクトル）を
決定する。この決定方向については以下に図９を用いて
詳述する。次に、ステップＳ３０３でその辺に繋がる点
（すなわち、先端の点）の座標を決定する。この決定方
法は単純に（始点の位置＋辺のベクトル＝先端の点の位
置）の公式を用いて決定する。

【００２５】ステップＳ３０４では矛盾が発生したか否
かをチェックし、すでに先端の点の位置が決定されてい
て、かつ、今回の新たに求めた先端の点の位置がその位
置と違う場合、矛盾が発生したと考え、ステップＳ３０
５へ進んでワーニングを表示して認識を終了する。この
矛盾が発生する状況は、普通の立体図を描いている限り
発生しないが、「エッシャーの無限段階」のような特殊
な場合に発生する。

【００２６】もし、矛盾が発生しない場合はステップＳ
３０６へ進み、辺が繋がった先端の点を新たに基準点と
して、その点に繋がる辺の探索手順（ステップＳ３０
１）へ戻ってループする。最初はスタートの基準点以外
はどの頂点も辺も決定されていないので、このループが
逐次実行されていく。しかし、ある程度認識過程が進む
と、基準点に繋がる辺のベクトルが全て決定されている
場合が発生する。この時は、図５下図のリスト構造を無
視して、ステップＳ３０１からステップＳ３０７へ進
み、未決定の頂点を探索する。そして、どこか未決定の
点が発見できれば、ステップＳ３０８からステップＳ３
０９へ進み、それを基準点としてステップＳ３０１に戻
り、また、図５下図のリストに構造に従って、それに繋
がる辺を探索するループに入る。

【００２７】もし、すべての点が決定していれば、ステ
ップＳ３０８からステップＳ３１０へ進み、認識を終了
する。この時、すべての辺のベクトルが決定していると
は限らないので、残りの辺のベクトルを決定する。 ＜ベクトルの決定方法＞次に、図９を用いて上記のベク
トルを決定する方法を説明する。

【００２８】図９の（ａ）の太い矢印が立体図中のある
辺だとする。図９の（ｂ）はこの立体図の空間座標系で
ある。この時、辺のベクトル（８，４）をＸＹＺ座標の
２次元ベクトル（４，０）（２，１）（０，４）とマッ
チングする。そして、方向の一致した座標のベクトルの
絶対値（すなわち、単位距離）と辺のベクトルの絶対値
との比を求めて、３次元座標（０，４，０）を算出す
る。

【００２９】この時、例えば図７の（ｃ）におけるよう
に“空間座標系に平行な直線しか含まない”というフラ
グがたっていた場合は、上記ＸＹＺ座標の２次元ベクト
ル（４，０）（２，１）（０，４）とのマッチング手順
を厳密に行わず、その傾き（すなわち、ｄｙ／ｄｘ）が
一番近いものを方向の一致した座標とする。また、上記
の逆、すなわち“空間座標系に平行でない直線も含む”
のフラグがたっていても、厳密に方向が一致することは
まれであるから、ある閾値を決定しておいて、その閾値
を越えない範囲では方向が一致するとしてもよい。もち
ろん、この場合、閾値は拘束条件として設定する。

【００３０】＜その他拘束条件設定ステップＳ２０４＞
では、図７の（ｄ）に示す”空間座標系に平行でない直
線も含む”場合、どうやってより正確に３次元図形を認
識するのかを説明する。立体図の中に空間座標系に平行
でない直線が存在する場合、立体図の表わす３次元図形
を認識することは非常に困難を極める。この場合、最悪
でも方向がわからないベクトルを図１０のように逐次決
定していく。

【００３１】この処理が図２のその他拘束条件設定ステ
ップＳ２０４であり、上記方法より少し進んだ方法とし
て、面の法線ベクトルを決定する方法がある。この手順
を図１１の図形と図１２のフローチャートを用いて説明
する。 （面の法線ベクトルの指定：ステップＳ４０１）図１１
のような図形において太線の方向を決定しようとした場
合を想定する。この時、まず太線で囲まれた面の内部か
らの矢印をマウスなどをドラッグすることによって書
く。次に、こうして得られた矢印の正確な傾きを数値を
入力したりして指定する。もちろん、矢印の始点だけを
指定した後で正確な傾きを数値入力しても、すでに入力
されている空間座標より逆算して表示することは可能で
ある。これで、この面の縁を囲む辺はこの法線ベクトル
に垂直なことが決定されたこととなる。

【００３２】（面を囲む辺の方向の決定：ステップＳ４
０２）すでに空間座標系の平面投射図（すなわち、ＸＹ
Ｚ座標の向きと長さ）は決定しているはずであるから、
立体図中の任意の辺の含まれる面は決定されている。但
し、その面内でどの方向を向いているかは決定していな
い。例えばずっと遠くから手前に向かってのびているベ
クトルかもしれない。この面上で設定された法線ベクト
ルに垂直で面上にある交線がその辺の方向であるわけで
ある。

【００３３】（面を囲む辺の長さの決定：ステップＳ４
０３）方向が決定されれば、あとは空間座標系より逆算
して距離を決定する。以下、このように不確定な情報
を、その他拘束条件設定ステップ２０４で補いながら、
３次元図形作成ステップＳ２０２で３次元図形を作成し
ていく。なお、一番手間がかかる方法であるが、その他
拘束条件設定ステップＳ２０４において不確定な頂点の
座標を直接指定していってもよい。

【００３４】尚、本発明は、複数の機器から構成される
システムに適用しても１つの機器から成る装置に適用し
ても良い。また、本発明は、システム或は装置にプログ
ラムを供給することによって達成される場合にも適用で
きることはいうまでもない。

【００３５】

【発明の効果】以上説明してきたように、本発明によれ
ば、２次元上に描かれた３次元図形を認識する際に常識
的に用いる種々の拘束条件（例えば、空間座標系の立体
図中における形状や、図形が手前に凸といった情報）を
補うことによって、一般的な立体図を容易に認識するこ
とができるようになる。

【００３６】また、空間座標系の立体図中における形状
や図形が手前に凸といった、基本的だが、図形全般の拘
束条件では指定し切れない条件は、部分的に指定してい
くことによって、更に複雑な立体図も同じ要領で認識で
きるようになる。

【図面の簡単な説明】

【図１】本発明の３次元図形認識方法が適用される情報
処理装置の構成を示すブロック図である。

【図２】本実施例の３次元図形認識方法の特徴をよく表
わすフローチャートである。

【図３】立方体を表わす立体図の例を示す図である。

【図４】既存の３次元図形認識方法では認識しづらい図
の例を示す図である。

【図５】細線化された後の図形データを示す図である。

【図６】基本拘束条件設定ステップの内容を示す図であ
る。

【図７】基本拘束条件設定ステップで指定されるフラグ
の例を示す図である。

【図８】３次元図形作成ステップの内容を示すフローチ
ャートである。

【図９】辺の方向を決定するプロセスを説明した図であ
る。

【図１０】その他拘束条件設定ステップの内容例を示し
た図である。

【図１１】その他拘束条件設定ステップの内容例を示す
ための図である。

【図１２】その他拘束条件設定ステップの処理を説明す
るためのフローチャートである。

【符号の説明】

１０１ 座標入力手段 １０２ 表示装置 １０３ 中央処理装置（ＣＰＵ） １０４ メモリ

フロントページの続き (51)Int.Cl.⁶ 識別記号 庁内整理番号 ＦＩ 技術表示箇所 Ｇ０６Ｆ 17/50 9191−5Ｈ Ｇ０６Ｆ 15/60 ６２４ Ａ (72)発明者 阪口 克彦 東京都大田区下丸子３丁目30番２号 キヤ ノン株式会社内

Claims (5)

【特許請求の範囲】
1. 【請求項１】 ２次元で表された図形データを３次元図
   形として認識する３次元図形認識方法であって、 入力された２次元の図形データの辺と頂点とを細線化に
   より求め、 ３次元図形としての拘束条件を逐次入力し、 入力された拘束条件により前記図形データを３次元図形
   として認識することを特徴とする３次元図形認識方法。
2. 【請求項２】 前記拘束条件は、空間座標系と図形全体
   の基本拘束条件とを含むことを特徴とする請求項１記載
   の３次元図形認識方法。
3. 【請求項３】 前記図形全体の基本拘束条件は、特定の
   頂点の凹凸を含むことを特徴とする請求項２記載の３次
   元図形認識方法。
4. 【請求項４】 前記拘束条件は、更に捕捉的な部分的拘
   束条件を随時含むことを特徴とする請求項２記載の３次
   元図形認識方法。
5. 【請求項５】 前記部分的拘束条件は、特定の面の法線
   ベクトルを含むことを特徴とする請求項４記載の３次元
   図形認識方法。