In this paper, we propose a lossless compression scheme for binary images which consists of a novel encoding algorithm which uses a new edge tracking algorithm. The proposed compression scheme has two sub- stages: (i) encoding binary image data using the proposed encoding method (ii) compression the encoded image data using any well-known image compression method such as Huffman, Run-Length or Lempel-Ziv-Welch (LZW). The proposed encoding method contains two subsequent processes: (i) determining the starting points of independent objects (ii) obtaining their edge points and geometrical shapes information. Experimental results show that using the proposed encoding method together with any traditional compressing method improves the compression performance. Computed mathematical results related to compression performance are represented comparatively in a tabular format.