图像恢复问题的随机算法研究

Research on Random Algorithms for Image Restoration Problems

摘要: 经典奇异值分解(SVD)图像去躁算法常依赖全局统一的截断秩，难以兼顾图像局部平滑与边缘结 构的差异。 此外，直接将针对逆问题的截断补偿策略(如MTRSVD的尾部填充)应用于纯数据域 去躁时，会在数学上向躁声子空间注入伪能量，导致去躁性能受损。 针对上述局限，本文提出了 一种基于分块梯度排序与分组自适应随机奇异值分解(RSVD)的图像去躁算法。 首先，将图像分 块并依据全变分(TV)特征对列向量进行升序重排，人为诱导矩阵在局部空间产生强连贯的低秩流 形。 其次，通过严格的矩阵代数分析，本文揭示并证明了在全局线性正交投影条件下，对重排操 作必然导致的“数学抵消效应”。 为打破该理论困境并主动顺应自然图像局部结构的非平稳性，本 文创新性地引入基于分段非线性投影的分组自适应截断机制，结合基于Hutchinson迹估算的随机 误差准则，为不同复杂度的图像子组动态计算最优截断秩，并执行纯粹的RSVD低秩逼近。 消融 实验与泛化性能对比表明，相较于全局固定秩、 不分组的自适应算法，以及代表性的重型经典方 法一一三维块匹配(BM3D)与传统加权核范数最小化(WNNM)算法，本文算法不仅有效规避了 传统算法高躁易失效与缺乏局部自适应的短板，更以仅约0.03秒的毫秒级极低开销(比传统重型算 法快近1000 倍)，取得了极具竞争力的去躁保真表现(PSNR/SSIM)。 本文成功开辟了一条在强 力去躁、 细节保真与极致计算吞吐量之间取得高度平衡的新路径，为大规模图像恢复提供了高效 的数值代数方案。

Abstract: Classical singular value decomposition (SVD) image denoising algorithms often rely on a globally uniform truncation rank, making it difficult to balance the differences between local smoothness and edge structures. Furthermore, directly applying trun- cation compensation strategies designed for inverse problems (such as the tail-filling in MTRSVD) to pure data-domain denoising mathematically injects pseudo-energy into the noise subspace, thereby degrading denoising performance. To address these limitations, this paper proposes an image denoising algorithm based on patch gradient sorting and grouped adaptive randomized singular value decomposition (RSVD). First, images are partitioned into patches, and the column vectors are rearranged in ascend- ing order according to their total variation (TV) characteristics, artificially inducing highly coherent low-rank manifolds in the local space. Second, through rigorous ma- trix algebraic analysis, this paper reveals and proves the “mathematical cancellation effect” of the rearrangement operation strictly under the condition of global linear orthogonal projection. To break through this theoretical dilemma and proactively adapt to the non-stationarity of local structures in natural images, this paper innova- tively introduces a grouped adaptive truncation mechanism based on piecewise non- linear projection. Combined with a randomized error criterion based on Hutchinson’s trace estimation, the optimal truncation rank is dynamically calculated for image sub- groups of varying complexities, and a pure RSVD low-rank approximation is executed. Ablation experiments and generalization performance comparisons demonstrate that, compared with globally fixed-rank algorithms, un-grouped adaptive algorithms, as well as representative heavy-duty classical methods like Block-Matching 3D filtering (B- M3D) and traditional Weighted Nuclear Norm Minimization (WNNM), the proposed algorithm not only effectively circumvents the shortcomings of traditional methods (e.g., failure under high noise and lack of local adaptability), but also achieves highly competitive denoising fidelity (PSNR/SSIM) with a millisecond-level, extremely low overhead of only about 0.03 seconds (nearly 1000 times faster than traditional heavy algorithms). This work successfully pioneers a new path that strikes a high degree of balance among robust denoising, detail preservation, and extreme computation- al throughput, providing an exceptionally efficient numerical algebraic solution for large-scale image restoration.