我正在编写一个函数,该函数从大型坐标集中选择所有在一条线周围的边界框内的点(以加速RANSAC拟合)。昨晚我运行了包含该函数的脚本,在总共55k秒的时间内,有30k秒(在55M次调用中)花费在以下代码行上(X
是3×N笛卡尔坐标,xmin
、xmax
等是与X
长度相同且对应的边界向量):
inlierIdx = ( X(1,:) >= xmin & X(1,:) <= xmax & X(2,:) >= ymin & X(2,:) <= ymax );
你能帮我加速这个吗?短路计算可以很好地提高性能,但似乎无法与索引一起使用。
如果有完全不同的更好方法,这是函数代码的其余部分(p1
,p2
是定义线的点,a是边界框的偏移量;额外步骤需要另外12k秒钟处理5500万次调用):
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
我突然想到应该将那个奇异点if语句移动,这样如果条件成立就可以跳过计算,但这会稍微降低性能。
该函数针对每个RANSAC样本进行调用,以选择仅距离采样线合理距离的点来计算它们的距离以进行阈值处理。
MATLAB版本为R2016a。
并行计算工具箱可用,我尝试将步骤移入arrayfuns,并使用gpuArrays调用整个函数,但速度要慢得多。
整个上下文如下:
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
我处理包含1万到10万个点的数组,对于每条线我想要拟合,我运行1E+5...1E+6次试验来找到最佳组合。我有大约50条线需要进行拟合,通过删除找到的线上的异常值并在其余数据上运行算法来完成。
inlierX
重要,还是inlierIdx
也很重要?请把你所拥有的一切都发一个最小化可运行示例! :) - Rody OldenhuisinlierX
,那么不要实例化xmin
等(我假设你并不总是绘图)。 - Steve Heim