向量圖(vector images)是一個很熱門的圖像顯示方式，該表示法也常被用作多媒體的素材。向量圖(vector images)比起一般常見的點陣圖(raster images)而言， 更能無失真地進行縮放與更容易做某一些特定的編輯動作， 因此有許多的應用也建立在此顯示方式上。儘管已有大量的研究關注於如何將點陣圖(raster images)向量化， 但是，這些方法在將全彩點陣圖(raster images)影像向量化時， 會面臨細節無法完整保留， 或者是需要耗費大量的人力去完成等問題。因此，本研究主要著重在本實驗室所設計的一套新向量圖(vector images)顯示格式之上， 我們將原本點陣圖(raster images)上所截取出的形狀與影像特徵做為向量圖(vector images)形的結構， 以這些資料支援影像的放大， 影像完整形狀的編輯， 影像顏色的編輯與局部圖像的替換， 也可只對部分的影像做變型的編輯。雖然，此系統的強項在於能保留原圖的大量細節， 但是，也因此需要大量的特徵點計算，包含了大矩陣的運算與大量數值的內插計算， 如此造成了計算的強大負擔， 及立即快速編輯的困難。為了要能達到立即編輯(WYSWYG)目的， 加速整個向量計算是必要的。我們除了利用GPU的多核平行結構用以加速基本的矩陣及內插運算外， 我們更著重於將所有特徵點分群計算， 用以減少GPU與CPU之間資料的傳遞， 強化GPU的運算核心(Kernel)的一致性及統一性， 減少等待時間， 以利於在GPU上平行運算處理， 同時再修正群落之間的誤差來達到不失真的即時形狀編輯。經過加速後， 在控制影像的失真率下， 演算速度可以讓編輯達到即時的狀態。

Vector graphics is popular to describe various multimedia contents in versatile applications because of its compactness and scalability and past proposed representations generally require intensive labor to create and fall short in editability. Thin Plate Spline (TPS) can preform constrained interpolation mechanics for preserving complex details of arbitrary images. Therefore, this work vectorize a raster image by encoding global object geometry and image details in a hybrid vector structure as explicit geometric patches and implicit detail features. A user provides an input color patch definition to guide patch decomposition and our system compute image details as gradient and color constraints computed as Canny-based curvilinear features and adaptive color samples. It is time consuming for TPS interpolation to construct a non-linear interpolation kernel based on these constrained features. We develop a patch-based structure to approximate the TPS interpolation by localizing color samples and salient features for real-time parallel computation of the kernel and inversion with minimal error. The realtime TPS interpolation allows to create an interactive system for complicated detail editing operations including image magnification, shape editing, material replacement, image warping based on the proposed vector-based representation. Experiments indicate that our proposed system can produce high-quality results comparable to existing state-of-the-art vector-based representations with better editability and real-time performance.

[1] S.-H. Zhang, T. Chen, Y.-F. Zhang, S.-M. Hu, and R. R. Martin, “Vectorizing cartoon animations,” IEEE Transactions on Visualization and Computer Graphics, vol. 15, no. 4, pp. 618–629, 2009.
[2] G. Noris, A. Hornung, R. W. Sumner, M. Simmons, and M. Gross, “Topologydriven vectorization of clean line drawings,” ACM Trans. Graph., vol. 32,pp. 4:1–4:11, Feb. 2013.
[3] L. Xu, Q. Yan, Y. Xia, and J. Jia, “Structure extraction from texture via relative total variation,” ACM Trans. Graph., vol. 31, pp. 139:1–139:10, Nov.2012.
[4] J. Kopf and D. Lischinski, “Digital reconstruction of halftoned color comics,” ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia 2012),vol. 31, p. to appear, Nov. 2012.
[5] Z. Liao, H. Hoppe, D. Forsyth, and Y. Yu, “A subdivision-based representation for vector image editing,” IEEE Transactions on Visualization and Computer Graphics, vol. 18, no. 11, pp. 1858–1867, 2012.
[6] M. Finch, J. Snyder, and H. Hoppe, “Freeform vector graphics with controlled thin-plate splines,” ACM Trans. Graph., vol. 30, no. 6, pp. 166:1–166:10, 2011.
[7] Y.-K. Lai, S.-M. Hu, and R. R. Martin, “Automatic and topology-preserving gradient mesh generation for image vectorization,” ACM Trans. Graph., vol. 28, no. 3, pp. 85:1–85:8, 2009.
[8] T. Xia, B. Liao, and Y. Yu, “Patch-based image vectorization with automatic curvilinear feature alignment,” ACM Trans. Graph., vol. 28, no. 5, pp. 115:1–115:10, 2009.
[9] L. Demaret, N. Dyn, and A. Iske, “Image compression by linear splines over adaptive triangulations,” in Signal Processing, pp. 1604–1616, 2006.
[10] G. Lecot and B. Levy, “Ardeco: Automatic region detection and conversion,” in Eurographics Symposium on Rendering, 2006.
[11] S. Swaminarayan and L. Prasad, “Rapid automated polygonal image decomposition,” in Applied Imagery and Pattern Recognition Workshop, 2006. AIPR 2006. 35th IEEE, p. 28, oct. 2006.
[12] A. Orzan, A. Bousseau, H. Winnemぴoller, P. Barla, J. Thollot, and D. Salesin, “Diffusion curves: a vector representation for smooth-shaded images,” ACM Trans. Graph., vol. 27, no. 3, pp. 92:1–92:8, 2008.
[13] S. Jeschke, D. Cline, and P. Wonka, “Estimating color and texture parameters for vector graphics,” Computer Graphics Forum, vol. 30, pp. 523–532, Apr. 2011. This paper won the 2nd best paper award at Eurographics 2011.
[14] J. Sun, L. Liang, F. Wen, and H.-Y. Shum, “Image vectorization using optimized gradient meshes,” ACM Trans. Graph., vol. 26, no. 3, 2007.
[15] Y. Li, J. Sun, C.-K. Tang, and H.-Y. Shum, “Lazy snapping,” ACM Trans. Graph., vol. 23, no. 3, pp. 303–308, 2004.
[16] C. Rother, V. Kolmogorov, and A. Blake, “”grabcut”: interactive foreground extraction using iterated graph cuts,” ACM Trans. Graph., vol. 23, no. 3, pp. 309–314, 2004.
[17] A. Delong, A. Osokin, H. N. Isack, and Y. Boykov, “Fast approximate energy minimization with label costs,” Int. J. Comput. Vision, vol. 96, no. 1, pp. 1–27, 2012.
[18] J. Powell, A Thin Plate Spline Method for Mapping Curves Into Curves in Two Dimensions. Cambridge DAMTP, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, 1995.
[19] B. Price and W. Barrett, “Object-based vectorization for interactive image editing,” Vis. Comput., vol. 22, no. 9, pp. 661–670, 2006.
[20] R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua, and S. Susstrunk, “Slic superpixels compared to state-of-the-art superpixel methods,” Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 34, no. 11, pp. 2274–2282, 2012.
[21] Wikipedia, “Lab color space.”
[22] NVIDIA, “cublas.”
[23] C.-Y. Yao, M.-T. Chi, T.-Y. Lee, and T. Ju, “Region-based line field design using harmonic functions,” IEEE Transactions on Visualization and Computer Graphics, vol. 18, pp. 902–913, 2012.
[24] Y.-S. Wang, C.-L. Tai, O. Sorkine, and T.-Y. Lee, “Optimized scale-and-stretch for image resizing,” ACM Trans. Graph., vol. 27, no. 5, pp. 118:1–118:8, 2008.
[25] F. Bookstein, “Principal warps: Thin-plate splines and the decomposition of deformations,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 11, pp. 567–585, 1989.
[26] R. Maharik, M. Bessmeltsev, A. Sheffer, A. Shamir, and N. Carr, “Digital micrography,” ACM Trans. Graph., vol. 30, no. 4, pp. 100:1–100:12, 2011.
[27] C. Yuksel, J. Keyser, and D. H. House, “Mesh colors,” ACM Transactions on Graphics, vol. 29, no. 2, pp. 15:1–15:11, 2010.
[28] P. F. Felzenszwalb and D. P. Huttenlocher, “Efficient graph-based image segmentation,” 2004.
[29] J. Schreiner, A. Asirvatham, E. Praun, and H. Hoppe, “Inter-surface mapping,” in ACM SIGGRAPH 2004 Papers, SIGGRAPH ’04, (New York, NY, USA), pp. 870–877, ACM, 2004.
[30] V. Kraevoy and A. Sheffer, “Cross-parameterization and compatible remeshing of 3d models,” in ACM SIGGRAPH 2004 Papers, SIGGRAPH ’04, (New York, NY, USA), pp. 861–869, ACM, 2004.
[31] B. Dalstein, R. Ronfard, and M. van de Panne, “Vector graphics animation with time-varying topology,” ACM Trans. Graph., vol. 34, July 2015.