The problem of block noise removal is considered. It is assumed that the original image is on or close to a sub-space of admissible images in the form of a low dimensional nonlinear manifold. We propose to use a close variant of the total variation regularizer for measuring block noise. Based on this noise measure, we present an effective approach that reconstructs the original image in the presence of block noise. Our main computational task is the solution of a quadratic programming problem, for which we propose a very efficient interior point method. The effectiveness and efficiency of our approach is demonstrated by an example.