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

Question

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

Соседи 4-подключены и не обертываются.

Answer 1

После того, как вы получите количество различных форм для сгустка пикселей размера к (here's a reference), то она сводится к двум вещам:

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

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

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

Answer 2

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

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

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

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

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

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

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

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

Answer 3

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

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