Os dados aoagados da galeria continuam no aparelho eles apenas são marcados como invisíveis pelo sistema.
Se você baixar um monte de coisas ou ficar usando o celular, estes dados serão sobrescritos. Quanto mais usar o celular menores as chances de recuperação de dados.
Você vai precisar de um computador. Vai precisar dar root no celular e conectar ele via cabo no PC.
Depois você usa um tipo de programa chamado file recovery.
Faz um tempinho que não uso, mas o "Recurva" e o "wondershare file recovery" costumam ser bons.