Strings and Trees for Thumbnail Images Classification – SATTIC

In order to manage some of the huge data sets that are now available, and more particularly to classify, recognize or search through these sets, one needs a representation system which is rich enough to describe the data while allowing an efficient and mathematically well understood exploitation. This sort of representation is both well defined and nicely computed when data are numerical values, or more generally vectors of numerical values. - However, many objects are poorly modelled with such vectors of numerical values that cannot express notions such as sequentiality or relationships between attributes. In particular, this project aims at representing and exploiting thumbnail images such as those returned by search engines like Google. If much work has been done on images having high definition levels, none concerns the question of filtering these small images, the definition of which is too low to allow a segmentation into regions and/or the exploitation of wide support local measures. - An appealing alternative lays in modelling images by extracting and symbolically structuring salient points: salient points, corresponding to the image high contrast points, may be easily detected in thumbnail images; we propose to structure them by means of strings, trees, or more generally graphs, in order to integrate information on saliency degree or spatial relationships. - We propose in this project to study the capabilities of such salient point structuring to model and exploit thumbnail images. This goal implies the definition of a new paradigm for analysing and statistically characterizing symbolic structured data, at odds with classical approaches used for numerical data. - To achieve this goal, a first step is to choose a symbolic structuring and define a relevant distance measure, such that the distance between the structures that model images actually reflects image similarity. A main difficulty relies in the very special semantics of our structures. In particular, when chaining salient points by decreasing saliency, the obtained strings have the unusual property that symbols at the beginning of the string are much more important than symbols at the end. - A second sub-goal is to define a statistical characterization of a set of symbolic structures (strings, trees, or graphs) modelling images: to perform clustering or filtering, one needs statistical characterizations of sets of structures such as mean or median structures, but also measures that evaluate the dispersion of the structures within the set, such as variance, standard deviation, or probability density. - A third sub-goal is to propose algorithms for computing the statistical measures introduced previously. The challenge relies here in the fact that the sets to characterize may contain a huge number of structures, that may contain thousands of symbols, and that most of the problems to solve are NP-hard. - Finally, we shall validate our work on tasks dealing with thumbnail images, typically classification and filtering. The low definition of these images forbids us to use classical pattern recognition approaches; the huge number of thumbnail images available on the web imposes to design efficient algorithm with nice scale-up properties. - ...