Introduction

Feature point is a piece of information which is relevant to solving a certain application-related computational task. Feature points find their use in numerous applications such as image stitching, stereo correspondence, locating and tracking of a moving object, object detection and recognition, and others [1,2]. The ubiquitous usage of feature points is a direct consequence of their properties [3]:  Repeatability: Given two images of the same object or scene, a high percentage of the features detected on the scene visible in both images should be found in both images.  Informativeness: The intensity patterns underlying the detected features should show a lot of variation.  Locality: The features should be local, so as to reduce the probability of occlusion and to allow simple model approximations of the geometric and photometric deformations between two images.  Quantity: The number of detected features should be sufficiently large, such that a reasonable number of features are detected even on small objects.  Accuracy: The detected features should be accurately localized.  Efficiency: The detection of features in a new image should allow for time-critical applications.

Algorithms and methods that detect image feature points by making local decisions are called feature points detector. An abundance of image feature points detectors is known, most of which are based on a certain criterion -a heuristics that implicitly defines what a term feature point constitutes. Generally these heuristics can be classified into three categories [4]:  Gradient-based: A majority of image feature points detectors is based on computation of gradients of intensity function, for example Förstner [5], Harris [6], Shi-Tomasi [7].  Template-based: Feature points are found by comparing the intensity of surrounding pixels with that of center pixels which is governed by some template. The well-known template-based detectors are SUSAN [8], FAST [9], AGAST [10].  Contour-based: A feature point is defined as the intersecting point of two adjacent edge lines, examples are DoG-curve [11],

ANDD [12].

However, formulating a heuristics for an image feature points detector requires a well-formed application-dependent definition of the term feature point, which in turn requires some level of expertise in the application domain. Moreover, a strictly stated criterion, although sharpening performance, diminishes its flexibility to adjust to a particular problem, which renders all the possible usages outside the destined application moot.

The goal of this work is to dispense with defining the term feature point altogether and focus on the properties we wish the feature points to possess. With that goal in mind we resort to machine learning methods. Image raw moments and image moment invariants are used along with some other local characteristics of image points to form a feature space of a learning algorithm. The detector is trained to solve a specific problem on a relevant and carefully collected training set. This effectively defines the term feature point implicitly, since it's inductively inferred from the training examples.

The proposed method is described in full detail in section 2, along with the learning algorithm, its feature space and the procedures for collecting training and test sets. Evaluation criteria of a trained detector's performance and the results of experimental evaluation are described in section 3. We conclude with a discussion of these results.

Proposed method

The proposed learning-based feature points detector is based on the idea of transforming detection task into a classification task as suggested in [13], which boils down to training the detector's classifier on a set of the desired responses.

Feature space

The first step towards constructing our detector is to define the classifier's feature space, which is an ℝ 15 vector space. Each pixel of an image 𝐼[𝑥, 𝑦] is mapped to a certain vector in this feature space using a locally defined operator 𝑃 9×9 → ℝ 15 , where 𝑃 = {𝑛: 0 ≤ 𝑛 < 256} is a set of intensities of a grayscale image. The features of the feature space are described below.

The first two features are standard deviation of a standardized local area, 𝜙 1 , and standard deviation divided by the norm of the local area, 𝜙 2 :

𝜙 1 = √ 1 80 ∑ ∑ 1 𝑛 2 (𝐼[𝑥 + 𝑖, 𝑦 + 𝑗] − 𝐼 ̅ ) 2 4 𝑗=−4 4 𝑖=−4 , 𝜙 2 = 𝜙 1 𝑛 ,(1)

where norm 𝑛 and local mean 𝐼 ̅ are defined:

𝐼 ̅ = 1 81 ∑ ∑ 𝐼[𝑥 + 𝑖, 𝑦 + 𝑗] 4 𝑗=−4 4 𝑖=−4 , 𝑛 = √∑ ∑ (𝐼[𝑥 + 𝑖, 𝑦 + 𝑗]) 2 4 𝑗=−4 4 𝑖=−4 .

The use of these features is motivated by their sensitivity to monotonous and textured areas.

The next four features are chosen to be central image moments of a local image area: 𝜙 𝑡+3 = 𝜇 𝑡𝑡 , 0 ≤ 𝑡 ≤ 3. The central moments are defined [14]:

𝜇 𝑖𝑗 = ∑ ∑ 𝑘 𝑖 • 𝑙 𝑗 • 1 81 𝐼[𝑥 + 𝑘, 𝑦 + 𝑙] 4 𝑙=−4 4 𝑘=−4 . (2)

To induce invariance to rotation transformations the following Hu invariant image moments and Flusser moments are used [15,16]: (

𝜙 7 = 𝜇 20 + 𝜇 02 , 𝜙 8 = (𝜇 20 − 𝜇 02 ) 2 + 4𝜇)3

Moments calculation is an intensive computational task that requires of a lot of operations. To reduce the number of arithmetical operations we apply the recursive method of moments calculation based on the use of integer factorial polynomials [16].

The last feature that characterizes misalignment of centre of local area and its centre of mass is defined:

𝜙 15 = √(𝑥 𝑐 − 𝑥) 2 + (𝑦 𝑐 − 𝑦) 2 , (4)

where 𝑥 𝑐 = 𝜇 10 /𝜇 00 and 𝑦 с = 𝜇 01 /𝜇 00 . The set of the features 𝜙 𝑖 , 1 ≤ 𝑖 ≤ 15, defined by ( 1) -( 4), with a usual addition and scalar multiplication operations form the feature vector space.

Tuning the detector 2.2.1. Collecting a training set

Tuning the detector requires a training set that consists of the desired detector's responses. Depending on the application there are various ways the set can be obtained:  manually, involving experts of the domain;  automatically, using well-known feature points detectors such as Harris or Canny;  combining the two.

In case there is a human involvement of any kind it is inevitable for a training set to contain a so called training noise [17]. Besides, in a typical scenario a number of feature points is small compared to the other points. To alleviate these negative effects the neighbouring points of the feature points can be considered feature points as well.

Provided an application requires high level of robustness to certain transformations, a training set can be enlarged to contain the so called virtual examples [18]. To this end every image used to form a training set is transformed according to some transformation. Since the parameters of that transformation are known, the elements of the original image can be mapped onto the transformed image, which makes it possible to extract feature vectors of the points of the transformed image that correspond to the feature points of the original image. These new feature vectors are the virtual examples that convey information about various effects the transformation have on the feature vectors.

Training a classifier

With a training set at hand we can pose and solve a supervised learning problem. Since the number of the feature vectors in a training set is typically quite large we chose to apply nonparametric probability density estimation approach. Let 𝐷 = {(𝒙 𝑖 , 𝑦 𝑖 )} 𝑖=1 𝑁 denote training set, where 𝒙 𝑖 is a feature vector, 𝑦 𝑖 is its label, 𝑦 𝑖 ∈ {𝐶 1 , 𝐶 2 }. 𝐶 1 corresponds to feature points and 𝐶 2 corresponds to the other points. Then, an estimation of conditional probability density function is defined as follows:

𝑝(𝒙|𝐶 𝑖 ) ∝ ∑ [𝑦 𝑗 = 𝐶 𝑖 ] 𝑁 𝑗=1 𝐾 ( ‖𝒙−𝒙 𝑗 ‖ ℎ ), (5)

where 𝐾 is a kernel function, ℎ is kernel's width parameter. By the Bayes' Theorem:

𝑝(𝐶 𝑖 |𝒙) ∝ 𝑝(𝒙|𝐶 𝑖 ) • 𝜋 ̂𝑖,(6)

where 𝜋 ̂𝑖 is an estimate of prior probability of i th class:

𝜋 ̂𝑖 = 1 𝑁 ∑ [𝑦 𝑗 = 𝐶 𝑖 ] 𝑁 𝑗=1 . (7)

Define a characteristic function of a feature point 𝑙(𝒙):

𝑙(𝒙) = 𝑙𝑛(𝑝(𝐶 1 |𝒙)) − 𝑙𝑛(𝑝(𝐶 2 |𝒙)).(8)

In order to smooth the detector's response we filter the characteristic function 𝑙(𝒙) using a local peak filter. The peak filter suppresses non-maximal values in a local 3×3 neighbourhood of the point 𝒙:

𝑙 ̃(𝒙) = { 𝑙(𝒙), 𝑙(𝒙) > 𝑙(𝒈) + 𝛿 ∀𝒈 ∈ 𝑊 ∖ {𝒙} 0, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 , (9)

where 𝑊 is a set of all feature vectors from the local neighbourhood, 𝛿is some threshold. From ( 8) and ( 9) we infer the decision rule:

𝑦(𝒙) = { 𝐶 1 , 𝑙 ̃(𝒙) > 𝑡 = 𝑙𝑛 ( 𝜋 ̂2 𝜋 ̂1) 𝐶 2 , 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 . (10)

Experimental evaluation

Experimental setup

To experimentally evaluate the proposed detector we built a set of images. The set contains a series of 10 overlapping images of 6 different scenes, 60 images in total. Figure 1 shows three images of one of these scenes. Each of the 6 groups of images was split in relation 8:2 to form training set 𝐷 and test set 𝐶, respectively. We chose to use Harris [6] corner detector to detect feature points. The training set was enlarged by the virtual examples as described in section 2.2.1 and the transformations that were applied are described in section 3.3.

Evaluation of training accuracy

Let 𝑉 = {(𝒙 𝑖 , 𝑦 𝑖 )} 𝑖=1 𝑁 be training or test set. The primary criterion of detector's performance on the set V is its accuracy:

𝐴(𝑉) = 1 𝑁 ∑ [𝑦(𝒙 𝑖 ) = 𝑦 𝑖 ] 𝑁 𝑖=1 . (11)

Besides the accuracy two more criteria are used: precision 𝑃 and recall 𝑅 [19]. Precision is the fraction of relevant instances over the retrieved instances, while recall is the fraction of relevant instances among the retrieved ones over the total number of relevant instances in the set.

Let 𝐹𝑃, 𝐹𝑁 and 𝑇𝑃 denote false positives, false negatives and true positives, respectively. Then,

𝐹𝑃(𝑉) = ∑ [𝑦(𝒙 𝑖 ) = 𝐶 1 ] • [𝑦 𝑖 = 𝐶 2 ] 𝑁 𝑖=1

,

𝐹𝑁(𝑉) = ∑ [𝑦(𝒙 𝑖 ) = 𝐶 2 ] • [𝑦 𝑖 = 𝐶 1 ] 𝑁 𝑖=1 , 𝑇𝑃(𝑉) = ∑ [𝑦(𝒙 𝑖 ) = 𝑦 𝑖 ] 𝑁 𝑖=1 .(12)

Precision and recall are defined: .

(

)13

The proposed detector was first trained on the training set. Accuracy, precision and recall were evaluated on the training set 𝐷 and test set 𝐶. The results are shown in table 1. Taking into account a fairly large size of the sets, the data suggests an adequate quality of training.

Repeatability evaluation of the detector

As mentioned in introduction, repeatability is one of the most important properties of the feature points. Along with its importance, repeatability allows for an objective and qualitative evaluation. Hence, we used repeatability to evaluate the performance of the proposed detector.

The procedure for repeatability evaluation is outlined below.

 An original image is used to find a set of feature points 𝑃 𝑜 .  The original image is transformed by one of the transformations (cf. the next list below).  The transformed image is used to find a set of feature points 𝑃 𝑡 .  Since parameters of the transformation are known, coordinates of the points 𝑃 𝑜 of the original image can be mapped onto the transformed image. Thus, the points in the set 𝑃 𝑜 are mapped onto the transformed image, forming a set 𝑃 𝑚 .  The sets 𝑃 𝑚 and 𝑃 𝑡 are matched. Two points 𝑎 ∈ 𝑃 𝑚 and 𝑏 ∈ 𝑃 𝑡 are considered equal if 𝑎 ∈ 𝑉 𝜀 (𝑏), 𝜀 = 2.0.  As a result of the comparison performed in the previous step we find three sets of points: 𝑃 𝑇𝑃 are the points found on both sets, 𝑃 𝐹𝑃 are new points that were not found on the original image but were found on the transformed image, 𝑃 𝐹𝑁 are the missed points that were found on the original image and were not found on the transformed image. The cardinalities of these sets are, respectively, 𝑇𝑃, 𝐹𝑃 and 𝐹𝑁 values of the proposed detector. These values are used to calculate the detector's accuracy, precision and recall.

To evaluate repeatability we used the following transformations of the images:  rotation by angle 𝛼, −45°≤ 𝛼 ≤ 45°, 𝛼 is increased by 3°;  sub-pixel shift by 𝑡, 0.25 ≤ 𝑡 ≤ 0.75, 𝑡 is increased by 0.05;  scaling by 𝑠, 0.5 ≤ 𝑠 < 1.5, 𝑠 is increased by 0.1

The results of the repeatability evaluation of the proposed detector that was trained on the training set 𝐷 are shown on fig. 2. The detector's performance can be considered adequate on rotated images for −9°< 𝛼 < 9° and on scaled images for 0.8 ≤ 𝑠 ≤ 1.2. The performance on shifted images is high for the whole range of the parameter 𝑡.

Conclusion

In this paper we investigated a relatively new approach to feature point detection. Contrary to the standard approach to the problem, we didn't formulate any heuristics-based definition of the term feature point but tried to infer it inductively using the methods of machine learning and a representative training set. This enabled us to tune the proposed detector to a specific problem at hand. The results of the experimental evaluation of the detector verify that such a tuning is in fact possible. Moreover, the detector showed acceptable robustness to rotation and scaling transformation, and high robustness to sub-pixel shift transformation. This suggests a great potential of the learning-based approach to feature points detection.