Vol. 12 (2003): Abstracts of Papers
- No. 1: Special Issue on Diagrammatics & Design (Selected papers from the 1st European Workshop on "Diagrammatics and Design")
- No. 2
- No. 3
- No. 4
Grabska E., Kulpa Z.:
Guest Editorial: Diagrammatics and Design.
MGV vol. 12, no. 1, 2003, pp. 3-4.
Design and reasoning with diagrams.
MGV vol. 12, no. 1, 2003, pp. 5-16.
In this paper a new framework for conceptual design based on diagrammatic reasoning is sketched. The approach considers a dynamic context for design. The main phases of the design process are treated as different classes of situations in the appropriate worlds and as such they belong to their own classifications domains. The notion of classification allows one to model constraints that govern the construction diagrams to be drawn or generated.
Key words: diagram, diagrammatic reasoning, action, conceptual design, design requirement.
Bailin S. C.:
Diagrams and design stories.
MGV vol. 12, no. 1, 2003, pp. 17-37.
We present a theory of design stories that structurally distinguishes a "story" from other forms of documentation. We examine how design diagrams might convey such stories, and how an implicit story can be made more explicit through diagrammatic cues and annotations. We develop these ideas in the context of a real-life design process. Members of the design team themselves found it a challenge to recall the rationale for various decisions. We present a series of diagrams that discloses the underlying progression of ideas, and we show how this story may be too-opaquely packaged in the "final" diagram that the team produced.
Key words: diagrams, design story, narrative, rationale, documentation.
Barker-Plummer D., Etchemendy J.:
Applications of heterogeneous reasoning in design.
MGV vol. 12, no. 1, 2003, pp. 39-54.
The task of designing a complex artifact can be thought of as reasoning within a space of alternatives. This reasoning shares the large-scale structure of logical proof: the elucidation of information as the design is fleshed out, and hypothetical reasoning concerning the consequences of various possible design decisions, for example. However, design reasoning differs from the kind of reasoning usually considered by logicians because it involves reasoning with multiple representations of information, and with complex rationale and goal structures. We describe an architecture for building applications to support design reasoning which generalizes traditional notions of proof to the case of real-world problem solving, including design reasoning.
Key words: heterogeneous reasoning, design, computational architecture.
Representing design ideas with hierarchical graph diagrams .
MGV vol. 12, no. 1, 2003, pp. 55-60.
Graphs are often used as formal models for representing design ideas. Models based on hierarchical graphs are needed in order to conveniently represent the structures of real-life objects. This paper presents a proposal of a design system which uses hierarchical graph transformation rules to automate the process of generating graph diagrams.
Key words: design, hierarchical graphs, double-pushout transformation rules.
Biegus L., Branki C.:
Bipartite graph approach to coordinating disparate workflows.
MGV vol. 12, no. 1, 2003, pp. 61-71.
This paper presents a way of modelling and executing inter-company workflows that require parallel-synchronised interoperability approach. The modelling is carried out using the concepts of coordination dialogue and bipartite graphs. Execution requires a kind of messaging service, which can conveniently be implemented with software agents.
Key words: workflow interoperability, coordination, bipartite graphs, agents.
MGV vol. 12, no. 1, 2003, pp. 73-82.
This paper discusses a class of diagrams that are often referred to by both experts and novices in any given domain of activity. This type of diagram is given the term 'Reference Diagram'. The paper will outline a definition of what the term 'Reference Diagram' alludes to as well as outline the characteristics of such diagrams. A case study is then reported which highlights a particular domain of activity (Case-Based Reasoning) and provides example of the class of diagrams in question. Furthermore, it is suggested in this paper that such is the importance of Reference Diagrams that they should be collected in order to maintain ease of access. This can be done in much the same way as with a set of maps, a compilation of pictures, a dictionary or thesaurus of words or an anthology of literature, such as a set of academic papers and articles of a particular domain.
Key words: reference diagrams, teaching and learning diagrams, educational diagrams, classification of diagrams.
Application of the combinatorial sequencing theory for innovative design based on diagrammatics.
MGV vol. 12, no. 1, 2003, pp. 83-98.
The paper proposes application of the combinatorial sequencing theory, namely the concept of Ideal Ring Bundles (IRBs), for design of high performance engineering devices or systems with non-uniform structure based on diagrammatics approach. An ordinary IRB is a ring-like sequence of positive integers which form perfect partitions of a finite interval [1,S] of integers. The sums of connected sub-sequences of an IRB enumerate the set of integers [1,S] exactly once. This property makes IRBs useful in applications which need to partition sets with the smallest possible number of intersections. Application of the idea of "perfect" combinatorial configurations for innovative design provides a better understanding of the role of a geometric structure in behavior of natural and man-made objects. It also helps configure systems with fewer elements and bonds than at present, while maintaining or improving on reliability, precision, resolving ability, and functionality, using combinatorial techniques based on the remarkable properties and structural perfection of one- and multidimensional IRBs. The objectives of the IRB concept are: development of a scientific basis for technologically optimum distributed systems theory using diagrammatic, generalization of these methods and results to the improvement and optimization of a larger class of technological systems, and development of new directions in fundamental and applied research in systems engineering based on diagrammatics for designing a whole range of high-performance devices, systems, or technologies, including applications to coded design of signals for communications and radar, positioning of elements in an antenna array, and other areas to which the IRB concept can be applied.
Key words: perfection, harmony, optimization, numerical diagram, geometrical diagram, innovative design, monolithic code, vector data code, non-redundant scale, vector data logistic management.
What makes a system less graphical?.
MGV vol. 12, no. 1, 2003, pp. 99-115.
Certain representation systems, loosely called "linguistic" ones, seem to lack the inferential efficiency, the expressive inflexibility, and the expressive richness possessed by certain other systems, loosely called "graphical" ones. This paper investigates the semantic mechanism underlying this intuitive phenomenon, and attributes a reason to the fact that semantic interpretation in "linguistic" systems is only applied to fairly specific properties of representations.
Key words: graphical representation, linguistic representation, diagrammatic reasoning, non-verbal communication, semantics of graphics.
Drewes F., Hoffmann B., Minas M.:
Context-exploiting shapes for diagram transformation.
MGV vol. 12, no. 1, 2003, pp. 117-132.
DiaPlan is a language for programming with graphs representing diagrams that is currently being developed. The computational model of the language - nested graph transformation - supports nested structuring of graphs and graph variables, but is still intuitive. This paper discusses structural typing of nested graphs and nested graph transformation systems by shape rules. We extend the context-free shape rules proposed in earlier work to context-exploiting shape rules with which many relevant graph structures can be specified. The conformance of a nested graph to the shape rules is decidable. If a transformation system conforms to shape rules as well, it can be shown to preserve shape conformance of the graphs it is applied to. This sets up a static type discipline for nested graph transformation.
Key words: graph transformation, diagram language, visual programming, data type.
Le T. L., Kulpa Z.:
MGV vol. 12, no. 1, 2003, pp. 133-146.
The diagrammatic spreadsheet concept is an attempt to develop a fully interactive animated diagrammatic system in which the transformation and animation of the diagram is interactively available to the user in a click-and-drag mode, and the description of what elements can move, and in what way (according to the required constraints between their components) can be also easily and interactively defined by the user. A constraint is used here like a formula in a spreadsheet, which is employed to automatically recompute the value of a cell whenever any other cells bound to it by the constraint undergo change. The graphical elements of the diagram play the role of spreadsheet cells, and their various attributes constitute the cell contents. The system may be used by human users for interactive exploration of diagrammatic representation and reasoning problems, or as a front-end to a more automatic diagrammatic inference system. In the paper, an overview of this concept and general construction principles of the system are described.
Key words: diagrams, diagrammatic representation, diagrammatic reasoning, graph transformations, diagrammatic spreadsheet, CP-graphs.
Self-consistency, imprecision, and impossible cases in diagrammatic representations.
MGV vol. 12, no. 1, 2003, pp. 147-160.
The main argument against the use of diagrams in rigorous reasoning is that they are unreliable. Thus, a serious error source analysis for this kind of reasoning should be undertaken, and proper diagrammatic reasoning procedures formulated as a result. As yet, little has been done in this matter. In this paper, one aspect of this problem is addressed, namely errors resulting in generation of so-called impossible cases in diagrammatic representations, violating the property of self-consistency claimed to hold for them. It is shown that the lack of self-consistency is in general due to limited analogicity of many diagrammatic representations, either because of limited precision of diagrams, or of certain structural properties of the visual language used. Several examples of these effects are shown and analyzed informally, with suggestions for possible remedies and for more formal analysis of the effects.
Key words: diagrammatic representation, diagrammatic reasoning, diagrammatic reasoning errors, analogicity limits, self-consistency, diagram imprecision, impossible cases, impossible figures.
Wang Y., Bhattacharya P.:
Using connected components to guide image understanding and segmentation.
MGV vol. 12, no. 2, 2003, pp. 163-186.
In this paper, we propose a method for understanding an image with the help of the theory of parameter-dependent connected components developed by us in a previous work. We may study various properties of an image at the connected component level, from the low level vision to an intermediate level vision. Using the information obtained from various component histograms and certain pre-knowledge, we describe how to select suitable values of the parameters so that an object in a gray image may be represented by a parameter-dependent component. Segmentation of the object could be conducted by locating the corresponding component. Our approach can be applied to a wide variety of images as we do not make any assumptions about the image formation model, and the method is independent of the type of the grid system used for the digitization process and the type of pixel adjacency relation.
Key words: gray image, connected components, image understanding, segmentation, intermediate level vision.
Holden E.-J., Owens R.:
Representing the finger-only topology for hand shape recognition.
MGV vol. 12, no. 2, 2003, pp. 187-202.
Automatic recognition of hand shapes in a moving image sequence requires the elements of hand tracking, feature extraction and classification. We have developed a robust tracking algorithm and a new hand shape representation technique that characterises the finger-only topology of the hand by adapting an existing technique from speech signal processing. The tracking algorithm determines the centre of the largest convex subset of the hand throughout an image sequence, using a combination of pattern matching and condensation algorithms. A hand shape feature represents the topological formation of the finger-only regions of the hand using a Linear Predictive Coding parameter set called cepstral coefficients. Feature extraction is performed on the polar dimensions of the hand region-of-interest, by tracking the finger-only region and extracting euclidean distances between the finger-only contour and the hand centre, which are then converted into cepstral coefficients. Experiments are conducted using mug-grabbing sequences to recognise four different hand shapes. Results demonstrate the robustness of hand tracking on cluttered backgrounds and the effectiveness of the hand shape representation technique on varying hand shapes.
Key words: hand shape representation, hand tracking, gesture recognition.
Yeates S., Holden E.-J., Owens R.:
An Animated Auslan Tuition System.
MGV vol. 12, no. 2, 2003, pp. 203-214.
The Auslan Tuition System uses a computer generated signer to provide a flexible, visual Australian Sign Language (Auslan) educational tool. Signs are generated and animated by our generic Human Modelling System that is implemented in cross-platform object-oriented C++. The Human Modelling System consists of three modules: the core Human Modelling Module for model construction, manipulation and forward kinematics; the Model Rendering Module for displaying model configuration visually using OpenGL; and the Model Interpolation Module, for providing flexible partial-keyframe interpolation and animation control. These modules form the basis of the Auslan Tuition System, and allow the display of categorised sign phrases, interactive fingerspelling and contextual sign dialogue examples. The user has complete viewing control of sign display and animation, running on modest hardware.
Key words: human movement animation, sign language translation, human modelling.
Label placement for dynamic objects.
MGV vol. 12, no. 2, 2003, pp. 215-234.
Placing object labels in dynamic scenes requires the label positions themselves to be dynamic. Algorithms for dynamic label placement are presented that tend to avoid overlaps and consider aesthetic preferences. The procedures are derived from a quadratic program. As a special feature, hysteresis is incorporated to restrict the optical flow induced by label changes.
Key words: graphical user interface, mixed reality, optical flow, quadratic programming.
A comparative discussion of distance transforms and simple deformations in digital image processing.
MGV vol. 12, no. 2, 2003, pp. 235-256.
The paper discusses algorithms for extracting essential properties of binary objects in digital images which are either based on distance transforms defined by different metrics or algorithms based on simple shape deformations. Thinning algorithms define one-way simple deformations. Two-way simple deformations transfer object points into background points and vice versa, without destroying the image topology. This article reviews contributions in this area with respect to properties of algorithms and characterizations of simple points, and informs about a few new results. A main intention of this article is the comparative discussion of experimental results and theoretical equivalences.
Key words: shape simplification, skeletonization, thinning, distance transform.
Horgan G. W.:
Variance and autocovariance filters for flexible and efficient texture assessment.
MGV vol. 12, no. 2, 2003, pp. 267-278.
The variance of image intensities in a moving window is an indicator of texture which can be calculated very efficiently and perhaps deserves to be more widely used. Ways in which it can be extended to comparisons of responses with different window sizes, to calculation of lagged autocorrelations and to anisotropic measurements are described and illustrated.
Key words: texture, variance, autocovariance.
Eghbali H. J.:
Adaptive digital image filtering in wavelet domain.
MGV vol. 12, no. 2, 2003, pp. 279-290.
In recent years wavelet transforms have been widely used for image denoising. This is because wavelet transform represents both the stationary and the transient behavior of the image. In this paper an adaptive filtering method is used for removing additive white Gaussian noise. It is based on statistics estimated from a local neighborhood of each wavelet coefficient. Denoising results compare favorably to the shrinkage denoising method, both perceptually and in terms of signal to noise ratio (SNR). The performance of the method is compared to shrinkage denoising method for both low and high (SNR) images.
Key words: image denoising, wavelet coefficients, shrinkage, statistic, adaptive filtering.
Madi M., Walton D.:
An interactive modification data structure for 3D surfaces.
MGV vol. 12, no. 3, 2003, pp. 293-310.
The design and display of 3D models on a computer screen is usually interleaved by a series of data manipulations. Data are usually sets of 3D points that make up polygonal patches in the composition of polyhedral models. Manipulations are the transformation operations that are applied to points to facilitate design and visual understanding of the graphical models. To further facilitate and speed up the design phase, methods are proposed to interactively segment and modify selected sub-surfaces, thereby limiting the number of patches that need to be manipulated for computationally cheaper and faster results. This paper illustrates how polyhedral surfaces can be organized into special data structures to facilitate rapid selection of vertices, and how those same surfaces can be segmented into sub-polyhedra for zooming and vertex manipulation during design, and can then be re-introduced as modified segments into the original structure. Algorithms and visual examples are also provided to support the work.
Key words: 3D surfaces, vertex selection, surface manipulation, triangular-loop data structure (TLDS).
Dharmaratne A., Harada K.:
Vertex correspondence between polygons in different applications.
MGV vol. 12, no. 3, 2003, pp. 311-333.
This paper describes some applications in computer graphics and computational geometry where establishing a vertex correspondence between a pair of objects is necessary. We present an algorithm for establishing a correspondence between the vertices of a pair of polygons by inserting new vertices, regardless of the polygons' locations, orientations, sizes, shapes, or numbers of vertices. The new vertices can be inserted either at the existing vertices or along the corresponding edges of the polygons. After establishing a successful correspondence between the vertices, its role in compatible convex decompositions, skeleton construction and polygon morphing is discussed.
Key words: vertex correspondence, polygon morphing, compatible convex decomposition.
MGV vol. 12, no. 3, 2003, pp. 335-352.
We describe a method for succinctly summarizing multi-dimensional data. It involves using computer-generated diagrams of faces in which the size of each feature is proportional to some parameter or dimension. Unlike the previous attempts by researchers to use face diagrams, our method insists that all facial features have constant locations, standard shapes and identical maximum possible sizes. This minimizes any tendency for observers to notice some facial parameters more than others or to interpret the face emotionally. We then present a case study in which our face diagrams were used by some advice-giving software to pictorialize different people's respective planning styles. The ability of our method to prompt new and deeper insights is highlighted.
Key words: multi-dimensional data, face diagrams, graphic communication, diagramming, decision making, planning.
Valev V., Asaithambi A.:
Fuzzy non-reducible descriptors.
MGV vol. 12, no. 3, 2003, pp. 353-361.
We present a model for supervised pattern recognition problems in which the features of patterns are fuzzy numbers. Non-Reducible Descriptors (NRDs) for such problems are obtained through the use of a threshold value, which is calculated based on the distance between patterns defined in a manner similar to Hamming distance between binary sequences. Boolean formulas are used to represent these Fuzzy NRDs. This model is useful in a wide variety of applications, and we illustrate its usefulness with a medical application.
Key words: supervised pattern recognition, fuzzy non-reducible descriptors, severe acute respiratory syndrome.
He X.C., Yu S.S., Zhou J. L., Li J.:
Context based multiwavelet image coding using SPIHT framework.
MGV vol. 12, no. 3, 2003, pp. 363-376.
In this paper, multiwavelets are considered in the context of image compression. For evaluating the effectiveness of multiwavelet transform for coding image at low bit-rates, an efficient embedded coding of wavelet coefficients has been realized. Firstly, selecting the BSA(4/4)* filters, two-dimensional (2-D) image is transformed with our proposed algorithm I. Secondly; we split the coefficients into two parts, namely the significance map and the residue map. Then a new modified algorithm for set partitioning in hierarchical trees (SPIHT) is proposed prencoding the significance map. Further, algorithm III is presented for coding the residue map. Finally, we adopt context-based adaptive arithmetic coding to encode the bit stream. We also provide some experimental results proving that multiwavelets are worth studying, and compare them with those of other multiwavelet and scalar wavelet algorithm.
Key words: multiwavelet, image compression, SPIHT, adaptive arithmetic coding, context.
Effective neural LUM smoother for image smoothing applications.
MGV vol. 12, no. 3, 2003, pp. 377-391.
In this paper, an effective image filtering approach for the impulsive noise suppression with the simultaneous signal-detail preservation is presented. The novelty of the proposed method lies in the combination of the LUM (lower-upper-middle) smoothing characteristics and the neural network. The included LUM-based impulse detector improves the signal-detail preservation capability of the proposed method, whereas the neural network along with the input LUM smoothers guarantee its noise attenuation capability. Since the LUM operation can be very efficiently implemented, the proposed method is computationally attractive and useful for practical image filtering applications.
Key words: LUM smoothers, impulsive noise, adaptive filtering, neural network, backpropagation, noise removal, image processing.
El-Henawy I., El-Areef T., Karawia A. A.:
On wavelets applications in medical image denoising.
MGV vol. 12, no. 3, 2003, pp. 393-404.
An important application domain of the wavelet theory is denoising. In this paper, we use the wavelet transforms to denoise the medical images. There are many kinds of noise and we study only three types i) additive random noise, ii) pop noise and iii) localized random noise. Further, we use Root Mean Square Error(RMSE) and Signal to Noise Ratio (SNR) to measure the error between a noisy image and the original image.
Key words: wavelet transform, noise modeling, image processing.
Two and a half dimensional models of convex polyhedra for visual identification.
MGV vol. 12, no. 3, 2003, p. 405.
Kowalczyk M., Mokrzycki S.W.:
Methods for generating 3D exact views of convex polyhedra for visual identification.
Part I: View sphere with perspective projection and iterative methods.
MGV vol. 12, no. 4, 2003, pp. 409-433.
The paper studies the methods of generating 3D exact multiview models of convex polyhedra for visual identification systems. In particular, an original view space concept (a view sphere with perspective projection) and the representation completeness controlling concept (a view sphere covering by single-view areas) as well as two groups of methods: iterative (part I of the paper) and non-iterative ones (part II) are characterized. A set of views generated by each method forms a complete view representation which is verified by controlling the view sphere covering by the so called single-view areas). The perspective projection used for calculating the views, the complete, tight covering of the view sphere by the single-view areas and 3-dimensionality of the views ensure unambiguous and proper identification of polyhedral objects.
Part I of our study presents the view sphere with perspective projection concept, the view sphere covering by the single-view areas mechanism, and the iterative methods generating feature-dependent views and reaching a complete view set through an iterative process of views generation.
Key words: object representation, distinguished features, 3D exact multiview model, visual object identification, view sphere with perspective projection, standardised views.
Kowalczyk M., Mokrzycki S.W.:
Methods for generating 3D exact views of convex polyhedra for visual identification.
Part II: Non-iterative methods, implementation and test results.
MGV vol. 12, no. 4, 2003, pp. 435-452.
This paper is the second part of our study describing methods for obtaining a 3D multiview exact and complete model of convex polyhedra used for visual identification. Non-iterative methods, like the iterative ones, explore the concept of the view sphere with perspective projection and the view sphere covering as a mechanism for representation completeness.
The non-iterative methods consist in calculating a view, determining the corresponding single-view area (the so-called seedling single-view area) and then searching for the neighbouring single-view areas (generating the views at the same time) in a spiral way until the whole view sphere is covered by the latter. Having a complete set of the single-view areas (complete view sphere covering), we get a complete set of views as well. Test results and computational complexity estimation are also included.
Key words: object representation, distinguished features, 3D exact multiview model, visual object identification, view sphere with perspective projection, standardised 3D views.
Ababsa F., Roussel D., Mallem M.:
Structured light 3D free form recovering with sub-pixel precision.
MGV vol. 12, no. 4, 2003, pp. 453-476.
This paper deals with the 3D Free form object pose recovering problem that is present in several industrial applications, such as online quality control in production as well as image systems for assembly/welding, augmented reality and robotics. The method presented here uses a structured light based vision system to reconstruct several accurate local 3D patches of the objects. A robust sub-pixel method for image features detection has been developed in order to increase 3D reconstruction accuracy. The curvature method is then used to compute a geometric invariant "footprint" to discriminate reconstructed patches, which allows to match them with the object's model. Pose recovering is performed by using the prediction-verification hypotheses paradigm. Some experimental results are given to show the efficiency of the proposed solution when applied to a complex free form object.
Key words: free form object, structured light, sub-pixel detection, 3D recovery, matching, geometric invariant, recognition by indexation.
Xu X.L., Harada K.:
Sequential projective reconstruction with factorization.
MGV vol. 12, no. 4, 2003, pp. 477-487.
The objective of the present study is to propose a new sequential projective factorization approach for recovering the structure and motion. In contrast to the previous sequential factorization methods or nonlinear filter methods, it starts with the first two images and the accurate result can be obtained even for the first image pair without considering provision of a reliable initial estimation. In each recursive step, the infinite sequences can be effectively handled while keeping the size of the factorization matrix unchanged. The experimental data in the paper show that sufficient accuracy can be attained with absence of noise.
Key words: sequential, projective factorization, structure from motion.
On the construction of transition functions for DPLL(k) automata for syntactic pattern recognition
MGV vol. 12, no. 4, 2003, pp. 489-513.
DPLL(k) automata have been introduced as a tool for inference support in pattern recognition-based real-time expert systems. The automata can be characterised by the two following features: they can recognise languages of a big descriptive power (quasi context sensitive languages), and they are efficient (i.e. they are of linear computational complexity). The two features make the automata useful in case of many practical applications, such as the on-line analysis of complex trend functions describing behaviour of industrial equipment. In this paper we present a method for construction of transition functions for the automata and a formal proof of its correctness.
Key words: syntactic pattern recognition, context sensitive languages, parsing.
El-henawy I., Karawia A.A.:
On wavelets applications in image compression.
MGV vol. 12, no. 4, 2003, pp. 515-524.
An important application domain of the wavelet theory is compression. In this paper, we use wavelet transforms to compress two different types of images (i) medical images (Echo image), (ii) color images, by using two different procedures. We use different types of wavelet transforms. Further, the compression ratio, the bits per pixel and the relative 2-norm difference are calculated. The quantitative measures are used to compare and contrast the performance of different wavelet transforms.
Key words: wavelet transform, image processing.
Saitoh T., Sato M., Kaneko T., Kuriyama S.:
Transient texture synthesis based on multiple templates.
MGV vol. 12, no. 4, 2003, pp. 525-537.
Texture synthesis based upon a sample image or template has attracted much attention recently. This paper describes a new blending algorithm for synthesizing a transient texture based upon two or more templates that gives an impression of a gradual transition from one template to another. Based upon a pair combination out of four templates, we synthesize six transitional textures. Then, we shown that various blending patterns can be designed by controlling the blending ratio maps. Based upon investigations of unsuccessful results of blending, we derive some necessary conditions on the statistical properties of templates for the applicability of this synthesis method.
Key words: texture synthesis, multiple templates, blending, contracting.
Contents of volume 12, 2003