自然影像擷取是從一張影像中擷取出前景。擷取前景時，需要利用附屬之三元圖將影像分成前景區、背景區及未知區三個部分。未知區裡的每個未知像素都需要計算透明度。本研究利用影像中顏色的梯度資訊，使用局部梯度門檻值法來縮減三元圖的未知區，以減少計算透明度的時間，還可以提高透明度的品質。此外，針對計算未知像素的透明度時，所需要的前景樣本與背景樣本，我們提出一些不影響品質的加速方法。對於以正方形擴大的搜尋方法，我們有兩個方法來加速。另一個全新的反向放射線法，可以避免重複搜尋樣本，是較快的方法。完成樣本搜尋後，針對每一對前景樣本與背景樣本的組合，使用未知像素與樣本的顏色距離及空間距離計算該組合的成本，以挑選最佳的透明度，在大部分未知像素屬於前景或背景的情況下，可以獲得良好的透明度。

Natural image matting is to extract a foreground object from an image. It often requires the user to provide a trimap, which partitions the original image into definitely foreground, definitely background, and unknown regions. For any pixel in the unknown region, the foreground opacity must be computed. Our research uses gradient of color image and the new local gradient threshold to reduce the unknown region. It can reduce time for computing opacity values and improve their quality. For any pixel in the unknown region, its possible foreground values and background values are required to compute its opacity. We propose three methods to speed up the time for obtaining the foreground values and background values. Form every pair of foreground and background values, an opacity value and cost are computed. The cost gives an evaluation of the quality of the corresponding opacity value. Our method produces quality alpha matte when the foreground object is opaque.

[1] X. Bai and G. Sapiro, "Geodesic matting: A framework for fast interactive image and video segmentation and matting," International Journal of Computer Vision, vol. 82, no. 2, pp. 113-132, 2009
[2] Y. Y. Boykov and M.-P. Jolly, "Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images," Proc. IEEE International Conference on Computer Vision, Vancouver, BC, pp. 105-112, July 2001.
[3] Q. Chen, D. Li, and C.-K. Tang, "KNN matting," Proc. IEEE Conference on Computer Vision and Pattern Recognition, Providence, RI, pp. 869-876, June 2012.
[4] X. Chen, D. Zou, Q. Zhao, and P. Tan, "Manifold preserving edit propagation," ACM Transactions on Graphics, vol. 31, no. 6, Nov. 2012.
[5] Y.-Y. Chuang, B. Curless, D. H. Salesin, and R. Szeliski, "A Bayesian approach to digital matting," Proc. IEEE Conference on Computer Vision and Pattern Recognition, Kauai, HI, pp. 264-271, Dec. 2001.
[6] E. S. L. Gastal and M. M. Oliveira, "Shared sampling for real-time alpha matting," Computer Graphics Forum, vol. 29, no. 2, pp. 575-584, May 2010.
[7] M. Gleicher, "Image snapping," Proc. 22nd Annual Conference on Computer Graphics and Interactive Techniques, Los Angeles, CA, pp. 183-190, Aug. 1995.
[8] R. C. Gonzalez and R. E. Woods, Digital Image Processing, 3rd ed., Prentice Hall. Upper Saddle River, NJ, 2008.
[9] L. Grady, T. Schiwietz, S. Aharon, and R. Westermann, "Random walks for interactive alpha-matting," Proc. 5th IASTED International Conference on Visualization, Imaging, and Image Processing, pp. 423-429, Sep. 2005.
[10] Y. Guan, W. Chen, X. Liang, Z. Ding, and Q. Peng, "Easy matting: A stroke based approach for continuous image matting," Computer Graphics Forum, vol. 25, no. 3, pp. 567-576, Sep. 2006.
[11] B. He, G. Wang, Z. Ruan, X. Yin, X. Pei, and X. Lin, "Local matting based on sample-pair propagation and iterative refinement," Proc. IEEE International Conference on Image Processing, Orlando, FL, pp. 285-288, Sep. 2012.
[12] K. He, J. Sun, and X. Tang, "Fast matting using large kernel matting Laplacian matrices," Proc. IEEE Conference on Computer Vision and Pattern Recognition, San Francisco, CA, pp. 2165-2172, June 2010.
[13] K. He, C. Rhemann, C. Rother, X. Tang, and J. Sun, "A global sampling method for alpha matting," Proc. IEEE Conference on Computer Vision and Pattern Recognition, Colorado Springs, CO, pp. 2049-2056, June 2011.
[14] H. Huang, L. Zhang, and H.-C. Zhang, "RepSnapping: Efficient image cutout for repeated scene elements," Computer Graphics Forum, vol. 30, no. 7, pp. 2059-2066, Sep. 2011.
[15] M. Huang, W. Yu, and D. Zhu, "An improved image segmentation algorithm based on the Otsu method," Proc. 13th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel & Distributed Computing, Kyoto, Japan, pp. 135-139, Aug. 2012.
[16] S.-J. Ko and Y. H. Lee, "Center weighted median filters and their applications to image enhancement," IEEE Transactions on Circuits and Systems, vol. 38, no. 9, pp. 984-993, Sep. 1991.
[17] A. Levin, A. R. Acha, and D. Lischinski, "Spectral matting," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30, no. 10, pp. 1699-1712, Oct. 2007.
[18] A. Levin, D. Lischinski, and Y. Weiss, "A closed-form solution to natural image matting," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30, no. 2, pp. 228-242, Feb. 2008.
[19] Y. Li, J. Sun, C.-K. Tang, and H.-Y. Shum, "Lazy snapping," ACM Transactions on Graphics, vol. 23, no. 3, pp. 303-308, Aug. 2004.
[20] Y.-C. Lin, H.-A. Wang, and Y.-F. Hsieh, "Image matting through a Web browser," Multimedia Tools and Applications, vol. 61, pp. 551-570, Dec. 2012.
[21] Y.-C. Lin and C.-H. Yeh, "Improved online tool for image matting," International Journal of Networked Computing and Advanced Information Management, vol. 3, no. 1, pp. 16-24, Apr. 2013.
[22] E. N. Mortensen and W. A. Barrett, "Intelligent scissors for image composition," Proc. 22nd Annual Conference on Computer Graphics and Interactive Techniques, Los Angeles, CA, pp. 191-198, Aug. 1995.
[23] N. G. Nayi, "Image matting for natural image," International Journal of Engineering Research and Applications, vol. 2, no. 3, pp. 2182-2185, May 2012.
[24] N. Ostu, "A threshold selection method from gray-level histograms," IEEE Transactions on Systems, MAN and Cybernetics, vol. 9, no. 1, pp. 62-66, Jan. 1979.
[25] T. Porter and T. Duff, "Compositing digital images," ACM SIGGRAPH Computer Graphics, vol. 18, no. 3, pp. 253-259, 1984
[26] C. Rhemann, C. Rother, and M. Gelautz, "Improving color modeling for alpha matting," Proc. British Machine Vision Conference, pp. 115.1-115.10, Sep. 2008.
[27] C. Rhemann, C. Rother, A. Rav-Acha, and T. Sharp, "High resolution matting via interactive trimap segmentation," Proc. IEEE Conference on Computer Vision and Pattern Recognition, Anchorage, AK, pp. 1-8, June 2008.
[28] C. Rhemann, C. Rother, J. Wang, M. Gelautz, P. Kohli, and P. Rott, "A perceptually motivated online benchmark for image matting," Proc. IEEE Conference on Computer Vision and Pattern Recognition, Miami, FL, pp. 1826-183, June 2009.
[29] C. Rother, V. Kolmogorov, and A. Blake, "GrabCut: interactive foreground extraction using iterated graph cuts," ACM Transactions on Graphics, vol. 23, no. 3, pp. 309-314, Aug. 2004.
[30] M. A. Ruzon and C. Tomasi, "Alpha estimation in natural images," Proc. IEEE Conference on Computer Vision and Pattern Recognition, Hilton Head, SC, pp. 18-25, June 2000.
[31] E. Shahrian and D. Rajan, "Weighted color and texture sample selection for image matting," Proc. IEEE Conference on Computer Vision and Pattern Recognition, Providence, RI, pp. 718-725, June 2012.
[32] E. Shahrian, D. Rajan, B. Price, and S. Cohen, "Improving image matting using comprehensive sampling sets," Proc. IEEE Conference on Computer Vision and Pattern Recognition, Portland, OR, pp. 636-642, June 2013.
[33] D. Singaraju, C. Rother, and C. Rhemann, "New appearance models for natural image matting," Proc. IEEE Conference on Computer Vision and Pattern Recognition, Miami, FL, pp. 659-666, June 2009.
[34] A. R. Smith and J. F. Blinn, "Blue screen matting," Proc. 23rd Annual Conference on Computer Graphics and Interactive Techniques, New Orleans, LA, pp. 259-268, Aug. 1996.
[35] J. Sun, J. Jia, C.-K. Tang, and H.-Y. Shum, "Poisson matting," ACM Transactions on Graphics, vol. 23, no. 3, pp. 315-321, Aug. 2004.
[36] J. Sun, Y. Li, S. B. Kang, and H.-Y. Shum, "Flash matting," ACM Transactions on Graphics vol. 25, no. 3, pp. 772-778, 2006.
[37] J. Sun, S. B. Kang, and Z.-B. Xu, "Flash cut: Foreground extraction with flash and no-flash image pairs," Proc. IEEE Conference on Computer Vision and Pattern Recognition, Minneapolis, MN, pp. 1-8, June 2007.
[38] J. Wang and M. F. Cohen, "An iterative optimization approach for unified image segmentation and matting," Proc. IEEE International Conference on Computer Vision, Beijing, pp. 936-943, Oct. 2005.
[39] J. Wang, M. Agrawala, and M. F. Cohen, "Soft scissors: An interactive tool for realtime high quality matting," ACM Transactions on Graphics, vol. 26, no. 3, July 2007.
[40] J. Wang and M. F. Cohen, "Image and video matting: A survey," Foundations and Trends in Computer Graphics and Vision, vol. 3, no. 2, pp. 97-175, Jan. 2007.
[41] J. Wang and M. F. Cohen, "Optimized color sampling for robust matting," Proc. IEEE Conference on Computer Vision and Pattern Recognition, Minneapolis, MN, pp. 1-8, June 2007.
[42] X.-g. Wang and S.-h. Chen, "An improved image segmentation algorithm based on two dimensional Otsu method," Information Science Letters, vol. 1, no. 2, pp. 77-83, Sep. 2012.
[43] C. J. Willmott and K. Matsuura, "Advantages of the mean absolute error (MAE) over the root mean square error (RMSE) in assessing average model performance," Climate Research, vol. 30, no. 1, pp. 79-82, Dec. 2005.
[44] Q. Yang, X. Tang, C. Wang, and Z. Ye, "Progressive cut: An image cutout algorithm that models user intentions," IEEE Multimedia, vol. 14, no. 3, pp. 56-66, July-Sep. 2007.
[45] Y. Zheng, C. Kambhamettu, J. Yu, T. Bauer, and K. Steiner, "Fuzzymatte: A computationally efficient scheme for interactive matting," Proc. IEEE Conference on Computer Vision and Pattern Recognition, Anchorage, AK, pp. 1-8, June 2008.
[46] Y. Zheng and C. Kambhamettu, "Learning based digital matting," Proc. IEEE International Conference on Computer Vision, Kyoto, Japan, pp. 285-288, Sep. 2009.