【手続補正書】
【提出日】平成30年1月25日(2018.1.25)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】発明の名称
【補正方法】変更
【補正の内容】
【発明の名称】一連の点によって形成されるポリラインの表現を生成する方法およびシステムおよびそのための非一時的コンピューター可読記憶媒体
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
一連の点によって形成されるポリラインの表現を生成する方法であって、
不揮発性コンピューター可読メモリと通信状態にあるプロセッサを用いて、前記ポリラインの重なり合ったセクションに冗長に適合する幾何プリミティブの過完備集合を求めることであって、前記幾何プリミティブの過完備集合は、複数のタイプの幾何プリミティブを含むようになっており、該複数のタイプの幾何プリミティブは、前記一連の点の部分集合によって形成される前記ポリラインの少なくとも１つのセクションに当てはめられていることと、
前記プロセッサを用いて、前記幾何プリミティブと前記ポリラインの前記セクションとの間の当てはめ誤差と、前記幾何プリミティブの符号化コストとの組合せに基づいて、前記幾何プリミティブの過完備集合における各幾何プリミティブの局所コストを求めることであって、前記幾何プリミティブの前記符号化コストは、前記幾何プリミティブを前記不揮発性コンピューター可読メモリ内に記憶するのに必要なビット数の関数であり、少なくとも１つの幾何プリミティブは、前記幾何プリミティブの過完備集合における別の幾何プリミティブの符号化コストとは異なる符号化コストを有することと、
前記プロセッサを用いて、隣接する幾何プリミティブの対間の結合の幾何学的品質と、前記結合の位置の符号化コストとに基づいて、前記幾何プリミティブの過完備集合における隣接する幾何プリミティブの対の結合コストを求めることと、
前記プロセッサを用いて、前記ポリラインの長さに沿って連結パスを形成する前記幾何プリミティブの組合せを求めることであって、該組合せにおける、前記幾何プリミティブの前記局所コストと前記隣接する幾何プリミティブの対の前記結合コストとの和が最適化されるようにすることと、
前記プロセッサを用いて、前記幾何プリミティブの前記最適化された組合せを前記不揮発性コンピューター可読メモリに記憶することと、
を含み、
該方法の結果、前記不揮発性コンピューター可読メモリのメモリ利用の効率性がもたらされる、一連の点によって形成されるポリラインの表現を生成する方法。
【請求項２】
前記点は地理的座標を表す、請求項１に記載の方法。
【請求項３】
前記幾何プリミティブの過完備集合における幾何プリミティブの前記タイプは、線分、円弧及びクロソイドを含む、請求項１に記載の方法。
【請求項４】
半径がｒで中心が点ｃにある前記円弧の前記局所コストを以下の式に従って求めることを更に含み、
【数１】
2015212936.tif 000001
ここで、１＞λ＞０であり、ｘｉは、前記円弧によって当てはめられるｉ番目のポリライン点であり、ｋは座標を量子化するのに必要なビット数であり、ＬＳ（ｒ）は、前記半径を量子化するのに必要なビット数であり、ｊは、次の幾何プリミティブへの前記結合の前記結合コストであり、表記||ｘｉ−ｃ||２は、差ｘｉ−ｃのユークリッド距離を表す、請求項３に記載の方法。
【請求項５】
線分と円弧との組合せによって形成されるパスの前記局所コストを以下の式に従って求めることを更に含み、
【数２】
2015212936.tif 000002
ｘｉは、前記ポリライン上のｉ番目の点であり、ｄ（ｘｉ）は、前記点ｘｉと前記パスとの間の距離であり、ｎｌｉｎｅｓは、前記パス内の線分数であり、ｎａｒｃsは、前記パス内の円弧数であり、パラメーターλａｒｃ＞０は、円弧の相対的な符号化コストを表し、λｌｉｎｅ＞０は、線分の前記相対的な符号化コストを表し、パラメーターλｅｒｒ＞０は、前記当てはめ誤差と前記符号化コストとのトレードオフを表し、ｊｋは、前記パス内の隣接する幾何プリミティブのｋ番目の対間の前記結合の結合コストである、請求項３に記載の方法。
【請求項６】
動的計画法（ＤＰ）を用いて、組合せごとに前記局所コストと前記結合コストとの和を求めることを更に含む、請求項１に記載の方法。
【請求項７】
離散グラフを構築することであって、各結合は重み付きエッジによって表され、各幾何プリミティブは重み付きノードによって表されることと、
前記ポリラインの始点の近傍のエンドポイントを有する幾何プリミティブを表すノードに連結された開始ノードを前記離散グラフに加えることと、
前記ポリラインの終点の近傍のエンドポイントを有する幾何プリミティブを表すノードに連結された最終ノードを前記離散グラフに加えることと、
前記開始ノードから前記最終ノードへの最小コストパスを求めることであって、前記幾何プリミティブの前記最適化された組合せを生成することと、
を含む、請求項６に記載の方法。
【請求項８】
前記幾何プリミティブの前記最適化された組合せを用いることと、
前記幾何プリミティブの前記最適化された組合せを前記ポリラインに再当てはめすることと、
を更に含む、請求項１に記載の方法。
【請求項９】
前記再当てはめすることは、前記幾何プリミティブの前記最適化された組合せにおいて、前記ポリラインの真の交差部を維持するか、偽の交差部を防ぐかのうちの一方、又はその双方をもたらす、請求項８に記載の方法。
【請求項１０】
少なくとも１つの幾何プリミティブは前記ポリライン上にない少なくとも１つのエンドポイントを有する、請求項１に記載の方法。
【請求項１１】
少なくとも１つの幾何プリミティブの少なくとも１つのエンドポイントは、前記一連の点における前記点と一致しない、請求項１に記載の方法。
【請求項１２】
ポリラインの集合の表現を生成することであって、幾何プリミティブの最適化された組合せは前記集合におけるポリラインごとに求められることを更に含む、請求項１に記載の方法。
【請求項１３】
ポリラインの集合を取得することと、
前記取得されたポリラインの集合の表現を生成することであって、該生成することは、
ポリラインのエンドポイントにおいて交わる該ポリラインを一緒にチェーン接続して、より長いポリラインにすることによって、前記取得されたポリラインの集合を前処理し、ポリラインチェーンの集合を取得することであって、前記ポリラインチェーンの各々は、前記取得されたポリラインの集合からの１つ以上のポリラインからなることと、
請求項１に記載の方法のステップを用いて前記ポリラインチェーンの集合における各ポリラインチェーンの表現を生成することと、
を更に含む、請求項１に記載の方法。
【請求項１４】
単一の地理的特徴の複数のポリラインを含む、ポリラインの集合を取得することと、
前記単一の地理的特徴の前記複数のポリラインを一緒にリンクしてポリラインチェーンにすることによって、前記単一の地理的特徴の前記複数のポリラインを前処理することと、
請求項１に記載の方法のステップを用いて前記ポリラインチェーンの表現を生成することと、
を更に含む、請求項１に記載の方法。
【請求項１５】
前記ポリラインの集合からの２つ以上のポリラインは、交点において交差し、幾何プリミティブの最適化された組合せはポリラインごとに求められ、前記幾何プリミティブの前記最適化された組合せを用い、
幾何プリミティブの前記最適化された組合せのうちの少なくとも１つを、前記２つ以上のポリラインを表す前記連結パスが単一の点において交差するように変更する、
請求項１２に記載の方法。
【請求項１６】
前記幾何プリミティブの前記最適化された組合せを用いることと、
前記幾何プリミティブの前記最適化された組合せをサンプリングして、前記ポリラインを近似する新たなポリラインを生成することと、
を更に含む、請求項１に記載の方法。
【請求項１７】
空間上に離散グリッドを重ね合わせることと、
前記離散グリッド上にエンドポイント又は制御点を有する幾何プリミティブのみを生成することであって、符号化ビット数を制限することと、
を更に含む、請求項１に記載の方法。
【請求項１８】
一連の点によって形成されるポリラインの表現を生成するシステムであって、
幾何プリミティブを記憶する不揮発性コンピューター可読メモリと、
前記不揮発性コンピューター可読メモリに結合されたプロセッサであって、
該プロセッサを用いて、前記ポリラインの重なり合ったセクションに冗長に適合する幾何プリミティブの過完備集合を求めることであって、前記幾何プリミティブの過完備集合は複数のタイプの幾何プリミティブを含むようになっており、該複数のタイプの幾何プリミティブは前記一連の点の部分集合によって形成される前記ポリラインの少なくとも１つのセクションに適合されることと、
該プロセッサを用いて、幾何プリミティブと前記ポリラインのセクションとの間の当てはめ誤差と、前記幾何プリミティブの符号化コストとの組合せに基づいて、各幾何プリミティブの局所コストを求めることであって、前記幾何プリミティブの前記符号化コストは、前記幾何プリミティブを前記不揮発性コンピューター可読メモリに記憶するのに必要なビット数の関数であり、少なくとも１つの幾何プリミティブは、前記幾何プリミティブの過完備集合における別の幾何プリミティブの符号化コストとは異なる符号化コストを有することと、
該プロセッサを用いて、隣接する幾何プリミティブの各連続する対の結合コストを求めることと、
該プロセッサを用いて、前記ポリラインの長さに沿って連結パスを形成する前記幾何プリミティブの組合せを求めることであって、該組合せにおける、前記幾何プリミティブの前記局所コストと前記結合コストとの和が最適化されるようにすることと、
該プロセッサを用いて、前記幾何プリミティブの前記最適化された組合せを前記不揮発性コンピューター可読メモリに記憶することと、
を行うように構成され、
前記の方法の結果、前記不揮発性コンピューター可読メモリのメモリ利用の効率性がもたらされる、一連の点によって形成されるポリラインの表現を生成するシステム。
【請求項１９】
方法を行うプロセッサによって実行可能なプログラムを具現された非一時的コンピューター可読記憶媒体であって、前記方法は、一連の点によって形成されるポリラインの表現を生成することを含み、該方法は、
該非一時的コンピューター可読記憶媒体と通信状態にある前記プロセッサを用いて、前記ポリラインの重なり合ったセクションに冗長に適合する幾何プリミティブの過完備集合を求めることであって、前記幾何プリミティブの過完備集合は複数のタイプの幾何プリミティブを含むようになっており、前記複数のタイプの幾何プリミティブは前記一連の点の部分集合によって形成される前記ポリラインの少なくとも１つのセクションに当てはめられていることと、
前記プロセッサを用いて、前記幾何プリミティブと前記ポリラインの前記セクションとの間の当てはめ誤差と、前記幾何プリミティブの符号化コストとの組合せに基づいて、前記幾何プリミティブの過完備集合における各幾何プリミティブの局所コストを求めることであって、前記幾何プリミティブの前記符号化コストは、前記幾何プリミティブを該非一時的コンピューター可読記憶媒体に記憶するのに必要なビット数の関数であり、少なくとも１つの幾何プリミティブは、前記幾何プリミティブの過完備集合における別の幾何プリミティブの符号化コストとは異なる符号化コストを有し、前記誤差を適合することは、前記ポリラインの点と前記幾何プリミティブとの間の二乗距離の和として求められることと、
前記プロセッサを用いて、隣接する幾何プリミティブの対間の結合の幾何学的品質と、前記結合の位置の符号化コストとに基づいて、前記幾何プリミティブの過完備集合における隣接する幾何プリミティブの対の結合コストを求めることと、
前記プロセッサを用いて、前記ポリラインの長さに沿って連結パスを形成する前記幾何プリミティブの組合せを求めることであって、該組合せにおける、前記幾何プリミティブの前記局所コストと前記隣接する幾何プリミティブの対の前記結合コストとの和が最適化されるようにすることと、
前記幾何プリミティブの前記最適化された組合せを用いることと、
前記幾何プリミティブの前記最適化された組合せを前記ポリラインに再当てはめすることと、
前記プロセッサを用いて、前記幾何プリミティブの前記最適化された組合せを前記非一時的コンピューター可読記憶媒体に記憶することと、
を含み、
前記のシステムの結果、該非一時的コンピューター可読記憶媒体の利用の効率性がもたらされる、非一時的コンピューター可読記憶媒体。