2D curve and 3D surface models are widely used for a variety of purposes in computer vision and graphics. There exist efficient function based shape representation techniques such as Fourier, B-Splines, Non-Uniform Rational B-Splines (NURBS), Radial Basis Function (RBF), Rational Gaussian and Implicit Polynomial (IP). Among these techniques, representation in IPs focuses attention from researchers in the vision community who, in particular, are developing sophisticated techniques for the automatic recognition, registration and matching of 2D/3D objects. In contrast to other representations, IPs are superior especially in the areas of fast fitting, compactness of parameters, algebraic/geometric invariants, robustness against noise and occlusion, etc.

IP representation mainly suffers from the following two issues that not only greatly limit its applicability, but also confuse the users who need to model their target objects with IPs:

1) Poor representation for complex shapes.

Objects obtained by vision modalities are often very precise and thus complex. Unfortunately, using one IP even with a high degree to model a complex object is nearly impossible, i.e., IP cannot give an accurate shape representation for a complex shape due to numerical instability and high computational cost.

2) Difficulty in determining a moderate IP degree and achieving global/local stability.

It often needs a fitting method for representing dataset with an IP. Prior IP fitting methods require that the degree of IP must be determined before handling fitting and therefore they are difficult to determine a moderate degree for a complex object. Furthermore the prior methods suffer from computational instability that many redundant zero-level sets are generated around the desired one. This makes the fitting result nearly impossible to be interpreted in the desired region space.

The above two issues greatly limit the applicability of IP that the literatures, up to now, only applied IPs into such simple applications as single object recognition or global shape registration. This thesis makes three major contributions, two for solving these above two issues respectively and one for extending the IP's applicability for various applications.

- Contribution 1

In order to address issue 1), we propose a 3D segmentation method that is capable of dividing a complex 3D surface into simple surface segments and each segment of which can be accurately represented by an IP. This method is based on a cut-and-merge approach. Two cutting procedures adopt low-degree IPs to divide and fit the surface segments simultaneously, while avoiding generating high-curved segments. A merging procedure merges the similar adjacent segments to avoid over-segmentation. The purpose of this method aims at reducing the burden for encoding a complex object with an IP of high degree and simplifying the representation by encoding each simple segment with an IP of low degree.

The advantages of this method are that it is capable of i) finding the appropriate segmentation for various desired accuracies, ii) achieving stable fitting since we avoid using high-degree IPs, and iii) decomposing heavy computation from one high-degree IP into light computations from multiple low-degree IPs. This method maintains inherent algebraic/geometric invariants. Therefore the segmentation method opens up new vistas for 3D applications such as 3D matching, recognition and registration. This method can be applied to general 3D data formats such as polygonal mesh models.

- Contribution 2

Regarding issue 2), we propose a stable method for accurate fitting that automatically determines the moderate degree required. Our method increases the degree of IP until a satisfactory fitting result is obtained. The incrementability of the QR decomposition with Gram-Schmidt orthogonalization gives our method computational efficiency. Furthermore, since the decomposition detects the instability element precisely, our method can selectively apply ridge regression-based constraints only to that element.

The first advantage of this method is its computational efficiency because the incrementability of Gram-Schmidt QR decomposition dramatically reduces the burden of the incremental fitting by reusing the calculation results of the previous step. The second advantage is that the method can successfully avoid global instability, and furthermore maintain local accuracy, because constraints derived from the RR regularization are selectively utilized in our incremental scheme. Finally, a set of stopping criteria can successfully stop the incremental scheme at the step where the moderate degree is achieved. Also as long as this method is properly applied into the above segmentation method, we obtain an extended version that the adaptive segmentation result is available.

- Contribution 3

In this contribution, we first exploit two new applications for 3D object matching and registration based on our segmentation method. For matching problem, we take advantage of the geometric invariants of IP which have been encoded into the each segment. Since these geometric invariants can be fast and easily extracted from the IP coefficients, 3D matching problem can be hence solved by finding the corresponding IPs on two segmented surfaces. For 3D registration problem, we utilize the property of IP that intrinsic center and principal axes of an IP are easily extracted from the coefficients. Therefore over the conventional methods our method achieves that 1) the registration is in a non-iterative process and thus fast; 2) no initialization is required.

Furthermore, based on the better IP representation obtained by our previous methods and for further extending the applicability of IP, we present a new and fast 2D-3D / 3D-3D alignment technique making use of 3D implicit polynomials (IP). The method registers a target object to a source object which has been modeled by IP in advance. In alignment process, our method drives the motion of IP toward the desired 2D/3D image features, such as object boundaries. The resulting evolution is the gradient flow derived from IP function that minimizes the proposed energy functional.

This method has been effectively applied into Ultrasound (US) image pose estimation for medical purposes. Ultrasound (US) images are widely used in clinic for diagnosis and image guidance. However, US images are notorious for the poor image quality, due to speckle noises, low signal-to-noise ratio, occlusions and uniform brightness. And field of view (FOV) in US imaging is very limited; in severe cases, only 2D ross-sectional images are obtained. Therefore, matching a 2D US image to a pre-operative 3D organ models is often desirable for medical diagnosis.

Three main advantages over the traditional registration method are i) a fast transformation method for IP coefficients is introduced; ii) the alignment is formulated as to minimize an energy functional derived from IP gradient flow and thus avoid the cost for calculating point-wise correspondences; iii) with the property of IPs having very few coefficients, it makes both IP gradients and its transformation calculation extremely light both on computational complexity and memory. Through applying our alignment techniques to a real-time US image pose estimation, we demonstrate the capabilities of overcoming the limitations of unconstrained freehand US data by robust and fast pose estimation.

In conclusion, the research provides insights into the theory and practice of polynomial representation, and the main contribution can be summarized by the three following points: Firstly, a 3D IP-segment representation method is developed even for robustly representing complex objects. Secondly, an efficient fitting method has been developed for adaptively estimating the IP of moderate degree for objects with various shapes. Thirdly, two applications of solving 3D matching and registration problem based on our segmentation method, and one registration method using IP gradients for medical image applications have been developed.

本論文は、「2D Curve and 3D Surface Representation using Implicit Polynomial and Its Application(陰関数を用いた2D曲線と3D曲面の多項式表現とその応用)」と題し、計測等により得られた平面曲線や空間曲面等のデータを多項式陰関数により効率的に表現する手法を提案するとともに、実際に多項式陰関数モデルを用いた3次元モデル間および2次元画像-3次元モデル間の高速位置合わせや超音波画像解析への応用を示した研究をまとめたものであり、6章で構成され、英文で書かれている。

第1章「Introduction」では、平面曲線・空間曲面のモデリング技術について概観し、モデリングの手法を大きく(1) Explicit、(2) Parametric、(3) Implicitな方法に分類し、それぞれの従来研究について紹介している。さらに、既提案手法の問題点を指摘し、問題を解消するための方針を示している。

第2章は「Implicit polynomial」と題し、多項式陰関数の定義、モデリング(対象形状とのフィッティング)に関する関連研究、コンピュータビジョンに役立つ多項式陰関数の性質について述べている。フィッティング手法として非線形および線形手法の2つが提案されているが、計算の頑健さ、高速さから本手法は線形手法をベースとすることを述べている。また、線形手法として代表的な3つの手法: 3L法、Gradient-One法、Min-Max、Min-Var法を紹介している。本手法は、いずれの線形手法にも適用可能な手法である。また、計算の安定性を増すためのRidge Regression (RR) 法も紹介している。さらに、多項式陰関数独特の演算、不変量に関して紹介している。

第3章は「3D Surface Segmentation and Representation using IP」と題し、多項式陰関数の表現能力を増す手法の1つとして、対象形状を多項式陰関数で表現するのに適した断片に分割しながら、複数多項式陰関数の組み合わせで表現する方法を提案している。従来の曲率等の幾何的特徴量に基づく方法、グラフカット等のクラスタリングに基づく方法では、必ずしも多項式陰関数表現に適した分割が得られないことを述べ、多項式陰関数を直接用いたcut-and-merge戦略に基づく手法を提案している。その際、多項式陰関数の微分可能性、および微分幾何の知見等を積極的に利用している。また、提案手法が従来の多項式陰関数の不変量の利用に関し悪影響を与えないことを理論的、実験的に示している。

第4章は「An Adaptive and Stable Method for IP fitting」と題し、多項式陰関数の表現能力を増すもう1つの手法として、多項式の次数を適応的に決定する方法を提案している。従来法では、フィッティングの際の逆行列演算の過程において、あらかじめ次数を決定する必要があったが、Gram-Schmidtの直交化に基づくQR分解を用い、その増分的計算可能性を利用して適用的に次数を決定する方法を提案している。また増分の過程と協調することでRR法を部分的に適用することにより、表現能力と計算安定性を同時に満たす手法を提案している。また第3章の分割表現手法と同時に用いる方法についても述べている。

第5章は「A Fast Registration Method using IP Gradient Field」と題し、多項式陰関数の勾配場を利用することにより、3次元モデル同士、2次元画像と3次元モデルを高速に位置合わせする手法を提案している。多項式陰関数の微分可能性に着目し、代数的距離に基づくエネルギー関数を定義し、エネルギー最小化の枠組みで高速な位置合わせを実現している。また、エネルギー関数に超音波画像特有の特性を加えることで、従来S/N比が低く画像処理が困難な2次元超音波画像に対して、頑健に3次元モデルを位置合わせする方法を提案している。これにより手術中に取得された超音波画像とあらかじめモデル化された臓器とを位置合わせすることにより、医師の画像理解を助けるのに役に立つことが期待される。

第6章は「Conclusion」であり、本論文の成果を要約するとともに今後の課題が示されている。

以上これを要するに、本論文では、計測等により得られた平面曲線や空間曲面等のデータを 多項式陰関数により効率的に表現する手法を提案しており、多項式陰関数の表現能力の低さを、(1)対象形状のセグメンテーション、(2) 多項式の次数の適応的選択、の2つのアイディアにより解決する方法を提案し、有効性を示し、また従来処理が困難であった超音波画像処理への適用例を示しており、電子情報学上貢献するところが少なくない。

よって博士(情報理工学)の学位請求論文として合格と認められる。