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

Question

I suck at math, so I can't figure this out: how many combinations 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.

Answer 1

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.)