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

• US 7,916,931 B2
• Filed: 07/05/2007
• Issued: 03/29/2011
• Est. Priority Date: 07/05/2006
• Status: Expired due to Fees

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Myeong, Hyeon, Bang, Seok-won, Lee, Su-jinn, Lee, Yong-beom
• Primary Examiner(s): Lu; Tom Y
• Assistant Examiner(s): Conway; Thomas A
• Application Number:
  US11/822,407
• Publication Number:
  US 20080273791A1
• Time in Patent Office: 1,363 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 pairs 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 distances from obstacles;

extracting feature points from the grid map;

extracting pairs of candidate feature points, included in a range of a region division element, from the feature points;

extracting pairs of final feature points, which satisfy requirements of the region division element, from the pairs of candidate 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 distances from obstacles 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. 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.

6. The method of claim 1, 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.

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

8. The method of claim 1, 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 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.

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

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

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

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

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

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

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

18. The method of claim 1, 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 distances from obstacles;

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

pairs of candidate feature points extracting unit to extract pairs of feature points, which are included within a range of a region division element, from the feature points;

pairs of final feature points extracting unit to extract pairs of final feature points, which satisfy the requirements of the region division element, from the pairs of candidate 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.

25. The apparatus of claim 24, wherein the distances from obstacles are detected by using any one of infrared ray sensor, laser sensor, or supersonic wave sensor.

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

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

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

29. The apparatus of claim 28, 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.

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

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

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

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

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

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 regions formed of the closed curve are included with each other and the area difference between the regions 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 except that a line connecting the pair of feature points overlaps with the grid map.

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 except that a pair of feature points is not included in the grid map.

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 distances from obstacles;

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

pairs of candidate feature points extracting unit to extract pairs of feature points, which are included within a range of a region division element, from the feature points;

pairs of final feature points extracting unit to extract pairs of final feature points, which satisfy the requirements of the region division element, from the pairs of candidate 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;

a topological map forming unit to form a topological map on the basis of the final region; and

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.

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