US20090046595A1 - Method and system for content estimation of packet video streams - Google Patents

Abstract

A method and system for estimating the content of frames in an encrypted packet video stream without decrypting the packets. The method involves comparing the relative sizes of frames within a video stream and estimating the content of the video stream based on the frame sizes and the ordering of frames within the video stream. The method can alternatively be used to estimate the content of frames in an unencrypted packet stream.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS
• This application claims priority to U.S. provisional application No. 60/949,988, filed Jul. 16, 2007, and U.S. provisional application No. 60/951,321, filed Jul. 23, 2007, both of which are incorporated herein by reference.
BACKGROUND OF THE INVENTION
• Packet video systems such as High Definition Television (“HDTV”) and Internet Protocol Television (“IPTV”) are becoming increasingly important today and are replacing older non-packet broadcast television and video streaming. Such packet video systems can experience transmission problems which lead to lost or delayed packets. This, in turn, can cause a degradation in the quality of service delivered to the end-viewer such as frozen or distorted images.
• Providers of broadcast or streaming video commonly encrypt video streams to ensure that only authorized persons can view the video content. While this encryption is necessary to prevent the unauthorized dissemination of the provider's video content, encryption also precludes easy diagnosis of transmission problems within the packet network. This is because packet analyzing systems cannot analyze degradations within an encrypted video stream to determine what effect those degradations might have on the quality of service delivered to the end-viewer. Because not all packet losses within a video stream will have a human-perceptible impact on the quality of the video, it is necessary for a network analyzer to determine the type and content of packets that are lost. Thereafter, the analyzer can estimate the subjective effects of the lost packets on the viewer.
• It is well known in the art that most packet video systems display a series of pictures (or “frames”), each frame representing a small change from the previous frame. Frames are usually updated 10-50 times per second. Digital video that is carried over packet networks is usually compressed using standard methods such as MPEG2, MPEG4, or H.264. These compression techniques produce three distinct types of frames, denoted as I-frames, P-frames, and B-frames, respectively. Each frame has a picture header that identifies the type of frame and contains other data related to the image size and encoding.
• I-frames (“intra” frames) are intra-frame encoded frames that do not depend upon past or successive frames in the video stream to aid in the reconstruction of the video image at the video receiver. Rather, the I-frame itself contains all the information needed to reconstruct an entire visible picture at the video receiver. As such, the I-frame is the largest in size of the three types of frames, typically 2-5 times as large as a P-frame or B-frame. Because of its large size, an I-frame must often be broken up and sent in multiple packets over the packet network. An I-frame (along with a P-frame) is also known as a “reference frame” because it provides a point of reference from which later frames can be compared for reconstruction of a video image.
• P-frames (“predicted” frames) are inter-frame encoded frames that are dependent upon prior frames in the video stream to reconstruct a video image at the video receiver. In essence, P-frames contain only the differences between the current image and the image contained in a prior reference frame. Therefore, P-frames are typically much smaller than I-frames, especially for video streams with relatively little motion or change of scenes. P-frames are also reference frames themselves, upon which successive P-frames or B-frames can rely for encoding purposes.
• B-frames (“bi-directionally predicted” frames) are inter-frame encoded frames that depend both upon prior frames and upon successive frames in the video stream. B-frames are the smallest type of frame and cannot be used as reference frames.
• A typical video stream is divided up into a series of frame units, each known as a “Group of Pictures” (“GoP”). Each GoP begins with an I-frame and is followed by a series of P and B-frames. The length of the GoP can be either fixed or variable. A typical GoP might last for 15 frames. In video sequences where there is little motion and few scene changes, the P and B-frames will tend to be small because little has changed in the image since the previous reference frame. However, in a video sequence with considerable motion or many scene changes, the P and B-frames will be considerably larger because they must contain more data to indicate the large amount of changes from the previous reference frame. Some video compression algorithms will even include an I-frame in the middle of a GoP when necessitated by a large amount of motion or a scene change in the video sequence. This allows successive P and B-frames to reference the recent I-frame and hence they can contain smaller amounts of data.
• The size of the encoded frames can also depend upon the amount of detail in the video sequence to be encoded. Images in a video sequence with a high resolution will produce encoded frames with more data than video sequences with a low resolution. For instance, the packets produced for a high-resolution HDTV signal will be considerably larger than those produced for a grainy IPTV stream.
• As discussed previously, not all packet losses or packet delays will have a human-perceptible impact upon a video sequence. The loss of a single B-frame will have little impact, because no other frames are dependent upon that frame and hence the image will only be distorted for the fraction of a second corresponding to the single B-frame. The loss of a reference frame (an I-frame or P-frame), however, will affect any P-frame or B-frame that depends on the reference frame. A series of packet losses—especially those involving reference frames—will begin to cause human-perceptible degradations in the video image quality. Furthermore, losses of reference frames at the beginning of a scene change or during high-motion video sequences are more likely to cause human-perceptible distortions than losses of reference frames in relatively static video sequences. Conversely, losses of non-reference frames during scene changes or high-motion video sequences are less likely to produce noticeable distortions because the visual artifact is obscured by the rapid changes in the images presented to the viewer.
• The GoP length and structure can be fixed or variable, depending upon the particular video stream. For streams with a fixed GoP structure, the I, P, and B frames occur at well-defined and fixed intervals within the video stream. In such a case, a network analyzer can easily determine whether a lost packet is part of an I, P, or B frame even if the video stream is encrypted. However, if the GoP structure within an encrypted video stream is variable or unknown to the network analyzer, then the network analyzer cannot readily determine the nature or content of a lost packet. Prior art systems have attempted to partially decrypt packets to determine their content. However, this will only work if the network analyzer has the encryption key.
SUMMARY OF THE INVENTION
• The invention provides a system and method for the estimation of the content of frames in an encrypted packet video stream without decrypting the packets. In addition, the invention estimates the subjective effect of lost packets on a viewer's perception of the video stream. The invention can also be used as an alternative method for estimating the content of unencrypted packet video streams.
• The invention works by first examining the packet headers to determine where a given frame begins and ends. (Because large frames are broken up into multiple packets, it cannot be assumed that each frame is contained in a single packet.) A network analyzer can accomplish this task, for example, by examining the timestamp fields contained in the RTP (Real-time Transport Protocol) headers of the packets in the video stream. Packets with identical timestamps comprise a single frame.
• Next, the analyzer classifies the frame observed within the interval as an I, P, or B-frame. For unencrypted video streams, the analyzer can simply read the frame type from the picture header. For encrypted video streams, the analyzer can read the frame type directly if it has the appropriate decryption key. Alternatively, the analyzer can estimate the type of the frame based on the size (in bytes) of the frame. As described earlier, I, P, and B frames are respectively large, medium, and small in relation to one another.
• In embodiments where the analyzer estimates the frame type based on the size of the frames, the network analyzer will begin by counting the number of bytes in the frame. It can do this by determining the size of the data payload in each packet and summing this value for all packets that comprise the frame. The analyzer will also estimate the size of any packets that were dropped and include this estimate in its overall byte count for the frame.
• The analyzer can detect a dropped packet by examining the packet sequence numbers, for example the RTP sequence number, to find any gaps in the sequence. (Because packets can travel in a non-sequential order, the analyzer will have to maintain a list of recently observed sequence numbers. It can then classify a missing sequence number as dropped if it has not been seen after a sufficient length of time.) The analyzer can estimate the size of a dropped packet based on the average size of the packets. Such an average can be computed, for example, as a weighted average of the last n packets, as an average of all packets received, or as an average over packets within the given GoP. In addition, the average could be limited to packets containing data of the same frame type (I, P, or B). The network analyzer can further calculate the average packet loss rate by determining the proportion of packets in the video stream that are dropped.
• The network analyzer will keep one or two “frame threshold” values so it can estimate the varying sizes of the I, P, and B-frames. Because I-frames are so much larger than P and B-frames, those frames with a byte count above a certain threshold (“I-frame threshold”) will be classified as I-frames. Similarly, some embodiments utilize a separate (lower) threshold (“P-frame threshold”) to discriminate between P and B-frames because the former are usually significantly larger than the latter. The I and P-frame thresholds can be continuously updated based on the varying sizes of the frames in the video stream.
• The network analyzer can also maintain values for the maximum, minimum, and average sizes of I, P, and B-frames, respectively. These values can be continuously updated. For each frame encountered, the network analyzer can compare its size to the average frame size of its type and compute the variance for the given frame. The network analyzer can further maintain average values for the frame variances.
• Because each I-frame begins a new GoP, the network analyzer can further calculate the length of each GoP it observes. The analyzer can also maintain maximum, minimum, average, and variance values for GoP length.
• For each GoP, the analyzer can estimate the amount of detail, motion, or panning present in the GoP. Similarly, the analyzer can estimate if there has been a scene change from the prior GoP to the current GoP. The analyzer can accomplish this by comparing the frame sizes and GoP length to the various maxima, minima, and averages described above.
• For instance, an I-frame that is relatively large in comparison to other I-frames in the video sequence indicates a high level of detail in the GoP of which it is a part. If a GoP contains P or B-frames that are relatively large, then the GoP is exhibiting a large amount of motion. Panning in a video sequence can be detected by the relatively more frequent transmission of I-frames. A scene change is indicated when an I-frame is sent in the middle of a normal GoP and effectively restarts the GoP.
• After calculating these various metrics, the network analyzer could use them as inputs to a video quality estimation algorithm. Such an algorithm could calculate the estimated peak signal to noise ratio (PSNR) and deliver a mean opinion score (MOS).
BRIEF DESCRIPTION OF THE DRAWINGS
• FIG. 1 is a block diagram of a system in one embodiment of the invention.
• FIG. 2 is an illustration of a Group of Pictures (GoP) within a packet video stream.
• FIG. 3 is a chart demonstrating the various sizes (in bytes) of frames within a GoP.
• FIG. 4 is a flow diagram illustrating the operation of the network analyzer in one embodiment of the invention.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
• FIG. 1 is a diagram of a system in one embodiment of the invention. Avideo source101 is sending a packet video stream to avideo receiver102 over apacket network103 or over the air. Thevideo source101 could be, for example, an internet web server streaming video to thereceiver102. Alternatively, thevideo source101 could be a broadband cable television company streaming video to thereceiver102. Likewise, thevideo receiver102 could be a computer or a television set. Thepacket network103 could be the internet or a private network.
• Anetwork analyzer104 reads the packets that are being sent fromsender101 torecipient102. Thenetwork analyzer104 could be incorporated into a set-top box, television set, IP gateway, network router, ONU, cellular handset or the like. Alternatively, thenetwork analyzer104 could be a stand-alone test and measurement device or probe. Thenetwork analyzer104 could be implemented in software running on a general purpose device or with special-purpose hardware. Thenetwork analyzer104 will perform the measurements and calculations described further herein.
• FIG. 2 shows a representative view of a Group of Pictures within a packet video stream. It will be noted that the underlying packets carrying the frames are not shown. The frames are shown in sequence from left to right. The I-frame labeled1 is the first frame in the GoP. Following it are twelve inter-encoded (P and B-frames) in the same GoP. The I-frame labeled14 begins a new GoP.
• FIG. 3 shows a representative view of the size (in bytes) of the data comprising the frames of the GoP ofFIG. 2. It will be noted that the I-frames are significantly larger than the P or B-frames. It will also be noted that the P-frames are larger than the B-frames. As will be explained further below, “ithresh” and “pthresh” represent the threshold sizes for I-frames and P-frames respectively.
• FIG. 4 is a flow diagram illustrating the operation of the network analyzer in one embodiment. Atstep401, the analyzer will buffer or store certain information for each packet that it encounters. Such information will include the packet sequence number, timestamp field, and the size (in bytes) of the data payload. The analyzer must buffer a sufficient number of packets so it can 1) correlate packets containing the same timestamp and 2) detect lost packets using the sequence numbers.
• Atstep402, the analyzer will identify all packets with an identical timestamp. These packets comprise a single frame of the video sequence.
• The analyzer will also determine the number (if any) of packets that have been lost during the present frame by examining the sequence numbers contained in the packets. If a sequence number is missing and is not received within a certain time period (1 sec, e.g.), then the network analyzer will assume that the packet has been dropped by the network. (Because packets can arrive in a non-sequential order, the network analyzer cannot immediately assume that a missing packet has been dropped. Rather, the missing packet could simply have traveled over a slower network segment than the subsequent packet(s).) Dropped packets that appear at a frame boundary—i.e., between packets with differing timestamps—can be arbitrarily assigned to the preceding or succeeding frame. Alternatively, such dropped boundary packets could be assigned based on other factors, such as the size or type of the preceding or succeeding frames.
• The network analyzer will also calculate the average size of the data payload in the packets observed over a period of time. Such an average could be taken over all packets received, as a weighted average of the last n packets, or as an average over all packets within the last n GoPs. In some embodiments, separate averages could be maintained for packets containing data of the same frame type (I, B, or P). The identification of frame type will be described instep406, below.
• Some embodiments will maintain counters that keep running totals for the number of packets lost and the total number of packets in the video stream(s) (either received or lost) over a period of time. The network analyzer could periodically reset such counters to zero at specified times such as the beginning of a video stream or the beginning of a day, week, month, etc.
• The following table illustrates the values that will be calculated in step402:

• TABLE 1
  Value	Description	Calculation
  npackets_lost	Number of packets lost	<Reset to zero at the
  	for the present frame.	beginning of each frame.
  		Incremented each time a
  		lost packet is detected.>
  npackets_received	Number of packets	<Reset to zero at the
  	actually received for	beginning of each frame.
  	the present frame.	Incremented each time a
  		packet is received.>
  npackets	Number of packets in the	npackets_lost +
  	present frame (including	npackets_received
  	lost packets).
  av_packet_size	Average size of packet	<Average size over the
  	data payload (over	last n packets.>
  	multiple frames) for a
  	given time period.
  total_npackets_lost	Total number of packets	<Incremented each
  	lost (over multiple	time a lost packet is
  	frames) for a given	detected.>
  	time period.
  total_npackets	Total number of packets	<Incremented each
  	in video stream(s) (over	time a packet is received
  	multiple frames) for a	or a lost packet is
  	given time period.	detected.>

• Atstep403, the network analyzer will calculate the size (in bytes) of the frame identified instep402. It will do this by summing the data payload size for all the packets that comprise a single frame. The network analyzer will include in this calculation an estimated size of any lost packet(s) that were part of the frame. Such an estimate can be based on the average packet size (av_packet_size) computed instep402.
• The following table represents the data that will be measured, estimated, or calculated duringstep403.

• TABLE 2
  Value	Description	Calculation
  nbytes_received	Number of bytes actually	<Measured value>
  	observed for the present frame.
  estimated_nbytes_lost	Estimated number of bytes lost in	estimated_nbytes_lost =
  	dropped packets for the present	npackets_lost*
  	frame.	av_packet_size
  nbytes	Number of bytes for the present	nbytes = nbytes_received +
  	frame (including estimate of lost	estimated_nbytes_lost
  	bytes.)
  av_nbytes	†Average number of bytes per	av_nbytes = (av_nbytes*
  	frame.	15 + nbytes)/16
  total_nbytes_lost	Total number of bytes lost (over	total_nbytes_lost =
  	multiple frames) for a given time	total_nbytes_lost +
  	period.	estimated_nbytes_lost
  total_nbytes	Total number of bytes in video	total_nbytes = total_nbytes +
  	stream(s) (over multiple frames)	nbytes
  	for a given time period.
  †Av_nbytes can be calculated using a variety of averaging techniques, as described above in relation to av_packet_size.

• As described above, nbytes_received is simply the size of the data payloads for the present frame that were actually observed by the network analyzer. Estimated_nbytes_lost represents the aforementioned estimate of the number of bytes lost in dropped packets for the frame. Finally, nbytes represents an estimate of the actual number of bytes in the frame.
• Total_nbytes_lost and total_nbytes are running counters that accumulate (over multiple frames) the values of estimated_nbytes_lost and nbytes, respectively. These counters can be reset to zero at different times in different embodiments. For instance, they could be reset to zero at the beginning of each video stream; after n number of packets, frames, or GoPs; or after n number of seconds, minutes, hours, or days. Alternatively, they could be reset to zero arbitrarily by the user or only when the network analyzer is first installed.
• Some embodiments will maintain total_npackets_lost and total_npackets (as calculated in step402) in lieu of, or in addition to, total_nbytes_lost and total_nbytes.
• Instep404, the network analyzer will calculate and update a value representing the packet loss rate (“PLR”). This value simply represents the proportion of sent packets that have been dropped in the network. It can be calculated using either of the following two equations:
• 
  PLR=total_—npackets_lost/total_—npackets  (Eq. 1)
• 
  PLR=total_—nbytes_lost/total_—nbytes  (Eq. 2)
• Equation 1 is more precise thanEquation 2 because the latter includes estimated sizes of dropped packets, as discussed above.
• Atstep405, the network analyzer will perform calculations to update the frame threshold(s). InFIG. 3, the “ithresh” line indicates the I-frame threshold level and the “pthresh” line indicates the P-frame threshold level. The network analyzer will classify frames that have a byte count above ithresh as I-frames. Likewise, it will classify frames with a byte count above pthresh (but below ithresh) as P-frames. Any frames with a byte count lower than pthresh will be classified as B-frames.
• To calculate the I-frame threshold, the network analyzer will maintain a value for the largest I-frame (“scaled_max_iframe”). This value will periodically be multiplied by a scaling factor (less than 1.0). The scaling factor will gradually reduce the value stored in scaled_max_iframe to compensate for abnormally large I-frames.
• The network analyzer will compare every newly encountered frame with scaled_max_iframe. If the newly encountered frame has more bytes than scaled_max_iframe, then the latter will be set to the former. In essence, this step will search for a new maximum sized I-frame. The following pseudo-code illustrates the calculation of scaled_max_iframe.

• scaled_max_iframe = scaled_max_iframe * 0.995 //Apply scaling factor
  if (nbytes > scaled_max_iframe) then  //New maximum I-frame
  scaled_max_iframe = nbytes

• Finally, the network analyzer will update the value of ithresh. The analyzer can use a variety of algorithms to periodically recalibrate ithresh. These algorithms apply scaling factors to such variables as scaled_max_iframe and av_nbytes. For example, in one embodiment, the network analyzer will calculate ithresh as follows:
• 
  ithresh=(scaled_max_—iframe/4+av_—nbytes*2)/2
• This calculation averages two heuristics to calculate the I-frame threshold level. First, the I-frame threshold level is estimated as being one-quarter of the maximum scaled I-frame (scaled_max_iframe/4). Second, the I-frame threshold level is estimated as being twice the size of the average frame size (av_nbytes*2). These two estimates are then averaged to calculate ithresh.
• In other embodiments, the network analyzer could calculate ithresh by applying scaling factors to other variables such as av_iframe_size and max_iframe_size (explained below) or ithresh itself. Different scaling factors can also be used.
• The network analyzer can calculate pthresh in a similar manner to ithresh. First, the network analyzer will maintain a value for the maximum scaled P-frame:

• scaled_max_pframe = scaled_max_pframe * 0.995 //Apply
  scaling factor
  if ( (nbytes > scaled_max_pframe) && (nbytes < ithresh) ) then
  //New maximum P-frame
  scaled_max_pframe = nbytes

• Second, the network analyzer will calculate pthresh using a heuristic:
• 
  pthresh=av_—nbytes*(¾)
• This heuristic sets the P-frame threshold at three-quarters of the average size of all (I, P, and B) frames. Other embodiments can apply other scaling factors and use different variables such as av_pframe_size (explained below) and scaled_max_pframe.
• Atstep406, the network analyzer will classify the present frame as being an I-frame, P-frame, or B-frame. It will do this by comparing the size of the present frame with the values for ithresh and pthresh. The network analyzer will also calculate average values for the size of I-frames, P-frames, and B-frames, respectively. Finally, the network analyzer will calculate a variance for the present frame and an average variance over time. A frame's variance is simply the amount by which the frame is above or below average size (of the same type). The following table illustrates the values that will be calculated instep406, depending upon which frame type is detected (I, P, or B):

• 	TABLE 3
  	Value	Description
  	av_iframe_size	Average size of the last n I-frames.
  	iframe_variance	Variance of the present I-frame.
  	av_iframe_variance	Average variance of the last n I-frames.
  	av_pframe_size	Average size of the last n P-frames.
  	pframe_variance	Variance of the present P-frame.
  	av_pframe_variance	Average variance of the last n P-frames.
  	av_bframe_size	Average size of the last n B-frames.
  	bframe_variance	Variance of the present B-frame.
  	av_bframe_variance	Average variance of the last n B-frames.

• The following pseudo-code illustrates the classification of the frames by type and the calculation of the aforementioned values:

• 	if (nbytes > ithresh) then
  	/* I-frame detected */
  	av_iframe_size = (av_iframe_size * 7 + nbytes) / 8
  	iframe_variance = abs(nbytes − av_iframe_size)
  	av_iframe_variance = (av_iframe_variance * 7+
  	iframe_variance) / 8
  	else if (nbytes > pthresh) then
  	/* P-frame detected */
  	av_pframe_size = (av_pframe_size * 7 + nbytes) / 8
  	pframe_variance = abs(nbytes − av_pframe_size)
  	av_pframe_variance = (av_pframe_variance * 7+
  	pframe_variance) / 8
  	else
  	/* B-frame detected */
  	av_bframe_size = (av_bframe_size * 7 + nbytes) / 8
  	bframe_variance = abs(nbytes − av_bframe_size)
  	av_bframe_variance = (av_bframe_variance * 7+
  	bframe_variance) / 8

• From the pseudo-code, it can be seen that the present frame is classified based on its size in relation to ithresh and pthresh. One can also see that the average frame size is taken as a weighted average over the previous eight frames of the same type (whether an I, P, or B-frame.) The “abs” function in the pseudo-code represents an absolute value function that is used to calculate the amount the present frame is above or below average. Finally, the frame variances are averaged over the previous eight frames of the same type.
• It will be recognized by those skilled in the art that different averaging algorithms could be used to calculate the average frame size and average frame variance. Such averages could be taken over all (or n) previous frames of the same type, for example.
• If an I-frame was detected instep406, then the network analyzer will proceed to step407a, where it will calculate values related to the GoP length. The following table describes the data that will be calculated instep407a:

• TABLE 4
  Value	Description
  nframes	A counter for the number of frames in the
  	current Group of Pictures (GoP).
  last_GoP_length	The total number of frames in the
  	immediately preceding GoP.
  penultimate_GoP_length	The total number of frames in the
  	penultimate GoP.
  av_GoP_length	The average number of frames in a GoP
  	for a given time period.
  max_GoP_length	The number of frames in the largest GoP
  	encountered.

• The following pseudo-code illustrates the logic used to calculate the data of Table 4:

• penultimate_GoP_length = last_GoP_length
  last_GoP_length = nframes
  av_GoP_length = (av_GoP_length * 15 + last_GoP_length) / 16
  if (last_GoP_length > max_GoP_length) then
  max_GoP_length = last_GoP_length

• The nframes counter represents the number of frames encountered (so far) in a GoP. Because an I-frame, by definition, begins a new GoP, the nframes counter will, at the beginning ofstep407a, contain a value indicating the length of the immediately prior GoP. (As will be seen insteps407band412, the nframes counter is incremented whenever a P-frame or B-frame is encountered and reset to one (1) after an I-frame is encountered.)
• At the beginning ofstep407a, the network analyzer will move the current value in last_GoP_length to penultimate_GoP_length. (See ¶ [0088].) The analyzer will then save the nframes value as last_GoP_length. (See ¶ [0089].) Thus, the analyzer will maintain the GoP length for the last two GoPs. Some embodiments of the invention could maintain an array of multiple GoP lengths going back an arbitrary number of GoPs.
• Next, the network analyzer will update the value representing the average size of a GoP, av_GoP_length. In the pseudo-code above, the network analyzer calculates a weighted average GoP length over the past 16 GoPs. Such an average could be taken over the past n GoPs and/or could be periodically reset at the beginning of a video stream or beginning of a time period such as an hour, day, week, month, etc.
• The network analyzer will also update the value of max_GoP_length if the previous GoP was the longest GoP encountered so far. (See ¶å [0092]-[0093], above.) Like av_GoP_length, max_GoP_length could be periodically reset to zero.
• Atstep408, the network analyzer will estimate the amount of detail present in the most recent I-frame. Relatively detailed images require relatively large I-frames; conversely, images with relatively little detail result in relatively small I-frames. Thus, the network analyzer can compare the size (in bytes) of the most recent I-frame with the maximum I-frame encountered. This is illustrated by the following:

• 	if (nbytes > 0.75 * scaled_max_iframe) then
  	detail = high
  	else if (nbytes < 0.3 * scaled_max_iframe) then
  	detail = low
  	else
  	detail = medium

• Those skilled in the art will recognize that nbytes could instead be compared to the average I-frame size (av_iframe_size), a maximum I-frame size (max_iframe_size), or some combination of the above. It will further be recognized that percentages other than 75% and 30% could be used to determine the level of detail. In addition, finer granularity could be achieved by making more comparisons.
• Atstep409, the network analyzer will estimate the amount of motion in the recent frames. High levels of motion result in larger than average P and B frames. Thus, the analyzer can compare the sizes of recent P and B frames with historical maxima (such as scaled_max_iframe):

• 	av_pbframe_size = (av_pframe_size + av_bframe_size) / 2
  	if (av_pbframe_size > 0.25 * scaled_max_iframe) then
  	motion = high
  	else if (av_pbframe_size > 0.125 * scaled_max_iframe) then
  	motion = medium
  	else if (av_pbframe_size > 0.05 * scaled_max_iframe) then
  	motion = low
  	else
  	motion = none

• This pseudo-code begins by combining the average frame size for recent P-frames and B-frames. (See ¶ [00109].) It is important that av_pframe_size and av_bframe_size are weighted averages over recent past P-frames and B-frames, respectively. (See ¶¶ [0074] and [0080], above, illustrating averages over the past eight P-frames and B-frames, respectively.) Thus, the combined av_pbframe_size represents the average frame size of recent P and B-frames.
• Next, the analyzer compares av_pbframe_size against scaled_max_iframe to determine the comparative size of the recent P and B-frames. In this embodiment, if av_pbframe_size is greater than 25% of the size of the largest scaled I-frame, then the analyzer will record that the video stream is experiencing a high degree a motion. If av_pbframe_size is at least 12.5% of scaled_max_iframe (but less than 25%), then the video stream is classified as exhibiting a medium amount of motion. An av_pbframe_size above 5% of scaled_max_iframe (but below 12.5%) indicates low motion. Any av_pbframe_size below 5% of scaled_max_iframe is classified as having no motion.
• Those skilled in the art will recognize that the network analyzer could make other similar comparisons to determine the degree of motion in the video stream. For instance, the size of the recent P and B-frames could be compared to the average size of I-frames instead of a maximum scaled (or non-scaled) I-frame size. Additionally, the size of recent P and B-frames could be compared to maximum P and B-frame sizes. The size of recent P and B-frames could be compared to average P and B-frames over an extended period of time (as opposed to simply the last eight P and B-frames.) The size of recent P and B-frames could also be compared to idealized or empirical values for average P and B-frames. The network analyzer could use different percentages than the 25%, 12.5%, and 5% described above. The analyzer could also make more or fewer comparisons to increase or decrease the granularity of its estimations. The analyzer could also make these comparisons for each individual P-frame or B-frame rather than for an average of the recent P and B-frames.
• Atstep410, the network analyzer will estimate whether there has been panning in the recent frames. Panning is the lateral motion of a camera within a scene. When a video stream contains panning, new I-frames must be sent more frequently to convey the constantly changing image data. This is unlike the motion described instep409 where the camera remains focused on an object (or group of objects) that are moving.
• The network analyzer can detect the increased frequency of I-frames characteristic of panning by examining the length of the last two (or more) GoPs. If those GoPs are relatively short in comparison to other GoPs, then the network analyzer will conclude that the video sequence contains panning data. The following pseudo-code illustrates this concept:

• 	if ( (last_GoP_length < 0.6 * max_GoP_length) &&
  	(penultimate_GoP_length < 0.6 * max_GoP_length) ) then
  	panning = true
  	else
  	panning = false

• In this embodiment, the network analyzer will determine that the video sequence is exhibiting panning if the last two GoPs are less than 60% the size of the maximum GoP length. In embodiments that keep a record of three or more GoPs, then the network analyzer could make comparisons over multiple GoPs.
• Those skilled in the art will recognize that these comparisons could be made with percentages other than 60%. It will further be recognized that comparisons could be made to an average GoP length (rather than max_GoP_length).
• Atstep411, the network analyzer will estimate if there has been an abrupt scene change in the video sequence. An abrupt scene change often results in an I-frame being sent to mark the scene change. This I-frame may truncate the previous GoP or simply be inserted into the GoP, resulting in an apparently short GoP. A scene change is different from panning in that the former results in a single short GoP whereas the latter results in several short GoPs in a row.
• The following pseudo-code illustrates the detection of a scene change:

• 	if ( (last_GoP_length < max_GoP_length) &&
  	(penultimate_GoP_length = max_GoP_length) ) then
  	scene_change = true
  	else
  	scene_change = false

• In this embodiment, the network analyzer will determine that the video sequence has experienced a scene change if the prior GoP length was abnormally short while the penultimate GoP length was equal to max_GoP_length. In video systems that employ variable GoP sizes, the comparison would be made based on the similarity of the penultimate GoP to the average GoP rather than exact equivalence.
• Those skilled in the art will recognize that these comparisons could be made with other statistical characteristics of previous GoP lengths. Further, in embodiments that maintain a record for the past three (or more) GoPs, the network analyzer could search for an abnormally truncated GoP in between two (or more) average sized GoPs.
• Atstep412, the analyzer will reset the value of nframes to one (1). This is because the current I-frame is the first frame in the new GoP.
• Atstep407b, the analyzer will increment the value of nframes each time the analyzer encounters a P or B-frame. In this manner, the nframes counter will properly count the frames in a GoP, starting with an I-frame and ending with the last P or B-frame before the next I-frame.
• Followingsteps412 and407b, the network analyzer will examine the next frame in the buffer and repeat the process over again.
• Those skilled in the art will recognize that the content estimation of steps408-411 could be performed at other times. That is, steps408-411 need not be performed every time an I-frame is detected. In some embodiments, for instance, some or all of those steps could be performed at periodic intervals such as every ten seconds. In some embodiments, some or all of steps408-411 could be performed whenever a certain number of frames had been received.
• In some embodiments, the network analyzer could forego counting the individual bytes in each packet and instead just count the number of packets per frame. Thus, the values for frame thresholds and frame sizes would be calculated based on the number of packets (rather than bytes) per frame. These embodiments would essentially operate at a higher level of granularity and would thus be less accurate in predicting frame type and estimating the content of the video sequence. Nevertheless, these embodiments would provide some level of content estimation for video streams.
• The content related metrics computed as described above may be used to provide general information on the nature of the video content being carried or to recognize if there are certain types of content related problems. For example, if the level of detail appears normal and there is no apparent motion for an extended period of time then the video content may have “frozen”. As a further example, if the level of detail appears consistently very low and there appears to be no motion then the video content may be “blank”. If these blank, frozen or other similar problems are detected then the service provider may be alerted to correct the problem.
• The metrics and content estimation calculated by the network analyzer can be used as inputs to a video quality estimation algorithm to calculate metrics such as an estimated peak signal to noise ratio (PSNR) or a mean opinion score (MOS). In addition, the data can be used to provide statistical data over time or immediate feedback to a network operator or automated system administrator to diagnose problems within a network. Such a network operator could try to repair those problems.
• Accordingly, while the invention has been described with reference to the structures and processes disclosed, it is not confined to the details set forth, but is intended to cover such modifications or changes as may fall within the scope of the following claims.

Claims (30)

1. A method for estimating the type of a plurality of video frames in a packet video stream comprising the steps of:

a) comparing the size of each of said plurality of video frames to a first threshold;

b) classifying each of said plurality of video frames as a first type if said video frame is larger than said first threshold; and

c) classifying each of said plurality of video frames as a second type if said video frame is smaller than said first threshold.

2. The method ofclaim 1 further comprising the step of periodically adjusting said first threshold based on the size of said video frames in said packet video stream.

3. The method ofclaim 1 further comprising the steps of:

a) comparing the size of each of said video frames of said second type to a second threshold; and

b) classifying each of said video frames of said second type as a third type if said video frame is smaller than said second threshold.

4. The method ofclaim 3 further comprising the step of periodically adjusting said second threshold based on the size of said video frames in said packet video stream.

5. A method for estimating the content of a plurality of video frames in a packet video stream comprising the steps of:

a) classifying each of said video frames by type;

b) determining the size of each of said video frames; and

c) estimating the level of detail in said video stream based on the type and size of said video frames in said video stream.

6. A method for estimating the content of a plurality of video frames in a packet video stream comprising the steps of:

a) determining the size of each of said plurality of video frames in said video stream;

b) comparing the size of each of said plurality of video frames to a first threshold;

c) classifying each of said plurality of video frames as a first type if said video frame is larger than said first threshold;

d) classifying each of said plurality of video frames as a second type if said video frame is smaller than said first threshold;

e) classifying said video stream as exhibiting a high level of detail if said video frames of said first type are relatively large; and

f) classifying said video stream as exhibiting a low level of detail if said video frames of said first type are relatively small.

7. A method for estimating the content of a plurality of video frames in a packet video stream comprising the steps of:

a) classifying each of said video frames by type;

b) determining the size of each of said video frames; and

c) estimating the amount of motion in said video stream based on the type and size of said video frames in said video stream.

8. A method for estimating the content of a plurality of video frames in a packet video stream comprising the steps of:

a) classifying each of said video frames by type;

b) determining the size of each of said video frames; and

c) estimating the presence of panning in said video stream based on the distribution of different types of said video frames in said video stream.

9. A method for estimating the content of a plurality of video frames in a packet video stream comprising the steps of:

a) classifying each of said video frames by type;

b) determining the size of each of said video frames; and

c) estimating whether a scene change in said video stream has occurred based on the distribution of different types of said video frames in said video stream.

10. A method for estimating the content of a plurality of video frames in a packet video stream comprising the steps of:

a) comparing the size of each of said video frames to a first counter;

b) classifying each of said frames as a first type of frame if said frame is larger than said first counter; and

c) classifying each of said frames as a second type or a third type of frame if said frame is smaller than said first counter.

11. The method ofclaim 10 wherein step (c) further comprises:

a) comparing each of said frames to a second counter;

b) classifying each of said frames as the second type of frame if said frame is smaller than said first counter and larger than said second counter; and

c) classifying each of said frames as the third type of frame if said frame is smaller than said second counter.

12. The method ofclaim 10 wherein said first counter is calculated by multiplying the size of the largest frame encountered in said video stream by a scaling factor.

13. The method ofclaim 10 wherein said first counter is calculated by multiplying the average size of said frames encountered in said video stream by a scaling factor.

14. The method ofclaim 10 wherein said first counter is calculated by the steps comprising:

a) multiplying the size of the largest frame encountered in said video stream by a first scaling factor to obtain a first value;

b) multiplying the average size of said frames encountered in said video stream by a second scaling factor to obtain a second value;

c) computing a weighted average of said first and second values.

15. A method for estimating the level of detail of a plurality of I-frames in a packet video stream comprising the steps of:

a) comparing the size of each of said I-frames to a counter; and

b) characterizing each of said I-frames to a detail level based on said comparison of step (a) wherein relatively larger I-frames are characterized as having a relatively high level of detail and relatively smaller I-frames are characterized as having a relatively low level of detail.

16. The method ofclaim 15 wherein said counter is calculated by multiplying the size of the largest I-frame encountered in said video stream by a scaling factor.

17. The method ofclaim 15 wherein said counter is calculated by multiplying the average size of said I-frames encountered in said video stream by a scaling factor.

18. The method ofclaim 15 wherein said characterized level of detail is compared to a threshold and an indication generated if said level of detail is classified as low detail for a time exceeding a predetermined time threshold.

19. A method for estimating the level of motion in a plurality of frames comprising P-frames and/or B-frames in a packet video stream comprising the steps of:

a) computing the average size of said frames;

b) comparing said average to a counter; and

c) characterizing said plurality of frames to a motion level based on said comparison of step (a) wherein frames having a relatively larger average size are characterized as having a relatively high level of motion and frames having a relatively smaller average size are characterized as having a relatively low level of motion.

20. The method ofclaim 19 wherein said counter is calculated by multiplying the size of the largest frame encountered in said video stream frames by a scaling factor.

21. The method ofclaim 19 wherein said counter is calculated by multiplying the average size of frames encountered in said video stream by a scaling factor.

22. The method ofclaim 19 wherein said characterized level of motion is compared to a threshold and an indication generated if said level of motion is classified as very low motion for a time exceeding a predetermined time threshold.

23. A method for estimating the presence of panning in a packet video stream comprising the steps of:

a) calculating the length of a first Group of Pictures (GoP) in said video stream as a first value;

b) calculating the length of a second GoP immediately following said first GoP as a second value;

c) comparing said first value to a first counter;

d) comparing said second value to a second counter; and

e) classifying said video stream as containing panning if said first value is less than said first counter and said second value is less than said second counter.

24. The method ofclaim 23 wherein said first counter and said second counter are calculated by multiplying the length of the largest GoP encountered in said video stream by a scaling factor.

25. The method ofclaim 23 wherein said first counter and said second counter are calculated by multiplying the average length of GoPs encountered in said video stream by a scaling factor.

26. A method for estimating a scene change in a packet video stream comprising the steps of:

a) calculating the length of a first Group of Pictures (GoP) in said video stream as a first value;

b) calculating the length of a second GoP immediately following said first GoP as a second value;

c) comparing said first value to a first counter;

d) comparing said second value to a second counter; and

e) classifying said video stream as containing a scene change if said first value is greater than said first counter and said second value is less than said second counter.

27. The method ofclaim 26 wherein said first counter is calculated by multiplying the length of the largest GoP encountered in said video stream by a scaling factor.

28. The method ofclaim 26 wherein said second counter is calculated by multiplying the length of the largest GoP encountered in said video stream by a scaling factor.

29. The method ofclaim 26 wherein said first counter is calculated by multiplying the average length of GoPs encountered in said video stream by a scaling factor.

30. The method ofclaim 26 wherein said second counter is calculated by multiplying the average length of GoPs encountered in said video stream by a scaling factor.

Images