Hierarchical Line Matching Based on Line-Junction-Line Structure Descriptor and Local Homography Estimation
Kai Li, Jian Yao*, Xiaohu Lu
School of Remote Sensing and Information Engineering, Wuhan University, Wuhan, Hubei, P.R.China
*EMail: jian.yao@whu.edu.cn
*Web: http://www.scholat.com/jianyao http://cvrs.whu.edu.cn
[
] The executable files are released [download]. (26/1/2015).
[] The test dataset is added [download]. (26/1/2015).
Abstract
A novel hierarchical method for matching line segments from two images is proposed. Line segments are matched first in groups and then in individuals. While matched in groups, adjacent line segments are first intersected to form junctions and then used to construct structures called Line-Junction-Line (LJL), consisting of two adjacent lines segments and their intersecting junction. To reliably deal with the possible scale change between two images, we proposed to describe LJLs from multi-scale pyramids of images constructed from two original images with a robust descriptor. By evaluating their descriptor vector distances, some candidate LJL matches are obtained, which are then refined and expanded by an effective match-propagation strategy. Line segments, which cannot be matched in the form of LJL, are further matched in individuals by utilizing the local homographies estimated from their neighbor corresponding LJLs. Experimental results on a lot of image pairs captured from different scenes demonstrate the robustness of the proposed method both under various image transformations and in poorly-textured scenes. Compared with the state-of-the-art line matching methods, the proposed method has the superiority for quite more correct matches and higher accuracy in most cases.
Figure 1: The flowchart of the proposed algorithm.
Algorithm
The proposed line matching method matches line segments both in groups and in individuals under a hierarchical framework. The framework is comprised of three stages where line segments are matched in groups in the first two stages while in individuals in the third stage. The three-stage flowchart of the proposed line matching algorithm is illustrated in Figure 1. The first stage commences intersecting neighbor line segments to form junctions and then using them to construct the structures called Line-Junction-Line (LJL), consisting of two adjacent lines segments and their intersecting junction. To greatly reduce the effect of the scale change between two images to be matched, we proposed to build the Gaussian image pyramids for both images and the LJLs constructed in the original two images are adjusted to fit each one in the image pyramids and are described in that image by the proposed LJL descriptor. Figure 2(a) gives an illustration of the proposed LJL descriptor. A LJL descriptor is comprised of 16 gradient orientation histograms of 8 bins that are computed from the local patch around the junction of a LJL. Some initial LJL matches can be found by matching these LJLs according to their corresponding descriptor vector distances. These LJL matches are then refined and expanded in the second stage, where we propagate the LJL matches by iteratively adding new matches while deleting possibly false ones. Line segments fail to be matched in the form of LJL are further matched in individuals in the third stage by utilizing the estimated local homographies from neighbor corresponding LJLs. Figure 2(b) shows the way of matching individual line segments via the estimated local homography.
|
|
(a) |
(b) |
Figure 2: Illustrations of the two main contributions of the proposed method. (a): Describing a LJL. (b): Matching individual line segments via the estimated local homography.
Experimental Results
The algorithm was tested in various image pairs and Figures 3--10 show the line matching results on some representative ones. For better interpreting these results, please click the figures to view the original figures.
Figure 3. P1: illumination change. #DetectedLines: (572, 275), #TotalMatches: 217, #FalseMatches: 3, accuracy: 97.5%
Figure 4. P2: rotation change. #DetectedLines: (537, 556), #TotalMatches: 363, #FalseMatches: 1, accuracy: 99.7%
Figure 5. P3: viewpoint change. #DetectedLines: (1071, 1016), #TotalMatches: 792, #FalseMatches: 3, accuracy: 99.6%
Figure 6. P4: poorly-textured scene. #DetectedLines: (102, 82), #TotalMatches: 33, #FalseMatches: 1, accuracy: 97.0%
Figure 7. P5: scale & rotation change. #DetectedLines: (1334, 569), #TotalMatches: 151, #FalseMatches: 7, accuracy: 95.4%
Figure 8. P6: rotation change. #DetectedLines: (526, 398), #TotalMatches: 311, #FalseMatches: 2, accuracy: 99.4%
Figure 9. P7: image blur. #DetectedLines: (1700, 454), #TotalMatches: 334, #FalseMatches: 11, accuracy: 96.7%
Figure 10. P8: JPEG compression. #DetectedLines: (590, 1083), #TotalMatches: 356, #FalseMatches: 14, accuracy: 96.1%
Comparison with The-state-of-the-art Methods
Table 1 shows the comparative line matching results of the proposed method with three stage-of-the-art line matching methods: LPI [Fan, et al., 2012], LS [Wang, et al., 2009] and RPR [Li, et al., 2014]. For each of the three methods, the proposed method took its used line segments as input and generated line matching results. The dual elements shown in the table represent the number of correct matches and the accuracy, respectively. The last row represents the average accuracy of each method.
LPI lines |
LS lines |
RPR lines |
||||
Ours |
LPI |
Ours |
LS |
Ours |
RPR |
|
P1 |
(214, 97.5%) |
(136, 99.3%) |
(257, 99.2%) |
(189, 97.9%) |
(171, 97.2%) |
(124, 99.2%) |
P2 |
(362, 99.7%) |
(328, 99.4%) |
(579, 99.3%) |
(241, 99.6%) |
(298, 100%) |
(240, 100%) |
P3 |
(789, 99.6%) |
(735, 99.5%) |
(1229, 99.1%) |
(269, 99.3%) |
(699, 99.6%) |
(546, 99.6%) |
P4 |
(32, 97.0%) |
(16, 100%) |
(31, 96.9%) |
(42, 95.5%) |
(24, 100%) |
(23, 95.8%) |
P5 |
(144, 95.4%) |
(82, 94.3%) |
(33, 49.3) |
(0, 0) |
(118, 94.4) |
(16, 94.1) |
P6 |
(309, 99.4%) |
(276, 99.3%) |
(526, 99.1%) |
(214, 99.7%) |
(260, 97.7%) |
(124, 99.2%) |
P7 |
(323, 96.7) |
(82, 93.2%) |
(205, 94.0%) |
(17, 73.9%) |
(151, 92.1%) |
(0, 0) |
P8 |
(342, 96.1%) |
(225, 93.4%) |
(311, 95.4%) |
(126, 92.6%) |
(259, 95.6%) |
(137, 94.5%) |
97.7% |
97.3% |
91.5% |
82.3% |
97.1% |
85.3% |
|
Table 1: Comparative results of the proposed method with three state-of-the-art line matching methods.
Extreme Cases
To give a thorough evaluation of the robustness of the proposed method, some extremely challenging image pairs were employed for the experiments. LPI was also applied on these image pairs for the comparison. From the comparative results shown in Table 2, we can noticed that for these extreme cases, our method produced quite more correct matches than LPI and thus are more robust than it. For the aerial image pairs, we provided only the number of the total matches produced by our method, but not the numbers of correct matches. This is because the amount of total matches is so great (5748) that it is so hard to access the correctness of every match. But through access the correctness of the 100 samples among the total matches from different parts of the images, we observed that only 1 of the 100 samples is incorrect. A rough estimation of the accuracy of the total matches would thus be 99%. The implementation of LPI failed in this image pair, and the reason behind which may be that LPI requires too much memory to process such large two images and to match such great amounts of line segments that the computer cannot provide. For better interpreting these results, please click the figures to view the original figures.
Wide-baseline. #DetectedLines: (1007, 998) |
|
 |
 |
Ours: #TotalMatches: 178, #CorrectMatches: 133. |
LPI: #TotalMatches: 62, #CorrectMatches: 24. |
Wide-baseline. #DetectedLines: (509, 552) |
|
 |
 |
Ours: #TotalMatches: 81, #CorrectMatches: 66. |
LPI: #TotalMatches: 69, #CorrectMatches: 34. |
Wide-baseline & poorly-texture & illumination change. #DetectedLines: (198, 367) |
|
 |
 |
Ours: #TotalMatches: 75, #CorrectMatches: 54. |
LPI: #TotalMatches: 4, #CorrectMatches: 2. |
Illumination change. #DetectedLines: (1783, 315) |
|
 |
 |
Ours: #TotalMatches：236, #CorrectMatches: 233. |
LPI: #TotalMatches：83, #CorrectMatches: 81. |
Aerial Image (large scene). #DetectedLines: (18261, 15717) |
|
 |
Failed |
Ours: #TotalMatches: 5748. |
LPI: #TotalMatches: 0. |