Buenas,
Es normal lo que te pasa ya que estas perdiendo informacion.
Código Java:
Ver originalimagen_2.setRGB(i, j, imagen.getRGB(posX, posY));
imagen_2.setRGB(posX, posY, imagen.getRGB(i, j));
Cuando sustituyes el RBG recoges el valor del pixel de una imagen 'limpia' (imagen).Esto no es correcto, ya que debes trabajar siempre con el valor 'verdadero'.
Imaginate una imagen de cuatro pixeles con colores 1,2,3,4
Recorres cada pixel y obtienes un aleatorio
Paso 1 -> posicion 1 0 -> aleatorio 3 0 -> resultado 3,2,1,4
Paso 2 -> posicion 2 0 -> aleatorio 3 0 -> resultado 3,3,2,4
Paso 3 -> posicion 3 0 -> aleatorio 4 0 -> resultado 3,3,4,3
Paso 4 -> posicion 4 0 -> aleatorio 1 0 -> resultado 4,3,4,1
El resultado es 4,3,4,1. Has perdido definitivamente el valor 2!!!, por lo que no puedes reconstruir la imagen correctamente.
Cuando hagas las permutaciones tienes que hacerlas sobre los valores existentes en imagen2.
Un saludo