平成9年度 委託研究ソフトウェアの提案 |
研究代表者: | 田中 英彦 教授 |
東京大学・工学系研究科・情報工学専攻 |
しかし、ただ単に正方形や円や直線を画面上に並べるだけでなく、それらの間で合 同性や対称性、平行や垂直といった一般的な幾何学的関係が満たされるようにしよ うとすると、オブジェクトの複製や反転、回転などを組み合わせなければならず、 現在利用可能な描画インタフェースでは非常に困難である。幾何的関係を明示的に 指定し自動的に処理を行なう制約ベースの描画システムなどが研究されているが、 幾何学的制約を正確に指定することは難しく、一般に普及するには至っていない。 また、既存の描画システムは主にデスクトップ環境で比較的時間をかけることので きる状況でのマウスによる描画のためのものであり、近い将来に普及が予想される 電子黒板システムや携帯端末上でのペンによる短時間での描画には適しているとは いえず、そのための新しい技術が求められている。
一方、計算機科学の分野では複雑な問題を効率的に扱う手法として、宣言的関係と して表現された知識である制約を効率的に管理する制約処理系に関する研究が従来 より活発に行なわれている。数多くの実用的な制約論理型言語が提案されている他、 エキスパートシステムのような知識処理から対話型ユーザインタフェースに渡るま で様々な新しい応用が試みられている。
具体的には、以下に述べるように手書き入力から自動的に満たすべき幾何学的制約を
抽出し、それらの制約を充足する図形を生成して提示するシステムを構築する。
このような描画手法は、すべての操作をユーザが直接的に行なっていた従来の描画シ
ステムと異なり、ユーザの負担を減らし計算機側での処理を多く行なうという新しい
方向性を追求したもので、様々な研究課題が存在する。例えば、インタフェースはど
のように設計すべきなのか、どのような幾何学的制約を用意するべきなのか、あるい
はいかにして複雑な制約を効率的に解いていくのかなど、の研究課題がある。これら
の問題にソフトウェアを実際に作成しテストを行なうことで実験科学的に取り組んで
いくことを目的とする。
また提案する手法は、抽出された幾何学的制約から整形図形を計算する際の数値計算 に、一般的な宣言的知識の処理手法の一種である制約処理系を利用しており、この点 についても研究としての意義が認められる。すなわち、従来の制約処理系の研究の多 くは主に理論的な立場から行なわれてきたものが多く、実用的な制約解消系の提供、 あるいは制約処理系の新しい利用方法の提案などはあまり行なわれて来なかった。こ のような中で、本研究は具体的な制約処理系を効果的に利用したアプリケーションの 構築を通して、制約処理系の研究に利用者としての立場から寄与することが期待される。
これらの複雑な操作は、描画作業の効率を下げる原因であり、また適切な操作の組み 合わせを見つけられないことによる不完全な図形描画の原因にもなり得る。我々は、 このような幾何制約充足に関わる編集操作からユーザを解放する「対話的整形」とい う描画手法を提案、プロトタイプシステムの実装を行なう。
本手法は基本的にはフリーストロークの自動整形である。システムは、ユーザが画面 上に描いた線分からその線分の満たすべき幾何制約を自動抽出し、連立方程式として 解くことにより各座標を計算し、整形図形として表示する。例えば、画面上にすでに 存在する線分に接近して垂直に近いストロークを描いた場合、線分の接続条件および 垂直条件を満たすような整形線分が出力される。本手法により、左右対称や平行垂直、 接続、平行線分間の距離の一致といった複雑な制約を満たす図形を、複製や反転・回転 といった編集操作や特殊な描画モードを一切使用することなく描くことが可能となる。
しかし、このような自動認識機能をもったシステムには、常に入力の曖昧性および認識 の失敗という問題が存在する。そこで本システムは、制約を解く際に連立方程式として 矛盾しない組み合わせをすべて数えあげ、それぞれを解くことにより複数の候補の自動 生成を行なう。生成された複数の候補は画面上に表示され、ユーザは希望する候補を直 接選択することができる。さらに、それぞれの候補の満たしている制約が視覚的にユー ザに示されるため、他数の候補が生成された場合でも効率良く描画を進めることが可能 になっている。
上記のような機構を効率的に実現する実装手法として、制約抽出部と制約解消部を分離 したアルゴリズムを提案する。制約抽出部では入力された線分と画面中の線分との位置 関係を調べ、満たすべき幾何関係を抽出する。制約解消部では抽出された幾何関係を制 約過剰状態の連立方程式として解き、可能な解の集合としての複数候補を返す。このよ うに制約の抽出と解消を分離することにより、負荷の大きい処理を重複して行なうこと を避けることが可能になる。実装されている制約解消アルゴリズムは制約過剰状態を扱 うという点で従来のアルゴリズムの大幅な拡張となっている。例えば、
x - y = 100, x + y = 310, x = 200, y = 120,
という制約が与えられた場合、従来の通常の制約処理系は矛盾した制約として 答を返すことができなかったが、本制約処理系は矛盾する制約を自動的に識別して
(x, y) = (200, 100), (220, 120), (200, 110), (190, 120)
という解の集合を返す。 内部的には、制約を解く過程で生成される過渡的な解を充足さ れる制約の組み合わせに応じて複数保持し、それらの間の依存関係を利用つつ解いてい くことで最終的な解集合を効率的に生成する。
現在までに基本的な実験システムが実際にペン入力端末に実装されており、対話的な作 業を可能するに十分な実行速度を達成している。また、実験システムおよび市販のシス テムを利用した評価実験を行なっている。市販システムとしては、通常の CADシステム および 描画エディタを使用した。この実験は、各システムを利用して被験者に所定の幾 何的図形を描かせるものであり、描画時間および描画された図形がどのくらい要求した 幾何関係を満たしているかの比較を行なった。その結果、描画時間は従来手法に比して 約半分以下になり、幾何制約の充足率は 20 % 以上改善されていることが確認された。 この実験結果により、対話的整形という描画手法の有効性および将来の実用化に向けて の可能性が示されたといえる。今後は、さらにシステムを拡張し、より現実的な状況で のユーザの行動を記録、評価および考察を行なっていく予定である。
(以下が、本研究の参考文献の一部)
氏 名 | 所 属 | |
研究代表者 | 田中 英彦 | 東大・工学系研究科 |
研究協力者 | 五十嵐 健夫 | 東大・工学系研究科 |
研究協力者 | 松岡 聡 | 東工大・情報理工学 |
本システムの役割は、ある特定のアプリケーションの支援を行なうのでなく、単体とし
て計算機上での幾何学的図形の描画という作業を支援することである。すなわち、本シ
ステムはユーザに対して総合的に快適な描画環境を提供することをその役割としている。
その他に、本システムは今まで理論的な研究の先行していた制約処理系を実際に応用的
な場面で有効に利用している数少ない事例であり、アプリケーションの立場から制約処
理系の研究に対してフィードバックを行なうという第二の役割も担っている。
本システムの特徴としては、
システムは大きく分けて、ユーザが直接に触れる部分であるユーザインタフェース部、 入力図形から幾何学的制約を抽出する制約抽出部、抽出された制約を解いて整形結果の 複数候補を生成する制約解消部、の三つの部分よりなる。
システム全体が単体で動作するためにインストールも簡単で動作に不安定を生じる可能 性も低く、より多くの人につかってもらうことを期待できる。描画結果は一般的な形式 で保存可能であるため、作成の困難な幾何学的制約を満たす骨格を本システム上で生成 したのち、より機能の豊富な既存のエディタで装飾等の後処理を行なうなど実際的な場 面で利用することが可能である。
利用方法としては、通常の描画エディタとして従来の描画システムの補助として利用す る他、電子黒板によるプレゼンテーションでの利用、携帯端末での図形的なメモとりで の利用、などが考えられる。特に理科や数学の教材として使用する資料を作成する際な どは、本システムの提供するような幾何学的形状の正確な描画が可能になるため、本シ ステムの有効性は非常に高いと考えられる。
さらに興味に応じて、ユーザインタフェースの裏で動いている制約解消系の動作を観察 することができるため、制約処理について何も知らないユーザが制約解消系についての 理解を深めるきっかけとなることが期待でき、教材としてあるいは研究用の資料として の価値が認められる。
www-admin@icot.or.jp