Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!genrad!decvax!decwrl!turtlevax!ken
From: ken@turtlevax.UUCP
Newsgroups: net.math,net.graphics
Subject: Re: Lempel and Ziv do it again (two-dimensional compression)
Message-ID: <1141@turtlevax.UUCP>
Date: Thu, 24-Apr-86 21:52:08 EDT
Article-I.D.: turtleva.1141
Posted: Thu Apr 24 21:52:08 1986
Date-Received: Sun, 27-Apr-86 04:58:50 EDT
References: <1135@turtlevax.UUCP> <1490@ames.UUCP>
Reply-To: ken@turtlevax.UUCP (Ken Turkowski)
Organization: CIMLINC, Inc. @ Menlo Park, CA
Lines: 34
Xref: watmath net.math:3120 net.graphics:1610

In article <1490@ames.UUCP> jaw@ames.UUCP (James A. Woods) writes:
>It's rather like the impossibility of multiplication on an FSA. 
>(see Minsky, section 2.6.)

It's results like the above that leave me skeptical of many information
theory results.  I personally know of several automatons that can do
multiplication on two 16x16 numbers :-) and I'm sure others do too.  I
have only found one issue (the March 1982 issue on quantization:  get
your hands on it and xerox(tm) the whole thing) that I have found to be
useful in the IEEE transactions on IT.

>  Now a bit about LZ2D pragmatics:  I programmed a simple Peano-Hilbert curve
>image scanner ...                         Alas, after compressing a 512x512
>gray-scale image or two (from the "spaceman" series), I lost interest after
>discovering file *expansion* (1d gave me about 30% for the image, and
>2d only about 20%).

Skeptic though I am, I really believed that the Peano-Hilbert scan
could compress better than the "video scan".  I'd like to believe that
James missed something (an event of measure zero), but I've been held
up in my own implementation because of a practical concern:

The LZ2D was designed to work only with square images with binary power
dimensions.  Usually, I like to save images with arbitrary rectangular
dimensions, perhaps with an associated alpha mask to get
non-rectangular silhouettes.  What is the best way to extend LZ2D to
rectangular images?  Find the next larger square and pad it with
zeros?  Find the next smaller square and break up the remainder into
smaller and smaller squares that can be P-H-scanned?
-- 
Ken Turkowski @ CIMLINC, Menlo Park, CA
UUCP: {amd,decwrl,hplabs,seismo}!turtlevax!ken
ARPA: turtlevax!ken@DECWRL.DEC.COM