樣條子空間上的隨機采樣

李慧敏， 李水艷

(河海大學(xué) 理學(xué)院，江蘇 南京 211100)

1 引言

利用離散序列重構(gòu)連續(xù)信號(函數(shù))是信號處理的重要任務(wù)之一.Shannon-Whittaker采樣定理[1]成功地解決了帶限函數(shù)空間中的采樣重構(gòu)問題.在實際應(yīng)用中,用到的信號空間往往是非帶限函數(shù)空間,如平移不變空間[2-5].樣條子空間作為特殊的平移不變空間,在計算機圖形學(xué)[6]、計算機輔助設(shè)計[7]、信號和圖像處理[8]等領(lǐng)域起著至關(guān)重要的作用.對于樣條子空間中的函數(shù),如何確定合適的采樣點使函數(shù)能夠唯一地重構(gòu)出來,是信號處理中的一個關(guān)鍵問題.孫文昌等人在樣條子空間上的局部采樣[9]中給出了一個選取采樣點的方法,但該方法比較難驗證.為了更好地解決這一問題,本文利用隨機采樣的方法來研究樣條子空間上的函數(shù)重構(gòu)問題.

考慮由m階樣條φm生成的樣條子空間

中信號f∈Vm的隨機采樣重構(gòu)問題,其中φm=χ[0,1]*…*χ[0,1](m個卷積),χ[0,1]是有限區(qū)間[0,1]上的特征函數(shù),h為尺度參數(shù).首先給出隨機采樣集E∶={xi∶1≤i≤n}的刻畫條件,使得信號f能唯一地重構(gòu)出來,并且得到重構(gòu)概率,然后運用最小二乘法建立重構(gòu)模型和算法，最后通過數(shù)值實驗對模型和算法進行驗證.

2 隨機采樣的概率估計

對于有界區(qū)間Ω=[0,1]上的隨機采樣數(shù)據(jù)密度水平的概率估計,將有界區(qū)域Ω=[0,1]均勻地分成N=1/h個小區(qū)間Ωl=[hl,h(l+1)],其中0≤l≤N-1.

引理1 設(shè)隨機采樣集E∶={xi∶1≤i≤n}是一個獨立隨機變量序列,每個變量均勻分布在Ω=[0,1]上.對于每個子區(qū)間Ωl,使用#(E∩Ωl)表示E∩Ωl上的采樣點數(shù),則

證明對于任意的子區(qū)間Ωl?Ω,令

p∶=P(xi∈Ωl)=1/N

是n個獨立實驗中“成功”的概率,累積分布函數(shù)表示為F(0;n,p)∶=P{#(E∩Ωl)≤0}.通過Chernoff二項分布不等式[10],有

令#(E∩Ωl)≤0為事件Al,那么

結(jié)合基本概率公式,可得

特別地,當(dāng)n=N1+ε時,上式變?yōu)?/p>

3 樣條子空間函數(shù)可以唯一重構(gòu)的條件刻畫

若Vm中的信號f能在高概率下唯一地重構(gòu)出來，即存在唯一的序列{a(α)∶α∈I},使得

(1)

其中h=1/N,I={α∈∶suppφm∩Ω≠0}=[-m,N-1].

定理1 假設(shè)生成子φm具有一定的光滑性,隨機采樣集E∶={xi∶1≤i≤n}是一個獨立隨機變量序列,每個變量均勻分布在Ω=[0,1]上，則僅用有限個采樣值{f(xi)∶1≤xi≤n}就可以唯一地重構(gòu)信號f∈Vm,并且得到重構(gòu)概率為

其中,采樣點數(shù)n滿足n≥(N+m).

證明等式(1)的矩陣形式表示為

F=Aa

其中

F=[f(x1),f(x2),…,f(xn)]T

a=[a(-m),a(-m+1),…,a(N-1)]T

A=[φm(xi-α)]1≤i≤n,-m≤α≤N-1

4 模型與算法

通過求解

(2)

得到最優(yōu)解a*，進而有逼近解

將(2)式寫成矩陣的形式,得到優(yōu)化模型

(3)

其中Ai,α=φm(xi/h-α),I=[-m,N-1]，F(xiàn)=[f(x1),f(x2),…,f(xn)]T.

(4)

其中Ai,α=φm(xi/h-α),I=[-m,N-1]，Y=[y(x1),y(x2),…,y(xn)]T,基于此模型,給出如下算法:

步驟1:估計采樣點之間的距離hh≈min|xi-xj|i≠j

步驟2:生成矩陣AAi,α=φm(xi/h-α)

由定理1,可以得到矩陣A的列向量是線性無關(guān)的,所以最小二乘法的解是唯一的,信號f能夠被唯一地重構(gòu)出來.

5 數(shù)值實驗

為了驗證算法的有效性,利用MATLAB進行數(shù)值實驗,分別考慮無噪音的信號的隨機采樣重構(gòu)問題與有噪音的信號的隨機采樣重構(gòu)問題.

第一個實驗,設(shè)f1(x)=sin(5πx)2為未知連續(xù)信號,在[0,1]上進行隨機采樣E∶={xi∶1≤i≤20},得到采樣值{f1(xi)∶1≤i≤20},取尺度參數(shù)h=1/10,三次B-樣條[12]

作為樣條子空間的基.

圖1 無噪音的信號重構(gòu) 圖2 有噪音的信號重構(gòu)

第二個實驗,設(shè)f2(x)=cos(3πx)2為未知連續(xù)信號,在[0,1]上進行隨機采樣E∶={xi∶1≤i≤20},得到采樣值yi=f2(xi)+ηj,其中ηj服從正態(tài)分布N(0,0.02),參數(shù)和空間的選取與第一個實驗相同.

上述數(shù)值結(jié)果表明,該算法能夠較好地解決樣條子空間上有無噪音的信號采樣重構(gòu)問題.