Processing: a programming language for generative art

Recently I got some interest about generative art. As computer scientist who has interest about art but no drawing skills, it sounds interesting to being able to generate art by coding. Especially geometric and abstract art looks quite mesmerizing:

  3262623734_5954148e84_o

To do so, I found that several artists are using « Processing » which is according to the website: « a flexible software sketchbook and a language for learning how to code within the context of the visual arts ». Some simple tutorials are available in the website, and after few minutes, I was already able to generate some simple shape.

To go further, I looked for some books and found a nice one written by Matt Pearson and published by Manning Publication named: Generative Art – A practical guide using Processing. And the nice thing is that the code used in the book is open source and anyone can download and use it.

.

Big Data : comment gérer les grands volumes de données pour le calcul de similarité

Les volumes de données numériques augmentant considérablement (des milliards d’images, de vidéo, de documents, de tweets, …), la problématique du Big data est de donner des moyens techniques pour traiter des bases de données de plus en plus grandes et de moins en moins structurées.

L’objectif est de mettre au point des algorithmes permettant d’accélérer la comparaison des données afin de créer des regroupements, de calculer la similarité entre les données ou encore de segmenter ou partitionner les données. Les applications sont nombreuses : systèmes de recommandation (achats, .musique, vidéo…), de prédiction (en analysant les tweets, il est possible de détecter qu’un événement est en train d’avoir lieu), etc.

Pour pouvoir effectuer se genre de tâche ou tout autres opération de data mining, le traitement des données se fait en 2 étapes principales : 1) représenter les données et 2) calcul de distances ou de similarités.

Représenter les données

Avant toutes choses, il faut extraire des caractéristiques. Si j’analyse des images, je vais extraire des informations sur la couleur, les formes, les textures, etc. Chaque image sera alors décrit par un vecteur de caractéristique à plusieurs dimensions. Plus ces caractéristiques sont pertinentes pour la tâche à effectuer mieux ce sera. Moins il y aura de dimension et plus il sera facile de traiter le problème. Si le nombre de dimension devient très grand, cela va rendre plus difficile le calcul de similarité et la fouille de données. En effet, le calcul de distance est sensible aux nombre de dimensions, c’est ce qu’on appelle la « curse of dimensionality ».  Plus le nombre de dimensions augmente et plus la distance entre les données augmentent également, ce qui à implique que chaque données tend à être à la même distance que toutes les autres. Il devient alors impossible de regrouper les données par ressemblance puisqu’elles sont toutes dissimilaires.

Similarité, distance, voisinage et topologie

Les calculs des similarité et de distances permettent de découvrir la topologie d’un espace de données, de comprendre la structure qui émerge entre une données et ses données voisines. Quand une nouvelle donnée apparait, on souhaite explorer ses données voisines afin de se faire une idée au sujet de cette nouvelle donnée. Pour cela on utilise un algorithme de recherche de Plus Proches Voisins (k-PPV).

La recherche « basique » de k-PPV est longue car exhaustive. Pour une donnée, on calcule sa distance par rapport à toutes les autres données. On peux alors connaitre quelles sont les « k » données les plus proches (par exemple les 5-PPV). Ces 5 PPV vont m’informer de la nature de la donnée que je suis en train d’étudier. Si je fais de la classification, je peux faire voter les 5-PPV pour estimer la classe de la donnée étudiée.

Il existe de nombreuses astuces pour accélérer ce temps de calcul basée sur une structuration/segmentation de l’espace de données : arbres KD, k-means récursifs, tables de hashage, LSH… DG Lowe a publié en 2009 un article très intéressant sur l’algorithme FLANN qui regroupe à la fois la méthode basée sur les arbres KD et les k-means récursifs. Ces algorithmes sont adaptables au Big Data, mais ne sont pas conçues originellement pour traiter des grand volumes de données.

Je vais m’intéresser ici à la technique « Permutation Based Indexing » qui est plus récente (j’en ai entendu parlé par le professeur Stéphan Marchang-Maillet en 2014) et plus à même d’être utiliser dans un contexte de Big Data. Le principe consiste à choisir un certain nombre de données parmi toutes les données comme « points de référence ». Ensuite, au lieu de chercher les k-PPV parmis toutes les données, on va simplement calculer la distance entre la donnée et les points de référence. Si le nombre de points de référence est grand, on peux se limiter au calcul des plus proches points de référence. On créé alors une liste ordonnée des plus proches points de référence. Pour comparer deux données, je comparerai ces deux listes.

Par analogie, on peux comparer le « Permutation Based Indexing » à la localisation d’un bateau en pleine mer. En donnant les balises les plus proches que le bateau voie, on peux estimer sa position. Le nombre de données nécessaires est beaucoup plus faible que pour les techniques classiques ce qui permettra d’être applicable à des grand volumes de données.

Traitement Automatique du Langage Naturel avec MALLET

mallet

MALLET est une bilbiothèque JAVA pour traitement statistique des langues naturelles, la classification de document, la classification non-supervisée, le « topic modeling » , le tagging de séquence (Part of Speech), l’extraction d’information et encore d’autres applications sur le traitement et la classification de texte.

Cette bibliothèque a été principalement développé par Andrew McCallum, un des scientifique très renommé dans le domaine de la classification de texte. La version 2.0 de la bibliothèque date de 2008.

 

Extraction d’information des pdf avec CERMINE

http://cermine.ceon.pl/cermine/about.html

http://cermine.ceon.pl/cermine/about.html

CERMINE (Content ExtRactor and MINEr)  est une bibliothèque Java (GitHub) et un web service (http://cermine.ceon.pl/index.html) permettant d’extraire des meta-données  et du contenu depuis des PDF d’articles scientifiques créés numériquement.

Le système analyse le contenu du PDF et tente d’extraire des informations telles que le titre de l’article, le journal dans lequel il a été publié, la bibliographie (volume, pages, etc.), les auteurs et leurs affiliations, les mots-clés, le résumé…

Pour l’instant à l’étape de prototype, le projet reste expérimental mais très intéressant. Le code source étant disponible sur Github et le web service permet de tester le programme directement avec ses propres documents !

J’ai découvert cette technique lors de la conférence internationale DAS (Document Analysis System)

Référence :

Dominika Tkaczyk, Pawel Szostek, Piotr Jan Dendek, Mateusz Fedoryszak and Lukasz Bolikowski. CERMINE – automatic extraction of metadata and references from scientific literature. In 11th IAPR International Workshop on Document Analysis Systems, 2014.

Using Flickr images for 3D reconstruction

At the Electronic Imaging symposium of 2013, Steve Seitz from Washington University and Google presented a very interesting keynote entitled « a trillion photos ».

The principle is to exploit the millions of images found in databases such as Flickr. The aim of the project Building Rome in a Day is to harvest images from Flickr by simply typing the keywords « Rome » or « Venice ». Many images are unusable because they can not be matched with other images  – such as pictures of a restaurant, of a family, etc. On the other hand, the most touristic places such as « San Marco » are taken in picture from many different angles. By using a standard processing stream such as SIFT + RANSAC + FLANN it is possible to match the images and then to do the 3D reconstruction.

In this video , the pyramids represent the estimated shooting positions. The reconstruction was made by ​​using 14,079 pictures. The reconstruction of Venice is made by ​​using 250,000 images, 496 computing cores. 27h are necessary for matching and 38h for reconstruction.