差分圖演算法
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 了。
差分演算法工具化