Issue 121233 - Lanczos3 resampling for Bitmaps
Lanczos3 resampling for Bitmaps
Status: RESOLVED FIXED
Product: General
Classification: Code
Component: code
4.0.0-dev
All All
: P3 normal (vote)
: 4.0.0
Assigned To: Armin Le Grand
:
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2012-10-18 20:01 UTC by Tomaž Vajngerl
Modified: 2012-10-30 12:03 UTC (History)
6 users (show)

See Also:
Issue Type: PATCH
Latest Confirmation on: ---
Developer Difficulty: ---


Attachments
Lanczos3 resampling for Bitmaps (10.83 KB, patch)
2012-10-18 20:01 UTC, Tomaž Vajngerl
no flags Details | Diff
Lanczos3 resampling for Bitmaps : dup line fix (10.73 KB, patch)
2012-10-19 20:15 UTC, Pedro Giffuni
no flags Details | Diff

Note You need to log in before you can comment on or make changes to this issue.
Description Tomaž Vajngerl 2012-10-18 20:01:17 UTC
Created attachment 79792 [details]
Lanczos3 resampling for Bitmaps

Hi,

Attached is a patch for lanczos3 resampling of Bitmaps which I would be glad if it is used in Apache OpenOffice.

Regards, Tomaž
Comment 1 Pedro Giffuni 2012-10-18 20:15:34 UTC
I will take this.
Comment 2 Ariel Constenla-Haile 2012-10-18 20:20:47 UTC
(In reply to comment #1)
> I will take this.

Wouldn't it be better to let Armin review the patch? he is the expert in this area
Comment 3 Pedro Giffuni 2012-10-18 20:24:12 UTC
Thank you Tomaz, it's a great feature!!

I was actually considering to use the functions provided by Vigra to provide the bicubic resampling but having the code here and not depend on Vigra is actually good.

Looking at the Symphony code, there is:

symphony/trunk/main/vcl/inc/vcl/bitmap.hxx (line 54)
...
#define BMP_SCALE_SUPER             0x00000004UL
...

I will ask in the list to see if there is someone from the Symphony team that has conflicting plans here or I will go ahead and commit it.
Comment 4 Pedro Giffuni 2012-10-18 20:31:08 UTC
(In reply to comment #2)
> (In reply to comment #1)
> > I will take this.
> 
> Wouldn't it be better to let Armin review the patch? he is the expert in
> this area

I will take it != I will commit this without asking :).

More reviewers are always welcome and if Armin wants to take over I won't object.
Comment 5 Rob Weir 2012-10-19 00:28:36 UTC
Just noting for the record, in case this comes up later.  The same code is also in LibreOffice.  But this is OK because the author of the LO code is the same person who is submiting the patch here to AOO.

For reference:  http://cgit.freedesktop.org/libreoffice/core/commit/?id=47e0df5cebc05576e55210c5dd408a6f3eb91700
Comment 6 Armin Le Grand 2012-10-19 08:44:24 UTC
ALG: Hi Tomaž, thanks for adding the patch here, this is very welcome!
@Pedro: Go ahead...
Comment 7 Armin Le Grand 2012-10-19 08:46:57 UTC
ALG: Took a look; it seems as if these nice high-quality scalers are added, but not used yet.
@Tomaž: Which one do you think should be used by default in the future? Should it get the default ASAP?
Comment 8 Andre 2012-10-19 09:59:05 UTC
@Tomaž: Thanks for improving the bitmap resampling.
At first I wondered why you reimplemented the convolution but then I looked at Bitmap::ImplConvolute3 in vcl/source/gdi/bitmap4.cxx an saw why.  Maybe we can replace it with your code.

Two remarks:

1. At about line 25 of your patch there is a line
+	    else if( BMP_SCALE_LANCZOS == nScaleFlag )
that exists twice (the copy is two lines down).

Remove the first to activate the Lanczos resampling.

2. In ImplScaleConvolution you are using an separable kernel.  If I understand that method correctly then ImplConvolutionPass is used to do a horizontal application of the two one-dimensional kernels.  For this to work the image has to be transposed twice.  Either I am not understanding all this correctly or I fail to see where the transposition takes places.  Can you explain what I am missing?
Comment 9 Tomaž Vajngerl 2012-10-19 10:02:34 UTC
I think SCALE_SUPER from Symphony should be default and used for bitmaps on the GUI as it is as fast as SCALE_INTERPOLATE when scaling ratio is > 0.5, but much better quality for scaling ratio < 0.5. 

Lanczos should be used when quality of scaling is more important than speed - which means at (PDF) export or where the bitmap is persistently scaled. Others resamplers like bicubic are better in some cases but should not be used unless the (advanced) user explicitly chooses it. Currently there is no place where this can be used.

The biggest problem for the users is that the quality of scaling is not good at PDF export - this is where Lanczos should be used ASAP.

Re, Tomaž
Comment 10 Tomaž Vajngerl 2012-10-19 10:27:39 UTC
> @Tomaž: Thanks for improving the bitmap resampling.
> At first I wondered why you reimplemented the convolution but then I looked
> at Bitmap::ImplConvolute3 in vcl/source/gdi/bitmap4.cxx an saw why.  Maybe
> we can replace it with your code.
In LO I replaced Blur filter with the same separable convolution code but I don't think you can replace all convolution filters as all are not separable. 

> Two remarks:
> 
> 1. At about line 25 of your patch there is a line
> +	    else if( BMP_SCALE_LANCZOS == nScaleFlag )
> that exists twice (the copy is two lines down).
> 
> Remove the first to activate the Lanczos resampling.

OK

> 2. In ImplScaleConvolution you are using an separable kernel.  If I
> understand that method correctly then ImplConvolutionPass is used to do a
> horizontal application of the two one-dimensional kernels.  For this to work
> the image has to be transposed twice.  Either I am not understanding all
> this correctly or I fail to see where the transposition takes places.  Can
> you explain what I am missing?

ImplCalculateContributions always writes pixels to target image as if it is transposed. The key thing is in pWriteAcc->SetPixel( x, y, aResultColor ); 
SetPixel definition uses y (height) as the first parameter any x (width) as the second parameter! (this fact has bitten me a couple of times during development as it is counter intuitive)

The second key thing is how you create intermediate bitmap : 
first pass - aNewBitmap = Bitmap( Size( nHeight, nNewWidth ), 24);  - height and width are reversed
second pass -  aNewBitmap = Bitmap( Size( nNewWidth, nNewHeight ), 24);

With this you can have just one ConvolutionPass method instead two similar ConvolutionPassHorizontal and ConvolutionPassVertical but it is a harder to understand how it works.

Re, Tomaž
Comment 11 Andre 2012-10-19 11:16:24 UTC
(In reply to comment #10)
> ImplCalculateContributions always writes pixels to target image as if it is
> transposed.

Ah, that was the detail that I was missing.  Thanks for pointing it out.
Comment 12 Pedro Giffuni 2012-10-19 20:15:26 UTC
Created attachment 79795 [details]
Lanczos3 resampling for Bitmaps : dup line fix

I fixed the dup line that Andre reported, however ...
Once upon a time this code used to build.

Now this looks familiar:

[ build CXX ] vcl/source/gdi/bitmap
R=/usr/ports/editors/openoffice-3-devel/work/ooo && S=$R/main && O=$S/solver/350/unxfbsdx.pro && W=$O/workdir &&  mkdir -p $W/CxxObject/vcl/source/gdi/ && mkdir -p $W/Dep/CxxObject/vcl/source/gdi/ && c++ -DCPPU_ENV=gcc3 -DCUI -DENABLE_GRAPHITE -DENABLE_GTK -DENABLE_LAYOUT=0 -DENABLE_LAYOUT_EXPERIMENTAL=0 -DFREEBSD -DGCC -DGXX_INCLUDE_PATH=/usr/include/c++/4.2 -DHAVE_GCC_VISIBILITY_FEATURE -DNDEBUG -DOPTIMIZE -DOSL_DEBUG_LEVEL=0 -DPRODUCT -DPRODUCT_FULL -DSOLAR_JAVA -DSTLPORT_VERSION=400 -DSUPD=350 -DUNIX -DUNX -DVCL -DX86_64 -D_PTHREADS -D_REENTRANT   -DVCL_DLLIMPLEMENTATION -DCUI_DLL_NAME=\"libcui.so\" -DDLLPOSTFIX=  -DSAL_DLLPREFIX=\"lib\" -DSAL_DLLPOSTFIX=\"\" -D_XSALSET_LIBNAME=\"libspa.so\"  -DENABLE_FONTCONFIG  -DENABLE_CUPS  -DENABLE_GRAPHITE  -Wall -Wendif-labels -Wextra -Wno-ctor-dtor-privacy -Wno-non-virtual-dtor -Wshadow -fPIC -fmessage-length=0 -fno-common -fno-strict-aliasing -fno-use-cxa-atexit -fvisibility-inlines-hidden -fvisibility=hidden -pipe    -DEXCEPTIONS_ON -fexceptions -fno-enforce-eh-
specs  -Os -c $S/vcl/source/gdi/bitmap.cxx -o $W/CxxObject/vcl/source/gdi/bitmap.o -MMD -MT $W/CxxObject/vcl/source/gdi/bitmap.o -MF $W/Dep/CxxObject/vcl/source/gdi/bitmap.d -I$S/vcl/source/gdi/ -I$O/inc/stl -I$O/inc/stl -I$O/inc/external -I$O/inc -I$S/solenv/unxfbsdx/inc -I$S/solenv/inc -I$S/res -I$S/solenv/inc/Xp31 -I/usr/local/openjdk6/include -I/usr/local/openjdk6/include/freebsd -I/usr/local/openjdk6/include/bsd -I/usr/local/openjdk6/include/linux -I/usr/local/openjdk6/include/native_threads/include -I/usr/local/include -I$S/vcl/inc -I$S/vcl/inc/pch -I$S/solenv/inc -I$O/inc/offuh -I$O/inc/stl -I$O/inc -I/usr/local/include/freetype2 -I/usr/local/include  
[ build CXX ] vcl/source/gdi/bitmapex
/usr/ports/editors/openoffice-3-devel/work/ooo/main/vcl/source/gdi/bitmap3.cxx: In member function 'bool Bitmap::ImplConvolutionPass(Bitmap&, int, BitmapReadAccess*, int, double*, int*, int*)':
/usr/ports/editors/openoffice-3-devel/work/ooo/main/vcl/source/gdi/bitmap3.cxx:1402: error: no matching function for call to 'BitmapReadAccess::GetPaletteColor(BitmapColor&)'
/usr/ports/editors/openoffice-3-devel/work/ooo/main/solver/350/unxfbsdx.pro/inc/vcl/bmpacc.hxx:426: note: candidates are: const BitmapColor& BitmapReadAccess::GetPaletteColor(sal_uInt16) const
gmake: *** [/usr/ports/editors/openoffice-3-devel/work/ooo/main/solver/350/unxfbsdx.pro/workdir/CxxObject/vcl/source/gdi/bitmap3.o] Error 1
gmake: *** Waiting for unfinished jobs....
dmake:  Error code 2, while making 'all'
Comment 13 Pedro Giffuni 2012-10-19 20:19:47 UTC
@Armin ... looks definitely like the code wants you :).

I just wanted to note that the last time I used products from Adobe, they seemed to support bicubic sampling.
Comment 14 Clarence GUO 2012-10-22 07:21:37 UTC
I have a question on flag BMP_SCALE_BICUBIC, I haven't found a caller to call Bitmap::Scale with this scale flag in the patch. Then how does this flag works?

As SCALE_SUPER from Symphony should be default and BMP_SCALE_BICUBIC is useful when export PDF, can we set additioal flag to let vcl know now is in PDF exporting, then vcl will know BMP_SCALE_BICUBIC should be used?
Comment 15 Armin Le Grand 2012-10-22 08:29:40 UTC
ALG@Pedro: Okay, I'll take a look.
ALG@Clarence: It's not used currently; part of this task will be to find the correct places and adapt them. I'll see...
Comment 16 Armin Le Grand 2012-10-22 08:30:03 UTC
ALG: Taking over...
Comment 17 Tomaž Vajngerl 2012-10-22 08:43:01 UTC
(In reply to comment #14)
> I have a question on flag BMP_SCALE_BICUBIC, I haven't found a caller to
> call Bitmap::Scale with this scale flag in the patch. Then how does this
> flag works?

bitmap.Scale( Size(width, height), BMP_SCALE_BICUBIC);

> As SCALE_SUPER from Symphony should be default and BMP_SCALE_BICUBIC is
> useful when export PDF, can we set additioal flag to let vcl know now is in
> PDF exporting, then vcl will know BMP_SCALE_BICUBIC should be used?

Um.. why should bitmap have to know in what context it is used? PDF export should do the right thing.

Also I don't recommend BMP_SCALE_BICUBIC but BMP_SCALE_LANCZOS for all places where high (perceptual) quality is needed.

(In reply to comment #15)
> ALG@Clarence: It's not used currently; part of this task will be to find the
> correct places and adapt them. I'll see...

For PDF export: http://svn.services.openoffice.org/opengrok/xref/Current%20(trunk)/vcl/source/gdi/pdfwriter_impl2.cxx line 141
Comment 18 Armin Le Grand 2012-10-22 15:24:52 UTC
ALG: Hi Tomaž, thanks for the info, but it's not just these cases. Of course it is necessary to separate model data changes (use high quality) and pure visualisation (temporary, speed over quality). There are more places; have you ever looked at the print preview...?

So.. what *are* the best candidates for these?

Model change: BMP_SCALE_LANCZOS
Visualisation: SCALE_SUPER

Thanks for the hints!
Comment 19 Tomaž Vajngerl 2012-10-23 09:10:21 UTC
(In reply to comment #18)
> ALG: Hi Tomaž, thanks for the info, but it's not just these cases. Of course
> it is necessary to separate model data changes (use high quality) and pure
> visualisation (temporary, speed over quality). There are more places; have
> you ever looked at the print preview...?
> 
> So.. what *are* the best candidates for these?
> 
> Model change: BMP_SCALE_LANCZOS
> Visualisation: SCALE_SUPER
> 
> Thanks for the hints!

Sorry, I don't know the cases where it makes sense to use SCALE_LANCZOS (I have implemented this mainly for PDF Export, where this problem was most noticeable for users). The best is to go through all users of Bitmap::Scale and decide depending on the context. If unsure, use SCALE_LANCZOS. I don't think there are many places where the change would cause noticeable performance degradation.

It may also make sense not to use BMP_SCALE_LANCZOS flag directly but an alias like BMP_SCALE_BEST (which is also used in LO, but the code was not mine). This would allow to easily change the resampler for "Best quality usage" if a better one will be implemented in the future. 

Just for the info - scaling for visualization of bitmaps in documents, scale/crop/rotate onepass implementation in svtools - grfmgr2.cxx is used and not Bitmap::Scale. So even if you change all the usage of Bitmap::Scale, the bitmaps will still look like crap when scaling factor < 0.5 is used. 

Regards, Tomaž
Comment 20 Armin Le Grand 2012-10-29 12:37:34 UTC
ALG: I have adapted BMP_SCALE_SUPER from symphony code now. For all-case hard test I added a mechanism to check these new scalers by setting them as default scaler for the Bitmap::Scale method in debug mode. I made some changes to adapt to critical cases.

Also added modes BMP_SCALE_BESTQUALITY which will fall back to BMP_SCALE_LANCZOS in the future. Also added BMP_SCALE_FASTESTINTERPOLATE to have a good-compromize default between good quality and good speed; I plan to map this to the default for Bitmap::Scale (currently is BMP_SCALE_FAST) and map it to BMP_SCALE_SUPER.

Also did some bigger reworks for the convolution scaler of this patch.
- Added reacting on negative scaling which means mirroring in X and/or Y
- Added detection of hor/ver scale at all
- Due to that, splitted into two helpers for Hor and Ver handling; the testing showed that there are many cases where a bitmap is scaled only in one direction. With the original added two-pass and X/Y exchange trick this was not optimizable (both passes had to be made), thus the split.
- Added code to decide which (Hor or Ver) to do first, taking the area of the in-between bitmap as criteria (the smaller the better)
- Extended to not only work with palette bitmaps as source (using GetPaletteColor), but also as target; this will preserve the 8bit depths of e.g. mask bitmaps which will be also scaled when part of BitmapEx sources.

Doing some more low-level tests...
Comment 21 Armin Le Grand 2012-10-29 13:33:30 UTC
ALG: Added code for For PDF export, also exchanged many old defaults from BMP_SCALE_FAST to BMP_SCALE_FASTESTINTERPOLATE.

Yes, the GraphicManager is a problem - noone really knows it well and it's not even used a lot nowadays (primitives may choose another way for painting anyways). I'll check possibilities there. Main thing there is that we need something like

Bitmap(Ex).Transform(const BitmapEx& rSource, const basegfx::B2DHomMatrix& rTransform)

for freely transformed bitmaps, which you may find in drawinglayer/source/processor2d/vclhelperbitmaptransform in it's current form as impTransformBitmapEx. It has smoothing, but just uses the neighbour pixels. Maybe this can be done more common and intelligent, I'll have a look, too.
Comment 22 Armin Le Grand 2012-10-29 15:53:13 UTC
ALG: Just found out that some of the Impl* methods used from Bitmap::Scale always return a 24bit result; that's bad since e.g. for BitmapEx::Scale the Mask (which internally is also a Bitmap) may be 24bit depth suddenly which is not good for masks. Thus, all Impl* scaling methods do also have to preserve the bit depth of the source. Checking and adapting methods accordingly...
Comment 23 Armin Le Grand 2012-10-29 17:11:22 UTC
ALG: Okay, adapted and pretty sure that it is safe now, no more asserts to be seen in various scenarios. Checked PDF export, seems to work as intended when reduce resolution is used.
Comment 24 SVN Robot 2012-10-29 17:20:49 UTC
"alg" committed SVN revision 1403434 into trunk:
#121233# Added bitmap scaling methods BMP_SCALE_SUPER (from symphony), BMP_SC...
Comment 25 Armin Le Grand 2012-10-29 17:28:30 UTC
ALG: Okay, done.
Sorry, the svn commit did ignore my 'Patch by' and other inputs, so I add them here:

Patch by: Tomaž Vajngerl
Review by: alg

If someone knows how to add this to the comment of the svn commit r1403434, please feel free to do so, I've no idea...
Comment 26 Armin Le Grand 2012-10-29 17:29:05 UTC
ALG: Set to fixed
Comment 27 Tomaž Vajngerl 2012-10-29 22:29:14 UTC
Wow this is great! I am really impressed with additions to the code.

> - Due to that, splitted into two helpers for Hor and Ver handling; the
> testing showed that there are many cases where a bitmap is scaled only in
> one direction. With the original added two-pass and X/Y exchange trick this
> was not optimizable (both passes had to be made), thus the split.
Yes this makes sense. I did once split to Hor and Ver also for this reason but the scaling did not work correctly afterwards and I reverted the changes.

> Yes, the GraphicManager is a problem - noone really knows it well and it's
> not even used a lot nowadays (primitives may choose another way for painting
> anyways). I'll check possibilities there. Main thing there is that we need
> something like
> 
> Bitmap(Ex).Transform(const BitmapEx& rSource, const basegfx::B2DHomMatrix&
> rTransform)
> 
> for freely transformed bitmaps, which you may find in
> drawinglayer/source/processor2d/vclhelperbitmaptransform in it's current
> form as impTransformBitmapEx. It has smoothing, but just uses the neighbour
> pixels. Maybe this can be done more common and intelligent, I'll have a
> look, too.

Well for LO I have enhanced that scaler to use "averaging" for scale factors < 0.6 (similar to how the scale super works)... otherwise normal bilinear scaling is used which is good enough for other scaling factors. At scaling factors < 0.6 you have to make one pixel from a matrix of pixels and the stupidest thing I could think of is to average them and it worked good and fast enough. I can also release this code under Apache license if you find any value for this.
Comment 28 Armin Le Grand 2012-10-30 11:45:09 UTC
ALG: Optimized one more case where an unnecessary in-between reduction to 8bit could happen in ImplScaleInterpolate, corrected an error for smoothing with own renderer (impTransformBitmap) for 8bit graphics, added AdaptBitCount to bitmap interface. Looking for scales done for GraphicManager paints...
Comment 29 Armin Le Grand 2012-10-30 11:50:33 UTC
ALG: Ih Tomaž, thanks for starting this at all :-) Yes, it's one area where improvements are needed, but as always -there's always something more urgent...
For the code: Thanks for the offer, sure I'm interested (I can guess what you talk about). Even more useful would be to have what I already mentioned (and use for primitives, see drawinglayer module, look for impTransformBitmap).
It takes a dest size (evtl. cropped), a soure bitmap and a homogen transformation which contains the transformation from the target pixel coordinates (0,0, size) to bitmap coordinates on the source bitmap. I'm thinking about moving it to vcl for broader usage.
You may look at 'bForceUseOfOwnTransformer' in modle drawinglayer to use it temporarily...
Comment 30 SVN Robot 2012-10-30 12:03:03 UTC
"alg" committed SVN revision 1403676 into trunk:
#121233# some slight corrections/enhancements