OBJECT LOCALIZATION BASED ON SPARSE REPRESENTATIONFOR REMOTE SENSING IMAGERYNaoto Yokoya and Akira Iwasaki
Department of Advanced Interdisciplinary Studies, The University of Tokyo, Japan
ABSTRACTIn this paper, we propose a new object localization method
named sparse representation based object localization (SROL),
which is based on the generalized Hough-transform-based approach using sparse representations for parts detection. The
proposed method was applied to car and ship detection inremote sensing images and its performance was comparedto those of state-of-the-art methods. Experimental results
showed that the SROL algorithm can accurately localize categorical objects or a specific object using a small size of
training data.
Index Terms— Sparse representation, object localization, generalized Hough transform
1. INTRODUCTION
The spatial resolution of optical remote sensing imagers has
been improving particularly in the last decade, e.g., GeoEye,
WorldView, and Pleiades series. Skysat series firstly launchedon November 2013 enable the acquisition of movies with a
1-m ground sampling distance (GSD) from space. These advances in sensor technologies allow advanced image understanding and interpretation, such as object detection and localization. Fully automated object localization is required toanalyze big data of high-spatial-resolution imagery.
Object detection has been actively studies in the field ofcomputer vision. A joint use of local-feature extraction andclassification based on machine learning algorithms is an effective approach for object detection. Various feature extraction methods, such as Haar-like feature, the scale invariant
feature transform (SIFT), and histograms of oriented gradient (HOG), have been used for many tasks of object detection[1, 2, 3]. Support vector machine (SVM) and AdaBoost are
well-known classifiers used for object recognition [1, 4].
An approach that uses the presence of parts for the object class and their structural relations has been getting attention for object detection. Agarwal and Roth proposed an
approach for learning a sparse, part-based representation for
object detection and showed its robustness to partial occlusion
and background variation [5]. The Hough-transform-based
method proposed by Leibe et al. learns the class-specific implicit shape model (ISM), which detect local appearances ofcategorical objects according to a codebook and localize objects considering their co-occurrence consistency by the generalized Hough transform [6]. Gall and Lempitsky proposeda class-specific Hough forest algorithm, which uses a random
forest to discriminatively detect object parts and directly castprobabilistic votes about possible centers of the object to generate a Hough image [7].
Object detection of high-resolution remote sensing images has different characteristics compared to ground-shot
images: objects are generally small relative to a GSD withcluttered backgrounds; rotation invariance is required, whereas
scale invariance is not strongly required owing to the a fixed
GSD for each imaging sensor and appearance changes are
relatively small owing to limited pointing angles. Many researchers have worked on detection of specific object classin remote sensing imagery, such as car, ship, and airplane
detection; however, many of them are adhoc and limited to
specific uses. Lei et al. proposed an extended method of theHough forest for object detection of remote sensing images[8]. The major improvement is to achieve rotation invarianceby firstly detecting dominant gradient orientations and alignlocal image patches.
The theory of sparse representation and compressed sensing has been getting attention in the areas of signal processing, computer vision and pattern recognition [9]. Sparse representations enable finding essential image patterns and havebeen used for a wide range of image processing applications[10]. In this paper, we present a new method, named sparse
representation based object localization (SROL), to detect andlocalize categorical objects or specific objects in remote sensing imagery. Our approach uses sparse representations as
local-feature detection of the generalized Hough-transformbased object localization. Parts of the object are detectedby sparse representations of patches in an input image using
pre-learned target and background dictionaries and the locations of the objects are determined by considering their structural relations using the generalized Hough voting. We adopt
sparse representations for local-feature detection to deal withcluttered backgrounds, occlusion, and appearance changes ofobjects and to achieve a good performance with a small sizeof training data. Our experiments are performed on car andship detection to demonstrate the effectiveness of the proposed method.

Three sample
patches

Parts detection

Hough image

Target dictionary

Gaussian blurred Detection
Hough image
hypothesis≈

×-0.5 0.0

Fig. 1. Outline of object localization based on sparse representation.
2. METHODOLOGY
Fig. 1 illustrates the outline of our proposed method. The
SROL algorithm is composed of four steps: i) sliding window
search to extract patch images in a test image; ii) parts detection via sparse representations of patch images; iii) Houghvoting using offsets of detected parts of the target object; iv)
finding local maxima in the Hough image.
2.1. Dictionary Construction
The fist task of any local-feature based approach is to detectobject parts in a given image. Sparse representations can beused for this purpose. Any patch image is assumed to be represented as a sparse linear combination of atoms. A patch
image y ∈ RP is formulated asy ≈ Dx,(1)

where D ∈ RP ×N denotes the dictionary with each column
vector representing an atom, x ∈ RN is the sparse coefficient
vector, P is the number of pixels in the patch image, and N is
the number of atoms. In the sparse representation, the numberof nonzero values of x is assumed to be much smaller than P ,i.e., ∥x∥0 ≪ P . Therefore, x is obtained by the following
optimizationmin ∥x∥0 s.t.∥y − Dx∥22 ≤ ϵx(2)This optimization is known as an NP-hard problem; however,
several techniques have been studied to approximately solve
it, such as matching pursuit (MP) and its extensions [11, 12].
In the case of ∥x∥0 = 1, the MP-based sparse representation acts as image matching using an Euclidean distance forsimilarity measurement.
When atoms of the dictionary have class labels, i.e., target or background, sparse representations can be used for
object part detection. We prepare the dictionary D as thehorizontally stacked matrix [Dt Db ], where Dt ∈ RP ×Nt
is the target dictionary with the column vectors representing various parts images of the target and Db ∈ RP ×Nb isthe background dictionary with the column vectors representing atoms of the background. Nt and Nb are the numbersof atoms for the target and background dictionaries, respectively, and then N = Nt + Nb . Fig. 2 illustrates the binaryclass-labeled sparse representation of a patch for object partdetection. Positive coefficients of the target-dictionary atoms,

Background dictionary

+

×

1.0

Fig. 2. Binary class labeled sparse representation of patch.
xk > 0 (k ≤ Nt ), suggest the existence of the object parts.
The first step of our approach aims to construct a structured
dictionary.
Learning a dictionary directly from training data usuallyleads to better representation than using a predetermined dictionary. We adopt the K-SVD algorithm to build a reconstructive and compact background dictionary [13]. A large numberof patch images that do not include the target objects are randomly sampled and K-SVD is applied to them to learn the
background dictionary, which can reconstruct various patch
patterns including cluttered backgrounds. In our implementation, we construct the background dictionary depending on
the GSD of test images because patch patterns are conditional
to the GSD.
Random sampling and atom selection are used to construct the target dictionary. We keep raw image patches because each atom of the target dictionary needs to have the offset of the patch relative to the center of the object for Houghvoting. To achieve rotation-invariant object localization, we
augment the training samples with rotated copies of the original images and obtain an initial redundant target dictionary
by random sampling. Next, the number of atoms in the redundant dictionary is reduced by removing samples that havevery similar other samples. The zero-mean normalized crosscorrelation (ZNCC) is used to measure the similarities between all samples. The offset (δik , δjk ) of the patch centerfrom the target center need to be linked to the patch image,i.e., the k th atom in Dt (k = 1, ..., Nt ). When the target havesufficient spatial features, it is possible to estimate its orientation. In this case, the orientation of the target (θk ) is also
linked to the patch image.
2.2. Object Localization with Sparse Representation
Based Hough Voting
Sliding-window search for all patches of the test image istime-consuming. Interest point detectors have widely beenused for the Hough-transform-based object detection; however, small sizes of objects in remote sensing images require
lower level feature detector for sliding-window search. We
use edges obtained by a Sobel operation for sliding-window
search. In this case, the generation of the target dictionary canbe effectively processed by sampling patches along edges tomake consistency between patch images of the dictionary andtest images.

Ground truth
Precision: 0.931 Recall: 0.885

True positive

False positive
Precision: 0.839 Recall: 0.658

10 m

10 m

(b)
1

0.9

0.9

0.8

0.8

0.7

0.7

Precision

Precision

(a)
1

0.6
0.5
0.4

SROL
Hough forest
HOG+SVM

0.3
0.2

0.5
0.4

SROL
Hough forest
HOG+SVM

0.3
0.2

0.1
0

0.6

0.1
0

0.2

0.4

0.6

Recall

(c)

0.8

1

0

0

0.2

0.4

0.6

0.8

1

Recall(d)Fig. 3. Car detection results and precision-recall curves for
two test images.
Sparse representations are used to judge whether a patch
image contains a part of the target or not dealing with changesof background and appearance of the target. For a patch with
its center locating at (i, j) of the test image, a sparse representation x is derived solving (2) by MP. When xk > 0 (k ≤ Nt ),it suggests that the target may be located at (i + δik , j + δjk ).
Higher value of xk indicates higher correlation between thegiven patch and the part of the target dk , and thus higher probability of the existence of the target. Therefore, we cast thevote of the value xk to the location (i + δik , j + δjk ), whichis the generalised Hough transform. The Hough image can beobtained as a result of iterations of this process for all patches,
which represents the existence probability of the target.
The target objects can be simply localized by returning
the set of the local-maxima locations in the Gaussian-filtered
Hough image. A Gaussian blur filter with its full width at half
maximum setting to the size of the smaller side of the target
object is useful to smooth the Hough image for effectively
finding its local maxima.
3. EXPERIMENTAL RESULTS
3.1. Car Detection
First, we demonstrate an experiment of car detection using
airborne images. The RGB images were taken over urban areas of Tokyo Japan from approximately 1000 m altitude with
the 0.2 m GSD on 11 August 2013. The images were converted to Lab color space and the lightness channel was used
for processing. 36 training samples were used for this exper-

iment. Detection results are considered as “true” when their
Euclidean location errors from the ground truth are less than
the average size of the objects. The patch is 13×13 pixel
size. The proposed method is compared to the state-of-the-art
methods, i.e., the joint use of HOG and SVM (HOG-SVM)
and the rotation-invariant Hough forest [8]. We use the same
window search and patch size for the Hough forest for a faircomparison. The patch size of HOG-SVM is set to 40×40
pixel size to include a whole object. The precision-recall
curve is used to quantitatively evaluate their detection performances. Fig. 3 shows the car detection results of SROL
and the comparison of precision-recall curves for two test images. As shown in Figs. 3(c)(d), SROL outperforms HOGSVM and Hough forest for both images. One of the reasonsfor the low performance of HOG-SVM may be the small sizeof training data. Generally speaking, machine-learning-badeclassifiers (e.g. SVM) require a large size of training datacontaining various appearances of the object class. The patch
size of HOG-SVM is larger than those of SROL and Houghforest and thus requires more training samples to learn various
effects of backgrounds. In this sense, the generalized Houghtransform-based approaches have the advantage to constructobject detectors robust to cluttered backgrounds with a small
size of training data. In addition, sparse representations candeal with appearance varieties of the object by the background
dictionary using limited training samples, which result in robust detection of the parts compared to Hough forest. The
robust detection of the parts and the integration of their cooccurrences enables the accurate detection of the object class.
As shown in Figs. 3(a)(b), many of false negatives areblack cars. The main reason for this drawback is that there is
not enough characteristic parts for black cars. It is much morechallenging to distinguish black bodies and windows or dark
backgrounds. In addition, less edges around black cars resultin less searching windows for the proposed method, which isa critical issue to use co-occurrence of parts. Higher spatial
resolution may be required to accurately detect such objects.
3.2. Ship Detection
As a second illustration of the proposed method, we turn toship detection examples. The test image was taken over Sydney by WorldView-2 on 21 August 2012 with the 0.5 m GSD
in the panchromatic channel. The patch is 13×13 pixel size.
25 ships on the sea without no surrounding objects were used
for training data and two subimages were selected for testing.
Figs. 4(a)(b) show the ship detection results of SROL for thetwo test images and Figs. 4(c)(d) show the precision-recall
curves comparing with HOG-SVM and Hough forest. Even
though the test images include berths that clutter backgrounds
relative to the training samples, the SROL method successfully detect the ships. HOG-SVM performed relatively better
than the case of car detection because of the simpler backgrounds and the higher contrast between targets and back-Ground truth
Precision: 0.893 Recall: 0.833

True positive

30 m

30 m

(b)

1

1

0.9

0.9

0.8

0.8

0.7

0.7

Precision

Precision

(a)

0.6
0.5
0.4

SROL
Hough forest
HOG-SVM

0.3
0.2

4. CONCLUSION

0.6
0.5
0.4

SROL
Hough forest
HOG-SVM

0.3
0.2

0.1
0

its location. Fig. 5(c) shows the detected two ships as the top
two local maxima in the Hough image with each rectangle illustrating the estimated direction of the ship. To examine therobustness to occlusion, we added synthetic occlusion to thetest image. As shown in Fig. 5(d), the SROL method can still
localize the two ships as the 1st and 5th local maxima with theaccurate locations and orientations. This experiment provesthat the proposed method is also useful for target identification and it works well even with occlusion when informative
textures of the target are visible.

False positive
Precision: 0.857 Recall: 0.906

0.1
0

0.2

0.4

0.6

0.8

1

0

0

0.2

0.4

RecallRecall

(c)

(d)

0.6

0.8

1

Fig. 4. Ship detection results and precision-recall curves for
two test images.

We presented a novel object localization method based onsparse representation and demonstrated its effectiveness forremote sensing imagery. Parts of an object class or a specifictarget can be detected by sparse representations using the target and background dictionaries. This parts detection is integrated with the generalized Hough-transform-based object
localisation. Experimental results on car and ship detection
demonstrated a good performance of the proposed method
compared to the state-of-the-art methods using a small sizeof training samples.
5. REFERENCES(a) Target[1] P. Viola and M. Jones, “Rapid object detection using a boosted cascade of simple features,” in Proc IEEE Conf. on Computer Vision and Pattern Recognition,
2001.
[2] D. G. Lowe, “Discriminative image features from scale-invariant keypoints,”
International Journal of Computer Vision, vol. 60, no. 2, pp. 91–110, 2004.
[3] N. Dalal and B. Triggs, “Histograms of oriented gradients for human detection,”in Proc IEEE Conf. on Computer Vision and Pattern Recognition, 2005.
[4] M. Pontil and A. Verri, “Support vector machines for 3D object recognition,”
IEEE Trans. Pattern Anal. Mach. Intell., vol. 20, no. 6, pp. 637–646, 1998.

(b) Test image[5] S. Agarwal and D. Roth, “Learning a sparse representation for object detection,”
In Proc. ECCV, pp. 113–130, 2002.
[6] B. Leibe, A. Leonardis, and B. Schiele, “Robust object detection with interleaved categorization and segmentation,” Int. J. Comput. Vis., vol. 77, no. 1, pp.
259–289, May 2008.
[7] J. Gall and V. Lempitsky, “Class-specific Hough forests for object detection,” inProc. IEEE Conf. Comput. Vis. Pattern Recognit., 2009, pp. 1022–1029.

20 m(c) Detected objects without occlusion(d) Detected objects with occlusion

Fig. 5. Ship identification results.
grounds. The precision value of SROL decreases later thanthose of other methods, which implies that SROL preferentially detect parts of the target object and return their locations
owing to robust parts detection.
Finally, we show an example of identification of a specificobject. Fig. 5(a) shows the target of this experiment and Fig.
5(b) is the test image that captured two ships manually recognized as the same type with the target. Since this ship has
informative textures, we estimate its direction together with

[8] Z. Lei, T. Fang, H. Huo, and D. Li, “Rotation-invariant object detection of remotely sensed images based on texton forest and Hough voting,” IEEE Trans.
Geosci. Remote Sens., vol. 50, no. 4, pp. 1206–1217, 2012.
[9] D. L. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory, vol. 52, no. 4,
pp. 1289–1306, Apr. 2006.
[10] J. Wright, A. Yang, A. Ganesh, S. Sastry, and Y. Ma, “Robust face recognition
via sparse representation,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 30, no.
2, pp. 210–227, 2009.
[11] S. G. Mallat and Z. Zhang, “Matching pursuits with time-frequency dictionaries,” IEEE Trans. Signal Process., vol. 41, no. 12, pp. 3397–3415, 1993.
[12] Y. Pati, R. Rezaiifar, and P. Krishnaprasad, “Orthogonal matching pursuit : recursive function approximation with application to wavelet decomposition,” inProc. Asilomar Conf. on Signals, vol. 1, no. 40–44, 1993.
[13] M. Aharon, M. Elad, and A. M. Bruckstein, “The K-SVD: An algorithm fordesigning of overcomplete dictionaries for sparse representation,” IEEE Trans.
Signal Process., vol. 54, no. 11, pp. 4311–4322, 2006.