A Multiobjective Approach to Homography Estimation

Abstract

In several machine vision problems, a relevant issue is the estimation of homographies between two different perspectives that hold an extensive set of abnormal data. A method to find such estimation is the random sampling consensus (RANSAC); in this, the goal is to maximize the number of matching points given a permissible error (Pe), according to a candidate model. However, those objectives are in conflict: a low Pe value increases the accuracy of the model but degrades its generalization ability that refers to the number of matching points that tolerate noisy data, whereas a high Pe value improves the noise tolerance of the model but adversely drives the process to false detections. This work considers the estimation process as a multiobjective optimization problem that seeks to maximize the number of matching points whereas Pe is simultaneously minimized. In order to solve the multiobjective formulation, two different evolutionary algorithms have been explored: the Nondominated Sorting Genetic Algorithm II (NSGA-II) and the Nondominated Sorting Differential Evolution (NSDE). Results considering acknowledged quality measures among original and transformed images over a well-known image benchmark show superior performance of the proposal than Random Sample Consensus algorithm.

Valentin Osuna-Enciso 1 and Erik Cuevas 2 and Diego Oliva 2,3 and Virgilio Zúñiga 1 and Marco Perez-Cisneros 1 and Daniel Zaldivar 2

Academic Editor:Yufeng Zheng

1, Sciences Division, Centro Universitario de Tonala of Universidad de Guadalajara, 45400 Guadalajara, JAL, Mexico
2, Electronic Division, Centro Universitario de Ciencias Exactas e Ingenierias of Universidad de Guadalajara, 44430 Guadalajara, JAL, Mexico
3, Computer Sciences Department, Tecnologico de Monterrey Campus Guadalajara, 45201 Guadalajara, JAL, Mexico

Received 4 June 2015; Accepted 4 October 2015; 28 December 2015

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

A homography is a transformation that maps points of interest by considering movements as translation, rotation, skewing, scaling, and projection among image planes, all of them contained into a single, invertible matrix. In general terms, those displacements could be considered to be belonging to three cases: [figure omitted; refer to PDF] an object moving in front of a static camera, [figure omitted; refer to PDF] a static scene captured by a moving camera, and [figure omitted; refer to PDF] multiple cameras from different viewpoints. In either case, those approximations simplify the utilization of image sequences to construct panoramic views [1-3], to increment resolution in low quality imagery [4-6], to remove camera movements when studying the motion of an object into a video [7], and to control the position of robots [8-10], among other uses [11-13].

Taking a set of experimental data as a base, in a modeling problem there exist two data types: those that can be adjusted to a model with a certain probability (also known as inliers) and those that are not related to the model (e.g., outliers). There are several algorithms specialized in solving this classification problem; one of such techniques is the Random Sample Consensus (RANSAC) [14].

In the algorithm, minimum subsets of experimental data are randomly taken, and a model is proposed and evaluated according to a permissible error (Pe), in order to determine how well the model adjusts to the data [15]. This process is repeated until a number of iterations are completed, and the model with the maximum number of inliers is taken.

Even considering that RANSAC is a robust and simple algorithm, it has some drawbacks [16-18], two of which are the high dependency between the number of matching points (model quality) and the permissible error. In this work, it is considered that those disadvantages belong to a multiobjective optimization problem. On the one hand, due to the random nature of RANSAC, achieving improvements in the quantity of inliers implies more iterations in order to discard unadjusted data to the proposed model. On the other hand, the number of matching points conflictingly depends on the permissible error (Pe). A low Pe value increases the accuracy of the model but degrades its generalization ability to tolerate noisy data (number of matching points). By contrast, a high Pe value improves the noise tolerance of the model but adversely drives the process to false detections. The main error source in the model estimation procedure arises from defining the Pe value with no consideration of the relationship between the dataset and the model.

In order to make the RANSAC algorithm more efficient, some improvements have been suggested; for instance, in the algorithm called MLESAC [19] it is considered that the inliers into the images will follow a Gaussian distribution whereas the outliers are considered as uniformly positioned; according to that, the voting process is achieved through maximizing the likelihood and the original RANSAC. The SIMFIT method [20] proposed the forecasting of the permissible error, through an iterative reestimation of that value, until the model is adjusted to the experimental data. Some other variants to the original RANSAC are the projection-pursuit method, the Two-Step Scale Estimator, and the CC-RANSAC [15, 21, 22], all of them focused on maximizing the number of inliers by making more searches into the data and therefore making the complete process more expensive, computationally speaking. In such sense, an algorithm that tries to reduce the computational cost is the one proposed in [17], where the maximization of the inliers is achieved by using a metaheuristic technique, called Harmony Search.

Nevertheless the mentioned improvements, the search strategy used in the mentioned articles (with exception of [17]), are more close to random walking, and therefore those approaches are computationally expensive. Moreover, in all the cases only one objective function is considered, usually related to the number of matching points, while the permissible error is left behind. In accordance with that, and in order to overcome the typical RANSAC problems, we propose to visualize the RANSAC operation as a multiobjective problem solved by an evolutionary algorithm. Under such point of view, at each iteration, new candidate solutions are built by using evolutionary operators taking into account the quality of the previously generated models, rather than purely random, reducing significantly the number of iterations. Likewise, new objective functions can be added to incorporate other elements that allow an accurate evaluation of the quality of a candidate model.

When an optimization problem involves more than one objective function, the procedure of finding one or more optimum solutions is known as multiobjective optimization (MO) [23]. Under MO, different solutions produce conflicting scenarios among the objectives [24]. Contrary to single objective optimization, in MO it is usually difficult to find one optimal solution. Instead, algorithms for optimizing multiobjective problems try to find a family of points known as the Pareto optimal set [25]. These points verify that there is no different feasible solution which strictly improves one component of the objective function vector without worsening at least one of the remaining ones. Evolutionary algorithms (EAs) are considered the most adequate methods for solving complex MO problems, due mainly they are many times capable of maintaining a good diversity [26], can extend to multiple populations [27], as well as can work with a variety of problems such as discrete ones [28]. Several variants of nondominated sorting as well as new methods have been proposed in recent years in order to solve problems related to feature selection [29], community detection [30], among other issues [24, 31]; however, the Nondominated Sorting Genetic Algorithm II (NSGA-II) [32] and the Nondominated Sorting Differential Evolution (NSDE) [31] are some of the most representative.

In this paper, the estimation process is considered as a multiobjective problem where the number of matching points and the permissible error (Pe) are simultaneously optimized. In order to solve the multiobjective formulation, two different evolutionary algorithms have been explored: the Nondominated Sorting Genetic Algorithm II (NSGA-II) and the Nondominated Sorting Differential Evolution (NSDE). Results considering acknowledged quality measures among original and transformed images over a well-known image benchmark show superior performance of the proposal than Random Sample Consensus algorithm on the problem being assessed, giving good results even with high outliers levels.

The remainder of the paper is organized as follows: Section 2 explains the problem of image homography considering multiple views. Section 3 introduces the fundamentals of the RANSAC method. Section 4 briefly explains the evolutionary approaches that are used in this paper in order to solve the multiobjective problem while Section 5 presents the proposed method. Section 6 exhibits the experimental set and its performance. Finally, Section 7 establishes some final conclusions.

2. Homography between Images

For the case where two images are taken of the same scene from different perspectives, a problem consists in finding a transformation that permits the matching among the pixels belonging to both images. This denominated the image matching problem. The search of a geometric transformation is achieved by utilizing corresponding points from image pairs [33, 34], which enable forming feature vectors, also called image descriptors. Even when considering that such descriptors are not completely reliable, so they can produce erroneous results for the image matching, in this paper they are used to find the geometric relations between images by using the homography, which is explained in the next paragraphs.

Consider a set of points [figure omitted; refer to PDF] such that [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are the positions with respect to a given image pair.

By means of a [figure omitted; refer to PDF] plane, a homography [figure omitted; refer to PDF] establishes a geometric relation between two images taken under different perspectives, as can be seen in Figure 1; this allows for a projection of the points from the plane to a pair of images, through [figure omitted; refer to PDF] or [figure omitted; refer to PDF] . Conducive to find the homography between an image pair, a set with four point matches is only required, to construct a linear system which must be solved [35]. Concerning evaluation of the quality of the candidate homography, it is necessary to calculate the distance among the point positions of the first image with respect to the second image; that distance is labeled as the Mismatch Error and is defined by [figure omitted; refer to PDF] as long as [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are the respective errors from each image.

Figure 1: Homography from a plane between two views.

[figure omitted; refer to PDF]

Consider the example shown in Figure 2, where five correspondences [figure omitted; refer to PDF] are depicted; for the case of the points [figure omitted; refer to PDF] , the error [figure omitted; refer to PDF] is considerable, and therefore the quality of the candidate homography will be ranked with a low value.

Figure 2: Example of evaluation process for a particular homography [figure omitted; refer to PDF] .

[figure omitted; refer to PDF]

3. Random Sampling Consensus (RANSAC) Algorithm

To find correspondences from images through a geometric transformation (homography) and therefore to increase the number of correct matches (inliers), the use of a robust approach, such as RANSAC, is necessary. Contrary to the inliers, outliers are conflicting points related to the candidate homography.

The idea behind the algorithm consists in discovering the best hypothesis [figure omitted; refer to PDF] from a set of hypotheses [figure omitted; refer to PDF] generated by the source data, usually corrupted with noise. The construction of candidate hypothesis [figure omitted; refer to PDF] is achieved by means of a sample [figure omitted; refer to PDF] , with a minimum size [figure omitted; refer to PDF] , to model estimation. As in this paper [figure omitted; refer to PDF] , then several [figure omitted; refer to PDF] could be taken from the complete source data [figure omitted; refer to PDF] , and, therefore, an exhaustive search would be computationally expensive.

In Pseudocode 1 the basic pseudocode of the RANSAC algorithms family is shown.

Pseudocode 1

(1) for [figure omitted; refer to PDF] through [figure omitted; refer to PDF]

(2) Randomly select a subsample from [figure omitted; refer to PDF] , and assemble a sample [figure omitted; refer to PDF]

(3) According to [figure omitted; refer to PDF] , compose the candidate hypothesis [figure omitted; refer to PDF]

(4) Calculate the degree of agreement [figure omitted; refer to PDF]

A subsequent step consists in finding the best candidate hypothesis [figure omitted; refer to PDF] from all the constructed and evaluated hypotheses, according to [figure omitted; refer to PDF] The degree of agreement is directly related to the number of inliers, and it is calculated by [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is a permissible error, [figure omitted; refer to PDF] is the number of elements contained in the source data [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] is the quadratic error produced by the [figure omitted; refer to PDF] th data considering the hypothesis [figure omitted; refer to PDF] ; in other words, it represents the error produced by the [figure omitted; refer to PDF] th correspondence.

In original RANSAC algorithm, the best hypothesis is the one with the maximum number of inliers. The point [figure omitted; refer to PDF] which produces an error [figure omitted; refer to PDF] lesser than a permissible error [figure omitted; refer to PDF] is considered as an inlier of candidate hypothesis [figure omitted; refer to PDF] ; otherwise, it is considered as an outlier.

The RANSAC technique has to search the entire source data [figure omitted; refer to PDF] at least once in the worst case; by considering such situation, the algorithm is similar to random walking. Several strategies could improve that kind of search, like evolutionary algorithms (EAs) [36]. These techniques are capable of exploitation and exploration of the search space judiciously, by considering that new candidate solutions will contain information regarding the best spots from search space, visited through each generation.

This work proposes working the estimation process as a multiobjective problem, by simultaneously optimizing both the number of matching points and the permissible error (Pe). In order to solve the multiobjective formulation, two different evolutionary algorithms have been explored: the Nondominated Sorting Genetic Algorithm II (NSGA-II) and the Nondominated Sorting Differential Evolution (NSDE). With the formulation, the proposed method adopts a different sampling strategy than RANSAC to generate putative solutions. Under the new mechanism, at every iteration new candidate solutions are generated based on the quality of previously found solutions, avoiding random walks in the searching process, as in the case of RANSAC.

4. Multiobjective Evolutionary Algorithms

A MO problem can be stated as minimizing or maximizing the function [37] [figure omitted; refer to PDF] where a solution [figure omitted; refer to PDF] is a vector of [figure omitted; refer to PDF] decision variables [figure omitted; refer to PDF] . The last set of constraints is called variable bounds, restricting each decision variable [figure omitted; refer to PDF] to take a value within a lower [figure omitted; refer to PDF] and upper [figure omitted; refer to PDF] bound and whose limits constitute a decision space [figure omitted; refer to PDF] . There are [figure omitted; refer to PDF] inequalities and [figure omitted; refer to PDF] equality constraints, both associated with the problem. In order to cover both minimization and maximization of objective functions, the operator [figure omitted; refer to PDF] is used between two solutions [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . Therefore, [figure omitted; refer to PDF] denotes that solution [figure omitted; refer to PDF] is better than solution [figure omitted; refer to PDF] whereas [figure omitted; refer to PDF] implies that solution [figure omitted; refer to PDF] is better than or equal to solution [figure omitted; refer to PDF] .

Different from single objective optimization, in the case of multiobjective optimization, it is usually difficult to find one optimal solution. Instead, algorithms for optimizing multiobjective problems attempt to find a group of points known as the Pareto optimal set [38]. These points verify that there is no other feasible solution which strictly improves one component of the objective function vector without worsening at least one of the remaining ones. A more formal definition of Pareto optimality or Pareto efficiency is the following.

Definition 1.

If, given a solution [figure omitted; refer to PDF] , there exists another solution [figure omitted; refer to PDF] such that [figure omitted; refer to PDF] [figure omitted; refer to PDF] and [figure omitted; refer to PDF] such that [figure omitted; refer to PDF] , then one will say that solution [figure omitted; refer to PDF] dominates solution [figure omitted; refer to PDF] (denoted by [figure omitted; refer to PDF] ), and, obviously, solution [figure omitted; refer to PDF] will never be sensibly selected as the solution to the problem. If [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , one will say that solution [figure omitted; refer to PDF] weakly dominates solution [figure omitted; refer to PDF] and will be denoted by [figure omitted; refer to PDF] [figure omitted; refer to PDF] [figure omitted; refer to PDF] .

Definition 2.

A solution [figure omitted; refer to PDF] is considered to be part of the Pareto optimal set [figure omitted; refer to PDF] if and only if [figure omitted; refer to PDF] such that [figure omitted; refer to PDF] .

Evolutionary algorithms (EAs) are considered the most adequate methods for solving complex MO problems and some have been proposed to face such problems, where the Nondominated Sorting Genetic Algorithm II (NSGA-II) and the Nondominated Sorting Differential Evolution (NSDE) are some of the most representative.

4.1. Nondominated Sorting Genetic Algorithm II (NSGA-II)

NSGA-II, introduced by Deb et al. [32], is one of the most applicable and employed algorithms based on GA to solve multiobjective optimization problems. NSGA-II starts randomly generating an initial ( [figure omitted; refer to PDF] ) parent population [figure omitted; refer to PDF] of size [figure omitted; refer to PDF] . During several consecutive generations ( [figure omitted; refer to PDF] ), the [figure omitted; refer to PDF] objective values of [figure omitted; refer to PDF] are evaluated. Then, the population is ranked based on the nondomination sorting procedure to create Pareto optimal fronts [figure omitted; refer to PDF] . Each individual of the population under evaluation obtains a rank equal to its nondomination level (1 is the best level, 2 is the next-best level, and so on), where the first front contains individuals with the best rank, the second front corresponds to the individuals with the second rank, and so on. In the next step, the crowding distance between members of each front is calculated by a linear distance criterion. As a binary tournament selection operator based on a crowded-comparison operator is used, it is necessary to calculate both the rank and the crowding distance of each member in the population. Using this selection operator, two members are selected among the population. Then, the member with the larger crowding distance is selected if they share an equal rank. Otherwise, the member with the lower rank is chosen. Next, a new population of offspring with a size of [figure omitted; refer to PDF] is created using the random selection, the simulated binary crossover [19], and the polynomial mutation [20] operators to create a population consisting of the current and the new population of the size of [figure omitted; refer to PDF] .

4.1.1. Simulated Binary Crossover

This operator simulates the behavior of the single-point crossover on binary strings. Given as parents [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , they generate the [figure omitted; refer to PDF] th component ( [figure omitted; refer to PDF] ) of the offspring individuals as follows: [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is a random number in [figure omitted; refer to PDF] . The parameter [figure omitted; refer to PDF] determines the separation between the offspring individuals in comparison to their parents.

4.1.2. Polynomial Mutation

This operator employs a polynomial distribution in the following way: [figure omitted; refer to PDF] where [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are the low and upper bounds, respectively, for the [figure omitted; refer to PDF] decision variable, whereas [figure omitted; refer to PDF] represents the distribution index.

4.2. Nondominated Sorting Differential Evolution (NSDE)

The NSDE [31] algorithm is an extension of the original differential evolution (DE) [39] method for solving multiobjective problems. NSDE works in a similar way to DE except in the selection operation which is modified in order to be coherent with the nondominated criterion.

The algorithm begins by initializing a population of [figure omitted; refer to PDF] -dimensional individuals and considers parameter values that are randomly distributed between the prespecified lower initial parameter bound [figure omitted; refer to PDF] and the upper initial parameter bound [figure omitted; refer to PDF] . In order to generate a trial individual (solution), the DE algorithm first mutates the current individual [figure omitted; refer to PDF] from the population by adding the scaled difference of two vectors from the current population: [figure omitted; refer to PDF] with [figure omitted; refer to PDF] being the mutant individual. Indexes [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are randomly selected with the condition that they are different and have no relation to the individual index [figure omitted; refer to PDF] whatsoever (i.e., [figure omitted; refer to PDF] ). The mutation scale factor [figure omitted; refer to PDF] is a positive real number, typically less than one. In order to increase the diversity of the parameter element, the crossover operation is applied between the mutant individual [figure omitted; refer to PDF] and the original individuals [figure omitted; refer to PDF] . The result is the trial individual [figure omitted; refer to PDF] which is computed by considering an element to element operation as follows: [figure omitted; refer to PDF] where [figure omitted; refer to PDF] . The subscripts [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are the parameter and individual indexes, respectively. The crossover parameter [figure omitted; refer to PDF] controls the fraction of parameters where the mutant individual is contributing to the final trial individual. In addition, the trial individual always inherits the mutant individual parameter according to the randomly chosen index [figure omitted; refer to PDF] , assuring that the trial individual differs by at least one parameter from [figure omitted; refer to PDF] . Finally, a nondominated selection is used to build the Pareto optimal front. Thus, if the trial individual [figure omitted; refer to PDF] dominates the target individual [figure omitted; refer to PDF] , the trial individual [figure omitted; refer to PDF] is copied into the population for the next generation; otherwise, the target individual [figure omitted; refer to PDF] is copied: [figure omitted; refer to PDF]

5. The Proposed Approach

5.1. Individual Representation

In the estimation process, each candidate homography [figure omitted; refer to PDF] is calculated by using four different point correspondences. The candidate homography [figure omitted; refer to PDF] is thus evaluated over the entire dataset [figure omitted; refer to PDF] , dividing all elements from the dataset to inliers and outliers, according to a permissible error (Pe).

In order to construct a candidate solution or individual [figure omitted; refer to PDF] , four indexes, [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] , are selected from the set [figure omitted; refer to PDF] of correspondences. Therefore, the homography [figure omitted; refer to PDF] across the two views is computed by solving the linear system produced from the set of four point matches [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] . Additionally, the permissible error [figure omitted; refer to PDF] that is associated with the individual [figure omitted; refer to PDF] is incorporated as a decision variable. Thus, in the proposed algorithm, an individual or candidate solution [figure omitted; refer to PDF] is coded as a vector of five decision variables [figure omitted; refer to PDF] that is defined by [figure omitted; refer to PDF]

In our approach, the candidate solution [figure omitted; refer to PDF] presents the same functionality, that is, hypothesis [figure omitted; refer to PDF] in the original RANSAC algorithm.

5.2. Multiobjective Problem Formulation

In the proposed approach, the estimation process is considered as a multiobjective problem where the number of matching points and the permissible error are simultaneously optimized. Under such circumstances, the multiobjective problem can be defined as follows: [figure omitted; refer to PDF] considering that [figure omitted; refer to PDF] and [figure omitted; refer to PDF] ; [figure omitted; refer to PDF] and where [figure omitted; refer to PDF] represents the maximal commensurable error produced by a candidate homography. Although [figure omitted; refer to PDF] could be any high value, a sufficiently small value significantly reduces the search of Pareto fronts. In this work, [figure omitted; refer to PDF] has been set to 25.

5.3. Computational Procedures

In order to solve the multiobjective formulation, two different evolutionary algorithms have been explored: the Nondominated Sorting Genetic Algorithm II (NSGA-II) and the Nondominated Sorting Differential Evolution (NSDE). In this section, the computational procedure of both methods is described when they face the multiobjective problem described in (12).

(a) Nondominated Sorting Genetic Algorithm II (NSGA-II)

(1) Generate randomly a population [figure omitted; refer to PDF] of [figure omitted; refer to PDF] five-dimensional individuals. The decision variables of each individual [figure omitted; refer to PDF] ( [figure omitted; refer to PDF] ) are produced, considering a random number between their search bounds.

(2) Produce an offspring population [figure omitted; refer to PDF] from [figure omitted; refer to PDF] by using simulated binary crossover and polynomial mutation.

(3) Create a new population [figure omitted; refer to PDF] as the combination of [figure omitted; refer to PDF] and [figure omitted; refer to PDF] ( [figure omitted; refer to PDF] ).

(4) Perform a nondominated sorting to [figure omitted; refer to PDF] and identify different fronts: [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and so forth.

(5) Set the new population [figure omitted; refer to PDF] and the counter [figure omitted; refer to PDF] .

(6) Perform [figure omitted; refer to PDF] and increment [figure omitted; refer to PDF] [figure omitted; refer to PDF] .

(7) Assuming that [figure omitted; refer to PDF] represents the number of elements contained in [figure omitted; refer to PDF] , repeat step [figure omitted; refer to PDF] , until [figure omitted; refer to PDF] .

(8) Assuming that [figure omitted; refer to PDF] , clear the initial distance ( [figure omitted; refer to PDF] ) of each element [figure omitted; refer to PDF] from [figure omitted; refer to PDF] .

(9) For each objective function [figure omitted; refer to PDF] , sort the set in worse order of [figure omitted; refer to PDF] . Therefore, [figure omitted; refer to PDF] contains the sorted elements of the objective function [figure omitted; refer to PDF] .

(10) For [figure omitted; refer to PDF] , assign a large distance to the boundary elements of [figure omitted; refer to PDF] [figure omitted; refer to PDF] . For all other elements [figure omitted; refer to PDF] , assign a distance calculated as follows: [figure omitted; refer to PDF]

: where [figure omitted; refer to PDF] represent the element [figure omitted; refer to PDF] from the sorted set [figure omitted; refer to PDF] . [figure omitted; refer to PDF] and [figure omitted; refer to PDF] symbolize the maximum and minimum value of [figure omitted; refer to PDF]

(11) Select the [figure omitted; refer to PDF] elements from [figure omitted; refer to PDF] whose distances are the longest and include them in [figure omitted; refer to PDF] .

(12) If the maximum number of iterations has been reached, the process is thus completed; otherwise, go back to step [figure omitted; refer to PDF] .

(13) The final population [figure omitted; refer to PDF] contains the Pareto optimal set.

(b) Nondominated Sorting Differential Evolution (NSDE)

(1) Set the DE parameters [figure omitted; refer to PDF] and [figure omitted; refer to PDF] .

(2) Generate randomly a population [figure omitted; refer to PDF] of [figure omitted; refer to PDF] five-dimensional individuals. The decision variables of each individual [figure omitted; refer to PDF] ( [figure omitted; refer to PDF] ) are produced, considering a random number between their search bounds.

(3) Generate a trial population [figure omitted; refer to PDF] with [figure omitted; refer to PDF] individuals ( [figure omitted; refer to PDF] ) of five dimensions

: ( [figure omitted; refer to PDF] ) under Procedure 1.

(4) Select the elements [figure omitted; refer to PDF] ( [figure omitted; refer to PDF] ) of the next population [figure omitted; refer to PDF] under Procedure 2.

(5) If the maximum number of iterations has been reached, the process is thus completed; otherwise, go back to step [figure omitted; refer to PDF] .

(6) The final population [figure omitted; refer to PDF] contains the Pareto optimal set.

Procedure 1

for ( [figure omitted; refer to PDF] ; [figure omitted; refer to PDF] ; [figure omitted; refer to PDF] ++)

do [figure omitted; refer to PDF] ; while ( [figure omitted; refer to PDF] );

do [figure omitted; refer to PDF] ; while (( [figure omitted; refer to PDF] ) or ( [figure omitted; refer to PDF] ));

[figure omitted; refer to PDF] ;

for ( [figure omitted; refer to PDF] ; [figure omitted; refer to PDF] ; [figure omitted; refer to PDF] ++) // generate a trial vector

if ( [figure omitted; refer to PDF] ) <= CR or [figure omitted; refer to PDF] = [figure omitted; refer to PDF] rand)

[figure omitted; refer to PDF] ;

else

[figure omitted; refer to PDF] ;

end if

end for

end for

Procedure 2

for ( [figure omitted; refer to PDF] ; [figure omitted; refer to PDF] ; [figure omitted; refer to PDF] ++)

if [figure omitted; refer to PDF]

[figure omitted; refer to PDF]

else

[figure omitted; refer to PDF]

end if

end for

6. Experimental Results

This part of the paper deals with several experiments performed over a collection of real images. The results exhibit the performance of NSGA-II and NSDE solving the estimation problem as a multiobjective optimization task in comparison to RANSAC. In the experiments, two performance indexes are considered: the mean squared error (MSE) and the Peak Signal to Noise Ratio (PSNR). Such indexes allow appropriately assessing the accuracy of the estimation.

The problem of homography estimation consists in finding a geometric transformation that maps points of a first view ( [figure omitted; refer to PDF] ) to a second view ( [figure omitted; refer to PDF] ), taken from different point of view. This projective transformation [figure omitted; refer to PDF] relates corresponding points of the plane projected into the first and second views by [figure omitted; refer to PDF] or [figure omitted; refer to PDF] . In order to calculate the MSE and the PSNR, two different images are defined: the estimated image (EI ) and the actual image (AI ). The EI is produced by mapping the pixels from the first view in terms of the estimated homography [figure omitted; refer to PDF] [figure omitted; refer to PDF] . On the other hand, the actual image (AI ) corresponds to the second view image.

The mean squared error (MSE) evaluates the squared differences among the pixels of EI and AI . Considering that [figure omitted; refer to PDF] represents the image dimensions, the MSE can be computed as follows: [figure omitted; refer to PDF]

The Peak Signal to Noise Ratio (PSNR) is commonly used to measure the quality of reconstruction of an image that undergoes some process. The signal in this case is the original data (AI ), and the noise is the error introduced by the transformation H (EI ). When comparing images, PSNR is an approximation to human perception of approximation quality. A higher PSNR value generally indicates that the estimation is of higher quality. PSNR is mainly defined via the mean squared error (MSE). Given [figure omitted; refer to PDF] image, the PSNR is defined as [figure omitted; refer to PDF] where MAX is the maximum possible pixel value contained in the image.

The images used in the experiments are collected from [40] which contains several two-view images of different objects, considering a dimension of 640 × 480 pixels. Likewise, the set of images used in the experimental test is presented in Figure 3.

Figure 3: Set of images used in the experimental set.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

(c) [figure omitted; refer to PDF]

(d) [figure omitted; refer to PDF]

(e) [figure omitted; refer to PDF]

(f) [figure omitted; refer to PDF]

(g) [figure omitted; refer to PDF]

(h) [figure omitted; refer to PDF]

(i) [figure omitted; refer to PDF]

(j) [figure omitted; refer to PDF]

(k) [figure omitted; refer to PDF]

(l) [figure omitted; refer to PDF]

For the test, both algorithms, NSGA-II and NSDE, have been configured considering 200 individuals under 200 iterations. In order to conduct a fair comparison between RANSAC and multiobjective approaches, RANSAC has been operated during 40,000 iterations. Such number of calculations (200 × 200) corresponds to the maximum number of evaluations invested by NSGA-II and NSDE during their execution.

Figure 4 shows the Pareto optimal set obtained by NSGA-II and NSDE during the estimation process, considering Figures 5(a) and 5(b) as the first and second views, respectively. In Figure 4, the best RANSAC estimations have been also included as a reference, only to validate the performance of the multiobjective approaches.

Figure 4: Pareto fronts found by NSGA-II and NSDE. The point obtained by RANSAC is placed only as a reference.

[figure omitted; refer to PDF]

Figure 5: Estimation results: (a) and (b) original images, (c) and (d) RANSAC, (e) and (f) NSGA-II, and (g) and (h) NSDE.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

(c) [figure omitted; refer to PDF]

(d) [figure omitted; refer to PDF]

(e) [figure omitted; refer to PDF]

(f) [figure omitted; refer to PDF]

(g) [figure omitted; refer to PDF]

(h) [figure omitted; refer to PDF]

In order to illustrate the obtained results, Figure 5 shows the estimations produced by all methods in terms of their resulting estimated images. The single estimation generated by RANSAC is exhibited in Figures 5(c) and 5(d). In case of the multiobjective approaches, three solutions from the Pareto optimal set have been selected: the boundary solution for [figure omitted; refer to PDF] , the boundary solution for [figure omitted; refer to PDF] , and the median solution. Such solutions are presented in Figures 5(e)-5(f) and 5(g)-5(h), for NSGA-II and NSDE, respectively.

Table 1 presents the performance results for NSGA-II and NSDE in terms of the mean squared error (MSE) and the Peak Signal to Noise Ratio (PSNR) over three pairs of images. The results present the averaged outcomes obtained throughout 30 different executions. In order to appreciate the differences, results only report the boundary solutions obtained for [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . The best results at each experiment are highlighted in Table 1.

Table 1: Evaluation of the estimation results for NSGA-II and NSDE.

Algorithm	Image pair	MSE	PSNR
NSGA-II	Figures 3(a) and 3(b)	97.44 (23.4474)	93.11 (19.9691)	8.59 (1.8793)	8.94 (1.6751)
NSDE	82.64 (0.7574)	82.14 (0.0787)	9.82 (0.0791)	9.87 (0.0083)
NSGA-II	Figures 3(c) and 3(d)	62.81 (20.6944)	56.09 (10.9807)	12.56 (2.4086)	13.31 (1.3887)
NSDE	51.81 (0.1233)	51.87 (0.2008)	13.87 (0.0207)	13.86 (0.0336)
NSGA-II	Figures 3(e) and 3(f)	118.23 (9.2986)	114.46 (0.4646)	6.73 (0.6693)	6.99 (0.0353)
NSDE	114.56 (0.6316)	114.29 (0.2172)	6.98 (0.0480)	7.00 (0.0165)

In order to evaluate the robustness of both algorithms, a set of outliers was added by selecting correspondence random points within the space limits. In the test, the fraction of outliers varies from 85% to 95%. Figure 6 shows the estimations produced by all methods in terms of their resulting estimated images, considering image pairs in Figures 3(k) and 3(l). Table 2 presents the performance results for RANSAC, NSGA-II, and NSDE in terms of the mean squared error (MSE) over the three pairs of images. The results exhibit the averaged outcomes obtained throughout 30 different executions.

Table 2: Quality measures, calculated from single extreme values, found by RANSAC, NSDE, and NSGA-II, varying the outlier number.

Algorithm	Image pair	MSE [figure omitted; refer to PDF]
95% of outliers	90% of outliers	85% of outliers
NSDE	Figures 3(g) and 3(h)	117.9057 (17.2158)	105.3281 (3.2716)	102.7769 (1.7186)
NSGA-II	146.7161 (3.3511)	140.1202 (13.2941)	122.5373 (22.6950)
RANSAC	135.0995 (17.8106)	103.6220 (2.8878)	100.8954 (1.0529)
NSDE	Figures 3(i) and 3(j)	70.2051 (14.8488)	52.0970 (0.3064)	51.7556 (0.1016)
NSGA-II	91.8883 (14.9284)	85.6721 (17.6376)	61.3195 (21.0951)
RANSAC	72.2009 (25.6447)	52.1122 (0.2773)	51.8429 (0.1234)
NSDE	Figures 3(k) and 3(l)	109.3420 (15.7526)	95.9762 (0.4746)	95.7580 (0.0121)
NSGA-II	135.5036 (5.6795)	110.0551 (21.9004)	96.9498 (2.5278)
RANSAC	120.9408 (21.7259)	95.8901 (0.1421)	95.8631 (0.1470)

Figure 6: Results obtained by RANSAC, NSGA-II, and NSDE.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

(c) [figure omitted; refer to PDF]

(d) [figure omitted; refer to PDF]

(e) [figure omitted; refer to PDF]

(f) [figure omitted; refer to PDF]

(g) [figure omitted; refer to PDF]

(h) [figure omitted; refer to PDF]

(i) [figure omitted; refer to PDF]

From Table 2, it can be easily seen that as the number of outliers increases, the performance of each algorithm also decreases. However, the NSDE algorithm obtains the best performance in almost every case despite outliers rising above 95%.

The approach has been experimentally tested considering a set of benchmark experiments. The efficiency of the method has been evaluated in terms of the mean squared error (MSE) and the Peak Signal to Noise Ratio (PSNR) measurements. Experimental results that consider real images provide evidence on the remarkable performance of the proposed approach in comparison to the classical RANSAC.

The Wilcoxon signed rank test [41] is a nonparametric test used both to compare quantitatively some experimental data and also to determine whether there exists a meaningful difference among them. By applying the test to the data contained in Table 2, it was found that the algorithms NSGA-II and NSDE are substantially different with a 5% significance, so it can be considered that NSDE gives better results than NSGA-II when both algorithms are applied to the homography problem. In the same order of ideas, the same test was used to compare NSGA-II and RANSAC algorithms, causing the first algorithm to be better than the second.

7. Conclusions

In this work the use of two multiobjective evolutionary algorithms in conjunction with point correspondences is proposed to estimate homographies between image pairs. Under this approach, the estimation process is considered as a multiobjective problem with the number of matching points [figure omitted; refer to PDF] and the permissible error [figure omitted; refer to PDF] being simultaneously optimized. Under such circumstances, the approach has the capacity to find the best balance between both objectives.

A close inspection of the standard deviations from Table 1 reveals that NSGA-II maintains a big dispersion in its solutions. This aspect is mainly emphasized in the MSE index. Such an inconsistency is a consequence of the NSGA-II incapacity to produce similar solutions during its executions. On the contrary, NSDE produces better solutions than NSGA-II in terms of accuracy (MSE) and consistency. On the other hand, as a higher PSNR value indicates that the estimation is of higher quality, results produced by the NSDE algorithm exhibit the best performance.

In order to solve the multiobjective formulation, two different evolutionary algorithms have been explored: the Nondominated Sorting Genetic Algorithm II (NSGA-II) and the Nondominated Sorting Differential Evolution (NSDE).

After several tests, it was found that NSDE gives better results in solving the image matching problem presented, according to a known statistical test over a set of experimental results.

Acknowledgment

This work was supported by the Consejo Nacional de Ciencia y Tecnologia, CONACYT, under various grants.

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

[1] R. Szeliski, H.-Y. Y. Shum, "Creating full view panoramic image mosaics and environment maps," in Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH '97), pp. 251-258, ACM, Los Angeles, Calif, USA, August 1997.

[2] Y. He, R. Chung, "Image mosaicking for polyhedral scene and in particular singly visible surfaces," Pattern Recognition , vol. 41, no. 3, pp. 1200-1213, 2008.

[3] M. Brown, D. G. Lowe, "Automatic panoramic image stitching using invariant features," International Journal of Computer Vision , vol. 74, no. 1, pp. 59-73, 2007.

[4] A. Akyol, M. Gökmen, "Super-resolution reconstruction of faces by enhanced global models of shape and texture," Pattern Recognition , vol. 45, no. 12, pp. 4103-4116, 2012.

[5] H. Huang, H. T. He, X. Fan, J. P. Zhang, "Super-resolution of human face image using canonical correlation analysis," Pattern Recognition , vol. 43, no. 7, pp. 2532-2543, 2010.

[6] K. Jia, S. G. Gong, "Hallucinating multiple occluded face images of different resolutions," Pattern Recognition Letters , vol. 27, no. 15, pp. 1768-1775, 2006.

[7] O. Deniz, G. Bueno, E. Bermejo, R. Sukthankar, "Fast and accurate global motion compensation," Pattern Recognition , vol. 44, no. 12, pp. 2887-2901, 2011.

[8] H. Zhang, J. P. Ostrowski, "Visual motion planning for mobile robots," IEEE Transactions on Robotics and Automation , vol. 18, no. 2, pp. 199-208, 2002.

[9] C. Sagües, J. J. Guerrero, "Visual correction for mobile robot homing," Robotics and Autonomous Systems , vol. 50, no. 1, pp. 41-49, 2005.

[10] G. Lopez-Nicolas, J. J. Guerrero, C. Sagües, "Visual control of vehicles using two-view geometry," Mechatronics , vol. 20, no. 2, pp. 315-325, 2010.

[11] E. Montijano, C. Sagues, "Distributed multi-camera visual mapping using topological maps of planar regions," Pattern Recognition , vol. 44, no. 7, pp. 1528-1539, 2011.

[12] J. Su, R. Chung, L. Jin, "Homography-based partitioning of curved surface for stereo correspondence establishment," Pattern Recognition Letters , vol. 28, no. 12, pp. 1459-1471, 2007.

[13] T. T. Santos, C. H. Morimoto, "Multiple camera people detection and tracking using support integration," Pattern Recognition Letters , vol. 32, no. 1, pp. 47-55, 2011.

[14] M. A. Fischler, R. C. Bolles, "Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography," Communications of the ACM , vol. 24, no. 6, pp. 381-395, 1981.

[15] X. Qian, C. Ye, "NCC-RANSAC: a fast plane extraction method for 3-D range data segmentation," IEEE Transactions on Cybernetics , vol. 44, no. 12, pp. 2771-2783, 2014.

[16] J. Matas, O. Chum, "Randomized RANSAC with T_d,d test," Image and Vision Computing , vol. 22, no. 10, pp. 837-842, 2004.

[17] C.-M. Cheng, S.-H. Lai, "A consensus sampling technique for fast and robust model fitting," Pattern Recognition , vol. 42, no. 7, pp. 1318-1329, 2009.

[18] E. Cuevas, M. Diaz, "A method for estimating view transformations from image correspondences based on the harmony search algorithm," Computational Intelligence and Neuroscience , vol. 2015, 2015.

[19] P. H. S. Torr, A. Zisserman, "MLESAC: a new robust estimator with application to estimating image geometry," Computer Vision and Image Understanding , vol. 78, no. 1, pp. 138-156, 2000.

[20] S. B. Heinrich, "Efficient and robust model fitting with unknown noise scale," Image and Vision Computing , vol. 31, no. 10, pp. 735-747, 2013.

[21] R. Subbarao, P. Meer, "Beyond RANSAC: user independent robust regression," in Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition Workshop (CVPRW '06), pp. 101, IEEE, June 2006.

[22] H. Wang, D. Suter, "Robust adaptive-scale parametric model estimation for computer vision," IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. 26, no. 11, pp. 1459-1474, 2004.

[23] K. Deb Multi-Objective Optimization Using Evolutionary Algorithms , John Wiley & Sons, New York, NY, USA, 2001.

[24] A. Rosales-Perez, J. A. Gonzalez, C. A. Coello Coello, H. J. Escalante, C. A. Reyes-Garcia, "Multi-objective model type selection," Neurocomputing , vol. 146, pp. 83-94, 2014.

[25] I. Giagkiozis, P. J. Fleming, "Methods for multi-objective optimization: an analysis," Information Sciences , vol. 293, pp. 338-350, 2014.

[26] M. Li, S. Yang, X. Liu, "Diversity comparison of Pareto front approximations in many-objective optimization," IEEE Transactions on Cybernetics , vol. 44, no. 12, pp. 2568-2584, 2014.

[27] Z.-H. Zhan, J. Li, J. Cao, J. Zhang, H. S.-H. Chung, Y.-H. Shi, "Multiple populations for multiple objectives: a coevolutionary technique for solving multiobjective optimization problems," IEEE Transactions on Cybernetics , vol. 43, no. 2, pp. 445-463, 2013.

[28] X.-B. Hu, M. Wang, E. Di Paolo, "Calculating complete and exact pareto front for multiobjective optimization: a new deterministic approach for discrete problems," IEEE Transactions on Cybernetics , vol. 43, no. 3, pp. 1088-1101, 2013.

[29] B. Xue, M. Zhang, W. N. Browne, "Particle swarm optimization for feature selection in classification: a multi-objective approach," IEEE Transactions on Cybernetics , vol. 43, no. 6, pp. 1656-1671, 2013.

[30] C. Liu, J. Liu, Z. Jiang, "A multiobjective evolutionary algorithm based on similarity for community detection from signed social networks," IEEE Transactions on Cybernetics , vol. 44, no. 12, pp. 2274-2287, 2014.

[31] H. J. Sun, C. H. Peng, J. F. Guo, H. S. Li, "Non-dominated sorting differential evolution algorithm for multi-objective optimal integrated generation bidding and scheduling," in Proceedings of the IEEE International Conference on Intelligent Computing and Intelligent Systems (ICIS '09), vol. 1, pp. 372-376, Shanghai, China, November 2009.

[32] K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II," IEEE Transactions on Evolutionary Computation , vol. 6, no. 2, pp. 182-197, 2002.

[33] H. Bay, A. Ess, T. Tuytelaars, L. V. Gool, "Surf: speeded up robust features," Computer Vision and Image Understanding , vol. 110, no. 3, pp. 346-359, 2008.

[34] C. Harris, M. Stephens, "A combined corner and edge detector," in Proceedings of the 4th Alvey Vision Conference, pp. 147-151, 1988.

[35] R. I. Hartley, A. Zisserman Multiple View Geometry Try in Computer Vision , Cambridge University Press, 2004., 2nd.

[36] P. Meer, G. Medioni, S. B. Kang, "Robust techniques in computer vision," Emerging Topics in Computer Vision , pp. 107-190, Prentice-Hall, Boston, Mass, USA, 2004.

[37] M. Ray, D. P. Mohapatra, "Multi-objective test prioritization via a genetic algorithm," Innovations in Systems and Software Engineering , vol. 10, no. 4, pp. 261-270, 2014.

[38] M. Ehrgott, J. Ide, A. Schöbel, "Minmax robustness for multi-objective optimization problems," European Journal of Operational Research , vol. 239, no. 1, pp. 17-31, 2014.

[39] R. Storn, K. Price, "Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces,", no. TR-95-012, 012, International Computer Science Institute, Berkeley, Calif, USA, 1995.

[40] D. Nister, H. Stewenius, "Scalable recognition with a vocabulary tree," in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR '06), vol. 2, pp. 2161-2168, June 2006.

[41] F. Wilcoxon, "Individual comparisons by ranking methods," Biometrics Bulletin , vol. 1, no. 6, pp. 80-83, 1945.