IEEE GEOSCIENCE AND REMOTE SENSING LETTERS, VOL. 10, NO. 6, NOVEMBER 2013 1429
Bi-SOGC: A Graph Matching Approach Based on
Bilateral KNN Spatial Orders Around Geometric
Centers for Remote Sensing Image Registration
Ming Zhao, Bowen An, Yongpeng Wu, Member, IEEE, and Changqing Lin
Abstract—In this letter, Bilateral K Nearest Neighbors Spatial
Orders around Geometric Centers (Bi-SOGC) is presented to
match feature points for remote sensing images with large affine
transformation, similar patterns or multispectral images. In Bi-
SOGC, both the bilateral adjacent relations and the spatial angu-
lar orders are considered. Bilateral K Nearest Neighbors (BiKNN)
descriptors are proposed to describe the adjacent information.
The vertices with maximum BiKNN difference are deemed as
candidate outliers. The invariant spatial angular orders for affine
transformation are used to deal with outliers in pseudo isomorphic
structures, geometric centers are taken as the reference points.
To increase the correct matching points and eliminate stubborn
outliers, a recovery strategy utilizes the addition of fresh inliers
to break down the stabilized pseudo graphs of the residual sets.
Experimental results demonstrate the superior performance of
this algorithm under various conditions for remote sensing images.
Index Terms—Graph matching, image registration, remote
sensing images, spatial orders.
I. INTRODUCTION
I
MAGE registration is a crucial preprocessing technology
for image analysis, which has been widely applied to re-
mote sensing, computer vision and pattern recognition [1], [2].
Feature matching in registration process is a challenging step
to determine reliable corresponding relationships of detected
features between the images to be registered.
For remote sensing images, feature matching is interfered
with various factors, such as the large affine transformation
and similar patterns caused by different or large field of views.
Another intractable issue is the multispectral image registra-
tion, of which the gray-level values at the same areas differ
from each other. Compared by Mikolajzyk [3], Scale Invariant
Feature Transform (SIFT) [4] is the best among intensity-based
descriptors for local interest regions, which is invariant to image
Manuscript received December 11, 2012; revised March 6, 2013; accepted
April 14, 2013. Date of publication June 17, 2013; date of current version
October 10, 2013. This work was supported in part by the National Natural
Science Foundation of China under Grants 61302132 and 61171126, the In-
novation Program of Shanghai Municipal Education Commission under Grant
11ZZ142, and the Shanghai Municipal Natural Science Foundation under Grant
11ZR1415200.
M. Zhao is with the Department of Logistics Engineering, Shanghai Mar-
itime University, Shanghai 201306, China (e-mail: mingzhao@shmtu.edu.cn).
B. An is with the Department of Information Engineering, Shanghai Mar-
itime University, Shanghai 201306, China (e-mail: bwan@shmtu.edu.cn).
Y. Wu is with the National Mobile Communications Research Laboratory,
Southeast University, Nanjing 210096, China (e-mail: ypwu@seu.edu.cn).
C. Lin is with Shanghai Institute of Technical Physics, Chinese Academy of
Sciences, Shanghai 200083, China (e-mail: hellososo2009@163.com).
Color versions of one or more of the figures in this paper are available online
at http://ieeexplore.ieee.org.
Digital Object Identifier 10.1109/LGRS.2013.2259612
scaling and rotations. Nevertheless, SIFT is partially invariant
to intensity change and shear deformations [5]. Therefore,
only relying upon the image intensity in feature matching is
insufficient [6], [7], and spatial relations need to be considered.
A classic spatial-based approach called Random Sample Con-
sensus (RANSAC) estimates transformation parameters from
initial matching sets, but it cannot deal with large proportion
of outliers. Aguilar et al. introduced a simple method named
Graph Transformation Matching (GTM) [8] based on matching
K Nearest Neighbor (KNN) graphs with limitations of distances
to remove outliers. However, it may not be adequate to deal
with those outliers with the same local neighbor structures
called pseudo isomorphic structures. Besides, inliers with dif-
ferent neighbor structures might be removed arbitrarily [9].
Liu et al. proposed Restricted Spatial Orders Constraints
(RSOC) algorithm [ 10], which integrated the two-way spa-
tial order constraints and the transformation error restrictions.
However, the convergence rates and accuracy depend on trans-
formation models and the initial parameter settings. Also, the
cyclic string matching for spatial orders is very time consuming
[11]. Izadi et al. proposed Weighted Graph Transformation
Matching (WGTM) algorithm [9]. Utilizing the angular dis-
tances between edges that connect a feature point to its KNN
as the weight, WGTM can only deal with pseudo isomorphic
structures to a certain extent. This arises because angular dis-
tance is only invariant with respect to scales and rotations,
and shear deformations are not considered in that case.
In this letter, we propose a so called Bilateral KNN Spatial
Orders around Geometric Centers (Bi-SOGC) graph matching
algorithm, and Bilateral K Nearest Neighbors (BiKNN) and
spatial orders are considered. First, BiKNN is presented as
the bilateral graph descriptor. Then, the spatial orders around
geometric centers (SOGC) are given, which are invariant to
rotations, scaling and shear deformations. Point matching is
formulated as comparison with angular orders between adjacent
point pairs. In case of the inliers surrounded by outliers as their
KNN points and some inliers with cyclic adjacent orders, a
recovering strategy is designed to bring them back. Likewise,
with the addition of recovered inliers, the stubborn outliers in
the residual sets might be deleted. Thus, the performance of
feature point matching is significantly improved.
II. B
ILATERAL KNN SPATIAL ORDERS AROUND
GEOMETRIC CENTERS (BI-SOGC)
The input of feature matching algorithms is the one-to-one
correspondence between a reference image and an image to
be registered. Since the aforementioned ambiguity in the initial
1545-598X © 2013 IEEE
资源评论
