Advances in Computer Graphics and Computer Vision

Surface editing operations commonly require geometric details of the surface to be preserved as much as possible. We argue that geometric detail is an intrinsic property of a surface and that, consequently, surface editing is best performed by operating over an intrinsic surface representation. This intrinsic representation could be derived from differential properties of the mesh, i.e. its Laplacian. The modeling process poses nonzero boundary constraints so that this idea results in a Poisson model. Different ways of representing the intrinsic geometry and the boundary constraints result in alternatives for the properties of the modeling system. In particular, the Laplacian is not invariant to scaling and rotations. Either the intrinsic representation is enhanced to be invariant to (linearized) transformations, or scaling and rotation are computed in a preprocess and are modeled as boundary constraints. Based on this representation, useful editing operations can be developed: Interactive free-form deformation in a region of interest based on the transformation of a handle, transfer and mixing of geometric detail between two surfaces, and transplanting of a partial surface mesh into another surface. The main computation involved in all operations is the solution of a sparse linear system, which can be done at interactive rates. We demonstrate the effectiveness of this approach in several examples, showing that the editing operations change the shape while respecting the structural geometric detail.

In the field of view-dependant continuous level of detail of triangle-meshes it is often necessary to extract the current LOD triangle by triangle. Thus, triangle strips are only of very limited use, or only usable with a high effort. In this work a method is proposed that allows a stepwise reduction of a great, fine stepped LOD hierarchy by merging nodes. The result of this process is a reduced hierarchy, which allows the extraction of many neighboring static triangles in one step, so that triangle strips are applicable more efficiently. We show that this results in a significant decimation of processed vertices without loosing a smooth LOD transition.

This paper examines the application of the human vision theories of Marr and Biederman to the retrieval of three-dimensional objects. The key idea is to represent an object by an attributed graph that consists of the object’s meaningful components as nodes, where each node is fit to a basic shape. A system that realizes this approach was built and tested on a database of about 400 objects and achieves promising results. It is shown that this representation of 3D objects is very compact. Moreover, it gives rise to a retrieval algorithm that is invariant to non-rigid transformations and does not require normalization.

Synthesizing terrain or adding detail to terrains manually is a long and tedious process. With procedural synthesis methods this process is faster but more difficult to control. This paper presents a new technique of terrain synthesis that uses an existing terrain to synthesize new terrain. To do this we use multi-resolution analysis to extract the high-resolution details from existing models and apply them to increase the resolution of terrain. Our synthesized terrains are more heterogeneous than procedural results, are superior to terrains created by texture transfer, and retain the large-scale characteristics of the original terrain.

Professional 3D digital content creation tools, like Alias Maya or discreet 3ds max, offer only limited support for a team of artists to work on a 3D model collaboratively. We present a scene graph repository system that enables fine-grained collaboration on scenes built using standard 3D DCC tools by applying the concept of collaborative versions to a general attributed scene graph. Artists can work on the same scene in parallel without locking out each other. The artists’ changes to a scene are regularly merged to ensure that all artists can see each others progress and collaborate on current data. We introduce the concept of indirect changes and indirect conflicts to systematically inspect the effects that collaborative changes have on a scene. Inspecting indirect conflicts helps maintaining scene consistency by systematically looking for inconsistencies at the right places.

Visualising implicit surfaces with the ray casting method is a slow procedure. The design cycle of a new implicit surface is, therefore, fraught with long latency times as a user must wait for the surface to be rendered before being able to decide what changes should be introduced in the next iteration. In this paper, we present an attempt at reducing the design cycle of an implicit surface modeler by introducing a progressive refinement rendering approach to the visualisation of implicit surfaces. This progressive refinement renderer provides a quick previewing facility. It first displays a low quality estimate of what the final rendering is going to be and, as the computation progresses, increases the quality of this estimate at a steady rate. The progressive refinement algorithm is based on the adaptive subdivision of the viewing frustrum into smaller cells. An estimate for the variation of the implicit function inside each cell is obtained with an affine arithmetic range estimation technique. Overall, we show that our progressive refinement approach not only provides the user with visual feedback as the rendering advances but is also capable of completing the image faster than a conventional implicit surface rendering algorithm based on ray casting.

An Image-Based Rendering (IBR) approach to appearance modelling enables the capture of a wide variety of real physical surfaces with complex reflectance behaviour. The challenges with this approach are handling the large amount of data, rendering the data efficiently, and previewing the model as it is being constructed. In this paper, we introduce the Incremental Weighted Least Squares approach to the representation and rendering of spatially and directionally varying illumination. Each surface patch consists of a set of Weighted Least Squares (WLS) node centers, which are low-degree polynomial representations of the anisotropic exitant radiance. During rendering, the representations are combined in a non-linear fashion to generate a full reconstruction of the exitant radiance. The rendering algorithm is fast, efficient, and implemented entirely on the GPU. The construction algorithm is incremental, which means that images are processed as they arrive instead of in the traditional batch fashion. This human-in-the-loop process enables the user to preview the model as it is being constructed and to adapt to over-sampling and under-sampling of the surface appearance.

Painterly animation is a method that expresses images with a hand-painted appearance from a video, and the most crucial element for it is the coherence between frames. A motion map generation is proposed in this paper as a resolution to the issue of maintaining the coherence in the brush strokes between the frames. A motion map refers to the range of motion calculated by their magnitudes and directions between the frames with the edge of the previous frame as a point of reference. The different methods of motion estimation used in this paper include the optical flow method and the block-based method, and the method that yielded the biggest PSNR using the motion information (the directions and magnitudes) acquired by various methods of motion estimation has been chosen as the final motion information to form a motion map. The created motion map determined the part of the frame that should be re-painted. In order to maintain the temporal coherence, the motion information was applied to only the strong edges that determine the directions of the brush strokes. Also, this paper sought to reduce the flickering phenomenon between the frames by using the multiple exposure method and the difference map created by the difference between images of the source and the canvas. Maintenance of the coherence in the direction of the brush strokes was also attempted by a local gradient interpolation in an attempt to maintain the structural coherence.

This paper focuses on visualization and manipulation of graphical content in distributed network environments. The developed graphical middleware and 3D desktop prototypes were specialized for situational awareness. This research was done in the LArge Scale COllaborative decision support Technology (LASCOT) project, which explored and combined software technologies to support human-centred decision support system for crisis management (earthquake, tsunami, flooding, airplane or oil-tanker incidents, chemical, radio-active or other pollutants spreading, etc.). The performed state-of-the-art review did not identify any publicly available large scale distributed application of this kind. Existing proprietary solutions rely on the conventional technologies and 2D representations. Our challenge was to apply the "latest" available technologies, such Java3D, X3D and SOAP, compatible with average computer graphics hardware. The selected technologies are integrated and we demonstrate: the flow of data, which originates from heterogeneous data sources; interoperability across different operating systems and 3D visual representations to enhance the end-users interactions.

This paper describes novel concepts for the interactive composition of artistic real-time graphics, so-called live visuals. By establishing two fundamental techniques dealing with the structured media integration and the intrinsic design process, we significantly increase the efficiency of interactive editing in live visuals applications. First, we present a media manager that supports the user in both retrieval and utilization of automatically annotated digital media. The computer-assisted application of individual media items permits the interactive control of non-linear editing (NLE) of video in real-time. Second, we optimize the design process by introducing the design tree, which collects and organizes the artist’s work in an intuitive way. Design tree operations provide interactive high-level editing methods which allow for exploration, combination, reuse, and evolution of designs before and particularly during the performance. We examined the effectiveness of our techniques on numerous long-lasting live performances from which representative examples are demonstrated.

Tolerance-based feature transforms (TFTs) assign to each pixel in an image not only the nearest feature pixels on the boundary (origins), but all origins from the minimum distance up to a user-defined tolerance. In this paper, we compare four simple-to-implement methods for computing TFTs on binary images. Of these methods, the Fast Marching TFT and Euclidean TFT are new. The other two extend existing distance transform algorithms. We quantitatively and qualitatively compare all algorithms on speed and accuracy of both distance and origin results. Our analysis is aimed at helping practitioners in the field to choose the right method for given accuracy and performance constraints.

Quadrature filters serve for computing the local energy and local phase of a signal. Whereas for the one dimensional case quadrature filters are theoretically well founded, this is not the case for higher dimensional signal spaces. The monogenic signal (Felsberg and Sommer, 2001) based on the Riesz transformation has been shown to be a rotational invariant generalization of the analytic signal. A further generalization of the monogenic signal, the 2D rotational invariant quadrature filter (Köthe, 2003), has been shown to capture richer structures in images as the monogenic signal.

We present a generalization of the rotational invariant quadrature filter based on our steerable theory. Our approach includes the important case of 3D rotational invariant quadrature filters but it is not limited to any signal dimension and includes all transformation groups that own a unitary group representation.

Generalised Principal Component Analysis (GPCA) is a recently devised technique for fitting a multi-component, piecewise-linear structure to data that has found strong utility in computer vision. Unlike other methods which intertwine the processes of estimating structure components and segmenting data points into clusters associated with putative components, GPCA estimates a multi-component structure with no recourse to data clustering. The standard GPCA algorithm searches for an estimate by minimising a simple algebraic misfit function. The underlying constraints on the model parameters are ignored. Here we promote a variant of GPCA that incorporates the parameter constraints and exploits constrained rather than unconstrained minimisation of a statistically motivated error function. The output of any GPCA algorithm hardly ever perfectly satisfies the parameter constraints. Our new version of GPCA greatly facilitates the final correction of the algorithm output to satisfy perfectly the constraints, making this step less prone to error in the presence of noise. The method is applied to the example problem of fitting a pair of lines to noisy image points, but has potential for use in more general multi-component structure fitting in computer vision.

Ellipse detection is an important task in vision based systems because many real world objects can be described by this primitive. This paper presents a fast data driven four stage filtering process which uses geometric features in each stage to synthesize ellipses from binary image data with the help of lines, arcs, and extended arcs. It can cope with partially occluded and overlapping ellipses, works fast and accurate and keeps memory consumption to a minimum.

The research presented in this article is aimed at developing an automated imaging system for classification of tissues in medical images obtained from Computed Tomography (CT) scans. The article focuses on using multi-resolution texture analysis, specifically: the Haar wavelet, Daubechies wavelet, Coiflet wavelet, and the ridgelet. The algorithm consists of two steps: automatic extraction of the most discriminative texture features of regions of interest and creation of a classifier that automatically identifies the various tissues. The classification step is implemented using a cross-validation Classification and Regression Tree approach. A comparison of wavelet-based and ridgelet-based algorithms is presented. Tests on a large set of chest and abdomen CT images indicate that, among the three wavelet-based algorithms, the one using texture features derived from the Haar wavelet transform clearly outperforms the one based on Daubechies and Coiflet transform. The tests also show that the ridgelet-based algorithm is significantly more effective and that texture features based on the ridgelet transform are better suited for texture classification in CT medical images.

In this paper we present a new method for color segmentation of complex document images which can be used as a preprocessing step of a text information extraction application. From the edge map of an image, we choose a representative set of samples of the input color image and built the 3D histogram of the RGB color space. These samples are used to locate a relatively large number of proper points in the 3D color space and use them in order to initially reduce the colors. From this step an oversegmented image is produced which usually has no more than 100 colors. To extract the final result, a mean shift procedure starts from the calculated points and locates the final color clusters of the RGB color distribution. Also, to overcome noise problems, a proposed edge preserving smoothing filter is used to enhance the quality of the image. Experimental results showed the method’s capability of producing correctly segmented complex color documents while removing background noise or low contrast objects which is very desirable in text information extraction applications. Additionally, our method has the ability to cluster randomly shaped distributions.

This paper describes a new method for removing geometric distortion in images of submerged objects observed from outside shallow water. We focus on the problem of analyzing video sequences when the water surface is disturbed by waves. The water waves will affect the appearance of the individual video frames such that no single frame is completely free of geometric distortion. This suggests that, in principle, it is possible to perform a selection of a set of low distortion sub-regions from each video frame and combine them to form a single undistorted image of the observed object. The novel contribution in this paper is to use a multi-stage clustering algorithm combined with frequency domain measurements that allow us to select the best set of undistorted sub-regions of each frame in the video sequence. We evaluate the new algorithm on video sequences created both in our laboratory, as well as in natural environments. Results show that our algorithm is effective in removing distortion caused by water motion.

One of the remaining obstacles to a widespread introduction of industrial robots is their inability to deal with 3D objects in a bin that are not precisely positioned, i.e., the bin-picking problem. In this work we address the general bin-picking problem where a CAD model of the object to be picked is available beforehand. Structured light, in the form of Time Multiplexed Binary Stripes, is used together with a calibrated camera to obtain 3D data of the objects in the bin. The 3D data is then segmented into points of interest and for each a regional feature vector is extracted. The features are the Harmonic Shape Contexts. These are characterized by being rotational invariant and can in general model any free-form object. The Harmonic Shape Contexts are extracted from the 3D scene data and matched against similar features found in the CAD model. This allows for a pose estimation of the objects in the bin. Tests show the method to be capable of pose estimating partial-occluded objects, however, the method is also found to be sensitive to the resolution in the structured light system and to noise in the data.

The laws of gestalt-perception play an important role in human vision. Psychological studies identified similarity, good continuation, proximity and symmetry as important inter-object relations that distinguish perceptive gestalts from arbitrary sets of clutter objects. Particularly, symmetry and continuation possess a high potential in detection, identification, and reconstruction of man-made objects. This contribution focuses on coding this principle in an automatic production system. Such systems capture declarative knowledge. Procedural details are defined as control strategy for an interpreter. Often an exact solution is not feasible while approximately correct interpretations of the data with the production system are sufficient. Given input data and a production system the control acts accumulatively instead of reducing. The approach is assessment driven features any-time capability and fits well into the recently discussed paradigms of cognitive vision. An example from automatic extraction of groupings and symmetry in man-made structure from high resolution SAR-image data is given. The contribution also discusses the relations of such approach to the “mid-level” of what is today proposed as “cognitive vision”.

Subspace analysis such as the Principal Component Analysis (PCA) and Linear Discriminant Analysis (LDA) are widely used feature extraction methods for face recognition. However, since most of them employ holistic basis, local information can not be represented in the subspace. Therefore, in general, they cannot cope with the occlusion problem in face recognition. In this paper, we propose a new method that uses the two-dimensional principal component analysis (2D PCA) for occlusion invariant face recognition. In contrast to 1D PCA, 2D PCA projects a 2D image directly onto the 2D PCA subspace, and each row of the resulting feature matrix exhibits the distribution of corresponding row of the image. Therefore by classifying each row of the feature matrix independently, we can easily identify the locally occluded parts in a face image. The proposed occlusion invariant face recognition algorithm consists of two parts: occlusion detection and partial matching. To detect occluded regions, we apply a novel combined k-NN and 1-NN classifier to each row of the feature matrix of the test face. And for partial matching, similarity between feature matrices is evaluated after removing the rows identified as the occluded parts. Experimental results on AR face database demonstrate that the proposed algorithm outperforms other existing approaches.

In this paper, we present an algorithm to detect and track both frontal and side faces in video clips. By means of both learning Haar-like features of human faces and boosting the learning accuracy with InfoBoost algorithm, our algorithm can detect frontal faces in video clips. Furthermore, we map these Haar-like features to a 3D model to create the classifier that can detect both frontal and side faces. Since it is costly to detect and track faces using the 3D model, we project Haar-like features from the 3D model to a 2D space in order to generate various face orientations. By using them, we can detect even side faces in real time by only learning frontal faces.

Many algorithms in computer vision operate with directions, i. e. with representations of 3D-points by ignoring their distance to the origin. Even though minimal parametrizations of directions may contain singularities, they can enhance convergence in optimization algorithms and are required e. g. for accumulator spaces in Hough transforms. There are numerous possibilities for parameterizing directions. However, many do not account for numerical stability when dealing with noisy data. This paper gives an overview of different parametrizations and shows their sensitivity with respect to noise. In addition to standard approaches in the field of computer vision, representations originating from the field of cartography are introduced. Experiments demonstrate their superior performance in computer vision applications in the presence of noise as they are suitable for Gaussian filtering.

This work aims at defining a new method for matching correspondences in stereoscopic image analysis. The salient aspects of the method are -an explicit representation of occlusions driving the overall matching process and the use of neural adaptive technique in disparity computation. In particular, based on the taxonomy proposed by Scharstein and Szelinsky, the dense stereo matching process has been divided into three tasks: matching cost computation, aggregation of local evidence and computation of disparity values. Within the second phase a new strategy has been introduced in an attempt to improve reliability in computing disparity. An experiment was conducted to evaluate the solutions proposed. The experiment is based on an analysis of test images including data with a ground truth disparity map.

Recently, researchers proposed deterministic and statistical appearance-based 3D head tracking methods which can successfully tackle the image variability and drift problems. However, appearance-based methods dedicated to 3D head tracking may suffer from inaccuracies since these methods are not very sensitive to out-of-plane motion variations. On the other hand, the use of dense 3D facial data provided by a stereo rig or a range sensor can provide very accurate 3D head motions/poses. However, this paradigm requires either an accurate facial feature extraction or a computationally expensive registration technique (e.g., the Iterative Closest Point algorithm). In this paper, we improve our appearance-based 3D face tracker by combining an adaptive appearance model with a robust 3D-to-3D registration technique that uses sparse stereo data. The resulting 3D face tracker combines the advantages of both appearance-based trackers and 3D data-based trackers while keeping the CPU time very close to that required by real-time trackers. We provide experiments and performance evaluation which show the feasibility and usefulness of the proposed approach.

In this paper, we propose a 3D tracking method which integrates two kinds of 2D feature tracking techniques. Our tracker searches 2D-3D correspondences used to estimate camera pose on the next frame from detected straight edges and projected 3D-CAD model on the current frame, and tracks corresponding edges on the consecutive frames. By tracking those edges, our tracker can keep correct correspondences even when large camera motion occurs. Furthermore, when the estimated pose seems incorrect, our tracker brings back to the correspondences of the previous frame and proceeds tracking of corresponding edges. Then, on the next frame, our tracker estimates the pose from those correspondences and can recover to the correct pose.

Our tracker also detects and tracks corners on the image as 2D feature points, and estimates the camera pose from 2D-3D line segment correspondences and the motions of feature points on the consecutive frames. As the result, our tracker can suppress the influence of incorrect 2D-3D correspondences and can estimate the pose even when the number of detected correspondences is not enough.

We also propose an approach which estimates both the camera pose and the correspondences. With this approach, our tracker can estimate the pose and the correspondence on the initial frame of the tracking.

From experimental results, we confirmed our tracker can work in real-time with enough accuracy for various applications even with a less accurate CAD model and noisy low resolution images.

This paper presents a new vision-based system for motion correction in functional-MRI experiments. fMRI is a popular technique for studying brain functionality by utilizing MRI technology. In an fMRI experiment a subject is required to perform a task while his brain is scanned by an MRI scanner. In order to achieve a high quality analysis the fMRI slices should be aligned. Hence, the subject is requested to avoid head movements during the entire experiment. However, due to the long duration of such experiments head motion is practically unavoidable. Most of the previous work in this field addresses this problem by extracting the head motion parameters from the acquired MRI data. Therefore, these works are limited to relatively small movements and may confuse head motion with brain activities. In the present work the head movements are detected by a system comprised of two cameras that monitor a specially designed device worn on the subject’s head. The system does not depend on the acquired MRI data and therefore can overcome large head movements. Additionally, the system can be extended to cope with inter-block motion and can be integrated into the MRI scanner for real-time updates of the scan-planes. The performance of the proposed system was tested in a laboratory environment and in fMRI experiments. It was found that high accuracy is obtained even when facing large head movements.

Dynamic textures are sequences of images of moving scenes that show stationarity properties in time. Eg: waves, flame, fountain, etc. Recent attempts at generating, potentially, infinitely long sequences model the dynamic texture as a Linear Dynamic System. This assumes a linear correlation in the input sequence. Most real world sequences however, exhibit nonlinear correlation between frames. In this paper, we propose a technique of generating dynamic textures using a low dimension model that preserves the non-linear correlation. We use nonlinear dimensionality reduction to create an embedding of the input sequence. Using this embedding, a nonlinear mapping is learnt from the embedded space into the image input space. Any input is represented by a linear combination of nonlinear bases functions centered along the manifold in the embedded space. A spline is used to move along the input manifold in this embedded space as a similar manifold is created for the output. The nonlinear mapping learnt on the input is used to map this new manifold into a sequence in the image space. Output sequences, thus created, contain images never present in the original sequence and are very realistic.