HDTenEightyP/NetNews huggingface dataset:
From: kumarad@ecf.toronto.edu (KUMARADAS JOSEPH CARL)
Subject: Re: DCT optimisation
Organization: University of Toronto, Engineering Computing Facility
Date: Fri, 29 Jan 1993 02:51:51 GMT

In article <C1L49B.9ML@cs.bham.ac.uk> ahp@cs.bham.ac.uk writes:
>I am a final year undergraduate doing a software engineering project in Digital Video.
>I have implemented a number of image compression algorithms that run on Sun Unix
>workstations, among these is a JPEG and MPEG codec. I should immediately add that these
>are not true compliant codecs but merely abstract the core ideas present in them. The
>problem I have is that I am currently using the standard fast DCT algorithm, but even
>with the speed of a Sun/4 processor I cannot get more than a frame a second at 160 by
>120 image size. I have already scaled the algorithm into integer maths that helped a
>lot but I am stuck for the next move. I have also implemented a fairly sophisticated
>motion estimation system which allows me to miss out well matched blocks completely
>if the error between the motion estimated blocks and the actual block is below a given
>threshold, this obviously presents one way of speeding up the process by simply not
>doing an inverse DCT on every block !
>Any thoughts and ideas would be greatly appreciated. Anthony Phillips.

Take a look at an artical by Ephriam Feig from IBM, published in "Image 
Processing and Techniques", Vol 1244, pp2-13.  It is I suspect the fastest
known algorithm for DCT's.  I worked on optimizing an implementation of it
while at IBM.  The work lead to what we believe to be the fastest JPEG
software decoder.

I still don't suspect that it will improve your frame rate significantly.
I too am a undegrad in my final year.  I was looking at issues in diplaying
MPEG type video using software, but I have decided to concentrate only on
the DCT section due to a lack of time.

For performance reasons I was looking at displaying 160X120 (coincidence!)
8bit gray-scale video.  How about coding the error stream with some other
less-computation intensive coding (run-length?)?

You may want to take a look at a product for OS/2 released by IBM for 
software only video display.  It uses their own video compression algorithm
with adjusts to difference CPU power.  I think it's called Ultimotion
or something to that effect.

Carl.

Newsgroups: comp.compression.research
From: hansoo@kum (Kim HanSoo (Daewoo Elec.))
Subject: Help: CCITT test sequence for H.261
Organization: KAIST in Seoul, Korea
X-Newsreader: Tin 1.1 PL4
Date: Thu, 21 Jan 93 06:46:42 GMT

I lost the CCITT test sequence for H.261. Thus I want to know the placeof those sequence which get by FTP. Wanted specifications of sequence is
 following:

  a. Sequence Name : TREVOR, MISS AMERICA, CLAIR, ALIXIS,
                     SWING, SALES MEN, ...
  b. Sequence Spec : CIF (Common Intermediate Format)
                     30 frame/sec or 25 frame/sec
                     352 pixels/line x 288 lines/frame
                     color component : Y, R-Y, B-Y

  If the sequence is encoded by any-algorithms (ex: GIF, ppm, etc), I wa
nt to also get the decoding software.

  Mail address : hansoo@kum.kaist.ac.kr (hansoo@128.134.1.1)

  Bye.

Newsgroups: comp.compression.research
From: kumarad@ecf.toronto.edu (KUMARADAS JOSEPH CARL)
Subject: Re: best way to describe jpeg
Organization: University of Toronto, Engineering Computing Facility
Distribution: comp
Date: Sun, 24 Jan 1993 18:36:50 GMT

In article <1993Jan24.020112.9370@netcom.com> pdh@netcom.com (Phil Howard ) writes:
>"danny hawrysio" <danny.hawrysio@canrem.com> writes:
>
>			A summary of JPEG
>				by
>			Philip D. Howard
>
>
>JPEG works with 24-bit color images.  It functions separately in each of the
>3 primary colors, that is, do the reds, then do the greens, then do the blues.
>The three colors are 8 bits each.  It also works with gray scale 8-bit.  The
>theory could also be applied in other ways.

For best results, JPEG work with the YUV colour model, where represents the
intensity of a colour, and U and V together describe the chrominance of
a colour.  The reason this is done is that the Y component has mostly
low spatial frequency (changes slowly) components and so can have its high
frequency components quatized by a larger amount.

>The image is chopped up into little squares of 8 pixels by 8 pixels in order
>to reduce the computation scale.  These image segments are then analyzed by
>a method called the Digital Cosine Transform, which is similar in certain
>ways to a Fourier Transform.  The result of this transform is that the various
>repetitious patterns are extracted with respect to their periodicy and their
>amplitude (the degree to which they contribute).

The transform used is called the Discrete Cosine Transform.

>These quantized numbers are then formed into variable length integers that
>occupy only a few bits.  The zeroes are treated as a special case since it
>is known that the quantizing results in a lot of them; they take the fewest
>bits, typically 1 bit and maybe fewer (I have not looked at this area of
>detail yet).  The more loss there is, the more zeroes and the smaller the
>data.  The non-zero numbers will also have less range and can be squeezed
>into few bits in many cases as well.

The coefficients from the DCT process are seperated into to types, the DC
(average colour of the 8x8 block) and AC (the remaining frequency components).
The DC coefficients are differentailly coded by themselves.  Coding them
differentially (storing the difference between two consecutive DC's) is
advantageous in that it produces many 0's since the average colour of
adjacent 8x8 blocks is usually the same.  

As pointed out the AC coefficients have many zero's in them and are coded
using run-lengths (store the number of consecutive 0's).

>The best way to compress a JPEG image is to start from the original 24-bit
>data.  Images with less noise work better, of course, since noise can appear
>to be high frequency spectral components.  Noise typically appears in the
>image as graininess.

Actaully I expect JPEG to improve the quality of noisy images since it chops
off high frequency components and noise is usually present in the high
frequencies.

Carl.
From: ahp@cs.bham.ac.uk (Anthony H Phillips)
Newsgroups: comp.compression.research
Subject: DCT optimisation
Date: 28 Jan 93 22:10:22 GMT
Reply-To: ahp@cs.bham.ac.uk
Organization: The University of Birmingham Computer Science Department.

I am a final year undergraduate doing a software engineering project in Digital Video.
I have implemented a number of image compression algorithms that run on Sun Unix
workstations, among these is a JPEG and MPEG codec. I should immediately add that these
are not true compliant codecs but merely abstract the core ideas present in them. The
problem I have is that I am currently using the standard fast DCT algorithm, but even
with the speed of a Sun/4 processor I cannot get more than a frame a second at 160 by
120 image size. I have already scaled the algorithm into integer maths that helped a
lot but I am stuck for the next move. I have also implemented a fairly sophisticated
motion estimation system which allows me to miss out well matched blocks completely
if the error between the motion estimated blocks and the actual block is below a given
threshold, this obviously presents one way of speeding up the process by simply not
doing an inverse DCT on every block !
Any thoughts and ideas would be greatly appreciated. Anthony Phillips.
From: quandt@cs.umr.edu (Brian Quandt)
Newsgroups: comp.compression.research
Subject: motion estimation
Date: 27 Jan 93 02:41:57 GMT
Article-I.D.: umr.1993Jan27.024157.9222
Organization: University of Missouri - Rolla, Rolla, MO

First I apologize that my last message ended up containing nothing
for the body... who knows why but anyways.

Well, since the last message got messed up I thought I would take my
time and write this one with hopefully a clear head.

I'm working on MPEG motion estimation (eventually to become a
parallel encoder... but that's later).  

A thought occurred to me whether the string matching algorithm found
in Udi Manber's text "Introduction to Algorithms, A Creative Approach"
pg 141, could be useful in effciently matching the macroblocks used in MPEG.
Quickly stated:
	Given two strings 'A' and 'B' match 'B' within the string 'A'.

	String 'B' is first preprossesed to generate a thing called a 'next' 
	table.  Bascically this table reduces the amount of time that
	'B' has to be looked at when a match against 'A' fails.  This
	is the main 'time' saving feature of this alogrithm...if you 
	need more help on this consult the book, but suffice it to say that
	it involves things like 'prefix' and 'suffix' of a string.

So anyways I was wondering if this algorithm could apply to motion
estimation.  My thought was to treat the macroblock to find as the 'B'
string, preprocess it creating a 'next' table and then use this information
to help find a match within the 'frame'.

THE PROBLEMS (at least the ones I immediately see)

1) The string match algo is a 1-diminsional algorithm.  How can it
be modified to work on 2-dim objects?

	My initial thought is to just pick a row within a macroblock and 
	compare this against one row at a time within the frame.  When 
	a match occurs (or find the best match) then use brute force to 
	check the other rows of the macroblock with the appropriate rows
	within the frame.  Since we are looking for a best match I would
	just maintain the best (least errors) macroblock.

2) Using the algorithm from above (chosing a row within the macroblock),
which row should be chosen?

	Here I think the answer would be to choose the row that has the most 
	random/differing data within it.  This should result in the 'string' 
	matching algorithm to perform much better.

Okay so here's a rough outline of the algorithm
	Set the found matched macroblock to NULL
	Set the number of errors in matching to MAXINT (infinity)
	Find the most random row within the macroblock.
	Calculate 'next' for this row.
	For each row within the frame (or whatever you search range).
		Do the fast 'string' match using the 'next' table.
			For each found matching prefix... calculate the error
				for the potential macroblock versus the macroblock to match.
			If the error is better (less errors) save this potential macroblock.
	The best matching macroblock should be found when finished.


That should do it, I know I left lots out, but hopefully someone out there
remembers this string matching alogrithm.  I appreciate hearing from anyone

								Brian Quandt
From: dak@tabaqui.informatik.rwth-aachen.de (David Kastrup)
Newsgroups: comp.compression.research
Subject: Re: best way to describe jpeg
Date: 24 Jan 93 10:06:20 GMT
Organization: Rechnerbetrieb Informatik - RWTH Aachen
Distribution: comp
NNTP-Posting-Host: tabaqui.informatik.rwth-aachen.de

pdh@netcom.com (Phil Howard ) writes:


>			A summary of JPEG
>				by
>			Philip D. Howard


>JPEG works with 24-bit color images.  It functions separately in each of the
>3 primary colors, that is, do the reds, then do the greens, then do the blues.
>The three colors are 8 bits each.  It also works with gray scale 8-bit.  The
>theory could also be applied in other ways.

The rest agrees pretty much with what I know. However, I think I remember
that JPEG did not use a RGB model, but some other color model. This is
because changes in luminosity are more easy spotted by the human eye
than changes in saturation in hue. The exact color model I do not know,
but I think I remember that about double the number of information was
kept for luminosity than for the other two color vectors.
Newsgroups: comp.compression.research
From: hansoo@kum (Kim HanSoo (Daewoo Elec.))
Subject: E.E.Mail to Mr. Zammits
Organization: KAIST in Seoul, Korea
X-Newsreader: Tin 1.1 PL4
Date: Tue, 26 Jan 93 06:13:46 GMT


To : Zammits

Thank you Zammits.
I appreciate your message for H.261 sequence. I have 'Table Tennis' sequ
ence for MPEG I standards. But this sequence's specification is not CCIR
601-format(original format) but Source Input Format for MPEG-I(filteredversion from CCIR601), i.e 352 pixels/line x 288 lines/picture x 25 pict
ures/1 sec.

The site, kum.kaist.ac.kr, is my friend's site, and my site is ksseo@vis
sol.kaist.ac.kr. But my site can not receive any mail messages and not c
onnected for foreign host. Also friend's site(kum.kaist.ac.kr) have smal
l hard disk. Hence I have to receive H.261 sequence and send Table Tenni
s sequence by my operation. I am sorry for these bad enviroments. Please
 say FTP-ing method to me : I want to know connection address (134.151.9
2.27 ?), login method, disk path, and a period of connection .....

Thank you for your assistance.

Mail Address : hansoo@kum.kaist.ac.kr (hansoo@128.134.1.1)

From : ksseo@vissol.kaist.ac.kr

Newsgroups: comp.compression.research
From: g44140g@nucc.cc.nagoya-u.ac.jp (Haruhiko Okumura)
Subject: Re: improvements to lha
Organization: Matsusaka University, Matsusaka, Japan.
Date: Fri, 22 Jan 1993 01:31:45 GMT

Thanks for the many ideas to improve LHA.  I'm aware that hashing will
make LHA faster.  In fact there was an archiver (before ARJ and ZIP),
written by a Japanese (in Z80 assembler!), that mimicked LHA's
algorithm but used hashing.

As Dan Halem has mentioned, the idea by Leonid A. Broukhis reminded me
of Bender and Wolf, IEEE IT 37, 721-729 (1991).  This should improve
compression, but is probably rather slow.

I received several emails asking the status of LHA in Japan.  LHA 2.13
is still the de fact standard archiver here.  It won the first Free
Software Grand Prix of Japan last year.  Yoshi (the author of LHA) has
written several minor revisions.  I think 2.56a1 is the latest one,
This particular version tries to cope with NetWare file sharing.  But
its algorithm is the same as LHA 2.13.  Some of the previous test
versions were compiled under DOS extender with larger dictionary
sizes.  They were very very slow.

It's high time Yoshi rewrote his archiver, but he's too busy (and so
am I).  We need your help.

                     Haruhiko Okumura (g44140g@nucc.cc.nagoya-u.ac.jp)
              Matsusaka University, 1846 Kubo-cho, Matsusaka 515 Japan

Newsgroups: comp.compression.research
From: cmcgldrk@unix2.tcd.ie (Wowbagger - the infinitely Prolonged)
Subject: Re: Help: CCITT test sequence for H.261
Organization: Trinity College, Dublin
Date: Mon, 25 Jan 1993 13:29:59 GMT

In <1993Jan21.064642.4381@kum.kaist.ac.kr> hansoo@kum (Kim HanSoo (Daewoo Elec.)) writes:

>I lost the CCITT test sequence for H.261. Thus I want to know the placeof those sequence which get by FTP. Wanted specifications of sequence is
> following:

>  a. Sequence Name : TREVOR, MISS AMERICA, CLAIR, ALIXIS,
>                     SWING, SALES MEN, ...
>  b. Sequence Spec : CIF (Common Intermediate Format)
>                     30 frame/sec or 25 frame/sec
>                     352 pixels/line x 288 lines/frame
>                     color component : Y, R-Y, B-Y

>  If the sequence is encoded by any-algorithms (ex: GIF, ppm, etc), I wa
>nt to also get the decoding software.

>  Mail address : hansoo@kum.kaist.ac.kr (hansoo@128.134.1.1)

Me too!

Ciaran Mc Goldrick.                cmcgldrk@vax1.tcd.ie
From: pdh@netcom.com (Phil Howard )
Newsgroups: comp.compression.research
Subject: Re: best way to describe jpeg
Date: 25 Jan 93 13:15:05 GMT
Distribution: comp
Organization: Netcom - Online Communication Services  (408 241-9760 guest)

dak@tabaqui.informatik.rwth-aachen.de (David Kastrup) writes:

>The rest agrees pretty much with what I know. However, I think I remember
>that JPEG did not use a RGB model, but some other color model. This is
>because changes in luminosity are more easy spotted by the human eye
>than changes in saturation in hue. The exact color model I do not know,
>but I think I remember that about double the number of information was
>kept for luminosity than for the other two color vectors.

There is a different color model.  Luminance (Y) and two dimensional color
(Cr and Cb).  I'm only guessing this is similar to YIQ in NTSC video.  It
is based on the same chrominance theories, so it should be at least rather
close.  Also, the blocking is a bit different for color to gain more
compression.

I'll be rewriting my article with the new information.
-- 
/************************************************************************\
| Phil Howard,  pdh@netcom.com,  KA9WGN    Spell protection?  "1(911)A1" |
| "It's not broken... it's just functionally challenged" --Phil and Pete |
\************************************************************************/
Newsgroups: comp.compression.research
From: rsl11@kuhub.cc.ukans.edu
Newsgroups: comp.compression.research,comp.os.msdos.misc
Subject: PROBLEMS WITH STACKER...
Date: 28 Jan 93 18:29:31 GMT
Organization: University of Kansas Academic Computing Services

Hello there,

	I am using stacker 2.0 for DOS and I have some problems. Everything was
running OK until I deleted some files with smartcan of Norton, the files I deleted
are not any system files or anything  that stacker is using or any files that dos
is using, and what happened smartcan kept on running without stopping. Then, I 
rebooted the computer and I got the following error:

Stacker drive write protected

I got the DOS prompt without any problem but when I loaded windows, with Norton 
as the shell, the computer freezes.

When I run the scheck on the stacker drive of stacker it tells me 

Sector allocation map invalid

	Do you think the stacker volume file, the compressed file, is corrupted?
Is there anything we can do to fix this problem? What would happend if I try to 
install stacker again, same version? Would it make any difference? I was planning
to try that but is it going to mess up anything?

	Does anybody have the telephone number of the company that developed
stacker? I had it but I cannot find it now. Also, is there any good book I can refer
to to get information about stacker besides the stacker manual?

	IS there any FAQ list for stacker problems?

	I would very much appreciate any relevant response.

Thanks,
Feel Free to send mail to :
Internet Address: rsl11@kuhub.cc.ukans.edu
Bitnet Address: rsl11@ukanvm.bitnet
Newsgroups: comp.compression.research
From: broy@cs.umr.edu (Brian Roy)
Subject: DSP's and MPEG I
Date: Tue, 26 Jan 1993 06:40:33 GMT
Organization: University of Missouri - Rolla, Rolla, MO

Good morning.
I am currently embroiled in a project involving MPEG I encoding.
We are attempting at this time to establish a feasible method of 
achieving our goals "off-line" but the prospects of theoretically
be able to encode in realtime loom temptingly in the immediate future.
Does anyone know what it will take to do realtime MPEG audio encoding,
layer I?  Layers II or III?
Can we reasonably do this with a DSP card in a PC?  Two cards, maybe?
Or even a hopped up PC by itself?
As long as I'm asking, does anyone have any horsepower estimates for what
it would take to accomplish the video encoding in realtime?

E-mail responses would be much appreciated by
	broy@umrgec.eec.umr.edu

Thank you.

Brian A. Roy
From: mkcummin@apgea.army.mil (M. Keath Cummings <mkcummin>)
Newsgroups: comp.compression
Subject: Re: PKZIP 2.04E now available...
Date: 28 Jan 93 13:20:49 GMT
Organization: APG-Edgewood

Hello,

I read your article saying that PKZIP v2.04e was available now for
downloading pleasure.   My question to you is:  "Is there an FTP Site run
my PKWare or do they have a toll free BBS number?" or "What FTP site is the
most up-to-date when it comes to Compression Utilities such as PKWare?"

-=[ Keath Cummings ]=-

ADVthanksANCE
Newsgroups: comp.compression
From: sigma@degas.ipl.rpi.edu (Kevin Martin)
Subject: Re: zipsplit with pkzip204c Was: Re: Unix release? (Was etc.
Date: Sat, 23 Jan 1993 04:13:06 GMT

madler@cco.caltech.edu (Mark Adler) writes:
>Or perhaps you think that the other zipsplit optimizes the chunks
>better.  I don't know what algorithm the other zipsplit uses, but
>our's uses a simple "greedy" algorithm that achieves the optimum in
>nearly all cases with typical distributions of entry sizes.  The
>chunk optimization is an NP-complete problem, so there are lots of
>approximate approaches to the solution.

This is what's called the Knapsack Problem.  It's NP-complete, but since
your knapsack is usually relatively small compared to the total size of the
files, an early-out algorithm which avoids combinations which will
obviously not fit actually has to check very few combinations.  Even with
four hundred files, I've never had to check more than 30000 combinations
(well, my program does - not myself by hand) to get a perfect fit.

"Perfect" in the sense that no clusters are wasted, which also simplifies
things.

-- 
Kevin Martin
sigma@ipl.rpi.edu
"I told you I'd shoot, but you didn't believe me! WHY didn't you BELIEVE me?!"
From: drinnen@deakin.edu.au (Philip Shead)
Newsgroups: comp.compression
Subject: Re: Which compressors under Unix?
Date: 28 Jan 1993 09:30:34 -0600
Organization: UTexas Mail-to-News Gateway
NNTP-Posting-Host: cs.utexas.edu


In article <1993Jan28.112443.7931@uwasa.fi> ts@uwasa.fi (Timo Salmi) writes:
>In article <1993Jan27.202444.19378@opus40.ix.de> hm@opus40.ix.de (Harald Milz) writes:
>>I found some of PC-world's compressors for Unix (LHA, GZIP).
>>Are there already any other compressors ported to Unix? Where
>>can I get them?
>
> 125879 Nov 23 11:38 garbo.uwasa.fi:/unix/arcers/arc.tar.Z
> 667464 Dec  5 16:43 garbo.uwasa.fi:/unix/arcers/hpack78src.tar.Z
  ^^^^^^ The first thing that struck me about this is the
very large size of the code in comparison with lha, 7 times in fact.

 Is this a factor in hpack greater (I'm lead to believe) compression
or does it implemented a few methods of compression, because I notice
the combined info-zip programs are much larger. This is another factor
in my preference for lha. It comes in one small package of course.

 I'll get the hpack source code and have a look, to see what the difference
is. I've decided to have a look at the dos version and you never know
I may switch to it although it will have to be pretty persuasive.

>  96999 Jan 11 07:24 garbo.uwasa.fi:/unix/arcers/lha101u.tar.Z
>  35321 Nov 23 11:38 garbo.uwasa.fi:/unix/arcers/unarj230.tar.Z
 I would love to see a unix version of arj.
> 299288 Jan 15 08:42 garbo.uwasa.fi:/unix/arcers/unz50p1.tar.Z
> 186591 Nov 23 11:38 garbo.uwasa.fi:/unix/arcers/zip10ex.tar.Z
> 244565 Nov 23 11:38 garbo.uwasa.fi:/unix/arcers/zip19p1.tar.Z
> 237093 Nov 23 11:38 garbo.uwasa.fi:/unix/arcers/zoo210.tar.Z
        Too slow and poor compression from zoo.
Newsgroups: comp.compression
From: fox@rei.com (Fuzzy Fox)
Subject: Re: zipsplit with pkzip204c Was: Re: Unix release? (Was etc.
Date: Tue, 26 Jan 1993 04:49:40 GMT
Organization: Recognition Equipment, Inc.

sigma@degas.ipl.rpi.edu (Kevin Martin) writes:

>This is what's called the Knapsack Problem.  It's NP-complete, but since
>your knapsack is usually relatively small compared to the total size of the
>files, an early-out algorithm which avoids combinations which will
>obviously not fit actually has to check very few combinations.

Where can I find a write-up or description of an algorithm which solves
the Knapsack Problem?  I have been unable to locate such a description
(or even source code).

-- 
#ifdef TRUE        | Fuzzy Fox (a.k.a. David DeSimone)       fuzzy@netcom.com
#define  TRUE   0  |
#define  FALSE  1  |         "S-O-C-K-S ?   Wow, Spanish *is* easy!!"
#endif             |