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

 
 

bug #60322: [octave forge] (image) imresize bicubic interpolation inaccurate

Submitter:  Avinoam Kalma <avinoam>
Submitted:  Thu 01 Apr 2021 05:58:38 PM UTC
   
 
Category:  Octave Package Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Inaccurate Result
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 06 Jan 2022 07:48:56 PM UTC, comment #24: 

Pushed:

http://hg.code.sf.net/p/octave/image/rev/69c15ef73ae6
http://hg.code.sf.net/p/octave/image/rev/70381e694d1b

Thanks, @Christof for this valuable improvement.
Thanks, @Hartmut for reviewing.

See you in bug #61760.

Closing as fixed.

Avinoam Kalma <avinoam>
Group Member
Wed 05 Jan 2022 03:52:59 PM UTC, comment #23: 

I've seen the new file versions (comment #19 and comment #22). There is now even a note about the missing anti-aliasing. Those files look fine to me, I'd be happy to see them pushed to the image repo. Thanks for taking care of this, Avinoam.

Hartmut <hardy>
Tue 04 Jan 2022 01:29:58 PM UTC, comment #22: 

Very nice. Thank you!

Christof Kaufmann <christofkaufmann>
Tue 04 Jan 2022 12:01:23 PM UTC, comment #21: 

As you wish :-)
see attached file.
I have added spaces after function names.

(file #52611)

Avinoam Kalma <avinoam>
Group Member
Tue 04 Jan 2022 11:23:57 AM UTC, comment #20: 

@Avinoam: I am not a big fan of line breaks in general, but especially the ones in imremap.m:221–228 seem to make it more difficult to read (in my opinion).

The note comment in imresize is very helpful.

Christof Kaufmann <christofkaufmann>
Tue 04 Jan 2022 05:52:44 AM UTC, comment #19: 

Now with the files (Thanks @Christof)

(file #52608, file #52609)

Avinoam Kalma <avinoam>
Group Member
Tue 04 Jan 2022 12:19:26 AM UTC, comment #18: 

@Avinoam: The file is missing.

Christof Kaufmann <christofkaufmann>
Mon 03 Jan 2022 10:10:32 PM UTC, comment #17: 

I have filed a new bug report (#61760) about antialiasing.

Please review the attached files (the last patch of @Christof with some cosmetic changes).

Avinoam Kalma <avinoam>
Group Member
Mon 03 Jan 2022 09:15:08 AM UTC, comment #16: 

@Avinoam: Your suggestions (comment #14) sound like a good way forward. Thanks for your engagement in this topic.

Hartmut <hardy>
Mon 03 Jan 2022 01:34:59 AM UTC, comment #15: 

OK, I filed a new bug report in bug #61754.

I also think anti-aliasing should be a different bug report. It can be fixed there or at least documented as "not implemented". When you open the bug, maybe give a reference to comment #1 in it. Maybe it would also be useful to have the link to the bug report here.

Thanks for the discussion, review and code improvements!

Christof Kaufmann <christofkaufmann>
Sun 02 Jan 2022 05:08:28 PM UTC, comment #14: 


I have checked the results for the new code.
Looks very good - I have checked Matlab compatibility.
I have checked uint8(imresize(double(I), factor)), and the results are the same (if we set antialiasing as false).
Checking uint8 images gave up to 4 gray levels difference.

I would like to push this code, and:
1. Handle the antialiasing in another bug report
2. Make a few coding style corrections.

Any objections (@Harmut)?

Thank you very much, @Christof, for the good work.

Avinoam Kalma <avinoam>
Group Member
Wed 29 Dec 2021 08:21:41 PM UTC, comment #13: 

I just had a short look at the more formal aspects of this latest patch (from comment #12). And most things looked fine to me. (Good test coverage, all tests pass, doc strings, coding style.) One single point I noted:

  • It seems to me (from the comments in the tests) that Octave's imresize only gives Matlab compatible results, when Matlab runs with the anti-aliasing turned off. If this is true, I think this should be mentioned somewhere in the help string of imresize. (Is this only relevant when shringing images, as suggestd by the Matlab help page?)


I would like Avinoam to also have a last look at the algorithmic logic of this new code. He started to look into this, that's why I hesitate to also dig deeply into this. Afterwards we should hopefully be ready to push this code improvement to the image repository.

One other thing that I realised when reading through the history of this bug report is: a new bug report regarding the incompatibility of the bicubic method in interp2.m (in core Octave) has not been filed so far (as discussed in comment #4 and #5). I would be very good to still do this. Or maybe I have missed this new bug report, then please just mention its bug report number here.

Hartmut <hardy>
Mon 25 Oct 2021 11:35:27 AM UTC, comment #12: 

So, now that the patch of bug #60946 has been pushed, I rebased the patch for the bicubic interpolation, see attachment. I also extended the tests regarding 1-pixel images, row images and column images from bug #60946. These now check nearest neighbour, bilinear and bicubic interpolation to have a better code coverage.

(file #52152)

Christof Kaufmann <christofkaufmann>
Sat 14 Aug 2021 08:18:22 PM UTC, comment #11: 

Sorry for my long silence.
I will check the patch, assuming that the patch of bug #60946 will be pushed soon.

Avinoam Kalma <avinoam>
Group Member
Tue 13 Apr 2021 09:43:17 AM UTC, comment #10: 

Note concering the filtering (e.g. interpolation) of color images:
Yes, I think it is totally common to do this channel wise directly in the RGB color space. But this method generates interpolated colors with some "not so nice" properties, because the RGB color space is not linear in terms of visual perception, for example visual brightness perception. An example to see this is to smooth (or interpolate) a sharp color edge from red to blue color. The generated interpolation colors will be darker (converted with rgb2gray for example) than either red and blue color are on its own. (Because those sharp color edges are pretty rare in real photography images, this is not too much of a problem with this kind of images.) If you want to do better, you can first convert the color image to a "more linear" color space, e.g. LUV oder Lab, do the filtering there, and then convert back. This way you do not generate "wrong" interpolation brightnesses, but you need to take a bit more care when doing the math of interpolating the color channels. If you want to read more about this, I can suggest the book of Burger and  Burge (available in English and German), chapter 15 "filtering of color images" (in the german 3rd edition).

Yes, let's wait and see if Avinoam has more comments on your proposed patch.

Hartmut <hardy>
Sat 10 Apr 2021 09:31:11 PM UTC, comment #9: 

Thanks for your comments.

  • So, I found a quite recent thread about unit testing local functions. So it is not really possible.


  • I seem to have tested everything (partially implicitly) except the padding function. I checked it manually, but I have to add a unit test for it. Actually I can test it indirectly. I haven't thought about it before. So there is no need for making it global.


  • I will revert the demo changes. However, I think that RGB images are indeed interpolated channel-wise. Just out of curiosity, what is the alternative from your experience?


I prepared an updated patch (appended), so Avinoam does not need to look at outdated code.

(file #51235)

Christof Kaufmann <christofkaufmann>
Fri 09 Apr 2021 06:41:26 PM UTC, comment #8: 

(edit: It's probably better to ask on the maintainer's forum nowadays, and not use the old mailing list if you decide to do so: https://octave.discourse.group/c/maintainers/ )

Hartmut <hardy>
Fri 09 Apr 2021 06:32:28 PM UTC, comment #7: 

I have not tried to understand the algorithms and code to do the real calculation here, because I think that Avinoam is already into this topic and will probably continue with this.

Nevertheless I will comment on your discussion points from comment #6:

  • testing a local function: I think it is OK to not explicitly test this local function pad_indices in imremap at all. We do still test this local function implicitly, when running the tests in imresize, is this true? I agree, that this would probably not be worth the "mess" of a dedicated subdirectory as with @strel. But if you still consider it useful to test this local function explicitly in some way, you could simply ask on the Octave maintainers email list, probably someone there will have a hint for you how to do this (or confirm your suspicion that it's impossible): -email is unavailable-


  • change the demo to color images: I personally do not like this change. Demos are not ment to be tests, they are more kind of educational to show what you can do with a function. And doing interpolation of color images on the 3 color channels seperatly is a bit wrong from the image processing aspect. So I would rather not make this a showcase example, but rather stick with a demo using a grayscale image, here.


  • padding option: I think this is fine. Imremap is an Octave only function, so there are no compatibility considerations involved. Addidtionally you only add a feature, you do not remove one, so no long standing user of the image package will be disturbed by this.


  • The +-1 difference in output images of integer classes: I think this is fine as well. It is hard to perfectly mimic thte Matlab outputs without actually knowing their code. And your result has 100% the same quality, it is just not 100% compatible to their implementation. A side note: Yes, we are maybe "better" in terms of accuracy with this implementation, but on the other hand we do need more memory for this calculation on integer images, if it is really true that Matlab does the full calculation in the integer domain. Below the bottom line: Our compatibility would still improve a lot to what it currently is.


Just an additional question: Are there now tests included for all the code improvements you did? If you improved the code in aspect A, you should afterwards add a test to check for this aspect A. Otherwise this improvement might get lost after another person, who might not look out for this aspect A, does the next code change to this function.

Thanks for this good code improvment! Let's see if Avinoam has more comments.

Hartmut <hardy>
Wed 07 Apr 2021 04:17:14 PM UTC, comment #6: 

So I finished the implementation in imremap, see attached patch.

Here are some discussion points about the code:

  • I left in a commented out test of a local function in the bottom of imremap.m. Is there some way to add unit tests for local functions? I saw e. g. the "@strel" directory, but did not want to go the same way on my own. If you think unit testing the local functions is important, we could go this way.
  • I changed the demos in imremap to RGB images to see how the interpolation reacts to RGB images. However, there is also a unit test in imresize to check this.
  • There is now a padding option in imremap that can be used instead of extrapval (which is actually constant padding). The padding argument is only valid for bicubic interpolation. It is necessary for imresize, when the output size is rounded up in such a way, that the interpolation point are outside of the input image. This happens in one of the unit tests in imresize (the one with scale 1/3).
  • Regarding the tolerance of 1 in the comparison with the Matlab results in the imresize unit tests, I found that Matlab does not seem to do the algorithm in double and round afterwards, but using another algorithm for integer types. The floating point results are quite the same, but when using integer the result in Matlab is sometimes rounded up and sometimes rounded down. So the bicubic interpolation is not completely compatible, because we are more accurate.


(file #51207)

Christof Kaufmann <christofkaufmann>
Mon 05 Apr 2021 01:34:41 AM UTC, comment #5: 

OK, I will do that. However, a small benefit from doing it in a function, which is not available in Matlab and hence does not have to be compatible interface-wise, is, that we can have a padding in the interpolation, which is more efficient. Anyway, the most part of the implementation could be moved to interp2, I think.

Christof Kaufmann <christofkaufmann>
Sun 04 Apr 2021 05:24:03 PM UTC, comment #4: 

I have not followed this topic too deeply. But when reading Christof's choice in comment #1, then I would naturally prefer to have the best of both worlds: use interp2 (to not invent the wheel a second time) and still have Matlab compatible results from our imresize. But when I understand this correctly, this ideal solution is currently not possible because interp2 is Matlab incompatible. If this is true, I am fine with proceeding as you currently planned (comment #3) for a short term improvement of our image package function.

But please also DO file a new bug report and explain (to the core Octave people) what is incompatible with the current implementation of interp2. This could help them fix interp2 and then give us the possibility to maybe get the ideal solution in the long run.

Hartmut <hardy>
Sat 03 Apr 2021 10:49:53 AM UTC, comment #3: 

OK, I made (besides the loop implementation) two vectorized test implementations and compared their performance, see attached script. In terms of Wikipedia:

  • The first one uses the formula for W(x).
  • The second one uses the formula for p(t).


To my surprise the first one is faster. I will do an implementation in imremap based on the first approach and report back when it's done. Any comments or feedback that I need to consider?


(file #51180)

Christof Kaufmann <christofkaufmann>
Fri 02 Apr 2021 03:30:53 PM UTC, comment #2: 

Thanks Christof,

imremap implementation of bicubic interpolation was removed because of bug #55780.

If we get Matlab compatibility, we can reintroduce the bicubic convolution algorithm in imremap, with the right alpha.
 




Avinoam Kalma <avinoam>
Group Member
Fri 02 Apr 2021 02:27:51 PM UTC, comment #1: 

So, imresize and interp2 in MATLAB use a convolution algorithm, see Wikipedia, with a = -0.5 and a symmetrical padding for the borders. In Octave imresize uses imremap, which uses interp2 and this approximates the derivatives instead of using the convolution algorithm, see Wikipedia. So interp2 is not MATLAB compatible. imremap was implementing an own bicubic interpolation using convolution in 2019, see this commit, but with a = -1 instead of a = -0.5.

Now, there are basically two options:

  • Reintroduce the bicubic convolution algorithm in imremap, but with a = -0.5. This would give MATLAB compatibility.
  • Stick with interp2 and apply appropriate padding (only for scale > 1). Then we could not test against a MATLAB reference and need a new test.


I don't know what is better. We might want to look at some interpolated images and compare them. The differences are not only near the borders. However, currently there are errors at the border because of a workaround to avoid padding for bilinear interpolation. I made an example to compare the results of both bicubic methods, see attachment bicubic_examples.m. bicubic_conv yields the same results as MATLAB and bicubic_interp uses interp2 with padding.

I read somewhere that MATLAB implements antialiasing by broadening the interpolation convolution kernel. When thinking about implementing antialiasing, it could be useful to have a convolutional implementation of the cubic interpolation. Though there are certainly other ways of implementing antialiasing.

So, what's your opinion?

(file #51178)

Christof Kaufmann <christofkaufmann>
Thu 01 Apr 2021 05:58:38 PM UTC, original submission:  


There seem to be differences between Matlab results and Octave results, when doing bicubic interpolation.
The differences are near the boundaries of the image.

See also bug #51769

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 #52611:  imremap.m added by avinoam (11KiB - application/octet-stream)
file #52608:  imresize.m added by avinoam (21KiB - application/octet-stream)
file #52609:  imremap.m added by avinoam (11KiB - application/octet-stream)
file #52152:  bicubicpatch3.diff added by christofkaufmann (20KiB - text/x-patch - Bicubic implementation in imremap - v3 (rebase))
file #51235:  bicubicpatch2.diff added by christofkaufmann (16KiB - text/x-patch - Bicubic implementation in imremap - v2 (reverted demos; test padding))
file #51207:  bicubicpatch1.diff added by christofkaufmann (16KiB - text/x-patch - Bicubic implementation in imremap - v1)
file #51180:  bicubic_implementations.m added by christofkaufmann (7KiB - text/x-objcsrc - Two implementations of bicubic interpolation to compare performance)
file #51178:  bicubic_examples.m added by christofkaufmann (3KiB - text/x-objcsrc - Both bicubic methods with tiny examples.)

 

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 avinoam
  • -email is unavailable- added by christofkaufmann (Updated the item)
  • -email is unavailable- added by hardy
  • -email is unavailable- added by avinoam (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 13 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-01-06 avinoam StatusPatch Reviewed Fixed
        Open/ClosedOpen Closed
    2022-01-04 avinoam Attached File- Added imremap.m, #52611
    2022-01-04 avinoam Attached File- Added imresize.m, #52608
        Attached File- Added imremap.m, #52609
    2022-01-03 avinoam StatusNone Patch Reviewed
    2021-10-25 christofkaufmann Attached File- Added bicubicpatch3.diff, #52152
    2021-04-10 christofkaufmann Attached File- Added bicubicpatch2.diff, #51235
    2021-04-07 christofkaufmann Attached File- Added bicubicpatch1.diff, #51207
    2021-04-03 christofkaufmann Attached File- Added bicubic_implementations.m, #51180
    2021-04-02 avinoam Carbon-Copy- Added carandraug
    2021-04-02 christofkaufmann Attached File- Added bicubic_examples.m, #51178
    2021-04-01 hardy Carbon-Copy- Added hardy

    Back to the top

    Powered by Savane 3.13-cf05.
    Corresponding source code