外文翻译--实现三维异常照.doc

毕业设计（论文）译文及原稿译文题目：实现三维异常照片-一个对儿童玩具设计的理论解释原稿题目：THREE-DIMENSIONAL REALIZATION OF ANOMALOUS PICTURES-AN APPLICATION OF PICTURE INTERPRETATION THEORY TO TOY DESIGN原稿出处：Technologies for lifelong kindergarten实现三维异常照片-一个对儿童玩具设计的理论解释杉原孝吉数学系信息工程和物理学，东京大学，7-3-1乡，113 bunkyo-ku，东京，日本摘要异常图片一般被视为不可能的物体的照片，但他们中的一些可以实现为三维多面体对象。本文提出了一个交互式系统生成展开表面的对象，系统输出被用来实现作为不可能实现物体的儿童玩具。关键词：光学错觉 释图理论 异常图 玩具 表面展开 不可能的对象可实现性1简介在70年代和80年代早期，解释线图为多面体对象是一个热门话题。然而，在计算机视觉，研究者的兴趣对这个主题已逐渐下降。第一个原因是该理论的主要问题已经被完全解决了。即是，画线代表一个多面体是物理学的一个充要条件。本原因之二是，问题本身是太理想化了很难被应用到实际。数据提取从实际图像到完美的路线图其实有很大的差距，并且这个很难用释图理论来进行直接实时图像处理。 然而，这并不意味着，释图理论是无用的。我们在本文中提出了释图理论的一个新的应用儿童玩具设计。有一类图片我们称为“异常的图片”或“不可能物体的图片”。那些图片产生错觉；当我们看到他们，我们有印象，但在三维物体同一时间，我们觉得是好笑的东西。尽管名字为“不可能的物体”，但是这些照片是对实际三维多面体对象投影的正确的预测。本文描述一个计算机系统，判断一个给定的异常爱洛丝图是否是对一个多面体正确的预测，并且如果是，构建这样一个多面体和生成图的折叠多面体表面。本系统的输出可以应用在为孩子构建“不可能”的对象的材料。本文第二部分是对释图理论的叙述，第三部分描述三维多面体异常图片的特点，第四部分描述如何构建这样一个多面体和生成图的折叠多面体表面。2释图理论述评2.1可实现性问题假设，（x, y, z）是在一个固定的坐标系统三维空间。在Z=1这个面画一条直线D,我们认为如果D是一个多面体在这个三维空间里的投影，那么直线D在这个坐标系统的三维空间里存在的。我们感兴趣的是判断直线D是否能实现。2.2计划第一步的解释线图四是找到一个合理的候选人人数的空间结构，可能代表的图片。为这一目的，本图片标记方案。我们使用术语“顶点”，“边缘”和“面孔”表示几何元素的多面体，使用术语“路口”，“线段”（“线”短）和“区域”，代表自己，图像中的线图。一个边缘被称为凸如果相关的两侧面形成山脊沿着这条边，如果他们形成一个凹谷。一种称为凹线，如果它的形象是一个凹缘；我们分配标签“-”。线被称为凸线，如果它的形象是一个凸棱，我们分配标签“+”。 哈夫曼编码（5）和克劳夫斯（1）建造的完整列表可能的组合的标签在这路口；名单现在称为联接词典。他们发现候选人的代表的空间结构画线的指定标签的线条的一种方法该组合的标签在路口是一致的与交界的字典。 3实现异常的照片那些平时被作为异常物体的照片未必是无法实现的。一些异常物体的图片是可以实现的。比如在图例5中我们看到的这些照片，当我们看到他们的时候，我们很容易想到多面体组成的投影组成的。让我们想象一个多面体便面，我们会发觉如果它是由几个相互垂直的矩形表面拼接而成。事实上，在这些照片里，规则的矩形表面并不存在。因此得名“异常的照片”是合理的。从物质的角度来看，在另一方面，多面体是不规则的表面是可以实现的。这就是为什么他们称为异常的图片。换句话说，他们是异常是因为他们不正确的图片矩形的多面体，但他们仍然是可实现的是由于多面体（除矩形的）能够存在的能从这些照片的投影中。因为他们是可实现的相关的多面体。一个有趣的一点是，当我们看到在一些重建多面体适当的照明，我们得到的印象矩形多面体和一些有趣的感觉。因此，这些产生的一种新型的光幻觉。 4构建“不可能的物体”我们通过异常照片构建不可能的物体，由以下步骤实现交互。首先，我们找到一个图片，图片是隐藏线导致异常但仍然可以实现的。为此，我们采用交界字典图片与隐藏线13）和前面描述的理论1和理论2。一旦一个异常但可实现的图片被发现，该系统的方程（1）和（2）告诉我们最小顶点集，如果我们把整个结构的顶点深度的投影起点的指定为唯一点。然后，我们对这张图片重新选择一个观察点，虽然这个观察点是无穷距离的，但是如果我们采取平行投影，这个观察点相对图片是有限距离的，我们也给深度的顶点在上述最低集。在这一步，我们必须小心不要违反不等式（2）。下一步我们解决系统的方程（1），就会获取三维坐标的所有顶点与平面方程的所有面；这样我们得到的聚面体。最后一步是绘制图的展开表面。如果重叠自动展开，那么我们得尽我们所能做最详尽的搜索，这需要时间相当长。一个有效的方法是当多面体是仅限于一个凸一个凹，我们把表面仅沿边缘展开得到图 18）这样，我们目前指定边缘被削减，图6（一）和（一）以互动的方式表明折叠表面的两点所代表的对象的图片是图5（一）。边界在这个图片中显示为点，这两点的对象应该是2个圆大小相同，而且应该互相接触。 5结语我们描述了一个互动式系统发现多面体的异常的图片和绘画出他们表面展开后形式。系统输出被用来作为不可能实现物体的儿童玩具。这些玩具可以让孩子有机会学习空间几何和视觉感知经验。THREE-DIMENSIONAL REALIZATION OF ANOMALOUS PICTURES-AN APPLICATION OF PICTURE INTERPRETATION THEORY TO TOY DESIGNKOKICHI SUGIHARA Department of Mathematical Engineering and Information Physics, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113, Japan (Received 16 April 1996; in revised form 12 August 1996; received for publication 9 September 1996) Abstract-Anomalous pictures are naively regarded as pictures of impossible objects, but some of them are realizable as three-dimensional polyhedral objects. This paper presents an interactive system for generating the unfolded surfaces of those objects, thus offering toy material from which children can make impossible objects. Published by Elsevier Science Ltd. Optical illusion Interpretation of line drawing Anomalous picture Toy Unfolded surface Impossible object Realizability1. INTRODUCTION In the 1970s and in early 1980s, the interpretation of line drawings as polyhedral objects was one of the hot topics in computer vision. (1-17) However, researchers interest in this topic has decreased gradually. The first reason is that the main theoretical problem was solved comple- tely, O416) i.e. a necessary and sufficient condition for a line drawing to represent a polyhedron was given. The second reason is that the problem itself was too idealistic to be applied to practical problems; line data extracted from real images are far from perfect line drawings treated in this theory. Actually there is a great gap between real noisy data and perfect line drawings, and it seems difficult to utilize the picture-interpretation theory directly for real image processing. However, this does not mean that the picture-inter- pretation theory is practically useless. As an example, we present in this paper a new application of the picture- interpretation theory to the design of childrens toys. There is a class of pictures called anomalous pic- tures or pictures of impossible objects. (2515) Those pictures generate optical illusion; when we see them, we have the impression of three-dimensional objects but at the same time we feel something funny. In spite of the name impossible object, some of those pictures are the correct projection of actual three- dimensional polyhedral objects. In this paper we describe a computer system that judges whether a given anom- alous picture is a correct projection of a polyhedron, and if so, constructs such a polyhedron and generates the figure of the unfolded surface of the polyhedron. The output of the system can be used as toy material from which children construct the impossible objects. We review the basic results in picture-interpretation theory in Section 2, and characterize the class of anom- alous pictures that are correct projections of polyhedra, inSection 3. In Section 4, we describe the interactive sys- tem for generating unfolded surfaces of such polyhedra, and show some examples of objects generated by the system.2. REVIEW OF PICTURE-INTERPRETATION THEORY 2.1. Realizability problem Suppose that the (x, y, z) coordinate system is fixed in a three-dimensional space. Let D be a line drawing fixed in the plane z=l. We say that D is realizable if D is the projection of some polyhedron in the three-dimensional space. We are interested in judging whether D is realiz- able. As shown in Fig. 1, let us assume that the polyhedron is projected on to the picture plane z= 1 by the perspective projection with the center of projection at the origin (0, 0, 0). This assumption does not restrict the problem because whether D is realizable or not does not depend on whether the projection is orthographic, oblique or per- spective.(17) 2.2. Huffman-Clowes labeling scheme The first step for the interpretation of the line drawing D is to find a reasonable number of candidates of the spatial structure which the picture D may represent. For this purpose, the Huffman-Clowes labeling scheme is employed. (1,5) We use the terms vertices, edges and faces to represent geometric elements belonging to a polyhedron, and use the terms junctions, line segments (lines for short) and regions, respectively, to represent their images in the line drawing. An edge is said to be convex if the associated two side faces form a ridge along this edge, and concave if they form a valley. A line is called a concave line if it is the image of a concave edge; we assign the label - to this line. A line is called a convex line if it is the image of a convex edge and if the associated side faces are both visible; we assign the label + to this line. A line is called an occluding line if it is the image of a convex edge and if one of the associated side faces is invisible; we assign the arrow to this line in such a way that both of the associated side faces are to the right of the arrow. Huffman (5) and Clowes (1) constructed the complete list of possible combinations of labels around junctions; this list is now called a junction dictionary. They found candidates of the spatial structure represented by the line drawing D by assigning labels to lines in such a way that the combinations of labels at junctions are consistent with the junction dictionary. Figure 2 shows an example of the consistent labeling. Obviously, this picture does not represent a polyhedron correctly. As shown in this example, a line drawing with a consistent labeling does not necessarily represent a poly- hedron correctly. The existence of a consistent labeling is a necessary (but not sufficient) condition for a line drawing to represent a polyhedron. The junction dictionary was generalized for pictures of paper-made objects (8) and for pictures with hidden lines. 3) 2.3. Realizable pictures Suppose that the line drawing D has a consistent labeling. We want to judge whether the labeling is a correct interpretation of D. 3. REALIZABLE ANOMALOUS PICTURES The pictures that are traditionally classified as anom- alous pictures are not necessarily unrealizable. Some of the anomalous pictures are realizable. (15) Examples of such pictures are shown in Fig. 5. Those pictures are mainly composed of three groups of mutually parallel lines, and when we see them, we are apt to think of polyhedra composed of mutually perpendi- cular faces. Let us call a polyhedron rectangular if it is composed of mutually perpendicular faces. Indeed, rectangular polyhedra are not realizable from those pictures. Hence the name anomalous picture is reasonable. From a mathematical point of view, on the other hand, polyhedra are realizable from those pictures although they are not rectangular. This is the reason why they are called anomalous pictures. In other words, they are anomalous because they are not correct pictures of rectangular polyhedra, but still they are realizable be- cause polyhedra (other than rectangular ones) are realiz- able from those pictures. Since they are realizable, we can reconstruct the associated polyhedra. An interesting point is that, when we see the reconstructed polyhedra under some appropriate illumination, we have the impression of rectangular polyhedra together with some funny feeling. Thus, these polyhedra generate a new type of optical illusion.4. CONSTRUCTION OF IMPOSSIBLE OBJECTS We construct impossible objects from anomalous but realizable pictures interactively by the following steps. First, we find a picture with hidden lines that is anomalous but still realizable. For this purpose, we employ the junction dictionary for pictures with hidden lines 13) and Theorems 1 and 2 described in previous sections. Once an anomalous but realizable picture is found, the system of equations (1) and inequalities (2) tells us the minimum set of vertices such that if we give the depth ofthese vertices, the whole structure of the polyhedron is specified uniquely. Then, we choose the viewpoint re- lative to the picture; the viewpoint is in fmite distance if we take perspective projection, while it is a point at infinity if we take parallel projection. Also we give the depths of the vertices in the above-mentioned minimum set. At this step we have to be careful not to violate the inequalities (2). Next we solve the system of equations (1), and obtain the three-dimensional coordinates of all the vertices together with the plane equations of all the faces; thus we get the complete description of the poly- hedron. The final step is to draw the figure of the unfolded surface. It is difficult to generate a non-overlapping unfolded surface automatically. Indeed, an efficient method is not known for this purpose. What we can do is the exhaustive search, which requires the exponen- tial time in general. An efficient method is known only when the polyhedron is restricted to a convex one and we are allowed to cut the surface not only along the edges but also across the faces. 18) Hence, at present we specify the edges to be cut in an interactive manner. Figure 6(a) and (a t) show the unfolded surfaces of the two pieces of the object represented by the picture in Fig. 5(a). The small circles in this figure show the points at which two pieces of the object should be glued; two circles with the same size sho