Dynamic Selection of Parameter Sets for Transcoding Media Data

• US 20110060792A1
• Filed: 09/08/2010
• Published: 03/10/2011
• Est. Priority Date: 09/08/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Swarmcast, Inc.
• Inventors: Ebersviller, Matthew R.
• Granted Patent: US 8,635,357 B2
• Time in Patent Office: Days
• US Class Current: 709/203
• CPC Class Codes: H04N 19/102 characterised by the element, parameter or selection affected or controlled by the adaptive coding
• CPC Class Codes: H04N 19/154 Measured or subjectively estimated visual quality after decoding, e.g. measurement of distortion use of rate-distortion criteria H04N19/147
• CPC Class Codes: H04N 19/196 being specially adapted for the computation of encoding parameters, e.g. by averaging previously computed encoding parameters processing of motion vectors H04N19/513
• CPC Class Codes: H04N 19/40 using video transcoding, i.e. partial or full decoding of a coded input stream followed by re-encoding of the decoded output stream
• CPC Class Codes: H04N 19/46 Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

An iterative operation is performed at a computing device to identify a parameter set for an initial segment. A parameter set for an initial segment includes a plurality of encoding parameters and values assigned to the encoding parameters. The initial segment is re-encoded using the parameter set, thereby generating a transcoded segment. In some embodiments, the transcoded segment is transmitted to a client computing device that presents media represented by the transcoded segment.

Claims

1. A method for distributing media data, the method comprising:

performing, at a computing device, an iterative operation that selects a final parameter set, each iteration of the iterative operation generating a parameter set and transcoding an initial segment into a transcoded segment using the parameter set; and

generating, at the computing device, a transcoded media data stream comprising a given transcoded segment, the given transcoded segment being a transcoded version of a given initial segment re-encoded using the final parameter set, the final parameter set having been used during the iterative operation to encode a transcoded segment having a fitness score greater than fitness scores of each other transcoded segment generated by the iterative operation.

2. The method of claim 1, further comprising:

transmitting the transcoded media data stream to a client device via a computer communications network.

3. The method of claim 1,

wherein the method further comprises:

receiving, at the computing device, an initial media data stream;

dividing, at the computing device, the initial media data stream into a plurality of initial segments, the initial segment being in the plurality of initial segments; and

performing, at the computing device, the iterative operation for each initial segments in the plurality of initial segments; and

wherein generating the transcoded media data stream comprises;

generating the transcoded media data stream such that the transcoded media data stream comprises a plurality transcoded segments, the plurality of transcoded segments being generated by transcoding the plurality of initial segments.

4. The method of claim 3, further comprising:

transmitting the transcoded media data stream to a client device via a computer network.

5. The method of claim 4,

wherein the initial media data stream represents video that is substantially live;

and

wherein the transcoded media data stream represents video that is substantially live.

6. The method of claim 3, wherein the method further comprises:

identifying, by the computing device, a representative segment of a media data stream, the representative segment being the given initial segment; and

transcoding the media data stream into the transcoded media data stream using the final parameter set.

7. The method of claim 6, wherein identifying the representative segment comprises identifying a busiest segment of the initial media data stream.

8. The method of claim 6, further comprising:

receiving, by the computing device, via a computer communications network, a request for a media file that stores the initial media data stream; and

transmitting, by the computing device, the media file to a client device in response to the request.

9. The method of claim 1, wherein the parameter sets generated by each successive iteration of the iterative operation tend to generate segments have higher similarity to the initial segment than segments that result from transcoding the initial segment using parameter sets generated by earlier iterations of the iterative operation.

10. The method of claim 9, wherein performing the iterative operation comprises performing a genetic algorithm.

11. The method of claim 1, wherein performing the iterative operation comprises performing the iterative operation for each segment in an initial media data stream.

12. The method of claim 11, wherein performing the iterative operation comprises performing iterations of the iterative operation, each iteration of the iterative operation comprising:

transcoding the given initial segment into a plurality of transcoded segments using parameter sets in a current generation of parameter sets;

calculating fitness scores of each transcoded segment in the plurality of transcoded segments;

determining whether a generation limit has been reached;

determining whether one of the fitness scores exceeds a fitness score threshold;

when the generation limit has not been reached or one of the fitness scores exceeds the fitness score threshold, outputting the given transcoded segment, the given transcoded segment being the transcoded segment generated by the iterative operation that has a fitness score greater than the fitness scores of each other transcoded segment generated by the iterative operation; and

when the generation limit has not been reached and none of the fitness scores exceeds the fitness score threshold;

calculating selection probabilities of the parameter sets in the current generation of parameter sets; and

performing the following steps until a new generation of parameter sets includes a sufficient number of parameter sets;

selecting parent parameter sets based on the selection probabilities of the parameter sets in the current generation of parameter sets; and

generating a child parameter set in the new generation of parameter sets by recombining values of encoding parameters in the parent parameter sets.

13. The method of claim 1,

wherein each of the parameter set generated by the iterative operation includes a plurality of encoding parameters;

and

wherein performing the iterative operation comprises performing iterations of the iterative operation, each iteration of the iterative operation comprising;

receiving a current segment;

determining whether all possible parameter sets have been tested for the current segment;

when not all possible parameter sets have been tested for the current segment;

generating a current parameter set, the current parameter set being one of the parameter sets not yet tested for the current segment;

transcoding the current segment into a current transcoded segment using the current parameter set;

calculating a fitness score of the current transcoded segment;

when the fitness score of the current transcoded segment exceeds a fitness score threshold, selecting the current parameter set as the final parameter set.

14. The method of claim 1, wherein performing the iterative operation comprises performing iterations of the iterative operation, each iteration of the iterative operation comprising:

receiving a current segment;

transcoding the current segment into a first transcoded segment using a current parameter set;

when the current parameter set is the final parameter set, outputting the first transcoded segment;

when the current parameter set is not the final parameter set;

calculating a fitness score of the first transcoded segment;

mutating the current parameter set into a mutated parameter set;

transcoding the current segment into a second transcoded segment using the mutated parameter set;

calculating a fitness score of the second transcoded segment;

when the fitness score of the second transcoded segment is greater than the fitness score of the first transcoded segment;

outputting the second transcoded segment; and

setting the mutated parameter set as the current parameter set;

when the second fitness score exceeds a fitness score threshold, selecting the mutated parameter set as the final parameter set; and

when the fitness score of the second transcoded segment is not greater than the fitness score of the first transcoded segment, outputting the first transcoded segment.

15. The method of claim 1, wherein performing the iterative operation comprises performing iterations of the iterative operation, each iteration of the iterative operation comprising:

receiving a current series of segments;

when the final parameter set has been selected;

transcoding each segment in the current series of segments into a current series of transcoded segments using the final parameter set; and

outputting the current series of transcoded segments;

when the final parameter set has not been selected;

transcoding each segment in the current series of segments into the current series of transcoded segments using different parameter sets in a current generation of parameter sets;

outputting transcoded segments in the current series of transcoded segments;

calculating fitness scores of transcoded segments in the current series of transcoded segments;

determining whether any of the fitness scores of the transcoded segments in the current series of transcoded segments exceed a fitness score threshold;

determining whether a generation limit is reached;

when any of the fitness scores of the transcoded segments in the current series of transcoded segments exceeds the fitness score threshold or when the generation limit is reached, selecting a given parameter set in the current generation of parameter sets as the final parameter set, the given transcoded segment being in the current series of transcoded segments generated using the given parameter set, the given transcoded segment having a fitness score greater than each other transcoded segment in the current series of transcoded segments;

when none of the fitness scores of the transcoded segments in the current series of transcoded segments exceeds the fitness score threshold and when the generation limit is not reached;

calculating selection probabilities of parameter sets in the current generation of parameter sets;

performing the following steps until a new generation of parameter sets includes a sufficient number of parameter sets;

selecting parent parameter sets in the current generation of parameter sets based on the selection probabilities of the parameter sets in the current generation of parameter sets; and

generate a child parameter set in the new generation of parameter sets by recombining values of encoding parameters in the parent parameter sets.

16. The method of claim 1,

wherein the initial segment is encoded according to a first video encoding standard;

and

wherein transcoding the initial segment comprises;

transcoding the initial segment such that the transcoded segment is formatted according to a second video encoding standard, the first video encoding standard being different than the second video encoding standard.

17. The method of claim 16, wherein the first video encoding standard and the second video encoding standard are selected from a group including:

H.263, H.264, Asynchronous Serial Interface (ASI), Serial Digital Interface, TrueMotion VP7, Theora, MPEG-4, and Windows Media Video (WMV).

18. The method of claim 1, wherein transcoding the initial segment comprises:

transcoding the initial segment such that the transcoded segment has a lower bit rate than the initial segment.

19. The method of claim 1, wherein the final parameter set includes encoding parameters selected from a group comprising:

a parameter indicating a motion estimation method, a parameter indicating a motion estimation range, a parameter indicating a quantization scale between I-frames and P-frames, a parameter indicating a quantization scale difference between P-frames and B-frames, a parameter indicating a quantization parameter curve compression value, a parameter indicating a maximum keyframe interval, a parameter indicating a minimum keyframe interval, a parameter indicating a complexity blur parameter, a parameter indicating a quantization blur parameter, a parameter indicating a motion estimation compare function, a parameter indicating whether to use an in-loop deblocking filter, a parameter indicating a scene change threshold, a parameter indicating whether to add B-frames into a normal reference list, a parameter indicating whether to allow or disallow B-frames to use weight prediction options, a parameter indicating whether to allow each macroblock to use different references, a parameter indicating whether to allow or disallow skipping of P-macroblocks that do not appear to change, a parameter indicating whether to allow or disallow an encoder to use access unit delimiters, a value indicating whether to allow or disallow the encoder to choose which coefficients to round up or down, a parameter indicating a minimum quantizer, a parameter indicating a maximum quantizer, a parameter indicating a minimum step of a quantization parameter, a parameter indicating a number of frame to reference, a parameter indicating a predicting mode, a parameter indicating allowed combinations of partitions in macroblocks, a parameter indicating a maximum number of B-frames between keyframes, a parameter indicating how adaptive B-frame look ahead is, a parameter indicating an entropy encoder, a parameter indicating an alpha value for use in in-loop deblocking, a parameter indicating a beta value for use in in-loop deblocking, a parameter indicating a constant quality mode, and a parameter indicating algorithms used for both subpixel motion searching and partition decisions.

20. A computing device comprising:

a memory that stores software instructions; and

a processing unit, wherein the software instructions, when executed by the processing unit, cause the computing device to;

perform an iterative operation that selects a final parameter set, each iteration of the iterative operation generating a parameter set and transcoding an initial segment into a transcoded segment using the parameter set;

generate a transcoded media data stream comprising a given transcoded segment, the given transcoded segment being a transcoded version of a given initial segment re-encoded using the final parameter set, the final parameter set having been used during the iterative operation to encode a transcoded segment having a fitness score greater than fitness scores of each other transcoded segment generated by the iterative operation; and

transmit the transcoded media data stream to a client device via a computer communications network.

21. The computing device of claim 20,

wherein the software instructions, when executed by the processing unit, further cause the computing device to:

receive an initial media data stream,;

divide the initial media data stream into a plurality of initial segments that includes the given initial segment;

transcode each initial segment in the plurality of initial segments into transcoded segments using parameter sets generated by performing the iterative operation; and

wherein the software instructions that cause the computing device to generate the transcoded media data stream cause the computing device to generate the transcoded media data stream such that the transcoded media data stream comprises the transcoded segments.

22. The computing device of claim 21,

wherein the initial media data stream represents video that is substantially live;

and

wherein the transcoded media data stream represents video that is substantially live.

23. The computing device of claim 20, wherein the software instructions, when executed by the processing unit, further cause the computing device to:

identify a representative segment of a media data stream, the representative segment being the initial segment, the representative segment being a busiest segment of the media file;

transcode the media data stream into the transcoded media data stream using the final parameter set;

receive, via the computer communications network, a request for the media data stream; and

transmit the transcoded media data stream to the client device in response to the request.

24. The computing device of claim 20, wherein the software instructions that, when executed by the processing unit, cause the computing device to perform the iterative operation cause the computing device to perform a genetic algorithm that selects the final parameter set.

25. The computing device of claim 24, wherein the software instructions that, when executed by the processing unit, cause the computing device to perform the genetic algorithm cause the computing device to:

repeatedly perform the following steps until the final parameter set is selected;

transcoding the initial segment into a plurality of transcoded segments using different parameter sets in a current generation of parameter sets;

calculating fitness scores of each transcoded segment in the plurality of transcoded segments;

selecting the final parameter set when a generation limit has been reached;

selecting the final parameter set when one of the fitness scores exceeds a fitness score threshold; and

when the generation limit has not been reached and when none of the fitness scores exceeds the fitness score threshold;

calculating selection probabilities of each parameter set in the current generation of parameter sets; and

performing the following steps until a new generation of parameter sets includes a sufficient number of parameter sets;

selecting parent parameter sets based on the selection probabilities of the parameter sets in the current generation of parameter sets; and

generating a child parameter set in the new generation of parameter sets at least in part by recombining values of encoding parameters in the parent parameter set.

26. A computer readable data storage medium that stores software instructions that, when executed by a processing unit of a computing device, cause the computing device to:

perform an iterative operation that selects a final parameter set, each iteration of the iterative operation generating a parameter set and transcoding an initial segment into a transcoded segment using the parameter set; and

generate a transcoded media data stream comprising a given transcoded segment, the given transcoded segment being a transcoded version of a given initial segment re-encoded using the final parameter set, the final parameter set having been used during the iterative operation to encode a transcoded segment having a fitness score greater than fitness scores of each other transcoded segment generated by the iterative operation.

27. A system for distributing media data, the system comprising:

a media source that streams an initial media data stream; and

a media processing system comprising a computer-readable data storage media storing software instructions that, when executed by a processor of the media processing system, cause the media processing system to;

receive the initial media data stream;

perform an iterative operation that selects a final parameter set, each iteration of the iterative operation generating a parameter set and transcoding an initial segment in the initial media data stream into a transcoded segment using the parameter set;

generate a transcoded media data stream comprising a given transcoded segment, the given transcoded segment being a transcoded version of a given initial segment encoded using the final parameter set, the given initial segment being in the initial media data stream, the final parameter set having been used during the iterative operation to encode a transcoded segment having a fitness score greater than fitness scores of each other transcoded segment generated by the iterative operation; and

stream the transcoded media data stream to one or more client devices.