Vol. 5 (1996): Abstracts of Papers

Machine GRAPHICS & VISION, Vol. 5 (1996), Nos. 1/2:

Special issue:
Proc. 4th International Conference on Computer Graphics and Image Processing (GKPO'96),
Machocice, Poland, May 20-24, 1996.
[See also two papers in the No. 3 below]

Valev V.:
Construction of Boolean classification rules and their applications in computer vision problems.
MGV vol. 5, nos. 1/2, 1996, pp. 5-23.

Classical supervised pattern recognition problems are considered in the paper. For solving these problems a mathematical model using Boolean classification rules based on the notion of non-reducible descriptor is proposed. It is proved that the computational complexity of the model belongs to the class of NP-complete problems. A computational procedure for the construction of all non-reducible descriptors for a given object is discussed. Applications of the proposed model for solving some computer vision problems such as recognition of Arabic numerals and recognition of electrocardiograms are given as well.

Handels H.:
Automatic analysis and visualization of brain tissues in multispectral MR image data.
MGV vol. 5, nos. 1/2, 1996, pp. 25-34.

In this paper a new approach for automatic analysis and visualization of brain tissues in multispectral MR image data is presented. Histogram pyramids are introduced as a generalization of histogram based cluster analysis methods and used for unsupervised classification of tissue structures in multispectral image data. The cluster analysis leads to an extraction of segments corresponding to different brain tissues. The following post-processing algorithm merges split tissue parts to improve the segmentation. Different visualization techniques and physiological colors scales are used for the visualization of the segmentation results showing similar relaxing tissues with similar colors. Based on a brain tissue data base the segmented tissues are classified with the k-nearest-neighbor and the maximum-likelihood classifier, alternatively. The best classification results were achieved with the 4-nearest-neighbor classifier showing a classification rate of 93,4%.
Key words: multidimensional histograms, histogram pyramids, tissue segmentation, physiological color scales.

Riaz M.S., Gillies D.F.:
Analysis of facial features using one dimensional Fourier transform.
MGV vol. 5, nos. 1/2, 1996, pp. 35-49.

In recent years there has been considerable research into automatic face recognition, and it is widely agreed that there are many potentially useful applications for it. However, there are considerable difficulties in implementing such systems, and to date no one system has proved sufficiently accurate to be widely applicable. The major difficulty is in determining a set of features which give good discrimination between similar faces, but are invarient over sets of images of the same face. Research into human vision suggests that spectral information is used in recognition, however, the mechanisms by which it operates are not fully known. We have experimented with frequency information to determine its discriminant capabilities on faces. Using localised features, in this case the right eye, we divide the image into 128 scan lines and take a one dimensional transform from each line. This has the advantage, over the two dimensional transform, that computations may be done fast, and at the same time spatial position invariance is retained. The resultant frequency magnitudes are then taken as a feature vector. Five subjects with similar visual features were chosen, and for each two sets of sixty four different images of the right eye were taken. The images were normalised so that they were all at the same scale. We then looked at the discrimatory power of the feature vector provided by each spectral point in turn. This was assessed by computing the Fisher linear discriminator for each possible pairing. Using the low frequency points, the results showed strong discrimination between different faces. As the frequency became higher, the discrimination capability reduced, indicating that primarily low frequencies are used in the recognition. The method shows excellent potential for fine discrimination of facial features.
Key words: one dimensional Fourier transform, Fisher's linear discriminant.

Hansen M., Sommer G.:
Real-time vergence control using local phase differences.
MGV vol. 5, nos. 1/2, 1996, pp. 51-63.

We address the control of vergence movement of an active camera system and the computation of disparity maps in real-time. We apply a phase-based approach to estimate horizontal disparity. Besides we use the disparity value of the image center as an error signal for a PD-controller, which has been implemented for movement control because of his stability in real-time systems. To estimate large disparities with small Gabor filters a coarse-to-fine strategy is coupled with the PD-control. The closed-loop vergence control has a performance of 25 Hz. The settling time for convergence on a fixated point is 0.3-0.5 seconds. Due to the phase-based approach sub-pixel accuracy in disparity estimation is possible.
Key words: active vision, stereo disparity, vergence movement.

Zeng L., Sommer G.:
Extracting an illumination invariant face representation.
MGV vol. 5, nos. 1/2, 1996, pp. 65-76.

Effective computer based face recognition requires successful extraction and representation of the relevant information. In this paper the face structure signal and the illumination signal are analyzed in frequency domain. Non-linear methods are then proposed to achieve an illumination invariant face representation. By employing the homomorphic filtering, the illumination signal is separated and then filtered out from the grey-level image. Face images in two different databases are analyzed and recognized with this new representation. The experiments show that even for images taken under substantially changed lighting conditions, the representation is invariant to changes in both direction and intensity of illumination. The data distribution are greatly ameliorated. Hence the performance of the recognition system utilizing principal component analysis is improved significantly.
Key words: non-linear filtering, face recognition, principal component analysis.

Firmin C., Hamad D., Postaire J-G., Zhang R.D.:
Feature extraction and selection for fault detection in production of glass bottles.
MGV vol. 5, nos. 1/2, 1996, pp. 77-86.

In the glass bottle production, the detection of defects on the finish is one of the most important steps in quality control. This inspection requires, high speed and robust detection of faults. Although many automated visual inspection systems have been developed to solve a lot of specific problems, their ability to cope with variations of the environment is limited and they require to be tuned very carefully whenever the characteristics of the production change. During the past decade, neural networks have been increasingly used in different areas, such as image processing, chemical processes, engineering, etc. Based on learning from examples, they can solve very complex problems. In this paper, we use this approach for defaults detection in glass bottle production. In the first section, we present the fault detection problem, in the second section, we expose the image acquisition system. After to have explain the images processing in section III, we list the features extracted in section IV, for selecting, in section V the most discriminate ones. The Multilayer Perceptron is used as detection system and is exposed in section VI.
Key words: industrial inspection, image processing, features extraction, neural networks, classification.

Flasinski M.:
Mathematical linguistics models for computer vision.
MGV vol. 5, nos. 1/2, 1996, pp. 87-97.

The role of mathematical linguistics models in computer vision is discussed in the paper. Theoretical foundations of syntactic pattern recognition are briefly presented. Basic formal languages and automata theory schemes useful for computer vision are presented. Languages of various dimensionalities are introduced and their applications are discussed.

Okun O.:
Text image analysis by distance transform-based clustering.
MGV vol. 5, nos. 1/2, 1996, pp. 99-110.

A new algorithm based on projection profile analysis is proposed. Instead of pixels, centroids of connected components are projected on X,Y-axes. To incorporate these projections into clusters corresponding to separate text elements (blocks, lines and words), distance transform-based clustering is used. Unlike other methods, in this case it is not necessary to count the number of detected clusters for each parameter (image resolution) value to determine validity of a cluster partition. Cluster validity measure is obtained by analyzing a histogram of distances between pairs of adjacent projections in 1-D. Memory requirements and processing time are reduced by using the proposed algorithm.
Key words: distance transform, clustering, text segmentation.

Zorski W.:
Application of the Hough transform with a clustering technique to segmentation of digital images.
MGV vol. 5, nos. 1/2, 1996, pp. 111-121.

The paper presents the problem of digital images segmentation. The presented method is based on the straight line Hough transform. A fundamental element of this method is the clustering technique. The technique simplifies the application of Hough transform to segmentation tasks as well as accelerates the calculations considerably.
Key words: digital images segmentation, Hough transform, clustering, computer vision, text recognition.

Cofalka P, Philipp M., Cabestaing F.:
Detection of feature points using the moving contours detection operators.
MGV vol. 5, nos. 1/2, 1996, pp. 123-130.

Parametrization of object movement requires some special information included in an image. That's why it is necessary to find some feature points belonging to an analyzed object. In this paper we tried to find corners of contour of the moving objects. For detection of moving object contours we used the Vieren operator which gives the best result comparing with the Haynes, Jain and the Stelmaszyk operators. To obtain a distinct and continuous contour five different gradient filters were tested. For detection of moving contour corners the method is proposed. According to this method corners of the moving object were correctly detected. However points close-fiting to the moving object contour which don't belong to the object were also detected. So, to extract only the interesting corners feature points matching methods should be applied.
Key words: feature points, moving contours, corners.

Nakata K., Olivier P., Bill J., Boyce D.:
Matching and tracking using decomposition.
MGV vol. 5, nos. 1/2, 1996, pp. 131-140.

This paper describes a shape matching technique based on bitmap arrays. While this class of technique has an advantage of using the direct representation of objects thus eliminating the need for feature identification and improving generality, it has been seen to be computationally expensive since it involves extremely large number of pixels to be manipulated. We have developed a technique to reduce the computational overhead using decomposition. By using images at several levels of resolution, we can reduce the complexity by eliminating unnecessary computation at the finest resolution. This technique has been successfully applied to motion tracking and there are various possible enhancements for further improvement.
Key words: occupancy arrays, multiple resolution, decomposition, shape matching, tracking.

Kaminsky R.:
Mathematical modeling of binary image and object and noise interaction by scanning method.
MGV vol. 5, nos. 1/2, 1996, pp. 141-146.

An analytical describing algorithm of scanning principle and a method of realization for a construction of binary object image in impulse noise condition on information field is considered.
Key words: binary image, scanning method, noise-object interaction.

Chmielewski L.:
The concept of a competitive step and roof edge detector.
MGV vol. 5, nos. 1/2, 1996, pp. 147-156.

A concept of using data obtained as a side effect by a new version of the competitive filter to detect step and roof edges in an image is described. Promising properties of the new detector presented with 1D examples indicate that the 2D extension which is now being developed could become a valuable tool in analysing images with piecewise linear brightness function corrupted with noise.
Key words: edge detector, step edge, roof edge, competitive filter.

Denzler J., Niemann H.:
A new energy term combining Kalman-filter and active contour models for object tracking.
MGV vol. 5, nos. 1/2, 1996, pp. 157-165.

In the past years active contour models have been applied in the field of object tracking. For object tracking a prediction step is necessary, especially when tracking in natural scenes with an imhomogeneous background or for fast moving objects. Thus, in our paper we introduce a new energy term which combines a Kalman-filter based prediction with an active contour energy description. For this, a new energy term is proposed which can be applied for all prediction steps for which a confidence of the predicted positions is available. We present results which show the improvement due to this new energy term for tracking a moving object in front of an inhomogeneous background and a partial occlusion during the tracking.
Key words: active contour models, tracking, prediction.

Bello F., Kitney R.I.:
Contrast enhancement by confined range adaptive histogram equalisation.
MGV vol. 5, nos. 1/2, 1996, pp. 167-175.

A new method of adaptive histogram equalisation that is effective in enhancing images with a relatively uniform background on which objects of interest are superimposed is presented in this paper. Its main characteristic is the confinement of the grey level range over which the equalisation takes place. By selecting a suitable range, this confined range adaptive histogram equalisation has the potential advantages of reducing noise enhancement and avoiding the shift of object grey levels into those of their background. Moreover, the selected range effectively determines the contextual region over which the equalisation will take place in an easy and intuitive manner. An application of this technique to magnetic resonance (MR) images of the human brain is given as an example of the results obtained using the new method on images with complex features.
Key words: contrast enhancement, histogram equalisation, image enhancement.

Mraghni M.C., Asselin de Beauville J.P.:
Contour detection by symbolic local and dual analysis.
MGV vol. 5, nos. 1/2, 1996, pp. 177-188.

A new method of edge detection, based on symbolic reasoning, has been developed. For a given pixel, the shape of its nearest neighbourhood, NN, (included in the 8-neighbourhood) indicates whether an edge crosses the 8-neighbourhood. Therefore, the analysis of the 8-neighbourhood leads to define a set of masks (nearest neighbourhood) which label the edge-pixel. An edge-pixel is characterised by two masks (they are it dual each other). The duality notion is introduced to : (1) offset the effect of noise, (2) provide good localisation, (3) provide only one response to a single edge. To compute the NNs, a multithreshoding method is used. As this method detects edge chains, the spurious edge elements (small chains) are rejected. Some experimental results are provided to illustrate the success of the method.
Key words: edge detection, 8-neighbourhood, nearest neighbourhood, mutithresholding.

Mazur P.:
Hardware implementation of neighborhood operations on interlaced format images.
MGV vol. 5, nos. 1/2, 1996, pp. 189-195.

Pipeline processing is a common method for implementing image processing dedicated hardware. The interlaced data format, supplied by a standard TV camera brings problems for designers of such hardware. This paper describes a hardware-efficient way of performing neighborhood operations on interlaced data. Neighborhoods are computed in two passes during two consecutive TV frames. Described circuit was implemented and tested by the author.
Key words: image processing, pipeline processors, interlaced format.

Warecki S.:
Fast ASIC stack processor for 1D and 2D images.
MGV vol. 5, nos. 1/2, 1996, pp. 197-207.

Hardware implementation of a given algorithm usually speeds up the algorithm realization but often it can lead to new solutions and better understending of fenomenon previously described only in theoretical papers. This paper tryes to bring some new ideas showing the way of speeding up the filtering process as well as helps in better understanding of s stack filter itself.
First, the general structure of stack filter is being presented with distinction of its internal modules. Then two approaches for increase of speed of a typical 1D filter are shown. One of them considers compensative comparison used instead of incremental (linear) search which is necessary for calculating the stack filter value. The other shows the way of additional increase in speed made by pipelined stack processors. Each of such processors deals with only one bit of a calculated output word at a time which in effect makes it possible to spend one cycle to compute single filter value.
In the end, an example of 2D filter with programmable aperture is shown in details. A notion of Aperture Lattice is introduced and an example of small aperture lattice is presented. Structures used in this paragraph are not only a subject to stack filter implementation but also to a vast range of filters including Rank Order filter.
Key words: stack filter, pipelined stack processor, aperture lattice, rank order filter.

Kus Z.:
Examples of stack filter design based on the mean absolute error criterion.
MGV vol. 5, nos. 1/2, 1996, pp. 209-219.

Some methods of solving of numerical problems and examples of stack filters for window width 5 are presented. The stack filter is fully determined by selection of appropriate Boolean function. As a criteria for selection of the function the minimization of the mean absolute error between required signal and the filter output is taken.
Key words: stack filter, mean absolute error, Markov chain, positive Boolean function, linear programming problem.

Alexopoulos V., Kollias S.:
Neural network based image analysis with regions of interest and multiresolution decomposition.
MGV vol. 5, nos. 1/2, 1996, pp. 221-228.

An approach based on definition of regions of interest and multiresolution image analysis is proposed in this paper for extracting small-sized feature representations from real life images in classification or recognition problems. Various feefdforward neural network architectures are used for effectively selecting regions of interest in the images and for optimally deriving low resolution representations of them; the networks are appropriately trained using data from the specific real-life application which is considered.
Key words: image analysis and recognition, regions of interest, multiresolution decomposition, autoassociative neural networks.

Krupiczka A.:
Interblock variance as a segmentation criterion in image coding.
MGV vol. 5, nos. 1/2, 1996, pp. 229-235.

Very low bit-rate image coding has recently become one of the most important areas of image communication. Since conventional (pixel based) approaches are reaching a saturation point in terms of coding efficiency, a new generation of image coding techniques, aiming at a deeper "understanding" of the image is being considered. The idea based on variable block size is applied. This paper proposes a new segmentation criterion based on interblock variance. It is used for image partitioning taking into consideration the quantitative relations between all the image blocks. This results in a smaller mean square error compared to that obtained using a fixed block size.
Key words: image coding, image segmentation.

Palenichka R.M.:
Adaptive binary segmentation of images for detection of the regions of interest.
MGV vol. 5, nos. 1/2, 1996, pp. 237-243.

The problem of image binary segmentation is addressed as applied to flaws detection in diagnostics imaging. The solution of this problem by conventional methods of thresholding with a constant threshold value does not yield a satisfactory result due to poor quality of images in the applications. To segment unsharp images in the noise presence a structure-adaptive method is proposed which uses regions-of-interest detection procedure. Theoretical and experimental investigation of the proposed method confirms its efficiency for flaws detection in metallic materials and article.
Key words: binary segmentation, region of interest, defect detection, thresholding, trimmed mean, structuring element, structuring segment.

Kosinski C., Olszak A., Kujawinska M.:
Adaptive system for smart fringe image processing.
MGV vol. 5, nos. 1/2, 1996, pp. 245-256.

Optical methods are widely used in non-destructive testing, shape measurement and stress analysis applications. Their vulnerability to unproper settings of operational parameters can be reduced by adding "intelligent" image evaluation modules and closed loops that modify parameters of data analysis. Such a system utilizing distributed quantity and quality estimation methods during image evaluation is presented. Examples are given of improved calculation cycle after the optimization performed by system.
Key words: optical methods of testing, image analysis, fringe pattern analysis, phase measurement methods.

Choras R.S., Andrysiak T.:
Predictive/transform coding of the stereo vision images.
MGV vol. 5, nos. 1/2, 1996, pp. 257-264.

Stereo vision is one of the most extensive areas of research in computer vision. Stereo images are used in many applications e.g. geoscience, machine vision and autonomous navigation. The storage and transmission of the stereo images involve large amounts of data. We discuss method to compressing stereo image data using lossy compression techniques. The proposed method is based on predictive coding, Discrete Cosine Transform (DCT) and disparity measurement. The major problem with stereo is that of determining the correspondence between features pixels in the two images. The process of stereo vision essentially measures the disparities of two images of a 3D scene and uses them to recover the depth information of surfaces in the scene.
Key words: stereo vision, disparity, stereo matching process, predictive coding, discrete cosine transform, run length coding.

Ultré V., Macaire L., Postaire J.-G.:
Determining compatibility coefficients for color contour detection by relaxation.
MGV vol. 5, nos. 1/2, 1996, pp. 265-275.

The article discusses contour detection in color images. The first part is a critical review of methods found in the existing literature. A new original color contour detection method is then presented. This method uses a local thresholding based on a relaxation algorithm to binarize the gradient image for each of the color planes. The choice of the compatibility coefficients used at the relaxation stage and their influence on the performance of the method are dicussed at length. Experimental results are presented using an image of a real scene.

Woznicki J., Kukielka G.:
Some fundamental and practical limitations of accuracy of digital image representation.
MGV vol. 5, nos. 1/2, 1996, pp. 277-296.

The purpose of this paper is to present an overview of some practical limitations in accuracy of digital image reresentation and also to indicate some examples of possible sources of errors in image processing. The paper has been based both on literature review and authors experience. The paper contains: a survey of illumination ways and sources, basic information about lenses and optical limitations, an analysis of the CCD camera as a solid-state image sensor, some considerations about practical sampling limitations and two examples showing problems arising in image analysis. So, the method of presentation is to individually discuss the chosen features of the main system components. The Modulation Transfer Function is used to characterize the performance of an image sensing system.

Wojdala A.:
Virtual set. The state of the art.
MGV vol. 5, nos. 1/2, 1996, pp. 297-315.

Virtual set technology evolved recently from the traditional blue-box technique and has already started to influence the broadcast industry. The possibility to embed real actors in realistically-looking, computer generated sets with no physical constrains has significant consequences in both economics and creative design. This paper reviews the technology involved in the virtual sets, covering the studio equipment, essential software issues and the production process. It also attempts to define the future needs, to make the virtual set a complete and reliable production tool.

Gillies D.F., Ismaili I.A., Shackleton R., Robertshaw S.:
Computer vision and interactive graphic art in the nature of history exhibition.
MGV vol. 5, nos. 1/2, 1996, pp. 317-325.

The Nature of history exhibition is an example of large scale installation art employing a wide variety of computer graphics and computer vision techniques. At its centre is an interactive area where the visitors to the exhibition are tracked using an overhead camera, and the exhibited material is made to depend on their positions. The tracking system follows the movements of a single person. The artwork changes in response to his or her movements in a variety of ways. Images of faces are made to follow the tracked observer with their eyes, figures change in age and expression, and forest walks shift revealing new perspectives. The installation is based on a network of macintosh computers, and even on these low cost machines, tracking at four frames per second is feasible.
Key words: interactive art, tracking, installation art.

Raczkowski J.:
Visual simulation and animation of a laminar candle flame.
MGV vol. 5, nos. 1/2, 1996, pp. 327-334.

Modelling and visualisation of natural phenomena is a challenge problem in computer graphics. Many researchers proposed models and rendering techniques to obtain realistic images. But rarely authors took into account small scale flames like candle or gas-lighter flames. In the paper a simple model for visual simulation of a candle flame is presented. The model uses volume modelling and visualisation techniques and is suitable for animation purposes.
Key words: modelling natural phenomena, volume visualisation, animation.

Dworzynski P., Stepien C.:
Analysis of the shape of the water droplet on an inclined glass plate and visualization with the revolved surface with b-spline cross-section.
MGV vol. 5, nos. 1/2, 1996, pp. 335-346.

The paper presents an analysis of the shape of the water droplet lying on the glass plate inclined at the angle of varphi. The physical factors such as mass of the droplet, gravitation and surface tension have been taken into consideration. Obtained results have been used for development of the droplet's model that uses B-spline surfaces. Some examples of the visualization are included.
Key words: physical model, water, droplet, visualization, B-spline curve.

Bielecka M., Bielecki A.:
Aesthetic measure for two-dimensional objects consisting of curvilinear segments.
MGV vol. 5, nos. 1/2, 1996, pp. 347-356.

This article discusses the aesthetic measure of objects consisting of curvilinear segments according to the Birkhoff theory. The definition of the complexity and the order is proposed in such a way that they can be used for such objects. Some examples of the aesthetic measure for a few objects are calculated as well.
Key words: aesthetic measure, complexity, order.

Zaremba M.B.:
A geometrical learning method for complex function approximation networks.
MGV vol. 5, nos. 1/2, 1996, pp. 357-364.

This paper presents a method that allows the user to build neural network architecture by applying qualitative geometrical analysis of the space of input states. The issue of constructive learning is addressed in the context of a general problem of the approximation of arbitrary continuous target functions by neural networks. The proposed approach considers integral representations of the desired function in the hidden layer, and generation of the continuous component of an integral representation by means of linear differential equations. The importance of this conclusion consists in the fact that the regularity of exact solutions will ensure good convergence and allow for construction of optimal connectionist networks approximating a given function with a desired precision. The presented method is illustrated in an example of processing images generated by a fibre-optic strain sensor.

Prusinkiewicz P., Hanan J., Hammel M., Mech R.:
L-systems: from the theory to visual models of plants.
MGV vol. 5, nos. 1/2, 1996, pp. 365-392.

In this paper we revisit foundations of the applications of L-systems to the modeling of plants, and we illustrate them using recently developed sample models.
Key words: L-system, fractal, plant, modeling, simulation, realistic image synthesis, emergence, artificial life.

Drewes F., Kreowski H.-J, Schwabe N.:
Collage-One: A system for evaluation and visualization of collage grammars.
MGV vol. 5, nos. 1/2, 1996, pp. 393-402.

CollageOne is a system for evaluating and visualizing collage grammars, which are rule-based picture-generating devices of a context-free type. Pictures are represented as collages that consist of coloured parts, and they are derived by applying rules to collages, thereby producing pictures that get more and more detailed. CollageOne provides a textual and graphical collage grammar editor, an evaluator of derivations, and a display of the derived pictures.
Key words: collage grammar, visualization, picture generation.

Vincent N., Merle G., Emptoz H.:
Analysis and modeling of shrinkage in composite material curing, using fractal geometry.
MGV vol. 5, nos. 1/2, 1996, pp. 403-412.

In this paper we are dealing with the problem of the analysis of images containing very irregular patterns. We propose, before the image is studied, to understand how it has been produced and then, to adapt the method. The method proposed is fractal dimension computation that we adapt to isotropic images. Finally, the fractal behavior of image is once more shown through a simulation of the fissure formation.
Key words: fractal dimension, simulation.

Chernov W.M.:
Some spectral properties of fractal curves.
MGV vol. 5, nos. 1/2, 1996, pp. 413-421.

The connection between fractal properties of sets and meromorphous continuation of some Dirichlet series is considered. Discrete orthogonal bases associated with fractal curves of the special type and fast algorithms of the spectral coefficients calculation are synthesized.
Key words: Dirichlet series, fractals, fast algoritms.

Lebiedz J.:
Structural description of digitized circles.
MGV vol. 5, nos. 1/2, 1996, pp. 423-430.

In his paper R. Brons wrote that he did not know any structural description of circles and ellipses. My paper presents this sort of description for circles generated by Bresenham's algorithm. The structural description of ellipses is analogous but more complicated. The paper also shows a scan converting algorithm based on the derived structural description. At the end, the obtained structural algorithm is compared with Bresenham's algorithm.
Key words: structural description, discrete circles, scan conversion, raster graphics.

 

Machine GRAPHICS & VISION, Vol. 5 (1996), No. 3:

Skomorowski M.:
On the parsing of random graphs for syntactic pattern recognition.
MGV vol. 5, no. 3, 1996, pp. 433-464.

An efficient parsing algorithm for ETL(1) graph grammars for syntactic pattern recognition presented in [5] is extended so that distorted patterns can be recognized. The concept of random IE graphs representing distorted patterns is introduced. An efficient, O(n^2), parsing algorithm for random IE graphs is proposed. An example is provided to illustrate the proposed parsing algorithm.
Key words: IE graphs, ETL(1) graph grammars, random IE graphs, parsing algorithm, syntactic pattern recognition.

Kulikowski J.L.:
Basic concepts in the theory and design of logical filters.
MGV vol. 5, no. 3, 1996, pp. 465-482.
[An invited talk at the 4th Int. Conf. on Computer Graphics and Image Processing (GKPO'96)]

Basic concepts of logical filtering of discrete images are describeds. Logical filtering consists in observation-space partition into subareas in which suitable (in general - different) filtering subroutines are used. Logical filtering becomes effective when strongly nonhomogenous images are to be processed. Particular examples of logical filters used in biomedical image processing are described. Some general problems concerning logical filters optimization are also considered.
Key words: image procesing, image filtering, logical filters, contour enhancement, edge detection.

Skala V.:
Trading time for space: an O(1) average time algorithm for point-in-polygon location problem - theoretical fiction or practical usage?.
MGV vol. 5, no. 3, 1996, pp. 483-494.

Algorithms for point-in-polygon problem solution are very often used especially in computer graphics applications. The naive implementation has O(N) processing time complexity or O(lg N) complexity if a convex polygon is considered. A new algorithm of O(1) processing complexity was developed. The important feature of the algorithm is that preprocessing complexity is O(N) and memory requirements depend on geometrical properties of the given polygon. Usage of the algorithm is expected in applications where many points are tested whether residing in the given polygon or not. The presented approach can be considered as alternative to the parallel processing usage. Experimental results are included, too.
Key words: point-in-polygon algorithm, data structures, algorithm complexity, geometry.

Velichova D.:
Creative geometry.
MGV vol. 5, no. 3, 1996, pp. 495-502.

The paper deals with the definition and basic notions of a new geometric space, creative space, which had been developed as the theoretical bases of CAGD. In this space, all classical geometric notions and figures are treated equivalently to the new ones - interpolated figures, which had been revealed thanks to the developement of computer graphics and computational geometry. The background of the presented 3D scenes generation using personal computers is based on geometric properties of the figures in the extended Euclidean space. A new part of geometry is introduced, Creative Geometry, which serves as a tool for generating analytic representations of figures in Euclidean space from their creative representations attached to all geometric figures due to one of their generating principles. Computers are used to visualize any figure produced from a basic figure by applying a generating principle, drawing a net of its parametric subsets. Educational software based on above mentioned ideas was developed and has been used for teaching computer and constructive geometry at the College of Mechanical Engineering, Slovak Technical University in Bratislava.
Key words: computer aided geometric design, computational geometry, creative geometry, geometric modelling.

Tjahjadi T., Dale-Jones R.:
Contrast enhancement adapted for a display monitor.
MGV vol. 5, no. 3, 1996, pp. 503-520.

This paper presents two global contrast enhancement algorithms which take into account the display capabilities of the monitor where the image is viewed. The algorithms approximately space out the grey level bins in the image histogram according to the results of two psychophysical experiments, which determine the ability of the eye to distinguish the Just Noticeable Difference (JND) between grey levels for different monitors. The look-up-table of JNDs of a monitor is used to ensure that the enhanced image will appear the same on different monitors. The first algorithm assumes that there is only one background in the image and separates the grey level bins close to the background intensity. The second algorithm considers the largest bin within the grey level range of each of the identified regions in the image to be the background intensity, and separates the bins on either side of each background.
Key words: psychophysical contrast enhancement, display monitor, holograph, photometric image.

Pamula J.:
Computer-aided imaging.
MGV vol. 5, no. 3, 1996, pp. 523-530.
[An invited talk at the 4th Int. Conf. on Computer Graphics and Image Processing (GKPO'96)]

The paper attempts to assess, in general terms, the impact of computers, as a novel medium and tool for producing visual images, on the areas of communication and artistic expression. It starts from the observation that today, mostly due to the profound advances in electronic and computer media, the image becomes more and more important as a medium of communication in comparison with traditional textual means. This leads to enormous demands for efficient generation of meaningful and effective images, calling in turn for new breakthrougths in the theory and practice of devising new visual languages and visualization of information, suitable for computer implementation.

 

Machine GRAPHICS & VISION, Vol. 5 (1996), No. 4:

Löffelmann H., Gröller E., Wegenkittl R., Purgathofer W.:
Classifying the visualization of analytically specified dynamical systems.
MGV vol. 5, no. 4, 1996, pp. 533-550.

In this paper we suggest a classification of visualization techniques for analytically specified dynamical systems into four different approaches. We distinguish between local properties, the topology of behavior, global properties, and classes of dynamical systems with respect to various topics of visualization. By presenting advanced visualization techniques that we applied during three recent projects, we discuss their embedding within the classification scheme. The dynamical systems visualized are the "Dynastic Cycle", which is a model for rise and fall of dynasties in ancient China, the "Wonderland" model, that simulates the interactions of population growth, economic activities, and environmental pollution, and a model for mixed-mode oscillations, which occurs in chemistry.
Key words: visualization, dynamical systems.

Skala V.:
Line clipping in E3 with expected complexity O(1).
MGV vol. 5, no. 4, 1996, pp. 551-562.

A new line clipping algorithm against convex polyhedron in E3 with an expected complexity O(1) is presented. The suggested approach is based on two orthogonal projections to E2 co-ordinate system and on pre-processing of the given polyhedron. The pre-processing enables to speed up solution significantly. The proposed method is convenient for those applications when many lines are clipped against constant convex polyhedron. Theoretical considerations and experimental results are also presented.
Key words: line clipping, convex polyhedron, computer graphics, algorithm complexity, geometric algorithms, algorithm complexity analysis.

Bartkowiak A., Szustalewicz A.:
Some issues connected with a 3D representation of multivariate data points.
MGV vol. 5, no. 4, 1996, pp. 563-578.

The presented considerations complement our former paper. Now we consider some topics concerned with a 3D representation of n points-individuals and p points-variables included in a data matrix X [n × p]. The representation is displayed in the form of a spinplot called also a spinner. We are concerned with the display of two kinds of information: (i) the goodness of the representation of individual points, and (ii) recognizing the mutual position (the out-of-page position) of several points when viewed in a projection plane displaying the flat projection of the whole system which is spinned by performed rotations. We present 3D displays made by this program for the oat varieties data and locations of their growing and the farm production data considered formerly. We show on these examples what a variety of questions can be answered when constructing the spinner with appropriate enhancements.
Key words: biplot, 3D plot, spinner, interdependence between variables, reduction of dimensionality.

Szczypinski P., Strumillo P.:
Application of an active contour model for extraction of fuzzy and broken image edges.
MGV vol. 5, no. 4, 1996, pp. 579-594.

The method of an active contour model (popularly termed snake) for extraction of image edges is presented in the paper. The main strength of the method is that it yields continuous contours even if the image edge/boundary information is fuzzy or fragmented. Two modifications to the original active contour model are proposed and explained in the paper. First of the modifications simplifies the original method and makes it faster in computer implementation while retaining its performance. Second modification introduces novel method of contour construction which improves active contour capabilities in detecting complex curve shapes, e.g. spirals. Results are presented which demonstrate performance of the discussed edge detection methods on a number of artificial test images and on images derived from echoardiographic scans and X-ray scans of grains.
Key words: machine vision, edge detection, active contour model.

Qu G.:
Improved morphological gradient edge detector.
MGV vol. 5, no. 4, 1996, pp. 595-612.

The morphological gradient is a nonlinear methods for edge detection. The classical morphological gradient generates an edge strength map, which provides both major and trivial edges (false edges) without clear edge orientation, thus making the performance of morphological gradient not as good as regular linear operators. In this paper, we propose a method to calculate the edge direction from edge strength map which is produced by the morphological gradient. The edge direction is estimated based on the moment of the edge strength. A non-maximum suppression perpendicular to the edge direction is introduced, i.e., the suppression is done along the edge normal. Both local features(gradient) and global properties (larger area moment) are considered to fully utilize all available edge information. A theoretical analysis of how morphological operators affect the edge orientation is discussed. The edge bias produced by the morphological operation is studied. Finally, an algorithm for edge detection by morphological gradient is implemented, which further improves and extends classical morphological gradient method for edge detection. Experimental images and comparisons with other algorithms show that the performance of this algorithm is a competitive edge detector, and has the benefit of simple implementation.

Quelle H.-Ch., Boucher J.-M., Pieczynski W.:
Adaptive parameter estimation and unsupervised image segmentation.
MGV vol. 5, no. 4, 1996, pp. 613-633.

In this paper we present a new approach to non-supervised Bayesian image segmentation. We propose an adaptive method for parameter estimation which can easily be included in most methods applying a local Bayesian decision theory. Due to the local character of our method, we dispense with the hypothesis of stationarity. This allows us to get segmentation methods working properly on non-stationary image scenes. Furthermore, the local adaptation includes spatial information in the a priori probability of the Bayesian rule. Our work treats unsupervised segmentation of SAR images. However, the developed method is a general technique for parameter estimation and can be used for most types of images. The results show that segmentation methods using spatial adaptive a priori distributions are more efficient than segmentation based on globally estimated a priori distributions.

Kolingerova I, Lobaz P.:
Experimenting with Chaos Game.
MGV vol. 5, no. 4, 1996, pp. 635-642.

This paper describes a simple modification of the Chaos Game algorithm which enables to construct attractors - combinations of fractal and "classical geometry" or two kinds of fractal shapes.
Key words: Chaos Game, iterated function system, random iteration, fractals, Julia set.

Revievers' index

Authors' index

Contents of volume 5, 1996