Rapide (er) façon de faire correspondre la fonctionnalité à la base de données

Question

Je travaille sur un projet où j'ai une fonctionnalité dans une image décrite comme un ensemble de coordonnées X & Y (5-10 points par caractéristique) qui sont uniques pour cette fonctionnalité. J'ai aussi une base de données avec des milliers de fonctionnalités où chacun a le même type de descripteur. Le résultat ressemble à ceci:

myFeature: (x1,y1), (x2,y2), (x3,y3)... 

myDatabase: Feature1: (x1,y1), (x2,y2), (x3,y3)... 
      Feature2: (x1,y1), (x2,y2), (x3,y3)... 
      Feature3: (x1,y1), (x2,y2), (x3,y3)... 
      ... 

Je veux trouver la meilleure correspondance entre myFeature et myDatabase.

Quel est le moyen le plus rapide de faire correspondre ces fonctionnalités? À l'heure actuelle je quitte que chaque élément dans la base de données et en comparant chaque point:

bestScore = 0 
for each feature in myDatabase: 
    score = 0 
    for each point descriptor in MyFeature: 
     find minimum distance from the current point to the... 
      points describing the current feature in the database 
     if the distance < threshold: 
      there is a match to the current point in the target feature 
      score += 1 

    if score > bestScore: 
     save feature as new best match 

Cette recherche fonctionne, mais clairement il obtient péniblement lent sur de grandes bases de données. Est-ce que quelqu'un connaît une méthode plus rapide pour effectuer ce type de recherche, ou du moins s'il existe un moyen d'exclure rapidement des fonctionnalités qui ne correspondent pas au descripteur?

Answer 1

Créez un ensemble de bits (un tableau de 1 et 0) à partir de chaque entité.

Créez un tel masque pour vos critères de recherche, puis utilisez simplement un bit et comparez le masque de recherche à vos caractéristiques.

Avec cette approche, vous pouvez déplacer la plupart du travail vers les routines chargées de sauvegarder les données. De plus, la création des masques de bits ne devrait pas être aussi intensive en calculs.

Si vous souhaitez exclure des fonctionnalités qui ne peuvent absolument pas correspondre, votre algorithme de création de masques devrait prendre soin de cela et créer un peu de flou sur les masques de bits. La manière la plus simple de créer de tels masques est probablement de créer une matrice aussi grande que la matrice de vos entités et d'en mettre une dans chaque coordonnée définie pour l'entité et un zéro dans chaque coordonnée qui ne l'est pas. Ensuite, transformez cette matrice en une rangée à une dimension. Comparez ensuite la ligne caractéristique au masque de recherche au niveau des bits. Ceci est similaire à la façon dont les index bitmap fonctionnent sur des bases de données volumineuses (oracle, par exemple), mais avec une intention différente et sans une image bitmap complète de toutes les lignes de base de données en mémoire.

La puissance de ceci est dans les comparaisons au niveau du bit.

Sur une machine 32 bits, vous pouvez effectuer 32 comparaisons par instruction lorsque vous ne pouvez en faire qu'une avec des nombres entiers dans une comparaison de points. Il donne encore plus de boni pour les opérations en virgule flottante, en fonction de l'architecture.

Answer 2

Cela ressemble en général à un problème d'index spatial. Ce n'est pas mon domaine, mais vous devrez probablement créer une sorte d'index d'arborescence, tel qu'un quadtree, que vous pouvez utiliser pour rechercher facilement des entités. Vous pouvez trouver quelques liens de cet article wikipedia: http://en.wikipedia.org/wiki/Spatial_index

Il peut s'agir d'un problème que vous pouvez facilement implémenter dans une base de données spatiale existante. C'est très SIG dans sa description. Une chose que vous pouvez faire est de calculer un point de gravité pour chaque fonctionnalité et d'utiliser cela pour réduire un peu l'espace de recherche (une recherche unidimensionnelle est beaucoup plus facile à construire pour un index), mais cela a l'inconvénient d'être juste une heuristique (selon les formes de votre caractéristique, le point de gravité peut finir dans des endroits étranges).