米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> 松下電器産業株式会社

発明の名称 形状データ圧縮方法および形状データ伸長方法
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開平7−192146
公開日 平成7年(1995)7月28日
出願番号 特願平5−333859
出願日 平成5年(1993)12月27日
代理人 【弁理士】
【氏名又は名称】小鍜治 明 (外2名)
発明者 平井 誠
要約 目的
頂点等の特徴点を削減することなく形状データ量を削減する。

構成
主軸変換処理31で、形状データの各座標値の分布範囲を狭めた後、部品データ量が多く、階層化がされてない場合は、分布範囲分割階層部品化処理43で、頂点の分布範囲を分割、階層部品化し、各部品について、再帰的部品圧縮処理44を再帰的に実行後、処理46で、各部品のデータの中の共有部分を探し、共有化する。処理47で、この部品階層における部品の、逆量子化座標変換パラメータの分布を調べ、量子化パラメータを決定する。最後に処理48で、量子化によってデータ量を削減可能な逆量子化座標変換パラメータを量子化し、データ圧縮する。次に、部品データ量が少なく、階層化指定もない場合は、処理34〜41で、特徴点である頂点と法線の量子化を行ない、各逆量子化座標変換パラメータの算出、補正を行なう。
特許請求の範囲
【請求項1】画像生成装置で使用される形状データの圧縮方法であって、複数の部品に分割された部品形状データを入力する第1の段階と、前記各部品ごとに、部品形状データの各座標値の分布を求め、各部品ごとの各座標値の量子化パラメータを決定する第2の段階と、前記各部品ごとの各座標値の量子化パラメータにしたがって、前記各部品形状データの各座標値を量子化する第3の段階とを有する形状データ圧縮方法。
【請求項2】第1の段階から第3の段階と、各部品の組み立てデータを構成している部品形状座標変換パラメータを入力し、量子化された各座標値を逆量子化するための逆量子化パラメータに基づいて演算し、逆量子化座標変換パラメータを得る第4の段階をさらに有する請求項1記載の形状データ圧縮方法。
【請求項3】量子化パラメータとして、量子化幅または量子化精度または量子化幅と量子化精度のいずれかを用いる請求項1記載の形状データ圧縮方法。
【請求項4】部品形状データとして、線の端点または線の中心点または面の頂点または面の中心点または曲面の制御点または楕円の中心点または楕円体の中心点のいずれかを用いる請求項1記載の形状データ圧縮方法。
【請求項5】第1の段階から第3の段階または第1の段階から第4の段階を再帰的に実行し、階層化された部品形状を階層的に圧縮する請求項1または2記載の形状データ圧縮方法。
【請求項6】第1の段階において、各部品形状データの各座標値を主軸変換し、第4の段階において、前記各部品形状データの主軸変換パラメータに基づいて、各部品形状座標変換パラメータを補正する請求項2記載の形状データ圧縮方法。
【請求項7】第1の段階において、各部品形状データの各座標値を円筒座標系または球座標系に変換し、第4の段階において、前記変換のパラメータに基づいて、各部品形状座標変換パラメータを補正する請求項2記載の形状データ圧縮方法。
【請求項8】部品形状データとして、面の法線ベクトルを用いる請求項1記載の形状データ圧縮方法。
【請求項9】第4の段階において得られた逆量子化座標変換パラメータの各座標値の一部または全部を、上の階層の部品形状データとして圧縮する請求項5記載の形状データ圧縮方法。
【請求項10】第1の段階において、部品化されていない形状データを入力し、入力した形状データの各座標値の分布を求め、分布範囲を分割し、部品化した形状データを得る請求項1記載の形状データ圧縮方法。
【請求項11】画像生成装置で使用される形状データの伸長方法であって、複数の部品に分割され量子化され圧縮された圧縮部品形状データと、前記各圧縮部品形状データの逆量子化パラメータを入力する第1の段階と、前記各部品ごとに、前記各逆量子化パラメータに基づいて、前記各圧縮部品形状データの各座標値を逆量子化する第2の段階とを有する形状データ伸長方法。
【請求項12】画像生成装置で使用される形状データの伸長方法であって、複数の部品に分割され量子化され圧縮された圧縮部品形状データと、前記各圧縮部品形状データの逆量子化座標変換パラメータを入力する第1の段階と、前記各部品ごとに、前記各逆量子化座標変換パラメータに基づいて、前記各圧縮部品形状データの各座標値を逆量子化し座標変換する第2の段階とを有する形状データ伸長方法。
【請求項13】逆量子化パラメータとして、量子化幅または量子化精度または量子化幅と量子化精度のいずれかを用いる請求項11または12記載の形状データ伸長方法。
【請求項14】圧縮部品形状データとして、線の端点または線の中心点または面の頂点または面の中心点または曲面の制御点または楕円の中心点または楕円体の中心点のいずれかを用いる請求項11または12記載の形状データ伸長方法。
【請求項15】第1の段階から第2の段階を再帰的に実行し、階層的に圧縮された部品形状と逆量子化パラメータとを階層的に伸長する請求項11または12記載の形状データ伸長方法。
【請求項16】第2の段階において、請求項6記載の主軸変換パラメータに基づいて補正された座標変換パラメータを用いる請求項12記載の形状データ伸長方法。
【請求項17】第2の段階において、請求項7記載の各圧縮部品形状データの円筒座標系または球座標系に変換された各座標値と前記変換のパラメータに基づいて補正された座標変換パラメータとを用いる請求項12記載の形状データ伸長方法。
【請求項18】圧縮部品形状データとして、面の法線ベクトルを用いる請求項11または12記載の形状データ伸長方法。
【請求項19】第2の段階において、下の階層の圧縮部品形状データとして、下の階層の逆量子化座標変換パラメータの各座標値の一部または全部を伸長する請求項15記載の形状データ伸長方法。
発明の詳細な説明
【0001】
【産業上の利用分野】本発明は、画像生成装置で使用される形状データの圧縮方法および伸長方法に関するものである。
【0002】
【従来の技術】従来の画像生成装置では、形状データ量を削減するために、曲面を多角形パッチもしくはパラメトリック曲面で近似する方法がとられていた(例えば、特願平4-202151号「3次元形状入力装置」)。
【0003】図6は従来のデータ量削減のための曲面を多角形パッチで近似する方法の説明図である。曲面60を近似多面体61で近似し、近似多面体61の各面を多角形パッチで表現している。
【0004】
【発明が解決しようとする課題】しかしながら上記の従来の方法では、さらに形状データ量を削減するために、多角形パッチの頂点もしくはパラメトリック曲面の特徴点を削減すると、曲面の滑らかさが失われたり、近似誤差が大きくなるという課題を有していた。
【0005】本発明はかかる点に鑑み、頂点もしくは特徴点を削減することなく、形状データ量を削減するための形状データ圧縮方法および形状データ伸長方法を提供するものである。
【0006】
【課題を解決するための手段】上記目的を達成するために、本発明の第1の形状データ圧縮方法は、複数の部品に分割された各部品ごとに、形状データの各座標値の各々の分布を求め、量子化パラメータを決定し、形状データの各座標値を量子化するものである。
【0007】また、上記第1の方法で圧縮された形状データを伸長する第1の形状データ伸長方法は、上記各部品ごとに逆量子化パラメータにしたがって逆量子化し伸長するものである。
【0008】さらに、本発明の第2の圧縮方法および伸長方法は、第1の方法の逆量子化パラメータの代わりに、部品形状座標変換パラメータに基づいて両者を合成した逆量子化座標変換パラメータを用いるものである。
【0009】本発明の第3の圧縮方法および伸長方法は、第1もしくは第2の方法を部品組み立ての階層構造に沿って再帰的に実行するものである。
【0010】本発明の第4の圧縮方法および伸長方法は、第2の方法において、各部品形状データの各座標値を主軸変換し、主軸変換パラメータに基づいて補正した部品形状座標変換パラメータを用いるものである。
【0011】本発明の第5の圧縮方法および伸長方法は、第2の方法において、各部品形状データの各座標値を円筒座標系または球座標系に変換し、前記変換パラメータに基づいて補正した部品形状座標変換パラメータを用いるものである。
【0012】本発明の第6の圧縮方法および伸長方法は、第3の方法において、逆量子化座標変換パラメータの各座標値の一部または全部を、上の階層の部品形状データとして圧縮し伸長するものである。
【0013】本発明の第7の圧縮方法は、部品化されていない形状データを入力し、入力した形状データの各座標値の分布を求め、分布範囲を分割し、部品化した形状データを得たのち、第1もしくは第2の方法を実行するものである。
【0014】
【作用】前記した手段により、本発明の第1の方法は、各部品ごとに各座標値の最適な量子化を行なうことができるので、座標値を表現するために必要なビット数を少なくすることが可能になる。
【0015】本発明の第2の方法は、逆量子化パラメータと座標変換パラメータを個別に表現する必要がないので、形状データ量を削減することができると同時に、伸長時に、逆量子化処理と座標変換処理をまとめて行なえるので、演算量を削減できる。
【0016】本発明の第3の方法は、形状データの各座標値の分布範囲を階層的に狭めることができ、最適な量子化を行なうことが可能になる。
【0017】本発明の第4の方法は、形状データの各座標値の分布範囲を狭めることができ、最適な量子化を行なうことが可能になると同時に、伸長時に、逆量子化処理と主軸逆変換処理と座標変換処理とをまとめて行なえるので、演算量を削減可能になる。
【0018】本発明の第5の方法は、球面もしくは円筒面上の点の座標値および単位長のベクトルの座標値の最適な量子化を行なうことが可能になると同時に、伸長時に、逆量子化処理と座標系逆変換処理と座標変換処理とをまとめて行なえるので、演算量を削減可能になる。
【0019】本発明の第6の方法は、各部品ごとに逆量子化座標変換パラメータの各座標値の最適な量子化を行なうことができるので、座標値を表現するために必要なビット数を少なくすることが可能になる。
【0020】本発明の第7の方法は、部品化されていない形状データを部品化し、各部品ごとに各座標値の最適な量子化を行なうことができるので、座標値を表現するために必要なビット数を少なくすることが可能になる。
【0021】
【実施例】以下本発明の一実施例の形状データ圧縮方法および形状データ伸長方法について、図面を参照しながら説明する。図1は本発明の方法を実施するための画像生成システムのブロック図である。
【0022】図1において、1は形状データ入力部で、形状データを入力する。2は形状データ処理部で、形状データの圧縮処理を行ない、圧縮した形状データを形状データ記憶部4に記憶する。また、形状データ処理部2は、必要に応じて形状データ記憶部4に記憶された圧縮記憶データを読みだし、伸長処理を行ない、形状データ表示部3に表示する。
【0023】図2は階層的に構成された部品形状例を示す図である。図2において、座標原点16と座標軸17a〜cで表される座標系(XYZ)で、机の形状データが表現されている。机全体は、天板10と足11〜14の部品から階層的に構成されている。天板10の形状データは、8つの頂点と6面の法線のデータで構成される。図2には、頂点A〜Fと法線I〜Kが示されている。
【0024】図3は図2に示した部品形状例の本実施例により圧縮された形状データの構成を示す図である。図3において、机21aは天板21bと4本の足21c〜fから構成され、天板21bと4本の足21c〜fは8つの頂点A〜Hと6つの法線I〜Nを共有している。スクリーン座標変換20は画像生成する場合に必要な座標変換で、上記座標原点16と座標軸17a〜cで表される座標系(XYZ)から、スクリーン座標系へ座標変換するものである。
【0025】(表1)に、天板21bの頂点A〜Fの座標系(XYZ)における座標値と、量子化した座標値(X’Y’Z’)を示す。
【0026】
【表1】

【0027】この2つの座標系の間の変換式を(数1)に示す。
【0028】
【数1】

【0029】(数1)において、右辺第1項の第1の行列(CX CY CZ)は天板21bの主軸変換22bを表している。右辺第1項の第2の行列は天板21bの頂点座標の量子化25bを表している。右辺第2項は天板21bの部品座標変換24bを表している。(表1)から明らかなように、量子化した座標値(X’Y’Z’)は、各座標値を1ビット、頂点ごとに3ビットで表現できるため、データ量を圧縮することができる。
【0030】(数1)に示した量子化を行なうには、まず主軸変換によって、各座標値の分布範囲を狭め、つぎに各座標値の分布範囲と分布の集中位置とから、逆量子化パラメータとして量子化幅と量子化精度を決定し、量子化する方法を用いる。
【0031】尚、量子化パラメータとしては、量子化幅または量子化精度または量子化幅と量子化精度のいずれかを用いればよい。
【0032】(表2)に、天板21bの量子化座標変換パラメータを構成する主軸変換行列22bの座標系(XYZ)における座標値と、球座標系(rθφ)に変換して量子化した座標値を示す。
【0033】
【表2】

【0034】この2つの座標系の間の変換式を(数2)に示す。
【0035】
【数2】

【0036】rの値は1固定で、0ビットで表現できる。θはπ/2単位で量子化され、0とπ/2の値をとり、1ビットで表現できる。φはπ/4単位で量子化され、0から7π/4の8通りの値をとり、3ビットで表現できる。よって、主軸変換22bは合計12ビットで表現できるため、データ量を圧縮することができる。
【0037】(表3)に、天板21bの法線I〜Kの座標系(XYZ)における座標値と、主軸変換した座標値(X”Y”Z”)と、球座標系(rθφ)に変換して量子化した座標値を示す。
【0038】
【表3】

【0039】この3つの座標系の間の変換式を(数3)に示す。
【0040】
【数3】

【0041】rの値は1固定で、0ビットで表現できる。θはπ/2単位で量子化され、0とπ/2の値をとり、1ビットで表現できる。φはπ/2単位で量子化され、0から3π/2の4通りの値をとり、2ビットで表現できる。よって、法線ごとに3ビットで表現できるため、データ量を圧縮することができる。
【0042】また、上記量子化によって、天板21bと4本の足21c〜fは、8つの頂点A〜Hと、6つの法線I〜Nと、主軸変換22bの座標値が同一になるため、共有することが可能となって、データ量を圧縮することができる。
【0043】図4は、本発明の一実施例の形状データ圧縮方法の流れ図である。図4において、30は再帰的部品圧縮処理の開始点を示し、44は再帰的部品圧縮処理の再帰的実行を示している。49は再帰的部品圧縮処理の再帰的実行からの復帰を示し、最も上の階層からの復帰は圧縮処理の終了を意味する。
【0044】以下、図4に示した処理の流れに沿って、部品化されていない場合の図2および図3に示した机の形状データの圧縮処理を説明する。
【0045】形状データが部品化されていない場合には、すべての頂点データとすべての法線データがそれぞれ同一の階層で表現されている。まず、主軸変換処理31を行ない、形状データの各座標値の分布範囲を狭める。次に、部品データ量が多く、階層化されていない場合は、分布範囲分割階層部品化処理43を行なう。処理43で、頂点間の接続を考慮しつつ、頂点の分布範囲を分割することで、階層部品化し、天板21bと4本の足21c〜fを得る。これらの部品について、1つずつ再帰的部品圧縮処理44を再帰的に実行する。
【0046】すべての部品の再帰的部品圧縮処理44を完了したら、処理46で、各部品のデータの中で、共有できる部分を探し、共有化する。そして処理47で、この部品階層における部品である天板21bおよび4本の足21c〜fの、部品座標変換24b〜fと、主軸変換22b〜fと、頂点座標の量子化25b〜fを合成した逆量子化座標変換パラメータの分布を調べ、逆量子化座標変換パラメータを量子化するための量子化パラメータを決定する。最後に処理48で、量子化によってデータ量を削減可能な逆量子化座標変換パラメータを量子化し、データ圧縮する。
【0047】以下再帰的に実行された天板21bの再帰的部品圧縮処理について説明する。まず、主軸変換処理31を行ない、形状データの各座標値の分布範囲を狭める。つぎに、部品データ量が少なく、これ以上階層化する指定もない場合は、処理34〜41で、特徴点である頂点と法線の量子化を行ない、それぞれの逆量子化座標変換パラメータを算出し、上記の主軸変換や、球座標変換にしたがって逆量子化座標変換パラメータを補正する。
【0048】図5は、本発明の一実施例の形状データ伸長方法の流れ図である。図5において、50は再帰的部品伸長処理の開始点を示し、55は再帰的部品伸長処理の再帰的実行を示している。57は再帰的部品伸長処理の再帰的実行からの復帰を示し、最も上の階層からの復帰は伸長処理の終了を意味する。
【0049】以下、図5に示した処理の流れに沿って、図2および図3に示した机の形状データの伸長処理を説明する。まず、再帰的部品伸長の実行に先立ち、スクリーン座標変換処理20のパラメータが与えられる。そして、処理51で、主軸変換処理22aと逆量子化座標変換パラメータの量子化処理23の合成されたパラメータをスクリーン座標へ逆量子化し、座標変換する。ここで得られた逆量子化座標変換パラメータを用いて、処理55で下の階層を、処理53で頂点などの特徴点を、処理54で法線を逆量子化し、座標変換する。
【0050】以上のように、本実施例の第1の形状データ圧縮方法は、複数の部品に分割された各部品ごとに、形状データの各座標値の各々の分布を求め、量子化パラメータを決定し、形状データの各座標値を量子化することにより、各部品ごとに各座標値の最適な量子化を行なうことができるので、座標値を表現するために必要なビット数を少なくすることが可能になる。
【0051】また、本実施例の第1の形状データ伸長方法は、上記各部品ごとに逆量子化パラメータにしたがって逆量子化し伸長することにより、各部品ごとに各座標値の最適な逆量子化を行なうことができるので、座標値を表現するために必要なビット数を少なくすることが可能になる。
【0052】さらに、本実施例の第2の圧縮方法および伸長方法は、部品形状座標変換パラメータに基づいて両者を合成した逆量子化座標変換パラメータを用いることにより、逆量子化パラメータと座標変換パラメータを個別に表現する必要がないので、形状データ量を削減することができると同時に、伸長時に、逆量子化処理と座標変換処理をまとめて行なえるので、演算量を削減できる。
【0053】本実施例の第3の圧縮方法および伸長方法は、部品組み立ての階層構造に沿って再帰的に実行することにより、形状データの各座標値の分布範囲を階層的に狭めることができ、最適な量子化を行なうことが可能になる。
【0054】本実施例の第4の圧縮方法および伸長方法は、各部品形状データの各座標値を主軸変換し、主軸変換パラメータに基づいて補正した部品形状座標変換パラメータを用いることにより、形状データの各座標値の分布範囲を狭めることができ、最適な量子化を行なうことが可能になると同時に、伸長時に、逆量子化処理と主軸逆変換処理と座標変換処理とをまとめて行なえるので、演算量を削減可能になる。
【0055】本実施例の第5の圧縮方法および伸長方法は、各部品形状データの各座標値を円筒座標系または球座標系に変換し、前記変換パラメータに基づいて補正した部品形状座標変換パラメータを用いることにより、球面もしくは円筒面上の点の座標値および単位長のベクトルの座標値の最適な量子化を行なうことが可能になると同時に、伸長時に、逆量子化処理と座標系逆変換処理と座標変換処理とをまとめて行なえるので、演算量を削減可能になる。
【0056】本実施例の第6の圧縮方法および伸長方法は、逆量子化座標変換パラメータの各座標値の一部または全部を、上の階層の部品形状データとして圧縮し伸長することにより、各部品ごとに逆量子化座標変換パラメータの各座標値の最適な量子化を行なうことができるので、座標値を表現するために必要なビット数を少なくすることが可能になる。
【0057】本実施例の第7の圧縮方法は、部品化されていない形状データを入力し、入力した形状データの各座標値の分布を求め、分布範囲を分割し、部品化した形状データを得たのち、形状データ圧縮方法を実行することにより、部品化されていない形状データを部品化し、各部品ごとに各座標値の最適な量子化を行なうことができるので、座標値を表現するために必要なビット数を少なくすることが可能になる。
【0058】なお、本実施例では形状データの特徴点として頂点について説明したが、特徴点として、線の端点または線の中心点または面の頂点または面の中心点または曲面の制御点または楕円の中心点または楕円体の中心点のいずれかを用いる場合にも、同一の方法で同じ効果が得られる。
【0059】
【発明の効果】以上のように、本発明の第1の形状データ圧縮方法は、複数の部品に分割された各部品ごとに、形状データの各座標値の各々の分布を求め、量子化パラメータを決定し、形状データの各座標値を量子化することにより、各部品ごとに各座標値の最適な量子化を行なうことができるので、座標値を表現するために必要なビット数を少なくすることが可能になる。
【0060】また、上記第1の方法で圧縮された形状データを伸長する第1の形状データ伸長方法は、上記各部品ごとに逆量子化パラメータにしたがって逆量子化し伸長することにより、各部品ごとに各座標値の最適な逆量子化を行なうことができるので、座標値を表現するために必要なビット数を少なくすることが可能になる。
【0061】さらに、本発明の第2の圧縮方法および伸長方法は、第1の方法の逆量子化パラメータの代わりに、部品形状座標変換パラメータに基づいて両者を合成した逆量子化座標変換パラメータを用いることにより、逆量子化パラメータと座標変換パラメータを個別に表現する必要がないので、形状データ量を削減することができると同時に、伸長時に、逆量子化処理と座標変換処理をまとめて行なえるので、演算量を削減できる。
【0062】本発明の第3の圧縮方法および伸長方法は、第1もしくは第2の方法を部品組み立ての階層構造に沿って再帰的に実行することにより、形状データの各座標値の分布範囲を階層的に狭めることができ、最適な量子化を行なうことが可能になる。
【0063】本発明の第4の圧縮方法および伸長方法は、第2の方法において、各部品形状データの各座標値を主軸変換し、主軸変換パラメータに基づいて補正した部品形状座標変換パラメータを用いることにより、形状データの各座標値の分布範囲を狭めることができ、最適な量子化を行なうことが可能になると同時に、伸長時に、逆量子化処理と主軸逆変換処理と座標変換処理とをまとめて行なえるので、演算量を削減可能になる。
【0064】本発明の第5の圧縮方法および伸長方法は、第2の方法において、各部品形状データの各座標値を円筒座標系または球座標系に変換し、前記変換パラメータに基づいて補正した部品形状座標変換パラメータを用いることにより、球面もしくは円筒面上の点の座標値および単位長のベクトルの座標値の最適な量子化を行なうことが可能になると同時に、伸長時に、逆量子化処理と座標系逆変換処理と座標変換処理とをまとめて行なえるので、演算量を削減可能になる。
【0065】本発明の第6の圧縮方法および伸長方法は、第3の方法において、逆量子化座標変換パラメータの各座標値の一部または全部を、上の階層の部品形状データとして圧縮し伸長することにより、各部品ごとに逆量子化座標変換パラメータの各座標値の最適な量子化を行なうことができるので、座標値を表現するために必要なビット数を少なくすることが可能になる。
【0066】本発明の第7の圧縮方法は、部品化されていない形状データを入力し、入力した形状データの各座標値の分布を求め、分布範囲を分割し、部品化した形状データを得たのち、第1もしくは第2の方法を実行することにより、部品化されていない形状データを部品化し、各部品ごとに各座標値の最適な量子化を行なうことができるので、座標値を表現するために必要なビット数を少なくすることが可能になる。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013