(57)【特許請求の範囲】
【請求項１】
２次元または３次元の形状情報を表示・操作するシステムにおいて、
実空間を計測して得られた間引き前の点群の情報を入力する手段と、
前記点群を含む所定の対象領域を順次２分割し下位に行くに従って多くの領域（ノード）に分割されてなる木構造データを生成する手段と、
木構造データにおける間引き処理を行うノードを木構造の枝ごとに決定する手段と、
決定されたノード群を、間引き後の点群の取得対象とする分割領域群として選別する手段と、
前記選別された各ノードにおいてそのノードが表す分割領域を代表する１以上の点を代表点として選別し、選別された代表点群の総体を間引き後点群として取得する手段と
を有し、
前記間引き後点群に含まれる任意の点は、前記間引き前の点群中に１対１に対応する点が存在するものである
ことを特徴とするシステム。
【請求項２】
請求項１記載のシステムにおいて、
さらに、間引き後の点群数を入力する手段を有し、
前記間引き処理を行うノードを決定する手段は、前記間引き前の点群数に対する前記入力された間引き後の点群数の割合に基づき、木構造の各ノードに含まれる点数に上記割合を掛けた数が所定数より小さくなった時のノードを間引き処理を行うノードとして決定するものである
ことを特徴とするシステム。
【請求項３】
請求項２記載のシステムにおいて、
前記所定数は１である
ことを特徴とするシステム。
【請求項４】
請求項２記載のシステムであって、
前記間引き後の点群数を指定する手段は、点群データの表示目的に応じて、動的な視点変更を伴う表示やアニメーション表示には少ない間引き点群数を指定し、静的な表示や計測にはより多い間引き点群数を指定するものであることを特徴とするシステム。
【請求項５】
請求項１に記載のシステムにおいて、
さらに、取得された間引き後点群データを、図面情報を格納する中間フォーマットで出力する点群データ出力手段を有することを特徴とするシステム。
【請求項６】
コンピュータによって実行される、２次元または３次元の形状情報を表示・操作する方法であって、
コンピュータに、実空間を計測して得られた間引き前の点群の情報を入力する工程と、
コンピュータが、前記点群を含む所定の対象領域を順次２分割し下位に行くに従って多くの領域（ノード）に分割されてなる木構造データを生成する工程と、
コンピュータが、前記木構造データにおける間引き処理を行うノードを木構造の枝ごとに決定する工程と、
コンピュータが、前記決定されたノード群を、間引き後の点群の取得対象とする分割領域群として選別する工程と、
コンピュータが、前記選別された各ノードにおいてそのノードが表す分割領域を代表する１以上の点を代表点として選別し、選別された代表点群の総体を間引き後点群として取得する工程と
を有し、
前記間引き後点群に含まれる任意の点は、前記間引き前の点群中に１対１に対応する点が存在するものである
ことを特徴とする方法。
【請求項７】
請求項６記載の方法において、
さらに、コンピュータに、間引き後の点群数を入力する工程を有し、
前記間引き処理を行うノードを決定する工程は、コンピュータが、前記間引き前の点群数に対する前記入力された間引き後の点群数の割合に基づき、木構造の各ノードに含まれる点数に上記割合を掛けた数が所定数より小さくなった時のノードを間引き処理を行うノードとして決定するものである
ことを特徴とする方法。
【請求項８】
請求項７記載の方法において、
前記所定数は１である
ことを特徴とする方法。
【請求項９】
請求項７記載の方法であって、
前記間引き後の点群数を指定する工程は、コンピュータに、点群データの表示目的に応じて、動的な視点変更を伴う表示やアニメーション表示には少ない間引き点群数を指定し、静的な表示や計測にはより多い間引き点群数を指定するものである
ことを特徴とする方法。
【請求項１０】
請求項６に記載の方法において、
さらに、コンピュータが、取得された間引き後点群データを、図面情報を格納する中間フォーマットで出力する点群データ出力工程を有する
ことを特徴とする方法。
【請求項１１】
記憶媒体に格納され、コンピュータに、２次元または３次元の物体データを表示操作させるコンピュータソフトウエアプログラムであって、
コンピュータを、
実空間を計測して得られた間引き前の点群の情報を入力する手段、
前記点群を含む所定の対象領域を順次２分割し下位に行くに従って多くの領域（ノード）に分割されてなる木構造データを生成させる手段、
木構造データにおける間引き処理を行うノードを木構造の枝ごとに決定させる手段、
決定されたノード群を、間引き後の点群の取得対象とする分割領域群として選別させる手段、
前記選別された各ノードにおいてそのノードである分割領域を代表する１以上の点を代表点として選別し、選別された代表点群の総体を間引き後点群として取得させる手段
として機能させるものであり、
前記間引き後点群に含まれる任意の点は、前記間引き前の点群中に１対１に対応する点が存在するものである
ことを特徴とするコンピュータソフトウエアプログラム。
【請求項１２】
請求項１１記載のコンピュータソフトウエアプログラムにおいて、
さらに、コンピュータを、間引き後の点群数を入力する手段として機能させるものであり、
前記間引き処理を行うノードを決定する手段は、コンピュータを、前記間引き前の点群数に対する前記入力された間引き後の点群数の割合に基づき、木構造の各ノードに含まれる点数に上記割合を掛けた数が所定数より小さくなった時のノードを間引き処理を行うノードとして決定させるように機能させるものである
ことを特徴とするコンピュータソフトウエアプログラム。
【請求項１３】
請求項１２記載のコンピュータソフトウエアプログラムにおいて、
前記所定数は１である
ことを特徴とするコンピュータソフトウエアプログラム。
【請求項１４】
請求項１２記載のコンピュータソフトウエアプログラムであって、
前記間引き後の点群数を指定する手段は、コンピュータを、点群データの表示目的に応じて、動的な視点変更を伴う表示やアニメーション表示には少ない間引き点群数を指定し、静的な表示や計測にはより多い間引き点群数を指定させるように機能させるものであることを特徴とするコンピュータソフトウエアプログラム。
【請求項１５】
請求項１１に記載のコンピュータソフトウエアプログラムにおいて、
さらに、コンピュータを、取得された間引き後点群データを、図面情報を格納する中間フォーマットで出力させる点群データ出力手段として機能させることを特徴とするコンピュータソフトウエアプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、２次元または３次元の形状情報、特に点群データを表示・操作するシステムに関するものである。
【背景技術】
【０００２】
従来から、例えば３次元空間スキャナ等で所定の空間を計測し、その計測結果を点群データとして出力するシステムがある。
【０００３】
点群データは、例えば、部品の３次元モデル作成、計測による品質管理、可視化処理、アニメーション、レンダリング、マスカスタマイゼーション等の用途で用いられることが想定されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００６-２０８２６２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところで、点群データを活用する場合、用途に応じて必要となる点群の密度が異なることが想定される。すなわち、高い密度を満たす点群データを用意する必要がある用途がある一方で、例えばモデルの操作を必要とせず表示のみを目的とする場合には点群の数が多すぎると表示性能の低下が問題となるということがある。
【０００６】
このため、高密度点群から所定の方法で点群を間引いて点群数を減らすことが想定されるが、点群の分布密度は空間全体に亘って一様ではなく、単に隣り合う点群の１つを間引く等の処理では、間引いた後の点群に偏りが生じ形状の特徴を保ったまま点群数を減らすことはできない可能性がある。
【０００７】
この発明はこのような事情に鑑みてなされたもので、高密度点群から偏りの少ない間引き点群を取得できる形状データの処理システムを提供することにある。
【課題を解決するための手段】
【０００８】
上記課題を解決するため、本願発明の第一の主要な観点によれば、２次元または３次元の形状情報を表示・操作するシステムであって、実空間を計測して得られた間引き前の点群の情報を入力する手段と、前記点群を含む所定の対象領域を順次２分割し下位に行くに従って多くの領域（ノード）に分割されてなる木構造データを生成する手段と、木構造データにおける間引き処理を行うノードを木構造の枝ごとに決定する手段と、決定されたノード群を、間引き後の点群の取得対象とする分割領域群として選別する手段と、前記選別された各ノードにおいてそのノードが表す分割領域を代表する１以上の点を代表点として選別し、選別された代表点群の総体を間引き後点群として取得する手段とを有することを特徴とするシステムが提供される。
【０００９】
このような構成によれば、点群を含む領域を木構造データに属する各ノードに分割し、所定のノードから代表点を選択し、その代表点の総体を間引き後の点群とすることができる。このことで、高密度点群から偏りの少ない間引き点群を取得できる。
【００１０】
すなわち、入力された点群データにおいて相対的に点群の密度が高い領域では、間引き後の点群データにおいても相対的に点群の密度が高いものとなり、元の点群データにおいて相対的に点群の密度が低い領域では、間引き後の点群データにおいても、相対的に点群の密度が低いものとなる。
【００１１】
また、この発明の一実施形態によれば、このシステムは、さらに、間引き後の点群数を入力する手段を有し、前記間引き処理を行うノードを決定する手段は、前記間引き前の点群数に対する前記入力された間引き後の点群数の割合に基づき、木構造の各ノードに含まれる点数に上記割合を掛けた数が所定数より小さくなった時のノードを間引き処理を行うノードとして決定するものである。この場合、前記所定数は１であることが好ましい。また、前記間引き後の点群数を指定する手段は、点群データの表示目的に応じて、動的な視点変更を伴う表示やアニメーション表示には少ない間引き点群数を指定し、静的な表示や計測にはより多い間引き点群数を指定するものであることが望ましい。
【００１２】
この発明の他の一実施形態によれば、このシステムは、さらに、取得された間引き後点群データを、図面情報を格納する中間フォーマットで出力する点群データ出力手段を有する。
【００１３】
この発明の第二の主要な観点によれば、コンピュータによって実行される、２次元または３次元の形状情報を表示・操作する方法であって、コンピュータに、実空間を計測して得られた間引き前の点群の情報を入力する工程と、コンピュータが、前記点群を含む所定の対象領域を順次２分割し下位に行くに従って多くの領域（ノード）に分割されてなる木構造データを生成する工程と、コンピュータが、前記木構造データにおける間引き処理を行うノードを木構造の枝ごとに決定する工程と、コンピュータが、前記決定されたノード群を、間引き後の点群の取得対象とする分割領域群として選別する工程と、コンピュータが、前記選別された各ノードにおいてそのノードが表す分割領域を代表する１以上の点を代表点として選別し、選別された代表点群の総体を間引き後点群として取得する工程とを有することを特徴とする方法が提供される。
【００１４】
この発明の第三の主要な観点によれば、  記憶媒体に格納され、コンピュータに、２次元または３次元の物体データを表示操作させるコンピュータソフトウエアプログラムであって、コンピュータに、実空間を計測して得られた間引き前の点群の情報を入力する手段と、コンピュータに、前記点群を含む所定の対象領域を順次２分割し下位に行くに従って多くの領域（ノード）に分割されてなる木構造データを生成させる手段と、コンピュータに、木構造データにおける間引き処理を行うノードを木構造の枝ごとに決定させる手段と、コンピュータに、決定されたノード群を、間引き後の点群の取得対象とする分割領域群として選別させる手段と、コンピュータに、前記選別された各ノードにおいてそのノードが表す分割領域を代表する１以上の点を代表点として選別させ、選別された代表点群の総体を間引き後点群として取得させる手段とを有することを特徴とするコンピュータソフトウエアプログラムが提供される。
【００１５】
なお、ここに記載していない本願発明のその他の技術特徴は、以下の発明を実施するための形態及び添付図面の記載中で明らかにされるものである。
【図面の簡単な説明】
【００１６】
【図１】図１は、この発明の一実施形態を示す概略構成図。
【図２】図２は、同じく、処理を示すフローチャート。
【図３】図３は、間引き前の点群データと間引き後の点群データを示す概念図。
【図４】図４は、ＢＶＨの木構造を示す概略図。
【図５】図５は、同じく、点群ＢＶＨに従い間引き処理を行ったノード及び間引き後のラフ点群（代表点群の総体）を示す概念図。
【発明を実施するための形態】
【００１７】
以下、この発明の一実施形態を図面を参照して説明する。
【００１８】
図１は、この発明の点群データ間引きシステム１を示す概略構成図である。
【００１９】
このシステム１は、ＣＰＵ２、ＲＡＭ３、入出力インタフェース４等が接続されてなるバス５に、プログラム格納部６及びデータ格納部７が接続されてなる。プログラム格納部６には、点群テキストファイル処理部８と、ラフ点群数入力部９と、点群データ間引き処理部１０と、点群データファイル出力部１１と、ＩＧＥＳファイル出力部１２とが格納されている。また、データ格納部７には、点群テキストファイル１３と、点群データファイル１４と、ＩＧＥＳファイル１５とが格納される。さらに、点群データファイル１４はラフ点群データ１４ａと、詳細点群データ１４ｂにより構成されている。ここで、「ラフ点群」とは間引き処理後に残った点群を表し、「詳細点群」とは間引き処理で間引いた点群を表す。
【００２０】
ここで、上記プログラム格納部６及びデータ格納部７は、実際にはハードディスク等の記憶媒体である。そして、各構成部８〜１２は、実際には、コンピュータソフトウエアプログラムであり、上記ＣＰＵ２によってＲＡＭ３上に呼び出されて展開され実行されることで、この発明の各構成要素として機能するものである。
【００２１】
以下、各構成部８〜１２の構成及び作用を、図２のフローチャートを参照して、実際の動作と共に説明する。
【００２２】
まず、ステップＳ１（図２）で、点群テキストファイル処理部８が、点群テキストファイル１３を読み取って点群データ間引き処理部１０で処理できる一時点群データに変換する。この一時点群データは、ＲＡＭ３に展開される。ここで、上記点群テキストファイル１３は、例えば前記入出力インタフェース４に接続された３次元空間スキャナ等１６で計測された、空間上の各点の座標値と色の情報をテキスト形式で表した点群情報である。そして、図３（ａ）は、この点群テキストファイル処理部８で変換され、前記入出力インタフェース４に接続された出力手段１７としてのディスプレイ上に描画された一時点群データ１９を示したものである。このシステム１は、図３（ａ）に示す点群データから、図３（ｂ）に示すように、所望の数だけ間引いてなるラフ点群データを生成しようとするものである。
【００２３】
なお、この実施形態では、点群テキストファイル１３は、３次元空間スキャナ１６から出力されたデータを想定しているが、他の方法で作られたものであっても良い。
【００２４】
次に、ステップＳ２〜Ｓ３で、ラフ点群数入力部９により、間引き対象の点群データの範囲指定（ステップＳ２）と、ラフ点群数の指定（ステップＳ３）が行われる。ここで点群データの範囲指定は、ユーザが前記入力手段１８としてのマウス等を使ってディスプレイ（出力手段１７）上にボックスを描いてその範囲に含まれる点群（若しくは含まれない点群）を指定することで行っても良いし、実際に座標範囲をデータとして入力することで行っても良い。また、点群テキストファイル１３に含まれる点群データの全てを対象としても良い。また、点群テキストファイル処理部８は、この時、入力手段１８による指示に基づき出力手段１７上で点群データを回転させたり、移動させたり、拡大したりする等の処理を行って得られるように構成されていても良い。
【００２５】
ステップＳ３で指定するラフ点群数としては、ユーザが望む間引き後の点群の数を指定しても良いし、パーセンテージで指定するようにしても良い。具体的な点群数で指定を行う場合には、前記ラフ点群数入力部９は、ユーザの参照のために上記選択範囲に含まれる総点群数を取得して表示するようになっていることが好ましい。
【００２６】
また、このラフ点群数入力部９は、上記入力手段１８から点群データの使用目的が入力された際にこれに応じてラフ点群数（若しくは間引く割合）を決定する点群使用目的判別部９ａをさらに有する。この使用目的判別部９ａは、例えば、点群データの表示目的に応じて、動的な視点変更を伴う表示やアニメーション表示には少ない間引き点群数を指定し、静的な表示や計測にはより多い間引き点群数を指定する。
【００２７】
次に、ステップＳ４〜Ｓ６で、点群データ間引き処理部１０が、点群間引き処理を行う。この点群データ間引き処理部１０は、図１に示すように、点群が含まれる領域をＢＶＨの手法で複数の領域に分割するＢＶＨ領域分割処理部１０ａと上記分割した各領域に含まれる点群の個数と密度に応じて、領域毎に一定の割合（点群の総個数に対するラフ点群の個数の割合）で点群を間引く間引き部１０ｂとを有する。
【００２８】
まず、ＢＶＨ領域分割処理部１０ａが、指定された領域（内に含まれる点群）をＢＶＨの手法で複数の領域に分割する（ステップＳ４）。
【００２９】
ここで、ＢＶＨとは、Ｂｏｕｎｄｉｎｇ  Ｖｏｌｕｍｅ  Ｈｉｅｒａｒｃｈｙの略であり、一般的に、空間内での距離計測を高速に行うための手法として知られているものあるが、この発明では、新たな用途である、高密度な点群から偏りの少ない間引き点群を取得するための技術として用いるものである。本技術で用いるＢＶＨを、以後「点群ＢＶＨ」と呼ぶ。
【００３０】
この技術の原理は、３次元空間内の要素を含む空間を、順次２分割することにより木構造データを構成することである。この木構造は無閉路有向グラフであり、空間の２分割により作成されるため、各ノードは子を２つ持つか、全く子を持たないかのいずれかである。通常全く子を持たないノードは、対象となる要素の最小単位に関連付けられている。
【００３１】
図４は、空間内の３角形を対象要素としたＢＶＨの例である。簡単のため、２次元平面で表している。左側の木構造はＢＶＨの模式図である。ここでは、ＢＶＨの最も親のノードを深度１のノードと呼び、そこから世代が下がるにつれ、深度２のノード群、深度３のノード群、と数字を１つずつ上げて呼んでいる。
【００３２】
各ノードには境界ボックスが関連付けられている。ここで「境界ボックス」とは、図４の右側に点線で示すもので、対象となる３角形を含む最小の直方体を指す。図４の右側は各境界ボックスに含まれる３角形と、境界ボックスを表す長方形(２次元平面なので)のイメージを示すものである。
【００３３】
このようにして、入力された点群を含む領域は、このＢＶＨ技術により、複数の領域に分割されることなる。ただし、点群の密度は全領域に亘って一定ではないので、同じ深度であっても、ノード毎に含まれる点数が異なることになる。
【００３４】
次に、間引き部１０ｂが、上記総点群数と、ラフ点群数に基づいて具体的な間引き処理を行うために、間引き処理を行うノードを決定する。
【００３５】
すなわち、点群ＢＶＨを用いることで，以下の情報を取得することができる。
【００３６】
・３次元空間内の点群が含まれる複数の領域
・各領域内での点群の個数と密度
前記間引き部１０ｂは、これらの情報を利用することにより、どのノードで間引き処理を行うかを以下の方法で木構造の枝ごとに決定する。
【００３７】
・ラフ点群数入力部９への指定により、点群の総個数に対するラフ点群数の割合Ｘが求まる。
【００３８】
・深度の小さいノードから深度の大きいノードに向けて子を辿る。これは、枝を１つ１つ調べるようにして辿る。このとき、各ノードに対応する領域に含まれる点群数を確認する。
【００３９】
・点群数に対して上記のラフ点群数の割合Ｘを掛けた値が１以下になったときに、該当するノードを「間引き処理を行うノード」とする。
【００４０】
・上記「間引き処理を行うノード」の子ノード以下は探索しない。
【００４１】
ついで、当該間引き処理を行うそれぞれのノードにおいて、総点群数に対する詳細点群の数の割合で求められる割合の点群を間引く（ステップＳ６）。各領域に１点ずつ点群が残ることになるが、残る点は各領域を表す境界ボックスの中心に最も近い点とする。
【００４２】
図５は、上記間引き処理を行った後のラフ点群と間引き処理を行ったノードの例である。簡単のため、２次元平面で表している。この例では、図５の左側および右側下部の領域はより深度の小さいノードが「間引き処理を行うノード」として決定され、右側上部の領域は、より深度の大きいノードが「間引き処理を行うノード」として決定されている。
【００４３】
上記処理により、以下の条件を満たす間引きが可能となる。
【００４４】
・間引き前後で、相対的な点群の密度がほぼ変わらないこと。つまり、点群の密度が高い領域は、間引き実行後も点群全体に対する密度は相対的に高く、点群の密度が低い領域は、間引き実行後も点群全体に対する密度は相対的に低いままである。
【００４５】
・ラフ点群の数が、外部より入力された値にほぼ近い値になる。
【００４６】
この結果、点群データファイル出力部１１を介して、点群データファイル１４が出力される（ステップＳ７）。ステップＳ６によって求まったラフ点群と詳細点群は、それぞれラフ点群データ１４ａ、詳細点群データ１４ｂとして出力される。
【００４７】
出力されたラフ表示用点群データ１４ａと詳細点群データ１４ｂは以下に示す性質を持つ。
【００４８】
・ラフ点群データ１４ａと詳細点群データ１４ｂに含まれる任意の点は、入力された３次元空間内の一時点群データ１９に含まれる点と１対１に対応する。また、対応する点の３次元空間内での座標値は同一である。
【００４９】
・ラフ点群データ１４ａの点群の個数は、ラフ点群数入力部９により指定された値にほぼ近いものになっている。
【００５０】
・ラフ点群データ１４ａと詳細点群データ１４ｂは必ずしも密度が均一な点群データではない。入力された３次元空間内の一時点群データ１９において、相対的に点群の密度が高い領域では、ラフ点群データ１４ａと詳細点群データ１４ｂにおいても、相対的に点群の密度が高い。逆に、３次元空間内の一時点群データ１９において、相対的に点群の密度が低い領域では、ラフ点群データ１４ａと詳細点群データ１４ｂにおいても、相対的に点群の密度が低い。
【００５１】
加えて、ＩＧＥＳファイル出力部１２を介して、ラフ点群をＩＧＥＳファイル１５へ出力することが可能である（ステップＳ８）。ＩＧＥＳファイル１５は、図面情報を格納する中間フォーマットであるＩＧＥＳ形式のファイルである。
このことで、このシステムで処理した点群データを、ＣＡＤシステム等の図面編集ソフトでの評価・編集を支援することが容易になる。
【００５２】
以上説明した例はこの発明の一実施形態に過ぎず、この発明の要旨を変更しない範囲で種々変形可能である。
【符号の説明】
【００５３】
１…点群データ間引きシステム
２…ＣＰＵ
３…ＲＡＭ
４…入出力インタフェース
５…バス
６…プログラム格納部
７…データ格納部
８〜１２…構成部
８…点群テキストファイル処理部
９…ラフ点群数入力部
９ａ…点群使用目的判別部
１０…点群データ間引き処理部
１０ａ…ＢＶＨ領域分割処理部
１０ｂ…間引き部
１１…点群データファイル出力部
１２…ＩＧＥＳファイル出力部
１３…点群テキストファイル
１４…点群データファイル
１４ａ…ラフ点群データ
１４ｂ…詳細点群データ
１５…ＩＧＥＳファイル
１６…３次元空間スキャナ
１７…出力手段
１８…入力手段
１９…一時点群データ
【要約】      （修正有）【課題】高密度点群から偏りの少ない間引き点群を取得できる形状データの処理システムを提供する。【解決手段】実空間を計測して得られた間引き前の点群の情報を入力し処理する入力手段１８、点群テキストファイル処理部８と、前記入力された点群の間引き処理を行う点群データ間引き処理部１０とを有する。この点群データ間引き処理部１０は、前記点群を含む所定の対象領域を順次２分割し、下位に行くに従って多くの領域（ノード）に分割されてなる木構造データを生成するＢＶＨ領域分割処理部１０ａと、木構造データにおける間引き処理を行うノードを木構造の枝ごとに決定すると共に、決定されたノード群を、間引き後の点群の取得対象とする分割領域群として選別し、選別された各ノードにおいてそのノードが表す分割領域を代表する１以上の点を代表点として選別し、選別された代表点群の総体を間引き後点群として取得する間引き部１０ｂとを有する。【選択図】図１【図１】
0005948480.tif 000002
【図２】
0005948480.tif 000003
【図３】
0005948480.tif 000004
【図４】
0005948480.tif 000005
【図５】
0005948480.tif 000006