网络结构

• node/vertex：人
• link/edge：人与人之间的relation，可以有标签、权重、 方向
• graph/network：社交网络，表示个体之间的相互关系

• 图、网络参见cs_algorithm/data_structure/graph

基本统计指标、特性

• subnetwork/subgraph

  • singleton：单点集，没有边的子图
  • clique：派系，任意两个节点间均有连边的子图

• degree：

  • 对有向图可以分为out-degree、in-degree
  • average degree：网络平均度，所有节点度的算术平均
  • degree distribution：网络度分布，概率分布函数 $P(k)$

Path

• path length：路径长度
• shortest path：节点间最短路径
• distance：节点距离，节点间最短路径长度

• diameter：网络直径，任意两个节点间距离最大值

• 对规模（节点数量）为$N$大多数现实网络（尤其是社交网络）

  • 小直径：与六度分离实验相符
  • 存在巨大连通分支
  • 高聚类特性：具有较大点聚类系数
  • 明显的模块结构

• giant connected component：巨大连通分支，即规模达到 $O(N)$的连通分支

• node clustering coefficient：点聚类系数

  $$\begin{align*} NC_i & = \frac {triange_i} {triple_i} \\ NC & = \frac {\sum_i NC_i} N \end{align*}$$

  • $triangle_i$：包含节点$i$三角形数量
  • $triple_i$：与节点$i$相连三元组：包含节点$i$的三个 节点，且至少存在节点$i$ 到其他两个节点的两条边
  • $NC_i$：节点$i$聚类系数
  • $NC$：整个网络聚类系数

• edge clustering coefficient：边聚类系数

  $$EC_{ij} = \frac {|包含边<i,j>三角形|} {min\{(d_i-1), (d_j-1)\}}$$

  • $d_i$：节点$i$度，即分母为边$$最大可能存在于 的三角形数量

• edge betweenness：边介数，从源节点$v$出发、通过该边 的最短路径数目

边介数的计算

• 从源节点$i$出发，为每个节点$j$维护距离源节点最短路径 $d_j$、从源节点出发经过其到达其他节点最短路径数目$w_j$

  • 定义源节点$i$距离$d_i=0$、权值$w_i=1$

  • 对源节点$i$的邻接节点$j$，定义其距离$d_j=d_i+1$、 权值$w_j=w_i=1$

  • 对节点$j$的任意邻接节点$k$

    • 若$k$未被指定距离，则指定其距离$d_k=d_j+1$、 权值$w_k=w_j$
    • 若$k$被指定距离且$d_k=d_j+1$，则原权值增加1， 即$w_k=w_k+1$
    • 若$k$被指定距离且$d_k<d_j+1$，则跳过

  • 重复以上直至网络中包含节点的连通子图中节点均被指定 距离、权重

• 从节点$k$经过节点$j$到达源节点$i$的最短路径数目、与节点 $k$到达源节点$i$的最短路径数目之比为$w_i/w_j$

  • 从叶子节点$l$开始，若叶子节点$l$节点$i$相邻，则将 权值$w_i/w_l$赋给边$(i,l)$

  • 从底至上，边$(i,j)$赋值为该边之下的邻边权值之和加1 乘以$w_i/w_j$

  • 重复直至遍历图中所有节点

• 叶子节点：广度优先搜索叶子节点，即不被任何从源节点出发到 其他节点的最短路径经过
• 此边介数计算方式与节点介数中心性计算，都是寻找通过边、 节点的最短路径数目，但是具体计算方式不同

最短路径唯一

• 考虑从任何节点间最短路径只有一条，则某节点到其他节点 的最短路径构成一棵最短路径树

• 找到最短路径树的叶子节点，为每条与叶子节点相连的边赋值 为1
• 自下而上为树中其他边赋值：边之下所有临边值之和加1
• 处理所有节点直至树根源节点时，各边相对于树根源节点的介数 即为其权重

• 对各节点分别重复以上即可得到各边对各节点介数，相总即可得 各边总边介数

Node Centrality

节点中心性：采用某种定量方法对每个节点处于网络中心地位的程度 进行刻画

• 描述整个网络是否存在核心、核心的状态

基于度

• Degree Centrality：度中心性

  $$DC_i = \frac {d_i} {N-1}$$

  • $d_i$：节点$i$的度

  • 衡量节点对促进网络传播过程发挥的作用

• eigenvector centrality：特征向量中心性

  $$ EC_i = $

• subgraph centrality：子图中心性

  $$ SC_i = $

基于路径数

• Betweenness Centrality：介数中心性

  $$BC_i = \frac 2 {(N-1)(N-2)} \sum_{j<k, j,k \neq i} \frac {p_{j,k}(i)} {p_{j,k}}$$

  • $p_{j,k}$：节点$j,k$间路径数量
  • $p_{j,k}(i)$：节点$j,k$间路径经过节点$i$路径数量

  • 衡量节点对其他节点间信息传输的潜在控制能力

• Closeness Centrality

  $$CC_i =$$

Community Structure

社团/模块/社区结构：内部联系紧密、外部联系稀疏（通过边数量 体现）的子图

基于连接频数的定义

$$\begin{align*} \sigma_{in}(S) & = \frac {|E(S)|} {|V(S)|(|V(S)|-1)/2} \\ \sigma_{out}(S) & = \frac {|E| - |E(S)|} {(N - |V(S)|)(N - |V_S| - 1) / 2} \\ \sigma(G) & = \frac {|E|} {|V|(|V|-1) / 2} \end{align*}$$

• $G, S$：全图、子图
• $\simga_{in}(S)$：子图$S$的内部连接率/频数
• $S_{in}$：子图$S$内部的实际边数
• $E, E(S)$：全图、子图$S$内部边
• $V, V(S)$：全图、子图$S$内部节点

• 若子图$S \subset G$满足如下，则称为网络$G$的社区

  $$\sigma_{in}(S) > \sigma(G) > \sigma_{out}(S)$$

强弱社区

• 强社区结构

  $$|E_{in}(S, i)| > |E_{out}(S, i)|, \forall i \in S$$

  • $E_{in}(S, i)$：节点$i$和子图$S$内节点连边
  • $E_{out}(S, i)$：节点$i$和子图$S$内节点连边

• 弱社区结构

  $$\sum_{i \in S} |E_{in}(S, i)| > \sum_{i \in S} |E_{out}(S, i)|, \forall i \in S$$

• 最弱社区结构

  $$\forall i \in S_j, |E_{in}(S_j, i)| > |E(S_j, i, S_k)|, j \neq k, k=1,2,\cdots,M$$

  • 社区$S_1,S_2,\cdots,S_M$是网络$G$中社区
  • $E(S_j, i, S_k)$：子图$S_j$中节点$i$与子图$S_k$之间 连边数

• 改进的弱社区结构：同时满足弱社区结构、最弱社区结构

LS集

LS集：任何真子集与集合内部连边数都多于与集合外部连边数 的节点集合

Clique

• 派系：节点数大于等于3的全连通子图

• n派系：任意两个顶点最多可以通过n-1个中介点连接

  • 对派系定义的弱化
  • 允许两社团的重叠

• 全连通子图：任意两个节点间均有连边

模块度函数Q

$$\begina{align*} Q & = \sum_{i} (e_{i,i} - \hat e_{i,i}) \\ & = \sum_{i} (e_{i,i} - a_i^2) \\ & = \sum_{i} (e_{i,i} - \sum_j e_{i,j}^2) & = Tre - \sum_{i,j} e_{i,j}^2 \end{align*}$$

• $\hat e_{i,i}$：随机网络中社区$i$内连边数占比期望
• $e_{i,j}$：社区$i,j$中节点间连边数在所有边中所占比例
• $ai = \sum_j e{i,j}$：与社区$i$中节点连边数比例

• 思想：随机网络不会具有明显社团结构

  • 不考虑节点所属社区在节点对间直接连边，则应有 $\hat e{i,j} = a_i a_j$，特别的 $\hat e{i,i} = a_i^2$

  • 比较社区实际覆盖度、随机连接覆盖度差异评估对社区结构 的划分

• 划分对应Q值越大，划分效果越好

  • $0< Q <1$：一般以$Q=0.3$作为网络具有明显社团结构的 下限
  • 实际网络中$Q{max} \in [0.3, 0.7]$，$Q{max}$越大 网络分裂（聚类）性质越强，社区结构越明显

• 缺点

  • 采用完全随机形式，无法避免重边、自环的存在，而现实 网络研究常采用简单图，所以Q值存在局限
  • Q值分辨能力有限，网络中规模较大社区会掩盖小社区， 即使其内部连接紧密

• 覆盖度：社区内部连接数占总连接数比例

模块密度D

$$\begin{align*} D & = \sum_{i=1}^M d(S_i) \\ & = \sum_{i=1}^K \frac {|E_{in}(S_i)| - |E_{out}(S_i)|} {|V_{in}(S_i)} \begin{align*}$$

• 模块密度D表示社区内部连边、社区间连边之差与社区节点总数 之比
  • 值越大表示划分结果越好
  • 考虑社区总节点数，克服模块度Q无法探测小社区的缺陷

社区度C

$$C = \frac 1 M \sum_{i=1}^M [\frac {|E_{in}(S_i)|} {|V(S_i)|(|V(S_i)| - 1) / 2} - \frac {|E_{out}(S_i)|} {|V(S_i)| (|V| - V(S_i)|}]$$

• $\frac {|E_{in}(S_i)} {|V(S_i)||(|V(S_i)-1)/2}$：社区 $S_i$的簇内密度
• $\frac {|E_{out}(S_i)} {|V(S_i)||(|V|-|V(S_i))}$：社区 $S_i$的簇内密度

Fitness函数

$$\begin{align*} f_i & = \frac {d_{in}(S_i)} {d_{in}(S_i) + d_{out}(S_i)} \\ & = \frac {2 * E_{in}(S_i)} {2 * E_{in}(S_i) + E_{out}(S_i)} \\ \bar f = \frac 1 M \sum_{i=1}^M f_i \end{align*}$$

• $f_i$：社区$S_i$的fitness函数
• $d{in}(S_i) = 2 * E{in}(S_i)$：社区$S_i$内部度
• $d{out}(S_i) = E{out}(S_i)$：社区$S_i$外部度
• $\bar f$：整个网络社区划分的fitness函数

• fitness函数使用直接的方式避开了模块度Q函数的弊端
  • 应用结果显示其为网络社区结构的有效度量标准

Modularity

$$Q = \frac 1 {2|E|} \sum_{i,j}$$

社区发现算法

网络测试集

• Girvan、Newman人工构造网络

  • 网络包含128个节点、平均分为4组
  • 每组内部连边、组间连边概率分别记为$p{in}, p{out}$
  • 要求每个节点度期望为16

• Lancichinet ti人工构造网络

  • 测试集中节点度、社区大小服从幂律分布
  • 混淆参数$\mu$控制社区结构显著程度

• 小规模、社区结构已知真实网络

  • Zachary空手道俱乐部
  • 海豚社会关系网络
  • 美国大学生足球俱乐部网络

社区发现算法

• Agglomerative Method：凝聚算法

  • NF算法
  • Walk Trap

Division Method：分裂算法

• Girvan-Newman算法
• 边聚类探测算法

• 凝聚算法流程

  • 最初每个节点各自成为独立社区
  • 按某种方法计算各社区之间相似性，选择相似性最高的社区 合并
    • 相关系数
    • 路径长度
    • 矩阵方法
  • 不断重复直至整个网络成为一个社区

• 算法流程可以的用世系图表示

  • 可以在任意合并步骤后停止，此时节点聚合情况即为网络中 社区结构
  • 但应该在度量标准值最大时停止

• 分裂算法流程同凝聚算法相反

Girvan-Newman算法

GN算法

• 流程

  • 计算网络中各边相对于可能源节点的边介数
  • 删除网络中边介数较大的边，每当分裂出新社区 （即产生新连通分支）
    • 计算网络的社区结构评价指标
    • 记录对应网络结构
  • 重复直到网络中边都被删除，每个节点为单独社区，选择 最优评价指标的网络结构作为网络最终分裂状态

• 缺点：计算速度满，边介数计算开销大，只适合处理中小规模 网络

Newman Fast Algorithm

NF快速算法：

• 流程

  • 初始化网络中各个节点为独立社区、矩阵$E={e_{i,j}}$

    $$\begin{align*} e_{i,j} & = \left \{ \begin{array}{l} \frac 1 {2M}, & 边(i,j)存在 \\ 0, & 节点间不存在边 \end{array} \right. \\ a_i & = \frac {d_i} {2M} \end{align*}$$

    • $M$：网络中边总数
    • $e_{i,j}$：网络中社区$i,j$节点边在所有边中占比
    • $a_i$：与社区$i$中节点相连边在所有边中占比

  • 依次合并有边相连的社区对，计算合并后模块度增量

    $$\Delta Q = e_{i,j} + e_{j,i} = 2(e_{i,j}-a_i a_j)$$
    • 根据贪婪思想，每次沿使得$Q$增加最多、减少最小 方向进行
    • 每次合并后更新元素$e_{i,j}$，将合并社区相关行、 列相加
    • 计算网络社区结构评价指标、网络结构

  • 重复直至整个网络合并成为一个社区，选择最优评价指标 对应网络社区结构

• 基于贪婪思想的凝聚算法

• GN算法、NF算法大多使用无权网络，一个可行的方案是计算无权 情况下各边介数，加权网络中各边介数为无权情况下个边介数 除以边权重

  • 此时，边权重越大介数越小，被移除概率越小，符合社区 结构划分定义

Edge-Clustering Detection Algorithm

边聚类探测算法：

• 流程：
  • 计算网络中尚存的边聚类系数值
  • 移除边聚类系数值最小者$(i,j)$，每当分裂出新社区 （即产生新连通分支）
    • 计算网络社区评价指标fitness、modularity
    • 记录对应网络结构
  • 重复直到网络中边都被删除，每个节点为单独社区，选择 最优评价指标的网络结构作为网络最终分裂状态

Walk Trap

随机游走算法：

Label Propagation

标签扩散算法：

Self-Similar

（网络结构）自相似性：局部在某种意义上与整体相似

• fractal分形的重要性质

Random Walk

（网络）随机游走：

游走形式

• unbiased random walks：无偏随机游走，等概率游走
• biased random walks：有偏随机游走，正比于节点度
• self-avoid walks：自规避随机游走
• quantum walks：量子游走

研究内容

• first-passage time：平均首达时间

  $$F(s,t)$$

• mean commute time：平均转移时间

  $$C(t,s) = F(s,t) + F(t,s)$$

• mean return time：平均返回时间

  $$T(s,s)$$

用途

• community detection：社区探测
• recommendation systems：推荐系统
• electrical networks：电力系统
• spanning trees：生成树
• infomation retrieval：信息检索
• natural language proessing：自然语言处理
• graph partitioning：图像分割
• random walk hypothesis：随机游走假设（经济学）
• pagerank algorithm：PageRank算法

网络可视化

Graph Layout

图布局：无实际意义但是影响网络直观效果

• random layout：随机布局，节点、边随机放置
• circular layout：节点放在圆环上
• grid layout：网格布局
• force-directed layout：力导向布局
  • 最常用
  • 动态、由节点相互连接决定布局
  • 点距离较近节点在放置在较近位置
• YiFan Hu layout
• Harel-Koren Fast Multiscale Layout
• NodeXL：节点以box形式被展示，边放置在box内、间

Visualizing Network Features

网络特征可视化：边权、节点特性、标签、团结构

• 标签：只显示感兴趣标签
• 度、中心性、权重等量化特征：借助大小、形状、颜色体现
• 节点分类信息：节点节点颜色、形状体现

Scale Issue

网络可视化：是否对所有网络均有可视化必要

• 网络密度太小、太大，无可视化必要

现实网络

• 网络科学：现实世界的任何问题都可以用复杂关系网络近似模拟

  • 节点：研究问题中主体
  • 边：模拟主体间的某种相互关系

• 现实网络大多为无标度网络，且幂指数$\gamma \in [2, 3]$

  • 网络中大部分节点度很小，小部分hub节点有很大的度
  • 对随机攻击稳健，但对目的攻击脆弱
  • triangle power law：网络中三角形数量服从幂律分布
  • eigenvalue power law：网络邻接矩阵的特征值服从 幂律分布

• 绝大多数现实网络、网络结构模型虽然不能只管看出自相性， 但是在某种length-scale下确实具有自相似性

  • 万维网
  • 社会网络
  • 蛋白质交互作用网络
  • 细胞网络

• 个体社会影响力：社交网络中节点中心性

• power-law distribution：幂律分布
• scale-free network：无标度网络，度分布服从幂律分布的 复杂网络，具有无标度特性
• heavy-tailed distribution：厚尾分布

社交网络

• 人、人与人之间的关系确定，则网络结构固定

• 有人类行为存在的任何领域都可以转化为社交网络形式

  • offline social networks：线下社交网络，现实面对面 接触中的人类行为产生，人类起源时即出现
  • online social networks/social webs：在线社交网络
  • social media websites：多媒体网社交网

• 由于社交网络中人类主观因素的存在，定性特征可以用于社交 网络分析

  • 关系强弱
  • 信任值

• 对网络结构的分析的数量化指标可以分析社交网络的基本特征

  • 度、度分布
  • 聚类系数
  • 路径长度
  • 网络直径

• 数据分析类型

  • Content Data：内容数据分析，文本、图像、其他多媒体 数据
  • Linkage Data：链接数据分析，网络的动力学行为：网络 结构、个体之间沟通交流

社交网络中社区发现

• 现实世界网络普遍具有模块/社区结构特性

  • 内部联系紧密、外部连接稀疏
  • 提取社区/模块结构，研究其特性有助于在网络动态演化 过程中理解、预测其自然出现的、关键的、具有因果关系的 本质特性

• 挑战

  • 现实问题对应的关系网络
    • 拓扑结构类型未知
    • 大部分为随时间变化网络
    • 规模庞大
  • 现有技术方法应用受到限制
    • 多数方法适用静态无向图，研究有向网络、随时间动态 演化网络形式技术方法较少
    • 传统算法可能不适用超大规模网络

• 社区发现/探测重要性

  • 社区结构刻画了网络中连边关系的局部聚集特性，体现了 连边的分布不均匀性
  • 社区通常由功能相近、性质相似的网络节点组成
    • 有助于揭示网络结构和功能之间的关系
    • 有助于更加有效的理解、开发网络

综述

局部二值模式：描述图像局部纹理的特征算子

• 具有旋转不变性、灰度不变性
• 通过对窗口中心的、领域点关系进行比较，重新编码形成新特征 以消除外界场景对图像影响，一定程度上解决了复杂场景下 （光照变换）特征描述问题
• 分类
  • 经典LBP：3 * 3正方向窗口
  • 圆形LBP：任意圆形领域

Classical LBP

Sobel Operator

Laplace Operator

Canny Edge Detector

Circular LBP

缩略图Hash

• 对图像进行特征提取得到0、1特征向量
• 通过比较图片向量特征间汉明距离即可计算图片之间相似度

Average Hashing

aHash：平均哈希算法

• 将原始图片转换为64维0、1向量，即提取出的特征

步骤

• 缩放图片：将图像缩放到8 * 8=64像素
  • 保留结构、去掉细节
  • 去除大小、纵横比差异
• 灰度化：把缩放后图转换为256阶灰度图
• 计算平均值：计算灰度图像素点平均值
• 二值化：遍历64个像素点，大于平均值者记为1、否则为0

Perceptual Hashing

pHash：感知哈希算法

• 利用离散余弦变换降低频率，去除成分较少的高频特征

• 特点

  • 相较于aHash更稳定

步骤

• 缩放图片：将图片缩放至32 * 32
• 灰度化：将缩放后图片转换为256阶灰度图
• 计算DCT：把图片分离成频率集合
• 缩小DCT：保留32 32左上角8 8代表图片最低频率
• 计算平均值：计算缩小DCT均值
• 二值化：遍历64个点，大于平均值者记为1、否则为0

Differential Hashing

dHash：差异哈希算法

• 基于渐变实现

• 特点

  • 相较于dHash非常快
  • 相较于aHash效果好

步骤

• 缩放图片：将图片缩放至9 * 8
• 灰度化：将缩放后图片转换为256阶灰度图
• 计算差异值：对每行像素计算和左侧像素点差异，得到8 * 8
• 二值化：遍历64个点，大于0记为1、否则为0

Scale-Invariant Feature Transform

SIFT：通过求图中interest/corner point、及其scale和 orientation描述子得到特征，并进行图像特征点匹配

• SIFT是检测局部特征的算法
  • 实质：在不同尺度空间查找关键点，计算关键点大小、方向 、尺度信息，进而组成对关键点得描述
  • SIFT查找的关键点为突出、稳定的特征点，不会因光照、 仿射变换、噪声等因素而改变
    • 角点
    • 边缘点
    • 暗区亮点
    • 亮区暗点
  • 匹配过程就是对比特征点过程

• 优点

  • 稳定性：具有旋转、尺度、平移、视角、亮度不变性， 利于对目标特征信息进行有效表达
  • 独特性：信息量丰富，适合海量特征数据中进行匹配
  • 多量性：少数物体也可以产生大量SIFT特征向量
  • 可扩展性：可以方便同其它形式特征向量联合
  • 对参数调整稳健性好：可以根据场景调整特征点数量进行 特征描述、方便特征分析

• 缺点

  • 不借助硬件加速、专门图像处理器难以实现

构建尺度空间

图像的尺度空间：解决如何对图像在所有尺度下描述的问题

• 思想：对原始图像进行尺度变换，获得多尺度空间下图像表示 序列，模拟图像数据的多尺度特征

  • 对序列进行尺度空间主轮的提取
  • 以主轮廓作为特征向量，实现边缘、角点检测、不同分辨率 上稳定关键点提取

• 对高斯金字塔生成的O组、L层不同尺度图像，$(O, L)$就构成 高斯金字塔的尺度空间

  • 即以高斯金字塔组$O$、层$L$作为坐标
  • 给定一对$(o,l)$即可唯一确定一幅图像

图像金字塔

图像金字塔：以多分辨率解释图像的结构

• 通过对原始图像进行多尺度像素采样方式生成N个不同 分辨率的图像

  • 图像分辨率从下至上逐渐减小
  • 直至金字塔顶部只包含一个像素

• 获取图像金字塔步骤

  • 利用低通滤波器平滑图像
  • 对平滑图像进行采样
    • 上采样：分辨率逐渐升高
    • 下采样：分辨率逐渐降低

高斯金字塔

高斯金字塔：由很多组图像金字塔构成，每组金字塔包含若干层

• 同一组金字塔中

  • 每层图像尺寸相同
  • 仅高斯平滑系数$\sigma$不同，后一层图像是前一层$k$倍

• 不同组金字塔中

  • 后一组图像第一个图像是前一组倒数第三个图像二分之一 采样
  • 图像大小是前一组一半

构建过程

• 构建第1组图像金字塔

  • 第1层：将原图扩大一倍得到

  • 第2层：第1层图像经过高斯卷积得到

    • SIFT算子中，高斯平滑参数$\sigma=1.6$

  • 第k层：

    • $\sigma$乘以比例系数得到新平滑因子 $\sigma = k\sigma$，
    • 使用平滑因子平滑第k层图像得到

  • 不断重复得到L层图像

• 构建第k组图像金字塔

  • 第1层：将第k-1组金字塔倒数第3层做比例因子为2的降采样 得到

  • 之后同第1组图像金字塔

• 不断重复得到O组图像金字塔，共计O * L个图像

Difference of Gaussian

DOG金字塔：差分金字塔

• DOG金字塔第0组第k层由高斯金字塔第0组第k+1层减去第k层得到

  • DOG金字塔每组比高斯金字塔少一层
  • 按高斯金字塔逐组生成$O * (L-1)$个差分图像

• DOG图像包含大量信息（需要归一化才能人眼可见）

  • 在不同DOG层（即不同模糊程度、不同尺度）都存在的特征 即SIFT要提取的稳定特征
  • 后续SIFT特征点都是在DOG金字塔中进行

空间极值点检测

空间极值点检测：关键点初步查探

• 寻找DOG图像极值点：每个像素点和其所有相邻点比较

  • 需要同时比较图像域、尺度空间域相邻点
  • 保证关键点在尺度空间、二维图像空间上都是局部极值点

• 对二维图像空间，对中心点

  • 图像域：与3 * 3领域内8个点比较
  • 同组尺度空间：和上下两层图像中2 * 9个点比较

• 极值点是在不同尺度空间下提取的，保证了关键点尺度不变性

精确定位

稳定关键点精确定位

• DOG值对噪声、边缘敏感，需要对局部极值进一步筛选，去除 不稳定、错误检测极值点

• 构建高斯金字塔时采用下采样图像，需要求出下采样图像中 极值点对应在原始图像中确切位置

方向信息分配

稳定关键点方向信息分配

• 为关键点分配方向信息赋予关键点旋转不变性

• 通过对稳定关键点求梯度实现方向分配

计算方式

• 梯度幅度值

  $$m(x, y) = \sqrt {(L(x+1,y) - L(x-1,y))^2 + (L(x,y+1) - L(x,y-1))^2}$$

• 梯度方向

  $$\theta(x,y) = tan^{-1} (\frac {L(x,y+1) - L(x,y-1)} {L(x+1,y) - L(x-1,y)})$$

• 通过梯度方向直方图给出关键点梯度方向

  

  • 计算关键点为中心领域内所有点梯度方向，在0~360度范围
  • 把所有梯度方向划分到36个区域，每个方向代表10度
  • 累计每个方向关键点数目，生成梯度方向直方图
  • 将直方图中峰值代表方向作为关键点主方向

  • 若存在相当于峰值80%大小的方向，则作为辅方向

    • 辅方向可以增强匹配的鲁棒性

    • Lowe指出：大概15%关键点具有辅方向，且这些关键点 对稳定匹配起关键作用

关键点描述

关键点描述：以数学方式定义关键点的过程，包括关键点周围对其 有贡献的领域点

• 对关键点周围像素区域分块

  • 计算块内梯度直方图
  • 生成具有独特性的向量，作为对该区域图像信息的抽象表述

• 如下图

  

  • 将关键点周围分为2 * 2块
  • 对每块所有像素点梯度做高斯加权（softmax拉开差距？）
  • 每块最终取8个方向，得到2 2 8维向量，作为中心 关键点数学描述

• Lowe实验表明：采用4 4 8共128维描述子表征关键点， 综合效果最好

特征点匹配

特征点匹配：计算两组特征点128维描述向量的欧式距离

• 欧式距离越小、相似度越高，小于指定阈值时既可认为匹配成功

Speeded Up Robust Feature

SURF特征：对SIFT算法的改进，降低了时间复杂度，提高了稳健性

• 主要是简化SIFT一些运算
  • 高斯二阶维分模型简化，卷积平滑操作仅需要转换为加减 运算
  • 最终生成特征向量维度从128维减少为64维

Brief

Oriented Brief

ORB：Brief算法改进版

• 比SIFT算法快100倍

综述

• corner point：角点，邻域各方向上灰度变化值足够高的点， 是图像边缘曲线上曲率极大值的点

分类

• 基于灰度图像的角点检测

  • 基于梯度：计算边缘曲率判断角点
  • 基于模板：考虑像素邻域点的灰度变化，将领域点亮度对比 足够大的点定义为角点
  • 基于模板、梯度组合

• 基于二值图像的角点检测：将二值图像作为单独的检测目标， 可使用各种基于灰度图像的角点检测方法

• 基于轮廓曲线的角点检测：通过角点强度、曲线曲率提取角点

思想、步骤

• 使用角点检测算子，对图像每个像素计算 cornner response function值

  $$E(u, v) = \sum_{(x,y)} w(x,y)[I(x+u, y+v) - I(x,y)]^2$$

  • $w(x,y)$：window function，窗口函数
  • $I(x,y)$：图像梯度
  • $E(x,y)$：角点响应函数，体现灰度变化剧烈程度，变化 程度剧烈则窗口中心就是角点

• 阈值化角点响应函数值

  • 根据实际情况选择阈值$T$
  • 小于阈值$T$者设置为0

• 在窗口范围内对角点响应函数值进行非极大值抑制

  • 窗口内非响应函数值极大像素点置0

• 获取非零点作为角点

Moravec

todo

步骤

• 取偏移量$(\Delta x, \Delta y)$为 $(1,0), (1,1), (0,1), (-1,1)$，分别计算每个像素点灰度 变化

• 对每个像素点(x_i, y_i)$计算角点响应函数 $R(x) = min {E}$

• 设定阈值$T$，小于阈值者置0

• 进行非极大值抑制，选择非0点作为角点检测结果

特点

• 二值窗口函数：角点响应函数不够光滑
• 只在4个方向（偏移量）上计算灰度值变化：角点响应函数会在 多处都有较大响应值
• 对每个点只考虑响应函数值最小值：算法对边缘敏感

Harris

Good Features to Track

Feature from Accelerated Segment Test

FAST：加速分割测试获得特征

文本挖掘

• 文本处理：将非结构化数据转换为结构化数据

• 预测建模

  • 文本分类：根据观察到的对象特征值预测其他特征值

• 描述建模

  • 文本聚类：对数据对象进行概括，以看到数据对象的最重要 特征
    • 适应范围非常广
  • 聚类分析

• 基于相似度方法

  • 需要用户显式指定相似度函数
  • 聚类算法根据相似度的计算结果将相似文本分在同一个组
  • 每个文本只能属于一个组，因此也成为“硬聚类”

• 基于模型的方法

  • 文本有多个标签，也成为“软聚类”

话题检测

找出文档中的K个话题，计算每个文档对话题的覆盖率

话题表示方法

基于单个词

基于词分布

问题描述

• 输入

  • N个文档构成的文本集C
  • 话题个数K
  • 词典V

• 输出

  • K个话题的分布 $(\theta_1, \theta2, \cdots, \theta_K)$
  • N个文档在K个话题上的概率分布 $(\pi_1, \pi_2, \cdots, \pi_N)$

语言模型

词向量：将向量表示词

• 1-of-N representation/one hot representation：one-hot 表示词

  

  • 词向量维度为整个词汇表大小
  • 简单、效率不高

• distributed representation：embedding思想，通过训练， 将词映射到较短词向量中

  

  • 词向量维度自定义
  • 容易分析词之间关系

Continuous Bag-of-Words

CBOW：输入特征词上下文相关词对应词向量，输出特征词的词向量

• CBOW使用词袋模型
  • 特征词上下文相关从平等，不考虑和关注的词之间的距离

Skip-Gram

Skip-Gram：输入特征词词向量，输出softmax概率靠前的词向量

神经网络词向量

神经网络词向量：使用神经网络训练词向量

• 一般包括三层：输入层、隐层、输出softmax层

• 从隐藏层到输出softmax层计算量很大

  • 需要计算所有词的softmax概率，再去找概率最大值