(57)【特許請求の範囲】
【請求項１】
データ・オブジェクトについて実行された複数の対話式編集操作をアンドゥーする方法であって、
不均一な間隔で離間された、前にオブジェクトについて実行された編集操作にそれぞれ対応するデータ・オブジェクトの複数の前状態を記憶し、
データ・オブジェクトについて実行された不要な編集操作をアンドゥーするための命令を受取り、
不要な編集操作前に実行された、前に実行された編集操作に対応する記憶された前状態を選択し、
オブジェクトを選択された記憶された前状態に回復し、
データ・オブジェクトを不要な編集操作の直前の状態に戻すために、回復されたオブジェクトに、選択された記憶された前状態の後で且つ不要な編集操作の前において、前に実行された編集操作を再び加える、
各ステップを含む方法。
【請求項２】
実行されるべき次の編集操作の各々に対し、記憶された前状態の選ばれた１つを削除するかどうかを決定し、
データ・オブジェクトに次の編集操作を加える前にデータ・オブジェクトの現在状態を記憶し、
データ・オブジェクトに次の編集操作を加える、
各ステップをさらに含む請求項１に記載の方法。
【請求項３】
複数編集操作がそれぞれ操作番号を割当てられ、そして、記憶された前状態に対応する編集操作の操作番号を含んだスタックを維持するステップをさらに含む請求項２に記載の方法。
【請求項４】
削除するかどうかを決定するステップが、どの記憶された前状態が削除されるべきかを決定するため、最後に実行された編集操作の操作番号についてＸＯＲ操作を実行することを含む請求項３に記載の方法。
【請求項５】
データ・オブジェクトが、デジタル・ピクチャーである請求項１に記載の方法。
【請求項６】
編集操作が、デジタル・ピクチャーにペインテイング・ストロークを加えることを含む請求項５に記載の方法。
【請求項７】
記憶された前状態に対応する編集操作間の間隔は、前記編集操作が最後に実行された編集操作から遠ざかるにつれて、増加する請求項１に記載の方法。
【請求項８】
記憶された前状態に対応する編集操作間の間隔は、概して指数関数的に増加する請求項７に記載の方法。
【請求項９】
記憶された状態に対応する編集操作間の間隔は、概して底２の指数関数的に増加する請求項８に記載の方法。
【請求項１０】
新しい編集操作を実行する際、記憶された前状態の選択された１つを削除するかどうかを決定するステップをさらに含む請求項９に記載の方法。
【請求項１１】
削除するかどうを決定するステップが、記憶された前状態のどれを削除すべきかを決定するために、最後に実行された編集操作の操作番号についてＸＯＲ操作を実行することを含む請求項１０に記載の方法。
【請求項１２】
コンピュータ実行可能な命令を有するコンピュータ読取り可能な媒体であって、
データ・オブジェクトについて複数の編集操作を実行し、
不均一な間隔で離間された、前にオブジェクトについて実行された編集操作にそれぞれ対応するデータ・オブジェクトの複数の前状態を記憶し、
データ・オブジェクトについて実行された不要な編集操作をアンドゥーするための命令を受取り、
不要な編集操作前に実行された、前に実行された編集操作に対応する記憶された前状態を選択し、
オブジェクトを選択された記憶された前状態に回復し、
データ・オブジェクトを不要な編集操作の直前の状態に戻すために、回復されたオブジェクトに、選択された記憶された前状態の後で且つ不要な編集操作の前において、前に実行された編集操作を再び加える、
各ステップを実行するコンピュータ実行可能命令を含むコンピュータ読取り可能媒体。
【請求項１３】
データ・オブジェクトに新しい編集操作を加えるためにユーザ命令を受取り、
ユーザ命令の受取りに応じて、記憶された前状態の選択された１つを削除し、
データ・オブジェクトに新しい編集操作を加える前にデータ・オブジェクトの現在状態を記憶し、
データ・オブジェクトに新しい編集操作を加える、
各ステップを実行するためのコンピュータ実行可能命令をさらに含む請求項１２に記載のコンピュータ読取り可能な媒体。
【請求項１４】
デジタル・ピクチャーに加えられたデジタル・ペインテイング・ストロークをアンドゥーする方法であって、
予め選択された間隔で離間された、前に加えられたペインテイング・ストロークにそれぞれ対応するデジタル・ピクチャーの複数の前状態を記憶し、予め選択された間隔は概して底２の指数関数的に増加し、
ペインテイング・ストロークをアンドゥーするための命令を受取る際、アンドゥーされるべきペインテイング・ストロークの前に実行された、前に加えられたペインテイング・ストロークに対応する記憶された前状態を選択し、
デジタル・ピクチャーを選択された記憶された前状態に回復し、
回復されたオブジェクトに、選択された記憶された前状態の後で且つあんどぅーされたペインテイング・ストロークの前において、前に加えられたペインテイング・ストロークをを再び加える、
各ステップを含む方法。
【請求項１５】
デジタル・ピクチャー上に描かれるべき次のペインテイング・ストロークを加える際に、記憶された前状態の選ばれた１つを削除するかどうかを決定し、
ペインテイング・ストロークを加える前にデジタル・ペインテイングの現在状態を記憶し、
デジタル・ピクチャーに次のペインテイング・ストロークを描く、
各ステップをさらに含む請求項１４に記載の方法。
【請求項１６】
削除するかどうかを決定するステップが、どの記憶された前状態が削除されるべきかを決定するため、最後に加えられたペインテイング・ストロークのストローク番号についてＸＯＲ操作を実行することを含む請求項１５に記載の方法。
【請求項１７】
データ・オブジェクトについて複数の編集操作をアンドゥーする方法であって、
データ・オブジェクトについて実行された前記複数の編集操作の各々に操作番号を割当て、
不均一な間隔で離間された複数の編集操作の複数の操作番号をスタック内に入れ、
スタック内の操作番号にそれぞれ対応するデータ・オブジェクトの複数の前状態を記憶し、
データ・オブジェクトに実行された不要な編集操作をアンドゥーするための命令を受取り、不要な編集操作は第１の操作番号を有し、
スタック内に入れられた操作番号から、第１の操作番号より前の第２の操作番号を選択し、
第２の操作番号に対応する記憶された前状態にデータ・オブジェクトを回復し、
第２の操作番号が第１の操作番号の直前で無い時、第２及び第１の操作番号の間の操作番号を有する前に実行された編集操作を回復されたオブジェクに順次に再び加える、
各ステップを含む方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般に対話式データ編集に関し、より詳細にはデータ・オブジェクトについて実行された編集をアンドゥー（取消）することに関する。
【０００２】
【発明の背景】
テキスト書類、ビジネス・チャート、エンジニアリング図面、デジタル・ピクチャー、及びコンピュータ・グラフイックス等、広い範囲の様々なデータ・オブジェクトを対話式に編集するために開発された多くの対話式データ編集ソフトウェア・アプリケーションが存在する。普通に使用される対話式データ編集アプリケーションでは、ユーザはデータ・オブジェクトに対して連続的な編集操作を加えることにより、データ・オブジェクトを修正する。例えば、ワード・プロセシング・プログラムのユーザは、タイプし、語を削除し、カットし、貼付けし、再フォーマット等をすることによりテキスト文書を編集する。そして、デジタル・ペインテイング・プログラムのユーザは、さまざまなデジタル・ペイントブラシの複数のストロークを加えることにより、ピクチャーを修正できる。データ・オブジェクトのタイプ及び関与する対話式編集操作とは関係無く、ユーザは時々、最後の又はいくつかの編集ステップの効果が望ましくないことを決定し、これらの編集ステップにより発生した変化を除去したいと欲するてあろう。この目的のため、今日入手可能な大部分の対話式データ編集アプリケーションは、編集されたデータ・オブジェクトを最後の編集ステップが実行される直前にその状態を回復する「アンドゥー」機能を支援する。
【０００３】
アンドゥー機能を実現するために広く使用されている手法は、「後方向−非生成」手法と呼ぶことができる。この手法の下では、最後の編集ステップをアンドゥーするには、データ・オブジェクトをその前の状態に戻すためにデータ・オブジェクトに最後の編集コマンドの逆転が加えられる。この後方向−非生成手法はワード・プロセシング・プログラムにおいて編集操作をアンドゥーするために普通に使用されている。編集操作のアンドゥーを可能にするため、編集コマンド（例えば、挿入、削除、カット、貼付け、フォーマット等）及び対応する変化（挿入された又は削除された部分など）はバッフア内に記憶される。ユーザがアンドゥー機能を選択する時は何時も、最後の編集操作の逆転が文書を前の状態に再生するために加えられる。例えば、文書に行なわれた削除は削除された部分を文書に再挿入することによりアンドゥーできる。アンドゥー機能を複数回選択することにより、ユーザは文書に加えられた複数の連続編集ステップをアンドゥーできる。
【０００４】
しかし、この後方向−非生成手法は全ての対話式編集操作に広く使用することができない。これはいくつかの編集操作が逆転不可能である、すなわち、アンドゥーされる編集操作の「逆転」を適用することにより前の状態が回復できないからである。このような逆転不可能な編集操作の一例は、デジタル・ピクチャーにデジタル・ペインテイング・ストロークを加えることである。デジタル・ピクチャーは、各々がピクセルの色を定義する色データを有する複数のピクセルを含む。もし、不透明の色のデジタル・ブラシ・ストロークがピクチャーに加えられたらならば、ブラシで触れられたピクチャーのそれらのピクセルの元の色データは新しい色データで書きかえられる。元の色データは、たとえブラシ・ストロークの効果が知られていても、新しい色データからは再生できない。この結果、デジタル・ペインテイング・ストロークのアンドゥは後方向−非生成手法を使用しては実現できない。
【０００５】
ペインテイング・ストロークの逆転不可能性は、満足なアンドゥー機構実現することをより困難にしている。現在、メモリ内に最後のストロークの直前のピクチャーの状態を記憶することにより最後のペテンテイング・ストロークを素早くアンドゥーすることを可能にすることが提案されている。この機構は相対的に速いけれども、それは最後のペインテイング・ストロークのアンドゥーのみを処理できるだけである。もし、ユーザが最後から２番目のストロークをアンドゥーすることを欲する場合は、ピクチャーは最後から３番目のストロークまでペインテイング・セッションの最初のストロークからストローク毎に再生されなければならない。もし、最後から３番目のストロークをアンドゥーすべき場合は、ピクチャーは最初のストロークから最後の第４番目のストロークまで、全てのストロークを再び加えることにより再生される。この結果、複数アンドゥー操作、すなわち、最後の編集操作以上のアンドゥー操作は、ピクチャー内の既存のストロークの数が大きい時は、許容できないほどに遅くなる。
【０００６】
複数アンドゥー操作の速度を改良するために１つの可能な方法は、最近の幾つかのストロークのためにピクチャーの前の状態を記憶することである。複数アンドゥー操作は、メモリ内に回復されるべきピクチャーの状態が記憶されている限り、素早く実行できる。しかし、この手法は一般に好まれない。第１に、このアンドゥー機構の深さ、すなわち、効率的にアンドゥーできる連続したストロークの数は、メモリ内に記憶されている最近の状態の数によりいまだ制限される。さらに、ピクチャーの最近の状態を記憶するのに必要なメモリ量は、それほど深くない操作についてさえも大変大きくなる。
【０００７】
従って、デジタル・ペインテイング・プログラムのユーザにより加えられたデジタル・ペインテイング・ストロークなど、複数の逆転不可能な編集操作をアンドゥーするために使用できる、合理的に速く、操作の合理的な深さの大きさを持ち、そしてメモリ空間に許容できないほどの高い要求を課すことのない、アンドゥー機構が必要とされる。
【０００８】
【発明の開示】
本発明によれば、速さ、操作の深さ、及びメモリ要求の観点で改良された性能を与え、そして逆転不可能な編集操作のアンドゥーに使用することができる、データ・オブジェクトについて複数の編集操作をアンドゥーするための方法及びシステムが提供される。編集操作中、メモリ内に複数の前状態が記憶される。記憶された前状態は、不均一にそして好ましくは指数関数的に増加する間隔で離間された前に実行された編集操作に対応する。望まれない編集操作をアンドゥーする時、データ・オブジェクトは最初に記憶された前状態に回復される。もし、その回復された状態が目標の状態でなければ（すなわち、望まれない編集操作直前の状態）、回復された状態と望まれない操作の間の全ての前に実行された編集操作がデータ・オブジェクトに再び加えられて、目標の状態を再生する。
他の効果は、図面を参照して以下の詳細な説明を読むことにより明らかとなる。
【０００９】
本発明はさまざまな修正や代替的な構成が可能であるけれど、図面及び以下の説明にはその内のある例示的な実施の形態が示されている。しかし、本発明を開示された特定の形に限定する意図は無く、逆に、特許請求の範囲により定義される本発明の精神と範囲の内に入る全ての修正、代替的な構成及び均等物を含む意図であることを理解されるべきである。
【００１０】
【好適な実施の形態の説明】
図面を参照すると、図１及び以下の議論は本発明を実施できる適当なコンピューテイング環境について短く、一般的な説明を与えることを意図している。必要ではないが、本発明はパーソナル・コンピュータで実行できるプログラム・モジュールなどのコンピュータ実行可能命令の一般的な文脈で説明される。一般に、プログラム・モジュールは特定の仕事を実行し又は特定の抽象データ・タイプを実現する、ルーチン、プログラム、オブジェクト、コンポーネント、データ構造等を含む。さらに、本発明は、手持ちの装置、複数プロセッサ・システム、マイクロプロセッサ・ベース又はプログラム可能コンシューマー電子装置、ネットワークＰＣ、ミニコンピュータ、メインフレーム・コンピュータ等を含む他のコンピュータ・システム構成でもって実施できることは、当業者には理解される。本発明はまた、仕事が通信ネットワークを介して接続された遠隔の処理装置により実行される分散型コンピューテイング環境においても実行できる。分散型コンピューテイング環境において、プログラム・モジュールは遠隔及びローカルメモリ装置の両方に配置できる。
【００１１】
図１を参照すると、本発明を実施するための例示的なシステムは、処理ユニット２１、システム・メモリ２２、及びシステム・メモリを含むさまざまなシステム・コンポーネントを処理ユニット２１に結合するシステム・バス２３を含む、通常のパーソナル・コンピュータ２０の形式の汎用コンピューテイング装置を含む。システム・バス２３は、メモリ・バス又はメモリ・コントローラ、周辺バス、及びさまざまなバス・アーキテクチャのいすれかを使用したローカル・バスを含むバス構造のいくつかのタイプのいずれかである。システム・メモリは読出し専用メモリ（ＲＯＭ）２４及びランダム・アクセス・メモリ（ＲＡＭ）２５を含む。スタート・アップ中など、パーソナル・コンピュータ２０内の要素間の情報の転送を助ける基本的ルーチンを含んだ基本入力／出力システム２６（ＢＩＯＳ）が、ＲＯＭ２４内に記憶される。パーソナル・コンピュータ２０はさらに、図示しないハード・ディスクから読取り及び書込むためのハード・ディスク・ドライブ２７と、取外し可能磁気ディスク２９から読取り又は書込むための磁気ディスク・ドライブ２８と、ＣＤＲＯＭ又は他の光学媒体などの取外し可能な光学ディスク３１から読取り又は書込むための光学ディスク・ドライブ３１とを含む。ハード・ディスク・ドライブ２７、磁気ディスク・ドライブ２８、及び光学ディスク・ドライブ３０はそれぞれ、ハード・ディスク・ドライブ・インターフエイス３２、磁気テセィスク・ドライブ・インターフエイス３１、及び光学ドライブ・インターフエイス３４によりシステム・バス２３に接続されている。ドライブ及びそれらに付随したコンピュータ読取り可能な媒体は、コンピュータ読取可能な命令、データ構造、プログラム・モジュール、及びパーソナル・コンピュータ２０のための他のデータのための不揮発性記憶を与える。ここに説明された例示的な環境はハード・ディスク、取外し可能磁気ディスク２９及び取外し可能光学ディスク３１を使用するけれど、当業者には理解されるように、磁気カセット、フラッシュ・メモリ・カード、デジタル・ビデオ・ディスク、ベルヌーイ・カートリッジ、ランダム・アクセス・メモリ（ＲＡＭ）、リード・オンリー・メモリ（ＲＯＭ）等、コンピュータによりアクセス可能なデータを記憶できるコンピュータ読取り可能な媒体の他のタイプも例示的なオペレーテイング環境に使用できる。
【００１２】
オペレーテイング・システム３５、１つ又は複数のアプリケーション・プログラム３６、他のプログラム・モジュール３７、及びプログラム・データ３８を含む、いくつかのプログラム・モジュールがハード・ディスク、磁気ディスク２９、光学ディスク３１、ＲＯＭ２４又はＲＡＭ２５上に記憶できる。ユーザは、キーボード４０などの入力装置及びマウスなどのポインテイング装置４２を介してパーソナル・コンピュータ２０内に命令や情報を入力できる。他の入力装置（図示しない）は、マイクロホン、ジョイステイック、ゲームパッド、スキャナー等を含むことができる。これら及び他の入力装置はしばしばシステム・バスに結合されているシリアルポート・インターフエイス４６を介して処理ユニット２１へ接続される。しかし、パラレルポート、ゲームポート、又はユニバーサル・シリアル・ポート（ＵＳＢ）などの他のインターフエイスにより接続されても良い。モニター４７又は他のタイプのデイスプレイ装置が、ビデオ・アダプター４８などのインターフエイスを介してシステム・バス２３にまた接続されている。モニターに加えて、パーソナル・コンピュータは典型的にスピーカー及びプリンターなどの他の周辺出力装置（図示しない）を含む。
【００１３】
パーソナル・コンピュータ２０は、遠隔コンピュータ４９などの１つ又は複数の遠隔コンピュータへの論理的接続を使用したネットワーク環境内で動作できる。遠隔コンピュータ４９は、図１にはメモリ記憶装置５０のみが示されているけれど、別のパーソナル・コンピュータ、サーバー、ルーター、ネットワークＰＣ、ピア装置、又は他の共通ネットワーク・ノードであり、そして典型的にはパーソナル・コンピュータ２０に関して上述した要素の全て又は多くを含む。図１に描かれた論理的接続は、ローカル・エリア・ネットワーク（ＬＡＮ）５１及びワイド・エリア・ネットワーク（ＷＡＮ）５２を含む。このようなネットワーク環境は、オフイス、企業コンピュータ・ネットワーク、イントラネット、及びインターネットにおいてありふれたものである。
【００１４】
ＬＡＮネットワーク環境で使用される時、パーソナル・コンピュータ２０はネットワーク・インターフエイス又はアダプター５３を介してローカル・ネットワーク５１に接続される。ＷＡＮネットワーク環境で使用される時、パーソナル・コンピュータ２０は、インターネットなどのワイド・エリア・ネットワーク５２を介して通信を確立するためのモデム５４又は他の手段を典型的に含む。内部又は外部であるモデム５４は、シリアル・ポート・インターフエイス４６を介してシステム・バス２３に接続される。ネットワーク環境では、パーソナル・コンピュータ２０に関連して説明されたプログラム・モジュール又はそれらの部分は遠隔メモリ記憶装置内に記憶できる。図示されたネットワーク接続は例示であり、コンピュータ間の通信接続を確立する他の手段が使用できる。
【００１５】
本発明は、データ・オブジェクトに実行された複数の編集操作をアンドゥーするための方法及びシステムに関する。編集プロセス中、ユーザにより複数の連続した編集操作がデータ・オブジェクトに加えられる。そして、ユーザはデータ・オブジェクトを前の状態に戻すために最後の又は複数の編集操作をアンドゥーすることを決定することができる。
【００１６】
図２を参照すると、編集プロセス中、本発明による方法は概して、メモリ内に編集されているデータ・オブジェクトの複数の前状態を記憶する（ステップ６０）。本発明の特徴によれば、記憶された前状態は連続でないが不均一な間隔で離間された前に加えられたそれぞれの編集操作に対応する。データ・オブジェクトに実行された編集操作もメモリ内に記憶される。ユーザが１つの編集操作をアンドゥーするための命令を入力する時、記憶された編集操作及び記憶された前状態はデータ・オブジェクトをアンドゥーされるべき編集操作が実行される直前のその状態に戻すのに使用される。より詳細には、もし、記憶された前状態の１つが目標の状態であるならば（すなわち、アンドゥーされるべき編集操作の直前の状態）（ステップ６４）、データ・オブジェクトは記憶された状態データを使用してその状態に回復される（ステップ６６）。一方、もし、目標の状態が記憶された前状態の１つでなければ、データ・オブジェクトは最も若い記憶された前の状態に回復される（ステップ６８）。そして、最も若い記憶された前状態とアンドゥーされるべき操作の間に前に加えられた全ての編集操作が、回復されたデータ・オブジェクトに再度加えられて、目標の状態を再生する（ステップ７０）。
【００１７】
一例として、図３は、０からＮまで番号が付されたＮ＋１の連続した編集操作が実行された対話式編集プロセスの時間線８０を示している。そして、不均一な間隔で離間したデータ・オブジェクトの前状態の複数が記憶されている。説明される例においては、記憶された前状態８１−８３は、操作番号Ｎ−１、Ｎ−４、Ｎ−８を持つ編集操作に対応する。ユーザが番号Ｎの編集操作をアンドゥーするために命令を入力すると、データ・オブジェクトは単純に操作番号Ｎ−１についての記憶された状態８１に回復される。しかし、もし、ユーザがさらに編集操作Ｎ−１をアンドゥーするための命令を入力すれば、データ・オブジェクトは編集操作Ｎ−４についての記憶された状態８２へ最初に回復される。これは、編集操作Ｎ−２についての前状態が記憶されておらず、そして編集操作Ｎ−４についての状態が最も若い記憶された前状態だからである。引き続いて、編集操作Ｎ−３及びＮ−２が回復されたデータ・オブジェクトに再度加えられて、編集操作Ｎ−２に対応する状態を再生する。以下に詳細に説明するように、記憶された前状態のリストは好ましくは動的に更新される。すなわち、編集されているデータ・オブジェクトにより多くの編集操作及びアンドゥー操作が加えられる時、既存の記憶された状態が削除され、そして、新しい状態が記憶される。記憶された状態のリストの動的な更新は、前状態を記憶するためにメモリ空間を有効に使用することを可能にする。
【００１８】
好適な実施の形態において、記憶された前状態間の間隔は、記憶された前状態がデータ・オブジェクトの現在状態から遠ざかるにつれて一般に増大する。より好適な実施の形態において、間隔は一般に指数関数的に増加する。以下に詳細に説明するように、この構成は、合理的に大きな深さのアンドゥー操作を支援するために相対的に小さい数の記憶された前状態が十分であるという利点を有する。
【００１９】
本発明のアンドゥー方法は、対話式編集プロセスの多くの異なるタイプに適用可能である。例えば、編集されているデータ・オブジェクトはテキスト文書であり、編集操作はテキストを入力又は削除、カッテイング、貼付け、再フォーマット等のワード・プロセッシング操作を含むことができる。上述したように、ワード・プロセッシング・アプリケーション中のアンドゥー機能は典型的に、アンドゥーされるべき編集操作の逆転がデータ・オブジェクトに加えられてそれを前の状態に戻すという「逆方向−非生成」手法の下で実行される。本発明のアンドゥー方法は、このような逆転可能編集操作に対してアンドゥー機能を実現するための効果的な代替を与える。
【００２０】
しかし、本発明のアンドゥー方法は、デジタル・ピクチャーへデジタル・ペイントブラシ・ストロークを描くなどの逆転不可能な編集操作をアンドゥーするために特に有利である。逆転不可能な編集操作をアンドゥーするのに有利に使用できることを説明するために、本発明のアンドゥー方法が、デジタル・ピクチャーにさまざまなデジタル・ペイントブラシのストロークが加えるためにユーザにより使用されるデジタル・ペインテイング・プログラムの文脈において、以下に説明される。しかし、編集操作とデータ・オブジェクトの対応する状態が記憶できる限り、本発明によりアンドゥーできる編集操作の特別なタイプについて制限が無いことを理解できる。
【００２１】
何が１つの編集操作を構成するかは、編集操作の性質とソフトウェア開発者による設計選択とに依存することも理解される。例えば、ワード・プロセッシング・アプリケーションにおいて、編集操作は与えられた時間間隔内でテキストを入力すること又は選ばれたテキスト・ブロックを削除することである。デジタル・ペインテイング・プログラムにおいて、各ペインテイング・ストロークを１つの編集操作として処理することが便利である。代替的に、各編集操作は、アンドゥー操作のより細かい粒子性を与えるためにストロークの一部のみを含んでも良い。
【００２２】
一例として、図４は、背景イメージ９１及びそれに加えられた複数のデジタル・ペインテイング・ストローク９２−９４とを含んだ、デジタル・ピクチャー９０を示す。本出願と同じ譲受人に譲渡された米国特許５，８３５，０８６（米国特許出願シリアル番号０８／９７９，５２４）に記載されているように、ペインテイング・ストロークを形成するために異なる形式及び形状のさまざまなデジタル・ペイントブラシが使用できる。好適な実施の形態において、各ペインテイング・ストロークは１つの編集操作を構成する。ペインテイング・ストロークは、ピクチャー内にストロークとそのトレースを形成するために使用されるデジタル・ペイントブラシの属性により定義される。図５に示すように、ストローク１０２を形成するペイントブラシのトレース１００は、開始点１０４、終了点１０６、及び複数の中間点を含むトレースに沿った複数の制御点により定義される。ペインテイング・ストローク・トレースを記憶するためのデータ構造が上記の米国特許出願シリアル番号０８／９７９，５２４に記載されている。とりわけ、メモリ内にペインテイング・ストロークを記憶することは、デジタル・ピクチャーに逆転ペインテイング・ストロークを加えることにより、より前の状態からピクチャーの状態を再生成することを可能にする。
【００２３】
ある時間において編集されているピクチャーの状態は、ピクチャー内のピクセルの色により定義される。色情報は、Ｒ、Ｇ、Ｂ、及びａが、赤、緑、青、及び透明性をそれぞれ表す周知のＲＧＢａフォーマットなどの普通に使用される色フォーマット内にある。ある時間のピクチャーの状態はメモリ内にピクセルの色情報を記憶することにより記憶される。ある状態にピクチャーを回復するために十分な情報を維持するために、必ずしもそのある状態についてピクチャーのピクセル毎の色を記憶する必要は無い。例えば、好適な実施の形態では、デジタル・ピクチャーは複数のタイルに分割され、各タイルは６４ピクセルの高さと６４ピクセルの幅を有する。ある状態について、１つ又は複数のストロークにより触られたこれらのタイルのみがメモリ内に記憶される必要がある。
【００２４】
デジタル・ピクチャーにペインテイング・ストロークを加えるという文脈において、好適な実施の形態の特徴に従えば、デジタル・ピクチャーの記憶された前状態は、一般に底２の指数関数的に増加する間隔により、分離される。好適な実施の形態の別の特徴に従えば、バッフア内の記憶された状態のリストは、記憶された前の状態間の指数関数的に増加する一般的なパターンを維持するために新しいストローク及びアンドゥー操作がピクチャーに加えられる時に、動的に更新される。この目的のため、編集セッション中のストロークは、セッションの最初のストロークがストローク番号０を持つ、連続したストローク番号が割当てられる。記憶された前状態の管理を容易にするため、スタックがどの前の状態が記憶されているかの追跡を維持するために使用される。図６を参照すると、異なるストロークに対応する状態データがバッフア・メモリ１１０内に記憶されている。各記憶された前状態のストローク番号はスタック１１２の要素である。ピクチャーの前状態がバッフアに記憶される時、そのストローク番号がスタック内にプッシュされる。バッフアから記憶された状態が削除される時、そのストローク番号もまたスタックから除去される。新しいストロークが加えられ、又は既存のストロークがアンドゥーされる時、スタックは常に更新されて、そして対応する状態データはバッフアから削除され又は追加される。
【００２５】
好適な実施の形態の特徴に従えば、スタック１１０及びバッフア１１２の動的管理は、スタック及びバッフアからどの記憶された前状態が除去されるべきかを決定するため大変単純で且つ効率的な方法を使用することにより達成される。図７を参照すると、もし、現在のストローク番号（すなわち、最後に加えられたストロークの番号）がＮであり、そして新しいストロークが与えられる場合、整数Ｋは次の様に計算される：
【００２６】
Ｋ＝ＣｏｕｎｔＢｉｔｓ（Ｎ  ＸＯＲ  （Ｎ＋１））
ここで、ＸＯＲは「排他的ＯＲ」演算子であり、そしてＣｏｕｎｔＢｉｔｓはそのオペランド中の１に等しいビットの数を計算する関数である。このＣｏｕｎｔＢｉｔｓ関数は、以下の例示的なコードにより実現できる。
【００２７】
0003554279.tif 000002
【００２８】
図７を参照すると、整数Ｋが計算された後（ステップ１１６）、スタック及び状態データ・バッフアがそこで更新される。スタックの長さが最初に整数Ｋと比較される（ステップ１１８）。もし、スタックの長さが整数Ｋよりも小さければ、スタック及びデータ状態バッフアは修正されない。一方、もし、整数Ｋがスタックの長さよりも小さければ、スタックのＫ番目の要素が検索される。そして、このスタック要素（ｓ（Ｋ））とスタックのトップ要素（ｓ（０））の間の差は、２Ｋと比較される（ステップ１２０）。もし、差が２Ｋよりも小さければ、Ｋ番目のスタック要素がスタックから除去される（ステップ１２２）。そして、Ｋ番目のスタック要素に対応する状態データがバッフアから削除されて新しい状態データを記憶するためにメモリ空間を自由にする（ステップ１２４）。一方、もし、スタックのトップとＫ番目のスタック要素の間の差が、２Ｋよりも大きければ、スタック及びバッフアは変化されない。この比較ステップは、その状態がスタックのトップに対応する状態から既に十分に遠く離れている時、記憶された状態の不必要な削除が発生しないことを保証するために実行される。
【００２９】
図８に、新しいストロークが加えられる時に、スタックと状態データを更新するプロセスが示されている。この実施の形態においては、ユーザはある数「ｎＳｔｏｒｏｋｅｓ」の連続したストロークを加えることができる。もちろん、数ｎＳｔｒｏｋｅｓは、１度に１つのストロークのみを加えることができるように、１に設定してもよい。ユーザによりデジタル・ピクチャーに加えられる各新しいストローク対して（ステップ１２８）、スタック及び状態データ・バッフアは上述した方法で更新される（ステップ１３０）。より詳細には、もし、最後に加えられたストロークのストローク番号がＮであるとすると、整数Ｋ＝ＣｏｕｎｔＢｉｔｓ（Ｎ  ＸＯＲ  （Ｎ＋１））が計算される。そして、スタックからＫ番目のスタック要素を除去するかどうか及びバッフアからそれに対応する状態データを削除するかどうかの決定が行なわれる。スタック及びバッフアが更新された後、最後のストローク番号、すなわち、Ｎ、がスタック内に押し込まれる（ステップ１３２）。そして、現在状態の状態データがバッフア内に記憶される（ステップ１３４）。そして、ストローク番号Ｎ＋１を持つ新しいストロークがデジタル・ピクチャー上に描かれる（ステップ１３６）。
【００３０】
一例として、図９は、デジタル・ピクチャーにストロークを加えた時にどのように記憶されたストローク番号のスタックが変化するかを示す表である。示された例では、２１の連続したペインテイング、番号０から番号２０まで、がデジタル・ピクチャーに加えられている。図９の表の各行は最右欄に示されたストローク番号に対応し、そしてそのストロークが加えられた後のスタック内の番号を含む。例えば、ストローク番号１７が加えられた後、スタックはストローク番号１６、１４、１２、８、及び０を含む。これらストローク番号に対応する状態データがバッフア内に記憶される。ストローク番号１８が加えられる時、Ｋ＝ＣｏｕｎｔＢｉｔｓ（１７  ＸＯＲ  １８）が、２と決定される。従って、スタック上の第２番目の項目、１４、がスタックから除去されて、そして、バッフアからストローク番号１４についての記憶された状態データが削除される。最後のストローク番号のストローク番号、すなわち、１７、がスタック内に押込まれ、そして、ストローク番号１７に対する状態データがバッフア内に記憶される。この結果、ストローク番号１８を描いた後のスタックは、ストローク番号１７、１６、１２、８、及び０を含む。
【００３１】
図９の表から理解されるように、ＣｏｕｎｔＢｉｔｓ（Ｎ  ＸＯＲ  （Ｎ＋１））関数に基づいてスタックを更新することは、概して底２の指数関数で増加する不均一な間隔により分離されたストローク番号のスタックを生成する。間隔は正確に指数関数のパターンに従う必要がないことが理解される。むしろ、間隔には指数関数的順序のいくつかの要素が省略されるか又は繰返されてもよい。例えば、ストローク番号１９に対してスタックはストローク番号１８、１６、１２、８、及び０を含み、これらは間隔２、４、４、及び８により分離されている。ストローク番号２０に対するスタックは、ストローク番号１９、１８、１６、８、及び０を含み、これらは間隔１、２、８、及び８により分離されている。時々、間隔は正確な指数関数のパターンに従う。例えば、ストローク番号１６が加えられた後、記憶された前状態はストローク番号１５、１４、１２、８及び０の状態を含み、これらはそれぞれ、間隔１、２、４、及び８により分離されている。しかし、この例は特別な場合と理解すべきである。
【００３２】
概して指数関数的に増加する間隔で前状態を記憶することの重要な利点は、合理的な大きな深さ（すなわち、相対的に効率的にアンドゥーできる連続した編集操作の最大数）の操作を支援するために記憶されるべき前状態が相対的に少ないことである。間隔が概して底２の指数関数で増加する好適な実施の形態において、約ｌｏｇ２（Ｍ）の前状態のみがＭのアンドゥー操作の深さを支援するために記憶される必要がある。例えば、約１００ストロークのアンドゥー深さを支援するためには約１０の前状態のみが記憶されなければならない。概して指数関数的に増加する間隔により分離されたストロークに対応する前状態を記憶することは、前状態を記憶するのに必要なメモリ量とアンドゥー操作を実行するのに要する時間量とをはかりにかけている。
【００３３】
この概して指数関数的なパターンのストローク間の間隔の別の重要な利点は、記憶された状態の密度がより最近の状態についてはより高いことである。この結果、ピクチャーの最近の状態と２番目に最近の状態がメモリ内に記憶されている可能性が高い。これは最近の状態が多いと、最近のいくつかの状態のアンドゥーは素早く実行できることを強調している。
【００３４】
図１０に、好適な実施の形態の複数ストロークのアンドゥーのプロセスが示されている。この実施の形態において、ユーザは１度にアンドゥーされるべきある数「ｎＵｎｄｏ」のストロークをアンドゥーするための命令を入力できる。ｎＵｎｄｏを１に設定することにより、ユーザが１度に１ストロークをアンドゥーすることを選択できることが理解される。アンドゥー命令を受取った後（ステップ１４０）、デジタル・ペインテイング・プログラムは、次式を計算することにより、アンドゥー操作後にピクチャーが回復されるべき目標の状態のストローク番号を決定する（ステップ１４２）：
【００３５】
ｎｅｗＬａｓｔ＝ＬＡＳＴ  −ｎＵｎｄｏ
ここで、ｎｅｗＬａｓｔは目標状態のストローク番号であり、ＬＡＳＴはアンドゥー操作前の現在ストロークである。トップのスタック要素、「ｎＴｏｐ」、はスタックから放出される（ステップ１４４）。もし、ｎＴｏｐがｎｅｗＬａｓｔよりも大きく、そして、スタック長が０よりも大きければ（ステップ１４６）、ストローク番号ｎＴｏｐに対応するバッフア内の状態データが削除される（ステップ１４８）。スタックを放出し、そしてバッフアから状態データを削除するステップは、ｎＴｏｐがｎｅｗＬａｓｔよりも小さいか又は等しくなるまで繰返される。そして、ピクチャーはストローク番号ｎＴｏｐに対応した状態に回復される（ステップ１５０）。もし、ｎＴｏｐがｎｅｗＬａｓｔに等しければ、この時点でアンドゥー操作が完了する。もし、ｎＴｏｐがｎｅｗＬａｓｔよりも小さければ（ステップ１５２）、ｎＴｏｐよりも大きくてｎｅｗＬａｓｔまでのストローク番号を持つ前に加えられたストロークの全てがピクチャーに加えられて（ステップ１５４）、ストローク番号ｎｅｗＬａｓｔに対応するピクチャーの状態が再生成される。
【００３６】
図１１は、ストロークが連続してアンドゥーされる時、デジタル・ピクチャーについてのストローク番号のスタックの進化を示す。表内の各列は、最右列内に示された対応するストロークがアンドゥーされる前にスタック内の数を含む。この例において、アンドゥーされるべき最初のストロークはストローク番号２０である。ストローク番号１９が既にスタック内に存在するから、アンドゥー操作は単にバッフア内の対応する状態データを使用してストローク番号１９の状態にピクチャーを回復することにより実行される。アンドゥー操作の一部として、スタックからストローク番号１９が放出されて、そしてバッフア内の対応する状態データが削除される。ストローク番号２０がアンドゥーされた後、ストローク１９のアンドゥーは同様に簡潔である。何故ならば、ストローク番号１８についての状態データは既にバッフア内に記憶されているからである。
【００３７】
これに対して、ピクチャーはストローク番号１７の状態には直接的に回復できない。何故ならば、バッフア内にその状態についての状態データが存在しないからである。その代り、ピクチャーは最初にストローク番号１６の状態に回復される。そして、ストローク番号１７がピクチャーへ加えられる。別の例として、ストローク１７の後にアンドゥーすると、スタック中にはストローク番号８及び０のみが残っている。ストローク１６をアンドゥーするために、ピクチャーが最初にストローク番号８の状態に回復される。そして、回復されたピクチャーにストローク番号９から１５までが連続的に加えられて、ピクチャーをストローク番号１５の状態に持って来る。
【００３８】
アンドゥー操作中、ピクチャーに前に加えられたストロークの各々が再び加えられる時、スタックは図８に関連して上述された方法に従って更新される。この結果、ストローク番号１６のアンドゥー後、バッフアへストローク１４及び１２についての状態データが加えられ、そしてスタックはストローク番号１４、１２、８、及び０を含むために再充填される。
【００３９】
スタックの再充填はより多くのストロークをアンドゥーするのに要する時間を顕著に減少することが理解される。例えば、もし、ストローク１５がアンドゥーされる場合、ピクチャーはストローク１４の状態に単純に回復できる。この状態はストローク番号１６のアンドゥーの際にバッフア内に記憶されているからである。スタックの再充填により、相対的に大きい数のストロークをアンドゥーするために再び加えられる必要のあるストロークが相対的に少なくなる。図６の表の最左列は、各ストロークをアンドゥーするために再び加えられるべきストローク数を示している。２０の連続したストロークをアンドゥーするためにさえも、再び加えられるストロークの全数は２５だけである。
【００４０】
以上説明したことから、本発明は逆転不可能な編集操作をアンドゥーするために有利に使用できる複数の編集操作をアンドゥーするための方法及びシステムが提供することが理解される。好適な実施の形態においては、記憶された状態を概して底２の指数関数で増加する間隔で持って離間する記憶された前状態を管理する単純で効率的な方法が提供される。記憶された前状態を管理するこの方法は、複数アンドゥー操作を、前状態を記憶するためのメモリ空間の量を許容可能に小さく維持しながら、操作の合理的に大きい深さで持って、合理的な速さで実行することを可能にする。
【図面の簡単な説明】
【図１】本発明によるデータ・オブジェクトについて実行された複数の対話式編集操作をアンドゥーするための方法及びシステムを実現するのに使用できるコンピュータ・システムのブロック図。
【図２】本発明による複数の編集操作をアンドゥーするステップを示すフロー・チャート。
【図３】本発明による複数編集操作をアンドゥーするのに編集されているデータ・オブジェクトの複数の記憶された前の状態の使用を示す概略図。
【図４】複数のペインテイング・ストロークが加えられたデジタル・ピクチャーを示す概略図。
【図５】デジタル・ピクチャーに加えられたペインテイング・ストロークを示す概略図。
【図６】複数編集操作のアンドゥーを支援するためにデータ・オブジェクトの前状態を記憶するスタック及びバッフアを示す概略図。
【図７】本発明の１つの実施の形態による記憶された前状態のスタックを更新するステップを示すフロー・チャート。
【図８】本発明の１つの実施の形態によるデジタル・ピクチャーへペインテイング・ストロークを加えるプロセスのステップを示すフロー・チャート。
【図９】本発明の１つの実施の形態によるペインテイング・ストロークがピクチャーに加えられる時にデジタル・ピクチャーの記憶された前状態のストローク数のスタックの進化を示すテーブル。
【図１０】本発明の１つの実施の形態によるデジタル・ピクチャーに加えられたペインテイング・ストロークをアンドゥーするステップを示すフロー・チャート。
【図１１】本発明の１つの実施の形態による複数のペインテイング・ストロークがピクチャーに加えられる時にデジタル・ピクチャーの記憶された前状態のストローク数のスタックの進化を示す表。
【図１】
0003554279.tif 000003
【図２】
0003554279.tif 000004
【図３】
0003554279.tif 000005
【図４】
0003554279.tif 000006
【図５】
0003554279.tif 000007
【図６】
0003554279.tif 000008
【図７】
0003554279.tif 000009
【図８】
0003554279.tif 000010
【図９】
0003554279.tif 000011
【図１０】
0003554279.tif 000012
【図１１】
0003554279.tif 000013