A similarity enrichment scheme for the application to image compression through the extension of weighted finite automata (WFA) has been recently proposed [1 ] by the authors. We shall here first establish additional theoretical results on the extended WFA of minimum states. We then devise an effective inference algorithm and its concrete implementation through the consideration of WFA of minimum states, image approximation in least squares, state image intensity generation via Gauss-Seidel method, as well as the improvement on the decoding efficiency. The codec implemented this way will exemplify explicitly the performance gain due to extended WFA under otherwise the same conditions.