# Line Segment Matching Fusing Local Gradient Order and Non-Local Structure Information
## 3 Methodologies
### Local Gradient Order Encoding  
[PERSON] et al. [11] introduced the LIOP [26] descriptor into line feature matching and obtained certain illumination robustness, proving that the method based on intensity sorting is more robust to illumination change than the one based on direction estimation [8; 9]. However, they only focus on the local intensity information of the LSR, ignoring the gradient information which can better describe the line segment. [PERSON] et al. [27] proposed a texture classification descriptor by sorting the intensity difference of the center and its neighboring pixels. Inspired by them, we combined the adaptive intensity partition to carry out local gradient order encoding for the sub-region of the line support region. Before constructing the local gradient order descriptor, an index table is defined. Let \(\Pi^{P}\) be the set of permutations of \(P\) integers, which would have \(P!\) elements in total. Next, number the elements in the collection \(\Pi^{P}\) in non-descending order to ensure that each arrangement has a unique corresponding index. Table 1 is an example. Figure 3: Demonstration of sub-region generation. Before sampling, gradient information should be extracted. First, two Sobel operators are employed to process \(u\) direction and \(v\) direction of the image, respectively, to obtain \(u\) direction and \(v\) direction gradients \(g_{u}\) and \(g_{v}\). To guarantee the invariance of the pixel gradient rotation, the gradients are projected under the original coordinate system of the image to the line support region coordinate system,  
\[g_{d_{L}}=g_{u}\times\cos_{d_{L}}+g_{v}\times\sin_{d_{L}} \tag{4}\]  
\[g_{d_{O}}=g_{u}\times\cos_{d_{O}}+g_{v}\times\sin_{d_{O}} \tag{5}\]  
where \(g_{d_{O}}\) and \(g_{d_{L}}\) represent the gradient projected to the \(d_{O}\) direction and \(d_{L}\) direction under the local coordinate system of the support region, \(\cos_{d_{L}}\) represents the cos value in the \(d_{L}\) direction, and the same for the other ones. Thereafter, the sum of \(g_{d_{O}}\) and \(g_{d_{L}}\) is calculated to obtain the gradient \(g\) under the local coordinate system of the line support region. \[g=g_{d_{O}}+g_{d_{L}} \tag{6}\]  
In the latter, unless otherwise specified, all references to gradients refer to gradients in the local coordinate system of the line support region. Considering a pixel \(x_{i}(x_{i}\in\text{Bin}_{k})\) in the sub-region \(Bin_{k}\), when constructing the feature descriptor of this pixel, the gradient order information of its neighborhood sampling points is needed. To achieve this goal, a neighborhood circle centered at this pixel with radius R is formed and \(P\) sampling pixels are selected within the circle, denoted as  
\[\text{G}(x_{i})=\left(g_{x_{i},0},g_{x_{i},1},g_{x_{i},2},\cdots g_{x_{i},P-1}\right) \tag{7}\]  
where \(\text{G}(x_{i})\) stores the gradient of the sampling points of pixel \(x_{i}\), and \(g_{x_{i},p}\) is defined as the gradient of the \(p\)th sampling point of the pixel \(x_{i}\). To reduce the dimensionality, divide these \(P\) sampling points into \(M\) groups with \(Q\) points within each group. (\(Q\) is limited to 3). The starting point of sampling is defined as the position where the gradient of adjacent sampling points is maximum. This leaves the descriptor invariant to rotation When rotating the sampling sequence cyclically the point with the largest gradient is located at the first position. Then, the group corresponding to this sampling point will be the starting sampling group, thus forming a rotation-invariant sampling sequence. \[\text{G}_{m}(x_{i})=\left\{\begin{array}{cc}\left(g_{x_{i},0},g_{x_{i},M},g _{x_{i},2M},\cdots,g_{x_{i},(Q-1)M}\right),&m=1\\ \left(g_{x_{i},1},g_{x_{i},M+1},g_{x_{i},2M+1},\cdots,g_{x_{i},(Q-1)M+1} \right),&m=2\\ \vdots&\vdots\\ \left(g_{x_{i},M-1},g_{x_{i},2M-1},g_{x_{i},3M-1},\cdots,g_{x_{iconverted to a unique integer by the index table. The corresponding histogram is obtained by this integer. \[\mathrm{H}_{m}(x_{i})=\left(