Implementazione di un algoritmo per l'individuazione di punti salienti in dati 3D

3  
  
Introduzione  
  
Un  problema  classico  nella  visione  artificiale  è  
quello  di  determinare  se  l'immagine  analizzata  
contiene  o  no  determinati  oggetti  ( Object  
recognition ).    
L'uomo  riconosce  una  moltitudine  di  oggetti  in  
immagini  con  poco  sforzo,  nonostante  l'immagine  
degli  oggetti  possa  variare  a  causa  di  diversi  
punti  di  vista,  cambiamenti  di  scala  o  rotazioni.  
  
sono  parzialmente  occlusi.  Riconoscere  oggetti  in  
condizioni  così  disparate  rappresenta  ancora  una  
sfida  per  la  computer  vision.    


vengono  considerate  molte  'features',  che  sono  zone  
interessanti  dell'oggetto,  dette  anche  punti  
salienti,  i  quali  possono  essere  estratti  
automaticamente  ne 
una  descrizione  "caratteristica"  dell'oggetto.  
Esempi  di  tali  feature  sono  punti  con  forti  

detti  corner,  o  zone  uniformi  circondate  da  una  
differente  intensità  luminosa,  dette  blob.  Questa  
descrizione  estratta  da  una  immagine  campione  può  
poi  essere  utilizzata  per  identificare  l'oggetto  

importante  che  l'insieme  di  feature  estratte  dal  
modello  sia  invariante  a  rotazioni  e  cambiamenti  di  
scala  delle  immagini  e  robusto  a  rumore  e  cambi  di  
illuminazione,  in  modo  da  rendere  possibile  il  
riconoscimento  basato  su  feature  anche  in  presenza  
di  questi  fattori  di  disturbo.  Quindi  un  detector,  
cioè  un  algoritmo  in  grado  di  estrarre  queste  
feature,  deve  essere  invariante  a  rotazioni  e  
cambiamenti  di  scala,  nonché  robusto  al  rumore  e d   a  
variazioni  fotometriche.    
4  
  
L'approccio  sin  qui  presentato  basato  su  feature  
locali  può  essere  esteso  anche  al  caso  del  
riconoscimento  di  oggetti  in  dati  3D,  quali  quelli  
prodotti  da  una  camera  stereo,  una  camera  di  tipo  
Time  of  Flight  o d   un  laser  scanner.    
Infatti,  in  molte  applicazioni  della  visione  
artificiale,  ed  in  particolare  in  quelle  riferibili  
al  settore  della  robotica ,  si  sta  sempre  più  
diffondendo  l'uso  di  sensori  in  grado  di  acquisire  
dati  3D  al  fine  di  effettuare  in  riconoscimento  
degli  oggetti  presenti  nella  scena.  In  questo  
contesto,  a  differenza  delle  più  convenzionali  
applicazioni  in  ambito  industriale  generalmente  
orientate  al  riconoscimento  di  poche  forme  
elementari,  si  mira  a  sviluppare  sistemi  di  visione  
in  grado  di  riconoscere  le  forme  più  disparate.    
Anche  in  ambito  3D,  in  virtù  delle  occlusioni,  
tipicamente  presenti  nelle  scene  da  analizzare,  si  
segue  prevalentemente  un  approccio  al  
riconoscimento  oggetti  basato  su  feature  locali.  
Come  nel  caso  2D,  si  utilizzano  quindi  detector  in  
grado  di  individuare  le  feature  più  salienti  
presenti  nei  dati  3D  forniti  dal  sistema  di  
acquisizione.  
In  questo  ambito,  una  stima  delle  curvature  

per  fornire  punti  rappresentativi  indipendenti  e  
poter  poi  classificare  correttamente  oggetti  e  
forme.    
In  questa  tesi  è  stato  studiato,  implementato  e  
caratterizzato  sperimentalmente  un  algoritmo  
("detector")  recentemente  proposto  in  letteratura  
[1 ]  per  l'individuazione  di  punti  salienti  in  dati  
3D.  Nella  parte  sperimentale,  l'a l goritmo  
implementato  è  stato  confrontato,  in  particolare  in  
termini  di  ripetibilità  dei  punti  individuati,  con  
due  altre  significative  proposte  presenti  in  
letteratura,  cui  si  farà  riferimento  come  LBSS  [ 2]  
e  LFB -­3D  [ 3].  
5  
  
Tali  metodi  sono  stati  scelti  per  il  confronto  in  
quanto,  analogamente  a  quello  implementato,  sono  
detector  di  tipo  "scale  invariant",  e  cioè  sono  in  
grado  non  solo  di  individuare  i  punti  salienti  in  
dati  3D,  ma  anche  di  determinare  la  dimensione  
dell'intorno  di  ciascuno  di  essi  che  risulta  più  
adeguato  a  stabilire  corrispondenze  fra  le  features  
estratte  in  acquisizioni  differenti  dello  stesso  
oggetto.    
  
  
Nel  primo  capitolo  vengono  presentati  i  concetti  
fondamentali  utilizzat 
brevemente  descritti  gli  altri  due  detector,  LBSS  e  
LFB -­3D  ,  con  cui  verrà  confrontato  questo  metodo.    
Nel  secondo  capitolo  viene  descritta  uno  delle  
procedure  chiave  del  metodo  implementato,  e  cioe'  
la  parametrizzazione  che  consente  di  passare  dal  
dominio  3D,  ad  un  dominio  2D  su  cui  poi  si  andrà  
effettivamente  a  lavorare  per  trovare  i  punti  
caratteristici.  
Nel  terzo  capitolo  viene   
v ero  e  proprio  con  cui  si  andranno  ad  estrarre  i  
punti  salienti  che  verranno  poi  ricollocati  sui  
dati    3D  di  partenza  un  volta  identificati.    
Nel  quarto  capitolo  vengono  presentati  gli  
esperimenti  effettuati,  i  utilizzati  e  le  modifiche  
che  si  sono  rese  necessarie  per  rendere  i  dataset  
  
impiegato  dal  metodo  implementato  nel  lavoro  di  
tesi.    
6  
  
1  Concetti  Fondamentali  
1.1  Detector  
I  detector  si  posso  suddividere  in  base  alla  
tipologia  di  dati  su  cui  lavorano,  cioè  3D  o  2D.  La  
dimensione  aggiuntiva  dei  dati  3D  complicata  il  
compito  del  detector,  specialmente  in  termini  di  
complessità,  ma  questa  informazione  aggiuntiva  può  
essere  utilizzata  per  arricchire  la  risposta  ed  
arrivare  quindi  a  risultati  più  affidabili.  Dati  
una  serie  di  modelli  e  un  oggetto  in  una  
determinata  scena,  è  possibile  riconoscere  di  quale  
oggetto  si  tratt i   
della  scena,  anche  in  presenza  di  altri  oggetti.  
Questa  operazione  sarebbe  molto  più  complicata  
agendo  su  dati  2D.  La  maggior  parte  dei  metodi  noti  

3D  andando  a  cercare  corrispondenze  tra  i  punti  
salienti  del  modello  e   d ella  scena.  Il  primo  passo  
della  ricerca  di  corrispondenze  consiste  quindi  
nell'individuazione  sulla  superficie  del  modello  e  
della  scena  di  alcuni  punti  rappresentativi.  
Vengono  poi  confrontati  con  quelli  del  modello  e  
vengono  valutati  i  match  per  determinare  se  

strumento  che  consente  di  individuare  questi  punti  
è  detto  Detector  3D.  Un  buon  algoritmo  di  detection  

sarà  probabile  individuare  in  nuove  acquisizioni  
dello  stesso  oggetto.  I  punti  individuati  devono  
avere  il  più  possibile  un  intorno  caratteristico,  
perché  in  un  secondo  momento  il  punto  estratto  
dovrà  essere  descritto  proprio  dal  suo  intorno  in  
modo  da  poter  essere  confrontato  con  i  punti    
estratti  in  altre  acquisizioni  al  fine  di  stabilire  
le  corrispondenze  necessarie  per  il  riconoscimento.  
Questi  algoritmi  che  descrivono  un  intorno  vengono  
chiamat i   Descriptor  e  lavorano  tanto  meglio  quanto  
meglio  lavora  il  detector  che  estrae  i  punti  
salienti .  
7  
  
1. 2   Detector  confrontati  
Per  effettuare  dei  confront i   
implementato  sono  stati  scelti  due  detector,  LBSS  
sviluppato  da  Unnikrishnam  e  Herber t ,  e  LFB -­3D,  
sviluppato  da  Mian,Bennamoun  e  Owens  [3] .  Entrambi  
questi  algoritmi  sono  scale -­invariant  e  quindi  più  
versatili  rispetto  ad  altri  metodi  proposti  in  
letteratura.  Questi  due  algoritmi  vengono  
brevemente  descritti  nelle  sezioni  successive.  
  
1. 2 .1  LBSS    
Unnikrishnam  e  Herber t   presentano  un  algoritmo  
multi  scala(Laplace -­Beltrami  Scale -­Space).  La  
proposta  è  quella  di  costruire  uno  scale -­space  non  
partendo  dalla  normal  map  ma  usando  un  operatore  di  
integrazione  che  mappa  una  funzione  sulla  sua  
rappresentazione  multi  scala.  Per  capire  meglio  
come  funziona  questo  algoritmo  e  la  teoria  che  sta  
dietro  di  esso,  è  necessario  innanzitutto  partire  
dalla  teoria  semplificata  di  curve  2D,  passando  poi  
al  caso  3D.  
                    
A:  R
d  x  R
d   
d  (con  d=2  esse ndo  nel  caso  2D)  che  ha  
la  forma:  
                      
 tura   
in  questione.  


 o  R
d        A  è   quindi  definito  in  termini  di  geometria  
intrinseca  e  non  viene  fatto  riferimento  ad  un  
sistema  di  coordinate  estrinseco.  Questo  permette  
di  avere  un  operatore  invariante  rispetto  alle  
trasformazioni  rigide  nello  spazio  2D.  Affinché  
8  
  
 operatore  sia  invariante  anche  alle  traslazioni  

 -­u,t).  Esso  viene  
fissato  come  kernel  gaussiano  descritto  da:  
          
             
 
   
Con  alcuni  passaggi  è  possibile  dimostrare  come  

generico  punto    (s)  appartenente  alla  curva,  
viene  spostato  in  direzione  della  normale  n
x  in  
maniera  proporzionale  alla  curva  k
x  in  x.  
Per  estendere  tutte  queste  considerazioni  al  caso  

di  un  punto  x  che  giace  su  una  superficie  M  avente  
direzione  della  normale  (in  x)  definita  da  n
x .  

  che  
contengono  n
x  le  cui  normali  giacciono  nello  spazio  

certo  riferimento  tangente.   

  con  la  superficie  M  è  una  

    
  .  
Mediando  le  curvature  di  ogni      in  corrispondenza  
del  punto  x,  si  ottiene  il  valore  di  curvatura  


x  viene  spostato  lungo  la  direzione  n
x ,  in  
proporzione  alla  curvatura  media  H.  Di  seguito  
 .  
Per  prima  cosa  questo  metodo  fissa  una  scala  di  
partenza  t
0
  e  un  numero  di  scale  k.  Il  valore  della  
scala  k -­esima  è  dato  dalla  formula:  
t k =t
0
(1.6)
k  
 h e  unisce  tutti  
i  punti  del  modello,  o  usa  la  mesh  se  questa  è  
fornita.   
più  breve,  calcolata  lungo  il  grafo,  che  separa  due  
punti  qualsiasi  ad  esso  appartenenti,  è  detta  
9  
  
distanza  geodetica  e  verrà  presentata  più  avanti,  
in  questo  caso  la  distanza  geodetica  tra  A  e  B  
sulla  superficie  s  può  essere  vista  come  in  figura  
1:  
  
Figura   1     distanza  geodetica  tra  A  e  B  
  
Iterativamente,  per  ogni  valore  di  scala  t
k ,  

i ,  una  stima  
della  densità  definita  come:  
        
 
  
  

i ,x
j ,t)  è  un  kernel  gaussiano  così  
definito:  
 
 
                    
 
  
   
Il  termine     
 
   rappresenta  la  distanza  
geodetica  del  punto  i  dal  punto  j.  Per  ogni  coppia  

rappresenta  il  peso:  
  
 
   
 
 
  

 
    
 
  
    così  definito:  
10  
  
       
   
 
   
    
 
  
  
       Beltrami,  ovvero  un  
laplaciano  definito  su  una  superficie  nello  spazio  

normalizzato  per  tenere  conto  del  fatto  che  la  
sampling -­density  su  dati  3D  reali  non  è  uniforme.  
Infine  s   
      
 
      
              
    
Si  dichiarano  keypoint  quei  punti  che  presentano  il  
valore  massimo/minimo  di         rispetto:  
 Ai  vicini  x
i  sulla  scala  k -­esima,  che  si  
trovano  entro  una  sfera  di  raggio  t
k .  
 Al  valore  di       

  e       

 .  
  
Figura   2  
In  figura  2  sono  evidenziate  alcune  delle  parti  
dell'oggetto  in  cui  l'algoritmo  trova  dei  punti  
salienti.  In  Figura  3  si  mostra  in  dettaglio  una  di