Veja potrace para vetorizar imagens em preto e branco. Dá resultados muito bons para imagens do tipo cartoon (embora você possa precisar ajustar os parâmetros).
No caso geral, suponho que você poderia usar o gimp para extrair bordas e, em seguida, alimentá-lo para o potrace e, em seguida, rasterizá-lo em uma resolução mais alta e adicioná-lo como uma camada na parte superior da imagem original.