我有兩條折線（路徑），每條都由二維點陣串列示。我想計算兩者之間的距離或相似度分數。每個陣列中可能有不同數量的點。如果您要繪制折線并且它們直接在彼此之上，則距離應該為零。
p1 = np.array([[0,0], [5,5], [9,9]])
p2 = np.array([[0,0], [3,3], [6,6], [9,9]])
p3 = np.array([[0,0], [3,4], [6,7], [9,9]])
p4 = np.array([[0,0], [0,9]])
polyline_dist(p1, p2) # Should be 0 since the plots are identical
polyline_dist(p1, p3) # Should be small since the plots are close
polyline_dist(p1, p4) # Should be larger since the plots are much different
我嘗試了一種方法，計算從陣列 1 中的每個點到陣列 2 的線段的距離并取最小距離，然后取所有點的平均值。這很有效，但是對于具有數百個點的較長陣列來說，速度非常慢。
歡迎大家提出意見！
uj5u.com熱心網友回復：
您可以嘗試找到每個繪圖投射到 x 和 y 軸上的區域，然后比較該區域的交集。與有兩條曲線 f(x) 和 g(x) 的微積分類似，您可以使用 (f(x) - g(x)) 的下限到上限的積分找到曲線之間的面積DX。如果您的行沒有重疊的域/共域，您可能需要添加一些懲罰并從 p1[0] 和 p2[0] 的最大值開始，并在 p1[-1] 和 p2[-1 的最小值處結束]。相同的折線彼此之間的距離為 0，因此每條折線之間的面積將為 0。對于折線區域高度垂直的情況，您將檢查 x 軸和 y 軸。我寫了以下代碼減去 sample_at_point 部分，因為它遲到了，這部分需要做的就是在給定軸的 p1 中找到 p 的上下邊界點，然后定義一個直線方程并找到傳遞的點 p 在該直線方程上的位置并回傳該值。我明天會編輯這個答案，但我想我會發布我現在所擁有的。此解決方案適用于您在上面顯示的折線，但是如果折線與基本曲線不相似（例如：圓/任何曲線，其中 f(x) 可能有兩個不同的值），它將失敗。
def polydist(p1, p2):
x_area = area_between_squared(p1, p2, axis=0, value=1)
y_area = area_between_squared(p1, p2, axis=1, value=0)
return (x_area y_area)**0.5
def sample_at_point(p1, p, axis, value):
"""
# There should be a fast way to do this,
# Finnd the bounding points that p is between,
# the bounding points are the max point < p and the min point > p
# these points form a line,
# find the value of p applied to that line formula.
"""
def area_between_squared(p1, p2, axis, value):
start = max(p1[0][axis], p2[0][axis])
start_penalty = start - min(p1[0][axis], p2[0][axis])
end = min(p1[-1][axis], p2[-1][axis])
end_penalty = max(p1[-1][axis], p2[-1][axis]) - end
# Getting late, may edit this later tomorrow with the code for this to work but feel free to implement the following idea below:
axis_points = [x[axis] for x in p1]
axis_points.extend([x[axis] for x in p2])
axis_points.sort()
prev_p1_v = sample_at_point(p1, axis_points[0], axis, value)
prev_p2_v = sample_at_point(p2, axis_points[0], axis, value)
prev_axis_point = axis_points[0]
axis_points.pop(0) # remove the first item
sum = 0
for e in axis_points:
p1_v = sample_at_point(p1, e, axis, value)
p2_v = sample_at_point(p2, e, axis, value)
point_c = p1_v - p2_v
point_b = prev_p1_v - prev_p2_v
area = 0.5 * (point_c point_b) * (e - prev_axis_point)
sum = area
prev_p1_v = p1_v
prev_p2_v = p2_v
prev_axis_point = e
sum *= sum # square the result value, add the penalties since this difference should be positive
sum = start_penalty end_penalty
return sum
uj5u.com熱心網友回復：
感謝您的評論和回答。他們實際上讓我找到了一個很好的解決方案，它使用了 OpenCV 函式pointPolygonTest，它比我寫得不好的 numpy 代碼優化得更多。
方法是通過以相反的順序附加點將折線變成輪廓，然后遍歷第一個陣列的點并呼叫pointPolygonTest以獲取距離。我發現將距離平方有助于放大較小的差異。然后我取所有點的平均值。
這是代碼：
import cv2
import numpy as np
def point_to_polyline_dist(p, polyline):
cnt = np.concatenate((polyline, polyline[::-1]))
return np.abs(cv2.pointPolygonTest(cnt, (int(p[0]),int(p[1])), True))
def polyline_dist(polyline1, polyline2):
return np.mean([point_to_polyline_dist(p, polyline2)**2 for p in polyline1])
p1 = np.array([[0,0], [5,5], [9,9]])
p2 = np.array([[0,0], [3,3], [6,6], [9,9]])
p3 = np.array([[0,0], [3,4], [6,7], [9,9]])
p4 = np.array([[0,0], [0,9]])
print(polyline_dist(p1, p2)) # 0.0
print(polyline_dist(p1, p3)) # 0.1666666666666667
print(polyline_dist(p1, p4)) # 35.333333333333336
這在我的情況下效果很好，因為我的折線有很多短線段。計算兩個陣列之間的距離并將距離相加可能更穩健，如下所示：
def polyline_dist_better(polyline1, polyline2):
dist_1to2 = np.mean([point_to_polyline_dist(p, polyline2)**2 for p in polyline1])
dist_2to2 = np.mean([point_to_polyline_dist(p, polyline1)**2 for p in polyline2])
return dist_1to2 dist_2to1
希望能幫助那里的人！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/421395.html
標籤：