平成9年度 委託研究ソフトウェアの提案

(14) 制約処理系を利用した図形描画システム

  
研究代表者: 田中 英彦 教授
東京大学・工学系研究科・情報工学専攻



[目次]

  1. 研究の背景
  2. 研究の目的
  3. 研究内容
  4. 研究体制/研究方法
  5. 想定されるソフトウェア成果

[研究の背景]

計算機上での図形描画システムはすでに一般的なアプリケーションとして定着して おり、利用されているソフトウェアの種類、数は膨大な数にのぼっている。また、 画面上の図形オブジェクトをマウスを利用して直接に操作する直接操作インタフェ ースの普及により、これらの図形描画システムの操作性は飛躍的に向上し、初心者 でも従来不可能であったような正確で美しい図を短時間で描くことが可能になって きている。

しかし、ただ単に正方形や円や直線を画面上に並べるだけでなく、それらの間で合 同性や対称性、平行や垂直といった一般的な幾何学的関係が満たされるようにしよ うとすると、オブジェクトの複製や反転、回転などを組み合わせなければならず、 現在利用可能な描画インタフェースでは非常に困難である。幾何的関係を明示的に 指定し自動的に処理を行なう制約ベースの描画システムなどが研究されているが、 幾何学的制約を正確に指定することは難しく、一般に普及するには至っていない。 また、既存の描画システムは主にデスクトップ環境で比較的時間をかけることので きる状況でのマウスによる描画のためのものであり、近い将来に普及が予想される 電子黒板システムや携帯端末上でのペンによる短時間での描画には適しているとは いえず、そのための新しい技術が求められている。

一方、計算機科学の分野では複雑な問題を効率的に扱う手法として、宣言的関係と して表現された知識である制約を効率的に管理する制約処理系に関する研究が従来 より活発に行なわれている。数多くの実用的な制約論理型言語が提案されている他、 エキスパートシステムのような知識処理から対話型ユーザインタフェースに渡るま で様々な新しい応用が試みられている。


[研究の目的]

本研究の目的は、前述のような既存の描画システムの問題点を解決することのできる 描画方式とその効率的な実装アルゴリズムを提案するとともに、実際に計算機上に実 装することによってその実現可能性と有効性を示していくことである。

具体的には、以下に述べるように手書き入力から自動的に満たすべき幾何学的制約を 抽出し、それらの制約を充足する図形を生成して提示するシステムを構築する。
このような描画手法は、すべての操作をユーザが直接的に行なっていた従来の描画シ ステムと異なり、ユーザの負担を減らし計算機側での処理を多く行なうという新しい 方向性を追求したもので、様々な研究課題が存在する。例えば、インタフェースはど のように設計すべきなのか、どのような幾何学的制約を用意するべきなのか、あるい はいかにして複雑な制約を効率的に解いていくのかなど、の研究課題がある。これら の問題にソフトウェアを実際に作成しテストを行なうことで実験科学的に取り組んで いくことを目的とする。

また提案する手法は、抽出された幾何学的制約から整形図形を計算する際の数値計算 に、一般的な宣言的知識の処理手法の一種である制約処理系を利用しており、この点 についても研究としての意義が認められる。すなわち、従来の制約処理系の研究の多 くは主に理論的な立場から行なわれてきたものが多く、実用的な制約解消系の提供、 あるいは制約処理系の新しい利用方法の提案などはあまり行なわれて来なかった。こ のような中で、本研究は具体的な制約処理系を効果的に利用したアプリケーションの 構築を通して、制約処理系の研究に利用者としての立場から寄与することが期待される。


[研究内容]

計算機上での図形描画システムはすでに一般に広く普及しており、簡単な操作で紙の 上の作業では困難であった正確な図形を手早く描くことが可能になっている。
しかし、ただ単に独立した図形要素を適当に並べるだけでなく各種の幾何的位置関係 を満たした図形を描こうとした場合には、通常複雑な操作を組み合わせて使用するこ とが必要となる。たとえば、対称な図形を描く場合には複製、反転、移動、といった 操作を組み合わせて使わなければならず、また斜線に垂直な線分を描く場合には複製、 90度回転、といった操作が必要になる。

これらの複雑な操作は、描画作業の効率を下げる原因であり、また適切な操作の組み 合わせを見つけられないことによる不完全な図形描画の原因にもなり得る。我々は、 このような幾何制約充足に関わる編集操作からユーザを解放する「対話的整形」とい う描画手法を提案、プロトタイプシステムの実装を行なう。

本手法は基本的にはフリーストロークの自動整形である。システムは、ユーザが画面 上に描いた線分からその線分の満たすべき幾何制約を自動抽出し、連立方程式として 解くことにより各座標を計算し、整形図形として表示する。例えば、画面上にすでに 存在する線分に接近して垂直に近いストロークを描いた場合、線分の接続条件および 垂直条件を満たすような整形線分が出力される。本手法により、左右対称や平行垂直、 接続、平行線分間の距離の一致といった複雑な制約を満たす図形を、複製や反転・回転 といった編集操作や特殊な描画モードを一切使用することなく描くことが可能となる。

しかし、このような自動認識機能をもったシステムには、常に入力の曖昧性および認識 の失敗という問題が存在する。そこで本システムは、制約を解く際に連立方程式として 矛盾しない組み合わせをすべて数えあげ、それぞれを解くことにより複数の候補の自動 生成を行なう。生成された複数の候補は画面上に表示され、ユーザは希望する候補を直 接選択することができる。さらに、それぞれの候補の満たしている制約が視覚的にユー ザに示されるため、他数の候補が生成された場合でも効率良く描画を進めることが可能 になっている。

上記のような機構を効率的に実現する実装手法として、制約抽出部と制約解消部を分離 したアルゴリズムを提案する。制約抽出部では入力された線分と画面中の線分との位置 関係を調べ、満たすべき幾何関係を抽出する。制約解消部では抽出された幾何関係を制 約過剰状態の連立方程式として解き、可能な解の集合としての複数候補を返す。このよ うに制約の抽出と解消を分離することにより、負荷の大きい処理を重複して行なうこと を避けることが可能になる。実装されている制約解消アルゴリズムは制約過剰状態を扱 うという点で従来のアルゴリズムの大幅な拡張となっている。例えば、

 x - y = 100, x + y = 310, x = 200, y = 120,

という制約が与えられた場合、従来の通常の制約処理系は矛盾した制約として 答を返すことができなかったが、本制約処理系は矛盾する制約を自動的に識別して

 (x, y) = (200, 100), (220, 120), (200, 110), (190, 120)

という解の集合を返す。 内部的には、制約を解く過程で生成される過渡的な解を充足さ れる制約の組み合わせに応じて複数保持し、それらの間の依存関係を利用つつ解いてい くことで最終的な解集合を効率的に生成する。

現在までに基本的な実験システムが実際にペン入力端末に実装されており、対話的な作 業を可能するに十分な実行速度を達成している。また、実験システムおよび市販のシス テムを利用した評価実験を行なっている。市販システムとしては、通常の CADシステム および 描画エディタを使用した。この実験は、各システムを利用して被験者に所定の幾 何的図形を描かせるものであり、描画時間および描画された図形がどのくらい要求した 幾何関係を満たしているかの比較を行なった。その結果、描画時間は従来手法に比して 約半分以下になり、幾何制約の充足率は 20 % 以上改善されていることが確認された。 この実験結果により、対話的整形という描画手法の有効性および将来の実用化に向けて の可能性が示されたといえる。今後は、さらにシステムを拡張し、より現実的な状況で のユーザの行動を記録、評価および考察を行なっていく予定である。

(以下が、本研究の参考文献の一部)

五十嵐 健夫 河内谷 幸子 松岡 聡 田中 英彦
「自動認識整形機能をもったペンによる描画システム」
情報処理学会研究会報告 96-CG-81,
1996年8月, Vol. 96, No. 77, pp. 85-90.

河内谷 幸子 五十嵐 健夫 松岡 聡 田中 英彦
「認知的負荷を軽減する描画方式の提案と実装」
インタラクティブシステムとソフトウェアに関するワークショップ
(日本ソフトウェア科学会),
池田町営田園ホール(北海道), pp.71-80, 1996年11月.

五十嵐 健夫 河内谷 幸子 松岡 聡 田中 英彦
「制約を利用した対話的図形整形システム」
情報処理学会シンポジウム 「インタラクション '97」論文集, pp.69-70,1997年2月

五十嵐 健夫 河内谷 幸子 松岡 聡 田中 英彦
「手早く正確な図を描くことのできる描画システム」
第54回情報処理学会全国大会論文集, 1997年3月, Vol.4, No.5デモ-3,pp.425-426.

Takeo Igarashi, Sachiko Kawachiya, Satoshi Matsuoka, Hidehiko Tanaka
``In Search for an Ideal Computer-Assisted Drawing System''
INTERACT97
( The Sixth IFIP Conference on Human-Computer Interaction )
Sydney, Australia, 14-18 July, 1997


[研究体制/研究方法]

(1) 研究体制

   氏 名所  属
研究代表者田中 英彦東大・工学系研究科
研究協力者五十嵐 健夫東大・工学系研究科
研究協力者松岡 聡東工大・情報理工学


(2) 研究の方法

研究は、Windows 95 の搭載された通常のデスクトップ型の PC および Pen Computer を利用して行なう。

  1. まず、公開版 Pegasus の全体的な仕様を決定する。
    その作業には簡単なプロトタイプを作成しての検討なども含まれる。

  2. 最終版に先だって、テスト用のプロトタイプを作成する。
    この時点では付随的な機能は入れず、整形に基づく描画システムとしての 核となる部分を集中的に実装する。

  3. 作成したプロトタイプを使用してユーザテストを行なう。
    本研究は、ユーザの作業負荷を低減することを目標としており、 このようなユーザテストは不可欠なプロセスである。
    テストは、何人かの被験者に数多くの絵を描いてもらいそのプロセスを ビデオで録画して解析する他、主観的な判断を求めるアンケートをとる。

  4. ユーザテストの結果を分析して最終的な仕様を決定し、 プロトタイプシステムの調整と未完成な部分の実装を行なう。

  5. 一般に公開するために、使用法などについての文書を整備するとともに サンプル画像の作成、最終テスト、デバッグなどを行なう。


[想定されるソフトウェア成果]

(1)作成されるソフトウェア名称

制約処理系を利用した幾何学的図形の描画システム Pegasus

(2)そのソフトウェアの機能/役割/特徴

本ソフトウェアは、PC/AT 互換機上で通常の Windows用描画アプリケーションとして機 能する。ユーザは、本システム上でペンあるいはマウスを利用して自由に図形を入力す ることができ、システムはその入力図形から必要な幾何学的制約を抽出、整形を行なう。
図形のフリーストロークによる入力の他に、簡単なジェスチャーによる図形の消去、 メニューによる操作の取消や画面の消去、図形のファイルへの書き込み、読み込みが 可能である。

本システムの役割は、ある特定のアプリケーションの支援を行なうのでなく、単体とし て計算機上での幾何学的図形の描画という作業を支援することである。すなわち、本シ ステムはユーザに対して総合的に快適な描画環境を提供することをその役割としている。
その他に、本システムは今まで理論的な研究の先行していた制約処理系を実際に応用的 な場面で有効に利用している数少ない事例であり、アプリケーションの立場から制約処 理系の研究に対してフィードバックを行なうという第二の役割も担っている。

本システムの特徴としては、

  1. 図形描画という一般的な作業に利用できる実用性と、それを可能にしている、実 時間での処理を実現する高速性、
  2. 複雑な操作を一切必要とせず、誰でも簡単に使うことのできる簡便性、
  3. 制約解消系の利用という高度な計算処理の有効性を明確に伝えるメッセージ性、 等が挙げられる。
一般に、研究対象として作成されたプログラムは背景となる理論が先進的なものでも実 際に通常のユーザが利用することは困難であることが多いが、本ソフトウェアは初心者 でも利用可能でしかも需要の多いアプリケーションであるという点を最大の特徴として おり、公開することの意義は大きいといえる。

(3)ソフトウェアの構成/構造

本システムは全体として一つのアプリケーションとして動作するものであり、 既存のソフトウェアを利用したり、他のソフトウェアの一部として動作することはない。

システムは大きく分けて、ユーザが直接に触れる部分であるユーザインタフェース部、 入力図形から幾何学的制約を抽出する制約抽出部、抽出された制約を解いて整形結果の 複数候補を生成する制約解消部、の三つの部分よりなる。

  1. ユーザインタフェース部は、画面上にウインドウを開きペンまたはマウスを利用 した入力を受け付け入力図形および整形結果を表示する、といったインタフェース に関する一連の処理を行なう。

  2. 制約抽出部は、手書き入力から生成される入力座標列とすでに整形済みの全線分 の位置情報をユーザインタフェース部から受けとり、それらの間で満たされるべき 幾何学的制約を取り出す。生成された幾何学的制約は、整形結果の座標値を未知数 とする連立方程式として表現される。

  3. 制約解消部は、制約抽出部で生成された幾何学的制約をもとに計算を行ない、同 時充足可能な制約を組み合わせて解くことで複数の候補を生成し、ユーザインタフ ェース部へ返す。

(4)参考とされたICOTフリーソフトウェアとの関連

本ソフトウェアは、統合型制約ソルバー Consort と機能的に類似する制約解消系を実 装する。Consort は線形等式から非線系不等式までを解くことのできる並列計算機上 で動作する制約解消システムである。我々の実装する制約解消系は、幾何学的関係を 表現する限定された種類の線形等式のみを扱うシステムであること、通常の Windows マシン上で動作すること、過制約の状態から自動的に適切な組み合わせを見つけ出し 複数の候補を生成すること、などの点で Consort と性質が異なっている。将来、より 複雑な処理を並列計算機上で効率良く行う必要が生じた場合には、Consort のような 制約解消システムの利用も考えられる。

(5)使用予定言語および動作環境/必要とされるソフトウェア・パッケージ/ポータビリティなど

ユーザインタフェース部分は Microsoft Visual Basic で記述され、 幾何制約抽出部分および制約処理系は Microsoft Visual C++ で記述される。
OS は、Microsoft Windows 3.1 以上 (3.1, 85, NT) をターゲットとする。
プログラム本体と適合するOS以外に特殊なパッケージは必要としない。

(6)ソフトウェアの予想サイズ(新規作成分の行数)

  1. ユーザインタフェース部分 1000 行 (Visual Basic)
  2. 幾何制約抽出部 3000 行 (Visual C++)
  3. 制約処理系 2000 行 (Visual C++)

(7)ソフトウェアの利用形態

本ソフトウェアは、一般の Windows アプリケーションとして広く利用可能である。
すなわち、特別な環境を必要としたり限られた人間にのみ有用性のあるソフトウェアで はなく、一般にコンピュータ上で図形を描く必要のある多くの人が、現実に直面してい る問題を解決するために使用することができる。本ソフトウェアを利用することにより、 既存の描画システムではあまりに複雑で非直感的な操作を必要とされるために事実上描 画不可能であった幾何学的図形を、計算機の利用になれていない初心者でも手早く描く ことが可能になる。

システム全体が単体で動作するためにインストールも簡単で動作に不安定を生じる可能 性も低く、より多くの人につかってもらうことを期待できる。描画結果は一般的な形式 で保存可能であるため、作成の困難な幾何学的制約を満たす骨格を本システム上で生成 したのち、より機能の豊富な既存のエディタで装飾等の後処理を行なうなど実際的な場 面で利用することが可能である。

利用方法としては、通常の描画エディタとして従来の描画システムの補助として利用す る他、電子黒板によるプレゼンテーションでの利用、携帯端末での図形的なメモとりで の利用、などが考えられる。特に理科や数学の教材として使用する資料を作成する際な どは、本システムの提供するような幾何学的形状の正確な描画が可能になるため、本シ ステムの有効性は非常に高いと考えられる。

さらに興味に応じて、ユーザインタフェースの裏で動いている制約解消系の動作を観察 することができるため、制約処理について何も知らないユーザが制約解消系についての 理解を深めるきっかけとなることが期待でき、教材としてあるいは研究用の資料として の価値が認められる。

(8)添付予定資料

簡単なソフトウェアの概念仕様書、及びユーザマニュアル、サンプル画像集を 添付する予定である。通常のメンテナンスの必要なソフトウェアハウスの開発では なく、PDSとして'AS IS'で配布するもののため、機能仕様書・詳細仕様書はその性 格上全くそぐわないので、作成しない。


www-admin@icot.or.jp