Patent ID: 8676033

Claim:
A method for extracting key frames from a video, comprising: dividing the video into multiple levels of video segments, wherein each video segment at a non-lowest level comprises one or more video segments at the next lower level, and the multiple levels range from a first level to an N-th level, where N is an integer greater than 1, the first level is the lowest level, and the N-th level is the highest level; extracting, from the video segments of the video at a non-highest level, candidate frames at the non-highest level; for each level from a next higher level of the non-highest level to the highest level, selecting zero, one or more candidate frames at the level from the candidate frames at the next lower level comprised in each video segment at the level; removing approximately repetitive frames of the candidate frames at the highest level; and after removing the approximately repetitive frames, outputting the candidate frames at the highest level as the key frames of the video, wherein for at least one M-th level ranging from the next higher level of the non-highest level to the highest level, M being an integer greater than 1, the selecting the candidate frames at the M-th level from the candidate frames at a (M−1)-th level comprised in each video segment at the M-th level comprises: for each video segment at the M-th level, ranking the candidate frames at the (M−1)-th level comprised in the video segment in order of large to small numbers of the frames represented by the candidate frames at the (M−1)-th level; and repeating the following steps for selection until a predetermined number of candidate frames at the M-th level are selected using processing circuitry: for each video segment at the M-th level, choosing a candidate frame which has not been selected as a candidate frame at the M-th level and is the highest ranked in the candidate frames at the (M−1)-th level in the video segment to participate in the selection; calculating a number of votes for each participated candidate frame according to a number of frames represented by each participated candidate frame and a number of votes supported by other candidate frames, which have not been determined as candidate frames at the M-th level, in the video segment at the M-th level where the participated candidate frame locates, wherein a sum of the number of votes for each participated candidate frame and the total number of frames represented by determined candidate frames at the M-th level in the video segment at the M-th level where the participated candidate frame locates is not greater than the total number of the frames of the video segment at the M-th level where the participated candidate frame locates; and selecting the participated candidate frame with the largest number of votes as a candidate frame of the video segments at the M-th level.