We consider the complexity of problems for highly compressed 2-dimensional texts: {\em compressed} pattern-matching (when the pattern is not compressed and the text is compressed) and {\em fully compressed} pattern-matching (when also the pattern is compressed). First we consider 2-dimensional compression in terms of straight-line programs, see \cite{KRS}. It is a natural way for representing very highly compressed images, by describing larger parts in terms of smaller (earlier described) ones. For 1-dimensional strings there exist polynomial-time deterministic algorithms for similar types of compression \cite{ABF1,FT,GKPR,KRS}. We show that the complexity {dramatically} increases in a 2-dimensional setting: \begin{itemize} \item %\hspace*{0.6cm} {\em Compressed matching} for two dimensional compressed images is {\em NP-complete}. \item %\hspace*{0.6cm} {\em Fully compressed matching} for two dimensional compressed images is {\em $\Sigma_2P$-complete}. \item %\hspace*{0.6cm} Testing a given occurrence of a two dimensional compressed pattern is {\em co-NP-complete}. \end{itemize} %\vskip 0.1cm \noindent On the other hand we show efficient algorithms for some related problems: \begin{itemize} \item %\hspace*{0.6cm} Testing equality of two compressed two dimensional patterns %can be done efficiently by a randomized algorithm (an application of algebraic techniques). \item %\hspace*{0.6cm} Testing a given occurrence of an uncompressed pattern in a two dimensional compressed image. %can be done efficiently by a deterministic algorithm. \end{itemize} %\noindent We also show the surprising fact that the compressed size of a subrectangle of a compressed two dimensional array can grow exponentially, unlike the one dimensional case.