cut&paste w/arbitrary warp

[Kenneth Sloan-2]

I’m about to write a Java plug-in to do cut&paste with arbitrary warp.  As usual, I’d like to make sure I’m not re-inventing the wheel.  Here are a few of the operations I have in mind:

[in most cases, there will be two images open - think of them as source and destination, although I may play a bit fast and loose with this]

For all operations, begin by outlining a (closed, simple) polygon) - P

a) specify 1 point in the source and 1 point in the destination.  MOVE the pixels in P using simple TRANSLATION

b) specify 2 points (u,v) in the source and 2 points (s,t) in the destination, MOVE the pixels in P such that u maps to s and the direction from u->v maps to the direction s->t

c) specify2 points (u,v) in the source and 2 points (s,t) in the destination.  MOVE the pixels in P such that u maps to s and v maps to t

Those are pretty simple - and those may be all I need for the immediate application.  Now it becomes more complicated.

d) specify segment of P (begin at vertex v1 and end at vertex vn).    Specify points w1 and wn in the destination.  Move and scale the polyline v1..vn so that v1->w1 and v2->w2.  Next, allow the user to perturb the vertices of the new polyline (within reason) to produce w1’..wn'.  Finally, MOVE the pixels in P s.t. the entire polyline v1..vn maps to the perturbed poly line w1’..wn’ AND (the tricky part) the rest of the polygon warps “appropriately”.  

e) special case of the above - map the entire bouncary polygon P to a copied and perturbed boundary w’, warping the interior as needed.

I think I’ve simplified some things by making the number of vertices in v and w (and w’) match exactly.  Freeform specification of v and w is probably not that much harder to implement - but the end users will probably be thinking in terms of specific landmark POINTS rather than boundaries, per se.

Before someone asks, in all cases “MOVE the pixels in P” means “iterate over the pixels in the destination and fetch pixel values from the source.

So…my main question is: does this functionality exist anywhere?

And if so, where can I steal it.

Please note - I know how to do the warping and will (with some work) figure out how to implement the interaction.  So, I don’t nee advice on appropriate methods (but…feel free to offer it anyway!).
I’m really just interested in whether or not there is an existing tool that does what I want.

Once past that - I welcome ideas on improving my specifications (either simplifying, or generalizing).

The specific applications is to repair artifacts generated in the creation of thin sections of human retina.  The most serious problem with these is that some of the layers of the retina are fragile, and the tissue separates, with one part pulling away (with some warping and bending).  The goal is to put it back together again, if only crudely.  The matching doesn’t have to be terribly precise - the point is to create a correspondence between features found along the length of one part with features found along the length of the other (separated) part.  Decisions about what warping is “reasonable” may well turn out to depend on the types of warping actually present.  Mostly, this is a fairly simple separation and rotation.  I anticipate some issues here near the pivot point, where the tissue remains attached.  This may, or may not, be important.

And finally…I’ve gone to a generalized “cut and paste” because there may be several such “separation and movement” artifacts in the same section.  I originally thought I could simply throw a mesh over everything and warp things back together - but, I’ve seen enough examples that I’m now going to count on a trained observer starting from one source image and doing successive “cut/paste/warp”  operations to put things together manually.

We could *almost” do this by grabbing polygons and moving them using only translation and rotation - but again, examples demonstrate that some amount of local generalized warping will be necessary.

—
Kenneth Sloan
[hidden email]




--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[Wilhelm Burger]

Hi Kenneth,

when you say "perturbed polyline" -- do you mean that the n vertices are cyclically shifted or could they be fully permuted?

Regarding the geometric part of the mapping, you need a transformation preserving straight lines if you want to transform one polygon shape to another (i.e., spline models are out of question). Selecting 2 corresponding point pairs will give you a unique rigid transformation (i.e., rotation and uniform scaling only), 3 point pairs define an affine transformation and 4 point pairs give a projective transformation (linear in homogeneous coordinates). There is no straight line-preserving 2D transformation that could map more than n=4 point pairs. The common approach for n>4 is to tesselate the image into triangles or quads, and transforming these individually with the resulting affine or projective transformations, respectively. In this way it should be straightforward to map between arbitrary polygons by triangulation.

Hope I understood the question right ...

--Wilhelm

[Kenneth Sloan-2]

By "perturb", I mean small, local changes in the location of a
(destination) vertex.

One special case is an example that at least one FIJI plugin already
handles - suppose one "edge" of a region is curved in the source, but
straight in the destination. In my version, there would be a curving, open
polyline in the source. The destination vertices would first be crudely
positioned, and then each vertex individually adjusted.


On Mon, Jan 30, 2017 at 06:27 Burger Wilhelm <[hidden email]>
wrote:

> Hi Keneth,
>
> when you say "perturbed polyline" -- do you mean that the n vertices are
> cyclically shifted or could they be fully permuted?
>
> Regarding the geometric part of the mapping, you need a transformation
> preserving straight lines if you want to transform one polygon shape to
> another (i.e., spline models are out of question). Selecting 2
> corresponding point pairs will give you a unique rigid transformation
> (i.e., rotation and uniform scaling only), 3 point pairs define an affine
> transformation and 4 point pairs give a projective transformation (linear
> in homogeneous coordinates). There is no straight line-preserving 2D
> transformation that could map more than n=4 point pairs. The common
> approach for n>4 is to tesselate the image into triangles or quads, and
> transforming these individually with the resulting affine or projective
> transformations, respectively. In this way it should be straightforward to
> map between arbitrary polygons by triangulation.
>
> Hope I understood the question ...
>
> --Wilhelm
>
>
> ________________________________________
> From: ImageJ Interest Group <[hidden email]> on behalf of Kenneth
> Sloan <[hidden email]>
> Sent: Sunday, January 29, 2017 21:53
> To: [hidden email]
> Subject: cut&paste w/arbitrary warp
>
> I’m about to write a Java plug-in to do cut&paste with arbitrary warp.  As
> usual, I’d like to make sure I’m not re-inventing the wheel.  Here are a
> few of the operations I have in mind:
>
> [in most cases, there will be two images open - think of them as source
> and destination, although I may play a bit fast and loose with this]
>
> For all operations, begin by outlining a (closed, simple) polygon) - P
>
> a) specify 1 point in the source and 1 point in the destination.  MOVE the
> pixels in P using simple TRANSLATION
>
> b) specify 2 points (u,v) in the source and 2 points (s,t) in the
> destination, MOVE the pixels in P such that u maps to s and the direction
> from u->v maps to the direction s->t
>
> c) specify2 points (u,v) in the source and 2 points (s,t) in the
> destination.  MOVE the pixels in P such that u maps to s and v maps to t
>
> Those are pretty simple - and those may be all I need for the immediate
> application.  Now it becomes more complicated.
>
> d) specify segment of P (begin at vertex v1 and end at vertex vn).
> Specify points w1 and wn in the destination.  Move and scale the polyline
> v1..vn so that v1->w1 and v2->w2.  Next, allow the user to perturb the
> vertices of the new polyline (within reason) to produce w1’..wn'.  Finally,
> MOVE the pixels in P s.t. the entire polyline v1..vn maps to the perturbed
> poly line w1’..wn’ AND (the tricky part) the rest of the polygon warps
> “appropriately”.
>
> e) special case of the above - map the entire bouncary polygon P to a
> copied and perturbed boundary w’, warping the interior as needed.
>
> I think I’ve simplified some things by making the number of vertices in v
> and w (and w’) match exactly.  Freeform specification of v and w is
> probably not that much harder to implement - but the end users will
> probably be thinking in terms of specific landmark POINTS rather than
> boundaries, per se.
>
> Before someone asks, in all cases “MOVE the pixels in P” means “iterate
> over the pixels in the destination and fetch pixel values from the source.
>
> So…my main question is: does this functionality exist anywhere?
>
> And if so, where can I steal it.
>
> Please note - I know how to do the warping and will (with some work)
> figure out how to implement the interaction.  So, I don’t nee advice on
> appropriate methods (but…feel free to offer it anyway!).
> I’m really just interested in whether or not there is an existing tool
> that does what I want.
>
> Once past that - I welcome ideas on improving my specifications (either
> simplifying, or generalizing).
>
> The specific applications is to repair artifacts generated in the creation
> of thin sections of human retina.  The most serious problem with these is
> that some of the layers of the retina are fragile, and the tissue
> separates, with one part pulling away (with some warping and bending).  The
> goal is to put it back together again, if only crudely.  The matching
> doesn’t have to be terribly precise - the point is to create a
> correspondence between features found along the length of one part with
> features found along the length of the other (separated) part.  Decisions
> about what warping is “reasonable” may well turn out to depend on the types
> of warping actually present.  Mostly, this is a fairly simple separation
> and rotation.  I anticipate some issues here near the pivot point, where
> the tissue remains attached.  This may, or may not, be important.
>
> And finally…I’ve gone to a generalized “cut and paste” because there may
> be several such “separation and movement” artifacts in the same section.  I
> originally thought I could simply throw a mesh over everything and warp
> things back together - but, I’ve seen enough examples that I’m now going to
> count on a trained observer starting from one source image and doing
> successive “cut/paste/warp”  operations to put things together manually.
>
> We could *almost” do this by grabbing polygons and moving them using only
> translation and rotation - but again, examples demonstrate that some amount
> of local generalized warping will be necessary.
>
> —
> Kenneth Sloan
> [hidden email]
>
>
>
>
> --
> ImageJ mailing list: http://imagej.nih.gov/ij/list.html
>

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html