1、1XIDIAN UniversityIntelligent Perception and Image Understanding Key Lab of Ministry of China压缩感知理论与应用压缩感知理论与应用智能感知与图像理解教育部重点实验室 2011年8月Intelligent Perception and Image Understanding Key Lab of Ministry of China2上次课内容回顾上次课内容回顾 Lecture 1： 压缩感知概述压缩感知概述 为什么研究压缩感知为什么研究压缩感知 压缩感知的涵义压缩感知的涵义 压缩感知的过程压缩感知的过程
2、压缩感知的关键问题压缩感知的关键问题3From Nyquist to CS4CompressionOriginal 2500 KB100%Compressed 950 KB38%Compressed 392 KB15%Compressed 148 KB6%“Can we not just directly measure the part that will not end up being thrown away ?” Donoho5Sparse representation of an image via a multiscale wavelet transform.(a) Origina
3、l image. (b) Wavelet representation. Large coefficients are represented by light pixels, while small coefficients are represented by dark pixels. Observe that most of the wavelet coefficients are close to zero.Sparse in wavelet-domain6Sparse approximation of a natural image. (a) Original image.(b) A
4、pproximation of image obtained by keeping only the largest 10% of the wavelet coefficients.Sparse in wavelet-domain7Our Point-Of-ViewCompressed Sensing(CS) must be based on sparsity and compressibility.The signals must be sparse in time-domain or in frquency-domain.8Compressed Sensing“Can we not jus
5、t directly measure the part that will not end up being thrown away ?” Donoho“sensing as a way of extracting information about an object from a small number of randomly selected observations”Cands et. al.Nyquist rateSamplingAnalogAudioSignalCompression(e.g. MP3)High-rateLow-rateCompressedSensing9Conc
6、eptGoal: Identify the bucket with fake coins. Nyquist:Weigh a coinfrom each bucketCompressionBucket #numbers1 numberCompressed Sensing:Bucket #1 numberWeigh a linear combinationof coins from all buckets10Mathematical Toolsy Axnon-zero entries at least measurementsRecovery: brute-force, convex optimi
7、zation, greedy algorithms, and more11CS theory Compressed sensing (2003/4 and on) Main resultsMaximal cardinality of linearly independent column subsetsHard to compute !is uniquely determined by Donoho and Elad, 2003Smallest number of columns that are linearly-dependent.12is uniquely determined by i
8、s random with high probabilityDonoho, 2006 and Cands et. al., 2006NP-hardConvex and tractableGreedy algorithms: OMP, FOCUSS, etc.Donoho, 2006 and Cands et. al., 2006Tropp, Cotter et. al. Chen et. al. and many otherCompressed sensing (2003/4 and on) Main resultsCS theory Donoho and Elad, 200313RIP cr
9、iterion(a)The measurements can maintain the energy of the original time-domain signal .(b)If is sparse, the must be dense to maintain the energy. 14Vector spaceUnit spheres in for the norms with , and for the quasinorm with 15Vector spaceThe norms is used to reconstruct the signal Best approximation
10、 of a point in by a one-dimensional subspace using the norms for , and the quasinorm with 16Lecture 2 : Modern Sampling Methods and CS c n c n c n17Sampling: “Analog Girl in a Digital World” Judy Gorman 99Digital worldAnalog worldSignal processingDenoisingImage analysis ReconstructionD2ASamplingA2D
11、c n c n c n c n c n(Interpolation)18Applications:Sampling Rate ConversionCommon audio standards: 8 KHz (VOIP, wireless microphone, ) 11.025 KHz (MPEG audio, ) 16 KHz (VOIP, ) 22.05 KHz (MPEG audio, ) 32 KHz (miniDV, DVCAM, DAT, NICAM, ) 44.1 KHz (CD, MP3, ) 48 KHz (DVD, DAT, ) 19Lens distortion corr
12、ectionImage scalingApplications:Image Transformations20 Applications: CT Scans21Applications: Spatial Superresolution22Our Point-Of-ViewThe field of sampling was traditionally associated with methods implemented either in the frequency domain, or in the time domainSampling can be viewed in a broader
13、 sense of projection onto any subspace or union of subspacesCan we sample a signal below Nyquist sampling rate.(We must know something about the signals).23Shannons sampling theorem revisited 24Cauchy (1841):Whittaker (1915) - Shannon (1948):A. J. Jerri, “The Shannon sampling theorem - its various e
14、xtensions and applications: A tutorial review”, Proc. IEEE, pp. 1565-1595, Nov. 1977.Bandlimited Sampling Theorems25Limitations of Shannons TheoremTowards more robust DSPs:General inputsNonideal sampling: general pre-filters, nonlinear distortionsSimple interpolation kernels26Generalized anti-aliasi
15、ng filterSampling ProcessSampling functions27Employ estimation techniques Sampling Process Noise28Signal Priorsx(t) bandlimitedx(t) piece-wise linearDifferent priors lead to different reconstructions29SparsityIf a sequence has elements and only of them are nonzeros .Then the sequence is sparse.If a
16、sequence is a sparse vector, then the30 Signal Priors：Sparsity PriorsWavelet transform of images is commonly sparseSTFT transform of speech signals is commonly sparseFourier transform of radio signals is commonly sparse31From discrete to analogDiscrete Compressed SensingAnalog Compressive Sampling32
17、Analog Compressed SensingA signal with a multiband structure in some basisno more than N bands, max width B, bandlimited to (Mishali and Eldar 2007)Each band has an uncountable number of non-zero elementsBand locations lie on an infinite gridBand locations are unknown in advanceWhat is the definitio
18、n of analog sparsity ?33Sampling and ReconstructionSamplingReconstruction34Union of subspaces35If the filter is different from ,then a multirate correction system must be given.(In practice, the filters are often undesirable).Problem36Sub-Nyquist samplingBoth process and recovery are based on lowrat
19、e computation.The raw data can be directly stored.37Some questions about the Sub-Nyquist samplingHow to obtain the digital signal at a sub-nyquist rate?Can we reconstruct the signal with high probability approximately?38Sub-Nyquist sampling and Compressed Sensing c n c n c n39Multi-Band Sensing: Goa
20、lsbandsSamplingReconstructionGoal: Perfect reconstructionConstraints:Minimal sampling rateFully blind systemAnalogInfiniteAnalogWhat is the minimal rate ?What is the sensing mechanism ?How to reconstruct from infinite sequences ?40Sub-Nyquist sampling Landau minimum rate means sampling at of the Nyq
21、uist rate can reconstruct the signal perfectly.（but the spectral support must be known） f1B2B41Nonuniform samplingAnalog signalIn each block of samples, only are kept, as described byPoint-wise samples023002233Multi-Coset: Periodic Non-uniform on the Nyquist gridMMMMMT7M mm Mm =3 mii=1C = ci0cM-142N
22、onuniform samplingx t（ ）1t = c Tmt= c Tt=nMTt=nMT ()x nx nTDenote by the sequence of samples taken at the Nyquist rate.Therefore， in which . ()ciixnx nMTcT()itnMc T43Nonuniform samplingThe building blocks are uniform samplers at rate , so that the average sampling rate is ,which is lower than the Ny
23、quist rate where .m1 / MTm/ MT1/Tm M44Nonuniform samplingReconstruction of the original signal is achieved if we recover its spectral components . But there are fewer equations than the unknown for each . HOW TO RECONSTRUCT THE SIGNAL0( )() ()rrXfX ffMTF010,MTFr1()0fH-12021()exp()( )iLjfTicrrjcrXeXf
24、MTL( )x t( )rXf( )m()L0f F45Nonuniform samplingA method should be used to reduce the degree of the problem.Some subcell are active,while the others are not.The analog signal can be reconstructed perfectly if the amplitude and locations of has been known.( )X fff( )X f( )X f46Some problem 1 Practical
25、 ADCs introduce an inherent bandwidth limitation,which distorts the samples. Any spectral content beyond bHz is attenuated and distorted. 2 Another practical issue of multicoset sampling, arises from the time shift elements. Maintaining accurate time delays between the ADCs in the order of the Nyqui
26、st interval is difficult.47Introduce to RDTo solve the parctical problems somethings about the RD(random demodulated) methord can be used.48a Our system exploits spread-spectrum techniques from communication theory . An analog mixing front-end aliases the spectrum, such that a spectrum portion from
27、each band appears in baseband.b Sign alternating functions can be implemented by a standard(high rate) shift register. Todays technology allows to reach alternation rates of 23 GHz and even 80GHz .c Blind multiband signal(arbitrary spectral locations) can be reconstructed by this system with high pr
28、obablity.Advantage49多频带信号-许多信号只占用了少量带宽，因而具有稀疏性子空间采样理论子空间采样理论MWC模块模块50这里我们需要大量的滤波器，才能精确的重构，也就是 值越大越好（对应的采样频率也逐渐增大），由于信号的稀疏性，一般要求 ， 为频带个数4mNmN51实际采样框图5253A傅里叶变换原子傅里叶变换原子54如果是离散信号的重构，我们可以直接通过优化求解，模拟信号我们有无穷多个方程要解，必须转化成有限的模型，高概率的重构原始信号引入一个CTFCTF模型模型，通过 和支撑区间 ，我们可以重构出信号( )x tyS55AIC via Random Demodulatio
29、n理论框图理论框图 公式描述公式描述56Qusi-Toeplitz矩阵观测矩阵观测理论框图理论框图几个参数的说明 B随机滤波器的长度，随机滤波器的长度，d是信号的长度，是信号的长度，N是采样点数，是采样点数，s是原始信号，是原始信号，h是随机滤波器是随机滤波器ys ()yD s h/d N可以看成是可以看成是其中观测矩阵其中观测矩阵 为每一行元素移位为每一行元素移位 个单元，构成的观测矩阵个单元，构成的观测矩阵570.10.20.30.40.50.60.70.800.10.20.30.40.50.60.70.80.91sampling rateerror=1e-25 B=4B=16B=64B=
30、128GaussianBenoulli实验结果实验结果58501001502002502040608010012059 Definition：Those that are determined by a finite number of parameters per time unit. The -local rate of innovation of a signal x(t), denoted , is the minimal number of parameters defining any length- segment of x(t), divided by . An FRI sig
31、nal is one for which is finite, at least for large enough .Perhaps the simplest class of FRI signals corresponds to functions that can be expressed asFinite rate of innovation Signals60This set of signals is a linear subspace of L2, which is often termed a shift-invariant (SI) space. Finite rate of
32、innovation Signals61A union of subspacesThis model generalizes the family of multiband signalsThe frequencies determine the subspace and the amplitudes a,m determine the position within the subspace.62Our goal is to recover x by observing N generalized samples c = (c1, . . . , cN)T obtained as where
33、 S : H RN is some (possibly nonlinear) Frechet differentiable operator. This representation is more general than the widely used linear setting, in whichfor some set of vectors sn in H. In particular, it may account for nonlinear distortions introduced by the sampling device. For example, S can repr
34、esent the samples where f() is a nonlinear sensor response. We say that a sampling operator S is stable with respect to X if there exist constants 0 s s such thatfor all x1, x2 XSampling method6364The pulse shape is known a-priori, and therefore the signal has only 2K degrees of freedom per period.S
35、ince x is periodic it can be represented in terms of its Fourier series coefficientswhere in a we used Poisson summation formula, and65where uk and p-1 denotes the multiplicative inverse of p. Since p is known a-priori, we assume for simplicity of notation that p=1 .In order to nd the values uk in (
36、1.23), let h denote the filter whose z-transform is, where the last equality is due to the fact that h=0. The filter is called an annihilating filter , since it zeroes the signal xm. Its roots uniquely define the set of values uk, provided that the locations tk are distinct.666768Sinc kernels69E-spl
37、ine kernels70Sos kernels71Super-resolution72Ultrasound imaging73Super-resolution radar74Sinc函数观测矩阵函数观测矩阵751112220sin (1) sin (2)sin ()( , )sin (1) sin (2)sin ()sin (1) sin (2)sin ()MMMtttcccNTTTtttMm ncccNTTTtttcccNTTTSinc函数观测矩阵函数观测矩阵76202( , )sin ()sin ()PmmPppttMm ncnpNcnpNTT加入加入 个周期的观测矩阵个周期的观测矩阵P
38、1,1mMnN1()()exp(2)ccpkkkf tpNfjtNNNPoissonPoisson求和公式的变形求和公式的变形sincfccf为为 的傅里叶变换的傅里叶变换cf20121(,)exp2()NmNKtkMm njnNNT用有限个求和表示无穷多个周期相加的观测矩阵用有限个求和表示无穷多个周期相加的观测矩阵Sinc函数观测矩阵函数观测矩阵77Compressed SensingExplosion of interest in the idea of CS: Recover a vector x from a small number of measurements y=AxMany
39、beautiful papers covering theory, algorithms, and applications78Analog Compressed SensingCan we use these ideas to build new sub-Nyquist A/D converters? Prior work: Yu et. al., Ragheb et. al., Tropp et. al. vector xfew nonzero values random/det. matrix convex optimizationgreedy methods analog signal
40、 x(t) ? RF hardware need to recover analog input or specific data (demodulation)79One approach to treating continuous-time signals within the CS framework is via discretizationAlternative: Use more standard sampling techniques to convert the signal from analog to digital and then rely on CS methods
41、in the digital domain (Xampling = CS + Sampling)Possible benefits: Simple hardware, compatibility with existing methods, smaller size digital problemsPossible drawbacks: SNR sensitivitiesCan we tie the two worlds together?Sampling/Compressed Sensing80Robustness in the Presence of Noise Gedalyahu, Tu
42、r & Eldar (2010)Proposed scheme:Mix & integrateTake linear combinations from which Fourier coeff. can be obtained Supports general pulse shapes (time limited) Operates at the rate of innovation Stable in the presence of noise achieves the Cramer-Rao bound Practical implementation based on the MWCFou
43、rier coeff. vectorSamples81Sub-Nyquist sampler in hardwareCombines analog preprocessing with digital post processingSupporting theory proves the concept and robustness for a variety of applications including multiband signalsAllows time delay recovery from low-rate samples (Gedalyahu and Eldar 09-10
44、) Applications to ultrasound (Tur and Eldar 09)Xampling: Sub-Nyquist Sampling(Mishali and Eldar, 08-10)82Online Demonstrations GUI package of the MWCVideo recording of sub-Nyquist sampling + carrier recovery in lab83Can these ideas be exploited to characterize fundamental limits in other areas? Degr
45、ees of FreedomToday: Applications to linear time-varying (LTV) system identificationSub-Nyquist sampling of pulse streams can be used to identify LTV systems using low time-bandwidth productLow rate sampling means the signal can be represented using fewer degrees of freedomThe Xampling framework imp
46、lies that many analog signals have fewer DOF than previously assumed by Nyquist-rate sampling84 美国RICE大学的研究者们将微列阵与单一光学传感器结合起来创造了一种图像/摄像式照相机，这一相机具有图像压缩功能。这所大学的电子工程学教授Baraniuk说：“白噪声是关键，得益于那些数学理论，我们能够在随机分散的测量中得到有效且连贯的图像。单像素相机单像素相机85结构及成像原理结构及成像原理 86 这种单像素照相机使用了一款来自德州仪器的数字微反射镜（DMD digital micro mirror d
47、evice）及单一光电二极管。有趣的部件是数字微反射镜，这款芯片主要用在数字背投或是投影机中。DMD芯片由大量只有细菌大小的镜片组成，每块微型镜片都一面反光，一面不反光，并可以快速8787翻转。一种伪随机模式可映射到上面。这种微反射镜可倾斜 12 ，在芯片的表面有黑白两部分区域，白色部分表示反射镜可倾斜+12 .黑色部分表示反射镜可倾斜-12 .这一系列黑白区域中的反射光集中在光电二极管上。每一种伪随机模式都会发出一组系数（光电压），应用这些系数和随机种子88，可重新建立图像。Baraniuk说：“压缩传感的好处在于我们对样本的图片及影像的测量次数要多于对实际像素的测量。这能大大减少为获得图像
48、/录影编码所要进行的计算。” 在整套系统中，被拍摄物体的图像经过镜头打在DMD上，而经过DMD反射的图像又经过二次镜头聚焦在只有一89个像素的传感器上，形成一个光信号。而在拍摄过程中，DMD上每个镜片反射的明暗矩阵以伪随机码的形式快速变换，每变化一次形成一个像素的型号。最后，经过将每次的信号和伪随机码综合进行计算，就得到了物体的影像.90实现设备实现设备91 由于每次拍照只需要得到多个单像素信号，而在接收端和伪随机码综合计算得到影像。因此解压成像之前的信号量非常小，做到了很有效的数据压缩，十分有利于远距离无线传输（如：航天摄影）。另外，只需要单像素传感器的特点，使得在科学领域中，一些原本需要大
49、面积传感器，或92是传统方法无法拍摄的非可见光领域，这种拍摄方法都有其很大的应用价值。研发人员还称，DMD可以每秒数百万次的速度翻转，因此想把这种拍摄方法转为民用，甚至做成和现在一样的掌上相机也不是没有可能。尽管现在这套系统只对静止物体进行拍摄，拍一张照片需要5分钟，整套设备要占93据一张大桌子。针对数字摄影不能应用在很多科学领域，需对照相机进行改进，例如：有可能应用在消费者市场的Terahertz图像技术。94 拍摄效果拍摄效果95 拍摄效果拍摄效果96 具有单像素探测器的太赫兹相机可以提高测量速度，在太赫兹频段快速成像，能够在机场中的隐蔽武器探测以及航天飞机隔热层泡沫材料中的定位缺陷探测等
50、方面发挥重要作用。基于单像素相机概念的太赫兹成像的新方法，有望改进太赫兹相机的性能，使其克服现有成像系统的缺点，97同时提供较高的速度和较强的探测能力。 这种成像方法的另一个优点是硬件的简单性和多功能性。通过采用一个连续波太赫兹光源，如一台太赫兹量子级联激光器，这种相机可以使用灵敏的单像素探测器（如高莱盒探测器）取代探测器阵列，因此降低了对98光源功率的要求。如果采用脉冲光源，这种相机还可以将其成像能力扩展到捕获光谱相位其他超光谱特征。 这种相机的下一代产品将采用电驱动或光驱动的太赫兹空间调制器来取代随机模式的挡板。这将使其能在不需要任何机械移动部件的情况下，非常快速地对太赫兹光束进行调制。预
