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

 
 

bug #51769: [octave forge] (image) imresize bilinear interpolation inaccurate

Submitter:  Christof Kaufmann <christofkaufmann>
Submitted:  Wed 16 Aug 2017 09:01:37 PM UTC
   
 
Category:  Octave Package Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Inaccurate Result
Status:  Fixed Assigned to:  None
Originator Name:  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

Sat 28 Aug 2021 02:12:53 PM UTC, comment #28: 

Closing according to comment #27.
Thanks @Christof

Avinoam Kalma <avinoam>
Group Member
Mon 05 Apr 2021 01:07:23 AM UTC, comment #27: 

Yes, it is fixed and can be closed.

Christof Kaufmann <christofkaufmann>
Sun 04 Apr 2021 04:17:25 PM UTC, comment #26: 

Is this issue (only the bilinear method) now fully fixed? Could we CLOSE this issue then?

Hartmut <hardy>
Thu 01 Apr 2021 05:59:45 PM UTC, comment #25: 

See bug #60322 for bicubic interpolation inaccuracies.


Avinoam Kalma <avinoam>
Group Member
Thu 01 Apr 2021 05:53:38 PM UTC, comment #24: 

I have pushed Christof's imresize.
see http://hg.code.sf.net/p/octave/image/rev/49c01ed59b61

Avinoam Kalma <avinoam>
Group Member
Wed 31 Mar 2021 01:37:35 PM UTC, comment #23: 

OK, I already had a look at cubic interpolation, but I don't want to post my insights here to not mixup different topics. Please post the link to the new bug here, when you are ready. Then we can discuss there.

Christof Kaufmann <christofkaufmann>
Mon 29 Mar 2021 08:41:21 PM UTC, comment #22: 

Thanks for the discussion!

Regarding bicubic interpolation: I can have a look. Maybe having an option for padding in imremap could help. I guess adding an option for padding to interp2 is probably going to be not accepted, right?

Christof Kaufmann <christofkaufmann>
Mon 29 Mar 2021 09:49:00 AM UTC, comment #21: 

Thanks Christof and Hartmut.
I will push the current version and open a new bug for bicubic interpolation.

Avinoam Kalma <avinoam>
Group Member
Fri 26 Mar 2021 10:19:34 AM UTC, comment #20: 

My personal preference would be to first finish up one thing (e.g. bilinear interpolation) and then afterwards proceed to the next topic (e.g. bicubic interpolation). Otherwise things might get lost on the way, given that most contributors cannot spend vast amounts of time and our whole process tends to be a bit "slowish".

Hartmut <hardy>
Tue 23 Mar 2021 10:03:46 PM UTC, comment #19: 

When I fixed bilinear interpolation, I had noticed that the results were wrong for bicubic interpolation, too. However, I was not sure, whether you would be interested in a patch at all and therefore I had not fixed bicubic interpolation.

There is also a comment in the code:
## work around for imremap, valid for linear interpolation, probably bad
## for cubic interpolation. Limits indices to the bounds 1 and end.

Should bicubic interpolation be fixed right here? The title only talks about bilinear interpolation. Still, the methods are all based on sampling points at the right positions... so would still be on topic. It could take a while for me to fix it though.

Christof Kaufmann <christofkaufmann>
Tue 09 Mar 2021 09:53:37 PM UTC, comment #18: 

@Christof:
You are right. When using a double image, Matlab result and your result are almost the same.
In uint8 images there are differences. It seems that Matlab does not do round(double image).
Since the difference is at most 1 gray level, this is acceptable.

Now to bicubic interpolation: There are big differences bwtween Octave result (yours) and Matlab result at the borders.
The size of the borders with error depends on the scale change.
Is there a simple way to fix this?

Avinoam Kalma <avinoam>
Group Member
Sun 07 Mar 2021 12:03:26 PM UTC, comment #17: 

Ah, I just see that I wrote a comment in the tests regarding the difference:

> The floating point error is less than 1e-13, but it affects the rounding
> to int. So a difference of 1 is acceptable.


So, we could check the floating point error. That would require new reference outputs without uint8, e. g.:
imresize (in, 1.5, 'bilinear', 'Antialiasing', false)

As mentioned, I don't have Matlab installed currently, but I could do that, if you think floating point comparison is better.

As an alternative, we could find the values near tie break and only accept a tolerance of 1 for them.

Christof Kaufmann <christofkaufmann>
Sat 06 Mar 2021 04:51:41 PM UTC, comment #16: 

Thanks for the fix.
Indeed 1 gray level difference is OK. However, I would like
to see if there is a simple fix for this.

Avinoam Kalma <avinoam>
Group Member
Wed 03 Mar 2021 08:28:27 AM UTC, comment #15: 

Thanks for the checks. I fixed the issue with multi-channel images and added a corresponding test, for 1 to 3 channels and for "nearest", "bilinear" and "bicubic". It just checks that resizing a multi-channel image is equivalent to resizing the channels separately.

Regarding the gray level difference: The tests have a tolerance of 1. It might be a rounding issue (tie break), I forgot. Should we investigate this or use tolerances only at tie breaks in the test?

(file #50977, file #50978)

Christof Kaufmann <christofkaufmann>
Tue 02 Mar 2021 06:15:16 PM UTC, comment #14: 

I have started to check imresize

  • With 'nearest' option
    •  A 3-bands image is transformed into a single band image (this should be fixed).
    • Using a single band image, the new imresize gives the same image as Matlab, while the current imresize does not.


  • With 'bilinear' option:
    • I got one gray level difference with respect to Matlab result.
    • More checks should be done.
Avinoam Kalma <avinoam>
Group Member
Sun 28 Feb 2021 05:41:30 PM UTC, comment #13: 

Attached @Christof Kaufmann imresize.m + diff file.

Please review.



(file #50944, file #50945)

Avinoam Kalma <avinoam>
Group Member
Wed 10 Feb 2021 05:59:41 AM UTC, comment #12: 

See also bug #57504 which seems to be the same

Avinoam Kalma <avinoam>
Group Member
Wed 10 Feb 2021 05:57:08 AM UTC, comment #11: 

Thanks @Christof for the link.
I will check it and make a diff file for review

Avinoam Kalma <avinoam>
Group Member
Tue 09 Feb 2021 09:43:26 PM UTC, comment #10: 

@Avinoam Kalma: Yes, bitbucket shut down the mercurial repositories. I forked your mercurial repository at source forge and merged my old commits with default. You can find it here:
https://sourceforge.net/u/ckaufmann/octave

Should I make a merge request or do you rather like a raw patch attached here?

BTW, here is a list of things, it does not fix:

  • Anti-aliasing is not implemented.
  • Single-row and single-column images don't work.
  • Bicubic interpolation probably needs a fix, too.
Christof Kaufmann <christofkaufmann>
Tue 09 Feb 2021 05:53:09 PM UTC, comment #9: 

@Christof Kaufmann: This bug hits again in https://savannah.gnu.org/patch/?9730

I have tried to check your patch, but did not find it.
Could you please attach the patch here?

Avinoam Kalma <avinoam>
Group Member
Sat 02 Sep 2017 03:39:24 PM UTC, comment #8: 

OK, I made a new commit. So Carne can still see the previous behavior with the changing scale factors.

Regarding the tests: OK, good to know. I added now two more tests, which require rounding the output size and confirm Matlab compatibility. I removed the test with the Gimp output, since no compatibility is desired here. Also for Gimp approach 2 is fine, since it shows the user the modified scale factors before scaling is done.

Christof Kaufmann <christofkaufmann>
Sat 02 Sep 2017 08:46:53 AM UTC, comment #7: 

@Christof:

  • Regarding your argumentation about rounding issues: I would also prefer to use the path (1.), i.e. keeping the scale factor untouched and slightly increase the output image pixel number if necessary. If you have checked (without looking at the Matlab source code) that this is also the Matlab behavior, then this path is definitly even better, because it is more Matlab compatible (and still correct in some sense). Image analysis (like done with Octave's image package) might differ here from image edition (like done with Gimp).
  • Regarding your second patch: I think it doesn't make a difference if you prepare a new patch based on your old patch, or based on the image package repo version. It is good that you are already presenting your patches in a separate (bitbucket) repository, which is the preferred way of Carne to review patches (if I understood him right).
  • The philosophy about tests in the image package is to have the test results Matlab compatible (if somehow possible). If there is a (intentional or also unwanted) Matlab incompatibility, then it's good to leave a failing (!) test in place, to document this behavior. So please do not change existing test, just because they are failing, please only change tests if those tests weren't Matlab compatible and your improved function now is. You can always add new tests, if you want to.


Eventually we need to wait for Carne's comments and review, here. He is not only the package maintainer of the image package, but he is also the latest author of the current imresize.m function and its current indexing approach.

Hartmut <hardy>
Thu 31 Aug 2017 09:55:52 AM UTC, comment #6: 

Regarding the changed tests, there are several reasons.

I added some tests to make the suite more complete:

  • nearest neighbor with x-scale 1 and y-scale 2
  • bilinear scaling with gimp output for reference
  • checkerboard


I replaced the nearest neighbor check, that used a reference matrix  to a more general test. The new pixel centers are all lying in between 4 points, similarly as shown in comment #4. So all neighbors have the same distance and thus there is no unique nearest neighbor. Hence I only checked that one of the 4 neighbors is used in the output.

The tests for bilinear and bicubic interpolation with matlab reference outputs were all failing. This is currently still the case for bicubic interpolation (I like to look at that later). However, to avoid rounding of the output size, I changed the input matrices from 7 x 10 to 8 x 10. This gives a 4 x 5 or a 12 x 15 matrix with scale factors 0.5 or 1.5, respectively. Because of the changed input I had to redo the reference outputs (but I could also not confirm all of the old Matlab results). Now the new bilinear interpolation results in the same output as the one from Matlab (without anti-aliasing).

Let me explain the issue with the output size rounding with a tiny example:
Let in = [1 2 3];
When scaling with 0.5 and the output size should be 1 x 2, there are two options:

  1. Replace the input by in = [1 2 3 3]; which will result in the output out = [1.5 3];
  2. Replace the scaling by 0.666..., which will result in the output out = [1.25 2.75];


(Note, this does not run in octave currently, since interp2 needs at least a 2 x 2 matrix to work.)
Matlab goes for the first approach, while I chose the second. Also Gimp seems to use the second. However, this might need some further discussion.

  1. Replacing the input seemed odd to me at first glance. However, it preserves the scale factor and gives accurate results for all pixels, that are not at the right or bottom border. In the example above you can see this from the first two values, which have been scaled down exactly to 1.5, which is what you expect with a factor of 0.5.
  2. Replacing the scale factor seemed better to me, since the output is accurate for the new scaling. However, this might result in a different scaling for x and y. This does clearly not preserve shapes. Also, the user might not notice that  the scaling changed at all.


So, now I think the first approach is better, since it gives less surprises. What do you think? If you agreed, I would like to change it. Are there any restrictions here about how to do it? Should I make a new commit or rather try to change the current one?

Regarding your question for the bicubic interpolation: Yes, the changed interpolation points affect all methods. Hopefully in a good way.

Sorry for the length of this comment and thanks for the good discussion!

Christof Kaufmann <christofkaufmann>
Wed 30 Aug 2017 04:35:08 PM UTC, comment #5: 

Here is the Matlab result on simple sample inputs:


in1 = checkerboard (1,2, 2);

out1 = imresize (in1, 0.5, 'bilinear')   % for Octave (has no antialiasing)
%out1 = imresize (in1, 0.5, 'bilinear', 'Antialiasing', false) % for Matlab
out1_Matlab = [0.5 0.35; 0.5 0.35]

in2 = checkerboard (1,3, 3);

out2 = imresize (in2, 0.5, 'bilinear')  % for Octave
%out2 = imresize (in, 0.5, 'bilinear', 'Antialiasing', false) % for Matlab
out2_Matlab = [0.5 0.425 0.35; 0.5 0.425 0.35; 0.5 0.425 0.35]


In general I think the approach in comment #1 and comment #4 sounds reasonable.

I have not understood yet, why you needed to change existing tests in the code? Where they never Matlab compatible? Did the Matlab result change over the last years?

Do the results of bicubic interpolation also change with your patch?

To finally review (and hopefully commit in some way) your propsed code change, we need to wait for Carne, the current image package maintainer.

Hartmut <hardy>
Mon 28 Aug 2017 08:47:55 PM UTC, comment #4: 

This problem is not mainly handling Matlab incompatibility. The approach was just not correct. Raster graphics have pixels and pixels represent the mean color (or value) of an area. They are not samples of infinitesimal small points. This is what I changed.

The image should cover the same area before and after scaling. A pixel has a width and height of 1 unit. This means the first pixel starts at (0.5, 0.5), has its center at (1, 1) and ends at (1.5, 1.5). The last pixel starts at (end-0.5, end-0.5), has its center at (end, end) and ends at (end+0.5, end+0.5). So the whole image starts at (0.5, 0.5) and ends at (end+0.5, end+0.5). The scaled image has to cover the same area, but with a different resolution. In the example of my first comment I scaled the image down by using a factor of 0.5. This means in the system of the original resolution the pixels have now a size of 2 units. So the new first pixel will start at (0.5, 0.5), have its center at (1.5, 1.5) and end at (2.5, 2.5) and so on.

From this you can see that the checkerboard in the example should give the mean value, since the new pixel centers (marked with an X) are exactly in the middle of 4 pixel groups:

+-------+-------+
| 0   1 | 0  0.7|
|   X   |   X   |
| 1   0 |0.7  0 |
+-------+-------+
| 0   1 | 0  0.7|
|   X   |   X   |
| 1   0 |0.7  0 |
+-------+-------+


Matlab shows this behavior in this example, but when a rounding  occured in the new image size, it would not adjust the scale factor. I handled rounding errors in the commit. So I was not trying to be 100% compatible, but rather to do it correct.

To answer you question: With the old behavior all positions were a bit off, since the first pixel center has always been at 1 and the last at end. The pixel centers in between were linearly spread. So for the checkerboard it just selected the 4 corner pixels.

Christof Kaufmann <christofkaufmann>
Mon 28 Aug 2017 05:25:19 PM UTC, comment #3: 

Is this problem (i.e. Matlab incompatible results) only about pixels on the edge of a resized image, or are the pixels "inside" also wrong sometimes?

Hartmut <hardy>
Thu 17 Aug 2017 04:04:33 AM UTC, comment #2: 

added people to cc

Avinoam Kalma <avinoam>
Group Member
Wed 16 Aug 2017 09:15:33 PM UTC, comment #1: 

So I made a patch for that:
https://bitbucket.org/ChristofKaufmann/octave-image/commits/branch/imresize-fix
(If you like to have a patch as attached file rather, please tell me.)

The problem in the original code were mainly the indices. These were quite wrong. I fixed the indices, which changes the behaviour of all methods; 'bilinear' works now, 'nearest' was working and is still working, 'bicubic' was not passing the test and is still not. So 'bicubic' might have to be fixed. Also, anti-aliasing is not implemented yet.

The patch also updates the matlab reference outputs and adds and modifies a few tests. It is split into two commits, since the first just makes a few coding style changes, but does not change any behaviour. The second commit has the real content.

Christof Kaufmann <christofkaufmann>
Wed 16 Aug 2017 09:01:37 PM UTC, original submission:  

octave-image version 6.2.1 (default branch from repository)

Hi,

I noticed very inaccurate results when using the 'bilinear' method with imresize. I can give a small example:

in = checkerboard (1, [2 2]);
imresize (in, 0.5, 'bilinear')
## gives:
## ans =  0.0   0.7
##        1.0   0.0

The expected behaviour would be (which matlab would give for a larger example):

imresize (in, 0.5, 'bilinear')
## gives:
## ans = 0.50   0.35
##       0.50   0.35


Christof Kaufmann <christofkaufmann>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #50977:  imresize.diff added by christofkaufmann (18KiB - text/x-patch - Fixed multi-channel nearest neighbor and added test.)
file #50978:  imresize.m added by christofkaufmann (16KiB - text/x-objcsrc - Fixed multi-channel nearest neighbor and added test.)
file #50945:  imresize.diff added by avinoam (18KiB - application/octet-stream)
file #50944:  imresize.m added by avinoam (16KiB - application/octet-stream)

 

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 (Posted a comment)
  • -email is unavailable- added by avinoam
  • -email is unavailable- added by avinoam
  • -email is unavailable- added by christofkaufmann (Submitted the item)
  • -email is unavailable- added by christofkaufmann
  •  

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

    Date Changed by Updated Field Previous Value => Replaced by
    2021-08-28 avinoam Open/ClosedOpen Closed
    2021-04-01 avinoam StatusPatch Submitted Fixed
    2021-03-03 christofkaufmann Attached File- Added imresize.diff, #50977
        Attached File- Added imresize.m, #50978
    2021-02-28 avinoam Attached File- Added imresize.m, #50944
        Attached File- Added imresize.diff, #50945
    2017-08-17 avinoam StatusNone Patch Submitted
        Release4.0.3 other
        Carbon-Copy- Added -email is unavailable-
        Carbon-Copy- Added -email is unavailable-
    2017-08-16 christofkaufmann Carbon-Copy- Added christofkaufmann

    Back to the top

    Powered by Savane 3.13-cf05.
    Corresponding source code