Improvement of Retrieval Speed and Required Amount of Memory for Geometric Hashing by Combining Local Invariants

Thegeometrichashing(GH) is a well-knownmodel-basedobject recognition techniquewith goodpropertiesbothin retrievalspeedandrequiredamountof memory. However, it has a significant weak point; as the number of objects increases, both retrieval speed and required amount of memory increase in the cubic, fourth or higher order. Recently, a new technique “locally likely arrangement hashing (LLAH)” whose computational cost is a linear order has been proposed. The objective of the current paper is to reveal how LLAH improves the performance. By comparing GH and LLAH, we describe four primary factors of the performance improvement.