高效的类距离矩阵计算(手动度量函数) [英] Effificient distance-like matrix computation (manual metric function)
问题描述
我想计算一个距离"矩阵,类似于
例如,假设我们有两个边界框集合,例如 我想计算一个矩阵 给出以下用于计算两个给定bbox之间的IoU的函数: IoU矩阵可以计算如下: 导致: 现在,我想做同样的事情,但是 without 使用该双重for循环.我知道 但是,我看不到如何将IoU的计算嵌入到lambda表达式中.有什么办法可以避免lambda函数吗? 答案 使用lambda形式嵌入IoU的计算似乎非常容易.解决方法如下:
如果您想要高性能的解决方案,则可以使用cython或numba.两者都非常直接地使您的cdist方法的性能提高了3个数量级. 模板功能 对于其他距离函数(如Minkowski距离),我一个月前写了 answer . 自定义功能示例 I want to compute a "distance" matrix, similarly to For example, let's suppose that we have two collections of bounding boxes, such as I want to compute a matrix Given the following function for computing the IoU between two given bboxes: the IoU matrix can be computed as follows: which leads to: Now, I'd like to do the same, but without using that double for-loop. I know that However, I cannot see how I could embed the computation of IoU into a lambda expression. Is there any way to do so or even a different way of avoiding the lambda function? Edit: Answer It seems that it's really very easy to embed the computation of IoU using a lambda form. The solution is as follows:
If you want a performant solution you could use cython or numba. With both it is quite straight forward to outperform your cdist approach by 3 orders of magnitude. Template function For other distance functions like Minkowski distance I have written an answer a month ago. Example with your custom function
这篇关于高效的类距离矩阵计算(手动度量函数)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!import numpy as np
A_bboxes = np.array([[0, 0, 10, 10], [5, 5, 15, 15]])
array([[ 0, 0, 10, 10],
[ 5, 5, 15, 15]])
B_bboxes = np.array([[1, 1, 11, 11], [4, 4, 13, 13], [9, 9, 13, 13]])
array([[ 1, 1, 11, 11],
[ 4, 4, 13, 13],
[ 9, 9, 13, 13]])
J
,其第{i,j}个元素将在A_bboxes
的第i个bbox和B_bboxes
的第j个bbox之间保持IoU. >
def compute_iou(bbox_a, bbox_b):
xA = max(bbox_a[0], bbox_b[0])
yA = max(bbox_a[1], bbox_b[1])
xB = min(bbox_a[2], bbox_b[2])
yB = min(bbox_a[3], bbox_b[3])
interArea = max(0, xB - xA + 1) * max(0, yB - yA + 1)
boxAArea = (bbox_a[2] - bbox_a[0] + 1) * (bbox_a[3] - bbox_a[1] + 1)
boxBArea = (bbox_b[2] - bbox_b[0] + 1) * (bbox_b[3] - bbox_b[1] + 1)
iou = interArea / float(boxAArea + boxBArea - interArea)
return iou
J = np.zeros((A_bboxes.shape[0], B_bboxes.shape[0]))
for i in range(A_bboxes.shape[0]):
for j in range(B_bboxes.shape[0]):
J[i, j] = compute_iou(A_bboxes[i], B_bboxes[j])
J = array([[0.70422535, 0.28488372, 0.02816901],
[0.25388601, 0.57857143, 0.20661157]])
scipy.spatial.distance.cdist
可以对用户定义的2-arity函数执行类似的任务,例如:dm = cdist(XA, XB, lambda u, v: np.sqrt(((u-v)**2).sum()))
J = cdist(A_bboxes, B_bboxes, lambda u, v: compute_iou(u, v)))
J = array([[0.70422535, 0.28488372, 0.02816901],
[0.25388601, 0.57857143, 0.20661157]])
import numpy as np
import numba as nb
from scipy.spatial.distance import cdist
def gen_cust_dist_func(kernel,parallel=True):
kernel_nb=nb.njit(kernel,fastmath=True)
def cust_dot_T(A,B):
assert B.shape[1]==A.shape[1]
out=np.empty((A.shape[0],B.shape[0]),dtype=np.float64)
for i in nb.prange(A.shape[0]):
for j in range(B.shape[0]):
out[i,j]=kernel_nb(A[i,:],B[j,:])
return out
if parallel==True:
return nb.njit(cust_dot_T,fastmath=True,parallel=True)
else:
return nb.njit(cust_dot_T,fastmath=True,parallel=False)
def compute_iou(bbox_a, bbox_b):
xA = max(bbox_a[0], bbox_b[0])
yA = max(bbox_a[1], bbox_b[1])
xB = min(bbox_a[2], bbox_b[2])
yB = min(bbox_a[3], bbox_b[3])
interArea = max(0, xB - xA + 1) * max(0, yB - yA + 1)
boxAArea = (bbox_a[2] - bbox_a[0] + 1) * (bbox_a[3] - bbox_a[1] + 1)
boxBArea = (bbox_b[2] - bbox_b[0] + 1) * (bbox_b[3] - bbox_b[1] + 1)
iou = interArea / float(boxAArea + boxBArea - interArea)
return iou
#generarte custom distance function
cust_dist=gen_cust_dist_func(compute_iou,parallel=True)
A_bboxes = np.array([[0, 0, 10, 10], [5, 5, 15, 15]]*100)
B_bboxes = np.array([[1, 1, 11, 11], [4, 4, 13, 13], [9, 9, 13, 13]]*1000)
%timeit cust_dist(A_bboxes,B_bboxes)
#1.74 ms ± 13.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit cdist(A_bboxes, B_bboxes, lambda u, v: compute_iou(u, v))
#3.33 s ± 11.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
scipy.spatial.distance.cdist
, but using the intersection over union (IoU) between "bounding boxes" (4-dimensional vectors), instead of a typical distance metric (like the Euclidean distance).import numpy as np
A_bboxes = np.array([[0, 0, 10, 10], [5, 5, 15, 15]])
array([[ 0, 0, 10, 10],
[ 5, 5, 15, 15]])
B_bboxes = np.array([[1, 1, 11, 11], [4, 4, 13, 13], [9, 9, 13, 13]])
array([[ 1, 1, 11, 11],
[ 4, 4, 13, 13],
[ 9, 9, 13, 13]])
J
, whose {i,j}-th element will hold the IoU between the i-th bbox of A_bboxes
and the the j-th bbox of B_bboxes
.def compute_iou(bbox_a, bbox_b):
xA = max(bbox_a[0], bbox_b[0])
yA = max(bbox_a[1], bbox_b[1])
xB = min(bbox_a[2], bbox_b[2])
yB = min(bbox_a[3], bbox_b[3])
interArea = max(0, xB - xA + 1) * max(0, yB - yA + 1)
boxAArea = (bbox_a[2] - bbox_a[0] + 1) * (bbox_a[3] - bbox_a[1] + 1)
boxBArea = (bbox_b[2] - bbox_b[0] + 1) * (bbox_b[3] - bbox_b[1] + 1)
iou = interArea / float(boxAArea + boxBArea - interArea)
return iou
J = np.zeros((A_bboxes.shape[0], B_bboxes.shape[0]))
for i in range(A_bboxes.shape[0]):
for j in range(B_bboxes.shape[0]):
J[i, j] = compute_iou(A_bboxes[i], B_bboxes[j])
J = array([[0.70422535, 0.28488372, 0.02816901],
[0.25388601, 0.57857143, 0.20661157]])
scipy.spatial.distance.cdist
can perform a similar task for a user-defined 2-arity function, e.g.: dm = cdist(XA, XB, lambda u, v: np.sqrt(((u-v)**2).sum()))
J = cdist(A_bboxes, B_bboxes, lambda u, v: compute_iou(u, v)))
J = array([[0.70422535, 0.28488372, 0.02816901],
[0.25388601, 0.57857143, 0.20661157]])
import numpy as np
import numba as nb
from scipy.spatial.distance import cdist
def gen_cust_dist_func(kernel,parallel=True):
kernel_nb=nb.njit(kernel,fastmath=True)
def cust_dot_T(A,B):
assert B.shape[1]==A.shape[1]
out=np.empty((A.shape[0],B.shape[0]),dtype=np.float64)
for i in nb.prange(A.shape[0]):
for j in range(B.shape[0]):
out[i,j]=kernel_nb(A[i,:],B[j,:])
return out
if parallel==True:
return nb.njit(cust_dot_T,fastmath=True,parallel=True)
else:
return nb.njit(cust_dot_T,fastmath=True,parallel=False)
def compute_iou(bbox_a, bbox_b):
xA = max(bbox_a[0], bbox_b[0])
yA = max(bbox_a[1], bbox_b[1])
xB = min(bbox_a[2], bbox_b[2])
yB = min(bbox_a[3], bbox_b[3])
interArea = max(0, xB - xA + 1) * max(0, yB - yA + 1)
boxAArea = (bbox_a[2] - bbox_a[0] + 1) * (bbox_a[3] - bbox_a[1] + 1)
boxBArea = (bbox_b[2] - bbox_b[0] + 1) * (bbox_b[3] - bbox_b[1] + 1)
iou = interArea / float(boxAArea + boxBArea - interArea)
return iou
#generarte custom distance function
cust_dist=gen_cust_dist_func(compute_iou,parallel=True)
A_bboxes = np.array([[0, 0, 10, 10], [5, 5, 15, 15]]*100)
B_bboxes = np.array([[1, 1, 11, 11], [4, 4, 13, 13], [9, 9, 13, 13]]*1000)
%timeit cust_dist(A_bboxes,B_bboxes)
#1.74 ms ± 13.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit cdist(A_bboxes, B_bboxes, lambda u, v: compute_iou(u, v))
#3.33 s ± 11.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)