Efficient Computation of Algebraic Invariants from Higher-Degree Implicit Polynomials Using Tensor-Based Representation

Abstract

Higher-degree implicit polynomials and moments provide useful global descriptors for complex curves and surfaces. In this paper, a tensor-based approach for obtaining Euclidean and affine invariants from coefficients of higher-degree implicit polynomials has been pro posed. The algorithm is an extension of the matrix-based approach by Taubin, but unlike the previous works, it is not based on partial derivative forms or symbolic computation. Owing to the close re lationship between algebraic invariants and moment invariants, the approach is equally applicable to moment invariants.

Get full access to this article

View all access options for this article.

References

Abhyankar, S.S. 1992. Invariant theory and enumerative combinatorics of young tableaux. Geometric Invariance in Computer Vision, eds. J. L. Mundy and A. Zisserman. Cambridge, MA: MIT Press, pp. 45-76.

Bookstein, F.L. 1979. Fitting conic sections to scattered data. Comp Graphics and Image Proc. 9:56-71.

Brown, W.C. 1991. Matrices and Vector Spaces New York : Marcel Dekker.

Cyganski, D. , and Orr, J.A. 1985. Applications of tensor theory to object recognition and orientation determination IEEE Trans. Pattern Analysis Machine Intell. 7(6):662-673.

Gool, L.V. , Moons, T. , Pauwels, E. , and Oosterlinck, A. 1995. Vision and Lie's approach to invariance Image and Vision Computing 13(4):259-277.

Grimson, W.E.L. , and Huttenlocher, D.P. 1990 (Osaka). On the sensitivity of geometric hashing. Proc. of the Third Int. Conf. on Comp. Vision Los Alamitos, CA: IEEE, pp. 334-338.

Hu, M.K. 1962. Visual pattern recognition by moment invariants IRE Trans. Information Theory 8(2):179-187.

Kaveti, S. , Teoh, E.K. , and Wang, H. 1997. Efficient algo rithms for obtaining algebraic invariants from higher degree implicit polynomials for recognition of curved objects Pattern Recognition J. 31(3):301-313.

Keren, D. 1994. Using symbolic computation to find algebraic invariants IEEE Trans. Pattern Analysis Machine Intell. 16(11):1143-1149.

10.

Keren, D. , Cooper, D. , and Subramonia, J. 1994. Describing complicated objects by implicit polynomials IEEE Trans. Pattern Analysis Machine Intell. 16(1):38-53.

11.

Knuth, D.E. 1968. Fundamental Algorithms, vol. 1 of The Art of Computer Programming Reading, MA: Addison-Wesley .

12.

Lamdan, Y. , and Wolfson, J.J. 1988 (Tarpon Springs, FL). Geometric hashing: A general and efficient model-based recognition scheme. Proc. of the Second Int. Conf on Comp. Vision Los Alamitos, CA: IEEE, pp. 238-249.

13.

Lamdan, Y. , and Wolfson, H.J. 1991 (Maui, HI). On the error analysis of geometric hashing. Proc. of the CVPR Los Alamitos, CA: IEEE, pp. 22-27.

14.

Lawson, C.L. , and Hanson, R.J. 1974. Solving Least Squares Problems Englewood Cliffs, NJ: Prentice-Hall.

15.

Lovelock, D. , and Rund, H. 1975. Tensors, Differential Forms, and Variational Principles New York: Wiley Interscience.

16.

Moons, T. , Pauwels, E.J. , Gool, L. J. V. , and Oosterlinck, A. 1995. Foundations of semi-differential invariants Int. J. Comp. Vision 14:25-47.

17.

Parshall, K.H. 1989. Toward a history of nineteenth-century invariant theory. The History of Modern Mathematics New York: Academic.

18.

Pei, S.-C. , and Lin, C.-N. 1995. Image normalization for pattern recognition Image and Vision Computing 13(10):711-723.

19.

Pratt, V. 1987. Direct least squares fitting of algebraic surfaces Comp. Graphics 21(4):145-152.

20.

Sampson, P.D. 1982. Fitting conic sections to very scattered data: An iterative refinement of the Bookstein algorithm Comp. Graphics Image Proc. 18:97-108.

21.

Spiegal, M.R. 1974. Schaum's Outline of Theory and Problems of Vector Analysis and an Introduction to Tensor Analysis New York : McGraw-Hill.

22.

Strumfels, B. 1993. Algorithms in Invariant Theory New York: Springer-Verlag.

23.

Subramonia, J. , Keren, D. , and Cooper, D.B. 1993 (Berlin). Recognizing mice, vegetables, and hand-printed characters based on implicit polynomials, invariants, and Bayesian methods. Proc. Fourth Int. Conf. on Comp. Vision Los Alamitos, CA : IEEE, pp. 320-324.

24.

Sullivan, S. , Sandford, L. , and Ponce, J. 1994. Using geometric distance fits for 3-D object modeling and recogniton IEEE Trans. Pattern Analysis Machine Intell. 16(12):1183-1196.

25.

Synge, J.L. , and Shild, A. 1978. Tensor Calculus. New York: Dover.

26.

Taubin, G. 1990. Recognition and positioning of rigid objects using algebraic and moment invariants Technical Report LEMS-80, Brown University, Providence, RI.

27.

Taubin, G. 1991. Estimation of planar curves, surfaces, and nonplanar space curves defined by implicit equations with applications to edge and range image segmentation IEEE Trans. Pattern Analysis Machine Intell. 13(11):1115-1138.

28.

Taubin, G. , Cukierman, F. , Sullivan, S. , Ponce, J. , and Kriegman, D.J. 1994. Parameterized families of polynomials for bounded algebraic curve and surface fitting IEEE Trans. Pattern Analysis Machine Intell. 16(3):287-303.