Deblocking filter for JPEG/digital video

Thanks Bill, that would be interesting to see. I don't have PSP myself.

I know that various image editing programs have plugins available that
allow deblocking based on user interaction and tunable parameters. I am
mainly seeking comparisons with deblocking filters that do not require
this sort of fine-tuning, as they are not suitable for video
applications. The Pegasus decompressor falls into this category,
although I am trying to figure out why their two products are giving
different results (see above discussion with Jack). But I'd still be
very interested to see any comparisons, whether user input is required
or not, for reference purposes.

On the demo page I posted comparisons of the same image across a wide
range of compression ratios, because it is just as important that the
algorithm not degrade high-quality images as it is that it deblock more
highly compressed ones.

Thanks in advance for any comparisons you can provide.

John

Hi M,

Understood about the ringing -- my goal was to removing the blocking,
not the ringing, which is an artifact of any Fourier technique because
of the Gibbs phenomenon. However, having said that, I am also looking
at using some similar tricks to work on the ringing problem too.
(That's for another day.)

I understand that it is difficult to create an objective test, because
the blocking phenomenon is objectionable, visually, because the
discontinuities are correlated into edges, and the human visual system
is very good at detecting edges. As you note, a simple measure like
SNR, that does not take into account this coherence effect, is not very
useful.

Of course, I do have an objective way to quantify the average degree of
blocking artifact across an image, because the UnBlock algorithm uses
it, and then removes it. :) But I can hardly apply this metric to
images processed by other algorithms, because UnBlock will always come
out as being perfect, which is hardly a useful comparison at all.

I guess the answer you are giving me is that, no, there are no agreed
objective tests of deblocking efficiency.

I would be interested in knowing of the other deblocking algorithms
that you have seen and implemented, if they are publicly demonstrated,
anyway. I know that Pegasus have boasted the best decompressors over
the years, and to their credit they have put their software out there
to be put to the test. I guess I am looking to test against algorithms
that have been implemented and can be applied by anyone to any image
(even if the details of how they work have not been released), rather
than academic suggestions that have only been tested by the authors on
their own selected images.

Thanks again for your comments,
John

John Costella wrote:

> All but one of the papers on that site were no longer there, but the
> one that was had a couple of sample grayscale results. They did look
> quite good at low resolution, although on magnification remnant
> blocking artifacts remained.

It does leaves some patchiness on what should be smooth gradients, most 
post processing filters don't completely reconstruct linear gradients 
where possible ... it can prevent some blurring, but overall I would 
call it a fault in their design.

All in all I still think it looks better though, especially on something 
like Lena. Your algorithm has the tendency to cause stair casing on hard 
edges. It also does leave some blocking in place, mostly along vertical 
lines for some reason.

I also think the algorithm is quite elegant, slow but straightforward 
and derived from first principles rather than ad-hoc like most post 
processing filters.

Marco

John Costella wrote:
> Hi M,
> 
> Understood about the ringing -- my goal was to removing the blocking,
> not the ringing, which is an artifact of any Fourier technique because
> of the Gibbs phenomenon. However, having said that, I am also looking
> at using some similar tricks to work on the ringing problem too.
> (That's for another day.)
> 
> I understand that it is difficult to create an objective test, because
> the blocking phenomenon is objectionable, visually, because the
> discontinuities are correlated into edges, and the human visual system
> is very good at detecting edges. As you note, a simple measure like
> SNR, that does not take into account this coherence effect, is not very
> useful.
> 
> Of course, I do have an objective way to quantify the average degree of
> blocking artifact across an image, because the UnBlock algorithm uses
> it, and then removes it. :) But I can hardly apply this metric to
> images processed by other algorithms, because UnBlock will always come
> out as being perfect, which is hardly a useful comparison at all.
> 
> I guess the answer you are giving me is that, no, there are no agreed
> objective tests of deblocking efficiency.
> 
> I would be interested in knowing of the other deblocking algorithms
> that you have seen and implemented, if they are publicly demonstrated,
> anyway. I know that Pegasus have boasted the best decompressors over
> the years, and to their credit they have put their software out there
> to be put to the test. I guess I am looking to test against algorithms
> that have been implemented and can be applied by anyone to any image
> (even if the details of how they work have not been released), rather
> than academic suggestions that have only been tested by the authors on
> their own selected images.
> 
> Thanks again for your comments,
> John
> 
Granted that PSNR may not be the best objective measure, I would like to 
see figures about achievable compression ratios for same quality, ie 
JPEGcompress+JPEGdecompress vs. compress+decompress+unblock.


-- 
Michel Bardiaux
R&D Director
T +32 [0] 2 790 29 41
F +32 [0] 2 790 29 02
E mailto:mbardiaux@mediaxim.be

Mediaxim NV/SA
Vorstlaan 191 Boulevard du Souverain
Brussel 1160 Bruxelles
http://www.mediaxim.com/

John,

Yes, I checked and the JPEG Wizard product is a few code versions back.  It 
is scheduled for an update later this year.  Sorry I mislead you there.  It 
does show lossless JPEG crop, lossless JPEG hue/tint/brighten/contrast and 
'lossless' JPEG recompression however.  The Minerva code, with the 'enhanced 
decompression' flag set is close to our latest code however, and you are to 
be applauded for getting better results than this, as it is pretty doggone 
good.  JPEG is less and less a focus here at Pegasus, for obvious reasons 
like JPEG 2000, so it has been a while since we looked at JPEG decompression 
and deblocking.  However, some time ago we looked around and did find some 
superior deblocking schemes, in some cases, than our own, but in our 
judgment they were too computationally expensive to be commercially viable. 
If speed is not an issue then JPEG 2000 will provide superior compression 
results with less artifacts everytime anyway.  So, all the computations in 
the world is still not going to produce wavelet quality to DCT compressed 
images at some threshold of compression ratio.  Our deblocking is meant to 
squeeze out a few percent of quality when it matters (printing) with as 
little speed impact as possible.

None of this should be taken to minimize your work or its importance.  This 
is just where Pegasus is in its priorities at the moment.  Artifact removal 
is very important research, as it results in enabling higher compression 
ratios if needed.  Continued work in this area would be applicable to 
digital video, as you said (if made computationally acceptable), or applied 
to wavelet compressed images perhaps.  Your results seem promising and 
certainly better than ours in some/most/all? cases.  In extreme compression 
cases your edges seem to blur and ours do not, but I doubt that case is also 
not of commercial interest.  Our artifacting is certainly more objectionable 
to the eye and your PSNR is slightly better in the couple of images we 
tried.  Even with our in house smoothing algorithm, not released, your 
results seem slightly better.  So, seems to be a nice bit of science.

This is why we try to stay a very open and transparent image technology 
company.  It is easy to test our algorithms for yourself, and hopefully 
glean ideas and improvements to our work.  (The absolute latest code would 
be found in our PICTools RapidVUE development kit with the command source 
code sample.)  And when you have a test program the members of this group 
can test we would enjoy seeing the computational effort you are applying to 
achieve these results.  I am sure it would be interesting to understand the 
algorithmic complexity variance between your method and ours.  Perhaps 
Pegasus can find a commercial use for your work?

Good luck,
jack
--
http://www.jpg.com/ - Pegasus - The BETTER JPEG People!
--

"John Costella" <jpcostella@hotmail.com> wrote in message 
news:1138147954.389198.208280@o13g2000cwo.googlegroups.com...
> Hi Jack,
>
> My comparisons were based on the Minerva program, which I had
> downloaded from pegasusimaging.com. You are right: the About box lists
> it as Copyright 1996-2005, Version 1.0.0.155 for PIC version 2.00
> libraries, and the page http://www.pegasusimaging.com/jpegfeatures.htm
> refers to it as your current "Pegasus imaging viewer". Apologies for
> being cautious as to whether it represented your current technology.
>
> I have now downloaded JPEG Wizard 2, but it seems to do a much worse
> job at deblocking than Minerva. Indeed, it only seems to apply
> deblocking to very highly compressed images, and only then in selected
> areas. I cannot find any option to turn on deblocking for less heavily
> compressed images. Am I missing something?
>
> I do not see the chrominance smoothing option either, in either Minerva
> or JPEG Wizard 2; could you guide me to it?
>
> In any case, the results from Minerva don't seem to be optimal. I have
> compared them for the same test images as on the UnBlock demo page and
> you can see from a side-by-side comparison that they fall short at all
> compression ratios:
>
> http://www.assassinationscience.com/johncostella/unblock/pegasus-v-unblock.html
>
> I agree that the Pegasus decompressor does not introduce blurring or
> distortion in its deblocking, but neither does UnBlock, and neither, I
> assume, do other deblocking filters available.
>
> I will continue to play with JPEG Wizard 2, but so far I am hitting a
> brick wall with it.
>
> Thanks for your help,
> John
> 

In comp.compression John Costella <jpcostella@hotmail.com> wrote:
>
> Thanks Bill, that would be interesting to see. I don't have PSP myself.
>
> I know that various image editing programs have plugins available that
> allow deblocking based on user interaction and tunable parameters.

PSP is one of them.  I used defaults: Normal Strength, Sharpness 50.
The documentation says nothing about these parameters, nor did I find
anything on the web recommending different settings.

Here are the comparisons, offered without comment.  The "ski" image is
from an old Fuji digicam.  The "twins" image is R rated nudes, saved from
e-mail due to incredibly bad JPEG encoding, somewhat corrected here.

 http://cacreeks.com/unblock/

John Costella wrote:
> Hi M,
>
> Understood about the ringing -- my goal was to removing the blocking,
> not the ringing, which is an artifact of any Fourier technique because
> of the Gibbs phenomenon. However, having said that, I am also looking
> at using some similar tricks to work on the ringing problem too.
> (That's for another day.)
>
> I understand that it is difficult to create an objective test, because
> the blocking phenomenon is objectionable, visually, because the
> discontinuities are correlated into edges, and the human visual system
> is very good at detecting edges. As you note, a simple measure like
> SNR, that does not take into account this coherence effect, is not very
> useful.
>
> Of course, I do have an objective way to quantify the average degree of
> blocking artifact across an image, because the UnBlock algorithm uses
> it, and then removes it. :) But I can hardly apply this metric to
> images processed by other algorithms, because UnBlock will always come
> out as being perfect, which is hardly a useful comparison at all.
>
> I guess the answer you are giving me is that, no, there are no agreed
> objective tests of deblocking efficiency.
>
> I would be interested in knowing of the other deblocking algorithms
> that you have seen and implemented, if they are publicly demonstrated,
> anyway. I know that Pegasus have boasted the best decompressors over
> the years, and to their credit they have put their software out there
> to be put to the test. I guess I am looking to test against algorithms
> that have been implemented and can be applied by anyone to any image
> (even if the details of how they work have not been released), rather
> than academic suggestions that have only been tested by the authors on
> their own selected images.
>
> Thanks again for your comments,
> John

I'll email you the one's I implemented, which were all from academic
papers.

Cheers! --M

Hi Marco,

I'd appreciate it if you could post some images somewhere (or send them
to me) showing examples of the staircasing and vertical lines.

UnBlock does not affect a linear gradient across a boundary (nor a
parabolic one, for that matter). I'm not sure if you are saying that
the other algorithm erroneously modifies such gradients, or whether you
are talking about something more subtle.

The UnBlock algorithm treats vertical and horizontal lines equally, but
of course it analyzes the image before correcting it, so if there are
many (true) vertical-line discontinuities in the your image (i.e. in
the interiors of the blocks), it won't be as aggressive on the vertical
block boundaries. I'd be interested to see your examples.

Thanks again
John

No worries, Jack. I applaud the way that Pegasus has put its claims out
there for all to test, and your honesty in telling me that UnBlock
out-performs your new patented but unreleased deblocking method
(something I would have had no way of testing if you hadn't told me)
says volumes about your company's integrity. I'm impressed.

In terms of computational speed, the UnBlock algorithm is very fast.
There are no transcendental functions, divisions, or multiplications
involved, only integer additions and subtractions, and bitwise
right-shifts. Only blocks bordering a boundary are used in its analysis
and correction (except for a very fast global process at the end of the
analysis pass). As I noted in an earlier posting, the deblocking
analysis and correction takes only about twice as long per pixel as the
colorspace conversion and chrominance upsampling, which is also done as
fast as possible (well, as fast as I could think of), without the use
of multiplications or divisions, similarly to the way the IJG code does
it. The deblocking corrections are done in-place (or optionally to
another image, without altering the original), with look-up tables and
row buffers taking only a nominal number of kilobytes.

The code is currently written in ANSI C, makes no assumptions about
architecture, and pixel access is done by generalized macros that can
be changed in the header file. (The Windows app on my website uses
32-bit COLORREF structures, but it can be changed via a #define switch
to handle BGRBGR triples, etc.) The code itself is not too complex (the
object file is 25 kB in VC6). Just some intelligent mathematics, as I
am sure is also the case with much of Pegasus's code. :)

I am sure that an assembler version for a specific architecture and
pixel structure would squeeze out even more speed, because then
register and pointer management can be optimized, etc. At the moment I
haven't even optmized by unrolling the grayscale and color routines
into different functions; there are grayscale/color switches all over
the place. Even more cycles could be saved if the results of the
analysis phase were saved in an image-sized buffer, because currently
they are discarded and then recomputed all over again in the correction
pass, although the speed gain would probably only be of the order of
20-30% (at the expense of an extra image-sized memory buffer).

Right now I haven't decided what I'm going to do with the algorithm,
the code, and the short scientific paper that describes and derives the
relevant formulas. I'd be happy to hear from you privately (initially
email me jpcostella@hotmail.com) if you think that it's something that
has a degree of commercial potential, however minor that may now be. (I
understand JPEG is now a mature technology, and no longer at the edge
of research, but the algorithm is fast enough to play a role in video
applications.)

As far as JPEG 2000 is concerned, I don't know enough about it yet to
comment. I have some ideas (in progress) as to how some of the same
tricks used in UnBlock (plus a couple more) could be used, together
with plain old JPEG, to address the fundamental weaknesses of a DCT
approach like JPEG without needing to go to wavelet methods. Whether it
pans out or not, I don't know; like UnBlock, I'll suck it and see. :)

Thanks again,
John

Thanks for those, Bill. The two images you've tested seem to suffer
much worse from ringing artifacts than blocking, and so it's difficult
to come to any conclusions. Definitely, for the twins image, the
maximum PSP setting is doing a good job at removing a lot of the
ringing -- but that's not what UnBlock addresses.

I'll be addressing the ringing problem separately, so I'll defer a more
complete discussion of it to then.

If you have the chance, would you be able to process the following test
images using PSP?

http://www.assassinationscience.com/johncostella/unblock/before000.jpg
http://www.assassinationscience.com/johncostella/unblock/before005.jpg
http://www.assassinationscience.com/johncostella/unblock/before010.jpg
http://www.assassinationscience.com/johncostella/unblock/before020.jpg

That would give me something definite to compare some of the existing
results against.

Thanks again,
John