图像处理算法工程师-面试准备

一、基础的图像处理知识
1.腐蚀与膨胀、开闭运算
对于二值图像，使用合适大小、形状结构元素（Structure Element）对图像中的每一个元素进行操作；
腐蚀：将图像中每一个点与结构元素进行比对，如果完全一致，则保留该点；如果不一致，将该点去除；
膨胀：将图像中每一个点与结构元素进行比对，如果完全一致，则保留该点；如果不一致，以该点为中心点，利用结构元素为模板对该点进行扩充。
开运算：先腐蚀后膨胀，目的是去除图像中的一些孤立块，减少噪声；
闭运算：先膨胀后腐蚀，目的是减少空洞、合并同类。
2.图像的缩放算法
最近邻算法、双线性插值、双三次插值
3.图像特征提取方法
HOG、LBP、SIFT、SURF
https://www.cnblogs.com/zhehan54/p/6723956.html
SIFT：
SIFT算法是用来提取图像局部特征的经典算法，SIFT算法的实质是在不同的尺度空间上查找关键点(特征点)，并计算出关键点的方向。SIFT所查找到的关键点是一些十分突出，不会因光照，仿射变换和噪音等因素而变化的点，如角点、边缘点、暗区的亮点及亮区的暗点等。

1、构建DOG尺度空间
高斯金字塔
高斯差分金字塔
2、关键点搜索和定位
3、方向赋值
4、关键点描述子的生成

1，构建DOG尺度空间
（1）基础知识
（a）尺度空间：
在视觉信息处理模型中引入一个被视为尺度的参数，通过连续变化尺度参数获得不同尺度下的视觉处理信息，然后综合这些信息以深入地挖掘图像的本质特征。尺度空间方法将传统的单尺度视觉信息处理技术纳入尺度不断变化的动态分析框架中，因此更容易获得图像的本质特征。尺度空间的生成目的是模拟图像数据多尺度特征。
尺度空间中各尺度图像的模糊程度逐渐变大，能够模拟人在距离目标由近到远时目标在视网膜上的形成过程。大尺度对应图像的概貌特征，小尺度对应图像的细节特征。所以对不同尺度的图像检测关键点，最终得到的sift特征点具有尺度不变性。尺度空间是客观存在的，我们使用高斯卷积的形式来表现尺度空间。
一幅二维图像的尺度空间可以定义为
图片说明
其中I(x,y)是图像区域，G(x,y,σ)是尺度可变高斯函数，x,y是空间坐标，σ大小决定图像的平滑程度。
（b）高斯模糊：
这里尺度空间的生成需要使用高斯模糊来实现，Lindeberg等人已经证明高斯卷积核是实现尺度变换的唯一线性核。高斯模糊是一种图像滤波器，它使用正态分布(高斯函数)计算模糊模板，并使用该模板与原图像做卷积运算，达到模糊图像的目的。
图片说明
其中， $图片说明$ 是正态分布的标准差，值越大，图像越模糊(平滑)。r为模糊半径，模糊半径是指模板元素到模板中心的距离。如二维模板大小为m*n，则模板上的元素(x,y)对应的高斯计算公式为：

https://blog.csdn.net/happyer88/article/details/45817305

SURF
https://www.cnblogs.com/gfgwxw/p/9415218.html
SURF和SIFT的主要区别在于计算速度的不同，这主要是由于积分图的引入导致的。
图片说明
4.最邻近插值算法和双线性插值算法
https://www.cnblogs.com/wanghui-garcia/p/11171954.html
用于图像缩放时，目标点的坐标为浮点数时，不知道应该对应的是哪个像素点的像素值。
这个时候最邻近插值算法使用的方法就是四舍五入法，表示为[.],所以像素值f(x,y) = f( [W/w * x], [H/h y])
举个例子，如果原图为55，缩放后的图为33，那么缩放后的图的像素点(1,1)对应的就是原图中([5/3 * 1], [5/3 * 1]) = ([0.6], [0.6]) = (1,1) 像素点对应的像素值。这种方法的好处就是简单，但是坏处就是太过粗暴，会缺失精度，造成缩放后的图像灰度上的不连续，在变化地方可能出现明显锯齿状。
双线性插值采用与其距离最近的四个点，距离越近的点对所求像素点的影响越大。最终得到的图片较最近邻插值算法更为平滑。
HOG步骤：
1.转为灰度图；
2.Gamma校正；
3.计算梯度和方向；
4.根据方向得到直方图；
5.构成向量形成描述子。
http://shartoo.github.io/HOG-feature/
LBP：
二进制
5.
二、经典算法与数据结构
1.排序
2.
三、传统机器学习
1.判别式模型与生成式模型
*判别式模型(Discriminative Model)：直接对条件概率p(y|x)进行建模，常见判别模型有：线性回归、决策树、支持向量机SVM、k近邻、神经网络等；
**生成式模型(Generative Model)：对联合分布概率p(x,y)进行建模，常见生成式模型有：隐马尔可夫模型HMM、朴素贝叶斯模型、高斯混合模型GMM、LDA等；生成式模型更普适；
判别式模型更直接，目标性更强生成式模型关注数据是如何产生的，寻找的是数据分布模型；
判别式模型关注的数据的差异性，寻找的是分类面由生成式模型可以产生判别式模型，但是由判别式模式没法形成生成式模型
2.L1正则化与稀疏性
图片说明

3.L2正则化与平滑性
L2正则化：在原来的损失函数上加上权重的平方和：

其中，Ein 是未包含正则化项的训练样本误差，λ 是正则化参数，可调。
我们知道，正则化的目的是限制参数过多或者过大，避免模型更加复杂。例如，使用多项式模型，如果使用 10 阶多项式，模型可能过于复杂，容易发生过拟合。所以，为了防止过拟合，我们可以将其高阶部分的权重 w 限制为 0，这样，就相当于从高阶的形式转换为低阶。
为了达到这一目的，最直观的方法就是限制 w 的个数，但是这类条件属于 NP-hard 问题，求解非常困难。所以，一般的做法是寻找更宽松的限定条件：
图片说明
上式是对 w 的平方和做数值上界限定，即所有w 的平方和不超过参数 C。这时候，我们的目标就转换为：最小化训练样本误差 Ein，但是要遵循 w 平方和小于 C 的条件。
下面，我用一张图来说明如何在限定条件下，对 Ein 进行最小化的优化。
图片说明
如上图所示，蓝色椭圆区域是最小化 Ein 区域，红色圆圈是 w 的限定条件区域。在没有限定条件的情况下，一般使用梯度下降算法，在蓝色椭圆区域内会一直沿着 w 梯度的反方向前进，直到找到全局最优值 wlin。例如空间中有一点 w（图中紫色点），此时 w 会沿着 -∇Ein 的方向移动，如图中蓝色箭头所示。但是，由于存在限定条件，w 不能离开红色圆形区域，最多只能位于圆上边缘位置，沿着切线方向。w 的方向如图中红色箭头所示。

那么问题来了，存在限定条件，w 最终会在什么位置取得最优解呢？也就是说在满足限定条件的基础上，尽量让 Ein 最小。

我们来看，w 是沿着圆的切线方向运动，如上图绿色箭头所示。运动方向与 w 的方向（红色箭头方向）垂直。运动过程中，根据向量知识，只要 -∇Ein 与运行方向有夹角，不垂直，则表明 -∇Ein 仍会在 w 切线方向上产生分量，那么 w 就会继续运动，寻找下一步最优解。只有当 -∇Ein 与 w 的切线方向垂直时，-∇Ein在 w 的切线方向才没有分量，这时候 w 才会停止更新，到达最接近 wlin 的位置，且同时满足限定条件。
图片说明

介绍完 L1 和 L2 正则化的物理解释和数学推导之后，我们再来看看它们解的分布性。

以二维情况讨论，上图左边是 L2 正则化，右边是 L1 正则化。从另一个方面来看，满足正则化条件，实际上是求解蓝域与黄域的交点，即同时满足限定条件和 Ein 最小化。对于 L2 来说，限定区域是圆，这样，得到的解 w1 或 w2 为 0 的概率很小，很大概率是非零的。

对于 L1 来说，限定区域是正方形，方形与蓝***域相交的交点是顶点的概率很大，这从视觉和常识上来看是很容易理解的。也就是说，方形的凸点会更接近 Ein 最优解对应的 wlin 位置，而凸点处必有 w1 或 w2 为 0。这样，得到的解 w1 或 w2 为零的概率就很大了。所以，L1 正则化的解具有稀疏性。

扩展到高维，同样的道理，L2 的限定区域是平滑的，与中心点等距；而 L1 的限定区域是包含凸点的，尖锐的。这些凸点更接近 Ein 的最优解位置，而在这些凸点上，很多 wj 为 0。

4.过拟合的解决方法
a.增加数据
b.降低模型复杂度
c.采用正则化方法
5.欠拟合的解决方法
a.增加特征
b.增加模型的复杂度
c.降低正则化的系数
5.进行特征归一化的方法和原因：线性归一化和零均值归一化；消除数据特征之间的量纲对于特征选择的影响，比如归一化之后采用梯度下降法更容易收敛到最优解。但是归一化并不对所有的模型都起作用，比如对于决策树就毫无影响。
6.Xgboost和GBDT 的区别
xgboost相比传统gbdt有何不同？xgboost为什么快？xgboost如何支持并行？
https://www.cnblogs.com/fujian-code/p/9018114.html
1）将树模型的复杂度加入到正则项中，来避免过拟合，因此泛化性能会优于GBDT。
　 2）损失函数是用泰勒展开式展开的，同时用到了一阶导和二阶导，可以加快优化速度。
　　3）和GBDT只支持CART作为基分类器之外，还支持线性分类器，在使用线性分类器的时候可以使用L1，L2正则化。
　　4）引进了特征子采样，像RandomForest那样，这种方法既能降低过拟合，还能减少计算。
　　5）在寻找最佳分割点时，考虑到传统的贪心算法效率较低，实现了一种近似贪心算法，用来加速和减小内存消耗，除此之外还考虑了稀疏数据集和缺失值的处理，对于特征的值有缺失的样本，XGBoost依然能自动找到其要分裂的方向。
　　6）XGBoost支持并行处理，XGBoost的并行不是在模型上的并行，而是在特征上的并行，将特征列排序后以block的形式存储在内存中，在后面的迭代中重复使用这个结构。这个block也使得并行化成为了可能，其次在进行节点分裂时，计算每个特征的增益，最终选择增益最大的那个特征去做分割，那么各个特征的增益计算就可以开多线程进行。
7.集成学习的分类？
Boosting和Bagging
Boosting:串行方式，各个基分类器之间有依赖。每一层在训练时，对前一层基分类器分错的样本给予更高的权重。减少集成分类器的偏差。
Bagging：并行方式，各个基分类器之间无强依赖。每个基分类器之间单独训练，再通过集体投票决策的方式做决策。减小集成分类器的方差。
8.AdaBoost
Boosting策略，可能采用决策树（也可能是其他算法）作为基训练器，损失函数采用指数损失。每一个训练器都受上一个训练器的影响，重点关注上一个分类器分类错误的训练样本。同时最终预测时，错误率低的分类器他的结果预测权重较大。
https://blog.csdn.net/fuqiuai/article/details/79482487
9.GBDT
Boosting策略，每一颗树学习的都是之前所有树结论和的残差。

10.随机森林（Random Forest）
Bagging策略。

11.logisitic回归
解决分类问题，学习的是将输入样本预测为1的条件概率，其因变量为+1和-1，值域是离散的。
四、深度学习
fasterRCNN论文
ResNet
Deeplab3
PSP
Unet

1.机器学习中的梯度消失、爆炸原因及其解决方法
https://blog.csdn.net/qq_25737169/article/details/78847691
在介绍梯度消失以及爆炸之前，先简单说一说梯度消失的根源—–深度神经网络和反向传播。目前优化神经网络的方法都是基于反向传播的思想，即根据损失函数计算的误差通过梯度反向传播的方式，指导深度网络权值的更新优化。我们最优的权值就是为了寻找下图中的最小值点，对于这种数学寻找最小值问题，采用梯度下降的方法再适合不过了。
梯度消失与梯度爆炸其实是一种情况，两种情况下梯度消失经常出现，一是在深层网络中，二是采用了不合适的损失函数，比如sigmoid。梯度爆炸一般出现在深层网络和权值初始化值太大的情况下，下面分别从这两个角度分析梯度消失和爆炸的原因。
a.深层网络角度
b.激活函数角度
解决方案：
a.预训练加微调
b.梯度剪切加正则
c.relu、leakrelu、elu等激活函数
d.残差结构
e.LSTM
2.LSTM与GRU
3.卷积参数的计算
https://blog.csdn.net/qian99/article/details/79008053

五、语言C/C++
1.C语言中struct成员变量顺序对内存的占用有影响么？内存对齐方式
有影响，比如定义三个变量double、char和int,当三者顺序是char、int、double时，占用4+4+8=16个字节的内存；
当是int、char、double时，占用4+4+8=16个字节的内存；当是double、int、char时，占用8+8+8=24个字节的内存。最小占用空间时16个字节，最大占用空间时24个字节。
2.C语言中静态变量存在哪里？
静态局部变量和静态全局变量都存储在静态（全局）存储区中。
局部变量存放在栈区；全局变量存放在静态存储区。
补充：
在c/c++中，内存分成5个区，他们分别是堆、栈、自由存储区、全局/静态存储区和常量存储区。
栈：就是那些由编译器在需要的时候分配，在不需要的时候自动清楚的变量的存储区。里面的变量通常是局部变量、函数参数等。
堆：就是那些由new分配的内存块，他们的释放编译器不去管，由我们的应用程序去控制，一般一个new就要对应一个delete。如果程序员没有释放掉，那么在程序结束后，操作系统会自动回收。
自由存储区：就是那些由malloc等分配的内存块，他和堆是十分相似的，不过它是用free来结束自己的生命的。
全局存储区（静态存储区）：全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。程序结束后有系统释放。
常量存储区：这是一块比较特殊的存储区，他们里面存放的是常量，不允许修改。
六、数学
1.鞍点、在深度学习中如何避开鞍点
https://blog.csdn.net/zhangbaoanhadoop/article/details/83050111
若某个一阶导数为0的点在至少一个方向上的二阶导数小于0，那它就是鞍点。在鞍点处，横着看的话，鞍点就是个极小值点，但是竖着看的话，鞍点就是极大值点（线性代数和最优化算法过关的同学应该能反应过来，鞍点处的Hessian矩阵的特征值有正有负。
图片说明
2.池化层的反向传播是如何实现的?maxpooling和meanpooling的区别？
https://www.cnblogs.com/WSX1994/p/11230121.html
https://blog.csdn.net/Jason_yyz/article/details/80003271
CNN的前向传播
对于卷积层，卷积核与输入矩阵对应位置求积再求和，作为输出矩阵对应位置的值。如果输入矩阵inputX为M * N大小，卷积核为a * b大小，那么输出Y为（M-a+1）（N-b+1）大小。

*Pooling池化操作的反向梯度传播**
CNN网络中另外一个不可导的环节就是Pooling池化操作，因为Pooling操作使得feature map的尺寸变化，假如做2×2的池化，假设那么第l+1层的feature map有16个梯度，那么第l层就会有64个梯度，这使得梯度无法对位的进行传播下去。其实解决这个问题的思想也很简单，就是把1个像素的梯度传递给4个像素，但是需要保证传递的loss（或者梯度）总和不变。根据这条原则，mean pooling和max pooling的反向传播也是不同的。
1、mean pooling
mean pooling的前向传播就是把一个patch中的值求取平均来做pooling，那么反向传播的过程也就是把某个元素的梯度等分为n份分配给前一层，这样就保证池化前后的梯度（残差）之和保持不变，还是比较理解的，图示如下：