(57)【要約】【課題】  用途に応じた精度の法線ベクトルデータを提供可能な技術を提供すること。【解決手段】  三次元形状モデルを構成する複数の多角形を符号化する符号化装置であって、複数の多角形のうち第１の多角形の法線ベクトルに基づいて、該第１の多角形の表裏を判定し、該判定された結果を符号化する。【選択図】  図１
2017191574.tif 000002
【特許請求の範囲】
【請求項１】
三次元形状モデルを構成する複数の多角形を符号化する符号化装置であって、
前記複数の多角形のうち第１の多角形の法線ベクトルに基づいて、該第１の多角形の表裏を判定する判定手段と、
前記判定手段によって判定された結果を符号化する符号化手段と
を備えることを特徴とする符号化装置。
【請求項２】
三次元形状モデルを構成する複数の多角形を符号化する符号化装置であって、
前記複数の多角形のうち第１の多角形の法線ベクトルに基づいて、該第１の多角形の表裏を判定する判定手段と、
前記第１の多角形と隣接している第２の多角形に対して前記判定手段が既に行った表裏判定の結果と、前記第１の多角形に対する前記判定手段による表裏判定結果と、が一致しているか否かを表す情報を符号化する符号化手段と
を備えることを特徴とする符号化装置。
【請求項３】
更に、
前記第１の多角形における一辺に沿ったベクトルと、該一辺と一端を共有する他辺に沿ったベクトルと、の外積により該第１の多角形の予測法線ベクトルを求め、該予測法線ベクトルと該第１の多角形の法線ベクトルとの差分を符号化する第２の符号化手段を有することを特徴とする請求項１又は２に記載の符号化装置。
【請求項４】
前記第２の符号化手段は、前記第１の多角形に対する前記判定手段による表裏判定の結果に応じて、前記予測法線ベクトルの方向を反転させることを特徴とする請求項３に記載の符号化装置。
【請求項５】
前記差分は、前記予測法線ベクトルと前記第１の多角形の法線ベクトルとの各軸方向の成分値の差分であることを特徴とする請求項３又は４に記載の符号化装置。
【請求項６】
前記差分は、前記予測法線ベクトル及び前記第１の多角形に対する前記第１の多角形の法線ベクトルの角度情報であることを特徴とする請求項３又は４に記載の符号化装置。
【請求項７】
前記判定手段は、前記第１の多角形における一辺に沿ったベクトルと、該一辺と一端を共有する他辺に沿ったベクトルと、の外積を計算し、該外積の結果と、前記第１の多角形の法線ベクトルと、の内積結果に基づいて、前記第１の多角形の表裏判定を行うことを特徴とする請求項１乃至６の何れか１項に記載の符号化装置。
【請求項８】
請求項２に記載の符号化装置の前記符号化手段によって符号化された情報を復号する復号手段と、
前記第１の多角形における一辺に沿ったベクトルと、該一辺と一端を共有する他辺に沿ったベクトルと、の外積により該第１の多角形の予測法線ベクトルを求め、該予測法線ベクトルと、前記復号手段が復号した情報が表す前記第１の多角形の表裏判定の結果と、に応じて、前記第１の多角形の法線ベクトルを決定する決定手段と
を備えることを特徴とする復号装置。
【請求項９】
請求項３に記載の符号化装置の前記符号化手段によって符号化された情報を復号する第１の復号手段と、
前記第２の符号化手段によって符号化された前記差分を復号する第２の復号手段と、
前記第１の多角形における一辺に沿ったベクトルと、該一辺と一端を共有する他辺に沿ったベクトルと、の外積により該第１の多角形の予測法線ベクトルを求め、該予測法線ベクトルと、前記第１の復号手段が復号した情報が表す前記第１の多角形の表裏判定の結果と、前記第２の復号手段が復号した前記差分と、に応じて、前記第１の多角形の法線ベクトルを決定する決定手段と
を備えることを特徴とする復号装置。
【請求項１０】
三次元形状モデルを構成する複数の多角形を符号化する符号化装置が行う符号化方法であって、
前記符号化装置の判定手段が、前記複数の多角形のうち第１の多角形の法線ベクトルに基づいて、該第１の多角形の表裏を判定する判定工程と、
前記符号化装置の符号化手段が、前記判定工程で判定された結果を符号化する符号化工程と
を備えることを特徴とする符号化方法。
【請求項１１】
三次元形状モデルを構成する複数の多角形を符号化する符号化装置が行う符号化方法であって、
前記符号化装置の判定手段が、前記複数の多角形のうち第１の多角形の法線ベクトルに基づいて、該第１の多角形の表裏を判定する判定工程と、
前記符号化装置の符号化手段が、前記第１の多角形と隣接している第２の多角形に対して前記判定工程で既に行った表裏判定の結果と、前記第１の多角形に対する前記判定工程による表裏判定結果と、が一致しているか否かを表す情報を符号化する符号化工程と
を備えることを特徴とする符号化方法。
【請求項１２】
更に、
前記符号化装置の第２の符号化手段が、前記第１の多角形における一辺に沿ったベクトルと、該一辺と一端を共有する他辺に沿ったベクトルと、の外積により該第１の多角形の予測法線ベクトルを求め、該予測法線ベクトルと該第１の多角形の法線ベクトルとの差分を符号化する第２の符号化工程を有することを特徴とする請求項１０又は１１に記載の符号化方法。
【請求項１３】
復号装置が行う復号方法であって、
前記復号装置の復号手段が、請求項１１に記載の符号化方法における前記符号化工程で符号化された情報を復号する復号工程と、
前記復号装置の決定手段が、前記第１の多角形における一辺に沿ったベクトルと、該一辺と一端を共有する他辺に沿ったベクトルと、の外積により該第１の多角形の予測法線ベクトルを求め、該予測法線ベクトルと、前記復号工程で復号した情報が表す前記第１の多角形の表裏判定の結果と、に応じて、前記第１の多角形の法線ベクトルを決定する決定工程と
を備えることを特徴とする復号方法。
【請求項１４】
復号装置が行う復号方法であって、
前記復号装置の第１の復号手段が、請求項１２に記載の符号化方法における前記符号化工程で符号化された情報を復号する第１の復号工程と、
前記復号装置の第２の復号手段が、前記第２の符号化工程で符号化された前記差分を復号する第２の復号工程と、
前記復号装置の決定手段が、前記第１の多角形における一辺に沿ったベクトルと、該一辺と一端を共有する他辺に沿ったベクトルと、の外積により該第１の多角形の予測法線ベクトルを求め、該予測法線ベクトルと、前記第１の復号工程で復号した情報が表す前記第１の多角形の表裏判定の結果と、前記第２の復号工程で復号した前記差分と、に応じて、前記第１の多角形の法線ベクトルを決定する決定工程と
を備えることを特徴とする復号方法。
【請求項１５】
コンピュータを、請求項１乃至７の何れか１項に記載の符号化装置の各手段として機能させるためのコンピュータプログラム。
【請求項１６】
コンピュータを、請求項８又は９に記載の復号装置の各手段として機能させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、三次元形状モデルにおける法線ベクトルの符号化、復号技術に関するものである。
【背景技術】
【０００２】
三次元形状を表すための代表的なデータとして、例えば、頂点、頂点間のリンク、法線ベクトルがある。頂点とリンクによって面が構成され、法線ベクトルは、頂点に付加される場合と面に付加される場合とがある。三次元形状の法線ベクトルのｘ方向、ｙ方向、ｚ方向のそれぞれの方向成分は浮動小数で表現される。法線ベクトルの符号化として、法線ベクトルをクラスタリングし、代表ベクトルと、その予測残差を符号化する方法が開示されている（例えば、特許文献１）。また浮動小数の符号化として、符号化対象と予測値それぞれを符号部、指数部、仮数部に分離し、各部で整数として差分を取って可逆符号化する方法が開示されている（例えば、非特許文献１）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第５５１２８２７号
【非特許文献】
【０００４】
【非特許文献１】Ｍａｒｔｉｎ  Ｉｓｅｎｂｕｒｇ，Ｐｅｔｅｒ  Ｌｉｎｄｓｔｒｏｍ，Ｊａｃｋ  Ｓｎｏｅｙｉｎｋ，“Ｌｏｓｓｌｅｓｓ  ｃｏｍｐｒｅｓｓｉｏｎ  ｏｆ  ｐｒｅｄｉｃｔｅｄ  ｆｌｏａｔｉｎｇ−ｐｏｉｎｔ  ｇｅｏｍｅｔｒｙ．”Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｄｅｓｉｇｎ，Ｖｏｌｕｍｅ３７，Ｉｓｓｕｅ８，ｐａｇｅｓ８６９−８７７，２００５．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
例えば、三次元形状モデルを３Ｄプリンタで出力するために該３Ｄプリンタに入力するデータ（三次元形状モデルデータ）には、高精度の法線ベクトルデータは必要はなく、むしろ、各面の表裏情報が必要になる。このように、アプリケーションによっては、法線ベクトルデータにどの程度の精度が要求されるのかが異なる。
【０００６】
本発明はこのような問題に鑑みてなされたものであり、用途に応じた精度の法線ベクトルデータを提供可能な技術を提供する。
【課題を解決するための手段】
【０００７】
本発明の一様態は、三次元形状モデルを構成する複数の多角形を符号化する符号化装置であって、前記複数の多角形のうち第１の多角形の法線ベクトルに基づいて、該第１の多角形の表裏を判定する判定手段と、前記判定手段によって判定された結果を符号化する符号化手段とを備えることを特徴とする。
【発明の効果】
【０００８】
本発明の構成によれば、用途に応じた精度の法線ベクトルデータを提供することができる。
【図面の簡単な説明】
【０００９】
【図１】符号化装置の機能構成例を示すブロック図。
【図２】符号化部１０２が行う符号化処理のフローチャート。
【図３】３次元形状モデルの一例を示す図。
【図４】符号データの構成例を示す図。
【図５】復号装置の機能構成例を示すブロック図。
【図６】第１の復号モードにおける復号処理のフローチャート。
【図７】第２の復号モードにおける復号処理のフローチャート。
【図８】コンピュータのハードウェア構成例を示すブロック図。
【図９】符号化装置の機能構成例を示すブロック図。
【図１０】符号化部９０２が行う符号化処理のフローチャート。
【図１１】第２の実施形態を説明する図。
【発明を実施するための形態】
【００１０】
以下、添付図面を参照し、本発明の実施形態について説明する。なお、以下説明する実施形態は、本発明を具体的に実施した場合の一例を示すもので、特許請求の範囲に記載した構成の具体的な実施例の１つである。
【００１１】
［第１の実施形態］
本実施形態では、各面に法線ベクトルが割り当てられている三次元形状モデルにおいて、法線ベクトルを階層的に符号化する符号化装置について説明する。この符号化装置は、三次元形状モデルを構成する複数の多角形を符号化する符号化装置であって、次のような構成の一例として説明するものである。すなわち、複数の多角形のうち第１の多角形の法線ベクトルに基づいて、該第１の多角形の表裏を判定する。そして、第１の多角形と隣接している第２の多角形に対して既に行った表裏判定の結果と、第１の多角形に対する表裏判定結果と、が一致しているか否かを表す情報を符号化する。更に、第１の多角形における一辺に沿ったベクトルと、該一辺と一端を共有する他辺に沿ったベクトルと、の外積により該第１の多角形の予測法線ベクトルを求め、該予測法線ベクトルと該第１の多角形の法線ベクトルとの差分を符号化する（第２の符号化）。先ず、本実施形態に係る符号化装置の機能構成例について、図１のブロック図を用いて説明する。
【００１２】
入力部１０１には、三次元形状モデルを構成する各面に対応する法線ベクトル（単位ベクトル）のデータ（法線ベクトルデータ）が入力される。本実施形態では、法線ベクトルデータは、法線ベクトルのＸ軸方向の成分値、Ｙ軸方向の成分値、Ｚ軸方向の成分値のそれぞれが３２ビットの浮動小数値で表されたデータであるものとする。しかし、法線ベクトルの表現方法や、各軸方向の成分値を表現するデータのフォーマットについてはこれに限るものではない。
【００１３】
符号化部１０２は、入力部１０１が入力した法線ベクトルデータを用いて、三次元形状モデルを構成する各面の法線ベクトルを階層的に符号化する。本実施形態では、三次元形状モデルにおける各面を符号化する際に、該面に対応する法線ベクトルも符号化する。各面の符号化については周知の符号化技術でもって符号化すればよく、法線ベクトルの符号化処理については、図２のフローチャートに従って行う。符号化部１０２が行う法線ベクトルの符号化処理について、図２のフローチャートに従って説明する。
【００１４】
ステップＳ２０１では、判定部１０４は、三次元形状モデルを構成する全ての面の符号化が完了したか否か、換言すれば、三次元形状モデルを構成する全ての面に対応する法線ベクトルの符号化が完了したか否かを判断する。この判断の結果、未だ符号化していない法線ベクトルが残っている場合には、処理はステップＳ２０２に進み、全ての法線ベクトルの符号化が完了した場合には、図２のフローチャートに従った処理は終了する。
【００１５】
ステップＳ２０２では、判定部１０４は、未だ符号化していない法線ベクトルのうちの１つを対象法線ベクトルとして選択する。以下では、三次元形状モデルにおいて対象法線ベクトルに対応する面を着目面と呼称する。すなわち、ステップＳ２０２では、三次元形状モデルを構成する全ての面のうち着目面を以下の処理の対象として設定したことになる。
【００１６】
ステップＳ２０３では、判定部１０４は、対象法線ベクトルの方向、すなわち、着目面の法線ベクトル方向が、該着目面の表面方向であるのか、それとも裏面方向であるのかを判定し、該判定結果を示す情報を表裏情報として生成する。ステップＳ２０３における判定部１０４の動作を説明するために、図３を例にとって説明する。図３には、頂点ｖ１を共有する３つの面（ｆ１，ｆ２，ｆ３）を示している。面ｆ１は３つの頂点ｖ１，ｖ２，ｖ３を有している。ｎ１は面ｆ１に対応する法線ベクトルデータが表す法線ベクトルである。面ｆ２は３つの頂点ｖ１，ｖ３，ｖ４を有している。ｎ２は面ｆ２に対応する法線ベクトルデータが表す法線ベクトルである。面ｆ３は３つの頂点ｖ１，ｖ４，ｖ５を有している。ｎ３は面ｆ３に対応する法線ベクトルデータが表す法線ベクトルである。頂点ｖ１〜ｖ５に係るデータ（頂点のインデックスや座標位置等）は三次元形状モデルのデータに含まれている。
【００１７】
以下では、頂点ｖ１を共有する各面（ｆ１〜ｆ３）及び対応する法線ベクトル（ｎ１〜ｎ３）の符号化において、面ｆ１及び法線ベクトルｎ１の符号化が完了して、これから面ｆ２及び法線ベクトルｎ２を符号化する場合について説明する。なお、頂点ｖ１を共有する各面及び対応する法線ベクトルの符号化が完了すると、次に、頂点ｖ１以外の頂点について、該頂点を共有する面及び法線ベクトルを符号化する。上記の通り、面の符号化については従来技術であるため説明は省略し、以下では、法線ベクトルの符号化について重点的に説明する。
【００１８】
判定部１０４は先ず、面ｆ２において頂点ｖ１を一端とする一方の辺に沿ったベクトル、すなわち、頂点ｖ１から頂点ｖ３に向かうベクトルｗ２を求める。更に判定部１０４は、面ｆ２において頂点ｖ１を一端とする他方の辺に沿ったベクトル、すなわち、頂点ｖ１から頂点ｖ４に向かうベクトルｗ３を求める。そして判定部１０４は、ベクトルｗ２とベクトルｗ３との外積（ｗ２×ｗ３）を求め、該外積の結果得られるベクトルを長さ１に正規化したベクトルｐ２を求める。そして判定部１０４は、ベクトルｐ２と法線ベクトルｎ２との内積を算出する。ｐ２、ｎ２は共に長さ１のベクトルであり、これらの内積結果は、ｐ２とｎ２の成す角をθとした時に、ｐ２・ｎ２＝ｃｏｓθを満たす。内積ｃｏｓθが０以上のとき、判定部１０４は法線ベクトルｎ２の方向が、面ｆ２の表面の方向であると判断し、面ｆ２に対する表裏情報ＢＮ２として０を出力する。一方、内積ｃｏｓθが０未満のとき、判定部１０４は法線ベクトルｎ２の方向が、面ｆ２の裏面の方向であると判断し、面ｆ２に対する表裏情報ＢＮ２として１を出力する。
【００１９】
なお、上記の通り、法線ベクトルｎ２の符号化に先んじて法線ベクトルｎ１に対する符号化は完了しており、法線ベクトルｎ１に対するステップＳ２０３の処理は以下の通りである。すなわち、判定部１０４は先ず、面ｆ１において頂点ｖ１を一端とする一方の辺に沿ったベクトル、すなわち、頂点ｖ１から頂点ｖ２に向かうベクトルｗ１を求める。更に判定部１０４は、面ｆ１において頂点ｖ１を一端とする他方の辺に沿ったベクトル、すなわち、頂点ｖ１から頂点ｖ３に向かうベクトルｗ２を求める。そして判定部１０４は、ベクトルｗ１とベクトルｗ２との外積（ｗ１×ｗ２）を求め、該外積の結果得られるベクトルを長さ１に正規化したベクトルｐ１を求める。そして判定部１０４は、ベクトルｐ１と法線ベクトルｎ１との内積を算出する。ｐ１、ｎ１は共に長さ１のベクトルであり、これらの内積結果は、ｐ１とｎ１の成す角をθとした時に、ｐ１・ｎ１＝ｃｏｓθを満たす。内積ｃｏｓθが０以上のとき、判定部１０４は法線ベクトルｎ１の方向が、面ｆ１の表面の方向であると判断し、面ｆ１に対する表裏情報ＢＮ１として０を出力する。一方、内積ｃｏｓθが０未満のとき、判定部１０４は法線ベクトルｎ１の方向が、面ｆ１の裏面の方向であると判断し、面ｆ１に対する表裏情報ＢＮ１として１を出力する。
【００２０】
このように、面ごとにステップＳ２０３の処理を行うことで、該面の法線ベクトルの方向が表面の方向であるのか、それとも裏面の方向であるのかを示す表裏情報を生成することができる。
【００２１】
図２に戻って次に、ステップＳ２０４で判定部１０４は、着目面の直前に符号化された面についてステップＳ２０３で生成した表裏情報と、着目面についてステップＳ２０３で生成した表裏情報と、の差分の絶対値を、着目面の表裏判定情報として算出する。図３の例では、ステップＳ２０３において面ｆ２の表裏情報ＢＮ２を算出すると、直後のステップＳ２０４では、面ｆ１の表裏情報ＢＮ１と表裏情報ＢＮ２との差分の絶対値を、面ｆ２の表裏判定情報として算出する。ＢＮ１＝ＢＮ２であれば、表裏判定情報＝０となり、ＢＮ１≠ＢＮ２であれば、表裏判定情報＝１となる。なお、着目面の直前に符号化された面が存在しない場合（図３の例では着目面が面ｆ１の場合）、着目面の表裏情報を該着目面の表裏判定情報とする。
【００２２】
ステップＳ２０３で算出される表裏情報は、頂点ｖ１に相当する回転軸となる頂点を共有する場合には高い相関もつため、ステップＳ２０４で隣接する面の表裏情報の差分の絶対値を算出すると、同一の値を有する表裏判定情報を連続して出力する可能性が高い。然るにこのような表裏判定情報の符号化は、高い圧縮率の符号化となる。
【００２３】
ステップＳ２０５の処理は、頂点を共有するそれぞれの面（図３の例では面ｆ１〜ｆ３）の表裏判定情報が得られた時点で行われる処理であり、符号化部１０５は、頂点を共有するそれぞれの面の表裏判定情報をエントロピー符号化する。具体的には、頂点を共有するそれぞれの面の表裏判定情報（＝０若しくは１）を算術符号化する。なお、表裏判定情報の符号化方式については、特定の符号化方式に限るものではなく、ランレングス符号化等、他の符号化方式を用いても構わない。
【００２４】
次に、ステップＳ２０６では、生成部１０６は、着目面についてステップＳ２０３の外積計算で得た単位ベクトルと、着目面の表裏情報と、に基づいて、着目面に対する予測法線ベクトルを設定する。図３の場合、着目面＝面ｆ２とすると、表裏情報ＢＮ２＝０の場合、単位ベクトルｐ２を予測法線ベクトルとし、表裏情報ＢＮ２＝１の場合、単位ベクトルｐ２の各軸方向の成分値の符号を反転させたベクトル（−ｐ２）を予測法線ベクトルとする。
【００２５】
ステップＳ２０７では、符号化部１０７は、ステップＳ２０６で設定した着目面の予測法線ベクトルに対する着目面の法線ベクトルの差分（軸方向ごとの成分値の差分）を求め、該求めた差分を符号化する。図３の場合、着目面＝面ｆ２とすると、面ｆ２について設定した予測法線ベクトルに対する法線ベクトルｎ２の差分を求め、該求めた差分を符号化する。
【００２６】
一般的に差分が小さくなるほど符号量は小さくなる。ここでは、非特許文献１に記載の符号化方法でもって符号化する。非特許文献１に記載の符号化方法では、入力された浮動小数を符号化対象と予測値それぞれで符号部、指数部、仮数部に分離し、各部で整数として差分を取って符号化することで、浮動小数においても可逆圧縮を実現することができる。
【００２７】
以上説明した図２のフローチャートに従った処理が完了すると、出力部１０３は、符号化部１０２による符号化結果を符号データとして出力する。この符号データには、表裏判定情報の符号化結果、予測法線ベクトルに対する法線ベクトルの差分の符号化結果、が含まれている。符号データの構成例を図４に示す。
【００２８】
ヘッダ部にはヘッダデータが格納されている。ヘッダデータには、符号データに係る様々な情報が含まれており、その中には、ヘッダデータのデータ長及び表裏情報符号データのデータ長が含まれている。符号データの先頭に、ヘッダデータのデータ長及び表裏情報符号データのデータ長を加算することで、差分情報符号データの先頭を特定することができる。表裏情報データ部には、表裏判定情報を符号化した表裏情報符号データが格納されている。差分情報データ部には、予測法線ベクトルに対する法線ベクトルの差分を符号化した差分情報符号データが格納されている。なお、符号データの構成は図４に示した構成に限るものではない。例えば、表裏情報符号データと差分情報符号データとは別個のファイルとして出力しても構わない。
【００２９】
符号データの出力先については特定の出力先に限るものではなく、符号化装置内のメモリや符号化装置に対して着脱可能なメモリに対して出力しても良いし、ネットワークを介して外部の装置に対して出力しても良い。
【００３０】
次に、このような符号データに基づいて、必要に応じたレベルの法線ベクトルを生成する復号装置について説明する。先ず、本実施形態に係る復号装置の機能構成例について、図５のブロック図を用いて説明する。なお、本実施形態では、三次元形状モデルにおける各面を復号する際に、該面に対応する法線ベクトルを復号する。各面の復号については周知の復号技術でもって復号すればよく、法線ベクトルの復号処理については、以下の通りである。
【００３１】
入力部５０１は、符号化装置によって生成された符号データを取得する。入力部５０１による符号データの取得形態については特定の取得形態に限るものではなく、復号装置に着脱可能なメモリから符号データを取得しても良いし、ネットワークを介して符号化装置や記憶装置から符号データを取得しても良い。
【００３２】
復号部５０２は、入力部５０１が取得した符号データに基づいて、必要に応じたレベルの法線ベクトルを復号する。例えば、復号装置の不図示の表示画面に、高精度に法線ベクトルを復号する第１の復号モード、該第１の復号モードより低い精度で法線ベクトルを復号する第２の復号モード、の何れかを選択させるための選択画面を表示し、ユーザからの選択指示を受け付ける。そしてユーザが復号装置の不図示の操作部を操作して、第１の復号モードを選択すると、復号部５０２は、図７のフローチャートに従った復号処理を実行する。一方、ユーザが復号装置の不図示の操作部を操作して、第２の復号モードを選択すると、復号部５０２は、図６のフローチャートに従った復号処理を実行する。
【００３３】
先ず、図６のフローチャートに従った復号処理について説明する。図６のフローチャートに従った復号処理では、表裏情報符号データ及び差分情報符号データのうち表裏情報符号データのみを復号する。
【００３４】
ステップＳ６０１では、復号部５０４は、三次元形状モデルの全ての面が復号されたか否かを判断する。法線ベクトルは面に付加されているため、言い換えれば、全ての法線ベクトルが復号されたか否かを判断することになる。この判断の結果、全ての法線ベクトルを復号したのであれば、図６のフローチャートに従った処理は終了する。一方、未だ復号していない法線ベクトルが残っているのであれば、処理はステップＳ６０２に進む。
【００３５】
ステップＳ６０２では、復号部５０２は、未だ復号していない法線ベクトルのうちの１つを対象法線ベクトルとして選択する。以下では、三次元形状モデルにおいて対象法線ベクトルに対応する面を着目面と呼称する。すなわち、ステップＳ６０２では、三次元形状モデルを構成する全ての面のうち着目面を以下の処理の対象として設定したことになる。
【００３６】
ステップＳ６０３では、復号部５０２は、表裏情報符号データに対してエントロピー復号（符号化装置側でステップＳ２０５において行った符号化に対応する復号）を行う。これにより、着目面が、該着目面の直前に符号化された面と表裏情報が一致しているか否かを表す表裏判定情報を取得することができる。但し、着目面の直前に符号化された面が存在しない場合は、着目面の表裏情報が取得される。
【００３７】
ステップＳ６０４では、生成部５０５は、着目面の法線ベクトルを生成する。なお、この段階で、着目面の各頂点の座標は復号されているものとする。生成部５０５の動作について、図３を例にとり説明する。なお、頂点ｖ１を共有する各面及び対応する法線ベクトルの復号が完了すると、次に、頂点ｖ１以外の頂点について、該頂点を共有する面及び法線ベクトルを復号する。
【００３８】
ここで、面ｆ１及び法線ベクトルｎ１の復号が完了して、これから面ｆ２及び法線ベクトルｎ２を復号する場合について説明する。面の復号については従来技術であるため説明は省略し、以下では、法線ベクトルの復号について重点的に説明する。
【００３９】
生成部５０５は先ず、面ｆ２において頂点ｖ１を一端とする一方の辺に沿ったベクトル、すなわち、頂点ｖ１から頂点ｖ３に向かうベクトルｗ２を求める。更に生成部５０５は、面ｆ２において頂点ｖ１を一端とする他方の辺に沿ったベクトル、すなわち、頂点ｖ１から頂点ｖ４に向かうベクトルｗ３を求める。そして生成部５０５は、ベクトルｗ２とベクトルｗ３との外積（ｗ２×ｗ３）を求め、該外積の結果得られるベクトルを長さ１に正規化したベクトルｐ２を求める。
【００４０】
次に生成部５０５は、面ｆ２の表裏判定情報を参照し、表裏判定情報＝０であれば、ＢＮ２＝ＢＮ１であるから、ＢＮ１＝１であればＢＮ２＝１となり、ＢＮ１＝０であればＢＮ２＝０となる。一方、表裏判定情報＝１であれば、ＢＮ２≠ＢＮ１であるから、ＢＮ１＝１であればＢＮ２＝０となり、ＢＮ１＝０であればＢＮ２＝１となる。なお、着目面が面ｆ１の場合、着目面の表裏情報が該着目面の表裏判定情報となっているため、表裏判定情報の値そのものが表裏情報として使用される。
【００４１】
次に生成部５０５は、表裏情報ＢＮ２＝０の場合、単位ベクトルｐ２を面ｆ２の復号法線ベクトルとし、表裏情報ＢＮ２＝１の場合、単位ベクトルｐ２の各軸方向の成分値の符号を反転させたベクトル（−ｐ２）を面ｆ２の復号法線ベクトルとする。
【００４２】
このように、差分情報符号データは復号せずに、表裏情報符号データのみを復号し、法線ベクトルは外積計算及び表裏判定情報から求めるような構成は、例えば、次のようなアプリケーションに適用することができる。三次元形状モデルを３Ｄプリンタで出力するために該３Ｄプリンタに入力するデータについては、表裏情報が重要で、法線ベクトルの精度は粗くても構わない。然るにこのような場合は、差分情報符号データは復号せずに、表裏情報符号データのみを復号し、法線ベクトルは外積計算及び表裏判定情報から求めるようにすれば、余分な復号処理は省くことができ、且つ必要な表裏情報は確実に得ることができる。また、第１の復号モードは、三次元形状モデルを高速に表示したいときにも有効である。
【００４３】
つまり、図６のフローチャートに従った処理を実行する復号装置は、次のような構成の復号装置の一例である。つまり、上記の符号化装置によって符号化された情報を復号する。そして、第１の多角形における一辺に沿ったベクトルと、該一辺と一端を共有する他辺に沿ったベクトルと、の外積により該第１の多角形の予測法線ベクトルを求める。そして、該予測法線ベクトルと、上記復号した情報が表す第１の多角形の表裏判定の結果と、に応じて、第１の多角形の法線ベクトルを決定する。
【００４４】
次に、図７のフローチャートに従った復号処理について説明する。図７のフローチャートに従った復号処理では、表裏情報符号データ及び差分情報符号データの両方を復号する。なお、図７のステップＳ７０１〜Ｓ７０４はそれぞれ、図６のステップＳ６０１〜Ｓ６０４と同様の処理ステップであるため、これらの処理ステップに係る説明は省略する。
【００４５】
ステップＳ７０５では、復号部５０６は差分情報符号データを復号して、着目面の予測法線ベクトルに対する差分を取得し、該取得した差分をステップＳ７０４で生成した着目面の予測法線ベクトルに加算することで、該着目面の法線ベクトルを求める。図３を例にとると、面ｆ２が着目面の場合、面ｆ２の予測法線ベクトルに対する差分をΔ（ｘ２，Δｙ２，Δｚ２）、面ｆ２の予測法線ベクトルを（ｘ２，ｙ２，ｚ２）とすると、法線ベクトルｎ２（ｘ２＋Δｘ２，ｙ２＋Δｙ２，ｚ２＋Δｚ２）を求める。ここでは、非特許文献１の復号方法を適用する。非特許文献１では入力された浮動小数を符号化対象と予測値それぞれで符号部、指数部、仮数部に分離し、各部で整数として差分を取って符号化する。差分を復号して予測値（予測法線ベクトル）に加えることで、復号対象（法線ベクトル）を復号できる。このように、表裏情報符号データ及び差分情報符号データの両方を復号すると、第２の復号モードよりも法線ベクトルを高精度に復号することができる。
【００４６】
つまり、図７のフローチャートに従った処理を実行する復号装置は、次のような構成の復号装置の一例である。つまり、上記の符号化装置によって符号化された情報を復号し（第１の復号）、上記の第２の符号化によって符号化された差分を復号する（第２の復号）。そして、第１の多角形における一辺に沿ったベクトルと、該一辺と一端を共有する他辺に沿ったベクトルと、の外積により該第１の多角形の予測法線ベクトルを求める。そして、該予測法線ベクトルと、第１の復号で復号した情報が表す第１の多角形の表裏判定の結果と、第２の復号で復号した差分と、に応じて、第１の多角形の法線ベクトルを決定する。
【００４７】
なお、本実施形態では符号化効率向上のために着目する面の順番の前後で表裏情報ＢＮの差である表裏判定情報を符号化したが、処理の簡単のために表裏情報を直接符号化してもよい。この場合、復号側では、表裏判定情報の代わりに表裏情報を復号することになり、それ以外については本実施形態と同様である。
【００４８】
［第２の実施形態］
第１の実施形態では、法線ベクトルを、表裏判定情報と、予測法線ベクトルに対する差分情報と、に分けて符号化していた。そしてこの差分情報は、着目面について生成した予測法線ベクトルに対する、着目面の法線ベクトルの差分であった。本実施形態では、着目面についての差分情報を、予測法線ベクトル及び着目面に対する法線ベクトルの角度情報とする。
【００４９】
本実施形態に係る符号化装置の機能構成例について、図９のブロック図を用いて説明する。図９において、図１に示した機能部と同様の動作を行う機能部には同じ参照番号を付しており、該機能部に係る説明は省略する。
【００５０】
符号化部９０２における符号化部９０６は、差分情報としての角度情報を生成して符号化することで、差分情報符号データを生成する。符号化部９０２の動作について、図１０のフローチャートに従って説明する。図１０において、ステップＳ１００１〜Ｓ１００５はそれぞれ、図２のステップＳ２０１〜Ｓ２０５と同様の処理ステップであるため、これらのステップに係る説明は省略する。
【００５１】
ステップＳ１００６では、符号化部９０６は、着目面についての角度情報を生成する。本ステップにおける処理について、図３を例にとり説明する。着目面を面ｆ２とすると、先ず符号化部９０６は、法線ベクトルｎ２を、面ｆ２に対する仰角成分と、面ｆ２内の方向成分とに分解し、それぞれの成分を量子化したものを角度情報として生成する。
【００５２】
先ずベクトルｗ２（ベクトルｗ３でも良い）の長さを１に正規化したものをベクトルｗ２’として求め、ベクトルｗ２’とベクトルｐ２との外積（ｗ２’×ｐ２）を計算することで、図１１（ｃ）に示す如く、これらのベクトルに直交するベクトルｏ２を求める。このとき、ベクトルｗ２’、ｐ２，ｏ２は互いに直交する長さ１のベクトル（基底）となっている。次に、これら３つの基底を左からｗ２’、ｏ２、ｐ２の順に縦ベクトルとして並べた直交行列をＫとし、法線ベクトルｎ２を直交行列Ｋに写像（面に対して垂直な基底に回転）した結果をベクトルｍとする（ｍ＝ｎ２・Ｋ）。この時、ベクトルｍは３つの要素からなり、ｍ＝｛ｍ１、ｍ２、ｍ３｝で表されるものとする。この段階でベクトルｍの長さは１であることが保証されているため、ｍを曲座標表現で表し、その角度情報を量子化して符号化する。
【００５３】
ここで、図１１（ａ）、（ｂ）に示す如く、面ｆ２の予測法線ベクトルｐ２に対する法線ベクトルｎ２の角度をθとする。また、図１１（ｃ）に示す如く、ベクトルｗ２’を一方の軸、ベクトルｏ２を他方の軸とする座標系において、ベクトルｗ２’とベクトルｍとが成す角度をφとする。このとき、θ及びφと、ｍ１，ｍ２，及びｍ３と、の間には以下のような関係が成り立つ。
【００５４】
ｍ１＝ｓｉｎθｃｏｓφ
ｍ２＝ｓｉｎθｓｉｎφ
ｍ３＝ｃｏｓθ
これらの式から、以下の式が成り立つ。
【００５５】
θ＝ｃｏｓ−１（ｍ３）
φ＝Ｓ０ｃｏｓ−１（ｍ１／ｓｉｎθ）＝Ｓ０ｃｏｓ−１（ｍ１／√（１−ｍ３２））
ただしＳ０はｍ２の正負情報（ｗ２’に対してｏ２の正負どちらの方向に角度φを成すか）であり、ｍ２が負でれば−１、そうでなければ１をとる。曲座標上の位置を特定するには上記のθ及びφを保持すれば十分である。
【００５６】
ここで、θ及びφはそれぞれ０≦θ≦π、−π≦φ≦πの値域を持つ。だたし、ｍ３はｃｏｓθに一致し、この正負情報は符号化部１０５で符号化済みであるため、実際にはθ＝ｃｏｓ−１｜ｍ３｜を知ることができれば十分であり、θの値域は０≦θ≦π／２となる。
【００５７】
そこで、符号化部９０６は、θ及びφを次のように量子化する。
【００５８】
Ａθ＝Ｒ（θ／Ｔ）
Ａφ＝Ｒ（（φ＋π）／Ｔ）
Ｒ（ｘ）は値ｘの小数部を四捨五入する関数で、Ｔは規定の量子化ステップである。なお、量子化ステップＴは固定であることに限らず、例えば、Ａθを求める場合とＡφを求める場合とで異なる量子化ステップＴを用いても良い。
【００５９】
図１０に戻って、次に、ステップＳ１００７では、符号化部９０６は、角度情報Ａθ及びＡφを符号化する。なお、角度情報の符号化方式については、特定の符号化方式に限るものではなく、例えば、ハフマン符号化や、ＺＩＰ圧縮等のユニバーサル符号化を適用しても構わない。出力部９０３は、符号化部９０２による符号データを出力する。このように、表裏情報を判定するときの演算結果を利用して角度情報を設定することで、符号化処理の演算量削減を図ることができる。
【００６０】
一方、復号側において、第１の復号モードが指定されると、差分情報符号データを復号して角度情報Ａθ及びＡφを得る。そして、角度情報Ａθ及びＡφから上記の式によりベクトルｍを求め、更に上記式により、ベクトルｍの写像元である法線ベクトルを得る。
【００６１】
［第３の実施形態］
図１，５，９に示した各機能部は、ハードウェアで実装しても良いし、ソフトウェアプログラム（コンピュータプログラム）で実装しても良い。後者の場合、このソフトウェアプログラムは、ＰＣ（パーソナルコンピュータ）等、一般のコンピュータのメモリにインストールされることになる。そしてこのコンピュータのＣＰＵがこのインストールされたソフトウェアプログラムを実行することで、このコンピュータは、上述の符号化装置、復号装置の機能（図１，５，９に示した各機能部の機能）を実現することになる。即ち、このコンピュータは、上述の符号化装置、復号装置に適用することができる。また、符号化装置、復号装置は同一の装置であっても良いし、それぞれ別個の装置であっても良い。符号化装置、復号装置に適用可能なコンピュータのハードウェア構成例について、図８のブロック図を用いて説明する。
【００６２】
ＣＰＵ８０１は、ＲＡＭ８０２やＲＯＭ８０３に格納されているコンピュータプログラムやデータを用いて処理を実行する。これによりＣＰＵ８０１は、コンピュータ全体の動作制御を行うと共に、上記の符号化装置や復号装置が行うものとして上述した各処理を実行若しくは制御する。
【００６３】
ＲＡＭ８０２は、外部記憶装置８０７やＲＯＭ８０３からロードされたコンピュータプログラムやデータ、記憶媒体ドライブ８０８が記憶媒体から読み出したコンピュータプログラムやデータを格納するためのエリアを有する。更にＲＡＭ８０２は、Ｉ／Ｆ（インターフェース）８０９を介して外部から取得したコンピュータプログラムやデータを格納するためのエリアを有する。更にＲＡＭ８０２は、ＣＰＵ８０１が各種の処理を実行若しくは制御するために使用するワークエリアを有する。このようにＲＡＭ８０２は、各種のエリアを適宜提供することができる。ＲＯＭ８０３には、書き換え不要のブートプログラムや本コンピュータの設定データなどが格納されている。
【００６４】
キーボード８０４及びマウス８０５は、ユーザが各種の指示をＣＰＵ８０１に対して入力するために操作するユーザインターフェースの一例である。然るに、同様の目的を達成することができるのであれば、キーボード８０４やマウス８０５以外のユーザインターフェースを設けるようにしても良い。
【００６５】
表示装置８０６は、ＣＲＴや液晶画面などにより構成されており、ＣＰＵ８０１による処理結果を画像や文字などでもって表示することができる。例えば、表示装置８０６には、三次元形状モデルの画像や、上記の第１の復号モード及び第２の復号モードの何れかを選択するための選択画面を表示させることができる。また、キーボード８０４及びマウス８０５と表示装置８０６の代わりに若しくは加えて、タッチパネル画面を設けても良い。
【００６６】
外部記憶装置８０７は、ハードディスクドライブ装置に代表される大容量情報記憶装置である。外部記憶装置８０７には、ＯＳ（オペレーティングシステム）や、上記の符号化装置や復号装置が行うものとして上述した各処理をＣＰＵ８０１に実行若しくは制御させるためのコンピュータプログラムやデータが保存されている。このコンピュータプログラムには、図１，５，９に示した各機能部の機能をＣＰＵ８０１に実現させるためのコンピュータプログラムが含まれている。また、外部記憶装置８０７に保存されているデータには、三次元形状モデルのデータ（法線ベクトルデータを含む）や、既知の情報として上述した情報（例えば、上記の量子化ステップＴ等）が含まれている。また、上記の出力部１０３や出力部９０３が出力するものとして上述した符号データは、この外部記憶装置８０７に保存するようにしても良い。外部記憶装置８０７に保存されているコンピュータプログラムやデータは、ＣＰＵ８０１による制御に従って適宜ＲＡＭ８０２にロードされ、ＣＰＵ８０１による処理対象となる。
【００６７】
記憶媒体ドライブ８０８は、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等の記憶媒体に格納されているコンピュータプログラムやデータを読み出して、ＲＡＭ８０２や外部記憶装置８０７に対して出力する機器である。なお、外部記憶装置８０７に保存しておくものとして上述したコンピュータプログラムやデータの一部若しくは全部をこの記憶媒体に格納させておくようにしても構わない。
【００６８】
Ｉ／Ｆ８０９は、外部装置を本コンピュータに接続する為のものである。例えば、３Ｄスキャナなど、三次元形状データを取得するための装置を、このＩ／Ｆ８０９に接続し、この装置から三次元形状データをＩ／Ｆ８０９を介してＲＡＭ８０２や外部記憶装置８０７に取得するようにしても良い。
【００６９】
バス８１０には、ＣＰＵ８０１、ＲＡＭ８０２、ＲＯＭ８０３、キーボード８０４、マウス８０５、表示装置８０６、外部記憶装置８０７、記憶媒体ドライブ８０８、Ｉ／Ｆ８０９が接続されている。
【００７０】
上述構成において、本コンピュータの電源がＯＮになると、ＣＰＵ８０１はＲＯＭ８０３に格納されている上記ブートプログラムに従って、外部記憶装置８０７からＯＳをＲＡＭ８０２にロードする。その結果、キーボード８０４、マウス８０５を介した情報入力操作が可能となり、表示装置８０６にＧＵＩ（グラフィカルユーザインターフェース）等を表示することが可能となる。ユーザが、キーボード８０４やマウス８０５を操作し、外部記憶装置８０７に格納された三次元形状処理用アプリケーションのプログラムの起動指示を入力すると、ＣＰＵ８０１はこのプログラムをＲＡＭ８０２にロードし、実行する。これにより、本コンピュータが上記の符号化装置や復号装置として機能することになる。
【００７１】
（その他の実施例）
本発明は、上述の実施形態の１以上の機能を実現するプログラムを、ネットワーク又は記憶媒体を介してシステム又は装置に供給し、そのシステム又は装置のコンピュータにおける１つ以上のプロセッサーがプログラムを読出し実行する処理でも実現可能である。また、１以上の機能を実現する回路（例えば、ＡＳＩＣ）によっても実現可能である。
【符号の説明】
【００７２】
１０４：判定部  １０５：符号化部  １０６：生成部  １０７：符号化部  ５０４：復号部  ５０５：生成部  ５０６：復号部
【図１】
2017191574.tif 000003
【図２】
2017191574.tif 000004
【図３】
2017191574.tif 000005
【図４】
2017191574.tif 000006
【図５】
2017191574.tif 000007
【図６】
2017191574.tif 000008
【図７】
2017191574.tif 000009
【図８】
2017191574.tif 000010
【図９】
2017191574.tif 000011
【図１０】
2017191574.tif 000012
【図１１】
2017191574.tif 000013