A measure of importance is calculated for segmented parts of a video. The segmented parts are determined by segmenting the video into component shots and then merging by iteration the component shots based on similarity or other factors. Segmentation may also be determined by clustering frames of the video, and creating segments from the same cluster ID. The measure of importance is calculated based on a normalized weight of each segment and on length and rarity of each shot/segmented part. The importance measure may be utilized to generate a video summary by selecting the most important segments and generating representative frames for the selected segments. A thresholding process is applied to the importance score to provide a predetermined number or an appropriate number generated on the fly of shots or segments to be represented by frames. The representative frames are then packed into the video summary. The sizes of the frames to be packed are predetermined by their importance measure and adjusted according to space availability. Packing based on a grid and an exhaustive search of frame combinations to fill each row in the grid. A cost algorithm and a space-filling rule are utilized to determine the best fit of frames. The video summary may be presented on either a paper interface referencing or a web page linking the frames of the summary to points of the video.