Combien de combinaisons de k pixels voisins sont là dans une image?

Question

Je suce en mathématiques, donc je ne peux pas comprendre cela: combien de combinaisons de k pixels voisins sont là dans une image?Combinaisons de k pixels de N * N pixels totaux de l'image, mais avec la restriction qu'ils doivent être voisins, pour chaque K de 2 à N * n.J'ai besoin de la somme de toutes les valeurs de K pour un programme qui doit prendre en compte le fait de nombreux éléments dans un ensemble de raisonnement.

Les voisins sont connectés à 4 et ne s'enveloppent pas.

Answer 1

Une fois que vous avez obtenu le nombre de formes distinctes pour un blob de pixels de taille K ( Voici une référence ) alors cela revient à deux choses:

• Combien de façons de votre image pouvez-vous placer ce blob?
• Combien d'entre eux sont les mêmes afin que vous ne comptez pas (à cause de symétries)?

Obtenir une réponse exacte est un énorme travail de calcul (vous cherchez plus de 10 ^ 30 formes distinctes pour K= 56 - Imaginez si k= 10 000) Mais vous pourrez peut-être obtenir suffisamment pour ce dont vous avez besoinEn adaptant les 50 premières valeurs de k.

(Remarque: la référence dans l'article Wikipedia s'occupe des doublons avec leur définition d'A_K.)

Answer 2

Il semble que vous travailliez sur un problème pouvant être mappé aux promenades markoviennes.

Si je comprends votre question, vous essayez de compter des chemins de longueur K comme ceci:

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

Dans une structure similaire à une carte d'échecs, et que vous souhaitez connecter uniquement des voisins verticaux et horizontaux.

Je pense que vous voulez que les chemins soient auto-évitant, ce qui signifie qu'un pixel ne doit pas être traversé deux fois dans une promenade (ce qui ne signifie pas de boucles). Cette condition conduit à un problème classique appelé Scies (auto-évitant les promenades).

Eh bien, maintenant la mauvaise nouvelle: le problème est ouvert! Personne n'a encore résolu.

Vous pouvez trouver une belle intro au problème ici , à partir de la page 54 (ou à la page 16, le comptage est confus, car les numéros de page se répètent dans la doc). Mais tout le papier est très intéressant et facile à lire. Il parvient à expliquer le fond mathématique, les anecdotes historiques et l'importance scientifique des chaînes markoviennes dans quelques diapositives.

J'espère que cela vous aidera à éviter le problème.

Answer 3

Si vous prévoyez d'itérer sur tout le possible Polyominos , je crains que vous "ll attendra depuis longtemps.Du site Wikipedia sur les polyominos, il va être au moins (4,0626 ^ N) et probablement plus proche de O (8 ^ n).Au moment où N= 14, le nombre sera de plus de 5 milliards de dollars et trop gros pour s'intégrer à un Int.Par le temps n= 30, le compte sera plus de 17 quintilles et vous ne pourrez pas l'adapter dans une longue.Si tous les gouvernements mondiaux ont mis en commun ensemble leurs ressources pour itérer tous les polyominos dans une icône 32 x 32, ils ne seraient pas en mesure de le faire avant que le soleil ne devienne supernova.

Maintenant que cela ne signifie pas ce que vous voulez faire est intraitable.Il est probable que presque tout le travail que vous faites sur un polyominal a été fait en partie sur d'autres.Il peut s'agir d'une tâche amusante apporter une vitesse exponentielle à l'aide de la programmation dynamique.Qu'est-ce que vous essayez d'accomplir?