按照课本（讲义）顺序的一个复（yu）习纲要，也参考了PPT。
图像特征提取
问题
- 通用 的视觉特征和 领域相关 的视觉特征
- 前者主要包括色彩、纹理和形状；后者与应用相关，如人脸特征、指纹特征等
- 因此， 视觉特征选取 非常重要
步骤
- Extraction：特征提取
- Representation：特征表达
- Discrimination：区别性特征选择
- Indexing/Hashing：特征索引
挑战
- 复杂度
- 特征不变性：尺度无关、变换无关等
- 特征的本征结构
- 特征距离度量算子（Distance Metric）
图像颜色特征
- 对图像尺寸、方向、视角的依赖性较小，鲁棒性好
- 多种颜色空间，灰度、RGB、HSV等
- 需要 量化方法 和 距离标准
颜色直方图
特点
- 要归一化到[0,1]空间
- 优点：给出了像素点在图中的统计信息
- 缺点：和空间位置无关，无法描述物体
计算
- 颜色量化：将颜色空间划分成若干个小的颜色区间，每个小区间成为直方图的一个bin
- 计算落在每个小区的像素数量，即可得到直方图
用处
- 计算图像之间的相似度
- 图像均衡
- 图像切分
图像均衡化/直方图归一化
思想：直方图中的值/所有像素点的值加起来为1。
处理方法：
- 先计算频数，然后计算每个灰度值的累计分布次数（即小于等于此灰度值的点出现的次数）
- 每个点的灰度值=round(当前点累计分布次数cdf(v) - 最小累计分布次数cdfmin) / (像素总数M * N - cdfmin) * (灰度区间长度L-1)
- 重新绘制直方图，即为均衡后的直方图
结果
累计直方图接近正比例函数
从聚类和量化角度看
颜色直方图中的Bins就是将颜色空间划分成若干个小的颜色空间，可视为 颜色量化
颜色矩
特点
- 图像中任何颜色分布都可以用它的矩来表示
- 颜色分布信息主要集中在低阶矩中，因此仅采用一阶矩（mean）、二阶矩（variance）和三阶矩（skewness）就可以表达图像的颜色分布
- 与颜色直方图相比，这种方法无需对特征进行向量化
计算方式
- 一阶矩 µ = 1/Ν * Σx 即所有像素均值
- 二阶矩 σ = ( 1/Ν * Σ(x-µ)^2 )^1/2 即方差开根号
- 三阶矩 s = ( 1/Ν * Σ(x-µ)^3 )^1/3
- 彩色图像，RGB3个颜色分量，每个颜色分量求3个低阶矩，一共9个值
颜色集
这个ppt里都没有是不是一定不会考啊
大概思路就是先把RGB转化成HSV，并把颜色空间向量化成若干个Bin。
然后用色彩自动分割技术把图像划分为若干区域，每个区域用量化颜色空间的某个颜色分量来索引，从而得到一个二进制的颜色索引集。
匹配的时候比较不同图像颜色集之间的距离和色彩域的空间关系，包裹分离、包含、交等操作。
因为表达为二进制的特征向量，所以可以构造二分查找树，适用于大规模图像。
RGB转HSV
v = max(r, g, b)
s = [v - min(r, g, b)] / v
h =
5 + b’ if r=max(rgb) and g=min(rgb)
1 - g’ if r=max(rgb) and g!=min(rgb)
1 + r’ if g=max(rgb) and b=min(rgb)
3 - b’ if g=max(rgb) and b!=min(rgb)
3 + g’ if b=max(rgb) and r=min(rgb)
5 - r’ otherwise
r’ = [v - r] / [v-min(r, g, b)]
g’ = [v - g] / [v-min(r, g, b)]
b’ = [v - b] / [v-min(r, g, b)]
颜色聚合向量（看上去很像重点）
核心思想
将属于同一色度的像素点分为两部分：如果同属同一颜色值的某些像素点所占连续区域面积大于给定阈值，则该区域内像素点作为聚合像素，否则作为非聚合像素。
步骤
- 平均化，用每个像素点周围8个像素的均值代替此点。然后将每个灰度点的值离散化，使图像中只有L种不同灰度，也即L个Bins。
- 对于每个灰度值，将像素点值等于它的所有像素点分类为连贯和不连贯两部分。
- 把灰度值相同的所有像素点以及他们之间的距离看成一张无向加权图，通过最小生成树（MST）算法分别得到 某个灰度值 的联通像素点数目和非联通像素点数目。
- Dn={di} (1<=i<=K) 表示灰度值为n的所有像素点组成的集合，也即灰度值为n的像素数目为K。定义无向加权图G(Dn)=(V,E)，其中V表示所有点集，E表示所有边集。图G(Dn)的生成树T(Dn)=(V,E’)被定义为G(Dn)的一棵子树，T(Dn)满足：包含了G(Dn)的所有定点，且T(Dn)中不会有环路出现
- G(Dn)中每条边ρ(di,dj)的权值就是di和dj两点之间的几何距离。则无向加权图G(Dn)的最小生成树就是使所有边加权和最小的生成树
- 最小生成树要求：任意增加一条边则会产生回路，且任意去掉一条边则会变成非联通图。使用贪婪算法来生成：先取任意一个点为起点；之后选所有点中离当前点最近的、且未被联通的点，和当前点相连；之后每一步都选择到现在树上任意一点距离最近的点，将这个点和这条最短的边添加到树上；直到所有点都被添加
- 得到最小生成树后，如果任意一条边的距离大于 τ = sqrt(M * N) * 5%，则将这条边去除。这样，图像就分成了联通点和非联通点。对于所有灰度值，重复上述计算。
用法
两个图像之间的距离 ΔCCV = Σ( |αj-α’j| + |βj-β’j| )
两个直方图之间的距离 ΔCΗ = Σ| (αj + βj) - (α’j + β’j) |
可以减少对直方图相同而实际不同的图像的误识别
得到的α就是一幅图中所有连续区域内的像素的点的数目之和，β是所有不连续的像素点的数目之和（对同一个灰度值j）
颜色相关图
不但刻画了某一种颜色的像素数量占整个图像的比例，还反映了具有两种颜色的像素点之间的空间相关性。
方法
- 给定距离k
- 对于任意一个像素点P1，如果其灰度值为C(i)，计算存在下述像素点的概率是多少：
与之相距k，灰度值为C(j)的像素点 - 一般而言，将这样配对出现像素点的数目作为概率值，如果没有这样的匹配对，则置为0.或者采取归一化方法，计算概率值
- 如果灰度值为d，则得到一个d * d大小的矩阵
结果
- 矩阵第L行和第M列值，表示色彩值L和色彩值为M、距离为k配对像素点一共出现的次数
- 颜色相关图一定程度上考虑了像素点色度值和空间信息
- 如果考虑到任何颜色之间的相关性，颜色相关图会变得非常复杂和庞大（空间复杂度为O(n^2d)）
图像相似度比较方法
常用的图像相似度的比较方法都是基于向量空间模型，即将图像特征看做是向量空间中的点，通过计算两个点之间的接近程度来衡量图像特征间的相似度。
- 后期会学到降维
- 这里不考虑特征向量之间的相关性
欧拉距离
- L1范式距离：D(H1, H2) = Σ| h(1,i) - h(2,i) |
- L2范式距离：D(H1, H2) = sqrt( Σ(h(1,i) -h(2,i))^2 ) （即欧式距离）
直方图交
- 直方图的交：D(H1, H2) = 1 - Σmin( h(1,i), h(2,i) ) / min( Σh(1,i), Σh(2,i) )
如果两幅图完全一样，直方图的交的距离为0；如果两幅图在直方图意义上视觉差距很大，则接近1。
直方图的交是直方图相似度计算的最佳算子。
二次式距离
这个PPT里也没有啊
用途
然而二次式距离再许多方面已经被证明比欧拉距离或者直方图相交距离更有效。喂PPT上不是这样说的啊
因为这种距离考虑到了不同颜色之间存在的相似度。
公式
两个颜色直方图I和Q之间的二次式距离可以表示为：
D = ( Q - I )^t A( Q - I )
引入颜色相似性矩阵A = [aij]，表示直方图中下表为i和j的两个颜色bin之间的相似度。可以通过色彩心理学研究获得。
或者可以先对颜色直方图求闭包操作，使得每个颜色bin的值都受到来自他相邻颜色bin的影响。这样，颜色直方图本身就包含了不同颜色之间的相似性因素，因此可以直接使用欧拉距离或直方图相交距离。
这种预处理的好处是检索过程中计算相似度的代价较小。
马氏距离
另外一个PPT里没有的
用途
用于特征向量的各个分量间具有相关性或者具有不同的权重。
公式
Dmahal = ( A - B )^t C^-1 ( A - B )
其中C是特征向量的协方差矩阵。
简化
特征向量的各分量之间没有相关性的时候，只需要计算每个分量的方差ci，因此可以简化为：
Ds = Σ( (Ai-Bi)^2 / ci )
Hausdorff距离（看上去很像重点）
用途
用于计算维数不一样的向量之间的相似度。
公式
假设向量A，B的维度分别为m,n：
H(A,B) = max( h(A,B), h(B,A) )
h(A,B) = max_a∈A min_b∈B D(a,b)
D(a,b)表示A，B中任意两个分量之间的距离，根据实际情况定义
H(A,B)表示：任意属于A的分量，在B中找到距离D下最相似的分量。然后将A和B中最不相似的两个分量之间的距离作为A和B之间的Hausdorff距离。
应用
- 时序处理（动态规划DP/动态时间卷曲DTW）
- 时序系列对齐
- 形状对应点对齐
非几何的相似度方法
- 之前的方法都是基于向量空间模型，在欧式几何空间里运算
- 解决方法
公式看不懂还不够实用反正ppt上也没有不看了
图像纹理特征
什么是纹理
- 纹理是对图像中色彩或色度值空间分布的一种描述
- 不依赖于 颜色 或 亮度
- 是 物体材料 本身固有特性，不随外界改变而改变
- 纹理是图像中像素点 局部分布和全局分布 的统一
分类
- 纹理分为结构纹理和统计纹理
- 结构纹理：由一系列 纹理基元 按照一定规则或重复关系组合而成，但是实际生活中很难定义研究
- 统计纹理：对某一区域色彩或灰度值在空间分布的一种 数值度量 。不直观，但是计算速度快，而且自然界图像大多由不规则成分组成。
Tamura纹理特征
不是特污曼纹理特征
基于心理学角度对纹理的感知，包括 粗糙度、*对比度**、方向度*、**线像度、*规整度*** 和 *粗略度***。其中前三个尤其重要。
- 粗糙度：比较复杂，和其周围2^k * 2^k个点有关
- 对比度：Fcon = σ / α4^(1/4), α4 = μ4/α^4
- 方向度：要卷积，和梯度向量的模有关
卷积
不同卷积矩阵有不同效果
图像卷积结果一定要做额外处理，比如保证值域正确
灰度共生纹理特征
什么事灰度共生矩阵
- 若像素点灰度值为256，则灰度共生矩阵为256 * 256
- 第i行第j列(i,j)表示：符合某一约束条件，灰度值为i何j的像素点共同出现的次数
- 一般用(d,θ)表示像素点和像素点之间的约束条件。eg (1,0)表示neighbor点在reference点右边
灰度共生矩阵的解释
- 灰度共生矩阵中对角线上的值越大，表示图像对比度越小
- 与对角线平行，且离对角线越近的平行线上值越大，表示图像的对比度越小
- 与对角线平行，且离对角线越远的平行线上值越大，表示图像的对比度越大
提取的特征
- 能量：图像灰度共生矩阵中值平方后累加的结果
- 对比度：某个像素点与其领域像素点之间的区别程度。对比度为0则灰度值相等。
- 同质性：灰度共生矩阵个元素分布与其对角线的靠近程度。若图像中各点灰度区别度不大，即像素点趋于同质，则同质性对应取值就越大
- 熵：度量灰度共生矩阵提供的信息量。信息量与该事件概率的倒数成正比，平均信息量就是熵
- 相关性：指定像素对出现的联合概率，即测量整个图像中某个像素与其领域相关性
皮尔森相关系数/样本相关系数怎么看都是协方差和相关系数
ρ和r的值越大，表明X和Y的相关性越强。>0正相关，<0负相关。
图像形状特征
SIFT特征（必须是重点）
其实MR课讲的很清楚了
算法步骤
- 构造不同尺度的高斯滤波算子，对图像进行不同尺度的高斯模糊，获得一系列不同尺度的高斯模糊图像。注意此时像素点数目没有发生任何改变。
- 构造高斯差图像：两个经过不同方差的高斯滤波后的图像相减，可视为“带通滤波”，保留了原始图像中位于某些空间的结构属性，如边界等。
- 搜索候选极大/小值点：与周围26个像素点比较，极大或极小点作为候选关键点。
- 去除候选极大/小值点种可能噪音点：
- 去除其中对比度较低，以及位于图像边缘附近的点：对高斯差图像进行二阶泰勒展开，对X进行一阶求导，令导数为0，得到真正X^的位置公式，带回泰勒展开式。结果含D(X^)，令|D(X^)|<0.03即可去除与周围像素点对比度较低的关键点。
- 去除噪音像素点：Hessian矩阵，α为最大特征根，β为次大特征根，α=rβ，则(rβ+β)^2 / rβ^2 < (r+1)^2/r，采用r=10做阈值，上式成立的关键点才是真的关键点。
- 极大/小值点方向表示：对每个关键点，形成16 * 16的块，对其中每个像素点计算梯度模和方向。
- SIFT点的描述生成：对每个块按照4 * 4切分，得到16个子块，每个块中每个像素点方向已知，因此分成8个区间，构成8Bin的方向直方图。每一个Bin分别代表上、下、左、右、左上、右上、左下、右下等8个方向。磊将所有像素点梯度的模的值，再乘以当前高斯滤波卷积方差σ，再乘1.5，作为这个Bin的大小。得到4 * 4 * 8 = 128维的特征向量。即为SIFT描述。
上下文形状特征
上下文形状描述符，基于Canny算子
Canny算子
算法步骤
- 定位图像边界点
- 跟踪提取边界片段
- 对每个边界像素点提取其与其他边界像素点之间的context信息
- 行程Shape Context的描述
形状无关矩
1~7阶中心矩
局部二值模式（LBP）
基本思想：用一组0/1编码来表示每个像素点与周围像素点之间的空间大小关系
- 从3 * 3方格左上角开始，顺时针或逆时针转圈，如果某个周围像素点大于中心像素点则记为1，否则记为0。一般把得到的8为二进制串转换为十进制的数。
- 结果是0~255之间的数，因此可以统计出一个256维的直方图。这个直方图构成了图像的LBP纹理/形状特征
- 世纪可以改变方格大小或者按照一定步长采用领域像素点，得到更为灵活的方格LBP编码
图像视觉单词构造与特征学习
概述略
自然语言能处理中的文档词袋
图像中视觉单词提取
k-means聚类算法
- 初始化得到K个初始聚类质心，维度均为128维。也可以选K个SIFT特征作为初始聚类质心
- 计算每个Fi（从图像中提取的第i个SIFT特征）点与K个聚类质心的距离，将Fi放入与其最小的聚类质心所在集合
- 如下更新每个聚类集合中的质心：新的聚类质心为所得到聚类集合中所包含元素的均值
- 比较前后两次聚类中，对于新旧的聚类集合，其旧聚类质心与新聚类质心是否接近，如果接近则完成，否则返回2
- 如果迭代步骤超过一定次数，仍不接近，则说明算法收敛较慢，也退出K平均聚类
- 得到的K个聚类质心作为视觉单词
归一化谱聚类算法
- 任意两个数据xi,xj之间相似性形成的相似矩阵 S = exp( -||xi-xj|| / 2σ^2 )
- 归一化拉普拉斯矩阵 L = I - D^(-1/2)SD^(-1/2)
- I是单位对角矩阵，D是对角矩阵diag(d1, … ,dn) di = Σ_j=1:n S(xi,xj) 即di为数据xi与它所有数据xj相似度之和
- 选取L的m个最大特征值对应的特征向量，记其为Z，对它的每一行归一化为单位长度，得到Y
- 用K平均算法把数据点yi聚成k个cluster V1, … , Vk.
图像视觉单词关联关系表示
基于统计方法的关联性建立
图像金字塔模型
两种方法：逐次分割成不同大小尺寸的图像方格/采样成不同尺度的图像
图像高维特征降维基本理论
线性降维和非线性降维
- 线性降维：主成分分析PCA、多维尺度分析MDS、线性判别分析LDA。主要思路是在原始空间设计得到一系列特征向量，然后通过对这些特征向量进行线性组合来达到高维特征降维的目的。优点在于课通过简单变换函数实现原始高维数据降维。
- 非线性降维：适用于原始高维数据分布在非线性特征空间中，如等距映射ISOMAP、局部线性嵌入LLE、拉普拉斯特征映射LE、局部不变投影LPP等。
局部保持与全局保持降维 - 局部保持：LLE、LPP等
- 全局保持：ISOMAP、PCA等
监督学习将为和非监督学习降维 - 监督降维：LDA
- 非监督降维：PCA、LPP
奇异值分解及其应用
奇异值分解（SVD）
隐形语义分析（LSI）
奇异值分解在文本分析中也叫做隐形语义分析（LSI）。
主成分分析降维及其应用
特征人脸方法
本质：通过人脸表达人脸，而不是通过像素点表达人脸
实现：使用奇异值分解或PCA