DeepSORT(目标跟踪算法)中的马氏距离详解(很详细)

2024-06-11 09:52

本文主要是介绍DeepSORT(目标跟踪算法)中的马氏距离详解(很详细),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

DeepSORT(目标跟踪算法)中的马氏距离详解(很详细)

flyfish

马氏距离的公式是由印度统计学家【普拉萨纳·钱德拉·马哈拉诺比斯(Prasanta Chandra Mahalanobis)】)(好长的名字,抄的)在1936年提出的。马氏距离是一种多维尺度上的距离度量,它考虑了各个维度之间的相关性,并且通过协方差矩阵对数据进行缩放,使得在计算不同数据点之间的距离时,可以考虑到各个维度的不同特性。可以直接拖到最后的一张图,看下马氏距离与欧式距离相比有什么优势

介绍

假设我们有两个点 x x x y y y ,并且我们有这些点的协方差矩阵 S S S。马氏距离的公式为:

D M ( x , y ) = ( x − y ) T S − 1 ( x − y ) D_M(x, y) = \sqrt{(x - y)^T S^{-1} (x - y)} DM(x,y)=(xy)TS1(xy)

下面是一个具体的例子:

假设点 x = [ 2 , 3 ] x = [2, 3] x=[2,3],点 y = [ 6 , 8 ] y = [6, 8] y=[6,8],协方差矩阵 S = [ 4 2 2 3 ] S = \begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix} S=[4223]

代码计算

  1. 计算 x − y x - y xy
  2. 计算协方差矩阵的逆矩阵 S − 1 S^{-1} S1
  3. 计算 ( x − y ) T S − 1 ( x − y ) (x - y)^T S^{-1} (x - y) (xy)TS1(xy)
  4. 最后取平方根得到马氏距离
    让我们用Python代码验证这个计算过程。

代码

import numpy as np# 定义点 x 和 y
x = np.array([2, 3])
y = np.array([6, 8])# 定义协方差矩阵 S
S = np.array([[4, 2],[2, 3]])# 计算 x - y
delta = x - y# 计算协方差矩阵的逆矩阵 S^{-1}
S_inv = np.linalg.inv(S)# 计算马氏距离
mahalanobis_distance = np.sqrt(np.dot(np.dot(delta.T, S_inv), delta))print(mahalanobis_distance)

我们来执行这个代码,看看结果。

2.9154759474226504

计算结果显示,点 x x x y y y 之间的马氏距离为 2.915。

手工计算马氏距离

  1. 计算 x − y x - y xy
  2. 计算协方差矩阵的逆矩阵 S − 1 S^{-1} S1
  3. 计算 ( x − y ) T S − 1 ( x − y ) (x - y)^T S^{-1} (x - y) (xy)TS1(xy)
  4. 最后取平方根得到马氏距离
    给定点 x = [ 2 , 3 ] x = [2, 3] x=[2,3] y = [ 6 , 8 ] y = [6, 8] y=[6,8],以及协方差矩阵 S = [ 4 2 2 3 ] S = \begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix} S=[4223]
步骤 1: 计算 x − y x - y xy

δ = x − y = [ 2 , 3 ] − [ 6 , 8 ] = [ − 4 , − 5 ] \delta = x - y = [2, 3] - [6, 8] = [-4, -5] δ=xy=[2,3][6,8]=[4,5]

步骤 2: 计算协方差矩阵的逆矩阵 S − 1 S^{-1} S1

计算 S S S 的行列式:
det ⁡ ( S ) = 4 ⋅ 3 − 2 ⋅ 2 = 12 − 4 = 8 \det(S) = 4 \cdot 3 - 2 \cdot 2 = 12 - 4 = 8 det(S)=4322=124=8

计算伴随矩阵:
adj ( S ) = [ 3 − 2 − 2 4 ] \text{adj}(S) = \begin{bmatrix} 3 & -2 \\ -2 & 4 \end{bmatrix} adj(S)=[3224]

计算逆矩阵:
S − 1 = 1 8 ⋅ adj ( S ) = 1 8 ⋅ [ 3 − 2 − 2 4 ] = [ 0.375 − 0.25 − 0.25 0.5 ] S^{-1} = \frac{1}{8} \cdot \text{adj}(S) = \frac{1}{8} \cdot \begin{bmatrix} 3 & -2 \\ -2 & 4 \end{bmatrix} = \begin{bmatrix} 0.375 & -0.25 \\ -0.25 & 0.5 \end{bmatrix} S1=81adj(S)=81[3224]=[0.3750.250.250.5]

步骤 3: 计算 ( x − y ) T S − 1 ( x − y ) (x - y)^T S^{-1} (x - y) (xy)TS1(xy)

我们分步计算:

  1. 计算 S − 1 ⋅ δ T S^{-1} \cdot \delta^T S1δT
    S − 1 ⋅ δ T = [ 0.375 − 0.25 − 0.25 0.5 ] ⋅ [ − 4 , − 5 ] T S^{-1} \cdot \delta^T = \begin{bmatrix} 0.375 & -0.25 \\ -0.25 & 0.5 \end{bmatrix} \cdot [-4, -5]^T S1δT=[0.3750.250.250.5][4,5]T
    我们先计算每个元素:
    0.375 ⋅ ( − 4 ) + ( − 0.25 ) ⋅ ( − 5 ) = − 1.5 + 1.25 = − 0.25 − 0.25 ⋅ ( − 4 ) + 0.5 ⋅ ( − 5 ) = 1 − 2.5 = − 1.5 \begin{align*} 0.375 \cdot (-4) + (-0.25) \cdot (-5) &= -1.5 + 1.25 = -0.25 \\ -0.25 \cdot (-4) + 0.5 \cdot (-5) &= 1 - 2.5 = -1.5 \\ \end{align*} 0.375(4)+(0.25)(5)0.25(4)+0.5(5)=1.5+1.25=0.25=12.5=1.5
    所以:
    S − 1 ⋅ δ T = [ − 0.25 , − 1.5 ] S^{-1} \cdot \delta^T = [-0.25, -1.5] S1δT=[0.25,1.5]

  2. 计算 δ ⋅ [ − 0.25 , − 1.5 ] T \delta \cdot [-0.25, -1.5]^T δ[0.25,1.5]T
    δ ⋅ [ − 0.25 , − 1.5 ] T = [ − 4 , − 5 ] ⋅ [ − 0.25 , − 1.5 ] T = ( − 4 ⋅ − 0.25 ) + ( − 5 ⋅ − 1.5 ) = 1 + 7.5 = 8.5 \delta \cdot [-0.25, -1.5]^T = [-4, -5] \cdot [-0.25, -1.5]^T = (-4 \cdot -0.25) + (-5 \cdot -1.5) = 1 + 7.5 = 8.5 δ[0.25,1.5]T=[4,5][0.25,1.5]T=(40.25)+(51.5)=1+7.5=8.5

步骤 4: 取平方根

8.5 ≈ 2.915 \sqrt{8.5} \approx 2.915 8.5 2.915

马氏距离的绘图

绘制两个点之间的欧氏距离和马氏距离来进行比较。假设我们使用之前定义的点 x = [ 2 , 3 ] x = [2, 3] x=[2,3] y = [ 6 , 8 ] y = [6, 8] y=[6,8],以及协方差矩阵 S S S

我们可以进行以下步骤:

  1. 计算欧氏距离。
  2. 计算马氏距离。
  3. 绘制这两个点在平面上的位置。
  4. 绘制欧氏距离和马氏距离的线段。
    以下是完整的Python代码来实现这些步骤,并进行绘图。
import numpy as np
import matplotlib.pyplot as plt# 定义点 x 和 y
x = np.array([2, 3])
y = np.array([6, 8])# 定义协方差矩阵 S
S = np.array([[4, 2],[2, 3]])# 计算欧氏距离
euclidean_distance = np.linalg.norm(x - y)# 计算马氏距离
delta = x - y
S_inv = np.linalg.inv(S)
mahalanobis_distance = np.sqrt(np.dot(np.dot(delta.T, S_inv), delta))# 绘图
plt.figure(figsize=(8, 8))
plt.scatter(*x, color='blue', label='Point x')
plt.scatter(*y, color='red', label='Point y')# 绘制欧氏距离
plt.plot([x[0], y[0]], [x[1], y[1]], 'k--', label=f'Euclidean Distance = {euclidean_distance:.2f}')# 为了绘制马氏距离的等高线,我们可以绘制马氏距离的椭圆
from matplotlib.patches import Ellipse# 计算椭圆的参数
eigvals, eigvecs = np.linalg.eigh(S)
angle = np.degrees(np.arctan2(*eigvecs[:,0][::-1]))width, height = 2 * np.sqrt(eigvals)ellipse = Ellipse(xy=x, width=width, height=height, angle=angle, edgecolor='purple', fc='None', lw=2, label=f'Mahalanobis Distance = {mahalanobis_distance:.2f}')
plt.gca().add_patch(ellipse)plt.xlabel('X-axis')
plt.ylabel('Y-axis')
plt.legend()
plt.title('Comparison of Euclidean and Mahalanobis Distances')
plt.grid(True)
plt.axis('equal')
plt.show()

在这里插入图片描述
欧氏距离和马氏距离的比较:

  • 蓝点代表点 x x x
  • 红点代表点 y y y
  • 虚线表示两点之间的欧氏距离,长度为 6.40。
  • 紫色椭圆表示马氏距离等高线,马氏距离为 2.92。

图中的椭圆反映了协方差矩阵 S S S 的影响,显示了在不同方向上的不同尺度,这使得马氏距离能更准确地反映点与点之间的关系。欧氏距离忽略了数据的相关性和尺度,而马氏距离考虑了这些因素,使其在一些应用场景中更有用。

协方差

import numpy as np# 定义数据样本
data = np.array([[2, 3],[6, 8],[3, 5]
])# 计算均值向量
mean_vector = np.mean(data, axis=0)# 计算协方差矩阵
cov_matrix = np.cov(data, rowvar=False)print(mean_vector, cov_matrix)
[3.66666667 5.33333333] [[4.33333333 5.16666667][5.16666667 6.33333333]]

手工计算详细步骤

给定数据样本:

样本1 = [ 2 , 3 ] \text{样本1} = [2, 3] 样本1=[2,3]
样本2 = [ 6 , 8 ] \text{样本2} = [6, 8] 样本2=[6,8]
样本3 = [ 3 , 5 ] \text{样本3} = [3, 5] 样本3=[3,5]

计算均值向量:

S i j = 1 n − 1 ∑ k = 1 n ( x k i − μ i ) ( x k j − μ j ) S_{ij} = \frac{1}{n-1} \sum_{k=1}^{n} (x_{ki} - \mu_i)(x_{kj} - \mu_j) Sij=n11k=1n(xkiμi)(xkjμj)
μ = [ 2 + 6 + 3 3 , 3 + 8 + 5 3 ] = [ 3.67 , 5.33 ] \mu = \left[ \frac{2+6+3}{3}, \frac{3+8+5}{3} \right] = [3.67, 5.33] μ=[32+6+3,33+8+5]=[3.67,5.33]

计算协方差矩阵
  1. 计算 S 11 S_{11} S11

S 11 = 1 n − 1 ∑ k = 1 n ( x k 1 − μ 1 ) 2 S_{11} = \frac{1}{n-1} \sum_{k=1}^{n} (x_{k1} - \mu_1)^2 S11=n11k=1n(xk1μ1)2S11

S 11 = 1 2 [ ( 2 − 3.67 ) 2 + ( 6 − 3.67 ) 2 + ( 3 − 3.67 ) 2 ] = 1 2 [ ( − 1.67 ) 2 + ( 2.33 ) 2 + ( − 0.67 ) 2 ] = 1 2 [ 2.79 + 5.43 + 0.45 ] = 8.67 2 = 4.33 \begin{aligned}S_{11} &= \frac{1}{2} \left[ (2 - 3.67)^2 + (6 - 3.67)^2 + (3 - 3.67)^2 \right] \\ &= \frac{1}{2} \left[ (-1.67)^2 + (2.33)^2 + (-0.67)^2 \right] \\ &= \frac{1}{2} \left[ 2.79 + 5.43 + 0.45 \right] \\ &= \frac{8.67}{2} = 4.33 \\ \end{aligned} S11=21[(23.67)2+(63.67)2+(33.67)2]=21[(1.67)2+(2.33)2+(0.67)2]=21[2.79+5.43+0.45]=28.67=4.33

  1. 计算 S 12 S_{12} S12

S 12 = 1 n − 1 ∑ k = 1 n ( x k 1 − μ 1 ) ( x k 2 − μ 2 ) S_{12} = \frac{1}{n-1} \sum_{k=1}^{n} (x_{k1} - \mu_1)(x_{k2} - \mu_2) S12=n11k=1n(xk1μ1)(xk2μ2)
S 12 = 1 2 [ ( 2 − 3.67 ) ( 3 − 5.33 ) + ( 6 − 3.67 ) ( 8 − 5.33 ) + ( 3 − 3.67 ) ( 5 − 5.33 ) ] = 1 2 [ ( − 1.67 ) ( − 2.33 ) + ( 2.33 ) ( 2.67 ) + ( − 0.67 ) ( − 0.33 ) ] = 1 2 [ 3.89 + 6.22 + 0.22 ] = 10.33 2 = 5.17 \begin{aligned} S_{12} &= \frac{1}{2} \left[ (2 - 3.67)(3 - 5.33) + (6 - 3.67)(8 - 5.33) + (3 - 3.67)(5 - 5.33) \right] \\ &= \frac{1}{2} \left[ (-1.67)(-2.33) + (2.33)(2.67) + (-0.67)(-0.33) \right] \\ &= \frac{1}{2} \left[ 3.89 + 6.22 + 0.22 \right] \\ &= \frac{10.33}{2} = 5.17 \\ \end{aligned} S12=21[(23.67)(35.33)+(63.67)(85.33)+(33.67)(55.33)]=21[(1.67)(2.33)+(2.33)(2.67)+(0.67)(0.33)]=21[3.89+6.22+0.22]=210.33=5.17
4. 计算 S 22 S_{22} S22
S 22 = 1 n − 1 ∑ k = 1 n ( x k 2 − μ 2 ) 2 S_{22} = \frac{1}{n-1} \sum_{k=1}^{n} (x_{k2} - \mu_2)^2 S22=n11k=1n(xk2μ2)2
S 22 = 1 2 [ ( 3 − 5.33 ) 2 + ( 8 − 5.33 ) 2 + ( 5 − 5.33 ) 2 ] = 1 2 [ ( − 2.33 ) 2 + ( 2.67 ) 2 + ( − 0.33 ) 2 ] = 1 2 [ 5.43 + 7.11 + 0.11 ] = 12.65 2 = 6.33 \begin{aligned} S_{22} &= \frac{1}{2} \left[ (3 - 5.33)^2 + (8 - 5.33)^2 + (5 - 5.33)^2 \right] \\ &= \frac{1}{2} \left[ (-2.33)^2 + (2.67)^2 + (-0.33)^2 \right] \\ &= \frac{1}{2} \left[ 5.43 + 7.11 + 0.11 \right] \\ &= \frac{12.65}{2} = 6.33 \\ \end{aligned} S22=21[(35.33)2+(85.33)2+(55.33)2]=21[(2.33)2+(2.67)2+(0.33)2]=21[5.43+7.11+0.11]=212.65=6.33

协方差矩阵

S = [ 4.33 5.17 5.17 6.33 ] S = \begin{bmatrix} 4.33 & 5.17 \\ 5.17 & 6.33 \end{bmatrix} S=[4.335.175.176.33]

协方差矩阵对称性的解释

协方差矩阵的对称性来源于协方差的定义。对于随机变量 X X X Y Y Y,协方差定义为:

Cov ( X , Y ) = 1 n − 1 ∑ i = 1 n ( X i − μ X ) ( Y i − μ Y ) \text{Cov}(X, Y) = \frac{1}{n-1} \sum_{i=1}^{n} (X_i - \mu_X)(Y_i - \mu_Y) Cov(X,Y)=n11i=1n(XiμX)(YiμY)

由于协方差的计算中 ( X i − μ X ) (X_i - \mu_X) (XiμX) ( Y i − μ Y ) (Y_i - \mu_Y) (YiμY) 可以互换位置,所以协方差矩阵的 i , j i,j i,j 元素等于 j , i j,i j,i 元素,即 Cov ( X , Y ) = Cov ( Y , X ) \text{Cov}(X, Y) = \text{Cov}(Y, X) Cov(X,Y)=Cov(Y,X)。因此协方差矩阵是对称矩阵。

协方差矩阵是对称的。这意味着 S i j S_{ij} Sij 等于 S j i S_{ji} Sji。矩阵中的元素 5.17 5.17 5.17 是重复的。

马氏距离公式的推导

马氏距离 D M D_M DM 的公式如下:

D M = ( x − y ) T S − 1 ( x − y ) D_M = \sqrt{(x - y)^T S^{-1} (x - y)} DM=(xy)TS1(xy)

其中:

  • x x x y y y 是两个 d d d 维向量,表示两个数据点。
  • S S S 是数据的协方差矩阵。
  • S − 1 S^{-1} S1 是协方差矩阵 S S S 的逆矩阵。
  • ( x − y ) T (x - y)^T (xy)T x − y x - y xy 的转置向量。

推导过程

  1. 欧氏距离的局限性:在多维数据中,直接使用欧氏距离来度量两个点之间的距离,会忽略各个维度之间的相关性和尺度差异。欧氏距离公式为:
    D E = ( x − y ) T ( x − y ) D_E = \sqrt{(x - y)^T (x - y)} DE=(xy)T(xy)
  2. 标准化:为了克服欧氏距离的局限性,我们需要对数据进行标准化。对于一个维度上的数据,可以用均值和标准差来标准化,得到标准化后的数据:
    z = x − μ σ z = \frac{x - \mu}{\sigma} z=σxμ
  3. 考虑相关性:在多维数据中,不同维度之间可能存在相关性。协方差矩阵 S S S 反映了这种相关性。为了同时考虑尺度和相关性,我们可以对数据点进行变换,使得变换后的数据具有单位方差和零协方差。
  4. 变换数据:为了进行这种变换,我们需要使用协方差矩阵的逆矩阵 S − 1 S^{-1} S1 来对数据进行缩放。变换后的数据点为:
    z = S − 1 / 2 ( x − y ) z = S^{-1/2} (x - y) z=S1/2(xy)
    其中 S − 1 / 2 S^{-1/2} S1/2 是协方差矩阵的逆矩阵的平方根。
  5. 计算距离:变换后的数据点 z z z 在单位方差和零协方差的情况下,可以直接使用欧氏距离来度量:
    D M = z T z = ( x − y ) T S − 1 ( x − y ) D_M = \sqrt{z^T z} = \sqrt{(x - y)^T S^{-1} (x - y)} DM=zTz =(xy)TS1(xy)

上面已经计算的过程再走一遍(温习,下面的可不看)

假设我们有两个数据点 x = [ 2 , 3 ] x = [2, 3] x=[2,3] y = [ 6 , 8 ] y = [6, 8] y=[6,8],协方差矩阵 S = [ 4 2 2 3 ] S = \begin{bmatrix} 4 & 2 \\ 2 & 3 \end{bmatrix} S=[4223],我们可以计算马氏距离如下:

  1. 计算 x − y x - y xy
    δ = x − y = [ 2 , 3 ] − [ 6 , 8 ] = [ − 4 , − 5 ] \delta = x - y = [2, 3] - [6, 8] = [-4, -5] δ=xy=[2,3][6,8]=[4,5]
  2. 计算协方差矩阵的逆矩阵 S − 1 S^{-1} S1
    S − 1 = [ 0.6 − 0.4 − 0.4 0.8 ] S^{-1} = \begin{bmatrix} 0.6 & -0.4 \\ -0.4 & 0.8 \end{bmatrix} S1=[0.60.40.40.8]
  3. 计算 ( x − y ) T S − 1 ( x − y ) (x - y)^T S^{-1} (x - y) (xy)TS1(xy)
    δ T S − 1 δ = [ − 4 , − 5 ] [ 0.6 − 0.4 − 0.4 0.8 ] [ − 4 − 5 ] = [ 4.4 + 2 , 2 + 8 ] \delta^T S^{-1} \delta = [-4, -5] \begin{bmatrix} 0.6 & -0.4 \\ -0.4 & 0.8 \end{bmatrix} \begin{bmatrix} -4 \\ -5 \end{bmatrix} = [4.4 + 2, 2 + 8] δTS1δ=[4,5][0.60.40.40.8][45]=[4.4+2,2+8]
    = [ − 4 − 5 ] [ − 0.8 − 1.5 ] = 3.2 + 7.5 = 8.5 = \begin{bmatrix} -4 & -5 \end{bmatrix} \begin{bmatrix} -0.8 \\ -1.5 \end{bmatrix} = 3.2 + 7.5 = 8.5 =[45][0.81.5]=3.2+7.5=8.5
  4. 最后取平方根:
    D M = 8.5 ≈ 2.915 D_M = \sqrt{8.5} \approx 2.915 DM=8.5 2.915
    通过这种方式,我们可以考虑各个维度之间的相关性和不同的尺度,得到更准确的点与点之间的距离度量。

这篇关于DeepSORT(目标跟踪算法)中的马氏距离详解(很详细)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1050839

相关文章

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

OpenHarmony鸿蒙开发( Beta5.0)无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息,即可快速实现设备配网,是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递,利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力,实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后,即可发送相关配网数据。同时还支持与常规Sof

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

烟火目标检测数据集 7800张 烟火检测 带标注 voc yolo

一个包含7800张带标注图像的数据集,专门用于烟火目标检测,是一个非常有价值的资源,尤其对于那些致力于公共安全、事件管理和烟花表演监控等领域的人士而言。下面是对此数据集的一个详细介绍: 数据集名称:烟火目标检测数据集 数据集规模: 图片数量:7800张类别:主要包含烟火类目标,可能还包括其他相关类别,如烟火发射装置、背景等。格式:图像文件通常为JPEG或PNG格式;标注文件可能为X

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费