SYSTEM AND METHOD FOR PROCESSING DIGITAL MEDIA

• US 20090116695A1
• Filed: 12/03/2007
• Published: 05/07/2009
• Est. Priority Date: 11/07/2007
• Status: Active Grant

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Viewdle, Inc.
• Inventors: Milshteyn, Kostyantyn, Musatenko, Yuriy, Anchyshkin, Yegor, Matsello, Vyacheslav, Kovtun, Ivan, Schlezinger, Mykhailo, Kyyko, Volodymyr
• Granted Patent: US 8,064,641 B2
• Time in Patent Office: Days
• US Class Current: 382/106
• CPC Class Codes: G06F 16/58 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06V 20/40 in video content extracting overlay text G06V20/62; video retrieval G06F16/70; processing of video elementary streams in video servers H04N21/234; processing of video elementary streams in video clients H04N21/44
• CPC Class Codes: G06V 20/635 Overlay text, e.g. embedded captions in a TV program
• CPC Class Codes: G06V 40/16 Human faces, e.g. facial parts, sketches or expressions

Abstract

A method for processing digital media is described. In one example embodiment, the method may include detecting an unknown object in a video frame, receiving inputs representing probable identities of the unknown object in the video frame from various sources, and associating each input with the unknown object detected in the video frame. The received inputs may be processed, compared with reference data and, based on the comparison, probable identities of the object associated with the input derived. The method may further include retrieving a likelihood of the input to match the unknown object from historical data and producing weights corresponding to the inputs, fusing the inputs and the relative weight associated with each input, and identifying the unknown object based on a comparison of the weighted distances from the unknown identify to a reference identity. The relative weights are chosen from the historical data to maximize correct recognition rate based on the history of recognitions and manual verification results.

Claims

1. A method to identify an unknown object extracted from a video stream, the method comprising:

detecting the unknown object in a video frame, the video frame being one of a plurality of video frames from the video stream;

receiving a plurality of inputs, each input in the plurality of inputs being a probable identity of the unknown object in the video frame;

associating each input with the unknown object;

associating a relative weight with each input, the relative weight being a likelihood of an input to match the unknown object;

obtaining values of a distance from each probable identity associated with the unknown object to each reference object;

obtaining a joint distance between every unknown object and each reference object, the joint distance being a weighted transformation of distances from each probable identity associated with the unknown object to reference object;

comparing the joint distances or input modality distances from the unknown object to each reference object; and

identifying the unknown object based on the comparing.

2. The method of claim 1, wherein the receiving of the plurality of inputs includes receiving inputs associated with a distance to the reference object, the distance being an Euclidean or a non-Euclidean distance between vectors representing the reference object and the unknown object in an input modality.

3. The method of claim 1, wherein the identifying of the unknown object is based on the values of the joint or particular distance function being less than or equal to a threshold identification value associated with the reference object.

4. The method of claim 1, further comprising creating index data, the index data including one or more of the following:

an identifier associated with the unknown object, a time at which the unknown object appears in the video stream, a spatial position of the unknown object in one or more video frames of the video stream, and other metadata associated with the unknown object.

5. The method of claim 4, wherein the creating of the index data is to permit the index data to be searched for a name of a person in a video and to view the video beginning from a moment in which the person appeared on screen.

6. The method of claim 1, wherein the unknown object is a facial image of a person.

7. The method of claim 2, wherein the input modality associated with a facial image detected in the video frame is selected from a group consisting of an Electronic Program Guide (EPG), a television channel identifier, sub-titles accompanying the video stream, optical character recognition data (OCR), human voices detected in an accompanying audio, textual data derived from the accompanying audio, a transcript of the video stream, and the facial image.

8. The method of claim 1, wherein the unknown object is a facial image of a person, and a weight of the distance to the reference facial image is derived from a likelihood of the person to appear in a given category of the video, and each input weight is based on a determination of a likelihood of each input to correctly suggest an identity of the person, the likelihood being based on historical data representing an identification of persons in a corresponding category of videos.

9. The method of claim 1, further comprising providing the input based on a corresponding analysis of the video frame, an accompanying audio, an EPG, and subtitles.

10. The method of claim 1, wherein the identifying of the unknown object is based on categories of the video stream, the categories selected from a group consisting of same television (TV) set, same TV channel, same news channel, same web broadcast, same category of entertainment, social life, sports, politics, fashion, show business, finance, stock market;

the categories of the video stream being derived from a group consisting of EPG, a video transcript, and previously learned information.

11. The method of claim 10, further comprising receiving statistics from previously recognized videos and manually verifying and correcting incorrect indexes.

12. The method of claim 9, further comprising;

extracting a text block from a frame of the video stream;

performing OCR on the text block to extract a text from the text block;

identifying probable names of people or objects from the text;

associating every unknown object in video frames with probable names;

comparing distances between the probable names and reference names, each distance being an edit distance between two names; and

suggesting a name of the unknown object based on the comparing.

13. The method of claim 9, further comprising:

analysing data provided by an EPG identifying the video stream to obtain probable names of people;

associating every unknown object in video frames with probable names and corresponding distances to every reference person name;

associating every unknown object in the video frames with probable names;

comparing distances between the probable names and reference names, each distance being an edit distance between two names; and

suggesting a name of the unknown object based on the comparing.

14. The method of claim 1, wherein obtaining the joint distance includes the following:

(C_w) D_w=sqrt(1/b_wC_w+a_w/b_w) C_w being computed as C_w=(w₁C₁)+(w₂C₂)+ . . . (w_nC_n), wherein w_i are weights and C_i are confidences associated with i—

the input and the confidences C_i are computed from an input distance D_i as C_i=1/(a_i+b_i·

D_i²), where a_i and b_i are constants chosen based on historical data and where weights w_i are assigned to the inputs based on historical data to maximize a correct recognition rate, and D_i is a distance between vectors for the unknown object and a reference object, or a distance from the unknown object'"'"'s inputs probable identity to the reference object, or D_i is an edit distance.

15. The method of claim 14, wherein the unknown object is a facial image and Dw defines a joint distance to the facial image in a reference database, the facial image being assumed to be correctly identified when Dw is less than a threshold associated with the facial image.

16. A system to identify an unknown object extracted from a video stream, the system comprising:

a buffered frame sequence processor to process a plurality of video frames comprising the video stream;

a facial context extraction processor to detect and extract the unknown object in a video frame, the video frame being one of the plurality of video frames comprising the video stream;

a receiving module to receive a plurality of inputs, each input being a predicted identity of the unknown object in the video frame;

an associating module to associate each input with the unknown object detected in the video frame and to associate a relative weight with each input, the relative weight being a likelihood of an input to correctly identify the unknown object;

a computing module to obtain values of a distance function from the unknown object in the video frame and each reference object selected from a set of known objects based on the plurality of the inputs and the relative weight associated with each input;

a comparing module to compare the values of the distance function for the unknown object and each reference object; and

an identification module to identify the unknown object based on the comparing.

17. The system of claim 16, wherein the receiving module is to receive the plurality of inputs associated with a distance to the reference object, the distance comprising non-Euclidean distance between vectors representing the reference object and the unknown object in an input modality.

18. The system of claim 16, wherein the identification module is to identify the unknown object based on the value of the distance function being less than or equal to a threshold identification value associated with the reference object.

19. The system of claim 16, further comprising an indexing module to create indexed data, the indexed data including one or more of the following:

an identifier of the unknown object, a time at which the unknown object appears in the video stream, and a spatial position of the unknown object in one or more video frames of the video stream.

20. The system of claim 19, wherein the indexing module is to create the indexed data being used in searching for person names in videos and to enable a user to view a video exactly from a moment in which a person appeared on screen.

21. The system of claim 16, wherein the identification module is influenced by categories of the video stream, the categories comprising same television (TV) set, same TV channel, same news channel, same web broadcast, same category of entertainment, social life, sports, politics, fashion, show business, finance, and stock market, the categories of the video stream derived from Electronic Program Guide (EPG), a video transcript or learned previously.

22. The system of claim 21, wherein the categories of the video stream are previously learned by gathering statistics from recognized videos and from manual verification and correction of incorrect indexes.

23. The system of claim 22, further comprising;

an optical character recognition (OCR) content extraction processor to extract a text block from a frame of the video stream;

a text-based context creation processor to perform OCR on the text block to extract text from the text block; and

a names extraction processor to identify probable names of people in the text, associate every unknown object in the video frames with probable names, compare distances between the probable names and reference names, each distance being an edit distance between two names, and to suggest a name of the unknown object based on the comparing.

24. A method to identify an unknown object extracted from a video stream, the method comprising;

means of detecting the unknown object in a video frame, the video frame being one of a plurality of video frames from the video stream;

means of receiving a plurality of inputs, each input in the plurality of the inputs being a probable identity of the unknown object in the video frame;

means of associating each input with the unknown object;

means associating a relative weight with each input, the relative weight being a likelihood of an input to match the unknown object;

means of obtaining values of a distance from each probable identity associated with the unknown object to each reference object;

means of obtaining a joint distance between every unknown object and each reference object, the joint distance being a weighted transformation of distances from each probable identity associated with the unknown object to reference object;

means of comparing the joint distances or input modality distances from the unknown object to each reference object; and

means of identifying the unknown object based on the comparing.

25. A machine-readable medium comprising instructions, which when implemented by one or more processors perform the following operations:

detect the unknown object in a video frame, the video frame being one of a plurality of video frames from the video stream;

receive a plurality of inputs, each input in the plurality of the inputs being a probable identity of the unknown object in the video frame;

associate each input with the unknown object;

associate a relative weight with each input, the relative weight being a likelihood of an input to match the unknown object;

obtain values of a distance from each probable identity associated with the unknown object to each reference object;

obtain a joint distance between every unknown object and each reference object, the joint distance being a weighted transformation of distances from each probable identity associated with the unknown object to reference object;

compare the joint distances or input modality distances from the unknown object to each reference object; and

identify the unknown object based on the comparing.