Title: ILS-SUMM: ITERATED LOCAL SEARCH FOR UNSU-PERVISED VIDEO SUMMARIZATION

Abstract: 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 paper, 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. Extensive experiments show that our method finds solutions with significantly better total distance than previous methods. Moreover, to indicate the high scalability of ILS-SUMM, we introduce a new dataset consisting of videos of various lengths.

1. INTRODUCTION:

In recent years, the amount of video data has significantly increased. In addition to many cinema movies, news videos, and TV-shows, people frequently shoot events with their cellphone and share it with others on social media. To illustrate, it has been reported that every minute, 300 hours of new videos are uploaded to YouTube. Consequently, the user's ability to manage, search, and retrieve a specific item of content is limited. One remedy to this challenge can be an automatic video summarization algorithm where the goal is to create a shortened video that contains the essence of the original video. If fact, several commercial video summarization products are already on the market.

Various video summarization algorithms have been suggested in the literature. In most methods, the process consists of two main stages -segmenting the video into short video shots, and then choosing a subset of the shots to aggregate a summary (Otani et al., 2019) . In order to be a good summary, this shot subset selection should optimize a certain property. For example, the selected shots should well represent the content of the video in the sense that each object from the original video has a similar object in the summary.

Video summarization approaches can generally be divided into supervised and unsupervised. Supervised methods include exploiting a ground truth importance score of each frame to train a model (Zhang et al., 2016; Zhao et al., 2018; Gygli et al., 2015) and utilizing auxiliary data such as web images (Khosla et al., 2013) , titles (Song et al., 2015) , category (Potapov et al., 2014) and any other side information (Yuan et al., 2017) . A pitfall of a supervised approach is the necessity of expensive human-made labels. This drawback is especially restrictive because of the complicated and vague structure of a good summary, which requires a lot of labeled data.

In contrast, unsupervised methods do not need human-made labels as they follow rational guidelines for creating a good summary. One group of unsupervised algorithms maximizes the similarity between the original video and the generated summary using generative adversarial networks as evaluators (Mahasseni et al., 2017; Jung et al., 2019; Yuan et al., 2019) , or by dictionary learning (Cong et al., 2011; Zhao & Xing, 2014) . Another salient group of methods seek to minimize the total distance between shots and their nearest selected shots while satisfying the limit on the summary duration. Attempts in this direction include using submodular optimization (Gygli et al., 2015) , reinforcement learning (Zhou et al., 2018) and clustering methods (Chheng, 2007; De Avila et al., 2011; Hadi et al., 2006) .

Even though several methods have been proposed for minimizing this total distance, no experiments have presented to directly measure the success of these methods in obtaining solutions with low total distance. Our experiments indicate that the best current existing method obtains solutions with total distance, which is, in some datasets around 10% worse than the optimal solution on average. Hence, we see that there is room for a new method that leads to better solutions.

In this paper, we propose ILS-SUMM, a novel unsupervised video summarization algorithm which uses the Iterated Local Search (ILS) optimization framework (Lourenc ¸o et al., 2003) to find a representative subset of shots. We formalize the following optimization problem: given the entire set of shots with varied shot duration, select a subset which minimizes the total distance between shots and their nearest selected shots while satisfying a knapsack constraint, i.e., the limit on the summary duration. This problem is known in the Operations Research field as the Knapsack Median (KM) problem, and is known to be NP-hard. A major challenge in performing a local search in the solution domain is the high chance of getting stuck in a local minimum because of the hard knapsack constraint (Fang et al., 2002) . Therefore we use the ILS framework, which is the basis for several state-of-the-art algorithms for NP-hard problems (Lourenc ¸o et al., 2019) .

ILS-SUMM creates a video summary by selecting shots that well represent the original video, using the ILS framework. First, it initializes a solution that satisfies the summary duration limit. Then, it applies steps of improvements by adding or replacing one shot at a time, while allowing only steps that obey the knapsack constraint. When a local minimum point is reached, the ILS executes a gentle, yet noticeable, perturbation to the current solution, to get out from the local minimum while trying to keep part of the high quality of the solution it obtained. We perform extensive experiments on the SumMe and TvSum benchmarks showing that our method finds solutions that are on average less than 2% worse than the optimal solution, which is significantly superior than the results of previous methods. Moreover, experiments on long real open-source movies indicate ILS-SUMM scalability. A Python implementation of the proposed method is released in [www.github.com/ArthurName/ILS-SUMM].

2. RELATED WORK:



2.1. VIDEO SUMMARIZATION:

Various unsupervised video summarization methods have been presented in the recent literature. Most methods share the underlying assumption that a good summary should represent and be similar to the original video. Cong et al. (2011) and Zhao & Xing (2014) build a representative dictionary of key frames that minimizes the reconstruction error of the original video. Mahasseni et al. (2017) train a deep neural network to minimize the distance between original videos and a distribution of their summarizations. Chheng (2007) cluster the video shots into k clusters using the k means algorithm, and then select shots from various clusters. Gygli et al. (2015) apply submodularity optimization to minimize the total distance between shots and the nearest of the selected shots. Zhou et al. (2018) use a reinforcement learning framework to train a neural network to select frames such that the representativeness and diversity of the summary will be maximized.

In recent years, most methods evaluate their results by measuring the similarity between automatic summaries and human-made summaries. Recently, Otani et al. (2019) observed that randomly generated summaries obtain competitive or better performance in this metric to the state-of-the-art. Based on this surprising observation, instead of evaluating our method using human labels, we mea-sure the success of our algorithm in terms of having low total distance between all shots and the nearest of the selected shots.

2.2. ITERATED LOCAL SEARCH:

In the ILS framework, a sequence of locally optimal solutions is iteratively generated by a heuristic algorithm. The initial point of the heuristic search in each iteration is a perturbation of a previous obtained solution, rather than a complete random trail. ILS has been applied successfully to various optimization problems, leading to high performance and even established the current state-of-the-art algorithms in some tasks. Some successful applications of ILS include solving common combinatorial problems such as graph partitioning problems, traveling salesperson problems and scheduling problems (De Corte & Sörensen, 2016) , in addition to other applications such as image registration (Cordón & Damas, 2006) , car sequencing (Cordeau et al., 2008; Ribeiro et al., 2008) and the generalized quadratic multiple knapsack problem (Avci & Topaloglu, 2017) . To the best of our knowledge, this paper is the first to apply Iterated Local Search to the Knapsack Median problem.

3. METHOD:

In this section, we introduce an unsupervised method for video summarization, based on the Iterated Local Search (ILS) optimization framework.

3.1. FORMULATION:

Given an input video v, the video is divided temporally into a set of shots

S v = {s 1 , s 2 , . . . s N },

where N is the number of shots in the video. We denote the duration in seconds of a shot s as t (s). Each shot is represented by its middle frame feature vector x (s) (for details see section 4.1). A condensed video summary is a representative subset of shots S summ ⊆ S v . The summarization task is then formulated by the following optimization problem. We denote T D(S summ |S v , x(s)) as the total distance between all video shots and their nearest shot in S summ :

T D(S summ |S v , x(s)) = s ∈Sv min s∈Ssumm {dist (x (s ) , x (s))} (1)

The objective is to obtain the subset S summ that minimizes the total distance:

EQUATION

subject to:

EQUATION

where dist (x, y) denotes some distance metric between x and y, and T is the maximum total duration in seconds allowed for the video summary. Equation 2 expresses the goal that the subset will minimize the total distance between shots and their nearest selected shots. Equation 3 encodes the knapsack constraint which limits the total duration of the selected shots not to exceed T seconds. S := Select(N(S * , S v , t(s), T ), x(s))

5: if f(S|S v , x(s)) < f(S * |S v , x(s)) then 6:

S * := S 7:

end if 8: end for 9: return: end if 15: end while 16: return: S Best Algorithm 1. This algorithm contains the following functions: f() -an objective function, N() -a map between a solution S to a neighborhood of solutions, and Select() -a function that selects one of the neighbors, all detailed below. As an input, Local-Search-SUM gets S init -an initialization of a solution. In each iteration of the algorithm, it selects a neighbor of the current solution and moves to this neighbor if it decreases the objective function. The loop continues until a local minimum is reached or until MAX TRIALS, i.e., the predefined maximum number of trials, is reached. To solve the KM problem with a local search algorithm, we use the setting as described below.

S * Algorithm 2 ILS-SUMM 1: Input: S init , S v , x(s), t(s), T 2: S * := Local-Search-SUMM(S init , S v , x(s), t(s), T ) 3: S Best := S * 4: M := 1 5: while M ≤ M MAX do 6: S := Perturbation(S * , S v , M, t(s), T ) 7: S * := Local-Search-SUMM(S , S v , x(s), t(s), T ) 8: S * := Acceptance-Criterion(S Best, S * , S * , S v , x(s)) 9: if f(S * |S v , x(s)) < f(S Best |S v , x(s)) then

Objective function. Straightforwardly, we define the objective function as the total distance between shots and their nearest selected shots:

EQUATION

Note that an extension to a multi-objective function is straightforward, by changing f () to be a weighted sum of objectives as proposed by Gygli et al. (2015) .

Initialization. To deal with the knapsack constraint, we define the local search initialization and neighborhood such that throughout all the solution process, only feasible solutions will be considered. To ensure that the initialized solution S init satisfies the knapsack constraint, the initialization subset is set to be the single shortest shot.

Neighborhood. A neighborhood N(S summ , S v , t(s), T ) includes any subset which is obtained by swapping or adding a single shot to S summ , while satisfying the knapsack constraint. Removing a shot will never decrease the objective function, and therefore is not included in the neighborhood set.

Selection. As a selection method, Select (N(), x(s)), we use the steepest descent method, i.e., selecting the neighbor which decreases the objective function the most. To boost run-time performance the algorithm first considers adding a shot, and only if this is impossible it considers swaps. This approach reduces the complexity of the algorithm and demonstrates significantly better run-time performance in our experiments. S ← -S 8: end if 9: return: S

3.3. ILS-SUMM:

A local search algorithm may lead to a poor local minimum that is far away from the global minimum. Hence, after getting stuck in a local minimum, it is worthwhile to continue searching for other solutions which potentially can be far better. ILS performs this continued search, by repeatedly calling a local search algorithm which in each call starts from a different starting solution. As illustrated in figure 1 , in each iteration the starting point of the next iteration is a perturbation of the current solution.

ILS-SUMM pseudo-code is given by Algorithm 2. It consists of three main components which are executed at each iteration: A perturbation of the last solution, a call of a local search algorithm and a decision whether to accept the new found local minimum or to stay with the old solution. As a local search, we use the Local-Search-SUMM introduced above. In the following, we will go into more details regarding the perturbation mechanism and acceptance criterion. Perturbation. In this stage, the previous solution is modified to a different solution. Specifically, ILS-SUMM perturbs a given subset S by swapping M shots in S with M shots that are currently not in S. See the perturbation mechanism pseudo-code in Algorithm 3. To maximize the chance of getting a feasible solution, the perturbation is executed in a constraintgreedy manner. This constraint greediness means that the longest-duration currently selected shots are swapped with the shortestduration non-selected shots. However, if the new solution does not satisfy the knapsack constraint, then the original solution is returned (line 7). This perturbation mechanism is deterministic. Another option is to add randomness when selecting which shots to swap. Since the stochastic version did not lead to an improvement in the experiments, we retain the deterministic version which also enjoys the benefit of repeatability.

The strength of the perturbation can range between two extremes. On one extreme, it can totally change the solution and in fact, restart from a new solution. These complete initializations typically lead to long iterations and poor solutions because of the low quality of the starting solution. On the other extreme, applying a weak perturbation which only slightly changes the solution may lead to being stuck repeatedly in the same local minimum; hence, a good perturbation has a balanced intensity. As described in the ILS-SUMM pseudo code (Algorithm 2), we use a gradually increasing perturbation strength. It starts from M = 1 and gradually increases M by one until M MAX, i.e., a predefined maximum value of M is reached. In this way, we use the minimal strength of perturbation that accomplishes exiting the current local minimum.

Acceptance Criterion. In this stage, the algorithm decides which solution will be perturbed in the next iteration to get a new starting point. Two extreme cases of this procedure are either to always continue with the new local minimum obtained or to stick with the currently best achieved local minimum. The first extreme can be interpreted as a random walk over the local minima, whereas the second extreme can be viewed as a greedy local search over the local minima (Lourenc ¸o et al., 2019) . An intermediate approach would be to prioritize good solutions while occasionally exploring inferior solutions. An example of such a scheme is the Metropolis Heuristic where worse solutions randomly get the chance to be explored. An interesting modification of the Metropolis Heuristic is Simulated Annealing (Van Laarhoven & Aarts, 1987) , where the temperature of these exploration events, i.e., the probability of moving to a worse solution, progressively decreases. Since all the above options demonstrate similar results in our experiments, we assign an acceptance criterion which chooses the best achieved local minimum.

4. EXPERIMENTS:



4.1. EXPERIMENTAL SETUP:

Datasets. We evaluate our approach on two popular video summarization datasets -SumMe (Gygli et al., 2014) and TvSum (Song et al., 2015) , as well as on our new Open Source Total Distance dataset with full-length videos which we present below. SumMe consists of 25 user videos on various topics such as cooking, traveling, and sport. Each video length ranges from 1 to 6 minutes. TvSum consists of 50 videos with a duration varying between 2 to 10 minutes. We use a video shot segmentation technology to subdivide each video into shots (for details see Section 4.1). For SumMe and TvSum we use their common summary length limit which is 15% of the video length. We use Python PuLP library to obtain the optimal total distance of each video using an integer programming solver. As we will show in the results section, this integer programming tool has poor run-time scalability, but is useful for obtaining the optimal total distance as ground truth.

To evaluate the total distance results and the scalability on longer movies, we establish a new total distance dataset -Open-Source-Total-Distance (OSTD). This dataset consists of 18 movies with duration range between 10 and 104 minutes leveraged from the OVSD dataset (Rotman et al., 2016) . For these videos, we set the summary length limit to be the minimum between 4 minutes and 10% of the video length. Links for OSTD movies and ground truth optimal total distance of all above datasets are available on [www.github.com/ArthurName/ILS-SUMM].

Implementation Details. For temporal segmentation, we use two different types of shot segmentation methods, in accordance with video types. For the OSTD movies, we use FFprobe Python tool (Python Software Foundation, 2019) since this tool has high accuracy when applied on videos with fast shots transitions. For the SumMe and TvSum datasets, we use KTS proposed by Potapov et al. (2014) , since this shot segmentation method is more appropriate for catching slow shot transitions which are common in these two datasets. For feature extraction, we use the RGB color histogram with 32 bins for each of the three color channels. See some comments on using deep features in section 4.3.

For the perturbation mechanism of the ILS-SUMM, we set the maximum value of M to be 5 since we found that this value leads to a balanced perturbation intensity. However, we observed that ILS-SUMM is not sensitive to this value, and other values are just as satisfactory.

Evaluation. To compare between different approaches, we calculate the total distance defined in equation (1) that each approach achieved for each video. We then calculate the optimality percentage, i.e., the ratio between the optimal value and the achieved value, mutiplied by 100. For each method, we average all optimality percentages achieved on all the videos of a specific dataset, and report the averaged optimality ratio.

Comparison. To compare total distance results with other approaches, we apply DR-DSN (Zhou et al., 2018) and Submodularity (Gygli et al., 2015) on the datasets. For both methods, we use the implementations provided by the original authors. Although both methods can optimize multiple objectives, for our experiments we set them to maximize only representativeness since this is the evaluation metric we use. As mentioned above, an extension of our method to a multi-objective setting is straightforward, but to simplify the comparison we focus on representativeness.

4.2. RESULTS:

First, we compare our method with simple local search baselines. Then, we compare our method with previously proposed algorithms.

Comparison with baselines. We set the baseline algorithms as two variants of local search algorithms. The first baseline is Local-Search-SUMM described above in Algorithm 1. The second baseline, denoted by Restarts-SUMM, repeatedly restarts Local-Search-SUMM initialized with a different single shot at each restart and then selects the best result. The algorithm stops when it finishes going over the entire video shots or when the run-time resources are reached. For each video we set the Restart-SUMM maximum run-time allowed to be the video duration. Table 1 reports the total distance achieved by the baselines and ILS-SUMM on SumMe, TvSum, and OSTD datasets. Although Restart-SUMM is significantly better than Local-Search-SUMM, it is still inferior to ILS-SUMM. More essentially, Restart-SUMM is highly unpractical since in many videos the time it takes for generating a summary with Restart-SUMM is equal to the time it takes watching the full video (for more details see the run-time analysis below). This indicates the usefulness of the ILS perturbation mechanism, which rather than initializing the solution to a completely new solution, partially reuses the good solution it already obtained and thus obtains better results in less time.

Comparison with previous approaches. Table 2 shows the results of ILS-SUMM measured against other video summarization methods that aim to minimize total distance, on SumMe, TvSum, and OSTD. It can be seen that ILS-SUMM significantly outperforms the other approaches on all datasets. Run-time performance. Table 3 presents the run-time measurements of the PuLP, Submodularity, Restart-SUMM and ILS-SUMM methods in OSTD dataset. Our experiments demonstrate that for obtaining a reasonable solution, submodularity is the fastest approach. These results may be expected since Submodularity runs only two iterations of greedily adding shots, without any further exploration. However, as we presented above, ILS-SUMM obtains significantly better results than submodular optimization, while enjoying a substantially better run-time scalability than PuLP. With these numbers it is possible to make a decision of solution optimality vs. run-time for a given specific use of video summarization. (Otani et al., 2019) , there is no solid evidence for an advantage in using deep features rather than color histogram features for this task. To decide which features to use, we extracted both types of features for all videos from the SumMe dataset. For color histograms we used 32 bins of each of the RGB channels, and as deep features we used the penultimate layer from the ResNet model (He et al., 2016) pre-trained on ImageNet (Deng et al., 2009) . Then, for each video, we applied a dimensionality reduction on these features using PCA.

We observed that even though deep features are better in representing the semantics of the images, color histogram features seem to represent background and scene changes better. For example, Figure 3a visualizes the color histogram feature space of the "Bearpark Climbing" video from the SumMe dataset, and Figure 3b visualizes the deep feature space. The plot's axes are the two first principle components of the shot features. Each shot is represented by the image of the middle frame in the shot. It can be seen that in both cases, deep and shallow features, different scenes tend to be located and grouped in different parts of the feature space. However, the grouping of the color histogram space visually looks better than the deep features grouping, especially given the task definition of creating a summary which is visually similar to the source. Therefore we used the color histogram features to represents shots in this paper. Future research may examine the integration of deep and color histogram features.

5. CONCLUSION:

In this paper, we have proposed a new subset selection algorithm based on the Iterated Local Search (ILS) framework for unsupervised video summarization. Motivated by the success of ILS in many computationally hard problems, we leverage this method for explicitly minimizing the total distance between video shots and their nearest selected shots under a knapsack-like constraint on the total summary duration. We have shown that a proper balance between local search and global exploration indeed leads to an efficient and effective algorithm for the Knapsack Median problem. Our experiments on video summarization datasets indicate that ILS-SUMM outperforms other video summarization approaches and finds solutions with significantly better total distance. Furthermore, experiments on a long videos dataset we have introduced demonstrate the high saclability of our method.

:



Figures and Tables:

Figure 1: Illustration of Iterated Local Search framework. Given a local minimum S * , a perturbation leads to a solution S . Then, a call of a local search algorithm obtains a local minimum S * which is potentially better than S * .

Figure 2: ILS-SUMM selection in Cosmos Laundromat movie from OSTD data set. The middle frame of shot is presented. A red circle denotes the shots that were chosen by ILS-SUMM algorithm.

(a) Visualization of the color histogram features. (b) Visualization of the deep features.

Figure 3: Visualization of the features of the shots of "Bearpark Climbing" video from SumMe dataset. In each figure the features dimension were reduced to two dimensions using PCA. Figure (a) visualizes the color histogram features, and Figure (b) visualizes the deep features.

This problem is known in the Operations Research field as the Knapsack Median (KM) problem.Motivated by the success of Iterated Local Search (ILS) in many computationally hard problems(Lourenc ¸o et al., 2019), we use this simple yet powerful metaheuristic to address the KM problem, and consequently obtain a representative video summary. A fundamental component in the ILS framework is a local search algorithm. In the following section, we first introduce a local search algorithm tailored to the KM problem, which we name Local-Search-SUMM, and subsequently we present the complete ILS-SUMM algorithm.

Table content: <table/>

Results (total distance optimality percentage) of different variants of local search on SumMe, TVSum and OSTD.We can see that ILS-SUMM clearly outperforms Local-Search-SUMM. This result demonstrates the importance of the exploration process of ILS, since stopping the algorithm in the first reached local minimum as done in Local-Search-SUMM is far from optimal.

Table content: <table><tr><td/><td>SumMe TVSum OSTD</td></tr><tr><td colspan="2">Local-Search-SUMM 70.80% 87.11% 91.66%</td></tr><tr><td>Restart-SUMM</td><td>93.19% 98.19% 94.95%</td></tr><tr><td>ILS-SUMM</td><td>98.48% 99.27% 98.38%</td></tr></table>

Results (total distance optimality percentage) of different approaches on SumMe, TVSum and OSTD. Our ILS-SUMM exhibits a significant advantage over others

Table content: <table><tr><td/><td>SumMe TVSum OSTD</td></tr><tr><td>DR-DSN</td><td>90.78% 82.50% 62.56%</td></tr><tr><td colspan="2">Submodularity 85.18% 94.14% 95.99%</td></tr><tr><td colspan="2">ILS-SUMM 98.48% 99.27% 98.38%</td></tr></table>

Run-time comparison (% of video duration)  between PuLP, Submodularity, Restart-SUMM and ILS-SUMM in OSTD dataset.

Table content: <table><tr><td/><td colspan="4">PuLP Submodularity Restart-SUMM ILS-SUMM</td></tr><tr><td>Big Buck Bunny (596 [Sec])</td><td>1.96%</td><td>0.02%</td><td>8.08%</td><td>0.33%</td></tr><tr><td>La Chute dune Plume (624 [Sec])</td><td>0.48%</td><td>0.01%</td><td>2.12%</td><td>0.09%</td></tr><tr><td>Elephants Dream (654 [Sec])</td><td>0.60%</td><td>0.01%</td><td>2.34%</td><td>0.11%</td></tr><tr><td>Meridian (719 [Sec])</td><td>1.66%</td><td>0.01%</td><td>5.10%</td><td>0.21%</td></tr><tr><td>Cosmos Laundromat (731 [Sec])</td><td>0.95%</td><td>0.01%</td><td>2.41%</td><td>0.06%</td></tr><tr><td>Tears of Steel (734 [Sec])</td><td>1.51%</td><td>0.01%</td><td>6.90%</td><td>0.29%</td></tr><tr><td>Sintel (888 [Sec])</td><td>0.83%</td><td>0.01%</td><td>5.67%</td><td>0.32%</td></tr><tr><td>Jathia's Wager (1261 [Sec])</td><td>2.09%</td><td>0.02%</td><td>21.20%</td><td>0.38%</td></tr><tr><td>1000 Days (2620 [Sec])</td><td>5.48%</td><td>0.02%</td><td>71.48%</td><td>0.98%</td></tr><tr><td>Pentagon (3034 [Sec])</td><td>4.71%</td><td>0.02%</td><td>50.10%</td><td>0.60%</td></tr><tr><td>Seven Dead Men (3424 [Sec])</td><td>22.49%</td><td>0.02%</td><td>62.47%</td><td>0.36%</td></tr><tr><td colspan="2">Boy Who Never Slept (4186 [Sec]) 25.47%</td><td>0.03%</td><td>100%</td><td>0.84%</td></tr><tr><td>Sita Sings the Blues (4891 [Sec])</td><td>58.33%</td><td>0.06%</td><td>100%</td><td>4.97%</td></tr><tr><td>CH7 (5189 [Sec])</td><td>24.10%</td><td>0.02%</td><td>100%</td><td>0.85%</td></tr><tr><td>Honey (5210 [Sec])</td><td>45.12%</td><td>0.03%</td><td>100%</td><td>1.19%</td></tr><tr><td>Valkaama (5586 [Sec])</td><td>51.82%</td><td>0.04%</td><td>100%</td><td>1.86%</td></tr><tr><td>Star Wreck (6195 [Sec])</td><td>91.96%</td><td>0.05%</td><td>100%</td><td>2.38%</td></tr><tr><td>Route 66 (6205 [Sec])</td><td>49.06%</td><td>0.05%</td><td>100%</td><td>3.13%</td></tr><tr><td>4.3 DEEP FEATURES</td><td/><td/><td/><td/></tr></table>

Peer review (iclr2020):
This paper proposes a method for unsupervised video summarization. The problem formulation considered in this paper is to minimize the total distance between each shot in a video and its nearest shot in the selected summary. The authors propose to use iterated local search (ILS) to solve this problem. To escape local optima, the authors propose to add a perturbation heuristic, which randomly swaps in a number of random shots. The method is evaluated on 3 datasets. The authors choose to use color histograms as shot features. In ablation study, the results show that the proposed ILS-SUMM outperforms a vanilla Local-Search-SUMM and an improved variant of Restart-SUMM. It also outperforms existing methods on all three datasets. Overall I found this paper clearly written. The method is clearly described. The ablation is helpful for understanding the design choices. It*s also nice that it outperforms existing methods in terms of total distance. My main concerns are regarding the experiments. 1. Does total distance reflect the quality of video summarization well? There exist human annotated video summarization datasets. It*ll make the results more convincing if the authors can show that the selected metric with the selected features (color histograms) reflects the human-judged quality. 2. How does it compare with supervised methods? I understand that being unsupervised is a useful feature (e.g., don*t require expensive annotations), but it would be useful to assess the trade-off. For example, how many annotations do we need to outperform an unsupervised method? If the number is small, it suggests that unsupervised methods probably haven*t reached to point being practically useful yet. Presenting these results and discussions would help readers build a more comprehensive view of the area of video summarization. In addition, if it works worse than supervised methods, knowing how big the gap is would also be useful. (It*s okay to perform worse than supervised methods, but having some comparisons would be useful. ) 3. In Sec 4.3, the authors discussed about the pros and cons of using deep features. While I agree with the authors on the observations, I think it*s still useful to present quantitative results, so readers can compare them with color histogram results. 4. Since the supporting of the proposed method is solely empirical (instead of providing new theoretical results), I believe making the experiments more thorough and extensive would greatly benefit this paper. 5. I also think the proposed method is technically light-wight. This is not necessarily a weakness, but I*d have a higher standard on experiments if the experiments are among the main contributions. Overall I think the paper would benefit from extending the experiments to make results more convincing. In its current form I think it*s not ready for publication yet.