APPARATUS, METHOD, AND MEDIUM FOR DIVIDING REGIONS BY USING FEATURE POINTS AND MOBILE ROBOT USING THE SAME

• US 20110211731A1
• Filed: 03/17/2011
• Published: 09/01/2011
• Est. Priority Date: 07/05/2006
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Lee, Su-Jinn, Myeong, Hyeon, Bang, Seok-won, Lee, Yong-beom
• Granted Patent: US 8,326,019 B2
• Time in Patent Office: Days
• US Class Current: 382/106
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G06V 20/52 Surveillance or monitoring of activities, e.g. for recognising suspicious objects recognising microscopic objects G06V20/69

Abstract

An apparatus, method, and medium for dividing regions by using feature points and a mobile robot cleaner using the same are provided. A method includes forming a grid map by using a plurality of grid points that are obtained by detecting distances of a mobile robot from obstacles; extracting feature points from the grid map; extracting candidate pairs of feature points, which are in the range of a region division element, from the feature points; extracting a final pair of feature points, which satisfies the requirements of the region division element, from the candidate pair of feature points; forming a critical line by connecting the final pair of feature points; and forming a final region in accordance with the size relationship between regions formed of a closed curve which connects the critical line and the grid map.

Claims

1. A method for dividing regions by using feature points, the method comprising:

forming a grid map by using a plurality of grid points that are obtained by detecting obstacles;

extracting feature points from the grid map;

extracting pairs of final feature points, which satisfy requirements of a region division element, from the feature points;

forming a critical line by connecting the pairs of final feature points to each other; and

forming a final region in accordance with the size relationship between regions having a closed curve formed by connecting the critical line and the grid map.

2. The method of claim 1, wherein, in the forming of the grid map, the grid points are obtained by detecting distances from the obstacles and the distances are detected by using any one of infrared ray sensor, laser sensor, or supersonic wave sensor.

3. The method of claim 1, wherein the extracting pairs of final feature points includes extracting candidate pairs of feature point, which are included in a distance range of the region division element, from the feature points, and the pairs of final feature points, which satisfy requirements of the region division element, are extracted from the pairs of candidate feature points.

4. The method of claim 3, wherein, in the extracting of the pairs of candidate feature points, a distance range of the region division element is set on the basis of a width of a gateway.

5. The method of claim 4, wherein the extracting of the pairs of candidate feature points from the feature points comprises extracting pairs of candidate feature points, which are included within the distance range set in consideration of noise due to interval between grid points in range of the width of the gateway.

6. The method of claim 3, wherein the extracting of the pairs of final feature points comprises extracting pairs of final feature points except that a line connecting the pair of feature points overlaps with the grid map.

7. The method of claim 6, wherein the extracting of the pairs of final feature points further comprises extracting pairs of final feature points except that a pair of feature points is not included in the grid map.

8. The method of claim 7, wherein the extracting of the pairs of final feature points further comprises extracting the pairs of final feature points, in which the length of a closed curve formed by connecting a line of the pair of feature points and the grid map is within a predetermined length range.

9. The method of claim 8, wherein the predetermined length range is set on the basis of the boundary of a room.

10. The method of claim 6, wherein the extracting of the pairs of final feature points further comprises extracting the pairs of final feature points, in which the length of a closed curve formed by connecting a line of the pair of feature points and the grid map is within a predetermined length range.

11. The method of claim 10, wherein the predetermined length range is set on the basis of the boundary of a room.

12. The method of claim 3, wherein the extracting of the pairs of final feature points further comprises extracting the pairs of final feature points, in which the length of a closed curve formed by connecting a line of the pair of feature points and the grid map is within a predetermined length range.

13. The method of claim 12, wherein the predetermined length range is set on the basis of the boundary of a room.

14. The method of claim 1, wherein the extracting of the feature points comprises extracting the feature points by using a RANSAC (random sample consensus) algorithm.

15. The method of claim 1, wherein the extracting of the feature points comprises extracting the feature points by using a SLAM (Simultaneous Localization And Map building) algorithm.

16. The method of claim 1, wherein the forming of the final region comprises separating a smaller region from a larger region when the regions formed of the closed curve are included with each other and the area difference between the regions exceeds a predetermined range.

17. The method of claim 16, wherein the predetermined range is set on the basis of half the area of the smallest region.

18. The method of claim 16, wherein the forming of the final region comprises pruning a critical line forming the smaller region when the regions formed of the closed curve are included with each other and the area difference between the regions is within a predetermined range.

19. The method of claim 18, wherein the predetermined range is set on the basis of half the area of the smallest room.

20. The method of claim 1, wherein the forming of the final region comprises pruning a critical line forming the smaller region when the regions formed of the closed curve are included with each other and the area difference between the regions is within a predetermined range.

21. The method of claim 20, wherein the predetermined range is set on the basis of half the area of the smallest region.

22. The method of claim 1, further comprising drawing a topological map on the basis of the final region that is formed in the forming of the final region.

23. The method of claim 22, further comprising displaying the topological map on a display device.

24. At least one non-transitory computer readable medium storing computer readable instructions that control at least one processor to implement the method of claim 1.

25. An apparatus for dividing regions by using feature points, the apparatus comprising:

a grid map forming unit to form a grid map by using a plurality of grid points that are obtained by detecting obstacles;

a feature point extracting unit to extract feature points from the grid map;

pairs of final feature points extracting unit to extract pairs of final feature points, which satisfy the requirements of a region division element, from the feature points;

a critical line forming unit to form a critical line by connecting the pairs of final feature points; and

a region forming unit to form a final region in accordance with the size relationship between the regions formed of a closed curve which connects the critical line and the grid map.

26. The apparatus of claim 25, wherein the grid points are obtained by detecting distance from the obstacles and the distances are detected by using any one of infrared ray sensor, laser sensor, or supersonic wave sensor.

27. The apparatus of claim 25, further comprising pairs of candidate feature points extracting unit to extract a pair of feature points, which are included in a distance range of the region division element, from the feature points,

wherein the pairs of final points extracting unit extracts the pairs of final feature points, which satisfy requirements of the region division element from the pairs of candidate feature points.

28. The apparatus of claim 25, wherein the feature points are extracted by using a RANSAC algorithm.

29. The apparatus of claim 25, wherein the feature points are extracted by using a SLAM (Simultaneous Localization And Map building) algorithm.

30. The apparatus of claim 25, wherein the range of the region division element, when the pairs of candidate feature points extracting unit extracts candidate pairs of feature points, is set on the basis of a width of a gateway.

31. The apparatus of claim 30, wherein the pairs of candidate feature points extracting unit extracts the pairs of candidate feature points, which are included within a distance range set in consideration of noise generated due to interval between grid points in range of the width of the gateway.

32. The apparatus of claim 25, wherein the pairs of final feature points extracting unit extracts the pairs of final feature points except that a line connecting the pair of feature points overlaps with the grid map.

33. The apparatus of claim 32, wherein the pairs of final feature points extracting unit extracts the pairs of final feature points except that a pair of feature points is not included in the grid map.

34. The apparatus of claim 33, wherein the pairs of final feature points extracting unit further extracts the pairs of final feature points, in which the length of a closed curve formed by connecting a line of the pair of feature points and the grid map is within a predetermined length range.

35. The apparatus of claim 34, wherein the predetermined range is set on the basis of the boundary of a room.

36. The apparatus of claim 32, wherein the pairs of final feature points extracting unit further extracts the pairs of final feature points, in which the length of a closed curve formed by connecting a line of the pair of feature points and the grid map is within a predetermined length range.

37. The apparatus of claim 36, wherein the predetermined range is set on the basis of the boundary of a room.

38. The apparatus of claim 25, wherein the pairs of final feature points extracting unit further extracts the pairs of final feature points, in which the length of a closed curve formed by connecting a line of the pair of feature points and the grid map is within a predetermined length range.

39. The apparatus of claim 38, wherein the predetermined range is set on the basis of the boundary of a room.

40. The apparatus of claim 25, wherein the region forming unit separates a smaller region from a larger region when the regions formed of the closed curve are included with each other and the area difference between the regions exceeds a predetermined range.

41. The apparatus of claim 40, wherein the predetermined range is set on the basis of half the area of the smallest region.

42. The apparatus of claim 25, wherein the forming of the final region prunes a critical line forming the smaller region when the regions formed of the closed curve are included with each other and the area difference between the regions is within a predetermined range.

43. The apparatus of claim 42, wherein the predetermined range is set on the basis of half the area of the smallest region.

44. The apparatus of claim 25, further comprising a topological map forming unit to form a topological map on the basis of the final region.

45. The apparatus of claim 44, further comprising a displaying unit to display the topological map on a display device.

46. The apparatus of claim 25, wherein the forming of the final region prunes a critical line forming the smaller region when the regions formed of the closed curve are included with each other and the area difference between the regions is within a predetermined range.

47. The apparatus of claim 46, wherein the predetermined range is set on the basis of half the area of the smallest region.

48. The apparatus of claim 25, wherein the apparatus is part of a mobile robot.

49. The apparatus of claim 48, wherein the mobile robot is a cleaning robot.

50. A mobile robot having an apparatus for dividing regions by using feature points, the apparatus comprising:

a grid map forming unit to form a grid map by using a plurality of grid points that are obtained by detecting obstacles;

a feature point extracting unit to extract feature points from the grid map;

pairs of final feature points extracting unit to extract pairs of final feature points, which satisfy the requirements of a region division element, from the feature points;

a critical line forming unit to form a critical line by connecting the pairs of final feature points; and

a region forming unit to form a final region in accordance with the size relationship between the regions formed of a closed curve which connects the critical line and the grid map.

51. The mobile robot of claim 50, further comprising a topological map forming unit to form a topological map on the basis of the final region.

52. The mobile robot of claim 51, further comprising a displaying unit to display the topological map on a display device,

wherein when a predetermined region of the topological map, which is recognizably displayed on the display device, is selected, the region is automatically cleaned.

53. The mobile robot of claim 50, wherein the mobile robot is a cleaning robot.

54. The mobile robot of claim 50, wherein the grid points are obtained by detecting distance from the obstacles and the distances are detected by using any one of infrared ray sensor, laser sensor, or supersonic wave sensor.

55. The mobile robot of claim 50, further comprising pairs of candidate feature points extracting unit to extract a pair of feature points, which are included in a distance range of the region division element, from the feature points,

wherein the pairs of final points extracting unit extracts the pairs of final feature points, which satisfy requirements of the region division element from the pairs of candidate feature points.