How many combinations of k neighboring pixels are there in an image?

I suck at math, so I can't figure this out: how many combinatio开发者_JAVA百科ns of k neighboring pixels are there in an image? Combinations of k pixels out of n * n total pixels in the image, but with the restriction that they must be neighbors, for each k from 2 to n * n. I need the sum for all values of k for a program that must take into account that many elements in a set that it's reasoning about.

Neighbors are 4-connected and do not wrap-around.

Once you get the number of distinct shapes for a blob of pixels of size k (here's a reference) then it comes down to two things:

• How many ways on your image can you place this blob?
• How many of these are the same so that you don't double-count (because of symmetries)?

Getting an exact answer is a huge computational job (you're looking at more than 10^30 distinct shapes for k=56 -- imagine if k = 10,000) but you may be able to get good enough for what you need by fitting for the first 50 values of k.

(Note: the reference in the wikipedia article takes care of duplicates with their definition of A_k.)

It seems that you are working on a problem that can be mapped to Markovian Walks.

If I understand your question, you are trying to count paths of length k like this:

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

in a structure that is similar to a chess board, and you want to connect only vertical and horizontal neighbours.

I think that you want the paths to be self avoiding, meaning that a pixel should not be traversed twice in a walk (meaning no loops). This condition lead to a classical problem called SAWs (Self Avoiding Walks).

Well, now the bad news: The problem is open! No one solved it yet.

You can find a nice intro to the problem here, starting at page 54 (or page 16, the counting is confusing because the page numbers are repeating in the doc). But the whole paper is very interesting and easy to read. It manages to explain the mathematical background, the historical anecdotes and the scientific importance of markovian chains in a few slides.

Hope this helps ... to avoid the problem.

If you were planning to iterate over all possible polyominos, I'm afraid you'll be waiting a long time. From the wikipedia site about polyominos, it's going to be at least O(4.0626^n) and probably closer to O(8^n). By the time n=14, the count will be over 5 billion and too big to fit into an int. By time n=30, the count will be more than 17 quintillion and you won't be able to fit it into a long. If all the world governments pooled together their resources to iterate through all polyominos in a 32 x 32 icon, they would not be able to do it before the sun goes supernova.

Now that doesn't mean what you want to do is intractable. It is likely almost all the work you do on one polyominal was done in part on others. It may be a fun task make an exponential speedup using dynamic programming. What is it you're trying to accomplish?