The cost of processing imagery that exhibits a large data burden can be reduced by compressive processing, which computes over a compressed image versus the corresponding (uncompressed) source image. When the compressive result is decompressed, one obtains an approximation to the corresponding operation over uncompressed imagery. In previous publications, we have shown that compressive processing can lead to computational efficiency (e.g., a sequential speedup) that approaches the compression ratio. In certain cases, computational speedup that exceeds the compression ratio can be achieved with sufficient parallelism. We have also derived techniques for computing pointwise arithmetic operations, global reduce operations such as image sum or image maximum, and selected image- template operations over imagery compressed by several blockwise transformations. In particular, our previous research has emphasized the processing of imagery compressed by block truncation coding, vector quantization (VQ), and visual pattern image coding (VPIC). In this paper, we extend our previous work by deriving algorithms that more accurately simulate the operations of Prewitt, Sobel, and Kirsch edge detection over imagery compressed by VQ and VPIC transforms. We also derive morphological operations of erosion and dilation with the von Neumann template over VQ- and VPIC-compressed Boolean imagery. Analysis of each operation includes a model of computational complexity and theoretical/experimental assessment of information loss incurred by computing over a lossy compressed image representation. We show that edge detection over VPIC- compressed imagery can be implemented in terms of a simple codebook transformation. Thus, if an uncompressed (source) image has N pixels and the compression ratio is denoted by CR, approximately O(N/CR) substitutions of exemplars from the transformed codebook are required. This technique is extensible to certain morphological operations with the von Neumann template and can be implemented in SIMD-parallel fashion.