Patent ID: 8117204

Claim:
A computer-based-method for enabling navigation of video using a keyframe-based video browser on a display device, comprising the steps of: determining a number of keyframes the display device is capable of displaying, wherein each keyframe is a frame of a point in time in the video; segmenting a video into video shots, wherein each video shot includes one or more keyframes; determining a number of video shots within the video; clustering the video shots according to visual similarity; placing the video shots in order according to temporal position with respect to other video shots in the same cluster; and producing a hierarchically organized navigation tree for the clusters of video shots, wherein producing the navigation tree includes minimizing the path lengths of the navigation tree by determining a height of the tree such that the number of keyframes the display device is capable of displaying raised to a power equal to the height of the tree is greater than or equal to the number of video shots, and determining a maximum number of video shots in each cluster, wherein the maximum number of video shots in each cluster is less than the number of keyframes the display device is capable of displaying raised to the power equal to the height of the tree divided by the number of keyframes the display device is capable of displaying.