A Nfl-based and Feature Extraction Supported Shot Retrieval Approach

Zhen Lei, Yujun Liu, Wenge Zhang, Xuelin Liu2012 · DOI

Abstract

Nearest Feature Line (NFL) is a convenient and effective way to search in video database, but the Framework does not address the feature extraction for dimension reduction. In this paper, a novel method is proposed for content-based shot retrieval. Karhunen Loeve Transform (KLT) is used to reduce dimensionality of feature spaces. In addition, we present a new take-maximum-from-minima (TMFM) based key frame extraction algorithm, and keyframes extraction is combined with the NFL method to achieve a better performance. Experimental results have shown that our combined method not only achieves superior performance than the NFL and Equal interval (EI), and other classification methods such as Nearest Neighbor (NN) and EI and Nearest Center (NC) and EI but also increases the retrieval speed and reduces the memory significantly without sacrificing the retrieval accuracy.

The Challenge of Content-Based Video Retrieval

Content-based video retrieval is a significant "big data" challenge. When searching for a specific video shot, systems typically analyze low-level features such as color, texture, or shape. However, these raw feature vectors are often massive and high-dimensional, containing significant "noise"—information that does not contribute to distinguishing one shot from another.

High dimensionality presents two primary obstacles:

  1. Computational Burden: Processing and comparing complex vectors is time-consuming.
  2. Memory Demand: Storing these vectors for millions of video frames is resource-intensive.

While the Nearest Feature Line (NFL) method is a popular framework for navigating video databases, it does not inherently address the dimensionality problem. This research bridges that gap by streamlining how features are extracted and represented.

Methodology: A Three-Pronged Approach

The proposed method integrates three core components to optimize retrieval:

  1. Dimensionality Reduction via KLT: The Karhunen Loeve Transform (KLT) is employed to strip away redundant data. By identifying the most significant "directions" in the feature space, KLT allows the system to discard less important dimensions that contribute more noise than value.
  2. TMFM Keyframe Extraction: Rather than processing every frame, the system selects "key" frames using a novel Take-Maximum-From-Minima (TMFM) algorithm. This iterative process starts with an initial frame and selects subsequent frames that are maximally distant from existing keyframes, ensuring the selection represents the most diverse parts of the video shot.
  3. Improved Nearest Feature Line (NFL): A video shot is represented as a trajectory in feature space. By connecting the feature points of keyframes with lines, retrieval is simplified to finding the shortest distance between a query point and these lines.

Key Insights: The 35% Rule

A critical finding of this study is that 100% of the data is not required for optimal results. The researchers discovered that by using KLT, they could discard 65% of the feature dimensions while maintaining stable retrieval accuracy. This "35% Rule" significantly reduces the computational load.

Impact of dimensionality reduction on retrieval accuracy using KLT.

Furthermore, the TMFM algorithm prioritizes "diversity over density," preventing the system from wasting resources on redundant, nearly identical frames within the same shot.

Key Results and Performance

The experimental evaluation utilized 30 minutes of news footage (120 video shots) with 475-dimensional feature vectors. The results demonstrated significant efficiency gains over traditional methods like Nearest Neighbor (NN) or Nearest Center (NC).

Comparison of retrieval performance across different algorithms.
  • Speed and Memory: Retrieval speed was tripled, and memory requirements were reduced to one-third of the original size.
  • Accuracy: The NFL+TMFM approach outperformed Equal Interval (EI) sampling and performed on par with the more complex Breakpoint (BP) method.

Conclusion

By combining KLT dimensionality reduction with the TMFM keyframe extraction algorithm and the NFL framework, this approach offers a robust solution for efficient video shot retrieval. Future work will focus on scaling the method to larger datasets and incorporating Relevance Feedback (RF) to further refine accuracy.

Summary updated

Abstract

Nearest Feature Line (NFL) is a convenient and effective way to search in video database, but the Framework does not address the feature extraction for dimension reduction. In this paper, a novel method is proposed for content-based shot retrieval. Karhunen Loeve Transform (KLT) is used to reduce dimensionality of feature spaces. In addition, we present a new take-maximum-from-minima (TMFM) based key frame extraction algorithm, and keyframes extraction is combined with the NFL method to achieve a better performance. Experimental results have shown that our combined method not only achieves superior performance than the NFL and Equal interval (EI), and other classification methods such as Nearest Neighbor (NN) and EI and Nearest Center (NC) and EI but also increases the retrieval speed and reduces the memory significantly without sacrificing the retrieval accuracy.
BibTeX
@misc{lei2012nfl,
  author = {Zhen Lei and Yujun Liu and Wenge Zhang and Xuelin Liu},
  title = {{A Nfl-based and Feature Extraction Supported Shot Retrieval Approach}},
  year = {2012},
  doi = {10.2991/iccasm.2012.272},
}
Figure