Techniques for video encoding and decoding

Video encoding and decoding technology

This application claims the priority of the U.S. Provisional Application Serial No. 60/390,101 filed on June 18, 2002, entitled "Method for Reducing Power Consumption in Video Motion Estimation System", which has been assigned to the assignee of this application It is incorporated herein by reference in its entirety for various purposes.

Related Application This application relates to a joint pending patent application with serial number 10/371,768 (file number 020127) filed on the same day, entitled "Video Encoding and Decoding Technology". This application further relates to a joint pending patent application with serial number 10/139,772 (file number 020086) filed on May 3, 2002, entitled "Video Coding Technology". Both of the above applications are assigned to the assignee of this application.

Technical field

The present invention relates to digital video processing, in particular to the coding of video sequences.

Background Digital video functions can be combined with a wide range of devices, including digital televisions, digital direct broadcasting systems, wireless communication devices, personal digital assistants (PDAs), laptop computers, desktop computers, digital cameras, digital recording devices, Cellular or satellite radio phones and so on. Compared with traditional analog video systems, digital video devices have made important improvements in the production, correction, transmission, storage, recording, and playback of complete motion video sequences.

Many different video coding standards have been established to encode digital video sequences. For example, the Moving Picture Experts Group (MPEG) has developed many standards, including MPEG-1, MPEG-2 and MPEG-4. Other standards include ITU H.263, QuicktimeTM technology developed by Apple Computer of Cupertino, California, WindowsTM video developed by Microsoft Corporation of Redmond, Washington, IndeoTM developed by Intel Corporation, RealvideoTM and SuperMac developed by RealNetworks, Seattle, Washington. CinepakTM developed by the company.

Many video coding standards increase the transfer rate by encoding data in a compressed form. Compression can reduce the total amount of data that needs to be transmitted in order to efficiently transmit video frames. For example, the MPEG standard uses graphics and video compression techniques to transmit video and graphics on a narrower bandwidth than uncompressed.

For example, the MPEG standard supports video coding technology, which uses the similarity between consecutive video frames (called time or inter-frame correlation) to complete inter-frame compression. The inter-frame compression technology takes advantage of the data redundancy that runs through multiple frames by converting the pixel-based display of the video frame into a motion display. In addition, video coding techniques can use similarities within frames (referred to as spatial or intra-frame correlation) to further compress video frames. Intra-frame compression is usually based on texture coding that compresses still images, such as discrete cosine transform (DCT) coding.

To support compression, digital video devices usually include an encoder for compressing digital video sequences and a decoder for decompressing digital video sequences. In many cases, the encoder and decoder form an integrated codec (CODEC) that operates on blocks of pixels within frames that define a sequence of video images. For example, in the MPEG-4 standard, the encoder divides the video frame to be transmitted into macroblocks including a 16×16 pixel array.

For each macro block in a video frame, the encoder searches for the closest macro block of the previous video frame (or the next frame) to identify the most similar macro block, encodes the difference between these macro blocks, and performs Transmission, while transmitting the motion vector, the motion vector indicates which macroblock in the previous frame was used for encoding. The decoder receives the motion vector and the encoded difference value, and performs motion compensation to create a video sequence.

The video encoding process has considerable computational intensity, especially when using motion estimation techniques. For example, the process of comparing a video block to be encoded with a video block of a previously transmitted frame requires a lot of calculations. There is an urgent need for an improved encoding technology, especially for wireless devices or other portable video devices with more limited computing resources and power consumption issues. At the same time, improved compression is needed to reduce the bandwidth required to efficiently transmit video sequences. Improving one or more of these factors can facilitate or improve the real-time encoding of video sequences, especially in wireless and other bandwidth-limited settings.

Summary of the invention

This application describes a video encoding technology that can reduce the processing cycle and the number of storage transfers necessary for encoding a video sequence. In this way, the disclosed video encoding technology can speed up video encoding and reduce power consumption. In addition, this technique can use the same calculation group to define the difference values related to the macroblock to be coded, and to define the difference values related to the various macroblocks forming the macroblock to be coded.

The video coding technique described here can use a candidate memory, which stores the search space of the motion estimation program in a columnar form. The memory control unit can address the candidate memory to retrieve multiple pixels in parallel for simultaneous comparison with the pixels of the video block to be encoded, for example, using the sum of absolute difference (SAD) or the sum of square difference (SSD) technology. A difference processor can perform parallel calculations. Each group of parallel calculations can correspond to a row in a micro block forming a macro block. In addition, for subsequent video blocks to be encoded, the candidate memory can be gradually updated by loading a new list of video blocks instead of reloading the entire search space.

These or other technologies described herein can be implemented in a digital video device in hardware, software, firmware, or any combination thereof. If implemented in software, this technology can be cited on a computer-readable medium including program code, and when executed, one or more encoding techniques described herein are executed. Other details of various embodiments are given in the drawings and the following description. Other features, purposes and advantages will be revealed from the description, drawings and claims.

Description of the drawings

Figure 1 is a block diagram illustrating an example system in which a source digital video device transmits an encoded video data sequence to a receiving digital video device.

Figure 2 is a block diagram illustrating a video encoder that encodes a digital video sequence.

Figure 3 is a conceptual illustration of an example video data macroblock.

Figure 4 is a conceptual illustration of an example search space.

Figure 5 is a conceptual illustration of macroblocks to be coded. The macroblocks are conceptually placed on a search space arranged in a macroblock array.

Fig. 6A is a diagram illustrating the macroblock pixel index.

Fig. 6B is a diagram illustrating the arrangement of video data in the video memory.

Fig. 6C is a diagram illustrating the arrangement of video data in the encoding memory.

Fig. 7A is a diagram illustrating a search space pixel index.

Fig. 7B is a diagram illustrating the arrangement of search spaces in the video memory.

FIG. 7C is a diagram illustrating the arrangement of search spaces in the candidate memory.

Fig. 8A is a diagram illustrating the pixel index of a macroblock column.

Fig. 8B is a diagram illustrating the arrangement of macroblock columns in the video memory.

FIG. 9 is a block diagram illustrating the conversion of pixel index to basic address conversion for the storage pile in the candidate memory.

Figure 10 is a block diagram illustrating a block counter that tracks the search process of forming a macro block through a series of blocks.

FIG. 11 is a block diagram illustrating the physical address mapping of the memory heap in the candidate memory.

FIG. 12 is a block diagram illustrating the physical address mapping of the update of the macroblock column in the candidate memory.

Fig. 13 is a block diagram illustrating a difference processor.

Fig. 14 is a flowchart illustrating a video coding technique.

FIG. 15 is a flowchart illustrating a video encoding technique that uses column updates to gradually load into the search space.

FIG. 16 is a flowchart illustrating the basic address mapping of the memory bank in the candidate memory.

FIG. 17 is a flowchart illustrating the physical address mapping of the memory heap in the candidate memory.

FIG. 18 is a flowchart illustrating the physical address mapping for updating the macroblock column in the candidate memory.

Fig. 19 is a flowchart illustrating the difference between a macro block and many micro blocks constituting the macro block by the same calculation.

Detailed Description Generally, the present invention is directed to video coding techniques that can be used to improve the coding of digital video data. Video encoding technology can reduce the number of processing cycles and storage transfers necessary to encode video sequences, thereby increasing video encoding speed and reducing power consumption. For example, video coding technology can improve computational efficiency, especially for the motion estimation process with the greatest computational intensity in the video coding process. In addition, the video coding technology can be compatible with decoding standards (such as the MPEG-4 decoding standard).

Video coding technology can be implemented in various digital video devices, such as digital broadcasting systems, personal digital assistants (PDAs), laptop computers, desktop computers, digital cameras, digital recording devices, mobile phones, etc. According to standards such as MPEG-4, video coding technology can improve the efficiency of video coding, and better promote the implementation of video coding in wireless communication devices such as mobile phones, where computing resources are greater. It is limited and power consumption is a problem.

The video coding technology may use a candidate memory, which stores video blocks in a search space in a columnar form. The memory control unit addresses the candidate memory to retrieve multiple pixels in parallel for simultaneous comparison with the pixels in the video block to be encoded, for example, using a sum of absolute difference (SAD) or a sum of square difference (SSD) technology. A difference processor can perform parallel calculations. After multiple parallel comparison cycles, the difference processor may generate a search result in the form of a difference (sometimes referred to as a difference metric), the search result being related to the candidate video block of the search space to be compared with the video block to be encoded. In addition, for subsequent video blocks to be encoded, the candidate memory can be gradually updated by loading a new list of video blocks instead of reloading the entire search space. This column update can reduce power consumption and system bus usage, and can reduce the time to load a new search space.

FIG. 1 is a block diagram illustrating an example system 10 in which a source device 12 transmits an encoded video data sequence to a receiving device 14 via a communication link 15. The source device 12 and the sink device 14 are both digital video devices. In particular, the source device 12 uses any of various video compression standards, such as MPEG-4 developed by the Moving Picture Experts Group, to encode and transmit video data. Other standards may include MPEG-1, MPEG-2 or other MPEG standards developed by the Motion Picture Experts Group, ITU H.263 and similar standards, Motion JPEG 2000, QuicktimeTM technology developed by Apple Computer, Cupertino, California, Washington WindowsTM video developed by Microsoft Corporation of Redmond, IndeoTM developed by Intel Corporation and CinepakTM developed by SuperMac Corporation.

The communication link 15 may include a wireless link, a physical transmission, and a packet-based network, such as a local area network, a wide area network, or a global network, such as the Internet, a public switched telephone network (PSTN), and the like. Therefore, the communication link 15 represents any suitable communication medium or a collection of possible different networks and links for sending video data from the source device 12 to the sink device 14.

The source device 12 may be any digital video device capable of encoding and transmitting video data. For example, the source device 12 may include a video memory 16 for storing a digital video sequence, a video encoder 18 for encoding the sequence, and a transmitter 20 for sending the encoded sequence to the receiving device 14 via the communication link 15 . For example, the video encoder 18 may include a digital signal processor (DSP) that executes one or more programmable software modules to control the video encoding technology. Provide relevant memory and logic circuit to support DSP in controlling video coding technology. As described below, the video encoder 18 can be configured to reduce processing cycles, memory transfer, and power consumption. In addition, the video encoder 18 may be configured to perform a set of calculations to generate the difference values of the macroblocks and various differences of the microblocks constituting the macroblocks.

In addition, the source device 12 may include a video capture device 23 (such as a camera) for capturing a video sequence and storing the captured sequence in the memory 16. In particular, the video capture device 23 may include a charge coupled device (CCD), a charge injection device, a photodiode array, a complementary metal oxide semiconductor (CMOS) device, or other photosensitive devices capable of capturing video images or digital video sequences.

In other examples, the video capture device 23 may be a video converter for converting analog video data from a television, a video recorder, a camera, etc. into digital video data. In some embodiments, the source device 12 may be configured to send a real-time video sequence on the communication link 15. In this case, the receiving device 14 can receive a real-time video sequence and display the video sequence for the user. Alternatively, the source device 12 may capture and encode the video sequence sent to the sink device 14 as a video data file, that is, in non-real time. Therefore, the source device 12 and the sink device can support, for example, various applications in a mobile wireless network, such as video clip playback, video mail, or video conference.

The receiving device 14 may adopt any digital video device capable of receiving and decoding video data. For example, the receiving device 14 may include a receiver 22 for receiving an encoded digital video sequence from the transmitter 20 through, for example, an intermediate link, a router, other network equipment, and the like. The receiving device 14 may also include a video decoder 24 that decodes the sequence and a display device 26 that displays the sequence to the user. In some embodiments, the receiving device 14 may not include the integrated display device 14. Instead, the receiving device 14 may be used as a receiver for decoding the received video data to drive a separate display device, such as a television or monitor.

Example devices of the source device 12 and the sink device 14 include servers, workstations or other desktop computing devices provided on a computer network, and mobile computing devices such as laptop computers or personal digital assistants (PDAs). Other examples include digital television broadcasting satellites and receiving devices such as digital television, digital cameras, digital video cameras or other digital recording devices, digital video phones such as mobile phones with video capabilities, or other wireless video devices.

In some cases, the source device 12 and the sink device 14 each include a codec (CODEC) (not shown) for encoding and decoding digital video data. In this case, the source device 12 and the receiving device 14 may include a transmitter and a receiver as well as a memory and a display. The various encoding techniques outlined below are described in the context of a digital video device that includes an encoder. However, it is understood that the encoder can form part of the CODEC. In this way, CODEC can be implemented with DSP, microprocessor, application specific integrated circuit (ASIC), separate hardware components, or various combinations of them.

The video encoder 18 in the source device 12 operates on pixel blocks in a sequence of video frames to encode video data. For example, the video decoder 18 may perform a motion estimation coding technique, which divides a video frame to be transmitted into pixel blocks (referred to as video blocks). For illustrative purposes, video blocks may include micro blocks and macro blocks. For example, a micro block can be an 8×8 pixel array. A macro block can be a 16×16 pixel array. Therefore, one macro block can contain four micro blocks. This format is usually used to adapt to MPEG-4 encoding technology. However, other sizes of microblocks and macroblocks can also be used. Generally, in this application, the terms microblock and macroblock refer to video blocks that include multiple pixels. One macro block is further defined as multiple micro blocks. The number of microblocks that define a macroblock, the number of pixels that define a macroblock, and the number of pixels that define a macroblock are determined by a wide variety of special implementation formats.

Sometimes, calculating the motion estimation of microblocks instead of macroblocks can achieve improved resolution. Moreover, as will be described in more detail below, the pixels of a macroblock can be stored or addressed in a way that allows for difference calculations (also called difference metrics) of parallel smaller microblocks and difference values for macroblocks. Method of calculation. In other words, the calculation of the difference metric of the macro block can be regarded as a series of four calculations of the difference metric of the four micro blocks that make up the macro block. Correspondingly, the difference metric of the macroblock and the microblocks forming the macroblock can be generated from the same calculation. The special feature is that this technique can be simplified by not adding SAD or SSD calculations. Instead, the addressing and calculation scheme can be designed so that the encoder can translate the same calculation into micro-block difference calculation and macro-block difference calculation.

Each pixel in a microblock or a macroblock can be represented by an n-bit value, such as 8 bits, which defines the visual characteristics of the pixel, such as color and intensity, such as chroma and brightness. However, motion estimation is usually performed only based on the brightness component, because human vision is more sensitive to changes in brightness than changes in color. Therefore, for motion estimation, all n-bit values can be the quantized brightness of a given pixel. However, the principle of the present invention is not limited to pixel formats, but can be extended to use simpler pixel formats with fewer bits or more complex pixel formats with more bits.

For each video block in the video frame, the video encoder 18 of the source device 12 searches the transmitted video block of the previous video frame (or subsequent video frame) stored in the memory 16 to identify similar video blocks, and encodes the video The difference between the blocks, and the motion vector that identifies the video block from the previous frame (or subsequent frame) to be used for encoding. In this way, instead of encoding each frame as an independent image, the video encoder 18 encodes the difference between adjacent frames. Motion estimation includes identifying micro-blocks or macro-blocks in previous or subsequent frames, which preferably match the micro-blocks or macro-blocks in the current frame to be encoded.

The motion vector can define the pixel position associated with the upper left corner of the video block, although other formats of motion vectors can also be used. In any case, by encoding video blocks that use motion vectors, the bandwidth required to transmit the video data stream can be significantly reduced. In some cases, the source device 12 may support a programmable threshold that can cause the termination of various comparisons or calculations during the encoding process to reduce the number of calculations and save power.

The receiver 22 of the receiving device 14 may receive the encoded video data in the form of a motion vector and an encoded difference value. The decoder 24 performs motion compensation technology to generate a video sequence for display to the user through the display device 26. The decoder 24 of the receiving device 24 may also be implemented by a codec (CODEC). In this case, both the source device 12 and the sink device 14 can encode, send, receive, and decode the digital video sequence.

Figure 2 is a block diagram illustrating a video encoder 18 that encodes a digital video sequence in accordance with the techniques described herein. Figure 2 shows an exemplary implementation and should not be considered as a limitation to the present invention. As shown in FIG. 2, the video encoder 18 may include a digital signal processor (DSP) 28 and a motion estimator 29. The DSP 28 controls the operation of the motion estimator 29 and serves as a video encoding controller. Alternatively, the video encoding controller can be implemented with a processor, hardware components, firmware, application specific integrated circuit (ASIC), field programmable gate array (FPGA), and the like.

In the example of FIG. 2, the DSP 28 executes one or more programmable software modules to control the video encoding technique. The motion estimator 29 may include a DSP interface 30. The DSP 28, the DSP interface 30, and the video memory 32 communicate via the bus 33. The video memory 32 can be regarded as an external component of the video encoder 18 or integrated as a part of the video encoder 18. The DSP interface 30 interacts with the difference processor 34, which performs calculations related to the motion estimation program. The difference processor 34 may perform SAD or SSD calculations, for example, for calculating the motion vector of a block to be encoded or a macroblock of a given video frame. By informing the DSP 28 of the control of the encoding algorithm, and separating the motion estimation with high computational intensity in the hardware of the motion estimator 29, the ability to support real-time encoding is enhanced.

The difference processor memory 35 is further shown in FIG. 2, which includes an encoding memory 36 and a candidate memory 38. The encoding memory 36 uses a motion estimation program to store the current macroblock to be encoded. The current macro block corresponds to one of the macro block arrays in the video frame to be encoded. The candidate memory 38 stores an array of macroblocks from different frames that make up the search space. The difference processor 34 compares the macroblock in the candidate memory 38 with the current macroblock in the encoding memory 36 to identify the best match for use as a motion vector. For example, a search space of 48×48 pixels can be used. In this case, the search space will contain nine macro blocks, that is, three columns of three macro blocks, and each macro block contains a 16×16 pixel array. Other macroblocks may also be defined in the search space of 48×48 pixels to include pixels from two or more of the nine macroblocks that customize the search space.

The memory control unit 39 controls the addressing of the candidate memory 38 and the encoding memory 36 to drive the search process for the motion estimation program. In particular, the memory control unit 39 controls the pixel data to be loaded from the video memory 32 through the bus 33 to the candidate memory 38 to form a search space. For this purpose, the memory control unit 39 may be configured to provide memory address translation. Loading the entire 48×48 pixel search space directly into the candidate memory 38 without interference from the DSP 28 can reduce the bus action between the DSP 28 and the DSP interface unit 30, and reduce the need for moving video data in the DSP 28 The number of instructions. The difference processor 34 determines the SAD or SSD result of each macroblock and returns the result of the best match to the DSP interface 30. The DSP interface 30 in turn provides the encoded macroblocks and motion vectors to the DSP 28 for storage in the video memory 32 via the bus 33.

In operation, the DSP 28 can control the DSP interface unit 30 to drive the search process through the control channel 40. Generally, the control channel 40 is used for a memory load command, and it may include a pixel index to be loaded into the search space of the candidate memory 38. Each pixel index can indicate the address or candidate macroblock in the upper left corner, although other formats can also be used. In addition, the DSP 28 can receive the search result generated by the difference processor 34 through the data channel 41. The data channel 41 is also used for hardware construction and mode switching. The storage transfer between the DSP 28 and the video memory 32 can be realized through a direct memory exchange (DME) port on the DPS and the bus 33. In this case, the DSP interface unit 30, the difference processor 34, the encoding memory 36, the candidate memory 38, and the memory control unit 39 may reside in the entire motion estimator (ME) controlled by the DSP 28. Generally, the DME is used to access data from the video memory 32 to load the encoding memory 36 and the candidate memory 38.

In the example of FIG. 2, the video encoder 18 provides the host source device 12 with a compressed digital video sequence for transmission to the sink device 14. The video encoder 18 encodes the video sequence and buffers the encoded digital video sequence in the video memory 32 before transmission. The video memory 32 and the difference processor memory 35 can take the form of synchronous dynamic random access memory (SDRAM), flash memory, electrically erasable programmable read-only memory (EEPROM), and the like. The encoding memory 36 and the candidate memory are usually the local memory of the video encoder 18, and may include a common memory device partitioned into several virtual memories.

In addition to the components shown in FIG. 2, in some embodiments, the video encoder 18 may include other components, such as a texture encoder, for performing intra-frame or inter-frame compression commonly used to compress still images, such as discrete Cosine transform (DCT) coding. For example, texture coding can be performed in addition to motion estimation, or can be performed instead of motion estimation when processing power seems to be very limited for effective motion estimation. The DSP 28 can selectively invoke the motion estimator (29) and the texture encoder (not shown) to guide the encoding procedure according to the processing capacity at any given moment.

FIG. 3 shows an example video block in the form of a macro block 42 which can be stored in the video memory 32 in video frames. The MPEG standard and other video coding schemes use video blocks in the form of macroblocks during motion estimation video coding. As mentioned above, in a system where MPEG-4 is applied, the term "macroblock" refers to a collection of 16×16 pixel values that form a subset of a video frame. Each pixel value can be expressed as a byte of data, although more or fewer bits can also be used to define each pixel to obtain the desired image quality. The macroblock may include a plurality of smaller 8×8 pixel microblocks 44A-44D. However, generally, if necessary, the encoding technique described here can be operated with blocks of any size, such as 16-byte×16-byte macroblocks, 8-byte×8-byte microblocks, or video blocks of different sizes.

FIG. 4 shows an example part of the search space 46, which may be stored in the candidate memory 38. The search space 46 is a collection of pixels corresponding to a previously transmitted video frame (or a subsequent video frame in a sequence of frames). If needed, the search space can include the entire previous or subsequent video frame, or a subset of the video frame, if needed. As shown in the figure, the search space can be rectangular, or any various shapes and sizes can be assumed.

During video encoding, the current macroblock to be encoded is compared with the video block in the search space 46 to identify an appropriate match, so that the difference between the current macroblock and similar macroblocks in the search space can be sent, and similar videos can be identified The motion vector of the block. As described above, the macroblock 48 defined in the search space 46 may be stored in the candidate memory 38, and the current macroblock to be encoded may be stored in the encoding memory 36.

During motion estimation video encoding, the difference processor 34 may use comparison techniques, such as SAD and SSD techniques, to compare the current macroblock to be encoded with the macroblock of the previous or subsequent frame. As shown in FIG. 4, the macro block 48 in the search space 46 can be identified by the upper left pixel address 48 of each macro block. Other comparison techniques can also be used. In particular, according to the principles of the present invention, SAD and SSD calculations can be performed in parallel for multiple pixels. In addition, the addressing and calculation order of the pixel-like comparison can be accomplished in a manner that results in the difference of each macroblock to be coded and the difference of the microblocks forming the macroblock.

In the present invention, the term "task" refers to a set of general calculations used to compare the current video block with different video blocks in the search space. In other words, the task refers to a single comparison between the current video block and different video blocks in the search space. For example, the task may involve performing multiple calculations to compare multiple pixels of the current video block with multiple pixels of the candidate video block in the search space. As described here, various subsets of these task calculations can be performed in parallel to speed up the encoding process. 64 calculations can be regarded as a microblock task (assuming the microblock is an 8×8 pixel array), and 256 calculations can be regarded as a macroblock task (assuming the macroblock is a 16×16 pixel array). During each task, these calculations are accumulated to define the ongoing difference (sometimes called the difference metric) for that task.

In the present invention, the term "iteration" refers to a set of general tasks performed during video encoding. A complete series of tasks associated with a current video block to be encoded is an iteration. In other words, one iteration is a set of comparisons in which the current video block is compared with a set of previous video blocks (or subsequent video blocks) in the search space. Each individual comparison is a task that contains multiple calculations. Therefore, the search space defines a set of video blocks, which are compared with the current video block during one iteration. Each comparison of an iteration is called a task, and each task, that is, each comparison, can contain multiple calculations.

In some cases, the iteration may include defining a first search in the search space, identifying a first match in the search space, defining a second search in a subset of the search space based on the first match, and identifying a second match in the subset . For example, a later search in an iteration can include subtle movements in the search space to more accurately locate the best match. Other search techniques may also be used, such as a diamond search technique, in which the search is continuously performed until the pixel position of the macroblock that produces the smallest difference is identified at the center of the diamond search parameter. In addition, other techniques can be used, such as a circular search technique, in which the pixel position of the macroblock that produces the smallest difference is identified at the center of the search parameter defined by the radius (R). Compared with diamond search parameters, a circle with a radius (R) can define a larger and wider range of search parameters.

If the diamond search technique or the circle search technique is used during the iteration, the initialization technique can also be used to speed up the process of identifying the macroblock that is located at the center of the diamond search parameter or the circle search parameter that produces the smallest difference. For example, an initialization technique that utilizes the phenomenon of spatial redundancy can be used. Spatial redundancy generally indicates that the video motion of a given video block may be similar to the video motion of another video block that is spatially close to it. The initialization technique can more easily use this phenomenon to initialize the motion estimation of a position in the search space, and the search space is likely to contain video blocks that can be used for effective video coding.

Specifically, the initialization technique can use the motion vector calculated for the video block that is spatially similar to the video block to be encoded to identify the position in the search space where the motion estimation procedure can be initialized, that is, the pixel in the search space where the motion estimation procedure starts. position. For example, the average pixel position, the intermediate pixel position, or the pixel position calculated using a weighting function may be calculated according to the motion vector previously determined for the video block that is spatially close to the video block to be encoded. Other linear or non-linear functions can also be used. In any case, by initializing the motion estimation program in this way, video coding can be speeded up in the case of diamond search or circular search, because it reduces the tasks required to locate the video block in the search space in the iteration Number, the video block is an acceptable match for the video block to be encoded.

If necessary, the calculation used to generate the difference may include SAD technology, SSD technology, or other comparison technology. The SAD technology includes the task of calculating the absolute difference between the pixel value of the current macroblock to be encoded and the pixel value of the previous macroblock compared with the current macroblock. The results of these absolute difference calculations are summed, that is, accumulated, to define a difference that represents the difference between the current macroblock and the previous macroblock compared with the current macroblock. For an 8×8 pixel image block, 64 difference values are calculated and summed, and for a 16×16 pixel macroblock, 256 difference values are calculated and summed. By addressing the current video block and performing calculations in a specific order, 256 differences can be calculated and summed in four independent groups, so that a difference can be generated for each micro-block. Then, the sum of all four sets of calculations can define the difference of the macroblock.

A smaller difference usually indicates that the macro block compared with the current macro block is a better match. Therefore, compared with the candidate macro block that produces a larger difference (that is, the distortion is increased), it is a better match for motion estimation coding. Good candidate. In some cases, the calculation can end when the accumulated difference exceeds a predetermined threshold. In this case, additional calculations are unnecessary because the macroblock compared with the current macroblock is not acceptable for efficient motion estimation coding.

The SSD technology may also include the task of performing the calculation of the difference between the pixel value of the current macroblock to be encoded and the pixel value of the previous macroblock compared with the current macroblock. However, in the SSD technology, the result of the absolute difference calculation is squared, and then these squared values are summed, that is, accumulated, to define a difference representing the difference between the current macroblock and the previous macroblock compared with the current macroblock. Alternatively, other comparison techniques can be implemented, such as mean square error (MSE), normalized cross-correlation function (NCCF) or other suitable comparison algorithms.

In some cases, for example, once it is determined that a given task does not produce a better match than the previous task, or it is recognized that a given task produces an acceptable match, various tasks or iterations are terminated early. For example, various techniques can be used to identify when additional calculations for a given task are unnecessary. Specifically, when the difference produced by a subset of the second task calculation is greater than the difference related to the previously calculated first task, it is well known that the additional calculation of the second task is unnecessary because the second task is not completed. Will produce a smaller difference than the first task. In this case, the second task can be terminated without sacrificing coding performance, and the third task can be started faster.

The termination technique can also be performed at the iteration level, or at the task level and the iteration level at the same time. In one example, the iteration threshold defines an acceptable value, which is suitable for efficient video coding. In this case, if the task of identifying a candidate video block in the search space is performed, and the candidate video block matches the current video block to be encoded in a way that is considered acceptable by the iteration threshold, then the iteration can be terminated and the process will be pending. The next video block to be coded is compared with the search space. In this case, you can avoid performing multiple unnecessary tasks.

The various techniques here are described in the context of comparing a video block to be encoded with a previous video block in a previous video frame. However, it can be understood that the same technique can be used when comparing a video block to be encoded with candidate video blocks in subsequent video frames. In some cases, two-way motion estimation is used, where the video block to be encoded is compared with various video blocks of one or more previous video frames and various video blocks of subsequent video frames. In summary, the various techniques described here can be used at any time when a video block to be encoded is compared with different video blocks, such as candidate video blocks of previous video frames or candidate video blocks of subsequent video frames. In other words, the search space can be loaded with various candidates in various implementations.

FIG. 5 is a conceptual illustration of the current macroblock 50 to be coded, which is located in an example search space 52 arranged as a candidate macroblock array. Specifically, as shown in FIG. 5, the search space includes three rows 54A-54C and three columns 56A-56C candidate macroblocks for comparison with the macroblock 50 to be coded. Therefore, in the example of FIG. 5, the search space 52 includes an array of nine 16×16 pixel macroblocks to form a 48×48 pixel area. The difference processor 34 is used to compare the current macroblock 50 to be encoded with the macroblock in the search space 52.

In order to reduce the storage transfer and related processing overhead between the video memory 32 and the candidate memory 38, once the search space 52 is initially loaded, subsequent updates to the search space can be performed on a column-by-column basis as needed. For example, in order to encode subsequent macroblocks of a given frame, the memory control unit 39 may only replace the candidate macroblocks in the left column 56A of the search space 52 instead of reloading the entire search space 52.

In order to implement column update and allow parallel motion estimation calculations to be performed on multiple pixels simultaneously, the memory control unit 39 is configured to perform an address mapping scheme for the memory stored in the video memory 32, the encoding memory 36, and the candidate memory 38. Convert between addresses. The data update of the encoding memory 36 and the candidate memory 38 occurs between them and the video memory 32 through the bus 33 that directly accesses the video memory. In order to initialize and control the transfer via the bus 33, the DSP 28 acts as a bus controller via the DME port.

Fig. 6A is a diagram illustrating the pixel index of a macroblock. As shown in FIG. 6A, the macroblock pixel index can be divided into four microblocks (A, B, C, D). The macroblock pixel index is 16×16, and each macroblock A, B, C, D is 8×8. The entire macroblock pixel index extends from the upper left pixel Y0 to the lower right pixel Y255 (not shown). The DSP 28 saves the pixel index to track the macroblocks in the search space. According to the application, the memory control unit 39 is used to convert the pixel index provided by the DSP 28 into a physical memory address in the video memory 32, the encoding memory 36, or the candidate memory 38. For example, the memory control unit 39 provides the converted address to the candidate memory 38 for search space update, or to the code memory 36 for SAD calculation by the SAD engine 34.

FIG. 6B is a diagram illustrating the arrangement of video data in the video memory 32. Specifically, FIG. 6B shows the difference between the macroblock pixel index saved by the DSP 28 and the physical arrangement of the macroblock pixel data in the video memory 32. As shown in FIG. 6B, the video memory 32 stores macroblock pixel data at 64 addresses arranged in rows of four pixels, generating 64 rows for each macroblock. Each pixel is 8 bits, and each row contains 32 bits of data. Therefore, in order to access the video memory in response to the pixel index from the DSP 28, the memory control unit 39 needs to convert the pixel index into a physical address in the video memory.

FIG. 6C is a diagram illustrating the arrangement of video data in the encoding memory 34. FIG. As shown in FIG. 6C, the macroblock pixel data stored in the encoding memory 36 is arranged into 32 rows, with 8 pixels per row, that is, 64 bits per row. According to the present invention, the storage arrangement in the encoding memory 36 facilitates the parallel absolute difference (AD) calculation performed by the difference processor 34 for multiple pixels at the same time. Specifically, the example of FIG. 6 is the physical arrangement of the encoding memory 36, which allows parallel AD calculations for 8 pixels at the same time. In addition, when a microblock is defined to have a width of 8 pixels, the physical arrangement of FIG. 6C may allow the difference calculation of the microblock as well as the macroblock, because the microblock generally has a width of 8 pixels. The width of the encoding memory 36 may be 64 bits. 6A-6C collectively show how the macroblock pixel index is mapped to the video memory 32, and then how the video memory is mapped to the physical encoding memory 36 in the difference processor memory 35.

FIG. 7A is a diagram illustrating the search space pixel index held by the DSP 28. The DSP 28 uses the pixel index in the search space to specify the search task, such as a set of calculations for the result (difference) produced by the difference processor 34. The search space pixel index of FIG. 7A corresponds to a 3 macroblock×3 macroblock search space, and therefore contains 2304 pixels (3×3×16×16). As shown in FIG. 7A, the search space pixel index contains 48 rows, and each row contains 48 pixels.

FIG. 7B is a diagram illustrating the arrangement of search spaces in the video memory 32. As shown in FIG. As shown in FIG. 7B, the physical arrangement of search space pixels includes 4 pixels per row, as shown in the macroblock memory arrangement of FIG. 6B. In addition, the pixels are arranged in 576 rows. Each pixel is 8 bits, and each row of 4 pixels contains 32 bits.

FIG. 7C is a diagram illustrating the search space arrangement in the candidate memory 38. In particular, similar to the encoding memory 36, the candidate memory 38 is arranged in 8 pixels per row. In order to store the entire search space, the candidate memory 38 includes 288 rows. In other words, the candidate memories 38 are arranged into 8 stacks of 288×8-bit memories. Each line is 64 bits wide. Although the encoding memory 36 only stores macroblocks, and the candidate memory 38 stores a search space of three macroblocks wide and a total of nine microblocks, each memory 36, 38 has an output of 8 pixels wide. In this way, the encoding memory 36 and the candidate memory are arranged to facilitate the comparison of each macroblock to be encoded, even if the absolute difference of 8 pixels is calculated in parallel at the same time. In addition, the encoding memory 36 and the candidate memory 38 are arranged to calculate the microblock difference value during the calculation of the macroblock difference value.

In addition to allowing parallel AD calculations for multiple pixels, the candidate memory 38 is arranged to allow addressing of macroblocks starting at any pixel in the search space. In addition, as described below, the structure of the candidate memory 38 may allow for gradual column updating, that is, loading a column of macroblocks at a time, instead of reloading the entire search space for each new macroblock to be coded. This loading technique can reduce power by avoiding redundant memory loading and reducing the use of the bus 33. The memory control unit 39 is again configured to convert the search space pixel index into a physical memory address in the video memory 32, and then convert the memory address from the video memory into a corresponding physical memory address in the candidate memory 38.

Fig. 8A is a diagram illustrating the pixel index of a macroblock column. For two adjacent macroblocks to be coded, the difference between the applicable search spaces is only one macroblock column. As a result, only one macroblock column needs to be updated. The candidate memory is arranged to adopt this feature, thereby reducing the data bandwidth required for the transfer between the video memory 32 and the candidate memory. As shown in FIG. 8A, the macroblock column pixel index saved by the DSP 28 can be arranged in rows of 16 pixels and extend 48 rows over the length of a single column in the search space. Therefore, the macroblock pixel index shown in FIG. 8A corresponds to a column of three macroblocks, that is, one third of the search space pixel index of FIG. 7A.

The physical memory arrangement of the macroblock column pixel index in the video memory 32 is also different from the memory arrangement of the entire search space pixel index. Fig. 8B is a diagram illustrating the arrangement of macroblock columns in the video memory. For a macroblock column, the video memory 32 provides 192 rows, each with 4 pixels. Therefore, the macro block column arranged in the video memory 32 is 32 bits wide. Once the search space is loaded into the candidate memory 38 for the initial macroblock, the search for subsequent, adjacent macroblocks to be coded can be realized by loading only a new column.

During the column update, the memory control unit 39 replaces the previous left macroblock column with a new macroblock column. Then, the newly loaded macro block column is designated as the current right macro block column. In addition, the previous middle macro block is designated as the new left macro block column, and the previous right macro block column is designated as the new middle macro block column.

Therefore, the search space can be regarded as being shifted to the right in a larger frame to eliminate the previous left macroblock column, thereby making room for the new right macroblock column. After this column update operation, the search space in the candidate memory 38 is applied to the next macroblock in the encoding memory 36.

By converting the pixel index provided by the DSP 28 into the physical addresses of the video memory 32 and the candidate memory 38 in the memory control unit 39, there is no need for the DSP to track the column movement operation. As a result, the DSP 28 only needs to provide the pixel index of the new right macroblock column.

FIG. 9 is a block diagram illustrating an example circuit constituting part of the memory control unit 39, which is used to convert a pixel index into a basic address conversion for a memory bank in the candidate memory 38. As shown in FIG. 9, the memory control unit 39 includes a suitable logic circuit for realizing the memory address conversion. The memory control unit 39 tracks the current iteration, such as the update of the encoding memory 36, the update or full loading of the candidate memory 38, or the difference processor 34 performs a search task of parallel AD calculation for the contents of the encoding memory and the candidate memory. As described below, the memory control unit 39 can also track the block boundary during the search, manage the movement of the macroblock column in the candidate memory 28, and perform pixel-to-address conversion.

Generally, for a search, the memory control unit 39 determines the corresponding starting pixel stack in the candidate memory 38 according to the following formula, that is, the position in the row containing 8 pixels: starting pixel stack = mod 8 (pixel index) (1) In addition , The memory control unit 39 determines the row of starting pixels according to the following formula: row of starting pixels=int(pixel index/8) (2) Therefore, according to the mod function (1), the starting pile is the remainder of the pixel index divided by 8. According to the integer division function (2), the starting line is the largest integer that can be divided by the pixel index.

According to the above formulas (1) and (2), the starting or "basic" address of each pile x can be expressed as: pile x basic address = row of starting pixels, if x >= pile of starting pixels = row of starting pixels +1 If x<the starting pixel heap (3) is shown in Fig. 9, the comparator 58 in the memory control unit 39 compares the row indicated by the pixel index (pixel index mod 8) with the heap index, and if the pixel index is smaller than the heap index The index produces an output of 1, and if the pixel index is greater than or equal to the heap index, an output of 0 is produced. Then the adder 60 in the memory control unit 39 adds the output 1 or 0 of the comparator 58 to the stack [int (pixel index/8)] indicated by the pixel index to generate the base address of the stack x.

FIG. 10 is a block diagram illustrating a video block counter circuit 62 that tracks the search process of a series of micro blocks (A, B, C, D) shown in FIG. 3 to form a macro block. Once the basic address of each heap is determined, the memory control unit 39 generates a gradual update and reload of the counter according to the block boundary tracking address. In the example of FIG. 10, the block counter circuit 62 may include a 5-bit counter 64 that is initially loaded with a value 31 to provide 32 counts. After initialization (task_start), the counter 64 performs a positive count every clock cycle. However, it can also be adapted to a counter that counts down. When the count reaches 0b11000, the judgment logic 66 indicates that the search controlled by the difference processor 34 has completed the AD calculation of the microblock A. Similarly, the counts 0b10000, 0b01000, and 0b00000 indicate that microblocks B, C, and D are completed. When the count 0b00000 is reached, the search for a given macroblock (task_done) is completed. In this way, the block counter circuit 62 tracks the process of calculating the current macroblock difference controlled by the difference processor 34. In addition, the block counter circuit 62 can determine when the difference value associated with each macroblock is calculated.

When the boundary of each microblock is crossed, the judgment logic 66 generates a block_done signal, which is used to instruct the difference processor 34 to latch the results of each microblock. Therefore, the video encoder 18 generates the difference value of each micro block and the result of the difference value of the macro block. In addition, the same individual calculations are used to produce these difference results. In other words, the four independent subsets of calculations produce each difference of the microblock, and the sum of all calculations produces the difference of the macroblock.

As mentioned above, termination techniques can be added to terminate various tasks or iterations to avoid calculations in some cases. In one implementation, after performing each group of parallel AD calculations, it can be determined whether to terminate the task. In other words, each latch of the microblock row can provide an appropriate time for determining whether the task threshold has been exceeded. If it exceeds, the additional calculation for the specific task can be terminated, because it can be known that the search will not produce the smallest difference. Specifically, if the task threshold is exceeded, the difference of the subset of candidate macroblocks has exceeded the difference calculated for the previous candidate macroblock in the search space.

FIG. 11 is a block diagram illustrating the physical address mapping circuit 68 of the storage heap in the candidate memory 38. Generating the physical address in the candidate memory 38 includes loading the basic address generated by the pixel index into the accumulator, as shown in FIG. 9 for conversion addressing. For each clock cycle, the address is incremented by 48 pixels to the next row of pixels in the macroblock, which is converted to 6 rows (48 pixels ÷ 8 stacks). After completing block B, the accumulator is reloaded with the base address +1 for calculation of block C and block D.

As shown in FIG. 11, the mapping circuit 68 may include an adder 70, which adds 1 to the base address (mb_base_addr) when the calculation of the block B (block_b_done) is completed, thereby generating the column base address (col_base_addr) in the candidate memory 38. If the block B is completed or the search task is started (task_start), the OR gate 72 passes the logic high output to the multiplexer 74.

In response to the logic high output from the OR gate 72, the multiplexer 74 outputs the column base address to the accumulator 76. In response to the logic low output from the OR gate 72, the multiplexer passes the output of the adder 78 to the accumulator 76. The adder 78 adds the current candidate memory address (logical_cram_addr) from the accumulator 76 to a value of 6. If there is no start of the search task or completion of block B, the multiplexer 74 and accumulator 78 advance the current candidate memory address by 6 lines, that is, 48 pixels on 8 piles. In this way, when encountering the completion block B or starting a new search task, the memory control unit 39 loops through each row of the 8 piles in the candidate memory 38 to indicate to the difference memory 34 one microblock row at a time. Therefore, the calculation is performed line by line until each difference of microblocks is generated, and is performed one microblock after microblock, until the difference of the macroblock is calculated. Then, for the next macroblock in the search space, the process continues in a row by row, microblock by microblock, and so on.

FIG. 12 is a block diagram of the physical address mapping circuit 80 for explaining the update of the macroblock column in the candidate memory. The address mapping circuit 68 shown in FIG. 11 does not process the movement of the macroblock column when the update of the macroblock column occurs. Instead, the mapping circuit 68 is adapted to completely reload the macroblock column of the search space. When the column update feature is applied, the address mapping circuit 80 of FIG. 12 passes another range of address mapping.

In the physical candidate memory 38, each row of the macroblock column is mapped into two rows of data. For example, at reset, address 0 and address 1 (addr 0/1) indicate the first row of the left macroblock column. In particular, the address 0 represents the rows of 8 piles in the candidate memory 38, which corresponds to the first group of 8 pixels in the pixel index row of the left macroblock column. Address 1 represents the rows of 8 stacks in the candidate memory 38, which corresponds to the second group of 8 pixels in the pixel index row of the left macroblock column.

Then, address 2 and address 3 (addr 2/3) indicate the first row of the middle macro block column, and address 4 and address 5 (addr 4/5) indicate the first row of the right macro block column. Therefore, as shown in FIG. 7C, the 8 piles of rows in the candidate memory 38 sequentially store pixel data across each entire row of the left, middle, and right macroblock columns (for example, Y0-Y47 for the first row).

After a macroblock column is updated, addr 0/1 (previously represents the left macroblock column) is used to represent the right macroblock column, and addr 2/3 (previously represents the middle macroblock column) is used to represent the left macroblock column , Addr 4/5 (previously indicated the right macroblock column) is used to indicate the middle macroblock column.

In this way, the left and right macroblock columns store the same data as the previous middle and right macroblock columns, respectively, without the need to reload new data. However, now the addresses (addr 2/3 and addr 4/5) are mapped to the left and middle macroblock columns. However, the previous left macroblock column address (addr 0/1) is mapped to the right macroblock column and reloaded with new data from the video memory 32.

In order to perform the address mapping in the column update mode, the mapping circuit 80 in FIG. 12 determines two conditions: the mod 3 output of the base address of the candidate memory column (col_base_addr mod 3) and the macroblock column movement status, that is, a full update or a column update is requested.

As shown in FIG. 12, the mapping circuit 80 includes a mod 3 operator 82, which generates a mod 3 output of the current basic column address divided by 2 (cram_addr[8:1]), and applies the mod 3 output to the temporary storage device 84 ( Sometimes called a trigger). The mod 3 output of the column base address is always 0, 1, or 2. For example, the column base address (Y0) of the first column will produce 0, the column base address (Y16) of the second column will produce 1, and the column base address (Y32) of the third column will produce 2.

When a new search task starts (task_start) or the calculation block B is completed (block_b_done), the OR gate 86 activates the flip-flop 84 to output the mod 3 output from the mod 3 operator to be applied to the multiplexer 88. The mod 3 output indicates the column in which the basic address of the column is currently located, that is, the first column (0), the second column (1), or the third column (2).

In response, the multiplexer 88 passes one of the outputs of the multiplexers 90, 92, 94 to the adder 96. The output of the multiplexers 90, 92, 94 is determined by the output of the 2-bit counter 98. The counter 98 is reset with a value of 0 in response to the received full update (full_update) signal, which indicates that the entire search space in the candidate memory 38 will be reloaded. In response to the column update (col_update) signal at the start input, the counter 98 counts up by 1, or in other implementations, counts down.

The column update signal indicates that the search space in the candidate memory 38 will be gradually updated by loading a new column. The counter 98 may be incremented for each column update, or for two column updates, and return a value of 0 after the third column update. For example, the counter 98 can be incremented from 0 to 1, to 2, back to 0, to 1, to 2, to 0, to 1, to 2, and so on. The counter 98 may also be reset when the count is 0x11, and the reset may occur regardless of the startup state.

In each case, the count output of counter 98 keeps track of how many column moves have been performed during the stepwise column update procedure. The count output of the counter 98 can provide logic inputs to the multiplexers 90, 92, 94 to facilitate address mapping judgments. The multiplexers 90, 92, 94 correspond to the left, middle, and right columns of the search space, respectively. If the count output is 0, the multiplexers 90, 92, 94 output the values 0, 0, and 0. If the count output is 1, the multiplexers 90, 92, 94 output the values +2, +2, and -4, respectively. If the count output is 2, the multiplexers 90, 92, 94 output the values 0, -4, and +2, respectively. In addition, the count output is provided to the 0b11 comparator 95, and the 0b11 comparator 95 provides a signal to the OR gate 97. Therefore, the reset of the counter 98 can occur in response to a complete update signal or a signal from the comparator 95, both of which are input to the OR gate 97.

The operation of the multiplexers 90, 92, 94 reflects the previous movement of the middle column to the left column and the previous movement of the right column to the middle column, that is, two rows to the left (+2) in each case. Each row in the calling macroblock column is represented by two rows in the candidate memory 38 (see FIG. 7C). This operation can also reflect the previous movement from the left column to the right column, that is, four rows to the left (-4). After the three columns are updated, the address matches the physical memory again, so the output values of the multiplexers 90, 92, 94 return to 0, 0, and 0, respectively.

The outputs of the multiplexers 90, 92, 94 reflect the next move in sequence. After the second move, the original middle column has been moved to the left column and is now moved to the right column, the original right column is now moved to the left column, and the original left column is now moved to the middle column. In this case, the current left column deviates from its original position, the right column + 4 rows, the current middle column deviates from its original position, the left column -2 rows, and the current right column deviates from its original position, the middle column -2 Row.

If the output of the flip-flop 84 is 0, the output of the first column multiplexer 90 passes through the multiplexer 88. If the output of the flip-flop 84 is 1 or 2, the outputs of the second or third column multiplexers 92, 94 pass through the multiplexer 88, respectively. In each case, the output of the multiplexer 88 is applied to the adder 96, which adds the output to the logical candidate memory address (logical_cram_addr).

In this way, the adder 96 moves the logical candidate memory address by an amount equivalent to the column update movement state to obtain the physical candidate memory address of the appropriate macroblock. If the logical address corresponds to the right column as a result of the move operation, and the physical address actually corresponds to the middle column, the mapping circuit 80 provides the necessary address translation. Then, the memory control unit 39 causes the difference processor 34 to compare the appropriately addressed data in the candidate memory 38 with the corresponding data in the encoding memory 6, such as performing parallel AD calculations on 8 output piles.

FIG. 13 is a block diagram illustrating the difference processor 34 in more detail. In particular, FIG. 13 shows the parallel computing function provided by arranging the encoding memory 36 and the candidate memory 38 to generate 8 simultaneous heap outputs. As shown in FIG. 13, the difference processor may include a plurality of absolute difference (AD) calculation channels 100A-100H, collectively referred to as 100. Each AD calculation channel 100 receives its own heap output (a0-a7) from the encoding memory 36 for the macroblock to be encoded.

In order to compare and calculate the absolute difference, each AD calculation channel 100 also receives the corresponding heap output (b0-b7) from the candidate memory 38. A set of 8-bit adders 102A-102D, a pair of 9-bit adders 104A and 104B, and a 10-bit adder 106 sum the AD results in cascade. If more bits are used to represent pixels, a larger adder can be realized. In any case, the output of the adder 106 is applied to the adder 108. The adder 108 sums its own output and the output of the adder 106 through the flip-flop 110 to generate a sum of absolute difference (SAD) result. Each group of eight inputs (a0-a7) can correspond to rows of eight pixels of the microblock. For example, for each row of microblock A (FIG. 6A), then each row of microblock B, followed by microblock C and microblock D, the input can be provided to the difference processor. The accumulation may be latched after calculating the difference metric for each micro block, and then latch the total accumulation of the difference metric corresponding to the macro block again.

In addition, after each latching step, it can be judged whether to terminate the task. In other words, each latch of the microblock row can provide an appropriate time for determining whether the task threshold has been exceeded. If it exceeds, the additional calculation for the specific task can be terminated, because it can be known that the search will not produce the smallest difference.

Figure 14 is a flowchart illustrating the video encoding technique described herein. As shown in FIG. 14, once the search is started, the task is started (112), and the DSP 28 generates a pixel index for the macroblock to be coded (114). The memory control unit 39 converts the macroblock pixel index into a video memory address and an encoding memory address (116), and loads the macroblock from the video memory 32 into the encoding memory 36 through the bus 33 and the memory control unit (118). The DSP 28 also generates a pixel index for the search space (120). Once the search space pixel index is converted into a video memory address and a candidate memory address (122), the memory control unit 39 loads the search space macroblock into the candidate memory 28 (124).

The difference processor 34 performs a parallel AD calculation (126) between the multiple stack outputs of the candidate memory 38 and the encoding memory 36 to compare the macroblock to be encoded with the macroblock in the search space. According to the parallel AD calculation, the difference processor 34 produces the best SAD result (128) on the entire search space (or may produce acceptable results regardless of the entire search space). In another case, the result is related to the pixel index of the macroblock to be encoded. As described above, the difference processor 34 can generate the SAD result for each micro block forming the macro block without requiring additional SAD calculation. After generating the SAD result for the macroblock, the DSP 28 can determine whether an acceptable match is recognized, and if recognized, it can store the motion vector according to the MPEG-4 compression standard to identify the macroblock to be encoded.

FIG. 15 is a flowchart illustrating a video coding technique that uses column updates to gradually load into the search space. Once the next pixel index (130, 132) is generated by the DSP 28 to drive another search task, the memory control unit 39 converts the macroblock pixel index into a video memory address and an encoding memory address (134). Then, the relevant macroblock is loaded from the video memory 32 into the encoding memory 36 (136). However, in this case, the search space is gradually updated by adding a new column instead of reloading the entire search space.

Correspondingly, the DSP 28 generates a pixel index for the search space column update (138), and then the memory control unit 39 converts the column to update the pixel index to generate related video memory addresses and candidate memory addresses (140). Once the new macroblock column is loaded from the video memory 32 into the candidate memory 28 (142), the difference processor 34 performs the parallel AD calculation (144) of the eight output stacks of the candidate memory 38 and the encoding memory 36 (144), The parallel AD calculation produces the best SAD result (or acceptable SAD result) (146).

FIG. 16 is a flowchart illustrating the basic address mapping of the memory bank in the candidate memory. The process shown in FIG. 16 corresponds to the operation of the circuit in FIG. 9, although other various circuits may be used. In order to obtain the basic address from the pixel index, the memory control unit 39 calculates the result of the pixel index mod 8 operation (150). If the result is greater than or equal to the current heap index (152), the base address is equal to the integer quotient of the pixel index divided by 8 (154). If the result is less than the current heap index (152), the base address is equal to the integer quotient of the pixel index divided by 8 plus 1 (156).

FIG. 17 is a flowchart illustrating the physical address mapping of the memory heap in the candidate memory. The process shown in FIG. 17 corresponds to the operation of circuit 68 in FIG. 11, although other various circuits may be used. If the AD calculation of block B in the macro block has been completed (160), the column base address in the candidate memory 38 is equal to the macro block base address + 1 (162). If block B is not completed (160), the column base address in the candidate memory 38 is equal to the macroblock base address (164). Then, if block B has completed or started a new search task (166), the logical memory address in the candidate memory 38 is equal to the base address (168). If block B is not completed and no new search starts (166), the logical candidate memory address is moved by six rows (170).

FIG. 18 is a flowchart illustrating the physical address mapping for updating the macroblock column in the candidate memory. The process shown in FIG. 18 corresponds to the operation of the circuit 80 in FIG. 12, although other various circuits may be used. As shown in FIG. 18, the column specified by the column base address is determined, and the memory control unit 39 applies a mod 3 operation to the column base address (174). If the column update feature is not activated (176), the logical candidate memory address is not moved (178). This corresponds to the output (0, 0, 0) of the multiplexers 90, 92, 94 in FIG. 12, and corresponds to the counter output 0 of the counter 98, so the multiplexer 88 passes 0.

If the column update is activated (176), the memory control unit 39 refers to the output of the counter 98 to determine the number of column update moves that have occurred (180). Based on the identified column and the number of column update moves, the memory control unit 39 determines the amount by which the logical candidate memory address should be moved to generate the correct physical candidate memory address (182). The memory control unit 39 then converts the logical candidate memory address plus the address movement into a physical candidate memory address (184).

Fig. 19 is a flowchart illustrating the difference between a macro block and many micro blocks constituting the macro block by the same calculation. As shown in the figure, when the motion estimator 29 starts the macroblock search iteration (191), the difference processor 34 performs parallel absolute difference (AD) calculations one macroblock row after the macroblock row. For example, the value X may be initialized (192), and the difference processor 34 may perform a parallel AD calculation (193) on the Xth row of the first microblock in the encoded macroblock. As long as there are other rows in the microblock (194 is a branch), the value X is incremented (195) and the parallel AD calculation is performed on the next row of the microblock.

The video block counter circuit 62 may determine whether there are other rows in the micro block (194). For example, the video block counter circuit 62 may be integrated as a part of the difference processor 34, or may form a part of the DSP interface unit 30. Once it is determined that the AD calculation has been performed on each row of the first microblock, the difference processor 34 outputs the difference value of the first microblock (196). This step is continuously performed for each microblock of the macroblock until there are no other microblocks (197). Task termination techniques can also be used at this stage of the process, for example, the task is terminated when the total accumulated difference exceeds a task threshold, such as the threshold corresponding to the minimum difference that has been calculated for the current iteration.

The difference processor 34 may accumulate the ongoing (ongoing) difference value for the macro block, and may output the difference value of each micro block because the calculation of each micro block is performed. The difference of the first microblock may be the accumulated value of the previous differences. The difference of the second microblock may correspond to the total accumulated value before this minus the difference of the first microblock. The difference of the third microblock may correspond to the total accumulated value before this minus the difference between the first and second microblocks, and so on.

The video block counter circuit 62 can also determine when the accumulation of the calculation of the last micro block has been completed (the yes branch of 197). At this time, the difference processor 34 outputs the difference value of the macro block (198), which is the total accumulated value of the previous AD calculation. The DSP 28 or the DSP interface unit 30 may determine whether to perform other tasks of the current macroblock to be encoded with other rows in the microblock (194). Again, the task refers to a set of calculations used to compare the current video block to be coded with the video block in the search space. Iteration refers to the calculations corresponding to various different video blocks in the search space and the current video block to be coded. A set of tasks for comparison.

The iteration can be simplified to compare a predetermined group of video blocks in the search space with the video blocks to be encoded, or can be more complex to include initialization techniques for locating positions in the search space, nested searches, and/or predetermined and redefined Search parameters to locate the best match as quickly as possible. In any case, after the motion estimator 29 has performed all the tasks of the iteration (No branch of 199), the video encoder 18 encodes the current macroblock (200). Advantageously, the video encoder has various options during the encoding process. At this time, the difference between various candidate macroblocks in the search space is generated, and the difference between the candidate macroblocks is also generated.

Using four independent motion vectors corresponding to the best candidate microblocks can be used to encode the macroblocks to improve compression. For other reasons, it is better to use a single motion vector corresponding to the best candidate macroblock, such as to maintain compatibility with a decoder that can only recognize macroblock motion vectors. Texture coding can also be added, such as by performing discrete cosine transform (DCT) coding on a matrix that defines the difference between the current macroblock to be coded and the video block defined by the motion vector.

After the current macroblock is coded, the video encoder 18 can determine whether there are other macroblocks to be coded in the current video frame, that is, whether other iterations are to be performed (201). If not, the encoding process of a given video frame ends (No branch of 201), and the encoded video blocks of the frame can be transmitted by the transmitter 20 via the communication medium 15 (FIG. 1). However, if there are other macroblocks to be encoded in the current video frame, the search space can be reloaded (202) and the next iteration (191) can be started. In addition, the process of reloading the search space (202) can use the column update technique described above, in which the memory control unit reloads a subset of the columns of the candidate memory 38 and tracks the candidate memory through the addressing scheme described above. These and other technologies described here, regardless of whether stand-alone technology is used to improve the various traditional encoding processes, or when they are used in combination, can improve the efficiency of video encoding in accordance with standards such as MPEG-4, and it is more convenient to use more computing resources. Video encoding is implemented in wireless communication devices that are limited and power consumption is a problem, such as mobile phones.

A number of different embodiments have been described. These technologies can improve video encoding by reducing storage transfers, computing cycles, and power consumption, thereby speeding up the encoding process and potentially extending the life of battery-powered video devices. In addition, these technologies can provide options in the encoding process by generating the difference between macroblocks and microblocks without requiring additional AD calculations. Among these or possibly other methods, these techniques can improve video coding in accordance with standards such as MPEG-4 or other video coding standards.

These technologies can be implemented in hardware, software, firmware, or any combination. If implemented in software, these technologies may involve a computer-readable medium that includes program code, and when the program code is executed in a device that encodes a video sequence in accordance with the MPEG-4 standard, it performs one or more of the above-mentioned methods. In this case, the computer-readable medium may include random access memory (RAM), such as synchronous dynamic random access memory (SDRAM), read-only memory (ROM), non-volatile random access memory (NVRAM), Electrically erasable programmable read-only memory (EEPROM), flash memory, etc.

The program code can be stored in the memory in the form of computer readable instructions. In this case, a processor, such as a DSP, can execute instructions stored in a memory to implement one or more of the techniques described herein. In some cases, the DSP implements these techniques, and the DSP calls various hardware components, such as a motion estimator, to speed up the encoding process. In other embodiments, the video encoder may be implemented with a microprocessor, one or more application specific integrated circuits (ASIC), one or more field programmable gate arrays (FPGA), or some other hardware-software combination. These or other embodiments are within the scope of the following claims.