  This work combines three paradigms of image processing: i) the total
variation approach to denoising, ii) the superior structure of hexagonal
lattices, and iii) fast and exact graph cut optimization techniques. Although
isotropic in theory, numerical implementations of the $BV$ seminorm invariably
show anisotropic behaviour. Discretization of the image domain into a hexagonal
grid seems perfectly suitable to mitigate this undesirable effect. To this end,
we recast the continuous problem as a finite-dimensional one on an arbitrary
lattice, before focussing on the comparison of Cartesian and hexagonal
structures. Minimization is performed with well-established graph cut
algorithms, which are easily adapted to new spatial discretizations. Apart from
producing minimizers that are closer in the $\ell^1$ sense to the clean image
for sufficiently high degrees of regularization, our experiments suggest that
the hexagonal lattice also allows for a more effective reduction of two major
drawbacks of existing techniques: metrication artefacts and staircasing. For
the sake of practical relevance we address the difficulties that naturally
arise when dealing with non-standard images.
