Fast Algorithms for Dominant Point Detection with Variable Tradeoff between the Approximation Error and the Compression

Abstract

This paper proposes two new algorithms for dominant point detection in digital curves. The motivation is the following: ‘points of large curvature contain much information about shape; however, points of small curvature are not devoid of such Information. In many cases, the cumulative curvature due to a large number of such points occurring consecutively is significant.’ In the proposed schemes, detecting the next dominant point on the curve involves determining the curvature at each point, and computing the resultant cumulative curvature for all the points starting with the last detected dominant point. It is demonstrated that such an approach effectively imposes an upper bound on the error in reconstruction. In our algorithms, the compression ratio and the error in the shape representation have been controlled by appropriately chosen parameters. The magnitude of curvature and its sign are both important. Since the algorithms use only 1-curvature, they are very efficient. The proposed strategies yield excellent results, and have been compared with the Teh-Chin algorithm [1] and the Ansari-Huang [2] algorithm.

Indexing terms:

• Dominant point
• Digital curve
• Curvature
• Compression ratio
• 1-curvature

Additional information

Notes on contributors

Arnab Chakrabarti

Amab Chakrabarti is currently working towards a PhD at Rice University, Houston, Texas, USA. He received the Degree of Master of Science in May, 2003. Prior to this, he received his degree of Bachelor of Technology (Hons) in 2001 from the Department of Electronics and Electrical Communication Engineering of IIT-Kharagpur. His current research interests are in Sensor and Ad-Hoc Networks, Wireless Communication, Information Theory, Source and Channel Coding and in a variety of problems related to Communication and Signal Processing.

Abha Jain

Abha Jain is currently pursuing the degree of Master of Science at Rice University, Houston Texas, USA. She looks forward to receiving this degree in January, 2004. Prior to this, she received her degree of Bachelor of Technology (Hons) in 2001 from the Department of Electronics and Electrical Communication Engineering of IIT-Kharagpur, where she received the Sarat Memorial Award for being the best woman student in her batch. She also received the best BTech Dissertation Award from the Department of ECE at IIT-Kharagpur. Her current research interests include Neural Networks, Pattern Recognition and Communication and Signal Processing.

A K Ray

Ajoy Kumar Ray received his BE (Electronics & Telecommunication) from BE College, Sibpur and M Tech and PhD from IIT Kharagpur. Currently he is a Professor in the Electronics & ECE department, IIT Kharagpur. He has published more than 75 papers in various international and national journals and conferences and has authored two books. He has successfully completed twelve research projects sponsored by various national and multinational agencies and presently he is the chief investigator of an INTEL sponsored research project. His research interests include Image Processing, Machine Intelligence and Microprocessor based System Design.