We consider the problem of obtaining a binary sketch from a grey level image and coding it at very low bit rates. Halftone representations of images have too many transitions from level to level, and cannot be coded at similar rates. We use an image segmentation algorithm, presented in a previous paper, to obtain the binary sketch. It is an adaptive thresholding scheme that uses spatial constraints and takes into consideration the local intensity characteristics of the image to obtain the sketch. The algorithm is applied to a variety of images. In particular, it is applied to images of human faces. The sketches preserve most of the information necessary for recognition. They are similar to what an artist would sketch with a few brushstrokes. The sketches are coded by tracing the boundaries of the black or white regions. For the human face images, our coding scheme typically requires less than 0.1 bit/pixel. This is substantially lower than what waveform coding techniques require. We also compare our technique to other thresholding schemes as well as edge detectors, and demonstrate its advantages.