/ Tosiyasu L. Kunii / Professor
/ Takafumi Hayashi / Associate Professor
/ Karol Myszkowski / Associate Professor
/ Elena V. Anoshkina / Visiting Researcher
/ Ilia A. Bogaevski / Visiting Researcher
/ Galina Okuneva / Visiting Researcher
/ Runhe Huang / Research Associate
The research conducted in the Computer Science and Engineering Laboratory is concentrated on creating synthetic worlds as the Digital Genesis inside networked computers. The scale of the research requires advanced knowledge including that of advanced mathematics to abstract and model complexity. An important role in the research belongs also to visualization, which is helpful in understanding complex synthetic worlds in computers. The members of the Laboratory currently are working on three ongoing projects:
1. Intelligent Dental Care System
The aim of the project is to develop techniques for computer-aided design and manufacturing of dental restorations. At present the research is focused on designing occlusal surface of teeth taking into account human jaw articulation and following gnathologic rules. During the third year of the project the following research was conducted:
2. Singularity and Differential Topological Modeling of Artificial Worlds in Computers
The goal of the project is to find applications of advanced differential geometry and singularity theory in computer science and its teaching. The research so far is concentrated on:
Geometric features of surfaces: ridges and ravines. A singularity-based coordinate-independent definition for ridges and ravines in surfaces is developed; links are found with classic objects such as caustics and wavefronts. Several computational approaches to the extraction of ridges and ravines are tested, using other geometric features and parallel computation.
Hamiltonian and non-holonomic mechanical systems. Topology of a non-compact non-holonomic Suslov type dynamic system and of the generalized Goryachev-Chaplygin top system are completely investigated. In the first system, exotic topological types of the joint integral levels are found.
3. Virtual Reality
The main goals of the project are enhancement of realism in virtual environments via careful simulation of lighting, and application of parallel processing techniques for speeding up computation.
Lighting simulation. The research was focused on speeding up lighting simulation in complex environments. A hierchical clustering-based radiosity technique has been developed, which shows a high potential for calculating secondary illumination.
Parallel processing and its applications. Several parallel algorithms for extracting ridge and ravine geometric features of a surface were developed and implemented on a GCel-1/64 T805 transputer based parallel machine.
Hyperworld modeling. The basic characteristic of a hyperworld is the direct mapping between multimedia information worlds and real worlds. Drastic efficiency and exactness increase is the primary feature of direct mappings in general. How to effectively model the direct mapping between the multimedia information worlds and the real worlds is key to hyperworld modeling. Two cases of the direct mapping modeling are presented for explaining the drastic efficiency and exactness increase in related application areas.
Refereed Journal Papers
All perestroikas (=bifurcations, metamorphoses) occurring with time in a generic one-parameter family of fronts are standard. If the dimension of a front does not exceed 4, then the list of all standard perestroikas is finite with respect to shifts of time and diffeomorphisms depending on time. This list is known in theory of Legendre singularities. However, families of fronts usually considered in applications are evolutionary. It means that any front is defined uniquely by the initial condition that is the front at a given instant. So evolutionary families ``are not generic'' and the above proposition is not applicable for them. In the paper there are formulated conditions on an evolutionary family of fronts which are true in a plenty of applications and imply the following result. Namely, all perestroikas occurring with time in an evolutionary family of fronts are standard providing the initial condition is generic.
The subject of the paper is the geometrical optics of short linear waves on plane. We describe perestroikas of momentary fronts and scattering of rays when the light hypersurface has generic conical singularities. They appear if the waves propagate in a nonhomogeneous anisotropic medium and are controlled by a hyperbolic variational principle.
The interference of the motion paths of objects has been an important theme of research. The previous works concentrate on detecting collisions and finding colliding points, and little has been done on characterizing the contact of two objects considering the structures of the space between the objects. This paper proposes a novel method to characterize the interference of objects. Our method is based on the analysis of the structures of the complementary space of three-dimensional objects. The topological structures are analyzed using the coding method based on the Morse theory and the Reeb graph. The method is applied to actual dental articulations to validate the model.
This new method employs a hand model and static images to analyze hand posture. Guided by internal constraints and external forces, the model is automatically fitted to the hand image.
This paper presents a novel approach to the reconstruction of geometric models and surfaces from given sets of points using volume splines. It results in the representation of a solid by the inequality $f (x,y,z) \geq 0$. The volume spline is based on use of the Green's function for interpolation of scalar function values of a chosen ''carrier'' solid. Our algorithm is capable of generating highly concave and branching objects automatically. The particular case where the surface is reconstructed from cross-sections is discussed too. Potential applications of this algorithm are in tomography, image processing, animation and CAD for bodies with complex surfaces.
We present an efficient method for collision detection between complex solid objects. The method features stable processing time and low sensitivity to the complexity of contact between objects. The algorithm handles both concave and convex objects, however, the top performance is achieved when at least one object is convex in the proximity of the collision zone (our techniques check the required convexity property as a by-product of calculations). The method exhibits realtime performance when calculations are supported by standard functionality of graphics hardware available on high-end workstations.
Researchers in the fields of computer graphics and geographical information systems (GISs) have extensively studied the methods of extracting terrain features such as peaks, pits, passes, ridges and ravines from discrete elevation data. The existing techniques, however, do not guarantee the topological integrity of the extracted features because of their heuristic operations, which results in spurious features. Furthermore, there have been no algorithms for constructing topological graphs such as the surface network and the Reeb graph from the extracted peaks, pits and passes. This paper presents new algorithms for extracting features and constructing the topological graphs using the features. Our algorithms enable us to extract correct terrain features; i.e., our method extracts the critical points that satisfy the Euler formula, which represents the topological invariant of smooth surfaces. This paper also provides an algorithm that converts the surface network to the Reeb graph for representing contour changes with respect to the height. The discrete elevation data used in this paper is a set of sample points on a terrain surface. Examples are presented to show that the algorithms also appeal to our visual cognition.
We suggest a general method for one-dimensional interpolation in general manifolds, which allows to produce interpolation of arbitrary smoothness; interpolation in the group of orthogonal three-dimensional matrices and group of isometries of the three-dimensional space using the exponential mapping is described as an example of application of this general method.
As the proliferation of multimedia systems continues in diverse application areas, it is becoming increasingly apparent that the performance of the I/O subsystem is a critical limiting factor in the usefulness of such systems. This has spurred extensive research to discover and design efficient and robust I/O systems for the storage and retrieval of multimedia data. To mitigate the effects of the I/O bottleneck in multimedia application environments, we must employ novel technologies and efficient algorithms, and we must use available resources carefully. This paper identifies some significant issues involved and presents a survey of the techniques developed or proposed during recent years to make multimedia I/O more efficient.
To analyze given object shapes, it is necessary first to model the shapes and then to analyze the models. This paper proposes a method of modeling and analyzing two- dimensional (2D) and three-dimensional (3D) shapes based on singularities. First, a function is defined on an object. The object is then modeled by the distribution of the singularities of the function. Finally, the extracted singular points are analyzed by a Reeb graph together with wavelets for multiresolution analysis. The applications of the method include analysis of botanical leaf shapes and human facial expressions.
Computer Graphics has been a very active research area in Japan. Universities and companies have been allocating a relatively large amount of research and development budget on computer graphics research. With the developments of CAD/CAM, visualization and entertainment applications, especially, recent advanced technologies of multimedia and virtual reality, computer graphics research and its applications have become hotter topics. There are unique pure academic researches at universities. Most of the research and development at companies have been traditionally emphasizing engineering and applied research. This article reviews the ''state-of-the-art'' of the Computer Graphics industry and research activities in Japan.
Volume Phase Transition of polymer gel is invesitgated by usin PlotonNMR. $T_1, T_2$ are measeured. Tempolal change of the volume phase transition is made clear on the molecular motion of the polymer chains.
In order to reduce computational complexity of extracting ridges and ravines, two approaches called explicit arithmetic formulae (EAF) and explicit arithmetic formulae with local memory (EAFWLM) are proposed and compared to the approach in which the derivative formulae are used. An even strip parallel algorithm with different approaches of reducing complexity of extraction procedure were implemented on a GCel-1/64 transputer based parallel machine. The results show that the approach of using EAFWLM can greatly reduce the computational complexity of the extraction procedure and significantly ease load balance problem. The even strip parallel algorithm, in conjunction with the EAFWLM approach as an optimized parallel algorithm has shown the much better performance comparing with the other two approaches.
The VC-1 is a parallel graphics machine for polygon rendering based on image composition. This paper describes the architecture of the VC-1 along with a parallel polygon rendering algorithm for it. The structure of the VC-1 is a loosely-coupled array of 16 general- purpose processors, each of which is equipped with a local frame buffer. The contents of the local frame buffers are virtualized with a demand-paging technique, by which the image memory capacity for each local frame buffer is reduced to one eighth of the full-screen capacity. Polygons are rendered in either pixel parallel or polygon parallel depending on the on-screen area of each polygon. The real performance of the VC-1 as well as estimated performance for systems with up to 256 processors is shown.
In massively parallel and distributed systems, as they grow along with the complexity of the tasks they solve, the share of multi-task regimes, such as real-time control problems, multimedia, signal and image analysis and processing, increases. In the presented paper we discuss a mathematical framework for the organization of resource sharing to attain global maximum in computer performance when we have limited resources, such as common memory, channels and so forth. Local strategy of optimization is considered that leads to the optimal distribution of common resources.
Dynamic characteristics of occlusion during lower jaw motion are useful in the diagnosis of jaw articulation problems and in computer-aided design/manufacture of teeth restorations. The Functionally Generated Path (FGP), produced as a surface which envelops the actual occlusal surface of the moving opponent jaw, can be used for compact representation of dynamic occlusal relations. In traditional dentistry FGP is recorded as a bite impression in a patient's mouth. We propose an efficient computerized technique for FGP reconstruction and validate it through implementation and testing. Real-world data are used: the scanned shape of teeth and the measured motion of the lower jaw. We show applications of FGP to analysis of the occlusion relations and occlusal surface design for restorations.
We present new visual tools and a related user interface for global articulation simulation, developed for the Intelligent Dental Care System project. The aim of the simulation is visual representation of characteristics relevant to the chewing process. The simulation is based on the construction of distance maps, which are visual representations of the distributions of the distances of points in a tooth to the opposite jaw. Distance maps are used for collision detection and for the derivation of various characteristics showing the distribution of load on the teeth and the chewing capability of the teeth.
This paper describes a cluster-based hierarchical approach to energy transfer within the framework of a progressive radiosity algorithm. The clustering does not rely on the input geometry, but is performed on the basis of a local position in the scene for a pre-meshed scene model. The locality of the resulting clusters improves the accuracy of form factor calculations, and increases the number of possible high-level energy transfers between clusters within the imposed error bound. Limited refinement of the hierarchy of light interactions is supported without compromising the quality of shading when intermediate images are produced immediately upon user request. The algorithm performs well for complex scenes, and the growth of required data structures is linear with geometric complexity. The results of the experimental validation of the algorithm against measured real-world data show that calculation speed is reasonably traded for accuracy.
The design and fabrication of teeth restorations in dentistry relies increasingly on CAD/CAM techniques. We present an approach for interactive design of the occlusal surface of teeth based on simulation of jaw articulation and computer-aided diagnosis of occlusal disorders. To bridge the cognitive gap between the dentist and the computer system, we propose a virtual reality user interface, which applies the metaphors of tools and techniques known in dentistry. This makes the restoration design more intuitive for dentists. The system uses Virtual Reality Modeling Language (VRML) and HTML standards to generate a treatment report and exchange data in an electronic form.
Modeling of the occlusal surface of teeth is an important problem in computer-aided design of dental restorations. The designed shape must fit the existing jaw articulation. Also, the design process must be fast to be practical in clinical applications. In this paper we present techniques for automatic adjustment of the occlusal surface of restorations based on the results of articulation simulation. The shape of restorations is changed to avoid interpenetrations with the opponent teeth during functional jaw movements. The 3-D space mapping method is used which guarantees the surface smoothness and preservation of the main topological features of the occlusal surface. To speedup calculations we use rasterizing graphics hardware for computationally involved collision detection between complex surfaces of teeth.
As the key visual display- and processing- element of information super highway nodes, computer graphics is advancing into dynamic and higher dimensional visual worlds. So is visual algorithms to program visual worlds as the contents of information super highways. This research presents a drastic approach in designing visual algorithms to construct visual worlds. The address is on the most critical phase of conceptual design that has been conducted ad hoc in designers' mind. Conceptual visual algorithms make mental design processes and design results explicitly represented in a computer executable form after interactive machine translation. Hence, they are explicitly validatable against the design requirements. Taking a popular case of human performance design including dramas, music performance and sporting, recreational skiing algorithm design in particular as an example of visual world design, we show a requirement- driven approach to conceptual visual human algorithm design produces a truly effective skiing method to meet wide varieties of recreational requirements.
This research addresses the issue of human visual cognitive capability to identify an object irrespective of object orientation throughout the course of object movement in computer animation. The identification is by cognizing the shape characteristics that are independent of the object orientation as invariants. Taking a simple case of a silhouette cartoon animation and having a dolphin as an popular example of an object that changes the orientation while swimming and also jumping up into the air, we show that the orientation independent invariants are the critical points, namely the peaks of the convex portion of the object and the pits of concave portions, and that they are derived from a graph of the curvature change along the boundary of the object.
By direct mapping, multimedia information worlds and real worlds are connected closely, and in fact, their combinations form a new world: a hyperworld. In this hyperworld we can, not only get passive multimedia information but also, sense and control real worlds directly and actively. The basic characteristic of a hyperworld is the direct mapping between multimedia information worlds and real worlds. The direct mapping means what we or computers are thinking are realized directly. Drastic efficiency and exactness increase is the primary feature of direct mappings in general. How to effectively model the direct mapping between the multimedia information worlds and the real worlds is key to hyperworld modeling. Two cases of the direct mapping modeling are presented for explaining the drastic efficiency and exactness increase in related application areas.
Up to now, multimedia technology has been focused on transmitting various information via computer networks; everything is converted to data and is transmitted. Such information has been virtual; i.e., the information remains in the realm of synthetic worlds, and at its best, transmitted to the real world in audio-visual (AV) forms. It presents virtual realities. This is the reality of current multimedia. This paper proposes the ideal: the next generation multimedia that use the multimedia data for controlling the real world. The information is mapped to the reality by direct mappings. For example, we can use direct-control robots or direct-control micro machines. The control data can be transmitted via CrossoverNets whose prototype installations have been completed at five hundred sites and have been in daily use for ten years.
Multimedia networks have been studied and developed mainly from a audio-visual information network point of view having such applications in mind as entertainment industry and information systems in general. We have been looking into the possible technological potential of multimedia networks for actually ''moving'' the real worlds such as factories and offices instead of just communicating through various audio-visual media. The aspects of our efforts to crossover the boundary of existing and future analog and digital media has been shown in our past 10 year work realized as CrossoverNet. The ''moving'' of the real world requires enhancing the currently popular multimedia network architecture to incorporate the mechanisms to control various mechanisms in the real worlds, such as instruments and devices in office, factories and other places, mostly in real time. This often requires further work to enhance the mechanisms to make them controllable through multimedia network, ideally directly and digitally without going through complicated servo control schemes. The proposed direct control architecture, thus, inspires a fairly large new research and development area to link multimedia network communication with flexible manufacturing and flexible office automation community. For example, direct control robotics can be advantageously exploited to revolutionary increase the applications to interactively setup flexible manufacturing sites and flexible office automation sites. Office and manufacturing automation are naturally extended to cover the related areas such as hospital automation and logistic automation. This paper presents a multimedia network architecture targeted at flexible manufacturing and flexible automation.
Facing the critical moment of entering into the era of information superhighways, we have to be well prepared to control the flood of information, by cognizing the human need, as well as watch out for the danger of being washed off the shore of human leadership into the ocean of information. The key to success is establishing a cognitive technology that will let the knowledge, either inside computers or accessible through information superhighways, match the level of human cognition through abstraction. As a case study, the most dominant information for human beings, namely visual information, is selected to illustrate the application of essential cognitive technology for abstracting the key features of visual information, in particular of shape information, such as singularities and, more generally, the use of differential topology. Through concrete examples worked out over a couple of decades, I will show, in the case of visual cognition, how the most effective technologies also are the most abstract. The examples include the cognition of the features of geographical terrain surfaces for efficient planning in backpacking, of expert techniques in martial arts (shortening the learning time from 3 years to 30 minutes), and of an effective guide-map generation method to present multiple views of the place of guidance, based on manifolds instead of on a single view.
The CrossoverNet/G2 has been prototyped to provide the information era with an integrated communication infrastructure that allows crossover of diversified communication media currently used in human society, including point-to-point and broadcasting communication, as well as analog and digital communication. The early version has been installed and working for 8 years at 500 sites. The CrossoverNet/G2 is a multimedia network, and realizes our Networked Boxes Conceptual Model. To clear up concepts, the broadcasting system is also reconstructed according to the OSI 7 layers model and specifies the protocols for the audio-visual devices. The prototype model of the CrossoverNet/G2 has been equipped with three subsystems which includes a broadband network, an ATM switching network and an MPEG2 codec system. The Multimedia Center network based on the CrossoverNet/G2 has already been installed at the University of Aizu and this paper presents detailed design of this system.
Many medical, geographical, and computer vision applications require the automatic registration of the 3D images of the same original surface as seen from different directions. For that reason we need to implement visual invariants reflecting essential surface properties. In this paper we investigate view- and coordinate-independent ridges, ravines, and related surface point features; they turn out to be closely connected with singularities of wavefronts, caustics, and Euclidean distance skeletons and, therefore, involve both local and global surface properties. We present methods for their extraction based on advanced differential geometry and demonstrate applicability of the introduced features in image understanding. The analysis of CT images, terrain feature recognition, and fashion design are a partial list of applications.
Computer-aided diagnosis of occlusal disorders and design of dental restorations requires an automated evaluation of jaw occlusion and chewing ability. This requires simulation of the motion of the jaws and characterization of contacts between the surfaces of teeth. We propose approaches to evaluation of the load on teeth and of the grinding process. These characteristics are derived in interactive time, and are based on distance maps and topological structure of the contact zones. The proposed approaches are general and usable in applications where modeling of contact between objects with complex geometry is required.
The multidimensional diffusion model for computer animation of diffuse ink painting opens up a new dimension in painting. In diffuse painting final image is a result of ink diffusion in absorbent paper. A straightforward diffusion model however is unable to provide very specific features of real diffuse painting. In particular, it can not explain the appearance of certain singularities in intensity distribution of gray color in the image. This distribution is one of the most important features of diffuse ink painting. In our previous work, a model based on physical analysis of paper structure was proposed. Although this model provided an adequate simulation of many diffuse ink painting properties, it was still insufficient to explain the singularities of intensity distribution precisely. In the present paper we solve this problem. A multidimensional diffusion model which we propose proves to provide exactly the same intensity distribution as in real images. Method was applied to animate ink diffusion 'Nijimi' of traditional Japanese ink painting 'Sumie'.
Both good measures and essential models are the important premises of evaluating models and mechanisms of distributed multimedia synchronization. Multimedia distortion and fidelity are introduced as the bases of measuring the performance of a reproduced or synthetic multimedia object. Time fidelity, as one kind of important construction information fidelity, is classified into intra-media, inter-media and inter-destination fidelity. The essential model of distributed multimedia synchronization is proposed, and many other models may be regarded as special cases of the essential model. Transmission error and transformation distortion as two new sources of time distortion, are addressed in this paper, and the detailed forms of time distortion are presented and discussed from different viewpoints.
We present an approach to sculpting of functionally defined (or implicit) 3D geometric objects with arbitrary control points linked to features of an object. The displacement of these control points defines global space mapping. To interpolate displacements we use a volume spline based on the Green's function. We apply this technique to objects defined by implicit functions constructed in different ways: set-theoretic operations with R-functions, volume data interpolation, and depth data conversion. A splitting operation by a deformed halfspace is introduced to show the benefits of combining the implicit representation and set-theoretic modeling with sculpting.
Analyzing the 3D images of a given surface as viewed from different positions naturally leads to investigation of coordinate-independent geometric surface features reflecting its essential properties. In the present paper we study surface point features related to ridge and ravine lines on a surface. These lines introduced in our previous works are defined as curves corresponding to the boundary points of the skeleton of the distance transform of the surface. We show that the ridges and ravines can be extracted via the directional derivatives of the principal curvatures along the associated principal directions. However, even after this local description the direct extraction of the ridges and ravines is a time-consuming procedure. It turns out that the ridge and ravine lines contain some remarkable points (end points and others) that can be extracted relatively easily. After finding such points the procedure of ridge and ravine extraction becomes much simpler. Moreover, these points are closely connected with some singularities of caustics and wavefronts, and have an independent interest in image analysis as visual invariants. The paper is devoted to the investigation of such points and the accompanying geometry of singularities of wavefronts and caustics.
Research of this paper is focused on developing an essential model of multimedia synchronization in a distributed multimedia system. Information of a multimedia object is decomposed into content information and time information. An essential model of multimedia synchronization is proposed, and relations of the essential model with some other models are discussed. Multimedia distortion and fidelity are introduced with considering perception of multimedia objects. It is emphasized that multimedia fidelity should become one of basic criteria of multimedia synchronization. It is first time that transmission error of time information and transformation distortion are found as two kinds of time distortion sources. Some new forms of time distortion are given and discussed from different viewpoints.
Person interacts with various worlds in two ways: the one-to-one interaction with a single world and the one-to-many interaction with multi-worlds. Most of the current researches on improving human interaction with the world are limited to the one-to-one interaction, i.e. the interaction of a person with each individual world. Since relations among worlds in the multi-worlds are nonlinear and can be expressed by a set of links, such multi-worlds as a whole is called a hyperworld. This paper focuses on giving an outline of a future hyperworld as a system and presents some problems of developing such a system and proposes potential solutions.
This paper describes an asynchronous communication protocol for an embedded network of transputer I/O devices. The aim of the protocol was to allow a message routing infrastructure small enough to fit within the internal memory of the inexpensive T2 transputer range and yet be flexible enough to cater for all the control and message passing requirements of a complex assembly machine. It was also a requirement that then network was scalable without the need to recompile the source code.
Geometric aspects of computer simulation of a growing mammalian cell colony are presented. Cells are modelled as arbitrarily shaped deformable particles with implicit surfaces. Interpenetrating particles deform each other. A particle can be substituted by a pair of new particles that models the process of cell division. Packing of reproducing particles is performed by a genetic algorithm based on collision detection. Volume of an interpenetration area serves as a fitness function. Parallelization of the simulation algorithm on the network of workstations under the PVM system is described. Simulation results are compared with the images of real cell colonies.
Research of this paper is focused on definitions and models of multimedia distortion and fidelity, and their relations with multimedia synchronizations. The basic idea is that information of a multimedia object can be decomposed into content information (or non-time information) and time information. Time information can be either classified into centralized and decentralized time information, or classified into steady and dynamic time information. According to burstness, diffusions and accumulation of distortion, several new forms of distortion are defined. A logic model of multimedia synchronizations based on synchronization controllers and transmissions is proposed. Main tasks of the controllers are distribution and mapping of distortion on basis of fidelity. It is addressed how to map distortion tolerance to QoS (quality of service) of logic channels for time or non-time information and physical channels.