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.