/ Tosiyasu L. Kunii / Professor
/ Takafumi Hayashi / Associate Professor
/ Karol Myszkowski / Associate Professor
/ Elena V. Anoshkina / Visiting Researcher
/ Oleg G. Okunev / Visiting Researcher
/ Galina Okuneva / Visiting Researcher
/ Runhe Huang / Research Associate
The research conducted in the Computer Science and Engineering Laboratory is concentrated on applying methods and concepts progressing in 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. We expect that our techniques of jaw articulation simulation by the computer can replace mechanical articulators used nowadays in dental practice. Also, the quality of design of the occlusal surface will improve and manual adjustment of the inlay/onlay/crown will not be needed after manufacturing. During the second year of the project the following research was conducted: establishing models for articulation simulation and characteristics for evaluation of articulation; development of fast algorithms for collision detection, construction and visualization of distance maps; definition of features of occlusal surfaces (cusps and dips) and basic algorithms for their extraction, including use of parallel processing.
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.
Interpolation in manifolds. A general method for interpolation in manifolds using broken splines is proposed. The approach makes possible construction of splines of arbitrary smoothness in arbitrary manifolds. The method is applied to interpolation of rotations and positions of a rigid body in three-dimensional space using the exponential mapping as the chart.
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. Since real-time lighting simulation is out of question for complex environments, the problem is an efficient storage and display of precalculated distribution of light. An adaptive hybrid approach based on mesh and textures has been developed which makes possible real-time realistic image display
Parallel processing and its applications. In 1994, two parallel algorithms called an even region parallel algorithm and an even strip parallel algorithm for extracting ridge and ravine geometric features of a surface were proposed and implemented on a GCel-1/64 T805 transputer based parallel machine.
Refereed Journal Papers
The Fomenko topological invariant is constructed for the Goryachev-Chaplygin case of the motion of a rigid body with a generalized potential. A theorem asserting that this system and the Kovalevskaya system are roughly equivalent (in the sense that the corresponding Liouville foliations are obtained from one another by twisting along Liouville tori) on some isoenergetic surfaces is proved.
The topology of a new integrable variant of non-holonomic Suslov problem is investigated. Bifurcation diagrams for two independent integrals and Fomenko topological invariants are constructed. The integral manifolds are either Liouville tori with quasiperiodic windings or two-dimensional closed surfaces of maximal genus five with almost all trajectories closed.
This paper presents an efficient adaptive mesh subdivision technique for view-independent, global illumination solutions. The main goal is to provide experimental proof that relaxing the requirement for well-shaped mesh (i.e. allowing disproportions in size and shape of mesh elements, e.g. long, thin triangles) and using variable luminance thresholds to adaptively control mesh subdivision can significantly reduce the number of mesh elements without degrading shading quality. As a result, total time of the lighting simulation is shortened, and subtle shading details can be revealed where other algorithms fail.
We present an efficient method for collision detection between complex objects. The method features stable processing time and a low sensitivity to the complexity of contact between the objects. The algorithm handles both convex and concave objects; however, the top performance is achieved when at least one object is convex in a proximity of the collision zone. The method exhibits real-time performance when calculations are supported by the standard functionality of graphics hardware available on high-end workstations.
A new approach for recognition, description and extraction of ridges and ravines, based on singularity theory; the approach may be used for shape coding and animation.
A new concept of ridges, ravines and related structures (skeletons) associated with a surface in three-dimensional space is introduced. The concept is based on the investigation of relationships between the singularities of the distance function from the surface and singularities of caustic of the normals to the surface. It involves both local and global geometric surface properties and leads to the effective procedure for ridges and ravines recognition.
An integrable variant of a nonholonomic Suslov problem with compact and noncompact energy levels is investigated. The integral manifolds can be both compact and noncompact two-dimensional surfaces, in particular, a torus with four holes, a sphere with four holes, and a sphere with a number of handles and a number of holes. The surgeries of noncompact integral manifolds of integrable Hamiltonian systems are also considered. A generalization of the Reeb graph is proposed for noncompact case.
This paper aims at extracting common factors of art in various areas and scientifically analyze the essential properties of art. We model art by abstract hierarchical data structures and algorithms used in computer science. We try to discover the essential laws common in art based on the " three-step model.'' What is common in various areas of art is that art has extremely high degrees of freedom and there exist infinite solutions even for a simple goal. To overcome such difficulties, this paper proposes a method of abstracting the common features of art using scientific tools such as singularities.
There are kinds of pictures that are drawn with multiple viewpoints. Mountain guide maps, cubism pictures and medical-diagnosis drawings are examples of such pictures. So far, however, they have been drawn intuitively by hand. Implementing a CAD system for such pictures requires clear modelling of their drawing processes. As a case study, the paper presents mountain guide-map modelling using manifolds, and the implementation of multiple-viewpoint CAD based on the model. A local land surface is designed using critical points such as peaks, pits and passes. The local surfaces are then pasted together to from the manifold representing the whole surface. Surface shapes in the overlapping areas are blended using a partition of unity. Projecting a land surface as seen from multiple viewpoints is conducted interactively using the CAD system. Then, the mountain guide map is generated automatically.
We present a new mathematical model and a related user interface for global articulation simulation, developed for the Intelligent Dental Care System project. The aim of the simulation is elimination of the use of mechanical articulators and manual adjustment in the process of designing dental restorations and articulation diagnostic. The mathematical model is based upon differential topological modeling of the jaws considered as a mechanical system. The user interface exploits metaphors that are familiar to dentists from everyday practice. A new input device designed specifically for use with articulation simulation is proposed.
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.
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 hte singularities of the function. Finally, the extracted singular points are analyzed by a Reeb graph together with multiresolution analysis. The applications of the method include analysis of botanical leaf shapes and human facial expressions.
We prove that, under MA+$\neg CH$, if $X$ is a compact, separable space, then every subspace $Y$ of $C_p(X)$ with $Y^n$ Lindel\"of for all $n\in N$ has countable network.
We give criteria for finite and countable powers of a space similar to the Michael line being Lindel\"of. As applications, we give examples related to Lindel\"of property in products of spaces of Michael line type and in products of spaces of continuous functions on separable $\sigma$-compact spaces.
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.
We present a rendering method based on physically accurate lighting simulation designed to visualize complex scenes characteristic for architectural and interior design applications. Separating light interaction with surface into perfectly diffuse and specular components, we propose a method for efficiently handling light paths reaching diffuse surfaces via specular reflection by intermediate surfaces. Specular component is calculated ``on-the-fly'', affecting diffuse component that is stored in adaptive mesh structure for later reuse. It allows a good quality walkthrough animation that by contrast to radiosity approach, exhibits also specular component illuminating diffuse surfaces. Final still images are generated by tracing rays from the eye and collecting mesh stored light from diffuse surfaces. The method compares favorably with analytically precalculated results.
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'.
In the last decade, immense progress in realistic image synthesis has been achieved: increasingly complex scenes can be efficiently rendered, and resulting images look very natural. However, surprisingly little attention has been paid to experimental validation of lighting synthesis algorithms through the comparison of simulation results against measured real-world data. Even more challenging is the comparison of final computer images against corresponding real-world scenes, which also involves human perception issues. In this paper we briefly survey existing reflectance models as well as global illumination and spectral sampling algorithms, and evaluate their verisimilitude in physically-based lighting synthesis. We outline our approach and give a detailed description of our validation experiments. We address also the problem of perception-based reproduction of world luminance levels on a computer monitor. Finally, we present successful applications of our algorithms to lighting design and architecture.
The interest in human body motions in computer science and machinery has been increasing recently, for example, for sports instruction systems and for constructing a robot that can simulate human motions. The understanding of the mechanism of human motions is not, however, sufficient due to its complexity. Basic elements for the analysis of human motions are similar to those of robotics: the Denavit-Hartenberg notation, the configuration space, the work space, singularity etc. Each of the elements is, however, far more complex compared with robots. For example, in robotics, the configuration space is just a cartesian product of the ranges of motion of the joints. In case of a human body, the values of a joint angle depends on the angles of other joints. This paper proposes a new method to obtain data of the human motion using image processing techniques and to analyze it by extracting the essential parts of its configuration path called regions .
Mesh-based radiosity calculation requires many mesh elements to reconstruct subtle details of shading. On the other hand, the excessive number of polygons slows down rendering, impairing the sensation of interactivity when a user-navigated walkthrough in complex environment is performed. When distribution of illumination over a scene is to be quickly rendered, then the Gouraud shaded polygon becomes an inefficient drawing primitive, which can be successfully replaced by texture mapping. This paper proposes an application of texture mapping to reconstruct the shading of surfaces in the scene regions where distribution of illumination is extremely complex. Mesh-based Gouraud shading is used to visualize the remaining surfaces, exhibiting simple illumination, usually constituting the majority of the scene. As a result, many mesh elements can be eliminated, compared to traditional approaches, and image display can be done significantly faster. Also, the improvement of shading quality is possible by recalculating illumination and storing the results as textures in scene regions where a mesh-based approach produces shading artifacts. Experiments performed have shown that application of this idea pays off on high-end workstations, when hardware supported texture mapping is available.
This paper presents a new method for measuring 3D (three dimensional) facial shapes. First of all, the normal vectors at points on the face are computed by using three light sources and by solving Lambertian reflectance map. We can obtain dense information on the approximate facial shape at a time. Light stripes are then projected onto the face to increase the accuracy of the measured value and 3D coordinate values of the points on the stripes are computed by stereo vision. The normal vectors are then integrated inside the circular domains centered at points on the stripes. The local surface shape in each domain is computed using integration. Finally, the local surface shapes are blended to obtain the global facial shape using blending function. This method enables the accurate 3D measurement of complicated shapes of a human face in a short time.
The use of computers to break down communication barriers with the hearing impaired is one of the most challenging tasks of computer application. Our work to generate and recognize sign language based on graphic models, along with the in-depth review of the problems in the conventional approaches, has been summarized in this paper. The explanation is done divided into two subtasks, sign language generation and sign language recognition.
We introduce a new concept of ridges, ravines and related structures (skeletons) associated with surfaces in three-dimensional space that generalizes the medial axis transformation approach. The concept is based on singularity theory and involves both local and global geometric properties of the surface; it is invariant with respect to translations and rotations of the surface. It leads to a method of hierarchic description of surfaces that yields new approaches to shape coding, rendering and design. The extraction of the features is based on differential geometry of surfaces with consequent segregation via multiscale analysis. Terrain feature recognition, dental shape reconstruction and medical imagery are a partial list of applications.
This paper presents a technique for designing a fillet connecting two disjoint solids or surfaces along two rail curves, one on the surface of each geometric object. An axis curve which expresses the essence of the fillet longitudinal shape is first generated. It may be automatically created depending on the objects relative spatial orientations and the rail curves neighborhoods, or modified by the designer. The correspondence between the rail curves is established using a general reparametrization procedure. The homotopy sweep formulation is then used to determine the intermediate contours shapes. The formulation allows the contours shapes to be controlled by an intuitive shape control parameter and two scaling functions. Finally, a lofting surface connecting the contours and and at $G^1$ continuity with the base objects surfaces is generated. The method allows fillets of aesthetic shapes to be designed with ease. It requires less user input and provides a convenient and intuitive means to control the fillet shape. Objects of complex topological shapes can be created by joining handles and branches as fillets, thus ensuring objects are always valid.
This paper describes a parallel polygon rendering method on the graphics computer VC-1 which has been developed for past 4 years. The architecture of the VC-1 is a loosely-coupled array of general-purpose processors, each of which is equipped with a local frame buffer. The contents of the local frame buffers are merged into one in real time considering the visibility control based on screen depth. In our polygon rendering method, polygons are distributed among the processors and each processor independently computes the image of the assigned polygons using the Z-buffer method. To achieve load balancing, a technique called adaptive parallel rasterization is developed. The adaptive parallel rasterization automatically selects the appropriate parallelizing approach according to the estimated size of polygons displayed on the screen. The measured rendering performance of VC-1 using this polygon rendering method is shown.
This paper proposes two parallel algorithms called an even region parallel algorithm (ERPA) and an even strip parallel algorithm (ESPA) respectively for extracting ridge and ravine geometric features of a surface. The parallel programs were implemented on a GCel-1/64 T805 transputer based parallel machine with maximum 64 transputers. The performance of these two algorithms are reported and analyzed in respect of a load balance problem and communication overheads. The efficiency and speed-up versus the number of transputers used and the problem size chosen are shown and discussed.
We define the multimedia as an interface between the real world and Synthetic Worlds. When we treat multimedia in such a way, the limits of current multimedia technology are made clear. There exist 6 types of information corresponding to our 6 senses, and each type of information has its own problems about input, output, synthesis, transfer, creation, and cognition. Our final goal of the multimedia research is to integrate of all types of information. From our experience of 26 years' research, we are certain that the method based on the differential topological modeling and also on collective phenomena modeling plays an essential role in the multimedia research filed, especially in cognition phase.
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.
A conventional analytic method for a process control is based on differential equations. For many complex process control systems, however, the essential mathematical models are seldom valid. Therefore, an alternative approach like an expert system -- an knowledge based controller is required. This approach has overcome the above problem but it requires expert knowledge. When such knowledge is not available or not sufficient, developing a more advanced approach in which a control system does not require expert knowledge and has learning ability, becomes inevitable. Based on prototype rule concept and a genetic algorithm, an intelligent control method is developed and described in this paper.
All approaches to rule-based control have relied upon a pre-classification of the state-space for their success. Given a classification of the state-space, either an individual control action or a whole set of control actions can be learnt. But quality of control is limited by the quality of the state-space classification. When no classification is specified, a more challenging problem is how to arrive at the most suitable partitioning of the state-space with its associated control actions. The approach presented in this paper is to generate prototype rules. Instead of learning a control action for every point encountered, a genetic algorithm is used to learn control actions for a set of limited number of prototype states and the nearest neighbor matching is employed to decide which of the rules to fire in any particular situation when controlling a system. The example of a simulated multiple burner combustion optimization is used to demonstrate this approach.
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, diffusion 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.