An efficient animation of wrinkled cloth with approximate implicit integration

This paper presents an efficient method for creating the animation of flexible objects. The mass-spring model was used to represent flexible objects. The easiest approach to creating animation with the mass-spring model is the explicit Euler method, but the method has a serious weakness in that it suffers from an instability problem. The implicit integration method is a possible solution, but a critical flaw of the implicit method is that it involves a large linear system. This paper presents an approximate implicit method for the mass-spring model. The proposed technique updates with stability the state of n mass points in O(n) time when the number of total springs is O(n). In order to increase the efficiency of simulation or reduce the numerical errors of the proposed approximate implicit method, the number of mass points must be as small as possible. However, coarse discretization with a small number of mass points generates an unrealistic appearance for a cloth model. By introducing a wrinkled cubic spline curve, we propose a new technique that generates realistic details of the cloth model, even though a small number of mass points are used for simulation.     

Dynamic vp-tree indexing for n-nearest neighbor search given pair-wise distances

Abstract. For some multimedia applications, it has been found that domain objects cannot be represented as feature vectors in a multidimensional space. Instead, pair-wise distances between data objects are the only input. To support content-based retrieval, one approach maps each object to a k-dimensional (k-d) point and tries to preserve the distances among the points. Then, existing spatial access index methods such as the R-trees and KD-trees can support fast searching on the resulting k-d points. However, information loss is inevitable with such an approach since the distances between data objects can only be preserved to a certain extent. Here we investigate the use of a distance-based indexing method. In particular, we apply the vantage point tree (vp-tree) method. There are two important problems for the vp-tree method that warrant further investigation, the n-nearest neighbors search and the updating mechanisms. We study an n-nearest neighbors search algorithm for the vp-tree, which is shown by experiments to scale up well with the size of the dataset and the desired number of nearest neighbors, n. Experiments also show that the searching in the vp-tree is more efficient than that for the -tree and the M-tree. Next, we propose solutions for the update problem for the vp-tree, and show by experiments that the algorithms are efficient and effective. Finally, we investigate the problem of selecting vantage-point, propose a few alternative methods, and study their impact on the number of distance computation. Received June 9, 1998 / Accepted January 31, 2000     

View management in multimedia databases

Abstract. Though there has been extensive work on multimedia databases in the last few years, there is no prevailing notion of a multimedia view, nor there are techniques to create, manage, and maintain such views. Visualizing the results of a dynamic multimedia query or materializing a dynamic multimedia view corresponds to assembling and delivering an interactive multimedia presentation in accordance with the visualization specifications. In this paper, we suggest that a non-interactive multimedia presentation is a set of virtual objects with associated spatial and temporal presentation constraints. A virtual object is either an object, or the result of a query. As queries may have different answers at different points in time, scheduling the presentation of such objects is nontrivial. We then develop a probabilistic model of interactive multimedia presentations, extending the non-interactive model described earlier. We also develop a probabilistic model of interactive visualization where the probabilities reflect the user profiles, or the likelihood of certain user interactions. Based on this probabilistic model, we develop three utility-theoretic based types of prefetching algorithms that anticipate how users will interact with the presentation. These prefetching algorithms allow efficient visualization of the query results in accordance with the underlying specification. We have built a prototype system that incorporates these algorithms. We report on the results of experiments conducted on top of this implementation. Received June 10, 1998 / Accepted November 10, 1999     

Layered animation of captured data

normal volume of a triangle to convert individual triangles to a volumetric representation. A layered model is constructed to animate the reconstructed high-resolution surface. The model consists of 3 layers: a skeleton for animation from key-frame or motion capture; a low-resolution control model for real-time mesh deformation; and a high-resolution model to represent the captured surface detail. Initially the skeleton model is manually placed inside the low-resolution control model and high-resolution scanned data. Automatic techniques are introduced to map both the control model and captured data into a single layered model. The high-resolution captured data is mapped onto the low-resolution control model using the normal volume. The resulting model enables efficient, seamless animation by manipulation of the skeleton while maintaining the captured high-resolution surface detail. The animation of high-resolution captured data based on a low-resolution generic model of the object opens up the possibility of rapid capture and animation of new objects based on libraries of generic models. Published online: 2 October 2001     

Silhouette-based occluded object recognition through curvature scale space

A complete and practical system for occluded object recognition has been developed which is very robust with respect to noise and local deformations of shape (due to weak perspective distortion, segmentation errors and non-rigid material) as well as scale, position and orientation changes of the objects. The system has been tested on a wide variety of free-form 3D objects. An industrial application is envisaged where a fixed camera and a light-box are utilized to obtain images. Within the constraints of the system, every rigid 3D object can be modeled by a limited number of classes of 2D contours corresponding to the object's resting positions on the light-box. The contours in each class are related to each other by a 2D similarity transformation. The Curvature Scale Space technique [26, 28] is then used to obtain a novel multi-scale segmentation of the image and the model contours. Object indexing [16, 32, 36] is used to narrow down the search space. An efficient local matching algorithm is utilized to select the best matching models. Received: 5 August 1996 / Accepted: 19 March 1997     

Evaluation of statistical and multiple-hypothesis tracking for video traffic surveillance

Abstract. Conventional tracking methods encounter difficulties as the number of objects, clutter, and sensors increase, because of the requirement for data association. Statistical tracking, based on the concept of network tomography, is an alternative that avoids data association. It estimates the number of trips made from one region to another in a scene based on interregion boundary traffic counts accumulated over time. It is not necessary to track an object through a scene to determine when an object crosses a boundary. This paper describes statistical tracing and presents an evaluation based on the estimation of pedestrian and vehicular traffic intensities at an intersection over a period of 1 month. We compare the results with those from a multiple-hypothesis tracker and manually counted ground-truth estimates. Received: 30 August 2001 / Accepted: 28 May 2002 Correspondence to: J.E. Boyd     

A bin picking system based on depth from defocus

It is generally accepted that to develop versatile bin-picking systems capable of grasping and manipulation operations, accurate 3-D information is required. To accomplish this goal, we have developed a fast and precise range sensor based on active depth from defocus (DFD). This sensor is used in conjunction with a three-component vision system, which is able to recognize and evaluate the attitude of 3-D objects. The first component performs scene segmentation using an edge-based approach. Since edges are used to detect the object boundaries, a key issue consists of improving the quality of edge detection. The second component attempts to recognize the object placed on the top of the object pile using a model-driven approach in which the segmented surfaces are compared with those stored in the model database. Finally, the attitude of the recognized object is evaluated using an eigenimage approach augmented with range data analysis. The full bin-picking system will be outlined, and a number of experimental results will be examined. Received: 2 December 2000 / Accepted: 9 September 2001 Correspondence to: O. Ghita     

Smooth multiple B-spline surface fitting with Catmull%ndash;Clark subdivision surfaces for extraordinary corner patches

This paper presents an algorithm for simultaneously fitting smoothly connected multiple surfaces from unorganized measured data. A hybrid mathematical model of B-spline surfaces and Catmull–Clark subdivision surfaces is introduced to represent objects with general quadrilateral topology. The interconnected multiple surfaces are G ² continuous across all surface boundaries except at a finite number of extraordinary corner points where G ¹ continuity is obtained. The algorithm is purely a linear least-squares fitting procedure without any constraint for maintaining the required geometric continuity. In case of general uniform knots for all surfaces, the final fitted multiple surfaces can also be exported as a set of Catmull–Clark subdivision surfaces with global C ² continuity and local C ¹ continuity at extraordinary corner points. Published online: 14 May 2002 Correspondence to: W. Ma     

Model-based detection,segmentation, and classification for image analysis using on-line shape learning

Detection, segmentation, and classification of specific objects are the key building blocks of a computer vision system for image analysis. This paper presents a unified model-based approach to these three tasks. It is based on using unsupervised learning to find a set of templates specific to the objects being outlined by the user. The templates are formed by averaging the shapes that belong to a particular cluster, and are used to guide a probabilistic search through the space of possible objects. The main difference from previously reported methods is the use of on-line learning, ideal for highly repetitive tasks. This results in faster and more accurate object detection, as system performance improves with continued use. Further, the information gained through clustering and user feedback is used to classify the objects for problems in which shape is relevant to the classification. The effectiveness of the resulting system is demonstrated in two applications: a medical diagnosis task using cytological images, and a vehicle recognition task. Received: 5 November 2000 / Accepted: 29 June 2001 Correspondence to: K.-M. Lee     

Zodiac: A history-based interactive video authoring system

Easy-to-use audio/video authoring tools play a crucial role in moving multimedia software from research curiosity to mainstream applications. However, research in multimedia authoring systems has rarely been documented in the literature. This paper describes the design and implementation of an interactive video authoring system called Zodiac, which employs an innovative edit history abstraction to support several unique editing features not found in existing commercial and research video editing systems. Zodiac provides users a conceptually clean and semantically powerful branching history model of edit operations to organize the authoring process, and to navigate among versions of authored documents. In addition, by analyzing the edit history, Zodiac is able to reliably detect a composed video stream's shot and scene boundaries, which facilitates interactive video browsing. Zodiac also features a video object annotation capability that allows users to associate annotations to moving objects in a video sequence. The annotations themselves could be text, image, audio, or video. Zodiac is built on top of MMFS, a file system specifically designed for interactive multimedia development environments, and implements an internal buffer manager that supports transparent lossless compression/decompression. Shot/scene detection, video object annotation, and buffer management all exploit the edit history information for performance optimization.     

A database model for object dynamics

To effectively model complex applications in which constantly changing situations can be represented, a database system must be able to support the runtime specification of structural and behavioral nuances for objects on an individual or group basis. This paper introduces the role mechanism as an extension of object-oriented databases to support unanticipated behavioral oscillations for objects that may attain many types and share a single object identity. A role refers to the ability to represent object dynamics by seamlessly integrating idiosyncratic behavior, possibly in response to external events, with pre-existing object behavior specified at instance creation time. In this manner, the same object can simultaneously be an instance of different classes which symbolize the different roles that this object assumes. The role concept and its underlying linguistic scheme simplify the design requirements of complex applications that need to create and manipulate dynamic objects. Edited by D. McLeod / Received March 1994 / Accepted January 1996     

Using vanishing points for camera calibration and coarse 3D reconstruction from a single image

In this paper, we show how to calibrate a camera and to recover the geometry and the photometry (textures) of objects from a single image. The aim of this work is to make it possible walkthrough and augment reality in a 3D model reconstructed from a single image. The calibration step does not need any calibration target and makes only four assumptions: (1) the single image contains at least two vanishing points, (2) the length (in 3D space) of one line segment (for determining the translation vector) in the image is known, (3) the principle point is the center of the image, and (4) the aspect ratio is fixed by the user. Each vanishing point is determined from a set of parallel lines. These vanishing points help determine a 3D world coordinate system R _o. After having computed the focal length, the rotation matrix and the translation vector are evaluated in turn for describing the rigid motion between R _o and the camera coordinate system R _c. Next, the reconstruction step consists in placing, rotating, scaling, and translating a rectangular 3D box that must fit at best with the potential objects within the scene as seen through the single image. With each face of a rectangular box, a texture that may contain holes due to invisible parts of certain objects is assigned. We show how the textures are extracted and how these holes are located and filled. Our method has been applied to various real images (pictures scanned from books, photographs) and synthetic images.     

Sparse communication networks and efficient routing in the plane

Traditional approaches to network design separate the issues of designing the network itself and designing its management and control subsystems. This paper proposes an approach termed routing-oriented network design, which is based on designing the network topology and its routing scheme together, attempting to optimize some of the relevant parameters of both simultaneously. This approach is explored by considering the design of communication networks supporting efficient routing in the special case of points located in the Euclidean plane. The desirable network parameters considered include low degree and small number of communication links. The desirable routing parameters considered include small routing tables, small number of hops and low routing stretch. Two rather different schemes are presented, one based on direct navigation in the plane and the other based on efficient hierarchical tree covers. On a collection of n sites with diameter D, these methods yield networks with a total of communication links and some bounds on the degree, coupled with routing schemes with constant routing stretch, memory bits per vertex and routes with at most or hops. Received: October 2000 / Accepted: May 2001     

NeTra: A toolbox for navigating large image databases

We present here an implementation of NeTra, a prototype image retrieval system that uses color, texture, shape and spatial location information in segmented image regions to search and retrieve similar regions from the database. A distinguishing aspect of this system is its incorporation of a robust automated image segmentation algorithm that allows object- or region-based search. Image segmentation significantly improves the quality of image retrieval when images contain multiple complex objects. Images are segmented into homogeneous regions at the time of ingest into the database, and image attributes that represent each of these regions are computed. In addition to image segmentation, other important components of the system include an efficient color representation, and indexing of color, texture, and shape features for fast search and retrieval. This representation allows the user to compose interesting queries such as “retrieve all images that contain regions that have the color of object A, texture of object B, shape of object C, and lie in the upper of the image”, where the individual objects could be regions belonging to different images. A Java-based web implementation of NeTra is available at http://vivaldi.ece.ucsb.edu/Netra.     

Using extended feature objects for partial similarity retrieval

In this paper, we introduce the concept of extended feature objects for similarity retrieval. Conventional approaches for similarity search in databases map each object in the database to a point in some high-dimensional feature space and define similarity as some distance measure in this space. For many similarity search problems, this feature-based approach is not sufficient. When retrieving partially similar polygons, for example, the search cannot be restricted to edge sequences, since similar polygon sections may start and end anywhere on the edges of the polygons. In general, inherently continuous problems such as the partial similarity search cannot be solved by using point objects in feature space. In our solution, we therefore introduce extended feature objects consisting of an infinite set of feature points. For an efficient storage and retrieval of the extended feature objects, we determine the minimal bounding boxes of the feature objects in multidimensional space and store these boxes using a spatial access structure. In our concrete polygon problem, sets of polygon sections are mapped to 2D feature objects in high-dimensional space which are then approximated by minimal bounding boxes and stored in an R-tree. The selectivity of the index is improved by using an adaptive decomposition of very large feature objects and a dynamic joining of small feature objects. For the polygon problem, translation, rotation, and scaling invariance is achieved by using the Fourier-transformed curvature of the normalized polygon sections. In contrast to vertex-based algorithms, our algorithm guarantees that no false dismissals may occur and additionally provides fast search times for realistic database sizes. We evaluate our method using real polygon data of a supplier for the car manufacturing industry. Edited by R. Güting. Received October 7, 1996 / Accepted March 28, 1997     

A dynamic animation engine for generic spline objects

This paper introduces an accurate and efficient engine whose purpose is the dynamic animation of curvilinear objects which are modelled as successions of splines. At each time step the object shape conforms to its spline definitions, thus ensuring that each property implied by the chosen spline models is verified. This is achieved by animating spline control points. However, these control points are not considered as material points but rather as the degrees of freedom of the continuous object. The chosen dynamic equations (Lagrangian formalism) reflect this modelling scheme and yield an exact and very proficient linear system. In the chosen formalism, forces are introduced by either their potential energy or their power ratings in the virtual movements instilled by the degrees of freedom. Both methods are carried out in three cases: gravity, viscosity and generic force. Suitable and classical methods for constraint handling and numerical resolution are briefly discussed. Finally, this animation engine is applied to knitted patterns. Copyright © 2000 John Wiley & Sons, Ltd.     

Geometric fusion for a hand-held 3D sensor

Abstract. This article presents a geometric fusion algorithm developed for the reconstruction of 3D surface models from hand-held sensor data. Hand-held systems allow full 3D movement of the sensor to capture the shape of complex objects. Techniques previously developed for reconstruction from conventional 2.5D range image data cannot be applied to hand-held sensor data. A geometric fusion algorithm is introduced to integrate the measured 3D points from a hand-held sensor into a single continuous surface. The new geometric fusion algorithm is based on the normal-volume representation of a triangle, which enables incremental transformation of an arbitrary mesh into an implicit volumetric field function. This system is demonstrated for reconstruction of surface models from both hand-held sensor data and conventional 2.5D range images. Received: 30 August 1999 / Accepted: 21 January 2000     

Motion detection with nonstationary background

Abstract. This paper proposes a new background subtraction method for detecting moving foreground objects from a nonstationary background. While background subtraction has traditionally worked well for a stationary background, the same cannot be implied for a nonstationary viewing sensor. To a limited extent, motion compensation for the nonstationary background can be applied. However, in practice, it is difficult to realize the motion compensation to sufficient pixel accuracy, and the traditional background subtraction algorithm will fail for a moving scene. The problem is further complicated when the moving target to be detected/tracked is small, since the pixel error in motion that is compensating the background will subsume the small target. A spatial distribution of Gaussians (SDG) model is proposed to deal with moving object detection having motion compensation that is only approximately extracted. The distribution of each background pixel is temporally and spatially modeled. Based on this statistical model, a pixel in the current frame is then classified as belonging to the foreground or background. For this system to perform under lighting and environmental changes over an extended period of time, the background distribution must be updated with each incoming frame. A new background restoration and adaptation algorithm is developed for the nonstationary background. Test cases involving the detection of small moving objects within a highly textured background and with a pan-tilt tracking system are demonstrated successfully. Received: 30 July 2001 / Accepted: 20 April 2002 Correspondence to: Chin-Seng Chau     

Visualization of eclipses and planetary conjunction events. The interplay between model coherence, scaling and animation

The problem of an instructive and realistic animation and visualization of the shadow- and color-conditions during conjunctions of actively and passively illuminated cosmic objects has found only particularly satisfying solutions so far. As an example we study a total solar eclipse. There are didactic shortcomings of specialized astronomical software, even though solutions have been given, which are very impressive for experts. Using the possibilities of commercial 3D-animation software we give an object-oriented partial solution. In order to get correct astronomical representations we model – for different tasks – the object space under cinematic aspects with parameters for spatial and temporal scaling, for illumination and coloring under couplings of varying strength. The adaptation of the parameters to optimal acceptance of the spectator must be done a posteriori.