域適應演算法

㈠ 視覺追蹤的典型演算法

（1）基於區域的跟蹤演算法
基於區域的跟蹤演算法基本思想是：將目標初始所在區域的圖像塊作為目標模板，將目標模板與候選圖像中所有可能的位置進行相關匹配，匹配度最高的地方即為目標所在的位置。最常用的相關匹配准則是差的平方和准則，(Sum of Square Difference，SSD)。
起初，基於區域的跟蹤演算法中所用到的目標模板是固定的，如 Lucas 等人提出 Lucas-Kanade 方法，該方法利用灰度圖像的空間梯度信息尋找最佳匹配區域，確定目標位置。之後，更多的學者針對基於區域方法的缺點進行了不同的改進，如：Jepson 等人提出的基於紋理特徵的自適應目標外觀模型[18],該模型可以較好的解決目標遮擋的問題，且在跟蹤的過程中採用在線 EM 演算法對目標模型進行更新；Comaniciu 等人[19]提出了基於核函數的概率密度估計的視頻目標跟蹤演算法，該方法採用核直方圖表示目標，通過 Bhattacharya 系數計算目標模板與候選區域的相似度，通過均值漂移(MeanShift)演算法快速定位目標位置。
基於區域的目標跟蹤演算法採用了目標的全局信息，比如灰度信息、紋理特徵等，因此具有較高的可信度，即使目標發生較小的形變也不影響跟蹤效果，但是當目標發生較嚴重的遮擋時，很容易造成跟蹤失敗。
（2）基於特徵的跟蹤方法
基於特徵的目標跟蹤演算法通常是利用目標的一些顯著特徵表示目標，並通過特徵匹配在圖像序列中跟蹤目標。該類演算法不考慮目標的整體特徵，因此當目標被部分遮擋時，仍然可以利用另一部分可見特徵完成跟蹤任務，但是該演算法不能有效處理全遮擋、重疊等問題。
基於特徵的跟蹤方法一般包括特徵提取和特徵匹配兩個過程：
a) 特徵提取
所謂特徵提取是指從目標所在圖像區域中提取合適的描繪性特徵。這些特徵不僅應該較好地區分目標和背景，而且應對目標尺度伸縮、目標形狀變化、目標遮擋等情況具有魯棒性。常用的目標特徵包括顏色特徵、灰度特徵、紋理特徵、輪廓、光流特徵、角點特徵等。D.G. Lowe 提出 SIFT(Scale Invariant Feature Transform)演算法[20]是圖像特徵中效果較好的一種方法，該特徵對旋轉、尺度縮放、亮度變化具有不變性，對視角變化、仿射變換、雜訊也具有一定的穩定性。
b) 特徵匹配
特徵匹配就是採用一定的方式計算衡量候選區域與目標區域的相似性，並根據相似性確定目標位置、實現目標跟蹤。在計算機視覺領域中，常用的相似性度量准則包括加權距離、Bhattacharyya 系數、歐式距離、Hausdorff 距離等。其中，Bhattacharyya 系數和歐式距離最為常用。
Tissainayagam 等人提出了一種基於點特徵的目標跟蹤演算法[21]。該演算法首先在多個尺度空間中尋找局部曲率最大的角點作為關鍵點，然後利用提出的MHT-IMM 演算法跟蹤這些關鍵點。這種跟蹤演算法適用於具有簡單幾何形狀的目標，對於難以提取穩定角點的復雜目標，則跟蹤效果較差。
Zhu 等人提出的基於邊緣特徵的目標跟蹤演算法[22]，首先將參考圖像劃分為多個子區域，並將每個子區域的邊緣點均值作為目標的特徵點，然後利用類似光流的方法進行特徵點匹配，從而實現目標跟蹤。
（3）基於輪廓的跟蹤方法
基於輪廓的目標跟蹤方法需要在視頻第一幀中指定目標輪廓的位置，之後由微分方程遞歸求解，直到輪廓收斂到能量函數的局部極小值，其中，能量函數通常與圖像特徵和輪廓光滑度有關。與基於區域的跟蹤方法相比，基於輪廓的跟蹤方法的計算復雜度小，對目標的部分遮擋魯棒。但這種方法在跟蹤開始時需要初始化目標輪廓，因此對初始位置比較敏感，跟蹤精度也被限制在輪廓級。
Kass 等人[23]於 1987 年提出的活動輪廓模型(Active Contour Models，Snake)，通過包括圖像力、內部力和外部約束力在內的三種力的共同作用控制輪廓的運動。內部力主要對輪廓進行局部的光滑性約束，圖像力則將曲線推向圖像的邊緣，而外部力可以由用戶指定，主要使輪廓向期望的局部極小值運動，。
Paragios 等人[24]提出了一種用水平集方法表示目標輪廓的目標檢測與跟蹤演算法，該方法首先通過幀差法得到目標邊緣，然後通過概率邊緣檢測運算元得到目標的運動邊緣，通過將目標輪廓向目標運動邊緣演化實現目標跟蹤。
（4）基於模型的跟蹤方法[25]
在實際應用中，我們需要跟蹤的往往是一些特定的我們事先具有認識的目標，因此，基於模型的跟蹤方法首先根據自己的先驗知識離線的建立該目標的 3D 或2D 幾何模型，然後，通過匹配待選區域模型與目標模型實現目標跟蹤，進而在跟蹤過程中，根據場景中圖像的特徵，確定運動目標的各個尺寸參數、姿態參數以及運動參數。
Shu Wang 等人提出一種基於超像素的跟蹤方法[26]，該方法在超像素基礎上建立目標的外觀模板，之後通過計算目標和背景的置信圖確定目標的位置，在這個過程中，該方法不斷通過分割和顏色聚類防止目標的模板漂移。
（5）基於檢測的跟蹤演算法
基於檢測的跟蹤演算法越來越流行。一般情況下，基於檢測的跟蹤演算法都採用一點學習方式產生特定目標的檢測器，即只用第一幀中人工標記的樣本信息訓練檢測器。這類演算法將跟蹤問題簡化為簡單的將背景和目標分離的分類問題，因此這類演算法的速度快且效果理想。這類演算法為了適應目標外表的變化，一般都會採用在線學習方式進行自更新，即根據自身的跟蹤結果對檢測器進行更新。

㈡ LMS自適應演算法分析及在數字濾波器設計中的應用

自適應過程一般採用典型LMS自適應演算法，但當濾波器的輸入信號為有色隨機過程時，特別是當輸入信號為高度相關時，這種演算法收斂速度要下降許多，這主要是因為輸入信號的自相關矩陣特徵值的分散程度加劇將導致演算法收斂性能的惡化和穩態誤差的增大。此時若採用變換域演算法可以增加演算法收斂速度。變換域演算法的基本思想是：先對輸入信號進行一次正交變換以去除或衰減其相關性，然後將變換後的信號加到自適應濾波器以實現濾波處理，從而改善相關矩陣的條件數。因為離散傅立葉變換�DFT本身具有近似正交性，加之有FFT快速演算法，故頻域分塊LMS�FBLMS演算法被廣泛應用。

FBLMS演算法本質上是以頻域來實現時域分塊LMS演算法的，即將時域數據分組構成N個點的數據塊，且在每塊上濾波權系數保持不變。其原理框圖如圖2所示。FBLMS演算法在頻域內可以用數字信號處理中的重疊保留法來實現，其計算量比時域法大為減少，也可以用重疊相加法來計算，但這種演算法比重疊保留法需要較大的計算量。塊數據的任何重疊比例都是可行的，但以50％的重疊計算效率為最高。對FBLMS演算法和典型LMS演算法的運算量做了比較，並從理論上討論了兩個演算法中乘法部分的運算量。本文從實際工程出發，詳細分析了兩個演算法中乘法和加法的總運算量，其結果為：

復雜度之比＝FBLMS實數乘加次數／LMS實數乘加次數＝（25Nlog2N＋2N－4）／[2N(2N－1)]�

採用ADSP的C語言來實現FBLMS演算法的程序如下：

for(i＝0;i＜＝30;i＋＋)

{for(j＝0;j＜＝n－1;j＋＋)

{in[j]＝input[i×N＋j;]

rfft(in,tin,nf,wfft,wst,n);

rfft(w,tw,wf,wfft,wst,n);

cvecvmlt(inf,wf,inw,n);

ifft(inw,t,O,wfft,wst,n);

for(j＝0,j＜＝N－1;j＋＋)

{y[i×N＋j]＝O[N＋j]．re;

e[i×N＋j]＝refere[i×N＋j]－y[i×N＋j];

temp[N＋j]＝e[i×N＋j;}

rfft(temp,t,E,wfft,wst,n);

for(j＝0;j＜＝n－1;j＋＋)

{inf_conj[j]＝conjf(inf[j]);}��

cvecvmlt(E,inf_conj,Ein,n);

ifft(Ein,t,Ein,wfft,wst,n);

for(j＝0;j＜＝N－1;j＋＋)

{OO[j]＝Ein[j]．re;

w[j]＝w[j]＋2＊u＊OO[j];}��

}

在EZ－KIT測試板中，筆者用匯編語言和C語言程序分別測試了典型LMS演算法的運行速度，並與FBLMS演算法的C語言運行速度進行了比較，表2所列是其比較結果，從表2可以看出濾波器階數為64時，即使是用C語言編寫的FBLMS演算法也比用匯編編寫的LMS演算法速度快20％以上，如果濾波器的階數更大，則速度會提高更多。

㈢ 【高分懸賞】用C/C++語言設計一個適應演算法（最先、最佳或最壞適應演算法）

考的是內存的動態劃分區域內容，很好寫啊
1.可以用數字來模擬內存區域劃分情況，比如建一個100大小的數組（結構為struc （區號，值），值為0表示空閑，值為1表示佔用，初始化幾個已確定佔有的分區，分區一，1-5 佔有，6-12 空閑，。。。。。。。，並建立空閑區域表，很簡單，從頭到尾對數組掃描下就知道了
2.最先適應：從內存開始地址找到第一個大於請求大小的連續空閑區域，如請求5個空間，那就在剛開始6-12空閑處建立分區二 ，6-11 ，佔用
3.最佳適應：指所有空閑塊最適應請求大小的那塊，min（空閑塊大小-請求大小）
4.最壞：指適應請求大小，且最大的那塊空閑區域