(57)【要約】【課題】線分列をより本数の少ない線分で近似する直線近似を行う場合に、従来技術では道路形状の特徴を維持した直線近似ができなかった。本発明では、元の線分列の形状特徴を維持しつつ、より単純化した線分列で表現することを課題とする。【解決手段】２つ以上の線分が接続している接続点において、線分の方向が大きく変化しているかを調べ、大きく変化している接続点においては、その点を残すようにして直線近似を行う。すべての線分を方向によってグループに分けし、接続点においてどのグループの線分とどのグループの線分が接続しているかを調べる。線分が同じグループに属する場合は方向の変化が少ないとみなす。隣り合うグループに属する場合も変化が少ないとみなす。それ以外は方向の変化が大きいとみなす。【選択図】  図３
2008158925.tif 000002
【特許請求の範囲】
【請求項１】
電子的に記憶された線分列を読み出す手段および直線近似処理手段および該直線近似結果の線分列を出力する手段を有する装置であって、該直線近似処理手段が、線分を方向によってグループ分けした後、同じグループまたは隣り合うグループに属していない線分同士を接続している接続点については、削除されることなく直線近似された場合に屈折点として残すことを特徴とする直線近似装置。
【請求項２】
前記直線近似処理手段において、線分を方向によってグループに分けする時に、グループ分けの境界線が水平と垂直の方向にくることなく、水平方向および垂直方向から時計回り又は反時計回りに閾値角度分ずれた方向までを同じグループとすることを特徴とする請求項１に記載の直線近似装置。
【請求項３】
電子的に記憶された線分列を読み出す手段および直線近似処理手段および該直線近似結果の線分列を出力する手段を有する方法であって、該直線近似処理手段が、線分を方向によってグループ分けした後、同じグループまたは隣り合うグループに属していない線分同士を接続している接続点については、削除されることなく直線近似された場合に屈折点として残すことを特徴とする直線近似方法。
【請求項４】
前記直線近似処理方法において、線分を方向によってグループに分けする時に、グループ分けの境界線が水平と垂直の方向にくることなく、水平方向および垂直方向から時計回り又は反時計回りに閾値角度分ずれた方向までを同じグループとすることを特徴とする請求項３に記載の直線近似方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、線分列を直線化する図形処理に関し、道路を線分列で表す場合など図形の特徴をできるだけ維持させながら直線近似させたい場合に用いる線分列の直線近似装置およびその方法に係わる。
【背景技術】
【０００２】
道路をより直線化させ、水平・垂直または４５度方向へ方向量子化させることを基本とする変形方法が行われており、その方法には道路を順次選択して変形していく逐次型の変形方法（非特許文献１）と、すべての道路を徐々に微動させて変形していく並列型の変形方法（非特許文献２）がこれまでに提案されている。
【０００３】
【非特許文献１】梶田健史  山守一徳  長谷川純一：”デフォルメ地図自動生成システムの開発”情報処理学会論文誌,Vol.37（No.9):pp.1736-1744 (Sep 1996)
【非特許文献２】山守一徳  本田宏  長谷川純一：”ストリート単位の道路変形に基づく道路網の整形手法”、電子情報通信学会論文誌、VOL.J84-D-II (No.9):pp.2058-2069 (Sep 2001)
【０００４】
しかしながら非特許文献１で提案されている変形手法は、道路を順次選択して変形していくものであり、複雑な形状の道路地図においては、変形が進むに従って、最後の方の道路では有効な変形が行えないという問題があった。また、この時、優先度の高い道路より順番に変形させることを行っているが、優先度の低い道路の存在によって、交差を引き起こす等の不具合を生じ、充分に変形した位置へ優先度の高い道路を変形させることができないという問題もあった。そこで、これらの問題を解決するために、本発明者は区分分けされた道路ごとに段階的に道路形状を変形させ、優先度の低い区分の道路に対してはその道路の存在による制約を受けることなく道路変形させていくことを特徴とする道路地図自動デフォルメ方法を発明した（特許文献１）。
【０００５】
【特許文献１】特開２００６−２５９０１２号
【０００６】
ところで、直線近似すべき線分列が道路用に限られておらず一般的な線分列を直線近似する方法として、区分的直線近似法がある。この方法では、両端の点を直線で結び、途中の接続点に関して、その直線へ降ろした垂線の足がもっとも長くなる接続点を選ぶ。その垂線の足の長さが閾値以上である場合には、両端を結ぶ線分がその接続点で屈折した線分へ置き換えられる。閾値より短い場合には、両端を結ぶ線分自身が直線近似結果となる。屈折した線分へ置き換えられた場合には、両端位置を置き換えられた線分の位置へ再帰的に変更し、さらに屈折させるか否かの処理を繰り返し行う。
【０００７】
上述の内容を図１を用いて説明すると、点ｘから点ｙに至る太い実線から成る線分列が与えられた場合、点ｘと点ｙを直線で結ぶ線分ｘｙに降ろした垂線の足の長さが最も長くなる点Ａを見つける。点Ａから降ろした垂線の足の長さ（点Ａと点Ｌを結ぶ線分の長さ）が閾値以上の場合、点Ａで線分列を分断する。点Ｘから点Ａに至る太い実線から成る線分列と、点Ａから点Ｙに至る太い実線から成る線分列に分けて、それぞれ同様に、垂線の足の長さが最も長くなる点を見つける。点Ｂ、点Ｃがそれぞれ見つかったとすると、点Ｂと点Ｍを結ぶ線分の長さが閾値以上であるか調べる。また、点Ｃと点Ｎを結ぶ線分の長さが閾値以上であるか調べる。閾値以上ならば、その点で線分列を分断する。閾値より小さいならば、線分列は両端を結ぶ線分で近似される。図１では、線分ＢＭは閾値以上で点Ｂは分断され、線分ＣＮは閾値より小さく点Ｃは分断されない場合を示している。分断された場合には、再帰的に分断されなくなるまで繰り返される。図１では、二重線で表示された線が最終的な直線近似結果となる。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、区分的直線近時法では、置き換えられた線分から接続点が閾値以内の距離に収まるか否かにのみ着目しており、線分の方向が急激に変化する接続点があったとしても垂線の足の距離が閾値以内ならばその接続点は残されない問題が生ずる。又、道路を表す線分列の場合、線分の方向が急激に変化する接続点は、道路形状の特徴的な形状を表しており、線分列を直線近似によって簡単化させる場合において、それらの特徴的な形状の地点を残したいことがある。しかし、区分的直線近似法では、特徴的な形状を残すことができないという問題があった。
【０００９】
さらに、道路を表す線分列を単純化させる場合、水平に近い線分列はより水平に単純化させ、垂直に近い線分列はより垂直に単純化させたい場合がある。人間が水平と垂直の線分を使うことを重要視してデフォルメ地図を描くことが多く、道路を表す線分列を直線近似する場合においても水平と垂直に近づけて近似させたいことがある。しかし、区分的直線近似法では、方向に特異性はなく、水平と垂直のみを重要視して近似することができないという問題があった。
【課題を解決するための手段】
【００１０】
そこで本発明では、線分の方向が急激に変化する接続点を残して直線近似し、水平・垂直方向をより重要視して直線近似する方法を提供することを目的とし、以下の解決手段に到達した。
【００１１】
すなわち本発明は、電子的に記憶された線分列を読み出す手段および直線近似処理手段および該直線近似結果の線分列を出力する手段を有する装置および方法であって、該直線近似処理手段が、線分を方向によってグループ分けした後、同じグループまたは隣り合うグループに属していない線分同士を接続している接続点については、削除されることなく直線近似された場合に屈折点として残すことを特徴とする直線近似装置および方法である。
【００１２】
さらに本発明は、前記直線近似処理手段において、線分を方向によってグループに分けする時に、グループ分けの境界線が水平と垂直の方向にくることなく、水平方向および垂直方向から時計回り又は反時計回りに閾値角度分ずれた方向までを同じグループとすることを特徴とする直線近似装置および方法である。
【発明の効果】
【００１３】
本発明により、線分の方向が大きく変化している接続点においては、その点を残すようにして直線近似を行うことができる。例えば、道路を表す線分列のように、道路形状の特徴的な変化地点を表している線分の方向が急激に変化する接続点について、その点を屈折点として残して直線近似させることができる。また、水平に近い線分列はより水平に単純化させ、垂直に近い線分列はより垂直に単純化させることができる。
【発明を実施するための最良の形態】
【００１４】
本発明の実施形態について下記に説明するが、本発明の技術的範囲は下記の実施形態によって限定されるものではなく、その要旨を変更することなく様々に改変して実施することができる。また、本発明の技術的範囲は、均等の範囲にまで及ぶものである。
【００１５】
本発明における直線近似処理手段において、線分を方向によってグループに分けする時に、グループ分けの境界線が水平と垂直の方向にくることなく、水平方向から時計回りおよび反時計回りに閾値角度分ずれた方向までを同じグループとする、また、垂直方向から時計回りおよび反時計回りに閾値角度分ずれた方向までを同じグループとする分け方をする。
例えば、３６０度を１６個のグループに分ける場合には、１つのグループは、２２．５度の範囲の方向が１つのグループとなり、前記閾値は１１．２５度を用いる。すなわち、水平からプラスマイナス１１．２５度の間の範囲が１つのグループとなる。２つ目のグループは、１１．２５度から３３．７５度の範囲、３つ目のグループは、３３．７５度から５６．２５度の範囲、３つ目のグループは、５６．２５度の範囲から７８．７５度の範囲、４つ目のグループは、７８．７５度から１０１．２５度の範囲となる。以下同様にして、１周に１６個のグループを２２．５度の間隔で割り当てる。
例えば、３６０度を８個のグループに分ける場合には、１つのグループは、４５度の範囲の方向が１つのグループとなり、前記閾値は２２．５度を用いる。すなわち、水平からプラスマイナス２２．５度の間の範囲が１つのグループとなる。２つ目のグループは、２２．５度から６７．５度の範囲、３つ目のグループは、６７．５度から１１２．５度の範囲となる。以下同様にして、１周に８個のグループを４５度の間隔で割り当てる。
【００１６】
本発明の具体的な実施形態を、図面を参照して説明する。３６０度を１６個のグループに分けた場合の例を図２に示す。図２において、グループ１が、水平からプラスマイナス１１．２５度の間の範囲を受け持つグループである。グループ２が、１１．２５度から３３．７５度の範囲を受け持つグループである。線分の方向がその範囲に属する場合、その線分はそのグループに属すると判断する。
【００１７】
次に、３６０度を１６個のグループに分けた場合には、１つ目のグループが、 水平からプラスマイナス１１．２５度の間の範囲を受け持ち、１６個目のグループは、３２６．２５度から３４８．７５度の間の範囲を受け待つが、１つ目のグループと１６個目のグループは隣り合うグループとみなす。
３６０度を８個のグループに分けた場合には、１つ目のグループは、水平からプラスマイナス２２．５度の間の範囲を受け持ち、８個目のグループは、２９２．５度から３３７．５度の間の範囲を受け待つが、１つ目のグループと８個目のグループは隣り合うグループとみなす。
【００１８】
次に、同じグループまたは隣り合うグループに属することのない線分同士を接続している接続点について、与えられた線分列をその接続点で分断させる。分断された線分列をその後直線近似させる。この時の直線近似の方法は、従来の区分的直線近似手法でも良く、その手法は問わない。
【００１９】
次に、本発明の直線近似装置の一構成例を、図３を用いてより具体的に説明する。本発明の直線近似装置１００は、図３に示したように、本発明の記憶される線分列を読み出す手段１０１と、直線近似処理手段１０２と、該直線近似結果の線分列を出力する手段１０３を有する。
【００２０】
又、前記直線近似処理手段１０２は、各線分を方向によってグループに分ける処理１１０と、同じグループまたは隣り合うグループに属することのない線分同士を接続している接続点を抽出する処理１１１と、抽出した接続点で線分列を分断する処理１１２と、分断後の線分列を直線近似する処理１１３を有する。分断後の線分列を直線近似する処理１１３では、例えば区分的直線近似手法などの従来手法による直線近似手法を用いても良いものとする。
【図面の簡単な説明】
【００２１】
【図１】従来手法による区分的直線近似手法による処理方法を説明するための図である。
【図２】本発明による線分を方向によって１６個のグループに分ける場合のグループを説明するための図である。
【図３】本発明の実施形態に係る直線近似装置の一構成例を説明するための図である。
【符号の説明】
【００２２】
１００・・・直線近似装置
１０１・・・記憶される線分列を読み出す手段
１０２・・・直線近似処理手段
１０３・・・直線近似結果の線分列を出力する手段
１１０・・・各線分を方向によってグループに分ける処理
１１１・・・同じグループまたは隣り合うグループに属することのない線分同士を接続している接続点を抽出する処理
１１２・・・抽出した接続点で線分列を分断する処理
１１３・・・分断後の線分列を直線近似する処理
【図１】
2008158925.tif 000003
【図２】
2008158925.tif 000004
【図３】
2008158925.tif 000005