Source: http://www.google.com/patents/US6775413?dq=6666377
Timestamp: 2014-03-17 05:01:37
Document Index: 774094749

Matched Legal Cases: ['Application No; 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No; 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No; 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09', 'Application No: 09']

Patent US6775413 - Techniques to implement one-dimensional compression - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsEmbodiments of the present invention are disclosed in which one dimensional image compression, such as for bi-level images, is implemented. An integrated circuit includes digital logic circuitry and digital memories. The digital logic circuitry and digital memories are coupled so as to implement one...http://www.google.com/patents/US6775413?utm_source=gb-gplus-sharePatent US6775413 - Techniques to implement one-dimensional compressionAdvanced Patent SearchPublication numberUS6775413 B1Publication typeGrantApplication numberUS 09/666,486Publication dateAug 10, 2004Filing dateSep 18, 2000Priority dateSep 18, 2000Fee statusPaidAlso published asWO2002023888A2, WO2002023888A3Publication number09666486, 666486, US 6775413 B1, US 6775413B1, US-B1-6775413, US6775413 B1, US6775413B1InventorsTinku AcharyaOriginal AssigneeIntel CorporationExport CitationBiBTeX, EndNote, RefManPatent Citations (44), Non-Patent Citations (39), Referenced by (4), Classifications (6), Legal Events (4) External Links: USPTO, USPTO Assignment, EspacenetTechniques to implement one-dimensional compressionUS 6775413 B1Abstract Embodiments of the present invention are disclosed in which one dimensional image compression, such as for bi-level images, is implemented. An integrated circuit includes digital logic circuitry and digital memories. The digital logic circuitry and digital memories are coupled so as to implement one dimensional compression of a bit stream to be applied to the digital logic circuitry and digital memories without performing arithmetic operations. One of the digital read only memories stores, for a plurality of run lengths, a memory address for a make up code and a memory address for a termination code for the respective run lengths.
RELATED APPLICATION This patent application is related to concurrently filed U.S. patent application Ser. No. 09/664,131, titled �Techniques to Implement Two-Dimensional Compression,� by Acharya, assigned to the assignee of the present invention and herein incorporated by reference.
BACKGROUND The present disclosure is related to one-dimensional image compression, such as for bi-level images.
As is well-known, a facsimile machine scans a document line by line and converts each line to alternating black and white dots. The resulting document image is referred to as a bilevel image because each pixel is represented by a single bit and its value may be either 0 to represent a black dot or 1 to represent a white dot or pixel. A combination of run-length encoding and modified Huffman coding has been found suitable to compress such bi-level images. The International Telecommunications Union (ITU, formerly known as Consultative Committee on International Telephone and Telegraph�CCITT) has, therefore, provided a number of standards or specifications suitable to compressing such bi-level facsimile images. See, for example, Hunter, et. al., International Digital Facsimile Coding Standards, Proceedings of the IEEE Vol. 68, No. 7, July 1980, pages 854-857. The CCITT Group 3 is one such standard and is applied to facsimile or �fax� machines. The recommendations for Group 3 has two coding schemes�one dimensional and two dimensional. In the one dimensional scheme, the coding of each scan line is performed independently of any other line. Although this standard was recommended for facsimile machines, the approach is also suitable for coding bi-level document images in various other applications, such as, for example, photocopying machines, scanners, etc.
DETAILED DESCRIPTION In the following detailed description, numerous specific details are set forth in order to provide a thorough understanding of the invention. However, it will be understood by those skilled in the art that the present invention may be practiced without these specific detailed. In other instances, well-known methods, procedures, components and circuits have not been described in detail so as not to obscure the present invention.
FIG. 1 is a table illustrating codes that may be employed when complying with the aforementioned standard or specification. When one dimensional compression coding is applied in a manner to comply with the aforementioned standard, a scan line is compressed by coding the length of each one of alternating �runs� of black or white pixels using a pre-specified static Huffman code. Separate code tables are used for black and white runs because the respective statistical distributions are different. Each code table may represent a run-length of up to 1,728 pixels, the maximum length of a scan line in the bi-level image in this particular embodiment. The first 64 entries of the code table is a Huffman code of run-length 0 to 63, respectively. The 64 codes are referred to in this context as termination codes (TC). A binary code of a run-length (L) bigger than 63 is represented using two parts or two codes, a makeup code (MUC) and a termination code (TC). The run length (L) is represented by
FIG. 2 is a schematic diagram illustrating an example of the bit stream that may be applied to an embodiment of a circuit to implement one-dimensional compression. It is generally assumed by default that there is an imaginary �white� pixel (1) at the left end of the scan line. Hence, the example scan line in FIG. 3 may be encoded as the following sequence of runs: four white pixels (including the imaginary one), five black pixels, two white pixels, three black pixels, and one white pixel. The coding of the bit stream, here, is ended by an end of line (EOL) code. It is noted, of course, that an alternate default to the left of the scan line, such as a �black� pixel, may be employed in alternative approaches. For this particular bit stream or scan line, the binary code is:
Although only a few entries are shown of the pre-specified code table in FIG. 2, the entries are well-known and defined in the standard. It is, likewise noted that the code to represent the EOL is �0000000001.�
It is noted that a host of one-dimensional compression processes may be implemented in this particular embodiment in accordance with the invention or in other embodiments in accordance with the invention. Nonetheless, this particular embodiment has the capability to comply with the one-dimensional coding scheme of CCITT Group 3 bi-level compression standard. Again, although the invention is not limited in scope in this respect, one of the digital read only memories comprises, for a plurality run-lengths, a memory address for the makeup code (MUC) and a memory address for the termination code (TC) for the particular run-length. It is noted, in this particular embodiment, that the digital read only memory, here 330, provides these memory addresses, here, a combination of MUCA�Makeup Code Address and TCA�Termination Code Address, for the combination of a particular run-length and a particular color. Likewise, for this particular embodiment, digital read only memory 340 comprises termination codes for the respective termination code addresses (TCA) and digital read only memory 350 comprises makeup codes for the respective makeup code addresses (MUCA).
In this embodiment, if the two bits of the bit stream compared by XOR 370 are identical, 370 provides a �0� output signal. However, once an input bit is received having a binary value the opposite of immediately previous bit, 370 provides a �1� output signal. Therefore, 370, in this particular embodiment, signals the end of a run of pixels of a particular color, here, either black or white. The output signal of 370 is applied to toggle switch 360. In this particular embodiment the switch is implemented also using a flip-flop, here a Toggle or T flip-flop, although, of course the invention is not limited in scope in this respect. The output signal of 360 is toggled when an output signal from 370 applied to 360 comprises a �1.� In this particular embodiment, 360 and 380 are initialized to �1� to indicate that initially the runs comprise white pixels, although, an alternative embodiment having a different initialization may be employed. Therefore, when toggle switch 360 toggles to �0,� this indicates the end of a run of white pixels and the beginning of a run of black pixels. The output signals of toggle switch 360 remain �0� until the end of the run of black pixels is detected, as indicated by the output signal of 370, in which case toggle switch 360 toggles back to �1.� Therefore, in this embodiment, in addition to signaling the end of a run of pixels of a particular color, toggle switch 360 also signals the color of the run, where, in this particular embodiment, 0 indicates a black run and 1 indicates a white run, although, of course, the invention is not limited in scope in this respect.
In this particular embodiment, binary counter 320 comprises a binary up counter, although, of course, the invention is not limited in scope in this respect. Counter 320, as illustrated in FIG. 3, counts the length of the run of a particular color. At the end of the run, that is, in this embodiment, when the output signal of gate 370 is �1,� counter 320 is reset to �0.� When the run ends, the length of the run is the output signal of counter 320, which, in this particular embodiment, is applied to form an address to a memory location of digital read only memory 330, which, in this particular embodiment, operates as a �look up table� (LUT). In addition to applying the output signal of the counter 320 to memory 330, toggle switch 360 applies an output signal to signal the color of the run, in this particular embodiment, 0 for black and 1 for white. A combination of these two signals from 320 and 360 indicates an address in memory 330 to be read and loaded into register 410. Likewise, as illustrated in FIG. 3, for this particular embodiment, the output signal of 370 is also employed as a �load� signal for register 410. Therefore, when the output signal of 370 comprises a 1, a makeup code address (MUCA) and termination code address (TCA) of the corresponding run length of pixels is loaded from memory 330 into register or buffer 410. Then, as illustrated further in FIG. 3, memories 350 and 340, respectively, provide a makeup code (MUC) and termination code (TC), and corresponding length information. Both MUC and TC comprise variable-length codes. Therefore, this information is employed to properly output the code. The makeup code address and termination code address, previously loaded into register 410, are respectively applied to memories 350 and 340. Memories 350 and 340 provide these codes as output signals which are then packed and output by a pack and output circuit, such as illustrated in FIG. 3.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4040093Sep 8, 1975Aug 2, 1977Kokusai Denshin Denwa Kabushiki KaishaSystem for coding information change picture elements in facsimile signalUS4185303Nov 30, 1978Jan 22, 1980Bell Telephone Laboratories, IncorporatedRun length encoding of facsimile picturesUS4245257Jul 30, 1979Jan 13, 1981Kokusai Denshin Denwa Kabushiki KaishaTransmission method and system for facsimile signalUS4486784Dec 27, 1982Dec 4, 1984International Business Machines CorporationImage compression systemsUS4558371Aug 19, 1983Dec 10, 1985Advanced Micro Devices, Inc.Method and device for two-dimensional facsimile codingUS4760461Feb 24, 1987Jul 26, 1988Kabushiki Kaisha ToshibaBinary data compression and expansion processing apparatusUS5196945Sep 4, 1990Mar 23, 1993Motorola, Inc.Data compression/expansion circuit for facsimile apparatusUS5875122Dec 17, 1996Feb 23, 1999Intel CorporationIntegrated systolic architecture for decomposition and reconstruction of signals using wavelet transformsUS5995210Aug 6, 1998Nov 30, 1999Intel CorporationIntegrated architecture for computing a forward and inverse discrete wavelet transformsUS6009201Jun 30, 1997Dec 28, 1999Intel CorporationEfficient table-lookup based visually-lossless image compression schemeUS6009206Sep 30, 1997Dec 28, 1999Intel CorporationCompanding algorithm to transform an image to a lower bit resolutionUS6047303Aug 6, 1998Apr 4, 2000Intel CorporationSystolic architecture for computing an inverse discrete wavelet transformsUS6091851Nov 3, 1997Jul 18, 2000Intel CorporationEfficient algorithm for color recovery from 8-bit to 24-bit color pixelsUS6094508Dec 8, 1997Jul 25, 2000Intel CorporationPerceptual thresholding for gradient-based local edge detectionUS6108453Sep 16, 1998Aug 22, 2000Intel CorporationGeneral image enhancement frameworkUS6124811Jul 2, 1998Sep 26, 2000Intel CorporationReal time algorithms and architectures for coding images compressed by DWT-based techniquesUS6130960Nov 3, 1997Oct 10, 2000Intel CorporationBlock-matching algorithm for color interpolationUS6151069Nov 3, 1997Nov 21, 2000Intel CorporationDual mode digital camera for video and still operationUS6151415Dec 14, 1998Nov 21, 2000Intel CorporationAuto-focusing algorithm using discrete wavelet transformUS6166664Aug 26, 1998Dec 26, 2000Intel CorporationEfficient data structure for entropy encoding used in a DWT-based high performance image compressionUS6178269Aug 6, 1998Jan 23, 2001Intel CorporationArchitecture for computing a two-dimensional discrete wavelet transformUS6195026Sep 14, 1998Feb 27, 2001Intel CorporationMMX optimized data packing methodology for zero run length and variable length entropy encodingUS6215908Feb 24, 1999Apr 10, 2001Intel CorporationSymmetric filtering based VLSI architecture for image compressionUS6215916Feb 4, 1998Apr 10, 2001Intel CorporationEfficient algorithm and architecture for image scaling using discrete wavelet transformsUS6229578Dec 8, 1997May 8, 2001Intel CorporationEdge-detection based noise removal algorithmUS6233358Jul 13, 1998May 15, 2001Intel CorporationImage compression using directional predictive coding of the wavelet coefficientsUS6236433Sep 29, 1998May 22, 2001Intel CorporationScaling algorithm for efficient color representation/recovery in videoUS6236765Aug 5, 1998May 22, 2001Intel CorporationDWT-based up-sampling algorithm suitable for image display in an LCD panelUS6269181Jan 13, 2000Jul 31, 2001Intel CorporationEfficient algorithm for color recovery from 8-bit to 24-bit color pixelsUS6275206Mar 17, 1999Aug 14, 2001Intel CorporationBlock mapping based up-sampling method and apparatus for converting color imagesUS6285796Nov 3, 1997Sep 4, 2001Intel CorporationPseudo-fixed length image compression schemeUS6292114Jun 10, 1999Sep 18, 2001Intel CorporationEfficient memory mapping of a huffman coded list suitable for bit-serial decodingUS6301392Sep 3, 1998Oct 9, 2001Intel CorporationEfficient methodology to select the quantization threshold parameters in a DWT-based image compression scheme in order to score a predefined minimum number of images into a fixed size secondary storageUS6348929Jan 16, 1998Feb 19, 2002Intel CorporationScaling algorithm and architecture for integer scaling in videoUS6351555Jan 13, 2000Feb 26, 2002Intel CorporationEfficient companding algorithm suitable for color imagingUS6356276Mar 18, 1998Mar 12, 2002Intel CorporationMedian computation-based integrated color interpolation and color space conversion methodology from 8-bit bayer pattern RGB color space to 12-bit YCrCb color spaceUS6366692Mar 30, 1998Apr 2, 2002Intel CorporationMedian computation-based integrated color interpolation and color space conversion methodology from 8-bit bayer pattern RGB color space to 24-bit CIE XYZ color spaceUS6366694Mar 26, 1998Apr 2, 2002Intel CorporationIntegrated color interpolation and color space conversion algorithm from 8-bit Bayer pattern RGB color space to 24-bit CIE XYZ color spaceUS6373481Aug 25, 1999Apr 16, 2002Intel CorporationMethod and apparatus for automatic focusing in an image capture system using symmetric FIR filtersUS6377280Apr 14, 1999Apr 23, 2002Intel CorporationEdge enhanced image up-sampling algorithm using discrete wavelet transformUS6381357Feb 26, 1999Apr 30, 2002Intel CorporationHi-speed deterministic approach in detecting defective pixels within an image sensorUS6392699Mar 4, 1998May 21, 2002Intel CorporationIntegrated color interpolation and color space conversion algorithm from 8-bit bayer pattern RGB color space to 12-bit YCrCb color spaceEP0288219A2Apr 15, 1988Oct 26, 1988Advanced Micro Devices, Inc.Apparatus for decoding facsimile coded data to image dataJPS5113748A * Title not available* Cited by examinerNon-Patent CitationsReference1Acharya, "A Mathematical Model for Gray Scale and Contrast Enhancement of a Digital Image", Application No; 09/207,153, Filed: Dec. 8, 1998, 28 pgs.2Acharya, "A Memory Based VLSI Architecture for Image Compression" Applicaion No: 08/885,415, Filed: Jun. 30, 1997, 37 pgs.3Acharya, "Discrete Filter", Application No: 09/432,337, Filed Nov. 2, 1999, Atty. docket No: 042390.P7626, 15 pgs.4Acharya, "Enhancing Image Compression Performance by morphological Processing", Application No: 09/291,810, Filed: Apr. 14, 1999, 31 Pgs.5Acharya, "Method of Converting a Sub-Sampled Color Image", Application No: 09/461,068, Filed: Dec. 14, 1999, 22 pgs.6Acharya, "Techniques to Implement Two-Dimensional Compression", Application No: 09/664,131, Filed: Sep. 18, 2000. 24 pgs.7Acharya, "Video Motion Estimation", Application No: 09/406,032, Filed: Sep. 27, 1999, 24 pgs.8Acharya, et al. "Method of Using Hue to Interpolate Color Pixel Signals", Application No: 09/591,867, Filed: Jun. 12, 2000, 23 pgs.9Acharya, et al., "A Fuzzy Based Threshold Technique for Image Segmentation", Application No; 09/393,136, Filed: Sep. 10, 1999, 28 pgs.10Acharya, et al., "A Fuzzy Distinction Based Thresholding Technique for Image Segmentation", Application No: 09/393,017, Filed: Sep. 10, 1999, 29 pgs.11Acharya, et al., "Chip Rate Selectable Square Root Raised Cosine Filter for Mobile Telecommunications", Application No: 09/467,487, Filed: Dec. 20, 1999, 44 pgs.12Acharya, et al., "Color Interpolation for a Four Color Mosaic Pattern", Application No: 09/199,836, Filed. Nov. 24, 1998, 26 Pgs.13Acharya, et al., "Image Processing Method and Apparatus", Application No: 09/359,523, filed: Jul. 23, 1999, 16 pgs.14Acharya, et al., "Indexing Wavelet Compressed Video for Efficeint Data Handling", Application No: 09/438,091, Filed: Nov. 10, 1999, 29 pgs.15Acharya, et al., "Method of Cideo Coding the Movement of a Human Face From a Sequence of Images" Application No: 09/608,989, Filed: Jun. 30, 2000, 25 pgs.16Acharya, et al., "Method of Compressing a Color Image" Application No: 09/411,697, Filed: Oct. 1, 1999, 26 pgs.17Acharya, et al., "Method of Compressing an Image", Application No: 09/597,354, Filed: Jun. 19, 2000, 23 pgs.18Acharya, et al., "Method of Integrating a Watermark Into a Compressed Image", Application No: 09/519,135, Filed: Mar. 6, 2000, 25 pgs.19Acharya, et al., "Method of Integrating a Watermark into an Image", Application No: 09/519,874, Filed: Mar. 6, 2000, 27 pgs.20Acharya, et al., "Method of Inverse Quantizing Signal Samples of an Image During Image Decompression", Application No: 09/507,213, Filed: Feb. 18, 2000, 32 pgs.21Acharya, et al., "Method of Quantizing Signal Samples of an Image During Compression", Application No: 09/507,399, Filed: Feb. 18, 2000, 24 pgs.22Acharya, et al., "Method of Upscaling a Color Image", Application No: 09/461,080, Filed: Dec. 14, 1999, 22 pgs.23Acharya, et al., "Method of Video Coding Shoulder Movement from a Sequence of Images", Application No: 09/607,724, Filed: Jun. 30, 2000, 25 pgs.24Acharya, et al., "Square Root Raised Cosine Symmetric Filter for Mobile Telecommunications" Application No: 09/429,058, Filed: Oct. 29, 1999, 36 pgs.25Acharya,et al., "Method of Interpolating Color Pixel Signals from a Subsampled Color Image", Application No: 09/410,800, Filed: Oct. 1, 1999, 20 pgs.26Acharya,et al., "Model-Based Video Image Coding", Application No: 09/608,991, Filed: Jun. 30, 2000, 36 pg.27Acharya., et al, "Zerotree Encoding of Wavelet Data", Application No; 09/390,255, Filed: Sep. 3, 1999, 22 pgs.28Bawolek, et al., "Infrared Correction System", Application No: 09/126,203, Filed Jul. 30, 1998, 23 Pgs.29Hunter, et al., "International Digital Facsimile Coding Standards", 1980 IEEE, British Post Office Centre, Martlesham Heath, England, pp. 854-867.30Kim, et al. "Method of Performing Motion Estimation", Application No: 09/596,127, Filed: Jun. 16, 2000, 29 pgs.31Metz, et al., "Image Processing Architecture", Application No: 09/473,643, Filed: Dec. 28, 1999, 15 pgs.32Miao, et al., "Dual Mode Filter For Mobile Telecommunications", Application No: 09/467,611, filed: Dec. 20, 1999, 49 pgs.33Pazmino, et al., "Method of Compressing and/or Decompressing a Data Set Using Significance Mapping", Application No: 09/151,336, filed: Sep. 11, 1998, 25 pgs.34Tan, et al., "A Hardware Efficient Wavelet-Based Video Compression Scheme", Application No: 09/342,863, Filed: Jun. 26, 1999, 32 pgs.35Tan, et al., "A Methodology for Color Correction with Noise Regulation", Application No: 09/359,831, Filed: Jul. 23, 1999, 30 pgs.36Tan, et al., "Method and Apparatus for Adaptively Sharpening Local Image Content of an Image", Application No: 09/328,935, Filed: Jun. 9, 1999, 29 pgs.37Tan, et al., "Robust Sequential Approach in Detecting Defective Pixels Within an Image Sensor", Application No: 09/191,310, 35 Pgs.38Tan, et al., "Using an Electronic Camera to Build a File Containing Text", Application No: 09/301,753, Filed Apr. 29, 1999, 21 pgs.39Tsai, et al., "Method and Apparatus for Adaptively Sharpening an Image", Application No: 09/320,192, Filed May 26, 1999, 27 pgs.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS6982661Mar 18, 2003Jan 3, 2006Intel CorporationMethod of performing huffman decodingUS6987469Jun 3, 2003Jan 17, 2006Intel CorporationMethod of generating Huffman code length informationUS7190287Dec 6, 2005Mar 13, 2007Intel CorporationMethod of generating Huffman code length informationUS7308150 *Feb 24, 2003Dec 11, 2007Fuji Xerox Co., Ltd.Image processing apparatus* Cited by examinerClassifications U.S. Classification382/245, 358/426.16International ClassificationH03M7/46, H04N1/419Cooperative ClassificationH04N1/419European ClassificationH04N1/419Legal EventsDateCodeEventDescriptionSep 21, 2011FPAYFee paymentYear of fee payment: 8Feb 18, 2008REMIMaintenance fee reminder mailedFeb 8, 2008FPAYFee paymentYear of fee payment: 4Dec 12, 2000ASAssignmentOwner name: INTEL CORPORATION, CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:ACHARYA, TINKU;REEL/FRAME:011374/0251Effective date: 20001031Owner name: INTEL CORPORATION 2200 MISSION COLLEGE BOULEVARDSAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:ACHARYA, TINKU /AR;REEL/FRAME:011374/0251RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google