B- spline representation

• Representation of curves using piecewise polynomial interpolation to obtain smooth curves is widely used in computer graphics.

• B-splines are piecewise polynomial curves whose shape is closely related to

their control polygon - a chain of vertices giving a polygonal representation of a curve.

• B-splines of the third-order are most common because this is the lowest order which includes the change of curvature.

• Splines have very good representation properties and are easy to compute: o Firstly, they change their shape less then their control polygon, and do not oscillate between sampling points as many other representations do. A spline curve is always positioned inside a convex n+1-polygon for a B-spline of the n-th order.

o Secondly, the interpolation is local in character. If a control polygon vertex changes its position, a resulting change of the spline curve will occur only in a small neighborhood of that vertex.

o Thirdly, methods of matching region boundaries represented by

splines to image data are based on a direct search of original image data.

Fig 16: Splines of order n. (a),(b),(c) Convex n+1 polygon for a B-spline of the nth order. (d) 3rd order spline.

• Each part of a cubic B-spline curve is a third-order polynomial, meaning that it and its first and second derivatives are continuous. B-splines are given by

Other contour-based shape description approaches

• Many other methods and approaches can be used to describe two- dimensional curves and contours.

• The Hough transform has excellent shape description abilities.

• Region-based shape description using statistical moments is covered below.

• Fractal approach to shape is gaining attention in image shape description.

• Mathematical morphology can be used for shape description, typically in connection with region skeleton construction.

• Neural networks can be used to recognize shapes in raw boundary representations directly. Contour sequences of noiseless reference shapes are used for training, and noisy data are used in later training stages to increase robustness; effective representations of closed planar shapes result.

Shape invariants

• Shape invariants represent a very active current research area in machine vision.

• Importance of shape invariance has been known for a long time however it is somewhat novel approach in machine vision.

• Invariant theory is not new and many of its principles were introduced in the nineteenth century.

• Shape descriptors discussed so far depend on viewpoint, meaning that object recognition may often be impossible as a result of changed object or observer position.

• The role of shape description invariance is obvious -- shape invariants represent properties of such geometric configurations which remain unchanged under an appropriate class of transforms.

• Machine vision is especially concerned with the class of projective transforms.

Change of shape caused by a projective transform. The same rectangular cross section is represented by different polygons in the image plane.

• Collinearity is the simplest example of a projectively invariant image feature. Any straight line is projected as a straight line under any projective transform.

• Similarly, the basic idea of the projection-invariant shape description is to find such shape features that are unaffected by the transform between the object and the image plane.

• A standard technique of projection-invariant description is to hypothesize the pose (position and orientation) of an object and transform this object into a specific co-ordinate system; then shape characteristics measured in this co-ordinate system yield an invariant description.

• However, the pose must be hypothesized for each object and each image which makes this approach difficult and unreliable.

• Application of invariant theory, where invariant descriptors can be computed directly from image data without the need for a particular co- ordinate system, represents another approach.

• Let corresponding entities in two different co-ordinate systems be distinguished by large and small letters. An invariant of a linear transformation may be defined as:

o An invariant, I(P), of a geometric structure described by a parameter

vector P, subject to a linear transformation T of the co-ordinates x=TX, is transformed according to I(p)=I(P)|T|^w.

o Here I(p) is the function of the parameters after the linear transformation, and |T| is the determinant of the matrix T.

• In this definition, w is referred to as the weight of the invariant. If w=0, the invariants are called scalar invariants, which are considered below.

• Invariant descriptors are unaffected by object pose, by perspective projection, and by the intrinsic parameters of the camera.

• Several examples of invariants are now given.

Cross ratio:

• The cross ratio represents a classic invariant of a projective line.

• A straight line is always projected as a straight line. Any four collinear points A,B,C,D may be described by the cross-ratio invariant

where (A-C) represents the distance between points A and C(Fig 17). Note that the cross ratio depends on the order in which the four collinear points are labeled.

Fig 17: Cross ratio; four collinear points form a projective invariant.

Systems of lines or points

• A system of four general coplanar lines forms two invariants .

• If the three lines forming the matrix Mijk are concurrent, the matrix becomes singular and the invariant is undefined.

• A system of five coplanar points is dual to a system of five lines and the same two invariants are formed. These two functional invariants can also be formed as two cross ratios of two coplanar concurrent line quadruples (Fig 18).

• Note that even though combinations other than those given in Figure may be formed, only the two presented functionally independent invariants exist.

Fig 18: Five co-planar points form two cross-ratio invariants. (a) Co-planar points (b) Five points form a system of four concurrent lines (c) The same five points form another system of four co-planar lines

Plane conics:

• A plane conic may be represented by an equation

• For any conic represented by a matrix C, and any two coplanar lines not tangent to the conic, one invariant may be defined

• The same invariant can be formed for a conic and two coplanar points.

• Two invariants can be determined for a pair of conics represented by their respective matrices C_1, C_2 normalized so that |C_i|=1

• Two plane conics uniquely determine four points of intersection, and any point that is not an intersection point may be chosen to form a five-point system together with the four intersection points.

o Therefore, two invariants exist for the pair of conics, as for the five- point system.

Many man-made objects consist of a combination of straight lines and conics, and these invariants may be used for their description.

However, if the object has a contour which cannot be represented by an algebraic curve, the situation is much more difficult.

• Differential invariants can be formed (e.g. curvature, torsion, Gaussian curvature) which are not affected by projective transforms.

• These invariants are local - that is, the invariants are found for each point on the curve, which may be quite general.

• Unfortunately, these invariants are extremely large and complex polynomials, requiring up to seventh derivatives of the curve, which makes them practically unusable due to image noise and acquisition errors, although noise-resistant local invariants are beginning to appear.

• However, if additional information is available, higher derivatives may be

avoided.

• Stability of invariants is another crucial property which affects their applicability. The robustness of invariants to image noise and errors introduced by image sensors is of prime importance, although not much is known about this.

• Different invariants have different stability and distinguishing powers.

• The recognition system is based on a model library containing over thirty object models - significantly more than that reported for other recognition systems.

• Moreover, the construction of the model library is extremely easy; no special measurements are needed, the object is digitized in a standard way and the projectively invariant description is stored as a model.

o Further, there is no need for camera calibration. The recognition

accuracy is 100% for occluded objects viewed from different viewpoints if the objects are not severely disrupted by shadows and specularities.

Fig 19: Object recognition based on shape invariants. (a) Original image of overlapping objects taken from an arbitrary viewpoint. (b) Object recognition based on line and conic invariants.