`United States Patent
`5,706,216
`[11] Patent Number:
`Reisch
`
`[45] Date of Patent: Jan. 6, 1998
`
`US005706216A
`
`[57]
`
`ABSTRACT
`
`A system for fi.ltering an image during data compression
`using a standard JPEG compression/decompression chip
`typically requires a separate spatial filter external to the chip.
`The spatial filter is composed of numerous shift registers.
`flipflops, multipliers and at least one adder. In oonuast, an
`image filtering system which filters in the frequency domain
`using the inventive IPEG compression chip modified for
`filtering in the frequency domain does not require the
`separate spatial filter and its many components. The modi-
`fied IPEG chip includes a raster to block converter which
`converts an image signal into 8x8 blocks, a DCT processor
`which converts the 8X8 blocks into DCT coefiicients, a
`multiplier which generates filtered DCI‘ coeflicients by
`multiplying predetermined filtering coeflicients times the
`DCT coefiicients, a quantizer which generates quantized
`blocks to a predetermined level stored in a visibility table by
`quantizing the filtered coeflicients, a zigzag scanner which
`generates a vector having the same number of elements as
`the quantized blocks, a run—1ength coder for determining the
`appropriate run—1ength according to en1:ropy encoding
`received from a preloaded Hutfrnan table, and a Variable
`length code packerlunpacker for compressing the entropy
`encoded vector. A block to raster converter is included to
`reformat decompressed data.
`
`[54] SYSTEM FOR DATA COMPRESSION OF AN
`IMAGE USING A JPEG COMPRESSION
`CIRCUIT MODIFIED FOR FILTERING IN
`THE FREQUENCY DOMAIN
`
`[76]
`
`Inventor: Michael L. Reiseh, 53 Nathan La.,
`Carlisle, Mass. 01741
`
`[21] Appl. No.: 508,745
`[22] Filed:
`Jul. 28, 1995
`
`Int. Cl.5
`[51]
`. G061?‘ 17/00
`[52] U.S. Cl.
`364I715.02
`
`[5 8] Field of Search
`. 364/514 R, 514 A,
`364/715.02, 728.01; 382/233, 262, 264;
`358/433
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`2/1996 Fan ................
`5,495,538
`10/1996 Weber et al.
`.
`5,563,718
`FOREIGN PATENT DOCUMENTS
`W095/15533
`6/1995 WEPO .
`
`
`
`Primary Examiner—E]]is B. Ramirez
`Attorney, Agent, or Firm—Robert A. Sabourin
`
`'7 Claims, 4 Drawing Sheets
`
`
`
`
`
`
`
`|—MFDIt¥D— _ _
`“PEG
`VISIBILITY
`
`
`
`IMAGE
`ct-up 4,-lg
`QUANTIZER
`TABLE
`
`
`
`5e
`“°§é’¢?€é°”
`
`ASTERCONVERTER
`
`400—
`
`ZIG ZAG
`512
`FILTER
`SCANNER
`COEFFICIENT
`Q
`MEMORY
`10.3
`
`
`
`
`
`
`RUN-LENGTH
`cooen
`
`526
`
`VARIABLE
`
`LENGTH CODE
`PACKERIUNPACKEFI
`gas
`
`
`
`
`
`
`
`
`IMAGE
`"A§_TE§ T0
`MEMORY
`O Kcomvemea
`
`
`4.02
`13:5
`
`
`DCT
`PROCESSOR
`
`$29
`
`COMPRESSED
`IMAGE
`MEMORY
`fl
`
`BASIS
`MATRIX
`MEMORY
`A29
`
`
`
`DESTINATION
`DEVICE
`
`HUFFMAN
`AM
` MICROCOMPUTER (LIC)
`TABLE
`
`13.0
`
`LLLQ
`
`
`
`
`Apple 1028
`
`U.S. Pat. 8,504,746
`
`Apple 1028
`U.S. Pat. 8,504,746
`
`
`
`M..._mm_
`
`6
`
`2,_I
`
`U
`
`6,m
`
`...m_mo_>m_ommflzo:m_:oo<a_mjmfimo<s__D..._>:.__m_m_>sIIIIIIIIIIlIiIIII_.w@,I_
`
`oflmmmwmm_mmzz<omm:mmEm>zoo_o<NonmmN:z<_._o
`
`
`
`
`Q3
`
`
`
`N,_:Ezm._-z_.ESo9.mm_.5<m4<EEmw_o<s__
`
`
`
`
`IWWII_mm_a_.Q3«E%_mmooomomwmoommmmwwwpmooE5:>mosm_s_
`
`
`
`H.m:m<_m<>m_m<mES:
`
`mmxo<n_z:Emxo<n_
`
`
`
`
`
`mosma_zo:<z:mmo_4_fln_m_mM.,.»m_...~m_..w_,___\,_oo>mW%ms_>m%m_>_
`
`
`_z<s_.._..5:
`
`5:_m._m<»eamm:.:n_s_ooomo_2II
`W_cl?—GE
`
`1IIIIIII52moan;
`
`2:
`
`
`
`
`U.S. Patent
`
`Jan. 6, 1998
`
`Sheet 2 of 4
`
`5,706,216
`
`VI.
`
`
`
`:-_.P+_Vx§
`
`ENmom
`
`
`
`2+...Sax?cum
`
`Emfilll
`
`vow
`
`
`
`n_O._n_n__._..._0
`
`
`
`n_O.En=n_u_D
`
`mmbeomm
`
`afi
`
`
`
`n_O.En:._u_Q
`
`Hu:Iw
`
`mm:m_omE
`
`mdlm
`
`52mo_m$N._o_u_
`
`
`
`
`
`
`
`
`U.S. Patent
`
`Jan. 6, 1998
`
`Sheet 3 of 4
`
`5,706,216
`
`
`
`5: § x
`§§§
`l\ <|' 1"
`2: :5 x
`
`
`E
`U)
`co <5
`Q55
`E -
`Q:
`9,
`
`:39
`X X X
`
`1- C\[
`
`“
`/'‘'\.»v‘‘''\
`cq cq _
`>,.:§><
`‘‘‘.‘N..
`-
`::S.\',SP,
`?.<3.£?£
`23:5;
`
`X X X
`
`E,
`X
`
`'
`
`\"’
`
`E
`< <
`F’:
`CO C:
`E
`§ 99
`E”
`U‘ [I
`V
`D.
`K
`V
`E
`
`X
`
`
`
`U.S. Patent
`
`Jan. 6, 1993
`
`Sheet 4 of4
`
`5,706,216 '
`
`>._._.__m__m_>
`
`m._m<»
`
`Jim
`
`0<N0_N
`
`mmzz<om
`
`wfi
`
`:Ezm._-z:_n_
`
`EMDOO
`
`amlw
`
`Z<_2n_n_DI
`
`m_._m<+
`
`m._m<_m<>
`
`
`
`MDOOI._.0Zw._
`
`mmv_o<n_z:Emxo<m
`
`mwm
`
`mmN_»z<:o
`
`ma
`
`O...505
`
`mm_.5<m
`
`mmEm>zoo
`
`NIQ
`
`om_..__oos_
`
`.omn=.
`
`
`
`fly.n:IO
`
`._.On_
`
`mm.5<m9
`
`._.
`
`Qmommmoomm
`
`v_OO:_m
`
`mmEm>zoo
`
`.3
`
`>m_os_ms_
`
`mm
`
`
`
`ommmmmmzoo>mos_ms_
`
`mo<s__m~|¢
`
`m_m<m
`
`X_I._.<_>_
`
`am63mmSn_s_ooomo__>_
`
`mmbm
`
`+zm__oEn_moo
`
`>mos_ms_
`
`wolv
`
`mo<s__
`
`zo:m5oo<
`
`mo_>mo
`
`am
`
`mo<2_
`
`>mosm_s_
`
`mum
`
`zoP<z_._.mm_o
`
`mo_>mo
`
`mm
`
`v._®_n_
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`5,706,216
`
`1
`SYSTEM FOR DATA COMPRESSION OF AN
`IMAGE USING A JPEG COMPRESSION
`CIRCUIT MODIFIED FOR FILTERING IN
`THE FREQUENCY DOMAIN
`FIELD OF THE INVENTION
`
`This invention relates generally to improved circuitry for
`image processing and more particularly to a compression
`circuit using a JPEG (Joint Photographic Experts Group)
`chip modified for filtering in the frequency domain without:
`the use of a separate spatial filter.
`BACKGROUND OF THE INVENTION
`
`10
`
`2
`
`Oftentimes filtering of an image is desirable to optimize
`the appearance of the image. For example, filtering by
`sharpening enhances blurry images by bringing out high
`frequency components that represent edges in the image,
`whereas filtering by smoothing softens or blurs the edges of
`the image. When the image is segmented into blocks of data
`prior to filtering, blocking artifacts can occur along the
`borders of adjacent blocks. These blocldng artifacts, too, can
`be removed from the image by overlapping the adjacent
`blocks prior to filtering.
`Compressing and filtering an image typically utilizes
`standard JPEG hardware, i.e. a standard JPEG compression
`chip, a spatial filter, a microcomputer and memory.
`However, it has been discovered that the standard JPEG chip
`can be modified as described hereinafter to allow filtering of
`the image in the frequency domain, which obviates the need
`for a separate spatial filter. The modified JPEG chip results
`in both cost savings and miniaturization of circuitry.
`Consequently, it is a primary object of this invention to
`provide an image processing system including JPEG com-
`pression chip modified to allow filtering of an image in the
`frequency domain without the need for a separate spatial
`filter.
`
`Other objects of the invention will, in part, appear here-
`inafter and, in part, be obvious when the following detailed
`description is read in conjunction with the drawings.
`SUMMARY OF THE INVENTION
`
`A system for filtering an image during data compression
`using a standard JPEG compression chip typically requires
`a separate spatial filter external to the chip. The spatial filter
`is composed of numerous shift registers, flip-flops, multi-
`pliers and at least one adder. In contrast, an image filtering
`system using the inventive JPEG compression chip modified
`for filtering in the frequency domain does not require a
`separate spatial filter and its many components. The modi-
`fied JPEG chip includes a raster to block converter which
`converts an image signal into 8><8 blocks, a DCI‘ processor
`which converts the 8x8 blocks into DCI‘ coefficients, a
`multiplier which generates a filtered signal by multiplying
`predetermined filtering coefficients times the DCT
`coefficients, a quantizer which generates a quantized signal
`by dividing predetermined values stored in a visibility table
`into the filtered signal, a zigzag scanner which generates a
`vector having the same number of elements as the quantized
`blocks, a run-length coder for producing a run-length code
`of the vector, and a variable length code packer for receiving
`and coding the rim-length code in accordance with a pre-
`determined Huffman code retrieved from a Huffman table to
`produce a compressed, filtered signal. A block to raster
`converter is included in the modified JPEG chip to reformat
`decompressed data.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The aforementioned aspects and other features of the
`invention are described in detail in conjunction with the
`accompanying drawings in which the same reference numer-
`als are used throughout for denoting corresponding elements
`and wherein:
`
`Image processing can occur in either the spatial domain or
`the frequency domain. An image is said to reside in the
`spatial domain when the values of the parameters used to
`describe it, such as brightness, have a direct correspondence
`with spatial location. In the frequency domain, the equiva-
`lent to an image in the spatial domain may be represented by
`a series of frequency components in the form of trigono-
`metric functions which, when summed for each image data
`point (i.e., pixel) yield the value of the parameter used to
`characterize the image of that image data point in the spatial
`domain, and such a representation may be extended to cover
`all image data points of the image.
`In the spatial domain, original image data may be con-
`veniently represented as image data points in a first spatial
`matrix designated, s(j,i), for a two-dimensional case where
`the lower case, s, designates the spatial domain, i is the index
`of rows and j is the index of columns. In the frequency
`domain, matrices can also be used to mathematically
`describe an image as a set of the transform coeflicients (also
`referred to as frequency coefficients) which represent fre-
`quency data in a transform matrix conventionally
`designated, S(v,u), where the upper case, S, designates the
`frequency domain, u is the number of rows, and v is the
`number of columns.
`
`Spatial image data points may be transformed to fre-
`quency space using transformations such as Fourier trans-
`forms or discrete cosine transforms (DCI‘s). When the
`transformation involved is a discrete cosine transformation,
`the frequency domain is referred to as the DCI‘ domain and
`the frequency coeflicients are referred to as DCI‘ coefli-
`cients. Conventionally, transforming data from the spatial
`domain to the frequency domain is referred to as a forward
`transformation, whereas transforming data from the fre-
`quency domain to the spatial domain is referred to as an
`inverse transformation. Hence, a forward discrete cosine
`transformation is defined as a transform that maps an image
`from the original image data points s(j,i) in the spatial
`domain to DCI‘ coeificients S(v,u) in the DCI‘ domain
`according to the basis function of the forward DCI‘, whereas
`an inverse discrete cosine transformation (or IDCI‘) is
`defined as a transform that maps the DCT coefiicients S(v,u)
`from the DCI‘ domain to reconstructed image data points
`s(j ,i) in the spatial domain according to the basis function of
`the IDCI‘.
`The use of DCI‘ and IDCI‘ transforms for compressing or
`decompressing images to reduce memory storage require-
`ments and/or increase transfer and computational speeds is
`well-known and, in fact, the practice has been adopted as
`standard in industry by The Joint Photographic Experts
`Group (JPEG), which was created as part of a joint effort of
`the Consultative Committee on International Telegraphy and
`Telephony (CCl'I'I') and The International Standards Orga-
`nization (ISO). Today, many image processing programs
`confonn to JPEG standards.
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`FIG. 1 is a block diagram of a system for compressing and
`filtering an image using a standard JPEG compression chip
`and a spatial filter;
`FIG. 2 is a detailed schematic block drawing of the spatial
`filter 106 of FIG. 1;
`FIG. 3A is an mxn (read “In by n”) matrix representation
`of a digital image to be filtered;
`
`65
`
`
`
`3
`
`4
`
`5,706,216
`
`FIG. 3B is a representation of a 3X3 filter kernel useful for
`filtering the image represented in FIG. 3A; and
`FIG. 4 is a schematic block diagram of a system for
`compressing and filtering an image according to the inven-
`tion using a JPEG chip modified for filtering in the fre-
`quency domain without the need for a separate spatial filter.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`
`The present invention is directed towards a system that
`uses an improved JPEG compression chip modified for
`faltering a digital image in the frequency domain Without the
`need for a separate spatial filter. 'I‘urning to the filtering
`system of FIG. 1, an image acquisition device 100 (i.e. an
`image signal source), such as but not limited to an electronic
`still camera, a camcorder, a scanner, a charge—coupled
`device (CCD), or a charge-injected device (CID), captures
`and converts an image of a scene (not shown) into spatially
`correlated digital image data points or pixels representing
`some predetermined characteristic of the image, such as
`luminance, chrominance, etc. In this particular example, the
`image acquisition device 100 is a scanner which scans the
`scene to produce the image in raster format. The scanned
`image is stored in image memory 102, then filtered in the
`spatial domain in spatial filter 106 by multiplying predeter-
`mined filter coeflicients received from filter coefiicient
`memory 108 times the image data points received from the
`image memory 102. The spatially filtered image data points
`are then received by the standard JPEG circuit 132 (to be
`explained in detail hereinafter) where compression and
`decompression take place. A basis memory 129 is used to
`store predetermined DCT and IDCI‘ basis coefiicients nec-
`essary for DC1‘ processing. After the spatially filtered image
`is compressed in JPEG circuit 132. the compressed image is
`stored in compressed image memory 122.
`To reconstruct the filtered image to a destination appli-
`cation or device 104 (such as, but not limited to, a printer,
`memory or display). the compressed image is retrieved from
`memory 122, decompressed in the standard JPEG circuit
`132, and transmitted through the spatial filter 106 in pass-
`through mode where the reconstructed image data points are
`finally stored in the image memory 102 before being trans-
`ferred to the destination device 104. A microcomputer 110
`controls various components of the image filtering system as
`shown. Also, although individual memories 108, 122 and
`129 are portrayed, a single memory could just as easily be
`employed with suitable addressing.
`The filtering system of FIG. 1 can be more clearly
`understood in view of the schematic block diagram of FIG.
`2 which details the components of the spatial filter 106.
`Filter 106 generally uses a two-dimensional filter kernel
`which must be convolved spatially with the image. FIG. 3A
`depicts the image as an m><n matrix of image data points, and
`FIG. 3B depicts an exemplary predetermined nine point
`filter kernel. The spatial filter 106 of FIGS. 1 and 2 includes
`two shift registers 200, 202, six delay type flip-flops 204,
`206, 208, 210, 212, 214, 216, nine multipliers 216, 218, 220,
`222, 224, 226, 228, 230, 232 and an adder 234. In the present
`example, using the filter kernel of FIG. 3B, nine image data
`points at a time are processed in the spatial filter 106. As will
`be apparent to those skilled in the art, the filter architecture
`of FIG. 2 as used with the filtering system of FIG. 1 requires
`N2 multipliers and an N2 input adder for an NXN kernel size,
`where N is a predefined integer. Thus, a spatial falter for
`processing an 8><8 block of image data points in accordance
`with JPEG standards would require 64 multipliers, numer-
`
`10
`
`20
`
`25
`
`30
`
`35
`
`45
`
`S0
`
`55
`
`65
`
`ous D flip-flops and shift registers, and a 64 input adder. A
`filter with fewer multipliers would be unable to process the
`8x8 blocks at the system clock frequency rate.
`The image data points received from image memory 102
`are input into spatial filter 106 in raster format. Shift
`registers 200, 202, and delay flip-flops 204, 206, 208, 210,
`212, 214 provide proper timing for the pixel stream in the
`vertical and horizontal directions, respectively, so that all
`nine inputs to the adder 234 will occur on the same dock
`pulse. Specifically, kernel element K1 is multiplied in mul-
`tiplier 216 times image data point X(i+l,
`j—1), kernel
`element K2 is multiplied in multiplier 218 times image data
`point X(i+l, j), kernel element K3 is multiplied in multiplier
`220 times X(i+l, j+1), and so forth where i and j are integer
`indices. The filter coeflicients may be hardwired, but are
`usually stored in data registers which must be loaded from
`the external filter coeflicient memory 108 (see FIG. 1). The
`ability to load the kernel from storage provides flexibility
`and makes the implementation of adaptive filtering possible,
`which is important for certain applications. In the current
`example, the products of the nine multipliers 216 through
`232 are concatenated in adder 234 to yield filter output
`Y(i,j)-
`The compression operation of the JPEG circuit 132 begins
`when the raster to block converter 114 converts the filter
`output Y(i,j) to block format, i.e. a plurality of (overlapped
`or unoverlapped) 3X8 element arrays of filtered image data
`points. Aforward DCI‘ is performed on each filtered array of
`image data points in DCI‘ processor 120 to generate a matrix
`of DCT coeflicients by multiplying the array of filtered
`image data points times the predetermined forward DCI‘
`basis matrix stored in basis matrix memory 129. In this
`example, each DCI‘ coeflicient is represented by eight bits,
`whereby the DCT coeflicients in the upper left-hand corner
`of the DCT matrix represent direct current and low fre-
`quency harmonics to which the human eye is most sensitive.
`The DCI‘ coeflicients are quantized, i.e. scaled, into quan-
`tized blocks in quantizer 118 so that the quantizer 118 retains
`most of the low frequency information and truncates much
`of the high frequency harmonics as unwanted noise, thus
`resulting in compression. The level of quantization is pre-
`determined and stored in the quantization table 116, also
`called a visibility table, which contains entries for determin-
`ing how many bits should be assigned to each DCI‘ coef-
`ficient during quantization. The visibility table 116 can be
`determined empirically or by analyzing eye threshold sen-
`sitivity.
`Each quantized block is input and converted by the zigzag
`scanner 124 (the operation of which is well known in the art)
`into a vector having the same number of elements as the
`quantized block. ‘The vector from zigzag scanner 124 is
`processed in run-length coder 126 to determine the appro-
`priate run-length code according to the Huffman code, i.e.
`entropy coding, received from preloaded Huifman table 130.
`The variable length code packer/unpacker 128 compresses
`the entropy encoded vector. Finally, the compressed data is
`stored in compressed image memory 122.
`The compressed, filtered image stored in the compressed
`image memory 122 is reconstructed by first, unpacking in
`the variable length code packer/unpacker 128 to generate
`decompressed data. The decompressed data then passes
`through the run-length coder 126 to the zigzag scanner 124
`where it is reinstated into block format. The block formatted
`data from the zigzag scanner 124 then passes through the
`quantizer 118 to the DCI‘ processor 120 where an IDCI‘ is
`performed to generate a block of IDCI‘ coeflicients by
`multiplying the block formatted data times the predeter-
`
`
`
`5,706,216
`
`10
`
`20
`
`5
`mined IDCI‘ basis coeflicients stored in basis matrix
`memory 129. In the case of adjacent overlapped blocks,
`overlapped IDCI‘ coeflicients corresponding to overlapped
`sections of the adjacent overlapped blocks are discarded by
`the DCT processor 120. The IDCI‘ coefficients are converted
`to raster format in block to raster converter 112, then the
`converted coefficients pass through the spatial filter 106
`without processing and are stored in image memory 102
`prior to being transmitted to the destination device 104. Of
`course, the microcomputer 110 controls the various compo-
`nents of the image filtering system.
`FIG. 4 illustrates a preferred embodiment of a data
`compression and filtering system according to the invention
`which processes the image without the use of a separate
`spatial filter. Using the JPEG chip 432 modified for filtering
`in the frequency domain, filtering typically occurs prior to
`compression (as in the preferred embodiment explained
`hereinafter), although the chip could be easily further altered
`as understood by those skilled in the art to allow compres-
`sion prior to filtering if desired. Additionally, the chip 432
`could be used for compression only, without any filtering.
`The modified IPEG chip 432 requires a single multiplier
`421 placed in the data path between the DCI‘ processor 420
`and the quantizer 418. The multiplier 421 multiplies the
`DCI‘ coeflicients times the predetermined frequency domain
`filter coefficients stored in filter coefficient memory 408,
`yielding a filtered signal. The multiplier 421 includes a
`pass-through mode to ensure that data can flow unmodified
`back and forth between the quantizer 418 and the DCI‘
`processor 420, allowing the modified IPEG circuit 432 to be
`operated solely for compression without filtering, if desired.
`The image filtering circuit of FIG. 4, including the JPEG
`chip 432 modified for filtering in the frequency domain,
`facilitates filtering of a spatial image in the frequency .
`domain in a manner similar to a mathematical convolution
`in the spatial domain using a discrete odd cosine transform
`of overlapped blocks of image data points as described and
`taught in International Application No. PCI‘IUS94l13617
`filed 29 Nov. 1994 by Wober and Reisch, herein incorpo-
`rated by reference in its entirety. The circuit of FIG. 4 is also
`amenable to filtering unoverlapped blocks of image data
`points.
`In the overlapped mode, the convolution (i.e. filtering in
`the frequency domain in a manner similar to performing a
`mathematical convolution in the spatial domain) is math-
`ematically exact and requires three passes through the
`modified JPEG chip 432 to produce a filtered and com-
`pressed image. On the first pass, the overlapped blocks are
`frequency weighted by the filter response, compressed with-
`out loss, and stored in the compressed image memory 422 as
`the filtered signal of blocks of frequency coeflicients. The
`degree of overlap is determined by the size of the preselected
`filter kernel, which is the same as for the fast convolution
`FFI‘ (fast fourier transform) algorithm described by E. 0.
`Brigham in ‘The Fast Fourier Transform”; Prentice-Hall
`1974, Chapter 13, section 13-4, pages 217-221. Lossless
`compression is achieved by adjusting the values of the
`visibility table 416 so that none of the DCT coeflicients of
`the filtered blocks is truncated during quantization. This
`ensures that the filtered blocks can be recovered exactly.
`Also, the values of the quantization or visibility table 416
`can be set as either lossless or lossy depending on the
`application. The performance of the run length coder 426
`and the variable length code packerlunpacker 428 is such
`that compression ratios of 2:1 to 4:1 are possible depending
`upon the image entropy desired.
`On the second pass in the overlapped mode, the data flow
`is reversed. That is, the blocks of frequency coeificients
`
`30
`
`45
`
`50
`
`55
`
`65
`
`6
`
`stored in the compressed image memory 422 are decoded
`and inverse transfonned back to the spatial domain. The
`compressed blocks of frequency coeflicients are retrieved
`from memory 422 and decompressed in unpacker 428. The
`coeflicients then pass through the run-length coder 426 to the
`zigzag scanner 424 where the coeflicients are reinstated into
`block format. The block formatted coefficients from the
`zigzag scanner 424 then pass through the quantizer 418 and
`the multiplier 421 without processing to the DCI‘ processor
`420 where an ]DCI‘ is performed to generate a block of
`IDCT coefficients by multiplying the block formatted data
`coefficients times the predetermined IDCI‘ basis coefiicients
`stored in basis matrix memory 429. Overlapped IDCI‘
`coefficients corresponding to overlapped sections of the
`adjacent overlapped blocks are discarded by the DCI‘ pro-
`cessor 420. The remaining IDCI‘ coefiicients are converted
`to raster format in block to raster converter 412, then the
`converted coefficients are stored in image memory 402.
`To generate the final compressed and filtered coeflicients
`of the image in the overlapped mode requires a third pass
`through the modified JPEG compression chip 432. The
`coefficients representing the image have already been fil-
`tered in the first pass and predetermined decompressed data
`corresponding to overlapped portions of the reconstructed
`blocks have been discarded during the second pass. The
`third pass is solely concerned with the compression of the
`remaining filtered coeflicients into the frequency domain.
`For the third pass, the blocks of reconstructed image data
`points from image memory 402 are not overlapped. The
`coefficients are sent from image memory 402 to raster to
`block converter 435 which converts the coeflicients into 8X8
`non-overlapped blocks. The discrete cosine transform of
`each block is taken in DCI‘ processor 420, then the DCI‘
`coefiicients pass through the multiplier 421 (since no addi-
`tional filtering is necessary) to quantizer 418. The DCT
`coeflicients are quantized into quantized blocks in quantizer
`418 so that the quantizer 418 retains most of the low
`frequency infonnation and truncates much of the high
`frequency harmonics as unwanted noise. The level of quan-
`tization is predetermined and stored by the values in the
`visibility table 416, which can be set as either lossless or
`lossy depending on the application and, which contains
`entries for determining how many bits should be assigned to
`each DCT coeflicient dining quantization.
`Each quantized block is input and converted by the zigzag
`scanner 424 into a vector having the same number of
`elements as the quantized blocks. The vector from zigzag
`scanner 424 is processed in run-length coder 426 to deter-
`mine the appropriate run-length code according to the Huff-
`man code,
`i.e. entropy coding, received from preloaded
`Huifman table 430. The variable length code packer!
`unpacker 428 compresses the entropy encoded vector.
`Finally, the compressed data is stored in compressed image
`memory 422.
`The compressed, filtered image stored in the compressed
`image memory 422 can be reconstructed by first, unpacking
`in the variable length code packer/unpacker 428 to generate
`decompressed data. The decompressed data then passes
`through the run-length coder 426 to the zigzag scanner 424
`where it is reinstated into block format. The block formatted
`data from the zigzag scanner 424 then passes through the
`quantizer 418 and the multiplier 421 without processing to
`the DCI‘ processor 420 where an IDCT is performed in
`accordance with an IDCI‘ basis matrix stored in the basis
`matrix memory 429 to generate a block of IDCI‘ coefli-
`cients. The IDCI‘ coefficients are converted to raster format
`in block to raster converter 412, then the converted coefli-
`
`
`
`5,706,216
`
`7
`cients are stored in the image memory 402 prior to being
`transmitted to the destination application or device 404. The
`microcomputer 410 controls the various components of the
`image filtering system.
`For many applications, filtering an image to produce an
`exact convolution is unnecessary. Alternatively, blocks of
`non-overlapped image data can be filtered and otherwise
`processed by a single pass (rather than three passes as
`described above) through the modified JPEG chip 432. The
`single pass method results in a tradeoff of increased pro-
`cessing speed and compromised image quality. The image
`data points stored in image memory 402 are sent to raster to
`block converter 435 which converts the data into 8><8
`non-overlapped blocks. A DCI‘ of each block is taken in
`DCI‘ processor 420 to generate DCT coefficients. A filtered
`signal of filtered coeflicients is generated in multiplier 421
`by multiplying the DCI‘ coefficients times predetermined
`filter coeflicients stored in filter coeificient memory 408. The
`filtered coeflicients are quantized into quantized blocks in
`quantizer 418 so that the quantizer 418 retains most of the
`low frequency infomnation and truncates much of the high
`frequency harmonics as unwanted noise. The level of quan-
`tization is predetermined and stored by the values in the
`visibility table 416, which can be set as either lossless or
`lossy depending on the application and, which contains
`entries for determining how many bits should be assigned to
`each DCI‘ coeflicient during quantization.
`Each quantized block is input and converted by the zigzag
`scanner 424 into a vector having the same number of
`elements as the quantized blocks. The vector from zigzag
`scanner 424 is processed in run-length coder 426 to deter-
`mine the appropriate run-length code according to the Huff-
`man code,
`i.e. entropy coding, received from preloaded
`Huffman table 430. The variable length code packerl
`unpacker 428 compresses the entropy encoded vector.
`Finally, the compressed data is stored in compressed image
`memory 422.
`The compressed, filtered image stored in the compressed
`image memory 422 can be reconstructed by first, unpacking
`in the variable length code packer/unpacker 428 to generate
`decompressed data. The decompressed data then passes
`through the run-length coder 426 to the zigzag scanner 424
`where it is reinstated into block format. The block formatted
`data from the zigzag scanner 424 then passes through the
`quantizer 418 and the multiplier 421 without processing to
`the DCT processor 420 where an IDCT is performed to
`generate a block of IDCI‘ coetficients stored in the basis
`matrix memory 429. The IDCI‘ coeflicients are converted to
`raster format in block to raster converter 412, then the
`converted coefficients are stored in _the image memory 402
`prior to being transmitted to the destination device 404. The
`microcomputer 410 controls the various components of the
`image filtering system.
`It is to be understood that the above described embodi-
`ments are merely illustrative of the present invention and
`represent a limited number of the possible specific embodi-
`ments that can provide applications of the principles of the
`invention. Numerous and varied other arrangements may be
`readily devised in accordance with these principles by those
`slrilled in the art without departing from the spirit and scope
`of the invention as claimed
`What is claimed is:
`1. A JPEG compatible compression and filtering chip for
`operation in a frequency domain, said chip comprising:
`a raster to block converter for receiving an electronic
`signal representing an image and converting said elec-
`tronic signal from raster to block format;
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`8
`basis matrix input means for receiving a forward DCI'
`basis matrix from an external basis matrix memory;
`a discrete cosine transform (DCT) processor for receiving
`said block formatted electronic signal from the raster to
`block converter, receiving said forward DCI‘ basis
`matrix via said basis matrix input means, and perform-
`ing a discrete cosine transform of said block formatted
`electronic signal to generate DCI‘ coeflicients;
`a multiplier for receiving said DCT coefiicients, receiving
`said predetermined frequency filter coeflicients, and
`multiplying said DCT coeflicients and said predeter-
`mined frequency domain filter coeflicients to generate
`a filtered signal;
`a quantizer for receiving predetermined quantization val-
`ues from a visibility table, receiving said filtered signal,
`dividing said predetermined quantization values into
`said filtered signal to produce a quotient, and truncating
`the quotient to a predefined accuracy to generate a
`quantized signal;
`a zigzag scanner for producing a vector representing said
`quantized signal;
`a run-length coder for producing a run-length code of said
`vector; and
`a variable length code packer for receiving and coding
`said run-length code in accordance with a predeter-
`mined Huifman code retrieved from a Hufl‘man table to
`
`produce a compressed, filtered signal.
`2. The JPEG compatible compression and filtering chip of
`claim 1, further comprising:
`means for unpacking said compressed, filtered signal to
`reproduce said run-length code;
`means for reproducing said vector from said reproduced
`rim-length code;
`means for reproducing said quantized signal from said
`reproduced vector;
`means for reproducing said filtered signal from said
`reproduced quantized signal;
`means for receiving an inverse basis matrix from said
`basis matrix memory, receiving said reproduced filtered
`signal, and performing an inverse discrete cosine trans-
`form (IDCI‘) of said reproduced filtered signal
`to
`generate lDCI' coeflicients; and
`a block to raster converter for receiving and converting
`said IDCI‘ coeflicients from block to raster format to
`generate a reproduced said electronic signal.
`3. The JPEG compatible compression and filtering chip of
`claim 2, wherein said block formatted electronic signal
`comprises adjacent overlapped blocks, and wherein said
`means for performing an DCT further comprises means for
`discarding overlapped IDCT coeflicients corresponding to
`overlapped sections of said adjacent overlapped blocks.
`4. A sys