¿Cuántas combinaciones de k vecinos píxeles están allí en una imagen?

Question

Estoy chupando en las matemáticas, así que no puedo entender esto: ¿Cuántas combinaciones de K vecinos píxeles están allí en una imagen?Combinaciones de píxeles K de n * n Píxeles totales en la imagen, pero con la restricción que deben ser vecinos, por cada K de 2 a n * n.Necesito la suma para todos los valores de K para un programa que debe tener en cuenta que muchos elementos en un conjunto sobre el que está razonando.

Los vecinos están 4-conectados y no envuelven alrededor.

Answer 1

Una vez que obtiene la cantidad de formas distintas para un blob de píxeles de tamaño K ( Aquí hay una referencia )) Luego se reduce a dos cosas:

• ¿Cuántas maneras en tu imagen puedes colocar este blob?
• ¿Cuántos de estos son los mismos, para que no tenga doble cuenta (debido a las simetrías)?

obtener una respuesta exacta es un gran trabajo computacional (está buscando más de 10 ^ 30 formas distintas para K= 56 - Imagine si K= 10,000) pero es posible que pueda obtener lo suficientemente bueno para lo que necesitaajustando los primeros 50 valores de k.

(Nota: la referencia en el artículo de Wikipedia se encarga de duplicarse con su definición de A_K.)

Answer 2

Parece que está trabajando en un problema que se puede asignar a los caminatas de Markovian.

Si entiendo su pregunta, está tratando de contar las rutas de longitud k como esta:

Start          (end)-> any pixel after visiting k neighbours
*     - - - - -*
|     |
|     |
- - - -

En una estructura similar a una junta de ajedrez, y desea conectar solo vecinos verticales y horizontales.

Creo que desea que los caminos sean evitando, lo que significa que un píxel no debe atravesarse dos veces a un paseo (que significa ningún buceo). Esta condición conduce a un problema clásico llamado sierras (auto evitando caminatas).

Bueno, ahora las malas noticias: ¡El problema está abierto! Nadie lo resolvió todavía.

Puede encontrar una bonita introducción al problema aquí , comenzando en la página 54 (o en la página 16, el conteo es confuso porque los números de la página se repiten en el DOC). Pero todo el papel es muy interesante y fácil de leer. Se las arregla para explicar el fondo matemático, las anécdotas históricas y la importancia científica de las cadenas markovianas en unas pocas diapositivas.

Espero que esto ayude a ... para evitar el problema.

Answer 3

Si planeaba iterar todo lo posible poliominos , me temo queEstará esperando mucho tiempo.Desde el sitio de Wikipedia sobre poliominos, va a ser al menos O (4.0626 ^ N) y probablemente más cerca de O (8 ^ N).Para cuando n= 14, el recuento será de más de 5 mil millones y demasiado grande para caber en un int.Por el tiempo n= 30, el recuento será más de 17 quintillion y no podrá ajustarse a un largo.Si todos los gobiernos del mundo agruparon sus recursos para iterar a través de todos los poliominos en un ícono de 32 x 32, no podrían hacerlo antes de que el sol se vuelva supernova.

Ahora eso no significa lo que quiere hacer es intratable.Es probable que sea casi todo el trabajo que haga en un poliominal se hizo en parte en otros.Puede ser una tarea divertida hacer una velocidad exponencial utilizando una programación dinámica.¿Qué es lo que está tratando de lograr?