图像处理 药丸分割_药丸图片 图像处理 - CSDN
  • MATLAB实现静态图像分割

    万次阅读 多人点赞 2017-05-18 20:09:05
    MATLAB实现静态图像分割处理图像是一张药板图,我们的处理目标有以下几个: 1. 将药板从黑色背景中分离(药板部分显示为白色,背景显示为黑色); 2. 根据分割结果将药板旋转至水平; 3. 提取药板中的药丸的...

    MATLAB实现静态图像分割

    待处理图像是一张药板图,我们的处理目标有以下几个:
    1. 将药板从黑色背景中分离(药板部分显示为白色,背景显示为黑色);
    2. 根据分割结果将药板旋转至水平;
    3. 提取药板中的药丸的信息;
    待处理照片


    • 首先将药板从黑色背景中分离出来,用otsu对图像进行分割,很简单,代码是王道。
    clc;clear all;  
    H=imread('C:\Users\Administrator\Desktop\1\1.tiff');       
    I=rgb2gray(H);  
    T=graythresh(I);    %采用Otsu方法计算最优阈值T对图像二值化;  
    Ibw1 = im2bw(I,T);
    figure, imshow(Ibw1);title('Otsu-图1');
    

    只贴一个 结果:
    这是图
    接着将孔洞填充:

    clear,clc,close all;
    I=imread('C:\Users\Administrator\Desktop\1\1.tiff');
    bw=rgb2gray(I);
    bw=im2bw(I,graythresh(bw));%采用Otsu方法
    BW1 = imfill(bw, 'holes');%孔洞填充
    figure;imshow(BW1);title('分离出的药板')
    

    是不是很纯洁了

    • 将药板旋转至水平
      将药板二值化之后,取出边缘,Hough变换求出线段斜率,得到角度,然后通过imrotate()函数进行自动旋转。这一步重点在于标出直线,求得斜率。
      霍夫变换传送门

    废话不多说,代码:

    clear,clc,close all;
    I=imread('C:\Users\Administrator\Desktop\1\1.tiff');
    bw=rgb2gray(I);
    bw=im2bw(I,graythresh(bw));%采用Otsu方法
    bw=double(bw);
    BW=edge(bw,'canny');
    %霍夫变换
    [H,T,R]=hough(BW);
    P=houghpeaks(H,4,'threshold',ceil(0.3*max(H(:))));
    lines=houghlines(BW,T,R,P,'FillGap',50,'MinLength',7);
    max_len = 0;
    %figure,imshow(BW),title('直线标识产物');
    %hold on;
    for k=1:length(lines)
    xy=[lines(k).point1;lines(k).point2];
    %plot(xy(:,1),xy(:,2),'LineWidth',2,'Color','green');
    % 标出线段的起始和终端点
    %plot(xy(1,1),xy(1,2),'x','LineWidth',2,'Color','yellow');
    %plot(xy(2,1),xy(2,2),'x','LineWidth',2,'Color','red');
        len=norm(lines(k).point1-lines(k).point2);
        Len(k)=len;
        if (len>max_len)
            max_len=len;
            xy_long=xy;
        end
    end
    [L1 Index1]=max(Len(:));
    % 求得最长线段的斜率
    K1=-(lines(Index1).point1(2)-lines(Index1).point2(2))/...
        (lines(Index1).point1(1)-lines(Index1).point2(1))
    angle=atan(K1)*180/pi
    A = imrotate(I,-angle,'bilinear','crop');% imrorate 是逆时针的所以取负
    figure; imshow(A);title('旋转后的药板')
    

    现在老规矩就是贴上结果:
    这是提取的边缘
    旋转正的图片
    旋转的角度8.9726
    当然你可以用眼睛看着调,除了有点low之外。。

    • 提取药板中药丸的位置信息
      简单点说就是把药丸框起来。用到regionprops函数。
    %在二值图中确定出标记位置信息
    B=rgb2gray(A);
    B=im2bw(A,graythresh(A));
    L = bwlabel(~B);
    stats = regionprops(L, 'BoundingBox');
    %在旋转后的图像中标记
    figure; imshow(A);title('旋转后的药板(标记药丸位置)')
    hold on;
    for i = 1 : length(stats)
        if stats(i).BoundingBox(1)>10
        rectangle('Position', stats(i).BoundingBox, 'edgecolor', 'r','LineWidth',3);
        end
    end
    

    运行结果:
    标记药丸
    可能有人说了,你咋标成这个样子??这我也不想啊,otsu分割完只能弄成这样。

    • 基于颜色特征的区域分割
      “早干嘛去了,一开始就应该用这个东西。。”我不服啊,什么东西刚开始弄就很十全十美。代码有个重构的过程,人类更有个从猿人进化到智人的阶段。
      首先看张图:
      这是图
      你有什么发现?是不是感觉两个图就像一个夫妻,一阴一阳,一上一下。没错,这是原始图片分别在y颜色空间和cb颜色空间图像。
    ycbcr=rgb2ycbcr(A);
    y=ycbcr(:,:,1);
    cb=ycbcr(:,:,2);
    cr=ycbcr(:,:,3);
    
    thr_y=graythresh(y);
    bw_y=im2bw(y,thr_y);
    
    thr_cb=graythresh(cb);
    bw_cb=im2bw(cb, thr_cb);
    

    将两个颜色空间的图像取反,相加,即B=~bw_y+~bw_cb,结果如下:
    这图有没有很强
    剩下的我想你们也知道该怎么办——做一下形态学运算,再框起来
    结果:
    这是最后的图
    附代码,亲测

    clear,clc,close all;
    I=imread('C:\Users\Administrator\Desktop\1\1.tiff');
    bw=rgb2gray(I);
    bw=im2bw(I,graythresh(bw));%采用Otsu
    %将药板从黑色背景中分离
    BW1 = imfill(bw, 'holes');
    figure;imshow(BW1);title('分离出的药板')
    
    bw=double(bw);
    BW=edge(bw,'canny');
    %哈佛变换
    [H,T,R]=hough(BW);%H是霍夫变换矩阵,T、R是p和θ值向量,在这些值上产生霍夫变换BW是二值图像
    P=houghpeaks(H,4,'threshold',ceil(0.3*max(H(:))));
    lines=houghlines(BW,T,R,P,'FillGap',50,'MinLength',7);%%lines为结构数组,长度等于找到的线段数
    max_len = 0;
    for k=1:length(lines)
        xy=[lines(k).point1;lines(k).point2];
        len=norm(lines(k).point1-lines(k).point2);
        Len(k)=len;
        if (len>max_len)
            max_len=len;
            xy_long=xy;
        end
    end
    [L1 Index1]=max(Len(:));
    % 求得线段的斜率
    K1=-(lines(Index1).point1(2)-lines(Index1).point2(2))/...
        (lines(Index1).point1(1)-lines(Index1).point2(1))
    angle=atan(K1)*180/pi
    A = imrotate(I,-angle,'bilinear','crop');% imrate 是逆时针的所以取负
    
    %颜色特征的区域分割
    ycbcr=rgb2ycbcr(A);
    y=ycbcr(:,:,1);
    cb=ycbcr(:,:,2);
    cr=ycbcr(:,:,3);
    
    thr_y=graythresh(y);
    bw_y=im2bw(y,thr_y);
    
    thr_cb=graythresh(cb);
    bw_cb=im2bw(cb, thr_cb);
    
    B=~(~bw_y+~bw_cb);
    
    se=strel('disk',5);
    B=imclose(B,se);
    B=imopen(B,se);
    
    %确定出标记位置
    L = bwlabel(~B);
    stats = regionprops(L, 'BoundingBox');
    %在旋转后的图像中标记
    
    figure; imshow(A);title('旋转后的药板1(标记药丸位置)')
    hold on;
    for i = 1 : length(stats)
        if stats(i).BoundingBox(1)>10
        rectangle('Position', stats(i).BoundingBox, 'edgecolor', 'r','LineWidth',3);
        end
    end
    
    展开全文
  • 图像分割实例--MATLAB代码

    万次阅读 多人点赞 2018-07-04 11:00:55
    处理图像是一张药板图,我们的处理目标有以下几个: 1. 将药板从黑色背景中分离(药板部分显示为白色,背景显示为黑色); 2. 根据分割结果将药板旋转至水平; 3. 提取药板中的药丸的信息; 采用两种方法执行...
    待处理图像是一张药板图,我们的处理目标有以下几个: 
    1. 将药板从黑色背景中分离(药板部分显示为白色,背景显示为黑色); 
    2. 根据分割结果将药板旋转至水平; 

    3. 提取药板中的药丸的信息; 

    采用两种方法执行,详细注释见代码

    clc;clear all;  
    %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
    %% 法一:用otsu对图像进行分割
    img=imread('1.jpg');       
    I=rgb2gray(img);  
    T=graythresh(I);    %采用Otsu方法计算最优阈值T对图像二值化;  
    Ibw1 = im2bw(I,T);
    figure, imshow(Ibw1);title('Otsu-图1');
    %% 接着将孔洞填充
    BW1 = imfill(Ibw1, 'holes');%孔洞填充
    figure;imshow(BW1);title('分离出的药板')
    %% 将药板旋转至水平 
    %将药板二值化之后,取出边缘,Hough变换求出线段斜率,得到角度,然后通过imrotate()函数进行自动旋转。这一步重点在于标出直线,求得斜率。
    bw=double(Ibw1);
    BW=edge(bw,'canny');
    %霍夫变换
    [H,T,R]=hough(BW); %H:累计数组  ,T:H对应的θ, R:H对应的ρ,实际上H的大小就是R×T,
    P=houghpeaks(H,4,'threshold',ceil(0.3*max(H(:))));%峰值提取 --peaks = houghpeaks(H,numpeaks,param1, val1)  
    %Numpeaks:指定需要检测的峰值个数; Param1:可以是'Threshold'或'NHoodSize'
    %'Threshold'-指定峰值的域值,默认是0.5*max(H(:)); 
    %'NHoodSize'-是个二维向量[m,n],检测到一个峰值后,将峰值周围[m,n]内元素置零。
    lines=houghlines(BW,T,R,P,'FillGap',50,'MinLength',7);%画直线段 lines = houghlines(BW,theta, rho, peaks,param1, val1)
    %Lines:结构数组,大小等于检测到的直线段数,每个单元包含point1、point2:线段的端点,Theta、rho:线段的theta和rho
    max_len = 0;
    figure,imshow(BW),title('直线标识产物');
    hold on;
    for k=1:length(lines)
    xy=[lines(k).point1;lines(k).point2];
    %plot(xy(:,1),xy(:,2),'LineWidth',2,'Color','green');
    % 标出线段的起始和终端点
    %plot(xy(1,1),xy(1,2),'x','LineWidth',2,'Color','yellow');
    %plot(xy(2,1),xy(2,2),'x','LineWidth',2,'Color','red');
        len=norm(lines(k).point1-lines(k).point2);
        Len(k)=len;
        if (len>max_len)
            max_len=len;
            xy_long=xy;
        end
    end
    [L1 Index1]=max(Len(:));
    % 求得最长线段的斜率
    K1=-(lines(Index1).point1(2)-lines(Index1).point2(2))/(lines(Index1).point1(1)-lines(Index1).point2(1));
    angle=atan(K1)*180/pi;
    A = imrotate(img,-angle,'bilinear','crop');% imrorate 是逆时针的所以取负
    figure; imshow(A);title('旋转后的药板')
    %% 提取药板中药丸的位置信息 --简单点说就是把药丸框起来。用到regionprops函数。
    %在二值图中确定出标记位置信息
    B=rgb2gray(A);
    B=A;
    B=im2bw(A,graythresh(A));
    L = bwlabel(~B);%返回一个和B大小相同的L矩阵,包含了标记了B中每个连通区域的类别标签,这些标签的值为1、2、num(连通区域的个数)。
                    %n的值为4或8,表示是按4连通寻找区域,还是8连通寻找,默认为8。
    stats = regionprops(L, 'BoundingBox');%用来度量图像区域属性的函数。
        %测量标注矩阵L中每一个标注区域的一系列属性。L中不同的正整数元素对应不同的区域。
        %例如:L中等于整数1的元素对应区域1;L中等于整数2的元素对应区域2;以此类推。
        %返回值STATS是一个长度为max(L(:))的结构数组,结构数组的相应域定义了每一个区域相应属性下的度量。
        %properties 可以是由逗号分割的字符串列表、饱含字符串的单元数组、单个字符串 'all' 或者 'basic'。
        %如果 properties 等于字符串 'all',则所有下述字串列表中的度量数据都将被计算。
        %如果 properties 没有指定或者等于 'basic',则属性: 'Area', 'Centroid', 和 'BoundingBox' 将被计算。
    
    %在旋转后的图像中标记
    figure; imshow(A);title('旋转后的药板(标记药丸位置)')
    hold on;
    for i = 1 : length(stats)
        if stats(i).BoundingBox(1)>10
        rectangle('Position', stats(i).BoundingBox, 'edgecolor', 'r','LineWidth',3);
        end
    end
    %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %% 法二:基于颜色特征的区域分割 
    ycbcr=rgb2ycbcr(A);
    y=ycbcr(:,:,1); %亮度
    cb=ycbcr(:,:,2); %彩度
    cr=ycbcr(:,:,3); %浓度
    
    thr_y=graythresh(y);
    bw_y=im2bw(y,thr_y);
    figure; 
    imshow(bw_y);
    
    thr_cb=graythresh(cb);
    bw_cb=im2bw(cb, thr_cb);
    figure; 
    imshow(bw_cb);
    %将两个颜色空间的图像取反,相加
    B1=~(~bw_y+~bw_cb);
    %做一下形态学运算,再框起来
    se=strel('disk',5); %%生成圆形结构元素
    B1=imclose(B1,se); %%用生成的结构元素对图像进行闭运算
    B1=imopen(B1,se); %%用生成的结构元素对图像进行开运算
    
    %确定出标记位置
    L1 = bwlabel(~B1);
    stats1 = regionprops(L1, 'BoundingBox');
    %在旋转后的图像中标记
    
    figure; imshow(A);title('旋转后的药板1(标记药丸位置)')
    hold on;
    for i = 1 : length(stats1)
        if stats1(i).BoundingBox(1)>10
        rectangle('Position', stats1(i).BoundingBox, 'edgecolor', 'r','LineWidth',3);
        end
    end
    参考:https://blog.csdn.net/jiji_vip/article/details/72487804?utm_source=itdadao&utm_medium=referral
    展开全文
  • 图像处理岗位面试题搜罗汇总

    万次阅读 多人点赞 2018-06-21 15:11:46
    原文...传统图像处理部分 图像处理基础知识 彩色图像、灰度图像、二...

    传统图像处理部分

    图像处理基础知识

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

    彩色图像: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的草图,然后快速估算支架和各柱的高度,以及球的半径,算出各部分体积,然后和各部分密度运算,最后相加得出一个结果。

    展开全文
  • 图像处理岗位面试题

    千次阅读 2019-03-31 19:19:46
    图像处理基础知识 彩色图像、灰度图像、二值图像和索引图像区别? 彩色图像:RGB图像。灰度图像:0-255像素值。二值图像:0和1,用于掩膜图像。 索引图像:在灰度图像中,自定义调色板,自定义输出256种颜色值。 ...

    转载自: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的草图,然后快速估算支架和各柱的高度,以及球的半径,算出各部分体积,然后和各部分密度运算,最后相加得出一个结果。

    展开全文
  • 霍尔夫变换是图像处理中从图像中识别几何形状的基本方法之一。 原理:在原始图像坐标系下的一个点(直线)对应了参数坐标系下的一条直线(点)。 OpenCV提供了如下三种霍夫变换相关的函数: HoughLines:检测...
  • 进一步熟悉一下halcon怎么用,图像处理的理论学习暂停。 参考书籍:《Halcon学习教程》(王海勇) regiongrowing(Image, Regions, Row, Column, Tolerance, MinSize) 用区域生长法对单通道图像做图像分割。 首先用...
  • 开始halcon语义分割的第一步是创建一个用于深度学习的语义分割的模型,在这个模型中将设置各种用于深度学习的参数。 1、模型的数据结构如下: DLDataset { 'image_dir' : 所有图像文件夹路径 'segmentation_...
  • 一、目标 1 将药板从黑色背景中分离(药板部分显示为白色,背景显示为黑色... (1)首先将图像转为灰度图像,并做二值化处理,并采用闭运算将胶囊边缘平滑处理。得到图像如下所示: (2)利用imfill填充命令将...
  • 它使用MVTec药丸数据集。 四个部分是: * 1.数据集预处理。 * 2.训练模型。 * 3.评估训练后的模型。 * 4.推断新图像。 * *此示例涵盖第4部分:推理(应用程序) *在新图像上训练有素的模型。 * *请注意:此脚本使用...
  • 阅读目录入门Bootstrap4组件警报链接颜色附加内容解除JavaScript行为事件徽章药丸徽章链接浏览路径更换隔板辅助功能按钮例子禁用文字换行按钮标签轮廓按钮尺码活跃状态禁用状态按钮插件切换状态复选框和单选按钮方法...
  • 打开halcon,按下ctrl+e打开halcon自带例程。工业领域->制药业->classify_pills_auto_select_features.hdev * This example shows how to use the calculate_feature_set * procedure library together with...
  • 它使用MVTec药丸数据集。 * *四个部分是: * 1.数据集预处理。 * 2.训练模型。 * 3.评估训练后的模型。 * 4.推断新图像。 * *此示例包含第1部分:“数据集预处理 dev_update_off () *在此示例中,在执行预处理...
  • 它使用MVTec药丸数据集。 * *四个部分是: * 1.数据集预处理。 * 2.训练模型。 * 3.评估训练后的模型。 * 4.推断新图像。 * *此示例包含第2部分:“模型训练”。 * *请注意:此脚本需要第1部分的输出: * segment_...
  • 以下内容转自...amp;wfr=spider&amp;for=pc 图像分类领域 1)MNIST 经典的小型(28x28 像素)灰度手写数字数据集,开发于 20 世纪 90 年代,主要用于测试当时最复杂的模型...
  • 云计算+大数据+AI+物联网

    千次阅读 2019-08-26 21:21:37
    一般谈云计算的时候会提到大数据、谈人工智能的时候会提大数据、谈人工智能的时候会提云计算……感觉三者之间相辅相成又不可分割。但如果是非技术的人员,就可能比较难理解这三者之间的相互关系,所以有必要解释一下...
  • 三通道图像的灰度值是是三个单通到图像灰度值的组合,值越大看起来图像越亮,值越小图像越暗,在三通道图像上看哪部分的哪种颜色越深,证明在该部分的哪种颜色分量越大,反映到该通道上越亮 高斯混合模型: 1....
  • JAVA--图形界面化

    2015-07-17 22:13:12
    图形界面继承体系Component 所有图形界面超类 抽象类,具有图形表示能力的类Container 容器: 就是可以将对象存储进去 存储的是图形界面上的内容,菜单,按钮... Panel – 面板 窗体分割可以存储按钮容器 Dialog –
  • 来源:星环科技数据猿官网 | www.datayuan.cn今日头条丨一点资讯丨腾讯丨搜狐丨网易丨凤凰丨阿里UC大鱼丨新浪微博丨新浪看点丨百度百家丨博客中国丨趣头条丨腾讯...
  • CVPR 2019 追踪之论文纲要(修正于2020.08.27)讲在前面论文目录 讲在前面 论坛很多博客都对论文做了总结和分类,但就医学领域而言,对这些论文的筛选信息显然需要更加精细的把控,所以自己对这1400篇的论文做一个...
1 2
收藏数 35
精华内容 14
关键字:

图像处理 药丸分割