Closed Bug 75077 Opened 23 years ago Closed 9 years ago

Interlaced PNGs should be displayed with interpolation

Categories

(Core :: Graphics: ImageLib, enhancement)

Product:
Core
Component:
Graphics: ImageLib
Type:
enhancement
Priority:
Not set
Severity:
normal

Tracking

()

Status:
VERIFIED FIXED
Milestone:
Future
Tracking Flags:
Tracking Status
firefox45 --- fixed

People

(Reporter: karl, Assigned: glennrp+bmo)

References

(
URL
)

Details

(Whiteboard: [imglib])

Attachments

(7 files, 9 obsolete files)

grammie.png (noninterlaced RGBA PNG)
709.02 KB, image/png
Details
grammie_i.png (interlaced RGBA PNG)
831.35 KB, image/png
Details
grammie.html
730 bytes, text/html
Details
grammie_ii.gif (Interlaced GIF)
382.54 KB, image/gif
Details
grammie_ii.png (Interlaced Indexed PNG)
356.95 KB, image/png
Details
grammie_gif_vs_png.html (Interlaced Indexed PNG and GIF)
732 bytes, text/html
Details
v06-75077-interpolate-interlaced-pngs
11.69 KB, patch
seth
: review+
Details | Diff | Splinter Review 
This bug is spawned from bug #67674.

PNG images can be written as 7-pass interlaced images. This means that the whole
image is displayed even though only 1/64 of it is downloaded, and the quality is
gradually improved as more data (1/32, 1/16, 1/8 &c.) gets downloaded.

You can find a frame-by-frame demonstration of this at
<URL:http://www.its.caltech.edu/~stl/png.html>. You can find a real example at
the the URL referenced in this bug.

As you can also see (on the mentioned page), that web browsers are free to use
interpolation to improve the quality of partially downloaded images. This looks
much nicer, and makes it easier to see what the image is about.

I propose that we use bicubic interpolation to display interlaced PNGs.
yes  this "bug" should be fixed
Whiteboard: [imglib]
*** Bug 75941 has been marked as a duplicate of this bug. ***
Target Milestone: --- → mozilla1.0
Blocks: 66962
Bugs targeted at mozilla1.0 without the mozilla1.0 keyword moved to mozilla1.0.1 
(you can query for this string to delete spam or retrieve the list of bugs I've 
moved)
Target Milestone: mozilla1.0 → mozilla1.0.1
Blocks: 98971
On some machines with slower CPUs, large bicubic interpolated images could
pose a performance problem with the large number of triggered redraws.
I vote for bilinear, as in bug 98971.  If you want to get started on this
bug, bug 98971 has an implementation of bilinear scaling.

Is bug 76703 related?

i think i deped these two wrong
No longer blocks: 98971
Depends on: 98971
I think this would be best done inside libpng, and shouldn't be that difficult.
I've already done similar coding to handle the MNG MAGN chunk in ImageMagick,
and to create Figure 1-4 of PNG: The Definitive Guide.  But bug 128502 stops
me from working on it now.

Glenn
I think that bicubic is the ideal solution on current, speedy machines. A
greater level of perceived detail earlier in the image loading process would
give users the impression that Mozilla is "faster" with images. However, we do
still have to accommodate older, slower machines. It would be possible to have
more than one interpolation scheme as a option, controlled by a hidden pref, but
that would bloat the app (especially since it's most likely that the
interpolation would be chosen once for the processor speed, and never changed
again--leaving the other options just taking up space). Maybe a compile-time
option? Heck, if the interpolation code was somehow compiled as a shared
library, the choice of interpolation scheme could be put off until
installation--the installer could just install the appropriate library by asking
the user, or even by automagically detecting the processor speed.

Shouldn't this be futured? It looks kind of silly targeted at Mozilla 1.0.1,
when 1.4b is already out...
retargeting
Target Milestone: mozilla1.0.1 → Future
Why not using a very low priority thread that does the interpolation?
I think using bicubic is the minimum interpolation that should be done
(sinc interpolation is overkill ;-)
(http://home.no.net/dmaurer/~dersch/interpolator/interpolator.html)
but having an option to allow the user to set a worse interpolation
or maybe Mozilla deciding based on /proc/cpuinfo (Linux) is also a good idea.
Linear interpolation is simpler and would also be adequate.
Hardware -> all.

Glenn
Hardware: PC → All
Re: comment #1:  The demo has moved to http://nuwen.net/png.shtml
Alias: bicubic
Is work still going on on this? All deps are fixed, but PNGs are still nearest-neighbour!
(In reply to comment #12)
> Is work still going on on this? All deps are fixed, but PNGs are still
> nearest-neighbour!
> 

see bug 98971 comment 140 and bug 372462
Assignee: pavlov → nobody
QA Contact: tpreston → imagelib
Bicubic is considered baseline for todays machines....it's 9 years after this bug was first filed.

This should be fixed ASAP.  PNG may have 7 levels, but I *regularly* use 5 levels for jpg.  Same issues apply (though the problem may be worse for png's).

Dynamic runtime resizing should be switchable at user's request (config option).

Allow defaults for bicubic, bilinear or nearest neighbor.  NN might still be useful/needed for portable/handheld platforms.

But for people running on 64-bit w/4 CPU's, I'd go so far as to add you should have 4th mode of "auto sharper/smoother" depending on whether it is a reduction or an enlargement (respectively).  FF does a horrible job at enlarging and I've seen other SW enlarging -- and FF could do much better.

FF is falling behind IE..sad to say.  They have bicubic, 64-bit and multi-threading.  Supposedly Opera just added full SVG support, as well. FF has definitely lost lead in being state-of-the-art in all areas (title it once held, hands down).  *sigh*
Assignee: nobody → glennrp+bmo
Depends on: 1187569
This will be much simpler to accomplish when the patch for bug #1187569 lands, because the PNG decoder will have easier access to each interlacing pass.
See comment #10.  Linear interpolation should be adequate for this purpose.  The image is only displayed fleetingly, and the difference between linear and bicubic interpolation is imperceptable in the demo mentioned in comment #11 and other images I've looked at.  I'll work on linear interpolation for now, but that doesn't preclude follow-on work to add bicubic.
Alias: bicubic
Summary: Interlaced PNGs should be displayed with bicubic interpolation → Interlaced PNGs should be displayed with interpolation
See this article: https://en.wikipedia.org/wiki/Bicubic_interpolation which compares nearest-neighbor versus linear interpolation versus bicubic interpolation.
As the original reporter of this bug, I agree that linear interpolation will be adequate.
Please submit to try.
Flags: needinfo?(ryanvm)
I regret only saying this after you've written some pretty complicated code, but enabling downscale-during-decode for PNGs is actually the right way to fix this. The downscaler we use for DDD is both *much* higher quality than this (it uses Lanczos resampling rather than linear interpolation) and uses SIMD on many platforms for improved performance.
Depends on: 1060609
Clearing ni? based on comment 20. Let me know if you want me to run it through Try anyway.
Flags: needinfo?(ryanvm)
Doesn't matter, thanks.  Maybe revisit after bug #1060609 lands.
Attached file grammie.html — 
Fix links
Attachment #8653567 - Attachment is obsolete: true
Update links, again.
Attachment #8653655 - Attachment is obsolete: true
Update links, again.
Attachment #8653656 - Attachment is obsolete: true
Comment on attachment 8653182 [details] [diff] [review]
v00-75077-interpolate-interlaced-pngs

The v00 patch was made obsolete by landing patches for bug #1060609
Attachment #8653182 - Attachment is obsolete: true
So Glenn, at this point is the output for interlaced PNGs good enough that we should consider this resolved? Or is there more to do?
Flags: needinfo?(glennrp+bmo)
There's more to do. The downscaling stuff doesn't address this bug (enhancement request); it does not change the appearance of the PNG passes.  But I've got to rewrite the patch now.  The attached "grammie.html" page gets delivered too fast to see the effect very well, though, so you need to throttle the download somehow.
Flags: needinfo?(glennrp+bmo)
(In reply to Glenn Randers-Pehrson from comment #34)
> There's more to do. The downscaling stuff doesn't address this bug
> (enhancement request); it does not change the appearance of the PNG passes. 
> But I've got to rewrite the patch now.  The attached "grammie.html" page
> gets delivered too fast to see the effect very well, though, so you need to
> throttle the download somehow.

OK. When you rewrite, can you put the interpolation code in a separate function? The row_callback() function is getting pretty big...
Does linear interpolation of interlaced PNG except when downscaling, when it reverts to the libpng "blocky" display of interlace passes. Moved interpolation into a separate function as Seth requested. Please do a "try" run.
Flags: needinfo?(ryanvm)
Try failed on pngsuite odd sizes test.

I visited http://schaik.com/pngsuite/pngsuite.html#sizes clicked "odd sizes" and got a crash:
https://crash-stats.mozilla.com/report/index/b6ebba45-7789-4fd5-8901-281b22150908
The crashes in the Try push have more-useful stacks.
Attachment #8657459 - Attachment is obsolete: true
Does not try to interpolate images that are too small (width or height less than 7).
Try?
Status: NEW → ASSIGNED
Flags: needinfo?(ryanvm)
Comment on attachment 8658413 [details] [diff] [review]
v02-75077-interpolate-interlaced-pngs

Try is all green except for two B2G tests that seem unrelated to this patch.  r?
Attachment #8658413 - Flags: review?(jmuizelaar)
Attachment #8658413 - Flags: feedback?(seth)
Comment on attachment 8658413 [details] [diff] [review]
v02-75077-interpolate-interlaced-pngs

Review of attachment 8658413 [details] [diff] [review]:
-----------------------------------------------------------------

This interpolation code looks slow (It looks like it does 3-4 divisions per pixel). How much time does this add to png decoding? Is it actually worth the additional decoding time for a temporarily better image? FWIW, It should be able to write this code so that it is much faster using techniques similar to skia or pixman.
Attachment #8658413 - Flags: review?(jmuizelaar) → review-
Comment on attachment 8658413 [details] [diff] [review]
v02-75077-interpolate-interlaced-pngs

I'll see about making an instrumented version and do some timings.  But the divisions are all integer divisions by powers of 2 so I expect that the compiler will optimize them into right-shifts.  In fact there are about 3 or 4 divisions per pixel, for each of six passes.  I'm marking the v02 patch obsolete for now.
Attachment #8658413 - Attachment is obsolete: true
Attachment #8658413 - Flags: feedback?(seth)
The interpolation in the v03 patch uses about 1/8 of the CPU time used by the v02 patch.  The divisions were replaced with shifts, and the odd-numbered interlace passes are skipped.  Please submit to tryserver.
Flags: needinfo?(ryanvm)
Comment on attachment 8668237 [details] [diff] [review]
v03-75077-interpolate-interlaced-pngs

Cancel v03, I uploaed the wrong file.
Attachment #8668237 - Attachment is obsolete: true
Removed several lines of code that were accidentally duplicated in the v03 patch.
Rebased.  I've been using this patch for a month on Ubuntu-14.04LTS with Nightly and have had no trouble with it.  Try?
Attachment #8668384 - Attachment is obsolete: true
Flags: needinfo?(ryanvm)
Comment on attachment 8682281 [details] [diff] [review]
v05-75077-interpolate-interlaced-pngs

Try looks OK.  This patch is about 6-8x faster than the one Jeff evaluated previously; all divisions have been replace with shift operations. r?
Flags: needinfo?(bugzmuiz)
Attachment #8682281 - Flags: review?(seth)
Comment on attachment 8682281 [details] [diff] [review]
v05-75077-interpolate-interlaced-pngs

Review of attachment 8682281 [details] [diff] [review]:
-----------------------------------------------------------------

Looks good, but needs a few tweaks. It's pretty much all style - the actual functionality looks great!

::: image/decoders/nsPNGDecoder.cpp
@@ +681,5 @@
>  
>  void
> +nsPNGDecoder::InterpolateInterlacedPNG(int pass, bool hasAlpha,
> +                                       uint32_t width, uint32_t height,
> +                                       uint8_t* imageData)

Style nit: parameter names need to start with |a|, as in |aPass|, |aHasAlpha|, etc.

@@ +688,5 @@
> +  // imageData as an array of uint8_t ARGB or XRGB pixels, optionally
> +  // premultiplied, 4 bytes per pixel. If there are leftover partial
> +  // blocks at the right edge or bottom of the image, we just use the
> +  // uninterpolated pixels that libpng gave us.
> +  

Nit: whitespace.

@@ +692,5 @@
> +  
> +  // See Bug #75077, Interpolation of interlaced PNG
> +  // See https://en.wikipedia.org/wiki/Bilinear_interpolation
> +
> +  // Note: this doesn't work when downscaling so we simply show 

Whitespace.

@@ +708,5 @@
> +  uint32_t bh = bw;
> +
> +  bool first_component = hasAlpha ? 0: 1;
> +
> +  // Reduced version of the PNG_PASS_ROW_SHIFT(pass) macro in libpng/png.h 

Whitespace.

@@ +722,5 @@
> +
> +      // Loop over component=[A,]R,G,B
> +      for (uint32_t component = first_component; component < 4; component++) {
> +
> +      uint32_t top;

The indentation is incorrect starting at this point. Everything inside the for loop needs to be indented one more level. Also, please remove the black line above |uint32_t top|, and please initialize top and bottom to 0.

@@ +730,5 @@
> +          top = *(topleft + component);
> +          bottom = *(topleft + component + (4 * bh * width));
> +          for (uint32_t j = 1; j < bh; j++) {
> +            *(topleft + component + 4 * j * width) =
> +              (((top * (bh - j) + bottom * j) >> divisor_shift) & 0xff);

Nit: please remove the unnecessary outer set of parentheses.

@@ +739,5 @@
> +        top = *(topleft + component + 4 * bw);
> +        bottom = *(topleft + component + 4 * (bw + (bh * width)));
> +        for (uint32_t j = 1; j < bh; j++) {
> +          *(topleft + component + 4 * (bw + j * width)) =
> +            (((top * (bh - j) + bottom * j) >> divisor_shift) & 0xff);

Same here re: unnecessary parentheses.

This loop is essentially the same as the previous one, right? Seems like it could be factored out into a separate function.

@@ +749,5 @@
> +          uint32_t left = *(topleft + component + 4 * j * width);
> +          uint32_t right = *(topleft + component + 4 * (bw + j * width));
> +          for (uint32_t i = 1; i < bw; i++) {
> +            *(topleft + component + 4 * (i + j * width)) =
> +              (((left * (bw - i) + right * i) >> divisor_shift) & 0xff);

Same here re: unnecessary parentheses.

It might be nice to factor this these nested loops into a separate function too.

@@ +801,5 @@
>      return;
>    }
>  
> +  bool lastRow =
> +    (row_num == static_cast<png_uint_32>(decoder->mFrameRect.height) - 1);

Same here re: unnecessary parentheses. |lastRow| can be const, right?

@@ +906,5 @@
> +      bool hasAlpha = decoder->format != SurfaceFormat::B8G8R8X8;
> +      decoder->InterpolateInterlacedPNG(pass, hasAlpha,
> +                                        static_cast<uint32_t>(width),
> +                                        decoder->mFrameRect.height,
> +                                        decoder->mImageData);

If you're going to pass in all the data that InterpolateInterlacedPNG works with, that's great, because it means that you can - and should - turn it into a static method. Or even better, just make it a static function and move it totally into the .cpp file; since it's private, there's no reason to include it in the .h file at all.

@@ +911,3 @@
>        decoder->PostFullInvalidation();
>      }
> +  } // lastRow

I don't think you need |// lastRow| here.

::: image/decoders/nsPNGDecoder.h
@@ +79,5 @@
>  
>    void PostPartialInvalidation(const IntRect& aInvalidRegion);
>    void PostFullInvalidation();
> +  void InterpolateInterlacedPNG(int pass, bool hasAlpha, uint32_t uwidth,
> +                                uint32_t uheight, uint8_t* imageData);

Style nit: update these parameter names as well.
Attachment #8682281 - Flags: review?(seth)
Made the interpolation function private
Fixed indentation
Removed trailing blanks
Removed unnecessary outer parentheses
Reduced scope of "top" and "bottom" so they don't need to be initialized to 0
Added "a" prefix to argument names
Made aHasAlpha const bool

I didn't refactor the loops into one because I thought that might introduce
extra operations into the most common case.  I can revisit that later in another bug.
Attachment #8682281 - Attachment is obsolete: true
Flags: needinfo?(bugzmuiz)
Attachment #8687583 - Flags: review?(seth)
Comment on attachment 8687583 [details] [diff] [review]
v06-75077-interpolate-interlaced-pngs

Review of attachment 8687583 [details] [diff] [review]:
-----------------------------------------------------------------

Looks good, Glenn!
Attachment #8687583 - Flags: review?(seth) → review+
Keywords: checkin-needed
https://hg.mozilla.org/mozilla-central/rev/421e725a39d2
Status: ASSIGNED → RESOLVED
Closed: 9 years ago
status-firefox45: --- → fixed
Resolution: --- → FIXED
Status: RESOLVED → VERIFIED
Depends on: 1228225
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: