计算机视觉的几个经典算法 —— 最小二乘法 + RANSAC + 哈希算法（附DCT） + 图像聚类算法

计算机视觉的几个经典算法

目录

• • 计算机视觉的几个经典算法
  • 1. 最小二乘法（寻找线性回归函数）
  • 2. RANSAC（模型已知，参数未知）
  • • 2.1 RANSAC 与 最小二乘法的区别
    • 2.2 RANSAC算法的步骤
    • 2.3 RANSAC的参数确定
    • 2.4 RANSAC的应用
    • 2.5 RANSAC算法的优缺点
  • 3. 哈希算法
  • • 3.1 均值哈希算法与差值哈希算法
    • 3.2 离散余弦变换DCT与感知哈希算法
  • 4. 图像聚类算法K-Means
  • • 4.1 分类与聚类
    • 4.2 K-Means聚类

1. 最小二乘法（寻找线性回归函数）

在了解最小二乘法之前，我们有必要先说说线性回归，所谓线性回归我们最常见的例子y=2x这个一元线性回归方程中，斜率2就是回归系数，它表示的是x变动时，y与之对应的关系，而线性回归就是表示一些离散的点在总体上是最逼近某一条直线的

这跟最小二乘法有啥关系呢？其实最小二乘法（Least Square Method）是寻找线性回归函数的一个方法，它是通过最小化误差的平方和来求得的，那我们为什么使用残差平方和呢？因为它的拟合程度更高，也就是拟合函数与待求解函数的y之间的相似性更高

利用最小二乘法可以简便得求得未知的数据，并使得这些求得的数据与实际数据之间误差的平方和为最小

2. RANSAC（模型已知，参数未知）

RANSAC，即随机采样一致性，它不是一种方法或算法，它是一种思想，一个求解已知模型的参数的框架，它不限定某一特定的问题，可以是计算机视觉的问题，也可以是统计数学，甚至可以是经济学领域的模型参数的估计问题

它是一种迭代的方法，用来在一组包含离散的被观测数据中估算出数学模型的参数，它也是一种非确定性算法，它会产生一个在一定概率下合理的结果，其允许使用更多次的迭代来使其概率增加

RANSAC的基本假设是 “内群”数据可以通过几组模型参数来叙述其数据分布，而“离群”数据则是不适合模型化的数据。 数据会受噪声影响,噪声指的是离群，例如从极端的噪声或错误解释有关数据的测量或不正确的假设

RANSAC假定，给定一组（通常很小的）内群，存在一个程序，这个程序可以估算最佳解释或最适用于这一数据模型的参数

2.1 RANSAC 与 最小二乘法的区别

从上述的内容我们可以得知其实这两个东西都是用来做拟合的，但是他们之间又有什么关系、有什么区别、应用场景有什么不同呢？

在实际开发或生产实践中，数据都会有一定的偏差，当我们已知两个变量之间的关系是线性回归函数，Y=aX+b，如果我们想知道具体的a和b的值，理论上说我们只需要两个点就能满足需求，但是由于误差的存在，我们任意选取的两个点所求出的a和b可能都不相同，我们最想要的就是最后的理论模型与测试值的误差最小

• 最小二乘法：通过计算最小均方差关于a和b的偏导数为0时的值，在很多情况下最小二乘法就是线性回归的代名词，但是它只适用于误差较小的情况
• RANSAC：在模型已确定且最大迭代次数允许的情况下，RANSAC总是可以找到最优解（对于包含80%误差的数据集，RANSAC的效果远远好过最小二乘法）

综上所述我们可以片面地认为最小二乘法适用于误差小的情况，RANSAC使用与误差稍大且最大迭代次数允许的情况，在图像处理的实际开发中，由于一张图片的像素个数庞大，采用最小二乘法运算量巨大且计算速度很慢

2.2 RANSAC算法的步骤

RANSAC算法的输入数据：是一组观测数据，并且由于RANSAC的独特性，通常这些观测数据中会有较大的噪点和无效点，除了观测数据，RANSAC还需要一个已知的模型（理解为一个函数），还有一些可信的参数也很重要

在RANSAC算法的实现过程中，我们可以大致分为6个步骤：

1. 在输入数据中随机选择几个点设置为内群，也就是除噪点和无效点之外的有效点
2. 计算合适内群的模型，作为输入数据传入RANSAC算法中
3. 把其他的刚才没有选中的点传入建立的模型中，计算是否为内群
4. 把内群数量记录下来，并重复以上的步骤
5. 在每一次计算内群数量过程中选出内群数量最多的那一个，内群数量最多的那一次建立的模型就是我们需要的结果

在执行RANSAC算法的过程中，对于不同的数学模型，在计算参数模型时的方法也必定不同，故RANSAC不是为了找到计算模型参数，而是提供这样的一个思路

RANSAC最大的缺陷在于要求数学模型已知

在算法执行的过程中我们应该关注两个问题：1.开始时应该选择多少个点为内群；2.最大迭代次数是多少

2.3 RANSAC的参数确定

假设我们在第一步选取的点是内群的概率为w，而选取的个数为n，w^n是所选择的n个点都是内群的机率, 1-w^n 是所选择的n个点至少有一个不是内群的机率, (1 − wⁿ⁾k 是表示重复 k 次都没有全部的n个点都是内群的机率, 假设算法跑 k 次以后成功的机率是p，我们可以得到p的计算公式：p = 1 − (1 − w^n)k

再通过上述公式得到k的计算公式：K=log(1-P)/log(1-w^n)

通过这两个函数我们可以得知，如果我们希望建立的模型是最优解的几率高一点，当w确定时，k越大p就越大。当w不变时，n越大所需要的k就越大，然而通常来讲w是位置的，所以我们会把n选小一点

2.4 RANSAC的应用

RANSAC最典型的应用场景是全景拼接，它的实现过程大致分为4个步骤

1. 针对某个场景拍摄多张图像，这些图像一般成序列
2. 通过特征匹配（SIFT）计算下一张图片与上一张图片之间的变换结构
3. 图像映射，将下一张图片叠加到上一张图片的坐标系中
4. 将变换后的图像融合起来就得到了最后的全景图

2.5 RANSAC算法的优缺点

优点：其优点就是其功能咯，那就是可以找出最优的计算模型

缺点：由于其受限颇多，缺点也非常明显

• 它计算参数的迭代次数没有上限；如果设置迭代次数的上限，得到的结果可能不是最优的结果，甚至可能得到错误的结果
• RANSAC只有一定的概率得到可信的模型，概率与迭代次数成正比
• 它要求设置跟问题相关的阀值
• RANSAC只能从特定的数据集中估计出一个模型，如果存在两个（或多个）模型，RANSAC不能找到别的模型
• 要求数学模型已知

3. 哈希算法

Hash算法与RANSAC和最小二乘法没有关系，它是另一种算法，在我们计算机视觉领域它常用来做图像相似度比较，相似图像搜索的哈希算法有三种：均值哈希算法（aHash）、差值哈希算法（dHash）和感知哈希算法（pHash）

说到哈希算法就必须要说说散列函数了，它是一种从任何一种数据中创建小的数字”指纹”的方法，它把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来，该函数将数据打乱混合，重新创建一个叫做散列值的指纹，散列值常用一个短的随机字母和数字组成的字符串来表示

通过哈希算法得到的任意长度的二进制值映射为较短的固定长度的二进制值，即哈希值。此外，哈希值是一段数据唯一且极其紧凑的数值表示形式，如果通过哈希一段明文得到哈希值，哪怕只更改该段明文中的任意一个字母，随后得到的哈希值都将不同，哈希算法是一个函数，能够把几乎所有的数字文件都转换成一串由数字和字母构成的看似乱码的字符串

哈希函数作为一种加密函数，它有两个最重要的特点：

• 不可逆性，输入信息得出输出的那个看似乱码的字符串（哈希值）非常容易，但是从输出的字符串反推出输入的结果却是却非常非常难
• 输出值唯一性和不可预测性，只要输入的信息有一点点区别，那么根据哈希算法得出来的输出值也相差甚远

汉明距离

汉明距离是用来比较两个哈希值的接近程度的量，它代表的是两个数字对应二进制不同的位置的数目

3.1 均值哈希算法与差值哈希算法

均值哈希算法的过程分为6步：

1. 缩放：图片缩放为8*8，保留结构，除去细节
2. 灰度化：转换为灰度图
3. 求平均值：计算灰度图所有像素的平均值
4. 比较：像素值大于平均值记作1，相反记作0，总共64位
5. 生成hash：将上述步骤生成的1和0按顺序组合起来既是图片的指纹（hash）
6. 对比指纹：将两幅图的指纹对比，计算汉明距离，即两个64位的hash值有多少位是不一样的，不相同位数越少，图片越相似

差值哈希算法与均值哈希算法前期和后期的处理基本相同，只是在比较hash时有不同，差值哈希算法分为6步：

1. 缩放：图片缩放为8*9，保留结构，除去细节
2. 灰度化：转换为灰度图
3. 比较：像素值大于后一个像素值记作1，相反记作0。本行不与下一行对比，每行9个像素，八个差值，有8行，总共64位

#均值哈希算法
def aHash(img):
    #缩放为8*8
    img=cv2.resize(img,(8,8),interpolation=cv2.INTER_CUBIC)
    #转换为灰度图
    gray=cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
    #s为像素和初值为0，hash_str为hash值初值为''
    s=0
    hash_str=''
    #遍历累加求像素和
    for i in range(8):
        for j in range(8):
            s=s+gray[i,j]
    #求平均灰度
    avg=s/64
    #灰度大于平均值为1相反为0生成图片的hash值
    for i in range(8):
        for j in range(8):
            if  gray[i,j]>avg:
                hash_str=hash_str+'1'
            else:
                hash_str=hash_str+'0'           
    return hash_str
  
#差值感知算法
def dHash(img):
    #缩放8*9
    img=cv2.resize(img,(9,8),interpolation=cv2.INTER_CUBIC)
    #转换灰度图
    gray=cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
    hash_str=''
    #每行前一个像素大于后一个像素为1，相反为0，生成哈希
    for i in range(8):
        for j in range(8):
            if   gray[i,j]>gray[i,j+1]:
                hash_str=hash_str+'1'
            else:
                hash_str=hash_str+'0'
    return hash_str

3.2 离散余弦变换DCT与感知哈希算法

我们在上面说有3中哈希算法，但是只说了两种，第三种感知哈希算法关系到一个新的东西DCT，也就是离散余弦变换

均值哈希算法过于严格，不够精确，更适合搜索缩略图，为了获得更精确的结果可以选择感知哈希算法，它采用的是DCT（离散余弦变换）来降低频率的方法，感知哈希算法分为8步：

1. 缩小图片：32 * 32是一个较好的大小，这样方便DCT计算
2. 转化为灰度图：把缩放后的图片转化为灰度图。
3. 计算DCT:DCT把图片分离成分率的集合
4. 缩小DCT：DCT计算后的矩阵是32 * 32，保留左上角的8 * 8，这些代表图片的最低频率
5. 计算平均值：计算缩小DCT后的所有像素点的平均值
6. 进一步减小DCT：大于平均值记录为1，反之记录为0.
7. 得到信息指纹：组合64个信息位，顺序随意保持一致性
8. 最后比对两张图片的指纹，获得汉明距离即可

离散余弦变换(Discrete Cosine Transform)，主要用于将数据或图像的压缩，能够将空域的信号转换到频域上，具有良好的去相关性的性能，DCT变换本身是无损的，同时，由于DCT变换是对称的，所以，我们可以在量化编码后利用DCT反变换，在接收端恢复原始的图像信息，DCT变换在当前的图像分析以及压缩领域有着极为广大的用途，我们常见的JPEG静态图像编码以及MJPEG、MPEG动态编码等标准中都使用了DCT变换

这个东西我也没太懂，只能先为大家提供一点理论的东西了，以后有机会接触到会细说

4. 图像聚类算法K-Means 4.1 分类与聚类

分类

分类其实是从特定的数据中挖掘模式，作出判断的过程，分类学习的主要过程可以分为3步：

1. 训练数据集存在一个类标记号，判断它是正向数据集还是负向数据集
2. 然后需要对数据集进行学习训练，并构建一个训练的模型
3. 通过该模型对预测数据集进行预测，并计算其结果的性能

聚类

从广义上说，聚类就是将数据集中在某些方面相似的数据成员放在一起，一个聚类就是一些数据实例的集合，其中处于相同聚类中的数据元素彼此相似，但是处于不同聚类中的元素彼此不同

由于在聚类中那些表示数据类别的分类或分组信息是没有的，即这些数据是没有标签的，所以聚类通常被归为无监督学习（Unsupervised Learning），从这个角度来看，分类就类似于监督学习

聚类的目的也是把数据分类，但是事先是不知道如何去分的，完全是算法自己来判断各条数据之间的相似性，相似的就放在一起。在聚类的结论出来之前，完全不知道每一类有什么特点，一定要根据聚类的结果通过人的经验来分析，看看聚成的这一类大概有什么特点

总之，聚类主要是"物以类聚"，通过相似性把相似元素聚集在一起，它没有标签；而分类通过标签来训练得到一个模型，对新数据集进行预测的过程，其数据存在标签

4.2 K-Means聚类

K-Means聚类是最常用的聚类算法，最初起源于信号处理，其目标是将数据点划分为K个类簇，该算法的最大优点是简单、便于理解，运算速度较快，缺点是要在聚类前指定聚集的类簇数，该算法的最大优点是简单、便于理解，运算速度较快，缺点是要在聚类前指定聚集的类簇数

K-Means聚类算法的分析流程

第一步：确定K值，即将数据集分为K个类簇或小组

第二步：从数据集中随机选择K个数据点作为质心（Centroid）或数据中心

第三步：分别计算每个点到每个质心之间的距离，并将每个点划分到最近质心的小组

第四步：当每个质心都聚集了一些点后，重新定义算法选出新的质心（对于每个簇，计算其均值，即得到新的k个质心点）

第五步：迭代执行3、4步，知道迭代终止或满足迭代结束条件（聚类结果不再变化）

import cv2
import numpy as np
import matplotlib.pyplot as plt
 
#读取原始图像
img = cv2.imread('lenna.png') 
print (img.shape)
 
#图像二维像素转换为一维
data = img.reshape((-1,3))
data = np.float32(data)
 
#停止条件 (type,max_iter,epsilon)
criteria = (cv2.TERM_CRITERIA_EPS +
            cv2.TERM_CRITERIA_MAX_ITER, 10, 1.0)
 
#设置标签
flags = cv2.KMEANS_RANDOM_CENTERS
 
#K-Means聚类 聚集成2类
compactness, labels2, centers2 = cv2.kmeans(data, 2, None, criteria, 10, flags)
 
#K-Means聚类 聚集成4类
compactness, labels4, centers4 = cv2.kmeans(data, 4, None, criteria, 10, flags)
 
#K-Means聚类 聚集成8类
compactness, labels8, centers8 = cv2.kmeans(data, 8, None, criteria, 10, flags)
 
#K-Means聚类 聚集成16类
compactness, labels16, centers16 = cv2.kmeans(data, 16, None, criteria, 10, flags)
 
#K-Means聚类 聚集成64类
compactness, labels64, centers64 = cv2.kmeans(data, 64, None, criteria, 10, flags)
 
#图像转换回uint8二维类型
centers2 = np.uint8(centers2)
res = centers2[labels2.flatten()]
dst2 = res.reshape((img.shape))
 
centers4 = np.uint8(centers4)
res = centers4[labels4.flatten()]
dst4 = res.reshape((img.shape))
 
centers8 = np.uint8(centers8)
res = centers8[labels8.flatten()]
dst8 = res.reshape((img.shape))
 
centers16 = np.uint8(centers16)
res = centers16[labels16.flatten()]
dst16 = res.reshape((img.shape))
 
centers64 = np.uint8(centers64)
res = centers64[labels64.flatten()]
dst64 = res.reshape((img.shape))
 
#图像转换为RGB显示
img = cv2.cvtColor(img, cv2.COLOR_BGR2RGB)
dst2 = cv2.cvtColor(dst2, cv2.COLOR_BGR2RGB)
dst4 = cv2.cvtColor(dst4, cv2.COLOR_BGR2RGB)
dst8 = cv2.cvtColor(dst8, cv2.COLOR_BGR2RGB)
dst16 = cv2.cvtColor(dst16, cv2.COLOR_BGR2RGB)
dst64 = cv2.cvtColor(dst64, cv2.COLOR_BGR2RGB)
 
#用来正常显示中文标签
plt.rcParams['font.sans-serif']=['SimHei']
 
#显示图像
titles = [u'原始图像', u'聚类图像 K=2', u'聚类图像 K=4',
          u'聚类图像 K=8', u'聚类图像 K=16',  u'聚类图像 K=64']  
images = [img, dst2, dst4, dst8, dst16, dst64]  
for i in range(6):  
   plt.subplot(2,3,i+1), plt.imshow(images[i], 'gray'), 
   plt.title(titles[i])  
   plt.xticks([]),plt.yticks([])  
plt.show()

K-Means聚类与图像处理

在图像处理中国，通过K-Means聚类算法可以实现图像分割、图像聚类和图像识别等 *** 作，我们通过算法可以将这些像素点聚类成K个类簇，然后使用每个簇内的质心点来替换簇内所有的像素点，这样就能实现在不改变分辨率的情况下量化压缩图像颜色，实现图像颜色层级分割

K-Means聚类在图像处理的应用中，优点非常的明显，虽然效果不如我们神经网络那一块儿的方法，但是在一般情况下也是够用，而且简单迅速，对应处理大数据集算法效率很高，而当结果簇是密集的时候其效果也是非常理想的

其缺点一个是刚才说过的必须指定类簇数K，另一个是对噪声和孤立点数据敏感，在一般的问题处理时这些缺陷都可以用其他的方法来弥补

---

版权声明：以上学习内容及配图来自或参考自——八斗人工智能 王小天
如果文章对您有所帮助，记得一键三连支持一下哦~