Title of Invention: System and method for automatically generating an image to represent a video sequence
Abstract: A system automatically generates a representative image to represent a video sequence of a video program, and facilitates editing and manipulating of the video program. The system comprises receiving means (such as a frame selector or a unit extractor) for receiving a frame having at least one unit from a sequence of frames, resolving means (such as a unit extractor) for resolving one of the at least one unit, and generating means (such as an image engine) for generating an image representative of the sequence based on the unit. The system may further comprise a sequence divider for dividing the video program into multiple video sequences, and a frame selector for selecting the first sequence from the multiple sequences. The system may also comprise a unit distinction engine for determining distinct units from the units resolved by the resolving means, a unit predominance engine for defining predominance of each of the distinct units, and a unit representation engine for determining the distinct units which most uniquely represent the first video sequence. The resolving means preferably generates the representative image based on the distinct units determined by the unit representation engine to represent the first video sequence most uniquely. The resolving means may include an enhancement module for adding artwork or other enhancements to the representative image.
Detailed Description: Part PAC: DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT
Part PAR: FIG. 1 is a block diagram illustrating a computer system 100, in accordance with the present invention. The computer system 100 includes a processor 105, such as a SPARC.TM. processor available from Sun Microsystems, Inc. of Mountain View, Calif., an Intel Pentium.RTM. microprocessor or a Motorola Power PC.RTM. microprocessor, coupled to a signal bus 120. The computer system 100 further includes an input device 110 such as a keyboard or mouse, an output device 115 such as a Cathode Ray Tube (CRT) display, a data storage device 125 such as a magnetic disk, and an internal storage 130 such as Random-Access Memory (RAM), each coupled to the signal bus 120. The external storage 125 stores video sequences 135 in the form of a full-motion video program, and images 140 representing the video sequences 135. The computer system further includes a reader 165 coupled to the signal bus 120 for reading data from a computer-readable storage medium 160.
Part PAR_2: An operating system 145 controls processing by processor 105, and is typically stored in internal storage 130 (as illustrated) for execution by processor 105. An image generator 150 automatically generates a representative image 140 corresponding to a video sequence of video sequences 135. Image generator 150 also may be stored in internal storage 130 (as illustrated) for execution by processor 105. A video editor/player 155 enables manipulation, e.g., deletion, re-ordering, archiving, etc., of representative images 140 and performance of selected sequences. Video editor/player 155 is also stored in internal storage 130.
Part PAR_3: It will be appreciated that the video sequences 135, representative images 140, operating system 145, image generator 150, video editor/player 155 and other information may be stored on the computer-readable storage medium 160 and loaded via the reader 165 to the data storage device 125 or to internal storage 130. Alternatively, the video sequences 135, representative images 140, operating system 145, image generator 150, video editor/player 155 and other information may be stored on the data storage device 125 and loaded into internal storage 130 for execution. It will be further appreciated that one of ordinary skill in the art will recognize that the computer system 100 may include other devices, such as network connections for transferring information across a hardware channel, the Internet or an intranet, additional memory, additional processors, LANs, etc.
Part PAR_4: FIG. 2 is a block diagram illustrating details of the image generator 150. Image generator 150 includes a sequence divider 205, a frame selector 210, a unit extractor 215, a unit distinction engine 220, a unit predominance engine 225, a unit representation engine 230 and an image engine 235, each coupled to a communications channel 240. The image engine 235 includes an enhancements module 245. Although one of ordinary skill in the art knows that software routines/threads communicate via techniques such as memory sharing, system calls, etc., the elements are illustrated and described as being connected via a bus-like structure (i.e., communications channel 240) for simplicity.
Part PAR_5: The sequence divider 205 is preferably a software module for dividing a video program into video sequences 135. For example, a news broadcast video program may include a video sequence 135 providing sports updates, a video sequence 135 on the weather, a video sequence 135 on world news, a video sequence 135 on local news, etc. The sequence divider 205 examines the video program for appropriate sequence division and, for example, creates an index representing the start or end of each sequence 135. Sequence division may be performed by recognizing noise found between sequences 135, evaluating content (e.g., screening for words commonly used as sequence segues), recognizing background changes, prompting for user input, reviewing predefined index tables, etc.
Part PAR_6: The frame selector 210 automatically selects an untested video sequence 135 and an untested frame for examination. For example, the frame selector 210 may select in order the first video sequence 135, and may select every 30.sup.th frame. It will be appreciated that, since the conventional video player performs thirty frames per second, every frame need not be selected. Depending on the specific application or subject material, selecting every frame may lead to wasted processor and user time.
Part PAR_7: The unit extractor 215 uses pattern recognition (including contour recognition) and image analysis to extract, i.e., resolve, units from the frame selected by the frame selector 210. A unit is defined as an integral set of pixels representing a single physical object in the frame. For example, using pattern recognition, the unit extractor 215 may identify a grouping of orange-colored pixels (which may also have a similar contrast, brightness, etc.) as a single unit (e.g., a basketball). The unit extractor 215 preferably extracts all units possible from the selected frame. It will be appreciated that the unit extractor 215 may also use pattern recognition as described, for example, in "Fundamentals of Digital Image Processing" by Anil K. Jain (1989) and in "Machine Vision" by Ramesh Jain, Rangachar Kasturi and Brian Schunck (1995), which are hereby incorporated by reference.
Part PAR_8: It will be appreciated that the unit extractor 215 may examine other frames in a video sequence 135 to resolve particular units. That is, if the unit extractor 215 learns that the grouping of orange-colored pixels remain together in previous or subsequent frames, the unit extractor 215 may resolve integral units more accurately and efficiently. Further, the unit extractor 210 may examine units in previous or subsequent frames to resolve the greatest possible unit. For example, a shirt includes a collar, arms, buttons, cuffs, etc. The unit extractor 210 may initially determine that the collar is a unique unit, each arm is a unique unit, each button is a unique unit, each cuff is a unique unit, etc. However, by examining the units in the previous and subsequent frames, the unit extractor 210 can recognize that the shirt as a whole may be deemed an integral unit.
Part PAR_9: The unit distinction engine 220 reviews the units located in the frames of a video sequence 135 to identify like units and distinguish unlike units. That is, a unit shown in one frame most likely has similar attributes in a subsequent frame. Accordingly, the unit distinction engine 220 looks for common pixel groupings in the frames of the selected video sequence 135, recognizes like units, and defines the like units as instances of the same unit. For example, the unit distinction engine 220 may determine that a "basketball #1" unit in a first selected frame is similar to a "basketball #2" unit in a subsequent selected frame, and thus defines these basketballs as two instances of a single basketball unit. It will be appreciated that the unit distinction engine 220 may use unit distinction techniques as described, for example, in "Fundamentals of Digital Image Processing" and in "Machine Vision," which have been incorporated by reference above.
Part PAR_10: The unit predominance engine 225 determines the predominant units in the frames of a video sequence 135. Determining predominance may include examining unit attributes including the number of instances found of each particular unit, unit size relative to frame size, unit brightness, prominence or peculiarity of the unit relative to frame background, the amount of apparent unit motion across frames, the change in unit size across frames, unit shape, etc. The unit predominance engine 225 computes a predominance factor for each unit. For example, a basketball which is visible in substantially all frames may have a greater predominance factor than a wall advertisement which is visible in only a few frames. Further, the basket ball may have the same predominance factor as the scoreboard, which, although visible in fewer frames, has greater visibility, size, prominence, etc.
Part PAR_11: The unit representation engine 230 examines units having a high predominance factor, and based on this information selects the units that best represent the video sequence 135. The unit representation engine 230 may review frames in previous and subsequent video sequences 135 to determine whether a unit scoring a high predominance factor is unique to the current video sequence 135. For example, a particular newscaster scoring a high predominance factor in several sequential video sequences 135 does not effectively represent the current video sequence 135 with respect to the specific complete video program containing the sequences. The unit representation engine 230 eliminates units providing poor sequence representation, and selects the units providing best sequence representation.
Part PAR_12: Alternatively, to select representative units, the unit representation engine 230 may prompt for user input. The unit representation engine 230 may enable the user to select from all the units distinguished by the unit distinction engine 220, to select from units selected by the predominance engine 225, or to select a frame and to select one of the units in the frame. Other ways of selecting representative units may be used.
Part PAR_13: The image engine 235 uses the selected units to generate a representative image 140 for a video sequence 135. The representative image 140 may include a still image, a "moving" image or a combined still and moving image. For example, if the best representative units include a basketball and a scoreboard, the image engine 235 may generate a still image of the basketball superimposed over the scoreboard. The enhancements module 245 of the image engine 235 enhances the generated image, for example, by adding additional descriptive artwork to the generated image. For example, if the basketball appears to move across the frames of a sequence from the left side to the right side, then the enhancements module 245 may place lines representing air movement to the left of the basketball. The representative image 140 will thus be a still image of the scoreboard having a superimposed basketball with air-defining lines on the left side. Alternatively, to represent the movement of the basketball, the enhancements module 245 may create a thumbnail video image of a basketball moving from the left to the right. The representative image will thus be the scoreboard having a superimposed moving basketball thumbnail video image.
Part PAR_14: It will be further appreciated that representative image generation can be performed on sub-sequences (which respectively may be referred to as a video sequence 135). For example, a news program may include a video sequence 135 on crime, and the crime video sequence 135 may include a sub-sequence on local crime, a sub-sequence on national crime, a sub-sequence on legal reformation, etc. A representative image 140 may be generated for each of these video sub-sequences. Further, although representative image generation is being described herein relative to integral sequences and sub-sequences, one skilled in the art will recognize that an image can be generated to represent a portion of an integral video sequence 135. For example, multiple representative images 140 can be generated to represent portions of a sub-sequence reporting local weather. Still further, it will be appreciated that a meta-representative image 140 can be generated to represent a set of representative images 140. Accordingly, the resulting representative images 140 may be referred to as "hierarchical."
Part PAR_15: FIG. 3 is a block diagram illustrating details of the video editor/player 155 of FIG. 1. The video editor/player 155 includes a representative image viewer 305, a sequence editor 310, a sequence selector 315 and a video player 320, each coupled to a communications channel 325. Although the communications channel 325 is illustrated as a bus-like structure, one skilled in the art knows that conventional software techniques such as shared memory, system calls, etc. are typically used.
Part PAR_16: The representative image viewer 305 enables a user to view the representative images 140 generated by the image generator 150. For example, the representative image viewer 305 may display on the output device 115 the representative images 140 as an array of icons, preferably, in sequential order. For example, if a news program includes a first sequence on world news, a second sequence on local news, and a third sequence on the space program, then the representative image viewer 305 will place the world news representative image 140 first, the local news representative image 140 second, and the space program representative image 140 third. It will be appreciated that, should the representative images 140 contain representative sub-images 140 or be a member of a representative parent image 140, the representative viewer 305 may enable the user to peruse through the images using similar methods to those used when perusing through a set of software containers, windows, folders, etc. Alternatively, the representative viewer 305 may enable the user to view the images through the use of a tree-type structure. It will be further appreciated that, to provide a visual clue of the content and context of a particular video sequence 135, the representative image viewer 305 may enable the user to view the distinct units of the sequence 135 in order of predominance.
Part PAR_17: The sequence editor 310 enables a user to edit (e.g., delete, re-order, duplicate, etc.) video sequences 135 via the representative images 140. For example, the sequence editor 310 may enable the user to re-order the representative images 140, thereby re-ordering the video sequences 135, or may drag a representative image 140 into a waste basket, thereby deleting the corresponding video sequence 135. Accordingly, the news program may be edited so that the space program video sequence 135 comes first, the local news video sequence 135 comes second, and the world news video sequence 135 comes third. The sequence editor 310 may further enable the user to edit the content of a video sequence 135 via the representative images 140. For example, the user may delete, move, etc. representative sub-images 140 within a selected video sequence 135. Alternatively, the user may select a video sequence 135 (thereby causing the sequence editor 310 to enable the selection of frames), and may select a particular frame (thereby causing the sequence editor 310 to enable modification of the selected frame).
Part PAR_18: The sequence selector 315 and video player 320 enable a user to select and perform a video sequence 135 or video sequences 135. That is, the sequence selector 315 enables the user to select video sequences 135 to perform, and the video player 320 performs the selected video sequences 135. Selection and performance of the video sequences 135 by the sequence selector 315 and the video player 320 may differ from the actual broadcast. The user can select and re-order the video sequences 135 for review before the actual broadcast. For example, the user may already have ordered the representative images 140 of a video program, but may wish to re-order the representative sub-images 140 of a particular video sequence 135. The user may select and perform the video sub-sequences 135 in different orders without compromising the order of the parent video sequences 135. The video player 320 uses the representative images 140 as a guide to retrieving and performing the video sequences 135. Namely, the video player 320 retrieves and performs the video sequence 135 corresponding to the first representative image 140, then retrieves and performs the video sequence corresponding to the second representative image 140, etc. Similarly, it will be appreciated that retrieval and performance of a video sequence 135 may be controlled according to the order of its representative sub-images 140. It will be appreciated that, as an alternative to broadcasting, one could also archive, transmit, process, etc.
Part PAR_19: FIG. 4 illustrates a first example video sequence 400 exemplifying a video sequence 135. The first example video sequence 400 includes a first frame (Frame 1), a second frame (Frame 31) and a third frame (Frame 61). Frame 1 contains a person 404 wearing a hat 402 and tossing a basketball 406 into a basket 408 while a spectator 410 watches. Frame 31 contains a person 412 having his arms raised high, a hat 414 mid-air, and a basketball 416 within the net of a basket 418. Frame 61 contains two flying birds 420, a basketball 424, a hat 426 and a basket 422.
Part PAC_2: Generating a Representative Image for the First Example Video Sequence
Part PAR_20: The frame selector 210 selects Frame 1 and, for example, every thirty frames. The unit extractor 215 uses, for example, contour recognition to recognize the person, 404, the hat 412, the basketball 406, the basket 408 and the spectator 410. It will be appreciated that the objects recognized are based on the particular unit extractor 215 and the objects as drawn. For example, one unit extractor 215 may recognize basket 408 as a single unit, and another unit extractor 215 may recognize the pole as a first unit, the net as a second unit and the backboard as a third unit. However, the basket is being described as a single unit for simplicity. The frame selector 210 and unit extractor 215 perform similar methods on Frame 31 and on Frame 61.
Part PAR_21: The unit distinction engine 220 determines whether the units of one frame can be found and identified in the other frames. That is, the unit distinction engine 220 determines whether the basketball 406 can be found in Frame 31 or in Frame 61. By examining like attributes, the unit distinction engine 220 recognizes that person 404 and person 412 are instances of the same unit; that basketball 406, basketball 416 and basketball 424 are instances of the same unit; that hat 402, hat 414 and hat 426 are instances of the same unit, etc.
Part PAR_22: The unit predominance engine 225 computes the predominance factor for each of the units located. The unit predominance engine 225 recognizes two instances of a person 404/412, three instances of hat 402/414/426, one instance of spectator 410, three instances of basketball 406/416/424, three instances of basket 408/418/422, and one instance of birds 420. For simplicity, the predominance factor herein equals the number of instances of a unit. Accordingly, the predominance factor of person 404/412 is two, of hat 402/414/426 is three, of spectator 410 is one, of basketball 406/416/424 is three, of basket 408/418/422 is three, and of birds 420 is one. However, as stated above, the unit predominance engine 225 may apply size, contrast, uniqueness, and other variables to compute the predominance factors of the units.
Part PAR_23: The unit representation engine 230 determines the best representatives of the video sequence 400 from the units having the highest predominance factor. Assuming only two units per representative image 140, the unit representative engine 230 will select two units from the hat 408/414/426, the basketball 406/416/424 and the basket 408/418/422. As stated above, selection may be based on a review of previous and future video sequences 135 so that unique units can be selected. Upon review of FIG. 5, which illustrates a second example video sequence 135 of the video program, it can be seen that the unit representation engine 230 discards the basket 408/418/422 (since a basket also appears therein and thus does not uniquely represent the first example video sequence 400).
Part PAR_24: The image engine 235 uses the selected two units, namely, the basketball 406/416/424 and the hat 402/414/426, to generate the image 140 representative of the video sequence 400. For example, based on its configuration, the image engine 235 may superimpose the hat on top of the basketball, may place the hat over the basketball, etc. Further, the enhancements module 245 of the image engine 235 may generate and include descriptive artwork to illustrate the apparent movement of the units across the frames. An example resulting representative image 140 representing the first example video sequence 400 is shown in FIG. 6A.
Part PAR_25: FIG. 5 illustrates a second example video sequence 500 exemplifying a video sequence 135. Example video sequence 500 includes a first frame (Frame 101), a second frame (Frame 131) and a third frame (Frame 161). Frame 101 contains a moon 502, a star 504, a cloud 506 and a basket 508. Frame 131 contains a cloud 510, a partial moon 512 and a basket 514. Frame 161 contains a partial cloud 520, a moon 524, a star 526 and a basket 528. Using similar techniques as described with reference to FIG. 4, the unit predominance engine 225 determines that the predominance factors of the moon 502/512/524 is three, of the star 514/526 is two, of the cloud 506/510/520 is three, and of the basket 508/514/528 is three. The unit representation engine 230 discards the basket 508/514/528 and selects the moon and the cloud. The image engine 235 generates an image 140 using the cloud and the moon to represent the second example video sequence 500. The enhancements module 245 of the image engine 235 includes descriptive artwork in the representative image 140 to illustrate the disappearance of the cloud and the moon in some frames. An example representative image 140 representing the second example video sequence 500 is illustrated in FIG. 6B.
Part PAR_26: FIG. 7 is a flowchart illustrating a method 700 of generating an image 140 to represent a video sequence 135. Method 700 begins in step 705 with the sequence divider 205 dividing the video program into video sequences 135. Dividing a video into sequences can be performed using an index, noise identification, scene change analysis, etc. The frame selector 210 in step 710 selects an untested video sequence 135, and in step 715 selects an untested frame of the untested video sequence 135. Video sequence 135 and frame selection are preferably performed in a sequential manner. The unit extractor 215 uses techniques such as contour recognition, contrast, color and brightness analysis, etc. to locate units within each selected frame. It will be appreciated that the units extracted may differ based on the type of unit extractor 215 implemented. The frame selector 210 in step 725 determines whether all frames intended to be tested have been tested. For example, the frame selector 210 may be configured to select every thirtieth frame as an intended frame. If not, then method 700 returns to step 715 to select and extract units from the intended frames remaining in the selected video sequence 135.
Part PAR_27: After the frame selector 210 determines that all intended frames have been tested, the unit distinction engine 220 in step 730 distinguishes (i.e., extracts or resolves) the units between the frames in the selected video sequence 135. That is, the unit distinction engine 220 recognizes like units between frames. The unit predominance engine 225 in step 735 computes unit predominance, i.e., computes a predominance factor for each distinct unit. Computing a predominance factor may depend on the number of instances the unit appears in the sequence, the size of the unit in each frame, the brightness relative to other units in the frames, etc. The unit representation engine 230 in step 740 determines the units which best represent the sequence 135. For example, if a unit can be found in other video sequences 135, the unit may not be deemed sufficiently unique to identify the particular video sequence 135. In the preferred embodiment, the unit representation engine 230 selects the units having the highest predominance factor and from them locates the units that best represent the video sequence 135. Alternatively, the unit representation engine 230 in step 740 may prompt for user input to select the units that will represent the sequence.
Part PAR_28: The image engine 235 in step 745 uses the best representative units to generate a representative image 140. For example, the image engine 235 may superimpose the best representative units over one another. Alternatively, the image engine 235 may place them in order of appearance. Step 745 includes using an enhancements module 245 to add artwork to the representative image 140. The artwork may be representative of apparent movement of the units in the sequence or may be merely decorative. The frame selector 210 in step 750 then determines whether to test another video sequence 135, for example, by determining whether all video sequences 135 in the video program have been tested or by prompting a user for additional video sequence selection. If it is determined that another video sequence 135 should be tested, then method 700 returns to step 710 to select another untested video sequence 135. Otherwise, method 700 ends.
Part PAR_29: FIG. 8 is a flowchart illustrating a method 800 for editing and performing video sequences 135. Method 800 begins in step 805 with the representative image viewer 305 displaying the representative images 140. The sequence editor 310 in step 810 determines whether an edit request has been received. If not, then method 800 jumps to step 820. Otherwise, the sequence editor 310 in step 815 enables the editing of the video sequences 135, preferably, by enabling the user to re-order, delete, duplicate, etc. the representative images 140 which causes the corresponding re-ordering, deletion, duplication, etc. of the video sequences 135 in the video program. Similarly, the sequence editor 310 enables the user to re-order, delete, duplicate, etc. video sub-sequences 135 within each video sequence 135. After editing the video sequences 135, method 800 proceeds to step 820.
Part PAR_30: In step 820, the sequence selector 315 enables a user to request video performance. If a performance request is not received, then method 800 jumps to step 835 to determine whether the user is done. If so, then method 800 ends. Otherwise, method 800 returns to step 805. If in step 820 a performance request is received, then the sequence selector 315 in step 825 enables the selection of representative images 140, which indirectly enables the selection of video sequences 135 to perform. The video performer 320 in step 830 performs the selected video sequences 135. Method 800 then proceeds to step 835 to determine whether the user is done.
Part PAR_31: FIG. 9 is a block diagram illustrating an example memory 900 storing the units located in Frame 1 of FIG. 4. The unit extractor 215 stores a title 920 for each unit and corresponding attributes 925 in memory 900. For example, a first portion 905 of memory 900 stores a title ("Ball") for a first unit, and corresponding attributes 925 including color ("Orange"), size ("200 pixels") and location ("x1,y1"). A second portion 910 of memory 900 stores a title ("Player") for a second unit, and corresponding attributes 925 including a list of RGB color values ("&lt;RGB&gt;"), size ("600 pixels") and location ("x2,y2"). A third portion 915 of memory 900 stores a title ("Hat") for a third unit, and corresponding attributes 925 including color ("Black"), size ("150 pixels") and location ("x3,y3"). Other attributes such as shape, brightness, contrast, etc. (not shown) for each unit may also be listed in memory 900. Color, shape, size and location may also be stored in other ways.
Part PAR_32: The unit distinction engine 220 may use the attributes 925 to resolve other instances of-each unit in other frames. The unit predominance engine 225 may use the attributes 925 to compute the predominance factor for each unit. The image engine 235 may use the attributes 925 to generate the representative image 140.
Part PAR_33: The foregoing description of the preferred embodiments of the present invention is by way of example only, and other variations and modifications of the above-described embodiments and methods are possible in light of the foregoing teaching. Components of this invention may be implemented using a programmed general purpose digital computer, using application specific integrated circuits, or using a network of interconnected conventional components and circuits. The embodiments described herein are not intended to be exhaustive or limiting. The present invention is limited only by the following claims.


{'bibliographic_information': "{'Patent Number': '060524928', 'Series Code': '8', 'Application Number': '9873279', 'Application Type': '1', 'Art unit': '271', 'Application Filing Date': '19971209', 'Title of Invention': 'System and method for automatically generating an image to represent a video sequence', 'Issue Date': '20000418', 'Number of Claims': '14', 'Exemplary Claim Number(s)': '1', 'Assistant Examiner': 'Sherali; Ishrat', 'Primary Examiner': 'Boudreau; Leo H.', 'Number of Drawing Sheets': '9', 'Number of figures': '10'}", 'source_file': './grant/2000/pftaps20000418_wk16.txt', 'source_data': 'USPTO-Grant'}