 |
Implicitization by Matrix Annihilation
|
with
William Wolovich
and
Mustafa Unel
|
|
|
Both parametric and implicit representations can be used to model 2D curves and 3D surfaces. Each has certain advantages compared to the other. Implicit polynomial (IP) methods are not as popular as parametric procedures because the lack of general procedures for obtaining IP models of higher degree has prevented their general use in many practical applications. In most cases today, parametric equations are used to model curves and surfaces. One such parametric representation, elliptic Fourier Descriptors (EFD) has been widely used to represent 2D and 3D curves, as well as 3D surfaces. Although EFDs can represent nearly all curves, it is often convenient to have an implicit representation: for example: (i) for determining whether given points lie on the curve or (ii) for determining curve/surface intersections and (iii) for computing “how close” measured points on a curve/surface are to the ideal curve/surface modeled with an implicit polynomial. Besides these nice features of implicit polynomials, there are also various algebraic and geometric invariants that have been obtained from implicit models. Obtaining implicit polynomials directly from points have been studied extensively by a group of researchers at Brown university. Instead of obtaining implicit representations directly from points, it is also possible to convert parametric equations to implicit ones. The general process of converting from parametric equations of curves or surfaces to implicit ones is known as implicitization and it has been studied for more than a century now. Here we use elliptic Fourier descriptors to parametrically represent curves. Elliptic Fourier descriptors have been widely used to represent 2D curves. There are also some invariants derived from EFDs which are used for shape recognition. We developed a new non-symbolic implicitization technique called the matrix annihilation method, for converting parametric Fourier representations to algebraic (implicit polynomial) representations to provide a means of benefiting from the features of both. Our method is numerical, so that we can parametrize more complex curves with higher order polynomial degrees than previously possible. Furthermore, our procedure is computationally efficient. We start with representing curves parametrically using elliptic Fourier descriptors and obtain their complex form. The complex form allows us to tackle with the problem in z-domain. We utilize time convolution property in z-domain and obtain a matrix representation that maps every monomial of an implicit polynomial in terms of the Fourier bases: sines and cosines of different harmonics. This matrix is obtained after some convolutions of Fourier coefficients and some decompositions. The vector that annihilates this matrix yields the coefficients of the implicit polynomial which is equivalent to the original parametric representation. |
|
Above figure illustrates a 6 harmonic EFD curve converted into a 12th degree IP curve. The parametric curve is represented by following Fourier coefficients: |
|
Following figure illustrates carpal bones represented by implicit polynomials. |
| Related Publications |
 |
|
"Implicitization of Algebraic Curves by Matrix Annihilation," International Journal of Computer Vision, 54(1-3):105-115, October 2003. [Abstract] [pdf] |
|
|
|
Resume
| Research
| Main Page
Carnegie Mellon University, Robotics Institute
5000 Forbes Av., Pittsburgh, PA, 15213
hulyayalcin@gmail.com
