points.py 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395
  1. import numpy as np
  2. from scipy import optimize
  3. from .utils import area_pad
  4. class Points:
  5. def __init__(self, points):
  6. if points is None or len(points) == 0:
  7. self._bool = False
  8. self.points = None
  9. else:
  10. self._bool = True
  11. self.points = np.array(points)
  12. if len(self.points.shape) == 1:
  13. self.points = np.array([self.points])
  14. self.x, self.y = self.points.T
  15. def __str__(self):
  16. return str(self.points)
  17. __repr__ = __str__
  18. def __iter__(self):
  19. return iter(self.points)
  20. def __getitem__(self, item):
  21. return self.points[item]
  22. def __len__(self):
  23. if self:
  24. return len(self.points)
  25. else:
  26. return 0
  27. def __bool__(self):
  28. return self._bool
  29. def link(self, point, is_horizontal=False):
  30. if is_horizontal:
  31. lines = [[y, np.pi / 2] for y in self.y]
  32. return Lines(lines, is_horizontal=True)
  33. else:
  34. x, y = point
  35. theta = -np.arctan((self.x - x) / (self.y - y))
  36. rho = self.x * np.cos(theta) + self.y * np.sin(theta)
  37. lines = np.array([rho, theta]).T
  38. return Lines(lines, is_horizontal=False)
  39. def mean(self):
  40. if not self:
  41. return None
  42. return np.round(np.mean(self.points, axis=0)).astype(int)
  43. def group(self, threshold=3):
  44. if not self:
  45. return np.array([])
  46. groups = []
  47. points = self.points
  48. if len(points) == 1:
  49. return np.array([points[0]])
  50. while len(points):
  51. p0, p1 = points[0], points[1:]
  52. distance = np.sum(np.abs(p1 - p0), axis=1)
  53. new = Points(np.append(p1[distance <= threshold], [p0], axis=0)).mean().tolist()
  54. groups.append(new)
  55. points = p1[distance > threshold]
  56. return np.array(groups)
  57. class Lines:
  58. MID_Y = 360
  59. def __init__(self, lines, is_horizontal):
  60. if lines is None or len(lines) == 0:
  61. self._bool = False
  62. self.lines = None
  63. else:
  64. self._bool = True
  65. self.lines = np.array(lines)
  66. if len(self.lines.shape) == 1:
  67. self.lines = np.array([self.lines])
  68. self.rho, self.theta = self.lines.T
  69. self.is_horizontal = is_horizontal
  70. def __str__(self):
  71. return str(self.lines)
  72. __repr__ = __str__
  73. def __iter__(self):
  74. return iter(self.lines)
  75. def __getitem__(self, item):
  76. return Lines(self.lines[item], is_horizontal=self.is_horizontal)
  77. def __len__(self):
  78. if self:
  79. return len(self.lines)
  80. else:
  81. return 0
  82. def __bool__(self):
  83. return self._bool
  84. @property
  85. def sin(self):
  86. return np.sin(self.theta)
  87. @property
  88. def cos(self):
  89. return np.cos(self.theta)
  90. @property
  91. def mean(self):
  92. if not self:
  93. return None
  94. if self.is_horizontal:
  95. return np.mean(self.lines, axis=0)
  96. else:
  97. x = np.mean(self.mid)
  98. theta = np.mean(self.theta)
  99. rho = x * np.cos(theta) + self.MID_Y * np.sin(theta)
  100. return np.array((rho, theta))
  101. @property
  102. def mid(self):
  103. if not self:
  104. return np.array([])
  105. if self.is_horizontal:
  106. return self.rho
  107. else:
  108. return (self.rho - self.MID_Y * self.sin) / self.cos
  109. def get_x(self, y):
  110. return (self.rho - y * self.sin) / self.cos
  111. def get_y(self, x):
  112. return (self.rho - x * self.cos) / self.sin
  113. def add(self, other):
  114. if not other:
  115. return self
  116. if not self:
  117. return other
  118. lines = np.append(self.lines, other.lines, axis=0)
  119. return Lines(lines, is_horizontal=self.is_horizontal)
  120. def move(self, x, y):
  121. if not self:
  122. return self
  123. if self.is_horizontal:
  124. self.lines[:, 0] += y
  125. else:
  126. self.lines[:, 0] += x * self.cos + y * self.sin
  127. return Lines(self.lines, is_horizontal=self.is_horizontal)
  128. def sort(self):
  129. if not self:
  130. return self
  131. lines = self.lines[np.argsort(self.mid)]
  132. return Lines(lines, is_horizontal=self.is_horizontal)
  133. def group(self, threshold=3):
  134. if not self:
  135. return self
  136. lines = self.sort()
  137. prev = 0
  138. regrouped = []
  139. group = []
  140. for mid, line in zip(lines.mid, lines.lines):
  141. line = line.tolist()
  142. if mid - prev > threshold:
  143. if len(regrouped) == 0:
  144. if len(group) != 0:
  145. regrouped = [group]
  146. else:
  147. regrouped += [group]
  148. group = [line]
  149. else:
  150. group.append(line)
  151. prev = mid
  152. regrouped += [group]
  153. regrouped = np.vstack([Lines(r, is_horizontal=self.is_horizontal).mean for r in regrouped])
  154. return Lines(regrouped, is_horizontal=self.is_horizontal)
  155. def distance_to_point(self, point):
  156. x, y = point
  157. return self.rho - x * self.cos - y * self.sin
  158. @staticmethod
  159. def cross_two_lines(lines1, lines2):
  160. for rho1, sin1, cos1 in zip(lines1.rho, lines1.sin, lines1.cos):
  161. for rho2, sin2, cos2 in zip(lines2.rho, lines2.sin, lines2.cos):
  162. a = np.array([[cos1, sin1], [cos2, sin2]])
  163. b = np.array([rho1, rho2])
  164. yield np.linalg.solve(a, b)
  165. def cross(self, other):
  166. points = np.vstack(self.cross_two_lines(self, other))
  167. points = Points(points)
  168. return points
  169. def delete(self, other, threshold=3):
  170. if not self:
  171. return self
  172. other_mid = other.mid
  173. lines = []
  174. for mid, line in zip(self.mid, self.lines):
  175. if np.any(np.abs(other_mid - mid) < threshold):
  176. continue
  177. lines.append(line)
  178. return Lines(lines, is_horizontal=self.is_horizontal)
  179. def area2corner(area):
  180. """
  181. Args:
  182. area: (x1, y1, x2, y2)
  183. Returns:
  184. np.ndarray: [upper-left, upper-right, bottom-left, bottom-right]
  185. """
  186. return np.array([[area[0], area[1]], [area[2], area[1]], [area[0], area[3]], [area[2], area[3]]])
  187. def corner2area(corner):
  188. """
  189. Args:
  190. corner: [upper-left, upper-right, bottom-left, bottom-right]
  191. Returns:
  192. np.ndarray: (x1, y1, x2, y2)
  193. """
  194. x, y = np.array(corner).T
  195. return np.rint([np.min(x), np.min(y), np.max(x), np.max(y)]).astype(int)
  196. def corner2inner(corner):
  197. """
  198. The largest rectangle inscribed in trapezoid.
  199. Args:
  200. corner: ((x0, y0), (x1, y1), (x2, y2), (x3, y3))
  201. Returns:
  202. tuple[int]: (upper_left_x, upper_left_y, bottom_right_x, bottom_right_y).
  203. """
  204. x0, y0, x1, y1, x2, y2, x3, y3 = np.array(corner).flatten()
  205. area = tuple(np.rint((max(x0, x2), max(y0, y1), min(x1, x3), min(y2, y3))).astype(int))
  206. return area
  207. def corner2outer(corner):
  208. """
  209. The smallest rectangle circumscribed by the trapezoid.
  210. Args:
  211. corner: ((x0, y0), (x1, y1), (x2, y2), (x3, y3))
  212. Returns:
  213. tuple[int]: (upper_left_x, upper_left_y, bottom_right_x, bottom_right_y).
  214. """
  215. x0, y0, x1, y1, x2, y2, x3, y3 = np.array(corner).flatten()
  216. area = tuple(np.rint((min(x0, x2), min(y0, y1), max(x1, x3), max(y2, y3))).astype(int))
  217. return area
  218. def trapezoid2area(corner, pad=0):
  219. """
  220. Convert corners of a trapezoid to area.
  221. Args:
  222. corner: ((x0, y0), (x1, y1), (x2, y2), (x3, y3))
  223. pad (int):
  224. Positive value for inscribed area.
  225. Negative value and 0 for circumscribed area.
  226. Returns:
  227. tuple[int]: (upper_left_x, upper_left_y, bottom_right_x, bottom_right_y).
  228. """
  229. if pad > 0:
  230. return area_pad(corner2inner(corner), pad=pad)
  231. elif pad < 0:
  232. return area_pad(corner2outer(corner), pad=pad)
  233. else:
  234. return area_pad(corner2area(corner), pad=pad)
  235. def points_to_area_generator(points, shape):
  236. """
  237. Args:
  238. points (np.ndarray): N x 2 array.
  239. shape (tuple): (x, y).
  240. Yields:
  241. tuple, np.ndarray: (x, y), [upper-left, upper-right, bottom-left, bottom-right]
  242. """
  243. points = points.reshape(*shape[::-1], 2)
  244. for y in range(shape[1] - 1):
  245. for x in range(shape[0] - 1):
  246. area = np.array([points[y, x], points[y, x + 1], points[y + 1, x], points[y + 1, x + 1]])
  247. yield ((x, y), area)
  248. def get_map_inner(points):
  249. """
  250. Args:
  251. points (np.ndarray): N x 2 array.
  252. Yields:
  253. np.ndarray: (x, y).
  254. """
  255. points = np.array(points)
  256. if len(points.shape) == 1:
  257. points = np.array([points])
  258. return np.mean(points, axis=0)
  259. def separate_edges(edges, inner):
  260. """
  261. Args:
  262. edges: A iterate object which contains float ot integer.
  263. inner (float, int): A inner point to separate edges.
  264. Returns:
  265. float, float: Lower edge and upper edge. if not found, return None
  266. """
  267. if len(edges) == 0:
  268. return None, None
  269. elif len(edges) == 1:
  270. edge = edges[0]
  271. return (None, edge) if edge > inner else (edge, None)
  272. else:
  273. lower = [edge for edge in edges if edge < inner]
  274. upper = [edge for edge in edges if edge > inner]
  275. lower = lower[0] if len(lower) else None
  276. upper = upper[-1] if len(upper) else None
  277. return lower, upper
  278. def perspective_transform(points, data):
  279. """
  280. Args:
  281. points: A 2D array with shape (n, 2)
  282. data: Perspective data, a 2D array with shape (3, 3),
  283. see https://web.archive.org/web/20150222120106/xenia.media.mit.edu/~cwren/interpolator/
  284. Returns:
  285. np.ndarray: 2D array with shape (n, 2)
  286. """
  287. points = np.pad(np.array(points), ((0, 0), (0, 1)), mode='constant', constant_values=1)
  288. matrix = data.dot(points.T)
  289. x, y = matrix[0] / matrix[2], matrix[1] / matrix[2]
  290. points = np.array([x, y]).T
  291. return points
  292. def fit_points(points, mod, encourage=1):
  293. """
  294. Get a closet point in a group of points with common difference.
  295. Will ignore points in the distance.
  296. Args:
  297. points: Points on image, a 2D array with shape (n, 2)
  298. mod: Common difference of points, (x, y).
  299. encourage (int, float): Describe how close to fit a group of points, in pixel.
  300. Smaller means closer to local minimum, larger means closer to global minimum.
  301. Returns:
  302. np.ndarray: (x, y)
  303. """
  304. encourage = np.square(encourage)
  305. mod = np.array(mod)
  306. points = np.array(points) % mod
  307. points = np.append(points - mod, points, axis=0)
  308. def cal_distance(point):
  309. distance = np.linalg.norm(points - point, axis=1)
  310. return np.sum(1 / (1 + np.exp(encourage / distance) / distance))
  311. # Fast local minimizer
  312. # result = optimize.minimize(cal_distance, np.mean(points, axis=0), method='SLSQP')
  313. # return result['x'] % mod
  314. # Brute-force global minimizer
  315. area = np.append(-mod - 10, mod + 10)
  316. result = optimize.brute(cal_distance, ((area[0], area[2]), (area[1], area[3])))
  317. return result % mod