JPS63285688A - 点情報の管理方式 - Google Patents
点情報の管理方式Info
- Publication number
- JPS63285688A JPS63285688A JP12002887A JP12002887A JPS63285688A JP S63285688 A JPS63285688 A JP S63285688A JP 12002887 A JP12002887 A JP 12002887A JP 12002887 A JP12002887 A JP 12002887A JP S63285688 A JPS63285688 A JP S63285688A
- Authority
- JP
- Japan
- Prior art keywords
- node
- information
- division information
- nodes
- point
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Image Analysis (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔技術分野〕
本発明は画像符号化、画像検索、画像伝送、クラスタリ
ング等に適用しうる点情報の管理方式に関するものであ
る。
ング等に適用しうる点情報の管理方式に関するものであ
る。
従来より、画像を表現するデータ構造として、４分木構
造によって表現する方式が知られている。
造によって表現する方式が知られている。
このものは、第２図（ａ）にも示すように、４分領域内
が単−領域種になるまで再帰的に４分割する方式であり
、記憶効率がよくしかもそのデータ構造上で基本的な画
像処理が可能であるとともに、対象物の構造を概略的な
段階から詳細な段階まで階層的に捉え易い利点を有して
いるが、特に境界部でノードの数が増加するといった問
題点があった。
が単−領域種になるまで再帰的に４分割する方式であり
、記憶効率がよくしかもそのデータ構造上で基本的な画
像処理が可能であるとともに、対象物の構造を概略的な
段階から詳細な段階まで階層的に捉え易い利点を有して
いるが、特に境界部でノードの数が増加するといった問
題点があった。
また、電子通信学会技術研究報告書「画像工学」Ｉ Ｅ
８３−８ （大火、坂内：“２値図形の簡約化２分木
表現”）には、２分木を基本とした領域式（０，１の順
列データ）によるノード管理方式が提示されている。こ
のものは、簡約化２分木構造表現による管理方式であり
、上記した４分木構造表現と比較してノードの数が減少
するものの、２分木構造を基本としているために、ルー
ト（根）でもリニフ（葉）でもない中間ノードが増加す
るといった問題点があった。
８３−８ （大火、坂内：“２値図形の簡約化２分木
表現”）には、２分木を基本とした領域式（０，１の順
列データ）によるノード管理方式が提示されている。こ
のものは、簡約化２分木構造表現による管理方式であり
、上記した４分木構造表現と比較してノードの数が減少
するものの、２分木構造を基本としているために、ルー
ト（根）でもリニフ（葉）でもない中間ノードが増加す
るといった問題点があった。
本発明は、上記した従来における問題点を解消するため
になされたもので、ｎ次元空間における点情報を管理す
る方式において、点情報の記憶容量の圧縮ならびに効率
的検索を行なえるようにした点情報の管理方式を提供す
ることを目的とする。
になされたもので、ｎ次元空間における点情報を管理す
る方式において、点情報の記憶容量の圧縮ならびに効率
的検索を行なえるようにした点情報の管理方式を提供す
ることを目的とする。
本発明の構成を、２次元空間における点情報を対象にし
た場合の実施例に基づいて説明する。
た場合の実施例に基づいて説明する。
第１図は２次元空間において対象とする点情報を示した
図であり、この領域内にＡ、Ｂ、Ｃ，Ｄ、Ｅ、Ｆの点情
報が存在している場合の例である。
図であり、この領域内にＡ、Ｂ、Ｃ，Ｄ、Ｅ、Ｆの点情
報が存在している場合の例である。
また、第２図（ａｌ〜（Ｃ１は、第１図に示した点情報
を゛対象とした場合の、本発明による木構造の静的生成
過程を示す図である。
を゛対象とした場合の、本発明による木構造の静的生成
過程を示す図である。
先ず、第１図に示された領域を再帰的に４等分割してい
き、各々の分割領域内に点が１つだけ存在するまで分割
が行なわれる。ここまでの過程を木表現で示すと、第２
図（ａ）に示すようになる。なお、図中の目印と０印は
リーフを示しており、目印の付けられたリーフは点デー
タが有ることを示し、この点に関する情報を付加するこ
とが可能である。そして、０印の付けられたリーフは点
データが無いことを示している。また、図中の数字０．
１，２，３は各ノードに付加された分割情報であり、そ
れぞれ第３図に示す４分領域の分割情報ＮＷ、ＮＥ、Ｓ
Ｗ、ＳＥに対応している。
き、各々の分割領域内に点が１つだけ存在するまで分割
が行なわれる。ここまでの過程を木表現で示すと、第２
図（ａ）に示すようになる。なお、図中の目印と０印は
リーフを示しており、目印の付けられたリーフは点デー
タが有ることを示し、この点に関する情報を付加するこ
とが可能である。そして、０印の付けられたリーフは点
データが無いことを示している。また、図中の数字０．
１，２，３は各ノードに付加された分割情報であり、そ
れぞれ第３図に示す４分領域の分割情報ＮＷ、ＮＥ、Ｓ
Ｗ、ＳＥに対応している。
次に、第２図（ｂｌに示すように、点データの無いリー
フを削除して対象とする点のみを木構造で表現し、かつ
第２図（Ｃ）に示すように枝の数が１本である位数１の
ノードを削除し、その子ノードに統合して分割情報を付
加する。
フを削除して対象とする点のみを木構造で表現し、かつ
第２図（Ｃ）に示すように枝の数が１本である位数１の
ノードを削除し、その子ノードに統合して分割情報を付
加する。
第４図（ａ） 、 （ｂ）にそれぞれノードとリーフの
構造を示す。ノードは分割情報として子ノードまたはリ
ーフへのポインタを最大４個まで設定可能な構造となっ
ており、リーフはインデックスと分割情報からなる構造
となっている。
構造を示す。ノードは分割情報として子ノードまたはリ
ーフへのポインタを最大４個まで設定可能な構造となっ
ており、リーフはインデックスと分割情報からなる構造
となっている。
上記した第２図（Ｃ）の木構造を、第４図（ａ） 、
（ｂ）に示したノードならびにリーフの構造で表現する
と第５図のようになり、ノードのポインタが０のところ
はその下にはノードもリーフもつながらないことを示し
ている。
（ｂ）に示したノードならびにリーフの構造で表現する
と第５図のようになり、ノードのポインタが０のところ
はその下にはノードもリーフもつながらないことを示し
ている。
第６図（ａ）〜（ｆ）は、上記した木構造の動的生成過
程を示す図である。
程を示す図である。
第６図（ａ）には、点Ａのみが存在する木が示されてい
る。いま、ここに点Ｂを入力すると、この点Ｂは点Ａの
ノードに包含されないため、第６図（ｂｌに示すように
幅方向にリーフを追加する。次に、点Ｃを入力すると、
この点Ｃは上記の点Ｂがあるノードに包含されるので、
第６図（ｅ）に示すように深さ方向にノードを追加して
分割情報を更新しリーフを追加する。
る。いま、ここに点Ｂを入力すると、この点Ｂは点Ａの
ノードに包含されないため、第６図（ｂｌに示すように
幅方向にリーフを追加する。次に、点Ｃを入力すると、
この点Ｃは上記の点Ｂがあるノードに包含されるので、
第６図（ｅ）に示すように深さ方向にノードを追加して
分割情報を更新しリーフを追加する。
続いて、点りを入力すると、この点りは上記したどのノ
ードにも包含されないので、第６図（ｄ）に示すように
幅方向にリーフを追加する。点Ｅを入力すると、この点
Ｅは上記の点りがあるノードに包含されるので、第６図
（ｅ）に示すように深さ方向にノードを追加して分割情
報を更新しリーフを追加する。さらに、点Ｆを入力する
と、この点Ｆは゛ 上記の点Ｅがあるノードに包含され
るので、第６図（ｆ）に示すように深さ方向にノードを
追加して分割情報を更新しリーフを追加する。
ードにも包含されないので、第６図（ｄ）に示すように
幅方向にリーフを追加する。点Ｅを入力すると、この点
Ｅは上記の点りがあるノードに包含されるので、第６図
（ｅ）に示すように深さ方向にノードを追加して分割情
報を更新しリーフを追加する。さらに、点Ｆを入力する
と、この点Ｆは゛ 上記の点Ｅがあるノードに包含され
るので、第６図（ｆ）に示すように深さ方向にノードを
追加して分割情報を更新しリーフを追加する。
次に、静的、動的な木構造生成フローを示し説明する。
第７図は、静的な木構造生成フローを示す図である。ま
ず、ステップＳ１において対象のみを４分木で再帰的に
表現し、次いでステップＳ２において位数１のノードを
子ノードに統合して分割情報を各ノードに付加し、さら
にステップＳ３において各部分木におけるリーフの多い
ノードから左から順に並べ替えることにより静的な木構
造が生成される。
ず、ステップＳ１において対象のみを４分木で再帰的に
表現し、次いでステップＳ２において位数１のノードを
子ノードに統合して分割情報を各ノードに付加し、さら
にステップＳ３において各部分木におけるリーフの多い
ノードから左から順に並べ替えることにより静的な木構
造が生成される。
第８図は、動的な木構造生成フローを示す図である。ス
テップＳｌｌにおいてインデックス、座標データ、更新
前の木構造が入力され、ステップＳ１２において座標デ
ータを分割情報に変換した後、ステップＳ１３において
更新前の木構造のルートを設定する。そして、ステップ
Ｓ１４において子の分割情報を取り出し、ステップ３１
５において入力座標の分割情報が子の分割情報に包含さ
れるかどうかが判断される。
テップＳｌｌにおいてインデックス、座標データ、更新
前の木構造が入力され、ステップＳ１２において座標デ
ータを分割情報に変換した後、ステップＳ１３において
更新前の木構造のルートを設定する。そして、ステップ
Ｓ１４において子の分割情報を取り出し、ステップ３１
５において入力座標の分割情報が子の分割情報に包含さ
れるかどうかが判断される。
ステップ５１５において、入力座標の分割情報が子の分
割情報に包含されると判断された場合は、ステップＳ１
６において子がリーフであるかどうかが判断され、リー
フであればステップＳ１７で深さ方向にノードを追加し
て分割情報を更新しリーフを追加する。そして、ステッ
プＳ２１で各部分木においてリーフの多いノードを左か
ら順に並べ替える。なお、上記したステップＳ１６にお
いて、子がリーフでないと判断された場合にはステップ
ＳＬ４にもどる。
割情報に包含されると判断された場合は、ステップＳ１
６において子がリーフであるかどうかが判断され、リー
フであればステップＳ１７で深さ方向にノードを追加し
て分割情報を更新しリーフを追加する。そして、ステッ
プＳ２１で各部分木においてリーフの多いノードを左か
ら順に並べ替える。なお、上記したステップＳ１６にお
いて、子がリーフでないと判断された場合にはステップ
ＳＬ４にもどる。
また、ステップ３１５において、入力座標の分割情報が
子の分割情報に包含されないと判断された場合はステッ
プ３１８に移行し、ここで入力座標の分割情報の長さを
親の分割情報の長さ＋１桁に設定し、それが子の分割情
報を包含するかどうかを判断する。このステップ３１８
で包含すると判断された場合は、ステップ３１９におい
て深さ方向にノードを追加して分割情報を更新しリーフ
を追加する。そして、ステップ３２１で各部分木におい
てリーフの多いノードを左から順に並べ替える。
子の分割情報に包含されないと判断された場合はステッ
プ３１８に移行し、ここで入力座標の分割情報の長さを
親の分割情報の長さ＋１桁に設定し、それが子の分割情
報を包含するかどうかを判断する。このステップ３１８
で包含すると判断された場合は、ステップ３１９におい
て深さ方向にノードを追加して分割情報を更新しリーフ
を追加する。そして、ステップ３２１で各部分木におい
てリーフの多いノードを左から順に並べ替える。
なお、上記したステップ８１８において、包含しないと
判断された場合にはステップ３２０で幅方向にリーフを
追加した後、ステップＳ２１で各部分木においてリーフ
の多いノードを左から順に並べ替える。
判断された場合にはステップ３２０で幅方向にリーフを
追加した後、ステップＳ２１で各部分木においてリーフ
の多いノードを左から順に並べ替える。
上記のようにしてノードを統合することにより、通常の
４分木構造に比較して、ノードの数を大幅に減らすこと
ができるものであり、さらに各ノードに分割情報を付加
することにより、上記した木構造生成過程で損われた階
層性を補うとともに、木構造上での検索を効率的に実行
することができる。これは、上記の分割情報の長さが領
域の大きさを表現しており（分割情報の長さが長い程領
域が小さい）、該分割情報のマツチングにより簡単に包
含関係が導かれることに基づくものである。
４分木構造に比較して、ノードの数を大幅に減らすこと
ができるものであり、さらに各ノードに分割情報を付加
することにより、上記した木構造生成過程で損われた階
層性を補うとともに、木構造上での検索を効率的に実行
することができる。これは、上記の分割情報の長さが領
域の大きさを表現しており（分割情報の長さが長い程領
域が小さい）、該分割情報のマツチングにより簡単に包
含関係が導かれることに基づくものである。
すなわち、第９図に示すように、Ｘの４骨領域ＸがＹの
４骨領域ｙに包含されているかどうかを判断するには、
Ｙの分割情報がｎ個のコード“３１”で表現されている
場合、Ｘの分割情報がｎ個以上“３１２”であり、かつ
このＸの分割情報の先頭からｎ個のコード“３１″′が
Ｙの分割情報コード“３１″と一致している場合のみ包
含されていると判断される。
４骨領域ｙに包含されているかどうかを判断するには、
Ｙの分割情報がｎ個のコード“３１”で表現されている
場合、Ｘの分割情報がｎ個以上“３１２”であり、かつ
このＸの分割情報の先頭からｎ個のコード“３１″′が
Ｙの分割情報コード“３１″と一致している場合のみ包
含されていると判断される。
そして、検索キーと各ノードの分割情報のパターンマツ
チングにより、ルートからリーフに辿ることにより検索
が実行されるが、該パターンマツチングを各部分木にお
いて左の技から行なおうとすると、左側のほうを辿る方
が早く下位の部分木に辿ることができる。そこで、各部
分木のノードにおいて、該ノードの下位につながってい
るリーフの数の多いノードから、左側から順に並べ替え
るという再構築を実行することにより、木構造そのもの
は左側に重心のあるアンバランスな木構造となるが、検
索時間に関してはバランス化される。
チングにより、ルートからリーフに辿ることにより検索
が実行されるが、該パターンマツチングを各部分木にお
いて左の技から行なおうとすると、左側のほうを辿る方
が早く下位の部分木に辿ることができる。そこで、各部
分木のノードにおいて、該ノードの下位につながってい
るリーフの数の多いノードから、左側から順に並べ替え
るという再構築を実行することにより、木構造そのもの
は左側に重心のあるアンバランスな木構造となるが、検
索時間に関してはバランス化される。
第１０図は、指定座標上に点が存在するかどうかを検索
するためのフローを示したものである。
するためのフローを示したものである。
検索が開始されると、まずステップＳ３１において座標
点をある大きさをもった分割情報に変換し、ステップＳ
３２においてルートを指定した後、ステップＳ３３で各
部分木において座標点の分割情報とノードの分割情報と
のパターンマツチングが行なわれる。そして、ステップ
Ｓ３３において、パターンマツチングが全て失敗した場
合は他領域に存在すると判断され、成功した場合は再帰
的に本処理が実行され、そしてリーフに辿りついた場合
は検索が正常に実行されたものとして終了する。
点をある大きさをもった分割情報に変換し、ステップＳ
３２においてルートを指定した後、ステップＳ３３で各
部分木において座標点の分割情報とノードの分割情報と
のパターンマツチングが行なわれる。そして、ステップ
Ｓ３３において、パターンマツチングが全て失敗した場
合は他領域に存在すると判断され、成功した場合は再帰
的に本処理が実行され、そしてリーフに辿りついた場合
は検索が正常に実行されたものとして終了する。
なお、上記した実施例においては、２次元空間上におけ
る点情報を管理する場合について説明したが、ｎ次元空
間上における点情報を管理する場合にも有効であること
は言うまでもない。
る点情報を管理する場合について説明したが、ｎ次元空
間上における点情報を管理する場合にも有効であること
は言うまでもない。
以上説明した本発明によれば、再帰的に２のｎ乗に分割
された領域のうち点情報を含む領域のみを木表現し、さ
らに位数が１のノードは子ノードと統合するとともに、
各ノードには親ノードに対する位置情報である分割情報
を付加するようにしたので、枝、ノードの数を少なくで
きるので記憶容量が少なくてすみ、分割情報に基づ（検
索ならびに木構造の再構築により、検索時間が短縮化さ
れ効率的検索が行なえるとともに検索時間のバランス化
が計れる。
された領域のうち点情報を含む領域のみを木表現し、さ
らに位数が１のノードは子ノードと統合するとともに、
各ノードには親ノードに対する位置情報である分割情報
を付加するようにしたので、枝、ノードの数を少なくで
きるので記憶容量が少なくてすみ、分割情報に基づ（検
索ならびに木構造の再構築により、検索時間が短縮化さ
れ効率的検索が行なえるとともに検索時間のバランス化
が計れる。
第１図は本発明の詳細な説明するための対象とする点情
報を示す図、 第２図は第１図に示す点情報を本方式により木構造で表
現する場合の静的生成過程を示す図、 第３図は対象とする４分領域と分割情報の関係を示す図
、 第４図は本発明によるノードとリーフの構造を示す図、 第５図は第２図（Ｃ）に示した木構造を本発明によるノ
ードとリーフの構造で示した図、 第６図は本発明による木構造の動的生成過程を 。 示す図、 第７図は静的な木構造生成フローを示す図、第８図は動
的な木構造生成フローを示す図、第９図は包含関係を説
明するための図、第１０図は指定座標上に点が存在する
かどうかを検索するためのフローを示す図である。 特許出願人 株式会社 リ コ −（０１ノーＹ′
、、構ｒ乏 （ｂ）シー７の構郊
配第４図 第５図 （０） （ｂ） （Ｃ）
（ｄ）Ｆ （ｅ） （ｆ）第６図 第７図 第９図 第８図
報を示す図、 第２図は第１図に示す点情報を本方式により木構造で表
現する場合の静的生成過程を示す図、 第３図は対象とする４分領域と分割情報の関係を示す図
、 第４図は本発明によるノードとリーフの構造を示す図、 第５図は第２図（Ｃ）に示した木構造を本発明によるノ
ードとリーフの構造で示した図、 第６図は本発明による木構造の動的生成過程を 。 示す図、 第７図は静的な木構造生成フローを示す図、第８図は動
的な木構造生成フローを示す図、第９図は包含関係を説
明するための図、第１０図は指定座標上に点が存在する
かどうかを検索するためのフローを示す図である。 特許出願人 株式会社 リ コ −（０１ノーＹ′
、、構ｒ乏 （ｂ）シー７の構郊
配第４図 第５図 （０） （ｂ） （Ｃ）
（ｄ）Ｆ （ｅ） （ｆ）第６図 第７図 第９図 第８図
Claims (3)
- （１）ｎ次元空間における点情報を管理する方式におい
て、ｎ次元空間を再帰的に２のｎ乗に分割し、この分割
された領域のうち点情報を含む領域のみを木表現し、さ
らに位数が１のノードは子ノードと統合するとともに、
各ノードには親ノードに対する位置情報である分割情報
を付加するようにしたことを特徴とする点情報の管理方
式。 - （２）上記木表現過程においてリーフの多いノード順に
並べることを特徴とする特許請求の範囲第（１）項記載
の点情報の管理方式。 - （３）入力データを上記分割情報に変換しノードの分割
情報とのパターンマッチングにより検索を行なうように
したことを特徴とする特許請求の範囲第（１）項または
第（２）項記載の点情報の管理方式。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP12002887A JPS63285688A (ja) | 1987-05-19 | 1987-05-19 | 点情報の管理方式 |
| US07/195,266 US4944023A (en) | 1987-05-19 | 1988-05-18 | Method of describing image information |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP12002887A JPS63285688A (ja) | 1987-05-19 | 1987-05-19 | 点情報の管理方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPS63285688A true JPS63285688A (ja) | 1988-11-22 |
Family
ID=14776121
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP12002887A Pending JPS63285688A (ja) | 1987-05-19 | 1987-05-19 | 点情報の管理方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS63285688A (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2001043388A (ja) * | 1999-07-29 | 2001-02-16 | Canon Inc | 画像処理方法、画像処理装置及び記憶媒体 |
| JP2008044102A (ja) * | 2007-09-25 | 2008-02-28 | Hitachi Via Mechanics Ltd | 加工装置 |
| WO2022097279A1 (ja) * | 2020-11-06 | 2022-05-12 | 日本電信電話株式会社 | マージ領域検出方法、マージ領域検出装置及びプログラム |
-
1987
- 1987-05-19 JP JP12002887A patent/JPS63285688A/ja active Pending
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2001043388A (ja) * | 1999-07-29 | 2001-02-16 | Canon Inc | 画像処理方法、画像処理装置及び記憶媒体 |
| JP2008044102A (ja) * | 2007-09-25 | 2008-02-28 | Hitachi Via Mechanics Ltd | 加工装置 |
| WO2022097279A1 (ja) * | 2020-11-06 | 2022-05-12 | 日本電信電話株式会社 | マージ領域検出方法、マージ領域検出装置及びプログラム |
| JPWO2022097279A1 (ja) * | 2020-11-06 | 2022-05-12 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Guibas et al. | Optimal shortest path queries in a simple polygon | |
| KR100798609B1 (ko) | 데이터 소트 방법, 데이터 소트 장치 및 데이터 소트 프로그램을 기억하는 기억 매체 | |
| CN107798054B (zh) | 一种基于Trie的范围查询方法及装置 | |
| Kopelowitz | On-line indexing for general alphabets via predecessor queries on subsets of an ordered list | |
| JPH11184837A (ja) | 最短経路探索システム | |
| JPH11212980A (ja) | インデクス作成方法および検索方法 | |
| US7222125B2 (en) | Data structure managing device, data structure managing system, data structure managing method, and recorded medium where data structure managing program is stored | |
| CN113407538A (zh) | 一种多源异构关系型数据库数据的增量采集方法 | |
| De Jonge et al. | Two access methods using compact binary trees | |
| Tamassia et al. | Dynamic maintenance of planar digraphs, with applications | |
| Tseng et al. | Generating frequent patterns with the frequent pattern list | |
| CN108628969A (zh) | 一种空间关键字索引方法及平台、存储介质 | |
| Matula et al. | Two linear-time algorithms for five-coloring a planar graph | |
| CN105025013A (zh) | 基于优先级Trie树的动态IP匹配模型 | |
| JPS63285688A (ja) | 点情報の管理方式 | |
| KR100256686B1 (ko) | 다중 균형 트리 구조를 이용한 관리정보 트리에서의 노드 검색,생성 및 삭제 방법 | |
| Scholten et al. | General methods for adding range restrictions to decomposable searching problems | |
| JPS63286976A (ja) | ２種領域情報の管理方式 | |
| JP2001134594A (ja) | 類似特徴量の検索方法，その検索装置およびその検索プログラム記録媒体 | |
| Preparata et al. | Output-sensitive generation of the perspective view of isothetic parallelepipeds | |
| Plesník | Towards minimum k‐geodetically connected graphs | |
| CN115062054B (zh) | 基于递归索引树的克林闭包正则路径查询优化方法 | |
| JPH01267780A (ja) | 多種領域情報の管理方式 | |
| JPS63292271A (ja) | ２種領域情報の管理方式 | |
| KR20080008573A (ko) | Ｘｍｌ 데이터로부터 연관규칙을 추출하기 위한 방법 |