Combining Independent Solutions to an Image or Video Processing Task

• US 20170357880A1
• Filed: 06/08/2016
• Published: 12/14/2017
• Est. Priority Date: 06/08/2016
• Status: Active Grant

• Current Assignee: GoPro, Inc.
• Original Assignee: GoPro, Inc.
• Inventors: Adsumilli, Balineedu Chowdary, Lustig, Ryan
• Granted Patent: US 9,965,703 B2
• Time in Patent Office: Days
• 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, each of the first generation of different combining algorithms to combine the respective solutions from each of the respective base algorithms 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, 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.

2. The method of claim 1, wherein updating 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 updating 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 1, wherein updating 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.

5. The method of claim 1, wherein applying the combining algorithm comprises:

applying a first subset of a predefined plurality of operations to at least a subset of the respective base algorithm 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.

6. The method of claim 5, 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.

7. The method of claim 6, 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.

8. The method of claim 6, 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.

9. The method of claim 5, 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 the video at which a highlight occurred and a duration of the highlight.

10. The method of claim 9, 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.

11. The method of claim 9, 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”

).

12. A non-transitory computer-readable storage medium storing instructions for generating an algorithm for performing an image or video processing task, the instructions when executed by a processor causing the processor 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 to combine the respective solutions from each of the respective base algorithms 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.

13. The non-transitory computer-readable storage medium of claim 12, wherein updating 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 medium of claim 12, wherein updating 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 medium of claim 12, wherein updating 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.

16. The non-transitory computer-readable storage medium of claim 12, wherein applying the combining algorithm comprises:

applying a first subset of a predefined plurality of operations to at least a subset of the respective base algorithm 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.

17. The non-transitory computer-readable storage medium of claim 16, 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.

18. The non-transitory computer-readable storage medium of claim 17, 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.

19. The non-transitory computer-readable storage medium of claim 17, 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.

20. The non-transitory computer-readable storage medium of claim 16, 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 the video at which a highlight occurred and a duration of the highlight.

21. The non-transitory computer-readable storage medium of claim 20, 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.

22. The non-transitory computer-readable storage medium of claim 20, 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”

).