6 : DCT 675 CS / [7 9]. Xie Sarkis [7 8],,,,, ;,,,. Zhang [9] DCT CS, H. 264 DC,. (Two-dimensional, 2-D) DCT 1-D DCT [6], Zhang 1-D, DCT 1-D DCT, ;, Z

Size: px

Start display at page:

Download "6 : DCT 675 CS / [7 9]. Xie Sarkis [7 8],,,,, ;,,,. Zhang [9] DCT CS, H. 264 DC,. (Two-dimensional, 2-D) DCT 1-D DCT [6], Zhang 1-D, DCT 1-D DCT, ;, Z"

儡解
7 years ago
Views:

1 37 6 Vol. 37, No ACTA AUTOMATICA SINICA June, 2011 DCT (Compressed sensing, CS), (Discrete cosine transform, DCT)., DCT CS. DCT DCT, CS,.,, CS, (Inverse DCT, IDCT), (Peak signal to noise ratio, PSNR) 5 db,, PSNR. DOI,,,, /SP.J Image Coding and Reconstruction via Compressed Sensing Based on Partial DCT Coefficients PAN Rong 1 LIU Yu 1 HOU Zheng-Xin 1 WANG Shao-Chu 1 Abstract This paper introduced the CS (compressed sensing) theory and proposed a new method to encode and reconstruct images after acquiring the partial two-dimensional DCT (discrete cosine transform) coefficients. The CS total variation reconstruction algorithms based on partial DCT coefficients with or without quantization were studied in this paper. In the quantization step, partial noisy DCT coefficients were obtained, based on which the general image coding/decoding process able to realize the CS reconstruction was designed, and a practical application system was made up. The experimental results showed that for images with strong sparsity, the image coding/decoding system integrated with CS theory and its methods can be used to obtain reconstructed images with high quality, and that compared with traditional direct inverse DCT (IDCT) method, the improved peak signal to noise ratio (PSNR) can be up to 5 db, and it also has some improvement in the term of PSNR for general images. Key words Image coding, image reconstruction, discrete cosine transform (DCT), compressed sensing (CS), minimum total variation (TV) (Compressed sensing, CS),, 2006 [1 2],,. CS, CS [3 4]. CS,, ( ),, /,. CS, (Discrete fourier transform, DFT) Manuscript received June 28, 2010; accepted February 28, 2011 ( ) Supported by National Natural Science Foundation of China ( ) School of Electronic Information Engineering, Tianjin University, Tianjin , DFT,,,, DFT, [2]. CS, DFT [5]., /, (Discrete cosine transform, DCT), JPEG, MPEG1/2 H. 264 ( DCT ),, JPEG 2000 [6]. CS,,,,,. DFT DCT,,,.

00674 Image Coding and Reconstruction via Compressed Sensing Based on Partial DCT Coefficients PAN Rong 1 LIU Yu 1 HOU Zheng-Xin 1 WANG Shao-Chu 1 Abstract This paper introduced the CS (compressed

2 6 : DCT 675 CS / [7 9]. Xie Sarkis [7 8],,,,, ;,,,. Zhang [9] DCT CS, H. 264 DC,. (Two-dimensional, 2-D) DCT 1-D DCT [6], Zhang 1-D, DCT 1-D DCT, ;, Zhang DCT, M 1-D DCT,. /, CS, ; DCT, 2-D DCT,, 2-D,. 1 CS, 2 2-D DCT, 3, CS, 4, 5. 1 CS x supp (x) = {k x(k) 0} K, x K ( x K ); Ψ, x. Ψ, ( DCT ),,. N x R n M {ϕ i R n } M 1 : y i = x, ϕ i, [ ] T( i = 1,, M; Φ = ϕ 1 ϕ 2 ϕ M ), : y = Φx (1) y = {y i } M 1 CS, M N. (1),, x, (2) l 0, y x: ˆx = arg min x 0 s.t. Φx = y (2) x, Ψ, x = Ψs, s. Θ = ΦΨ, (2) (3): ŝs = arg min s 0 s.t. Θs = y (3) ˆx = Ψŝs x., (3) CS. (2) (3) f 0 f, l 0, NP-hard. Φ Ψ [10] ( Θ = ΦΨ [11] ), l 0 l 1, (3) (4): ŝs = arg min s 1 s.t. Θs = y (4) (1), CS,,,, (4)., (4) (5) : ŝs = arg min s 1 s.t. Θs s y 2 < ε (5) ˆx x : x ˆx 2 < Cε, C., (1) CS, 1-D, 2-D. Zhang (1), 2-D 1-D, [9]. 2 CS M N, Candes DFT (Total variation, TV) CS [2], (6): ˆx = arg min x TV s.t. ˆx(ω) = f(ω), ω Ω (6) (6), Ω 2-D DFT, f(ω) 2-D DFT, ω 2-D, x TV TV, : x TV = t 1,t 2 D xh (t 1, t 2 ) 2 + D xv (t 1, t 2 ) 2 (7) (7), D xh (t 1, t 2 ) = x(t 1, t 2 ) x(t 1 1, t 2 ), D xv (t 1, t 2 ) = x(t 1, t 2 ) x(t 1, t 2 1), t 1, t 2

N x R n M {ϕ i R n } M 1 : y i = x, ϕ i, [ ] T( i = 1,, M; Φ = ϕ 1 ϕ 2 ϕ M ), : y = Φx (1) y = {y i } M 1 CS, M N. (1),, x, (2) l 0, y x: ˆx = arg min x 0 s.t. Φx = y (2) x, Ψ, x = Ψs, s.

3 676 自动化学报的横纵坐标, 0 t1 M 1, 0 t2 N 1. 式 x(ω) 是未知图像 (6) 中的待重构图像 x 是未知的, x 的 DFT 系数; 而 f (ω) 则是已知的 DFT 系数, 在已知系数和未知信号 DFT 系数达到匹配的情况下, 通 x. 过迭代寻找 TV 最小 (也即最稀疏) 的重构信号 x 式 (6) 可转化为求解二阶锥规划问题[12]. 对于具有稀疏离散梯度的图像信号, 最小全变差法重构精确但速度较慢, 现在已有有效的快速算法[5]. 在图像视频编码中, 一般使用 DCT 或基于 DCT 的变换 (如 H. 264 的整数变换) 以提高编码效率. DCT 与反离散余弦变换 (Inverse DCT, IDCT) 是可逆过程. 但对于局部 DCT 系数, 直接进行补零然后反变换得到的恢复值与原始值会有较大差异. 根据 CS 理论, 在一定条件下, 对局部测量值进行 CS 重构, 能以极大的概率恢复原始数据. 因此, 可考虑对局部 DCT 系数进行 CS 重构. 将式 (6) 转化为下式, 在局部 DCT 系数基础上重构图像信号: x = arg min kx xktv s.t. x x(u) = c (u), u U x (8) 式 (8) 中, U 是局部 2-D DCT 频率集, c (u) 是 x(u) 是待重构未知图像的 DCT 2-D DCT 系数值, x 系数. 式 (8) 采用的是局部 2-D DCT 系数, 因为图像具有二维空间相关性, 对于变换基而言, 采用 2-D DCT 变换比 1-D DCT 变换效果更好, 在重构的时候, 根据式 (7), 采用 TV 方法能同时利用图像二维空间上的梯度信息, 从而有效地重构原始图像. 为直观说明式 (8) 在基于局部 DCT 系数重构图像信号方面的有效性, 类似于文献 [2], 本文采用 Logan-shepp phantom 测试图像, 将直接反变换效果和 CS 重构效果做一对比. 根据 DCT 系数的分布特点, 设计放射状采样图进行 DCT 频域采样, 然后根据式 (8) 基于局部 DCT 系数得到重构图像, 如图 1 所示. 图 1 直观地显示了 CS 重构图像比通过 IDCT 得到的图像的主观质量更高. 绝对误差和 SAD = P x x x 可用来客观地表示图像的失真度 (SAD x 值越大, 则失真度越高), 在本实验对比中, CS 重构图像的 SADCS = , IDCT 变换图像 SADIDCT = 这表明在获取局部 DCT 系数的基础上, 也能采用 CS 理论与方法对图像进行有效重构, 显示了 CS 在图像压缩算法领域的潜在应用价值. 3 实际图像 CS 重构系统现有图像/视频的编码标准一般都采用基于块的编码结构, 即将图像/视频序列划分成或更小的块, 然后针对每个块分别进行处理, 一般有如 37 卷 (a) 原始图像 (b) DCT 域放射状采样 (a) Original (b) Radial sampling in DCT image domain (c) IDCT 重构图像 (d) CS 重构图像 (c) Reconstructed image via (d) Reconstructed image via IDCT 图1 Fig. 1 CS 对整幅图像的 IDCT 与 CS 重构质量比较 Comparison of the whole image reconstruction qualities by IDCT and CS 下基本的处理步骤: 提取块与块之间的冗余度变换量化和熵编码. 大部分小系数的归零将由量化完成, 采用不同的量化表是控制图像压缩率的关键. 图像量化过程采用标量量化器: a = round(a/qstep), 反量化过程为: a = a Qstep; 其中 a 是变换系数原始值, Qstep 是量化步长, round( ) 是四舍五入取整函数, a 是量化值, a 是反量化值. 由以上可以看出, 在量化阶段将会产生量化误差, 其本质就是舍入误差, 即在原始值 a 上加入了量化噪声, 从而得到反量化值 a. CS 理论解决的是从局部测量值出发重构未知原始信号的问题. 图像编码虽然处理的是已知信号, 但是在解码端信号则是未知的, 需要在得到局部 DCT 系数的基础上重构信号, 因此可以应用 CS 理论与方法. 现有编码标准主要采用 DCT 变换, 量化过程就是对 DCT 系数进行量化: 尽量保留人眼敏感的低频系数, 尽量舍弃对图像质量影响不大的高频系数, 从而在高频段出现大量的零值. 因此, 量化过程就是选择局部 DCT 系数 (低频段和高频段的少量非零值) 作为测量值的过程, 而已量化 DCT 系数是含噪的. 由 2-D DCT 的变换式 C = AXAT, A 为 DCT 变换核[6], 又可看出每一个 DCT 系数都包含了原图像的全局相关信息 (原图像 X 的每个像素

但对于局部 DCT 系数, 直接进行补零然后反变换得到的恢复值与原始值会有较大差异. 根据 CS 理论, 在一定条件下, 对局部测量值进行 CS 重构, 能以极大的概率恢复原始数据. 因此, 可考虑对局部 DCT 系数进行 CS 重构. 将式 (6) 转化为下式, 在局部 DCT 系数基础上重构图像信号: x = arg min kx xktv

4 6 : DCT 677 DCT )., Candes, Φ (Spike basis) Ψ [13], 1 Φ Ψ., CS 2-D DCT. DCT, (5), (8) (9): ˆx = arg min x TV s.t. ˆx(u) c(u) 2 < ε, u U (9) (9), c(u) DCT, ε. (9) Cε.,,, ( ), 2-D DCT CS IDCT.,,.,, DCT, CS : 1. f, x; 2. 2-D DCT, c(u); 3. c(u), c(u); 4. c(u), c(u); 5. c(u) IDCT (9) CS, ˆx IDCT ˆx CS ; 6. ˆx IDCT, ˆx CS x, SAD IDCT SAD CS ; 7. CS CSflag, SAD CS < SAD IDCT, CSflag, x CS, CSflag, IDCT; 8. 3 c(u) ; 9. CSflag EOB y; , ; 11. g., CS : 1. g, EOB y; 2. y, c(u); 3. c(u), c(u); 4. CSflag, CSflag, 5, CSflag, 6; 5. c(u) IDCT, ˆx, 7; 6. c(u) CS, ˆx, 7; , ; 8. ˆf. IDCT CS,, (, CSflag EOB ). 2-D DCT CS, 2-D CS,, CS, CS ( CSflag ), CS. 4 3, Matlab., 8 8, JPEG,, 1010, EOB, CSflag, IDCT ; 1001, EOB, CSflag, CS JPEG EOB, 1001,, EOB CSflag,. (9) CS,, ε = , : Camera man, Lena, Ballet ( ) Orthophoto ( 2 ), Liftingbody, Rice ( Matlab ) 1 (a) Phantom., 4.1 CS, 4.2 CS IDCT (JPEG), 4.3 CS, 2-D CS. 4.1 CS 2 CS, CS. TV, CS. 2 (d) Orthophoto CS,

3 c(u) ; 9. CSflag EOB y; 10. 2 9, ; 11. g., CS : 1. g, EOB y; 2. y, c(u); 3. c(u), c(u); 4. CSflag, CSflag, 5, CSflag, 6; 5. c(u) IDCT, ˆx, 7; 6. c(u) CS, ˆx, 7; 7. 2 6, ; 8. ˆf.

5 678 37, 2 (a) 2 (c)., (9), TV (TV ),, 2., CS. (a) Camera man (a) IDCT (b) CS (a) Direct IDCT (b) CS reconstruction reconstruction 3 IDCT CS (Camera man) Fig. 3 Comparison of images reconstructed by IDCT and CS (Camera man) Fig. 2 2 (b) Lena (c) Ballet (d) Orthophoto CS Test images and distribution of CS blocks D CS IDCT 2-D DCT IDCT JPEG. 3 2-D IDCT 2-D CS, Camera man., IDCT,, CS, (Peak signal to noise ratio, PSNR). 8 bit, 255, P SNR = 10 log ( 255 2/ MSE ), db, MSE (Mean square error, MSE), MSE = S 1 (I K) 2, S, I K : 1) IDCT P SNR IDCT ; 2) CS P SNR CS ; 3) CS IDCT, P SNR ; 4) CS. CS,,. 1, Ballet Phantom, CS, P SNR 3 db 5 db,, Rice CS Ballet Phantom, Ballet Phantom, P SNR Rice,,,, TV. Orthophoto Lena, CS, P SNR. Camera man, Liftingbody Rice, CS D CS CS 2-D CS CS. CS : 1) 1-DPCS, [9], 1-D DCT, M (

3 2-D IDCT 2-D CS, Camera man., IDCT,, CS, (Peak signal to noise ratio, PSNR). 8 bit, 255, P SNR = 10 log ( 255 2/ MSE ), db, MSE (Mean square error, MSE), MSE = S 1 (I K) 2, S, I K.

6 6 : DCT 679 Table D CS IDCT Comparison of qualities of images reconstructed by 2-D CS and IDCT Camera man Lena Ballet Orthophoto Liftingbody Rice Phantom P SNR IDCT (db) P SNR CS (db) P SNR (db) CS block (%) ), 1-D 2-D zig-zag ; 2) 1-D CS, 1-D DCT, ; 3) 2-D PCS, 2-D DCT, M ( 21 ). 1/2, 3/4 5/4. 2 4, 2-D CS CS ( Camera man ) P SNR (, ). 2, ( ), 2-D CS CS, P SNR,. 2 QP 2-D CS CS (Camera man) Table 2 Comparison of the qualities of images reconstructed by 2-D CS and other CS methods through 1-D PCS 1-D CS 2-D PCS different QPs (Camera man) 1 2 QP 3 4 QP QP 5 4 QP P SNR (db) bits (%) P SNR (db) bits (%) P SNR (db) bits (%) P SNR, 4 (Camera man), 4 1-D PCS, 1-D CS, 2-D CS 2-D PCS (Bits-distortion, B-D). 4, 2-D CS 2-D PCS 1-D CS 1-D PCS, B-D,, CS. 2-D CS 2-D PCS B-D 1-D PCS 1-D CS, 2-D DCT CS 1-D. 2 4,. 4 Fig. 4 (Camera man) Bits-distortion curves (Camera man) B-D, Bjontegaard [14] P SNR ( 3 )., P SNR P SNR, bits P SNR (, ). 2, 2-D CS CS,, 3, P SNR, 2-D CS CS,, P SNR 4 db, 2-D CS B-D. 5 CS,

38 21 ), 1-D 2-D zig-zag ; 2) 1-D CS, 1-D DCT, ; 3) 2-D PCS, 2-D DCT, M ( 21 ). 1/2, 3/4 5/4. 2 4, 2-D CS CS ( Camera man ) P SNR (, ). 2, ( ), 2-D CS CS, P SNR,.

7 D CS CS (Bjontegaard ) Table 3 Comparison of qualities of images reconstructed by 2-D CS and other CS methods (Bjontegaard method) Camera man Lena Ballet Orthophoto Liftingbody Rice Phantom 1-D PCS 1-D CS 2-D PCS P SNR (db) bits (%) P SNR (db) bits (%) P SNR (db) bits (%) , DCT CS., DCT, DCT, DCT CS. 2-D DCT, 1-D DCT, 2-D. DCT, CS,.,,, IDCT, P SNR 5 db,, P SNR ; 1-D DCT DCT CS, P SNR 4 db., P SNR ( ),, CS /. CS ( ), JPEG, MPEG H References 1 Donoho D L. Compressed sensing. IEEE Transactions on Information Theory, 2006, 52(4): Candes E J, Romberg J, Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 2006, 52(2): Li Shu-Tao, Wei Dan. A survey on compressive sensing. Acta Automatica Sinica, 2009, 35(11): (,.., 2009, 35(11): ) 4 Shi Guang-Ming, Liu Dan-Hua, Gao Da-Hua, Liu Zhe, Lin Jie, Wang Liang-Jun. Advances in theory and application of compressed sensing. Acta Electronica Sinica, 2009, 37(5): (,,,,,.,, 2009, 37(5): ) 5 Yang J F, Zhang Y, Yin W T. A fast alternating direction method for TVL1-L2 signal reconstruction from partial Fourier data. IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2): Yao Qing-Dong, Bi Hou-Jie, Wang Zhao-Hua, Xu Meng-Xia. Image Coding Primer (Third Edition). Beijing: Tsinghua University Press, (,,,. ( ). :, ) 7 Xie X C, Yu L J. A new video codec based on compressed sensing. In: Proceedings of the 2nd International Congress on Image and Signal Processing. Tianjin, China: IEEE, Sarkis M, Diepold K. Depth map compression via compressed sensing. In: Proceedings of the 16th IEEE International Conference on Image Processing. Cairo, Egypt: IEEE, Zhang Y F, Mei S L, Chen Q Q, Chen Z B. A novel image/video coding method based on compressed sensing theory. In: Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing. Las Vegas, USA: IEEE, Candes E J, Romberg J. Sparsity and incoherence in compressive sampling. Inverse Problems, 2007, 23(3): Candes E J, Tao T. Decoding by linear programming. IEEE Transactions on Information Theory, 2005, 51(12): Boyd S, Vandenberghe L. Convex Optimization. Cambridge: Cambridge University Press, Candes E J, Wakin M B. An introduction to compressive sampling. IEEE Signal Processing Magazine, 2008, 25(2): Bjontegaard G. Calculation of Average PSNR Differences between RD-curves, Technical Report VCEG-M33, the 13th Meeting of Video Coding Experts Group-SG16, USA, 2001

84 28.48 35.51 21.79 5.82 P SNR (db) 0.15 0.03 2.16 0.03 0.22 0.06 3.11 bits (%) 2.32 0.45 32.24 0.37 5.67 1.61 31.44, DCT CS., DCT, DCT, DCT CS. 2-D DCT, 1-D DCT, 2-D. DCT, CS,.

8 6 : DCT ,. panrong@tju.edu.cn (PAN Rong Ph. D. candidate in signal and information processing at the School of Electronic Information Engineering, Tianjin University. He received his bachelor degree in communication and master degree in signal and information processing from Tianjin University in 2005 and 2007, respectively. His research interest covers multimedia processing, and digital image and video coding.). 1969, 1982.,,. zhengxinhou@163.com (HOU Zheng-Xin Professor at the School of Electronic Information Engineering, Tianjin University. He received his bachelor degree in electrical engineering from Peking University in 1969 and master degree in signal and information processing from Tianjin University in His research interest covers digital filtering theory, signal processing theory, image and video processing, wavelet analysis and its applications.) , HDTV.. liuyu@tju.edu.cn (LIU Yu Associate professor at the School of Electronic Information Engineering, Tianjin University. He received his Ph. D. degree in signal and information processing from Tianjin University in His research interest covers image and video compression, HDTV and multimedia systems. Corresponding author of this paper.) ,,. wangshaochu@tju.edu.cn (WANG Shao-Chu Ph. D. candidate in signal and information processing at the School of Electronic Information Engineering, Tianjin University. He received his master degree in signal and information processing from Tianjin University in His research interest covers multimedia processing, compressed sensing, and digital signal processing hardware and software.)

His research interest covers multimedia processing, and digital image and video coding.). 1969, 1982.,,. E-mail: zhengxinhou@163.

698 39,., [6].,,,, : 1) ; 2) ,, 14,, [7].,,,,, : 1) :,. 2) :,,, 3) :,,,., [8].,. 1.,,,, ,,,. : 1) :,, 2) :,, 200, s, ) :,.

698 39,., [6].,,,, : 1) ; 2) ,, 14,, [7].,,,,, : 1) :,. 2) :,,, 3) :,,,., [8].,. 1.,,,, ,,,. : 1) :,, 2) :,, 200, s, ) :,. 39 6 Vol. 39, No. 6 2013 6 ACTA AUTOMATICA SINICA June, 2013 1, 2,,,. DOI,,,., 2013, 39(6): 697 702 10.3724/SP.J.1004.2013.00697 Present Situation and Development Tendency of Aerospace Control Techniques