# Line Segment Matching Fusing Local Gradient Order and Non-Local Structure Information
## 3 Methodologies
### Adaptive Intensity Partition  
Many popular and advanced line segment description methods adopt a geometric division strategy to divide the supported region into several fixed and regular sub-regions, such as the division based on line band--LBD [9]. However, this strategy underutilized intensity information. [PERSON] et al. [11; 12] used intensity order to partition and obtained certain robustness. However, their method suffers from two major problems:  
1. Using sequential partitioning requires a lot of sorting operations;
2. When the intensity value is excessively concentrated in a specific value, it will lead to uneven partition and significant partition change when the illumination changes.  
The present study adopts the intensity histogram for adaptive intensity partition to address these two problems.  
Ideally, if one wants to divide \(N\) pixels into \(B\) parts, each part will have \(N/B\) pixels. However, in natural images, pixel intensity is often stacked at a specific value, making it challenging to achieve uniform partitions. Therefore, multiple homogenization is adopted to get relatively uniform partitions adaptively.  
Assume that there are \(N\) pixels in the line support region, which is expressed as \(\Omega=\{x_{1},x_{2},x_{3},\cdots,x_{N}\}\). Their intensity is expressed as \(I=\{I_{x_{1}},I_{x_{2}},I_{x_{2}},\cdots,I_{x_{N}}\}\). The pixel intensity in the support region is traversed to get its intensity histogram as  
\[H_{I}=\{H_{0},H_{1},H_{2},\cdots,H_{255}\} \tag{1}\]  
where \(H_{0},H_{1},H_{2},\cdots,H_{255}\) represent the value is the number of occurrences of each intensity, and \(H_{I}\) meet \(H_{0}+H_{1}+H_{2}+\cdots+H_{255}=N\). If there are \(B\) sub-regions divided by the LSR, it is necessary to select \(B-1\) intensity values as thresholds, and set these \(B-1\) intensity thresholds as \(T_{k},k\in[1,B-1]\). First, for the first threshold \(T_{1}\), the cumulative pixel number of intensity histograms \(H_{0}\) to \(H_{T_{1}}\) is close to \(\frac{N}{B}\). For the second threshold \(T_{2}\), the cumulative pixel number of intensity histograms \(H_{T_{1}+1}\) to \(H_{T_{2}}\) is close to \(\frac{(N-\frac{T_{1}}{H_{1}}H_{1})}{(B-1)}\). For the \(k\)th threshold \(T_{k}\), the cumulative pixel number of intensity histograms \(H_{T_{k-1}+1}\) to  
Figure 2: Line support region generation demonstration.  
\(H_{T_{k}}\) is close to \(\frac{(N-\sum_{0}^{T_{k-1}-1}H_{I})}{(B-k+1)}\). The above process is iterated for \((B-1)\) times, and \((B-1)\) intensity thresholds are finally acquired. The calculation formula of the above process is represented as  
\[\frac{\sum_{T_{k-1}+1}^{T_{k}}H_{I}}{\left[\frac{\left(N-\sum_{0}^{T_{k-1}+1}H_ {I}\right)}{B-k+1}\right]}\approx 1 \tag{2}\]  
where, in order for \(k=0\) to satisfy the formula, \(T_{0}=0\) is set. According to the \((B-1)\) adaptive intensity thresholds, divide the pixels in the support region into \(B\) sub-regions. Then, we can define a mapping \(\eta(x,T)\) to map all pixels \(x\) in LSR to the corresponding sub-region.  
\[\eta(x,T)=\left\{\begin{array}{ll}1,&I(x)\leq T_{1}\\ k,&T_{k-1}<I(x)\leq T_{k},k=2,3,\cdot\cdot\cdot,B-1\\ B,&I(x)>T_{B-1}\end{array}\right. \tag{3}\]  
where the integer obtained by \(\eta(x,T)\) is the index of the sub-region, \(Bin_{k}\) is represented as the \(k\)th sub-region. Figure 3 shows a schematic representation of this sub-region partition based on adaptive strength partitions, where each sub-region is colored differently. It can be seen that compared with the computational complexity of sorting the supporting region, the histogram method has lower computational complexity. The method of multiple equalizations makes the partition less affected by the illumination change.