一種基於第二代小波的原始信號重構方法與流程
2023-10-09 00:05:39
本發明屬於數據壓縮領域，尤其涉及一種基於第二代小波的原始信號重構方法，適用於傳統壓縮感知對非結構化海量網絡數據的重構。
背景技術：
壓縮感知作為一個新興的採樣理論，通過利用數據的稀疏特性，可以在遠低於奈奎斯特採樣率的條件下，獲取數據量遠小於原始信號的數據樣本，然後通過非線性算法重構原始信號。
傳統的壓縮感知技術是開發以用於應用於圖像壓縮領域的，由於圖像數據可用點陣的形式進行表示，用第一代小波作為稀疏基可以很好地對其進行稀疏表示。而對於非結構化海量網絡數據，由於其明顯的非結構化特性，以第一代小波作為稀疏基難以很好的對其進行稀疏表示，這將導致壓縮感知對非結構化海量網絡數據的質量顯著下降。
第二代小波方法相對於傳統小波算法，是一種更為快速有效的小波變換實現方法，不依賴Fourier變換，完全在時域完成了對雙正交小波濾波器的構造。這種構造方法在結構化設計和自適應構造方面突出優點彌補了傳統頻域構造方法的不足。在壓縮感知技術應用中，通過第二代小波作為稀疏基對原始信號進行稀疏表示，使得非結構化海量數據能夠被很好的稀疏表示。
技術實現要素：
本發明的目的在於提出一種基於第二代小波的原始信號重構方法，以解決傳統壓縮感知對於非結構化海量網絡數據的不適用性問題，以實現儘可能大的壓縮比和儘可能小的失真。
為實現上述目的，本發明的技術方案包括如下：
一種基於第二代小波的原始信號重構方法，包括以下步驟：
步驟1：對原始信號進行稀疏表示，通過稀疏基和原始信號得到稀疏係數；
步驟2：對原始信號進行採樣，由測量矩陣和原始信號得到測量值；
步驟3：對稀疏基、測量值及隨機數種子進行存儲；
步驟4：通過迭代得到稀疏係數，利用稀疏基對原始信號進行重構。
進一步根據所述基於第二代小波的原始信號重構方法，步驟1中所述對原始信號進行稀疏表示，通過稀疏基和原始信號得到稀疏係數：
對於給定的點集S＝{x1,x2,…,xn}，有x1<x2<…<xn，n＝k×2l，其中n,k,l均為正整數；
對於任意一個2k×2k的矩陣V，則VL表取矩陣V的下邊的k×2k半部分，VU表示取矩陣V的上邊的k×2k半部分，有
通過第二代小波作為稀疏基對原始信號x進行稀疏表示，使得非結構化海量數據能夠被很好的稀疏表示，對原始信號x進行稀疏表示，按如下步驟進行：
(1-1)構造2k×2k的矩陣M1,i，其中i＝1,…,n/2k，si＝(i-1)2k；
矩陣M1,i的正交基U1,i，U1,i＝[Orth(M1,i)]T，Orth表示求正交基運算；由U1,i得到U1：
由U1得到第一個基矩陣Ψ1，第一個基矩陣Ψ1是構造稀疏基Ψ時所必須的中間運算結果，Ψ1＝U1；
(1-2)構造一個2k×2k的矩陣M2,i，其中i＝1,…,n/2k，由M2,i得到U2,i，U2,i＝[Orth(M2,i)]T；再通過U2,i得到U2′：
其中n2＝n/4k，由U2′得到U2，其中In/2為(n/2)×(n/2)的單位矩陣；
由U2和U1，得到第二個基矩陣ψ2，ψ2＝U1U2；
按照構造矩陣M1,i的方法構造M1,2i和M1,2i-1；
(1-3)得到第j個基矩陣ψj，其中j＝2，…，log2(n/k)，構造2k×2k的矩陣Mj,i，其中i＝1,…,n/2k，由Mj,i可以得到Uj,i，Uj,i＝[Orth(Mj,i)]T，由Uj,i可以得到Uj′：
由Uj′可以得到Uj，
對於j＝2，…，log2(n/k)所得的Uj和U1，可以得到第j個基矩陣ψj，ψj＝U1U2…Uj；
(1-4)當j取得最大值log2(n/k)時，所得第j個基矩陣ψj即為稀疏基ψ，即
(1-5)通過稀疏基ψ和原始信號x得到稀疏係數s，具體的s＝ψ-1x，其中ψ-1表示求稀疏基ψ的逆矩陣；
所述稀疏係數s就是原始信號x在稀疏基ψ上稀疏表示的結果。
進一步根據所述基於第二代小波的原始信號重構方法，步驟2中所述對原始信號進行採樣，由測量矩陣和原始信號得到測量值；
構造一個大小為M×N的Bernoulli隨機矩陣作為測量矩陣Φ，其中每一個元素獨立服從Bernoulli分布，第i行、第j列個元素用Φi,j表示：
由測量矩陣Φ和原始信號x得到測量值y，y＝Φx＝Φψs＝As。
進一步根據所述基於第二代小波的原始信號重構方法，步驟3中所述對稀疏基、測量值及隨機數種子進行存儲：
將稀疏基ψ、測量值y和用作測量矩陣Φ的Bernoulli隨機矩陣的隨機數種子進行存儲，待需要對原始信號重構時進行調用；
所述隨機數種子是指計算機用於生成隨機矩陣的真隨機數，矩陣中的每一個元素都是通過一個來源於計算機系統時間的真隨機數經算法計算得到，所述真隨機數即隨機數種子；在種子一定，算法一定的情況下，獲得的隨機矩陣是相同的；在存儲時，不需要存儲傳輸整個測量矩陣Φ，只存儲隨機數種子；
進一步根據所述基於第二代小波的原始信號重構方法，步驟4中所述通過迭代得到稀疏係數，利用稀疏基對原始信號進行重構，按如下步驟進行：
(4-1)獲取測量值y、隨機數種子以及稀疏基ψ，生成測量矩陣Φ，並由測量矩陣Φ和稀疏基ψ得到傳感矩陣A，A＝Φψ；
(4-2)未開始迭代時的殘差r0＝y，未開始迭代時的索引集合迭代次數t的初始值1，其中t為迭代次數，最大迭代次數為tmax；
(4-3)由上次迭代得到的殘差rt-1和傳感矩陣A的行數M，得到門限Th，||·||2表示求矩陣的2範數，其中ts為門限參數ts，rt表示第t次迭代時的殘差；
由傳感矩陣A和殘差rt-1得到一個長為N的向量u，有u＝abs(ATrt-1)，abs(·)表示求模值；
對於1≤j≤N，依次計算，表示求向量內積，將得到的N個數值構成向量u，選擇u中大於門限Th的值，將對應傳感矩陣A的列序號j構成集合J0，所述集合為列序號集合，J0表示每次迭代找到的索引；
(4-4)索引集合Λt＝Λt-1∪J0，列集合At＝At-1∪aj，求y＝Atst的最小二乘解，得st的估計值更新殘差t＝t+1；
其中aj表示矩陣傳感矩陣A的第j列，At表示按索引Λt選出的傳感矩陣A的列集合；
若Λt＝Λt-1，或t>tmax，或rt＝0，則停止迭代；
重構所得在Λt處有非零項，其值為最後一次迭代所得稀疏係數st，為迭代結束時對稀疏係數s的最終估計值，st為第t次迭代時對稀疏係數s的估計值；
(4-5)迭代結束時，得到稀疏係數利用稀疏基ψ可重構原始信號，即得到原始信號x的估計值
所述估計值即為重構的原始信號。
本發明與現有技術相比，具有如下優點：
1.本發明由於使用第二代小波作為稀疏基對原始信號x進行稀疏表示，使得非結構化海量數據能夠被很好的稀疏表示，解決了傳統的基於第一代小波的壓縮感知技術對非結構化海量數據的不適用性問題，獲得了較大的壓縮比，第二代小波是多項式，所以具有計算速度快的優點。
2.本發明由於使用了分段正交匹配追蹤進行數據的重構，使得能夠通過測量值y，即原始信號x壓縮後的結果，在允許的失真範圍內恢復出原始信號x，對提高壓縮比提供了有力的保障。
附圖說明
圖1為本發明所述一種基於第二代小波的原始信號重構方法實現流程圖。
具體實施方式
為使本發明的目的、技術方案及優點更加清楚明白，以下結合附圖，對本發明所述方案和效果作進一步詳細描述。
如圖1所示，本發明對所述一種基於第二代小波的原始信號重構方法，具體步驟如下所述。
步驟1：對原始信號進行稀疏表示，通過稀疏基和原始信號得到稀疏係數。
對於給定的點集S＝{x1,x2,…,xn}，其中x1<x2<…<xn，n＝k×2l，n,k,l均為正整數。
對於任意一個2k×2k的矩陣V，則VL表取矩陣V的下邊的k×2k半部分，VU表示取矩陣V的上邊的k×2k半部分，有
通過第二代小波作為稀疏基對原始信號x進行稀疏表示，使得非結構化海量數據能夠被很好的稀疏表示，對原始信號x進行稀疏表示，按如下步驟進行：
(1-1)構造2k×2k的矩陣M1,i如下：
其中i＝1,…,n/2k，si＝(i-1)2k。
矩陣M1,i的正交基U1,i，U1,i＝[Orth(M1,i)]T，Orth表示求正交基運算，由U1,i得到U1：
由U1得到第一個基矩陣Ψ1，第一個基矩陣Ψ1是構造稀疏基Ψ時所必須的中間運算結果，Ψ1＝U1。
(1-2)構造一個2k×2k的矩陣M2,i，其中i＝1,…,n/2k，由M2,i得到U2，i，U2，i＝[Orth(M2，i)]T，再通過U2，i得到U2′：
其中n2＝n/4k，由U2′得到U2，其中In/2為(n/2)×(n/2)的單位矩陣。
由U2和U1，得到第二個基矩陣ψ2，ψ2＝U1U2。
按照構造矩陣M1，i的方法構造M1，2i和M1，2i-1。
(1-3)得到第j個基矩陣ψj，其中j＝2，…，log2(n/k)，構造2k×2k的矩陣Mj，i，其中i＝1，…，n/2k，由Mj，i可以得到Uj，i，Uj，i＝[Orth(Mj，i)]T，由Uj，i可以得到Uj′：
由Uj′可以得到Uj，
對於j＝2，…，log2(n/k)所得的Uj和U1，可以得到第j個基矩陣Ψj，ψj＝U1U2…Uj。
(1-4)當j取得最大值log2(n/k)時，所得第j個基矩陣ψj即為稀疏基ψ，即
(1-5)通過稀疏基ψ和原始信號x得到稀疏係數s，具體的s＝ψ-1x。其中ψ-1表示求稀疏基ψ的逆矩陣。
所述稀疏係數s就是原始信號x在稀疏基ψ上稀疏表示的結果。
步驟2：對原始信號進行採樣，由測量矩陣和原始信號得到測量值。
構造一個大小為M×N的Bernoulli隨機矩陣作為測量矩陣Φ，其中每一個元素獨立服從Bernoulli分布，第i行、第j列個元素用Φi,j表示：
由測量矩陣Φ和原始信號x得到測量值y，y＝Φx＝Φψs＝As。
步驟3：對稀疏基、測量值及隨機數種子進行存儲。
將稀疏基ψ、測量值y和用作測量矩陣Φ的Bernoulli隨機矩陣的隨機數種子進行存儲，待需要對原始信號重構時進行調用。
所述隨機數種子是指計算機用於生成隨機矩陣的真隨機數，矩陣中的每一個元素都是通過一個來源於計算機系統時間的真隨機數經算法計算得到，所述真隨機數即隨機數種子。在種子一定，算法一定的情況下，獲得的隨機矩陣是相同的。在存儲時，不需要存儲傳輸整個測量矩陣Φ，只存儲隨機數種子。
步驟4：通過迭代得到稀疏係數，利用稀疏基對原始信號進行重構。
按如下步驟進行：
(4-1)獲取測量值y、隨機數種子以及稀疏基ψ，生成測量矩陣Φ，並由測量矩陣Φ和稀疏基ψ得到傳感矩陣A，A＝Φψ；
(4-2)未開始迭代時的殘差r0＝y，未開始迭代時的索引集合迭代次數t的初始值1，其中t為迭代次數，最大迭代次數為tmax；
(4-3)由上次迭代得到的殘差rt-1和傳感矩陣A的行數M，得到門限Th，||·||2表示求矩陣的2範數，其中ts為門限參數ts，rt表示第t次迭代時的殘差；
由傳感矩陣A和殘差rt-1得到一個長為N的向量u，u＝abs(ATrt-1)，abs(·)表示求模值；
對於1≤j≤N，依次計算，表示求向量內積，將得到的N個數值構成向量u，選擇u中大於門限Th的值，將對應傳感矩陣A的列序號j構成集合J0，所述集合為列序號集合，J0表示每次迭代找到的索引；
(4-4)索引集合Λt＝Λt-1∪J0，列集合At＝At-1∪aj，求y＝Atst的最小二乘解，得st的估計值更新殘差t＝t+1；
其中aj表示矩陣傳感矩陣A的第j列，At表示按索引Λt選出的傳感矩陣A的列集合；
若ΛΛ＝Λt-1，或t>tmax，或rt＝0，則停止迭代；
重構所得在Λt處有非零項，其值為最後一次迭代所得稀疏係數st，為迭代結束時對稀疏係數s的最終估計值，st為第t次迭代時對稀疏係數s的估計值；
(4-5)迭代結束時，得到稀疏係數利用稀疏基ψ可重構原始信號，即得到原始信號x的估計值
所述估計值即為重構的原始信號。
以上僅是對本發明的優選實施方式進行了描述，並不將本發明的技術方案限制於此，本領域技術人員在本發明的主要技術構思的基礎上所作的任何公知變形都屬於本發明所要保護的技術範疇，本發明具體的保護範圍以權利要求書的記載為準。