In this paper, a very efficient image denoising scheme, which is called nonlocal means based on bidirectional principal component analysis, is proposed. Unlike conventional principal component analysis (PCA) based methods, which stretch a 2D matrix into a 1D vector and ignores the relations between different rows or columns, we adopt the technique of bidirectional PCA (BDPCA), which preserves the spatial structure and extract features by reducing the dimensionality in both column and row directions. Moreover, we also adopt the coarse-to-fine procedure without performing nonlocal means iteratively. Simulations demonstrated that, with the proposed scheme, the denoised image can well preserve the edges and texture of the original image and the peak signal-to-noise-ratio is higher than that of other methods in almost all the cases.