Patent ID: 7949050

Claim:
A method of identifying semantically similar shots in a video sequence, comprising the steps of:— a) identifying shots within the video sequence, each shot being a temporally consecutive sequence of video frames; b) calculating distance values between each shot and every other shot; and c) clustering shots into groups in dependence on the respective calculated distance values therebetween; wherein the calculating step comprises:— i) generating a codebook representation of each identified shot expressing at least a keyframe of each shot as a plurality of codes; ii) calculating the distance values between each shot and each other shot in dependence on the respective codebook representations thereof; and the clustering step comprises iteratively performing the steps of i) selecting a first shot or cluster of shots and a second shot or cluster of shots which have a low distance therebetween, (ii) clustering the selected shots or cluster of shots into a new cluster, (iii) for the new cluster, generating a new codebook representation using at least the keyframes of each of the first and second shots or clusters which form the new cluster, and calculating the distance values between the codebook(s) for the remaining shots or clusters and the new codebook for the new single cluster, (iv) generating an error value for the new single cluster based on the sum of distances between the new codebook and the codebooks previously determined for the first and second shots or clusters forming the new cluster, and (v) in dependence on the error value, invalidating the new cluster and retaining the selected shots or clusters of shots.