Compression - Patent-free JPEG?

Author

Patent-free JPEG?

Matt Mahoney

2005-02-20, 3:55 am

As you may be aware, Forgent is suing a number of companes that use
JPEG for infringing on patent 4,698,672. They have already collected
$30 million in royalties since they asserted their claim in 2002. I
believe the patent expires Oct. 27, 2006 (20 years after filing).
http://pmt.sourceforge.net/SVG-patents/jpeg.html
http://wwwcms.brookes.ac.uk/webmsc2...jpeg/patent.htm

I believe it is possible to create progressive mode JPEG files in a way
that do not infringe on the patents, and I'm looking for comments.

The patent covers the (R,S) codes used to Huffman code the AC
coefficients in all of the lossy modes, except for arithmetic coding
(which is covered by other patents and rarely used). An (R,S) code
represents a run of R zero coefficients followed by an S-bit number
representing a nonzero coefficient. For example, the code (5,2)
(0x52 in the Huffman table) means that the next 5 coefficients in
zigzag order are 0, the the following is a 2 bit number (one of -3, -2,
2, or 3). The patent claim numbers 1, 6, 13, 25, 30, 36, 38, 39, and
42 cover (with slightly different wordings) the idea of a code
representing a run of one value (not necessarily 0) followed by a
single instance of a second value. The other claims depend on these.

Progressive mode JPEG is described in Annex G of the the JPEG standard
http://www.w3.org/Graphics/JPEG/itu-t81.pdf
Scanning my computer, I find that about 5-10% of JPEG images are
already in progressive mode, so the format is widely supported, however
most of these files still infringe on the patent. To avoid
infringement, I believe it is necessary to use spectral selection with
each coefficient in a separate scan (Ss = Se). This requires 190
scans, one for the three DC components, and 63x3 for the 63 AC
coeffients x 3 colors.

The DC coeffients uses a simple Huffman code, so they do not infringe.
Now by splitting the AC coeffients into separate scans, there are only
two types of codes: (0,S), a simple Huffman code for an S-bit number,
and (R,0), a simple run length code (specifically EOBn codes for an
R-bit numbers which give the run length). Neither code is patented.

I haven't tried creating such files, so I don't know about performance
issues such as poor compression or slow rendering. Also, I suppose the
technique would only be practical for applications that create JPEGs,
not those that read them and need to be compatible with existing
images.

Comments?

-- Matt Mahoney

Jack Berlin

2005-02-22, 3:55 pm

Or you could use Pegasus JPEG which is indemnified and protected from all
patent claims....

'Free' JPEG users have paid $30 mil; Pegasus customers have been approached,
yet have paid zero. Sometimes you get what you pay for!

Cheers,
jack
--
The JPEG Wizard free web compression testing: http://www.jpegwizard.com/
http://www.jpg.com/ - Pegasus - The BETTER JPEG People!
--

"Matt Mahoney" <matmahoney@yahoo.com> wrote in message
news:1108857533.501207.319380@g14g2000cwa.googlegroups.com...
> As you may be aware, Forgent is suing a number of companes that use
> JPEG for infringing on patent 4,698,672. They have already collected
> $30 million in royalties since they asserted their claim in 2002. I
> believe the patent expires Oct. 27, 2006 (20 years after filing).
> http://pmt.sourceforge.net/SVG-patents/jpeg.html
> http://wwwcms.brookes.ac.uk/webmsc2...jpeg/patent.htm
>
> I believe it is possible to create progressive mode JPEG files in a way
> that do not infringe on the patents, and I'm looking for comments.
>
> The patent covers the (R,S) codes used to Huffman code the AC
> coefficients in all of the lossy modes, except for arithmetic coding
> (which is covered by other patents and rarely used). An (R,S) code
> represents a run of R zero coefficients followed by an S-bit number
> representing a nonzero coefficient. For example, the code (5,2)
> (0x52 in the Huffman table) means that the next 5 coefficients in
> zigzag order are 0, the the following is a 2 bit number (one of -3, -2,
> 2, or 3). The patent claim numbers 1, 6, 13, 25, 30, 36, 38, 39, and
> 42 cover (with slightly different wordings) the idea of a code
> representing a run of one value (not necessarily 0) followed by a
> single instance of a second value. The other claims depend on these.
>
> Progressive mode JPEG is described in Annex G of the the JPEG standard
> http://www.w3.org/Graphics/JPEG/itu-t81.pdf
> Scanning my computer, I find that about 5-10% of JPEG images are
> already in progressive mode, so the format is widely supported, however
> most of these files still infringe on the patent. To avoid
> infringement, I believe it is necessary to use spectral selection with
> each coefficient in a separate scan (Ss = Se). This requires 190
> scans, one for the three DC components, and 63x3 for the 63 AC
> coeffients x 3 colors.
>
> The DC coeffients uses a simple Huffman code, so they do not infringe.
> Now by splitting the AC coeffients into separate scans, there are only
> two types of codes: (0,S), a simple Huffman code for an S-bit number,
> and (R,0), a simple run length code (specifically EOBn codes for an
> R-bit numbers which give the run length). Neither code is patented.
>
> I haven't tried creating such files, so I don't know about performance
> issues such as poor compression or slow rendering. Also, I suppose the
> technique would only be practical for applications that create JPEGs,
> not those that read them and need to be compatible with existing
> images.
>
> Comments?
>
> -- Matt Mahoney
>

Tom St Denis

2005-02-22, 3:55 pm

Jack Berlin wrote:
> Or you could use Pegasus JPEG which is indemnified and protected from
all
> patent claims....
>
> 'Free' JPEG users have paid $30 mil; Pegasus customers have been
approached,
> yet have paid zero. Sometimes you get what you pay for!
>
> Cheers,
> jack
> --
> The JPEG Wizard free web compression testing:
http://www.jpegwizard.com/
> http://www.jpg.com/ - Pegasus - The BETTER JPEG People!

Your website renders horribly in the latest release of Mozilla. Let me
guess, big fans of the IE are we?

Tom

Scott

2005-02-22, 3:55 pm

On Tue, 22 Feb 2005 14:33:39 GMT, "Jack Berlin" <jberlin@jpg.com> wrote:

>Or you could use Pegasus JPEG which is indemnified and protected from all
>patent claims....

It doesn't support my development platforms, though.

Also, I don't do business with liars.

-Scott

Jack Berlin

2005-02-23, 3:55 am

Scott,

I am sorry, I do not understand your 'points'. What platform and what lie?
Or are you just being rude?

Let me know,
jack
--
Pegasus - BETTER DIGITAL IMAGING!
http://www.pegasusimaging.com/

"Scott" <nobody@xmission.com> wrote in message
news:421b7133.246429890@localhost...
> On Tue, 22 Feb 2005 14:33:39 GMT, "Jack Berlin" <jberlin@jpg.com> wrote:
>
>
> It doesn't support my development platforms, though.
>
> Also, I don't do business with liars.
>
> -Scott

Jack Berlin

2005-02-23, 3:55 am

Fans? No. Microsoft-centric? Yes. They accounts for 90+% of world
commercial PC use, and 95% of our sales, so we have to be. Our LINUX,
Solaris, Mac, PowerPC solutions don't fly off the shelves, but I would bet
the mozilla issue is just more of ignorance and learning on our part, as we
probably never tested outside of IE. I will pass to our (part-time)
webmaster.

Thanx,
jack
--
Pegasus - BETTER DIGITAL IMAGING!
http://www.pegasusimaging.com/

"Tom St Denis" <tomstdenis@gmail.com> wrote in message
news:1109085688.243900.314460@z14g2000cwz.googlegroups.com...
>
> Jack Berlin wrote:
> all
> approached,
> http://www.jpegwizard.com/
>
> Your website renders horribly in the latest release of Mozilla. Let me
> guess, big fans of the IE are we?
>
> Tom
>

Scott

2005-02-23, 3:55 am

On Wed, 23 Feb 2005 02:28:34 GMT, "Jack Berlin" <jberlin@jpg.com> wrote:

>I am sorry, I do not understand your 'points'. What platform

At the moment, FreeBSD and MSDOS.

> and what lie?

"SECURITY VULNERABILITY IN NON-PEGASUS JPEG"

An incomplete and misleading statement, at the very least.

>Or are you just being rude?

I can't tell the difference anymore.

-Scott

Jack Berlin

2005-02-23, 3:55 am

I thought all marketing was "incomplete and misleading", but now I am being
rude.

We did have DOS libraries which I doubt we could compile anymore, and may
have compiled some of our stuff under BSD for one client, but you are right
that these are not our forté.

Good luck,
jack
--
www.jpg.com

"Scott" <nobody@xmission.com> wrote in message
news:421bf984.281332270@localhost...
> On Wed, 23 Feb 2005 02:28:34 GMT, "Jack Berlin" <jberlin@jpg.com> wrote:
>
>
> At the moment, FreeBSD and MSDOS.
>
>
> "SECURITY VULNERABILITY IN NON-PEGASUS JPEG"
>
> An incomplete and misleading statement, at the very least.
>
>
> I can't tell the difference anymore.
>
> -Scott

Sponsored Links