Derivation of the position in scan order of the last significant transform coefficient in video coding

This application claims the benefit of U.S. Provisional Application No. 61/502,269, filed Jun. 28, 2011, U.S. Provisional Application No. 61/503,529, filed Jun. 30, 2011, U.S. Provisional Application No. 61/550,775, filed Oct. 24, 2011, and U.S. Provisional Application No. 61/550,784, filed Oct. 24, 2011, the entire content of which are hereby incorporated by reference.

TECHNICAL FIELD

This disclosure relates to techniques for encoding and decoding video data. More particularly, this disclosure relates to signaling positions of significant transform coefficients that represent information in the video data.

BACKGROUND

Digital video capabilities may be incorporated into a wide range of devices, including digital televisions, digital direct broadcast systems, wireless broadcast systems, personal digital assistants (PDAs), laptop or desktop computers, digital cameras, digital recording devices, digital media players, video gaming devices, video game consoles, cellular or satellite radio telephones, video teleconferencing devices, and the like. Digital video devices implement video compression techniques, such as those described in the standards defined by MPEG-2, MPEG-4, ITU-T H.263 or ITU-T H.264/MPEG-4, Part 10, Advanced Video Coding (AVC), and extensions of such standards, to transmit and receive digital video information more efficiently.

Video compression techniques perform spatial prediction and/or temporal prediction to reduce or remove redundancy inherent in video sequences. For block-based video coding, a video frame or slice may be partitioned into blocks. Each block may be further partitioned. Blocks in an intra-coded (I) frame or slice are encoded using spatial prediction with respect to neighboring blocks. Blocks in an inter-coded (P or B) frame or slice may use spatial prediction with respect to neighboring blocks in the same frame or slice or temporal prediction with respect to other reference frames.

SUMMARY

This disclosure relates generally to techniques for signaling a position of a last significant coefficient (LSC) in a block of transform coefficients during video coding. For example, the techniques provide for a video decoder that receives a block-based LSC indicator for a LSC of a block of transform coefficients. The block-based LSC indicator indicates coordinates of the LSC when the block is scanned according to a scanning order. The video decoder converts the block-based LSC indicator to a scan-based LSC indicator. The scan-based LSC indicator indicates an ordinal position of the LSC according to the scanning order. The video decoder may then use the scan-based LSC indicator to decode a significance map.

In one example, this disclosure describes a method for decoding video data. The method comprises converting a block-based LSC indicator into a scan-based LSC indicator. The block-based LSC indicator indicates coordinates of a last significant coefficient of a block of transform coefficients according to a scanning order. The scan-based LSC indicator indicates an ordinal position of the LSC according to the scanning order. The method also comprises decoding, based on the scan-based LSC indicator, a significance map for the block.

In another example, this disclosure describes a video decoding device comprising one or more processors configured to convert a block-based LSC indicator into a scan-based LSC indicator. The block-based LSC indicator indicates coordinates of a last significant coefficient of a block of transform coefficients according to a scanning order. The scan-based LSC indicator indicates an ordinal position of the LSC according to the scanning order. The one or more processors are also configured to decode, based on the scan-based LSC indicator, a significance map for the block.

In another example, this disclosure describes a video decoding device comprising means for converting a block-based LSC indicator into a scan-based LSC indicator. The block-based LSC indicator indicates coordinates of a last significant coefficient of a block of transform coefficients according to a scanning order. The scan-based LSC indicator indicates an ordinal position of the LSC according to the scanning order. The video decoding device also comprises means for decoding, based on the scan-based LSC indicator, a significance map for the block.

In another example, this disclosure describes computer program product that comprises a computer-readable storage medium having instructions stored thereon that configure one or more processors to convert a block-based LSC indicator into a scan-based LSC indicator. The block-based LSC indicator indicates coordinates of a last significant coefficient of a block of transform coefficients according to a scanning order. The scan-based LSC indicator indicates an ordinal position of the LSC according to the scanning order. The instructions also configure the one or more processors to decode, based on the scan-based LSC indicator, a significance map for the block.

The details of one or more aspects of the disclosure are set forth in the accompanying drawings and the description below. Other features, objects, and advantages of the techniques described in this disclosure will be apparent from the description and drawings, and from the claims.

BRIEF DESCRIPTION OF THE DRAWINGS

<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram that illustrates an example video coding system.

<figref idref="DRAWINGS">FIG. 2</figref> is a conceptual diagram that illustrates an example transform coefficient block.

<figref idref="DRAWINGS">FIG. 3</figref> is a conceptual diagram that illustrates example scanning orders.

<figref idref="DRAWINGS">FIG. 4</figref> is a conceptual diagram that illustrates a two-dimensional representation of an example significance map for the transform coefficient block of <figref idref="DRAWINGS">FIG. 2</figref>.

<figref idref="DRAWINGS">FIG. 5</figref> is a block diagram that illustrates an example configuration of a video encoder.

<figref idref="DRAWINGS">FIG. 6</figref> is a block diagram that illustrates an example configuration of a video decoder.

<figref idref="DRAWINGS">FIG. 7</figref> is a flowchart that illustrates an example operation performed by the video encoder.

<figref idref="DRAWINGS">FIG. 8</figref> is a flowchart that illustrates an example operation to decode a transform coefficient block.

<figref idref="DRAWINGS">FIG. 9</figref> is a flowchart that illustrates an example non-iterative operation to convert a block-based last significant coefficient (LSC) indicator into a scan-based LSC indicator.

<figref idref="DRAWINGS">FIG. 10</figref> is a flowchart that illustrates another example non-iterative operation to convert a block-based LSC indicator into a scan-based LSC indicator.

<figref idref="DRAWINGS">FIG. 11</figref> is a flowchart that illustrates an example operation to convert a block-based LSC indicator into a scan-based LSC indicator in which a map data structure is accessed.

<figref idref="DRAWINGS">FIG. 12</figref> is a flowchart that illustrates an example iterative operation to convert a block-based LSC indicator into a scan-based LSC indicator.

<figref idref="DRAWINGS">FIG. 13</figref> is a conceptual diagram of a transform coefficient block showing a last significant transform coefficient.

DETAILED DESCRIPTION

The attached drawings illustrate examples. Elements indicated by reference numbers in the attached drawings correspond to elements indicated by like reference numbers in the following description. In this disclosure, elements having names that start with ordinal words (e.g., “first,” “second,” “third,” and so on) do not necessarily imply that the elements have a particular order. Rather, such ordinal words are merely used to refer to different elements of a same or similar type.

As described below, a video encoder may generate transform coefficient blocks. Each of the transform coefficient blocks may be a two-dimensional array of transform coefficients. After the video encoder generates a transform coefficient block, the video encoder may identify a last significant coefficient (LSC) of the transform coefficient block according to the scanning order. In other words, when the transform coefficients of the transform coefficient block are sequenced according to the scanning order, the LSC of the transform coefficient block is the last non-zero transform coefficient. The scanning order may start at a DC transform coefficient (i.e., the top-left transform coefficient) of the transform coefficient block.

The video encoder may output a scan-based LSC indicator that indicates an ordinal position of the LSC according to the scanning order. In other words, the video encoder may output a scan-based LSC indicator that indicates that the LSC is the n'th transform coefficient when the transform coefficients are sequenced according to the scanning order.

In some conventional video encoders, the video encoder may perform a series of coding passes on the transform coefficient block. During each of the coding passes, the video encoder may process the transform coefficients of the transform coefficient block according to the scanning order. During each of the coding passes, the video encoder encodes information about the transform coefficients.

During one of the coding passes, the video encoder generates a significance map. The significance map includes a series of significance flags that indicate whether transform coefficients in the transform coefficient block are significant (i.e., non-zero). To generate the significance map, the video encoder may process each of the transform coefficients according to the scanning order. When the video encoder processes a transform coefficient, the video encoder may determine whether the ordinal position of the transform coefficient occurs before the ordinal position of the LSC according to the scanning order. If so, the video encoder may generate a significance flag for the transform coefficient. The significance flag may have a value of “1” if the value of the transform coefficient is non-zero. The significance flag may have a value of “0” if the value of the transform coefficient is equal to zero. However, if the ordinal position of the transform coefficient does not occur before the ordinal position of the LSC according to the scanning order, the video encoder does not generate a significance flag for the transform coefficient.

A video decoder may receive the scan-based LSC indicator and the significance map of the transform coefficient block. The video decoder may then determine, based on the scan-based LSC indicator, whether the significance map includes significance flags for particular transform coefficients of the transform coefficient block. If the video encoder does not generate a significance flag for a transform coefficient, the video decoder may infer that the transform coefficient is not significant.

In some instances, the video encoder may generate a block-based LSC indicator that indicates the coordinates within the transform coefficient block of the LSC. The video encoder may then CABAC encode the block-based LSC indicator. Because of the statistical relationships between the x and y coordinates, it may require fewer bits to indicate the position of the LSC using the block-based LSC indicator than to indicate the position of the LSC in terms of the ordinal position of the LSC.

Furthermore, in some instances, it may require fewer bits to represent the significance map when the video encoder uses a reverse of the scanning order to generate the significance map rather than when the video encoder uses the scanning order to generate the significance map. However, if the video encoder generates a block-based LSC indicator and if the video encoder uses the reverse scanning order to generate the significance map, the video decoder may be unable to determine, based on the block-based LSC indicator, whether the ordinal position of a transform coefficient occurs before the ordinal position of LSC of the transform coefficient block. Consequently, the video decoder may be unable to determine, based on the block-based LSC indicator, whether the significance map includes significance flags for particular transform coefficients.

To address this problem, the video decoder may, in accordance with the techniques of this disclosure, perform a conversion operation that converts the block-based LSC indicator into a scan-based LSC indicator. The scan-based LSC indicator may indicate the ordinal position of the LSC according to the scanning order. The video decoder may then decode, based on the scan-based LSC indicator, the significance map for the block.

As described herein, the video decoder may convert the block-based LSC indicator into the scan-based LSC indicator in various ways. For example, the video decoder may perform a non-iterative algorithm to derive the scan-based LSC indicator from the block-based LSC indicator. In another example, the video decoder may convert the block-based LSC indicator into the scan-based LSC indicator at least in part by accessing a data structure that maps block-based LSC indicators to scan-based LSC indicators. In yet another example, the video decoder may perform a loop operation that scans through positions in a transform coefficient block according to the scanning order until a position having the coordinates of the block-based LSC indicator is reached. In this example, the video decoder may increment the scan-based LSC indicator for each position of the transform coefficient block prior to the position having the coordinates.

<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram that illustrates an example video coding system <b>10</b> that may utilize the techniques described in this disclosure. In this disclosure, the term “video coding” may refer to video encoding and video decoding. As shown in <figref idref="DRAWINGS">FIG. 1</figref>, video coding system <b>10</b> includes a source device <b>12</b> and a destination device <b>14</b>. Source device <b>12</b> generates encoded video data. Destination device <b>14</b> may decode the encoded video data at a later time. Source device <b>12</b> and destination device <b>14</b> may comprise any of a wide range of devices, including desktop computers, notebook (i.e., laptop) computers, tablet computers, set-top boxes, mobile telephones, telephone handsets, “smart” pads, televisions, cameras, display devices, digital media players, video gaming consoles, video streaming devices, or types of computing devices capable of encoding and decoding video data.

Destination device <b>14</b> may receive the encoded video data via a channel <b>16</b>. Channel <b>16</b> may comprise a medium or device capable of moving the encoded video data from source device <b>12</b> to destination device <b>14</b>. In one example, channel <b>16</b> may comprise a communication medium that enables source device <b>12</b> to transmit encoded video data directly to destination device <b>14</b> in real-time. Source device <b>12</b> or another device may modulate the encoded video data according to a communication standard, such as a wireless communication protocol. The communication medium may comprise any wireless or wired communication medium, such as a radio frequency (RF) spectrum or one or more physical transmission lines. Channel <b>16</b> may form part of a packet-based network, such as a local area network, a wide-area network, or a global network such as the Internet. Channel <b>16</b> may include routers, switches, base stations, or any other equipment that may be useful to facilitate communication of the encoded video data from source device <b>12</b> to destination device <b>14</b>.

In some examples, source device <b>12</b> and destination device <b>14</b> may be equipped for wireless communication. However, the techniques of this disclosure are not necessarily limited to wireless applications or settings. Rather, the techniques may be applied to video coding in support of any of a variety of multimedia applications, such as over-the-air television broadcasts, cable television transmissions, satellite television transmissions, streaming video transmissions, e.g., via the Internet, encoding of digital video for storage on a data storage medium, decoding of digital video stored on a data storage medium, or other applications. In some examples, source device <b>12</b> and destination device <b>14</b> may be configured to support one-way or two-way video transmission to support applications such as video streaming, video playback, video broadcasting, and/or video telephony.

Furthermore, in some examples, source device <b>12</b> may output the encoded video data to a storage system <b>34</b>. Similarly, destination device <b>14</b> may access encoded video data stored on storage system <b>34</b>. In various examples, storage system <b>34</b> may include various distributed or locally accessed data storage media. Example types of data storage media include, but are not limited, to hard drives, Blu-ray discs, DVDs, CD-ROMs, solid state memory units, volatile or non-volatile memory, or other digital storage media suitable for storing encoded video data.

In some examples, storage system <b>34</b> may comprise a file server or another intermediate storage device that may hold the encoded video generated by source device <b>12</b>. Destination device <b>14</b> may access stored video data from storage system <b>34</b> via streaming or download. The file server may be any type of server capable of storing encoded video data and transmitting that encoded video data to destination device <b>14</b>. Example file servers include a web server (e.g., for a website), an FTP server, network attached storage (NAS) devices, or a local disk drive. Destination device <b>14</b> may access the encoded video data through any standard data connection, including an Internet connection. This may include a wireless channel (e.g., a Wi-Fi connection), a wired connection (e.g., DSL, cable modem, etc.), or a combination of both that is suitable for accessing encoded video data stored on a file server. The transmission of encoded video data from storage system <b>34</b> may be a streaming transmission, a download transmission, or a combination of both.

In the example of <figref idref="DRAWINGS">FIG. 1</figref>, source device <b>12</b> includes a video source <b>18</b>, a video encoder <b>20</b> and an output interface <b>22</b>. In some examples, output interface <b>22</b> may also include a modulator/demodulator (modem) and/or a transmitter. Video source <b>18</b> provides video data to video encoder <b>20</b>. In various examples, video source <b>18</b> may comprise various types of devices and/or systems for providing video data. For example, video source <b>18</b> may comprise a video capture device, such as a video camera. In another example, video source <b>18</b> may comprise a video archive that contains previously captured video. In yet another example, video source <b>18</b> may comprise a video feed interface that receives video from a video content provider. In yet another example, video source <b>18</b> may comprise a computer graphics system for generating computer graphics data.

As described in detail below, video encoder <b>20</b> may encode the video data provided by video source <b>18</b>. In some examples, source device <b>12</b> may transmit the encoded video data directly to destination device <b>14</b> via output interface <b>22</b>. Moreover, in some examples, storage system <b>34</b> may store the encoded video data for later access by destination device <b>14</b> or other devices.

This disclosure may generally refer to video encoder <b>20</b> “signaling” certain information to another device, such as video decoder <b>30</b>. It should be understood, however, that video encoder <b>20</b> may signal information by associating certain syntax elements with various encoded portions of video data. That is, video encoder <b>20</b> may “signal” data by storing certain syntax elements to headers of various encoded portions of video data. In some cases, such syntax elements may be encoded and stored (e.g., stored to storage system <b>34</b>) prior to being received and decoded by video decoder <b>30</b>. Thus, the term “signaling” may generally refer to the communication of syntax or other data used to decode the compressed video data. Such communication may occur in real- or near-real-time. Alternately, such communication may occur over a span of time, such as might occur when storing syntax elements to a medium at the time of encoding, which then may be retrieved by a decoding device at any time after being stored to this medium.

In the example of <figref idref="DRAWINGS">FIG. 1</figref>, destination device <b>14</b> includes an input interface <b>28</b>, a video decoder <b>30</b>, and a display device <b>32</b>. In some examples, input interface <b>28</b> may include a receiver and/or a modem. Input interface <b>28</b> of destination device <b>14</b> receives encoded video data from channel <b>16</b> and/or storage system <b>34</b>. Video decoder <b>30</b> decodes the encoded video data received by input interface <b>28</b>. Destination device <b>14</b> may render the decoded video data for display on display device <b>32</b>.

Display device <b>32</b> may be integrated with or may be external to destination device <b>14</b>. In some examples, destination device <b>14</b> may include an integrated display device and also be configured to interface with an external display device. In various examples, display device <b>32</b> may comprise various types of display devices. For example, display device <b>32</b> may comprise a liquid crystal display (LCD), a plasma display, an organic light emitting diode (OLED) display, or another type of display device.

Although not shown in <figref idref="DRAWINGS">FIG. 1</figref>, in some aspects, video encoder <b>20</b> and video decoder <b>30</b> may each be integrated with an audio encoder and decoder, and may include appropriate MUX-DEMUX units, or other hardware and software, to handle encoding of both audio and video in a common data stream or separate data streams. If applicable, in some examples, MUX-DEMUX units may conform to the ITU H.223 multiplexer protocol, or other protocols such as the user datagram protocol (UDP).

Video encoder <b>20</b> and video decoder <b>30</b> each may be implemented as any of a variety of suitable circuitry, such as one or more microprocessors, digital signal processors (DSPs), application specific integrated circuits (ASICs), field programmable gate arrays (FPGAs), discrete logic, software, hardware, firmware or any combinations thereof. When the techniques are implemented partially in software, a device may store instructions for the software in a suitable, non-transitory computer-readable medium and execute the instructions in hardware using one or more processors to perform the techniques of this disclosure. Each of video encoder <b>20</b> and video decoder <b>30</b> may be included in one or more encoders or decoders, either of which may be integrated as part of a combined encoder/decoder (CODEC) in a respective device.

Video encoder <b>20</b> and video decoder <b>30</b> may operate according to a video compression standard, such as the High Efficiency Video Coding (HEVC) standard presently under development, and may conform to the HEVC Test Model (HM). Alternatively, video encoder <b>20</b> and video decoder <b>30</b> may operate according to other proprietary or industry standards, such as the ITU-T H.264 standard, alternatively referred to as MPEG-4, Part 10, Advanced Video Coding (AVC), or extensions of such standards. Example extensions to standards include the scalable video coding (SVC) and Multiview Video Coding (MVC) extensions to the H.264/AVC standard. The techniques of this disclosure are not limited to any particular coding standard. Other examples of video compression standards include MPEG-2 and ITU-T H.263.

As mentioned briefly above, video encoder <b>20</b> encodes video data. The video data may comprise one or more sequences of pictures. Each of the pictures is a still image. In some instances, a picture may be referred to as a “frame.” When video encoder <b>20</b> encodes the video data, video encoder <b>20</b> may generate a bitstream. The bitstream includes a sequence of bits that form a representation of coded pictures and associated data. A coded picture is a coded representation of a picture.

To generate the bitstream, video encoder <b>20</b> may perform an encoding operation for sequences of pictures in the video data. When video encoder <b>20</b> performs the encoding operation for a sequence of pictures, video encoder <b>20</b> may generate a series of coded pictures and associated data. In addition, video encoder <b>20</b> may generate a sequence parameter set that contains parameters applicable to zero or more sequences of pictures. Furthermore, video encoder <b>20</b> may generate picture parameter sets (PPSs) that contain parameters applicable to zero or more pictures as a whole. In some examples, video encoder <b>20</b> may generate adaptation parameter sets (APSs). The APS may store parameters applicable to zero or more picture as a whole.

To generate a coded picture, video encoder <b>20</b> may partition a picture into one or more equally-sized video blocks. Each of the video blocks may be associated with a treeblock. A video block may be a two-dimensional (2D) block of video data (e.g., samples). In some instances, a treeblock may also be referred to as a largest coding unit (LCU). The treeblocks of HEVC may be broadly analogous to the macroblocks of previous standards, such as H.264/AVC. However, a treeblock is not necessarily limited to a particular size and may include one or more coding units (CUs).

In some examples, video encoder <b>20</b> may partition a picture into a plurality of slices. Each of the slices may include an integer number of CUs. In some instances, a slice comprises an integer number of treeblocks. In other instances, a boundary of a slice may be within a treeblock. If the boundary of a slice is within a treeblock, the slice may be referred to as a fine granular slice. In some examples, video encoder <b>20</b> may encode slices according to the size in bytes of the slices or according to the number of treeblocks in the slices.

As part of performing an encoding operation for a picture, video encoder <b>20</b> may perform encoding operations for each slice of the picture. The encoding operation for a slice may generate encoded data associated with the slice. The encoded data associated with the slice may be referred to as a “coded slice.” The coded slice may include a slice header and slice data. The slice data may include a series of successive coding units in coding order. The slice header may contain data elements pertaining to the first or all treeblocks of the slice.

To generate the coded slice data for a slice, video encoder <b>20</b> may perform encoding operations on each treeblock in the slice. When video encoder <b>20</b> performs the encoding operation on a treeblock, video encoder <b>20</b> may generate a coded treeblock. The coded treeblock may comprise data representing an encoded version of the treeblock.

To generate a coded treeblock, video encoder <b>20</b> may recursively perform quadtree partitioning on the video block of a treeblock to divide the video block into progressively smaller video blocks. Each of the smaller video blocks may be associated with a different CU. For example, video encoder <b>20</b> may partition the video block of a treeblock into four equally-sized sub-blocks, partition one or more of the sub-blocks into four equally-sized sub-sub-blocks, and so on. One or more syntax elements in the bitstream may indicate a maximum number of times video encoder <b>20</b> may partition a video block of a treeblock. The syntax elements may also indicate a smallest coding unit (SCU). A video block of a CU may be square in shape.

Video encoder <b>20</b> may perform encoding operations on each non-partitioned CU in a treeblock. As part of performing an encoding operation on a non-partitioned CU, video encoder <b>20</b> may generate one or more prediction units (PUs) for the CU. Each of the PUs of the CU may be associated with a different video block within the video block of the CU. Video encoder <b>20</b> may use intra prediction or inter prediction to generate prediction data for the PUs of the CU. When video encoder <b>20</b> uses intra prediction to generate the prediction data for a PU, video encoder <b>20</b> derives the prediction data for the PU from decoded samples of the picture that contains the PU. When video encoder <b>20</b> uses inter prediction to generate the prediction data for the PU, video encoder <b>20</b> derives the prediction data for the PU from decoded values of reference pictures other than the picture that contains the CU. The prediction data for a PU may include a predicted video block and various syntax elements.

After video encoder <b>20</b> generates prediction data for a CU, video encoder <b>20</b> may generate residual data for the CU. The residual data for the CU may indicate differences between samples in the predicted video blocks for the PUs of the CU and the samples in the original video block of the CU.

Each non-partitioned CU of a treeblock may have one or more transform units (TUs). Each TU of a CU may be associated with a different portion of the residual data of the CU. Video encoder <b>20</b> may perform a transform operation for each TU of the CU. When video encoder <b>20</b> performs the transform operation for a TU, video encoder <b>20</b> may generate a transform coefficient block at least in part by applying a transform to residual data associated with the TU. The transform coefficient block may be a 2D matrix of transform coefficients. <figref idref="DRAWINGS">FIG. 2</figref> is a conceptual diagram that illustrates an example transform coefficient block.

Video encoder <b>20</b> may quantize the transform coefficients in a transform coefficient block. Quantization generally refers to a process in which transform coefficients in a transform coefficient block are quantized to possibly reduce the amount of data used to represent the transform coefficients, providing further compression. Quantization may reduce the bit depth associated with some or all of the transform coefficients. For example, an n-bit value may be rounded down to an m-bit value during quantization, where n is greater than m.

After quantizing a transform coefficient block, video encoder <b>20</b> may generate a set of syntax elements associated with the transform coefficient block. Video encoder <b>20</b> may then perform Context Adaptive Binary Arithmetic Coding (CABAC) operations on some of these syntax elements. In other examples, video encoder <b>20</b> may perform other entropy coding operations on the syntax elements. For instance, video encoder <b>20</b> may perform context adaptive variable length coding (CAVLC) operations, syntax-based context-adaptive binary arithmetic coding (SBAC) operations, Probability Interval Partitioning Entropy (PIPE) coding operations, or another type of entropy encoding operation on the syntax elements associated with the transform coefficient block. Video encoder <b>20</b> may also perform CABAC operations on other syntax elements associated with the video data.

After video encoder <b>20</b> generates the syntax elements associated with the transform coefficient block and performs the CABAC operations, video encoder <b>20</b> may include the resulting data in a bitstream for the video data. The bitstream may include a sequence of bits that forms a representation of coded pictures and associated data.

The bitstream may comprise a sequence of network abstraction layer (NAL) units. Each of the NAL units may be a syntax structure containing an indication of a type of data in the NAL unit and bytes containing the data. For example, a NAL unit may contain data representing a PPS, an APS, a coded slice, supplemental enhancement information, an access unit delimiter, filler data, or another type of data. The data of a NAL unit may be in the form of a raw byte sequence payload (RBSP) interspersed with emulation prevention bits. A RBSP may be a syntax structure containing an integer number of bytes that is encapsulated within a NAL unit.

When video encoder <b>20</b> performs an entropy encoding operation on a transform coefficient block, video encoder <b>20</b> may determine whether there is at least one significant (i.e., non-zero) transform coefficient in the transform coefficient block. If there is at least one significant transform coefficient in the transform coefficient block, video encoder <b>20</b> may update a coded block flag (CBF) to indicate that the transform coefficient block includes at least one significant transform coefficient. If there are no significant transform coefficients in the transform coefficient block, video encoder <b>20</b> may update the CBF to indicate that the transform coefficient block does not include any significant transform coefficients.

If there is at least one significant transform coefficient in the transform coefficient block, video encoder <b>20</b> may identify a last significant coefficient (LSC) of the transform coefficient block according to a scanning order. The LSC of the transform coefficient block is the non-zero transform coefficient that occurs last when the transform coefficients of the transform coefficient block are sequenced according to the scanning order. The scanning order may be a forward scanning order. In other words, the scanning order may start at a DC transform coefficient of the transform coefficient block. The DC transform coefficient occurs at a top left corner of the transform coefficient block. In contrast, reverse or inverse scanning orders start at a bottom right transform coefficient of a transform coefficient block.

Video encoder <b>20</b> may identify the LSC of the transform coefficient block according to various scanning orders. For example, video encoder <b>20</b> may identify the LSC according to a zigzag scanning order, a horizontal scanning order, a vertical scanning order, a diagonal scanning order, or a sub-block scanning order. In some examples, if the transform coefficient block is associated with an intra-predicted CU, video encoder <b>20</b> may select the scanning order based on an intra-prediction mode associated with the CU. Furthermore, in some examples, video encoder <b>20</b> may adaptively switch between scanning orders to optimize coding efficiency and/or subjective picture quality.

<figref idref="DRAWINGS">FIG. 3</figref> is a conceptual diagram that illustrates example scanning orders. Part (a) of <figref idref="DRAWINGS">FIG. 3</figref> shows an example zigzag scanning order. Part (b) of <figref idref="DRAWINGS">FIG. 3</figref> shows an example horizontal scanning order. Part (c) of <figref idref="DRAWINGS">FIG. 3</figref> shows an example vertical scanning order. Part (d) of <figref idref="DRAWINGS">FIG. 3</figref> shows an example reverse diagonal scanning order.

Part (e) of <figref idref="DRAWINGS">FIG. 3</figref> shows an example diagonal sub-block scanning order. In a sub-block scanning order, video encoder <b>20</b> may split a large transform coefficient block into sub-blocks. In the example of <figref idref="DRAWINGS">FIG. 3</figref>, the sub-blocks are shown as dashed-line squares. For each of the sub-blocks, video encoder <b>20</b> may process the transform coefficients of the sub-block in a particular order. In the example of <figref idref="DRAWINGS">FIG. 3</figref>, video encoder <b>20</b> scans the transform coefficients in a upper-left sub-block in an up/right diagonal order, then scans the transform coefficients in a lower-left sub-block in the up/right diagonal order, then scans the transform coefficients in the upper-right sub-block in the up/right diagonal order, and finally scans the transform coefficients in the lower-right sub-block in the up/right diagonal order.

In other examples, video encoder <b>20</b> may partition the transform coefficient block into 4×4 sub-blocks (or other sub-block sizes). In this example, video encoder <b>20</b> may then process each of the 4×4 transform coefficient blocks according to the scanning order.

After identifying the LSC, video encoder <b>20</b> may generate a block-based LSC indicator. The block-based LSC indicator specifies the coordinates of the LSC. For example, if the transform coefficient block is 8×8, the scanning order is the horizontal scanning order, and video encoder <b>20</b> determines that the LSC occurs at the 10^thposition when the transform coefficients of the transform coefficient block are sequenced according to the scanning order, video encoder <b>20</b> may generate a block-based LSC indicator specifying coordinates (1, 1).

Video encoder <b>20</b> may perform a CABAC encoding operation on the block-based LSC indicator. In some instances, performing the CABAC encoding operation on the block-based LSC indicator may be more efficient than performing the CABAC encoding operation on a corresponding scan-based LSC indicator because the entropy encoding operation may be able to exploit statistical relationships between the x-coordinate and the y-coordinate of the block-based LSC indicator. Video encoder <b>20</b> may add the CABAC encoded version of the block-based LSC indicator to the encoded bitstream.

After identifying the LSC, video encoder <b>20</b> may perform one or more coding passes on the transform coefficient block to generate and encode syntax elements associated with the transform coefficient block. The syntax elements associated with the transform coefficient block include a significance map for the transform coefficient block, and level information for the transform coefficients.

In each of the coding passes, video encoder <b>20</b> may scan through the transform coefficients of the transform coefficient block according to a reverse scanning order. The reverse scanning order may be a reverse of the scanning order used to identify the LSC. For example, if video encoder <b>20</b> identified the LSC according to a forward diagonal scanning order, the reverse scanning order may be a reverse diagonal scanning order.

For each transform coefficient processed during a first coding pass, video encoder <b>20</b> may determine whether the ordinal position of the transform coefficient occurs before the ordinal position of the LSC. If the ordinal position of the transform coefficient occurs before the ordinal position of the LSC, video encoder <b>20</b> may generate and CABAC encode a syntax element (i.e., a significance flag) that indicates whether the transform coefficient is significant. A transform coefficient may be “significant” if the transform coefficient is non-zero. If the transform coefficient does not occur before the ordinal position of the LSC, video encoder <b>20</b> does not generate or CABAC encode a significance flag for the transform coefficient. In this way, video encoder <b>20</b> may generate and CABAC encode a significance map for the transform coefficient block. After generating and CABAC encoding the significance map, video encoder <b>20</b> may include the CABAC encoded version of the significance map in the bitstream.

In some instances, there may be statistical relationships between the position of the LSC and the content of the significance map. Accordingly, video encoder <b>20</b> may use the position of the LSC to select one or more context models for use in CABAC encoding the significance flags of the significance map.

For each transform coefficient processed during a second coding pass, video encoder <b>20</b> may determine whether the transform coefficient is significant. If the transform coefficient is significant, video encoder <b>20</b> may generate and CABAC encode a syntax element (i.e., a level-greater-than-one flag) that indicates whether the absolute value of the transform coefficient is greater than one. If the transform coefficient is not significant, video encoder <b>20</b> does not generate or CABAC encode a level-greater-than-one flag for the transform coefficient. After generating and CABAC encoding the level-greater-than-one flags, video encoder <b>20</b> may include the CABAC encoded version of the level-greater-than-one flags in the bitstream.

During a third coding pass, video encoder <b>20</b> may generate and CABAC encode syntax elements indicating whether the absolute values of the transform coefficients are greater than two (i.e., level-greater-than-two flags). After generating and CABAC encoding the level-greater-than-two flags, video encoder <b>20</b> may include the CABAC encoded version of the level-greater-than-two flags in the bitstream.

For each transform coefficient processed during a fourth coding pass, video encoder <b>20</b> may determine whether the transform coefficient is significant. If the transform coefficient is significant, video encoder <b>20</b> may generate a syntax element (i.e., a sign flag) that indicates whether the transform coefficient is positive or negative. If the transform coefficient is not significant, video encoder <b>20</b> does not generate a sign flag for the transform coefficient. After generating the sign flags, video encoder <b>20</b> may include the sign flags in the bitstream.

For each transform coefficient processed during a fifth coding pass, video encoder <b>20</b> may determine whether the transform coefficient is significant. If the transform coefficient is significant, video encoder <b>20</b> may generate a remainder value for the coefficient (i.e., level-remainder elements). Video encoder <b>20</b> may then identify a Golomb-Rice code that corresponds to the remainder value. After identifying the Golomb-Rice code for the transform coefficient, video encoder <b>20</b> may include the Golomb-Rice code in the bitstream. If the transform coefficient is not significant, video encoder <b>20</b> does not generate a level-remainder element for the transform coefficient.

The syntax elements generated by the second, third, fourth, and fifth coding passes may constitute the level information of the transform coefficient block because the absolute values (i.e., levels) of the transform coefficients can be derived from these syntax elements.

When video decoder <b>30</b> receives a bitstream, video decoder <b>30</b> may perform a decoding operation that is generally reciprocal to the encoding operation performed by video encoder <b>20</b>. For instance, video decoder <b>30</b> may perform a decoding operation on each slice of the picture. When video decoder <b>30</b> performs the decoding operation on a slice of the picture, video decoder <b>30</b> may perform decoding operations on the treeblocks in the slice. When video decoder <b>30</b> completes the decoding operation on a treeblock, video decoder <b>30</b> has decoded the samples in the video block associated with the treeblock. When video decoder <b>30</b> has decoded the samples for each treeblock of a slice, video decoder <b>30</b> has reconstructed the samples for the slice.

When video decoder <b>30</b> performs the decoding operation for a treeblock, video decoder <b>30</b> may perform a decoding operation for each non-partitioned CU within the treeblock. As discussed above, non-partitioned CUs may be partitioned into one or more TUs. Each of the TUs is associated with one or more transform coefficient blocks. In this disclosure, a TU is a “significant TU” if the transform coefficient block associated with the TU includes one or more significant transform coefficients.

When video decoder <b>30</b> performs a decoding operation on a non-partitioned CU, video decoder <b>30</b> may receive encoded level information for transform coefficient blocks associated with significant TUs of the CU, encoded significance maps for transform coefficient blocks associated with the significant TUs of the CU, and encoded block-based LSC indicators for the transform coefficient blocks associated with the significant TUs of the CU.

Because video encoder <b>20</b> does not generate significance flags for transform coefficients that occur after the ordinal position of the LSC according to the scanning order, video decoder <b>30</b> may be unable to determine which transform coefficients have significance flags until video decoder <b>30</b> is able to determine the ordinal position of the LSC. Moreover, because video encoder <b>20</b> does not generate level-greater-than-one flags, level-greater-than-two flags, sign flags, or level-remainder elements for non-significant coefficients, video decoder may be unable to determine which transform coefficients have level-greater-than-one flags, level-greater-than-two flags, sign flags, or level-remainder elements until video decoder <b>30</b> is able to determine the significance map.

Accordingly, video decoder <b>30</b> may first CABAC decode the block-based LSC indicator. In addition, video decoder <b>30</b> may convert the block-based LSC indicator into a scan-based LSC indicator. After the converting the block-based LSC indicator into the scan-based LSC indicator, video decoder <b>30</b> may decode, based on the scan-based LSC indicator, the significance map for the transform coefficient block. Video decoder <b>30</b> may then use the significance map to decode the level information of the transform coefficient block.

The scan-based LSC indicator indicates an ordinal position of the LSC according to the scanning order. The ordinal position of the LSC may be the relative position of the LSC in a sequence of transform coefficients formed by scanning the transform coefficient block according to the scanning order. For example, the transform coefficient block may be 8 transform coefficients by 8 transform coefficients and the block-based LSC indicator may specify the coordinates (1, 1). In this example, a transform coefficient at coordinates (1, 1) may be the 10^thtransform coefficient when the transform coefficients are sequenced according to the horizontal scanning order. Hence, in this example, video decoder <b>30</b> may generate a scan-based LSC indicator indicating the 10^thposition.

In accordance with the techniques of this disclosure, video decoder <b>30</b> may efficiently convert the block-based LSC indicator into the scan-based LSC indicator. Video decoder <b>30</b> may perform various operations to convert the block-based LSC indicator into the scan-based LSC indicator. For example, video decoder <b>30</b> may perform a non-iterative algorithm that derives the scan-based LSC indicator from the transform coordinates specified by the block-based LSC indicator. In another example, video decoder <b>30</b> may store a data structure that maps transform coordinates of block-based LSC indicators to scan-based LSC indicators. In this example, video decoder <b>30</b> may access this data structure to generate the scan-based LSC indicator.

In yet another example of how video decoder <b>30</b> may convert the block-based LSC indicator into the scan-based LSC indicator, video decoder <b>30</b> may generate the scan-based LSC indicator by performing a loop operation. In this example, an indicator may indicate a current transform coefficient of the given transform coefficient block. During each iteration of the loop operation, video decoder <b>30</b> may determine whether the current transform coefficient has the coordinates specified by the block-based LSC indicator. If not, video decoder <b>30</b> may increment the scan-based LSC indicator and update the indicator to indicate the next transform coefficient according to the scanning order. Thus, in this example, video decoder <b>30</b> may perform a loop operation that scans through positions in the given transform coefficient block according to the scanning order until a position having the coordinates is reached, incrementing the scan-based LSC indicator for each position of the given transform coefficient block prior to the position having the coordinates. In this example, the scanning order may be a sub-block scanning order in which the given transform coefficient is divided into sub-blocks. Video decoder <b>30</b> may scan through each of the transform coefficients in one of the sub-blocks before scanning through each of the transform coefficients in the next one of the sub-blocks.

In some examples, video decoder <b>30</b> may use different conversion operations based on different scanning orders. In other words, video decoder <b>30</b> may select a conversion operation based on a scanning order and use the selected conversion operation to convert a block-based LSC indicator to a scan-based LSC indicator. For example, video decoder <b>30</b> may use the non-iterative algorithm mentioned above when the scanning order is a reverse horizontal scanning order and video decoder <b>30</b> can use the mapping data structure mentioned above when the scanning order is a reverse diagonal scanning order.

In another example, video decoder <b>30</b> may use a combination of conversion operations. In this example, video decoder <b>30</b> may divide a transform coefficient block into sub-blocks. Video decoder <b>30</b> may use a non-iterative algorithm to identify the coordinates of the sub-blocks and the coordinates of the block-based LSC indicator within the sub-blocks. Video decoder <b>30</b> may then use another algorithm to determine the scanning order of the sub-blocks and a scanning order of the last significant transform coefficient within the sub-blocks. In this way, video decoder <b>30</b> may determine the scan-based LSC indicator.

<figref idref="DRAWINGS">FIG. 5</figref> is a block diagram that illustrates an example configuration of video encoder <b>20</b> that is configured to implement the techniques of this disclosure. <figref idref="DRAWINGS">FIG. 5</figref> is provided for purposes of explanation and should not be considered limiting of the techniques as broadly exemplified and described in this disclosure. For purposes of explanation, this disclosure describes video encoder <b>20</b> in the context of HEVC coding. However, the techniques of this disclosure may be applicable to other coding standards or methods.

In the example of <figref idref="DRAWINGS">FIG. 5</figref>, video encoder <b>20</b> includes a plurality of functional components. The functional components of video encoder <b>20</b> include a mode select module <b>40</b>, a motion estimation module <b>42</b>, a motion compensation module <b>44</b>, an intra-prediction module <b>46</b>, a residual generation module <b>50</b>, a transform module <b>52</b>, a quantization module <b>54</b>, a CABAC module <b>56</b>, an inverse quantization module <b>58</b>, an inverse transform module <b>60</b>, a reconstruction module <b>62</b>, and a decoded picture buffer <b>64</b>. In other examples, video encoder <b>20</b> may include more, fewer, or different functional components. For example, video encoder <b>20</b> may include a deblocking filter module to filter the output of reconstruction module <b>62</b> to remove blockiness artifacts from reconstructed video. Furthermore, motion estimation module <b>42</b> and motion compensation module <b>44</b> may be highly integrated, but are represented in the example of <figref idref="DRAWINGS">FIG. 5</figref> separately for purposes of explanation.

Video encoder <b>20</b> may receive video data. In various examples, video encoder <b>20</b> may receive the video data from various sources. For example, video encoder <b>20</b> may receive the video data from video source <b>18</b> (<figref idref="DRAWINGS">FIG. 1</figref>) or another source. The video data may represent sequences of pictures. To encode the video data, video encoder <b>20</b> may perform an encoding operation on each sequence of pictures.

As part of performing the encoding operation on a sequence of pictures, video encoder <b>20</b> may perform encoding operations on each picture within the sequence of pictures. As part of performing the encoding operation on a picture, video encoder <b>20</b> may perform encoding operations on each slice in the picture. As part of performing the encoding operation on a slice, video encoder <b>20</b> may perform an encoding operation on each treeblock in the slice.

As part of performing an encoding operation on a treeblock, video encoder <b>20</b> may partition the video block of the treeblock into one or more video blocks. Each of the video blocks may be associated with a different CU. In some examples, the sizes of the video blocks of the CUs may range from 8×8 pixels up to the size of the video block of the treeblock with a maximum of 64×64 pixels or greater. In this disclosure, “N×N” and “N by N” may be used interchangeably to refer to the pixel dimensions of a video block in terms of vertical and horizontal dimensions, e.g., 16×16 pixels or 16 by 16 pixels. In general, a 16×16 block has 16 pixels in a vertical direction (y=16) and 16 pixels in a horizontal direction (x=16). Likewise, an N×N block generally has N pixels in a vertical direction and N pixels in a horizontal direction, where N represents a nonnegative integer value. Similar notation may be used to indicate dimensions of transform coefficient blocks.

As part of performing the encoding operation for a treeblock, video encoder <b>20</b> may generate a hierarchical quadtree data structure for the treeblock. For example, a treeblock may correspond to a root node of the quadtree data structure. If video encoder <b>20</b> partitions the video block of the treeblock into four sub-blocks, the root node has four child nodes in the quadtree data structure. The child nodes correspond to the CUs associated with the sub-blocks. If video encoder <b>20</b> partitions one of the sub-blocks into four sub-sub-blocks, the node corresponding to the CU associated with the sub-block may have four child nodes, which correspond to the CUs associated with the sub-sub-blocks.

Each node of the quadtree data structure may provide syntax data for the corresponding CU. For example, a node in the quadtree may include a split flag, indicating whether the video block of the CU corresponding to the node is partitioned (i.e., split) into four sub-blocks. Syntax elements for a CU may be defined recursively, and may depend on whether the video block of the CU is split into sub-blocks. A CU whose video block is not partitioned may correspond to a leaf node in the quadtree data structure. A leaf node in the quadtree data structure may be referred to as a “coding node.” The data representing the encoded version of the treeblock may include data based on the quadtree data structure for the treeblock.

Video encoder <b>20</b> may perform encoding operations on each non-partitioned CU of the treeblock. When video encoder <b>20</b> performs the encoding operation on a non-partitioned CU, video encoder <b>20</b> generates data representing an encoded version of the non-partitioned CU.

As part of performing the encoding operation for a CU, motion estimation module <b>42</b> and motion compensation module <b>44</b> perform inter prediction on each PU of the CU. In other words, motion estimation module <b>42</b> and motion compensation module <b>44</b> may generate prediction data for each PU of the CU based on decoded samples of reference pictures other than the picture that contains the CU. Inter prediction may provide temporal compression.

Video encoder <b>20</b> and video decoder <b>30</b> may support various PU sizes. Assuming that the size of a particular CU is 2N×2N, video encoder <b>20</b> and video decoder <b>30</b> may support PU sizes of 2N×2N, N×N, 2N×N, or N×2N. Video encoder <b>20</b> and video decoder <b>30</b> may also support asymmetric partitioning for PU sizes of 2N×nU, 2N×nD, nL×2N, and nR×2N. In some examples, video encoder <b>20</b> may partition the video block of a CU among PUs of the CU along a boundary that does not meet the sides of the video block of the CU at right angles.

Motion estimation module <b>42</b> may perform a motion estimation operation with regard to each PU of the CU. When motion estimation module <b>42</b> performs a motion estimation operation with regard to a PU, motion estimation module <b>42</b> generates one or more motion vectors for the PU. For instance, slices may be I slices, P slices, or B slices. Motion estimation module <b>42</b> and motion compensation module <b>44</b> may perform different operations for a PU of a CU depending on whether the CU is in an I slice, a P slice, or a B slice. In an I slice, all CUs (and hence all PUs of the CUs) are intra predicted. Hence, if the PU is in an I slice, motion estimation module <b>42</b> and motion estimation module <b>44</b> do not perform inter prediction on the PU.

If the PU is in a P slice, the picture containing the PU is associated with a list of reference pictures referred to as “list 0.” Each of the reference pictures in list 0 contains samples that may be used for inter prediction of subsequent pictures in decoding order. When motion estimation module <b>42</b> performs the motion estimation operation with regard to a PU in a P slice, motion estimation module <b>42</b> searches the reference pictures in list 0 for a reference sample for the PU. The reference sample of the PU may be a set of pixel values that most closely corresponds to the pixels values of the PU. Motion estimation module <b>42</b> may use a variety of metrics to determine how closely a set of pixel values in a reference picture corresponds to the pixel values of a PU. For example, motion estimation module <b>42</b> may determine how closely a set of pixel values in a reference picture corresponds to the pixel values of a PU by sum of absolute difference (SAD), sum of square difference (SSD), or other difference metrics.

After identifying a reference sample of a PU of a CU in a P slice, motion estimation module <b>42</b> may generate a reference index that indicates the reference picture in list 0 containing the reference sample and a motion vector that indicates a spatial displacement between the PU and the reference sample. In various examples, motion estimation module <b>42</b> may generate motion vectors to varying degrees of precision. For example, motion estimation module <b>42</b> may generate motion vectors at one-quarter pixel precision, one-eighth pixel precision, or other fractional pixel precision. Motion estimation module <b>42</b> may output the reference index and motion vector to CABAC module <b>56</b> and motion compensation module <b>44</b>. Motion compensation module <b>44</b> may use the reference indexes and motion vectors of PUs of the CU to identify and retrieve the reference samples of the PUs. Motion compensation module <b>44</b> may then use pixel values of reference samples of PUs to generate the prediction data for the CU.

If the PU is in a B slice, the picture containing the PU may be associated with two lists of reference pictures, referred to as “list 0” and “list 1.” Each of the reference pictures in list 0 contains samples that may be used for inter prediction of subsequent pictures in decoding order. The reference pictures in list 1 may occur before the picture in decoding order but after the picture in presentation order. In some examples, a picture containing a B slice may be associated with a list combination that is a combination of list 0 and list 1.

Furthermore, if the CU is in a B slice, motion estimation module <b>42</b> may perform uni-directional prediction or bi-directional prediction for PUs of the CU. When motion estimation module <b>42</b> performs uni-directional prediction for a PU, motion estimation module <b>42</b> may search the reference pictures of list 0 or list 1 for a reference sample for the PU. Motion estimation module <b>42</b> may then generate a reference index that indicates the reference picture in list 0 or list 1 that contains the reference sample and a motion vector that indicates a spatial displacement between the PU and the reference sample. Motion estimation module <b>42</b> may output the reference indexes and motion vectors for PUs of a CU to CABAC module <b>56</b> and motion compensation module <b>44</b>. Motion compensation module <b>44</b> may use the reference indexes and motion vectors of PUs of the CU to identify and retrieve the reference samples of the PUs. Motion compensation module <b>44</b> may then use pixel values of reference samples of PUs to generate predicted video blocks for the PUs of the CU.

When motion estimation module <b>42</b> performs bi-directional prediction for a PU, motion estimation module <b>42</b> may search the reference pictures in list 0 for a reference sample for the PU and may also search the reference pictures in list 1 for another reference sample for the PU. Motion estimation module <b>42</b> may then generate reference indexes that indicate the reference samples and motion vectors that indicate spatial displacements between the reference samples and the PU. Motion estimation module <b>42</b> may output the reference indexes and motion vectors to CABAC module <b>56</b> and motion compensation module <b>44</b>. Motion compensation module <b>44</b> may use the reference indexes and motion vectors to identify and retrieve the reference samples of the PUs. Motion compensation module <b>44</b> may then interpolate pixel values of the predicted video blocks of the PUs of the CU from pixel values in the reference samples of the PUs of the CU.

As part of performing an encoding operation on a CU, intra prediction module <b>46</b> may perform intra prediction on PUs of the CU. In other words, intra prediction module <b>46</b> may generate prediction data for the PUs of the CU based on decoded pixel values in the same slice as the CU. Intra prediction may provide spatial compression.

To perform intra prediction on a PU, intra prediction module <b>46</b> may use multiple intra prediction modes to generate multiple sets of prediction data for the PU. When intra prediction module <b>46</b> uses an intra prediction mode to generate a set of prediction data for a PU, intra prediction module <b>46</b> may extend pixel values from neighboring PUs across the video block of the PU in a direction and/or gradient associated with the intra prediction mode. The neighboring PUs may be above, above and to the right, above and to the left, or to the left of the PU, assuming a left-to-right, top-to-bottom encoding order for PUs, CUs and treeblocks. Intra prediction module <b>46</b> may use various numbers of intra prediction modes, e.g., 33 directional intra prediction modes, depending on the size of the PU.

Intra prediction module <b>46</b> may select one of the sets of prediction data for the PU. In various examples, intra prediction module <b>46</b> may select the set of prediction data for the PU in various ways. For example, intra prediction module <b>46</b> may select the set of prediction data for the PU by based on a comparison of distortion and bit rates for the sets of prediction data and selecting the set of prediction data that has the lowest distortion rate.

Mode select unit <b>40</b> may select the prediction data for the PUs of a CU from among the sets of prediction data generated by motion compensation module <b>44</b> for the PUs of the CU or the sets of prediction data generated by intra prediction unit <b>46</b> for the PUs of the CU. In some examples, mode select unit <b>40</b> selects the prediction data for the PUs of the CU based on error (i.e., distortion) and bit rates of the sets of prediction data.

After mode select unit <b>40</b> selects the prediction data for the PUs of a CU, residual generation module <b>50</b> may generate residual data for the CU by subtracting the pixel values of the predicted video blocks of the selected prediction data of the PUs of the CU from the pixel values of original video block of the CU. The residual data of a CU may include 2D residual blocks that correspond to different pixel components of the video blocks in the CU. For example, the residual data may include a residual video block that corresponds to differences between luminance components of pixels in the predicted video blocks of the CU and luminance components of pixels in the original video block of the CU. In addition, the residual data of the CU may include residual video blocks that correspond to the differences between chrominance components of pixels in the predicted video blocks of the PUs of the CU and the chrominance components of the pixels of the original video block of the CU.

As described above, a CU may have one or more TUs. Each TU of a CU may correspond to a different video block within the residual data of the CU. The sizes of the video blocks of the TUs of a CU may or may not be based on the sizes of the video blocks of the PUs of the CU. In some examples, the residual data of a CU may be subdivided into smaller video blocks using a quadtree structure known as “residual quad tree” (RQT). The TUs may correspond to the leaf nodes of the RQT.

Transform module <b>52</b> may generate transform coefficient blocks for each TU of a CU by applying a transform to residual video blocks corresponding to the TU. Each of the transform coefficient blocks may be a 2D matrix of transform coefficients. In various examples, transform module <b>52</b> may apply various transforms to a residual video block corresponding to a TU. For example, transform module may apply a discrete cosine transform (DCT), a directional transform, or a conceptually similar transform. After transform module <b>52</b> generates a transform coefficient block for a TU, quantization module <b>54</b> may quantize the transform coefficients in the transform coefficient block.

CABAC module <b>56</b> may receive a transform coefficient block from quantization module <b>54</b>. When CABAC module <b>56</b> receives the transform coefficient block, CABAC module <b>56</b> may generate a significance map for the transform coefficient block and a block-based LSC indicator. The block-based LSC indicator may indicate the coordinates in the transform coefficient block of a last significant transform coefficient of the transform coefficient block. CABAC module <b>56</b> may also generate level information for the transform coefficient block. As explained above, the level information for the transform coefficient block may include a series of level-greater-than-one flags, a series of level-greater-than-two flags, a series of sign flags, and a series of level-remainder elements.

CABAC module <b>56</b> may perform CABAC encoding operations on the significance map, block-based LSC indicator, the level-greater-than-one flags, and the level-greater-than-two flags. In addition, CABAC module <b>56</b> may perform CABAC encoding operations on other syntax elements, such as motion vectors or motion vector difference information, and any of a variety of other syntax elements useful in decoding the video data at video decoder <b>30</b>.

Inverse quantization module <b>58</b> and inverse transform module <b>60</b> may apply inverse quantization and inverse transformation to the transform coefficient block, respectively, to reconstruct a residual video block from the transform coefficient block. Reconstruction module <b>62</b> may add the reconstructed residual video block to pixel values of one or more predicted video blocks generated by motion compensation module <b>44</b> or intra prediction module <b>46</b> to produce a reconstructed video block for storage in decoded picture buffer <b>64</b>. Motion estimation module <b>42</b> and motion compensation module <b>44</b> may use a reference picture that contains the reconstructed video block to perform intra or inter prediction on CUs of subsequent pictures.

<figref idref="DRAWINGS">FIG. 6</figref> is a block diagram that illustrates an example configuration of video decoder <b>30</b>. <figref idref="DRAWINGS">FIG. 6</figref> is provided for purposes of explanation and is not limiting on the techniques as broadly exemplified and described in this disclosure. For purposes of explanation, this disclosure describes video decoder <b>30</b> in the context of HEVC coding. However, the techniques of this disclosure may be applicable to other coding standards or methods.

In the example of <figref idref="DRAWINGS">FIG. 6</figref>, video decoder <b>30</b> includes a plurality of functional components. The functional components of video decoder <b>30</b> include a parsing module <b>70</b>, a motion compensation module <b>72</b>, an intra prediction module <b>74</b>, an inverse quantization module <b>76</b>, an inverse transform module <b>78</b>, a reconstruction module <b>80</b>, and a decoded picture buffer <b>82</b>. In some examples, video decoder <b>30</b> may perform a decoding pass generally reciprocal to the encoding pass described with respect to video encoder <b>20</b> of <figref idref="DRAWINGS">FIG. 5</figref>. In other examples, video decoder <b>30</b> may include more, fewer, or different functional components. For example, video decoder <b>30</b> may include a deblocking filter to filter the output of reconstruction module <b>80</b> to remove blockiness artifacts from reconstructed video.

Video decoder <b>30</b> may receive a bitstream that comprises encoded video data. The bitstream may include a plurality of syntax elements. When video decoder <b>30</b> receives the bitstream, parsing module <b>70</b> may perform a parsing operation on the bitstream. As a result of performing the parsing operation on the bitstream, parsing module <b>70</b> may extract the syntax elements from the bitstream. As part of performing the parsing operation, parsing module <b>70</b> may CABAC decode various CABAC encoded syntax elements in the bitstream. Motion compensation module <b>72</b>, intra prediction module <b>74</b>, inverse quantization module <b>76</b>, and inverse transform module <b>78</b> may perform a reconstruction operation that generates decoded video data based on the syntax elements extracted from the bitstream.

The bitstream may include data that represent a block-based LSC indicator for a transform coefficient block, a significance map for the transform coefficient block, and level information for the transform coefficient block. As part of performing the parsing operation, parsing module <b>70</b> may CABAC decode the block-based LSC indicator. Parsing module <b>70</b> may then convert the block-based LSC indicator into a scan-based LSC indicator. The scanning order may be signaled in the encoded bitstream or may be inferred by parsing module <b>70</b> from one or more syntax elements or parameters.

After converting the block-based LSC indicator into the scan-based LSC indicator, parsing module <b>70</b> may use the scan-based LSC indicator to parse the significance map from the bitstream. For example, parsing module <b>70</b> may determine, based on the scan-based LSC indicator, whether the significance map for the transform coefficient block includes a significance flag for a transform coefficient. Furthermore, in some examples, parsing module <b>70</b> may select a context model based on the scan-based LSC indicator. Parsing module <b>70</b> may use the selected context model during a CABAC decoding operation that decodes the significance map. Parsing module <b>70</b> may use the significance map to parse the level information of the transform coefficient block from the bitstream.

It may be desirable to convert the block-based LSC indicator into the scan-based LSC indicator in an efficient manner. In accordance with the techniques of this disclosure, parsing module <b>70</b> may perform various operations to convert the block-based LSC indicator into the scan-based LSC indicator. For example, parsing module <b>70</b> may perform a non-iterative algorithm that derives the scan-based LSC indicator from the coordinates specified by the block-based LSC indicator. <figref idref="DRAWINGS">FIGS. 9 and 10</figref>, described in detail below, are flowcharts of example non-iterative algorithms that may derive the scan-based LSC indicator from the coordinates specified by the block-based LSC indicator. In another example, parsing module <b>70</b> may store a data structure that maps coordinates to scan-based LSC indicators. In this example, parsing module <b>70</b> may access this data structure to generate the scan-based LSC indicator. <figref idref="DRAWINGS">FIG. 11</figref>, described in detail below, illustrates an example operation in which video decoder <b>30</b> converts the block-based LSC indicator to a scan-based LSC indicator at least in part by accessing a data structure that maps block-based LSC indicators to scan-based LSC indicators. In yet another example, parsing module <b>70</b> may generate the scan-based LSC indicator by performing a loop operation that scans through positions in a transform coefficient block according to a forward scanning order until a transform coefficient having the coordinates specified by the block-based LSC indicator is reached. <figref idref="DRAWINGS">FIG. 12</figref>, described in detail below, illustrates an example iterative operation in which video decoder <b>30</b> converts a block-based LSC indicator into a scan-based LSC indicator by performing such a loop operation.

In some examples, parsing module <b>70</b> may use different conversion operations based on different scanning orders. For instance, parsing module <b>70</b> may use the non-iterative algorithm mentioned above when the scanning order is a diagonal scanning order and parsing module <b>70</b> may use the mapping data structure mentioned above when the scanning order is a zigzag scanning order.

After parsing module <b>70</b> decodes transform coefficient block, inverse quantization module <b>76</b> may inverse quantize, i.e., de-quantize, the transform coefficient block. Inverse quantization module <b>76</b> may inverse quantize the transform coefficient block in a manner similar to the inverse quantization processes proposed for HEVC or defined by the H.264 decoding standard. Inverse quantization module <b>76</b> may use a quantization parameter QPY calculated by video encoder <b>20</b> for a CU of the transform coefficient block to determine a degree of quantization and, likewise, a degree of inverse quantization for inverse quantization module <b>76</b> to apply.

After inverse quantization module <b>76</b> inverse quantizes the transform coefficient block, inverse transform module <b>78</b> may generate a residual video block for the TU associated with the transform coefficient block. Inverse transform module <b>78</b> may generate the residual video block for the TU at least in part by applying an inverse transform to the transform coefficient block. For example, inverse transform module <b>78</b> may apply an inverse DCT, an inverse integer transform, an inverse Karhunen-Loeve transform (KLT), an inverse rotational transform, an inverse directional transform, or another inverse transform to the transform coefficient block. In some examples, inverse transform module <b>78</b> may determine an inverse transform to apply to the transform coefficient block based on signaling from video encoder <b>20</b>. In such examples, inverse transform module <b>78</b> may determine the inverse transform based on a signaled transform at the root node of a quadtree for a treeblock associated with the transform coefficient block. In other examples, inverse transform module <b>78</b> may infer the inverse transform from one or more coding characteristics, such as block size, coding mode, or the like. In some examples, inverse transform module <b>78</b> may apply a cascaded inverse transform.

Motion compensation module <b>72</b> may perform motion compensation to generate prediction data for a PU of a CU. In some examples, motion compensation module <b>72</b> may refine the prediction data for a PU by performing interpolation based on interpolation filters. Identifiers for interpolation filters to be used for motion compensation with sub-pixel precision may be included in the syntax elements. Motion compensation module <b>72</b> may use the same interpolation filters used by video encoder <b>20</b> during generation of the prediction data of the PU to calculate interpolated values for sub-integer pixels of a reference block. Motion compensation module <b>72</b> may determine the interpolation filters used by video encoder <b>20</b> according to received syntax information and use the interpolation filters to produce prediction data.

Motion compensation module <b>72</b> and intra prediction module <b>74</b>, in an HEVC example, may use some of the syntax information (e.g., provided by a quadtree) to determine sizes of treeblocks used to encode frame(s) of the encoded video sequence, split information that describes how video blocks of each CU of a frame of the encoded video sequence are split (and likewise, how sub-blocks are split), modes indicating how each PU is encoded (e.g., intra- or inter-prediction, and for intra-prediction an intra-prediction encoding mode), one or more reference frames (and/or reference lists containing identifiers for the reference frames) for each inter-predicted CU, and other information to decode the encoded video sequence.

Reconstruction module <b>80</b> combines the residual video blocks of a CU with the corresponding predicted video blocks of the PUs of the CU generated by motion compensation module <b>72</b> or intra prediction module <b>74</b> to form decoded video blocks. In some examples, video decoder <b>30</b> may apply a deblocking filter to filter the decoded video blocks in order to remove blockiness artifacts from the decoded video blocks. Decoded picture buffer <b>82</b> stores the decoded video blocks. Decoded picture buffer <b>82</b> may provide reference pictures for subsequent motion compensation and may also store pictures for presentation on a display device, such as display device <b>32</b> of <figref idref="DRAWINGS">FIG. 1</figref>.

<figref idref="DRAWINGS">FIG. 7</figref> is a flowchart that illustrates an example operation <b>100</b> performed by video encoder <b>20</b>. After CABAC module <b>56</b> starts operation <b>100</b>, video encoder <b>20</b> may identify a LSC of a transform coefficient block according to a scanning order (<b>102</b>). After video encoder <b>20</b> has identified the LSC of the transform coefficient block, video encoder <b>20</b> may generate a block-based LSC indicator that indicates the coordinates of the identified LSC of the transform coefficient block (<b>104</b>).

After generating the block-based LSC indicator, video encoder <b>20</b> may perform a CABAC encoding operation on the block-based LSC indicator (<b>106</b>). In various examples, video encoder <b>20</b> may perform the CABAC encoding operation on the block-based LSC indicator in various ways. For instance, in some examples, video encoder <b>20</b> may first convert each coordinate of the block-based LSC indicator into a binary code. In other words, video encoder <b>20</b> may “binarize” the coordinates of the block-based LSC indicator. After binarizing the coordinates, video encoder <b>20</b> may select a context model for encoding the binary code that represents the y-coordinate of the block-based LSC indicator. In some instances, video encoder <b>20</b> may select the context model for encoding the binary code that represents the y-coordinate based on the x-coordinate of the block-based LSC indicator. Video encoder <b>20</b> may use the selected context model when encoding one or more bins of the binary code that represents the y-coordinate. Similarly, video encoder <b>20</b> may select a context model for encoding the binary code that represents the x-coordinate of the block-based LSC indicator based on the y-coordinate of the block-based LSC indicator. Video encoder <b>20</b> may use the selected context model when encoding one or more bins of the binary code that represents the x-coordinate.

There may be a statistical relationship between the x-coordinate and the y-coordinate of the block-based LSC indicator. For instance, significant transform coefficients tend to cluster around the DC transform coefficients of transform coefficient blocks. Thus, if the x-coordinate is relatively close to the DC transform coefficient, the y-coordinate is also likely to be relatively close to the DC transform coefficient, and vice versa. By selecting the context model for the y-coordinate based on the x-coordinate, video encoder <b>20</b> may be able to exploit this statistical relationship in order to more accurately select the context model for the y-coordinate. Likewise, by selecting the context model for the x-coordinate based on the y-coordinate, video encoder <b>20</b> may be able to exploit this statistical relationship in order to more accurately select the context model for the x-coordinate.

In some examples, video encoder <b>20</b> may interleave the entropy encoding operations of symbols for the x and y coordinates. For example, video encoder <b>20</b> may first perform the entropy encoding operation for the first symbol of the x coordinate. Assuming that video encoder <b>20</b> represents the x coordinate as a unary number, the first symbol of the x coordinate is 0 if the x coordinate is 0 and 1 otherwise. After encoding the first symbol of the x coordinate, video encoder <b>20</b> may perform the entropy encoding operation on a first symbol of the y coordinate. Video encoder <b>20</b> may use different contexts to encode the first symbol of the y coordinate depending on the value of the first symbol of the x coordinate. Then, if the x coordinate is larger than 0, video encoder <b>20</b> may perform the entropy encoding operation on the second symbol of the x coordinate. Video encoder <b>20</b> may use different contexts to encode the second symbol of the x coordinate depending on the value of the first symbol of the y coordinate. Video encoder <b>20</b> may continue encoding symbols of the x and y coordinates until video encoder <b>20</b> has encoded each of the symbols of the x and y coordinates.

In some examples, video encoder <b>20</b> may map the transform coefficients from a transform coefficient block into another 2D transform coefficient block using a scanning order. For instance, the other 2D transform coefficient block may be eight positions wide. In this example, video encoder <b>20</b> may map the first eight transform coefficients of the transform coefficient block as determined by the scanning order into the first row of the other 2D transform coefficient block, the second eight transform coefficients of the transform coefficient block as determined by the scanning order into the second row of the other 2D transform coefficient block, and so on. In this example, video encoder <b>20</b> may then identify the last significant transform coefficient of the other 2D transform coefficient block according to the scanning order and generate a block-based LSC indicator that indicates the last significant transform coefficient of the other 2D block. In this example, a statistical relationship may exist between lower row numbers and the probability of a transform coefficient being significant. For instance, the probability of a transform coefficient being significant may be higher in low row numbers than in high row numbers. Video encoder <b>20</b> may exploit this statistical relationship when performing the entropy encoding operation on the block-based LSC indicator. For instance, video encoder <b>20</b> may first perform the entropy encoding operation on the y coordinate and then perform the entropy encoding operation on the x coordinate. When video encoder <b>20</b> performs the entropy encoding operation on the x coordinate, video encoder <b>20</b> may select a context model based on the y coordinate.

Furthermore, video encoder <b>20</b> may generate a significance map for the transform coefficient block (<b>108</b>). In some examples, video encoder <b>20</b> may generate the significance map and identify the LSC of the transform coefficient block in parallel.

In various examples, video encoder <b>20</b> may generate the significance map in various ways. For example, video encoder <b>20</b> may perform a coding pass that processes each of the transform coefficients according to a reverse scanning order. The reverse scanning order may be the inverse of the scanning order used to identify the LSC. In other examples, video encoder <b>20</b> may use the same scanning order to generate the significance map for the transform coefficient block as video encoder <b>20</b> uses to identify the LSC. For each transform coefficient processed during the coding pass, video encoder <b>20</b> may generate and CABAC encode a significance flag for the transform coefficient if the ordinal position of the transform coefficient according to the scanning order is before the ordinal position of the LSC according to the scanning order.

In another example, video encoder <b>20</b> may first generate a 2D block to serve as the significance map. In this example, video encoder <b>20</b> may scan through the transform coefficient block. As video encoder <b>20</b> scans through the transform coefficient block, video encoder <b>20</b> may indicate in the 2D significance map whether corresponding transform coefficients of the transform coefficient block are significant or not significant.

Furthermore, video encoder <b>20</b> may perform a CABAC encoding operation on the significance map (<b>110</b>). In some examples, video encoder <b>20</b> may interleave steps <b>108</b> and <b>110</b>. For instance, video encoder <b>20</b> may generate a significance flag for a first transform coefficient. Video encoder <b>20</b> may then perform a CABAC encoding operation on the significance flag for the first transform coefficient. After performing the CABAC encoding operation on the significance flag for the first transform coefficient, video encoder <b>20</b> may generate a significance flag for a second transform coefficient and then perform a CABAC encoding operation on the significance flag for the second transform coefficient, and so on.

Video encoder <b>20</b> may perform the CABAC encoding operation on the significance map in various ways. For example, video encoder <b>20</b> may select a context model based on the LSC of the transform coefficient block. There may be a statistical relationship between the position of the LSC and the value of the next significance flag (in reserve scanning order) of the significance map. For instance, if video encoder <b>20</b> uses a reverse scanning order to generate the significance map and the LSC of the transform coefficient block is relatively distant from the DC transform coefficient of the transform coefficient block, the probability of the next significance flag being 1 are relatively greater than if the LSC of the transform coefficient block is relatively close to the DC transform coefficient of the transform coefficient block. By selecting the context model based on the LSC of the transform coefficient block, video encoder <b>20</b> may be able to exploit this statistical relationship in order to more accurately select the context model for encoding the significance map. After selecting the context model for the significance map, video encoder <b>20</b> may use the context model to CABAC encode one or more significance flags of the significance map. During the CABAC encoding operation on the significance map, video encoder <b>20</b> may use one or more other context models to CABAC encode subsequent significance flags of the significance map.

In other examples, video encoder <b>20</b> may exploit the statistical relationship between the LSC and significance map in other ways. For example, video encoder <b>20</b> may use one set of contexts to CABAC encode the significance map if the ordinal position of the LSC is greater than a given threshold and another set of contexts to encode the significance map if the ordinal position of the LSC is not greater than the given threshold. Using different contexts in this manner may improve coding efficiency.

In another example, video encoder <b>20</b> may exploit the statistical relationship between the LSC and the significance map by grouping transform coefficients. For instance, in this example, video encoder <b>20</b> may group three transform coefficients together and encode the resulting group as a single transform coefficient. Thus, video encoder <b>20</b> may encode three transform coefficients at a time. If all three transform coefficients in a group are 0, then video encoder <b>20</b> may encode the three transform coefficients as 0. If not, video encoder <b>20</b> may generate a 1 flag and flags indicating which of the three corresponding transform coefficients are significant.

In some instances, all of the significant transform coefficients of a transform coefficient block may be located within a small region at the upper left corner of the transform coefficient block. For example, all of the significant transform coefficients of a transform coefficient block may be located within a 4×4 region at the upper left corner of the transform coefficient block. In such instances, it may require fewer bits to indicate the LSC of the transform coefficient block using a scan-based LSC indicator than a block-based LSC indicator. Hence, in some examples, video encoder <b>20</b> may generate a scan-based LSC indicator instead of a block-based LSC indicator when all of the significant transform coefficients are within the region. In such examples, video encoder <b>20</b> may generate a block-based LSC indicator if the transform coefficient block includes one or more significant transform coefficients outside the region. Furthermore, in some such examples, video encoder <b>20</b> may include a flag in the bitstream to indicate whether the LSC is indicated using a block-based LSC indicator or a scan-based LSC indicator.

In addition, video encoder <b>20</b> may generate level information for the transform coefficients in the transform coefficient block (<b>112</b>). As described above, the level information for the transform coefficients may include level-greater-than-one flags, level-greater-than-two flags, sign flags, and level-remainder elements.

Furthermore, video encoder <b>20</b> may perform CABAC encoding operations on at least some of the level information for the transform coefficients (<b>114</b>). In some examples, video encoder <b>20</b> may interleave steps <b>112</b> and <b>114</b>. For instance, video encoder <b>20</b> may perform separate coding passes for level-greater-than-one flags, level-greater-than-two flags, sign flags, and level-remainder elements. During the coding pass for the level-greater-than-one flags, video encoder <b>20</b> may generate and CABAC encode a level-greater-than-one flag for a first transform coefficient, generate and CABAC encode a level-greater-than-one flag for the next transform coefficient, and so on. Similarly, during the coding pass for the level-greater-than-two flags, video encoder <b>20</b> may generate and CABAC encode a level-greater-than-two flag for a first transform coefficient, generate and CABAC encode a level-greater-than-two flag for the next transform coefficient, and so on. During the coding pass for the sign flags, video encoder <b>20</b> may generate a sign flag for a first transform coefficient, generate a sign flag for a next transform coefficient, and so on. In this example, video encoder <b>20</b> does not CABAC encode the sign flags. During the coding pass for the level-remainder elements, video encoder <b>20</b> may generate a level-remainder element and identify a corresponding Golomb-Rice code for a first transform coefficient, generate a level-remainder element and identify a corresponding Golomb-Rice code for the next transform coefficient, and so on. In this example, video encoder <b>20</b> may not generate a level-greater-than-one flag, a level-greater-than-two flag, a sign flag, or a level-remainder element for a transform coefficient if the transform coefficient flag is not significant.

In some examples, when video encoder <b>20</b> binarizes the level information of a transform coefficient, the first bin of the binarized level information may indicate whether the transform coefficient is significant. Thus, in such examples, generating the significance map in step <b>108</b> may be part of generating the level information in step <b>112</b> and CABAC encoding the significance map in step <b>110</b> may be part of CABAC encoding the level information in step <b>114</b>.

<figref idref="DRAWINGS">FIG. 8</figref> is a flowchart that illustrates an example operation <b>130</b> to decode a transform coefficient block. After video decoder <b>30</b> starts operation <b>130</b>, video decoder <b>30</b> may receive a bitstream that comprises data representing a block-based LSC indicator for a transform coefficient block associated with a TU, a significance map for the transform coefficient block, and level information for the transform coefficient block (<b>132</b>). The bitstream may comprise other encoded video data.

After receiving the data that represents the block-based LSC indicator, video decoder <b>30</b> may perform a CABAC decoding operation to decode the encoded block-based LSC indicator (<b>134</b>). Thus, by performing the CABAC decoding operation, video decoder <b>30</b> may receive, from the bitstream of encoded video data, a block-based LSC indicator for a LSC of a block of transform coefficients.

After video decoder <b>30</b> performs the CABAC decoding operation to decode the block-based LSC indicator, video decoder <b>30</b> may select a conversion operation (<b>135</b>). In some examples, video decoder <b>30</b> may select the conversion operation based on the scanning order. Video decoder <b>30</b> may then use the selected conversion operation to convert the block-based LSC indicator into a scan-based LSC indicator (<b>136</b>). In various examples, video decoder <b>30</b> may convert the block-based LSC indicator into the scan-based LSC indicator in various ways. For example, video decoder <b>30</b> may use the example operations shown in <figref idref="DRAWINGS">FIGS. 9-12</figref> to convert the block-based LSC indicator into the scan-based LSC indicator. In other examples, video decoder <b>30</b> may perform a combination of one or more of the example operations of <figref idref="DRAWINGS">FIGS. 9-12</figref> to convert the block-based LSC indicator into the scan-based LSC indicator. Furthermore, in yet other examples, video decoder <b>30</b> does not select a conversion operation after decoding a block-based LSC indicator. Rather, in some such examples, video decoder <b>30</b> may only be configured to perform one specific conversion operation.

Subsequently, video decoder <b>30</b> may use the scan-based LSC indicator to decode the significance map for the transform coefficient block (<b>138</b>). Video decoder <b>30</b> may use the scan-based LSC indicator to decode the significance map in various ways.

For example, video encoder <b>20</b> may not encode significance flags for transform coefficients occurring after the LSC in coding order. Consequently, the number of significance flags in the significance map can vary among transform coefficient blocks. Because the number of significance flags may vary, video decoder <b>30</b> may not be able to determine based on the size of the transform coefficient block how many significance flags are in the significance map of the transform coefficient block. Thus, when video decoder <b>30</b> decodes the significance map, video decoder <b>30</b> may need to be able to determine whether video decoder <b>30</b> has parsed all of the significance flags of the significance map from the bitstream. Accordingly, video decoder <b>30</b> may continue parsing significance flags from the bitstream until the number of significance flags parsed from the bitstream is equal to the ordinal position of the LSC (i.e., position indicated by the scan-based LSC indicator). In this way, video decoder <b>30</b> may use the scan-based LSC indicator to determine whether the significance map includes significance flags for the transform coefficients of the transform coefficient block.

In another example, the scan-based LSC indicator may indicate the number of bins that indicate significant transform coefficients to be decoded. In addition, as described above, there may be a statistical relationship between the number of transform coefficients occurring prior the LSC in scanning order and the probability of a bin of the significance map being a 1 or 0. The scan-based LSC indicator indicates the number of transform coefficients occurring prior to the LSC in the scanning order. Accordingly, video decoder <b>30</b> may select, based on the scan-based LSC indicator, a context model from among a plurality of available context models. Video decoder <b>30</b> may then use the selected context model to decode one or more bins of the significance map. During the CABAC decoding operation for the significance map, video decoder <b>30</b> may switch to one or more other context models.

In some examples, a transform coefficient block may include a plurality of sub-blocks. Video decoder <b>30</b> may identify, based on the scan-based LSC indicator, a last significant sub-block from among the plurality of sub-blocks, the last significant sub-block containing the LSC. Furthermore, video decoder <b>30</b> may perform a first coding pass that processes the last significant sub-block and ones of the sub-blocks that occur before the last significant sub-block according to a first reverse scanning order that starts with the last significant sub-block. For each of the sub-blocks processed during the first coding pass, video decoder <b>30</b> may perform a second coding pass that processes transform coefficients in the sub-block according to a second reverse scanning order. The second reverse scanning order may be the same or different than the first reverse scanning order. For each transform coefficient processed during the second coding pass, video decoder <b>30</b> may determine, based on the scan-based LSC indicator, whether the significance map includes a significance flag for the transform coefficient.

After video decoder <b>30</b> decodes the significance map for the transform coefficient block, video decoder <b>30</b> may perform a decoding operation on the level information of the transform coefficient block (<b>140</b>). For example, the level information of the transform coefficient block may include level-greater-than-one flags, level-greater-than-two flags, sign flags, and level-remainder elements. The level-greater-than-one flags and the level-greater-than-two flags may be CABAC encoded and the level-remainder elements may be encoded as Golomb-Rice codes. In this example, video decoder <b>30</b> may perform CABAC decoding operations to decode the level-greater-than-one flags and the level-greater-than-two flags and may convert the Golomb-Rice codes back into the level-remainder elements.

In addition, video decoder <b>30</b> may use the significance map, the scan-based LSC indicator, and the transform coefficient level information of the transform coefficient block to reconstruct the transform coefficient block from the level information for the transform coefficient block (<b>142</b>). In some examples, video decoder <b>30</b> may interleave steps <b>140</b> and <b>142</b>. For example, video decoder <b>30</b> may store the transform coefficients in a two-dimensional array. In this example, video decoder <b>30</b> may add or adjust transform coefficients in the array as video decoder <b>30</b> decodes the level information in step <b>140</b>.

As described above, the level information for the transform coefficient block may comprise a series of level-greater-than-one flags, a series of level-greater-than-two flags, a series of a sign flags, and a series of level-remainder elements. In some examples, the series of level-greater-than-one flags, the series of level-greater-than-two flags, the sign flags, and the level-remainder elements do not include entries regarding the non-significant transform coefficients within the transform coefficient block. Hence, the series of level-greater-than-one flags, the series of level-greater-than-two flags, the sign flags, and the level-remainder elements may not include information that indicate the positions of the transform coefficient block that correspond to the level-greater-than-one flags, the level-greater-than-two flags, the sign flags, and the level-remainder elements. Accordingly, video decoder <b>30</b> may use the significance map to determine the positions within the transform coefficient block that correspond to the level-greater-than-one flags, the level-greater-than-two flags, the sign flags, and the level-remainder elements. In this instance, video decoder <b>30</b> may then use the level-greater-than-one flags, level-greater-than-two flags, sign flags, and level-remainder elements to reconstruct the transform coefficient block.

As described above, in some examples, the first bin of the binarized level information of a transform coefficient may indicate whether the transform coefficient is significant. Thus, the significance map may be integrated into the binarized level information of the transform coefficients. In such examples, performing the entropy decoding operation on the significance map in step <b>138</b> may be part of performing the CABAC decoding operation on the level information in step <b>140</b>.

<figref idref="DRAWINGS">FIG. 9</figref> is a flowchart that illustrates an example non-iterative operation <b>150</b> to convert a block-based LSC indicator for a transform coefficient block into a scan-based LSC indicator for the transform coefficient block. In the example of <figref idref="DRAWINGS">FIG. 9</figref>, operation <b>150</b> assumes that the scanning order is the zigzag scanning order. After video decoder <b>30</b> starts operation <b>150</b>, video decoder <b>30</b> may determine the value of a diagonal number variable (<b>152</b>). Video decoder <b>30</b> may determine the value of the diagonal number variable by adding the y-coordinate of the block-based LSC indicator and the x-coordinate of the block-based LSC indicator.

Next, video decoder <b>30</b> may determine whether the diagonal number variable is greater than a block width of the transform coefficient block (<b>154</b>). If the diagonal number is greater than the block width of the transform coefficient block (“YES” of <b>154</b>), video decoder <b>30</b> may calculate an initial value for the scan-based LSC indicator (<b>156</b>). Video decoder <b>30</b> may calculate the initial value for the scan-based LSC indicator as follows: ScanPositionLast=DiagNum*(DiagNum+1))&gt;&gt;1, where “ScanPositionLast” is the scan-based LSC indicator, “DiagNum” represents the diagonal number variable, and “&gt;&gt;” represents the right-shift operation.

Next, video decoder <b>30</b> may determine whether the diagonal number variable is an odd number (<b>158</b>). In some examples, video decoder <b>30</b> may determine whether the diagonal number variable is odd as follows: (DiagNum % 2)==1. If the diagonal number variable is an odd number (“YES” of <b>158</b>), video decoder <b>30</b> may recalculate the scan-based LSC indicator based on the y-coordinate of the block-based LSC indicator (<b>160</b>). For instance, video decoder <b>30</b> may recalculate the scan-based LSC indicator by adding the y-coordinate of the block-based LSC indicator to the initial value of the scan-based LSC indicator. Otherwise, if the diagonal number variable is not an odd number (“NO” of <b>158</b>), video decoder <b>30</b> may recalculate the scan-based LSC indicator based on the x-coordinate of the block-based LSC indicator (<b>162</b>). For instance, video decoder <b>30</b> may recalculate the scan-based LSC indicator by adding the x-coordinate of the block-based LSC indicator to the initial value of the scan-based LSC indicator.

If the diagonal number is not greater than the block width (“NO” of <b>154</b>), video decoder <b>30</b> may calculate the value of a temporary variable (<b>164</b>). Video decoder <b>30</b> may calculate the value of the temporary variable as follows: (BlockWidth−1)&lt;&lt;1)−DiagNum, where “BlockWidth” indicates the width of the transform coefficient block and “&lt;&lt;” represents the left shift operation. After calculating the temporary value, video decoder <b>30</b> may calculate an initial value of the scan-based LSC indicator (<b>166</b>). Video decoder <b>30</b> may calculate the initial value of the scan-based LSC indicator as follows: MaxNumCoeffM1−((T*(T+1))&gt;&gt;1), where “MaxNumCoeffM1” is the maximum number of transform coefficients in the transform coefficient block and “T” is the temporary variable.

Video decoder <b>30</b> may then determine whether the temporary variable is odd (<b>168</b>). If the temporary variable is odd (“YES” of <b>168</b>), video decoder <b>30</b> may recalculate the scan-based LSC indicator based on the y-coordinate of the block-based LSC indicator (<b>170</b>). For instance, video decoder <b>30</b> may recalculate the scan-based LSC indicator as follows: ScanPositionLast=ScanPositionLast−BlockWidth+1+PositionLastY, where “ScanPositionLast” is the scan-based LSC indicator, “BlockWidth” is the width of the transform coefficient block, and “PositionLastY” is the y-coordinate of the block-based LSC indicator.

Otherwise, if the temporary variable is not odd (“NO” of <b>168</b>), video decoder <b>30</b> may recalculate the scan-based LSC indicator based on the x-coordinate of the block-based LSC indicator (<b>172</b>). For instance, video decoder <b>30</b> may recalculate the scan-based LSC indicator as follows: ScanPositionLast=ScanPositionLast−BlockWidth+1+PositionLastX, where “ScanPositionLast” is the scan-based LSC indicator, “BlockWidth” is the width of the transform coefficient block, and “PositionLastX” is the x-coordinate of the block-based LSC indicator.

The following pseudo-code describes a non-iterative algorithm in accordance with the example of <figref idref="DRAWINGS">FIG. 9</figref> that derives the scan-based LSC indicator from the coordinates specified by the block-based LSC indicator.

<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="196pt" align="left" /><thead><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>1.</entry><entry>DiagNum = PositionLastY + PositionLastX</entry></row><row><entry>2.</entry><entry>If ( DiagNum &lt; BlockWidth)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="168pt" align="left" /><tbody valign="top"><row><entry /><entry>a.</entry><entry>ScanPositionLast = ( DiagNum * (DiagNum + 1) ) &gt;&gt; 1</entry></row><row><entry /><entry>b.</entry><entry>If ((DiagNum % 2) == 1 )</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="70pt" align="left" /><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="126pt" align="left" /><tbody valign="top"><row><entry /><entry>i.</entry><entry>ScanPositionLast = ScanPositionLast +</entry></row><row><entry /><entry /><entry>PositionLastY</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="168pt" align="left" /><tbody valign="top"><row><entry /><entry>c.</entry><entry>Else</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="70pt" align="left" /><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="126pt" align="left" /><tbody valign="top"><row><entry /><entry>i.</entry><entry>ScanPositionLast = ScanPositionLast +</entry></row><row><entry /><entry /><entry>PositionLastX</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="196pt" align="left" /><tbody valign="top"><row><entry>3.</entry><entry>Else</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="168pt" align="left" /><tbody valign="top"><row><entry /><entry>a.</entry><entry>T = ( (BlockWidth−1) &lt;&lt; 1 ) − DiagNum</entry></row><row><entry /><entry>b.</entry><entry>ScanPositionLast = MaxNumCoeffM1 − (( T * (T +</entry></row><row><entry /><entry /><entry>1) ) &gt;&gt; 1)</entry></row><row><entry /><entry>c.</entry><entry>If ((T % 2) == 1 )</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="70pt" align="left" /><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="126pt" align="left" /><tbody valign="top"><row><entry /><entry>i.</entry><entry>ScanPositionLast = ScanPositionLast −</entry></row><row><entry /><entry /><entry>BlockWidth + 1 + PositionLastY</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="168pt" align="left" /><tbody valign="top"><row><entry /><entry>d.</entry><entry>Else</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="70pt" align="left" /><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="126pt" align="left" /><tbody valign="top"><row><entry /><entry>i.</entry><entry>ScanPositionLast = ScanPositionLast −</entry></row><row><entry /><entry /><entry>BlockWidth + 1 + PositionLastX</entry></row><row><entry /><entry namest="offset" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> In this pseudo-code, “PositionLastY” and “PositionLastX” are the x and y coordinates of the last transform coefficient (assuming the DC component is at coordinates (0, 0)), and “BlockWidth” is the width of the block, &lt;&lt; is the left-shift operation, &gt;&gt; is the right-shift operation, % is the modulus operation, and “MaxNumCoeffM1” is the maximum number of transform coefficients that the transform coefficient block may have (i.e., BlockWidth*BlockHeight−1).

The following pseudo-code is similar to the pseudo-code above, but converts a block-based LSC indicator into a scan-based LSC indicator when a top-right to bottom-left diagonal scan is used:

<tables id="TABLE-US-00002" num="00002"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="196pt" align="left" /><thead><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>1.</entry><entry>DiagNum = PositionLastY + PositionLastX</entry></row><row><entry>2.</entry><entry>If ( DiagNum &lt; BlockWidth)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="168pt" align="left" /><tbody valign="top"><row><entry /><entry>a.</entry><entry>ScanPositionLast = ( DiagNum * (DiagNum + 1) ) &gt;&gt; 1</entry></row><row><entry /><entry>b.</entry><entry>ScanPositionLast = ScanPositionLast + PositionLastX</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="196pt" align="left" /><tbody valign="top"><row><entry>3.</entry><entry>Else</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="168pt" align="left" /><tbody valign="top"><row><entry /><entry>a.</entry><entry>T = ( (BlockWidth−1) &lt;&lt; 1 ) − DiagNum</entry></row><row><entry /><entry>b.</entry><entry>ScanPositionLast = MaxNumCoeffM1 − (( T * (T +</entry></row><row><entry /><entry /><entry>1) ) &gt;&gt; 1)</entry></row><row><entry /><entry>c.</entry><entry>If ((T % 2) == 1 )</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="70pt" align="left" /><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="126pt" align="left" /><tbody valign="top"><row><entry /><entry>i.</entry><entry>ScanPositionLast = ScanPositionLast −</entry></row><row><entry /><entry /><entry>BlockWidth + 1 + PositionLastY</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="168pt" align="left" /><tbody valign="top"><row><entry /><entry>d.</entry><entry>Else</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="70pt" align="left" /><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="126pt" align="left" /><tbody valign="top"><row><entry /><entry>i.</entry><entry>ScanPositionLast = ScanPositionLast −</entry></row><row><entry /><entry /><entry>BlockWidth + 1 + PositionLastX</entry></row><row><entry /><entry namest="offset" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

The following pseudo-code is similar to the pseudo-code above, but converts a block-based LSC indicator into a scan-based LSC indicator when a bottom-left to top-right diagonal scan is used:

<tables id="TABLE-US-00003" num="00003"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="196pt" align="left" /><thead><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>1.</entry><entry>DiagNum = PositionLastY + PositionLastX</entry></row><row><entry>2.</entry><entry>If ( DiagNum &lt; BlockWidth)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="168pt" align="left" /><tbody valign="top"><row><entry /><entry>a.</entry><entry>ScanPositionLast = ( DiagNum * (DiagNum + 1) ) &gt;&gt; 1</entry></row><row><entry /><entry>b.</entry><entry>ScanPositionLast = ScanPositionLast + PositionLastY</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="196pt" align="left" /><tbody valign="top"><row><entry>3.</entry><entry>Else</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="168pt" align="left" /><tbody valign="top"><row><entry /><entry>a.</entry><entry>T = ( (BlockWidth−1) &lt;&lt; 1 ) − DiagNum</entry></row><row><entry /><entry>b.</entry><entry>ScanPositionLast = MaxNumCoeffM1 − (( T * (T +</entry></row><row><entry /><entry /><entry>1) ) &gt;&gt; 1)</entry></row><row><entry /><entry>c.</entry><entry>If ((T % 2) == 1 )</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="70pt" align="left" /><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="126pt" align="left" /><tbody valign="top"><row><entry /><entry>i.</entry><entry>ScanPositionLast = ScanPositionLast −</entry></row><row><entry /><entry /><entry>BlockWidth + 1 + PositionLastY</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="168pt" align="left" /><tbody valign="top"><row><entry /><entry>d.</entry><entry>Else</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="70pt" align="left" /><colspec colname="1" colwidth="21pt" align="left" /><colspec colname="2" colwidth="126pt" align="left" /><tbody valign="top"><row><entry /><entry>i.</entry><entry>ScanPositionLast = ScanPositionLast −</entry></row><row><entry /><entry /><entry>BlockWidth + 1 + PositionLastX</entry></row><row><entry /><entry namest="offset" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

<figref idref="DRAWINGS">FIG. 10</figref> is a flowchart that illustrates another example non-iterative operation <b>200</b> to convert a block-based LSC indicator into a scan-based LSC indicator. In the example of <figref idref="DRAWINGS">FIG. 10</figref>, video decoder <b>30</b> may store a transform coefficient block in memory in a 1-D array. In this 1-D array, transform coefficients in a top row of the transform coefficient block are followed by transform coefficients in a next lower row, which are followed by transform coefficients associated with a next lower row, and so on. After video decoder <b>30</b> starts operation <b>200</b>, video decoder <b>30</b> may set the scan-based LSC indicator to a value that indicates a position in the 1-D array that is associated with the coordinates indicated by the block-based LSC indicator (<b>202</b>). Video decoder <b>30</b> may determine the position in the 1-D array by multiplying the y-coordinate specified by the block-based LSC indicator by the width of the transform coefficient block and then adding the x-coordinate specified by the block-based LSC indicator. If the scanning order is the horizontal scanning order, video decoder <b>30</b> may not need to perform any further processing to obtain the scan-based LSC indicator.

Next, video decoder <b>30</b> may determine whether the scanning order is the zigzag scanning order (<b>204</b>). In response to determining that the scanning order is the zigzag scanning order (“YES” of <b>204</b>), video decoder <b>30</b> may calculate a diagonal number (“uiD”) as a sum of the y-coordinate of the block-based LSC indicator (“uiPosLastY”) and the x-coordinate of the block-based LSC indicator (“uiPosLastX”) (<b>206</b>). Video decoder <b>30</b> may then determine whether the diagonal number is less than the width of the transform coefficient block (“uiWidth”) (<b>208</b>). In response to determining that the diagonal number is less than the width of the transform coefficient block (“YES” of <b>208</b>), video decoder <b>30</b> may calculate a value for the scan-based LSC indicator (“uiScanPosLast”) based on the diagonal number (<b>210</b>). For example, video decoder <b>30</b> may calculate the initial value for the scan-based LSC indicator as follows: uiScanPosLast=uiD*(uiD+1))&gt;&gt;1, where “uiScanPosLast” is the scan-based LSC indicator and “uiD” is the diagonal number. In this example, if the diagonal number is an even number, video decoder <b>30</b> may then calculate the final value for the scan-based LSC indicator by adding the y-coordinate of the block-based LSC indicator to the initial value of the scan-based LSC indicator. If the diagonal number is an odd number, video decoder <b>30</b> may calculate the final value for the scan-based LSC indicator by adding the x-coordinate of the block-based LSC indicator to the initial value of the scan-based LSC indicator.

Otherwise, in response to determining that the position identifier is not less than the width of the transform coefficient block (“NO” of <b>208</b>), video decoder <b>30</b> may calculate a temporary value (“uiDI”) (<b>212</b>). Video decoder <b>30</b> may calculate the temporary value as follows: uiDI=((uiWidth−1)&lt;&lt;1)−uiD, where “uiDI” is the temporary value, “uiWidth” is the width of the transform coefficient block, and “uiD” is the diagonal number. After calculating the temporary value, video decoder <b>30</b> may calculate the scan-based LSC indicator based on the temporary value (<b>214</b>). Video decoder <b>30</b> may calculate an initial value of the scan-based LSC indicator as follows: uiScanPosLast=uiMaxNumCoeffM1−(uiDI*(uiDI+1)&gt;&gt;1), where “uiScanPosLast” is the scan-based LSC indicator, “uiMaxNumCoeffM1” is the maximum number of transform coefficients that the transform coefficient block may have, and “uiDI” is the temporary value. If the temporary value is even, video decoder <b>30</b> may calculate the final value of the scan-based LSC indicator by subtracting (uiWidth−1−uiPosLastY) from the initial value of the scan-based LSC indicator, where “uiWidth” is the width of the transform coefficient block and “uiPosLastY” is the y-coordinate of the block-based LSC indicator. If the temporary value is odd, video decoder <b>30</b> may calculate the final value of the scan-based LSC indicator by subtracting (uiWidth−1−uiPosLastX) from the initial value of the scan-based LSC indicator, where “uiWidth” is the width of the transform coefficient block and “uiPosLastX” is the x-coordinate of the block-based LSC indicator.

In response to determining that the scanning order is not the zigzag scanning order (“NO” of <b>204</b>), video decoder <b>30</b> may determine whether the scanning order is the vertical scanning order (<b>216</b>). In response to determining that the scanning order is the vertical scanning order (“YES” of <b>216</b>), video decoder <b>30</b> may calculate the scan-based LSC indicator from the block-based LSC indicator and the size of the transform coefficient block (<b>218</b>). For instance, video decoder <b>30</b> may calculate the scan-based LSC indicator as: uiScanPosLast=uiPosLastY+(uiPosLastX&lt;&lt;uiLog 2BlockSize), where uiScanPosLast is the scan-based LSC indicator, uiPosLastY is the y-coordinate of the block-based LSC indicator, uiPosLastX is the x-coordinate of the block-based LSC indicator, and “uiLog 2BlockSize” is the log-base 2 of the size of the transform coefficient block.

The following code describes an example algorithm for converting the block-based LSC indicator into a scan-based LSC indicator when the scanning order is the horizontal, vertical, or zigzag scanning order in accordance with the example of <figref idref="DRAWINGS">FIG. 10</figref>. The storage in memory of the transform coefficient block is assumed to be row-wise.

<tables id="TABLE-US-00004" num="00004"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="left" /><thead><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>/* Code for Zig-zag scan */</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="4"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="84pt" align="left" /><colspec colname="2" colwidth="56pt" align="left" /><colspec colname="3" colwidth="63pt" align="left" /><tbody valign="top"><row><entry /><entry>UInt uiScanPosLast =</entry><entry> uiBlkPosLast;</entry><entry> // −&gt; Horizontal</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="left" /><tbody valign="top"><row><entry>scan</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="140pt" align="left" /><colspec colname="2" colwidth="63pt" align="left" /><tbody valign="top"><row><entry /><entry>if( uiScanIdx == SCAN_ZIGZAG )</entry><entry> // −&gt; Zig-zag</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="154pt" align="left" /><colspec colname="1" colwidth="63pt" align="left" /><tbody valign="top"><row><entry /><entry> scan</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>{</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="70pt" align="left" /><colspec colname="2" colwidth="119pt" align="left" /><tbody valign="top"><row><entry /><entry>UInt uiD =</entry><entry>uiPosLastY + uiPosLastX;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>if( uiD &lt; uiWidth )</entry></row><row><entry /><entry>{</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="56pt" align="left" /><colspec colname="2" colwidth="119pt" align="left" /><tbody valign="top"><row><entry /><entry>uiScanPosLast =</entry><entry>( uiD * ( uiD + 1 ) ) &gt;&gt; 1;</entry></row><row><entry /><entry>uiScanPosLast +=</entry><entry>uiD % 2 ? uiPosLastY : uiPosLastX;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row><row><entry /><entry>else</entry></row><row><entry /><entry>{</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="56pt" align="left" /><colspec colname="2" colwidth="119pt" align="left" /><tbody valign="top"><row><entry /><entry>UInt uiDI =</entry><entry>( (uiWidth−1) &lt;&lt; 1 ) − uiD;</entry></row><row><entry /><entry>uiScanPosLast =</entry><entry>uiMaxNumCoeffM1 − ( uiDI * ( uiDI +</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="98pt" align="left" /><colspec colname="1" colwidth="119pt" align="left" /><tbody valign="top"><row><entry /><entry>1 ) &gt;&gt; 1 );</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="56pt" align="left" /><colspec colname="2" colwidth="119pt" align="left" /><tbody valign="top"><row><entry /><entry>uiScanPosLast −=</entry><entry>uiDI % 2 ? uiWidth − 1 − uiPosLastY :</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="left" /><tbody valign="top"><row><entry>uiWidth − 1 − uiPosLastX;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="140pt" align="left" /><colspec colname="2" colwidth="63pt" align="left" /><tbody valign="top"><row><entry /><entry>else if( uiScanIdx == SCAN_VER )</entry><entry>// −&gt; Vertical scan</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>{</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>uiScanPosLast = uiPosLastY +</entry></row><row><entry /><entry>(uiPosLastX&lt;&lt;uiLog2BlockSize);</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

Video decoder <b>30</b> may perform a similar operation with regard to the diagonal scanning order (as opposed to the zig-zag scan discussed above). In such an operation, video decoder <b>30</b> may calculate the scan-based LSC indicator in step <b>214</b> as uiScanPosLast=uiMaxNumCoeffM1−(uiDI*(uiDI+1)&gt;&gt;1)−uiWidth+1+uiPosLastX, where “uiScanPosLast” is the scan-based LSC indicator, “uiMaxNumCoeffM1” is the maximum number of transform coefficients in the transform coefficient block, “uiDI” is the temporary value, “uiWidth” is the width of the transform coefficient block, and “uiPosLastX” is the x-coordinate of the block-based LSC indicator. The following code describes an example algorithm for converting the block-based LSC indicator into a scan-based LSC indicator when the scanning order is the diagonal scanning order.

<tables id="TABLE-US-00005" num="00005"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="left" /><thead><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>/* Code for diagonal scan */</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="4"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="84pt" align="left" /><colspec colname="2" colwidth="56pt" align="left" /><colspec colname="3" colwidth="63pt" align="left" /><tbody valign="top"><row><entry /><entry>UInt uiScanPosLast =</entry><entry> uiBlkPosLast;</entry><entry> // −&gt; Horizontal</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="154pt" align="left" /><colspec colname="1" colwidth="63pt" align="left" /><tbody valign="top"><row><entry /><entry> scan</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="140pt" align="left" /><colspec colname="2" colwidth="63pt" align="left" /><tbody valign="top"><row><entry /><entry>if( uiScanIdx == SCAN_DIAGONAL )</entry><entry>// −&gt; Diagonal scan</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>{</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="70pt" align="left" /><colspec colname="2" colwidth="119pt" align="left" /><tbody valign="top"><row><entry /><entry>UInt uiD =</entry><entry>uiPosLastY + uiPosLastX;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>if( uiD &lt; uiWidth )</entry></row><row><entry /><entry>{</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="56pt" align="left" /><colspec colname="2" colwidth="119pt" align="left" /><tbody valign="top"><row><entry /><entry>uiScanPosLast =</entry><entry>( uiD * ( uiD + 1 ) ) &gt;&gt; 1;</entry></row><row><entry /><entry>uiScanPosLast +=</entry><entry>uiD % 2 ? uiPosLastY : uiPosLastX;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row><row><entry /><entry>else</entry></row><row><entry /><entry>{</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="56pt" align="left" /><colspec colname="2" colwidth="119pt" align="left" /><tbody valign="top"><row><entry /><entry>UInt uiDI =</entry><entry>( (uiWidth−1) &lt;&lt; 1 ) − uiD;</entry></row><row><entry /><entry>uiScanPosLast =</entry><entry>uiMaxNumCoeffM1 − ( uiDI * ( uiDI +</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="left" /><tbody valign="top"><row><entry>1 ) &gt;&gt; 1 ) − uiWidth + 1 + uiPosLastX;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="140pt" align="left" /><colspec colname="2" colwidth="63pt" align="left" /><tbody valign="top"><row><entry /><entry>else if( uiScanIdx == SCAN_VER )</entry><entry> // −&gt; Vertical scan</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>{</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>uiScanPosLast = uiPosLastY +</entry></row><row><entry /><entry>(uiPosLastX&lt;&lt;uiLog2BlockSize);</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

<figref idref="DRAWINGS">FIG. 11</figref> is a flowchart that illustrates another example operation <b>250</b> to convert a block-based LSC indicator into a scan-based LSC indicator. As illustrated in the example of <figref idref="DRAWINGS">FIG. 11</figref>, video decoder <b>30</b> may store a lookup table (<b>252</b>). The lookup table maps block-based LSC indicators to scan-based LSC indicators according to the scanning order. For example, if the scanning order is the zigzag scanning order, the lookup table may include an entry that maps the coordinates (1, 1) to the scan-based LSC indicator “6.” In some examples, video decoder <b>30</b> may store different lookup tables for different scanning orders and different transform coefficient block sizes.

After video decoder <b>30</b> stores the lookup table, video decoder <b>30</b> may receive the block-based LSC indicator (<b>254</b>). After receiving the block-based LSC indicator, video decoder <b>30</b> may access the lookup table to retrieve the scan-based LSC indicator that corresponds to the block-based LSC indicator (<b>256</b>). In some examples, video decoder <b>30</b> generates a single value based on the x and y coordinates of the block-based LSC indicator. For instance, video decoder <b>30</b> may generate the single value by multiplying the y-coordinate by a width of the transform coefficient block and then adding the x-coordinate. In such examples, video decoder <b>30</b> may use the single value as an index to retrieve the scan-based LSC indicator from the lookup table.

Video decoder <b>30</b> may use additional operations to convert block-based LSC indicators to scan-based LSC indicators. For example, video decoder <b>30</b> may use the following pseudo-code to convert a block-based LSC indicator to a scan-based LSC indicator when transform coefficients are scanned in a sub-block diagonal scanning order. In this sub-block diagonal scanning order, video decoder <b>30</b> processes sub-blocks in a top-right to bottom-left diagonal order and scans transform coefficients within each of the sub-blocks in a top-right to bottom-left diagonal order.

<tables id="TABLE-US-00006" num="00006"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="70pt" align="left" /><colspec colname="2" colwidth="133pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>uiScanPosLast =</entry><entry>0;</entry></row><row><entry /><entry>UInt sWidth =</entry><entry>uiWidth &gt;&gt; 2;</entry></row><row><entry /><entry>UInt sX =</entry><entry>uiPosLastX &gt;&gt; 2;</entry></row><row><entry /><entry>UInt sY =</entry><entry>uiPosLastY &gt;&gt; 2;</entry></row><row><entry /><entry>UInt uiDs =</entry><entry>sX + sY;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>if( uiDs &lt; sWidth )</entry></row><row><entry /><entry>{</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="56pt" align="left" /><colspec colname="2" colwidth="133pt" align="left" /><tbody valign="top"><row><entry /><entry>uiScanPosLast +=</entry><entry> sX + (( uiDs * ( uiDs + 1 ) ) &gt;&gt; 1);</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row><row><entry /><entry>else</entry></row><row><entry /><entry>{</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="56pt" align="left" /><colspec colname="2" colwidth="133pt" align="left" /><tbody valign="top"><row><entry /><entry>UInt uiDI =</entry><entry> ( (sWidth−1) &lt;&lt; 1 ) − uiDs;</entry></row><row><entry /><entry>uiScanPosLast +=</entry><entry> sWidth*(sWidth−1) − ( uiDI * ( uiDI + 1</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="left" /><tbody valign="top"><row><entry>) &gt;&gt; 1 ) + sX;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="70pt" align="left" /><colspec colname="2" colwidth="133pt" align="left" /><tbody valign="top"><row><entry /><entry>uiPosLastX −=</entry><entry>sX&lt;&lt;2;</entry></row><row><entry /><entry>uiPosLastY −=</entry><entry>sY&lt;&lt;2;</entry></row><row><entry /><entry>uiScanPosLast &lt;&lt;=</entry><entry>4;</entry></row><row><entry /><entry>UInt uiD =</entry><entry>uiPosLastY + uiPosLastX;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>if( uiD &lt; 4 )</entry></row><row><entry /><entry>{</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="56pt" align="left" /><colspec colname="2" colwidth="133pt" align="left" /><tbody valign="top"><row><entry /><entry>uiScanPosLast +=</entry><entry> uiPosLastX + (( uiD * ( uiD + 1 ) ) &gt;&gt;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="left" /><tbody valign="top"><row><entry>1);</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row><row><entry /><entry>else</entry></row><row><entry /><entry>{</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="56pt" align="left" /><colspec colname="2" colwidth="133pt" align="left" /><tbody valign="top"><row><entry /><entry>UInt uiDI =</entry><entry>6 − uiD;</entry></row><row><entry /><entry>uiScanPosLast +=</entry><entry>12 − ( uiDI * ( uiDI + 1 ) &gt;&gt; 1 ) +</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="left" /><tbody valign="top"><row><entry>uiPosLastX;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> In the pseudo-code above, the “uiWidth” indicates a width of the transform coefficient block, “uiPosLastX” indicates an x-coordinate of the block-based LSC indicator, “uiPosLastY” indicates a y-coordinate of the block-based LSC indicator, and “uiScanPosLast” indicates the scan-based LSC indicator. “sX” indicates the x-coordinate of the top-left transform coefficient of the sub-block containing the last significant transform coefficient. “sY” indicates the y-coordinate of the top-left transform coefficient of the sub-block containing the last significant transform coefficient. The pseudo-code above may represent a combination of operations to convert the block-based LSC indicator to a scan-based LSC indicator because the pseudo-code above first performs an operation to determine the scan order (“uiScanPosLast”) of the sub-block that contains the last significant transform coefficient and then performs an operation to determine the scan order of the last significant transform coefficient within the sub-block.

<figref idref="DRAWINGS">FIG. 12</figref> is a flowchart that illustrates an example iterative operation <b>300</b> to convert a block-based LSC indicator into a scan-based LSC indicator. After video decoder <b>30</b> starts operation <b>300</b>, video decoder <b>30</b> may receive a block-based LSC indicator that indicates an LSC of a transform coefficient block according to a scanning order (<b>302</b>). Video decoder <b>30</b> may then set a position indicator to indicate a first position of the transform coefficient block according to the scanning order (<b>304</b>). In some examples, the position indication may include a first value that indicates a horizontal, x position of a current transform coefficient and a second value that indicates a vertical, y position of the current transform coefficient. For example, if the scanning order starts at the DC component, video decoder <b>30</b> may set the position indicator to indicate the position at coordinates (0,0). In addition, video decoder <b>30</b> may initialize a scan-based LSC indicator to zero (<b>306</b>).

Video decoder <b>30</b> may then advance the position indicated by the position indicator according to the scanning order (<b>308</b>). For example, if the scanning order is the horizontal scanning order and the position indicator currently indicates the position (3, 4), video decoder <b>30</b> may advance the position indicated by the position indicator such that the position indicator indicates the position (3, 5). Video decoder <b>30</b> may then increment the scan-based LSC indicator (<b>310</b>).

Video decoder <b>30</b> may then determine whether the position indicated by the position indicator is the same as the position indicated by the block-based LSC indicator (<b>312</b>). In other words, video decoder <b>30</b> may determine whether the indicated positions match. If the position indicated by the position indicator is the same as the position indicated by the block-based LSC indicator, the scan-based LSC indicator indicates the position of the LSC. If the position indicated by the position indicator is not the position indicated by the block-based LSC indicator (“NO” of <b>312</b>), video decoder <b>30</b> may repeat steps <b>308</b>-<b>312</b> with the advanced position indicator. If the position indicated by the position indicator is the position indicated by the block-based LSC indicator (“YES” of <b>312</b>), video decoder <b>30</b> may end operation <b>300</b>.

The following pseudo-code may describe an alternate iterative operation to convert a block-based LSC indicator into a scan-based LSC indicator. In this pseudo-code, video decoder <b>30</b> checks each scan position to determine whether the corresponding block-based position is the position indicated by the LSC indicator. Video decoder <b>30</b> stops checking positions when the current scan position (“uiBlkPosLast”) is equal to the block-based LSC indicator (“uiBlkPos”).

<tables id="TABLE-US-00007" num="00007"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>for( uiScanPosLast = 0; uiScanPosLast &lt; uiMaxNumCoeffM1;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="left" /><tbody valign="top"><row><entry>uiScanPosLast++ )</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>{</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>UInt uiBlkPos = scan[ uiScanPosLast ];</entry></row><row><entry /><entry>if( uiBlkPosLast == uiBlkPos )</entry></row><row><entry /><entry>{</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>break;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

<figref idref="DRAWINGS">FIG. 13</figref> is a conceptual diagram of a transform coefficient block <b>350</b> showing a last significant transform coefficient. In the example of <figref idref="DRAWINGS">FIG. 13</figref>, each circle represents a different transform coefficient in transform coefficient block <b>350</b>. Black circles in <figref idref="DRAWINGS">FIG. 13</figref> correspond to significant transform coefficients and white circles correspond to non-significant transform coefficients. Transform coefficient <b>352</b> is the last significant transform coefficient of transform coefficient block <b>350</b> according to the diagonal scanning order. <figref idref="DRAWINGS">FIG. 13</figref> represents a diagonal scanning order as an arrow running through the circles. Assuming that the top row of transform coefficient block <b>350</b> is row 0 and the leftmost column is column 0, the block-based LSC indicator for transform coefficient <b>352</b> indicates coordinates (2, 1). The scan-based LSC indicator for transform coefficient <b>352</b> may be the number “7.”

It is to be recognized that depending on the embodiment, certain acts or events of any of the methods described herein may be performed in a different sequence, may be added, merged, or left out altogether (e.g., not all described acts or events are necessary for the practice of the method). Moreover, in certain embodiments, acts or events may be performed concurrently, e.g., through multi-threaded processing, interrupt processing, or multiple processors, rather than sequentially.

Those of skill will recognize that the various illustrative logical blocks, modules, circuits, and algorithm steps described in connection with the methods, systems, and apparatuses disclosed herein may be implemented as electronic hardware, computer software executed by a processor, or combinations of both. To clearly illustrate this interchangeability of hardware and software, various illustrative components, blocks, modules, circuits, and steps have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the overall system. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present invention.

Moreover, embodiments disclosed herein may be implemented or performed with an electronic device or circuit such as a general purpose processor, a digital signal processor (DSP), an application specific integrated circuit (ASIC), a field programmable gate array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions described herein. A general purpose processor may be a microprocessor, but in the alternative, the processor may be any conventional processor, controller, microcontroller, or state machine. A processor may also be implemented as a combination of computing devices, e.g., a combination of a DSP and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with a DSP core, or any other such configuration.

The steps of a method or algorithm described in connection with the embodiments disclosed herein may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. A software module may reside in RAM memory, flash memory, ROM memory, EPROM memory, EEPROM memory, registers, hard disk, a removable disk, a CD-ROM, or any other form of storage medium known in the art. An exemplary storage medium is coupled to the processor such the processor may read information from, and write information to, the storage medium. In the alternative, the storage medium may be integral to the processor. The processor and the storage medium may reside in an ASIC. The ASIC may reside in a user terminal. In the alternative, the processor and the storage medium may reside as discrete components in a user terminal.

Various examples have been described. These and other examples are within the scope of the following claims.