Method and system for automatically determining lines of sight between nodes

• US 20030218994A1
• Filed: 05/24/2002
• Published: 11/27/2003
• Est. Priority Date: 05/24/2002
• Status: Active Grant

• Current Assignee: Clearmesh Networks Incorporated
• Original Assignee: Omnilux, Inc.
• Inventors: Di Bernardo, Enrico, Goncalves, Luis, Caminiti, Lorenzo, Moursund, Carter
• Granted Patent: US 6,771,932 B2
• Time in Patent Office: Days
• US Class Current: 370/316
• CPC Class Codes: H04W 16/18 Network planning tools

Abstract

The present invention uses data from several sources to determine lines-of-sight between nodes in a FSO network. The present invention provides a three-dimensional neighborhood modeling system that uses aerial image data, Digital Elevation Models, U.S. street map data and address data to automatically map the placement of nodes within a neighborhood or other geographical area.

Method for creating the 3-Dimensional, House and Tree Maps used in the line-of-sight processing are also disclosed. A House Map in the present invention identifies houses in an area of consideration, and a Tree Map in the present invention identifies trees in an area of consideration. A 3-Dimensional Map in the present invention provides an elevation for every pixel for the area under consideration, whereby the elevation is adjusted for the height of trees, houses and other objects.

Claims

1. A method of determining line-of-sight configurations between a plurality of points in three-dimensional space, comprising the steps of:

(a) selecting a first point and a second point for processing;

(b) determining whether a valid, unobstructed line-of-sight exists between the first point and the second point;

(c) if a valid, unobstructed line-of-sight exists between the first point and the second point, recording information about the line-of-sight in a first database; and

(d) if a valid, unobstructed line-of-sight does not exist between the first point and the second point, determining whether an alternative placement of at least one point results in a valid, alternative unobstructed line-of-sight between the first point and the second point, and if a valid, alternative unobstructed line-of-sight does exist between the first point and the second point, recording information about the alternative line-of-sight in a second database;

repeating steps (a)-(d) for other combinations of points.

2. The method of claim 1, wherein the points are nodes in an infrared wireless system.

3. The method of claim 1, wherein step (b) comprises:

(i) determining a straight line between the first point and the second point;

(ii) determining whether the length of the straight line is less than a maximum link length;

(iii) determining whether the angle between the straight line and the vertical is less than a maximum vertical angle; and

(iv) if the length of the straight line is less than the maximum link length, and the vertical angle of the straight line is less than the maximum vertical angle, determining whether the straight line intersects with an obstruction in the three-dimensional space.

4. The method of claim 3, wherein step (b)(i) additionally comprises adding a margin to the straight line.

5. The method of claim 4, wherein said margin comprises a vertical margin and a horizontal margin.

6. The method of claim 4, wherein step (b)(iv) determines whether the straight line with the margin added intersects with an obstruction in the three-dimensional space.

7. The method of claim 3, wherein said maximum link length is a configurable parameter.

8. The method of claim 3, wherein said maximum vertical angle is a configurable parameter.

9. The method of claim 3, wherein step (b)(iv) comprises:

dividing the straight line into equally sized pixels in a 3-Dimensional Map;

determining each pixel'"'"'s elevation;

for each pixel, reading an adjusted terrain elevation from the 3-Dimensional Map for that pixel'"'"'s ground location and determining whether the pixel'"'"'s elevation is lower than the adjusted terrain elevation; and

if the elevation of any segment is lower than the adjusted terrain elevation at that pixel'"'"'s location, determining that the straight line intersects with an obstruction.

10. The method of claim 9, wherein the adjusted elevation of a location in the 3-Dimensional Map is the elevation of the terrain at that location adjusted by the height of an object at that location.

11. The method of claim 10, wherein the object is a building.

12. The method of claim 10, wherein the object is a tree.

13. The method of claim 1, wherein step (c) additionally comprises recording information about the straight line between the first point and the second point in the first database, if a valid, unobstructed line-of-sight does not exist between the first point and the second point.

14. The method of claim 1, wherein step (c) records information about the line-of-sight including first point identification, second point identification, location of the first point, location of the second point, elevation of the first point, elevation of the second point, and a field that records whether or not there is a valid unobstructed line-of-sight between the first point and the second point.

15. The method of claim 14, wherein the first point and second points are nodes in a communications system, and wherein information about a structure on which the first node resides and information about a structure on which the second node resides is also recorded.

16. The method of claim 14, wherein information about the length of the link between the first point and the second point is also recorded.

17. The method of claim 1, wherein steps (a)-(d) are repeated for every combination of points in a system and wherein the first database has a record for every possible combination of points.

18. The method of claim 1, wherein step (d) additionally comprises recording information about a straight line between an alternative placement of the first point and an alternative placement of the second point in the second database.

19. The method of claim 18, wherein step (d) records information about the straight line including first point identification, second point identification, location of the first point, location of the second point, elevation of the first point, elevation of the second point, and a field that records whether or not there is a valid unobstructed line-of-sight between the points when at least one point is placed in an alternative location in the second database.

20. The method of claim 19, wherein the first point and second point are nodes in a communications system, and step (d) additionally records information about a structure on which the first node resides and information about a structure on which the second resides in the second database.

21. The method of claim 20, wherein step (d) additionally records information about the length of the link between points when at least one point is placed at an alternative location in the second database.

22. A computer-readable medium containing instructions for determining line-of-sight configurations between a plurality of points in three-dimensional space, wherein said instructions that cause a computer to:

select a first point and a second point for processing;

determine whether a valid, unobstructed line-of-sight exists between the first point and the second point;

if a valid, unobstructed line-of-sight exists between the first point and the second point, record information about the line-of-light in a first database; and

if a valid, unobstructed line-of-sight does not exist between the first point and the second point, determine whether an alternative placement at least one point results in a valid, alternative unobstructed line-of-sight between the first point and the second point, and if a valid, alternative unobstructed line-of-sight does exist between the first point and the second point, record information about the alternative line-of-sight in a second database;

repeat steps (a)-(d) for other combination of points.

23. The computer-readable medium of claim 22, wherein the points are nodes in an infrared wireless system.

24. The computer-readable medium of claim 22, wherein said instructions to determine whether a valid line-of-sight exists comprises instructions that cause a computer to:

determine a straight line between the first point and the second point;

determine whether the length of the straight line is less than a maximum link length;

determine whether the angle between the straight line and the vertical is less than a maximum vertical angle; and

if the length of the straight line is less than the maximum link length, and the angle between the straight line and the vertical is less than the maximum vertical angle, determine whether the straight line intersects with an obstruction in the three-dimensional space.

25. The computer-readable medium of claim 24, wherein said instructions to determine whether the length of the straight line is less than a maximum link additionally comprises instructions to add a margin to the straight line.

26. The computer-readable medium of claim 25, wherein said margin comprises a vertical margin and a horizontal margin.

27. The computer-readable medium of claim 25, wherein said instructions to determine whether the straight line intersects with an obstruction cause a computer to determine whether the straight line with the margin added intersects with an obstruction in the three-dimensional space.

28. The computer-readable medium of claim 24, wherein said maximum link length is a configurable parameter.

29. The computer-readable medium of claim 24, wherein said maximum vertical angle is a configurable parameter.

30. The computer-readable medium of claim 24, wherein said instructions to determine whether the straight line intersects with an obstruction cause a computer to:

divide the straight line into equally sized pixels in a 3-Dimensional Map;

determine each pixel'"'"'s elevation;

for each pixel, read an adjusted terrain elevation from the 3-Dimensional Map for that pixel'"'"'s ground location and determining whether the pixel'"'"'s elevation is lower than the adjusted terrain elevation; and

if the elevation of any segment is lower than the adjusted terrain elevation at that pixel'"'"'s location, determine that the straight line intersects with an obstruction.

31. The computer-readable medium of claim 30, wherein the adjusted elevation of a location in the 3-Dimensional Map is the elevation of the terrain at that location adjusted by the height of an object at that location.

32. The computer-readable medium of claim 31, wherein the object is a building.

33. The computer-readable medium of claim 31, wherein the object is a tree.

34. The computer-readable medium of claim 22, wherein said instructions to record information about the line-of-sight in a first database additionally includes instructions to record information about the straight line between the first point and the second point in the first database if a valid, unobstructed line-of-sight does not exist between the first point and the second point.

35. The computer-readable medium of claim 22, wherein said instructions to record information about the line-of-sight in a first database cause the computer to record information about the line-of-sight including first point identification, second point identification, location of the first point, location of the second point, elevation of the first point, elevation of the second point, and a field that records whether or not there is a valid unobstructed line-of-sight between the first point and the second point.

36. The computer-readable medium of claim 35, wherein the first point and second points are nodes in a communications system, and said instructions to record information additionally comprise instructions to record information about a structure on which the first node resides and information about a structure on which the second node resides.

37. The computer-readable medium of claim 35, wherein said instructions to record information additionally comprises instructions to record information about the length of the link between the first point and the second point.

38. The computer-readable medium of claim 22, wherein said instructions are repeated for every combination of points in a system and wherein the first database has a record for every possible combination of points.

39. The computer-readable medium of claim 38, wherein said instructions to record information in a second database additionally comprises instructions to record information about a straight line between an alternative placement of the first point and an alternative placement of the second point in the second database.

40. The computer-readable medium of claim 38, wherein said instructions to record information in a second database additionally comprises instructions to record information about the straight line including first point identification, second point identification, location of the first point, location of the second point, elevation of the first point, elevation of the second point, and a field that records whether or not there is a valid unobstructed line-of-sight between the points when at least one point is placed in an alternative location in the second database.

41. The computer-readable medium of claim 40, wherein the first point and second point are nodes in a communications system, and additionally comprising instructions to record information in the second database about a structure on which the first node resides and information about a structure on which the second resides.

42. The computer-readable medium of claim 40, additionally comprising instructions to record information in the second database about the length of the link between points when at least one point is placed at an alternative location.

43. In a system for automatically determining line-of-sight configurations between nodes, wherein each node has a node height, a method of determining the elevation of a node, comprising:

(a) determining the node'"'"'s ground location;

(b) determining the node'"'"'s elevation by reading an elevation from a 3-Dimensional Map at the node'"'"'s ground location; and

(c) adding the node height to the node'"'"'s elevation;

whereby the 3-Dimensional map provides elevations given a ground location,

wherein said an elevation in the 3-Dimensional Map was determined by adding the height of any objects at a ground location to the elevation of terrain at the ground location.

44. The method of claim 43, wherein a node'"'"'s ground location is its ground coordinates.

45. The method of claim 43, wherein the objects at a ground location are selected from the group comprising houses and trees.

46. The method of claim 43, wherein said nodes are nodes in an infrared wireless system.

47. In a system for automatically determining line-of-sight configurations between nodes, wherein each node has a node height, a method of determining the elevation of a node, a computer-readable medium containing instructions that cause the system to:

determine the node'"'"'s ground location;

determine the node'"'"'s elevation by reading an elevation from a 3-Dimensional Map at the node'"'"'s ground location; and

add the node height to the node'"'"'s elevation;

whereby the 3-Dimensional Map provides elevations given a ground location, wherein said an elevation in the 3-Dimensional Map was determined by adding the height of any objects at a ground location to the elevation of terrain at the ground location.

48. The computer-readable medium of claim 47, wherein a node'"'"'s ground location is its ground coordinates.

49. The computer-readable medium of claim 47, wherein the objects at a ground location are selected from the group comprising houses and trees.

50. The computer-readable medium of claim 47, wherein said nodes are nodes in an infrared wireless system.

51. A method of determining a possible alternative line-of-sight between a first node and a second node, wherein said nodes are located in an aerial for which an aerial image is available, comprising the steps of:

(a) determining a first degree of freedom line for the first node, and a second degree of freedom line for the second node, such that each degree of freedom line is orthogonal to the straight line between the nodes;

(b) determining a resolution of the aerial image and an alternative position data parameter;

(c) placing the first node at a first placement that is a distance equal to the resolution in a first direction along the first degree of freedom line from the current placement of the first node, and placing the second node at a second placement that is a distance equal to the resolution in the first direction along the second degree of freedom line from the current placement of the second node;

(d) determining if the straight line between the first node at the first placement and the second node at the second placement is a valid, unobstructed line-of-sight;

(e) if the straight line is a valid, unobstructed line-of-sight, saving the line-of-sight; and

if the straight line is not a valid, unobstructed line-of-sight, repeating steps (c)-(e) until the first node has been moved the distance specified in the alternative position data parameter.

52. The method of claim 51, additionally comprising the step of

(f) if a valid, unobstructed line-of-sight is not found by moving the nodes in the first direction along the degree of freedom lines to a placement equal to the alternative position data parameter, repeating steps (c)-(e) moving the nodes in a second direction along the degree of freedom lines.

53. A method of identifying pixels in an aerial image that are part of a structure, comprising the steps of:

(a) obtaining the aerial image;

(b) dividing the image into blocks;

(c) for each block, clustering pixels in the image into small regions of uniform color and texture; and

(d) identifying at least one region as a structure.

54. The method of claim 53, wherein the aerial photograph image is a color photograph.

55. The method of claim 53, wherein the structure is a house.

56. The method of claim 53, wherein step (b) comprises:

(i) obtaining street data for the area associated with the aerial image;

(ii) updating the image with street information from the street data; and

(iii) segmenting the image into elementary city blocks based on the street information.

57. The method of claim 56, wherein the street data is comprised a standard electronic street map.

58. The method of claim 57, wherein the standard electronic street map is a TeleAtlas map.

59. The method of claim 56, wherein the street data includes street names, locations and postal addresses.

60. The method of claim 56, wherein step (b)(ii) comprises matching streets in the street data to street pixels in the image.

61. The method of claim 60, wherein street segments are shifted such that they are placed close to the middle of the associated street in the image.

62. The method of claim 61, wherein accuracy of matching streets in the street data to streets in the image is determined by comparing placement of a street segment from the street data to the color of the pixels in the image at the point of placement.

63. The method of claim 62, wherein an expected average street color is determined and accuracy of matching streets is determined by comparing the color of the pixels in the image at the point of placement to the expected average street color.

64. The method of claim 62, wherein street segments in the street data are shifted to match street in the image.

65. The method of claim 64, wherein Maximum A Posteriori estimation is used to shift street segments in the street data.

66. The method of claim 56, wherein step (b)(iii) comprises segmenting the image into blocks based on the street data obtained in step (b)(i).

67. The method of claim 53, wherein step (c) comprises using a Watershed technique to cluster pixels into regions.

68. The method of claim 67, wherein the Watershed technique creates regions of similar color.

69. The method of claim 53, wherein identifying a region as a house comprises comparing at least one characteristic of the region to at least one expected characteristic of a region encompassing a house.

70. The method of claim 69, wherein said at least characteristic is selected from the group comprising color, shape, area, distance from street and distance to closest house.

71. The method of claim 70, wherein at least characteristic is color, and the average color of the region is compared to an expected average color of a house.

72. The method of claim 53, additionally comprising creating a house map that labels each pixel as a house or not a house depending on the identification in step (d).

73. The method of claim 72, wherein said house map additionally identifies each region that as been identified as a house with a house identification code.

74. The method of claim 73, wherein every pixel in said house map is identified by a zero if it has not been identified as a house, or by a house number is it has been identified as a house, wherein said house number identifies the house.

75. A computer-readable medium containing instructions that cause a computer to identify pixels in an aerial image that are part of a structure, wherein said instructions cause include instructions to:

obtain the aerial image;

divide the image into blocks;

for each block, cluster pixels in the image into small regions of uniform color and texture; and

identify at least one region as a structure.

76. A method of identifying tree pixels in an aerial image, comprising the steps of:

(a) obtaining the aerial image;

(b) identifying at least one tree in the image;

(c) creating a statistical model of tree color using the at least one identified tree;

(d) for every pixel, using the statistical model to determine the probability that a pixel is a tree; and

(e) for every pixel, if the probability that a pixel is a tree exceeds a predetermined threshold, labeling the pixel as a tree.

77. The method of claim 76, wherein the aerial photograph image is a color photograph.

78. The method of claim 76, wherein step (b) comprises a user selecting at least one region on the image that is a tree.

79. The method of claim 76, wherein step (b) additionally comprises identifying at least one tree of a first type and at least one tree of a second type, and step (c) additionally comprises creating a statistical model of tree color using the at least one tree of a first type and the at least one tree of a second type, whereby the model estimates how the color of the at least one tree of a first type and the color of the at least one tree of a second type are distributed.

80. The method of claim 79, wherein the model is a Mixture of Gaussians model.

81. The method of claim 76, wherein step (e) additionally comprising creating a tree map with tree pixels labeled.

82. The method of claim 76, wherein every pixel in said tree map is labeled with a zero if it has not been identified as a tree, or with a non-zero number if it has been identified as a tree.

83. The method of claim 76, wherein step (b) additionally comprises identifying at least one tree shadow, and step (c) comprises creating a statistical model of tree color using the at least one identified tree and the at least one identified tree shadow.

84. The method of claim 83, wherein step (d) additionally comprises using the tree statistical model and the tree shadow statistical model to create a tree probability model.

85. The method of claim 84, wherein said tree probability model is used as the statistical model to determine the probability that a pixel is a tree.

86. The method of claim 83, wherein step (c) additionally comprises obtaining a sun direction, wherein the tree shadow statistical model is updated to account for the direction of the sun.

87. A method of creating a 3-Dimensional map of an area, wherein the 3-Dimensional map identifies every pixel in the area as a tree, house or terrain and identifies the elevation of every pixel, comprising the steps of:

(a) obtaining a tree map of the area, wherein the tree map identifies pixels that have been determined to be trees;

(b) obtaining a house map of the area, wherein the house map identifies pixels that have been determined to be houses;

(c) creating a city map from the tree map and the house map, wherein every pixel has a classification, wherein the classification is selected from the group comprised of tree, house and terrain;

(d) obtaining height data;

(e) obtaining terrain elevation data; and

(f) determining an elevation for every pixel.

88. The method of claim 87, wherein said height data is comprised of an estimated house height and an estimated tree height.

89. The method of claim 88, wherein step (f) is comprised of:

(i) determining a base pixel elevation from the terrain elevation data;

(ii) determining if the pixel is a tree from the city map, and if the pixel is a tree, determining the pixel'"'"'s elevation by adding estimated tree height to the base pixel elevation;

(iii) determining if the pixel is a house from the city map, and if the pixel is a house, determining the pixel'"'"'s elevation by adding estimated house height to the base pixel elevation.

(iv) if the pixel is neither a house nor a tree, determining the pixel'"'"'s elevation as the base pixel elevation.

90. A computer-readable medium containing instructions that cause a computer to create a 3-Dimensional map of an area, wherein the 3-Dimensional map identifies every pixel in the area as a tree, house or terrain and identifies the elevation of every pixel, wherein said instruction include instructions to:

obtain a tree map of the area, wherein the tree map identifies pixels that have been determined to be trees,

obtain a house map of the area, wherein the house map identifies pixels that have been determined to be houses;

create a city map from the tree map and the house map, wherein every pixel has a classification, wherein the classification is selected from the group comprised of tree, house and terrain;

obtain height data;

obtain terrain elevation data; and

determine an elevation for every pixel.