多尺度并行坐标插值实时图像克隆算法

作为一种重要的数字图像合成编辑技术,图像克隆能够将源图像中的克隆区域平滑自然地嵌入目标图像的指定位置。 传统的图像克隆技术通过分析图像的梯度域并求解泊松方程来获取图像信息, 具有算法复杂度高、内存消耗大的缺点, 从而限制了其在高分辨率图像中的实时应用。本文提出了一种改进的均值坐标计算方法, 将图像克隆转化为高效且易于实现的图像插值流程。此外本文还采用多尺度和GPGPU并行计算技术进一步提升了算法的整体运算效率, 从而能够实现对100万像素图像区域的实时克隆。     

一种针对大波数Helmholtz方程的高性能并行预条件迭代求解算法

针对传统串行迭代法求解大波数Helmholtz方程存在效率低下且受限于单机内存的问题,提出了一种基于消息传递接口(Message Passing Interface,MPI) 的并行预条件迭代法。该算法利用复移位拉普拉斯算子对Helmholtz方程进行预条件处理,联合稳定双共轭梯度法和基于矩阵的多重网格法来求解预条件方程离散后的大规模线性系统,在Linux集群系统上基于 MPI环境实现了求解算法的并行计算,重点解决了多重网格的并行划分、信息传递和多重网格组件的构建问题。数值实验表明,对于大波数问题,提出的算法具有良好的并行加速比,相较于串行算法极大地提高了计算效率。     

基于卷积金字塔的屏蔽泊松方程快速求解算法

屏蔽泊松方程在图像视频处理和图形学领域有着广泛应用,传统上一般借助离散余弦变换或快速傅里叶变换求解,计算复杂度为O(nlogn).提出了一种基于卷积金字塔的快速近似求解算法,将屏蔽泊松方程求解视为一个"大核"卷积过程,利用卷积金字塔,将"大核"卷积分解为若干个"小核"卷积,从而将计算复杂度改善至线性.实验发现,在图像无缝拼合和梯度域绘制的应用中,对于千万像素级别图像,所提算法能获得5～6倍的性能提升.进一步,屏蔽泊松方程求解也是许多图像迭代算法的中间步骤,以加权最小二乘图像光滑和基于总变差正则化的图像重建算法为例,运用所提算法,在视觉效果和均方误差上都有着很好的近似,在速度上有显著的提升.     

一种基于正弦变换的三维泊松方程并行求解算法

泊松方程的数值解法在许多物理或者工程问题上得到广泛应用,但是由于大部分三维泊松方程的离散化格式不具有明显的并行性,实际中使用整体迭代的思想,这使得计算效率和稳定性受到了限制。摒弃了传统数值解法中整体迭代的思想,结合离散正弦变换理论(DST),基于27点四阶差分格式,将三维泊松方程求解算法在算法级进行修改和并行优化,把整个求解问题转化成多个独立的问题进行求解,稳定性和并行性能得到大幅提升。对于确定的离散化形式,可以使用同一套参数解决不同的泊松方程,大大提高了编程效率。基于共享存储并行模型实现了该算法,实验结果显示,对于给出的实例,新算法具有较好的加速效果,计算结果精度误差约为10e-5,在可接受范围内,并且计算精度随着维数的升高具有一定提升。     

二维泊松问题的并行共轭梯度算法

该论文研究了利用并行共轭梯度算法求解二维泊松方程的方法,在由24台微机组成的机群上进行了实验。实验数据表明并行共轭梯度算法适用于求解二维泊松方程,它具有收敛快,可扩展性强的特点。在实验的基础上提出并验证了适用于并行共轭梯度算法的合理计算节点数的选择函数。     

求解半线性椭圆型方程组的并行算法

本文结合区域分裂技术、多重网格方法、加速Ｓｃｈｗａｒｚ收敛方法、高低解方法、非线性Ｊａｃｏｂｉ迭代方法和Ｎｅｗｔｏｎ线性化迭代方法,设计了三种求解半线性椭圆型方程（组）的并行算法：并行Ｎｅｗｔｏｎ多重网格算法、并行非线性多重网格算法和并行加速Ｓｃｈｗａｒｚ收敛算法。数值试验说明这三种算法的并行计算是可行的。     

复用拉普拉斯算子的高效网格融合方法

针对传统基于测地线的泊松融合方法中插值旋转场与尺度场计算量大而影响交互建模的应用,提出了基于复用拉普拉斯算子的高效融合方法.该方法将几何融合、旋转场与尺度场的插值问题均转化为拉普拉斯（泊松）方程进行求解,仅需一次Cholesky分解和多次回代计算,得到融合所需的8个标量场,比起传统基于测地线的插值方法快两个数量级;随后,运用基于约束Delaunay三角化与离散极小曲面的鲁棒方法对融合边界处的网格进行优化,实现网格的高效融合.同时,再次复用拉普拉斯算子,在进行几何融合的同时,实现了纹理坐标的快速融合.该算法不仅能够处理具有复杂拓扑与多个边界模型,并获得与传统泊松融合方法相媲美的实验结果,而且显著地提高了效率,能够满足交互响应的需求.     

三维Navier-Stokes方程分步法的并行算法在异构平台上实现初探

本文选取了三维不可压缩流动方程的分步法(fractional-step method),其中动量方程使用BiCGSTAB算法进行迭代求解,而压力泊松方程使用Fourier变换法进行直接求解。本文研究该算法在集群平台上的并行算法,从区域分解入手,分析一维、两维、三维区域划分三种情况下,各并行处理器上的计算量与通讯量,根据分析结果使用两维区域分解。分析BiCGSTAB算法和泊松Fourier变换法在GPGPU异构平台上的移植方法。最后,本文分析了BiCGSTAB和泊松方程Fourier变换法两种算法在CPU集群和GPGPU异构平台上的并行性能结果。     

基于细分曲面的泊松网格编辑

针对具有丰富几何细节的三维网格模型,基于直接坐标操纵的传统编辑算法在编辑过程中不可避免地存在细节特征无法得到有效保持的问题.综合基于细分曲面的空间变形方法以及微分域网格编辑二者优势,提出一种基于细分曲面的泊松网格编辑方法.首先建立待变形网格模型的包围网格,以包围网格所决定的细分曲面构造变形控制曲面;然后根据用户变形意图操纵包围网格,将对应细分曲面变化信息转化为对网格模型泊松梯度场的改变;最后根据变化后的梯度场重建网格模型.文中方法交互简单、直观,具有多分辨率编辑的优势,可以有效地保持网格模型的细节特征.丰富的变形实例证明了该方法的有效性和可行性.     

求解二维椭圆型界面问题的外推完全多重网格法

针对二维椭圆型界面问题的离散化方程,应用外推插值技巧和样条插值方法在细网格层上构造合适的迭代初始值,加快V型多重网格法求解离散化系统的速度,设计了外推完全多重网格(EXFMG)法.数值实验表明新算法有效降低了迭代次数,计算量更少.     

Adaptive Compositing and Navigation of Variable Resolution Images

We present a new, high‐quality compositing pipeline and navigation approach for variable resolution imagery. The motivation of this work is to explore the use of variable resolution images as a quick and accessible alternative to traditional gigapixel mosaics. Instead of the common tedious acquisition of many images using specialized hardware, variable resolution images can achieve similarly deep zooms as large mosaics, but with only a handful of images. For this approach to be a viable alternative, the state‐of‐the‐art in variable resolution compositing needs to be improved to match the high‐quality approaches commonly used in mosaic compositing. To this end, we provide a novel, variable resolution mosaic seam calculation and gradient domain color correction. This approach includes a new priority order graph cuts computation along with a practical data structure to keep memory overhead low. In addition, navigating variable resolution images is challenging, especially at the zoom factors targeted in this work. To address this challenge, we introduce a new image interaction for variable resolution imagery: a pan that automatically, and smoothly, hugs available resolution. Finally, we provide several real‐world examples of our approach producing high‐quality variable resolution mosaics with deep zooms typically associated with gigapixel photography.     

Efficient Gradient‐Domain Compositing Using an Approximate Curl‐free Wavelet Projection

Gradient‐domain compositing has been widely used to create a seamless composite with gradient close to a composite gradient field generated from one or more registered images. The key to this problem is to solve a Poisson equation, whose unknown variables can reach the size of the composite if no region of interest is drawn explicitly, thus making both the time and memory cost expensive in processing multi‐megapixel images. In this paper, we propose an approximate projection method based on biorthogonal Multiresolution Analyses (MRA) to solve the Poisson equation. Unlike previous Poisson equation solvers which try to converge to the accurate solution with iterative algorithms, we use biorthogonal compactly supported curl‐free wavelets as the fundamental bases to approximately project the composite gradient field onto a curl‐free vector space. Then, the composite can be efficiently recovered by applying a fast inverse wavelet transform. Considering an n‐pixel composite, our method only requires 2n of memory for all vector fields and is more efficient than state‐of‐the‐art methods while achieving almost identical results. Specifically, experiments show that our method gains a 5× speedup over the streaming multigrid in certain cases.     

基于偏微分方程的误差分散逆半调改进算法

结合误差分散半调噪声特征,提出一种基于偏微分方程的逆半调改进算法。通过研究偏微分方程的去噪原理,以3次B样条函数作为扩散函数,采用迭代求解偏微分方程的方法估计逆半调图像,计算每次迭代前后图像梯度模值的增量以确定平滑度的调节参数,解决偏微分方程在应用中的参数选择自适应问题。实验结果表明,该算法在图像整体平滑度和细节保持能力上都具有较好的效果。     

Nonlinear multigrid methods for total variation image denoising

The classical image denoising technique introduced by Rudin, Osher, and Fatemi [17] a decade ago, leads to solve a constrained minimization problem for the total variation (TV) of the image. The formal first variation of the minimization problem is a nonlinear and highly anisotropic boundary value problem. In this paper, a computational PDE method based on a nonlinear multigrid scheme for restoring noisy images is suggested. Here, we examine different discretizations for the Euler–Lagrange equation as well as different smoothers within the multigrid scheme. Then we describe the iterative total variation regularization scheme, which starts with an isotropic (smooth) problem and leads to smooth edges in the image. Within the iteration the problem becomes more and more anisotropic and converges to an image with sharp edges. Finally, we present some experimental results for synthetic and real images.     

一种适于移动设备的全景图快速拼接方法

针对传统移动端全景图生成方法存在拼接速度慢、消耗内存以及存在接缝和“鬼影”等问题,提出了一种适用于移动设备的全景图生成算法。算法首先对源序列图像进行色彩校正,从而保证色彩及亮度均匀,以缩短后期图像融合时间;然后在全景图拼接过程中检测“鬼影”,同时运用梯度域目标移除和区域填充方法移除“鬼影”,利用泊松融合进行拼接后的平滑处理;同时在图像拼接过程中优化了内存分配机制,以减少在图像拼接过程中的内存消耗。通过编程实现了该算法,在配置为332MHz处理器和128MB内存的手机上对不同光照下拍摄的分辨率为1280×720的照片进行测试,并与传统的全局全景图拼接算法进行对比,若利用全局全景图拼接算法对2至9张源序列图像进行拼接,内存消耗为12.3~23.6MB,而提出的算法占用更少内存,分别为9.9~14.5MB。实验结果表明该方法消除图像接缝及“鬼影”较彻底,拼接速度快且节省内存,生成的最终全景图质量较好,可用于移动设备上的全景图拼接。     

Regularizing Image Reconstruction for Gradient‐Domain Rendering with Feature Patches

We present a novel algorithm to reconstruct high‐quality images from sampled pixels and gradients in gradient‐domain Rendering. Our approach extends screened Poisson reconstruction by adding additional regularization constraints. Our key idea is to exploit local patches in feature images, which contain per‐pixels normals, textures, position, etc., to formulate these constraints. We describe a GPU implementation of our approach that runs on the order of seconds on megapixel images. We demonstrate a significant improvement in image quality over screened Poisson reconstruction under the L₁ norm. Because we adapt the regularization constraints to the noise level in the input, our algorithm is consistent and converges to the ground truth.     

A Multigrid Approach for Minimizing a Nonlinear Functional for Digital Image Matching

In this paper, we consider a multigrid application in digital image processing. Here, the problem is to find a map, which transforms an image T into another image R such that the grey level of the different images are nearly equal in every picture-element. This problem arises in the investigation of human brains. The complete inverse problem is ill posed in the sense of Hadamard and nonlinear, so the numerical solution is quite difficult. We solve the inverse problem by a Landweber iteration. In each minimization step an approximate solution for the linearized problem is computed with a multigrid method as an inner iteration. Finally, we present some experimental results for synthetic and real images. Received December 30, 1998; revised August 16, 1999     

Poisson image fusion based on Markov random field fusion model

In this paper, we present a gradient domain image fusion framework based on the Markov Random Field (MRF) fusion model. In this framework, the salient structures of the input images are fused in the gradient domain, then the final fused image is reconstructed by solving a Poisson equation which forces the gradients of the fused image to be close to the fused gradients. To fuse the structures in the gradient domain, an effective MRF-based fusion model is designed based on both the per-pixel fusion rule defined by the local saliency and also the smoothness constraints over the fusion weights, which is optimized by graph cut algorithm. This MRF-based fusion model enables the accurate estimation of region-based fusion weights for the salient objects or structures. We apply this method to the applications of multi-sensor image fusion, including infrared and visible image fusion, multi-focus image fusion and medical image fusion. Extensive experiments and comparisons show that the proposed fusion model is able to better fuse the multi-sensor images and produces high-quality fusion results compared with the other state-of-the-art methods.     

基于梯度投影的图像盲复原算法

为了利用多帧退化图像信息快速恢复出高质量的图像,提出了一种新的递归梯度投影多帧图像盲复原算法。该算法充分利用多帧图像的先验信息,首先给出一种能够有效抑制噪声放大的新的代价函数,然后通过梯度投影算法对新的代价函数进行最小化以推导出迭代公式,最后通过频率域多次递归迭代运算对退化图像进行复原。模拟实验结果证明该算法运算快速,对于不同高斯噪声级别和不同PSF衰退的图像,均能够清晰地恢复出图像细节特征、同时也能够准确地恢复出衰退PSF。     

Videoshop: A new framework for spatio-temporal video editing in gradient domain

This paper proposes a new framework for video editing in gradient domain. The spatio-temporal gradient fields of target videos are modified and/or mixed to generate a new gradient field which is usually not integrable. We compare two methods to solve this “mixed gradient problem”, i.e., the variational method and loopy belief propagation. We propose a 3D video integration algorithm, which uses the variational method to find the potential function whose gradient field is closest to the mixed gradient field in the sense of least squares. The video is reconstructed by solving a 3D Poisson equation. The main contributions of our framework lie in three aspects: first, we derive a straightforward extension of current 2D gradient technique to 3D space, thus resulting in a novel video editing framework, which is very different from all current video editing software; secondly, we propose using a fast and accurate 3D discrete Poisson solver which uses diagonal multigrids to solve the 3D Poisson equation, which is up to twice as fast as a simple conventional multigrid algorithm; finally, we introduce a set of new applications, such as face replacement and painting, high dynamic range video compression and graphcut based video compositing. A set of gradient operators is also provided to the user for editing purposes. We evaluate our algorithm using a variety of examples for image/video or video/video pairs. The resulting video can be seamlessly reconstructed.