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.

SQLpro · 10/07/2012, 18h23

Utilisez PostGIS et mettez un index sur votre colonne géometry cela ira beaucoup plus vite. utilisez ST_Distance et faite le MIN.

A +

vmolines · 10/07/2012, 18h26

Le problème étant que ça n'est pas implémenté pour des géométries à plus de 2 dimensions comme je le disais.

Yannok · 10/07/2012, 21h19

Citation:

Utilisez PostGIS et mettez un index sur votre colonne géometry cela ira beaucoup plus vite. utilisez ST_Distance et faite le MIN.

A +

J'ai déjà fait beaucoup de recherches et j'avais en effet trouver quelques informations parlant de postGIS et de ST distance, mais selon moi, ce n'est pas adapter à des vecteurs à N dimensions ou N = 64 ou 128 ..

ce n'est pas la recherche d'un point en terme de distance (dans un plan 2D) mais bien la recherche d'un point d'intérêt avec son plus proche voisin en terme de descripteurs.

Est ce que vous avez (ou quelqu'un a) déjà implémenté un tel algo ? ça me parait bizarre que non ...

SQLpro · 11/07/2012, 13h30

Citation:

Envoyé par Yannok

ce n'est pas la recherche d'un point en terme de distance (dans un plan 2D) mais bien la recherche d'un point d'intérêt avec son plus proche voisin en terme de descripteurs.

Mais la couche GIS est justement faite pour cela. Lisez l'article que j'ai écrit à ce sujet : http://blog.developpez.com/sqlpro/p9...n-geographiqu/

A +

Yannok · 11/07/2012, 13h52

je vais lire votre article mais vous parlez de st_distance or

Citation:

COMMENT ON FUNCTION public.st_distance(geometry, geometry) IS 'args: g1, g2 - For geometry type Returns the 2-dimensional cartesian minimum distance

on est bien dans un espace 2D et je travaille dans un espace 64 D...
De plus les données traitées par gist sont des points avec des coordonnées x et y. A la limite Z .. Or moi au lieu d'un vecteur (x,y) j'ai un vecteur(d1,d2,..,dN)

estofilo · 11/07/2012, 15h51

Citation:

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é.

Yannok · 11/07/2012, 16h42

1 : Votre article ne m'a pas aidé pour moi il s'agit que d'espace limités à 3D
2 :

Citation:

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é

Heureusement que tout le monde ne pense pas comme ça.. on avancerait pas bcp !

Je pense qu'on s'éloigne pttr du problème et qu'optmiser ma 1ère requête est pttr plus simple..

estofilo · 11/07/2012, 16h52

Citation:

Envoyé par Yannok

Je pense qu'on s'éloigne pttr du problème et qu'optmiser ma 1ère requête est pttr plus simple..

Ta 1ere requête est en 2 dimensions.
Ceux qui essaient de t'aider avec 2 dimensions, tu leur rétorques que ça ne t'intéresse pas parce que tu veux 64 dimensions.
Et tu en conclus qu'il faut optimiser ta requête à 2 dimensions.
Bon courage pour continuer à tourner en rond.

Yannok · 11/07/2012, 17h00

Citation:

Ta 1ere requête est en 2 dimensions.
Ceux qui essaient de t'aider avec 2 dimensions, tu leur rétorques que ça ne t'intéresse pas parce que tu veux 64 dimensions.
Et tu en conclus qu'il faut optimiser ta requête à 2 dimensions.
Bon courage pour continuer à tourner en rond.

Mais non ... la requête est en 64 dimensions :cette phrase est plutôt claire
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... )

l'EXEMPLE de la requête à 2D c'est juste pour comprendre le principe de l'algo que j'essaye d'implémenter

vmolines · 11/07/2012, 17h09

J'ai proposé une autre formulation de requête pour voir si elle pouvait s'avérer plus rapide en l'état (qu'on soit en 2 ou x dimensions). On vous a dit que postgre n'implémentait pas de solution native pour votre problème (à travers des opérateurs et des index spécifiques).

Estofilo a fait remarquer que la littérature sur le sujet indique qu'avec beaucoup de dimensions, il n'y a pas de recherche de solution exacte qui soit rapide. C'est aussi ce que j'ai cru lire (vu mes faibles connaissances) car ils évoquaient systématiquement des approximations pour optimiser ça.

Qu'avez vous cherché/trouvé concernant votre problème si ce n'est penser que postgre disposait en son sein d'une solution toute prête ?

Yannok · 11/07/2012, 17h15

je travaille sous openCV en C++, donc actuellement je réalise l'appariement à l'aide d'une fonction propre à cette bibliothèque appelé cvFindFeatures qui me permet de trouver mes paires (id_courant et id_ref).

En passant par la BDD (après chargement des images) je pensais que j'irais plus vite pour trouver mes paires. c'était une piste comme une autre..

vmolines · 11/07/2012, 17h21

Si vous avez les données en mémoire et que vous utilisez Postgre comme tampon pour y faire des requêtes de traitement d'image avec un algorithme glouton, il ne faut pas s'étonner que vous n'arriviez pas à faire du temps réel surtout vu vos contraintes.

Je ne pense pas que vous utilisez la base de données à bon escient ici.

vmolines · 11/07/2012, 17h25

Avez vous fait des recherches sur votre problème d'un point de vue purement algorithmique pour améliorer les performances ?

SQLpro · 11/07/2012, 20h58

Il n'est pas possible de vous aider sans :
1) le DDL de votre table
2) un jeu d'essais
3) un résultat

Et pas des exemples bidons dont vous avez pollué le forum.

A +

10/07/2012, 10h41	#1
Yannok Inscription : juillet 2012 Messages : 14 Détails du profil Informations personnelles : Sexe : Informations forums : Inscription : juillet 2012 Messages : 14 Points : -3 Points : -3	Point d'intérêt : recherche du plus proche voisin 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
	00

10/07/2012, 15h15	#5
Yannok Inscription : juillet 2012 Messages : 14 Détails du profil Informations personnelles : Sexe : Informations forums : Inscription : juillet 2012 Messages : 14 Points : -3 Points : -3	NON résolu .. 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 ?
	00

10/07/2012, 18h23	#7
SQLpro Rédacteur Frédéric BROUARD Expert SGBDR & SQL Inscription : mai 2002 Messages : 12 080 Détails du profil Informations personnelles : Nom : Frédéric BROUARD Localisation : France Informations professionnelles : Activité : Expert SGBDR & SQL Secteur : Conseil Informations forums : Inscription : mai 2002 Messages : 12 080 Points : 21 678 Points : 21 678	Utilisez PostGIS et mettez un index sur votre colonne géometry cela ira beaucoup plus vite. utilisez ST_Distance et faite le MIN. A + __________________ Frédéric Brouard - SQLpro - ARCHITECTE DE DONNÉES - expert SGBDR et langage SQL Site sur les SGBD relationnels et le langage SQL: http://sqlpro.developpez.com/ *Expert Microsoft SQL Server - M.V.P. (Most valuable Professional) MS Corp.* Blog SQL, SQL Server, modélisation données : http://blog.developpez.com/sqlpro http://www.sqlspot.com : modélisation, conseils, audit, optimisation, formation * * * * * Enseignant CNAM PACA - ISEN Toulon - CESI Aix en Provence * * * * *
	00

11/07/2012, 20h58	#20
SQLpro Rédacteur Frédéric BROUARD Expert SGBDR & SQL Inscription : mai 2002 Messages : 12 080 Détails du profil Informations personnelles : Nom : Frédéric BROUARD Localisation : France Informations professionnelles : Activité : Expert SGBDR & SQL Secteur : Conseil Informations forums : Inscription : mai 2002 Messages : 12 080 Points : 21 678 Points : 21 678	Il n'est pas possible de vous aider sans : 1) le DDL de votre table 2) un jeu d'essais 3) un résultat Et pas des exemples bidons dont vous avez pollué le forum. A + __________________ Frédéric Brouard - SQLpro - ARCHITECTE DE DONNÉES - expert SGBDR et langage SQL Site sur les SGBD relationnels et le langage SQL: http://sqlpro.developpez.com/ *Expert Microsoft SQL Server - M.V.P. (Most valuable Professional) MS Corp.* Blog SQL, SQL Server, modélisation données : http://blog.developpez.com/sqlpro http://www.sqlspot.com : modélisation, conseils, audit, optimisation, formation * * * * * Enseignant CNAM PACA - ISEN Toulon - CESI Aix en Provence * * * * *
	00

10/07/2012, 12h44	#3
Yannok Inscription : juillet 2012 Messages : 14 Détails du profil Informations personnelles : Sexe : Informations forums : Inscription : juillet 2012 Messages : 14 Points : -3 Points : -3	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 !
	00

10/07/2012, 14h47	#4
vmolines Membre Expert Inscription : mars 2005 Messages : 1 682 Détails du profil Informations personnelles : Âge : 30 Localisation : France, Haute Garonne (Midi Pyrénées) Informations forums : Inscription : mars 2005 Messages : 1 682 Points : 2 494 Points : 2 494	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.
	00

10/07/2012, 15h42	#6
vmolines Membre Expert Inscription : mars 2005 Messages : 1 682 Détails du profil Informations personnelles : Âge : 30 Localisation : France, Haute Garonne (Midi Pyrénées) Informations forums : Inscription : mars 2005 Messages : 1 682 Points : 2 494 Points : 2 494	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.
	00

10/07/2012, 18h26	#8
vmolines Membre Expert Inscription : mars 2005 Messages : 1 682 Détails du profil Informations personnelles : Âge : 30 Localisation : France, Haute Garonne (Midi Pyrénées) Informations forums : Inscription : mars 2005 Messages : 1 682 Points : 2 494 Points : 2 494	Le problème étant que ça n'est pas implémenté pour des géométries à plus de 2 dimensions comme je le disais.
	00

11/07/2012, 17h09	#16
vmolines Membre Expert Inscription : mars 2005 Messages : 1 682 Détails du profil Informations personnelles : Âge : 30 Localisation : France, Haute Garonne (Midi Pyrénées) Informations forums : Inscription : mars 2005 Messages : 1 682 Points : 2 494 Points : 2 494	J'ai proposé une autre formulation de requête pour voir si elle pouvait s'avérer plus rapide en l'état (qu'on soit en 2 ou x dimensions). On vous a dit que postgre n'implémentait pas de solution native pour votre problème (à travers des opérateurs et des index spécifiques). Estofilo a fait remarquer que la littérature sur le sujet indique qu'avec beaucoup de dimensions, il n'y a pas de recherche de solution exacte qui soit rapide. C'est aussi ce que j'ai cru lire (vu mes faibles connaissances) car ils évoquaient systématiquement des approximations pour optimiser ça. Qu'avez vous cherché/trouvé concernant votre problème si ce n'est penser que postgre disposait en son sein d'une solution toute prête ?
	10

11/07/2012, 17h15	#17
Yannok Inscription : juillet 2012 Messages : 14 Détails du profil Informations personnelles : Sexe : Informations forums : Inscription : juillet 2012 Messages : 14 Points : -3 Points : -3	je travaille sous openCV en C++, donc actuellement je réalise l'appariement à l'aide d'une fonction propre à cette bibliothèque appelé cvFindFeatures qui me permet de trouver mes paires (id_courant et id_ref). En passant par la BDD (après chargement des images) je pensais que j'irais plus vite pour trouver mes paires. c'était une piste comme une autre..
	00

11/07/2012, 17h21	#18
vmolines Membre Expert Inscription : mars 2005 Messages : 1 682 Détails du profil Informations personnelles : Âge : 30 Localisation : France, Haute Garonne (Midi Pyrénées) Informations forums : Inscription : mars 2005 Messages : 1 682 Points : 2 494 Points : 2 494	Si vous avez les données en mémoire et que vous utilisez Postgre comme tampon pour y faire des requêtes de traitement d'image avec un algorithme glouton, il ne faut pas s'étonner que vous n'arriviez pas à faire du temps réel surtout vu vos contraintes. Je ne pense pas que vous utilisez la base de données à bon escient ici.
	00

11/07/2012, 17h25	#19
vmolines Membre Expert Inscription : mars 2005 Messages : 1 682 Détails du profil Informations personnelles : Âge : 30 Localisation : France, Haute Garonne (Midi Pyrénées) Informations forums : Inscription : mars 2005 Messages : 1 682 Points : 2 494 Points : 2 494	Avez vous fait des recherches sur votre problème d'un point de vue purement algorithmique pour améliorer les performances ?
	00

Outils de la discussion
Afficher une version imprimable Envoyer un lien vers cette page par email