FORM-2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
PROVISIONAL
Specification
(See section 10 and rule 13)
METHOD AND APPARATUS FOR TRACING AT LEAST ONE BOUNDARY OF A PATTERN
I2IT PVT. LTD.,
an Indian Company
of 26-27 Mumbai-Pune Road, Pimpri, Pune 411018,
Maharashtra, India

THE FOLLOWING SPECIFICATION DESCRIBES THE INVENTION.

This invention relates to a method and apparatus for tracing at least one boundary of a pattern.
Systems for tracing of boundary are known in the prior art. These systems are typically disclosed in the following documents.
1) Apparatus for transforming a two-level image into contour vectors by decomposing composite figures into "unitary" (open) and closed-loop figures, especially suitable for minimizing memory use while maintaining system processing speed. United States Patent 5357602.
2) Apparatus for tracing contours of segmented regions. United States Patent 5757382.
3) Method and apparatus for extracting a contour of an image. United States Patent 5379350.
4) Method of and apparatus for extracting image contour data. United States Patent 5119439.
5) Contour tracing and boundary detection for object identification in digital image. US 6674904 Bl.
6) Method for contour extraction for object representation. US 6937765 B2.
These prior art are not adapted to utilize modern hardware features like multiply and accumulate units consequently they cannot be supported in field programmable gate array systems which can support multiple MAC units.


Therefore there is need for pattern recognition that makes use of these modem features which will increase the speed of computational pattern matching. Additionally, there is further need for recognizing patterns in real time and in an embedded system environment.
This invention therefore provides a method and apparatus for pattern recognition that makes use of modem hardware features like multiply and accumulate units these modern features which will increase the speed of computational pattern matching.
Additionally, this invention also provides a method and system for pattern recognition in real time and in an embedded system environment.
Additionally, this invention also provides a method and system for pattern recognition which will increase the speed of computational pattern matching.
The system and apparatus of this invention includes means to trace external boundary of a pattern which further includes means to :
1. Scan to locate a convex vertex.
2. Use the property of the convex vertex to get two pixel locations (starting and next) in the direction of tracing (clockwise or anticlockwise).
3. Current = starting.
4. Previous = current, current = next.
5. Seek minimum angle from current to previous vector in clockwise or anticlockwise fashion to locate nearest region pixel. Next = located


pixel location. (Note that the sense of rotation and the tracing are same.) 6. Repeat 4 and 5 till "next" not found or starting pixel location = next.
The invention further includes means to trace the internal boundary of a pattern to be recongnised having the following further means to:
1. Scan within external boundary to locate an internal background pixel.
2. Use the "proved property for 3x3 neighborhood" two pixel locations (starting and next) in the direction of tracing (clockwise or anticlockwise).
3. Current = starting.
4. Previous = current, current = next.
5. Seek minimum angle from current to previous vector in anticlockwise or clockwise fashion to locate nearest region pixel. Next = located pixel location. (Note that the sense of rotation and the tracing are opposite.)
6. Repeat 4 and 5 till "next" not found or starting pixel location = next.
The principal feature of the invention include :
1. Method and apparatus for locating the first two pixels in the direction of tracing, for the internal boundary tracing as well as the external boundary tracing.
2. Elements to "Seek minimum angle from current to previous vector" which can "find/ locate/ prioritize...minimum angle from current to previous ray/ vector/ (even at times) line". The located minimum angle can be in clockwise sense or anticlockwise sense. The


method in accordance with this invention can be implemented in multiple ways:
a. Using scalar and vector products.
b. Actual computation of angle. (Measure circular arc length or
area of circular sector of known radius).
c. Using trigonometry relations. (Like arctan or arcsin or arccos)
d. Using some transformation which amounts to indirect angle
computation e.g. look up table or priority table.
e. Any method or means that directly or indirectly prioritizes the
angle.
3. Sense (clockwise or anticlockwise) of "The minimum angle seeking" is opposite to that of tracing the internal boundary, where as it is same while tracing the external boundary.
1. The major innovation in this invention is
"that the method and apparatus iadapted to the use of vector
algebra techniques for determining the adjacent pixels
(iteratively and then) sequentially"; and
2. It is further adapted to compute the angle of at least one
next boundary pixel and establish an order between computed
angles iteratively.
The invention will now be described with reference to the accompanying drawings in which:
Figure 1 shows the Boundary Tracing Using Vector Algebra. Typically Figure 1 shows the Impact of the "starting pixel" and "direction of first


step" parameters on boundary tracing. The shaded pixels indicate the traced boundary pixels where as black pixels indicate remaining boundary and/or region pixels.
Figure 2 shows the pixels with a black square at the center are part of the object and the shaded pixel is the current pixel. CNVs are drawn from the current pixel to the next (probable) boundary pixels.
Figure 3 shows the impact of distribution of CNVs in a plane, (a) CNVs in a single half plane (b) CNVs in different half planes.
Figure 4 (a) illustrate the case of failure while using only cross product. And figure 4 (b) The result of cross product and dot product between CPV and
CNVs.
Figure 5 shows the case of priority assignment of pixels using sign of cross product and dot product between connectivity vectors and current to previous vector. The shaded pixel at the center is the current pixel. The solid arrows indicate connectivity vectors and dotted arrow indicates current to previous vector. The numbers indicate the priority assignment, with the lowest number having the highest priority.
Figure 6 shows the "internal boundary", "external boundary", "internal background" and "external background" in a closed contour, having a hole in it.


Figure 7 shows an example image of traced external and internal boundary the results for obtaining external and internal boundary, (a) Input image, (b) Traced external boundary, (c) Traced internal boundary.
Figure. 8. Shows a few of the test images and the obtained results of boundary tracing in accordance with this invention.
While considerable emphasis has been placed herein on the specific steps and elements of the preferred embodiment of the method and apparatus , it will be appreciated that many alterations can be made and that many modifications can be made in the preferred embodiment without departing from the principles of the invention. These and other changes in the preferred embodiment as well as other embodiments of the invention will be apparent to those skilled in the art from the disclosure herein, whereby it is to be distinctly understood that the foregoing descriptive matter is to be interpreted merely as illustrative of the invention and not as a limitation.