C++及图像算法基础知识（一）

PS：为了面试准备的，总结的有点粗糙。

 

1.receptive field：感受野

在卷积神经网络CNN中，决定某一层输出结果中一个元素所对应的输入层的区域大小，被称作感受野

 

左图：如果只看特征图，我们无法得知特征的位置（即感受野的中心位置）和区域大小（即感受野的大小）

右图：CNN特征图的大小固定，其特征位置即感受野的中心位置。各个特征（可以理解为图像中的像素点）的位置在卷积后保持不变，空的部分用空白来填充。

 

2.虚函数，virtual关键字，c++多态

a、编译时多态性（静态多态）：通过重载函数实现

b、运行时多态性（动态多态）：通过虚函数实现。（声明基类的指针，利用该指针指向任意一个子类对象，调用相应的虚函数，可以根据指向的子类的不同而实现不同的方法。virtual关键字）

 

虚函数： 就是允许被其子类重新定义的成员函数

纯虚函数： 是在基类中声明的虚函数，它在基类中没有定义，但要求任何派生类都要定义自己的实现方法

 

简单记：一个接口，多种方法

 

作用：封装可以使得代码模块化，继承可以扩展已存在的代码，他们的目的都是为了代码重用。而多态的目的则是为了接口重用。

 

 

3.常见CNN结构

LeNet,AlexNet,VGG,GoogleNet,ResNet

 

4.物体跟踪与识别，SLAM（重要！！！！）

Simultaneous Localization and Mapping, 同时定位与地图构建

SLAM 的目的是解决“定位”与“地图构建”

应用：

室内扫地机

室内服务机器人

自动驾驶

空中的无人机

虚拟现实

增强现实

 

整个视觉SLAM流程包括以下步骤：

1.传感器信息读取。在视觉SLAM中主要为相机图像信息的读取和预处理。如果是在机器人中，还可能有码盘、惯性传感器等信息的读取和同步。

2.视觉里程计（Visual Odometry，VO）。视觉里程计的任务是估算相邻图像间相机的运动，以及局部地图的样子。VO又称为前端（Front End）。

3.后端优化（Optimization）。后端接受不同时刻视觉里程计测量的相机位姿，以及回环检测的信息，对它们进行优化，得到全局一致的轨迹和地图。由于接在VO之后，又称为后端（Back End）。

4.回环检测（Loop Closing）。回环检测判断机器人是否到达过先前的位置。如果检测到回环，它会把信息提供给后端进行处理。

5.建图（Mapping）。它根据估计的轨迹，建立与任务要求对应的地图。

经典的视觉SLAM框架是过去十几年的研究成果。这个框架本身及其所包含的算法已经基本定型，并且已经在许多视觉程序库和机器人程序库中提供。依靠这些算法，我们能够构建一个视觉SLAM系统，使之在正常的工作环境里实时定位与建图。因此，我们说，如果把工作环境限定在静态、刚体，光照变化不明显、没有人为干扰的场景，那么，这个SLAM系统是相当成熟的了。

 

 

5.梯度下降和牛顿法的区别

凸函数求极值的方法，他们都是为了求得目标函数的近似解。

梯度下降：

 

 

首先计算目标函数在当前参数值的斜率（梯度），然后乘以步长因子后带入更新公式，如图点所在位置（极值点右边），此时斜率为正，那么更新参数后参数减小，更接近极小值对应的参数。

如果更新参数后，当前参数值仍然在极值点右边，那么继续上面更新，效果一样。

如果更新参数后，当前参数值到了极值点的左边，然后计算斜率会发现是负的，这样经过再一次更新后就会又向着极值点的方向更新。

根据这个过程我们发现，每一步走的距离在极值点附近非常重要，如果走的步子过大，容易在极值点附近震荡而无法收敛。解决办法：将alpha设定为随着迭代次数而不断减小的变量，但是也不能完全减为零。

 

牛顿法：

首先得明确，牛顿法是为了求解函数值为零的时候变量的取值问题的，具体地，当要求解 f(θ)=0时，如果 f可导，那么可以通过迭代公式

 

当应用于求解最大似然估计的值时，变成ℓ′(θ)=0的问题。这个与梯度下降不同，梯度下降的目的是直接求解目标函数极小值，而牛顿法则变相地通过求解目标函数一阶导为零的参数值，进而求得目标函数最小值。

 

当θ是向量时，牛顿法可以使用下面式子表示：

其中H叫做海森矩阵，其实就是目标函数对参数θ的二阶导数。

 

海森矩阵的逆就好比梯度下降法的学习率参数alpha。牛顿法收敛速度相比梯度下降法很快，而且由于海森矩阵的的逆在迭代中不断减小，起到逐渐缩小步长的效果。

 

牛顿法的缺点就是计算海森矩阵的逆比较困难，消耗时间和计算资源。因此有了拟牛顿法。

 

 

牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。

根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。

 

 

6.颜色检测，为什么转换到HSV空间

按照维基百科定义，“颜色是通过眼、脑和我们的生活经验所产生的一种对光的视觉效应。人对颜色的感觉不仅仅由光的物理性质所决定，还包含心理等许多因素，比如人类对颜色的感觉往往受到周围颜色的影响”。

当我们想要检测特定颜色的时候，也就是需要某种“色相+饱和度”的颜色，这时使用RGB色彩空间不是一个好主意，而HSV色彩空间空间是个不错的选择。HSV色彩空间中，各个分量分别是Hue(色相）、饱和度（Saturation）、Value（明度），其中H和S通道对颜色有着重要的影响。题图是当明度最大时，H(0~180)和S(0~255)的变化对颜色的影响。我们可以在根据H和S的值选择特定的颜色。

HSV 颜色空间可以很好地把颜色信息和亮度信息分开，将它们放在不同的通道中，减小了光线对于特定颜色识别的影响。

 

7.Sobel和Laplace哪个对噪声更敏感？怎么在数学上证明

Laplace，二阶导，对噪声更敏感，各向同性，没有方向信息，sobel有垂直、水平方向

 

8.sobel和canny边缘检测的区别

sobel检测的边缘较粗较宽，看起来图片是模糊的，canny检测的边缘较细，边缘点定位的较准

 

 

9.编译器工作过程

源码要运行，必须先转成二进制的机器码：

1) 编译预处理

2) 编译、优化阶段

3) 汇编过程

4) 链接程序

一、编译预处理

（1）宏定义指令（2）条件编译指令（3） 头文件包含指令

 

二、编译、优化阶段

经过预编译得到的输出文件中，只有常量；如数字、字符串、变量的定义，以及C语言的关键字，如main,if,else,for,while,{,}, +,-,*,\等等。

在《编译原理》中我们可以了解到一个编译器对程序代码的编译主要分为下面几个过程：

a) 词法分析

b) 语法分析

c) 语义分析

d) 中间代码生成

e) 代码优化

f) 代码生成

g) 符号表管理

h) 将多个步骤组合成趟

i) 编译器构造工具

优化处理是编译系统中一项比较艰深的技术。它涉及到的问题不仅同编译技术本身有关，而且同机器的硬件环境也有很大的关系。优化处理主要分为下面几个过程：

1) 局部优化

a) 基本块的划分

b) 基本块的变换

c) 基本块的DAG表示

d) DAG的应用

e) 构造算法讨论

2) 控制流分析和循环优化

a) 程序流图与循环

b) 循环

c) 循环的查找

d) 可归约流图

e) 循环优化

3) 数据流的分析与全局优化

a) 一些主要的概念

b) 数据流方程的一般形式

c) 到达一定值数据流方程

d) 可用表达式及其数据流方程

e) 活跃变量数据流方程

f) 复写传播

经过优化得到的汇编代码必须经过汇编程序的汇编转换成相应的机器指令，方可能被机器执行。

 

三、汇编过程

汇编过程实际上指把汇编语言代码翻译成目标机器指令的过程。

 

四、链接程序

由汇编程序生成的目标文件并不能立即就被执行，其中可能还有许多没有解决的问题。

例如，某个源文件中的函数可能引用了另一个源文件中定义的某个符号（如变量或者函数调用等）；

在程序中可能调用了某个库文件中的函数，等等。所有的这些问题，都需要经链接程序的处理方能得以解决。

链接程序的主要工作就是将有关的目标文件彼此相连接，也即将在一个文件中引用的符号同该符号在另外一个文件中的定义连接起来，使得所有的这些目标文件成为一个能够诶操作系统装入执行的统一整体。

（1）静态链接

在这种链接方式下，函数的代码将从其所在地静态链接库中被拷贝到最终的可执行程序中。

（2） 动态链接

在此种方式下，函数的代码被放到称作是动态链接库或共享对象的某个目标文件中。

链接程序此时所作的只是在最终的可执行程序中记录下共享对象的名字以及其它少量

的登记信息。在此可执行文件被执行时，动态链接库的全部内容将被映射到运行时相应

进程的虚地址空间。

 

10.c++变量声明

变量的声明有两种情况：

1、一种是需要建立存储空间的。例如：int a 在声明的时候就已经建立了存储空间。

2、另一种是不需要建立存储空间的。 例如：extern int a 其中变量a是在别的文件中定义的。

 

用static来声明一个变量的作用有二：

(1)对于局部变量用static声明，则是为该变量分配的空间在整个程序的执行期内都始终存在。

(2)外部变量用static来声明，则该变量的作用只限于本文件模块。

 

声明是向编译器介绍名字－－标识符。它告诉编译器“这个函数或变量在某处可找到，它的模样象什么”。

而定义是说：“在这里建立变量”或“在这里建立函数”。它为名字分配存储空间。

 

定义和声明的最重要区别就是：

定义创建对象并为这个对象分配了内存，声明没有分配内存。

 

1.extern告诉编译器变量在其他地方定义了。

extern int i; //声明

int i; //也是定义，未初始化

 

2.如果声明有初始化式，就被当作定义，即使前面加了extern

extern double pi=3.141592654; //定义 

 

3.函数的声明和定义区别比较简单，带有{ }的就是定义，否则就是声明。

extern double max(double d1,double d2); //声明

 

 

 

static作用： http://www.cnblogs.com/stoneJin/archive/2011/09/21/2183313.html

http://www.cnblogs.com/yyxt/p/4912271.html

static 用来控制变量的存储方式和可见性！！！

（1）隐藏。

当我们同时编译多个文件时，所有未加static前缀的全局变量和函数都具有全局可见性。

（2）static的第二个作用是保持变量内容的持久。存储在静态数据区的变量会在程序刚开始运行时就完成初始化，也是唯一的一次初始化。共有两种变量存储在静态存储区：全局变量和static变量，只不过和全局变量比起来，static可以控制变量的可见范围，说到底static还是用来隐藏的。

（3）static的第三个作用是默认初始化为0。其实全局变量也具备这一属性，因为全局变量也存储在静态数据区。在静态数据区，内存中所有的字节默认值都是0x00，某些时候这一特点可以减少程序员的工作量。比如初始化一个稀疏矩阵，我们可以一个一个地把所有元素都置0，然后把不是0的几个元素赋值。如果定义成静态的，就省去了一开始置0的操作。再比如要把一个字符数组当字符串来用，但又觉得每次在字符数组末尾加’\0’太麻烦。如果把字符串定义成静态的，就省去了这个麻烦，因为那里本来就是’\0’。

1. static全局变量与普通的全局变量有什么区别 ?

　　全局变量(外部变量)的说明之前再冠以static 就构成了静态的全局变量。

　　全局变量本身就是静态存储方式， 静态全局变量当然也是静态存储方式。 这两者在存储方式上并无不同。

　　这两者的区别在于全局变量的作用域是整个源程序， 当一个源程序由多个源文件组成时，全局变量在各个源文件中都是有效的。 而静态全局变量则限制了其作用域， 即只在定义该变量的源文件内有效， 在同一源程序的其它源文件中不能使用它。　　

    static全局变量只初使化一次，防止在其他文件单元中被引用; 　

 

2.  static局部变量和普通局部变量有什么区别 ？

 　 把局部变量改变为静态变量后是改变了它的存储方式即改变了它的生存期，直到程序结束时才释放。

　　static局部变量只被初始化一次，下一次依据上一次结果值； 　

 

3.  static函数与普通函数有什么区别？

　　 static函数与普通函数作用域不同,仅在本文件。只在当前源文件中使用的函数应该说明为内部函数(static修饰的函数)，内部函数应该在当前源文件中说明和定义。对于可在当前源文件以外使用的函数，应该在一个头文件中说明，要使用这些函数的源文件要包含这个头文件.

　　static函数在内存中只有一份，普通函数在每个被调用中维持一份拷贝

 

全局变量、文件域的静态变量和类的静态成员变量在main执行之前的静态初始化过程中分配内存并初始化；局部静态变量（一般为函数内的静态变量）在第一次使用时分配内存并初始化。

 

 

静态函数:使某个函数只在一个源文件中有效，不能被其他源文件所用。（与静态全局变量一样）

静态函数的效果：

（1）它允其他源文件建立并使用同名的函数，而不相互冲突。

（2） 声明为静态的函数不能被其他源文件所调用，因为它的名字不能得到。 

 

 

static一个简单的总结：

j告知编译器，将变量存储在程序的静态存储区而不是栈区。

（希望函数中此变量的值保存到下一次调用）

k把变量的可见范围限制在编译单元内，使其成为一个内部连接。

 

对于局部变量，已经是内部连接了，只改变其存储方式——>静态存储

对于全局变量，已经是静态存储了，只改变其连接方式——>内部连接

 

11.请说出static和const关键字尽可能多的作用

static:

1. 修饰普通变量，修改变量的存储区域和生命周期，使变量存储在静态区，在main函数运行前就分配了空间，如果有初始值就用初始值初始化它，如果没有初始值系统用默认值初始化它。

2. 修饰普通函数，表明函数的作用范围，仅在定义该函数的文件内才能使用。在多人开发项目时，为了防止与他人命令函数重名，可以将函数定位为static。

3. 修饰成员变量，修饰成员变量使所有的对象只保存一个该变量，而且不需要生成对象就可以访问该成员。

4. 修饰成员函数，修饰成员函数使得不需要生成对象就可以访问该函数，但是在static函数内不能访问非静态成员。

const:

1. 修饰变量，说明该变量不可以被改变；

2. 修饰指针，分为指向常量的指针和指针常量；

3. 常量引用，经常用于形参类型，即避免了拷贝，又避免了函数对值的修改；

4. 修饰成员函数，说明该成员函数内不能修改成员变量。

 

 

12.char s[]和char *s 的区别