A method has been developed to identify video shots of the same scene where camera flash lights are observed, and the method has been tested by using it to detect such shots from a large TV video archive. Camera flashes are often used in impressive scenes, such as interviews of important persons. Because such scenes are broadcasted repeatedly on various TV programs, a method for detecting them is a promising approach for semantic video indexing. The proposed identification method is invariant to the differences in viewpoint, illumination or any other visual environment because it depends on comparison between temporal occurrence patterns of flash lights. Furthermore, because each flash pattern is represented with a binary array, the comparison requires low computing cost. These advantages mean that the proposed method can be considered to provide semantic and efficient video analysis.

In this paper, an interactive object annotation approach for video database will be proposed. The same semantic objects such as characters, backgrounds, and the main subjects in keyframes of each video shots can be queried and annotated based on the similarity of low-level features such as the color, area, and position of each region. An adaptive image enhancement algorithm is used for handling the lighting changes, and a region-based fuzzy feature matching approach is used for addressing the typical feature representation impreciseness. The content provider can then select relevant keyframes interactively from the results to annotate matched objects in them according to the descriptions that are added into the model. Based on this approach, a video information system is proposed for supporting video content generation. Furthermore, a novel practical application is constructed by using this support system and implemented to show the practicability of it

In this paper, a novel approach, which automatically measures the illumination instability of the video, is proposed to provide selection measure of target video for color-based multimedia system. An information-theoretic measure is proposed as a quantitative measure of the information distribution within an image. This measure is further extended to the video case and used to quantitatively represent the lighting condition of each scene. The illumination instability of the video is thus measured by calculating the instability of the features extracted from the extended measure. Experiments are generated to demonstrate how the proposed approach using the information-theoretic measure to take information distribution within an image into account can reflect the instability more effectively than other simple and straight-forward measures, and how to use it to provide selection measure of target video for color-based multimedia data indexing system

Traffic signal control is proposed for alleviating heavy traffic congestions in urban areas. It is important to measure traveling time along each network link in order to optimize urban traffic signal control. Traveling time measurement by using vision sensor has an advantage in cost compared with those by using spot sensor, license plate reader or floating car. Therefore, we have developed a vision sensor which is able to measure traveling time between the adjacent intersections, installing a single camera at each intersection. This vision sensor covers whole the area of an intersection, and detects a region of vehicle in an image and classifies vehicle sizes and colors. The two vehicle feature sequences are compared with DP Matching to search the same vehicle sequences. Upstream vehicle feature sequences and downstream vehicle feature sequences are segmented into units called fragments and these fragments are compared in DP matching. By matching vehicles on the plane, multiple paths are obtained. Only one path is determined according to two rules; minimize turning frequency of lines, and maximize length of cross line. Measured traveling time has a margin of error of 4.5 % one way or the other for true traveling time. Even if some vehicles fail to match, traveling time of vehicle sequence can be measured according to the vehicles which run around the vehicles. Therefore, this method is very practical.

In this paper, an automated incident detection system for traffic on multilane straight roadways is presented. Utilizing ST-MRF based tracking algorithm, this system detects slow vehicles, congestion and incidents including stalled vehicles. ST-MRF based tracking algorithm is designed for robustness against occlusion and illumination changes regardless of camera angle. Incident detection algorithm consists of multiple operators of three classes: coordinate-class, behavior-class, and event-class. Constructing the semantic hierarchy composed of these classes enables the system to have a natural interface with human traffic control experts. We evaluated the efficiency of this system with 30 months real traffic data in total at two different locations, in which it performed with more than 95% recall rate.

It is important to measure travel time along each network link in order to optimize urban traffic signal control. Although floating car data can provide traveling time along road network precisely, using such on-car devices are not cost effective compared to infrastructure sensors. Therefore, we have developed a vision sensor which is able to measure travel time between the neighboring intersections, installing a single camera at each intersection. This vision sensor covers whole the area of an intersection, and it detects an image region of vehicle each by each, classifies vehicle types and colors, and perform DP-matching to the two sequences of vehicles between the neighboring intersections to identify the same vehicles

Variation in illumination conditions caused by weather, time of day, etc., makes the task difficult when building video surveillance systems of real world scenes. Especially, cast shadows produce troublesome effects, typically for object tracking from a fixed viewpoint, since it yields appearance variations of objects depending on whether they are inside or outside the shadow. In this paper, we handle such appearance variations by removing shadows in the image sequence. This can be considered as a preprocessing stage which leads to robust video surveillance. To achieve this, we propose a framework based on the idea of intrinsic images. Unlike previous methods of deriving intrinsic images, we derive time-varying reflectance images and corresponding illumination images from a sequence of images instead of assuming a single reflectance image. Using obtained illumination images, we normalize the input image sequence in terms of incident lighting distribution to eliminate shadowing effects. We also propose an illumination normalization scheme which can potentially run in real time, utilizing the illumination eigenspace, which captures the illumination variation due to weather, time of day, etc., and a shadow interpolation method based on shadow hulls. This paper describes the theory of the framework with simulation results and shows its effectiveness with object tracking results on real scene data sets.

Cast shadows produce troublesome effects for video surveillance systems, typically for object tracking from a fixed viewpoint, since it yields appearance variations of objects depending on whether they are inside or outside the shadow. To robustly eliminate these shadows from image sequences as a preprocessing stage for robust video surveillance, we propose a framework based on the idea of intrinsic images. Unlike previous methods for deriving intrinsic images, we derive time-varying reflectance images and corresponding illumination images from a sequence of images. Using obtained illumination images, we normalize the input image sequence in terms of incident lighting distribution to eliminate shadow effects. We also propose an illumination normalization scheme, which can potentially run in real time, utilizing the illumination eigenspace, which captures the illumination variation due to weather, time of day etc., and a shadow interpolation method based on shadow hulls. This paper describes the theory of the framework with simulation results, and shows its effectiveness with object tracking results on real scene data sets for traffic monitoring.

For a long period, object tracking in images has suffered from occlusion problems. In order to resolve occlusion problems, we proposed the spatio-temporal Markov random field model for segmentation of spatio-temporal images (Kamijo, S. et al., ICPR'00, vol.1, p.142-7, 2000). This S-T MRF optimizes the segmentation boundaries of occluded objects and their motion vectors simultaneously, by referring to textures and segment labeling correlations along the temporal axis, as well as the spatial axes. As a result, tracking moving objects became very successful against occlusion. Since then, the S-T MRF model has been practically applied to vehicle tracking to reveal good results against occlusion. However, the S-T MRF model was defined to be a general model for the segmentation of spatio-temporal images, and the model is independent of the shape models of target objects. Therefore, in addition to solid objects such as vehicles, the model would be effective for tracking flexible objects, such as pedestrians, against occlusion and clutter situations. We prove the S-T MRF model to be effective for segmentation of traffic scenes which are cluttered by vehicles and pedestrians.

For a long period, object tracking in images has suffered from occlusion problem. In order to resolve occlusion problems, we proposed the spatio-temporal Markov random field model for segmentation of spatio-temporal images in 2000. This S-T MRF optimizes the segmentation boundaries of occluded objects and their motion vectors simultaneously, by referring to textures and segment labeling correlations along the temporal axis, as well as the spatial axes. As a result, tracking moving objects became very successful against occlusion. Since then, the S-T MRF model has been practically applied to vehicle tracking to reveal good results against occlusion. However, the S-T MRF model was defined to be a general model for the segmentation of spatio-temporal images, and the model is independent of shape models of target objects. Therefore, in addition to solid objects such as vehicles, the model would be effective for tracking flexible objects such as pedestrians against occlusion and clutter situation. As a result in this paper, the S-T MRF model was proved to be effective for segmentation of traffic scene which is cluttered by vehicles and pedestrians.

A video content generation support system, based on an interactive approach that maps low-level features to high-level concepts, is proposed. By consulting an ontological semantic object model database, the same semantic objects such as characters, backgrounds, and the main subjects in key frames of each video shots can be queried and automatically annotated based on the similarity of low-level features such as the color, area, and position of each region. Since image recognition techniques are limited in their ability to fully identify and compare images, an additional function is proposed, which uses a coarse model to recover a higher number of similar key frames to provide more relevant results. The content provider can then select relevant key frames interactively from the results to annotate matched objects in them according to the descriptions that are added into the model. Therefore, more complex content can be generated with a higher accuracy by using a combination of the application-oriented operations. The system has high potential for use in object-based interactive multimedia applications. One prototype application is also presented.

Although numerous attempts have been made to determine algorithms and approaches for building up a video information system, not many practical applications have been proposed. In this paper, a novel interactive video information system called the Drama Characters' Popularity Voting System (DCPVS) is constructed by applying the results of off-line object recognition. The system's purpose is to provide description annotation, retrieval, and statistics in the video associated with an object, such as a character as a basic unit, over the Internet. By using the proposed system, multiple users in a network can enjoy the same video and can vote for the characters they like in it. The voting information is collected and stored in the server, which then provides the statistics regarding the popularity of different characters or the voting rates within different periods of the video.

In order to model and to control traffics efficiently, precise traffic monitoring is very important. For those purposes, we developed a real-time system which is able to detect various events such as accidents, congestion, stalled vehicles, fallen objects, etc., and also able to record images before and after the events. This system is based on dedicated tracking algorithm called the spatio-temporal MRF model, which is very robust against occlusions and variations in illumination. Combined with stochastic reasoning, our system was able to classify above events against cluttered situations in traffic images. Finally, by operating the system by a roadside for six months, our system proven to be very successful.

To achieve efficient traffic flow, it is important to base control of traffic signals on observation of pedestrian flow as well as vehicle flow. In consideration of safety, it is also important to analyze behavioral relationship between pedestrians and vehicles, which can be conductive to accidents at intersections. Toward the goals of efficiency and safety, we developed a precise tracking algorithm based on the spatio-temporal MRF model which is able to track both pedestrians and vehicles simultaneously against occlusions in the images. Based on experimental results, this model was able to simultaneously track pedestrians and vehicles against occlusion even in very cluttered situations. Consequently, the S-T MRF model was proven to be effective for traffic monitoring at urban intersections.

In this paper, we present an efficient method to synthesize large-scale scenes, such as broad city landscapes. To date, model based approaches have mainly been adopted for this purpose, and some fairly convincing polygon cities have been successfully generated. However, the shapes of real world objects are usually very complicated and it is infeasible to model an entire city realistically. On the other hand, image based approaches have been attempted only recently. Image based methods are effective for realistic rendering, but their huge data sets and restrictions on interactivity pose serious problems for an actual application. Thus, we propose a hybrid method, which uses simple shapes such as planes to model the city, and applies image based techniques to add realism. It can be performed automatically through a simple image capturing process. Further, we also analyze the relationship between error and number of needed images to reduce the data size.

Considerable progress has been attained in media streaming technology. It is now possible to combine digital images with synchronized audio and video content to create live or on-demand slide shows for the Web. In more advanced settings, the images can also be annotated for synchronized playback. However, despite advances in data compression and congestion control, media streaming is still sensitive to fluctuation of network traffic. We propose a new Web presentation tool that uses text-to-speech synthesis as an alternative to audio streaming. On playback the synchronization of slide annotations and transitions with the synthetic narration can be preserved without concerns for the individual differences in the users' environments in terms of CPU power and bandwidth availability. The implemented prototype includes a standalone production client and a Web playback client.

This paper deals with content-based objects detection for the recognition of building images. The aim of this research is to develop a robust method by which the building images taken under different imaging conditions like view, illumination and scale can be recognized correctly. In the approach presented in this paper, the regions of objects like windows and wall are first detected from a building image based on their visual contents. Here, the segmentation of regions is done using color information and the regions of windows and wall are detected based on edge information and the location of regions. Then, some features like the proportions of width to height of windows and the invariant color features extracted from the region of wall are extracted for the robust recognition of building images. Finally, experimental results reveal the efficacy of the method proposed in this paper.

In this paper, we propose an image-based approach to synthesize a novel view image for mixed reality (MR) systems. Theoretically, the image-based method is good for synthesizing realistic images, but it is difficult to achieve interactive handling of the object. As a solution, we propose a new method based on the "surface light field rendering" technique. With this method, we can synthesize the objects with arbitrary deformation and illumination changes. To demonstrate the efficiency of this method, we describe successful experiments that we performed using objects with non-rigid effects (e.g. velvet and Tatami carpet) which are difficult to render correctly by the use of general model-based rendering techniques.

In this paper, we present a multimedia map database system. The system is mainly employed for acquisition, storage and retrieval of the real-world urban images with viewpoint information. Here, the images and the viewpoint information are assumed to be collected from the mobile multimedia terminal users. By using the viewpoint information in the database system, an Extended Visual Map is proposed for presenting the images according to the actual viewpoint of any user; also a position information service is implemented to retrieval the map information by building images. To realize these objectives, the features of the regions containing a building in every real-world urban image are extracted and compared automatically by the proposed system.

This paper describes an efficient method to obtain 3D information by using spatio-temporal analysis of omni images for outdoor navigation and map-making in the intelligent transportation system (ITS) application. Two types of omni-directional cameras are employed to make a spatio-temporal volume, which is a sequence of omni images stacked in the spatio-temporal space. For the spatio-temporal analysis of an omni image, we define several different cross sections in such spatio-temporal volumes, and examine characteristics of the traces of image features on the cross sections. We determine that the vertical straight lines in the real world are preserved as straight lines on these cross sections and that the degree of this slope represents the quotient of the velocity of the camera motion and the depth of the object. To acquire 3D information using these characteristics, we propose a hybrid method of the epipolar-plane image (EPI) analysis and the model-based analysis. To demonstrate the effectiveness of this method, we present some experimental results and the ITS applications using an omni-directional video camera to obtain images in outdoor environments.

This paper presents a new method for rendering views, especially those of large-scale scenes, such as broad city landscapes. The main contribution of our method is that we are able to easily render any view from an arbitrary point to an arbitrary direction on the ground in a virtual environment. Our method belongs to the family of work that employs plenoptic functions; however, unlike other works of this type, this particular method allows us to render a novel view from almost any point on the plane at which images are taken. Previous methods, on the other hand, have some restraints concerning their re-constructable area. Thus, when synthesizing a large-scale virtual environment such as a city, our method has a great advantage. One of the applications of our method is a driving simulator in the ITS domain. We can generate any view on any lane on the road from images taken by running along just one lane. Our method, using an omni-directional camera or a measuring device of a similar type, first captures panoramic images by running along a straight line, recording the capturing position of each image. When rendering, the method divides the stored panoramic images into vertical slits, selects some suitable ones based on our theory, and reassembles them for generating an image. The method can make a virtual city with walk-through capabilities. In that virtual city, people can move and look rather freely. In this paper, we describe the basic theory of a new plenoptic function, analyze the applicable areas of the theory and the characteristics of generated images, and demonstrate a complete working system using both indoor and outdoor scenes.

In order to use multimedia information more flexibly, supplemental reference information which describe the contents of the data need to be more substantially utilized. This kind of information can be generated at different levels of abstractions and with differing reliabilities depending on the method of acquisition (manual/automatic/semi-automatic). For practical applications, it would be extremely useful to have a framework which can integrate and manage these reference information. We are currently developing an XML based framework, VSDL (video stream description language) which can integrate and manage reference information of various media. In this paper, a subset of VSDL-VSDL-RW (real world video stream description language) is proposed, which can potentially be used to develop a variety of different application systems concerning real world information. As an example of its capabilities, we have developed a prototype system based on VSDL-RW, named image-map linking/utilization system (IMLUS) which can automatically associate image sequences with related digital maps.

It is very important to achieve reliable vehicle tracking in ITS application such as accident detection. The most difficult problem associated with vehicle tracking is the occlusion effect among vehicles. In order to resolve this problem, we applied the dedicated algorithm which we defined as spatio-temporal Markov random field model to traffic images at an intersection. The spatio-temporal MRF considers texture correlations between consecutive images as well as the correlation among neighbors within a image. As a result, we were able to track vehicles at the intersection robustly against occlusions. Vehicles appear in various kinds of shapes and they move in random manners at the intersection. Although occlusions occur in such complicated manners, the algorithm given was able to segment and track such occluded vehicles at a high success rate of 93-96%. The algorithm requires only gray scale images and does not assume any physical models of vehicles.

The paper describes an efficient method to obtain 3D information from omni-camera images using epipolar-plane image (EPI) analysis. Two types of omni cameras are employed to make a spatio-temporal volume, which is a sequence of omni images stacked in the spatio-temporal space. For the EPI analysis of omni image, we examine different types of cross sections in such spatio-temporal volumes. To conduct the EPI analysis realisticly, we must find out the cross section on which the vertical straight lines in the real world are preserved as straight lines. We define such a cross section as omni EPI. To acquire 3D information using the characteristics of the omni EPI, we propose model based EPI analysis. To demonstrate the effectiveness of this method, we present experimental results using an omni video of outdoor environments.

Presents a method for creating a 3D virtual broad city environment with walk-through systems based on image-based rendering (lBR). In that virtual city, people can move rather freely and look at arbitrary views. The strength of our method is that we are able to easily render any view from an arbitrary point to an arbitrary direction on the ground in a virtual environment; previous methods, on the other hand, have strong restraints concerning their reconstructable areas. One of the other applications of our method is a driving simulator in the ITS domain. We can generate any view on any lane on the road from images taken by running along just one lane. Our method first captures panoramic images running along a straight line, indexing the capturing position of each image. The rendering process consists of selecting some suitable slits divided vertically from stored images, and reassembling them to create an image from a novel observation point.

We have developed an algorithm, referred to as spatio-temporal Markov random field, for traffic images at intersections. This algorithm models a tracking problem by determining the state of each pixel in an image and its transit, and how such states transit along both the x-y image axes as well as the time axes. Our algorithm is sufficiently robust to segment and track occluded vehicles at a high success rate of 93%-96%. This success has led to the development of an extendable robust event recognition system based on the hidden Markov model (HMM). The system learns various event behavior patterns of each vehicle in the HMM chains and then, using the output from the tracking system, identifies current event chains. The current system can recognize bumping, passing, and jamming. However, by including other event patterns in the training set, the system can be extended to recognize those other events, e.g., illegal U-turns or reckless driving. We have implemented this system, evaluated it using the tracking results, and demonstrated its effectiveness.

In order to utilize image sequences and their related digital map, the linking between them is indispensable. This paper proposes a method for linking between image sequences and their related digital map using DP (Dynamic Programming) matching algorithm. In this method, at first several numbers of patterns-such as the vertical boundary pattern, the height pattern, and the street intersection pattern-are extracted from the video, as well as from the digital city map. The linking is realized by matching these video patterns with the corresponding patterns of the digital city map using an end-opened DP matching technique. In order to show the effectiveness of this proposed method, experimental results are also presented.

In this paper, a method of detecting the information relating to building object in news video is proposed. Some models are used for the detection. The first frame of each shot is employed based on the detection of scene changes. From the viewpoints of computation and complexity, the frames irrelevant to information on building objects are first removed. For the detection of frames containing building objects, edge information is used to decide whether a frame contains building objects. Moreover, the caption appearing in news video is also used for the detection of information on building objects. Based on the construction of indices on building names in the Multimedia Map Database (MMD) using a method called "finger prints", the caption information on building objects can be recognized. Finally, some experimental results are given to reveal the efficacy and accuracy of the proposed method in this paper.

Mixed reality (MR) systems which integrate the virtual world and the real world have become a major topic in the research area of multimedia. As a practical application of these MR systems, we propose an efficient method for making a 3D map from real-world video data. The proposed method is an automatic organization method focusing on video objects to describe video data in an efficient way, i.e., by collating the real-world video data with map information using DP matching. To demonstrate the reliability of this method, we describe successful experiments that we performed using 3D information obtained from the real-world video data.

Fully automated understanding of engineering drawing is still extremely difficult. In practice, tremendous efforts have to be spent on manual operations on the results generated by automatic understanding systems. To solve this bottleneck we have proposed an interactive recognition system which employs strictly conditioned production rules to automatically process objects with little noise and distortion, and for the rest, employs more flexible rules to propose possible recognition results. The final judgement is left for operator to make. To overcome its problems, in this paper, we propose a new method for generating proposal of recognition results. The proposed method makes use of past interface results to generate proposals. We also propose a mechanism for planning the order in which graphical objects are presented to operator for judgement, to maintain the success rate of proposal at a steady rise. Experimental results show that the proposed new system is very effective. The correct rate of recognition proposals is improved from 70% to 90%. Since the proposed method only makes use of processed examples, it is also application independent.

We propose a new way of constructing a drawing recognition system. The system has the ability of rule acquisition and therefore can be easily adopted to drawings of different specifications. Rule acquisition is realized through an empirical learning module, which constructs decision trees from teacher examples and translates the decision trees into production rules for actual recognition. The teacher examples are stored along with the corresponding environmental parameters so that future modification/expansion becomes much more easier. Since most of the attribute values are continuous-valued so that the construction of decision tree is more time consuming, we propose can improved algorithm for more efficient selection of cut points. Experimental results show that the proposed algorithm for cut point selection in decision tree generation improves the efficiency by up to 6 times while ensuring the optimal result.

In this paper we propose a new framework of object-oriented model named MTDM (Matching Tree Driving Model) for drawing understanding and verify its ability of noise absorption. MTDM makes use of descriptions of object-oriented style and is an integration of static and dynamic description of recognition target. Static descriptions are for representation of abstract features so that description of structure and restriction become easier. At the same time static descriptions can be independent of matching procedures of recognition target. The dynamic descriptions are for matching control of recognition target in the form of tree structure named matching tree. Matching procedures for complex targets can be easily described with multiple matching trees. By application to several typical engineering drawings, particularly drawings with noises and distortions MTDM is proven to be suitable for multipurpose and multitarget platform.

The development of a graphical kernel for geographical information systems is reported. It is based on a multi-dimensional data structure called GBD tree which provides an efficient environment for spatial data retrieval. Graphic entities are classified and represented by a small set of primitive geometrical entities which are implemented as a C++ class library. Applications can derive their own data types from the providing kernel by exploiting the IFO object-oriented data model. Although the main purpose is to support the GIS applications, it can be expected that this graphic kernel can be extended to a general-purpose one for graphic applications.>

A drawing understanding system using state transition models is described. This system performs flexible understanding following bottom-up and top down rules, which are easily derived. However, the system is sensitive to minor changes in drawings and has difficulty determining threshold values. A rule learning facility for overcoming these problems was added and evaluated. The system can generate rules from interactions with users using a machine learning method. It was confirmed that this system can generate proper rules for practical drawing understanding from plain interactions.>

An object-oriented drawing understanding system named OO-Mudams, which can flexibly adapt to various types of drawings by defining their model, is proposed. OO-Mudams is a model-driven system, with reasoning engine, management of internal database for reasoning results, and model definition for users. By defining the models, the system can be customized to process various kinds of drawings including engineering drawings and layout drawings. In order to manage huge reasoning result space effectively, the system uses an efficient multidimensional data structure named BD-tree, and, to facilitate the reasoning process, the TMS (truth maintenance system) is used to maintain the dependency among reasoning results. OO-Mudams is characterized by its flexible object-oriented system structure and an object-oriented language for defining the model of target objects.>

A new multidimensional data structure, multidimensional tree (MD-tree), is proposed. The MD-tree is developed by extending the concept of the B-tree to the multidimensional data, so that the MD-tree is a height balanced tree similar to the B-tree. The theoretical worst-case storage utilization is guaranteed to hold more than 66.7% (2/3) of full capacity. The structure of the MD-tree and the algorithms to perform the insertion, deletion, and spatial searching are described. By the series of simulation tests, the performances of the MD-tree and conventional methods are compared. The results indicate that storage utilization is more than 80% in practice, and that retrieval performance and dynamic characteristics are superior to conventional methods.>

Color video images have become a very important media in communication. This has increased the necessity of displaying and handling color video images on various types of computers. In computerized color image processing, most color images are represented by 24 bits per pixel. Such images usually contain a lot of redundancy and require a large amount of space to be stored. Furthermore, they require expensive full color display devices, so that many general-purpose computers which have only colormap display devices are not capable of displaying them. In order to lower the display and the storage cost, color image quantization algorithms are needed to reduce the number of colors in original images. The authors propose a color quantization method for video images which efficiently generates color quantized video images with stable color allocations.>

An efficient spatial data management method for non-zero size spatial objects, called R(Region)MD-tree, is proposed. In this method, a graphic object in an N-dimensional space is represented as a point in a 2*N dimensional space by the centroid and the extension in each axial direction. The point data are managed by the MD-tree after applying the coordinate transformation. The point location problem or range searching in the original N-dimensional space are carried out by the hyper-rectangular range searching to the point data in the 2*N dimensional space. In this representation and data management, data objects are sorted and classified according to not only the location but also the size of the data. By the simulation experiments, the performances and efficiencies of the RMD-tree are compared with the conventional MD-tree and the R-tree. As the data objects become larger, the RMD-tree is superior in the searching speed by 2 approximately 4 times to the conventional ones, and the performances are almost comparable even if the objects are points or small graphic data.>

Recently, multi-purpose and generalized image/pattern recognition methods are required. To achieve this, it is desired to realize an automated recognition rule generation system. In this paper, a learning system of structural description rules which are used as models for the model based vision is presented. This system can generate structural description rules efficiently using partially structured example figure descriptions, and a proper inductive inference algorithm for generating structural description rules.>

In graphics data management, intermediary shape representations such as minimal rectangles and minimal spheres are useful to accelerate such basic geometrical operations as range retrieval. However, when the shapes of the data are complicated or the time for the intersection checks is dominant, another intermediary representation which can reduce the number of intersection checks is desired. The authors propose a new method using 'bound dots' which locate on the contacts of the entity and its minimal rectangle. According to the results of theoretical evaluations and simulation experiments, this method can be found to drastically reduce the number of required intersection checks, compared with the ordinary method using minimal rectangles.>

A new dynamic data structure for spatial retrieval called a GBD tree is proposed. The GBD tree is systematically constructed using homogeneous nodes with a small amount of extra data called a DZ expression which plays an important role in efficient multiway recursive division of N-dimensional space. On the GBD tree, CPU cost during insertion and deletion is much smaller than on an R-tree, while attaining higher spatial retrieval efficiency.>

A multilayer (ML) data structure, which is a hierarchical data structure for N-dimensional data classified into layers, is proposed. In the ML structure, a node structure is extended so that data can be stored not only in the leaves (terminal nodes) but also in internal nodes by adding a layer-management mechanism. The creation, management, and searching methods of the ML structure are described, taking two-dimensional point data classified into layers as an object. The management of line data or expansion to n(n>2)-dimensional data can be easily realized. Good retrieval performances are obtained in the case of a spatial search for a specific layer's data and that for plural layers' data.>

A flexible drawing understanding system with state transition models is proposed. The drawing processor AI-Mudams (written in C) is used as the token extractor in the embodiment discussed. Given drawing images are converted efficiently to suitable geometrical primitives, such as contour vectors, core vectors, dots loops, or, in some cases, primitives with semantics (road line, or house etc.). The understanding system kernel is implemented in Prolog, and the geometrical evaluator is also prepared in C for checking basic geometrical situations, including shape, geometrical relations, and allocations. This understanding kernel accepts the individual state transition rules corresponding to individual drawing images and recognition targets and realizes understanding in the form of bottom-up and top-down state transition. Experiments on different types of drawings reveal that the framework is flexible and effective for various kinds of drawing image.>

A multidimensional data structure, the MD-tree (multidimensional tree), is proposed. The MD-tree is developed by extending the concept of the B-tree to multidimensional data, so that the MD-tree is a height-balanced tree similar to the B-tree and, even its worst-case storage utilization is more than 66.7%. A description is given of the structure of an MD-tree and the results of a series of simulation tests which indicate that the storage utilization is more than 80% in practice and that the retrieval performance and the dynamic characteristics are superior to those of conventional methods.>