bugGNU Octave - Bugs: bug #61845, [octave forge] (image) speed of...

 
 

bug #61845: [octave forge] (image) speed of imrotate with bicubic interpolation increased

Submitter:  Hartmut <hardy>
Submitted:  Mon 17 Jan 2022 10:17:55 PM UTC
   
 
Category:  Octave Package Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  None Assigned to:  None
Originator Name:  Open/Closed:  * Open
Release:  * other Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Sun 25 Sep 2022 04:20:57 PM UTC, comment #6: 

I had a look into what happens in imremap.m that makes imrotate with bicubic interpolation so slow, now. The profiler shows, that most of the computing time is spent in the function intpolcub in bicubic_conv in inremap.m. Most of the time there is due to the two functions cubic12 and cubic01. And these functions eventually spend most of their time with simple arithmetic calculations: plus, minus, power of n, times, all with matrices of the size of the image.

My conculsion now is: It is not easy to speed this up. There seem to be two ways to do this:

  • Find a clever way to do the same calculation in m-code as now, but using existing functions in core Octave (like corr2) that also calculate correlation and convolution. Those functions will probably do the job faster, because their inner part does the calculation in compiled C code. (But I am not sure if there is a equivalent formulation of the same calculation that uses those core functions.)
  • Rewrite the caculation bit of this code path in a compiled Octave C file.
Hartmut <hardy>
Thu 10 Mar 2022 11:06:30 PM UTC, comment #5: 

I have tested the suggested patch in comment #4 a bit. Results:

  • I also see a (small, less then 10%) speed increase for very big images. Similar to the test code in comment #4, just less of speed increase on my linux laptop.


  • I do like the idea of only casting to "single" for the less accurate integer types like uint8. This mainly saves memory. I would even argue to use this patch and to push it to the repo.


  • But in the original matter, the decreased speed when rotating images with bicubic interpolation, the botton line does unfortunally not change. With this patch applied, I still see a execution time that is roughly doubled when going from image-2.12 to the current bicubic_conv to be included in image-2.14.


@Christof: Do you have a good idea, how to speed up your new convolution method in the bicubic interpolation of imremap.m? Or is this doubleing in execution time the price we have to pay for the now better Matlab compatibility?

Hartmut <hardy>
Thu 27 Jan 2022 02:21:25 PM UTC, comment #4: 

I made a simple patch (as full file and as diff) for imremap, that uses "single" for 8 and 16 bit integer (and also for "single") images. It just does not make sense to convert these to double. I have not checked it very thoroughly, since imremap is lacking tests, but the patch is quite simple. It should improve the performance quite a bit:

I = uint16 (checkerboard (1000) * 65535);
tic;
J = imrotate(I,36,'bicubic','crop',1);
t=toc

  • before: 63.032
  • with patch: 44.580

But also some of the other methods are faster:

I = uint16 (checkerboard (1000) * 65535);
tic;
J = imrotate(I,36,'pchip','crop',1);
t=toc

  • before: 38.220
  • with patch: 28.364

Although especially pchip would be faster for multi-channel images, if interp2 supported them.
For "linear" there seems to be no speed-up.

(file #52748, file #52749)

Christof Kaufmann <christofkaufmann>
Wed 19 Jan 2022 04:56:41 PM UTC, comment #3: 

Meanwhile I implemented also the other methods including "nearest" and "bilinear" using convolutions to support anti-aliasing in imresize, see bug #61760 (not yet pushed, but I already have to submit an update soon). I could see a large speedup in bilinear interpolation as well. So I guess the approach is more efficient.

I just submitted a patch for interp2.m in bug #61754, which implements bicubic interpolation there. This could be extended to bilinear interpolation with only a few lines of code, if the performance improvement can be confirmed. This would lead to a performance improvement of imremap as well.

Christof Kaufmann <christofkaufmann>
Tue 18 Jan 2022 10:30:35 PM UTC, comment #2: 

Yes, that's really what I ment. I tried to use the same Octave version, to proof that the execution time increase is really due to our octave package version, and not due to the core Octave version. And the latest Octave (7.0.90) is currently not able to install image 2.12.0, that's why I used Octave 6.3.0 instead.

But in the octave code in comment #0 is a little typo. I ment to re-rotate the image incrementally, i.e. I = imrotate(I, ...). But the given run times in comment #0 are still correct for the given test code. So the given test code is non-sense from the image processing stand point, but it is good enough to show the drop in execution speed, let's just keep it as it is.

Hartmut <hardy>
Tue 18 Jan 2022 09:52:45 PM UTC, comment #1: 

@Hartmut,

You wrote:

Octave 6.3.0 (linux) and image-2.14.0 -> 6s
Octave 6.3.0 (linux) and image-2.12.0 -> 3s

Both with 6.3.0. Is that what you meant?

Avinoam Kalma <avinoam>
Group Member
Mon 17 Jan 2022 10:17:55 PM UTC, original submission:  

I have observed the following: When you run this little script, that rotates an image several times with imrotate:


pkg load image
I = checkerboard(120);
tic;
for n=1:10
  J = imrotate(I,36,'bicubic','crop',1);
end
t=toc


Then the execution speed is significantly increased in current dev image (what should become image-2.14.0), compared to the current image release 2.12.0. I have observed this on windows and linux, and I have observed this under serveral versions of core Octave (6.3.0 and 7.0.90).

Example:

  • Octave 6.3.0 (linux) and image-2.14.0 -> 6s
  • Octave 6.3.0 (linux) and image-2.12.0 -> 3s


The other interpolation methods (nearest or bilinear) are not affected by this speed increase.

Is this a "speed regression" introduced by the recent code changes regarding bicubic interpolation? Can we improve this, back to (more or less) the old speed?

Hartmut <hardy>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #52748:  imremap.m added by christofkaufmann (11KiB - text/x-objcsrc - v1 (improve performance for 8, 16 bit int and 32 bit float images))
file #52749:  imremap_cast.diff added by christofkaufmann (2KiB - text/x-patch - v1 (improve performance for 8, 16 bit int and 32 bit float images))

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by christofkaufmann (Posted a comment)
  • -email is unavailable- added by avinoam (Posted a comment)
  • -email is unavailable- added by hardy (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 2 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-01-27 christofkaufmann Attached File- Added imremap.m, #52748
        Attached File- Added imremap_cast.diff, #52749

    Back to the top

    Powered by Savane 3.13-758e.
    Corresponding source code