近年來，超像素算法具有各種應用，並已被廣泛研究。它通常用在許多應用中，例如圖像分割和障礙物檢測可以利用超像素來降低圖像的解析度，同時維持影像的結構。這表示，超像素可以加速影像處理的速度。有些應用甚至需要即時產生超像素的執行能力。目前已經有許多研究努力維持超像素的高精準度，並同時減少超像素產生的演算法計算時間和複雜度。在本文中，我們提出了一個藉由動態規劃最佳路徑的方法來改善現有的超像素或生產新的超像素，改進現有或產生超像素有兩個主要步驟。第一步是分析每個超像素的顏色變異數來選擇一個超像素目標。第二步是藉由動態規劃來找到超像素的分割路徑，我們將一個超像素用十字相交的分割線來分割成四塊。實驗結果顯示，本方法可以明顯的提高現有超像素的準確性。並藉由與其他超像素演算法相比，當本方法從一個單一標籤的圖片分割時能達到與SLIC超像素相似的精準度。最後，我們分析了本方法的時間複雜度為O(n log n)，n是超像素的數量。

In recent years, superpixel algorithms have various applications and have been widely studied. It is commonly used on many applications such as image segmentation and obstacles detections since superpixels can reduce the resolution of images and maintain image structure at the same time. This means that superpixels can accelerate the processing speed of images. Moreover, some of applications even requires real-time execution performance in superpixel generation. Many researches have tried to preserve the accuracy as high as possible while reducing the computation time and complexity in the superpixel generation. In this thesis, we propose a seam-carving based refinement method to refine and produce superpixels. The proposed method can refine existing superpixels with two major steps. First is to choose a superpixel candidate by analyzing color variances of each superpixel. Second is to split a superpixel by a cross seam which is obtained by dynamic programming. The experimental results show that the proposed method can obviously improve existing superpixel label map’s accuracy. By comparing to other superpixel algorithms, the proposed method can reach similar accuracy as the known best SLIC superpixel when refining an image from only a single label. The complexity of the proposed system is O(n log n) where n is the number of superpixel.

REFERENCES
[1]Z. Li, X. M. Wu, and S. F. Chang, "Segmentation using superpixels: A bipartite graph partitioning approach," in IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 789-796, 2012.
[2]J. Shen, Y. Du, W. Wang, and X. Li, "Lazy Random Walks for Superpixel Segmentation," in IEEE Transactions on Image Processing, vol. 23, pp. 1451-1462, 2014.
[3]Y. Li, J. Sun, C.-K. Tang, and H.-Y. Shum, "Lazy snapping," in ACM Special Interest Group on Graphics and Interactive Techniques, pp. 303-308, 2004.
[4]J. J. Ding, C. J. Lin, I. F. Lu, and Y. H. Cheng, "Real-time interactive image segmentation using improved superpixels," in IEEE International Conference on Digital Signal Processing, pp. 740-744, 2015.
[5]S. Javed, S. H. Oh, A. Sobral, T. Bouwmans, and S. K. Jung, "Background Subtraction via Superpixel-Based Online Matrix Decomposition with Structured Foreground Constraints," in IEEE International Conference on Computer Vision Workshop (ICCVW), pp. 930-938, 2015.
[6]C. L. Zitnick and S. B. Kang, "Stereo for Image-Based Rendering using Image Over-Segmentation," in International Journal of Computer Vision, vol. 75, pp. 49-65, 2007.
[7]J. Seo, C. Oh, and K. Sohn, "Segment-based free space estimation using plane normal vector in disparity space," in International Conference on Connected Vehicles and Expo (ICCVE), pp. 144-149, 2015.
[8]S. Iizuka, Y. Endo, Y. Kanamori, J. Mitani, and Y. Fukui, "Efficient Depth Propagation for Constructing a Layered Depth Image from a Single Image," in Computer Graphics Forum, vol. 33, pp. 279-288, 2014.
[9]A. Saxena, M. Sun, and A. Y. Ng, "Learning 3-D Scene Structure from a Single Still Image," in 2007 IEEE 11th International Conference on Computer Vision, pp. 1-8, 2007.
[10]D. Xiang, T. Tang, L. Zhao, and Y. Su, "Superpixel Generating Algorithm Based on Pixel Intensity and Location Similarity for SAR Image Classification," in IEEE Geoscience and Remote Sensing Letters, vol. 10, pp. 1414-1418, 2013.
[11]I. Giosan and S. Nedevschi, "Superpixel-based obstacle segmentation from dense stereo urban traffic scenarios using intensity, depth and optical flow information," in IEEE Conference on Intelligent Transportation Systems (ITSC), pp. 1662-1668, 2014.
[12]P. Siva and A. Wong, "Grid Seams: A Fast Superpixel Algorithm for Real-Time Applications," in Canadian Conference on Computer and Robot Vision, pp. 127-134, 2014.
[13]J.-L. Lin, "A Real-Time Superpixel Algorithm based on Two-Layered Grid Seams," Master, Department of Electronic and Computer Engineering, National Taiwan University of Science and Technology, 2015.
[14]R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua, and S. Süsstrunk, "SLIC Superpixels Compared to State-of-the-Art Superpixel Methods," in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 34, pp. 2274-2282, 2012.
[15]P. Morerio, G. C. Georgiu, L. Marcenaro, and C. Regazzoni, "Optimizing Superpixel Clustering for Real-Time Egocentric-Vision Applications," in IEEE Signal Processing Letters, vol. 22, pp. 469-473, 2015.
[16]A. P. Moore, S. J. D. Prince, J. Warrell, U. Mohammed, and G. Jones, "Superpixel lattices," in IEEE Conference on Computer Vision and Pattern Recognition, pp. 1-8, 2008.
[17]S. Jianbo and J. Malik, "Normalized cuts and image segmentation," in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, pp. 888-905, 2000.
[18]P. F. Felzenszwalb and D. P. Huttenlocher, "Efficient Graph-Based Image Segmentation," in International Journal of Computer Vision, vol. 59, pp. 167-181, 2004.
[19]M. Y. Liu, O. Tuzel, S. Ramalingam, and R. Chellappa, "Entropy rate superpixel segmentation," in IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2097-2104, 2011.
[20]D. Comaniciu and P. Meer, "Mean shift: a robust approach toward feature space analysis," in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24, pp. 603-619, 2002.
[21]A. Levinshtein, A. Stere, K. N. Kutulakos, D. J. Fleet, S. J. Dickinson, and K. Siddiqi, "TurboPixels: Fast Superpixels Using Geometric Flows," in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 31, pp. 2290-2297, 2009.
[22]A. Vedaldi and S. Soatto, "Quick Shift and Kernel Methods for Mode Seeking," in 10th European Conference on Computer Vision, pp. 705-718, 2008.
[23]L. Vincent and P. Soille, "Watersheds in digital spaces: an efficient algorithm based on immersion simulations," in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, pp. 583-598, 1991.
[24]S. Avidan and A. Shamir, "Seam carving for content-aware image resizing," in ACM Special Interest Group on Graphics and Interactive Techniques, p. 10, 2007.
[25]ITU-R Recommendation BT.709, International Telecommunication Union - Radiocommunication sector, 1990.
[26]ITU-R Recommendation BT.601, International Telecommunication Union - Radiocommunication sector, 1982.
[27]R. C. Gonzalez and R. E. Woods, Digital Image Processing (3rd Edition), 3 ed.: Pearson, 2007.
[28]D. Martin, C. Fowlkes, D. Tal, and J. Malik, "A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics," in IEEE International Conference on Computer Vision, vol. 2, pp. 416-423, 2001.
[29]Prince Vision Lab. (Access on: July,14, 2016). Superpixel Lattices sample code. Available: http://web4.cs.ucl.ac.uk/research/vis/pvl/index.php?option=com_content&view=article&id=76:superpixel-lattices-code&catid=49:downloads&Itemid=62
[30] Image and Visual Representation Lab (IVRL). (Access on: July,14, 2016). SLIC Superpixels source code. Available: http://ivrl.epfl.ch/research/superpixels