manually cutting a picture

[Amit Khemka]

On 11/7/07, Cameron Walsh <cameron.walsh at gmail.com> wrote:
> Amit Khemka wrote:
>
> > Cut image by "m X m" grid (bigger the m, the more varied shapes you
> > would be able to generate), this will give you m*m square pieces. With
> > each piece store a vector which represents the polygon (say by storing
> > co-ordinates of the corners).
> > Now visualize this set of pieces as a graph with an edge between
> > adjacent pieces. Now depending on the final number of pieces that you
> > want to generate (N), you traverse the graph and for each node:
> >
> > 1. "Merge" a node with a randomly selected neighbor
> >
> > Repeat step 1 until you have N pieces left
> >
> Doesn't that have the fairly likely possibility of ending up with 1 very
> large piece and n-1 very small pieces?  If you iterate over the graph
> merging with a neighbour at random, then each node has a 50% chance of
> being merged with a node that has already been merged.
>
> *-*-* *-*
> |   | |
> * *-*-* *
>
> * * * * * etc. could be the result of the first 8 steps.  Already every
> node touched is part of the same group.  Or have I misunderstood your
> algorithm?

Yes, It potentially can result into that. That is the reason I
suggested to calculate (m*m/N) and while merging nodes keep track of
the "size" (number of nodes are merged in a node), so that while
growing/merging the node does not grow 'much large' than (m*m/M)

>
> A random region growing approach might work, with seeds scattered evenly
> throughout the image.  That would be prone to orphaning squares inside
> larger objects, but that may be what you want.  It would not be easy to
> program.
>
> What I would do is break the graph in to m*m squares, then for each
> edge, randomly select a means of joining them - blob sticking out of
> piece A, or hole for blob in piece A; move hole/blob along the edge by a
> random amount, move edge in or out to get different sized pieces.  For
> each square this was applied to, it would apply the reverse sizing to
> the square touching on that edge.
>
> I'd restrict in/out movement of edges and movement of blob/hole along
> the edge to a specific range, to avoid problems where the blob of one
> square is stuck on the furthest corner, but the piece touching that
> corner has had its edge moved in too far so the blob would overlap two
> squares.

Interesting idea, though the implementation may become a bit complex !


To OP :
1. Have you checked out research papers on Digital Image Processing
and Graphics ?  I would guess that there should exist some good
solutions. I hadn't had much time but a quick search showed quite a
few "free softwares" to create Jigsaw puzzles and Algorithms to solve
one.

2. Can you please post anything relevant to this topic on this thread
only instead of doing a new post. Helps to track the postings easily.

Cheeers,

-- 
--
Amit Khemka