Image Representation & Descriptors

After an image has been segmented into regions ; the resulting pixels is usually is represented and described in suitable form for further computer processing.

1. I mage Representation & Descriptors By Pundrik P atel (304) Hardik Prajapati (270) DEPARTMENT OF ELECTRICAL ENGINEERING FACULTY OF TECHNOLOGY AND ENGINEERING THE MAHARAJA SAYAJIRAO UNIVERSITY OF BARODA VADODARA,GUJARAT, INDIA

2. Introduction After an image has been segmented into regions ; the resulting pixels is usually is represented and described in suitable form for further computer processing. Representing regions incolves in to two choices: in terms of it’s 1) external characteristics ( boundary) 2) internal characteristics ( pixels) Above task is making data useful to computer Next task is to describe the region on bases of representation

3. External representation is chosen when primary focus on shape characteristics. Internal representation is chosen when primary focus on regionl properties like color and texture characteristics. Sometime it is possible to choose both characteristics. Features selected as descriptors should be insensitive to changes in size , tanslation & rotation.

4. Representation It deals with compaction of segmented data into representations that facilitate the computation of descriptors. Technique of Representation :- a. Chain codes b. Polygonal Approximations - Minimum perimeter polygones - Merging technique - Splitting technique c. Signatures d. Boundary Segments e. Skeletons

5. Chain codes They are used to represent a boundary by a connected sequence of straight line segments of specified length & direction. Typically this representation is based on 4- or 8- connectivity of segments. The direction of each segments is coded by using a numbering scheme. 1 3 2 2 1 3 4 5 6 7 4-connectivity 8-connectivity

6. A boundary code formrd as a sequence of such directional number is referred as a Freeman chain code. Digital images are acquired & processed in a grid format with equal spacing in x and y directions . So a chain code can be generated by following a boundary ( say clockwise direction) and assigning a direction to the segments connecting every pair of pixels . Unacceptable method : (because) 1 ) Resulting chain tends to be quite long 2 ) Any small disturbances along the boundary due to noise or imperfect segmentation can cause changes in code.

7. A solution to this problem is to resample the boundary by selecting a larger grid spacing . Then, as the boundary is traversed, a boundary point is assigned to each node of the large grid, depending upon the proximity of original boundary to that node . The re-sampled boundary can now be represented by a 4- or 8-code. The accuracy of the resulting code representation depends on the spacing of the sampling grid . Example:- Start Chain Code: 0, 0, 0, 3, 0, 0, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1

8. The chain code of a boundary depends upon the starting point. However the code can be normalized : – Assume the chain is a circular sequence ( given a chain of 1 to N codes ; N+1 = 1) – Redefine the starting point such that we generate an integer of smallest magnitude Chain Code 1 Chain Code 2 , 0, , 3, 0, 0, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1 3, 0, 0, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0   Normalized Code , 0, 0, 3, 0, 0, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1

9. Chain code depend on orientation – a rotation results in a different chain code One solution   – Use the “ first difference ” of the chain code instead of the code itself   The difference is obtained by simply counting (counter-clockwise) the number of directions that separate two adjacent elements 1 2 3 Difference : Count the number of separating directions inan anti-clockwise fashion 2 1 0 1 0 3 3 2 2 2 Chain Code 3 3 1 3 3 0 3 0 Difference Code Ex. First difference of 4-direction chain code 10103322 is 3133030. Considering the circular sequence first element is calculated by subtracting last and first component. Ex. 33133030

10. Polygon Approximation A digital boundary can be approximated with arbitrary accuracy by a polygon . For a closed boundary, approx becomes exact when no. of segments of polygon = no. of points in the boundary . Goal of poly. Approx is to capture the essence of the shape in a given boundary using fewest no. of segments.

11. Min. Perimeter Polygon (MPP): An approach for generating an algorithm to compute MPPs is to enclose a boundary by a set of concatenated cells . Allow the boundary to shrink as a rubber band. This shrinking produces the shape of a polygon of min. perimeter. Size of cells determine the accuracy of the polygonal approximation. In the limit if size of each cell corresponds to a pixel in the boundary , the error in each cell between the boundary & the MPP approx. at most would be √2d , where d-min possible pixel distance . The objective is to use the largest possible cell size acceptable in a given application . Thus, producing MPPs with fewest no. of vertices .

12. The cellular approach reduces the shape of the object enclosed by the original boundary. boundary enclose by cells Min. Perimeter Polygon

13. Merging Techniques Techniques based on average error or other criteria have been applied to the problem of polygonal approximation. One approach is to merge points along a boundary until the least square error line fit of the points merged so far exceeds a preset threshold. When this condition occurs, parameters of line are stored , the error is set to 0, the procedure is repeated, merging new points along the boundary until the error again exceeds the threshold . Merging technique problem : – No guarantee for corner detection Solution: – Splitting Techniques

14. Splitting Techniques to subdivide a segment successively into two parts until a given criterion is satisfied. – Objective: seeking prominent inflection points Step:- 1. Start with an initial guess, e.g., based on majority axes 2. Calculate the orthogonal distance from lines to all points 3. If maximum distance > threshold, create new vertex there 4. Repeat until no points exceed criterion

15. Example:-

16. Signature It is a 1D functional representation of a boundary & may be generated in various ways . One of the simplest is to plot the distance from the centroid to the boundary as a function of angle . Signatures generated by this method are invariant to translation but they depend on rotation and scaling . Normalization with respect to rotation can be achieved by finding a way to select the same starting point to generate the signature , according to shape. One way to normalize this is to scale all functions so that they always span the same range of values. e.g [0,1 ]

17. Advantage : - it’s simplicity disadvantage : - scaling of the entire function depends upon only two values: maximum & minimum.

18. Boundary segments The boundary can be decomposed into segments. – Useful to extract information from concave parts of the objects . A good way to achieve this is to calculate the convex Hull of the region enclosed by the boundary Hull. Can be a bit noise sensitive 1 . Smooth prior to Convex hull calculation 2 . Calculate Convex Hull on polygon approximation

19. Convex Hull, H, of an arbitrary set, S, is the smallest set containing S   H minus S (H-S) – Is called the convex deficiency   We can use the convex deficiency to mark features Follow the contour of S and mark points that transitions into or out of the convex deficiency

20. Using Convex Hull and its Deficiency     This data can be used to describe the region   – Number of pixels in convex deficiency   – Number of components in convex deficiency   – Ratio lengths of the transition points   – so on

21. Skeletons An important approach to represent the structural shape of a plane region is to reduce it to a graph . The reduction may be accomplished by obtaining the skeleton of the region via thinning ( skeletonizing ) algorithm . Skeleton of a region may be defined as the medial axis transformation (MAT ). MAT of a region R with border B is as follows : - For every point p in R , we find its closest neighbor in B . If p has more than such neighbor, it is said to belong to the medial axis (skeleton). ‘ prairie fire concept’

22. Implementation involves calculating the distance from every interior point to every boundary point on region . Thinning algorithm deals with deleting the boundary points of a region subject to condition that deleting these points : 1) Does not remove end points. 2 ) Does not break connectivity & 3 ) Does not cause excessive erosion of the region .

23. Thinning algorithm : Region points are assumed to have value 1 & background points are assumed to have value 0 . p9 p2 p3 p8 p1 p4 p7 p6 p5 Step 1 flags a contour point for deletion if the followingconditions are satisfied : a ) 2 ≤ N(p1) ≤ 6 b ) T(p1) = 1 c ) p2.p4.p6 = 0 d ) p4.p6.p8 = 0

24. where N(p1) is the number of nonzero neighbors of p1; i.e . N(p1) = p2 + p3 + …… + p8 + p9 where pi is either 0 or 1. T(p1 ) is number of 0-1 transitions in the ordered sequence p2 , p3, ….., p8, p9., p2 In Step 2: conditions a & b remain the same, but conditions c & d are changed to c ’) p2.p4.p8 = 0 d ’) p2.p6.p8 = 0 0 1 1 p1 0 1 1 Step 1 is applied to every border pixel in binary region under Consideration If 1 or more of conditions a to d are violated, the value of point in question is not changed .

25. If all conditions are satisfied, the point is flagged for deletion. But not deleted until all border points have been processed. This delay prevents the change of structure of data during execution of algorithm. After step 1 been applied to all border points, those who are flagged are deleted (changed to 0). Step 2 is applied to resulting data in exactly same manner as step1 .

26. Boundary Descriptors Some simple discriptors :- Length of the contour   – Simply count the number of pixels along the border – You may consider diagonally connected pixels to count as √2 Diameter of the boundary B   – Diam (B) = max[D( pi,pj )] – this is the major axis of the region Curvature – Rate of change of the slope Bounding Box – Smallest rectangle (aligned with the image axis) that can bound the region  

27. Shape number – compute the chain code difference – re-order this to create the minimum integer – this is called the shape number Example:-

28. Fourier Descriptors Consider an N-point digital boundary in the xy plane   This forms a coordinate pairs (xo, yo ), (x1, y2), . . . . ., (xn-1, yn-1 )   We can consider this as two vectors   – x(k) = xk   – y(k) = yk   Furthermore   – We could consider this a complex number – s(k) = x(k) + jy (k) where j= sqrt (-1)

29. Using the vector s(k)   Compute the 1-D Discrete Fourier Transform

30. Thank You