Abstract
In different types of information systems, such as multimedia information systems and geographic information systems, object-based information is represented via polygons corresponding to the boundaries of object regions. In many applications, the polygons have large number of vertices and edges, thus a way of representing the polygons with less number of vertices and edges is developed. This approach, called polygon approximation, or polygon simpliflication, is basically motivated with the difficulties faced in processing polygons with large number of vertices. Besides, large memory usage and disk requirements, and the possibility of having relatively more noise can also be considered as the reasons for polygon simplification. In this paper, a kinematics-based method for polygon approximation is proposed. The vertices of polygons are simplified according to the velocities and accelerations of the vertices with respect to the centroid of the polygon. Another property of the proposed method is that the user may set the number of vertices to be in the approximated polygon, and may hierarchically simplify the output. The approximation method is demonstrated through the experiments based on a set of polygonal objects.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
E. Arkin, P. Chew, D. Huttenlocher, K. Kedem, and J. Mitchel. An efficiently computable metric for comparing polygonal shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(3):209–215, 1991.
M.E. Dönderler, Ö. Ulusoy, and U. Güdükbay. A rule-based approach to represent spatio-temporal relations in video data. In T. Yakhno, editor, Advances in Information Sciences (ADVIS’2000), volume 1909 of LNCS, pages 248–256, 2000.
M.E. Dönderler, Ö. Ulusoy, and U. Güdükbay. A rule-based video database system architecture, to appear in Information Sciences, 2002.
D. Eu and G.T. Toussaint. On approximating polygonal curves in two and three dimensions. CVGIP: Graphical Models and Image Processing, 56(3):231–246, 1994.
M. Garland and P. S. Heckbert. Surface simplification using quadric error metrics. ACM Computer Graphics, 31(Annual Conference Series):209–216, 1997.
S. Grumbach, P. Rigaux, and L. Segoufin. The DEDALE system for complex spatial queries. Proceedings of ACM SIGMOD Symp. on the Management of Data, pages 213–224, 1998.
J.D. Hobby. Polygonal approximations that minimize the number of infections. In Proceedings of Fourth ACM-SIAM Symposium on Discrete Algorithms, pages 93–102, 1993.
J. Kim, A.C. Bovik, and B.L. Evans. Generalized predictive binary shape coding using polygon approximations. Signal Processing: Image Communication, 15(7–8):643–663, 2000.
Y. Kurozumi and W.A. Davis. Polygonal approximation by the minimax method. Computer Graphics and Image Processing, 19:248–264, 1982.
C.C. Lu and J.G. Dunham. Hierarchical shape recognition using polygon approximation and dynamic alignment. Proceedings of 1988 IEEE International Conference on Acoustic, Speech and Signal Processing, Vol. II, pages 976–979, 1988.
J.R. Rossignac and P. Borrel. Multiresolution 3d approximations for rendering complex scenes. In B. Falcidieno and T. Kunii, editors, Modeling in Computer Graphics: Methods and Applications, pages 455–465, 1993.
J. Russ. The Image Processing Handbook. CRC Press, in cooperation with IEEE Press, 1999.
E. Saykol, U. Güdükbay, and Ö. Ulusoy. A semi-automatic object extraction tool for querying in multimedia databases. In S. Adali and S. Tripathi, editors, 7th Workshop on Multimedia Information Systems MIS’01, Capri, Italy, pages 11–20, 2001.
E. Saykol, U. Güdükbay, and Ö. Ulusoy. A histogram-based approach for objectbased query-by-shape-and-color in multimedia databases. Technical Report BUCE-0201, Bilkent University, 2002.
W. J. Schroeder, J. A. Zarge, and W. E. Lorensen. Decimation of triangle meshes. Computer Graphics, 26(2):65–70, 1992.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Saykol, E., Gülesir, G., Güdükbay, U., Ulusoy, Ö. (2002). KiMPA: A Kinematics-Based Method for Polygon Approximation. In: Yakhno, T. (eds) Advances in Information Systems. ADVIS 2002. Lecture Notes in Computer Science, vol 2457. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36077-8_18
Download citation
DOI: https://doi.org/10.1007/3-540-36077-8_18
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00009-9
Online ISBN: 978-3-540-36077-3
eBook Packages: Springer Book Archive