Video to animation conversion with file size constraint

• US 20050122427A1
• Filed: 11/10/2004
• Published: 06/09/2005
• Est. Priority Date: 11/10/2003
• Status: Active Grant

• Current Assignee: Mobixell Networks Incorporated (Constellation Software Incorporated)
• Original Assignee: Mobixell Networks Incorporated (Constellation Software Incorporated)
• Inventors: Hougui, Yair, Novikov, Vladislav
• Granted Patent: US 7,177,474 B2
• Time in Patent Office: Days
• US Class Current: 348/453
• CPC Class Codes: H04N 19/103 Selection of coding mode or of prediction mode
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/132 Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
• CPC Class Codes: H04N 19/142 Detection of scene cut or scene change
• 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/182 the unit being a pixel
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• 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 7/122 involving expansion and subsequent compression of a signal segment, e.g. a frame, a line

Abstract

A method for converting video from a first format into a second format, the method including decoding into a series of frames video that is encoded in a first format, mapping the colors represented in the frames into a palette having fewer colors than the number of colors represented in the frames, removing noise from the frames, selectably removing at least one frame from the sequence, and re-encoding the sequence using the fewer colors into a second video format.

Claims

1. A method for converting video from a first format into a second format, the method comprising:

decoding into a series of frames video that is encoded in a first format;

mapping the colors represented in said frames into a palette having fewer colors than the number of colors represented in said frames;

removing noise from said frames;

selectably removing at least one frame from said sequence; and

re-encoding said sequence using said fewer colors into a second video format.

2. A method for color quantization of a sequence of video frames, the method comprising:

mapping a plurality of pixels in a series of video frames to a corresponding color in a palette;

defining a plurality of groups of colors in said palette;

weighting each of the colors in any of said color groups by its respective number of occurrences of each of said pixels of a particular color, wherein said weighting is applied to each color value in the color to be weighted;

summing said weighted color values in any of said color groups;

summing said number of occurrences of each of said pixels in said color group; and

dividing said summed weighted color values in said color group by said summed number of occurrences, thereby yielding a single color that represents the weighted mean of the said color group.

3. A method according to claim 2 wherein said defining step comprises masking said pixels with a bit mask.

4. A method according to claim 2 and further comprising maintaining a count for each of said numbers of occurrences.

5. A method according to claim 2 wherein said summing steps comprise separately summing for each color component of said color group.

6. A method according to claim 2 wherein said dividing step comprises separately dividing each color component of said color group by said summed number of occurrences.

7. A method according to claim 2 and further comprising merging said weighted mean color with a neighboring weighted mean color wherein said summed number of occurrences of said first-mentioned weighted mean color is below a predefined occurrence threshold, and wherein the difference between the merged color value and the value of said first-mentioned weighted mean color is below a predefined error threshold.

8. A method according to claim 7 wherein said merging step is performed a plurality of times until a merged palette is formed having a predetermined number of weighted mean colors.

9. A method according to claim 8 and further comprising constructing a set of indexed images corresponding to said frames of said original video where each pixel in said indexed images points to a color in said merged palette.

10. A method for smoothing an indexed palletized image, the method comprising:

rasterwise scanning the pixels of a palletized image with a sliding window;

determining a pixel value occurring most often within said window; and

setting any of said pixels within said window to said most often occurring pixel value.

11. A method according to claim 10 wherein said setting step comprises setting one of said pixels within a first distance from the leading extent of said window and within a second distance from the trailing extent of said window to said most often occurring pixel value.

12. A method according to claim 11 wherein said setting step comprises setting where said distances differ.

13. A method according to claim 10 and further comprising weighting any of said pixel values occurring within said window in accordance with a positionally corresponding predefined weight, wherein said weighting step is performed prior to performing said determining step.

14. A method for processing a region of interest in a sequence of frames, the method comprising:

deriving a difference frame between two consecutive frames in a sequence of frames, wherein each pixel position value in said difference frame is set equal to the absolute pixel value difference between its positionally corresponding pixels in both of said consecutive frames;

deriving a region of interest mask by multiplying the pixel position values in said difference frame by a weight map and setting any of said pixel position values in said region of interest mask to a predefined value as a function of its weighted value with respect to a predefined threshold;

defining a region of interest within the last of said two consecutive frames to include pixels that positionally correspond to pixel positions in said region of interest mask that have a predefined value; and

setting any of said pixels in the last of said two consecutive frames that lie inside said region of interest as transparent pixels if said pixels are identical to their positionally corresponding pixels in the first of said two consecutive frames and if said pixels are not part of a larger sequence of contiguous pixels with identical values.

15. A method according to claim 14 and further comprising excluding any of said pixels in the last of said two consecutive frames that lie outside said region of interest from being used to reconstruct said last frame.

16. A method according to claim 14 and further comprising:

identifying a segment of pixels in said region of interest, beginning at a pixel location corresponding to a pixel location in said difference frame whose value is equal to 0;

determining the number of contiguous pixels in said region of interest extending from said pixel location whose corresponding pixel locations in said difference frame all have a value equal to 0, thereby resulting in a transparency candidate run length;

determining the number of contiguous pixels in said region of interest extending from said pixel location having identical color values, thereby resulting in an identical color run length;

determining the length of said segment as the longer of said run lengths; and

setting the values of the pixels in said segment to a transparent pixel value if said transparency candidate run is longest.

17. A method for frame selection, the method comprising:

determining the size of a video segment;

should said size exceed a predefined limit;

measuring the amount of information in a frame of said video segment;

dropping the frame if said amount of information is below a predefined threshold.

18. A method according to claim 17 wherein said measuring step comprises:

selecting said frame as part of two consecutive frames; and

measuring the magnitude of change that occurs between said frame the other selected frame.

19. A method according to claim 18 wherein said measuring magnitude of change step comprises measuring using the following formula:

20. A method according to claim 18 wherein said measuring magnitude of change step comprises dividing the sum of absolute difference between pixels in a region of interest of said frame with corresponding pixels in the other selected frame by the number of pixels in said region of interest.

21. A method according to claim 17 and further comprising performing said steps a plurality of times for a plurality of frames of said video segment until said size does not exceed said predefined limit.

22. A method according to claim 21 and further comprising recalculating a region of interest and transparency pixels for a subsequent frame of said dropped frame.

23. A method according to claim 17 and further comprising:

calculating a display duration for said frame to be dropped;

retaining said frame in said video sequence if said display duration exceeds a predefined duration threshold.

24. A system for converting video from a first format into a second format, the system comprising:

means for decoding into a series of frames video that is encoded in a first format;

means for mapping the colors represented in said frames into a palette having fewer colors than the number of colors represented in said frames;

means for removing noise from said frames;

means for selectably removing at least one frame from said sequence; and

means for re-encoding said sequence using said fewer colors into a second video format.

25. A system for color quantization of a sequence of video frames, the system comprising:

means for mapping a plurality of pixels in a series of video frames to a corresponding color in a palette;

means for defining a plurality of groups of colors in said palette;

means for weighting each of the colors in any of said color groups by its respective number of occurrences of each of said pixels of a particular color, wherein said weighting is applied to each color value in the color to be weighted;

means for summing said weighted color values in any of said color groups;

means for summing said number of occurrences of each of said pixels in said color group; and

means for dividing said summed weighted color values in said color group by said summed number of occurrences, thereby yielding a single color that represents the weighted mean of the said color group.

26. A system according to claim 25 wherein said means for defining is operative to masking said pixels with a bit mask.

27. A system according to claim 25 and further comprising means for maintaining a count for each of said numbers of occurrences.

28. A system according to claim 25 wherein said means for summing are operative to separately sum for each color component of said color group.

29. A system according to claim 25 wherein said means for dividing is operative to separately divide each color component of said color group by said summed number of occurrences.

30. A system according to claim 25 and further comprising means for merging said weighted mean color with a neighboring weighted mean color wherein said summed number of occurrences of said first-mentioned weighted mean color is below a predefined occurrence threshold, and wherein the difference between the merged color value and the value of said first-mentioned weighted mean color is below a predefined error threshold.

31. A system according to claim 30 wherein said means for merging is operative to merge a plurality of times until a merged palette is formed having a predetermined number of weighted mean colors.

32. A system according to claim 31 and further comprising means for constructing a set of indexed images corresponding to said frames of said original video where each pixel in said indexed images points to a color in said merged palette.

33. A system for smoothing an indexed palletized image, the system comprising:

means for rasterwise scanning the pixels of a palletized image with a sliding window;

means for determining a pixel value occurring most often within said window; and

means for setting any of said pixels within said window to said most often occurring pixel value.

34. A system according to claim 33 wherein said means for setting is operative to set one of said pixels within a first distance from the leading extent of said window and within a second distance from the trailing extent of said window to said most often occurring pixel value.

35. A system according to claim 34 wherein said means for setting is operative to set where said distances differ.

36. A system according to claim 33 and further comprising means for weighting any of said pixel values occurring within said window in accordance with a positionally corresponding predefined weight, wherein said means for weighting is operative to weight prior to performing said determining step.

37. A system for processing a region of interest in a sequence of frames, the system comprising:

means for deriving a difference frame between two consecutive frames in a sequence of frames, wherein each pixel position value in said difference frame is set equal to the absolute pixel value difference between its positionally corresponding pixels in both of said consecutive frames;

means for deriving a region of interest mask by multiplying the pixel position values in said difference frame by a weight map and setting any of said pixel position values in said region of interest mask to a predefined value as a function of its weighted value with respect to a predefined threshold;

means for defining a region of interest within the last of said two consecutive frames to include pixels that positionally correspond to pixel positions in said region of interest mask that have a predefined value; and

means for setting any of said pixels in the last of said two consecutive frames that lie inside said region of interest as transparent pixels if said pixels are identical to their positionally corresponding pixels in the first of said two consecutive frames and if said pixels are not part of a larger sequence of contiguous pixels with identical values.

38. A system according to claim 37 and further comprising means for excluding any of said pixels in the last of said two consecutive frames that lie outside said region of interest from being used to reconstruct said last frame.

39. A system according to claim 37 and further comprising:

means for identifying a segment of pixels in said region of interest, beginning at a pixel location corresponding to a pixel location in said difference frame whose value is equal to 0;

means for determining the number of contiguous pixels in said region of interest extending from said pixel location whose corresponding pixel locations in said difference frame all have a value equal to 0, thereby resulting in a transparency candidate run length;

means for determining the number of contiguous pixels in said region of interest extending from said pixel location having identical color values, thereby resulting in an identical color run length;

means for determining the length of said segment as the longer of said run lengths; and

means for setting the values of the pixels in said segment to a transparent pixel value if said transparency candidate run is longest.

40. A system for frame selection, the system comprising:

means for determining the size of a video segment;

means for should said size exceed a predefined limit;

means for measuring the amount of information in a frame of said video segment;

means for dropping the frame if said amount of information is below a predefined threshold.

41. A system according to claim 40 wherein said means for measuring is operative to:

select said frame as part of two consecutive frames; and

measure the magnitude of change that occurs between said frame the other selected frame.

42. A system according to claim 41 wherein said means for measuring magnitude of change is operative to measure using the following formula:

43. A system according to claim 41 wherein said means for measuring magnitude of change is operative to divide the sum of absolute difference between pixels in a region of interest of said frame with corresponding pixels in the other selected frame by the number of pixels in said region of interest.

44. A system according to claim 40 wherein said means are operative for a plurality of frames of said video segment until said size does not exceed said predefined limit.

45. A system according to claim 44 and further comprising means for recalculating a region of interest and transparency pixels for a subsequent frame of said dropped frame.

46. A system according to claim 40 and further comprising:

means for calculating a display duration for said frame to be dropped;

means for retaining said frame in said video sequence if said display duration exceeds a predefined duration threshold.