Point d'intérêt : recherche du plus proche voisin

[Yannok]

Bonjour,

je n'ai pas le droit de poster mon code d'origine.

Actuellement l'appariement de points d'intérêt est fait par une fonction codée en C.
Une piste avait été de voir si à partir d'une base de donnée, je pouvais aller beaucoup plus vite que le code en C (de l'ordre de 3*plus vite).

Au lieu de comparer deux images, on aurait stocké leurs points dans la base et récupérer les paires une fois l'algo du plus proche voisin optimisé.
Malheureusement comme je l'ai lu ici et ailleurs, il ne semble pas encore possible d'effectuer une telle requête de manière optimale (50 ms).
Merci vmolines pour votre implémentation et merci à SQLpro pour son expertise

[SQLpro]

Personnellement en test, la recherche d'un point plus proche voisin d'un lot de 100000 points met 5 secondes sans index sous MS SQL Server (SIG) et 0 lorsque c'est indexé.

Démo :

Code :

1
2
3
4
5
6
7
8
9
CREATE TABLE T_POINT
(ID   INT IDENTITY PRIMARY KEY,
 P    GEOMETRY)
GO
 
INSERT INTO T_POINT 
SELECT 'POINT (' + CAST(CHECKSUM(NEWID()) AS VARCHAR(32)) 
       + ' ' + CAST(CHECKSUM(NEWID()) AS VARCHAR(32)) +')'
GO 100000

Code :

1
2
3
4
SET STATISTICS TIME ON;
 
SELECT MIN(P.STDistance('POINT (123456 987654)'))
FROM   T_POINT;

--> SQL Server, Temps d'exécution*: Temps UC = 3292*ms, temps écoulé = 4106*ms.

Code :

1
2
3
4
5
6
7
8
CREATE SPATIAL INDEX X_SIG_P2
ON T_POINT(P)
   WITH ( BOUNDING_BOX = (-2000000000, -2000000000, 2000000000, 2000000000));
GO   
 
SELECT MIN(P.STDistance('POINT (123456 987654)'))
FROM   T_POINT
WHERE  P.STDistance('POINT (123456 987654)') < 10000000;

--> SQL Server \endash Temps d'exécution*: Temps UC = 0*ms, temps écoulé = 9*ms.

A +

[vmolines]

Et avec un vecteur à 64 dimensions au lieu d'un point, quelle est la syntaxe pour la création d'index et la fonction pour le calcul de la distance euclidienne ? Quid des temps de réponse ?

[SQLpro]

Je suppose qu'un vecteur peut être représenté par un polygone... Cela ne change donc rien aux performances, l'indexation étant de complexité logarithmique. Donc au lieu d'un temps de réponse de zero, vous aurez zero + epsilon...

A +

[vmolines]

Etant mauvais en math, je pose la question suivante : pouvez vous utiliser l'opérateur de distance entre des polygones (votre matérialisation d'un point dans un espace à N dimensions) en ayant les mêmes résultats que le calcul traditionnel de distance entre points de ce même espaces à N dimensions.

Mon intuition me dit que non mais je serais heureux de me tromper.

[Yannok]

Si j'ai bien compris, vous mettez 9 ms pour trouver le plus proche voisin d'un point par rapport à 10000 points.
et ce, uniquement par rapport aux coordonnées x,y.

Donc moi qui doit faire ça pour une image (300 points).. cela prendrait 300 * 9 ms = 2.7 sec.

et j'ai 25 images à la sec : 2.7 * 25 = 67.5 sec.

Donc pour traiter une seconde de vidéo (25 images) cela me prendrait un peu plus d'une min..
et là on a comparé que des vecteurs 2D et non 64 D

Actuellement avec mon prgm en C++ je suis à une min de vidéo pour 2 min de traitement. et en passant par la BDD, je suis capable de trouver , pour chaque point, le voisin le plus proche, en 2.8 sec à l'aide d'une boucle comme indiqué dans le tout premier post (résultat qui reste totalement médiocre quand même surtout que je compare à une BDD d'un peu moins de 1000 pts)

Voilà l'ampleur de mon problème. J'espère que je suis plus clair.

Donc au lieu d'un temps de réponse de zero, vous aurez zero + epsilon...

un temps de réponse de zéro .. lol !
tout est dans le Epsilon justement =)

Je pense que les polygones utilisés par postgis sont uniquement des ensembles de points, à l'exemple de http://postgis.refractions.net/docum...-1.3/ch03.html

[SQLpro]

Envoyé par Yannok

Si j'ai bien compris, vous mettez 9 ms pour trouver le plus proche voisin d'un point par rapport à 10000 points.
et ce, uniquement par rapport aux coordonnées x,y.

Donc moi qui doit faire ça pour une image (300 points).. cela prendrait 300 * 9 ms = 2.7 sec.

et j'ai 25 images à la sec : 2.7 * 25 = 67.5 sec.

Donc pour traiter une seconde de vidéo (25 images) cela me prendrait un peu plus d'une min..
et là on a comparé que des vecteurs 2D et non 64 D

Actuellement avec mon prgm en C++ je suis à une min de vidéo pour 2 min de traitement. et en passant par la BDD, je suis capable de trouver , pour chaque point, le voisin le plus proche, en 2.8 sec à l'aide d'une boucle comme indiqué dans le tout premier post (résultat qui reste totalement médiocre quand même surtout que je compare à une BDD d'un peu moins de 1000 pts)

Voilà l'ampleur de mon problème. J'espère que je suis plus clair.

un temps de réponse de zéro .. lol !
tout est dans le Epsilon justement =)

Je pense que les polygones utilisés par postgis sont uniquement des ensembles de points, à l'exemple de http://postgis.refractions.net/docum...-1.3/ch03.html

Non pas 9 ms... 0 ms En effet, 0 ms (pas mesurable) est le temps d'utilisation du CPU. Le temps écoulé tient compte de l'envoi des données (aller vers le moteur SQL et retour de réponse) qui sera le même quelque soit le nombre de points à calculer...

Et il est parfaitement possible de trouver la distance entre un polygone et un point, sachant que ce qui vous importe est le min, cela ne pose pas de problème...

Bref, il faut tester !

A +