Vol. 11 (2002): Abstracts of Papers
Machine GRAPHICS & VISION, Vol. 11 (2002), No. 1:
Csonka F., Szirmay-Kalos L., Antal G.:
Generalized multiple importance sampling for Monte-Carlo global illumination.
MGV vol. 11, no. 1, 2002, pp. 3-20.
The global illumination or transport problems can be considered as a sequence of integrals, while their Monte-Carlo solutions - as different sampling techniques. Multiple importance sampling takes advantage of different sampling strategies, and combines the results obtained with them to establish a quasi-optimal sampling for Monte-Carlo quadratures. This offers a combination of totally different global illumination algorithms which preserves their strengths. However, implementation of this general concept poses two problems. The solution of the global illumination problem does not contain a single integral, but a sequence of integrals that are approximated simultaneously. One objective of this paper is to generalize the fundamental theory of multiple importance sampling to sequences of integrals. The cost of the computation and the contribution of a single integral to the final result vary. On the other hand, different methods compute a sample with different computational burdens, which should also be taken into account. This paper attacks this problem and introduces the concept of computational cost in multiple importance sampling. The theoretical results are used to combine bi-directional path tracing and ray-bundle based stochastic iteration. We conclude that the combined method preserves the high initial speed of stochastic iteration, but can also accurately compute the specular light paths through bi-directional path tracing.
Key words: multiple importance sampling, stochastic iteration, random walk.
The principles of using the equigradient and reflection lines as the tools of surface continuity diagnosis.
MGV vol. 11, no. 1, 2002, pp. 21-36.
The paper presents new theorems about characteristic curves on the surface used as a shape smoothness diagnosis tool. First, general principles of examination of characteristic curves, treated as contour lines of a shape function, are presented. Two subsequent sections deal with properties of two most popular characteristic curves: equigradient lines and reflection lines. The theorems presented there are a theoretical background for evaluation of the surface continuity via of examination of these type of lines.
Key words: shape evaluation, surface continuity, characteristic curves, equigradient lines, reflection lines, geometric data quality, CAD/CAM system.
Triangulation of NURBS surfaces through adaptive refinement.
MGV vol. 11, no. 1, 2002, pp. 37-52.
This paper discusses adaptive approach to the problem of automatic triangulation of NURBS surfaces. The algorithm presented here generates triangulation through the so-called adaptive refinement - a process carried out entirely in a parametric space with a variable triangle size adjusted to the local curvature of the surface, so that the imposed approximation error is not exceeded. The mesh is generated as an adaptive one right from the start, and no further decimation is required. Sample triangulations generated by the algorithm as well as a discussion of its computational complexity are included. Running times of the computer implementation confirm that an average computational cost of the algorithm is O(N), with N denoting the total number of triangles in the final mesh.
Key words: tesselation of surface, NURBS, adaptive triangulation.
Zhang Y., Prakash E.C., Sung E.:
Anatomy-based 3D facial modeling for expression animation.
MGV vol. 11, no. 1, 2002, pp. 53-76.
In this paper we propose a new hierarchical 3D facial model that conforms to the human facial anatomy for realistic facial expression animation. The facial model has a hierarchical biomechanical structure, incorporating a physically-based approximation to facial skin tissue, a set ofanatomically motivated facial muscle actuators and underlying skull structure. The deformable skin model has multi-layer structure to approximate different types of soft tissue. It takes into account the nonlinear stress-strain relationship of the skin and the fact that soft tissue is almost incompressible. Different kinds of muscle models have been developed to simulate the distribution of the muscle force on the skin due to muscle contraction. By the presence of the skull model, our facial model takes advantage of both more accurate facial deformation and the consideration of facial anatomy during the interactive definition of facial muscles. Under the muscular force, the deformation of the facial skin is evaluated by solving the governing dynamic equation numerically. To improve computational efficiency, we use a localized, semi-implicit integration method which allows a larger time step to be taken in the simulation while retaining stability. The dynamic facial animation algorithm runs at an interactive rate with flexible and realistic facial expressions to be generated.
Key words: facial animation, anatomy-based facial model, hierarchical structure, mass-spring-damper system, semi-implicit integration method.
Segmentation of MRI trabecular-bone images using network of synchronised oscillators.
MGV vol. 11, no. 1, 2002, pp. 77-99.
Segmentation of textured images, a very important aspect of visual perception, remains still a challenging task for many image analysis problems. This paper presents a recently emerged segmentation method based on the temporary correlation theory. It proposes an explanation of visual scene analysis performed by human brain. Based on this theory, a network of locally connected synchronised oscillators is proposed for the image segmentation task. This oscillator network can be realised as a VLSI chip, providing very fast image segmentation. For texture description, the Gaussian Markov Random Field model widely used in many texture analysis tasks, is applied. The proposed method is applied to segment MRI images of human foot cross-section in order to detect bone structure. This analysis could be useful in osteoporosis diagnosis, allowing further evaluation of bone microarchitecture. The efficiency of the GMRF approach in bone texture modelling is demonstrated. The oscillator network method is compared with an ANN-based classifier. The segmentation results using both methods are presented and discussed.
Key words: image segmentation, oscillator network, GMRF model.
Nieniewski M., Serneels R.:
Segmentation of spinal cord images by means of watershed and region merging together with inhomogeneity correction.
MGV vol. 11, no. 1, 2002, pp. 101-122.
The paper presents a morphological method for segmentation of high field Magnetic Resonance (MR) images of the human spinal cord and extraction of the gray matter mask. These images are of low quality and poor contrast. The inhomogeneity of brightness in the image is usually more pronounced than the difference in brightness between the gray matter and the white matter. Due to this inhomogeneity, it is very hard to use watershed segmentation for automatic extraction of the gray matter, and what remains is manual pointing out of a hundred or more regions belonging to the gray matter. However, as shown in the paper, by using the White Top Hat (WTH) transform with a large structuring element, one can correct the images, significantly reducing the inhomogeneity and appropriately modifying individual region statistics. In particular, watershed segmentation is carried out on the original image, whereas region statistics used for region merging are calculated from the corrected image. Then the extraction of the gray matter mask is carried out in a semi-automatic way, with the user pointing out the first region belonging to the gray matter area, and the program selecting subsequent neighboring regions based on the statistics of the regions. The method was tested on images coming from different cross-sections of the spinal cord, and the results indicate that the process of extracting the gray matter mask has been significantly speeded up and improved.
Key words: spinal cord, extraction of gray matter, correction of MR images, watershed, region merging.
Leski J., Henzel N.:
Minimum hypervolume clustering algorithm.
MGV vol. 11, no. 1, 2002, pp. 123-132.
The Hard C-Means (HCM) clustering method is one of the most popular clustering methods based on minimization of a criterion function. However, one of the greatest disadvantage of this method is that the performance of the HCM is good only when the data set contains clusters that have approximately the same size and shape. The paper is devoted to a new clustering algorithm, called minimum hypervolume clustering (MHC), that seeks C-hyperellipsoids with the smallest hypervolumes that enclose all the data points. Performances of the new clustering algorithm are experimentally verified using synthetic and real life data containing clusters with different sizes and orientations.
Key words: C-means clustering, HCM, isodata algorithm.
Machine GRAPHICS & VISION, Vol. 11 (2002), No. 2/3:
Special Issue on Color Image Processing and its Applications.
Special Issue Editor: Henryk Palus.
Guest Editorial: Latest Results in Color Image Processing and its Applications.
MGV vol. 11, no. 2/3, 2002, pp. 135-137.
Chernov V. M.:
Some FFT-like algorithms for RGB-spectra calculation.
MGV vol. 11, no. 2/3, 2002, pp. 139-151.
The paper deals with some new algorithms for "overlapped" calculation of 1D and 2D DFT spectra of a multi-channel signal. The algorithms' computational complexity is decreased via a fast calculation of an auxiliary transform that takes values in special algebraic structures: the group algebra of a quaternion units group and the algebra associated with integral Hurwitz quaternions.
Key words: FFT, overlapped algorithms, color images.
Rizzi A., Marini D., De Carli L.:
LUT and multilevel brownian retinex colour correction.
MGV vol. 11, no. 2/3, 2002, pp. 153-168.
Retinex, a model of human color vision suitable for unsupervised chromatic equalization, due to Land and McCann, is receiving a renewed interest after several years. Different versions have been developed so far, and it has been used for various applications. Most of the implementations skip the classical random paths approach because of the high frequency chromatic noise it introduces. To solve the noise problem, avoiding the increase of paths number and without substituting the random paths approach, we present in this paper two new retinex versions: one based on a look-up table transformation, and another based on multilevel image decomposition. These versions strongly decrease the dependency of the computed pixel value on the path randomness, eliminating in this way a great part of the chromatic noise.
Key words: Retinex, cromatic equalization, color constancy.
Cucchiara R., Grana C., Seidenari S., Pellacani G.:
Exploiting color and topological features for region segmentation with recursive fuzzy c-means.
MGV vol. 11, no. 2/3, 2002, pp. 169-182.
In this paper we define a novel approach to image segmentation into regions which focuses on both visual and topological cues, namely color similarity, inclusion and spatial adjacency. Many color clustering algorithms have been proposed in the past for skin lesion images but none exploits explicitly the inclusion properties between regions. Our algorithm is based on a recursive version of fuzzy c-means (FCM) clustering algorithm in the 2D color histogram constructed by Principal Component Analysis (PCA) of the color space. The distinctive feature of the proposal is that recursion is guided by evaluation of adjacency and mutual inclusion properties of extracted regions; then, the recursive analysis addresses only included regions or regions with a not-negligible size. This approach allows a coarse-to-fine segmentation which focuses attention on the inner parts of the images, in order to highlight the internal structure of the object depicted in the image. This could be particularly useful in many applications, especially in biomedical image analysis. In this work we apply the technique to segmentation of skin lesions in dermatoscopic images. It could be a suitable support for diagnosis of skin melanoma, since dermatologists are interested in analysis of spatial relations, symmetrical positions and inclusion of regions.
Key words: PCA, fuzzy C-means, clustering, color segmentation, topological features, dermatoscopic images.
Bing C., Nanning Z., Ying W., Yongping Z., Zhihua Z.:
Color image segmentation based on edge-preservation smoothing and soft C-means clustering.
MGV vol. 11, no. 2/3, 2002, pp. 183-194.
A new approach to color image segmentation is demonstrated here. The color image, which is usually in the RGB space, is translated into the CIE(Lab) color space. The three components are smoothed using a variation-based approach. By minimizing an energy functional with a non-convex regular function, we can get a smoothed image. During the iteration, the edges of the image are preserved. A soft C-means clustering algorithm, which is an improvement on the hard C-means algorithm, is employed to segment them after smoothing. This algorithm overcomes the problem of dependence on the initializations. Finally, an experiment is given to show the effectiveness and robustness of the method.
Key words: color image, image segmentation, edge-preservation smoothing, soft C-means clustering.
Palm C., Lehmann T. M.:
Classification of color textures by gabor filtering.
MGV vol. 11, no. 2/3, 2002, pp. 195-219.
A novel approach to Gabor filtering of color textures is introduced. It is based on the complex chromatic Fourier transform. Complex colors are derived from the HSL color space representing intensity-independent color textures. Additionally, a novel Gabor texture feature for the grayscale as well as the color domain is proposed. It relies on local phase changes characterizing the homogeneity of a texture in the spatial frequency domain. Several classification experiments on two image databases are performed to study the texture features according to different color spaces and Gabor filter bank variants. The color features show significantly better results than the grayscale features. Although they are completely intensity-independent, the features on the basis of the complex color space show satisfying results. The RGB based features, where color and intensity work inherently together, perform best. Especially the local phase change measure supplements the known amplitude measure appropriately.
Key words: Gabor filter, color texture, classification, color Fourier transform.
Object recognition using a multi-spectral imaging system.
MGV vol. 11, no. 2/3, 2002, pp. 221-240.
A spectral-imaging system and algorithms for identifying objects in a natural scene based on surface-spectral reflectances are described. The imaging system is composed of a liquid-crystal tunable filter, a monochrome CCD camera, and a personal computer. The tunable filter is convenient for spectral imaging because the wavelength band can be changed easily and electronically. It is described how we can recover the surface-spectral reflectances of natural objects by using the multi-spectral imaging system. Algorithms are presented for estimating both spectral functions of the illuminant spectral-power distribution and surface-spectral reflectance from the spectral image data. Moreover, effective image processing procedures are proposed for highlight extraction and region segmentation. The segmentation is based on a pixel classification method using only the maximum sensor outputs. The overall performance of the proposed imaging system and algorithms is examined in an experiment using natural products, in which 21 spectral images are acquired in the wavelength range of 450-650 nm.
Key words: multi-spectral imaging, object recognition, surface-spectral reflectance, spectral-imaging system, image segmentation, color.
Ho K. I-J., Chen T.-S., Cheng C-Y.:
An efficient face detection method using skin-color discovering and chain code.
MGV vol. 11, no. 2/3, 2002, pp. 241-256.
In this paper, we propose a method to locate human faces in color images. For color images, the skin color is an important key feature for human face detection. Thus, this paper applies skin color information to segmented human face areas. First, we reduce the size of the color image, hold its ratio, and detect skin color pixels in the resized image based on the properties of skin color. Next, our method employs the detected pixels and chain code to locate continuous areas. Finally, we check the width and the height of each located area, and filter out the non-facial ones. The remaining areas are the human face regions. To fully explore the efficiency and effectiveness of the proposed method, we conduct a lot of experiments on the test images used in other papers. The experimental results show that both the false positive and false negative rates are either equal to or better than those obtained in previous research results. Moreover, in most of experiments, the processing time of our method is shorter.
Key words: face detection, face segmentation, skin color, chain code.
Muselet D., Macaire L., Postaire J.-G.:
A new approach to color person image indexing and retrieval.
MGV vol. 11, no. 2/3, 2002, pp. 257-283.
In the context of image indexing for the purpose of retrieval, colored object recognition methods tend to fail when the illumination of the objects varies from an image to another. A new approach to indexing images of persons is proposed, which copes with the variations of the lighting conditions. We assume that illumination changes can be described using a simple linear transform. For comparing two images, we transform the colors of the target one according to the colors of the query one by means of an original color histogram specification based on color invariant evaluation. For the retrieval purpose, we evaluate invariant color signatures of the query image and the transformed target image through the use of color co-occurrence matrices. Tests on real images are very encouraging, with substantially better results than those obtained with other well-established indexing and retrieval schemes.
Key words: color, illumination, invariant features, indexing, retrieval, highlights, shadows, color co-occurrence matrices.
A fast hue-based colour image indexing algorithm.
MGV vol. 11, no. 2/3, 2002, pp. 285-295.
In content-based image indexing and retrieval (IIR), hue component histograms of images are widely used for indexing the images in an image database. The aim is to retrieve all colour images whose distances to the query image in terms of hue distributions do not exceed some threshold value. Edit distance has been successfully used as a similarity measure. Our earlier O(b2) algorithm computing the edit distance between two angular histograms, where b is the number of bins in the hue histogram, tends to be too slow for users to wait for the outputs when applied to every image in the database. For this reason, we design two filtration functions that quickly eliminate most colour images from consideration as possible outputs, and exact edit distances are only computed for the remaining images. We are still guaranteed to find all similar hue distributions, and the filtration technique gives significant speeds-ups.
Key words: colour image, filtration, hue, image indexing and retrieval, similarity measure.
Skarbek W., Kukielka G.:
Optimal intervals for fuzzy categories of color temperature with application to image browsing.
MGV vol. 11, no. 2/3, 2002, pp. 297-310.
This paper presents the results of experiments for a color temperature browsing descriptor. We consider the problem of the optimal conversion of an objective value (color temperature) into a subjective category (Hot, Warm, Neutral, and Cold). The situation where subjective categories are based on an objective object attribute appears to be common while comparing interpretation of human sensors with physical sensors. The proposed optimal procedure for segmenting the color temperature partition into four disjoint intervals and the experimental results are described.
Key words: color temperature, optimal intervals, MPEG-7.
Optimised directional distance filter.
MGV vol. 11, no. 2/3, 2002, pp. 311-326.
In this paper, a new adaptive directional distance filter especially for the impulse noise suppression in color images is provided. The proposed method takes advantage from the optimal filtering situation when only the affected samples are estimated, whereas noisy image points are passed to a filter output without change. For that reason, the proposed method is based on switching between the identity filter (no smoothing) and the directional distance filter that provides a maximum amount of the smoothing. In order to achieve the most precise control of the proposed method, three center-weighted directional distance filters are utilised to determine a parameter compared with a threshold value. This simple comparison serves as a switching control. After the optimisation of the threshold, it will be shown that the proposed method achieves a significant improvement of the filter performance in comparison with standard vector filter classes for a wide range of impulse noise corruption.
Key words: color images, vector order-statistics, distance function, weight vector, adaptive filter.
Adaptive modification of the vector median filter.
MGV vol. 11, no. 2/3, 2002, pp. 327-350.
In this paper we address the problem of impulsive noise reduction in color images. A new, simple but efficient, filter for noise attenuation is introduced, and its relationship with commonly used techniques is investigated. The computational complexity of the new filter is shown to be lower than that of the Vector Median Filter (VMF). The experiments indicate that the new filter outperforms the VMF, as well as other basic procedures used in color image processing for elimination of impulsive noise.
Key words: image processing, noise filtering, restoration, image quality.
Baranyai L., Szepes A.:
Analysis of fruit and vegetable surface color.
MGV vol. 11, no. 2/3, 2002, pp. 351-361.
Changes of color on the surfaces of tomatoes, mushrooms and apples were measured with digital image processing techniques. Texture analysis methods were applied to identify the stage of ripeness and defects, such as mechanical injuries and microbiological infection. Distributions of red, green, and blue color components and intensity values were shown by histograms. Differences in intensities - in the directions of 0o, 45o, 90o, and 135o - were also collected. First-order statistical parameters and coordinates of polar quality points for sum and difference histograms were calculated and evaluated. Classification powers of different color signals were compared.
Key words: surface texture, sum and difference histograms, Polar Qualification System (PQS).
Chambah M., Besserer B., Courtellemont P.:
Latest results in digital color film restoration.
MGV vol. 11, no. 2/3, 2002, pp. 363-395.
Motion picture is not only a theatrical art but also a vivid record of past life. Unfortunately, almost all color films made since the 1950s are subject to fading that can be arrested only by storing prints at very low temperatures. Photochemical restoration of faded motion prints is impossible. Nowadays, the improvement of computer power allows us to expect digital restoration of motion pictures at acceptable rates. In this paper we present two original techniques for restoring faded color image sequences: an assisted and an automatic one. The first method consists in choosing a "reference image" from the sequence, after removing side absorptions introduced by the scanning process, adjusting its colors and contrast, then propagating the correction performed to the whole image sequence. The second method consists in reviving the colors of the image (color enhancement), then balancing them.
Key words: digital film restoration, color fading, color correction, color mapping, selection of points of interest, automatic color balance, color constancy, saturation enhancement.
Machine GRAPHICS & VISION, Vol. 11 (2002), No. 4:
Baldassarri S., Gutierrez D., Seron F.:
Modelling objects with changing shapes: a survey.
MGV vol. 11, no. 4, 2002, pp. 399-430.
The great number of object modelling computer techniques that already exist and the new ones that are continuously appearing are the result of a multidisciplinary exchange of ideas. Within this area, objects with changing shapes are inherently more difficult to model than rigid objects. Our main goal has been to provide a classification of the algorithms involved in the modelling of objects that can be as diverse as water, clothes, faces, ... The classification has been made from the starting point of inorganic and organic categories. Inorganic objects are classified according to their material state while the organic ones are classified according to the realm they belong to. Within each category, works are generally presented in chronological order, providing an extensive bibliography.
Key words: object modelling, changing shapes, hair and fur, cloth, viscous matter, water, gases and smoke, clouds, fire, plants, plants-surrounding relation, bodies, internal organs, faces.
Computing intersections of rational patches.
MGV vol. 11, no. 4, 2002, pp. 431-454.
A procedure of finding the intersection of rational patches is developed. It consists of adaptive division of the patches, convex hull test to reject pairs of disjoint pieces, normal vectors test that verifies some condition ensuring a simple enough shape of the pieces, computing end points of common arcs (described in a separate paper) and computing other points using the Newton method with pseudo-inversion. Some issues concerning the reliability of this procedure are discussed.
Key words: Rational Bézier patches, intersections of surfaces.
Solving systems of algebraic equations.
MGV vol. 11, no. 4, 2002, pp. 455-473.
Numerical procedures of solving a system for algebraic equations usually consist of a part that localizes the solutions and a part that computes their accurate approximations. The localization is often based on the convex hull property of the Bernstein-Bézier representation of the equations. In the procedure described in this paper, the convex hull test is complemented with another test, which significantly improves the efficiency of the procedure.
Key words: Bernstein polynomials, rational Bézier curves and patches, free-form deformation, de Casteljau algorithm, convex hull property.
Wu X., Li D.:
Triangle mesh compression and simplification.
MGV vol. 11, no. 4, 2002, pp. 475-488.
Triangular meshes are widely used in computer graphics fields, such as GIS, CAD and VR. Very complex models, with hundreds of thousands of faces, are easily produced by current CAD tools, automatic acquisition devices, or by fitting isosurfaces out of volume datasets. Many geometric datasets require a large amount of disk space. One of the solutions is to compress those large geometric data sets with geometric compression algorithms. On the other hand, a highly complex data representation is not always necessary. For example, a full size model is not required for generation of each frame of an interactive visualization. This has led to substantial research on the surface mesh simplification. Unfortunately, however, nearly all the methods only deal with one aspect above, either mesh compression or mesh simplification. We present a method to deal with both issues. It breaks down the triangle meshes into a set of triangle strips and vertex chains. Following that, inter-triangle-strip simplification and intra-triangle-strip simplification are used to simplify the meshes. The method can not only compress the mesh geometry datasets for hard disk storage, but also simplify the meshes for the purposes of rendering and displaying. The results show the validity and efficiency of our method.
Key words: triangular meshes, mesh compression, mesh simplification, triangle strip.
Simplification of 3D head mesh acquired from laser scanner.
MGV vol. 11, no. 4, 2002, pp. 489-498.
Complex triangle meshes arise extensively in computer graphics. Such meshes greatly exceed the processing power of modern computer hardware and need to be simplified. The purpose of this paper is to simplify a 3D color human head mesh acquired from a 3D laser scanner. It is more important to keep the boundaries and quality of the sense organs which are the region of interest, while it is reasonable to simplify other features of the head aggressively, such as hair, face and neck. Based on these heuristics, we present a novel vertex merging mesh simplification algorithm based on region segmentation. The algorithm can be divided into two stages: segmentation and simplification. First, the 3D color head mesh is segmented into different head parts with respect to both geometry and attributes, then vertices are classified into region-inner vertices and region-boundary vertices. Second, iterative vertex merging is applied using region-weighted error metric in order to implement controllable simplifications. Results of several experiments are shown, demonstrating the potential of our method for a 3D color head mesh. Also, our method is resistant to noise in practical applications.
Key words: mesh simplification, level of detail, 3D color head mesh, laser scanner.
El-Bakry H. M.:
Human iris detection using fast cooperative modular neural nets and image decomposition.
MGV vol. 11, no. 4, 2002, pp. 499-512.
In this paper, a combination of fast and cooperative modular neural nets to enhance the performance of the detection process is introduced. I have applied such approach successfully to detect human faces in cluttered scenes. Here, this technique is used to identify human irises automatically in a given image. Neural nets are used to test whether a window of 20x20 pixels contains an iris or not. The major difficulty in the learning process comes from the large database required for iris/non-iris images. A simple design for cooperative modular neural nets is presented to solve this problem by dividing these data into three groups. Such division results in reduction of computational complexity and thus decreasing the time and memory needed during the test of an image. Simulation results for the proposed algorithm show a good performance. Moreover, a powerful system for personal identification using iris detection is presented. Furthermore, faster iris detection is obtained through image decomposition into many sub-images and applying cross correlation in the frequency domain between each sub-image and the weights of the hidden layer.
Key words: personal identification, fast iris dection, modular neural nets.
Segmentation method of digital images based on the evolutionary strategy.
MGV vol. 11, no. 4, 2002, p. 513.
Contents of volume 11, 2002