图像处理 掩膜怎么弄

2015-08-30 17:07:49 u011620352 阅读数 6063
电路板是用掩膜法制作而成的,现在电路板表面涂上一层抗腐蚀的材料,然后再进行处理,最后洗去材料就得到了电路。

掩膜法在图像处理中的应用:
可用于分割图像中的特定部分,关键在于怎么取膜。

例子:通过掩膜法分割图像的背景并且换背景色。

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% FileName: frog.m
% description: masking way to change color of background in a image
% Reversion History: no
% Author: greyson
% Date: 2014/04/11
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% parameters
back_threshold = [160 160 190];
back = 125;

% read image
im = imread('E:\frog_1.jpg');

% processing image
mask = ones(size(im,1), size(im,2));

for k = 1:3
mask = mask .* double( im(:,:,k) > back_threshold(k) );
end

figure

for k = 1:3
im(:,:,k) = im(:,:,k) .* (1 - mask) + back * mask;
end

% show images
figure;
imshow(im)

注意:图像的颜色分量有3个,RGB,在去掩膜的时候要主要取得是3个分量的交集,切勿分别取RGB分量的掩膜!

结果:
图像分割——掩膜法 - Greyson - Greyson的博客图像分割——掩膜法 - Greyson - Greyson的博客
  
2019-06-04 10:59:12 weixin_40943549 阅读数 0

传统图像处理部分

图像处理基础知识

彩色图像、灰度图像、二值图像和索引图像区别?

  • 彩色图像:RGB图像。
  • 灰度图像:0-255像素值。二值图像:0和1,用于掩膜图像。
  • 索引图像:在灰度图像中,自定义调色板,自定义输出256种颜色值。

常用的图像空间有哪些?

HSI、HSV、RGB、CMY、CMYK、HSL、HSB、Ycc、XYZ、Lab、YUV色彩空间(颜色模型)

  • RGB颜色空间是算法处理中应用最多的颜色空间。
  • HSI颜色空间,色调(Hue)、色饱和度(Saturation或Chroma)和亮度(Intensity或Brightness)   HSV颜色空间,V(value)明度
  • YUV,(YCrCb):分为三个分量,“Y”表示明亮度(Luminance或Luma),也就是灰度值;而“U”和“V” 表示的则是色度(Chrominance或Chroma),作用是描述影像色彩及饱和度,用于指定像素的颜色。YUV 4:4:4采样,每一个Y对应一组UV分量。YUV 4:2:2采样,每两个Y共用一组UV分量。 YUV 4:2:0采样,每四个Y共用一组UV分量。

图像的像素数与分辨率有什么区别?

  • 像素数为图像实际组成的像素的个数,像素是没有固定宽度和高度的,是一个感光单元。
  • 分辨率的单位为 像素/英寸(1英寸(inch)=2.54厘米(cm)),这里指的不是面积,而是对角线的长度,即dpi、ppi。分辨率也称之为点密度,分辨率越高,看的越细腻。、

视频帧播放速度的单位?

PAL制式是——25fps,NTSC是——30fps。

图像预处理

图像增强:平滑--去噪,梯度--锐化

图像信息提取、检测:颜色、几何(边缘、点)、纹理、局部

叙述Gabor滤波器原理?

          使用一个三角函数(如正弦函数)与一个高斯函数叠加我们就得到了一个Gabor滤波器。Gabor滤波器可以抽取空间局部频度特征,是一种有效的纹理检测工具。

附:图像的空域是指二维坐标系上的操作,频域指的是图像经过傅里叶变换后的频谱。在频率域中,高频分量表示图像中灰度变换比较快的那些地方,比如物体的边缘就是灰度的突然变化,所以物体边缘就是高频分量。而物体内部比较平坦的区域,灰度基本没有变化,对应的就是低频分量。比如低通滤波只让低频分量通过,往往就是使图像模糊,因为边缘信息被去除了。高频对应图像细节,低频对应图像大致轮廓。

椒盐噪声用什么滤波处理比较有效?

椒盐噪声:也称为脉冲噪声。在图像中,它是一种随机出现的白点或者黑点,可能是亮的区域有黑色像素或是在暗的区域有白色像素(或是两者皆有)。滤除椒盐噪声比较有效的方法是对信号进行中值滤波处理。

常用插值方法

  • 最近邻插值:
  • 双线性插值:
  • 立方卷积插值:

常用滤波器

均值滤波:均值滤波是一种线性低通滤波器,均值滤波是取领域像素值的平均作为该像素的新值。

中值滤波:中指滤波是一种非线性的平滑滤波器,中值滤波是将窗口内的所有像素值按大到小排序后,取中间值作为中心像素的新值。

最大最小值滤波:最大最小值滤波是一种比较保守的图像处理手段,与中值滤波类似,首先要排序周围像素和中心像素值,然后将中心像素值与最小和最大像素值比较,如果比最小值小,则替换中心像素为最小值,如果中心像素比最大值大,则替换中心像素为最大值。

高斯滤波:模拟人眼,关注中心区域,有效去除高斯噪声,离中心越远,感受精度越模糊。

机器学习部分

特征算子

常用边缘检测有哪些算子,各有什么特点和优缺点?

Prewitt算子     优点:一阶微分算子,平均滤波,对低噪声的图像有较好的检测效果。缺点:抗噪性差。

Sobel算子       优点:一阶微分算子,加权平均滤波,对低噪声的图像有较好的检测效果。缺点:抗噪性差。

Roberts算子    优点:一种利用局部差分算子寻找边缘的算子,定位比较精确。缺点:对噪声敏感,无法抑制噪声的影响。

Laplacian算子  优点:各向同性,二阶微分,精确定位边缘位置所在。缺点:无法感知边缘强度。只适用于无噪声图象。存在噪声情况下,使用Laplacian算子检测边缘之前需要先进行低通滤波。

Laplacian of Gaussian(LoG)算子:先对图像做高斯滤波,再做Laplacian算子检测。

Canny算子:一个具有滤波,增强,检测的多阶段的优化算子。先利用高斯平滑滤波器来平滑图像以除去噪声,采用一阶偏导的有限差分来计算梯度幅值和方向,然后再进行非极大值抑制。

SIFT/SURF LDA/PCA

SIFT/SURF为了实现不同图像中相同场景的匹配,主要包括4个步骤:

  • 1. 尺度空间的建立(之所以采用尺度空间,是为了应对尺度不变性);
  • 2. 特征点的提取;
  • 3. 利用特征点周围邻域的信息生成特征描述子;
  • 4. 特征点匹配。

SIFT具体步骤实现

1.生成高斯差分金字塔(DOG金字塔),尺度空间构建

  • 通过对原始图像进行尺度变换,获得图像多尺度下的尺度空间表示序列
  • 对这些序列进行尺度空间主轮廓的提取,并以该主轮廓作为一种特征向量,实现边缘、角点检测不同分辨率上的关键点提取等
  • 尺度空间构建的基础是DOG金字塔,DOG金字塔构建的基础是高斯金字塔

2.空间极值点检测(关键点的初步查探)

  •     为了寻找DOG函数的极值点,每一个像素点要和它所有的相邻点比较,看其是否比它的图像域和尺度空间域的相邻点大或者小
  •     在二维图像空间,中心点与它3*3邻域内的8个点做比较,在同一组内的尺度空间上,中心点和上下相邻的两层图像的2*9个点作比较,如此可以保证检测到的关键点在尺度空间和二维图像空间上都是局部极值点。

3.稳定关键点的精确定位

  • DOG值对噪声和边缘比较敏感,所以在第2步的尺度空间中检测到的局部极值点还要经过进一步的筛选,去除不稳定和错误检测出的极值点,另一点就是在构建高斯金字塔过程中采用了下采样的图像,在下采样图像中提取的极值点对应在原始图像中的确切位置,也是要在本步骤中解决的问题。

4.稳定关键点方向信息分配

  • 稳定的极值点是在不同尺度空间下提取的,这保证了关键点的尺度不变性。为关键点分配方向信息所要解决的问题是使得关键点对图像角度和旋转具有不变性。方向的分配是通过求每个极值点的梯度来实现的。
  • 分配给关键点的方向并不直接是关键点的梯度方向,而是按照一种梯度方向直方图的方式给出的。
  • 具体的方法是:计算以关键点为中心的邻域内所有点的梯度方向,当然梯度方向一定是在0~360°范围内,对这些梯度方向归一化到36个方向内,每个方向代表了10°的范围。然后累计落到每个方向内的关键点个数,以此生成梯度方向直方图。

5.关键点描述

  • 对关键点的描述是后续实现匹配的关键步骤,描述其实就是一种以数学方式定义关键的过程。描述子不但包含关键点,也包括关键点周围对其有贡献的邻域点。
  • 描述的思路是:对关键点周围像素区域分块,计算块内梯度直方图,生成具有独特性的向量,这个向量是该区域图像信息的一种抽象表述。
  • 如下图,对于2*2块,每块的所有像素点做高斯加权,每块最终取8个方向,即可以生成2*2*8维度的向量,以这2*2*8维向量作为中心关键点的数学描述。
  • David G.Lowed的实验结果表明:对每个关键点,采用4*4*8共128维向量的描述子进项关键点表征,综合效果最佳:

6.特征点匹配

特征点的匹配是通过计算两组特征点的128维的关键点的欧式距离实现的。欧式距离越小,则相似度越高,当欧式距离小于设定的阈值时,可以判定为匹配成功。

线性判别分析(LDA), 主成分分析(PCA)

        LDA和PCA最终的表现都是解一个矩阵特征值的问题,分类的目标是,使得类别内的点距离越近越好(集中),类别间的点越远越好。LDA的全称是Linear Discriminant Analysis(线性判别分析),是一种supervised learning。

        LDA的原理是,将带上标签的数据(点),通过投影的方法,投影到维度更低的空间中,使得投影后的点,会形成按类别区分,一簇一簇的情况,相同类别的点,将会在投影后的空间中更接近。要说明白LDA,首先得弄明白线性分类器(Linear Classifier):因为LDA是一种线性分类器。对于K-分类的一个分类问题,会有K个线性函数 y = wx+b.

         当满足条件:对于所有的j,都有Yk > Yj,的时候,我们就说x属于类别k。对于每一个分类,都有一个公式去算一个分值,在所有的公式得到的分值中,找一个最大的,就是所属的分类了。

y = wx+b实际上就是一种投影,是将一个高维的点投影到一条高维的直线上,LDA最求的目标是,给出一个标注了类别的数据集,投影到了一条直线之后,能够使得点尽量的按类别区分开
 

       主成分分析(PCA)与LDA有着非常近似的意思,LDA的输入数据是带标签的,而PCA的输入数据是不带标签的,所以PCA是一种unsupervised learning。PCA更像是一个预处理的方法,它可以将原本的数据降低维度,而使得降低了维度的数据之间的方差最大。它的目标是通过某种线性投影,将高维的数据映射到低维的空间中表示,并期望在所投影的维度上数据的方差最大,以此使用较少的数据维度,同时保留住较多的原数据点的特性。

       通俗的理解,如果把所有的点都映射到一起,那么几乎所有的信息(如点和点之间的距离关系)都丢失了,而如果映射后方差尽可能的大,那么数据点则会分散开来,以此来保留更多的信息。可以证明,PCA是丢失原始数据信息最少的一种线性降维方式。(实际上就是最接近原始数据,但是PCA并不试图去探索数据内在结构),与PCA保持数据信息不同,LDA是为了使得降维后的数据点尽可能地容易被区分!

特征点匹配应用问题

如下图所示,请以准确快速实现配准为目标,设计算法,让两图中对应的特征点(至少一部分特征点)配准(即精准地地找出对应点之间对应的坐标关系值)。

参考答案

之前是用角点检测,后来采用SIFT算子,Sift算法的实质是在不同的尺度空间上查找关键点(特征点),计算关键点的大小、方向、尺度信息,利用这些信息组成关键点对特征点进行描述的问题。

  •    1 生成高斯差分金字塔(DOG金字塔),尺度空间构建
  •    2 空间极值点检测(关键点的初步查探)
  •    3 稳定关键点的精确定位
  •    4 稳定关键点方向信息分配
  •    5 关键点描述(128维向量算子)
  •    6 特征点匹配(欧氏距离)
     

极值点邻域筛选

对于一般应用图像中,景物可能存在任意特征(如折线,弧形、亮度极值、色调等),请设计合适的算法,找到图像中可以作为明显特征点的灰度的极值点所在的邻域。以准确快速实现极值点邻域筛选为目标,设计算法。用流程图表达)。

参考答案:也使用shif特性

特征离散化的好处

  1. 增减特征较为方便,易于迭代。
  2. 离散化后运算速度快,存储方便。
  3. 对脏数据的鲁棒性较强。
  4. 离散化一定程度简化了模型,可以防止过拟合。

GMM的基本原理和应用

        高斯混合模型(Gaussian Mixture Model, GMM)将一个事物分解为若干的基于高斯概率密度函数(正态分布曲线)形成的模型。高斯混合模型(GMM,Gaussian mixture model)是建模最为成功的方法之一,同时GMM可以用在监控视频索引与检索。

用于动目标检测中的背景建模。

  • 混合高斯模型使用K(++基本为3到5个++) 个高斯模型来表征图像中各个像素点的特征。
  • 在新一帧图像获得后更新混合高斯模型,用当前图像中的每个像素点与混合高斯模型匹配,如果成功则判定该点为背景点, 否则为前景点。
  • 通观整个高斯模型,他主要是有++方差++和++均值++两个参数决定,,对均值和方差的学习,采取不同的学习机制,将直接影响到模型的稳定性、精确性和收敛性。
  • 由于我们是对运动目标的背景提取建模,因此需要对高斯模型中方差和均值两个参数实时更新。
  • 为提高模型的学习能力,改进方法对均值和方差的更新采用不同的学习率
  • 为提高在繁忙的场景下,大而慢的运动目标的检测效果,引入权值均值的概念,建立背景图像并实时更新,然后结合权值、权值均值和背景图像对像素点进行前景和背景的分类。
     

分类算法

常用的分类器有哪些,并简述其原理?

线性分类器:Logistic回归  y=sigmoid(wx+b )2分类,softmax regression,对于logistic 回归的扩展,为多分类算法,应用梯度下降法找到最优解。

SVM:选定特征, SVM算法输出一个最优化的分隔超平面(分类面)。训练好的模型完全依赖于支持向量。

KNN:K最近邻,判断图像与各个类别的距离。

BPNN:全连接网络,计算量巨大

CNN:卷积神经网络,用神经网络训练模型

迁移学习,利用别人训练好的参数,自定义网络

logistic regression (LR)与线性回归(linear regression)的对比

LR的优化函数为似然函数,经典线性回归的优化函数为最小二乘。

LR将预测范围缩小到了[0,1],而经典线性回归的预测范围为整个实数。

LR与SVM的对比

相同:都是分类模型。都处理二分类。都可以添加正则项。

区别:LR是参数模型,SVM是非参数模型;

          LR采用logistical loss,SVM采用hinge loss;

         SVM之所以称之为支持向量,是因为SVM只考虑了与分类最相关的少数点来学习分类器。

KNN的K是如何选取的?

        K值较小意味着模型会越复杂,容易发生过拟合。K值过大会使模型过于简单,使得预测发生错误。实际使用中K一般取较小的数字。

什么是SVM?

       是一个二分分类器,找寻数据之间间隔最大的线性分类器。其学习策略是使分隔间隔最大化。对于线性可分的数据,SVM构造一个分隔面。对于线性不可分的数据,SVM采用核函数将低维空间的问题映射到了高维空间,从而线性可分。常用核函数有多项式核函数、高斯核函数、线性核函数。为了应对维度爆炸的情形,核函数事先在低维空间上进行计算,再将分类的实际效果展现在高维上。SVM的损失函数叫做Hinge(hɪndʒ) Loss,形式为max(0,1-y*a),y为真实值+-1,a为预测值,介于-1到1之间。

简述BP神经网络

BP(back propagation)神经网络,输入X,通过隐藏节点的非线性变换后,输出信号Y,通过误差分析,来调整隐藏节点的W和b。

AdaBoost的基本原理? 

AdaBoost是一个广泛使用的BOOSTING算法,其中训练集上依次训练弱分类器,每次下一个弱分类器是在训练样本的不同权重集合上训练。权重是由每个样本分类的难度确定的。分类的难度是通过分类器的输出估计的。 

聚类算法 

简述你熟悉的聚类算法并说明其优缺点?

K均值聚类(K-meansClustering)

将输入数据分到K个类中。K均值是通过循环更新类中心的初始估计值来实现的。优势是实现起来很简单,是并行化的。主要缺陷是,类的数目需要提前确定。

主要分三步:

  • 1. 随机选取k个聚类质心点(cluster centroids)
  • 2. 对于每一个样例i,计算其应该属于的类
  • 3. 对于每一个类j,重新计算该类的质心(每个类中所有数的平均值)
  • 1. 重复下面过程直到收敛

层次聚类

        层次聚类(或者叫做凝聚聚类)是另一个简单但是强大的聚类算法。其思想是基于成对距离建立一棵相似度树。该算法首先分组成为两个最近的对象(基于特征向量之间的距离),并且在一棵有着两个对象作为孩子的树中创建一个平均结点。然后在余下的结点中找到一个最近的pair,并且也包含任何平均节点,等等。在每一个结点,两个孩子之间的距离也会被存储。簇然后可以通过遍历这棵树并在距离比某个阈值小以至于决定聚类的大小的结点处停止来被提取出来。

层次聚类有几个优势。比如,树结构可以被用来可视化关系,并且显示簇是如何关联起来的。一个好的特征向量将得到树中好的分离。另一个优势是树可以在不同的簇阈值中被重用,而不需要重新计算树。缺点是需要选择一个阈值如果实际的簇需要的话。

谱聚类

         对于n个元素的相似度矩阵(或者叫affinity matrix, 有时也叫距离矩阵)是一个有着成对相似度分数的n*n矩阵。谱聚类的这个名称是从相似度矩阵构造的矩阵的谱的使用得来。这个矩阵的特征向量被用来降维,然后再聚类。

       谱聚类方法的其中一个优势是唯一的输入就是这个矩阵,并且可以被你可以想到的任何相似度度量构造出来。像K均值和层次聚类这样的方法计算特征向量的平均值,这个限制了特征(或者是描述符)对向量(为了能够计算平均值)。有了谱方法,不再需要任何类型的特征向量,只有“距离”或者“相似度”。

Mean Shift 聚类算法

  • 在未被标记的数据点中随机选择一个点作为中心center;
  • 找出离center距离在bandwidth之内的所有点,记做集合M,认为这些点属于簇c。同时,把这些求内点属于这个类的概率加1,这个参数将用于最后步骤的分类
  •  以center为中心点,计算从center开始到集合M中每个元素的向量,将这些向量相加,得到向量shift。
  • center = center+shift。即center沿着shift的方向移动,移动距离是||shift||。
  •  重复步骤2、3、4,直到shift的大小很小(就是迭代到收敛),记住此时的center。注意,这个迭代过程中遇到的点都应该归类到簇c。
  • 如果收敛时当前簇c的center与其它已经存在的簇c2中心的距离小于阈值,那么把c2和c合并。否则,把c作为新的聚类,增加1类。
  • 重复1、2、3、4、5直到所有的点都被标记访问。
  • 分类:根据每个类,对每个点的访问频率,取访问频率最大的那个类,作为当前点集的所属类。

     简单的说,mean shift就是沿着密度上升的方向寻找同属一个簇的数据点。
 

欧式距离和曼哈顿距离的区别

  • 欧式距离为最常见的2点之间的距离,为2点之间的直线距离。
  • 曼哈顿距离又称为L1距离或者城市区块距离,是两个点的1范数距离。

图像分割
Graph-cut的基本原理和应用?

         Graph cuts是一种十分有用和流行的能量优化算法,在计算机视觉领域普遍应用于前背景分割(Image segmentation)、立体视觉(stereo vision)、抠图(Image matting)等。利用图,将目标和背景进行分割。

图像融合,镶嵌

       已知两幅拼接好的图像,两幅图像在几何关系配准之后,但两图之间存在明显灰度差别跳变,请设计一个算法对图像进行处理,让两幅图之间的灰度看不出跳变,形成自然过渡。(可以不考虑两图之间的黑图部分)?

       答:影像融合是指高分辨率灰度图像和低分辨率彩色图像融合得到具有高分辨率的彩色图像。该算法称之为图像镶嵌。简单的做法可以是寻找两幅影像的镶嵌线,镶嵌线是指两幅影像公共区域区别最小的一条线,可以利用相关系数法判断得到,然后根据镶嵌线上两幅影像的灰度差异对右影像进行反差调整,最后拼接。
https://blog.csdn.net/QiangLi_strong/article/details/80760889

2018-06-21 15:11:26 QiangLi_strong 阅读数 19506

传统图像处理部分

图像处理基础知识

彩色图像、灰度图像、二值图像和索引图像区别?

彩色图像:RGB图像。灰度图像:0-255像素值。二值图像:0和1,用于掩膜图像。

索引图像:在灰度图像中,自定义调色板,自定义输出256种颜色值。

常用的图像空间

HSI、HSV、RGB、CMY、CMYK、HSL、HSB、Ycc、XYZ、Lab、YUV色彩空间(颜色模型)

RGB颜色空间是算法处理中应用最多的颜色空间。

HSI颜色空间,色调(Hue)、色饱和度(Saturation或Chroma)和亮度(Intensity或Brightness)

YUV,分为三个分量,“Y”表示明亮度(Luminance或Luma),也就是灰度值;而“U”和“V” 表示的则是色度(Chrominance或Chroma),作用是描述影像色彩及饱和度,用于指定像素的颜色。YUV 4:4:4采样,每一个Y对应一组UV分量。YUV 4:2:2采样,每两个Y共用一组UV分量。 YUV 4:2:0采样,每四个Y共用一组UV分量。 紧缩格式(packed formats)平面格式(planar formats)。YYYYYYYYUVUV YYYYYYYYUUVV

图像的像素数与分辨率有什么区别?

像素数为图像实际组成的像素的个数,像素是没有固定宽度和高度的,是一个感光单元。

分辨率的单位为 像素/英寸(1英寸(inch)=2.54厘米(cm)),这里指的不是面积,而是对角线的长度,即dpi、ppi。分辨率也称之为点密度,分辨率越高,看的越细腻。

视频帧播放速度的单位

PAL制式是——25fps,NTSC是——30fps。

图像预处理

叙述GABOR滤波器原理?

使用一个三角函数(如正弦函数)与一个高斯函数叠加我们就得到了一个Gabor滤波器。Gabor滤波器可以抽取空间局部频度特征,是一种有效的纹理检测工具。

附:图像的空域是指二维坐标系上的操作,频域指的是图像经过傅里叶变换后的频谱。在频率域中,高频分量表示图像中灰度变换比较快的那些地方,比如物体的边缘就是灰度的突然变化,所以物体边缘就是高频分量。而物体内部比较平坦的区域,灰度基本没有变化,对应的就是低频分量。比如低通滤波只让低频分量通过,往往就是使图像模糊,因为边缘信息被去除了。高频对应图像细节,低频对应图像大致轮廓。

椒盐噪声用什么滤波处理比较有效?

参考:中值滤波与椒盐噪声

椒盐噪声:也称为脉冲噪声:

在图像中,它是一种随机出现的白点或者黑点,可能是亮的区域有黑色像素或是在暗的区域有白色像素(或是两者皆有)。

滤除椒盐噪声比较有效的方法是对信号进行中值滤波处理。

插值

最近邻插值

双线性插值

立方卷积插值

二值图像连通域搜索

matlab中连通区域标记函数bwlabel中的算法,一次遍历图像,并记下每一行(或列)中连续的团(run)和标记的等价对,然后通过等价对对原来的图像进行重新标记。

  1. 创建RUN(团)结构体,包含(纵坐标、横坐标开始、横坐标结束、标记号)
  2. 开始逐行扫描图像,寻找所有的团,将他们放到一个二维数组vector< vector<Stuct> >中,以下为每一行的操作。
    1. 当遇到一个255时,创建一个团的对象,标记纵坐标和横坐标的开始。
    2. 从开始点向右寻找,直到遇到0或者这行结束,则标记为这个团的横坐标结束。
    3. 将该行的RUN push到对应的位置。回到步骤2.1.
  3. 对众多的团进行分析,对团进行标记且得到等价对,创建一个vector< pair<int, int> >用于存放所有的等价对。
    1. 遍历所有相邻行。
    2. 若该行为第一行,则直接进行标记。
    3. 对于相邻行,遍历该行的所有RUN,对于每一个RUN,遍历上一行的所有RUN(超出范围即停止循环)。
      1. 若上一行中没有与该行RUN邻接,则创建新的标记。
      2. 若上一行只有一个与该RUN邻接,则沿用相邻RUN的标记。
      3. 若上一行有多个与该RUN邻接,则使用这多个RUN中最小的标记,并创建多个等价对。
  4. 消除等价对,可使用并查集,使得所有的团都拥有自己的祖先。
    1. 假设标记从0开始,到1000结束。标记对为类似的(0,10).(10,39)。
    2. 创建一个prev[1000]数组,初始化值为-1,记录该标记的上一级领导。初始prev[10]=0,prev[39]=10。初始化所有的等价对。
    3. 遍历所有的等价对,修改每一级的上一级领导为最上层领导。
  5. 修改每个团中的标记为最上层领导的标记。

代码见github

开源库cvBlob中使用的标记算法,它通过定位连通区域的内外轮廓来标记整个图像,这个算法的核心是轮廓的搜索算法

TODO:轮廓跟踪算法

并行计算

Intel指令集中MMX,SSE,SSE2,SSE3和SSE4指的是什么?

MMX(Multi Media eXtension,多媒体扩展指令集)是一些整数并行运算指令。

SSE(Streaming SIMD Extensions,单指令多数据流扩展)是一系列浮点并行运算指令。

SIMD,单指令多数据流,是指用一条指令执行多个计算,比如图像像素一般是BYTE占8位,而计算机中总线是64位,所以理论上可以同时进行8个像素的运算。

并行计算有哪些实现方式?

单指令多数据流SIMD、对称多处理机SMP、大规模并行处理机MPP、工作站机群COW、分布共享存储DSM多处理机。

机器学习面试题链接

机器学习部分

特征算子

常用边缘检测有哪些算子,各有什么特性和优缺点?

  1. Prewitt算子
    优点:一阶微分算子,平均滤波,对低噪声的图像有较好的检测效果。缺点:抗噪性差。
  2. Sobel算子Sobel算子
    优点:一阶微分算子,加权平均滤波,对低噪声的图像有较好的检测效果。缺点:抗噪性差。
  3. Roberts算子Roberts
    优点:一种利用局部差分算子寻找边缘的算子,定位比较精确。缺点:对噪声敏感,无法抑制噪声的影响。
  4. Laplacian算子
    优点:各向同性,二阶微分,精确定位边缘位置所在。缺点:无法感知边缘强度。只适用于无噪声图象。存在噪声情况下,使用Laplacian算子检测边缘之前需要先进行低通滤波。
  5. Laplacian of Gaussian(LoG)算子:先对图像做高斯滤波,再做Laplacian算子检测。
  6. Canny算子:一个具有滤波,增强,检测的多阶段的优化算子。先利用高斯平滑滤波器来平滑图像以除去噪声,采用一阶偏导的有限差分来计算梯度幅值和方向,然后再进行非极大值抑制。

请描述以下任一概念:SIFT/SURF LDA/PCA

SIFT/SURF为了实现不同图像中相同场景的匹配,主要包括三个步骤:
1. 尺度空间的建立;
2. 特征点的提取;
3. 利用特征点周围邻域的信息生成特征描述子;
4. 特征点匹配。

之所以采用尺度空间,是为了应对尺度不变性。

SIFT

  1. 生成高斯差分金字塔(DOG金字塔),尺度空间构建
    • 通过对原始图像进行尺度变换,获得图像多尺度下的尺度空间表示序列
    • 对这些序列进行尺度空间主轮廓的提取,并以该主轮廓作为一种特征向量,实现边缘、角点检测不同分辨率上的关键点提取等
    • 尺度空间构建的基础是DOG金字塔,DOG金字塔构建的基础是高斯金字塔
  2. 空间极值点检测(关键点的初步查探)
    • 为了寻找DOG函数的极值点,每一个像素点要和它所有的相邻点比较,看其是否比它的图像域和尺度空间域的相邻点大或者小
    • 在二维图像空间,中心点与它3*3邻域内的8个点做比较,在同一组内的尺度空间上,中心点和上下相邻的两层图像的2*9个点作比较,如此可以保证检测到的关键点在尺度空间和二维图像空间上都是局部极值点
  3. 稳定关键点的精确定位
    • DOG值对噪声和边缘比较敏感,所以在第2步的尺度空间中检测到的局部极值点还要经过进一步的筛选,去除不稳定和错误检测出的极值点,另一点就是在构建高斯金字塔过程中采用了下采样的图像,在下采样图像中提取的极值点对应在原始图像中的确切位置,也是要在本步骤中解决的问题。
  4. 稳定关键点方向信息分配
    • 稳定的极值点是在不同尺度空间下提取的,这保证了关键点的尺度不变性。为关键点分配方向信息所要解决的问题是使得关键点对图像角度和旋转具有不变性。方向的分配是通过求每个极值点的梯度来实现的。
    • 分配给关键点的方向并不直接是关键点的梯度方向,而是按照一种梯度方向直方图的方式给出的。
    • 具体的方法是:计算以关键点为中心的邻域内所有点的梯度方向,当然梯度方向一定是在0~360°范围内,对这些梯度方向归一化到36个方向内,每个方向代表了10°的范围。然后累计落到每个方向内的关键点个数,以此生成梯度方向直方图。
  5. 关键点描述
    • 对关键点的描述是后续实现匹配的关键步骤,描述其实就是一种以数学方式定义关键的过程。描述子不但包含关键点,也包括关键点周围对其有贡献的邻域点。
    • 描述的思路是:对关键点周围像素区域分块,计算快内梯度直方图,生成具有独特性的向量,这个向量是该区域图像信息的一种抽象表述。
    • 如下图,对于2*2块,每块的所有像素点的荼毒做高斯加权,每块最终取8个方向,即可以生成2*2*8维度的向量,以这2*2*8维向量作为中心关键点的数学描述。
    • David G.Lowed的实验结果表明:对每个关键点,采用4*4*8共128维向量的描述子进项关键点表征,综合效果最佳:
  6. 特征点匹配
    • 特征点的匹配是通过计算两组特征点的128维的关键点的欧式距离实现的。欧式距离越小,则相似度越高,当欧式距离小于设定的阈值时,可以判定为匹配成功。

线性判别分析(LDA), 主成分分析(PCA)

参考参考

LDA和PCA最终的表现都是解一个矩阵特征值的问题,分类的目标是,使得类别内的点距离越近越好(集中),类别间的点越远越好。

LDA的全称是Linear Discriminant Analysis(线性判别分析),是一种supervised learning。

LDA的原理是,将带上标签的数据(点),通过投影的方法,投影到维度更低的空间中,使得投影后的点,会形成按类别区分,一簇一簇的情况,相同类别的点,将会在投影后的空间中更接近。要说明白LDA,首先得弄明白线性分类器(Linear Classifier):因为LDA是一种线性分类器。对于K-分类的一个分类问题,会有K个线性函数 y = wx+b.

当满足条件:对于所有的j,都有Yk > Yj,的时候,我们就说x属于类别k。对于每一个分类,都有一个公式去算一个分值,在所有的公式得到的分值中,找一个最大的,就是所属的分类了。

y = wx+b实际上就是一种投影,是将一个高维的点投影到一条高维的直线上,LDA最求的目标是,给出一个标注了类别的数据集,投影到了一条直线之后,能够使得点尽量的按类别区分开

主成分分析(PCA)与LDA有着非常近似的意思,LDA的输入数据是带标签的,而PCA的输入数据是不带标签的,所以PCA是一种unsupervised learning。

PCA更像是一个预处理的方法,它可以将原本的数据降低维度,而使得降低了维度的数据之间的方差最大

它的目标是通过某种线性投影,将高维的数据映射到低维的空间中表示,并期望在所投影的维度上数据的方差最大,以此使用较少的数据维度,同时保留住较多的原数据点的特性。

通俗的理解,如果把所有的点都映射到一起,那么几乎所有的信息(如点和点之间的距离关系)都丢失了,而如果映射后方差尽可能的大,那么数据点则会分散开来,以此来保留更多的信息。可以证明,PCA是丢失原始数据信息最少的一种线性降维方式。(实际上就是最接近原始数据,但是PCA并不试图去探索数据内在结构)

Linear Discriminant Analysis (也有叫做Fisher Linear Discriminant)是一种有监督的(supervised)线性降维算法。与PCA保持数据信息不同,LDA是为了使得降维后的数据点尽可能地容易被区分!

特征点匹配

如下图所示,请以准确快速实现配准为目标,设计算法,让两图中对应的特征点(至少一部分特征点)配准(即精准地地找出对应点之间对应的坐标关系值)。

参考

之前是用角点检测,后来采用SIFT算子,Sift算法的实质是在不同的尺度空间上查找关键点(特征点),计算关键点的大小、方向、尺度信息,利用这些信息组成关键点对特征点进行描述的问题。

  1. 生成高斯差分金字塔(DOG金字塔),尺度空间构建
  2. 空间极值点检测(关键点的初步查探)
  3. 稳定关键点的精确定位
  4. 稳定关键点方向信息分配
  5. 关键点描述(128维向量算子)
  6. 特征点匹配(欧氏距离)

极值点邻域筛选

对于一般应用图像中,景物可能存在任意特征(如折线,弧形、亮度极值、色调等),请设计合适的算法,找到图像中可以作为明显特征点的灰度的极值点所在的邻域。以准确快速实现极值点邻域筛选为目标,设计算法。用流程图表达)。

也使用SIFT特征

特征离散化的好处

  1. 增减特征较为方便,易于迭代。
  2. 离散化后运算速度快,存储方便。
  3. 对脏数据的鲁棒性较强。
  4. 离散化一定程度简化了模型,可以防止过拟合。

分类算法

常用的分类器有哪些,并简述其原理?

线性分类器:Logistic回归 y=sigmoid(wx+b)

传统方式:特征描述和检测

KNN,K最近邻,判断图像与各个类别的距离

SVM,选定特征, SVM算法输出一个最优化的分隔超平面(分类面)。本科课题:SIFT、k-means、Bag of Words、SVM。映射函数可能为多项式。

BPNN,全连接网络,计算量巨大

CNN,卷积神经网络

迁移学习,利用别人训练好的参数,自定义网络

LR与线性回归的对比

LR的优化函数为似然函数,经典线性回归的优化函数为最小二乘。

LR将预测范围缩小到了[0,1],而经典线性回归的预测范围为整个实数。

LR与SVM的对比

相同:都是分类模型。都处理二分类。都可以添加正则项。

区别:LR是参数模型,SVM是非参数模型;LR采用logistical loss,SVM采用hinge loss;SVM之所以称之为支持向量,是因为SVM只考虑了与分类最相关的少数点来学习分类器。

KNN的K是如何选取的

K值较小意味着模型会越复杂,容易发生过拟合。K值过大会使模型过于简单,使得预测发生错误。实际使用中K一般取较小的数字。

什么是SVM?

参考http://blog.csdn.net/v_july_v/ … 24837

是一个二分分类器,找寻数据之间间隔最大的线性分类器。其学习策略是使分隔间隔最大化。对于线性可分的数据,SVM构造一个分隔面。对于线性不可分的数据,SVM采用核函数将低维空间的问题映射到了高维空间,从而线性可分。常用核函数有多项式核函数、高斯核函数、线性核函数。为了应对维度爆炸的情形,核函数事先在低维空间上进行计算,再将分类的实际效果展现在高维上。

SVM的损失函数叫做Hinge(hɪndʒ) Loss,形式为max(0,1-y*a),y为真实值+-1,a为预测值,介于-1到1之间。

简述BP神经网络

BP(back propagation)神经网络,输入X,通过隐藏节点的非线性变换后,输出信号Y,通过误差分析,来调整隐藏节点的W和b。

AdaBoost的基本原理?

AdaBoost是一个广泛使用的BOOSTING算法,其中训练集上依次训练弱分类器,每次下一个弱分类器是在训练样本的不同权重集合上训练。权重是由每个样本分类的难度确定的。分类的难度是通过分类器的输出估计的。

参考资料

//TODO 详细学习

聚类算法

简述你熟悉的聚类算法并说明其优缺点

K均值聚类(K-meansClustering)

将输入数据分到K个类中。K均值是通过循环更新类中心的初始估计值来实现的。优势是实现起来很简单,是并行化的。主要缺陷是,类的数目需要提前确定。

主要分三步:
1. 随机选取k个聚类质心点(cluster centroids)
2. 对于每一个样例i,计算其应该属于的类
3. 对于每一个类j,重新计算该类的质心
1. 重复下面过程直到收敛

层次聚类

层次聚类(或者叫做凝聚聚类)是另一个简单但是强大的聚类算法。其思想是基于成对距离建立一棵相似度树。该算法首先分组成为两个最近的对象(基于特征向量之间的距离),并且在一棵有着两个对象作为孩子的树中创建一个平均结点。然后在余下的结点中找到一个最近的pair,并且也包含任何平均节点,等等。在每一个结点,两个孩子之间的距离也会被存储。簇然后可以通过遍历这棵树并在距离比某个阈值小以至于决定聚类的大小的结点处停止来被提取出来。

层次聚类有几个优势。比如,树结构可以被用来可视化关系,并且显示簇是如何关联起来的。一个好的特征向量将得到树中好的分离。另一个优势是树可以在不同的簇阈值中被重用,而不需要重新计算树。缺点是需要选择一个阈值如果实际的簇需要的话

谱聚类

对于n个元素的相似度矩阵(或者叫affinity matrix, 有时也叫距离矩阵)是一个有着成对相似度分数的n*n矩阵。谱聚类的这个名称是从相似度矩阵构造的矩阵的谱的使用得来。这个矩阵的特征向量被用来降维,然后再聚类。

谱聚类方法的其中一个优势是唯一的输入就是这个矩阵,并且可以被你可以想到的任何相似度度量构造出来。像K均值和层次聚类这样的方法计算特征向量的平均值,这个限制了特征(或者是描述符)对向量(为了能够计算平均值)。有了谱方法,不再需要任何类型的特征向量,只有“距离”或者“相似度”。

Mean Shift 聚类算法

  1. 在未被标记的数据点中随机选择一个点作为中心center;
  2. 找出离center距离在bandwidth之内的所有点,记做集合M,认为这些点属于簇c。同时,把这些求内点属于这个类的概率加1,这个参数将用于最后步骤的分类
  3. 以center为中心点,计算从center开始到集合M中每个元素的向量,将这些向量相加,得到向量shift。
  4. center = center+shift。即center沿着shift的方向移动,移动距离是||shift||。
  5. 重复步骤2、3、4,直到shift的大小很小(就是迭代到收敛),记住此时的center。注意,这个迭代过程中遇到的点都应该归类到簇c。
  6. 如果收敛时当前簇c的center与其它已经存在的簇c2中心的距离小于阈值,那么把c2和c合并。否则,把c作为新的聚类,增加1类。
  7. 重复1、2、3、4、5直到所有的点都被标记访问。
  8. 分类:根据每个类,对每个点的访问频率,取访问频率最大的那个类,作为当前点集的所属类。

简单的说,mean shift就是沿着密度上升的方向寻找同属一个簇的数据点。

欧式距离和曼哈顿距离的区别

欧式距离为最常见的2点之间的距离,为2点之间的直线距离。

曼哈顿距离又称为L1距离或者城市区块距离,是两个点的1范数距离。

图像分割

Graph-cut的基本原理和应用?

Graph cuts是一种十分有用和流行的能量优化算法,在计算机视觉领域普遍应用于前背景分割(Image segmentation)、立体视觉(stereo vision)、抠图(Image matting)等。

利用图,将目标和背景进行分割。

图像融合,镶嵌

已知两幅拼接好的图像,两幅图像在几何关系配准之后,但两图之间存在明显灰度差别跳变,请设计一个算法对图像进行处理,让两幅图之间的灰度看不出跳变,形成自然过渡。(可以不考虑两图之间的黑图部分)。

影像融合是指高分辨率灰度图像和低分辨率彩色图像融合得到具有高分辨率的彩色图像。该算法称之为图像镶嵌。简单的做法可以是寻找两幅影像的镶嵌线,镶嵌线是指两幅影像公共区域区别最小的一条线,可以利用相关系数法判断得到,然后根据镶嵌线上两幅影像的灰度差异对右影像进行反差调整,最后拼接。

其他模型

Random Forest的随机性表现在哪里。

Bagging方法是ensemble methods中获得用于训练base estimator的数据的重要一环。 正如其名,Bagging方法就是将所有training data放进一个黑色的bag中,黑色意味着我们看不到里面的数据的详细情况,只知道里面有我们的数据集。然后从这个bag中随机抽一部分数据出来用于训练一个base estimator。抽到的数据用完之后我们有两种选择,放回或不放回。

我们可以看到从根节点开始往下会有分支,最终会走向叶子节点,得到分类结果。每一个非叶子节点都是一个特征,上图中共有三维特征。但是决策树的一个劣势就是容易过拟合,下面我们要结合上文提到的bagging技术来中和一下。

img

bagging + decision trees,我们得到了随机森林。将决策树作为base estimator,然后采用bagging技术训练一大堆小决策树,最后将这些小决策树组合起来,这样就得到了一片森林(随机森林)。

(X[1],Y[1])….(X[n],Y[n])是数据集,我们要训练T棵决策树g[1]….g[t]…g[T]。 每次从数据中有放回地随机抽取size-N’的子数据集D[t]用于训练第t棵决策树g[t]。

随机森林的随机性体现在每颗树的训练样本是随机的,树中每个节点的分裂属性集合也是随机选择确定的。有了这2个随机的保证,随机森林就不会产生过拟合的现象了。

GMM的基本原理和应用

高斯混合模型(Gaussian Mixture Model, GMM)将一个事物分解为若干的基于高斯概率密度函数(正态分布曲线)形成的模型。

高斯混合模型(GMM,Gaussian mixture model)是建模最为成功的方法之一,同时GMM可以用在监控视频索引与检索。

用于动目标检测中的背景建模。

  • 混合高斯模型使用K(++基本为3到5个++) 个高斯模型来表征图像中各个像素点的特征。
  • 在新一帧图像获得后更新混合高斯模型,用当前图像中的每个像素点与混合高斯模型匹配,如果成功则判定该点为背景点, 否则为前景点。
  • 通观整个高斯模型,他主要是有++方差++和++均值++两个参数决定,,对均值和方差的学习,采取不同的学习机制,将直接影响到模型的稳定性、精确性和收敛性。
  • 由于我们是对运动目标的背景提取建模,因此需要对高斯模型中方差和均值两个参数实时更新。
  • 为提高模型的学习能力,改进方法对均值和方差的更新采用不同的学习率
  • 为提高在繁忙的场景下,大而慢的运动目标的检测效果,引入权值均值的概念,建立背景图像并实时更新,然后结合权值、权值均值和背景图像对像素点进行前景和背景的分类。

其他理论

监督学习和非监督学习。

  • 监督学习:通过已有的一部分输入数据与输出数据之间的对应关系,生成一个函数,将输入映射到合适的输出,例如分类。
  • 非监督学习:直接对输入数据集进行建模,例如聚类。
  • 半监督学习:综合利用有类标的数据和没有类标的数据,来生成合适的分类函数。

目前最广泛被使用的分类器有人工神经网络、支持向量机、最近邻居法、高斯混合模型、朴素贝叶斯方法、决策树和径向基函数分类。

无监督学习里典型的例子就是聚类了。聚类的目的在于把相似的东西聚在一起,而我们并不关心这一类是什么。因此,一个聚类算法通常只需要知道如何计算相似度就可以开始工作了。

过拟合的解决方法

减小模型复杂度、加大数据、batch normalization、dropout、正则化、early stopping。

谈谈判别式模型和生成式模型?

常见的判别模型有:K近邻、SVM、决策树、感知机、线性判别分析(LDA)、线性回归、传统的神经网络、逻辑斯蒂回归、boosting、条件随机场。通过决策函数来进行判别。

常见的生成模型有:朴素贝叶斯、隐马尔可夫模型、高斯混合模型、文档主题生成模型(LDA)、限制玻尔兹曼机。通过联合概率密度分布函数来进行预测。

L1和L2的区别

  • L1范数为向量中各个元素的绝对值之和,符合拉普拉斯分布,可以使权值稀疏。
  • L2范数为向量中各个元素的平方和的1/2次方,符合高斯分布,可以防止过拟合。
  • Lp范数为向量中各个元素的p次方和的1/p次方。

归一化的好处

归一化加快了梯度下降求解最优解的速度;归一化还可能会提高精度。

归一化的种类

  • 线性归一化。利用max和min进行归一化,如果max和min不稳定,则常用经验值来替代max和min。
  • 标准差归一化。利用所有样本的均值和方差将样本归一化为正态分布。
  • 非线性归一化。比如指数、对数、三角函数等。

归一化和标准化的区别

标准化是依照特征矩阵的列处理数据,其通过求z-score的方法,将样本的特征值转换到同一量纲下。归一化是依照特征矩阵的行处理数据,其目的在于样本向量在点乘运算或其他核函数计算相似性时,拥有统一的标准,也就是说都转化为“单位向量”。

对于深度网络而言,归一化的目的是方便比较,可以加快网络的收敛速度;标准化是将数据利用z-score(均值、方差)的方法转化为符合特定分布的数据,方便进行下一步处理,不为比较。

熵是指样本的随机程度。样本越无序,熵越大, 信息越多。

完成机器学习项目流程

  1. 抽象成数学问题。明确我们可以获得什么样的数据,这个问题是回归还是分类。
  2. 获取数据。增加数据的代表性,防止因数据引起的过拟合。
  3. 特征预处理和特征选择。进行数据清洗,包括归一化、离散化等操作。结合数据和业务的特点来确定需要选取的特征算子。
  4. 训练模型和调优。选择一个模型进行训练,并对超参数进行调节。
  5. 模型诊断。分析模型是否过拟合或者欠拟合,然后进行相应的操作。同时可以进行误差分析,针对不同的问题来优化模型。
  6. 模型融合。将预处理和预测进行统一。
  7. 上线运行。

深度学习部分

潮流

图像检测和分割,增强学习,生成对抗网络,预测学习

基础理论

SGD 中 S(stochastic)代表什么

Stochastic Gradient Descent 随机梯度下降。GD即Full-Batch,SGD即为Mini-Batch。随机性表现在训练数据的shuffle。

Softmax Loss推一下

Sigmoid、Tanh、ReLU比较

Rectified Linear Unit, ReLU

ReLU比Sigmoid、Tanh好的原因

  1. 指数函数运算量大。ReLU节省运算量。
  2. Sigmoid容易引发梯度消失问题,因为Sigmoid函数在两端的导数趋近于0.
  3. ReLU使得一部分神经元死亡,这样可以使得网络变得比较稀疏,缓解了过拟合的发生。

引入非线性激活函数的原因?

若使用线性激活函数,则无论神经网络有多少层,输出都是输入的线性组合。

好的激活函数有以下特点:

  1. 非线性:即导数不是常数。
  2. 几乎处处可微:可微性保证了在优化中梯度的可计算性。
  3. 计算简单。
  4. 非饱和性(saturation):饱和指的是在某些区间梯度接近于零(即梯度消失),使得参数无法继续更新的问题。
  5. 单调性(monotonic):即导数符号不变。
  6. 输出范围有限:有限的输出范围使得网络对于一些比较大的输入也会比较稳定
  7. 接近恒等变换(identity):即约等于x。这样的好处是使得输出的幅值不会随着深度的增加而发生显著的增加
  8. 参数少:大部分激活函数都是没有参数的。
  9. 归一化(normalization):这个是最近才出来的概念,对应的激活函数是SELU。类似于Batch Normalization。

什么造成了梯度消失和梯度膨胀?

深度网络的链式连乘法则,使得反向传播时到达前几层时,权值更新值非常小或非常大。

可以通过ReLU解决一部分。

各大指标

先是混淆矩阵,这是基础。

混淆矩阵

包含四部分的信息:
1. True negative(TN),称为真阴率,表明实际是负样本预测成负样本的样本数
2. False positive(FP),称为假阳率,表明实际是负样本预测成正样本的样本数
3. False negative(FN),称为假阴率,表明实际是正样本预测成负样本的样本数
4. True positive(TP),称为真阳率,表明实际是正样本预测成正样本的样本数

前面有的表示预测正确。

ROC曲线

二分类标签的输出概率需要定义一个阈值p,p值的选取反映了分类器的分类性能。ROC曲线的横轴为FP(将真实负样本预测为了正样本,越低越好),纵轴为TP(将真实正样本预测为正样本,越高越好)

ROC

  • (0,0):假阳率和真阳率都为0,即分类器全部预测成负样本
  • (0,1):假阳率为0,真阳率为1,全部完美预测正确,happy
  • (1,0):假阳率为1,真阳率为0,全部完美预测错误,悲剧
  • (1,1):假阳率和真阳率都为1,即分类器全部预测成正样本
  • TPR=FPR,斜对角线,预测为正样本的结果一半是对的,一半是错的,随机分类

则,若ROC曲线处于对角线之下,则分类性能差于随机分类器。希望该曲线向左上角凸。

AUC指标

AUC(Area under the ROC curve),适用于二元分类问题,AUC实际上就是ROC曲线下的面积。AUC直观地反映了ROC曲线表达的分类能力。

  • AUC = 1,代表完美分类器
  • 0.5 < AUC < 1,优于随机分类器
  • 0 < AUC < 0.5,差于随机分类器

求解步骤:

  1. 获得样本的输出概率和标签值。
  2. 对于不同的从高到低的阈值,计算不同的TP和FP。
  3. 绘制ROC曲线,计算面积。

AUC含义:从所有真实的正样本中取一个数据,判断这个样本是正样本的概率是p1,从所有真实的负样本中取一个数据,判断这个样本是正样本的概率是p2。对于分类器来说p1越大越好,p2越小越好。则p1大于p2的概率称之为AUC。

mAP

计算步骤,参考

  1. 得到所有测试样本的id、输出概率和真实标签值。
  2. 对输出概率进行排序。
  3. 假设有M个recall值,分别计算不同recall下的准确率。
  4. 取M个准确率的平均值。

AP(average precision),

卷积神经网络

图像预处理手段

卷积和相关

相关和卷积的机理相似,但卷积滤波器首先要旋转180度。

卷积算法的时间复杂度

因为在图像的每个位置都要计算一遍卷积核,所以图像像素数为M,卷积核大小为N,则卷积的时间复杂度为O(M*N)。

池化层的作用

  • 保留主要特征的同时进行降维和减少计算量,防止过拟合,提高模型泛化能力。
  • 增加一定的不变性,在池化窗口内。包括平移、旋转、尺度不变性。

CNN特性

CNN的四个特点:局部连接、权值共享、池化操作、多层次结构。

局部连接使网络可以提取数据的局部特征;权值共享降低了网络的训练难度,一个Filter只提取一个特征;池化操作与多层次结构一起,实现了数据的降维,将低层次的局部特征组合成为较高层次的特征,从而对整个图片进行表示。

为什么很多做人脸的Paper会最后加入一个Local Connected Conv?

人脸在不同的区域存在不同的特征(眼睛/鼻子/嘴的分布位置相对固定),当不存在全局的局部特征分布时,Local-Conv更适合特征的提取。

循环神经网络

LSTM为何比RNN好

LSTM可以防止梯度消失或者爆炸

其他网络

生成对抗网络

简称GAN。该网络包含2个部分,一个称之为生成器generator,主要作用是生成图片,并且尽量使得其看上去是来自于训练样本的。另一方是discriminator,其目标是判断输入图片是否属于真实训练样本。

TensorFlow

如何理解TensorFlow的计算图?

TensorFlow分为二部分,一部分是构造部分,用来构造网络;一部分是执行部分,用来执行网络中的计算。

图像相关开放性知识

怎样在一张街拍图像中识别明星的衣着服饰信息?

我们需要把服装与背景、人物、建筑等等元素区别开来,确定是否有衣服以及衣服在什么位置。接下来需要对衣服进行分析,提取出服装的属性、特征等等。最后再根据这些特征,在庞大的数据库里搜索同款或者类似的服装图片。

上衣纯色,裙子花色,怎样做区分?

方差判断,梯度变化。

怎样判断一张广告图片中是否有文字信息?是否用到OCR技术?怎样应用?

场景文字检测与识别,先用CNN等对文字进行定位,然后再使用LSTM、OCR进行文字识别。

给一张二值化图片(包含一个正方形),怎样识别图片中的正方形?如果图片污损严重,怎样识别并恢复?

首先检测轮廓,然后对轮廓进行分析(角点)。

如果图像污损严重,如何识别?

简述图像识别在移动互联网中的应用

人脸识别、识别各类东西、检索各类图像。

图像处理领域相关顶级论文

  • Image and Vision Computing (IVC)
  • Pattern Recognition (PR)
  • ICCV: IEEE International Conference on Computer Vision
  • CVPR: IEEE Conf on Comp Vision and Pattern Recognition
  • NIPS: Neural Information Processing Systems

数学部分

公式

贝叶斯全概率公式题

全概率公式

对任一事件A,若有互不相容的事件Bi(i=1,2,...,n),满足P(Bi)>0,i=1nP(Bi)=1(i=1,2,...,n)i=1nBiA,则事件A的概率可用下式计算:

P(A)=i=1nP(Bi)P(A|Bi)

img

此概率称之为全概率公式。

Bayes公式

利用乘法公式与全概率公式可导出Bayes公式

对任一事件A,若有互不相容的事件Bi(i=1,2,,n),满足P(Bi)>0,i=1nP(Bi)=1(i=1,2,...,n)i=1nBiA,(跟上个公式条件相同)则

P(Bi|A)=P(Bi)P(A|Bi)i=1nP(Bi)P(A|Bi)(i=1,2,,n)

最小二乘拟合的公式推导和代码实现。

最小二乘法通常用于 曲线拟合 (least squares fitting) 。

推导过程

核心思想是最小化损失函数:距离差值的平方((diR)2),若想公式可导,则可以计算平方差的平方(di2R2)2

C/C++部分

基本概念

关键字static的作用是什么?

  1. 在函数体,一个被声明为静态的变量在这一函数被调用过程中维持其值不变。
  2. 在模块内(但在函数体外),一个被声明为静态的变量可以被模块内所用函数访问,但不能被模块外其它函数,它是一个本地的全局变量。
  3. 在模块内,一个被声明为静态的函数只可被这一模块的它函数调用。那就是,这个函数被限制在声明它的模块的本地范围内使用。

简述C,C++程序编译的内存分配情况?

C,C++中内存分配方式可以分为三种:

  1. 从静态存储区域分配:内存在程序编译时就已经分配好,这块内存在程序的整个运行期间都存在。速度快,不容易出错,因有系统自行管理。它主要存放静态数据、全局数据和常量。会默认初始化,其他两个不会自动初始化。
  2. 在栈上分配:在执行函数时,函数内局部变量的存储单元都在栈上创建,函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中,效率很高,但是分配的内存容量有限。
  3. 从堆上分配:即运态内存分配。程序在运行时候用malloc或new申请任意大小的内存,程序员自己负责在何进用free 和delete释放内存。

一个C、C++程序编译时内存分为5大存储区:堆区、栈区、全局区、文字常量区和程序代码区。

new 和 malloc的区别

  1. malloc/free是C的标准库函数,new/delete是C++的运算符。它们都可用于申请动态内存和释放内存。
  2. 当使用一些非内置数据类型的对象时,maloc/free不能自动执行构造函数和析构函数。这是因为malloc/free是库函数,不在编译器控制下。

图的遍历

深度搜索DFS

递归写法

  1. 定义一个visited数组。
  2. 访问当前节点,输出该节点。
  3. 循环遍历该节点的相邻的,未被访问过的节点。
    1. 递归第二步。

非递归写法

  1. 定义一个栈和一个visited数组。
  2. 将初始节点入栈。开始循环,直道栈空。循环如下:

广度搜索BFS

设置队列

  1. 定义一个队列Queue和visited数组。
  2. 将开头节点入队。
  3. 开始循环
    1. 出队,访问该节点
    2. 遍历该节点的相邻的未被访问过的节点,入队

hash 冲突及解决办法

键字值不同的元素可能会映象到哈希表的同一地址上就会发生哈希冲突。解决办法:

  1. 开放定址法。按照一定的方法进行顺延。
  2. 再哈希法。同时构造多个不同的哈希函数。
  3. 链地址法。数组后的每个元素后添加单链表。

红黑树的特征

具有二叉查找树的所有特征。二叉查找树查找的效率最坏为O(n),红黑树通过颜色着色的方法将最坏降低到平均水平。

  1. 每个结点要么是红的要么是黑的。
  2. 根节点是黑的。
  3. 每个叶结点(树尾端的NIL指针或者NULL结点)都是黑的。
  4. 如果一个节点是红色,他的两个孩子都是黑色。
  5. 对于任意结点而言,其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

是红黑树的这5条性质,使一棵n个结点的红黑树始终保持了logn的高度,从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”

其他编程

嵌入式系统总是用户对变量或寄存器进行位操作。给定一个整型变量a,写两段代码,第一个设置a的bit3,第二消除a的 bit 3。在以上两个操作中,要保持其它位不变.

#include <iostream>
#include <bitset>
using namespace std;

#define BIT3 (0x1<<3)
void set_bit3(unsigned &a)
{
    a |= BIT3;
}
void clear_bits(unsigned &a)
{
    a &= ~BIT3;
}

int main()
{
    unsigned a = UINT_MAX;
    clear_bits(a);
    cout << (bitset<32>)a << endl;
    set_bit3(a);
    cout << (bitset<32>)a << endl;
    return 0;
}

行列递增矩阵的查找

解法一、分治法

因为矩阵的行和列都是递增的,所以整个矩阵的对角线上的数字也是递增的,故我们可以在对角线上进行二分查找,如果要找的数是6介于对角线上相邻的两个数4、10,可以排除掉左上和右下的两个矩形,而在左下和右上的两个矩形继续递归查找

解法二、定位法

首先直接定位到最右上角的元素,比要找的数大就往左走,比要找数的小就往下走,直到找到要找的数字为止,走不动,说明这个数不存在。这个方法的时间复杂度O(m+n)。代码如下:

#include <iostream>
#include <vector>
using namespace std;

bool YoungMatrix(vector< vector<int> > mat, int target){
    int y = 0, x = mat[y].size() - 1;
    int var = mat[y][x];
    while (true) {
        if (var == target){
            printf("Mat[%d][%d]=%d\n", y, x, target);
            return true;
        }
        else if (var < target && y < mat.size() - 1){
            var = mat[++y][x];
        }
        else if (var > target && x > 0){
            var = mat[y][--x];
        }
        else{
            return false;
        }
    }
}

int main(){
    vector<vector<int> > matrix(20);
    for (int i = 0; i < 20; i++){
        for (int j = 0; j < 20; j++) {
            matrix[i].push_back(i+j);
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
    cout << YoungMatrix(matrix, 38) << endl;
    return 0;
}

从1到500的500个数,第一次删除奇数位上的所有数,第二次删除剩下来的奇数位,以此类推,最后剩下的唯一一位数是什么?

就是当1~n,2^i

给出了一个n*n的矩形,编程求从左上角到右下角的路径数(n > =2),限制只能向右或向下移动,不能回退。例如当n=2时,有6条路径。

从左上角到右下角总共要走2n步,其中横向要走n步,所以总共就是C2nn次。

给出一棵二叉树的前序和中序遍历,输出后续遍历的结果。

已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为多少?

#include <iostream>
#include <string>
using namespace std;

string Subsequent(string pre, string mid) {
    if (pre.size() != mid.size() || pre.empty()) return "";
    char root = pre[0];
    int rootIndex = mid.find(root);
    string leftPre = pre.substr(1, rootIndex);
    string leftMid = mid.substr(0, rootIndex);
    string rightPre = pre.substr(rootIndex + 1);
    string rightMid = mid.substr(rootIndex + 1);

    string res;
    res += Subsequent(leftPre, leftMid);
    res += Subsequent(rightPre, rightMid);
    res += root;
    return res;
}

int main(){
    string pre = "ABDEGCFH";
    string mid = "DBGEACHF";
    cout << Subsequent(pre, mid) << endl;
    return 0;
}

自定义实现字符串转为整数的算法,例如把“123456”转成整数123456.(输入中可能存在符号,和数字)

代码见github

字符串最长公共子序列

动态规划推导式

img

代码见github

字符串最长公共子串

与上文区别是不等时的处理方式,和最后是整个矩阵中寻找最大值。

代码见github

请实现一个函数:最长顺子。输入很多个整数(1<=数值<=13),返回其中可能组成的最长的一个顺子(顺子中数的个数代表顺的长度); 其中数字1也可以代表14;

直方图

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> LongestShunZi(vector<int> input) {
    // 统计直方图
    vector<int> hist;
    hist.resize(15);
    for (int i = 0; i < input.size(); i++)
        if (input[i] > 0 && input[i] < 15)
            hist[input[i]] ++;
    hist[14] = hist[1];
    //最大牌数
    int maxCount = 0;
    for (int i = 1; i < 15; i++)
        if (hist[i] > maxCount)
            maxCount = hist[i];
    //求结果
    int resLen = 0;
    int resCount = 0;
    int resEnd = 0;
    for (int i = 1; i <= maxCount; i++)
    {
        int len = 0;
        int longestLen = 0;
        int longestEnd = 1;
        for (int j = 1; j < 15; j++) {
            if (hist[j] >= i) {
                len++;
                if (len > longestLen) {
                    longestLen = len;
                    longestEnd = j;
                }
            }
            else {
                len = 0;
            }
        }
        if (longestLen == 14 && 2 * i > hist[1]) longestLen--;
        if (longestLen * i > resLen * resCount) {
            resLen = longestLen;
            resCount = i;
            resEnd = longestEnd;
        }
    }

    vector<int> res;
    for (int i = resEnd - resLen + 1; i <= resEnd; i++)
        for (int j = 0; j < resCount; j++)
            res.push_back(i);
    return res;
}

int main() {
    int arr[] = { 1, 5, 2, 3, 4, 4, 5, 9, 6, 7, 2, 3, 3, 4 };
    vector<int> v(arr, arr+sizeof(arr)/sizeof(int));
    vector<int> res = LongestShunZi(v);
    for (int i = 0; i < res.size(); i++) cout << res[i] << " ";
    cout << endl;
    return 0;
}

对一批编号为1-100,全部开关朝上(开)的亮灯进行如下操作

对一批编号为1-100,全部开关朝上(开)的亮灯进行如下操作:凡是编号为1的倍数的灯反方向拨一次开关;凡是编号为2的倍数的灯反方向又拨一次开关;编号为3的倍数的灯反方向又拨一次开关……凡是编号为100的倍数的灯反方向拨一次开关。编写程序,模拟此过程,最后打印出所熄灭灯的编号。

#include <iostream>
using namespace std;

int main() {
    bool arr[101];
    memset(arr, 0, 101);

    for (int i = 2; i <= 100; i++) {
        for (int j = 1; j <= 100; j++) {
            if (j % i == 0) {
                arr[j] = !arr[j];
            }
        }
    }
    for (int i = 1; i <= 100; i++) {
        if (!arr[i])
            cout << i << endl;
    }
    return 0;
}
1
4
9
16
25
36
49
64
81
100

一个数的约数个数为奇数。所有的数都包含1和自己,平方数的约数肯定是奇数个。

实现个函数 unsigned int convect(char* pstr)

实现个函数 unsigned int convect(char* pstr)。其中pstr是十六进制数的字符串。函数convectpstr转换成数字返回(比如:字符串’1A’,将返回数值26.注意,pstr[0]是’1’)。pstr中只有数字字符0到9、A到F。不得借助其它的系统函数调用。

#include <iostream>
using namespace std;

unsigned int convect(char* pstr) {
    char *p = pstr;
    unsigned long long res = 1;
    unsigned long long maxInt = (res << 32) - 1;
    res = 0;
    while (*p != '\0') {
        if (*p >= '0' && *p <= '9') {
            res = res * 16 + *p - '0';
        }
        else if (*p >= 'A' && *p <= 'F') {
            res = res * 16 + *p - 'A' + 10;
        }
        else return 0;
        p++;
    }
    if (res > maxInt) return 0;
    return res;
}

int main() {
    cout << convect((char*)"1A") << endl;
    cout << convect((char*)"FFFFFFFF") << endl;
    cout << convect((char*)"FFFFFFFFF") << endl;
    return 0;
}

实现一个函数unsigned int counter(char* pstr)

实现一个函数unsigned int counter(char* pstr)。函数将打印出匹配的括号对。比如:字符串”a(bc(d)ef(12)g)”就存在3对匹配的括号对,分别是:
1. 位置4上的(与位置6上的)匹配。打印4 6即可。
1. 位置9上的(与位置12上的)匹配。打印9 12即可。
1. 位置1上的(与位置14上的)匹配。打印1 14即可。

软件编程部分

设计

给你一个模块要求,你要做出这个模块,那么你的做出该模块的思路和步骤是什么?

明确这个模块的功能,明确其输入以及输出。

尽量去除与其他模块的耦合关系,确保独立性。

我会首先编写输入和输出的接口函数,然后由粗到精,逐步实现细节算法。

同时还需要编写模块的测试代码,保证交付的可靠性。

Matlab编程

Matlab 中读、写及显示一幅图像的命令各是什么?

imread(), imwrite(), imshow()

Matlab 与VC++混合编程有哪几种方式?

Matlab引擎方式(Matlab后台程序为服务器,VC前端为客户端,C/S结构)、Matlab编译器(将Matlab源代码编译为C++可以调用的库文件)及COM组件(Matlab生成COM组件,VC调用)

Matlab运算中 .** 的区别?

.*表示矩阵元素分别相乘,要求两个矩阵具有相同的shape。*表示矩阵相乘。

逻辑推理部分

智力题

药丸问题

有四人装药丸的罐子,每个药丸都有一定的重量,被污染的药丸是没被污染的重量+1.只称量一次,如何判断哪个罐子的药被污染了?

答:在四个罐子里面分别取1、2、3、4颗药丸,然后进行称量。如果称量结果比实际(污染前)重了n,就是第n罐被污染了。 (因为每加一颗被污染的药丸就增加1所以增加n就是增加n颗就是在第n个罐子里拿的)

帽子黑白问题

一群人开舞会,每人头上都戴着一顶帽子。帽子只有黑白两种,黑的至少有一顶。每个人都能看到其他人帽子的颜色,却看不到自己的。主持人先让大家看看别人头上戴的是什么帽子,然后关灯,如果有人认为自己戴的是黑帽子,就打自己一个耳光。第一次关灯,没有声音。于是再开灯,大家再看一遍,关灯时仍然鸦雀无声。一直到第三次关灯,才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子?

解:假如只有一个人戴黑帽子,那他看到所有人都戴白帽,在第一次关灯时就应自打耳光,所以应该不止一个人戴黑帽子;如果有两顶黑帽子,第一次两人都只看到对方头上的黑帽子,不敢确定自己的颜色,但到第二次关灯,这两人应该明白,如果自己戴着白帽,那对方早在上一次就应打耳光了,因此自己戴的也是黑帽子,于是也会有耳光声响起;可事实是第三次才响起了耳光声,说明全场不止两顶黑帽,依此类推,应该是关了几次灯,有几顶黑帽。

金条问题

让工人为你工作7天,给工人的回报是一根金条。金条平分成相连的7段,你必须在每天结束时给他们一段金条,如果只许你两次把金条弄断,你如何给你的工人付费?

答:分成1、2、4段。利用1,2,4可以组合成1,2,3,4,5,6,7

拆字游戏

下面玩一个拆字游戏,所有字母的顺序都被打乱。你要判断这个字是什么。假设这个被拆开的字由5个字母组成:
1. 共有多少种可能的组合方式?
2. 如果我们知道是哪5个字母,那会怎么样?
3. 找出一种解决这个问题的方法。

个人解答:
1. A55=54321=120
1. 会依靠英文字母的规则等大致弄几种可能性出来。
1. 将弄出来的可能性的单词进行查找。

为什么下水道的盖子是圆的?

解:很大程度上取决于下水道的形状,一般为了使得各个方向的管子都可以接入到下水道中,所以下水道设计成了圆柱形,所以盖子相应的也是圆形。且圆形比较省材料,便于运输。

请估算一下CNTOWER电视塔的质量

首先在纸上画出了CNTOWER的草图,然后快速估算支架和各柱的高度,以及球的半径,算出各部分体积,然后和各部分密度运算,最后相加得出一个结果。

2018-07-15 10:34:34 ywxk1314 阅读数 2206

这里讨论利用输入图像中像素的小邻域来产生输出图像的方法,在信号处理中这种方法称为滤波(filtering)。其中,最常用的是线性滤波:输出像素是输入邻域像素的加权和。

 

1.相关算子(Correlation Operator)

       定义:image,  即image ,其中h称为相关核(Kernel).

        

  步骤:

        1)滑动核,使其中心位于输入图像g的(i,j)像素上

        2)利用上式求和,得到输出图像的(i,j)像素值

        3)充分上面操纵,直到求出输出图像的所有像素值

 

  例:

A = [17  24   1   8  15            h = [8   1   6
     23   5   7  14  16                     3   5   7
      4   6  13  20  22                     4   9   2]
     10  12  19  21   3           
     11  18  25   2   9]

计算输出图像的(2,4)元素=image

image

Matlab 函数:imfilter(A,h)

 

2.卷积算子(Convolution)

定义:image image ,其中

   步骤:

        1)将核围绕中心旋转180度

        2)滑动核,使其中心位于输入图像g的(i,j)像素上

        3)利用上式求和,得到输出图像的(i,j)像素值

        4)充分上面操纵,直到求出输出图像的所有像素值

       例:计算输出图像的(2,4)元素=image

       image

Matlab 函数:Matlab 函数:imfilter(A,h,'conv')% imfilter默认是相关算子,因此当进行卷积计算时需要传入参数'conv'

3.边缘效应

当对图像边缘的进行滤波时,核的一部分会位于图像边缘外面。

image

常用的策略包括:

1)使用常数填充:imfilter默认用0填充,这会造成处理后的图像边缘是黑色的。

2)复制边缘像素:I3 = imfilter(I,h,'replicate');

image

   

4.常用滤波

fspecial函数可以生成几种定义好的滤波器的相关算子的核。

例:unsharp masking 滤波

1
2
3
4
5
I = imread('moon.tif');
h = fspecial('unsharp');
I2 = imfilter(I,h);
imshow(I), title('Original Image')
figure, imshow(I2), title('Filtered Image')
 
 

图像处理-线性滤波-2 图像微分(1、2阶导数和拉普拉斯算子)

更复杂些的滤波算子一般是先利用高斯滤波来平滑,然后计算其1阶和2阶微分。由于它们滤除高频和低频,因此称为带通滤波器(band-pass filters)。

在介绍具体的带通滤波器前,先介绍必备的图像微分知识。

1 一阶导数

连续函数,其微分可表达为image ,或image                         (1.1)

对于离散情况(图像),其导数必须用差分方差来近似,有

                                   image,前向差分 forward differencing                  (1.2)

                                   image ,中心差分 central differencing                     (1.3)

1)前向差分的Matlab实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function dimg = mipforwarddiff(img,direction)
% MIPFORWARDDIFF     Finite difference calculations 
%
%   DIMG = MIPFORWARDDIFF(IMG,DIRECTION)
%
%  Calculates the forward-difference for a given direction
%  IMG       : input image
%  DIRECTION : 'dx' or 'dy'
%  DIMG      : resultant image
%
%   See also MIPCENTRALDIFF MIPBACKWARDDIFF MIPSECONDDERIV
%   MIPSECONDPARTIALDERIV
  
%   Omer Demirkaya, Musa Asyali, Prasana Shaoo, ... 9/1/06
%   Medical Image Processing Toolbox
  
imgPad = padarray(img,[1 1],'symmetric','both');%将原图像的边界扩展
[row,col] = size(imgPad);
dimg = zeros(row,col);
switch (direction)   
case 'dx',
   dimg(:,1:col-1) = imgPad(:,2:col)-imgPad(:,1:col-1);%x方向差分计算,
case 'dy',
   dimg(1:row-1,:) = imgPad(2:row,:)-imgPad(1:row-1,:); 
otherwise, disp('Direction is unknown');
end;
dimg = dimg(2:end-1,2:end-1);

2)中心差分的Matlab实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function dimg = mipcentraldiff(img,direction)
% MIPCENTRALDIFF     Finite difference calculations 
%
%   DIMG = MIPCENTRALDIFF(IMG,DIRECTION)
%
%  Calculates the central-difference for a given direction
%  IMG       : input image
%  DIRECTION : 'dx' or 'dy'
%  DIMG      : resultant image
%
%   See also MIPFORWARDDIFF MIPBACKWARDDIFF MIPSECONDDERIV
%   MIPSECONDPARTIALDERIV
  
%   Omer Demirkaya, Musa Asyali, Prasana Shaoo, ... 9/1/06
%   Medical Image Processing Toolbox
  
img = padarray(img,[1 1],'symmetric','both');
[row,col] = size(img);
dimg = zeros(row,col);
switch (direction)
    case 'dx',
        dimg(:,2:col-1) = (img(:,3:col)-img(:,1:col-2))/2;
    case 'dy',
        dimg(2:row-1,:) = (img(3:row,:)-img(1:row-2,:))/2;
    otherwise,
        disp('Direction is unknown');
end
dimg = dimg(2:end-1,2:end-1);
1
  

实例:技术图像x方向导数

1
2
I = imread('coins.png'); figure; imshow(I);
Id = mipforwarddiff(I,'dx'); figure, imshow(Id);

      image image

    原图像                                                   x方向1阶导数

 

2 图像梯度(Image Gradient)

图像I的梯度定义为image  ,其幅值为image 。出于计算性能考虑,幅值也可用image 来近似。

Matlab函数

1)gradient:梯度计算

2)quiver:以箭头形状绘制梯度。注意放大下面最右侧图可看到箭头,由于这里计算横竖两个方向的梯度,因此箭头方向都是水平或垂直的。

实例:仍采用上面的原始图像

1
2
3
4
5
I = double(imread('coins.png'));
[dx,dy]=gradient(I);
magnitudeI=sqrt(dx.^2+dy.^2);
figure;imagesc(magnitudeI);colormap(gray);%梯度幅值
hold on;quiver(dx,dy);%叠加梯度方向

        image image

                         梯度幅值                                   梯度幅值+梯度方向

 

3 二阶导数

对于一维函数,其二阶导数image ,即image 。它的差分函数为

                                 image                  (3.1)

 

3.1 普拉斯算子(laplacian operator)

3.1.2 概念

拉普拉斯算子是n维欧式空间的一个二阶微分算子。它定义为两个梯度向量算子的内积

                          image       (3.2)

其在二维空间上的公式为:    image                (3.3)

 

对于1维离散情况,其二阶导数变为二阶差分

1)首先,其一阶差分为image

2)因此,二阶差分为

          image

3)因此,1维拉普拉斯运算可以通过1维卷积核image 实现

 

对于2维离散情况(图像),拉普拉斯算子是2个维上二阶差分的和(见式3.3),其公式为:

image   (3.4)

上式对应的卷积核为

                       image

常用的拉普拉斯核有:

                      image

3.1.2 应用

拉普拉斯算子会突出像素值快速变化的区域,因此常用于边缘检测。

 

 

Matlab里有两个函数

1)del2

计算公式:image image  

2)fspecial:图像处理中一般利用Matlab函数fspecial

h = fspecial('laplacian', alpha) returns a 3-by-3 filter approximating the shape of the two-dimensional Laplacian operator.
The parameter alpha controls the shape of the Laplacian and must be in the range 0.0 to 1.0. The default value for alpha is 0.2.

 

3.1.3 资源

http://fourier.eng.hmc.edu/e161/lectures/gradient/node8.html (非常清晰的Laplacian Operator介绍,本文的主要参考)

http://homepages.inf.ed.ac.uk/rbf/HIPR2/log.htm

 

 
 
 
 

sift算法

 

尺度不变特征转换(Scale-invariant feature transform 或 SIFT)是一种电脑视觉的算法用来侦测与描述影像中的局部性特征,它在空间尺度中寻找极值点,并提取出其位置、尺度、旋转不变量,此算法由 David Lowe 在1999年所发表,2004年完善总结。

Sift算法就是用不同尺度(标准差)的高斯函数对图像进行平滑,然后比较平滑后图像的差别,
差别大的像素就是特征明显的点。

sift可以同时处理亮度,平移,旋转,尺度的变化,利用特征点来提取特征描述符,最后在特征描述符之间寻找匹配

 

五个步骤

1构建尺度空间,检测极值点,获得尺度不变性

2特征点过滤并进行经确定位,剔除不稳定的特征点

3 在特征点处提取特征描述符,为特征点分配方向直

4声称特征描述子,利用特征描述符寻找匹配点

5计算变换参数

当2幅图像的sift特征向量生成以后,下一步就可以采用关键点特征向量的欧式距离来作为2幅图像中关键点的相似性判定量度

 

尺度空间:

尺度就是受delta这个参数控制的表示

而不同的L(x,y,delta)就构成了尺度空间,实际上具体计算的时候即使连续的高斯函数,都要被离散为矩阵来和数字图像进行卷积操作

L(x,y,delta)=G(x,y,e)*i(x,y)

尺度空间=原始图像(卷积)一个可变尺度的2维高斯函数G(x,y,e)

 

G(x,y,e) = [1/2*pi*e^2] * exp[ -(x^2 + y^2)/2e^2] 


为了更有效的在尺度空间检测到稳定的关键点,提出了高斯差分尺度空间,利用不同尺度的高斯差分核与原始图像i(x,y)卷积生成

D(x,y,e)=(G(x,y,ke)-G(x,y,e))*i(x,y)

=L(x,y,ke)-L(x,y,e)

(为避免遍历每个像素点)

 

高斯卷积:

在组建一组尺度空间后,再组建下一组尺度空间,对上一组尺度空间的最后一幅图像进行二分之一采样,得到下一组尺度空间的第一幅图像,然后进行像建立第一组尺度空间那样的操作,得到第二组尺度空间,公式定义为
         L(x,y,e) = G(x,y,e)*I(x,y)

    图像金字塔的构建:图像金字塔共O组,每组有S层,下一组的图像由上一组图像降采样得到、

高斯差分

    在尺度空间建立完毕后,为了能够找到稳定的关键点,采用高斯差分的方法来检测那些在局部位置的极值点,即采用俩个相邻的尺度中的图像相减,即公式定义为:
        D(x,y,e) = ((G(x,y,ke) - G(x,y,e)) * I(x,y) 
                 = L(x,y,ke) - L(x,y,e)
 咱们再来具体阐述下构造D(x,y,e)的详细步骤:
    1、首先采用不同尺度因子的高斯核对图像进行卷积以得到图像的不同尺度空间,将这一组图像作为金子塔图像的第一层。
    2、接着对第一层图像中的2倍尺度图像(相对于该层第一幅图像的2倍尺度)以2倍像素距离进行下采样来得到金子塔图像的第二层中的第一幅图像,对该图像采用不同尺度因子的高斯核进行卷积,以获得金字塔图像中第二层的一组图像。
    3、再以金字塔图像中第二层中的2倍尺度图像(相对于该层第一幅图像的2倍尺度)以2倍像素距离进行下采样来得到金字塔图像的第三层中的第一幅图像,对该图像采用不同尺度因子的高斯核进行卷积,以获得金字塔图像中第三层的一组图像。这样依次类推,从而获得了金字塔图像的每一层中的一组图像,
 4、对上图得到的每一层相邻的高斯图像相减,就得到了高斯差分图像,如下述第一幅图所示。下述第二幅图中的右列显示了将每组中相邻图像相减所生成的高斯差分图像的结果,限于篇幅,图中只给出了第一层和第二层高斯差分图像的计算
sift算法
 

 

图像处理之卷积概念

 

我们来看一下一维卷积的概念.
连续空间的卷积定义是 f(x)与g(x)的卷积是 f(t-x)g(x) 在t从负无穷到正无穷的积分值.t-x要在f(x)定义域内,所以看上去很大的积分实际上还是在一定范围的.
实际的过程就是f(x) 先做一个Y轴的反转,然后再沿X轴平移t就是f(t-x),然后再把g(x)拿来,两者乘积的值再积分.想象一下如果g(x)或者f(x)是个单位的阶越函数. 那么就是f(t-x)与g(x)相交部分的面积.这就是卷积了.
把积分符号换成求和就是离散空间的卷积定义了.

 

么在图像中卷积卷积地是什么意思呢,就是图像f(x),模板g(x),然后将模版g(x)在模版中移动,每到一个位置,就把f(x)与g(x)的定义域相交的元素进行乘积并且求和,得出新的图像一点,就是被卷积后的图像. 模版又称为卷积核.卷积核做一个矩阵的形状.


卷积定义上是线性系统分析经常用到的.线性系统就是一个系统的输入和输出的关系是线性关系.就是说整个系统可以分解成N多的无关独立变化,整个系统就是这些变化的累加.
如 x1->y1, x2->y2; 那么A*x1 + B*x2 -> A*y1 + B*y2 这就是线性系统. 表示一个线性系统可以用积分的形式 如 Y = Sf(t,x)g(x)dt S表示积分符号,就是f(t,x)表示的是A B之类的线性系数.
看上去很像卷积呀,,对如果f(t,x) = F(t-x) 不就是了吗.从f(t,x)变成F(t-x)实际上是说明f(t,x)是个线性移不变,就是说 变量的差不变化的时候,那么函数的值不变化. 实际上说明一个事情就是说线性移不变系统的输出可以通过输入和表示系统线性特征的函数卷积得到.

 

http://dept.wyu.edu.cn/dip/DIPPPT2005/����������ϵͳ.ppt


 
 
 
 
 
谈起卷积分当然要先说说冲击函数—-这个倒立的小蝌蚪,卷积其实就是为它诞生的。”冲击函数”是狄拉克为了解决一些瞬间作用的物理现象而提出的符号。
古人曰:”说一堆大道理不如举一个好例子”,冲量这一物理现象很能说明”冲击函数”。在t时间内对一物体作用F的力,我们可以让作用时间t很小,作用力F很大,但让Ft的乘积不变,即冲量不变。于是在用t做横坐标、F做纵坐标的坐标系中,就如同一个面积不变的长方形,底边被挤的窄窄的,高度被挤的高高的,在数学中它可以被挤到无限高,但即使它无限瘦、无限高、但它仍然保持面积不变(它没有被挤没!),为了证实它的存在,可以对它进行积分,积分就是求面积嘛!于是”卷积” 这个数学怪物就这样诞生了。说它是数学怪物是因为追求完美的数学家始终在头脑中转不过来弯,一个能瘦到无限小的家伙,竟能在积分中占有一席之地,必须将这个细高挑清除数学界。但物理学家、工程师们确非常喜欢它,因为它解决了很多当时数学家解决不了的实际问题。最终追求完美的数学家终于想通了,数学是来源于实际的,并最终服务于实际才是真。于是,他们为它量身定做了一套运作规律。于是,妈呀!你我都感觉眩晕的卷积分产生了。
例子:
有一个七品县令,喜欢用打板子来惩戒那些市井无赖,而且有个惯例:如果没犯大罪,只打一板,释放回家,以示爱民如子。
有一个无赖,想出人头地却没啥指望,心想:既然扬不了善名,出恶名也成啊。怎么出恶名?炒作呗!怎么炒作?找名人呀!他自然想到了他的行政长官——县令。
无赖于是光天化日之下,站在县衙门前撒了一泡尿,后果是可想而知地,自然被请进大堂挨了一板子,然后昂首挺胸回家,躺了一天,嘿!身上啥事也没有!第二天如法炮制,全然不顾行政长管的仁慈和衙门的体面,第三天、第四天……每天去县衙门领一个板子回来,还喜气洋洋地,坚持一个月之久!这无赖的名气已经和衙门口的臭气一样,传遍八方了!
县令大人噤着鼻子,呆呆地盯着案子上的惊堂木,拧着眉头思考一个问题:这三十个大板子怎么不好使捏?……想当初,本老爷金榜题名时,数学可是得了满分,今天好歹要解决这个问题:
——人(系统!)挨板子(脉冲!)以后,会有什么表现(输出!)?
——费话,疼呗!
——我问的是:会有什么表现?
——看疼到啥程度。像这无赖的体格,每天挨一个板子啥事都不会有,连哼一下都不可能,你也看到他那得意洋洋的嘴脸了(输出0);如果一次连揍他十个板子,他可能会皱皱眉头,咬咬牙,硬挺着不哼
(输出1);揍到二十个板子,他会疼得脸部扭曲,象猪似地哼哼(输出3);揍到三十个板子,他可能会象驴似地嚎叫,一把鼻涕一把泪地求你饶他一命(输出5);揍到四十个板子,他会大小便失禁,勉
强哼出声来(输出1);揍到五十个板子,他连哼一下都不可能(输出0)——死啦!
县令铺开坐标纸,以打板子的个数作为X轴,以哼哼的程度(输出)为Y轴,绘制了一条曲线:
——呜呼呀!这曲线象一座高山,弄不懂弄不懂。为啥那个无赖连挨了三十天大板却不喊绕命呀?
—— 呵呵,你打一次的时间间隔(Δτ=24小时)太长了,所以那个无赖承受的痛苦程度一天一利索,没有叠加,始终是一个常数;如果缩短打板子的时间间隔(建议 Δτ=0.5秒),那他的痛苦程度可就迅速叠加了;等到这无赖挨三十个大板(t=30)时,痛苦程度达到了他能喊叫的极限,会收到最好的惩戒效果,再多打就显示不出您的仁慈了。
——还是不太明白,时间间隔小,为什么痛苦程度会叠加呢?
——这与人(线性时不变系统)对板子(脉冲、输入、激励)的响应有关。什么是响应?人挨一个板子后,疼痛的感觉会在一天(假设的,因人而异)内慢慢消失(衰减),而不可能突然消失。这样一来,只要打板子的时间间隔很小,每一个板子引起的疼痛都来不及完全衰减,都会对最终的痛苦程度有不同的贡献:
t个大板子造成的痛苦程度=Σ(第τ个大板子引起的痛苦*衰减系数)
[衰减系数是(t-τ)的函数,仔细品味]
数学表达为:y(t)=∫T(τ)H(t-τ)
——拿人的痛苦来说卷积的事,太残忍了。除了人以外,其他事物也符合这条规律吗?
——呵呵,县令大人毕竟仁慈。其实除人之外,很多事情也遵循此道。好好想一想,铁丝为什么弯曲一次不折,快速弯曲多次却会轻易折掉呢?
——恩,一时还弄不清,容本官慢慢想来——但有一点是明确地——来人啊,将撒尿的那个无赖抓来,狠打40大板!
卷积及拉普拉斯变换的通俗解释–对于我这类没学过信号系统的人来说太需要了
卷积(convolution, 另一个通用名称是德文的Faltung)的名称由来,是在于当初定义它时,定义成 integ(f1(v)*f2(t-v))dv,积分区间在0到t之间。举个简单的例子,大家可以看到,为什么叫”卷积”了。比方说在(0,100)间积分,用简单的辛普生积分公式,积分区间分成100等分,那么看到的是f1(0)和f2(100)相乘,f1(1)和f2(99)相乘,f1(2)和f2 (98)相乘,……… 等等等等,就象是在坐标轴上回卷一样。所以人们就叫它”回卷积分”,或者”卷积”了。
为了理解”卷积”的物理意义,不妨将那个问题”相当于它的时域的信号与系统的单位脉冲响应的卷积”略作变化。这个变化纯粹是为了方便表达和理解,不影响任何其它方面。将这个问题表述成这样一个问题:一个信号通过一个系统,系统的响应是频率响应或波谱响应,且看如何理解卷积的物理意义。
假设信号函数为f, 响应函数为g。f不仅是时间的函数(信号时有时无),还是频率的函数(就算在某一固定时刻,还有的地方大有的地方小);g也是时间的函数(有时候有反应,有时候没反应),同时也是频率的函数(不同的波长其响应程度不一样)。那我们要看某一时刻 t 的响应信号,该怎么办呢?
这就需要卷积了。
要看某一时刻 t 的响应信号,自然是看下面两点:
1。你信号来的时候正赶上人家”系统”的响应时间段吗?
2。就算赶上系统响应时间段,响应有多少?
响 应不响应主要是看 f 和 g 两个函数有没有交叠;响应强度的大小不仅取决于所给的信号的强弱,还取决于在某频率处对单位强度响应率。响应强度是信号强弱和对单位强度信号响应率的乘积。”交叠”体现在f(t1)和g(t-t1)上,g之所以是”(t-t1)”就是看两个函数错开多少。
由于 f 和 g 两个函数都有一定的带宽分布(假若不用开头提到的”表述变化”就是都有一定的时间带宽分布),这个信号响应是在一定”范围”内广泛响应的。算总的响应信号,当然要把所有可能的响应加起来,实际上就是对所有可能t1积分了。积分范围虽然一般在负无穷到正无穷之间;但在没有信号或者没有响应的地方,积也是白积,结果是0,所以往往积分范围可以缩减。
这就是卷积及其物理意义啊。并成一句话来说,就是看一个时有时无(当然作为特例也可以永恒存在)的信号,跟一个响应函数在某一时刻有多大交叠。
*********拉普拉斯*********
拉普拉斯(1729-1827) 是法国数学家,天文学家,物理学家。他提出拉普拉斯变换(Laplace Transform) 的目的是想要解决他当时研究的牛顿引力场和太阳系的问题中涉及的积分微分方程。
拉普拉斯变换其实是一个数学上的简便算法;想要了解其”物理”意义 — 如果有的话 — 请看我举这样一个例子:
问题:请计算十万乘以一千万。
对于没学过指数的人,就只会直接相乘;对于学过指数的人,知道不过是把乘数和被乘数表达成指数形式后,两个指数相加就行了;如果要问究竟是多少,把指数转回来就是。
“拉 普拉斯变换” 就相当于上述例子中把数转换成”指数” 的过程;进行了拉普拉斯变换之后,复杂的微分方程(对应于上例中”复杂”的乘法) 就变成了简单的代数方程,就象上例中”复杂”的乘法变成了简单的加减法。再把简单的代数方程的解反变换回去(就象把指数重新转换会一般的数一样),就解决了原来那个复杂的微分方程。
所以要说拉普拉斯变换真有” 物理意义”的话,其物理意义就相当于人们把一般的有理数用指数形式表达一样。
另外说两句题外话:
1 。拉普拉斯变换之所以现在在电路中广泛应有,根本原因是电路中也广泛涉及了微分方程。
2。拉普拉斯变换与Z变换当然有紧密联系;其本质区别在于拉氏变换处理的是时间上连续的问题,Z变换处理的是时间上分立的问题。
Signals, Linear Systems, and Convolution
Download from here
 
我们都知道卷积公式,但是它有什么物理意义呢?平时我们用卷积做过很多事情,信号处理时,输出函数是输入函数和系统函数的卷积;在图像处理时,两组幅分辨率不同的图卷积之后得到的互相平滑的图像可以方便处理。卷积甚至可以用在考试作弊中,为了让照片同时像两个人,只要把两人的图像卷积处理即可,这就是一种平滑的过程,可是我们怎么才能真正把公式和实际建立起一种联系呢?生活中就有实例:
     比如说你的老板命令你干活,你却到楼下打台球去了,后来被老板发现,他非常气愤,扇了你一巴掌(注意,这就是输入信号,脉冲),于是你的脸上会渐渐地(贱贱地)鼓起来一个包,你的脸就是一个系统,而鼓起来的包就是你的脸对巴掌的响应。
      好,这样就和信号系统建立起来意义对应的联系。下面还需要一些假设来保证论证的严谨:假定你的脸是线性时不变系统,也就是说,无论什么时候老板打你一巴掌,打在你脸的同一位置(这似乎要求你的脸足够光滑,如果你说你长了很多青春痘,甚至整个脸皮处处连续处处不可导,那难度太大了,我就无话可说了),你的脸上总是会在相同的时间间隔内鼓起来一个相同高度的包来,并且假定以鼓起来的包的大小作为系统输出。好了,那么,下面可以进入核心内容——卷积了!
      如果你每天都到楼下去打台球,那么老板每天都要扇你一巴掌,不过当老板打你一巴掌后,你5分钟就消肿了,所以时间长了,你甚至就适应这种生活了……如果有一天,老板忍无可忍,以0.5秒的间隔开始不间断的扇你的过程,这样问题就来了:第一次扇你鼓起来的包还没消肿,第二个巴掌就来了,你脸上的包就可能鼓起来两倍高,老板不断扇你,脉冲不断作用在你脸上,效果不断叠加了,这样这些效果就可以求和了,结果就是你脸上的包的高度岁时间变化的一个函数了(注意理解)!
      如果老板再狠一点,频率越来越高,以至于你都辨别不清时间间隔了,那么,求和就变成积分了。可以这样理解,在这个过程中的某一固定的时刻,你的脸上的包的鼓起程度和什么有关呢?和之前每次打你都有关!但是各次的贡献是不一样的,越早打的巴掌,贡献越小,这就是说,某一时刻的输出是之前很多次输入乘以各自的衰减系数之后的叠加而形成某一点的输出,然后再把不同时刻的输出点放在一起,形成一个函数,这就是卷积。卷积之后的函数就是你脸上的包的大小随时间变化的函数。本来你的包几分钟就可以消肿,可是如果连续打,几个小时也消不了肿了,这难道不是一种平滑过程么?反映到公式上,f(a)就是第a个巴掌,g(x-a)就是第a个巴掌在x时刻的作用程度,乘起来再叠加就ok了,这就是卷积!
     最后提醒各位,请勿亲身尝试……

卷积的物理意义?
在信号与系统中,两个函数所要表达的物理含义是什么?例如,一个系统,其单位冲激响应为h(t),当输入信号为f(t)时,该系统的输出为y(t)。为什么y(t)是f(t)和h(t)的卷积?(从数学推导我明白,但其物理意义不明白。)y(t)是f(t)和h(t)的卷积表达了一个什么意思?

卷积(convolution, 另一个通用名称是德文的Faltung)的名称由来,是在于当初定义它时,定义成 integ(f1(v)*f2(t-v))dv,积分区间在0到t之间。举个简单的例子,大家可以看到,为什么叫“卷积”了。比方说在(0,100)间积分,用简单的辛普生积分公式,积分区间分成100等分,那么看到的是f1(0)和f2(100)相乘,f1(1)和f2(99)相乘,f1(2)和f2(98)相乘,......... 等等等等,就象是在坐标轴上回卷一样。所以人们就叫它“回卷积分”,或者“卷积”了。
为了理解“卷积”的物理意义,不妨将那个问题“相当于它的时域的信号与系统的单位脉冲响应的卷积”略作变化。这个变化纯粹是为了方便表达和理解,不影响任何其它方面。将这个问题表述成这样一个问题:一个信号通过一个系统,系统的响应是频率响应或波谱响应,且看如何理解卷积的物理意义。
假设信号函数为f, 响应函数为g。f不仅是时间的函数(信号时有时无),还是频率的函数(就算在某一固定时刻,还有的地方大有的地方小);g也是时间的函数(有时候有反应,有时候没反应),同时也是频率的函数(不同的波长其响应程度不一样)。那我们要看某一时刻 t 的响应信号,该怎么办呢?
这就需要卷积了。
其实卷积积分应用广泛用在信号里面,一个是频域一个是时域
 

卷积是个啥?我忽然很想从本质上理解它。于是我从抽屉里翻出自己珍藏了许多年,每每下决心阅读却永远都读不完的《应用傅立叶变换》。
 
3.1 一维卷积的定义
 
函数f(x)与函数h(x)的卷积,由函参量的无穷积分

  定义。这里参量x和积分变量α皆为实数;函数f和h可实可复。
 
定义虽然找到了,但我还是一头雾水。卷积是个无穷积分吗?那它是干啥用的?再往后翻:几何说明、运算举例、基本性质,一堆的公式,就是没有说它是干啥用的。我于是坐在那呆想,忽然第二个困扰我的问题冒了出来:傅立叶变换是个啥?接着就是第三个、第四个、……、第N个问题。
 
傅立叶变换是个啥?听说能将时域上的东东变到频域上分析?哎?是变到频域上还是空间域上来着?到底啥是时域,频域,空间域?
 
上网查傅立叶变换的物理意义,没发现明确答案,倒发现了许多和我一样晕着问问题的人。结果又多出了许多名词,能量?功率谱?图像灰度域?……没办法又去翻那本教材。
 
1.1 一维傅立叶变换的定义与傅立叶积分定理
 
设f(x)是实变量x的函数,该函数可实可复,称积分

为函数f(x)的傅立叶变换。
 
吐血,啥是无穷积分来着?积分是啥来着?还能记起三角函数和差化积、积化和差公式吗?我忽然有种想把高中课本寻来重温的冲动。
 
卷积主要是为了将信号运算从时域转换为频域。
信号的时域的卷积等于频域的乘积。
利用这个性质以及特殊的δ函数可以通过抽样构造简单的调制电路
 
 
我比较赞同卷积的相关性的作用  在通信系统中的接收机部分MF匹配滤波器等就是本质上的相关
匹配滤波器最简单的形式就是原信号反转移位相乘积分得到的近似=相关
相关性越好得到的信号越强   这个我们有一次大作业做的  做地做到呕吐  呵呵
还有解调中一些东西本质就是相关
 

卷积公式  解释  卷积公式是用来求随机变量和的密度函数(pdf)的计算公式。  定义式:  z(t)=x(t)*y(t)= ∫x(m)y(t-m)dm.   已知x,y的pdf,x(t),y(t).现在要求z=x+y的pdf. 我们作变量替显,令  z=x+y,m=x. 雅可比行列式=1.那么,z,m联合密度就是f(z,m)=x(m)y(z-m)*1. 这样,就可以很容易求Z的在(z,m)中边缘分布  即fZ(z)=∫x(m)y(z-m)dm..... 由于这个公式和x(t),y(t)存在一一对应的关系。为了方便,所以记 ∫x(m)y(z-m)dm=x(t)*y(t)   长度为m的向量序列u和长度为n的向量序列v,卷积w的向量序列长度为(m+n-1),   u(n)与v(n)的卷积w(n)定义为: w(n)=u(n)@v(n)=sum(v(m)*u(n-m)),m from 负无穷到正无穷;   当m=n时w(1) = u(1)*v(1)   w(2) = u(1)*v(2)+u(2)*v(1)   w(3) = u(1)*v(3)+u(2)*v(2)+u(3)*v(1)   …   w(n) = u(1)*v(n)+u(2)*v(n-1)+ … +u(n)*v(1)   …   w(2*n-1) = u(n)*v(n)   当m≠n时,应以0补齐阶次低的向量的高位后进行计算  这是数学中常用的一个公式,在概率论中,是个重点也是一个难点。

  卷积公式是用来求随机变量和的密度函数(pdf)的计算公式。
  定义式:
  z(t)=x(t)*y(t)= ∫x(m)y(t-m)dm.
  已知x,y的pdf,x(t),y(t).现在要求z=x+y的pdf. 我们作变量替显,令
  z=x+y,m=x. 雅可比行列式=1.那么,t,m联合密度就是f(z,m)=x(m)y(z-m)*1. 这样,就可以很容易求Z的在(z,m)中边缘分布
  即fZ(z)=∫x(m)y(z-m)dm..... 由于这个公式和x(t),y(t)存在一一对应的关系。为了方便,所以记 ∫x(m)y(z-m)dm=x(t)*y(t)
 
卷积是一种线性运算,图像处理中常见的mask运算都是卷积,广泛应用于图像滤波。castlman的书对卷积讲得很详细。
高斯变换就是用高斯函数对图像进行卷积。高斯算子可以直接从离散高斯函数得到:
for(i=0; i<N; i++)
{
for(j=0; j<N; j++)
{
g[i*N+j]=exp(-((i-(N-1)/2)^2+(j-(N-1)/2)^2))/(2*delta^2));
sum += g[i*N+j];
}
}
再除以 sum 得到归一化算子
N是滤波器的大小,delta自选
首先,再提到卷积之前,必须提到卷积出现的背景。卷积是在信号与线性系统的基础上或背景中出现的,脱离这个背景单独谈卷积是没有任何意义的,除了那个所谓褶反公式上的数学意义和积分(或求和,离散情况下)。
信号与线性系统,讨论的就是信号经过一个线性系统以后发生的变化(就是输入输出和所经过的所谓系统,这三者之间的数学关系)。所谓线性系统的含义,就是,这个所谓的系统,带来的输出信号与输入信号的数学关系式之间是线性的运算关系。
因此,实际上,都是要根据我们需要待处理的信号形式,来设计所谓的系统传递函数,那么这个系统的传递函数和输入信号,在数学上的形式就是所谓的卷积关系。

卷积关系最重要的一种情况,就是在信号与线性系统或数字信号处理中的卷积定理。利用该定理,可以将时间域或空间域中的卷积运算等价为频率域的相乘运算,从而利用FFT等快速算法,实现有效的计算,节省运算代价


//////////////////////////////////////////////////////////////////

转载:http://blog.sina.com.cn/s/blog_4bdb170b01019atv.html


2019-03-31 19:19:46 qq_38701868 阅读数 1447

转载自:https://blog.csdn.net/QiangLi_strong/article/details/80760889

图像处理基础知识

彩色图像、灰度图像、二值图像和索引图像区别?

彩色图像:RGB图像。灰度图像:0-255像素值。二值图像:0和1,用于掩膜图像。

索引图像:在灰度图像中,自定义调色板,自定义输出256种颜色值。

常用的图像空间

HSI、HSV、RGB、CMY、CMYK、HSL、HSB、Ycc、XYZ、Lab、YUV色彩空间(颜色模型)

RGB颜色空间是算法处理中应用最多的颜色空间。

HSI颜色空间,色调(Hue)、色饱和度(Saturation或Chroma)和亮度(Intensity或Brightness)

YUV,分为三个分量,“Y”表示明亮度(Luminance或Luma),也就是灰度值;而“U”和“V” 表示的则是色度(Chrominance或Chroma),作用是描述影像色彩及饱和度,用于指定像素的颜色。YUV 4:4:4采样,每一个Y对应一组UV分量。YUV 4:2:2采样,每两个Y共用一组UV分量。 YUV 4:2:0采样,每四个Y共用一组UV分量。 紧缩格式(packed formats)平面格式(planar formats)。YYYYYYYYUVUV YYYYYYYYUUVV

图像的像素数与分辨率有什么区别?

像素数为图像实际组成的像素的个数,像素是没有固定宽度和高度的,是一个感光单元。

分辨率的单位为 像素/英寸(1英寸(inch)=2.54厘米(cm)),这里指的不是面积,而是对角线的长度,即dpi、ppi。分辨率也称之为点密度,分辨率越高,看的越细腻。

视频帧播放速度的单位

PAL制式是——25fps,NTSC是——30fps。

图像预处理

叙述GABOR滤波器原理?

使用一个三角函数(如正弦函数)与一个高斯函数叠加我们就得到了一个Gabor滤波器。Gabor滤波器可以抽取空间局部频度特征,是一种有效的纹理检测工具。

附:图像的空域是指二维坐标系上的操作,频域指的是图像经过傅里叶变换后的频谱。在频率域中,高频分量表示图像中灰度变换比较快的那些地方,比如物体的边缘就是灰度的突然变化,所以物体边缘就是高频分量。而物体内部比较平坦的区域,灰度基本没有变化,对应的就是低频分量。比如低通滤波只让低频分量通过,往往就是使图像模糊,因为边缘信息被去除了。高频对应图像细节,低频对应图像大致轮廓。

椒盐噪声用什么滤波处理比较有效?

参考:中值滤波与椒盐噪声

椒盐噪声:也称为脉冲噪声:

在图像中,它是一种随机出现的白点或者黑点,可能是亮的区域有黑色像素或是在暗的区域有白色像素(或是两者皆有)。

滤除椒盐噪声比较有效的方法是对信号进行中值滤波处理。

插值

最近邻插值

双线性插值

立方卷积插值

二值图像连通域搜索

matlab中连通区域标记函数bwlabel中的算法,一次遍历图像,并记下每一行(或列)中连续的团(run)和标记的等价对,然后通过等价对对原来的图像进行重新标记。

  1. 创建RUN(团)结构体,包含(纵坐标、横坐标开始、横坐标结束、标记号)
  2. 开始逐行扫描图像,寻找所有的团,将他们放到一个二维数组vector< vector<Stuct> >中,以下为每一行的操作。
    1. 当遇到一个255时,创建一个团的对象,标记纵坐标和横坐标的开始。
    2. 从开始点向右寻找,直到遇到0或者这行结束,则标记为这个团的横坐标结束。
    3. 将该行的RUN push到对应的位置。回到步骤2.1.
  3. 对众多的团进行分析,对团进行标记且得到等价对,创建一个vector< pair<int, int> >用于存放所有的等价对。
    1. 遍历所有相邻行。
    2. 若该行为第一行,则直接进行标记。
    3. 对于相邻行,遍历该行的所有RUN,对于每一个RUN,遍历上一行的所有RUN(超出范围即停止循环)。
      1. 若上一行中没有与该行RUN邻接,则创建新的标记。
      2. 若上一行只有一个与该RUN邻接,则沿用相邻RUN的标记。
      3. 若上一行有多个与该RUN邻接,则使用这多个RUN中最小的标记,并创建多个等价对。
  4. 消除等价对,可使用并查集,使得所有的团都拥有自己的祖先。
    1. 假设标记从0开始,到1000结束。标记对为类似的(0,10).(10,39)。
    2. 创建一个prev[1000]数组,初始化值为-1,记录该标记的上一级领导。初始prev[10]=0,prev[39]=10。初始化所有的等价对。
    3. 遍历所有的等价对,修改每一级的上一级领导为最上层领导。
  5. 修改每个团中的标记为最上层领导的标记。

代码见github

开源库cvBlob中使用的标记算法,它通过定位连通区域的内外轮廓来标记整个图像,这个算法的核心是轮廓的搜索算法

TODO:轮廓跟踪算法

并行计算

Intel指令集中MMX,SSE,SSE2,SSE3和SSE4指的是什么?

MMX(Multi Media eXtension,多媒体扩展指令集)是一些整数并行运算指令。

SSE(Streaming SIMD Extensions,单指令多数据流扩展)是一系列浮点并行运算指令。

SIMD,单指令多数据流,是指用一条指令执行多个计算,比如图像像素一般是BYTE占8位,而计算机中总线是64位,所以理论上可以同时进行8个像素的运算。

并行计算有哪些实现方式?

单指令多数据流SIMD、对称多处理机SMP、大规模并行处理机MPP、工作站机群COW、分布共享存储DSM多处理机。

机器学习面试题链接

机器学习部分

特征算子

常用边缘检测有哪些算子,各有什么特性和优缺点?

  1. Prewitt算子
    优点:一阶微分算子,平均滤波,对低噪声的图像有较好的检测效果。缺点:抗噪性差。
  2. Sobel算子Sobel算子
    优点:一阶微分算子,加权平均滤波,对低噪声的图像有较好的检测效果。缺点:抗噪性差。
  3. Roberts算子Roberts
    优点:一种利用局部差分算子寻找边缘的算子,定位比较精确。缺点:对噪声敏感,无法抑制噪声的影响。
  4. Laplacian算子
    优点:各向同性,二阶微分,精确定位边缘位置所在。缺点:无法感知边缘强度。只适用于无噪声图象。存在噪声情况下,使用Laplacian算子检测边缘之前需要先进行低通滤波。
  5. Laplacian of Gaussian(LoG)算子:先对图像做高斯滤波,再做Laplacian算子检测。
  6. Canny算子:一个具有滤波,增强,检测的多阶段的优化算子。先利用高斯平滑滤波器来平滑图像以除去噪声,采用一阶偏导的有限差分来计算梯度幅值和方向,然后再进行非极大值抑制。

请描述以下任一概念:SIFT/SURF LDA/PCA

SIFT/SURF为了实现不同图像中相同场景的匹配,主要包括三个步骤:
1. 尺度空间的建立;
2. 特征点的提取;
3. 利用特征点周围邻域的信息生成特征描述子;
4. 特征点匹配。

之所以采用尺度空间,是为了应对尺度不变性。

SIFT

  1. 生成高斯差分金字塔(DOG金字塔),尺度空间构建
    • 通过对原始图像进行尺度变换,获得图像多尺度下的尺度空间表示序列
    • 对这些序列进行尺度空间主轮廓的提取,并以该主轮廓作为一种特征向量,实现边缘、角点检测不同分辨率上的关键点提取等
    • 尺度空间构建的基础是DOG金字塔,DOG金字塔构建的基础是高斯金字塔
  2. 空间极值点检测(关键点的初步查探)
    • 为了寻找DOG函数的极值点,每一个像素点要和它所有的相邻点比较,看其是否比它的图像域和尺度空间域的相邻点大或者小
    • 在二维图像空间,中心点与它3*3邻域内的8个点做比较,在同一组内的尺度空间上,中心点和上下相邻的两层图像的2*9个点作比较,如此可以保证检测到的关键点在尺度空间和二维图像空间上都是局部极值点
  3. 稳定关键点的精确定位
    • DOG值对噪声和边缘比较敏感,所以在第2步的尺度空间中检测到的局部极值点还要经过进一步的筛选,去除不稳定和错误检测出的极值点,另一点就是在构建高斯金字塔过程中采用了下采样的图像,在下采样图像中提取的极值点对应在原始图像中的确切位置,也是要在本步骤中解决的问题。
  4. 稳定关键点方向信息分配
    • 稳定的极值点是在不同尺度空间下提取的,这保证了关键点的尺度不变性。为关键点分配方向信息所要解决的问题是使得关键点对图像角度和旋转具有不变性。方向的分配是通过求每个极值点的梯度来实现的。
    • 分配给关键点的方向并不直接是关键点的梯度方向,而是按照一种梯度方向直方图的方式给出的。
    • 具体的方法是:计算以关键点为中心的邻域内所有点的梯度方向,当然梯度方向一定是在0~360°范围内,对这些梯度方向归一化到36个方向内,每个方向代表了10°的范围。然后累计落到每个方向内的关键点个数,以此生成梯度方向直方图。
  5. 关键点描述
    • 对关键点的描述是后续实现匹配的关键步骤,描述其实就是一种以数学方式定义关键的过程。描述子不但包含关键点,也包括关键点周围对其有贡献的邻域点。
    • 描述的思路是:对关键点周围像素区域分块,计算快内梯度直方图,生成具有独特性的向量,这个向量是该区域图像信息的一种抽象表述。
    • 如下图,对于2*2块,每块的所有像素点的荼毒做高斯加权,每块最终取8个方向,即可以生成2*2*8维度的向量,以这2*2*8维向量作为中心关键点的数学描述。
    • David G.Lowed的实验结果表明:对每个关键点,采用4*4*8共128维向量的描述子进项关键点表征,综合效果最佳:
  6. 特征点匹配
    • 特征点的匹配是通过计算两组特征点的128维的关键点的欧式距离实现的。欧式距离越小,则相似度越高,当欧式距离小于设定的阈值时,可以判定为匹配成功。

线性判别分析(LDA), 主成分分析(PCA)

参考参考

LDA和PCA最终的表现都是解一个矩阵特征值的问题,分类的目标是,使得类别内的点距离越近越好(集中),类别间的点越远越好。

LDA的全称是Linear Discriminant Analysis(线性判别分析),是一种supervised learning。

LDA的原理是,将带上标签的数据(点),通过投影的方法,投影到维度更低的空间中,使得投影后的点,会形成按类别区分,一簇一簇的情况,相同类别的点,将会在投影后的空间中更接近。要说明白LDA,首先得弄明白线性分类器(Linear Classifier):因为LDA是一种线性分类器。对于K-分类的一个分类问题,会有K个线性函数 y = wx+b.

当满足条件:对于所有的j,都有Yk > Yj,的时候,我们就说x属于类别k。对于每一个分类,都有一个公式去算一个分值,在所有的公式得到的分值中,找一个最大的,就是所属的分类了。

y = wx+b实际上就是一种投影,是将一个高维的点投影到一条高维的直线上,LDA最求的目标是,给出一个标注了类别的数据集,投影到了一条直线之后,能够使得点尽量的按类别区分开

主成分分析(PCA)与LDA有着非常近似的意思,LDA的输入数据是带标签的,而PCA的输入数据是不带标签的,所以PCA是一种unsupervised learning。

PCA更像是一个预处理的方法,它可以将原本的数据降低维度,而使得降低了维度的数据之间的方差最大

它的目标是通过某种线性投影,将高维的数据映射到低维的空间中表示,并期望在所投影的维度上数据的方差最大,以此使用较少的数据维度,同时保留住较多的原数据点的特性。

通俗的理解,如果把所有的点都映射到一起,那么几乎所有的信息(如点和点之间的距离关系)都丢失了,而如果映射后方差尽可能的大,那么数据点则会分散开来,以此来保留更多的信息。可以证明,PCA是丢失原始数据信息最少的一种线性降维方式。(实际上就是最接近原始数据,但是PCA并不试图去探索数据内在结构)

Linear Discriminant Analysis (也有叫做Fisher Linear Discriminant)是一种有监督的(supervised)线性降维算法。与PCA保持数据信息不同,LDA是为了使得降维后的数据点尽可能地容易被区分!

特征点匹配

如下图所示,请以准确快速实现配准为目标,设计算法,让两图中对应的特征点(至少一部分特征点)配准(即精准地地找出对应点之间对应的坐标关系值)。

参考

之前是用角点检测,后来采用SIFT算子,Sift算法的实质是在不同的尺度空间上查找关键点(特征点),计算关键点的大小、方向、尺度信息,利用这些信息组成关键点对特征点进行描述的问题。

  1. 生成高斯差分金字塔(DOG金字塔),尺度空间构建
  2. 空间极值点检测(关键点的初步查探)
  3. 稳定关键点的精确定位
  4. 稳定关键点方向信息分配
  5. 关键点描述(128维向量算子)
  6. 特征点匹配(欧氏距离)

极值点邻域筛选

对于一般应用图像中,景物可能存在任意特征(如折线,弧形、亮度极值、色调等),请设计合适的算法,找到图像中可以作为明显特征点的灰度的极值点所在的邻域。以准确快速实现极值点邻域筛选为目标,设计算法。用流程图表达)。

也使用SIFT特征

特征离散化的好处

  1. 增减特征较为方便,易于迭代。
  2. 离散化后运算速度快,存储方便。
  3. 对脏数据的鲁棒性较强。
  4. 离散化一定程度简化了模型,可以防止过拟合。

分类算法

常用的分类器有哪些,并简述其原理?

线性分类器:Logistic回归 y=sigmoid(wx+b)

传统方式:特征描述和检测

KNN,K最近邻,判断图像与各个类别的距离

SVM,选定特征, SVM算法输出一个最优化的分隔超平面(分类面)。本科课题:SIFT、k-means、Bag of Words、SVM。映射函数可能为多项式。

BPNN,全连接网络,计算量巨大

CNN,卷积神经网络

迁移学习,利用别人训练好的参数,自定义网络

LR与线性回归的对比

LR的优化函数为似然函数,经典线性回归的优化函数为最小二乘。

LR将预测范围缩小到了[0,1],而经典线性回归的预测范围为整个实数。

LR与SVM的对比

相同:都是分类模型。都处理二分类。都可以添加正则项。

区别:LR是参数模型,SVM是非参数模型;LR采用logistical loss,SVM采用hinge loss;SVM之所以称之为支持向量,是因为SVM只考虑了与分类最相关的少数点来学习分类器。

KNN的K是如何选取的

K值较小意味着模型会越复杂,容易发生过拟合。K值过大会使模型过于简单,使得预测发生错误。实际使用中K一般取较小的数字。

什么是SVM?

参考http://blog.csdn.net/v_july_v/ … 24837

是一个二分分类器,找寻数据之间间隔最大的线性分类器。其学习策略是使分隔间隔最大化。对于线性可分的数据,SVM构造一个分隔面。对于线性不可分的数据,SVM采用核函数将低维空间的问题映射到了高维空间,从而线性可分。常用核函数有多项式核函数、高斯核函数、线性核函数。为了应对维度爆炸的情形,核函数事先在低维空间上进行计算,再将分类的实际效果展现在高维上。

SVM的损失函数叫做Hinge(hɪndʒ) Loss,形式为max(0,1-y*a),y为真实值+-1,a为预测值,介于-1到1之间。

简述BP神经网络

BP(back propagation)神经网络,输入X,通过隐藏节点的非线性变换后,输出信号Y,通过误差分析,来调整隐藏节点的W和b。

AdaBoost的基本原理?

AdaBoost是一个广泛使用的BOOSTING算法,其中训练集上依次训练弱分类器,每次下一个弱分类器是在训练样本的不同权重集合上训练。权重是由每个样本分类的难度确定的。分类的难度是通过分类器的输出估计的。

参考资料

//TODO 详细学习

聚类算法

简述你熟悉的聚类算法并说明其优缺点

K均值聚类(K-meansClustering)

将输入数据分到K个类中。K均值是通过循环更新类中心的初始估计值来实现的。优势是实现起来很简单,是并行化的。主要缺陷是,类的数目需要提前确定。

主要分三步:
1. 随机选取k个聚类质心点(cluster centroids)
2. 对于每一个样例i,计算其应该属于的类
3. 对于每一个类j,重新计算该类的质心
1. 重复下面过程直到收敛

层次聚类

层次聚类(或者叫做凝聚聚类)是另一个简单但是强大的聚类算法。其思想是基于成对距离建立一棵相似度树。该算法首先分组成为两个最近的对象(基于特征向量之间的距离),并且在一棵有着两个对象作为孩子的树中创建一个平均结点。然后在余下的结点中找到一个最近的pair,并且也包含任何平均节点,等等。在每一个结点,两个孩子之间的距离也会被存储。簇然后可以通过遍历这棵树并在距离比某个阈值小以至于决定聚类的大小的结点处停止来被提取出来。

层次聚类有几个优势。比如,树结构可以被用来可视化关系,并且显示簇是如何关联起来的。一个好的特征向量将得到树中好的分离。另一个优势是树可以在不同的簇阈值中被重用,而不需要重新计算树。缺点是需要选择一个阈值如果实际的簇需要的话

谱聚类

对于n个元素的相似度矩阵(或者叫affinity matrix, 有时也叫距离矩阵)是一个有着成对相似度分数的n*n矩阵。谱聚类的这个名称是从相似度矩阵构造的矩阵的谱的使用得来。这个矩阵的特征向量被用来降维,然后再聚类。

谱聚类方法的其中一个优势是唯一的输入就是这个矩阵,并且可以被你可以想到的任何相似度度量构造出来。像K均值和层次聚类这样的方法计算特征向量的平均值,这个限制了特征(或者是描述符)对向量(为了能够计算平均值)。有了谱方法,不再需要任何类型的特征向量,只有“距离”或者“相似度”。

Mean Shift 聚类算法

  1. 在未被标记的数据点中随机选择一个点作为中心center;
  2. 找出离center距离在bandwidth之内的所有点,记做集合M,认为这些点属于簇c。同时,把这些求内点属于这个类的概率加1,这个参数将用于最后步骤的分类
  3. 以center为中心点,计算从center开始到集合M中每个元素的向量,将这些向量相加,得到向量shift。
  4. center = center+shift。即center沿着shift的方向移动,移动距离是||shift||。
  5. 重复步骤2、3、4,直到shift的大小很小(就是迭代到收敛),记住此时的center。注意,这个迭代过程中遇到的点都应该归类到簇c。
  6. 如果收敛时当前簇c的center与其它已经存在的簇c2中心的距离小于阈值,那么把c2和c合并。否则,把c作为新的聚类,增加1类。
  7. 重复1、2、3、4、5直到所有的点都被标记访问。
  8. 分类:根据每个类,对每个点的访问频率,取访问频率最大的那个类,作为当前点集的所属类。

简单的说,mean shift就是沿着密度上升的方向寻找同属一个簇的数据点。

欧式距离和曼哈顿距离的区别

欧式距离为最常见的2点之间的距离,为2点之间的直线距离。

曼哈顿距离又称为L1距离或者城市区块距离,是两个点的1范数距离。

图像分割

Graph-cut的基本原理和应用?

Graph cuts是一种十分有用和流行的能量优化算法,在计算机视觉领域普遍应用于前背景分割(Image segmentation)、立体视觉(stereo vision)、抠图(Image matting)等。

利用图,将目标和背景进行分割。

图像融合,镶嵌

已知两幅拼接好的图像,两幅图像在几何关系配准之后,但两图之间存在明显灰度差别跳变,请设计一个算法对图像进行处理,让两幅图之间的灰度看不出跳变,形成自然过渡。(可以不考虑两图之间的黑图部分)。

影像融合是指高分辨率灰度图像和低分辨率彩色图像融合得到具有高分辨率的彩色图像。该算法称之为图像镶嵌。简单的做法可以是寻找两幅影像的镶嵌线,镶嵌线是指两幅影像公共区域区别最小的一条线,可以利用相关系数法判断得到,然后根据镶嵌线上两幅影像的灰度差异对右影像进行反差调整,最后拼接。

其他模型

Random Forest的随机性表现在哪里。

Bagging方法是ensemble methods中获得用于训练base estimator的数据的重要一环。 正如其名,Bagging方法就是将所有training data放进一个黑色的bag中,黑色意味着我们看不到里面的数据的详细情况,只知道里面有我们的数据集。然后从这个bag中随机抽一部分数据出来用于训练一个base estimator。抽到的数据用完之后我们有两种选择,放回或不放回。

我们可以看到从根节点开始往下会有分支,最终会走向叶子节点,得到分类结果。每一个非叶子节点都是一个特征,上图中共有三维特征。但是决策树的一个劣势就是容易过拟合,下面我们要结合上文提到的bagging技术来中和一下。

img

bagging + decision trees,我们得到了随机森林。将决策树作为base estimator,然后采用bagging技术训练一大堆小决策树,最后将这些小决策树组合起来,这样就得到了一片森林(随机森林)。

(X[1],Y[1])….(X[n],Y[n])是数据集,我们要训练T棵决策树g[1]….g[t]…g[T]。 每次从数据中有放回地随机抽取size-N’的子数据集D[t]用于训练第t棵决策树g[t]。

随机森林的随机性体现在每颗树的训练样本是随机的,树中每个节点的分裂属性集合也是随机选择确定的。有了这2个随机的保证,随机森林就不会产生过拟合的现象了。

GMM的基本原理和应用

高斯混合模型(Gaussian Mixture Model, GMM)将一个事物分解为若干的基于高斯概率密度函数(正态分布曲线)形成的模型。

高斯混合模型(GMM,Gaussian mixture model)是建模最为成功的方法之一,同时GMM可以用在监控视频索引与检索。

用于动目标检测中的背景建模。

  • 混合高斯模型使用K(++基本为3到5个++) 个高斯模型来表征图像中各个像素点的特征。
  • 在新一帧图像获得后更新混合高斯模型,用当前图像中的每个像素点与混合高斯模型匹配,如果成功则判定该点为背景点, 否则为前景点。
  • 通观整个高斯模型,他主要是有++方差++和++均值++两个参数决定,,对均值和方差的学习,采取不同的学习机制,将直接影响到模型的稳定性、精确性和收敛性。
  • 由于我们是对运动目标的背景提取建模,因此需要对高斯模型中方差和均值两个参数实时更新。
  • 为提高模型的学习能力,改进方法对均值和方差的更新采用不同的学习率
  • 为提高在繁忙的场景下,大而慢的运动目标的检测效果,引入权值均值的概念,建立背景图像并实时更新,然后结合权值、权值均值和背景图像对像素点进行前景和背景的分类。

其他理论

监督学习和非监督学习。

  • 监督学习:通过已有的一部分输入数据与输出数据之间的对应关系,生成一个函数,将输入映射到合适的输出,例如分类。
  • 非监督学习:直接对输入数据集进行建模,例如聚类。
  • 半监督学习:综合利用有类标的数据和没有类标的数据,来生成合适的分类函数。

目前最广泛被使用的分类器有人工神经网络、支持向量机、最近邻居法、高斯混合模型、朴素贝叶斯方法、决策树和径向基函数分类。

无监督学习里典型的例子就是聚类了。聚类的目的在于把相似的东西聚在一起,而我们并不关心这一类是什么。因此,一个聚类算法通常只需要知道如何计算相似度就可以开始工作了。

过拟合的解决方法

减小模型复杂度、加大数据、batch normalization、dropout、正则化、early stopping。

谈谈判别式模型和生成式模型?

常见的判别模型有:K近邻、SVM、决策树、感知机、线性判别分析(LDA)、线性回归、传统的神经网络、逻辑斯蒂回归、boosting、条件随机场。通过决策函数来进行判别。

常见的生成模型有:朴素贝叶斯、隐马尔可夫模型、高斯混合模型、文档主题生成模型(LDA)、限制玻尔兹曼机。通过联合概率密度分布函数来进行预测。

L1和L2的区别

  • L1范数为向量中各个元素的绝对值之和,符合拉普拉斯分布,可以使权值稀疏。
  • L2范数为向量中各个元素的平方和的1/2次方,符合高斯分布,可以防止过拟合。
  • Lp范数为向量中各个元素的p次方和的1/p次方。

归一化的好处

归一化加快了梯度下降求解最优解的速度;归一化还可能会提高精度。

归一化的种类

  • 线性归一化。利用max和min进行归一化,如果max和min不稳定,则常用经验值来替代max和min。
  • 标准差归一化。利用所有样本的均值和方差将样本归一化为正态分布。
  • 非线性归一化。比如指数、对数、三角函数等。

归一化和标准化的区别

标准化是依照特征矩阵的列处理数据,其通过求z-score的方法,将样本的特征值转换到同一量纲下。归一化是依照特征矩阵的行处理数据,其目的在于样本向量在点乘运算或其他核函数计算相似性时,拥有统一的标准,也就是说都转化为“单位向量”。

对于深度网络而言,归一化的目的是方便比较,可以加快网络的收敛速度;标准化是将数据利用z-score(均值、方差)的方法转化为符合特定分布的数据,方便进行下一步处理,不为比较。

熵是指样本的随机程度。样本越无序,熵越大, 信息越多。

完成机器学习项目流程

  1. 抽象成数学问题。明确我们可以获得什么样的数据,这个问题是回归还是分类。
  2. 获取数据。增加数据的代表性,防止因数据引起的过拟合。
  3. 特征预处理和特征选择。进行数据清洗,包括归一化、离散化等操作。结合数据和业务的特点来确定需要选取的特征算子。
  4. 训练模型和调优。选择一个模型进行训练,并对超参数进行调节。
  5. 模型诊断。分析模型是否过拟合或者欠拟合,然后进行相应的操作。同时可以进行误差分析,针对不同的问题来优化模型。
  6. 模型融合。将预处理和预测进行统一。
  7. 上线运行。

深度学习部分

潮流

图像检测和分割,增强学习,生成对抗网络,预测学习

基础理论

SGD 中 S(stochastic)代表什么

Stochastic Gradient Descent 随机梯度下降。GD即Full-Batch,SGD即为Mini-Batch。随机性表现在训练数据的shuffle。

Softmax Loss推一下

Sigmoid、Tanh、ReLU比较

Rectified Linear Unit, ReLU

ReLU比Sigmoid、Tanh好的原因

  1. 指数函数运算量大。ReLU节省运算量。
  2. Sigmoid容易引发梯度消失问题,因为Sigmoid函数在两端的导数趋近于0.
  3. ReLU使得一部分神经元死亡,这样可以使得网络变得比较稀疏,缓解了过拟合的发生。

引入非线性激活函数的原因?

若使用线性激活函数,则无论神经网络有多少层,输出都是输入的线性组合。

好的激活函数有以下特点:

  1. 非线性:即导数不是常数。
  2. 几乎处处可微:可微性保证了在优化中梯度的可计算性。
  3. 计算简单。
  4. 非饱和性(saturation):饱和指的是在某些区间梯度接近于零(即梯度消失),使得参数无法继续更新的问题。
  5. 单调性(monotonic):即导数符号不变。
  6. 输出范围有限:有限的输出范围使得网络对于一些比较大的输入也会比较稳定
  7. 接近恒等变换(identity):即约等于x。这样的好处是使得输出的幅值不会随着深度的增加而发生显著的增加
  8. 参数少:大部分激活函数都是没有参数的。
  9. 归一化(normalization):这个是最近才出来的概念,对应的激活函数是SELU。类似于Batch Normalization。

什么造成了梯度消失和梯度膨胀?

深度网络的链式连乘法则,使得反向传播时到达前几层时,权值更新值非常小或非常大。

可以通过ReLU解决一部分。

各大指标

先是混淆矩阵,这是基础。

混淆矩阵

包含四部分的信息:
1. True negative(TN),称为真阴率,表明实际是负样本预测成负样本的样本数
2. False positive(FP),称为假阳率,表明实际是负样本预测成正样本的样本数
3. False negative(FN),称为假阴率,表明实际是正样本预测成负样本的样本数
4. True positive(TP),称为真阳率,表明实际是正样本预测成正样本的样本数

前面有的表示预测正确。

ROC曲线

二分类标签的输出概率需要定义一个阈值p,p值的选取反映了分类器的分类性能。ROC曲线的横轴为FP(将真实负样本预测为了正样本,越低越好),纵轴为TP(将真实正样本预测为正样本,越高越好)

ROC

  • (0,0):假阳率和真阳率都为0,即分类器全部预测成负样本
  • (0,1):假阳率为0,真阳率为1,全部完美预测正确,happy
  • (1,0):假阳率为1,真阳率为0,全部完美预测错误,悲剧
  • (1,1):假阳率和真阳率都为1,即分类器全部预测成正样本
  • TPR=FPR,斜对角线,预测为正样本的结果一半是对的,一半是错的,随机分类

则,若ROC曲线处于对角线之下,则分类性能差于随机分类器。希望该曲线向左上角凸。

AUC指标

AUC(Area under the ROC curve),适用于二元分类问题,AUC实际上就是ROC曲线下的面积。AUC直观地反映了ROC曲线表达的分类能力。

  • AUC = 1,代表完美分类器
  • 0.5 < AUC < 1,优于随机分类器
  • 0 < AUC < 0.5,差于随机分类器

求解步骤:

  1. 获得样本的输出概率和标签值。
  2. 对于不同的从高到低的阈值,计算不同的TP和FP。
  3. 绘制ROC曲线,计算面积。

AUC含义:从所有真实的正样本中取一个数据,判断这个样本是正样本的概率是p1,从所有真实的负样本中取一个数据,判断这个样本是正样本的概率是p2。对于分类器来说p1越大越好,p2越小越好。则p1大于p2的概率称之为AUC。

mAP

计算步骤,参考

  1. 得到所有测试样本的id、输出概率和真实标签值。
  2. 对输出概率进行排序。
  3. 假设有M个recall值,分别计算不同recall下的准确率。
  4. 取M个准确率的平均值。

AP(average precision),

卷积神经网络

图像预处理手段

卷积和相关

相关和卷积的机理相似,但卷积滤波器首先要旋转180度。

卷积算法的时间复杂度

因为在图像的每个位置都要计算一遍卷积核,所以图像像素数为M,卷积核大小为N,则卷积的时间复杂度为O(M*N)。

池化层的作用

  • 保留主要特征的同时进行降维和减少计算量,防止过拟合,提高模型泛化能力。
  • 增加一定的不变性,在池化窗口内。包括平移、旋转、尺度不变性。

CNN特性

CNN的四个特点:局部连接、权值共享、池化操作、多层次结构。

局部连接使网络可以提取数据的局部特征;权值共享降低了网络的训练难度,一个Filter只提取一个特征;池化操作与多层次结构一起,实现了数据的降维,将低层次的局部特征组合成为较高层次的特征,从而对整个图片进行表示。

为什么很多做人脸的Paper会最后加入一个Local Connected Conv?

人脸在不同的区域存在不同的特征(眼睛/鼻子/嘴的分布位置相对固定),当不存在全局的局部特征分布时,Local-Conv更适合特征的提取。

循环神经网络

LSTM为何比RNN好

LSTM可以防止梯度消失或者爆炸

其他网络

生成对抗网络

简称GAN。该网络包含2个部分,一个称之为生成器generator,主要作用是生成图片,并且尽量使得其看上去是来自于训练样本的。另一方是discriminator,其目标是判断输入图片是否属于真实训练样本。

TensorFlow

如何理解TensorFlow的计算图?

TensorFlow分为二部分,一部分是构造部分,用来构造网络;一部分是执行部分,用来执行网络中的计算。

图像相关开放性知识

怎样在一张街拍图像中识别明星的衣着服饰信息?

我们需要把服装与背景、人物、建筑等等元素区别开来,确定是否有衣服以及衣服在什么位置。接下来需要对衣服进行分析,提取出服装的属性、特征等等。最后再根据这些特征,在庞大的数据库里搜索同款或者类似的服装图片。

上衣纯色,裙子花色,怎样做区分?

方差判断,梯度变化。

怎样判断一张广告图片中是否有文字信息?是否用到OCR技术?怎样应用?

场景文字检测与识别,先用CNN等对文字进行定位,然后再使用LSTM、OCR进行文字识别。

给一张二值化图片(包含一个正方形),怎样识别图片中的正方形?如果图片污损严重,怎样识别并恢复?

首先检测轮廓,然后对轮廓进行分析(角点)。

如果图像污损严重,如何识别?

简述图像识别在移动互联网中的应用

人脸识别、识别各类东西、检索各类图像。

图像处理领域相关顶级论文

  • Image and Vision Computing (IVC)
  • Pattern Recognition (PR)
  • ICCV: IEEE International Conference on Computer Vision
  • CVPR: IEEE Conf on Comp Vision and Pattern Recognition
  • NIPS: Neural Information Processing Systems

数学部分

公式

贝叶斯全概率公式题

全概率公式

对任一事件A,若有互不相容的事件Bi(i=1,2,...,n)Bi(i=1,2,...,n),则事件A的概率可用下式计算:

P(A)=i=1nP(Bi)P(A|Bi)P(A)=∑i=1nP(Bi)P(A|Bi)

img

此概率称之为全概率公式。

Bayes公式

利用乘法公式与全概率公式可导出Bayes公式

对任一事件A,若有互不相容的事件Bi(i=1,2,,n)Bi(i=1,2,…,n),(跟上个公式条件相同)则

P(Bi|A)=P(Bi)P(A|Bi)ni=1P(Bi)P(A|Bi)(i=1,2,,n)P(Bi|A)=P(Bi)P(A|Bi)∑i=1nP(Bi)P(A|Bi)(i=1,2,…,n)

最小二乘拟合的公式推导和代码实现。

最小二乘法通常用于 曲线拟合 (least squares fitting) 。

推导过程

核心思想是最小化损失函数:距离差值的平方((diR)2(di−R)2

C/C++部分

基本概念

关键字static的作用是什么?

  1. 在函数体,一个被声明为静态的变量在这一函数被调用过程中维持其值不变。
  2. 在模块内(但在函数体外),一个被声明为静态的变量可以被模块内所用函数访问,但不能被模块外其它函数,它是一个本地的全局变量。
  3. 在模块内,一个被声明为静态的函数只可被这一模块的它函数调用。那就是,这个函数被限制在声明它的模块的本地范围内使用。

简述C,C++程序编译的内存分配情况?

C,C++中内存分配方式可以分为三种:

  1. 从静态存储区域分配:内存在程序编译时就已经分配好,这块内存在程序的整个运行期间都存在。速度快,不容易出错,因有系统自行管理。它主要存放静态数据、全局数据和常量。会默认初始化,其他两个不会自动初始化。
  2. 在栈上分配:在执行函数时,函数内局部变量的存储单元都在栈上创建,函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中,效率很高,但是分配的内存容量有限。
  3. 从堆上分配:即运态内存分配。程序在运行时候用malloc或new申请任意大小的内存,程序员自己负责在何进用free 和delete释放内存。

一个C、C++程序编译时内存分为5大存储区:堆区、栈区、全局区、文字常量区和程序代码区。

new 和 malloc的区别

  1. malloc/free是C的标准库函数,new/delete是C++的运算符。它们都可用于申请动态内存和释放内存。
  2. 当使用一些非内置数据类型的对象时,maloc/free不能自动执行构造函数和析构函数。这是因为malloc/free是库函数,不在编译器控制下。

图的遍历

深度搜索DFS

递归写法

  1. 定义一个visited数组。
  2. 访问当前节点,输出该节点。
  3. 循环遍历该节点的相邻的,未被访问过的节点。
    1. 递归第二步。

非递归写法

  1. 定义一个栈和一个visited数组。
  2. 将初始节点入栈。开始循环,直道栈空。循环如下:

广度搜索BFS

设置队列

  1. 定义一个队列Queue和visited数组。
  2. 将开头节点入队。
  3. 开始循环
    1. 出队,访问该节点
    2. 遍历该节点的相邻的未被访问过的节点,入队

hash 冲突及解决办法

键字值不同的元素可能会映象到哈希表的同一地址上就会发生哈希冲突。解决办法:

  1. 开放定址法。按照一定的方法进行顺延。
  2. 再哈希法。同时构造多个不同的哈希函数。
  3. 链地址法。数组后的每个元素后添加单链表。

红黑树的特征

具有二叉查找树的所有特征。二叉查找树查找的效率最坏为O(n),红黑树通过颜色着色的方法将最坏降低到平均水平。

  1. 每个结点要么是红的要么是黑的。
  2. 根节点是黑的。
  3. 每个叶结点(树尾端的NIL指针或者NULL结点)都是黑的。
  4. 如果一个节点是红色,他的两个孩子都是黑色。
  5. 对于任意结点而言,其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

是红黑树的这5条性质,使一棵n个结点的红黑树始终保持了logn的高度,从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”

其他编程

嵌入式系统总是用户对变量或寄存器进行位操作。给定一个整型变量a,写两段代码,第一个设置a的bit3,第二消除a的 bit 3。在以上两个操作中,要保持其它位不变.

#include <iostream>
#include <bitset>
using namespace std;

#define BIT3 (0x1<<3)
void set_bit3(unsigned &a)
{
    a |= BIT3;
}
void clear_bits(unsigned &a)
{
    a &= ~BIT3;
}

int main()
{
    unsigned a = UINT_MAX;
    clear_bits(a);
    cout << (bitset<32>)a << endl;
    set_bit3(a);
    cout << (bitset<32>)a << endl;
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

行列递增矩阵的查找

解法一、分治法

因为矩阵的行和列都是递增的,所以整个矩阵的对角线上的数字也是递增的,故我们可以在对角线上进行二分查找,如果要找的数是6介于对角线上相邻的两个数4、10,可以排除掉左上和右下的两个矩形,而在左下和右上的两个矩形继续递归查找

解法二、定位法

首先直接定位到最右上角的元素,比要找的数大就往左走,比要找数的小就往下走,直到找到要找的数字为止,走不动,说明这个数不存在。这个方法的时间复杂度O(m+n)。代码如下:

#include <iostream>
#include <vector>
using namespace std;

bool YoungMatrix(vector< vector<int> > mat, int target){
    int y = 0, x = mat[y].size() - 1;
    int var = mat[y][x];
    while (true) {
        if (var == target){
            printf("Mat[%d][%d]=%d\n", y, x, target);
            return true;
        }
        else if (var < target && y < mat.size() - 1){
            var = mat[++y][x];
        }
        else if (var > target && x > 0){
            var = mat[y][--x];
        }
        else{
            return false;
        }
    }
}

int main(){
    vector<vector<int> > matrix(20);
    for (int i = 0; i < 20; i++){
        for (int j = 0; j < 20; j++) {
            matrix[i].push_back(i+j);
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
    cout << YoungMatrix(matrix, 38) << endl;
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36

从1到500的500个数,第一次删除奇数位上的所有数,第二次删除剩下来的奇数位,以此类推,最后剩下的唯一一位数是什么?

就是当1~n,2^i

给出了一个n*n的矩形,编程求从左上角到右下角的路径数(n > =2),限制只能向右或向下移动,不能回退。例如当n=2时,有6条路径。

从左上角到右下角总共要走2n步,其中横向要走n步,所以总共就是Cn2nC2nn次。

给出一棵二叉树的前序和中序遍历,输出后续遍历的结果。

已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为多少?

#include <iostream>
#include <string>
using namespace std;

string Subsequent(string pre, string mid) {
    if (pre.size() != mid.size() || pre.empty()) return "";
    char root = pre[0];
    int rootIndex = mid.find(root);
    string leftPre = pre.substr(1, rootIndex);
    string leftMid = mid.substr(0, rootIndex);
    string rightPre = pre.substr(rootIndex + 1);
    string rightMid = mid.substr(rootIndex + 1);

    string res;
    res += Subsequent(leftPre, leftMid);
    res += Subsequent(rightPre, rightMid);
    res += root;
    return res;
}

int main(){
    string pre = "ABDEGCFH";
    string mid = "DBGEACHF";
    cout << Subsequent(pre, mid) << endl;
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

自定义实现字符串转为整数的算法,例如把“123456”转成整数123456.(输入中可能存在符号,和数字)

代码见github

字符串最长公共子序列

动态规划推导式

img

代码见github

字符串最长公共子串

与上文区别是不等时的处理方式,和最后是整个矩阵中寻找最大值。

代码见github

请实现一个函数:最长顺子。输入很多个整数(1<=数值<=13),返回其中可能组成的最长的一个顺子(顺子中数的个数代表顺的长度); 其中数字1也可以代表14;

直方图

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> LongestShunZi(vector<int> input) {
    // 统计直方图
    vector<int> hist;
    hist.resize(15);
    for (int i = 0; i < input.size(); i++)
        if (input[i] > 0 && input[i] < 15)
            hist[input[i]] ++;
    hist[14] = hist[1];
    //最大牌数
    int maxCount = 0;
    for (int i = 1; i < 15; i++)
        if (hist[i] > maxCount)
            maxCount = hist[i];
    //求结果
    int resLen = 0;
    int resCount = 0;
    int resEnd = 0;
    for (int i = 1; i <= maxCount; i++)
    {
        int len = 0;
        int longestLen = 0;
        int longestEnd = 1;
        for (int j = 1; j < 15; j++) {
            if (hist[j] >= i) {
                len++;
                if (len > longestLen) {
                    longestLen = len;
                    longestEnd = j;
                }
            }
            else {
                len = 0;
            }
        }
        if (longestLen == 14 && 2 * i > hist[1]) longestLen--;
        if (longestLen * i > resLen * resCount) {
            resLen = longestLen;
            resCount = i;
            resEnd = longestEnd;
        }
    }

    vector<int> res;
    for (int i = resEnd - resLen + 1; i <= resEnd; i++)
        for (int j = 0; j < resCount; j++)
            res.push_back(i);
    return res;
}

int main() {
    int arr[] = { 1, 5, 2, 3, 4, 4, 5, 9, 6, 7, 2, 3, 3, 4 };
    vector<int> v(arr, arr+sizeof(arr)/sizeof(int));
    vector<int> res = LongestShunZi(v);
    for (int i = 0; i < res.size(); i++) cout << res[i] << " ";
    cout << endl;
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62

对一批编号为1-100,全部开关朝上(开)的亮灯进行如下操作

对一批编号为1-100,全部开关朝上(开)的亮灯进行如下操作:凡是编号为1的倍数的灯反方向拨一次开关;凡是编号为2的倍数的灯反方向又拨一次开关;编号为3的倍数的灯反方向又拨一次开关……凡是编号为100的倍数的灯反方向拨一次开关。编写程序,模拟此过程,最后打印出所熄灭灯的编号。

#include <iostream>
using namespace std;

int main() {
    bool arr[101];
    memset(arr, 0, 101);

    for (int i = 2; i <= 100; i++) {
        for (int j = 1; j <= 100; j++) {
            if (j % i == 0) {
                arr[j] = !arr[j];
            }
        }
    }
    for (int i = 1; i <= 100; i++) {
        if (!arr[i])
            cout << i << endl;
    }
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
1
4
9
16
25
36
49
64
81
100
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

一个数的约数个数为奇数。所有的数都包含1和自己,平方数的约数肯定是奇数个。

实现个函数 unsigned int convect(char* pstr)

实现个函数 unsigned int convect(char* pstr)。其中pstr是十六进制数的字符串。函数convectpstr转换成数字返回(比如:字符串’1A’,将返回数值26.注意,pstr[0]是’1’)。pstr中只有数字字符0到9、A到F。不得借助其它的系统函数调用。

#include <iostream>
using namespace std;

unsigned int convect(char* pstr) {
    char *p = pstr;
    unsigned long long res = 1;
    unsigned long long maxInt = (res << 32) - 1;
    res = 0;
    while (*p != '\0') {
        if (*p >= '0' && *p <= '9') {
            res = res * 16 + *p - '0';
        }
        else if (*p >= 'A' && *p <= 'F') {
            res = res * 16 + *p - 'A' + 10;
        }
        else return 0;
        p++;
    }
    if (res > maxInt) return 0;
    return res;
}

int main() {
    cout << convect((char*)"1A") << endl;
    cout << convect((char*)"FFFFFFFF") << endl;
    cout << convect((char*)"FFFFFFFFF") << endl;
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

实现一个函数unsigned int counter(char* pstr)

实现一个函数unsigned int counter(char* pstr)。函数将打印出匹配的括号对。比如:字符串”a(bc(d)ef(12)g)”就存在3对匹配的括号对,分别是:
1. 位置4上的(与位置6上的)匹配。打印4 6即可。
1. 位置9上的(与位置12上的)匹配。打印9 12即可。
1. 位置1上的(与位置14上的)匹配。打印1 14即可。

软件编程部分

设计

给你一个模块要求,你要做出这个模块,那么你的做出该模块的思路和步骤是什么?

明确这个模块的功能,明确其输入以及输出。

尽量去除与其他模块的耦合关系,确保独立性。

我会首先编写输入和输出的接口函数,然后由粗到精,逐步实现细节算法。

同时还需要编写模块的测试代码,保证交付的可靠性。

Matlab编程

Matlab 中读、写及显示一幅图像的命令各是什么?

imread(), imwrite(), imshow()

Matlab 与VC++混合编程有哪几种方式?

Matlab引擎方式(Matlab后台程序为服务器,VC前端为客户端,C/S结构)、Matlab编译器(将Matlab源代码编译为C++可以调用的库文件)及COM组件(Matlab生成COM组件,VC调用)

Matlab运算中 .** 的区别?

.*表示矩阵元素分别相乘,要求两个矩阵具有相同的shape。*表示矩阵相乘。

逻辑推理部分

智力题

药丸问题

有四人装药丸的罐子,每个药丸都有一定的重量,被污染的药丸是没被污染的重量+1.只称量一次,如何判断哪个罐子的药被污染了?

答:在四个罐子里面分别取1、2、3、4颗药丸,然后进行称量。如果称量结果比实际(污染前)重了n,就是第n罐被污染了。 (因为每加一颗被污染的药丸就增加1所以增加n就是增加n颗就是在第n个罐子里拿的)

帽子黑白问题

一群人开舞会,每人头上都戴着一顶帽子。帽子只有黑白两种,黑的至少有一顶。每个人都能看到其他人帽子的颜色,却看不到自己的。主持人先让大家看看别人头上戴的是什么帽子,然后关灯,如果有人认为自己戴的是黑帽子,就打自己一个耳光。第一次关灯,没有声音。于是再开灯,大家再看一遍,关灯时仍然鸦雀无声。一直到第三次关灯,才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子?

解:假如只有一个人戴黑帽子,那他看到所有人都戴白帽,在第一次关灯时就应自打耳光,所以应该不止一个人戴黑帽子;如果有两顶黑帽子,第一次两人都只看到对方头上的黑帽子,不敢确定自己的颜色,但到第二次关灯,这两人应该明白,如果自己戴着白帽,那对方早在上一次就应打耳光了,因此自己戴的也是黑帽子,于是也会有耳光声响起;可事实是第三次才响起了耳光声,说明全场不止两顶黑帽,依此类推,应该是关了几次灯,有几顶黑帽。

金条问题

让工人为你工作7天,给工人的回报是一根金条。金条平分成相连的7段,你必须在每天结束时给他们一段金条,如果只许你两次把金条弄断,你如何给你的工人付费?

答:分成1、2、4段。利用1,2,4可以组合成1,2,3,4,5,6,7

拆字游戏

下面玩一个拆字游戏,所有字母的顺序都被打乱。你要判断这个字是什么。假设这个被拆开的字由5个字母组成:
1. 共有多少种可能的组合方式?
2. 如果我们知道是哪5个字母,那会怎么样?
3. 找出一种解决这个问题的方法。

个人解答:
1. A55=54321=120A55=5∗4∗3∗2∗1=120
1. 会依靠英文字母的规则等大致弄几种可能性出来。
1. 将弄出来的可能性的单词进行查找。

为什么下水道的盖子是圆的?

解:很大程度上取决于下水道的形状,一般为了使得各个方向的管子都可以接入到下水道中,所以下水道设计成了圆柱形,所以盖子相应的也是圆形。且圆形比较省材料,便于运输。

请估算一下CNTOWER电视塔的质量

首先在纸上画出了CNTOWER的草图,然后快速估算支架和各柱的高度,以及球的半径,算出各部分体积,然后和各部分密度运算,最后相加得出一个结果。