Latent Semantic Consensus For Deterministic Geometric Model Fitting

Random model fitting methods can be classified into sampling and model selection methods according to their process. For the first step, to hit all model instances in data, that is, there is at least an all-inlier minimal subset sampled for each model instance, the sampling problem approximately possesses a combinatorial nature, making the number of minimal subsets huge. For an example of data with the outlier ratio $\alpha$, RANSAC [6], one of the most popular sampling algorithms, requires to sample $\frac{log(1-\beta)}{log(1-(1-\alpha)^{\rho})}$ minimal subsets, to hit a model instance with the probability $\beta$. Here $\rho$ is the minimum number of data points in a minimal subset. Even worse, the sampled minimal subsets contain a large number of bad ones. Then, there are many variants of RANSAC to improve the performance on more complex cases, e.g., ROSAC [14], LO-RANSAC [15], HMSS [16] and CBS [8].

For model selection methods, they can be roughly classified into the consensus analysis-based and the preference analysis-based methods, according to the space they perform. The consensus analysis-based fitting methods, e.g., MSHF [1] and CBG [17], select the best model hypotheses as the estimated model instances; The preference analysis-based methods, e.g., SWS [18], RPA [19], RansaCov [20], T-linkage [21], MultiLink [22], MCT [23] and CLSA [2], label data points and then estimate the parameters of model instances. These two kinds of model fitting methods have their own advantages and disadvantages. Specifically, the former methods are not sensitive to unbalanced data distribution, but they rely heavily on the quality of model hypotheses; in contrast, the latter methods are very sensitive to unbalanced data distribution, but they estimate model instances based on data points, so they do not rely heavily on the generated model hypotheses. Thus, there is not a model selection algorithm that has clear advantage.

Deep learning-based methods have gained popularity in various computer vision tasks, including model fitting [24, 25, 26, 27]. These methods offer a significant advantage in learning powerful representations directly from raw data, eliminating the need for hand-crafted features. However, a drawback is their dependency on large amounts of training data, and its sensitivity to outliers, particularly in multi-structural datasets.

Compared with random model fitting methods whose results often vary, deterministic model fitting methods are able to provide stable solutions and they also can be tractable. Most of currently existing deterministic model fitting methods cast the fitting task as a global optimization problem. Such as, Li [10] and Chin et al. [11] adopted a tailored branch-and-bound scheme and the A* algorithm to search for a globally optimal solution, respectively; Doan et al. [28] and Le et al. [12] introduced a hybrid quantum-classical algorithm and the maximum consensus criterion for deterministic fitting, respectively; Fan et al. [29] discussed two loss functions to seek geometric models.

These above deterministic methods only work for single-structural data and they also often suffer from high computational complexity. Xiao et al. [9, 13] used the superpixel information and the min-hash technique to propose two heuristic methods for multiple-structural deterministic model fitting. However, they only work for two-view fitting problem due to the information of correspondences they depend on. That is, they cannot be used for general fitting problems, e.g., line fitting and circle fitting.

This paper also proposes a deterministic method, but, it not only can work for multiple-structural data, but also has not the limitation of two-view model fitting. That is, this paper proposes a deterministic methods by preserving latent semantic consensus for general multiple-structural model fitting problems.

It is important to note that CLSA [2] and the proposed method (LSC) both utilize latent semantic analysis to tackle model fitting problems. However, they differ significantly in the following aspects: 1) CLSA employs LSA to eliminate outliers in LSS, whereas LSC preserves latent semantic consensus in LSS for minimal subset sampling. 2) CLSA constructs LSS once, and its effectiveness depends on the input data; in contrast, LSC dynamically updates LSS based on generated model hypotheses, enhancing its effectiveness. 3) CLSA is a random model selection method, whereas LSC follows a deterministic approach for both sampling and model selection. Consequently, LSC provides more stable and superior fitting results compared to CLSA.

A geometric model is usually provided beforehand, such as, line, circle, homography matrix, fundamental matrix, etc, for model fitting. Then, given $n$ data points $S=\{s_{1},\ldots,s_{i},\ldots,s_{n}\}$, the output of geometric model fitting is the parameter of model instances and the labels of data points. Here, a model instance (or structure) is an instance of the given geometric model, and the labels of data points include inliers belonging to different model instances and outliers.

As aforementioned, a model fitting problem generally contains minimal subsets sampling for model hypothesis generation, and model selection based on the generated model hypotheses. Here, a model hypothesis is a parameter formulation of the given geometric model. For the model of a line, a model hypothesis is $[a~{}b~{}c]$, where $ax_{i}+by_{i}+c=0$ for a data point $s_{i}=\{x_{i},y_{i}\}$; For the model of a circle, a model hypothesis is $[a~{}b~{}r]$, where $(a,b)$ is the coordinate values of the center of a circle, and $r$ is the value of radius, and $(x_{i}-a)^{2}+(y_{i}-b)^{2}=r^{2}$ for a data point $s_{i}=\{x_{i},y_{i}\}$; For the model of a homography matrix, a model hypothesis $\theta$ is $3\times 3$ matrix in $\mathbb{R}^{3\times 3}$, where $\begin{bmatrix}x^{\prime}_{i}~{}y^{\prime}_{i}~{}1\end{bmatrix}^{T}=\theta\begin{bmatrix}x_{i}~{}y_{i}~{}1\end{bmatrix}^{T}$ for a data point $s_{i}=(x_{i},y_{i},x^{\prime}_{i},y^{\prime}_{i})$, and $(x_{i},y_{i})$ and $(x^{\prime}_{i},y^{\prime}_{i})$ are the image coordinates of the two feature points in the image pair. Of course, the geometric model is not limited to line, circle and homography matrix.

In this section, we delve into Latent Semantic Analysis (LSA) [30] as a key component of our deterministic model fitting approach. Drawing inspiration from topic modeling, a widely used technique in uncovering word-use patterns and document connections in word processing [31], LSA proves instrumental. Much like how words within the same topic exhibit similar distributions, our data points and model hypotheses share an analogous relationship to words and documents. In the realm of model fitting, certain data points align with inliers of a model hypothesis, mirroring the association between words and documents in topic modeling. The crux lies in recognizing that some model hypotheses correspond to actual model instances. Just as certain words form parts of a document, specific documents correspond to a broader topic. The parallels between these relationships underscore the efficacy of employing topic modeling principles for our model fitting endeavors.

Among various topic modeling methods [32, 33, 34], we opt for LSA to explore latent semantic information in our deterministic model fitting. Its simplicity, effectiveness, and non-interference with our deterministic approach make it an ideal choice.

To scrutinize the relationship between model hypotheses and data points via LSA, we initiate by constructing a preference matrix [21]. This matrix reflects the relationship between model hypotheses and data points based on the residual value. In essence, for a given data point $s_{i}$ and a model hypothesis $\theta_{j}$, the preference value is defined as:

where $d_{r}(s_{i},\theta_{j})$ is the Sampson distance [35] (residual value) between $\theta_{j}$ and $s_{i}$, and $\psi$ is a non-zero threshold. We note that, for a large residual value, the corresponding preference value is small; Conversely, for a small residual value, the corresponding preference value is large.

Then we can construct a preference matrix ${\bf P}_{n\times m}$ by Eq. (1) for $n$ data points and $m$ model hypotheses. Note that, the $m$ initial model hypotheses are generated by $\rho$ neighbors of each data point ($\rho$ is the number of a minimal subset), to preserve the deterministic nature of the proposed method. After that, we introduce LSA to decompose the preference matrix. That is, we decompose ${\bf P}_{n\times m}$ by singular value decomposition (SVD) as follows:

i.e.

where ${\bf U}$ and ${\bf V}$ are the orthogonal matrices of left and right singular vectors ${\bf U}{\bf U}^{T}={\bf V}{\bf V}^{T}=I$ (here $I$ is an identity matrix), respectively. ${\bf\Sigma}=diag(\sigma_{1},\ldots,\sigma_{r})$ is a diagonal matrix with singular values on the diagonal and the singular values are listed in non-increasing order, i.e., $\sigma_{1}\geq\sigma_{2}\geq\cdots\geq\sigma_{r}>0$, $r=rank({\bf P})$.

Then, the preference matrix is approximately decomposed by the top $k~{}{(\leq r)}$ singular values in ${\bf\Sigma}$, since the top $10\%$ (even $1\%$) of singular values account for over $99\%$ of all singular values, for SVD. i.e.,

Based on Eq. (4), we construct two latent semantic spaces (LSS) for data points and model hypotheses, respectively. For LSS of data points (we call DP-LSS), the points-to-points inner products are written as:

Thus, following LSA, we utilize the rows of ${\bf P}_{s}={\bf U}_{n\times k}{\bf\Sigma}_{k\times k}\in\mathbb{R}^{n\times k}$ as coordinates for DP-LSS. By Eq. (5), data points are project onto LSS, and meanwhile, the dimension $m$ of ${\bf P}\in\mathbb{R}^{n\times m}$ is also reduced to $k$.

For LSS of model hypotheses (we call MH-LSS), the hypotheses-to-hypotheses inner products are written as:

Thus, we adopt the rows of ${\bf P}_{\theta}={\bf V}_{m\times k}{\bf\Sigma}_{k\times k}$ as the coordinates for model hypotheses in MH-LSS. Also, the dimension $n$ of ${\bf P}\in\mathbb{R}^{n\times m}$ is reduced to $k$.

In this subsection, we propose a novel latent semantic consensus based sampling algorithm (called LSC-SA). To alleviate the bad influence of outliers, we first remove outliers by analyzing the distribution of the points in DP-LSS.

The points in DP-LSS corresponding to inliers are often situated farther from the origin of coordinates, while other points tend to be closer to the origin, as depicted in Fig. 2. This is attributed to the fact that the value of ${\bf P}_{s}$ is influenced by the preference value, and given that inliers typically receive a larger preference value than outliers.

Given a data point $s_{i}$ and the corresponding projected point $\hat{s}_{i}$ in DP-LSS, the distance between $\hat{s}_{i}$ and the origin in DP-LSS can be formulated as:

where ${\bf U^{\prime}}_{i}=[u_{i1}~{}u_{i2}~{}\cdots~{}u_{i{k}}]$ is the $i$-th row of ${\bf U}$. Then given the $i$-th row of ${\bf P}$, i.e., ${\bf P}_{i}=[p(s_{i},\theta_{1})~{}p(s_{i},\theta_{2})~{}\cdots~{}p(s_{i},\theta_{m})]$, we can decompose $p_{i}$ as:

For ${\bf P}_{i}$, the inner products are written as:

For ${\bf U^{\prime}}_{i}\sigma_{i}{\bf V}^{T}_{m\times{k}}$, the inner products are written as:

From Eqs. (7), (8), (9) and (10), we rewrite Eq. (7) as:

Therefore, the distance ${\bf D}_{\hat{s}}^{o}=\{\hat{d}_{\hat{s}_{i}}^{o}\}_{i=1,\ldots,n}$ between points and the origin in DP-LSS depends on the preference value. Leveraging the above characteristic allows us to effectively identify and remove outliers. To this end, we introduce information theory [36] to analyze the distance ${\bf D}_{\hat{s}}^{o}$. Specifically, we first measure the gap $g_{i}$ between $\hat{d}_{\hat{s}_{i}}^{o}$ and the maximum value in ${\bf D}_{\hat{s}}^{o}$ as:

Then, we compute the quantity of information provided by each mapped point $\hat{s}_{i}$:

where $\frac{g_{i}}{\sum_{i=1}^{n}g_{i}}$ represents the probability of $\hat{s}_{i}$ to be an outlier.

After that, we remove the points with quantity of information lower than an entropy value and retain the other points:

where $-\sum_{i=1}^{n}\big{(}\frac{g_{i}}{\sum_{j=1}^{n}g_{j}}\log\frac{g_{i}}{\sum_{j=1}^{n}g_{j}}\big{)}$ is the estimated entropy value.

After that, we integrate latent semantic consensus into DP-LSS to guide the sampling of subsets for model hypothesis generation. Specifically, the value of a point in DP-LSS is derived from the corresponding preference value, fostering similarity among inliers belonging to the same model instance. With the remaining points ${\bf\hat{S}}_{I}$, we search for $\rho$ (the minimum number of data points to generate a model hypothesis) neighbors for each point. Subsequently, we sample subsets from the input data points, with each subset consisting of neighbors from DP-LSS. In addition, to further refine the sampled subsets, we introduce the model hypothesis updating strategy [9]. This involves leveraging global residual information to mitigate sub-optimal results. The overall process is summarized in the proposed Latent Semantic Consensus-based Sampling Algorithm (LSC-SA), outlined in Algorithm 1.

In Algorithm 1, to select the best model hypotheses in the model hypothesis updating strategy, we assign a model hypothesis $\theta_{i}$ a positive weighting value [37]:

where $\delta({\theta_{i}})$ is the estimated inlier noise scale of the $i$-th model hypothesis, and ${b}({\theta_{i}})$ is the bandwidth of the $i$-th model hypothesis, and it is defined as [38]:

For the kernel function $\mathbf{EK}(\cdot)$, we employ the popular Epanechnikov kernel:

By Eq. (15), a good model hypothesis is assigned a large weight since it includes more inliers with small residual values.

In this subsection, we propose a novel latent semantic consensus based model selection algorithm (LSC-MSA). To mitigate the sensitivity on the distribution of input data points, we analyze MH-LSS for model selection. In the space of generated model hypotheses, the disparities in proportions between different categories are not as pronounced as in the data point space. As illustrated in the example in Fig. 1 (b), the smallest and largest ratios for different categories of data points are $8.57\%$ and $57.14\%$, respectively, while the corresponding ratios for different categories of model hypotheses are $15.27\%$ and $37.72\%$, respectively.

Firstly, we remove bad model hypotheses by the same manner as Eq. (14). This is because, MH-LSS includes the similar character as DP-LSS, that the points corresponding to good model hypotheses are often far from the origin of coordinates while the other points are close to the origin. Then, we formulate the model selection problem as a simple subspace recovery problem in MH-LSS based on the remaining model hypotheses ${\bm{\theta}}_{I}$.

Note that, in MH-LSS, the points corresponding to the model hypotheses of the same model instances generally belong to the same one-dimensional subspace. We make some discussions for this claim. Given the preference value of a model hypothesis $\theta_{i}$, i.e. ${\bf P}_{\theta_{i}}=[p(s_{1},\theta_{i})~{}p(s_{2},\theta_{i})~{}\cdots~{}p(s_{n},\theta_{i})]^{T}$, and the corresponding $i$-th row of ${\bf V}$, i.e. ${\bf V^{\prime}}_{i}=[v_{i1}~{}v_{i2}~{}\cdots~{}v_{i{k}}]$, we rewrite Eq. (6) as:

Then, we can obtain the following equation:

Finally, we obtain the coordinates ${\bf V^{\prime}}_{i}\sigma_{i}$ of $\theta_{i}$ in MH-LSS as:

We can see that, the coordinates of $\theta_{i}$ in MH-LSS depend on the preference value of $\theta_{i}$ to the input data points. Notably, the model hypotheses corresponding to the same model instance share similar preference to data points. Consequently, the projected points in MH-LSS corresponding to these hypotheses will exhibit the same subspace.

Then, we propose to cluster the remaining mapped points (${\hat{\bm{\theta}}}_{I}=\{\hat{\theta}_{1},\hat{\theta}_{2},\cdots,\hat{\theta}_{n_{I}}\}$) to several independent subspaces for subspace recovery, where each subspace corresponds to a model instance and each cluster of points belongs to the model instance. Theoretically, we can use a normal clustering method to cluster the remaining points in MH-LSS. However, we propose a simple but effective subspace recovery strategy to label the remaining points in MH-LSS. Specifically, we directly estimate several origin-lines in MH-LSS (lines passing through $\bf O$), using them for data point clustering.

Our goal is to estimate $k$ origin-lines that best capture the remaining points in MH-LSS. Notably, the proposed clustering strategy simplifies the intricate task of segmenting high-dimensional data, reducing it to the straightforward process of clustering points by estimating origin-lines in LSS.

For estimating an origin-line, it only requires to sample one point in MH-LSS to generate a model hypothesis of origin-line as the origin-line always passes through the origin of MH-LSS. To ensure with probability $\hat{\rho}$ that at least one all-inlier minimal subset is sampled, the number of minimal subsets $m_{I}$ required to sample is computed as:

where $\hat{\alpha}$ denotes the ratio of gross outliers and $\eta$ denotes the number of data points in a minimal subset (here $\eta=1$ as only one point is needed to estimate an origin-line). In our case, the ratio of gross outliers (i.e. bad model hypotheses) is small since we have removed most of gross outliers. Thus, we only need sample a very small number of the minimal subsets for the origin-line estimation. For example, for $\hat{p}=0.99$ and $\hat{\alpha}=0.5$, $m_{I}$ is approximately equal to $7$.

For the residual value between an origin-line $\vec{l}_{\hat{\theta}_{j}}$ (derived from a sampled point $\hat{\theta}_{j}$) and a point $\hat{\theta}_{i}$, as shown in Fig. 3, we can compute it as follows:

where $\langle\cdot,\cdot\rangle$ denotes the standard inner product.

After sampling a small number of model hypotheses, we adopt an integer linear program to estimate the $k$ origin-lines due to its effectiveness. The integer linear program is used to search for $k$ significant model hypotheses that cover the largest number of inliers of multiple model instances in data. For $n_{I}$ points in ${\bf\hat{\theta}}_{I}$ and $m_{I}$ model hypotheses $\vec{\bf L}_{I}$, we estimate the $k$ origin-lines via an integer linear program as [20]:

where $I_{\hat{\theta}_{i}}$ and $I_{\vec{l}_{\hat{\theta}_{j}}}$ denote the label of a point $\hat{\theta}_{i}$ and a model hypothesis $\vec{l}_{\hat{\theta}_{j}}$, respectively. If a point $\hat{\theta}_{i}$ (or a model hypothesis $\vec{l}_{\hat{\theta}_{j}}$) is selected to be an inlier of the returned model hypothesis, the label $I_{\hat{\theta}_{i}}=1$ (or $I_{\vec{l}_{\hat{\theta}_{j}}}=1$); Otherwise, $I_{\hat{\theta}_{i}}=0$ (or $I_{\vec{l}_{\hat{\theta}_{j}}}=0$). $\vec{l}_{\hat{\theta}_{j}}\ni\hat{\theta}_{i}$ represents that the point $\hat{\theta}_{i}$ belongs to the inliers of the model hypothesis $\vec{l}_{\hat{\theta}_{j}}$:

where $\beta$ is a threshold. We set $\beta$ to be a fixed value for different model fitting tasks, and the influence of its value on the proposed method will be discussed in Sec. 4.2.

After that, we can obtain the labels of the remaining model hypotheses, and we select the model hypotheses with the largest weighting scores by Eq. (15) for the same label as the final estimated model instances.

Based on the components described in the previous sections, we summarize the complete Latent Semantic Consensus based fitting method (called LSC) in Algorithm 2.

The proposed LSC method comprises a novel sampling algorithm and a new model selection algorithm. In essence, LSC not only analyzes the distributions of points in DP-LSS to generate high-quality model hypotheses but also exploits MH-LSS to accurately estimate model instances. Importantly, LSC involves deterministic nature, ensuring consistent and reliable solutions for model fitting.

For the computational complexity of LSC, in Algorithm 1, the neighborhood construction and the latent semantic space constructing take the main time. For the neighborhood construction, the time complexity is close to $O(n\log n)$. For constructing the latent semantic space (i.e. Step 2), we use truncated SVD where the time complexity depends on the number of singular values retained after truncation. Thus, the computational complexity is approximately $O(n^{2}*k)$, where ${k}$ is the dimension of MH-LSS. Step $3$-$7$ is based on the results of remaining model hypotheses (recall that we only deal with a very small number of high-quality model hypotheses), and their time complexity is close to $O(n)$. Therefore, the total complexity of LSC approximately amounts to $O(n^{2})$.

For synthetic data, we use all four datasets from [2] for line fitting, and the datasets from [1] for circle fitting.

For real images, we test all competing methods for single- and multiple-structural data. For multiple-structural data, we adopt all $38$ image pairs from the AdelaideRMF dataset [39] for homography and fundamental matrix estimation and all $155$ videos from $Hopkins$$155$ [40] for motion segmentation. For single-structural data, we uses $32,950$ image pairs to construct a dataset (called MS-COCO-F) from the MS-COCO images [41] for homography estimation and $12,455$ image pairs to construct a dataset (called YFCC100M-F) from the YFCC100M dataset [42] for the fundamental matrix estimation task.

To evaluate the performance of a model fitting method, we follow most of model fitting methods to compute the segmentation error (SE) as follows [16]:

There are two parameters for LSC, i.e., the threshold $\psi$ in Eq. (1) and the threshold $\beta$ in Eq. (26). To verify the influence of different values of parameters on the performance of LSC, we randomly select $1,000$ image pairs from the MS-COCO-F dataset for single-structural homography estimation, and $1,000$ image pairs from the YFCC100M-F dataset for single-structural fundamental matrix estimation, and all image pairs from the AdelaideRMF dataset for multiple-structural tasks.

For the threshold $\psi$, we report the quantitative results (the mean and standard deviation values) of SE and the CPU Time obtained by LSC with different values of $\psi$ ($0.01$-$0.10$) for the task of homography and fundamental matrix estimation in Fig. 4. Note that, the mean and standard deviation values are obtained by LSC on different image pairs for each $\psi$. We can see that, for homography estimation, LSC achieves stable values of SE with different values of $\psi$ on the MS-COCO-F dataset, but it obtains different values of SE on the AdelaideRMF datasets due to the influence of multiple structures. The CPU time used by LSC has not obvious change with different values of $\psi$ on the both datasets. We also find that LSC obtains the lowest values of SE when $\psi=0.05$ on the AdelaideRMF datasets. Thus, we set $\psi=0.05$ for homography estimation in the following experiments. For fundamental matrix estimation, LSC also achieves the same performance on the datasets with single and multiple structures as homography estimation, and it achieves the lowest values of SE when $\psi=0.01$ on the AdelaideRMF datasets. Thus, we set $\psi=0.01$ for fundamental matrix estimation in the following experiments. For the other tasks, we do not change the values of $\psi$ and set $\psi=0.01$.

For the threshold $\beta$, we report the quantitative results (the mean and standard deviation values) of SE and the CPU Time obtained by LSC with different values of $\beta$ ($0.1$-$1.0$) for the task of homography and fundamental matrix estimation in Fig. 5. Note that, we only test this experiment on the AdelaideRMF datasets since $\beta$ only affects the data with multiple structures. Recall that, we perform the model selection in the latent semantic space and regress all model fitting tasks to the subspace recovery problem, thus, we can set the same values of $\beta$ for all model fitting tasks. From Fig. 5, LSC obtains the lowest values of SE for homography and fundamental matrix estimation when $\beta=0.8$. Thus, in the following experiments, we set $\beta=0.8$.

In this section, we compare the proposed LSC with several state-of-the-art model fitting methods, including MSHF [1], RansaCov [20], T-linkage [21], RPA [19], Multi-link [22], CBG [17] and CLSA [2], for line and circle fitting on synthetic data.

In this subsection, we evaluate the performance of LSC on all $38$ image pairs from the AdelaideRMF dataset with data for two popular fitting tasks, i.e., homography and fundamental matrix estimation. For the competing methods, we add more fitting methods, i.e., RCMSA [43], Prog-X [44], SDF [9] and LGF [13], since they can deal with two-view fitting methods. To show the effectiveness of the proposed LSC, we also test it on two large datasets (i.e., the MS-COCO-F and YFCC100M-F datasets). We compare it with two deterministic fitting methods (i.e., SDF and LGF), and we run RANSAC as a baseline. In addition, we run two deep learning based methods (i.e., OANet [45] and ConvMatch [46]).

A sampling algorithm is very important for the final fitting performance, thus, we further discuss the sampling algorithm in this section. Specifically, we provide a quantitative comparison on all image pairs from the AdelaideRMF dataset with the ten state-of-the-art sampling methods, including RANSAC, NAPSAC [55], LO-RANSAC [15], G-MLESAC [56], PROSAC [14], Multi-GS [7], RCMSA [43], CBS [8], SDF [9] and LGF [13].

We report the total number of sampled minimal subsets and the ratio of all-inlier minimal subsets on the sampled minimal subsets (called the inlier-subset ratio) obtained by the competing methods within one second in Fig. 17. We can see that, most of random sampling methods achieve a large number of minimal subsets within one second, while three deterministic fitting methods (i.e., SDF, LGF and LSC-SA) only sample a few hundred subsets. This is because most of random sampling methods try to cover all model instances in data by increasing the number of subsets, in contrast, deterministic sampling methods often adopt a heuristic strategy to improve the quality of subsets while reducing the subsets including outliers. Thus, the inlier-subset ratios obtained by deterministic sampling methods are significantly higher than the ones obtained by random sampling methods.

For deterministic sampling methods, LSC-SA shows obvious advantages over SDF and LGF, that is, LSC-SA not only samples the most number of subsets among the three deterministic sampling methods, but also achieves the largest inlier-subset ratio.

To evaluate the impact of initialization sampling density on the proposed method, we test different numbers of initialization sampling subsets for the task of homography estimation and fundamental matrix estimation on the MS-COCO-F and YFCC100M-F dataset, respectively. We set the sampling number from $N/10$ to $2N$, increasing by $N/10$ each time, where $N$ represents the number of input correspondences. We report the quantitative results in Fig. 18.

We can see that, on the MS-COCO-F dataset, LSC achieves a relatively stable mean value of SE when the sampling number exceeds $N/5$. On the YFCC100M-F dataset, there is no significant fluctuation in SE at different sampling numbers. In terms of the CPU time, LSC also exhibits no significant variation. Thus, LSC is not sensitive to sampling initialization across different densities.

The proposed LSC includes an important components, i.e. LSC-MSA for model selection. To evaluate the impact of LSC-MSA, we test a new version LSC-DBSCAN that uses DBSCAN [57] to cluster the remaining points in MH-LSS for model selection. We perform LSC-MSA and LSC-DBSCAN on all image pairs of the AdelaideRMF dataset for the task of homography estimation and fundamental matrix estimation, and report SE in Fig. 19.

We can see that, for the homography estimation, LSC-MSA and LSC-DBSCAN are able to obtain good performance on $15$ out of the $19$ image pairs. LSC-MS still achieves low SE on the remaining four image pairs, but LSC-DBSCAN fails. For the fundamental matrix estimation, LSC-MSA and LSC-DBSCAN achieves the same values of SE on $10$ out of the $19$ image pairs, and LSC-MSA achieves lower values of SE than LSC-DBSCAN on all the remaining nine image pairs. This can show the effectiveness of LSC-MSA on the model selection for model fitting.