Сколько комбинаций из k соседних пикселей имеется в изображении?

Question

Я плохо разбираюсь в математике, поэтому не могу в этом разобраться:сколько комбинаций из k соседних пикселей имеется в изображении?Комбинации из k пикселей из n * n общего количества пикселей в изображении, но с тем ограничением, что они должны быть соседними, для каждого k от 2 до n * n.Мне нужна сумма для всех значений k для программы, которая должна учитывать столько элементов в наборе, о которых она рассуждает.

Соседи имеют 4 соединения и не пересекаются.

Answer 1

Как только вы получите количество различных форм для капли пикселей размера k ( Вот ссылка ) Тогда он сводится к двум вещам:

.
• Сколько способов на вашем изображении вы можете разместить этот BLOB?
• Сколько из них одинаково, так что вы не разбираетесь (из-за симметрий)?

Получение точного ответа - это огромная вычислительная работа (вы смотрите на более 10 ^ 30 различных форм для k= 56 - представьте, что k= 10 000), но вы можете получить достаточно хорошо для того, что вам нужноПодходящим для первых 50 значений K.

(Примечание. Ссылка в статье Википедии заботится о дубликатах с их определением A_K.)

Answer 2

Похоже, что вы работаете над проблемой, которая может быть сопоставлена с марковскими ходами.

Если я правильно понял ваш вопрос, вы пытаетесь подсчитать пути длиной k следующим образом:

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

в структуре, похожей на шахматную доску, и вы хотите соединять только вертикальных и горизонтальных соседей.

Я думаю, что вы хотите, чтобы пути были самоустраняющимися, что означает, что пиксель не должен пересекаться дважды за один проход (что означает отсутствие циклов).Это условие приводит к классической проблеме, называемой SAWs (Самоустраняющиеся прогулки).

Ну, а теперь плохие новости:Проблема открыта!Никто еще не разгадал эту загадку.

Вы можете найти хорошее введение в проблему здесь, начиная со страницы 54 (или страницы 16, подсчет сбивает с толку, потому что номера страниц в документе повторяются).Но в целом статья очень интересная, и ее легко читать.В нем на нескольких слайдах объясняются математические основы, исторические анекдоты и научная важность марковских цепей.

Надеюсь , это поможет ...чтобы избежать этой проблемы.

Answer 3

Если вы планировали повторить все возможное Полимино , я боюсь тебябуду ждать долгое время.С сайта Wikipedia о полимино, он будет по крайней мере O (4.0626 ^ n) и, вероятно, ближе к O (8 ^ n).К тому времени n= 14, счет будет более 5 миллиардов и слишком большой, чтобы вписаться в Int.Время n= 30, счет будет более 17 квинтиллиона, и вы не сможете вписать его в долгое время.Если все правительства мира объединяли свои ресурсы, чтобы проиграть всеми полиминос в 32 х 32 значок, они не смогут сделать это до того, как солнце идет сверхновой.

Теперь это не значит, что вы хотите сделать, это неразрешимо.Вероятно, почти вся работа, которую вы делаете на одном полиомииле, были сделаны частично на других.Это может быть забавная задача сделать экспоненциальную скорость с использованием динамического программирования.Что ты пытаешься сделать?