Posible EWA speed improvement

Discuss digital image processing techniques and algorithms. We encourage its application to ImageMagick but you can discuss any software solutions here.
Post Reply
NicolasRobidoux
Posts: 1944
Joined: 2010-08-28T11:16:00-07:00
Authentication code: 8675308
Location: Montreal, Canada

Posible EWA speed improvement

Post by NicolasRobidoux » 2011-07-01T05:07:47-07:00

It would seem to me that using the intersection of the bounding box (with all sides parallel to the axes) and the bounding parallelogram (with horizontal top and bottom, but not necessarily vertical sides) to select which pixels to select would be a cheap way of speeding up the computation when the ellipse is slanted. (Probably not a huge improvement, and certainly no difference when resizing, but easy and cheap, so why not.)

(Unfortunately, I have no time for this now.)

User avatar
anthony
Posts: 8883
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Re: Posible EWA speed improvement

Post by anthony » 2011-07-01T22:37:06-07:00

First I moved this discussion to Digital Image Processing as it is very general and not specific to IM and its implementation.

Actually I looked at that bounds solution, and was in fact implementing that bounds when I realised I could simplify it a little, leading to the parallelogram bounds.

As a FYI here is my parallelogram bounds diagram...
Image
Essentially it equivalent to a square bounds of a circle that is sheared to form the ellipse, which is why it has a fixed hit/miss ratio, compared to the previous method of using orthogonal X,Y bounds.

The question is how affordable is the calculation of the bounding box.

WIth the parallelogram, I the extraction of a row of pixels is quite straight forward. floating point start point, which is offset by a fixed amount form one row to the next row. and it has a fixed floating point length, the result mapped to integers for the access to the data.

Relative straight forward extention of the incremental code used for the quadratic distance formula (no sqrt is performed for that).

For a bounding box aligned with the major and minor axis, you actually have to work out the union of two parallelograms. So instead of on set of values (start,increment,length), you need the union of two sets, one for the major axis bounds and one for the minor axis.

Of course you can clip the Y axis directly by the orthogonal bounds of the ellipse.

So to combine that with the parallelogram, you get a union of three parallelogram bounds when implementing.

You could also add the X bounds to that union too, seeing you are doing unions.

So for each row, you want the maximum of 4 possible start points, and minimum of 4 possible end points.
With unions you no longer have a fixed length!

Now I could be wrong, but its seems to me, that it is a lot of work, for very little reward. Especially when an orthogonally aligned ellipse (simple resize) generally results in the all three bounding boxes aligning anyway!

Now pixel extraction in IM (and other images) can be complex and Virtual pixels become involved. You can't just reference the image data directly in that case.

As such when Virtual-Pixels become involved, reducing the length of each row of pixels may have a major benefit. But it will have no benefit if all the pixels are real, and as such you can reference the image data directly (IM allows both in its pixel cache processing! Or at least did at one point.)

So how beneficial this is open for debate, a test implementation may be useful as a comparison.

However as IM pixel cache for IMv7 is in alpha level development, now is probably not a good time for testing it.
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/

NicolasRobidoux
Posts: 1944
Joined: 2010-08-28T11:16:00-07:00
Authentication code: 8675308
Location: Montreal, Canada

Re: Posible EWA speed improvement

Post by NicolasRobidoux » 2011-07-03T06:07:39-07:00

Anthony:

Thank you for the clear and detailed reply.

I get your point. And I agree that using the intersection of the bounding box and of the parallelogram is likely to be a low bang for the buck "improvement."

NicolasRobidoux
Posts: 1944
Joined: 2010-08-28T11:16:00-07:00
Authentication code: 8675308
Location: Montreal, Canada

Re: Posible EWA speed improvement

Post by NicolasRobidoux » 2011-07-03T06:10:06-07:00

However, the computation of the bounding box is extremely cheap:

http://git.gnome.org/browse/gegl/tree/g ... 6943#n2220

Post Reply