传统的图像块匹配加速算法都要求待匹配的图像块具有预先定义好的形状。但有时候由于数据损坏、丢失等原因，待匹配块的形状是不规则的（如图像修复）。针对这种情况，提出了一种无损精度的不规则块匹配加速算法，将不规则块匹配扩展为一求最小加权平方差和（WSSD）的问题，块的形状间接地通过每个像素的权重来控制，这使得图像块都能被统一地当成矩形块。为了进行加速，提出了用快速傅里叶变换（FFT）计算WSSD的方法。并利用待匹配块及其权重在傅里叶变换过程中需大面积补零的特殊性改进了FFT算法，在不损失精度的前提下，进一步降低了其复杂度。最后以图像修复为例，说明WSSD是比SSD更一般的图像块相似度，并为各种图像块匹配的应用提供了一种统一的处理框架。

Traditional methods for fast patch matching can deal with only image patches with predefined shapes. However, in some cases （e.g. image completion） the patch shape is irregular and different from patch to patch due to destroyed or missing data. In this paper we propose an efficient method for accurate irregular patch matching. We formulate irregular patch matching as a problem to find the minimum weighted SSD （WSSD）, and the shape of patches is controlled indirectly with the weights of pixels. In this way all patches can be taken to be rectangular, and then the computation of WSSD can be accelerated with fast Fourier transform （FFT）. By taking advantage of the property that large area of patch should be padded with zero. We improve the FFT algorithm and further improve its performance without sacrificing accuracy. At the end of this paper we take image completion as an example to show that WSSD is a more general measure of patch similarity than SSD, and can serve as a uniform framework for various applications that involve image patch matching.