Nowadays a huge amount of digital data are generated every moment in a broad spectrum of application domains such as biomedical imaging, document processing, geosciences, remote sensing, video surveillance, etc. Processing such big data requires an efficient data structure, encouraging the algorithms with lower complexity and parallel operations. In this paper, first, a new method for computing the distance transform (DT) as the fundamental operation in binary images is presented. The method computes the DT with the parallel logarithmic complexity O(log(n)) where n is the maximum diameter of the largest foreground region in the 2D binary image. Second, we define the DT in the combinatorial map (CM) structure. In the CM, by replacing each edge with two darts a smoother DT with the double resolution is derived. Moreover, we compute n different distances for the nD-map. Both methods use the hierarchical irregular pyramid structure and have the advantage of preserving topological information between regions. The operations of the proposed algorithms are totally local and lead to parallel implementations. The GPU implementation of the algorithm has high performance while the bottleneck is the bandwidth of the memory or equivalently the number of available independent processing elements. Finally, the logarithmic complexity of the algorithm speeds up the execution and suits it. particularly for large images.

A structure preserving irregular image pyramid can be computed by applying basic graph operations (contraction and removal of edges) on the 4 adjacent neighbourhood graph of an image. In this paper, we derive an objective function that classifies the edges as contractible or removable for building an irregular graph pyramid. The objective function is based on the cost of the edges in the contraction kernel (sub-graph selected for contraction) together with the size of the contraction kernel. Based on the objective function, we also provide an algorithm that decomposes a 2D image into monotonically connected regions of the image surface, called slope regions. We proved that the proposed algorithm results in a graph-based irregular image pyramid that preserves the structure and the topology of the critical points (the local maxima, the local minima, and the saddles). Later we introduce the concept of the dictionary for the connected components of the contraction kernel, consisting of sub-graphs that can be combined together to form a set of contraction kernels. A favorable contraction kernel can be selected that best satisfies the objective function. Lastly, we show the experimental verification for the claims related to the objective function and the cost of the contraction kernel. The outcome of this paper can be envisioned as a step towards learning the contraction kernel for the construction of an irregular image pyramid

In this paper the properties of the generalized conics are used to create a unified framework for generating various types of the distance fields. The main concept behind this work is a metric that measures the distance from a point to a line segment according to the definition of the ellipse. The proposed representation provides a possibility to efficiently compute the proximity, arithmetic mean of the distances and a space tessellation with regard to the given set of polygonal objects, line segments and points. In addition, the weights can be introduced for objects, their parts and combinations. This fact leads to a hierarchical representation that can be efficiently obtained using the pixel-wise operations. The practical value of the proposed ideas is demonstrated on an example of applications like skeletonization, smoothing and optimal location finding.

The paper introduces a novel confocal ellipse-based distance (CED), that is based on the properties of the confocal ellipses. This distance is used to produce a confocal elliptical field (CEF). The Euclidean Distance Transform (EDT) of a single point (called seed) generates a distance field of concentric circles. The sum of two such distance fields of two distinct seed points produces a distance field of confocal ellipses. This fact enables to adapt CED and CEF to the discrete case, referred to as CED-DT and CEF-DT. The properties of the CEF and CEF-DT make them useful for skeletonization, in particular for efficient removal of the spurious branches.

In this paper, we present a novel distance metric called Segmentation Edit Distance (SED) and its use as a segmentation evaluation metric. In segmentation evaluation, the difference or distance of a test segmentation and the associated ground truth segmentation are measured in order to compare different algorithms. Our proposed edit distance extends the idea of other edit distances such as the string edit distance or the graph edit distance to the domain of image segmentations. The distance is based on the cost of edit operations that are needed to transform one segmentation into another. Only one edit operation, the deletion of an error region, is considered. Different to other edit distances, the costs assigned to this operation are based on properties of the error regions and the image processing method used to delete a region. As a segmentation evaluation metric, it combines the assessment of accuracy and efficiency into a single metric. Evaluations on synthetic and real world data show promising results compared to other state of the art segmentation evaluation metrics.

In this paper we present a novel algorithm to optimize the reconstruction from non-uniform point sets. We introduce a statistically-derived topology-controller for selecting the reconstruction resolution of a given non-uniform point set. Deriving information from homology-based statistics, our topology-controller ensures a stable and sound basis for the analysis process. By analyzing our topology-controller, we select an optimal reconstruction resolution which ensures both low reconstruction errors and a topological stability of the underlying signal. Our approach offers a valuable method for the evaluation of the reconstruction process without the need of visual inspection of the reconstructed datasets. By means of qualitative results we show how our proposed topology statistics provides complementary information in the enhancement of existing reconstruction pipelines in visualization.

This paper presents a flexible framework to build a target-specific, part-based representation for arbitrary articulated or rigid objects. The aim is to successfully track the target object in 2D, through multiple scales and occlusions. This is realized by employing a hierarchical, iterative optimization process on the proposed representation of structure and appearance. Therefore, each rigid part of an object is described by a hierarchical spring system represented by an attributed graph pyramid. Hierarchical spring systems encode the spatial relationships of the features (attributes of the graph pyramid) describing the parts and enforce them by spring-like behavior during tracking. Articulation points connecting the parts of the object allow to transfer position information from reliable to ambiguous parts. Tracking is done in an iterative process by combining the hypotheses of simple trackers with the hypotheses extracted from the hierarchical spring systems.

This paper presents a method to extract a part-based model of an observed scene from a video sequence. Independent motion is a strong cue that two points belong to different "rigid" entities. Conversely, things that move together throughout the whole video belong together and define a "rigid" object or part. Successfully tracked features indicate trajectories of salient points in the scene. A triangulated graph connects the salient points and encodes their local neighborhood in the first frame. The length variation of the triangle edges is used to label them as relevant (on an object) or separating (connecting different objects). A following grouping process uses the motion of the triangles marked as relevant as a cue to identify the "rigid" parts of the foreground or the background. The choice of the motion-based grouping criterion depends on the type of motion: in the image plane or out of the image plane. The result is a hierarchical description (graph pyramid) of the scene, where each vertex in the top level of the pyramid represents a "rigid" part of the foreground or the background, and encloses to the salient features used to describe it. Promising experimental results show the potential of the approach.

A framework for mapping a polar-like coordinate system to a non-rigid shape is presented. Using a graph pyramid, a binary shape is decomposed into connected parts, based on its structure as captured by the eccentricity transform. The decomposition is used to derive domains for the angular like coordinate. A closest point search is employed to find point correspondences.

When matching regions from "similar" images, one typically has the problem of missing counterparts due to local or even global variations of segmentation fineness. Matching segmentation hierarchies, however, not only increases the chances of finding counterparts, but also allows us to exploit the manifold constraints coming from the topological relations between any two regions in a hierarchy. To define the topological relations we represent a plane image ℐ by a plane attributed graph G and derive a finite topology [Formula: see text] from G. In particular, segmenting ℐ corresponds to taking a topological minor of G which, in turn, is equivalent to coarsening [Formula: see text]. Moreover, each finite topology involved is a coarsening of the standard topology on ℝ2. Then, we construct a weighted association graph GA, the nodes of which represent potential matches and the edges of which indicate topological consistency with respect to [Formula: see text]. Specifically, a maximal weight clique of GAcorresponds to a topologically consistent mapping with maximal total similarity. To find "heavy" cliques, we extend a greedy pivoting-based heuristic to the weighted case. Experiments on pairs of stereo images, on a video sequence of a cluttered outdoor scene, and on a sequence of panoramic images demonstrate the effectiveness of our method.

An irregular pyramid consists of a stack of successively reduced graphs. Each smaller graph is deduced from the preceding one by the contraction or the removal of a set of edges. Using a fixed decimation ratio we need approximately O(log(image size)) graphs to encode the whole pyramid. A combinatorial map encodes a planar graph thanks to two permutations encoding the edges and their orientation around the vertices. We present in this article an encoding of a combinatorial pyramid which allows to fold the whole pyramid in the base level layer and provides at the same time a measure of the relevance of every pixel. This encoding is used to retrieve any reduced combinatorial map of the pyramid from its base and to compute the borders of the partition encoded by the combinatorial maps.

Fingerprint recognition and verification are often based on local fingerprint features, usually ridge endings or terminations, also called minutiae. By exploiting the structural uniqueness of the image region around a minutia, the fingerprint recognition performance can be significantly enhanced. However, for most fingerprint images the number of minutia image regions (MIRs) becomes dramatically large, which imposes - especially for embedded systems - an enormous memory requirement. Therefore, we are investigating different algorithms for compression of minutia regions. The requirement for these algorithms is to achieve a high compression rate (about 20) with minimum loss in the matching performance of minutia image region matching. We investigate the matching performance for compression algorithms based on the principal component and the wavelet transformation. The matching results are presented in form of normalized ROC curves and interpreted in terms of compression rates and the MIR dimension.

A framework is presented that produces the mosaic corresponding to the background object of an image sequence. It is based on the dominant motion assumption, which states that the background has a parametric motion and occupies the main part of the images. The foreground objects are localised by their different motion. This localisation is computed together with the background motion in an iterative method. The regions corresponding to the background are then pasted onto the mosaic using classic methods adapted to object elimination or a new mosaicking method based on a striping that takes the foreground objects localisation into account.

Content based image retrieval is the task of searching images from a database, which are visually similar to a given example image. We present methods for content based image retrieval based on texture similarity using interest points and Gabor features. Interest point detectors are used in computer vision to detect image points with special properties, which can be geometric (corners) or non-geometric (contrast etc.). Gabor functions and Gabor filters are regarded as excellent tools for feature extraction and texture segmentation. The article combines these methods and generates a textural description of images. Special emphasis is devoted to distance measures on texture descriptions. Experimental results of a query system are given.

The matching of an object, a region of an image segmentation, to a template is a heavy computation process and is not very robust. We represent an object by a region adjacency graph (RAG) on the top of which a pyramid (a decreasing sequence of RAG) is built according to a set of rules, which verify some uniqueness and uniformity properties. The contraction process preserves the structure of the RAG across the pyramid's levels, and the rules are chosen according to the characteristics of the template. By building such a pyramid and then by a top-down process to match all the sub-graphs we have a linear parallel complexity time, with a robust match and a partial match relative to the given set of rules.

Dual graph contraction reduces the number of vertices and of edges of a pair of dual image graphs while, at the same time, the topological relations among the 'surviving' components are preserved. Repeated application produces a stack of successively smaller graphs: a pair of dual irregular pyramids. The process is controlled by selected decimation parameters which consist of a subset of surviving vertices and associated contraction kernels. Equivalent contraction kernels (ECKs) combine two or more contraction kernels into one single contraction kernel which generates the same result in one single dual contraction. This is the basis to the proof that any segmentation can be represented in one single level of such a pyramid. Experimental results demonstrate the applicability on synthetic and real images respectively.

This paper describes an extension of the binary curve pyramid to curves with strengths. In particular we propose fuzzy relations to represent curve strength. We show how fuzzy relations can be processed in a pyramidal framework. The advantage gained by this method is that the properties of the binary curve pyramid are preserved, and that we gain some additional properties, which can be used in the pyramid construction phase.

A general design strategy based on experiences of a successful application project concerning the reading of analog devices in order to automate the reading process is presented. The problem space is defined and a description language is introduced which controls the interpretation of specific types of instruments and decouples recognition of primitiva and formation of an aspired result. Furthermore, the interaction between Hough transform or line detection, the user-controlled computation of the measurement and the extension to other measuring instruments is described.

A new algorithm for building irregular pyramids is presented. The algorithm is based on only two basic operations on graphs, contraction and removal of edges. By making use of the concept of dual graphs, the algorithm overcomes the problem of unbounded vertex degree proper to the existing approach to building irregular pyramids. This boundedness extends the scope of parallel, degree preserving graph contraction also to irregular structures. Our method can be applied to all problems in which a 2D discrete space can be represented by a planar graph. Four-connected square grids, region adjacency graphs, Voronoi diagrams and Delaunay triangulations are examples of such plane representations.

An analysis system design based on experience with a successful application in the field of inspection and calibration of an analog display measuring instrument is presented in this paper. First the measuring instrument is divided into its primitiva, defining the a priori known parameter of the primitiva: shape, relative position and size. According to the shape of the primitiva pattern recognition algorithms are used to detect the primitiva in intensity images. These independent detection algorithms are then grouped into a detecting order with respect to efficiency. Following a discussion of the general design of the detecting algorithm, specific constraints of the application and the industrial environment are considered in order to refine the general design to an applicable and efficient device by modifying both hardware and software configuration depending on the given constraints. Finally, results of the implementation of the algorithm and the constructed image acquisition device are discussed.>

Planar curves are described by information about corners integrated over various levels of resolution. The detection of corners takes place on a digital representation. To compensate for ambiguities arising from sampling problems due to the discreteness, results about the local behavior of curvature extrema in continuous scale-space are employed.>

In order to usefully apply the concept of the curve pyramid on grouping problems, the shift variance problem must be overcome by extending the concept to irregular pyramids. These have a structure that adapts to the image data by deriving control information from curve relations. The algorithm that builds the irregular curve pyramid by deriving higher levels of abstraction from a set of relations goes far beyond merely solving the shift variance problem. It can reduce the computational complexity in comparable applications where all possible combinations of parts have to be checked in order to reassemble complex objects.>

A robust method for describing planar curves in multiple resolution using curvature information is presented. The method is developed by taking into account the discrete nature of digital images as well as the discrete aspect of a multiresolution structure (pyramid). The main contribution lies in the robustness of the technique, which is due to the additional information that is extracted from observing the behavior of corners in the whole pyramid. Furthermore, the resulting algorithm is conceptually simple and easily parallelizable. Theoretical results are developed analyzing the curvature of continuous curves in scale-space and showing the behavior of curvature extrema under varying scale. The results are used to eliminate any ambiguities that might arise from sampling problems due to the discreteness of the representation. Experimental results demonstrate the potential of the method.>

The interpretation of neural network behavior is of particular interest in neural network research. Visualization methods provide the necessary means to simultaneously analyze the huge amount of information hidden in the network. The authors propose a framework for visualization methods suited for feed forward neural networks. The basic idea is to use the spatial information available outside the network to arrange the data to be visualized (weights, activations of units) in the spatial domain of the display. Several examples which illustrate the proposed framework are presented.>

Presents a robust method for describing planar curves in multiple resolution using curvature information. The method is developed by taking into account the discrete nature of digital images as well as the discrete aspect of a multiresolution structure (pyramid). The authors deal with the robustness of the technique, which is due to the additional information that is extracted from observing the behavior of corners in the pyramid. Furthermore the resulting algorithm is conceptually simple and easily parallelizable. They develop theoretical results, analyzing the curvature of continuous curves in scale-space, which show the behavior of curvature extrema under varying scale. These results are used to eliminate any ambiguities that might arise from sampling problems due to the discreteness of the representation. Finally, experimental results demonstrate the potential of the method. >

Compared with the richness in detail of images generated by iterated function systems, the memory requirement of them is very low. Displaying these images is very time consuming, and currently there is no method published to derive an iterated function system directly from a given image. This is known as the inverse problem. The authors introduce discrete transformations and direct computation of a discrete attractor with deterministic noniterative algorithms. This results in an essential saving of time. Furthermore they present a solution of the inverse problem in the one dimensional discrete space.>

The neocognitron is a neural model which can recognize a pattern even when it is shifted in position, changed in size, or distorted. However, the complexity of its structure and its algorithm makes it difficult to tune its parameters and to specify the detail of its structure. The characteristics of this model are measured as the relationship between the degree of distortion of the input and the tolerance of the model. Computational experiments show that the pyramid has a suitable structure for implementing a neocognitron, provided that the input has a relatively low spatial frequency.>