# Multi-Constrained Optimization Method of Line Segment Extraction Based on Multi-Scale Image Space
## 1 Introduction
[PERSON] [24] proposed the line segment extraction algorithm with edge detection based on the Canny operator. However, the algorithm requires a large number of decision-making parameters, which has serious false positive (false detection) and false negative (missing detection) problems. A robust line segment extraction algorithm progressive probabilistic Hough transform (PPHT) proposed by [PERSON] et al. [25] combines the random edge point selection algorithm to improve the feature extraction speed. However, its error-detection mechanism easily raises false negatives and misses the necessary short line segments. More recently, a local line segment extraction algorithm, line segment detector (LSD), proposed by [PERSON] et al. [26], was found to be capable of extracting sub-pixel-level precision line segments in linear time, but the effect of line segments intersection, partial occlusion, image blur, image noise, and grayscale distortion caused severe segmentation fracture problems. [PERSON] et al. [27; 28] proposed a new edge detection operator, Edge Drawing, and a faster line segment extraction algorithm, Edge Drawing Lines (EDLines), but the segmentation fracture effect of the extracted line segments was not improved. The false negative of this method is inevitable and it is easy to miss critical line segments. The existing research mainly focuses on the accuracy and efficiency of the line feature extraction without considering the length of extracted line segments. Short line segments are less accurate than long line segments, which causes more processing errors (error matching and error reconstruction). Currently, there are few methods to solve this line segmentation fracture problem. To alleviate this common problem, this paper proposes a multi-constrained line segment extraction optimization algorithm based on multi-scale image space, namely MSLines, including MSLSD and MSEDLines (MS is an abbreviation of Multi-Scale), which reduces the influence of grayscale distortion on feature extraction using the idea of fuzzy processing. Figure 1 shows the overall methodology presented in this paper, which is divided into three main modules. The first module consists of constructing the line segment extraction model. A multi-scale image pyramid was constructed based on the Gaussian down-sampling and line segments of each image layer were extracted by the traditional line segment detection algorithm. All line segments were projected onto the original image and stored in line vector spaces. The second module was the optimization of the purification strategy. A set of line segment optimization and purification methods were designed with geometric constraints; line segments were merged or deleted according to the distance and angle relationships between line segments. The third module was second optimization. The virtual straight line was constructed and the secondary merge optimization of the line segment was realized based on the grayscale constraint relationship of the normalized cross correlation (NCC) measurement. Compared with several mainstream line segment extraction algorithms, i.e., LSD and EDLines, the proposed method could alleviate the segmental fracture effect of line segments and eliminate line segments' redundant problem. The remainder of this study is organized as follows. Section 2 describes the principle of multi-scale image space line segment extraction method. This section also introduces a new line segment  
Figure 1: Overall methodology of the proposed method. optimization and purification method based on geometric constraints. Also, a second optimization method of grayscale constraint is presented. In Section 3, three sets of real data, i.e., indoor, outdoor, and aerial images are tested to analyze superiority of our proposed line segment extraction method compared with the mainstream method. Section 4 discusses the selection of parameters in the model construction for various resolution images and analyses the accuracy of the proposed method. Section 5 presents conclusions and possible further studies.