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

 
 

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

Submitted by:  Avinoam Kalma <avinoam>
Submitted on:  Thu 01 Apr 2021 05:58:38 PM UTC  
 
Category:  Octave Forge Package Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Inaccurate Result
Status:  None 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)

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>
Project 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>
Project Member

 

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

Attach Files:
   
   
Comment:
   

Attached Files
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)
  •  

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

    Date Changed by Updated Field Previous Value => Replaced by
    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.6