壓縮感知（Compressed Sensing, CS）是一種利用稀疏信號的先驗知識，用遠少于奈奎斯特采樣定理要求的樣本數目恢復整個信號的技術。正交匹配追蹤（Orthogonal Matching Pursuit, OMP）是一種常見的貪婪算法（Greedy algorithm），用于解決壓縮感知中的信號重構問題。OMP算法試圖找到一組稀疏基，這些基與測量值之間有最大的相關性，并且用于迭代地重構原始信號。
OMP算法
下面是OMP算法的簡要步驟：
-
初始化殘差 ( r_0 = y )，其中 ( y ) 是測量向量，稀疏性基矩陣 ( \Phi )，觀測矩陣 ( \Psi )，支撐集 ( \Lambda = \emptyset )（選擇的基函數的索引集），和迭代計數器 ( k = 0 )。
-
找到與當前殘差最相關的列向量（原子） ( \phi_i )
( i = \arg\max_{j} | \langle r_k, \phi_j \rangle | )。 -
將選中的索引 ( i ) 加到支撐集 ( \Lambda ) 中 ( \Lambda = \Lambda \cup {i} )。
-
用最小二乘法從支撐集( \Lambda )上的列構建信號的近似解，即解線性方程 ( \Psi_{\Lambda} x’ = y )，得到( x’{\Lambda} )，在( \Lambda )上的系數，其中 ( \Psi{\Lambda} ) 表示 ( \Psi ) 的列僅包含 ( \Lambda ) 中索引對應的列。
-
更新殘差 ( r_{k+1} = y - \Psi_{\Lambda} x’ )。
-
檢查結束條件（例如，殘差足夠小，( ||r_{k+1}||_2 < \epsilon ) 或已達到預定的迭代次數）。如果未達到結束條件，( k = k + 1 ) 并返回步驟 2。
-
輸出重建信號，將 ( x’ ) 在非 ( \Lambda ) 的位置上填充零。
MATLAB代碼
以下是用MATLAB實現上述過程的代碼示例：
% 定義參數
N = 128; % 信號長度
M = 32; % 測量數量
K = 10; % 稀疏度（信號中非零值數量）% 生成一個 K-稀疏信號（隨機位置上有非零值）
x = zeros(N, 1);
q = randperm(N);
x(q(1:K)) = randn(K, 1);% 創建一個隨機高斯測量矩陣 Phi
Phi = randn(M, N) / sqrt(M);% 生成測量值 y
y = Phi * x;% 調用 OMP 算法
x_hat = OMP(y, Phi, eye(N), K);% 繪制原始信號和恢復信號
figure;
subplot(2, 1, 1);
stem(x, 'b');
title('原始稀疏信號');
subplot(2, 1, 2);
stem(x_hat, 'r');
title('OMP恢復信號');% OMP 函數
function x_hat = OMP(y, Phi, Psi, K)% y - 測量向量% Phi - 傳感矩陣% Psi - 稀疏基矩陣（在這里是單位矩陣）% K - 稀疏度或迭代次數% 初始化r = y; % 初始殘差（即測量值）index_set = []; % 支撐集合x_hat = zeros(size(Psi, 2), 1); % 估計信號初始化for k = 1:K% 計算相關性correlations = abs(Phi'*r);% 選擇具有最大相關性的索引[~, idx] = max(correlations);index_set = union(index_set, idx);% 使用當前支撐集合進行最小二乘求解x_temp = zeros(size(Psi, 2), 1);x_temp(index_set) = pinv(Phi(:, index_set)) * y;% 更新殘差r = y - Phi(:, index_set) * x_temp(index_set);% 檢查停止準則，可以是基于殘差的if norm(r) < 1e-6breakendendx_hat(index_set) = x_temp(index_set);
end
輸出結果
輸出結果如下，上面是原始信號，下面是恢復后的信號。
相關博文
理解并實現OpenCV中的圖像平滑技術
OpenCV中的邊緣檢測技術及實現
OpenCV識別人臉案例實戰
入門OpenCV：圖像閾值處理
我的圖書
下面兩本書歡迎大家參考學習。
OpenCV輕松入門
李立宗，OpenCV輕松入門，電子工業出版社，2023
本書基于面向 Python 的 OpenCV(OpenCV for Python)，介紹了圖像處理的方方面面。本書以 OpenCV 官方文檔的知識脈絡為主線，并對細節進行補充和說明。書中不僅介紹了 OpenCV 函數的使用方法，還介紹了函數實現的算法原理。
在介紹 OpenCV 函數的使用方法時，提供了大量的程序示例，并以循序漸進的方式展開。首先，直觀地展示函數在易于觀察的小數組上的使用方法、處理過程、運行結果，方便讀者更深入地理解函數的原理、使用方法、運行機制、處理結果。在此基礎上，進一步介紹如何更好地使用函數處理圖像。在介紹具體的算法原理時，本書盡量使用通俗易懂的語言和貼近生活的實例來說明問題，避免使用過多復雜抽象的公式。
本書適合計算機視覺領域的初學者閱讀，包括在校學生、教師、專業技術人員、圖像處理愛好者。
本書第1版出版后，深受廣大讀者朋友的喜愛，被很多高校選為教材，目前已經累計重印9次。為了更好地方便大家學習，對本書進行了修訂。
計算機視覺40例
李立宗，計算機視覺40例，電子工業出版社，2022
近年來，我深耕計算機視覺領域的課程研發工作，在該領域尤其是OpenCV-Python方面積累了一點兒經驗。因此，我經常會收到該領域相關知識點的咨詢，內容涵蓋圖像處理的基礎知識、OpenCV工具的使用、深度學習的具體應用等多個方面。為了更好地把所積累的知識以圖文的形式分享給大家，我將該領域內的知識點進行了系統的整理，編寫了本書。希望本書的內容能夠對大家在計算機視覺方向的學習有所幫助。
本書以OpenCV-Python（the Python API for OpenCV）為工具，以案例為載體，系統介紹了計算機視覺從入門到深度學習的相關知識點。
本書從計算機視覺基礎、經典案例、機器學習、深度學習、人臉識別應用等五個方面對計算機視覺的相關知識點做了全面、系統、深入的介紹。書中共介紹了40余個經典的計算機視覺案例，其中既有字符識別、信息加密、指紋識別、車牌識別、次品檢測等計算機視覺的經典案例，也包含圖像分類、目標檢測、語義分割、實例分割、風格遷移、姿勢識別等基于深度學習的計算機視覺案例，還包括表情識別、駕駛員疲勞監測、易容術、識別年齡和性別等針對人臉的應用案例。
在介紹具體的算法原理時，本書盡量使用通俗易懂的語言和貼近生活的示例來說明問題，避免使用復雜抽象的公式來介紹。
本書適合計算機視覺領域的初學者閱讀，適于在校學生、教師、專業技術人員、圖像處理愛好者使用。
)
