Vector transport for shape-from-shading

In this paper we describe a new shape-from-shading method. We show how the parallel transport of surface normals can be used to impose curvature consistency and also to iteratively update surface normal directions so as to improve the brightness error. We commence by showing how to make local estimates of the Hessian matrix from surface normal information. With the local Hessian matrix to hand, we develop an “EM-like” algorithm for updating the surface normal directions. At each image location, parallel transport is applied to the neighbouring surface normals to generate a sample of local surface orientation predictions. From this sample, a local weighted estimate of the image brightness is made. The transported surface normal which gives the brightness prediction which is closest to this value is selected as the revised estimate of surface orientation. The revised surface normals obtained in this way may in turn be used to re-estimate the Hessian matrix, and the process iterated until stability is reached. We experiment with the method on a variety of real world and synthetic data. Here we explore the properties of the fields of surface normals and the height data delivered by the method.     

Derivation of surface topography and terrain parameters from single satellite image using shape-from-shading technique

This paper evaluates and compares two area-based shape-from-shading algorithms for deriving detailed surface topography and terrain parameters. A Fourier transform-based linear algorithm and an iterative minimization algorithm with integrability constraint are devised and implemented using C++ programming language, and applied to a SPOT panchromatic image. The relative height measurements from the shape-from-shading technique are calibrated into an absolute elevation model using a parametric least-squares adjustment procedure based on a number of ground control points. Surface slope, orientation, and structural lines are also calculated based on the digital elevation model derived from the shape-from-shading technique. The comparative advantages of the two algorithms are discussed, and the combination of two algorithms is also explored. The fundamental requirement for the shape-from-shading algorithms is that the terrain surface under investigation has a relatively homogenous land cover. Source codes in C++ and test data sets are available.     

Facial gender classification using shape-from-shading

The aim in this paper is to show how to use the 2.5D facial surface normals (needle-maps) recovered using shape-from-shading (SFS) to perform gender classification. We use principal geodesic analysis (PGA) to model the distribution of facial surface normals which reside on a Remannian manifold. We incorporate PGA into shape-from-shading, and develop a principal geodesic shape-from-shading (PGSFS) method. This method guarantees that the recovered needle-maps exhibit realistic facial shape by satisfying a statistical model. Moreover, because the recovered facial needle-maps satisfy the data-closeness constraint as a hard constraint, they not only encode facial shape but also implicitly encode image intensity. Experiments explore the gender classification performance using the recovered facial needle-maps on two databases (Notre Dame and FERET), and compare the results with those obtained using intensity images. The results demonstrate the feasibility of gender classification using the recovered facial shape information.     

Surface orientation from a projected grid

Two simple methods are given for obtaining the surface shape using a projected grid. After the camera is calibrated to the 3-D workspace, the only input date needed for the computation of surface normals are grid intersect points in a single 2-D image. The first method performs nonlinear computations based on the distortion of the lengths of the grid edges and does not require a full calibration matrix. The second method requires that a full parallel projection model of the imaging is available, which enables it to compute 3-D normals using simple linear computations. The linear method performed better overall in the experiments, but both methods produced normals within 4-8° of known 3-D directions. These methods appear to be superior to methods based on shape-from-shading because the results are comparable, yet the equipment setup is simpler and the processing is not very sensitive to object reflectance     

Hearing the clusters of a graph: A distributed algorithm

We propose a novel distributed algorithm to cluster graphs. The algorithm recovers the solution obtained from spectral clustering without the need for expensive eigenvalue/eigenvector computations. We prove that, by propagating waves through the graph, a local fast Fourier transform yields the local component of every eigenvector of the Laplacian matrix, thus providing clustering information. For large graphs, the proposed algorithm is orders of magnitude faster than random walk based approaches. We prove the equivalence of the proposed algorithm to spectral clustering and derive convergence rates. We demonstrate the benefit of using this decentralized clustering algorithm for community detection in social graphs, accelerating distributed estimation in sensor networks and efficient computation of distributed multi-agent search strategies.     

Real-time Object Recognition in Sparse Range Images Using Error Surface Embedding

This article formulates a near-lighting shape-from-shading problem with a pinhole camera (perspective projection) and presents a solution to reconstruct the Lambertian surface of bones using a sequence of overlapped endoscopic images, with partial boundaries in each image. First we extend the shape-from-shading problem to deal with perspective projection and near point light sources that are not co-located with the camera center. Secondly we propose a multi-image framework which can align partial shapes obtained from different images in the world coordinates by tracking the endoscope. An iterative closest point (ICP) algorithm is used to improve the matching and recover complete occluding boundaries of the bone. Finally, a complete and consistent shape is obtained by simultaneously re-growing the surface normals and depths in all views. In order to fulfill our shape-from-shading algorithm, we also calibrate both geometry and photometry for an oblique-viewing endoscope that are not well addressed before in the previous literatures. We demonstrate the accuracy of our technique using simulations and experiments with artificial bones.     

Recovering facial shape using a statistical model of surface normal direction

In this paper, we show how a statistical model of facial shape can be embedded within a shape-from-shading algorithm. We describe how facial shape can be captured using a statistical model of variations in surface normal direction. To construct this model, we make use of the azimuthal equidistant projection to map the distribution of surface normals from the polar representation on a unit sphere to Cartesian points on a local tangent plane. The distribution of surface normal directions is captured using the covariance matrix for the projected point positions. The eigenvectors of the covariance matrix define the modes of shape-variation in the fields of transformed surface normals. We show how this model can be trained using surface normal data acquired from range images and how to fit the model to intensity images of faces using constraints on the surface normal direction provided by Lambert's law. We demonstrate that the combination of a global statistical constraint and local irradiance constraint yields an efficient and accurate approach to facial shape recovery and is capable of recovering fine local surface details. We assess the accuracy of the technique on a variety of images with ground truth and real-world images     

基于曲面法向量的曲面恢复

从另一个角度研究三维曲面的恢复,即根据曲面法向量,考虑多块曲面的重构.算法输入的数据是估计的曲面法向量,比如输入的数据是根据从阴影恢复形状或从纹理恢复形状等计算机视觉低层次处理中得到.通过球面坐标变换把曲面法向量分解成两个函数;然后再对这两个函数进行滤波处理,通过对这两个分割的叠加将空间曲面分割成几个子曲面;最后利用Green函数分别恢复各个子曲面.虽然只利用了一般的图像处理技术,却能得到比传统的基于曲面法向量的方法更好的结果,特别是边界部分的恢复.这是因为传统的方法只是考虑恢复一个曲面模型,因此在不同曲面的边界上会产生模糊.最后利用模拟数据和由阴影恢复形状算法获取真实数据来评价提出的算法,并都与传统的方法进行了比较.     

A probabilistic framework for specular shape-from-shading

One of the problems that hinders conventional methods for shape-from-shading is the presence of local specularities which may be misidentified as high curvature surface features. In this paper we address the problem of estimating the proportions of Lambertian and specular reflection components in order to improve the quality of surface normal information recoverable using shape-from-shading. The framework for our study is provided by the iterated conditional modes algorithm. We develop a maximum a posteriori probability (MAP) estimation method for estimating the mixing proportions for Lambertian and specular reflectance, and also, for recovering local surface normals. The MAP estimation scheme has two model ingredients. First, there are separate conditional measurement densities which describe the distributions of surface normal directions for the Lambertian and specular reflectance components. We experimentally compare three different models for the specular component. The second ingredient is a smoothness prior which models the distribution of surface normal directions over local image regions. We demonstrate the utility of method on real-world data. Ground truth data is provided by imagery obtained with crossed polaroid filters. This reveals not only that the method accurately estimates the proportion of specular reflection, but that it also results in good surface normal reconstruction in the proximity of specular highlights.     

一种基于改进快速搜索随机树算法的管路自动布局方法

针对非正交管路自动布局问题,提出一种基于障碍物碰撞信息的快速搜索随机树 改进算法。该算法主要采用基于碰撞信息的节点扩展策略、快速绕障算法以及基于概率思想的 节点扩展策略3 种方法进行改进,能够在较短的时间内搜索出一条沿结构件表面从起点到终点 的路径,在此基础上采用基于关键节点的路径优化策略,对求解得到的布局路径进行优化后形 成最终的管路布局结果。开发了原型系统,通过实例验证了该算法的可行性。     

基于GPU的芯片热分析方法研究

针对大规模IC芯片中局部高温热效应问题,提出基于网格的随机行走方法分析稳态温度分布。该算法只计算热源附近的点,从而大幅减少计算量。首先对金字塔型非规则热分析模型进行了研究,然后提出了一种预先保存概率表的加速策略。将随机行走算法在CUDA上实现了并行,得出了最大限度使用GPU资源并保证最大加速比的最优配置。实验结果表明,提出的并行随机行走算法,使总体计算性能提升了7-10倍。     

Sequential least-squares prediction based on spectral analysis

A spectral representation for time series analysis is formulated on the basis of classical least-squares theory, and is extended for application to the prediction of a random sequence with a sequential updating of model coefficients based on pre-computed eigenvector components and current online data. The solution for updating the time series coefficients is shown to be directly analogous to the form of piecewise solution of the steady-state electrical network problem based on Kron's method of tearing and interconnection. The sensitivity of the spectral prediction algorithm based on the eigenvalue properties of the defining covariance data matrix is also developed.     

双层随机游走半监督聚类

半监督聚类旨在根据用户给出的必连和不连约束,把所有数据点划分到不同的簇中,从而获得更准确、更加符合用户要求的聚类结果.目前的半监督聚类算法大多数通过修改已有的聚类算法或者结合度规学习,使聚类结果与点对约束尽可能地保持一致,却很少考虑点对约束对周围无约束数据的显式影响程度.提出一种由在顶点上的低层随机游走和在组件上的高层随机游走两部分构成的双层随机游走半监督聚类算法,其中,低层随机游走主要负责计算选出的约束顶点对其他顶点的影响范围和影响程度,称为组件;高层随机游走则进一步将各个点对约束以自适应的强度在组件上进行约束传播,把它们在每个顶点上的影响综合在一个簇指示矩阵中.UCI数据集和大型真实数据集上的实验结果表明,双层随机游走半监督聚类算法比其他半监督聚类算法更准确,也比较高效.     

A probabilistic spectral framework for grouping and segmentation

This paper presents an iterative spectral framework for pairwise clustering and perceptual grouping. Our model is expressed in terms of two sets of parameters. Firstly, there are cluster memberships which represent the affinity of objects to clusters. Secondly, there is a matrix of link weights for pairs of tokens. We adopt a model in which these two sets of variables are governed by a Bernoulli model. We show how the likelihood function resulting from this model may be maximised with respect to both the elements of link-weight matrix and the cluster membership variables. We establish the link between the maximisation of the log-likelihood function and the eigenvectors of the link-weight matrix. This leads us to an algorithm in which we iteratively update the link-weight matrix by repeatedly refining its modal structure. Each iteration of the algorithm is a three-step process. First, we compute a link-weight matrix for each cluster by taking the outer-product of the vectors of current cluster-membership indicators for that cluster. Second, we extract the leading eigenvector from each modal link-weight matrix. Third, we compute a revised link weight matrix by taking the sum of the outer products of the leading eigenvectors of the modal link-weight matrices.     

Parametric shape-from-shading by radial basis functions

We present a new method of shape from shading by using radial basis functions to parameterize the object depth. The radial basis functions are deformed by adjusting their centers, widths, and weights such that the intensity errors are minimized. The initial centers and widths are arranged hierarchically to speed up convergence and to stabilize the solution. Although the smoothness constraint is used, it can be eventually dropped out without causing instabilities in the solution. An important feature of our parametric shape-from-shading method is that it offers a unified framework for integration of multiple sensory information. We show that knowledge about surface depth and/or surface normals anywhere in the image can be easily incorporated into the shape from shading process. It is further demonstrated that even qualitative knowledge can be used in shape from shading to improve 3D reconstruction. Experimental comparisons of our method with several existing ones are made by using both synthetic and real images. Results show that our solution is more accurate than the others     

Fast and effective feature-preserving mesh denoising

We present a simple and fast mesh denoising method, which can remove noise effectively, while preserving mesh features such as sharp edges and corners. The method consists of two stages. Firstly, noisy face normals are filtered iteratively by weighted averaging of neighboring face normals. Secondly, vertex positions are iteratively updated to agree with the denoised face normals. The weight function used during normal filtering is much simpler than that used in previous similar approaches, being simply a trimmed quadratic. This makes the algorithm both fast and simple to implement. Vertex position updating is based on the integration of surface normals using a least-squares error criterion. Like previous algorithms, we solve the least-squares problem by gradient descent, but whereas previous methods needed user input to determine the iteration step size, we determine it automatically. In addition, we prove the convergence of the vertex position updating approach. Analysis and experiments show the advantages of our proposed method over various earlier surface denoising methods.     

Reconstruction of graphs based on random walks

The analysis of complex networks is of major interest in various fields of science. In many applications we face the challenge that the exact topology of a network is unknown but we are instead given information about distances within this network. The theoretical approaches to this problem have so far been focusing on the reconstruction of graphs from shortest path distance matrices. Often, however, movements in networks do not follow shortest paths but occur in a random fashion. In these cases an appropriate distance measure can be defined as the mean length of a random walk between two nodes — a quantity known as the mean first hitting time.In this contribution we investigate whether a graph can be reconstructed from its mean first hitting time matrix and put forward an algorithm for solving this problem. A heuristic method to reduce the computational effort is described and analyzed. In the case of trees we can even give an algorithm for reconstructing graphs from incomplete random walk distance matrices.     

基于FP-Growth的图上随机游走推荐方法

推荐是促进诸如社交网络等应用活跃度的重要模式,但 庞大 的节点规模以及复杂的节点间关系给社交网络的推荐问题带来了挑战。随机游走是一种能够有效解决这类推荐问题的策略,但传统的随机游走算法没有充分考虑相邻节点间影响力的差异。提出一种基于FP-Growth的图上随机游走推荐方法,其基于社交网络的图结构,引入FP-Growth算法来挖掘相邻节点之间的频繁度,在此基础上构造转移概率矩阵来进行随机游走计算,最后得到好友重要程度排名并做出推荐。该方法既保留了随机游走方法能有效缓解数据稀疏性等特性,又权衡了不同节点连接关系的差异性。实验结果表明,提出的方法比传统随机游走算法的推荐性能更佳。     

Terrain analysis using radar shape-from-shading

This paper develops a maximum a posteriori (MAP) probability estimation framework for shape-from-shading (SFS) from synthetic aperture radar (SAR) images. The aim is to use this method to reconstruct surface topography from a single radar image of relatively complex terrain. Our MAP framework makes explicit how the recovery of local surface orientation depends on the whereabouts of terrain edge features and the available radar reflectance information. To apply the resulting process to real world radar data, we require probabilistic models for the appearance of terrain features and the relationship between the orientation of surface normals and the radar reflectance. We show that the SAR data can be modeled using a Rayleigh-Bessel distribution and use this distribution to develop a maximum likelihood algorithm for detecting and labeling terrain edge features. Moreover, we show how robust statistics can be used to estimate the characteristic parameters of this distribution. We also develop an empirical model for the SAR reflectance function. Using the reflectance model, we perform Lambertian correction so that a conventional SFS algorithm can be applied to the radar data. The initial surface normal direction is constrained to point in the direction of the nearest ridge or ravine feature. Each surface normal must fall within a conical envelope whose axis is in the direction of the radar illuminant. The extent of the envelope depends on the corrected radar reflectance and the variance of the radar signal statistics. We explore various ways of smoothing the field of surface normals using robust statistics. Finally, we show how to reconstruct the terrain surface from the smoothed field of surface normal vectors. The proposed algorithm is applied to various SAR data sets containing relatively complex terrain structure.     

一种计算矩阵特征值特征向量的神经网络方法

当把Oja学习规则描述的连续型全反馈神经网络(Oja-N)用于求解矩阵特征值特征向量时,网络初始向量需位于单位超球面上,这给应用带来不便.由此,提出一种求解矩阵特征值特征向量的神经网络(1yNN)方法.在lyNN解析解基础上得到了以下结果:初始向量属于任意特征值对应特征向量张成的子空间,则网络平衡向量也将属于该空间;分析了lyNN收敛于矩阵最大特征值对应特征向量的初始向量取值条件;明确了lyNN收敛于矩阵不同特征值的特征子空间时,网络初始向量的最大取值空间;网络初始向量与已知特征向量垂直,则lyNN平衡解向量将垂直于该特征向量;证明了平衡解向量位于由非零初始向量确定的超球面上的结论.基于以上分析,设计了用lyNN求矩阵特征值特征向量的具体算法,实例演算验证了该算法的有效性.1yNN不出现有限溢,而基于Oja-N的方法在矩阵负定、初始向量位于单位超球面外时必出现有限溢,算法失效.与基于优化的方法相比,lyNN实现容易,计算量较小.