From garys@newshost.pictel.com Thu Jun 9 17:58:30 1994 X-VM-Summary-Format: "%n %*%a %-17.17F %-3.3m %2d %4l/%-5c %I\"%s\"\n" X-VM-Labels: nil X-VM-VHeader: ("Resent-" "From:" "Sender:" "To:" "Apparently-To:" "Cc:" "Subject:" "Date:") nil X-VM-Bookmark: 8 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["2544" "Thu" " 2" "June" "1994" "16:10:48" "GMT" "Gary Sullivan" "garys@newshost.pictel.com" nil "76" "Re: Computational complexity of DCT." "^From:" nil nil "6" nil nil (number " " mark " Gary Sullivan Jun 2 76/2544 " thread-indent "\"Re: Computational complexity of DCT.\"\n") nil] nil) Xref: saips.cv.nrao.edu sci.image.processing:7836 comp.compression:11922 comp.graphics.algorithms:5761 Newsgroups: sci.image.processing,comp.compression,comp.graphics.algorithms Path: saips.cv.nrao.edu!hearst.acc.Virginia.EDU!caen!math.ohio-state.edu!howland.reston.ans.net!noc.near.net!gateway-gw!newshost!garys Message-ID: Organization: PictureTel Corporation References: <1994May28.200555.6831@equalizer.cray.com> Lines: 76 From: garys@newshost.pictel.com (Gary Sullivan) Subject: Re: Computational complexity of DCT. Date: Thu, 2 Jun 1994 16:10:48 GMT In article <1994May28.200555.6831@equalizer.cray.com> billd@cray.com (Bill Davidson) writes: >I am going through the Pennebaker/Mitchell JPEG book and I'm trying to >understand the DCT as well as possible. I think that the place that >I'm getting hung up is the extension of a 1-D DCT to a 2-D DCT. For >reference I'm looking at pages 40-42. They give the definition of the >2-D FDCT as: > > 7 7 > ___ ___ > C(v) C(u) \ \ >S(v,u) = ---- ---- \ \ s(y,x)cos[(2x+1)u*pi/16]cos[(2y+1)v*pi/16] > 2 2 / / > /__ /__ > y=0 x=0 > >They also mention that you can work all the cosine stuff into pre >computed constants. That makes sense to me and would give: > > 7 7 > ___ ___ > \ \ >S(v,u) = \ \ s(y,x)constant(v,u,y,x) > / / > /__ /__ > y=0 x=0 > >To me this looks like 64 multiplies and 63 adds for every DCT >coeficient and so would give 64*64=4096 multiplies and 64*63=4032 adds >for the entire DCT. > >However, Pennebaker/Mitchell give the upper bound as 1024 multiplies >and 896 adds for the reference DCT. They talk about "separable 1-D >format" for this and that seems to be where I'm getting lost. >Apparently it's a natural extension to them but to me, it's not. > >Help! > >--Bill Davidson > First, compute eight 8x1 transforms, per 7 7 ___ ___ C(v) \ \ T(v,x) = ---- \ s(y,x) cos[(2y+1)v*pi/16] = \ s(y,x) constant(v,y) 2 / / /__ /__ y=0 y=0 which takes 64 terms * (8 multiplies + 7 adds) Then transform the other dimension, per 7 7 ___ ___ C(u) \ \ S(v,u) = ---- \ T(v,x) cos[(2x+1)u*pi/16] = \ T(v,x) constant(u,x) 2 / / /__ /__ x=0 x=0 which takes 64 terms * (8 multiplies + 7 adds), for a total of 128 terms * (8 multiplies + 7 adds) = 1024 multiplies + 896 adds (There are, of course, faster ways than this) -- --------------------------------- Gary Sullivan (garys@pictel.com) From eillihca@drizzle.StanFord.EDU Thu Jun 9 18:01:25 1994 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["1230" "" " 6" "June" "1994" "21:51:10" "GMT" "eillihca@drizzle.StanFord.EDU ( Achille Hui, the Day Dreamer )" "eillihca@drizzle.StanFord.EDU ( Achille Hui, the Day Dreamer )" nil "24" "Re: [Q] Lossless JPEG" "^From:" nil nil "6" nil nil (number " " mark " eillihca@drizzle. Jun 6 24/1230 " thread-indent "\"Re: [Q] Lossless JPEG\"\n") nil] nil) Path: saips.cv.nrao.edu!hearst.acc.Virginia.EDU!darwin.sura.net!usenet.fiu.edu!MathWorks.Com!news.duke.edu!news-feed-1.peachnet.edu!gatech!swrinde!sdd.hp.com!hplabs!unix.sri.com!headwall.Stanford.EDU!eillihca@drizzle.Stanford.EDU Newsgroups: comp.compression Organization: Dept. of Physics, Stanford University. Lines: 24 Message-ID: NNTP-Posting-Host: drizzle.stanford.edu X-Transfer-Agent: nntp.stanford.edu (NNTP) From: eillihca@drizzle.StanFord.EDU ( Achille Hui, the Day Dreamer ) Subject: Re: [Q] Lossless JPEG Date: 06 Jun 94 21:51:10 GMT +---dinesh@charlie.usd.edu-writes--- | | Hello, | | I am currently researching JPEG compression techniques. In particular | I am interested in Lossless JPEG compression. Unfortunately the FAQ of | this BB dosen't mention much about it. I would appreciate any leads, | ftp sites, currrent state of art in lossless JPEG. | The best reference is the book "JPEG still image data compression standard" by William B. Pennebaker and Joan L. Mitchell published by Van Nostrand Reinhold (ISBN 0-442-01272-1). It also include the relevant ISO DIS documents as appendices. The only public domain code which can deal with lossless JPEG is the PVRG code from Stanford (available through ftp at havefun.stanford.edu) Unluckily, it only handles the Huffman encoding mode (Unlike lossy JPEG, the compression model used in arithmetic encoding mode for lossless JPEG is different from those used in the Huffman encoding and offer much superior compression ratio) and is horribly slow. I would suggest you to grab the aforementioned book and code the arithmetic mode yourself. (At least for the lossless JPEG part, the coding is amazing simple). Hope this helps... ---------------------------------------achille (eillihca@drizzle.stanford.edu) From bourgin@turing.imag.fr Thu Jun 9 18:01:43 1994 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["1094" "" " 7" "June" "1994" "09:20:49" "GMT" "David Bourgin (The best player)." "bourgin@turing.imag.fr" nil "30" "Re: Wanted: LZW" "^From:" nil nil "6" nil nil (number " " mark " David Bourgin (Th Jun 7 30/1094 " thread-indent "\"Re: Wanted: LZW\"\n") nil] nil) Path: saips.cv.nrao.edu!hearst.acc.Virginia.EDU!darwin.sura.net!howland.reston.ans.net!math.ohio-state.edu!jussieu.fr!univ-lyon1.fr!cri.ens-lyon.fr!news.imag.fr!babbage.imag.fr!turing!bourgin Newsgroups: comp.compression Organization: ufrima Lines: 30 Distribution: world Message-ID: <2t1e5h$ldq@babbage.imag.fr> NNTP-Posting-Host: turing Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 8bit Keywords: LZW From: bourgin@turing.imag.fr (David Bourgin (The best player).) Sender: bourgin@turing (David Bourgin (The best player).) Subject: Re: Wanted: LZW Date: 7 Jun 1994 09:20:49 GMT In article <1994Jun6.162548.816@polar>, zz93f007@polar.etsiig.uniovi.es (Ortiz Boyero, Cesar M.) wrote: |> I'm looking for the specification or the source code of the LZW |> algorithm. |> Could somebody send me it? |> |> thanks in advance I wrote several codecs (4 RLE, 1 Huffman, 1 LZW). I put them available by anonymous ftp. Site: turing.imag.fr (129.88.31.7) Directory: /pub/compression File: codecs.dir.tar.gz See also the file: README The codec about LZW is not yet available (the explainations yes!) because I hadn't plenty of time to make tests. (Very soon available...) -- David /mmm\ /mmm\ /mmm\ (O o) (O O) (o o) U U u /mmm\ ||\ \\ / \\ . (- -) oOOo__oOOo _____oOOo ___________ ______u_oOOo___ ############ ######### ########### ################ (BAD ANSWER) (RETRY) (ONCE MORE) (Bored & Asleep) +----------------------------------------------------+ | Mail: david.bourgin@ufrima.imag.fr (David Bourgin) | | UFR IMA (French University - Grenoble) | From bilgin@dspcl1.sdsu.edu Sat Jun 11 22:42:55 1994 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["1064" "" " 9" "June" "1994" "00:21:31" "GMT" "Ali Bilgin" "bilgin@dspcl1.sdsu.edu" nil "33" "Re: [Want] ISBN number for K. R. Rao's DCT book?" "^From:" nil nil "6" nil nil (number " " mark " Ali Bilgin Jun 9 33/1064 " thread-indent "\"Re: [Want] ISBN number for K. R. Rao's DCT book?\"\n") nil] nil) Path: saips.cv.nrao.edu!hearst.acc.Virginia.EDU!darwin.sura.net!howland.reston.ans.net!vixen.cso.uiuc.edu!sdd.hp.com!math.ohio-state.edu!cs.utexas.edu!swrinde!ihnp4.ucsd.edu!ucsnews!dspcl1!bilgin Newsgroups: comp.compression Organization: San Diego State University Computing Services Lines: 33 Message-ID: <2t5nab$9am@gondor.sdsu.edu> References: NNTP-Posting-Host: 130.191.163.46 X-Newsreader: TIN [version 1.2 PL1] From: bilgin@dspcl1.sdsu.edu (Ali Bilgin) Subject: Re: [Want] ISBN number for K. R. Rao's DCT book? Date: 9 Jun 1994 00:21:31 GMT Norley Liu (nliu@tidmmpl.csc.ti.com) wrote: : Hi, netters. If you have "Discrete Cosine Transform: Algorithm, Advantages and : Applications" handy, could you tell me the ISBN number? I want to : order the book but BookStop won't do it unless I have the number. : BTW, if you know any other good books on DCT, please share the information. : Particularly, I am interested in implementation and applications. : Thanks in advance. : --Norley Here is the information: "Discrete Cosine Transform: Algorithms, Advantages, and Applications", K. R. Rao, P. Yip, Academic Press, 1990 ISBN = 0-12-580203-X Hope it helps, Ali -- -------------------------------------------------------------------------------- Ali Bilgin Digital Signal Processing & Communications Laboratory Dept. of Elec. and Comp. Eng. Office : E 224 San Diego State University Phone # : (619) 594 2432 San Diego, CA 92182-0190 E-mail : bilgin@anadolu.sdsu.edu ----------- From bourgin@turing.imag.fr Wed Jun 15 12:17:06 1994 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["1682" "" "13" "June" "1994" "14:09:13" "GMT" "David Bourgin (The best player)." "bourgin@turing.imag.fr" nil "41" "Re: General Compression" "^From:" nil nil "6" nil nil (number " " mark " David Bourgin (Th Jun 13 41/1682 " thread-indent "\"Re: General Compression\"\n") nil] nil) Path: saips.cv.nrao.edu!hearst.acc.Virginia.EDU!darwin.sura.net!howland.reston.ans.net!math.ohio-state.edu!jussieu.fr!univ-lyon1.fr!cri.ens-lyon.fr!news.imag.fr!babbage.imag.fr!turing!bourgin Newsgroups: comp.compression Organization: ufrima Lines: 41 Distribution: world Message-ID: <2thpa9$avt@babbage.imag.fr> NNTP-Posting-Host: turing Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 8bit Keywords: General Compression From: bourgin@turing.imag.fr (David Bourgin (The best player).) Sender: bourgin@turing (David Bourgin (The best player).) Subject: Re: General Compression Date: 13 Jun 1994 14:09:13 GMT In article , you write: |> Hello, |> |> I am currently seeking digital data compression schemes that will efficiently |> compact textual data, graphical images, still-motion video pictures, |> full-motion video, and audio data. I need to know what data compression |> schemes are available, the pro's and con's about the schemes, and if any of |> the schemes have patents. In addition, I would like to know which periodical |> articles, especially from computer journals such as the "Communications of the |> ACM", discuss such compression schemes. Some suggested books with names of |> titles and authors about specific data compression schemes would be helpful as |> well. Well, use a method as LZW. It will compress most of these data efficiently. But the best is to use specific scheme. E.g. Text: Huffman Documents (from data base), etc: LZW Pictures: JPEG Motion picture: MPEG ... See comp.compression FAQ. A copy of FAQ of comp.compression news group is available by ftp in rtfm.mit.edu:/pub/usenet/news.answers/compression.faq/part[1-3]. IMPORTANT: I was unable to reply on your message because your e-mail was BAD! -- Regards, David /mmm\ /mmm\ /mmm\ (O o) (O O) (o o) U U u /mmm\ ||\ \\ / \\ . (- -) oOOo__oOOo _____oOOo ___________ ______u_oOOo___ ############ ######### ########### ################ (BAD ANSWER) (RETRY) (ONCE MORE) (Bored & Asleep) +----------------------------------------------------+ | Mail: david.bourgin@ufrima.imag.fr (David Bourgin) | | UFR IMA (French University - Grenoble) | From davidm@marcam.com Sun Jun 26 21:54:47 1994 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["565" "" "24" "June" "1994" "21:09:43" "GMT" "David MacMahon" "davidm@marcam.com" nil "17" "Re: ADPCM" "^From:" nil nil "6" nil nil (number " " mark " David MacMahon Jun 24 17/565 " thread-indent "\"Re: ADPCM\"\n") nil] nil) Path: saips.cv.nrao.edu!hearst.acc.Virginia.EDU!caen!hellgate.utah.edu!dog.ee.lbl.gov!overload.lbl.gov!lll-winken.llnl.gov!ames!hookup!yeshua.marcam.com!usenet Newsgroups: comp.compression Organization: Marcam Corporation Lines: 17 Message-ID: <2ufi2n$3mt@yeshua.marcam.com> References: <2ufdf1$tun@elvis.syl.sj.nec.com> Reply-To: davidm@marcam.com (David MacMahon) NNTP-Posting-Host: woodstock.marcam.com X-Newsreader: IBM NewsReader/2 v1.00 From: davidm@marcam.com (David MacMahon) Subject: Re: ADPCM Date: 24 Jun 1994 21:09:43 GMT In <2ufdf1$tun@elvis.syl.sj.nec.com>, hisashi@atherton.com (Hisashi Naganuma) writes: >What is the ADPCM? ADPCM stands for Adaptive Delta Pulse Code Modulation. It is a lossy method of compressing (primarily) audio data. There are several different ways of implementing it. Source code for some of the ADPCM schemes is available on the net (see the FAQ for details). Does anyone know of any resources on the net that describe the theory behind the various ADPCM implementations? How about a book? Dave David MacMahon Software Engineer davidm@marcam.com From bourgin@turing.imag.fr Mon Jun 27 11:56:09 1994 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["1013" "" "24" "June" "1994" "10:57:49" "GMT" "David Bourgin (The best player)." "bourgin@turing.imag.fr" nil "24" "Re: .Z refers to which compression" "^From:" nil nil "6" nil nil (number " " mark " David Bourgin (Th Jun 24 24/1013 " thread-indent "\"Re: .Z refers to which compression\"\n") nil] nil) Path: saips.cv.nrao.edu!hearst.acc.Virginia.EDU!darwin.sura.net!howland.reston.ans.net!math.ohio-state.edu!jussieu.fr!univ-lyon1.fr!cri.ens-lyon.fr!news.imag.fr!babbage.imag.fr!turing!bourgin Newsgroups: comp.compression Organization: ufrima Lines: 24 Distribution: world Message-ID: <2uee7d$7ue@babbage.imag.fr> NNTP-Posting-Host: turing Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 8bit Keywords: .Z and compress From: bourgin@turing.imag.fr (David Bourgin (The best player).) Sender: bourgin@turing (David Bourgin (The best player).) Subject: Re: .Z refers to which compression Date: 24 Jun 1994 10:57:49 GMT In article <19940623220958IAGKMBS@MVS.OAC.UCLA.EDU>, IAGKMBS@MVS.OAC.UCLA.EDU wrote: |> A file with extension .Z refers to what compression program - ZOO? or |> GNUZIP. Where can I obtain the appropriate program, MSDOS version -- |> what FTP site and file name? |> Thanks in advance. DAKaiser@aol.com It refers to compress. See comp.compression FAQ for more details. A copy of FAQ of comp.compression news group is available by ftp in rtfm.mit.edu:/pub/usenet/news.answers/compression.faq/part[1-3]. -- David /mmm\ /mmm\ /mmm\ (O o) (O O) (o o) U U u /mmm\ ||\ \\ / \\ . (- -) oOOo__oOOo _____oOOo ___________ ______u_oOOo___ ############ ######### ########### ################ (BAD ANSWER) (RETRY) (ONCE MORE) (Bored & Asleep) +----------------------------------------------------+ | Mail: david.bourgin@ufrima.imag.fr (David Bourgin) | | UFR IMA (French University - Grenoble) | From rboucher@access1.digex.net Tue Jun 28 15:08:00 1994 Status: RO X-VM-v5-Data: ([nil nil nil nil nil nil nil nil nil] ["978" "" "27" "June" "1994" "10:15:21" "-0400" "Ronald Boucher" "rboucher@access1.digex.net" nil "22" "Re: Infos from JPEG-Header" "^From:" nil nil "6" nil nil (number " " mark " Ronald Boucher Jun 27 22/978 " thread-indent "\"Re: Infos from JPEG-Header\"\n") nil] nil) Path: saips.cv.nrao.edu!hearst.acc.Virginia.EDU!darwin.sura.net!howland.reston.ans.net!news.intercon.com!news1.digex.net!access1!rboucher Newsgroups: comp.compression Organization: Express Access Online Communications, Greenbelt, MD USA Lines: 22 Message-ID: References: <2u6t6l$7mu@hpsystem1.informatik.tu-muenchen.de> NNTP-Posting-Host: access1.digex.net From: rboucher@access1.digex.net (Ronald Boucher) Subject: Re: Infos from JPEG-Header Date: 27 Jun 1994 10:15:21 -0400 soller@Informatik.TU-Muenchen.DE (Andrea Soller) writes: >Hi, >does anybody know about getting information (image size) from the >(compressed) JPEG-Header without decompressing the whole file with >"jpeg_decompress" ? >Thanks, Andrea ! Just scan the file, looking for a 0xFF byte which is immediately followed by a 0xC0 byte. The third byte after that is the number of bits (which should be 8). The next two bytes is the height of the image, a 16-bit word with the high-order byte first. The next two bytes is the width, again high-order byte first. The next byte is the number of colors (usually 3 for a color image, 1 for monochrome). If this whets your appetite for more, read the book _JPEG_ by Pennebaker and Mitchell, which contains a copy of the JPEG standard. ALso, if anyone is interested, I have C code for a JPEG dump utility which runs under DOS (and maybe other systems). -- Ron Boucher rboucher@access.digex.net