Apparatus, method, and medium for dividing regions by using feature points and mobile robot using the same

• US 8,326,019 B2
• Filed: 03/17/2011
• Issued: 12/04/2012
• 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, Lee, Yong-beom, Bang, Seok-won
• Primary Examiner(s): Lu, Tom Y
• Assistant Examiner(s): CONWAY, THOMAS A
• Application Number:
  US13/050,459
• Publication Number:
  US 20110211731A1
• Time in Patent Office: 628 Days
• Field of Search: None
• US Class Current: 382/153
• 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, wherein the forming of the final region comprises separating a smaller region from a larger region when the smaller region formed of the closed curve is included in the larger region formed of the closed curve and the area difference between the smaller region and the larger region exceeds a predetermined range.

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 of the feature points comprises extracting the feature points by using a RANSAC (random sample consensus) algorithm.

4. 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.

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

6. 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.

7. The method of claim 1, wherein the forming of the final region comprises pruning a critical line forming the smaller region when the smaller region formed of the closed curve is included in the larger region formed of the closed curve and the area difference between smaller region and the larger region is within a predetermined range.

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

9. The method of claim 1, wherein the forming of the final region comprises pruning a critical line forming the smaller region when the smaller region formed of the closed curve is included in the larger region formed of the closed curve and the area difference between the smaller region and the larger region is within a predetermined range.

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

11. 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.

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

13. 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.

14. The method of claim 13, 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.

15. The method of claim 14, 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.

16. The method of claim 13, 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.

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

18. The method of claim 13, 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.

19. The method of claim 18, 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.

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

21. The method of claim 18, 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.

22. The method of claim 21, 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.

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

24. 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, wherein the region forming unit separates a smaller region from a larger region when the smaller region formed of the closed curve is included in the larger region formed of the closed curve and the area difference between the smaller region and the larger region exceeds a predetermined range.

25. The apparatus of claim 24, 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.

26. The apparatus of claim 24, 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 feature 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.

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

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

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

30. The apparatus of claim 24, 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 an 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 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 24, 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.

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

34. The apparatus of claim 24, wherein the forming of the final region prunes a critical line forming the smaller region when the smaller region formed of the closed curve is included in the larger region formed of the closed curve and the area difference between the smaller region and the larger region is within a predetermined range.

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

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

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

38. The apparatus of claim 24, wherein the forming of the final region prunes a critical line forming the smaller region when the smaller region formed of the closed curve is included in the larger region of the closed curve and the area difference between the smaller region and the larger region is within a predetermined range.

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

40. The apparatus of claim 24, wherein the apparatus is part of a mobile robot.

41. The apparatus of claim 40, wherein the mobile robot is a cleaning robot.

42. The apparatus of claim 24, wherein the pairs of final feature points extracting unit extracts the pairs of final feature points, and wherein when a line connecting any pair of feature points overlaps with the grid map, the pair of feature points pertaining to the line is excluded from the extracted pairs of final feature points.

43. The apparatus of claim 42, 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.

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

45. The apparatus of claim 42, wherein the pairs of final feature points extracting unit extracts the pairs of final feature points, and wherein when any pair of feature points is not included in the grid map, the pair of feature points not included in the grid map are excluded from the extracted pairs of final feature points.

46. The apparatus of claim 45, 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.

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

48. 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;

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, wherein the region forming unit separates a smaller region from a larger region when the smaller region formed of the closed curve is included in the larger region formed of the closed curve and the area difference between the smaller region and the larger region exceeds a predetermined range.

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

50. The mobile robot of claim 48, 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.

51. The mobile robot of claim 48, further comprising pairs of candidate feature points extracting unit to extract a pair of feature points, which are included in a distance range of 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.

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

53. The mobile robot of claim 52, 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.