质心跟踪算法

质心跟踪算法依赖于（1）现有对象质心（即，质心跟踪器之前已经看到的对象）与（2）视频中后续帧之间的新对象质心之间的欧几里得距离 。质心跟踪算法的主要假设是一个给定的对象将潜在地移动在后续的帧之间，但距离为帧中的质心之间和将小比对象之间的所有其它距离。因此，如果我们选择将质心与后续帧之间的最小距离相关联，则可以构建对象跟踪器。另外，我们将在旧对象无法与任何现有对象匹配的情况下（总共N个后续帧）注销旧对象。

步骤1：接受边界框坐标并计算质心

步骤2：计算新边界框与现有对象之间的欧几里得距离

步骤3：更新（x，y） -现有对象的坐标

步骤4：注册新对象

步骤5：注销旧对象

初始化下一个唯一的对象ID和两个有序的用于跟踪映射给定对象的字典 ID到它的质心和它拥有的连续帧数分别被标记为“消失”

存储给定的最大连续帧数对象被标记为“消失”，直到我们需要注销跟踪对象，CentroidTracker为质心跟踪器

    # import the necessary packages
    from scipy.spatial import distance as dist
    from collections import OrderedDict
    import numpy as np
    class CentroidTracker():
        def __init__(self, maxDisappeared=50):
            self.nextObjectID = 0
            self.objects = OrderedDict()
            self.disappeared = OrderedDict()
            self.maxDisappeared = maxDisappeared

注册对象时，我们使用下一个可用的对象ID存储质心。register为注册新对象的方法。

        def register(self, centroid):
            self.objects[self.nextObjectID] = centroid
            self.disappeared[self.nextObjectID] = 0
            self.nextObjectID += 1

注销一个对象ID，我们删除对象ID和我们各自的字典 ,deregister注销对象的方法

        def deregister(self, objectID):
            del self.objects[objectID]
            del self.disappeared[objectID]

update方法可以使用多种对象检测器比如Haar级联，HOG +线性SVM，SSD，Faster R-CNN等。代码功能依次包括检查输入边框是否为矩形是空的、循环所有已存在的跟踪对象并标记它们一样消失了、如果我们已经达到最大连续数指定对象被标记为的帧失踪，注销它、返回早，因为没有质心或跟踪信息更新。

        def update(self, rects):
            if len(rects) == 0:
                for objectID in list(self.disappeared.keys()):
                    self.disappeared[objectID] += 1
                    if self.disappeared[objectID] > self.maxDisappeared:
                        self.deregister(objectID)
                return self.objects

始化NumPy数组以存储每个的质心：

            inputCentroids = np.zeros((len(rects), 2), dtype="int")
            for (i, (startX, startY, endX, endY)) in enumerate(rects):
                cX = int((startX + endX) / 2.0)
                cY = int((startY + endY) / 2.0)
                inputCentroids[i] = (cX, cY)

如果当前没有要跟踪的对象，我们将注册每个新对象，

     
            if len(self.objects) == 0:
                for i in range(0, len(inputCentroids)):
                    self.register(inputCentroids[i])

否则，我们需要根据质心位置更新任何现有的对象（x，y）坐标，以最小化它们之间的欧几里得距离，are正在跟踪对象，所以我们需要尝试将输入的质心与现有对象匹配重心，然后获取一组对象id和相应的质心，计算每一对对象之间的距离centroids和输入centroids，分别——我们的目标是将输入质心与现有质心匹配物体质心。为了执行这个匹配，我们必须(1)找到每一行的最小值，然后(2)排序行索引基于它们的最小值，以便行的最小值位于索引的*front*处列表，接下来，我们对列执行类似的处理找出每一列中最小的值，然后使用先前计算的行索引列表进行排序。

     
            else:
                objectIDs = list(self.objects.keys())
                objectCentroids = list(self.objects.values())
                D = dist.cdist(np.array(objectCentroids), inputCentroids)
                rows = D.min(axis=1).argsort()
                cols = D.argmin(axis=1)[rows]

根据距离来查看是否可以关联对象ID，在这段代码中为了确定我们是否需要更新、注册、或注销需要跟踪的对象我们已经检查过的行和列索引的，循环(行，列)索引的组合元组，如果我们已经检查了行或列值前面，忽略它。否则，获取当前行的对象ID，设置它的新质心，并重置消失的，表示我们已经检查了每一行和列索引。

     
                usedRows = set()
                usedCols = set()
                for (row, col) in zip(rows, cols):
                    if row in usedRows or col in usedCols:
                        continue
                    objectID = objectIDs[row]
                    self.objects[objectID] = inputCentroids[col]
                    self.disappeared[objectID] = 0
                    usedRows.add(row)
                    usedCols.add(col)

在我们的索引中可能有 使用的行 + 用过的颜色  我们尚未检查，计算我们还没有的行和列索引。

                unusedRows = set(range(0, D.shape[0])).difference(usedRows)
                unusedCols = set(range(0, D.shape[1])).difference(usedCols)

因此，我们必须确定尚未检查的质心索引，并将它们存储在两个新的列表中方便集中。

我们的最终检查将处理丢失的或可能已消失的所有对象，在对象质心的数量为的情况下等于或大于输入质心的数目我们需要检查这些对象是否有可能消失了。循环遍历未使用的行索引，获取对应行的对象ID
索引和增加消失的计数器，检查是否有连续的数字物体被标记为“消失”取消对象注册的权证。

            
                if D.shape[0] >= D.shape[1]:
                    for row in unusedRows:
                        objectID = objectIDs[row]
                        self.disappeared[objectID] += 1
                        if self.disappeared[objectID] > self.maxDisappeared:
                            self.deregister(objectID)

否则，输入质心的数量大于现有对象质心的数量，因此我们要注册和跟踪新对象，返回可跟踪对象的集合，我们循环 未使用的颜色索引，然后注册每个新质心。最后，我们将可跟踪对象的集合返回给调用方法。

质心跟踪器程序编写完成！