You want all this to happen before the response comes back from the server (that's two or three minutes away, after all). Since PHP runs on the server, it's not going to be available; so you're going to have to do it on the client, using JavaScript. Have the loading image in a hidden <div>, and display it when the form submits.
Later on, if you want to get really fancy, you can add a periodic Ajax update that queries the server to see how things are getting on and provide feedback on progress.
Since this is a clientside issue, I'm moving it to the clientside forum.