We describe a framework which can be used to investigate the geometrical structure of datasets in high-dimensional spaces. Understanding these geometrical properties is essential in machine learning in general. An application which has received much attention recently is the investigation of adversarial examples which can be easily identified by humans but which are misleading neural networks. We will argue that these examples can be understood (and consequently avoided) by an investigation of the dimension and geometry of the classification hypersurface of the underlying neural network as a manifold using the tools introduced in this paper.We argue that a key concept in the analysis is the dimension of a manifold. Many machine learning methods use dimension reduction techniques to understand or classify the input data. We point out different definitions of a dimension of a manifold. We use tools from the theory of topological manifolds to introduce local, or intrinsic and global dimensions. The local dimension describes the local similarity between the dataset and a Euclidean space. The global dimension is the lowest dimension of a Euclidean space into which the dataset can be embedded. For a data space with a Riemannian structure the isometric embedding dimension is the lowest dimensional space into which the dataset can be embedded under the condition that the metric tensor is preserved between the two spaces.We introduce a framework for dimension estimation and topological manifold learning based on the measure ratio method to estimate the dimensions and structure of the data manifold. As an illustration we use images of handwritten digits and points of a Klein-bottle embedded in a five-dimensional space. We compare the results obtained by the measure ratio method with the well-known local-principal component analysis estimation.

Dimension reduction is one of the most important issues in machine learning and computational intelligence. Typical data sets are point clouds in a high dimensional space with a hidden structure to be found in low dimensional submanifolds. Finding this intrinsic manifold structure is very important in the understanding of the data and for reducing computational complexity. In this paper, we propose a novel approach for dimension estimation of topological manifolds based on measures of simplices. We also investigate the effects of resolution changes for dimension estimation in the framework of Morse theory. The result is a method that can be used for data located in simplical complexes of varying dimensions and with no continuous or differentiable structure. The proposed method is applied to images of handwritten digits with known deforming dimensions, data with a nontrivial topology and noisy data. We compare the estimates with results obtain by local PCA.

We introduce the Siegel upper half-space with its symplectic geometry as a framework for low-level image processing. We characterize properties of images with the help of six parameters: two spatial coordinates, the pixel value, and the three parameters of a symmetric positive-definite (SPD) matrix such as the metric tensor. We construct a mapping of these parameters into the Siegel upper half-space. From the general theory, it is known that there is a distance on this space that is preserved by the symplectic transformations. The construction provides a mapping that has relatively simply transformation properties under spatial rotations, and the distance values can be computed with the help of closed-form expressions which allow an efficient implementation. We illustrate the properties of this geometry by considering a special case where we compute for every pixel its symplectic distance to its four spatial neighbors and we show how spatial distances, pixel value changes, and texture properties are described in this unifying symplectic framework.

We use methods from Riemann geometry to investigate transformations between the color spaces of color-normal and color-weak observers. The two main applications are the simulation of the perception of a color weak observer for a color-normal observer, and the compensation of color images in a way that a color-weak observer has approximately the same perception as a color-normal observer. The metrics in the color spaces of interest are characterized with the help of ellipsoids defined by the just-noticeable-differences between the colors which are measured with the help of color-matching experiments. The constructed mappings are the isometries of Riemann spaces that preserve the perceived color differences for both observers. Among the two approaches to build such an isometry, we introduce normal coordinates in Riemann spaces as a tool to construct a global color-weak compensation map. Compared with the previously used methods, this method is free from approximation errors due to local linearizations, and it avoids the problem of shifting locations of the origin of the local coordinate system. We analyze the variations of the Riemann metrics for different observers obtained from new color-matching experiments and describe three variations of the basic method. The performance of the methods is evaluated with the help of semantic differential tests.

We introduce the generalized extreme value distributions as descriptors of edge-related visual appearance properties. Theoretically these distributions are characterized by their limiting and stability properties which gives them a role similar to that of the normal distributions. Empirically we will show that these distributions provide a good fit for images from a large database of microscopy images with two visually very different types of images. The generalized extreme value distributions are transformed exponential distributions for which analytical expressions for the Fisher matrix are available. We will show how the determinant of the Fisher matrix and the gradient of the determinant of the Fisher matrix can be used as sharpness functions and a combination of the determinant and the gradient information can be used to improve the quality of the focus estimation.

Level set methods are a popular way to solve the image segmentation problem. The solution contour is found by solving an optimization problem where a cost functional is minimized. Gradient descent methods are often used to solve this optimization problem since they are very easy to implement and applicable to general nonconvex functionals. They are, however, sensitive to local minima and often display slow convergence. Traditionally, cost functionals have been modified to avoid these problems. In this paper, we instead propose using two modified gradient descent methods, one using a momentum term and one based on resilient propagation. These methods are commonly used in the machine learning community. In a series of 2-D/3-D-experiments using real and synthetic data with ground truth, the modifications are shown to reduce the sensitivity for local optima and to increase the convergence rate. The parameter sensitivity is also investigated. The proposed methods are very simple modifications of the basic method, and are directly compatible with any type of level set implementation. Downloadable reference code with examples is available online.

We introduce normal coordinates in Riemann spaces as a tool to construct color-weak compensation methods. We use them to compute color stimuli for a color weak observers that result in the same color perception as the original image presented to a color normal observer in the sense that perceived color-differences are identical for both. The compensation is obtained through a color-difference-preserving map, i.e. an isometry between the 3D color spaces of a color-normal and any given color-weak observer. This approach uses discrimination threshold data and is free from approximation errors due to local linearization. The performance is evaluated with the help of semantic differential (SD) tests.

Computed Tomography Angiography (CTA) is commonly used in clinical routine for diagnosing vascular diseases. The procedure involves the injection of a contrast agent into the blood stream to increase the contrast between the blood vessels and the surrounding tissue in the image data. CTA is often visualized with Direct Volume Rendering (DVR) where the enhanced image contrast is important for the construction of Transfer Functions (TFs). For increased efficiency, clinical routine heavily relies on preset TFs to simplify the creation of such visualizations for a physician. In practice, however, TF presets often do not yield optimal images due to variations in mixture concentration of contrast agent in the blood stream. In this paper we propose an automatic, optimization-based method that shifts TF presets to account for general deviations and local variations of the intensity of contrast enhanced blood vessels. Some of the advantages of this method are the following. It computationally automates large parts of a process that is currently performed manually. It performs the TF shift locally and can thus optimize larger portions of the image than is possible with manual interaction. The method is based on a well known vesselness descriptor in the definition of the optimization criterion. The performance of the method is illustrated by clinically relevant CT angiography datasets displaying both improved structural overviews of vessel trees and improved adaption to local variations of contrast concentration.

We investigate several topics related to manifold-techniques for signal processing. On the most general level we consider manifolds with a Riemannian Geometry. These manifolds are characterized by their inner products on the tangent spaces. We describe the connection between the symmetric positive-definite matrices defining these inner products and the Cartan and the Iwasawa decomposition of the general linear matrix groups. This decomposition gives rise to the decomposition of the inner product matrices into diagonal matrices and orthonormal and into diagonal and upper triangular matrices. Next we describe the estimation of the inner product matrices from measured data as an optimization process on the homogeneous space of upper triangular matrices. We show that the decomposition leads to simple forms of partial derivatives that are commonly used in optimization algorithms. Using the group theoretical parametrization ensures also that all intermediate estimates of the inner product matrix are symmetric and positive definite. Finally we apply the method to a problem from psychophysics where the color perception properties of an observer are characterized with the help of color matching experiments. We will show that measurements from color weak observers require the enforcement of the positive-definiteness of the matrix with the help of the manifold optimization technique.

The octahedral group is one of the finite subgroups of the rotation group in 3-D Euclidean space and a symmetry group of the cubic grid. Compression and filtering of 3-D volumes are given as application examples of its representation theory. We give an overview over the finite subgroups of the 3-D rotation group and their classification. We summarize properties of the octahedral group and basic results from its representation theory. Wide-sense stationary processes are processes with group theoretical symmetries whose principal components are closely related to the representation theory of their symmetry group. Linear filter systems are defined as projection operators and symmetry-based filter systems are generalizations of the Fourier transforms. The algorithms are implemented in Maple/Matlab functions and worksheets. In the experimental part, we use two publicly available MRI volumes. It is shown that the assumption of wide-sense stationarity is realistic and the true principal components of the correlation matrix are very well approximated by the group theoretically predicted structure. We illustrate the nature of the different types of filter systems, their invariance and transformation properties. Finally, we show how thresholding in the transform domain can be used in 3-D signal processing.

The non-negativity of color signals implies that they span a conical space with a hyperbolic geometry. We use perspective projections to separate intensity from chromaticity, and for 3-D color descriptors the chromatic properties are represented by points on the unit disk. Descriptors derived from the same object point but under different imaging conditions can be joined by a hyperbolic geodesic. The properties of this model are investigated using multichannel images of natural scenes and black body illuminants of different temperatures. We show, over a series of static scenes with different illuminants, how illumination changes influence the hyperbolic distances and the geodesics. Descriptors derived from conventional RGB images are also addressed.

In this paper we describe how to use the direct product of the dihedral group D(4) and the symmetric group 5(3) to automatically derive low-level image processing filter systems for RGB images. For important classes of stochastic processes it can be shown that the resulting operators lead to a block-diagonalization of the correlation matrix. We show that the group theoretical derivation of the operators leads to a very fast implementation consisting mainly of additions and subtractions. They can therefore be implemented in fast graphics computation hardware such as a GPU. We then illustrate the block-diagonalization property in an experiment where we used 20,000 subimage patches collected from 10,000 random images in a large image database. The very short execution times make these operators suitable for applications where many images have to be processed. Typical examples are video processing and content-based image database search. We describe one example where we use the operators to compute content based descriptors of images. These descriptors are currently used in one search mode in an image database browser operating on a database with more than 750,000 images. The group theoretical tools used to derive these filters are very general and can directly be applied for other types of image data. Examples are the following generalizations of the methodology: filter systems for multiband images with more than the ordinary three RGB-channels or images with other grid geometries such as hexagonal sampling.

We introduce a two-stage analysis of color spectra. In the first processing stage, correlation with the first eigenvector of a spectral database is used to measure the intensity of a color spectrum. In the second step, a perspective projection is used to map the color spectrum to the hyperspace of spectra with first eigenvector coefficient equal to unity. The location in this hyperspace describes the chromaticity of the color spectrum. In this new projection space, a second basis of eigenvectors is computed and the projected spectrum is described by the expansion in this chromaticity basis. This description is possible since the space of color spectra is conical. We compare this two-stage process with traditional principal component analysis and find that the results of the new structure are closer to the structure of traditional chromaticity descriptors than traditional principal component analysis.

In many color based image retrieval systems the color properties of an image are described by the histogram of the colors in the image. Color histograms are insensitive to small object distortions and easy to compute. Histogram based searches are however often inefficient for the large histogram sizes needed to represent color distributions. Therefore we introduce several new, PCA-based methods that provide efficient representations of color histograms and differences between two color histograms. We also investigate distance measures in the space of histograms which are defined by quadratic forms and which take into account the geometric structure of the underlying color space. We show that the combination of the quadratic forms based distance measure and the compression of the histogram information by difference based PCA-approximations provide new powerful and efficient retrieval algorithms for color based image retrieval.

The description of the relation between the one-parameter subgroups of a group and the differential operators in the Lie-algebra of the group is one of the major topics in Lie-theory. We use this framework to derive a partial differential equation which describes the relation between the time-change of the spectral characteristics of the illumination source and the change of the color pixels in an image. We introduce and justify the usage of conical coordinate systems in color space. We also derive the differential equation describing the illumination change and illustrate the algorithm with some simulation examples.

In many multi-media applications it is desirable to separate the influence of the illumination sources and imaging equipment from the properties of the depicted scene. The ability of the human visual system to solve this task in many situations is known as color constancy. Technical applications of these methods include automatic color correction and illumination independent search in image databases. Many conventional computational color constancy methods assume that the effect of an illumination change can be described by a matrix multiplication with a diagonal matrix. In this paper we introduce a color normalization algorithm which computes the unique color transformation matrix which normalizes a given set of moments computed from the color distribution of an image. This normalization procedure is a generalization of the channel independent color constancy methods since general matrix transformations are considered. We compare the performance of this new normalization method with conventional color constancy methods. The experiments show that diagonal transformation matrices provide a better illumination compensation. This shows that the color moments also contain significant information about the color distributions of the objects in the image which is independent of the illumination characteristics. In another set of experiments we use the unique transformation matrix as a descriptor of the set of moments which describe the global color distribution in the image. Combining the matrices computed from two such images describes the color differences between them. We then use this as a tool for color dependent search in image databases. This matrix based color search is computationally less demanding than histogram based color search tools.

The groups which have received most attention in signal processing research are the affine groups and the Heisenberg-Weyl group related to wavelets and time-frequency methods. In low-level image processing the rotation-groups SO(2) and SO(3) were studied in detail. We argue that the Lorentz group SO(1,2) provides a natural framework in the study of dynamic processes like the analysis of image sequences. We summarize the connection between the group SO(1,2) and the groups SU(1,1) and SL(2,R) and give an overview over their representations. We show that their representation theory is in parts similar to the corresponding theory for the three-dimensional rotation group. The main differences between the compact groups (like SO(2) and SO(3)) is however that the Fourier transforms for these groups involves infinite-dimensional representations and that the finite-dimensional representations are no longer unitary. In the signal processing context this means that the filter vectors computed by finite-dimensional steerable filter systems no longer transform as unitary vector transformations under the symmetry operations in SO(1,2).

The information in a color image is always a function of the illuminating source, the geometry, the reflectance properties of the object and the characteristic of the camera. Separating the influence of the spectral distribution of the illumination and the reflectance properties of the object is known as the color constancy problem. Successful separation is important for vision and pattern recognition tasks, quality control in the graphic arts and image database applications. We describe an approach to the color constancy problem which is based on statistical assumptions about the distribution of colors. It uses the eigenvector system of the logarithmic spectra in a large database of color samples and employs methods from robust statistics to recover the illumination spectrum. We illustrate the performance of the algorithm with a simulation in which the effect of the illumination by the standard A-source is eliminated.

We propose a new algorithm, which needs almost no multiplication. We propose using modular arithmetic of the finite Galois field GF(Q) to map geometrical moments calculation to a fast Fourier-Mellin-Galois transform, which reduces the computational complexity from /spl Oscr/(N/sub 4/) to /spl Oscr/(N/sub 2/ log/sub 2/ N). We illustrate the performance of the method by some classification and matching experiments.

The paper describes iterative algorithms to normalize coefficient vectors computed by expanding functions on the unit sphere into a series of surface harmonics. Typical applications of the normalization procedure are the matching of different three-dimensional images, orientation estimations in low-level image processing or robotics. The method uses general methods from the theory of Lie-groups and Lie-algebras to linearize the highly-nonlinear original problem and can therefore also be adapted to applications involving groups different from the group of three-dimensional rotations. The performance of the algorithm is illustrated with a few experiments involving random coefficient vectors.

We present a new co-occurrence matrix based approach for multispectral texture analysis. The spectral and spatial domains of the multispectral textures are processed separately. The color space used in this study is represented by subspaces and it is classified by the averaged learning subspace method (ALSM). In the spatial domain we use a generalized co-occurrence matrix for vector valued pixels. The texture feature vectors are classified by the k-nearest neighbor (KNN) classifier and the multilayer perceptron (MLP) network. Experimental results of the multispectral texture segmentation are presented.

Uses the representation theory of finite groups to simplify the Karhunen-Loeve transform (KLT) of systems with group theoretically defined symmetries. In the paper the authors focus on applications of the dihedral groups D(n) which consist of all isometries that map the n-sided regular polygon into itself. The group D(4) is of special importance for all problems on square grids. Connected to each group is a type of Fourier transform. This transform block-diagonalizes all operators that commute with the group operations. As a result all correlation matrices of processes with group theoretically defined symmetries are block-diagonalized. This simplifies the computation of the KLT considerably. For real world data the symmetry assumptions leading to the simplification of the KLT are never exactly fulfilled and the KLT based on the block-diagonal correlation matrix is only an approximation to the correct KLT. In the second part of the paper the authors compare several approximations to the KLT for a large data base consisting of blocks collected from a standard TV-channel. Finally they discuss some of the consequences for image coding applications.

The correspondence between two coplanar sets of points (or lines) is established making use of a novel invariant representation of five-tuples of features. The projective/permutation (p/sup 2/) invariants are insensitive to the order of the features in the computation and thus provide a significant speedup in matching. Performance degradation due to the noise sensitivity of the invariants is avoided by using context independent constraints (noncollinearity of points, preservation of the convex hull); and by accumulating the feature correspondence hypotheses in a contingency table. Full projective correspondence can be recovered reliably for positional uncertainty of several pixels or in the presence of outliers.

The authors discuss two classes of unsupervised feature extraction methods. They show that a system based on second order moments can learn the Karhunen-Loeve expansion in parallel. Then they show that systems based on second order moments only have important drawbacks. The second class of systems described avoids this problem by using fourth order moments. Since these systems are much harder to analyze the authors demonstrate some of their advantages with the help of some experiments.>

We use the invariance principle and the principles of maximum information extraction and maximum signal concentration to design a parallel, linear filter system that learns the Karhunen-Loeve expansion of a process from examples. In this paper we prove that the learning rule based on these principles forces the system into stable states that are pure eigenfunctions of the input process.

A study is made of properties of so-called basic units. The authors investigate an eigenvalue problem that turns up in the study of the stable states of such units. Basic units using Hebb-type learning rules converge to stable states which are eigenfunctions of an integral equation whose kernel is given by the covariance function of the input process. The authors investigate one basic unit and assume that the set of input patterns of this basic unit is regular in the sense that all patterns can be derived from a single prototype pattern by a group-theoretically defined transformation. They show that the stable states of the unit are uniquely determined by the symmetry of the input set. It is demonstrated that the system stabilizes in a state in which the different basic units are characterized by the group-theoretically derived filter functions. The authors train the system with an input set consisting of rotated edge and line patterns and show that the stable states of the system are characterized by pure line and pure edge detectors. How the system can be used in texture segmentation is described

The author investigates the following fundamental pattern recognition problem. He assumes that he has a set of signals or patterns, denoted by S, and an unknown pattern p. The problem is to decide if P in S or p not in S. The author assumes further that S is symmetrical or regular in a group-theoretical sense. Harmonic analysis and the theory of group representations are applied to construct filter processes that se the regularity of S in an optimal way. Results are presented for 2-D and 3-D rotation-invariant filters.>

Twelve methods are evaluated to analyze an ideal sphere and a real human skull. They are different combinations of principles for detection of the surface to be displayed (gray-value threshold, gradient threshold, and zero-crossing of the second derivative), localizing this surface in space (including both grid-point accuracy and subvoxel accuracy), and finally estimating the direction of the surface normal (from the gradient in the 2-D depth image and from the gradient in the 3-D volume). The best quality is obtained by zero-crossing detection, subvoxel localization, and 3-D gradient orientation.>