何照江的博客

图的最短路算法有很多，在此记录一下非常常用的四个算法

• 单源最短路：
  • 不带负权边：Dijkstra
  • 带负权边：Bellman-Ford、SPFA
• 多源最短路：
  • 适用于正负权边：Floyd（但不能有负环）

我们定义无向连通图的 最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。

注意：只有连通图才有生成树，而对于非连通图，只存在生成森林。

链表基础

链表的定义（来自维基百科）：

在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据和一或两个用来指向上一个或下一个节点的位置的链接。

泛洪填充算法 (Flood Fill Algorithm) 泛洪填充算法又称洪水填充算法是在很多图形绘制软件中常用的填充算法，最熟悉不过就是 windows paint 的油漆桶功能。算法的原理很简单，就是从一个点开始附近像素点，填充成新的颜色，直到封闭区域内的所有像素点都被填充新颜色为止。泛红填充实现最常见有四邻域像素填充法，八邻域像素填充法，基于扫描线的像素填充方法。根据实现又可以分为递归与非递归方法，递归方法一般通过深度优先搜索进行实现，非递归方法一般通过广度优先搜索或并查集实现。

我们知道现在的主流编码器都是使用基于块的混合编码框架，以编码块为单位进行预测、变换、量化。

这就导致不同的编码块会使用不同的编码参数，进而不同编码重建块之间的存在一定的差异，尤其在编码块边界处较为明显。编码块边界处不连续的现象就是块效应，产生这种效应的原因主要有两个：

1. 预测时出现不准的地方称为残量（Residual），残量会利用离散余弦变换（Discrete Cosine Transform, DCT）做量化（Quantization），由于量化与反量化会产生误差，因此会在区块边界上产生视觉上的不连续。
2. 运动补偿，同一个画面内相邻区块可能不是从前几个编码影像中相邻区块获取来做预测，因此造成不连续的现象。同样地，画面内预测的方式也可能会造成影像不连续。

这种现象在 QP 较大时比较明显，因此 QP 越大 Deblocking 的强度也越大。

正是由于这种块效应的存在，才需要添加环路滤波器调整相邻的块边缘上的像素值以减轻这种视觉上的不连续感。

x264_deblock_init() 中初始化了一系列环路滤波函数。

1. 包含 "v" 的是垂直滤波器，用于处理水平边界；包含 "h" 的是水平滤波器，用于处理垂直边界。
2. 包含 "luma" 的是亮度滤波器，包含 "chroma" 的是色度滤波器。
3. 包含 "intra" 的是处理边界强度 Bs 为 4 的强滤波器，不包含 "intra" 的是普通滤波器。

[转载] 深入讲解音视频编码原理，H264 码流详解——手写 H264 编码器_黎程雨的博客 - CSDN 博客

要彻底理解视频编码原理，看书都是虚的，需要实际动手，实现一个简单的视频编码器：

知识准备：基本图像处理知识，信号的时域和频域问题，熟练掌握傅立叶正反变换，一维、二维傅立叶变换，以及其变种，dct 变换，快速 dct 变换。

x264 中 x264_quant_init 函数中初始化了量化有关的函数，本文分析部分量化函数的实现

x264 中参数集初始化主要包括如下两个函数：

• x264_sps_init()：根据输入参数生成 H.264 码流的 SPS 信息。
• x264_pps_init()：根据输入参数生成 H.264 码流的 PPS 信息。

对于加减乘运算都会满足：

　　\[ (a + b) \bmod p = a \bmod p + b \bmod p \]

　　\[ (a - b) \bmod p = a \bmod p - b \bmod p \]

　　\[ (a \times b) \bmod p = a \bmod p \times (b \bmod p) \]

但是对于除法而言 $ (a/b) p (a p) / (b p) $

这个可以通过举例验证一下或者可以通过 \(b \bmod p\) 可以为 0 但是分母不能为 0 得到对于除法而言不满足这个运算的结论。

但是如果非要求 \((a/b) \bmod p\) 要怎么办呢？

运动补偿是一种描述相邻帧（相邻在这里表示在编码关系上相邻，在播放顺序上两帧未必相邻）差别的方法，具体来说是描述前面一帧（相邻在这里表示在编码关系上的前面，在播放顺序上未必在当前帧前面）的每个小块怎样移动到当前帧中的某个位置去。这种方法经常被视频压缩 / 视频编解码器用来减少视频序列中的时域冗余。它也可以用来进行去交织（deinterlacing）以及运动插值（motion interpolation）的操作。

本文主要记录 x264 中的 x264_mc_init 函数，该函数主要对 x264_mc_functions_t 结构体中的函数指针进行赋值， 完成了像素内插、拷贝、求平均的等运动补偿相关函数的初始化。

x264 中 x264_dct_init 函数中初始化了与离散余弦变换有关的函数，本文分析部分离散余弦变换函数的实现

x264 中 x264_pixel_init 函数中初始化了与代价计算有关的函数，本文分析部分代价计算函数的实现，包括 SAD、SATD、SSD、等

• SAD (Sum of Absolute Difference) = SAE(Sum of Absolute Error) 绝对误差和
• SATD（Sum of Absolute Transformed Difference）即 hadamard 变换后再绝对值求和
• SSD（Sum of Squared Difference）= SSE（Sum of Squared Error) 差值的平方和
• MAD（Mean Absolute Difference）= MAE（Mean Absolute Error) 平均绝对差值
• MSD（Mean Squared Difference）= MSE（Mean Squared Error）平均平方误差

本文分析 x264 库中的帧内预测的 C 语言函数。