Bug 688990

Summary: imagemask interpolation doesn't quite match Adobe
Product: Ghostscript Reporter: Raph Levien <raph.levien>
Component: Graphics LibraryAssignee: Peter Cherepanov <sphinx.pinastri>
Status: RESOLVED FIXED    
Severity: enhancement CC: christinedelight.top85, htl10, robin.watts, shailesh.mistry, sphinx.pinastri
Priority: P5 Keywords: bountiable
Version: master   
Hardware: All   
OS: All   
Customer: Word Size: ---
Attachments: test case for analyzing Adobe imagemask interpolation
Patch
Large interpolation test file

Description Raph Levien 2006-11-11 13:25:24 UTC
Ghostscript now implements imagemask interpolation, internally done with the
/Imscale filter, which outputs a bitmap with 4 times the horizontal and vertical
resolution of its input. However, the results don't exactly match Adobe.

The current implementation is based on a 4x4 window of source pixels, addressing
a lookup table. This gives results that are fairly close to Adobe's
implementation, but not quite. On further analysis of test images, it looks like
even a 5x5 window is not adequate to exactly predict the Adobe interpolation
results.

A Python script generating all 4x4 combinations is attached to this bug, as well
as the results from an Adobe interpreter. The current results are probably "good
enough," but if anyone can figure out the actual logic used, that would be much
appreciated.

Keep in mind that the algorithm was initially implemented on an 8 MHz 68000
family processor, to make 75 dpi MacPaint bitmap images print more smoothly on
the then brand-new Apple LaserWriter. This suggests that the actual algorithm
must be fairly simple and not too expensive in CPU or memory.
Comment 1 Raph Levien 2006-11-11 13:28:18 UTC
Created attachment 2597 [details]
test case for analyzing Adobe imagemask interpolation

imm2.py generates the test file used to render the resulting images. The four
pbm files are the pages generated, in order. Rendering is 600dpi, so each pixel
from the interpolation filter is actually rendered as a 2x2 block.
Comment 2 Dan Coby 2006-11-11 21:09:13 UTC
Raph,

What format is the file that you attached to this bug report?
Comment 3 Raph Levien 2006-11-11 21:11:30 UTC
Sorry, it's a .tar.bz2 file. I should have realized that the bug tracker strips
out the name of the file.
Comment 4 Joel R. Voss 2007-05-02 10:11:16 UTC
I am a freelance developer working on the this bug. I am working towards the 
bounty. My plan is to work in my off time in the next 1-2 weeks to finish 
this.
My code converts the output of Ghostscript to 90% correlation to the Adobe 
pbms. My code does uses the same tables as Raphs code, no more. My code runs 
in 120 ms per page (not counting i/o) and would probably do fine on a 8 MHz 
mc68k.

I will be modifying the zoom_line function in simscale.c to concur with my 
code. I will ensure that the code is not dependent on resolution. The Adobe 
pattern does not change on a lower level than 300 dpi, so my code will also 
not change the pattern at any lower level.

Comment 5 Henry Stiles 2008-02-26 11:36:30 UTC
retest and reassign.
Comment 6 Ray Johnston 2008-08-21 13:52:23 UTC
A VERY low priority issue since this is 'implementation dependent'
Comment 7 Shailesh Mistry 2011-07-19 19:36:48 UTC
Enhancement still missing in Ghostscript 9.03
Comment 8 Robin Watts 2019-09-13 17:42:35 UTC
So to recap; Adobe used to have a special scaling routine that would upscale imagemasks in the style of the MAME scalers. (https://www.scale2x.it/)

Raph came up with an approximation to Adobe's routine using a 4x4 window, and this works, and is in ghostscript to this day (for imagemasks that don't get scaled up by more than a factor of 2).

This bug exists because Raph would have liked to get an exact match rather than an approximate match.

Testing with Acrobat 9 Pro, I cannot get Acrobat to scale in this style at all any more. I suspect this is no more than a piece of historical interest at this point.

There has been no progress on this bug in 12 years, and it seems likely that any will be forthcoming soon.

So, I'm closing the bug.
Comment 9 Peter Cherepanov 2019-12-27 07:22:15 UTC
Actually, there's progress. A 5x5 window is sufficient, and the resulting logical function can be made reasonably compact. I just need to grok Ghostscript streams to post a solution. Please reopen.
Comment 10 Peter Cherepanov 2020-02-19 17:33:49 UTC
Created attachment 18874 [details]
Patch

This patch assumes that the pixels around the image are white. This is the same as  it is done now. Adobe seems to have black pixels on the right (at the end of the scan line) and white pixels elsewhere. This bug has not been reproduced.
Comment 11 Peter Cherepanov 2020-07-09 02:40:20 UTC
Created attachment 19428 [details]
Large interpolation test file
Comment 12 Robin Watts 2020-07-09 10:23:06 UTC
Fixed with Peter's patch in:

commit da755f7ee3da900a504a3265c64fb08c93a41eac
Author: Robin Watts <Robin.Watts@artifex.com>
Date:   Wed Jul 8 16:41:11 2020 +0100

    Bug 688990: Reimplementation of image mask scaling.

    Aiming for a better match to Adobe's reference implementation.

    Patch supplied by Peter Cherepanov. Many Thanks!