Recherche locale (optimisation)

En algorithmique, la recherche locale est une méthode générale utilisée pour résoudre des problèmes d'optimisation, c'est-à-dire des problèmes où l'on cherche la meilleure solution dans un ensemble de solutions candidates. La recherche locale consiste à passer d'une solution à une autre solution proche dans l'espace des solutions candidates (l'espace de recherche) jusqu'à ce qu'une solution considérée comme optimale soit trouvée, ou que le temps imparti soit dépassé. Exemple introductif On prend comme exemple le problème du voyageur de commerce, qui consiste, étant donné une liste de villes et les distances entre celles-ci, à trouver un circuit qui passe par toutes les villes, et qui est le plus court possible. Autrement dit, l'ensemble des solutions admissibles est l’ensemble des circuits qui passent par toutes les villes, et l'objectif est la minimisation de la longueur. On peut considérer que l'on se place sur un graphe non orienté dont les sommets sont les villes, et

Alternative search techniques for face detection using location estimation and binary features

Venkatesh Bala Subburaman

The sliding window approach is the most widely used technique to detect objects from an image. In the past few years, classifiers have been improved in many ways to increase the scanning speed. Apart from the classifier design (such as the cascade), the scanning speed also depends on a number of different factors (such as grid spacing, and scale at which the image is searched). Scanning grid spacing controls the number of subwindows being processed, thus controlling the speed of detection.When the scanning grid spacing is larger than the tolerance of the trained classifier it can suffer from low detections. In this thesis, we propose an alternative search technique, which can improve the detections when lesser number of subwindows are processed. First, we present a technique to reduce the number of miss detections while increasing the grid spacing when using the sliding window approach for object detection. This is achieved by using a small patch to predict the location of an object within a local search area. To achieve speed, it is necessary that the time taken for location prediction is comparable or better than the time it takes in average for the object classifier to reject a subwindow. We use binary features and a decision tree as it proved to be efficient for our application. In the process we also propose a variation of an existing binary feature (Ferns) with similar performance, and requires only half the number of pixel access when compared to Fern feature. We analyze the effect of patch size on location estimation and also evaluate our approach on several face databases. Experimental evaluation shows better detection rate and speed with our proposed approach for larger grid spacing (lesser number of subwindows) when compared to standard scanning technique. We also show that by using a simple interest point detector based on quantized gradient orientation, as the front-end to the proposed location estimation technique, we can achieve better performance even when fewer number of subwindows are processed. The interest points detected can be assumed as a non-regular grid compared to regular grid in the sliding window framework. A few image patches are sampled around an interest point for estimating the probable face location and further verified using a strong face classifier. Experiment results show that using an interest point detector can reduce the number of subwindows processed while maintaining a good detection rate.

ECOLE POLYTECHNIQUE FEDERALE DE LAUSANNE2012

Alternative Search Techniques for Face Detection Using Location Estimation and Binary Features

Venkatesh Bala Subburaman

The sliding window approach is the most widely used technique to detect objects from an image. In the past few years, classifiers have been improved in many ways to increase the scanning speed. Apart from the classifier design (such as the cascade), the scanning speed also depends on a number of different factors (such as grid spacing, and scale at which the image is searched). Scanning grid spacing controls the number of subwindows being processed, thus controlling the speed of detection. When the scanning grid spacing is larger than the tolerance of the trained classifier it can suffer from low detections. In this thesis, we propose an alternative search technique, which can improve the detections when lesser number of subwindows are processed. First, we present a technique to reduce the number of miss detections while increasing the grid spacing when using the sliding window approach for object detection. This is achieved by using a small patch to predict the location of an object within a local search area. To achieve speed, it is necessary that the time taken for location prediction is comparable or better than the time it takes in average for the object classifier to reject a subwindow. We use binary features and a decision tree as it proved to be efficient for our application. In the process we also propose a variation of an existing binary feature (Ferns) with similar performance, and requires only half the number of pixel access when compared to Fern feature. We analyze the effect of patch size on location estimation and also evaluate our approach on several face databases. Experimental evaluation shows better detection rate and speed with our proposed approach for larger grid spacing (lesser number of subwindows) when compared to standard scanning technique. We also show that by using a simple interest point detector based on quantized gradient orientation, as the front-end to the proposed location estimation technique, we can achieve better performance even when fewer number of subwindows are processed. The interest points detected can be assumed as a non-regular grid compared to regular grid in the sliding window framework. A few image patches are sampled around an interest point for estimating the probable face location and further verified using a strong face classifier. Experiment results show that using an interest point detector can reduce the number of subwindows processed while maintaining a good detection rate.

EPFL2012

Distributed constraint satisfaction for coordinating and integrating a large-scale, heterogeneous enterprise

Carlos Eisenberg

Market forces are continuously driving public and private organisations towards higher productivity, shorter process and production times, and fewer labour hours. To cope with these changes, organisations are adopting new organisational models of coordination and cooperation that increase their flexibility, consistency, efficiency, productivity and profit margins. In this thesis an organisational model of coordination and cooperation is examined using a real life example; the technical integration of a distributed large-scale project of an international physics collaboration. The distributed resource constraint project scheduling problem is modelled and solved with the methods of distributed constraint satisfaction. A distributed local search method, the distributed breakout algorithm (DisBO), is used as the basis for the coordination scheme. The efficiency of the local search method is improved by extending it with an incremental problem solving scheme with variable ordering. The scheme is implemented as central algorithm, incremental breakout algorithm (IncBO), and as distributed algorithm, distributed incremental breakout algorithm (DisIncBO). In both cases, strong performance gains are observed for solving underconstrained problems. Distributed local search algorithms are incomplete and lack a termination guarantee. When problems contain hard or unsolvable subproblems and are tightly or overconstrained, local search falls into infinite cycles without explanation. A scheme is developed that identifies hard or unsolvable subproblems and orders these to size. This scheme is based on the constraint weight information generated by the breakout algorithm during search. This information, combined with the graph structure, is used to derive a fail first variable order. Empirical results show that the derived variable order is 'perfect'. When it guides simple backtracking, exceptionally hard problems do not occur, and, when problems are unsolvable, the fail depth is always the shortest. Two hybrid algorithms, BOBT and BOBT-SUSP are developed. When the problem is unsolvable, BOBT returns the minimal subproblem within the search scope and BOBT-SUSP returns the smallest unsolvable subproblem using a powerful weight sum constraint. A distributed hybrid algorithm (DisBOBT) is developed that combines DisBO with DisBT. The distributed hybrid algorithm first attempts to solve the problem with DisBO. If no solution is available after a bounded number of breakouts, DisBO is terminated, and DisBT solves the problem. DisBT is guided by a distributed variable order that is derived from the constraint weight information and the graph structure. The variable order is incrementally established, every time the partial solution needs to be extended, the next variable within the order is identified. Empirical results show strong performance gains, especially when problems are overconstrained and contain small unsolvable subproblems.

EPFL2003

Distributed constraint satisfaction for coordinating and integrating a large-scale, heterogeneous enterprise

Carlos Eisenberg

EPFL2003

Alternative search techniques for face detection using location estimation and binary features

Venkatesh Bala Subburaman

ECOLE POLYTECHNIQUE FEDERALE DE LAUSANNE2012

Alternative Search Techniques for Face Detection Using Location Estimation and Binary Features

Venkatesh Bala Subburaman

The sliding window approach is the most widely used technique to detect objects from an image. In the past few years, classifiers have been improved in many ways to increase the scanning speed. Apart from the classifier design (such as the cascade), the scanning speed also depends on a number of different factors (such as grid spacing, and scale at which the image is searched). Scanning grid spacing controls the number of subwindows being processed, thus controlling the speed of detection. When the scanning grid spacing is larger than the tolerance of the trained classifier it can suffer from low detections. In this thesis, we propose an alternative search technique, which can improve the detections when lesser number of subwindows are processed. First, we present a technique to reduce the number of miss detections while increasing the grid spacing when using the sliding window approach for object detection. This is achieved by using a small patch to predict the location of an object within a local search area. To achieve speed, it is necessary that the time taken for location prediction is comparable or better than the time it takes in average for the object classifier to reject a subwindow. We use binary features and a decision tree as it proved to be efficient for our application. In the process we also propose a variation of an existing binary feature (Ferns) with similar performance, and requires only half the number of pixel access when compared to Fern feature. We analyze the effect of patch size on location estimation and also evaluate our approach on several face databases. Experimental evaluation shows better detection rate and speed with our proposed approach for larger grid spacing (lesser number of subwindows) when compared to standard scanning technique. We also show that by using a simple interest point detector based on quantized gradient orientation, as the front-end to the proposed location estimation technique, we can achieve better performance even when fewer number of subwindows are processed. The interest points detected can be assumed as a non-regular grid compared to regular grid in the sliding window framework. A few image patches are sampled around an interest point for estimating the probable face location and further verified using a strong face classifier. Experiment results show that using an interest point detector can reduce the number of subwindows processed while maintaining a good detection rate.

EPFL2012