本文来自光头哥哥的博客【Ordering coordinates clockwise with Python and OpenCV】，仅做学习分享。
代码语言：javascript复制原文链接：https://www.pyimagesearch.com/2016/03/21/ordering-coordinates-clockwise-with-python-and-opencv/
前言
本文我认为我翻译的并不太成功，因为原文光头哥就写的很啰嗦，大概理顺一下思路就是：
光头哥想写一个把识别物体用矩形框起来，并将矩形四个顶点按左上，右上，右下，左下的顺序来排列，他之前写了一个排序算法，但有bug，所以本文介绍了一下旧方法，并介绍了一个新的没有bug的方法。
而这个算法将在本系列后续中发挥作用。
下面是正文：
今天，我们将开始一个系列的第一篇，这个系列为计算对象的大小，并测量它们之间的距离，一共三篇。
而在这之前，首先需要实现一个对四个顶点进行的排序算法。
这篇博文的主要目的是学习如何按左上、右上、右下和左下顺序排列矩形四个顶点。按照这样的顺序排列顶点是执行诸如透视变换或匹配对象角点(例如计算对象之间的距离)等操作的先决条件。
首先回顾一下之前写的原始的、有缺陷的按顺时针顺序排列四个顶点的方法。
原始的(有缺陷的)方法
在原来的
代码语言：javascript复制https://www.pyimagesearch.com/2014/08/25/4-point-opencv-getperspective-transform-example/博客文章中有详细介绍order_points方法。
原始排序算法：
代码语言：javascript复制# import the necessary packages
from __future__ import print_function
from imutils import perspective
from imutils import contours
import numpy as np
import argparse
import imutils
import cv2
def order_points_old(pts):
# initialize a list of coordinates that will be ordered
# such that the first entry in the list is the top-left,
# the second entry is the top-right, the third is the
# bottom-right, and the fourth is the bottom-left
rect = np.zeros((4, 2), dtype="float32")
# the top-left point will have the smallest sum, whereas
# the bottom-right point will have the largest sum
s = pts.sum(axis=1)
rect[0] = pts[np.argmin(s)]
rect[2] = pts[np.argmax(s)]
# now, compute the difference between the points, the
# top-right point will have the smallest difference,
# whereas the bottom-left will have the largest difference
diff = np.diff(pts, axis=1)
rect[1] = pts[np.argmin(diff)]
rect[3] = pts[np.argmax(diff)]
# return the ordered coordinates
return rect第2-8行句柄用于导入本例所需的Python包。稍后我们将在这篇博客中使用imutils包。
第9行定义了order_points_old函数。这个方法只需要一个参数，即我们将要按左上角，右上角，右下角和左下角顺序排列的点集。
我们从第14行开始，定义一个形状为(4,2)的NumPy数组，它将用于存储我们的四个(x, y)坐标集。
给定这些pts，我们将x和y值相加，然后找出最小和最大的和(第17-19行)。这些值分别为我们提供了左上角和右下角的坐标。
然后我们取x和y值之间的差值，其中右上角的点的差值最小，而左下角的距离最大(第23-25行)。
最后，第31行将有序的(x, y)坐标返回给调用函数。
说了这么多，你能发现我们逻辑上的缺陷吗? 我给你个提示：
当这两点的和或差相等时会发生什么?简而言之,悲剧。
如果计算的和s或差diff具有相同的值，我们就有选择错误索引的风险，这会对排序造成级联影响。
选择错误的索引意味着我们从pts列表中选择了错误的点。如果我们从pts中取出错误的点，那么左上角，右上角，右下角和左下角顺序排列就会被破坏。
那么我们如何解决这个问题并确保它不会发生呢? 为了处理这个问题，我们需要使用更合理的数学原理设计一个更好的order_points函数。这正是我们下面要讲的内容。
顺时针排列坐标的更好方法
我们将要介绍的，新的，没有bug的order_points函数的实现可以在imutils包中找到，确切的说是在perspective.py文件中（这个包应该是作者自己发布的，里面包含的是一系列方便的，作者自己定义的辅助算法函数）。
代码语言：javascript复制# import the necessary packages
from scipy.spatial import distance as dist
import numpy as np
import cv2
def order_points(pts):
# sort the points based on their x-coordinates
xSorted = pts[np.argsort(pts[:, 0]), :]
# grab the left-most and right-most points from the sorted
# x-roodinate points
leftMost = xSorted[:2, :]
rightMost = xSorted[2:, :]
# now, sort the left-most coordinates according to their
# y-coordinates so we can grab the top-left and bottom-left
# points, respectively
leftMost = leftMost[np.argsort(leftMost[:, 1]), :]
(tl, bl) = leftMost
# now that we have the top-left coordinate, use it as an
# anchor to calculate the Euclidean distance between the
# top-left and right-most points; by the Pythagorean
# theorem, the point with the largest distance will be
# our bottom-right point
D = dist.cdist(tl[np.newaxis], rightMost, "euclidean")[0]
(br, tr) = rightMost[np.argsort(D)[::-1], :]
# return the coordinates in top-left, top-right,
# bottom-right, and bottom-left order
return np.array([tl, tr, br, bl], dtype="float32")同样，我们从第2-4行开始导入所需的Python包。然后在第5行定义order_points函数，该函数只需要一个参数——我们想要排序的点pts列表。
第7行根据x-values对这些pts进行排序。给定已排序的xordered列表，我们应用数组切片来获取最左边的两个点和最右边的两个点(第12行和第13行)。
因此，最左边的点将对应于左上和左下的点，而最右边的点将对应于右上和右下的点——诀窍在于分清哪个是哪个。
幸运的是，这并不太具有挑战性。 如果我们根据它们的y值对最左边的点进行排序，我们可以分别推出左上角和左下角的点(第15行和第16行)。
然后，为了确定右下角和左下角的点，我们可以应用一点几何图形的知识。
使用左上点作为锚点，我们可以应用勾股定理计算左上点和最右点之间的欧式距离。根据三角形的定义，斜边是直角三角形最大的边。
因此，通过将左上角的点作为锚点，右下角的点将具有最大的欧几里得距离，从而允许我们提取右下角和右上角的点(第22行和第23行)。
最后，第26行返回一个NumPy数组，表示按左上角、右上角、右下角和左下角顺序排列的有序边界框坐标。
测试排序算法
现在我们已经有了order_points的原始版本和更新版本，让我们继续实现order_coordinates.py脚本，并尝试它们：
代码语言：javascript复制# import the necessary packages
from __future__ import print_function
from imutils import perspective
from imutils import contours
import numpy as np
import argparse
import imutils
import cv2
def order_points_old(pts):
# initialize a list of coordinates that will be ordered
# such that the first entry in the list is the top-left,
# the second entry is the top-right, the third is the
# bottom-right, and the fourth is the bottom-left
rect = np.zeros((4, 2), dtype="float32")
# the top-left point will have the smallest sum, whereas
# the bottom-right point will have the largest sum
s = pts.sum(axis=1)
rect[0] = pts[np.argmin(s)]
rect[2] = pts[np.argmax(s)]
# now, compute the difference between the points, the
# top-right point will have the smallest difference,
# whereas the bottom-left will have the largest difference
diff = np.diff(pts, axis=1)
rect[1] = pts[np.argmin(diff)]
rect[3] = pts[np.argmax(diff)]
# return the ordered coordinates
return rect
# construct the argument parse and parse the arguments
ap = argparse.ArgumentParser()
ap.add_argument("-n", "--new", type=int, default=-1,
help="whether or not the new order points should should be used")
args = vars(ap.parse_args())
# load our input image, convert it to grayscale, and blur it slightly
image = cv2.imread("example.png")
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
gray = cv2.GaussianBlur(gray, (7, 7), 0)
# perform edge detection, then perform a dilation erosion to
# close gaps in between object edges
edged = cv2.Canny(gray, 50, 100)
edged = cv2.dilate(edged, None, iterations=1)
edged = cv2.erode(edged, None, iterations=1)第29-32行解析命令行参数。我们只需要一个参数--new，它用于指示应该使用新的还是原始的order_points函数。我们将默认使用原始实现。
然后，我们从磁盘加载example.png，并通过将图像转换为灰度并使用高斯滤波器平滑它来执行一些预处理。
我们继续通过使用Canny边缘检测器来处理图像，然后通过膨胀 侵蚀来缩小边缘图中轮廓之间的任何缝隙。
进行边缘检测后，我们的图像应该是这样的：
正如你所看到的，我们已经能够确定图像中物体的轮廓。
现在我们有了边缘图的轮廓，我们可以应用cv2.findContours函数，实际提取对象的轮廓：
代码语言：javascript复制cnts = cv2.findContours(edged.copy(), cv2.RETR_EXTERNAL,
cv2.CHAIN_APPROX_SIMPLE)
cnts = imutils.grab_contours(cnts)
# sort the contours from left-to-right and initialize the bounding box
# point colors
(cnts, _) = contours.sort_contours(cnts)
colors = ((0, 0, 255), (240, 0, 159), (255, 0, 0), (255, 255, 0))然后，我们从左到右对对象轮廓进行排序，这不是必需的，但是可以更容易地查看脚本的输出。 下一步是在每个轮廓线上分别循环：
代码语言：javascript复制for (i, c) in enumerate(cnts):
# if the contour is not sufficiently large, ignore it
if cv2.contourArea(c) < 100:
continue
# compute the rotated bounding box of the contour, then
# draw the contours
box = cv2.minAreaRect(c)
box = cv2.cv.BoxPoints(box) if imutils.is_cv2() else cv2.boxPoints(box)
box = np.array(box, dtype="int")
cv2.drawContours(image, [box], -1, (0, 255, 0), 2)
# show the original coordinates
print("Object #{}:".format(i 1))
print(box)第2行开始循环我们的轮廓线。如果轮廓不够大(由于边缘检测过程中的“噪声”)，我们放弃轮廓区域(第4和5行)。
否则，第8-11行处理计算轮廓的旋转包围框(注意使用cv2.cv.BoxPoints）[如果使用的是OpenCV 2.4]或cv2.boxPoints[如果我们使用OpenCV 3])，并在图像上绘制轮廓。
我们还将打印原始的旋转包围框，这样我们就可以在对坐标排序后比较结果。
我们现在准备好按顺时针方向排列边界框坐标：
代码语言：javascript复制 # order the points in the contour such that they appear
# in top-left, top-right, bottom-right, and bottom-left
# order, then draw the outline of the rotated bounding
# box
rect = order_points_old(box)
# check to see if the new method should be used for
# ordering the coordinates
if args["new"] > 0:
rect = perspective.order_points(box)
# show the re-ordered coordinates
print(rect.astype("int"))
print("")第5行应用原始的(即有缺陷的)order_points_old函数来按照左上角、右上角、右下角和左下角的顺序排列边框坐标。
如果——new标识符已经传递给函数，那么我们将应用更新后的order_points函数(第8和9行)。
就像我们将原始的边界框打印到控制台一样，我们也将打印有序的点，以确保函数正常工作。
最后，我们可以将结果可视化：
代码语言：javascript复制 # loop over the original points and draw them
for ((x, y), color) in zip(rect, colors):
cv2.circle(image, (int(x), int(y)), 5, color, -1)
# draw the object num at the top-left corner
cv2.putText(image, "Object #{}".format(i 1),
(int(rect[0][0] - 15), int(rect[0][1] - 15)),
cv2.FONT_HERSHEY_SIMPLEX, 0.55, (255, 255, 255), 2)
# show the image
cv2.imshow("Image", image)
cv2.waitKey(0)我们在第2行对矩阵四个点坐标循环，并在图像上绘制它们。
根据color列表，左上的点应该是红色的，右上的点应该是紫色的，右下的点应该是蓝色的，最后左下的点应该是蓝绿色的。
最后，第5-7行在图像上绘制对象编号并显示输出结果。
正如我们所看到的，我们预期的输出是按顺时针顺序排列的，按左上角、右上角、右下角和左下角排列——但对象6除外!
看看我们的终端输出对象6，我们可以看到为什么：
求这些坐标的和，我们得到：
- 520 255 = 775
- 491 226 = 717
- 520 197 = 717
- 549 226 = 775
而这个差异告诉我们：
- 520 – 255 = 265
- 491 – 226 = 265
- 520 – 197 = 323
- 549 – 226 = 323
正如您所看到的，我们最终得到了重复的值!
由于存在重复的值，argmin()和argmax()函数不能像我们预期的那样工作，从而给我们提供了一组错误的“有序”坐标。
要解决这个问题，我们可以使用imutils包中更新的order_points函数。我们可以通过发出以下命令来验证我们更新的函数是否正常工作：
代码语言：javascript复制$ python order_coordinates.py --new 1这一次，我们所有的点被正确地排序，包括对象#6：
当使用透视转换(或任何其他需要有序坐标的项目)时，请确保使用我们更新的实现!
THE END
