DOI: 10.1162/neco.1997.9.7.1545. Shape Quantization and Recognition with Randomized Trees

Shape Quantization and Recognition with Randomized Trees

10.1162/neco.1997.9.7.1545

Crossref journal-article

MIT Press - Journals

Neural Computation (281)

Abstract

We explore a new approach to shape recognition based on a virtually infinite family of binary features (queries) of the image data, designed to accommodate prior information about shape invariance and regularity. Each query corresponds to a spatial arrangement of several local topographic codes (or tags), which are in themselves too primitive and common to be informative about shape. All the discriminating power derives from relative angles and distances among the tags. The important attributes of the queries are a natural partial ordering corresponding to increasing structure and complexity; semi-invariance, meaning that most shapes of a given class will answer the same way to two queries that are successive in the ordering; and stability, since the queries are not based on distinguished points and substructures. No classifier based on the full feature set can be evaluated, and it is impossible to determine a priori which arrangements are informative. Our approach is to select informative features and build tree classifiers at the same time by inductive learning. In effect, each tree provides an approximation to the full posterior where the features chosen depend on the branch that is traversed. Due to the number and nature of the queries, standard decision tree construction based on a fixed-length feature vector is not feasible. Instead we entertain only a small random sample of queries at each node, constrain their complexity to increase with tree depth, and grow multiple trees. The terminal nodes are labeled by estimates of the corresponding posterior distribution over shape classes. An image is classified by sending it down every tree and aggregating the resulting distributions. The method is applied to classifying handwritten digits and synthetic linear and nonlinear deformations of three hundred [Formula: see text] symbols. State-of-the-art error rates are achieved on the National Institute of Standards and Technology database of digits. The principal goal of the experiments on [Formula: see text] symbols is to analyze invariance, generalization error and related issues, and a comparison with artificial neural networks methods is presented in this context. [Figure: see text]

Bibliography

Amit, Y., & Geman, D. (1997). Shape Quantization and Recognition with Randomized Trees. Neural Computation, 9(7), 1545â1588.

Authors 2

Yali Amit (first)
Donald Geman (additional)

References 25 Referenced 912

10.1162/neco.1989.1.1.151
10.1016/0031-3203(93)90060-A
10.1109/34.184774
10.1147/rd.274.0386
10.1109/TIT.1984.1056834
10.1613/jair.105
10.1109/34.99233
10.1109/TC.1977.1674849
10.1016/0031-3203(82)90024-3
10.1109/72.97912
10.1162/neco.1992.4.1.1
10.1073/pnas.93.2.615
10.1093/cercor/4.5.532
10.1109/72.165594
10.1214/aos/1176324456
10.1109/34.273711
10.1093/cercor/4.5.499
{'issue': '1', 'key': 'p_25', 'first-page': '218', 'volume': '73', 'author': 'Ito M.', 'year': '1995', 'journal-title': 'J. Neuroscience'} / J. Neuroscience by Ito M. (1995)
10.1109/72.165597
10.1162/neco.1991.3.2.258
10.1038/379728a0
10.1162/neco.1996.8.4.819
10.1007/BF00116251
10.1016/S0893-6080(05)80144-3
10.1016/0031-3203(90)90098-6

Dates

Type	When
Created	19 years, 2 months ago (May 29, 2006, 11:25 a.m.)
Deposited	4 years, 5 months ago (March 12, 2021, 4:34 p.m.)
Indexed	1 day, 19 hours ago (Aug. 23, 2025, 9:25 p.m.)
Issued	27 years, 10 months ago (Oct. 1, 1997)
Published	27 years, 10 months ago (Oct. 1, 1997)
Published Print	27 years, 10 months ago (Oct. 1, 1997)

Funders 0

None

BibTeX

@article{Amit_1997, title={Shape Quantization and Recognition with Randomized Trees}, volume={9}, ISSN={1530-888X}, url={http://dx.doi.org/10.1162/neco.1997.9.7.1545}, DOI={10.1162/neco.1997.9.7.1545}, number={7}, journal={Neural Computation}, publisher={MIT Press - Journals}, author={Amit, Yali and Geman, Donald}, year={1997}, month=oct, pages={1545–1588} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        8,
        24
      ]
    ],
    "date-time": "2025-08-24T01:25:16Z",
    "timestamp": 1755998716153
  },
  "reference-count": 25,
  "publisher": "MIT Press - Journals",
  "issue": "7",
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        1997,
        10,
        1
      ]
    ]
  },
  "abstract": "<jats:p> We explore a new approach to shape recognition based on a virtually infinite family of binary features (queries) of the image data, designed to accommodate prior information about shape invariance and regularity. Each query corresponds to a spatial arrangement of several local topographic codes (or tags), which are in themselves too primitive and common to be informative about shape. All the discriminating power derives from relative angles and distances among the tags. The important attributes of the queries are a natural partial ordering corresponding to increasing structure and complexity; semi-invariance, meaning that most shapes of a given class will answer the same way to two queries that are successive in the ordering; and stability, since the queries are not based on distinguished points and substructures. </jats:p><jats:p> No classifier based on the full feature set can be evaluated, and it is impossible to determine a priori which arrangements are informative. Our approach is to select informative features and build tree classifiers at the same time by inductive learning. In effect, each tree provides an approximation to the full posterior where the features chosen depend on the branch that is traversed. Due to the number and nature of the queries, standard decision tree construction based on a fixed-length feature vector is not feasible. Instead we entertain only a small random sample of queries at each node, constrain their complexity to increase with tree depth, and grow multiple trees. The terminal nodes are labeled by estimates of the corresponding posterior distribution over shape classes. An image is classified by sending it down every tree and aggregating the resulting distributions. </jats:p><jats:p> The method is applied to classifying handwritten digits and synthetic linear and nonlinear deformations of three hundred [Formula: see text] symbols. State-of-the-art error rates are achieved on the National Institute of Standards and Technology database of digits. The principal goal of the experiments on [Formula: see text] symbols is to analyze invariance, generalization error and related issues, and a comparison with artificial neural networks methods is presented in this context. </jats:p><jats:p> [Figure: see text] </jats:p>",
  "DOI": "10.1162/neco.1997.9.7.1545",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2006,
        5,
        29
      ]
    ],
    "date-time": "2006-05-29T15:25:35Z",
    "timestamp": 1148916335000
  },
  "page": "1545-1588",
  "source": "Crossref",
  "is-referenced-by-count": 912,
  "title": "Shape Quantization and Recognition with Randomized Trees",
  "prefix": "10.1162",
  "volume": "9",
  "author": [
    {
      "given": "Yali",
      "family": "Amit",
      "sequence": "first",
      "affiliation": [
        {
          "name": "Department of Statistics, University of Chicago, Chicago, IL, 60637, U.S.A."
        }
      ]
    },
    {
      "given": "Donald",
      "family": "Geman",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Department of Mathematics and Statistics, University of Massachusetts, Amherst, MA 01003, U.S.A."
        }
      ]
    }
  ],
  "member": "281",
  "reference": [
    {
      "key": "p_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1162/neco.1989.1.1.151"
    },
    {
      "key": "p_6",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0031-3203(93)90060-A"
    },
    {
      "key": "p_7",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/34.184774"
    },
    {
      "key": "p_8",
      "doi-asserted-by": "publisher",
      "DOI": "10.1147/rd.274.0386"
    },
    {
      "key": "p_9",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/TIT.1984.1056834"
    },
    {
      "key": "p_11",
      "doi-asserted-by": "publisher",
      "DOI": "10.1613/jair.105"
    },
    {
      "key": "p_12",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/34.99233"
    },
    {
      "key": "p_13",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/TC.1977.1674849"
    },
    {
      "key": "p_14",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0031-3203(82)90024-3"
    },
    {
      "key": "p_15",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/72.97912"
    },
    {
      "key": "p_18",
      "doi-asserted-by": "publisher",
      "DOI": "10.1162/neco.1992.4.1.1"
    },
    {
      "key": "p_19",
      "doi-asserted-by": "publisher",
      "DOI": "10.1073/pnas.93.2.615"
    },
    {
      "key": "p_20",
      "doi-asserted-by": "publisher",
      "DOI": "10.1093/cercor/4.5.532"
    },
    {
      "key": "p_21",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/72.165594"
    },
    {
      "key": "p_22",
      "doi-asserted-by": "publisher",
      "DOI": "10.1214/aos/1176324456"
    },
    {
      "key": "p_23",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/34.273711"
    },
    {
      "key": "p_24",
      "doi-asserted-by": "publisher",
      "DOI": "10.1093/cercor/4.5.499"
    },
    {
      "issue": "1",
      "key": "p_25",
      "first-page": "218",
      "volume": "73",
      "author": "Ito M.",
      "year": "1995",
      "journal-title": "J. Neuroscience"
    },
    {
      "key": "p_29",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/72.165597"
    },
    {
      "key": "p_34",
      "doi-asserted-by": "publisher",
      "DOI": "10.1162/neco.1991.3.2.258"
    },
    {
      "key": "p_37",
      "doi-asserted-by": "publisher",
      "DOI": "10.1038/379728a0"
    },
    {
      "key": "p_38",
      "doi-asserted-by": "publisher",
      "DOI": "10.1162/neco.1996.8.4.819"
    },
    {
      "key": "p_39",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF00116251"
    },
    {
      "key": "p_42",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/S0893-6080(05)80144-3"
    },
    {
      "key": "p_44",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0031-3203(90)90098-6"
    }
  ],
  "container-title": "Neural Computation",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://www.mitpressjournals.org/doi/pdf/10.1162/neco.1997.9.7.1545",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2021,
        3,
        12
      ]
    ],
    "date-time": "2021-03-12T21:34:30Z",
    "timestamp": 1615584870000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://direct.mit.edu/neco/article/9/7/1545-1588/6116"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1997,
        10,
        1
      ]
    ]
  },
  "references-count": 25,
  "journal-issue": {
    "issue": "7",
    "published-print": {
      "date-parts": [
        [
          1997,
          10,
          1
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1162/neco.1997.9.7.1545"
  ],
  "URL": "http://dx.doi.org/10.1162/neco.1997.9.7.1545",
  "relation": {},
  "ISSN": [
    "0899-7667",
    "1530-888X"
  ],
  "subject": [],
  "container-title-short": "Neural Computation",
  "published": {
    "date-parts": [
      [
        1997,
        10,
        1
      ]
    ]
  }
}