2017-06-12 22:29:15 coming_is_winter 阅读数 9547
  • Java经典算法讲解

    在面试中,算法题目是必须的,通过算法能够看出一个程序员的编程思维,考察对复杂问题的设计与分析能力,对问题的严谨性都能够体现出来。一个算法的好坏,直接影响一个方法调用的性能,进而影响软件的整体性能。算法是学习所有编程语言的基础,在Java的学习过程中首先也会选择以算法起步,本次课程重点讲解Java开发中常用的基本算法。

    31034 人正在学习 去看看 张中强

图像处理之图像分割(一)之活动轮廓模型:Snake算法简单梳理


  Snake算法,应该也可以翻译成蛇形算法,或者是包含曲折前进的意思。具体函数背景原理介绍参考:zouxy09,http://blog.csdn.net/zouxy09/article/details/8712287,图像分割之(五)活动轮廓模型之Snake模型简介,这里还是就几个自己思考的重点拓展一下。

  

 1. 这段中讲v(s)的表示,s∈[0,1],和s是以傅里叶变换形式描述边界的自变量。自己理解不是很明白,查了点资料,整合一下,说法有可能不严谨。首先:




   2.Snake模型到底是怎么变化的?



  弹性力量和弯曲力量合成内部力量,,保持固有的自身形状,外部力量改变其固有的自身形状,在合适的范围内受某种力而变化,这里举个例子:
 


  上面图中这种特大气泡(或想一下气球)的形状是有什么决定的呢?其中的弹性力量是曲线的斜率使其保持大概的圆形(可以理解为材料的张力,失重条件下水会变成水球),虽然现在上图的圆形变形严重,而弯曲力量是曲线斜率的斜率,这里理解为收缩的力量,可以想象一下气球紧绷的力量(这是气球本身材质决定,与外力无关),如果有漏气现象,紧绷的力量会使气泡或气球逐渐收缩,直至最小。外部力量这里的是空气的压力,这在上图中可以看到气泡的不规则凹凸,可以说是大气的压力的力量,形象的说是空气力量梯度的变化,在Snake中表现为像素灰度值梯度的变化。联系再丰富一点,Snake迭代的过程可以想一下真空包装:



  一开始先验知识人为划定Snake框架,相当于还未抽气时的包装袋,抽气开始在内力(包装袋的形状与材质决定)与外力(大气压力)的作用下,不断迭代,最终的轮廓收缩到鸡腿形状,能量最小达到平衡。

  3.泛函与变分
  函数的函数为泛函,我们求解的能量函数公式最终表现为函数的函数,怎样求公式最小值,一般求导找零点。函数的函数求导为变分。

  参考文献:
  [数字图像处理(第二版)].(美)冈萨雷斯.扫描版。

2017-01-23 09:11:04 u014798482 阅读数 1990
  • Java经典算法讲解

    在面试中,算法题目是必须的,通过算法能够看出一个程序员的编程思维,考察对复杂问题的设计与分析能力,对问题的严谨性都能够体现出来。一个算法的好坏,直接影响一个方法调用的性能,进而影响软件的整体性能。算法是学习所有编程语言的基础,在Java的学习过程中首先也会选择以算法起步,本次课程重点讲解Java开发中常用的基本算法。

    31034 人正在学习 去看看 张中强

          图像变形是图像处理中不太常用的算法,因为不应用不广范。但这种算法还是挺有意思的。把矩形图像变形到一个指定的轮廓的区域中,图像的内容适应到目标区域后,会发生比较奇特的扭曲挤压效果,当然,前提是这个轮廓必须是单连通封闭曲线。

哥2015实现的,看几张效果图:

                                                   几种效果集锦



这个算法的结果都不太容易预料,这一点是优点从某种角度上来说也算是缺点。优点是往往能得到比较令人惊喜的效果。

2018-12-11 17:40:06 shanwenkang 阅读数 1453
  • Java经典算法讲解

    在面试中,算法题目是必须的,通过算法能够看出一个程序员的编程思维,考察对复杂问题的设计与分析能力,对问题的严谨性都能够体现出来。一个算法的好坏,直接影响一个方法调用的性能,进而影响软件的整体性能。算法是学习所有编程语言的基础,在Java的学习过程中首先也会选择以算法起步,本次课程重点讲解Java开发中常用的基本算法。

    31034 人正在学习 去看看 张中强

Snakes算法

上一讲我们讲的图像分割算法主要是基于像素的,这一讲主要是基于曲线的。我们希望能得到一个能够包围住图像轮廓的平滑的曲线,snakes算法就是一个很有用的算法。首先我们将曲线的坐标x、y同一用参数s表示,s范围从0-1代表从起点绕曲线一周再回到原点

我们假定初始化的时候这个曲线已经给定,我们定义这个曲线的能量函数,曲线衍进的过程就是让能量函数降低的的过程,能量函数分为外部能量和内部能量

如下是内部能量的定义,内部能量只与曲线的形状有关。能量由两部分组成:一阶导部分与二阶导部分。一阶导代表曲线的“弹性”,也就是曲线是否被拉伸的非常长;二阶导代表曲线曲折程度,也就是曲线是否弯曲不平滑。曲线弹性越低,弯曲越少能量越低

第二部分是曲线的外部能量,代表曲线与边缘的重合程度。重合程度大的时候能量低。

我们有了能量函数以后如何求它的最小值呢?这涉及到变分法,在此就不细讲了。对于数字图像,我们一般用一定数量的点对曲线进行逼近,之后我们可以用梯度下降法来求得函数的最小值

在曲线衍进的时候还需要注意有时我们需要对曲线的点进行重排(再采样)来保证下一次循环(衍进)时我们有更好的效果

当然这种方法也存在问题,我们的活动轮廓无法看到远处的边缘,因此当周围像素值都差不多的时候曲线可能不会继续向内收敛;第二点是当图像中存在噪声时轮廓很可能和噪声点重合。为了解决这个问题我们可以对图像先进行模糊处理,这相当于将原本的边界变得更加模糊了(即扩大的边界的影响范围),这样就能使轮廓有更好的收敛性

 

梯度向量流

采用模糊处理的效果实际上并不是很好,更好的方法是采用梯度向量流(gradient vector flow)。梯度向量流用一个新的矢量场来代替梯度场,从而替换外部能量的部分。

我们用如下方式定义这个新的矢量场v,当梯度值较大的时候,我们另这个矢量场与梯度场的值大致相同;当梯度值较小的时候我们让v的值尽量平滑的变化。这也就意味着在图像边缘处,v的值与梯度场的值相同,当我们逐渐远离边界的时候,v的值不像梯度场一样立马变小,而是有一个逐渐变小的过程。实际上这个新的场v也是扩大了边界的影响范围,使得轮廓能够在更远的地方捕捉到边缘

如果我们将这个场画出来可以得到如下结果。我们可以看出在这种情况下如果初始轮廓在边界外部,那么轮廓将会收缩;如果初始轮廓在边界内部,那么轮廓将会外扩,即朝着向v的模大的地方衍进

Snakes算法也有很多令人头疼的地方,例如追踪每一个点不是一件容易的事,例如snake无法包围多个物体等等

除此以外由于这种算法是基于边缘的,它还会使曲线与我们不需要的边缘重合,例如以下这个例子:曲线并不能很好地包围手掌,而是被背景木桌的条纹所吸引了

 

水平集

为了解决snakes算法不能包围多个物体与洞的问题,我们有水平集(level set)这个算法。与定义一条曲线不同的是,我们定义了一个三维的函数,二维平面上的曲线实际上是这个函数在z=0的横截面

我们用这种方法可以很好地表示包含多个物体或洞的曲线

举个例子,下面右图是我们需要的曲线,左边是这个曲线对应的函数

这种算法还有很多细节我们就不在这讨论了

我们在以上讨论的算法都是基于图像边缘的,当然我们还有基于图像区域的算法,这种算法的能量只与曲线本身的性质以及两个区域块内的像素有关,而与图像的边界无关

比如以下的例子,我们运用基于区域的算法可以让曲线很好地收敛到斑马周围,因为这种情况下曲线外部的颜色基本是绿色,曲线内部基本是黑白的。但如果我们采用基于边缘的算法来计算,那么这个曲线就会收敛到斑马身上的条纹上

 

 

 

 

2015-04-14 12:38:49 Trent1985 阅读数 1993
  • Java经典算法讲解

    在面试中,算法题目是必须的,通过算法能够看出一个程序员的编程思维,考察对复杂问题的设计与分析能力,对问题的严谨性都能够体现出来。一个算法的好坏,直接影响一个方法调用的性能,进而影响软件的整体性能。算法是学习所有编程语言的基础,在Java的学习过程中首先也会选择以算法起步,本次课程重点讲解Java开发中常用的基本算法。

    31034 人正在学习 去看看 张中强


[函数名称]

  二值图像轮廓提取         ContourExtraction(WriteableBitmap src) 

[算法说明]

  二值图像的轮廓提取对于图像识别,图像分割有着重要意义。该算法的核心就是将图像目标的内部点消除。所谓内部点,我们要根据当前像素点的邻域来进行判断,假设邻域窗口为3*3窗口,如果当前像素P(x,y)的八个邻域像素满足如下条件,则该点即内部点:

  1P(x,y)为目标像素,假设目标像素为黑色0,背景像素为白色255,那么P(x,y)=0;

  2P(x,y)的八个邻域像素均为目标像素0

  我们把满足条件的内部点删除,换为背景点255,即可得到图像轮廓。

  内部点如下图所示:

[函数代码]

        /// <summary>
        /// Contour Extraction process.
        /// </summary>
        /// <param name="src">The source image.</param>
        /// <returns></returns>
        public static WriteableBitmap ContourExtraction(WriteableBitmap src)
        {
            if (src != null)
            {
                int w = src.PixelWidth;
                int h = src.PixelHeight;
                WriteableBitmap srcImage = new WriteableBitmap(w, h);
                byte[] temp = src.PixelBuffer.ToArray();
                byte[] tempMask = (byte[])temp.Clone();
                for (int j = 1; j < h-1; j++)
                {
                    for (int i = 4; i < w*4-4; i+=4)
                    {
                        if ((tempMask[i + j * w * 4] == 0) && (tempMask[i - 4 + j * w * 4] == 0) && (tempMask[i + 4 + j * w * 4] == 0) && (tempMask[i - 4 + (j - 1) * w * 4] == 0)
                            && (tempMask[i - 4 + (j + 1) * w * 4] == 0) && (tempMask[i + (j - 1) * w * 4] == 0) && (tempMask[i + (j + 1) * w * 4] == 0)
                            && (tempMask[i + 4 + (j - 1) * w * 4] == 0) && (tempMask[i + 4 + (j + 1) * w * 4] == 0))
                        {
                            temp[i + j * w * 4] = (byte)255;
                            temp[i + 1 + j * w * 4] = (byte)255;
                            temp[i + 2 + j * w * 4] = (byte)255;
                        }
                    }
                }
                Stream sTemp = srcImage.PixelBuffer.AsStream();
                sTemp.Seek(0, SeekOrigin.Begin);
                sTemp.Write(temp, 0, w * 4 * h);
                return srcImage;
            }
            else
            {
                return null;
            }
        }

2016-11-15 13:21:13 plc_jianghao 阅读数 12585
  • Java经典算法讲解

    在面试中,算法题目是必须的,通过算法能够看出一个程序员的编程思维,考察对复杂问题的设计与分析能力,对问题的严谨性都能够体现出来。一个算法的好坏,直接影响一个方法调用的性能,进而影响软件的整体性能。算法是学习所有编程语言的基础,在Java的学习过程中首先也会选择以算法起步,本次课程重点讲解Java开发中常用的基本算法。

    31034 人正在学习 去看看 张中强

1.图像处理方法分类

输入 输出 等级 例子
图像 图像 初级 降噪,增强对比度
图像 图像特征 中级 轮廓提取
图像 图像表征的信息 高级 模式识别,机器视觉

2. 图像增强(image enhancement)

  1. 没有统一的图像增强算法,要针对具体问题具体分析,用户是最终标准的评判者;用户说好就是好,所以没有所谓”最好 ”的图像增强算法。

3. 像素点之间的关系

这里写图片描述

名称 表示法 包括点
4邻域(4-neightbors) N4(p) {2,4,5,7}
D邻域(d-neightbors) ND(p) {1,3,6,8}
8邻域(8-neightbors) N8(p) {1,2,3,4,5,6,7,8}

4. 邻接(adjacency)、连通(connectivity)、区域(regions) 、边界(boundaries)

4.1 邻接

邻接有的书上翻译叫连接,其实是一个意思。这就体现了看英文资料的好处,没有翻译导致的奇异。
f(p)f(q)分别表示像素点p、q的强度,V表示函数f()全体值域的y一个子集,则

名称 定义
4邻接(4-adjacency) f(p)Vf(q)VqN4(p)
8邻接(8-adjacency f(p)Vf(q)VqN8(p)
m邻接(m-adjacency) 1.f(p)Vf(q)V
2.qN4(p) or qND(p)(N4(p)N4(q))V

m邻接又称为混合邻接,其作用是为了消除8邻接导致的多路问题。
为了解释这个多路问题,需要引入路径的概念。路径(path)是一系列像素点的集合,相邻的俩个像素点的关系要满足一种邻接的定义。比如4邻接路径,就表示路径中相邻两个像素点满足4邻接关系。8邻接路径、m邻接路径的定义与此类似。
假设V={1},则各种邻接的路径如下图所示:
这里写图片描述
可以看出8邻接路径存在多路的问题。

4.2 连通

设S为图像中部分像素的集合
如果可以在S中找到一条路径连接像素点p和q,则称p和q 在S中是连通的。自然,根据路径选择方法的不同,连通也应该分为4连通,8连通和m连通。
在S中,对于任意的像素点p,所有与p点连通的像素点的集合(包括p点)称为一个连通组件。如果在S中只能找到一个连通组件,则称S为连通集合

4.3 区域

图像中的一个连通集合也可以叫做一个区域。自然,依据使用的连通类型不同,区域也分为4连通区域,8连通区域(原则上讲也应该有m连通区域,但在涉及区域的问题讨论中很少应用m连通)。
如果两个4连通区域可以合并为一个更大的4连通区域,则称这两个区域是4邻接的。相应的,也存在8邻接。
如果两个类型相同的连通区域无法合并,则称这两个连通区域是不想交的(disjoint)。
ps:在同一副图像上划分区域时,只会采用一种连通类型。要么都是4连通的,要么都是8连通的。不会出现我把图像的左边划分为4连通的,右边划分为8连通的情况。

4.4 前景(foreground)和背景(background)

假设在一副图像上有k个不想交的区域。
设Ru等于所有者k个区域的集合,(Ru)c等于图像上Ru以外的像素点的集合。
则,Ru称为图像的前景,(Ru)c称为Ru的背景。(这个相对性很重要,背景是针对前景而言的)

4.5 边界(boundary,border)

如果区域R中存在像素点p,且p点的领域中至少有一个像素点落在R的背景中,则R中所有这样的点P组成的集合叫做区域R的边界。
根据上面的定义,自然也存在4连通边界和8连通边界的说法。但更多使用的是8连通边界,否则如下图中红圈圈出的点将不被认为是边界,这很不自然。
这里写图片描述
以上方式定义的区域的内边界,响应的,在背景中与内边界相邻的点组成的集合称为外边界。

5. 距离

两个像素点间的距离计算方式,常见的有三种,定义如下:

De(p,q)=(p.xq.x)2+(p.yq.y)2

D4(p,q)=|p.xq.x|+|p.yq.y|

D8(p,q)=max(|p.xq.x|,|p.yq.y|)

6. gamma校正

6.1 gamma校正的定义

首先介绍一下变换函数

S=crγ

其中
r—某个像素点的强度;
c—为尝试;
γ—为变换参数;
s—此像素点变换后的强度;
利用以上公式对输入图像的每个像素点进行处理的过程称为gamma校正。

6.2 gamma校正的作用

1.修复图像失真

下图展示了一副自然界图像经电子设备呈现在人眼上的过程
这里写图片描述
如果自然界图像经过传感器直接转化为数字图像时,会发生失真。这种失真是由于传感器硬件引起的,无法避免。经验上可以将失真总结为如下的形式:

(x,y)=(x,y)α

为了弥补这种失真,可以在步骤2增加一部gamma校正,即:
(x,y)=gamma((x,y)α)

gamma(r)=r1α

经过这样的校正,数字图像和自然界图像就相同了。
可以看出,校正的关键是α值的选择。这个值一般由传感器的生成厂家根据自身产品的特点固化在传感器里,对传感器的用户来说,是不需要关系的。

2.增加对比度

下图展示了不同γ下,输入与输出的关系
这里写图片描述
可以看出当γ<1时,会增强原图像中暗处的对比度;
可以看出当γ==1时,无任何效果;
可以看出当γ>1时,会增强原图像中亮处的对比度;
但是对强度的影响是非线性的。

7. 灰度分层(intensity-level slicing)

8.Bit平面分层(bit-plane slicing)

概念上比较抽象,举个例子来理解。
假设每一个像素点由2bit组成,一副图像有4个像素点。则如下图所示,图像1可以由图像2和图像3叠加而来。
这里写图片描述
那么,图像2和图像3就是图像1的两个bit平面。
同理可以推断出,如果每个像素点由8个bit组成,则一副图像应该有8个bit平面。
bit平面分层可以用于图像的有损压缩,通过这种分析你可以发现,有些bit平面对图像的贡献是很小的,删除这一层的数据,人眼是无法分辨的,但这样就节约了空间以及传输的数据量。

9.直方图(histogram)处理

1.图像的直方图

图像的直方图实际上就是图像不同强度的像素点的概率分布图。
假设一副8bit图像(8bit图像指图像的每个像素点用8bit长度的数据表示,共可以表示0~255,共计256个强度)有M*N个像素点。
令n255表示强度的255的点,在图像中的数量,则此图像强度为255的概率可根据如下公式计算:

P255=n255MN

同理可以计算出P0~P255的值,然后以强度为x轴,概率为y轴绘制的直方图,就是此图像的直方图。
通过图像的直方图可以看出以下几点结论:
1. 图像亮度较暗,则直方图集中在x轴的左侧;
2. 图像亮度较亮,则直方图集中在x轴的右侧;
3. 图像对比度较低,则直方图集中在某个很小的范围内;
4. 图像对比度较高,则直方图均匀分布在整个x轴。

2.直方图均衡

根据上一节的结论4,“图像对比度较高,则直方图均匀分布在整个x轴”。我们可以将一个对比度较低的图像,通过某种变化,使其直方图均匀分布,这样就可以增进对比度。这其中最简单的算法是“直方图均衡”。
s=T(r),其中s表示转换后的像素点强度,r表示原像素点强度。如果T(r)是连续可微函数,则有如下结论:

Ps(s)=Pr(r)drds
,其中Ps()Pr()分别是sr的概率分布函数。这数学结论很重要,但我并没有亲自推导过。只需要记住T(r)必须是“连续可微”函数。
基于以上的结论,我们可以构造如下的转换函数:
T(r)=(N1)r0Pr(w)dw
其中N表示像素点可能的取值数量,比如8bit图像,N=28=256
基于以上构造的转换函数,我们很容易计算出
Ps(s)=1N1
,即转换后,所有的像素点的概率分布为常数,对比度最大。

3.自由选择输出图像的概率密度函数

上一节中构造的转换函数,转换后图像的概率密度是常数。这在多数情况下已经足够好,但有时我们希望自由选择输出图像的概率密度函数。
下面直接介绍算法:
1. 令变换后的概率密度函数为Pz(z);
2. 令s1=(N1)z0Pz(w)dws2=(N1)r0Pr(w)dw
3. 由于Pr(r)r是输入图像的数据,是已知的,我们可以计算出{(s2,r)}的对应关系表;
4. 由于Pz(z)是我们选定的,z的取值范围是[0,2n1],所以可以得到{(s1,z)}的对应关系表;
5. 基于以上几点可知,当有一个输入r,便可以查询到一个s2,然后选择|s2s1|最小的s1,再根据这个s1得到z,即完成了变换。

没有更多推荐了,返回首页