# Patent

## Title
System and method for enabling the fast extraction of interleaved image data

## Abstract

An improved system and method for deinterleaving a data unit containing chunks of two or more different data types. In an embodiment of the invention, both a device MPU and DMA hardware are used to deinterleave a data unit containing chunks of both compressed data and uncompressed data. The device MPU is used to transfer compressed data from an interleaved data buffer to a compressed data buffer, while the DMA hardware is used to transfer uncompressed data from the interleaved data buffer to a compressed data buffer. By using both the MPU and the DMA hardware, the overall efficiency of the data transfer process is improved.

## Background
FIELD OF THE INVENTION
The present invention relates generally to the processing of data in electronic devices. More particularly, the present invention relates to the deinterleaving of different types of data in mobile electronic devices such as mobile telephones with built-in camera modules.
BACKGROUND OF THE INVENTION
In recent years, mobile telephones have increasingly become equipped with built-in camera modules. These camera modules enable a user to take a digital photograph and quickly transmit it to friends and family.
A generic digital camera system that is part of a mobile telephone or other electronic device is shown at 10 in FIG. 1. The digital camera 10 includes a housing 11 which contains at least one lens 12 and at least one image sensor 18 which is operatively connected to a memory unit 14 and a processor or controller 16, both of which are located outside of the camera module 10 and inside of the mobile telephone or other electronic device within which the camera module 10 is housed. The memory unit 14 can be used to store digital images and computer software for performing various functions in the digital camera 10, as well as to implement the present invention. The image sensor 18 can be a charge coupled device (CCD), a complementary metal oxide semiconductor (CMOS), or another system.
Camera modules that are used in mobile telephones are commonly designed to be both small and inexpensive for many reasons. As a consequence of this fact, a typical image sensor 18 does not include any frame memory within the camera module 10. Instead, the image data from a captured image must be output to the telephone engine as soon as it is read from the sensor. Otherwise, the image data would be lost. The image sensor 18 is typically read in a line-by-line fashion, and the data is sent in the same order to the telephone engine, where there exists sufficient memory for storing the data.
In order to reduce the bandwidth needed for transmission of the image data between the camera module 10 and telephone engine, the image sensor 18 often compresses the data before sending it any further. In order to reduce the processing requirements in the telephone engine, many camera modules use JPEG compression at this stage, as the images would likely end up in a JPEG format in any case so that the telephone engine does not need to consume additional time for JPEG encoding.
From a usability perspective, it is not sufficient for the camera images to only be processed and saved to memory. This is because the end-user would also like to view the image he or she has just taken on the screen of the telephone, for example, to decide whether or not the image was of a satisfactory quality. It is also desirable from the user's perspective for there not be any additional delay in showing the preview image to the user.
Unfortunately, however, making a preview image out of the compressed data is not an immediate operation, but instead inevitably takes some additional time. There are a number of different potential solutions to this issue, but each possesses serious drawbacks of its own. One such solution involves allowing the camera module 10 to output the data of the captured image in such a format to allow the quick construction of the smaller preview image that is to be shown on the telephone display. In practice, this means using an uncompressed format for the image data. The problem in this approach, however, is that with higher resolution cameras, there might not be enough bandwidth to transfer the data.
Another potential solution to this problem is to use a camera module that includes sufficient frame memory to permit the same image to be transmitted twice, first as an image with proper size for the display, and then a full resolution image for saving purposes. The problem with this approach is that additional memory is simply too expensive to practically implement this solution.
Another potential solution to the problem discussed above involves interleaving a compressed image for saving and an uncompressed preview image for viewing. Even though there is no memory for a whole image frame in the camera module, a JPEG encoder in the camera requires that there be memory for 8 lines of the image. This makes it possible to interleave the uncompressed preview image data within the compressed full resolution image data. Because the preview data is intended for the mobile telephone's display (whose resolution is substantially lower than the one of the camera sensors), the interleaving of the downscaled preview image does not increase the bandwidth requirements by a large amount. The process of interleaving, where two types of data are split into chunks and sent one after another, is depicted in FIG. 2. In FIG. 2, the white and black diamonds represent specific markers that mark the beginning of each type of chunk. In practice, the markers must be chosen so that they cannot appear in the data itself. Alternatively, one could include information about the length of the chunk into each marker. However, in JPEG encoding, for example, it is generally not possible to know the size of the output data before the encoding has taken place. The camera should therefore be equipped with additional buffers for this approach.
Transmitting all of the data of one image frame requires the transmission of several chunks of preview data and compressed data. One chunk can contain as much information as the camera module is able to buffer at any given time. For example, if a JPEG encoder requires that 8 lines must be available in a buffer of some sort, then it is possible to use chunks that contain data at least for those 8 lines. It should be noted that there might be some additional buffering capability as well in the camera module.
FIG. 2 also illustrates how chunks of preview image data always have the same length, while the length of compressed data chunks may vary. This is because the compression efficiency depends upon the image content and can vary even within one single image. The preview data, on the other hand, is uncompressed and there is therefore always the same amount of preview data to be sent in one chunk. For this reason, the markers after the preview data chunks (at the beginning of the compressed data chunks) are not obligatory, as it is the length of the preview data chunk is always known.
Although the interleaving of compressed and uncompressed data addresses many of the issues that arise in the other potential solutions discussed previously, it still has a significant deficiency. With this approach, even though compressed data is available for storing purposes and preview data available for displaying purposes, the interleaved data must first be deinterleaved before it can be used. In other words, the compressed data must be extracted from the preview data, or the preview data must be extracted from compressed data, before the compressed data can be saved and the preview data can be viewed.
In most conventional mobile telephones with a built-in camera module, once all of the image data has been received into a memory inside the telephone engine, it is processed or copied further by the phone processor in such a way that all of the data contained within the image is addressed in turn. In the case of interleaved data, the data is copied into one of the two buffers upon processing. One buffer is dedicated for storing the preview (uncompressed) data, and the other buffer is dedicated for storing the compressed data. It should be noted that in practice, one of these two buffers may be the same as the original buffer, in case the original interleaved data is no longer needed but can be overwritten. However, this process takes consumes both time and processing power.
It would therefore be desirable to develop a system that enables the more rapid and efficient transmission and availability of both compressed and uncompressed image data in a mobile telephone or other electronic device.
SUMMARY OF THE INVENTION
The present invention report provides a system and method for efficiently deinterleaving interleaved data by using a combination of a micro processor unit (MPU) and direct memory access (DMA) hardware. Because both the MPU and DMA hardware are used for processing the data at the same time, the overall processing time may be decreased significantly depending upon the relative lengths of the chunks of the compressed data and the preview data.
The present invention provides for a number of advantages over conventional systems. With the present invention, the MPU does not need to process the preview data at all; it can skip all of the preview data chunks whose size is known beforehand. As a result, the MPU has more time to perform other functions in the system. In addition, because the DMA hardware and MPU both process data at the same time, deinterleaving finishes much more quickly than in the traditional MPU-only solution. Still further, once the DMA hardware is properly configured, there is little need for additional configurations during the operation. In an optimal situation—depending upon the DMA hardware—one only needs to indicate the new read address and reenable the transfer of data. The present invention can be used in conjunction with a wide variety of types of interleaved data, where of one type have fixed length, and is not only limited to image data.
These and other advantages and features of the invention, together with the organization and manner of operation thereof, will become apparent from the following detailed description when taken in conjunction with the accompanying drawings, wherein like elements have like numerals throughout the several drawings described below.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a sectional side view of a generic digital camera system;
FIG. 2 is a representation showing how both compressed data and uncompressed image preview data can be interleaved for transfer from an image sensor to a telephone engine;
FIG. 3 is a perspective view of an electronic device that can incorporate the principles of the present invention;
FIG. 4 is a schematic representation of the circuitry of the electronic device of FIG. 3;
FIG. 5 is a representation of the various components involved in the implementation of one embodiment of the present invention; and
FIG. 6 is a flow chart showing the implementation of one embodiment of the present invention.



DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
The present invention provides for a system of deinterleaving interleaved compressed and uncompressed image data by using a combination of MPU and DMA processing capability. As the MPU and DMA hardware process the data at the same time, the overall processing time may decreased by fifty percent or more depending upon the relative lengths of the chunks of the compressed data and the preview data.
FIGS. 3 and 4 show one representative mobile telephone 112 upon which the present invention may be implemented. However, it is important to note that the present invention is not limited to any type of electronic device and could be incorporated into devices such as personal digital assistants, personal computers, and other devices. It should be understood that the present invention could be incorporated on a wide variety of mobile telephones 112. The mobile telephone 112 of FIGS. 2 and 3 includes a housing 130, a display 132 in the form of a liquid crystal display, a keypad 134, a microphone 136, an ear-piece 138, a battery 140, an infrared port 142, an antenna 144, a smart card 146 in the form of a universal integrated circuit card (UICC) according to one embodiment of the invention, a card reader 148, radio interface circuitry 152, codec circuitry 154, the controller 16 and the memory unit 14. Individual circuits and elements are all of a type well known in the art, for example in the Nokia range of mobile telephones.
FIG. 5 is a representation of the various components involved in the implementation of one embodiment of the present invention. FIG. 5 shows an interleaved data buffer 200, a compressed data buffer 210, and an uncompressed data buffer 220. It should be noted that either the compressed data buffer 210 or the uncompressed data buffer 220 may use the same memory area as the interleaved data buffer 200 if the original data is no longer needed after transmission and can be overwritten. Each of the interleaved data buffer 200, the compressed data buffer 210 and the uncompressed data buffer 220 can be included in the memory unit 14 of the electronic device shown in FIGS. 3 and 4. The system also includes a MPU 230 and DMA hardware 240. The MPU 230, which can comprise the controller 16 of the system shown in FIG. 4, is used to execute the system software, as well as carry out the operations specified by the system software. The DMA hardware 240 is a hardware controller that is capable of moving data from one place in the memory to another place in the memory independent from the MPU 230. It should be noted that the MPU 230, the DMA hardware 240 and the memory unit 14 can comprise separate components, or they can be combined into a single integrated circuit.
FIG. 6 is a flow chart showing the implementation of one embodiment of the present invention. Step 300 in FIG. 6 represents the starting point for the deinterleaving of a data unit. At this point, an image has been captured and the interleaved data buffer 200 contains the original interleaved data unit. The compressed data buffer 210 and the uncompressed data buffer 220 have been reserved for storing the compressed data and preview data in concatenated form, accordingly. Those DMA configurations that do not change in the course of the operation are also performed at this point.
At step 310 in FIG. 6, and assuming that the data unit begins with compressed data, the MPU 230 begins to examine the interleaved data unit from the beginning of the data unit. The MPU 230 searches for a marker that indicates where the next preview data chunk begins. While performing this action, the MPU 230 copies the compressed data to the compressed data buffer 210 up to, but not including, the marker that indicates the beginning of the preview data. It should be noted that, if the data unit begins with preview data, this step is skipped.
At step 320, the DMA hardware 240 is initialized to perform a memory-to-memory copy from the newly-found beginning of the preview data to the uncompressed data buffer 220. It should be noted that the markers are not included in this memory copy. The size of the DMA transfer is known, as it is the fixed size of the preview data chunk.
At step 330 and as the DMA hardware 240 is transferring data in the background, the MPU 230 skips the preview data chunk (as its size was known) and starts examining the data that follows the now-skipped preview chunk. In case the optional marker for compressed data is expected and found, or in case the optional marker is not used, but there is more data to process, the MPU 230 will continue to examine the data until a marker for preview data is found. While performing this action, the MPU 230 copies the compressed data to the compressed data buffer 210, placing it immediately after the data that was previously moved to the compressed data buffer 210.
At step 340, either one can assume that the DMA hardware 240 has finished copying the image data chunk that was being copied at step 320, or the system can specifically check the status of the DMA hardware 240 and can wait until the transfer is finished. In either of the above events, the DMA hardware 240 is reinitialized to perform a memory-to-memory copying for the next preview data chunk, copying the data to the uncompressed data buffer 220, placing it immediately after the data that was previously moved to the uncompressed data buffer 220.
It should be noted that because DMA hardware is in particular designed for moving data quickly, and since MPU has to additionally examine the data it is copying, the DMA hardware 240 should be able to process more data in the same time period than the MPU 230. In case there is a risk that the DMA transfer is not finished at the point where new a DMA transfer should be initiated, an alternative solution involves using two or more DMA channels so that consecutive DMA requests are always made for different channels.
At step 350, it is determined whether the entire data unit has been copied. If the entire data unit has been copied, then the preview image can be displayed at step 360, and the compressed data is saved in the compressed data buffer 210. If the entire data unit has not been copied, then steps 330 and 340 are repeated until the entire data unit has been processed and placed in the compressed data buffer 210 and the uncompressed data buffer 230, respectively.
As mentioned previously, the process depicted in FIG. 6 can also work in the situation where the compressed data buffer 210 is the same as the interleaved data buffer 200. It should be noted that, if the data unit is ordered as depicted in FIG. 2, the MPU 230 will begin overwriting the first preview data chunk at about at the same time as the DMA hardware 240 is transferring that data chunk to the uncompressed data buffer 220. In most cases, however, it can be safely assumed that the DMA hardware 240 operates faster than the MPU 230, as the DMA hardware 240 can blindly copy the data and does not have to spend any time analyzing it. Therefore, the DMA hardware 240 is able to read the preview data before it is overwritten by compressed data from the next chunk.
Because the size of the DMA transfer is always the same, initializing a new DMA transfer may only require two actions after the initial configuration is made. The first action is configuring the DMA read start address, while the second action is enabling the DMA transfer. This assumes that the DMA hardware 240 contains a write pointer that is automatically incremented while the transfer progresses. The write pointer therefore automatically points to the correct location in the uncompressed data buffer 220 when the next preview data chunk is copied.
In an alternative embodiment of the invention, there are data chunks of more than two different types. In this situation, the MPU 230 can handle all of the chunks whose size can vary, while the DMA hardware 240 continues to take care of all fixed size chunks. More than one DMA channel in the DMA hardware 240 can be used if there is more than one type of chunks with a fixed length. These multiple channels are used in order to ensure that there is no need to wait for the completion of one DMA transfer before the next transfer can begin, as each DMA channel can operate independent of other channels.
It should be noted that a wide variety of chunk markers may be used in conjunction with the present invention, and that the present invention is not limited to any specific type of marker. In addition, even though chunk markers have been used in the beginning of each chunk in the process depicted in FIG. 6, the markers could be also be used at the end of each chunk or both at the beginning and at the end of each chunk.
The present invention is described in the general context of method steps, which may be implemented in one embodiment by a program product including computer-executable instructions, such as program code, executed by computers in networked environments.
Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. Computer-executable instructions, associated data structures, and program modules represent examples of program code for executing steps of the methods disclosed herein. The particular sequence of such executable instructions or associated data structures represents examples of corresponding acts for implementing the functions described in such steps.
Software and web implementations of the present invention could be accomplished with standard programming techniques with rule-based logic and other logic to accomplish the various database searching steps, correlation steps, comparison steps and decision steps. It should also be noted that the words “component” and “module” as used herein, and in the claims, is intended to encompass implementations using one or more lines of software code, and/or hardware implementations, and/or equipment for receiving manual inputs.
The foregoing description of embodiments of the present invention have been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the present invention to the precise form disclosed, and modifications and variations are possible in light of the above teachings or may be acquired from practice of the present invention. The embodiments were chosen and described in order to explain the principles of the present invention and its practical application to enable one skilled in the art to utilize the present invention in various embodiments and with various modifications as are suited to the particular use contemplated.

## Claims

1. A method of processing an interleaved data unit including a plurality of data chunks of a first type comprising compressed data and a plurality of data chunks of a second type comprising uncompressed data, the method comprising:
using a microprocessor unit to copy a first data chunk of the first type in the interleaved data unit to a first data buffer comprising a compressed data buffer, wherein the chunks of data of the first type comprise compressed image data of an image;
using direct memory access hardware to copy a first data chunk of the second type in the interleaved data unit to a second data buffer comprising an uncompressed data buffer distinct from the compressed data buffer, wherein the chunks of data of the second type comprise uncompressed image preview data of the image;
upon completion of copying the first data chunk of the first type, using the microprocessor unit to copy the next data chunk of the first type in the interleaved data unit to the first data buffer while the direct memory access hardware is completing the copying of the first data chunk of the second type;
after the completion of copying the first data chunk of the second type, using the direct memory access hardware to copy the next data chunk of the second type in the interleaved data unit to the second data buffer; and
continuing to use the microprocessor unit and the direct memory access hardware to copy subsequent data chunks of the first type and the second type, respectively, of the interleaved data unit to the first data buffer and the second data buffer until all data chunks in the interleaved data unit have been copied, wherein the plurality of data chunks of the first type and the second type are copied from an interleaved data buffer; and
after all data chunks of the second type in the interleaved data unit have been copied to the second data buffer, using the uncompressed image preview data to display an image to a user.

2. The method of claim 1, wherein the copying of data chunks of the first type in the interleaved data unit to the first data buffer includes using the microprocessor unit to search for a marker that indicates where the next uncopied data chunk of the first type begins.

3. The method of claim 1, wherein the interleaved data buffer comprises the first data buffer, and wherein individual data chunks of the second type are overwritten on the interleaved data buffer during the copying of data chunks of the first type.

4. The method of claim 1, wherein the interleaved data unit is generated from the capturing of an image by a camera module.

5. The method of claim 1, wherein the plurality of data chunks of the first type comprise chunks of data having nonuniform lengths.

6. A non-transitory computer readable medium embodied with instructions for processing an interleaved data unit including a plurality of data chunks of a first type comprising compressed data and a plurality of data chunks of a second type comprising uncompressed data, the instructions comprising:
computer code for using a microprocessor unit to copy a first data chunk of the first type in the interleaved data unit to a first data buffer comprising a compressed data buffer, wherein the chunks of data of the first type comprise compressed image data of an image;
computer code for using direct memory access hardware to copy a first data chunk of the second type in the interleaved data unit to a second data buffer comprising an uncompressed data buffer distinct from the compressed data buffer, wherein the chunks of data of the second type comprise uncompressed image preview data of the image;
computer code for upon completion of copying the first data chunk of the first type, using the microprocessor unit to copy the next data chunk of the first type in the interleaved data unit to the first data buffer while the direct memory access hardware is completing the copying of the first data chunk of the second type;
computer code for, after the completion of copying the first data chunk of the second type, using the direct memory access hardware to copy the next data chunk of the second type in the interleaved data unit to the second data buffer; and
computer code for continuing to use the microprocessor unit and the direct memory access hardware to copy subsequent data chunks of the first type and the second type, respectively, of the interleaved data unit to the first data buffer and the second data buffer until all data chunks in the interleaved data unit have been copied, wherein the plurality of data chunks of the first type and the second type are copied from an interleaved data buffer; and
computer code for, after all data chunks of the second type in the interleaved data unit have been copied to the second data buffer, using the uncompressed image preview data to display an image to a user.

7. The computer program product of claim 6, wherein the copying of data chunks of the first type in the interleaved data unit to the first data buffer includes using the microprocessor unit to search for a marker that indicates where the next uncopied data chunk of the first type begins.

8. The computer program product of claim 6, wherein the interleaved data buffer comprises the first data buffer, and wherein individual data chunks of the second type are overwritten on the interleaved data buffer during the copying of data chunks of the first type.

9. An electronic device, comprising:
a microprocessor unit; a memory unit operatively connected to the multiprocessor unit, the memory unit including a first data buffer comprising a compressed data buffer and a second data buffer comprising an uncompressed data buffer distinct from the compressed data buffer; and
direct memory access hardware operatively connected to the memory unit,
wherein the memory unit includes a computer program product for processing an interleaved data unit including a plurality of data chunks of a first type comprising compressed image data of an image, and a plurality of data chunks of a second type comprising uncompressed image preview data of the image, the computer program product comprising:
computer code for using the microprocessor unit to copy a first data chunk of the first type in the interleaved data unit to the first data buffer;
computer code for using the direct memory access hardware to copy a first data chunk of the second type in the interleaved data unit to the second data buffer;
computer code for upon completion of copying the first data chunk of the first type, using the microprocessor unit to copy the next data chunk of the first type in the interleaved data unit to the first data buffer while the direct memory access hardware is completing the copying of the first data chunk of the second type;
computer code for, after the completion of copying the first data chunk of the second type, using the direct memory access hardware to copy the next data chunk of the second type in the interleaved data unit to the second data buffer; and
computer code for continuing to use the microprocessor unit and the direct memory access hardware to copy subsequent data chunks of the first type and the second type, respectively, of the interleaved data unit to the first data buffer and the second data buffer until all data chunks in the interleaved data unit have been copied, wherein the plurality of data chunks of the first type and the second type are copied from an interleaved data buffer; and
computer code for, after all data chunks of the second type in the interleaved data unit have been copied to the second data buffer, using the uncompressed image preview data to display an image to a user.

10. The electronic device of claim 9, wherein the copying of data chunks of the first type in the interleaved data unit to the first data buffer includes using the microprocessor unit to search for a marker that indicates where the next uncopied data chunk of the first type begins.

11. The electronic device of claim 9, wherein the interleaved data buffer comprises the first data buffer, and wherein individual data chunks of the second type are overwritten on the interleaved data buffer during the copying of data chunks of the first type.

12. An integrated circuit, comprising:
a microprocessor portion; a memory portion operatively connected to the multiprocessor portion, the memory portion including a first buffer comprising a compressed data buffer and a second buffer comprising an uncompressed data buffer distinct from the compressed data buffer; and
a direct memory access hardware portion operatively connected to the memory portion, wherein the memory portion includes a computer program product for processing an interleaved data unit including a plurality of data chunks of a first type and a plurality of data chunks of a second type, comprising:
computer code for using the microprocessor portion to copy a first data chunk of the first type in the interleaved data unit to the first buffer, wherein the plurality of data chunks of the first type comprise compressed image data of an image;
computer code for using the direct memory access hardware portion to copy a first data chunk of the second type in the interleaved data unit to the second buffer, wherein the chunks of data of the second type comprise uncompressed image preview data of the image;
computer code for upon completion of copying the first data chunk of the first type, using the microprocessor portion to copy the next data chunk of the first type in the interleaved data unit to the first buffer while the direct memory access hardware is completing the copying of the first data chunk of the second type;
computer code for, after the completion of copying the first data chunk of the second type, using the direct memory access hardware portion to copy the next data chunk of the second type in the interleaved data unit to the second buffer; and
computer code for continuing to use the microprocessor portion and the direct memory access hardware portion to copy subsequent data chunks of the first type and the second type, respectively, of the interleaved data unit to the first buffer and the second buffer until all data chunks in the interleaved data unit have been copied, wherein the plurality of data chunks of the first type and the second type are copied from an interleaved data buffer; and
computer code for, after all data chunks of the second type in the interleaved data unit have been copied to the second data buffer, using the uncompressed image preview data to display an image to a user.