con un programa de retoque fotográfico no vas a sacar calidad de donde no la hay, yo te recomiendo que lo pases a vectores con un programa tipo, corel, freehand, ilustrator...
así una vez que lo tengas hecho podrás aumentarla todo lo que quieras sin perder calidad.
Salu2