Motion-sketch Based Video Retrieval Using a Trellis Levenshtein Distance

We present a fast technique for retrieving video clips using free-hand sketched queries. Visual keypoints within each video are detected and tracked to form short trajectories, which are clustered to form a set of space-time tokens summarising video content. A Viterbi process matches a space-time graph of tokens to a description of colour and motion extracted from the query sketch. Inaccuracies in the sketched query are ameliorated by computing path cost using a Levenshtein (edit) distance. We evaluate over datasets of sports footage.

1. Introduction

Techniques to search video databases are increasingly important in a media rich world. Video Retrieval is predominantly addressed by searching metadata tags, yet keyword based retrieval can be semantically ambiguous, and often lacks rich descriptive power for actions. Querying by Visual Example (QVE) can mitigate these problems, however most video QVE techniques require a photo-real query (an image [18], or video [4]) and so are unsuitable in use cases where exemplar footage is absent. This paper presents a new QVE technique for retrieving video clips using a freehand motion-sketch query, depicting both the colours and trajectories of objects (Figure 3).