Rotation Invariant Point Set Matching Technique in Clutter Scenes

Rotation Invariant Point Set Matching Technique in Clutter Scenes

Sapna. S. M

Research Scholar,Dept of EC&E, GMIT Davanagere, India.

Email id: coolsapna2008@gmail.com

Manjula. B. K

Asst professor, DeptOf EC&E, GMIT Davanagere, India.

Email id: manjulasuresp9@gmail.com

Abstract: This paper addresses the problem of rotation-invariant non-rigid point set matching. The shape context (SC) feature descriptor is used because of its strong discriminative nature, whereas edges in the images are constructed by point sets are used to determine the orientations of shape context. Similar to lengths or directions, oriented SCs constructed this way can be regarded as attributes of edges. By matching edges between two point sets, rotation invariance is achieved. Two novel ways of constructing graphs on a model point set are proposed, aiming at making the orientations of SCs as robust to disturbances as possible. The structures of these graphs facilitate the use of dynamic programming (DP) for optimization. The strong discriminative nature of SC, the special structure of the model graphs, and the global optimality of DP make our methods robust to various types of disturbances, particularly clutters. The extensive experiments on both synthetic and real data validated the robustness of the proposed methods to various types of disturbances. They can robustly detect the desired shapes in complex and highly cluttered scenes.

Keywords: Rotation, Object Segmentation, Point Set Matching, Clustered Scenes

1. Introduction

   Point matching is a fundamental yet challenging problem in computer vision, pattern recognition and medical image analysis, while non-rigid point matching is particularly difficult due to the large number of possible non-rigid transformations of the template [1]. In this paper, we will address the following problem under the non-rigid point matching framework: locating a deformable shape in cluttered scenes. The shape may undergo arbitrary translational and rotational changes, and it may be non-rigidly deformed, occluded and corrupted by random or structured outliers. All these difficulties make shape matching a formidable task. To overcome these problems, different methods have been proposed [2], which

   can be classified as those based on local search and those based on global search.

   Methods based on local search. The Iterated Closest Point (ICP) method [3-4] uses the closest points as the matched points, and it has variants [5- 6]. The Robust Point Matching (RPM) method [1] uses deterministic annealing [7] to recover a continuously relaxed point correspondence. The method in [8] uses constraint projection based on quadratic programming to gradually recover the point correspondence and uses clustering for speedup. The Covariance Driven Correspondence (CDC) method [9] uses the covariance of the transformation. Parameters to prune the possible false point correspondences. The methods in [10, 11] convert point set registration to an image registration problem. These local search methods are generally not rotation invariant and not robust to strong outlier disturbances. Methods based on global search. These methods can be further classified as those based on spatial mapping and those based on point correspondence. For the first category, solution space searching techniques such as genetic algorithm [12], particle filtering [11] and particle swarm optimization [12] can be used to recover the transformation. These methods need no initial coarse alignment and are robust against clutter, but they require an explicit modeling of the transformation and may become computationally expensive when the number of transformation parameters becomes high, which makes them unsuitable for non-rigid matching. The method in

   [1] constructs a global convex approximation to the matching function and thus the transformations can be optimally recovered. But the number of constraints for the method is usually very high which is circumvented by using interior point methods. For the second category, linear programming was employed in [6, 7] to minimize both the feature matching cost and geometric distortion. Ant colony optimization was employed in [18] for contour correspondence. Dynamic programming (DP) was used to match chain-like or tree-like structures in [9, 10]. In [2], it was extended to match regions of a shape. Belief

   propagation was used in [2] to match shapes where shapes with loops or holes are allowed. Shape context (SC) [3] is a very informative feature descriptor. The SC of a point is a measure of the distribution of other points relative to it. SC is very discriminative and quite robust to various types of disturbances, which makes it especially useful for non-rigid point matching. However, SC is rotation variant in most applications (i.e. no significant rotations are allowed between two point sets). Attempts at making SC rotation invariant are either susceptible to noise, tend to degrade the discriminative power of SC (e.g. tangent directions were used to determine the orientations of SCs in [2,3], distance between two SCs was rendered rotation invariant by traversing all rotated versions of one of them and retaining the minimum distance in [11] ) or imposing unnatural requirements on point sets (e.g. the directions pointed at the mass center of a point set were used as the orientations of SCs in [4]) We propose in this paper a new approach to representing point set and apply it to rotation invariant non-rigid point matching. A shape is triangulated such that the non-boundary edges are long enough and also DP can be used to find the best embedding of the triangles in target point set. Then SC features are constructed for vertices of the triangles whose orientations coincide with the directions of non-boundary edges. The SC features constructed in this way are therefore rotation invariant. To further improve our methods robustness to outliers, we modify the original SC distance measure in [3] such that the SC input belonging to the template is used as a mask to reduce the influence of outliers on the SC input belonging to the target. Compared with previous attempts at enabling SC rotation invariant, our approach retains the discriminative power of SC, is robust to orientation disturbances and appears natural. It shares similarities with the method in [2] in that both approaches use triangulation to represent shapes and DP is used to find the best embedding of triangles in target set. However, the method in [1] is for deformable template matching in images, and the purpose of triangulation is to introduce non-rigid deformation in template (constrained Delaunay triangulation is adopted to achieve the maximum effect). In comparison, the purpose of triangulation in our method is to render SC rotation invariant, where a different Triangulation approach is adopted with the aim that the orientations of SCs should be as robust to disturbances as possible.

2. Methods Used

   1. Point Set Representation

      Here point set can be represented by using the built in function canny. Using this function we get the intensity of the image means it gives the edge point

      of the inputted image then those points are grouped by using the classification algorithm to produce the exact picture of the given image. classification algorithm can make groups by using the different following algorithms such as MST in MST first it finds the edge points then it applies the distance of each point then which point is nearest that will make a solid connection between those points then make a angle between those point then only obtained the pint set representation of given image by using the MST algorithm.

   2. Star Graph for Point Set Matching

   If no speedup measure is taken, the time complexity will be O (nm3), which is relatively high. Therefore it will be of great interest if we could simplify the algorithm so that the time complexity can be reduced without sacrificing much the accuracy. Fortunately, this is possible. Due to the strong discriminative nature of SC, the frame edges with SCs acting as attributes in MST induced triangulation are already adequate to form a strong constraint on the shape of X.

3. Experimental Result

   The below fig shows the experimental results of different algorithms

   Fig. 1: Original Image of Fish

   Fig. 1 gives the input for MST, SC and SG algorithms. The below fig. 2 shows the output of the different algorithms grouping may vary from one algorithm to another as show below fig. 2 and fig. 3

   Fig. 2: Result of MST Algorithm

   From the above fig. 2 shows the how the classification of the point has been done by using the MST algorithm.

   From the fig. 3 the classification of the points can be done by using the SG algorithm

   Fig. 3: Result of SG Algorithm

   From the above fig. 3 can be recognized clustering of the different points to group of the fish body clustering can be done by using the nearest neabauring or distance matrices algorithm which points are nearest to center points those points are grouped into a single cluster as showed above fig. 3.

   Fig. 4: Comparison of the Outlier and the Error

   From the above fig. 4 shows the outlier and the error produced by the different classifier algorithms such as MST, LP, VA, FST and SG.

   Fig. 5: Average Error of Different Algorithm

   From the above fig. 5 average error of MST, SG, FST and LP algorithms with lamda value is one using these algorithms makes a different groups or cluster with the lamda value is one.

   From the average error of different algorithms we can conclude that MST algorithm performs the best compares the others, SG algorithm performs the almost similar to LP algorithm as shown above fig. 5.

4. Acknowledgement

   With great pleasure and gratefulness, I extend my deep sense of gratitude to Mrs. Manjula. B.K, Asst. Prof, GMIT, Davanagere for giving me an opportunity to accomplish my dissertation under her guidance and to increase my knowledge. Lastly I wish to thank my HOD Prof. D. Basavalingappa and Principal Dr. S.G. Hiremath GMIT, Davanagere for my dissertation successful.

   Thank You.

5. Conclusion

To address the problem of rotation invariant non rigid point set matching, we proposed two methods for shape representation. The Shape Context (SC) feature descriptor was used and we constructed graphs on point sets where edges are used to determine the orientations of SCs. This enables the proposed methods rotation invariant. The structures of our shape representations facilitate the use of DP for optimization. The strong discriminative nature of SC, the calculated robust orientations of SCs, and the global optimality of DP make our methods robust to various types of disturbances, particularly clutters. The proposed methods were tested on both synthetic and real data in comparison with several representative methods.

The results show that our methods, especially MSTT, clearly outperform other methods in terms of robustness against clutter. The proposed methods are very useful for tasks involving detection and matching of shapes in cluttered scenes where the initial poses of the shapes may not be known.

REFERENCES

1. Neelambike S, Comparison of K-mean and Fuzzy K-mean algorithms for color image segmentation, international journal of computer science and information technology,

   ISSN:0975-9646

2. Neelambike S, Effective generation of clusters for gene data, COMPUSOFT, An international journal of advanced computer technology, 2 (8), Aug-2013 (Volume-II, Issue- VIII), ISSN:2320-

3. Lian and L. Zhang, Rotation invariant non-rigid shape matching in cluttered scenes, in European Conference on Computer Vision, 2010.0780

4. R. C. Veltkamp and M. Hagedoorn, State of the art in shape matching, in Principles of visual information retrieval. London, UK: Springer-Verlag, 2001, pp. 87119.

5. S. Belongie, J. Malik, and J. Puzicha, Shape matching and object recognition using shape contexts, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 24, no. 4, pp. 509522, 2002.

6. D. G. Lowe, Distinctive image features from scale-invariant keypoints, International Journal of Computer Vision, 2004.

7. W. Cheung and G. Hamarneh, N-sift: N-dimensional scale invariant feature transform, IEEE Trans. Image Processing.

8. K. Mikolajczyk and C. Schmid, A performance evaluation of local descriptors, IEEE Trans. Pattern Anal. Mach. Intell., vol. 27, no. 10, pp. 16151630, 2005.

9. Z. Chen and S.-K. Sun, A zernike moment phase-based descriptor for local image representation and matching, IEEE Trans. Image Processing, vol. 19, no. 1, pp. 205219, 2010.

10. H. Jiang and S. X. Yu, Linear solution to scale and rotation invariant object matching, in IEEE Conf. Computer Vision and Pattern Recognition, 2009, pp. 2474 2481.

11. Y. Zheng and D. Doermann, Robust point matching for nonrigid shapes by preserving local neighborhood structures, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 28, no. 4, pp. 643649, 2006.

12. D. B. West, Introduction to graph theory, 2001, pearson Education, Inc. C. Godsil and G. Royle, Algebraic graph theory, 2001, springer-Verlag new York,Inc.