Aug 31, 2010

Mathjax in action... First impressions

Post @ 12:10:07 | HTML
Well, thanks to Mark Reid (I recommend his blog btw), I got my hands on Mathjax. It was very easy to install and run. Moreover, it brings you an automatic translater TeX <-> MathML. That is nice! Here is a sample file

I can use it in my blog too from now on:

The Bregman divergences for dual Legendre convex conjugates

\begin{align} B_F(p:q) & = & F(p)-F(q)- \langle p-q, \nabla F(q) \rangle \\ B_{F}(p:q) & = & B_{F^*}(\nabla F(q) : \nabla F(p))\\ B_{F}(p:q) & = & F(p)+F^*(\nabla F(q)) - \langle p, \nabla F(q) \rangle \end{align}

When using both Mathjax and jsmath, I got problems with parenthesis (...). So I desintalled jsmath, and it runs fine now...


PS: Some readers asked me how to post comments: just need to write email and choose any password in the form. No pre-registration required, so feel free to post comments.

Frank.

Aug 26, 2010

Testing Math in my blog....

Post @ 11:13:56 | test

For a strictly convex function F, we define the Jensen divergence (also called Burbea-Rao divergence) as :

$\mathrm{Jensen}_F(p,q) = \frac{F(p)+F(q)}{2} - F\left(\frac{p+q}{2}\right) $

This class includes the celebrated Jensen-Shannon divergence.
More math to come hopefully. I shall also try to set up mathjax soon... -:)

Another test on Chernoff information.

Aug 25, 2010

What is a good measure of complexity?

Post @ 14:53:41 | information

Recently, there has been a lot of work (and published books too!) to categorize and tabulate distances. The same task has been done for a measuring complexity by trying to unravel the (hopefully) few principles that rule things.

To mention a few notions, let us say that we have

  • Fisher information
  • Shannon information
  • Chernoff information
  • Kolmogorov information (better known as Kolmogorov complexity)

All those notions are closely related (and that is nice, since they try to tackle the same problem under different facets): how to define information from data...


I have read:
Measures of Complexity: A Nonexhaustive List

So what is lacking in information theory nowadays? Any suggestion?
Does information really exist. Science based on transduction as advocated by Vapnik does not need intermediate general model. I welcome opinions!

Frank.

Aug 24, 2010

ICPR: Burbea-Rao centroids

Post @ 12:15:32 | Burbea-Rao divergences

The Burbea-Rao centroids allows one to compute the Bhattacharyya distance of exponential families in closed forms. Moreover, by skewing the Burbea-Rao divergence, we obtain Bregman divergences in limit cases (and Kullback-Leibler divergence on exponential families). Today, at ICPR, we will present a simple algorithm to compute those Burbea-Rao centroids using the concave-convex procedure (CCCP).

All details:

Frank.

Aug 23, 2010

Boosting Bayesian map classification

Post @ 11:13:03 | k-nn rule

Today, the Int Conf on Pattern Recognition (ICPR) opens in Istanbul. We shall present two papers: 1 on k-nn boosting and the second on Burbea-Rao centroids.

Here is the poster for the paper entitled Boosting Bayesian map classification

BoostingKNN-icpr10_poster.jpg

You can get its pdf too BoostingKNN-icpr10_poster.pdf

Paolo Piro will present those results.

Frank.

Aug 20, 2010

Converging to truth...

Post @ 17:06:55 | probability

Ok, is that obvious that there is a Heaven world of random variables, were us Human beings can observe samples. I let you decide (do you think also that in that World, things are iid., but here on Earth everything seems to be dependent and different, think of the butterfly effect... are two atoms exactly alike?).

Anyway, to come back to pragmatic discussion. Suppose that we are given many samples, then in 1933, it was proven that the empirical CDF (cumulative distribution function) was converging to the underlying true distribution at an exponential rate. This bears the name of Glivenko-Cantelli theorem. So the inverse probability problem might be potentially tackled. Of course, Fisher key idea was to consider class of CDFs by parameterizing them (say, Gaussian, etc.) instead of looking for the non-parametric case.

Here are then bibtex entries for those articles (I had to brush up my Italian to create those entries to my bibtex file... -:) )

@article{Glivenko-1933,
author={Valery Ivanovich Glivenko},
title={Sulla determinazione empirica delle leggi di probabilita},
journal={Giornale dell'Istituto Italiano degli Attuari},
number={4},
pages={92-99},
year=1933
}
@article{Cantelli-1933,
author={Francesco Paolo Cantelli},
title={Sulla determinazione empirica delle leggi di probabilita},
journal={Giornale dell'Istituto Italiano degli Attuari},
number={4},
pages={221-424},
year=1933
}

Aug 19, 2010

Merging information:Chernoff information

Post @ 18:50:27 | hypothesis testing

Inference from data to deduce solution has been increasingly popular in computer vision. Specially with the success of AdaBoost. More and more algorithms are data-driven (thanks to manually prepared groundtruth databases). Today, I would like to mention the use of the optimal log-likelihood ratio test. The error rate is know to decrease exponentially according to Chernoff information. So suppose you have to label on-edge or out-edge pixels (say, for a road tracking system), you can learn the response distributions, and design a simple classification based on a calibrated test.

This was done in a CVPR'99 (later PAMI 2003) paper. The method is rather generic and allows one to measure the amount of information gained by each operator/filter.

Statistical edge detection: learning and evaluating edge cues
loglikelihoodratio-edgestrength.png (PAMI 2003)
Frank.

Aug 18, 2010

Typesetting math on a web page...

Post @ 18:05:05 | technology

There are many ways to do it. Whether you produce images by rendering math, or use a player for MathML, there is not a single universal way to do that. A simple solution is to use jsmath.
I produced such a toy example here
Frank.

Where is your nearest neighbor (NN query)?

Post @ 11:45:30 | GPU

Well, nearest neighbor queries are fundamental primitives to many algorithms (eg., computational geometry and texture synthesis). Often, we have to deal with high-dim data-sets and even if theoretical brand new algorithms (eg., LSH) have been designed, we are still lacking performance in practice. So why not, try the brute force method, and optimize on GPU the simplest algorithm using the intrinsic parallelism provided by graphics core. Here are the experiments we obtained. It is going to be presented at icip 2010 (image processing).

The question is how fast can you perform NN queries in practice....

Frank.

Aug 17, 2010

Soft clustering, not so soft after all!

Post @ 9:58:25 | clustering

When you use or teach clustering, you certainly begin with k-means, expectation-maximization (besides hierarchical clustering). You can also explain k-means as a kind of expectation-maximization. K-means has hard membership: a point belongs to only one cluster, while expectation-maximization (EM for short) has a density membership: each point belongs to all clusters according to a weight. We say that EM is a soft clustering (with soft membership)

Well, that is the traditional story. But actually, expectation-maximization is a local optimization technique for learning a Gaussian mixture model. That means with have a probabilistic generative model: a statistical mixture of Gaussians.So the soft membership is in fact a probability of not knowing the true membership of the indicator. Statistical mixtures use latent variables, but points belong to a single component (say, here Gaussian).

To alleviate this shortcoming, the MMNB method was recently introduced. MMNB stands for mixed membership naive-Bayes. Here is the link to the paper.

Frank.

Aug 16, 2010

Shannon entropy as limit of parametric entropies

Post @ 11:00:01 | Shannon entropy

I wrote a note showing how to use l'Hopital rule to prove that both Renyi and Tsallis entropies coincide with Shannon entropy in the limit case.

NoteHopitalRule.pdf


Comments welcome!
Frank.

Jul 23, 2010

Simulating loops in Gnuplot

Post @ 17:02:14 | gnuplot

tsallisdense.png
Suppose you want to plot 2D functions y=T(x,a) for a parameter a falling within a range, say [-10,10] with 0.1 increments. Gnuplot has a primitive called reread and an if instruction that you can use to simulate a loop.
So first, write the body of the loop in a text file, say plotTsallis.txt:

# filename:  plotTsallis.txt
plot T(x,a)
a=a+0.1;
if (a < 10) reread

Then open the gnuplot program and type:

set terminal png
set out 'C:/tsallisdense.png'
# Tsallis bit entropy
T(x,a)=(1-x**a-(1-x)**a)/(a-1)
set xrange [0:1]
set yrange [0:5]
set size square
unset key
set multiplot
a=-10
# Simulate the loop
load "C:/plotTsallis.txt"
unset multiplot

and here you are with your collection of plots now...
Frank.

Tsallis bit entropy

Post @ 15:10:15 | entropy

Summer time is a good time to refresh one's skills using various software, including Ipe and Gnuplot. I have plotted Tsallis entropies for binomial distributions (bit entropies). As one can see, Tsallis entropies are concave (like Shannon for positive entropic index), and convex otherwise.

TsallisBitEntropy.png

I am looking for the best combination to use gnuplot and latex. The set terminal latex is not so flexible as we cannot manually locate tags. Ipe comes in handy but cannot parse eps files generated for latex. Any suggestion ?
Frank.

Jul 20, 2010

ISVD 2010: Voronoi diagrams

Post @ 10:12:25 | Voronoi

Olivier recently attended ISVD where he presented the paper
Jensen-Bregman Voronoi diagrams and centroidal tessellations
on my behalf (I had unfortunately teaching duties colliding with the event).
Here is a short trip report

ISVD 2010 -- International Symposium on Voronoi Diagrams in Science and Engineering 

The 7th ISVD International Symposium on Voronoi Diagrams in Science and
Engineering hold in Quebec City, Qc, Canada from the 28th to the
30th of June 2010.
This symposium is devoted to a data structure which is famous in
computational geometry: the Voronoi diagrams. It allows to present both
theoretical results on this field and related ones (power diagrams,
Delaunay triangulations, two-sites diagrams, etc) or applications in
science or engineering (art, data visualization, etc).
The first keynote was made by Prof. Nikolai N. Medvedev from Novosibirsk
State University, Russia: he made a very interesting talk about the
impact of Delaunay on Voronoi diagrams, completed by a biography of
Boris Delaunay killing some myths about his life. The second one was
made by Sergio de Biasi, courageously replacing the planned speaker,
describing polynomiography and showing a lot of great images. The third
invited speaker, Prof. Leonidas J. Guibas from Stanford University,
first described a method for recovering curvature from a sampled 3D
shape, with theoretical guaranties, and next a Voronoi diagram
application to routing in sensors network. The last speakers, Prof.
Menelaos Karavela from the University of Crete, presented the CGAL
library, from theory to practice.
Some words about a few talks I particularly enjoyed: Toshihiro Tanuma
presented the paper /Revisiting Hyperbolic Voronoi Diagrams from
Theoretical, Applied and Generalized Viewpoints/, showing a new proof
that hyperbolic diagrams are power diagrams with some applications to
graphs embedding. Sergio De Biasi spoke about the paper /Maximal Zone
Diagrams and Their Computation/, describing a variation on zone diagrams
and some interesting properties about it. Danyel Fisher, presenting
/Fast Dynamic Voronoi Tree maps/, described new visualization techniques
with applications ranging from disk space visualization to display of
bug reports.
The conference was very well organized: except for the very last
session, which was made using Skype and thus a bit difficult to follow,
everything everything went without any particular problem.

Olivier & Frank.

Jul 13, 2010

Professor Igor Vajda

Post @ 11:03:42 | People

It is a very sad news to hear that Professor Igor Vajda passed away. Professor Imre Csiszar will give a lecture on his scientific legacy at the forthcoming conference on information geometry.
Frank.

Jul 06, 2010

A misbelief (?) on the concavity of entropies

Post @ 18:30:24 | bregman, tsallis

Shannon entropy is well-known to be concave. The entropy and cross-entropy (inaccuracy) yield the notion of relative entropy. Bregman divergences can be interpreted as relative entropies for a convex generator. The negative (and hence concave) generator can thus be interpreted as an entropy measure. Bregman divergences include both extensive (eg., Shannon) and non-extensive (eg., quadratic) entropies.

However, entropies need NOT BE always concave.

For example, Tsallis entropies (Havrda-Charvat) generalizing Shannon entropy are CONVEX for q<0

TsallisEntropies.png

This proves also that Tsallis relative entropy is not a Bregman divergence for q<0.

Jul 05, 2010

Graph metric

Post @ 20:09:24 | metric

Structural pattern matching has gained a lot of attention the past decades by considering structures on features. Matching structural features thus relies on underlying graph structures.
A simple metric on graphs P and Q can be defined by

graphmetric.gif

where mcs denotes the maximum common subgraph.

This bounded distance satisfies the triangle inequality property (non-trivial proof, see ref below) but is NP-hard to compute.
Nevertheless it has been used successfully in applications.

@article{graphmetric-1998,
 author = {Bunke, Horst and Shearer, Kim},
 title = {A graph distance metric based on the maximal common subgraph},
 journal = {Pattern Recogn. Lett.},
 volume = {19},
 number = {3-4},
 year = {1998},
 issn = {0167-8655},
 pages = {255--259},
 doi = {http://dx.doi.org/10.1016/S0167-8655(97)00179-7},
 publisher = {Elsevier Science Inc.},
 address = {New York, NY, USA}
 }

Jul 02, 2010

Yet another quizz!

Post @ 2:19:07 | quizz

I have prepared the 4th quizz on information geometry. Need to polish a bit the questions. But here it is:

Take me to the quizz!

Jun 30, 2010

Cross-disciplinary approach of E. T. Jaynes

Post @ 20:33:48 | maximum entropy

Edwin Thompson Jaynes is nowadays mostly known for the maximum entropy principle exposed in the 1957 papers:

@article{jaynes-1957,
  author = {Edwin Thompson Jaynes},
  journal = {The Physical Review},
  number = 4,
  pages = {620--630},
  publisher = {American Physical Society},
  title = {Information Theory and Statistical Mechanics},
  volume = 106,
  year = 1957,
  numpages = {10},
  doi = {10.1103/PhysRev.106.620},
  month = may
}

There it is shown that distributions with expectation constraints maximizing Shannon entropy are precisely exponential families. There a nice biography here.

Jaynes work was profound as he brought a new viewpoint of statistical mechanics as inference based on incomplete information.

Note that now-famous papers (his 1957 Phys. rev. papers) was objected by a reviewer then.

Jaynes-report.jpg
Frank.

Jun 29, 2010

Video lecture of the Burbea-Rao centroids

Post @ 14:57:04 | Burbea-Rao

The video lecture (in french) of
The Burbea-Rao and Bhattacharyya centroids
is available for streaming here.

Jun 28, 2010

Mitio Nagumo

Post @ 23:42:43 | aggregator

Again, I have searched for the first name of one of the pioneering paper on quasi-arithmetic means (simplest kind of aggregators). It has been allegedly studied by Nagumo and Kolmogorov in the 1930's. I found then the reprint of the papers of mathematician MITIO Nagumo in a Springer 1993 book. I have updated accordingly my bibtex entry

@article{mean-nagumo-1930,
  author    = {Mitio Nagumo},
  title     = {{\"U}ber eine {K}lasse der {M}ittelwerte},
  journal   = {Japanese Journal of Mathematics},
  volume    = {7},
  year      = {1930},
  pages =           {71-79},
  note ={see Collected papers, Springer 1993}
}

MitioNagumo-CollectedWorks.jpg

Jun 23, 2010

Jensen-Bregman Voronoi diagrams.

Post @ 5:46:57 | Voronoi

On sunday is the 2010 Int. Symp. on Voronoi Diagrams (ISVD). We shall present: Jensen-Bregman Voronoi diagrams and centroidal tessellations

Here are the slides of the talk.
The Jensen-Bregman divergence is a distortion measure defined by the Jensen difference provided by a strictly convex function. Jensen-Bregman divergences extend the well-known Jensen-Shannon divergence by allowing to choose an arbitrary convex function generator instead of the standard Shannon entropy. This class of Jensen-Bregman divergences notably includes the squared Euclidean distance. Although Jensen-Bregman divergences are symmetric distances by construction, they are not metrics as they violate the triangle inequality. We study the geometric properties and combinatorial complexities of both the Voronoi diagrams and the centroidal Voronoi diagrams induced by such as class of information-theoretic divergences. We show that those Jensen- Bregman divergences appear naturally into two contexts: (1) when symmetrizing Bregman divergences, and (2) when computing the Bhattacharyya distances of statistical distributions. The Bhattacharyya distance measures the amount of overlap of distributions, and is popularly used to provide both lower and upper bounds in machine learning: the Bayes? misclassification error. Since the Bhattacharyya distance of popular distributions in statistics called the exponential families (including familiar Gaussian, Poisson, multinomial, Beta/Gamma families, etc.) can be computed equivalently as Jensen-Bregman divergences, the Jensen-Bregman Voronoi diagrams allow one also to study statistical Voronoi diagrams induced by an entropic function. Keywords-Jensen?s inequality, Jensen difference, Bregman divergences, Jensen-Shannon divergence, Bhattacharyya distance, Burbea-Rao divergence, Hellinger-Kakutani-Matusita divergences, f-divergence, -divergence, exponential families, information geometry.

Jun 18, 2010

Total Bregman Divergence and its Applications to Shape Retrieval

Post @ 21:21:59 | Bregman

The following work has been presented at CVPR 2010. It considers orthogonal projection onto a tangent plane instead of vertical projection when defining a distance using a convex generator.

Shape database search is ubiquitous in the world of biometric systems, CAD systems etc. Shape data in these domains is experiencing an explosive growth and usually requires search of whole shape databases to retrieve the best matches with accuracy and efficiency for a variety of tasks. In this paper, we present a novel divergence measure between any two given points in Rn or two distribution functions. This divergence measures the orthogonal distance between the tangent to the convex function (used in the definition of the divergence) at one of its input arguments and its second argument. This is in contrast to the ordinate distance taken in the usual definition of the Bregman class of divergences [4]. We use this orthogonal distance to redefine the Bregman class of divergences and develop a new theory for estimating the center of a set of vectors as well as probability distribution functions. The new class of divergences are dubbed the total Bregman divergence (TBD).We present the L1-norm based TBD center that is dubbed the t-center which is then used as a cluster center of a class of shapes The t-center is weighted mean and this weight is small for noise and outliers. We present a shape retrieval scheme using TBD and the t-center for representing the classes of shapes from the MPEG-7 database and compare the results with other state-of-the-art methods in literature..

Jun 15, 2010

Everything comes in threes!

Post @ 23:23:48 | Bregman divergences

All good things come in threes. So here is the third installement of the information-theoretic quizz! Suggestions welcome.
Frank.

Jun 13, 2010

Applet demonstrating Burbea-Rao centroids

Post @ 16:54:18 | Burbea-Rao

I have set up an applet that computes the skew Burbea-Rao centroids linking the left to right sided Bregman centroids.

BurbeaRao-centroids.png


Frank.

Jun 11, 2010

Simplification and hierarchical representations of mixtures of exponential families

Post @ 5:15:09 | GMMs

Simplification and hierarchical representations of mixtures of exponential families just got out at Signal Processing
Abstract

A mixture model in statistics is a powerful framework commonly used to estimate the probability measure function of a random variable. Most algorithms handling mixture models were originally specifically designed for processing mixtures of Gaussians. However, other distributions such as Poisson, multinomial, Gamma/Beta have gained interest in signal processing in the past decades. These common distributions are unified in the framework of exponential families in statistics. In this paper, we present three generic clustering algorithms working on arbitrary mixtures of exponential families: the Bregman soft clustering, the Bregman hard clustering, and the Bregman hierarchical clustering. These algorithms allow one to estimate a mixture model from observations, to simplify such a mixture model, and to automatically learn the ?optimal? number of components in a simplified mixture model according to a resolution parameter. In addition, we present jMEF, an open source JavaTM library allowing users to create, process and manage mixtures of exponential families. In particular, jMEF includes the three aforementioned Bregman clustering algorithms.

Keywords: Mixtures models; Kullback?Leibler divergence; Bregman divergence; Exponential family; Mixtures of exponential families; Clustering algorithms

Jun 09, 2010

An asymptotic property of centroids with respect to f-divergences

Post @ 4:39:49 | f-divergence

f-centroids can be defined as the unique minimizer of the average Csiszar/Ali-Silvey f-divergence. All f-centroids are homogeneous (scale free, homogeneous degree 1).

f-centroids include power means (also reachable as Bregman centroids), extreme means, Lehmer mean, Gini mean, etc

An interesting property is by shifting the origin and letting the origin tend to infinity, all f-means become arithmetic mean.

fmeanlimit.jpg
The proof requires f to be C3, three times continously differentiable.

Frank.

Jun 04, 2010

Joyce and danger of Internet

Post @ 17:48:15 | f-divergence

We all daily use Internet and are biased by its non-controlled source of information. I was looking for the full name of the Ali and Silvey f-divergence paper, also independently studied by Csiszar. In those days, it was not rare to only mention the last name and give only initials, so it is hard to know for sure what those capital letters mean in

Ali, S. M.; Silvey, S. D. (1966). "A general class of coefficients of divergence of one distribution from another". Journal of the Royal Statistical Society, Series B 28 (1): 131?140.

After using several search tools (google x, x in plain, books, scholar, etc.), and tracing back previous papers, eventually writing some emails to Aligarh Muslim University, I figured out the full names of the celebrated paper, and finally completed by bibtex entry as follows:

% Computational information geometry bibtex file
@Article{AliSilvey-1966,
  author =       {Syed Mumtaz Ali and Samuel David Silvey},
  title =        {A general class of coefficients of divergence of one distribution from another},
  journal =      {Journal of the Royal Statistical Society, Series B},
  year =         {1966},
  volume =   {28},
  pages =    {131--142}
}

S. M. Ali was a PhD student of S. D. Silvey.

On a different side of Internet, I searched for some Kullback-Leibler properties, and figured out a weird french article mentionning

Kilolitre de divergence et mise à jour bayésienne

In fact, it was the automated translation for

KL divergence and Bayesian updating

KL has been suggested by the automatic translator to be kiloliter... Then the translated article becomes really funny to read. Have a look http://www.worldlingo.com/ma/enwiki/fr/Kullback%E2%80%93Leibler_divergence (french) and http://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence (english)

Frank.

May 27, 2010

Mailing list on information geometry and seminar

Post @ 17:56:27 | conference

There is newly created mailing list on information geometry and related areas available at: http://www.informationgeometry.org/mailman/listinfo/infogeo.

Tomorrow, we will have a full-day course lecture at Paris, that will be also broadcasted real-time on Internet and later as VODs. The home page of the seminar is at: http://www.informationgeometry.org/Seminar/seminarBrillouin.html

This is the 2nd seminar in the Leon Brillouin series organized by the  
French research group on Information Geometry.
Live video transmission of the seminar: http://video.ircam.fr/
French Information Geometry Research Group
Transdisciplinary Leon Brillouin Seminar Series
Place: IRCAM, Salle Igor Stravinsky, Paris (http://www.ircam.fr/contact.html 
)
Date: 28 mai 2010, d?but ? 10h.
Programme:
10h - 12h:  Xavier Pennec (partie I), Current Issues in Statistical  
Analysis on Manifolds for Computational Anatomy
12h - 14h:  d?jeuner
14h - 16h:  Xavier Pennec (partie I), Current Issues in Statistical  
Analysis on Manifolds for Computational Anatomy
16h - 16h30: Pause caf?
16h30-17h30: Frank Nielsen, The Burbea-Rao and Bhattacharyya centroids

Frank.

May 26, 2010

French shape recognition and AI conference report (RFIA 2010)

Post @ 19:59:35 | conference report

Yet another report by Olivier who attended RFIA 2010

RFIA 2010 -- Reconnaissance de formes et intelligence artificielle

RFIA (which stands for Reconnaissance de formes et intelligence artificielle) is a French-speaking conference about pattern recognition and artificial intelligence. The 17th edition held in Caen from January 20 to January 22 2010.

There was four parts in the workshop: an invited speaker session, a short talk session, a poster session and a demo session.

The short talk session was divided into two tracks: pattern recognition and artificial intelligence. I mainly followed the Pattern Recognition track. Unfortunately I was only able to attend the first two days of the conference, so I will present only talks from these days. Sang Ly presented a method to estimate moves of a stereoscopic vision system. Hervé Jégou presented a new compact representation of bag-of-words for image retrieval. Thierry Germa presented some results to follow people with a mobile platform, using information from image and RFID tags. Pierre Lébraly explained an extrinsic calibrating method for multi-camera system, using a planar mirror.

The three invited talks I attended were given by Olivier Teytaud (INRIA Saclay, France) speaking about artificial intelligence methods for Go game, Schlomo Zilberstein (University of Massachusetts, USA) presenting challenges and directions for decentralized decision making and by Nicu Sebe (University of Amsterdam, Nederlands) detailing some perspectives for human centered computing.

Frank.

May 24, 2010

Reranking with Contextual dissimilarity measures from representational Bregman k-means

Post @ 18:15:25 | Bregman

Olivier attended the VISAPP conference where he presented results on

Reranking with Contextual dissimilarity measures from representational Bregman k-means

Here is the abstract followed by a short report of the conference.

We present a novel reranking framework for Content Based Image Retrieval (CBIR) systems based on con-textual dissimilarity measures. Our work revisit and extend the method of Perronnin et al. (Perronnin et al., 2009) which introduces a way to build contexts used in turn to design contextual dissimilarity measures for reranking. Instead of using truncated rank lists from a CBIR engine as contexts, we rather use a clustering algorithm to group similar images from the rank list. We introduce the representational Bregman divergences and further generalize the Bregman k-means clustering by considering an embedding representation. These representation functions allows one to interpret ?-divergences/projections as Bregman divergences/projections on ?-representations. Finally, we validate our approach by presenting some experimental results on ranking performances on the INRIA Holidays database.

VISAPP 2010 -- International Conference on Computer Vision Theory and Applications

VISAPP is part of VISIGRAPP - The International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications. The purpose of this joint conference is to bring together researchers and practitioners on the areas of computer vision, imaging, computer graphics and information visualization, interested in both theoretical advances and applications in these fields. Computer Vision, Imaging, Computer Graphics and Information Visualization are well known areas which are becoming more and more interrelated with important interdisciplinary work, often as a result of an iterative combined process of image analysis and synthesis with models created in one of the fields being used to improve models created in another.

The VISIGRAPP component conferences are specialized in the following topics: GRAPP is structured along four main tracks, covering different aspects related to Computer Graphics, from Modelling to Rendering, including Animation and Interactive Environments, IMAGAPP covers theory, applications and technologies related to image display, colour coding, medical imaging, remote sensing, business document processing, digital fabrication, printing and electronic devices, VISAPP has also four main tracks, namely: Image Formation and Processing, Image Analysis, Image Understanding and Motion, Tracking and Stereo Vision and IVAPP structured along several topics related to Information Visualization.

The 2010 edition of VISIGRAPP was hold in Angers (France) from May 17th to May 21th. There were 4 invited speakers: Pascal Fua, from the École Polytechnique Fédérale de Lausanne (Switzerland), spoke about different ways of modeling deformable surfaces from monocular video sequences; Ali Mohammad-Djafari, from CNRS and Supéléc (France) spoke about methods for solving inverse problems, mainly regularization and bayesian estimation approaches, with applications in imaging and computer vision. The talk by Gabriela Csurka, from Xerox Research (France), was about Fisher kernel representation, describing Bag-Of-Features representation, Fisher vector and some applications. The last keynote speaker, Brian Barsky from University of California Berkeley, described recent research for modeling the human vision process, mainly for simulating eye diseases and consequences of surgery cures.

There were a lot of parallel sessions (2 or 3 only for VISAPP) which led to difficult choices between interesting talks. I will just a say a few words about some talks from the session I attended: Nuria Ortigosa presented the paper "Disparity maps for free path detection" describing an algorithm to detect obstacles and free path using stereo images. Sang Min presented the paper "Object retrieval based on user-drawn sketches", describing a similarity measure between sketches based on tensorial fields. Duan-Yu Chen, presenting the paper "Real-time gender recognition for uncontrolled environment of real-life images" spoke about a way to combine different approaches in order to get a robust algorithm. Laura Papaelo presented TOPMESH, a powerful library to build models of non-manifolds objects. Codruta Orniana-Ancuti, presenting "Robust grayscale conversion for vision-substitution systems", described a method to convert color images to grayscale images suitable for an auditory-vision system. Roland Moerzinger presented the paper "Improving person detection in videos by automatic scene adaptation" which introduces a way to improve person detection quality in the case of a static camera and a single planar ground. Zhaolin Su, for the paper "Real-time enhancement of image and video saliency using semantic depth of field", presented a way to change the depth of field of an image using saliency information. The talk of Svenja Kahn, "Time-of-flight based scene reconstruction with a mesh processing tool for model based camera tracking", described a way to build 3D models using a time-of-flight camera without the need of a prior knowledge of the model, for application in augmented reality.

Even if the goal to allow meetings between people from different fields is very interesting, it was really difficult to attend sessions from other fields without missing interesting talks in one's own field.

Previous Logs