(57)【要約】  少なくとも１つのオブジェクトの少なくともいくつかの要素は、ズーミングに関連付けられた１つまたは複数のズームレベルに非物理的に比例するように拡大および／または縮小され、例えばこの非物理的に比例するスケーリングは公式ｐ＝ｄ’・ｚａで表すことが可能であり、この式で、ｐはそのズームレベルでのオブジェクトの１つまたは複数の要素のピクセル単位での線形サイズであり、ｄ’は物理単位でのオブジェクトの１つまたは複数の要素の帰属線形サイズであり、ｚは物理線形サイズ／ピクセルの単位でのズームレベルであり、ａはａ≠−１である指数である、少なくとも１つのオブジェクトを有するイメージをズームインまたはズームアウトすることを含む、様々なアクションを実行するための方法および装置が企図される。
2008501160.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも１つのオブジェクトを有するイメージをズームインまたはズームアウトするステップを含む方法であって、前記少なくとも１つのオブジェクトのうちの少なくともいくつかの要素は、前記ズーミングに関連付けられた１つまたは複数のズームレベルに非物理的に比例するように拡大および／または縮小されることを特徴とする方法。
【請求項２】
前記非物理的に比例するスケーリングは、式ｐ＝ｄ’・ｚａで表すことが可能であり、上式で、ｐは前記ズームレベルでの前記オブジェクトの１つまたは複数の要素のピクセル単位での線形サイズであり、ｄ’は物理単位での前記オブジェクトの前記１つまたは複数の要素の帰属線形サイズであり、ｚは物理線形サイズ／ピクセル単位での前記ズームレベルであり、ａはａ≠−１である指数であることを特徴とする請求項１に記載の方法。
【請求項３】
ｄ’およびａのうちの少なくとも１つは前記オブジェクトのうちの１つまたは複数の要素について異なりうることを特徴とする請求項２に記載の方法。
【請求項４】
前記指数はズームレベルｚ０からｚ１の範囲内で−１＜ａ＜０であり、ｚ０はｚ１よりも小さい物理線形サイズ／ピクセルであることを特徴とする請求項２に記載の方法。
【請求項５】
ｚ０、ｚ１、ｄ’、およびａのうちの少なくとも１つは前記オブジェクトのうちの１つまたは複数の要素について異なりうることを特徴とする請求項４に記載の方法。
【請求項６】
前記少なくとも１つのオブジェクトのうちの少なくともいくつかの要素は、前記ズーミングに関連付けられた１つまたは複数のズームレベルに物理的に比例するように拡大および／または縮小もされることを特徴とする請求項１に記載の方法。
【請求項７】
前記物理的に比例するスケーリングは、式ｐ＝ｃ・ｄ／ｚで表すことが可能であり、上式で、ｐは前記オブジェクトの１つまたは複数の要素のピクセル単位での線形サイズであり、ｃは定数であり、ｄは前記オブジェクトの前記１つまたは複数の要素の物理単位での実線形サイズまたは帰属線形サイズであり、ｚは物理線形サイズ／ピクセル単位での前記ズームレベルであることを特徴とする請求項６に記載の方法。
【請求項８】
前記オブジェクトの前記要素は粗さの程度が異なり、
所与のズームレベルでの前記要素の前記スケーリングは、（ｉ）こうした要素の粗さの程度および（ｉｉ）前記ズームレベルのうちの、少なくとも１つに基づいて物理的に比例するかまたは非物理的に比例することを特徴とする請求項６に記載の方法。
【請求項９】
前記オブジェクトは道路地図であり、前記オブジェクトの前記要素は道路であり、前記異なる粗さの程度は道路階層であって、
所与のズームレベルでの所与の道路の前記スケーリングは、（ｉ）前記所与の道路の前記道路階層および（ｉｉ）前記ズームレベルに基づいて、物理的に比例するかまたは非物理的に比例することを特徴とする請求項８に記載の方法。
【請求項１０】
少なくとも１つのオブジェクトを有するイメージをズームインまたはズームアウトすることであって、前記少なくとも１つのオブジェクトのうちの少なくともいくつかの要素は、ズーミングに関連付けられた１つまたは複数のズームレベルに非物理的に比例するように拡大および／または縮小される、ズームインまたはズームアウトすることを含むアクションを、処理ユニットに実行させるように動作可能な１つまたは複数のソフトウェアプログラムを含むことを特徴とする記憶媒体。
【請求項１１】
前記非物理的に比例するスケーリングは、式ｐ＝ｄ’・ｚａで表すことが可能であり、上式で、ｐは前記ズームレベルでの前記オブジェクトの１つまたは複数の要素のピクセル単位での線形サイズであり、ｄ’は物理単位での前記オブジェクトの前記１つまたは複数の要素の帰属線形サイズであり、ｚは物理線形サイズ／ピクセル単位での前記ズームレベルであり、ａはａ≠−１である指数であることを特徴とする請求項１０に記載の記憶媒体。
【請求項１２】
ｄ’およびａのうちの少なくとも１つは前記オブジェクトのうちの１つまたは複数の要素について異なりうることを特徴とする請求項１１に記載の方法。
【請求項１３】
前記スケール指数はズームレベルｚ０からｚ１の範囲内で−１＜ａ＜０であり、ｚ０はｚ１よりも小さい物理線形サイズ／ピクセルであることを特徴とする請求項１１に記載の記憶媒体。
【請求項１４】
ｚ０およびｚ１のうちの少なくとも１つは前記オブジェクトのうちの１つまたは複数の要素について異なりうることを特徴とする請求項１３に記載の記憶媒体。
【請求項１５】
前記少なくとも１つのオブジェクトのうちの少なくともいくつかの要素は、前記ズーミングに関連付けられた１つまたは複数のズームレベルに物理的に比例するように拡大および／または縮小もされることを特徴とする請求項９に記載の記憶媒体。
【請求項１６】
前記物理的に比例するスケーリングは、式ｐ＝ｃ・ｄ／ｚで表すことが可能であり、上式で、ｐは前記オブジェクトの１つまたは複数の要素のピクセル単位での線形サイズであり、ｃは定数であり、ｄは前記オブジェクトの前記１つまたは複数の要素の物理単位での実線形サイズまたは帰属線形サイズであり、ｚは物理線形サイズ／ピクセル単位での前記ズームレベルであることを特徴とする請求項１５に記載の記憶媒体。
【請求項１７】
前記オブジェクトの前記要素は粗さの程度が異なり、
所与のズームレベルでの前記要素の前記スケーリングは、（ｉ）こうした要素の粗さの程度および（ｉｉ）前記ズームレベルのうちの、少なくとも１つに基づいて物理的に比例するかまたは非物理的に比例することを特徴とする請求項１５に記載の記憶媒体。
【請求項１８】
前記オブジェクトは道路地図であり、前記オブジェクトの前記要素は道路であり、前記異なる粗さの程度は道路階層であって、
所与のズームレベルでの所与の道路の前記スケーリングは、（ｉ）前記所与の道路の前記道路階層および（ｉｉ）前記ズームレベルに基づいて、物理的に比例するかまたは非物理的に比例することを特徴とする請求項１７に記載の記憶媒体。
【請求項１９】
少なくとも１つのオブジェクトを有するイメージをズームインまたはズームアウトすることであって、前記少なくとも１つのオブジェクトのうちの少なくともいくつかの要素は、ズーミングに関連付けられた１つまたは複数のズームレベルに非物理的に比例するように拡大および／または縮小される、ズームインまたはズームアウトすることを含むアクションを、処理ユニットに実行させるように動作可能な１つまたは複数のソフトウェアプログラムの制御の下で動作する、処理ユニットを含むことを特徴とする装置。
【請求項２０】
前記非物理的に比例するスケーリングは、式ｐ＝ｄ’・ｚａで表すことが可能であり、上式で、ｐは前記ズームレベルでの前記オブジェクトの１つまたは複数の要素のピクセル単位での線形サイズであり、ｄ’は物理単位での前記オブジェクトの前記１つまたは複数の要素の帰属線形サイズであり、ｚは物理線形サイズ／ピクセル単位での前記ズームレベルであり、ａはａ≠−１である指数であることを特徴とする請求項１９に記載の装置。
【請求項２１】
ｄ’およびａのうちの少なくとも１つは前記オブジェクトのうちの１つまたは複数の要素について異なりうることを特徴とする請求項２０に記載の方法。
【請求項２２】
前記指数はズームレベルｚ０からｚ１の範囲内で−１＜ａ＜０であり、ｚ０はｚ１よりも小さい物理線形サイズ／ピクセルであることを特徴とする請求項２０に記載の装置。
【請求項２３】
ｚ０およびｚ１のうちの少なくとも１つは前記オブジェクトのうちの１つまたは複数の要素について異なりうることを特徴とする請求項２２に記載の装置。
【請求項２４】
前記少なくとも１つのオブジェクトのうちの少なくともいくつかの要素は、前記ズーミングに関連付けられた１つまたは複数のズームレベルに物理的に比例するように拡大および／または縮小もされることを特徴とする請求項１９に記載の装置。
【請求項２５】
前記物理的に比例するスケーリングは、式ｐ＝ｃ・ｄ／ｚで表すことが可能であり、上式で、ｐは前記オブジェクトの１つまたは複数の要素のピクセル単位での線形サイズであり、ｃは定数であり、ｄは前記オブジェクトの前記１つまたは複数の要素の物理単位での実線形サイズまたは帰属線形サイズであり、ｚは物理線形サイズ／ピクセル単位での前記ズームレベルであることを特徴とする請求項２４に記載の装置。
【請求項２６】
前記オブジェクトの前記要素は粗さの程度が異なり、
所与のズームレベルでの前記要素の前記スケーリングは、（ｉ）こうした要素の粗さの程度および（ｉｉ）前記ズームレベルのうちの、少なくとも１つに基づいて物理的に比例するかまたは非物理的に比例することを特徴とする請求項２４に記載の装置。
【請求項２７】
前記オブジェクトは道路地図であり、前記オブジェクトの前記要素は道路であり、前記異なる粗さの程度は道路階層であって、
所与のズームレベルでの所与の道路の前記スケーリングは、（ｉ）前記所与の道路の前記道路階層および（ｉｉ）前記ズームレベルに基づいて、物理的に比例するかまたは非物理的に比例することを特徴とする請求項２６に記載の装置。
【請求項２８】
少なくとも１つのオブジェクトの異なるズームレベルの複数のイメージを作成するステップを含む方法であって、前記少なくとも１つのオブジェクトのうちの少なくともいくつかの要素は、１つまたは複数のズームレベルに非物理的に比例するように拡大および／または縮小されることを特徴とする方法。
【請求項２９】
前記イメージは、クライアント端末への配信のためにソース端末で事前レンダリングされることを特徴とする請求項２８に記載の方法。
【請求項３０】
前記非物理的に比例するスケーリングは、式ｐ＝ｄ’・ｚａで表すことが可能であり、上式で、ｐは前記ズームレベルでの前記オブジェクトの１つまたは複数の要素のピクセル単位での線形サイズであり、ｄ’は物理単位での前記オブジェクトの前記１つまたは複数の要素の帰属線形サイズであり、ｚは物理線形サイズ／ピクセル単位での前記ズームレベルであり、ａはａ≠−１である指数であることを特徴とする請求項２８に記載の方法。
【請求項３１】
ｄ’およびａのうちの少なくとも１つは前記オブジェクトのうちの１つまたは複数の要素について異なりうることを特徴とする請求項３０に記載の方法。
【請求項３２】
前記指数はズームレベルｚ０からｚ１の範囲内で−１＜ａ＜０であり、ｚ０はｚ１よりも小さい物理線形サイズ／ピクセルであることを特徴とする請求項３０に記載の方法。
【請求項３３】
ｚ０およびｚ１のうちの少なくとも１つは前記オブジェクトのうちの１つまたは複数の要素について異なりうることを特徴とする請求項３２に記載の方法。
【請求項３４】
前記少なくとも１つのオブジェクトのうちの少なくともいくつかの要素は、前記ズーミングに関連付けられた１つまたは複数のズームレベルに物理的に比例するように拡大および／または縮小もされることを特徴とする請求項２８に記載の方法。
【請求項３５】
前記物理的に比例するスケーリングは、式ｐ＝ｃ・ｄ／ｚで表すことが可能であり、上式で、ｐは前記オブジェクトの１つまたは複数の要素のピクセル単位での線形サイズであり、ｃは定数であり、ｄは前記オブジェクトの前記１つまたは複数の要素の物理単位での実線形サイズまたは帰属線形サイズであり、ｚは物理線形サイズ／ピクセル単位での前記ズームレベルであることを特徴とする請求項３４に記載の方法。
【請求項３６】
前記オブジェクトの前記要素は粗さの程度が異なり、
所与のズームレベルでの前記要素の前記スケーリングは、（ｉ）こうした要素の粗さの程度および（ｉｉ）前記ズームレベルのうちの、少なくとも１つに基づいて物理的に比例するかまたは非物理的に比例することを特徴とする請求項３４に記載の方法。
【請求項３７】
前記オブジェクトは道路地図であり、前記オブジェクトの前記要素は道路であり、前記異なる粗さの程度は道路階層であって、
所与のズームレベルでの所与の道路の前記スケーリングは、（ｉ）前記所与の道路の前記道路階層および（ｉｉ）前記ズームレベルに基づいて、物理的に比例するかまたは非物理的に比例することを特徴とする請求項３６に記載の方法。
【請求項３８】
前記指数はズームレベルｚ０からｚ１の範囲内で−１＜ａ＜０であり、ｚ０はｚ１よりも小さい物理線形サイズ／ピクセルであることを特徴とする請求項３７に記載の方法。
【請求項３９】
ｚ０およびｚ１のうちの少なくとも１つは前記道路地図のうちの１つまたは複数の道路について異なりうることを特徴とする請求項３８に記載の方法。
【請求項４０】
ズームレベルの異なる道路地図の複数の事前レンダリングされたイメージをクライアント端末で受信するステップと、
ズーミング情報を含む１つまたは複数のユーザナビゲーションコマンドを前記クライアント端末で受信するステップと、
前記ナビゲーションコマンドの前記ズーミング情報に対応する中間ズームレベルの中間イメージを取得するために、前記クライアント端末上での前記中間イメージの表示が滑らかなナビゲーションの外観を提供するように、前記事前レンダリングされたイメージのうちの２つまたはそれ以上をブレンドするステップと
を含むことを特徴とする方法。
【請求項４１】
前記道路地図のうちの少なくともいくつかの道路は、前記複数の事前決定されたイメージを生成するために拡大および／または縮小され、前記スケーリングは、（ｉ）前記ズームレベルに物理的に比例すること、および（ｉｉ）前記ズームレベルに非物理的に比例することのうちの少なくとも１つであることを特徴とする請求項４０に記載の方法。
【請求項４２】
前記物理的に比例するスケーリングは、式ｐ＝ｃ・ｄ／ｚで表すことが可能であり、上式で、ｐは前記ズームレベルでの前記オブジェクトの１つまたは複数の要素のピクセル単位での線形サイズであり、ｃは定数であり、ｄは前記オブジェクトの前記１つまたは複数の要素の物理単位での実線形サイズまたは帰属線形サイズであり、ｚは物理線形サイズ／ピクセル単位での前記ズームレベルであることを特徴とする請求項４１に記載の方法。
【請求項４３】
前記非物理的に比例するスケーリングは、式ｐ＝ｄ’・ｚａで表すことが可能であり、上式で、ｐは前記ズームレベルでの前記オブジェクトの１つまたは複数の要素のピクセル単位での線形サイズであり、ｄ’は物理単位での前記オブジェクトの前記１つまたは複数の要素の帰属線形サイズであり、ｚは物理線形サイズ／ピクセル単位での前記ズームレベルであり、ａはａ≠−１である指数であることを特徴とする請求項４１に記載の方法。
【請求項４４】
ｄ’およびａのうちの少なくとも１つは前記オブジェクトのうちの１つまたは複数の要素について異なりうることを特徴とする請求項４３に記載の方法。
【請求項４５】
前記指数はズームレベルｚ０からｚ１の範囲内で−１＜ａ＜０であり、ｚ０はｚ１よりも小さい物理線形サイズ／ピクセルであることを特徴とする請求項４３に記載の方法。
【請求項４６】
ｚ０およびｚ１のうちの少なくとも１つは前記道路地図のうちの１つまたは複数の道路について異なりうることを特徴とする請求項４５に記載の方法。
【請求項４７】
前記道路地図の前記道路は粗さの程度が異なり、
所与の事前レンダリングされたイメージにおける前記道路の前記スケーリングは、（ｉ）こうした道路の粗さの程度および（ｉｉ）前記所与の事前レンダリングされたイメージの前記ズームレベルのうちの、少なくとも１つに基づいて物理的に比例するかまたは非物理的に比例することを特徴とする請求項４０に記載の方法。
【請求項４８】
ズームレベルの異なる少なくとも１つのオブジェクトの複数の事前レンダリングされたイメージをクライアント端末で受信するステップであって、前記少なくとも１つのオブジェクトのうちの少なくともいくつかの要素は、前記複数の事前決定されたイメージを生成するために拡大および／または縮小され、前記スケーリングは、（ｉ）前記ズームレベルに物理的に比例すること、および（ｉｉ）前記ズームレベルに非物理的に比例することのうちの少なくとも１つである、受信するステップと、
ズーミング情報を含む１つまたは複数のユーザナビゲーションコマンドを前記クライアント端末で受信するステップと、
前記ナビゲーションコマンドの前記ズーミング情報に対応する中間ズームレベルの中間イメージを取得するために、前記事前レンダリングされたイメージのうちの２つまたはそれ以上をブレンドするステップと、
前記クライアント端末上で前記中間イメージを表示するステップと
を含むことを特徴とする方法。
【請求項４９】
前記ブレンドするステップは、アルファブレンディングと、トリリニア補間と、双３次線形補間とのうちの少なくとも１つを実行するステップを含むことを特徴とする請求項４８に記載の方法。
【請求項５０】
前記事前レンダリングされたイメージの数は、それらの間のブレンディングが滑らかなナビゲーションの外観を提供するようなものであることを特徴とする請求項４８に記載の方法。
【請求項５１】
前記ズームレベルおよび前記事前レンダリングされたイメージのスケーリングは、前記オブジェクトのうちの所与の１つまたは複数の前記要素のピクセル単位のそれぞれの線形サイズｐが、１つの事前レンダリングされたイメージと他のより解像度の高い事前レンダリングされたイメージとの間の事前に決定されたピクセル数よりも大きく異ならないように選択されることを特徴とする請求項４８に記載の方法。
【請求項５２】
前記事前に決定されたピクセル数は約２であることを特徴とする請求項５１に記載の方法。
【請求項５３】
事前レンダリングされたイメージのうちの最低解像度のズームレベルを超えたズームレベルへのナビゲートを容易にするために、前記事前レンダリングされたイメージのうちの最低解像度のイメージをダウンサンプリングするステップをさらに含むことを特徴とする請求項５０に記載の方法。
【請求項５４】
前記物理的に比例するスケーリングは、式ｐ＝ｃ・ｄ／ｚで表すことが可能であり、上式で、ｐは前記ズームレベルでの前記オブジェクトの１つまたは複数の要素のピクセル単位での線形サイズであり、ｃは定数であり、ｄは前記オブジェクトの前記１つまたは複数の要素の物理単位での実線形サイズまたは帰属線形サイズであり、ｚは物理線形サイズ／ピクセル単位での前記ズームレベルであることを特徴とする請求項４８に記載の方法。
【請求項５５】
前記非物理的に比例するスケーリングは、式ｐ＝ｄ’・ｚａで表すことが可能であり、上式で、ｐは前記ズームレベルでの前記オブジェクトの１つまたは複数の要素のピクセル単位での線形サイズであり、ｄ’は物理単位での前記オブジェクトの前記１つまたは複数の要素の帰属線形サイズであり、ｚは物理線形サイズ／ピクセル単位での前記ズームレベルであり、ａはａ≠−１である指数であることを特徴とする請求項４８に記載の方法。
【請求項５６】
ｄ’およびａのうちの少なくとも１つは前記オブジェクトのうちの１つまたは複数の要素について異なりうることを特徴とする請求項５５に記載の方法。
【請求項５７】
前記指数はズームレベルｚ０からｚ１の範囲内で−１＜ａ＜０であり、ｚ０はｚ１よりも小さい物理線形サイズ／ピクセルであることを特徴とする請求項５５に記載の方法。
【請求項５８】
ｚ０およびｚ１のうちの少なくとも１つは前記オブジェクトのうちの１つまたは複数の要素について異なりうることを特徴とする請求項５７に記載の方法。
【請求項５９】
前記複数の事前レンダリングされたイメージは、パケット化されたネットワークを介して前記クライアント端末によって受信されることを特徴とする請求項４８に記載の方法。
【請求項６０】
前記パケット化されたネットワークはインターネットであることを特徴とする請求項５９に記載の方法。
【請求項６１】
前記オブジェクトの前記要素は粗さの程度が異なり、
所与の事前レンダリングされたイメージにおける前記要素の前記スケーリングは、（ｉ）こうした要素の粗さの程度および（ｉｉ）前記所与の事前レンダリングされたイメージの前記ズームレベルのうちの、少なくとも１つに基づいて物理的に比例するかまたは非物理的に比例することを特徴とする請求項４８に記載の方法。
【請求項６２】
前記オブジェクトは道路地図であり、前記オブジェクトの前記要素は道路であり、前記異なる粗さの程度は道路階層であって、
所与の事前レンダリングされたイメージでの所与の道路の前記スケーリングは、（ｉ）前記所与の道路の前記道路階層および（ｉｉ）前記所与の事前レンダリングされたイメージの前記ズームレベルに基づいて、物理的に比例するかまたは非物理的に比例することを特徴とする請求項６１に記載の方法。
【請求項６３】
前記非物理的に比例するスケーリングは、式ｐ＝ｄ’・ｚａで表すことが可能であり、上式で、ｐは前記ズームレベルでの前記オブジェクトの１つまたは複数の要素のピクセル単位での線形サイズであり、ｄ’は物理単位での前記オブジェクトの前記１つまたは複数の要素の帰属線形サイズであり、ｚは物理線形サイズ／ピクセル単位での前記ズームレベルであることを特徴とする請求項６２に記載の方法。
【請求項６４】
ｄ’およびａのうちの少なくとも１つは前記オブジェクトのうちの１つまたは複数の要素について異なりうることを特徴とする請求項６３に記載の方法。
【請求項６５】
前記指数はズームレベルｚ０からｚ１の範囲内で−１＜ａ＜０であり、ｚ０はｚ１よりも小さい物理線形サイズ／ピクセルであることを特徴とする請求項６３に記載の方法。
【請求項６６】
ｚ０およびｚ１のうちの少なくとも１つは前記道路地図のうちの１つまたは複数の道路について異なりうることを特徴とする請求項６５に記載の方法。
【請求項６７】
異なるズームレベルの少なくとも１つのオブジェクトの複数のイメージを、通信チャネルを介して端末に送信するステップであって、前記少なくとも１つのオブジェクトのうちの少なくともいくつかの要素は、前記複数のイメージを生成するために拡大および／または縮小され、前記スケーリングは、（ｉ）前記ズームレベルに物理的に比例すること、および（ｉｉ）前記ズームレベルに非物理的に比例することのうちの少なくとも１つである、送信するステップと、
前記端末で前記複数のイメージを受信するステップと、
前記端末を使用してズーミング情報を含む１つまたは複数のユーザナビゲーションコマンドを発行するステップと、
前記ナビゲーションコマンドの前記ズーミング情報に対応する中間ズームレベルの中間イメージを取得するために、前記イメージのうちの少なくとも２つをブレンドするステップと、
前記端末上で前記中間イメージを表示するステップと
を含むことを特徴とする方法。
【請求項６８】
前記ブレンドするステップは、アルファブレンディングと、トリリニア補間と、双３次線形補間とのうちの少なくとも１つを実行するステップを含むことを特徴とする請求項６７に記載の方法。
【請求項６９】
前記イメージの数は、それらの間のブレンディングが滑らかなナビゲーションの外観を提供するようなものであることを特徴とする請求項６７に記載の方法。
【請求項７０】
前記ズームレベルおよび前記事前レンダリングされたイメージのスケーリングは、前記オブジェクトのうちの所与の１つまたは複数の前記要素のピクセル単位のそれぞれの線形サイズｐが、１つの事前レンダリングされたイメージと他のより解像度の高い事前レンダリングされたイメージとの間の事前に決定されたピクセル数よりも大きく異ならないように選択されることを特徴とする請求項６７に記載の方法。
【請求項７１】
前記事前に決定されたピクセル数は約２であることを特徴とする請求項７０に記載の方法。
【請求項７２】
前記イメージのうちの最低解像度のズームレベルを超えたズームレベルへのナビゲートを容易にするために、前記イメージのうちの最低解像度のイメージをダウンサンプリングするステップをさらに含むことを特徴とする請求項６９に記載の方法。
【請求項７３】
前記物理的に比例するスケーリングは、式ｐ＝ｃ・ｄ／ｚで表すことが可能であり、上式で、ｐは前記ズームレベルでの前記オブジェクトの１つまたは複数の要素のピクセル単位での線形サイズであり、ｃは定数であり、ｄは前記オブジェクトの前記１つまたは複数の要素の物理単位での実線形サイズまたは帰属線形サイズであり、ｚは物理線形サイズ／ピクセル単位での前記ズームレベルであることを特徴とする請求項６９に記載の方法。
【請求項７４】
前記非物理的に比例するスケーリングは、式ｐ＝ｄ’・ｚａで表すことが可能であり、上式で、ｐは前記ズームレベルでの前記オブジェクトの１つまたは複数の要素のピクセル単位での線形サイズであり、ｄ’は物理単位での前記オブジェクトの前記１つまたは複数の要素の帰属線形サイズであり、ｚは物理線形サイズ／ピクセル単位での前記ズームレベルであり、ａはａ≠−１である指数であることを特徴とする請求項６９に記載の方法。
【請求項７５】
ｄ’およびａのうちの少なくとも１つは前記オブジェクトのうちの１つまたは複数の要素について異なりうることを特徴とする請求項７４に記載の方法。
【請求項７６】
前記指数はズームレベルｚ０からｚ１の範囲内で−１＜ａ＜０であり、ｚ０はｚ１よりも小さい物理線形サイズ／ピクセルであることを特徴とする請求項７４に記載の方法。
【請求項７７】
ｚ０およびｚ１のうちの少なくとも１つは前記オブジェクトのうちの１つまたは複数の要素について異なりうることを特徴とする請求項７６に記載の方法。
【請求項７８】
前記複数のイメージは、パケット化されたネットワークを介して前記端末によって受信されることを特徴とする請求項６９に記載の方法。
【請求項７９】
前記パケット化されたネットワークはインターネットであることを特徴とする請求項７８に記載の方法。
【請求項８０】
前記オブジェクトの前記要素は粗さの程度が異なり、
所与のイメージにおける前記要素の前記スケーリングは、（ｉ）こうした要素の粗さの程度および（ｉｉ）前記所与の事前レンダリングされたイメージの前記ズームレベルのうちの、少なくとも１つに基づいて物理的に比例するかまたは非物理的に比例することを特徴とする請求項６９に記載の方法。
【請求項８１】
前記オブジェクトは道路地図であり、前記オブジェクトの前記要素は道路であり、前記異なる粗さの程度は道路階層であって、
所与のイメージでの所与の道路の前記スケーリングは、（ｉ）前記所与の道路の前記道路階層および（ｉｉ）前記所与の事前レンダリングされたイメージの前記ズームレベルに基づいて、物理的に比例するかまたは非物理的に比例することを特徴とする請求項８０に記載の方法。
【請求項８２】
前記非物理的に比例するスケーリングは、式ｐ＝ｄ’・ｚａで表すことが可能であり、上式で、ｐは前記ズームレベルでの前記オブジェクトの１つまたは複数の要素のピクセル単位での線形サイズであり、ｄ’は物理単位での前記オブジェクトの前記１つまたは複数の要素の帰属線形サイズであり、ｚは物理線形サイズ／ピクセル単位での前記ズームレベルであり、ａはａ≠−１である指数であることを特徴とする請求項８１に記載の方法。
【請求項８３】
ｄ’およびａのうちの少なくとも１つは前記オブジェクトのうちの１つまたは複数の要素について異なりうることを特徴とする請求項８２に記載の方法。
【請求項８４】
前記スケール指数はズームレベルｚ０からｚ１の範囲内で−１＜ａ＜０であり、ｚ０はｚ１よりも小さい物理線形サイズ／ピクセルであることを特徴とする請求項８２に記載の方法。
【請求項８５】
ｚ０およびｚ１のうちの少なくとも１つは前記道路地図のうちの１つまたは複数の道路について異なりうることを特徴とする請求項８４に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、滑らかで連続したナビゲートの動きの外観を提供するように、オブジェクトのイメージにわたってズームおよびパンなどのナビゲートするための方法および装置に関する。
【背景技術】
【０００２】
ほとんどの従来のグラフィカルコンピュータユーザインターフェース（ＧＵＩ）は、固定空間スケール（ｆｉｘｅｄ  ｓｐａｃｉａｌ  ｓｃａｌｅ）の視覚構成要素（ｖｉｓｕａｌ  ｃｏｍｐｏｎｅｎｔ）を使用するように設計されるが、これまで長い間、視覚構成要素はディスプレイ上に固定空間スケールを持たないが、実際にはパンならびに／あるいはズームインまたはズームアウトが可能なように表現および操作可能であると認識されてきた。イメージ上でズームインおよびズームアウトするための機能は、例えば地図の表示、新聞などのテキストレイアウトのブラウジング、デジタル写真の表示、設計図または図の表示、および他の大規模データセットの表示などに関連して望ましいものである。
【０００３】
Ｍｉｃｒｏｓｏｆｔ  Ｗｏｒｄ、Ａｄｏｂｅ  Ｐｈｏｔｏ  Ｓｈｏｐ、Ａｄｏｂｅ  Ａｃｒｏｂａｔなどの多くの既存のコンピュータアプリケーションには、ズーム可能な構成要素が含まれる。一般にこれらのコンピュータアプリケーションによって提供されるズーム機能は、ユーザがソフトウェアと対話する上でそれほど重要な側面ではなく、ズーム機能は時折使用されるだけである。これらのコンピュータアプリケーションは、ユーザがイメージ全体にわたって滑らかに連続してパンできるように（例えば、スクロールバーまたはカーソルを使用して、表示されたイメージを左、右、上、または下に移動させる）するものである。しかしながら、こうしたコンピュータアプリケーションに伴う重要な問題は、ユーザが滑らかに連続してズームできないことである。実際には、１０％、２５％、５０％、７５％、１００％、１５０％、２００％、５００％などの、ズームインの離散的ステップが提供される。ユーザがカーソルを使用して所望のズームを選択すると、イメージはこれに応答して、選択されたズームレベルに急峻に変化する。
【０００４】
インターネットベースのコンピュータアプリケーションには、望ましくない品質の不連続ズームも存在する。www.mapquest.comウェブサイトの基礎となるコンピュータアプリケーションがこの点を例示している。ＭａｐＱｕｅｓｔウェブサイトでは、ユーザが１つまたは複数のアドレスを入力すると、これに応答して道路地図のイメージを受信できる。図１〜４は、米国ニューヨーク州ロングアイランドの地域地図の照会に応答してＭａｐＱｕｅｓｔウェブサイトから取得できるイメージの例である。ＭａｐＱｕｅｓｔウェブサイトでは、ユーザは１０レベルなどの離散レベルまでズームインおよびズームアウトすることができる。図１は、およそ１００メートル／ピクセルのズームレベル５でのレンダリングである。図２は、約３５メートル／ピクセルのズームレベル６のイメージである。図３は、約２０メートル／ピクセルのズームレベル７のイメージである。図４は、約１０メートル／ピクセルのズームレベル９のイメージである。
【０００５】
図１〜４を比較するとわかるように、ズームレベル間の急峻な遷移により、ズームアウト時の突然かつ急峻な詳細の損失、およびズームイン時の突然かつ急峻な詳細の追加が発生する。例えば図１（ズームレベル５）には、一般（ｌｏｃａｌ）、２次（ｓｅｃｏｎｄａｒｙ）、または連絡（ｃｏｎｎｅｃｔｉｎｇ）の道路は見られないが、すぐ次のズームレベルである図２には、２次および連絡の道路が突然現れる。ＭａｐＱｕｅｓｔウェブサイトを使用する場合、こうした急峻な不連続性は非常に不快である。しかしながら、ＭａｐＱｕｅｓｔソフトウェアアプリケーションが、ズームレベル５（図１）で例えば一般道路の表示ができるように修正されたとしても、結果は依然として不満足であろうということに留意されたい。地図の視覚密度は、あるズームレベルで結果が満足となる（例えば図３のレベル７）ようにズームレベルに応じて変化するが、ズームインすると、道路が密集しておらず地図が過度にまばらに見える場合がある。ズームアウトすると、道路は最終的に互いに混ざり合い、個々の道路が区別できないような隙間のない巣（ｎｅｓｔ）がすぐに形成される。
【０００６】
道路地図のイメージ上に滑らかで連続したズーミングを提供するための機能は、道路カテゴリに関連付けられた異なる粗さのレベルによる問題が多い。米国の道路には、Ａ１：主要高速道路、Ａ２：主要道路、Ａ３：高速州道、２次道路、および連絡道路、Ａ４：一般道路、市街路、および地方道路、Ａ５：未舗装道路という、およそ５つの道路カテゴリ（米国国勢調査局によって配布されるＴｉｇｅｒ／Ｌｉｎｅ  Ｄａｔａに基づいて分類された場合）がある。これらの道路は全体オブジェクト（すなわち道路地図）の要素とみなすことができる。道路要素の粗さは、Ａ３道路よりもＡ４道路の方がかなり多いこと、Ａ２道路よりもＡ３道路の方がかなり多いこと、およびＡ１道路よりもＡ２道路の方がかなり多いことから表れる。加えて、道路の物理的寸法（例えばそれらの幅）は、大幅に異なる。Ａ１道路は約１６メートル幅、Ａ２道路は約１２メートル幅、Ａ３道路は約８メートル幅、Ａ４道路は約５メートル幅、およびＡ５道路は約２．５メートル幅とすることができる。
【０００７】
ＭａｐＱｕｅｓｔコンピュータアプリケーションは、特定のズームレベルで適切であると思われる道路カテゴリのみを表示することによって、これらの異なる粗さのレベルに対処する。例えば、国家規模のビューではＡ１道路のみが表示され、州規模のビューではＡ１およびＡ２道路が表示され、群規模のビューではＡ１、Ａ２、およびＡ３道路が表示される可能性がある。たとえＭａｐＱｕｅｓｔが道路地図の連続したズーミングができるように修正されたとしても、この手法は混乱させる視覚的に不快な、ズーミング中の道路カテゴリの突然の出現および消失につながるであろう。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
前述の内容に鑑み、当技術分野では、サイズまたは重要性に基づくオブジェクトの要素間の視覚的な相違を保持しながらも、イメージの円滑で連続するズーミングを可能にする、複雑なオブジェクトのイメージをナビゲートするための新しい方法および装置が求められている。
【課題を解決するための手段】
【０００９】
本発明の１つまたは複数の態様によれば、少なくとも１つのオブジェクトの少なくともいくつかの要素が、ズーミングに関連付けられた１つまたは複数のズームレベルに非物理的に比例するように拡大および／または縮小される、少なくとも１つのオブジェクトを有するイメージのズームインまたはズームアウトを含む、様々なアクションを実行するための方法および装置が企図されている。
【００１０】
非物理的に比例するスケーリングは、公式ｐ＝ｃ・ｄ・ｚａで表すことが可能であり、この式で、ｐは、ズームレベルでのオブジェクトの１つまたは複数の要素のピクセル単位での線形サイズであり、ｃは定数であり、ｄはオブジェクトの１つまたは複数の要素の物理単位での線形サイズであり、ｚは物理的線形サイズ／ピクセルの単位でのズームレベルであり、ａはａ≠−１のスケール指数である。
【００１１】
非物理的スケーリングの下では、ズームレベルｚ０からｚ１の範囲内でスケール指数ａは−１に等しくなく（通常は−１＜ａ＜０）、ｚ０はｚ１よりも下位の物理線形サイズ／ピクセルである。好ましくは、ｚ０およびｚ１のうちの少なくとも１つが、オブジェクトの１つまたは複数の要素に対して異なる場合がある。ａ、ｃ、およびｄは要素によっても異なる場合があることに留意されたい。
【００１２】
少なくとも１つのオブジェクトの少なくともいくつかの要素を、ズーミングに関連付けられた１つまたは複数のズームレベルに物理的に比例するように、拡大および／または縮小することもできる。物理的に比例するスケーリングは、公式ｐ＝ｃ・ｄ／ｚで表すことが可能であり、この式で、ｐは、ズームレベルでのオブジェクトの１つまたは複数の要素のピクセル単位での線形サイズであり、ｃは定数であり、ｄは物理単位でのオブジェクトの１つまたは複数の要素の線形サイズであり、ｚは物理的線形サイズ／ピクセルの単位でのズームレベルである。
【００１３】
本書における前述および／または後述の方法および装置は、標準デジタル回路、アナログ回路、ソフトウェアおよび／またはファームウェアプログラムを実行するように動作可能な任意の既知のプロセッサ、プログラム可能デジタルデバイスまたはシステム、プログラム可能アレイ論理デバイス、あるいは上記の任意の組合せなどの、任意の既知の技術を使用して達成可能であることに留意されたい。本発明は、好適な記憶媒体に格納するためおよび処理ユニットによって実行するためのソフトウェアプログラムでも具体化することができる。
【００１４】
オブジェクトの要素は、粗さ（ｃｏａｒｓｅｎｅｓｓ）の程度が異なる可能性がある。例えば、前述のように、道路地図オブジェクトの要素の粗さは、Ａ３道路よりもＡ４道路の方がかなり多いこと、Ａ２道路よりもＡ３道路の方がかなり多いこと、およびＡ１道路よりもＡ２道路の方がかなり多いことから表れる。道路カテゴリにおける粗さの程度は、平均道路長さ、交差点頻度、および最大湾曲などの特性にも表れる。他のイメージオブジェクトの要素の粗さも他の面で現れるが、多すぎてすべてを列挙できない。したがって、所与の所定のイメージにおける要素のスケーリングは、（ｉ）こうした要素の粗さの程度、および（ｉｉ）所与の所定のイメージのズームレベルのうちの少なくとも１つに基づいて、物理的に比例するかまたは非物理的に比例する可能性がある。例えば、オブジェクトは道路地図とすることが可能であり、オブジェクトの要素は道路とすることが可能であり、異なる粗さの程度は道路階層とすることが可能である。したがって、所与の所定のイメージにおける所与の道路のスケーリングは、（ｉ）所与の道路の道路階層、および（ｉｉ）所与の所定のイメージのズームレベルに基づいて、物理的に比例するかまたは非物理的に比例する可能性がある。
【００１５】
本発明の１つまたは複数の他の態様によれば、ズームレベルが異なる道路地図の複数の事前レンダリングされたイメージをクライアント端末で受信するアクションと、クライアント端末でズーミング情報を含む１つまたは複数のユーザナビゲーションコマンドを受信するアクションと、クライアント端末上での中間イメージの表示が滑らかなナビゲーションの外観を提供するように、ナビゲーションコマンドのズーミング情報に対応する中間ズームレベルの中間イメージを取得するために、２つまたはそれ以上の事前レンダリングされたイメージをブレンドするアクションとを含む、様々なアクションを実行するための方法および装置が企図される。
【００１６】
本発明の１つまたは複数の他の態様によれば、ズームレベルが異なる少なくとも１つのオブジェクトの複数の事前レンダリングされたイメージをクライアント端末で受信するアクションであって、この少なくとも１つのオブジェクトのうちの少なくともいくつかの要素は複数の所定のイメージを作成するために拡大および／または縮小され、このスケーリングは（ｉ）ズームレベルに物理的に比例する、および（ｉｉ）ズームレベルに非物理的に比例する、のうちの少なくとも１つである、受信するアクションと、クライアント端末でズーミング情報を含む１つまたは複数のユーザナビゲーションコマンドを受信するアクションと、ナビゲーションコマンドのズーミング情報に対応する中間ズームレベルの中間イメージを取得するために、２つまたはそれ以上の事前レンダリングされたイメージをブレンドするアクションと、クライアント端末上に中間イメージを表示するアクションとを含む、様々なアクションを実行するための方法および装置が企図される。
【００１７】
本発明の１つまたは複数の他の態様によれば、ズームレベルが異なる道路地図の複数の事前レンダリングされたイメージを通信チャネルを介してクライアント端末に送信するアクションと、クライアント端末で複数の事前レンダリングされたイメージを受信するアクションと、クライアント端末を使用してズーミング情報を含む１つまたは複数のユーザナビゲーションコマンドを発行するアクションと、クライアント端末上での中間イメージの表示が滑らかなナビゲーションの外観を提供するように、ナビゲーションコマンドのズーミング情報に対応する中間ズームレベルの中間イメージを取得するために、２つまたはそれ以上の事前レンダリングされたイメージをブレンドするアクションとを含む、様々なアクションを実行するための方法および装置が企図される。
【００１８】
本発明の１つまたは複数の他の態様によれば、ズームレベルが異なる少なくとも１つのオブジェクトの複数の事前レンダリングされたイメージを通信チャネルを介してクライアント端末に送信するアクションであって、この少なくとも１つのオブジェクトのうちの少なくともいくつかの要素は複数の所定のイメージを作成するために拡大および／または縮小され、このスケーリングは（ｉ）ズームレベルに物理的に比例する、および（ｉｉ）ズームレベルに非物理的に比例する、のうちの少なくとも１つである、送信するアクションと、クライアント端末で複数の事前レンダリングされたイメージを受信するアクションと、クライアント端末を使用してズーミング情報を含む１つまたは複数のユーザナビゲーションコマンドを発行するアクションと、ナビゲーションコマンドのズーミング情報に対応する中間ズームレベルの中間イメージを取得するために、２つの事前レンダリングされたイメージをブレンドするアクションと、クライアント端末上に中間イメージを表示するアクションとを含む、様々なアクションを実行するための方法および装置が企図される。
【００１９】
他の態様、特徴、および利点は、当業者であれば添付の図面と共に本明細書について説明すれば明らかとなろう。
【００２０】
図面に示された形は本発明を例示するためのものであり、本発明は図示された精密な配置構成および手段に限定されるものでないことを理解されよう。
【発明を実施するための最良の形態】
【００２１】
次に図面を参照すると、同じ番号は同じ要素を示し、図５〜１１には米国ニューヨーク州ロングアイランドの道路網を表す一連のイメージが示されており、それぞれのイメージは異なるズームレベル（または解像度）である。本発明がどのように実施されるかについての技術的な詳細を掘り下げる前に、情報の完全性を維持しながら、本発明を使用した結果として生じる望ましい特徴、すなわち少なくとも滑らかで連続したナビゲーションの外観、特にズーミングに関連して、これらのイメージについて説明する。
【００２２】
以下で説明する本発明の様々な態様は、道路地図イメージのナビゲーション以外のコンテキストで適用可能であることに留意されたい。実際、本発明が使用可能なイメージ及び実装の範囲は、数が多いためにその全体を列挙することはできない。例えば本発明の特徴は、人体の解剖図、複雑な地形図、配線図や設計図などの工学図面、遺伝子オントロジなどのイメージをナビゲートするために使用できる。しかしながら、本発明が、その要素の詳細または粗さのレベルが異なるイメージのナビゲートに対する特定の適用可能性を有することがわかっている。したがって簡潔および明瞭にするために、本発明の様々な態様は特定の例すなわち道路地図のイメージに関連して説明される。
【００２３】
滑らかで連続したズーミングの外観を特許文書で実証することは不可能であるが、この特徴は、Ｐｅｎｔｉｕｍ（登録商標）搭載のコンピュータ上で好適なソフトウェアプログラムを実行することによる実験およびプロトタイプ開発を介して実証されてきた。図５に例示された道路地図のイメージ１００Ａは、物理的な長さ／ピクセル（または物理的な線形サイズ／ピクセル）の単位で特徴付けることが可能なズームレベルである。言い換えれば、ズームレベルｚは、イメージ１００Ａの単一ピクセルが表す実際の物理的線形サイズを表す。図５では、ズームレベルは約３３４メートル／ピクセルである。当業者であれば、このズームレベルが、請求される本発明の趣旨および範囲を逸脱することなく他の単位で表すことが可能であることを理解されよう。図６は、図５と同じ道路地図のイメージ１００Ｂであるが、ズームレベルｚは約１９１メートル／ピクセルである。
【００２４】
本発明の１つまたは複数の態様によれば、本発明の１つまたは複数の態様を具体化するソフトウェアプログラムのユーザは、図５および６に示されたレベルの間でズームインまたはズームアウトすることができる。こうしたズーミングは、３３４メートル／ピクセルレベル（図５）から１９１メートル／ピクセルレベル（図６）の間、およびそれらの間の任意のレベルとの間での滑らかで連続した遷移の外観を有することに留意することが重要である。同様にユーザは、ｚ＝１０９．２メートル／ピクセル（図７）、ｚ＝６２．４メートル／ピクセル（図８）、ｚ＝３５．７メートル／ピクセル（図９）、ｚ＝２０．４メートル／ピクセル（図１０）、およびｚ＝１１．７メートル／ピクセル（図１１）などの他のレベルへとズームすることができる。ここでも有利には、これらのズームレベルおよびそれらの間の任意のレベルを介した遷移は滑らかで連続する動きの外観を有する。
【００２５】
図５〜１１に示された本発明の他の重要な特徴は、１つのレベルから他のレベルへとズームする場合に、急峻に出現または消失する細部がわずかであるかまたはないことである。図８（ズームレベルｚ＝６２．４メートル／ピクセル）に示される細部は、図５（ズームレベルｚ＝３３４メートル／ピクセル）でも見つけることができる。これは、この場合は道路地図であるイメージオブジェクトが、たとえ粗さの程度が異なる要素（すなわち道路）を含む場合であっても同様である。実際、図８の道路地図１００Ｄは、少なくとも１０２などのＡ１の高速道路、１０４などのＡ３の２次道路、および１０６などのＡ４の一般道路を含む。これらの詳細は、Ａ４の一般道路１０６でさえ、図５のイメージ１００Ａにも依然として見られるが、図８のイメージ１００Ｄと比較すると大幅にズームアウトされている。
【００２６】
さらに、ズームレベルｚ＝３３４メートル／ピクセル（図５）ではＡ４の一般道路１０６が見られるにもかかわらず、Ａ１、Ａ２、Ａ３、およびＡ４道路を互いに見分けることができる。レンダリングされたイメージ１００Ａにおけるこうした道路に与えられた相対的重みと相対して、Ａ１の主要高速道路１０２とＡ２の主要道路１０８の区別でさえも互いに見分けられる。
【００２７】
有利には、ユーザが、例えば、図１０のイメージ１００Ｆに示されるようなズームレベルｚ＝２０．４メートル／ピクセルまでズームインを続行した場合、道路階層間を区別する機能も維持される。Ａ１の主要高速道路１０２の重みは、図８のズームレベルｚ＝６２．４メートル／ピクセルに比べて大幅に増加するが、Ａ４の一般道路１０６、またはさらにはＡ５の未舗装道路などの他の詳細を消してしまうほどまでには増加しない。それでも、Ａ４の一般道路１０６などの低い階層レベルの道路の重みは、図８のズームレベルｚ＝６２．４メートル／ピクセルでのその相対道路の重みに比べて、大幅に増加する。
【００２８】
したがって、図５に示されるズームレベルと図１１に示されるズームレベルとの間のダイナミックレンジが相当にあり、詳細はほぼ一貫したまま（すなわち、滑らかにズームしている間に突然現れたり消えたりする道路がない）であっても、ユーザが所与のズームレベルで取得しようとしている情報が、望ましくないアーティファクト（ａｒｔｉｆａｃｔ）によって隠されることはない。例えばズームレベルｚ＝３３４メートル／ピクセル（図５）で、ユーザはどのような主要高速道路が存在しており、どの方向に延在しているかについて、概略的に知りたい場合がある。この情報は、たとえＡ４の一般道路１０６が表示されていても、容易に得ることができる。ズームレベルｚ＝６２．４メートル／ピクセル（図８）で、ユーザは、特定のＡ１の主要高速道路１０２またはＡ２の主要道路１０８が特定の町または区域をサービス対象としているかどうかを知りたい場合がある。ここでもユーザは、Ａ４の一般道路１０６、またはさらにはＡ５の未舗装道路の存在および範囲などの、他のより詳細な情報に妨害されることなく、この情報を得ることができる。最終的に、ズームレベルｚ＝１１．７メートル／ピクセルで、ユーザは１１２などの特定のＡ４の一般道路を見つけることに関心を持ち、Ａ１主要高速道路１０２などのかなり大規模な道路に妨害されることなくこれを実行することができる。
【００２９】
前述の本発明の様々な態様のうちの１つまたは複数を達成するために、１つまたは複数のコンピューティングデバイスが、コンピューティングデバイスに適切なアクションを実行させる１つまたは複数のソフトウェアプログラムを実行することが企図される。これに関して、次に、好ましくは１つまたは複数のコンピューティングデバイスおよび／または関連機器によって実行されるプロセスステップを示す流れ図である、図１２〜１３を参照する。
【００３０】
このプロセス流れは、市販のコンピューティング機器（Ｐｅｎｔｉｕｍ（登録商標）搭載コンピュータなど）によって実行されることが好ましいが、このプロセスステップは、請求される本発明の趣旨および範囲を逸脱することなく、任意のいくつかの他の技法を使用して実行することができる。実際に、使用されるハードウェアは、標準デジタル回路と、アナログ回路と、ソフトウェアおよび／またはファームウェアプログラムを実行するように動作可能な任意の既知のプロセッサと、プログラム可能読み取り専用メモリ（ＰＲＯＭ）、プログラム可能アレイ論理デバイス（ＰＡＬ）などの、１つまたは複数のプログラム可能デジタルデバイスまたはシステムと、上記の任意の組合せと、その他などの、任意の他の既知または以下に展開される技法を使用して、実装することができる。さらに、本発明の方法は、任意の既知または以下に展開される媒体上に格納可能なソフトウェアプログラムで具体化することができる。
【００３１】
図１２は、アクション２００で（それぞれが異なるズームレベルまたは解像度の）複数のイメージが作成され、ズーミングなどの滑らかなナビゲーションの外観を達成するために２つまたはそれ以上のイメージがブレンドされる（アクション２０６）、本発明の実施形態を示す図である。本発明を実施するために必要ではないが、図１２に示された手法はサービスプロバイダとクライアントとの関係に関連して使用されることが企図される。例えばサービスプロバイダは、複数の事前レンダリングされたイメージを作成し（アクション２００）、そのイメージをユーザのクライアント端末がインターネットなどの通信チャネルを介して使用できるようにする（アクション２０２）ように、リソースを拡張する。代替として、事前レンダリングされたイメージは、ユーザが自分のコンピュータにロードおよび実行するアプリケーションプログラムの組み込み部分または関連部分とすることもできる。
【００３２】
ブレンド手法を使用する場合、イメージオブジェクトが道路地図である場合に、３０メートル／ピクセル、５０メートル／ピクセル、７５メートル／ピクセル、１００メートル／ピクセル、２００メートル／ピクセル、３００メートル／ピクセル、５００メートル／ピクセル、１０００メートル／ピクセル、および３０００メートル／ピクセルのズームレベルで、イメージセットが適切に動作することが、実験を通じてわかってきた。しかしながら、本発明の範囲を逸脱することなく、任意数の解像度で任意数のイメージが使用可能であることに留意されたい。実際に、特定のズームレベルが前述の例とは異なる、より多いかまたは少ない数のイメージによって、他のコンテキストで他のイメージオブジェクトが最適に働く場合がある。
【００３３】
クライアント端末がイメージをどのように取得するかにかかわらず、ズーミングコマンドなどのユーザが開始するナビゲーションコマンドに応答して（アクション２０４）、好ましくはクライアント端末は、ナビゲーションコマンドと一致する中間解像度イメージを作成するために２つまたはそれ以上のイメージをブレンドするように動作可能である（アクション２０６）。このブレンディングは、その開示全体が参照により本明細書に組み込まれた文献（例えば、Lance Williams, Pyramidal Parametrics, Computer Graphics, Proc. SIGGRAPH '83, 17(3):1-11 (1983)参照）によって説明された、周知のトリリニア補間技法などのいくつかの方法によって実施可能である。双３次（ｂｉｃｕｂｉｃ）線形補間などのイメージを補間するための他の手法も本発明に関連して有用であり、さらに他の手法も今後開発される可能性がある。本発明は、これらのブレンディング方法のうちの任意の特定の１つを必要としないかまたはこれに依存しないことに留意されたい。例えば図８に示されるように、ユーザは６２．４メートル／ピクセルのズームレベルまでナビゲートしたい場合がある。このズームレベルは２つの事前レンダリングされたイメージの間（例えばこの例では、ズームレベル５０メートル／ピクセルとズームレベル７５メートル／ピクセルとの間）とすることが可能であり、所望のズームレベル６２．４メートル／ピクセルは、トリリニア補間技法を使用して達成することができる。さらに、前述のようなブレンディング方法を使用して、５０メートル／ピクセルと７５メートル／ピクセルとの間の任意のズームレベルを取得することも可能であり、これが十分即時に実行されれば滑らかで連続したナビゲーションの外観が得られる。ブレンディング技法は、図９に示された３５．７メートル／ピクセルレベルなどの、他のズームレベルまで実行することができる。こうしたケースでは、ブレンディング技法は、前述の例の３０メートル／ピクセルと５０メートル／ピクセルとの間の事前レンダリングされたイメージとして実行することができる。
【００３４】
前述のブレンディング手法は、本発明が実行される処理ユニットの計算能力が、滑らかなナビゲーションのための高イメージフレームレートを達成するために、（ｉ）第１のインスタンスでレンダリング操作を実行する、および／または（ｉｉ）「実行時（ｊｕｓｔ−ｉｎ−ｔｉｍｅ）」または「実行中」（例えばリアルタイム）にイメージレンダリングを実行するのに、十分に高くない場合に、使用することができる。しかしながら後述のように、本発明の他の諸実施形態は、ブレンディングおよび／または高フレームレートアプリケーション用にクライアントターミナルでレンダリング可能な、既知または以下に展開される高性能処理ユニットの使用を企図する。
【００３５】
図１３のプロセス流れは、本発明による、好ましくは１つまたは複数のイメージを作成するように実行される詳細なステップおよび／またはアクションを示す。アクション２２０では、任意の既知または以下に展開される技法を使用してイメージオブジェクト（１つまたは複数）に関する情報が取得される。通常、こうしたイメージオブジェクトは、多角形、線、点などの適切なプリミティブを使用してモデル化されてきた。例えば、イメージオブジェクトが道路地図の場合、任意のＵｎｉｖｅｒｓａｌ  Ｔｒａｎｓｖｅｒｓｅ  Ｍｅｒｃａｔｏｒ（ＵＴＭ）ゾーン内の道路のモデルが容易に取得できる。モデルは通常、ゾーン内の道路を含む（任意の座標系内の）線セグメントのリストの形である。リストは、ピクセル（空間）ドメイン内の所与のプリミティブの重み（例えば見かけまたは実際の厚さ）を決定するためのある一定の技法を組み込んでいる限り、任意の既知または以下に展開されるレンダリングプロセスを使用して、空間ドメイン内のイメージ（ピクセルイメージ）に変換することができる。引き続き前述の道路地図の例を見ると、レンダリングプロセスは、空間ドメイン内の道路地図の道路をモデル化する線の重みを決定するためのある一定の技法を組み込むものとする。これらの技法について、以下で説明する。
【００３６】
アクション２２２（図１３）で、オブジェクトの要素が分類される。道路地図オブジェクトの場合、この分類は既存のカテゴリ、すなわちＡ１、Ａ２、Ａ３、Ａ４、およびＡ５を認識する形を取ることができる。実際、これらの道路要素は異なる粗さの程度を有し、以下で説明するように、この分類に基づいて様々にレンダリングすることができる。アクション２２４では、ズームレベルに基づいて、異なる道路要素に数学的スケーリングが適用される。以下でより詳細に説明するように、数学的スケーリングは要素分類に基づいて異なっていてもよい。
【００３７】
背景として、地図の道路などのイメージ要素をレンダリングするためには、実物理スケーリングおよびピクセル幅の事前設定という２つの従来技法がある。実物理スケーリング技法は、異なるスケールで道路の実物理イメージを表示しているかのように道路地図がレンダリングされることを指示する。例えばＡ１高速道路は１６メートル幅であり、Ａ２道路は１２メートル幅であり、Ａ３道路は８メートル幅であり、Ａ４道路は５メートル幅であり、Ａ５道路は２．５メートル幅であるとすることができる。これは地図の小さな区域にズームインする場合は見る人に受け入れられるが、ズームアウトする場合は、主要な道路も主要でない道路もすべてが薄すぎて見えなくなる。何らかのズームレベル、例えば州レベル（例えば約２００メートル／ピクセル）では、すべての道路がまったく見えなくなる。
【００３８】
ピクセル幅の事前設定手法は、あらゆる道路が、ディスプレイ上の１ピクセル幅などのある一定のピクセル幅であることを指示する。高速道路などの主要道路は、例えば２ピクセル幅などにすることによって強調できる。残念ながらこの手法では、ズームインおよびズームアウトする際に地図の視覚密度を変化させる。例えば小規模な群レベルなどの何らかのズームレベルでは、この結果は満足のいくものである。しかしながら、ズームインした場合、道路は濃くならずに地図全体がまばらに見えてしまう。さらにズームアウトした場合、道路は互いに混ざり合い、個々の道路が区別できないような隙間のない巣がすぐに形成されてしまう。
【００３９】
本発明の１つまたは複数の態様によれば、アクション２２４で、イメージは、以下でより詳細に説明するパラメータに依存して、（ｉ）ズームレベルに物理的に比例する、または（ｉｉ）ズームレベルに非物理的に比例する、のいずれかで、少なくともいくつかのイメージ要素が拡大および／または縮小されるように作成される。
【００４０】
スケーリングが「ズームレベルに物理的に比例する」ということは、要素のサイズが人間の目からの距離に伴って変化するように見える場合、道路幅を表すピクセル数がズームレベルと共に増加または減少することを意味することに留意されたい。透視画法（ｐｅｒｓｐｅｃｔｉｖｅ）の公式で、物理サイズｄのオブジェクトの見かけの長さｙが与えられた場合、
ｙ＝ｃ・ｄ／ｘ
となり、ここでｃは有角透視を決定する定数であり、ｘは見る人からのオブジェクトの距離である。
【００４１】
本発明では、表示ピクセルｐにおける物理線形サイズｄ’のオブジェクトの線形サイズは、
ｐ＝ｄ’・ｚａ
であり、ここでｚは物理線形サイズ／ピクセル（例えばメートル／ピクセル）の単位のズームレベルであり、ａは指数（ｐｏｗｅｒ  ｌａｗ）である。ａ＝−１およびｄ’＝ｄの場合（オブジェクトの実物理線形サイズ）、この式は寸法的に正しく、ｐ＝ｙおよびｚ＝ｘ／ｃで透視画法の公式に等しくなる。これは、物理的ズーミングと透視画法変換との間の等しさを表し、ズームインはオブジェクトを見る人に近づけることに等しく、ズームアウトはオブジェクトを遠ざけることに等しい。
【００４２】
非物理的スケーリングを実施するためには、ａを−１以外の指数に設定し、ｄ’を実物理線形サイズｄ以外の物理線形サイズに設定することができる。道路地図のコンテキストでは、ｐはピクセル単位で表示される道路の幅を表し、ｄ’は物理単位の帰属（ｉｍｐｕｔｅｄ）幅を表すことが可能であり、「ズームレベルに非物理的に比例する」とは、表示ピクセル単位での道路幅が、ズームレベルに物理的に比例する以外の方法で、ズームレベルと共に増加または減少する、すなわちａ≠−１であることを意味する。スケーリングは、ある一定の望ましい結果を達成するという点で歪曲される。
【００４３】
「線形サイズ」とは、１次元サイズを意味することに留意されたい。例えば、任意の２次元オブジェクトを想定し、その「線形」サイズを２倍にする場合、その領域は４＝２２だけ増える。２次元の場合、オブジェクトの要素の線形サイズは長さ、幅、半径、直径、および／またはユークリッド平面上のルーラで読み取ることが可能な任意の他の寸法を含むことができる。線の太さ、線の長さ、円またはディスクの直径、多角形の１辺の長さ、および２点間の距離は、すべて線形サイズの例である。この意味で、２次元の「線形サイズ」は、２Ｄユークリッド平面上にあるオブジェクトの、識別された２点間の距離である。例えば線形サイズは、（ｄｘ２＋ｄｙ２）の平方根を取ることによって算出可能であり、この式でｄｘ＝ｘ１−ｘ０、ｄｙ＝ｙ１−ｙ０、および識別された２点はデカルト座標（ｘ０，ｙ０）および（ｘ１，ｙ１）によって得られる。
【００４４】
「線形サイズ」の概念は、必然的に２次元より上の次元まで延長され、例えば容積オブジェクトを想定すると、その線形サイズを２倍にすることは、容積が８＝２３だけ増えることを意味する。同様の線形サイズの測量は、球体の表面などの非ユークリッド空間にも定義することができる。
【００４５】
任意の指数ａ＜０は、要素のレンダリングサイズをズームアウト時に減少させ、ズームイン時に増加させる。ａ＜−１の場合、要素のレンダリングサイズは、ズームアウト時の比例物理スケーリングよりも速く減少することになる。その反対に、−１＜ａ＜０の場合、レンダリング要素のサイズは、ズームアウト時の比例物理スケーリングよりも遅く減少する。
【００４６】
本発明の少なくとも１つの態様によれば、ユーザが、ナビゲーション時にイメージの要素サイズにおける突然のジャンプまたは不連続性を体験することがないように、所与のオブジェクトの所与の長さについて、ｐ（ｚ）をほぼ連続させることが可能である（最も極端な不連続性、すなわちナビゲーション時に要素を突然に出現または消失させる、従来の手法とは対照的）。加えて、ｐ（ｚ）は、ズームアウトによってオブジェクトの要素が小さくなっていく（例えば、道路が狭くなっていく）、および、ズームインによってオブジェクトの要素が大きくなっていくように、ズームアウトに伴って単調に減少することが好ましい。これにより、イメージのオブジェクトに関する物性（ｐｈｙｓｉｃａｌｉｔｙ）の感覚がユーザに与えられる。
【００４７】
前述のスケーリング特徴は、Ａ１高速道路に関するピクセル単位のレンダリングされた線幅に対するメートル／ピクセル単位のズームレベルの、対数−対数グラフである図１４を参照することで、より完全に理解することができる。（ｘ軸上に対数（ｚ）およびｙ軸上に対数（ｐ）をプロットすると、ｌｏｇ（ｘａ）＝ａ・ｌｏｇ（ｘ）の関係により、プロットが直線になるので便利である。）線（道路）幅に対するズームレベルプロットの基本的特徴は、
（ｉ）ズームイン（例えば約０．５メートル／ピクセルまで）した場合、道路幅のスケーリングは、ズームレベルに物理的に比例する可能性があること、
（ｉｉ）ズームアウト（例えば約０．５メートル／ピクセルより上）した場合、道路幅のスケーリングは、ズームレベルに非物理的に比例する可能性があること、および
（ｉｉｉ）さらにズームアウト（例えば、以下でより詳細に説明するパラメータに依存して、約５０メートル／ピクセルより上）した場合、道路幅のスケーリングは、ズームレベルに物理的に比例する可能性があること、
である。
【００４８】
道路幅のスケーリングがズームレベルに物理的に比例するゾーンに関しては、ｐ＝ｄ’・ｚａのスケーリング公式が採用され、この式ではａ＝−１である。この例では、実際のＡ１高速道路の物理幅に関する妥当な値は、約ｄ’＝１６メートルである。したがって、少なくともある一定のズームレベルｚ０、例えば、ｚ０＝０．５メートル／ピクセルまでズームアウトした場合、Ａ１高速道路を表す線のレンダリング幅は、物理スケーリングに伴って単調に減少する。
【００４９】
ｚ０＝０．５のズームレベルは、その下に物理スケーリングが適用される内部スケールとなるように選択される。これにより、道路地図が実物理寸法の他の詳細スケールのＧＩＳコンテンツと組み合わされた場合の、非物理的外観を避ける。この例では、１５インチディスプレイ（１６００×１２００ピクセル解像度）上で地図スケールとして表された場合、約１：２６００のスケールに対応する、ｚ０＝０．５メートル／ピクセル、または２ピクセル／メートルである。Ａ１道路に関して妥当な実物理幅であるｄ＝１６メートルでは、レンダリングされる道路は、ズームイン（０．５メートル／ピクセルまたはそれ未満）するとその実サイズであるように表示されることになる。ズームレベル０．１メートル／ピクセルでは、レンダリングされる線は約１６０ピクセル幅である。ズームレベル０．５メートル／ピクセルでは、レンダリングされる線は３２ピクセル幅である。
【００５０】
道路幅のスケーリングがズームレベルに非物理的に比例するゾーンに関しては、ｐ＝ｄ’・ｚａのスケーリング公式が採用され、この式では−１＜ａ＜０（ズームレベルｚ０からｚ１の間）である。この例では、約ｚ０＝０．５メートル／ピクセルからｚ１＝３３００メートル／ピクセルの間で非物理スケーリングが実行される。ここでも、−１＜ａ＜０の場合、レンダリングされる道路の幅は、ズームアウトの際に比例物理スケーリングよりもゆっくりと減少する。これにより有利には、ズームアウトの際に、Ａ１道路が見えるように維持できる（さらに他の小さな道路と区別できる）。例えば図５に示されるように、Ａ１道路１０２は、ズームレベルｚ＝３３４メートル／ピクセルで見えるように維持され、他の道路と区別できる。Ａ１道路の物理幅がｄ’＝ｄ＝１６メートルであると想定すると、物理スケーリングを使用してレンダリングされる線の幅は約３３００メートル／ピクセルのズームレベルで約０．００５ピクセルとなり、事実上見えないようにレンダリングする。しかしながら、−１＜ａ＜０（この例では、ａは約−０．４７３）の非物理スケーリングを使用すると、レンダリングされる線の幅は３３００メートル／ピクセルのズームレベルで約０．８ピクセルであり、はっきり見えるようにレンダリングする。
【００５１】
ｚ１の値は、所与の道路が依然として「実際よりも大きな」重要度を有する、最もズームアウトされたスケールになるように選択されることに留意されたい。例を挙げると、米国全体が１６００×１２００ピクセルディスプレイ上にレンダリングされる場合、解像度はほぼ３３００メートル／ピクセル、すなわち３．３キロメートル／ピクセルとなる。世界全体を見る場合、米国の高速道路の重要度が国だけの表示に比べて高められると想定する理由はない。
【００５２】
したがって、上記例では約３３００メートル／ピクセルである、ｚ１より上のズームレベルでは、道路幅のスケーリングはズームレベルに物理的に比例するが、好ましくはｐ（ｚ）の連続性に関するｄ’が大きい（実幅ｄよりもかなり大きい）。このゾーンでは、ｐ＝ｄ’・ｚａのスケーリング公式が使用され、この式でａ＝−１である。ｚ１＝３３００メートル／ピクセルでレンダリングされる道路幅を連続させるために、Ａ１高速道路の新しい帰属物理幅、例えばｄ’＝１．６５キロメートルが選択される。ｚ１およびｄ’の新しい値は、好ましくは、外側のスケールｚ１で線のレンダリング幅は妥当なピクセル数となるように選択される。この場合、ディスプレイ上で国全体が見られるズームレベル（３３００メートル／ピクセル）では、Ａ１道路は、細いが依然としてはっきりと見える約１／２ピクセル幅とすることが可能であり、これは、１６５０メートル、すなわち１．６５キロメートルの帰属物理道路幅に対応する。
【００５３】
前述の内容により、ズームレベルの関数としてレンダリングされる線幅に関する、以下の特定の等式セットを提案する。
ｐ（ｚ）＝ｄ０・ｚ−１、ｚ≦ｚ０の場合
ｐ（ｚ）＝ｄ１・ｚａ、ｚ０＜ｚ＜ｚ１の場合
ｐ（ｚ）＝ｄ２・ｚ−１、ｚ≧ｚ１の場合
上記ｐ（ｚ）の形は、６つのパラメータ、ｚ０、ｚ１、ｄ０、ｄ１、ｄ２、およびａを有する。ｚ０およびｚ１は、ｐ（ｚ）のが変化するスケールをマークする。ズームインゾーン（ｚ≦ｚ０）ではズーミングは物理的（すなわち、ｚの指数は−１）であり、物理幅はｄ０であって、好ましくは実物理幅ｄに対応する。ズームアウトゾーン（ｚ≧ｚ１）でもズーミングは物理的であるが、物理幅はｄ１であり、一般にｄに対応しない。ｚ０からｚ１の間で、レンダリングされる線幅は、−１以外の値とすることが可能なａの指数でスケーリングする。ｐ（ｚ）が連続するプリファレンスが与えられた場合、ｄ１およびａを一意に決定するためにはｚ０、ｚ１、ｄ０、およびｄ２を指定すれば十分であり、これは図１４に明確に示されている。
【００５４】
Ａ１道路に関する前述の手法は、道路地図オブジェクトの他の道路要素にも適用可能である。これらのスケーリング技法をＡ１、Ａ２、Ａ３、Ａ４、およびＡ５の道路に適用する例が、図１５の対数−対数グラフに示されている。この例では、すべての道路についてｚ０＝０．５メートル／ピクセルであるが、コンテキストによっては要素間で異なる可能性がある。Ａ２道路は一般にＡ１道路よりも多少小さく、ｄ０＝１２メートルである。さらにＡ２道路は、例えば米国の州レベルでは「重要」であるため、およそ単一の州のレンダリング解像度（線形スケールでは国の約１／１０）である、ｚ１＝３１２メートル／ピクセルである。このスケールでは、１ピクセルの線幅が望ましいことがわかっているため、ｄ２＝３１２メートルは妥当な設定値である。
【００５５】
上記で概説したＡ１およびＡ２の道路についての一般的な手法を使用して、道路地図オブジェクトの残りの要素のパラメータを確立することができる。Ａ３道路の場合、ｄ０＝８メートル、ｚ０＝０．５メートル／ピクセル、ｚ１＝５０メートル／ピクセル、およびｄ２＝１００メートルである。Ａ４街路の場合、ｄ０＝５メートル、ｚ０＝０．５メートル／ピクセル、ｚ１＝２０メートル／ピクセル、およびｄ２＝２０メートルである。さらにＡ５の未舗装道路の場合、ｄ０＝２．５メートル、ｚ０＝０．５メートル／ピクセル、ｚ１＝２０メートル／ピクセル、およびｄ２＝２０メートルである。このパラメータ設定値を使用すると、Ａ５の未舗装道路はズームレベルをズームアウトしていくと、より一層街路に類似していくが、ズームインした場合、物理スケールでは半分の幅であることに留意されたい。
【００５６】
図１５の対数−対数プロットは、道路タイプ別のスケーリング動作の概要である。あらゆるスケールで、見かけの幅はＡ１＞Ａ２＞Ａ３＞Ａ４＞＝Ａ５であることに留意されたい。さらに、未舗装道路を除き、すべての指数はａ＝−０．４１付近で生じることにも留意されたい。すべての破線は−１の勾配を有し、異なる物理幅の物理スケーリングを示す。上から下の順に、これらの破線の対応する物理幅は、１．６５キロメートル、３１２メートル、１００メートル、２０メートル、１６メートル、１２メートル、８メートル、５メートル、および２．５メートルである。
【００５７】
複数の事前レンダリングされたイメージ間の補間が使用される場合、多くのケースで、結果として生じる補間と、物理的および非物理的なスケーリング式によって決定された正しいピクセル幅でのすべての線または他の基本的幾何学的要素の理想的なレンダリングとが、人間の目では区別できないか、またはほとんど区別できないことが保証できる。本発明のこの代替実施形態を理解するために、エイリアス除去（ａｎｔｉａｌｉａｓ）された線を描画する上のいくつかの背景を以下に提示する。
【００５８】
エイリアス除去された線の描画についての説明は、すべての基本的要素が線であり、線幅は前述のスケーリング式に従う、上記で詳細に説明した道路地図の例に沿って提示していく。図１６Ａを参照すると、線の水平位置がピクセルグリッドと正確に位置合わせされ、単に白い背景上にある１ピクセル幅の黒いピクセルのカラムからなるように、１ピクセル幅の垂直線が白い背景上に黒で描画される。本発明の様々な態様によれば、線幅が非整数ピクセルの場合を考慮し、これに対処することが望ましい。図１６Ｂを参照すると、線の端点は固定したままであるが、線の重みを１．５ピクセル幅まで増加した場合、エイリアス除去されたグラフィックス表示では、中央カラムの左右にあるピクセルのカラムは２５％グレーで描画される。図１６Ｃを参照すると、２ピクセル幅で、これらの側面カラムは５０％グレーで描画される。図１６Ｄを参照すると、３ピクセル幅で、側面カラムは１００％黒であり、結果として、予想通り３つの中実の黒いカラムが生じる。
【００５９】
ピクセル化されたディスプレイ上に非整数幅の線を描画するためのこの手法は、結果として、線幅の変化に伴う視覚的連続性の感覚（または錯覚）を発生させ、たとえほんのわずかのピクセル数だけ幅が異なる場合であっても、幅の異なる線が明確に区別できるようになる。一般にこの手法は、エイリアス除去された線描画として知られ、描画された線に対する垂直線にわたる強度関数の線積分（または、白い背景上の黒い線の場合、「１強度」関数）が、線幅に等しいことを保証するように設計される。この方法は、端点が正確にピクセルの中心に位置していない線、垂直以外の向きにある線、および曲線に対して、容易に一般化される。
【００６０】
図１６Ａ〜Ｄのエイリアス除去された垂直線を描画することは、一方（イメージＡ）は線が１ピクセル幅、他方（イメージＢ）は線が３ピクセル幅の、２つのイメージをアルファブレンディング（ａｌｐｈａ−ｂｌｅｎｄｉｎｇ）することによっても実施可能であることに留意されたい。アルファブレンディングは、ディスプレイ上の各ピクセルに、（１−アルファ）＊（イメージＡ内の対応するピクセル）＋アルファ＊（イメージＢ内の対応するピクセル）を割り当てる。アルファがゼロから１の間で変化すると、レンダリングされる線の有効幅は１から３ピクセルの間で滑らかに変化する。このアルファブレンディング手法は、最も一般的なケースで、イメージＡおよびＢ内の２つのレンダリングされた線幅間の差異が１ピクセル以下の場合にのみ、良好な視覚的結果を生成し、そうでない場合、線は中間幅にハロー（ｈａｌｏｅｄ）が現れる可能性がある。この同じ手法を、異なる線形サイズの点、多角形、および任意の他の基本的グラフィカル要素のレンダリングに適用することができる。
【００６１】
図１６Ａ〜Ｄに戻ると、１．５ピクセル幅の線（図１６Ｂ）および２ピクセル幅の線（図１６Ｃ）は、１ピクセル幅の線（図１６Ａ）と３ピクセル幅の線（図１６Ｄ）との間のアルファブレンディングによって構築することができる。図１７Ａ〜Ｃを参照すると、１ピクセル幅の線（図１７Ａ）、２ピクセル幅の線（図１７Ｂ）、および３ピクセル幅の線（図１７Ｃ）が任意の向きで示されている。線がピクセルグリッドと正確に位置合わせされる場合と同じ原理を、図１７Ａ〜Ｃのこの任意の向きに適用するが、良い結果を出すためには、アルファブレンディングされる線幅間の間隔が２ピクセルよりも小さい必要がある。
【００６２】
この地図の例のコンテキストでは、図１４〜１５の対数−対数プロットを参照して、事前レンダリングに解像度の異なるイメージのセットを選択することができる。例えば次に、図１４とほぼ同様の図１８を参照するが、図１８には水平線と垂直線のセットが含まれる点が異なる。水平線は、１ピクセルずつ増分する１から１０までのピクセル間の線幅を示す。垂直線は、２つの隣接する垂直線間の間隔にわたる線幅が２ピクセル以下ずつ変化するように間隔が空けられる。したがって、垂直線は事前レンダリングに好適なズーム値のセットを表し、２つの隣接するこうして事前レンダリングされたイメージ間のアルファブレンディングは、幅が連続して変化する道路を表す線をレンダリングする場合とほとんど等価の特徴を生み出すことになる。
【００６３】
図１８に示された垂直線で表される６つの解像度間の補間は、約９メートル／ピクセルおよびそれを超えて示されたスケーリング曲線を使用してＡ１高速道路を正確にレンダリングするのに十分である。約９メートル／ピクセル未満のレンダリングは、こうした表示がかなりズームインされ、表示される道路の数が非常に少ないため、事前レンダリングされたイメージ間を補間するよりも、それらをベクトル的にレンダリングする方が、計算上はより効率的（さらに、データ格納要件に関してもより効率的）になり、事前レンダリングを必要としない。約１０００メートル／ピクセルを超える解像度（こうした表示は、地球の表面の大きな部分を包含する）では、１ピクセル幅の線を使用するレンダリングであるため、最終的な事前レンダリングされたイメージだけを使用することが可能である。単一ピクセルよりも細い線は、同じピクセルをよりかすかにレンダリングする。したがって、Ａ１線が０．５ピクセル幅のイメージを作成するには、１ピクセル幅線のイメージに０．５アルファを掛けることができる。
【００６４】
実際、解像度間の各間隔にわたって、１ピクセルを超えて変化する図１５のスケーリング曲線がないように、解像度のやや大きなセットが事前レンダリングされる。許容される変化を１ピクセルまで減らすことにより、結果としてレンダリング品質を向上させることができる。とりわけ、企図および説明された（例えば、参照によりその開示全体が本明細書に組み込まれた、２００４年３月１日出願の「SYSTEM AND METHOD FOR EXACT RENDERING IN A ZOOMING USER INTERFACE」という名称の米国特許出願第１０／７９０２５３号明細書（整理番号４８９／２）参照）タイリング技法を、本発明に関連して考慮の対象とすることができる。このタイリング技法は、たとえそのレベルが事前レンダリングされたイメージと一致していない場合でも、特定のズームレベルでイメージを解決するために使用することができる。多少大きな解像度セット内の各イメージが適切な解像度で事前レンダリングおよびタイリングされた場合、その結果は、本明細書に開示されたスケーリング式に従ってすべての線の幅が連続して変化するように見える、任意の複雑さの道路地図を介してズームおよびパンでナビゲーションするための完全なシステムとなる。
【００６５】
本発明の実施に関連して使用可能な、イメージをブレンドするための他の技法に関する追加の詳細（例えば、参照によりその開示全体が本明細書に組み込まれた、２００３年６月５日出願の「SYSTEM AND METHOD FOR THE EFFICIENT, DYNAMIC AND CONTINUOUS DISPLAY OF MULTI RESOLUTIONAL VISUAL DATA」という名称の米国仮特許出願第６０／４７５８９７号参照）が見られる。本発明の実施に関連して使用可能な、ブレンディング技法に関する他の詳細（例えば、参照によりその開示全体が本明細書に組み込まれた、２００３年３月１２日出願の「SYSTEM AND METHOD FOR FOVEATED, SEAMLESS, PROGRESSIVE RENDERING IN A ZOOMING USER INTERFACE」という名称の米国仮特許出願第６０／４５３８９７号参照）で見られる。
【００６６】
有利には、本発明の前述の態様を使用して、ユーザは様々なズームレベルで滑らかで連続したナビゲーションの外観を楽しむことができる。さらに、あるレベルから別のレベルにズームする場合、詳細が急峻に出現または消失することがほとんどないかまたはまったくない。これは、最先端技術における大幅な進歩を表す。
【００６７】
本発明の様々な態様が、インターネットを介した対話型ソフトウェアアプリケーション、自動車対応ソフトウェアアプリケーションなど、多数の製品で適用可能であることが企図される。例えば本発明は、ユーザ要求に応答して地図および走行方向をクライアント端末に提供する、インターネットウェブサイトで使用可能である。代替として、本発明の様々な態様は、自動車内のＧＰＳナビゲーションシステムでも使用可能である。本発明は、医療用イメージング機器に組み込むことも可能であり、これによって、例えば患者の循環系、神経系などに関する詳細な情報を前述のようにレンダリングおよびナビゲートすることができる。本発明の適用範囲は多数あるため、その全体を列挙することはできないが、当業者であれば、それらが本明細書で企図され、請求された本発明の範囲内に入ることを理解されよう。
【００６８】
本発明は、レンダリングされたイメージが広告およびその他の進歩する取引のための手段を提供する、他の適用範囲に関連して使用することも可能である。本発明のこれらの態様および用途に関連する追加の詳細（参照によりその開示全体が本明細書に組み込まれた、本明細書と同日出願の「METHOD AND APPARATUS FOR EMPLOYING MAPPING TECHNIQUES TO ADVANCE COMMERCE」という名称の米国仮特許出願第６０／５５３８０３号（整理番号４８９／７）参照）も見られる。
【００６９】
本文書には付録が添付されている。この付録は、本明細書の開示の一部である。
【００７０】
本明細書では、特定の実施形態を参照しながら本発明について説明してきたが、これらの諸実施形態は本発明の原理および適用範囲を単に例示したにすぎないことを理解されよう。したがって例示的な諸実施形態には、添付の特許請求の範囲によって定義された本発明の趣旨および範囲を逸脱することなく、多数の修正が可能であること、および他の配置構成が考案可能であることを理解されよう。
【００７１】
（付録）
ＢＬＡＩＳＥ  ＨＩＬＡＲＹ  ＡＧＵＥＲＡ  Ｙ  ＡＲＣＡＳによる
ズーミングユーザインターフェースにおける正確なレンダリングのためのシステムおよび方法のための特許出願
Ｋａｐｌａｎ  ＆  Ｇｉｌｍａｎ，ＬＬＰ
代理人整理番号４８９／２
【００７２】
（書類名）明細書
（発明の名称）ズーミングユーザインターフェースにおける正確なレンダリングのためのシステムおよび方法
【００７３】
（技術分野）
本出願は、２００３年３月５日付出願の米国仮出願第６０／４５２０７５号、２００３年３月１２日付出願の米国仮出願６０／４５３８９７号、２００３年６月５日付出願の米国仮出願第６０／４７５８９７号、および２００３年５月３０日付出願の米国仮出願第６０／４７４３１３号の優先権を主張するものである。
【００７４】
本発明は、一般に、コンピュータ用のグラフィカルズーミングユーザインターフェース（ＺＵＩ）に関する。より具体的に言えば、本発明は、結果的に良好なユーザ応答性および対話フレームレート（ｉｎｔｅｒａｃｔｉｖｅ  ｆｒａｍｅ  ｒａｔｅｓ）を生じることになる、計算上効率の良い方法、ならびに、通常はイメージ品質の劣化につながる再サンプリングなし、および同様に劣化につながる他のイメージの補間なしで、最終的にベクトル描画、テキスト、および他の非グラフィックコンテンツが描画されるという意味で正確な方法の、両方で、ズーム可能なビジュアルコンテンツを累進的にレンダリングするためのシステムおよび方法である。
【００７５】
（背景技術）
現在のほとんどのグラフィカルコンピュータユーザインターフェース（ＧＵＩ）は、固定空間スケールの視覚構成要素を使用するように設計される。しかしながら、コンピュータグラフィックス分野の出現から、視覚構成要素は、ディスプレイ上に固定空間スケールを持たないがズームインまたはズームアウトが可能であるような方法で、表現および操作可能であることがわかった。ズーム可能な構成要素が望ましいことは、ごく一部を挙げると、地図の表示、新聞などの大規模な異種テキストのレイアウトのブラウジング、デジタル写真のアルバムの表示、および大規模データセットの視覚化作業など、多くの応用例で明らかである。たとえ、スプレッドシートおよびレポートなどの通常のドキュメントを表示する場合でも、ドキュメントの概要が一目でわかり、その後、関心ある領域にズームインできることがしばしば有用である。多くの現在のコンピュータアプリケーションには、Ｍｉｃｒｏｓｏｆｔ（登録商標）および他のＯｆｆｉｃｅ（登録商標）製品（「表示」メニューの下の「ズーム」）、Ａｄｏｂｅ（登録商標）Ｐｈｏｔｏｓｈｏｐ（登録商標）、Ａｄｏｂｅ（登録商標）Ａｃｒｏｂａｔ（登録商標）、ＱｕａｒｋＸＰｒｅｓｓ（登録商標）、などの、ズーム可能な構成要素が含まれる。ほとんどの場合、これらのアプリケーションはドキュメントをズームインおよびズームアウトすることが可能であるが、必ずしもアプリケーションの視覚構成要素自体はズームインおよびズームアウトしない。ドキュメント全体にわたる連続したパンが標準（すなわち、スクロールバーまたはカーソルを使用して、表示されたドキュメントを左、右、上、または下に変換する）であるが、ユーザの使いやすい方法で連続的にズームおよびパンする機能は、従来技術のシステムにはない。
【００７６】
初めに、いくつかの定義について説明する。ディスプレイは、レンダリングされたイメージをユーザに出力するために使用されるデバイスである。フレームバッファは、ディスプレイの少なくとも一部のコンテンツを動的に表現するために使用される。ディスプレイリフレッシュ速度は、物理ディスプレイまたはその一部がフレームバッファのコンテンツを使用してリフレッシュされる速度である。フレームバッファのフレームレートは、フレームバッファが更新されるレートである。
【００７７】
例えば、通常のパーソナルコンピュータでは、ディスプレイリフレッシュ速度は６０〜９０Ｈｚである。例えば、ほとんどのデジタルビデオは２４〜３０Ｈｚのフレームレートを有する。したがってデジタルビデオの各フレームは、ディスプレイがリフレッシュされる間に実際には少なくとも２回表示されることになる。複数のフレームバッファを異なるフレームレートで使用することができるため、同じディスプレイ上でほぼ同時に表示できる。例えばこれは、フレームレートの異なる２つのデジタルビデオが同じディスプレイ上の異なるウィンドウ内で再生されている場合に発生することになる。
【００７８】
ズーミングユーザインターフェース（ＺＵＩ）に伴う問題点の１つが、ユーザがズームする場合に、ビジュアルコンテンツを異なる解像度で表示しなければならないことである。この問題の理想的な解決策は、あらゆる連続したフレームにおいて、基礎となるビジュアルコンテンツに基づいて正確で新しく計算されたイメージを表示することであろう。こうした手法に伴う問題点は、ユーザがズームする場合にリアルタイムでビジュアルコンテンツの各解像度を正確に再計算することが、基礎となるビジュアルコンテンツが複雑であれば計算上実行不可能なことである。
【００７９】
前述の結果として、多くの従来技術のＺＵＩシステムでは、それぞれが同じビジュアルコンテンツの表現であるが解像度の異なる、複数の事前計算されたイメージを使用する。本発明者等は、それぞれのこうした異なる事前計算されたイメージを、詳細レベル（ＬＯＤ）と呼ぶ。図１に示された、概念上は解像度が減少していくイメージのスタックとして編成されたＬＯＤの完全なセットは、ＬＯＤピラミッドと呼ぶ。こうした従来システムでは、ズーミングが発生するとシステムはＬＯＤ間を補間し、結果として生じるイメージを所望の解像度で表示する。この手法で計算上の問題は解決されるが、しばしばぼやけた非現実的な最終折衷イメージが表示され、異なるＬＯＤの補間を表すという事実により、しばしば情報の損失が含まれる。これらの補間エラーは、ユーザがズーミングを停止し、任意のＬＯＤの解像度と精密に一致しない選択された解像度で静止イメージを表示する機会を得た場合に、特に顕著である。
【００８０】
事前計算されたＬＯＤ間の補間に伴う他の問題点は、この手法が通常はベクトルデータを写真またはイメージデータと同じ方法で扱うことである。設計図または線画などのベクトルデータは、線、曲線、および他の基本的な形状を任意の所望の解像度でレンダリングできるレンダリングアルゴリズムを使用して、抽象命令のセットを処理することによって表示される。スケーラブルなフォントを使用してレンダリングされたテキストは、ベクトルデータの重要な特殊ケースである。イメージまたは写真データ（ビットマップフォントを使用してレンダリングされたテキストを含む）はそのように生成されないが、事前計算されたＬＯＤ間の補間によるか、またはオリジナルイメージの再サンプリングによる、いずれかで表示されなければならない。本発明者等は本明細書で、後者を非ベクトルデータと呼ぶ。
【００８１】
ズームシーケンス中に各フレームの新しい解像度でベクトルデータを再表示するためにレンダリングアルゴリズムを使用する従来技術システムは、対話フレームレートを達成するためにのみ、システム自体を単純なベクトル描画に限定しなければならない。他方で、ベクトルデータについてＬＯＤを事前計算してそれらの間を補間する従来技術システムは、ほとんどのベクトルデータレンダリングにつきものの鋭い縁部に特に補間エラーが生じやすいため、非ベクトルデータについては視覚的な品質が著しく劣化する。この劣化は、通常、ベクトルデータの特殊ケースであるテキストコンテンツでは受け入れられないものである。
【００８２】
（発明の開示）
（発明が解決しようとする課題）
本発明の目的は、ユーザが実際に自分で物理オブジェクト見てこれを自分の近くへ移動した場合に感じるようなズーミング効果を複製するＺＵＩを作成することである。
【００８３】
本発明の目的は、最終的に表示されるイメージでの補間エラーを避けるかまたはなくす適切な解像度でイメージを表示するＺＵＩを作成することである。本発明の他の目的は、ユーザが、明瞭でぼやけていないビューを維持し、対話フレームレートを維持しながら、ベクトルコンテンツ内で任意にかなりズームインできるようにすることである。
【００８４】
本発明の他の目的は、ユーザが、コンテンツの全体の概観を保持することおよび対話フレームレートを維持することの両方を実行しながら、複雑なベクトルコンテンツの外観を取得するまで任意にかなりズームアウトできるようにすることである。
【００８５】
本発明の他の目的は、ユーザが対話時にＬＯＤ間またはレンダリング品質間の遷移を知覚しないようにすることである。
【００８６】
本発明の他の目的は、イメージの一部をレンダリングするために通常必要な情報がまだ不完全である場合、ぼかしによるイメージ品質の安全な劣化を可能にすることである。
【００８７】
本発明の他の目的は、イメージの一部をレンダリングするために必要なより完全な情報が入手できるようになるにつれて、焦点をより明瞭にしていくことでイメージ品質を徐々に上げていくことである。
【００８８】
本発明の目的は、ベクトルデータおよび非ベクトルデータの両方を最適かつ別個にレンダリングすることである。
【００８９】
本発明のこれらおよび他の目的は、当業者が以下の明細書を再検討することで明らかになろう。
【００９０】
（課題を解決するための手段）
従来技術の前述および他の問題点は、ユーザが自分のイメージビューをズームインまたはズームアウト、パン、または他の方法で変更する場合に、動的に変化する解像度でイメージを表示できるようにする、ＺＵＩを実施するための混合（ｈｙｂｒｉｄ）ストラテジに関する、本発明に従って克服される。こうしたビューにおける変更をナビゲーションと呼ぶ。事前に定義された任意のＬＯＤとは異なる解像度までイメージをズーミングすることは、所望の解像度を「取り囲む」事前定義されたＬＯＤから補間された新しい解像度でイメージを表示することによって実施される。「取り囲み（ｓｕｒｒｏｕｎｄｉｎｇ）ＬＯＤ」とは、所望の解像度よりも高い最低解像度のＬＯＤおよび所望の解像度よりも低い最高解像度のＬＯＤを意味する。所望の解像度が、最高の使用可能解像度を伴うＬＯＤの解像度よりも高いか、または最低の解像度を伴うＬＯＤの解像度よりも低い場合、単一の「取り囲みＬＯＤ」しか存在しないことになる。本書では、事前計算されたＬＯＤのセットに基づく所望の解像度でのイメージの動的補間を、ミップマッピングまたはトリリニア補間と呼ぶ。後者の用語は、取り囲みＬＯＤの再サンプリングに双１次サンプリングが使用され、その後、これらの再サンプリングされたＬＯＤ間が線形補間される（すなわちトリリニア）ことを示す。（例えば、参照によりその開示全体が本明細書に組み込まれた、Lance Williams, “Pyramidal Parametrics,” Computer Graphics (Proc. SIGGRAPH ’83) 17(3): 1-11(1983)参照。）Ｗｉｌｌｉａｍｓによって紹介されたミップマッピング技法への明らかな修正またはその拡張では、取り囲みＬＯＤの再サンプリングおよび／または補間を使用する。本発明では、再サンプリングおよび補間の操作がゼロ次（最隣接）、線形、高次、またはより一般的には非線形であるかどうかは重要でない。
【００９１】
本明細書で説明された本発明によれば、ユーザが、事前定義されたＬＯＤのうちの１つの解像度ではほとんどない正確な所望の解像度を定義する場合、最終イメージは好ましくは第１に中間最終イメージを表示することによって表示される。中間最終イメージは、後述するように、イメージが改良される前に所望の解像度で表示される第１のイメージである。中間最終イメージは、従来技術を使用して所望の解像度で表示されることになるイメージに対応する可能性がある。
【００９２】
好ましい実施形態では、以下でより詳細に説明するように、中間最終イメージから最終イメージへの遷移は漸進的とすることができる。
【００９３】
強化された実施形態では、以下でより詳細に説明するように、本発明は、無理増分（すなわち、２つの整数の比として表すことが不可能な連続するＬＯＤ間の拡大または縮小係数）を含む任意の解像度増分で間隔を空けてＬＯＤを配置することができる。
【００９４】
他の強化された実施形態では、各異なるＬＯＤでのイメージの一部はタイルとして示され、こうしたタイルは、ユーザが知覚する任意の不完全さを最小限にするようにレンダリングされる。他の諸実施形態では、表示されるビジュアルコンテンツは複数のＬＯＤ（潜在的には取り囲みＬＯＤのスーパーセット）で構成され、そのそれぞれが、不完全さを隠すように表示を漸進的に最終イメージにフェードインさせるために、適切な割合および場所に表示される。
【００９５】
複数のＬＯＤでの様々なタイルのレンダリングは、システムが標準コンピュータ上で、ほとんどのラップトップおよびデスクトップのパーソナルコンピュータで使用可能な典型的なクロック速度で実行できるように、計算の複雑さを許容可能なレベル内に維持しながら、ビジュアルコンテンツの外観を最適化するように実施される。
【００９６】
本発明は、高速ズームおよびパンの際には事前定義されたＬＯＤを使用してイメージが表示されるが、ビューが十分に安定している場合は正確なＬＯＤがレンダリングおよび表示される、混合ストラテジを含む。正確なＬＯＤは、通常は事前定義されたＬＯＤとは異なる、ユーザによって選択された精密な解像度でレンダリングおよび表示される。人間の視覚系は、動きが静止している間はビジュアルコンテンツの詳細な部分に対して敏感でないため、この混合ストラテジは、連続した「完全なレンダリング」の錯覚（ｉｌｌｕｓｉｏｎ）をかなり少ない計算で生み出すことができる。
【００９７】
（発明を実施するための最良の形態）
図２は、本発明を実施するための基本的な技法を示す流れ図である。図２の流れ図は、本発明の例示的な実施形態を表し、イメージが初期の解像度で表示された場合に実行を開始する。本発明は、クライアント／サーバモデルで使用可能であるが、クライアントおよびサーバは同じマシン上または異なるマシン上にある可能性があることに留意されたい。したがって、例えばホストコンピュータ側で離散ＬＯＤのセットがリモートに格納されている可能性があり、ユーザはローカルＰＣを介してこのホストに接続することができる。使用される実際のハードウェアプラットフォームおよびシステムは、本発明にとって重要ではない。
【００９８】
流れ図は、特定解像度でのイメージの初期ビューを伴うブロック２０１で開始される。この例では、イメージは静的であると捉えられる。イメージはブロック２０２で表示される。ユーザは、例えばコンピュータマウスを動かすことによって、そのイメージをナビゲートすることができる。ブロック２０２で表示された初期ビューは、ユーザがイメージをナビゲートした場合に変化することになる。基礎となるイメージは、モーションビデオの場合などのように、それ自体が動的である可能性があるが、ここでは例示の目的で、イメージそれ自体は静的として扱われることに留意されたい。前述のように、表示されることになる任意のイメージは、テキストまたは他のベクトルデータならびに／あるいは写真および他のイメージなどの非ベクトルデータを有することも可能である。本発明および以下の説明全体は、イメージがベクトルデータまたは非ベクトルデータ、あるいはその両方を含むかどうかにかかわらず、適用可能である。
【００９９】
ブロック２０２で表示されるビジュアルコンテンツのタイプにかかわらず、この方法は、ナビゲーション入力が検出される可能性のある意思決定ポイント２０３に制御を転送する。こうした入力が検出されない場合、方法はブロック２０２にループバックし、静的なビジュアルコンテンツの表示を続行する。ナビゲーション入力が検出された場合、図に示されるように、制御はブロック２０４に転送されることになる。
【０１００】
意思決定ポイント２０３は、動きを検出する特定の信号を探すソフトウェア内の連続ループ、ハードウェア内の割り込みシステム、または任意の他の所望の方法によって実施することができる。ナビゲーション要求の検出および分析に使用される特定の技法は、本発明にとって重要ではない。使用される方法にかかわらず、システムは、イメージをナビゲートする旨の要望を示す要求を検出することができる。本明細書での説明の大半はズームに関するものであるが、諸技法はズーム、パン、またはその他の方法でのナビゲートにも適用可能であることに留意されたい。実際のところ、本明細書で説明する技法は、イメージの見方における任意のタイプの動的変形または変更に適用可能である。こうした変形には、例えば３次元変換および回転、イメージフィルタの適用、ローカルストレッチング（ｓｔｒｅｔｃｈｉｎｇ）、イメージの選択された領域に適用される動的空間ひずみ、またはより多くの情報を示す可能性のある任意の他の種類のひずみを含むことができる。他の例は、イメージ上を動かすことが可能な仮想拡大鏡であり、この仮想拡大鏡の下にあるイメージの一部が拡大される。意思決定ポイント２０３でユーザがナビゲーションを開始したことが検出された場合、ブロック２０４はイメージの新しいビューをレンダリングおよび表示し、このビューは、例えば以前に表示されたビューとは異なる解像度とすることができる。
【０１０１】
新しいビューを表示する簡単な従来技術の技法の１つは、ユーザがズームインまたはズームアウトする場合のＬＯＤの補間に基づく。選択されたＬＯＤは、所望の解像度、すなわち新しいビューの解像度を「取り囲む」２つのＬＯＤとすることができる。従来のシステムでは、補間は、ユーザがズームする間に絶えることなく実行され、ハードウェア内では速度を達成するためにしばしば直接実施される。意思決定ポイント２０５での動きの検出と、ブロック２０４での適切に補間されたイメージのほぼ即時の表示との組合せの結果、ユーザがナビゲートする間にイメージのズームが連続して表れることになる。ズームインまたはズームアウト中にイメージが移動するため、補間されたイメージは十分現実的かつ明瞭に見える。補間エラーがあっても、こうしたエラーは絶えず変化するイメージのビューによって隠されるため、人間の視覚系では最小限に検出できるにすぎない。
【０１０２】
意思決定ポイント２０５では、システムは動きがほぼ停止したか否かをテストする。これは、例えば、ビューの１つまたは複数のパラメータの変化レートを測定することを含む、様々な技法を使用して実施することができる。すなわちこの方法は、ユーザがズーミングを終了する地点に到達したか否かを確認する。意思決定ポイント２０５でこうした安定化が確認されると、制御はブロック２０６に転送され、正確なイメージがレンダリングされた後、制御はブロック２０３に戻される。このようにして、システムは、任意の所望な解像度で最終的に正確なＬＯＤを表示することになる。
【０１０３】
特にディスプレイは、２つの事前定義されたＬＯＤの補間によって単にレンダリングおよび表示されるのではなく、ブロック２０２で初期ビューが表示された際にテキストまたは他のベクトルデータをレンダリングするために使用されたオリジナルアルゴリズムを使用する、ベクトルデータの再レンダリングによってレンダリングおよび表示することができる。非ベクトルデータは、正確な要求されたＬＯＤでレンダリングおよび表示するために、再サンプリングすることもできる。要求された再レンダリングまたは再サンプリングは、所望の解像度での表示に必要な精密な解像度で実行できるだけでなく、所望のビューに基づいて計算された基礎となるコンテンツに関する表示ピクセルの正しい位置に精密に対応する、サンプリンググリッド上でも実行することができる。一例として、ディスプレイ上でのディスプレイ面における１／２ピクセルごとのイメージの変換では必要な解像度を変更しないが、サンプリンググリッドは変更するため、正確なＬＯＤの再レンダリングまたは再サンプリングが必要である。
【０１０４】
図２の前述のシステムは、ビューが変化している（例えばナビゲーションが発生している）間に、事前定義されたＬＯＤに基づく補間が使用されるが、正確なビューはビューがほぼ静止した場合にレンダリングおよび表示されるという、混合手法を表す。
【０１０５】
本明細書の説明では、レンダリングという用語は、ベクトルまたは非ベクトルデータに基づく特定ＬＯＤでのコンピュータによるタイルの生成を指す。非ベクトルデータに関しては、より高解像度または低解像度でオリジナルイメージを再サンプリングすることによって、任意の解像度でレンダリングすることが可能である。
【０１０６】
次に、図２のブロック２０６によって表される正確な最終イメージを達成するために必要な、ビジュアルコンテンツの異なる部分をレンダリングおよび表示する方法に進む。図３を参照すると、ナビゲーションが停止したと判定された場合、制御がブロック３０３に転送され、補間済みイメージはズーミング中とまったく同様に即時に表示される。ナビゲーションが停止した後に一時的に表示することができるこの補間済みイメージのことを、本発明者等は中間最終イメージ、または単に中間イメージと呼ぶ。このイメージは、取り囲みＬＯＤの補間から生成される。いくつかのケースでは、以下でより詳細に説明するように、中間イメージは２つより多くの離散ＬＯＤから、または所望の解像度を取り囲むＬＯＤ以外の２つの離散ＬＯＤから、補間することができる。
【０１０７】
中間イメージが表示されるとブロック３０４に進み、本発明者らが最終イメージと呼ぶイメージの正確なレンダリング方向への漸進的なフェードを、イメージに開始させる。最終イメージは、最終イメージが任意の事前定義されたＬＯＤの補間を含まない可能性があるという点で、中間イメージとは異なる。代わりに、最終イメージまたはその一部は、新しくレンダリングされたタイルを含むことができる。写真データの場合、新しくレンダリングされたタイルはオリジナルデータの再サンプリングの結果として生じ、ベクトルデータの場合、新しくレンダリングされたタイルは所望の解像度でのラスタ化の結果として生じることができる。
【０１０８】
ブロック３０３から３０５に直接スキップして、補間済みイメージを最終の正確なイメージに即時に交換できることにも留意されたい。しかしながら、好ましい実施形態では、ステップ３０４は、中間最終イメージから最終イメージへの切り替えが漸進的かつ滑らかに実行されるように実行される。この漸進的フェーディングは、時にはブレンディングと呼ばれ、ナビゲーションが停止した場合にイメージの焦点を漸進的に合わせていき、カメラまたは他の光学機器における自動焦点合わせと同様の効果を生み出す。この効果によって物理的に作成される錯覚は、本発明の重要な態様である。
【０１０９】
次に、イメージにおいて知覚される不規則さ、突然の変化、継ぎ目、および他の不完全さを最小限にするために、このフェーディングまたはブレンディングが実行できる方法について説明する。しかしながら、フェーディングの特定の技法が本発明にとっては重要でないこと、および当業者であれば多くの変形形態が明らかとなることを理解されよう。
【０１１０】
異なるＬＯＤは、基礎となるビジュアルコンテンツの物理的領域ごとのサンプル数が異なる。したがって、第１のＬＯＤは１インチ×１インチ領域の表示可能オブジェクトを利用し、３２×３２の単一のサンプルタイルを生成することができる。しかしながら、情報は同じ１インチ×１インチ領域を利用し、これを６４×６４サンプル、したがってより高い解像度のタイルとして表すことも可能である。
【０１１１】
本発明者等は、無理タイリング（ｉｒｒａｔｉｏｎａｌ  ｔｉｌｉｎｇ）と呼ばれる概念を定義する。本発明者等が変数ｇとして書き込むことになるタイリング細分性は、高解像度ＬＯＤでの線形タイリンググリッドサイズと、次の低解像度ＬＯＤでの線形タイリンググリッドサイズとの比として定義される。トリリニア補間を紹介するＷｉｌｌｉａｍｓの論文では、ｇ＝２である。従来技術では、これと同じｇの値が使用されてきた。ＬＯＤは、任意の様式でタイルに細分化できるが、例示的実施形態では、各ＬＯＤは一定数のサンプル（必要に応じてビジュアルコンテンツの縁部は除く）を含む正方形または矩形タイルのグリッドに細分化される。概念上、ｇ＝２の場合、図４に示されるように、ある一定のＬＯＤでの各タイルは、次に高解像度のＬＯＤでは２×２＝４タイルに「分割」される（ここでも、潜在的に縁部は除く）。
【０１１２】
細分性（ｇｒａｎｕｌａｌｉｔｙ）２のタイリングには基本的な欠点がある。通常、ユーザがタイル内のランダムなポイントでズームインした場合、ズームにおけるｇ倍ごとの増加には、ユーザのズームが向かっているポイントに近い次の高解像度のＬＯＤに対応する単一の追加のタイルをレンダリングすることが必要となる。しかしながら、ユーザがタイリンググリッド内のグリッド線上にズームインしている場合、線の両側で１つずつ、２つの新しいタイルのレンダリングが必要となる。最後に、ユーザが２本のグリッド線の交差部分にズームインしている場合、４つの新しいタイルのレンダリングが必要となる。ｇ倍ズームごとに１、２、または４つの新しいタイルを要求する、これらのイベントが、拡張ズーミングシーケンス全体にわたってランダムに点在する場合、全体の性能は変わらない。しかしながら、任意の整数細分性タイリング（すなわち、ｇは整数）におけるグリッド線は、あらゆる高解像度ＬＯＤでのグリッド線を維持する。
【０１１３】
例えば、細分性２でタイリングされた非常に大きなイメージの中心にズームインすると考えてみる。本発明者等は、このポイントの（ｘ，ｙ）座標を（１／２，１／２）とし、ビジュアルコンテンツが、コーナーが（０，０）、（０，１）、（１，０）、および（１，１）の正方形内に収まるという規則を採用する。この中心は２本のグリッド線の交差部分であるため、ユーザが各高解像度ＬＯＤに達するごとに、４つの新しいタイルをレンダリングする必要があり、その結果、この特定のポイントでのズーミングは処理速度が遅く、非効率的になる。他方で、ユーザが無理ポイント、すなわち、ｘおよびｙを２つの整数の比として表すことができないグリッドポイント（ｘ，ｙ）にズームインすると想定する。こうした数の例はｐｉ（＝３．１４１５９．．．）および２の平方根（＝１．４１４２１３．．．）である。そこで、ｇ倍ズームごとにレンダリングが必要なタイル数によって得られる１、２、および４のシーケンスが、擬似ランダム（ｑｕａｓｉ−ｒａｎｄｏｍ）である、すなわち周期的なパターンに従わないことが、容易に実証できる。この種の擬似ランダムシーケンスが性能の見地から見てより望ましいことは明らかであり、性能の見地からは、ズーミングに関して顕著なポイントはない。
【０１１４】
無理タイリングはこの問題を解決するものであり、ｇそれ自体が無理数である、通常は３、５、または１２の平方根であると解釈される。これは、所与のＬＯＤでの平均３、５、または１２タイル（それに対応して）が、次の低解像度ＬＯＤでの単一のタイル内に含まれることを意味するが、連続したＬＯＤでのタイリンググリッドは、このスキームでは、いかなるグリッド線上でももはや「一致」しないことに留意されたい（潜在的には、ビジュアルコンテンツの先端、ｘ＝０およびｙ＝０、または各軸に沿った何らかの他の事前に選択された単一グリッド線を除く）。任意の整数のｎ乗根でないように（ｐｉはこうした数である）ｇが選択された場合、ＬＯＤはいかなるグリッド線をも共有しない（ここでも、潜在的にはｘ＝０およびｙ＝０を除く）。したがって、各タイルは、次の低位ＬＯＤにある１、２、または４つのタイルとランダムに重複する可能性があることがわかるが、ｇ＝２の場合、この数は常に１である。
【０１１５】
無理タイリング細分性の場合、任意のポイントにズームインすると、１、２、または４つのタイルを要求する擬似ランダムストリームが生成され、どこにズームインする場合でも、性能は平均して均一になる。おそらく無理タイリングの最も大きな利点は、大きくズームした後のパンに関連して表れる。ユーザが大きくズームインした後にイメージをパンする場合、ある地点で、グリッド線がディスプレイ上に移動することになる。これは通常、このグリッド線の反対側の領域が、ディスプレイ上の残りの領域よりも低い解像度のＬＯＤに対応する場合であるが、これらの解像度の差異はできる限り小さいことが望ましい。しかしながら整数ｇの場合、グリッド線が多くの連続するＬＯＤにわたって重複する可能性があるため、この差異はしばしばかなり大きくなる。これにより、図６（ａ）に示されるように、ノード領域全体にわたる解像度に「深いクラック（ｃｒａｃｋ）」が生じる。
【０１１６】
他方で、無理タイリングにおけるグリッド線は隣接するＬＯＤのグリッド線とは決して重複しないため（ここでも、イメージの１コーナーに存在する可能性のある各方向の１本のグリッド線は除く場合がある）、複数のＬＯＤの解像度における不連続性は発生しない。このように相対的解像度における滑らかさが増加することで、空間的連続性の錯覚がより大きな説得力のあるものとなる。
【０１１７】
図６（ｂ）は、無理タイリング細分性によって得られる利点を示す。図６は、ビジュアルコンテンツのいくつかのＬＯＤを通る断面図を示し、各バーは矩形タイルの断面図を表す。したがって、２本のバーがある、上から２番目のレベルは、２×２＝４タイルのＬＯＤとすることができる。上から下へと描かれた曲線６０１は、ズーミング操作中の関連ＬＯＤでのビジュアルコンテンツの可視領域の境界を表し、解像度が増加する（より詳細に表すためにズームインする）と、調査中の領域は減少する。色の濃いバー（例えば６０２）は、ズームの間にすでにレンダリングされているタイルを表す。色の薄いバーはまだレンダリングされていないため、表示できない。図６（ａ）のようにタイリングが整数の場合、スペース全体にわたる解像度の突然の変化は一般的であり、ユーザがズーム後に右へパンすると、矢印によって示された空間的境界線で４つのＬＯＤが突然「終了」することに留意されたい。結果として生じるイメージは、この境界線の左側で鮮明に見え、右側では極端にぼやけることになる。無理タイリング細分性を使用して表される同じビジュアルコンテンツには、こうした解像度の「クラック」がなく、隣接するＬＯＤは、左端に示されるのを除き、タイルの境界線を共有しない。計算上、この共有境界線（ｓｈａｒｅｄ  ｂｏｕｎｄａｒｙ）は、多くてもｘ軸上に１箇所およびｙ軸上に１箇所に生じる可能性がある。図示された実施形態では、これらの共有境界線はｙ＝０およびｘ＝０に位置するが、存在する場合は任意の他の位置にも配置することができる。
【０１１８】
無理タイリング細分性の他の利点は、特にｇがそれほど大きくない有用な範囲全体では、整数よりもかなり多くの無理数があるため、ｇのより細かい制御が可能なことである。この追加の自由は、ある一定のアプリケーションのズーミング性能を調整するために役立つ。ｇが整数の無理平方根に設定された場合（ｓｑｒｔ（２）、ｓｑｒｔ（５）、ｓｑｒｔ（８））、前述の実施形態では、１つおきのＬＯＤのグリッド線が正確に位置合わせされ、ｇが無理立方根である場合、２つおきのＬＯＤが正確に位置合わせされるという具合である。これは、以下で定義されるような複合タイリングの複雑さを制限することに関して、追加の特典を与える。
【０１１９】
本発明の重要な態様は、タイルがレンダリングされる順序である。より具体的に言えば、すべての可視タイルが第１にレンダリングされるように、様々なＬＯＤの様々なタイルが最適にレンダリングされる。不可視タイルは、まったくレンダリングされない可能性がある。可視タイルセット内では、レンダリングは解像度の増加順に進行するため、低解像度ＬＯＤ内のタイルが第１にレンダリングされる。任意の特定のＬＯＤ内では、タイルはディスプレイの中心からの距離が増加する順にレンダリングされ、本発明者等はこれを窩のあるレンダリングと呼ぶ。こうしたタイルを前述の順序でソートするために、ヒープソート、クイックソート、その他の、多数のソートアルゴリズムを使用することができる。この順序付けを実施するには、タイルをレンダリングするための「要求」をソートするために、一字一語法（ｌｅｘｉｇｒａｐｈｉｃ）キーを使用することが可能であり、外側のサブキーは可視性、真ん中のサブキーは物理単位あたりのサンプルの解像度、および内側のサブキーはディスプレイの中心までの距離である。タイルレンダリング要求を順序付けするための他の方法も使用することができる。タイルの実際のレンダリングは、最適には、本明細書で説明するナビゲーションおよび表示と並行するプロセスとして実行される。レンダリングおよびナビゲーション／表示が並行プロセスとして進行する場合、たとえタイルのレンダリングが遅い場合であっても、ユーザの応答性は高いままとすることができる。
【０１２０】
次に、例示的実施形態でのタイルのレンダリングプロセスについて説明する。タイルが、ストロークベースフォントの英字タイポグラフィなどのベクトルデータを表す場合、タイルのレンダリングには、英字データをラスタ化するためのアルゴリズムの実行、および場合によってはそのデータのサーバからクライアントへの伝送が含まれる。代替として、ラスタ化アルゴリズムに供給されたデータはクライアントに送信され、クライアントはタイルをラスタ化するためのアルゴリズムを実行することができる。他の例では、関連するデジタルサンプリングされた写真データを含むタイルのレンダリングは、適切なＬＯＤでタイルを生成するためにそのデータを再サンプリングすることを含む。事前に格納された離散ＬＯＤでは、レンダリングには、後続の表示のために単にタイルをクライアントコンピュータに伝送することだけが含まれる場合がある。最終イメージ内のタイルなどの離散ＬＯＤ間にあるタイルでは、前述のようにさらにいくつかの計算が必要な場合がある。
【０１２１】
タイルがレンダリングされ、イメージが正確なイメージへのフェードを開始する場合は、常に、異なるＬＯＤからの異なるタイルの異なる組合せが実際の表示に含まれる可能性がある。したがって、表示の任意の部分が、例えばＬＯＤ  １から２０％、ＬＯＤ  ２から４０％、およびＬＯＤ  ３から４０％を含む可能性がある。表示されるタイルには関係なく、アルゴリズムは、最も必要とされる表示のためにレンダリング済みタイルを供給するのに最も好適な優先順位で、様々なＬＯＤからのタイルをレンダリングしようと試みる。レンダリング済みタイルの実際の表示について、図５を参照しながら以下でより詳細に説明する。
【０１２２】
以下では、イメージの詳細の空間的および時間的連続性を保証できるアルゴリズムを使用して、複数のＬＯＤを描画するための方法について説明する。このアルゴリズムは、同じ表示領域をカバーする低解像度タイルに優先して高解像度タイルを使用しながらも、ＬＯＤ間の鮮明な境界線を避けるための空間的ブレンディング、ならびに、使用可能になった場合（すなわち、高解像度タイルがレンダリングされた場合）は、より詳細にブレンドするための時間的に漸進的な重みのブレンディングを使用して、すべてのレンダリング済みタイルが最適に使用できるように設計される。従来技術とは異なり、このアルゴリズムおよびその変形は、結果として２つを超えるＬＯＤをディスプレイ上の所与の地点で互いにブレンドすることになり、ディスプレイ領域全体にわたって滑らかに変化するブレンディング係数を生じさせ、たとえユーザがナビゲーションを停止した後でも発展していくブレンディング係数を生じさせることができる。それにもかかわらず、この例示的実施形態では、計算上は効率的であり、部分的に透明なイメージ、または以下で明らかになるように全体の透明性がイメージ領域全体にわたって変化するイメージをレンダリングする場合に使用することができる。
【０１２３】
本明細書では、複合タイル領域、または単に複合タイルを定義する。複合タイルを定義するために、本発明者等は、互いの上に積み重ねられたすべてのＬＯＤについて考えてみる。各ＬＯＤはそれ自体のタイルグリッドを有する。その後、複合グリッドは、すべてのＬＯＤからのすべてのグリッドを単一平面に投影することによって形成される。その後、複合グリッドは、すべての異なるＬＯＤからのタイルの境界線によって定義された、異なるサイズの様々な複合タイルで構成される。これについては、図７に概念的に示されている。図７は、すべてが同じイメージを表す、７０１から７０３の３つの異なるＬＯＤからのタイルを示す。ＬＯＤ  ７０１から７０３が互いの上に積み重ねられていることが想像できよう。こうしたケースでは、これらそれぞれのＬＯＤのコーナー７５０を１列に整列させ、互いの上に積み重ねた場合、７４０で示される領域は７３０で示される領域の内部に存在することになり、７３０および７４０で示された領域は、７２０で示された領域の内部に存在することになる。図７の領域７１０は、単一の「複合タイル」７１０が存在することを示す。それぞれの複合タイルがフレームごとに検査され、通常、フレームレートは毎秒１０フレームより大きくなる可能性がある。前述のように、このフレームレートは必ずしもディスプレイのリフレッシュレートではないことに留意されたい。
【０１２４】
図５は、タイルがレンダリングされる際にフレームバッファを更新するためのアルゴリズムを示す流れ図である。図５の配置構成は、フレームバッファが更新されるごとに、表示されたイメージ内のあらゆる複合タイル上で動作するように意図される。したがって、例えばフレーム持続時間（ｆｒａｍｅ  ｄｕｒａｔｉｏｎ）が１／２０秒である場合、好ましくはスクリーン全体上の各複合タイルが１／２０秒ごとに検査および更新されることになる。複合タイルが図５のプロセスに基づいて操作される場合、複合タイルは１つまたは複数のＬＯＤで関連タイルが欠如する可能性がある。図５のプロセスは、各複合タイルを、複合タイルが内部に存在する使用可能な重ねあわされたすべてのタイルの加重平均として表示することを試みる。複合タイルは、任意の所与のＬＯＤで１つのタイル内に正確に収まるような方法で定義されるため、加重平均は各ＬＯＤの相対的比率として表すことができることに留意されたい。このプロセスは、複合タイル内の各ＬＯＤについて適切な重みを決定すること、および、前述の最終イメージに向かってイメージを漸進的にフェードさせるためにそれらの重みを空間および時間全体にわたって漸進的に変化させることを試みる。
【０１２５】
複合グリッドは、複合グリッド内のグリッドラインの任意の交差部分またはコーナーとなるように定義された複数の頂点を含む。これらは複合グリッド頂点と呼ばれる。本発明者等は、各複合グリッド頂点での各ＬＯＤの不透明度（ｏｐａｃｉｔｙ）を定義する。この不透明度は、０．０から１．０の間の重みとして表すことが可能であるため、所望の結果が完全に不透明となるイメージに関する場合、各頂点でのすべてのＬＯＤ重みの合計は、１．０となるはずである。各頂点の各ＬＯＤに関する任意の特定の時点での現在の重みは、メモリ内に維持される。
【０１２６】
頂点の重みを更新するためのアルゴリズムは、以下のように進行する。
【０１２７】
０．０から１．０の間の数値を取る以下の変数、ｃｅｎｔｅｒＯｐａｃｉｔｙ、各コーナー（タイリングが矩形グリッドの場合は４）のｃｏｒｎｅｒＯｐａｃｉｔｙ、および各縁部（タイリングが矩形グリッドの場合は４）のｅｄｇｅＯｐａｃｉｔｙは、各タイルのメモリ内に保持される。タイルが第１にレンダリングされた場合、列挙したようなそのすべての不透明度は通常１．０に設定される。
【０１２８】
描画パスの間、アルゴリズムは、最高解像度のＬＯＤから始まり、関連するＬＯＤごとに１回ずつ複合タイリングを通過する。アルゴリズムは、このタイルごとの変数に加えて、ｌｅｖｅｌＯｐａｃｉｔｙＧｒｉｄおよびｏｐａｃｉｔｙＧｒｉｄという変数も維持する。ここでも、これらの変数はどちらも０．０から１．０の間の数であり、複合タイリング内の各頂点について維持される。
【０１２９】
アルゴリズムは、最高解像度から最低解像度への順に各ＬＯＤを通過して、以下の操作を実行する。最初に、すべての頂点でｌｅｖｅｌＯｐａｃｉｔｙＧｒｉｄに０．０が割り当てられる。その後、そのＬＯＤでの各レンダリング済みタイルについて（一部がまだレンダリングされていない場合、そのＬＯＤのタイルセットのサブセットである可能性がある）、アルゴリズムは、タイルのｃｅｎｔｅｒＯｐａｃｉｔｙ、ｃｏｒｎｅｒＯｐａｃｉｔｙ、およびｅｄｇｅＯｐａｃｉｔｙ値に基づいてそのタイルに接触しているｌｅｖｅｌＯｐａｃｉｔｙＧｒｉｄの一部を以下のように更新する。
【０１３０】
頂点全体がタイルの内部にある場合、ｃｅｎｔｅｒＯｐａｃｉｔｙを使用して更新される。
【０１３１】
頂点が、例えばタイルの左端上にある場合、左のｅｄｇｅＯｐａｃｉｔｙで更新される。
【０１３２】
頂点が、例えば右上コーナーにある場合、右上のｃｏｒｎｅｒＯｐａｃｉｔｙで更新される。
【０１３３】
「更新」とは、既存のｌｅｖｅｌＯｐａｃｉｔｙＧｒｉｄ値が０．０よりも大きい場合、新しい値を最低現在値、または更新に使用される値に設定することを意味する。既存の値がゼロ（すなわちこの頂点はまだ接触されていない）の場合、ｌｅｖｅｌＯｐａｃｉｔｙＧｒｉｄ値を更新に使用される値に設定するだけである。最終結果は、各頂点位置のｌｅｖｅｌＯｐａｃｉｔｙＧｒｉｄが、更新に使用される最低非ゼロ値に設定されることになる。
【０１３４】
次にアルゴリズムは、ｌｅｖｅｌＯｐａｃｉｔｙＧｒｉｄを通過し、ホールと呼ばれるまだレンダリングされていないタイルに接触する任意の頂点を０．０に設定する。これにより、ブレンディングの空間的連続性が保証され、現在のＬＯＤで、複合タイルがホール内に収まる場合は必ず、そのホールと境を接するすべての頂点で不透明度の描画はゼロにフェードするはずである。
【０１３５】
拡張実施形態の場合、アルゴリズムは、ＬＯＤブレンディングの空間的連続性をさらに向上させるために、すべてのｌｅｖｅｌＯｐａｃｉｔｙＧｒｉｄ値を緩和（ｒｅｌａｘ）する。前述の状況は、あらゆる頂点がテントポールのようであり、そのポイントでのｌｅｖｅｌＯｐａｃｉｔｙＧｒｉｄ値がテントポールの高さとなるように、視覚化することができる。このアルゴリズムは、ホール上で隣接するすべてのポイントでのテントポールの高さはゼロであり、レンダリングされたタイルの内部では、テントポールは何らかの（おそらくは）非ゼロの値に設定されることを大いに保証する。極端な場合、レンダリング済みタイル内部のおそらくすべての値が１．０に設定される。例示の目的で、レンダリング済みタイルの近隣がまだレンダリング済みでないと想定すると、境界線値は０．０である。０．０境界線のテントポールと１．０内部のテントポールのうちの１つとの間の「マージン」がどの程度の狭さであるかは、まだ特定していない。このマージンが小さすぎる場合は、たとえブレンディングが技術上連続していても、空間全体にわたる不透明度導関数として測定された場合に遷移が急激すぎる可能性がある。緩和操作はテントを平滑にして、常に値０．０を保持するが、場合によっては他のテントポールを低くして、テント表面によって定義される関数をより平滑にする、すなわちその最大空間導関数（ｍａｘｉｍｕｍ  ｓｐａｃｉａｌ  ｄｅｒｉｖａｔｉｖｅ）を制限する。これはこの操作を実施するためにその様々な方法が使用される本発明にとって重要ではなく、１つの手法は、例えば選択的低帯域フィルタリングを使用し、ゼロはそのままにして、あらゆる非ゼロ値をその近隣の加重平均にローカルに置き換えることである。当業者であれば、他の方法も明らかとなろう。
【０１３６】
次にアルゴリズムはすべての複合グリッド頂点を通過して、各頂点でのｌｅｖｅｌＯｐａｃｉｔｙＧｒｉｄおよびｏｐａｃｉｔｙＧｒｉｄの対応する値について考慮し、ｌｅｖｅｌＯｐａｃｉｔｙＧｒｉｄが１．０−ｏｐａｃｉｔｙＧｒｉｄよりも大きい場合、ｌｅｖｅｌＯｐａｃｉｔｙＧｒｉｄは１．０−ｏｐａｃｉｔｙＧｒｉｄに設定される。その後、再度各頂点について、ｌｅｖｅｌＯｐａｃｉｔｙＧｒｉｄの対応する値がｏｐａｃｉｔｙＧｒｉｄに追加される。前述のステップにより、これによってｏｐａｃｉｔｙＧｒｉｄが１．０より上になることはない。アルゴリズムでのこれらのステップにより、使用可能であればより高解像度のＬＯＤができる限り多くの不透明度に寄与することが保証され、ホールがある場合にのみ低解像度ＬＯＤが「透き通って見える」ようにすることができる。
【０１３７】
現在のＬＯＤの走査の最終ステップは、頂点ごとの不透明度値としてｌｅｖｅｌＯｐａｃｉｔｙＧｒｉｄを使用し、実際に現在のＬＯＤで複合タイルを描画することである。拡張実施形態では、描画直前にｌｅｖｅｌＯｐａｃｉｔｙＧｒｉｄと０．０から１．０の範囲内のスカラｏｖｅｒａｌｌＯｐａｃｉｔｙ変数とを掛け合わせることが可能であり、これによって、全体のイメージをｏｖｅｒａｌｌＯｐａｃｉｔｙによって与えられた部分的透明度で描画することができる。矩形などのイメージ含有多角形を各頂点の不透明度が異なるように描画することは、標準的な手順であることに留意されたい。例えば、ＯｐｅｎＧＬまたはＤｉｒｅｃｔ３Ｄグラフィックライブラリを使用する業界標準テクスチャマッピング機能を使用して実施することができる。実際には、こうした各多角形の内部に描画される不透明度は空間的に補間されており、結果として多角形全体にわたる不透明度が滑らかに変化することになる。
【０１３８】
前述のアルゴリズムの他の拡張実施形態では、タイルは、ｃｅｎｔｅｒＯｐａｃｉｔｙ、ｃｏｒｎｅｒＯｐａｃｉｔｙ、およびｅｄｇｅＯｐａｃｉｔｙのそれらの現在の値（現在値と呼ぶ）を維持するだけでなく、ｔａｒｇｅｔＣｅｎｔｅｒＯｐａｃｉｔｙ、ｔａｒｇｅｔＣｏｒｎｅｒＯｐａｃｉｔｙ、およびｔａｒｇｅｔＥｄｇｅＯｐａｃｉｔｙと呼ばれる値の並列セット（ターゲット値と呼ぶ）も維持する。この拡張実施形態では、タイルが最初にレンダリングされる場合、現在値はすべて０．０に設定されるが、ターゲット値はすべて１．０に設定される。その後、各フレーム後に、現在値はターゲット値により近い新しい値に調整される。これは、いくつかの数式を使用して実施可能であるが、一例として、ｎｅｗＶａｌｕｅ＝ｏｌｄＶａｌｕｅ＊（１−ｂ）＋ｔａｒｇｅｔＶａｌｕｅ＊ｂで実行可能であり、この式で、ｂは０．０よりも大きく１．０よりも小さなレートである。０．０に近いｂの値は、結果として非常に低速のターゲット値への遷移を生じることになり、１．０に近いｂの値は、結果として非常に高速のターゲット値への遷移を生じることになる。この不透明度更新の方法により、ターゲット方向への指数関数的収束が生じ、時間的連続性の視覚的に好ましい印象が生じることになる。他の式で同じ結果を達成することができる。
【０１３９】
前述の内容は、本発明の好ましい実施形態を説明している。本発明はこうした好ましい実施形態に限定されず、添付の特許請求の範囲と矛盾しない様々な修正も本発明に含まれる。
【０１４０】
（図面の簡単な説明）
（図１）ＬＯＤピラミッドを示す図である（この場合、最高解像度表現を表すピラミッドの底面は５１２×５１２サンプルイメージであり、このイメージの連続する縮小が因数２で示される）。
（図２）本発明の例示的実施形態で使用するための流れ図である。
（図３）システムがズーミング後の最終イメージを表示する方法を示す、他の流れ図である。
（図４）サンプル単位でサイズが等しい矩形タイルへの各ＬＯＤの細分化を示すグリッド線が追加された、図１のＬＯＤピラミッドを示す図である。
（図５）ディスプレイ上にレンダリング済みタイルを表示するためのプロセスを示す、本発明に関連して使用するための他の流れ図である。
（図６）本明細書でより詳細に説明される、無理タイリングと呼ばれる概念を示す図である。
（図７）本明細書でより詳細に説明される複合タイルと複合タイルを構成するタイルとを示す図である。
【０１４１】
2008501160.tif 000003
【０１４２】
2008501160.tif 000004
【０１４３】
2008501160.tif 000005
【０１４４】
2008501160.tif 000006
【０１４５】
2008501160.tif 000007
【０１４６】
2008501160.tif 000008
【０１４７】
2008501160.tif 000009
【０１４８】
（書類名）明細書
（発明の名称）ズーミングユーザインターフェースにおける窩のある、シームレスな、累進的レンダリングのためのシステムおよび方法
【０１４９】
（技術分野）
本発明は、一般に、コンピュータ用のズーミングユーザインターフェース（ＺＵＩ）に関する。より具体的には、本発明は、優れたユーザ反応性および高いフレームレートを維持しながら、ズーミング環境において任意に大規模または複雑なビジュアルコンテンツを累進的にレンダリングするためのシステムおよび方法である。いくつかの状況では、これらの目標を満たすためにレンダリングの品質を一時的に劣化させる必要があるが、本発明は、人間の視覚系の良く知られた特性を活用することにより、この劣化を大規模にマスクする。
【０１５０】
（背景技術）
現在のほとんどのグラフィカルコンピュータユーザインターフェース（ＧＵＩ）は、固定空間スケールの視覚構成要素を使用するように設計される。しかしながら、コンピュータグラフィックス分野の出現から、視覚構成要素は、ディスプレイ上に固定空間スケールを持たないがズームインまたはズームアウトが可能であるような方法で、表現および操作可能であることがわかった。ズーム可能な構成要素が望ましいことは、ごく一部を挙げると、地図の表示、新聞などの大規模な異種テキストのレイアウトのブラウジング、デジタル写真のアルバムの表示、および大規模データセットの視覚化作業など、多くの応用例で明らかである。たとえ、スプレッドシートおよびレポートなどの通常のドキュメントを表示する場合でも、ドキュメントの概要が一目でわかり、その後、関心ある領域にズームインできることがしばしば有用である。多くの現在のコンピュータアプリケーションには、Ｍｉｃｒｏｓｏｆｔ（登録商標）および他のＯｆｆｉｃｅ（登録商標）製品（「表示」メニューの下の「ズーム」）、Ａｄｏｂｅ（登録商標）Ｐｈｏｔｏｓｈｏｐ（登録商標）、Ａｄｏｂｅ（登録商標）Ａｃｒｏｂａｔ（登録商標）、ＱｕａｒｋＸＰｒｅｓｓ（登録商標）、などの、ズーム可能な構成要素が含まれる。ほとんどの場合、これらのアプリケーションはドキュメントをズームインおよびズームアウトすることが可能であるが、必ずしもアプリケーションの視覚構成要素自体はズームインおよびズームアウトしない。さらにズームは通常、ユーザがソフトウェアと対話する上でそれほど重要な側面ではなく、ズーム設定は時折修正されるだけである。ドキュメント全体にわたる連続したパンが標準（すなわち、スクロールバーまたはカーソルを使用して、表示されたドキュメントを左、右、上、または下に変換する）であるが、ほぼ例外なく、連続してズームする機能はない。より一般化されたズーミングフレームワークでは、任意の種類のビジュアルコンテンツをズームすることが可能であり、ズームはパンと同様に重要なユーザ体験の一部となる。こうした線に沿ったアイデアが、超近代的なコンピュータユーザインターフェースとして、早くも１９６０年代には多くの映画に登場し（例えば、スタンリーキューブリック監督の「２００１年宇宙の旅」、ターナーエンターテイメント社、タイムワーナー社（１９６８年））、その流れは最近の映画にまで続いている（例えば、スティーブンスピルバーグ監督の「マイノリティリポート」、２０世紀フォックスおよびドリームワークスピクチャーズ（２００２年））。１９７０年代から現在に至るまで、いくつかの連続的なズーミングインターフェースが考案および／または開発されてきた（初期に登場したのは、W.C. Donelson, Spatial Management of Information, Proceedings of Computer Graphics SIGGRAPH (1978), ACM Press, p.203-9。最近の例では、２００２年夏に開始されたＺａｎｖａｓ．ｃｏｍ）。１９９１年、これらのアイデアのうちのいくつかが、正式に承認された（例えば、Kenneth Perlin and Jacob Schwartz At New York University (“Fractal Computer User Centerface with Zooming Capability”)の米国特許第５３４１４６６号明細書参照）。Ｐｅｒｌｉｎおよびその協働者等によって開発されたズーミングユーザインターフェースの���型であるＰａｄと、その後継のＰａｄ＋＋は、それ以降、ある程度の開発が見られている（Ｐｅｒｌｉｎはその後の開発について、http://mrl.nyu.edu/projects/zuni/で説明している。）。
【０１５１】
（発明の開示）
（発明が解決しようとする課題）
しかしながら当方の知る限り、全ＺＵＩ（ズーミングユーザインターフェース）に基づく主要なアプリケーションは、いくつかの技術不足が一因となりいまだ大量には出回っておらず、本発明はその技術不足の１つに対処する。
【０１５２】
（課題を解決するための手段）
本発明は、新しく開発されたズーミングユーザインターフェースフレームワーク（以下、その実用名からＶｏｓｓと呼ぶ）の基となる新規なアイデアを具体化する。Ｖｏｓｓは、そのソフトウェアアーキテクチャにおけるいくつかの改革点により、その先行品よりもより強力で、より応答性が良く、より視覚的に説得力があり、より多用途である。本特許は、特にオブジェクトタイリング（ｔｉｌｉｎｇ）、詳細レベル（ｌｅｖｅｌ−ｏｆ−ｄｅｔａｉｌ）ブレンディング、およびレンダリングキューイングのための、Ｖｏｓｓの手法に関する。
【０１５３】
多重解像度ビジュアルオブジェクトは、通常、異なる解像度または詳細レベル（イメージピラミッド）でサンプリングされたイメージの離散セットからレンダリングされる。３Ｄゲーミングなどの連続ズーミングが使用されるいくつかの技術コンテキストでは、各フレームをレンダリングするために、所望の詳細レベルを取り囲む２つの隣接する詳細レベルがブレンドされるが、これは通常は、所望の詳細レベルが正確には離散セットによって表されるうちの１つであるというケースではないためである。こうした技法は、時にはトリリニア（ｔｒｉｌｉｎｅａｒ）フィルタリングまたはミップマッピング（ｍｉｐｍａｐｐｉｎｇ）と呼ばれる。ほとんどの場合、ミップマッピングされたイメージピラミッドは事前に作成され、ズーミング操作中は連続して短期メモリ（すなわちＲＡＭ）内で維持されるため、任意の必要な詳細レベルが常時使用可能である。いくつかの拡張３Ｄレンダリングシナリオでは、イメージピラミッドはそれ自体がアニメーションループ内でレンダリングされなければならないが、これらのケースでは、全体のフレームレートに影響が出ないように、この最初のレンダリングパスの複雑さを十分に制御しなければならない。
【０１５４】
本コンテキストでは、無制限量のコンテンツの任意の視覚的複雑さを介したズームおよびパンによって連続的にナビゲートできることが望ましい。このコンテンツは迅速なレンダリングが不可能であり、さらに即時使用は不可能であるが、低帯域幅接続を介したリモートな場所からのダウンロードを必要とする可能性がある。したがって、常に所望の表示フレームレート（第２パス）に匹敵するフレームレート（第１パス）で、詳細レベルをレンダリングできるとは限らない。さらに、すべてのコンテンツに関して事前に作成されたイメージピラミッドをメモリ内に維持することも不可能であり、イメージピラミッドは必要に応じてレンダリングまたは再レンダリングしなければならず、このレンダリングは所望のフレームレートに比べて遅い可能性がある。
【０１５５】
本発明には、現在のディスプレイに関連するイメージピラミッド部分のレンダリング（潜在的に遅い）に優先順位を付けるためのストラテジと、部分的な情報、すなわちイメージピラミッドの現在使用可能なサブセットのみに基づいてレンダリングされるコンテンツの滑らかで連続的な知覚をユーザに提示するためのストラテジの、両方が含まれる。これらのストラテジを組み合わせて、不完全なイメージピラミッドによって生じる任意のイメージ劣化を可能な範囲までマスクしながら、使用可能なコンピューティング能力または帯域幅を最適に近い形で利用する。イメージの鮮明さの不連続または突然の変化を避けるために、空間的および時間的なブレンディングが活用される。
【０１５６】
本発明の目的は、サンプリング（すなわちピクセル化（ｐｉｘｅｌｌａｔｅ））されたビジュアルコンテンツを、従来のトリリニア補間に対する最終的なイメージ品質の劣化なしに、ズーミングユーザインターフェース内でレンダリングできるようにすることである。
【０１５７】
本発明の他の目的は、任意に大規模または複雑なビジュアルコンテンツをズーミングユーザインターフェース内に表示できるようにすることである。
【０１５８】
本発明の他の目的は、任意に複雑なビジュアルコンテンツを、たとえこのコンテンツが最終的に大量のデータを使用して表現される場合であっても、およびこれらのデータがリモートな場所に格納され、低帯域幅ネットワークを介して共有されている場合であっても、ほぼ即時に表示できるようにすることである。
【０１５９】
本発明の他の目的は、ユーザが対話フレームレートを維持しながら、ビジュアルコンテンツ上で任意に大幅なズームインができるようにすることである。
【０１６０】
本発明の他の目的は、コンテンツ全体の外観を保持するプロセス、および対話フレームレートを維持するプロセスの両方で、ユーザが複雑なビジュアルコンテンツの概観を得るために任意に大幅なズームアウトができるようにすることである。
【０１６１】
本発明の他の目的は、対話中にユーザが知覚する詳細レベル間またはレンダリング品質間の遷移を最小限にすることである。
【０１６２】
本発明の他の目的は、レンダリングに必要な情報が使用不可であるため、または依然としてレンダリングが進行中であるために、それまでのところ詳細なビジュアルコンテンツが使用不可である場合、連続的なぼかし（ｂｌｕｒｒｉｎｇ）によって、イメージ品質のみにくくない（ｇｒａｃｅｆｕｌ）劣化を可能にすることである。
【０１６３】
本発明の他の目的は、ビジュアルコンテンツのある部分のレンダリングが最初に使用可能になった場合、徐々に鮮明化することによってイメージ品質を安全に向上させることである。
【０１６４】
本発明のこれらおよび他の目的は、当業者であれば、本明細書で後述する再検討から明らかとなるであろう。
【０１６５】
従来技術：多重解像度イメージおよびズーミングユーザインターフェース
技術的な見地から、ズーミングユーザインターフェースは、ビジュアルコンピューティングを基礎とする通常の概念の一般化であり、従来のユーザ／コンピュータ／ドキュメントの対話モデルに固有のいくつかの制限を克服できるようにするものである。こうした制限の１つが、コンピュータアプリケーションから「オープン」可能なドキュメントのサイズにあり、従来は表示または編集を始める前にこうしたドキュメント全体を「ロード」しなければならなかった。たとえ特定のコンピュータが使用可能な短期メモリ（通常はＲＡＭ）の量が大きい場合であっても、オープニング時に何らかのリポジトリから（例えばハードディスクから、またはネットワークを介して）すべてのドキュメント情報を短期メモリに転送しなければならないため、制限付き帯域幅により、「オープン」コマンドの発行から表示または編集が開始できるまでの遅延が我慢できないほど長くなってしまい、この制限が意識される。
【０１６６】
静止デジタルイメージは、この問題の最たる例と、コンピュータサイエンスコミュニティがこの問題を克服するにあたり、ビジュアルコンピューティングに関する標準モデルをいかに超えたかの例の、両方を提供する。以下の表１は、最小の有用なイメージ（時にはアイコンとして使用されるサムネイル）から、現在一般に使用される最大のイメージまで、様々な異なるイメージタイプの典型的な圧縮サイズについての異なる帯域幅でのダウンロード時間を示す。影付きの枠は、特定接続速度での対話型ブラウジングが困難または不可能なイメージサイズを示す。
【０１６７】
【表１】
2008501160.tif 000010
【０１６８】
ほとんどのユーザがＤＳＬまたはそれよりも低帯域幅でウェブに接続しており、より大きなイメージはダウンロードに長時間かかることになるため、現在ウェブ上にあるほぼあらゆるイメージは１００Ｋ（０．１ＭＢ）未満である。ローカル設定であっても、典型的なユーザのハードドライブ上では、５００Ｋ（０．５ＭＢ）より大きいイメージに遭遇することは稀である。平均的な家庭にあるイラスト付の本、道路地図帳、地図、新聞、および美術作品が、最大解像度でデジタル化された場合すぐにサイズが何１０メガバイトにもなってしまうような、非常に多くのイメージを含んでいるという事実によって、その大きな（すなわちより詳細な）イメージがしばしば有用であることが実証される。
【０１６９】
数年前まで、大規模イメージの不足はリポジトリ内の格納スペースの不足によるものであったが、ハードドライブ技術の向上、ＣＤＲＯＭ焼付けの簡便化、および大規模ネットワークサーバの普及増加により、リポジトリスペースはもはや制限要因ではなくなった。現在の主なボトルネックは帯域幅と、それに続く短期メモリ（すなわちＲＡＭ）スペースである。この問題は現実には前述の表によって提案された内容よりもかなり悪化しており、ほとんどのコンテキストで、ユーザは単一のイメージだけでなくイメージの集合全体を表示することに関心を寄せているため、イメージが中サイズよりも大きい場合、イメージを次々とダウンロードする間待機することは非現実的になっている。
【０１７０】
ＪＰＥＧ２０００（http://www.jpeg.org/JPEG2000.html）などの現在のイメージ圧縮標準は、この問題に正確に対処するよう設計される。イメージコンテンツを線形様式（すなわち、通常は上から下および左から右へと、ピクセル全体を単一のパスで）で格納するのではなく、多重解像度分解に基づいている。イメージは第１に解像度スケールの階層にサイズ変更され、通常は２分の１、例えば５１２×５１２ピクセルイメージは、２５６×２５６ピクセル、１２８×１２８、６４×６４、３２×３２、１６×１６、８×８、４×４、２×２、および１×１へとサイズ変更される。明らかなことに、詳細部分は高解像度のみでキャプチャされ、かなり少ない量の情報を使用する大まかな部分（ｂｒｏａｄ  ｓｔｒｏｋｅｓ）は低解像度でキャプチャされる。これが、異なるサイズのイメージが詳細レベル、または省略してＬＯＤと呼ばれる理由である。一見して、この一連のサイズが異なるイメージに関する格納要件が、高解像度イメージだけの要件よりも多いように見えるかもしれないが、実際にはそうではなく、低解像度イメージは次のより高解像度のイメージの「予測子」として働く。これにより、実際には、高解像度イメージのみの非階層型表現で通常可能なよりも、全体のイメージ階層をかなり効率良く符号化することができる。
【０１７１】
イメージの一連の多重解像度バージョンがサイズの小さいものから順にリポジトリに格納されると想像した場合、通常は、イメージがデータリンクを横切ってキャッシュへと転送される場合、ユーザはイメージ全体の低解像度の概観を取得できることになり、その後、さらに詳細な部分は伝送の進行と共に「充填」されていくことになる。これはインクリメンタル（ｉｎｃｒｅｍｅｎｔａｌ）またはプログレッシブ（ｐｒｏｇｒｅｓｓｉｖｅ）伝送と呼ばれる。適切に実施された場合、仮にどのようなイメージでも、どれほど大きくても、たとえリポジトリへの接続の帯域幅が中程度であっても、ほぼ瞬時に、その空間全体に（全詳細ではないが）表示可能であるという特性を有する。全詳細イメージをダウンロードするために必要な最終的な時間は同じであるが、この情報が送信される順序は、イメージの大規模フィーチャが第１に伝送されるように変更されており、これは、全詳細ならびに上から下および左から右の「読み取り順」でピクセル情報を伝送するよりも、ユーザにとってかなり役立つものである。
【０１７２】
この改良に隠されているのは、前述の従来型アプリケーションモデルには収まりきらないイメージを「オープン」するということが何を意味するかという新しい概念である。ここで、ユーザがイメージをダウンロードしながら表示可能な、その有用性が、イメージの大まかな部分はダウンロード開始直後、おそらくはダウンロードが完了するかなり前に使用可能であるという事実から生じる概念を想像してみる。したがって、アプリケーションにとって、ダウンロードが完了する間ユーザを待たせることは無意味であり、その代わりにアプリケーションはドキュメントのうちの可能な部分を即時表示するはずであり、詳細のダウンロードを「バックグラウンドで」続行する間、ユーザとの対話に遅延または不必要な中断は発生しない。これには、アプリケーションがマルチスレッド化と呼ばれる複数のタスクを一度に実行することが必要である。最新のウェブブラウザは、ウェブページのテキストレイアウトを表示し、その間にユーザとの対話を維持しながら、ウェブページ上でイメージを同時にダウンロードするために、やや異なる立場でマルチスレッド化を使用することに留意されたい。この場合、ウェブページの必要最低限のテキストレイアウトからなる基本の詳細レベルを機能強化する、追加の詳細レベルとして埋め込まれたイメージ自体について考えることができる。この類推が、後に重要性を証明することになる。
【０１７３】
明らかな階層状のイメージ表現およびイメージドキュメントの累進的伝送は、線形表現および伝送を超える進歩である。しかしながら、イメージがその最高の詳細レベルで、ユーザのディスプレイが一度に表示可能な量よりも多くの情報（すなわちより多くのピクセル）を有する場合、さらなる進歩が重要になる。現在のディスプレイ技術では、これは常に表１の下から４種類のイメージに当てはまるが、より小型のディスプレイ（ＰＤＡスクリーンなど）は、下から８つでさえも表示できない可能性がある。これは、大きなイメージにとってズーミング機能を必須にし、追加の詳細を見つけるためにズームインすることが不可能な場合、ディスプレイよりも大きなイメージの表示は無用である。
【０１７４】
大きなイメージのダウンロードが開始された場合、おそらくユーザはそれを全体として見ているであろう。第１の詳細レベルはしばしば粗すぎて、使用可能な少量の情報を大きな表示領域全体に広げるために使用される補間の種類に応じて、表示されるイメージは濃淡のむらがあるかまたはぼやけて見えることになる。その後このイメージは、累進的に詳細化されることになるが、ある地点でディスプレイを情報で「飽和」させ、任意の追加の詳細をダウンロードしても視覚的な効果がなくなる。したがって、仮にその地点を越えてダウンロードを続けても意味がない。しかしながら、ユーザが特定の領域をより詳しく見るためにズームインすることを決めたと想定すると、イメージの効果的な投影サイズは、物理的なスクリーンよりも大幅に大きくなる。そこで、前述のダウンロードモデルでは、より高い詳細レベルを昇順（ｉｎｃｒｅａｓｉｎｇ  ｏｒｄｅｒ）にダウンロードすることが必要となる。困難な点は、あらゆる詳細レベルに、前の詳細レベルのおよそ４倍の情報が含まれることであり、ユーザがズームインしていくと、ダウンロードプロセスは必然的について行けない。さらに悪いことに、ダウンロードされているほとんどの情報が、表示領域以外の高解像度詳細からなるため無駄になる。ある詳細レベルの中で選択された部分のみをダウンロードする機能が必要であることは明らかであり、すなわち、目に見える詳細のみをダウンロードするべきである。この変更に伴い、任意の大型サイズのイメージを表示できるだけでなく、こうしたイメージを任意の詳細レベルで効率良くナビゲート（すなわちズームおよびパンなど）できる、イメージブラウジングシステムが作成可能である。
【０１７５】
ドキュメントアクセスの以前のモデルは本来逐次的であり、すなわち情報オブジェクト全体が線形順序で伝送される。これに対してこのモデルはランダムアクセスであり、すなわち、情報オブジェクトの選択された部分のみが要求され、これらの要求は任意の順序で、延長期間にわたって、すなわち表示セッション中に実行することができる。ここでコンピュータおよびリポジトリは、ドキュメントと共にディスプレイ上に表示されるユーザの「ダイアログ」と並行する、拡張ダイアログに従事する。
【０１７６】
ランダムアクセスを効率的にするために、グリッド正方形またはタイルが伝送の基本単位となるように、各詳細レベルをグリッドに細分化することが（絶対に必要ではないが）便利である。各タイルのピクセル単位のサイズは、増加していく各詳細レベルに前の詳細レベルの約４倍のタイルが含まれるように、一定のサイズまたはそれより下に維持することができる。その寸法が公称タイル細部の正確な倍数でない可能性がある場合、イメージの縁部には小さなタイルが生じ、さらに最低の詳細レベルでは、イメージ全体が単一の公称タイルよりも小さくなる。結果として生じるタイリングされたイメージピラミッドが図２に示される。ダウンスケールされたイメージが単一のタイルよりも小さくなる、ピラミッドの「頂点」は、図１のタイリングされていないイメージピラミッドのように見えることに留意されたい。ＪＰＥＧ２０００イメージフォーマットには、タイリングされた多重解像度およびランダムアクセスイメージを表す際に説明したのと同じすべてのフィーチャが含まれる。
【０１７７】
ここまで、静的イメージの場合についてのみ説明してきたが、アプリケーション特有の修正を施せば、この同じ技法をほとんどどのようなタイプのビジュアルドキュメントにも適用することができる。これには、大規模テキスト、地図、または他のベクトルグラフィックス、スプレッドシート、ビデオ、およびウェブページなどの混合ドキュメントが含まれる（これらに限定されることはない）。これまでの説明では、表示専用アプリケーション、すなわち、オープンおよび描画に対応するアクションまたは方法のみの定義が必要なアプリケーションについて暗黙に考えてきた。静的イメージ用のペイントプログラムによって実施される編集コマンド、テキスト用のワードプロセッサによって実施される編集コマンドなどの、他の方法が望ましい場合があることは明らかである。さらに、タイプされた入力を挿入するなどの通常のアクションが、基礎となるドキュメントに関する空間的スケールのある一定の範囲にわたってのみ関連するという、テキスト編集の問題を考えてみる。テキストがもはや読めないほどにズームアウトした場合、対話型編集はもはや不可能である。単一の文字が画面全体を覆うほどズームインした場合、対話型編集はもはや不可能であることもわかる。したがってズーミングユーザインターフェースは、ある方法のアクションをそれらに関連する詳細レベルに限定することもできる。
【０１７８】
ビジュアルドキュメントが、内部的にはイメージとしてではなく、テキスト、スプレッドシートエントリ、またはベクトルグラフィックスなどのより抽象的なデータとして表される場合、前述のセクションで紹介されたタイリングの概念を一般化することが必要である。静止イメージの場合、（いったん伸張された）情報が正確なタイルのピクセル×ピクセルのコンテンツであるため、いったん取得したタイルをレンダリングするプロセスは自明である。さらに速度のボトルネックは通常、圧縮データをコンピュータに転送（例えばダウンロード）することである。しかしながら場合によっては、速度のボトルネックはタイルのレンダリングにあり、レンダリングを実行するために使用される情報は、すでにローカルに格納されているか、または非常にコンパクトであるためにダウンロードによる遅延が生じない可能性がある。したがって次に、これが低速プロセスの可能性があることを理解した上で、タイルレンダリングとしてのタイル描画要求に応答した、完成された完全に描画されたタイルの作成について言及する。これが低速であるかどうかが、要求されたデータが大量であり、低速接続を介してダウンロードしなければならないためであるか、あるいは、レンダリングプロセス自体が計算上集約的であるためであるかは、無関係である。
【０１７９】
完全なズーミングユーザインターフェースは、ユーザが、そのサブドキュメント（ｓｕｂ−ｄｏｃｕｍｅｎｔ）が通常は空間的に重複しない、大型で場合によっては動的な複合ドキュメントを表示できるような方法で、これらのアイデアを組み合わせる。これらのサブドキュメントは、さらにそのサブドキュメント（通常は重複しない）を含むことが可能であり、さらにその先も同様である。したがってドキュメントは、各ドキュメントがサブドキュメントの集まり、すなわち子を指すポインタを有し、子のそれぞれが親ドキュメントの空間的境界内に含まれる構造である、ツリーを形成する。こうしたそれぞれのドキュメントを、ツリーに関するプログラミング用語から借用して、ノードと呼ぶ。描画方法はすべての詳細レベルのすべてのノードについて定義されるが、アプリケーション特有の機能に対応する他の方法は、ある特定のノードについてのみ定義可能であり、それらのアクションはある特定の詳細レベルにのみ限定することができる。したがって、いくつかのノードは、ペインティングなどのコマンドを使用して編集可能な静的イメージとすることが可能であり、他のノードは編集可能なテキスト、他のノードは表示およびクリック用に設計されたウェブページとすることができる。これらはすべて、ズームおよびパンによってナビゲート可能な共通の大規模空間環境である、「スーパーノード」内に共存することができる。
【０１８０】
ズーミングユーザインターフェースが適切に実施されると、次のようないくつかの直接の結果が生じる。
【０１８１】
−  非常に大きなドキュメントは、それらを全体としてリポジトリからダウンロードせずにブラウズすることができるため、使用可能な短期メモリよりも大きい、またはそうでなければサイズが法外なドキュメントであっても、制限なく表示することができる。
【０１８２】
−  コンテンツは必要に応じてナビゲーション中にダウンロードされるだけであり、結果として使用可能な帯域幅が最適に効率良く使用される。
【０１８３】
−  ズームおよびパンは、空間的に直感的な操作であり、大量の情報を容易に理解できる方法で編成することができる。
【０１８４】
−  「スクリーンスペース」は本来無制限であるため、ウィンドウを最小化する、複数のデスクトップを使用する、あるいは、同時に複数のドキュメントまたはビューで作業するためにウィンドウを互いに後ろに隠す必要はない。代わりに、ドキュメントを所望に応じて配置構成し、ユーザはそれらすべての概観を見るためにズームアウトするか、特定の１つを見るためにズームインすることができる。これにより、それらの任意の組合せが同時にスクリーン上の有用なスケールで見えるようにするために、こうしたドキュメントの位置（またはスケールさえも）を再配置構成する可能性が排除されることはない。また、さらに旧式の手法を使用するズーミングの組合せを必ずしも除外することもない。
【０１８５】
−  ズーミングはナビゲーション本来の側面であるため、任意の種類のコンテンツを適切な空間スケールで表示することができる。
【０１８６】
−  高解像度表示は、もはやテキストおよびイメージを小さいサイズ（時には読めないほど）に縮小することを示唆してはおらず、ズームのレベルに依存して、より多くのコンテンツを一度に表示できるようにするか、またはコンテンツを通常サイズおよびより高い忠実度で表示できるようにする。
【０１８７】
−  視覚障害者が、さらにズームインするだけで、通常の視力の人と同じコンテンツを容易にナビゲートすることができる。
【０１８８】
これらの利点は、ウェブに接続された通常のコンピュータが使用可能な情報が急増している現在、特に価値がある。１０年前には、ＺＵＩで表示できるようにするこの種の非常に大規模なドキュメントは稀であり、さらに、こうしたドキュメントはかなりのスペースを要するため、ほとんどのコンピュータが使用可能なリポジトリ（例えば４０ＭＢハードディスク）上に収まることはほとんどなかった。しかしながら現在では、非常に異なる状況に直面しており、サーバは大量のドキュメントおよびドキュメント階層を容易に格納すること、およびこの情報をウェブに接続された任意のクライアントが使用できるようにすることが可能である。それでもなお、これらの潜在的に大容量のリポジトリと通常のユーザとの間の接続の帯域幅は、ローカルのハードディスクへの接続の帯域幅よりもはるかに低い。これがまさに、ＺＵＩが従来のグラフィカルユーザインターフェースに勝るその最大の利点を与えるシナリオである。
【０１８９】
（発明を実施するための最良の形態）
ある特定の所望な解像度での特定ノードのビューについて、ある特定のＬＯＤに、スクリーンピクセルあたり少なくとも１つのサンプルを含むようにレンダリングするための描画が必要ないくつかのタイルセットがある。ビューは通常はノードのＬＯＤうちの１つの解像度で精密には表示されず、それらのうちの２つの間の中間解像度で表示されることに留意されたい。したがって理想的に言えば、ズーミング環境でクライアントは、実際の解像度のすぐ上およびすぐ下の両方で可視タイルのセットを生成し、何らかの補間を使用してこの情報に基づいてディスプレイ上にピクセルをレンダリングする。最も一般的なシナリオは、空間的と詳細レベル間との両方での線形補間であり、グラフィックス文献では、これは通常トリリニア補間と呼ばれる。緊密に関連する技法は、一般に、テクスチャリングのための３Ｄグラフィックスアーキテクチャで使用される（S. L. Tanimoto and T. Pavlidis, A hierarchical data structure for picture processing, Computer Graphics and Image Processing, Vol.4, p.104-119 (1975); Lance Willliams, Pyramidal Parametrics, ACM SIGGRAPH Conference Proceedings (1982)）。
【０１９０】
残念なことに、タイルのダウンロード（またはプログラムでのレンダリング）はしばしば低速であり、特に高速ナビゲーション中は必要なすべてのタイルがいつでも使用できるわけではない。したがって本特許での革新点は、タイルのダウンロードまたは作成が低速および非同期で発生する環境で、この理想的なイメージを近似する、空間的および時間的に連続したコヒーレントなイメージをビューワに提示するためのストラテジの組合せに焦点をあてる。
【０１９１】
以下では、２つの変数名、ｆおよびｇを使用する。ｆは、＃１に定義されたディスプレイに関するタイルのサンプリング密度を指す。変数ｇとして記述するタイリング細分性は、あるＬＯＤでの線形タイリンググリッドサイズと、次に下位のＬＯＤでの線形タイリンググリッドサイズとの比として定義される。本明細書に提示された革新点のいずれも定数ｇに依拠しないが、これは一般に、所与のノードの異なる詳細レベルにわたって一定であると推定される。前のセクションで説明したＪＰＥＧ２０００の例ではｇ＝２であり、概念上、各タイルは次に高位のＬＯＤで２×２＝４タイルに「分割」される。細分性２は、同様のアプリケーションでは群を抜いて最も一般的であるが、本コンテキストでは、ｇは他の値を取ることもできる。
【０１９２】
１．詳細レベルタイル要求のキューイング。最初に、クライアントが光学機器を用いて類推により徐々に複合イメージの「焦点合わせ」ができるようにしていく、タイル要求をキューに入れるためのシステムおよび方法を紹介する。
【０１９３】
階層状にタイリングされたノードを含む情報リポジトリへの不規則な、場合によっては低帯域幅接続の問題に直面した場合、ズーミングユーザインターフェースは、ナビゲーション中にどのようにタイルを要求するかという問題に対処しなければならない。多くの状況で、こうしたすべての要求がタイムリーな形で満たされることになる、あるいは、情報が関連している期間中（すなわちユーザが他の場所でズームまたはパンする前）ずっと満たされることになる、と想定するのは非現実的である。したがって、タイル要求をインテリジェントに優先順位付けすることが望ましい。
【０１９４】
タイル要求キューイングに関する「最も外側」の規則は、ディスプレイに関する増加する詳細レベルである。このズームに依存した「関連詳細レベル」は、数値ｆ＝（タイルピクセル単位の線形タイルサイズ）／（スクリーンピクセル単位で測定されたスクリーン上に投影されたタイル長さ）によって得られる。ｆ＝１の場合、タイルピクセル対スクリーンピクセルは１：１であり、ｆ＝１０の場合、タイル内の情報はディスプレイが表示できる内容よりはるかに詳細であり（１０＊１０＝１００タイルピクセルが単一のスクリーンピクセル内に収まる）、ｆ＝０．１の場合、タイルはディスプレイに関して粗い（あらゆるタイルピクセルは、１０＊１０＝１００をカバーするように「伸長」または補間されなければならない）。この規則は、ディスプレイの領域がディスプレイの残余部分に関してサンプリング不十分（ｕｎｄｅｒｓａｍｐｌｅｄ）（すなわち粗雑に定義されるだけ）の場合、クライアントの第１の優先順位はこの「解像度ホール」の充填になることを保証する。ホール内に複数の詳細レベルがない場合、ｆ＜１のすべての詳細レベルに関する要求に、次に高位の詳細レベル（ＬＯＤのブレンディングを可能にするため。＃５を参照）に関する要求を加えて、昇順にキューに入れられる。厳密にはこれらの中で最も詳細な詳細レベルだけを現在のビューにレンダリングすればよく、より粗雑な詳細レベルは、低解像度イメージをディスプレイ上に定義するという点で冗長であるため、一見して、これが不必要なオーバヘッドを招くと推定される。しかしながら、これらのより粗雑なレベルはより大きな領域、すなわち一般にはディスプレイよりもかなり大きな領域をカバーしている。実際、任意のノードに対する最も粗雑な詳細レベルには、構造により単一のタイルのみが含まれるため、ノードの任意のビューをレンダリングするクライアントは、この「最も外側」のタイルを必ず最初にキューに入れることになる。
【０１９５】
これは、表示の堅固さにとって重要なポイントである。堅固さとは、たとえ満たされるのを待つタイル要求のバックログが大量にある場合でも、ユーザのパンおよびズームに応答して表示される内容に関してクライアントが決して「損をしない」ことを意味する。クライアントは単に、ディスプレイ上のあらゆる領域で使用可能な最高の（すなわち最高解像度の）イメージを表示するだけである。最悪の場合、これはノードに関連してこれまでに要求された最初のタイルである、最も外側のタイルとなる。したがって、第１のタイル要求のみに基づき、ノードのあらゆる空間部分は常にレンダリング可能となり、すべての後続のタイル要求は増分細分化とみなすことができる。
【０１９６】
低解像度タイルでフォールバックが生じるとイメージがぼやけた印象になるため、全体の影響は、サイズ変更のパンまたはズーム後にディスプレイがぼやけて見える可能性がある。その後タイル要求が満たされると、イメージは鮮明になる。
【０１９７】
単純な計算で、「冗長な」低解像度タイルを要求することによって生まれるオーバヘッドは実際にはわずかであることがわかり、特に、始めからあらゆる場所でノードイメージを適切に定義することの堅固さに対する代償は小さい。
【０１９８】
２．窩のある（ｆｏｖｅａｔｅｄ）タイル要求のキューイング。関連する詳細レベル内で、タイル要求は、図３に示されるようにスクリーンの中央までの距離を増加させることによってキューに入れられる。この技術は高解像度用に特化された中央領域、すなわち窩を有する人間の目からヒントを得たものである。通常、ズーミングはディスプレイの中央領域への関心に関連付けられているため、窩のあるタイル要求のキューイングは、通常ユーザがズームインする際の視覚情報に関する暗黙の優先順位付けを反映する。さらに、ユーザの目が一般に、ディスプレイの縁部よりも中央付近の領域を見ることにより多くの時間を費やすため、ディスプレイ縁部に残るぼやけは中央付近よりも目立ちにくい。
【０１９９】
窩のあるタイル要求を使用してズームインによって作成されるディスプレイ中心付近の一時的および相対的な鮮明度の増加は、図４に示されるようなズームアウトの当然の結果も反映する。この図は、２つの代替「ナビゲーションパス」を示し、１行目でユーザは、非常に高い解像度で表示される可能性があると想定する、およそディスプレイの３分の２を占める単一のドキュメント（またはノード）を見ながら、静止したままである。最初、ノードコンテンツは単一の低解像度タイルで表現され、その後、次のＬＯＤのタイルが使用可能となり、ノードコンテンツを４つ（＝２×２）のタイルを用いて２倍の解像度で見えるようにし、４×４＝１６および８×８＝６４タイルのバージョンが続く。２行目では、１行目に表示されたイメージが完全に詳細化されるまでユーザが影付きの正方形をズームインすると何が起こるかを見ていく。詳細レベルが高いタイルが再度キューに入れられるが、この場合は、部分的または完全に見えるタイルだけである。１行目に匹敵する（ディスプレイ上に見えるタイルの数に関して）地点まで詳細化が進む。３行目は、ユーザが再度ズームアウトした場合に何が使用できるか、および失われた詳細をどのように埋めるかを示す。すべての詳細レベルが表示されるが、実際には、非常に詳細なレベルは、ディスプレイが伝達できる以上に詳細な細部を表すため、おそらく３行目のディスプレイから省略されることに留意されたい。
【０２００】
ズームアウトは通常、ディスプレイの中央を周辺より詳細なタイルで満たしたままにすることに留意されたい。したがってこのタイル要求の順序は、すべてのナビゲーション中にディスプレイの中央領域の鮮明度を一貫して優先順位付けする。
【０２０１】
３．時間的なＬＯＤのブレンディング。それ以上詳細化せずに、現在のディスプレイに必要なタイルがダウンロードまたは構築され、最初に描画される場合、同じコンテンツを表すと思われる基礎となるより粗雑なタイルの一部をすぐに見えなくするため、ユーザはこの遷移をディスプレイの一部領域におけるぼやけの突然の変化として体験する。こうした突然の遷移は目障りであり、ユーザの注意をソフトウェアの実施の詳細に不必要にひきつける。本発明者等のＺＵＩ設計の一般的な手法は、ユーザにとってシームレスなビジュアル体験を作り出すことであり、これによって、「覆われた」ままであるべきタイルまたはソフトウェアの他の側面の存在に注意をひきつけられることはない。したがってタイルは、最初に使用可能になった場合すぐには表示されないが、いくつかのフレーム、通常はおよそ１秒の間ブレンドされる。このブレンディング関数は線形（すなわち、新しいタイルの不透明度が、固定のブレンド間隔の半分で新しいタイルが５０％不透明であるような、タイルが使用可能になってからの時間の１次関数である）、指数関数、または任意の他の補間関数に従うものとすることができる。指数関数的ブレンドでは、あらゆる短い一定の時間間隔が、不透明度の一定割合の変化に対応する。例えば、新しいタイルはフレームごとに２０％ずつより不透明になり、結果として、２０％、３６％、４９％、５９％、６７％、７４％、７９％、８３％、８７％、８９％、９１％、９３％などのような連続するフレームにわたる一連の不透明度が生じる。数学的には、指数は決して１００％に達しないが、実際には短期間で不透明度は１００％と区別がつかなくなる。指数関数的ブレンドには、不透明度の最も大きな上昇はブレンド開始付近で生じるため、依然として許容可能な時間的連続性を保持しながら、ユーザには新しい情報が即時に見えなくなる、という利点がある。本発明の参照実施形態では、必要な情報が使用可能になるにつれてディスプレイの領域の焦点が滑らかに合っていくような錯覚が生じる。
【０２０２】
４．連続ＬＯＤ。タイルのダウンロードまたは作成がユーザのナビゲーションに対して遅れを取る状況では、ディスプレイの隣接する領域が異なる詳細レベルを有する可能性がある。前の革新（＃３）では、詳細レベルにおける時間的不連続性の問題に対処したが、詳細レベルにおける空間的不連続性の問題に対処するためには別の革新が必要である。これらの空間的不連続性が修正されない場合、ユーザの目には、ビジュアルコンテンツが継ぎ目の片側でより鮮明に描画されるような、イメージ内の継ぎ目として見える。この問題は、各タイルの不透明度がタイル領域全体で変えられるようにすること、特に、相対的に低い詳細レベルを有するディスプレイ上のある領域とタイル縁部が接する場合、このタイル縁部で不透明度がゼロになるようにすることによって、解決する。状況によっては、相対的に低い詳細レベルの領域にコーナーが接触している場合、タイルの各コーナーでの不透明度がゼロになることも重要である。
【０２０３】
図５は、各タイル破片（ｓｈａｒｄ）にわたって不透明度が連続して変化するように、各タイルをタイル破片と呼ばれる矩形および三角形に分解する方法についての、本発明者等の最も単純な参照実施形態を示す。正方形ａｃｅｇで境界を画されたタイルＸは、左、右、上、および下に、それぞれが縁部を共有する隣接するタイルＬ、Ｒ、Ｔ、およびＢを有する。さらに、単一のコーナーを共有する隣接部ＴＬ、ＴＲ、ＢＬ、およびＢＲも有する。タイルＸが存在すると想定する。その「内部正方形」ｉｉｉｉは完全に不透明である。（繰り返される小文字は同一の頂点不透明度値を示すことに留意されたい。）しかしながら、周辺の矩形フレームの不透明度は、隣接するタイルが存在する（および完全に不透明である）かどうかによって決定される。したがって、タイルＴＬがない場合、ポイントｇは完全に透明となり、Ｌがない場合、ポイントｈは完全に透明となる、という具合である。本発明者等は、タイルの境界領域（Ｘの外側ｉｉｉｉ）をブレンディングフラップと呼ぶ。
【０２０４】
図６は、破片全体の不透明度を補間するために使用される参照方法を示す。部分（ａ）は一定不透明度の矩形を示す。部分（ｂ）は、２つの相反する縁部の不透明度が異なる矩形であり、内部全体の不透明度は、各内部ポイントの２つの縁部からの最短距離に基づく単なる線形補間である。部分（ｃ）は、３つのコーナーａｂｃすべての不透明度が異なる場合、三角形全体の不透明度を補間するための双１次（ｂｉｌｉｎｅａｒ）方法を示す。概念上あらゆる内部ポイントｐは、図に示されるように、三角形を領域Ａ、Ｂ、およびＣを伴う３つの部分三角形（ｓｕｂ−ｔｒｉａｎｇｌｅ）に細分する。ｐの不透明度はコーナーの不透明度の単なる重み付け合計であり、重みは３つの部分三角形の分数領域である（すなわち、合計三角形領域Ａ＋Ｂ＋Ｃで割ったＡ、Ｂ、およびＣ）。これはこの公式が、ｐが頂点に移動した場合にその頂点の不透明度を等しく与えることならびに、ｐが三角形の縁部上にある場合、その不透明度は２つの接続された頂点間の線形補間であることから、から、容易に検証される。
【０２０５】
破片内の不透明度は、全体としてその頂点での不透明度によって決定され、隣接する破片は常に頂点を共有する（すなわちＴ接合はない）ことから、この方法は、タイリングされた表面全体にわたって不透明度が滑らかに変化していくことを保証する。このストラテジは、＃３の時間的ＬＯＤブレンディングと組み合わせて、ユーザに見える相対的な詳細レベルが、ディスプレイ領域にわたって、および時間的に連続関数となるようにする。それによって空間的継ぎ目と時間的不連続性の両方が回避され、連続的に焦点が合っていくシーンをもたらす光学機器を連想させるビジュアル体験がユーザに提示される。大規模なドキュメントをナビゲートする場合、シーンの焦点が合う速度は、リポジトリへの接続の帯域幅の関数、またはタイルレンダリングの速度の関数の、いずれか遅い方である。最終的に、革新点＃２の窩のある優先順位付けと組み合わせて、連続する詳細レベルは、ディスプレイの中央領域の焦点が最初に合わされるような方法でバイアスされる。
【０２０６】
５．一般化された線形−ミップマップ−線形ＬＯＤブレンディング。これまでは、ノード上の明らかなＬＯＤにおける空間的および時間的平滑さを保証するための、ストラテジおよび参照実施形態について論じてきた。しかしながら、連続するズーミング操作中に詳細レベルをブレンドする方法についてはまだ対処していない。使用される方法は、隣接する詳細レベルがスケールの中間領域全体にわたって線形にブレンドされる、トリリニア補間の一般化である。各詳細レベルで、各タイル破片は、空間的平滑さに関して同じ詳細レベルの隣接するタイル破片と空間的に平均化され、経時的な平滑さに関して時間的に平均化された、描画時の不透明度を有する。詳細レベルがディスプレイを不十分にサンプリングしている場合、すなわちｆ＜１（＃１を参照）の場合、目標不透明度は１００％である。しかしながら、ディスプレイを過度にサンプリングしている場合、目標不透明度は、過度のサンプリングがｇ倍の場合ゼロになるように、線形に（または任意の他の単調関数を使用して）減じられる。トリリニア補間と同様、これによって、知覚される詳細レベルが決して突然変化することのないように、ズーム操作を介した連続するブレンディングが発生する。しかしながら、常に２つの詳細レベルのブレンドを含む従来のトリリニア補間とは異なり、このスキームでブレンドされる詳細レベルの数は１つ、２つ、またはそれ以上が可能である。２つより多い数は一時的であり、まだ時間的に完全にブレンドされていない複数の詳細レベルで、タイルによって発生する。単一レベルも、一般に理想より低いＬＯＤが、まだダウンロードまたは構築されておらず、ブレンドされていない、より高位のＬＯＤの１００％不透明の「代役をつとめている」場合に発生するという点で、通常は一時的である。
【０２０７】
ノードのタイル破片セットをレンダリングするための最も単純な参照実施形態は、いわゆる「ペインタアルゴリズム」を使用することであり、すべてのタイル破片は後ろから前の順番で、すなわち、最も粗雑（最低ＬＯＤ）から最も詳細（ｇ倍未満でディスプレイを過度にサンプリングする最高ＬＯＤ）へと、レンダリングされる。最高ＬＯＤ以外のすべての目標不透明度は１００％であるが、時間的ブレンディングが不完全な場合、より低い不透明度で一時的にレンダリングされる可能性がある。最高ＬＯＤは、前述のように、ディスプレイをどれだけ過度にサンプリングするかに依存する、可変の不透明度を有する。この参照実施形態は、後からレンダリングされる破片によって完全に隠される破片をレンダリングする可能性があるという点で、最適でないことは明らかである。より最適な実施形態は、３Ｄグラフィックスで隠された表面の除去に使用されるデータ構造およびアルゴリズムに類似したデータ構造およびアルゴリズムを使用することによって可能である。
【０２０８】
６．運動の予測。高速ズームまたはパンの間、タイル要求を求め続けるのは特に困難である。これらの高速ナビゲーションパターン中であっても、ズームまたはパンの運動は線形補外（ｌｉｎｅａｒ  ｅｘｔｒａｐｏｌａｔｉｏｎ）（すなわち、突然の反転または方向変更を実行することが困難である）によってローカルで適切に予測される傾向がある。したがって、この時間的運動コヒーレンスを活用して、時間をわずかに進ませたタイル要求を生成し、ビジュアル品質を向上させる。これは、パンまたはズームの際に運動の方向を伸長、膨張、または収縮する仮想ビューポートを使用してタイル要求を行い、追加タイルの要求を先取りすることによって実施される。ナビゲーションが終わると、仮想ビューポートは、実際のビューポートへ戻る短い時間間隔にわたって緩和する。
【０２０９】
前述の革新点は、いずれも矩形のタイリングに制約されず、三角形または六角形のタイリング、あるいはこうした形状の混合からなる異種のタイリング、あるいは完全に任意のタイリングなどの、グリッド上に定義可能な任意のタイリングパターンに明白な形で一般化することに留意されたい。こうした代替タイリングに対処するために実行する必要のある唯一の明示的変更は、縁部および内部の不透明度がすべて別個に制御可能な、図５に類似したタイル形状の三角形分割を定義することである。
【０２１０】
2008501160.tif 000011
【０２１１】
2008501160.tif 000012
【０２１２】
2008501160.tif 000013
【０２１３】
2008501160.tif 000014
【０２１４】
2008501160.tif 000015
【０２１５】
2008501160.tif 000016
【０２１６】
（書類名）明細書
（発明の名称）多重解像度ビジュアルデータの効率的、動的、および連続的な表示のためのシステムおよび方法
【０２１７】
（技術分野）
本発明は、一般に多重解像度イメージに関する。より具体的に言えば、本発明は、リアルタイムで異なる解像度または詳細レベルのコンテンツのビジュアル表現をまとめて効率的にブレンドするためのシステムおよび方法に関する。本方法は、視覚化されるデータが変化している可能性があり、所与の時点でデータの一部分のみが使用できる可能性がある、非常に動的なコンテキストであっても、知覚連続性を保証する。本発明は、コンピュータ向けのズーミングユーザインターフェース（ＺＵＩ）を含む（がこれに限定されることのない）、いくつかの分野での応用例を有する。
【０２１８】
（背景技術）
複雑なビジュアルデータのディスプレイを含む多くの状況では、これらのデータは異なる詳細レベル（ＬＯＤ）での表現の集合として、階層状に格納または計算される。多くの多重解像度方法および表現は、（例えば）デジタルイメージ用のウェーブレット、および３Ｄモデル用の累進的メッシュを含む（が、これらに限定されることのない）異なる種類のデータ用に考案されてきた。多重解像度方法は、場合によっては非常に長い計算をより「粗雑に」またはより「詳細に」実行可能な状況で、数学的および物理的シミュレーションでも使用され、本発明はこうしたシミュレーション、および多重解像度ビジュアルデータが対話形式で生成可能な他の状況にも適用される。さらに、本発明は、例えばマシン制御可能なパンおよびズームを備えたカメラから異なる詳細レベルで「実行中に」ビジュアルデータが取得可能な状況で、適用される。本発明は、こうした多重解像度ビジュアルデータを１つまたは複数の２Ｄディスプレイ（ＣＲＴまたはＬＣＤスクリーンなど）上に動的に表示するための汎用手法である。
【０２１９】
本発明を説明するにあたり、主な例として、（例えばＪＰＥＧ２０００イメージフォーマットで使用されるような）大規模デジタルイメージのウェーブレット分解を使用する。この分解は、その開始点として、通常は正規の矩形グリッド上のサンプルの配列である、オリジナルピクセルデータを採用する。通常、各サンプルは、そのグリッド座標に対応するスペース内のある地点で測定されたカラーまたは輝度を表す。いくつかの応用例では、グリッドは例えば１辺が何万サンプル（ピクセル）など、非常に大きい可能性がある。特に、（イメージが格納される）サーバが、低帯域幅接続によって（イメージが表示される予定の）クライアントに接続された環境で、こうしたイメージをリモートでブラウジングする場合、このような大型サイズを対話型で表示するにはかなりの問題点が見られる。イメージデータがサーバからクライアントへ単純なラスタ順で送信される場合、すべてのデータはクライアントがイメージ全体の概観を生成する前に伝送されなければならない。これには長い時間がかかる場合がある。こうした概観の生成は、計算上コストがかかり、おそらく、例えば２０，０００×２０，０００ピクセルイメージを５００×５００ピクセルにダウンサンプリングすることが必要な場合もある。こうした操作は対話式で実行するには非常に低速であるだけでなく、クライアントが全イメージデータを格納できるだけの十分なメモリを有する必要もあり、この例では、８ビットのＲＧＢカラーイメージにつき１．２ギガバイト（ＧＢ）である（＝３＊２０，０００＾２）。
【０２２０】
ほとんどのユーザがＤＳＬまたはそれよりも低帯域幅でウェブに接続しており、より大きなイメージはダウンロードに長時間かかることになるため、現在ウェブ上にあるほぼあらゆるイメージは１００Ｋ（０．１ＭＢ）未満である。ローカル設定であっても、典型的なユーザのハードドライブ上では、５００Ｋ（０．５ＭＢ）より大きいイメージに遭遇することは稀である。平均的な家庭にあるイラスト付の本、道路地図帳、地図、新聞、および美術作品が、最大解像度でデジタル化された場合すぐにサイズが何１０メガバイトにもなってしまうような、非常に多くのイメージを含んでいるという事実によって、その大きな（すなわちより詳細な）イメージがしばしば有用であることが実証される。
【０２２１】
数年前まで、大規模イメージの不足は不揮発性格納スペース（リポジトリスペース）の不足によるものであったが、ハードドライブ技術の向上、ＣＤＲＯＭ焼付けの簡便化、および大規模ネットワークサーバの普及増加により、リポジトリスペースはもはや制限要因ではなくなった。現在の主なボトルネックは帯域幅と、それに続く短期メモリ（すなわちＲＡＭ）スペースである。
【０２２２】
ＪＰＥＧ２０００（http://www.jpeg.org/JPEG2000.html）などの現在のイメージ圧縮標準は、この問題に正確に対処するよう設計される。イメージコンテンツを線形様式（すなわち、通常は上から下および左から右へと、ピクセル全体を単一のパスで）で格納するのではなく、多重解像度分解に基づいている。イメージは第１に解像度スケールの階層にサイズ変更され、通常は２分の１、例えば５１２×５１２ピクセルイメージは、２５６×２５６ピクセル、１２８×１２８、６４×６４、３２×３２、１６×１６、８×８、４×４、２×２、および１×１へとサイズ変更される。当発明者等は、各解像度のサイズが次に高位のサイズとどれだけ差があるかの係数を細分性と呼び、ここでは２であるが、この細分性を変数ｇで表す。細分性はスケールによって変化する場合があり、例えばここではｇは「イメージピラミッド」全体にわたって一定であると想定するが、これに限定されることはない。明らかなことに、詳細部分は高解像度のみでキャプチャされ、かなり少ない量の情報を使用する大まかな部分は低解像度でキャプチャされる。これが、異なるサイズのイメージが詳細レベル、または省略してＬＯＤと呼ばれる理由である。一見して、この一連のサイズが異なるイメージに関する格納要件が、高解像度イメージだけの要件よりも多いように見えるかもしれないが、実際にはそうではなく、低解像度イメージは次のより高解像度のイメージの「予測子」として働く。これにより、実際には、高解像度イメージのみの非階層型表現で通常可能なよりも、全体のイメージ階層をかなり効率良く符号化することができる。
【０２２３】
イメージの一連の多重解像度バージョンがサイズの小さいものから順にサーバのリポジトリに格納されると想像した場合、通常は、イメージがサーバからクライアントへと転送される場合、ユーザはイメージ全体の低解像度の概観を取得できることになり、その後、さらに詳細な部分は伝送の進行と共に「充填」されていくことになる。これは増分または累進的伝送と呼ばれ、多重解像度表現の主要な利点の１つである。累進的伝送が適切に実施された場合、仮にどのようなイメージでも、どれほど大きくても、たとえサーバへの接続の帯域幅が中程度であっても、ほぼ瞬時に、クライアントによってその空間全体に（全詳細ではないが）表示可能であるという特性を有する。全詳細イメージをダウンロードするために必要な最終的な時間は同じであるが、この情報が送信される順序は、イメージの大規模フィーチャが第１に伝送されるように変更されており、これは、全詳細ならびに上から下および左から右の「読み取り順」でピクセル情報を伝送するよりも、クライアントにとってかなり役立つものである。
【０２２４】
動的および対話型のコンテキストでランダムアクセスを効率的に実行するために、グリッド正方形またはタイルが伝送の基本単位となるように、各詳細レベルをグリッドに細分化することが（絶対に必要ではないが）便利である。各タイルのピクセル単位のサイズは、増加していく各詳細レベルに前の詳細レベルの約４倍のタイルが含まれるように、一定のサイズまたはそれより下に維持することができる。その寸法が公称タイル細部の正確な倍数でない可能性がある場合、イメージの縁部には小さなタイルが生じ、さらに最低の詳細レベルでは、イメージ全体が単一の公称タイルよりも小さくなる。したがって、６４×６４ピクセルタイルであると想定した場合、前述の５１２×５１２ピクセルイメージは、最高の詳細レベルで８×８タイルを有し、２５６×２５６レベルで４×４、１２８×１２８レベルで２×２、および残りの詳細レベルでは単一のタイルを有する。ＪＰＥＧ２０００イメージフォーマットは、タイリングされた多重解像度およびランダムアクセスイメージを表示するための前述の特徴を含む。
【０２２５】
大規模なタイリングされたＪＰＥＧ２０００イメージの詳細が、サイズおよび解像度が制限された２Ｄディスプレイ上でクライアントによって対話式で表示されている場合、いくつかの特定の隣接タイルのセットが、ある特定の詳細レベルで正確なレンダリングを生成することが必要である。しかしながら、この動的なコンテキストでは、これらがすべて使用可能でない可能性がある。しかしながら、特にユーザがイメージの広範な概観から始める場合、より粗雑な詳細レベルのタイルはしばしば使用可能となる。より粗雑な詳細レベルのタイルはより広い領域に空間的に広がるため、当該の領域全体が使用可能なタイルの何らかの組合せによってカバーされる確率が高い。これは、使用可能なイメージ解像度がディスプレイ領域全体にわたって一定ではないことを示唆する。
【０２２６】
以前に出願された仮特許出願で、当発明者は、同じ詳細レベルで空白スペースと接するタイルの縁部を「フェードアウト」するための方法を提案したが、これによって、詳細な詳細レベルの「対象範囲」が不完全である場合には他の結果となるような、鮮明さにおける突然の視覚的不連続性が回避される。ブレンディングのために予約されているタイルの縁部領域を、ブレンディングフラップと呼ぶ。完成された複合イメージを表示するための単純な参照実施形態は「ペインタアルゴリズム」であり、最も粗雑な詳細レベルのすべての関連タイル（すなわち、ディスプレイ領域が重複するタイル）が最初に描画され、続いて、累進的により詳細な詳細レベルのすべての関連タイルが描画されていく。前述のように、ブレンディングは各詳細レベルで不完全な領域の縁部に適用された。その結果は、所望の通り、より粗雑な詳細レベルは、より詳細な詳細レベルによって隠されない場所でのみ「透き通る（ｓｈｏｗ−ｔｈｒｏｕｇｈ）」ことになる。
【０２２７】
この単純なアルゴリズムは役立つが、いくつかの欠点があり、第１に、最終的に部分的またはたとえ完全に隠されることになる場合であってもタイルが描画されるため、処理時間が無駄である。特に、単純な計算で、各表示ピクセルはしばしばｌｏｇ２（ｆ）回（再）描画されることがわかり、ｆは最低の詳細レベルに対するディスプレイの拡大係数である。第２に、この技法はフレームバッファ内での複合に依拠しており、これによって、描画操作の中間地点で、描画される領域には最終的な外観はなく、２重バッファリングまたは関連する方法を使用して、解像度のちらつき表示を避けるためにオフスクリーンの複合を実行する必要を生じさせる。第３に、追加の複合操作が適用されない限り、この技法は不透明レンダリングにのみ使用可能であって、例えば、最終レンダリングがあらゆる場所で５０％の不透明度を有し、他のコンテンツを「透き通らせる」ことができるように保証することは不可能である。これは、ペインタアルゴリズムが下位レイヤを完全に隠す１つの「ペイントレイヤ」（すなわち詳細レベル）の効果に厳密に依拠しているためであり、どこで詳細レベルが隠されるか、およびどこで隠されないかは、前もってわからない。
【０２２８】
（発明の開示）
（発明が解決しようとする課題）
本発明は、ペインタアルゴリズムのすべての利点を保持しながら、これらの問題を解決する。
【０２２９】
（課題を解決するための手段）
これらの利点の１つは、非矩形または不規則なタイリング、ならびに無理（ｉｒｒａｔｉｏｎａｌ）グリッドタイリングを含む、任意の種類のＬＯＤタイリングに対処する機能であり、本発明者はこれに対して別の仮特許出願を出願している。一般にタイリングは、ビジュアルコンテンツを含む領域の多角形への細分化またはテセレーション（ｔｅｓｓｅｌａｔｉｏｎ）からなる。多重解像度コンテキストで有用となるタイリングの場合、一般に低い詳細レベルでのタイルの領域は、高い詳細レベルでのタイルの領域よりも大きいことが望ましく、それらのサイズの違いの乗法係数は細分性ｇであり、当発明者等はこれが一定であると想定する（がこれに限定されることはない）。以下では、無理数であるが矩形のタイリンググリッドを使用して、改善されたアルゴリズムについて説明する。当業者であれば、他のタイリングスキームに対する一般化は明らかであろう。
【０２３０】
（発明を実施するための最良の形態）
改善されたアルゴリズムは、４つの段階からなる。第１段階では、複合グリッドが、描画されるすべての詳細レベル内でのすべてのタイルグリッドの可視部分の重ね合わせから、イメージの基準フレーム内で構築される。無理タイリングの革新点（別の仮特許出願で詳述）が使用される場合、結果として、図１に概略的に示された不規則な複合グリッドが生じる。さらにこのグリッドは、各詳細レベルでタイルの「ブレンディングフラップ」を描画するために必要となるｘおよびｙの値に対応するグリッド線によって増補される（結果として生じるグリッドは密度が高すぎで視覚的に混雑するため、図１には図示せず）。この複合グリッドは、グリッド線に対してｘおよびｙの値のソート済みリストによって定義可能であり、すべての可視タイル（それらのブレンディングフラップを含む）を描画することが必要となるすべての矩形および三角形の頂点が、ｘおよびｙのグリッド線の交差位置にあるという特性を有する。ｘ軸に平行なｎのグリッド線と、ｙ軸に平行なｍのグリッド線があるものとする。その後、グリッドの正方形に対応するエントリを備えた２次元のｎ＊ｍのテーブルを構築する。各グリッドエントリは、ゼロに初期設定される不透明度と、初期には空白の特定タイルの参照リストという、２つのフィールドを有する。
【０２３１】
第２段階は、（単純な実施とは反対の）減少していく詳細レベル順にソートされたタイルを通り抜けることである。各タイルは整数の複合グリッド正方形をカバーする。これら正方形それぞれについて、そのテーブルエントリが１００％未満の不透明度を有するかどうかをチェックし、有する場合は現在のタイルをそのリストに追加し、それに応じて不透明度を増加させる。このステップで使用されたタイルごとの不透明度は、タイルデータ構造に格納される。この第２段階が完了した場合、複合グリッドは、これらの「タイル破片」を描画する際の不透明度と共に、各グリッド正方形内に描画するための正しいタイル片に対応するエントリを含むことになる。通常、これらの不透明度は、合計すると１になる。全体として隠される低解像度タイルはこのテーブルのどこにも参照されないが、部分的に隠されるタイルは部分的に見えるタイル破片でのみ参照されることになる。
【０２３２】
アルゴリズムの第３段階は、複合グリッドのトラバースであり、ここで、同じ詳細レベルの隣接する頂点と平均化し、その後、合計された各頂点の不透明度（通常は１００％）を保持するように頂点不透明度を再調整することによって、複合グリッドの頂点の破片不透明度が調整される。これにより、別の仮特許出願で説明されたスケールの空間的平滑化の細分化されたバージョンが実施される。細分化は、複合グリッドが一般に、特に低解像度タイルの場合、革新点＃４で定義されたタイルあたり３×３グリッドよりも高密度であるという事実から生じる。（最高のＬＯＤでは、構造により、複合グリッド化は少なくとも必要な限り詳細となる。）これにより、実際にはより多くのタイル破片からなるより平滑なブレンディングフラップを作成することによって、平均化技法が顕著な詳細レベルでかなりの滑らかさを達成できるようになる。
【０２３３】
最後に第４段階では、複合グリッドが再度トラバースされ、タイル破片が実際に描画される。このアルゴリズムにはデータを介する複数のパスおよびある一定量のブックキーピング（ｂｏｏｋｋｅｅｐｉｎｇ）が含まれるが、その結果、最終的に実施しなければならない描画がはるかに少なくなるため、単純なアルゴリズムよりもかなり性能が良くなり、レンダリングされたあらゆるタイル破片が、時には低不透明度であるが、ユーザに見えるようになる。一部のタイルはまったく描画されない可能性がある。これは、全体として表示された領域と交差するあらゆるタイルを描画する単純なアルゴリズムとは対照的である。
【０２３４】
このアルゴリズムの追加の利点は、合計不透明度目標を１００％から何らかの低い値へと変更するだけで、部分的に透明なノードが描画できるようになるという点である。これは、任意の基礎となる依然として低解像度のタイルに完全に「重ねペイント」するために、最も詳細なレベルを除くあらゆる詳細レベルを最高の不透明度で描画しなければならないため、単純なアルゴリズムでは不可能である。
【０２３５】
ビューがノードに対してｘ−ｙ面で回転される場合、効率性のために何らかのわずかな変更が必要である。複合グリッドは通常の様式で構築可能であり、対角線に沿ってより大きな座標領域が見える場合、回転されない場合のグリッドよりも大きくなる可能性がある。しかしながら、タイルを通り抜ける場合、（単純な交差多角形基準により）見えるタイルのみを考慮の対象とする必要がある。また、表示領域外の複合グリッド正方形は、第２または第３段階でのトラバース時、あるいは第４段階での描画時に、更新する必要がない。性能を最適化するためにいくつかの他の実施の細部が修正可能であり、アルゴリズムはその操作および本来の特徴を最も理解しやすい形で本明細書に提示されていることに留意されたい。当業者のグラフィックスプログラマであれば、最適化実装の細部を容易に追加できる。例えば、タイル破片あたりのタイルリストを維持する必要はなく、その代わりに、各詳細レベルが完了した場合、正しい不透明度で即時に描画することが可能であり、常に破片あたりの単一タイル識別を格納することのみが必要である。別の例示的最適化は、（領域）×（残りの透明度）で表されるまだ実行されていない合計不透明度レンダリングが追跡可能なことであり、その結果、すべてがすでに描画されている場合、アルゴリズムは早期に終了可能であり、その後必要でなければ低い詳細レベルを「訪ねる」必要はまったくない。
【０２３６】
このアルゴリズムは、頂点不透明度およびタイル破片識別子を格納するためのグリッドの代わりに制約付きドローネ三角形分割を使用することによって、任意の多角形タイリングパターンに一般化することができる。このデータ構造は、その縁部がすべてのオリジナルＬＯＤグリッド内のあらゆる縁部を含む三角形分割を、効率的に作成し、特定の三角形または頂点へのアクセスは、順番にｎ＊ｌｏｇ（ｎ）回（ｎは追加された頂点または三角形の数である）実行可能な効率的な操作である。さらに結果として生じる三角形は、ほとんどのグラフィックスプラットフォームでグラフィックスレンダリングに使用される基本プリミティブである。
【０２３７】
2008501160.tif 000017
【０２３８】
（書類名）明細書
（発明の名称）商取引を向上させるためにイメージナビゲーション技法を使用するための方法および装置
【０２３９】
（技術分野）
本発明は、例えば、製品および／またはサービスの広告および購買のために新しい環境を提供するなどの、商取引の向上においてイメージナビゲーション技法を適用するための方法および装置を対象にする。
【０２４０】
（背景技術）
デジタルマッピングおよび地理情報アプリケーションは、急成長中の業界である。これらは、多くの異なる市場における企業から、すなわちＦｅｄｅｒａｌ  Ｅｘｐｒｅｓｓ、衣料品店、およびファストフードチェーンなどの候補から得られる投資が急激に増加している。過去数年間で、マッピングは、検索エンジン、ウェブメール、および出会い系と並んで、非常に高い関心が寄せられる（いわゆる「キラーアプリケーション」）ウェブ上の数少ないソフトウェアアプリケーションのうちの１つにもなってきている。
【０２４１】
マッピングは、原則として高度な視覚表現であるはずだが、現時点では、そのエンドユーザ向けユーティリティのほとんどすべてがドライブ案内にある。ドライブ案内に常に随伴する地図イメージは、通常あまり良いレンダリングではなく、伝えられる情報は少なく、便利にナビゲートできず、体裁を整える程度にすぎない。パンまたはズーム制御をクリックすると長い遅延が発生し、その間にウェブブラウザは無応答となり、その後、前のイメージとほとんど視覚的な関係のない新しい地図イメージが出現する。原則的には、我々が紙の道路地図をナビゲートするよりも、コンピュータがデジタル地図をナビゲートする方がより効果的なはずであるが、実際には、コンピュータによる地図のビジュアルナビゲーションの方が依然として劣勢である。
【０２４２】
（発明の開示）
（発明が解決しようとする課題）
本発明は、新規な技術と組み合わせて使用し、たとえ低帯域幅接続を介する場合であっても、連続的かつ高速な地図（または任意の他のイメージ）のビジュアルナビゲーションを可能にすることを意図している。
【０２４３】
（課題を解決するための手段）
この技術は、パンおよびズーム環境において地図を連続してレンダリングするための新しい技法に関する。これは、線および点のレンダリングへのフラクタル幾何学の適用であり、道路網（１Ｄ曲線）および位置を示す点（０Ｄポイント）をすべてのスケールで描画できるようにし、連続した物理ズーミングの錯覚を生じさせながら、依然として境界が画された地図の「視覚密度」を維持する。関連技法は、テキストラベルおよびアイコンコンテンツに適用される。この新しいレンダリング手法は、ズーム中に小さな道路が突然出現または消失するような効果、デジタルマップドローイングに特有の悪影響を避ける。このナビゲーション技法の詳細を知ることができる（例えば、その開示全体が参照により本明細書に組み込まれた、本願と同日付出願の「METHOD AND APPARATUS FOR NAVIGATING AN IMAGE」という名称の米国特許出願（代理人整理番号４８９／９）参照）。このナビゲーション技術は、本明細書では「Ｖｏｓｓ」と呼ばれる場合がある。
【０２４４】
Ｖｏｓｓ技術を使用すると、インターネットマッピング向けのいくつかの新規な商品価値のあるビジネスモデルが実行可能である。これらのモデルは、それらの出発点としてＹａｈｏｏ！ＭａｐｓおよびＭａｐＱｕｅｓｔなどの実績のある成功ビジネスを採用し、そのどちらも地理広告から収益を得ている。しかしながら、本発明者等の手法は広告にとどまらず、企業とエンドユーザの両方にとってかなりの価値を付加するために新しい技術の機能を利用している。本質的なアイデアは、企業および人々が地図上の「不動産」を通常はそれらの物理アドレスで借り、その中にズーム可能なコンテンツを埋め込むことができるようにすることである。このコンテンツは広域地図上に表示される場合はアイコンの形、すなわち、ＭｃＤｏｎａｌｄｓの場合は金色のアーチなどで表示することができるが、その後、細密に表示される場合は、滑らかおよび連続的に任意の種類のウェブ様コンテンツに分解されていく。本発明者等のマッピングアプリケーションに動的なユーザコンテンツおよび企業／住居のアドレスデータを統合させることにより、一種の「地理的なワールドワイドウェブ」が可能になる。
【０２４５】
消費者および小売業者の両方に対する大規模な水平市場に加えて、カーナビゲーションシステム、携帯電話およびＰＤＡ、不動産レンタルまたは販売、３行広告、およびその他多くなどの、既存の地理情報サービス（ＧＩＳ）プロバイダおよび関連業界との相乗作用が得られる。これらの領域における可能な業務関係には、技術ライセンス交付、戦略的提携、および直接垂直統合販売が含まれる。
【０２４６】
本発明の新しいナビゲーション技法の機能については、前述の米国特許出願に詳細に説明されている。本出願の場合、基本技術の最も関連のある態様は、以下の通りである。
【０２４７】
・  知覚的連続性および拡張帯域幅管理による２Ｄ世界を介した滑らかなズームおよびパン
・  ビジュアルコンテンツを無制限にネストすることが可能な無限精度座標系
・  空間的閉じ込め（ｓｐａｃｉａｌ  ｃｏｎｔａｉｎｍｅｎｔ）がハイパーリンクと等価の、多くの異なるサーバ上に格納されたコンテンツをネストする機能
【０２４８】
後者２つの要素に関して、追加の詳細を知ることができる（例えば、その開示全体が参照により本明細書に組み込まれた、２００３年５月３０日付出願の「SYSTEM AND METHOD FOR INFINITE PRECISION COORDINATES IN A ZOOMING USER INTERFACE」という名称の米国仮特許出願第６０／４７４３１３号明細書参照）。
【０２４９】
地図は情報の多くのレイヤからなり、最終的にＶｏｓｓ地図アプリケーションは、ユーザがこれらレイヤのほとんどをオンおよびオフにできるようにし、地図を高度にカスタマイズできるようにする。レイヤには以下が含まれる。
【０２５０】
１．道路
２．水路
３．行政区画
４．航空写真ベースの垂直イメージ（ｏｒｔｈｏｉｍａｇｅｒｙ）（地図を完全にタイル化するようにデジタル形式で「ゆがみ除去（ｕｎｗａｒｐ）」された航空写真）
５．地形図
６．公共インフラストラクチャ位置、例えば学校、教会、公衆電話、トイレなど
７．上記それぞれについてのラベル
８．雲量、降水量、および他の気象条件
９．交通条件
１０．広告
１１．個人および営利ユーザコンテンツなど
【０２５１】
典型的なユーザの視点から見て最も重要なレイヤは、１〜４および７である。本特許出願において特に関心のある広告／ユーザコンテンツレイヤ１０〜１１も、かなり関心が高い。１〜７を含む地図レイヤの多くは、高品質およびわずかな金額で、すでに米国連邦政府から入手可能である。８〜９（およびその他）のような付加価値レイヤは、開発中またはたとえ展開後であっても、いつでも使用可能にすることができる。
【０２５２】
いくつかの会社は、ドライブ案内の生成には重要であるが視覚的地理には重要でない、一方通行路、高速道路の出入口ランプ、および他の特徴を示す注釈付きの、拡張道路データを提供している。本出願に関して提供された最も関連のある商用地理情報サービス（ＧＩＳ）は、所在地住所を精密な緯度経度座標に変換できるようにするジオコーディング（ｇｅｏｃｏｄｉｎｇ）である。ジオコーディングサービスの取得は法外に高くないことが判定されている。
【０２５３】
地図データに加えて、全国職業別電話帳／個人別電話帳データも、本発明を実施する際には役立つ可能性がある。この情報はライセンス交付される可能性もある。全国職業別電話帳／個人別電話帳データをジオコーディングと組み合わせて使用することで、地理的なユーザの企業検索、またはフィルタリング（例えば、「マンハッタンのすべてのレストランをハイライト表示する」）を可能にする。おそらく最も重要なことに、ジオコーディングと組み合わせたディレクトリリストが、企業および個人ユーザと地理的場所との関連付けをはるかに簡略化し、オンライン取引を介して「不動産」をレンタルまたは委託できるようにするため、大規模な販売力を必要としない。
【０２５４】
テレマーケティング用に設計された全国の電話および住所データベースは、ＣＤで安価に取得できるが、これらは必ずしも高品質ではなく、その対象範囲は通常一部分にすぎず、古いことがしばしばある。いくつかの会社が、本発明のようにソフトウェア指向の企業向けに設計されたＡＰＩを備えた堅固なディレクトリサーバを提供している。最も適したのはＷ３Ｄａｔａ（www.w3data.com）であり、ＸＭＬベースＡＰＩを使用した「ニアタイム（ｎｅａｒｔｉｍｅ）」と呼ばれる全国電話リストを最低＄５００／月で提供し、＄０．１０／ヒットから始まり、量が２５０，０００／月の場合は＄０．０５／ヒット、または量が１，０００，０００／月を超える場合は＄０．０３／ヒットに下がっていく。米国全土およびカナダが対象範囲である。電話番号から名前を検索する逆照会も可能である。「ニアタイム」データは、少なくとも９０日ごとに更新される。本発明者等側ですでに取得しているエントリの９０日キャッシュと組み合わせると、高品質全国リストを取得するための非常に経済的な方法である。毎夜更新される「リアルタイム」データも使用可能であるが、より高価である（＄０．２０／ヒット）。リアルタイムデータは、４１１オペレータによって使用されるものと同一である。
【０２５５】
同等の業務および価格モデルを持つ、カテゴリ別の全国企業リストを生成できるＷ３Ｄａｔａと同様のサービスプロバイダも存在する。
【０２５６】
従来の広告ベースの業務モデル、ならびに知的所有権のあるデータ形式およびダウンロード可能なプラグイン（Ｆｌａｓｈ、Ａｄｏｂｅ  Ａｃｒｏｂａｔ、およびＲｅａｌ  Ｐｌａｙｅｒなど）を含む「メディアプレーヤ」モデルは、通常、どちらが後か先かわからない問題を抱えている。広告スポットは、人々がすでに見ている場合にのみ価値のある広告になり、プラグイン（たとえ無料の場合であっても）は、すでに表示用の有用なコンテンツがある場合にのみダウンロードする価値があり、コンテンツは、それを簡単に表示できるユーザ基盤がすでにインストール済みの場合にのみ、投資が得られるようになる。
【０２５７】
Ｖｏｓｓマッピングアプリケーションは、ダウンロード可能なクライアントソフトウェアを必要とし、これを広告することによって収益が得られるが、従来の広告ベースの業務モデルの欠点はない。たとえかなりの商用スペースを「レンタル」する前であっても、本発明は、地図を表示してアドレスを検索するための有用で視覚に訴える方法、すなわち、既存のマッピングアプリケーションと同様であるが、かなり改善されたビジュアルインターフェースを備えた機能を提供することになる。さらに本発明の手法は、ユーザ基盤を得ることが無料の非営利ユーザにとって制限付きであるが役に立つサービスを提供する。制限付きサービスは、ユーザの地理的位置、通常は家庭に、ユーザ１人あたり少量（５〜１５ＭＢ）のサーバスペースをホストすることからなる。クライアントソフトウェアは、ユーザがイメージおよびテキストを自分の「物理アドレス」にドラッグアンドドロップした後、クライアントソフトウェアを備えた任意の他の許可されたユーザによって表示できるようにする、簡単なオーサリング機能を含むことができる。（パスワード保護が使用可能である）。特に限られた帯域幅を介してデジタル写真のコレクションをナビゲートするためには、ズーミングユーザインターフェース手法は明らかに有益であるため、潜在性のみを共有する写真アルバムは、かなりの数のユーザをひきつけることができる。適度な年会費で、追加のサーバスペースも使用できる。これは、主要な収入源となる可能性のある非常に水平的な市場である。
【０２５８】
検索エンジンおよび他の有用な（および現在では有益な）ウェブサービスに対して適切な働きをする手法である、有用なサービスを最初から提供することによって、通常のどちらが後か先かわからない問題が発生するのは避けられる。これは、例えばユーザ基盤が構築されるまでは有用でないオンライン出会い系サービスとははっきりと対照的である。
【０２５９】
本発明の様々な態様によれば、収入源には以下のものが含まれる。
１．物理アドレスに対応する地図上のスペースの商用「レンタル」
２．営利ユーザに向けられた「プラスサービス」（以下に定義）料金
３．非営利ユーザに向けられた「プラスサービス」料金
４．専門的なズーム可能コンテンツオーサリングソフトウェア
５．ＰＤＡ、携帯電話、カーナビゲーションシステムなどのベンダおよびサービスプロバイダとのライセンス交付または提携
６．情報
【０２６０】
地図上のスペースの基本的な商用レンタルは、以下の変数の組合せを使用して価格付けすることができる。
１．地図上のサイト数
２．平方メートル単位での１サイトあたりの地図面積（「土地専有面積」）
３．総計表示統計に基づく不動産の望ましさ
４．ＭＢ単位でのコンテンツをホストするために必要なサーバスペース
【０２６１】
営利ユーザ向けのプラスサービスは、フランチャイズ、電子商取引または他のより洗練されたウェブの使用法の実行を望む企業、および自社広告の認知度を上げることを望む企業に向けられる。
【０２６２】
１．可視高さの上昇−−可視であるが控えめなアイコンまたは「フラグ」が、それ以外の方法で可視となるよりも遠くから（よりズームアウトして）業務サイトの場所を示すことができるような、いくつかのレベルが提供される。
【０２６３】
２．焦点合わせ優先順位−−Ｖｏｓｓはナビゲーション中にデータが使用可能になるとイメージ領域の焦点を合わせる。デフォルトでは、すべてのビジュアルコンテンツが等しく扱われ、焦点はスクリーンの中心から外側に向かって合わされていく。焦点合わせの優先順位により、商品コンテンツの方がそれ以外よりも早く焦点が合わされ、ユーザの「周辺視野」における顕著さが上昇する。この機能は、ユーザのナビゲーション体験を損なうことなく商品価値を送達するように調整される。
【０２６４】
３．従来のウェブハイパーリンクのズーム可能コンテンツへの包含−−これらは明瞭にマーク付けされ（例えば、従来のように下線が引かれた青いテキストで）、ユーザがクリックするとウェブブラウザがオープンする。本発明者等は、こうしたハイパーリンクを含めるために課金するか、またはＧｏｏｇｌｅのようにクリックごとに課金することができる。
【０２６５】
４．それ自体が任意のタイプおよびサイズのズーム可能なコンテンツをホストする外部商用サーバを参照した地理領域のレンタル化−−これは、＃３の愛好家版であり、任意の種類のｅビジネスを地図を介して実行させることができる。本発明者等は、再度均一料金を課すか、または外部サーバに接続するユーザごとに（これにはもはやクリックは必要なく、ズームインするだけで）課金することができる。
【０２６６】
５．掲示板−−実生活と同様に、地図の多くの高可視領域にはかなりの空きスペースがある。会社はこのスペースを購入して、ハイパーリンクおよび、クリックされた場合、ユーザはスペースを通って地図上のどこか他の場所にある商用サイトにジャンプすることになる「ハイパージャンプ」を含むコンテンツを、挿入することができる。通常の商用スペースとは対照的に、掲示板スペースは固定場所でレンタルする必要がなく、その場所はユーザナビゲーションの進行中に生成することができる。
【０２６７】
この最後のサービスでは、「エコロジー」または視覚美学および地図の使いやすさの問題が発生する。地図が魅力的であり、広告における制限および洗練された「区画規制」を示唆するユーザに対する誠実なサービスを残していることが望ましい。地図が掲示板または実世界の地理を映していない他のコンテンツによって乱雑になりすぎた場合、ユーザはオフとなり、広告および電子商取引としての地図の価値は下がることになる。
【０２６８】
本発明者等の統計が集められた場合、これら多くの商用「プラスサービス」の価値を量的に実証することができる。競走上の優位性の量的証拠は、これら付属品の販売を上昇させるはずである。
【０２６９】
非営利ユーザに向けられたプラスサービスは、縮尺、価格、および市場参入が異なる同じ製品のうちのいくつかからなる。
【０２７０】
ズーム可能なＶｏｓｓコンテンツの制限付きオーサリングは、無料クライアント内から可能である。これには、テキストの挿入、デジタル写真のドラッグアンドドロップ、およびパスワードの設置が含まれる。専門的なオーサリングソフトウェアは、より柔軟なズーム可能コンテンツの作成、ならびに、ハイパーリンクおよびハイパージャンプの作成とカスタムアプレットの挿入のための機構を可能にするように設計された、クライアントの修正版とすることができる。
【０２７１】
本発明を使用することで、空間的注目密度（ｓｐａｔｉａｌ  ａｔｔｅｎｔｉｏｎ  ｄｅｎｓｉｔｙ）、ナビゲーションルート、および他のパターンに関する大量の総計および個々の情報を生成することができる。これらのデータには商品価値がある。
【図面の簡単な説明】
【０２７２】
【図１】ＭａｐＱｕｅｓｔウェブサイトから取得したズームレベル５のイメージを示す図である。
【図２】ＭａｐＱｕｅｓｔウェブサイトから取得したズームレベル６のイメージを示す図である。
【図３】ＭａｐＱｕｅｓｔウェブサイトから取得したズームレベル７のイメージを示す図である。
【図４】ＭａｐＱｕｅｓｔウェブサイトから取得したズームレベル９のイメージを示す図である。
【図５】本発明の１つまたは複数の態様による、約３３４メートル／ピクセルのズームレベルで作成されたロングアイランドのイメージを示す図である。
【図６】本発明の１つまたは複数の他の態様による、約１９１メートル／ピクセルのズームレベルで作成されたロングアイランドのイメージを示す図である。
【図７】本発明の１つまたは複数の他の態様による、約１０９．２メートル／ピクセルのズームレベルで作成されたロングアイランドのイメージを示す図である。
【図８】本発明の１つまたは複数の他の態様による、約６２．４メートル／ピクセルのズームレベルで作成されたロングアイランドのイメージを示す図である。
【図９】本発明の１つまたは複数の他の態様による、約３５．７メートル／ピクセルのズームレベルで作成されたロングアイランドのイメージを示す図である。
【図１０】本発明の１つまたは複数の他の態様による、約２０．４メートル／ピクセルのズームレベルで作成されたロングアイランドのイメージを示す図である。
【図１１】本発明の１つまたは複数の他の態様による、約１１．７メートル／ピクセルのズームレベルで作成されたロングアイランドのイメージを示す図である。
【図１２】本発明の１つまたは複数の態様による、イメージの滑らかで連続するナビゲーションを提供するために実施可能なプロセスステップを示す流れ図である。
【図１３】本発明の様々な態様による、イメージを滑らかにナビゲートするために実施可能な他のプロセスステップを示す流れ図である。
【図１４】本発明の１つまたは複数の他の態様による、物理的および非物理的スケーリングを示す、ピクセル単位の線幅に対するメートル／ピクセル単位のズームレベルの、対数−対数で表されるグラフを示す図である。
【図１５】図１４の物理的および非物理的スケーリングにおける変化を示す、対数−対数で表されるグラフを示す図である。
【図１６】ＡからＤは、端点がピクセル座標の中央に精密に位置する、エイリアス除去された垂直線を示す図である。
【図１７Ａ】ＡからＣは、端点がピクセル座標に厳密に収まるように位置付けられていない、傾斜したエイリアス除去された線を示す図である。
【図１８】増分線幅を示す水平線と、２つの隣接する垂直線間の間隔にわたる線幅が２ピクセル以下ずつ変化するように間隔を空けて配置された垂直線とを含む、図１４の線幅に対するズームレベルの、対数−対数で表されるグラフを示す図である。
【図１】
2008501160.tif 000018
【図２】
2008501160.tif 000019
【図３】
2008501160.tif 000020
【図４】
2008501160.tif 000021
【図５】
2008501160.tif 000022
【図６】
2008501160.tif 000023
【図７】
2008501160.tif 000024
【図８】
2008501160.tif 000025
【図９】
2008501160.tif 000026
【図１０】
2008501160.tif 000027
【図１１】
2008501160.tif 000028
【図１２】
2008501160.tif 000029
【図１３】
2008501160.tif 000030
【図１４】
2008501160.tif 000031
【図１５】
2008501160.tif 000032
【図１６】
2008501160.tif 000033
【図１７】
2008501160.tif 000034
【図１８】
2008501160.tif 000035