• MulinB按:最近打算好好学习一下几种图像处理和计算机视觉中常用的 global optimization (或 energy minimization) 方法,这里总结一下学习心得。分为以下几篇: 1. Discrete Optimization: Graph C

    原文:http://blog.csdn.net/mulinb/article/details/9079645

    MulinB按:最近打算好好学习一下几种图像处理和计算机视觉中常用的 global optimization (或 energy minimization) 方法,这里总结一下学习心得。分为以下几篇:

    1. Discrete Optimization:  Graph Cuts and Belief Propagation

    2. Quadratic Optimization: Poisson Equation and Laplacian Matrix (本篇)

    3. Variational Methods for Optical Flow Estimation

    4. TODO: Likelihood Maximization (e.g., Blind Deconvolution)


    2. Quadratic Optimization: Poisson Equation and Laplacian Matrix

    Quadratic Optimization (Least Squares Minimization)在图像处理中的魅力要从SIGGRAPH 02和03年的两篇Gradient Domain Image Editing文章说起:Fattal的HDR Compression[1] 和Perez的Poisson Image Editing [2]。 其后,Levin的两篇文章Colorization [3]和Closed-Form Matting [4]更是将其魅力展现的淋漓尽致。而Farbman的基于Weighted Least Squares的WLS filter [5]也是在Edge-preserving Filter领域名声大噪。由于目标函数是quadratic, 这类问题的求解一般比较容易,大多都可以最终归结为求解一个大型稀疏线性方程组。而数值求解大型线性方程组是一个由来已久的问题,有着各种现成的solver,更是有着为以上这类问题量身定做的solver,见下文solver小节。

    题外话:以色列的耶路撒冷希伯来大学(The Hebrew University of Jerusalem)的Lischinski教授貌似很偏爱这类方法,上面提到的这些文章大多有他的署名。


    2.1 Problem I: Gradient Domain Image Editing

    有心理学为证(见Poisson Image Editing [2]文章的introduction部分),对图像的gradient进行修改可以产生比较不容易感知到的artifacts,这使得很多图像编辑的工作可以放到gradient domain使得效果很逼真,比如下图的图像拼合例子(图例来自[2]):


    其实对gradient domain进行修改而获得逼真的编辑效果由来已久,最早见于1983年Burt-Adelson的Laplacian Pyramid [6]图像融合(这里有个简洁的中文介绍),这是题外话。在gradient domain进行图像编辑的pipeline一般如下(图例修改自ICCV 2007 Course -- Gradient Domain Manipulation Techniques,顺便赞一个,nice ppt!):


    其中第一步的gradient processing根据不同的需求有具体的操作,比如HDR Compression里是将较大的gradient value进行削弱,而上面的图像拼合例子(Seamless Clone)则是将源图像的gradient拷贝到目标区域。而其中第二步中由gradient重建出新图像并非那么容易,因为经过编辑后的gradient一般是不可积分的,这时Quadratic Optimization粉墨登场。


    假设待求图像为I,修改后的已知gradient是G,则通过Least Squares Minimization可以将问题formulate成如下(使得待求图像I的gradient在L2 norm下尽量接近G):


    注意其中的约束条件,比如,在图像拼合例子中,非编辑区域的像素是已知的,在求解编辑区域的像素时,边界上的像素值是约束条件。上面的formulation是假设图像I是定义在x-y连续空间的函数,所以其实上述目标函数是关于I的functional(泛函,也就是“函数的函数”)。使用calculus of variation(变分法)中的Euler-Lagrange Equation (one unknown function, two variables)可以将其转化为一个非常经典的偏微分方程形式,这就是Poisson Equation

          

    注意其中G是已知的,I是未知的,Δ是Laplacian operator,div是divergence operator。当已知边界像素值时,该偏微分方程具有第一类边界条件(Dirichlet boundary condition),比如图像拼合;当处理整个图像时,该偏微分方程具有第二类边界条件(Neumann boundary condition),即已知边界导数值(设为0),比如HDR Compression。


    上面的formulation是在x-y连续空间(像素坐标是连续的),而用于图像处理时,一般需要将其离散化(因为事实上像素坐标(x,y)是整数),上面相应的偏微分形式可以使用有限差分(finite difference)形式近似代替。具体来讲,离散化的discrete Laplacian operator如下,


    而divergence operator中的一阶偏导可以用前向或者后向差分近似(由于G本身是由gradient得来,一般如果之前计算gradient使用前向差分,那么这里计算div就使用后向差分,这样使得两次差分的结果等价于一次二阶中心差分,具体参考[1]),比如这里的divG可以由以下后向差分近似,


    于是,整个Poisson Equation离散化之后,每个pixel都有一个线性方程,假设图像有N个pixel,那么整个Poisson Equation就成了一个包含N个方程的大型方程组。如果将这个大型方程组写成矩阵形式(假设将待求图像I拉成一个长的vector,用x表示,将已知的divG也拉成一个长的vector,用b表示),离散化的Poisson Equation变成了经典的Ax=b形式。以5×5的图像为例,假设待求图像I为如下形式(每个pixel的值都是未知):


    将其拉成列向量x(按列展开),则整个Discrete Poisson Equation (with Neumann boundary condition)写成Ax=b形式即,


    该矩阵A可以直接从Laplacian operator得来,一般称为Laplacian Matrix(其实如果将图像看成graph,该矩阵即为graph theory中的Laplacian Matrix)。注意,对角线上值为2和3的元素是对应在图像边界上的pixel(因为其discrete Laplacian operator无法完整展开,包含了一些不存在的neighboring pixel),如果将边界条件改为Dirichlet boundary condition并且未知区域周边的pixle都是已知的话,对角线上的元素就全为4,比如下面的例子。假设待求图像I为如下形式(未知pixel的周边pixel是已知):

    则未知向量x包含9个元素,整个Discrete Poisson Equation (with Dirichlet boundary condition)变成以下形式,

    注意等式右侧包含了边界已知pixel的值。这里的Laplacian Matrix较为规整,主要是因为所有的未知pixel处的discrete Laplacian operator可以完整的展开。


    总之,上面的discrete Poisson Equation都可以归结为求解一个大型线性方程组,其中的Laplacian Matrix具有以下特点

    1. 对角线元素为non-negative;

    2. 非对角线元素为non-positive;

    3. 对称(symmetric);

    4. 正定或半正定(positive semidefinite);

    5. 属于分块对角阵。

    下面的solver小节再讨论如何求解这样的线性方程组。另外,其实如果直接对上面Least Squares Minimization的目标函数进行离散化,也可以得到相同的方程组(省去了应用Euler-Lagrange Equation的步骤),参见文章[2]的推导过程。


    如果进一步对上述的Gradient Domain Image Editing Pipeline进行推广,将原始图像考虑进来(注意,前面的方法是完全由新的gradient重建图像,不考虑原始图像的影响),这样可以得到一个更为强大的framework,这就是GradientShop[7] (其实之前Levin的Colorization[3],以及Lischinski的Interactive Local Adjustment[8],和Farbman的WLS filter[5]都可以算作这个framework的特例),新的框架如下:


    假设constraint image为图像S(可以是原始图像本身或者经过处理后的图像、用户输入的像素值等),新的gradient为G,待求图像为I,则Least Squares Minimization的目标函数推广为如下:


    其中lambda为weighting factor,用来权衡constraint image和new gradient对待求图像的影响,可以整个image用统一的lambda值,也可以用一个weighting map为每个pixel赋上不同的lambda值。比如,在Levin的Colorization[3]中,待求的图像I是chrominance通道(比如YUV中的U和V通道),G=0,S是用户输入的scribbles,lambda_2是scribble的mask(有scribble为1,否则0),lambda_1是根据已知灰度图中相邻pixel的affinity进行赋值(pixel灰度值越相似,值越大),这样获得的Laplacian Matrix可以使得用户输入的scribble根据pixel affinity进行有效的propagation。再以5×5图像为例,假设图像M(元素为m_xy)为S的reverse mask(有输入为0,没有输入为1),S的元素用s_xy表示(无用户输入处的pixel为0),用w_{x1y1-x2y2}表示pixel(x1,y1)和pixel(x2,y2)的affinity weight(已经归一化),则Colorization的整个线性方程组可以表示为如下(右键查看大图):


    可见,其矩阵跟上述Poisson Equation中的矩阵形式一模一样(满足Laplacian Matrix的几个特点,其实也可以称之为Laplacian Matrix),只是矩阵元素的值不再是固定值,而是跟输入有关,而且是spatially varying。注意:这里使用的neighborhood是四邻域,Levin的代码中使用的是8邻域。


    GradientShop framework的另一个特例是WLS filter [5]。令constraint image S为输入图像本身,G=0,而lambda_1是根据输入图像的gradient进行spatially varying weighting:某个pixel的gradient越大,lambda_1越小(期待与输入图像较为接近);gradient越小,lambda_1越大(进行smoothing)。这样的效果就是进行edge-preserving smoothing,在decomposition-manipulation-recombination时可以避免artifacts的产生。


    最后值得一提的是,在Gradient Domain进行操作的其他work有:Diffusion Curves [9],Gradient Domain Painting [10] 等,都是很有趣的东东。另外,没有通过解线性方程组而是通过操作Laplacian Pyramid的local Laplacian filter [11]也是很有趣的work,个人非常喜欢,能生成类似于梦幻般的图像效果并且没有什么artifacts,例如下图。



    2.2 Problem II: Closed-Form Matting

    Image Matting就是精确抠图问题,主要是用来抠出毛发等具有半透明边界的物体,可以用以下方程描述:

    给一个输入图像I,以及部分foreground和background的标记(用Trimap或者scribbles标记,如下图),目标是求出alpha matte, F和B。


    Trimap中白色部分和黑色部分分别是已经标记为F和B的区域,所以matting的主要目的是求出灰色未知区域的alpha matte值(介于0到1之间的值)。基于scribbles的输入相当于稀疏的Trimap,除了白色和黑色的scribbles外,都是未知区域。较为经典的几种算法包括Bayesian MattingPoisson MattingClosed-Form MattingRobust Matting等,这里还有个网站专门评测每年新提出的matting算法,这里有篇专门介绍matting算法的2007年的survey (by Jue Wang and Michael Cohen)。近年来的很多新算法其实大多是基于Closed-Form Matting和Robust Matting做improvement的,比如基于Closed-Form Matting的有Non-local Matting和KNN Matting,基于Robust Matting的有Shared-Matting,Global Sampling Matting,Weighted Color and Texture Matting,以及各种带有sampling字样的算法。这里主要介绍一下Closed-Form Matting。


    Levin的Closed-Form Matting [4] 主要基于一个非常有见地的假设 -- Local Linear Model,大概意思就是,在一个很小的local window里,alpha matte应当可以用图像的三个颜色通道线性表出(linear combination),即下图所示:

    这个模型的精妙之处在于:第一,将原有的composition equation中的三个未知变量alpha,F,B解耦合,变成了未知变量alpha,a,b,而三个未知变量之间不再有相乘的关系,也就是nonlinear model转化成了linear model;第二,由于a和b是在一个local window里不变的,而每个pixel都被好几个重叠的local window覆盖,这些互相重叠的local window使得用户的输入可以有效进行propagation。有了这个模型,可以直接对其进行Regularized Least Squares Minimization来求解alpha,即:


    其中w_j是每个pixel j附近的local window,S是用户输入的scribbles,epsilon是regularization parameter(该regularization term相当于prior:希望alpha matte较为smooth)。该optimization中包含三个未知变量(每个pixel:alpha, a, b),但幸运的是,目标函数相对于每个未知变量都是quadratic的,因此可以推导出其closed-form的解(分别对alpha,a,b求偏导并令式子等于0)。仔细观察目标函数,发现其关于a和b比较简单:每个pixelj可以单独计算。如果先将alpha看做已知,把目标函数对a和b求偏导并令其等于0,可以很容易计算出每个pixelj处a和b的表达式(包含alpha),然后再将其代入目标函数中,可以得到一个只包含一个未知变量alpha的目标函数(仍然是quadratic),写成矩阵形式如下(注意,这时求alpha不像刚才求a和b那么简单,无法对每个pixel分别求出alpha,因为每个pixel的未知量alpha与其他pixel的未知量有关联,只能通过求解线性方程组才能求出alpha):

    其中alpha是所有pixel的alpha value组成的列向量,其中L是可以由输入图像计算出的已知矩阵,Levin称之为Matting Laplacian Matrix,与前面介绍的Poisson Equation中的Laplacian Matrix有着很一致的形式和功能(propagation user input)。假设图像有N个pixel,Matting Laplacian是一个N×N的矩阵,其中在(i,j)处的元素为:


    其中w_k是local window,|w_k|是local window内pixel的个数,注意I_i是3×1的vector(即rgb三个channel的pixel值),I_3表示3×3单位矩阵,其他几个符号如下表示:

      

    可以看出,只有当i和j代表的pixel处于同一个local window时,元素(i,j)才不为0。将δ_ij单独提出来(其实只有对角线上的元素有这一项),令


    Levin称之为Matting Affinity,跟前面colorization中用到的affinity相似,只是这里的affinity值可能为负。如果将local window size为2×2(只是为了方便直观显示,事实上一般用奇数边长的window size),以5×5的图像为例,Matting Laplacian可以表示成如下形式(注意:只要两个相邻的pixel能放入一个2×2的window,其affinity就不为空,因此事实上每个pixel周围8邻域的pixel的affinity都不为空):


    注意其中形如的元素表示的是输入图像中pixel(3,3)和pixel(3,4)的affinity。由上可见,Matting Laplacian的形式与colorization中的Laplacian Matrix形式基本一致(如果colorization也用8邻域,那么形式一模一样)。考虑进去目标函数的constraint(即input scribbles),可以使用跟上面colorization类似的mask列出方程组,或者使用Levin的TPAMI文章里介绍的方法。这里有Levin提供的Matlab代码。需要注意的是:这里的对角线元素不一定非负(non-negative),非对角线元素也不一定非正(non-positive),但是整个矩阵仍然是半正定(positive semidefinite)(Levin的paper [4]里有证明),当然也是对称阵。(注意有些为前面的Laplacian Matrix特别定制的解线性方程组的算法不一定适用于这里的Matting Laplacian Matrix,比如[13],针对的是非对角元素必须non-positive)。


    另外值得一提的是,使用和这里同样的Local Linear Model,假设alpha matte是一个给定的guidance图像,将目标改成要计算出从原始图像到guidance图像的local linear transformation(即求出a和b的值),将global optimization变为local window内的optimization,可以导出一个计算起来非常快的edge-preserving filter,这就是guided filter [12]。该filter由于其计算速度快,可以作为经典的bilateral filter的近似,很受欢迎。


    2.3 Solvers: Solving Large Sparse Linear System

    解大型稀疏线性方程组是一个很well-studied的问题,一般来讲,解法分为两大类:直接法(direct solver)和迭代法(iterative solver)。直接解法一般指高斯消元法(Gaussian Elimination),比如对于普通矩阵用LU Decomposition,对于对称正定阵用Cholesky Decomposition。这类算法的问题是,计算的过程中稀疏矩阵会变成稠密矩阵,如果矩阵规模较大(对于图像处理来讲很正常,比如对于1000×1000的图像,矩阵规模达到1000000×1000000),存储计算过程中的稠密矩阵都是问题,这就是文献中经常提到的fill-in问题[14]。这类方法的另一个问题是不太容易并行化。当然,也有很多新的direct算法克服了这些问题,参见Tim Davis的大作Direct Methods for Sparse Linear Systems [15](貌似Matlab里的backslash用的就是direct算法)。不过在computer vision中较受欢迎的还是iterative算法,推荐一本很棒的教科书,就是Yousef Saad的Iterative Methods for Sparse Linear Systems [16]。在ICCV 2007 gradient course中,有一个很棒的总结(section3 ppt)。这里也有个不错的总结。这里有个很棒的介绍Jacobi/Gauss-Seidel/SOR的ppt。


    先将上述涉及到的方程组的系数矩阵及可以使用的算法进行一个分类,注意有些算法是对所有矩阵通用的,有些算法只能用于一些特定矩阵。以下分类基本是从上往下呈包含关系:

    1. 普通矩阵(general):LU DecompositionMultigrid method

    2. 对角优势阵(diagonal dominant):Jacobi/Gauss-Seidel/SOR(在diagonal dominant的情况下才收敛);

    2. 对称正定阵(symmetric positive-definite, SPD):Cholesky DecompositionConjugate Gradient,Hierarchical Preconditioning (ABF) [14][17]

    3. M-matrix(非对角元素是non-positive的Laplacian Matrix,包括上述的Poisson Equation,colorization以及WLS filter中的Laplacian Matrix,但是不包括matting中的矩阵):Hierarchical Preconditioning (HSC)[13]

    4. Spatially homogeneous Laplacian Matrix in Poisson Equation(在[13]中被如此称呼,注意跟homogeneous Poisson Equation不同):FFT-based Poisson Solver (or see Chapter 2.2.6, Saad [16]);


    这些涉及到的算法的复杂度如下(参见这里)(N是未知元素的个数,即图像像素个数):

    算法 时间复杂度 适用矩阵类型
    LU Decomposition N^3 General
    Jacobi/Gauss-Seidel N^2 Diagonal dominant
    SOR N^(3/2) Diagonal dominant
    Conjugate Gradient N^(3/2) Symmetric positive-definite
    ABF[17] N^(3/2) Symmetric positive-definite
    HSC[13] N M-matrix (off-diagonal non-positive)
    Multigrid method N General
    FFT-based method NlogN Poisson Equation
    由上面可以看出,一般想要速度快的solver都会用Multigrid method,只是对于irregular的矩阵,quality不是很好。另外由于computer vision中的problem一般都是对称正定阵(甚至大多都是M-matrix),Preconditioned Conjugate Gradient和SOR也很受欢迎。对于M-matrix,今年SIGGRAPH出现的HSC[13]算法也值得一试。



    2.4 Reference

    [1] R. Fattal, D. Lischinski, and M. Werman, "Gradient Domain High Dynamic Range Compression," SIGGRAPH, 2002.

    [2] P. Perez, M. Gangnet, and A. Blake, "Poisson Image Editing," SIGGRAPH, 2003.

    [3] A. Levin, D. Lischinski, and Y. Weiss, “Colorization Using Optimization,” SIGGRAPH, 2004.

    [4] A. Levin, D. Lischinski, and Y. Weiss, “A Closed-Form Solution to Natural Image Matting,” CVPR, 2006. ->TPAMI2008 extension. 

    [5] Z. Farbman, R. Fattal, D. Lischinski, and R. Szeliski, “Edge-Preserving Decompositions for Multi-Scale Tone and Detail Manipulation,” SIGGRAPH, 2008.

    [6] P. Burt and  E. Adelson, "A Multiresolution Spline with Application to Image Mosaics," TOG, 1983.

    [7] P. Bhat, C.L. Zitnick, M. Cohen, and B. Curless, "GradientShop: A Gradient-Domain Optimization Framework for Image and Video Filtering," TOG, 2009.

    [8] D. Lischinski, Z. Farbman, M. Uyttendaelem, and R. Szeliski, “Interactive Local Adjustment of Tonal Values,” SIGGRAPH, 2006.

    [9] A. Orzan, A. Bousseau, H. Winnemöller, P. Barla, J. Thollot, and D. Salesin, "Diffusion Curves: A Vector Representation for Smooth-Shaded Images," SIGGRAPH, 2008.

    [10] J. McCann and N. Pollard, "Real-Time Gradient-Domain Painting," SIGGRAPH, 2008.

    [11] S. Paris, S.W. Hasinoff, J. Kautz, "Local Laplacian Filters: Edge-aware Image Processing with a Laplacian Pyramid," SIGGRAPH, 2011.

    [12] K. He, J. Sun, and X. Tang, "Guided Image Filtering," ECCV, 2010. ->TPAMI 2012 extension. 

    [13] D. Krishnan, R. Fattal, and R. Szeliski, "Efficient Preconditioning of Laplacian Matrices for Computer Graphics," SIGGRAPH, 2013.

    [14] R. Szeliski, "Locally Adapted Hierarchical Basis Preconditioning," SIGGRAPH, 2006.

    [15] T. Davis, "Direct Methods for Sparse Linear Systems," 2006.

    [16] Y. Saad, "Iterative Methods for Sparse Linear Systems," Second Edition, 2003.

    [17] D. Krishnan and R. Szeliski, "Multigrid and Multilevel Preconditioners for Computational Photography," SIGGRAPH Asia, 2011.


    展开全文
  • 1.《图形图像处理-之-一个复杂度为常数的快速局部自适应算法 上篇  》 http://blog.csdn.net/housisong/article/details/2316924 2.《图形图像处理-之-误差扩散 中篇 》 ...3.《图形图像处理-之-误差扩散 下篇 -...

    1.《图形图像处理-之-一个复杂度为常数的快速局部自适应算法 上篇 》
    http://blog.csdn.net/housisong/article/details/2316924
    2.《图形图像处理-之-误差扩散 中篇 》
    http://blog.csdn.net/housisong/article/details/2320688
    3.《图形图像处理-之-误差扩散 下篇 - 更快的速度或更好的效果 》
    http://blog.csdn.net/housisong/article/details/5138874


    4.《图形图像处理-之-一个复杂度为常数的快速局部自适应算法 上篇 》
    http://blog.csdn.net/housisong/article/details/2286776
    5.《图形图像处理-之-一个复杂度为常数的快速局部自适应算法 下篇 》
    http://blog.csdn.net/housisong/article/details/2286804


    6.《YUV视频格式到RGB32格式转换的速度优化 上篇 》
    http://blog.csdn.net/housisong/article/details/1859084
    7.《YUV视频格式到RGB32格式转换的速度优化 中篇 》
    http://blog.csdn.net/housisong/article/details/1866970
    8.《YUV视频格式到RGB32格式转换的速度优化 下篇 》
    http://blog.csdn.net/housisong/article/details/2210594


    9.《图形图像处理-之-任意角度的高质量的快速的图像旋转 上篇 纯软件的任意角度的快速旋转 》
    http://blog.csdn.net/housisong/article/details/1586717
    10.《图形图像处理-之-任意角度的高质量的快速的图像旋转 中篇 高质量的旋转 》
    http://blog.csdn.net/housisong/article/details/1666962
    11.《图形图像处理-之-任意角度的高质量的快速的图像旋转 下篇 补充话题 》
    http://blog.csdn.net/housisong/article/details/1671378


    12.《图形图像处理-之-高质量的快速的图像缩放 上篇 近邻取样插值和其速度优化 》
    http://blog.csdn.net/housisong/article/details/1404896
    13.《图形图像处理-之-高质量的快速的图像缩放 中篇 二次线性插值和三次卷积插值 》
    http://blog.csdn.net/housisong/article/details/1452249
    14.《图形图像处理-之-高质量的快速的图像缩放 下篇 三次线性插值和MipMap链 》
    http://blog.csdn.net/housisong/article/details/1528392
    15.《图形图像处理-之-高质量的快速的图像缩放 补充 使用SSE2优化 》
    http://blog.csdn.net/housisong/article/details/6318890


    16.《图形图像处理-之-彩色转化到灰度的速度优化 》
    http://blog.csdn.net/housisong/article/details/3884368

    
    展开全文
  • 嵌入式图像处理算法优化指南,适用于任何基于ARM或PC平台的视觉应用程序开发 转载2015-08-05 15:09:15 标签:目标识别与跟踪视觉定位与目标识别视觉算法研究与验证视频图像处理开发板it 第一章 绪论 ...

    http://blog.sina.com.cn/s/blog_1368ebb6d0102vuhg.html


    嵌入式图像处理算法优化指南,适用于任何基于ARM或PC平台的视觉应用程序开发

    转载2015-08-05 15:09:15

    第一章 绪论

    1.1 

    计算机视觉/图像处理研究者的困惑

    作为一名从业近10年、一直致力于视频目标识别和跟踪的研究者,笔者认为视频图像处理的应用远远没有达到其应有的程度。究其原因,可能包括如下几个方面:

    n  科研单位和高校的研究者多以理论研究为主,偏论文的评价体系使得研究者更关注理论是否新颖,忽略了算法效率及实用性,造成绝大多数的研究成果在实际应用中无法应用或成本太高。

    n  Mathlab等工具和OpenCV等库函数加快了研究者出论文的效率,并加快了功能初步验证的过程,但其带来的负面影响不容小觑。由于对现有工具产生了很强的依赖,缺少对图像处理技术本质的认识及经验积累,需要新的功能时无法高效实现。

    n  图像处理本身是一门工程技术,在一定程度上不具有“可推导性”和“通用性”,要想解决某一问题,必须针对性地提出解决方案才有可能研制出高效的功能模块。

    n  硬件平台的依赖性太强,研制成本高。之前的图像处理算法通常运行于DSP或FPGA平台上,硬件研制和移植成本动辄上百万,使得普通开发者望而却步。

    1.2 

    让嵌入式图像处理技术流行起来

    为加快图像处理技术的工程应用,“让嵌入式图像处理技术流行起来”,嵌视科技倡导开发者遵循如下两个原则:

    n  除可购置的功能芯片外,针对特定应用设计针对性的解决方案,并自己编写所有的算法,保证整个模块的高效运行。在这个问题上周围经常有反对的声音,说自己实现的算法肯定没有成熟的库函数的快。在单个标准的功能函数方面,我们承认库函数在效率方面并不低,但结果往往是笔者开发的应用模块通常比调用库函数的快很多倍。比如,在目标跟踪的应用中,笔者开发的模块在双核2.4G

    的PC上耗时只有

    0.3ms

    ,事后分析发现所有代码没有用到任何一个“完整”的库函数(在此基础上开发了

    QS-PTE9

    中的“视觉跟踪示例程序”)。

    “磨刀不误砍柴工”,只有熟练掌握图像处理的实现技巧,灵活设计应用模块的针对性实现方案,才能开发出高效稳定的嵌入式视觉应用模块,本手册将通过实例的形式带你进入这条路线。当然我们只是领进门,修行还得靠自身

    n  选用基于ARM的嵌入式图像处理平台,以节省硬件及移植成本。原因在1.3节中介绍。

    为节省彼此的时间,本手册推崇言简意赅的原则,希望您能理解。第二章 高效视频图像处理的几个基本原则

    高效视频应用模块的开发更多需要的是长时间的经验积累,在这里我们仅仅列出一些原则性的经验:

    • 算法级的优化或简化永远放到第一位:算法的计算复杂度决定了经过优化后能够达到的最佳性能,没有好的算法作为基础,一切优化都是白搭。

    • 代码优化是必不可少的

    :同一个算法,不同的人实现出来效率方面可能存在10

    倍以上的差距,消除这10倍以上的差距是开发嵌入式视觉应用模块必须掌握的基本技能。

    算法级的优化属于算法设计的问题,是图像处理研究的重点,不同应用差别很大,本手册不作介绍。

    这里列出图像处理方面代码优化的几个基本原则:

    • 重点优化针对每个像素的操作,即for

    循环里面的:理由再简单不过了,假设我们要处理的图像是30万像素的,每个for循环减少10次运算就减少了300万次运算,那效率方面就会提高很多。

    • 不要在大的for

    循环里面调用函数:调用一次函数就涉及到函数寻址、参数传递过程,如果对每个像素调用一次函数想想会浪费多少时间啊。

    • 避免大量的除法运算

    :不管是PC

    ,还是ARM、DSP等,除法运算都很慢,尽量以乘法和移位来替代。

    • 查表是实现高效运算的首选

    :尽可能多的利用查表来代替计算。

    • 避免重复计算

    • 尽量采用定点整形运算,尽量避免大量的多层级的if…else…

    :使得开发的算法能够支持更多的嵌入式图像处理开发平台。

    是不是很枯燥和无从下手?后面所有的章节将以实例的形式一步一步教会你如何开发高效的图像处理算法。




    展开全文
  • 图形图像处理-之-彩色转化到灰度的速度优化 HouSisong@GMail.com 2009.02.08tag:灰度算法,速度优化,定点数优化,MMX,SSE,SSE2,CPU缓存优化摘要: 彩色转化到灰度的速度优化文章包括图形图像处理简单Demo框架和...

                   图形图像处理-之-彩色转化到灰度的速度优化
                       HouSisong@GMail.com  2009.02.08

    tag:灰度算法,速度优化,定点数优化,MMX,SSE,SSE2,CPU缓存优化

    摘要:
      彩色转化到灰度的速度优化文章包括图形图像处理简单Demo框架和灰度转换的实
    现及其速度优化,并演示其使用SIMD指令集的优化;
       本篇文章将第一次提供完整的可以编译的图像处理完整项目代码;
       (以后会用这个框架逐步改写以前的图形图像处理文章)

    正文:  
      为了便于讨论,这里只处理32bit的ARGB颜色;代码使用C++;使用的编译器为vc2008;
    (经过测试代码也可以在DevC++和xcode下编译通过) 测试使用的CPU为AMD64x2 4200+(2.33G);

    速度测试说明:
      只测试内存数据到内存数据的ARGB32颜色的灰度转化;
      测试图片是800*600; fps表示每秒钟的帧数,值越大表示函数越快;

    A: 图形图像处理简单Demo框架
       
      我以前写的图形图像处理方面的blog文章都没有完整的可以编译运行的代码,
    而仅仅列出了关键的核心代码;经常有网友看了我的文章,但因为不能实际运行看看,
    从而对代码的理解不深,也不能把代码移植到自己的项目中使用; 所以决定为我的图形
    图像处理系列blog文章建立一个简单的小型的框架;我把它命名为hGraphic32,
    它会尽量的小,演示为主,仅支持ARGB32颜色,能够加载和保存bmp图片文件,能够在
    多个编译器和平台下编译和运行;
       现在就下载完整项目源代码吧:  完整项目源代码


      <hGraphic32>文件夹里的文件说明:
        "hColor32.h"  : 里面定义了32bitARGB颜色类型Color32,它占用4字节,代表一个颜色;
            TPixels32Ref是图像数据区的描述信息,可以把它理解为一个"指针",指向了Color32构成的像素区;
            IPixels32Buf是图像数据区接口,用于描述一个图像的缓冲区;
        "hPixels32.h" : 里面定义了TPixels32类,它实现了IPixels32Buf接口,用于申请和管理一块内存像素;
        "hStream.h"   : 里面定义了IInputStream输入流接口;
            IBufInputStream数据区输入流接口,继承自IInputStream;
            TFileInputStream文件输入流类,它实现了IBufInputStream接口;
            IOutputStream输出流接口;
            TFileOutputStream文件输出流类,它实现了IOutputStream接口;
         "hBmpFile.h" : 里面定义了TBmpFile类,它负责加载bmp和保存bmp;
         "hGraphic32.h" 文件include了上面的*.h头文件,所以使用的时候,只要#include "hGraphic32.h"就可以了

    B: 灰度转化项目
      所有的转换和测试代码都在"ColorToGray/ColorToGray.cpp"文件中(带有main函数的命令行程序);
      "ColorToGray/win_vc/ColorToGray.sln"是windows系统下的vc2008项目文件(测试的时请设定调试运行目录为"..");
      "ColorToGray/win_DevC++/ColorToGray.dev"是windows系统下的DevC++项目文件;
      "ColorToGray/macosx_xcode/ColorToGray.xcodeproj"是macosx系统下的xcode项目文件;
      你也可以自己建立项目,包含ColorToGray.cpp文件和<hGraphic32>文件夹下的所有文件,就可以编译了;

    C: 灰度转化公式和代码实现
      文章中用的灰度公式: Gray = R*0.299 + G*0.587  + B*0.114;
     
    代码实现:


    ////////////////////////////////////////////////////////////////////////////////
    //速度测试
    //==============================================================================
    // colorToGray_float           145.49 FPS
    ////////////////////////////////////////////////////////////////////////////////

    D: 将浮点运算转化为定点数(整数)运算
        


    ////////////////////////////////////////////////////////////////////////////////
    //速度测试
    //==============================================================================
    // colorToGray_int16           355.33 FPS
    ////////////////////////////////////////////////////////////////////////////////

    E: 做一个简单的循环代码展开


    ////////////////////////////////////////////////////////////////////////////////
    //速度测试
    //==============================================================================
    // colorToGray_int16_expand4   413.22 FPS
    ////////////////////////////////////////////////////////////////////////////////

    F: 一个特别的版本
       在高级语言范围内进行单条指令多数据流计算,减少需要的乘法量;
    在乘法运算代价比较高昂的cpu上应该效果不错; (x86上速度可能慢)

    ////////////////////////////////////////////////////////////////////////////////
    //速度测试
    //==============================================================================
    // colorToGray_int8_opMul      387.97 FPS
    ////////////////////////////////////////////////////////////////////////////////

    G: 内联汇编的MMX实现版本
       注意:这里的MMX代码都只支持x86CPU(奔腾MMX以上CPU);
       在x64下不再有MMX寄存器,而应该使用SEE的XMM寄存器;
       而且在x64模式下vc2008编译器还没有提供内联汇编的直接支持,而必须使用函数指令方式的实现;
       GCC编译器也支持内联汇编模式,但是汇编语法不同,请参考相应的说明;



    ////////////////////////////////////////////////////////////////////////////////
    //速度测试
    //==============================================================================
    // colorToGray_MMX             590.84 FPS
    ////////////////////////////////////////////////////////////////////////////////

    H: 优化写缓冲的内联汇编的MMX实现版本
      该版本相应于上面的MMX版本只改写了两句:
       一是写内存的movq [edx+ecx*4],mm0 改成了 movntq [edx+ecx*4],mm0 绕过缓存
       二是函数结束的时候调用sfence刷新写入
      完整代码如下:




    ////////////////////////////////////////////////////////////////////////////////
    //速度测试
    //==============================================================================
    // colorToGray_MMX2            679.50 FPS
    ////////////////////////////////////////////////////////////////////////////////

    I: 使用MMX函数指令方式的实现
      MMX/SSE等特殊指令除了内联汇编来使用外,也可以使用函数指令方式的实现,从而在多种
    编译器下都可以使用SIMD相关指令,可移植性也会好很多;
      但现在看来,vc对此的优化还不够,还可能遇到编译器的实现bug;
      (可以考虑使用intel的编译器编译这些代码,感觉优化能力很不错)



    ////////////////////////////////////////////////////////////////////////////////
    //速度测试
    //==============================================================================
    // colorToGray_MMX_mmh         508.69 FPS
    ////////////////////////////////////////////////////////////////////////////////


     优化写缓冲的使用MMX函数指令方式的实现



    ////////////////////////////////////////////////////////////////////////////////
    //速度测试
    //==============================================================================
    // colorToGray_MMX2_mmh        540.78 FPS
    ////////////////////////////////////////////////////////////////////////////////

    J:把测试成绩放在一起:

    ////////////////////////////////////////////////////////////////////////////////
    //CPU: AMD64x2 4200+(2.33G)  800*600 to 800*600
    //==============================================================================
    // colorToGray_float           145.49 FPS
    // colorToGray_int16           355.33 FPS
    // colorToGray_int16_expand4   413.22 FPS
    // colorToGray_int8_opMul      387.97 FPS
    // colorToGray_MMX             590.84 FPS
    // colorToGray_MMX2            679.50 FPS
    // colorToGray_MMX_mmh         508.69 FPS
    // colorToGray_MMX2_mmh        540.78 FPS
    ////////////////////////////////////////////////////////////////////////////////

    ps:用SSE的浮点指令的版本/用SSE2整数指令的版本/利用SSE3的水平加指令等的实现版本有机会时再补充
    ps:SIMD特殊指令集的使用框架请参见我的<YUV视频格式到RGB32格式转换的速度优化 中篇>一文,从而
    根据CPU对指令集的支持情况动态的调用最优的实现函数版本;

    展开全文
  • 论文:Bag of Tricks for Image Classification with Convolutional Neural Networks ... 论文复现对很多人而言难度都比较大,因为常常涉及很多细节,部分细节对于模型效果影响很大,但是却很少有文章介绍这些细节,前...

    论文:Bag of Tricks for Image Classification with Convolutional Neural Networks

    论文链接:https://arxiv.org/abs/1812.01187

    论文复现对很多人而言难度都比较大,因为常常涉及很多细节,部分细节对于模型效果影响很大,但是却很少有文章介绍这些细节,前段时间正好看到这篇文章,再加上之前就有关注GluonCV,因此就抽空看了下这篇文章。这篇文章是亚马逊科学家介绍CNN网络调优的细节,许多实验是在图像分类算法做的,比如ResNet,作者不仅复现出原论文的结果,在许多网络结构上甚至超出原论文的效果,而且对于目标检测、图像分割算法同样有提升作用。目前这些复现结果都可以在GluonCV中找到:https://github.com/dmlc/gluon-cv, GluonCV是亚马逊推出的深度学习库,除了提供许多图像任务的论文复现结果,还提供了非常多常用的数据读取、模型构建的接口,大大降低了入门深度学习的门槛。因此这篇文章可以看作是一群经验丰富的工程师介绍炼丹技巧,帮助广大读者炼出更好的丹药,个人感觉非常实用。

    首先可以先来看看作者训练的ResNet50网络的效果。在Table1中对比了目前几个常用分类网络的效果,最后一行是作者通过添加各种训练技巧后复现的ResNet-50效果,和原论文的结果对比提升非常明显(top-1准确率从75.3提升到79.29)。
    在这里插入图片描述

    既然要做对比实验,那么首先要有一个baseline,这个baseline就是作者复现相关算法的结果,这个baseline的复现细节可以参考论文2.1节内容,包括数据预处理的方式和顺序、网络层参数初始化方式、迭代次数、学习率变化策略等,这里不再赘述。Table2是作者采用baseline方式复现的3个常用分类网络的结果,可以看出来效果基本上和原论文差不多,这里的baseline也将作为后续实验的对比对象。
    在这里插入图片描述

    介绍完baseline后,接下来就是这篇论文的重点:怎么优化?整篇论文主要从加快模型训练、网络结构优化和训练调优3个部分分别介绍如何提升模型效果,接下来分别介绍。

    一、加快模型训练部分:
    这部分主要有2块内容,一块是选用更大的batch size,另一块是采用16位浮点型进行训练。

    选用更大的batch size能够在整体上加快模型的训练,但是一般而言如果只增大batch size,效果不会太理想,这部分目前有比较多的研究论文,比如Facebook的这篇:Accurate, Large Minibatch SGD:
    Training ImageNet in 1 Hour,作者也总结了主要的几个解决方案:
    1、增大学习率,因为更大的batch size意味着基于每个batch数据计算得到的梯度更加贴近整个数据集(数学上来讲就是方差更小),因此当更新方向更加准确后,迈的步子也可以更大了,一般而言将batch size修改为原来的几倍,那么初始学习率也需要修改为原来的几倍。
    2、用一个小的学习率先训几个epoch(warmup),因为网络的参数是随机初始化的,假如一开始就采用较大的学习率容易出现数值不稳定,这是使用warmup的原因。等到训练过程基本稳定了就可以使用原先设定的初始学习率进行训练了。作者在实现warmup的过程中采用线性增加的策略,举例而言,假设warmup阶段的初始学习率是0,warmup阶段共需要训练m个batch的数据(实现中m个batch共5个epoch),假设训练阶段的初始学习率是L,那么在batch i的学习率就设置为i*L/m。
    3、每个残差块的最后一个BN层的γ参数初始化为0,我们知道BN层的γ、β参数是用来对标准化后的输入做线性变换的,也就是γx^+β,一般γ参数都会初始化为1,作者认为初始化为0更有利于模型的训练。
    4、不对bias参数执行weight decay操作,weight decay主要的作用就是通过对网络层的参数(包括weight和bias)做约束(L2正则化会使得网络层的参数更加平滑)达到减少模型过拟合的效果。

    采用低精度(16位浮点型)训练是从数值层面来做加速。一般而言现在大部分的深度学习网络的输入、网络参数、网络输出都采用32位浮点型,现在随着GPU的迭代更新(比如V100支持16为浮点型的模型训练),如果能使用16位浮点型参数进行训练,就可以大大加快模型的训练速度,这是作者加速训练最主要的措施,不过目前来看应该只有V100才能支持这样的训练。

    那么这二者的优化效果如何?Table3是采用更大的batch size和16位浮点型进行训练的结果,可以看出和原来的baseline相比训练速度提升还是比较明显的,效果上也有一定提升,尤其是MobileNet。
    在这里插入图片描述

    详细的对比实验可以参考Table4。
    在这里插入图片描述

    二、优化网络结构部分:
    这部分的优化是以ResNet为例的,Figure1是ResNet网络的结构示意图,简单而言是一个input stem结构、4个stage和1个output部分,input stem和每个stage的内容在第二列展示,每个residual block的结构在第三列展示,整体而言这个图画得非常清晰了。
    在这里插入图片描述

    关于residual block的改进可以参考Figure2,主要有3点。
    1、ResNet-B,改进部分就是将stage中做downsample的residual block的downsample操作从第一个11卷积层换成第二个33卷积层,如果downsample操作放在stride为2的11卷积层,那么就会丢失较多特征信息(默认是缩减为1/4),可以理解为有3/4的特征点都没有参与计算,而将downsample操作放在33卷积层则能够减少这种损失,因为即便stride设置为2,但是卷积核尺寸够大,因此可以覆盖特征图上几乎所有的位置。
    2、ResNet-C,改进部分就是将Figure1中input stem部分的77卷积层用3个33卷积层替换。这部分借鉴了Inception v2的思想,主要的考虑是计算量,毕竟大尺寸卷积核带来的计算量要比小尺寸卷积核多不少,不过读者如果仔细计算下会发现ResNet-C中3个33卷积层的计算量并不比原来的少,这也是Table5中ResNet-C的FLOPs反而增加的原因。
    3、ResNet-D,改进部分是将stage部分做downsample的residual block的支路从stride为2的1
    1卷积层换成stride为1的卷积层,并在前面添加一个池化层用来做downsample。这部分我个人理解是虽然池化层也会丢失信息,但至少是经过选择(比如这里是均值操作)后再丢失冗余信息,相比stride设置为2的1*1卷积层要好一些。
    在这里插入图片描述

    最终关于网络结构改进的效果如Table5所示,可以看出在效果提升方面还是比较明显的。
    在这里插入图片描述

    三、模型训练调优部分
    这部分作者提到了4个调优技巧:
    1、学习率衰减策略采用cosine函数,这部分的实验结果对比可以参考Figure3,其中(a)是cosine decay和step decay的示意图,step decay是目前比较常用的学习率衰减方式,表示训练到指定epoch时才衰减学习率。(b)是2种学习率衰减策略在效果上的对比。
    在这里插入图片描述

    2、采用label smoothing,这部分是将原来常用的one-hot类型标签做软化,这样在计算损失值时能够在一定程度上减少过拟合。从交叉熵损失函数可以看出,只有真实标签对应的类别概率才会对损失值计算有所帮助,因此label smoothing相当于减少真实标签的类别概率在计算损失值时的权重,同时增加其他类别的预测概率在最终损失函数中的权重。这样真实类别概率和其他类别的概率均值之间的gap(倍数)就会下降一些,如下图所示。
    在这里插入图片描述

    3、知识蒸馏(knowledge distillation),这部分其实是模型加速压缩领域的一个重要分支,表示用一个效果更好的teacher model训练student model,使得student model在模型结构不改变的情况下提升效果。作者采用ResNet-152作为teacher model,用ResNet-50作为student model,代码上通过在ResNet网络后添加一个蒸馏损失函数实现,这个损失函数用来评价teacher model输出和student model输出的差异,因此整体的损失函数原损失函数和蒸馏损失函数的结合:
    在这里插入图片描述
    其中p表示真实标签,z表示student model的全连接层输出,r表示teacher model的全连接层输出,T是超参数,用来平滑softmax函数的输出。

    4、引入mixup,mixup其实也是一种数据增强方式,假如采用mixup训练方式,那么每次读取2张输入图像,假设用(xi,yi)和(xj,yj)表示,那么通过下面这两个式子就可以合成得到一张新的图像(x,y),然后用这张新图像进行训练,需要注意的是采用这种方式训练模型时要训更多epoch。式子中的λ是一个超参数,用来调节合成的比重,取值范围是[0,1]。
    在这里插入图片描述

    最终这4个调优技巧的实验结果对比如Table6所示。
    在这里插入图片描述

    最后作者也证明了在分类算法中的这些优化点在其他图像任务中同样有效,比如目标检测任务,如Table8所示,可以看出在ImageNet数据集上表现最好的图像分类算法同样在VOC数据集上有最后的表现。
    在这里插入图片描述

    另外在语义分割任务上也有类似的迁移效果,如Table9所示。
    在这里插入图片描述
    整体而言,这篇论文提供了模型优化方面的炼丹秘诀,采用作者复现的这些模型迁移到个人数据集上也能看到明显的效果提升,真的是非常实用。

    文章来源:https://blog.csdn.net/u014380165/article/details/85268719

    展开全文
  • 在手机端的图像处理程序中,为了提升算法运行速度,需要对程序代码进行优化。而如何优化?需要在哪些地方进行优化?这些都是我们需要思考的问题。 因此,这里对代码优化进行相关总结,并将不定期更新,作为长期的...
  • 在深度学习大火的今天,熟不知以前的图像处理方法大都还是使用能量泛函优化的方法,即使是今天依然有着深度学习不可取代的魅力。要想学习,基础的优化方法必不可少。 先说说传统的图像处理方法包括图像超分,图像去...
  • 要求使用背景建模的相关技术(最好使用优化方法),区分出前景和背景,输出为视频的每一帧对应的前景和背景。 如图[pic1]所示: 图像,左边是输入,右边是输出。 问题二:主成分提取 输入为一张由若干张小图...
  • OpenCV库包括了对OpenCL和CUDA GPU架构的支持。 OpenCL(Open Computing Language):开放计算语言,可以附加在主机处理器的CPU或GPU上执行。 OpenCV有一个新的统一数据结构UMat,用于在必要和可能的时候,负责将...
  • 做了这么长的时间,我也一直在是思考这个问题,也当是个经验总结。先抛开硬件上的东西。 2019年第一更,本来想去放松下的,那就下午吧,...假如说CPU是多个核心的话,那么完全可以用多线程加速。原理性的东西这里...
  • 使用GPU提高OpenCV的图像处理运算速度OpenCV中提供了GPU模块,可以用来加速图像处理的相关运算。OpenCV的GPU模块是使用CUDA编写的。OpenCV中GPU模块的调用点击这里,使用GPU模块需要开启WITH_CUDA选项。OpenCV官方...
  • 图像本身存在一些规律,因此形成了独特的处理方法。 存储特点: 凡谈到图像,一般都是指的是一个二维的矩阵(数组),其在计算机内存的存放是一个连续的地址空间,该地址空间可以由第一象素和最末一个象素的存储...
  • 早期的时候我使用的开发工具是VB6,VB6做图像处理速度在我的软件Imageshop中有所体现,还是算可以的。目前,我已经改用C#来研究图像算法,C#中有指针,做图像处理起来效率确实要高不少。VB.NET当初也用过不到半年...
  • 图像处理界双线性插值算法的优化  该博文转载于Imageshop的博文  在图像处理中,双线性插值算法的使用频率相当高,比如在图像的缩放中,在所有的扭曲算法中,都可以利用该算法改进处理的视觉效果。首先,...
  • 软件方面且先到此为止。再试试硬件的威力。 关于SIMD及为CPU做优化的指引文章请参考这里。
  • 第 1 章 基本的图像操作和处理本章讲解操作和处理图像的基础知识,将通过大量...1.1 PIL:Python图像处理类库PIL(Python Imaging Library Python,图像处理类库)提供了通用的图像处理功能,以及大量有用的基本图...
  • Python中的图像处理

    2018-03-03 22:27:15
    第 1 章 基本的图像操作和处理本章讲解操作和处理图像的基础知识,将通过大量...1.1 PIL:Python图像处理类库PIL(Python Imaging Library Python,图像处理类库)提供了通用的图像处理功能,以及大量有用的基本图...
  • 数字图像处理方法的重要性源于两个主要应用领域: 改善图像信息以便解释。 为存储、传输和表示而对图像数据进行处理,以便于机器自动理解。 图像处理(image processing): 用计算机对图像...
  • CUDA图像处理示例程序

    2020-07-02 23:30:34
    一个简单的CUDA程序,使用CUDA进行图像二值化操作,编译环境为VS2005,用到了cuda_vs_wizard进行环境设置,使用OpenCV读入和处理图像并与CUDA的处理结果...有兴趣的可以做一下优化或在此基础上完成更复杂的图像处理工作
  • 最近工作挺有意思的,对优化技术进行了各种的尝试和研究,经过测试,多线程对图像处理优化有一定的功效,通过分散处理的区域,指派不同线程处理不同位置的像素数据: Android.mk: LOCAL_SHARED_LIBRARIES := ...
1 2 3 4 5 ... 20
收藏数 91,600
精华内容 36,640