Source: http://www.google.com/patents/US6947592?dq=actionscript
Timestamp: 2017-04-26 04:26:21
Document Index: 228919689

Matched Legal Cases: ['arts 42', 'art 41', 'art 41', 'art 41', 'art 42', 'art 42']

Patent US6947592 - Encoding method of a color image and its encoding device and a decoding ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsThe invention improves the refresh rate and minimizes the memory for display when reproducing a color image. A color image encoding device has a creation device which counts the number of colors used in color image data and creates a global palette which lists corresponding indexes when the number of...http://www.google.com/patents/US6947592?utm_source=gb-gplus-sharePatent US6947592 - Encoding method of a color image and its encoding device and a decoding method of the color image and its decoding deviceAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS6947592 B2Publication typeGrantApplication numberUS 10/234,094Publication dateSep 20, 2005Filing dateSep 5, 2002Priority dateNov 27, 1997Fee statusPaidAlso published asUS6542631, US20030048943Publication number10234094, 234094, US 6947592 B2, US 6947592B2, US-B2-6947592, US6947592 B2, US6947592B2InventorsMasaki IshikawaOriginal AssigneeSeiko Epson CorporationExport CitationBiBTeX, EndNote, RefManPatent Citations (19), Referenced by (9), Classifications (15), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetEncoding method of a color image and its encoding device and a decoding method of the color image and its decoding device
US 6947592 B2Abstract
The invention improves the refresh rate and minimizes the memory for display when reproducing a color image. A color image encoding device has a creation device which counts the number of colors used in color image data and creates a global palette which lists corresponding indexes when the number of colors is a specified value or less, a block division device which divides the color image data into a plurality of blocks, a local palette creation device which creates a local palette which lists indexes in the global palette when the number of colors in a block is less than the number of colors in the global palette, and a color index assigning device which assigns the indexes in the global palette to the input pixels when the number of colors is the same as the number of colors in the global palette, and assigns the indexes in the local palette to the input pixels when the numbers of colors is different from the number of colors in the global palette.
Furthermore, as a method for creating the data of the index, that is, the color pixel data 100A, the method to apply the index in order of the color to be input is common. As shown in FIG. 19, phenomena occur such that the colors are significantly different even if the numbers of the index are close (e.g., “1” and “2”) and the colors are close even if the numbers of the index are distant (e.g., “100” and “200”). In order to avoid these phenomena, as shown in Japanese Patent Laid-Open Publication No. Hei 5-328142, there is also a method to apply a sequential number to the approximate color.
Furthermore, in Japanese Patent Laid-Open Publication No. Hei 8-9163, the input color image data is divided into blocks of 16×16 pixels, and it is checked whether each block is a color area or a black-and-white area. With respect to a block of a color area, after sampling is performed in a predetermined sub-sampling ratio, DCT conversion, linear quantization, and entropy encoding are performed. Meanwhile, with respect to a block of a black-and-white area, only the Y component of the color components YCrCb which form the color image data is performed by DCT conversion, linear quantization, and entropy encoding.
However, in the conventional multi-color image and natural image general encoding and decoding devices, various types of compression technologies are used and the encoded and decoded data amount is significantly reduced, but no solution to this problem has been developed in terms of the data capacity for the palette. That is, in the conventional color image encoding and decoding devices, when the number of colors to be used is increased, the data capacity for the image increases and the refresh rate for the image display tends to be slow. For example, when a color image of 256×256 pixels is encoded or decoded by 256 colors, a memory of 66,304 bytes is needed. That is, when each color needs a total of three bytes in RGB, 256×3 bytes +256×256×1 byte (256 colors)=66,304 bytes is established. Thus, in the case of a screen with the 256×256 pixels, even if 256 colors are used, it requires a large capacity of approximately 70 K bytes and becomes a relatively large amount of data even by using various kinds of complicated compression means. Because of this, when the refresh rate becomes slow, the memory for the display becomes large.
An object of the present invention is to provide a color image encoding method which can improve the refresh rate and minimize the memory for display, and an encoding device, and a color image decoding method and a decoding device for when the color image is reproduced. Furthermore, another object of the present invention is to provide a color image encoding method and an encoding device that improves the compression rate and the decoding efficiency of the image and the encoding device, and also to provide a corresponding color image decoding method and decoding device.
Moreover, in the present invention, in the color image encoding method, the predetermined value is set at 256 colors, the specified value is set at 5, and the size of one block is set at 32×32 pixels.
When the block size is set at 32×32 pixels, the maximum becomes 1,024 colors, and most images are accommodated within 256 colors. Thus, by setting the predetermined value at 256 colors, the present invention applies to most images and it is possible to reduce the memory and improve the refresh rate. Furthermore, when the number of colors in the block exceeds 16 colors and stays less than 32 colors, it can be expressed by five bits, when the number of colors exceeds 32 colors and stays less than 64 colors, it can be expressed by six bits, when the number of colors exceeds 64 colors and stays less than 128 colors, it can be expressed by 7 bits. It is possible to control the data capacity required for the color indexes to a small size. In particular, data such as a map has approximately 20 colors in many cases, so in the case of data like that, it can be expressed by five bits, and it is possible to definitely minimize the capacity compared to eight bits when m is the x square of 2. In addition, when run length encoding is performed, 16 can be used as a maximum number of runs and it can be processed by four bits at that time.
In addition, in the invention, in the color image encoding device, the predetermined value is set at 256 colors, the specified value is set at 5, and the size of one block is set at 32×32 pixels.
Moreover, in the present invention, in the color image decoding method, the predetermined value is set at 256 colors, the specified value is set at 5, and the size of one block is set at 32×32 pixels.
When the block size is thus set at 32×32 pixels, the maximum becomes 1,024 colors, and most images are accommodated within 256 colors. Thus, by setting the predetermined value at 256 colors, the present invention applies to most images and it is possible to reduce the memory required and improve the refresh rate. Furthermore, when the number of colors in the block exceeds 16 colors and stays less than 32 colors, it can be expressed by five bits, when the number of colors exceeds 32 colors and stays less than 64 colors, it can be expressed by six bits, when the number of colors exceeds 64 colors and stays less than 128 colors, it can be expressed by 7 bits. It is possible to control the data capacity required for the color indexes to a small size. In particular, data such as a map has approximately 20 colors in many cases, so in such a case, it can be expressed by, five bits, and it is possible to definitely minimize the capacity compared to eight bits when m is the x square of 2. In addition, when run length encoding is performed, 16 can be used as a maximum number of runs and it can be processed by four bits at that time.
When the block size is set at 32×32 pixels, the maximum becomes 1,024 colors, and most images are accommodated within 256 colors. Thus, by setting the predetermined value at 256 colors, the present invention applies to most images and it is possible to reduce the memory and improve the refresh rate. Furthermore, when the number of colors in the block exceeds 16 colors and stays less than 32 colors, it can be expressed by five bits, when the number of colors exceeds 32 colors and stays less than 64 colors, it can be expressed by six bits, when the number of colors exceeds 64 colors and stays less than 128 colors, it can be expressed by 7 bits. It is possible to control the data capacity required for the color indexes to a small size. In particular, data such as a map has approximately 20 colors in many cases, so in a case such as that, it can be expressed by five bits, and it is possible to definitely minimize the capacity compared to eight bits when m is the x square of 2. In addition, when run length encoding is performed, 16 can be used as a maximum number of runs and it can be processed by four bits at that time.
FIG. 1 is a function block diagram of the color image encoding device of an embodiment of the present invention.
FIGS. 12(A)-12(D) are diagrams showing the content of the code data which is formed by the color image encoding device of FIG. 1: wherein FIG. 12(A) is when s mode is “1”, FIG. 12(B) is when s mode is “2”, FIG. 12(C) is when s mode is “4”, and FIG. 12(D) is when s mode is “8”.
Hereafter, an example of an embodiment of the present invention is explained based on FIGS. 1-18. The encoding device and its encoding method is explained initially.
In the present embodiment, 256 colors is adopted as the specified value. In other words, when the entire image which is stored in the buffer register 4 is 256 colors or less, the global palette is written out. The global palette 5, as shown in FIG. 2, aligns specified colors in order, for which the values of RGB are specified. Therefore, they are numbered in order from the top of the global palette. When the value of the number of used colors (hereafter, g count) is 2 colors or less, the number of used colors counting means 15 outputs “1” as the used color number mode (hereafter g mode) with the g count. Similarly, it outputs g mode=2 when the g count is 4 or less, g mode=4 when the g count is 16 or less and g mode=8 when the g count is 256 or less.
Moreover, in the present embodiment, the block dividing means 7 forms and processes blocks with a unit of 32×32 pixels. The number of colors counting means 16 counts the number of colors in the blocks. When the entire image is 256 colors or less and the global palette 5 is written-out, the following processing is performed. Namely, the value of the number of colors in the block (hereafter, s count) and the number of used colors mode (hereafter s mode) are output.
When the number of colors used in the entire image is 256 colors or less, it divides the image into blocks of 32×32 pixels by the block dividing means 7 (step S5) and processes the blocks. Next, the number of colors used in the first block is counted by the number of colors used in blocks counting means 16 (step S6). In this step S6, the s count and s mode are formed. The formed s mode and the previous g mode are compared by the number of colors comparison means 17 (step S7).
In this case, the global palette 5 is not created, and the color image data 2 in the buffer register 4 is directly divided into blocks of 32×32 pixels by the block dividing means 7 (step S11). Then, the number of colors used in the block is counted by the number of colors in blocks counting means 16 (step S12). The count value evaluates whether it is 256 colors or less (step S13), and when it is 256 colors or less, the palette data corresponding to the global palette 5 which was shown previously is formed in the place corresponding to the local palette 8 (step S14). After this, the index in the palette is assigned by the color index assigning means 10 to each pixel, and it is run length modeled or the like by the modeling means 11. After this, it is encoded by the entropy encoding means 12 (step S15). At step S13, when it exceeds 256 colors, new palette data is not created, and after the index of the original palette of the original pixel which corresponds to each pixel is run length modeled, it is encoded (step S16).
The processes of encoding that are performed at steps S9, S10, S15 and S16 are illustrated in the flow chart of FIG. 7. Specifically, when it is temporarily run length encoded, it is evaluated whether the ratio where the value of run value becomes 1 and 2 exceeds a specified value in the block, which is 20% in the present embodiment by a modeling method evaluation means (not shown) (step S20). Moreover, if the specified value is 15˜25%, it is preferable since the efficiency of the run length encoding becomes good when at or under these values.
When the evaluation of step S20 is affirmative, the surrounding reference pixel modeling is performed (step S21). In this step S21, as shown in FIG. 8(A), the same as the Markov model, the surrounding reference pixels A, B, C and D and the encoding object pixel X are compared. Then, when the encoding object pixel X and the reference pixel A (=one ahead pixel) are matched, the value of L1 data is “0”. When it is matched with the reference pixel B (=one above pixel), the value of L1 data is “1”, and the value of the L2 data is “00”. When it is matched with the reference pixel C, L1=“1”, and L2=“01”, and when it is matched with the reference pixel D, L1=“1”, and L2=“10”. When it does not match with the reference pixels A, B, C or D, L1=“1”, and L2=“11”.
For example, as shown in FIG. 9(A), normally, the pixel {circle around (1)} which is right in front of the encoding object pixel X is compared, but the pixel {circle around (2)} which is directly above is compared when the pixel {circle around (1)} and the encoding object pixel X are different. Then, for the normal code data, as shown in FIG. 9(B), when it is the copy mode, C=“0” and L≠“0”, where the portion of the color index C is other than “0” and the portion of the run L is other than “0”. Moreover, it is expressed as C=“0” and L=“0” when a certain pixel and everything following are all empty. Accordingly, the value of C=“0” is positioned as a special mode (=copy mode) in the present embodiment, and also L=“0” is used with a special meaning of all the lines being empty.
The above-mentioned flow is shown based on the concrete example of FIG. 10. The color index C and the run L become the values as shown in FIG. 10(B) when there are pixels which have the color indexes which are shown in FIG. 10(A). L is “2” since two “1”s of the color index C continue, and next L=3 since there are three C=5. Next, L=2 since two C=4 continue. At this time, when C is changed from “1” to “5”, and when C is changed from “5” to “4”, the normal run length is performed since it becomes Yes at step S32 even though it is different from the pixel directly above in step S33.
Next, when the color index C is changed from “4” to “X”, it moves to the steps S32, S33, S34 since it is same as the pixel directly above, and it becomes the copy mode. Because of this, C becomes “0”. After this, the copy mode is continued since each of three pixels are same as the pixel directly above, respectively, and the copy mode is completed when different pixels (=“3” and “Δ”) appear. Then, “4” is saved as the value corresponding to the run. After this, L=“0” is assigned with C=“0” since one color index C is “3”, two color indexes C=“4” and an empty space comes at the end.
Moreover, since each data is expressed as the bits of “0” and “1” and the completed portion of each data cannot be determined, the key data K which shows the completed portion of each data is added to the last of each data.
Also, in the present embodiment, the predetermined value is 256 colors, and the size of one block is 32×32 pixels. Accordingly, based on similar rules to the algorithm at the time of the encoding, the color image data 2 is obtained from the encoded bit 3 by using the algorithm for decoding.
The left and right operating parts 42 of the display part 41 have 10 kinds 1˜10 of the menu buttons 42 a. The corresponding operating menu is displayed on the display part 41 which is adjacent to these buttons 42 a. For example, various animations stored in the personal computer can be selected by the numbers. In other words, when the first menu button 42 a is pressed, the first animation is replayed. Moreover, at the lower side of the display part 41, various operation button part 42 b are arranged to be used when accessing a web page on the Internet. Moreover, the designation operating part 42 c for moving the controlling arrow on the screen up and down and left and right is provided in the vicinity of the magnetic card reader 44.
Furthermore, as shown in FIG. 18, the entire image does not have to be decoded, and the memory for display can be minimized since only one part of the image is displayed instead of displaying the entire image of the PC 46. Moreover, it is also acceptable to change the size of the memory for display and the panel for display depending on the portable terminal display device 40. For example, it is acceptable that one portable terminal display device 40 be able to display “A B C D”, another portable terminal display device 40 be able to display “A B”, and further, another portable terminal display device 40 only be able to display “A”. This color image decoding device 21 and portable terminal display device 40 has a simple and minimized structure, and performs lossless decoding.
In the above-mentioned embodiment, the replay speed becomes faster due to the decoding. Moreover, it is unnecessary to decode the entire image, and to decode only the blocks which are necessary for the display. In addition, simple and lossless decoding becomes possible. Moreover, the block size may be arbitrary. When it is 32×32 pixels, it is 1024 colors at the maximum value, and stays in the 256 colors normally. Moreover, the run number at the time of the run length encoding can be 4 bits, and the encoding efficiency and the decoding efficiency are good.
Moreover, the above-mentioned embodiment is an appropriate example of the present invention. However, the present invention is not limited to this, and modified operations are possible without deviating from the range of this summary. For example, the block size can be a square block of 16×16 pixels, 64×64 pixels or the like instead of 32×32 pixels, can be a horizontally long rectangular when the run number is large. There may be various sizes and shapes of blocks.
Moreover, it is desired that the block size be not too large since it is preferable that the local palette 28 in the color image decoding device 21 be a lower mode than the global palette 24. In other words, it is desirable to have from 16×16 pixels to 64×64 pixels.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS3748379 *Jan 22, 1970Jul 24, 1973Electronic Image Sys CorpRun length coding techniqueUS4020502 *Oct 10, 1975Apr 26, 1977Matsushita Electric Industrial Co., Ltd.Method and apparatus for separating, combining and rearranging colored imagesUS4847677 *Apr 27, 1988Jul 11, 1989Universal Video Communications Corp.Video telecommunication system and method for compressing and decompressing digital color video dataUS4853767 *Feb 20, 1987Aug 1, 1989Mita Industrial Co., Ltd.Color graphic image processing system involving data compression using reference samplesUS5283840 *Apr 22, 1992Feb 1, 1994Dainippon Screen Mfg. Co., Ltd.Method and apparatus for extracting image dataUS5768403Dec 21, 1994Jun 16, 1998Fuji Xerox Co., Ltd.Image-area identifying system for a color image processing apparatusUS5805735Nov 13, 1997Sep 8, 1998Apple Computer, Inc.Method and apparatus for compression of digitized image data using variable color fidelityUS5883633 *Apr 15, 1997Mar 16, 1999Microsoft CorporationMethod and system of variable run length image encoding using sub-paletteUS5930387Dec 4, 1997Jul 27, 1999Apple Computer, Inc.Method and apparatus for encoding color image data using dynamic color matchingUS6016360Oct 15, 1997Jan 18, 2000Apple Computer, Inc.Method and apparatus for encoding color image dataUS6115496Jan 20, 1998Sep 5, 2000Apple Computer, Inc.Method and apparatus for accelerating image data compressionUS6574364 *Mar 19, 1999Jun 3, 2003Koninklijke Philips Electronics N. V.Pixel color value encoding and decodingJPH089163A Title not availableJPH05328142A Title not availableJPH06178122A Title not availableJPH07336696A Title not availableJPS6374324A Title not availableJPS6376525A Title not availableJPS62185413A Title not available* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS7684644Dec 16, 2008Mar 23, 2010Canon Kabushiki KaishaVariable-length encoding for image data compressionUS7893851 *Nov 27, 2007Feb 22, 2011Nec CorporationEncoding apparatus, method, and processorUS8405881 *Apr 7, 2009Mar 26, 2013Brother Kogyo Kabushiki KaishaImage processing device with an additional image overlaying functionUS8615138 *Nov 3, 2011Dec 24, 2013Google Inc.Image compression using sub-resolution imagesUS8977066Nov 15, 2013Mar 10, 2015Google Inc.Image compression using sub-resolution imagesUS20090161973 *Dec 16, 2008Jun 25, 2009Canon Kabushiki KaishaVariable-Length Encoding for Image Data CompressionUS20090257094 *Apr 7, 2009Oct 15, 2009Brother Kogyo Kabushiki KaishaImage processing deviceUS20100019941 *Nov 27, 2007Jan 28, 2010Takahiro KumuraEncoding apparatus, method, and processorUS20130002729 *Jun 6, 2012Jan 3, 2013Lg Electronics Inc.Image display apparatus and method for operating the same* Cited by examinerClassifications U.S. Classification382/166, 382/245International ClassificationG06T1/00, H04N11/04, G06T5/00, H04N1/41, G09G5/06, G06T9/00, H04N1/64Cooperative ClassificationG06T9/005, G09G5/06, H04N1/644European ClassificationG09G5/06, H04N1/64C, G06T9/00SLegal EventsDateCodeEventDescriptionFeb 18, 2009FPAYFee paymentYear of fee payment: 4Feb 20, 2013FPAYFee paymentYear of fee payment: 8RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services