/ Tosiyasu L. Kunii / Professor
/ Valeril V. Trofimov / Visiting Professor
/ Jaques J. Vidal / Visiting 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:
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:
(1) Development of occlusal surface modeling algorithms and software.
(2) Development of jaw sliding simulation algorithm and software, which eliminates the necessity of jaw motion measurement. Recording computer animation on this topic.
(3) Functionally Generated Path modeling.
(4) User interface: report generator using VRML and HTML, a module to enter and view annotations, a motion path visualization.
(5) Algorithms for geometric features extraction of a tooth surface has been developed and implemented on a parallel machine.
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:
Surface curvature features: ridges and ravines. A singularity-based approach to describe view-independent ridges and ravines on generic smooth surfaces is developed. Links are established with singularities of caustics, equidistant sets and skeletons. Several computational approaches to fast and accurate extraction of the ridges and ravines are proposed and tested, using discrete approximations of surface curvature 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.
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 hierarchical 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 hyperworlid 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
Without supports of effective modeling in visual worlds, even if the visual information can be displayed in real worlds, it is difficult to recognize and extract its features and to confirm or verify the identities and the characteristics. Direct mappings target at refining and abstracting multimedia information by cognitive technology and differential technology to efficiently improve our human performance and actively control the real worlds we live. The modeling of visual worlds includes modeling and assembling objects. An assemblability discriminating method and an assembling sequence generating method named SYDEM, which can reduce component match steps from the order of $O(2^n)$ by compositive assembly to the order of $O(n^2)$, is explained by giving an example of CIM assembly process. The three other examples of an effective guide-map generation method, of a hierarchical description of surfaces, and of a conceptual visual human algorithm for skiing, are given to show the drastic efficiency and exactness increase.
Dental CAD/CAM requires appropriate modeling of human jaw motion in contact with the opposite jaw. Such modeling is necessary for planning orthodontic treatment and robust design of dental restorations, especially their occlusal surfaces which must fit the existing articulation patterns. We propose a fast and purely geometric approach to model sliding of the lower jaw over the surface of the upper, fixed jaw. For every discrete step of the motion, a new position and orientation of the sliding object is found by maximizing its displacement toward the fixed object, to get stable contact without interpenetrations. We impose constraints on the range of rotation angles to justify simplifications of our linear model handling the distance from the fixed object to chosen points on the surface of the sliding object as a function of its configuration. In such formulation, we reduce the complexity of the problem of object placement in contact to a linear optimization task. Expensive multi-point collision detection and distance computation are handled by rasterizing graphics hardware, which supports generation of valid configurations for complex objects at stable and interactive speeds. Our model of human jaw sliding compares favorably with experimental motion data.
It is important to reconstruct three-dimensional objects from their cross sections in the field of geographical information systems, medical imaging and solid modeling. For the reconstruction, it is necessary to interpolate the cross sections. Existing methods of interpolation generate the inbetween surfaces using only the points on the cross sectional contours, and produce self-intersecting surfaces when the cross sections vary widely in shape. Moreover, they cannot handle branches correctly when the branching is complex. This paper proposes a method of interpolating complex cross sections by transforming a cross-sectional contour to another based on a diffusion equation. Our method can handle complex branching and can correctly reconstruct passes automatically.
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 $3\times 3$ matrices and the group of isometries of the three dimensional space using the exponential mapping is described as an example of application of this general method.
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 () 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 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.
This paper is devoted to developing a genetic algorithm for a communication network design that minimizes total link cost, and subjects to some constraints like diameter and two-connectivity. Two parallel genetic algorithms on the level of partitioning requirements and the level of dividing population are proposed and implemented over a transputer based parallel network with various virtual network topologies. The ring-ring topology gives the best performance for the parallel genetic algorithm on the level of partitioning requirements, and the torus topology is the most suitable topology for the parallel genetic algorithm on the level of dividing population.
Recent advance in multimedia has necessitated us to look for an effective search method of images. Most of the contemporary indexing methods are based on color distribution in the images. When the users do not remember the colors clearly, however, it has been difficult to retrieve desired images. This paper proposes an indexing method based on shapes contained in an image. We characterize an image by the half planes that contain the objects in it. We also propose a method to characterize images by the vanishing points of parallel lines contained in an image. The vanishing points represent how three-dimensional () objects are projected onto the 2D image.
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.
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.
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.
We propose fast algorithms for the detection of view independent ridges on surfaces given by graphs of functions. The ridges are defined via extrema of the principal curvatures along the associated principal directions. These algorithms have the advantage to be fast and it appears that so-defined ridges deserve as a characteristic feature of the shape of the surface. Results on analytical surfaces and on real data are shown and discussed.
The need for capturing human body motions has been increasing recently for making movies, sports instruction systems and robots that can simulate human motions. This paper proposes a method to facilitate motion capturing using inexpensive video cameras. In our system, a few cameras are used to obtain multiple views of a human body and a three-dimensional () volume consistent with the views is created. A model of the human body is then fitted to the volume to obtain the configuration of the human body. We also propose a method to analyze the stability of human postures. We have analyzed a technique of the traditional Chinese martial art Shorinji Kempo based on the stability to show the effectiveness of our method.
This paper proposes a system that recognizes three-dimensional () objects while measuring them. The system consists of a liquid crystal (LC) projector and a video camera. Our system can be applied to moving objects. The system itself can also move while measuring the objects to obtain the data of a whole scene. In our system, range data is registered on the fly.
Manufacturing automation has lead the global social changes going across the three centuries since its birth in Yorkshire. The 21st century is expecting drastic advances in manufacturing automation with its social impact in several orders of magnitude greater than the predecessors. This research clarifies its nature and direction.
To design industrial products using computers, it is necessary to use highly abstract mathematics such as topology and differential topology. For example, we need topology to check whether the designed objects is valid homologically and manufacturable by NC machines. There are, however, insufficient number of computer engineers that understand such abstract mathematics. To remedy this problem, this paper proposes a new method to visualize a highly abstract mathematical concept such as groups and homology. The visualization method is then used as the core of educational software (eduware). The learners can interact with our system using the actual data where such abstract mathematics are useful and can obtain the intuitive images of the abstract mathematics.
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. We use rasterizing graphics hardware for fast calculation of the distance maps. 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. Such characteristics can be calculated for particular positions of the jaws; cumulative characteristics are used to describe the properties of jaw movement. This information may be used for interactive design of the occlusal surfaces of restorations and for jaw articulation diagnosis. We also demonstrate elements of a user interface that exploit metaphors.
Monte Carlo (MC) photon shooting approach is becoming an important global illumination technique in research and commercial applications. In this work, we focus on the problem of lighting reconstruction of photon density for planar surfaces. Our contribution is in the development of new, efficient density estimation techniques. We formulate local error measures of lighting reconstruction which under some reasonable constraints (discussed below) imposed on the lighting function that behave like the actual error. The minimization of our error estimates is very fast for planar surfaces and usually leads to a better quality lighting result than traditional methods. Also, the local error estimation offers more information than global error measures usually provided by MC solvers, which are not good predictors of image quality. We compare the actual error resulting from various techniques, and evaluate the visual appearance of the reconstructed lighting.
A 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.
With the rapid development and use of fiber optic technology, survivable network design against any single link or single node failure for traffic becomes an extremely important issue for communication network. Several heuristic methods were proposed and compared by many researchers, such as Monma and Shallcross. In this paper, we focus on developing a genetic algorithm based learning algorithm to evolve solutions that minimize total link cost, and subject to more constraints like the network routing, diameter and two-connected survivability rather than just the survivability considered in Davis and Palmer's papers.
In this paper, a distributed genetic algorithm is proposed and it is emphasized that how the distributed genetic algorithm is implemented over a transputer based parallel machine called ParsyTec Gcel-1/64 by using virtual torus topology for a communication network design that minimizes total communication link cost, and subjects to more constraints like the network routing, diameter and two-connected survivability rather than just the survivability.
There are two kinds of modelling topics in a hyperworld system: modelling direct mapping between multimedia information worlds and real worlds, and modelling human interface with a hyperworld. Most of the current researches on improving human interaction with the worlds are limited to the one-to-one interaction, i.e. the interaction of a person with each individual world. The study of the paper is devoted to one-to-many interaction features with the hyperworld, composition of a one-to-many interaction system, and its associated reference model so as to lay foundations for further study and system development.
The most critical step in applying a genetic algorithm to a survivable communication network design is to choose a way to represent a solution to the problem. In this paper, we present a genetic algorithm in which the routing, diameter, and 2 connectivity constraints can be easily and successfully encoded in a chromosome representation. A parallel implementation of the genetic algorithm based learning algorithm in the level of requirements is proposed and implemented in a transputer based parallel machine.
World integration, beyond media integration, means integrating various interaction worlds of different time, space and reality into one system. Such world integration, called a hyperworld, originates from matching with an one-to-many interaction way between a person and the worlds. There have been lots of models, mechanisms and standards the world integration. This paper focuses on basic features of the hyperworld, composition and models of an one-to-many interaction system, and a case study of a telemedicine hyperworld system.