# Multi-Constrained Optimization Method of Line Segment Extraction Based on Multi-Scale Image Space
## 2 Methods
### Optimization and Purification Based on Geometric Constraints
#### 2.2.1 Distance Geometric Constraint  
The distance geometric constraint relationships can be divided into horizontal and vertical distance relationships. Considering the horizontal distance relationship (Figure 4a), the distance \(D_{1}\) between the midpoints of two line segments is used to judge whether they are related and whether \(l_{2}\) needs to be retained or deleted. If \(D_{1}>\left(length^{(1)}+length^{(2)}\right)/2\), \(l_{2}\) and \(l_{1}\) are independent. \(l_{2}\) is retained and stored as one of the reference line segments in the next judgment process. If \(D_{1}\leq\left(length^{(1)}+length^{(2)}\right)/2\), \(l_{2}\) is related to \(l_{1}\) and \(l_{2}\) continues to be judged by the vertical distance constraint relationship. Considering vertical distance constraint (Figure 4b), if \(D_{2}\leq\xi_{d}\) (where \(\xi_{d}\) is the vertical threshold), \(l_{2}\) is strongly correlated with \(l_{1}\) and we then merge \(l_{1}\) and \(l_{2}\). If \(\xi_{d}<D_{2}\leq 3\xi_{d}\), \(l_{2}\) is a redundant or invalid segment and needs to be deleted. If \(D_{2}>3\xi_{d}\), \(l_{2}\) and \(l_{1}\) are independent and \(l_{2}\) is retained and stored as one of the reference line segments in the next judgment. Here we set \(\xi_{d}=1(pixel)\), because the resolution of the human eye is 1 pixel, and the error of more than 1 pixel is discernible. In this paper, as a part, we also propose an optimization method for merging short line segments based on endpoint projection transformation. The reason for selecting optimization method is that the least squares fitting method has larger extraction errors for extracted line segments from low-resolution images than from original images by using the multi-scale image space model. The least squares fitting is an error-averaging method to minimize the sum of squared errors. If the least squares fitting strategy was used here to merge line segments, it would bring more merging errors. The line segment merging method based on endpoint projection transformation is shown in Figure 5.  
Figure 4: The geometric constraint relationships between line segments. (**a**) Horizontal distance constraint. (**b**) Vertical distance constraint. (**c**) Angle constraint relationship (extension line intersection). (**d**) Angle constraint relationship (non-extension line intersection). Figure 5: Line segment merging method based on endpoint projection transformation. (**a**) The slope of the reference line segment is \(>0\). (**b**) The slope of the reference line segment is \(\leq\)0. The origin \(O\) of an image coordinate system is located in the upper left corner of image. \(l_{1}\) was a reference line segment extracted from the original image and the two endpoints were \(p_{1}=(u_{1},v_{1})\) and \(p_{3}=(u_{3},v_{3})\). \(l_{2}\) was an error-containing line segment in the multi-scale image space and its two endpoints were \(p_{2}=(u_{2},v_{2})\) and \(p_{4}=(u_{4},v_{4})\), whereas \(\hat{p}=(u,v,1)\) were homogeneous coordinates corresponding to these endpoints. We projected error-containing line segments onto the reference line segment, as well as obtained projected coordinate values \(p_{2}^{*}=\left(u_{2}^{*},v_{2}^{*}\right)\) and \(p_{4}^{*}=\left(u_{4}^{*},v_{4}^{*}\right)\) at both endpoints of the error-containing line segment. Equation (6) gives the endpoint projection formula:  
\[p^{*T}=\frac{1}{A^{2}+B^{2}}\left[ \begin{array}{ccc}B^{2}&-AB&-AC\\ -AB&A^{2}&-BC\end{array} \right]\hat{p}^{T}, \tag{6}\]  
where \(A\), \(B\), and \(C\) are the reference line equation \(Au+Bv+C=0\) parameters, which can be taken by known two endpoints image coordinates. Thereby, the projected coordinate value \(p^{*}=(u^{*},v^{*})\) of endpoints for the error-containing line segment can be achieved. Due to difference between positive and negative slopes of the reference line segment, the method of line segment merging has two possibilities regarding endpoint transformations.