Imran SHARIF, Debasis CHAUDHURI, Naveen Kumar KUSHWAHA, Ashok SAMAL, Brij Mohan SINGH

An efficient algorithm to decompose a compound rectilinear shape into simple rectilinear shapes

Detection of a compound object is a critical problem in target recognition. For example, buildings form an important class of shapes whose recognition is important in many remote sensing based applications. Due to the coarse resolution of imaging sensors, adjacent buildings in the scenes appear as a single compound shape object. These compound objects can be represented as the union of a set of disjoint rectilinear shaped objects. Separating the individual buildings from the resulting compound objects in a segmented image is often difficult but important nevertheless. In this paper we propose a new and efficient technique to decompose a compound shape into a set of simple rectilinear shapes. First, the true interior and exterior corner points of the compound object are extracted. A modi ed corner detector based on polygonal approximation is proposed to accurately determine the boundaries of compound shapes. The compound shape is then split at the interior corner points to minimize the difference between the perimeter of the compound object and the sum of the perimeters of the decomposed objects. We have systematically compared the results our algorithm with those of existing approaches and the results show that the proposed algorithm is more accurate than the algorithms in the literature in terms of accuracy of perimeter estimation and computational cost.

PDF

___

[1] Zakaria MF, Vroomen LJ, Zsombor-Murray P, Vankessel JM. Fast algorithm for the computation of moment invariants. Pattern Recog 1987; 20: 639-643.
[2] Spiliotis IM, Mertzios BG. Real-time computation of two-dimensional moments on binary images using image block representation. IEEE T Image Process 1998; 7: 1609-1615.
[3] Kawaguchi E, Endo T. On a method of binary picture representation and its application to data compression. IEEE T Pattern Anal 1980; 29: 27-35.
[4] Keil JM. Polygon decomposition. In: Sack JR, Urrutia J, editors. Handbook of Computational Geometry. New York, NY, USA: Elsevier 2000. pp. 491-518.
[5] Zhang D, Lu G. Review of shape representation and description techniques. Pattern Recogn 2004; 37: 1-19.
[6] Wang H, Zhang W, Chen Y, Chen M, Yan K. Semantic decomposition and reconstruction of compound buildings with Semantic roofs from LiDAR data and Aerial imagery. Remote Sens-Basel 2015; 7: 13945-13974.
[7] Har-Peled S, Roy S. Approximating the maximum overlap of polygons under translation. Lecture Notes in Computer Science 2014; 6737: 542-553.
[8] Nagamochi H, Abe Y. An approximation algorithm for dissecting a rectangle into rectangles with speci ed areas. Discrete Appl Math 2007; 155: 523-537.
[9] Liu G, Xi Z, Lien JM. Dual space decomposition of 2D complex shapes. IEEE Conference on Computer Vision and Pattern recognition; 23-28 June 2014; Columbus, OH, USA: pp. 4154-4161.
[10] Patel TP, Panchal SR. Corner detection techniques: an introductory survey. Int. Journal of Engineering Develop- ment and Research 2014; 2: 3680-3686.
[11] Sojka E. A new algorithm for detecting corners in digital images. Proc. Spring Conference on Computer Graphics; 24{27 Apr 2002; Budmerice, Slovakia: pp. 55-62.
[12] Parvez MT, Mahmoud SA. Polygonal approximation of digital planar curves through adaptive optimizations. Pattern Recogn Lett 2010; 31: 1997-2005.
[13] Chaudhuri D, Kushwaha NK. Least square based automatic threshold selection for polygonal approximation of digital curves. International Journal of Advanced Technology & Engineering Research 2013; 3: 125-135.
[14] Song Y, Shan J. Building extraction from high resolution color imagery based on edge ow driven active contour and JSEG. In: The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. XXXVII, Part B 3G; 3{11 July 2008; Bejing China: pp. 185-190.
[15] Rottensteiner F, Sohn G, Jung J, Gerke N, Baillard C, Benitez S, Breitkopf U. The ISPRS benchmark on urban object classi cation and 3D building reconstruction. Int Soc Photogramm 2012; 1: 293-298.
[16] Cramer M. The DGPF test on digital aerial camera evaluation - overview and test design. Photogramm Femerkun 2010; 2: 73-82.
[17] Chaudhuri D, Kushwaha NK, Samal A. Automatic building detection from high resolution satellite image based on morphology and internal gray energy operations. IEEE J Sel Top Appl 2016; 9: 1767-1779.