Abstract:
Optical discs may support “Out Of Multiplex” formats, meaning that different presentation components, like video, audio and subtitles, are stored on different files on the disc, e.g. Blu-ray discs. The different data streams are read by a single pick-up, requiring frequent pick-up jumps and extensive data buffering. The method for operating a scheduler for an optical pick-up reduces the number of pick-up jumps while optimizing the required buffer space. The scheduler is based on a static schema, meaning that the buffer for the data stream with the highest data rate is of minimal size, and therefore refilled in short periods while the buffers for the lower rated streams are dimensioned such that they can be refilled in multiples of the short period. Deviations from the static schema may be allowed, e.g. due to multi-angle video technique. Afterwards the scheduler returns to the original schedule.

Description:
FIELD OF THE INVENTION  
       [0001]     This invention relates to a method for operating a scheduler for an optical pick-up. The pick-up reads data streams from an optical storage medium, wherein the data streams belong to different data types like audio, video or subtitles, and are distributed to several files on the storage medium.  
       BACKGROUND  
       [0002]     Pre-recorded or self-recorded optical discs may support “Out Of Multiplex” (OOM) formats. Out of multiplex is a format that stores different presentation components, e.g. video, audio and subtitles, on different locations on the disc, i.e. different files. This may be possible with various standardized media, e.g. Blu-ray disc. Also, a video technique known as multi-angle, or seamless angle change, may be implemented. It is well known from DVD-Video, and it means that a video film may contain multiple video tracks that are parallel on the time-line, wherein each video track usually shows the same scene from a different perspective. The user may select a perspective, e.g. by pressing a dedicated button. It is a requirement that switching between the different video tracks is performed with minimal delay, and that the tracks are integrated seamlessly into the video.  
         [0003]     During playback of OOM formats, a number of the presentation components need to be decoded separately, and then presented synchronously and continuously, i.e. without noticeable interruption of the presentation. Therefore it is required that each of the decoders is provided with a continuous stream of data. On the other hand, optical drives are usually equipped only with a single pick-up unit, which is capable of reading only one data stream from the disc at a time, at a higher data rate than required by any of the decoders. That means that the pick-up has to jump from stream to stream in order to serve all decoders simultaneously. This requires buffering, i.e. the data that are read from the disc are fed into properly sized buffers, wherein each of the buffers is associated with a decoder. Buffering the coded data is more effective than buffering the decoded data. Thus, any decoder is provided with a continuous data stream.  
         [0004]     Feeding the buffers requires a scheduling algorithm, because any buffer under-run must be prevented for a continuous presentation. The buffer sizes strongly depend on the applied scheduling scheme.  
         [0005]     A pick-up usually contains an actuator carrying an optical sensor, and the pick-up is movable by a mechanical drive for raw adjustment, while the actuator is separately movable for fine adjustment without a mechanical drive. When the pick-up has to read multiple streams, this requires a much higher pick-up jump frequency than a single, multiplexed stream.  
       SUMMARY OF THE INVENTION  
       [0006]     One problem arising from the fact that multiple files must be read simultaneously is the high pick-up jump frequency causing noise and wastage due to the mechanical drive. A further problem is the delay appearing during seamless video angle switches. The delay is the time needed from requesting the video angle change until seeing the other video angle. It is determined mainly by the video buffer size, or by the amount of time until the video buffer has run empty and the new content reaches the video decoder. The same applies to the start up of OOM decoding. The time passing by from pressing the start button until effectively starting the display is quite long, since all buffers must be filled from scratch.  
         [0007]     A problem to be solved by the invention is to provide a scheduling method for controlling a pick-up such that a reduction of the pick-up jump frequency is achieved, while using a minimum of buffering space. This problem is solved by the method disclosed in claim  1 .  
         [0008]     Advantageously, a method for reducing the delay times required for angle switch can be included. This method is disclosed in claim  6 .  
         [0009]     Another problem to be solved by the invention is to reduce the delay times required at presentation start up. This problem is solved by the method disclosed in claim  8 .  
         [0010]     The inventive method leads to a lower pick-up jump frequency and thus achieves noise reduction and improved pick-up durability. According to the invention, this is achieved by employing an appropriately adapted scheduling raster, and by individually increasing the lower-rated buffers by a small amount of memory. The proposed scheduling raster is static, i.e. based on a fixed time constant, and thus independent from the actual buffer filling. Further, the method provides a technique for OOM decoding that reduces the switching time for seamless angle changes. For a HDTV stream, the typical application of Blu-ray disc, the buffers are quite large. The large buffers cause a long delay for the user waiting for a requested angle change to get visible, which delay can be reduced by the inventive method. The same problem arises for the start-up of OOM decoding. According to the invention, the problem of optimizing the start-up or video switch procedure for the proposed scheduling scheme can be solved by filling the buffers only partially, such that the buffer filling situation matches with an optimal position in the static scheduling scheme.  
         [0011]     According to the invention, it is possible to interrupt the scheme by an angle change request, and return to the scheme after serving the request, when the normal scheme is such that for any three successively read data streams, wherein the second is the video data stream, the first or the third data stream is also the video data stream.  
         [0012]     Advantageously, the invention can also be used to optimize the partitioning of a given amount of buffering space for the described application.  
         [0013]     Advantageous embodiments of the invention are disclosed in the dependent claims, the following description and the figures.  
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0014]     Exemplary embodiments of the invention are described with reference to the accompanying drawings, which show in  
         [0015]      FIG. 1  an exemplary buffer filling diagram for a static scheduler;  
         [0016]      FIG. 2 a  diagram showing an optimized start-up procedure;  
         [0017]      FIG. 3  the principle of delayed services due to a user request;  
         [0018]      FIG. 4  service interruption by a user request; and  
         [0019]      FIG. 5  video service interruption by a user request. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0020]     In the following, a detailed description of the invention including a detailed analysis of the problem is given. Though the invention is suitable for any number of data streams, the typical application case of three streams is described here, namely video, audio and subtitle streams.  
         [0021]     OOM decoding is mainly influenced by the following mutually dependent parameters: 
        the maximum data rate of the pick-up R D ,     the maximum pick-up jump time T j ,     the pick-up jump frequency f jump ,     the maximum data rate of the first component stream R V ,     the size of the corresponding buffer B V ,     the maximum data rate of the second component stream R A ,     the size of the corresponding buffer B A ,     the maximum data rate of the third component stream R S ,     and the size of the corresponding buffer B S .        
 
         [0031]     The pick-up jump time is the maximum time required by the mechanical move of the pick-up to a new position, ending when data from the new stream reach the buffer. This time may depend on the data allocation on the medium. The order of the component streams is the order of their data rates, i.e. the first component stream has the highest data rate R V , the second stream the second highest data rate R A  etc. Therefore, in the typical application mentioned above R V  refers to the video stream, R A  to the audio stream and R S  to the subtitle stream. The buffer sizes B V ,B A ,B S  do not encompass any decoder internal buffers, and thus are independent from e.g. any special decoder.  
         [0032]     Further, a basic system time constant T and integer numbers n and k are introduced. According to the invention, the system time constant T is selected such that the buffer of the component with the highest data-rate, e.g. video, is being continuously emptied and refilled in periods of T, while all lower rated component buffers are emptied and refilled in periods of multiples of T.  FIG. 1  shows buffer fillings of an exemplary system according to the invention during a complete pick-up cycle, assuming a situation where all buffers already contain data and are continuously being read, and assuming that when a buffer is being filled it is being filled completely. Consequently, the pick-up data rate R D  must be considerably higher than any of the read data rates R V ,R A ,R S , which is a realistic case.  
         [0033]     In  FIG. 1 , at a certain time to the pick-up is idle since all buffers contain data. The pick-up position, depending on its previous action not shown, may be on the video stream. If the position is another, the pick-up jumps to the video stream within a time of not more than T j . Then it reads video data and fills the video buffer B video  within a time of t fill,v . When the video buffer is full at a time t 1 , it requires no further refill within a time period of t leak,v . During this time the pick-up jumps to the subtitle stream, requiring a jump time of T j , and fills the subtitle buffer B sub  within a time of t fill,S . Then at the time t 2  it jumps back to the video stream within T j . In the inventive system the buffer sizes are selected such that at the time t 2 +T j , when the video data reach the video buffer B video , the buffer still has enough data to continuously provide the decoder with data. The video buffer is refilled, and then at a time t 3  the pick-up jumps to the audio stream, since the audio buffers requires refilling after another T j . After filling the audio buffer during t fill,A  the pick-up returns to the video stream. The described schema is continued such that the pick-up reads the highest rated stream and any of the lower rated streams in turn, meaning that when it has read any one lower rated stream to fill a corresponding buffer B audio, B sub , it always returns to the highest rated stream, and reads that stream at least once to fill the corresponding buffer B video . In other words, at least one out of two successively read data streams is the stream with the highest data rate. In this respect, the schema is static.  
         [0034]     Advantageously this schema can also handle components with variable data-rate, up to a maximum allowed data rate. Variable data-rate of a component simply causes a higher remaining buffer filling level than calculated, at the time the buffer is refilled, and therefore results in quicker filling. However, according to the invention this shall not influence the scheduling raster. Instead, it results in some additional pick-up idle time.  
         [0035]     An important aspect of the invention is that each of the lower rated component buffers, i.e. audio and subtitles, is being refilled and emptied at its own time-constant, wherein the time-constant for the audio component is n*T, and the time-constant for the subtitle component is k*n*T. As defined above, T is the time required for a complete cycle of filling and emptying the buffer for the highest rated stream, and n and k are integer numbers. Therefore the inventive scheduler is static also with respect to accessing the lower rated streams, i.e. the lower rated streams are accessed in a constant predetermined order. In the example shown in  FIG. 1  the audio stream is always read twice before the subtitle stream is read once, bearing in mind that before and after every audio or subtitle stream access the video stream is read. This can be formally described by n=2 and k=2.  
         [0036]     Another important aspect of the invention is the distinction between “one-service-periods” 1SP and “two-services-periods” 2SP. A “one-service-period” 1SP is defined as the time T between two successive peak fillings of the video buffer, wherein the pick-up performs only one service, namely reading video data. Contrary, a “two-services-period” 2SP is defined as the time T between two successive peak fillings of the video buffer, wherein the pick-up performs two services, namely reading video data and reading data from a lower rated stream. Therefore any “two-services-period” 2SP requires the pick-up to jump twice, while any “one-service-period” 1SP requires no pick-up jump, and therefore provides some pick-up idle time, thus giving flexibility, as required below. In general, the inventive schema does not force the video buffer to run empty during these periods, as exemplarily illustrated. E.g. the buffer could also be kept at a certain level until the next service period starts.  
         [0037]     The resulting frequency of pick-up jumps, in the following called the “jump-frequency” is for a system with three streams defined as  
               f   jump     :=         2     n   ·   T       +     2     n   ·   k   ·   T         =       2   ⁢     (     k   +   1     )         n   ·   k   ·   T                 (     Eq   .           ⁢   1     )             
 
         [0038]     It means that two pick-up jumps are required to the medium rated stream within a time of n·T, and two further pick-up jumps to the lowest rated stream within a time of n·k·T. The buffer sizes for all components and the system time constant can be calculated according to the following equations.  
         [0039]     A general relation describing the filling or emptying of a buffer of size B is  
             t   =     B   R             (     Eq   .           ⁢   2     )             
 
         [0040]     R is the resulting filling or leakage rate, i.e. filling the buffer with a filling rate R takes a time of t, and emptying the buffer with a leakage rate R also takes the time t. If the empty buffer is filled and emptied simultaneously, with the difference between leakage rate and filling rate being R and the filling rate being higher, it also takes a time of t until the buffer is full.  
         [0041]     Thus, the following equations describe the filling and reading processes for three individual components, as shown in  FIG. 1 :  
             T   =         t     fill   ,   V       +     t     leak   ,   V         =         B   V         R   D     -     R   V         +       B   V       R   V                   (     Eq   .           ⁢   3.1     )                 n   ·   T     =         t     fill   ,   A       +     t     leak   ,   A         =         B   A         R   D     -     R   A         +       B   A       R   A                   (     Eq   .           ⁢   3.2     )                 k   ·   n   ·   T     =         t     fill   ,   S       +     t     leak   ,   S         =         B   S         R   D     -     R   S         +       B   S       R   S                   (     Eq   .           ⁢   3.3     )             
 
 with n being in the range of [2,n max ] and k in the range of [1,k max ]. Further, the system time constant T obeys to  
             T   =       2   ·     T   j       +       B   V         R   D     -     R   V         +       B   A         R   D     -     R   A                   (     Eq   .           ⁢   4     )             
 
         [0042]     This allows calculating the required buffer sizes according to  
               B   V     =     2   ⁢           T   j     ⁡     (       R   D     -     R   V       )       ⁢     R   V           R   D     -     R   V     -     n   ·     R   A                     (     Eq   .           ⁢   5.1     )                 B   A     =     2   ⁢         n   ·       T   j     ⁡     (       R   D     -     R   A       )         ⁢     R   A           R   D     -     R   V     -     n   ·     R   A                     (     Eq   .           ⁢   5.2     )                 B   S     =     2   ⁢         n   ·   k   ·       T   j     ⁡     (       R   D     -     R   S       )         ⁢     R   S           R   D     -     R   V     -     n   ·     R   A                     (     Eq   .           ⁢   5.3     )             
 
 and the system time constant according to  
             T   =     2   ⁢         T   j     ⁢     R   D           R   D     -     R   V     -     n   ·     R   A                     (     Eq   .           ⁢   5.4     )             
 
         [0043]     General assumptions for this scheduler are 
 
n min =2   (Eq.6.1) 
 
K min =1   (Eq.6.2) 
 
         [0044]     Since the denominator in eq.5.4 must be positive, this means  
               n   max     =         R   D     -     R   V         R   A               (     Eq   .           ⁢   6.3     )             
 
         [0045]     As a result of the different leakage rates for audio and subtitle buffers follows  
               k   max     =       R   A       R   S               (     Eq   .           ⁢   6.4     )             
 
         [0046]     The resulting jump-frequency is  
               f   jump     =         2   ⁢     (     k   +   1     )         n   ·   k   ·   T       =         (     k   +   1     )     ⁢     (       R   D     -     n   ·     R   A       -     R   V       )         n   ·   k   ·     T   j     ·     R   D                   (     Eq   .           ⁢   7     )             
 
         [0047]     To achieve minimal buffering requirements for the scheme, n and k are chosen to their minimal values n=2 and k=1, for the case of three presentation components.  
         [0048]     In one embodiment of the invention, preferably the parameter k may be increased (k=1 . . . k max ) in a first step. This results in a reduced pick-up jump frequency with requiring only little additional buffer size. In another embodiment of the invention the second step is to increase also the parameter n (n=1 . . . n max ) to reduce the frequency of pick-up jumps even further.  
         [0049]     Advantageously, the invention allows minimizing the start-up delay of a presentation.  FIG. 2  shows how this may be achieved by selecting the optimal entry point into the scheduling raster and an appropriate buffer filling sequence. At system start-up T start , the video, audio and subtitle data need to be read from the disc and written into the associated buffers B video , B audio , B sub . When this procedure has finished, the presentation can start. According to the invention, the start-up sequence is such that the buffer for the highest rated stream, i.e. video, is filled last, after the buffers for the lower rated streams are already filled. However, different start-up procedures are possible, resulting in different delay times. Possible entry points S,S* into the static scheduling raster are when the filling of each buffer is such that the corresponding decoder can start working. The inventive method of selecting the optimal entry point for minimal start-up delay chooses the possible entry point S* where the required amount of data in the audio and subtitle buffers is the smallest compared to other possible entry points S, so that they require minimal filling time before the presentation starts. The start-up procedure shown in  FIG. 2  begins at T start  with moving the pick-up to access first the subtitle stream within a time of T j , reading the appropriate amount of subtitle data required at S*, then moving the pick-up to the audio stream and reading audio data as required at S*, and then moving the pick-up to the video stream and reading video data at last. At the time S* the video buffer has enough data to start the video decoder, and thus the presentation. It is assumed here that the buffered amount of audio and subtitle data is sufficient to start their respective decoders, since S* must be selected correspondingly.  
         [0050]     It is also possible that e.g. during presentation start-up one or more data streams must be read from the medium that are required only once, e.g. configuration data, and that can be processed at the data rate provided by the pick-up. Therefore, all described procedures refer only to those data streams that are continuously required for the presentation. That means that the described static schedule starts at presentation start-up time S*, and may be flexible before and after the presentation.  
         [0051]     In one embodiment of the invention, the process of reading the lower rated streams at start-up is optimized such that the streams are read in the same, or reverse, order that they have on the medium, depending on and starting from the current pick-up position. This minimizes the number of pick-up jumps required during start-up.  
         [0052]     As another advantage, in one embodiment the inventive method reduces delay times required for seamless angle changes. This can be achieved by delayed servicing, as shown in  FIG. 3 . The scheduling raster is selected such that the audio buffer B audio  and the subtitle buffer B sub  have a period of 4-T, i.e. n=4 and k=1. Using the above-mentioned flexibility of the pick-up during one-service-periods, it is possible to handle angle change requests at any time, however assuming that the time between successive requests is more than 2·T, which is not unrealistic. Delayed servicing can be used when in the normal scheduling raster after any two-services-period a one-service-period follows. This means that if the second of any three successively read data streams is the video data stream, then also the first or the third is the video data stream. Advantageously only an actuator movement is required when reading the same stream twice successively, no pick-up movement.  
         [0053]      FIG. 3  shows a situation where an angle change is requested at a time T a  when the video buffer has just been filled, and according to the schedule the audio buffer has to be filled next, since it is almost empty. This would be a regular service S r . In order to prevent any interruption of the running presentation in such situation, and simultaneously achieve only minimal angle switch delay, the best solution according to the invention is to serve the angle change request with priority, and serve the audio buffer in a delayed service S d . This means to move the pick-up, when an angle change is requested, within the jump time T j  to the appropriate position on the disc where the requested video stream can be read, flush the video buffer down to the lowest possible angle switch position as described below, and read the new video stream into the video buffer. Then the audio buffer can be served, after another pick-up jump time T j . This requires that the audio buffer can bridge the time period t d  from its regular service S r  start time to the delayed service S d  start time, and thus the audio buffer B audio  must be larger than calculated above. Analogously, the same applies for the subtitle buffer B sub . The time t d  to be bridged corresponds to the load time of the video buffer, and thus is shorter than T. The additional amount of buffer space ΔB audio ,ΔB sub  can be calculated to  
               Δ   ⁢           ⁢     B   audio       =       (         B   V         R   D     -     R   V         +     T   j       )     ·     R   A               (     Eq   .           ⁢   8.1     )                 Δ   ⁢           ⁢     B   sub       =       (         B   V         R   D     -     R   V         +     T   j       )     ·     R   S               (     Eq   .           ⁢   8.2     )               
         [0054]     The additional buffer space, and thus the additional cost, depends directly on the data rate. Therefore this embodiment of the invention comprises an increase of buffer space for the lower rated streams.  
         [0055]     To finish the angle switch process according to the invention, the scheduler returns to the original scheduling raster. This may be achieved by interrupting the delayed service S d  for the audio buffer at a time T d,a  when the filling of the audio buffer is the same as it would be if a regular service S r  had been performed before. Thus, the audio buffer may return to the original scheduling raster. Then the pick-up may jump to the video stream and fill the video buffer, until at a time T d,v  the filling of the video buffer is the same as it would be if no angle change had been requested before. Thus, also the video buffer may return to the original scheduling raster.  
         [0056]     In one embodiment of the invention introducing “service interruption” may further reduce angle switch delay, as shown in  FIG. 4 . This means that in the case of a video angle change request the video buffer is served with priority, even if the pick-up is busy with serving another, e.g. the audio buffer. Thus, the lower prioritized service is interrupted. In  FIG. 4  the video buffer is full at a time T a , and the pick-up is moved within the pick-up jump time T j  to the audio stream, which in this example is the next stream in turn. At a nearby time T a ′, either during the pick-up jump or during the following regular audio service S r , a video angle change may be requested. According to the invention, the video stream is prioritized such that the pick-up is moved immediately, at T a ′, to the new video stream, not completing the audio buffer service. After the pick-up jump time T j  the new video stream is read, and when the video buffer is full, the pick-up returns to the interrupted audio service. After another period of T j  the audio buffer continues to be filled.  
         [0057]     As described above for a delayed service S d , the scheduler returns to the original scheduling raster by filling the audio buffer not completely, but only up to the level that it would have if it had been served regularly. When this level is reached at a time T d,a ′, the pick-up is moved back to the video stream, and the video buffer is flushed down to the lowest possible angle switch position, as described below. Then the pick-up fills the video buffer up to the level that it would have if no angle change had been requested. At that time T d,v ′ the system has returned to the original scheduling raster, and may continue with it.  
         [0058]     The described service interruption requires another additional buffer space for the lower rated stream buffers, because an additional time of 2-T j  must be bridged. Thus, the equations eq.8.l and eq.8.2 become  
               Δ   ⁢           ⁢     B   audio       =       (       2   ·     T   j       +       B   V         R   D     -     R   V           )     ·     R   A               (     Eq   .           ⁢   9.1     )                 Δ   ⁢           ⁢     B   sub       =       (       2   ·     T   j       +       B   V         R   D     -     R   V           )     ·     R   S               (     Eq   .           ⁢   9.2     )             
 
         [0059]     The lowest possible angle switch position is used for buffer flushing, as mentioned above. In OOM, video sequences may contain angle switch labels that mark positions, where a seamless angle change is possible. According to one embodiment of the invention, these angle switch labels are stored together with their associated video data. The scheduler may determine the lowest possible angle switch position by selecting the first angle switch label above a certain minimum buffer filling level B v,min , also called bonding label. This level B v,min  can be calculated as the amount of data that is required to continue video presentation until the new video data arrive at the buffer, roughly after a time of T j  plus a decoding time that is usually negligible. Buffer flushing means that the video data beyond the bonding label are overwritten with the new video data.  
         [0060]     In a further embodiment of the invention the angle switch delay may also be improved for the case that an angle switch is requested while the video buffer is being served, as shown in  FIG. 5 . Advantageously, this leads to a shorter recovery time between two successive angle change requests, or to a recovery time that is less dependent on the video contents. Since the delay time between the request for an angle change and its presentation depends on the remaining video buffer filling up to the bonding label, and therefore depends also on the current video data rate, it may be unacceptably high for low video data rates.  FIG. 5  shows a delayed service S d  for audio data, as described above, and the pick-up returning to the video data stream at a time T d,a , taking a jump time of T j . At a time T a ″, which is later than T d,a  and could be e.g. within T d,a +T j  or while the video buffer is being filled, a video angle change may be requested. As a worst case,  FIG. 5  shows T a ″ being equal to T d,a +T j . To handle this situation, in this embodiment of the 30 invention also a delayed service for video is possible, meaning that the scheduler interrupts the pick-up reading the current video stream and moves it to another video stream that contains the video data for the requested angle. It may take an additional delay time of T j +T GOP  to have the video visible, where T GOP  is the duration of a video access unit that is sufficient for decoding. In the case of e.g. an MPEG video stream, this is a group-of-pictures (GOP). Generally T GOP  is the minimal amount of a certain type of data used for decoding. T GOP  was neglected in the previous examples since for audio and subtitles it is considerably less than T j . It could be added without changing the achieved results by replacing T j  with “T j +T GOP ” where T GOP  refers to the audio or subtitle decoder. To support delayed service, the video buffer must bridge the additional delay time T i +T GOP , wherein it is sufficient to assume T j +T GOP  always being less than T. The video buffer is therefore enlarged by the minimum amount of 
 
Δ B   V   =R   V ( T   j   +T   GOP )   (Eq.10) 
 
         [0061]     Generally it is assumed that any buffer mentioned in this disclosure may be replaced by a plurality of cooperating buffers. Further, it is possible that buffers for different data streams may be implemented in a single device.  
         [0062]     Advantageously, the invention can be used for devices that construct multi-media or audio-visual (AV) representations from data read from a storage medium, e.g. an optical storage medium such as a DVD or Blu-ray disc, wherein a single pick-up reads multiple data streams.  
         [0063]     More generally, the invention can be used for devices that construct any combined data representation from a plurality of data streams that are read from a single storage medium, e.g. optical storage medium, wherein the data streams are read by a single pick-up and the data streams have different data rates.