♪
I. SIFT▲
SIFT (Scale-invariant feature transform) est un algorithme de vision assistée par ordinateur permettant de détecter et décrire des zones d'intérêts dans une image. Cet algorithme a été publié par David Lowe en 1999, et le propriétaire du brevet est l'Université de la Colombie-Britannique (en anglais, University of British Columbia, UBC). Cet algorithme inclut la reconnaissance d'objets et de mouvements, de la modélisation 3D, et du suivi vidéo. Il est aussi utilisé dans la robotique pour la gestion des déplacements par visualisation. Cet algorithme consiste à rechercher des points caractéristiques (appelés « features ») sur une photo qui seront décrits chacun par des coordonnées (x et y), une orientation, une échelle, ainsi que 128 descripteurs. L'idée générale de SIFT est donc de trouver des points-clés qui sont invariants à plusieurs transformations : rotation, échelle, illumination et changements mineurs du point de vue.
À noter qu'il s'agit ici non seulement de détecter, mais aussi de caractériser par des valeurs pour pouvoir reconnaitre (mettre en correspondance) par la suite ces zones ou points d'intérêt dans d'autres images de la même scène. Cet algorithme a eu un succès très important au sein de la communauté vision. Ainsi, ceci pourrait, par exemple, servir pour un programme de reconnaissance de bâtiments. En effet, si deux mêmes bâtiments sont pris en photo, certains points-clés retrouvés sur les deux photos seront concordants et nous permettront d'affirmer que celles-ci représentent le même bâtiment. De plus, le gros avantage de l'algorithme SIFT est, comme dit précédemment, qu'il reste invariant à l'échelle, par un éventuel changement d'angle de vue (± 30°), ainsi qu'à un changement de luminosité pouvant différer entre deux photos d'un même bâtiment.
II. JavaSIFT▲
Après la sortie de l'article de David Lowe, l'algorithme SIFT a été retranscrit dans de nombreux langages de programmation. JavaSIFT, comme son nom l'indique, a été écrit en Java et sous licence GNU GPL par Stephan Saalfeld (http://fly.mpi-cbg.de/~saalfeld/javasift.html).
Cependant, JavaSIFT a été développé pour être utilisé en tant que plugin pour le programme ImageJ, logiciel de traitement et d'analyse d'images (calcul d'histogramme, transformation de Fourier…) et permettant l'ajout de nouvelles fonctions grâce à un système de plugins (plus d'information à propos d'ImageJ à cette adresse : http://rsbweb.nih.gov/ij/). Le plugin JavaSIFT permettait donc d'appliquer l'algorithme sur une image importée dans l'interface d'ImageJ, ce qui le rendait ainsi dépendant de ce logiciel, car en effet, le code source de JavaSIFT nécessitait les librairies, et fonctions proposées par ImageJ pour la gestion des ressources, ce qui rendait impossible l'intégration de cette librairie directement dans un projet quelconque sans l'utilisation auxiliaire d'ImageJ.
Les modifications que j'ai alors apportées au code ont permis de le rendre totalement indépendant de la bibliothèque d'ImageJ, afin d'être utilisable sous forme de librairie externe (jar) depuis n'importe quel projet Java.
III. Mise en place du projet▲
La première étape consiste, bien évidemment, à créer un nouveau projet sous Eclipse pour la plate-forme Android et qu'on nommera SIFT Camera. La version du SDK importe peu ici, sachant que même la version minimum est suffisante. Cependant, il est nécessaire de générer avec, une Activity qu'on appellera CameraActivity.
Afin de pouvoir utiliser SIFT, le projet requiert la librairie téléchargeable ci-dessous. Ainsi faut-il l'attacher au projet afin de pouvoir accéder aux différentes méthodes qu'elle propose.
javasift.jar (Miroir)
Voici donc à quoi devrait ressembler l'architecture du projet :
IV. Création de l'interface▲
L'interface du projet restera extrêmement simpliste et se résumera à un layout composé d'une ImageView, prenant toute la surface de l'écran, et servant à afficher la photo prise.
Voici le code du fichier main.xml présent dans le dossier res/layout:
<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
android:orientation="vertical" android:layout_width="fill_parent"
android:layout_height="fill_parent" android:gravity="center">
<ImageView android:layout_width="fill_parent"
android:layout_height="fill_parent" android:id="@+id/view" android:keepScreenOn="true"/>
</LinearLayout>L'ImageView aura pour identifiant view.
Nous allons aussi mettre en place un menu composé d'un élément qui permettra à l'utilisateur de lancer la caméra pour prendre une photo.
Créez donc un fichier menu.xml que vous placerez dans res/menu; et placez-y ce code :
<?xml version="1.0" encoding="utf-8"?>
<menu
xmlns:android="http://schemas.android.com/apk/res/android">
<item android:title="Camera" android:icon="@drawable/ic_menu_camera" android:id="@+id/camera"></item>
</menu>Pour finir avec cette section, on va faire aussi en sorte de fixer l'application en mode portrait afin d'éviter tout relancement intempestif de l'Activity durant un changement d'orientation du téléphone, ce qui aurait pour conséquence d'annuler toute action en cours (la recherche des points-clés dans notre cas).
Pour cela, il suffit d'ajouter dans le fichier AndroidManifest.xml dans la balise correspondant à notre Activity :
android:screenOrientation="portrait"Donnant ainsi :
<activity android:name=".CameraActivity" android:screenOrientation="portrait"
android:label="@string/app_name">
<intent-filter>
<action android:name="android.intent.action.MAIN" />
<category android:name="android.intent.category.LAUNCHER" />
</intent-filter>
</activity>V. Lancer la caméra et récupérer la photo▲
Dans ce chapitre, nous allons mettre en place la base du programme qui permettra à l'utilisateur, dans un premier temps, de pouvoir afficher le menu, prendre une photo, et afficher la photo dans l'ImageView. Pour cela, il faudra surcharger trois méthodes dans l'Activity principal :
- public boolean onCreateOptionsMenu(Menu menu) : affiche le menu quand l'utilisateur appuiera sur le bouton menu ;
- public boolean onOptionsItemSelected(MenuItem item) : lance la caméra quand l'utilisateur aura sélectionné l'élément du menu ;
- protected void onActivityResult(int requestCode, int resultCode, Intent data) : récupère la photo prise renvoyée en retour de la caméra.
public class CameraActivity extends Activity {
private static final int PICTURE_RESULT = 9;
private Bitmap mPicture;
private ImageView mView;
public void onCreate(Bundle icicle) {
super.onCreate(icicle);
setContentView(R.layout.main);
mView = (ImageView) findViewById(R.id.view);
}
@Override
public boolean onCreateOptionsMenu(Menu menu) {
MenuInflater inflater = getMenuInflater();
inflater.inflate(R.menu.menu, menu);
return true;
}
@Override
public boolean onOptionsItemSelected(MenuItem item) {
switch (item.getItemId()) {
case R.id.camera:
Intent camera = new Intent(MediaStore.ACTION_IMAGE_CAPTURE);
CameraActivity.this.startActivityForResult(camera, PICTURE_RESULT);
return true;
default:
return super.onOptionsItemSelected(item);
}
}
public void onDestroy() {
super.onDestroy();
if (mPicture != null) {
mPicture.recycle();
}
}
@Override
protected void onActivityResult(int requestCode, int resultCode, Intent data) {
super.onActivityResult(requestCode, resultCode, data);
// if results comes from the camera activity
if (requestCode == PICTURE_RESULT) {
// if a picture was taken
if (resultCode == Activity.RESULT_OK) {
// Free the data of the last picture
if(mPicture != null)
mPicture.recycle();
// Get the picture taken by the user
mPicture = (Bitmap) data.getExtras().get("data");
// Avoid IllegalStateException with Immutable bitmap
Bitmap pic = mPicture.copy(mPicture.getConfig(), true);
mPicture.recycle();
mPicture = pic;
// Show the picture
mView.setImageBitmap(mPicture);
// if user canceled from the camera activity
} else if (resultCode == Activity.RESULT_CANCELED) {
}
}
}
}Ainsi, à cette étape, notre application permet à l'utilisateur de prendre une photo et de l'afficher dans l'interface.
Comme dans la suite nous allons dessiner sur l'image, celui-ci devra être dans l'état mutable. Or l'image renvoyée par la caméra se trouve être dans un état immutable, ce qui provoquera une exception lorsqu'on tentera de dessiner par-dessus. D'où la copie de l'image dans une autre variable afin de la rendre mutable.
VI. Appliquer l'algorithme SIFT▲
En jetant un coup d'œil dans la documentation de la librairie SIFT, on constate que la méthode qui nous intéresse est celle-ci :
static java.util.Vector<Feature> SIFT.getFeatures(int w, int h, int[] pixels);Ainsi, la méthode prend en paramètres la largeur et la hauteur de l'image, ainsi qu'un tableau d'entiers représentant la couleur pour chaque pixel. Or nous possédons une instance de la classe Bitmap pour représenter l'image, nous devons ainsi procéder à l'écriture d'une fonction permettant la conversion d'un type Bitmap vers un tableau de pixels :
private int[] toPixelsTab(Bitmap picture) {
int width = picture.getWidth();
int height = picture.getHeight();
int[] pixels = new int[width * height];
// copy pixels of picture into the tab
picture.getPixels(pixels, 0, picture.getWidth(), 0, 0, width, height);
// On Android, Color are coded in 4 bytes (argb),
// whereas SIFT needs color coded in 3 bytes (rgb)
for (int i = 0; i < (width * height); i++)
pixels[i] &= 0x00ffffff;
return pixels;
}Maintenant, les choses vont se compliquer un peu plus. En effet, l'algorithme SIFT étant assez lent, il est indispensable d'afficher durant le traitement un dialogue demandant à l'utilisateur de patienter, et ceci pour diverses raisons :
- parce que c'est une règle dans la création d'IHM, c'est-à-dire d'afficher à l'utilisateur qu'un traitement est en cours et ainsi le rassurer dans le fait que l'application est bien en train d'agir et de faire quelque chose en fond ;
- sans ça, cela provoquerait un blocage de l'interface durant le traitement, qui pourrait avoir comme conséquence l'affichage d'une alerte provenant du système informant que le programme ne répond plus.
Pour répondre à ce besoin, on utilisera la classe ProgressDialog afin d'alerter qu'un traitement est en cours. Elle sera affichée lors de la réception de la photo, puis nous instancierons un nouveau thread afin de nous occuper du traitement de l'image en tâche de fond. Pour finir, afin de gérer la communication entre le thread UI, et le thread de traitement, on utilisera la classe Handler, cela afin que le thread UI puisse être alerté du résultat du traitement (erreur ou succès) et d'arrêter l'affichage du ProgressDialog.
Cet article n'ayant pas pour but d'expliquer le fonctionnement et l'utilité de la classe Handler, référez-vous à la documentation AndroidHandler | Android Developers pour plus d'information.
Nous allons donc créer plusieurs constantes qui serviront à l'envoi de messages au Handler.
À la fin du thread de traitement, trois choses peuvent avoir pu se passer :
- l'algorithme s'est bien déroulé ;
- il y a eu un dépassement de mémoire ;
- il y a eu une erreur quelconque.
Pour chacun de ces évènements, on attribuera une constante :
private static final int OK = 0;
private static final int MEMORY_ERROR = 1;
private static final int ERROR = 2On n'oublie pas de définir notre ProgressDialog en attribut :
private ProgressDialog mProgressDialog;Et enfin la définition de notre Handler qui exécutera une certaine action selon le code reçu :
private final Handler mHandler = new Handler() {
@Override
public void handleMessage(Message msg) {
AlertDialog.Builder builder;
switch (msg.what) {
case OK:
// set the picture
mView.setImageBitmap(mPicture);
break;
case MEMORY_ERROR:
builder = new AlertDialog.Builder(CameraActivity.this);
builder.setMessage("Out of memory.\nPicture too big.");
builder.setPositiveButton("Ok", null);
builder.show();
break;
case ERROR:
builder = new AlertDialog.Builder(CameraActivity.this);
builder.setMessage("Error during the process.");
builder.setPositiveButton("Ok", null);
builder.show();
break;
}
mProgressDialog.dismiss();
}
};En cas de succès, on rafraîchit l'image dans notre ImageView, car on verra par la suite qu'on dessinera dessus les différents points-clés que l'algorithme en aura extraits. En cas d'erreur, on prévient l'utilisateur. Puis dans tous les cas, on élimine le ProgressDialog.
Maintenant, nous allons attaquer la partie la plus intéressante : nous allons créer la méthode qui va se charger d'appliquer l'algorithme SIFT sur notre image. Elle va tout d'abord instancier notre ProgressDialog, puis créer le thread qui s'occupera d'appeler la méthode nécessaire, et d'avertir via un message le Handler en lui indiquant le résultat.
private void processSIFT() {
// show the dialog
mProgressDialog = ProgressDialog.show(this, "Please wait",
"Processing of SIFT Algorithm...");
new Thread(new Runnable() {
@Override
public void run() {
Message msg = null;
try {
// convert bitmap to pixels table
int pixels[] = toPixelsTab(mPicture);
// get the features detected into a vector
Vector<Feature> features = SIFT.getFeatures(
mPicture.getWidth(), mPicture.getHeight(), pixels);
msg = mHandler.obtainMessage(OK);
} catch (Exception e) {
e.printStackTrace();
msg = mHandler.obtainMessage(ERROR);
} catch (OutOfMemoryError e) {
msg = mHandler.obtainMessage(MEMORY_ERROR);
} finally {
// send the message
mHandler.sendMessage(msg);
}
}
}).start();
}Maintenant, on peut ajouter l'appel à cette méthode dans la méthode onActivityResult :
if (resultCode == Activity.RESULT_OK) {
// Free the data of the last picture
if(mPicture != null)
mPicture.recycle();
// Get the picture taken by the user
mPicture = (Bitmap) data.getExtras().get("data");
// Avoid IllegalStateException with Immutable bitmap
Bitmap pic = mPicture.copy(mPicture.getConfig(), true);
mPicture.recycle();
mPicture = pic;
// Show the picture
mView.setImageBitmap(mPicture);
// process SIFT algorithm on the picture
processSIFT();
// if user canceled from the camera activity
} else if (resultCode == Activity.RESULT_CANCELED) {
// ...
}Jusqu'ici, on a donc un programme qui permet à l'utilisateur de prendre une photo puis d'appliquer la recherche de points-clés dessus grâce à l'algorithme SIFT.
Cependant, on n'en voit pas le résultat. On va donc, pour finir, créer une méthode dessinant sur la photo un point-clé :
public void drawFeature(Canvas c, float x, float y, double scale,
double orientation) {
Paint paint = new Paint(Paint.ANTI_ALIAS_FLAG);
// line too small...
scale *= 6.;
double sin = Math.sin(orientation);
double cos = Math.cos(orientation);
paint.setStrokeWidth(2f);
paint.setColor(Color.GREEN);
c.drawLine((float) x, (float) y, (float) (x - (sin - cos) * scale),
(float) (y + (sin + cos) * scale), paint);
paint.setStrokeWidth(4f);
paint.setColor(Color.YELLOW);
c.drawPoint(x, y, paint);
}Et d'appeler cette méthode pour chaque point-clé, après leur récupération dans le vecteur :
// convert bitmap to pixels table
int pixels[] = toPixelsTab(mPicture);
// get the features detected into a vector
Vector<Feature> features = SIFT.getFeatures(
mPicture.getWidth(), mPicture.getHeight(), pixels);
// draw features on bitmap
Canvas c = new Canvas(mPicture);
for (Feature f : features) {
drawFeature(c, f.location[0], f.location[1], f.scale, f.orientation);L'application est maintenant terminée. Ci-dessous vous trouverez des captures d'écran du programme en fonctionnement :
Code complet de l'Activity :
package com.jidul.android.sift_camera;
import java.util.Vector;
import mpi.cbg.fly.Feature;
import mpi.cbg.fly.SIFT;
import android.app.Activity;
import android.app.AlertDialog;
import android.app.ProgressDialog;
import android.content.Intent;
import android.graphics.Bitmap;
import android.graphics.Canvas;
import android.graphics.Color;
import android.graphics.Paint;
import android.os.Bundle;
import android.os.Handler;
import android.os.Message;
import android.provider.MediaStore;
import android.view.Menu;
import android.view.MenuInflater;
import android.view.MenuItem;
import android.widget.ImageView;
public class CameraActivity extends Activity {
private static final int PICTURE_RESULT = 9;
private static final int OK = 0;
private static final int MEMORY_ERROR = 1;
private static final int ERROR = 2;
private Bitmap mPicture;
private ImageView mView;
private ProgressDialog mProgressDialog;
public void onCreate(Bundle icicle) {
super.onCreate(icicle);
setContentView(R.layout.main);
mView = (ImageView) findViewById(R.id.view);
}
@Override
public boolean onCreateOptionsMenu(Menu menu) {
MenuInflater inflater = getMenuInflater();
inflater.inflate(R.menu.menu, menu);
return true;
}
@Override
public boolean onOptionsItemSelected(MenuItem item) {
switch (item.getItemId()) {
case R.id.camera:
Intent camera = new Intent(MediaStore.ACTION_IMAGE_CAPTURE);
CameraActivity.this.startActivityForResult(camera, PICTURE_RESULT);
return true;
default:
return super.onOptionsItemSelected(item);
}
}
public void onDestroy() {
super.onDestroy();
if (mPicture != null) {
mPicture.recycle();
}
}
@Override
protected void onActivityResult(int requestCode, int resultCode, Intent data) {
super.onActivityResult(requestCode, resultCode, data);
// if results comes from the camera activity
if (requestCode == PICTURE_RESULT) {
// if a picture was taken
if (resultCode == Activity.RESULT_OK) {
// Free the data of the last picture
if(mPicture != null)
mPicture.recycle();
// Get the picture taken by the user
mPicture = (Bitmap) data.getExtras().get("data");
// Avoid IllegalStateException with Immutable bitmap
Bitmap pic = mPicture.copy(mPicture.getConfig(), true);
mPicture.recycle();
mPicture = pic;
// Show the picture
mView.setImageBitmap(mPicture);
// process SIFT algorithm on the picture
processSIFT();
// if user canceled from the camera activity
} else if (resultCode == Activity.RESULT_CANCELED) {
}
}
}
private void processSIFT() {
// show the dialog
mProgressDialog = ProgressDialog.show(this, "Please wait",
"Processing of SIFT Algorithm...");
new Thread(new Runnable() {
@Override
public void run() {
Message msg = null;
try {
// convert bitmap to pixels table
int pixels[] = toPixelsTab(mPicture);
// get the features detected into a vector
Vector<Feature> features = SIFT.getFeatures(
mPicture.getWidth(), mPicture.getHeight(), pixels);
// draw features on bitmap
Canvas c = new Canvas(mPicture);
for (Feature f : features) {
drawFeature(c, f.location[0], f.location[1], f.scale,
f.orientation);
}
msg = mHandler.obtainMessage(OK);
} catch (Exception e) {
e.printStackTrace();
msg = mHandler.obtainMessage(ERROR);
} catch (OutOfMemoryError e) {
msg = mHandler.obtainMessage(MEMORY_ERROR);
} finally {
// send the message
mHandler.sendMessage(msg);
}
}
}).start();
}
private int[] toPixelsTab(Bitmap picture) {
int width = picture.getWidth();
int height = picture.getHeight();
int[] pixels = new int[width * height];
// copy pixels of picture into the tab
picture.getPixels(pixels, 0, picture.getWidth(), 0, 0, width, height);
// On Android, Color are coded in 4 bytes (argb),
// whereas SIFT needs color coded in 3 bytes (rgb)
for (int i = 0; i < (width * height); i++)
pixels[i] &= 0x00ffffff;
return pixels;
}
public void drawFeature(Canvas c, float x, float y, double scale,
double orientation) {
Paint paint = new Paint(Paint.ANTI_ALIAS_FLAG);
// line too small...
scale *= 6.;
double sin = Math.sin(orientation);
double cos = Math.cos(orientation);
paint.setStrokeWidth(2f);
paint.setColor(Color.GREEN);
c.drawLine((float) x, (float) y, (float) (x - (sin - cos) * scale),
(float) (y + (sin + cos) * scale), paint);
paint.setStrokeWidth(4f);
paint.setColor(Color.YELLOW);
c.drawPoint(x, y, paint);
}
private final Handler mHandler = new Handler() {
@Override
public void handleMessage(Message msg) {
AlertDialog.Builder builder;
switch (msg.what) {
case OK:
// set the picture with features drawed
mView.setImageBitmap(mPicture);
break;
case MEMORY_ERROR:
builder = new AlertDialog.Builder(CameraActivity.this);
builder.setMessage("Out of memory.\nPicture too big.");
builder.setPositiveButton("Ok", null);
builder.show();
break;
case ERROR:
builder = new AlertDialog.Builder(CameraActivity.this);
builder.setMessage("Error during the process.");
builder.setPositiveButton("Ok", null);
builder.show();
break;
}
mProgressDialog.dismiss();
}
};
}
Sources du projet :
android_sift_camera.zip (Miroir)
VII. Performance▲
Voici le détail des performances de l'algorithme selon différents modèles de téléphone :
- Samung Teos, Photo 3M pixels : 4 secondes ;
- Nexus S, Photo 3M pixels : 2 secondes.
VIII. Pour continuer…▲
La question que tout le monde se pose maintenant est : mais que faire de ces points-clés ?
Intéressons-nous à la javadoc contenue dans la librairie JAR, et notez cette méthode :
static java.util.Vector<PointMatch> SIFT.createMatches(java.util.List<Feature> fs1, java.util.List<Feature> fs2, float max_sd, Model model, float max_id)Cette méthode permet, à partir de deux vecteurs de points-clés calculés chacun sur deux images différentes par exemple, d'obtenir tous les points qui se correspondent entre eux. Pour comprendre à quoi les paramètres de cette méthode correspondent, reportez-vous à la documentation.
Avec tout cela, à vous de trouver les bonnes idées pour exploiter au mieux cet algorithme dans une application !
IX. Remerciements▲
Je tiens particulièrement à remercier ClaudeLELOUP pour sa relecture attentive, ainsi que yan et Feanorin pour leur relecture technique.