I'm trying to work on an algorithm that will morph one "shape" into another "shape". Both shapes are arbitrary, and may even have smaller, disjointed shapes too.

The basic idea I have so far is as follows: locate the edges of the shape, place points all along those edges, then do the same with the target image, then move the points to their targets.

Here's an illustration:

I just don't know where to start. The image above is a simplification, actual use case has more complex shapes/outlines. My main problem is: How do I handle disjoint shapes? The best I can come up with is to figure out the closest point between the two pieces, and join them together as part of the path. But how would I implement this?

I don't have any code yet, I'm still at the planning phase for this. I guess what I'm asking for is if anyone can link me to any resources that may help, or give any pointers. Searching Google has yielded some interesting morph algorithms, but they all deal with full images and involve breaking the image into pieces to reshape them, which is not what I'm looking for.

Note that this will be used in JavaScript, but could be precomputed in PHP instead if it's easier.

I'm trying to work on an algorithm that will morph one "shape" into another "shape". Both shapes are arbitrary, and may even have smaller, disjointed shapes too.

The basic idea I have so far is as follows: locate the edges of the shape, place points all along those edges, then do the same with the target image, then move the points to their targets.

Here's an illustration:

I just don't know where to start. The image above is a simplification, actual use case has more complex shapes/outlines. My main problem is: How do I handle disjoint shapes? The best I can come up with is to figure out the closest point between the two pieces, and join them together as part of the path. But how would I implement this?

I don't have any code yet, I'm still at the planning phase for this. I guess what I'm asking for is if anyone can link me to any resources that may help, or give any pointers. Searching Google has yielded some interesting morph algorithms, but they all deal with full images and involve breaking the image into pieces to reshape them, which is not what I'm looking for.

Note that this will be used in JavaScript, but could be precomputed in PHP instead if it's easier.

• php
• javascript
• image-manipulation

• Can you have third party PHP extensions installed for this? With OpenCV it seem to be pretty straightforward once you got that. – complex857 Commented Mar 23, 2013 at 19:47
• I would rather not have to get a whole extension just to use one of its functions. Is there any way to port that particular function to PHP or JavaScript? – Niet the Dark Absol Commented Mar 23, 2013 at 20:32
• I guess with a lot of work and emscripten it could be "ported", also there are other partial opencv ports like js-aruco that implements the findContours but this project seems to be abandoned, but it included with the simplecv-js project that has other related goodies (like edge detection in pixastic to substitute missing canny). – complex857 Commented Mar 23, 2013 at 22:04
• What do you mean by How do I handle disjoint shapes? have you implemented standard shapes ? Your expected output is not clear – Baba Commented Mar 24, 2013 at 21:56
• this is definitely a job for vector graphics, rather than bitmaps. it will be a lot easier in the browser in Javascript than in PHP, because the browser has built-in support for vector graphics. A library like Raphael will make it relatively straightforward. – Spudley Commented Mar 29, 2013 at 15:45

4 Answers 4

It's best to break the problem into multiple smaller problems which can be solved independently. That way you also own independent functionalities after solving this problem, which can be added to some global module collection.

First we need to figure out which pixel in the from_shape goes to which pixel in the to_shape.
We can figure that out with the following method:

1. Place to_shape over from_shape.
   

2. For every pixel in from_shape, find its closest to_shape pixel.
   Every pixel in a shape must have a unique id, that id can be for instance, its xy location.

3. Now you can record each unique pixel in from_shape, and which unique pixel it goes to in to_shape.

4. Delete the overlapped shapes and go back to the original ones,
   just now each pixel in from_shape knows its destination in to_shape.

We also need to know which 'siblings' each pixel has.
A sibling is a pixel that lies right next to another pixel.
To find it, go to a given pixel, collect all pixels in radius one from it, all of them which are black.. are the from-pixel's siblings. This information is necessary to keep the shape as a single unit when the pixels travel to their destination. Skipping the siblings would substantially speed up and simplify the morph, but without them the shape might become fragmented during morph. Might wanna begin with a siblingless version, see how that goes.

And finally we implement the morph:

1. There is morph_time_duration.
   For each pixel in from_shape, find the distance to it's destination in to_shape.
   That distance, divided by morph_time_duration, is the speed of the pixel during the morph.
   Also, the angle towards destination is the angle to travel in.
   So now you have speed and angle.

2. So at each frame in the morphing procedure, a given from_pixel now knows which direction to travel in, speed, and it also knows its siblings. So in each frame just draw the pixel in its new location, after having traveled at its speed in its direction. And then draw a line to all of that pixels siblings.

And that will display your morph.

I've found a demonstration (using Raphael.js) of outline morphing and motion tweening in JavaScript, showing how Raphael.js can be used to morph one curve into another curve.

Also, this related question (about shape tweening in JavaScript) may contain some answers that are relevant to this question.

The MorpherJS library may also be suitable for this purpose. Some demonstrations of outline morphing with MorpherJS can be found here.

Doing that wont be very easy, but I can give you a couple of starting points. If you want a plain javascript implementation a great starting point would be: http://raphaeljs.com/animation.html which is doing exactly what you want. So you can check what methods are invoked and browse through the library source for those methods to see the implementation.

If you instead need to morph 2 images in PHP, I would suggest you use some sort of an extension and not do that in plain PHP. Here is an example using ImageMagick to do it: http://www.fmwconcepts.com/imagemagick/shapemorph2/index.php

If you want to know more about the internals of it: http://web.mit.edu/manoli/www/ecimorph/ecimorph.html#algo

Hope one of those helps.

The short answer, if you're trying to roll your own, it's not a straightforward task. There's plenty of math out there on these topics that perform these very transformations (the most common you're find deal with the most common shapes, obviously), but that may or may not be accessible to you and it won't be as easy to figure out how to do the non-standard transformations.

If you're just looking for a logical approach, here's where I'd start (not having done the math in years, and not having studied the inner workings of the graphics libraries linked):

1. Choose a distance, measured in whatever units make sense, pixels perhaps.

2. Identify each continuous edge in each shape. Pick an arbitrary point on one edge for each shape (say, on a plane where (0,0) represents the upper left corner, the edge point on each shape closest to (0,0)), and align your separate shapes on that point. For the purposes of your transformation, that point will remain static and all other points will conform to it.

3. If your shape has two or more distinct edges, order them by perimeter length. Consider the shorter lengths to be subordinate to the longer lengths. Use a similar process as in step 2 to pick an arbitrary point to connect these two edges together.

4. At each of your chosen points, count points around your edges at the interval of the distance you selected in step 1.

5. (left as an exercise for the reader) conform your points on your disparate edges together and into the target shape, aligning, reducing or adding points on the edges as necessary.

Alternatively, you could select an arbitrary number of points instead of an arbitrary distance, and just spread them appropriately along the edges at whatever distance they will fit, and then conform those points together.

Just throwing some ideas out there, I don't honestly know how deep the problem goes.