本論文之目的在藉由Wings重建多面體的線段圖。所謂的線段圖(Line Drawing Graph)包含了影像中的稜線(edge)和頂點(vertex)；而多面體線段圖,則指影像中所含的物體，其表面都是平面而非曲面。Wings是由實際影像偵測得來的稜線的片段，而且在該片段兩邊的平面方程式都已被計算出來，所以它和一般的稜線不同，除了二維空間的資訊之外,還包含了一些立體的資訊。本研究之目標就是希望由實際影像所偵測到的Wings，將完整的多面體線段圖重建回來。
本研究共分成三部分。在第一部分中，利用完形心理學家所提出的知覺組織(Perceptual Organization)之原則將落在同一稜線上小段的Wings整合成完整的一長段；在第二部分中，假設每個稜線上至少都有偵測到一條Wing，藉由將Wings做延伸，要把完整的線段圖重建起來；在第三部分中則將第二部分的假設去掉，亦即原影像中的某些稜線可能完全沒有被偵測到，而要將完整的線段圖儘可能重新建立起來。
經由本研究證實：雖然由影像偵測到的Wings可能不夠完整，有些稜線可能根本沒有被偵測到，甚至還會抓到一些多餘的Wings，但是藉由充份利用Wings所提供的資訊，特別是關於立體的情況，我們仍然可以將影像的線段圖相當完整的建立起來；換言之，先前李忠謀教授在其博士論文中所指出的建立影像線段圖的方法：先由影像偵測出Wings、再由Wings建立完整的線段圖，對多面體而言，確實是可行的。

This thesis addresses the problem of reconstructing the labeled line drawing graph of a scene containing polygonal surface objects from wing samples extracted from the scene. The line drawing graph of a scene is a representation of all the visible edges and surfaces of objects in the scene. A line drawing graph is said to be labeled if all lines and regions in the graph are interpreted and the 3D locations of all vertices are recovered. The wings, which are derived from a raw fused image, are 2 1/2 D primitives encoding fragments of object boundaries and their adjacent surfaces. Since the sampled wings detected from raw fused images are often short, nearly co-curvilinear, principles of perceptual organization identified by the Gestalt Psychologists are first applied to merge co-edge wings together.
After the preprocessing of input wing samples, two working algorithms for reconstructing the labeled line drawing graphs of polygonal scenes from wings are given to analyze scenes under various restrictive assumptions. With very idealistic assumptions about the wing samples, a reconstruction algorithm which reconstructs the complete labeled line drawing graph via deterministic rules is devised. As the strong assumptions on input wing samples being removed, a heuristic based algorithm is presented to deal with the possibilities that wings may not be sensed and be "missing" after wing detection stage. By extracting the 3D information of the wings, missing line segments are recovered whenever possible. As a result, the nearly complete labeled line drawing graph is reconstructed.
In all, construction of labeled line drawing graphs of polygonal scenes via wing features is proven to be feasible. Although the experimental results of wing detection reveal that the sampled wings are sometimes "imperfect", yet the work in this thesis shows that even when there are missing and/or spurious wings in the set of wing samples, the labeled line drawing graph can still be reconstructed nearly completely.

[1] M. Boldt, R. Weiss, and E. Riseman. Token based extraction of straight lines. IEEE Transactions on Systems, Man, and Cybernetics, 19(6):1581-1594, December 1989.
[2] R. Brooks. Model-based Computer Vision. UMI Research Press, 1984.
[3] I. Chakravarty. A generalized line and junction labeling scheme with applications to scene analysis. IEEE Transactions on Pattern Recognition and Machine Intelligence, 1(2):202-205, April 1979.
[4] S.-W. Chen. 3-D Representation and Recognition Using Object Wings. PhD thesis, Michigan State University, 1989.
[5] S.-W. Chen and G. Stockman. Object wings - 2 1/2 D primitives for 3-D recognition. In IEEE 1989 Conference on Computer Vision and Pattern Recognition, pages 535-540, San Diego, CA, June 1989.
[6] J. Dolan and R. Weiss. Perceptual grouping of curved lines. In DARPA Image Understanding Workshop, pages 1135-1145, Palo Alto, CA, 1989.
[7] T.-J.Fan, G. Medioni, and R. Nevatia. Recognizing 3-D objects using surface descriptions. In 2nd International Conference on Computer Vision, pages 474-481, Tampa, FL, December 1988.
[8] P. J. Flynn. CAD-Based Computer Vision: Modeling and Recognition Strategies. PhD thesis, Michigan State University, 1990.
[9] W. E. L. Grimson and T. Lozano-Perez. Model-based recognition and localization from sparse range or tactile data. International Journal of Robotics Research, 3(3):3-35, 1984.
[10] A. K. Jain and R. Hoffman. Evidence-based recognition of 3-D objects. IEEE Transactions on Pattern Recognition and Machine Intelligence, 10(6):783-8802, November 1988.
[11] G. C. Lee. Reconstruction of Line Drawing Graphs from Fused Range and Intensity Imagery. PhD thesis, Michigan State University, 1992.
[12] D. G. Lowe. Perceptual Organization and Visual Recognition. Kluwer, Boston, MA, 1985.
[13] R. Mohan and R. Nevatia. Perceptual organization for scene segmentation and description. IEEE Transactions on Pattern Recognition and Machine Intelligence, 14(6):616-635, June 1992.
[14] G. Reynolds and J. Beveridge. Searching for geometric structure in images of natural scenes. In DARPA Image Understanding Workshop, Los Angeles, CA, February 1987.
[15] L. G. Roberts. Machine perception of three-dimensional solids. In J. T. Tippett, editor, Optical and Electro-Optical Information Processing, pages 159-197. MIT Press, Cambridge, MA, 1965.
[16] S. Sarkar and K. Boyer. A highly efficient computational structure for perceptual organization. Technical report sampl-90-06, The Ohio State University, November 1990.
[17] G. Stockman. Object recognition and localization via pose clustering. Computer Vision, Graphics, and Image Processing, 40:361-387, 1987.
[18] G. Stockman, G. C. Lee, and S.-W. Chen. Reconstructing line drawings from wing representations: The polyhedral case. In 3rd International Conference on Computer Vision, Osaka, Japan, December 1990.
[19] D. A. Trytten and M. Tuceryan. Segmentation and grouping of object boundaries using energy minimization. In IEEE 1991 conference on Computer Vision and Pattern Recognition, pages 730-731, Maui, HI, June 1991.