深度学习常用代码总结(k-means, NMS)

发布时间:2024年01月22日

目录

一、k-means 算法

二、NMS

1. NMS

2. soft-NMS

3. softer-NMS


一、k-means 算法

k-means 是一种无监督聚类算法,常用的聚类算法还有 DBSCAN。k-means 由于其原理简单,可解释强,实现方便,收敛速度快,在数据挖掘、数据分析、异常检测、模式识别、金融风控、数据科学、智能营销和数据运营等领域有着广泛的应用。具体实现步骤为:

  • 设定 K 个类别的中心的初值;
  • 计算每个样本到 K个中心的距离,按最近距离进行分类;
  • 以每个类别中样本的均值,更新该类别的中心;
  • 重复迭代以上步骤,直到达到终止条件(迭代次数、最小平方误差、簇中心点变化率)。

k-means 算法可以通过纯原生 python 语法实现,也可以通过 numpy 科学数据包实现。

纯原生 python 语法实现:

# 定义 List 求距离的函数
def getDistance(point1, point2, dim):
    sum = 0
    for i in range(dim):
        sum += (point1[i]-point2[i])**2
    return pow(sum, 0.5)

# 定义 List 求和的函数,引用调用
def getSum(point1, point2, dim):
    for i in range(dim):
        point1[i] += point2[i]

# 定义 List 求除法的函数,引用调用
def getDiv(point1, v, dim):
    for i in range(dim):
        point1[i] /= v

# 定义 List 深拷贝的函数
def deepCopy(det1, det2):
    m, n = len(det1), len(det1[0])
    for i in range(m):
        for j in range(n):
            det1[i][j] = det2[i][j]

# 定义主函数
def kmeans(dets, k, n):

    nums, dim = len(dets), len(dets[0])
    # 初始化旧的聚类中心,默认前k
    center_old = []
    for i in range(k):
        center_old.append(dets[i][:])  # [:]是浅拷贝 == copy()
    # 初始化新的聚类中心
    center_new = []
    for i in range(k):
        center_new.append([0]*dim)
    # 初始化一个记录的 List
    center_num = [0]*dim

    # 迭代 n 次
    for _ in range(n):
        for i in range(nums):
            min_dis = 1e10
            min_idx = 0
            for j in range(k):  # 基于最新距离找到第 i 数据的新的类别归属
                dis = getDistance(dets[i], center_old[j], dim)
                if min_dis > dis:
                    min_dis = dis
                    min_idx = j
            getSum(center_new[min_idx], dets[i], dim)  # 在新的类别归属上累计求和
            center_num[min_idx] += 1                   # 记录数量,以求均值

        for i in range(k):                             # 求取均值,获得新的聚类中心
            getDiv(center_new[i], center_num[i], dim)

        deepCopy(center_old, center_new)               # 将新的聚类中心赋值给旧的聚类中心
    
        for i in range(k):                             # 清空新的聚类中心
            for j in range(dim):
                center_new[i][j] = 0
            center_num[i] = 0

    return center_old

if __name__ == "__main__":
    x = [[1, 2], [1.5, 1.8], [5, 8], [8, 8], [1, 0.6], [9, 11]]
    y = kmeans(x, 2, 50)
    print(y)         # 结果为:[[1.1667, 1.4666], [7.3333, 9.0]]

numpy 科学数据包实现:参考

class Kmeans:
    def __init__(self, k=2, tolerance=0.01, max_iter=300):
        self.k = k
        self.tol = tolerance
        self.max_iter = max_iter
        self.features_count = -1
        self.classifications = None
        self.centroids = None

    def fit(self, data):
        """
        :param data: numpy数组,约定shape为:(数据数量,数据维度)
        :type data: numpy.ndarray
        """
        self.features_count = data.shape[1]
        # 初始化聚类中心(维度:k个 * features种数)
        self.centroids = np.zeros([self.k, data.shape[1]])
        for i in range(self.k):
            self.centroids[i] = data[i]

        for i in range(self.max_iter):
            # 清空聚类列表
            self.classifications = [[] for i in range(self.k)]
            # 对每个点与聚类中心进行距离计算
            for feature_set in data:
                # 预测分类
                classification = self.predict(feature_set)
                # 加入类别
                self.classifications[classification].append(feature_set)

            # 记录前一次的结果
            prev_centroids = np.ndarray.copy(self.centroids)

            # 更新中心
            for classification in range(self.k):
                self.centroids[classification] = np.average(self.classifications[classification], axis=0)

            # 检测相邻两次中心的变化情况
            for c in range(self.k):
                if np.linalg.norm(prev_centroids[c] - self.centroids[c]) > self.tol:
                    break

            # 如果都满足条件(上面循环没break),则返回
            else:
                return

    def predict(self, data):
        # 距离
        distances = np.linalg.norm(data - self.centroids, axis=1)
        # 最小距离索引
        return distances.argmin()

二、NMS

1. NMS

非极大值抑制 (Non-maximum supression) 简称 NMS,其作用是去除冗余的检测框,去冗余手段是剔除与极大值重叠较多的检测框结果。 通常我们所说的 NMS 指的是标准 NMS,非标准的 NMS 还有 soft NMS 和 softer NMS 参考?参考。那么为什么一定要去冗余呢?因为图像中的目标是多种多样的形状、大小和长宽比,目标检测算法中为了更好的保障目标的召回率,通常会使用 SelectiveSearch、RPN (例如:Faster-RCNN)、Anchor (例如:YOLO) 等方式生成长宽不同、数量较多的候选边界框 (BBOX)。因此在算法预测生成这些边界框后,紧接着需要跟着一个 NMS 后处理算法,进行去冗余操作,为每一个目标输出相对最佳的边界框,依次作为该目标最终检测结果。默认的两个框相似度的评判工具是 IOU,其它常用的还有 GIOU、DIOU、CIOU、EIOU 参考参考

一般NMS后处理算法需要经历以下步骤(不含背景类,背景类无需NMS):

step1:先将所有的边界框按照类别进行区分;

step2:把每个类别中的边界框,按照置信度从高到低进行降序排列;

step3:选择某类别所有边界框中置信度最高的边界框bbox1,然后从该类别的所有边界框列表中将该置信度最高的边界框bbox1移除并同时添加到输出列表中;

step4:依次计算该bbox1和该类别边界框列表中剩余的bbox计算IOU;

step5:将IOU与NMS预设阈值Thre进行比较,若某bbox与bbox1的IOU大于Thre,即视为bbox1的“邻域”,则在该类别边界框列表中移除该bbox,即去除冗余边界框;

step6:重复step3~step5,直至该类别的所有边界框列表为空,此时即为完成了一个物体类别的遍历;

step7:重复step2~step6,依次完成所有物体类别的NMS后处理过程;

step8:输出列表即为想要输出的检测框,NMS流程结束。

import numpy as np

def IOU(point, points):
    # 计算交集面积
    lu = np.maximum(point[0:2], points[:, 0:2])
    rd = np.minimum(point[2:4], points[:, 2:4])
    intersection = np.maximum(0, rd-lu)
    inter_area = intersection[:,0]*intersection[:,1]
    # 计算每个框的单独面积
    area1 = (point[2]-point[0])*(point[3]-point[1])
    area2 = (points[:,2]-points[:,0])*(points[:,3]-points[:,1])
    union_area = np.maximum(area1+area2-inter_area, 1e-10)
    # 计算交并比
    return inter_area/union_area

def nms(dets, thresh):
    points = dets[:,:4]
    score = dets[:,4]
    order = score.argsort()[::-1]
    keep = []
    while order.size > 0:
        i = order[0]
        keep.append(i)
        ious = IOU(points[i,:], points[order[1:]])  # 当order.size==1时,order[1]会报错,但order[1:]不会报错
        inds = np.where(ious<=thresh)[0]            # 对于IOU函数,order[1:]不会报错,但np.array([])则会报错
        order = order[inds+1]                       # 定义函数时,不需要特殊处理,numpy会自动帮忙处理这种情况
    
    return keep


if __name__ == "__main__":
    dets = np.array([
        [30, 10, 200, 200, 0.95],
        [25, 15, 180, 220, 0.98],
        [35, 40, 190, 170, 0.96],
        [60, 60, 90, 90, 0.3],
        [20, 30, 40, 50, 0.1],
    ])
    print(nms(dets, 0.5))

2. soft-NMS

由于 NMS 直接删除所有 IOU 大于阈值的框,这种做法是粗暴的,有可能会漏检目标。因此,softe-nms 吸取了 NMS 的教训,在算法执行过程中不是简单的对 IOU 大于阈值的检测框删除,而是降低得分。soft-NMS 算法流程同 NMS 相同,但是对原置信度得分使用函数运算,目标是降低置信度得分。相比原 NMS 算法,只是将删除 IOU 过大框的操作修改为将 IOU 过大框的置信度降低。具体降低置信度的方法一般有两种,如下,分别是线性加权和高斯加权法。当所有 Box 都运算一遍后,将最终得分小于阈值的 Box 删除。

线性加权:

高斯加权:

import numpy as np

def soft_nms(boxes, thresh=0.3, sigma2=0.5, score_thresh=0.5, method=1):
    """
    :param boxes: 检测结果 n*5 前4列是x1y1x2y2, 第5列是置信度
    :param thresh: IOU阈值 
    :param sigma2: 高斯函数中用到的sigma
    :param score_thresh: 置信概率分数阈值
    :param method: soft-nms对应1或者2, 传统nms对应0
    :return: 最终保留的boxes的索引号
    """

    # 初始化参数
    N = boxes.shape[0]
    indexs = [i for i in range(N)]

    # 得到每个box的左上角和右下角坐标并得到每个box的面积
    x1 = boxes[:, 0]
    y1 = boxes[:, 1]
    x2 = boxes[:, 2]
    y2 = boxes[:, 3]
    areas = (y2-y1+1)*(x2-x1+1)

    # 得到每个box的得分
    scores = boxes[:, 4]

    # 用keep存放保留的数据的索引并完成初始化,用keep_scores存放保留的数据的得分,该得分是乘以系数降低后的分数
    # 其实keep保存了所有得分非0的数据和得分,所有得分非0数据调整了数据的优先级进行排序,优先级逐步降低,最后再通过阈值去除一部分数据
    keep = []
    keep_scores = []
    pos = np.argmax(scores, axis=0)
    pos_scores = np.max(scores, axis=0)
    keep.append(pos)
    keep_scores.append(pos_scores)

    # 处理N-1次
    for _ in range(N):
        # 通过index-keep找到所有未检查的数据
        b = list(set(indexs).difference(set(keep)))

        # 计算当前pos数据与所有未检查数据的IOU
        # 计算交集的左上角和右下角
        x11 = np.maximum(x1[pos], x1[b])
        y11 = np.maximum(y1[pos], y1[b])
        x22 = np.minimum(x2[pos], x2[b])
        y22 = np.minimum(y2[pos], y2[b])
        # 如果两个方框相交, x22-x11, y22-y11是正的, 如果两个方框不相交,x22-x11, y22-y11是负的,将不相交的w和h设为0
        w = np.maximum(0, x22-x11)
        h = np.maximum(0, y22-y11)
        # 计算重叠交集的面积
        overlaps = w*h
        # 计算IOU, IOU公式(交集/并集)
        ious = overlaps / (areas[pos] + areas[b] - overlaps)

        # IOU大于阈值的重新赋值分数,大于阈值被认为是重叠度过高
        weight = np.ones(ious.shape)
        # Three methods: 1.linear 2.gaussian 3.original NMS
        if method == 1:
            weight[ious>thresh] = weight[ious>thresh] - ious[ious>thresh]
        elif method == 2:
            weight[ious>thresh] = np.exp(-(ious[ious>thresh])**2/sigma2)
        else:
            weight[ious>thresh] = 0
        scores[b] = weight*scores[b]

        # 更新pos, pos_scores, keep, keep_scores
        b_scores = scores[b]
        if np.any(b_scores) == 0: # 如果全为0则不再继续循环
            break
        pos = b[np.argmax(b_scores, axis=0)]
        pos_scores = np.max(b_scores, axis=0)
        keep.append(pos)
        keep_scores.append(pos_scores)

    # score约束
    keep = np.array(keep)
    keep_scores = np.array(keep_scores)
    indx = keep[keep_scores>=score_thresh]

    return indx


if __name__ == "__main__":
    a = np.array([[191, 89, 413, 420, 0.80],      # 0
                  [281, 152, 573, 510, 0.99],     # 1
                  [446, 294, 614, 471, 0.65],     # 2
                  [50, 453, 183, 621, 0.98],      # 3
                  [109, 474, 209, 635, 0.78]])    # 4
    nms_result = soft_nms(a)
    print(a[nms_result])

3. softer-NMS

以上两种 NMS 算法都忽略了一个问题,就是 NMS 时用到的 score 仅仅是分类置信度得分,不能反映 Bounding Box 的定位精准度,既分类置信度和定位置信非正相关的。因此,?softer-NMS?改进了预测模型,原本预测模型输出为 4+1+nClass,其中 4 为 xywh,修改后的模型输出为 8+1+nClass,其中 8 为 x1_u、x1_std、y1_u、y1_std、x2_u、x2_std、y2_u、y2_std,这里用一个预测的高斯分布描述预测坐标的准确度。softer-NMS 的算法流程同 soft-NMS 相同。唯一的区别是在每次循环中,当排在首位的 Box 找到与其重叠度很高 (IOU 大于 thresh) 的一组 Box 后,除了基于 IOU 对这一组 Box 的 score 进行降低外,还需要基于这一组 Box 对排在首位的 Box 的坐标进行加权求平均,权重因子就是每个 Box 的坐标方差的倒数,需要注意的是修改 score 所用的 Box 集合是修改坐标所用 Box 集合的子集。在训练过程中,可以认为预测输出的 u 和 std 构成一个高斯分布,而真值 x 构成一个脉冲分布 (狄拉克 delta 分布),采用 KL 散度作为损失函数用于评价预测分布与真值分布之间的误差。

import numpy as np

def softer_nms(dets, confidence, thresh=0.6, score_thresh=0.7, sigma=0.5):
    """
    :param boxes: 检测结果 n*5 前4列是x1_u,y1_u,x2_u,y2_u, 第5列是置信度
    :param confidence: 检测结果 n*4 是x1_std,y1_std,x2_std,y2_std
    :param thresh: IOU阈值
    :param score_thresh: 置信概率分数阈值
    :param sigma: 高斯函数中用到的sigma
    :return: 最终保留的boxes
    """

    # 初始化参数
    N = dets.shape[0]

    # 构建一个N*N的矩阵,第i-j表示第i个box与第j个box之间的IOU
    # 获取每个box的左上角和右下角坐标,直接=号是引用,后面会对dets做改变,所以这里需要浅拷贝
    x1 = dets[:, 0].copy()
    y1 = dets[:, 1].copy()
    x2 = dets[:, 2].copy()
    y2 = dets[:, 3].copy()
    # 计算每个box的面积,用于IOU的计算
    areas = (x2-x1)*(y2-y1)
    # 预定义IOU矩阵
    ious = np.zeros((N,N))
    # 循环计算IOU,这里存在重复计算,其实可以优化一下!!!
    for i in range(N):
        # 计算交集坐标
        xx1 = np.maximum(x1[i], x1)
        yy1 = np.maximum(y1[i], y1)
        xx2 = np.minimum(x2[i], x2)
        yy2 = np.minimum(y2[i], y2)
        # 计算交集宽高
        w = np.maximum(0.0, xx2-xx1)
        h = np.maximum(0.0, yy2-yy1)
        # 计算交集面积
        inter = w*h
        # 计算IOU
        ious[i, :] = inter/(areas[i] + areas - inter)

    # 遍历循环N次,调整每个box的坐标(在IOU大于阈值的box中依照坐标方差加权求平均),以及按照优先级调整排序
    i = 0
    while i < N:

        # 找到i到n-1索引中的极大值索引,作为该轮循环中的待调整box,这里可以优化,如果最大值过小,就跳出循环!!!
        maxpos = dets[i:N, 4].argmax()
        maxpos += i
        # 对调第i和第maxpos的位置,让maxpos成为本轮循环的待调整box和最高优先级box,排位在最靠前位置,如此操作会比较耗时,可以优化为只对索引操作!!!
        dets[[maxpos, i]] = dets[[i, maxpos]]
        confidence[[maxpos, i]] = confidence[[i, maxpos]]
        areas[[maxpos, i]] = areas[[i, maxpos]]
        ious[[maxpos, i]] = ious[[i, maxpos]]
        ious[:,[maxpos, i]] = ious[:,[i, maxpos]]
        # 找到与待调整box的IOU大于阈值的box,利用这些box的坐标调整待调整box的坐标,1/confidence是加权参数
        ovr_bbox = np.where(ious[i,:N]>thresh)[0]
        avg_std_bbox = ((dets[ovr_bbox,:4] / confidence[ovr_bbox]).sum(0)) / ((1/confidence[ovr_bbox]).sum(0))
        dets[i, :4] = avg_std_bbox

        # 利用待调整box调整从i+1到N-1中与其重叠度过高的box的得分,与soft-nms一模一行,这里也可以优化为矩阵运算!!!
        pos = i + 1
        while pos < N:
            if ious[i , pos] > 0:
                # 得到IOU并利用高斯函数调整得分
                ovr =  ious[i, pos]
                dets[pos, 4] *= np.exp(-(ovr*ovr)/sigma)
                # 如果得分过低,可以将其移到最后,这里其实有点浪费,即使没有这部分代码,经过N-1个循环后,最小得分的也都是在最后,可以优化!!!
                if dets[pos, 4] < score_thresh:
                    dets[[pos, N-1]] = dets[[N-1, pos]]
                    confidence[[pos, N-1]] = confidence[[N-1, pos]]
                    areas[[pos, N-1]] = areas[[N-1, pos]]
                    ious[[pos, N-1]] = ious[[N-1, pos]]
                    ious[:,[pos, N-1]] = ious[:,[N-1, pos]]
                    N -= 1      # 减少循环的次数
                    pos -= 1
            pos += 1

        i += 1

    return dets[:N, :]


if __name__ == "__main__":
    a = np.array([[191, 89, 413, 420, 0.80],      # 0
                  [281, 152, 573, 510, 0.99],     # 1
                  [446, 294, 614, 471, 0.65],     # 2
                  [50, 453, 183, 621, 0.98],      # 3
                  [109, 474, 209, 635, 0.78]])    # 4
    b = np.array([[1, 1, 1, 1],      # 0
                  [1, 1, 1, 1],      # 1
                  [1, 1, 1, 1],      # 2
                  [1, 1, 1, 1],      # 3
                  [1, 1, 1, 1]])     # 4
    nms_result = softer_nms(a, b)
    print(nms_result)

文章来源:https://blog.csdn.net/BIT_Legend/article/details/135637468
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。