Verbesserung der logischen MATLAB-Indizierungsleistung

Question

Ich arbeite an einer Funktion, die alle Punkte innerhalb eines Begrenzungsrahmens um eine Linie von einem großen Koordinatensatz auswählt (um eine RANSAC-Anpassung zu beschleunigen). Ich lief das Skript mit der Funktion letzte Nacht, und von den insgesamt 55k Sekunden 30k (in 55M Anrufe) wurden in dieser Zeile ausgegeben (X sind 3 × N kartesischen Koordinaten, xmin, xmax usw. sind Vektoren der gleichen Länge wie X und entsprechende Grenzen):

inlierIdx = (X(1,:) >= xmin & X(1,:) <= xmax & X(2,:) >= ymin & X(2,:) <= ymax); 

Können Sie mir helfen, wie man dies beschleunigt? Ein Kurzschluss, der ein guter Anfang für die Verbesserung der Leistung wäre, scheint bei der Indexierung nicht zu funktionieren.

Oder wenn es eine völlig andere besserer Ansatz wäre, hier ist der Rest des Codes der Funktion (p1 sind p2 die Punkte der Linie zu definieren, eine ist die des Begrenzungsrahmens versetzt, die zusätzlichen Schritte dauerte weitere 12k Sekunden für 55M Anrufe):

function [inlierX, xmin, xmax, ymin, ymax] = selectbox(X, L, a) % xmin ... ymax only for plotting purposes 
% X: 3xN coords to check; L: 3x2 vector defining line; a: offset of bounding box 
p1 = L(:,1); 
p2 = L(:,2); 

constfactor = (X(3,:)-p1(3))/(p2(3)-p1(3)); % precompute for following steps 
xmin = p1(1) + (p2(1)-p1(1))*constfactor - a; % line parallel to x-component of defined line, with offset 
xmax = xmin + 2*a; 
ymin = p1(2) + (p2(2)-p1(2))*constfactor - a; 
ymax = ymin + 2*a; 

inlierIdx = (X(1,:) >= xmin & X(1,:) <= xmax & X(2,:) >= ymin & X(2,:) <= ymax); 

if p1(3) == p2(3) % singularity if line is horizontal, discard then 
    inlierIdx = []; 
end 

inlierX = X(:,inlierIdx); % save & return inlier coordinates 

Es fiel mir nur, dass ich die Singularität bewegen sollte if-Klausel so die Berechnung, wenn wahr wird übersprungen, aber das ist eine geringe Leistungseinbußen.

Die Funktion wird für jedes RANSAC-Sample aufgerufen, um nur Punkte in einer angemessenen Entfernung von der abgetasteten Linie auszuwählen, um ihre Entfernung für die Schwellenwertbildung zu berechnen.

MATLAB-Version ist R2016a.

Parallel Computing Toolbox ist verfügbar, ich habe versucht, die Schritte in Arrayfuns und Aufruf der gesamten Funktion mit GPUArrays, aber es war viel langsamer.

Der ganze Kontext ist wie folgt:

prepare coordinates 

while trialcount < expectedNumTrialsNeeded 

draw random sample (generated array of randomly sampled coordinates and index into it) 

check if sample is not degenerate and has allowed angle 

compute number of inliers: 

    this calls my selectbox function, to select a smaller set of points, which are near enough to check - takes 30k sec of 55k 

    take those points and compute their distance to the line, all points within threshold are inliers - takes 12k secs of 55k 

if number of inliers > best number of inliers yet, this is new best set 

update expected number of trials needed to find sample of only inliers 
increment trialcount 

end 

return best set 

ich mit Arrays von 10k-100k Punkte arbeiten, und für jede Zeile möchte ich, dass ich finden laufen 1E + 5 ... 1E + 6 Studien passen das beste Set. Ich habe ungefähr 50 Zeilen, die passen, ich arbeite durch sie, indem ich Linien der gefundenen Linien lösche und den Algorithmus auf dem Rest mache.

Answer 1

Ich bezweifle, dass diese Linie das echte Problem ist. Sie sagen, Sie machen 55 Millionen Aufrufe an diese Funktion - können wir den Code sehen, der das tut? Weil ich stark befürchte, dass dieser Code ist, wo das wahre Problem liegt.

Ich vermute, dass Sie diese Funktion in einer Schleife aufrufen, die es MATLAB schwer/unmöglich machen würde, den Aufruf mit seinem JIT-Compiler effektiv zu beschleunigen. Wenn das der Fall ist, dann wird die schwerste Last, die gezeigt wird, diese eine Zeile sein, aber es ist nur so langsam, weil Ihre Code-Struktur MATLAB zwingt, den Interpreter aufzurufen, anstatt Maschinencode auszuführen. Wenn dies tatsächlich der Fall ist, wird das Kopieren dieser kleinen Funktion in den Schleifenkörper enorm beschleunigen (das heißt, wenn der Rest des Schleifenkörpers auch beschleunigt werden kann)

Nun Wie auch immer, das könnte ich daraus machen. Es reduziert die Anzahl der Vergleiche auf Kosten der zusätzlichen Indexierung; Ich bezweifle auch, dass das schneller ist ... naja, mach einfach 1000 Anrufe und vergleiche.

function [inlierX, xmin, xmax, ymin, ymax] = selectbox(X, L, a) 

    % X: 3xN coords to check; L: 3x2 vector defining line; a: offset of bounding box 
    p1 = L(:,1); 
    p2 = L(:,2); 

    constfactor = (X(3,:)-p1(3))/(p2(3)-p1(3)); 

    % line parallel to x-component of defined line, with offset 
    xmin = p1(1) + (p2(1)-p1(1))*constfactor - a; 
    xmax = xmin + 2*a; 
    ymin = p1(2) + (p2(2)-p1(2))*constfactor - a; 
    ymax = ymin + 2*a; 

    % singularity if line is horizontal, discard then 
    if p1(3) ~= p2(3)   
     inlierIdx   = X(1,:)   >= xmin;   
     inlierIdx(inlierIdx) = X(1,inlierIdx) <= xmax(inlierIdx); 
     inlierIdx(inlierIdx) = X(2,inlierIdx) >= ymin(inlierIdx); 
     inlierIdx(inlierIdx) = X(2,inlierIdx) <= ymax(inlierIdx);     
    else 
     inlierIdx = []; 
    end 

    inlierX = X(:,inlierIdx); % save & return inlier coordinates 

end 

Answer 2

Wie wäre es mit spaltenweiser Indizierung in Ihrem Code zu verwenden? Ich meine, X als kartesische Nx3-Koordinaten zu verwenden, nicht als 3xN.Soweit ich weiß, kann die spaltenweise Indizierung aufgrund von MATLAB-Arrays schneller sein, die FORTRAN-Weise gespeichert werden.