(57)【要約】      （修正有）【課題】一連の点によって形成されるポリラインの表現を生成する。【解決手段】ポリラインの重なり合ったセクションに冗長に適合する幾何プリミティブの過完備集合を求めることであって、集合が１つ又は複数のタイプの幾何プリミティブを含むように行われ、幾何プリミティブはそれぞれ、一連の点の部分集合によって形成されるポリラインのセクションに当てはめられる。幾何プリミティブの当てはめ誤差と符号化コストとの組合せに基づいて各幾何プリミティブの局所コストを求め、隣接プリミティブの各連続する対の結合コストを求める。次に、ポリラインの長さに沿って連結パスを形成する幾何プリミティブの組合せを求め、この組合せにおける、幾何プリミティブの局所コストと隣接するプリミティブの結合コストとの和が最適化されるようにする。【選択図】図１
2015212936.tif 000002
【特許請求の範囲】
【請求項１】
一連の点によって形成されるポリラインの表現を生成する方法であって、
前記ポリラインの重なり合ったセクションに冗長に適合する幾何プリミティブの過完備集合を求めることであって、該集合が１つ又は複数のタイプの幾何プリミティブを含むようになっており、各幾何プリミティブは前記一連の点の部分集合によって形成される前記ポリラインのセクションに当てはめられていることと、
前記幾何プリミティブと前記ポリラインの前記セクションとの間の当てはめ誤差と、前記幾何プリミティブの符号化コストとの組合せに基づいて、各幾何プリミティブの局所コストを求めることと、
隣接する幾何プリミティブの対間の結合の幾何学的品質と、前記結合の位置の符号化コストとに基づいて、隣接する幾何プリミティブの対の結合コストを求めることと、
前記ポリラインの長さに沿って連結パスを形成する前記幾何プリミティブの組合せを求めることであって、該組合せにおける、前記幾何プリミティブの前記局所コストと前記隣接する幾何プリミティブの対の前記結合コストとの和が最適化されるようにすることと、
を含み、
該方法のステップはプロセッサによって実行される、一連の点によって形成されるポリラインの表現を生成する方法。
【請求項２】
前記点は地理的座標を表す、請求項１に記載の方法。
【請求項３】
前記集合における前記幾何プリミティブのタイプは、線分、円弧及びクロソイドを含む、請求項１に記載の方法。
【請求項４】
半径がｒで中心が点ｃにある前記円弧の前記局所コストを以下の式に従って求めることを更に含み、
【数１】
2015212936.tif 000005
ここで、１＞λ＞０であり、ｘｉは、前記円弧によって当てはめられるｉ番目のポリライン点であり、ｋは座標を量子化するのに必要なビット数であり、ＬＳ(ｒ)は、前記半径を量子化するのに必要なビット数であり、ｊは、次の幾何プリミティブへの前記結合の前記結合コストである、請求項３に記載の方法。
【請求項５】
線分と円弧との組合せによって形成されるパスの前記局所コストを以下の式に従って求めることを更に含み、
【数２】
2015212936.tif 000006
ｘｉは、前記ポリライン上のｉ番目の点であり、ｄ(ｘｉ)は、前記点ｘｉと前記パスとの間の距離であり、ｎｌｉｎｅｓは、前記パス内の線分数であり、ｎａｒｃsは、前記パス内の円弧数であり、パラメーターλａｒｃ＞０は、円弧の相対的な符号化コストを表し、λｌｉｎｅ＞０は、線分の前記相対的な符号化コストを表し、パラメーターλｅｒｒ＞０は、前記当てはめ誤差と前記符号化コストとのトレードオフを表し、ｊｋは、前記パス内の隣接する幾何プリミティブのｋ番目の対間の前記結合の結合コストである、請求項３に記載の方法。
【請求項６】
動的計画法(ＤＰ)を用いて、組合せごとに前記局所コストと前記結合コストとの和を求めることを更に含む、請求項１に記載の方法。
【請求項７】
離散グラフを構築することであって、各結合は重み付きエッジによって表され、各幾何プリミティブは重み付きノードによって表されることと、
前記ポリラインの始点の近傍のエンドポイントを有する幾何プリミティブを表すノードに連結された開始ノードを前記グラフに加えることと、
前記ポリラインの終点の近傍のエンドポイントを有する幾何プリミティブを表すノードに連結された最終ノードを前記グラフに加えることと、
前記開始ノードから前記最終ノードへの最小コストパスを求めることであって、前記幾何プリミティブの前記組合せを生成することと、
を含む、請求項６に記載の方法。
【請求項８】
前記幾何プリミティブの前記組合せを前記ポリラインに再当てはめすることを更に含む、請求項７に記載の方法。
【請求項９】
少なくとも１つの幾何プリミティブは前記ポリライン上にない少なくとも１つのエンドポイントを有する、請求項１に記載の方法。
【請求項１０】
少なくとも１つの幾何プリミティブの少なくとも１つのエンドポイントは、前記一連の点における前記点と一致しない、請求項１に記載の方法。
【請求項１１】
ポリラインの集合の表現を生成することであって、幾何プリミティブの組合せは前記集合におけるポリラインごとに求められることを更に含む、請求項１に記載の方法。
【請求項１２】
ポリラインのエンドポイントにおいて交わる該ポリラインを一緒にチェーン接続して、より長いポリラインにすることによって、前記ポリラインの集合を前処理することを更に含む、請求項１１に記載の方法。
【請求項１３】
単一の地理的特徴の複数のポリラインをリンクさせることによって前記ポリラインを求めることを更に含む、請求項１に記載の方法。
【請求項１４】
交点において交差する２つ以上のポリラインの表現を生成することであって、幾何プリミティブの組合せはポリラインごとに求められることと、
幾何プリミティブの前記組合せのうちの少なくとも１つを変更することであって、前記２つ以上のポリラインに対応する前記連結パスが単一の点において交差するようにすることと、
を更に含む、請求項１に記載の方法。
【請求項１５】
前記幾何プリミティブの前記組合せをサンプリングすることであって、前記ポリラインを近似する新たなポリラインを生成することを更に含む、請求項１に記載の方法。
【請求項１６】
空間上に離散グリッドを重ね合わせることと、
前記離散グリッド上にエンドポイント又は制御点を有する幾何プリミティブのみを生成することであって、符号化ビット数を制限することと、
を更に含む、請求項１に記載の方法。
【請求項１７】
一連の点によって形成されるポリラインの表現を生成するシステムであって、
前記ポリラインの重なり合ったセクションに冗長に適合する幾何プリミティブの過完備集合を求め、
幾何プリミティブと前記ポリラインのセクションとの間の当てはめ誤差と、前記幾何プリミティブの符号化コストとの組合せに基づいて、各幾何プリミティブの局所コストを求め、
隣接する幾何プリミティブの各連続する対の結合コストを求め、
前記ポリラインの長さに沿って連結パスを形成する前記幾何プリミティブの組合せを求め、該組合せにおける、前記幾何プリミティブの前記局所コストと前記結合コストとの和が低減されるようにする、
プロセッサを備える、一連の点によって形成されるポリラインの表現を生成するシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、包括的には、グラフィカル情報システム(ＧＩＳ)に関し、より詳細には、ＧＩＳシステムにおけるポリラインの表現を生成することに関する。
【背景技術】
【０００２】
２次元曲線は、グラフィカル情報システム(ＧＩＳ)における主要なデータタイプである。例には、道路、海岸線及び行政的境界が含まれる。通常、これらの曲線はポリラインとして記憶される。ポリラインとは直線分によって連結された一連の点座標である。ＧＩＳデータをポリラインとして記憶することは、ＧＰＳデバイス上でのマップのズーム等の種々のデータ操作及び視覚化技法に有利であるが、メモリ使用が非効率である。
【０００３】
ポリライン内の点が曲線をオーバーサンプリングすること、すなわちポリラインが曲線を表すのに必要であるよりも多くの点を用いることは珍しくない。オーバーサンプリングは、ポリラインを処理し表示するのに必要なメモリ使用量及び時間の双方の観点で非効率である。さらに、サンプリングされたデータ点は通常、確率的誤差又は雑音を含み、これらは下位ビットにおけるデータ値を支配する可能性がある。
【０００４】
様々な従来の手法が、ポリラインデータをより効率的に表す方法を記載している。例えば、特許文献１及び特許文献２に記載されている方法は、より単純な他のポリラインを用いてポリラインを表している。特許文献３に記載されている方法は、円弧を用いて点の部分集合を表すことによってポリラインを単純化している。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許第６，８１２，９２５号明細書
【特許文献２】米国特許第７，８５９，５３６号明細書
【特許文献３】米国特許出願公開第２０１１／００８７７１５号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、これらの方法は依然として準最適である可能性がある。
【０００７】
この発明の様々な実施の形態は、ポリラインを用いて幾何学的特徴を表すことは準最適である可能性があるという認識に基づいている。特に、幾何学的特徴を表すポリラインは、これらの特徴を形成する幾何プリミティブの区分的当てはめを用いて、より正確に圧縮することができる。例えば、グラフィカル情報システム(ＧＩＳ)における曲線の多くは、道路等の人工の特徴を表す。設計により、道路は直線(ゼロ曲率)、円弧(定曲率)及びクロソイド(一定の曲率変化率)であるセグメントを有する。さらに、これらのセグメントは、地形を通る一定標高のパスが平滑化されたものを有することができる。これは、これらの幾何プリミティブの区分的当てはめを用いて等高線データをより正確に圧縮することができることを示唆している。
【０００８】
通常、ポリラインによって表されるＧＩＳにおける曲線を形成する幾何プリミティブの特定の組合せは未知である。しかしながら、この発明の幾つかの実施の形態は、大域最適化技法を用いて特定の組合せを求める。さらに、幾つかの実施の形態の最適化技法は、表現の正確度のコスト及び各幾何プリミティブの符号化のコストを検討する。このため、ポリラインを表す幾何プリミティブの組合せは、表現の正確度及び圧縮率の双方について最適化される。
【課題を解決するための手段】
【０００９】
したがって、１つの実施の形態は、一連の点によって形成されるポリラインの表現を生成する方法を開示する。本方法は、前記ポリラインの重なり合ったセクションに冗長に適合する幾何プリミティブの過完備集合を求めることであって、該集合が１つ又は複数のタイプの幾何プリミティブを含むようになっており、各幾何プリミティブは前記一連の点の部分集合によって形成される前記ポリラインのセクションに当てはめられていることと、
前記幾何プリミティブと前記ポリラインの前記セクションとの間の当てはめ誤差と、前記幾何プリミティブの符号化コストとの組合せに基づいて、各幾何プリミティブの局所コストを求めることと、
隣接する幾何プリミティブの対間の結合の幾何学的品質と、前記結合の位置の符号化コストとに基づいて、隣接する幾何プリミティブの対の結合コストを求めることと、
前記ポリラインの長さに沿って連結パスを形成する前記幾何プリミティブの組合せを求めることであって、該組合せにおける、前記幾何プリミティブの前記局所コストと前記隣接する幾何プリミティブの対の前記結合コストとの和が最適化されるようにすることと、
を含み、該方法のステップはプロセッサによって実行される。
【００１０】
別の実施の形態は、一連の点によって形成されるポリラインの表現を生成するシステムであって、
前記ポリラインの重なり合ったセクションに冗長に適合する幾何プリミティブの過完備集合を求め、
幾何プリミティブと前記ポリラインのセクションとの間の当てはめ誤差と、前記幾何プリミティブの符号化コストとの組合せに基づいて、各幾何プリミティブの局所コストを求め、
隣接する幾何プリミティブの各連続する対の結合コストを求め、
前記ポリラインの長さに沿って連結パスを形成する前記幾何プリミティブの組合せを求め、該組合せにおける、前記幾何プリミティブの前記局所コストと前記結合コストとの和が低減されるようにする、
プロセッサを備える、一連の点によって形成されるポリラインの表現を生成するシステムを開示する。
【図面の簡単な説明】
【００１１】
【図１】この発明の幾つかの実施の形態による、一連の点によって形成されるポリラインの表現を生成する方法のブロック図である。
【図２Ａ】この発明の幾つかの実施の形態による、ポリラインの重なり合ったセクションの冗長な適合の例の１つである。
【図２Ｂ】この発明の幾つかの実施の形態による、ポリラインの重なり合ったセクションの冗長な適合の例の１つである。
【図２Ｃ】この発明の幾つかの実施の形態による、ポリラインの重なり合ったセクションの冗長な適合の例の１つである。
【図２Ｄ】この発明の幾つかの実施の形態による、ポリラインの重なり合ったセクションの冗長な適合の例の１つである。
【図３】ポリラインの表現を生成するための例示的な実施の形態のブロック図である。
【図４】この発明の幾つかの実施の形態による、動的計画法(ＤＰ)を用いて幾何プリミティブの最適な組合せを求めるための例示的な実施の形態のブロック図である。
【図５】ＤＰの原理を用いて構築される離散グラフの例である。
【図６】幾何プリミティブとポリラインのセクションとの間の当てはめ誤差を求めるための例示的な実施の形態の概略図である。
【図７Ａ】この発明の幾つかの実施の形態による圧縮前後の３つの道路の交差部の概略図の１つである。
【図７Ｂ】この発明の幾つかの実施の形態による圧縮前後の３つの道路の交差部の概略図の１つである。
【図７Ｃ】この発明の幾つかの実施の形態による圧縮前後の３つの道路の交差部の概略図の１つである。
【発明を実施するための形態】
【００１２】
２次元(２Ｄ)曲線は、グラフィカル情報システム(ＧＩＳ)における主要なデータタイプである。例には、道路、並びに政治的境界、自然境界及び行政的境界が含まれる。通常、これらの曲線はポリラインとして記憶される。ポリラインとは、直線分によって連結された一連の点座標である。例えば、自動車のＧＰＳユニット等のポータブルナビゲーションユニットによって記憶され用いられるマップにおいて、道路及び他のマップ特徴は通常、ポリライン又はポリゴンとして表される。
【００１３】
ポリゴンは、同じ点で開始及び終了するポリラインであることに留意されたい。ポリゴンはポリラインの特殊な例として捉えることができるので、本開示はポリラインについてのみ論考するが、ポリラインに関して論考される本方法はポリゴンにも適用することができることを理解されたい。
【００１４】
ＧＩＳデータをポリラインとして記憶することは非効率的である。点が曲線をオーバーサンプリングすること、及び各縦座標の下位ビットが雑音に支配されることは珍しくない。この発明の幾つかの実施の形態は、ＧＩＳの２Ｄ曲線を、幾何プリミティブの組合せを用いてより効率的に表すことができるという認識に基づいている。
【００１５】
ＧＩＳにおける曲線の多くが道路等の人工の特徴を表す。設計により、道路は直線(ゼロ曲率)、円弧(定曲率)及びクロソイド(一定の曲率変化率)であるセグメント、並びに、自然地形を通る一定標高のパスが平滑化されたものであるセグメントを有することができる。これは、これらのプリミティブの区分的当てはめを用いて等高線データを正確に圧縮し、雑音除去することができることを示唆している。
【００１６】
図１は、この発明の幾つかの実施の形態による、一連の点によって形成されるポリラインの表現を生成する方法を示す図である。本方法はプロセッサ１０１を用いて実施することができ、プロセッサ１０１は、スタンドアローンデータ圧縮システムの一部、及び／又はＧＩＳユニット若しくはＧＰＳユニットの一部とすることができる。
【００１７】
本方法は、ポリラインの重なり合ったセクションに冗長に適合する幾何プリミティブ１３７の過完備集合(overcomplete set)を求める(１３０)。この集合は、一連の点の部分集合によって形成されるポリラインのセクションに当てはめられた１つ又は複数のタイプの幾何プリミティブを含むようになっている。本方法は、幾何プリミティブとポリラインのセクションとの間の当てはめ誤差１３５と、幾何プリミティブの符号化コスト１３６との組合せに基づいて、各幾何プリミティブの局所コストを求める(１４０)。本方法は、連結パスにおいて隣接し得るプリミティブの各対間の結合コストも求める(１３８)。
【００１８】
本方法は、組合せ内の幾何プリミティブの局所コストと、組合せ内の隣接する幾何プリミティブの対の結合コストとの和、すなわち総コストが最適化されるように、ポリラインの長さに沿って連結パスを形成する幾何プリミティブの組合せを求める(１５０)。通常、本方法は総コストを低減し、例えば最小にする。しかし、局所コストの定式化に依拠して最適化の他の変形形態が可能である。
【００１９】
図２Ａ、図２Ｂ、図２Ｃ及び図２Ｄは、この発明の幾つかの実施の形態によるポリラインの重なり合うセクションの冗長な適合の例を示している。特に、図２Ａは、４つの順序付けされた点２１０、２２０、２３０及び２４０の集合によって形成されるポリライン２０５の一部を示している。
【００２０】
図２Ｂは、一連の点２１０、２２０及び２３０からなる部分集合によって形成されるポリラインのセクションの冗長な適合を示している。２つの幾何プリミティブ、すなわち線分２２１及び弧２２２がそのセクションに当てはめられている。異なる実施の形態は異なるタイプの幾何プリミティブを当てはめ、それによって異なるタイプの幾何プリミティブがポリラインのセクションに当てはめられることに留意されたい。例えば、１つの実施の形態では、幾何プリミティブのタイプは、線分、円弧及びクロソイドを含む。他の実施の形態は、円錐曲線及びスプライン等の他のタイプの幾何プリミティブを用いることができる。
【００２１】
図２Ｃは、連続点２２０、２３０及び２４０からなる部分集合によって形成されるポリラインの異なるセクションの冗長な適合を示している。２つの幾何プリミティブ、すなわち線分２３１及び弧２３２がそのセクションに当てはめられている。同様に、図２Ｄは、連続点２１０、２２０、２３０及び２４０からなる部分集合によって形成されるポリラインの異なるセクションの冗長な適合を示している。２つの幾何プリミティブがそのセクション、すなわち線分２４１及び弧２４２に当てはめられている。
【００２２】
幾つかの実施の形態では、幾何プリミティブはポリライン上にエンドポイントを有しない。例えば、１つの実施の形態では、集合１３７は、ポリライン上にない少なくとも１つのエンドポイントを有する少なくとも１つの幾何プリミティブを含む。付加的に又は代替的に、別の実施の形態では、集合１３７内の少なくとも１つの幾何プリミティブの少なくとも１つのエンドポイントは、一連の点からの点と一致しない。
【００２３】
図３は、ポリラインの表現を生成するための例示的な実施の形態のブロック図である。実施の形態は、幾何プリミティブの複数の組合せ３１５を求め(３１０)、各組合せはポリラインの長さ全体に沿って一意のパスを形成する。各パスは連結パスであり、組合せ内の各幾何プリミティブがポリラインの一意のセクションに当てはめられ、これらの幾何プリミティブの結合体がポリラインを間隙なしでカバーするようになっている。幾つかの実施の形態では、幾何プリミティブの組合せのうちの少なくとも幾つかは、最適化後にポリラインに再当てはめされる。
【００２４】
実施の形態は、各組合せ内の幾何プリミティブごとに局所コスト３２５を求め(３２０)、各組合せ内の隣接する幾何プリミティブの各対の結合コスト３２８を求める(３２７)。実施の形態は、各組合せ内の幾何プリミティブの局所コスト及び結合コストを合算し、各組合せの総コスト３３５を求める(３３０)。実施の形態は、最低総コストを有する幾何プリミティブの組合せ３４５を選択する(３４０)。
【００２５】
図４は、動的計画法(ＤＰ)を用いて、幾何プリミティブの最適な組合せ、及び／又は組合せごとの局所コストと結合コストとの和を求めるための例示的な実施の形態のブロック図を示している。
【００２６】
図５は、ＤＰが最適な組合せを求めるのに用いる離散グラフ５０１である最適化トレリスの例を示している。ＤＰ手法は、この発明の他の実施の形態によって用いることができることに留意されたい。
【００２７】
実施の形態は、近傍エンドポイントを有する幾何プリミティブの各対に、その幾何プリミティブの対間の結合の幾何学的品質を反映する(例えば平滑性の欠如にペナルティーを科す)結合コストと、結合ロケーションの符号化コストとを割り当て(４１０)、離散グラフ５０１を構築する(４２０)。離散グラフにおいて、各結合は重み付きエッジ、例えばエッジ５２１、５２３、５２５、５２７及び５２９によって表され、各幾何プリミティブは重み付きノード、例えばノード５２０、５２２、５２４、５２６及び５２８によって表される。
【００２８】
実施の形態は、ポリラインの始点の近傍のエンドポイントを有する幾何プリミティブを表すノードに連結された開始ノード５０５をグラフに加え(４３０)、ポリラインの終点の近傍のエンドポイントを有する幾何プリミティブを表すノードに連結された最終ノード５１５をグラフに加える(４４０)。次に、実施の形態は、開始ノードから最終ノードまでの最小コストパスを求め(４５０)、ＤＰを用いて幾何プリミティブの組合せを生成する。
【００２９】
最適化技法は、表現の正確度のコストと、各幾何プリミティブの符号化のコストとを検討する。様々な実施の形態において、各幾何プリミティブの局所コストは、幾何プリミティブとポリラインのセクションとの間の当てはめ誤差と、幾何プリミティブの符号化コストとの組合せに基づく。このため、ポリラインを表す幾何プリミティブの組合せは、表現の正確度及び圧縮率の双方について最適化され、圧縮率及び圧縮の歪みを最適化する。
【００３０】
図６は、幾何プリミティブ６１０とポリライン２０５のセクションとの間の当てはめ誤差を求めるための例示的な実施の形態の概略図を示している。この実施の形態では、当てはめ誤差は、ポリラインの点と、幾何プリミティブとの間の距離、例えば、点２２０及び２３０と線分６１０との間の距離６２０及び６３０の和として求められる。代替的な実施の形態は、当てはめ誤差を求めるのに異なる判断基準を用いることができ、例えば、ポリラインのセクションによって占有される面積と当てはめられた幾何プリミティブによって占有される面積との差を用いることができる。
【００３１】
当てはめコストの当てはめ誤差成分に加えて、最適化は、ポリラインの圧縮表現を最適化するための幾何プリミティブの符号化コストを含む。例えば、各当てはめられた幾何プリミティブは、或る特定の数のパラメーターを用いて表すことができる。例えば、線分は、２つのパラメーター(ｄｘ，ｄｙ)を用いて表すことができ、円弧は３つのパラメーター(ｄｘ，ｄｙ，ｒａｄｉｕｓ)を用いて表すことができ、クロソイドは４つのパラメーター(ｄｘ，ｄｙ，ｓｃａｌｅ，ｓｔａｒｔ)を用いて表すことができる。
【００３２】
また、各種のパラメーターは分布を有し、この分布は、パラメーター化された分布関数、例えば、位置の場合は一様分布、曲率の場合はβ分布若しくはラプラス分布を用いて例示的なデータから近似することができるか、又は例えばデータヒストグラムとしてノンパラメトリックに記憶することができる。この分布に基づいて、エントロピー制約付き量子化方式を選択することができ、幾つかの実施の形態は、量子化方式に関して幾何プリミティブの組合せを生成する。
【００３３】
幾つかの実施の形態では、レートはビット数として明示的に表すことができる。例として円弧を考える。歪み誤差を、各当てはめ点から弧への距離の二乗とする。これはサンプル点にわたって合算されるか、又はポリラインにわたって積分される。(ｄｘ，ｄｙ)の量子化表現を、それぞれｋ個のビット(ｋは表示デバイスの精度によって決めることができる)を用いて表される固定点数とする。曲率パラメーターの量子化表現を、スケールｓにわたるゼロ平均ラプラス分布の最適な量子化からのシンボルとする。ここで、ｓはデータから前もって推定することができる。このとき、当てはめコストは以下となる。
【００３４】
【数１】
2015212936.tif 000003
【００３５】
ここで、１＞λ＞０は、レート／歪みトレードオフを制御するパラメーターであり、ｘｉは、弧によって当てはめられるｉ番目のポリライン点であり、ｃは中心であり、ｒは、弧を含む円の半径であり、ＬＳ(ｒ)は、量子化ビンがｒを含む符号語内のビット数であり、ｊは、パス内の次の幾何プリミティブへの結合の幾何学的品質を反映する(例えば、平滑でない結合にペナルティーを科す)結合コストである。幾何プリミティブの結合コストｊは、パス内の次のプリミティブに依拠し、動的計画法は全ての可能な組合せを考慮することに留意されたい。
【００３６】
幾つかの実施の形態では、レート、すなわちコーディングコストは、明示的にではなく暗黙的に最適化に組み込まれる。例えば、ポリライン｛ｘｉ｝に過完備に当てはめられた幾何プリミティブが線分及び円弧である場合、所与のパスについて、総当てはめコストは以下のように書くことができる。
【００３７】
【数２】
2015212936.tif 000004
【００３８】
ここで、ｘｉは、パスを当てはめられるポリライン上のｉ番目の点であり、ｄ(ｘｉ)は、ｘｉと、パス上のｘｉに最も近い点との間の距離であり、ｎｌｉｎｅｓは、パス内の線分数であり、ｎａｒｃsは、パス内の円弧数であり、ｊｋは、パス内の隣接する幾何プリミティブのｋ番目の対間の結合の幾何学的品質を反映する(例えば、平滑でない結合にペナルティーを科す)結合コストである。パラメーターλａｒｃ＞０及びλｌｉｎｅ＞０の相対的な値は、円弧を符号化するコストに対する線分を符号化する相対的なコストを表し、λｅｒｒ＞０に対するそれらの値によって、レート／歪みのトレードオフが暗黙的に決まる。
【００３９】
パラメーターλａｒｃ、λｌｉｎｅ及びλｅｒｒの値は、サンプルデータに適用すると、所望の圧縮レート、所望の歪みレベル、又は所望のレート−歪みトレードオフをもたらす選択された値を有する例示的なデータに基づくことができる。
【００４０】
さらに、符号化コストは、空間上に離散グリッドを重ね合わせ、このグリッド上にエンドポイント又は制御点を有する幾何プリミティブのみを生成して、パラメーターを符号化するのに用いられるビット数を制限することによって制御することができる。
【００４１】
様々な実施の形態の方法は、例えばパラメトリック空間曲線の過完備な当てはめ(overcomplete fitting)によって、３Ｄにおけるポリラインに拡張することができる。ＧＩＳシステムにおいて、第３の次元は標高である。通常、標高データは位置データよりもスパースでありかつ正確度が低く、標高変化は２Ｄの道路形状と無関係である。このため、標高データは多くの場合に別個に符号化することができる。
【００４２】
道路マップ等のＧＩＳデータは、多くの場合に、それぞれが道路又は特徴の一部を表すポリラインの大きな集合として記憶される。この発明の幾つかの実施の形態では、ポリラインの大きな集合内のポリラインごとに幾何プリミティブの組合せが求められる。
【００４３】
ＧＩＳデータにおけるポリライン等のポリラインの大きな集合において、通常、ポリラインの多くが連結されており、例えばポリラインは単一の道路の複数のセグメントを表す。そのような場合、幾つかの実施の形態は、エンドポイントで交わるポリラインを一緒にチェーン接続して、より長いポリラインにする前処理ステップを含む。結果として得られるポリラインのそれぞれが、ＧＩＳデータからの元のポリラインのうちの１つ又は複数を含むチェーンである。
【００４４】
したがって、幾つかの実施の形態は、単一の地理的特徴の複数のポリラインをリンクさせることによってポリライン１１０を求める。例えば、２つの元のポリラインは、それらの共有エンドポイントにおける傾斜の差が所定の閾値未満であるときにリンクさせることができる。
【００４５】
ポリラインの大きな集合がリンクされてより長いチェーン(それぞれ元のポリラインのうちの１つ又は複数からなる)にされると、ポリラインの大きな集合は、それぞれが元のポリラインのチェーンであるポリラインからなる、より小さな集合として表される。次に、より小さな集合内の各ポリラインは幾何プリミティブの組合せとして近似される。
【００４６】
さらに、更なる圧縮のために、幾つかの実施の形態は、ＧＩＳの元のポリラインデータの全てを近似する曲線シーケンスの全てからなる集合の、算術的符号化等のエントロピーベースの符号化を後処理ステップとして加える。
【００４７】
初期ポリラインの各チェーンは、当てはめられた曲線の組合せによって完全には近似されないので、ＧＩＳデータが圧縮されたものにおいて、当てはめられた曲線が、対応する元のポリラインが交差しなかった場所で交差する場合があるか、又は当てはめられた曲線が、対応する元のポリラインが交差した場所で交差し損なう場合があることが起こり得る。
【００４８】
図７Ａ、図７Ｂ及び図７Ｃに示すように、３つの道路７１０が元のＧＩＳデータにおいて単一点で交差する場合、圧縮後に、道路７２０は３つの別個の交点、例えば道路の対ごとに１つの交差部で交わる場合がある。ＧＩＳデータによっては、圧縮表現において真の交差部を維持するか又は偽の交差部を防ぐことが望ましい場合がある。これは、例えば、圧縮データにおける偽の交差部若しくは失われた交差部を検出し、λｅｒｒのより大きな値を用いて対応するチェーンを再圧縮するか、又は３つの交差位置を平均化して単一の新たな交差位置を得て、次に全ての３つの曲線を、新たな交差位置７３０を通るように変更することによって達成することができる。
【００４９】
圧縮データは、元のポリライン(又はポリラインのチェーン)を、元のポリラインデータを近似する幾何プリミティブの組合せ、すなわち曲線のチェーンとして表す。幾つかの実施の形態では、圧縮の目的は、デバイス内で必要とされるデジタル記憶装置を低減するか、又はデバイスに送信するデータのサイズを低減することである。データが表示されることになるデバイス上で、表示のための１つのオプションは、チェーン内で曲線を直接レンダリングすることである。ポリラインデータのみを処理するように設計されるデバイス、又は演算能力が制限されたデバイスにおいて、まず曲線チェーンをサンプリングして、元のポリラインを近似する新たなポリラインを生成することが望ましい場合がある。
【００５０】
様々なスケール(例えば、よりズームアウトされたスケール)においてデータを表示することが望ましいとき、幾つかの実施の形態は、表示スケールに依拠したサンプリングレートを用いて曲線チェーンをサンプリングする。例えば、よりズームアウトしたスケールでの表示の場合、曲線チェーンはより低いレートでサンプリングすることができ、より少ない点を有するポリラインが得られる。また別の実施の形態は、異なるスケールについて別個にデータを圧縮し、例えば、元の幾何学的形状に対する忠実度により少なくペナルティーを科し、符号化コストに相対的により多くペナルティーを科すコスト関数を用いて元のデータに当てはめを行い、それによって、よりズームアウトされたスケールでの表示に適した、より単純な曲線チェーン(より少ないプリミティブを有する)を得る。
【００５１】
この発明の様々な実施の形態は、数多くの汎用又は専用コンピューティングシステム環境又は構成によって動作することができる。この発明とともに用いるのに適しているコンピューティングシステム、環境及び／又は構成の例は、限定はしないが、パーソナルコンピューター、サーバーコンピューター、ハンドヘルドデバイス又はラップトップデバイス、マルチプロセッサ又はマルチコアシステム、グラフィックス処理ユニット(ＧＰＵ)、特定用途向け集積回路(ＡＳＩＣ)，フィールドプログラマブルゲートアレイ(ＦＰＧＡ)、マイクロコントローラーベースシステム、ネットワークＰＣ、メインフレームコンピューター、上記のシステム又はデバイスのうちの任意のものを含む分散コンピューティング環境等、すなわち、一般的にはプロセッサを含む。
【００５２】
例えば、それらの実施の形態は、ハードウェア、ソフトウェア又はその組み合わせを用いて実現することができる。ソフトウェアにおいて実現されるとき、そのソフトウェアコードは、単一のコンピューター内に設けられるにしても、複数のコンピューター間に分散されるにしても、任意の適切なプロセッサ、又はプロセッサの集合体において実行することができる。そのようなプロセッサは集積回路として実現することができ、集積回路構成要素内に１つ又は複数のプロセッサが含まれる。しかしながら、プロセッサは、任意の適切な構成の回路を用いて実現することができる。
【００５３】
さらに、コンピューターは、ラック取付けコンピューター、デスクトップコンピューター、ラップトップコンピューター、ミニコンピューター又はタブレットコンピューター等の幾つかの形態のうちのいずれかにおいて具現できる。そのようなコンピューターは、企業ネットワーク又はインターネット等の、ローカルエリアネットワーク又はワイドエリアネットワークを含む、任意の適切な形態の１つ又は複数のネットワークによって相互連結することができる。そのようなネットワークは、任意の適切な技術に基づくことができ、任意の適切なプロトコルに従って動作することができ、無線ネットワーク、有線ネットワーク又は光ファイバーネットワークを含むことができる。
【図１】
2015212936.tif 000007
【図２Ａ】
2015212936.tif 000008
【図２Ｂ】
2015212936.tif 000009
【図２Ｃ】
2015212936.tif 000010
【図２Ｄ】
2015212936.tif 000011
【図３】
2015212936.tif 000012
【図４】
2015212936.tif 000013
【図５】
2015212936.tif 000014
【図６】
2015212936.tif 000015
【図７Ａ】
2015212936.tif 000016
【図７Ｂ】
2015212936.tif 000017
【図７Ｃ】
2015212936.tif 000018
【外国語明細書】
2015212936.tif 000019
2015212936.tif 000020
2015212936.tif 000021
2015212936.tif 000022
2015212936.tif 000023
2015212936.tif 000024
2015212936.tif 000025
2015212936.tif 000026
2015212936.tif 000027
2015212936.tif 000028
2015212936.tif 000029
2015212936.tif 000030
2015212936.tif 000031
2015212936.tif 000032
2015212936.tif 000033
2015212936.tif 000034
2015212936.tif 000035
2015212936.tif 000036
2015212936.tif 000037
2015212936.tif 000038
2015212936.tif 000039
2015212936.tif 000040
2015212936.tif 000041
2015212936.tif 000042
2015212936.tif 000043
2015212936.tif 000044
2015212936.tif 000045
2015212936.tif 000046
2015212936.tif 000047
2015212936.tif 000048