JP3967626B2 - 画像データ圧縮処理方法および画像処理装置 - Google Patents
画像データ圧縮処理方法および画像処理装置 Download PDFInfo
- Publication number
- JP3967626B2 JP3967626B2 JP2002128748A JP2002128748A JP3967626B2 JP 3967626 B2 JP3967626 B2 JP 3967626B2 JP 2002128748 A JP2002128748 A JP 2002128748A JP 2002128748 A JP2002128748 A JP 2002128748A JP 3967626 B2 JP3967626 B2 JP 3967626B2
- Authority
- JP
- Japan
- Prior art keywords
- triangle
- isosurface
- triangles
- error
- data
- 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.)
- Expired - Fee Related
Links
- 238000012545 processing Methods 0.000 title claims description 44
- 238000013144 data compression Methods 0.000 title claims description 18
- 238000003672 processing method Methods 0.000 title claims description 15
- 230000009467 reduction Effects 0.000 claims description 70
- 238000000034 method Methods 0.000 claims description 23
- 230000008569 process Effects 0.000 claims description 15
- 238000011946 reduction process Methods 0.000 claims description 14
- 230000005484 gravity Effects 0.000 claims description 13
- 239000000284 extract Substances 0.000 claims description 2
- 230000008859 change Effects 0.000 description 11
- 238000010586 diagram Methods 0.000 description 5
- 210000000689 upper leg Anatomy 0.000 description 5
- 238000012217 deletion Methods 0.000 description 4
- 230000037430 deletion Effects 0.000 description 4
- 238000002474 experimental method Methods 0.000 description 4
- 230000006870 function Effects 0.000 description 3
- 230000015556 catabolic process Effects 0.000 description 2
- 238000007796 conventional method Methods 0.000 description 2
- 238000006731 degradation reaction Methods 0.000 description 2
- 230000009471 action Effects 0.000 description 1
- 238000007906 compression Methods 0.000 description 1
- 230000006835 compression Effects 0.000 description 1
- 230000006866 deterioration Effects 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 230000008030 elimination Effects 0.000 description 1
- 238000003379 elimination reaction Methods 0.000 description 1
- 238000011156 evaluation Methods 0.000 description 1
- 230000002452 interceptive effect Effects 0.000 description 1
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T17/00—Three dimensional [3D] modelling, e.g. data description of 3D objects
- G06T17/20—Finite element generation, e.g. wire-frame surface description, tesselation
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T9/00—Image coding
- G06T9/001—Model-based coding, e.g. wire frame
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Geometry (AREA)
- Software Systems (AREA)
- Computer Graphics (AREA)
- Multimedia (AREA)
- Image Generation (AREA)
- Magnetic Resonance Imaging Apparatus (AREA)
- Measuring And Recording Apparatus For Diagnosis (AREA)
- Apparatus For Radiation Diagnosis (AREA)
- Processing Or Creating Images (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は，医療や産業用のＣＴあるいはＭＲＩなどから得られる三次元データから、データ量を抑えて正確な立体画像を表示する三角形ポリゴン（等値面）データを得るための画像データ圧縮処理方法および画像処理装置に関するものである。
【０００２】
【従来の技術】
医療分野において、Ｘ線ＣＴやＭＲＩ等によって得られたボリュームデータからの立体画像再構成の手法は、これまでにも数多くなされている。その中で、等値面生成の技術は、三次元画像の世界では多く使われ議論されてきた。等値面とは、３次元フィールドにおいて同じ値を面で表現することであり、ボクセルデータで定義される三次元関数をＦ（ｘ，ｙ，ｚ）と定数Ｃにより、式（１）を満たす集合を求めることである。
【０００３】
Ｆ（ｘ，ｙ，ｚ）＝Ｃ （１）
このような等値面を用いることにより、解像度の高い三次元画像が高速に取得出来るようになってきた。しかし、等値面生成を行なうと、大量のポリゴンが発生して、ＣＰＵ処理に時間がかかりまた多量のメモリ資源が消費されることから、対話的処理が困難になりやすい。このため、画像データの圧縮技術に対する強い要望がある。
【０００４】
これまでに提案されてきたデータ圧縮手法の中で、ＱＥＭ（ Quadric Error Metrics ）は、局所的に平面に近い点を探すもので、高密度なオリジナルメッシュと簡略後のメッシュとの誤差に関するエネルギー最小問題を２次の評価関数を用いて高速に解くもので、エッジ消去を繰り返すことにより三角形を削減していくものである。速度的には有効であるとされてきたが、ＱＥＭは等値面で生成されたデータを基に削減していく手法であるために、元々ＱＥＭが保持している情報には限界がある。そのため、限界がある中で等値面データを削減することから、元の形状を損なうような削減をしてしまう可能性があった。
【０００５】
【発明が解決しょうとする課題】
従来、ＣＴやＭＲＩで計測した三次元画像データ（ベースデータ）から立体画像を形成する場合には、データの一部を削減して、メモリ使用量を軽減するとともに時間の短縮を図ることが行なわれているが、これまでのデータ圧縮手法では、現実的な処理時間で画像化しようとすると、元画像の劣化がある程度大きくなるのを受容せざるを得ないという問題があった。
【０００６】
またＱＥＭでは、各エッジを順次削減しながら三角形を削減するが、非常に小さい三角形を大量に含む等値面データの場合は、処理時間が長くなるという問題があった。
【０００７】
本発明の課題は、医療や産業用のＣＴやＭＲＩで取得された三次元データからデータ量を抑えて高速に正確な等値面データを作成できるデータ圧縮手段を実現することにある。
【０００８】
【課題を解決するための手段】
小さい三角形を大量に含む等値面データの場合は、従来手法のＱＥＭのようにエッジ単位で削減するよりも、三角形単位で削減した方が効率的である。本発明では、三角形を小さい方から順次選択して削減処理を行ない、等値面が効率的に削減されるようにした。また、削減処理により生じる画像劣化を一定の範囲にとどめるため、誤差の評価を等値面生成に用いたベースデータ上で行なうようにした。従来の手法では、生成された等値面データを元にして削減していたが、本発明では、等値面を削減する際に、等値面生成時のベースデータを参照して誤差を評価し、削減後の定数値を求めることにより、形状の変化を極力抑えながら削減していくことを可能にする。ベースデータとは、等値面を生成する際に必ず必要となる基のデータ（３次元画像、構造格子、非構造格子）である。
【０００９】
等値面削減処理では、データの中心値から一定の幅を許容誤差範囲として設定するとともに、小さい方から順次選択した削除候補の三角形について代表点を求め、その代表点で誤差を評価し、三角形の削除可否判定を行なうようにして効率化を図っている。削減処理では、初期値として、等値面を生成して出来た三角形数に応じて全体の目標削減割合を与え、三角形を小さい方、たとえば面積の小さい方あるいは形の細長い方から順次選択して削減の可否を判定し、目標削減割合に達するまで、削減処理を繰り返す。三角形は、点あるいは線にして削除し、削除した三角形に隣接していた三角形も、それに応じて削除あるいは変形する。図１により、本発明による等値面削除処理の原理を具体的に説明する。
【００１０】
図１の（ａ）は、面積の小さい三角形を点にして削減していく手法である。図中の１は、図示されている等値面（ポリゴン）の中で面積がもっとも小さい三角形であり、最初に削除候補として選択される。また２は、三角形１の代表点であり、たとえば重心点が用いられる。この代表点２の座標をベースデータの対応座標に変換して削減時に生じる誤差を評価する。削減可能である場合には、三角形１を削減して、代表点２に点化するとともに、三角形１の三つの辺にそれぞれ辺で隣接していた他の三つの三角形も同時に削除する。また三角形１の三つの頂点に頂点で接していた他の三角形は、三角形１の代表点２へ拡張するように変形する。最大で４つの三角形を一度に削減することになるため、残った三角形の形状は大きく変化する可能性があり、三角形削減と同時に隣接三角形の情報を更新する。
【００１１】
図１の（ｂ）は、形の細長い三角形を辺にして削減していく手法である。図中の３，４は、形の細長い三角形の例である。細長い三角形は、三角形の辺の長さがもっとも短いものと、次に短い辺の長さとの差で選択され、この差が大きい順に三角形の削減処理を行なう。三角形３に注目すると、削減される三角形３は、もっとも短い辺の長さを零にすることで線になる。このため、削減される三角形３のもっとも短い辺に辺で隣接する他の三角形４も同時に削除され、三角形は一度に最大２つ削減されることとなる。初期値の与え方、連続的な削減処理に関しては、（ａ）の面積の小さい三角形の場合と同様である。
【００１２】
本発明による画像データ圧縮処理方法および画像処理装置は、以下のように構成できる。
（１） 三次元データに基づいて生成した三角形の等値面を削減する画像データ圧縮処理方法において、生成された等値面について、三角形を小さい方から順次取り出して、その三角形を削減した場合に生じる誤差が許容しうるものかどうかを該三角形の代表点を用いて、上記等値面を生成した三次元データ上で判定し、誤差が許容できる場合に該三角形を削除するとともに隣接する関連三角形を削除あるいは変化させる処理を行ない、また誤差が許容できない場合には該三角形を削除せずに、次の順番の三角形を取り出して同様な処理を繰り返すことを特徴とする画像データ圧縮処理方法の構成。
（２） 三角形を取り出す順序は、面積が小さい方あるいは形が細長い方から行なうことを特徴とする前項（１）に記載の画像データ圧縮処理方法の構成。
（３） 三角形を削減した場合に生じる誤差の判定は、等値面の生成に用いたベースデータ上で行なうことを特徴とする前項（１）または（２）に記載の画像データ圧縮処理方法の構成。
（４） 三角形を削減した場合に生じる誤差の判定は、該三角形の代表点として重心点を用い、ベースデータから、該三角形の重心点の座標を含む立方格子体を取り出してその中心位置を補間し、得られた座標が許容誤差内に入るかどうかにより判定することを特徴とする前項（３）に記載の画像データ圧縮処理方法の構成。
（５） 予め等値面の目標削減率を設定しておき、目標削減率に達するまで三角形の削減処理を繰り返すことを特徴とする前項（１）ないし（４）の何れかに記載の画像データ圧縮処理方法の構成。
（６） 三次元データに基づいて三角形の等値面を生成する機能をもつ三次元画像処理装置において、生成された等値面について、三角形を小さい方から順次取り出して、その三角形を削減した場合に生じる誤差が許容しうるものかどうかを該三角形の代表点を用いて、上記等値面を生成した三次元データ上で判定し、誤差が許容できる場合に該三角形を削除するとともに隣接する関連三角形を削除あるいは変化させる処理を行ない、また誤差が許容できない場合には該三角形を削除せずに、次の順番の三角形を取り出して同様な処理を繰り返す等値面削減処理部を備えていることを特徴とする三次元画像処理装置の構成。
（７） 三角形を取り出す順序は、面積が小さい方あるいは形が細長い方から行なうことを特徴とする前項（６）に記載の三次元画像処理装置の構成。
（８） 三角形を削減した場合に生じる誤差の判定は、等値面の生成に用いたベースデータ上で行なうことを特徴とする前項（６）または（７）に記載の三次元画像処理装置の構成。
・ 三角形を削減した場合に生じる誤差の判定は、該三角形の代表点として重心点を用い、ベースデータから、該三角形の重心点の座標を含む立方格子体を取り出してその中心位置を補間し、得られた座標が許容誤差内に入るかどうかにより判定することを特徴とする前項（８）に記載の三次元画像処理装置の構成。
・ 予め等値面の目標削減率を設定しておき、目標削減率に達するまで三角形の削減処理を繰り返すことを特徴とする前項（６）ないし（９）の何れかに記載の三次元画像処理装置の構成。
【００１３】
【作用】
本発明の等値面削減処理は、ベースデータを基本にして行なわれる。等値面の生成処理では、ベースデータを基に等値面（３角形ポリゴン）が生成される。等値面を削減する際にもこのベースデータを使用すれば、正確な情報を得ることが可能となり、従来技術に見られる画像劣化の原因の誤差を無くすことが出来る。誤差が無くなることにより、削減可能な部分とそれ以外の部分とを明確に分けることが可能になる。その結果、削減したにもかかわらず高品質な形状を保持した等値面データが得られる。
【００１４】
【発明の実施の形態】
次に図２ないし図６を用いて、本発明の好適な実施の形態について説明する。
【００１５】
図２は、本発明による画像処理装置の実施例構成を示す。図中、１０はＣＴやＭＲＩなどから取得されたボクセルデータ形式の原三次元画像データ、１１は画像処理装置、１２は原三次元画像データに基づいて等値面を生成する等値面生成部、１３は生成された等値面データ、１４は本発明により等値面削減処理を行なう等値面削減処理部、１５は削減結果の等値面データ、１６は等値面削減処理で用いられる構造格子データおよび非構造格子データと三次元画像データを含むベースデータである。
【００１６】
原三次元画像データ１０に基づいて任意の立体画像表示を行なう場合、等値面生成部１２は、たとえばMarching Cubesによりボクセルデータから立体の構造格子および非構造格子を作成し、三角形の等値面生成を行なう。生成された等値面データ１３は、多量の小さい三角形を含んでいる。等値面データ１３のデータ量を削減する場合、等値面削減処理部１４が起動される。等値面削減処理部１４は、等値面データ１３から削減候補の小さい三角形を順次取り出す削減候補選択処理と、取り出した削減候補三角形の削減により生じる誤差量をベースデータ１６に基づいて評価する誤差判定処理と、誤差量が許容可能かどうかを評価して三角形の削減可否を判定する削減可否判定処理と、三角形の削減により生じた隣接三角形の変更を計算する変更等値面計算処理を行ない、削減結果の等値面データ１５を出力する。
【００１７】
本発明の等値面削減処理については、さらに図３の実施例フローを参照して詳述する。以下、フローのステップ（Ｓ１）〜（Ｓ８）にしたがって、処理内容を順に説明する。なお、小さい三角形の例として、面積の小さい三角形を用いる。（Ｓ１）： 初期値として削減割合を設定する。等値面生成で得られる三角形の数は画像により異なるため、削減数ではなく削減割合を目標にして削減処理を行なうようにする。
（Ｓ２）： 小さい三角形を見つける。小さい三角形としては、図１の（ａ），（ｂ）で述べたように、面積の小さい方あるいは形の細長い方から順に選択する。
（Ｓ３）： 選択した三角形について、等値面データから誤差を判定するための代表点の座標値を求める。代表点は、たとえば三角形の重心点とする。
（Ｓ４）： 図４に示すように、等値面データで求めた三角形の代表点（◎）の座標値を含む立方格子体を、ベースデータの構造格子から探し出す。
（Ｓ５）： ベースデータから取り出した立方格子体により座標値を線形補間する。ベースデータは整数座標値（立方格子体の格子点座標）しか値を持っていないため、計算した代表点（◎）の座標値が整数座標値でないときには、図４のように立方格子体上で線形補間により求める。
（Ｓ６）： 三角形の削減可否を判定する。図４において、Ｃは等値面をとった時の座標値であり、ｅは削減可能幅である。代表点（◎）の座標値が、削減可能幅内に入るかどうかを比較する。座標値Ｃが、削減可能幅から外れるときは、その三角形の削減をやめて（Ｓ２）へ戻り、つぎの小さい三角形を探し出して、同様に削減処理を繰り返す。
（Ｓ７）： 代表点（◎）の座標値が、削減可能幅内に入ったときは、その三角形を削減して点にする。同時に、隣接する三角形の削除、変形を行ない、関連する各三角形の定数を再計算する。
（Ｓ８）： 三角形を削減した結果として、目標の削減割合が達成されたかどうかを判定する。目標の削減割合が達成された場合は削減処理を終了し、まだ達成されないばあいは、（Ｓ２）へ戻り、つぎの小さい三角形を探し出して、同様に削減処理を繰り返す。
【００１８】
図５は、具体例を用いて削減するかどうかの判定の様子を示したものである。case１では、×印がついた点を削減する。case２では、その後に出来る形状で◎の点を、ベースデータを用いて判定する。この場合、判定点は削減可能幅内に含まれており、形状の変化はあまりないとみなして、小さい×印が付いている点は削減されることになる。case３では、小さい×印が削減された時の形状の変化を、同様に◎の点で判定している。この場合削減可能幅の外にあり、×印の点を削減することによって起こる形状の変化が大きいとみなし、×印の点は削減しないことになる。
【００１９】
図６は、上記（Ｓ７）で三角形の削減が行なわれたとき、削減、変更が必要な三角形の範囲を示す。図の左側のポリゴンの中央の三角形が、削減される三角形であり、その各辺に隣接しているドットパターンの三つの三角形は、付随して削減される三角形である。図６の右側のポリゴン中のドットパターンを付された八つの三角形は、三角形の削減の結果、定数値を再計算する必要のある三角形である。
【００２０】
図６に示すように、小さい三角形が削減されることにより、周りの三角形の位置や形状が変わってくる。それらの変形した三角形の重心の定数値は、等値面で生成したときの定数値とは異なっている。この定数値が大きく外れているときは、小さな三角形でも削除によって形状が大きく変化するので、これを繰り返していくと、元の形状データとはかけ離れたものになってしまう。逆に、定数値が等値面を生成したときの定数値とほとんど差がないときには、その三角形を削減しても形状の変化は最小限に抑えられる。この三角形の重心の定数値を求めるときに、ベースデータを使用する。ベースデータには、等値面を生成するために必要な定数値が入っている。しかし、このベースデータは整数座標値しか値を持っていないため、計算した座標値が整数座標値でないときには、線形補間により求める必要がある。具体的には、格子空間として計算するため、その点を含む８点の定数値を使用しまた８点からの距離の比を用いることにより、正確な定数値を求める。線形補間により求めた値が、等値面をとった時の定数値と比較して削減可能幅内であれば、重心をとった三角形を点にする。逆に削減可能幅外の場合は、形状が大きく変化してしまう可能性があるため、三角形を点にする処理をせずに次の小さい三角形を探し出す処理へと進む。また、さらに精度を上げるため、三角形の線分長を基準として決め、線分長が長くなってきた場合には比較する点を増やしていく。削減可能幅は、式（２）により求める。式（２）のｅは削減可能幅、Ｃｍａｘ、Ｃｍｉｎはそれぞれ定数Ｃの最大値、最小値である。ｘは割合であり、５％の削減可能幅にしたいときはｘ＝０．０５を代入する。
【００２１】
ｅ＝（（Ｃｍａｘ）−（Ｃｍｉｎ））＊ｘ （２）
図７は、削減可能幅を変化させたときのポリゴン削減率の変化を示している。データは、Ｆｅｍ１２８．ｖo１という人間の大腿骨のデータを使用した。削減可能幅の違いによるポリゴン削減率の変化を示している。凡例部分の等値面数は、削減処理を行っていない標準状態での等値面数を示している。またＣ＝１９９６とは、このデータでのＣの中心値である。
【００２２】
削減可能幅が小さければ、それだけ削減される三角形は少なくなり、逆に削減可能幅を大きくすればするだけ、削減率も比例して大きくなっていくことがわかる、データにより削減可能幅を見極めていくことが必要である。
【００２３】
図８〜図１０は、人間の大腿骨のデータを用いて行なった等値面削減実験の結果の画像例である。図８はＣ＝５００のもの、図９および図１０はＣ＝３００のものである。
【００２４】
図８（ａ）は、削減処理を行わずに等値面をとった標準時のものであり、等値面数は６９４４８ある。図８（ｂ）は、ポリゴン削減率９０％を与えて削減したもので、等値面数は、７６０５となる。図８（c ）は、ポリゴン削減率を９０％とし、さらに削減可能幅５％を与えた時のものであり、等値面数は、５２０８５となる。図９（ａ）は、小さい三角形をランダムに３０％削減したものである。図９（ｂ）は、削減可能幅５％を与えて３０％削減したときのものであり、等値面数は、４６９２６となる。図１０（ａ）は、標準時の画像である。図１０（ｂ）は、小さい三角形をランダムに３０％削減した画像である。図１０（ｃ）は、削減可能幅５％を用いてランダムに３０％削減したものである。削減可能幅を用いたものは、細かな筋に関しても無くすことなく削減できていることがわかる。
【００２５】
【発明の効果】
本発明によれば、医療や産業用のＣＴやＭＲＩで取得された三次元データに基づく三角形の等値面データについて、任意に設定された削減率に応じて、削減しても精度にあまり支障が生じないように元の三次元データで検証しつつ、小さい三角形を選択して削減するため、データ量の任意の削減に対応して常に最良の精度で等値面データを生成することができる。このため、三次元画像処理において、必要に応じて少ないデータ量の等値面を用いながら、正確な画像を高速に作成し、処理することができる。
【図面の簡単な説明】
【図１】 本発明による等値面削減処理の原理説明図である。
【図２】 本発明による画像処理装置の実施例構成図である。
【図３】 本発明による等値面削減処理の実施例フロー図である。
【図４】 等値面データで求めた三角形の代表点（◎）の座標値を含む立方格子体の説明図である。
【図５】 具体例を用いて削減するかどうかの判定の様子を示す説明図である。
【図６】 三角形の削減が行なわれたとき、削減、変更が必要な三角形の範囲を例示する説明図である。
【図７】 削減可能幅を変化させたときのポリゴン削減率の変化を示すグラフである。
【図８】 人間の大腿骨のデータを用いて行なった等値面削減実験の結果の画像例（その１）である。
【図９】 人間の大腿骨のデータを用いて行なった等値面削減実験の結果の画像例（その２）である。
【図１０】 人間の大腿骨のデータを用いて行なった等値面削減実験の結果の画像例（その３）である。
【符号の説明】
１０：ＣＴやＭＲＩなどから取得された原三次元画像データ
１１：画像処理装置
１２：原三次元画像データに基づいて等値面を生成する等値面生成部
１３：生成された等値面データ
１４：本発明により等値面削減処理を行なう等値面削減処理部
１５：削減結果の等値面データ
１６：等値面削減処理で用いられる構造格子データおよび非構造格子データと三次元画像データを含むベースデータ
【発明の属する技術分野】
本発明は，医療や産業用のＣＴあるいはＭＲＩなどから得られる三次元データから、データ量を抑えて正確な立体画像を表示する三角形ポリゴン（等値面）データを得るための画像データ圧縮処理方法および画像処理装置に関するものである。
【０００２】
【従来の技術】
医療分野において、Ｘ線ＣＴやＭＲＩ等によって得られたボリュームデータからの立体画像再構成の手法は、これまでにも数多くなされている。その中で、等値面生成の技術は、三次元画像の世界では多く使われ議論されてきた。等値面とは、３次元フィールドにおいて同じ値を面で表現することであり、ボクセルデータで定義される三次元関数をＦ（ｘ，ｙ，ｚ）と定数Ｃにより、式（１）を満たす集合を求めることである。
【０００３】
Ｆ（ｘ，ｙ，ｚ）＝Ｃ （１）
このような等値面を用いることにより、解像度の高い三次元画像が高速に取得出来るようになってきた。しかし、等値面生成を行なうと、大量のポリゴンが発生して、ＣＰＵ処理に時間がかかりまた多量のメモリ資源が消費されることから、対話的処理が困難になりやすい。このため、画像データの圧縮技術に対する強い要望がある。
【０００４】
これまでに提案されてきたデータ圧縮手法の中で、ＱＥＭ（ Quadric Error Metrics ）は、局所的に平面に近い点を探すもので、高密度なオリジナルメッシュと簡略後のメッシュとの誤差に関するエネルギー最小問題を２次の評価関数を用いて高速に解くもので、エッジ消去を繰り返すことにより三角形を削減していくものである。速度的には有効であるとされてきたが、ＱＥＭは等値面で生成されたデータを基に削減していく手法であるために、元々ＱＥＭが保持している情報には限界がある。そのため、限界がある中で等値面データを削減することから、元の形状を損なうような削減をしてしまう可能性があった。
【０００５】
【発明が解決しょうとする課題】
従来、ＣＴやＭＲＩで計測した三次元画像データ（ベースデータ）から立体画像を形成する場合には、データの一部を削減して、メモリ使用量を軽減するとともに時間の短縮を図ることが行なわれているが、これまでのデータ圧縮手法では、現実的な処理時間で画像化しようとすると、元画像の劣化がある程度大きくなるのを受容せざるを得ないという問題があった。
【０００６】
またＱＥＭでは、各エッジを順次削減しながら三角形を削減するが、非常に小さい三角形を大量に含む等値面データの場合は、処理時間が長くなるという問題があった。
【０００７】
本発明の課題は、医療や産業用のＣＴやＭＲＩで取得された三次元データからデータ量を抑えて高速に正確な等値面データを作成できるデータ圧縮手段を実現することにある。
【０００８】
【課題を解決するための手段】
小さい三角形を大量に含む等値面データの場合は、従来手法のＱＥＭのようにエッジ単位で削減するよりも、三角形単位で削減した方が効率的である。本発明では、三角形を小さい方から順次選択して削減処理を行ない、等値面が効率的に削減されるようにした。また、削減処理により生じる画像劣化を一定の範囲にとどめるため、誤差の評価を等値面生成に用いたベースデータ上で行なうようにした。従来の手法では、生成された等値面データを元にして削減していたが、本発明では、等値面を削減する際に、等値面生成時のベースデータを参照して誤差を評価し、削減後の定数値を求めることにより、形状の変化を極力抑えながら削減していくことを可能にする。ベースデータとは、等値面を生成する際に必ず必要となる基のデータ（３次元画像、構造格子、非構造格子）である。
【０００９】
等値面削減処理では、データの中心値から一定の幅を許容誤差範囲として設定するとともに、小さい方から順次選択した削除候補の三角形について代表点を求め、その代表点で誤差を評価し、三角形の削除可否判定を行なうようにして効率化を図っている。削減処理では、初期値として、等値面を生成して出来た三角形数に応じて全体の目標削減割合を与え、三角形を小さい方、たとえば面積の小さい方あるいは形の細長い方から順次選択して削減の可否を判定し、目標削減割合に達するまで、削減処理を繰り返す。三角形は、点あるいは線にして削除し、削除した三角形に隣接していた三角形も、それに応じて削除あるいは変形する。図１により、本発明による等値面削除処理の原理を具体的に説明する。
【００１０】
図１の（ａ）は、面積の小さい三角形を点にして削減していく手法である。図中の１は、図示されている等値面（ポリゴン）の中で面積がもっとも小さい三角形であり、最初に削除候補として選択される。また２は、三角形１の代表点であり、たとえば重心点が用いられる。この代表点２の座標をベースデータの対応座標に変換して削減時に生じる誤差を評価する。削減可能である場合には、三角形１を削減して、代表点２に点化するとともに、三角形１の三つの辺にそれぞれ辺で隣接していた他の三つの三角形も同時に削除する。また三角形１の三つの頂点に頂点で接していた他の三角形は、三角形１の代表点２へ拡張するように変形する。最大で４つの三角形を一度に削減することになるため、残った三角形の形状は大きく変化する可能性があり、三角形削減と同時に隣接三角形の情報を更新する。
【００１１】
図１の（ｂ）は、形の細長い三角形を辺にして削減していく手法である。図中の３，４は、形の細長い三角形の例である。細長い三角形は、三角形の辺の長さがもっとも短いものと、次に短い辺の長さとの差で選択され、この差が大きい順に三角形の削減処理を行なう。三角形３に注目すると、削減される三角形３は、もっとも短い辺の長さを零にすることで線になる。このため、削減される三角形３のもっとも短い辺に辺で隣接する他の三角形４も同時に削除され、三角形は一度に最大２つ削減されることとなる。初期値の与え方、連続的な削減処理に関しては、（ａ）の面積の小さい三角形の場合と同様である。
【００１２】
本発明による画像データ圧縮処理方法および画像処理装置は、以下のように構成できる。
（１） 三次元データに基づいて生成した三角形の等値面を削減する画像データ圧縮処理方法において、生成された等値面について、三角形を小さい方から順次取り出して、その三角形を削減した場合に生じる誤差が許容しうるものかどうかを該三角形の代表点を用いて、上記等値面を生成した三次元データ上で判定し、誤差が許容できる場合に該三角形を削除するとともに隣接する関連三角形を削除あるいは変化させる処理を行ない、また誤差が許容できない場合には該三角形を削除せずに、次の順番の三角形を取り出して同様な処理を繰り返すことを特徴とする画像データ圧縮処理方法の構成。
（２） 三角形を取り出す順序は、面積が小さい方あるいは形が細長い方から行なうことを特徴とする前項（１）に記載の画像データ圧縮処理方法の構成。
（３） 三角形を削減した場合に生じる誤差の判定は、等値面の生成に用いたベースデータ上で行なうことを特徴とする前項（１）または（２）に記載の画像データ圧縮処理方法の構成。
（４） 三角形を削減した場合に生じる誤差の判定は、該三角形の代表点として重心点を用い、ベースデータから、該三角形の重心点の座標を含む立方格子体を取り出してその中心位置を補間し、得られた座標が許容誤差内に入るかどうかにより判定することを特徴とする前項（３）に記載の画像データ圧縮処理方法の構成。
（５） 予め等値面の目標削減率を設定しておき、目標削減率に達するまで三角形の削減処理を繰り返すことを特徴とする前項（１）ないし（４）の何れかに記載の画像データ圧縮処理方法の構成。
（６） 三次元データに基づいて三角形の等値面を生成する機能をもつ三次元画像処理装置において、生成された等値面について、三角形を小さい方から順次取り出して、その三角形を削減した場合に生じる誤差が許容しうるものかどうかを該三角形の代表点を用いて、上記等値面を生成した三次元データ上で判定し、誤差が許容できる場合に該三角形を削除するとともに隣接する関連三角形を削除あるいは変化させる処理を行ない、また誤差が許容できない場合には該三角形を削除せずに、次の順番の三角形を取り出して同様な処理を繰り返す等値面削減処理部を備えていることを特徴とする三次元画像処理装置の構成。
（７） 三角形を取り出す順序は、面積が小さい方あるいは形が細長い方から行なうことを特徴とする前項（６）に記載の三次元画像処理装置の構成。
（８） 三角形を削減した場合に生じる誤差の判定は、等値面の生成に用いたベースデータ上で行なうことを特徴とする前項（６）または（７）に記載の三次元画像処理装置の構成。
・ 三角形を削減した場合に生じる誤差の判定は、該三角形の代表点として重心点を用い、ベースデータから、該三角形の重心点の座標を含む立方格子体を取り出してその中心位置を補間し、得られた座標が許容誤差内に入るかどうかにより判定することを特徴とする前項（８）に記載の三次元画像処理装置の構成。
・ 予め等値面の目標削減率を設定しておき、目標削減率に達するまで三角形の削減処理を繰り返すことを特徴とする前項（６）ないし（９）の何れかに記載の三次元画像処理装置の構成。
【００１３】
【作用】
本発明の等値面削減処理は、ベースデータを基本にして行なわれる。等値面の生成処理では、ベースデータを基に等値面（３角形ポリゴン）が生成される。等値面を削減する際にもこのベースデータを使用すれば、正確な情報を得ることが可能となり、従来技術に見られる画像劣化の原因の誤差を無くすことが出来る。誤差が無くなることにより、削減可能な部分とそれ以外の部分とを明確に分けることが可能になる。その結果、削減したにもかかわらず高品質な形状を保持した等値面データが得られる。
【００１４】
【発明の実施の形態】
次に図２ないし図６を用いて、本発明の好適な実施の形態について説明する。
【００１５】
図２は、本発明による画像処理装置の実施例構成を示す。図中、１０はＣＴやＭＲＩなどから取得されたボクセルデータ形式の原三次元画像データ、１１は画像処理装置、１２は原三次元画像データに基づいて等値面を生成する等値面生成部、１３は生成された等値面データ、１４は本発明により等値面削減処理を行なう等値面削減処理部、１５は削減結果の等値面データ、１６は等値面削減処理で用いられる構造格子データおよび非構造格子データと三次元画像データを含むベースデータである。
【００１６】
原三次元画像データ１０に基づいて任意の立体画像表示を行なう場合、等値面生成部１２は、たとえばMarching Cubesによりボクセルデータから立体の構造格子および非構造格子を作成し、三角形の等値面生成を行なう。生成された等値面データ１３は、多量の小さい三角形を含んでいる。等値面データ１３のデータ量を削減する場合、等値面削減処理部１４が起動される。等値面削減処理部１４は、等値面データ１３から削減候補の小さい三角形を順次取り出す削減候補選択処理と、取り出した削減候補三角形の削減により生じる誤差量をベースデータ１６に基づいて評価する誤差判定処理と、誤差量が許容可能かどうかを評価して三角形の削減可否を判定する削減可否判定処理と、三角形の削減により生じた隣接三角形の変更を計算する変更等値面計算処理を行ない、削減結果の等値面データ１５を出力する。
【００１７】
本発明の等値面削減処理については、さらに図３の実施例フローを参照して詳述する。以下、フローのステップ（Ｓ１）〜（Ｓ８）にしたがって、処理内容を順に説明する。なお、小さい三角形の例として、面積の小さい三角形を用いる。（Ｓ１）： 初期値として削減割合を設定する。等値面生成で得られる三角形の数は画像により異なるため、削減数ではなく削減割合を目標にして削減処理を行なうようにする。
（Ｓ２）： 小さい三角形を見つける。小さい三角形としては、図１の（ａ），（ｂ）で述べたように、面積の小さい方あるいは形の細長い方から順に選択する。
（Ｓ３）： 選択した三角形について、等値面データから誤差を判定するための代表点の座標値を求める。代表点は、たとえば三角形の重心点とする。
（Ｓ４）： 図４に示すように、等値面データで求めた三角形の代表点（◎）の座標値を含む立方格子体を、ベースデータの構造格子から探し出す。
（Ｓ５）： ベースデータから取り出した立方格子体により座標値を線形補間する。ベースデータは整数座標値（立方格子体の格子点座標）しか値を持っていないため、計算した代表点（◎）の座標値が整数座標値でないときには、図４のように立方格子体上で線形補間により求める。
（Ｓ６）： 三角形の削減可否を判定する。図４において、Ｃは等値面をとった時の座標値であり、ｅは削減可能幅である。代表点（◎）の座標値が、削減可能幅内に入るかどうかを比較する。座標値Ｃが、削減可能幅から外れるときは、その三角形の削減をやめて（Ｓ２）へ戻り、つぎの小さい三角形を探し出して、同様に削減処理を繰り返す。
（Ｓ７）： 代表点（◎）の座標値が、削減可能幅内に入ったときは、その三角形を削減して点にする。同時に、隣接する三角形の削除、変形を行ない、関連する各三角形の定数を再計算する。
（Ｓ８）： 三角形を削減した結果として、目標の削減割合が達成されたかどうかを判定する。目標の削減割合が達成された場合は削減処理を終了し、まだ達成されないばあいは、（Ｓ２）へ戻り、つぎの小さい三角形を探し出して、同様に削減処理を繰り返す。
【００１８】
図５は、具体例を用いて削減するかどうかの判定の様子を示したものである。case１では、×印がついた点を削減する。case２では、その後に出来る形状で◎の点を、ベースデータを用いて判定する。この場合、判定点は削減可能幅内に含まれており、形状の変化はあまりないとみなして、小さい×印が付いている点は削減されることになる。case３では、小さい×印が削減された時の形状の変化を、同様に◎の点で判定している。この場合削減可能幅の外にあり、×印の点を削減することによって起こる形状の変化が大きいとみなし、×印の点は削減しないことになる。
【００１９】
図６は、上記（Ｓ７）で三角形の削減が行なわれたとき、削減、変更が必要な三角形の範囲を示す。図の左側のポリゴンの中央の三角形が、削減される三角形であり、その各辺に隣接しているドットパターンの三つの三角形は、付随して削減される三角形である。図６の右側のポリゴン中のドットパターンを付された八つの三角形は、三角形の削減の結果、定数値を再計算する必要のある三角形である。
【００２０】
図６に示すように、小さい三角形が削減されることにより、周りの三角形の位置や形状が変わってくる。それらの変形した三角形の重心の定数値は、等値面で生成したときの定数値とは異なっている。この定数値が大きく外れているときは、小さな三角形でも削除によって形状が大きく変化するので、これを繰り返していくと、元の形状データとはかけ離れたものになってしまう。逆に、定数値が等値面を生成したときの定数値とほとんど差がないときには、その三角形を削減しても形状の変化は最小限に抑えられる。この三角形の重心の定数値を求めるときに、ベースデータを使用する。ベースデータには、等値面を生成するために必要な定数値が入っている。しかし、このベースデータは整数座標値しか値を持っていないため、計算した座標値が整数座標値でないときには、線形補間により求める必要がある。具体的には、格子空間として計算するため、その点を含む８点の定数値を使用しまた８点からの距離の比を用いることにより、正確な定数値を求める。線形補間により求めた値が、等値面をとった時の定数値と比較して削減可能幅内であれば、重心をとった三角形を点にする。逆に削減可能幅外の場合は、形状が大きく変化してしまう可能性があるため、三角形を点にする処理をせずに次の小さい三角形を探し出す処理へと進む。また、さらに精度を上げるため、三角形の線分長を基準として決め、線分長が長くなってきた場合には比較する点を増やしていく。削減可能幅は、式（２）により求める。式（２）のｅは削減可能幅、Ｃｍａｘ、Ｃｍｉｎはそれぞれ定数Ｃの最大値、最小値である。ｘは割合であり、５％の削減可能幅にしたいときはｘ＝０．０５を代入する。
【００２１】
ｅ＝（（Ｃｍａｘ）−（Ｃｍｉｎ））＊ｘ （２）
図７は、削減可能幅を変化させたときのポリゴン削減率の変化を示している。データは、Ｆｅｍ１２８．ｖo１という人間の大腿骨のデータを使用した。削減可能幅の違いによるポリゴン削減率の変化を示している。凡例部分の等値面数は、削減処理を行っていない標準状態での等値面数を示している。またＣ＝１９９６とは、このデータでのＣの中心値である。
【００２２】
削減可能幅が小さければ、それだけ削減される三角形は少なくなり、逆に削減可能幅を大きくすればするだけ、削減率も比例して大きくなっていくことがわかる、データにより削減可能幅を見極めていくことが必要である。
【００２３】
図８〜図１０は、人間の大腿骨のデータを用いて行なった等値面削減実験の結果の画像例である。図８はＣ＝５００のもの、図９および図１０はＣ＝３００のものである。
【００２４】
図８（ａ）は、削減処理を行わずに等値面をとった標準時のものであり、等値面数は６９４４８ある。図８（ｂ）は、ポリゴン削減率９０％を与えて削減したもので、等値面数は、７６０５となる。図８（c ）は、ポリゴン削減率を９０％とし、さらに削減可能幅５％を与えた時のものであり、等値面数は、５２０８５となる。図９（ａ）は、小さい三角形をランダムに３０％削減したものである。図９（ｂ）は、削減可能幅５％を与えて３０％削減したときのものであり、等値面数は、４６９２６となる。図１０（ａ）は、標準時の画像である。図１０（ｂ）は、小さい三角形をランダムに３０％削減した画像である。図１０（ｃ）は、削減可能幅５％を用いてランダムに３０％削減したものである。削減可能幅を用いたものは、細かな筋に関しても無くすことなく削減できていることがわかる。
【００２５】
【発明の効果】
本発明によれば、医療や産業用のＣＴやＭＲＩで取得された三次元データに基づく三角形の等値面データについて、任意に設定された削減率に応じて、削減しても精度にあまり支障が生じないように元の三次元データで検証しつつ、小さい三角形を選択して削減するため、データ量の任意の削減に対応して常に最良の精度で等値面データを生成することができる。このため、三次元画像処理において、必要に応じて少ないデータ量の等値面を用いながら、正確な画像を高速に作成し、処理することができる。
【図面の簡単な説明】
【図１】 本発明による等値面削減処理の原理説明図である。
【図２】 本発明による画像処理装置の実施例構成図である。
【図３】 本発明による等値面削減処理の実施例フロー図である。
【図４】 等値面データで求めた三角形の代表点（◎）の座標値を含む立方格子体の説明図である。
【図５】 具体例を用いて削減するかどうかの判定の様子を示す説明図である。
【図６】 三角形の削減が行なわれたとき、削減、変更が必要な三角形の範囲を例示する説明図である。
【図７】 削減可能幅を変化させたときのポリゴン削減率の変化を示すグラフである。
【図８】 人間の大腿骨のデータを用いて行なった等値面削減実験の結果の画像例（その１）である。
【図９】 人間の大腿骨のデータを用いて行なった等値面削減実験の結果の画像例（その２）である。
【図１０】 人間の大腿骨のデータを用いて行なった等値面削減実験の結果の画像例（その３）である。
【符号の説明】
１０：ＣＴやＭＲＩなどから取得された原三次元画像データ
１１：画像処理装置
１２：原三次元画像データに基づいて等値面を生成する等値面生成部
１３：生成された等値面データ
１４：本発明により等値面削減処理を行なう等値面削減処理部
１５：削減結果の等値面データ
１６：等値面削減処理で用いられる構造格子データおよび非構造格子データと三次元画像データを含むベースデータ
Claims (10)
- 三次元データに基づいて生成した三角形の等値面を削減する画像データ圧縮処理方法において、生成された等値面について、三角形を小さい方から順次取り出して、その三角形を削減した場合に生じる誤差が許容しうるものかどうかを該三角形の代表点を用いて、上記等値面を生成した三次元データ上で判定し、誤差が許容できる場合に該三角形を削除するとともに隣接する関連三角形を削除あるいは変化させる処理を行ない、また誤差が許容できない場合には該三角形を削除せずに、次の順番の三角形を取り出して同様な処理を繰り返すことを特徴とする画像データ圧縮処理方法。
- 三角形を取り出す順序は、面積が小さい方あるいは形が細長い方から行なうことを特徴とする請求項１に記載の画像データ圧縮処理方法。
- 三角形を削減した場合に生じる誤差の判定は、等値面の生成に用いたベースデータ上で行なうことを特徴とする請求項１または請求項２に記載の画像データ圧縮処理方法。
- 三角形を削減した場合に生じる誤差の判定は、該三角形の代表点として重心点を用い、ベースデータから、該三角形の重心点の座標を含む立方格子体を取り出してその中心位置を補間し、得られた座標が許容誤差内に入るかどうかにより判定することを特徴とする請求項３に記載の画像データ圧縮処理方法。
- 予め等値面の目標削減率を設定しておき、目標削減率に達するまで三角形の削減処理を繰り返すことを特徴とする請求項１ないし請求項４の何れかに記載の画像データ圧縮処理方法。
- 三次元データに基づいて三角形の等値面を生成する機能をもつ三次元画像処理装置において、生成された等値面について、三角形を小さい方から順次取り出して、その三角形を削減した場合に生じる誤差が許容しうるものかどうかを該三角形の代表点を用いて、上記等値面を生成した三次元データ上で判定し、誤差が許容できる場合に該三角形を削除するとともに隣接する関連三角形を削除あるいは変化させる処理を行ない、また誤差が許容できない場合には該三角形を削除せずに、次の順番の三角形を取り出して同様な処理を繰り返す等値面削減処理部を備えていることを特徴とする三次元画像処理装置。
- 三角形を取り出す順序は、面積が小さい方あるいは形が細長い方から行なうことを特徴とする請求項６に記載の三次元画像処理装置。
- 三角形を削減した場合に生じる誤差の判定は、等値面の生成に用いたベースデータ上で行なうことを特徴とする請求項６または請求項７に記載の三次元画像処理装置。
- 三角形を削減した場合に生じる誤差の判定は、該三角形の代表点として重心点を用い、ベースデータから、該三角形の重心点の座標を含む立方格子体を取り出してその中心位置を補間し、得られた座標が許容誤差内に入るかどうかにより判定することを特徴とする請求項８に記載の三次元画像処理装置。
- 予め等値面の目標削減率を設定しておき、目標削減率に達するまで三角形の削減処理を繰り返すことを特徴とする請求項６ないし請求項９の何れかに記載の三次元画像処理装置。
Priority Applications (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2002128748A JP3967626B2 (ja) | 2002-04-30 | 2002-04-30 | 画像データ圧縮処理方法および画像処理装置 |
| PCT/JP2003/005427 WO2003094117A1 (fr) | 2002-04-30 | 2003-04-28 | Procede de compression de donnees image et dispositif de traitement d'image |
| US10/512,250 US20050219237A1 (en) | 2002-04-30 | 2003-04-28 | Image data compression method and image processing device |
| EP03725690A EP1510974A1 (en) | 2002-04-30 | 2003-04-28 | Image data compression method and image processing device |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2002128748A JP3967626B2 (ja) | 2002-04-30 | 2002-04-30 | 画像データ圧縮処理方法および画像処理装置 |
Publications (3)
| Publication Number | Publication Date |
|---|---|
| JP2003323637A JP2003323637A (ja) | 2003-11-14 |
| JP2003323637A5 JP2003323637A5 (ja) | 2005-05-26 |
| JP3967626B2 true JP3967626B2 (ja) | 2007-08-29 |
Family
ID=29397278
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2002128748A Expired - Fee Related JP3967626B2 (ja) | 2002-04-30 | 2002-04-30 | 画像データ圧縮処理方法および画像処理装置 |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US20050219237A1 (ja) |
| EP (1) | EP1510974A1 (ja) |
| JP (1) | JP3967626B2 (ja) |
| WO (1) | WO2003094117A1 (ja) |
Families Citing this family (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP4959358B2 (ja) * | 2007-02-01 | 2012-06-20 | 東芝Ｉｔコントロールシステム株式会社 | Ｍｐｒ表示装置及びコンピュータ断層撮影装置 |
| JP2010117991A (ja) * | 2008-11-14 | 2010-05-27 | Chubu Electric Power Co Inc | 画像処理方法、そのプログラム及び画像処理装置 |
| JP6613727B2 (ja) * | 2015-08-28 | 2019-12-04 | 大日本印刷株式会社 | 立体物造形用データ削減装置 |
| JP6748368B2 (ja) | 2017-01-18 | 2020-09-02 | 富士通株式会社 | モデリング装置、モデリング方法、およびモデリングプログラム |
| US11797543B2 (en) * | 2018-12-20 | 2023-10-24 | Microsoft Technology Licensing, Llc | System and method for cascade elimination of candidates in spatial relation operations |
| CN110796693B (zh) * | 2019-09-11 | 2023-03-21 | 重庆大学 | 一种工业ct切片图像直接生成二维有限元模型的方法 |
Family Cites Families (14)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5590248A (en) * | 1992-01-02 | 1996-12-31 | General Electric Company | Method for reducing the complexity of a polygonal mesh |
| JPH06231276A (ja) * | 1993-01-29 | 1994-08-19 | Nippon Steel Corp | ３次元物体表示のためのポリゴン生成方法 |
| JP3340198B2 (ja) * | 1993-08-12 | 2002-11-05 | 株式会社東芝 | 形状復元装置 |
| JP2583009B2 (ja) * | 1993-12-16 | 1997-02-19 | インターナショナル・ビジネス・マシーンズ・コーポレイション | 可視化データ生成方法及び装置 |
| JP3514822B2 (ja) * | 1994-06-29 | 2004-03-31 | 株式会社東芝 | 画像処理装置 |
| JP3199231B2 (ja) * | 1997-05-27 | 2001-08-13 | 日本アイ・ビー・エム株式会社 | ３次元形状モデルへの情報の埋め込み方法及びシステム |
| US6262737B1 (en) * | 1998-01-30 | 2001-07-17 | University Of Southern California | 3D mesh compression and coding |
| JP2000067270A (ja) * | 1998-06-12 | 2000-03-03 | Sony Corp | 形状デ―タの近似化方法及び情報処理装置並びに媒体 |
| EP1194860A2 (en) * | 1999-01-27 | 2002-04-10 | Enbaya Inc. | Progressive compression of triangular meshes |
| GB9929957D0 (en) * | 1999-12-17 | 2000-02-09 | Canon Kk | Image processing apparatus |
| JP4192377B2 (ja) * | 1999-12-27 | 2008-12-10 | コニカミノルタセンシング株式会社 | 三次元形状データのデータ削減方法及びデータ削減装置 |
| US6958753B2 (en) * | 1999-12-27 | 2005-10-25 | Minolta Co., Ltd. | Method and apparatus for reducing three-dimensional shape data |
| JP3690501B2 (ja) * | 2001-02-26 | 2005-08-31 | トヨタ自動車株式会社 | ３次元モデル化方法 |
| JP2002342785A (ja) * | 2001-05-15 | 2002-11-29 | Ricoh Co Ltd | 三角形メッシュ簡単化装置およびプログラム |
-
2002
- 2002-04-30 JP JP2002128748A patent/JP3967626B2/ja not_active Expired - Fee Related
-
2003
- 2003-04-28 US US10/512,250 patent/US20050219237A1/en not_active Abandoned
- 2003-04-28 WO PCT/JP2003/005427 patent/WO2003094117A1/ja not_active Application Discontinuation
- 2003-04-28 EP EP03725690A patent/EP1510974A1/en not_active Withdrawn
Also Published As
| Publication number | Publication date |
|---|---|
| US20050219237A1 (en) | 2005-10-06 |
| EP1510974A1 (en) | 2005-03-02 |
| WO2003094117A1 (fr) | 2003-11-13 |
| JP2003323637A (ja) | 2003-11-14 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Xia et al. | Dynamic view-dependent simplification for polygonal models | |
| Gieng et al. | Constructing hierarchies for triangle meshes | |
| Gregory et al. | Interactive surface decomposition for polyhedral morphing | |
| Di Angelo et al. | A new mesh-growing algorithm for fast surface reconstruction | |
| US20050052452A1 (en) | 3D computer surface model generation | |
| Ruprecht et al. | Spatial free-form deformation with scattered data interpolation methods | |
| GB2378337A (en) | 3D computer modelling apparatus | |
| JP2002501639A (ja) | プログレッシブメッシュの適応細分方法および装置 | |
| Bronson et al. | Lattice cleaving: A multimaterial tetrahedral meshing algorithm with guarantees | |
| US6781582B1 (en) | Mesh generator for and method of generating meshes in an extrusion process | |
| JP4252138B2 (ja) | ２進コード化データとして記憶されているオブジェクトの表面の滑らかな表面表現を生成するためのコンピュータで実行される方法 | |
| KR101592294B1 (ko) | 복잡한 3차원 폴리곤 메쉬 데이터의 단순화 방법 | |
| JP3967626B2 (ja) | 画像データ圧縮処理方法および画像処理装置 | |
| CN109983509B (zh) | 一种使用几何面的即时布尔运算方法 | |
| Bajaj et al. | Tetrahedral meshes from planar cross-sections | |
| JP2003323637A5 (ja) | ||
| Wu et al. | An Accurate Error Measure for Adaptive Subdivision Surfaces. | |
| Lee | Automatic metric 3D surface mesh generation using subdivision surface geometrical model. Part 1: Construction of underlying geometrical model | |
| Kaye et al. | Strategies for evaluating boundary fractal dimensions by computer aided image analysis | |
| JP2006059061A (ja) | ３次元データ処理方法、装置及びプログラム | |
| JP2007102595A (ja) | 解析メッシュ生成装置 | |
| Jou et al. | A fast 3D seed-filling algorithm | |
| Yang et al. | Efficient simplification of large vector maps rendered onto 3D landscapes | |
| Boldt et al. | Selfintersections with cullide | |
| Kim et al. | Polygon reduction of 3D objects using Stokes’ theorem |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| RD03 | Notification of appointment of power of attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7423 Effective date: 20040210 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20040722 |
|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20040722 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20070227 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20070501 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20070529 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20070531 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110608 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120608 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130608 Year of fee payment: 6 |
|
| LAPS | Cancellation because of no payment of annual fees |