Back

Image Classification using Random Forests and Ferns

Anna BoschAndrew ZissermanX. Muñoz

article2007ICCV1,489 citations

Demonstrates how combining spatial pyramid descriptors of shape and appearance with automatic region-of-interest selection and random forest classifiers significantly improves multi-class image recognition on large-scale benchmarks like Caltech-256.

Listen

Scaling computer vision models to accurately classify hundreds of diverse object categories presents a significant technical bottleneck. Traditional multi-class classification methods, such as support vector machines, demand extensive computational resources during training and evaluation. Furthermore, real-world image datasets frequently exhibit high background clutter and wide variations in object positioning, which degrade the accuracy of standard scene-matching algorithms.

The article demonstrates an efficient and highly scalable image classification framework tailored for large category sets. It evaluates how combining automated region of interest selection, multi-cue spatial descriptors representing both shape and appearance, and randomized decision structures—specifically random forests and random ferns—improves both classification accuracy and processing speed.

The research evaluated these techniques on standard visual recognition benchmarks, including the Caltech-101 and Caltech-256 datasets, spanning up to 256 categories. The approach first identifies regions of interest in training images by searching for visually consistent subregions across image subsets. It then constructs spatial pyramid representations for appearance using dense visual word distributions and for shape using edge orientation gradients. Finally, random forests and random ferns are trained on these multi-cue descriptors using linear node tests and information gain optimization, complemented by synthetic data augmentation.

The evaluation produced several critical findings. First, random forests achieved 45.3% accuracy on Caltech-256 (250 categories with 30 training images per class), surpassing the prior state of the art of 34.1% by approximately 11 percentage points. Second, the automated selection of regions of interest suppressed background clutter effectively, providing a 3% to 5% boost in overall classification performance. Third, random forests and ferns delivered classification accuracy comparable to a multi-class support vector machine on Caltech-101 (80.0% versus 81.3%) while decreasing classification time by a factor of 40. Finally, random ferns offered extreme training efficiency, training in 1.5 to 4 hours compared to 7 to 20 hours for forests, while suffering less than a 1% drop in accuracy.

These findings indicate that organizations deploying large-scale image recognition systems do not need to accept severe computational delays to attain top-tier accuracy. Transitioning to randomized tree structures significantly lowers computational infrastructure costs and accelerates operational throughput. Moreover, the modular integration of shape and appearance features provides robust classification across categories that vary widely in visual structure.

Teams implementing visual categorization systems should adopt randomized decision architectures—particularly random ferns when training time and memory are critical constraints. Practitioners should also integrate automated region detection and data augmentation into their training pipelines to enhance resilience against unaligned images. Future development should focus on testing more flexible, non-rectangular region proposals and incorporating more robust edge features.

The conclusions are supported by rigorous multi-trial benchmark testing on standard datasets. However, stakeholders should note that performance relies on rectangular bounding approximations and dense feature extraction grids, which may introduce limitations in environments characterized by extreme geometric deformations or high occlusion.

sift descriptorssvmlocal descriptorsrandom forestsimage classificationrandom ferns
Bosch et al (2007).pdf
Cover for Image Classification using Random Forests and Ferns

Topics

sift descriptorssvmlocal descriptorssupervised classificationobject detectionrandom forest classifier

Keywords

random forestsimage classificationrandom fernsspatial pyramid kernelPHOW descriptorsSIFT descriptorsobject recognitionSVM classifier

Table of Contents

  • 1. Introduction
  • 2. Image Representation and Matching
  • 3. Learning the model
  • 3.1. Selecting the regions of interest (ROI)
  • 3.2. Random forests classifier
  • 3.3. Node tests for PHOG and PHOW
  • 3.4. Random ferns classifier
  • 3.5. Image Classification
  • 4. Datasets and Experimental Protocol
  • 5. Implementation
  • 6. Image Classification Results
  • 6.1. Random Forests vs Multi-way SVM
  • 6.2. Comparison with the state of the art
  • 7. Conclusions
  • Acknowledgements
  • References

Knowls

  1. Knowl 1 — Joint spatial-pyramid representation of appearance and shape

    model/method

    Each image region is described by two spatial pyramids: PHOW for appearance and PHOG for local shape. PHOW is built by computing dense SIFT descriptors on a regular grid and quantizing them into visual words; PHOG counts quantized edge orientations in spatial cells. At pyramid level ll, the region is divided into 2l2^l cells along each dimension. If each cell has NN histogram bins (N=VN=V for the VV-word appearance vocabulary or N=KN=K for the KK-bin shape histogram), the concatenated pyramid descriptor through level LL has dimension N∑l=0L4lN\sum_{l=0}^{L}4^l. The implementation capped LL at 3. The illustration on page 2 shows the same spatial subdivision applied to appearance and shape features.

    Similarity between two region descriptors DID_I and DJD_J is computed with a weighted pyramid kernel:

    K(DI,DJ)=exp⁡ ⁣(1β∑l=0Lαldl(DI,DJ)).K(D_I,D_J)=\exp\!\left(\frac{1}{\beta}\sum_{l=0}^{L}\alpha_l d_l(D_I,D_J)\right).

    Here dld_l is the chi-squared distance between the normalized histograms at level ll, αl\alpha_l is that level's weight, and β\beta is the training-set average of the weighted sum of level distances. The paper uses this representation for both whole images and, in its ROI procedure, rectangular image regions.

  2. Knowl 2 — Alternating optimization of class-specific training-image ROIs

    algorithm

    For each training image, the method seeks a rectangular region of interest (ROI) that matches regions in a subset of ss other training images from the same class. Let rir_i be the ROI in image ii, let D(ri)D(r_i) be its concatenated PHOG–PHOW descriptor, and let KK be the pyramid similarity kernel. With the other images' current ROIs fixed, the update for image ii maximizes the sum of similarities to the best-matching subset of ss images:

    max⁡ri, Si: ∣Si∣=s, i∉Si  ∑j∈SiK(D(ri),D(rj)),\max_{r_i,\,S_i:\,|S_i|=s,\,i\notin S_i}\;\sum_{j\in S_i}K\bigl(D(r_i),D(r_j)\bigr),

    where SiS_i contains training images of the same class. The optimization alternates through images, updating one ROI at a time while holding the others fixed; for a candidate ROI, the matching subset is the ss other images with greatest similarity. This avoids exhaustive joint optimization over all images' rectangles and subsets.

    The implemented search starts with each full image as its ROI, varies rectangle scale in steps of 0.1, and searches translations on a 10-pixel grid. It repeats the scaling and translation search for each image until the ROIs stop changing or 10 iterations have been completed. The paper evaluates s=1s=1 to 44 and uses s=3s=3 in its principal experiments. The ROI montage on page 3 illustrates rectangles concentrating on object instances amid varied backgrounds. The method is restricted to rectangular ROIs; more flexible region shapes are identified as future work.

  3. Knowl 3 — Random forests with sparse linear tests over selected descriptors and pyramid levels

    model/method

    The classifier uses binary trees whose node tests are sparse randomized linear functions of the PHOW or PHOG feature vector xx. A test has a coefficient vector nn and offset bb: it sends xx to the right child when nTx+b≤0n^T x+b\leq 0, and to the left child otherwise. To construct a candidate, the method randomly selects nfn_f feature indices, assigns their coefficients values uniformly from [−1,1][-1,1], and sets all other coefficients to zero. Each test uses one randomly selected descriptor type (appearance or shape) and one pyramid level, so only coordinates for that descriptor and level can be nonzero.

    At each node, candidate tests are scored by their class-separation criterion based on the entropy of the resulting child sets, and the best candidate is retained. In the implementation, one third of the training images per class are used to choose tests and the remaining images estimate terminal-node posteriors. The root considers r=10r=10 candidates; a node at depth DD considers r=100Dr=100D. Growth stops at the maximum depth or when fewer than 10 examples reach a node. The standard configuration uses 100 trees of depth 20. Each leaf stores the empirical class proportions of training images that reach it; classification averages the reached-leaf class probabilities across trees and chooses the class with the largest average.

  4. Knowl 4 — Random ferns as a non-hierarchical alternative to trees

    model/method

    A random fern consists of an ordered set of binary tests rather than a hierarchy of branching nodes. In this paper each test uses the same kind of sparse linear threshold used by the forest classifier. The ordered test outcomes for an image form a binary code that indexes a fern's terminal entry; that entry stores the empirical class-posterior distribution for training images with that code. During testing, every fern produces a posterior distribution and the distributions are averaged across ferns to classify the image.

    Unlike a tree, each fern's ordered tests are applied to the full training set rather than to subsets routed down successive branches. The implementation uses 10 candidate tests per binary test and tests fern lengths S=10,15,S=10,15, and 2020, with S=20S=20 as the standard comparison setting. This replaces tree traversal with code-based lookup and, as measured in the paper, makes training time grow linearly with the number of tests per fern.

  5. Knowl 5 — Sliding-window inference over image translations and scales

    algorithm

    At test time, the classifier is applied to subimages from a sliding window over a range of translations and scales. For a window ww, let pt(c∣w)p_t(c\mid w) be the class-cc posterior at the leaf reached in tree tt, and let TT be the number of trees. The window's class score is the average posterior across the forest, and the image receives the class associated with the highest-scoring window:

    (w∗,c∗)=arg⁡max⁡w,c1T∑t=1Tpt(c∣w).(w^*,c^*)=\arg\max_{w,c}\frac{1}{T}\sum_{t=1}^{T}p_t(c\mid w).

    Here cc ranges over the trained object classes and ww ranges over the tested translations and scales. This inference procedure uses the learned training ROIs while allowing the object to occur at different positions and scales in a test image.

  6. Knowl 6 — Datasets, evaluation protocol, and principal configuration

    experimental setup

    The experiments use Caltech-101 and Caltech-256. The standard Caltech-101 split has 30 randomly selected training images and 50 disjoint test images per category; Caltech-256 uses 30 training and 25 test images per category. For the Caltech-256 comparison with prior results, the paper also reports the 250-category setting that excludes the final six categories and clutter. Each classification result is averaged over 10 random train/test splits and scored as mean recognition rate per class; standard deviations are reported.

    Unless otherwise specified, the Caltech-256 parameter studies use 100 trees, depth 20, entropy-based test selection, and all descriptors. The principal state-of-the-art comparisons use 100 trees or ferns of depth/length 20, ROI optimization, and augmented training data. Appearance implementation uses a 10-pixel SIFT grid, circular support radii 4, 8, 12, and 16 pixels, and a 300-word vocabulary. Shape uses Canny edges and Sobel orientation gradients, with 20 bins for orientations in [0,180][0,180] degrees or 40 bins for orientations in [0,360][0,360] degrees.

  7. Knowl 7 — ROI selection improves Caltech-256 classification

    data/table

    The paper measures the effect of optimizing training-image ROIs on Caltech-256 using 100 randomized trees of depth 20, entropy-based test selection, and all descriptors. Accuracy is mean per-class recognition rate; the table gives the standard deviation beneath each mean. ROI selection raises performance from 38.7% without optimization to 42.5–43.5% for s=1s=1 to 44, with the best reported value at s=3s=3. The page 5 results table presents this comparison; the gain at s=3s=3 is 4.8 percentage points.

    ROI setting None s=1s=1 s=2s=2 s=3s=3 s=4s=4
    Accuracy (%) 38.7 42.5 42.9 43.5 42.8
    Standard deviation 1.3 1.0 1.0 1.1 1.0

  8. Knowl 8 — Appearance, shape, entropy selection, and fern performance on Caltech-256

    data/table

    This Caltech-256 comparison evaluates shape-only, appearance-only, and combined descriptors with randomized trees and ferns. All settings use 100 trees or ferns, depth/length 20, and ROIs optimized with s=3s=3; entries are mean per-class recognition rates in percent with standard deviations. Shape180 and Shape360 use orientation ranges [0,180][0,180] and [0,360][0,360] degrees; AppC and AppG denote color and grayscale appearance. Combining all descriptors gives the strongest result for both classifier families. Entropy optimization raises the all-descriptor result from 41.9% to 43.5% for trees and from 41.0% to 42.6% for ferns. The page 6 results grid reports these cue and classifier comparisons.

    Classifier Split rule Shape180 Shape360 AppC AppG All
    Trees Random tests 38.5±0.838.5\pm0.8 39.3±0.939.3\pm0.9 35.2±0.935.2\pm0.9 39.3±1.039.3\pm1.0 41.9±1.241.9\pm1.2
    Trees Entropy optimization 39.2±0.839.2\pm0.8 40.5±0.940.5\pm0.9 36.5±0.836.5\pm0.8 40.7±0.940.7\pm0.9 43.5±1.143.5\pm1.1
    Ferns Random tests 37.7±0.837.7\pm0.8 38.1±0.838.1\pm0.8 34.7±0.934.7\pm0.9 38.9±0.938.9\pm0.9 41.0±0.941.0\pm0.9
    Ferns Entropy optimization 38.9±0.838.9\pm0.8 39.7±0.939.7\pm0.9 36.5±0.936.5\pm0.9 39.2±0.839.2\pm0.8 42.6±1.042.6\pm1.0

  9. Knowl 9 — Benchmark accuracy and speed relative to multi-way SVMs

    empirical result

    With 30 training images per class, the random forest reaches 80.0% on Caltech-101, compared with 81.3% for a multi-way SVM; the random-forest classification time is reported as 40 times lower. Both methods use learned ROIs with s=3s=3 and 10 generated training examples per original training image for this comparison. On the Caltech-256 250-category setting, the random forest reaches 45.3% with 30 training images, compared with the cited prior result of 34.1%, an 11.2-percentage-point gain. For the full 256-category setting without clutter, the reported random-forest result is 44.0%. The page 7 benchmark table compares results at 15 and 30 training images; its prior-method entries are included below to show the scope of the comparison.

    Method C-101, 15 C-101, 30 C-256, 15 C-256, 30
    Multi-way SVM – 81.3±0.881.3\pm0.8 – –
    Random forests 70.4±0.770.4\pm0.7 80.0±0.680.0\pm0.6 38.6±0.638.6\pm0.6 45.3±0.845.3\pm0.8
    Random ferns 70.0±0.770.0\pm0.7 79.2±0.679.2\pm0.6 37.5±0.837.5\pm0.8 44.0±0.744.0\pm0.7
    Prior method [5] 67.4 77.8 – –
    Prior method [13] 59.0 67.6 29.0 34.1
    Prior method [26] 59.0 66.2 – –
    Prior method [11] 60.3 66.0 – –
    Prior method [16] 56.4 64.6 – –
    Prior method [18] 59.9 – – –

    The Caltech-256 entries in this comparison are for 250 categories, not the full 256-category setting. Dashes indicate results not reported in the paper's comparison.

  10. Knowl 10 — ROI perturbations provide useful synthetic training examples

    empirical result

    To increase the number of positive training examples, the method generates new ROI crops by perturbing each learned training ROI's horizontal and vertical position by up to 20 pixels, its scale by up to 0.2, and its rotation by up to 5 degrees. Ten perturbed examples are generated per original image; with 30 original images per category this adds 300 examples, for 330 training examples per category in total.

    On Caltech-256, adding these synthetic examples raises accuracy from 19.7% to 29.1% when training from five original images per class. With 30 original images per class, it raises accuracy from 43.5% to 45.3%, a 1.8-percentage-point increase. The results therefore show a larger benefit when the original training set is especially small.

Coverage note — The fine-grained sweeps over tree depth, number of node features, and tree ordering are omitted because they are secondary parameter diagnostics; the reported principal comparisons capture the main methodological and empirical contributions.

References

  1. 1.Y. Amit and D. Geman. Shape quantization and recognition with randomized trees. Neural Computation, 9:1545–1588, 1997.
  2. 2.Y. Amit, D. Geman, and K. Wilder. Joint induction of shape features and tree classifiers. IEEE PAMI, 19(11):1300–1305, 1997.
  3. 3.A. Berg, T. Berg, and J. Malik. Shape matching and object recognition using low distortion correspondence. CVPR, 2005.
  4. 4.A. Bosch, A. Zisserman, and X. Muñoz. Scene classification via plsa. ECCV, 2006.
  5. 5.A. Bosch, A. Zisserman, and X. Muñoz. Representing shape with a spatial pyramid kernel. CIVR, 2007.
  6. 6.L. Breiman. Random forests. Machine Learning, 45:5–32, 2001.
  7. 7.O. Chum and A. Zisserman. An exemplar model for learning object classes. CVPR, 2007.
  8. 8.G. Csurka, C. Bray, C. Dance, and L. Fan. Visual categorization with bags of keypoints. In Workshop on Statistical Learning in Computer Vision, ECCV, pages 1–22, 2004.
  9. 9.N. Dalal and B. Triggs. Histogram of oriented gradients for human detection. CVPR, 2005.
  10. 10.L. Fei-Fei, R. Fergus, and P. Perona. Learning generative visual models from few training examples: An incremental bayesian approach tested on 101 object categories. In IEEE CVPR Workshop of Generative Model Based Vision, 2004.
  11. 11.A. Frome, Y. Singer, and J. Malik. Image retrieval and classification using local distance functions. NIPS, 2006.
  12. 12.K. Grauman and T. Darrell. The pyramid match kernel: Discriminative classification with sets of image features. ICCV, 2005.
  13. 13.G. Griffin, A. Holub, and P. Perona. Caltech 256 object category dataset. Technical Report UCB/CSD-04-1366, California Institute of Technology, 2007.
  14. 14.A. Hegerath, T. Deselaers, and H. Ney. Patch-based object recognition using discriminatively trained gaussian mixtures. BMVC., 2006.
  15. 15.I. Laptev. Improvements of object detection using boosted histograms. BMVC., 2006.
  16. 16.S. Lazebnik, C. Schmid, and J. Ponce. Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories. CVPR, 2006.
  17. 17.V. Lepetit and P. Fua. Keypoint recognition using randomized trees. IEEE PAMI, 2006.
  18. 18.Y. Lin, T. Liu, and C. Fuh. Local ensemble kernel learning for object category recognition. CVPR, 2007.
  19. 19.D. Lowe. Distinctive image features from scale-invariant keypoints. IJCV, 60(2):91–110, 2004.
  20. 20.F. Moosmann, B. Triggs, and F. Jurie. Fast discriminative visual codebooks using randomized clustering forests. NIPS, 2006.
  21. 21.M. Ozuysal, P. Fua, and V. Lepetit. Fast keypoint recognition in ten lines of code. CVPR, 2007.
  22. 22.V. Perronnin, C. Dance, G. Csurka, and M. Bressan. Adapted vocabularies for generic visual categorization. ECCV, 2006.
  23. 23.J. Sivic and A. Zisserman. Video Google: A text retrieval approach to object matching in videos. ICCV, 2003.
  24. 24.J. Winn and A. Criminisi. Object class recognition at a glance. CVPR, 2006.
  25. 25.J. Winn and J. Shotton. The layout consistent random field for recognizing and segmenting partially occluded objects. CVPR, 2006.
  26. 26.H. Zhang, A. Berg, M. Maire, and J. Malik. SVM-KNN: Discriminative nearest neighbor classification for visual category recognition. CVPR, 2006.
  27. 27.J. Zhang, M. Marszałek, and C. Lazebnik, S. Schmid. Local features and kernels for classification of texture and object categories: a comprehensive study. IJCV, 2007.

Citation

MLA
Bosch, A., et al. “Image Classification Using Random Forests and Ferns”. 2007 IEEE 11th International Conference on Computer Vision, 2007, pp. 1–8, https://doi.org/10.1109/ICCV.2007.4409066.
APA
Bosch, A., Zisserman, A., & Munoz, X. (2007). Image Classification using Random Forests and Ferns. 2007 IEEE 11th International Conference on Computer Vision, 1–8. https://doi.org/10.1109/ICCV.2007.4409066
Chicago
Bosch, A., A. Zisserman, and X. Munoz. 2007. “Image Classification Using Random Forests and Ferns”. 2007 IEEE 11th International Conference on Computer Vision, 1–8. https://doi.org/10.1109/ICCV.2007.4409066.
Harvard
Bosch, A., Zisserman, A. and Munoz, X. (2007) “Image Classification using Random Forests and Ferns”, 2007 IEEE 11th International Conference on Computer Vision. IEEE, pp. 1–8. Available at: https://doi.org/10.1109/ICCV.2007.4409066.
Vancouver
1. Bosch A, Zisserman A, Munoz X (2007) Image Classification using Random Forests and Ferns. In: 2007 IEEE 11th International Conference on Computer Vision. IEEE, pp 1–8

BibTeX

@inproceedings{Bosch_2007, title={Image Classification using Random Forests and Ferns}, url={http://dx.doi.org/10.1109/ICCV.2007.4409066}, DOI={10.1109/iccv.2007.4409066}, booktitle={2007 IEEE 11th International Conference on Computer Vision}, publisher={IEEE}, author={Bosch, Anna and Zisserman, Andrew and Munoz, Xavier}, year={2007}, pages={1–8} }
Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: IEEE