自然背景下的抠图技术研究
|
摘要
抠图与合成是计算机图形学和视觉特效处理中的两个基本操作。传统的合成操作起源于电影工业,其模型简洁直观,现有的合成方法一直沿用传统的合成模型。传统的抠图技术尽管在业内已有广泛的运用,但是仍有诸多缺陷。抠图问题从其形式化表达上看,有七个未知数却只有三个方程,因而是一个病态问题。已有的抠图方案都是加入一些约束条件来求解抠图问题。依据图像的背景不同,抠图技术可以分为单色背景抠图和自然背景抠图。
本文从通用性、易用性、准确性三个方面分析已有的抠图算法,并指出了其各自的不足,同时,结合计算机视觉中的已有模型提出了自己的抠图算法。首先,利用图论中的图(Graph)与图像拓扑结构的相似之处,结合求解图的最小割集算法,实现了一种基于图的抠图算法;其次,分析了基于图的抠图算法的不足,结合可信度传播算法在求解能量最小化问题中的运用,实现了一种基于马尔可夫随机场(MRF)模型的逐步迭代抠图算法;最后,通过分析摄像机的成像原理,找到模糊图像的模糊程度与摄像机参数之间的对应关系。利用不同摄像机参数拍摄相同场景的散焦图像作为求解抠图方程的约束条件,计算图像中被摄主体的深度以及图像聚焦程度,实现图像的绝对前景、绝对背景的分割,并结合已有的Bayesian抠图算法实现自然背景图像的自动抠图处理。
本文的抠图方案都是自然背景抠图方法,全部采用了人机交互方式实现抠图处理。前两种方法,运用计算机视觉中已有的模型到抠图处理中,其交互量与已有的主流抠图算法相当,并且能取得不错的抠图结果;最后一种方法,是本文原创的自然背景自动抠图技术,交互量几乎为零,抠图结果与当前最优的算法相当。
Matting and compositing are the two fundamental operations in computer graphics and visual effects. Traditional compositing operation derived from film industry is a compact and intuitionistic model and it has been used in modern compositing methods until now. Traditional matting operation is widely used in the related field, but it still has some limitations. Matting is an under-constraint problem in theory, because it has seven unknown parameters but only three functions. The existing matting methods were associated by some extra constraints to solve the matting problem. Matting methods can be divided into two kinds by the background of the image disposed by matting algorithm, one is called single color background matting and the other is natural matting.
In this dissertation, we analyze all the methods from universality, convenience and veracity and point out some of their limitations. Then, this dissertation brings out three new methods enlightened by some models in computer vision. Firstly, based on that the structure between image and graph are similar, a graph based matting algorithm is realized using the max-flow methods to get the min-cut set. Secondly, an iterative optimize method is realized based on Markov Random Field model to improve the graph-based method. In order to solve the MRF model, we construct an energy function and use the belief propagation algorithm to get the minimal energy. Finally, we get the relationship between the defocus degree in a defocus image and the parameter of the camera by studying the image theory of the camera. We design an automatic matting method using two defocus images which we shot the same sense with different camera parameters as the extra restriction. In the method, we calculate the depth of the field and the defocus degree of the image, and then get the absolute foreground and absolute background of the image. And we get the alpha channel image using the Bayesian matting method to refine the unknown area which is the edge area of the foreground.
The matting methods in this dissertation pay their attention to the natural matting and adopt the mainstream human and machine interface which has the least labor intensity. The first two methods use the existing model to the matting problem, and they get proper good results as the same labor intensity as the mainstream methods. The last methods is an original automatic natural matting methods, which has the similar matting result with the best matting methods but has an labor intensity equals to zero.
本文从通用性、易用性、准确性三个方面分析已有的抠图算法,并指出了其各自的不足,同时,结合计算机视觉中的已有模型提出了自己的抠图算法。首先,利用图论中的图(Graph)与图像拓扑结构的相似之处,结合求解图的最小割集算法,实现了一种基于图的抠图算法;其次,分析了基于图的抠图算法的不足,结合可信度传播算法在求解能量最小化问题中的运用,实现了一种基于马尔可夫随机场(MRF)模型的逐步迭代抠图算法;最后,通过分析摄像机的成像原理,找到模糊图像的模糊程度与摄像机参数之间的对应关系。利用不同摄像机参数拍摄相同场景的散焦图像作为求解抠图方程的约束条件,计算图像中被摄主体的深度以及图像聚焦程度,实现图像的绝对前景、绝对背景的分割,并结合已有的Bayesian抠图算法实现自然背景图像的自动抠图处理。
本文的抠图方案都是自然背景抠图方法,全部采用了人机交互方式实现抠图处理。前两种方法,运用计算机视觉中已有的模型到抠图处理中,其交互量与已有的主流抠图算法相当,并且能取得不错的抠图结果;最后一种方法,是本文原创的自然背景自动抠图技术,交互量几乎为零,抠图结果与当前最优的算法相当。
Matting and compositing are the two fundamental operations in computer graphics and visual effects. Traditional compositing operation derived from film industry is a compact and intuitionistic model and it has been used in modern compositing methods until now. Traditional matting operation is widely used in the related field, but it still has some limitations. Matting is an under-constraint problem in theory, because it has seven unknown parameters but only three functions. The existing matting methods were associated by some extra constraints to solve the matting problem. Matting methods can be divided into two kinds by the background of the image disposed by matting algorithm, one is called single color background matting and the other is natural matting.
In this dissertation, we analyze all the methods from universality, convenience and veracity and point out some of their limitations. Then, this dissertation brings out three new methods enlightened by some models in computer vision. Firstly, based on that the structure between image and graph are similar, a graph based matting algorithm is realized using the max-flow methods to get the min-cut set. Secondly, an iterative optimize method is realized based on Markov Random Field model to improve the graph-based method. In order to solve the MRF model, we construct an energy function and use the belief propagation algorithm to get the minimal energy. Finally, we get the relationship between the defocus degree in a defocus image and the parameter of the camera by studying the image theory of the camera. We design an automatic matting method using two defocus images which we shot the same sense with different camera parameters as the extra restriction. In the method, we calculate the depth of the field and the defocus degree of the image, and then get the absolute foreground and absolute background of the image. And we get the alpha channel image using the Bayesian matting method to refine the unknown area which is the edge area of the foreground.
The matting methods in this dissertation pay their attention to the natural matting and adopt the mainstream human and machine interface which has the least labor intensity. The first two methods use the existing model to the matting problem, and they get proper good results as the same labor intensity as the mainstream methods. The last methods is an original automatic natural matting methods, which has the similar matting result with the best matting methods but has an labor intensity equals to zero.
引文
1 R. Brinkman. The Art and Science of Digital Compositing. Morgan Kaufman, 1999:23~40.
2 R. Rickitt. Special Effects: the History and Technique. Virgin Books, 2000:97~110.
3 D. Biedny, B. Monroy, N Moody. Photoshop Channel Chops. New Riders Publishing, 1998.
4 R. J. Qian, M. I. Sezan. Video Background Replacement without a Blue Screen. ICIP, 1999, 4(4):143~146.
5 B. A. Wallace. Merging and Transformation of Raster Images for Cartoon Animation. Proceedings of ACM SIGGRAPH, 1981:253~262.
6 A. R. Smith. Alpha and the History of Digital Compositing. Technical Report Microsoft Technical Memo 7, 1995.
7 T. Porter, T. Duff. Compositing Digital Images. Proceedings of ACM SIGGRAPH, 1984:253~259.
8 A. R. Smith. Image Compositing Fundamentals. Technical Report Microsoft Technical, 1995.
9 J. F. Blinn. Compositing. IEEE Computer Graphics & Applications, 1994, 14(5):83~87.
10 S. Wright. Digital Compositing for Film and Video. Focal Press, 2001
11 P. Vlahos. Composite Color Photography. U. S. Patent 3158477, November 24, 1964. Expired.
12 P. Vlahos. Electronic Composite Photography. U. S. Patent 3595987, July 27, 1971. Expired.
13 P. Vlahos. Electronic Composite Photography with Color Control. U. S. Patent 4007487, February 8, 1977. Expired.
14 P. Vlahos. Comprehensive Electronic Compositing System. U. S. Patent 4, 100 569, July 11, 1978. Expired.
15 P. Vlahos. Comprehensive Electronic Compositing System. U. S. Patent 4344085, August 10, 1982.
16 P. Vlahos. Encoded Signal Color Image Compositing. U. S. Patent 4409611,October 11, 1983.
17 P. Vlahos, D. F. Fellinger. Automated Encoded Signal Color Image Compositing. U. S. Patent 4589013, May 13, 1986.
18 P. Vlahos. Comprehensive Electronic Compositing System. U. S. Patent 4625231, November 25, 1986.
19 A. Smith, J. Blinn. Blue Screen Matting. In SIGGRAPH, 1996: 259~268.
20 Y. Mishima. A Software Chromakeyer Using Polyhydric Slice. Proceedings of NICOGRAPH, 1992:44~52.
21 F. V. D. Bergh, V. Lalioti. Software Chroma Keying in an Immersive Virtual Environment, South African Computer Journal, Durban, South Africa, 1999:42~45.
22 A. Berman, A. Dadourian, P. Vlahos. Method for Removing From an Image the Background Surrounding a Selected Object. U.S. Patent 6134346, October 17, 2000.
23 A. Berman, P. Vlahos, A. Dadourian. Comprehensive Method for Removing From an Image the Background Surrounding a Selected Object. U.S. Patent 6134345, October 17, 2000.
24 M. A. Ruzon, C. Tomasi. Alpha Estimation in Natural Images. In CVPR, 2000:18~25.
25 Y. Y. Chuang, B. Curless, D. Salesin, R. Szeliski. A Bayesian Approach to Digital Matting. In CVPR, 2001:264~271.
26 J. Sun, J. Y. Jia, C.K. Tang, H. Y. Shum. Poisson Matting. Proceeding of ACM SIGGRAPH, 2004, 23(3): 315~321.
27 T. Mitsunaga, T. Yokoyama, T. Totsuka. AutoKey: Human Assisted Key Extraction. In SIGGRAPH, August. 1995: 265~272.
28 ADOBE SYSTEMS INCORP. Adobe Photoshop User Guide, 2002.
29 Y. Boykov, M. P. Jolly. Interactive Graph Cuts for Optimal Boundary and Region Segmentation of Objects in N-D Images. Proceeding of IEEE International Conference on Computer Vision, 2001.
30 Y. Boykov, O. Veksler, R. Zabih. Fast Approximates Energy Minimization via Graph Cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(11):1222~1239.
31 D. E. Zongker, D. M. Werner, B. Curless, D. H. Salesin. Environment Mattingand Compositing. Proceedings of ACM SIGGRAPH, 1999:205~214.
32 Y. Y. Chuang, D. E. Zongker, J. Hindorff, B. Curless, D. H. Salesin, R. Szeliski. Environment Matting Extensions: Towards Higher Accuracy and Real-Time Capture. Proceedings of ACM SIGGRAPH, 2000: 121~130.
33 Y. Y. Chuang, D. B. Goldman, B. Curless, D. H. Salesin, R. Szeliski. Shadow Matting and Compositing. ACM Transactions on Graphics, 2003, 22(3):494~500.
34 Y. Y Chuang, A. Agarwala, B. Curless, D. H. Salesin, R. Szeliski. Video Matting of Complex Scenes. ACM Transactions on Graphics, 2002, 21(3):243.248, Special issue: Proceedings of ACM SIGGRAPH 2002.
35 Y. Boykov, V. Kolmogorov. An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision. IEEE Transaction on Pattern Analysis and Machine Intelligence. 2004, 126(9):1124~1137.
36 P. F Felzenszwalb, D. P. Huttenlocher. Efficient Belief Propagation for Early Vision. In CVPR. 2004, 70(1):261~268
37 A. P. Pentland. A New Sense for Depth of Field. IEEE Transactions on PAMI, 1987, 9(4):523~531.
38 M. Sabbaora. Parallel Depth Recovery by Changing Camera Parameters. Proceeding of second international conference on Computer Vision, December 1988:149~155.
39 M. Sabbaora, T. C. Wei, G. Surya. Focused Image Recovery from Two Defocused Images Recorded with Different Camera Settings. IEEE Transactions. Image Processing, December 1995:1613~1627.
40 M. Sabbaora, T. C. Wei. Fast Determination of Distance and Autofocusing from Image Defocus: A New Fourier Domain Approach, Preprint: http://www.ee.sunysb.edu:8080/murali/psfiles/tweil.ps.Z 1995.
41 A. N. Rajagopalan, S. Chaudhuri. Recovery of Depth from Defocused Images Using Space-Frequency Representation. Proceedings of Indian Conference on Pattern recognition, image processing and computer vision, ICPIC, IIT Kharagpur, 1995:95~100.
42 Y. L. Xiong. Depth from Focusing and Defocusing. Proceeding of International Conference on Computer Vision and Pattern Recognition, 1993:68~73.
43 B. K. P. Horn. Focusing. MIT Artificial Intelligence Laboratory MEMO No.160, May. 1968.
44 J. M. Tenenbaum. Accommodation in Computer Vision, Ph.D. Thesis, Stanford University, 1970:55~70
45 J. F. Schlag, A.C. Sanderson, C. P. Neumann, F.C. Wimberly. Implementation of Automatic Focusing Algorithms for a Computer Vision System with Camera Control, Carnegie Mellon University, CMU-RI-TR-83-14, 1983:78~85.
46 R. C. Gonzalez.数字图像处理.阮秋琦,阮宇智.第二版.电子工业出版社,2005:460~494.
47 R. A. Jarvis. Focus Optimization Criteria For Computer Image Processing, MICROSCOPE, 1976, 24(2):163~180.
48 S. K. Nayar, Y. Nakagawa. Shape from Focus. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1994, 16(8):824~831.
49 M. Subbarao, T. S. Choi. Accurate Recovery of Three Dimensional Shapes from Image Focus, IEEE Transactions on Pattern Analysis and Machine Intelligence, 1995, 17(3):2824~2836.
50 M. B. Ahmad, T. S. Choi. A Heuristic Approach For Finding Best Focused Shape, IEEE Transactions on Circuit System for Video Technologies, 2005, 15(4): 566~ 574
51 M. B. Ahmad, T. S. Choi. Fast and Accurate 3D Shape from Focus Using Dynamic Programming Optimization Technique, Proceeding of ICASSP, IEEE International Conference on 2005, (2):969~972
52 M. Subbarao. Spatial-Domain Convolution / Deconvolution Transform, Tech. Report, Computer Vision Laboratory, Depth of Electrical Engineering, SUNY, Stony Brook, NY 117942350, 1991: 773~776.
53 G. Surya, M. Subbarao. Depth from Defocus by Changing Camera Aperture: a Special Domain Approach. Computer Vision and Pattern Recognition, 1992: 61~67.
54章毓晋.图像分割.科学出版社,2001:21~33.
55 M. T. Orchard, C. A. Bouman. Color Quantization of Images. IEEE Transactions on Signal Processing, 1991, 39(12):2677~2690.
2 R. Rickitt. Special Effects: the History and Technique. Virgin Books, 2000:97~110.
3 D. Biedny, B. Monroy, N Moody. Photoshop Channel Chops. New Riders Publishing, 1998.
4 R. J. Qian, M. I. Sezan. Video Background Replacement without a Blue Screen. ICIP, 1999, 4(4):143~146.
5 B. A. Wallace. Merging and Transformation of Raster Images for Cartoon Animation. Proceedings of ACM SIGGRAPH, 1981:253~262.
6 A. R. Smith. Alpha and the History of Digital Compositing. Technical Report Microsoft Technical Memo 7, 1995.
7 T. Porter, T. Duff. Compositing Digital Images. Proceedings of ACM SIGGRAPH, 1984:253~259.
8 A. R. Smith. Image Compositing Fundamentals. Technical Report Microsoft Technical, 1995.
9 J. F. Blinn. Compositing. IEEE Computer Graphics & Applications, 1994, 14(5):83~87.
10 S. Wright. Digital Compositing for Film and Video. Focal Press, 2001
11 P. Vlahos. Composite Color Photography. U. S. Patent 3158477, November 24, 1964. Expired.
12 P. Vlahos. Electronic Composite Photography. U. S. Patent 3595987, July 27, 1971. Expired.
13 P. Vlahos. Electronic Composite Photography with Color Control. U. S. Patent 4007487, February 8, 1977. Expired.
14 P. Vlahos. Comprehensive Electronic Compositing System. U. S. Patent 4, 100 569, July 11, 1978. Expired.
15 P. Vlahos. Comprehensive Electronic Compositing System. U. S. Patent 4344085, August 10, 1982.
16 P. Vlahos. Encoded Signal Color Image Compositing. U. S. Patent 4409611,October 11, 1983.
17 P. Vlahos, D. F. Fellinger. Automated Encoded Signal Color Image Compositing. U. S. Patent 4589013, May 13, 1986.
18 P. Vlahos. Comprehensive Electronic Compositing System. U. S. Patent 4625231, November 25, 1986.
19 A. Smith, J. Blinn. Blue Screen Matting. In SIGGRAPH, 1996: 259~268.
20 Y. Mishima. A Software Chromakeyer Using Polyhydric Slice. Proceedings of NICOGRAPH, 1992:44~52.
21 F. V. D. Bergh, V. Lalioti. Software Chroma Keying in an Immersive Virtual Environment, South African Computer Journal, Durban, South Africa, 1999:42~45.
22 A. Berman, A. Dadourian, P. Vlahos. Method for Removing From an Image the Background Surrounding a Selected Object. U.S. Patent 6134346, October 17, 2000.
23 A. Berman, P. Vlahos, A. Dadourian. Comprehensive Method for Removing From an Image the Background Surrounding a Selected Object. U.S. Patent 6134345, October 17, 2000.
24 M. A. Ruzon, C. Tomasi. Alpha Estimation in Natural Images. In CVPR, 2000:18~25.
25 Y. Y. Chuang, B. Curless, D. Salesin, R. Szeliski. A Bayesian Approach to Digital Matting. In CVPR, 2001:264~271.
26 J. Sun, J. Y. Jia, C.K. Tang, H. Y. Shum. Poisson Matting. Proceeding of ACM SIGGRAPH, 2004, 23(3): 315~321.
27 T. Mitsunaga, T. Yokoyama, T. Totsuka. AutoKey: Human Assisted Key Extraction. In SIGGRAPH, August. 1995: 265~272.
28 ADOBE SYSTEMS INCORP. Adobe Photoshop User Guide, 2002.
29 Y. Boykov, M. P. Jolly. Interactive Graph Cuts for Optimal Boundary and Region Segmentation of Objects in N-D Images. Proceeding of IEEE International Conference on Computer Vision, 2001.
30 Y. Boykov, O. Veksler, R. Zabih. Fast Approximates Energy Minimization via Graph Cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(11):1222~1239.
31 D. E. Zongker, D. M. Werner, B. Curless, D. H. Salesin. Environment Mattingand Compositing. Proceedings of ACM SIGGRAPH, 1999:205~214.
32 Y. Y. Chuang, D. E. Zongker, J. Hindorff, B. Curless, D. H. Salesin, R. Szeliski. Environment Matting Extensions: Towards Higher Accuracy and Real-Time Capture. Proceedings of ACM SIGGRAPH, 2000: 121~130.
33 Y. Y. Chuang, D. B. Goldman, B. Curless, D. H. Salesin, R. Szeliski. Shadow Matting and Compositing. ACM Transactions on Graphics, 2003, 22(3):494~500.
34 Y. Y Chuang, A. Agarwala, B. Curless, D. H. Salesin, R. Szeliski. Video Matting of Complex Scenes. ACM Transactions on Graphics, 2002, 21(3):243.248, Special issue: Proceedings of ACM SIGGRAPH 2002.
35 Y. Boykov, V. Kolmogorov. An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision. IEEE Transaction on Pattern Analysis and Machine Intelligence. 2004, 126(9):1124~1137.
36 P. F Felzenszwalb, D. P. Huttenlocher. Efficient Belief Propagation for Early Vision. In CVPR. 2004, 70(1):261~268
37 A. P. Pentland. A New Sense for Depth of Field. IEEE Transactions on PAMI, 1987, 9(4):523~531.
38 M. Sabbaora. Parallel Depth Recovery by Changing Camera Parameters. Proceeding of second international conference on Computer Vision, December 1988:149~155.
39 M. Sabbaora, T. C. Wei, G. Surya. Focused Image Recovery from Two Defocused Images Recorded with Different Camera Settings. IEEE Transactions. Image Processing, December 1995:1613~1627.
40 M. Sabbaora, T. C. Wei. Fast Determination of Distance and Autofocusing from Image Defocus: A New Fourier Domain Approach, Preprint: http://www.ee.sunysb.edu:8080/murali/psfiles/tweil.ps.Z 1995.
41 A. N. Rajagopalan, S. Chaudhuri. Recovery of Depth from Defocused Images Using Space-Frequency Representation. Proceedings of Indian Conference on Pattern recognition, image processing and computer vision, ICPIC, IIT Kharagpur, 1995:95~100.
42 Y. L. Xiong. Depth from Focusing and Defocusing. Proceeding of International Conference on Computer Vision and Pattern Recognition, 1993:68~73.
43 B. K. P. Horn. Focusing. MIT Artificial Intelligence Laboratory MEMO No.160, May. 1968.
44 J. M. Tenenbaum. Accommodation in Computer Vision, Ph.D. Thesis, Stanford University, 1970:55~70
45 J. F. Schlag, A.C. Sanderson, C. P. Neumann, F.C. Wimberly. Implementation of Automatic Focusing Algorithms for a Computer Vision System with Camera Control, Carnegie Mellon University, CMU-RI-TR-83-14, 1983:78~85.
46 R. C. Gonzalez.数字图像处理.阮秋琦,阮宇智.第二版.电子工业出版社,2005:460~494.
47 R. A. Jarvis. Focus Optimization Criteria For Computer Image Processing, MICROSCOPE, 1976, 24(2):163~180.
48 S. K. Nayar, Y. Nakagawa. Shape from Focus. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1994, 16(8):824~831.
49 M. Subbarao, T. S. Choi. Accurate Recovery of Three Dimensional Shapes from Image Focus, IEEE Transactions on Pattern Analysis and Machine Intelligence, 1995, 17(3):2824~2836.
50 M. B. Ahmad, T. S. Choi. A Heuristic Approach For Finding Best Focused Shape, IEEE Transactions on Circuit System for Video Technologies, 2005, 15(4): 566~ 574
51 M. B. Ahmad, T. S. Choi. Fast and Accurate 3D Shape from Focus Using Dynamic Programming Optimization Technique, Proceeding of ICASSP, IEEE International Conference on 2005, (2):969~972
52 M. Subbarao. Spatial-Domain Convolution / Deconvolution Transform, Tech. Report, Computer Vision Laboratory, Depth of Electrical Engineering, SUNY, Stony Brook, NY 117942350, 1991: 773~776.
53 G. Surya, M. Subbarao. Depth from Defocus by Changing Camera Aperture: a Special Domain Approach. Computer Vision and Pattern Recognition, 1992: 61~67.
54章毓晋.图像分割.科学出版社,2001:21~33.
55 M. T. Orchard, C. A. Bouman. Color Quantization of Images. IEEE Transactions on Signal Processing, 1991, 39(12):2677~2690.