I'm working on a computer vision problem and I want to use the Mahalanobis distance to cluster image patches (2D matrices having the same dimensions). I haven't been able to find any generalisation up to this point and would prefer not to vectorise my patches and end-up with a huge covariance matrix.
If your "image patches" are what I think they are (i.e. 2D arrays of samples), then mathematically they are vectors, not matrices.
In linear algebra, a vector represents a position or a distance in multidimensional space, such as an array of samples, while a matrix represents a linear map from one vector space to another (or possibly the same one). The fact that vectors are commonly written as one-dimensional arrays, and matrices as two-dimensional arrays, is really more of an arbitrary historical convention.
It's not completely arbitrary, since a vector does of course need to be at least one-dimensional, while a matrix, being essentially a vector of vectors, is naturally represented as an array with twice as many dimensions as a vector. But there are plenty of situations, such as when working with 2D image data, where one does end up with vectors that would be most naturally represented as 2D arrays (implying that matrices mapping such "2D vectors" to other "2D vectors" really should be four-dimensional arrays).
The standard way of handling such situations is to flatten the "2D vectors" into ordinary one-dimensional vectors, and any matrices applied to them into two-dimensional block matrices, and then work with them using ordinary linear algebra. This does tend to yield large and awkward-looking expressions if you try to print them out without first transforming them back into a form better suited for the structure of your data, but that's kind of unavoidable when working with such data.
In any case, the question you should ask yourself is whether your 2D "image patches" somehow represent linear transformations between one-dimensional vectors. If not, then they're not matrices, and any attempt to treat them as matrices will probably end up producing nonsense. Instead, you should treat them as what they are, i.e. presumably as vectors of samples.
And yes, if your patches are large, then covariance matrices (which really are matrices in the linear algebra sense!) between them will probably end up being huge and hard to visualize. Which isn't really that surprising, given that they're fundamentally representing a four-dimensional data set, and humans aren't very good at visualizing 4D data.