Effiziente Suche in Bilddatenbanken
1. Wieso nicht lineare Suche?
• sinnige Datenbanken haben 100+ Bilder
• kleine Referenzbilder (640*480) 1000+ keys im Schnitt
• bei 1120*840 sind es 4000+ keys im Schnitt
• die Dimension eines keys ist 128
• Nearest Neighbour
• Abstandsmaß: Euklidscher Abstand
=> Lineare Suche dauert bei 100 größern Bildern 1 Stunde und mehr
2. Was haben wir gemacht?
• Aufbau eines KD-Baumes
• Binärbaum mit bucketsize an Elementen in einem Blatt
• Nearest Neighbour Suche auf dem KD-Baum
• Beschleunigung der Suche mittels einer Heuristik
• Optimierung mittels BestBinFirst
• Auswertungen und Messungen
3.1 Aufbau des KD-Baum
1. Berechne die Varianz aller Keys in jeder Dimension
2. Wähle die Dimension mit der größten Varianz
3. Sortier über die Dimension und ermittle den Median
4. Teile die Keymenge durch einen Knoten am Median,
vermerke Median und Dimension im Knoten
5. Wiederhole die Schritte für die Söhne bis nur noch
bucketsize oder weniger keys existieren
6. Erstelle ein Blatt, in das die übrig Keys gepackt werden
3.2 Übersicht KD-Baum
Innerer Knoten:
...
• Median
...
• Dimension
...
...
Blatt:
KD-Tree
• bucketsize an keys
3.3 Aufbau an einem Beispiel
Gegeben:
 021  021   1    1  0   8 
              
 0 4 9  0 4 9   2   3   3   7 
, , , ,  ,  ,  ,  ,  
 010
3 0  10
3 3
4
4 9
              
 0 6 2  0 6 2   4   5   9  10
              
 10 
 
 10 
Varianzen:    Dimension3
20
 
 11
 
Median10 0 3 3 4 4 9  3
3,3
  2   0  1
 1 1 1
101 03 10 88 
10

  
           
 
 4   0  9
 223333 10
323 77 
6
,
,
Varianzen
,
,
,
:
,
,
,

,
Dimension
3
Varianzen
:
  10  0   3 
 334444 13
434 99 
 7   Dimension1

  
           
 
 6   0  2
 445559  79 9410
10 
7

  
           
 
1
  2   0
  1  0 
 1  8 
 

 
  
  
9
4   0
3   3



 2 1
 7 8  0
Median

10
0
3
Median

0

1
0
,
,
,


  10  0 
 4   4
 3  9 
3
 

 




  
2 
 6   0
 5   9
 4  10
 

 
  
  
0,1
0,3




4.1 Nearest Neighbour Suche im KD-Baum
1. Solange man nicht in einem Blatt ist:
Betrachte den nächsten Knoten und entscheide
anhand der Dimension und des Median ob nach
links oder rechts abgestiegen wird
2. Im Blatt angekommen:
Berechne den Abstand zu allen Keys,
merke dir den minimalen Abstand und
den dazu passenden Key
4.2 Nearest Neighbour Suche im KD-Baum
3. Kletter den Baum wieder hoch und check bei jedem Knoten auf
dem Weg nach oben, ob der Abstand in der Dimension zum
Median kleiner gleich dem bis dato kleinsten Abstands ist
3.a. ist er kleiner gleich dem Median,
so wandere den Teilbaum herunter
3.b ist er größer wandere weiter hoch
4. Ist man in der Wurzel angekommen und
muss nicht mehr runterklettern ist man fertig
5.1 Lowe-Heuristik
Heuristik:
• Besuche maximal n Blätter
=> maximal n*bucketsize an Vergleichen
=> Man ist auf konstante Zeit runter, aber man macht viele Fehler
5.2 Beispielsuche mit NN
8
 
7
 2
 
9
 
Nearest Neighbour von:
Nearest Neighbour:
Distanz:
3,3
2  0  rechtsabsteigen
dist(0,2)  2  10,15  links runter gehen
  2   0

 
 4   0
  10,  0 

 
 6   0

 
0,3
dist(2,3)  1  10,15  rechts runter gehen
  1  0 
  
 3   3
 4 ,  4 
  
 5   9
  
mit hlowe = 2,
 02 wäre
88 1hier
1810
888Ende
877 0
 
 40
dist
dist
 10
0
 
 60
 
103
100
50
2  3  linksabsteigen
0,1
1
 
9
3 
 
2 
 
 81 
 
 792 
 93 
 
10

 42 
8  1  rechtsabsteigen
dist(0,8)  8  7,07  nicht runter gehen
 1  8 
  
 2  7 
 3 ,  9 
  
 4  10
  


 
777 275 0
77 9273

dist
dist
64
49
 949
4144
449
25

19
1
25
49
 103
150
103
103

100
7,

07
10
uninteressant
10
,15
 dist
100

49

81
uninteressant





22 9 121
7
22 33112


 






99 2499910
  975 1
Fertig !!
6.1 Best Bin First
1. Merke dir beim Herunterwandern den Abstand
zu jedem Knoten den Du besucht hast
2. Besuche beim Herraufwandern immer erst den Knoten
mit dem kleinsten Abstand
6.2 Beispielsuche mit BBF
Nearest Neighbour von:
8
 
7
 2
 
9
 
Nearest Neighbour:
Distanz:
81 
 
79 
93 
 
10

 2 
103
50
dist(2,3)  1
3,3
dist(0,8)  8
dist(0,2)  2
0,3
  2   0

 
 4   0
  10,  0 

 
 6   0

 
0,1
1
 
9
4 
 
2 
 
  1  0 
  
 3   3
 4 ,  4 
  
 5   9
  
 1  8 
  
 2  7 
 3 ,  9 
  
 4  10
  
Mit hlowe = 2 => Fertig !
7. Laufzeiten
Laufzeiten:
• NN auf KD-Tree für kleine Dimensionen O(n log(n))
• NN auf KD-Tree für große Dimensionen O(n)
• NN mit hlowe auf KD-Tree O(const)
• BBF mit hlowe auf KD-Tree O(const)
Suche nach ca. 5000 Keys auf einer Datenbankt mit ca. 570 000 Keys:
• Linear&NN etwa 60min
• NN/BBF mit hlowe:
hlowe:
Zeit:(ca.)
-1
20
1000
5000
10000
20000
60min
2.5sek
1 min
6 min
12 min
24 min
=> Linear in Anzahl an Keys, der Keys Datenbank und hlowe
8. Genauigkeit
Referenz: Linearesuche
NN/BBF mit hlowe:
hlowe:
-1
20
1000
5000
10000
20000
NN:
-
80%
50%
35%
25%
15%
BBF
-
65%
25%
10%
5%
3%
60min
2.5sek
1 min
6 min
12 min
24 min
Zeit:(ca.)
Beobachtung:
• wenn nur Bilder gematched werden sollen reicht hlowe 100
(< 1% Bild-Fehlzuweisungen)
• ansonsten BBF&hlowe + Linearesuche auf dem Match
Danke für‘s zuhören !
Quelle: Distinctive image features from scale-invariant keypoints by David G. Lowe, International Journal of Computer Vision, 60, 2 (2004), pp. 91-110.

Effiziente Suche in Bilddatenbanken