Source: http://www.google.com/patents/US7426311?dq=6,360,693
Timestamp: 2015-05-03 18:38:52
Document Index: 498752936

Matched Legal Cases: ['art 24', 'art 10', 'art 11', 'art 11', 'art 11', 'art 12', 'art 13', 'art 20', 'art 24', 'art 24', 'art 240', 'art 240', 'art 20', 'art 440', 'art 444', 'art 446', 'art 440', 'art 43', 'art 444', 'art 444']

Patent US7426311 - Object-based coding and decoding apparatuses and methods for image signals - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsAn object-based coding apparatus and method for image signals, wherein upon scanning shape-adaptive transform coefficients of an input image signal transformed in accordance with a shape-adaptive transform, only segments containing such shape-adaptive transform coefficients are scanned. In the scanning...http://www.google.com/patents/US7426311?utm_source=gb-gplus-sharePatent US7426311 - Object-based coding and decoding apparatuses and methods for image signalsAdvanced Patent SearchPublication numberUS7426311 B1Publication typeGrantApplication numberUS 09/195,897Publication dateSep 16, 2008Filing dateNov 19, 1998Priority dateOct 26, 1995Fee statusPaidPublication number09195897, 195897, US 7426311 B1, US 7426311B1, US-B1-7426311, US7426311 B1, US7426311B1InventorsSung Moon Chun, Jin Hak Lee, Joo Hee Moon, Gwang Hoon Park, Jae Kyoon Kim, Jae-Won ChungOriginal AssigneeHyundai Electronics Industries Co. Ltd.Export CitationBiBTeX, EndNote, RefManPatent Citations (5), Non-Patent Citations (1), Referenced by (3), Classifications (23), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetObject-based coding and decoding apparatuses and methods for image signals
US 7426311 B1Abstract
Compression coding and decoding of image signals makes it possible to achieve transmission of image information while reducing the memory capacity required to store image signals. Thus, such compression coding and decoding techniques are very important techniques in multimedia industries involving applications such as storage and transmission of image signals. Meanwhile, a standardization for information compression schemes has been necessary for extension of multimedia industries and information compatibility. To this end, various image standardization schemes associated with a variety of applications have been proposed. For example, as representative image coding and decoding standardization schemes, there are H.261 of International Telecommunication Union�Telecommunication Standardization Sector (ITU-T, the successor of CCITT) for video phone or video conference services using integrated services digital networks (ISDN), and H.263 of ITU-T for transmission of video information using public switched telephone networks (PSTN), MPEG-1 proposed by Moving Picture Experts Group (MPEG) of International Standardization Organization/International Electrotechnical Commission Joint Technical Committee 1/Sub Committee 29/Working Group 11 (ISO/IEC JTC1/SC29/WG11) for storage media, and MPEG-2 for high quality digital broadcasting associated with high definition televisions (HDTV) and enhanced digital television (EDTV). Standardization for compressive coding of still image signals also has been made by, for example, Joint Photographic Coding Experts Group (JPEG) of ISO/IEC JTC1/SC29/WG1.
In most conventional image signal coding schemes, the entire segment of a rectangular frame or picture is encoded. Such schemes are called �frame-based coding�. In such image signal coding schemes, texture information of all pixels included in a frame, namely, luminance and chrominance, is encoded and transmitted.
Recently, the demands for multimedia products have been increased which have functions of coding or manipulating only particular regions�or object�of a frame interested or needed to the user without coding the entire region of the frame. To this end, active research has recently been conducted for object-based coding schemes adapted to encode only arbitrary shape region of a frame, as a substitute for frame-based coding schemes adapted to encode the entire region of a frame. FIGS. 1 and 2 illustrate test images for explanation of such an object-based coding scheme, respectively. FIG. 1 is a frame showing features of two children playing with a ball in an arbitrary space (background). Where information, only associated with the children and ball, of the image is to be encoded and transmitted coding of such information can be achieved using the object-based coding scheme, that is, only texture information values of pixels associated with the children and ball are encoded and transmitted. In this case, the regions respectively associated with the children and ball are designated to be an object, whereas the remaining region of the picture other than the object is considered to be a background.
FIG. 2 shows shape information included in the image information where only the children and ball are considered to be an object. In this case, the pixels associated with the children and ball have shape information bearing a bright value whereas the pixels associated with the background have shape information bearing a dark value. Such shape information of pixels assigned with different values to distinguish those of the pixels associated with the object from those associated with the background is called a �binary mask�. Shape information may also be expressed by a contour indicative of the boundary between the background and the object. A transformation can be made between the shape information in the form of a binary mask and the shape information in the form of a contour. That is, the shape information having the form of a binary mask can be expressed into contour information by carrying out a contour extraction. On the other hand, a contour filling is carried out for obtaining a binary mask from contour information.
Transform coding is the most widely used coding method in well-known compressive coding schemes for image signals. In such a transform coding, an image signal is transformed to transform coefficients�or frequency coefficients and low frequency components are mainly transmitted while suppressing transmission of high frequency components. This scheme has an advantage of a high compression ratio while minimizing the degradation of picture quality. Examples of such a transform coding scheme include a discrete Fourier transform (DFT), a discrete cosine transform (DCT), a discrete sine transform (DST), and a Walsh-Hadamard transform (WHT).
Research of such transform coding schemes has been made with respect to image signals in blocks each consisting of a set of pixels (picture elements or pels) with a certain size. In accordance with transform coding schemes developed, a rectangular frame is divided into a plurality of blocks having the same size. A transform coding is then carried out for each block. In the case of an object-based coding scheme only texture information included in objects is encoded, as compared to frame-based coding scheme in which texture information of all pixels included in a rectangular frame is completely encoded. In such an object-based coding scheme, accordingly, it is required to conduct a transform coding only for image signal of some pixels of blocks associated to the object. FIG. 3 illustrates an object having an arbitrary shape in a frame divided into a plurality of blocks. In FIG. 3, each square region is indicative of one block. Dark region is indicative of a set of pixels associated with the object. In FIG. 4, transparent blocks correspond to blocks of FIG. 3 not to be encoded because of including no object pixel, respectively. The black blocks of FIG. 4 are indicative of blocks which are to be transformed by one of the known transform coding schemes because all pixels thereof are object pixels. The gray blocks of FIG. 4 are indicative of blocks each including both the object pixels and the non-object pixels, thereby requiring a transform coding only for texture information of a part of pixels thereof. In the following description, blocks corresponding to such gray blocks are referred to as �boundary blocks�. This scheme, in which a transform coding is not conducted for the entire pixels of each square block, but conducted for a part of pixels included in each square block, is called a �shape-adaptive transform coding�.
In a representative shape-adaptive transform coding scheme, each block which is a coding unit consists of 8�8 pixels. Namely, blocks include 8 lines per block and 8 pixels per line. In accordance with the scheme, texture signal of object pixels to be encoded are processed by an one-dimensional DCT in a vertical direction and then in a horizontal direction.
Referring to FIG. 5A, an 8�8 block is illustrated which has an object region to be encoded. In FIG. 5A, gray pixels are pixels associated with objects. For processing an shape-adaptive DCT coding for texture signal of object pixels to be encoded, a re-arrangement of pixels is carried out by vertically shifting those object pixels to the upper border of the block, thereby filling that border, as shown in FIG. 5B. In this state, one-dimensional DCT is performed in a vertical direction (indicated by thick lines in FIG. 5) for texture information of each column including object pixels. As a result, transform coefficients of one-dimensional DCT are generated, as shown in FIG. 5C. The solid circles in FIG. 5C denote positions of mean values of vertical one-dimensional DCT, namely, direct current (DC) values, respectively. After completing the vertical one-dimensional DCT as shown in FIG. 5D, a pixel re-arrangement is conducted again by shifting again the object pixels to the left border of the block. Thereafter, one-dimensional DCT is performed in a horizontal direction for the transform coefficients included in each of rows, which comprise at least one transform coefficient, as shown in FIG. 5E. FIG. 5F shows positions of transform coefficients completing the one-dimensional DCT in both the vertical and horizontal directions. This procedure, namely, the transform, in which one directional DCT is carried out in a successive manner in the vertical and horizontal directions, is called a �shape-adaptive DCT�. It should be noted that the positions of transform coefficients resulting from the shape-adaptive DCT may not be coincide with those of input object pixels (or input shape information) and that the positions of those transform coefficients are determined only based on the input shape information. The number of transform coefficients resulting from the shape-adaptive DCT is equal to the number of object pixels, as in the conventional block-wised DCT schemes.
FIG. 6 illustrates a block diagram of a conventional shape-adaptive image signal coding apparatus (=texture information encoding part 24) which utilizes the above mentioned shape-adaptive DCT. This apparatus 24 receives, as an input thereof, shape information on a block basis having a M�N size (M and N are integer values larger than zero) and texture information of object pixels in the form of a block having the same size as the shape information block. In the case of FIGS. 5A to 5F, block of M=8 and N=8 is inputted. The apparatus 24 generates an output in the form of a bitstream. The outputted bitstream is transmitted to a receiver. Otherwise, the bitstream may be transmitted to a multiplexer (MUX) so that it is multiplexed with other signals, for example, bitstreams of shape information.
An shape-adaptive DCT part 10 first performs a shape-adaptive DCT for input texture information of object pixels, based on input shape information, thereby outputting transform coefficients which are positioned at the upper left portion of an associated block, as shown in FIG. 5F. For these transform coefficients, a quantization is conducted for data compression in a quantization part 11. As a result, quantized transform coefficients are outputted from the quantization part 11. The transform coefficients from the quantization part 11 are then transmitted to a scanning part 12 which, in turn, carries out a scanning procedure for arranging the received transform coefficients into a one-dimensional array. Various scanning methods applicable to blocks of M=8 and N=8 are illustrated in FIGS. 7A to 7C. FIG. 7A illustrates a zig-zag scanning order most widely used. In FIG. 7A, the numerals indicated on respective portions of the block are indicative of the scanning order of corresponding transform coefficients upon arranging those transform coefficients in a one-dimensional array. The scanning methods of FIGS. 7A to 7C can be selectively used in accordance with the characteristics of input image signals to be subjected to a transform coding. These scanning methods are also used in MPEG-2 and MPEG-4 schemes. Blocks, which are processed by the shape-adaptive DCT, may include segments containing no transform coefficient, as shown in FIG. 5F. In accordance with a conventional schemes, a scanning operation is carried out for the entire segment of a block in a sequential manner according to a well-known, predetermined scanning order while setting transform coefficient values of segments containing no transform coefficient to �zero�. That is, all segments�64 transform coefficients in the case of an 8�8 block�are sequentially scanned using one of the known scanning methods, irrespective of whether or not the segments to be scanned contain transform coefficients. The resultant transform coefficients arranged in a one-dimensional array are subjected to a variable-length coding in a variable-length coding part 13. The resultant signal in the form of a bitstream is then transmitted to an MUX or receiver.
Now, the variable-length coding for transform coefficients will be described in conjunction with H. 263 which is a representative of conventional variable-length coding schemes. In accordance with this scheme, EVENTs of transform coefficients with values not being �zero� are first derived. For the derive EVENTs, corresponding bitstreams are then sought from a given variable-length coding (VLC) table. Thereafter, the sought codes are sequentially outputted. Each EVENT consists of a combination of three kinds of information, namely, a LAST indicative of whether or not the transform coefficient being currently encoded is the last non-zero transform coefficient, a RUN indicative of the number of successive zero transform coefficients preceding the current non-zero coefficient and a LEVEL indicative of the magnitude of the current transform coefficient.
0001 1111s
0001 00101s
0001 1110s
0001 1101s
In the Table 1, the first column represents indexes for distinguishing EVENTs from one another. The second column represents LASTs. LAST=0 denotes that coefficient to be coded is not the last non-zero transform coefficient whereas LAST=1 denotes that the coefficient is the last one. The third column represents RUNs. The fourth column represents LEVELs indicative of values of transform coefficients. The fifth column represents the number of bits generated for each EVENT. The last column represents a bitstream generated for each EVENT. In the last column, �s� is indicative of the sign of each LEVEL. A s of �0� (s=0) is indicative of the fact that the associated LEVEL is a positive number whereas a s of �1� (s=1) is indicative of the fact that the associated LEVEL is a negative number.
Known shape-adaptive DCT coding schemes may use the above mentioned transform coefficient VLC method or VLC table. This will be exemplarily described in conjunction with FIGS. 8A to 8E. FIG. 8A shows the result obtained after carrying out a shape-adaptive DCT and quantization for an image signal in the form of an 8�8 block. In FIG. 8A, the dark segments correspond to object pixels of the block, respectively. Accordingly, the dark segments correspond to segments containing transform coefficients generated due to the object pixels. The remaining bright segments are indicative of segments containing no transform coefficient, thereby being set with a transform coefficient value of �0�. In each dark segment, �Xij� represents a transform coefficient positioned at an i-th position in a horizontal direction and a j-th position in a vertical direction in 8�8 block. When all transform coefficients of the block are scanned in a zig-zag scanning order, they are arranged in the order of X11, X12, X21, X31, X22, X13, X14, 0, X32, X41, X51, X42, 0, 0, X15, X16, 0, 0, 0, X52, X61, X71, 0, 0, . . . , and 0. If the transform coefficient X71 is not zero, then the variable-length coding can be carried out only for segments positioned within the region defined by the thick solid line of FIG. 8B. FIG. 8C illustrates the case in which two transform coefficients X32 and X42 are zero whereas the remaining transform coefficients having non-zero values, respectively. When the transform coefficient X41 is encoded in this case, its LAST value is zero because it is not the last one of non-zero transform coefficients in the block. In this case, LEVEL and RUN values are X41 and 2, respectively. With regard to the transform coefficient X41, such an increase in RUN value caused by the transform coefficient X32 having a value of zero is reasonable because the zero value of the transform coefficient X32 is generated in accordance with a signal information of associated object. However, the transform coefficient value of zero existing between the transform coefficients X14 and X32 is a value not generated in accordance with the object information transform, but given for a segment containing no transform coefficient. Accordingly, transmission of such information is unnecessary and rather results in an increase in RUN value. As a result, there is a disadvantage in that an increased number of bits is generated. This causes a reduction of the coding efficiency of the shape-adaptive DCT coding.
Using the reconstructed shape information received from the shape information coding part 20, the texture information coding part 24 encodes the texture information of an associated object. In the texture information coding part 24, the coding operation is not carried out for entire object, but carried out on a block basis which is pixel set having a certain size, for example, a M�N size.
a shape information coding part for encoding shape information of an input image signal; a shape-adaptive transform part for carrying out a shape-adaptive transform for texture information of said input image signal, based on said shape information outputted from said shape information coding part; a shape-adaptive scan control part for forming a binary coefficient mask having the same transform coefficient distribution as that of an output signal from said shape-adaptive transform part, and generating a scan control signal in accordance with existence or nonexistence of a transform coefficient based on said binary coefficient mask; and a shape-adaptive scanning part for carrying out a scanning operation for an output from said shape-adaptive transform part, based on the associated control signal from said shape-adaptive scan control part. The shape-adaptive scan control part 240 of the object-based coding apparatus comprises:
a coefficient forming unit 241 adapted to form a binary coefficient mask for sorting segments containing transform coefficients from segments containing no transform coefficient which has the same transform coefficient distribution as that of an output signal from said shape-adaptive transform part; and a control signal generation unit 242 adapted to generate a skip signal for skipping segments containing no transform coefficient from the scanning operation of said shape-adaptive scanning part. The shape-adaptive scan control part 240 receives reconstructed shape information from the shape information coding part 20 of FIG. 10, thereby generating a control signal for sorting segments containing transform coefficients from segments containing no transform coefficient so as to control a scanning operation in such a manner that the segments containing transform coefficients are scanned in a scan order while the segments containing no transform coefficient are excluded from the scan order.
The shape-adaptive scanning part (245) according to the present invention also receives transform coefficients outputted from a shape-adaptive transform unit (243) and conducts a scanning operation for arranging those transform coefficients in a one-dimensional array. During the scanning operation, the shape-adaptive scanning part receives a control signal�a signal indicative of whether or not the currently scanned segment contains an associated transform coefficient�from the shape-adaptive scan control unit, in order to exclude segments containing no transform coefficient from the scan order, namely, to prevent zero coefficients of those segments from being included in the one-dimensional array.
a scanning unit 245-1 adapted to scan the entire segment including segments containing shape-adaptive transform coefficients and segments containing no transform coefficient, but respectively filled with coefficients of a predetermined value; and a switching unit 245-2 adapted to receive an output signal from said scanning unit and to switch off said output signal from said scanning unit, based on said skip signal from said control signal generation unit, when said output signal is associated with a segment containing no transform coefficient. In accordance with the present invention, therefore, it is possible to reduce the number of zero coefficients unnecessarily inserted irrespective of non-existence of transform coefficients in the case of the conventional scanning methods. This results in an advantage of an improvement in coding efficiency.
a shape information decoding part for decoding shape information associated with objects and contained in an object bitstream transmitted from a coding apparatus; a shape-adaptive inverse scan control part 440 for forming a binary coefficient mask, based on said shape information received from said shape information decoding part, and generating an inverse scan control signal in accordance with existence or nonexistence of the coefficient mask; a shape-adaptive inverse scanning part 444 for performing an inverse scanning operation to arrange transform coefficients of texture information contained in said object bitstream in the form of a two-dimensional signal, based on said inverse scan control signal from said shape-adaptive inverse scan control part; and a shape-adaptive inverse transform part 446 for performing a shape-adaptive inverse transform for the transform coefficients inversely scanned by said shape-adaptive inverse scanning part, based on said decoded shape information outputted from said shape information decoding part, thereby reconstructing texture information of an original image. The apparatus includes a shape-adaptive inverse scan control part 440 for receiving reconstructed shape information outputted from a shape information decoding part 43, thereby generating a control signal for sorting segments containing transform coefficients from segments containing no transform coefficient so as to control an inverse scanning operation in such a manner that the segments containing transform coefficients are scanned in the well-known scan order while the segments containing no transform coefficient are excluded from the scan order.
The shape-adaptive inverse scanning part 444 according to the present invention also receives transform coefficients outputted from a variable-length decoding unit 443 and conducts a inverse scanning operation for arranging those transform coefficients in the form of a two-dimensional signal. During the inverse scanning operation, the shape-adaptive inverse scanning part 444 receives a control signal�a signal indicative of whether or not the currently scanned segment contains an associated transform coefficient�from the shape-adaptive inverse scan control unit 440, in order to skip segments containing no transform coefficient from the scan order. In accordance with the present invention, therefore, it is possible to decode the bitstreams generated by way of reducing the number of zero coefficients unnecessarily inserted irrespective of non-existence of transform coefficients in the case of the conventional scanning methods.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4951157 *Jul 26, 1988Aug 21, 1990Korea Advanced Institute Of Science And TechnologySymmetrical image block scanning method for reducing block effectUS5045938 *Jul 24, 1990Sep 3, 1991Victor Company Of Japan, Ltd.Method and apparatus for encoding using variable length codesUS5086488 *Aug 9, 1990Feb 4, 1992Mitsubishi Denki Kabushiki KaishaTransform coding apparatusUS5339164 *Dec 24, 1991Aug 16, 1994Massachusetts Institute Of TechnologyMethod and apparatus for encoding of data using both vector quantization and runlength encoding and using adaptive runlength encodingUS5598484 *Feb 8, 1995Jan 28, 1997Fuji Xerox Co., Ltd.Apparatus for encoding an image signal* Cited by examinerNon-Patent CitationsReference1 *Sikora et al., "Shape-adaptive DCT for generic coding of video", IEEE Transactions , vol. 5, Issue 1, pp. 59-62, Feb. 1995.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS7602805 *Aug 29, 2003Oct 13, 2009Gary ParnesCircuits and methods for detecting the mode of a telecommunications signalUS20120082235 *Oct 5, 2011Apr 5, 2012General Instrument CorporationCoding and decoding utilizing context model selection with adaptive scan patternEP2257072A1 *May 27, 2009Dec 1, 2010Nxp B.V.Image and video coding* Cited by examinerClassifications U.S. Classification382/250, 375/240.2International ClassificationG06K9/36Cooperative ClassificationH04N19/115, H04N19/21, H04N19/17, H04N19/61, H04N19/18, H04N19/543, H04N19/132, H04N19/129, H04N19/12, H04N19/14European ClassificationH04N7/26J2, H04N7/26A4K, H04N7/26M2N4, H04N7/26A8R, H04N7/26A4S, H04N7/26A6C2, H04N7/50, H04N7/26A8C, H04N7/26A4Z, H04N7/26A4ELegal EventsDateCodeEventDescriptionFeb 23, 2012FPAYFee paymentYear of fee payment: 4Sep 4, 2002ASAssignmentOwner name: HYUNDAI CURITEL, INC., KOREA, REPUBLIC OFFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:HYNIX SEMICONDUCTOR INC.;REEL/FRAME:013235/0032Effective date: 20010725Effective date: 20010329Free format text: CHANGE OF NAME;ASSIGNOR:HYUNDAI ELECTRONICS IND. CO. LTD.;REEL/FRAME:013531/0590Owner name: HYNIX SEMICONDUCTOR, KOREA, REPUBLIC OFRotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services