Descifrar las imágenes sin probar todas las permutaciones

Question

Trato de escribir un algoritmo que descodifica las imágenes que fueron antes revueltos por la mezcla de pequeños bloques:

Mi idea es que en la parte inferior de la imagen hay más "fuerte" de las esquinas en comparación a la imagen de arriba. Por lo tanto trato de minimizar el funcional:

energy(image)
{
score = 0;
for(pixels inside the image)
score = score + abs(pixel sum of sourrounding 4 pixels - 4 value of internal pixel)
}

La energía debe por lo tanto ser alta si hay muchos bordes duros y bajos de la imagen original. En una prueba me encontré con que la imagen original tiene la partitura $845.812$, mientras que el revueltos uno tiene la partitura $1.085.521$ por lo que el enfoque podría ser vale la pena intentarlo.

Mi pregunta es si hay un método eficiente para minimizar la función de la energía ahora sin probar todas las $n!$ permutaciones (demasiados). O un enfoque diferente no he venido para arriba con.

Answer 1

Yo no creo que haya una solución analítica para esto. He aquí cómo iba a acercarse a ella. En lugar de calcular la energía total para toda la imagen, para cada par de bloques y cada una de las cuatro direcciones en las que los bloques se podría formar una interfaz, calcular el aporte de energía resultante de la interfaz. Que le da una energía definida directamente en las permutaciones de los bloques, y usted no tiene que lidiar con la imagen. Puedes aplicar el algoritmo de optimización combinatoria para esto, por ejemplo, el recocido simulado. El tiempo necesario para encontrar el óptimo puede depender fuertemente de los tipos de movimientos que permiten, desde que usted conseguirá a menudo partes de la imagen montada correctamente en el lugar equivocado y puede reducir significativamente las barreras de energía entre locales optima mediante el uso de movimientos que cambio todo de los grupos de bloques juntos, en lugar de los bloques individuales.