Suchalgorithmus zur Erkennung von Nachbarpunkten im 3-D Raum

WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Partner:

Forum

Option

[Erweitert]

• Diese Seite per Mail weiterempfehlen

Gehe zu:

Tom Xi

Forum-Newbie


	Beiträge: 4

	Anmeldedatum: 18.11.10

	Wohnort: ---

	Version: ---

Verfasst am: 31.01.2011, 16:59 Titel: Suchalgorithmus zur Erkennung von Nachbarpunkten im 3-D Raum

Einen wunderschönen guten Tag

Ich zerbreche mir gerade den Kopf über folgendes (hier vereinfachtes) Problem:

Ich habe Punkte im 3-D Raum in einer Matrix, sagen wir mal "XYZ". zu jeden Punkt in diesem Raum sollen die Nachbarpunkte gefunden werden (in einem bestimmten Radius, aber erstmal unwichtig). Nun brauche ich einen Suchalgorithmus der mir diese findet, das Problem ist er sollte sehr schnell sein. Da ich in Suchalgorithmen sagen wir mal gelinde gesagt keine Ahnung habe, hoffe ich darauf das hier jemand besser darüber bescheid weiß.

Der beste Ansatz war mit Hilfe einer minimal Funktion (in Matlab mit min Funktion) Mengen in die einzelnen Richtungen einzugrenzen, also (wenn N=Nachbar und Z=Zentrum P=Punkt)

Ziel: alle Punkte die erfülllen Radius < Abstand zwischen(Z(x,y,z) und N(x,y,z))

Teilmenge für die gilt :

Radius < Abstand zwischen(Z(x) und N(x))

Matlab : sortrows(XYZ,1) - Nach x-Sortieren
min(abs(XYZ(:,1)-(XYZ(Z,1)-Radius)) --- Gibt mir die (linksseitige-)Menge aller Punkte die die Bedingung erfüllen Radius < Abstand zwischen(Z(x) und N(x))

dann wird aus dieser Teilmenge die Teilmenge erzeugt für die gilt
Radius < Abstand zwischen(Z(x) und N(x)) && Abstand zwischen(Z(y) und N(y))

dann wird mit dieser Menge genauso in Z-Richtung verfahren und ich habe die Koordinaten meiner Nachbarpunkte zum Zentrum Z.

Problem: Das ist zu langsam, bei 10e4 Punkten brauch ich ca. 80 sec. Später wird das Problem aber mit 10e6-10e7 Punkten angewendet, sprich die Zeit ist unhaltbar lang.

Lohnt es sich die Punkte mit einem Algorithmus zu nummerieren und so die Nachbarpunkte einfach zu "erkennen" ?

Hat wer einen Vorschlag oder eine Quelle zu einer besseren Lösung?

( Mit for schleifen zu arbeiten ist zu langsam, bevor sich wer die mühe macht Smile

... ach und oben in dem ein Zeilen Beispiel wurde nur die linke Hälfte der X-Richtung betrachtet )

Greetz
Tom

aj.geissler

Forum-Guru


	Beiträge: 251

	Anmeldedatum: 26.11.07

	Wohnort: Seeheim-Jugenheim

	Version: ---

Verfasst am: 01.02.2011, 12:03 Titel:

Hi,

das Problem erinnert mich ein bisschen an die Umwandlung von RGB-Bildern in Bildern mit einer Farbpalette.
Bei großen Bildern mit z.B. 2000 x 1000 Bildpunkten erfolgt diese Umwandlung relativ schnell. Aus den maximal 2 Mio. Punkten mit im worst-case unterschiedlichen RGB (xyz) - Werten sollen diese nur "näcshtgelegene" Farbpalettenwerte ersetzt werden.

Unter dem Stichwort "Hashtable" kannst Du hierbei bei Wikipedia fündig werden.

Idee dabei: Der 3-dimensionale Raum wird grob diskretisiert und die Lage der Punkte den "groben" Würfeln (mit Index gekennzeichnet) zugeordnet.

Als ersten Ansatz dürfte dies ganz OK sein.

Allerdings kann ein Punkt eines Würfels bei diesem Verfahren den nächstgelegenen Punkt in einem anderen Würfel haben.
Ein iterativer Ansatz mit "versetzten Würfeln wäre dann beispielsweise denkbar.

Eine Realisierung einer HashTable-Sortierung könnte sein:

Zitat:

function H=hashtabl(xr,xg,xb,NR,COLMAX);
// HASHTABL Creating a colour histogram
//
// H=HASHTABL(XR,XG,XB)
//
// Description of variables:
// XR,XG,XB: Colour channels RED, GREEN, BLUE, value range {0,...,255},
// see also "BMPCOLOR"
// H : The HashTable. The 1st three columns contain RGB values,
// column 4 contains a RGB representative scalar and
// column 5 the absolute occurence.
// NR : Quantization factor for colour channels
// COLMAX : maximum nuber of colours

[lhs,rhs]=argn();
if rhs==3 then
NR=8;
COLMAX=240; // Number of colours in palette
end

basis=256/NR;
xr=floor(xr ./NR);
xg=floor(xg ./NR);
xb=floor(xb ./NR);

P=xr .*(basis^2) + xg .*basis + xb + 1;
P=P( Smile

.';

px=[ones(1,length(P));P].';

H=sparse(px,ones(P),[1,max(P)]);

[pz,ki,H]=mtlb_find(H);
kipos=ki( Smile

.';
ki=kipos-1;
H=H( Smile

.';

KI=[];
for p=2:-1:0,
kitmp=floor(ki ./(basis^p));
KI=[KI;kitmp];
ki=ki - (basis^p) .*kitmp;
end
H=[KI;kipos;H];

[Hs,k]=gsort(full(H(5, Smile

),'g','i');
H=H(:,k); // Sort by Occurance
H=H(:,$:-1:1); // Flip LEFT <-> RIGHT
if size(H,2)>COLMAX then
H=H(:,1:1:COLMAX);
end
H=H.';
H(:,1:3)=round(255 .*H(:,1:3) ./(basis - 1)); // RGB-Werte {0,...,255}

endfunction // end of hashtabl

Vielleicht hilft Dir das weiter ?

Grüße
Andreas

Tom Xi

Themenstarter

Forum-Newbie


	Beiträge: 4

	Anmeldedatum: 18.11.10

	Wohnort: ---

	Version: ---

Verfasst am: 01.02.2011, 19:23 Titel:

Hi

klingt interessant, mein stand war es jetzt durch eine injektive Zuordnung der Punkte einen Raum um den Zielpunkt eingrenzen zu können ( Die injektive Zuordnung bekomme ich durch externe Umstände "geschenkt" kostet also keine Zeit). Somit habe ich anstatt 10e6 Elemente nur noch 10e3 Element zu druchsuchen. Was , wie ich das auf die schnelle verstanden habe, eine ideale Hashtabelle ohne Kollision wäre ?!
Meine Sorge bezüglich Geschwindigkeit wäre das ich über jeden Zielpunkt loopen muss.... Morgen werde ich mich wieder eingehend damit beschäftigen können und mir die das Hash Prinzip näher anschauen, Lösung folgt

RoyalFlush

Forum-Fortgeschrittener


	Beiträge: 82

	Anmeldedatum: 27.10.08

	Wohnort: ---

	Version: ---

Verfasst am: 04.02.2011, 06:56 Titel:

http://www.mathworks.com/matlabcent.....-search-through-jit-ver-2

Sollte genau das sein was Du suchst...

Sonst einfach im File Eschange nach nearest neighbor suchen...


Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:	Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen

Impressum | Nutzungsbedingungen | Datenschutz | FAQ |

RSS

Hosted by:

Copyright © 2007 - 2024 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.