In this paper, a block-line-separated encoding approach (BLiSE) i s proposed for efficient and lossless compression of raster maps. Firstly, BLiSE separates a r aster map into blocks and lines through a r aster- map-decomposition algorithm. For each block, BLiSE uses a flag encoding to record t he location and color information, and a 4-direction Freeman coding to encode the block boundary. For each line, BLiSE directly applies t he 8-direction Freeman coding. With this separate-encoding strategy, BLiSE is highly suitable for compression of navigation maps. We evaluate BLiSE on a navigation-map dataset containing 100 raster maps and compare it with three traditional approaches, which are GIF, PNG and JP2000-LS. The results indicate an average compression ratio of 82.83 of the proposed BLiSE, which is much higher than that of several competing approaches.