Two-view “cylindrical decomposition” of binary images

This paper describes the discrete cylindrical algebraic decomposition (DCAD) construction along two orthogonal views of binary images. The combination of two information is used to avoid ambiguities for image recognition purposes. This algorithm associates an object connectivity graph to each connected component, allowing a complete description of the structuring information. Moreover, an easy and compact representation of the scene is achieved by using strings in a five letter alphabet. Examples on complex digital images are also provided. © 2001 Elsevier Science Inc.

Panel Summary One Model for Vision Systems?

This panel reports some considerations about the definition of vision-models. The panellists are scientists working on vision problems from different perspectives. The concept of model in vision seems to remain still open. In fact, it is dynamic, and context dependent. There exists the need for a better exchange of information, among biologists, engineers, physicists, and psychologists in order to improve our knowledge.

Representing 2D Digital Objects

The paper describes the combination a multi-views approach to represent connected components of 2D binary images. The approach is based on the Object Connectivity Graph (OCG), which is a sub-graph of the connectivity graph generated by the Discrete Cylindrical Algebraic Decomposition(DCAD) performed in the 2D discrete space. This construction allows us to find the number of connected components, to determine their connectivity degree, and to solve visibility problem. We show that the CAD construction, when performed on two orthogonal views, supply information to avoid ambiguities in the interpretation of each image component. The implementation of the algorithm is outlined and the computati…

A one class KNN for signal identification: a biological case study

The paper describes an application of a one class KNN to identify different signal patterns embedded in a noise structured background. The problem becomes harder whenever only one pattern is well-represented in the signal; in such cases, one class classifier techniques are more indicated. The classification phase is applied after a preprocessing phase based on a multi layer model (MLM) that provides preliminary signal segmentation in an interval feature space. The one class KNN has been tested on synthetic and real (Saccharomyces cerevisiae) microarray data in the specific problem of DNA nucleosome and linker regions identification. Results have shown, in both cases, a good recognition rate.

Soft Computing and Image Analysis

The paper describes a soft approach to solve image analysis problems. Theory of fuzzy-sets has been used to implement most of the algorithms described in the paper. Soft approaches can be useful to extend mathematical morphology operators on gray level images and to describe the shape of dotted objects. Examples on real data are also provided.

An unsupervised region growing method for 3D image segmentation

The paper deals with 3D shape decomposition problem, objects are modelled as finite unions of almost-convex primitives. A new region growing method is proposed to extract meaningful objects parts. Parts are individuated by performing a set-partitioning of surface dominating points. The partition step returns labelled seeds from which to start a region growing procedure that propagate labels onto object surface patches. A fuzzy concept of λ-convexity is introduced to test noised real images. Experimental results are given.

A memetic approach to discrete tomography from noisy projections

Discrete tomography deals with the reconstruction of images from very few projections, which is, in the general case, an NP-hard problem. This paper describes a new memetic reconstruction algorithm. It generates a set of initial images by network flows, related to two of the input projections, and lets them evolve towards a possible solution, by using crossover and mutation. Switch and compactness operators improve the quality of the reconstructed images during each generation, while the selection of the best images addresses the evolution to an optimal result. One of the most important issues in discrete tomography is known as the stability problem and it is tackled here, in the case of no…

Clustering Algorithms for MRI

Magnetic Resonance Imaging (MRI) plays a relevant role in the design of systems for computer assisted diagnosis. MR-images are multi-dimensional in nature; physicians have to combine several perceptual information images to perform the tissue classification needed for diagnosis. Automatic clustering methods help to discriminate relevant features and to perform a preliminary segmentation of the image; it can guide the final manual classification of body-tissues. Three clustering techniques and their integration in a MRI-system are described. Their performance and accuracy was evaluated on synthetic and real image-data. A comparison of our approach with the tissue-classification done by a rad…

A MULTI-LAYER MODEL TO STUDY GENOME-SCALE POSITIONS OF NUCLEOSOMES

The positioning of nucleosomes along chromatin has been implicated in the regulation of gene expression in eukaryotic cells, because packaging DNA into nucleosomes affects sequence accessibility. In this paper we propose a new model (called MLM) for the identification of nucleosomes and linker regions across DNA, consisting in a thresholding technique based on cut-set conditions. For this purpose we have defined a method to generate synthetic microarray data fully inspired from the approach that has been used by Yuan et al. Results have shown a good recognition rate on synthetic data, moreover, the $MLM$ shows a good agreement with the recently published method based on Hidden Markov Model …

Distance-based functions for image comparison

The interest in digital image comparison is steadily growing in the computer vision community. The definition of a suitable comparison measure for non-binary images is relevant in many image processing applications. Visual tasks like segmentation and classification require the evaluation of equivalence classes. Measures of similarity are also used to evaluate lossy compression algorithms and to define pictorial indices in image content based retrieval methods. In this paper we develop a distance-based approach to image similarity evaluation and we present several image distances which are based on low level features. The sensitivity and eAectiveness are tested on real data. ” 1999 Published…

Pyramid symmetry transforms: From local to global symmetry

Pyramid computation is a natural paradigm of computation in planning strategies and multi-resolution image analysis. This paper introduces a new paradigm that is based on the concept of soft-hierarchical operators implemented in pyramid architecture to retrieve global versus local symmetries. The concept of symmetry is mathematically well defined in geometry whenever patterns are crisp images (two levels). Necessity for a soft approach occurs with multi-levels images and whenever the separation between object and background is subjective or not well defined. The paper describes two new pyramid operators to detect symmetries based on previously introduced conventional operators. For sake of …

Representation of knowledge using Fuzzy set theory

Shape-Based Features for Cat Ganglion Retinal Cells Classification

This article presents a quantitative and objective approach to cat ganglion cell characterization and classification. The combination of several biologically relevant features such as diameter, eccentricity, fractal dimension, influence histogram, influence area, convex hull area, and convex hull diameter are derived from geometrical transforms and then processed by three different clustering methods (Ward’s hierarchical scheme, K-means and genetic algorithm), whose results are then combined by a voting strategy. These experiments indicate the superiority of some features and also suggest some possible biological implications.

Trends in pattern recognition

Aims of this paper are to present a short history of pattern recognition, its current areas of interest and future developments. The term pattern recognition is vague, its related topics including the study of sensorial stimuli, the analysis of physical phenomena and models of reasoning. Here we concentrate our attention on visual patterns and the machines that have been realized in order perform automatic pattern recognition. Some theoretical approaches will be also reviewed.

Symmetry operators in computer vision

Abstract Symmetry plays a remarkable role in perception problems. For example, peaks of brain activity are measured in correspondence with visual patterns showing symmetry . Relevance of symmetry in vision was already noted by Koler in 1929. Here, properties of a symmetry operator are reported and a new algorithm to measure local symmetries is proposed. Its performance is tested on segmentation of complex visual patterns and the classification of sparse images.

Symmetry as an Intrinsically Dynamic Feature

Symmetry is one of the most prominent spatial relations perceived by humans, and has a relevant role in attentive mechanisms regarding both visual and auditory systems. The aim of this paper is to establish symmetry, among the likes of motion, depth or range, as a dynamic feature in artificial vision. This is achieved in the first instance by assessing symmetry estimation by means of algorithms, putting emphasis on erosion and multi- resolution approaches, and confronting two ensuing problems: the isolation of objects from the context, and the pertinence (or lack thereof) of some salient points, such as the centre of mass. Next a geometric model is illustrated and detailed, and the problem …

Discrete Tomography Reconstruction Through a New Memetic Algorithm

Discrete tomography is a particular case of computerized tomography that deals with the reconstruction of objects made of just one homogeneous material, where it is sometimes possible to reduce the number of projections to no more than four. Most methods for standard computerized tomography cannot be applied in the former case and ad hoc techniques must be developed to handle so few projections.

Experiments on Concurrent Artificial Environment

We show how the simulation of concurrent system is of interest for both behavioral studies and strategies of learning applied on prey-predator problems. In our case learning studies into unknown environment have been applied to mobile units by using genetic algorithms (GA). A set of trajectories, generated by GA, are able to build a description of the external scene driving a predators to a prey. Here, an example of prey-predator strategy,based on field of forces, is proposed. The evolution of the corespondent system can be formalized as an optimization problem and, for that purpose, GA can be use to give the right solution at this problem. This approach could be applied to the autonomous r…

S_Kernel: A New Symmetry Measure

Symmetry is an important feature in vision. Several detectors or transforms have been proposed. In this paper we concentrate on a measure of symmetry. Given a transform S, the kernel SK of a pattern is defined as the maximal included symmetric sub-set of this pattern. It is easily proven that, in any direction, the optimal axis corresponds to the maximal correlation of a pattern with its flipped version. For the measure we compute a modified difference between respective surfaces of a pattern and its kernel. That founds an efficient algorithm to attention focusing on symmetric patterns.

A multi-layer method to study genome-scale positions of nucleosomes

AbstractThe basic unit of eukaryotic chromatin is the nucleosome, consisting of about 150 bp of DNA wrapped around a protein core made of histone proteins. Nucleosomes position is modulated in vivo to regulate fundamental nuclear processes. To measure nucleosome positions on a genomic scale both theoretical and experimental approaches have been recently reported. We have developed a new method, Multi-Layer Model (MLM), for the analysis of nucleosome position data obtained with microarray-based approach. The MLM is a feature extraction method in which the input data is processed by a classifier to distinguish between several kinds of patterns. We applied our method to simulated-synthetic and…

Combining one class fuzzy KNN’s

This paper introduces a parallel combination of N > 2 one class fuzzy KNN (FKNN) classifiers. The classifier combination consists of a new optimization procedure based on a genetic algorithm applied to FKNN’s, that differ in the kind of similarity used. We tested the integration techniques in the case of N = 5 similarities that have been recently introduced to face with categorical data sets. The assessment of the method has been carried out on two public data set, the Masquerading User Data (www.schonlau.net) and the badges database on the UCI Machine Learning Repository (http://www.ics.uci.edu/~mlearn/). Preliminary results show the better performance obtained by the fuzzy integration …

Symmetry in Computer Vision

Symmetry properties establish the invariance of a system to a given set of transformations. Physicists assign special meaning whenever symmetry is broken in nature; for example, groups of symmetry have been used to explain and predict the spatial organization of atoms in a crystal. Psychologists consider relevant the property of symmetry in the perception of visual signals. The paper will briefly describe different approaches, introduced in computer vision, to measure symmetry. A review of some applications at the Computer Vision Group (Department of Mathematics and Applications of Palermo University) is presented. They regard attentive visual processing, the analysis of faces, the recognit…

The S-kernel: A measure of symmetry of objects

In this paper we introduce a new symmetry feature named ''symmetry kernel'' (SK) to support a measure of symmetry. Given any symmetry transform S, SK of a pattern P is the maximal included symmetric sub-set of P for all directions and shifts. We provide a first algorithm to exhibit this kernel where the centre of symmetry is assumed to be the centre of mass. Then we prove that, in any direction, the optimal axis corresponds to the maximal correlation of a pattern with its symmetric version. That leads to a second algorithm. The associated symmetry measure is a modified difference between the respective surfaces of a pattern and its kernel. A series of experiments supports the actual algorit…

A cooperating strategy for objects recognition

The paper describes an object recognition system, based on the co-operation of several visual modules (early vision, object detector, and object recognizer). The system is active because the behavior of each module is tuned on the results given by other modules and by the internal models. This solution allows to detect inconsistencies and to generate a feedback process. The proposed strategy has shown good performance especially in case of complex scene analysis, and it has been included in the visual system of the DAISY robotics system. Experimental results on real data are also reported.

A one class classifier for Signal identification: a biological case study

The paper describes an application of a one-class KNN to identify different signal patterns embedded in a noise structured background. The problem become harder whenever only one pattern is well represented in the signal, in such cases one class classifier techniques are more indicated. The classification phase is applied after a preprocessing phase based on a Multi Layer Model (MLM) that provides a preliminary signal segmentation in an interval feature space. The one-class KNN has been tested on synthetic data that simulate microarray data for the identification of nucleosomes and linker regions across DNA. Results have shown a good recognition rate on synthetic data for nucleosome and lin…

Suitability of a content-based retrieval method in astronomical image databases

Abstract Indexing and retrieval methods based on the image content are required to effectively use information from large repositories of digital images. Usually, the way to search for data and images in astronomical archives is via textual queries expressed in terms of constraints on observation parameters. In this paper we present a method for automatic extraction of images by using shape descriptions based on local symmetry. The proposed indexing methodology has been developed and tested inside JACOB, a prototypal system for content-based video database querying.

A fuzzy approach to the evaluation of image complexity

The inherently multidimensional problem of evaluating the complexity of an image is of a certain relevance in both computer science and cognitive psychology. Computer scientists usually analyze spatial dimensions in order to deal with automatic vision problems, such as feature extraction. Psychologists seem more interested in the temporal dimension of complexity, as a means to explore attentional models. Is it possible to define, by merging both approaches, a more general index of visual complexity? The aim of this paper is the definition of objective measures of image complexity that fits with the so named perceived time. Towards the end we have defined a fuzzy mathematical model of visual…

Kernel Based Symmetry Measure

In this paper we concentrate on a measure of symmetry. Given a transform S, the kernel SK of a pattern is defined as the maximal included symmetric sub-set of this pattern. A first algorithm is outlined to exhibit this kernel. The maximum being taken over all directions, the problem arises to know which center to use. Then the optimal direction triggers the shift problem too. As for the measure we propose to compute a modified difference between respective surfaces of a pattern and its kernel. A series of experiments supports actual algorithm validation.

A note on the iterative object symmetry transform

This paper introduces a new operator named the iterated object transform that is computed by combining the object symmetry transform with the morphological operator erosion. This new operator has been applied on both binary and gray levels images showing the ability to grasp the internal structure of a digital object. We present also some experiments on artificial and real images and potential applications.

A heterogeneous and reconfigurable machine-vision system

This paper describes a new machine-vision system, a HERMIA heterogeneous and reconfigurable machine for image analysis. The architecture topology of the HERMIA machine is reconfigurable; moreover, the integration of its special modules allows a search for optimal strategies to solve vision problems. The general architecture and the hardware implementation are described. The software environment of the HERMIA machine provides a full iconic interface and a pictorial language oriented to vision in multiprocessor architectures. The preliminary system evaluation and applications are shown. © 1995 Springer-Verlag.

Early Vision and Soft Computing

The term soft-computing has been introduced by Zadeh in 1994. Soft-computing provides an appropriate paradigm to program malleable and smooth concepts. For example, it can be used to introduce flexibility in artificial systems and possibly to improve their Intelligent Quotient. Aim of this paper is to describe the applicability of soft-computing to early vision problems. The good performance of this approach is claimed by the fact that digital images are examples of fuzzy entities, where geometry of shapes are not always describable by exact equations and their approximation can be very complex.

Iterative Symmetry Detection: Shrinking vs. Decimating Patterns

This paper introduces a new mechanism that consists of applying a symmetry operator on an iteratively transformed version of the input image. The nature of the transformation characterizes the operator. Here, we consider the Object Symmetry Transform combined with the morphological operator erosion and the pyramid decimation respectively. The derived operators have been applied on both binary and gray levels images, comparing their ability to grasp the internal structure of a digital object. We present some experiments to evaluate their performances and check them for result quality versus computing complexity.

Compression of binary images based on covering

The paper describes a new technique to compress binary images based on an image covering algorithm. The idea is that binary images can be always covered by rectangles, univocally described by a vertex and two adjacent edges (L-shape). Some optimisations are necessary to consider degenerate configurations. The method has been tested on several images representing drawings and typed texts. The comparison with existing image file compression techniques shows a good performance of our approach. Further optimisations are under development.

Entropy measures in Image Classification

A Memetic Algorithm for Binary Image Reconstruction

This paper deals with a memetic algorithm for the reconstruction of binary images, by using their projections along four directions. The algorithm generates by network flows a set of initial images according to two of the input projections and lets them evolve toward a solution that can be optimal or close to the optimum. Switch and compactness operators improve the quality of the reconstructed images which belong to a given generation, while the selection of the best image addresses the evolution to an optimal output.

Interval Length Analysis in Multi Layer Model

In this paper we present an hypothesis test of randomness based on the probability density function of the symmetrized Kulback-Leibler distance estimated, via a Monte Carlo simulation, by the distributions of the interval lengths detected using the Multi-Layer Model (MLM). The $MLM$ is based on the generation of several sub-samples of an input signal; in particular a set of optimal cut-set thresholds are applied to the data to detect signal properties. In this sense MLM is a general pattern detection method and it can be considered a preprocessing tool for pattern discovery. At the present the test has been evaluated on simulated signals which respect a particular tiled microarray approach …

Local operators to detect regions of interest

The performance of a visual system is strongly influenced by the information processing that is done in the early vision phase. The need exists to limit the computation on areas of interest to reduce the total amount of data and their redundancy. This paper describes a new method to drive the attention during the analysis of complex scenes. Two new local operators, based on the computation of local moments and symmetries, are combined to drive the selection. Experimental results on real data are also reported. © 1997 Elsevier Science B.V.

Artificial Vision and Soft Computing

The term soft-computing has been introduced by Zadeh in 1994. Soft-computing provides an appropriate paradigm to program malleable and smooth concepts. For example, it can be used to introduce flexibility in artificial systems to improve their Intelligent Quotient. The aim of this paper is to describe the applicability of soft-computing to artificial vision problems. Good performance of this approach is assured by the fact that digital images are examples of fuzzy entities, where shapes are not always describable by exact equations and their approximation can be very complex.

A new heterogeneous and reconfigurable architecture for image analysis

In the paper a new architecture for image analysis: HERMIA (Heterogeneous and Reconfigurable Machine for Image Analysis) is presented. It has bt:en developed at the University of Palermo, inside the Progetto Finalizzato of the ltalian Council of Researches (CNR): Sistemi informatici e Calcolo Parallelo. The architecture of the HERMIA-machine is reconfigurable, moreover the integration of heterogeneous module, oriented to the solution of specific problems, allows to salve complex problems by search of optimal strategies. Signa! processing units allows the user to handle and integrate multi-sensors signals (from video, scanner, music recorder). Here the generai architecture, the hardware impl…

Data Analysis and Bioinformatics

Data analysis methods and techniques are revisited in the case of biological data sets. Particular emphasis is given to clustering and mining issues. Clustering is still a subject of active research in several fields such as statistics, pattern recognition, and machine learning. Data mining adds to clustering the complications of very large data-sets with many attributes of different types. And this is a typical situation in biology. Some cases studies are also described.

A genetic integrated fuzzy classifier

This paper introduces a new classifier, that is based on fuzzy-integration schemes controlled by a genetic optimisation procedure. Two different types of integration are proposed here, and are validated by experiments on real data sets of biological cells. The performance of our classifier is tested against a feed-forward neural network and a Support Vector Machine. Results show the good performance and robustness of the integrated classifier strategies.

On the Evaluation of Images Complexity: A Fuzzy Approach

The inherently multidimensional problem of evaluating the complexity of an image is of a certain relevance in both computer science and cognitive psychology. Computer scientists usually analyze spatial dimensions, to deal with automatic vision problems, such as feature-extraction. Psychologists seem more interested in the temporal dimension of complexity, to explore attentional models. Is it possible, by merging both approaches, to define an more general index of visual complexity? We have defined a fuzzy mathematical model of visual complexity, using a specific entropy function; results obtained by applying this model to pictorial images have a strong correlation with ones from an experime…

Fusion of experimental data

Abstract The integration of information from various sensory systems is one of the most difficult challenges in understanding both perception and cognition. For example, the problem of auditory-visual integration is a correspondence problem between perceived auditory and visual scenes. Two main questions arise when designing data analysis systems: what is the useful information to be integrated?, and what are the integration rules? The problem of integrating information becomes relevant whenever: (a) the same kind of data are detected by spatially distributed sensors; (b) heterogeneous data are detected by different sensors; (c) heterogeneous distributed data are involved. General problems …

Soft Pyramid Symmetry Transforms

Pyramid computation is a natural paradigm of computation in planning strategies and multi-resolution image analysis. This paper introduces a new paradigm that is based on the concept of soft-hierarchical operators implemented in a pyramid architecture to retrieve global versus local symmetries. The concept of symmetry is mathematically well defined in geometry whenever patterns are crisp images (two levels). Necessity for a soft approach occurs whenever images are multi-levels and the separation between object and background is subjective or not well defined. The paper describes a new pyramid operator to detect symmetries and shows some experiments supporting the approach. This work has bee…

New Similarity Rules for Mining Data

Variability and noise in data-sets entries make hard the discover of important regularities among association rules in mining problems. The need exists for defining flexible and robust similarity measures between association rules. This paper introduces a new class of similarity functions, SF's, that can be used to discover properties in the feature space X and to perform their grouping with standard clustering techniques. Properties of the proposed SF's are investigated and experiments on simulated data-sets are also shown to evaluate the grouping performance.

Genome-wide characterization of chromatin binding and nucleosome spacing activity of the nucleosome remodelling ATPase ISWI

The evolutionarily conserved ATP-dependent nucleosome remodelling factor ISWI can space nucleosomes affecting a variety of nuclear processes. In Drosophila, loss of ISWI leads to global transcriptional defects and to dramatic alterations in higher-order chromatin structure, especially on the male X chromosome. In order to understand if chromatin condensation and gene expression defects, observed in ISWI mutants, are directly correlated with ISWI nucleosome spacing activity, we conducted a genome-wide survey of ISWI binding and nucleosome positioning in wild-type and ISWI mutant chromatin. Our analysis revealed that ISWI binds both genic and intergenic regions. Remarkably, we found that ISWI…

GenClust: A genetic algorithm for clustering gene expression data

Abstract Background Clustering is a key step in the analysis of gene expression data, and in fact, many classical clustering algorithms are used, or more innovative ones have been designed and validated for the task. Despite the widespread use of artificial intelligence techniques in bioinformatics and, more generally, data analysis, there are very few clustering algorithms based on the genetic paradigm, yet that paradigm has great potential in finding good heuristic solutions to a difficult optimization problem such as clustering. Results GenClust is a new genetic algorithm for clustering gene expression data. It has two key features: (a) a novel coding of the search space that is simple, …

A PARALLEL ALGORITHM FOR ANALYZING CONNECTED COMPONENTS IN BINARY IMAGES

In this paper, a parallel algorithm for analyzing connected components in binary images is described. It is based on the extension of the Cylindrical Algebraic Decomposition (CAD) to a two-dimensional (2D) discrete space. This extension allows us to find the number of connected components, to determine their connectivity degree, and to solve the visibility problem. The parallel implementation of the algorithm is outlined and its time/space complexity is given.

PDB: A pictorial database oriented to data analysis

The paper describes a new pictorial database oriented to image analysis, implemented inside the MIDAS data analysis system. Pictorial databases need expressive data structures in order to represent a wide class of information from the numerical to the visual. The model of the database is relational; however, a full normalization is not achievable, owing to the complexity of the visual information. The paper reports the general design and notes on the software implementation. Preliminary experiments show the performance of the pictorial database. Copyright © 1993 John Wiley & Sons, Ltd

Image Segmentation based on Genetic Algorithms Combination

The paper describes a new image segmentation algorithm called Combined Genetic segmentation which is based on a genetic algorithm. Here, the segmentation is considered as a clustering of pixels and a similarity function based on spatial and intensity pixel features is used. The proposed methodology starts from the assumption that an image segmentation problem can be treated as a Global Optimization Problem. The results of the image segmentations algorithm has been compared with recent existing techniques. Several experiments, performed on real images, show good performances of our approach compared to other existing methods.

A new Multi-Layers Method to Analyze Gene Expression

In the paper a new Multi-Layers approach (called Multi-Layers Model MLM) for the analysis of stochastic signals and its application to the analysis of gene expression data is presented. It consists in the generation of sub-samples from the input signal by applying a threshold technique based on cut-set optimal conditions. The MLM has been applied on synthetic and real microarray data for the identification of particular regions across DNA called nucleosomes and linkers. Nucleosomes are the fundamental repeating subunits of all eukaryotic chromatin, and their positioning provides useful information regarding the regulation of gene expression in eukaryotic cells. Results have shown a good rec…

Panel Summary: Planning And Plasticity in Artificial and Natural Systems

Boncinelli underlined often, during our workshop, that simplest organisms are the more robust and they survived longer than more evolved organisms (what about the quality of their life?). This depends on the fact that complex systems either natural or artificial need for more complex controls. Moreover, planning strategies, one of the steps for finding optimal solutions, must be carefully designed and it is complex too.

A High Level Language for Pyramidal Architectures

In the paper are described the syntax and some implementation features of a high level language for pyramidal architectures called Pyramid B Language (PCL). The language is an extension of the B and include data type, set of instructions and builtin functions oriented to the pyramidal architectures. Some notes on the implementation for the PAPIA machine are also given.