is less than two pixels. In these experiments, the top eight

nearest neighbors are retained for each feature point. Only

approximately 60 percent correct matches appear in the first

nearest neighbor. Figure 1 shows the experiment result. To

find additional correct matches, considering multiple nearest

neighbors is valuable during the matching process (retain-

ing the top four nearest neighbors is an appropriate choice),

especially for images that are difficult to match.

Additional algorithms have been proposed in literature

(Kang

, 2014), most of which employ the geometrical

consistency between features. Relaxing labeling (Joglekar

, 2014; Kittler, 1997; Zhang

, 1995) is one of the effec-

tive methods to reject incompatible matches. To some extent,

it is similar to the Hough transform method (Kittler, 2000) in

two ways. First, they both choose geometrical consistency

criterions. Then, matches with extra support are selected as

correct matches by finding support from neighbors. However,

relaxing labeling is performed iteratively, whereas Hough

transform is not.

In the image retrieval field, methods based on geometri-

cal consistency have been proposed in recent years, such

as geometric coding (Zhou

, 2013) and weak geometric

consistency (Jegou

, 2008). Geometric coding encodes

the spatial relationships of local feature points and itera-

tively removes matches that cause the largest inconsistency

in the geometry structure. The assumption of weak geometric

consistency suggests that the matched features should have

similar scale and rotation changes. In those methods, the scale

and orientation information should be provided by the feature

extraction and description algorithms, such as

SIFT

.

In this paper, a candidate match filter based on Hough

transform (Hough, 1962) is proposed, namely, the geometric

consistency voting strategy. Hough transform has been widely

used in many applications for many years (Ballard, 1981;

Illingworth and Kittler, 1988; Razavi

, 2012; Woodford

, 2014). This paper provides a detailed description of

the application of Hough transform in filtering initial candi-

date matches. Only two parameters, namely, the scale and

the rotation between images, are used to form the parameter

space in Hough transform. Thus, it works better when dealing

with a low ratio of inliers. The method can handle multiple

nearest neighbors. Furthermore, the criteria to decide whether

a match is an inlier or not are straightforward. It is not a

replacement of the

RANSAC

-like method because our method

is unsuitable for working with the rigorous transformation

model between images (the epipolar geometry constraint). It

is suitable to be used as a preprocessing step of other outlier

removal methods. Good matching results can be obtained

even when the ratio of inliers is less than 10 percent when

combining our method and the

RANSAC

-like method.

The paper is organized as follows: The basic mechanism

of Hough transform is introduced first. Then, the process in-

volved in using Hough transform to remove incorrect matches

is described. Experiments and conclusions are presented in

the final section.

Basic Mechanism of Hough Transform

Hough transform uses the internal relationship between

two subjects (e.g., feature locations and the transformation

parameters) to construct a voting mechanism. Useful informa-

tion can be revealed through an analysis of the peaks of votes.

Taking the classic problem of finding straight lines as an

example, Hough transform can find the existence of straight

lines from a given distribution pattern of feature points. Sup-

pose that a straight line can be expressed by

. All

feature points (

) on this line share the same parameters (

). From another perspective, a point (

) in feature space

can determine a straight line,

in the parameter

space. Considering that these feature points share the same

parameters, straight lines determined by these feature points

will intersect into one point (

) in the parameter space, as

illustrated in Figure 2.

The parameter space is discretized into a two-dimensional

accumulate array by intervals. Then, the voting process can

be performed as follows. The accumulate array bins are ini-

tialized to zero. Then, for each feature point, the votes of bins

which are passed through by the straight line determined by

this feature point are increased. Consequently, array bins near

position (

) will have most of the votes, thereby forming a

Figure 1. Proportion of the first eight nearest neighbors in total

correct matches.

Figure 2. Hough transform uses the relationship between features and parameters to detect straight lines.

560

PHOTOGRAMMETRIC ENGINEERING & REMOTE SENSING

SEO Version