Soft delete + cronjob recommend:
I don't recommend a fully deletion of the records except you have to as of data privacy e.g.
However, as been mentioned already add to each table a column like deleted
and when a record has to be deleted you set the value in this column to true.
After this you can develop a cronjob which will be triggered. E.g. on a daily base during midnight.
A cronjob usually will be executed on a shell and has not the short time out as a browser has.
In your case: don't delete all data when image has been removed:
When you are dealing with just a few records it is legit to delete all records fully when a user wants to delete them.
However, in your case there are probably thousands of records which has to be deleted. So, when you try to delete all of them when a user deletes a certain image it surely takes time and probably end in a time out. Doing it via ajax is not good as users don't want to wait until all ajax-requests has been finished.