Palette re-ordering is an effective approach for improving the compression of color-indexed images. If the spatial distribution of the indexes in the image is smooth, greater compression ratios may be obtained. As is already known, obtaining an optimal re-indexing scheme is not a trivial task. In this paper, we provide a novel algorithm for palette re-ordering problem making use of a motor map neural network. Experimental results show the real effectiveness of the proposed method both in terms of compression ratio and zero-order entropy of local differences. Also, its computational complexity is competitive with previous works in the field.