International Journal of
Physical Sciences

  • Abbreviation: Int. J. Phys. Sci.
  • Language: English
  • ISSN: 1992-1950
  • DOI: 10.5897/IJPS
  • Start Year: 2006
  • Published Articles: 2569

Full Length Research Paper

A novel method for object detection based on graph theory

Shu Zhang*, Mei Xie, Yuefei Zhang and Ting Wei
School of Electronic Engineering, University of Electronic Science and Technology of China, Chengdu, China.
Email: [email protected]

  •  Accepted: 10 August 2011
  •  Published: 16 November 2011



Ideal object detection result in an image is an optimal free shape sub-window that tightly covers the object of interest. However, the sub-windows considered in widely-used sliding window method are limited to rectangles. This paper proposed a new graph-theoretic method which allowed the detection sub-window to be any shape for object detection. Firstly, local features responses were calculated by using locality-constrained linear coding (LLC) technique. Then the proposed method take advantage of local feature response and boundary information to construct an objective function for the whole image and global optimal solution is obtained by graph cut algorithm. We provided results on two challenging object detection datasets, and demonstrated that the proposed method can obtained better spatial support and higher detection precision than existing sliding window method.


Key words: Object detection, graph cut, sliding window, locality-constrained linear coding (LLC), support vector machine (SVM).



VOC, Visual object classes; SVM, support vector machine; LLC, locality-constrained linear coding; BOF, bag of feature; SIFT, scale-invariant feature transform; SPM, spatial pyramid matching; HOG, histograms of oriented gradients.