FLTK logo

STR #3296

FLTK matrix user chat room
(using Element browser app)   FLTK gitter user chat room   GitHub FLTK Project   FLTK News RSS Feed  
  FLTK Apps      FLTK Library      Forums      Links     Login 
 Home  |  Articles & FAQs  |  Bugs & Features  |  Documentation  |  Download  |  Screenshots  ]

Return to Bugs & Features | Post Text | Post File | SVN ⇄ GIT | Prev ]

STR #3296

Application:FLTK Library
Status:3 - Active
Priority:1 - Request for Enhancement, e.g. asking for a feature
Scope:3 - Applies to all machines and operating systems
Subsystem:Image Support
Summary:Improvement of bilinear scaling of images
Created By:rokan2
Assigned To:AlbrechtS
Fix Version:Unassigned
Update Notification:

Receive EMails Don't Receive EMails

Trouble Report Files:

Post File ]
Name/Time/Date Filename/Size  
#1 rokan2
10:33 Mar 23, 2016
#2 chris
11:22 May 29, 2016
#3 chris
11:44 May 29, 2016

Trouble Report Comments:

Post Text ]
Name/Time/Date Text  
#1 rokan2
10:33 Mar 23, 2016
This is alternative implementation of bilinear scaling.
It uses "int" calculations for speed improvement.
When scaling down it uses much better method than current one:

1) Current method is not very good for small scaling factors: If this factor is below 0.5, it will miss certain original pixels completely - the smaller factor is the more information will be missing.
For those factors it is not too much better than "nearest neighbor" because it is effectively "nearest four only" selection with additional weighting of these four.

2) My method is sort-or reversed: it does not choose four sources according to target position, but for each "source" pixel it calculates to which pixels and how it will contribute and sum of those contribution factors for all pixels is the same (1 when normalized by the number of targets) This gives much better result for those small scaling factors, - eg text is better readable, ...


For scaling up both those methods give exactly the same result - however my implementation is faster by about 30% (depends on the machine and number of pixels)

For scaling down my method is usually faster up to a factor of about 0.4, below that this method is slower: This can be explained by the fact that time of my method is proportional to the number of source pixels, current method is proportional to the number of target pixels (but as explained gives better result)

You might consider this as a replacement if you think it is worth it,
in this file it is implemented as global function

  Fl_Image * fl_copy_image(Fl_Image * im, int w2, int h2);

so that it can be used alongside current implementation with no patching required.
#2 chris
06:56 May 29, 2016
Moving over from thread https://groups.google.com/forum/#!topic/fltkcoredev/e3mSFJIciyk message http://www.fltk.org/newsgroups.php?s16723+gfltk.coredev+v16741

Meanwhile I found out by "intuitive programming" that the following fix works for the case described in the thread. Can you please check if this is reasonable?

diff resize_image.cxx resize_image_orig.cxx
<       RESAMPLE_UP(U32, unsigned char, U64, w1, w2, sou, tar, source_stride, target_stride, ,  alpha = scale * tg[alpha_shift];  if(!alpha) alpha = 1; *tg = (output + sc_add + alpha/2)/(alpha+scale);)
>       RESAMPLE_UP(U32, unsigned char, U64, w1, w2, sou, tar, source_stride, target_stride, ,  alpha = scale * tg[alpha_shift];  if(!alpha) alpha = 1; *tg = (output + alpha/2)/alpha;)

The change is to use sc_add and scale too in the alpha case.

Note: There are more instances in the file, where this change needs to be made!

BTW: I also made some other minor corrections (fixed warnings, removed unused code, reformatted a lot, fixed bitmap detection,..) in my copy. Do you want me to post it?
#3 rokan2
10:37 May 29, 2016
Hmm... seems like you are using some older version: are sure you are using current version  - 23 March 2016 from above? Because it seems it is there exactly as AFTER your patch. If you have also other fixes - yes, thanks I am interested and I will include them but check if it is against this current 23/3/2016 version (as it could be already fixed).
Thanks a lot!
#4 chris
10:53 May 29, 2016
No it is NOT there. I just re-downloaded the file resize_image.cxx from this STR and it is exactly the version I am using. Have a look at the lines 177/187/205/215,...  
#5 chris
11:22 May 29, 2016
1) Fixed warnings (-Wall -pedantic):

resize_image.cxx:244:135: warning: invoking macro RESAMPLE_UP argument 10: empty macro arguments are undefined in ISO C90 and ISO C++98 [enabled by default]
resize_image.cxx:244:135: warning: invoking macro RESAMPLE_UP argument 10: empty macro arguments are undefined in ISO C90 and ISO C++98 [enabled by default]
... (several more)
  ==> replaced the empty argument with a ; argument
resize_image.cxx:160:23: warning: ISO C++ 1998 does not support ‘long long’ [-Wlong-long]
 typedef unsigned long long U64; // use type at least 48 bit wide

  ==> use FLTK's 'HAVE_LONG_LONG' define or the 'uint64_t' type before falling back to use 'long long'

2) moved the end of the anonymous namespace (which is at a strange position at the moment) backwards

3) fl_copy_image()
  3a) detect the case w1=w2 && h1=h2 early (BTW: why did you include code for that copy at line 297ff?)
  3b) check im->d() <=1 seems more appropriate than !im->d()
  3c) ld() has to be added to the line width as far as I understand it

4) removed an unused resample() function

5) reformatted the source to split long lines (in order to better see what they do) - not the comment lines though

6) Fixed typos

7) Converted to UNIX format

8) applied the fix of course

Only 3) and 8) are really fixes, the rest is just cosmetic.

I attach my version as 'resize_image_chris_changes.cxx'
#6 rokan2
11:32 May 29, 2016
I think the confusion comes from the fact that your diff for line 215 has format in backward direction going from YOURS(newer) to OLD (mine): you've probably swapped arguments to diff command. To be sure:

Is the line 215 you want to get (new, AFTER your fix)

RESAMPLE_UP(U32, unsigned char, U64, w1, w2, sou, tar, source_stride, target_stride, ,  alpha = scale * tg[alpha_shift];  if(!alpha) alpha = 1; *tg = (output + sc_add + alpha/2)/(alpha+scale);)

If you have diff for all the reguired changes and you want to sent it I will review & apply them within next week...
#7 AlbrechtS
11:35 May 29, 2016
Chris and Roman,

I was curious and checked Roman's patch and Chris's suggested patch, let's see...

Chris, your patch seems to be reversed. The description "to use sc_add and scale too in the alpha case" shows the intention.

Roman, maybe you were confused by Chris's reversed patch?
#8 chris
11:37 May 29, 2016
The diff command issued is in the first line:

diff resize_image.cxx resize_image_orig.cxx
#9 chris
11:46 May 29, 2016
I also attach the test program I used for my initial report in #2.
It compares the output of the FLTK's current BILINEAR method with your version side by side.
#10 rokan2
12:48 May 29, 2016
Thanks, with regards to your points:

1a) yes, adding no-op code ";" can fix warnings on those compilers

1b) At the moment this code is an "extra" to fltk so it does not use its config.h. However should it become part of fltk, using HAVE_LONG_LONG is appropriate. Note that "unsigned long long" is a "brute-force" 64-bit integer definition: for this type (named as U64) it should be used 64-bit. If unavailable, the nearest longer should be used and if longer than 64-bit is unavailable too, the longest from any "int" should be used.

For "U32" the "fastest" int type not shorter than 32 bit should be used.

2) I am using the last resample() function outside fltk so it is defined as global (outside anon. namespace)

3a) If w1== w2, h1==h2 the resample() function uses efficient memcpy{} amyway, and I wanted the new code be completely separated/independent of old one and not to use it in "special cases" either.

3b) Probably good idea although for now fltk does not use negative d()... this code is rather "hack" to implement better scalling at particular time and independent of fltk.

3c) Not sure what do you mean, ld() is already uses/passed to resample() as "line stride"

4) I dont understand: there are two two resample() functions, one can use the other  so both are required.

5) I am enjoying /abusing big screen I've bought not long time ago, sorry.

6/7) thx :}

8) Ill have a look at this in next days.

#11 chris
23:34 May 29, 2016
ad 3c) Currently there is:

          int row_stride = ld ? ld : pixel_stride * w1;

       So you pass just ld as pixel_stride if ld is != 0.
       But ld() IMHO means "extra data" in addition to pixel data, so
       it should be:

          int row_stride = pixel_stride * w1 + ld;

ad 4)  Sorry. I meant the resample_scale() method in line 224.
#12 chris
23:39 May 29, 2016
ad 3b)  The point here is not so much negative values, but to check
        d() == 1 case too. Currently there is only check for d() == 0.
#13 rokan2
05:10 May 30, 2016
3c) No, everywhere in FLTK the convention is that ld is NOT EXTRA data/padding but pointer shift between two pixels in the same column and adjacent lines(eg beginnings of the lines). ld == 0 has special meaning of "packed data" and the pointer shift between lines should be calculated as w() * d() in such a case. Look for instance in Fl_Image.cxx around line 241. Your convention as "extra padding" is possible but incompatible with FLTK.

4) Right, this version with 32-bit accumulator is left-over from previous implementation where I had more-efficient shortcut if the scaling is in one direction only (and 1:1 in the other). But there was a bug so I have removed that shortcut (and simplified the code) so this version of resample_scale() with U32 accumulator can be removed too.

3b) NO, because d()== 1 can be perfectly valid Fl_RGB_Image too (a grayscale one) which you would eliminate by your modification.
So current unmodified code to eliminate pixmaps and bitmaps

   if(im->count()!=1 || !im->d()) return im->copy(w2, h2);

is the right one because only RGB(A) has count 1 and d() nonzero:
- pixmaps have count greater than 2. First part of the condition.
- bitmaps have d() == 0. Second part of the condition.
So if either first or second part is true, it is not RGB(A) and we return old, conventional copy (whatever is the implementation).
#14 chris
05:45 May 30, 2016
Guess you are right about 3b). I was fooled by Pixmaps having d=1 and did not consider the whole statement. Thanks for the explanation.

Concerning line data, I only read the documentation, and it talks about extra data. So either I misunderstand the documentation or it is wrong:


int Fl_Image::ld() const

Returns the current line data size in bytes.

Line data is extra data that is included after each line of color image data and is normally not present.
#15 rokan2
06:19 May 30, 2016
Yep, you are right, seems like misleading, unclear documentation. Checked again in Fl_Image.cxx, ld() is used at several places, always understood as a WHOLE line: pixels + extra_padding. Can you fill a separate STR so that doc can be corrected? Thanks.  
#16 chris
07:29 May 30, 2016
Well, seems nobody knows for sure. I see also code within current FLTK that uses ld() as extra data e.g. in Fl_win32.cxx, lines 2227-2247.  
#17 rokan2
08:23 May 30, 2016
This code in Fl_win32.cxx is relatively new and inconsistent with both Fl_RGB_Image class and fl_draw_image(...) function. Seems like a bug to me (which does not show for ld() == 0). I will go back to coredev with this issue...  
#18 AlbrechtS
08:35 May 30, 2016
Note: fixed typo in title ("Summary"): s/scalling/scaling/
for better search results.
#19 AlbrechtS
08:53 May 30, 2016
I agree with Roman that the documentation and code are inconsistent, and I do also believe that the docs are wrong in this regard.

Thanks to Chris for the pointer to the code in Fl_win32.cxx. Again, I agree with Roman that this (new) code is inconsistent and should probably be changed.

Note: I just filed STR #3308:
#20 AlbrechtS
06:36 Feb 01, 2023
As noticed by Chris (thanks) this STR supersedes STR 3126 "Image resizing algorithm" which is now closed. In case of questions or for more info please refer to this closed STR: https://www.fltk.org/str.php?L3126  
#21 chris
04:21 Feb 03, 2023
As this STR (and it's predecessor) have quite a long history, here is a summmary of the current state:

- The initial version in attachement #1 here had only one minor flaw with transparent images, that was corrected with a change in attachment #2.
- It's downscaling quality is *much* better than that of the current bilinear scaling.
- The (up-)scaling accuracy is better: with the current scaling images that stretch to the edges are aften cut off by 1 or 2 pixels (see https://www.fltk.org/strfiles/3126/test2.png and comment #2 in https://www.fltk.org/str.php?L3126).
- Speedwise it on par or faster than the current scaling.
- I have been using this version for quite a while in the past and it worked well without any unwanted side effects.

I do have a cleaned up version based on current head, that I could turn in a PR easily if you would like to use this contribution.
(I do not attach a diff here because these tend to get invalid soon).
#22 AlbrechtS
11:14 Feb 03, 2023
Hi Chris, thank you for your continuing support of FLTK, your help is much appreciated, and your summary is very helpful. I'm afraid I don't have enough time to understand and test this proposal sufficiently to add it to FLTK right now, but anyway:

Since you obviously know how to use it: what did you do to integrate it in FLTK? Did you replace the existing algorithm, or did you add this as another algorithm that can be selected by the user (another value in the enum which I don't remember right now)?

From what I read so far, the algorithm could be tested easily with the provided test program (file #3: 'test_resize_image.cxx') and the modified source file #2: 'resize_image_chris_changes.cxx', is this correct?

Maybe a PR could help to integrate this new (or should I say "old"? ;-)) algorithm in FLTK, but I see a lot of (formatting) and maybe more issues in the given patch. So please don't bother making a PR yet, but I may come back to your offer. :-)

OK, I'm looking into it now but I can't promise anything yet...

Return to Bugs & Features | Post Text | Post File ]


Comments are owned by the poster. All other content is copyright 1998-2024 by Bill Spitzak and others. This project is hosted by The FLTK Team. Please report site problems to 'erco@seriss.com'.