隨著個人電腦與智慧行動裝置的普及，使即時影像處理與應用有廣泛地發展。現今的裝置可以讓輸入影像達到Full HD(192×1080)或甚至更高的解析度。而高解析度的影像包含了更高的資訊量，並可擷取出更多精確的特徵來做各類的應用，但其運算量往往會與輸入影像的解析度成正相關。因此，如何減少運算量並保有高準確率與快速執行的特性成為重要的課題。一個超像素(superpixel)可以代表數個相鄰且具相同特徵的像素。利用超像素的演算，有降低影像解析度、減少運算量的效果，並可保有原始影像的結構。因此，超像素演算法可作為各種影像相關應用的前處理，以降低整體的運算量與執行時間。
在本論文中，我們提出一個快速而有效的超像素演算法，首先透過尋找垂直與水平方向的邊緣路徑可取得粗略的網格狀超像素，接著透過第二次尋找邊緣路徑、分出相對精細的影像結構，可以達到更高的精確度。我們用動態規劃法(Dynamic programing) 來找出邊緣最佳路徑，其可有效地降低整體運算時間。此演算法在Intel i7-4770中央處理器平臺上用單執行緒執行下，運算時間只需大約7毫秒。在對比多個超像素演算方法後，可以發現我們提出的演算法比目前多數或常用的方法來的精確且快速。而極短的執行時間使我們提出的超像素演算法可以做為其他影像相關應用的前處理。最後我們分析了精確度提升的原因，並歸納出未來能繼續深入研究的方向，使演算方法達到更高的效率。

In recent years, thanks to the great growth of the PC and smart mobile device development, real-time image processing applications are also widely discussed and proposed. With the advanced camera, the resolution of the image may achieve Full HD (1920×1080 pixels) or even higher easily. Consequently, the image can contain more information, which means that we can retrieve more precise features from the image, but the computational load is proportional to the image resolution most of the time. Superpixel algorithm integrates the adjacent pixels which have similar color to superpixels. It resembles that superpixel algorithm reduces the resolution of image but still maintains the image structures. Therefore, superpixel algorithms also are widely discussed and many superpixel methods are proposed.
In this thesis, we propose a fast superpixel method which has high accuracy. The vertical and horizontal First-Seams produces roughly grid-shape image structures. Then, the vertical and horizontal Second-Seams can figure out the relatively delicate structures. The Dynamic programing is used to find the optimal seam. Hence, the proposed method can achieve a high accuracy, and it only need about 7 milliseconds to complete the computing when it is processed on an Intel i7-4770 CPU platform with a single thread. By the comparison with other methods, it shows that the proposed method is faster and more accurate than most of other methods. Finally, we analyze the factors which boost the accuracy and sum up the ways which may improve the superpixel method and should be the interesting topics for future work.

REFERENCES
[1] 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, 2012.
[2] A. Moore, S. Prince, J. Warrell, U. Mohammed and G. Jones, "Superpixel Lattices," in IEEE Computer Vision and Pattern Recognition (CVPR), 2008.
[3] F. Drucker and J. MacCormick, "Fast superpixels for video analysis," in Workshop on Motion and Video Computing, 2009.
[4] P. Siva and A. Wong, "Grid seams: A fast superpixel algorithm for real-time applications," in Proceedings - Conference on Computer and Robot Vision, 2014.
[5] D. Xiang, T. Tang, L. Zhao and Y. Su, "Superpixel Generating Algorithm Based on Pixel," in IEEE GEOSCIENCE AND REMOTE SENSING LETTERS, 2013.
[6] C.-L. Zitnick and S.-B. Kang, "Stereo for image-based rendering using image over-segmentation," in International Journal of Computer Vision (IJCV), 2007.
[7] 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, 2012.
[8] Y. Li, J. Sun, C.-K. Tang and H.-Y. Shum, "Lazy snapping," in ACM Transactions on Graphics (SIGGRAPH), 2004.
[9] Z. Liu, X. Zhang, S. Luo and O. Le Meur, "Superpixel-Based Spatiotemporal Saliency Detection," in IEEE Transactions on Circuits and Systems for Video Technology, 2014.
[10] C.-Y. Hsu and J.-J. Ding, "Saliency detection using DCT coefficients and superpixel-based segmentation," in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013.
[11] B. Fulkerson, A. Vedaldi and S. Soatto, "Class segmentation and object localization with superpixel neighborhoods," in International Conference on Computer Vision (ICCV), 2009.
[12] J. Steiner, S. Zollmann and . G. Reitmayr, "Incremental superpixels for real-time video analysis," in Proceedings of the Computer Vision Winter Workshop, 2011.
[13] 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 (ICCV), 2001.
[14] J. Shi and J. Malik, "Normalized cuts and image segmentation," in IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 2000.
[15] P. Felzenszwalb and D. Huttenlocher, "Efficient graph-based image segmentation," in International Journal of Computer Vision (IJCV), 2004.
[16] O. Veksler, Y. Boykov and P. Mehrani, "Superpixels and supervoxels in an energy optimization framework," in European Conference on Computer Vision (ECCV), 2010.
[17] A. Levinshtein, A. Stere, K. Kutulakos, D. Fleet and K. Siddiqi, "Turbopixels: Fast superpixels using geometric flows.," in IEEE, 2009.
[18] A. Vedaldi and S. Soatto, "Quick shift and kernel methods for mode seeking," in In European Conference on Computer Vision (ECCV), 2008.
[19] in Specification ICC.1:2004-10 (Profile version 4.2.0.0) Image technology colour management — Architecture, profile format, and data structure, International Color Consortium, 2006.
[20] S. Avidan and A. Shamir, "Seam carving for content-aware image resizing," in ACM Transactions on Graphics, 2007.
[21] ITU-R Recommendation BT.601, International Telecommunication Union – Radiocommunication sector, 1982.
[22] I. Sobel and G. Feldman, "A 3x3 Isotropic Gradient Operator for Image Processing," Stanford Artificial Intelligence Project (SAIL), 1968.
[23] "IMAGE AND VISUAL REPRESENTATION LAB IVRL," EPFL, 2013. [Online]. Available: http://ivrl.epfl.ch/research/superpixels. [Accessed 7 2015].
[24] A. L. Shimpi and D. Wilson, in NVIDIA's GeForce 8800 (G80): GPUs Re-architected for DirectX 10, AnandTech, 2006.