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

 
 

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

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

Add a New Comment Rich Markup
   

Jump to the original submission

Thu 19 Jan 2023 06:47:15 PM UTC, comment #20: 

See problem with antialiasing in bug #63560

 Avinoam Kalma <avinoam>
Group Member
Wed 23 Feb 2022 05:37:40 AM UTC, comment #19: 


I have opened bug #62099 to continue our discussion on
lanczos* interpolation method.

Closing this bug report as fixed.

 Avinoam Kalma <avinoam>
Group Member
Tue 22 Feb 2022 09:42:26 AM UTC, comment #18: 

Thanks!

When you open the bug for Lanczos interpolation, please add me to CC.

 Christof Kaufmann <christofkaufmann>
Tue 22 Feb 2022 06:40:18 AM UTC, comment #17: 

I have added @Christof name at the top of imresize.m and added a note in the NEWS file. see:

http://hg.code.sf.net/p/octave/image/rev/bad4dabad213
http://hg.code.sf.net/p/octave/image/rev/584b4688bb02

Thank you @Christof for making this contribution, and @Hartmut for the detailed reviewing.

Let me know if I missed something.

Other issues (Lanczos interpolation) will be discussed in another bug report.

Thank you, guys :-)

Avinoam Kalma <avinoam>
Group Member
Sun 20 Feb 2022 05:39:42 PM UTC, comment #16: 

Thanks for the reviews and the nice comments. I am glad you like the code.

@Avinoam: You said, you will take care of Hartmuts suggestions. Is there anything left that I should do?

Regarding `imwarp`: There is always more that can be done. However, the next thing I want to implement is bicubic interpolation in `interpn`. Next, I probably look at bicubic interpolation in `interp1` and after that, I could make a start on `imwarp`.

 Christof Kaufmann <christofkaufmann>
Fri 18 Feb 2022 09:24:20 AM UTC, comment #15: 

Thanks, @Hartmut,
I will take care of your valuable suggestions.

I do not think that usage of imcast will be good here.
imcast changes the scale of the image ([0:255] -> [0:1]),
here we just want to change the type without rescaling.

About imperspectivewarp.m - it should be replaced by imwarp, as you have already commented in comment #2

 Avinoam Kalma <avinoam>
Group Member
Thu 17 Feb 2022 07:01:38 PM UTC, comment #14: 

I have eventually had a look at the patch (comment #11 plus interp_method from comment #4), sorry for the delay. This looks like a good piece of code to me. Thanks a lot for generating this @Christof. I would be happy to see this pushed to the image repo soon.

Just for completeness some things I've looked at:

  • There is a new feature "custom kernel", it also has a new test added.
  • There is a new method "box", it also has a new test added.
  • There is the new feature "anti-aliasing", it also has some tests.
  • All old and new BIST tests pass, also when running them 100 times in a row.
  • The help text is improved a lot and also covers those new features.
  • Coding style seems to be mostly followed.
  • The core algorithm now moved away from calling the function imremap.m. It now uses a ".*" multiplication with a kernel matrix.


Some minor details I would suggest:

  • @Christof: I think it would be alright to add your name at the top of the file "imresize.m" because you changed the core algorithm here. Please feel free to do this!
  • Please add a longer commit message, when pushing this to the repo.
  • Please mention it shortly in the NEWS file.
  • Please have a short look if the use of the image package function "imcast.m" could make this code shorter or easier to read. (I am unsure if it would.) Otherwise it is fine like it is now, as well.


Now the function "imperspectivewarp.m" is the only function left, that still uses our Octave-only "imremap.m".

 Hartmut <hardy>
Thu 17 Feb 2022 05:49:17 AM UTC, comment #13: 

If there are no comments or objections, I will push the last version in the next few days. Thanks.

 Avinoam Kalma <avinoam>
Group Member
Sun 30 Jan 2022 06:21:20 AM UTC, comment #12: 


Thanks, I will review the new patch.
I hope that @Hartmut will also review it.

 Avinoam Kalma <avinoam>
Group Member
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>
Group 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>
Group 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>
Group 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>
Group 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>
Group 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

    •  

    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 13 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-02-23 avinoam StatusReady For Test Fixed
        Open/ClosedOpen Closed
    2022-02-22 avinoam StatusPatch Reviewed Ready For Test
    2022-02-18 avinoam StatusPatch Submitted Patch Reviewed
    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

    Copyright © 2024 Free Software Foundation, Inc.
    Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.
    The Levitating, Meditating, Flute-playing Gnu logo is a GNU GPL'ed image provided by the Nevrax Design Team.
    Page source code

    Powered by Savane 3.13-7a7b.
    Corresponding source code