Efficient representation of geometrical information in images is very important in many image processing areas, including compression, denoising and feature extraction. However, the design of transforms that can capture these geometrical features and represent them with a sparse description is very challenging. Recently, the separable wavelet transform achieved a great success providing a computationally simple tool and allowing for a sparse representation of images. However, in spite of the success, the efficiency of the representation is limited by the spatial isotropy of the wavelet basis functions built in the horizontal and vertical directions as well as the lack of directionality. One-dimensional discontinuities in images (edges and contours), which are very important elements in visual perception, intersect with too many wavelet basis functions leading to a non-sparse representation. To capture efficiently these anisotropic geometrical structures characterized by many more than the horizontal and vertical directions, more flexible multi-directional and anisotropic transforms are required. We present a new lattice-based perfect reconstruction and critically sampled anisotropic multi-directional wavelet transform. The transform retains the separable filtering, subsampling and simplicity of computations and filter design from the standard two-dimensional wavelet transform, unlike in the case of some other existing directional transform constructions (e.g. curvelets, contourlets or edgelets). The corresponding anisotropic basis functions, which we call directionlets, have directional vanishing moments along any two directions with rational slopes. Furthermore, we show that this novel transform provides an efficient tool for non-linear approximation of images, achieving the decay of mean-square error O(N-1.55), which, while slower than the optimal rate O(N-2), is much better than O(N-1) achieved with wavelets, but at similar complexity. Owing to critical sampling, directionlets can easily be applied to image compression since it is possible to use Lagrange optimization as opposed to the case of overcomplete expansions. The compression algorithms based on directionlets outperform the methods based on the standard wavelet transform achieving better numerical results and visual quality of the reconstructed images. Moreover, we have adapted image denoising algorithms to be used in conjunction with an undecimated version of directionlets obtaining results that are competitive with the current state-of-the-art image denoising methods while having lower computational complexity.