Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Najbliższy sąsiad - dziwny algorytm

227 views
Skip to first unread message

B

unread,
Sep 6, 2010, 8:38:33 AM9/6/10
to
Witam,
mam taki algorytm w C/C++ do szukania najbliższego sąsiada i nie
bardzo rozumiem jego zasady działania.

double d;
double odlMin = ULONG_MAX;
double odlMax = ULONG_MAX;
for (int i = 0; i < MaxElem; i++) {
d = odleglosc( PunktA, tabPunkt[i]);
if (d < odlMin) {
odlMax = odlMin;
odlMin = d;
sasiad = i;
} else if (d < odlMax)
odlMax = d;
}
if (odlMin < 0.6 * odlMax)
return sasiad;
return -1;

Chodzi mi o ustalenie m.in.:
dlaczego odlMin < 0.6 * odlMax?
i dlaczego w taki a nie inny sposób zmienia się wartości odlMin i odlMax?

B.

Mariusz Marszałkowski

unread,
Sep 6, 2010, 11:06:33 AM9/6/10
to
On 6 Wrz, 14:38, B <B...@B.pl> wrote:
> Witam,
>    mam taki algorytm w C/C++ do szukania najbliższego sąsiada i nie
> bardzo rozumiem jego zasady działania.
A skąd go masz?
Pozdrawiam

B

unread,
Sep 6, 2010, 12:05:48 PM9/6/10
to
W dniu 06.09.2010 17:06, Mariusz Marszałkowski pisze:

Stąd:
http://groups.inf.ed.ac.uk/teaching/sdp/archive/sysd2/opencv/latest_tested_snapshot/opencv/samples/c/find_obj.cpp

funkcja:
int
naiveNearestNeighbor( const float* vec, int laplacian,
const CvSeq* model_keypoints,
const CvSeq* model_descriptors )

Tyle, że ponazywałem te rzeczy które wiem już po polsku.

Segmentation Fault

unread,
Sep 6, 2010, 1:52:01 PM9/6/10
to

Bo on nie szuka najbliższego sąsiada, tylko "sąsiada który jest
najbliżej danego, oraz jest dużo bliżej danego niż wszystkie pozostałe".

I to nie jest punkt tylko deskryptor SURF punktu charakterystycznego. Ma
kila wymiarów więcej niż punkt, jeśli już mowa o OpenCV ;)

B

unread,
Sep 7, 2010, 6:35:45 AM9/7/10
to
W dniu 06.09.2010 19:52, Segmentation Fault pisze:

> On 09/06/2010 02:38 PM, B wrote:
>> Witam,
>
> Bo on nie szuka najbliższego sąsiada, tylko "sąsiada który jest
> najbliżej danego, oraz jest dużo bliżej danego niż wszystkie pozostałe".

o, właśnie. Tak coś myślałem, że ten kod robi coś więcej niż tylko
najbliższego sąsiada znajduje, bo na dwa N-elementowe wektory znajdował
mniej niż N par. Czyli, że musi być jakieś kryterium odrzucania
najbliższego. Ale nie bardzo mogłem wyśledzić tego kryterium.

Czyli tak: jeżeli najbliższy sąsiad znajduje się w przedziale od 0 do
60% odległości do najdalszego to OK, w przeciwnym przypadku punkt nie ma
sąsiada. dobrze rozumiem?

> I to nie jest punkt tylko deskryptor SURF punktu charakterystycznego. Ma
> kila wymiarów więcej niż punkt, jeśli już mowa o OpenCV ;)

Oj tam. Takie zoczenie matematyczne. Przecież taki deskryptor można
potraktować jako punkt przestrzeni n-wymiarowej, gdzie n ilość cech w
deskryptorze. :-)
Czyli tak bardziej matematycznie szuka się najbliższe punkty, które są
dużo dalej niż wszystkie pozostałe, w 512-wymiarowej przestrzeni.

B.

0 new messages