Search And Rescue Unmanned Aerial System

[0001] This application claims the benefit of priority to U.S. Provisional Patent Application Ser. No. 62/607,311, filed Dec. 18, 2017, the contents of which are hereby incorporated by reference.

[0002] This instant specification relates to unmanned aerial vehicles configured for environmental mapping.

[0003] An unmanned aerial vehicle (UAV), commonly known as a “drone”, is an aircraft without a human pilot aboard. UAVs generally include at least some degree of autonomy in their flight controls, ranging from features that simplify remote piloting (e.g., stabilization, position holding, obstacle avoidance) to fully automatic flight. UAVs are commonly used for tasks that are too expensive or dangerous for humans to perform, such as aerial photography or remote surveillance. An unmanned aerial system (UAS) generally includes one or more UAVs, a remote (e.g., ground-based) controller, and a system of communications between the two.

[0004] In general, this document describes unmanned aerial vehicles configured and used for three-dimensional environmental mapping.

[0005] In a first aspect, a computer-implemented method for creating three-dimensional models includes capturing, at a first location, a two-dimensional first image of a three-dimensional scene, capturing, at a second location, a two-dimensional second image of the three-dimensional scene, measuring a range distance from at least one of the first location and the second location to a closest object in the scene, determining a depth map based on differences between the first image and the second image, determining a three-dimensional point cloud based on the range distance, the depth map, and at least one of the first image and the second image, and providing the three-dimensional point cloud as a three-dimensional model of the three-dimensional scene.

[0006] Various implementations can include some, all, or none of the following features. The method can also include capturing, at a third location, a two-dimensional third image of the three-dimensional scene, measuring a second range distance between the third location and another closest object in the scene, determining a second depth map based on differences between the third image and one of the first image and the second image, determining a second three-dimensional point cloud based on the second range distance, the second depth map, and the third image, and expanding the three-dimensional model based on the second three-dimensional point cloud. Capturing the first two-dimensional image can include capturing, by an image sensor positioned at the first location by an unmanned aerial system (UAS), the first two-dimensional image, capturing the second two-dimensional image comprises capturing, by the image sensor positioned at the second location by the UAS, the second two-dimensional image, and measuring the range distance comprises measuring, by a range sensor positioned by the UAS, the range distance. Capturing the first two-dimensional image can include capturing, by a first image sensor positioned at the first location by a first unmanned aerial system (UAS), the first two-dimensional image, capturing the second two-dimensional image comprises capturing, by a second image sensor positioned at the second location by a second UAS, the second two-dimensional image, and measuring the range distance comprises measuring, by a range sensor positioned by the first UAS or the second UAS, the range distance. Determining a three-dimensional point cloud can include determining a two-dimensional collection of difference values by comparing the first image and the second image, grouping the difference values into subsets of points having similar difference values, identifying a subset from the grouped subsets, associating the range depth with the identified subset, determining depths of other subsets of points based on an extrapolation of the depth, the difference values of the identified subset, and the difference values of the other subsets, and creating the three-dimensional point cloud based on the determined depths. The method can also include, for one or more difference values in the collection of depths, selecting the difference value, determine the two-dimensional location of the selected difference value, identify a two-dimensional location in least one of the first image and the second image that corresponds to the determined two-dimensional location, identify one or more image characteristics of the identified location, wherein the image characteristics are selected from a group comprising color values and luminance values, and associating the identified image characteristic and the selected difference value with the determined two-dimensional location, wherein creating the three-dimensional point cloud based on the determined depths is further based on the image characteristics and the selected difference values associated with the determined two-dimensional locations, such that one or more points of the point cloud each have a three dimensional position and one or more image characteristics. The method can also include determining a flight path based on the three-dimensional model, and navigating an unmanned aerial system based on the determined flight path. The method can also include identifying a portion of the three-dimensional point cloud having a relatively lower point density than other portions of the three-dimensional point cloud, and identifying a three-dimensional location based on the identified portion, wherein the flight path includes the identified three-dimensional location. The method can also include capturing, at the identified three-dimensional location, a two-dimensional third image of the three-dimensional scene, measuring a second range distance between the identified three-dimensional location and another closest object in the scene, determining a second depth map based on differences between the third image and one of the first image and the second image, determining a second three-dimensional point cloud based on the second range distance, the second depth map, and the third image, and increasing the point density of the three-dimensional point cloud based on the second three-dimensional point cloud.

[0007] In a second aspect, an unmanned aerial system (UAS) includes a processing system, an image sensor, a range sensor, a lifting system comprising one or more lifting mechanisms configured to be controlled by the processor, and a non-transitory computer-readable medium coupled to the processing system and having instructions stored thereon that, when executed by the processing system, cause the UAS to perform operations including positioning, by the lifting system, the UAS to a three-dimensional first location, capturing, by the image sensor at the first location, a two-dimensional first image of a three-dimensional scene, positioning, by the lifting system, the UAS at a three-dimensional second location, capturing, by the image sensor at the second location, a two-dimensional second image of the three-dimensional scene, measuring, based on range signals provided by the range sensor, a range distance from at least one of the first location and the second location to a closest object in the scene, determining a depth map based on differences between the first image and the second image, determining a three-dimensional point cloud based on the range distance, the depth map, and at least one of the first image and the second image, and providing the three-dimensional point cloud as a three-dimensional model of the three-goo dimensional scene.

[0008] Various embodiments can include some, all, or none of the following features. The operations can also include capturing, at a third location, a two-dimensional third image of the three-dimensional scene, measuring a second range distance between the third location and another closest object in the scene, determining a second depth map based on differences between the third image and one of the first image and the second image, determining a second three-dimensional point cloud based on the second range distance, the second depth map, and the third image, and expanding the three-dimensional model based on the second three-dimensional point cloud. Determining a three-dimensional point cloud can include determining a two-dimensional collection of difference values by comparing the first image and the second image, grouping the difference values into subsets of points having similar difference values, identifying a subset from the grouped subsets, associating the range depth with the identified subset, determining depths of other subsets of points based on an extrapolation of the range depth, the difference values of the identified subset, and the difference values of the other subsets, and creating the three-dimensional point cloud based on the determined depths. The operations can also include, for one or more difference values in the collection of depths, selecting the difference value, determine the two-dimensional location of the selected difference value, identify a two-dimensional location in least one of the first image and the second image that corresponds to the determined two-dimensional location, identify one or more image characteristics of the identified location, wherein the image characteristics are selected from a group comprising color values and luminance values, and applying the identified image characteristic to the selected difference value, wherein creating the three-dimensional point cloud based on the determined depths is further based on the image characteristics applied to the difference values, such that one or more points of the point cloud each have three dimensional position and one or more image characteristics. The operations can also include determining a flight path based on the three-dimensional model, and navigating the UAS based on the determined flight path. The operations can also include identifying a portion of the three-dimensional point cloud having a relatively lower point density than other portions of the three-dimensional point cloud, and identifying a three-dimensional location based on the identified portion, wherein the flight path includes the identified three-dimensional location. The operations can also include capturing, by the image sensor at the identified three-dimensional location, a two-dimensional third image of the three-dimensional scene, measuring, based on second range signals provided by the range sensor, a second range distance between the identified three-dimensional location and another closest object in the scene, determining a second depth map based on differences between the third image and one of the first image and the second image, determining a second three-dimensional point cloud based on the second range distance, the second depth map, and the third image, and increasing the point density of the three-dimensional point cloud based on the second three-dimensional point cloud. The UAS can also include a communications transceiver, wherein the operations can also include transmitting, by the communications transceiver, at least one of the first image, position information of the first location, the second image, position information of the second location, the range distance, the depth map, and the three dimensional point cloud to a computer system that is separate from the UAS, and processing, by the computer system, at least one of the first image, position information of the first location, the second image, position information of the second location, the range distance, the depth map, and the three dimensional point cloud to determine the three-dimensional model. The operations can also include receiving, by the communications transceiver, the three-dimensional model, determining a flight path based on the received three-dimensional model, and navigating the UAS based on the determined flight path.

[0009] In a third aspect, a system for creating full-color three-dimensional models includes a first unmanned aerial system (UAS) and a second UAS, each UAS having a processing system, an image sensor, a range sensor, a communications transceiver system, a lifting system having one or more lifting mechanisms configured to be controlled by the processor, a non-transitory computer-readable medium coupled to the processing system and having instructions stored thereon that, when executed by the processing system, cause the first UAS to perform operations including positioning, by the lifting system, the first UAS to a three-dimensional first location, capturing, by the image sensor at the first location, a two-dimensional first image of a three-dimensional scene, transmitting, by the communications transceiver, the first image and information descriptive of the first location to the second UAS, and cause the second UAS to perform operations including receiving, by the communications transceiver, the first image and information descriptive of the first location, positioning, by the lifting system, the second UAS to a three-dimensional second location, capturing, by the image sensor at the location, a two-dimensional second image of the three-dimensional scene, measuring, based on range signals provided by the range sensor, a range distance from the second location to a closest object in the scene, determining a depth map based on differences between the first image and the second image, determining a three-dimensional point cloud based on the range distance, the depth map, and at least one of the first image and the second image, and providing the three-dimensional point cloud as a three-dimensional model of the three-dimensional scene.

[0010] In a fourth aspect, a system for creating full-color three-dimensional models includes at least one unmanned aerial system (UAS) having a first processing system, an image sensor, a range sensor, a first communications transceiver system, a lifting system having one or more lifting mechanisms configured to be controlled by the processor, a first non-transitory computer-readable medium coupled to the first processing system and having instructions stored thereon that, when executed by the first processing system, cause the UAS to perform first operations including positioning, by the lifting system, the UAS to three-dimensional locations, capturing, by the image sensor at the locations, two-dimensional images of a three-dimensional scene, measuring, based on range signals provided by the range sensor, range distances from the locations to closest objects in the scene, and transmitting, by the first communications transceiver, the images, the range distances, and information descriptive of the locations, and a computing system having a second processing system, a second communications transceiver system, a second non-transitory computer-readable medium coupled to the second processing system and having instructions stored thereon that, when executed by the first processing system, cause the computer system to perform second operations including receiving, by the communications transceiver, a first image and information descriptive of a first location, receiving, by the communications transceiver, a second image and information descriptive of a second location, receiving, by the communications transceiver, a range distance from one of the first location and the second location to the a closest object in the scene, determining a depth map based on differences between the first image and the second image, determining a three-dimensional point cloud based on the range distance, the depth map, and at least one of the first image and the second image, and providing the three-dimensional point cloud as a three-dimensional model of the three-dimensional scene.

[0011] Various embodiments can include some, all, or none of the following features. The second operations can also include transmitting, by the second communications transceiver system, the three-dimensional model, and the first operations can also include receiving, by the first communications transceiver system, the three-dimensional model, determining a flight path based on the received three-dimensional model, and navigating the UAS based on the determined flight path.

[0012] The systems and techniques described here may provide one or more of the following advantages. First, a system can three-dimensional maps of an environment to human operators. Second, the system can show the 3D locations of objects, people, walls, doors, and other features. Third, the system can provide 3D maps in various spectra, including visible, ultraviolet, infrared, combinations of these, or others. Fourth, the system can provide 3D maps with little human input. Fifth, the system can provide the aforementioned advantages with relatively fewer moving parts and/or at lower cost than current solutions.

[0013] The details of one or more implementations are set forth in the accompanying drawings and the description below. Other features and advantages will be apparent from the description and drawings, and from the claims.

[0024] This document describes systems and techniques for mapping three-dimensional (3D) environments using an unmanned aerial system (UAS). In very general terms that will be explained in more detail below, an unmanned aerial vehicle (UAV) can be directed to a selected location within a 3D environment, and take a picture. The UAV can then be directed to a slightly different vantage point, and take a second picture and measure a distance to a closest object in the picture. The two pictures can be compared to detect the degree of shift in objects in the scene. Closer objects will appear to shift proportionally more than more distant objects. Since the distance to the closest object was measured, the distances to other objects can be determined proportional to their shifts. Color or other image information from one of the pictures can be combined with the determined distances to create a 3D color model of the scene.

[0025] In use, the example UAS can be used in search and rescue operations. For example, a fire department can send a single UAV or a swarm of cooperative UAVs into a burning building to capture multiple sets of 3D images (e.g., color, infrared, thermal) that can be combined into a larger, realistic-looking 3D model of the inside of the building. Fire fighters can use such models to preview the hazardous environment, pre-locate victims in need of rescue, plan searches, etc. For example, the UAS can help fire fighters get to victims with less risk to the fire fighters (e.g., avoiding especially dangerous areas, reducing human exposure to perform surveillance and search) and/or in less time (e.g., bypassing unimportant rooms and going more directly to the location of need, avoiding dead ends).

[0026] FIG. 1 is a block diagram of an example unmanned aerial system (UAS) 100. The terms “unmanned aerial system” and “UAS” can be used interchangeably with the terms “unmanned aerial vehicle” (UAV) and/or “drone” as they are also commonly called. In general, this document will use the term “unmanned aerial vehicle”, “UAV”, and/or “drone” to refer to a single flying apparatus, and use the term “unmanned aerial system” and/or “UAS” to refer to a collection of one or more UAVs and/or supporting equipment (e.g., remote controllers) used together in the operation of the UAVs.

[0027] Referring now to FIG. 1, the UAS 100 includes a UAV 101. The UAV 101 includes a low-level controller 110 and a high-level controller 150. In some embodiments, the functions of the low-level controller 100 and the high-level controller 150 can be performed by multiple processors, and in some other embodiments the functions can be performed on a shared processor. The low-level controller 110 includes one or more processors that can perform operations based on computer instructions and various forms of input and feedback, as will be described further below. The low-level processor 110 is communicatively connected to a flight data storage device 112. The flight data storage device 112 tangibly stores computer instructions that, when processed by the low-level controller 110, perform flight operations (e.g., controlling position and heading, power management, communications). The flight data storage device 112 also stores data that can be used during flight operations (e.g., maps, waypoints, calibration settings). The low-level controller 110 performs at least three general tasks: pose estimation, flight command reception, and lift control.

[0028] The low-level controller 110 is communicatively connected to a communications transceiver 114 for flight command reception. The communications transceiver 114 is configured to communicate (e.g., by digital or analog radio link) to a remote controller 102. In use, a human or automated operator uses the remote controller 102 to transmit flight instructions (e.g., pitch, yaw, roll, altitude, direction, speed) to the transceiver 114, and the low-level controller 110 uses those instructions as part of its flight control operations. The low-level controller 110 uses the transceiver 114 to provide feedback to the remote controller 102, such as position, power status, and system health information.

[0029] The low-level controller 110 also receives feedback from an aerial measurement unit (AMU) 116. The AMU 116 includes one or more devices for detecting the physical state of the UAV 101. For example, the AMU 116 can include one or more single or multiple axis accelerometers (e.g., inertial measurement units) that can be used to measure changes in position of the UAV 101. The AMU 116 can include local and/or global positioning systems (e.g., GPS, GLONASS) for identifying the absolute position of the UAV 101 (e.g., globally) or the relative position of the UAV 101 (e.g., relative to a “home” location or stationary transmitter system). The AMU 116 can include other measurement systems as well, such as compasses, gyroscopes, altimeters, thermometers, voltmeters, ammeters, optical flow sensors, and combinations of these and/or any other appropriate form of device that can provide feedback about UAV flight operations and/or conditions.

[0030] The pose of the UAV 101 includes the position and orientation of the UAV 101, and can be represented as a pair of three-element vectors:

$\mathrm{Position}\text{:}\xi =\left[\begin{array}{c}x\\ y\\ z\end{array}\right]$ $\mathrm{and}$ $\mathrm{Orientation}\text{:}\eta =\left[\begin{array}{c}\Phi \\ \theta \\ \varphi \end{array}\right]$

[0031] Position is the position of the UAV 101 (e.g., relative to the starting point, takeoff point, <0, 0, 0>). Orientation is the orientation of the UAV 101, relative to its initial orientation (e.g., <0, 0, 0>, starting out on a level surface and with a zero heading). <ϕ, θ, Ψ> are rotations around the <x, y, z> axes respectively (e.g., roll, pitch, yaw). These are intrinsic rotations (e.g., contrasted with extrinsic rotations).

[0032] Orientation can also be expressed as a quaternion:

$q=\left[\begin{array}{c}\begin{array}{c}{q}_0\\ q_1\\ q_2\end{array}\\ q_3\end{array}\right]$

[0033] In some implementations, quaternions, which are an extension of the complex number system, can be used to eliminate some issues associated with calculating the absolute orientation of the UAV as a roll-pitch-yaw vector. In some examples, quaternions can be used to avoid a phenomenon called gimbal lock.

[0034] Pose estimation is performed to provide absolute orientation data for the UAV 101. However, since noise is generally present in sensor data, a process of repeatedly modeling the absolute orientation of the UAV 101 in space is implemented. First, three-dimensional angular acceleration data is collected from the AMU 116. This data is then integrated twice to generate an estimate for the angular position (quaternion) of the UAV 101. Using sensor fusion with a Linear Quadratic Estimator (Kalman Filter):

$x_k=F_kx_{k-1}+B_ku_k+w_k$ $\mathrm{Where}\text{:}B_k=\left[\begin{array}{cccc}-0.15& -0.15& 0.15& 0.15\\ -0.15& 0.15& 0.15& 0.15\\ -0.1& 0.1& -0.1& 0.1\end{array}\right]$

[0035] This data is combined with the data from the history of motor outputs to generate a more robust pose estimate that accounts for noise and inconsistencies in the data. Pose estimates are calculated using previous pose data, sensor data, and control input history. In this case, x_k is the vector representing the current orientation of the UAV 101. F_k is the state transition model, which in this case consists of angular acceleration data that has been twice-integrated. This state transition model is applied to the previous pose estimate, x_k-1. The control model, B_k, is derived from a UAV linear matrix model, such as a quadcopter linear matrix model, and is applied to the control input vector u_k. Finally, process noise, w_k, which is taken from a multivariate normal distribution with mean zero is applied to account for noise in the sensor data and system as a whole. This pose estimate is then used to level the UAV 101 during hover routines, or to follow flight trajectories. In some implementations, other pose estimation techniques, including an Extended Kalman Filter, Unscented Kalman Filter, or machine learning-based approaches may be used.

[0036] Actual flight is achieved by a collection of lift-generating devices 120, such as motor/propeller combinations or jet turbines. Power for the lift-generating devices 120 is provided by a power system 130 (e.g., a battery, a fuel tank) that also provides power to the other subsystems of the UAV 101. Power to the lift-generating devices 120 is controlled by a motor controller 122 configured to receive commands from, and provide feedback to, the low-level controller 110.

[0037] The high-level controller 150 is in communication with the low-level controller 110, and includes one or more processors and electronic memory systems that tangibly store computer instructions that, when performed by the processor(s), perform high-level functions of the UAV 101. The high-level controller 150 is in communication with an image sensor 160 and a range sensor 170.

[0038] The image sensor 160 is configured to capture visual information as data (e.g., a digital camera). In the illustrated embodiment, the image sensor 160 is a form of color digital camera system that can capture a two-dimensional (2D) image of a scene and convert that image into data that is provided to the high-level controller 150. In some embodiments, the image sensor 160 can sense all or a portion of the visible light spectrum, ultraviolet, infrared (e.g., thermal vision, night vision), luminance only (e.g., greyscale), or combinations of these and/or any other appropriate form of imaging (e.g., x-rays). In some embodiments, the image sensor 160 can also include one or more illuminators (e.g., headlights, flashes) and/or light amplifiers (e.g., night vision). In use, the image sensor 160 captures images of scenes near (e.g., in front of) the UAV 101.

[0039] The range sensor 170 is configured to measure distances to solid objects and provide that measurement as data to the high-level controller 150. In some embodiments, the range sensor 170 can be a sonic or ultrasonic rangefinder. In some embodiments, the range sensor 170 can be a laser or other optical rangefinder. In use, the range sensor 170 measures the distance from the UAV 101 to one or more objects in the scene near (e.g., in front of) the UAV 101, such as the scene captured by the image sensor 160.

[0040] The high-level controller 150 is configured to process image data from the image sensor 160 and distance measurements from the range sensor 170 to create a three-dimensional (3D) model of the scene. This process will be discussed in detail in the descriptions of FIGS. 3-10. The high-level controller 150 stores the 3D model in a 370 map storage device 180 (e.g., a computer memory, a FLASH memory, a disk drive).

[0041] The high-level controller 150 is in data communication with a transceiver 190. The transceiver 190 provides wireless communications with a remote terminal 103. In some embodiments, the high-level controller 150 can provide 3D maps to the remote terminal 103 (e.g., for remote viewing). In some embodiments, the high-level controller 150 can provide raw or partly processed sensor information to the remote terminal 103. For example, the UAV 101 can transmit image, range, and positional information to the remote terminal 103, and the remote terminal 103 can process the data into the 3D map. Such examples can offload the process of building the map from the high-level processor 150 to the remote terminal 103 (e.g., which may have greater processing power and/or storage). Information (e.g., maps) can be transmitted from the remote terminal 103 to the UAV 101 for storage in the map storage device 180 as well.

[0042] FIG. 2 shows an example unmanned aerial vehicle 200. In some embodiments, the UAV 200 can be the example UAV 101 of FIG. 1. The UAV 200 includes a main fuselage 210 that supports four lift-generating devices 220 (e.g., motor-propeller pairs). An image sensor 260 and a range sensor 270 are supported by the main fuselage 210, and are oriented in the same general direction. Information collected through the image sensor 260, the range sensor 270, and aerial measurement units (not shown) is processed by a high-level controller (not shown) that is housed within the main airframe 210.

[0043] The UAV 200 has a transceiver 214 configured to receive flight commands from a remote controller (e.g., the remote controller 102) and transmit flight feedback information to the remote controller. The UAV 200 has a transceiver 290 configured to provide 3D map data, processed sensor data, and/or raw sensor data to a remote terminal (e.g., remote terminal 103), and/or receive 3D map data from the remote terminal.

[0044] Although the UAV 200 is depicted as a quadcopter, in other embodiments it can be configured with more lift generating devices 220 (e.g., hexacopter, octacopter), fewer lift generating devices (e.g., tricopter, single or dual-rotor helicopter), tiltrotors, jets, rockets, lighter-than-air lifters (e.g., dirigible), variable wings (e.g., ornithopter), fixed wings, or combinations of these and/or any other appropriate form of lift-generating system(s) that can be used with a UAV.

[0045] FIGS. 3 and 4 show the example unmanned aerial vehicle 200 of FIG. 2 in an example three-dimensional environment 300. The 3D environment 300 includes a number of 3D objects 301a-301e. In the illustrated examples, the objects 301a-301e are simple shapes that represent more complex objects, such as walls, furniture, stairs, window openings, desks, countertops, rocks, plants, another any other appropriate physical object. In use, the UAV 200 is flown, autonomously or remotely, to a first position in the 3D environment 300, as shown in FIG. 3.

[0046] In the first position, the UAV 200 uses the image sensor 260 (not visible in these views) to capture a first digital image of the objects 301a-301e of a first portion of the 3D environment 300. This first portion is represented by the scene 310a. The UAV 200 also uses the range sensor 270 (not visible in these views) to measure one or more distances from the UAV 200 to the objects 301a-301c. As will be explained further in the discussion below, the range measurement generally represents the distance to the closest object in the scene 310a.

[0047] Referring now to FIG. 4, the UAV 200 has been flown or otherwise repositioned, autonomously or remotely, to a second position in the 3D environment 300. In the second position, the UAV 200 uses the image sensor 260 to capture a second digital image of the objects 301a-301e of a second, overlapping portion of the 3D environment 300. This second portion is represented by the scene 310b. The UAV 200 also uses the range sensor 270 to measure one or more distances from the UAV 200 to the objects 301a-301c. As will be explained further in the discussion below, the range measurement generally represents the distance to the closest object in the scene 310b. In some implementations, the UAV may take only a single distance measurement from one of the two positions.

[0048] FIG. 5 shows a conceptual example of information collected by an unmanned aerial vehicle, such as the example UAV 101 of FIG. 1 or the example UAV 200 of FIG. 2. The example includes a pixel array 510a and a pixel array 510b. Each pixel in the image arrays 510a and 510b has a row (X) and column (Y) location.

[0049] In some implementations, a calibration process can be performed before using the UAV 101 for 3D capture operations, in order to account for image distortion. For example, the image sensor can be calibrated by capturing an image of a known checkerboard pattern, analyzing the captured image based on the known information to determine one or more correction matrices, and reference those matrices whenever future images are captured. In some implementations, since the hardware generally does not change during use of the UAV 101, the distortions can remain generally constant.

[0050] The pixel array 510a represents a first image of a 3D scene captured by a UAV (e.g., the image of the scene 310a). The UAV is then moved, as represented by arrow 512, to a second (e.g., offset) position. The pixel array 510b represents a second image of the 3D scene captured by the UAV from the offset position relative to the first image (e.g., the image of the scene 310b). A range measurement 520 is also taken from the second position.

[0051] FIG. 6 shows a conceptual example of data operations 600 for determining an example depth map 610 (or “point cloud”). In general, the depth map 610 is a 2D array of range values. In the illustrated example, each of the range values corresponds to a pixel location in the second image 510b.

[0052] The first image 510a and the second image 510b are compared in a difference process 620. In the difference process 620, the UAV or the UAS compares differences between the two captured images 510a and 510b to determine a difference array 630. The difference array 630 is a 2D array of difference values. In the illustrated example, each of the difference values corresponds to a pixel location in the second image 510b.

[0053] The first image 510a and the second image 510b is processed as a pair using a Semi-Global Block Matching (SGBM) process to generate depth maps, treating them as though they to matched pairs from a stereo camera. In some implementations, other techniques may be used, such as Scale-Invariant Feature Transformation (SIFT) or Speeded Up Robust Features (SURF), to match images. The process locates corners and edges within the images using Gaussian blurs to remove inconsistencies. Then, the process matches the detected corners and edges between the two images, and calculates how far each corner or edge moved between the two images 510a and 510b.

[0054] The process identifies epipolar lines (e.g., since the images have already been undistorted, these are just straight lines). Along these lines, the process identifies matching blocks of pixels (e.g., 3×3 blocks), especially corners and edges. A cost function compares various line angles to find the one that includes the most matched blocks. Then, the pixel coordinates of matched blocks are compared to estimate depths.

[0055] Pixels that move further between the two images 510a, 510b are considered to be closer to the UAV, while groups of pixels that move less are considered to be further away, which is a consequence of the parallax effect. The parallax effect that is leveraged in the implementation of the SGBM process determines relative distances among objects in the scene. For example, the process can determine that a certain group of pixels is three times further away than another group, but at this stage, it cannot determine the absolute distances.

[0056] As mentioned above, objects in the foreground of the images 510a, 510b will appear to have moved further proportionally further than objects in the background due to parallax. In the difference array 630, the magnitude of difference that is determined between the two images 510a, 510b for a given XY location is the difference value given for the corresponding XY location in the difference array 630.

[0057] Since the magnitudes of the difference values in the difference array 630 are proportional to the distances between the UAV and the objects in the captured image 510b, the difference values also indicate the relative distances from the UAV to the objects and/or objects represented by the pixels. At this point, only relative distances are known from the images.

[0058] The difference array 620 and the range measurement 520 are then provided to a scaling process 640. In the scaling process, the range measurement 520 is analyzed to determine an absolute distance to the closest object in the image 510b. This distance is associated with the location(s) in the difference array 620 having the greatest difference values.

[0059] Once an absolute distance value is known for one (or more) of the XY locations in the difference array 620, absolute distance values can be determined for the other XY locations in the difference array 620. Since the difference values are relative and proportional to each other, and represent distances that are proportionally further away from the known absolute distance to the closest foreground object, the absolute distances of the other XY locations can be extrapolated based on the range measurement 520. The resulting 2D array of absolute distances is provided as the depth map 610.

[0060] The depth map itself can be represented as a two-dimensional array of distance values, with each element containing the distance of the associated pixel. For example, the furthest object can be assigned a distance of 1, and all other objects can be assigned decimal values between 0 and 1.

$\mathrm{rel}=\left[\begin{array}{cccc}0.321& 0.281& 0.949& 0.101\\ 0.391& 0.532& 0.191& 0.932\\ 0.371& 0.134& 1.000& 0.294\\ 0.371& 0.134& 1.000& 0.452\end{array}\right]$

[0061] Since each image is associated with a range measurement, which denotes the distance to the closest object, the relative distances can be converted into absolute distances. Conversion:

a(x,y)=r(x,y)/r(min)×a(min)

[0062] Where:

[0063] a(x,y)=absolute distance at an arbitrary pixel (e.g., the value to be found).

[0064] r(x,y)=relative distance at an arbitrary pixel (e.g., from depth map).

[0065] a(min)=absolute distance of closest point (e.g., from range measurement).

[0066] r(min)=smallest relative distance from depth map.

[0067] Taking the previous example 4×4 array and converting it based on these equations, assuming 1 m for closest distance, the example result would be:

$\mathrm{rel}=\left[\begin{array}{cccc}2.287& 2.782& 9.936& 1.000\\ 3.871& 5.267& 1.891& 9.228\\ 8.040& 3.772& 1.307& 2.911\\ 3.673& 1.327& 9.901& 4.475\end{array}\right]$

[0068] As an array of pixels with distances, this array needs to be converted this into actual points in space. Each captured image is a two-dimensional projection of the three-dimensional space. As a result, the (x,y) coordinates of a pixel cannot be directly correlated with the associated depth into an (x,y,z) point.

[0069] Instead, the (x,y) location of a pixel corresponds to two angles of incidence, a horizontal and a vertical one. Knowing the image sensor's field of view (e.g., 90 degree horizontal and 60 degree vertical) and the resolution of the images (e.g., 640×480), the (x,y) values of the pixels can be converted into (θ_n, θ_v).

${\theta }_h=\frac{x-640/2}{90/2}$ ${\theta }_v=\frac{y-480/2}{60/2}$

[0070] At this point in the process, two angles and a distance (i.e., a point in a spherical coordinate system) have been determined. To convert this to the Cartesian (x,y,z) coordinate system, trigonometry is used. Here, r is the calculated distance, and θ_n and θ_v are the horizontal and vertical incidence angles.

x=r sin θ_v cos θ_h

y=r sin θ_v sin θ_h

z=r cos θ_v

[0071] Based on this information, the depth map can be converted into a scene point cloud. By cross-referencing the depth pixels with the original image pixels, color is also added into this point cloud. The x,y,z,R,G,B values are stored to be placed into the larger environment cloud.

[0072] FIG. 7 shows a conceptual example of data operations 700 for determining an example three-dimensional model 710. The depth map 610, by itself, is an array (e.g., XY) of distance values (e.g., Z) from the UAV to various points (e.g., pixels) in the image 510b. As such, the depth map 610 is a 2D (e.g., XY) collection of 3D coordinates (e.g., XYZ). In some implementations, a 3D model can be determined directly from the depth map 610. If such a model were to be represented visually, it would reveal shapes and surfaces of the scene captured in the image 510b (e.g., but not color).

[0073] In the illustrated example, the depth map 610 and the second image 510b are provided to a merging process 720. In general, a new 2D array is created in which each XY location stores a depth value from a corresponding XY location in the depth map 610, and one or more pixel values (e.g., red, green, blue, luminosity) from a corresponding XY location in the image 510b. The resulting 2D array of image (e.g., color) and depth values (sometimes called a “point cloud”) is provided as a point array 730.

[0074] The point array 730 is processed (e.g., extruded) into a 3D array. For example, the depth value for each XY location can be transformed into a Z value, and for each 3D cell with a transformed Z value, the corresponding XY image value can be stored. The 3D array is then visualized or otherwise presented as the 3D model 710, in which the 3D array locations having image values (e.g., colors) are presented with those image values at their corresponding 3D positions, and the 3D array locations without image values are transparent. As such, the 3D model 710 has both depth and color to at least partly emulate the look and form of the scene 310b.

[0075] In order to perform environment reconstruction, a set of base axes is identified: X, Y, and Z (note capitalization). These coordinates are used as a base for the placement of the individual scene point clouds into the larger environment, since there is a common basis that they are all converted to. In this example, the position according to these axes is referred to as the absolute position. In this example, these axes are relative to the takeoff location of the UAV. As a result, just before the UAV takes off, it is at absolute position <0,0,0> (in units of meters), and if it climbs 1 meter and moves forward 1 meter (without turning), it would be at absolute position <1,0,−1> (e.g., upwards is −Z in this example). The majority of the operations that follow are used to place the scene point clouds, which are only relative to the UAS at the position they were captured, into these absolute axes.

[0076] As discussed above, each of the points can be represented as a vector that encodes its position relative to the UAV at the moment that the point was captured. This vector can be given as:

$p=\left[\begin{array}{c}{p}_x\\ p_y\\ p_z\end{array}\right]$

[0077] Each of these must be converted to a vector that represents its position relative to the base axes. The goal vector can be given as:

$P=\left[\begin{array}{c}{P}_x\\ P_y\\ P_z\end{array}\right]$

[0078] To start, there is a vector p. Note that p represents the point's location in relation to the UAV, not to the base axes. The conversion process applies linear algebra, specifically the usage of matrices as linear transformations. The first step is translation.

[0079] Translation effectively moves the <x, y, z> relative axes of the UAV to share a common origin with the <X, Y, Z> absolute base axes. For example, knowing that:

$\xi =\left[\begin{array}{c}x\\ y\\ z\end{array}\right]$ $\mathrm{and}$ $p=\left[\begin{array}{c}{p}_x\\ p_y\\ p_z\end{array}\right]$

[0080] The goal is to shift p so that it can counteract the linear shift associated with the position of the UAV, ξ. This is accomplished with a matrix multiplication.

[0081] Construct a translation matrix T:

$T=\left[\begin{array}{cccc}1& 0& 0& x\\ 0& 1& 0& y\\ 0& 0& 1& z\\ 0& 0& 0& 1\end{array}\right]$

[0082] Add a fourth element, 1, to p. This helps in the next step. Call this p_h (e.g., “h” for “homogeneous” coordinates). Multiply p_h by T:

$T=\left[\begin{array}{cccc}1& 0& 0& x\\ 0& 1& 0& y\\ 0& 0& 1& z\\ 0& 0& 0& 1\end{array}\right]\left[\begin{array}{c}{p}_x\\ p_y\\ p_z\\ 1\end{array}\right]=\left[\begin{array}{c}{t}_x\\ t_y\\ t_z\\ 1\end{array}\right]$

[0083] Then remove the extraneous 1 from the resultant vector, to get a translated point location, t:

$t=\left[\begin{array}{c}{t}_x\\ t_y\\ t_z\end{array}\right]$

[0084] This represents the location of the point when the position of the UAV is accounted for, but not the orientation. To determine the rotation, the quaternion representation of the orientation of the UAV (q) is converted into a roll-pitch-yaw representation n. The quaternion q represents a rotation angle, q₀, about a rotation axis vector, <q₁, q₂, q₃>. This is contrasted with the roll-pitch-yaw representation, which represents the orientation as three angles (e.g., rotations around x,y,z axes). The formulae for conversion from quaternion to roll-pitch-yaw can be given as:

$\phi ={\tan }^{-1}\left(\frac{q_0q_1+q_2q_3}{q_0^2-q_1^2-q_2^2+q_3^2}\right)$ $\theta =-{\sin }^{-1}\left(2\left(q_1q_3-q_0q_2\right)\right)$ $\psi ={\tan }^{-1}\left(\frac{2\left(q_0q_3+q_1q_2\right)}{q_0^2+q_1^2-q_2^2-q_3^2}\right)$

[0085] This is what is known as an “intrinsic rotation”, which means that the rotations are done with respect to the axes of the UAV, not the absolute axes. When a rotation is performed about one axis, the other two axes move. Therefore, the second rotation takes place around an axis that is not where it started. As a result, the order of rotation matters. In this example, the rotation transformation happens in reverse order: yaw, then pitch, then roll (e.g., ψ, then θ, then ϕ). The derived formulae are unique to this order of rotations.

[0086] The orientation is now in the desired format, and t, the translated position of the point, has been calculated. The rotation of the point in 3D space is performed. A rotation matrix R is constructed. In this example, R is derived to be as follows (e.g., based on matrix multiplication of the three component rotations):

$R=\left[\begin{array}{ccc}\cos \psi \cos \theta & \cos \psi \sin \theta \sin \phi -\sin \psi \cos \phi & \cos \psi \sin \theta \cos \phi +\sin \psi \cos \phi \\ \sin \psi \cos \theta & \sin \psi \sin \theta \sin \phi +\cos \psi \cos \phi & \sin \psi \sin \theta \cos \phi -\cos \psi \sin \phi \\ -\sin \theta & \cos \theta \sin \phi & \cos \theta \cos \phi \end{array}\right]$

[0087] Multiply the translated point t by R. This will give the goal point, P:

$P=\mathrm{Rt}=\left[\begin{array}{ccc}\cos \psi \cos \theta & \cos \psi \sin \theta \sin \phi -\sin \psi \cos \phi & \cos \psi \sin \theta \cos \phi +\sin \psi \cos \phi \\ \sin \psi \cos \theta & \sin \psi \sin \theta \sin \phi +\cos \psi \cos \phi & \sin \psi \sin \theta \cos \phi -\cos \psi \sin \phi \\ -\sin \theta & \cos \theta \sin \phi & \cos \theta \cos \phi \end{array}\right]\hspace{1em}\left[\begin{array}{c}{t}_x\\ t_y\\ t_z\end{array}\right]=\left[\begin{array}{c}{P}_x\\ P_y\\ P_z\end{array}\right]$

[0088] This is the result being sought: a point with respect to the absolute base axes. The color or other image data is then assigned to the point, and the result is a representation of a point in the right place in 3D space, with the captured color of that point. This process is repeated for the other points. Since each scene point cloud is generally captured from a different pose, each one has its own associated T and R matrices.

[0089] In operation, the UAV streams the point data (<x, y, z> and <R, G, B>) to the remote workstation 103. In some implementations, the stream can look like:

[0090] x,y,z,R,G,B/x,y,z,R,G,B/x,y,z,R,G,B/ . . .

[0091] A process operating on the remote workstation 103 converts the point data into a standard file format, such as an .ASC file (e.g., plain text) or an XML file. In the example of a plain text file, the point data can be represented as a collection of lines of text, each of which corresponds to a point from the cloud:

[0092] x y z R G B

[0093] x y z R G B

[0094] x y z R G B

[0095] . . .

[0096] The resulting file can be provided to software that can interpret the 3D model data and provide a visual rendering of the 3D model. One such software package is on open-source software application called “MeshLab” (http://www.meshlab.net/), which is capable of reading the .ASC file and render it so that it can be seen as a point cloud on a display screen. The software converts the data from millions of lines of six numbers into a form that is easily interpretable by humans.

[0097] FIG. 8 shows a conceptual example of data operations 800 for expanding an example three-dimensional model. In the example operations 700, a single point map (e.g., point map 730) is used to model the scene 310b. In general, this process can be repeated to expand the model with additional data points.

[0098] In the illustrated example, a collection of point arrays 810a-810n are collected. For example, the point array 810a can be the example point array 730 of FIG. 7, and the point arrays 810b-810n can be additional point arrays taken by the same UAV or multiple UAVs from different points of view.

[0099] The point arrays 810a-810n can be combined in a merge process 820. The merge process 820 applies one or more techniques for matching points in absolute space. For example, the point arrays 810a-810n can be compared to identify similarities that represent overlap between two or more UAV perspectives, and/or images of the same object(s) but captured from two or more UAV orientations, and the relative positioning of the point arrays 810a-810n can be determined relative to each other in order to be assembled into a common 3D array.

[0100] In another example, the point arrays 810a-810n can be augmented with positional information obtained from the UAV's flight systems at the time an image is captured. Each point array 810a-810n can be a partial point cloud captured at a different position and orientation, each of which can be estimated based on UAV flight sensor information. Thus, each of the point arrays 810a-810n can be transformed using a matrix that takes into account the position and orientation of the UAV at the time of capture. By applying this linear transformation, which is unique to each cloud, the point arrays 810a-810n can be placed relative to a common coordinate system. The resulting 3D data can then be visualized or otherwise presented as a 3D model 830. This process allows large point clouds to be constructed as a map of the entire environment.

[0101] FIG. 9 shows an example floor plan of a space 900 and example UAV operations within the space 900. A UAV 910 is launched from a starting location 901a. In some implementations, the location 901a may be designated as a “home” location (e.g., for an autonomous return flight). In some implementations, the location 901a may be used as a point of origin for the 3D model that will be built based on the UAV 910 operations. For example, the location 901a may be identified as having a 3D position of X=0, Y=0, and Z=0, and an orientation of PITCH=0, YAW=0, and ROLL=0. In another example, the location 901a may be identified based on absolute position (e.g., GPS coordinates, compass heading, and sensed tilt angles).

[0102] In the illustrated example, the UAV 910 scans the area in front of the location 910, which includes a door 920. Information from that scan is processed (e.g., as described elsewhere in this document) and added to a database of 3D information that includes the 3D locations of objects in its view but also image (e.g., color) information about those 3D objects. In the illustrated example, a colorized 3D model of the door 920 could be rendered based on the UAV observations at the location 901a.

[0103] Continuing the illustrated example, the UAV 910 can be flown through the door 920 to a location 901b. In some implementations, the flight path of the UAV 910 can be determined at least partly based on the 3D information collected at the location 901a. For example, the 3D size and location of the door 920 can be determined, and a flight path can be plotted to take the UAV 910 thought the door 920 with the least possibility for a collision (e.g., through the middle of the opening rather than near the door frame).

[0104] At various points along the flight path from the location 901a to 901b, the UAV 910 performs image capture and range measurement operations. Pairs of such images are compared, and the range measurements are combined with them to determine portions of a 3D model of the space 900. As additional information is collected, the 3D model is expanded. The collection process continues at and between additional locations 901b-901e to build up a colorized or otherwise (e.g., infrared) visually representative 3D model of the space 900.

[0105] In some implementations, a single UAV can be used. For example, the UAV 910 can be flown to the various locations 901a-901e to collect information. In some implementations, multiple UAV (e.g., a “swarm”) can be used. For example, five UAVs similar to the UAV 910 can be flown to the locations 901a-901e to collect information at substantially the same time. In some embodiments of swarms, each UAV may report its information directly (e.g., star topology) to a remote, central workstation, and the workstation can be configured to assemble the information from multiple UAVs into a common 3D model. In some embodiments of swarms, the UAVs may be in communication with each other (e.g., mesh topology), in which each UAV can act not only as an information gathering device, but also as a repeater that can extend and/or improve the reach of communications to a remote workstation. For example, the location 901e may be out of direct communications range from the location 901a, but locations 901b-901e for mesh-enabled UAVs can be at least partly determined to ensure that each UAV is within communications range of at least one other UAV. In such an example, the UAV at 901c may act as a repeater for communications between a UAV at location 901a and location 901e. If the UAV at 901c is disabled, the UAV at location 901d may automatically take over the role as repeater to reconfigure the logical topology of the mesh network, and/or the UAV at location 901b may be automatically repositioned (e.g., within range of locations 901 a and 901e) to reconfigure the physical topology of the mesh network.

[0106] In some implementations, the locations 901a-901e can be determined at least partly based on information collected about others of the locations 901a-901e. For example, from the perspective of 901a, the door 920 and the space beyond it can be seen. 3D point image and range information about the shape and color of the door 920 can be gathered based on this vantage point. The robust information collected about the door 920 is considered to be “point dense”. Observable objects beyond the door have less resolution due to their distance, and objects to the sides of the door 920 cannot be observed. The sparse of nonexistent information collected about the background and hidden objects is considered to be “point scarce”. The relative point density and/or scarcity of the collected information can then be used to manually, semi-autonomously, or autonomously guide UAVs to “point scarce” locations in order to collect more information to increase the point density, and therefore the fidelity, of the 3D model in those locations. This process can continue or be repeated until a predetermined point density level is achieved.

[0107] FIG. 10 is a flow diagram of an example process 1000 for mapping a three dimensional environment. In some implementations, the process 1000 can be performed by all of part of the example UAS 100 or the example UAV 101 of FIG. 1, the example UAV 200 of FIGS. 2-4, or the example UAV 910 of FIG. 9. In some implementations, the process 1000 can be all or some of the example processes discussed in the descriptions of FIGS. 5-8.

[0108] At 1010, a two-dimensional first image of a three-dimensional scene is captured at a first location. In some implementations, capturing the first two-dimensional image can include capturing, by an image sensor positioned at the first location by an unmanned aerial system (UAS), the first two-dimensional image. For example, the UAV 200 can capture an image of the 3D environment 300 at a first location, as shown in FIG. 3.

[0109] At 1020, a two-dimensional second image of the three-dimensional scene is captured at a second location. In some implementations, capturing the second two-dimensional image can include capturing, by the image sensor positioned at the second location by the UAS, the second two-dimensional image. For example, the UAV 200 can capture an image of the 3D environment 300 at a location that is offset from the first location, as shown in FIG. 4.

[0110] At 1030, a range distance is measured from at least one of the first location and the second location to a closest object in the scene. In some implementations, measuring the range distance can include measuring, by a range sensor positioned by the UAS, the range distance. For example, the UAV 200 can measure the distance from the UAV 200 to the objects 301a-301c, as shown in FIG. 4.

[0111] At 1040, a depth map is determined based on differences between the first image and the second image. For example, the example depth map 610 of FIG. 6 can be determined from the difference map 630 determined from the first image 510a and the second image 501b.

[0112] At 1050, a three-dimensional point cloud is determined based on the range distance, the depth map, and at least one of the first image and the second image. For example, the example point array 630 (e.g., point cloud) of FIG. 7 can be determined based on the range measurement 520 of FIGS. 5 and 6, the depth map 610, and the image 510b.

[0113] At 1060, the three-dimensional point cloud is provided as a three-dimensional model of the three-dimensional scene. For example, the example 3D model 710 of FIG. 7 can be provided as a 3D pseudo-3D representation on a computer display (e.g., the workstation 102) of the scene 310b. The representation can be viewed and/or manipulated by a user, such as to remotely preview the 3D environment 300 of FIGS. 3-4, and/or to plot flight paths for the UAV 910 in the example of FIG. 9.

[0114] In some implementations, the process 900 can also include capturing, at a third location, a two-dimensional third image of the three-dimensional scene, a second range distance can be measured between the third location and another closest object in the scene, a second depth map can be determined based on differences between the third image and one of the first image and the second image, a second three-dimensional point cloud can be determined based on the second range distance, the second depth map, and the third image, and the three-dimensional model can be expanded based on the second three-dimensional point cloud. For example, the UAV 200 may offset to another vantage point different from the positions shown in FIGS. 3 and 4, and a third image of the 3D environment 300 can be captured and another range measurement can be taken. This third image can be compared to a previous image (e.g., the second image 510b) to determine another point array, such as the example point array 810n of FIG. 8. The point array 810n can be merged (e.g., 820) with previous point arrays (e.g., point arrays 810a-810_n-1 to expand the 3D model 830.

[0115] In some implementation, capturing the first two-dimensional image can include capturing, by a first image sensor positioned at the first location by a first unmanned aerial system (UAS), the first two-dimensional image, capturing the second two-dimensional image can include capturing, by a second image sensor positioned at the second location by a second UAS, the second two-dimensional image, and measuring the range distance can include measuring, by a range sensor positioned by the first UAS or the second UAS, the range distance. For example, in FIG. 3, the scene 310a can be captured by the UAV 200, and in FIG. 4, the scene 310b can be captured by a different UAV or UAS working in cooperation (e.g., swarm) with the UAV 200.

[0116] In some implementations, determining a three-dimensional point cloud can include determining a two-dimensional collection of difference values by comparing the first image and the second image, grouping the difference values into subsets of points having similar difference values, identifying a subset from the grouped subsets, associating the range depth with the identified subset, determining depths of other subsets of points based on an extrapolation of the depth, the difference values of the identified subset, and the difference values of the other subsets, and creating the three-dimensional point cloud based on the determined depths. For example, the values of the depth map 610 can be grouped based on their relative distance, and such groupings may be treated as a continuous surface since their similar values may suggest that the groupings represent a single object or a continuous grouping of objects at the same distance from the UAV.

[0117] In some implementations, for one or more difference values in the collection of depths, the difference value can be selected, the two-dimensional location of the selected difference value can be determined, a two-dimensional location in least one of the first image and the second image that corresponds to the determined two-dimensional location can be identified, one or more image characteristics of the identified location can be identified in which the image characteristics can selected from a group including color values and luminance values, the identified image characteristic and the selected difference value can be associated with the determined two-dimensional location, wherein creating the three-dimensional point cloud based on the determined depths is further based on the image characteristics and the selected difference values associated with the determined two-dimensional locations, such that one or more points of the point cloud each have a three dimensional position and one or more image characteristics. For example, as discussed in the description of FIG. 7, the depth values from the depth map 610 can be merged (720) with color (and/or luminance) values from corresponding pixels of the second image 510b to create a colorized depth map such as the point array 730.

[0118] In some implementations, the process 1000 can also include determining a flight path based on the three-dimensional model, and navigating an unmanned aerial system based on the determined flight path. In some implementations, the process 1000 can also include identifying a portion of the three-dimensional point cloud having a relatively lower point density than other portions of the three-dimensional point cloud, and identifying a three-dimensional location based on the identified portion, wherein the flight path includes the identified three-dimensional location. For example, the UAV 910 can collect information from the space 900 to recreate at least a partial 3D model of the space 900, and the partial model can be used to determine a flight path for the UAV 910 through the space 900, for example, to fly safely around obstacles in the space 900 and/or to explore areas of low point density in order to expand and improve the resolution of the 3D model.

[0119] In some implementations, the process 1000 can also include capturing, at the identified three-dimensional location, a two-dimensional third image of the three-dimensional scene, measuring a second range distance between the identified three-dimensional location and another closest object in the scene, determining a second depth map based on differences between the third image and one of the first image and the second image, determining a second three-dimensional point cloud based on the second range distance, the second depth map, and the third image, and increasing the point density of the three-dimensional point cloud based on the second three-dimensional point cloud. For example, the UAV 910 can collect information from the space 900 to recreate at least a partial 3D model of the space 900, and the partial model can be used to determine a flight path for the UAV 910 through the space 900, to explore areas of low point density. Additional images and distance measurements taken at the explored locations can be compared to and merged with previously collected information in order to expand and improve the resolution of the 3D model.

[0120] FIG. 11 is a block diagram of computing devices 1100, 1150 that may be used to implement the systems and methods described in this document, either as a client or as a server or plurality of servers. Computing device 1100 is intended to represent various forms of digital computers, such as laptops, desktops, workstations, personal digital assistants, servers, blade servers, mainframes, and other appropriate computers. Computing device 1150 is intended to represent various forms of mobile devices, such as personal digital assistants, cellular telephones, smartphones, and other similar computing devices. The components shown here, their connections and relationships, and their functions, are meant to be exemplary only, and are not meant to limit implementations of the inventions described and/or claimed in this document.

[0121] Computing device 1100 includes a processor 1102, memory 1104, a storage device 1106, a high-speed interface 1108 connecting to memory 1104 and high-speed expansion ports 1110, and a low speed interface 1112 connecting to low speed bus 1114 and storage device 1106. Each of the components 1102, 1104, 1106, 1108, 1110, and 1112, are interconnected using various busses, and may be mounted on a common motherboard or in other manners as appropriate. The processor 1102 can process instructions for execution within the computing device 1100, including instructions stored in the memory 1104 or on the storage device 1106 to display graphical information for a GUI on an external input/output device, such as display 1116 coupled to high speed interface 1108. In other implementations, multiple processors and/or multiple buses may be used, as appropriate, along with multiple memories and types of memory. Also, multiple computing devices 1100 may be connected, with each device providing portions of the necessary operations (e.g., as a server bank, a group of blade servers, or a multi-processor system).

[0122] The memory 1104 stores information within the computing device 1100. In one implementation, the memory 1104 is a computer-readable medium. In one implementation, the memory 1104 is a volatile memory unit or units. In another implementation, the memory 1104 is a non-volatile memory unit or units.

[0123] The storage device 1106 is capable of providing mass storage for the computing device 1100. In one implementation, the storage device 1106 is a computer-readable medium. In various different implementations, the storage device 1106 may be a floppy disk device, a hard disk device, an optical disk device, or a tape device, a flash memory or other similar solid state memory device, or an array of devices, including devices in a storage area network or other configurations. In one implementation, a computer program product is tangibly embodied in an information carrier. The computer program product contains instructions that, when executed, perform one or more methods, such as those described above. The information carrier is a computer- or machine-readable medium, such as the memory 1104, the storage device 1106, or memory on processor 1102.

[0124] The high speed controller 1108 manages bandwidth-intensive operations for the computing device 1100, while the low speed controller 1112 manages lower bandwidth-intensive operations. Such allocation of duties is exemplary only. In one implementation, the high-speed controller 1108 is coupled to memory 1104, display 1116 (e.g., through a graphics processor or accelerator), and to high-speed expansion ports 1110, which may accept various expansion cards (not shown). In the implementation, low-speed controller 1112 is coupled to storage device 1106 and low-speed expansion port 1114. The low-speed expansion port, which may include various communication ports (e.g., USB, Bluetooth, Ethernet, wireless Ethernet) may be coupled to one or more input/output devices, such as a keyboard, a pointing device, a scanner, or a networking device such as a switch or router, e.g., through a network adapter.

[0125] The computing device 1100 may be implemented in a number of different forms, as shown in the figure. For example, it may be implemented as a standard server 1120, or multiple times in a group of such servers. It may also be implemented as part of a rack server system 1124. In addition, it may be implemented in a personal computer such as a laptop computer 1122. Alternatively, components from computing device 1100 may be combined with other components in a mobile device (not shown), such as device 1150. Each of such devices may contain one or more of computing device 1100, 1150, and an entire system may be made up of multiple computing devices 1100, 1150 communicating with each other.

[0126] Computing device 1150 includes a processor 1152, memory 1164, an input/output device such as a display 1154, a communication interface 1166, and a transceiver 1168, among other components. The device 1150 may also be provided with a storage device, such as a microdrive or other device, to provide additional storage. Each of the components 1150, 1152, 1164, 1154, 1166, and 1168, are interconnected using various buses, and several of the components may be mounted on a common motherboard or in other manners as appropriate.

[0127] The processor 1152 can process instructions for execution within the computing device 1150, including instructions stored in the memory 1164. The processor may also include separate analog and digital processors. The processor may provide, for example, for coordination of the other components of the device 1150, such as control of user interfaces, applications run by device 1150, and wireless communication by device 1150.

[0128] Processor 1152 may communicate with a user through control interface 1158 and display interface 1156 coupled to a display 1154. The display 1154 may be, for example, a TFT LCD display or an OLED display, or other appropriate display technology. The display interface 1156 may include appropriate circuitry for driving the display 1154 to present graphical and other information to a user. The control interface 1158 may receive commands from a user and convert them for submission to the processor 1152. In addition, an external interface 1162 may be provide in communication with processor 1152, so as to enable near area communication of device 1150 with other devices. External interface 1162 may provide, for example, for wired communication (e.g., via a docking procedure) or for wireless communication (e.g., via Bluetooth or other such technologies).

[0129] The memory 1164 stores information within the computing device 1150. In one implementation, the memory 1164 is a computer-readable medium. In one implementation, the memory 1164 is a volatile memory unit or units. In another implementation, the memory 1164 is a non-volatile memory unit or units. Expansion memory 1174 may also be provided and connected to device 1150 through expansion interface 1172, which may include, for example, a SIMM card interface. Such expansion memory 1174 may provide extra storage space for device 1150, or may also store applications or other information for device 1150. Specifically, expansion memory 1174 may include instructions to carry out or supplement the processes described above, and may include secure information also. Thus, for example, expansion memory 1174 may be provide as a security module for device 1150, and may be programmed with instructions that permit secure use of device 1150. In addition, secure applications may be provided via the SIMM cards, along with additional information, such as placing identifying information on the SIMM card in a non-hackable manner.

[0130] The memory may include for example, flash memory and/or MRAM memory, as discussed below. In one implementation, a computer program product is tangibly embodied in an information carrier. The computer program product contains instructions that, when executed, perform one or more methods, such as those described above. The information carrier is a computer- or machine-readable medium, such as the memory 1164, expansion memory 1174, or memory on processor 1152.

[0131] Device 1150 may communicate wirelessly through communication interface 1166, which may include digital signal processing circuitry where necessary. Communication interface 1166 may provide for communications under various modes or protocols, such as GSM voice calls, Voice Over LTE (VOLTE) calls, SMS, EMS, or MMS messaging, CDMA, TDMA, PDC, WCDMA, CDMA2000, GPRS, WiMAX, LTE, among others. Such communication may occur, for example, through radio-frequency transceiver 1168. In addition, short-range communication may occur, such as using a Bluetooth, WiFi, or other such transceiver (not shown). In addition, GPS receiver module 1170 may provide additional wireless data to device 1150, which may be used as appropriate by applications running on device 1150.

[0132] Device 1150 may also communication audibly using audio codec 1160, which may receive spoken information from a user and convert it to usable digital information. Audio codex 1160 may likewise generate audible sound for a user, such as through a speaker, e.g., in a handset of device 1150. Such sound may include sound from voice telephone calls, may include recorded sound (e.g., voice messages, music files, etc.) and may also include sound generated by applications operating on device 1150.

[0133] The computing device 1150 may be implemented in a number of different forms, as shown in the figure. For example, it may be implemented as a cellular telephone 1180. It may also be implemented as part of a smartphone 1182, personal digital assistant, or other similar mobile device.

[0134] Various implementations of the systems and techniques described here can be realized in digital electronic circuitry, integrated circuitry, specially designed ASICs (application specific integrated circuits), computer hardware, firmware, software, and/or combinations thereof. These various implementations can include implementation in one or more computer programs that are executable and/or interpretable on a programmable system including at least one programmable processor, which may be special or general purpose, coupled to receive data and instructions from, and to transmit data and instructions to, a storage system, at least one input device, and at least one output device.

[0135] These computer programs (also known as programs, software, software applications or code) include machine instructions for a programmable processor, and can be implemented in a high-level procedural and/or object-oriented programming language, and/or in assembly/machine language. As used herein, the terms “machine-readable medium” “computer-readable medium” refers to any computer program product, apparatus and/or device (e.g., magnetic discs, optical disks, memory, Programmable Logic Devices (PLDs)) used to provide machine instructions and/or data to a programmable processor, including a machine-readable medium that receives machine instructions as a machine-readable signal. The term “machine-readable signal” refers to any signal used to provide machine instructions and/or data to a programmable processor.

[0136] To provide for interaction with a user, the systems and techniques described here can be implemented on a computer having a display device (e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor) for displaying information to the user and a keyboard and a pointing device (e.g., a mouse or a trackball) by which the user can provide input to the computer. Other kinds of devices can be used to provide for interaction with a user as well; for example, feedback provided to the user can be any form of sensory feedback (e.g., visual feedback, auditory feedback, or tactile feedback); and input from the user can be received in any form, including acoustic, speech, or tactile input.

[0137] The systems and techniques described here can be implemented in a computing system that includes a back end component (e.g., as a data server), or that includes a middleware component (e.g., an application server), or that includes a front end component (e.g., a client computer having a graphical user interface or a Web browser through which a user can interact with an implementation of the systems and techniques described here), or any combination of such back end, middleware, or front end components. The components of the system can be interconnected by any form or medium of digital data communication (e.g., a communication network). Examples of communication networks include a local area network (“LAN”), a wide area network (“WAN”), and the Internet.

[0138] The computing system can include clients and servers. A client and server are generally remote from each other and typically interact through a communication network. The relationship of client and server arises by virtue of computer programs running on the respective computers and having a client-server relationship to each other.

[0139] A number of embodiments of the invention have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the invention. For example, various forms of the flows shown above may be used, with steps re-ordered, added, or removed. Also, although several applications of the payment systems and methods have been described, it should be recognized that numerous other applications are contemplated. Accordingly, other embodiments are within the scope of the following claims.