Weighted Hough Forest for object detection
Yusuke Murai, Yuji Yamauchi, Takayoshi Yamashita, Hironobu Fujiyoshi
Chubu UniversityAichi, Japan{ym@vision., hf@}cs.chubu.ac.jp
Abstract

Figure 1. Image patches in positive sample

Probability
Low

1

Positive samples

High

Hough Forest is an object detection method basedon voting from patch images. In the Hough Forest
training, some negative patches are trained as a positive sample because the patches are truncated from thebackground region in a positive image. This makes areason to occur false positives. To overcome this problem, we introduce weight updating of training sample
to the Hough Forest. In the training of the proposed
method, if there is a positive sample with a high valueof similarity with a negative sample, sample weight are
updated to be smaller at each layer of the decision tree.
This makes it possible to suppress the vote to the background area. Experimental results show that the detection performance of the proposed method is 11% better
than that of conventional method, and is same as theconventional method with masked images.

Positive images(a) Test image(b) Likelihood map

Figure 2. Likelihood map voted by Hough Forest

Introduction

There are two approaches in object detection, called
region-based methods and local patch-based methods.
A region-based method performs feature extraction
from entire images of the detection window, and discriminates this image is a target object or not byclassiﬁers[1][2][3]. The method performs an exhaustive
raster scan on the input image and uses the trainedclassiﬁers to detect target objects. During this time,
there is a problem in that the detection precision candrop if part of an object is occluded or changes inshape.
With a local patch-based method, on the other hand,the voting is done using patches, so robust detection
is possible with respect to partially occluded objects.
Local patch-based methods are based on voteing by
Hough transform. Leibe et al., proposed an implicit
shape model (ISM) using a codebook [4]. With ISM,
the system performs vector quantization on a patch
image centered on a feature point extracted from an
input image, with reference to a codebook, and votes
for the centroid position of the object using training
sample information contained in the same codebook.
Gall et al., proposed a Hough Forest [6] that uses theRandom Forest[5] to construct decision tree to classify
patch images into two classes. At detection, the system traverses the Hough Forest during the raster scanand votes for the centroid position from patches thathave been identiﬁed as the target object. In the Hough
Forest training, some negative patches are trained as apositive sample, because the patches are cut out fromthe background region in a positive image, as shown in
Figure 1. This makes a reason to occur false positive
as shown in Figure 2(a). To overcome this problem, [7]reported a method for designing training sample. Thismethod [7] uses positive samples that are not mixed
with negative samples using mask image of the object.

However, the creation of masks human cost is high.
To resolve this problem, it is necessary to reduce theinﬂuence of negative sample automatically, which aresimilar to positive sample.
The objective of this work is to suppress the voteto the background area which as shown in Figure 2(b)becomes false positives, for object detection based on
Hough Forest. This paper presents a weighted Hough
Forest for object detection. In the proposed method,
we introduce weight updating of training samples tothe Hough Forest. In the training of the proposed
method, a weight of each training sample is updated
in each layer of decision tree. This makes it possible
to suppress the vote to the background area.

2 Proposed method
This section describes an algorithm of weighted
Hough Forest for object detection. In the training of
the proposed method, if there is a positive sample witha high value of similarity with a negative sample, sample weight is updated to be smaller at each layer of thedecision tree.

2.1 Training samples
Using a patch xi by grid sampling from the positive
images and negative images, we generate training sam(d)(d)
ples {(x1 , c1 , r1 , w1 ), · · · , (xN , cN , rN , wN )}. In thiscase, xi is the patch, ci is the class label {0, 1} of the(d)patch from image, ri is the oﬀset vector, and wi isthe sample weight at layer d of the decision tree. Thepatches sampled from the background are assigned theclass label ci = 0, while the patches sampled from theobject are assigned ci = 1. The subsets are generated
by random sampling from the training sample collection.

Depth0Positive Sample

calc

1

Weight Oﬀset vector

Negative Sample

Weightupdate

Leaf node
normarize

2

calc

updateInfomation of leaf nodeP

normarize

NFigure 4. Leaf node information
D
Leaf nodeP

In each decision tree, we repeat Steps 3 and 4 until all
the nodes in layer d have been generated.
PN

Conventional
methodNProposed
methodClass rate of leaf node

Figure 3. Weighted Hough Forest training process

2.2

Step4：Sample weight update Update the training
sample weights in each child node, after generating all
the nodes in layer d in each decision tree. We update(d)the weight wi using the evaluation function F basedon similarity. We deﬁne the F by Equation (4), andupdate the weight w(d) by Equation (5):Training of decision tree

The weighted Hough Forest training process isshown in Figure 3, with each processing step being
described below.
Step1：Weight initialization Initialize the weights(d)(0)
wi of the training sample i to wi = 1/N . In thiscase, d is a hierarchy of decision tree.
Step2：Split function candidates In this research,
we use the similarity according to a dominant orientation template (DOT) [8, 9] in the split function. The
DOT is obtained from a oriented histogram for each local region, and, is represented as binary feature. Template is choose from positive samples in the split node.
If the similarity of a training patch and the templateis less than the threshold value, it is branched to theleft, otherwise it is branched to the right. Split function candidates are created by repeating the process ofrandom selecting the template and the threshold.
Step3：Split function decisions Select the optimal
one from among the split function candidates. To dothis, we use two measures U1 and U2 to evaluate the(d)uncertainty for a set of cuboids A = {xi , ci , ri , wi }.
We switch between the two benchmarks described below in each layer in the evaluation function U? . We
deﬁne the U1 by Equation (1) for a sample collection
A, using entropy:
U1 (A) = |A|(−a · loga − (1 − a) · log(1 − a)),(1)where a is the positive sample rate, which we calculate
from Equation (2) using the sample weight wi :
∑(d)
wi(d)

a=wi

∈A∧ci =1

∑

(d)

wi(d)

,(2)

wi

∈A

The second U2 is a function that evaluates variationsin the oﬀset vector ri , as deﬁned by Equation (3):∑(3)
U2 (A) =(ri − rA )2 ,ri ∈A

where rA is the average value of the oﬀset vector ri , sothat U2 is equivalent to scattering of the oﬀset vector.

F (xi ) =1a+ln2 (1 − a) + 
(d)

wi

(d−1)

= wi

 = 0.000001,exp(F (xi )),

(4)
(5)

(d)

If the sample weight wi has a high value, this indi(d)cates likely to be a target. If the sample weight wi islow, this indicates likely to be non-target. Finally, wenormalize the weights of the positive samples withinthat node by Equation (6):(d)

(d)

wiw
∑i=(d)

wi(d),(6)wi∈S(d)where Sd represents all of the sample sets in the layerd.
Step5：Repeat Steps 2 to 4 Repeat the node generation and weight update of Steps 2 to 4 until either
the number of samples is less than a given number ora speciﬁed depth D has been reached. As the layers
become deeper, a decision tree is constructed having abranch structure where the inﬂuence of samples withlow weights is reduced.
Step6：Leaf node generation Store weighted sample rates for positive and negative, and a list of oﬀset
vectors to the object center in a leaf node, as shownin Figure 4. By constructing a decision tree by theabove processing, we are able to automatically lower
the weight of positive samples that are similar to nontarget objects.

2.3 Voting process
During the voting, a likelihood map of the same sizeas the input image is prepared. A patch image thathas been cut out from a position of the input image isinput to each decision tree, to obtain a positive sample
rate for each decision tree. Votes for each decision
tree are cast in a vote space using oﬀset vectors stored
in the eventual leaf nodes. The system detects theobject with respect to the generated likelihood map
by performing mean shift analysis.

1
HF
Proposed

0.9

Mask

0.8

p=0

RecallTraining image

0.7

p = 60

0.6

0.5
0.5

0.6

0.7

Precision

0.8

0.9

1

result using Pascal VOC car dataset

Figure 5. Creating training samples using themask

1
HF
Proposed

0.9

Experiments

0.8

We conducted evaluation experiments to conﬁrm thevalidity of the proposed method. We used cars, pedestrian, and rotated objects as the detection targets ineach round of experiments and compared the resultswith those of the Hough Forest using mask [7], whichis the conventional method.

3.1

0.7

0.6

0.5
0.5

Car
Pedestrian

p=0
0.70
0.67

p=20
0.78
0.76

p=40
0.84
0.79

p=60
0.81
0.77

proposed
0.83
0.77

Evaluation using the Pascal VOC dataset
and INRIA Person dataset

We show the experimental results using the otherdataset. In evaluation, we used the recall-precition
curve.
Pascal VOC dataset：We use the dataset of car in
the Pascal VOC. The training data is composed 590

0.60.7Precision

0.80.91result using INRIA Person dataset

Comparison with Hough Forest using a mask

Training samples are created by using a mask. Patchto be used for learning is truncated based on the content of a fraction containing the positive region. Create a learning sample by changing the content of p. In
evaluation, we used the F-measure.
Car detection：Training is performed using the Car
Side Training Set [10] in car detection. The training
data is composed 550 positive images and 500 negativeimages. The evaluation data of car is performed using
the UIUC cars dataset of 5667 images.
Pedestrian detection：Training is performed using
the TUD pedestrian data sets in pedestrian detection.
The training data is composed 100 positive images and190 negative images. The evaluation data of pedestrianis performed using the TUD pedestrian data sets of 250
images.
Mask indicating a positive region is provided in either data set. The car and pedestrian detection accuracy are shown in Table 1. p = 0 is a state that
does not use a mask. In comparison with the Hough
Forest(p = 0), we see that recall-precision is improved
with the proposed method. F value of the proposed
method in the car detection 0.13 higher than the conventional method. F value of the proposed method in
the pedestrian detection 0.10 higher than the conventional method.
Table 1. Comparison of the F-measure

3.2

Recall3Figure 6. detection result using Pascal VOC car
dataset and INRIA Person dataset

positive images and 5096 negative images. Evaluation
data is composed 4487 images.
INRIA Person dataset：The training data is composed 2388 positive images and 12180 negative images.
Evaluation data is composed 1126 images.
The detection accuracy are shown in Fig 6. In comparison with the Hough Forest, we see that recallprecision is improved with the proposed method. Proposed method compared to the conventional method
was improved 8% accuracy at Pascal VOC dataset, and
7% accuracy at INRIA Person dataset.

3.3 Discussion
We discuss the detection accuracy of the proposedmethod. Examples of the visualization of the weightsof training samples are shown in Figure 7. As canbe seen from Figs.7, we see that the weights of the car
and person regions are higher. Detection examples andlikelihood maps for each of the experiments are shownin Figure8. Figure 8(a) is a Hough Forest that wasconstructed using a content rate p = 0 of the training samples, Figure 8(b) is a detection example by theproposed method. False positives occur in the conventional methods, because vote value to the backgroundarea is large. The proposed method can suppress false
positives, because vote value to the background area
is small. From the above results, the weighting of thelearning sample can be validated. From the above results, the validity of the weighting of the learning sample was conﬁrmed.

4 Conclusions
We have proposed an weighted Hough Forest which
can suppress false positive of background area by lowering the weight of training samples that are similar tonegative samples. The proposed method has demonstrated it can suppress votes for background region

UIUC cars dataset
TUD Pedestrian dataset
Pascal VOC dataset
INRIA Person dataset(a) Hough Forest(b) Proposed method

Figure 8. Car detection examples and their likelihood maps

LowWeightHigh

Weight map

Mean gradient

Mean gradient

CarWeight map

High weight

High weight

Low weight

Low weight

PedestrianFigure 7. Visualization of teaining sample weights

with respect to conventional Hough Forest and enables
the detection of target objects more stably. In the future, we intend to investigate the design of local image
feature in order to increase the precision of the proposed method.

References[1] N. Dalal, and B. Triggs.: “Histograms of Oriented
Gradients for Human Detection , Computer Vision

and Pattern Recognition, vol.1, pp.886-893, 2005.
[2] C. Cortes, and V. Vapnik.: “Support-vector networks, Machine Learning, pp.273-297,1995.
[3] Y. Freund, and R. E. Schapire.: “Experiments witha new boosting algorithm , International Conference
on Machine Learning, pp.148-156, 1996.
[4] B. Leibe, A. Leonardis, and B. Schiele.: “Robust object detection with interleaved categorization and segmentation , International Journal of Computer Vision, vol.77, no.1-3, pp.259-289, 2008.
[5] L. B. Statistics, and L. Breiman.: “Random forests ,Machine Learning, pp.5-32, 2001.
[6] J. Gall, and V. Lempitsky.: “Class-specific hough forests
for object detection”, Computer Vision and PatternRecognition, 2009.
[7] S. Shimizu, N. Watanabe, Y. Miwa, M. Seki, T. Hirai
and H. Fujiyoshi.: “Training Method for an Object
Detection Using Hough Forests”, Vision Engineering
Workshop, 2012.
[8] S. Hinterstoisser, V. Lepetit, S. Ilic, P. Fua, and N.
Navab.: “Dominant orientation templates for real-time
detection of texture-less objects , Conference Computer Vision and Pattern Recognition, pp.2257-2264,
2010.
[9] D. Tang, Y. Liu, and T.-K. Kim.: “Fast pedestrian
detection by cascaded random forest with dominantorientation templates , British Machine Vision Conference, 2012.
[10] “Car Side Training Set , http://www.vision.ee.ethz.ch/˜bleibe/data/datasets.html