Method, apparatus, and program for evolving algorithms for detecting content in information streams

• US 7,337,455 B2
• Filed: 12/31/2001
• Issued: 02/26/2008
• Est. Priority Date: 12/31/2001
• Status: Expired due to Fees

• Current Assignee: Pendragon Wireless LLC (Pendrell Corporation)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: McGee, Thomas, Jeannin, Sylvie, Agnihotri, Lalitha, Schaffer, J. David, Dimitrova, Nevenka
• Primary Examiner(s): Lonsberry, Hunter B.
• Application Number:
  US10/029,916
• Publication Number:
  US 20030126598A1
• Time in Patent Office: 2,248 Days
• Field of Search: 725/32, 725/36, 725/22, 725/17, 706/13
• US Class Current: 725/32
• CPC Class Codes: G06F 16/7834 using audio features
• CPC Class Codes: G06F 16/785 using colour or luminescence
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06V 10/70 using pattern recognition or machine learning optical pattern recognition or electronic computations therefor G06V10/88
• CPC Class Codes: G06V 20/41 Higher-level, semantic clustering, classification or understanding of video scenes, e.g. detection, labelling or Markovian modelling of sport events or news items segmenting video sequences G06V20/49
• CPC Class Codes: G11B 2220/20 Disc-shaped record carriers
• CPC Class Codes: G11B 27/28 by using information signals recorded by the same method as the main recording G11B27/22 takes precedence
• CPC Class Codes: H04N 21/4147 PVR [Personal Video Recorder] H04N5/76 takes precedence ; arrangements for broadcast with accumulation-type receivers H04H20/40
• CPC Class Codes: H04N 21/44008 involving operations for analysing video streams, e.g. detecting features or characteristics in the video stream arrangements characterised by components specially adapted for monitoring, identification or recognition of video in broadcast systems H04H60/59
• CPC Class Codes: H04N 21/812 involving advertisement data advertising per se G06Q30/02
• CPC Class Codes: H04N 5/76 Television signal recording

Abstract

A method for optimizing the performance of an algorithm for detecting predetermined content in a media information stream, and a program and apparatus that operate in accordance with the method. The algorithm is a function of a set of parameters. The method comprises the steps of performing the algorithm at least once to detect the predetermined content in the media information stream, while employing a respective set of parameters in the algorithm for each performance thereof, and automatically evolving at least one respective set of parameters employed in the algorithm to maximize the degree of accuracy at which the algorithm detects the predetermined content in the media information stream.

Claims

1. A method for detecting predetermined content in a media information stream, comprising:

receiving an algorithm for detecting predetermined content in the media information stream, the algorithm being a function of a set of parameters;

performing the algorithm at least once to detect the predetermined content in the media information stream, while employing a respective set of parameters in the algorithm for each performance thereof;

automatically evolving at least one respective set of parameters employed in the algorithm to maximize the degree of accuracy at which the algorithm detects the predetermined content in the media information stream;

repeating the performing and evolving step until the at least one respective set of parameters employed in the algorithm is optimized; and

implementing in a machine the algorithm with at least one respective set of the optimized parameters to detect predetermined content in the media information stream.

2. A method as set forth in claim 1, wherein the media information stream includes at least one of video and audio information, and the predetermined content includes desired or undesired content.

3. A method as set forth in claim 1, wherein the algorithm detects the predetermined content based on a detection of at least one predetermined feature derived from the media information stream.

4. A method as set forth in claim 1, wherein the step of automatically evolving includes performing a genetic algorithm to evolve the at least one respective set of parameters.

5. A method as set forth in claim 1, wherein the media information stream includes a video information stream divided into a plurality of frames, the predetermined content includes at least one commercial, and the algorithm includes the steps of:

detecting a plurality of black or unicolor frames in the video information stream;

identifying the presence of a beginning portion of a commercial based on the detection of at least one of the plurality of black or unicolor frames; and

identifying the presence of an ending portion of the commercial based on the detection of at least one other of the plurality of black or unicolor frames.

6. A method as set forth in claim 1, wherein the step of automatically evolving comprises the steps of:

determining the accuracy at which the algorithm detects the predetermined content in the media information stream for each performance of the algorithm;

selecting at least one of the respective sets of parameters, based on a result of the step of determining the accuracy; and

producing at least one offspring set of parameters based on the at least one set of parameters selected in the selecting step.

7. A method as set forth in claim 6, wherein the step of automatically evolving further comprises the steps of:

further performing the algorithm at least once to detect the presence of the predetermined content in the media information stream, while employing a respective offspring set of parameters, produced in the producing step, in the algorithm for each further performance thereof;

determining the accuracy at which the algorithm detects the predetermined content in the media information stream for each further performance of the algorithm; and

further selecting one or more of at least one respective set of parameters selected in the selecting step and at least one offspring set of parameters produced in the producing step, based on a result of that step of determining.

8. A method as set forth in claim 7, wherein the step of automatically evolving further comprises the steps of:

determining if there is a convergence of all sets of parameters remaining after the further selecting step; and

if there is a convergence, storing a record of at least one of those sets of parameters selected in the further selecting step.

9. A method as set forth in claim 6, wherein the step of producing comprises:

pairing randomly-selected ones of the sets of parameters selected in the selecting step;

determining if the sets of parameters paired in the pairing step are incestuous; and

for each paired sets of parameters determined to be non-incestuous, swapping one or more values of the parameters of those sets with one another.

10. A method as set forth in claim 9, wherein the step of determining if the sets of parameters paired in the pairing step are incestuous comprises:

determining a number of corresponding parameter values of each paired sets of parameters, which differ from one another, if any; and

determining if the number of corresponding parameter values determined to be differing from one another is less than a predetermined incest threshold.

11. A method as set forth in claim 7, wherein the step of automatically evolving further comprises the steps of:

determining if there is a convergence of all sets of parameters remaining after the further selecting step; and

if there is no convergence,

mutating at least one value of a most optimum one of all the sets of parameters remaining after the further selecting step, to produce plural mutated versions of the most optimum set of parameters; and

performing at least some steps of the method again, beginning with performing the algorithm, but plural times, to detect the presence of the predetermined content in the media information stream while employing the most optimum set of parameters and the mutated versions of the most optimum set of parameters, in respective performances of the algorithm.

12. A method as set forth in claim 11, wherein the step of mutating comprises:

producing plural copies of the most optimum set of parameters; and

changing at least one parameter value of each of the plural copies of the most optimum set of parameters.

13. A method as set forth in claim 8, wherein the step of producing comprises:

pairing randomly-selected ones of the sets of parameters selected in the selecting step;

determining if the sets of parameters paired in the pairing step are incestuous by;

determining a number of corresponding parameter values of each paired sets of parameters, which differ from one another, if any, and

determining if the number of corresponding parameter values determined to be differing from one another is less than a predetermined incest threshold; and

for each paired sets of parameters determined to be non-incestuous, swapping at least corresponding values of the parameters of those sets with one another,

wherein the step of determining if there is a convergence comprises at least one of;

determining if the predetermined incest threshold is equal to a predetermined value; and

determining if performances of the algorithm employing the sets of parameters remaining after the fUrther selecting step each result in detections of the predetermined content with substantially a same degree of accuracy.

14. A method as set forth in claim 13, and further comprising:

determining if any offspring sets of parameters remain after the further selecting step is performed; and

if no offspring set of parameters remains, decreasing the predetermined incest threshold by a predetermined reduction value.

15. A method as set forth in claim 8, wherein if there is a convergence of all of the sets of parameters remaining after the further selecting step, performing at least one of:

determining if the method has been performed a predetermined number of times; and

determining if a predetermined number of offspring sets of parameters has been produced, and

wherein if either of those determining steps results in an affirmative determination, performing the step of storing.

16. A method as set forth in claim 1, wherein the step of automatically evolving includes evolving the at least one respective set of parameters employed in the algorithm to generate an evolved set of parameters which is optimized to enable the algorithm to detect the predetermined content in the media information stream with a maximum degree of accuracy.

17. A method as set forth in claim 16, and further comprising the step of forwarding at least one of the algorithm and the evolved set of parameters to a predetermined destination.

18. A method for evaluating a media information stream, comprising the steps of:

performing one or more algorithms, each to detect the presence of predetermined content in the media information stream, wherein each algorithm is a function of a corresponding chromosome; and

automatically determining a value, for the chromosome of at least one of the algorithms, which enables that algorithm to detect the presence of the predetermined content in the media information stream with an increased degree of accuracy relative to the accuracy achieved when other values are employed.

19. An apparatus for evaluating a media information stream, comprising:

a memory for storing a media information stream and a program, at least a portion of the program including instructions for performing a method for optimizing the performance of an algorithm for detecting predetermined content in a media information stream, the algorithm being a function of a set of parameters; and

a controller coupled to said memory, said controller being operable under the control of the program stored in said memory for (a) performing the algorithm at least once to detect the predetermined content in the media information stream stored by said memory, while employing a respective set of parameters in the algorithm for each performance thereof, and (b) automatically evolving at least one respective set of parameters employed in the algorithm to maximize the degree of accuracy at which the algorithm detects the predetermined content in the media information stream.

20. An apparatus as set forth in claim 19, wherein the media information stream includes video information.

21. An apparatus as set forth in claim 19, wherein at least a portion of the program includes a genetic algorithm, and said controller operates under the control of the program to automatically evolve the at least one respective set of parameters by performing the genetic algorithm.

22. An apparatus as set forth in claim 19, wherein said controller operates under the control of the program to perform the automatically evolving by:

determining the accuracy at which the algorithm detects the predetermined content in the media information stream for each performance of the algorithm;

selecting at least one of the respective sets of parameters, based on a result of the determining; and

producing at least one offspring set of parameters based on the at least one set of parameters selected in the selecting.

23. An apparatus as set forth in claim 22, wherein said controller also operates under the control of the program to further perform the evolving by:

further performing the algorithm at least once to detect the presence of the predetermined content in the media information stream, while employing a respective offspring set of parameters, produced in the producing, in the algorithm for each further performance thereof;

determining the accuracy at which the algorithm detects the predetermined content in the media information stream for each further performance of the algorithm; and

further selecting one or more of at least one respective set of parameters selected in the selecting and at least one offspring set of parameters produced in the producing, based on a result of that determining.

24. An apparatus as set forth in claim 23, wherein said controller also operates under the control of the program to further perform the evolving by:

determining if there is a convergence of all sets of parameters remaining after the further selecting; and

if there is a convergence, storing a record of at least one of those sets of parameters selected in the further selecting.

25. An apparatus as set forth in claim 23, wherein said controller also operates under the control of the program to further perform the evolving by:

determining if there is a convergence of all sets of parameters remaining after the further selecting; and

if there is no convergence,

mutating a most optimum one of all the sets of parameters remaining after the further selecting, to produce plural mutated versions of the most optimum set of parameters; and

performing at least some steps of the method again, beginning with performing the algorithm, but plural times, to detect the presence of the predetermined content in the media information stream while employing the most optimum set of parameters and the mutated versions of the most optimum set of parameters, in respective performances of the algorithm.

26. An apparatus as set forth in claim 19, wherein said controller performs the evolving to generate an evolved set of parameters which is optimized to enable the algorithm to detect the predetermined content in the media information stream with a maximum degree of accuracy.

27. An apparatus as set forth in claim 26, and further comprising an interface coupled to said controller, wherein said controller is operable for forwarding at least one of the evolved set of parameters and information representing the algorithm through the interface towards at least one external destination coupled to that interface.

28. An apparatus as set forth in claim 27, wherein the apparatus includes a server, and the external destination includes an information appliance.

29. An apparatus for optimizing the performance of an algorithm for detecting predetermined content in a media information stream, the algorithm being a function of a set of parameters, the apparatus comprising:

means for performing the algorithm at least once to detect the predetermined content in the media information stream, while employing a respective set of parameters in the algorithm for each performance thereof; and

means for automatically evolving at least one respective set of parameters employed in the algorithm to maximize the degree of accuracy at which the algorithm detects the predetermined content in the media information stream.

30. A program product comprising computer readable-code which, when executed, performs a method for optimizing the performance of an algorithm for detecting predetermined content in a media information stream, the algorithm being a function of a set of parameters, the method comprising the steps of:

performing the algorithm at least once to detect the predetermined content in the media information stream, while employing a respective set of parameters in the algorithm for each performance thereof; and

automatically evolving at least one respective set of parameters employed in the algorithm to maximize the degree of accuracy at which the algorithm detects the predetermined content in the media information stream.

31. A storage medium storing a program having computer readable-code which, when executed, performs a method for optimizing the performance of an algorithm for detecting predetermined content in a media information stream, the algorithm being a function of a set of parameters, the method comprising the steps of:

performing the algorithm at least once to detect the predetermined content in the media information stream, while employing a respective set of parameters in the algorithm for each performance thereof; and

automatically evolving at least one respective set of parameters employed in the algorithm to maximize the degree of accuracy at which the algorithm detects the predetermined content in the media information stream.

32. A system for exchanging information, comprising:

at least one first information apparatus; and

at least one second information apparatus, comprising;

an interface, coupled to said first information apparatus through an external communication interface,

a memory storing at least a program, and

a controller coupled to said memory and said interface, said controller operating under the control of the program stored in said memory for performing a method comprising (a) performing an algorithm at least twice to detect predetermined content in a provided media information stream, while employing a respective set of parameters in the algorithm for each performance thereof, wherein the algorithm is a function of the set of parameters, (b) automatically evolving at least one respective set of parameters employed in the algorithm to determine an optimum set of parameters which maximizes the degree of accuracy at which the algorithm detects the predetermined content in the media information stream, and (c) forwarding information representing at least one of the algorithm and the optimum set of parameters to the at least one first information apparatus through the interface and the external communication interface.

33. A system as set forth in claim 32, wherein the first information apparatus is an information appliance, and the second information apparatus is a server.

34. A system as set forth in claim 32, wherein the first information apparatus is a server, and the second information apparatus is an information appliance.

35. A system as set forth in claim 32, wherein the first information apparatus comprises:

a further interface, coupled to said interface of said second information apparatus through the external communication interface; and

a further controller coupled to said further interface, said further controller being responsive to said further interface receiving the information from said second information apparatus for at least one of storing the information in an associated further memory and performing the algorithm, while employing the optimum set of parameters in the algorithm, to detect the predetermined content in a provided information stream.

36. A system as set forth in claim 35, wherein the first information apparatus is an information appliance, and the second information apparatus is a server.

37. A system as set forth in claim 32, wherein the first information apparatus is operable for providing the information stream to said controller through said interface and said external communication interface, and wherein said controller performs the method after receiving that provided information stream.

38. A system as set forth in claim 37, wherein the first information apparatus is an information appliance, and the second information apparatus is a server.

39. A system as set forth in claim 37, wherein the first information apparatus is a server, and the second information apparatus is an information appliance.