三維電腦視覺已經被廣範的運用在各個領域，然而對於一般的使用者而言，使用現存的三維物體創建工具來創造仍然是一件繁雜的工作，通常需要使用者從大量的資料庫中選取想要的模組，透過旋轉、放大縮小、移動以及對應點的指定等來取得理想的物件。而對於三維物體搜尋的困難之處在於每個物件都有各式各樣的角度以及比例縮放。因此本篇論文開發了一個階層式的分類系統，來幫助使用者從大量的資料庫中快速且正確的找出想要的三維物件。在本系統的訓練程序中，資料庫中存放基本的三維模組，在各個角度上投影到二維上面取得物件外框，然後利用這些外框來訓練區域鑑別式的分類假構以加速搜尋的效率。另外，為了降低資料的存放量，我們使用了流形模組來計算更精確的物件角度。而在測式程序中，我們在階層式架構中利用找尋最近k個鄰居的方式來判段所屬的類別，並評估相似度來進行排序以決定階層式架構的搜尋路徑。基於本系統，使用者無需手動的選擇物體的種類及角度，也無需手動指定對應點。最後實驗也測試各種不同物體種類、角度以及比例來驗證本系統的效率。

Existing tools for reconstructing 3D models from user freehand sketch is a tedious work, as it requires manually choosing a targeted 3D model in a database and carefully matching 3D model to the desired 2D sketch. The major difficulty for automation of 3D reconstruction is that 3D model has various 2D contours caused by changing viewpoints. In this paper, we proposed a novel cascaded framework of 3D models reorganization and categorization for automatically choosing and matching tasks. In the training process, each 3D model in the database is decomposed as several 2D projected contours from different viewpoints. All contours are then organized in a cascade way combined with Locality Sensitive Discriminant Analysis (LSDA) to boost search efficiency. Also, manifold spaces are constructed to generate virtual 2D contours and consequently only a limited size of 2D contours is required in the database. In the testing process, the input free-form sketch is used for querying 2D projected contours from 3D database. The search stage is cascaded and parallel; at each layer, k-nearest neighbors of input sketch are selected and ranked by their similarity degree. The informative neighbors (only the top few of sorted list) are then used for indicating search direction in the next layer. Consequently, no user effort for choosing and matching 3D model is necessary where the object type and viewpoint are highly robust and efficiently estimated. Extensive experiments demonstrate that the proposed method is efficient and well-performed by testing for 8 object types, each has 1440 varied poses and 5 different contour ratios.

[1] C. Alvarado, M.P. Cani, “Sketch-based search and Composition of 3D Models,” EUROGRAPHICS Workshop on Sketch-Based Interfaces and Modeling, Jun. 2008
[2] D. Cai, X. He, K. Zhou, J. Han, and H. Bao, “Locality Sensitive Discriminant Analysis,” In Proceedings of IJCAI, pp. 708-713, 2007.
[3] Y. Chen, S. Dana, and M. van de Panne, “Sketch-based modeling of parameterized objects,” ACM SIGGRAPH 2005 Sketches, Aug. 2005.
[4] S. Dickinson, A. Pentland, and S. Stevenson, “Viewpoint-invariant indexing for content-based image retrieval,” Content-Based Access of Image and Video Database, pp. 20-30, Jan. 1998.
[5] A. Ecker, K.N. Kutulakos, and A.D. Jepson, “Shape from Planar Curves: A Linear Escape from Flatland,” Computer Vision and Pattern Recognition, pp. 1-8, Jun. 2007.
[6] T. Funkhouser and P. Shilane, “Partial Matching of 3D Shapes with Priority-Driven Search,” ACM International Conference Proceeding Series, vol. 256, pp. 131-142, 2006.
[7] S. Heung-Yeung, M. Hebert, and K. Ikeuchi, “On 3D shape similarity,” Computer Vision and Pattern Recognition, pp 526-531, Jun. 1996.
[8] T. Horikoshi and H. Kasahara, “3-D shape indexing language,” Computers and Communications, pp. 493-499, Mar. 1990.
[9] S. Hou, P. Jiantao, and K. Ramani, “Sketch-based 3D Engineering Part Class Browsing and Retrieval,” EuroGraphics Symposium Proceedings on Sketch-Based Interfaces & Modeling, pp. 131-138, Jul. 2006.
[10] J. Hulin and E. Thiel, “Chordal Axis on Weighted Distance Transforms,” Lecture Notes in Computer Science, Vol. 4245, pp. 271-282, Oct. 2006.
[11] D.P. Huttenlocher and S. Ullman, “Recognizing Solid Objects by Alignment with an Image,” International Journal of Computer Vision, No. 2, pp. 195-212, Nov. 1990.
[12] S. HyoJong and T. Igarashi, "Magic canvas: interactive design of a 3-D scene prototype from freehand sketches," Proceedings of Graphics Interface, pp. 63-70, 2007.
[13] T. Igarashi, S. Matsuoka, and H. Tanaka, “Teddy: Sketching Interface for 3D Freeform Design,” In Proceedings of SIGGRAPH, pp. 409-416, Aug. 1999.
[14] L. Jeehyung and F. Thomas, “Sketch based search and composition of 3D models,” EUROGRAPHICS Workshop on Sketch-Based Interfaces and Modeling, Jun. 2008.
[15] C. Jin-Long and G.C. Stockman, “Indexing to 3D Model Aspects using 2D Contour Features,” Computer Vision and Pattern Recognition, pp. 913-920, Jun. 1996.
[16] O. Karpenko, J. Hughes, and R. Raskar, “Inferring 3D free-form shapes from contour drawings,” Proceedings of ACM SIGGRAPH, vol. 25, Issue 3, pp. 589-598, Jul. 2006.
[17] O.A. Karpenko and J.F. Hughes, “SmoothSketch: 3D free-form shapes from complex sketches,” ACM Trans. Graph, vol. 25, No. 3, pp. 589-598, Jul. 2006.
[18] D.C. Ku, S.F. Qin, and D.K. Wright, “A sketching interface for 3d modeling of polyhedrons,” Proceedings of Eurographics Workshop on Sketch Based Interfaces and Modeling (SBIM06), pp. 83-90, Sep. 2006.
[19] E. Lynn, H. Ching-Yao, B. Beat D, and E. Gershon, “Inferring 3D models from freehand sketches and constraints,” Computer-Aided Design In Solid Modelling, vol. 29, No. 2, pp. 101-112, Feb. 1997.
[20] L. Lakshman and R. Ramana, “Multi-scale discretization of shape contours,” Vision geometry IX, pp. 30-31, Jul. 2000.
[21] Y. Lamdan, J.T. Schwartz, and H.J. Wolfson, “Affine invariant model-based object recognition,” IEEE Transactions on In Robotics and Automation, vol. 6, No. 5, pp. 578-589, 1990.
[22] D.T. Lee and B.J. Schacter, “Two Algorithms for Constructing a Delaunay Triangulation,” International Journal of Computer and Information Sciences, Plenum Press, vol. 3, 1980.
[23] S. Owada, F. Nielsen, M. Okabz, and T. Igarashi, “Volumetric illustration designing 3D models with internal textures,” ACM Transactions on Graphics, Proceedings of ACM SIGGRAPH, pp. 322-328, Aug. 2004.
[24] L. Prasad, “Morphological Analysis of Shapes,” CNLS Newsletter, No. 139, 1997.
[25] M. Safar, C. Shahabi, and X. Sun, “Image Retrieval by shape: a comparative study,” Multimedia and Expo, vol. 1, pp. 141-144, 2000.
[26] M. Tanase and R.C. Veltkamp, “Part-Based Shape Retrieval with Relevance Feedback,” Multimedia and Expo, pp. 936- 939, Jul. 2005.
[27] F. Thomas, M. Patrick, K. Michael, C. Joyce, H.A. Halderman, and D. David, “A Search Engine for 3D Models,” ACM Transactions on Graphics, pp. 83–105, Jan. 2003.
[28] J. Warren and H. Weimer, “Subdivision Methods for Geometric Design: A Constructive Approach,” Morgan Kaufmann Publishers Inc, 2001.
[29] R.C. Zeleznik, K. Herndon, and J.F. Hughes, “SKETCH: An interface for sketching 3D scenes,” In Proceedings of SIGGRAPH, pp. 409-416, Aug. 1999.
[30] L. Zhenguo, L, Jianzhuang, and T. Xiaoou, “A Closed-form Solution to 3D Reconstruction of Piecewise Planar Objects from Single Image,” Computer Vision and Pattern Recognition, pp. 1-6, Jun. 2007.