地物形状簡略化装置、簡略化方法およびそのプログラム
【課題】 地図における地物形状は複雑な形状をしており、アプリケーションによって必要とされる簡易な形状を、簡略な手法で生成することが求められていた。
【解決手段】 地物形状を構成する辺を、その方向により４つに分類し（ステップＳ１３０）、各分類に属する辺を一つずつ取り出して、その辺またはこれを延長して得た辺から四角形を構成する（ステップＳ１４０）。この四角形を候補形状として元の地物形状との重なりやはみ出しを計算し、スコアＳＣを求める（ステップＳ１４５）。このスコアＳＣが閾値ＴＳより大きいものがあれば、これを簡略化形状として出力する（ステップＳ１６０）。閾値ＴＳより大きなスコアＳＣを有する四角形が見つからなければ（ステップＳ１５０）、所定の条件を満たす二つの候補形状の和集合を求め（ステップＳ１８０）、これを新たな候補形状として再度スコアＳＣを計算して、簡略化形状を抽出できないか判定する。こうすることで、簡略な処理により、複雑な地物形状を容易に簡略化することができる。
【解決手段】 地物形状を構成する辺を、その方向により４つに分類し（ステップＳ１３０）、各分類に属する辺を一つずつ取り出して、その辺またはこれを延長して得た辺から四角形を構成する（ステップＳ１４０）。この四角形を候補形状として元の地物形状との重なりやはみ出しを計算し、スコアＳＣを求める（ステップＳ１４５）。このスコアＳＣが閾値ＴＳより大きいものがあれば、これを簡略化形状として出力する（ステップＳ１６０）。閾値ＴＳより大きなスコアＳＣを有する四角形が見つからなければ（ステップＳ１５０）、所定の条件を満たす二つの候補形状の和集合を求め（ステップＳ１８０）、これを新たな候補形状として再度スコアＳＣを計算して、簡略化形状を抽出できないか判定する。こうすることで、簡略な処理により、複雑な地物形状を容易に簡略化することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、頂点数Ｎ（Ｎは５以上の自然数）の多角形として表現された建物や土地などの地物の形状を、頂点数Ｍ（Ｍは３以上、Ｎ未満の自然数）の図形に変換する技術に関するものである。
【背景技術】
【０００２】
近年、地図情報はデジタル化されて、自動車のナビゲーションシステムなどに活用されている。こうした地図情報の一つとして、建物の形状がある。いわゆる住宅地図などでは、その場所に存在する建物の平面形状などを再現し、地図の利便性を高めているのである。建物の平面形状は、建築図面に基づいて入力することも可能であるが、多数の建物について、その形状を入力する手間を軽減するために、例えば航空写真を利用し、図形認識などの手法を用いて建物の平面形状を表わすポリゴン（多角形形状）を生成することが行なわれている。
【０００３】
こうして生成されたポリゴンは、実際の建物の平面形状（投影図における投影図形状）に基づいているため、建物が複雑な形状をしていれば、当然認識した形状も複雑なものとなり、頂点の数が１０以上になることも珍しくない。地図情報としてこうした地物形状を扱う場合には、地図情報として許容されるデータの大きさの制限もあり、またあまりに複雑な形状は地図としての使用上は意味をなさない場合もあり、地物形状としての適切な複雑さ（換言すれば、適切な簡略さ）が求められる。そこで、従来から、複雑な形状のポリゴンを簡略化する技術が提案されていた（下記特許文献１、２参照）。
【０００４】
【特許文献１】特開２００３−１４１５５４号公報
【特許文献２】特開２００３−１７８２９９号公報
【０００５】
しかしながら、従来の簡略化の技術では、個々の辺について所定の条件に合致するか否かといった判断を繰り返すため、処理に時間がかかるうえ、その割りに頂点数の大幅な削減を実現することができなかった。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、複雑な地物形状の大幅な簡略化が困難であるという課題を解決するものであり、短時間のうちに建物の形状の簡略化を実現することを目的とする。
【課題を解決するための手段】
【０００７】
かかる目的を実現する本発明の地物形状簡略化装置は、
頂点数Ｎ（Ｎは５以上の自然数）の多角形として表現された地物形状を、頂点数Ｍ（Ｍは３以上、Ｎ未満の自然数）の図形に変換する地物形状簡略化装置であって、
前記地物形状を構成する連続したＮ個の辺の情報を入力する辺情報入力手段と、
該情報を入力したＮ個の辺を、該辺の起点から終点に向かう方向を基準としてＭ種類に分類する辺分類手段と、
該分類された辺から、該分類毎に一つの辺を抽出する辺抽出手段と、
該抽出された辺もしくは該辺を延長した辺とにより、頂点が少なくとも３個以上の多角形を、候補形状として構成する候補形状形成手段と、
該形成された候補形状と前記地物形状とを比較して評価値を求める評価値演算手段と、
該評価値に基づいて、前記地物形状を簡略化した簡略化形状を求める簡略化形状決定手段と
を備えたこと
を要旨としている。
【０００８】
また、この地物形状簡略化装置に対応した簡略化方法は、
頂点数Ｎ（Ｎは５以上の自然数）の多角形として表現された地物形状を、頂点数Ｍ（Ｍは３以上、Ｎ未満の自然数）の図形に変換する方法であって、
前記地物形状を構成する連続したＮ個の辺の情報を入力し、
該情報を入力したＮ個の辺を、該辺の起点から終点に向かう方向を基準としてＭ種類に分類し、
該分類された辺から、該分類毎に一つの辺を抽出し、
該抽出された辺もしくは該辺を延長した辺とにより、頂点が少なくとも３個以上の多角形を、候補形状として構成し、
該形成された候補形状と前記地物形状とを比較して評価値を求め、
該評価値に基づいて、前記地物形状を簡略化した簡略化形状を求めること
を要旨としている。
【０００９】
かかる地物形状簡略化装置またはその方法によれば、頂点数Ｎの多角形として表現された地物形状を、頂点数Ｍの図形に変換することができる（３≦Ｍ＜Ｎ）。この装置または方法によれは、情報を入力したＮ個の辺を、該辺の起点から終点に向かう方向を基準としてＭ種類に分類し、分類された辺から、分類毎に一つの辺を抽出し、抽出された辺もしくは該辺を延長した辺とにより、頂点が少なくとも３個以上の多角形を、候補形状として構成する。その上で、形成された候補形状と地物形状とを比較して評価値を求め、評価値に基づいて、地物形状を簡略化した簡略化形状を求める。従って、簡略な構成で、地物形状の簡略化を実現することができる。辺の起点から終点に向かう方向は、辺がベクトルとして定義されている場合は、その情報をそのまま用いればよく、辺が単に両端の座標により定義されているに過ぎない場合には、そのいずれか一方を起点とし、他方を終点として定義すればよい。この時、一つの辺についていずれか一方が終点とされれば、これに接続された他の辺において、その接続された端点が起点となり、他方が終点となる。地物形状を構成する複数の辺は、順次接続されて閉空間を構成しているから、一つの辺について起点と終点を定めれば、他の辺の起点と終点は、一意に定めることができる。
【００１０】
辺の分類は、辺の起点から終点に向かう方向が、全方向をＭ個に分割したいずれの範囲に属するかにより行なうことができる。面積を有する形状としては三角形が最も辺の数が少ないので、全方向、即ち角度では３６０度（２π）を３分割した１２０度ずつの範囲に属することで、総ての辺を三種類に分類するのが最も簡易な構成である。地物形状は四角形を基準とすることが多いことに鑑み、全方向を４個に分割したいずれの範囲に属するかにより行なっても良い。もとより、Ｍ＝３から順次ＭをＮ−１まで増加させ、総ての場合を尽くすことも差し支えない。この場合、総ての場合を尽くして、評価の最も高いものを地物形状の簡略化形状として求めることにしても良いし、順次評価をして所定以上の評価となる簡略化形状が得られたら、そこで処理を打ち切り、辺の分類以下の処理を終了するものとしても良い。
【００１１】
全方向をいくつかに分割する際には、予め定めた特定の方向（例えば東方向に相当する角度）を基準として、そこからＭ個に分割するものとしても良いし、分類しようとする辺の中で最も長い辺を見出し、その辺の方向を基準として、Ｍ個に分割するものとしても良い。一般に、地物は、日照を考慮して形作られる場合が多いので、東などの特定の方向を基準とすることは、辺の分類において意味を持っている。また、地物を構成する辺のうち最も長い辺が、その地物の基本的な形状の方向性を示している場合が多いので、最も長い辺を基準にして全方向をＭ個に分割することは、地物形状を簡略化するための辺の分類として有効である。なお、最も長い辺の方向を０度として、０ないし３６０／Ｍ度を最初の範囲としても良いが、辺が有する方向の情報に誤差を有することを考慮し、最も長い辺の方向を１８０／Ｍ度とし、０ないし３６０／Ｍ度を最初の範囲とすることも現実的である。もとより、現実的な分割数Ｍが１０程度以下であることに鑑み、最も長い辺を１０ないし１５度程度の予め定めた角度とみなして、全方向をＭ個に分割することも差し支えない。
【００１２】
Ｍ種類に分類された辺のうちから、候補形状を形成するための辺の抽出は、種々の手法が想定されるが、例えば辺の長さに着目して抽出するものとすることができる。この場合、長い辺から順に抽出するものとすれば、少ない辺で元の地物形状に近い形状を候補形状とする可能性を高くすることができる。あるいは一つの分類から一つの辺を抽出した時、他の分類からは、先に抽出された辺と特定の関係、例えばなるべく直交に近い関係にある辺を選択すると言った対応も可能である。
【００１３】
この他、例えば、Ｍ種類に分類された各々の分類に属する辺のうち、絶対値が所定値より大きく、且つ地物形状の周囲長に対して所定の割合より大きな割合を有する辺を抽出の対象とすることも、元の地物形状に近似の形状を候補形状とする上で有効である。
【００１４】
抽出された辺を用いて候補形状を形成する場合、抽出された辺を延長した辺を用いる際には、元の地物形状からはみ出さない形状のみを、候補形状として構成することも実際的である。地物形状は、本来隣接する他の地物形状と重なることのないものであり、はみ出さない形状のみを候補形状とすれば、こうした地物形状の持つ特性を保持できるからである。もとより、一定の割合までは、はみ出しを許容したり、隣接する建物についての簡略化済みの形状との関係で、はみ出しを許容するといった対応も可能である。
【００１５】
抽出された辺により候補形状を構成する際、隣接する２辺が候補形状の内側に形成する総ての角度が、少なくとも２７０度（１．５π）以上の所定の角度より小さい形状のみを、候補形状として構成することも可能である。四角形以上の形状では、その形状の内側に向けて凸の角を形成することが一般に可能である。しかし、通常の地物形状としては、内側に凸の角の内角２７０度以上のものは、特殊な形状として、そのような角を有する形状を候補形状としないことが、処理を簡略化する上で有用である場合が存在する。なお、この角度は、２７０度以上の所定の角度として設定可能であり、２８０度、２９０度など、実際の処理に応じて、予め設定すればよい。
【００１６】
こうして得られた候補形状についての評価は、地物形状と候補形状の各面積および両形状の重なりに基づく面積を用いて評価値を演算することにより行なっても良い。こうした評価値を用いた評価には種々の手法を考えることができる。例えば、両形状の重なりに基づく面積として、両形状の重なった部分の面積および地物形状に対して前記候補形状が重ならない部分の面積のうち、少なくとも一方の面積を求め、この面積の地物形状の面積に対する割合を用いて評価値を求める、といった構成を採用することも差し支えない。こうした評価値の演算は、どのような候補形状を、元の地物形状を簡略化した形状として望ましいと考えるか、という観点から種々の手法を予め決めておくことができる。なお、上記の例で、地物形状の面積に対する割合を求めているのは、いわゆる正規化の処理に相当する。こうしておけば、大きな形状でも小さな形状でも同じ手法で評価することができる。
【００１７】
こうした地物形状の簡略化において、入力した辺情報に基づいて簡略化形状を求める過程で、頂点数Ｎの地物形状を簡略化することを中止すべき所定の条件が成立していることを判断し、簡略化の処理を中止することが考えられる。現実の地物形状の簡略化は、総ての場合に可能であるとは限らず、無用な探索の処理を行なわずに、所定の条件により中止した方が、トータルでは望ましい場合も存在するからである。中止条件が成立していると判断した場合には、地物形状を記述するために用意されたフォーマットで記述された地物形状の辺の情報をそのまま出力するものとすればよい。他方、簡略化情報が決定された場合には、簡略化情報を、地物形状が記述されたフォーマットと同一のフォーマットで出力すればよい。もとより、出力するデータに、中止されたか否かのフラグを付与しても良い。
【００１８】
簡略化の処理を中止する所定の条件としては、入力した総ての辺の長さが所定の判定値以下である場合や、入力した辺情報から、外形形状が曲線の地物形状を短い直線で近似した辺が存在する場合など、あるいは入力した辺情報に基づいて簡略化形状を求める過程で、予め設定した条件を満足する候補形状が一つも得られなかった場合などを考えることができる。
【００１９】
本発明において、候補形状として複数の形状が求められた場合であって、そのうちのいずれの候補形状も、評価値が、予め定めた閾値を超えていない場合には、複数の形状のうち所定の条件を満たす２個以上の形状を合成した形状を新たな候補形状として評価値を求め、評価値が所定の合成条件を満たす場合には、合成した候補形状を、簡略化形状として求めるものとして良い。複雑な形状の建物の場合、単一の候補形状では簡略化できない場合もあり得るからである。
【００２０】
もとよりこうした合成の対象となる候補形状はいくつもあり得るから、合成を行なう２個以上の形状が満たす所定の条件としては、各形状の面積が、地物形状の面積に対して、所定の割合以上であるという条件を設けておくことができる。あるいは、２個の形状が重なっていることや、記合成後の候補形状における隣接する２辺が該候補形状の内側に形成する総ての角度が、少なくとも２７０度以上の所定の角度より小さいことといった条件を設けておくことも差し支えない。複数個の形状の合成を許すと、多数の辺を有する地物形状の簡略化は、極めて複雑なものとなることが考えられる。そこで、通常の地物の形状に基づき、２個の形状を合成するという条件に限ることも差し支えない。「Ｌ」形状の地物などは、大部分２個の形状の合成により、簡略化した形状を見出すことができるからである。もとより、「コ」の字形状の地物も存在するから、合成する形状を３個まで、あるいはそれ以上とすることも差し支えない。
【００２１】
なお、本発明は、こうした地物形状簡略化装置やその方法として把握されるだけでなく、簡略化方法をコンピュータにより実現するプログラムの発明や、そのプログラムを記録した家禄媒体としての発明等として把握することも可能である。
【発明を実施するための最良の形態】
【００２２】
本発明の一実施例としての地物形状簡略化装置とその方法について、以下実施例を挙げて説明する。図１は、実施例としての地物形状簡略装置１０の概略構成図である。この装置１０は、演算処理を行なうＣＰＵ２１、処理用のワークエリアなどに用いられるＲＡＭ２２、モニタプログラムなどを記憶するＲＯＭ２３、使用者の指示を入力するマウス付きのキーボード２５、処理中の地物形状などを表示するディスプレイ２７、地物形状データベースＢＤＢなどを記憶するハードディスク３０等を備えている。この実施例では、簡略化の処理の対象となる地物形状は、予め建物を構成する複数の線分の集合として定義されており、データベースを構成している。
【００２３】
図２に、地物形状データベースＢＤＢのデータ構造の一例を示す。図示するように、この例では、地物形状データベースＢＤＢには、大きくは、「要素種別」「中抜き面数」「外枠面情報」が記憶されている。要素種別は、このデータベースＢＤＢが、更に上位の地図データベースの一部を構成していることから、地図データベースＧＤＢにおいて、どのような要素に該当するかを示す情報である。本実施例では、要素種別は、地図データベースＧＤＢ中では、面や中抜きの情報であることを示す値を持っている。中抜き面数は、一つの地物形状に、中抜きの部分がある場合に、その中抜きの部分の数を示す情報である。このデータベースＢＤＢでは、中抜きはないとして扱うので、総ての地物形状において、中抜き面数は、値０となっている。
【００２４】
外枠面情報は、地物形状を示す外枠を構成するｎ点の座標のデータからなっている。外枠面情報は、外枠面座標点数の情報とここで定義された数ｎだけの座標のデータとから構成されている。図３は、地物形状データベースＢＤＢに登録された一つの建物についての外枠面情報との対応関係を示す説明図である。図示するように、この地物形状は、１７の辺から構成されており、各辺は総て連結点で連結されている。この連結点ＣＰを、連結点ＣＰ１から連結点ＣＰｎまで、そのｘ座標およびｙ座標の組み（ｘ１，ｙ１）・・・（ｘｎ，ｙｎ）で表わしたものが、地物形状データベースＢＤＢの「外枠面情報」である。この例ではｎ＝１７であり、全部で１７の連結点ＣＰ１ないしＣＰ１７の座標データを記録している。この例では、連結点ＣＰの座標を記述しているが、連結点ＣＰ１と連結点ＣＰｎとは、異なる点であり、連結点ＣＰｎの次が連結点ＣＰ１であるとして扱うものとして、総ての連続する連結点間には、辺が存在することになる。従って、このデータベースＢＤＢは、連結点ＣＰの座標を記憶しているが、本質的には、地物形状を構成する辺を定義しているのである。建物毎に形状は異なるので、連結点の数も異なるから、このデータベースＢＤＢは、いわゆる可変長のデータベースである。
【００２５】
ＣＰＵ２１は、後述する簡略化プログラムを、ハードディスク３０から主記憶を構成するＲＡＭ２２に一旦ロードし、主記憶上のプログラムを実行することにより、この地物形状の簡略化を行なう。図３に示した例では、簡略化された後の形状は例えば図４に示すように、連結点が６個の形状となっている。なお、簡略化後の連結点は、必ずしも元の地物形状が備えていた連結点と一致するとは限らないから、図４では、簡略化後の連結点をＶＰで表わすものとしている。この場合の簡略化形状も、図２に示したデータベースと同様のフォーマットで定義している。簡略化された地物形状のデータベースを、簡略化地物形状データベースＳＤＢと呼ぶ。この簡略化地物形状データベースＳＤＢも、地物形状データベースＢＤＢと同様ハードディスク３０に記憶される。なお、詳しくは後述するが、簡略ができない場合も当然にあり得、この場合には、簡略化されていない元のデータ（図２参照）がそのまま簡略化地物形状データベースＳＤＢに保存される。
【００２６】
次に、地物形状簡略化装置１０が実行する処理について説明する。図５は、この装置１０が実行する処理を示すフローチャートである。簡略化装置１０は、地物形状データベースＢＤＢが準備され、キーボード２５を介して簡略化処理の開始を指示されると、まず地物形状データベースＢＤＢにアクセスして、データベースＢＤＢから、最初の地物形状データを読み出す処理を行なう（ステップＳ１００）。要するに、ハードディスク３０から、図２に示した一つの建物に相当するデータを読み出すのである。続いて、簡略化の閾値ＴＳを読み出す処理を行なう（ステップＳ１１０）。この閾値ＴＳは、元の地物形状を簡略化する際のいわば評価を行なうための閾値である。詳しく後述するが、所定の条件で得られた候補形状が、簡略化されたものとしてみなして良いか否かの判断基準を与えるものである。
【００２７】
こうした閾値ＴＳは、総ての地物形状に対して一律に同じ値としても良いが、地物形状が有する特性により変更するものとしても良い。例えば、地物形状の複雑さ、つまり通常は連結点ＣＰの数の多寡に応じて変更するものとしても良い。形状が複雑になれば、閾値をある程度下げてやらないと、簡略化ができたと判断することが困難になる場合が想定されるからである。もとより、地物形状の複雑さではなく、地物形状の大きさ（占有面積）や隣接する建物との距離や建物の種別（目標物なのか個人家屋なのか等の種別）などにより、閾値ＴＳを変更するものとしてもよい。実施例では、図６に示すように、着目した地物形状の面積ＳＳに応じて、下限値ＴＳｌから上限値ＴＳｕの間の値を取るものとしている。即ち、実施例においては、閾値ＴＳは、地物形状の面積ＳＳが下限ＳＬ以下であれば値ＴＳｌに等しく、地物形状の面積ＳＳが上限ＳＵ以上であれば値ＴＳｕに等しく、地物形状の面積ＳＳが下限ＳＬから上限ＳＵまでの間に入っている場合には、下限値ＴＳｌと上限値ＴＳｕとの間を線形補間した値として定義されている。もとより、線形補間などの処理に代えて、閾値ＴＳをテーブルの形で保持し、地物形状データベースＢＤＢ内から一つの地物形状のデータを読み出したとき（ステップＳ１００）、その面積を計算し、テーブルを参照して閾値ＴＳを読み込むものとしても良い。
【００２８】
こうして地物形状データベースＢＤＢから一つの建物のデータを取得し（ステップＳ１００）、その地物形状の簡略化のための閾値ＴＳを読み込んだ後（ステップＳ１１０）、次に簡略化が可能か否かの判断を行なう（ステップＳ１２０）。簡略化が可能な否かの判断については、詳しくは図７を用いて後述するが、総ての地物形状について簡略化が可能な訳ではないからである。ステップＳ１２０において、簡略化が可能でないと判断された場合は、ステップＳ１２５に移行し、地物形状データベースＢＤＢから取得したデータ（図２参照）を、そのまま簡略化後の簡略化地物形状データベースＳＤＢとして出力する処理を行なう。このように簡略化の処理ができない場合でも、データベースＳＤＢにデータを書き出しておくのは、本実施例では、地図を描画するために、簡略化できない地物形状も含めて総ての建物についてのデータを揃えておくためである。単に地物形状の簡略化だけを目的としている場合には、簡略化されなかった地物形状については、データを出力しない構成とすることも差し支えない。
【００２９】
簡略化可能か否かの判断の内容について、図７に依拠して説明する。図７は、簡略化の判断処理ルーチン（ステップＳ１２０）の詳細を示すフローチャートである。図示するように、この処理が開始されると、まず、地物形状データベースＢＤＢから取得した一つの建物のデータに基づき、この地物形状を構成している各辺のＸ方向長さおよびＹ方向長さが、総て所定値Ｌ１より小さいか否かの判断を行なうのである（ステップＳ１２１）。ｉ番目の連結点ＣＰi と次の連結点ＣＰi+1 間に存在する辺のＸ方向、Ｙ方向の長さＬｘｉ，Ｌｙｉは、
Ｌｘｉ＝｜ｘi+1 −ｘi ｜
Ｌｙｉ＝｜ｙi+1 −ｙi ｜
として簡易に求めることができる。そこで、これらの辺の長さＬｘｉ，Ｌｙｉが総て所定値Ｌ１以下であれば、地物形状が小さな微小建物であるとして、簡略化の処理を行なわないと判断するのである。
【００３０】
地物形状を表わす各辺に、長さＬ１以上のものがあると判断されれば（ステップＳ１２１）、続いて、着目している地物形状の一部に曲線図形が含まれるか否かの判断を行なう（ステップＳ１２２）。本実施例では、円形のホールなど、外形形状の少なくとも一部に曲線形状が含まれる場合、これを短い直線の連続として記述している。従って、所定値Ｌ２以下のショートベクトルが、所定値Ｎ１以上連続している場合には、これを曲線形状を近似していると判断し、簡略化の処理の対象から外すという判断を行なうのである。本実施例では、簡略化は、直線近似に拠っているので、もともと曲線形状の図形の簡略化は行なわないとしているのである。なお、実施例では、実際の長さ２５センチを１単位として、Ｌ１は４０単位分として設定した。同様に、実施例では、Ｌ２は１０単位分（２．５メートル相当）でＮ１＝１０として、曲線図形の判断を行なった。もとより、曲線図形を簡略化の処理から排除せず、他の図形と同じように簡略化の処理の対象とすることも差し支えない。
【００３１】
上記ステップＳ１２１，Ｓ１２２の判断により、候補形状の生成ができないと判断した場合には、「１」に抜けて、本ルーチンを一旦終了する。「１」は、図５に示した処理の連結箇所であり、この場合には、上述したステップＳ１２５に処理は移行し、候補形状は生成できないとして、元の地物形状のデータのコピーを行なうのである。他方、ステップＳ１２１，Ｓ１２２で、簡略化の処理が可能と判断された場合には、「ＮＥＸＴ」に抜けて、本処理ルーチンを終了し、図５の処理に戻る。
【００３２】
簡略化の処理が可能と判断した場合には、次に、地物形状データベースＢＤＢから取得したデータに含まれる総ての辺を、４つに分類する処理を行なう（ステップＳ１３０）。４つ分類するとは、本実施例では、各辺を始点と終点を持つベクトルとみなし、そのベクトルの有する角度θが、４つの象限のいずれに属するかを判定する処理である。４つの象限は、本実施例では、最も長い辺を基準にして定めている。即ち、まず全ての辺を探索して最も長い辺を見出し、この辺の方向を角度０として、−０．２５π≦θ＜０．２５πを第１象限、０．２５π≦θ＜０．７５πを第２象限、０．７５π≦θ＜１．２５πを第３象限、１．２５π≦θ＜１．７５πを第４象限として定めている。その上で、各辺がこれら４つの象限のいずれに属するかにより分類する。図８に、辺Ｓ１ないしＳ８からなる地物形状の一例を示した。この例では、辺Ｓ５が最も長いので、この辺を基準にして分類を行なうと、図９に示した結果となる。
【００３３】
この実施例で４つに分類したのは、便宜的なものであり、５つに分類しても差し支えない。また、各分類は、辺の方向に基づいて行なっていれば足り、４つに分類する場合であっても、各角度範囲は必ずしも９０度ずつである必要はない。各分類の角度範囲は、一つ一つ予め定めておくものとしても良い。また、本実施例では、最も長い辺の方向を基準として、各象限の範囲を定めたが、所定の方向、例えば実際の地図上における東に相当する方向を角度０として、各象限を定めても良い。
【００３４】
こうして辺を４つに分類した後、候補形状が生成可能か否かの判断を行なう（ステップＳ１３５）。候補形状は、４つの分類の各々から一つの辺を取り出し、都合４つの辺を組み合わせることにより生成される。もとより、元の地物形状が５個以上の連結点ＣＰを有するものであれば、４つに分類された辺を一つずつ取り出しても各辺は必ずしも連結しない。そこで、候補形状の生成時には、各分類から取り出した４つの辺については、適宜延長することにより、候補形状を生成するものとしている。
【００３５】
図８に例示した地物形状に沿って、候補形状の生成について説明する。図８に示した地物形状は、８個の連結点ＣＰ１ないしＣＰ８を有することから、隣接する各連結点ＣＰを番号の小さい方から大きい方に向かって右周りに接続する８個の辺Ｓ１ないしＳ８から構成されている。各辺Ｓ１ないしＳ８を、ベクトルとみなしてその方向を上記の４つの角度範囲に分類する。なお、方向が分かりやすいように、図８では、各辺は、終点側に矢印を有するベクトルとして示した。分類した結果は、図９に示されている。図９において、第１象限ないし第４象限の４つに分類された各辺については、更に長さが長いものを上位にして分類してある。即ち、全ての辺の中で最も長い辺であるＳ５が属するのが第１象限となり、第２象限には辺Ｓ４、Ｓ２が属し、この順に上位の辺Ｓ４が長く、第３象限には辺Ｓ１、Ｓ３、Ｓ７が属し、この順に上位の辺Ｓ１が最も長く、第４象限には辺Ｓ８、Ｓ６が属し、この順に上位の辺Ｓ８が長くなっている。そこで、各象限に分類された辺のうち、長いものから順次取り出し、それらの組み合わせて、候補形状を生成するのである。生成される候補形状の例を図１０および図１１に示した。各図において、元の地物形状を破線で、選択した辺を実線で、各辺をその交点まで延長した部分を一点鎖線で、それぞれ示した。図１０では、各分類において最も長い辺Ｓ１、Ｓ４、Ｓ５、Ｓ８の組み合わせとして、候補形状ＳＳ９が生成されている。また図１１では、基本的には、図１０と同様、各分類から、長い辺を取り出して候補形状を生成しているが、この例では、第３象限に属する辺についてのみ、二つの辺Ｓ２、Ｓ４から、２番目に長い辺Ｓ２を用いて候補形状ＳＳ１０を生成している。両者を比較すると、候補形状ＳＳ９では、図示の領域ＢＢ９が、元の地物形状から見るとはみ出した領域となっているのに対して、候補形状ＳＳ１０では、こうしたはみ出した領域が存在しない。
【００３６】
図８ないし図１１は、候補形状が生成できた場合を示しているが、形状によっては、候補形状として扱えない形状しか構成できない場合が存在する。そこで、その条件として、本実施例では、次の条件を定めている。即ち、
（１）各分類から取り出した各辺Ｓの長さをＬＬとしたとき、
（１−１）ＬＬ＞Ｌ３であること、
（１−２）ＬＬ／ＬＡ＞Ｔ４であること
（ここで、ＬＡは、地物形状の周囲長である）、
（２）候補形状における各内角αは、α≦（２π−Ｔ５）であること、
という条件を満足する場合にのみ、候補形状が生成可能と判断するのである。なお、実施例では、Ｔ５＝０．５［rad ］としたが、この大きさは出力する地図の大きさなどによっても影響を受ける。
【００３７】
上記条件（１−１）は、絶対値があまりに短い辺を無理に拡長して候補形状を生成させないためであり、条件（１−２）は、絶対値としては所定の長さＬ３以上ある辺でも、元の地物形状が大きい場合、相対的に小さな辺を拡張して候補形状を生成させないためであり、条件（２）は、図１２に示すように、内側にあまりに深く切れ込んだ形状を候補形状としないための条件である。辺を４つに分類して組み合わせる場合には、通常この条件（２）により除外される候補形状は少ないが、分類を５つ以上にした場合などには生じる可能性がある。
【００３８】
分類した総ての辺の組み合わせを試しても、上記の条件の総てを満足する形状が得られない場合には、候補形状は生成不可能として（ステップＳ１３５）、ステップＳ１２５に移行し、上述した地物形状のデータをコピーする処理を行なう。他方、総ての辺の組み合わせを試してみたとき、上記の（１−１）（１−２）（２）の総ての条件が満たされる形状が見出された場合には、候補形状は生成可能であると判断し、次に、候補形状を生成する処理を行なう（ステップＳ１４０）。候補形状は、既に図８ないし図１１を用いて例示したように、複数生成可能なことが多い。本実施例では、上記の条件を満たして生成できる総ての形状を、候補形状として生成するのである。
【００３９】
候補形状を生成した後、次に各候補形状についてのスコアＳＣを計算する処理を行なう（ステップＳ１４５）。スコアＳＣは、本実施例では、元々の地物形状の面積をＡ、候補形状の面積をＢとして、次式（１）により計算する。
ＳＣ＝（ＡＢ−λ・ＢＢ）／Ａ …（１）
ここで、ＡＢは地物形状と候補形状の積面積、ＢＢは、ＢＢ＝Ｂ−ＡＢ、つまり候補形状が、地物形状との重なりの形状からはみ出している面積である。また、λは、そのはみ出し量に対する重み付け係数（ペナルティ）である。
【００４０】
上記式（１）において、ＡＡを、ＡＡ＝Ａ−ＡＢ、つまり元々の地物形状が、候補形状との重なりの形状からはみ出している面積として定義すると、
ＳＣ＝（Ａ−ＡＡ−λＢＢ）／Ａ
と変形できるから、スコアＳＣは、結局、着目した候補形状が、地物形状に対して過小である面積ＡＡと、過大である面積ＢＢとを、共に評価していることになる。従って、λ＝１とすれば、過小な部分と過大な部分とに等しい重み付けがなされていることになり、λ＝０とすれば、過大な部分があっても許容することになり、λ＝∞とすれば、はみ出しを一切許容しないことになる。本実施例では、隣接した建物を簡略化した後の簡略化形状が互いに重ならないことを優先して、λ＝１００に設定してある。なお、全体Ａで除しているのは、スコアＳＣを地物形状の大小に拠らない値とする（正規化する）ためである。
【００４１】
スコアＳＣを計算した後、次に、ステップＳ１４０で生成した候補形状スコアＳＣが、先に読み込んだ（ステップＳ１１０）閾値ＴＳより大きいか否かの判断を行なう（ステップＳ１５０）。候補形状が複数生成されている場合には、総ての候補形状について判定するのである。ここで、スコアＳＣが、閾値ＴＳを上回る候補形状が存在すれば、閾値ＴＳを越えるスコアＳＣを有する候補形状の中から、最もスコアの高い候補形状を簡略化形状として出力する処理を行なう（ステップＳ１６０）。出力の形式は、ステップＳ１２５で説明したように、地物形状のものと同じフォーマットである。その後、地物形状データベースＢＤＢに保存されている全ての建物について簡略化の処理を完了したかを判別し（ステップＳ１７０）、完了していなければ、ステップＳ１００に戻って、地物形状データベースＢＤＢからデータを取得する処理以下を繰り返す。
【００４２】
スコアＳＣを計算した後（ステップＳ１５０）、閾値ＴＳを上回るスコアＳＣを有する候補形状が見いだせなかった場合には（ステップＳ１５０）、次に和集合を生成する処理を実行する（ステップＳ１７０）。和集合の生成は、次のように行なう。ステップＳ１４０で生成した候補形状（いずれも四角形）のうち、面積が大きい順にＮ２個を取り出し、且つその面積Ｂの地物形状の面積Ａに対する比（Ｂ／Ａ）が、所定値Ｔ２を越えているものを対象に、２つの四角形同士の和集合を生成して、これを新たな候補形状とするのである。図８に示した例では、図１３に示すように、辺Ｓ１−Ｓ２−Ｓ５−Ｓ８により形成した四角形ｄＳ１、辺Ｓ２−Ｓ３−Ｓ４−Ｓ５により形成した四角形ｄＳ２との和集合ＳＳｏｒが、新たな候補形状となるのである。なお、二つの四角形に重なりの部分を生じないものについては、簡略化候補とはしないものとした。同様に、重なりがあっても、いずれか一つの内角αが、α≦（２π−Ｔ５）となってしまう組み合わせについても除外するものとした。更に、二つの四角形を組み合わせた形状が元の地物形状より複雑な形状となる場合も除いている。
【００４３】
その後、和集合が一つでも生成できたかを判断し（ステップＳ１８０）、一つも生成できなければ、簡略化の処理をできないとして、上述したステップＳ１２５に移行して元のデータをそのまま出力し、着目した地物形状についての簡略化の全処理を終了する。他方、一つでも和集合が生成できた場合には（ステップＳ１８０）、ステップＳ１４５に戻って、その和集合の形状についてのスコアＳＣの計算から、上述した処理を繰り返す（ステップＳ１４５ないしＳ１６０）。和集合の形状について、スコアＳＣが閾値ＴＳより高いものが存在すれば、そのうちの最上位のスコアの和集合を、簡略化形状として出力する処理を行なう（ステップＳ１６０）。いずれの場合もこれで着目した地物形状については簡略化の処理が終了したことになるので、地物形状データベースＢＤＢ内の全ての地物形状についての簡略化の処理が完了したかを判別し（ステップＳ１７０）、完了するまで、上記の処理を継続する。
【００４４】
以上説明した本実施例によれば、多数の複雑な地物形状を、簡略な処理により、四角形またはその二つの和集合の形状に簡略化することができる。従来、地図上に存在する地物形状などの多数の、しかも複雑な形状を、高速に処理して簡略することは極めて困難であった。カーナビゲーションなどに用いられる地図の元になっている詳細な地図（地物形状なども実際に即した形状で入力されている住宅地図など）から、ナビゲーションシステム用の地図を生成する場合など、何千万という数の地物形状を簡略する必要がある場合もあり、こうした処理を高速に行なう簡略化装置および簡略化方法は、極めて有用である。また、本実施例では、簡略化できないものについては無理な簡略化を行なわず、入力した地物形状のデータをそのまま出力しているので、そのまま地図などの描画に用いることができる。全ての地物形状が簡略化されていなくても、大部分の地物形状が簡略化されれば、トータルのデータ容量を低減することができるので、例えば地物形状のデータを容量の限られたＤＶＤなどに収録する際に便利である。また、簡略化されていない形状は、連結点の数を見れば容易に判別できるので、それらのデータのみを抽出し、時間はかかるが例外的な形状でも簡略化する他の簡略化方法を採用して、簡略化の処理を行なうものとしても良い。この場合、多数の地物形状は本実施例の手法で簡略化を済ませているので、例え他の手法が、簡略化の処理に時間を要するものであっても、トータルの時間をさほど長くしないで済ませることができる。
【００４５】
また、本実施例では、簡略化を評価する閾値ＴＳを、地物形状の面積ＳＳにより図６に示したように変化させている。従って、面積が大きくなるに従って、地物形状と近似の候補形状しか出力しなくなるのである。形状が大きくなれば、一致の割合が等しくなっても、はみ出したり不足していたりする面積それ自体は大きくなる。このため、地物形状の面積ＳＳが大きくなるほど、一致率の高いもののみを簡略化形状として出力することになる。この場合、面積の大きな地物形状ほど、簡略化されにくいことになるが、現実には、大きな地物形状ほど、これを構成する辺の数も多く、様々な候補形状を作り得ること、大きな地物形状ほど、地物形状データベースＢＤＢ内での占める割合は相対的に小さくなるから、そのままデータを出力しても全体としてのデータ量の増大はさほど大きなものとならないことなどから、簡略化によりデータ全体の容量の低減の効果は享受することができる。
【００４６】
また、本実施例では、スコアＳＣを計算するとき、係数λを用いて、はみ出し部分についての評価の割合を容易に変更できるようにしている。従って、対象となる地物形状の性質に応じて、はみ出しを許さないという条件（λ＝∞）から、はみ出しを重なっていない部分と同程度に評価する条件（λ＝１）、更には、はみ出しにスコア上のペナルティを与えない条件（λ＝０）まで、簡易に設定することができる。
【００４７】
更に、本実施例では、単一の四角形では十分な簡略化が達成できない場合には、所定の条件を満たした候補形状の和集合を求めて新たな候補形状とすることができる。この場合でも、評価の手法は変える必要がなく、また和集合の元になる四角形の候補形状は先に抽出しているので、その取り扱いは容易である。建物は、四角形の組み合わせで実現されることが多いので、四角形かその和集合で簡略化すると、元の形状の特徴を残し易いという利点が得られる。同様の理由から、和集合を求めて再度評価する手法は、簡便なものでありながら、効果は大きい。なお、本実施例では、最初に求める候補形状は、四角形としたが、五角形や六角形まで許容するものとしても良い。また、和集合は二つに限るものではなく、三つあるいはそれ以上の和集合を許容するものとして簡略化の処理を行なっても良い。
【００４８】
以上説明した本実施例では、簡略化の処理は、専用の簡略化装置１０を用いて行ない、地物形状データベースＢＤＢから、表示や出力を行なうために、簡略化地物形状データベースＳＤＢを形成したが、図５、図７を用いて説明した簡略化のアルゴリズムを表示や出力を行なう装置に組み込んでおき、必要に応じてその場で簡略化の処理を施すものとしてもよい。カーナビゲーションシステムや携帯電話の画面に地図を表示するような場合には、一度に表示に供される地物形状の数はさほど多くないので、必要な地物形状だけ簡略化して表示などを行なうものとすることも可能である。例えば、ネットワークを介して接続された携帯電話などの端末装置に地図を表示する場合、地図データそのものはサーバ側に用意される。しかも端末装置側での表示の倍率は様々なので、倍率によっては、サーバに蓄積した地物形状データベースＢＤＢのデータをそのまま使って建物を表示したい場合も存在する。また縮尺を小さくして、建物の形状を簡略化しつつ表示したい場合も存在する。後者の場合に、縮尺に応じて、閾値ＴＳを調整しつつ、表示しようとする領域に含まれる地物形状のみ簡略化処理を行なうものとすることができる。この場合の簡略化の処理は、サーバ側で行なっても良いし、端末装置側で行なっても良い。
【００４９】
以上本発明の一実施例について説明したが、本発明は、こうした実施例に何ら限定されるものではなく、本発明の要旨を変更しない範囲内において、種々なる態様で実施できることは勿論である。
【図面の簡単な説明】
【００５０】
【図１】本発明の一実施例としての簡略化装置１０の概略構成図である。
【図２】簡略化装置１０における地物形状データベースＢＤＢのデータ構造を説明する説明図である。
【図３】簡略化の対象となる地物形状の一つを例示した説明図である。
【図４】簡略化された後の簡略化形状を例示する説明図である。
【図５】本実施例における簡略化処理ルーチンを示すフローチャートである。
【図６】閾値ＴＳの設定手法を示すグラフである。
【図７】簡略化の判断処理ルーチンの一部を示すフローチャートである。
【図８】４つに分類された辺に基づいて候補形状を生成する様子を示す説明図である。
【図９】各辺Ｓ１ないしＳ８の分類の様子を示す説明図である。
【図１０】候補形状と地物形状の関係を例示する説明図である。
【図１１】候補形状と地物形状の他の関係を例示する説明図である。
【図１２】内角の大きさによる制限について説明する説明図である。
【図１３】二つの四角形から新たな候補形状を生成する様子を示す説明図である。
【符号の説明】
【００５１】
１０…地物形状簡略化装置
２１…ＣＰＵ
２２…ＲＡＭ
２３…ＲＯＭ
２５…キーボード
２７…ディスプレイ
３０…ハードディスク
【技術分野】
【０００１】
本発明は、頂点数Ｎ（Ｎは５以上の自然数）の多角形として表現された建物や土地などの地物の形状を、頂点数Ｍ（Ｍは３以上、Ｎ未満の自然数）の図形に変換する技術に関するものである。
【背景技術】
【０００２】
近年、地図情報はデジタル化されて、自動車のナビゲーションシステムなどに活用されている。こうした地図情報の一つとして、建物の形状がある。いわゆる住宅地図などでは、その場所に存在する建物の平面形状などを再現し、地図の利便性を高めているのである。建物の平面形状は、建築図面に基づいて入力することも可能であるが、多数の建物について、その形状を入力する手間を軽減するために、例えば航空写真を利用し、図形認識などの手法を用いて建物の平面形状を表わすポリゴン（多角形形状）を生成することが行なわれている。
【０００３】
こうして生成されたポリゴンは、実際の建物の平面形状（投影図における投影図形状）に基づいているため、建物が複雑な形状をしていれば、当然認識した形状も複雑なものとなり、頂点の数が１０以上になることも珍しくない。地図情報としてこうした地物形状を扱う場合には、地図情報として許容されるデータの大きさの制限もあり、またあまりに複雑な形状は地図としての使用上は意味をなさない場合もあり、地物形状としての適切な複雑さ（換言すれば、適切な簡略さ）が求められる。そこで、従来から、複雑な形状のポリゴンを簡略化する技術が提案されていた（下記特許文献１、２参照）。
【０００４】
【特許文献１】特開２００３−１４１５５４号公報
【特許文献２】特開２００３−１７８２９９号公報
【０００５】
しかしながら、従来の簡略化の技術では、個々の辺について所定の条件に合致するか否かといった判断を繰り返すため、処理に時間がかかるうえ、その割りに頂点数の大幅な削減を実現することができなかった。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、複雑な地物形状の大幅な簡略化が困難であるという課題を解決するものであり、短時間のうちに建物の形状の簡略化を実現することを目的とする。
【課題を解決するための手段】
【０００７】
かかる目的を実現する本発明の地物形状簡略化装置は、
頂点数Ｎ（Ｎは５以上の自然数）の多角形として表現された地物形状を、頂点数Ｍ（Ｍは３以上、Ｎ未満の自然数）の図形に変換する地物形状簡略化装置であって、
前記地物形状を構成する連続したＮ個の辺の情報を入力する辺情報入力手段と、
該情報を入力したＮ個の辺を、該辺の起点から終点に向かう方向を基準としてＭ種類に分類する辺分類手段と、
該分類された辺から、該分類毎に一つの辺を抽出する辺抽出手段と、
該抽出された辺もしくは該辺を延長した辺とにより、頂点が少なくとも３個以上の多角形を、候補形状として構成する候補形状形成手段と、
該形成された候補形状と前記地物形状とを比較して評価値を求める評価値演算手段と、
該評価値に基づいて、前記地物形状を簡略化した簡略化形状を求める簡略化形状決定手段と
を備えたこと
を要旨としている。
【０００８】
また、この地物形状簡略化装置に対応した簡略化方法は、
頂点数Ｎ（Ｎは５以上の自然数）の多角形として表現された地物形状を、頂点数Ｍ（Ｍは３以上、Ｎ未満の自然数）の図形に変換する方法であって、
前記地物形状を構成する連続したＮ個の辺の情報を入力し、
該情報を入力したＮ個の辺を、該辺の起点から終点に向かう方向を基準としてＭ種類に分類し、
該分類された辺から、該分類毎に一つの辺を抽出し、
該抽出された辺もしくは該辺を延長した辺とにより、頂点が少なくとも３個以上の多角形を、候補形状として構成し、
該形成された候補形状と前記地物形状とを比較して評価値を求め、
該評価値に基づいて、前記地物形状を簡略化した簡略化形状を求めること
を要旨としている。
【０００９】
かかる地物形状簡略化装置またはその方法によれば、頂点数Ｎの多角形として表現された地物形状を、頂点数Ｍの図形に変換することができる（３≦Ｍ＜Ｎ）。この装置または方法によれは、情報を入力したＮ個の辺を、該辺の起点から終点に向かう方向を基準としてＭ種類に分類し、分類された辺から、分類毎に一つの辺を抽出し、抽出された辺もしくは該辺を延長した辺とにより、頂点が少なくとも３個以上の多角形を、候補形状として構成する。その上で、形成された候補形状と地物形状とを比較して評価値を求め、評価値に基づいて、地物形状を簡略化した簡略化形状を求める。従って、簡略な構成で、地物形状の簡略化を実現することができる。辺の起点から終点に向かう方向は、辺がベクトルとして定義されている場合は、その情報をそのまま用いればよく、辺が単に両端の座標により定義されているに過ぎない場合には、そのいずれか一方を起点とし、他方を終点として定義すればよい。この時、一つの辺についていずれか一方が終点とされれば、これに接続された他の辺において、その接続された端点が起点となり、他方が終点となる。地物形状を構成する複数の辺は、順次接続されて閉空間を構成しているから、一つの辺について起点と終点を定めれば、他の辺の起点と終点は、一意に定めることができる。
【００１０】
辺の分類は、辺の起点から終点に向かう方向が、全方向をＭ個に分割したいずれの範囲に属するかにより行なうことができる。面積を有する形状としては三角形が最も辺の数が少ないので、全方向、即ち角度では３６０度（２π）を３分割した１２０度ずつの範囲に属することで、総ての辺を三種類に分類するのが最も簡易な構成である。地物形状は四角形を基準とすることが多いことに鑑み、全方向を４個に分割したいずれの範囲に属するかにより行なっても良い。もとより、Ｍ＝３から順次ＭをＮ−１まで増加させ、総ての場合を尽くすことも差し支えない。この場合、総ての場合を尽くして、評価の最も高いものを地物形状の簡略化形状として求めることにしても良いし、順次評価をして所定以上の評価となる簡略化形状が得られたら、そこで処理を打ち切り、辺の分類以下の処理を終了するものとしても良い。
【００１１】
全方向をいくつかに分割する際には、予め定めた特定の方向（例えば東方向に相当する角度）を基準として、そこからＭ個に分割するものとしても良いし、分類しようとする辺の中で最も長い辺を見出し、その辺の方向を基準として、Ｍ個に分割するものとしても良い。一般に、地物は、日照を考慮して形作られる場合が多いので、東などの特定の方向を基準とすることは、辺の分類において意味を持っている。また、地物を構成する辺のうち最も長い辺が、その地物の基本的な形状の方向性を示している場合が多いので、最も長い辺を基準にして全方向をＭ個に分割することは、地物形状を簡略化するための辺の分類として有効である。なお、最も長い辺の方向を０度として、０ないし３６０／Ｍ度を最初の範囲としても良いが、辺が有する方向の情報に誤差を有することを考慮し、最も長い辺の方向を１８０／Ｍ度とし、０ないし３６０／Ｍ度を最初の範囲とすることも現実的である。もとより、現実的な分割数Ｍが１０程度以下であることに鑑み、最も長い辺を１０ないし１５度程度の予め定めた角度とみなして、全方向をＭ個に分割することも差し支えない。
【００１２】
Ｍ種類に分類された辺のうちから、候補形状を形成するための辺の抽出は、種々の手法が想定されるが、例えば辺の長さに着目して抽出するものとすることができる。この場合、長い辺から順に抽出するものとすれば、少ない辺で元の地物形状に近い形状を候補形状とする可能性を高くすることができる。あるいは一つの分類から一つの辺を抽出した時、他の分類からは、先に抽出された辺と特定の関係、例えばなるべく直交に近い関係にある辺を選択すると言った対応も可能である。
【００１３】
この他、例えば、Ｍ種類に分類された各々の分類に属する辺のうち、絶対値が所定値より大きく、且つ地物形状の周囲長に対して所定の割合より大きな割合を有する辺を抽出の対象とすることも、元の地物形状に近似の形状を候補形状とする上で有効である。
【００１４】
抽出された辺を用いて候補形状を形成する場合、抽出された辺を延長した辺を用いる際には、元の地物形状からはみ出さない形状のみを、候補形状として構成することも実際的である。地物形状は、本来隣接する他の地物形状と重なることのないものであり、はみ出さない形状のみを候補形状とすれば、こうした地物形状の持つ特性を保持できるからである。もとより、一定の割合までは、はみ出しを許容したり、隣接する建物についての簡略化済みの形状との関係で、はみ出しを許容するといった対応も可能である。
【００１５】
抽出された辺により候補形状を構成する際、隣接する２辺が候補形状の内側に形成する総ての角度が、少なくとも２７０度（１．５π）以上の所定の角度より小さい形状のみを、候補形状として構成することも可能である。四角形以上の形状では、その形状の内側に向けて凸の角を形成することが一般に可能である。しかし、通常の地物形状としては、内側に凸の角の内角２７０度以上のものは、特殊な形状として、そのような角を有する形状を候補形状としないことが、処理を簡略化する上で有用である場合が存在する。なお、この角度は、２７０度以上の所定の角度として設定可能であり、２８０度、２９０度など、実際の処理に応じて、予め設定すればよい。
【００１６】
こうして得られた候補形状についての評価は、地物形状と候補形状の各面積および両形状の重なりに基づく面積を用いて評価値を演算することにより行なっても良い。こうした評価値を用いた評価には種々の手法を考えることができる。例えば、両形状の重なりに基づく面積として、両形状の重なった部分の面積および地物形状に対して前記候補形状が重ならない部分の面積のうち、少なくとも一方の面積を求め、この面積の地物形状の面積に対する割合を用いて評価値を求める、といった構成を採用することも差し支えない。こうした評価値の演算は、どのような候補形状を、元の地物形状を簡略化した形状として望ましいと考えるか、という観点から種々の手法を予め決めておくことができる。なお、上記の例で、地物形状の面積に対する割合を求めているのは、いわゆる正規化の処理に相当する。こうしておけば、大きな形状でも小さな形状でも同じ手法で評価することができる。
【００１７】
こうした地物形状の簡略化において、入力した辺情報に基づいて簡略化形状を求める過程で、頂点数Ｎの地物形状を簡略化することを中止すべき所定の条件が成立していることを判断し、簡略化の処理を中止することが考えられる。現実の地物形状の簡略化は、総ての場合に可能であるとは限らず、無用な探索の処理を行なわずに、所定の条件により中止した方が、トータルでは望ましい場合も存在するからである。中止条件が成立していると判断した場合には、地物形状を記述するために用意されたフォーマットで記述された地物形状の辺の情報をそのまま出力するものとすればよい。他方、簡略化情報が決定された場合には、簡略化情報を、地物形状が記述されたフォーマットと同一のフォーマットで出力すればよい。もとより、出力するデータに、中止されたか否かのフラグを付与しても良い。
【００１８】
簡略化の処理を中止する所定の条件としては、入力した総ての辺の長さが所定の判定値以下である場合や、入力した辺情報から、外形形状が曲線の地物形状を短い直線で近似した辺が存在する場合など、あるいは入力した辺情報に基づいて簡略化形状を求める過程で、予め設定した条件を満足する候補形状が一つも得られなかった場合などを考えることができる。
【００１９】
本発明において、候補形状として複数の形状が求められた場合であって、そのうちのいずれの候補形状も、評価値が、予め定めた閾値を超えていない場合には、複数の形状のうち所定の条件を満たす２個以上の形状を合成した形状を新たな候補形状として評価値を求め、評価値が所定の合成条件を満たす場合には、合成した候補形状を、簡略化形状として求めるものとして良い。複雑な形状の建物の場合、単一の候補形状では簡略化できない場合もあり得るからである。
【００２０】
もとよりこうした合成の対象となる候補形状はいくつもあり得るから、合成を行なう２個以上の形状が満たす所定の条件としては、各形状の面積が、地物形状の面積に対して、所定の割合以上であるという条件を設けておくことができる。あるいは、２個の形状が重なっていることや、記合成後の候補形状における隣接する２辺が該候補形状の内側に形成する総ての角度が、少なくとも２７０度以上の所定の角度より小さいことといった条件を設けておくことも差し支えない。複数個の形状の合成を許すと、多数の辺を有する地物形状の簡略化は、極めて複雑なものとなることが考えられる。そこで、通常の地物の形状に基づき、２個の形状を合成するという条件に限ることも差し支えない。「Ｌ」形状の地物などは、大部分２個の形状の合成により、簡略化した形状を見出すことができるからである。もとより、「コ」の字形状の地物も存在するから、合成する形状を３個まで、あるいはそれ以上とすることも差し支えない。
【００２１】
なお、本発明は、こうした地物形状簡略化装置やその方法として把握されるだけでなく、簡略化方法をコンピュータにより実現するプログラムの発明や、そのプログラムを記録した家禄媒体としての発明等として把握することも可能である。
【発明を実施するための最良の形態】
【００２２】
本発明の一実施例としての地物形状簡略化装置とその方法について、以下実施例を挙げて説明する。図１は、実施例としての地物形状簡略装置１０の概略構成図である。この装置１０は、演算処理を行なうＣＰＵ２１、処理用のワークエリアなどに用いられるＲＡＭ２２、モニタプログラムなどを記憶するＲＯＭ２３、使用者の指示を入力するマウス付きのキーボード２５、処理中の地物形状などを表示するディスプレイ２７、地物形状データベースＢＤＢなどを記憶するハードディスク３０等を備えている。この実施例では、簡略化の処理の対象となる地物形状は、予め建物を構成する複数の線分の集合として定義されており、データベースを構成している。
【００２３】
図２に、地物形状データベースＢＤＢのデータ構造の一例を示す。図示するように、この例では、地物形状データベースＢＤＢには、大きくは、「要素種別」「中抜き面数」「外枠面情報」が記憶されている。要素種別は、このデータベースＢＤＢが、更に上位の地図データベースの一部を構成していることから、地図データベースＧＤＢにおいて、どのような要素に該当するかを示す情報である。本実施例では、要素種別は、地図データベースＧＤＢ中では、面や中抜きの情報であることを示す値を持っている。中抜き面数は、一つの地物形状に、中抜きの部分がある場合に、その中抜きの部分の数を示す情報である。このデータベースＢＤＢでは、中抜きはないとして扱うので、総ての地物形状において、中抜き面数は、値０となっている。
【００２４】
外枠面情報は、地物形状を示す外枠を構成するｎ点の座標のデータからなっている。外枠面情報は、外枠面座標点数の情報とここで定義された数ｎだけの座標のデータとから構成されている。図３は、地物形状データベースＢＤＢに登録された一つの建物についての外枠面情報との対応関係を示す説明図である。図示するように、この地物形状は、１７の辺から構成されており、各辺は総て連結点で連結されている。この連結点ＣＰを、連結点ＣＰ１から連結点ＣＰｎまで、そのｘ座標およびｙ座標の組み（ｘ１，ｙ１）・・・（ｘｎ，ｙｎ）で表わしたものが、地物形状データベースＢＤＢの「外枠面情報」である。この例ではｎ＝１７であり、全部で１７の連結点ＣＰ１ないしＣＰ１７の座標データを記録している。この例では、連結点ＣＰの座標を記述しているが、連結点ＣＰ１と連結点ＣＰｎとは、異なる点であり、連結点ＣＰｎの次が連結点ＣＰ１であるとして扱うものとして、総ての連続する連結点間には、辺が存在することになる。従って、このデータベースＢＤＢは、連結点ＣＰの座標を記憶しているが、本質的には、地物形状を構成する辺を定義しているのである。建物毎に形状は異なるので、連結点の数も異なるから、このデータベースＢＤＢは、いわゆる可変長のデータベースである。
【００２５】
ＣＰＵ２１は、後述する簡略化プログラムを、ハードディスク３０から主記憶を構成するＲＡＭ２２に一旦ロードし、主記憶上のプログラムを実行することにより、この地物形状の簡略化を行なう。図３に示した例では、簡略化された後の形状は例えば図４に示すように、連結点が６個の形状となっている。なお、簡略化後の連結点は、必ずしも元の地物形状が備えていた連結点と一致するとは限らないから、図４では、簡略化後の連結点をＶＰで表わすものとしている。この場合の簡略化形状も、図２に示したデータベースと同様のフォーマットで定義している。簡略化された地物形状のデータベースを、簡略化地物形状データベースＳＤＢと呼ぶ。この簡略化地物形状データベースＳＤＢも、地物形状データベースＢＤＢと同様ハードディスク３０に記憶される。なお、詳しくは後述するが、簡略ができない場合も当然にあり得、この場合には、簡略化されていない元のデータ（図２参照）がそのまま簡略化地物形状データベースＳＤＢに保存される。
【００２６】
次に、地物形状簡略化装置１０が実行する処理について説明する。図５は、この装置１０が実行する処理を示すフローチャートである。簡略化装置１０は、地物形状データベースＢＤＢが準備され、キーボード２５を介して簡略化処理の開始を指示されると、まず地物形状データベースＢＤＢにアクセスして、データベースＢＤＢから、最初の地物形状データを読み出す処理を行なう（ステップＳ１００）。要するに、ハードディスク３０から、図２に示した一つの建物に相当するデータを読み出すのである。続いて、簡略化の閾値ＴＳを読み出す処理を行なう（ステップＳ１１０）。この閾値ＴＳは、元の地物形状を簡略化する際のいわば評価を行なうための閾値である。詳しく後述するが、所定の条件で得られた候補形状が、簡略化されたものとしてみなして良いか否かの判断基準を与えるものである。
【００２７】
こうした閾値ＴＳは、総ての地物形状に対して一律に同じ値としても良いが、地物形状が有する特性により変更するものとしても良い。例えば、地物形状の複雑さ、つまり通常は連結点ＣＰの数の多寡に応じて変更するものとしても良い。形状が複雑になれば、閾値をある程度下げてやらないと、簡略化ができたと判断することが困難になる場合が想定されるからである。もとより、地物形状の複雑さではなく、地物形状の大きさ（占有面積）や隣接する建物との距離や建物の種別（目標物なのか個人家屋なのか等の種別）などにより、閾値ＴＳを変更するものとしてもよい。実施例では、図６に示すように、着目した地物形状の面積ＳＳに応じて、下限値ＴＳｌから上限値ＴＳｕの間の値を取るものとしている。即ち、実施例においては、閾値ＴＳは、地物形状の面積ＳＳが下限ＳＬ以下であれば値ＴＳｌに等しく、地物形状の面積ＳＳが上限ＳＵ以上であれば値ＴＳｕに等しく、地物形状の面積ＳＳが下限ＳＬから上限ＳＵまでの間に入っている場合には、下限値ＴＳｌと上限値ＴＳｕとの間を線形補間した値として定義されている。もとより、線形補間などの処理に代えて、閾値ＴＳをテーブルの形で保持し、地物形状データベースＢＤＢ内から一つの地物形状のデータを読み出したとき（ステップＳ１００）、その面積を計算し、テーブルを参照して閾値ＴＳを読み込むものとしても良い。
【００２８】
こうして地物形状データベースＢＤＢから一つの建物のデータを取得し（ステップＳ１００）、その地物形状の簡略化のための閾値ＴＳを読み込んだ後（ステップＳ１１０）、次に簡略化が可能か否かの判断を行なう（ステップＳ１２０）。簡略化が可能な否かの判断については、詳しくは図７を用いて後述するが、総ての地物形状について簡略化が可能な訳ではないからである。ステップＳ１２０において、簡略化が可能でないと判断された場合は、ステップＳ１２５に移行し、地物形状データベースＢＤＢから取得したデータ（図２参照）を、そのまま簡略化後の簡略化地物形状データベースＳＤＢとして出力する処理を行なう。このように簡略化の処理ができない場合でも、データベースＳＤＢにデータを書き出しておくのは、本実施例では、地図を描画するために、簡略化できない地物形状も含めて総ての建物についてのデータを揃えておくためである。単に地物形状の簡略化だけを目的としている場合には、簡略化されなかった地物形状については、データを出力しない構成とすることも差し支えない。
【００２９】
簡略化可能か否かの判断の内容について、図７に依拠して説明する。図７は、簡略化の判断処理ルーチン（ステップＳ１２０）の詳細を示すフローチャートである。図示するように、この処理が開始されると、まず、地物形状データベースＢＤＢから取得した一つの建物のデータに基づき、この地物形状を構成している各辺のＸ方向長さおよびＹ方向長さが、総て所定値Ｌ１より小さいか否かの判断を行なうのである（ステップＳ１２１）。ｉ番目の連結点ＣＰi と次の連結点ＣＰi+1 間に存在する辺のＸ方向、Ｙ方向の長さＬｘｉ，Ｌｙｉは、
Ｌｘｉ＝｜ｘi+1 −ｘi ｜
Ｌｙｉ＝｜ｙi+1 −ｙi ｜
として簡易に求めることができる。そこで、これらの辺の長さＬｘｉ，Ｌｙｉが総て所定値Ｌ１以下であれば、地物形状が小さな微小建物であるとして、簡略化の処理を行なわないと判断するのである。
【００３０】
地物形状を表わす各辺に、長さＬ１以上のものがあると判断されれば（ステップＳ１２１）、続いて、着目している地物形状の一部に曲線図形が含まれるか否かの判断を行なう（ステップＳ１２２）。本実施例では、円形のホールなど、外形形状の少なくとも一部に曲線形状が含まれる場合、これを短い直線の連続として記述している。従って、所定値Ｌ２以下のショートベクトルが、所定値Ｎ１以上連続している場合には、これを曲線形状を近似していると判断し、簡略化の処理の対象から外すという判断を行なうのである。本実施例では、簡略化は、直線近似に拠っているので、もともと曲線形状の図形の簡略化は行なわないとしているのである。なお、実施例では、実際の長さ２５センチを１単位として、Ｌ１は４０単位分として設定した。同様に、実施例では、Ｌ２は１０単位分（２．５メートル相当）でＮ１＝１０として、曲線図形の判断を行なった。もとより、曲線図形を簡略化の処理から排除せず、他の図形と同じように簡略化の処理の対象とすることも差し支えない。
【００３１】
上記ステップＳ１２１，Ｓ１２２の判断により、候補形状の生成ができないと判断した場合には、「１」に抜けて、本ルーチンを一旦終了する。「１」は、図５に示した処理の連結箇所であり、この場合には、上述したステップＳ１２５に処理は移行し、候補形状は生成できないとして、元の地物形状のデータのコピーを行なうのである。他方、ステップＳ１２１，Ｓ１２２で、簡略化の処理が可能と判断された場合には、「ＮＥＸＴ」に抜けて、本処理ルーチンを終了し、図５の処理に戻る。
【００３２】
簡略化の処理が可能と判断した場合には、次に、地物形状データベースＢＤＢから取得したデータに含まれる総ての辺を、４つに分類する処理を行なう（ステップＳ１３０）。４つ分類するとは、本実施例では、各辺を始点と終点を持つベクトルとみなし、そのベクトルの有する角度θが、４つの象限のいずれに属するかを判定する処理である。４つの象限は、本実施例では、最も長い辺を基準にして定めている。即ち、まず全ての辺を探索して最も長い辺を見出し、この辺の方向を角度０として、−０．２５π≦θ＜０．２５πを第１象限、０．２５π≦θ＜０．７５πを第２象限、０．７５π≦θ＜１．２５πを第３象限、１．２５π≦θ＜１．７５πを第４象限として定めている。その上で、各辺がこれら４つの象限のいずれに属するかにより分類する。図８に、辺Ｓ１ないしＳ８からなる地物形状の一例を示した。この例では、辺Ｓ５が最も長いので、この辺を基準にして分類を行なうと、図９に示した結果となる。
【００３３】
この実施例で４つに分類したのは、便宜的なものであり、５つに分類しても差し支えない。また、各分類は、辺の方向に基づいて行なっていれば足り、４つに分類する場合であっても、各角度範囲は必ずしも９０度ずつである必要はない。各分類の角度範囲は、一つ一つ予め定めておくものとしても良い。また、本実施例では、最も長い辺の方向を基準として、各象限の範囲を定めたが、所定の方向、例えば実際の地図上における東に相当する方向を角度０として、各象限を定めても良い。
【００３４】
こうして辺を４つに分類した後、候補形状が生成可能か否かの判断を行なう（ステップＳ１３５）。候補形状は、４つの分類の各々から一つの辺を取り出し、都合４つの辺を組み合わせることにより生成される。もとより、元の地物形状が５個以上の連結点ＣＰを有するものであれば、４つに分類された辺を一つずつ取り出しても各辺は必ずしも連結しない。そこで、候補形状の生成時には、各分類から取り出した４つの辺については、適宜延長することにより、候補形状を生成するものとしている。
【００３５】
図８に例示した地物形状に沿って、候補形状の生成について説明する。図８に示した地物形状は、８個の連結点ＣＰ１ないしＣＰ８を有することから、隣接する各連結点ＣＰを番号の小さい方から大きい方に向かって右周りに接続する８個の辺Ｓ１ないしＳ８から構成されている。各辺Ｓ１ないしＳ８を、ベクトルとみなしてその方向を上記の４つの角度範囲に分類する。なお、方向が分かりやすいように、図８では、各辺は、終点側に矢印を有するベクトルとして示した。分類した結果は、図９に示されている。図９において、第１象限ないし第４象限の４つに分類された各辺については、更に長さが長いものを上位にして分類してある。即ち、全ての辺の中で最も長い辺であるＳ５が属するのが第１象限となり、第２象限には辺Ｓ４、Ｓ２が属し、この順に上位の辺Ｓ４が長く、第３象限には辺Ｓ１、Ｓ３、Ｓ７が属し、この順に上位の辺Ｓ１が最も長く、第４象限には辺Ｓ８、Ｓ６が属し、この順に上位の辺Ｓ８が長くなっている。そこで、各象限に分類された辺のうち、長いものから順次取り出し、それらの組み合わせて、候補形状を生成するのである。生成される候補形状の例を図１０および図１１に示した。各図において、元の地物形状を破線で、選択した辺を実線で、各辺をその交点まで延長した部分を一点鎖線で、それぞれ示した。図１０では、各分類において最も長い辺Ｓ１、Ｓ４、Ｓ５、Ｓ８の組み合わせとして、候補形状ＳＳ９が生成されている。また図１１では、基本的には、図１０と同様、各分類から、長い辺を取り出して候補形状を生成しているが、この例では、第３象限に属する辺についてのみ、二つの辺Ｓ２、Ｓ４から、２番目に長い辺Ｓ２を用いて候補形状ＳＳ１０を生成している。両者を比較すると、候補形状ＳＳ９では、図示の領域ＢＢ９が、元の地物形状から見るとはみ出した領域となっているのに対して、候補形状ＳＳ１０では、こうしたはみ出した領域が存在しない。
【００３６】
図８ないし図１１は、候補形状が生成できた場合を示しているが、形状によっては、候補形状として扱えない形状しか構成できない場合が存在する。そこで、その条件として、本実施例では、次の条件を定めている。即ち、
（１）各分類から取り出した各辺Ｓの長さをＬＬとしたとき、
（１−１）ＬＬ＞Ｌ３であること、
（１−２）ＬＬ／ＬＡ＞Ｔ４であること
（ここで、ＬＡは、地物形状の周囲長である）、
（２）候補形状における各内角αは、α≦（２π−Ｔ５）であること、
という条件を満足する場合にのみ、候補形状が生成可能と判断するのである。なお、実施例では、Ｔ５＝０．５［rad ］としたが、この大きさは出力する地図の大きさなどによっても影響を受ける。
【００３７】
上記条件（１−１）は、絶対値があまりに短い辺を無理に拡長して候補形状を生成させないためであり、条件（１−２）は、絶対値としては所定の長さＬ３以上ある辺でも、元の地物形状が大きい場合、相対的に小さな辺を拡張して候補形状を生成させないためであり、条件（２）は、図１２に示すように、内側にあまりに深く切れ込んだ形状を候補形状としないための条件である。辺を４つに分類して組み合わせる場合には、通常この条件（２）により除外される候補形状は少ないが、分類を５つ以上にした場合などには生じる可能性がある。
【００３８】
分類した総ての辺の組み合わせを試しても、上記の条件の総てを満足する形状が得られない場合には、候補形状は生成不可能として（ステップＳ１３５）、ステップＳ１２５に移行し、上述した地物形状のデータをコピーする処理を行なう。他方、総ての辺の組み合わせを試してみたとき、上記の（１−１）（１−２）（２）の総ての条件が満たされる形状が見出された場合には、候補形状は生成可能であると判断し、次に、候補形状を生成する処理を行なう（ステップＳ１４０）。候補形状は、既に図８ないし図１１を用いて例示したように、複数生成可能なことが多い。本実施例では、上記の条件を満たして生成できる総ての形状を、候補形状として生成するのである。
【００３９】
候補形状を生成した後、次に各候補形状についてのスコアＳＣを計算する処理を行なう（ステップＳ１４５）。スコアＳＣは、本実施例では、元々の地物形状の面積をＡ、候補形状の面積をＢとして、次式（１）により計算する。
ＳＣ＝（ＡＢ−λ・ＢＢ）／Ａ …（１）
ここで、ＡＢは地物形状と候補形状の積面積、ＢＢは、ＢＢ＝Ｂ−ＡＢ、つまり候補形状が、地物形状との重なりの形状からはみ出している面積である。また、λは、そのはみ出し量に対する重み付け係数（ペナルティ）である。
【００４０】
上記式（１）において、ＡＡを、ＡＡ＝Ａ−ＡＢ、つまり元々の地物形状が、候補形状との重なりの形状からはみ出している面積として定義すると、
ＳＣ＝（Ａ−ＡＡ−λＢＢ）／Ａ
と変形できるから、スコアＳＣは、結局、着目した候補形状が、地物形状に対して過小である面積ＡＡと、過大である面積ＢＢとを、共に評価していることになる。従って、λ＝１とすれば、過小な部分と過大な部分とに等しい重み付けがなされていることになり、λ＝０とすれば、過大な部分があっても許容することになり、λ＝∞とすれば、はみ出しを一切許容しないことになる。本実施例では、隣接した建物を簡略化した後の簡略化形状が互いに重ならないことを優先して、λ＝１００に設定してある。なお、全体Ａで除しているのは、スコアＳＣを地物形状の大小に拠らない値とする（正規化する）ためである。
【００４１】
スコアＳＣを計算した後、次に、ステップＳ１４０で生成した候補形状スコアＳＣが、先に読み込んだ（ステップＳ１１０）閾値ＴＳより大きいか否かの判断を行なう（ステップＳ１５０）。候補形状が複数生成されている場合には、総ての候補形状について判定するのである。ここで、スコアＳＣが、閾値ＴＳを上回る候補形状が存在すれば、閾値ＴＳを越えるスコアＳＣを有する候補形状の中から、最もスコアの高い候補形状を簡略化形状として出力する処理を行なう（ステップＳ１６０）。出力の形式は、ステップＳ１２５で説明したように、地物形状のものと同じフォーマットである。その後、地物形状データベースＢＤＢに保存されている全ての建物について簡略化の処理を完了したかを判別し（ステップＳ１７０）、完了していなければ、ステップＳ１００に戻って、地物形状データベースＢＤＢからデータを取得する処理以下を繰り返す。
【００４２】
スコアＳＣを計算した後（ステップＳ１５０）、閾値ＴＳを上回るスコアＳＣを有する候補形状が見いだせなかった場合には（ステップＳ１５０）、次に和集合を生成する処理を実行する（ステップＳ１７０）。和集合の生成は、次のように行なう。ステップＳ１４０で生成した候補形状（いずれも四角形）のうち、面積が大きい順にＮ２個を取り出し、且つその面積Ｂの地物形状の面積Ａに対する比（Ｂ／Ａ）が、所定値Ｔ２を越えているものを対象に、２つの四角形同士の和集合を生成して、これを新たな候補形状とするのである。図８に示した例では、図１３に示すように、辺Ｓ１−Ｓ２−Ｓ５−Ｓ８により形成した四角形ｄＳ１、辺Ｓ２−Ｓ３−Ｓ４−Ｓ５により形成した四角形ｄＳ２との和集合ＳＳｏｒが、新たな候補形状となるのである。なお、二つの四角形に重なりの部分を生じないものについては、簡略化候補とはしないものとした。同様に、重なりがあっても、いずれか一つの内角αが、α≦（２π−Ｔ５）となってしまう組み合わせについても除外するものとした。更に、二つの四角形を組み合わせた形状が元の地物形状より複雑な形状となる場合も除いている。
【００４３】
その後、和集合が一つでも生成できたかを判断し（ステップＳ１８０）、一つも生成できなければ、簡略化の処理をできないとして、上述したステップＳ１２５に移行して元のデータをそのまま出力し、着目した地物形状についての簡略化の全処理を終了する。他方、一つでも和集合が生成できた場合には（ステップＳ１８０）、ステップＳ１４５に戻って、その和集合の形状についてのスコアＳＣの計算から、上述した処理を繰り返す（ステップＳ１４５ないしＳ１６０）。和集合の形状について、スコアＳＣが閾値ＴＳより高いものが存在すれば、そのうちの最上位のスコアの和集合を、簡略化形状として出力する処理を行なう（ステップＳ１６０）。いずれの場合もこれで着目した地物形状については簡略化の処理が終了したことになるので、地物形状データベースＢＤＢ内の全ての地物形状についての簡略化の処理が完了したかを判別し（ステップＳ１７０）、完了するまで、上記の処理を継続する。
【００４４】
以上説明した本実施例によれば、多数の複雑な地物形状を、簡略な処理により、四角形またはその二つの和集合の形状に簡略化することができる。従来、地図上に存在する地物形状などの多数の、しかも複雑な形状を、高速に処理して簡略することは極めて困難であった。カーナビゲーションなどに用いられる地図の元になっている詳細な地図（地物形状なども実際に即した形状で入力されている住宅地図など）から、ナビゲーションシステム用の地図を生成する場合など、何千万という数の地物形状を簡略する必要がある場合もあり、こうした処理を高速に行なう簡略化装置および簡略化方法は、極めて有用である。また、本実施例では、簡略化できないものについては無理な簡略化を行なわず、入力した地物形状のデータをそのまま出力しているので、そのまま地図などの描画に用いることができる。全ての地物形状が簡略化されていなくても、大部分の地物形状が簡略化されれば、トータルのデータ容量を低減することができるので、例えば地物形状のデータを容量の限られたＤＶＤなどに収録する際に便利である。また、簡略化されていない形状は、連結点の数を見れば容易に判別できるので、それらのデータのみを抽出し、時間はかかるが例外的な形状でも簡略化する他の簡略化方法を採用して、簡略化の処理を行なうものとしても良い。この場合、多数の地物形状は本実施例の手法で簡略化を済ませているので、例え他の手法が、簡略化の処理に時間を要するものであっても、トータルの時間をさほど長くしないで済ませることができる。
【００４５】
また、本実施例では、簡略化を評価する閾値ＴＳを、地物形状の面積ＳＳにより図６に示したように変化させている。従って、面積が大きくなるに従って、地物形状と近似の候補形状しか出力しなくなるのである。形状が大きくなれば、一致の割合が等しくなっても、はみ出したり不足していたりする面積それ自体は大きくなる。このため、地物形状の面積ＳＳが大きくなるほど、一致率の高いもののみを簡略化形状として出力することになる。この場合、面積の大きな地物形状ほど、簡略化されにくいことになるが、現実には、大きな地物形状ほど、これを構成する辺の数も多く、様々な候補形状を作り得ること、大きな地物形状ほど、地物形状データベースＢＤＢ内での占める割合は相対的に小さくなるから、そのままデータを出力しても全体としてのデータ量の増大はさほど大きなものとならないことなどから、簡略化によりデータ全体の容量の低減の効果は享受することができる。
【００４６】
また、本実施例では、スコアＳＣを計算するとき、係数λを用いて、はみ出し部分についての評価の割合を容易に変更できるようにしている。従って、対象となる地物形状の性質に応じて、はみ出しを許さないという条件（λ＝∞）から、はみ出しを重なっていない部分と同程度に評価する条件（λ＝１）、更には、はみ出しにスコア上のペナルティを与えない条件（λ＝０）まで、簡易に設定することができる。
【００４７】
更に、本実施例では、単一の四角形では十分な簡略化が達成できない場合には、所定の条件を満たした候補形状の和集合を求めて新たな候補形状とすることができる。この場合でも、評価の手法は変える必要がなく、また和集合の元になる四角形の候補形状は先に抽出しているので、その取り扱いは容易である。建物は、四角形の組み合わせで実現されることが多いので、四角形かその和集合で簡略化すると、元の形状の特徴を残し易いという利点が得られる。同様の理由から、和集合を求めて再度評価する手法は、簡便なものでありながら、効果は大きい。なお、本実施例では、最初に求める候補形状は、四角形としたが、五角形や六角形まで許容するものとしても良い。また、和集合は二つに限るものではなく、三つあるいはそれ以上の和集合を許容するものとして簡略化の処理を行なっても良い。
【００４８】
以上説明した本実施例では、簡略化の処理は、専用の簡略化装置１０を用いて行ない、地物形状データベースＢＤＢから、表示や出力を行なうために、簡略化地物形状データベースＳＤＢを形成したが、図５、図７を用いて説明した簡略化のアルゴリズムを表示や出力を行なう装置に組み込んでおき、必要に応じてその場で簡略化の処理を施すものとしてもよい。カーナビゲーションシステムや携帯電話の画面に地図を表示するような場合には、一度に表示に供される地物形状の数はさほど多くないので、必要な地物形状だけ簡略化して表示などを行なうものとすることも可能である。例えば、ネットワークを介して接続された携帯電話などの端末装置に地図を表示する場合、地図データそのものはサーバ側に用意される。しかも端末装置側での表示の倍率は様々なので、倍率によっては、サーバに蓄積した地物形状データベースＢＤＢのデータをそのまま使って建物を表示したい場合も存在する。また縮尺を小さくして、建物の形状を簡略化しつつ表示したい場合も存在する。後者の場合に、縮尺に応じて、閾値ＴＳを調整しつつ、表示しようとする領域に含まれる地物形状のみ簡略化処理を行なうものとすることができる。この場合の簡略化の処理は、サーバ側で行なっても良いし、端末装置側で行なっても良い。
【００４９】
以上本発明の一実施例について説明したが、本発明は、こうした実施例に何ら限定されるものではなく、本発明の要旨を変更しない範囲内において、種々なる態様で実施できることは勿論である。
【図面の簡単な説明】
【００５０】
【図１】本発明の一実施例としての簡略化装置１０の概略構成図である。
【図２】簡略化装置１０における地物形状データベースＢＤＢのデータ構造を説明する説明図である。
【図３】簡略化の対象となる地物形状の一つを例示した説明図である。
【図４】簡略化された後の簡略化形状を例示する説明図である。
【図５】本実施例における簡略化処理ルーチンを示すフローチャートである。
【図６】閾値ＴＳの設定手法を示すグラフである。
【図７】簡略化の判断処理ルーチンの一部を示すフローチャートである。
【図８】４つに分類された辺に基づいて候補形状を生成する様子を示す説明図である。
【図９】各辺Ｓ１ないしＳ８の分類の様子を示す説明図である。
【図１０】候補形状と地物形状の関係を例示する説明図である。
【図１１】候補形状と地物形状の他の関係を例示する説明図である。
【図１２】内角の大きさによる制限について説明する説明図である。
【図１３】二つの四角形から新たな候補形状を生成する様子を示す説明図である。
【符号の説明】
【００５１】
１０…地物形状簡略化装置
２１…ＣＰＵ
２２…ＲＡＭ
２３…ＲＯＭ
２５…キーボード
２７…ディスプレイ
３０…ハードディスク
【特許請求の範囲】
【請求項１】
頂点数Ｎ（Ｎは５以上の自然数）の多角形として表現された地物形状を、頂点数Ｍ（Ｍは３以上、Ｎ未満の自然数）の図形に変換する地物形状簡略化装置であって、
前記地物形状を構成する連続したＮ個の辺の情報を入力する辺情報入力手段と、
該情報を入力したＮ個の辺を、該辺の起点から終点に向かう方向を基準としてＭ種類に分類する辺分類手段と、
該分類された辺から、該分類毎に一つの辺を抽出する辺抽出手段と、
該抽出された辺もしくは該辺を延長した辺とにより、頂点が少なくとも３個以上の多角形を、候補形状として構成する候補形状形成手段と、
該形成された候補形状と前記地物形状とを比較して評価値を求める評価値演算手段と、
該評価値に基づいて、前記地物形状を簡略化した簡略化形状を求める簡略化形状決定手段と
を備えた地物形状簡略化装置。
【請求項２】
前記辺分類手段は、前記辺の方向が、全方向をＭ個に分割したいずれの範囲に属するかにより分類する手段である請求項１記載の地物形状簡略化装置。
【請求項３】
前記全方向のＭ個の分割は、前記分類する辺のうち最も長い辺の方向を基準とし行なう請求項２記載の地物形状簡略化装置。
【請求項４】
前記辺抽出手段は、前記Ｍ種類に分類された各々の分類に属する辺のうち、長い辺から順に所定個数を抽出して、前記評価値演算手段により演算に供する請求項１記載の地物形状簡略化装置。
【請求項５】
前記辺抽出手段は、前記Ｍ種類に分類された各々の分類に属する辺のうち、絶対値が所定値より大きく、且つ前記地物形状の周囲長に対して所定の割合より大きな割合を有する辺を抽出の対象とする請求項１記載の地物形状簡略化装置。
【請求項６】
前記候補形状形成手段は、前記抽出された辺を延長した辺を用いる際、前記地物形状からはみ出さない形状のみを、前記候補形状として構成する請求項１記載の地物形状簡略化装置。
【請求項７】
前記候補形状形成手段は、前記辺により候補形状を構成する際、隣接する２辺が候補形状の内側に形成する総ての角の角度が、少なくとも２７０度以上の所定の角度より小さい形状のみを、前記候補形状として構成する請求項１記載の地物形状簡略化装置。
【請求項８】
前記評価値演算手段は、前記地物形状と前記候補形状の各面積および両形状の重なりに基づく面積を用いて評価値を演算する請求項１記載の地物形状簡略化装置。
【請求項９】
請求項８記載の地物形状簡略化装置であって、
前記評価値演算手段は、前記両形状の重なりに基づく面積として、両形状の重なった部分の面積および前記地物形状に対して前記候補形状が重ならない部分の面積のうち、少なくとも一方の面積を求め、該面積の前記地物形状の面積に対する割合を用いて前記評価値を求める地物形状簡略化装置。
【請求項１０】
請求項１記載の地物形状簡略化装置であって、
前記辺情報入力手段が入力した辺情報に基づいて前記簡略化形状を求める過程で、前記頂点数Ｎの地物形状を簡略化することを中止すべき所定の条件が成立していることを判断する中止条件判別手段を備え、
前記簡略化形状決定手段は、
前記簡略化情報が決定された場合には、該簡略化情報を、前記地物形状が記述されたフォーマットと同一のフォーマットで出力すると共に、
前記中止条件が成立していると判断した場合には、前記フォーマットで記述された地物形状の辺の情報をそのまま出力する
地物形状簡略化装置。
【請求項１１】
前記中止条件判別手段は、前記辺情報を入力した総ての辺の長さが所定の判定値以下である場合には、前記中止条件が成立していると判断する請求項１０記載の地物形状簡略化装置。
【請求項１２】
前記中止条件判別手段は、前記入力した辺情報から、外形形状が曲線の地物形状を短い直線で近似した辺が存在する場合には、前記中止条件が成立していると判断する請求項１０記載の地物形状簡略化装置。
【請求項１３】
前記中止条件判別手段は、前記入力した辺情報に基づいて前記簡略化形状を求める過程で、予め設定した条件を満足する候補形状が一つも得られなかった場合には、前記中止条件が成立していると判断する請求項１０記載の地物形状簡略化装置。
【請求項１４】
請求項１記載の地物形状簡略化装置であって、更に、
前記候補形状として複数の形状が求められた場合であって、そのうちのいずれの候補形状も前記評価値が、予め定めた閾値を超えていない場合には、該複数の形状のうち所定の条件を満たす２個以上の形状を合成した形状を新たな候補形状として前記評価値を求め、該評価値が所定の合成条件を満たす場合には、該合成した候補形状を、前記簡略化形状として求める手段を備えた
地物形状簡略化装置。
【請求項１５】
請求項１４記載の地物形状簡略化装置であって、
前記合成を行なう２個以上の形状が満たす所定の条件は、各形状の面積が、前記地物形状の面積に対して、所定の割合以上であるという条件を含む地物形状簡略化装置。
【請求項１６】
請求項１４記載の地物形状簡略化装置であって、
前記所定の合成条件は、
前記２個以上の形状が重なっていること、
前記合成後の候補形状における隣接する２辺が該候補形状の内側に形成する総ての角度が、少なくとも２７０度以上の所定の角度より小さいこと
である地物形状簡略化装置。
【請求項１７】
頂点数Ｎ（Ｎは５以上の自然数）の多角形として表現された地物形状を、頂点数Ｍ（Ｍは３以上、Ｎ未満の自然数）の図形に変換する方法であって、
前記地物形状を構成する連続したＮ個の辺の情報を入力し、
該情報を入力したＮ個の辺を、該辺の起点から終点に向かう方向を基準としてＭ種類に分類し、
該分類された辺から、該分類毎に一つの辺を抽出し、
該抽出された辺もしくは該辺を延長した辺とにより、頂点が少なくとも３個以上の多角形を、候補形状として構成し、
該形成された候補形状と前記地物形状とを比較して評価値を求め、
該評価値に基づいて、前記地物形状を簡略化した簡略化形状を求める
地物形状簡略化方法。
【請求項１８】
頂点数Ｎ（Ｎは５以上の自然数）の多角形として表現された地物形状を、頂点数Ｍ（Ｍは３以上、Ｎ未満の自然数）の図形に変換する処理をコンピュータに実行させるプログラムであって、
前記地物形状を構成する連続したＮ個の辺の情報を入力する機能を実現するプログラムコードと、
該情報を入力したＮ個の辺を、該辺の起点から終点に向かう方向を基準としてＭ種類に分類する機能を実現するプログラムコードと、
該分類された辺から、該分類毎に一つの辺を抽出する機能を実現するプログラムコードと、
該抽出された辺もしくは該辺を延長した辺とにより、頂点が少なくとも３個以上の多角形を、候補形状として構成する機能を実現するプログラムコードと、
該形成された候補形状と前記地物形状とを比較して評価値を求める機能を実現するプログラムコードと、
該評価値に基づいて、前記地物形状を簡略化した簡略化形状を求める機能を実現するプログラムコードと
を含んだプログラム。
【請求項１】
頂点数Ｎ（Ｎは５以上の自然数）の多角形として表現された地物形状を、頂点数Ｍ（Ｍは３以上、Ｎ未満の自然数）の図形に変換する地物形状簡略化装置であって、
前記地物形状を構成する連続したＮ個の辺の情報を入力する辺情報入力手段と、
該情報を入力したＮ個の辺を、該辺の起点から終点に向かう方向を基準としてＭ種類に分類する辺分類手段と、
該分類された辺から、該分類毎に一つの辺を抽出する辺抽出手段と、
該抽出された辺もしくは該辺を延長した辺とにより、頂点が少なくとも３個以上の多角形を、候補形状として構成する候補形状形成手段と、
該形成された候補形状と前記地物形状とを比較して評価値を求める評価値演算手段と、
該評価値に基づいて、前記地物形状を簡略化した簡略化形状を求める簡略化形状決定手段と
を備えた地物形状簡略化装置。
【請求項２】
前記辺分類手段は、前記辺の方向が、全方向をＭ個に分割したいずれの範囲に属するかにより分類する手段である請求項１記載の地物形状簡略化装置。
【請求項３】
前記全方向のＭ個の分割は、前記分類する辺のうち最も長い辺の方向を基準とし行なう請求項２記載の地物形状簡略化装置。
【請求項４】
前記辺抽出手段は、前記Ｍ種類に分類された各々の分類に属する辺のうち、長い辺から順に所定個数を抽出して、前記評価値演算手段により演算に供する請求項１記載の地物形状簡略化装置。
【請求項５】
前記辺抽出手段は、前記Ｍ種類に分類された各々の分類に属する辺のうち、絶対値が所定値より大きく、且つ前記地物形状の周囲長に対して所定の割合より大きな割合を有する辺を抽出の対象とする請求項１記載の地物形状簡略化装置。
【請求項６】
前記候補形状形成手段は、前記抽出された辺を延長した辺を用いる際、前記地物形状からはみ出さない形状のみを、前記候補形状として構成する請求項１記載の地物形状簡略化装置。
【請求項７】
前記候補形状形成手段は、前記辺により候補形状を構成する際、隣接する２辺が候補形状の内側に形成する総ての角の角度が、少なくとも２７０度以上の所定の角度より小さい形状のみを、前記候補形状として構成する請求項１記載の地物形状簡略化装置。
【請求項８】
前記評価値演算手段は、前記地物形状と前記候補形状の各面積および両形状の重なりに基づく面積を用いて評価値を演算する請求項１記載の地物形状簡略化装置。
【請求項９】
請求項８記載の地物形状簡略化装置であって、
前記評価値演算手段は、前記両形状の重なりに基づく面積として、両形状の重なった部分の面積および前記地物形状に対して前記候補形状が重ならない部分の面積のうち、少なくとも一方の面積を求め、該面積の前記地物形状の面積に対する割合を用いて前記評価値を求める地物形状簡略化装置。
【請求項１０】
請求項１記載の地物形状簡略化装置であって、
前記辺情報入力手段が入力した辺情報に基づいて前記簡略化形状を求める過程で、前記頂点数Ｎの地物形状を簡略化することを中止すべき所定の条件が成立していることを判断する中止条件判別手段を備え、
前記簡略化形状決定手段は、
前記簡略化情報が決定された場合には、該簡略化情報を、前記地物形状が記述されたフォーマットと同一のフォーマットで出力すると共に、
前記中止条件が成立していると判断した場合には、前記フォーマットで記述された地物形状の辺の情報をそのまま出力する
地物形状簡略化装置。
【請求項１１】
前記中止条件判別手段は、前記辺情報を入力した総ての辺の長さが所定の判定値以下である場合には、前記中止条件が成立していると判断する請求項１０記載の地物形状簡略化装置。
【請求項１２】
前記中止条件判別手段は、前記入力した辺情報から、外形形状が曲線の地物形状を短い直線で近似した辺が存在する場合には、前記中止条件が成立していると判断する請求項１０記載の地物形状簡略化装置。
【請求項１３】
前記中止条件判別手段は、前記入力した辺情報に基づいて前記簡略化形状を求める過程で、予め設定した条件を満足する候補形状が一つも得られなかった場合には、前記中止条件が成立していると判断する請求項１０記載の地物形状簡略化装置。
【請求項１４】
請求項１記載の地物形状簡略化装置であって、更に、
前記候補形状として複数の形状が求められた場合であって、そのうちのいずれの候補形状も前記評価値が、予め定めた閾値を超えていない場合には、該複数の形状のうち所定の条件を満たす２個以上の形状を合成した形状を新たな候補形状として前記評価値を求め、該評価値が所定の合成条件を満たす場合には、該合成した候補形状を、前記簡略化形状として求める手段を備えた
地物形状簡略化装置。
【請求項１５】
請求項１４記載の地物形状簡略化装置であって、
前記合成を行なう２個以上の形状が満たす所定の条件は、各形状の面積が、前記地物形状の面積に対して、所定の割合以上であるという条件を含む地物形状簡略化装置。
【請求項１６】
請求項１４記載の地物形状簡略化装置であって、
前記所定の合成条件は、
前記２個以上の形状が重なっていること、
前記合成後の候補形状における隣接する２辺が該候補形状の内側に形成する総ての角度が、少なくとも２７０度以上の所定の角度より小さいこと
である地物形状簡略化装置。
【請求項１７】
頂点数Ｎ（Ｎは５以上の自然数）の多角形として表現された地物形状を、頂点数Ｍ（Ｍは３以上、Ｎ未満の自然数）の図形に変換する方法であって、
前記地物形状を構成する連続したＮ個の辺の情報を入力し、
該情報を入力したＮ個の辺を、該辺の起点から終点に向かう方向を基準としてＭ種類に分類し、
該分類された辺から、該分類毎に一つの辺を抽出し、
該抽出された辺もしくは該辺を延長した辺とにより、頂点が少なくとも３個以上の多角形を、候補形状として構成し、
該形成された候補形状と前記地物形状とを比較して評価値を求め、
該評価値に基づいて、前記地物形状を簡略化した簡略化形状を求める
地物形状簡略化方法。
【請求項１８】
頂点数Ｎ（Ｎは５以上の自然数）の多角形として表現された地物形状を、頂点数Ｍ（Ｍは３以上、Ｎ未満の自然数）の図形に変換する処理をコンピュータに実行させるプログラムであって、
前記地物形状を構成する連続したＮ個の辺の情報を入力する機能を実現するプログラムコードと、
該情報を入力したＮ個の辺を、該辺の起点から終点に向かう方向を基準としてＭ種類に分類する機能を実現するプログラムコードと、
該分類された辺から、該分類毎に一つの辺を抽出する機能を実現するプログラムコードと、
該抽出された辺もしくは該辺を延長した辺とにより、頂点が少なくとも３個以上の多角形を、候補形状として構成する機能を実現するプログラムコードと、
該形成された候補形状と前記地物形状とを比較して評価値を求める機能を実現するプログラムコードと、
該評価値に基づいて、前記地物形状を簡略化した簡略化形状を求める機能を実現するプログラムコードと
を含んだプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２００７−８７３３１（Ｐ２００７−８７３３１Ａ）
【公開日】平成１９年４月５日（２００７．４．５）
【国際特許分類】
【出願番号】特願２００５−２７８４２７（Ｐ２００５−２７８４２７）
【出願日】平成１７年９月２６日（２００５．９．２６）
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
【公開日】平成１９年４月５日（２００７．４．５）
【国際特許分類】
【出願日】平成１７年９月２６日（２００５．９．２６）
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
[ Back to top ]