1) Papers
Evolving estimators of the pointwise Hölder exponent with Genetic Programming.
2) Authors
Leonardo Trujillo
email: leonardo.trujillo@tectijuana.edu.mx
Doctorado en Ciencias de la Ingeniería,
Departamento de Ingeniería Eléctrica y Electrónica,
Instituto Tecnológico de Tijuana,
Blvd. Industrial y Av. ITR Tijuana S/N,
Mesa Otay C.P. 22500, Tijuana BC, México
Pierrick Legrand
email: pierrick.legrand@u-bordeaux2.fr
Université Victor Segalen Bordeaux 2
IMB, Institut de Mathématiques de Bordeaux, UMR CNRS 5251, France
ALEA Team, INRIA Bordeaux Sud-Ouest, France
Gustavo Olague
email: olague@cicese.mx
EvoVision Project, Computer Science Department,
Centro de Investigación Científica y de Educación Superior de Ensenada,
Km. 107 Carretera Tijuana-Ensenada, 22860 Ensenada, BC, México
Jacques Lévy-Véhel
email: Jacques.levy-vehel@inria.fr
REGULARITY Team, INRIA Saclay, Ile de France, France
3) Corresponding Author
Leonardo Trujillo
4) Abstracts.
Evolving estimators of the pointwise Hölder exponent with Genetic Programming
ABSTRACT
The regularity of a signal can be numerically expressed using Hölder exponents, which
characterize the singular structures a signal contains. In particular, within the domains
of image processing and image understanding, regularity-based analysis can be used to
describe local image shape and appearance. However, estimating the Hölder exponent is
not a trivial task, and current methods tend to be computationally slow and complex. This
work presents an approach to automatically synthesize estimators of the pointwise Hölder
exponent for digital images. This task is formulated as an optimization problem and
Genetic Programming (GP) is used to search for operators that can approximate a traditional
estimator, the oscillations method. Experimental results show that GP can generate
estimators that achieve a low error and a high correlation with the ground truth estimation.
Furthermore, most of the GP estimators are faster than traditional approaches, in
some cases their runtime is orders of magnitude smaller. This result allowed us to implement
a real-time estimation of the Hölder exponent on a live video signal, the first such
implementation in current literature. Moreover, the evolved estimators are used to generate
local descriptors of salient image regions, a task for which a stable and robust matching
is achieved, comparable with state-of-the-art methods. In conclusion, the evolved estimators
produced by GP could help expand the application domain of Hölder regularity within
the fields of image analysis and signal processing.
5) Criteria
(B), (D), (F), (G)
6) Statement, Why the Results satisfies the criteria.
(B) & (F)
In our work, we have developed new estimators of the Hölder exponent, to measure the regularity of a 2D signal;
the evolved estimators present several advantages. First, the best estimators are quite fast and simple, compared
with estimators in the signal processing literature.
Morevoer, efficiency does not sacrifice quality, and in some cases the GP estimators exhibit better performance.
These claims are based on a review of previous methods; for instance see:
1) S. Jaffard and Y. Meyer. Wavelet methods for pointwise regularity and local oscillations of
functions. Mem. Amer. Math. Soc., 123(587), 1996.
2) A. Ayache and J. Levy Vehel. On the identification of the pointwise hölder exponent of the generalized multifractional brownian motion.
Stoch. Proc. Appl., 111 :119–156, 2004.
3) Levy Vehel, J.; Legrand, P. Signal and Image processing with FracLab.
Thinking in Patterns : Fractals and related Phenomena in Nature. April 4-7, 2004, Vancouver, Canada, pp. 321--322.
4) Legrand P. Débruitage et interpolation par analyse de la régularité Hölderienne.
Application ŕ la modélisation du frottement pneumatique-chaussée. 12/9/2004, Ecole centrale de Nantes
5) Julien Ros and Christophe Laurent. 2006. Description of Local Singularities for Image Registration.
In Proceedings of the 18th International Conference on Pattern Recognition - Volume 04
(ICPR '06), Vol. 4. IEEE Computer Society, Washington, DC, USA, 61-64.
(D) One of the publications produced by this research work (Trujillo et al. 2012), focuses on the use of Holder regularity to solve the problem of
local image description, one of the main tools in modern computer vision. This was only possible because of the efficient GP estimators.
In fact, recent results in this field have focused on developing machine learning (black-box) approaches towards local feature description,
very similar to the proposals developed here.
For instance see:
Matthew Brown, Gang Hua, and Simon Winder. 2011. Discriminative Learning of Local Image Descriptors. IEEE Trans. Pattern Anal. Mach. Intell. 33, 1 (January 2011), 43-57.
Gustavo Olague and Leonardo Trujillo. 2011. Evolutionary-computer-assisted design of image operators that detect interest points using genetic programming.
Image Vision Comput. 29, 7 (June 2011), 484-498.
Perez, C., and Olague, G. Genetic Programming as a Strategy for Learning Image Descriptor Operators.
Intelligent Data Analysis. IOS Press. Accepted for Publication
(G) Irregularities and singularities present the most informative parts of a signal, useful to derive image descriptors or shape models.
These characteristics of a signal can be numerically expressed using Hölder exponents, which characterize the singular structures a signal contains.
Nevertheless, the Hölder exponent has some drawbacks. First, the mathematical definition of this exponent,
(related to a generalization of the derivation), is not trivial. Secondly, the closed formed computation of the exponent is not possible on most signals;
particularly on real data. Thirdly, it is well known that estimating the Hölder exponent is not a trivial task,
and current methods tend to be computationally slow and algorithmically complex. Our work allowed us to implement
a simple and real-time estimation of the Hölder exponent on a live video signal, the first such implementation in current literature.
7) Full Citations.
Leonardo Trujillo, Pierrick Legrand, Gustavo Olague and Jacques Levy-Vehel.
Evolving estimators of the pointwise Hölder exponent with Genetic Programming.
Information Sciences, 209:61-79, 2012.
8) Prize Money.
Leonardo Trujillo: 40%
Pierrick Legrand: 40%
Jacques Lévy-Véhel: 10%
Gustavo Olague: 10%
9) Why this entery is the BEST.
This entry presents a very unique result to the Hummies, solving a difficult theoretical problem in the field of signal processing.
Regularity is an intrinsic property of a signal; it provides important descriptive information regarding signal dynamics and the nature of the source.
However, the algorithmic tools that were available to estimate it were impractical, and limited its wider use.
This work showed that GP can be used to find a novel solution to the problem, a solution with properties that
may facilitate the use of Holder regularity in more domains.
In fact, our work already shows one promising area of use, local image description for computer vision systems.
Today, with the technology to capture huge amounts quite easily, results like this are necessary,
to develop new techniques that can process, analyze and extract useful information for higher-level tasks.
Thus, our contribution could open new application domains for
regularity based-analysis, particularly for real-time applications in computer vision systems.