In photoshop, add an adjustment layer, adjust levels, flatten the image again, use filters, sharpen, unsharp mask a couple times and thats it ! like i said 30 seconds or so in PS and thats the difference you get ! There are far better people at PS here that could get much better results, but that was a quicky to show you whats possible !
Best bet, is read through
this article that Matt wrote, and see if you can do the same sort of stuff in Linux package !