Vector Algebra Based Tracing of External and Internal Boundary of an Object in Binary Images

The present work details an algorithm using vector algebra for tracing a boundary of a binary pattern. More specifically, the paper provides a theoretical framework for boundary tracing and provides a basis for boundary tracing task. Core concept in the present work is the idea of seeking minimum angle between a vector formed by present and previous boundary locations, and the vectors formed by present and next possible boundary locations, using vector algebra. The proposed algorithm uses both cross and dot product for the choice of the minimum angle. This algorithm overcomes the drawbacks of heuristic approaches and provides a complete solution to the tracing problem. These include solutions taking into account a variety of contour possibilities external or internal on one hand and open or closed on the other, and the combinations thereof.

Use of sound mathematical basis in this tracing algorithm can avoid the drawbacks inherent in heuristic approaches. The paper includes proof for this algorithm providing 100% sensitivity and completeness. The trial runs performed on more than 1300 test images yielded a set of ordered boundary pixels 100% of the time.