Generalizing the Hough transform to detect arbitrary shapes

The Hough transform is a method for detecting curves by exploiting the duality between points on a curve and parameters of that curve. The initial work showed how to detect both analytic curves^(1,2) and non-analytic curves,⁽³⁾ but these methods were restricted to binary edge images. This work was generalized to the detection of some analytic curves in grey level images, specifically lines,⁽⁴⁾ circles⁽⁵⁾ and parabolas.⁽⁶⁾ The line detection case is the best known of these and has been ingeniously exploited in several applications.^(7,8,9)We show how the boundaries of an arbitrary non-analytic shape can be used to construct a mapping between image space and Hough transform space. Such a mapping can be exploited to detect instances of that particular shape in an image. Furthermore, variations in the shape such as rotations, scale changes or figure ground reversals correspond to straightforward transformations of this mapping. However, the most remarkable property is that such mappings can be composed to build mappings for complex shapes from the mappings of simpler component shapes. This makes the generalized Hough transform a kind of universal transform which can be used to find arbitrarily complex shapes.     

Pattern analysis of dermoscopic images based on Markov random fields

In this paper a method for detecting different patterns in dermoscopic images is presented. In order to diagnose a possible skin cancer, physicians assess the lesion based on different rules. While the most famous one is the ABCD rule (asymmetry, border, colour, diameter), the new tendency in dermatology is to classify the lesion performing a pattern analysis. Due to the colour textured appearance of these patterns, this paper presents a novel method based on Markov random field (MRF) extended for colour images that classifies images representing different dermatologic patterns. First, each image plane in L^*a^*b^* colour space is modelled as a MRF following a finite symmetric conditional model (FSCM). Coupling of colour components is taken into account by supposing that features of the MRF in the three colour planes follow a multivariate Normal distribution. Performance is analysed in different colour spaces. The best classification rate is 86% on average.     

Second Order Structure of Scale-Space Measurements

The second-order structure of random images f :? ^d →? ^N is studied under the assumption of stationarity of increments, isotropy and scale invariance. Scale invariance is defined via linear scale space theory. The results are formulated in terms of the covariance structure of the jet consisting of the scale space derivatives at a single point. Operators describing the effect in jet space of blurring and scaling are investigated. The theory developed is applicable in the analysis of naturally occurring images of which examples are provided.     

Human Face Recognition and the Face Image Set′s Topology

If we consider an n × n image as an n²-dimensional vector, then images of faces can be considered as points in this n²-dimensional image space. Our previous studies of physical transformations of the face, including translation, small rotations, and illumination changes, showed that the set of face images consists of relatively simple connected subregions in image space. Consequently linear matching techniques can be used to obtain reliable face recognition. However, for more general transformations, such as large rotations or scale changes, the face subregions become highly non-convex. We have therefore developed a scale-space matching technique that allows us to take advantage of knowledge about important geometrical transformations and about the topology of the face subregion in image space. While recognition of faces is the focus of this paper, the algorithm is sufficiently general to be applicable to a large variety of object recognition tasks     

Harmonic Embeddings for Linear Shape Analysis

We present a novel representation of shape for closed contours in ℝ² or for compact surfaces in ℝ³ explicitly designed to possess a linear structure. This greatly simplifies linear operations such as averaging, principal component analysis or differentiation in the space of shapes when compared to more common embedding choices such as the signed distance representation linked to the nonlinear Eikonal equation. The specific choice of implicit linear representation explored in this article is the class of harmonic functions over an annulus containing the contour. The idea is to represent the contour as closely as possible by the zero level set of a harmonic function, thereby linking our representation to the linear Laplace equation. We note that this is a local represenation within the space of closed curves as such harmonic functions can generally be defined only over a neighborhood of the embedded curve. We also make no claim that this is the only choice or even the optimal choice within the class of possible linear implicit representations. Instead, our intent is to show how linear analysis of shape is greatly simplified (and sensible) when such a linear representation is employed in hopes to inspire new ideas and additional research into this type of linear implicit representations for curves. We conclude by showing an application for which our particular choice of harmonic representation is ideally suited.     

Reconstruction from Projections Using Grassmann Tensors

In this paper a general procedure is given for reconstruction of a set of feature points in an arbitrary dimensional projective space from their projections into lower dimensional spaces. This extends the methods applied in the well-studied problem of reconstruction of scene points in ℘³ given their projections in a set of images. In this case, the bifocal, trifocal and quadrifocal tensors are used to carry out this computation. It is shown that similar methods will apply in a much more general context, and hence may be applied to projections from ℘ ⁿ to ℘ ^m , which have been used in the analysis of dynamic scenes, and in radial distortion correction. For sufficiently many generic projections, reconstruction of the scene is shown to be unique up to projectivity, except in the case of projections onto one-dimensional image spaces (lines), in which case there are two solutions. Projections from ℘ ⁿ to ℘² have been considered by Wolf and Shashua (in International Journal of Computer Vision 48(1): 53–67, 2002), where they were applied to several different problems in dynamic scene analysis. They analyzed these projections using tensors, but no general way of defining such tensors, and computing the projections was given. This paper settles the general problem, showing that tensor definition and retrieval of the projections is always possible.     

A lossless secret image sharing scheme using a larger finite field

Recent research has made an effort to take 8b-bit value as a polynomial coefficient and use a random number as the maximum coefficient term in a Shamir’s polynomial, where b > 0. These can help improve computationl efficiency by reducing the sum of calculating polynomials, and avoid the case of the coefficient of x^k??1 being zero. However, such research still has the issues of requiring much extra storage space, lossy secret image, shadow images with large size, and storing permutation key. To solve the above issues, in this paper, we propose a novel scheme which takes 8b-bit value as a polynomial coefficient, designs a bit-level method and runs under Galois Field GF(2^8b). Experimental results show that this scheme improves existing similar schemes on several aspects, such as less extra storage space and higher computational performance.

     

Image Manifolds which are Isometric to Euclidean Space

Recently, the Isomap procedure [10] was proposed as a new way to recover a low-dimensional parametrization of data lying on a low-dimensional submanifold in high-dimensional space. The method assumes that the submanifold, viewed as a Riemannian submanifold of the ambient high-dimensional space, is isometric to a convex subset of Euclidean space. This naturally raises the question: what datasets can reasonably be modeled by this condition? In this paper, we consider a special kind of image data: families of images generated by articulation of one or several objects in a scene—for example, images of a black disk on a white background with center placed at a range of locations. The collection of all images in such an articulation family, as the parameters of the articulation vary, makes up an articulation manifold, a submanifold of L ². We study the properties of such articulation manifolds, in particular, their lack of differentiability when the images have edges. Under these conditions, we show that there exists a natural renormalization of geodesic distance which yields a well-defined metric. We exhibit a list of articulation models where the corresponding manifold equipped with this new metric is indeed isometric to a convex subset of Euclidean space. Examples include translations of a symmetric object, rotations of a closed set, articulations of a horizon, and expressions of a cartoon face. The theoretical predictions from our study are borne out by empirical experiments with published Isomap code. We also note that in the case where several components of the image articulate independently, isometry may fail; for example, with several disks in an image avoiding contact, the underlying Riemannian manifold is locally isometric to an open, connected, but not convex subset of Euclidean space. Such a situation matches the assumptions of our recently-proposed Hessian Eigenmaps procedure, but not the original Isomap procedure.     

On the Choice of Band-Pass Quadrature Filters

Band-pass quadrature filters are extensively used in computer vision to estimate information from images such as: phase, energy, frequency and orientation,¹ possibly at different scales and utilise this in further processing-tasks. The estimation is intrinsically noisy and depends critically on the choice of the quadrature filters. In this paper, we first study the mathematical properties of the quadrature filter pairs most commonly seen in the literature and then consider some new pairs derived from the classical feature detection literature. In the case of feature detection, we present the first attempt to design a quadrature pair based on filters derived for optimal edge/line detection. A comparison of the filters is presented in terms of feature detection performance, wherever possible, in the sense of Canny and in terms of phase stability. We conclude with remarks on how our analysis can aid in the choice of a filter pair for a given image processing task.     

Quantum Mechanical Search and Harmonic Perturbation

Perturbation theory in quantum mechanics studies how quantum systems interact with their environmental perturbations. Harmonic perturbation is a rare special case of time-dependent perturbations in which exact analysis exists. Some important technology advances, such as masers, lasers, nuclear magnetic resonance, etc., originated from it. Here we add quantum computation to this list with a theoretical demonstration. Based on harmonic perturbation, a quantum mechanical algorithm is devised to search the ground state of a given Hamiltonian. The intrinsic complexity of the algorithm is continuous and parametric in both time T and energy E. More precisely, the probability of locating a search target of a Hamiltonian in N-dimensional vector space is shown to be 1/(1 + c N E⁻²T⁻²) for some constant c. This result is optimal. As harmonic perturbation provides a different computation mechanism, the algorithm may suggest new directions in realizing quantum computers.      

对数极坐标系下尺度不变特征点的检测与描述

目的 当前国际流行的SIFT算法及其改进算法在检测与描述特征点时基于高斯差分函数,存在损失图像高频信息的缺陷,从而导致图像匹配时其性能随着图像变形的增加而出现急剧下降。针对SIFT算法及其改进算法的这一缺陷,本研究提出了一种新的无图像信息损失的、在对数极坐标系下的尺度不变特征点检测与描述算法。方法 本研究提出的尺度不变特征点检测与描述算法首先将直角坐标系下以采样点为中心的圆形图块转换为对数极坐标系下的矩形图块,并以此矩形图块为基础对采样点进行特征点检测与描述符提取;该算法使用固定宽度的窗口在采样点的对数极坐标径向梯度图像的log_t^r轴上进行移动以判断该点是否为特征点并计算该点的特征尺度,并在具有局部极大窗口响应的特征尺度位置处提取特征点的描述符。该算法的描述符基于对数极坐标系下的矩形图块的灰度梯度的幅值与角度,是一个192维向量,并具有对于尺度、旋转、光照等变化的不变性。结果 本研究采用INRIA数据组和Mikolajczyk提出的匹配性能指标对SIFT算法、SURF算法和提出的尺度不变特征点检测与描述算法进行比较。与SIFT算法和SURF算法相比,提出的尺度不变特征点检测与描述算法在对应点数、重复率、正确匹配点数和匹配率等方面均具有一定优势。结论 提出了一种基于对数极坐标系的图像匹配算法,即将直角坐标系下以采样点为中心的圆形图块转换为对数极坐标系下的矩形图块,这样在特征点的检测过程中,可以有效规避SIFT算法因为采用DoG函数而造成的高频信息损失;在描述符提取过程中,对数极坐标系可以有效地减少图像的变化量,从而提高了匹配性能。     

Environment contribution to the atmospheric correction for Landsat-MSS images

The signal returning from the Earth's surface to the satellite is modified by the atmospheric effect, which has two components. The first one is solar radiation which, due to backscattering, is deviated in the direction of the sensor without reaching the Earth's surface. The second component is produced by the energy reflected in areas close to the pixel observed which, owing to collisions with atmospheric constituents, is deviated from its path in the sensor direction. This is called the adjacency effect and this paper presents a numerical method to estimate this effect under the assumption of a heterogeneous flat Lambertian surface. From this estimation it is possible to apply the atmospheric correction for the calculation of reflectance images based on data obtained by the optical channels of high resolution satellite systems such as Landsat-MSS, Landsat-TM and SPOT/H RV. In particular, in this paper the method is applied to Landsat-5 MSS images over urban regions. However, its application to any of the sensors mentioned is easily implemented considering the changes in spectral response and pixel size. Differences obtained in the results for reflectance at Earth's surface in winter and summer images were in the order of 10^?3 for bands 1 and 2, 10^?2 for band 3, and 10^?1 for band 4.     

Multiphase Soft Segmentation with Total Variation and <Emphasis Type="Italic">H</Emphasis><Superscript>1</Superscript> Regularization

In this paper, we propose a variational soft segmentation framework inspired by the level set formulation of multiphase Chan-Vese model. We use soft membership functions valued in [0,1] to replace the Heaviside functions of level sets (or characteristic functions) such that we get a representation of regions by soft membership functions which automatically satisfies the sum to one constraint. We give general formulas for arbitrary N-phase segmentation, in contrast to Chan-Vese’s level set method only 2 ^m -phase are studied. To ensure smoothness on membership functions, both total variation (TV) regularization and H ¹ regularization used as two choices for the definition of regularization term. TV regularization has geometric meaning which requires that the segmentation curve length as short as possible, while H ¹ regularization has no explicit geometric meaning but is easier to implement with less parameters and has higher tolerance to noise. Fast numerical schemes are designed for both of the regularization methods. By changing the distance function, the proposed segmentation framework can be easily extended to the segmentation of other types of images. Numerical results on cartoon images, piecewise smooth images and texture images demonstrate that our methods are effective in multiphase image segmentation.     

Robust Image Denoising Using a Virtual Flash Image for Monte Carlo Ray Tracing

We propose an efficient and robust image‐space denoising method for noisy images generated by Monte Carlo ray tracing methods. Our method is based on two new concepts: virtual flash images and homogeneous pixels. Inspired by recent developments in flash photography, virtual flash images emulate photographs taken with a flash, to capture various features of rendered images without taking additional samples. Using a virtual flash image as an edge‐stopping function, our method can preserve image features that were not captured well only by existing edge‐stopping functions such as normals and depth values. While denoising each pixel, we consider only homogeneous pixels—pixels that are statistically equivalent to each other. This makes it possible to define a stochastic error bound of our method, and this bound goes to zero as the number of ray samples goes to infinity, irrespective of denoising parameters. To highlight the benefits of our method, we apply our method to two Monte Carlo ray tracing methods, photon mapping and path tracing, with various input scenes. We demonstrate that using virtual flash images and homogeneous pixels with a standard denoising method outperforms state‐of‐the‐art image‐space denoising methods.     

Massively multithreaded maxflow for image segmentation on the Cray XMT‐2

Image segmentation is a very important step in the computerized analysis of digital images. The maxflow mincut approach has been successfully used to obtain minimum energy segmentations of images in many fields. Classical algorithms for maxflow in networks do not directly lend themselves to efficient parallel implementations on contemporary parallel processors. We present the results of an implementation of Goldberg–Tarjan preflow‐push algorithm on the Cray XMT‐2 massively multithreaded supercomputer. This machine has hardware support for 128 threads in each physical processor, a uniformly accessible shared memory of up to 4 TB and hardware synchronization for each 64 bit word. It is thus well‐suited to the parallelization of graph theoretic algorithms, such as preflow‐push. We describe the implementation of the preflow‐push code on the XMT‐2 and present the results of timing experiments on a series of synthetically generated as well as real images. Our results indicate very good performance on large images and pave the way for practical applications of this machine architecture for image analysis in a production setting. The largest images we have run are 32000² pixels in size, which are well beyond the largest previously reported in the literature.Copyright © 2013 John Wiley & Sons, Ltd.     

marginFace: A novel face recognition method by average neighborhood margin maximization

We propose a novel appearance-based face recognition method called the marginFace approach. By using average neighborhood margin maximization (ANMM), the face images are mapped into a face subspace for analysis. Different from principal component analysis (PCA) and linear discriminant analysis (LDA) which effectively see only the global Euclidean structure of face space, ANMM aims at discriminating face images of different people based on local information. More concretely, for each face image, it pulls the neighboring images of the same person towards it as near as possible, while simultaneously pushing the neighboring images of different people away from it as far as possible. Moreover, we propose an automatic approach for determining the optimal dimensionality of the embedded subspace. The kernelized (nonlinear) and tensorized (multilinear) form of ANMM are also derived in this paper. Finally the experimental results of applying marginFace to face recognition are presented to show the effectiveness of our method.     

How efficiently can room at the bottom be traded away for speed at the top?

Given exponential 2 ⁿ space, we know that an Adleman-Lipton computation can decide many hard problems – such as boolean formula and boolean circuit evaluation – in a number of steps that is linear in the problem size n. We wish to better understand the process of designing and comparing bio-molecular algorithms that trade away weakly exponential space to achieve as low a running time as possible, and to analyze the efficiency of their space and time utilization relative to those of their best extant classical/bio-molecular counterparts. We propose a randomized framework which augments that of the sticker model of Roweis et al. to provide an abstract setting for analyzing the space-time efficiency of both deterministic and randomized bio-molecular algorithms. We explore its power by developing and analyzing such algorithms for theCovering Code Creation (CCC) and k-SAT problems. In the process, we uncover new classical algorithms for CCC andk-SAT that, while exploiting the same space-time trade-off as the best previously known classical algorithms, are exponentially more efficient than them in terms of space-time product utilization. This work indicates that the proposed abstract bio-molecular setting for randomized algorithm design provides a logical tool of independent interest. This revised version was published online in June 2006 with corrections to the Cover Date.     

Shape space estimation by higher-rank of SOM

The aim of this study is to develop an estimation method for a shape space. In this work, “shape space” means a nonlinear subspace formed by a class of visual shapes, in which the continuous change in shapes is naturally represented. By using the shape space, various operations dealing with shapes, such as identification, classification, recognition, and interpolation can be carried out in the shape space. This paper introduces an algorithm based on a generative model of shapes. A higher-rank of the self-organizing map (SOM²) is used to implement the shape space estimation method. We use this method to estimate the shape space of artificial contours. In addition, we present results from a simulation of omnidirectional camera images taken from mobile robots. Our technique accurately predicts changes in image properties as the robot’s attitude changes. Finally, we consider the addition of local features to our method. We show that the inclusion of local features solves the correspondence problem. These results suggest the potential of our technique in the future.