Fast Automated Object Detection Using Signature Parsing
Tim Heaton, Shawn Becker, Kelley Anderson, William A. Barrett · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1990
A fast algorithm is described which makes use of image signatures or profiles for automated object detection. Following segmentation, signatures are generated with respect to both axes and transition points are marked to separate the signature into bands. The intersections of the bands define rectangular regions (subimages) which may contain objects or groups of objects. Signature parsing is repeated for each subimage until single band intersections are produced at which point each object is naturally bounded by the band limits. Recursive decomposition of the image in this manner allows fast location of objects and calculation of object parameters while avoiding pixel level processing. The output of the algorithm is a two-dimensional spatial object relationship tree (SORT) which contains a high-level hierarchical description of the spatial interrelationships between objects and groups of objects. The SORT provides a powerful tool for scene matching and can be used to distribute subimages (nodes) to multiple processors. The algorithm has been used for efficient detection of objects and their locations in picking and placing tasks with a (PC) compute time of 1-2 seconds for a typical image.