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

**Yannok** · 10/07/2012, 10h41

Bonjour,
Je pense que j'ai mal placé mon message donc je le déplace au bon endroit voici mon problème :

Je souhaiterai trouver, pour un point donné de la table courante, son plus proche voisin dans la table de référence.

CREATE TABLE table_courante(id_point serial PRIMARY KEY,id_image INTEGER,x_image FLOAT,y_image FLOAT)

CREATE TABLE table_ref(id_point serial PRIMARY KEY,id_image INTEGER,x_image FLOAT,y_image FLOAT).

Pour cela je recherche le plus proche voisin en terme de distance euclidienne
(x-y)² * (x-y)². Dans cet exemple, le vecteur est à 2 dimensions (x et y) mais dans ma vraie table il s'agit d'un vecteur à 64 dimensions (c'est un point d'intérêt avec 64 descripteurs
ex :table_ref.desc_0 - table_courante.desc_0) * (table_ref.desc_0 - table_courante.desc_0) + (table_ref.desc_1 - table_courante.desc_1) + etc... )

j'aimerais que ma requête retourne l'id du point de l'image courant et l'id du point de l'image de référence pour laquelle la distance est la plus petite, et ceux pour l'ensemble de mes points courants.

Actuellement je suis capable de faire ça :
select table_courante.id_point,table_ref.id_point ,((table_ref.x-table_courante.x)*(table_ref.x-table_courante.x) + (table_ref.y-table_courante.y)*(table_ref.y-table_courante.y)) AS distance FROM table_ref, table_courante WHERE table_courante.id_point=XXX ORDER BY distance LIMIT 1

et je fais une boucle ou XXX prend toutes les valeurs de mon id du point courant (0, 1, 2 ...N)
Mais cette requête prend 3 secondes pour comparer 2 images.. or j'ai 25 images à la sec.. et je dois être capable de faire du temps réel..
Je souhaiterais donc trouver un moyen de ne pas faire de boucle, et /ou trouver une requête complètement différente ou là requête prendrai quelques centaines de ms maximum. A terme la table de ref contiendra des milliers de points..

ATTENTION : ce n'est pas parce que l'id du point de l'image courante = l'id du point de ref qu'il s'agit du même point. Cela n'a rien à voir, ils sont chacun sur 2 images différentes
J'espère que j'ai été clair

Merci d'avance pour votre aide
PS : je travaille sous postgre 9.1. avec un XP et un processeur de 2.5 Ghz
PPS : je débute, Be nice

**vmolines** · 10/07/2012, 12h02

Bonjour,

Effectivement il faut faire une requête "ensembliste" qui retournera chaque POINT et son POI le plus proche.

L'idée est donc de calculer la distance entre POINTet POI pour chaque couple POINT-POI.

La requête qui donne tous les couples POINT-POI avec distance associée :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
	SELECT 
		POINT.POINT_ID,
		POI.POI_ID ,
		((POINT_X - POI_X) * (POINT_X - POI_X)) + ((POINT_Y - POI_Y) * (POINT_Y - POI_Y)) as Distance
	FROM POINT
		 CROSS JOIN POI

Problème, on ne veut conserver que les couples dont la distance est minimale par POINT. Vous pouvez utiliser les fonctions de fenêtrage pour donner un classement par point ordonné selon la distance. Avec un filtre sur ce rang, on obtient le résultat :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
SELECT 
	T1.POINT_ID, 
	T1.POI_ID
 FROM (
	SELECT 
		POINT.POINT_ID,
		POI.POI_ID ,
		rank() OVER (	PARTITION BY POINT_ID 
						ORDER BY ((POINT_X - POI_X) * (POINT_X - POI_X)) + ((POINT_Y - POI_Y) * (POINT_Y - POI_Y))  ASC) as Rang
	FROM POINT
		 CROSS JOIN POI 
) T1
WHERE T1.Rang = 1 ;

J'ai renommé vos tables en POINT (pour table_courante) et POI (pour table_ref) pour ce jeu d'essai sous SQL Server. Postgre propose les fonctions de fenêtrage donc vous devriez pouvoir produire la même requête.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
CREATE TABLE POINT
	(
	POINT_ID int NOT NULL IDENTITY (1, 1),
	POINT_X float(53) NOT NULL,
	POINT_Y float(53) NOT NULL
	)  ; 
 
ALTER TABLE POINT ADD CONSTRAINT
	PK_POINT PRIMARY KEY CLUSTERED 
	(
	POINT_ID
	) ;
 
 
CREATE TABLE POI
	(
	POI_ID int NOT NULL IDENTITY (1, 1),
	POI_X float(53) NOT NULL,
	POI_Y float(53) NOT NULL
	)  ;
 
ALTER TABLE POI ADD CONSTRAINT
	PK_POI PRIMARY KEY CLUSTERED 
	(
	POI_ID
	) ;
 
 
 
INSERT INTO POINT (POINT_X,POINT_Y) values (0.818582670617058, 0.985556772908735) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.713269401399025, 0.81097887205108) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.194535521335627, 0.0124077410312911) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.281937570484938, 0.890160077576039) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.650780078302762, 0.191317610360638) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.0739395509374265, 0.642377348468936) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.401943336164485, 0.708331173034934) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.918973993130198, 0.433642713381434) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.495538496879556, 0.348179912721617) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.345337753427621, 0.851305667201027) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.280108301736595, 0.723436416105253) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.378025936880004, 0.631662934538973) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.275106507213111, 0.719331138163388) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.477358759008437, 0.652521354663928) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.836899393393324, 0.757030029813829) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.379272598750997, 0.264497204375532) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.518435429804046, 0.61987999842367) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.404580630239183, 0.475780263095911) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.299996615929302, 0.0289548956889414) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.597808665550776, 0.62421252059612) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.0824863881499067, 0.617127300005919) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.795573410656195, 0.750726439888149) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.218209832655694, 0.215586131395841) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.356673284682968, 0.996717542701622) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.010561249477826, 0.892809921317062) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.303974245822957, 0.158234673314947) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.585069021531497, 0.325364737374638) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.396544181412241, 0.719660892517354) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.702604908561914, 0.940737598536585) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.780137911853013, 0.0648651624568277) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.65573013576289, 0.762890137243437) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.759380620815709, 0.119872037752179) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.295393774435239, 0.972513845309749) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.617175342125027, 0.437483670048466) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.412156391846973, 0.885318717868316) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.32029186833197, 0.974621642549017) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.952539397281789, 0.206466987875008) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.323427863424759, 0.295114665021911) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.0103716782911807, 0.0235953555543498) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.642784404176997, 0.454567118689553) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.913934540381516, 0.443860613890101) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.137774518251596, 0.568652338963264) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.43354874843968, 0.614665694489118) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.776591098439964, 0.124223021848062) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.638615096097886, 0.965327759212727) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.473263128181409, 0.998366553945839) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.939331017526304, 0.437574550651322) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.0901183996039432, 0.927137834253151) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.760681945856034, 0.381004917303767) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.665515041155488, 0.964143587744259) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.661972671803645, 0.609878966717733) ;
INSERT INTO POINT (POINT_X,POINT_Y) values (0.14069654398478, 0.420648171332581) ;
 
INSERT INTO POI (POI_X,POI_Y) values (0.836918968581705, 0.230316517122635) ;
INSERT INTO POI (POI_X,POI_Y) values (0.233487615722736, 0.0632046546083163) ;
INSERT INTO POI (POI_X,POI_Y) values (0.302121389036649, 0.0943385407217685) ;
INSERT INTO POI (POI_X,POI_Y) values (0.282042353170161, 0.314511812756899) ;
INSERT INTO POI (POI_X,POI_Y) values (0.261757241534069, 0.430522634202843) ;
INSERT INTO POI (POI_X,POI_Y) values (0.74695406561731, 0.257173237766772) ;
INSERT INTO POI (POI_X,POI_Y) values (0.0751587469630914, 0.119406569904903) ;
INSERT INTO POI (POI_X,POI_Y) values (0.066797638251225, 0.602213492833933) ;
INSERT INTO POI (POI_X,POI_Y) values (0.983229638309628, 0.341124710851094) ;
INSERT INTO POI (POI_X,POI_Y) values (0.897105173899553, 0.0406423067350787) ;
INSERT INTO POI (POI_X,POI_Y) values (0.903423780758424, 0.154958098698963) ;
INSERT INTO POI (POI_X,POI_Y) values (0.810294209547822, 0.731991348310767) ;
INSERT INTO POI (POI_X,POI_Y) values (0.212122122317062, 0.431354655545379) ;
INSERT INTO POI (POI_X,POI_Y) values (0.342022606700926, 0.101581384952916) ;
INSERT INTO POI (POI_X,POI_Y) values (0.38628108497448, 0.630766462938606) ;
INSERT INTO POI (POI_X,POI_Y) values (0.99791878516418, 0.359665688517391) ;
INSERT INTO POI (POI_X,POI_Y) values (0.217820516904739, 0.374647511237832) ;
INSERT INTO POI (POI_X,POI_Y) values (0.302931705533707, 0.945980200927524) ;
INSERT INTO POI (POI_X,POI_Y) values (0.251975886303743, 0.746712378201901) ;
INSERT INTO POI (POI_X,POI_Y) values (0.279884576730504, 0.0143419359113965) ;
INSERT INTO POI (POI_X,POI_Y) values (0.806763963118469, 0.488610633638716) ;
INSERT INTO POI (POI_X,POI_Y) values (0.0377105438180498, 0.933290269962104) ;
INSERT INTO POI (POI_X,POI_Y) values (0.540596329924859, 0.0241871846044894) ;
INSERT INTO POI (POI_X,POI_Y) values (0.811370581584759, 0.413491023956223) ;
INSERT INTO POI (POI_X,POI_Y) values (0.746231025875145, 0.668769929567581) ;
INSERT INTO POI (POI_X,POI_Y) values (0.576693687884039, 0.558456106620532) ;
INSERT INTO POI (POI_X,POI_Y) values (0.752239338117783, 0.742715305706587) ;
INSERT INTO POI (POI_X,POI_Y) values (0.477560509444533, 0.418796423930713) ;
INSERT INTO POI (POI_X,POI_Y) values (0.272391194219551, 0.67921453286289) ;
INSERT INTO POI (POI_X,POI_Y) values (0.133719334101453, 0.664918314905708) ;
INSERT INTO POI (POI_X,POI_Y) values (0.548404811360943, 0.0490952658348913) ;
INSERT INTO POI (POI_X,POI_Y) values (0.810448083421498, 0.00197681530135974) ;
INSERT INTO POI (POI_X,POI_Y) values (0.345938763302369, 0.891189020332768) ;
INSERT INTO POI (POI_X,POI_Y) values (0.422260423910426, 0.634441894317258) ;
INSERT INTO POI (POI_X,POI_Y) values (0.0665473940234769, 0.455378297437818) ;
INSERT INTO POI (POI_X,POI_Y) values (0.461324620138421, 0.277931326542238) ;
INSERT INTO POI (POI_X,POI_Y) values (0.933364346074433, 0.240927048909786) ;
INSERT INTO POI (POI_X,POI_Y) values (0.0915775691062137, 0.749052478770752) ;
INSERT INTO POI (POI_X,POI_Y) values (0.482344184839701, 0.883160425515589) ;
INSERT INTO POI (POI_X,POI_Y) values (0.723689338726255, 0.9846905195133) ;
INSERT INTO POI (POI_X,POI_Y) values (0.601811927683792, 0.709611823662558) ;
INSERT INTO POI (POI_X,POI_Y) values (0.988690926837466, 0.468339292970609) ;
INSERT INTO POI (POI_X,POI_Y) values (0.711494638027556, 0.0815508342115718) ;
INSERT INTO POI (POI_X,POI_Y) values (0.511438534459953, 0.158942564297963) ;
INSERT INTO POI (POI_X,POI_Y) values (0.09011509993781, 0.297084436708184) ;
INSERT INTO POI (POI_X,POI_Y) values (0.285338948086004, 0.953383774065311) ;
INSERT INTO POI (POI_X,POI_Y) values (0.759835885829603, 0.65791733439588) ;
INSERT INTO POI (POI_X,POI_Y) values (0.205253381116685, 0.846589869789518) ;
INSERT INTO POI (POI_X,POI_Y) values (0.864401148828737, 0.525531226698574) ;
INSERT INTO POI (POI_X,POI_Y) values (0.173395009892339, 0.265667701903721) ;
INSERT INTO POI (POI_X,POI_Y) values (0.1859368630908, 0.990323715688128) ;
INSERT INTO POI (POI_X,POI_Y) values (0.52622389480383, 0.506639360096308) ;

**Yannok** · 10/07/2012, 12h44

Merci pour l'aide que vous souhaitez m'apporter.

je viens d'implémenter votre algo.
Certes il fonctionne mais comme je vous l'ai dit chaque point n'a pas 2 coordonnées x et y mais 64 descripteurs..

Par conséquent, le temps de calcul avec votre algo ( comparaison de 300 points courant à 300 points de ref prend 9000 ms ... or mon algo avec une boucle prend 2850 ms

Et à l'avenir table_point-ref que vous appelez POI aura plus de 10 000 points..

Merci pour votre aide !

**vmolines** · 10/07/2012, 14h47

Il y a peut être des pistes d'amélioration pour ces requêtes qui donnent le même résultat. Cependant, les algorithmes utilisés restent gloutons et les optimisations offertes par Postgre (indexes spatiaux) pour le calcul de distances euclidiennes se limitent à la 2D si je ne dis pas de bêtises.

Il doit y avoir des pistes algorithmiques plus adaptées dans votre cas. Je ne suis pas du tout connaisseur, aussi je vous conseille de demander sur le forum algorithmie pour tenter une meilleure approche.

**Yannok** · 10/07/2012, 15h15

OK merci quand même pour ton aide..

J'ai du mal à croire que personne d'autre ne s'est intéressé à la recherche du plus proche voisin dans un espace à N dimensions..

C'est pourtant courant maintenant les KD-tree et compagnie... Impossible de trouver une implémentation en tout cas ..

PS : ou est ce que je peux trouver ton forum algorithmie ?

**vmolines** · 10/07/2012, 15h42

Des personnes s'y sont penchées mais il n'y a pas une implémentation native dans Postgre. Vous pouvez vous baser sur les solutions algorithmiques et faire une implémentation sous Postgre si besoin.

**estofilo** · 11/07/2012, 15h51

Envoyé par Yannok

J'ai du mal à croire que personne d'autre ne s'est intéressé à la recherche du plus proche voisin dans un espace à N dimensions..

Postgresql 9.2 actuellement en beta aura des index SP-Gist mais tout reste à faire pour les mettre en pratique dans un kd-tree. En plus 64 dimensions c'est notoirement trop élevé pour une recherche efficace dans un kd-tree, ça reviendrait certainement à une recherche "brute-force".

Il y a plein d'articles au sujet de la recherche de voisins dans un espace à N dimensions, mais ce sont des articles de niveau recherche et pas des tutoriels sur comment faire avec un SGBD. De plus ces articles sont incompréhensibles pour qui n'a pas déjà des connaissances avancées dans ce domaine.
Or tu te dis débutant, il y a à mon sens une contradiction avec le niveau de difficulté du problème auquel tu t'es attaqué.

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

Requêtes PostgreSQL

Vue hybride

Discussions similaires

Partager

Partager