🚀 go-pugleaf

I'd like to try an exhaustive search method for segmenting small
images, and I need to know the number of possible candidate
segmentations and how to generate them systematically.

Let's say I have a rectangular image of rectangular pixels with "n"
rows and "m" columns that I want to split into "r" distinct
4-connected or 8-connected regions.  There will be lots of different
possible region maps.  In each region map, each pixel will be labeled
with an integer 1,2,3, ... r (or, for you computer scientists, 0,1,2
... r-1).  I'll evaluate each region map somehow and pick the best
one.

The number of possible nxm IMAGES where each pixel has a value 1,2,3
... r is r^(mn).  (If m=n=r=10, then this is a googol.)  So r^(mn) is
a generous upper bound.


What I really want to know is:

   o How many possible region maps are there for a given (n,m,r) for
     the 4-connected and 8-connected cases?

   o How do I generate all the possibilities systematically?

What I can reasonably expect in response to this query is:

   o What field of mathematics might have the answer (graph theory)?

   o Where's an article or chapter that addresses the questions?

I'm hoping that if n, m, and r are small, then the complexity won't be
too large.


						John Krumm
						The Robotics Institute
						Carnegie Mellon University