差分图算法
A. 什么叫差分，差分方程是啥
1、差分又名差分函数或差分运算，差分的结果反映了离散量之间的一种变化，是研究离散数学的一种工具。它将原函数f(x) 映射到f(x+a)-f(x+b) 。差分运算，相应于微分运算，是微积分中重要的一个概念。差分又分为前向差分、向后差分及中心差分三种。
2、差分方程（是一种递推地定义一个序列的方程式：序列的每一项目是定义为前一项的函数。某些简单定义的递推关系式可能会表现出非常复杂的（混沌的）性质，他们属于数学中的非线性分析领域。
(1)差分图算法扩展阅读：
差分方程举例：
dy+y*dx=0,y(0)=1 是一个微分方程， x取值[0,1] （注：解为y(x)=e^(-x))；
要实现微分方程的离散化，可以把x的区间分割为许多小区间 [0,1/n],[1/n,2/n],...[(n-1）/n,1]
这样上述微分方程可以离散化为：y((k+1）/n)-y(k/n)+y(k/n)*（1/n)=0， k=0,1,2,...,n-1 （n 个离散方程组）
利用y(0)=1的条件，以及上面的差分方程，可以计算出 y(k/n) 的近似值了。
差分方程的性质
1、Δk(xn+yn)=Δkxn+Δkyn。
2、Δk(cxn)=cΔkxn。
3、Δkxn=∑（-1)jCjkXn+k-j。
4、数列的通项为n的无限次可导函数，对任意k>=1，存在η，有 Δkxn=f(k）（η）。
B. 什么是差分算法
在数值计算中,常用差分近似微分.
例如：
向前差分：f'(n)=f(n+1)-f(n)
向后差分：f'(n)=f(n)-f(n-1)
C. 帧间差分法的算法描述
（l）、对序列图像进行3×3中值滤波预处理，去掉图像随机噪声。减少以后运算的复杂度，克服噪声对图像处理结果的干扰。
（2）、从视频图像序列中选取出背景图像所阢砂，使其只包含固定的背景图像：
（3）、在视频图像序列中选取连续的两帧图像，其中前一帧图像pk-1(x,y)，当前帧图像pk(x,y)；
（4）、计算当前帧与背景帧的差得FD(x,y)，从 图像中提取出完整的目标；
（5）、计掉当前1帧的差得FG(x,y)，得到目标的变化量；
（6）、求帧差FD（x,y）与，FG(x,y)的交集得到运动目标粗糙的运动区域幽像，
（7）、数学形态学运算使得运动区域封毕、连续、完整，并去掉背持中的噪声。
其中：（略）
D. 显式差分算法
问题求解期望能找出一个静态解，然而在有限差分公式中包含有动力方程。这样，可以保证在被模拟的物理系统本身是非稳定的情况下，有限差分数值计算仍有稳定解。对于非线性材料，物理不稳定的可能性总是存在的。
质量守恒定律要求一个网格块中地下水的流入或流出净流量等于存储于网格块的地下水的变化量。图2-2表示了一个具有Δx，Δy和Δz维的网格块。图中也表示了网格块的6个相邻块中心处的节点，分别表示为x－，x+，y－，y+，z－和z+。通过该块的面流到中心节点的流量为正，且分别表示为Q(x－)，Q(x+)，Q(y－)，Q(y+)，Q(z－)和Q(z+)。
图2-2 网格块示意图
在该网格块中的地下水源汇项包括抽水井、排水，或者补给量。排泄到块的流量满足下列方程:
典型煤矿地下水运动及污染数值模拟:Feflow及Modflow应用
式中:h为中心节点的水头;S为中心块体的储水系数。
在有限差分中，偏导数可近似用有限差分形式表示，因此，方程可变为
典型煤矿地下水运动及污染数值模拟:Feflow及Modflow应用
式中:t为当前时刻;t－Δt为上一时间步长的时刻;h为中心节点的水头。
注意上述公式中所有的Q为在t时间步长处的流量。
现在考虑从临近节点来的典型流Q(x+)。该流量与处在中心节点和x+节点之间的水头差值有关，即
典型煤矿地下水运动及污染数值模拟:Feflow及Modflow应用
式中:h(x+)为x+节点处的水头;h为中心节点处的水头;C(x+)为导水系数，其值取决于中心节点和x+节点处的维数及Kx值。从其他方向的流量可简单定义为
典型煤矿地下水运动及污染数值模拟:Feflow及Modflow应用
式中:C(x－)，C(y+)，…为其他导水系数，h(x－)，h(y+)，…，为其他相邻节点的水头。将方程(2-20)和方程(221)代入到方程(219)中，则某节点的有限差分方程变为
典型煤矿地下水运动及污染数值模拟:Feflow及Modflow应用
该方程可概化为
典型煤矿地下水运动及污染数值模拟:Feflow及Modflow应用
其中D1～D8可用以下方法量化:
(1)中心网格块体和其6个直接相邻的块体的物理性质;
(2)中心网格块体的内在源项QS;
(3)在中心阶段h(t－Δt)上一个时间步长的水头;
(4)上一个时间步长的大小。
对于稳定流模型，h(t)－h(t－Δt)=0，且在每个节点方程中的储存项可以忽略不计。
假定中心块体和x+块体在3个方向中具有同一方向，大多数有限差分软件诸如modf-low允许这些方向因不同块体的不同而不同，且当块体中水位在块体中变化时，Δz方向的水头也随之变化。
假定在x方向上为一维流，利用达西定律计算流量Q(x+)为:
典型煤矿地下水运动及污染数值模拟:Feflow及Modflow应用
式中:Kx(→x+)为中心节点和x+节点之间的水力传导系数。和公式(2－20)对比，显然导水系数为
典型煤矿地下水运动及污染数值模拟:Feflow及Modflow应用
当中心节点和x+节点具有同样的Kx值，中心节点和x+节点之间的水力传导系数可简化为Kx(→x+)=Kx=Kx(x+)。
E. 优化算法笔记（七）差分进化算法
（以下描述，均不是学术用语，仅供大家快乐的阅读）
差分进化算法（Differential Evolution Algorithm，DE）是一种基于群体的进化算法，它模拟了群体中的个体的合作与竞争的过程。算法原理简单，控制参数少，只有交叉概率和缩放比例因子，鲁棒性强，易于实现。
差分进化算法中，每一个个体的基因表示待求问题的一个候选解。每次迭代将先进行变异操作，选择一个或多个个体的基因作为基，然后选择不同的个体的差分来构成差分基因，最后将作为基的基因与差分基因相加来得出新的个体。交叉操作将新的个体将于父代的对应个体交叉，然后进行选择操作，比较交叉后的个体与父代的对应个体，选择较优的个体保留至下一代。在迭代完成之后将选择种群中最优个体的基因作为解。
差分进化算法可以算是我所使用过的优化算法中大魔王级别的算法，虽然它每个方面都没有强到离谱，但是综合起来的效果好于大多数算法。它就像一个每个科目都能考到90分（百分制）的学生，虽然没门课都不是最优秀的，但是论综合，论总分，它有极大的概率是第一名。
在我研究优化算法的小路上，我的目标就是找到一个能打败大魔王或是能在大多数方面压制魔王的算法。
这次的主角就选魔王军吧（或者蚁王军，为了与蚁群算法区别还是叫魔王军吧），个体则称之为魔王兵。
魔王兵的能力取决于它们的基因，它们可以根据环境或者需要改变自己的基因使得自己更加强大，更方便的处理问题，问题的维度与基因维度相同。
表示第i个魔王兵在进化了第t次后的基因，该个体有D位基因。
与遗传算法同为进化算法的差分进化算法，它们的操作（算子）也都非常相似的，都是交叉，变异和选择，流程也几乎一样（遗传算法先交叉后变异，差分进化算法先变异后交叉）。
说到差分进化算法中的变异，我就想到一句论语 “三人行，必有我师焉。择其善者而从之，其不善者而改之。” ，其实这句论语已经向我们说明了差分进化算法的整个流程：
“三人行，必有我师焉”——变异，交叉。
“择其善者而从之，其不善者而改之”——选择。
差分进化算法中，当一个魔王兵变异时，它会先找来3个小伙伴，当然是随机找来3个小伙伴，避免同化。在一个小伙伴的基因上加上另外两个小伙伴基因之差作为自己的目标基因。其变异公式如下：
表示第i个魔王兵找到了编号为r1、r2和r3的三个魔王兵，当然了i、r1、r2、r3为互不相同的整数，F为缩放比例因子，通常 ，一般取F=0.5。 为第i个魔王兵交叉后的目标基因图纸，不过这是个半成品，再经过交叉后，目标基因图纸才算完成。
其实现在我们已经有了5个基因图纸了 ，接下来将进行交叉操作。由于变异操作，差分进化算法的种群中个体数至少为4，即魔王军中至少有4个小兵。
交叉操作中，魔王兵i会将目标基因图纸 进行加工得到 ，加工过程如下：
其中 。 为交叉概率，其值越大，发生交叉的概率越大，一般取 。 为{1,2,…,D}中的随机整数，其作用是保证交叉操作中至少有一维基因来自变异操作产生的基因，不能让交叉操作的努力白费。
从公式上可以看出交叉操作实际上是从变异操作得出的基因图纸上选择至少一位基因来替换自己的等位基因，得到最终的基因图纸。
选择操作相对简单，魔王兵i拿到了最终的基因图纸 ，大喊一声，进化吧，魔王兵i的基因改变了。它拿出了能力测量器fitness function,如果发现自己变强了，那么就将基因 保留到下一代，否则它选择放弃进化，让自己还原成 。
实验又来啦，还是那个实验 ，简单、易算、好画图。
实验1 ：参数如下
图中可以看出在第20代时，群体已经非常集中了，在来看看最终得出的结果。
这结果真是好到令人发指，恶魔在心中低语“把其他的优化算法都丢掉吧”。不过别往心里去，任何算法都有优缺点，天下没有免费的午餐，要想获得某种能力必须付出至少相应的代价。
实验2：
将交叉率CR设为0,即每次交叉只选择保留一位变异基因。
看看了看图，感觉跟实验1中相比没有什么变化，那我们再来看看结果。
结果总体来说比实验1好了一个数量级。为什么呢？个人感觉应该是每次只改变一位基因的局部搜索能力比改变多位基因更强。下面我们将交叉率CR设为1来看看是否是这样。
实验3：
将交叉率CR设为1,即每次交叉只选择保留一位原有基因。
实验3的图与实验1和实验2相比好像也没什么差别,只是收敛速度好像快了那么一点点。再来看看结果。
发现结果比实验2的结果还要好？那说明了实验2我得出的结论是可能是错误的，交叉率在该问题上对差分进化算法的影响不大，它们结果的差异可能只是运气的差异，毕竟是概率算法。
实验4：
将变异放缩因子设为0，即变异只与一个个体有关。
收敛速度依然很快，不过怎么感觉结果不对，而且个体收敛的路径好像遗传算法，当F=0，时，差分进化算法退化为了没有变异、选择操作的遗传算法，结果一定不会太好。
果然如此。下面我们再看看F=2时的实验。
实验5：
将变异放缩因子设为2。
实验5的图可以明显看出，群体的收敛速度要慢了许多，到第50代时，种群还未完全收敛于一点，那么在50代时其结果也不会很好，毕竟算法还未收敛就停止进化了。
结果不算很好但也算相对稳定。
通过上面5个实验，我们大致了解了差分进化算法的两个参数的作用。
交叉率CR，影响基因取自变异基因的比例，由于至少要保留一位自己的基因和变异的基因导致CR在该问题上对算法性能的影响不大（这个问题比较简单，维度较低，影响不大）。
变异放缩因子F，影响群体的收敛速度，F越大收敛速度越慢，F绝对值越小收敛速度越快，当F=0是群体之间只会交换基因，不会变异基因。
差分进化算法大魔王已经如此强大了，那么还有什么可以改进的呢？当然有下面一一道来。
方案1 .将3人行修改为5人行，以及推广到2n+1人行。
实验6：
将3人行修改为5人行，变异公式如下：
五人行的实验图看起来好像与之前并没有太大的变化，我们再来看看结果。
结果没有明显提升，反而感觉比之前的结果差了。反思一下五人行的优缺点，优点，取值范围更大，缺点，情况太多，减慢搜索速度。
可以看出算法的收敛速度比之前的变慢了一点，再看看结果。
比之前差。
差分进化算法的学习在此也告一段落。差分进化算法很强大，也很简单、简洁，算法的描述都充满了美感，不愧是大魔王。不过这里并不是结束，这只是个开始，终将找到打败大魔王的方法，让新的魔王诞生。
由于差分进化算法足够强，而文中实验的问题较为简单导致算法的改进甚至越改越差（其实我也不知道改的如何，需要大量实验验证）。在遥远的将来，也会有更加复杂的问题来检验魔王的能力，总之，后会无期。
以下指标纯属个人yy,仅供参考
目录
上一篇 优化算法笔记（六）遗传算法
下一篇 优化算法笔记（八）人工蜂群算法
优化算法matlab实现（七）差分进化算法matlab实现
F. 什么是三帧差分法
三帧差分算法是相邻两帧差分算法的一种改进方法，它选取连续三帧视频图像进行差分运算，消除由于运动而显露背景影响，从而提取精确的运动目标轮廓信息。该算法的基本原理是是先选取视频图像序列中连续三帧图像并分别计算相邻两帧的差分图像，然后将差分图像通过选取适当的阈值进行二值化处理，得到二值化图像，最后在每一个像素点得到的二值图像进行逻辑与运算，获取共同部分，从而获得运动目标的轮廓信息。
三帧差法的具体算法如下。
提取连续的三帧图像，I(k-1),I(k),I(k+1) 。
(1) d(k,k-1) [x,y] = | I(k)[x,y] - I(k-1)[x,y] |;
d(k,k+1)[x,y] = | I(k+1)[x,y] - I(k)[x,y] |;
(2) b(k,k-1)[x,y] = 1; if d(k,k-1) [x,y] >= T;
b(k,k-1)[x,y] = 0; if d(k,k-1) [x,y] < T;
b(k+1,k)[x,y] = 1 if d(k+1,k) [x,y] >= T;
b(k+1,k)[x,y] = 0 if d(k+1,k) [x,y] < T;
(3) B(k)[x,y] = 1 ; if b(k,k-1)[x,y] && b(k+1,k)[x,y] == 1 ;
B(k)[x,y] = 0 ; if b(k,k-1)[x,y] && b(k+1,k)[x,y] ==0 ;
比较关键的就是第2步的阈值T的选取问题，单纯用otsu算法分割貌似效果不太好，如果手动设置一个较小的值（如10）效果还行。
用otsu取阈值实现的一个三分差法代码。效果不是很好。
运行环境 VS2008＋OpenCV2.0＋windows XP .
[cpp] view plainprint?#include "highgui.h"
#include "cv.h"
#include "cxcore.h"
#include "cvaux.h"
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <windows.h>
using namespace std;
#pragma comment(lib, "highgui200.lib")
#pragma comment(lib, "cv200.lib")
#pragma comment(lib, "cxcore200.lib")
#pragma comment(lib, "cvaux200.lib")
#define GET_IMAGE_DATA(img, x, y) ((uchar*)(img->imageData + img->widthStep * (y)))[x]
int T = 10;
int Num[300];
int Sum[300];
void InitPixel(IplImage * img, int &_low, int &_top)
{
memset(Num,0,sizeof(Num));
memset(Sum,0,sizeof(Sum));
_low = 255;
_top = 0;
for(int i = 0;i < img->height;i++)
{
for(int j = 0;j < img->width;j++)
{
int temp = ((uchar*)(img->imageData + img->widthStep*i))[j];
if(temp < _low)
_low = temp;
if(temp > _top)
_top = temp;
Num[temp] += 1;
}
}
for(int i = 1 ; i < 256 ; i++)
{
Sum[i] = Sum[i-1]+ i*Num[i];
Num[i] += Num[i-1];
}
}
int otsu (IplImage *img)
{
int _low,_top,mbest=0;
float mn = img->height*img->width;
InitPixel(img,_low,_top);
float max_otsu = 0;
mbest = 0;
if( _low == _top)
mbest = _low;
else
{
for(int i = _low; i< _top ; i++)
{
float w0 = (float)((Num[_top]-Num[i]) / mn);
float w1 = 1 - w0;
float u0 = (float)((Sum[_top]-Sum[i])/(Num[_top]-Num[i]));
float u1 = (float)(Sum[i]/Num[i]);
float u = w0*u0 + w1*u1;
float g = w0*(u0 - u)*(u0 - u) + w1*(u1 - u)*(u1 - u);
if( g > max_otsu)
{
mbest = i;
max_otsu = g;
}
}
}
return mbest;
}
int main()
{
int ncount=0;
IplImage *image1=NULL;
IplImage *image2=NULL;
IplImage *image3=NULL;
IplImage *Imask =NULL;
IplImage *Imask1=NULL;
IplImage *Imask2=NULL;
IplImage *Imask3=NULL;
IplImage *mframe=NULL;
CvCapture *capture = cvCreateFileCapture("E:\\Motion\\IndoorGTTest2.avi");
//CvCapture *capture = cvCreateCameraCapture(0);
cvNamedWindow("src");
cvNamedWindow("dst");
cvNamedWindow("Imask1");
cvNamedWindow("Imask2");
cvNamedWindow("Imask3");
//cvCreateTrackbar("T","dst",&T,255,0);
while(mframe=cvQueryFrame(capture))
{
DWORD start=GetTickCount();
if(ncount>1000000000)
ncount=100;
ncount+=1;
if(ncount==1)
{
image1=cvCreateImage(cvGetSize(mframe),IPL_DEPTH_8U,1);
image2=cvCreateImage(cvGetSize(mframe),IPL_DEPTH_8U,1);
image3=cvCreateImage(cvGetSize(mframe),IPL_DEPTH_8U,1);
Imask =cvCreateImage(cvGetSize(mframe),IPL_DEPTH_8U,1);
Imask1=cvCreateImage(cvGetSize(mframe),IPL_DEPTH_8U,1);
Imask2=cvCreateImage(cvGetSize(mframe),IPL_DEPTH_8U,1);
Imask3=cvCreateImage(cvGetSize(mframe),IPL_DEPTH_8U,1);
cvCvtColor(mframe,image1,CV_BGR2GRAY);
}
if(ncount==2)
cvCvtColor(mframe,image2,CV_BGR2GRAY);
if(ncount>=3)
{
if(ncount==3)
cvCvtColor(mframe,image3,CV_BGR2GRAY);
else
{
cvCopy(image2,image1);
cvCopy(image3,image2);
cvCvtColor(mframe,image3,CV_BGR2GRAY);
}
cvAbsDiff(image2,image1,Imask1);
cvAbsDiff(image3,image2,Imask2);
//cvShowImage("Imask1",Imask1);
//cvShowImage("Imask2",Imask2);
int mbest1 = otsu(Imask1);
cvSmooth(Imask1, Imask1, CV_MEDIAN);
cvThreshold(Imask1,Imask1,mbest1, 255, CV_THRESH_BINARY);
int mbest2 = otsu(Imask2);
cvSmooth(Imask2,Imask2, CV_MEDIAN);
cvThreshold(Imask2,Imask2,mbest2, 255, CV_THRESH_BINARY);
cout<<mbest1<<" "<<mbest2<<endl;
cvAnd(Imask1,Imask2,Imask);
/*cvErode(Imask, Imask);
cvDilate(Imask,Imask);*/
DWORD finish=GetTickCount();
// cout<<finish-start<<"ms"<<endl;
cvShowImage("src",image2);
cvShowImage("dst",Imask);
}
char c = cvWaitKey(30);
if(c==27)
break;
}
return 0;
}
G. 机器视觉图像处理中，将标准图和实际图进行差分比较有哪些算法
题目本身就是一句算法。
还哪里来的其他算法。
将standard image与real image进行differential comparison
将算法实现就完成了。
是不是你对问题描述的不准确啊？
H. 差分法的计算原理
其实形象一点理解，我们可以作图，选取A（1,2）和点B（2,5）我们可以看到这时线段AO和线段BO（O为原点）的斜率都是一个分数，AO对应小分数（分子分母都比BO的小），BO对应大分数，且5/2>2/1我们将这两个点的坐标对应做差C（1,2），这不太形象，我们可以将AB连起来，这时，AB的斜率就是另外的一个分数，在坐标系中我们可以很容易看出，AB的斜率要比小值也就是AO斜率要大，这时，我们就能看出，
1。如果若差分数比小分数大，则大分数比小分数大；
再举其他的例子同理可以得到
2。若差分数比小分数小，则大分数比小分数小；
3。若差分数与小分数相等，则大分数与小分数相等。
现在对于3/4和1/2进行差分比较
差分后得（3-1）/(4-2)=2/2=1>1/2
故由上我们可知，3/4>1/2
I. 差分算法
diff差分数组，diff[i]就是nums[i]和nums[i-1]之差：
通过这个diff差分数组是可以反推出原始数组nums的：
这样构造差分数组diff，就可以快速进行区间增减的操作，如果你想对区间nums[i..j]的元素全部加 3，那么只需要让diff[i] += 3，然后再让diff[j+1] -= 3即可.
原理：
原理很简单，回想diff数组反推nums数组的过程，diff[i] += 3意味着给nums[i..]所有的元素都加了 3，然后diff[j+1] -= 3又意味着对于nums[j+1..]所有元素再减 3，综合起来，就是对nums[i..j]中的所有元素都加 3 了。
差分算法工具化