Combining independent solutions to an image or video processing task

• US 9,965,703 B2
• Filed: 06/08/2016
• Issued: 05/08/2018
• Est. Priority Date: 06/08/2016
• Status: Active Grant

• Current Assignee: GoPro, Inc.
• Original Assignee: GoPro, Inc.
• Inventors: Adsumilli, Balineedu Chowdary, Lustig, Ryan
• Primary Examiner(s): Niu, Feng
• Application Number:
  US15/177,310
• Publication Number:
  US 20170357880A1
• Time in Patent Office: 699 Days
• Field of Search: None
• CPC Class Codes: G06F 18/2111 by using evolutionary computational techniques, e.g. genetic algorithms
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 18/217 Validation; Performance evaluation; Active pattern learning techniques
• CPC Class Codes: G06F 18/285 Selection of pattern recognition techniques, e.g. of classifiers in a multi-classifier system
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06V 10/771 Feature selection, e.g. selecting representative features from a multi-dimensional feature space
• CPC Class Codes: G06V 10/776 Validation; Performance evaluation
• CPC Class Codes: G06V 10/87 using selection of the recognition techniques, e.g. of a classifier in a multiple classifier system
• CPC Class Codes: G06V 20/46 Extracting features or characteristics from the video content, e.g. video fingerprints, representative shots or key frames
• CPC Class Codes: G06V 40/161 Detection; Localisation; Normalisation

Abstract

An algorithm for performing an image or video processing task is generated that may be used to combine a plurality of different independent solutions to the image or video processing task in an optimized manner. A plurality of base algorithms may be applied to a training set of images or video and a first generation of different combining algorithms may be applied to combine the respective solutions from each of the respective base algorithms into respective combined solutions. The respective combined solutions may be evaluated to generate respective fitness scores representing measures of how well the plurality of different combining algorithms each perform the image or video processing task. The algorithms may be iteratively updated to generate an optimized combining algorithm that may be applied to an input image or video.

Claims

1. A method for generating an algorithm for performing an image or video processing task, the method comprising:

receiving a training set of input images or videos;

applying a plurality of base algorithms to the training set, each of the base algorithms independently generating respective base algorithm results as respective solutions to the image or video processing task;

applying a first generation of different combining algorithms, where the applying of the first generation of different combining algorithms comprises combining the respective solutions from each of the respective base algorithms into respective combined solutions, where the applying of the first generation of different combining algorithms further comprises;

applying a first subset of a predefined plurality of operations to at least a subset of the respective base algorithms to generate first tier results; and

applying a second subset of the predefined plurality of operations to the first tier results of the respective base algorithms results to generate second tier results;

evaluating the respective combined solutions from the first generation of different combining algorithms to generate respective fitness scores representing measures of how well the plurality of different combining algorithms each perform the image or video processing task;

updating the first generation of different combining algorithms based on the respective fitness scores to generate a second generation of different combining algorithms; and

selecting, by a processor, an optimized combining algorithm from the second generation of different combining algorithms that best meets a predefined optimization criterion associated with the image or video processing task;

wherein the image or video processing task comprises a background segmentation task, wherein each of the plurality of base algorithms comprises different background segmentation algorithms, and wherein each of the respective base algorithm results comprises respective binary masks generated from a different one of the different background segmentation algorithms.

2. The method of claim 1, wherein the updating of the first generation of different combining algorithms comprises:

selecting a parent algorithm from the first generation of different combining algorithms based on the respective fitness scores; and

duplicating the parent algorithm to generate an elite child algorithm from the parent algorithm as one of the second generation of different combining algorithms.

3. The method of claim 1, wherein the updating of the first generation of different combining algorithms comprises:

selecting a parent algorithm from the first generation of different combining algorithms based on the respective fitness scores; and

changing one or more operators, inputs, or structures of the parent algorithm to generate a mutation child algorithm as one of the second generation of different combining algorithms.

4. The method of claim 3, wherein the changing of the one or more operators, inputs, or structures of the parent algorithm comprises randomly changing the one or more operators, inputs, or structures of the parent algorithm.

5. The method of claim 1, wherein the updating of the first generation of different combining algorithms comprises:

selecting a first parent algorithm from the first generation of different combining algorithms based on the respective fitness scores; and

selecting a second parent algorithm from the first generation of different combining algorithms based on the respective fitness scores; and

combining a first portion of the first parent algorithm with a second portion of the second parent algorithm to generate a crossover child algorithm as one of the second generation of different combining algorithms.

6. The method of claim 1, wherein the plurality of base algorithms comprises at least one of:

a Gaussian Mixture Models (GMMs) algorithm, a K-Nearest Neighbors (K-NN) algorithm, and a Self-Balanced Sensitivity Segmenter (SuB SENSE) algorithm.

7. The method of claim 1, wherein the predefined plurality of operations comprises at least one of:

a 5×

5 median filter, a morphological image dilation with a 5×

5 square kernel, a morphological image erosion with a 5×

5 square kernel, a logical AND operation between two inputs, a logical OR operation between two images, and a majority vote with two or more inputs.

8. The method of claim 1, wherein the image or video processing task comprises an automatic highlight detection task, wherein each of the plurality of base algorithms comprises different automatic highlight detection algorithms, and wherein each of the respective base algorithm results comprises a set of parameters indicating a time in a video at which a highlight occurred and a duration of the highlight.

9. The method of claim 8, wherein the plurality of base algorithms comprises at least one of:

a motion detection algorithm, a scene change detection algorithm, a face detection algorithm, and an audio highlight detection algorithm.

10. The method of claim 8, wherein the predefined plurality of operations comprises at least one of:

a majority vote for highlights occurring within a same time duration, a logical AND operation of the duration of the highlight, and a logical OR operation of the duration of the highlight (“

OR”

).

11. The method of claim 1, further comprising:

determining whether a stopping criterion is met by the generated second generation of different combining algorithms;

when the stopping criterion is met, selecting the optimized combining algorithm from the second generation of different combining algorithms; and

otherwise

when the stopping criterion is not met, evaluating the second generation of different combining algorithms to generate respective fitness scores.

12. A non-transitory computer-readable storage apparatus comprising a storage medium storing instructions for generating an algorithm for performing an image or video processing task, the instructions, when executed by a processor apparatus, being configured to cause the processor apparatus to perform steps including:

receiving a training set of input images or videos;

applying a plurality of base algorithms to the training set, each of the base algorithms independently generating respective base algorithm results as respective solutions to the image or video processing task;

applying a first generation of different combining algorithms, each of the first generation of different combining algorithms being configured to combine the respective solutions from each of the respective base algorithm results into respective combined solutions;

evaluating the respective combined solutions from the first generation of different combining algorithms to generate respective fitness scores representing measures of how well the plurality of different combining algorithms each perform the image or video processing task;

updating the first generation of different combining algorithms based on the respective fitness scores to generate a second generation of different combining algorithms; and

selecting an optimized combining algorithm from the second generation of different combining algorithms that best meets a predefined optimization criterion associated with the image or video processing task;

wherein the applying of the first generation of different combining algorithms comprises;

applying a first subset of a predefined plurality of operations to at least a subset of the respective base algorithm results to generate first tier results; and

applying a second subset of the predefined plurality of operations to the first tier results or the respective base algorithm results to generate second tier results; and

wherein the image or video processing task comprises a background segmentation task, wherein each of the plurality of base algorithms comprises different background segmentation algorithms, and wherein each of the respective base algorithm results comprises respective binary masks generated from a different one of the different background segmentation algorithms.

13. The non-transitory computer-readable storage apparatus of claim 12, wherein the updating of the first generation of different combining algorithms comprises:

selecting a parent algorithm from the first generation of different combining algorithms based on the respective fitness scores; and

duplicating the parent algorithm to generate an elite child algorithm from the parent algorithm as one of the second generation of different combining algorithms.

14. The non-transitory computer-readable storage apparatus of claim 12, wherein the updating of the first generation of different combining algorithms comprises:

selecting a parent algorithm from the first generation of different combining algorithms based on the respective fitness scores; and

changing one or more operators, inputs, or structures of the parent algorithm to generate a mutation child algorithm as one of the second generation of different combining algorithms.

15. The non-transitory computer-readable storage apparatus of claim 12, wherein the changing of the one or more operators, inputs, or structures of the parent algorithm comprises a randomly change thereof.

16. The non-transitory computer-readable storage apparatus of claim 12, wherein the updating of the first generation of different combining algorithms comprises:

selecting a first parent algorithm from the first generation of different combining algorithms based on the respective fitness scores; and

selecting a second parent algorithm from the first generation of different combining algorithms based on the respective fitness scores; and

combining a first portion of the first parent algorithm with a second portion of the second parent algorithm to generate a crossover child algorithm as one of the second generation of different combining algorithms.

17. The non-transitory computer-readable storage apparatus of claim 12, wherein the plurality of base algorithms comprises at least one of:

a Gaussian Mixture Models (GMMs) algorithm, a K-Nearest Neighbors (K-NN) algorithm, and a Self-Balanced Sensitivity Segmenter (SuBSENSE) algorithm.

18. The non-transitory computer-readable storage apparatus of claim 12, wherein the predefined plurality of operations comprises at least one of:

a 5×

5 median filter, a morphological image dilation with a 5×

5 square kernel, a morphological image erosion with a 5×

5 square kernel, a logical AND operation between two inputs, a logical OR operation between two images, and a majority vote with two or more inputs.

19. The non-transitory computer-readable storage apparatus of claim 12, wherein the image or video processing task comprises an automatic highlight detection task, wherein each of the plurality of base algorithms comprises different automatic highlight detection algorithms, and wherein each of the respective base algorithm results comprises a set of parameters indicating a time in a video at which a highlight occurred and a duration of the highlight.

20. The non-transitory computer-readable storage apparatus of claim 19, wherein the plurality of base algorithms comprises at least one of:

a motion detection algorithm, a scene change detection algorithm, a face detection algorithm, and an audio highlight detection algorithm.

21. The non-transitory computer-readable storage apparatus of claim 19, wherein the predefined plurality of operations comprises at least one of:

a majority vote for highlights occurring within a same time duration, a logical AND operation of the duration of the highlight, and a logical OR operation of the duration of the highlight (“

OR”

).

22. The non-transitory computer-readable storage apparatus of claim 12, wherein the instructions, when executed by the processor apparatus, are further configured to cause the processor apparatus to perform steps including:

determining whether a stopping criterion is met by the generated second generation of different combining algorithms;

when the stopping criterion is met, selecting the optimized combining algorithm from the second generation of different combining algorithms; and

otherwise

when the stopping criterion is not met, evaluating the second generation of different combining algorithms to generate respective fitness scores.