Vol. 7 (1998):
  Abstracts of Papers

6 (1997)	main	8 (1999)

Nos. 1/2: Special Issue: Proc. 5th GKPO'98 Conference,
No. 3,
No. 4: Special Issue on Medical Image Analysis.

Machine GRAPHICS & VISION, Vol. 7 (1998), Nos. 1/2:

Wojdala A., Gruszewski M., Dudkiewicz K., Donotek M.:
Real-time depth-of-field algorithm for virtual studio.
MGV vol. 7, nos. 1/2, 1998, pp. 5-14.
[Paper nominated for the Best Paper Award.]

Since the beginning of realistic image synthesis, depth of field was considered an important, though computationally expensive factor enhancing the realism of computer generated images. Introduction of virtual reality techniques created the demand for this effect to be at least interactive. This paper describes physically-based, real-time depth of field algorithm, addressing the needs of even more demanding application - virtual TV studio.

Reginski M., Stepien C.:
The method of animation of a growing spruce with seasonal model changes.
MGV vol. 7, nos. 1/2, 1998, pp. 15-26.

This paper describes an algorithm which generates a model of a tree in different moments of it's life. The algorithm, in opposition to those already known, enables to get the model in time period shorter than a year. Therefore it is possible to make an animation of a growing tree including seasonal changes in its appearance. A morphing method was used as a base of this animation. Necessary transformations of a sequence of models are presented in order to adapt these models to the standard of the morphing method.
Key words: botanical tree, animation, morphing, simulation of the growing process.

Kobus K.:
Fast animation of turbulent fog.
MGV vol. 7, nos. 1/2, 1998, pp. 27-40.

This paper presents a method of fast animation of turbulent fog phenomena. The high realism and interactive frame rates are achieved due to use of spectral theory of turbulence and visualisation in post processing.

Wcislo R., Kitowski J., Moscinski J.:
Animation of group of elastic objects based on distributed physical simulation.
MGV vol. 7, nos. 1/2, 1998, pp. 41-48.

The paper presents the overview of a computer system for performing animations of a set of solids and (optionally) a liquid medium. The animation is driven by the simulation based on physical laws to ensure the maximum reality.
Key words: multi-body animation, molecular dynamics, cellular automata, distributed simulation.

Olenski R., Radziszewski P.:
Real-time rendering and animation of mirages.
MGV vol. 7, nos. 1/2, 1998, pp. 49-64.

The document presents a method that can be used to visualize a mirage phenomenon using a "conventional" polygonal renderer. An algorithm of the calculation of the scene reflection in the mirage is shown, with its major parts: preselection of the mirage surfaces, mirage polygons and scene polygons and calculation of the modified viewing frustum. Approaches to the mirage animation are also discussed. Method presented here allows for faster rendering process, in comparison to well-known ray-tracing methods, and thus can be easier used in applications that require fast image generation times, e.g. in flight simulators.

Kasprzak J., Raczkowski J.:
Modelling a wind field effecting a smoke.
MGV vol. 7, nos. 1/2, 1998, pp. 65-74.

The visual simulation of natural phenomena is a challenge problem in computer graphics. In the paper a simplified method of the wind field modelling is presented. The method is based on a discrete volume space where vectors of the field are defined. The wind field is used for animation of smoke. The smoke density is transferred between voxels in space due to wind vectors in subsequent frames.
Key words: modelling natural phenomena, animation, discrete volume space, wind, smoke.

Karpouzis K., Votsis G., Tsapatsoulis N., Kollias S.:
Compact 3D model generation based on 2D views of human faces: application to face recognition.
MGV vol. 7, nos. 1/2, 1998, pp. 75-85.

A face recognition and synthetic-natural hybrid coding tool involving frontal and profile views is presented in this paper. The tool utilizes the above mentioned 2D images - upon which certain protuberant points are automatically detected - and adapts a generic 3D head model (polygon mesh) according to the predetermined information gained by the available views. This mesh provides shape information which - combined with texture information - is important for the robustness of a recognition system. The main advantage of the proposed approach is its ability to overcome constraints raised from arbitrary variations in scale, rotation and orientation, which are dominant deterioration factors in the identification task. Besides the face recognition aspect, applications which involve geometry transmission, such as teleconferencing, can take advantage of the proposed algorithm's ability to parametrically describe a complex organic model, such as a human head.
During the texture map creation process, issues related to the luminance differences and rotation variance between the available views, are successfully dealt with. Regarding the adaptation of the polygon topology of the 3D model, we apply a set of localized transformations, in order to preserve the continuity of the human head surface. Besides this, the problem of the minimum organic model representation required is addressed. The aspect under which this issue is verged upon, is that of the solution of a trade-off problem between low computational complexity and high approximation quality.
Key words: 3D face modeling, automated feature extraction, geometry compression.

Bartkowiak M., Domanski M.:
An efficient technique for high-compression of chrominance data.
MGV vol. 7, nos. 1/2, 1998, pp. 87-97.
[Paper nominated for the Best Paper Award.]

The paper describes an original technique to encode chrominance. We assume that the luminance is encoded entirely independently from chrominance. Nevertheless the chrominance coder and decoder use the reconstructed luminance in order to exploit the mutual correlation between the luminance and the chrominance components. The experimental results prove usefulness of the technique for image coding with high compression ratios.
Key words: color, chrominance, video coding, very low bitrate.

Jozwik A., Chmielewski L., Sklodowski M., Cudny W.:
A parallel net of (1-NN, k-NN) classifiers for optical inspection of surface defects in ferrites.
MGV vol. 7, nos. 1/2, 1998, pp. 99-112.

The challenging task of optical inspection of surface defects in ferrite cores has been successfully approached with a set of methods. In this paper the attention is paid to the k Nearest Neighbours classifier developed for the system. A parallel net of two-decision classifiers is presented. The combination of the 1-NN and k-NN rules reduces the training time. A great part of computations is restricted to the class overlap area. The classification quality is significantly improved if a separate feature selection for each of the component classifiers is done. A dramatic improvement of classification speed obtained by reference patterns sets reduction for component classifiers is vital, as in the considered task the classifier is used for recognition of pixels. The proposed modifications of the classifier are of general usefulness for pattern recognition. The presented quality inspection system can be applied to various defect detection tasks.
Key words: statistical pattern recognition, nonparametric methods, k-NN rules, parallel classifiers, quality inspection, ferrite cores.

Doulamis N., Doulamis A., Kollias S.:
A dynamically trained neural network for machine vision applications.
MGV vol. 7, nos. 1/2, 1998, pp. 113-123.

A dynamically trained neural network is proposed in this paper proper for adapting the network performance to non stationary image or video inputs. The scheme includes, on one hand, a retrieval mechanism which selects the most appropriate network from the system memory and, on the other hand, a weight perturbation procedure which adapts the network weights to the current condition. If no suitable network exists in memory, new weights and network structure are created and then stored for future use. Experimental results are provided indicating the good performance of the proposed system to computer and machine vision applications.
Key words: neural networks, image processing, adaptive training, non stationary inputs.

Furtak J.:
Camera calibration utilising controlled translation.
MGV vol. 7, nos. 1/2, 1998, pp. 125-134.

This paper presents camera calibration algorithm based on the same landmarks observed by camera in different locations. The basic idea of algorithm is recurrent using of intermediary results. This feature makes the knowledge accumulation during calibration process possible. Algorithm was verified experimentally. The experiment realisation method and received results are described.

Kulikowski J.L.:
Computer-aided analysis of serial images.
MGV vol. 7, nos. 1/2, 1998, pp. 135-149.

A concept and basic procedures of computer analysis of serial images (ASI) stored in image databases (IDB) is described. An ASI is considered as a series of computer procedures recognising some relations among image-records stored in IDB. The relations can be described both on some vectors of parameters assigned to the records and on the images themselves. Three basic groups of relations are considered: similarity, ordering and some higher-order relations described as hyperrelations of the MATCH - and SPREAD-type. Special attention also has been paid to the semiordering of image-records based on the concept of semiordered linear vector spaces (Kantorovitsh spaces); this is considered as a general method of multi-aspect evaluation of image-records. Some concepts of ASI described in the paper have been realised in the system APOS, compatible with a standard library of image processing procedures and an IDB management system. APOS has been designed mainly for biomedical applications.
Key words: image processing, image databases, serial images, relations, hyperrelations, semiordered vector spaces.

Tanács A., Palágyi K., Kuba A.:
Medical image registration based on interactively identified anatomical landmark points.
MGV vol. 7, nos. 1/2, 1998, pp. 151-158.

Registration is a recently emerged task in medical image processing used to match two independently acquired images. To register images, the geometrical relationship between them is to be determined. Matching all the geometric data available for a patient provides better diagnostic capability, better understanding of data, and improves surgical and therapy planning and evaluation. Registration of images taken from different modalities (i.e., multimodality registration) is regarded as a rather difficult problem. This paper describes a method for solving 2D/2D and 3D/3D registration using interactively defined point landmarks. We have implemented this robust and effective method. The SIR (Simple Image Registration) software system runs on IMB PCs under Windows operating system.
Key words: medical imaging, registration problem, reslicing, image fusion.

Østergaard L.R, Lind J., Larsen O.V., Nielsen H., Bartholdy N.J., Haase J.:
System for 3D localisation of malformations in the human brain.
MGV vol. 7, nos. 1/2, 1998, pp. 159-167.

A 3D localisation system for pre-operative planning is presented. The developed localisation system is able to estimate the 3D position of a target, e.g. an AVM (Arterio-Venous Malformation), based on a set of digital X-ray images. Distortion correction and camera calibration is performed in order to obtain accurate 3D estimates. The system is tested on a plexiglass phantom with embedded steel pellets offering 126 test points with known 3D positions. The test has shown that the system is able to estimate 3D positions with a mean error of 0.33 mm and a maximum error of 1.18 mm. The required accuracy is 0.6 mm and the test showed that more than 90% of the 3D position estimates fulfil this requirement.
Key words: Digital X-ray imaging, distortion correction, camera calibration, pre-operative planning.

Punys J., Puniene J.:
Statistical approach for boundary extraction in echocardiographic images.
MGV vol. 7, nos. 1/2, 1998, pp. 169-178.

The technique for defining an initial endocardial boundary in 2D ultrasound heart images is developed. The model of a boundary is constructed on a set of connected vertices. The position of vertices is evaluated by applying the matched detector technique. The parameters of the detector weigth function are adapted for eliminating undesirable deformation effects caused by the papillary muscles. Then the endocardial boundary is modified on the basis of criterion on which the geometrically deformable model can be constructed. Results of applying the algorithm for endocardial boundary estimation to medical images are presented.

Thurfjell L., Ranefall P., Bengtsson E.:
A deformable atlas of the chest based on the visible man.
MGV vol. 7, nos. 1/2, 1998, pp. 179-186.

This paper describes the creation of a 3D computerised anatomical atlas of the chest based on data from the Visible Human project at the National Library of Medicine. A pixelwise box classifier was used to segment different organs in the chest colour and CT images of the male cadaver and a chest atlas containing surface descriptions of the segmented organs was created. The structures in the atlas can be visualised using fast surface rendering. The atlas can also be deformed to fit the anatomy of another individual. This is illustrated by an application example where the atlas is matched to MRI data from a healthy volunteer.

Belikova T.P., Stenina I.I., Yashunskaya N.I.:
Image interpretation based on image processing and knowledge-guided data analysis.
MGV vol. 7, nos. 1/2, 1998, pp. 187-196.

A series of methods has been developed to promote medical image analysis and interpretation in complex diagnostic tasks. Image processing methods were used for better representation of informative features for the expert's analysis. Then the expert's descriptions of processed image were collected in a database to find discriminative features and create classification decision rules. Created threshold rules were interpreted by physicians as a syndrome-like construction conventional for medicine. We proposed some statistics that were helpful for measuring some discriminative features directly in the image to realize unbiased expert-independent part of image descriptions. Developed methods were applied for early peripheral lung cancer diagnosis and helped to improve the efficacy of image interpretation for physicians of different qualifications.
Key words: image processing, knowledge-guided image analysis, uncertain data interpretation, computer-aided image diagnosis.

Hashoti E.:
Graphical and non-graphical information integration, data base application development using AutoCAD.
MGV vol. 7, nos. 1/2, 1998, pp. 197-203.

This research paper will analyze our ideas about different issues on integration of two different types of information: graphical and non-graphical. Although many GIS packages are available in the world's software market, still it is quite difficult to choose among this variety of numerous software, both satisfying cost and quality requirements. Most of many specific cases require approaching this argument without risking additional and maybe unnecessary investments. By choosing common tools and software, we offer to present our study which focuses and samples the Immovable Properties graphical and non-graphical manipulation.
Key words: AutoCAD extended data, one-directional linkage, external data identification.

Nieniewski M.:
Experiments with morphological Markov random fields.
MGV vol. 7, nos. 1/2, 1998, pp. 205-220.

The paper presents results of experiments with morphological Markov Random Fields (MRFs). The use of MRFs allows one to include a prior knowledge about an image via the probability model into the processing of the image. At the same time, when generating random textures, one notes that various textures are possible, for which the models still have to be invented. The morphological MRFs offer a method for enlarging the set of probability models. However, it is not obvious what the effects of changing the model and its parameters will be. The paper presents results of systematic experiments with the generalized Ising model as well as generalized Potts model. In this way a deeper insight into the properties of the morphological MRFs is obtained.

Lumini A., Maio D.:
Image generation by Petri nets.
MGV vol. 7, nos. 1/2, 1998, pp. 221-232.
[The Best Paper Award recipient.]

This paper presents a new approach to computer image generation. The basic idea is to translate the evolution of a Petri net into a graphic output. In particular, we focus on three methods for image generation which exhibit a certain analogy with fractals. Some experimental results are reported together with a brief investigation on the relationships between generated images and their corresponding Petri nets.
Key words: image generation, Petri nets, fractals.

Ihle T., Fuchs S.:
Marching open stars - single pass segmentation of 3-D pseudo-manifolds.
MGV vol. 7, nos. 1/2, 1998, pp. 233-244.

We present an approach for segmentation of 3D voxel data based on algebraic topology. The framework leads to a single pass algorithm for constructing symbolic descriptions of volumetric data. Unlike previous algorithms, segmentation is not limited to extracting isosurfaces, i.e. 2D manifolds, enabling the processing of image sequences. Due to the anchoring on algebraic topology, the correctness of the algorithm can be proven.
Key words: topology, 3D segmentation.

Iones A., Zhukov S., Krupkin A.:
Building optimal bounding volumes for real-time 3D visualization.
MGV vol. 7, nos. 1/2, 1998, pp. 245-258.

Bounding volume hierarchies are widely employed in many areas of Computer Graphics. Usually they are used as crude approximations of scene geometry to speed up time-consuming computations such as visibility tests for frustum culling, ray shooting, etc. A number of bounding volume types have been discussed by various researchers. They include bounding spheres, axis-aligned and oriented bounding boxes (OBBs), and others. Although it is practically possible to use any of these bounding volumes, some types prove to be particularly useful in certain applications. E.g., Gottschalk et al. used OBBs to implement a very effective exact collision detection scheme.
In this paper we address the problem of efficient bounding volume selection, the solution of which allows us to significantly accelerate such operations as visibility tests for frustum culling and ray shooting. We prove that minimal surface area (minimal perimeter in 2D) oriented bounding box is optimal among all the oriented bounding boxes with respect to the three operations stated above. Then, we develop a number of algorithms to create optimal oriented bounding boxes and their approximations and finally discuss the results of our practical implementation.
Key words: computational geometry, bounding volumes, frustum culling, ray shooting, real-time graphics.

Moscinska K.:
Markov random fields and constrained optimization for textured image segmentation.
MGV vol. 7, nos. 1/2, 1998, pp. 259-268.

Classical methods of image segmentation, like discontinuity detection or region growing concepts, are not satisfactory in case of textured images. The alternative is the application of stochastic models like Markov Random Fields (MRF) for image modelling and segmentation. Stochastic models may be described in terms of energy function that should be minimized during a relaxation procedure. Instead of doubly-stochastic model, in which both the intensity and the label process are modelled by a MRF, we apply MRF for region geometry modelling, whereas image intensity is modelled by the set of deterministic features. Local texture properties are evaluated using local linear transforms or results from the first order histogram. We measure the disparity between spatial features on the basis of the Kolmogorov-Smirnov statistics. Stochastic relaxation algorithm is applied for the minimization of the global energy function. The forbidden label configurations introduce constraints into the minimization process. Simulation results for the texture segmentation task are given. The examples presented in the paper confirm the usefulness of proposed models and the efficiency of the designed algorithms. Parallel implementation of the constrained optimization can be considered due to the local computation.
Key words: Markov Random Field, texture, image segmentation, stochastic relaxation, constrained optimization.

Sluzek A.:
Moment-based contour segmentation using multiple segmentation primitives.
MGV vol. 7, nos. 1/2, 1998, pp. 269-279.

The paper presents a new technique of segmenting digital contours using multiple segmentation primitives. Therefore, segmentation results are a combination of line segments, arcs, corners, etc., depending on how well these shapes match the original contour. In the first step, the prospective instances of all available segmentation primitives are detected within the input digital contour. This is done by using features based on moments and moment invariants adapted for digital contours. Then, the detected instances are ranked according to how accurately they fit the corresponding fragment of the contour. Finally, the top-rank segmentation primitives are selected one by one until the whole contour is approximated. The algorithm has relatively low computational complexity, and it allows parallel implementation. Moreover, the algorithm is not sensitive to the performance of edge detectors so that similar results are produced no matter what edge detector has extracted contours from the original image. Therefore, if the quality of camera-captured images is satisfactorily high, the algorithm can analyse them without any preprocessing required (except, of course, edge detection).
Key words: contour images, segmentation, shape primitives, moment invariants.

Palenichka R.M., Ivasenko I.B.:
Structure-adaptive evaluation of additive noise level in images.
MGV vol. 7, nos. 1/2, 1998, pp. 281-290.

In the paper the problem of noise estimation is considered. The distinctive feature of the presented structural image model is the separate modeling of the object's planar shape as well as the image intensity function which is defined within the support regions of objects and for the background itself. For the intensity function model of the original image a piecewise polynomial model is assumed.
Key words: noise estimation, piecewice polynomial model, sequentional differentiation, trimmed mean filter.

Kozera R.:
An overview of the shape-from-shading problem.
MGV vol. 7, nos. 1/2, 1998, pp. 291-312.

In this paper, we discuss the problem of recovering the shape of a smooth lambertian surface illuminated by one (two, three) distant point light-source(s). We show that the system of three (two) first-order non-linear partial differential equations corresponding to the case of three (two) point light-source photometric stereo has a unique (generically unique) solution. In the case of one point light-source, we discuss the existence and uniqueness of solutions to the corresponding eikonal equation. In connection with uniqueness, we consider circularly-symmetric eikonal equations forwhich there exist circularly-symmetric and non-circularly symmetric smooth solutions. In addition, we briefly discuss a number of shape reconstruction algorithms based on a single (multiple) image analysis.

Skomorowski M.:
Parsing of random graphs for scene analysis.
MGV vol. 7, nos. 1/2, 1998, pp. 313-323.

Further results of research into parsing of random graphs for recognition of distorted scenes are presented. An efficient top-down parallel parsing algorithm for analysis of distorted scenes is proposed. The proposed approach involves parsing of graph grammars. To take into account all variations of a distorted scene under study, a probabilistic description of the scene is needed. The random graph approach is proposed here for such a description.
Key words: scene analysis, graph grammars, graph parsing, random graphs.

Dabkowska M., Mokrzycki W.S.:
A face-dependent view model of convex polyhedra.
MGV vol. 7, nos. 1/2, 1998, pp. 325-334.

This paper relates to the view model of convex polyhedra construction in the perspective projection, using the view sphere concept. Such models are devoted to visual identification systems. In particular, a new concept of feature-dependent choice of the view points and their dislocations on the view sphere is presented. And also a new method and an algorithm of determining one-view areas on the sphere is described.
Key words: visual identification of objects, view model database, view sphere, view points, strategy of view points selection, one-view areas on the sphere.

Grabska E., Gurba M., Strug B.:
Designing Aalto lamps by means of attributed graph grammars.
MGV vol. 7, nos. 1/2, 1998, pp. 335-343.

This paper concerns with computer aided design. Design process is illustrated by means of designing lamps in the framework of graph transformations. The theoretical concepts are implemented and examples of designed artifacts are presented.
Key words: graph transformation, design, aesthetics, rendering.

Grabska E., Hliniak G.:
Graphic prints design using graph grammars.
MGV vol. 7, nos. 1/2, 1998, pp. 345-353.

The syntactic and semantic aspects of graphic prints design process are considered. The syntactic structures of prints are represented by graphs. Hence, graph grammars are tools for generation of graph representations of Escher's prints. The possible ways of a realisation of those representations are specified by a realisation scheme which maps graphs into graphic prints. The implementation of Escher's prints is also discussed.
Key words: graph, graphical model, graph grammar, graphic print.

Iwanowski M.:
An attempt to segmentation of semiographic characters of printed Japanese script for recognition by GedNLC grammars.
MGV vol. 7, nos. 1/2, 1998, pp. 355-365.

In the paper three methods of an automated segmentation of kanji graphs are described. The first two of them yield divisions at the level close to the traditional components of kanji} graphs. But a too large number of kanji graphs which do not lend themselves to division makes one assign to these methods an auxiliary role in the system under construction.
The third method divides a kanji graph into segments which approximately correspond to fragments of traditional strokes. Hence almost every kanji graph lends itself to division into segments, and the description thus obtained can be used for their recognition by GedNLC grammars.
Key words: kanji graph, segmentation, measure of distance.

Kowalczyk N.:
TREPHL: visual programming in three-dimensional environments.
MGV vol. 7, nos. 1/2, 1998, pp. 367-381.

In this paper we propose a new visual programming language called TREPHL intended for application in a three-dimensional environment. The main purpose of the language would be automation of repetitive tasks by end-users not trained as programmers. Other possible uses for the language may be solving domain-specific problems and creating prototypes. The design of the language profits from the following assumptions: paradigm of object-orientation, ready-to-use components supplied by operating systems and application programs as basic program blocks, construction metaphor for building programs from bricks shaped to emphasize the possible attachments between objects and hydraulic metaphor for representing the flow of data and control as pipes connecting objects.

Klopotek M.A.:
Structure and motion from multiframes.
MGV vol. 7, nos. 1/2, 1998, pp. 383-396.

The paper gives an overview of the problems and methods of recovery of structure and motion parameters of rigid bodies from multiframes.

Hassanien A.E., Nakajima M.:
An efficient cross-dissolve transformation with elastic body spline warping interpolation for facial image morphing.
MGV vol. 7, nos. 1/2, 1998, pp. 397-406.
[Paper nominated for the Best Paper Award.]

In this paper, we propose a new image morphing algorithm which uses elastic body spline to generate a warp function that interpolates scattered data points. The spline is based on a Partial Differential Equation of Navier that describes the equilibrium displacement of the elastic body subjected to forces. The spline maps can be expressed as the linear combination of an affine transformation and Navier interpolation spline. The proposed algorithm generates a smooth warp that reflects the feature point correspondence. It is efficient in time complexity and smoothed interpolated morphed images with only a remarkable small number of feature points specified. It allows each feature point to be mapped to the corresponding feature point in the warped image. Once the images warped to align the positions of feature and their shapes, the in-between facial animation from given two facial images can be defined by cross dissolving the positions of correspondence features and their shapes and colors. We describe an efficient cross dissolve algorithm for generating the in-between image.
Key words: image morphing, image warping, elastic body spline and feature specification.

Lebiedz J.:
Integer midpoint Bézier curve scan-conversion algorithm.
MGV vol. 7, nos. 1/2, 1998, pp. 407-415.

By much the same midpoint methodology as is employed in algorithms which generate a quantized representation of a straight line or a circle, incremental algorithms using only integer operations (addition/subtraction and sign testing) can generate a close approximation of more complicated curves given by implicit equation F(x,y)=0. The equations F(x,y)=0 for parabolic and cubic Bézier curves are derived and integer midpoint algorithms for these curves are presented.
Key words: Bézier curves, discrete curves, scan conversion, raster graphics.

Malgouyres R., Lenoir A.:
Topology preservation within digital surfaces.
MGV vol. 7, nos. 1/2, 1998, pp. 417-425.

Given two connected subsets Y in X of the set of the surfels of a connected digital surface, we propose three equivalent way to express that Y is homotopic to X. The first characterization is based on sequential deletion of simple surfels. This characterization enables us to define thinning algorithms within a digital Jordan surface. The second characterization is based on the Euler Characteristics of sets of surfels. This characterization enables us, given two connected sets Y in X of surfels, to decide whether Y is n-homotopic to X. The third characterization is based on the (digital) fundamental group.

Kiciak P.:
Rendering rational curves on raster devices.
MGV vol. 7, nos. 1/2, 1998, pp. 427-436.

We present a very fast and accurate procedure of rendering rational Bézier curves on a raster device. The method uses a homographic reparameterization of the curve to obtain the numerator and denominator represented in the monomial basis and uses the Horner scheme to compute them. The fixed point arithmetics used in the implementation is accompanied by a rounding error analysis that guarantees the accuracy of the curve image.
Key words: rational Bézier curves, fixed point arithmetics.

Putz B.:
Remarks on NURBS representation.
MGV vol. 7, nos. 1/2, 1998, pp. 437-443.

The paper presents two different knot vectors used in literature for NURBS representation. B-spline and Bézier representation are also easily presented as subsets of NURBS representation, with connection to knot vectors and existing standards.
Key words: NURBS, B-spline, Bézier curves and surfaces, knot vector, knot sequence.

Hrytskiv Z., Voloshynovskiy S.:
Nonlinear adaptive-parametric image restoration.
MGV vol. 7, nos. 1/2, 1998, pp. 445-454.

In this paper the problem of restoration of defocused images corrupted by mixed noise is considered. To enhance the noise immunity of restoration algorithm based on iterative method with adaptive regularization and parametric constrains on the solution the prefiltering is proposed to be carried out. To avoid double image blurring on the prefiltering stage the simultaneous suppression of gaussian and impulse noises is performed according to the local image structure using adaptive nonlinear filter.
Key words: noise removal and filtering, adaptive image restoration, regularization, iterative algorithm.

Starovoitov V., Samal D.:
Experimental study of color image similarity.
MGV vol. 7, nos. 1/2, 1998, pp. 455-462.

A new idea for low-level comparison of color images is presented and tested experimentally. The developed method allows to compare two color images of the same size and color range. A modified chess-board metric was used as a measure of local dissimilarity between the pixels of compared images followed by the calculating of global dissimilarity value. Providing the dissimilarity value is lower than some value, we can say that two digital images are similar and present the same scene.
Key words: digital color image, distance, low-level image processing, image comparison.

Okun O.:
Euclidean distance transform with the reduced number of multiplications.
MGV vol. 7, nos. 1/2, 1998, pp. 463-474.

A new method of the Euclidean distance map generation is developed which reduces the number of multiplication operations needed to compute distances. This method belongs to a class of the ordered propagation distance transforms using masks whose shape depends on a direction of the distance value propagation. To obtain Euclidean distances, we apply two non-Euclidean transforms (city block and chessboard) simultaneously so that our approach is faster than the standard algorithms because it uses only additions instead of multiplication operations when labelling the distance map. Experiments confirm correctness of our method and memory requirements for it do not exceed those for other transforms using ordered propagation.
Key words: distance transform, ordered propagation, Euclidean distance, city block distance, chessboard distance.

Szirmay-Kalos L., Fóris T., Purgathofer W.:
Non-diffuse, random-walk radiosity algorithm with linear basis functions.
MGV vol. 7, nos. 1/2, 1998, pp. 475-484.

This paper presents an efficient method to solve the general rendering equation, using a combined finite element and quasi-random walk approach. Applying point collocation method, the surfaces are decomposed into planar patches where the directional distribution of the radiance is assumed to be a linear combination of the distributions at the vertices. The direction dependent radiance function of the vertices is then computed by random or quasi-random walk.
Key words: rendering equation, quasi-monte carlo quadrature, radiosity, point-collocation method.

Toumit J.-Y., Emptoz H.:
From the segmentation to the complete reading of a mathematical document.
MGV vol. 7, nos. 1/2, 1998, pp. 485-504.

Automatic reading of scholar manuals is an important problem for the editors; we are presently working in this context on the conversion of mathematical manuals into electronic documents. No research on the entire mathematical document seem to have been achieved until now, there has been only studies on the formulas themselves. We therefore present the problem of reading such documents. Those documents contain two types of information of different natures: the text and the mathematical objects. To perform a better treatment on the text itself, we are leaded to separate those two types of information; in this article, we pay a particular attention to this treatment which can be considered as a multi-language segmentation problem. Classical methods do not provide satisfactory results and we needed to introduce a new segmentation approach; it fills the document's surface using "propagation" methods around particularily specific points of the text or of the mathematical objects. We also analysed the constraints relative to the documents we have to deal with; in this context, we need to use the gray-level image without binarizing it. A method for segmenting words and characters using this gray-level image is presented and we then introduce tetrarization which leads to more reliable images than binarized images.
Key words: automatic reading, mathematical formulas, multi-lingual segmentation, gray-scale image processing.

Bres S., Emptoz H.:
Local and global orientations on images.
MGV vol. 7, nos. 1/2, 1998, pp. 505-513.

This paper presents a new method of anisotropy inspection and quantification in digital images. It allows to detect the measure the occurrence of each directions of an image. The human visual system is usually very powerful for anisotropy detection, because it performs this analysis at different levels. Local information (from details) and more global information (from spatial distribution of patterns) are simultaneously present for the treatment. We show that our method is able to perform the anisotropy feature analysis using this global approach, unlike classic methods of directions analysis. Moreover, our method directly processes grey level images, uses the inner part of the patterns instead of their contours and is able to inspect all the directions of a picture. These specifications overcome most of the limitations of usual methods.

Betsos G., Heger R.:
A desktop virtual reality system for automated assembly planning.
MGV vol. 7, nos. 1/2, 1998, pp. 515-531.

This paper describes the basic components of a system, that automates the assembly planning of industrial products. The system makes use of the technique of Virtual Reality (VR) in order to simulate the manual assembly of products in an intuitive way. The end user can interact with three dimensional objects inside a virtual environment and assemble them in a variety of ways. He can subsequently use a browser to view the precedence graphs of the actions performed inside the VR environment. With the aid of these graphs, he can choose the optimal assembly sequence. All the components of the system are controlled using a Graphical User Interface (GUI) developed using the Tcl/Tk scripting language.

Machine GRAPHICS & VISION, Vol. 7 (1998), No. 3:

Neumann L., Neumann A., Prikryl J., Purgathofer W.:
The constant radiance term.
MGV vol. 7, no. 3, 1998, pp. 535-549.

This paper describes a fundamental improvement for all rendering methods that evaluate the rendering equation in any complexity. The "Constant Radiance Term" accelerates the computation of multiple interreflections in arbitrary non-diffuse environments. It is an extension of the constant radiosity step introduced earlier for solving radiosity problems and does not require geometrical nor visibility information.
A constant radiance portion is extracted from the solution in every surface point and every direction. The residuum problem can be solved faster or with reduced variance by all known methods that consider non-diffuse light interreflections, like different versions of distribution ray tracing, deterministic and stochastic radiosity methods, and hybrid solutions. The constant radiance value is chosen in such a way that the total self-emitted power of the residuum problem is zero so that after the extraction of the constant part there are places with positive self-emittance and places with negative self emittance.
The achieved acceleration can be significant for environments with many bright coloured surfaces. Using a decomposition into separate positive and negative problems it is possible to apply this technique even when using turnkey rendering software.

Li W., Ke Q., Huang X., Zheng N.:
Light field rendering of dynamic scene.
MGV vol. 7, no. 3, 1998, pp. 551-563.

Image based rendering has displayed advantage in speed over traditional geometry based rendering algorithms. With the four dimensional light field descriptions, static scene can be generated with interactive rate on ordinary computer. The limitation of the scheme is that it can only handle static scene and fixed illumination. This paper raises the idea to decompose the light field into sub-light-fields that do not change as scene changes. It expands the advantage of light field rendering to dynamic scenes where the position and orientation of objects, lights and viewpoint can be modified arbitrarily.
The sub-light-fields include: ambient light field and spot light field. The latter is actually an eight-dimensional space. Because diffuse reflection is independent on view direction, this paper presents a four-dimensional representation of spot light field. Considering the linearity of diffuse reflection to different spot lights, the spot light fields of an object can be represented by the reflection light field to a pure-color light with unit intensity, to decrease storage and preprocessing. Owing to the coherency in their data structures, data of the corresponding point in the ambient light field, diffuse light field and depth field are combined into a 5-dimensional vector which can be compressed efficiently with vector quantization. The algorithm given in this paper accurately computes typical characteristics of dynamic scene such as changes in surface color and shadow.
Key words: ambient light field, spot light field, diffuse light field, depth field.

Flasinski M., Skomorowski M.:
Parsing of random graph languages for automated inspection in statistical-based quality assurance systems.
MGV vol. 7, no. 3, 1998, pp. 565-623.

Basic requirements for an automated visual inspection in intelligent SPC-oriented quality assurance systems are discussed. Extensions of feature IE-graphs representing solids in CAD to a stochastic model of manufacturing processes are proposed. An efficient random graph language analysis based on parsable ETPL(k) graph grammars is presented as a tool for intelligent reasoning in high layer modules of automated inspection systems. The first applications of the model are shown.
Key words: graph parsing, graph grammar, syntactic pattern recognition, visual inspection.

Rosin P.L.:
Grouping curved lines.
MGV vol. 7, no. 3, 1998, pp. 625-644.

This paper examines the problem of automatically grouping image curves. In contrast, most previous work has been restricted to points and straight lines. Some of the computational aspects of the groupings, namely continuation, parallelism, and proximity are analysed, and the issues of neighbourhoods, combinatorics, and multiple scales are discussed.
Key words: illusory contours, automatic curve grouping, segmentation and completion of curves, multi-, natural and single scales of curves.

Abuzova I.V., Ignatiev V.M., Kotov V.V., Larkin E.V.:
The method of multiframe image filtering.
MGV vol. 7, no. 3, 1998, pp. 645-654.

Features of so called multiframe images are described. Methods and algorithms of multiframe images processing, such as reduction to the base frame and filtering of an outcome three-dimension signal, are considered. Results of experimental researches are given.
Key words: image, frame, multiframe, Fourier spectrum, Haar spectrum, filtering.

Bartkowiak A., Szustalewicz A.:
Watching steps of a grand tour implementation.
MGV vol. 7, no. 3, 1998, pp. 655-680.

Bartkowiak and Szustalewicz (1997), have proposed an implementation of the grand tour algorithm designed specially to detect outliers in multivariate data. The algorithm works by performing a sequence of rotations and projections onto a specific 2D-plane. This is equivalent to perform a series of rotations yielding transformed coordinates of the data:
X^tr = X A, with A being the rotation matrix, while X and X^tr denote the data matrices before and after the rotation, respectively. A superimposed concentration ellipse indicates the outstanding points. We complement the paper by considering some details and variants of the implementation of the grand tour algorithm. In particular we watch the trajectories of the projected points. Our concern is the denseness of the watched projections. We look at the trajectories of the projected points visible in the projection plane and the frequencies of their appearing in various sectors of that plane.
In the Appendix we present the derivation of the formula for the rotation matrix A employed in each step of the algorithm for obtaining the transformed data coordinates.
Key words: dynamic graphics, grand tour, rotation, projection, uniform distribution.

Yadohisa H.:
Visualization of proximity data by multidimensional scaling with residual from space reduction.
MGV vol. 7, no. 3, 1998, pp. 681-686.

New multidimensional scaling method for representing a two-way proximity data is proposed. Given an n x n data matrix D of proximity measures between n objects, a configuration of objects, optimum in a sense, is determined by applying some suitable multidimensional scaling method as a set of coordinates X. A residual matrix is defined here as a reduced-space difference of D and the inter object distance matrix composed from X. The main purpose of this paper is to propose a graphical method for representing the residual caused from space reduction.
Key words: asymmetry, data visualization, (dis)similarity, graphical representation, MDS.

Smolka B.:
An application of random Markov field in selected problems of low-level image processing (in Polish). [Dissertation Abstract]
MGV vol. 7, no. 3, 1998, pp. 688.

Machine GRAPHICS & VISION, Vol. 7 (1998), No. 4:

Kim J., Gillies D.:
Automatic morphometric analysis of neural cells.
MGV vol. 7, no. 4, 1998, pp. 693-709.

Studies of developing neural cells are widely used in fundamental research into the mechanisms of nervous diseases, such as multiple sclerosis. These studies normally require researchers to estimate the populations of different classes of cells in microscope images of either tissue or cultures. The estimation process is carried out by human visual inspection, and is time consuming and subjective in nature. As an attack on this problem, we have been investigating the use of computer vision to classify and count the neural cells automatically. We apply various image processing techniques to reduce the neural cells in an image to a skeleton form. Then various measures such as the fractal dimension and 2^nd moment are applied to classify cells according to their spatial growth characteristics seen during their development. The measures are then combined using a bayesian classifier, and a decision is taken as to which class a cell belongs. Our initial studies were aimed at classifying the different development stages of the cells knowns as oligodendrocytes. The results were encouraging with better then 80% agreement between the computer analysis and human judgement.
Key words: Sholl coefficient, fractal dimension, 2^nd moment, profile, bayesian classifier, oligodendrocytes.

Pietka D., Dulewicz A., Jaszczak P., Nechay A.:
Extending DIPS software package for research and routine investigations of biomedical images.
MGV vol. 7, no. 4, 1998, pp. 711-723.

The paper introduces DIPS (Digital Image Procesing System), a new, original software package, developed to meet specific requirements of image analysis in scientific environment. Without going deeply into programming details, key features of the system are highlighted: flexibility when designing new picture processing schemes and simplicity when performing routine tasks.
Key words: image processing software, microscopic image acquisition, object extraction, morphometry, cytopathology, histopathology, cells and smears classification.

Rakotomalala V., Macaire L., Postaire J-G., Valette M.:
Identification of retinal vessels by color image analysis.
MGV vol. 7, no. 4, 1998, pp. 725-742.

A recursive edge tracking of the retinal blood vessel is presented in order to achieve a bidimensionnal reconstruction of the retinal vasculature. First, color edge detection is applied on the original angiographic images. Second, from interactive selection of starting points near the papilla, the tracking of the two contours of a vessel is processed. The algorithm validates the next connected pixels to the current ones which satisfy the tracking hypotheses. Problems induced by the curvature of the vessel and the discontinuity of the detected edges will be dealed with. Third, during the tracking, the algorithm looks for branchings along the major vessel beeing tracked. Another recursive tracking procedure is then performed from these branch points until the end of the vessel is reached. Contour and the color of the vessel's body are associated in order to get more accurate extraction.The reconstructed vascular structures will be used as landmarks for the follow-up of a new retinopathy called CytoMegaloVirus retinitis found on patients with acquired immune deficiency syndrome (AIDS).
Key words: color image processing, color gradient, blood vessel reconstruction, edge tracking, color region/edge cooperation.

Nikiel S., Kirby G.H.:
Fractal palettes for medical imaging.
MGV vol. 7, no. 4, 1998, pp. 743-750.

A fractal colour model used for medical imaging is discussed in this paper. Presented method should lead to better understanding of displays of complex and ambiguous medical data sets. A simple technique for generation of fractal palettes with different 'irregularity' is presented together with sample images. The method was tested with real life datasets. Obtained results show that the fractal colour model can be used as an additional interactive tool for medical visualisation purposes. This tool is especially useful in enhancing detail visibility within uncertain regions of computer tomography, magnetic resonance and X-ray mammography images.
Key words: data display, medical imaging, fractals.

Khouas L., Clarysse P., Friboulet D., Odet C.:
Fast 2D vector field visualization using a 2D texture synthesis based on an autoregressive filter. Application to cardiac imaging.
MGV vol. 7, no. 4, 1998, pp. 751-764.

This paper presents a new technique for vector field visualization and its application to the motion estimation of the heart. Our approach is based on the principle of filtering a texture over the data to visualize. For this purpose, we have first developed a texture model that allows 2D synthesis of furlike texture. The technique is based on a non stationary two dimensional AutoRegressive synthesis (2D AR). The texture generator allows a local control of orientation and length of the synthesized texture (the orientation and length of filaments). We have experimented the use of this texture model to represent 2D vector fields. We use orientation, length and color attributes of our furlike texture to visualize local orientation and magnitude of a 2D vector field. The visual representations produced seem satisfying since complete information about local orientation is easily perceived. In addition, due to the AR formulation, the obtained technique is computationally efficient. In particular, the application of this technique to the visualization of the myocardial motion has proven very useful.
Key words: furlike texture, AR texture modeling, texture synthesis, 2D vector field visualization, computer-aided diagnosis, cardiac motion analysis.

Mari M., Smits P.C., Kies P., Chmielewski L.:
Interactive object detection using a fuzzy image segmentation approach.
MGV vol. 7, no. 4, 1998, pp. 765-780.

In this paper the attention is focused on the processing of digital images, in particular on the segmentation of medical images. A new 3D fuzzy segmentation technique is presented to outline the advantages of a relatively simple software tool that may help the user to find contours of the objects of interest in images. The proposed technique is based on a seed growing approach, which takes into account both contextual and topological information in the image. The uncertainty of the image is considered through the use of fuzzy measures, well suited to represent the characteristics of a medical image. The result is a set of possible contours for the volume of interest at different certainty values. They may be viewed as alternative contours of the same object. If the method is used interactively, the user has the possibility to scroll very quickly through the different contours to select the most appropriate one for a specific application, according to his own knowledge.
Quantitative and qualitative results have been presented for a set of standard test and real images, showing the peculiarities of the proposed approach. The main applications are suggested in diagnosis (volume determination of tumours) as well as in therapy (oncological treatment planning).
Key words: image processing, fuzzy connectedness, optimal path, isoregion, MR imaging.

Bogus P., Massone A.M., Masulli F., Schenone A.:
Interactive graphical system for segmentation of multimodal medical volumes using fuzzy clustering.
MGV vol. 7, no. 4, 1998, pp. 781-791.

The paper presents a computerized interactive graphical system for multimodal medical volumes segmentation. We present a new generation of the system obtaining by applying fuzzy methods in clustering. We give an outline of fuzzy c-means algorithm and we report the results obtained by using it to multimodal medical volumes segmentation.
Key words: multimodal medical volumes, fuzzy clustering, segmentation, medical application.

Csébfalvi B., Szirmay-Kalos L.:
Interactive volume rotation.
MGV vol. 7, no. 4, 1998, pp. 793-806.

In this paper a new volume rendering method is presented which provides real-time rotation without using any acceleration hardware. The algorithm is based on the efficient handling of empty voxels, where according to the opacity values a 3D binary mask is generated indicating the locations of the non-transparent voxels. Ray casting is performed on this binary mask which is rotated rapidly by shear-warp factorization and an incremental alignment technique. The location of a non-zero bit hit by a ray is mapped onto the corresponding voxel location in the original classified volume, in order to get the opacity and color values in the given sample point. The technique proposed for rotating and sampling the binary mask exploits only the standard ALU operations providing interactive frame rates even on low cost machines.
Key words: volume rendering, ray casting, shear-warp factorization.

Peckar W., Schnörr C., Rohr K., Stiehl H.S., Spetzger U.:
Linear and incremental estimation of elastic deformations in medical registration using prescribed displacements.
MGV vol. 7, no. 4, 1998, pp. 807-829.

We propose an approach for estimation of elastic deformations in medical registration. Compared to standard registration methods based on elasticity theory, our estimation scheme does not contain parameters of the deformation model (elastic constants). Rather, the computed elastic deformation is uniquely defined through incorporation of prescribed displacements on boundary structures in the source and target image. Under the assumption of correctness of input data, our estimation scheme provides the exact correspondence of structures to be registered due to the constraints. Furthermore, to cope with large-magnitude deformations, we propose an incremental model based on successive linearizations of the non-linear elastic equilibrium equation. To illustrate the performance of our approach, we show experimental results for 2-D and 3-D synthetic as well as real medical images and provide timing information for sequential and parallel realizations.
Key words: non-rigid medical image registration, elastic deformations, finite element method.

Belov D.I., Sadykhov R.H.:
New approach to hidden-surface elimination of 3D medical images.
MGV vol. 7, no. 4, 1998, pp. 831-840.

This article presents a new algorithm for hidden-segment elimination on the plane. A condition of equivalence of two solutions of hidden-segment elimination problems is presented. On the basis of the results a new approach to efficient solution of hidden-surface elimination problem for investigated 3D medical images is suggested.
Key words: hidden-surface elimination, hidden-segment elimination, layer-model.

Belikova T.P., Stenina I.I., Yashunskaya N.I.:
Image processing and knowledge-guided data analysis for medical diagnostics support.
MGV vol. 7, no. 4, 1998, pp. 841-858.

A series of methods has been developed to support medical image analysis. Optimal filtering was applied for better imaging of informative features (diagnostically important details and structures). Several models of image background were tested to design an optimal filter, which is the best by expert criteria. Descriptions of processed images were made in terms of emphasized informative features, collected in the database, and used to find a decision rule, which presented an effective solution of medical tasks in easily interpretable form. Developed methods allowed to explicit some elements of human visual task structure into several simpler subtasks. It shows the approaches to effective learning the physicians and to automated computing some informative features directly in the image to realize expert-independent part of image analysis and description. The methods were tested in the task of early peripheral lung cancer diagnosis and gave an essential improvement of diagnostic accuracy for the physicians of different qualifications.
Key words: image processing, knowledge-guided image analysis, uncertain data interpretation, computer-aided image diagnosis.

Cerezo E., Serón F.J., Soria A.:
PCRT3D: an interactive three-dimensional radiation treatment planning system based on volume rendering for low-end platforms.
MGV vol. 7, no. 4, 1998, pp. 859-878.

The objective of radiation therapy is to concentrate a prescribed radiation dose accurately within a target volume in the patient. Computer assisted radiation treatment planning provides a tool to find the optimum configuration of radiation beams for the treatment of an individual patient. It involves interesting 3D techniques that demand high-end visualisation and computational abilities, pushing the limits of available technology.
PCRT3D is a therapy-planning tool that runs under WINDOWS NT and is an updated and improved version of the PCRTv3.2 tool that is being used in more than 30 Spanish hospitals. All the visualisation part of the application has been developed in the Advanced Computer Graphics Group of the University of Zaragoza (Spain). Based on volume rendering, anatomical and dose information can be mixed and observed in 3D and on every desired plane. Some of its major features are a simple and intuitive interface, strict manipulation of the input data coming from the scanner to avoid artifacts showing up and special render algorithms to achieve interactivity. The creation of new images by means of morphing between images, beam-eye-view and digitally reconstructed radiographs also figure among its capabilities.
Key words: 3D visualisation, volume rendering, morphing, 3-dimensional treatment planning.

Martin R.R., Anguh M.M.:
Estimating wound volumes from scanner data.
MGV vol. 7, no. 4, 1998, pp. 879-889.

This paper considers how data from combined 3D depth maps and colour images can be used to estimate the volume of a wound - a procedure which may be important to its successful treatment. The colour image is used to segment the data into wound and non-wound areas. We then use the area of good skin surrounding the wound to fit a hypothetical surface going across the wound, telling us where the skin surface would have been without a wound. Finally, data in the wound area is used to estimate the depth of the wound relative to this hypothetical surface, from which the volume of the wound can be computed. The main new contribution of this paper lies in the surface fitting method described. At present only a methodology is given, as practical tests have not been carried out.
Key words: surface fitting, wound volume, volume estimation, depth map, image, scanner.

Revievers' index

Authors' index

Contents of volume 7, 1998

6 (1997)	main	8 (1999)