La libreria OpenCV - 13 - Detection, Extraction e Matching con ricerca approssimata Nearest Neighbor

Oggi vediamo un argomento piuttosto importante nell’analisi delle immagini: ricerca approssimata Nearest Neighbor per il matching di feature all’interno di due (o più) immagini.

Questo articolo è stato pubblicato prima della seconda parte dello Stabilizzatore digitale di video per un motivo ben preciso. Infatti, un modulo del sistema introdotto in questo articolo, coinvolge proprio questo argomento.

Di seguito presenteremo a grandi linee il concetto di ricerca approssimata Nearest Neighbors (NN) e come implementare un algoritmo di matching tra immagini che utilizzi questo tipo di ricerca. L’implementazione sarà fatta utilizzando una certa libreria… indovinate quale? … già, OpenCV.

La ricerca NN è un problema molto importante in molte applicazioni come il riconoscimento di immagini, compressione dei dati, riconoscimento e classificazione di pattern, machine learning, sistemi che fanno retrieval di documenti ecc.
Tuttavia, risolvere questo problema negli spazi in alta dimensionalità e molto difficile e soprattutto costoso! Non esistono infatti algoritmi con performance significativamente migliori rispetto alla standard ricerca forza bruta. Questo ha portato a un aumento di interesse in una classe di algoritmi che eseguano la ricerca approssimata Nearest Neighbors. Questo tipo di algoritmi si avvale di apposite strutture di indicizzazione (ad es. il KD-tree) che facilitano la ricerca scartando, ad ogni iterazione, un gran numero di candidati. Chiaramente, essendo la ricerca approssimata, non sempre i risultati saranno esatti ed è per questo che normalmente, a valle della ricerca, ci si avvale di un modulo che individui i match corretti.
È stato provato comunque che la ricerca approssimata NN è un tipo di ricerca che è abbastanza buona nella maggior parte delle applicazioni pratiche e, nella maggior parte dei casi, di ordini di grandezza più veloci rispetto agli algoritmi che fanno ricerche NN esaustive.

Prendiamo il classico esempio che fa OpenCV nei suoi tutorial.
Io voglio vedere se un oggetto rappresentato in un’immagine (la scatola di cantuccini) è all’interno di un’altra immagine (nella quale ci sono più oggetti nella scena).

img. A

img. B

Come si deve procedere?
Ipotizziamo che la img. A, che rappresenta la sola scatola di cantuccini, sia l’immagine di query e vogliamo trovare delle corrispondenze nell’img. B.

1. Fase di Detection: individuo i punti in cui sono presenti delle feature (keypoint)
   
   
2. Fase di Extraction: in un certo modo estraggo da ogni punto trovato in 1. dei vettori n-dimensionali che me li descrivano (descrittori)
3. Fase di Matching: per ogni descrittore dell’img di query si ricerca, in uno spazio a n dimensioni e in maniera approssimata, il “più vicino vicino” tra tutti i descrittori dell’img B. Siccome si parla di ricerca approssimata sarà necessaria una sogliatura per eliminare i match sabgliati.
   
   

Un'altra applicazione, che ci rimarrà utile per il prossimo articolo sullo Stabilizzatore digitale di video, è quella che ci permette di stimare il moto relativo di oggetti rappresentati in due frame successivi di un video.
Eccone un esempio.

Per il detection e l'extraction è stato usato il SIFT mentre per la ricerca approssimata il FLANN (Fast Approximate Nearest Neighbor Search Library) implementata da OpenCV

#include "opencv2/highgui/highgui.hpp"
#include "opencv2/imgproc/imgproc.hpp"
#include "opencv2/features2d/features2d.hpp"
#include "opencv2/nonfree/nonfree.hpp"
#include <opencv2/opencv.hpp>
#include "opencv2/flann/flann.hpp"

using namespace cv;
using namespace std;

void readme();

/** @function main */
int main( int argc, char** argv )
{
  if( argc != 3 )
  { readme(); return -1; }

  Mat img_1 = imread( argv[1], CV_LOAD_IMAGE_GRAYSCALE );
  Mat img_2 = imread( argv[2], CV_LOAD_IMAGE_GRAYSCALE );

  if( !img_1.data || !img_2.data )
  { std::cout<< " --(!) Error reading images " << std::endl; return -1; }

  //-- Step 1: Detect dei keypoints usando SIFT Detector

   SiftFeatureDetector detector( 200 ); //cerca di individuare 200 Sift Keypoints

  std::vector<KeyPoint> keypoints_1, keypoints_2; //dove verranno salvati i keypoints

  detector.detect( img_1, keypoints_1 );
  detector.detect( img_2, keypoints_2 );

  //-- Step 2: Calcolo dei Descrittori (feature vectors)
  SiftDescriptorExtractor extractor;

  Mat descriptors_1, descriptors_2; //dove verranno salvati i descrittori

  extractor.compute( img_1, keypoints_1, descriptors_1 );
  extractor.compute( img_2, keypoints_2, descriptors_2 );

  //-- Step 3: Matching i descrittori usando il FLANN matcher
  FlannBasedMatcher matcher;
  std::vector< DMatch > matches; //dove verranno salvati i match.

  matcher.match( descriptors_1, descriptors_2, matches );

  /*Per ogni keypoint di query viene associato il più simile keypoint
di training. La coppia costituisce (insieme ad altri valori come la
misura di dissimilarità dei loro descrittori "distance"), un elemento
DMatch. Visto che ogni punto di query gli sarà sempre associato un
punto, bisognerà vedere se questo match è effettivo o meno. Dunque
serve una sogliatura*/


  double max_dist = 0; double min_dist = 100;

  //-- Veloce calcolo della massima e della minima distanza tra i descrittori dei keypoint
  for( int i = 0; i < descriptors_1.rows; i++ )
  { double dist = matches[i].distance;
    if( dist < min_dist ) min_dist = dist;
    if( dist > max_dist ) max_dist = dist;
  }

  printf("-- Max dist : %f n", max_dist );
  printf("-- Min dist : %f n", min_dist );

  //-- Disegna solo i match "buoni" (cioè quelli con distanza minore di than 3*min_dist ) - SOGLIATURA
  //-- PS.- qui può essere utilizzato anche radiusMatch. - VEDI DOPO
  std::vector< DMatch > good_matches;

  for( int i = 0; i < descriptors_1.rows; i++ )
  { if(matches[i].distance <= 3*min_dist)
    { good_matches.push_back( matches[i]); }
  }

  //-- Disegna solo i match "buoni"
  Mat img_matches;
  drawMatches( img_1, keypoints_1, img_2, keypoints_2,
               good_matches, img_matches, Scalar::all(-1), Scalar::all(-1),
               vector<char>(), DrawMatchesFlags::NOT_DRAW_SINGLE_POINTS );

  //-- Mostra i match "buoni"
  imshow( "Good Matches", img_matches );

  for( int i = 0; i < good_matches.size(); i++ )
  { printf( "-- Good Match [%d] Keypoint 1: %d  -- Keypoint 2: %d  n", i, good_matches[i].queryIdx, good_matches[i].trainIdx ); }

  waitKey(0);

  return 0;
 }

 /** @function readme */
 void readme()
 { std::cout << " Usage: ./Sift_FlannMatcher <img1> <img2>" << std::endl; }

Per evitare di fare una sogliatura un po' barbara come quella sopra, si può usare il radiusMatch.
Con questo metodo è possibile settare la distanza (distance nel codice sottostante) sopra la quale il match non è considerato buono.

  //...
  vector < vector <DMatch> > good_matches;
  matcher.radiusMatch(descriptors_1,descriptors_2,good_matches,distance,Mat(),false);
  //...

Come è possibile vedere dal prototipo della funzione il risultato verrà scritto in un vector di vector di DMatch.
L’i-esimo elemento del vector corrisponde al vector con tutti i match con distanza minore di distance tra l’i-esimo punto di query e tutti i punti di training (ordinati per somiglianza: il 1° el è il più simile).

Per ora è tutto.
Se ci sono considerazioni, errori o domande da fare, non esitate a lasciare un commento qui sotto!
A presto! 😉

fonte: documentazione OpenCV