Systems for multimedia retrieval have been object of scientific research for many years. When it comes to present results to the user many solutions disregard the set of problems connected to content delivery. Especially time-constrained results of video retrieval systems need a different visualization. In this paper we present our solution for hierarchical content browsing of video files. Our workflow covers the phases of ingest, transcoding, automatic analysis, intellectual annotation and data aggregation. We describe an algorithm for the graph-based analysis of the content structure in videos. By identifying the requirements of professional users we developed a user interface enabling to access retrieval results in different hierarchical abstraction levels.
INTRODUCTION Compared to other areas of information retrieval, the content-browsing of audiovisual media bears special challenges. Videos are time-dependent. Usually the user’s intention is to find an element inside a video, depicting a certain semantic concept like a person, topic, location or event. By querying a video database, the returned result is either a complete video item or a single element inside a video item determined by its time position. Professional users are not mainly interested in finding only a single occurrence of the queued semantic concept. They want to gather the whole sequence related to their search query, e.g. to reuse it in a news report or for historic research. The user usually sees the retrieval result as a starting point for a further manual searching process inside the video item which is operated by using the playback and seek functions of the player software. In this paper we present our approach to provide a hierarchical presentation of video items to support professional users while browsing and consuming the content of a media retrieval system. Based on the primary focus of video content from television programs, this solution works best on video material edited in a post-production workflow. It is not supposed to be used on e.g. surveillance videos. Our framework has been developed to provide automatic and intellectual annotation to historical television recorded on video tapes. The digitized master copies and their metadata can be searched and displayed in a web-based user interface (UI). Video shots and sequences can be explored as a hierarchical structure in the UI. The system is in use in a pilot project by the “media state authority of Saxony” (Sächsische Landesmedienanstalt) in Germany.
USER REQUIREMENTS & EXISTING WORKFLOWS Our use case focuses on user groups in professions that rely heavily on reviewing large amounts of video data on a daily basis like journalists, editors or historians.
In a set of interviews we asked a group of experts to describe their daily work. Thereby, we especially focused on those areas that deal with the examination of the results of archive queries. Other fields of interest were the process of querying, preferred software solutions and the planning of new reports or videos. Our findings were subsequently merged into an extensive workflow that was used for identifying different problem areas.
Altogether, we spoke to three experts from three different
German TV stations, who all work in the field of TV
journalism. Their similar statements and their reports on the
workflows of other professionals and institutions give reason to
believe that our workflow is representative for a significant
part in this field of work. Conducting surveys and interviews
[
Specific software solutions addressing these issues do not yet exist in professional scenarios. This leads to a highly inefficient workflow: Precision rates are usually low because of the described storing modalities and the lack of precise metadata. Therefore, numerous files of comparatively large size have to be inspected in a short period of time. Classical User Interfaces The software that is used is normally designed to handle the simple consumption of video content (e.g. VLC Media Player or Apple QuickTime) or the tasks of professional post-production (e.g. Avid MediaComposer or Adobe Premiere). Both approaches are based on a perspective that emphasizes the linear structure of the completed video whilst or after the process of editing. By showing an ordered sequence of single shots, they present the content in consideration of the editor’s intention but not of the needs of an expert using a retrieval system.
Requirements Based on these findings, we compiled a list of requirements that have to be met by a user interface to improve the user experience significantly: Metadata is usable for both video processing and visualization. Information can be displayed based on the video’s structure. Richness of detail can be increased for single segments of the video. The video itself can be accessed through any bit of information displayed in the UI. Relevant segments of the video can be used in later steps of the user’s workflow, e.g. editing.
FRAMEWORK
Our framework provides functionalities for audio and video
analysis, manual annotation, data warehousing, retrieval and
visualization. It uses specialized components for each aspect.
The core “dispatcher” is controlling the analysis process,
allocation of work units and data aggregation. As deduced
from [
I. Digitization and Transcoding
The very first step is an incoming control of each video tape
and the generation of a unique identifier. Our id system
consists of a 12-byte block and can be represented and displayed
for human reading as a combination of 12 hexadecimal digits
(e.g. 0000-0074-0000-0026-Z) in four segments plus a
calculated check character. After the initial logging, the video
tape is digitized with an automatic robot ingest system as
described in [
The resulting digital master file is encoded as a broadband
IMX50 video codec captured in an mxf-container for
archiving and data exchange. As defined by [
II. Automatic Analysis and Annotation
The created analysis proxy video is transferred to the analysis
cluster. The dispatcher schedules the analysis of each video
file as a sequence of consecutive analysis steps. For
performance reasons, each component can be instantiated multiple
times. In the common configuration, the system runs with up
to 12 individual virtual machines. The analysis components
are controlled by the dispatcher via a web-service interfaces.
Shot detection component
The shot detection is the first component in the workflow. It
provides a segmentation of the continuous video stream into
parts of uninterrupted camera recordings (shots). The
algorithms developed by [
Face detection component
The face detection component uses the key frames from the
shot detection to mark bounding boxes around each detected
face. The used algorithm is optimized for high precision and
developed by [
Text extraction component
The text extraction component detects areas of overlay text
boxes within the video steam. The algorithm by [
Speech Recognition
The Speech Recognition component makes use of the
speaker change recognition method described by [
III. Intellectual Annotation This framework is not only used for demonstration of our solutions. It is in productive use for archiving historical tape based material. This constitutes the need for additional intellectual annotation, since today’s automatic annotation can provide support, but it cannot substitute the intellectual work of a human entirely. Secondly, the manual annotated metadata is used as training sets and test sets for the development of new algorithms. Therefor we collect metadata for 1 (REM http://rmd.dra.de/remid.php?id=REM_APR_3) each video tape in form of classical intellectual annotation as it is already implemented in media archives.
Scene & Topic Annotation We developed a web-based annotation tool for the intellectual annotation of the analyzed video files. To support the professional user, the tool makes use of the detected video shots. The video is presented in slices of camera shots. The video player repeats the current shot in a loop. This makes it easier for the user to fill out all input fields, without constantly dealing with the player controls. When the user is finished with the shot, he can jump to the next. The user marks the boundaries of storyline sequences as collections of multiple shots and adds a variety of bibliographical metadata like title and type of video content, topics and subjects in terms of individuals, locations, institutions, things, creations (like art) and other metadata useful for either information retrieval or as development test data.
IV. Data Aggregation In the past we were only analyzing video assets for isolated scientific experiments. To process large quantities of videos now, the integration of results from different analysis algorithms becomes a key challenge. For our environment of use cases, a data-warehouse solution is needed to aggregate more than only the results of video analysis. On the one hand it needs to incorporate the metadata supplied from its sources, like production information and data from TV broadcasters. On the other hand it has to provide its data as an export artifact witch is compatible with formats and conventions used by achieving facilities and institutes.
A special challenge was to find a scheme, which complies with the way video content producers and archives structure their data, and includes technical data, like feature-vectors and audiovisual classifications. Our selected databasescheme is adapted from a common standard for video documentation1 developed for the German public television. We combined metadata fields from the point of mandatory and optional meta-data classes with the goal to maintain a maximum of compatibility.
V. Content Delivery and Visualization For data exchange and archiving, the digital master file, the proxy files and the metadata are exported to a LTO tape library. Search and content access for the user are provided by a webserver.
The user interface is used for web-based intellectual annotation, controlling the analysis process, information retrieval and for content browsing. The UI is able to handle multiple tenants and has as scalable interface for different display resolutions or devices. Each function runs in its own web-app. GRAPH-BASED VIDEO CLUSTERING During the analysis and automatic annotation we extract segments of camera shots from the video stream. This shot-segmentation is helpful for content browsing, but it suffers from over-segmentation. The structure is too detailed for the visualization of the actions inside a video. The user needs to be able to search for scenes or sequences as basic units. Procedure Sequence-Graph input: List of detected shot-boundaries and transitions ℎ, list of sequences . output: Sequence-graph 1( , ) 1. for each detected shot and transition ℎ from ℎ do add new vertex to 1 add new edge to 1 connecting and +1 4. end for each 5. for each sequence from do
create new in 1 7. end for each 8. for each from 1do if belongs to sequence then remove and it’s out-edges and in-edge from 1 add and it’s edges as sub-elements to the 2. 3. 6. 9. 10. 11. 12. 15. 18. 19. 20. 13. end for each 14. for each removed from 1 16. end for each 17. for each
from 1do
edge in 1 connecting with the predecessors resp. successors of remove all duplicates and increment the weight of 24, 25]. Shots are represented as nodes, transitions as edges. Shots with a high similarity are clustered into group-nodes. This process leads to a digraph with cycles.
Description Singular Edges – Directed edge between two Singular Nodes (Ns) representing the transition from a camera shot to its successor in the sequence of the video.
Singular Nodes – A single continuous camera shot.
Aggregated Edge – Directed edge between two Aggregated Nodes (Na) or between a Singular Node and an Aggregated Node. It represents a set of interrelated Singular Nodes, respectively a sub-graph containing a scene in the video.
Aggregated Node – A group of Singular or Aggregated Nodes as a sequence or sub-graph.
Color-Similarity-Group ( )
— A list of shots, grouped by its visual similarity. The similarity is measured by a combination of the
MPEGdescriptors Edge-Histogram (EHD) and Color-Layout (CLD). [10 pp.169] Sequence-List ( ) – A List of shots, grouped by their affiliation to a sequence, found by intellectual annotation. A sequence represents a segment of continuous action or location in a video. In order to access the video content in a graph based hierarchical structure, we create a directed graph to represent the video’s shots and sequences. The vertices belonging to a sequence are aggregated to build a second level in the hierarchy. Metadata created during the intellectual annotation performs the aggregation.
Procedure Similarity-Graph input: List of Color-Similarity-Groups , graph 1 output: Sequence-Graph with Similarity-Subgraphs 2 1. for each
from 1 do create new temporal graph for each similarity group from do if one or more sub-vertex of is ∈ then add new group-vertex to 2. 3. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30.
for each sub-edge ∪ from
do add new edge to connecting the corresponding vertex of its sources group-vertex and its targets group-vertex
, respectively the non-group-vertex if source or target is not part of an similarity group . end for each Calculate the strongly connected components of for each strongly connected component from do create new similarity-vertex for each shot-vertex from do
as sub-element in if
then remove and it’s out-edges and in-edge from add and it’s edges as sub-elements to the remove all duplicates and increment the weight of created on the second level, representing the chain of shots forming a sequence.
Similarity-Graph-Algorithm
One important feature of videos from film and television is
the presence of recurring images. This happens especially
when interviews or dialogs are recorded where the same
individuals are shown several times. In terms of film grammar
this is called the shot-/ reverse-shot method. See Figure 4
Resulting Graph Structure
The final resulting graph represents the video in a
hierarchical structure. On the first level all sequences and all
standalone shots can be accessed. By selecting a sequence all
shots and similarity groups inside the selected sequence can
be accessed. If a shot shows a similar image multiple times,
each instance of this image is aggregated to a group.
Recurring shots are recognizable by cyclic structures of the edges.
On selecting a similarity group the individual instances of the
similar shots can be accessed. The results of the two
clustering-steps and the final 3-layer graph are shown in Figure 5.
Figure 6 shows die visualization of a single layer as used in
the UI.
UI approaches with the purpose of addressing structures in
video content have been developed mainly in in the fields of
film studies and in human-computer-interaction (HCI). They
representing all content sequences as aggregated nodes and
the remaining singular nodes not belonging to a sequence on
the first level. Inside each aggregated node a sub-graph was
normally focus on certain key aspects like analysis,
description [4] or summarization [
By shifting the main focus to the video’s structure, we managed to design a user interface that makes it possible to quickly overlook a whole file without losing any detail. Graph-based User Interface In order to avoid the issues reported by our user groups, as described above, we decided to organize all available information in a way that emphasizes the video’s structure. Richness of detail is increased from top (overview) to bottom (all details and metadata). The presented metadata-types are summarized in Table 2. The following interface description is connected to the layers presented in the Figures 6 and 7. I. Video player – The player can be used to examine the single segments in any intended way. In order to provide permanent availability, it remains at the top of the screen when scrolling to the lower parts of the UI.
II. Current graph – Its nodes represent either a single shot group or a cluster of related groups. By using a simple directed graph for the top level, we were able to display all nodes in a familiar left-to-right-order. Every node contains a representative image sample and some basic information on its content. The existence of child graphs is color coded (blue) on this level of detail.
III. Collapsible container that is used to display a more granular child graph belonging to a certain top-level node. IV. Queue – Nodes can be transferred in a drag-and-drop operated queue of cards that offer a more detailed view of their content. Furthermore, they can be used to manage a collection of shots or shot groups that can be watched directly or exported for further use e.g. in editing software. V. Details-view – shows all data that is available for one of the cards. It consists of several lines displaying key frames, detected faces, off text and text overlays.
EVALUATION We performed a first evaluation of our approach by using a combination of baseline tests and questionnaires. Therefore, we designed a set of tasks comparable to those described by our group of experts. A screenshot of the graph-based UI is depicted in Figure 7. The content used for evaluation consists of real television news programs, produced during the early to mid-1990s. It was archived on VHS video tapes. The actual test-set was composed by randomly selecting 1377 minutes of this video material.
Four expert users were asked to perform searching tasks. They were given short descriptions of 27 randomly picked video sequences with durations between 5 seconds and 10 minutes. The task was to find the described sequences in the corresponding video file and to write down the time codes of the sequence boundaries. Searching tasks like these are quite comparable to the real live work of video editors, because video content in tape based archives is only marginally documented. Manual content browsing in a video player and non-linear editing software (NLE) is used to find sequences of video content reusable in new video clips.
For comparison, the searching tasks were performed by using our graph-based user interface, VLC Media Player and Adobe Premiere Pro (CS 6). For each task the time needed for completion was recorded. Overall, 108 different search operations were performed. Furthermore, differences in the accuracy of the time-codes were taken into account. With the graph-based UI, the average duration per searching task was 93 seconds. When searching with VLC (average: 122 s) and Premiere Pro (average: 179s) significantly more time was needed (Figure 8). As a result our graph-based solution outperformed VLC and Premiere Pro. In VLC 27.8% more time was needed. Searching in Premiere Pro needed 48.5% more time. One reason for the weak performance of Premiere Pro could be the zoom function. It was heavily used by the testers, but leaded to longer searching times.
One disadvantage of the graph-based UI turned out to be the fact that entities and events inside a video shot cannot be isolated. They are bound to the boundaries of the surrounding shot and cannot be exported independently. In terms of perceiving the actual structure of the video, all users reported gaining a deeper understanding when using our approach than when using VLC or Premiere Pro.
FUTURE WORK
The next step for the analysis and graph-based clustering will
be the substitution of the manual annotation of video
sequences by an automatic sequence segmentation algorithm.
Surveys on the state-of-the-art in video-segmentation
indicate that a multimodal fusion of the analysis results can be
used to cluster successive shots into video sequences. Most
approaches use visual similarity features. But as discussed in
[
The graph-based user interface will be evaluated in additional user tests, exploring if its use is beneficial for non-professional users as well. A second study will evaluate, which text-based metadata should be presented at the different elements to comply the need of the users. Currently, extensions of the UI are under development to enable a sync-function. It will allow adapting the presented graph elements when the current position in the video shifts to the next sequence. This will give the UI a two-sided interaction between the video player and the graph structure.
CONCLUSION In this paper we presented our concept of a hierarchical presentation of video items in a graph-based structure. We described our framework which incorporates video and audio analysis, intellectual annotation and graph analysis to construct a multi-layer structure for content-consumption. Our web-based UI shows how classical sequential content browsing in videos can be extended to incorporate the inner structures and relations of the video’s sub-elements.
ACKNOWLEDGMENTS Parts of this work were accomplished in the research project validAX funded by the German Federal Ministry of Education and Research.