bugGNU Octave - Bugs: bug #61760, [octave forge] (image) imresize -...

 
 

bug #61760: [octave forge] (image) imresize - antialiasing is not implemented

Submitted by:  Avinoam Kalma <avinoam>
Submitted on:  Mon 03 Jan 2022 10:01:14 PM UTC  
 
Category:  Octave Forge Package Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Matlab Compatibility
Status:  Patch Submitted Assigned to:  None
Originator Name:  Avinoam Open/Closed:  Open
Release:  other Operating System:  Any

Add a New Comment (Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

( Jump to the original submission)

Thu 27 Jan 2022 05:29:27 PM UTC, comment #11: 

OK, I removed Lanczos for now. The attached patch is a proper export of a commit on the default branch. Additionally the current version of imresize.m is also attached (interp_method.m is attached in comment #4).

(file #52752, file #52753)

Christof Kaufmann <christofkaufmann>
Mon 24 Jan 2022 04:41:08 PM UTC, comment #10: 

We would like to release image package 2.14 in the next few weeks,
after a new release candidate for Octave version 7 will be released.

I am not sure that we will be able to review the Lanczos code before the release, but the antialiasing for bicubic interpolation could be a very good contribution to this image package release.

Avinoam Kalma <avinoam>
Project Member
Mon 24 Jan 2022 09:02:48 AM UTC, comment #9: 

Thanks for your comments. Anti-aliasing is generally only a thing to prevent frequency overlap, which can only occur when downscaling. The (new) documentation says about the property "Antialiasing":

> If this is set to @code{true} and the scale factor in horizontal or vertical direction is less than 1, anti-aliasing will used for that direction.

And regarding the default value in the same paragraph:

> The default value is @code{true}, except for the method "nearest" / "box".

Maybe we can improve the documentation, if this is not explicit enough. Do you have any suggestions?

I fixed the typo, that you mentioned. Thanks. (I will provide an updated patch when our discussion leads to new decisions.)

Regarding Lanczos:
When is version 2.14 due? I would like to know to set the right priorities regarding the implementations of interp1, interp2, interpn and imresize, and maybe a simple performance improvement of imremap.
I think I can do better with the textbox Lanczos (by implementing normalization) and maybe also get closer to the Matlab Lanczos. For that we could provide:

  • lanczos2 (quite matlab compatible, by limiting to "6 taps and 32 phases" and normalization)
  • lanczos2improved (only normalization, more accurate)
  • lanczos3 (quite matlab compatible, by limiting to "6 taps and 32 phases" and normalization)
  • lanczos3improved (only normalization, more accurate)

What do you think about that? I have no numbers yet about the differences though.

I just provided this work-in-progress patch so early to get your opinion on Lanczos and, maybe, also be able to look at the performance. At least Hartmut seems very interested in performance according to the discussion in bug #61845.

Christof Kaufmann <christofkaufmann>
Mon 24 Jan 2022 07:12:55 AM UTC, comment #8: 

Correction of comment #6, item 1:

Reading again the documentation, antialiasing is always true
unless "nearest" is used as interpolation method, or
if the input image is a categorical array (which is not supported by here) and the method is "box".

So the antialiasing does not depend on upscaling or downscaling.

Avinoam Kalma <avinoam>
Project Member
Sun 23 Jan 2022 06:37:14 AM UTC, comment #7: 

Another issue:

If Lanczos2 and Lanczos3 are still in work, we should remove them by now from the code, with "Not implemented yet".
We should also remove the printings in the tests.

We can ignore Lanczos2 and Lanczos3in the tests, or use xtests (maybe with a new bug number).

Avinoam Kalma <avinoam>
Project Member
Sun 23 Jan 2022 06:16:30 AM UTC, comment #6: 

Very nice work @Christof.
I would like to make some more tests, but meanwhile:

1. If I understand correctly if antialiasing is not specified, the default should be True only when downscaling, not for upscaling
2. typo: "Antialiasing must bei true, false or a number" in line 180.

I hope that we will be able to push it to the upcoming 2.14. release.

Avinoam Kalma <avinoam>
Project Member
Thu 20 Jan 2022 03:44:18 AM UTC, comment #5: 

This is an update with the following improvements:

  • The coding style is now more consistent.
  • The type cast of the input image is now optimized. For 8 and 16 bit types single precision is enough. A performance test is commented out at the bottom.
  • The implementation had issues when the resulting image gave a single row, single column or single pixel. There are now new tests for that and the issue is fixed of course.

Note: Lanczos2 and Lanczos3 are still not fixed. So, consider this still as work in progress.

BTW: I attached the full file again. Are you OK with this or should I rather attach a diff to the current tip? I did not reattach interp_method.m, since it is unchanged from comment #4.

(file #52695)

Christof Kaufmann <christofkaufmann>
Wed 12 Jan 2022 04:20:51 PM UTC, comment #4: 

I finished implementing imresize based on convolution.

  • I found out that "box" is the same as "nearest". I modified private/interp_method accordingly.
  • Anti-aliasing is implemented, like described here and here.
  • Performance might have improved. The convolution is now implemented in a more generic way. It requires less memory for bicubic interpolation. Compared to imremap / interp2 I could verify for bilinear interpolation that the convolutional approach is much faster.
  • A Property-Value interface is now implemented.
  • There are new tests for all the new features.
  • Matlab compatibility has improved a lot. However, I did not do anything for indexed colours or categorical images (except adding a note that there is currently no support).
  • Lanczos2 and Lanczos3 filters are now included.

I am quite happy with the results so far, but there is one big issue left: I implemented Lanczos in the way it is described at Wikipedia and everywhere else. I believe this gives quite good results, although the sum of coefficients may not be 1 (see last paragraph in wikipedia/Limitations). For normalization the coefficients of all shifts would have to be saved or at least added up, which costs a bit of memory. I have not tried that and don't know if this is a big issue, maybe not. The thing with the Lanczos implementation is, that it is quite similar to what Matlab does, but does not give the same results. Matlab precalculates the coefficients from the Lanczos kernels. Here they say they use 6 taps and 32 phases. So they use an approximation, maybe also optimized for hardware and I don't know which implementation is more accurate. I can try to mimic their behaviour, but I don't know if it is worth it. I left some outputs in the test for you, that show the mean absolute difference and max absolute difference between my Lanczos implementation and the Matlab reference images.

Maybe you can have a look on the imresize and tell me your opinion on Lanczos. I would appreciate a fast response, because it is a lot of work for me to get into interpolation again after a long time not looking into this.

(file #52651, file #52652)

Christof Kaufmann <christofkaufmann>
Fri 07 Jan 2022 03:54:52 PM UTC, comment #3: 

Sounds like a good idea at first glance, but when looking deeper into this, it is independent of this issue. The only functions that are using imremap are imresize and imperspectivewarp.

imresize would be the only function supporting anti-aliasing. It seems, that it needs an own implementation of interpolation based on convolution. Even for bilinear interpolation and maybe nearest neighbor as well to support anti-aliasing.

imperspectivewarp and imresize are both octave specific. Maybe they could be merged into imwarp. imperspectivewarp is quite similar to imwarp when using tform. The Matlab version of imwarp does not support anti-aliasing and also not "box", "lanczos2" and "lanczos3" interpolation methods. So it seems, they also have two implementations.

It is also not straightforward to implement anti-aliasing for imwarp, since the scale factor is required. imresize directly gives the scale factor, but for imwarp it is not that easy (but should be possible for linear transforms, I guess). With imremap it is possible to specify the interpolation points directly and then its impossible to define the scale in general.

Overall I think the convolutional based interpolation can be implemented in imresize directly (in this issue here). imremap can stay as it is for now, but in future the bicubic interpolation from bug #60322 should be moved into interp2 (bug #61754) and imremap might be merged with imperspectivewarp into imwarp.

Christof Kaufmann <christofkaufmann>
Wed 05 Jan 2022 04:50:58 PM UTC, comment #2: 

I would like to draw your attention to an older note from Carne:

"Since you're talking about cleaning up imremap, I would advise in investing your time in implementing imwarp instead. That would be matlab compatible. imremap is Octave only and is meant to do a  very similar job. Eventually, imremap should be throw out and replaced with the Matlab compatible function, so you might as well do that now."

(from bug #55780, comment 7)

I also think that before investing developer time for a huge revamp of our Octave-only imremap (what could be the result of this bug report here), we should consider implementing the Matlab-compatible imwarp function instead, and then use this new function to fix this (anti-aliasing issue in imresize) issze as well. Like this, the same development time (for an convolutional implementation e.g.) would have a greater impact.

What do you think?

Hartmut <hardy>
Wed 05 Jan 2022 04:16:35 PM UTC, comment #1: 

So anti-aliasing can be avoided by reducing high-frequency components in the image before downscaling. This can be done e. g. by applying a gaussian blur with sigma = 1/scale/2. I tried that, but it gives quite different results than the method used by Matlab.

Then I found this blog:
https://blogs.mathworks.com/steve/2017/01/16/aliasing-and-image-resizing-part-3/

With this anti-aliasing method I get the same results as in Matlab. However, I only tried bicubic interpolation yet, since the method requires convolution based interpolation and we only do this for bicubic interpolation currently. So, my opinion is, that because of anti-aliasing we should implement all interpolation methods as convolution kernels. This would also allow to implement "box", "lanczos2" and "lanczos3" interpolation methods, which exist in Matlab, but not in Octave yet. For upscaling and for downlscaling without anti-aliasing we could still use interp2 for bilinear and nearest neighbour methods, but I am not sure whether it wouldn't be simpler to do it all by convolution then. What is your opinion?

Also the defaults should be updated to bicubic with anti-aliasing (only in case of downscaling).

Christof Kaufmann <christofkaufmann>
Mon 03 Jan 2022 10:01:14 PM UTC, original submission:  

Antialiasing (https://en.wikipedia.org/wiki/Spatial_anti-aliasing) is used to remove signal components with high frequency, when
resampling at a lower resolution, otherwise,  undesirable artifacts may appear.

Currently, imresize does not support antialiasing.

Avinoam Kalma <avinoam>
Project Member

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #52752:  imresize_anti_aliasing.patch added by christofkaufmann (27KiB - text/x-patch - v3 (removed Lanczos and improved style))
file #52753:  imresize.m added by christofkaufmann (34KiB - text/x-objcsrc - v3 (removed Lanczos and improved style))
file #52695:  imresize.m added by christofkaufmann (45KiB - text/x-objcsrc - v2 ([WIP] better type cast, fix single row/column output))
file #52651:  interp_method.m added by christofkaufmann (1KiB - text/x-objcsrc - v1 (lanczos filters not matlab compatible))
file #52652:  imresize.m added by christofkaufmann (43KiB - text/x-objcsrc - v1 (lanczos filters not matlab compatible))

 

Depends on the following items: None found

Items that depend on this one: None found

 

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

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.

     

     

     

    Follow 9 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-01-27 christofkaufmann Attached File- => Added imresize_anti_aliasing.patch, #52752
        Attached File- => Added imresize.m, #52753
    2022-01-23 avinoam StatusNone => Patch Submitted
    2022-01-20 christofkaufmann Attached File- => Added imresize.m, #52695
    2022-01-12 christofkaufmann Attached File- => Added interp_method.m, #52651
        Attached File- => Added imresize.m, #52652
    2022-01-04 avinoam Carbon-Copy- => Added -email is unavailable-
    2022-01-03 avinoam Carbon-Copy- => Added carandraug
        Carbon-Copy- => Added hardy

    Back to the top


    Powered by Savane 3.7