I have an iPhone 4s 16 GB. I realized my photos took up a lot of space so I put most of them on my USB drive. I only kept 94 of them on my phone. But they still take up 463 MB of data. I looked at each photo on my laptop and they all took up between 100 and 600 KB each. There's ONE photo that takes up 3 MB but that's it. The rest are only a few hundred KB. I tried using that Phonecleaner thing and it did nothing. Also restarting my phone. Plus I have nothing saved to icloud or any shared photos or anything synced from my computer (I've never even signed into iCloud. EVER.). Just my normal album. 94 photos. Is there a reason why it's taking up so much storage space with so little photos?
Are there any photos in your "Recently Deleted" album? These still count towards your photos storage.
Try signing into iCloud and uploading the photos to iCloud Photo Library (enable at Settings > iCloud > Photos). The size of your iCloud Photo Library (Settings > iCloud > Manage Storage) should represent the size of the photos on your phone.
Some people have suggested performing a hard shut down (hold Power and Home buttons for 5 seconds until screen goes black) to reset Storage usage info.