(57)【特許請求の範囲】
【請求項１】
コンピュータに、
微分幾何学を使用してデジタルインクファイルのシャープポイントを算出する手順、
前記シャープポイント間のセグメントを曲線適合数学式によって定義する手順であって、前記セグメント内の２πを越える累積回転角を有するセグメントについては再分割し、かつ該再分割したセグメントを曲線適合数学式によって定義する手順、
前記シャープポイントに関する情報と前記曲線適合数学式を前記デジタルインクファイルのバックボーンスプラインとして記憶手段にストアしておく手順、
を実行させるためのプログラムを記録したことを特徴とするコンピュータ読取可能な記録媒体。
【請求項２】
請求項１に記載のコンピュータ読取可能な記録媒体において、前記バックボーンスプラインを前記デジタルインクファイルに関する追加情報と結合して、前記デジタルインクファイルの輪郭曲線を作成する手順を前記コンピュータに実行させるためのプログラムをさらに記録したことを特徴とするコンピュータ読取可能な記録媒体。
【請求項３】
請求項２に記載のコンピュータ読取可能な記録媒体において、前記追加情報は、太さ情報を含むことを特徴とするコンピュータ読取可能な記録媒体。
【請求項４】
請求項１に記載のコンピュータ読取可能な記録媒体において、前記シャープポイントを算出する手順に先立って、デジタルインクファイルをデノイズ（ノイズ除去）する手順を前記コンピュータに実行させるためのプログラムをさらに記録したことを特徴とするコンピュータ読取可能な記録媒体。
【請求項５】
請求項１に記載のコンピュータ読取可能な記録媒体において、前記シャープポイントは、前記デジタルインクファイル内のポイントであって、曲率が最大であるポイントを含むことを特徴とするコンピュータ読取可能な記録媒体。
【請求項６】
請求項１に記載のコンピュータ読取可能な記録媒体において、前記シャープポイントは、曲率が反転している個所のポイントを含むことを特徴とするコンピュータ読取可能な記録媒体。
【請求項７】
請求項１に記載のコンピュータ読取可能な記録媒体において、前記デジタルインクファイルは、生データインクトレースを含むことを特徴とするコンピュータ読取可能な記録媒体。
【請求項８】
請求項１に記載のコンピュータ読取可能な記録媒体において、前記シャープポイント間のセグメントを曲線適合数学式によって定義する前記手順は、該手順の実行の後で、その曲線適合数学式の曲線適合の誤差が予め定義されたしきい値以上であれば、そのセグメントをさらにサブセグメントに細分割し、そのサブセグメントを曲線適合数学式によって定義する手順を含むことを特徴とするコンピュータ読取可能な記録媒体。
【請求項９】
請求項１に記載のコンピュータ読取可能な記録媒体において、
前記バックボーンスプラインを前記デジタルインクファイルに関する追加情報と結合して、前記デジタルインクファイルの輪郭曲線を作成する手順、
前記輪郭曲線を表示手段に表示する手順
を前記コンピュータに実行させるためのプログラムをさらに記録したことを特徴とするコンピュータ読取可能な記録媒体。
【請求項１０】
請求項９に記載のコンピュータ読取可能な記録媒体において、前記輪郭曲線を表示する手順は、前記輪郭曲線を複数のストレートセグメントに分離し、該複数のストレートセグメントをレンダリングする手順を含むことを特徴とするコンピュータ読取可能な記録媒体。
【請求項１１】
請求項１０に記載のコンピュータ読取可能な記録媒体において、前記輪郭曲線を表示する手順は、さらに、前記ストレートセグメントの各々にアンチエイリアシング効果を適用する手順を含み、該アンチエイリアシング効果を適用する手順は、画像の中心よりも画像のエッジをより多くフィルタリングするアンチエイリアシングフィルタを含んでいることを特徴とするコンピュータ読取可能な記録媒体。
【請求項１２】
請求項１０または１１に記載のコンピュータ読取可能な記録媒体において、前記輪郭曲線を表示する手順は、さらに、前記ストレートセグメントの端に置かれているピクセルを平均化することによって前記ストレートセグメントの端を位置合わせする手順を含むことを特徴とするコンピュータ読取可能な記録媒体。
【請求項１３】
コンピュータシステムであって、
微分幾何学を使用してデジタルインクファイルのシャープポイントを算出する手段、
前記シャープポイント間のセグメントを曲線適合数学式によって定義する手段であって、前記セグメント内の２πを越える累積回転角を有するセグメントについては再分割し、かつ該再分割したセグメントを曲線適合数学式によって定義する手段、
前記シャープポイントに関する情報と前記曲線適合数学式を前記デジタルインクファイルのバックボーンスプラインとしてメモリにストアしておく手段、
前記バックボーンスプラインに前記デジタルインクファイルに関する追加情報を結合することで、前記デジタルインクファイルの輪郭曲線を作成する手段、
前記輪郭曲線を複数のストレートセグメントに分離し、該複数のストレートセグメントをレンダリングする手段、
画像の中心よりも画像のエッジをより多くフィルタリングするアンチエイリアシングフィルタを備えるディスプレイ上に前記輪郭曲線を表示する手段とを有し、
前記アンチエイリアシングフィルタは、画像の各前記スキャンラインに適用される複数のフィルタを用いるものであって、該複数のフィルタは、
画像の中心に隣接する画像をフィルタリングするように構成され、かつ第１しきい値でフィルタリングする少なくとも１つの中心フィルタと、
画像のエッジに隣接する画像をフィルタリングするように構成され、かつ前記第１しきい値よりも大きい第２しきい値でフィルタリングする少なくとも１つの外側フィルタと、
を含み、
前記複数のフィルタの各々は円錐断面を有し、かつ同じスキャンラインをもっているが、前記外側フィルタは減少係数だけサイズが減少していることを特徴とするコンピュータシステム。
【請求項１４】
請求項１３に記載のコンピュータシステムにおいて、前記アンチエイリアシングフィルタは、人間の知覚特性に基づいて画像をフィルタリングすることを特徴とするコンピュータシステム。
【請求項１５】
請求項１３に記載のコンピュータシステムにおいて、前記アンチエイリアシングフィルタは、GUPTA-SPROULLアルゴリズムを使用してフィルタリング効果を得ることを特徴とするコンピュータシステム。
【請求項１６】
請求項１３に記載のコンピュータシステムにおいて、前記第２しきい値は、人間の知覚特性に基づいてセットされることを特徴とするコンピュータシステム。
【請求項１７】
請求項１４または１６に記載のコンピュータシステムにおいて、前記人間の知覚特性は、コントラストセンシティビティを含むことを特徴とするコンピュータシステム。
【請求項１８】
請求項１３に記載のコンピュータシステムにおいて、前記中心フィルタの個数は１個であり、前記外側フィルタの個数は２個であり、これら外側フィルタは該外側フィルタの互いに向き合う側にあって、各々の外側フィルタが画像の異なるエッジに隣接するように配置されていることを特徴とするコンピュータシステム。
【請求項１９】
コンピュータに、
微分幾何学を使用してデジタルインクファイルのシャープポイントを算出する手順、
前記シャープポイント間のセグメントを曲線適合数学式によって定義する手順であって、前記セグメント内の２πを越える累積回転角を有するセグメントについては再分割し、かつ該再分割したセグメントを曲線適合数学式によって定義する手順、
前記シャープポイントに関する情報と前記曲線適合数学式を前記デジタルインクファイルのバックボーンスプラインとして記憶手段にストアしておく手順、
前記バックボーンスプラインを複数のラインセグメントに分離する手順、
前記ラインセグメントの各々について表示可能画像ファイルを生成するように該ラインセグメントの各々を変更する手順であって、各々の前記表示可能画像ファイルは、その画像ファイルを画像化するために定義されたピクセル値の集合を含む手順、
隣接する前記ラインセグメントがしきい値を超えているかどうかを判断する手順、
前記隣接するラインセグメントが前記しきい値を超えていれば、漏れているピクセル値を該隣接するラインセグメントに追加して、ラインセグメントの端を平滑化する手順、
を実行させるためのプログラムを記録したことを特徴とするコンピュータ読取可能な記録媒体。
【請求項２０】
請求項１９に記載のコンピュータ読取可能な記録媒体において、前記ラインセグメントの各々を変更する手順は、前記ストレートセグメントにアンチエイリアシング効果を適用する手順を含み、該アンチエイリアシング効果は、画像の中心よりも画像のエッジをより多くフィルタリングするアンチエイリアシングフィルタを含むことを特徴とするコンピュータ読取可能な記録媒体。
【請求項２１】
請求項１９に記載のコンピュータ読取可能な記録媒体において、前記隣接する前記ラインセグメントがしきい値を超えているかどうかを判断する手順は、前記ラインセグメント間に形成された角度が特定の角度を超えているかどうかを判断することを含むことを特徴とするコンピュータ読取可能な記録媒体。
【請求項２２】
請求項２０に記載のコンピュータ読取可能な記録媒体において、前記特定の角度は、４５度であることを特徴とするコンピュータ読取可能な記録媒体。
【請求項２３】
請求項１９に記載のコンピュータ読取可能な記録媒体において、前記ラインセグメントの端を平滑化する手順は、前記漏れているピクセルに隣接するピクセルのグレー値を平均化して、平均化されたグレー値を形成し、該平均化されたグレー値を前記漏れているピクセルに割り当てる手順を含むことを特徴とするコンピュータ読取可能な記録媒体。
【請求項２４】
請求項１９または２３に記載のコンピュータ読取可能な記録媒体において、２つの隣接する前記ラインセグメントの表示可能画像ファイルの各々は、同一ピクセルのピクセル値を含み、前記ラインセグメントの端を平滑化する手順は、前記同一ピクセルのピクセル値を平均化して、平均化されたグレー値を形成し、該平均化されたグレー値を同一ピクセルに割り当てる手順を含むことを特徴とするコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般的には、コンピュータに関し、さらに具体的には、デジタルインクを表現し、表示するためのコンピュータ読取可能媒体およびコンピュータシステムに関する。
【０００２】
【従来の技術】
手書き入力技法の一つである、デジタルインクテクノロジ (digital ink technology) によると、ユーザは、ハンドヘルドPC（パーソナルコンピュータ）または他のライティングタブレット (writing tablet) のタッチセンシティブスクリーン (touch-sensitive screen) 上で、スタイラス（stylus）や他のポインティングデバイスを使用してライティングやドローイングを行うことができるので、アプリケーションはキーボードを使用しなくても、ユーザからの入力を受け取ることができるという便利さがある。ユーザにとっては、デジタルインクテクノロジを使用してノートをとったり、スケッチをドローイングしたりすることは、ペーパ上にライティングまたはドローイングするのと非常によく似ている。
【０００３】
最新のデジタルインクテクノロジは、ユーザがデジタルインクテクノロジを使用して作成したインクトレース (ink trace) からさまざまな情報を抽出する能力を備えており、そのような情報としては、スタイラスのベクトル、座標、角度、および追加情報がある。デジタルインク情報はアプリケーションに入力することが可能で、ハンドライティング（手書き）認識といったように、多くの目的に使用することが可能になっている。また、デジタルインク情報は、ハンドライティングがどのように表示されるかを改善するためにも使用することができ、そのような例として、個々のエレメントの解像度、編集、平滑化 (smoothing)、および変更の向上がある。
【０００４】
デジタルインクテクノロジには１つの問題がある。それは、代表例として、ユーザのハンドライティングから生成されるファイルが大きいことである。一般的に、ファイルは、ユーザがライティング面に接触した個所のポイント（点）のシーケンスのほかに、上述したような追加デジタルインク情報から構成されている。ファイルのサイズが問題となる例として、デジタルインクファイルを伝送する必要がある場合に、非常に多数のデジタルインクファイルをストアする必要がある場合、あるいはディスプレイまたはハンドライティング認識といった目的のためにデジタルインクファイルを処理する必要がある場合がある。
【０００５】
デジタルインク情報を圧縮するための最新テクノロジが存在している。しかし、非常に大量の情報が圧縮過程で失われるのが代表的であるため、圧縮ファイルは、オリジナルインクトレースの形状情報を正確に表現していないことから、ディスプレイ（表示）や認識が低下する原因になっている。
【０００６】
デジタルインクテクノロジのもう１つの問題は、ディスプレイにある。オリジナルのインクトレース（ink trace)が使用される場合であっても、モニタや他のディスプレイデバイスの解像度に制約があるため、実際のインクトレースの表現を表示することが困難であることがよく起こっている。インクトレースを表しているポイントのシーケンスは、モニタ上のピクセルと正しく位置合わせ（アライメント）されないことがあり、現存のテクノロジによれば、モニタ上のビューが、あるアイテム（例えば、ポイントまたはラインの一部）のビジュアルプレゼンテーションを、ディスプレイ上のピクセルと位置合わせされていない位置に正確に表現できるようにする、機能が用意されていない。
【０００７】
多くの場合、最新ディスプレイソフトウェアはアンチエイリアシング効果 (antialiasing effects) を含んでいるため、グレーピクセル上に部分的にだけ置いておきたいアイテムの表現を表示しようとするとき、ディスプレイ上のピクセルに対して異なるグレーレベルが得られるようになっている。しかし、ラインや曲線がアンチエイリアシング手法を用いてレンダリングされるとき、これらのラインと曲線のレンダリングされた画像にリップル輪郭 (ripple contour) があるため、レンダリングされた形状は、異なる部分で幅が異なっている。幅が異なるのは、ラインまたは曲線に沿ったグレーレベル値に差異があるためである。この効果が最も顕著に現れるのは、レンダリングされるラインまたは曲線が相対的に長いときである。ほぼ水平または垂直であるラインでは、このリップル効果は特に顕著である。
【０００８】
【発明が解決しようとする課題】
本発明の目的は、従来技術での上述の課題を解決することを可能にした、デジタルインク情報を表現し、デジタルインクを表現し、表示するためのコンピュータ読取可能媒体およびコンピュータシステムを提供することにある。
【０００９】
【課題を解決するための手段】
本発明の一態様によれば、デジタルインクデータには、新規のフォーマットが用意されており、このフォーマットでは、デジタルインクデータは、インクトレースのオリジナルデジタルインクデータに比べて大幅に圧縮されているが、インクトレースの形状情報はそのまま残されている。この目的のために、本発明によれば、生インクデータ (raw ink data) を新規の圧縮インクデータフォーマットに変換する変換モジュール (conversion module) が用意されている。
【００１０】
本発明の一態様によれば、変換モジュールは、例えば、従来の平滑化フィルタ (smoothing filter) を使用して生インクデータをデノイズ（denoise：ノイズを除去すること）している。デノイズを行うと、特に、伝送からの不良データノイズや重複するデータ入力が除去される。デノイズを行った後、平滑化ラインのシャープポイント (sharp point) が見つけられる。これらのシャープポイントは、生データインクトレースのうち、直線（straight line)から最もはずれている（つまり、曲率が最大である）ポイント、またはそこで曲率が反転しているポイントを表している。次に、曲線適合 (curve-fitting) が使用され、隣接するシャープポイント間のラインセグメント (line segment) を定義している数学公式が生成される。この場合、インクトレースは、シャープポイントと、ラインセグメントの数学公式とを含むバックボーンスプライン (backbone spline) によって表されている。
【００１１】
バックボーンスプラインは、太さ (thickness) 情報を含んでいない。本発明の別の態様によれば、圧力や加速情報といった、太さ情報はバックボーンスプラインと結合され、オリジナルインクトレースの輪郭曲線 (contour curve) を表している圧縮インクファイルを得るようにしている。この輪郭曲線は、リアルタイムでバックボーンスプラインと結合することが可能であり、そこでは、輪郭曲線は圧縮データファイルとして保存される。別の方法として、バックボーンスプラインと太さ情報は保存しておくことができ、輪郭曲線はリアルタイムで生成されるようにすることも可能である（例えば、表示または認識のために必要時に生成する）。
【００１２】
本発明の一態様によれば、オリジナルインクトレースを近似的に表現している画像を圧縮ファイルから生成するディスプレイモジュールが用意されている。この目的のために、ディスプレイモジュールは、画像（例えば、輪郭曲線）を直線セグメントのシーケンスに分離する。次に、各直線セグメントを表示するために、新規のアンチエイリアシング方法を用いてピクセル集合が生成される。アンチエイリアシング方法によれば、スキャンラインの断面全体にわたって減少係数 (decreasing factor) が使用され、スキャンラインのエッジが中心よりも多くフィルタリングされるようにしている。このようにして、アンチエイリアシング方法によれば、各スキャンラインのピクセルグレーイングレベル (pixel graying level) が局所的に調整される。減少係数は、ライン中心からのピクセルの距離が増加すると、グレーイング（graying）レベルを実効的に減少するが、アンチエイリアシングが効果的になるように十分なグレーイングを保っている。このようにすると、レンダリングされる画像は、最新のアンチエイリアシング方法を用いてレンダリングされる画像よりも、リップル(ripple)が大幅に減少するという効果が得られる。
【００１３】
本発明の別の形態によれば、画像がアンチエイリアシングフィルタを使用して変更されたあと、隣接直線のピクセル集合は、平均化アルゴリズムを使用して位置合わせされる。生成され、再位置合わせされたピクセルは、そのあと、モニタなどのディスプレイデバイス上でレンダリングすることが可能になる。
【００１４】
本発明のその他の利点は、図面を参照して下述されている詳細説明の中で明らかにされている。
【００１５】
【発明の実施の形態】
以下では、本発明の種々の実施の形態について詳細に説明する。本発明の理解を容易にするために、説明の便宜上、特定の構成と詳細が示されている。しかし、この分野の精通者ならば理解されるように、本発明は、これらの具体的詳細がなくても実施することが可能である。さらに、周知の機能は、本発明を不明確にすることを避けるために、その説明が省略されているか、あるいは簡単に記述されている。
【００１６】
例示動作環境
図１は、本発明を実現することが可能である、適切なコンピューティングシステム環境１００の例を示す図である。このコンピューティングシステム環境１００は、適当なコンピューティング環境の一例にすぎず、本発明の使用または機能の有効範囲に関して、なんらの制限を意味するものではない。また、コンピューティング環境１００は、この例示動作環境に図示されているコンポーネントのどれとも、あるいはどの組み合わせとも、なんらかの依存関係または要件があるものと解釈してはならない。
【００１７】
本発明は、他の多数の汎用または特殊目的コンピューティングシステム環境または構成で動作することが可能である。本発明で使用するのに適している、周知のコンピューティングシステム、環境、および/または構成の例としては、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドまたはラップトップデバイス、マルチプロセッサシステム、マイクロコントローラベースのシステム、セットアップボックス (set top box)、プログラマブルコンシューマエレクトロニクス、ネットワークPC、ミニコンピュータ、メインフレームコンピュータ、上記システムまたはデバイスのいずれかを含んでいる分散型コンピューティング環境などがあるが、これらに限定されない。
【００１８】
本発明は、プログラムモジュールのように、コンピュータによって実行されるコンピュータ実行可能命令の広い意味で説明されている。一般的に、プログラムモジュールとしては、特定のタスクを実行し、あるいは特定の抽象データ型を実装しているルーチン、プログラム、オブジェクト、コンポーネント、データ構造などがある。さらに、本発明は、分散型コンピューティング環境で実施することも可能であり、そこでは、タスクは、通信ネットワークを通してリンクされたリモート処理デバイスによって実行されている。分散型コンピューティング環境では、プログラムモジュールは、メモリストレージデバイスを含む、ローカルとリモートの両方のコンピュータストレージ媒体に置いておくことができる。
【００１９】
図１を参照して説明すると、本発明を実現するための例示システムは、コンピュータ１１０の形体をした汎用コンピューティングデバイスを含んでいる。コンピュータ１１０のコンポーネントとしては、処理ユニット１２０、システムメモリ１３０、およびシステムメモリを含む種々のシステムコンポーネントを処理ユニット１２０に結合しているシステムバス１２１があるが、これらに限定されない。システムバス１２１は、数種タイプのバス構造のいずれかにすることが可能であり、その中には、種々のバスアーキテクチャのいずれかを採用したメモリバスまたはメモリコントローラ、ペリフェラル（周辺）バス、およびローカルバスが含まれている。このようなアーキテクチャの例としては、Industry Standard Architecture（ISA−業界標準アーキテクチャ）バス、Micro Channel Architecture（MCA −マイクロチャネルアーキテクチャ）バス、Enhanced ISA（EISA−拡張ISA）バス、Video Electronics Standards Association（VESA−ビデオエレクトロニクス標準協会）ローカルバス、およびMezzanineバスとも呼ばれているPeripheral Component Interconnects（PCI−ペリフェラルコンポーネント相互接続）バスがあるが、これらに限定されない。
【００２０】
コンピュータ１１０は、種々のコンピュータ読取可能媒体を装備しているのが代表的である。コンピュータ読取可能媒体としては、コンピュータ１１０によってアクセス可能な媒体であれば、どのような媒体も利用可能であり、その中には、揮発性媒体と不揮発性媒体、取り外し可能媒体と取り外し不能媒体が含まれている。コンピュータ読取可能媒体の例を挙げると、コンピュータストレージ媒体と通信媒体があるが、これらに限定されない。コンピュータストレージ媒体としては、コンピュータ読取可能命令、データ構造、プログラムモジュール、または他のデータなどの情報を格納しておく方法またはテクノロジで実現されている、揮発性と不揮発性の、取り外し可能および取り外し不能媒体がある。コンピュータストレージ媒体の中には、RAM、ROM、EEPROM、フラッシュメモリまたは他のメモリテクノロジ、CD-ROM、デジタルバーサタイルディスク (digital versatile disk - DVD) または他の光ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージまたは他の磁気ストレージデバイス、または必要とする情報をストアするために使用でき、コンピュータ１１０によってアクセスできる他の媒体が含まれている。通信媒体は、コンピュータ読取可能命令、データ構造、プログラムモジュール、または他のデータを、搬送波や他のトランスポートメカニズムなどの変調データ信号の形で具現化しているのが代表的あり、その中には、情報配信媒体が含まれている。ここで、「変調データ信号(modulated data signal)」という用語は、信号の中の情報をエンコード（符号化）するような形で、その特性の１つまたは２つ以上がセットまたは変更されている信号を意味している。通信媒体の例を挙げると、ワイヤド（有線）ネットワークや直接ワイヤドコネクションなどのワイヤド媒体と、音響、RF、赤外線および他のワイヤレス（無線）媒体などのワイヤレス媒体があるが、これらに限定されない。上記媒体の任意の組み合わせも、コンピュータ読取可能媒体の範囲に含まれるものである。
【００２１】
システムメモリ１３０には、リードオンリメモリ (read only memory - ROM) １３１とランダムアクセスメモリ (random access memory - RAM) １３２などの、揮発性および/または不揮発性メモリの形体をしたコンピュータ読取可能媒体が含まれている。スタートアップ時のときのように、コンピュータ１１０内のエレメント間で情報を転送するのを支援する基本ルーチンで構成された基本入出力システム (basic input/output system - BIOS) １３３は、ROM １３１に格納されているのが代表的である。RAM １３２には、処理ユニット１２０が即時にアクセス可能である、および/または処理ユニット１２０によって現在操作の対象になっているデータおよび/またはプログラムモジュールが置かれているのが代表的である。図１には、オペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６、およびプログラムデータ１３７が示されているが、これらは例示であって、これらに限定されるものではない。
【００２２】
コンピュータ１１０は、さらに、他の取り外し可能/取り外し不能の揮発性/不揮発性コンピュータストレージ媒体を装備することも可能である。単なる例示であるが、図１は、取り外し不能の不揮発性磁気媒体との間で読み書きを行うハードディスクドライブ１４０、取り外し可能の不揮発性磁気ディスク１５２との間で読み書きを行う磁気ディスクドライブ１５１、およびCD-ROMや他の光媒体などの、取り外し可能の不揮発性光ディスク１５６との間で読み書きを行う光ディスクドライブ１５３を示している。例示動作環境で使用できる、他の取り外し可能/取り外し不能の揮発性/不揮発性コンピュータストレージ媒体として、磁気テープカセット、フラッシュメモリカード、デジタルバーサタイルディスク、デジタルビデオテープ、ソリッドステートRAM、ソリッドステートROMなどがあるが、これらに限定されない。ハードディスクドライブ１４１は、インタフェース１４０のような、取り外し不能メモリインタフェースを通してシステムバス１２１に接続されているのが代表的であり、磁気ディスクドライブ１５１と光ディスクドライブ１５５は、インタフェース１５０のような、取り外し可能メモリインタフェースによってシステムバス１２１に接続されているのが代表的である。
【００２３】
上述し、図１に図示されているドライブとそれぞれに関連するコンピュータストレージ媒体は、コンピュータ読取可能命令、データ構造、プログラムモジュール、および他のデータをコンピュータ１３０のために格納している。図１には、例えば、ハードディスクドライブ１４１は、オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６、およびプログラムデータ１４７をストアしているものとして示されている。なお、これらのコンポーネントは、オペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６、およびプログラムデータ１３７と同じにすることも、それらとは異なったものにすることも可能である。ここで、オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６、およびプログラムデータ１４７に別の番号が付けられているのは、少なくとも、これらは異なるコピーであることを示すためである。ユーザは、キーボード１６２、および一般にマウス、トラックボールまたはタッチパッドと呼ばれているポインティングデバイス１６１などの、入力デバイスを通してコマンドと情報をコンピュータ１１０に入力することができる。他の入力デバイス（図示せず）としては、マイクロホン、ジョイスティック、ゲームパッド、サテライトディッシュ、スキャナ、ハンドヘルドPCまたは他のライティングタブレットのタッチセンシティブスクリーンなどがある。上記および他の入力デバイスは、システムバスに結合されたユーザ入力インタフェース１６０を通して処理ユニット１２０に接続されていることが多いが、パラレルポート、ゲームポートまたはユニバーサルシリアルバス (universal serial bus - USB) などの、他のインタフェースとバス構造によって接続することも可能である。モニタ１９１や他のタイプのディスプレイデバイスも、ビデオインタフェース１９０などのインタフェースを介してシステムバス１２１に接続されている。モニタのほかに、コンピュータは、スピーカ１９７やプリンタ１９６などの、他のペリフェラル（周辺）出力デバイスを装備することも可能であり、これらのデバイスは、出力ペリフェラルインタフェース１９０を通して接続可能になっている。
【００２４】
コンピュータ１１０は、リモートコンピュータ１８０などの、１つまたは２つ以上のリモートコンピュータとの論理コネクションを使用するネットワーキング環境で動作することができる。リモートコンピュータ１８０は、パーソナルコンピュータ、サーバ、ルータ、ネットワークPC、ピアデバイスまたは他の共通ネットワークノードにすることが可能であり、図１には、メモリストレージデバイス１８１だけが示されているが、コンピュータ１１０に関して上述したエレメントの多くまたは全部を装備しているのが代表的である。図１に示す論理コネクションとしては、ローカルエリアネットワーク (local area network - LAN) １７１と広域ネットワーク (wide area network - WAN) １７３があるが、他のネットワークを含めることも可能である。このようなネットワーキング環境は、オフィス、企業内 (enterprise-wide) コンピュータネットワーク、イントラネット (intranet)、およびインターネット (the Internet) で普及している。
【００２５】
LANネットワーキング環境で使用されるときは、コンピュータ１１０は、ネットワークインタフェースまたはアダプタ１７０を通してLAN １７１に接続されている。WANネットワーキング環境で使用されるときは、コンピュータ１１０は、インターネットなどの、WAN １７３上のコミュニケーションを確立するためのモデム１７２や他の手段を装備しているのが代表的である。モデム１７２は内蔵型と外付け型があるが、どちらも、ユーザ入力インタフェース１６０や他の該当メカニズムを介してシステムバス１２１に接続することが可能になっている。
【００２６】
ネットワーキング環境では、コンピュータ１１０に関して上述したプログラムモジュールまたはその一部は、リモートメモリストレージデバイスに格納しておくことが可能である。図１は、リモートアプリケーションプログラム１８５がメモリデバイス１８１に置かれているものとして示しているが、これは単なる例示であり、これに限定されるものではない。当然に理解されるように、図示のネットワークコネクションは例示であり、コンピュータ間の通信リンクを確立する他の手段を使用することも可能である。
【００２７】
デジタルインクを表現し、表示するシステム
代表例として、タッチセンシティブスクリーンまたはタブレット上でライティングを行っているユーザは、スタイラスまたは他のデジタルインクジェネレータを使用してデジタルインク情報を生成している。一般的に、デジタルインクテクノロジでは、スタイラス、マウス、または他のポインタの動きに関する情報は、スタイラスの計算されたベクトル情報、圧力、タイミング、ストローク、角度、イタリックとボールドのステートなどの、拡張情報と共にストアされ、および/または処理されている。デジタルインクフォーマットの種類はさまざまであり、そのフォーマットがポインタの動きと一緒にストアし、または処理できる追加情報は、アプリケーションが異なると変化している。
【００２８】
要約して説明すると、本発明の一形態は、デジタルインクファイルの圧縮表現を作成するための方法とシステムを目的としている。この圧縮インクファイルは、ユーザが行ったオリジナルインクトレースを近似的に表しているが、オリジナルインクデータに比べて大幅に圧縮されている。さらに、本発明は、圧縮デジタルインクファイルなどの、デジタルインクファイルを表示するためのシステムと方法を目的としている。表示される表現は、ユーザが行ったオリジナルインクトレースを近似的に表している。
【００２９】
次に図面を参照して説明すると、図２は、本発明の一形態に従ってデジタルインクファイルを圧縮するためのシステム２００のアーキテクチャを示す概要図である。システム２００は、デジタルインクレシーバ (digital ink receiver) ２０４を備えたコンピュータ２０２（例えば、コンピュータ１１０）を含んでいる。デジタルインクレシーバ２０４は、ユーザによるライティングの動きによって生成された生データ (raw data) を受け取り、必要ならばそのデータを処理し、対応する該当データを、オペレーティングシステムやアプリケーションなどの該当ソフトウェアに転送する。以上のように、デジタルインクレシーバ２０４を使用すると、ユーザは、キーボードを使用しなくても、ライティングタブレット (writing tablet) などのデジタルインクジェネレータを利用して、情報をコンピュータに入力することができる。
【００３０】
本発明の一形態によれば、デジタルインクレシーバ２０４は圧縮モジュール２０６を含んでいるか、さもなければ、この圧縮モジュールと関連付けられており、この圧縮モジュールは、以下で詳しく説明するように、オリジナルインクデータを圧縮インクファイルに変換するように構成されている。デジタルインクレシーバ２０４と圧縮モジュール２０６は、シングルPC（例えば、パーソナルコンピュータ２０２）上に実装させることができるが、圧縮モジュール２０６は、デジタルインクレシーバ２０４とは別のマシン上に実装させることも可能である。さらに、これらモジュールの種々機能は、シングルデバイスによって実行させることも、複数のデバイスによって実行させることも可能である。
【００３１】
圧縮モジュール２０６は、レコグナイザ(recognizer：認識器) ２０８および/またはディスプレイ生成メカニズム２０９に接続することが可能であり、これらの各々は、コンピュータ２０２と統合化することも、別にすることも可能である。これらのコンポーネントの一方または両方、またはコンピュータ２０２のオペレーティングシステムを含む他のソフトウェアは、圧縮モジュール２０６の出力を利用することができる。本発明の形態によれば、以下で詳しく説明するように、圧縮モジュール２０６によって生成される圧縮デジタルインクファイルなどの、デジタル画像ファイルのディスプレイ情報を生成するためのディスプレイモジュール２１０が用意されている。ディスプレイモジュール２１０は、ディスプレイ生成メカニズム２０９のような、モニタまたはディスプレイにディスプレイ情報を転送することができる。ディスプレイモジュール２１０と圧縮モジュール２０６は、シングルPC（例えば、パーソナルコンピュータ２０２）上に実装させることができるが、圧縮モジュール２０６は、ディスプレイモジュール２１０とは別のマシン上に実装させることも可能である。さらに、これらの種々機能は、シングルデバイスによって実行させることも、複数のデバイスによって実行させることも可能である。
【００３２】
コンピュータ２０２は、コネクション２１２を通してデジタルインクジェネレータ２２０に接続されており、このデジタルインクジェネレータは、例えば、ユーザがライティングの動きを行うと、デジタルインクを生成するメカニズムになっている。デジタルインクジェネレータ２２０は、例えば、スタイラスを通してライティングの入力を受信するライティングタブレット (writing tablet) にすることも、ユーザがライティングの動きを行うと、デジタルインク情報を生成するコンポーネント（例えば、加速度計）を内蔵しているペンにすることもできる。別の例として、デジタルインクは、デジタル画像の曲線をトレースした結果として生成することもできる。デジタルインクデータは、コネクション２１２を経由してコンピュータ２０２に送信される。
【００３３】
コネクション２１２は、ハードワイヤド（有線）にすることも、ワイヤレス（無線）にすることも可能である（ワイヤレスのときは、コネクションは概念的なものである。例えば、赤外線の見通し線 (line-of-sight)、FM送信範囲内、など）。いくつかの例を挙げると、コンピュータ２０２は、デジタルインクジェネレータ２２０から離れた個所に置いておくことが可能であり、デジタルインクジェネレータ２２０からコンピュータへのデジタルインクの送信は、ワイヤレス伝送、ローカルエリアネットワーク（例えば、LAN １７１）、広域ネットワーク（例えば、WAN １７３）、インターネット (the Internet) 経由で行うことも、別のネットワークまたは類似のコネクション経由で行うことも可能である。別の方法として、デジタルインク情報は、デジタルインクジェネレータ内のメモリにストアしておき、あとでコンピュータ２０２にダウンロードするようにすることもできる。さらに、デジタルインクレシーバ２０４、圧縮モジュール２０６、およびディスプレイモジュールの機能の一部または全部は、デジタルインクジェネレータに持たせることも可能であるが、実際には、そのように設計すると、メカニズムが煩雑になるため、快適なデジタルインク入力が得られないことになる。
【００３４】
図３は、本発明の一形態による圧縮モジュール２０６のアーキテクチャを示すブロック図である。圧縮モジュール２０６は、平滑化フィルタ (smoothing filter) ３０２、シャープポイントコンポーネント (sharp point component)３０４、曲線適合コンポーネント (curve-fitting component)３０６、および輪郭曲線コンポーネント (contour curve component)３０８を含んでいる。輪郭曲線コンポーネント３０８は、１つまたは２つ以上のデータベース３１０と関連付けられている（なお、図には１つだけが示されている）。これらのコンポーネントの各々の機能と動作は、以下で説明する。
【００３５】
オリジナルデジタルインクの圧縮
図４は、本発明の一形態に従ってデジタルインク情報を圧縮する（例えば、圧縮モジュール２０６を通して）ためのプロセスを示す全体概要図である。ステップ４００から始まって、ユーザは、デジタルインクジェネレータ２２０を使用してデジタルインクを生成する。一般的に、図５に示すように、オリジナルデジタルインクデータは、ユーザが行ったインクトレース５０４を表している一連のポイント(点)を含んでいる。タッチセンシティブスクリーンが使用されるときは、スタイラスの計算されたベクトル情報、圧力、タイミング、ストローク、角度などの追加デジタルインク情報が、タッチセンシティブスクリーンまたはタブレットによって生成されることがある。ステップ４０２では、ポイント５０２と追加デジタルインク情報（存在する場合）は、コネクション２１２を通してコンピュータ２０２に転送され、デジタルインクレシーバ２０４によって受信される。
【００３６】
ステップ４０４では、一連のポイント５０２のデノイズ(denosing：ノイズ除去)（例えば、圧縮モジュール２０６の平滑化フィルタ３００による）が行われ、大量のデータノイズが除去される。ノイズを除去するには、種々のデノイズ方法を使用できるが、好ましくは、有用であるかもしれない、余りに多数のディテールが除去されないようにする注意が必要である。曲線をデノイズする単純な方法は、ローパスフィルタを使用して曲線をフィルタリングすることである。このようなシステムはノイズを除去するのに有効な働きをするが、オリジナルポイントの有用なディテールが一部失われるおそれがある。もっと改善された平滑化ソリューションでは、Ann BengtssonおよびJan-Olof Eklundh著「マルチスケール輪郭近似化による形状表現(Shape Representation by Multi-scale Contour Approximation)」、IEEE Transaction on Pattern Analysis and Machine Intelligence, 1991に記載されているような、マルチスケール曲率空間理論 (theory of multi-scale curvature space) が利用されているが、この方法は複雑で、低速であるため、利用できる以上の処理能力を必要としている。これら２方法を改善した折衷方法では、一連のオリジナルシーケンスを特定のスケールに再サンプリングしている。再サンプリングは、画像データを別の解像度スケールに変換することを基本にしている。再サンプリングのために使用されるスケールが大きくなると（解像度が低くなると）、失われるオリジナルインクトレースのディテールが多くなり、他方、使用されるスケールが小さくなると（解像度が高くなると）、残されるディテールが多くなる。他のデノイズ手法を使用することも可能である。
【００３７】
ステップ４０６では、デノイズされたデータ曲線のシャープポイント (sharp point) が見つけられる（例えば、圧縮モジュール２０６のシャープポイントコンポーネント３０２によって）。シャープポイントとは、曲線の重要な形状情報を含んでいるポイントであり、オリジナルインクトレースのディテールの多くを残しておくのに役立っている。要約して説明すると、本発明の一形態によれば、平滑化データ曲線 (smoothed data curve) のシャープポイントを見つけることは、曲率が最も顕著である個所、または曲率が向きを変えている個所を、平滑化曲線から見つけることによって行われている。向きの変化は尖点 (cusp) であることもあれば、曲線が反時計回りの曲率から時計回りの曲率に、またはその逆に変化する位置であることもある。
【００３８】
シャープポイントを見つけるために、デノイズされた曲線の接線と曲率が、微分幾何学 (Differential Geometry) を使用して、平滑化曲線の各ポイントについて計算される。尖点が存在するときは、尖点の曲率は無限になる。微分幾何学を使用すると、曲率のすべての局所末端 (local extreme) とすべてのゼロ交差ポイント (zero-crossing point) を見つけることができる。曲率の局所末端は、曲線がシャープに回転している個所のクリティカルポイント（critical point：臨界点）であり、曲率のゼロ交差ポイントは、画像の回転方向が変化している（反時計回り方向から時計回り方向へ、またはその逆へ）個所のクリティカルポイントである。
【００３９】
シャープポイントの個所が見つかると、ラインは、ステップ４０８で、シャープポイント間のセグメントに分割される。ステップ４１０では、セグメントは曲線適合 (curve-fit) される（曲線適合コンポーネント３０６によって）。一般的に、曲線適合では、数学式で曲線を定義することが行われる。セグメントを曲線適合するプロセスは、以下に、図７を参照して説明されている。
【００４０】
曲線セグメントとシャープポイントの表現は、図６に示すように、曲線のバックボーンスプライン (backbone spline) を形成している。シャープポイント６０２はそのまま残され、シャープポイント間のセグメント６０４は、曲線適合数学式によって定義される。この情報は、オリジナルデジタルインクファイル内のポイントのシーケンスよりも重要度が劣るが、オリジナルインクトレースの曲率を近似的に表している。
【００４１】
ステップ４１２では、輪郭曲線が、太さ情報などの追加デジタルインク情報とバックボーンスプライン６００を使用して生成される（例えば、輪郭曲線コンポーネント３０８によって）。輪郭曲線は、ユーザが行ったオリジナルインクトレースを表現したものであり、その中には、太さや濃淡などの追加情報が含まれている。太さ情報（利用可能であれば、圧力センサによって生成されたもの）を使用すると、輪郭曲線コンポーネント３０８は、指示や他の情報をソフトウェアまたはディスプレイ生成メカニズム２０９に与えて、インクトレースをもっと太くするように太さ情報が指示している個所でデジタルインクを増幅するように（例えば、ビットマップに追加ビットを加えることにより、またはアプリケーションでラインの太さを増加することにより）ソフトウェアまたはディスプレイ生成メカニズムに指示することができるが、別の方法として、インクトレースをもっと細くするように太さ情報が指示している個所で細いラインを指示することも可能である。追加インク情報を使用すると、太さ情報に従ってラインをもっと黒くするといったように、他の方法でバックボーンスプラインを変更することができる。
【００４２】
輪郭曲線は、リアルタイムで生成することが可能であり（つまり、圧縮モジュールによって受信されたとき）、即時に使用することも、データベース３１０にストアしておいて、必要時に取り出すことも可能である。別の方法として、太さ情報や他の追加デジタル情報は、バックボーンスプライン６００と一緒にデータベース３１０にストアしておき、これらの２つを必要時に（例えば、インクトレースの表示が要求されたとき）結合することも可能である。後者の方法によると、リソースがそのまま残されるので、別のインクトレースのバックボーンスプラインを生成するといったように、他のタスクのために処理能力を利用することが可能になる。必要ならば、追加のデジタルインク情報は、バックボーンスプライン６００とは別のデータベースにストアしておくことができるので、必要時にアクセスすることができる。
【００４３】
図７は、本発明の一形態に従ってバックボーンスプライン６００のラインセグメント６０４を曲線適合するためのプロセスを示す全体概要図である。ステップ７００から始まって、隣接するシャープポイント６０２間のラインセグメントに対する曲線データが取り出される。曲線データとしては、例えば、シャープポイント６０２間のエリアを平滑化するときに生成された平滑化ライン情報がある。
【００４４】
ステップ７０２では、ラインセグメントの累積回転角度 (accumulating turn angle) が2πよりも大であるかどうかの判断が行われる。累積回転角度が2πよりも大であれば、少なくとも１つの円が存在するので、これを数学式で表すことが困難になる。円が検出されると、ステップ７０２はステップ７０４へブランチし、そこで、セグメントは、例えば、２つのサブセグメントに分割される。次に、プロセスはループしてステップ７００に戻り、そこで、サブセグメントの曲線データが取り出される。
【００４５】
回転角度が2πよりも大でなければ、ステップ７０２はステップ７０６へブランチし、そこで、セグメントまたはサブセグメントの曲線適合が行われる。曲線適合は、曲線群を使用してラインの曲率を近似化する数学的手法である。曲線群の中の各曲線は、数学式によって解析的に表されている。
【００４６】
現在では、曲線適合のためにいくつかの曲線群が使用されている。１つの例として、パラメトリック区分三次曲線群 (parametric piece-wise-cubic curves) が使用されている。この曲線群は、数学理論とコンピュータグラフィックス分野で幅広く使用されている。各パラメトリック区分三次曲線は、次式によって定義されている。
【００４７】
【数１】
0004162934.tif 000002
【００４８】
上式は、基底関数φj = tj をもっている。ただし、j =＜0,1,2,3＞ である。ほかにも、パラメトリック区分三次曲線を表すために２つの基底関数が使用されている。１つは、Bernstein多項式φj = C3jtj(1-t)3-j を基底関数として使用している。この基底関数では、三次曲線は、三次Bezier曲線として表されている。Bezier曲線は、曲線の形状を定義する４つのコントロールポイントをもっている。Bezier曲線またはスプラインを定義するためのアルゴリズムは、いくつかが曲率分野で知られている。しかし、一般的には、度数nのBezierスプラインは、Bezierコントロールポリゴン (control polygon) を定義する (n+1) ポイントによって定義された多項式補間曲線 (polynomial interpolated curve) である。Bezier補間で使用される補間基底関数は Bernstein多項式であり、度数nのとき次のように定義されている。
【００４９】
【数２】
0004162934.tif 000003
【００５０】
パラメータt は、[0, 1]の範囲にあり、0 からnまでの各iについてn+1個の多項式が定義されている。
【００５１】
従って、Bezierスプラインは、インターバル[0, 1]にわたって次のように定義されている。
【００５２】
【数３】
0004162934.tif 000004
【００５３】
上記において、bi は、ポリゴンを定義しているコントロールポイントである。
【００５４】
パラメトリック区分曲線を表すために使用できるもつ１つの基底関数は、Hermit多項式である。
【００５５】
【数４】
0004162934.tif 000005
【００５６】
Hermit多項式は、f(t) = a0φ0 + a1φ1 + a2φ2 + a3φ3 の形式になっている。パラメータaj は、a0 = f(0), a1 = f'(0), a2 = f(1), a3 = f'(1) を意味する数学式になっている。三次Hermit多項式は、数学的補間と曲線適合で使用すると便利である。
【００５７】
使用できる曲線適合曲線群はほかにもいくつかあるが、本件出願人によって分かったことは、曲線群の理論が完全であるため、パラメトリック区分三次曲線が特に有効な働きをすることである。さらに、曲線群を定義するために使用されるアルゴリズムは、特に正確である。
【００５８】
本発明の別の形態によれば、パラメトリック区分三次曲線を使用するとき、セグメントの端のシャープポイントは、セグメントの最初と最後のBezierコントロールポイントになっている。シャープポイントの位置と接線は既知になっている。これらの境界の限界を条件として、最小二乗法 (least squares method) を使用すると、全区分三次曲線 (whole piecewise-cubic curve) が得られる。サブセグメントが使用されるときは、そのサブセグメントのエンドポイントおよび対応する接線を計算することができる。
【００５９】
セグメントまたはサブセグメントが曲線適合された後、プロセスはステップ７０８へ進み、そこで、曲線適合の誤差が、定義されたしきい値以上であるかどうかの判断が行われる。そうであれば、ステップ７０８はブランチしてステップ７０４へ戻り、そこで、セグメントまたはサブセグメントは、例えば、２つのサブセグメントに細分割される。この方法によると、困難な曲線を処理しなくても、正確な曲線適合を簡単に行うことができる。一部の困難な曲線では、単一区分三次曲線適合は、セグメントを正しく定義できないため、別の処理が必要になる場合がある。Plass他著の論文「区分パラメトリック三次曲線の曲線適合(Curve-Fitting with Piecewise Cubics)」(Computer Graphics, Volume 17, Number 3, July, 1983) の中で、著者は、曲線適合を行っても、良好な曲線描写が正しく得られないようなセグメントを細分割するためにダイナミックプログラミングを使用することを提案している。この方法は本発明で使用することも可能であり、セグメントを半分に分割するだけの場合よりも、より正確な描写が得られるが、上記論文で提案されているダイナミックプログラミングによると、本発明で提案しているセグメントの細分割の場合よりも、消費時間が増加し、要求される計算が複雑化している。さらに、本発明によれば、回転角度が2πよりも大であるセグメントでは曲線適合を行わないので、ダイナミックプログラミングを使用する方法よりも、消費する処理能力と時間が少なくなっている。この時間は、リアルタイムでやりとりする環境では非常に貴重である。
【００６０】
曲線適合の誤差が、定義されたしきい値以下であれば、ステップ７０８はステップ７１０へブランチし、そこで、バックボーンスプラインのすべてのセグメントまたはサブセグメントが曲線適合されたかどうかの判断が行われる。そうでなければ、プロセスはループしてステップ７００に戻り、そこで、次のセグメントの曲線情報が取り出される。そうであれば、プロセスは終了する。
【００６１】
本発明の圧縮方法によれば、オリジナルインクデータ情報よりも大幅に小さい圧縮インクファイルが生成されるという利点が得られる。さらに、プロセスで使用される処理時間は、従来の圧縮手法に比べて大幅に低減されるという利点がある。
【００６２】
デジタルインクファイルの表示
図８は、本発明の一形態によるディスプレイモジュール２１０のアーキテクチャを示すブロック図である。ディスプレイモジュール２１０は、分離コンポーネント (separation component) ８０２、アンチエイリアシングコンポーネント (antialiasing component) ８０４、および端平均化コンポーネント (end-averaging component) ８０６を含んでいる。これらのコンポーネントの各々の機能と動作は以下に説明されている。
【００６３】
図９は、本発明の一形態に従ってデジタルインク情報を表示する（例えば、ディスプレイモジュール２１０を通して）ためのプロセスを示す全体概要図である。ステップ９００から始まって、輪郭曲線は複数のセグメントに分割され（例えば、分離コンポーネント８０２によって）、その各々は直線になっている。これを行うために、輪郭曲線は、例えば、Bezier曲線のde Casteljau関数に由来するアルゴリズムを使用して、いくつかの直線セグメントに分離することができる。de Casteljau関数は公知であるが、理解を容易にするために簡単に説明することにする。de Casteljau関数は、コントロールポリゴンが与えられているとき、任意の値がtであるときのBezier曲線上に位置するポイントを計算するリカーシブアルゴリズム (recursive algorithm) であり、Bernstein多項式（上述した）を使用しないでBezierスプラインを計算し、ドローイングするために使用することができる。このアルゴリズムは、ステップごとに、直前のステップで作成されたポリゴンよりも１だけ少ない度数のポリゴンを作成し、最後に１つのポイントだけが曲線上に残るまで続けていく。各ステップのポリゴン頂点 (polygon vertex) は、値をt（パラメータ）として直前のステップからのポリゴンの２連続頂点を線形的に補間することによって定義されている。
【００６４】
【数５】
0004162934.tif 000006
【００６５】
一般的に、この関数を使用すると、輪郭曲線はいくつかのセグメント（例えば、64個）に分割され、これらのセグメントは、輪郭曲線のもっとストレートになった部分では長さが長くなり、曲率がもっと大きい曲線部分では長さが短くなっている。このようにすると、ストレートセグメントは輪郭曲線の実際の形状を近似的に表すことができ、これらセグメントの各々を表示するための情報の計算が容易化されることになる。
【００６６】
ステップ９０２では、直線セグメントは、以下に詳しく説明されているように、改善されたアンチエイリアシングフィルタを使用して、アンチエイリアシングされて（例えば、アンチエイリアシングコンポーネント８０４によって）変更される。このプロセスにより、アンチエイリアシングされたピクセルが生成される。アンチエイリアシングされたピクセルは、ステップ９０４で隣接直線の端で位置合わせされるので、その結果の画像は、図１６と図１７を参照して以下で説明するように、平滑化されたように見えることになる。アンチエイリアシングされ、位置合わされたピクセルは、ステップ９０６で、例えば、ディスプレイ生成メカニズム２０９から表示される。
【００６７】
本発明のアンチエイリアシング方法の理解を容易にするために、従来からアンチエイリアシングのために使用されている、いくつかの一般的方法について説明することにする。一般的に、図１０に示すように、ライン画像１０００には、アンチエイリアシングが行われる前は、矩形形状のスライス (slice) がある。アンチエイリアシングを行わないと、その全部または一部が矩形スライスの下に置かれているピクセルがラインの画像でレンダリングされる。エイリアシングとは、デジタル化期間に画像のエッジに沿ってステアケースステップ（「ジャギー(jaggies)」とも呼ばれる）を生成するようなアンダサンプリング (undersampling) 効果のことであり、この効果が発生するのは、ピクセルのエリアが四角であるため、画像の傾斜したエッジと正確に位置合わせされていないためである。アンチエイリアシングを行うと、エッジが平滑化されたように見えるエッジが表示されることになる。簡単に説明すると、アンチエイリアシングを行うと、矩形形状のエッジ上にあるピクセルがフィルタリングされるので、部分的に矩形スライスの下に置かれているピクセルは部分的に明るくなる（またはグレーになる）。このようにすると、画像のエッジは、平滑化されたように見える。
【００６８】
アンチエイリアシングのフィルタリングプロセスは、ある種のフィルタ関数による画像信号のコンボルーション (convolution) によって表される。このプロセスは、次の積分で表すことができる。
【００６９】
【数６】
0004162934.tif 000007
【００７０】
上記において、Sは、サンプリングされた結果の画像であり、サンプルポイント (x, y) におけるピクセルで構成されている。h(x, y) はアンチエイリアシングフィルタであり、式 S(x, y) はアンチエイリアシング積分と呼ばれている。実際には、アンチエイリアシング積分をシミュレートするアルゴリズムには、２種類ある。１つはオーバサンプリング (over-sampling)、もう１つはプレフィルタリング (pre-filtering) である。一般的には、プレフィルタリングを行うと、ピクセルのグレーレベルは、ラインのエッジがピクセルのエリア全体にわたっている量に比例するように調整される。オーバサンプリングでは、ピクセルごとに２つ以上のサンプルが使用される。基本的考え方は、ディスプレイデバイスが処理できる以上の高解像度の画像が生成され、大きくなった画像のピクセルは、ディスプレイデバイスの解像度に合致するシングルのグレーピクセル (grayed pixel) が得られるように平均化されることである。どちらのタイプのアンチエイリアシングフィルタも、現行グラフィックスシステムで幅広く利用されている。
【００７１】
プレフィルタリングとオーバサンプリングのプロセスによると、レンダリングされた画像の輪郭上のジャギーは大幅に除去されるので、はるかに審美的な結果が得られることになる。しかし、ラインと曲線のレンダリングでアンチエイリアシング手法が使用されるときは、一定断面をもつアイテムの輪郭は、その長さに沿って幅が異なっているように見えるので、ラインはリップルした輪郭をもつことになる。このリップル輪郭現象は、ラインまたは曲線に沿って使用されるグレーレベルが異なっていると発生する。異なるグレーレベルが使用されるのは、従来のアンチエイリアシング方法では、ピクセルがグレーにされる量が画像を取り巻くピクセルの中心から画像化されるラインまでの距離に正比例するからである。この距離が変化すると、レンダリングされるラインに沿ったロケーションでの総グレー化 (total graying) が変化する。ラインに沿ったグレーレベルが変化すると、ラインはリップルした外観になる。
【００７２】
リップルが最も顕著に現れるのは、レンダリングされるラインまたは曲線が非常に長いときである。大部分の水平ラインと垂直ラインは、これらのライン（水平または垂直）が画像を表示するピクセルと正確に位置合わせされていないと、この効果を示している。ジャギーよりも改善されていると思われるが、リップル輪郭は、レンダリングされる画像のビジュアル効果を相殺することにもなる。非常に大きなフォントをレンダリングする場合は、このアンティファクト (antifact) があると、アンチエイリアシングされたエッジが依然として不規則のように見えるため、アンチエイリアシングで行ったことが無駄になってしまう。
【００７３】
リップル輪郭を生成させるためには、２つ係数が必要である。１つは、ディスプレイデバイスの解像度が有限であることであり、もう１つは、どこでも同じフィルタを使用してアンチエイリアシングが行われることである。これらの２係数は、理論的には、どのアンチエイリアシング方法にも内在しているので、オーバサンプリングを使用するか、プレフィルタリングを使用するかは重要でなく、レンダリングされた画像は依然としてリップル効果を含んでいる。アンチエイリアシングをもっと分かりやすく説明するために、ラインのレンダリングについて説明することにする。
【００７４】
理論的には、幅がゼロである理想的ラインは、２次元平面上のドットの列になっており、これは、数学的に、デルタ (delta) 関数で表されている。
【００７５】
【数７】
0004162934.tif 000008
【００７６】
ラインのアンチエイリアシング画像は、ライン上の各ドットのアンチエイリアシング画像の総和である。アンチエイリアシング積分Sを使用すると、デルタ関数に対するフィルタの応答は、(a, b) の中心にあるドットについて、次の積分で求めることができる。
【００７７】
【数８】
0004162934.tif 000009
【００７８】
デルタ関数のプロパティによると、この積分の結果はh(x -a, y - b)である。単純化と効率化のために、hは中心対称関数 (center symmetric function) であるので、その結果は、さらに次式に変えることができる。
【００７９】
【数９】
0004162934.tif 000010
【００８０】
このフィルタがライン上のすべてのドットに対して使用されると、ピクセル (x, y) でサンプリングされた画像の値は、ピクセルからドット (a, b) までの距離（以下、"d" と称す）だけで決まることになる。従って、サンプリングされた画像のグレーレベルは、フィルタフォームがライン上の全ポイントで一定であれば、dだけに依存することになる。
【００８１】
理想的ライン画像は、スキャン変換アルゴリズム (scan conversion algorithm)を使用してサンプリングされる。ラインの関数が与えられているとき、スキャン変換アルゴリズムは、ラインからレンダリングの候補となっているピクセルまでの距離を計算し、最寄りのピクセルを選択する。あるピクセルがスキャン変換アルゴリズムによって次にレンダリングされるものと判断されると、そのピクセルの中心から、同じx（またはy）座標をもつライン上のポイントまでの（垂直または水平）距離dは、そのyまたはx座標間の差分によって計算される。
【００８２】
理想的ラインでは、エネルギはどの個所でも等しくなっている。このことは、サンプリングされた画像が各スキャンラインに沿って等しい総和値をもっていることを意味する。解像度が無限であれば、各フィルタの中心は、ライン上のポイントに正確に位置していることになるので、ライン上のすべてのポイントはサンプル値がh(0) となり、相互に等しいので、均一幅の画像が得られることになる。
【００８３】
解像度が有限のときは、サンプリング値はdによって決まり、dは変化を受けることになるので、ラインの幅は変化する。単純なデジタル微分アナライザ (digital differential analyzer - DDA) スキャン変換アルゴリズムでは、dの値は、次式のように正方向微分 (forward differencing) によって計算することができる。
dn+1=dn+k.     round(dn+k)=round(dn)  ならば
dn+1=dn+k−1    そうでなければ  ｄ０＝０
kは、次式によって計算されたラインの傾斜 (slant) であり、
【００８４】
【数１０】
0004162934.tif 000011
【００８５】
dnは、ラインの開始ポイントから計算されたn番目のd値である。上式から、非常に稀な場合に限られるが（例えば、k = 0, 1 または∞のとき）、ライン上のdの値は一定値になる。従って、アンチエイリアシングされたラインが、その長さに沿って一定のグレーレベル値をもつことはほとんど不可能である。従来のオーバサンプリングアルゴリズムとプレフィルタリングアルゴリズムは、どちらもラインスキャン変換アルゴリズムに依存しているので、どちらにも、リップル輪郭の問題がある。
【００８６】
１つの例として、図１１は、ロケーション (1, 1) からロケーション (100, 10) までにドローイングされたライン上のグレーレベルの変化を示す全体グラフ図であり、従来のアンチエイリアシングフィルタを使用すると、ライン上のグレーレベルが不等であることを示している。ライン上のグレーレベルの変化は、ライン上の異なるロケーションで同じフィルタ関数に異なるd値をプラグインしたため、サンプリング値が異なった結果である。サンプリング値が異なると、最終的にディスプレイデバイス上でレンダリングされるとき、輪郭の幅にばらつき（つまり、リップル）が生じることになる。
【００８７】
本発明の一形態によれば、アンチエイリアシングコンポーネント８０４は、レンダリングされた画像の中のリップル輪郭を減少する。以下で詳しく説明するように、アンチエイリアシングコンポーネント８０４は、画像の各座標に対して複数のフィルタを使用し、局所的に（例えば、一定座標値に沿って）レンダリングされる異なるピクセルに対して使用されるフィルタの形状を若干変更する。このようにすると、ラインおよび/または曲線に沿った幅のばらつきは、大幅に減少される。基本的には、図１２に示すように、本発明のフィルタリングアルゴリズムは、その中心周りで左右対称になっていて、そのエッジに向かって下方に傾斜しているスライス１２００にライン画像を変更する。このようにすると、表示されるライン画像は、その長さに沿ってグレーレベルが一層統一されるので、レンダリングされる画像のリップル輪郭は減少することになる。
【００８８】
本発明の一形態によれば、従来のGUPTA-SPROULLアルゴリズムが基本的プロシージャとして使用され、アンチエイリアシングされたラインをレンダリングしている。このアルゴリズムは、論文「グレースケールディスプレイのためのエッジのフィルタリング(Filtering Edges for Gray-Scale Displays)」、Computer Graphics, vol. 22, pages 221-228 (ACM SIGGRAPH, July 1981) に説明されている。
【００８９】
一般的に、アンチエイリアシングコンポーネント８０４は、画像の中の各基準ポイント (datum point) のスキャンライン上の複数のピクセル（この例では、３ピクセル）に関するピクセル表示情報を自動的に作成する新規のフィルタリング関数を含んでいる。外側の２ピクセルに対するフィルタは、中心フィルタに対して減少係数βだけ減少しているので、外側の２フィルタから得られる、それぞれのピクセルの画像のグレー化 (graying) は、中心フィルタに比べて減少している。このようにすると、画像の外側エッジ上の隣接ピクセル間のコントラストが減少するので、グレーレベルの変化の知覚が隠れ、リップル効果は実効的に減少することになる。このようにして、ライン画像は、図１２に示すライン画像の形状になる。
【００９０】
βは、好ましくはラインに沿って一定になっている。本発明の一形態によれば、以下で詳しく説明するように、βは、人間のコントラストセンシティビティ (contrast sensitivity：コントラストに対する感度・感受性) に基づいて計算される。
【００９１】
３つのフィルタを使用すると、２つの外側フィルタは減少係数βだけピクセルのグレーを減少するので、ラインのエッジはシャープになる。フィルタリングはピクセルごとに行われ、ピクセルがフィルタリングされる量（従って、ピクセルが明るくなる量）は、特定のピクセルから実際の基準ポイントまでの距離に基づいている。
【００９２】
参照を容易にするために、一連の線形基準ポイントからなる直線の例が説明されている。また、説明を容易にするために、ラインは第１オクタントに置かれ、そこでは、xとyは共に正で、ラインの傾斜は１よりも小になっている。レンダリングプロシージャはx方向に行われる。
【００９３】
ラインのスキャン変換の各ステップでは、ラインの方向に直交する３つのピクセルがレンダリングされ、ラインのエッジが滑らかにされる。同じx値をもつライン上のポイントからこれら３ピクセルの各々までの距離は、フィルタリングのインデックスとして使用される。円錐フィルタ (conical filter) は、単純化のために３ピクセルロケーションの各々で使用されている。オリジナルのGUPTA-SPROULLアルゴリズムとは対照的に、本発明によれば、x値が１つであるとき、３つの異なるピクセルの各々について異なる円錐フィルタ１３０２、１３０４、１３０６（図１３）が使用されている。これらのフィルタは、図１３に示すように、傾斜角が同じになっているが、高さが異なっている。
【００９４】
y軸方向に沿ってアンチエイリアシングラインをレンダリングするためにGUPTA-SPROULLアルゴリズムが使用されるときは、サンプルピクセルに直接隣接する２ピクセルも使用されて、サンプル値を得ている。これら２隣接ピクセルからラインまでの距離は、直接に計算する必要がない。サンプルピクセルからラインまでの距離はdであるので、隣接ピクセルからラインまでの距離は、
【００９５】
【数１１】
0004162934.tif 000012
【００９６】
を使用して計算することができる。ただし、kはラインの傾斜である。これらの距離値をインデックスとして使用すると、これらの位置のサンプル値は、解析計算またはテーブルルックアップによってフィルタリング画像から抽出することができる。
【００９７】
本発明によれば、スキャン変換によって候補サンプリング位置を選択するプロセスはそのまま残されているが、フィルタリング画像から輝度値 (intensity value) を計算するときは、スキャン変換から得られた距離値は、ピクセルのグレーレベルの局所的調整を行うように変換される。距離dを使用して輝度を直接に計算する代わりに、サンプルの２隣接ピクセルについては縮小係数(shrinking factor)βがdの値に適用され、βdを使用して得られた輝度値は、これらのピクセルの距離値として使用されている。外側の２フィルタについては、使用される距離値は、
【００９８】
【数１２】
0004162934.tif 000013
【００９９】
である。縮小係数を追加することは、サンプリング位置をライン方向に移動したのと同じであるので、局所的調整が行われることになる。
【０１００】
この単純な局所的調整を行うと、レンダリングされたライン画像に沿った輝度の変化がどのように減少するかを示すために、円錐フィルタを使用して第１オクタントの理想的ラインをアンチエイリアシングする例が説明されている。理想的ラインをソース信号として使用したのは、説明を簡単にするためである。定義により、理想的ラインは、一連の2πデルタ関数から構成され、フィルタ関数による2πデルタ関数のコンボルーションは、フィルタ関数がそのデルタ関数の中心にもつ値だけになっている。このプロパティによると、コンボルーションの計算は、ピクセル位置のフィルタ関数を計算するだけで済むので、解析が容易化される。
【０１０１】
スキャンライン上のフィルタリング画像の平均サンプリング輝度値は、
【０１０２】
【数１３】
0004162934.tif 000014
【０１０３】
である。ただし、hは、円錐フィルタの高さ、aは、円錐の傾斜、Aは、ピクセルが占めているエリアである。輝度のリップリングは、この式の線形部分によって生成される。縮小係数
【０１０４】
【外１】
0004162934.tif 000015
【０１０５】
が導入されると、この平均サンプリング輝度値は、
【０１０６】
【数１４】
0004162934.tif 000016
【０１０７】
に変わる。だだし、縮小係数
【０１０８】
【外２】
0004162934.tif 000017
【０１０９】
は、ライン上の平均サンプリング輝度値の最大値と最小値の差分を減少するのに役立っている。これは、リップリング輪郭現象を低減するのに役立っている。
【０１１０】
本発明の一形態によれば、減少係数βは、人間の一般的コントラストセンシティビティに関して分かっている情報に基づいている。コントラストセンシティビティのテストを行うと、代表的なビジュアル敏感テスト (visual acuity test) で得られるビジュアル関数の評価が補足され、拡張される。プロシージャが複雑化し、時間がかかるという犠牲を伴うが、コントラストセンシティビティを測定すると、ターゲットサイズ（および向き）の拡張範囲にわたって低コントラストターゲットを個人が見る能力に関する情報が得られる。
【０１１１】
コントラストセンシティビティテストでは、敏感テストで一般に使用されている文字視力検査表 (letter optotype) ではなく、正弦波格子 (sine-wave grating) がターゲットとして使用されている。正弦波格子は有用な数学的プロパティを具備しており、研究者によれば、ビジュアル処理の初期ステージをそのようなターゲットに「チューニング」すると最適であることが判明している。
【０１１２】
コントラストセンシティビティ評価プロシージャは、所与の空間周波数（つまり、視角の１度当たりの正弦ルミナンスサイクルの数）の正弦波格子ターゲットを観察者に表示することからなっている。空間周波数は、ディスプレイの解像度を近似的に表すことができる点で重要である。ターゲット格子のコントラストが変化するので、その間に観察者のコントラスト検出しきい値が判断される。代表例として、この種のコントラストしきい値は、空間周波数が視角の１度当たり0.5（非常に広い）サイクルから32（非常に狭い）サイクルに変化する垂直向きの正弦波格子を使用して収集される。
【０１１３】
コントラストしきい値から生成された情報を使用すると、コントラストセンシティビティ関数を、個人に対して生成することができる。テストで生成される情報は、基本的には、いくつかの異なる周波数のときのコントラストしきい値（つまり、観察者が差異を対比できる最低レベル）をプロットしたものである。図１４に示すコントラストセンシティビティ関数１４００は、すべての空間周波数についてコントラストセンシティビティ（1 /（コントラストしきい値））をプロットする。図１４に示すコントラストセンシティビティ関数１４００は、一般的に、理想的条件（視力検査表、若い成年の観察者、網膜中心窩の視野(foveal viewing)）の下の代表的な形状を表している。一般的に、個人は、中間周波数（１度当たり略6 - 8サイクル）に最も敏感であり、低周波数と高周波数には感度が劣っている。
【０１１４】
コントラストセンシティビティ関数は、観察者の可視ウィンドウを示している。コントラストセンシティビティ関数ライン１４００以下（つまり、ナイキスト(Nyquist) 限界以下）のポイントは、観察者に可視になっている（これらは、しきい値レベルよりもコントラストがさらに高くなっているポイントである）。コントラストセンシティビティ関数以上のポイントは、観察者には見えない（これらは、しきい値レベルよりもコントラストが低くなっているポイントである）。
【０１１５】
本発明の一形態によれば、コントラストセンシティビティ関数は、減少係数βを計算するために使用されている。一般的に、この減少係数は、ジャギーとリップル輪郭の両方を最小限にするように最適化されているはずである。使用する減少係数βが小さすぎると、隣り合うピクセルのフィルタが極端に低下し、ジャギーを発生する原因になるので、その使用は好ましくない。正しい調整は、むらのない輪郭と平滑なエッジとのバランスをとることである。本発明の一形態によれば、減少係数βは、隣り合うピクセル間のコントラストを減少するように計算され、人間の知覚からコントラストが見えないように配慮している。
【０１１６】
コントラストセンシティビティ関数曲線は、A(f) = 0.04992[1+5.9375f]e-(0.114f)1.1としてモデル化され、空間周波数は次式で計算されている。
【０１１７】
【数１５】
0004162934.tif 000018
【０１１８】
上記において、rは、長さwのピクセル、Rは、スクリーンの解像度である。本件出願人は、d = 50cm、W = 34cm、R = 1280およびα = 1度として実験を行い、rの値として32.54を計算した。
【０１１９】
rが得られると、所与の傾斜をもつラインの空間周波数を計算することができる。傾斜kをもつラインでは、ラインの輝度値は、約1/k個のピクセルのあと、周期的変化をもつことになるので、サイクル/度で表した空間周波数は、r*kを使用して計算することができる。0.1から10までの傾斜がリップル輪郭に関係しているものとすると（これよりも大または小の傾斜はピクセルとほぼ位置合わせされている）、コントラストセンシティビティ関数は、可能な限り最良の減少係数値を計算するために使用できる。高解像度のディスプレイでは、個人のコントラストセンシティビティは、グレーレベルの差異を検出できるほどに高くないため、リップル効果は目に見えないのが一般である。従って、図１４に示すグラフでは、１度当りのサイクルが高いとき（一般に、20サイクル/度よりも高いか、あるいはライン１４０２の右にある）のコントラストセンシティビティは、リップル効果とは無関係になっている。しかし、周波数が低くなると、リップル効果が目立つことになる。再び図１４のグラフに示すように、コントラストセンシティビティ公式の最も関係する部分では、ラインが水平になるほど、人間の視力のコントラストセンシティビティは低下し、人間の目はルミナンス輝度の変化を検出しやすくなる。従って、減少係数は、低い傾斜値から生成される周波数を除去するように計算されている。
【０１２０】
傾斜値が0.1であるラインは、空間周波数が度当たり約３サイクルで表示されるようになっている。従って、本件出願人は、このレベルに基づいてβを計算した。本件出願人が発見したことは、βの値を0.6にすると、これは、１度当たり３サイクルで表示されるナイキストレベルに相当するので（図１４のポイント１４０４を参照）、減少係数が特に良好に働くことである。この値を使用すると、リップル効果の大部分は、１度当り３サイクルまたはそれ以上のとき、ユーザには見えないようになる。
【０１２１】
図１５は、本発明のアンリエイリアシングフィルタが適用された後の (1, 1) から (10, 100) までのライン上のグレーレベル値を示している。図１１に比べて、リップルのピークは大幅に（約50%）減少しているため、ラインが最終的にレンダリングされる画像は、ルミナンスが若干失われるという犠牲があるが、非常にばらつきのない幅になっているように見える。
【０１２２】
上述したアンチエイリアシングフィルタ関数を適用すると、直線セグメントのスキャンラインごとにアンチエイリアシングされたピクセルの集合が得られる。しかし、直線セグメントの端は正しく位置合わせされないことがある。位置合わせされていないラインセグメントのレンダリングを防止するために、本発明の端平均化コンポーネント８０６は、直線セグメントの端のピクセルを位置合わせして、その結果の画像がよりも平滑化されて見えるようにする。これを行うために、ある直線の端のピクセルは、隣接する直線の端のピクセルで重み付けされ、ラインからラインへの移行が平滑化するようにしている。そのあと、重み付けされた値が表示される。ここで「重み付け(weighting)」とは、ピクセルのロケーションとピクセルのグレー化が、平滑な移行が行われるように調整されることを意味している。例えば、ラインを平滑化するには、2セグメント間の空隙を埋めるためにピクセルの追加が必要になることがある。ピクセルのグレー値は、新ピクセルが既知のグレー値に対して置かれている相対位置に応じて重み付けすることができる。
【０１２３】
図１６は、単純化された例を示している。直線１６０４の端にあるピクセル値１６０２１、１６０２２、１６０２３は、すべてが直線１６０８の端にあるピクセル値１６０６１、１６０６２、１６０６３と正確に位置合わせされているとは限らない。ロケーションによっては、漏れているピクセル (leaking pixel) と呼ばれるギャップがピクセルの間に存在することがある。漏れているピクセルは、隣接するラインセグメント間の角度が45度を越えているとき発生する。この漏れているピクセルは、２ラインセグメントの接合点の外側エッジに発生している。例えば、ピクセル値１６０２１、１６０６１は、漏れているピクセル１６１０によって分離されている。漏れているピクセルごとに、対応するピクセルロケーションがあり、そこでは、隣接ラインセグメント上の２ピクセルがレンダリングされるようになっている。このロケーションは、２ラインセグメント（例えば、ピクセル値１６０２３、１６０３３）の接合点の内側エッジ上にある。以下で詳しく説明するように、端平均化コンポーネント８０６は、漏れているピクセル１６１０で漏れているピクセル値を追加し、複数のレンダリング指示をもつピクセルロケーションでグレー値を平均化することによって、これらの問題を解消している。
【０１２４】
図１７は、本発明の一形態に従って隣接直線セグメントの端のピクセルを重み付けする（端平均化コンポーネント８０６を通して）プロセスを示す全体概要図である。ステップ１７００から始まって、隣接直線セグメントは、例えば、端平均化コンポーネント８０６によって取り出される。次に、ステップ１７０２では、２ラインセグメント間の角度が45度を超えているかどうかの判断が行われる。この判断は、例えば、２ラインセグメント間の曲率の変化を、次の公式を使用して計算することによって行うことができる。
【０１２５】
【数１６】
0004162934.tif 000019
【０１２６】
上記において、abs(k1-k2) は、２ラインセグメントの傾斜値変化の絶対値である。
【０１２７】
角度が45度を超えていなければ、ステップ１７０２はステップ１７００へブランチし、そこで、次のペアの隣接ピクセルがアクセスされる。
【０１２８】
角度が45度を超えていれば、ステップ１７０２はステップ１７０４へブランチし、そこで、漏れているピクセルが見つけられる。このプロセスでは、例えば、２外側ピクセル間の平均ロケーションが計算され、その平均ロケーションに最も近接しているピクセルが見つけられる。例えば、図１６のピクセル値１６０２１、１６０６１は、空のピクセルロケーションによって分離されている。この例では、２ピクセル１６０２１、１６０６１間の平均位置は、おおよそであるが、これらの２ピクセルの中間に置かれているピクセルロケーション１６１０にある。
【０１２９】
ステップ１７０６では、漏れているピクセル位置に隣接している２ピクセルのグレー値が平均化される（例えば、ピクセル１６０２１、１６０６１）。次に、プロセスはステップ１７０８へ進み、そこで、平均化されたグレー値は、漏れているピクセルのグレー値としてセットされる。
【０１３０】
上述したように、漏れているピクセルが存在するときは、補足的なダブルレンダリングピクセル (double rendering pixel) も存在するのが代表的である。ステップ１７１０では、ダブルレンダリングピクセルが見つけられる。このステップでは、２ラインセグメントが共にピクセル情報をもっているピクセルを見つけるだけで済む場合がある。ダブルレンダリングピクセルにアドレスするために、ステップ１７１２では、そのピクセルの２ピクセル値のグレーレベル値が平均化される。平均化されたグレー値は、ステップ１７１４で、ダブルレンダリングピクセルのグレー値としてセットされる。
【０１３１】
ステップ１７１６では、隣接するセグメントペアがすべて評価されたかどうかの判断が行われる。そうでなければ、プロセスはループしてステップ１７００に戻り、そこで、次の隣接セグメントペアが取り出される。そうであれば、プロセスは終了する。
【０１３２】
本発明の平滑化プロセスによれば、直線セグメント間の移行が平滑化されるので、審美的に快適なレンダリング画像が作成される。本発明の概念を使用すると、画像に対してその他の変更を行うことが可能である。
【０１３３】
本発明は種々の変更と代替構成が可能であるが、本発明の特定の実施形態例を図示して、詳しく説明してきた。当然に理解されるように、本発明は、上述してきた特定の実施形態に限定されるものではなく、本発明の精神と範囲に属するすべての変更、代替構成、および等価技術は本発明に包含されるものである。
【図面の簡単な説明】
【図１】本発明を組み入れることができるコンピュータシステムを示すブロック図である。
【図２】本発明の一形態に従ってデジタルインクファイルを圧縮するためのシステムのアーキテクチャを示すブロック図である。
【図３】本発明の一形態による圧縮モジュールのアーキテクチャを示すブロック図である。
【図４】本発明の一形態に従ってデジタルインク情報を圧縮するためのプロセスを示す全体概要フロー図である。
【図５】本発明のデジタルインクジェネレータによって形成されたインクトレースを示す模式図である。
【図６】本発明の一形態に従って図５のインクトレースから作成された圧縮バックボーンスプラインを示す模式図である。
【図７】本発明の一形態に従って図６のバックボーンスプラインのラインセグメントを曲線適合するためのプロセスを示す全体概要フロー図である。
【図８】本発明の一形態に従ってデジタル情報を表示するためのシステムのアーキテクチャを示すブロック図である。
【図９】本発明の一形態に従ってデジタルインク情報を表示するためのプロセスを示す全体概要フロー図である。
【図１０】本発明の一形態に従ってアンチエイリアシングフィルタをラインに適用する以前のラインを示す模式図である。
【図１１】ロケーション (1, 1) からロケーション (100, 10) にドローイングされたライン上のグレーレベルの変化を示す全体グラフ図であり、そこでは、従来のアンチエイリアシングフィルタを使用すると、ライン上のグレーラインにばらつきがあることを示している。
【図１２】本発明の一形態に従ってアンチエイリアシングフィルタを適用した後のラインを示す模式図である。
【図１３】本発明の一形態に従ってアンチエイリアシングフィルタによるフィルタリングのパターンを示す概念図である。
【図１４】人間の知覚のコントラストセンシティビティ関数を示す全体グラフ図である。
【図１５】本発明の一形態に従って本発明のアンチエイリアシングフィルタが適用された後のライン (1, 1) から (10, 100) 上のグレーレベル値を示す全体グラフ図である。
【図１６】本発明の一形態に従って隣接直線セグメントの端のピクセルを平均化する例を示す模式図である。
【図１７】本発明の一形態に従って隣接直線セグメントの端のピクセルを平均化するためのプロセスを示す概要フロー図である。
【符号の説明】
２０４  デジタルインクレシーバ
２０６  圧縮モジュール
２０８  レコグナイザ
２０９  ディスプレイ生成メカニズム
２１０  ディスプレイモジュール
２１２  コネクション
２２０  デジタルインクジェネレータ
３０２  平滑化フィルタ
３０４  シャープポイントコンポーネント
３０６  曲線適合コンポーネント
３０８  輪郭曲線コンポーネント
３１０  データベース
８０２  分離コンポーネント
８０４  アンチエイリアシングコンポーネント
８０６  端平均化コンポーネント
【図１】
0004162934.tif 000020
【図２】
0004162934.tif 000021
【図３】
0004162934.tif 000022
【図４】
0004162934.tif 000023
【図５】
0004162934.tif 000024
【図６】
0004162934.tif 000025
【図７】
0004162934.tif 000026
【図８】
0004162934.tif 000027
【図９】
0004162934.tif 000028
【図１０】
0004162934.tif 000029
【図１１】
0004162934.tif 000030
【図１２】
0004162934.tif 000031
【図１３】
0004162934.tif 000032
【図１４】
0004162934.tif 000033
【図１５】
0004162934.tif 000034
【図１６】
0004162934.tif 000035
【図１７】
0004162934.tif 000036