Method, apparatus and system for encoding and decoding the transform units of a coding unit

Disclosed is a method of decoding a luma transform and plurality of chroma transforms from a video bitstream. The chroma transforms contain chroma data for a single color channel. The method determines a value of a luma transform skip flag for the luma transform indicating whether data of the luma transform is encoded in the video bitstream as a spatial domain representation. A value of a chroma transform skip flag is determined for a first chroma transform of the plurality of chroma transforms indicating whether the data of the chroma transform is encoded in the video bitstream as a spatial domain representation. The method decodes the luma transform according to the determined luma transform skip flag and the plurality of chroma transforms according to the determined chroma transform skip flag for the first chroma transform.

CROSS-REFERENCE TO RELATED APPLICATION(S)

This application claims the benefit under 35 U.S.C. § 119 of the filing date of Australian Patent Application No. 2012247040, filed Nov. 8, 2012, hereby incorporated by reference in its entirety as if fully set forth herein. That application is a divisional application of Australian Patent Application Nos. 2012232992, filed Sep. 28, 2012, hereby incorporated by reference in its entirety as if fully set forth herein.

TECHNICAL FIELD

The present invention relates generally to digital video signal processing and, in particular, to a method, apparatus and system for encoding and decoding residual coefficients of a transform unit (TU), wherein the transform unit (TU) includes one or more transform units (TUs) and may be configured for multiple chroma formats, including a 4:2:2 chroma format, and wherein the residual coefficients of the transform unit (TU) may either represent data in a frequency domain or a spatial domain.

BACKGROUND

Many applications for video coding currently exist, including applications for transmission and storage of video data. Many video coding standards have also been developed and others are currently in development. Recent developments in video coding standardisation have led to the formation of a group called the “Joint Collaborative Team on Video Coding” (JCT-VC). The Joint Collaborative Team on Video Coding (JCT-VC) includes members of Study Group 16, Question 6 (SG16/Q6) of the Telecommunication Standardisation Sector (ITU-T) of the International Telecommunication Union (ITU), known as the Video Coding Experts Group (VCEG), and members of the International Organisations for Standardisation/International Electrotechnical Commission Joint Technical Committee 1/Subcommittee 29/Working Group 11 (ISO/IEC JTC1/SC29/WG11), also known as the Moving Picture Experts Group (MPEG).

The Joint Collaborative Team on Video Coding (JCT-VC) has the goal of producing a new video coding standard to significantly outperform a presently existing video coding standard, known as “H.264/MPEG-4 AVC”. The H.264/MPEG-4 AVC standard is itself a large improvement on previous video coding standards, such as MPEG-4 and ITU-T H.263. The new video coding standard under development has been named “high efficiency video coding (HEVC)”. The Joint Collaborative Team on Video Coding JCT-VC is also considering implementation challenges arising from technology proposed for high efficiency video coding (HEVC) that create difficulties when scaling implementations of the standard to operate at high resolutions in real-time or high frame rates. One implementation challenge is the complexity and size of logic used to support multiple ‘transform’ sizes for transforming video data between the frequency domain and the spatial domain.

SUMMARY

According to one aspect of the present disclosure there is provided a method of decoding a luma transform and plurality of chroma transforms from a video bitstream, the plurality of chroma transforms containing chroma data for a single colour channel, the method comprising:

determining a value of a luma transform skip flag for the luma transform, the luma transform skip flag indicating whether data of the luma transform is encoded in the video bitstream as a spatial domain representation;

determining a value of a chroma transform skip flag for a first chroma transform of the plurality of chroma transforms, the chroma transform skip flag indicating whether the data of the chroma transform is encoded in the video bitstream as a spatial domain representation; and

decoding the luma transform according to the determined value of the luma transform skip flag and the plurality of chroma transforms according to the determined value of the chroma transform skip flag for the first chroma transform.

According to another aspect there is provided a method of decoding a transform unit having a luma transform and two chroma transforms from a video bitstream, the two chroma transforms containing chroma data for a single colour channel according to a 4:2:2 chroma format, the method comprising:

determining a value of a luma transform skip flag for the luma transform, the luma transform skip flag indicating whether data of the luma transform is encoded in the video bitstream as a spatial domain representation;

determining a value of a chroma transform skip flag for a first chroma transform of the two chroma transforms, the chroma transform skip flag indicating whether the data of the chroma transforms is encoded in the video bitstream as a spatial domain representation; and

decoding the luma transform according to the determined value of the luma transform skip flag and decoding the two chroma transforms according to the determined value of the chroma transform skip flag for the first chroma transform.

According to yet another aspect there is provided a method of decoding a luma transform and plurality of chroma transforms from a video bitstream, the plurality of chroma transforms containing chroma data for a single colour channel, the method comprising:

splitting at least one rectangular one of the transforms into a plurality of square transforms; and

decoding the square transforms.

Desirably the splitting comprises splitting all rectangular transforms into square transforms such that the decoding only operates upon square transforms.

According to another aspect there is provided a method of decoding a transform unit containing chroma residual coefficients from a video bitstream, the transform unit containing at least one chroma residual coefficient array associated with a single chroma channel, the method comprising:

determining a size of the transform unit, the size being related to a hierarchical level of the transform unit in a corresponding coding unit;

decoding from the video bitstream the at least one chroma residual coefficient array using a predetermined maximum number of transforms for the chroma channel of the transform unit;

selecting an inverse transform for the decoded chroma residual coefficient arrays, the inverse transform being selected from a predetermined set of inverse transforms; and

applying the selected inverse transform to each of the chroma residual coefficient arrays to decode chroma residual samples for the chroma channel of the transform unit.

In yet another aspect, disclosed is a method for decoding residual data for a region in a transform unit (TU) in a colour channel encoded in a video bitstream, the method comprising:

first determining from the bitstream that a transform skip flag is enabled;

second determining if the region is a first region in the colour channel and in the transform unit (TU) having a coded block flag (CBF) value of one, and if so, decoding and storing a value of the transform skip flag, otherwise retrieving the value of the transform skip flag; and

decoding the residual data of the region using the value of the transform skip flag.

Here, preferably the first determining step further comprises determining that a coding unit transform quantisation bypass flag is not enabled and the transform size is 4×4.

According to another aspect of the present disclosure, there is provided a method of inverse transforming a plurality of residual coefficient arrays from a video bitstream configured for a 4:2:2 chroma format, the method comprising:

decoding a plurality of luma residual coefficient arrays, wherein each luma residual coefficient array corresponds to one 4×4 luma block of a plurality of 4×4 luma blocks, each 4×4 luma block being collocated with one 4×4 transform unit of a plurality of 4×4 transform units, a plurality of 4×4 luma blocks collectively occupying an 8×8 luma region;

decoding, after the luma residual coefficient arrays are decoded, a plurality of chroma residual coefficient arrays for a first colour channel, wherein each chroma residual coefficient array corresponds to a 4×4 chroma block and each 4×4 chroma block for the first colour channel is collocated with two of the plurality of 4×4 transform units;

decoding, after the chroma residual coefficient arrays for the first colour channel are decoded, a plurality of chroma residual coefficient arrays for a second colour channel, wherein each chroma residual coefficient array corresponds to a 4×4 chroma block and each chroma block for the second colour channel is collocated with two of the plurality of 4×4 transform units; and

applying an inverse transform to each of the decoded plurality of luma residual coefficient arrays, the decoded plurality of chroma residual coefficient arrays for the first colour channel and the decoded plurality of chroma residual coefficient arrays for the second colour channel.

Preferably, the number of luma residual coefficient arrays in the plurality of luma residual coefficient arrays is four. Desirably, wherein the number of chroma residual coefficient arrays in the plurality of chroma residual coefficient arrays is two. Advantageously one residual coefficient array includes all coefficients necessary for inverse transforming one 4×4 block.

According to another aspect, disclosed is a method of forward transforming a plurality of residual coefficient arrays into a video bitstream configured for a 4:2:2 chroma format, the method comprising:

applying a forward transform to each of a plurality of luma residual coefficient arrays, a plurality of chroma residual coefficient arrays for a first colour channel and a plurality of chroma residual coefficient arrays for a second colour channel;

encoding the plurality of luma residual coefficient arrays, wherein each luma residual coefficient array corresponds to one 4×4 luma block of a plurality of 4×4 luma blocks, each 4×4 luma block being collocated with one 4×4 transform unit of a plurality of 4×4 transform units, a plurality of 4×4 luma blocks collectively occupying an 8×8 luma region;

encoding, after the luma residual coefficient arrays are encoded, the plurality of chroma residual coefficient arrays for the first colour channel, wherein each chroma residual coefficient array corresponds to a 4×4 chroma block and each 4×4 chroma block for the first colour channel is collocated with two of the plurality of 4×4 transform units; and

encoding, after the chroma residual coefficient arrays for the first colour channel are encoded, the plurality of chroma residual coefficient arrays for the second colour channel, wherein each chroma residual coefficient array corresponds to a 4×4 chroma block and each chroma block for the second colour channel is collocated with two of the plurality of 4×4 transform units.

Other aspects, including complementary encoders, are also disclosed.

DETAILED DESCRIPTION INCLUDING BEST MODE

FIG. 1is a schematic block diagram showing function modules of a video encoding and decoding system100that may utilise techniques for coding syntax elements representative of inferred subdivision of transform units into multiple transforms for a chroma channel. The system100includes a source device110and a destination device130. A communication channel120is used to communicate encoded video information from the source device110to the destination device130. In some cases, the source device110and destination device130may comprise respective mobile telephone hand-sets, in which case the communication channel120is a wireless channel. In other cases, the source device110and destination device130may comprise video conferencing equipment, in which case the communication channel120is typically a wired channel, such as an internet connection. Moreover, the source device110and the destination device130may comprise any of a wide range of devices, including devices supporting over the air television broadcasts, cable television applications, internet video applications and including applications where the encoded video is captured on some storage medium or a file server.

As illustrated, the source device110includes a video source112, a video encoder114and a transmitter116. The video source112typically comprises a source of captured video frame data, such as an imaging sensor, a previously captured video sequence stored on a non-transitory recording medium, or a video feed from a remote imaging sensor. Examples of source devices110that may include an imaging sensor as the video source112include smart-phones, video camcorders and network video cameras. The video encoder114converts the captured frame data from the video source112into encoded video data and will be described further with reference toFIG. 3. The encoded video data is typically transmitted by the transmitter116over the communication channel120as encoded video information. It is also possible for the encoded video data to be stored in some storage device, such as a “Flash” memory or a hard disk drive, until later being transmitted over the communication channel120.

The destination device130includes a receiver132, a video decoder134and a display device136. The receiver132receives encoded video information from the communication channel120and passes received video data to the video decoder134. The video decoder134then outputs decoded frame data to the display device136. Examples of the display device136include a cathode ray tube, a liquid crystal display, such as in smart-phones, tablet computers, computer monitors or in stand-alone television sets. It is also possible for the functionality of each of the source device110and the destination device130to be embodied in a single device.

Notwithstanding the exemplary devices mentioned above, each of the source device110and destination device130may be configured within a general purpose computing system, typically through a combination of hardware and software components.FIG. 2Aillustrates such a computer system200, which includes: a computer module201; input devices such as a keyboard202, a mouse pointer device203, a scanner226, a camera227, which may be configured as the video source112, and a microphone280; and output devices including a printer215, a display device214, which may be configured as the display device136, and loudspeakers217. An external Modulator-Demodulator (Modem) transceiver device216may be used by the computer module201for communicating to and from a communications network220via a connection221. The communications network220, which may represent the communication channel120, may be a wide-area network (WAN), such as the Internet, a cellular telecommunications network, or a private WAN. Where the connection221is a telephone line, the modem216may be a traditional “dial-up” modem. Alternatively, where the connection221is a high capacity (e.g., cable) connection, the modem216may be a broadband modem. A wireless modem may also be used for wireless connection to the communications network220. The transceiver device216may provide the functionality of the transmitter116and the receiver132and the communication channel120may be embodied in the connection221.

The computer module201typically includes at least one processor unit205, and a memory unit206. For example, the memory unit206may have semiconductor random access memory (RAM) and semiconductor read only memory (ROM). The computer module201also includes an number of input/output (I/O) interfaces including: an audio-video interface207that couples to the video display214, loudspeakers217and microphone280; an I/O interface213that couples to the keyboard202, mouse203, scanner226, camera227and optionally a joystick or other human interface device (not illustrated); and an interface208for the external modem216and printer215. In some implementations, the modem216may be incorporated within the computer module201, for example within the interface208. The computer module201also has a local network interface211, which permits coupling of the computer system200via a connection223to a local-area communications network222, known as a Local Area Network (LAN). As illustrated inFIG. 2A, the local communications network222may also couple to the wide network220via a connection224, which would typically include a so-called “firewall” device or device of similar functionality. The local network interface211may comprise an Ethernet™ circuit card, a Bluetooth™ wireless arrangement or an IEEE 802.11 wireless arrangement; however, numerous other types of interfaces may be practiced for the interface211. The local network interface211may also provide the functionality of the transmitter116and the receiver132and communication channel120may also be embodied in the local communications network222.

The I/O interfaces208and213may afford either or both of serial and parallel connectivity, the former typically being implemented according to the Universal Serial Bus (USB) standards and having corresponding USB connectors (not illustrated). Storage devices209are provided and typically include a hard disk drive (HDD)210. Other storage devices such as a floppy disk drive and a magnetic tape drive (not illustrated) may also be used. An optical disk drive212is typically provided to act as a non-volatile source of data. Portable memory devices, such optical disks (e.g. CD-ROM, DVD, Blu-ray Disc™), USB-RAM, portable, external hard drives, and floppy disks, for example, may be used as appropriate sources of data to the computer system200. Typically, any of the HDD210, optical drive212, networks220and222may also be configured to operate as the video source112, or as a destination for decoded video data to be stored for reproduction via the display214.

The components205to213of the computer module201typically communicate via an interconnected bus204and in a manner that results in a conventional mode of operation of the computer system200known to those in the relevant art. For example, the processor205is coupled to the system bus204using a connection218. Likewise, the memory206and optical disk drive212are coupled to the system bus204by connections219. Examples of computers on which the described arrangements can be practised include IBM-PC's and compatibles, Sun SPARCstations, Apple Mac™ or alike computer systems.

Where appropriate or desired, the video encoder114and the video decoder134, as well as methods described below, may be implemented using the computer system200wherein the video encoder114, the video decoder134and the processes ofFIGS. 10 to 13, to be described, may be implemented as one or more software application programs233executable within the computer system200. In particular, the video encoder114, the video decoder134and the steps of the described methods are effected by instructions231(seeFIG. 2B) in the software233that are carried out within the computer system200. The software instructions231may be formed as one or more code modules, each for performing one or more particular tasks. The software may also be divided into two separate parts, in which a first part and the corresponding code modules performs the described methods and a second part and the corresponding code modules manage a user interface between the first part and the user.

The software may be stored in a computer readable medium, including the storage devices described below, for example. The software is loaded into the computer system200from the computer readable medium, and then executed by the computer system200. A computer readable medium having such software or computer program recorded on the computer readable medium is a computer program product. The use of the computer program product in the computer system200preferably effects an advantageous apparatus for implementing the video encoder114, the video decoder134and the described methods.

The software233is typically stored in the HDD210or the memory206. The software is loaded into the computer system200from a computer readable medium, and executed by the computer system200. Thus, for example, the software233may be stored on an optically readable disk storage medium (e.g., CD-ROM)225that is read by the optical disk drive212.

In some instances, the application programs233may be supplied to the user encoded on one or more CD-ROMs225and read via the corresponding drive212, or alternatively may be read by the user from the networks220or222. Still further, the software can also be loaded into the computer system200from other computer readable media. Computer readable storage media refers to any non-transitory tangible storage medium that provides recorded instructions and/or data to the computer system200for execution and/or processing. Examples of such storage media include floppy disks, magnetic tape, CD-ROM, DVD, Blu-ray Disc, a hard disk drive, a ROM or integrated circuit, USB memory, a magneto-optical disk, or a computer readable card such as a PCMCIA card and the like, whether or not such devices are internal or external of the computer module201. Examples of transitory or non-tangible computer readable transmission media that may also participate in the provision of the software, application programs, instructions and/or video data or encoded video data to the computer module401include radio or infra-red transmission channels as well as a network connection to another computer or networked device, and the Internet or Intranets including e-mail transmissions and information recorded on Websites and the like.

The second part of the application programs233and the corresponding code modules mentioned above may be executed to implement one or more graphical user interfaces (GUIs) to be rendered or otherwise represented upon the display214. Through manipulation of typically the keyboard202and the mouse203, a user of the computer system200and the application may manipulate the interface in a functionally adaptable manner to provide controlling commands and/or input to the applications associated with the GUI(s). Other forms of functionally adaptable user interfaces may also be implemented, such as an audio interface utilizing speech prompts output via the loudspeakers217and user voice commands input via the microphone280.

FIG. 2Bis a detailed schematic block diagram of the processor205and a “memory”234. The memory234represents a logical aggregation of all the memory modules (including the HDD209and semiconductor memory206) that can be accessed by the computer module201inFIG. 2A.

When the computer module201is initially powered up, a power-on self-test (POST) program250executes. The POST program250is typically stored in a ROM249of the semiconductor memory206ofFIG. 2A. A hardware device such as the ROM249storing software is sometimes referred to as firmware. The POST program250examines hardware within the computer module201to ensure proper functioning and typically checks the processor205, the memory234(209,206), and a basic input-output systems software (BIOS) module251, also typically stored in the ROM249, for correct operation. Once the POST program250has run successfully, the BIOS251activates the hard disk drive210ofFIG. 2A. Activation of the hard disk drive210causes a bootstrap loader program252that is resident on the hard disk drive210to execute via the processor205. This loads an operating system253into the RAM memory206, upon which the operating system253commences operation. The operating system253is a system level application, executable by the processor205, to fulfill various high level functions, including processor management, memory management, device management, storage management, software application interface, and generic user interface.

The operating system253manages the memory234(209,206) to ensure that each process or application running on the computer module201has sufficient memory in which to execute without colliding with memory allocated to another process. Furthermore, the different types of memory available in the computer system200ofFIG. 2Amust be used properly so that each process can run effectively. Accordingly, the aggregated memory234is not intended to illustrate how particular segments of memory are allocated (unless otherwise stated), but rather to provide a general view of the memory accessible by the computer system200and how such is used.

As shown inFIG. 2B, the processor205includes a number of functional modules including a control unit239, an arithmetic logic unit (ALU)240, and a local or internal memory248, sometimes called a cache memory. The cache memory248typically includes a number of storage registers244-246in a register section. One or more internal busses241functionally interconnect these functional modules. The processor205typically also has one or more interfaces242for communicating with external devices via the system bus204, using a connection218. The memory234is coupled to the bus204using a connection219.

The application program233includes a sequence of instructions231that may include conditional branch and loop instructions. The program233may also include data232which is used in execution of the program233. The instructions231and the data232are stored in memory locations228,229,230and235,236,237, respectively. Depending upon the relative size of the instructions231and the memory locations228-230, a particular instruction may be stored in a single memory location as depicted by the instruction shown in the memory location230. Alternately, an instruction may be segmented into a number of parts each of which is stored in a separate memory location, as depicted by the instruction segments shown in the memory locations228and229.

In general, the processor205is given a set of instructions which are executed therein. The processor205waits for a subsequent input, to which the processor205reacts to by executing another set of instructions. Each input may be provided from one or more of a number of sources, including data generated by one or more of the input devices202,203, data received from an external source across one of the networks220,202, data retrieved from one of the storage devices206,209or data retrieved from a storage medium225inserted into the corresponding reader212, all depicted inFIG. 2A. The execution of a set of the instructions may in some cases result in output of data. Execution may also involve storing data or variables to the memory234.

The video encoder114, the video decoder134and the described methods may use input variables254, which are stored in the memory234in corresponding memory locations255,256,257. The video encoder114, the video decoder134and the described methods produce output variables261, which are stored in the memory234in corresponding memory locations262,263,264. Intermediate variables258may be stored in memory locations259,260,266and267.

Referring to the processor205ofFIG. 2B, the registers244,245,246, the arithmetic logic unit (ALU)240, and the control unit239work together to perform sequences of micro-operations needed to perform “fetch, decode, and execute” cycles for every instruction in the instruction set making up the program233. Each fetch, decode, and execute cycle comprises:

(a) a fetch operation, which fetches or reads an instruction231from a memory location228,229,230;

(b) a decode operation in which the control unit239determines which instruction has been fetched; and

(c) an execute operation in which the control unit239and/or the ALU240execute the instruction.

Thereafter, a further fetch, decode, and execute cycle for the next instruction may be executed. Similarly, a store cycle may be performed by which the control unit239stores or writes a value to a memory location232.

Each step or sub-process in the processes ofFIGS. 10 to 13to be described is associated with one or more segments of the program233and is typically performed by the register section244,245,247, the ALU240, and the control unit239in the processor205working together to perform the fetch, decode, and execute cycles for every instruction in the instruction set for the noted segments of the program233.

FIG. 3is a schematic block diagram showing functional modules of the video encoder114.FIG. 4is a schematic block diagram showing functional modules of the video decoder134. The video encoder114and video decoder134may be implemented using a general-purpose computer system200, as shown inFIGS. 2A and 2B, where the various functional modules may be implemented by dedicated hardware within the computer system200, by software executable within the computer system200such as one or more software code modules of the software application program233resident on the hard disk drive205and being controlled in its execution by the processor205, or alternatively by a combination of dedicated hardware and software executable within the computer system200. The video encoder114, the video decoder134and the described methods may alternatively be implemented in dedicated hardware, such as one or more integrated circuits performing the functions or sub functions of the described methods. Such dedicated hardware may include graphic processors, digital signal processors, application specific integrated circuits (ASICs), field programmable gate arrays (FPGAs) or one or more microprocessors and associated memories. In particular the video encoder114comprises modules320-344and the video decoder134comprises modules420-434which may each be implemented as one or more software code modules of the software application program233.

Although the video encoder114ofFIG. 3is an example of a high efficiency video coding (HEVC) video encoding pipeline, processing stages performed by the modules320-344are common to other video codecs such as VC-1 or H.264/MPEG-4 AVC. The video encoder114receives captured frame data, such as captured frame data, as a series of frames, each frame including one or more colour channels. Each frame comprises one sample grid per colour channel. Colour information is represented using a ‘colour space’, such as recommendation ITU-R BT.709 (‘YUV’), although other colour spaces are also possible. When the YUV colour space is used, the colour channels include a luma channel (‘Y’) and two chroma channels (‘U’ and ‘V’). Moreover, differing amounts of information may be included in the sample grid of each colour channel, depending on the sampling of the image or through application of filtering to resample the captured frame data. Several sampling approaches, known as ‘chroma formats’ exist, some of which will be described with reference toFIGS. 5A and 5B.

The video encoder114divides each frame of the captured frame data, such as frame data310, into regions generally referred to as ‘coding tree blocks’ (CTBs). Each coding tree block (CTB) includes a hierarchical quad-tree subdivision of a portion of the frame into a collection of ‘coding units’ (CUs). The coding tree block (CTB) generally occupies an area of 64×64 luma samples, although other sizes are possible, such as 16×16 or 32×32. In some cases even larger sizes, such as 128×128, may be used. The coding tree block (CTB) may be sub-divided via a split into four equal sized regions to create a new hierarchy level. Splitting may be applied recursively, resulting in a quad-tree hierarchy. As the coding tree block (CTB) side dimensions are always powers of two and the quad-tree splitting always results in a halving of the width and height, the region side dimensions are also always powers of two. When no further split of a region performed, a ‘coding unit’ (CU) is said to exist within the region. When no split is performed at the top level of the coding tree block, the region occupying the entire coding tree block contains one coding unit (CU) that is generally referred to as a ‘largest coding unit’ (LCU). A minimum size also exists for each coding unit, such as the area occupied by 8×8 luma samples, although other minimum sizes are also possible. Coding units of this size are generally referred to as ‘smallest coding units’ (SCUs). As a result of this quad-tree hierarchy, the entirety of the coding tree block (CTB) is occupied by one or more coding units (CUs).

The video encoder114produces one or more arrays of samples, generally referred to as ‘prediction units’ (PUs) for each coding unit (CU). Various arrangements of prediction units (PUs) in each coding unit (CU) are possible, with a requirement that the prediction units (PUs) do not overlap and that the entirety of the coding unit (CU) is occupied by the one or more prediction units (PUs). This scheme ensures that the prediction units (PUs) cover the entire frame area.

The video encoder114operates by outputting, from a multiplexer module340, a prediction unit (PU)382. A difference module344outputs the difference between the prediction unit (PU)382and a corresponding 2D array of data samples, in the spatial domain, from a coding unit (CU) of the coding tree block (CTB) of the frame data310, the difference being known as a ‘residual sample array’360. The residual sample array360may be transformed into the frequency domain in a transform module320, or the residual sample array360may remain in the spatial domain, with a selection between the two being performed by a multiplexer321, operating under the control of a transform skip control module346and signalled using a transform skip flag386. The transform skip control module346determines the transform skip flag386, which indicates whether the transform module320is used to transform the residual sample array360into a residual coefficient array362, or whether use of the transform module320is skipped. Skipping the transform module320is referred to as a ‘transform skip’. When the transform is not skipped, the residual sample array360from the difference module344is received by the transform module320, which converts (or ‘encodes’) the residual sample array360from a spatial representation to a frequency domain representation by applying a ‘forward transform’. The transform module320creates transform coefficients configured as the residual transform array362for each transform in a transform unit (TU) in a hierarchical sub-division of the coding unit (CU) into one or more transform units (TUs) generally referred to as a ‘transform tree’. When a transform skip is performed, the residual sample array360is represented in the encoded bitstream312in the spatial domain and the transform module320is bypassed, resulting in the residual sample array360being passed directly to a scale and quantise module322via the multiplexer321, which operates under control of the transform skip flag386. The transform skip control module346may test the bit-rate required in the encoded bitstream312for each value of the transform skip flag386(i.e. transform skipped, or normal transform operation). The transform skip control module346may select a value for the transform skip flag386that results in lower bit-rate in the encoded bitstream312, thus achieving higher compression efficiency. Each test performed by the transform skip control module346increases complexity of the video encoder114, and thus it is desirable to reduce the number of cases for which the transform skip module346performs the test to those where the benefit of selecting a transform skip outweighs the cost of performing test. For example, this may be achieved by restricting the transform skip to specific transform sizes and block types, such as only 4×4 transforms for intra-predicted blocks (as described further below) in the high efficiency video coding (HEVC) standard under development. The transform skip functionality is especially useful for encoding residual sample arrays360that contain much ‘high frequency’ information. High frequency information is typically present in frame data310containing many sharp edges, such as where alphanumeric characters are embedded in the frame data310. Other sources of frame data310, such as computer generated graphics, may also contain much high frequency information. The DCT-like transform of the transform module320is optimised for frame data310containing mostly low frequency information, such as that obtained from an imaging sensor capturing a natural image. The presence of the transform skip functionality thus provides considerable coding efficiency gain for applications, which are relevant for the high efficiency video coding (HEVC) standard under development. For the video encoder114, one drawback of supporting the transform skip functionality is the need to test two possible modes for the transform skip flag386. As discussed below, the transform skip functionality is supported for a residual sample array360size of 4×4 samples and when the residual sample array360corresponds to an intra-predicted block, as described with reference to an intra-frame prediction module336. However the transform skip flag386is desirably separately signalled for each colour channel and thus a separate test may be performed by the transform skip control module346for each colour channel. Separate signalling for each colour channel is advantageous because the high frequency information may be concentrated in one or both chroma channels, thus being suited to transform skip, while the luma channel may have minimal high frequency information and thus benefit from using a transform. For example, coloured text on a coloured background would result in this scenario.

For the high efficiency video coding (HEVC) standard under development, the conversion to the frequency domain representation is implemented using a modified discrete cosine transform (DCT), in which a traditional DCT is modified to be implemented using shifts and additions. Various sizes for the residual sample array360and the transform coefficients362are possible, in accordance with the supported transform sizes. In the high efficiency video coding (HEVC) standard under development, transforms are performed on 2D arrays of samples having specific sizes, such as 32×32, 16×16, 8×8 and 4×4. A predetermined set of transform sizes available to a video encoder114may thus be said to exist. Moreover, as foreshadowed above, the set of transform sizes may differ between the luma channel and the chroma channels. Two-dimensional transforms are generally configured to be ‘separable’, enabling implementation as a first set of 1D transforms operating on the 2D array of samples in one direction (e.g. on rows), followed by a second set of 1D transform operating on the 2D array of samples output from the first set of 1D transforms in the other direction (e.g. on columns) Transforms having the same width and height are generally referred to as ‘square transforms’. Additional transforms, having differing widths and heights are also possible and are generally referred to as ‘non-square transforms’. Optimised implementations of the transforms may combine the row and column one-dimensional transforms into specific hardware or software modules, such as a 4×4 transform module or an 8×8 transform module. Transforms having larger dimensions require larger amounts of circuitry to implement, even though they may be infrequently used. Accordingly, a maximum transform size of 32×32 exists in the high efficiency video coding (HEVC) standard under development. The integrated nature of transform implementation also introduces a preference to reduce the number of non-square transform sizes supported, as these will typically require entirely new hardware to be implemented, instead of reusing existing one-dimensional transform logic present from corresponding square transforms.

Transforms are applied to both the luma and chroma channels. Differences between the handling of luma and chroma channels with regard to transform units (TUs) exist and will be discussed below with reference toFIGS. 5A and 5B. Each transform tree occupies one coding unit (CU) and is defined as a quad-tree decomposition of the coding unit (CU) into a hierarchy containing one transform unit (TU) at each leaf node of the transform tree (quad-tree) hierarchy, with each transform unit (TU) able to make use of transforms of the supported transform sizes. Similarly to the coding tree block (CTB), it is necessary for the entirety of the coding unit (CU) to be occupied by one or more transform units (TUs). At each level of the transform tree quad-tree hierarchy a ‘coded block flag value’ signals the possible presence of a transform in each colour channel, either in the present hierarchy level when no further splits are present, or to signal that lower hierarchy levels may contain at least one transform among the resulting transform units (TUs). When the coded block flag value is zero, no transform is performed for the corresponding colour channel of any transform units (TU) of the transform tree, either at the present hierarchical level or at lower hierarchical levels. When the coded block flag value is one, the region contains a transform which must have at least one non-zero residual coefficient. In this manner, for each colour channel, zero or more transforms may cover a portion of the area of the coding unit (CU) varying from none up to the entirety of the coding unit (CU). Separate coded block flag values exist for each colour channel. Each coded block flag value is not required to be encoded, as cases exist where there is only one possible coded block flag value.

The output of the multiplexer321is thus one of the residual sample array360or the transform coefficient array362, and is labelled simply as an array363inFIG. 3. The array363is input to the scale and quantise module322where the sample values thereof are scaled and quantised according to a determined quantisation parameter384to produce a residual data array364. The scale and quantisation process results in a loss of precision, dependent on the value of the determined quantisation parameter384. A higher value of the determined quantisation parameter384results in greater information being lost from the residual data. This increases the compression achieved by the video encoder114at the expense of reducing the visual quality of the output from the video decoder134. The determined quantisation parameter384may be adapted during encoding of each frame of the frame data310, or it may be fixed for a portion of the frame data310, such as an entire frame. Other adaptations of the determined quantisation parameter384are also possible, such as quantising different residual coefficients with separate values. The residual data array364and determined quantisation parameter384are taken as input to an inverse scaling module326which reverses the scaling performed by the scale and quantise module322to produce rescaled data arrays366, which are rescaled versions of the residual data array364. The high efficiency video coding standard (HEVC) standard under development also supports a ‘lossless’ coding mode. When lossless coding is in use, the transform module320and the scale and quantise module322are both bypassed, resulting in the residual sample array360being input directly to the entropy encoder324. In lossless mode, the inverse scaling module326and the inverse transform module328are also bypassed. The selection of lossless coding mode (as opposed to the usual lossy′ mode) is encoded in the encoded bitstream312by the entropy encoder324. Logic to implement the bypass for lossless mode is not illustrated inFIG. 3. Bypassing the scale and quantise module322results in no quantisation of the residual coefficient array362or residual sample array360, and an exact representation of the frame data310is encoded in the encoded bitstream312by the entropy encoder324. The lossless coding mode results in low compression efficiency of the video encoder114and therefore is generally used only in applications where lossless coding is highly desirable, such as in medical applications.

The residual data array364, the determined quantisation parameter384and the transform skip flag386are also taken as input to an entropy encoder module324which encodes the values of the residual data array364in an encoded bitstream312(or ‘video bitstream’). The residual data array364in each transform unit (TU) are encoded in groups generally known as ‘sub-blocks’. Sub-blocks should preferably have the same dimensions regardless of the size of the transform, as this permits reuse of logic relating to sub-block processing. The residual data within one sub-block are generally referred to as a ‘data group’ (or a ‘coefficient group’, even when the transform skip is applied and the ‘coefficient group’ includes a spatial domain representation rather than a frequency domain representation) and for each data group, a data group flag is generally encoded to indicate if at least one residual data value within the data group is non-zero. In some cases the data group flag may be inferred and thus is not encoded. A flag is encoded for each residual data value belonging to a data group having a data group flag value of one to indicate if the residual data value is non-zero (‘significant’) or zero (‘non-significant’). Due to the loss of precision resulting from the scale and quantise module322, the rescaled data arrays366are not identical to the original values in the array363. The rescaled data arrays366from the inverse scaling module326are then output to an inverse transform module328. The inverse transform module328performs an inverse transform from the frequency domain to the spatial domain to produce a spatial-domain representation368of the rescaled transform coefficient arrays366identical to a spatial domain representation that is produced at the video decoder134. A multiplexer369is configured to complement the operation of the multiplexer321. The multiplexer369is configured to receive each of the rescaled data arrays366and the (transformed) spatial-domain representation368as inputs and, under control of the transform skip flag386, select one of the inputs366or368as an input to a summation module342.

A motion estimation module338produces motion vectors374by comparing the frame data310with previous frame data from one or more sets of frames stored in a frame buffer module332, generally configured within the memory206. The sets of frames are known as ‘reference picture lists’. The motion vectors374are then input to a motion compensation module334which produces an inter-predicted prediction unit (PU)376by filtering samples stored in the frame buffer module332, taking into account a spatial offset derived from the motion vectors374. Not illustrated inFIG. 3, the motion vectors374are also passed as syntax elements to the entropy encoder module324for encoding in the encoded bitstream312. The intra-frame prediction module336produces an intra-predicted prediction unit (PU)378using samples370obtained from the summation module342, which sums the prediction unit (PU)382from the multiplexer module340and the spatial domain output of the multiplexer369. The intra-frame prediction module336also produces an intra-prediction mode380which is sent to the entropy encoder324for encoding into the encoded bitstream312.

Prediction units (PUs) may be generated using either an intra-prediction or an inter-prediction method. Intra-prediction methods make use of samples adjacent to the prediction unit (PU) that have previously been decoded (typically above and to the left of the prediction unit) in order to generate reference samples within the prediction unit (PU). Various directions of intra-prediction are possible, referred to as the ‘intra-prediction mode’. Inter-prediction methods make use of a motion vector to refer to a block from a selected reference frame. As the block may have any alignment down to a sub-sample precision, e.g. one eighth of a sample, filtering is necessary to create a block of reference samples for the prediction unit (PU). The decision on which method to use is made according to a rate-distortion trade-off between desired bit-rate of the resulting encoded bitstream312and the amount of image quality distortion introduced by either the intra-prediction or inter-prediction method. If intra-prediction is used, one intra-prediction mode is selected from the set of intra-prediction possible modes, also according to a rate-distortion trade-off. The multiplexer module340selects either the intra-predicted reference samples378from the intra-frame prediction module336, or the inter-predicted prediction unit (PU)376from the motion compensation block334, depending on the decision made by the rate distortion algorithm. The summation module342produces a sum370that is input to a deblocking filter module330. The deblocking filter module330performs filtering along block boundaries, producing deblocked samples372that are written to the frame buffer module332configured within the memory206. The frame buffer module332is a buffer with sufficient capacity to hold data from one or more past frames for future reference as part of a reference picture list.

For the high efficiency video coding (HEVC) standard under development, the encoded bitstream312produced by the entropy encoder324is delineated into network abstraction layer (NAL) units. Generally, each slice of a frame is contained in one NAL unit. The entropy encoder324encodes the residual array364, the intra-prediction mode380, the motion vectors and other parameters, collectively referred to as ‘syntax elements’, into the encoded bitstream312by performing a context adaptive binary arithmetic coding (CABAC) algorithm. Syntax elements are grouped together into ‘syntax structures’, these groupings may contain recursion to describe hierarchical structures. In addition to ordinal values, such as an intra-prediction mode or integer values, such as a motion vector, syntax elements also include flags, such as to indicate a quad-tree split. The motion estimation module338and motion compensation module334operate on motion vectors374, having a precision of ⅛ of a luma sample, enabling precise modelling of motion between frames in the frame data310.

Although the video decoder134ofFIG. 4is described with reference to a high efficiency video coding (HEVC) video decoding pipeline, processing stages performed by the modules420-434are common to other video codecs that employ entropy coding, such as H.264/MPEG-4 AVC, MPEG-2 and VC-1. The encoded video information may also be read from memory206, the hard disk drive210, a CD-ROM, a Blu-Ray™ disk or other computer readable storage medium. Alternatively the encoded video information may be received from an external source such as a server connected to the communications network220or a radio-frequency receiver.

As seen inFIG. 4, received video data, such as the encoded bitstream312, is input to the video decoder134. The encoded bitstream312may be read from memory206, the hard disk drive210, a CD-ROM, a Blu-Ray™ disk or other computer readable storage medium. Alternatively the encoded bitstream312may be received from an external source such as a server connected to the communications network220or a radio-frequency receiver. The encoded bitstream312contains encoded syntax elements representing the captured frame data to be decoded.

The encoded bitstream312is input to an entropy decoder module420which extracts the syntax elements from the encoded bitstream312and passes the values of the syntax elements to other blocks in the video decoder134. The entropy decoder module420applies the context adaptive binary arithmetic coding (CABAC) algorithm to decode syntax elements from the encoded bitstream312. The decoded syntax elements are used to reconstruct parameters within the video decoder134. Parameters include zero or more residual data array450, motion vectors452, a prediction mode454and a transform skip flag468. The residual data array450is passed to an inverse scale module421, the motion vectors452are passed to a motion compensation module434, and the prediction mode454is passed to an intra-frame prediction module426and to a multiplexer428. The inverse scale module421performs inverse scaling on the residual data to create reconstructed data455. When the transform skip flag468is zero, the inverse scale module421outputs the reconstructed data455to an inverse transform module422. The inverse transform module422applies an ‘inverse transform’ to convert (or ‘decode’) the reconstructed data, which in this case are transform coefficients, from a frequency domain representation to a spatial domain representation, outputting a residual sample array456via a multiplexer module423. When the value of the transform skip flag468is one, the reconstructed data455, which in this case is in the spatial domain, are output as the residual sample array456via the multiplexer module423. The inverse transform module422performs the same operation as the inverse transform328. The inverse transform module422must therefore be configured to provide a predetermined set of transform sizes required to decode an encoded bitstream312that is compliant with the high efficiency video coding (HEVC) standard under development. When signalling in the encoded bitstream312indicates that the lossless mode was used, the video decoder134is configured to bypass the inverse scale module421and the inverse transform module422(not illustrated inFIG. 4), resulting in the residual data array450being input directly to a summation module424.

The motion compensation module434uses the motion vectors452from the entropy decoder module420, combined with reference frame data460from the a frame buffer block432, configured within the memory206, to produce an inter-predicted prediction unit (PU)462for a prediction unit (PU), being a prediction of output decoded frame data. When the prediction mode454indicates that the current prediction unit was coded using intra-prediction, the intra-frame prediction module426produces an intra-predicted prediction unit (PU)464for the prediction unit (PU) using samples spatially neighbouring the prediction unit (PU) and a prediction direction also supplied by the prediction mode454. The spatially neighbouring samples are obtained from a sum458, output from the summation module424. The multiplexer module428selects the intra-predicted prediction unit (PU)464or the inter-predicted prediction unit (PU)462for a prediction unit (PU)466, depending on the current prediction mode454. The prediction unit (PU)466, which is output from the multiplexer module428, is added to the residual sample array456from the inverse scale and transform module422by the summation module424to produce the sum458which is then input to each of a deblocking filter module430and the intra-frame prediction module426. The deblocking filter module430performs filtering along data block boundaries, such as transform unit (TU) boundaries, to smooth visible artefacts. The output of the deblocking filter module430is written to the frame buffer module432configured within the memory206. The frame buffer module432provides sufficient storage to hold one or more decoded frames for future reference. Decoded frames412are also output from the frame buffer module432to a display device, such as the display device136.

FIGS. 5A and 5Beach show sample grids of a frame portion500and a frame portion510encoded using a 4:2:0 and a 4:2:2 chroma format respectively. The chroma format is specified as a configuration parameter to the video encoder114and the video encoder114encodes a ‘chroma_format_idc’ syntax element into the encoded bitstream312that specifies the chroma format. The video decoder134decodes the ‘chroma_format_idc’ syntax element from the encoded bitstream312to determine the chroma format in use. For example, when a 4:2:0 chroma format is in use, the value of chroma_format_idc is one, when a 4:2:2 chroma format is in use, the value of chroma_format_idc is two and when a 4:4:4 chroma format is in use, the value of chroma_format_idc is three. InFIGS. 5A and 5B, luma sample locations, such as a luma sample location501, are illustrated using ‘X’ symbols, and chroma sample locations, such as a chroma sample location502, are illustrated using ‘O’ symbols. By sampling the frame portion500at the points indicated, a sample grid is obtained for each colour channel when a 4:2:0 chroma format is applied. At each luma sample location X, the luma channel (‘Y’) is sampled, and at each chroma sample location O, both the chroma channels (‘U’ and ‘V’) are sampled. As shown inFIG. 5A, for each chroma sample location, a 2×2 arrangement of luma sample locations exists. By sampling the luma samples at the luma sample locations and chroma samples at the chroma sample locations indicated in the frame portion510, a sample grid is obtained for each colour channel when a 4:2:2 chroma format is applied. The same allocation of samples to colour channels is made for the frame portion510as for the frame portion500. In contrast to the frame portion500, twice as many chroma sample locations exist in frame portion510. In frame portion510the chroma sample locations are collocated with every second luma sample location. Accordingly, inFIG. 5B, for each chroma sample location, an arrangement of 2×1 luma sample locations exists.

Various allowable dimensions of transform units were described above in units of luma samples. The region covered by a transform applied for the luma channel will thus have the same dimensions as the transform unit dimensions. As the transform units also encode chroma channels, the applied transform for each chroma channel will have dimensions adapted according to the particular chroma format in use. For example, when a 4:2:0 chroma format is in use, a 16×16 transform unit (TU) will use a 16×16 transform for the luma channel, and an 8×8 transform for each chroma channel. One special case is that when a 4×4 transform is used for the luma channel there is no corresponding 2×2 transform available (when the 4:2:0 chroma format is applied) or 4×2 transform available (when the 4:2:2 chroma format is applied) that could be used for the chroma channels. In this special case, a 4×4 transform for each chroma channel may cover the region occupied by multiple luma transforms.

FIG. 6Ais a schematic representation of an exemplary transform tree of a coding unit (CU)602(depicted with a thick border), within a coding tree block (CTB)600of the frame. A single quad-tree subdivision divides the coding tree block (CTB)600into four 32×32 coding units (CUs), such as the coding unit (CU)602. An exemplary transform tree exists within the coding unit (CU)602. The exemplary transform tree includes several quad-tree subdivisions, resulting in ten transform units (TUs) numbered as such inFIG. 6A, for example the transform unit #9(TU)604. The transform units #1-#10cover the entirety of the coding unit (CU)602. Each quad-tree subdivision divides a region spatially into four quadrants, resulting in four smaller regions. Each transform unit (TU) has a transform depth value, corresponding to a hierarchical level of the transform unit (TU) within the transform tree. The hierarchical level indicates the number of quad-tree subdivisions performed before the quad-tree subdivision terminated, resulting in an instance of a transform unit (TU) that occupies the corresponding region. For example, the transform unit #9(TU)604, occupies one quarter of the area of the coding unit (CU)602and therefore has transform depth of one. Each transform unit (TU) has an associated size (or ‘transform size’), generally described as the dimensions of the region containing the transform unit (TU) on the luma sample grid. The size is dependent on the coding unit (CU) size and the transform depth. Transform units (TUs) with a transform depth of zero have a size equal to the size of the corresponding coding unit (CU). Each increment of the transform depth results in a halving of the size of transform units (TUs) present in the transform tree at the given transform depth. As the frame includes a luma channel and chroma channels, the coding unit (CU)602occupies a region on both the luma sample grid and the chroma sample grid and thus each transform unit (TU) includes information describing both the luma samples on the luma sample grid and the chroma samples on the chroma sample grid. The nature of the information for each transform unit (TU) is dependent on the processing stage of the video encoder114or the video decoder134. At the input to the transform module320and the output of the inverse scale and transform module422, the residual sample array360and456respectively contain information for each transform unit (TU) in the spatial domain. The residual sample array360and456may be further divided into a ‘chroma residual sample array’ and a ‘luma residual sample array’, due to differences in processing between the luma channel and the chroma channels. At the output from the scale and quantise module322and the input of the inverse scale and transform module422, the residual data array364and450respectively contain information for each transform unit (TU) in the frequency domain. The residual data arrays364and450may be further divided into a ‘chroma residual data array’ and a ‘luma residual data array’, due to differences in processing between the luma channel and the chroma channels.

FIG. 6Billustrates an exemplary transform tree630, corresponding to the exemplary transform tree ofFIG. 6A, for the luma channel of a 32×32 coding unit (CU), containing a set of transform units (TUs) and occupying the coding unit (CU)602, which occupies a 32×32 luma sample array on the luma sample grid.FIG. 7illustrates a data structure700that represents the exemplary transform tree630. InFIG. 6B, boxes numbered 1 to 10 indicate transform units present within region632(exemplified by several transform units (TUs)640), and each box is contained in a region that is not further sub-divided (indicated by a box with dashed border).

InFIG. 6B, boxes numbered 1 and 9 contain 16×16 transforms for the luma channel, boxes numbered 2, 3 and 8 contain 8×8 transforms for the luma channel and boxes numbered 4 to 7 contain 4×4 transforms for the luma channel. The corresponding region (dashed box) for each of these boxes has coded block flag value of one, to indicate the presence of a transform.

The presence or absence of a transform for each colour channel is specified by a separate coded block flag value which is used in each of encoding and decoding of the bitstream, but which need not be transmitted in the bitstream, as will be discussed below. Consequently, the number of residual coefficient arrays450output from the entropy decoder420is dependent on the coded block flag values. When no significant coefficients are present (i.e. all coefficients are zero) in any colour channel, the number of residual data (coefficient) arrays450output from the entropy decoder420is zero.

InFIG. 7, the circles represent split transform flag values with the split transform flag value being indicated inside the corresponding circle. InFIG. 7, the triangles represent coded block flag values, with the coded block flag value being indicated inside the corresponding triangle. The squares represent transform units, with each transform numbered to accord with the transform numbering present inFIG. 6B.

The uppermost hierarchical level of the exemplary transform tree630contains a region632occupying a 32×32 coding unit (CU). A split transform flag value702indicates that the region632is sub-divided into four 16×16 regions, such as a region634, thus defining a ‘non-leaf’ node of the exemplary transform tree630. For each 16×16 region, a further split transform flag value, such as a split transform flag value704, indicates that the respective 16×16 region should be further sub-divided into four 8×8 regions. For example, the region634is not further sub-divided, as indicated by the split transform flag value704of zero, thus defining a ‘leaf’ node of the exemplary transform tree630. In contrast, a region638is further sub-divided into four 4×4 regions (such as a region636), as indicated by a split transform flag value712of one. The recursive split structure present in the transform tree630is analogous to the quad-tree split present in the coding tree block (CTB). For the luma channel, at the ‘leaf’ nodes of the quad-tree, the presence of a transform in the transform unit (TU) is signalled by a coded block flag value, for example a coded block flag value708of one indicates the presence of a transform710in the region634.

As a transform may be used to represent residual data in each region, regions are not permitted to be smaller than the smallest supported transform size, such as 4×4 luma samples for the luma channel. Additionally, for regions larger than the largest available transform size, a split transform flag value of one is inferred. For example, for a transform tree with a top level of a 64×64 coding unit, an automatic sub-division (i.e.: not signalled in the encoded bitstream312) into four 32×32 regions occurs when the largest supported transform size is 32×32 luma samples.

A lower right 16×16 region642contains a transform unit (TU) (numbered 10 (ten) and shaded) with no transform for the luma channel and therefore has a corresponding coded block flag value716of zero.

FIGS. 6C and 8illustrate the exemplary transform tree630, corresponding to the exemplary transform tree ofFIG. 6A, for a chroma channel, configured for the 4:2:2 chroma format and containing a set of transforms for a chroma channel corresponding to the transform tree630for the luma channel and represented by a data structure800. As the transform tree hierarchy is common by virtue of the structure ofFIG. 6Abetween the luma channel and the chroma channels, the split transform flag values are shared between the data structures700and800. In contrast to the data structure700, the data structure800includes a coded block flag value with each transform split flag value of one (i.e. on non-leaf nodes of the transform tree). For example, a coded block flag value802of one is associated with the transform split flag702. If the coded block flag value on a non-leaf node of the transform tree is zero, coded block flag values on the child nodes are inferred as zero (and no corresponding coded block flags are encoded in the encoded bitstream312). Coded block flag values at non-leaf regions enable terminating the encoding of coded block flags at lower levels of the transform tree for each chroma channel if no significant residual coefficients are present in any of the child regions, even though significant residual coefficients may be present in the luma channel. This is a common situation for typical captured frame data, as the majority of information is present in the luma channel.

When the video encoder114and the video decoder134are configured for a 4:4:4 chroma format, the chroma region of each chroma channel of any given transform unit (TU) of a size that is not one of the predetermined set of transform unit (TU) sizes has identical dimensions to the luma regions of the given transform unit (TU) (i.e.: when an inferred split does not take place). When the video encoder114and the video decoder134are configured for a 4:4:4 chroma format, the chroma region of each chroma channel of any given transform unit (TU) of a size that is one of the predetermined set of transform unit (TU) sizes has dimensions smaller than to the luma regions of the given transform unit (TU) (i.e.: when an inferred split does take place).

When a 4:2:2 chroma format is in use, this results in the coding unit (CU)602including a 16×32 region662ofFIG. 6Cof chroma samples for each chroma channel and thus occupying a 16×32 region on the chroma sample grid.FIG. 6Cillustrates the regions on a chroma sample grid, drawn as an array of chroma samples, with each chroma sample equally spaced horizontally and vertically (in contrast toFIG. 5B). Due to the use of the 4:2:2 chroma format, each chroma regions ofFIG. 6Cappears horizontally compressed with respect to the corresponding luma region ofFIG. 6B. The split transform flag value702of one divides the 16×32 region662, corresponding to the coding unit (CU)602, into four 8×16 regions, such as an 8×16 region664. The 8×16 region664has a non-square shape and is also larger in size than other non-square regions illustrated inFIG. 6C, such as a 4×8 region670. For each 8×16 region, a split transform flag value, such as the split transform flag value704, indicates whether the corresponding 8×16 region should be further sub-divided into four smaller 4×8 regions, in an analogous manner to the quad-tree splitting present in the transform tree630for the luma sample array. An upper right 8×16 region672is further sub-divided into four 4×8 regions. A coded block flag value804of one indicates that each of the four 4×8 regions could contain significant residual coefficients. A coded block flag for each 4×8 region is thus required to indicate the presence of a transform for the corresponding region. Of these four 4×8 regions, a lower left 4×8 region674(shaded) contains a transform unit (TU) but does not contain a transform and therefore has a coded block flag value814of zero. The remaining 4×8 regions, such as the region670, each have a transform and therefore have corresponding coded block flag values of one. The upper left 8×16 region is sub-divided into two equal-sizes 8×8 regions. In contrast to the quad-tree subdivision, no corresponding split transform flag is present in the encoded bitstream312.

Splitting a region of a channel, such as a chroma channel, of a transform unit (TU) into multiple regions (each of which may have a transform), without signalling being present in the encoded bitstream312, is referred to as an ‘inferred split’. The inferred split eliminates the need to introduce hardware supporting a non-square transform for this case (8×16). Instead, transforms, such as a first 8×8 transform666, are used. As it is possible for each of the regions resulting from the inferred split to contain all zero residual information, it is necessary to specify the presence of a transform in each region resulting from the inferred split. Accordingly, separate coded block flag values are required for each region resulting from an inferred split. In this case, coded block flag values806and808correspond to the first 8×8 transform666and a second 8×8 transform668respectively. For transform units (TUs) where no inferred split takes place, a coded block flag value for each chroma channel specifies the presence or absence of a transform for the region occupied by the transform unit (TU) for the chroma channel. When an inferred split takes place, a separate coded block flag value (not illustrated inFIG. 8) is required for each of the resulting regions, however implementations may retain a coded block flag value attributable to the entire transform unit (TU). The separate coded block flag value could be inferred as ‘one’ in all cases, or the separate coded block flag value could be determined by performing a logical ‘OR’ operation to the coded block flag value of each region resulting from the split. If the separate coded block flag value is determined from the coded block flag value of each region resulting from the split, the separate coded block flag value may be encoded in the encoded bitstream312by the entropy encoder324and decoded from the encoded bitstream312by the entropy decoder420as an additional coded block flag (not illustrated inFIG. 9). In such a case, when the separate coded block flag value is zero, the coded block flag value of each region from the split may be inferred to be zero and when the separate coded block flag value is one, the coded block flags for each region from the split are encoded in the encoded bitstream312by the entropy encoder324and decoded from the encoded bitstream312by the entropy decoder420.

The lower left 8×16 region680of the 16×32 region662illustrates an inferred split where an 8×8 transform is present in the upper 8×8 inferred region682but no 8×8 transform is present in the lower 8×8 inferred region684. A lower right 8×16 array676(shaded) contains a transform unit (TU) but does not contain a transform in either square 8×8 region resulting from the inferred split and therefore has coded block flag values810812of zero.

The presence of two chroma channels results in a duplication of the structure depicted inFIG. 6C, with separate coded block flag values used to specify the presence of transforms for each chroma channel. In this implementation, a split was inferred for region sizes for chroma other than the size 4×8, resulting in using a 4×8 rectangular transform, such as a 4×8 transform816(contained in region670), and enabling reuse of existing square transforms in other cases (e.g. 8×8, 16×16). Thus, a set of predetermined region sizes (such as 8×16 and 16×32) may be said to exist, for which a split into two regions, and hence two transforms (of sizes 8×8 and 16×16), can be used. Different definitions of the predetermined set of region sizes for which an inferred split occurs are also possible and will allow a different combination of existing square transforms and rectangular transforms to be used. It is also possible for certain implementations to always infer a split, in which case no rectangular transform is introduced for the chroma 4:2:2 colour channels. In such a case, the predetermined set of region sizes for which an inferred split occurs contains all possible chroma region sizes (e.g. 4×8, 8×16 and 16×32 for a 4:2:2 chroma format, or 4×4, 8×8, 16×16 and 32×32 for a 4:4:4 chroma format).

FIG. 16is a schematic representation showing an example of ‘no rectangular transform’ for an implementation of an ‘always’ inferred split for all possible chroma region sizes (4×8, 8×16, and 16×32) for the 4:2:2 chroma formats. As illustrated inFIG. 16with labelling of ‘1’ (one) and ‘2’ (two) for each chroma region resulting from the inferred split.

When a 4:2:0 chroma format is in use, an inferred split does not take place for either chroma region in the transform unit (TU), therefore the maximum number of transforms for each chroma channel is always one (the coded block flag value for each chroma channel controls whether the chroma transform occurs).

Although the video encoder114and the video decoder134are described independently of differences between the luma and chroma channels, the differing sample grids resulting from the chroma formats necessitates the need for differences in the modules. Practical implementations may have a separate ‘processing paths’ for the luma channel and for the chroma channels. Such an implementation may thus decouple processing of luma samples and chroma samples. As the encoded bitstream312is a single bitstream for both the luma and chroma channels, the entropy encoder324and the entropy decoder420are not decoupled. Additionally, a single frame buffer, such as the frame buffer332432holds luma and chroma samples and is thus not decoupled. However, the modules322-330and334-340and the modules422-430and434may have luma and chroma processing decoupled, enabling implementations to have separate logic for luma and chroma, thus creating a ‘luma processing path’ and a ‘chroma processing path’.

Certain implementations may infer a split for the 16×32 region of a chroma channel of a transform unit (TU) into two 16×16 regions, but not infer a split for the 8×16 and 4×8 cases. Such implementations avoid the need to introduce 32-point transform logic into the chroma processing path, instead being able to rely on 4, 8 or 16-point transform logic well-established in the art.

FIGS. 9A and 9Billustrate a syntax structure that can be used to encode or otherwise represent a hierarchical level of the transform tree. At non-leaf nodes of a transform tree, a syntax structure900is expanded recursively in accordance with data structures, such as the data structures700and800, to define the syntax elements present in a portion of the encoded bitstream312corresponding to the transform tree. At leaf nodes of a transform tree (where no further sub-division takes place in the transform tree) a syntax structure930defines syntax elements present in the portion of the encoded bitstream312. Typically, one data structure for luma and two data structures for chroma are present, although additional data structures are possible, such as for encoding an alpha channel or a depth map. Alternatively, fewer data structures may be utilised, such as in the case where a single data structure is shared by the chroma channels and coded block flag values are able to be shared between the chroma channels. A transform tree non-leaf node syntax structure902defines the encoding of one hierarchical level of a transform tree, such as the transform tree630. A split transform flag910encodes a split transform flag value of one, such as the split transform flag value702. This value indicates that the transform tree non-leaf node syntax structure902includes a lower hierarchical level that contains additional instances of the transform tree non-leaf node syntax structure902or transform tree leaf-node syntax structure932, or ‘child nodes’. A coded block flag912encodes the coded block flag value802of one for the ‘U’ chroma channel and a coded block flag914encodes a further coded block flag value for the ‘V’ chroma channel. If the transform tree non-leaf node syntax structure902is defining the top level of the transform tree hierarchy then the coded block flags912914are present. If the transform tree non-leaf node syntax structure902is not defining the top level of the transform tree hierarchy then the coded block flags912914are only present if the corresponding coded block flags in the parent level of the transform tree hierarchy are present and one-valued. As a lower hierarchical level exists in the transform tree630(relative to the top hierarchical level), a quad-tree sub-division takes place. This sub-division results in four transform tree syntax structures916,918,920,922(identified by a variable ‘blkIdx’ (block-index) numbered from zero to three) being included in the transform tree non-leaf node syntax structure902.

The syntax structure930defines the encoding of the leaf node of the transform tree leaf node932(i.e. where no further sub-division takes place). A split transform flag940encodes a split transform flag value of zero, such as the split transform flag value704.

A split transform flag is only encoded if the corresponding region is larger than a minimum size. For example, the region636has the smallest allowable size for a region of 4×4 luma samples (corresponding to the smallest supported luma transform size) so a transform split flag value714is inferred as zero and no split transform flag is encoded for the corresponding transform tree syntax structure.

For the region636, chroma residual samples are transformed using a 4×8 chroma transform, hence no inferred transform split is present. Coded block flags, such as a coded block flag942and a coded block flag946may be present to signal the presence of a transform for each of the chroma channels. A coded block flag950signals the presence of a transform for the luma channel. Residual coefficients for the luma and chroma channels (if present) are present in a transform unit (TU) syntax structure952. If the value of the coded block flag950is one, a luma transform skip flag964and a luma residual data block954, encoding either residual coefficients for a luma transform or residual samples when the transform is skipped, are present in the encoded bitstream312. The value of the luma transform skip flag964indicates whether the transform module320in the video encoder114and the inverse transform module422in the video decoder134is used (in normal operation) or bypassed (in transform skip operation). If the value of the coded block flag for each chroma channel is one, corresponding chroma transform skip flags966and968and chroma residual blocks956and960are present in the encoded bitstream312. The transform skip flag966signals the transform skip mode for chroma residual block956, and the transform skip flag968signals the transform skip mode for the chroma residual block960. When no inferred transform split occurs, a coded block flag944and948and chroma residual blocks958and962are absent from the encoded bitstream312. When no inferred transform split occurs, the transform skip flag for each chroma channel thus signals the transform skip mode for the corresponding chroma channel in the entirety of the region636.

For the region664, chroma residual samples are transformed using two 8×8 chroma transforms, hence an inferred transform split is present. The coded block flags942and946, if present, signal the presence of 8×8 transforms for each chroma channel of the first 8×8 transform666. The coded block flag944and the coded block flag948, if present, signal the presence of 8×8 transforms for each chroma channel of the second 8×8 transform668. If the value of the coded block flag944is one, the chroma residual block958is present in the encoded bitstream312. If the value of the coded block flag948is one, the chroma residual block962is present in the encoded bitstream312. The transform skip flag966signals the transform skip mode for the chroma residual blocks956and958and the transform skip flag968signals the transform skip mode for the chroma residual blocks960and962. When an inferred transform split is present, the transform skip flag for each chroma channel is thus signalling the transform skip mode for the corresponding chroma channel in the entirety of the region664, in accordance with the behaviour when no inferred transform split is present.

The syntax structure930as illustrated inFIG. 9B, shows the first and second transform of each chroma channel encoded adjacently for the inferred transform split. Other arrangements, such as encoding syntax elements for each chroma channel adjacently, or encoding syntax elements for each chroma channel interspersed with other syntax elements, may alternatively be used.

FIGS. 9C, 9D and 9Eillustrate an alternative syntax structure9100that can be used to encode or otherwise represent a hierarchical level of the transform tree. At non-leaf nodes of a transform tree, the alternative syntax structure9100is expanded recursively in accordance with data structures, such as the data structures700and800, to define the syntax elements present in a portion of the encoded bitstream312corresponding to the transform tree. An instance of the alternative syntax structure9100exists for each node in the transform tree, including the leaf nodes, which each contain a transform unit (TU). Where an ‘inferred split’ occurs to sub-divide the transform unit (TU) for each chroma channel, a syntax structure9130defines syntax elements present in the portion of the encoded bitstream312for the first sub-region resulting from the inferred split (e.g. the top half of a chroma region when a 4:2:2 chroma format is in use or the top-left quarter of a chroma region when a 4:4:4 chroma format is in use). Furthermore, a syntax structure9160defines syntax elements present in the portion of the encoded bitstream312for subsequent sub-regions resulting from the inferred split (e.g. one more sub-region for the lower half of a chroma region when a 4:2:2 chroma format is in use or the remaining three sub-regions of a chroma region when a 4:4:4 chroma format is in use). The notion of a ‘first’ sub-region and a ‘subsequent’ sub-region (e.g. a second and possibly a third or fourth sub-region) is implicit in the scanning order of the sub-regions of a region within a quad-tree. The scanning order is such that the sub-regions are traversed firstly from left to right and secondly from top to bottom. Typically, one data structure for luma and two data structures for chroma are present, although additional data structures are possible, such as for encoding an alpha channel or a depth map. Alternatively, fewer data structures may be utilised, such as in the case where a single data structure is shared by the chroma channels and coded block flag values are able to be shared between the chroma channels. A transform tree syntax structure9102defines the encoding of one hierarchical level of a transform tree, such as the transform tree630.

For an instance of the transform tree syntax structure9102at a non-leaf node of a transform tree, such as the transform tree630, a split transform flag9110encodes a split transform flag value of one, such as the split transform flag value702. This value indicates that the instance of the transform tree syntax structure9102includes a lower hierarchical level, containing additional instances of the transform tree syntax structure9102or ‘child nodes’. A coded block flag9112encodes a coded block flag value in accordance with the description of the coded block flag912. A coded block flag9114encodes a coded block flag value in accordance with the description of the coded block flag914. As a lower hierarchical level exists in the transform tree630(relative to the top hierarchical level), a quad-tree sub-division takes place. This sub-division results in four transform tree syntax structures9116,9118,9120,9122(identified by a ‘blkIdx’ variable numbered from zero to three) being included in the transform tree node syntax structure9102. Each of the transform tree syntax structures9116,9118,9120,9122is another instance of the transform tree syntax structure9102. A coded block flag9124and a luma transform unit portion9126, encoding either residual coefficients for a luma transform or residual samples when the transform is skipped, will be absent from the transform tree syntax structure9102.

Implementations may also arrange the transform tree syntax structure9102such that the coded block flag9124and the luma transform unit portion9126(if present) are placed earlier in the transform tree syntax structure9102, such as in between the coded block flag9114and the transform tree syntax structure9116.

For an instance of the transform tree syntax structure9102at a leaf node of a transform tree, such as the transform tree630, a split transform flag9110encodes a split transform flag value of zero, such as the split transform flag value704. The instance of the transform tree syntax structure9102thus corresponds to a transform unit (TU) in the transform tree930. The transform unit (TU) has a size determined in accordance with the coding unit (CU) containing the transform unit (TU), such as the coding unit (CU)602, and the transform depth. The coded block flag9112encodes a coded block flag value of one to indicate that any of the chroma regions resulting from the inferred split for the ‘U’ chroma channel may have a coded block flag value of one. If the coded block flag9112encodes a value of zero, then the coded block flag value for each chroma region resulting from the inferred split for the ‘U’ chroma channel have a coded block flag value inferred as zero. Even when the code block flag9112encodes a value of one, implementations may still encode a coded block flag having a value of zero for each chroma region resulting from the inferred split. Therefore, implementations may omit the coded block flag9112from the encoded bitstream312, instead always inferred a coded block flag value of one for the omitted coded block flag9112. The coded block flag9114encodes a further coded block flag value for the ‘V’ chroma channel in a similar manner to the coded block flag9112. For transform unit (TU) sizes that accord with those for which an inferred split into four chroma regions occurs (a maximum number of chroma residual coefficient arrays is four), the four transform tree syntax structures9116911891209122(identified by ‘blkIdx’ zero to three) are included in the transform tree node syntax structure9102. For transform unit (TU) sizes that accord with those for which an inferred split into two chroma regions occurs (a maximum number of chroma residual coefficient arrays is two), two transform tree syntax structures, such as transform tree syntax structures91169118(identified by ‘blkIdx’ zero and one) are included in the transform tree node syntax structure9102. Each of the transform tree syntax structures9116911891209122is an instance of a transform tree for chroma syntax structure9132. The coded block flag9124encodes a coded block flag value, such as the coded block flag value708, specifying the presence of absence of a transform for the luma channel of the transform unit (TU). The luma portion of the transform unit9126encodes a luma transform skip flag as transform skip flag9127and a luma residual coefficient array as luma residual syntax elements9128.

The transform tree for chroma syntax structure9132, only existing for the first chroma region (or ‘sub-region’) when an inferred split takes place, includes a reduced set of the syntax of the transform tree syntax structure930. A coded block flag9142encodes a coded block flag value for the ‘U’ chroma channel of the chroma region. A coded block flag9144encodes a coded block flag value for the ‘V’ chroma channel of the chroma region. A chroma portion of the transform unit (TU)9146, encodes a subset of the transform unit (TU) syntax structure952. The chroma portion of the transform unit (TU)9146encodes chroma transforms containing chroma data for a single colour channel. The chroma transforms are encoded in the form of a chroma residual coefficient array as chroma residual syntax elements9150for the ‘U’ chroma channel if the value of the coded block flag9142is one, and a chroma residual coefficient array as chroma residual syntax elements9152for the ‘V’ chroma channel if the value of the coded block flag9144is one (collectively, residual coefficient arrays for the ‘chroma transforms’). A transform skip flag9148is associated with the chroma residual syntax elements9150and encodes a transform skip flag value for the ‘U’ chroma channel, for each chroma region resulting from the inferred split. A transform skip flag9151is associated with the chroma residual syntax elements9152and encodes a transform skip flag value for the ‘V’ chroma channel, for each chroma region resulting from the inferred split. This association is by way of the transform skip flag being encoded in a ‘residual coding’ syntax structure that includes the corresponding residual syntax elements.

The transform tree for chroma syntax structure9162, only existing for chroma regions other than the first chroma region (or ‘sub-region’) when an inferred split takes place, includes a reduced set of the syntax of the transform tree syntax structure930. A coded block flag9172encodes a coded block flag value for the ‘U’ chroma channel of the chroma region. A coded block flag9174encodes a coded block flag value for the ‘V’ chroma channel of the chroma region. A chroma portion of the transform unit (TU)9176, encodes a subset of the transform unit (TU) syntax structure952. The chroma portion of the transform unit (TU)9176encodes a chroma residual coefficient array as chroma residual syntax elements9180for the ‘U’ chroma channel if the value of the coded block flag9172is one. The chroma portion of the transform unit (TU)9176encodes a chroma residual coefficient array as chroma residual syntax elements9182for the ‘V’ chroma channel if the value of the coded block flag9174is one. The transform skip mode for the region corresponding to each chroma residual syntax elements9180is determined from the transform skip flag9148. The transform skip mode for the region corresponding to the region corresponding to each chroma residual syntax elements9182is determined from the transform skip flag9151. Implementations may make use of hardware registers, such as the registers246, or the memory206to store the transform skip flag from the first chroma region for use in the subsequent sub-region(s).

The syntax structures9130and9160as illustrated inFIGS. 9D and 9Eshow the first and second coded block flag encoded adjacently followed by the first and second chroma residual coefficient array of each chroma channel for the inferred transform split. Other arrangements, such as encoding the coded block flag and the chroma residual coefficient array adjacently for each chroma channel may alternatively be used.

Although the inferred transform split is illustrated with the 8×16 region664split into two 8×8 regions, alternative implementations may perform the split for other regions. For example, some implementations may infer a split of a 16×32 region into two 16×16 regions. Such implementations advantageously avoid the need for a 32-point 1D transform in the chroma processing path. Since the 32-point 1D transform is not required for the chroma processing path when the 4:2:0 chroma format is applied, the requirement for the 32-point 1D transform is entirely removed from the chroma processing path. Implementations that use separate processing circuitry to decouple the luma and chroma channels may thus achieve a lower implementation cost in the chroma processing circuitry.

A 4:4:4 chroma format exists where there is one chroma sample location for each luma sample location. Accordingly, with this format, transforms for the chroma channel and the luma channel may have the same sizes. With a largest transform size of 32×32 in the luma processing path, this would require introducing a 32×32 transform into the chroma processing path for a decoupled implementation. Specific implementations may infer a split for each chroma channel to split a 32×32 region into four 16×16 regions, enabling reuse of the existing 16×16 transform in the chroma processing path. Since a 32×32 transform would only be used in the chroma processing path for the 4:4:4 chroma format, inferring a split for each chroma channel to split a 32×32 region into four 16×16 regions would enable the 32×32 transform to be removed from the chroma processing path, reducing the processing circuitry required. Such implementations would require four coded block flag values for each chroma channel, and thus up to four coded block flags coded in the syntax structure930for each chroma channel in the encoded bitstream312.

Implementations supporting a 4:2:2 chroma format may also infer a split for each chroma channel to split a 32×16 region into four 8×16 regions. Such implementations require four coded block flag values for each chroma channel, and thus four coded block flags coded in the syntax structure930for each chroma channel in the encoded bitstream312, thus a ‘CU3’, ‘CU4’, ‘CV3’ and ‘CV4’ coded block flag (not illustrated inFIG. 9B) may be introduced in the transform unit (TU) syntax structure952. Such implementations avoid introducing 32-point transform logic into the chroma processing path and, where 8×16 regions are not sub-divided, may reuse 8×16 transform logic required for transform units (TUs) of size 16×16 (in the luma channel) that require transforming transform of size 8×16 for the chroma channels.

FIG. 10is a schematic flow diagram showing a method1000for encoding a transform unit (TU) by encoding the transform tree non-leaf node syntax structure902and the transform tree leaf node syntax structure932. The method1000is described with reference to a chroma channel of the transform unit (TU) however the method1000may be applied to any chroma channel of the transform unit (TU). As the transform tree non-leaf node syntax structure902and the transform tree leaf node syntax structure932describe one node in the transform tree, the method1000encodes one node of the transform tree into the encoded bitstream312. The method1000may be implemented in hardware or by software executable on the processor205, for example. The method1000is initially invoked for the top level of the transform tree and is capable of invoking itself (recursively) to encode child nodes of the transform tree. A determine transform unit size step1002determines the size of a transform unit (TU) in a transform tree according to the coding unit (CU) size that contains the transform tree and a transform depth value of the transform unit (TU). When the method1000is invoked at the top level of the transform tree, the transform depth value is set to zero, otherwise the transform depth value is provided by the parent instance of the method1000. A split transform flag value, such as the split transform flag value702is encoded in the encoded bitstream312as split transform flag910if the transform depth value is less than the maximum allowed transform depth.

When the split transform flag value is one, chroma coded block flags912and914are encoded for each chroma channel only if the parent node of the transform tree hierarchy has a corresponding coded block flag value of one. The method1000then invokes a new instance of the method1000for each child node (represented in the portion of the encoded bitstream312by transform tree syntax structures916,918,920and922) of the transform tree. Each instance of the method1000, invoked for the child nodes, is provided with a transform depth value equal to the present method1000instance transform depth value incremented by one.

When the split transform flag value is zero, an identify maximum number of forward transforms step1004determines a maximum number (n) of transforms for each chroma channel of the region being encoded. When no inferred split takes place, this number n will be one. When a 4:2:2 chroma format is in use and a rectangular region of a chroma channel, such as the 8×16 region664, is encountered and the region size is one of a predetermined set of region sizes (such as 16×32 and 8×16), an inferred split takes place and the maximum number of transforms will be two (otherwise the number of transforms will be one). Otherwise (the region size is not one of a predetermined set of region sizes) the maximum number of transforms will be one. For example, if 4×8 is not one of the predetermined set of region sizes, then the maximum number of transforms will be one. When a 4:4:4 chroma format is in use and the encountered region size is one of a predetermined set of region sizes (such as a 32×32 region), an inferred split takes place and the maximum number of transforms will be four. Otherwise (the region size is not one of a predetermined set of region sizes) the maximum number will be one. For example, if 8×8 is not one of the predetermined set of region sizes, then the maximum number of transforms will be one. Although the predetermined set of region sizes includes 8×16, other predetermined set of region sizes are possible, such as only 16×32 when a 4:2:2 chroma format is in use or 32×32 when a 4:4:4 chroma format is in use.

For each chroma channel, if the parent node had a coded block flag value of one, then for each of n, a coded block flag is encoded in the encoded bitstream312. For example, when the number of transforms is equal to two, coded block flags942and944indicate the presence of a transform for each of the two regions inferred by the split. A select forward transform step1006selects a forward transform from a predetermined set of forward transforms, for each of the maximum number of transforms, based on a transform unit (TU) size, which is in turn dependent on the transform depth, and thus related to a hierarchical level of the transform unit in the largest coding unit. When the transform depth is equal to zero, the transform unit (TU) size is equal to the coding unit (CU) size. For each increment of the transform depth, the transform unit (TU) size is halved. For a 32×32 coding unit (CU) size, a transform depth of zero and using a 4:2:2 chroma format, the transform unit (TU) size will thus be 32×32 and the transform size for chroma will thus be 16×32. For example, when the maximum number of transforms is two and the region size for chroma is 16×32, then a 16×16 forward transform is selected for each of the 16×16 regions for chroma resulting from the inferred split.

An apply forward transform step1008performs the forward transform for each of the maximum number of transforms on the corresponding region that has a coded block flag value of one. The encode chroma residual sample arrays step1008is generally performed by the transform module320. This results in a conversion of each chroma residual sample array (spatial domain representation) into a chroma residual coefficient array (frequency domain representation).

An encode chroma residual coefficient arrays step1010encodes the chroma residual coefficient array for each of the maximum number of transform regions of each chroma channel having a coded block flag value of one into the encoded bitstream312. The number of chroma residual coefficient arrays encoded for a given transform unit for a given chroma channel depends on the coded block flag value of each transform and will thus vary from zero to (at most) the maximum number of transforms. For example, when the number of transforms is two and both chroma channels have coded block flag values of one for each of the count values, then the chroma residual blocks956,958,960and962are encoded in the encoded bitstream312. If the coded block flag value for each transform for a given chroma channel is zero, then no chroma residual block is encoded in the encoded bitstream312for that chroma channel. The encode chroma residual coefficient arrays step1010is generally performed by the entropy encoder324.

FIG. 11is a schematic flow diagram showing a method1100for decoding a transform unit (TU) by decoding the transform tree non-leaf node syntax structure902and the transform tree leaf node syntax structure932. The method1100is described with reference to a chroma channel of the transform unit (TU) however the method1100may be applied to any chroma channel of the transform unit (TU). As the transform tree non-leaf node syntax structure902and the transform tree leaf node syntax structure932describe one node in the transform tree, the method1100decodes one node of the transform tree from the encoded bitstream312. The method1100may be performed in appropriate hardware or alternatively in software, for example executable by the processor205. The method1100is initially invoked for the top level of the transform tree and is capable of invoking itself (recursively) to decode child nodes of the transform tree. A determine transform unit (TU) size step1102determines a transform unit (TU) size in a manner identical to the determine transform unit size step1002. The determine transform unit size step1102determines the size of a transform unit (TU) in a transform tree according to the coding unit (CU) size that contains the transform tree and a transform depth value of the transform unit (TU). When the method1100is invoked at the top level of the transform tree, the transform depth value is set to zero, otherwise the transform depth value is provided by the parent instance of the method1100. A split transform flag value, such as the split transform flag value702is decoded from the encoded bitstream312as split transform flag910if the transform depth value is less than the maximum allowed transform depth.

When the split transform flag value is one, chroma coded block flags912and914are decoded for each chroma channel only if the parent node of the transform tree hierarchy has a corresponding coded block flag value of one. The method1100then invokes a new instance of the method1100for each child node (represented in the portion of the encoded bitstream312by transform tree syntax structures916,918,920and922) of the transform tree. Each instance of the method1100, invoked for the child nodes, is provided with a transform depth value equal to the present method1100instance transform depth value incremented by one.

When the split transform flag value is zero, an identify maximum number of inverse transforms step1104determines a (maximum) number (n) of transforms for each of the at least one chroma residual coefficient arrays present in each chroma channel of the region being decoded, in a manner identical to the identify maximum number (n) of forward transforms step1004. When no inferred split takes place, this number n will be one. When a 4:2:2 chroma format is in use and a rectangular region of a chroma channel, such as the 8×16 region664, is encountered and the region size is one of a predetermined set of region sizes (such as 16×32 and 8×16), an inferred split takes place and the maximum number of transforms will be two (otherwise the number of transforms will be one). Otherwise (the region size is not one of a predetermined set of region sizes) the maximum number of transforms will be one. For example, if 4×8 is not one of the predetermined set of region sizes, then the maximum number of transforms will be one. When a 4:4:4 chroma format is in use and the encountered region size is one of a predetermined set of region sizes (such as a 32×32 region), an inferred split takes place and the maximum number of transforms will be four. Otherwise (the region size is not one of a predetermined set of region sizes) the maximum number will be one. For example, if 8×8 is not one of the predetermined set of region sizes, then the maximum number of transforms will be one. Although the predetermined set of region sizes includes 8×16, other predetermined set of region sizes are possible, such as only 16×32 when a 4:2:2 chroma format is in use or 32×32 when a 4:4:4 chroma format is in use. For each chroma channel, if the parent node had a coded block flag value of one, then for each of the (n) transforms, a coded block flag is decoded in the encoded bitstream312. For example, when the maximum number of transforms is equal to two, coded block flags942and944indicate the presence of a transform for each of the two regions inferred by the split.

A decode chroma residual coefficient arrays step1106then decodes the residual coefficient array for each of the maximum number of transforms regions of each chroma channel from the encoded bitstream312having a coded block flag value of one. The number of residual coefficient arrays decoded for a given transform unit for a given chroma channel depends on the coded block flag value of each transform and will thus vary from zero to (at most) the ‘number (n) of transforms’. For example, when the number of transforms is two and both chroma channels have coded block flags of one for each of the count values, then the chroma residual blocks956,958,960and962are decoded from the encoded bitstream312. The decode chroma residual coefficient arrays step1106is generally performed by the entropy decoder420for each chroma residual coefficient array having a coded block flag value of one.

A select inverse transform step1108then selects an inverse transform from a predetermined set of inverse transforms, for each of the maximum number of transforms having a coded block flag value of one for each chroma channel. For example, when the maximum number of transforms is two and the region size is 16×32 and the coded block flag value for each of the two transforms is one, then a 16×16 inverse transform is selected for each of the 16×16 regions resulting from the inferred split.

An apply inverse transform step1110then performs the inverse transform for each of the maximum number of transforms regions on the corresponding region having a coded block flag value of one. This results in a conversion of each chroma residual coefficient array (frequency domain representation) into a chroma residual sample array (spatial domain representation) representative of the decoded video frame. The apply inverse transform step1110is generally performed by the inverse scale and transform module422.

FIG. 12Ashows a diagonal scan pattern1201,FIG. 12Bshows a horizontal scan pattern1202, andFIG. 12Cshows a vertical scan pattern1203, each for a 4×8 transform unit1200. Those implementations that scan the 4×8 transform unit1200using the illustrated scan patterns have the property that the residual coefficients are grouped in 4×4 blocks, known as ‘sub-blocks’. A ‘coefficient group’ flag present in the encoded bitstream312may therefore be used to indicate, for each sub-block, the presence of at least one significant (non-zero) residual coefficient. Applying a 4×4 sub-block size for the 4×8 transform achieves consistency with the scan pattern present in other transform sizes, where coefficients are always grouped into sub-blocks.

Particular implementations may apply a coefficient group flag to signal the presence of at least one non-zero residual coefficient in each sub-block. Advantageously, these scan patterns permit re-use of control software or digital circuitry that processes residual coefficients, by reusing the sub-block processing for all transform sizes. The particular scan pattern used may be selected according to criteria such as the intra-prediction direction of the collocated prediction unit (PU). Where a transform encodes chroma samples on a 4:2:2 chroma format sample grid, the relationship between the intra-prediction direction and the scan pattern is altered because each chroma sample maps to a non-square (2×1) array of luma samples, affecting the ‘direction’ or angle of the intra-prediction mode. Scanning is shown in a ‘backward’ direction inFIGS. 12A to 12C, ending at the DC coefficient, located in the top-left corner of the transform unit (TU). Further, scanning is not required to start at the lower-right corner of the transform unit (TU). Due to the predominance of nonzero residual coefficients in the upper left region of the transform unit (TU), scanning may begin from a ‘last significant coefficient position’ and progress in a backward direction until the upper left coefficient is reached.

Other implementations may apply a single scan to a given region to encode residual coefficients and then apply more than one transform to these residual coefficients. In this case only one coded block flag is used for the region and therefore for all transforms covered by the scan pattern. The coded block flag is set to one if at least one significant residual coefficient exists in any of the scans. For example, the 4×8 scan patterns ofFIGS. 12A-12Cmay be applied to encode residual coefficients of two 4×4 transforms. The two 4×4 arrays of residual coefficients may be concatenated to form a 4×8 array suitable for the scan pattern. As a single scan is performed over the array, a single ‘last significant coefficient’ position is encoded in the bitstream for the scan pattern and a single coded block flag value is sufficient for the array. The energy compaction property of the modified discrete cosine transform (DCT) gives advantage to other schemes, such as interleaving the coefficients of each square transform along the path of the scan pattern into the rectangular coefficient array. This gives the advantage the density of residual coefficient values in each 4×4 residual coefficient array is approximately equalised in the combined 4×8 array, allowing higher compression efficiency to be created by the entropy encoder324, for subsequent decoding by the entropy decoder420.

Certain implementations encoding chroma colour channels may use a first transform to encode residual samples at chroma sample locations corresponding to a 4:2:0 chroma sample grid and a second transform to encode residual samples at the additional chroma sample locations introduced in the 4:2:2 chroma sample grid, relative to the 4:2:0 chroma sample grid. Such implementations may advantageously use a simplified transform for the second transform, such as a Hadamard transform with the output of the second transform being added (or otherwise combined) to the residual samples for the first transform to produce the residual samples for the second transform. Advantageously a preprocessing stage implementing a transform such as a Haar transform may be used to sample the chroma sample grid for a 4:2:2 chroma format into the chroma sample grid for a 4:2:0 chroma format. Such configurations must transmit additional residual coefficients from the preprocessing stage as side-information, such a residual applied to each largest coding unit (LCU) in the case that the preprocessing transform is applied at the largest coding unit (LCU) level.

Implementations having multiple transforms for a given region may use either a single combined scan covering the entire region, or a separate scan for each transform. If the scanning for the multiple transforms is combined into a single scan, then only one coded block flag is required for each region being scanned. Those implementations using a single combined scan may achieve higher compression of the residual coefficients by interleaving the residual coefficients of each transform, such as interleaving on a coefficient-by-coefficient basis, in order to collocate residual coefficients from each transform having similar spectral properties.

FIG. 13is a schematic block diagram showing a method1300of encoding a transform unit. The method1300, performed by the video encoder114, encodes the luma channel and a chroma channel of the transform unit. In a determine luma transform skip flag value step1302, the transform skip control module346determines the value of a transform skip flag, such as the transform skip flag964or9127, for the luma channel, typically by testing the cost of coding the residual sample array360in both the spatial domain (transform skip is performed) and in the frequency domain (transform skip is not performed). In a determine chroma transform skip flag value step1304, the transform skip control module346determines or otherwise sets the value of a transform skip flag, such as the transform skip flag966or9148, for one of the chroma channels to be applied to all of the sub-regions resulting from an inferred split and belonging to the same chroma channel. The transform skip control module346may apply similar logic as for the luma channel, however the bit-rate cost determination must account for each of the chroma residual sample arrays resulting from the inferred split when determining the cost of either performing the transform skip for all chroma residual sample arrays in the chroma channel (or ‘colour channel’) or performing the transform skip for none of the chroma residual sample arrays in the chroma channel. The determine chroma transform skip flag value step1304is repeated for each chroma channel, determining transform skip flag values for other chroma channels, such as transform skip flags968or9151. The encode luma transform and chroma transform step1306encodes the luma residual sample array in the encoded bitstream312using the entropy encoder324and encodes the chroma residual sample arrays for a chroma channel in the encoded bitstream312using the entropy encoder324. The luma residual sample array is determined in accordance with the luma transform skip flag, either by transforming in the transform module320the residual sample array into a residual coefficient array or bypassing the transform module320when a transform skip is performed by the video encoder114. Subsequently the residual array363is passed to the scale and quantise module322to create the residual data array364. When at least one of the values in the residual data array364is non-zero, the values of the residual data array364are encoded into the encoded bitstream312by the entropy encoder324(in a block of residual data, such as residual data block954,956,958,960or962) and the corresponding coded block flag is set to one. The chroma residual sample arrays are determined similarly to the luma residual sample arrays, except that chroma residual sample arrays other than the first share the transform skip flag with the first chroma residual sample array. The encoding of chroma residual sample arrays in the step1306is repeated for each chroma channel.

FIG. 14is a schematic flow diagram showing a method1400for decoding a transform unit. The method1400, performed by the video decoder134, decodes the luma channel and a chroma channel of the transform unit. A determine luma transform skip flag value step1402determines the value of a transform skip flag for the luma channel by decoding a transform skip flag, such as the transform skip flag964or9127, from the encoded bitstream312using the entropy decoder420. A determine chroma transform skip flag value step1404determines the value of a transform skip flag for one of the chroma residual sample arrays within a chroma channel to be applied to all chroma residual sample arrays within the chroma channel and in the same transform unit (TU). The step1404decodes a transform skip flag, such as the transform skip flag966or9148, from the encoded bitstream312using the entropy decoder420. Implementations that associate the transform skip flag with the first chroma residual sample array avoid the need to buffer earlier residual sample arrays before determining the transform skip flag from a later residual coefficient array (which would then be used to continue processing the earlier residual sample array, thus introducing additional internal buffering). The step1404may also determine a transform skip flag for additional chroma channels, such as by decoding the transform skip flag968or9151from the encoded bitstream312using the entropy decoder420. A decode luma transform and chroma transform step1406causes the entropy decoder420to decode a luma residual coefficient array, such as the luma residual data block954, when a corresponding coded block flag is one, such as the coded block flag950, and the chroma residual coefficient arrays associated with a particular chroma channel, such as the chroma residual coefficient arrays956and958, when each corresponding coded block flag, such as the coded block flags942and944, are one. When decoding a luma transform, the luma residual coefficient array is only passed through the inverse transform module422if a transform skip is not performed, otherwise the luma residual coefficient array bypasses the inverse transform module422. When decoding a chroma transform, for each chroma residual sample array in the transform unit, the transform skip flag present in the encoded bitstream312and associated with the first chroma residual sample array is applied.

The description of the methods1300and1400refer to a ‘transform unit’ that may contain multiple chroma residual sample arrays for a given chroma channel, when an inferred split takes place. This accords with the syntax structure930. When the syntax structures9100,9130and9160are in use, each chroma region resulting from an inferred split is illustrated as a separate transform unit (TU), marked as chroma transform units (CTUs) inFIGS. 9C, 9D and 9E. For the purposes of the methods1300and1400, the chroma transform units (CTUs) are merely an artefact of using the transform tree syntax structure9100to split the chroma regions. InFIG. 9C, the spatial region occupied by the luma transform unit (LTU)9126may be considered the ‘transform unit’ as it occupies the same spatial region as the transform unit952. The chroma transform units (CTUs)91169118and9120-9122(if present) may be considered as chroma sub-regions resulting from the inferred split.

Advantageously, both the methods1300and1400result in one transform skip flag being encoded for each colour channel, regardless of the presence or absence of an inferred split operation (which may be applicable when the 4:2:2 and the 4:4:4 chroma formats are in use). This characteristic results in consistent behaviour with the 4:2:0 chroma format, where one transform skip flag is present for each residual coefficient array, and only one residual coefficient array is present for each colour channel for a given transform unit. For example, an 8×8 transform unit in 4:2:0 would have an 8×8 transform for luma and a 4×4 chroma transform for each chroma channel. One transform skip flag would be present for each chroma channel in this case. In the 4:2:2 case, with an inferred split, two 4×4 chroma transforms would be present in each chroma channel. A transform skip flag coded with the first 4×4 chroma transform but applied to both 4×4 chroma transforms would control the transform skip status for the same spatial region as for the 4:2:0 case. This consistent behaviour results in the transform skip handling for 4:2:2 that is backward compatible with the 4:2:0 case (i.e. no rearrangement of syntax elements occurs in 4:2:0 due to supporting transform skip in 4:2:2). Having a common transform skip for all chroma results in an inferred split that avoids artificially dividing a transform unit into an upper half and a lower half for the purposes of specifying the transform skip.

FIG. 15is a schematic representation showing possible arrangements of 4×4 transforms in a 4×4 and an 8×8 transform unit, for the video encoder114and the video decoder134. The colour channels, Y, U and V are depicted inFIG. 15in columns and three cases are depicted along rows. In all depicted cases the video encoder114and the video decoder134are configured to use a 4:2:2 chroma format. Also, in all cases, the video encoder114and the video decoder134support an inferred split of the 4×8 chroma region into two 4×4 chroma regions, and thus two 4×4 chroma transforms are depicted for each colour channel. The three cases depicted are:

Case 2: four 4×4 transform units (TUs) with a first ordering (order 1) of the transforms (middle row); and

Case 3: four 4×4 transform units (TUs) with a second ordering (order 2) of the transforms (lower row).

For each case, the transforms are numbered in the order in which they appear in the encoded bitstream312. Case 1 shows a transform unit (TU) with an 8×8 luma transform and two 4×4 transforms, for each chroma channel. The luma transform does not have a transform skip flag as the luma transform is 8×8. Cases 2 and 3 further illustrate the case where the four 4×4 transforms units result in chroma regions for each chroma transform that span multiple transform units (TUs). In Cases 2 and 3, the four transform units (TUs) are numbered from zero to three and indexed with a ‘blkIdx’ variable, as used in the high efficiency video coding (HEVC) standard under development. For each transform depicted inFIG. 15, if a transform skip is supported, a box is included in the upper-left corner of the transform. For transforms where the transform skip flag is always explicitly coded, the box is shaded (such as shaded box1502). An unshaded box (such as unshaded box1504) illustrates the case where the transform skip flag for the present transform is derived from an earlier (such as an above transform). Implementations which do not support this derivation will explicitly code a transform skip flag in the encoded bitstream312for transforms with unshaded boxes. In Case 2 and Case 3, a transform unit syntax structure, such as the transform unit syntax structure952, is invoked four times (with the value for ‘blkIdx’ incrementing from zero to three), once for each 4×4 transform unit. Thus four instances of the transform unit syntax structure are present in the encoded bitstream312. On each invocation, a luma residual block, such as the luma residual data block954, is present in the encoded bitstream312if a corresponding coded block flag, such as the coded block flag950, has a value of one. In Case 2, on the fourth invocation (‘blkIdx’ is equal to three), chroma residual blocks for the chroma channels, such as the chroma residual blocks956,958,960,962, are coded in the encoded bitstream312(if corresponding coded block flags, such as the coded block flags942,944,946,948have a value of one). The ordering of the luma and chroma residual blocks fromFIG. 9Bcorresponds to the ordering of transforms presented in Case 2. In Case 3, the ordering is changed due to the following: Chroma residual blocks for the upper half (such as the chroma residual blocks956,960) are processed on the second invocation of the transform unit syntax structure (i.e. when ‘blkIdx’ is equal to one) and chroma residual blocks for the lower half (such as the chroma residual blocks958,962) are processed on the fourth invocation of the transform unit syntax structure (i.e. when ‘blkIdx’ is equal to three).

Another case, not illustrated inFIG. 15, is that of a 4×4 transform unit when the 4:2:0 chroma format is in use, where one 4×4 transform for chroma is applied to the area on the chroma sample grid that corresponds to the four 4×4 transform units for luma at the same quad-tree hierarchical level (collectively occupying an 8×8 region on the luma sample grid). When a 4×8 transform is available in chroma, transform skip for the 4:2:2 case is applied to the 4×8 transform (in addition to the 4×4 transform), as described with reference toFIG. 18below. When a 4×8 transform is not available in chroma and the 4:2:2 chroma format is in use, implementations must use two 4×4 transform for each chroma channel and may code the transform skip flag for one 4×4 transform, such as the upper 4×4 transform, but apply the coded transform skip flag for both 4×4 transform for the given chroma channel.

FIG. 17is a schematic flow diagram showing a method1700for decoding residual data for a transform unit (TU), elaborating upon aspects of the method1400ofFIG. 14. The method1700determines a transform skip flag for a given region and decodes the residual data for the region. When the method1700is invoked for the luma channel of a transform unit (TU), only one region exists. For a single chroma channel of a transform unit (TU) and when an inferred split occurs, two regions are present and the method1700is invoked for each region having a coded block flag value of one. The method1700begins with a transform skip supported test step1702. The step1702tests a transform skip enabled flag and a coding unit transform quantisation bypass flag and the transform size for the present region. The transform skip enabled flag, encoded in the encoded bitstream312, indicates if the transform skip function is available in the encoded bitstream312. The coding unit transform quantisation bypass flag, encoded in the encoded bitstream312, indicates if a ‘lossless’ coding mode was selected by the video encoder114, whereby both the transform320and the quantisation modules322are bypassed, and thus the video encoder114operates in a lossless mode, allowing the video decoder134to exactly reproduce captured frame data from the video source112. The transform size for the present region, indicated by a ‘log 2TrafoSize’ variable in the high efficiency video coding (HEVC) standard under development, which is defined as the log 2 of the side dimension of a square transform. When transform skip flag is true (i.e. enabled) and coding unit transform quantisation bypass flag is false (i.e. not enabled) and the transform size is 4×4 (i.e. log 2TrafoSize is equal to 2), control passes to a first true coded block flag (CBF) region in a colour channel test step1704, otherwise control passes to a decode residual data step1712. The test step1704determines if the present region is the first region in the colour channel (and in the transform unit (TU) to have a coded block flag (CBF) value of one). As the method1700is only invoked if the value of the coded block flag for the present region is one, two cases are possible. If the method1700is invoked for the first chroma region (the upper region when a 4:2:2 chroma format is in use, e.g. the region682or666inFIG. 6C) of an inferred split, then the test step1704evaluates as true and control passes to a decode transform skip flag step1706. If the method1700is invoked for the subsequent chroma region(s) of an inferred split (the lower region when a 4:2:2 chroma format is in use, e.g. the region684or668inFIG. 6C), the test step1704evaluates as false when the method1700was previously invoked for the first chroma region (for the present transform unit) and true when the method1700was not previously invoked for the first chroma region (for the present transform unit). When the test step1704evaluates as true, control passes to a decode transform skip flag step1706. In the step1706, the entropy decoder420decodes a transform skip flag from the encoded bitstream312to determine a transform skip flag value. A store transform skip flag value step1708stores the transform skip flag value in memory, such as hardware registers or registers246, for later use on subsequent invocations of the method1700. If the test step1704evaluates as false, control passes to a retrieve transform skip flag value step1710, where the transform skip flag value, determined and stored on a previous invocation of the method1700, is retrieve from memory, such as hardware registers or registers246. At a decode residual data step1712, a block of residual data, such as residual data block954,956,958,960or962is decoded from the encoded bitstream312by the entropy decoder420. The determined transform skip flag value is passed as the transform skip flag value468to control the transform skip operation, as described above with reference to the multiplexer423. The steps1702-1710correspond to the step1402ofFIG. 14when the method1700is invoked for the luma channel, and the steps1702-1710correspond to the step1404ofFIG. 14when the method1700is invoked for a chroma channel. The decode residual data step1712corresponds to the luma residual decoding of the step1406ofFIG. 14and the chroma residual decoding of the step1406ofFIG. 14. The method1700also corresponds to a ‘residual coding’ syntax structure, as defined in the high efficiency video coding (HEVC) standard under development.

FIG. 18is a schematic representation1800showing a transform skip operation applied to a 4×8 chroma region (with a 4×8 non-square transform) for each colour channel. The luma channel (‘Y’) and each chroma channel (‘U’ and ‘V’) are depicted inFIG. 18. Two cases are depicted inFIG. 18:

Case 1: ‘8×8 TU’ (the upper row ofFIG. 18) depicts an 8×8 transform unit (TU), with an 8×8 transform1802for the luma channel and a 4×8 (non-square or rectangular) transform1804for each chroma channel. A transform skip flag is depicted with a shaded box in the upper right corner of a transform for which the transform skip operation is supported. In this case, the transform skip operation is also supported in the 4×8 transform case (in addition to the 4×4 transform case) and thus the 4×8 transforms each include a transform skip flag1806, as illustrated inFIG. 18.

Case 2: ‘Four 4×4 TUs’ (the lower row ofFIG. 18) depicts four 4×4 transform units (TUs), with four 4×4 transforms1808for the luma channel and a 4×8 (non-square or rectangular) transform1810for each chroma channel. The 4×8 transform for each chroma channel is collocated (on the chroma sample grid) with the luma transform (on the luma sample grid) and shared among the four 4×4 transform units (TUs). In this implementation, the transform skip operation is also supported in the 4×8 transform case (in addition to the 4×4 transform case) and thus the 4×8 transforms include a transform skip flag1812, as illustrated inFIG. 18.

For an implementation supporting Cases 1 and 2 ofFIG. 18, a modified test step1702and steps1706and1712of the method1700are performed by the video decoder134. The modified test step1702operates as the test step1702ofFIG. 17, except that a transform size of 4×8 is included (in addition to a transform size 4×4) as a possible transform size for which a transform skip operation is supported, thus allowing the modified test step1702to evaluate as true in both the 4×4 and 4×8 transform cases.

Appendix A illustrates possible ‘text’ for the high efficiency video coding (HEVC) standard under development that is relevant to the syntax structure900and the syntax structure930. Each instance of a transform_tree( ) function in appendix A is depicted as a portion of the syntax structure labelled ‘TT’ inFIGS. 9A and 9Cand each instance of a transform_unit( ) function in Appendix A is depicted as a portion of the syntax structure labelled ‘TU’ inFIGS. 9A and 9B. The text provided in Appendix A is one example of text that accords with the syntax structures900and930and other examples are possible. Text that accords with the syntax structures900and930implies that the video encoder114performs the method1000to encode a bitstream and the video decoder134performs the method1100to decode the bitstream.

Appendix B illustrates possible text for the high efficiency video coding (HEVC) standard under development that is relevant to the syntax structure9100and the syntax structure9130. Each instance of a transform_tree( ) function in appendix B is depicted as a portion of the syntax structure labelled ‘TT’ inFIGS. 9C, 9D and 9Eand each instance of a transform_unit( ) function in appendix A is depicted as a portion of the syntax structure labelled ‘TU’ inFIGS. 9C, 9D and 9E. The text provided in Appendix B is one example of text that accords with the syntax structures9100and9130and other examples are possible. Text that accords with the syntax structures9100and9130also implies that the video encoder114performs the method1000to encode a bitstream and the video decoder134performs the method1100to decode the bitstream.

The text in Appendix A and Appendix B result in an implementation whereby the 32×32 chroma region encountered in a transform unit (TU) of size 32×32 configured for the 4:4:4 chroma format results in (a maximum number of) four 16×16 chroma transforms being applied, and the 16×32 chroma region encountered in a transform unit (TU) of size 32×32 configured for the 4:2:2 chroma format results in (a maximum number of) two 16×16 chroma transforms being applied. The implementation resulting from the text in Appendix A and Appendix B, when applied to transform units (Ms) of smaller size and configured for the 4:2:2 chroma format, (a maximum of) one chroma transforms is applied. For example, an 8×16 transform is applied to an 8×16 chroma region and a 4×8 transform is applied to a 4×8 chroma region.

INDUSTRIAL APPLICABILITY

The arrangements described are applicable to the computer and data processing industries and particularly for the digital signal processing for the encoding a decoding of signals such as video signals.

(Australia only) In the context of this specification, the word “comprising” means “including principally but not necessarily solely” or “having” or “including”, and not “consisting only of”. Variations of the word “comprising”, such as “comprise” and “comprises” have correspondingly varied meanings.

APPENDIX A

Transform_Tree( ) and Transform_Unit( ) Implement the Inferred Chroma Split Using a Loop Construct

APPENDIX B

Invoke Transform_Tree( ) Once Per Pair of Chroma Channels for Each Chroma Transform Resulting from the Inferred Split