Classification method based on skeleton lines for map building shapes

A classification method for map building shapes, comprising two parts, namely extracting skeleton lines of buildings, and constructing a template library and performing template matching by calculating cosine similarity of feature vectors:

• the steps for extracting skeleton lines are as follows:
• S1:
• extracting building feature points by using a Douglas-Peucker algorithm;
• S2:
• fitting points between feature points in a building polygon by using a least square method to obtain a line segment, and then extending each fitted line segment to form a closed polygon which is a least-squares template of the map building;
• S3:
• encrypting a point set constituting a boundary of the least-squares template of the building, and performing constrained Delaunay triangulation on this basis:
• dividing Delaunay triangles into three types:
• a triangle with one edge on the boundary of the building being called a triangle of a first type, a triangle with two edges on the boundary of the building being called a triangle of a second type, and a triangle without edges on the boundary of the building being called a third type of triangle;
• S4:
• performing connection to form local skeleton lines:
• for the triangle of a first type, connecting midpoints of two edges not located on the least-squares template to form local skeleton lines;
• and for the triangle of a third type, connecting a center of the triangle and midpoints of three edges to generate local skeleton lines;
• S5:
• connecting the local skeleton lines to form skeleton lines, a connecting principle being:
• by taking the midpoints of all the triangles of a third type as starting points, connecting the midpoints sequentially to the partial skeleton lines of the triangles of a first type between the midpoints of the next adjacent triangles of a third type, thereby forming complete skeleton lines;
• the steps of calculating feature vectors and performing template matching by using cosine similarity are as follows:
• S6:
• generating feature vectors of the buildings and templates:
• breaking the skeleton lines at intersection points, and connecting endpoints of the skeleton lines to form the feature vectors by taking the points with the largest number of connected line segments as starting points;
• S7:
• performing preliminary screening on the templates:
• since feature vector sets corresponding to different shapes are different, firstly, employing the feature vector sets to preliminarily screen the templates in the template library, and reserving templates identical to the feature vector sets of the buildings for further calculation;
• S8:
• performing superposition on the feature vectors:
• moving all the starting points of the feature vectors to an origin (0, 0), wherein this operation is capable of placing the feature vectors of the map buildings on the same basis as the feature vectors of the templates in the template library;
• fixing the feature vectors of the templates, and rotating the feature vectors of the buildings by a revolution by taking a fixed angle as a step size;
• S9:
• calculating cosine similarity between the feature vectors of the buildings and the feature vectors of the templates after each rotation, and taking a maximum value of the cosine similarity obtained as cosine similarity between the feature vectors of the buildings and the feature vectors of the templates after one revolution;
• and
• S10:
• determining the highest similarity, namely the category to which the buildings belong, by calculating the cosine similarity between the buildings and the screened templates.