Generating a highly condensed visual summary

• US 7,697,785 B2
• Filed: 03/31/2004
• Issued: 04/13/2010
• Est. Priority Date: 03/31/2004
• Status: Active Grant

• Current Assignee: Fujifilm Business Innovation Corp. (Fujifilm Holdings Corporation)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Inventors: Girgensohn, Andreas, Chiu, Patrick, Liu, Qiong
• Primary Examiner(s): Le; Brian Q
• Assistant Examiner(s): Park; Edward
• Application Number:
  US10/815,354
• Publication Number:
  US 20050220345A1
• Time in Patent Office: 2,204 Days
• Field of Search: 382/190, 382/284, 382/167, 382/170, 382/209, 382/274, 345/629, 345/641, 348/584, 348/601
• US Class Current: 382/284
• CPC Class Codes: G06F 16/739 in form of a video summary, e.g. the video summary being a video sequence, a composite still image or having synthesized frames
• CPC Class Codes: G06F 16/784 the detected or recognised objects being people
• CPC Class Codes: G06F 16/785 using colour or luminescence
• CPC Class Codes: G06F 16/786 using motion, e.g. object motion or camera motion
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G11B 27/031 Electronic editing of digitised analogue information signals, e.g. audio or video signals
• CPC Class Codes: G11B 27/28 by using information signals recorded by the same method as the main recording G11B27/22 takes precedence

Abstract

In one embodiment, the present invention extracts video regions of interest from one or more videos and generates a highly condensed visual summary of the videos. The video regions of interest are extracted based on to energy, movement, face or other object detection methods, associated data or external input, or some other feature of the video. In another embodiment, the present invention extracts regions of interest from images and generates highly condensed visual summaries of the images. The highly condensed visual summary is generated by laying out germs on a canvas and then filling the spaces between the germs. The result is a visual summary that resembles a stained glass window having cells of varying shape. The germs may be laid out by temporal order, color histogram, similarity, according to a desired pattern, size, or some other manner. The people, objects and other visual content in the germs appear larger and become easier to see. The visual summary of the present invention utilizes important regions within the key frames, leading to more condensed summaries that are well suitable for small screens.

Claims

1. A computer implemented method implemented within a computer system including memory and CPU for generating a highly condensed visual summary of video regions, comprising:

utilizing the memory and CPU for defining a germ in each of a plurality of images, the germ containing a region of interest;

utilizing the memory and CPU for defining a support in each of the video segments, wherein the support is the video segment less the germ;

utilizing the memory and CPU for separating the germ from the video segments;

utilizing the memory and CPU for laying out the germs on a canvas, wherein there is no more than one germ for every video segment, wherein the canvas is partitioned into disjoint areas corresponding to the shape of the germs, wherein the shape of the disjoint areas is defined by a Voronoi algorithm; and

utilizing the memory and CPU for filling in the space of the canvas between the disjoint areas corresponding to the shape of the germs, wherein filling in the space of the canvas between the germs includes laying out one or more portions of the supports by assigning a pixel value of a point in the space from the same value as the corresponding pixel of the germ'"'"'s support when this point is nearest the germ, and only when the germ'"'"'s support does not encompass the point assigning pixel values of a support of a neighboring germ based on a distance from the point to the neighboring germ, wherein a point in the space is only assigned a background value if no support includes the point, to generate a highly condensed visual summary of the plurality of video segments.

2. The method of claim 1 wherein defining a germ includes:

defining a two dimensional shape that encompasses the projection of a dominant group onto the key frame.

3. The method of claim 2 wherein the two dimensional shape is a rectangle.

4. The method of claim 2 wherein laying out the germs includes:

determining a scale factor to be applied to every germ such that the germs are scaled to the maximum size that fits into the canvas.

5. The method of claim 2 wherein laying out the germs includes:

placing the germs in rows, wherein each row has a height according to the longest germ in the particular row.

6. The method of claim 2 wherein the two dimensional shape is irregular.

7. The method of claim 1 wherein defining a germ includes:

detecting a face in each of the plurality of images.

8. The method of claim 1 wherein defining a germ includes:

using an algorithm to determine a region of interest of an image.

9. A computer implemented method implemented within a computer system including memory and CPU for generating a highly condensed visual summary of video regions, comprising:

utilizing the memory and CPU for determining a germ in each of a plurality of images, the germ containing a region of interest;

utilizing the memory and CPU for defining a support in each of the video segments wherein the support is the video segment less the germ;

utilizing the memory and CPU for separating the germ from the video segments;

utilizing the memory and CPU for laying out the germs on a canvas, wherein the germs are laid out in irregular two dimensional shapes on the canvas;

utilizing the memory and CPU for defining a space between the germs; and

utilizing the memory and CPU for filling in the space of the canvas between the irregular two dimensional shape germs, wherein filling in the space of the canvas between the irregular two dimensional shape germs includes laying out one or more portions of the supports by assigning the same value as the corresponding pixel of the germ'"'"'s support when this point is nearest the germ, and only when the germ'"'"'s support does not encompass the point assigning a pixel value of a point in the space from pixel values of a support of a neighboring germ based on a distance from the point to the neighboring germ, wherein a point between the irregular two dimensional shape germs is assigned an average value of nearby point values only if no support includes the point, to generate a highly condensed visual summary of the plurality of video segments.

10. The method of claim 9 wherein determining a germ includes:

detecting a face in each of the plurality of images.

11. The method of claim 9 wherein determining a germ includes:

receiving user input, the user input associated with a part of an image.

12. The method of claim 9 wherein determining a germ includes:

using an algorithm to determine the regions of interest of an image based on one or more methods selected from the group consisting of a face-detection algorithm, an object detection algorithms and user input.

13. The method of claim 9 wherein laying out the germs includes:

determining a scale factor to be applied to every germ such that the germs are scaled to the maximum size that fits into the canvas.

14. The method of claim 9 wherein laying out the germs includes:

placing the germs in rows, wherein each row has a height according to the longest germ in the particular row.

15. A computer implemented method implemented within a computer system including memory and CPU for generating a highly condensed visual summary of video regions, comprising:

utilizing the memory and CPU for determining a dominant group in each of a plurality of video segments, wherein the dominant group includes a face;

utilizing the memory and CPU for determining a key frame in each of the video segments;

utilizing the memory and CPU for defining a germ associated with each dominant group in each of the video segments, wherein the germ is the x-y projection of the dominant group including the face onto the keyframe;

utilizing the memory and CPU for separating the germ from the video segments;

utilizing the memory and CPU for laying out the germs on a canvas, wherein the canvas is partitioned into disjoint areas corresponding to the germs, wherein the shape of the disjoint areas is defined using one or more algorithm selected from the group consisting of the distances between the germs, the distance between the face and the germ and the distance between two or more faces and the germ; and

utilizing the memory and CPU for filling in the space of the canvas between the disjoint areas corresponding to the germs, wherein filling in the space of the canvas between the germs includes laying out one or more portions of the supports by assigning a pixel value of a point in the space from the same value as the corresponding pixel of the germ'"'"'s support when this point is nearest the germ, and only when the germ'"'"'s support does not encompass the point assigning pixel values of a support of a neighboring germ based on a distance from the point to the neighboring germ, wherein a point between the irregular two dimensional shape germs is assigned an average value of nearby point values only if no support includes the point, wherein the canvas generated is a highly condensed visual summary of the plurality of video segments.

16. A computer implemented method implemented within a computer system including memory and CPU for generating a highly condensed visual summary of video regions, comprising:

utilizing the memory and CPU for determining a germ in each of a plurality of images,

the germ containing a region of interest;

utilizing the memory and CPU for defining a support in each of the video segments,

wherein the support is the video segment less the germ;

utilizing the memory and CPU for separating the germ from the video segments;

utilizing the memory and CPU for laying out the germs on a canvas, wherein the canvas is partitioned into disjoint areas corresponding to the shape of the germs;

utilizing the memory and CPU for computing boundary curves between the germs,

wherein the boundary curves between the germs are defined using one or more algorithm selected from the group consisting of the distance between a point and the closest border of the germ, the distance between a point and the center of a germ and the distance between a point and the size of the germ;

utilizing the memory and CPU for defining a space between the boundary curves; and

utilizing the memory and CPU for filling in the space of the canvas, wherein filling in the space of the canvas includes laying out one or more portions of the supports by assigning a pixel value of a point in the space from the same value as the corresponding pixel of the germ'"'"'s support when this point is nearest the germ, and only when the germ'"'"'s support does not encompass the point assigning pixel values of a support of a neighboring germ based on a distance from the point to the neighboring germ, wherein a point between the boundary curves is assigned an average value of nearby point values only if no support includes the point, to generate a highly condensed visual summary of the plurality of video segments.

17. The computer implemented method of claim 16 wherein the germs are laid out in irregular two dimensional shapes on the canvas.