1241 
EFFICIENT CORRESPONDENCE CRITERION FOR GRIDDED DEM CO 
REGISTRATION 
ZHANG Tonggang*, CEN Minyi, REN Zizhen, YANG Ronghao, FENG YiCong 
Department of Surveying Engineering, School of Civil Engineering, Southwest Jiaotong University, Chengdu 610031, 
China - chnztg@gmail.com 
Commission IV, WG IV/9 
KEY WORDS: Co-Registration, Correspondence Criterion, DEM, Iterative Closest Points 
ABSTRACT: 
Multi-temporal DEM co-registration provides an efficient technique for automatic analyzing the terrestrial changes caused by the 
geological hazards. Because this technique does not require any ground control points (GCPs), it can bring us many benefits: 1) 
avoid the GCP establishment, which is a cost and labor- intensive task; 2) quick response to the natural hazards, especially to the 
landslides and debris-flows; 3)make full use of remote sensing data obtained before the events. It is very difficult to obtain effective 
GCP owing to the terrestrial changes, even impossible; 4) analyze the region could not access. Iterative closest points (ICP) is the 
standard algorithm for surface matching in computer vision and pattern recognition. Its computational efficiency is slower and only 
suit for relative small data set. It adopts an exhaustive search strategy to find the point-to-point or point-to-normal corresponding 
pairs. It is very time-consuming, and consumes about 95% time of the whole matching process. Although many modifications have 
reported to speed up the corresponding pairs searching, it still could not meet the requirement for co-registering the large gridded 
DEM used in geosciences. This paper proposes an efficiency correspondence criterion for gridded DEM matching, called normal 
correspondence criterion (NCC), which finds the corresponding points alone the reference DEM normal vector and is optimized with 
a focus on the gridded date set. The experimental results show that the corresponding points can be determined within no more than 6 
iterations in most cases, which yields high efficiency to DEM co-registration. According to the numerous experimental results based 
on the simulated data sets, DEM co-registration with NCC only use 1/10 time than that used by ICP, and slight larger convergence 
range. 
1. INTRODUCTION 
The surface matching is an important task in many applications, 
such as the scene modeling(Vogtle and Steinle 2000; Rabbani, 
Dijkman et al. 2007), change detection(Zhang, Cen et al. 2006) 
and quality inspection(Thoma, Gupta et al. 2005). Among 
methods have been reported, Iterative Closest Point (ICP) (Besl 
and Mckay 1992)algorithm has been recognized as the standard 
method for matching surface in computer vision and pattern 
recognition(Chetverikov, Stepanov et al. 2005). This algorithm 
contains three main steps: 1) search the nearest point-to-point or 
point-to-tangent plane pairs in two surfaces; 2) find the 
transformation by minimizing the mean squared distance 
between the paired point-to-point or point-to-surface pairs; 3) 
apply the derived transformation to second surface and then 
update the mean squared distance. The above three steps are 
iterated to give a most optimal transformation, and also the 
iterations have been proved to be convergence. In this paper, we 
address the problem of surface matching at the point level. The 
main contribution of this paper is proposing an efficient 
correspondence criterion, which reduces the most 
correspondence search. 
This work was motivated by the lower efficiency of ICP and its 
variant methods, which usually require heavily computation. 
The point-to-point correspondence criterion proposed by Besl 
and Paul (Besl and Mckay 1992) uses an exhaustive search 
strategy. The computational complexity of the original ICP is of 
order 0\mn). m and n are the size of the first and second 
surface, respectively. 95% run-time is consumed by the 
searching the correspondence points(Chetverikov 1991). 
Moreover, this correspondence criterion impliedly requires each 
point in second surface has one counterpart in first surface. The 
point-to-tangent plane correspondence criterion proposed by 
Chen(Chen and Medioni 1999) also requires the searching 
process, calculating the tangent plane and normal vector for 
every iteration. This correspondence criterion is much more 
complex, and also occupies most computational time. Both of 
them are difficult to work with the larger-size digital surface. In 
others words, their application is very limited. 
2. CORRESPONDENCE CRITERION FOR GRIDDED 
DEM 
2.1 The proposed correspondence criterion 
The surface normal vector on P', an arbitrary point on the first 
surface, will intersect the transformed second surface, the 
intersection point is assumed to be P . The P' and P are then 
called corresponding points. This correspondence criterion is 
called normal direction correspondence criterion (NDCC), and 
it can be described as 
(1) 
where t is the transform, and R is the 3 by 3 rotation matrix, 
Cl(P[) is the neighboring plane centered on P. 
Corresponding Author