def JudgeSameSide(line, unorder_pts): ''' Judge whether the set of points are at the same side or not
Args: line, 1*1 dict, A line determined by two points unorder_pts: n*2 double, set of points
Returns: flag which means whether the points are at the same side or not Bool, True or False '''
[x1, y1] = line['point_1'] [x2, y2] = line['point_2']
x = unorder_pts[:, 0] y = unorder_pts[:, 1]
A = (y1 - y2 )*x + (x2 - x1)*y - x2*y1 + x1*y2
if (all(A >= -0.05) or all(A <= 0.05)): flag = True else: flag = False
return flag
def GetDiagPts(unorder_pts): ''' Get the corners from the set of points Args: unorder_pts: n*2 double, set of points
Returns: two diag corners corners: [diag_corner_1, diag_corner_2], 1*2 double '''
x_increasing_index = np.argsort(unorder_pts, axis = 0) L_corner_pt = unorder_pts[x_increasing_index.T[0][0]].reshape(1, 2) R_corner_pt = unorder_pts[x_increasing_index.T[0][-1]].reshape(1, 2) U_corner_pt = unorder_pts[x_increasing_index.T[1][0]].reshape(1, 2) D_corner_pt = unorder_pts[x_increasing_index.T[1][-1]].reshape(1, 2)
corners = np.concatenate((L_corner_pt, R_corner_pt, U_corner_pt, D_corner_pt)) Diag_corners = []
line = {'point_1': [], 'point_2': []}
for corner_i in corners: for corner_j in corners: if (np.array_equal(corner_i, corner_j)): break else: line['point_1'] = corner_i line['point_2'] = corner_j
flag = JudgeSameSide(line, unorder_pts) if (flag == False): Diag_corners = [corner_i, corner_j] return Diag_corners
def IsSameline(line_1, line_2, threshold): ''' Judge whether line_1, line_2 are the same line
Args: line_1, line_2: 1*1 dict, A line determined by two points threshold: double, minimium value of angle between two lines
Returns: flag: Ture or False, bool '''
assert(np.array_equal(line_1['point_1'], line_2['point_1']))
direction_1 = np.array([(line_1['point_1'][0] - line_1['point_2'][0]), (line_1['point_1'][1] - line_1['point_2'][1])]).reshape(1,2) direction_2 = np.array([(line_2['point_1'][0] - line_2['point_2'][0]), (line_2['point_1'][1] - line_2['point_2'][1])]).reshape(1,2) angle = np.degrees(np.arccos(np.dot(direction_1, direction_2.T)/(np.linalg.norm(direction_1)*np.linalg.norm(direction_2))))
if angle > 90: angle = 180-angle if angle <= threshold: flag = True else: flag = False
return flag
def GetBoundaryLine(diag_corner, unorder_pts): ''' Get the boundary line from the two diag corners
Args: diag_corner: 1*2 double, one of the diag corners unorder_pts: n*2 double, set of points
Returns: BoundaryLine: dict, {'point_1': [], 'point_2': []} '''
diff_x_y = unorder_pts - diag_corner dist_diag_corner = np.array(np.sqrt(np.square(diff_x_y[:, 0]) + np.square(diff_x_y[:, 1])))
dist_increasing_index = np.argsort(dist_diag_corner)
current_line = {'point_1': [], 'point_2': []} firstLine = {'point_1': [], 'point_2': []} secondLine = {'point_1': [], 'point_2': []} line = {'point_1': diag_corner, 'point_2': [1, 1]}
num_lines = 0 threshold = 10
for current_pt in unorder_pts[dist_increasing_index]: if (np.array_equal(current_pt, diag_corner)): continue else: current_line['point_1'] = diag_corner current_line['point_2'] = current_pt
flag_sameside = JudgeSameSide(current_line, unorder_pts) if flag_sameside:
if(IsSameline(current_line, line, threshold) == False):
line = current_line.copy() num_lines += 1
if (num_lines == 1): firstLine = line.copy()
elif (num_lines == 2): secondLine=line.copy() break else: print('Your data is wrong!')
return firstLine, secondLine
def CalcPoint(line_1, line_2): ''' Calculate the point of intersection line_1 and line_2 Args: line_1, ine_2: 1*1 dict, A line determined by two points Returns: Point_intersection: 1*2 double, location of the point of intersection '''
A = np.array([line_1['point_1'][1]-line_1['point_2'][1], line_1['point_2'][0] - line_1['point_1'][0], line_2['point_1'][1]-line_2['point_2'][1], line_2['point_2'][0] - line_2['point_1'][0]]).reshape(2,2)
b = np.array([line_1['point_2'][0]*line_1['point_1'][1] - line_1['point_1'][0]*line_1['point_2'][1], line_2['point_2'][0]*line_2['point_1'][1] - line_2['point_1'][0]*line_2['point_2'][1]]).reshape(2, 1)
Point_intersection = np.array(np.dot(np.linalg.inv(A), b)).reshape(1, 2) return Point_intersection
def FindNearestPt(Point_intersection, unorder_pts): ''' Find the nearest point by the point of intersection in the unorder points Args: Point_intersection: 1*2 double, location of the point of intersection, [x, y] unorder_pts: n*2 double, set of points Returns: NearestPt: 1*2 double, location of the nearest point, [x, y] '''
diff_x_y = unorder_pts - Point_intersection min_dist_index = np.argmin(np.array(np.sqrt(np.square(diff_x_y[:, 0]) + np.square(diff_x_y[:, 1])))) return unorder_pts[min_dist_index]
def JudgePtUpLine(line, point): ''' Judge whether the point is up the line or not, when the point is on the line, return True
Args: line: 1*1 dict, A line determined by two points point: 1*2 double, location of point
Returns: flag_UpLine: bool, True or False '''
threshold = 1e-3
if (line['point_2'][0] - line['point_2'][0]) >= 0:
A = (line['point_1'][1] - line['point_2'][1])*point[0] + (line['point_2'][0] - line['point_1'][0])*point[1] - (line['point_2'][0]*line['point_1'][1] + line['point_1'][0]*line['point_2'][1])
else:
A = -((line['point_1'][1] - line['point_2'][1])*point[0] + (line['point_2'][0] - line['point_1'][0])*point[1] - (line['point_2'][0]*line['point_1'][1] + line['point_1'][0]*line['point_2'][1]))
if abs(A) < threshold: flag_UpLine = True return flag_UpLine if A > 0: flag_UpLine = True else: flag_UpLine = False return flag_UpLine
def GetCorners_order(Diag_corners, corners): ''' Determine the order of the four corners, by 'Up to down, left to right'
Args: Diag_corners: [diag_corner_1, diag_corner_2], 1*2 double corners: [calc_pt, calc_pt, diag_corner_1, diag_corner_2], 1*4 double
Returns: ordered_corners: the corners which are ordered by 'Up to down, left to right' '''
Diag_line = {'point_1': Diag_corners[0], 'point_2': Diag_corners[1]}
if (Diag_corners[0][0] < Diag_corners[1][0]) and (Diag_corners[0][1] < Diag_corners[1][1]):
flag_PtUpline = JudgePtUpLine(Diag_line, corners[0])
if flag_PtUpline:
ordered_corners = np.vstack((corners[0], Diag_corners[1], Diag_corners[0], corners[1]))
else:
ordered_corners = np.vstack((corners[1], Diag_corners[1], Diag_corners[0], corners[0]))
elif (Diag_corners[0][0] < Diag_corners[1][0]) and (Diag_corners[0][1] > Diag_corners[1][1]):
flag_PtUpline = JudgePtUpLine(Diag_line, corners[0])
if flag_PtUpline:
ordered_corners = np.vstack((Diag_corners[0], corners[0], corners[1], Diag_corners[1]))
else:
ordered_corners = np.vstack((Diag_corners[0], corners[1], corners[0], Diag_corners[1]))
elif (Diag_corners[0][0] > Diag_corners[1][0]) and (Diag_corners[0][1] < Diag_corners[1][1]):
flag_PtUpline = JudgePtUpLine(Diag_line, corners[0])
if flag_PtUpline:
ordered_corners = np.vstack((Diag_corners[1], corners[0], corners[1], Diag_corners[0]))
else:
ordered_corners = np.vstack((Diag_corners[1], corners[1], corners[0], Diag_corners[0]))
elif (Diag_corners[0][0] > Diag_corners[1][0]) and (Diag_corners[0][1] > Diag_corners[1][1]):
flag_PtUpline = JudgePtUpLine(Diag_line, corners[0])
if flag_PtUpline:
ordered_corners = np.vstack((corners[0], Diag_corners[0], Diag_corners[1], corners[1]))
else:
ordered_corners = np.vstack((corners[1], Diag_corners[0], Diag_corners[1], corners[0]))
return ordered_corners
def forwardAffineTransform(T,v1,v2): ''' The forwardAffineTransform is equal to the function transformPointsForward from matlab
Args: T: The matrix of perspective, 3*3 float v1, v2: the martixs x and y which are transformed and un-transformed
Returns: retMat: the transformed vectors '''
if v1.shape[1] != 1 or v2.shape[1] != 1:
print('Vectors must be column-shaped!')
return
elif v1.shape[0] != v2.shape[0]:
print('Vectors must be of equal length!')
return
vecSize = v1.shape[0]
concVec = np.concatenate((v1,v2),axis=1)
onesVec = np.ones((vecSize,1))
U = np.concatenate((concVec,onesVec),axis=1)
retMat = np.dot(U,T) return ((retMat[:,0]/retMat[:,2]).reshape((vecSize,1)), (retMat[:,1]/retMat[:,2]).reshape((vecSize,1)))
def Calibsort(unorder_pts, pts_shape): ''' Sort the unorder points by 'Up to down, left to right'
Args: unorder_pts: n*2 double, set of unordered points pts_shape: 1*2, shape of unorder_pts
Returns: ordered_pts_index: n*2 double, set of ordered points '''
results = np.zeros((pts_shape[0]*pts_shape[1], 2), np.int) results = np.mgrid[:pts_shape[0], :pts_shape[1]].T.reshape(-1, 2)
Diag_corners = GetDiagPts(unorder_pts) firstLineL, secondLineL = GetBoundaryLine(Diag_corners[0], unorder_pts) firstLineR, secondLineR = GetBoundaryLine(Diag_corners[1], unorder_pts)
calc_pt1 = CalcPoint(firstLineL,secondLineR) calc_pt2 = CalcPoint(secondLineL,firstLineR) calc_pt3 = CalcPoint(firstLineL,firstLineR) calc_pt4 = CalcPoint(secondLineL,secondLineR)
lines_list = [firstLineL, secondLineR, secondLineL, firstLineR]
for i in range(0, 2): if i == 1: corners = np.vstack((calc_pt1, calc_pt2, Diag_corners[0], Diag_corners[1])) else: corners = np.vstack((calc_pt3, calc_pt4, Diag_corners[0], Diag_corners[1]))
is_convex = np.zeros((4, 1)) for index in range(0, 4): is_convex[index] = JudgeSameSide(lines_list[index], corners)
if (all(is_convex) == True): corners = np.array([FindNearestPt(corners[0], unorder_pts), FindNearestPt(corners[1], unorder_pts), Diag_corners[0], Diag_corners[1]]).reshape(4, 2) break ordered_corners = GetCorners_order(Diag_corners, corners)
square = np.array([[4,0], [4,4], [0,0], [0,4]], dtype=np.float32).reshape(4, 2) ordered_corners = np.array(ordered_corners, dtype=np.float32)
PerspectiveMatrix = cv.getPerspectiveTransform(ordered_corners, square)
Transform_unorder_pts = forwardAffineTransform(PerspectiveMatrix.T, unorder_pts[:, 0].reshape(pts_shape[0]*pts_shape[1], 1), unorder_pts[:, 1].reshape(pts_shape[0]*pts_shape[1], 1))
Transform_unorder_pts = np.hstack((Transform_unorder_pts[0], Transform_unorder_pts[1])) Transform_unorder_pts = (np.round(Transform_unorder_pts)).astype(np.int)
y_increasing_index = np.argsort(Transform_unorder_pts[:, 1]) x_increasing_index = np.zeros((pts_shape[0]*pts_shape[1],)) for index in range(pts_shape[0]):
x_increasing_index_tmp = np.argsort(Transform_unorder_pts[y_increasing_index][index*pts_shape[1]:(index+1)*pts_shape[1], 0])
x_increasing_index[index*pts_shape[1]:(index+1)*pts_shape[1]] = x_increasing_index_tmp + pts_shape[1]*index x_increasing_index = x_increasing_index.astype(np.int)
if np.array_equal(Transform_unorder_pts[y_increasing_index][x_increasing_index], results): index_x_y = [x_increasing_index, y_increasing_index] return index_x_y else: return None
|