Shepards distortion

[snibgo]

IM has two methods of creating a Shepards distortion. They produce similar but different results, and I believe one is wrong. (Perhaps the bug is in my understanding.) The methods are:

(1) With "-distort Shepards", eg:

Code: Select all

"%IMG%convert" rose: -depth 16 rose.tiff
"%IMG%identify" rose.tiff

rem Check that it really is 16 bits.

rem Method (1).

"%IMG%convert" rose16.tiff ^
  -distort Shepards "10,10 20,10  60,10 60,5" ^
  b_d_shep.tiff

(2) With "-sparse-color Shepards" to create a displacement file, followed by a "composite -displace". Eg:

Code: Select all

rem Method (2).

"%IMG%convert" rose16.tiff ^
  -sparse-color Shepards "10 10 #7FF680000000  60 10 #800080050000" ^
  ac.tiff

"%IMG%composite" ac.tiff rose16.tiff -displace 32768x32768 b_shep.tiff

I have written software that creates a displacement file, emulating IM's "-sparse-color Shepards", "Inverse" and "Voronoi". It gives identical results to the IM "-sparse-color" methods. Thus, I believe IM's method (1) is incorrect.

The guts of my software is:

Code: Select all

static void WrPpm (void)
{
  FILE * f;

  if (strcmp(PpmFile, "-") == 0) f = stdout;
  else f = fopen (PpmFile, "wt");

  if (!f) FatalError ("Can't open %s", PpmFile);

  fprintf (f, "P3\n");
  fprintf (f, "%i %i\n", PpmWidth, PpmHeight);
  fprintf (f, "%i\n", 65535);

  int const mid_val = 32768;

  int x, y, i;
  float mult;

  float max_dist = (PpmWidth + PpmHeight) * 2;
  float ClosestDist;

  for (y = 0; y < PpmHeight; y++) {
    for (x = 0; x < PpmWidth; x++) {

      float shiftX = 0.0, shiftY = 0.0;
      float sigMult = 0.0;

      ClosestDist = max_dist;
      int ndxClosest;

      for (i = 0; i < nValues; i++) {
        ValueT * pv = &Values[i];
        if (pv->include) {
          float dx = (pv->x0 - x);
          float dy = (pv->y0 - y);
          float distSq = dx * dx + dy * dy;

          if (distSq==0) distSq = 1;

          if (DoVoronoi) {
            float dist = sqrt(distSq);
            if (ClosestDist > dist) {
              ClosestDist = dist;
              ndxClosest = i;
            }
          } else {
            // For speed, treat DistPower 1 and 2 as special cases.
            if      (DistPower == 1) mult = 1.0/sqrt(distSq);
            else if (DistPower == 2) mult = 1.0/distSq;
            else                     mult = 1.0 / pow (distSq, DistPower/2);

            shiftX += pv->dx * mult;
            shiftY += pv->dy * mult;
            sigMult += mult;
          }
        }
      }

      int dx, dy;

      if (DoVoronoi) {
        dx = Values[ndxClosest].dx + mid_val;
        dy = Values[ndxClosest].dy + mid_val;
      } else {
        dx = (shiftX / sigMult + 0.5) + mid_val;
        dy = (shiftY / sigMult + 0.5) + mid_val;
      }

      fprintf (f, "%i %i 0\n", dx, dy);
    }
  }

  if (strcmp(PpmFile, "-") != 0) fclose (f);

  if (gProcesses) printf ("Created %s\n", PpmFile);
}

In my software, the variable DistPower is the power the distance to each control point is to be raised. A value of 1 is equivalent to IM's "-sparse-color Inverse", while 2 is "-sparse-color Shepards". For my experiments, which is about matching photographs, larger powers give better results. I would like this feature to be added to ImageMagick, something like "-define ShepardsDistancePower:3.5". Ideally I'd like both "-distort Shepards" and "-sparse-color Shepards" to respect this, but only after the bug (if it is a bug) is fixed.

EDIT: should have said: IM 6.7.9 on Windows 7.

Perhaps I should also say that my simple examples above have only 2 control points, but my real-world images have 35 or more.

[anthony]

You need to remember that teh displacement field is applied to the desitination image not the source image.

That is it is used to map (displace) the destination coordinates to the source coordinates, so it can look up the source color (displaced) for the current destination pixel.

That is the way BOTH displacement maps and distortion work! For reasons why you do it in a seemingly backward way, see
General Distortion Techniques
http://www.imagemagick.org/Usage/distorts/#summary

As such to make a -distort shepards and -sparse-color shepards match, the -sparse-color map must use control points in the destination image with the appropriate displacement vector mapping to the source image coordinate.

That is your sparse color operation needs to be something like...

-sparse-color Shepards "20 10 ..color.. 60 5 ..color.."

with the color value negated (made negative with the 50% grayscale bias) to reverse the displacement vector direction
(destination to source)

Also note that to do a 2-dimentional displacement you need to generate two displacement maps, One for X and one for Y. In this situation you can provide -composite with three images, source, X displacement, Y displacement, OR a single displacement map with X in red channel and Y in green channel. (The CLI interface does this merger internally when given three images for displace or distort).

Have a look at Fred Wienhaus's script, which used -sparse-color (and even more directory using -fx) to generate the displacement maps. This was the original 'proof of concept' for the distort shepards. but only uses 5 points (4 fixed corners, and a single displaced control point)

The main difference is the -distort does all the calcualtions on the fly for multiple control points, where generating a displacement map basically pre-calculates all the displacements. also not there is a -compose distort, which uses an absolute coodrinate lookup map, rather than a displacement map. Again destination to source coordinate mapping.

For more information see "Mapping Effects" section
http://www.imagemagick.org/Usage/mapping/

Which also shows equivalent 'FX' operations.

[snibgo]

Ah, yes, the bug was in my understanding. Thanks very much. When I modify method (2) to ...

Code: Select all

"%IMG%convert" rose16.tiff ^
  -sparse-color Shepards "20 10 #7FF680000000  60 5 #800080050000" ^
  ac.tiff

"%IMG%composite" ac.tiff rose16.tiff -displace 32768x32768 b_shep.tiff

... the difference between the two methods is less than one pixel.

I'd still like the "power" option implemented, if possible.

[fmw42]

Perhaps a define could be added with the power so that new functions do not need to be created. However, I will leave that decision to Anthony, whenever he gets the time to look at it. I know he is very busy with the IM 7 development.

[anthony]

I can add something like a define setting.

Though then distorts would mean the addition of a pow() funtion. at the moment I use weight = x*x+y*y
That is weight = r^2 (Later weight is changed to be 1/weight after a zero distance check)

Using a variable power would make it... weight = pow(x*x+y*y,power/2)
the division by 2 is to handle sqrt() of the radius distance calculation, but that can be pre-calculated.

Do you want to slow down the calculations that much?

[snibgo]

You could do as I do in the code above, which is to special-case power==1 and power==2. I assume a couple of if-tests are cheap compared to the cost of calculating the squared distance of 4 or more points.

But I confess I'm not a brilliant programmer.

[fmw42]

It could be faster if you are willing to limit it to integer powers.

[anthony]

It could be faster if you are willing to limit it to integer powers.

Only by using 'special cases' as suggested. I do not believe there is a generally available 'interger power' type math function, only purely floating point.

I'll work out something.

Note that the two actually share a lot of code (same library module): Distort maps destination coordinates to source image x,y lookup coordinates. While sparse-color maps destination coordinates to a variable number color channel values.

In fact the even share a common set of methods, including Shepard's (also known as a Inverse Weighted Average).

[fmw42]

Isn't x^2 faster than pow(x,2)?

For even powers, you can do r^2=(x*x+y*y), then for r^4 = r^2*r^2.

For odd powers, I guess one would have to do r=sqrt(r^2) and then for r^3 = r *r^2.

This of course requires conditionals for even and odd powers and the sqrt.

[snibgo]

I wouldn't want to limit to integer powers.

While we're on the topic, another useful displacement is a more generic barycentric: triangulate the set of control points, then for each destination point find the containing triangle. As far as I can see, the current barycentric method only uses 3 points, thus one triangle. But I could be wrong; I haven't spent any time looking at it.

[anthony]

You are correct, and I am wanting to do this.

However it requires a paradigm shift in how distortions (and sparse colors) are currently handled as different areas require a different set of distortion (and area defining) parameters. That is each destination point it needs to determine which 'area' it is in in (if not the same as the last area) so as to select the right distortion to use.

Also when using a 'mesh' of points like this the coordinates is not just 'points' but a triangular mesh information, as the mesh to be applied may not be a straight forward Delaunay Triangulation, especially if you are using it for morphing between two sets of coordinates (which may result in different Delaunay Triangulation Meshes). That makes the input and pre-processing of the numbers much much more complex (another paradigm shift)

By comparison shepards which is purely 'points' and not 'areas' is dead simple, as it is all still just one distortion, rather than a whole set of distortions.

That brings up one final point. While a image map can do interpolated 'point' sampling for each pixel, and shepards does the same, simply because of its complexity, Affine distortions (and Bilinear distortion (for quadrilateral gridding) use a higher quality Area resampling method. That is for a given triangular mesh, a distort version will use a Area Filter Sampling, while the equivalent image mapped version would be Interpolated 'point' sampling.

NOTE; IM is open source. you are welcome to look at and try to implement it.

As a help, you can read distort and sparse color arguments from a file by using an argument of '@data_file.txt'. But such a file input currently does not understand 'lines' or 'comments' just a list of floating point numbers (a thrid to-do problem)

[fmw42]

I wouldn't want to limit to integer powers.

While we're on the topic, another useful displacement is a more generic barycentric: triangulate the set of control points, then for each destination point find the containing triangle. As far as I can see, the current barycentric method only uses 3 points, thus one triangle. But I could be wrong; I haven't spent any time looking at it.

You might want to see my unix shell script, meshwarp.

[anthony]

Okay I just committed a artifact (define) for Shepards method

Code: Select all

-define shepards-power=2.0

A value of 2.0 is the default. Using a value 1.0 will get the equivalent Inverse sparse-color method (though 'Inverse Method ignores this define).

Using a low number (like 0.5) generates 'spikes of color' in sparse-color, and very tight point moves in distort
Using a high number (like 5) generates more 'voronoi' type color areas, and 'rips and duplications' of images around control points (in a vornoni tile pattern) of the original image.

Actually try this, which generates voronoi-like displacements using distort.

Code: Select all

   convert koala.gif -virtual-pixel Black -define shepards-power=25 \
           -distort Shepards '28,24 35,35    28,24 20,10    28,24 50,10 
                             28,24 20,60   28,24 50,60
                             28,24 10,35   28,24 60,35'   show:

28,24 is the koala's nose, and it is distorted to 7 locations in a hexagon-like pattern. The higher the power, the sharper (more aliased) the edges will become.

[snibgo]

Cool. Many thanks.

[fmw42]

-define shepards-power=2.0

Is not the generally used syntax with a colon?

-define shepards:power=2.0

That seems to be the syntax used in most other defines.