M.Sc Thesis

M.Sc StudentShemer Yair
SubjectUnsupervised Video Summarization using Heuristic
Optimization Algorithms
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Nahum Shimkin
Full Thesis textFull thesis text - English Version


In recent years, there has been an increasing interest in building video summarization tools, where the goal is to automatically create a short summary of an input video that properly represents the original content. We consider shot-based video summarization where the summary consists of a subset of the video shots which can be of various lengths. A straightforward approach to maximize the representativeness of a subset of shots is by minimizing the total distance between shots and their nearest selected shots. We formulate the task of video summarization as an optimization problem with a knapsack-like constraint on the total summary duration. Previous studies have proposed greedy algorithms to solve this problem approximately, but no experiments were presented to measure the ability of these methods to obtain solutions with low total distance. Indeed, our experiments on video summarization datasets show that the success of current methods in obtaining results with low total distance still has much room for improvement. In this thesis, we develop ILS-SUMM, a novel video summarization algorithm to solve the subset selection problem under the knapsack constraint.  Our algorithm is based on the well-known metaheuristic optimization framework - Iterated Local Search (ILS), known for its ability to avoid weak local minima and obtain a good near-global minimum. In addition, we exploit the connection between the Knapsack Median (KM) problem and the well studied k medoids problem to develop algorithms for the KM problem based on the Partitions Around Medoids (PAM) algorithm. Extensive experiments show that ILS-SUMM finds solutions with significantly better total distance than previous algorithms. Moreover, to indicate the high scalability of ILS-SUMM, we introduce a new dataset consisting of videos of various lengths.