A paraperspective factorization method for shape and motionrecovery

The factorization method, first developed by Tomasi and Kanade (1992), recovers both the shape of an object and its motion from a sequence of images, using many images and tracking many feature points to obtain highly redundant feature position information. The method robustly processes the feature trajectory information using singular value decomposition (SVD), taking advantage of the linear algebraic properties of orthographic projection. However, an orthographic formulation limits the range of motions the method can accommodate. Paraperspective projection, first introduced by Ohta et al. (1981), is a projection model that closely approximates perspective projection by modeling several effects not modeled under orthographic projection, while retaining linear algebraic properties. Our paraperspective factorization method can be applied to a much wider range of motion scenarios, including image sequences containing motion toward the camera and aerial image sequences of terrain taken from a low-altitude airplane     

从运动中恢复目标结构的改进因子分解法

因子分解法是从图像序列中恢复刚体目标几何结构的重要方法。针对传统因子分解法基本过程中存在的不足,及其容易失效的缺点,提出一种改进的因子分解法。该方法避开传统方法中求解修正矩阵的复杂过程,利用旋转矩阵的特性,直接修正由传统方法奇异值分解(SVD)得到的每帧图像的旋转矩阵,然后根据观测矩阵和得到的旋转矩阵,直接利用线性最小二乘法求解目标的结构矩阵。仿真和实测数据的实验结果表明,本文方法能够有效地从序列图像中恢复目标的几何结构,相比传统因子分解法,在稳定性上有较大的提升。     

Motion and shape recovery based on iterative stabilization for modest deviation from planar motion

We describe an iterative stabilization method that can simultaneously recover camera motion and 3D shape from an image sequence captured under modest deviation from planar motion. This technique iteratively applies a factorization method based on planar motion and can approximate the observed image points to the 2D points projected under planar motion by stabilizing the camera motion. We apply the proposed method to aerial images acquired by a helicopter-borne camera and show better reconstruction of both motion and shape than Christy-Horaud's perspective factorization. Moreover, we confirm that the reprojection errors calculated from the recovered camera motion and 3D shape are very similar to the optimum results yielded by bundle adjustment.     

An improved parallel Jacobi method for diagonalizing a symmetric matrix

We compare five implementations of the Jacobi method for diagonalizing a symmetric matrix. Two of these, the classical Jacobi and sequential sweep Jacobi, have been used on sequential processors. The third method, the parallel sweep Jacobi, has been proposed as the method of choice for parallel processors. The fourth and fifth methods are believed to be new. They are similar to the parallel sweep method but use different schemes for selecting the rotations.

The classical Jacobi method is known to take O(n⁴) time to diagonalize a matrix of order n. We find that the parallel sweep Jacobi run on one processor is about as fast as the sequential sweep Jacobi. Both of these methods take O(n³ log₂n) time. One of our new methods also takes O(n³ log₂n) time, but the other one takes only O(n³) time. The choice among the methods for parallel processors depends on the degree of parallelism possible in the hardware. The time required to diagonalize a matrix on a variety of architectures is modeled.

Unfortunately for proponents of the Jacobi method, we find that the sequential QR method is always faster than the Jacobi method. The QR method is faster even for matrices that are nearly diagonal. If we perform the reduction to tridiagonal form in parallel, the QR method will be faster even on highly parallel systems.     

Shape and motion from image streams under orthography: a factorization method

Inferring scene geometry and camera motion from a stream of images is possible in principle, but is an ill-conditioned problem when the objects are distant with respect to their size. We have developed a factorization method that can overcome this difficulty by recovering shape and motion under orthography without computing depth as an intermediate step.An image stream can be represented by the 2F×P measurement matrix of the image coordinates of P points tracked through F frames. We show that under orthographic projection this matrix is of rank 3.Based on this observation, the factorization method uses the singular-value decomposition technique to factor the measurement matrix into two matrices which represent object shape and camera rotation respectively. Two of the three translation components are computed in a preprocessing stage. The method can also handle and obtain a full solution from a partially filled-in measurement matrix that may result from occlusions or tracking failures.The method gives accurate results, and does not introduce smoothing in either shape or motion. We demonstrate this with a series of experiments on laboratory and outdoor image streams, with and without occlusions.     

改进的增量奇异值分解协同过滤算法

推荐系统作为一种程序算法,是通过度量用户对给定商品的的喜好程度做个性化推荐。广泛地说,推荐系统试图总结出用户的个人喜好,并在用户和商品之间建立一种关系模型。与其他奇异值分解方法相比,改进的增量奇异值分解协同过滤算法基于一系列评分值对用户-商品矩阵进行分解,每次产生一对当前最重要的特征向量。算法有着最小的内存需求,扩展性高,特别适合处理大规模数据集;算法的有效性在Netflix数据集上得到了验证。     

Dynamic look-ahead in the reduction to band form for the singular value decomposition

We investigate the introduction of look-ahead in two-stage algorithms for the singular value decomposition (SVD). Our approach relies on a specialized reduction for the first stage that produces a band matrix with the same upper and lower bandwidth instead of the conventional upper triangular-band matrix. In the case of a CPU-GPU server, this alternative form accommodates a static look-aheadinto the algorithm in order to overlap the reduction of the “next” panel on the CPU and the “current” trailing update on the GPU. For multicore processors, we leverage the same compact form to formulate a version of the algorithm that advances the reduction of “future” panels, yielding a dynamic look-ahead that overcomes the performance bottleneck that the sequential panel factorization represents.     

Constant-time algorithm for computing the Euclidean distance maps of binary images on 2D meshes with reconfigurable buses

The computation of Euclidean distance maps (EDM), also called Euclidean distance transform, is a basic operation in computer vision, pattern recognition, and robotics. Fast computation of the EDM is needed since most of the applications using the EDM require real-time computation. It is shown in L. Chen and H.Y.H. Chuang [Information Processing Letters, 51, pp. 25–29 (1994)] that a lower bound Ω(n²) is required for any sequential EDM algorithm due to the fact that in any EDM algorithm each of the n² pixels has to be scanned at least once. Recently, many parallel EDM algorithms have been proposed to speedup its computation. Chen and Chuang proposed an algorithm for computing the EDM on an n×n mesh in O(n) time [L. Chen and H.Y.H. Chuang Parallel Computing, 21, pp. 841–852 (1995)]. Clearly, the VLSI complexities of both the sequential and the mesh algorithm described in L. Chen and H.Y.H. Chuang [Parallel Computing, 21, pp. 841–852 (1995)] are AT²=O(n⁴), where A is the VLSI layout area of the design and T is the computation time using area A when implemented in VLSI. In this paper, we propose a new and faster parallel algorithm for computing the EDM problem on the reconfigurable VLSI mesh model. For the same problem, our algorithm runs in O(1) time on a two-dimensional n²×n² reconfigurable mesh. We show that the VLSI complexity of our algorithm is the same as those of the above sequential algorithm and the mesh algorithm, while it uses much less time. To our best knowledge, this is the first constant-time EDM algorithm on any parallel computational model.     

Scaled rotation regularization

A new regularization method - a scaled rotation - is proposed and compared with the standard linear regularized discriminant analysis. A sense of the method consists in the singular value decomposition S=TDT′ of a sample covariance matrix S and a use of the following representation of an inverse of the covariance matrix S⁻¹=T(D+λI)⁻¹T ′. For certain data structures the scaled rotation helps to reduce the generalization error in small learning-set and high dimensionality cases. Efficacy of the scaled rotation increases if one transforms the data by y=(D+λI)^−1/2T ′x and uses an optimally stopped single layer perceptron classifier afterwards.     

Constant-Time Filtering by Singular Value Decomposition†

We present a technique implementing space-variant filtering of an image, with kernels belonging to a given family, in time independent of the size and shape of the filter kernel support. The essence of our method is efficient approximation of these kernels, belonging to an infinite family governed by a small number of parameters, as a linear combination of a small number k of “basis” kernels. The accuracy of this approximation increases with k, and requires O(k) storage space. Any kernel in the family may be applied to the image in O(k) time using precomputed results of the application of the basis kernels. Performing linear combinations of these values with appropriate coefficients yields the desired result. A trade off between algorithm efficiency and approximation quality is obtained by adjusting k. The basis kernels are computed using singular value decomposition, distinguishing this from previous techniques designed to achieve a similar effect. We illustrate by applying our methods to the family of elliptic Gaussian kernels, a popular choice for filtering warped images.     

PERFORM: a fast object recognition method using intersection ofprojection

This paper describes an object recognition methodology called PERFORM that finds matches by establishing correspondences between model and image features using this formulation. PERFORM evaluates correspondences by intersecting error regions in the image space. The algorithm is analyzed with respect to theoretical complexity as well as actual running times. When a single solution to the matching problem is sought, the time complexity of the sequential matching algorithm for 2D-2D matching using point features is of the order O(l³ N ²), where N is the number of model features and l is the number of image features. When line features are used, the sequential complexity is of the order O(l² N²). When a single solution is sought, PERFORM runs faster than the fastest known algorithm to solve the bounded-error matching problem. The PERFORM method is shown to be easily realizable on both SIMD and MIMD architectures     

Computation of the singular value expansion

A method for computing the singular values and singular functions of real square-integrable kernels is presented. The analysis shows that a “good” discretization always yields a matrix whose singular value decomposition is closely related to the singular value expansion of the kernel. This relationship is important in connection with the solution of ill-posed problems since it shows that regularization of the algebraic problem, derived from an integral equation, is equivalent to regularization of the integral equation itself.     

求解低秩矩阵融合高动态范围图像

目的 利用低秩矩阵恢复方法可从稀疏噪声污染的数据矩阵中提取出对齐且线性相关低秩图像的优点,提出一种新的基于低秩矩阵恢复理论的多曝光高动态范围（HDR）图像融合的方法,以提高HDR图像融合技术的抗噪声与去伪影的性能。方法 以部分奇异值（PSSV）作为优化目标函数,可构建通用的多曝光低动态范围（LDR）图像序列的HDR图像融合低秩数学模型。然后利用精确增广拉格朗日乘子法,求解输入的多曝光LDR图像序列的低秩矩阵,并借助交替方向乘子法对求解算法进行优化,对不同的奇异值设置自适应的惩罚因子,使得最优解尽量集中在最大奇异值的空间,从而得到对齐无噪声的场景完整光照信息,即HDR图像。结果 本文求解方法具有较好的收敛性,抗噪性能优于鲁棒主成分分析（RPCA）与PSSV方法,且能适用于多曝光LDR图像数据集较少的场合。通过对经典的Memorial Church与Arch多曝光LDR图像序列的HDR图像融合仿真结果表明,本文方法对噪声与伪影的抑制效果较为明显,图像细节丰富,基于感知一致性（PU）映射的峰值信噪比（PSNR）与结构相似度（SSIM）指标均优于对比方法：对于无噪声的Memorial Church图像序列,RPCA方法的PSNR、SSIM值分别为28.117 dB与0.935,而PSSV方法的分别为30.557 dB与0.959,本文方法的分别为32.550 dB与0.968。当为该图像序列添加均匀噪声后,RPCA方法的PSNR、SSIM值为28.115 dB与0.935,而PSSV方法的分别为30.579 dB与0.959,本文方法的为32.562 dB与0.967。结论 本文方法将多曝光HDR图像融合问题与低秩最优化理论结合,不仅可以在较少的数据量情况下以较低重构误差获取到HDR图像,还能有效去除动态场景伪影与噪声的干扰,提高融合图像的质量,具有更好的鲁棒性,适用于需要记录场景真实光线变化的场合。     

采用SVD-NMF的管道泄漏信号去噪算法

在管道泄漏检测中,压力信号中的噪声干扰会降低传统互相关法的定位精度。传统的去噪算法对环境的适应性差,去噪效果不理想。为此,提出了一种奇异值分解SVD( Singular Value Decomposition)与非负矩阵分解NMF( Nonnegative Matrix Factorization)相结合的管道泄漏信号去噪算法。该方法首先通过奇异值分解确定非负矩阵分解的阶数并对其初始化;然后,采用改进的非负矩阵分解算法对原信号进行迭代分解,获得去噪信号;最后,对去噪信号进行处理后通过互相关计算时延,并结合泄漏信号的传播速度实现泄漏定位。大量实验结果表明,SVD￣NMF算法能够显著降低迭代次数,提高去噪速度;同时在泄漏检测中,能够达到去除噪声干扰,提高定位精度的目的。     

基于稀疏约束的半监督非负矩阵分解算法

矩阵分解因可以实现大规模数据处理而具有十分广泛的应用。非负矩阵分解(Nonnegative Matrix Factorization,NMF)是一种在约束矩阵元素为非负的条件下进行的分解方法。利用少量已知样本的标注信息和大量未标注样本,并施加稀疏性约束,构造了一种新的算法——基于稀疏约束的半监督非负矩阵分解算法。推导了其有效的更新算法,并证明了该算法的收敛性。在常见的人脸数据库上进行了验证,实验结果表明CNMFS算法相对于NMF和CNMF等算法具有较好的稀疏性和聚类精度。     

Pattern recognition in multilinear space and its applications: mathematics,computational algorithms and numerical validations

We clarify the mathematical equivalence between low-dimensional singular value decomposition and low-order tensor principal component analysis for two- and three-dimensional images. Furthermore, we show that the two- and three-dimensional discrete cosine transforms are, respectively, acceptable approximations to two- and three-dimensional singular value decomposition and classical principal component analysis. Moreover, for the practical computation in two-dimensional singular value decomposition, we introduce the marginal eigenvector method, which was proposed for image compression. For three-dimensional singular value decomposition, we also show an iterative algorithm. To evaluate the performances of the marginal eigenvector method and two-dimensional discrete cosine transform for dimension reduction, we compute recognition rates for six datasets of two-dimensional image patterns. To evaluate the performances of the iterative algorithm and three-dimensional discrete cosine transform for dimension reduction, we compute recognition rates for datasets of gait patterns and human organs. For two- and three-dimensional images, the two- and three-dimensional discrete cosine transforms give almost the same recognition rates as the marginal eigenvector method and iterative algorithm, respectively.     

一种NMF和SVD相结合的鲁棒水印算法

提出了一种非负矩阵变换(NM})和奇异值分解(SVD)相结合的数字水印算法。该算法对宿主图像进行离散小波变换,然后选取低频部分进行非负矩阵变换和奇异值分解,最后在奇异值中嵌入Arnold置乱后的水印。实验表明,该算法在获得良好的视觉效果的同时,又具有很好的鲁棒性,对加噪、滤波、剪切等图像攻击有很好的抵杭能力。     

利用差分图像奇异值分解的置乱程度评价研究

提出了基于差分图像和奇异值分解相结合的图像置乱效果评价新方法。针对基于奇异值分解法的置乱程度评价法不能客观地反映图像置乱效果好坏的不足,首先对置乱前后图像进行差分运算并得到其相应的差分图像,其次对两差分图像进行奇异值分解,最后计算其奇异值差异程度的大小作为图像置乱效果评价的新准则。实验结果表明,提出的评价方法能够较好地刻画图像的置乱程度,反映了加密次数与置乱程度之间的关系,与人的视觉基本相符。对于不同的图像,该评价方法在一定程度上反映了所用的置乱变换在各置乱阶段的效果。     

基于全局运动估计的视频对象分割算法

视频全局运动(摄像机运动)所表现的视频序列之间的时间相关性,较其它视频特征更能表达视频序列的高层语义信息.为了能够有效快速的得到视频的全局运动,通过对视频运动估计方法的研究,提出了一种新的基于奇异值分解(SVD)的视频全局运动估计算法.该方法首先通过块匹配法得到局部运动场,利用矩阵的奇异值分解估计全局运动参数,然后运用形态学运动滤波得到前景运动目标的粗略掩摸图像,最后综合利用此掩摸图像和边缘信息分割出运动目标.试验表明,提出的算法能够分割出具有全局运动特征的视频序列中的运动目标.     

基于NMF和SVD相结合的Contourlet域鲁棒水印算法*

为了提高变换域数字水印技术的鲁棒性,提出了一种在Contourlet域将非负矩阵变换(NMF)与奇异值变换(SVD)相结合的鲁棒水印算法。宿主图像经过Contourlet变换后,对低频子带进行非负矩阵变换,然后对非负基向量组W进行奇异值分解,最后将经过Arnold置乱的水印图像嵌入到奇异值中。实验结果表明,该图像水印算法在获得良好视觉效果的同时,对于加噪声、滤波、剪切等图像攻击有较好的鲁棒性。