Identifying All Matches of a Rigid Object in an Input Image Using Visible Triangles

It has been suggested that for objects identifiable by their corners, every triangle formed by these corner points can serve as a reference for detecting other corner points. This approach enables effective rigid object detection, including partial matches. However, when there are many corner points, the implementation becomes impractical due to excessive memory requirements. To overcome this, we propose a new algorithm that leverages Delaunay triangulation, considering only the triangles generated by the Delaunay triangulation to reduce the complexity of the original approach. Our algorithm is significantly faster and requires significantly less memory, offering a viable solution for large problem instances. Moreover, it excels at identifying all matches of a queried object in an image when visible triangles of the object are present. A triangle formed by an object’s vertices is considered visible if a matching triangle is detected, and no vertices from any other object lie within its circumcircle. Recent AI-based methods have revolutionized rigid object matching, providing impressive accuracy with deep learning techniques. However, these methods require extensive training and specialized hardware like GPUs. In contrast, our approach requires no training or specialized hardware, making it a lightweight and efficient solution that maintains strong matching capabilities without the overhead of AI-based methods. Our study of the geometric features, combined with Delaunay triangulation, offers new mathematical insights.