System and process for broadcast and communication with very low bit-rate bi-level or sketch video

• US 20050135480A1
• Filed: 02/04/2005
• Published: 06/23/2005
• Est. Priority Date: 01/05/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chen, Gang, Li, Jiang, Shum, Heung-Yeung
• Granted Patent: US 7,558,325 B2
• Time in Patent Office: Days
• US Class Current: 375/240.120
• CPC Class Codes: H04N 19/119 Adaptive subdivision aspects, e.g. subdivision of a picture into rectangular or non-rectangular coding blocks
• CPC Class Codes: H04N 19/156 Availability of hardware or computational resources, e.g. encoding based on power-saving criteria
• CPC Class Codes: H04N 19/17 the unit being an image region, e.g. an object
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/29 involving scalability at the object level, e.g. video object layer [VOL]

Abstract

A system and process for broadcast and communication with bi-level or sketch video at extremely low bandwidths is described. Essentially, bi-level and sketch video presents the outlines of the objects in a scene being depicted. Bi-level and sketch video provides a clearer shape, smoother motion, shorter initial latency and cheaper computational cost than do conventional DCT-based video compression methods. This is accomplished by converting each color or gray-scale image frame to bi-level or sketch image frame using adaptive thresholding method, compressing bi-level or sketch image frames into bi-level or sketch video using adaptive context-based arithmetic coding method. Bi-level or sketch video is particularly suitable to such small devices as Pocket PCs and mobile phones that possess small display screen, low bandwidth connection, and light computational power.

Claims

1-59. -59. (canceled)

60. A system for generating a bi-level video, comprising:

a general purpose computing device;

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

input digitized video comprising a sequence of video image frames,

convert the input video image frames into bi-level image frames, wherein the digitized video is characterized by pixels defined in terms either a color level or a gray scale level, and wherein said conversion comprises,

ascertaining whether the input video image frames comprises pixels defined in terms of a color level, and

converting each input video image frame so as to define each pixel thereof in terms of one of a plurality of gray scale levels so as to produce a gray scale image frame whenever the pixels are defined in terms of color levels, wherein the particular gray scale level selected to define a pixel is based on the color level of that pixel, such that this converting comprises,

computing a threshold gray scale level,

assigning a first of two bi-level image frame colors to those pixels that exhibit a gray scale level exceeding said threshold by a prescribed upper-limit amount,

assigning the second of said two colors to those pixel exhibiting a gray scale level that is less than said threshold by a prescribed lower-limit amount, and

associating an indicator with those pixels that exhibit a gray scale level which does not exceed said threshold by the upper-limit amount and which are not less than said threshold by the lower-limit amount, wherein one of the two bi-level image frame colors is assigned to the pixels having said indicator associated therewith based on a predicted value established for the pixel as part of the performance of the process action for encoding the bi-level image frames, and

encode the bi-level image frames.

61. The system of claim 60, wherein the program module for computing a threshold gray scale level for a bi-level image frame, comprises sub-modules for:

(a) computing the mean of the gray scale levels of all the pixels of the image frame and designating the computed mean as a current preliminary gray scale level threshold value;

(b) computing the mean of all the gray scale levels of a first group of pixels having a gray scale level equal to or exceeding the currently-designated preliminary threshold value;

(c) computing the mean of all the gray scale levels of a second group of pixels having a gray scale level less than the currently-designated preliminary threshold value;

(d) computing the average of the mean gray scale levels computed for the first and second groups of pixels;

(e) designating the computed average gray scale level of the two pixel groups as the current preliminary gray scale level threshold value in lieu of the previously-designated value;

(f) repeating actions (b) through (e), until the computed average gray scale level does not change; and

(g) designating the last-computed average gray scale level as the threshold gray scale level for the bi-level image frame under consideration.

62. The system of claim 60, wherein the program module for computing a threshold gray scale level for a bi-level image frame, comprises sub-modules for:

(a) computing the mean of the gray scale levels of all the pixels of the image frame and designating the computed mean as a current preliminary gray scale level threshold value;

(b) computing the mean of all the gray scale levels of a first group of pixels having a gray scale level equal to or exceeding the currently-designated preliminary threshold value;

(c) computing the mean of all the gray scale levels of a second group of pixels having a gray scale level less than the currently-designated preliminary threshold value;

(d) computing the average of the mean gray scale levels computed for the first and second groups of pixels;

(e) designating the computed average gray sale level of the two pixel groups as the current preliminary gray scale level threshold value in lieu of the previously-designated value;

(f) repeating actions (b) through (e), until the computed average gray scale level does not change;

(g) inputting a user-supplied gray scale level threshold adjustment value;

(h) computing the sum of said threshold adjustment value and the last-computed average gray scale level; and

(i) designating the sum of the threshold adjustment value and the last-computed average gray scale level as the threshold gray scale level for the bi-level image frame under consideration.

63. The system of claim 60, further comprising a program module, which is executed prior to assigning any bi-level image frame color to the pixels of a frame of the input video, for reducing a flickering effect in the bi-level video caused when correspondingly-located pixels in a series of consecutive frames which depict the same unchanged portion of a captured scene are varyingly assigned one or the other of two bi-level image frame colors owing to a change in the lighting conditions between the times the individual frames of the series were captured.

64. The system of claim 63, wherein the program module for reducing a flickering effect, comprises, for each pixel in each consecutive frame of the input video starting with the second frame, sub-modules for:

computing a Laplacian of the pixel under consideration in a current frame and of each pixels contained in the current frame within an region centered on the pixel under consideration;

computing Laplacians for each correspondingly-located pixel in the frame immediately preceding the current frame in the frame sequence which are contained within a region corresponding in location to said region in the current frame;

computing the difference between the Laplacian computed for each pair of correspondingly-located pixels in the current frame and its immediately preceding frame;

summing the absolute value of the computed differences, and designating the sum as a SAD of the pixel under consideration;

determining whether the SAD of the pixel under consideration is greater than a prescribed dissimilarity threshold; and

whenever the SAD is equal to or less than a prescribed dissimilarity threshold,

assigning to the pixel under consideration an indicator indicating the pixel is similar to the correspondingly-located pixel in the immediately preceding frame,

computing the difference between the gray scale level threshold computed for the current frame and the gray scale level threshold computed for immediately preceding frame,

adding the computed difference to the gray level value assigned to the pixel corresponding in location to the pixel under consideration in the immediately preceding frame to create a compensated gray level value, and

assigning the compensated gray level value to the pixel under consideration in lieu of the value previously assigned to the pixel.

65. The system of claim 64, further comprises a sub-module for assigning to the pixel under consideration an indicator indicating this pixel is dissimilar to the correspondingly-located pixel in the immediately preceding frame whenever the SAD is greater than the dissimilarity threshold.

66. The system of claim 65, wherein the input video frame under consideration depicts the upper body of a person, and wherein the system for generating a bi-level video further comprises program modules which, for each pixel row in a frame under consideration:

identify the two outermost pixels that are assigned an indicator indicating the pixel is dissimilar to the correspondingly-located pixel in the immediately preceding frame, for those pixel rows having at least two pixel marked as being dissimilar;

identify the intervening pixels that are assigned an indicator indicating the pixel is similar to the correspondingly-located pixel in the immediately preceding frame and which are between the identified outermost pixels assigned an indicator indicating the pixel is dissimilar to the correspondingly-located pixel in the immediately preceding frame;

assign to each identified intervening pixel an indicator indicating this pixel is dissimilar to the correspondingly-located pixel in the immediately preceding frame; and

reassign to each identified intervening pixel its original gray scale value.

67. The system of claim 65, further comprises the program modules for:

identifying for the pixel under consideration whether it is assigned an indicator indicating it is similar to the correspondingly-located pixel in the immediately preceding frame;

whenever the pixel under consideration is identified as having been assigned an indicator indicating it is similar to the correspondingly-located pixel in the immediately preceding frame, ascertaining whether less than a prescribed number of corresponding-located pixels in frames sequentially preceding the frame under consideration are each marked as dissimilar; and

whenever less than the prescribed number of corresponding-located pixels in frames sequentially preceding the frame under consideration are each marked as dissimilar,

assigning an indicator indicating the pixel under consideration is dissimilar to the correspondingly-located pixel in the immediately preceding frame in lieu of an indicator indicating similarity, and

reassigning the original gray scale value associated with the pixel under consideration.

68. The system of claim 65, further comprises program modules for:

identifying in the frame under consideration each region of substantially contiguous pixels that has been assigned an indicator indicating they are dissimilar to their correspondingly-located pixels in the immediately preceding frame; and

for each pixel located immediately adjacent each identified dissimilarity region,

assigning an indicator indicating the pixel is dissimilar to the correspondingly-located pixel in the immediately preceding frame in lieu of an indicator indicating similarity, and

reassigning the original gray scale value associated with the pixel.

69. The system of claim 60, wherein the program module for encoding the bi-level image frames, comprises a sub-module for encoding the bi-level frames employing an adaptive context-based arithmetic coding technique that comprises predicting whether a pixel under consideration exhibits one or the other of the two bi-level image frame colors based on the values of a prescribed pattern of previously-predicted pixels and then compares the predicted pixel value to the actual value of the pixel and encodes the bi-level image frame under consideration by indicating those pixels for which the predicted pixel value does not match the actual pixel value, with the exception of those pixels having said indicator associated therewith that indicates the pixel exhibits a gray scale level which does not exceed said threshold by the prescribed upper-limit amount and which are not less than said threshold by the prescribed lower-limit amount, said excepted pixels being presumed to have a predicted value that matches its actual value.

70. The system of claim 65, wherein the program module for encoding the bi-level image frames, comprises sub-modules for:

designating the first bi-level image frame and frames in the frame sequence occurring at a prescribed interval as I-frames;

designating the bi-level image frames in the frame sequence falling between a pair of consecutive I-frames, as p-frames;

determining the smallest bounding box that will surround all regions of dissimilarity in each p-frame;

encoding each I-frame using an adaptive context-based arithmetic coding technique; and

encoding each p-frame using an adaptive context-based arithmetic coding technique.

71. The system of claim 70, wherein the sub-module for encoding each I-frame, comprises sub-modules for:

encoding the I-frame employing an adaptive context-based arithmetic coding technique which utilizes a ½

probability table;

encoding the I-frame employing an adaptive context-based arithmetic coding technique which utilizes a pre-trained probability table;

determining whether the encoding utilizing a ½

probability table or the encoding utilizing a pre-trained probability table produces a bit stream with the lowest bit rate;

designating the bit stream produced using the probability table determined to produce the lowest bit rate as representing the encoded I-frame; and

incorporating in the bit stream designated as representing the encoded I-frame an indicator of the type of probability table used to encode the bit stream.

72. The system of claim 70, wherein the sub-module for encoding each p-frame, comprises sub-modules for:

encoding the portion of the p-frame contained within said bounding box employing an adaptive context-based arithmetic coding technique which utilizes a ½

probability table;

encoding the portion of the p-frame contained within said bounding box employing an adaptive context-based arithmetic coding technique which utilizes a pre-trained probability table;

determining whether the encoding utilizing a ½

probability table or the encoding utilizing a pre-trained probability table produces a bit stream with the lowest bit rate;

designating the bit stream produced using the probability table determined to produce the lowest bit rate as representing the encoded p-frame; and

incorporating in the bit stream designated as representing the encoded p-frame an indicator of the type of probability table used to encode the bit stream and the size and location of the bounding box.

73. The system of claim 71, wherein the sub-module for encoding each p-frame, comprises sub-modules for:

encoding the portion of the p-frame contained within said bounding box employing an adaptive context-based arithmetic coding technique which utilizes a ½

probability table;

encoding the portion of the p-frame contained within said bounding box employing an adaptive context-based arithmetic coding technique which utilizes a first pre-trained probability table;

encoding the portion of the p-frame contained within said bounding box employing an adaptive context-based arithmetic coding technique which utilizes a second pre-trained probability table which is identical to that employed to encode the last preceding I-frame in relation to the p-frame under consideration;

determining whether the encoding utilizing the ½

probability table, the first pre-trained probability table, or the second pre-trained probability table produces a bit stream with the lowest bit rate;

designating the bit stream produced using the probability table determined to produce the lowest bit rate as representing the encoded p-frame; and

incorporating in the bit stream designated as representing the encoded p-frame an indicator of the type of probability table used to encode the bit stream and the size and location of the bounding box.

74. The system of claim 71, wherein the sub-module for encoding each p-frame, comprises sub-modules for encoding the portion of the p-frame contained within said bounding box employing an adaptive context-based arithmetic coding technique which utilizes a ½

probability table;

encoding the portion of the p-frame contained within said bounding box employing an adaptive context-based arithmetic coding technique which utilizes a first pre-trained probability table;

encoding the portion of the p-frame contained within said bounding box employing an adaptive context-based arithmetic coding technique which utilizes a second pre-trained probability table which is identical to the final probability table resulting from the complete encoding of the last preceding I-frame in relation to the p-frame under consideration;

determining whether the encoding utilizing the ½

probability table, the first pre-trained probability table, or the second pre-trained probability table produces a bit stream with the lowest bit rate;

designating the bit stream produced using the probability table determined to produce the lowest bit rate as representing the encoded p-frame; and

incorporating in the bit stream designated as representing the encoded p-frame an indicator of the type of probability table used to encode the bit stream and the size and location of the bounding box.

75. The system of claim 64, further comprising a program module for controlling the bit rate at which the bi-level video image frames are encoded so as to maintain the average bit rate to less than or approximately equal to a target bit rate consistent with low bandwidth devices.

76. The system of claim 75, wherein the program module for controlling the bit rate at which the bi-level video image frames are encoded, comprises sub-modules for:

establishing a rate control table having a hierarchical sequence of rate control scale factors each of which is assigned values for at least one of (i) said prescribed upper-limit and lower-limit amounts, and (ii) said prescribed dissimilarity threshold, wherein the values assigned to a rate control scale factor higher in the hierarchy of the sequence are the same or larger than the values assigned to a lower level scale factor;

initially selecting one of the rate control scale factors and then utilizing any values assigned thereto for said prescribed upper-limit and lower-limit amounts and said prescribed dissimilarity threshold in converting image frames of the input video into bi-level image frames;

establishing a buffer of a prescribed size for storing the bits produced as the bi-level video image frames are encoded, until their transfer for further processing;

determining whether the number of bits stored at any time in the buffer exceed the half-size of the buffer by more than a first prescribed amount or are less than the half-size of the buffer by more than a second prescribed amount;

whenever the number of bits stored at any time in the buffer exceed the half-size of the buffer by more than the first prescribed amount, selecting the rate control scale factor one level up from the previously selected level and employing any values assigned to the newly-selected scale factor for the upper-limit and lower-limit amounts and the dissimilarity threshold in converting the next, previously-unconverted, image frame of the input video into a bi-level image frame, unless the top scale factor level is the currently-selected level in which case the currently-employed values of the upper-limit and lower-limit amounts and the dissimilarity threshold are used; and

whenever the number of bits stored at any time in the buffer are less than the half-size of the buffer by more than the second prescribed amount, selecting the rate control scale factor one level down from the previously selected level and employing any values assigned to the newly-selected scale factor for the upper-limit and lower-limit amounts and the dissimilarity threshold in converting the next, previously-unconverted, image frame of the input video into a bi-level image frame unless the lowest scale factor level is the currently-selected level in which case the currently-employed values of the upper-limit and lower-limit amounts and the dissimilarity threshold are used.

77. The system of claim 76, further comprising sub-modules for:

determining whether the number of bits stored at any time in the buffer exceed the size of the buffer; and

whenever the number of bits stored at any time in the buffer exceed the size of the buffer,

deleting the bits associated with the last-converted image frame from the buffer,

selecting the top rate control scale factor level, and

employing any values assigned to the newly-selected scale factor for the upper-limit and lower-limit amounts and the dissimilarity threshold in converting the next, previously-unconverted, image frame of the input video into a bi-level image frame, unless the top scale factor level is the currently-selected level in which case the currently-employed values of the upper-limit and lower-limit amounts and the dissimilarity threshold are used.

78. A computer-implemented process for generating a bi-level video, comprising:

an inputting step for inputting digitized video comprising a sequence of video image frames;

a converting step for converting the input video image frames into bi-level image frames, wherein the digitized video is characterized by pixels defined in terms either a color level or a gray scale level, and wherein said conversion step comprises,

an ascertaining step for ascertaining whether the input video image frames comprises pixels defined in terms of a color level, and

a converting step for converting each input video image frame so as to define each pixel thereof in terms of one of a plurality of gray scale levels so as to produce a gray scale image frame whenever the pixels are defined in terms of color levels, wherein the particular gray scale level selected to define a pixel is based on the color level of that pixel, such that this converting step comprises,

a computing step for computing a threshold gray scale level,

a first assigning step for assigning a first of two bi-level image frame colors to those pixels that exhibit a gray scale level exceeding said threshold by a prescribed upper-limit amount,

a second assigning step for assigning the second of said two colors to those pixel exhibiting a gray scale level that is less than said threshold by a prescribed lower-limit amount, and

an associating step for associating an indicator with those pixels that exhibit a gray scale level which does not exceed said threshold by the upper-limit amount and which are not less than said threshold by the lower-limit amount, wherein one of the two bi-level image frame colors is assigned to the pixels having said indicator associated therewith based on a predicted value established for the pixel as part of the performance of the process action for encoding the bi-level image frames; and

an encoding step for encoding the bi-level image frames.

79. A computer-readable medium having computer-executable instructions for generating a bi-level video, said computer-executable instructions comprising:

inputting digitized video comprising a sequence of video image frames;

converting the input video image frames into bi-level image frames, wherein the digitized video is characterized by pixels defined in terms either a color level or a gray scale level, and wherein said conversion instruction comprises,

ascertaining whether the input video image frames comprises pixels defined in terms of a color level, and

converting each input video image frame so as to define each pixel thereof in terms of one of a plurality of gray scale levels so as to produce a gray scale image frame whenever the pixels are defined in terms of color levels, wherein the particular gray scale level selected to define a pixel is based on the color level of that pixel, such that this converting instruction comprises,

computing a threshold gray scale level,

assigning a first of two bi-level image frame colors to those pixels that exhibit a gray scale level exceeding said threshold by a prescribed upper-limit amount,

assigning the second of said two colors to those pixel exhibiting a gray scale level that is less than said threshold by a prescribed lower-limit amount, and

associating an indicator with those pixels that exhibit a gray scale level which does not exceed said threshold by the upper-limit amount and which are not less than said threshold by the lower-limit amount, wherein one of the two bi-level image frame colors is assigned to the pixels having said indicator associated therewith based on a predicted value established for the pixel as part of the performance of the process action for encoding the bi-level image frames; and

encoding the bi-level image frames.