I have deleted all photos from my iPhone 4s but phone usage and iTunes still show 16gb of photos
The best way to attack this is to make a good backup (perhaps two - one to iTunes and another iCloud) and then restore the device.

When you activate the phone, don't sign in to iCloud at all (or the app store) - just set it up as a new device. From there you can look at storage and then slowly add your Apple Accounts.

When you sign in to iCloud - look at the storage and see if it's downloading photos from the iCloud Drive, the Messages archives, the photo stream, etc...

My suspicion is you have iCloud and the "photos" are from the data that comes down from the server - even without having any photos in the photo app / camera roll.



Once you have a good feel for what item is causing the "photos" to arrive, you can then erase the phone and set it up from your backup if desired. You can also just reinstall the things you want on the device that was "set up as new" if that's easier than restoring a backup and deleting things you don't want.