Patent Publication Number: US-8112558-B2

Title: Frame buffer management program, program storage medium and management method

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is based upon and claims the benefit of priority from the prior Japanese Patent Application No. 2005-315081 filed on Oct. 28, 2005, the entire contents of which are incorporated herein by reference. 
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to a method for managing a plurality of frame buffers storing moving image data, and more particularly to a method for managing a plurality of frame buffers storing replayed image data obtained by a decoding process in the decoding system of moving image data compressed and encoded according to a variety of standards, such as MPEG and the like. 
     2. Description of the Related Art 
     As a standard specification concerning moving image compression and encoding, a variety of standards such as H.261 corresponding to ISDN moving image transfer, H.262 corresponding to broadcast media moving images, H.263 corresponding to the existing telephone network television telephone, MPGE-1 corresponding to storage media moving images, MPEG-2 as the same standard as H.262, MPEG-4 corresponding to multimedia, such as computer, communication, broadcasting, home appliance, etc. are used. In a system for decoding stream data encoded based on such a standard, a lot of frame buffers for storing replayed image data obtained by a decoding process, and after storing the image data of each frame in a frame buffer, the image data is displayed, for example, on a display screen. 
     However, since the volume of moving image data is usually enormous and the number of frame buffers for storing it is limited, the vacancy of a frame buffer must be appropriately managed and image data must be stored. Conventionally, for example, a flag for indicating whether a frame buffer stores data is provided, frame buffers are all retrieved and data is stored in a vacant frame buffer. However, there are a lot of frame buffers and when a vacant frame buffer is found near the end of the retrieval, the retrieval takes a lot of time. 
     As the prior art of a storage area management method for memory, such as a frame buffer or the like, Patent reference 1 discloses a technology capable of solving a problem that, in the management of the working area of frame memory or the like, an area cannot be assigned, depending on a required shape even when there is space sufficient to satisfy a requirement on memory and the efficiency in use of the working area degrades. 
     Patent reference 2 discloses a technology in which in a method for managing a memory area in units of rectangles, a memory management table corresponding to an adjacent area is provided with a left connection pointer and an upper connection point and an area of an arbitrary size can be used. 
     Patent reference 1: Japanese Patent Application Publication No. H3-44747 “Memory Management Processing Method” 
     Patent reference 2: Japanese Patent Application Publication No. H3-154973 “Memory Management Method” 
     However, when a frame buffer storing valid data and a vacant frame buffer are arrayed at random, such prior arts cannot improve the retrieval speed of a frame buffer in which data is subsequently stored or whose data is replayed. 
     SUMMARY OF THE INVENTION 
     It is an object of the present invention to provide a frame buffer management program capable of searching for a frame buffer which stores subsequent data or to from which a subsequent replayed image is read in high speed even when a vacant frame buffer which stores no valid data and a frame buffer in use which stores valid data are arrayed at random in a worm-eaten state and its management method. 
     The program of the present invention enables a computer to execute a process of preparing an area in which the data of a valid chain indicating a connection among frame buffers storing valid image data of a plurality of frame buffers and the data of a vacant chain indicating a connection among frame buffers storing no valid image data, is stored, on memory at the first step, and generating/updating the data of the valid chain and the data of the vacant chain and storing it in the memory when valid image data is stored in one of the plurality of frame buffers in a subsequent step. 
     When image data stored in one of the plurality of frame buffers becomes unnecessary, the program of the present invention can further enable a computer to execute a process of releasing a frame buffer storing the data and a process of updating the data of the valid chain and the data of the vacant chain and storing it in the memory. 
     In the present invention, a computer-readable portable storage medium on which this frame buffer management program is recorded can also be used and a frame buffer management method for preparing an area in which the data of a valid chain and the data of a vacant chain is stored in memory according to the frame buffer management program of the present invention, and generating/updating the data of the valid chain and the data of the vacant chain and storing it in the memory when valid image data is stored can be further used. 
     According to the present invention, even when a vacant frame buffer and a frame buffer storing valid data are arrayed at random in a worm-eaten state, a frame buffer to store subsequent data can be searched for in high speed or image data to be subsequently replayed can be obtained in high speed in fast-forward replay and rewind replay, thereby facilitating the frame buffer management in a moving image decoding system and improving its control speed. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is the basic functional block diagram of the frame buffer management program of the present invention. 
         FIG. 2  shows an example of the configuration of a moving image replay system using the frame buffer management method of the present invention. 
         FIG. 3  shows an example of a video decoder shown in  FIG. 2 . 
         FIG. 4  is a flowchart showing the entire moving image replay process of the system shown in  FIG. 2 . 
         FIG. 5  explains a method for storing data in a frame buffer (No.  1 ). 
         FIG. 6  explains a method for storing data in a frame buffer (No.  2 ). 
         FIG. 7  explains a method for storing data in a frame buffer (No.  3 ). 
         FIG. 8  explains a method for storing data in a frame buffer (No.  4 ). 
         FIG. 9  explains a method for storing data in a frame buffer (No.  5 ). 
         FIG. 10  explains a method for deleting data from a frame buffer. 
         FIG. 11  shows an example of the storage of common data corresponding to each block in a valid chain and a vacant chain. 
         FIG. 12  shows an example of the storage of individual data corresponding to each block in a valid chain and a vacant chain. 
         FIG. 13  is a detailed flowchart showing a chain update process at the time of storing data in a frame buffer. 
         FIG. 14  is a detailed flowchart showing a chain update process at the time of deleting data from a frame buffer. 
         FIG. 15  explains the loading of a program for realizing the present invention onto a computer. 
     
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       FIG. 1  is the basic functional block diagram of the frame buffer management program of the present invention.  FIG. 1  is the basic functional block diagram of a program used by a computer managing a plurality of frame buffers. 
     In  FIG. 1 , firstly in step S 1  of the program of the present invention, an area in which the data of a valid chain indicating a connection among frame buffers storing valid image data of a plurality of frame buffers and the data of a vacant chain indicating a connection among frame buffers storing no valid image data, is stored, is prepared on memory. In step S 2 , when valid image data is stored in one of the plurality of frame buffers, the data of a valid chain and the data of a vacant chain is generated/updated and are stored in the memory. 
     In the preferred embodiment of the present invention, when image data stored in one of the plurality of frame buffers becomes unnecessary, further a frame buffer storing the data can be released, and also the data of the valid chain and the data of the vacant chain can be updated and stored in memory. 
     In the preferred embodiment of the present invention, a computer-readable portable storage medium on which this frame buffer management program is recorded can also be used and a frame buffer management method for preparing an area in which the data of a valid chain and the data of a vacant chain is stored in memory according to the frame buffer management program of the present invention, and generating/updating the data of the valid chain and the data of the vacant chain and storing it in the memory when valid image data is stored can be further used. 
       FIG. 2  shows an example of the configuration of a moving image replay system using the frame buffer management method of the present invention. This system outputs MPEG bit stream recorded on a DVD  10  to video and audio output equipment. 
     The MPEG bit stream data recorded on the DVD  10  in  FIG. 2  is inputted to a video/audio separation unit  12  via a user interface unit  11 . The separated audio data and video data are provided to an audio decoder  13  and a video decoder  14 , respectively, and the decoding results of these decoders are replayed by a speaker  16  and a TV  17 , respectively, via an OS/driver unit  15 . 
     The frame buffer management method of the present invention is relates to the management method of moving image data decoded by the video decoder  14 . The internal configuration of the video decoder is described with reference to  FIG. 3 . In  FIG. 3 , variable-length decoding is applied to the data of a bit stream  20  by a VLD  21 , inverse quantization is applied to the data by an IQ  22 , inverse discrete cosine transform is applied to the data by an IQ  22 , inverse discrete cosine transform is an adder  24 . Motion compensation is applied to the output of the VLD  21  by a MC  25 , the compensated result is added to the output of the IDCT  23  by the adder  24  and is outputted as moving image data  26 . 
       FIG. 4  is a flowchart showing the entire moving image replay process of the system shown in  FIG. 2 . A process in the case where a replay button is pushed in  FIG. 4  and there is a possibility that rewind button may be pushed in the middle of video data repay is described below. 
     Firstly, in step S 10 , when it is determined that the replay button is pushed, in step S 11  bit stream data is read from the DVD  10 . Then, in step S 12 , the video/audio separation unit  12  separates video data from audio data. Then, in step S 13 , the video decoder  14  decodes the video data. Then, in step S 14 , moving image data as a decoded result is registered (stored) in a frame buffer. Then, in step S 15 , the decoded result is outputted to the TV  17 . The detailed process of registration of the valid chain after storing the decoded result in a frame buffer in step S 14 , that is, the process in step S 2  of  FIG. 1  will be described later. Furthermore, it is assumed that the process in step S 1  of  FIG. 1  is performed as the initialization process of the system prior to the process shown in  FIG. 4 . 
     Then, in step S 16  it is determined whether a buffer is nearly full, specifically, whether moving image data as a decoded result is stored in most of the plurality of frame buffers. If the buffer is nearly full, in step S 17  the process proceeds to a process in step S 18  after the old decoded result (moving image data) is deleted from the frame buffer. If the buffer is not nearly full, immediately the process proceeds to a process in step S 18 . In this case, although moving image data as a decoded result is deleted in ascending order of time, it is assumed that in rewinding, which will be described later, is deleted in descending order of time. 
     In step S 18  it is determined whether a rewind button is pushed. If the rewind button is not pushed, the processes in steps S 11  and after are continued and data replay is continued. If it is determined that the rewind button is pushed, in step S 19  moving image data as a decoded result to be replayed in the future is deleted from the frame buffer. 
     Specifically, generally a bit stream is read prior to the output of a decoded result during replay, the data read prior to the output is decoded and is stored in advance in a frame buffer. However, when the rewind button is pushed, such data is deleted from a buffer as unnecessary one. The update process of a valid chain or the like in the case where data is deleted from a frame buffer, including the data deletion in step S 17 , will also be described later. 
     After the future decoded result is deleted in step S 19 , in step S 20  it is determined whether there is a displayable frame in a frame buffer, that is, valid data. If there is such data, the processes in steps S 15  and after are repeated. If there is no such data, the processes in steps S 11  and after are repeated. In order to keep displaying data when there is no valid data while the rewind button is pushed, the processes in steps S 11  and after are repeated. 
     Next, the basic operation of the frame buffer management method of this preferred embodiment is described with reference with  FIGS. 5-10 . In this example, the frame buffer management method is described assuming that m frame buffers,  1 - m  exist. 
       FIG. 5  shows an initial status. In this initial status, m frame buffers are vacant, that is, unused, and these frame buffers are connected by a vacant chain indicating the data storage order of frame buffers storing no decoded results. This vacant chain is represented by a dotted line, and, for example, variables N 2  indicating one after frame buffer  1  and N 3  indicating one after frame buffer  2  indicate frame buffers  2  and  3 , respectively. 
     In  FIG. 6 , decoded data is stored in frame buffer  1  in the status shown in  FIG. 5 . In this status, a vacant chain indicated by a dotted line connects frame buffers  2 - m , while only frame buffer  1  is connected to a valid chain indicated by a solid line for frame buffers storing decoded results. A variable N 1  indicating one after frame buffer  1  indicates the frame buffer itself. 
     In  FIG. 7 , data is stored in frame buffer  2 . In this case, frame buffers  1  and  2  are connected by a valid chain, while frame buffers  3 - m  are connected by a vacant chain. 
     In  FIGS. 8 and 9 , decoded data is stored in frame buffers  1 - 3  and  1 - 4 , respectively, and each of the connections of valid and vacant chains is modified. 
     In  FIG. 10 , the decoded data stored in frame buffer  3  in  FIG. 9  is deleted and frame buffer  3  is released. Therefore, a valid chain connects frame buffers  1 ,  2  and  4 , while a vacant chain connects frame buffers  5 - m  and  3 . At this moment, frame buffer  5  in which data is to be stored after frame buffer  4  in the original decoded data storage order in the initial status is a frame buffer at the top of a vacant chain, and released frame buffer  3  is located at the end of the vacant chain. Assuming such a status, the preferred embodiment is described herein after. 
     As described above with reference to  FIGS. 5-10 , every time decoded data is stored in a frame buffer or deleted from it, valid and vacant chains are updated. Before describing the flowcharts of these update processes, a data storage format used for that process is described with references to  FIGS. 11  and  12 . In this description it is assumed that valid and vacant chains connect blocks corresponding to m frame buffers one to one in  FIGS. 5-10  and that each block number corresponds to a frame buffer number one to one. It is assumed that in  FIGS. 11 and 12 , 10 numbers of 0-9 are used. 
       FIG. 11  shows an example of the storage of common data corresponding to each block in each chain. In this example, the number of blocks connected by a valid chain, the number of blocks connected by a vacant chain and the respective leading block numbers of valid and vacant chains are stored. The initial status where all frame buffers are vacant as shown in  FIG. 5 , a status where data is registered in frame buffer  0 , a status where data is registered in frame buffers  0  and  1 , . . . and so on are shown rightward in that order, and the common data in the case where data is stored in all frame buffers is shown at the rightmost end. These data transition will be described later with reference to the flowcharts shown in  FIGS. 13 and 14 . 
       FIG. 12  shows an example of the storage of block individual data corresponding to each block in each chain. In this example, PREV and NEXT data is stored in addition to data indicating whether each of blocks # 0 -# 9  is used or unused, specifically, whether decoded data is stored in corresponding buffer memory, frame data and time information about frame data. In this case, PREV indicates a block number corresponding to a frame buffer located before a valid or vacant chain, and NEXT indicates a block number corresponding to a subsequent frame buffer in a chain. The transition of these values will be described later with reference to the flowcharts shown in  FIGS. 13 and 14 . 
     By using data shown in  FIGS. 11 and 12 , the structures of valid and vacant chains can be clarified. For example, in the initial status corresponding to  FIG. 5 , the number of blocks of a valid chain is “0” and there is no valid chain. The number of blocks of a vacant chain is “10” and all blocks are connected by a vacant chain. Since the leading block number of this vacant chain is “0”, and NEXT of block # 0  shown in  FIG. 12  is “1”, a block subsequent to block # 0  is # 1 . Since the NEXT value of block # 1  is “2”, a subsequent block is # 2 . In this way, by tracing a NEXT value, the connection status in the forward direction of a vacant chain can be clarified. While by tracing the PREV value of each block, the connection status in the backward direction of the vacant chain can be clarified. 
     When one frame is registered in  FIG. 11 , the number of blocks of a valid chain becomes “1” and its leading block number becomes “0”. In this case, since NEXT and PREV values of block # 0  in  FIG. 12  both are “0”, it is detected that the valid chain is composed of only block # 0 . 
     However, since the number of blocks of a vacant chain is “9” and its leading block number is “1”, as to a vacant chain connecting 9 blocks, its connections in the forward and backward directions can be clarified by tracing the NEXT and PREV values, respectively, of each block starting from block # 1 . 
     Similarly, when decoded data is stored in all 10 frame buffers, the connection status of the valid chain can be clarified since the number of the blocks of a valid chain and its leading block number are “10” and “0”, respectively. Since the number of blocks of a vacant chain is “0”, it can be clarified that there is no vacant chain. In this case, although the leading block number of the vacant chain is “9”, it simply indicates that the leading block number of a vacant chain in the status where decoded data is stored in 9 frame buffers is not updated and this leading block number is not referenced in the process of the flowchart, which will be described later. Therefore, no problem occurs in a non-updated status. 
       FIG. 13  is a detailed flowchart showing a chain update process at the time of storing data in a frame buffer. A process in  FIG. 13  until data is stored in one frame buffer from the initial status where no valid data is stored in any of 10 frame buffers and also a process until one valid data is stored another frame buffer, including the data update shown in  FIGS. 11 and 12 , are described as examples. 
     In step S 30  of  FIG. 13 , a block to register this time, that is, the leading block of a vacant chain (in  FIG. 11 , block numbers before and after a block with block number “0”, that is, PREV and NEXT values “9” and “1”, respectively, of block # 0 ) is sheltered, specifically is stored in a work area or the like as a value to be used for the process. Then, in step S 31  it is determined whether the number of blocks of a valid chain is “0”. Since at this moment it is in its initial status and the number of blocks of a valid chain is “0”, in step S 32  the number of block in which data is registered this time, that is, “0” is becomes the NEXT value of the block in which data is registered, that is, block # 0 . This is the NEXT value of block # 0  in which one frame is registered in  FIG. 12 . 
     Then, in step S 33 , similarly a block number “0” becomes the PREV value in one-frame registration status of block # 0 . Specifically, in these processes, the value of the right side is assigned to the value of the left side. Then, in step S 34 , the leading block number of the valid chain is set. In this status, valid data is stored only in a frame buffer corresponding to block # 0 , and the leading block number of the valid chain remains “0”. 
     Then, in step S 35 , the number of a block subsequent to the block in which data is registered this time, specifically a NEXT value “1” in the initial status before one-frame registration of block # 0  in which data is registered this time is stored as the NEXT of the final block of the vacant chain, that is, a block # 9  being a PREV block before one-frame registration of block # 0  in which data is registered this time. In step S 36 , the final block number of the vacant chain, that is, a previous PREV value “9” of block # 0  in which data is registered this time is stored as the PREV value of the leading block of the vacant chain, that is, block # 1  indicated by a previous NEXT of block # 0  in which data is registered this time. 
     Then, in step S 37  it is determined whether a block number “0” registered this time coincides with the leading block number of the vacant chain. In this case, since the leading block number of the vacant chain in the initial status is “0”, it is determined that they are matched, and in step S 38  the leading block number of the vacant chain is updated. Specifically, the second block number from the top in the initial status of the vacant chain, “1” in this case, is stored as the leading block number of the vacant chain in the one-frame registration shown in  FIG. 11 . 
     If in step S 37  it is determined that there is no need to update the leading block number of the vacant chain, immediately or after the process in step S 38 , in step S 39  the number of blocks of the valid chain is incremented, and in step S 40  the number of blocks of the vacant chain is decremented. Then, the chain update process in the case where data is stored only in a frame buffer corresponding to block # 0  after the initial status terminates. 
     Next, the chain update process from one-frame registration status to two-frame registration status in  FIG. 11 , that is, in the case where data is stored in a frame buffer corresponding to block # 1  is described. Firstly, in step S 30 , PREV and NEXT values “9” and “2”, respectively, corresponding to block # 1  are sheltered, in step S 31  it is determined that the number of valid chain blocks is not “0” and in step S 41  the leading block number of the valid chain, that is, “0” becomes a NEXT value at the time of two-frame registration of block # 1  in which data is registered this time. In step S 42 , the final block number of the valid chain, that is, “0” is stored as the PREV value of the block # 1  in which data is registered this time. Then, in step S 43 , the number of a block in which data is registered this time “1” becomes the PREV value of the leading block, that is, # 0  of the valid chain, and in step S 44 , similarly a block number “1” becomes the NEXT value of block # 0 . 
     Then, the same process as when the number of blocks of the valid chain is “0” is performed in steps S 35  and after. Firstly, in step S 35 , the number “2” of a block subsequent to a block in which data is registered this time, is stored as the NEXT value of the final block # 9  of the vacant chain. In step S 36 , the final block number “9” of the vacant chain is stored as the PREV value of the leading block # 2  of the vacant chain, and in step S 37  it is determined whether the leading block number of the vacant chain must be updated. In this case, since the block number registered this time and the leading block number of the vacant chain both are “1” and are matched, in step S 38  the leading block number of the vacant chain is updated to “2”, in step S 39  the number of blocks of the valid chain is incremented, in step S 40  the number of blocks of the vacant chain is decremented and the process terminates. 
       FIG. 14  is a detailed flowchart showing a chain update process at the time of deleting data from a frame buffer. The process shown in  FIG. 14  is described using a case where the data of a frame buffer corresponding to block # 1  after nine-frame registration in  FIG. 11  is deleted, that is, released, as an example. 
     Firstly, in step S 51 , the numbers of blocks before and after a block to be released this time, the PREV and NEXT values “0” and “2”, respectively, at the time of nine-frame registration of block # 1  in this case, are sheltered and in step S 52  it is determined that the number of blocks of the vacant chain is not “0”. Then, in step S 53  the leading block number “9” of the vacant chain is stored as the NEXT value of block # 1  released this time, and in step S 54  the final block number “9” of the vacant chain is also stored as the PREV value of block # 1 . Then, in step S 55  the block number “1” to be released this time is stored in the PREV of the leading block # 9  of the vacant chain, and in step S 56  a block number “1” is stored in the NEXT of block # 9 . By the processes in steps S 53 -S 56 , the connection of the vacant chain is modified, block # 1  is added to the vacant chain composed of only block # 9  and the vacant chain is connected. 
     Then, in step S 57  the number, “2” in this case, of a block subsequent to the block released this time is stored as the NEXT value of a block before the block released this time, that is, block # 0 , in step S 58  a block number “0” is stored as the PREV value of block # 2  and in step S 59  it is determined whether the number of the released block, “1” in this case, coincides with the leading block number of the valid chain. This is because if the released block is located at the top of the valid chain, the leading block number of the valid chain must be updated. If they are matched, in step S 60  the leading block number of the valid chain, the number of whose second block is the leading block number is updated and them the process proceeds to step S 61 . In this case, since the number of the released block is “1” and the leading block number of the valid chain is “0”, they are not matched. Therefore, without performing the process in step S 60 , in step S 61  the number of the blocks of the valid chain is decremented and in step S 62  the number of the blocks of the vacant chain is incremented. Then, the chain update process of deleting data from a frame buffer corresponding to block # 1  terminates. 
     Next, as another example of the chain update process, the case where a frame buffer corresponding to block # 1  is released in the same way as described above after data is stored in all of ten frame buffers is described. 
     In this case, after in step S 51  “0” and “2” are sheltered as PREV and NEXT values in the same way as described above, in step S 52  the number of blocks of the vacant chain is determined to be “0” and the process proceeds to step S 63 . 
     In step S 63  a block number “1” to be released this time is stored as the NEXT value of block # 1 , and in step S 64  the value “1” is stored as the PREV value of block # 1 . In step S 65  the leading block number of the vacant chain is set to “1”. Thus, the vacant chain is composed of only block # 1 . 
     Then, in steps S 57  and S 58  the same processes as described above are performed. Thus, block # 1  is removed from the valid chain. Then, in step S 59  it is determined in the same way as described above that the number of the released block does not coincide with the leading block number of the valid chain, in step S 61  the number of the blocks of the valid chain is decremented and in step S 62  the number of the blocks of the vacant chain is incremented. Then, the process terminates. 
     Although the frame buffer management program and its management method of the present invention have been so far described in detailed, this program can be used a decoding system based on a general-purpose computer.  FIG. 15  shows the configuration of such a computer system, specifically such a hardware environment. 
     In  FIG. 15 , a computer system comprises a central processing unit (CPU)  30 , read-only memory (ROM)  31 , random-access memory (RAM)  32 , a communication interface  33 , a storage device  34 , an input/output device  35 , a portable-storage-medium reading device  36  and a bus  37  to which all these devices and units are connected. 
     For the storage device  34 , various types of storage devices, such as a hard disk, a magnetic disk or the like can be used. Such a storage device  34  or ROM  31  stores the programs shown in the flowcharts of  FIGS. 4 ,  13 ,  14 , etc. If the CPU  30  executes such a program, the management of a plurality of frame buffers, the update of valid and vacant chains and the like of the preferred embodiment can be realized. 
     Such a program can be stored in, for example, the storage device  34  by a program provider  38  via a network  39  and the communication interface  33 . Alternatively, it can be stored in a portable storage medium  40  sold and distributed in the market, set in the reading device  36  and executed by the CPU  30 . For the portable storage medium  40 , various types of storage media, such as CD-ROM, a flexible disk, an optical disk, a magneto-optical disk, a DVD, etc., can be used. If the reading device  36  reads a program stored in such a storage medium, the management of a plurality of frame buffers, the improvement of control speed and the like can be realized.