Case 2:20-cv-03827-AB-AFM Document 1-1 Filed 04/27/20 Page 1 of 23 Page ID #:15
`Case 2:20-cv-03827-AB-AFM Document 1-1 Filed 04/27/20 Page 1 of 23 Page ID #:15
`
`
`
`
`
`
`
`EXHIBIT A
`
`EXHIBIT A
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-1 Filed 04/27/20 Page 2 of 23 Page ID #:16
`
`US008965598B2
`
`(12) United States Patent
`Kruglick
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 8,965,598 B2
`Feb. 24, 2015
`
`USPC ...................... 701/2, 3, 13, 24, 36, 31.4, 300;
`244f75.1
`See application file for complete search history.
`References Cited
`U.S. PATENT DOCUMENTS
`
`gigan,
`
`(Continued)
`
`(54) AUTOMATIC FLIGHT CONTROL FOR UAV
`BASED SOLID MODELING
`(75) Inventor: Ezekiel Kruglick, Poway, CA (US)
`(73) Assignee: Empire Technology Development LLC,
`Wilmington, DE (US)
`
`(56)
`
`'' " SEME" is a
`
`U.S.C. 154(b) by 97 days.
`
`wk -
`
`13/054,882
`Sep. 30, 2010
`PCT/US2010/050829
`
`(21) Appl. No.:
`(22) PCT Filed:
`(86). PCT No.:
`S371 (c)(1),
`Aug. 12, 2013
`(2), (4) Date:
`(87) PCT Pub. No.: WO2012/044297
`PCT Pub. Date: Apr. 5, 2012
`
`FOREIGN PATENT DOCUMENTS
`
`AU
`EP
`
`9, 2010
`2010219.335
`1020
`211260
`(Continued)
`OTHER PUBLICATIONS
`International Preliminary Reporton Patentability issued Apr. 2, 2013.
`(Continued)
`
`(65)
`
`Prior Publication Data
`US 2013/0317667 A1
`Nov. 28, 2013
`
`Primary Examiner — Gertrude Arthur Jeanglaude
`(74) Attorney, Agent, or Firm — Turk IP Law, LLC
`
`(51) Int. Cl.
`G05D3/00
`B64C 9/00
`
`(2006.01)
`(2006.01)
`(Continued)
`(52) U.S. Cl.
`CPC ............... B64C 19/00 (2013.01); B64C39/024
`(2013.01); G05D I/0094 (2013.01); G05D
`I/101 (2013.01); G06T 1705 (2013.01); G06T
`17/10 (2013.01); B64C 220 1/127 (2013.01);
`B64C 220 1/146 (2013.01)
`USPC ..................... 701/2; 701/3: 701/13; 24.4/75.1
`(58) Field of Classification Search
`CPC .............. B64C 19/00; B64C 2201/127; B64C
`2201/146; B64C39/024; G05D 1/101; G06T
`17/05
`
`ABSTRACT
`(57)
`Technologies are generally described for controlling a flight
`path of a UAV based image capture system for solid model
`ing. Upon determining an initial movement path based on an
`estimate of a structure to be modeled, images of the structure
`to be modeled may be captured and surface hypotheses
`formed for unobserved surfaces based on the captured
`images. A normal vector and a viewing cone may be com
`puted for each hypothesized surface. A set of desired loca
`tions may be determined based on the viewing cones for the
`entire structure to be modeled and a least impact path for the
`UAV determined based on the desired locations and desired
`flight parameters.
`
`21 Claims, 11 Drawing Sheets
`
`
`
`- 100
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-1 Filed 04/27/20 Page 3 of 23 Page ID #:17
`
`US 8,965,598 B2
`Page 2
`
`(51) Int. Cl.
`B64C39/02
`G05D I/00
`G05D L/10
`G06T I7/05
`G06T 7/10
`
`(2006.01)
`(2006.01)
`(2006.01)
`(2011.01)
`(2006.01)
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,628,354
`4,802,757
`5,104,217
`5,289,185
`5,602.586 A
`6,272.404 B1
`6,972,696 B2
`7,009,638 B2
`7,339,614 B2
`7,342,670 B2
`7,509,241 B2
`7,630,797 B2
`8,355,834 B2*
`8,768,555 B2*
`2003, OO14224 A1
`2008.0125920 A1
`2009, O256909 A1
`2009,0263009 A1
`2010, 0004802 A1
`2010.0013927 A1
`
`12, 1986
`2, 1989
`4, 1992
`2, 1994
`2, 1997
`8, 2001
`12, 2005
`3, 2006
`3, 2008
`3, 2008
`3, 2009
`12, 2009
`1, 2013
`T/2014
`1, 2003
`5/2008
`10, 2009
`10, 2009
`1, 2010
`1, 2010
`
`Nagura
`Pleitner et al.
`Pleitner et al.
`Ramier et al.
`Schauer et al.
`Amano et al.
`Rogers et al.
`Gruber et al.
`Gruber et al.
`Teichman
`Gou et al.
`Garceau et al.
`Duggan et al. .................. TO1/24
`Duggan et al. .................. TO1/24
`Guo et al.
`Miles et al.
`Nixon
`Krishnaswamy et al.
`Bodin et al.
`Nixon
`
`FOREIGN PATENT DOCUMENTS
`
`WO
`WO
`
`2006/037237
`2009.125304
`
`4/2006
`10/2009
`
`OTHER PUBLICATIONS
`Punchcard VideoTrace, Modelling a House, http://punchcard.com.
`au/wordpress/?p=12.
`Punchcard: VideoTrace, Image-based Modelling for All, http://
`tinyurl.com/y96q52c.
`Andert, et al. Online World Modeling and Path Planning for an
`Unmanned Helicopter, Autonomous Robot (2009) 27: 147-164.
`Metni et al., A UAV for Bridge Inspection: Visual Serving Control
`Law with Orientation Limits, Automation in Construction, vol. 17,
`#1, (2007) pp. 3-10.
`Faviet al., Techniques for Fully Integrated Intra-/Inter-Chip Optical
`Communication, Proceedings of the 45th annual Design Automation
`Conference, Anaheim, California (2008) 2 pages.
`Fischler et al., Random Sample Consensus: A Paradigm for Model
`Fitting with Applications to Image Analysis and Automated Cartog
`raphy. Commun. ACM, 24(6):381-395, 1981.
`Quirk et al., RANSAC-Assisted Display Model Reconstruction for
`Projective Display, Department of Computer Science University of
`North Carolina at Chapel Hill, 4 pages.
`International Search Report & Written Opinion dated Jan. 4, 2011 in
`PCT/US 10/050829.
`
`* cited by examiner
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-1 Filed 04/27/20 Page 4 of 23 Page ID #:18
`
`U.S. Patent
`
`Feb. 24, 2015
`
`Sheet 1 of 11
`
`US 8,965,598 B2
`
`3
`
`
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-1 Filed 04/27/20 Page 5 of 23 Page ID #:19
`
`U.S. Patent
`
`US 8,965,598 B2
`
`00Z
`
`.
`
`
`
`
`
`Z "SOIH
`
`ZZZ
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-1 Filed 04/27/20 Page 6 of 23 Page ID #:20
`
`U.S. Patent
`
`Feb. 24, 2015
`
`Sheet 3 of 11
`
`US 8,965,598 B2
`
`3
`
`
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-1 Filed 04/27/20 Page 7 of 23 Page ID #:21
`
`U.S. Patent
`
`Feb. 24, 2015
`
`Sheet 4 of 11
`
`US 8,965,598 B2
`
`
`
`
`
`997
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-1 Filed 04/27/20 Page 8 of 23 Page ID #:22
`
`U.S. Patent
`
`Feb. 24, 2015
`
`Sheet 5 of 11
`
`US 8,965,598 B2
`
`
`
`
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-1 Filed 04/27/20 Page 9 of 23 Page ID #:23
`
`U.S. Patent
`
`Feb. 24, 2015
`
`Sheet 6 of 11
`
`US 8,965,598 B2
`
`
`
`&
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-1 Filed 04/27/20 Page 10 of 23 Page ID #:24
`
`U.S. Patent
`
`Feb. 24, 2015
`
`Sheet 7 of 11
`
`US 8,965,598 B2
`
`- 700
`
`
`
`FIG. 7
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-1 Filed 04/27/20 Page 11 of 23 Page ID #:25
`
`U.S. Patent
`
`Feb. 24, 2015
`
`Sheet 8 of 11
`
`US 8,965,598 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Z8 ÅRHOWE'W
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-1 Filed 04/27/20 Page 12 of 23 Page ID #:26
`
`U.S. Patent
`
`Feb. 24, 2015
`
`Sheet 9 of 11
`
`US 8,965,598 B2
`
`(S)>{HONALEN
`
`õ55
`
`
`
`
`
`
`
`6 "SDI
`
`^_006
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-1 Filed 04/27/20 Page 13 of 23 Page ID #:27
`
`U.S. Patent
`
`Feb. 24, 2015
`
`Sheet 10 of 11
`
`US 8,965,598 B2
`
`
`
`COMPUTENG DEVICE OO
`
`COMPUTER-READABLE MEDUM 1020
`
`START WITH PREDEFINED PATH
`
`are
`
`reper
`
`repea
`
`are
`
`are
`
`area are
`
`1024
`DETERMNE MOVEMENT PATH
`
`1026
`CAPTURE VIDEO FROM MOBE
`PLATFORM
`
`1028
`OCATION NFO
`
`103
`EXTRACT MOTON 8.
`TRACKNG PONTS
`
`1032
`FORM SURFACE HYPOTHESES
`
`1034
`COMPUTE SURFACE NORMAL
`CONES
`
`1036
`DETERMNE DES RED OCAONS
`
`1038
`OPTIMIZE DESERED LOCATONSWS.
`FIGHT PARAMETERS
`
`FIG. 10
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-1 Filed 04/27/20 Page 14 of 23 Page ID #:28
`
`U.S. Patent
`
`Feb. 24, 2015
`
`Sheet 11 of 11
`
`US 8,965,598 B2
`
`
`
`COMPUTER PROGRAM PRODUCT 11 O
`
`SGNA-BEARNG MEDUM 11 O2
`
`11 O4 AT EAST ONE OF
`
`ONE OR MORE NSTRUCTIONS FOR FORMING
`SURFACE HYPOTHESES;
`ONE OR MORE NSTRUCTIONS FOR EXTRACTING
`iMAGES FROM MOBILE PLATFORM
`ONE OR MORE NSTRUCTIONS FOR DETERMINING
`MISSING SURFACE(S);
`ONE OR MORE NSTRUCTIONS FOR ADJUSTING
`MOVEMENT PATH
`
`READABLE
`MEDUM
`
`is see as a see -e see a ve
`
`COMMUNICATIONS
`MEDUM
`
`FIG. 11
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-1 Filed 04/27/20 Page 15 of 23 Page ID #:29
`
`1.
`AUTOMATIC FLIGHT CONTROL FOR UAV
`BASED SOLID MODELING
`
`US 8,965,598 B2
`
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`
`This Application is the National Stage filing under 35
`US.C. S371 of PCT Application Ser. No. PCT/US 10/50829
`filed on Sep. 30, 2010. The disclosure of the PCT Application
`is hereby incorporated by reference in its entirety.
`
`10
`
`BACKGROUND
`
`15
`
`25
`
`35
`
`Unless otherwise indicated herein, the materials described
`in this section are not prior art to the claims in this application
`and are not admitted to be prior art by inclusion in this section.
`Airborne unmanned camera platforms based on
`Unmanned Aerial Vehicles (UAVs) have various law enforce
`ment, firefighting, search and rescue, inspection, and televi
`sion broadcast applications. By installing a wirelessly acces
`sible camera (digital or analog) on a UAV that is remotely
`controlled, high cost and high maintenance manned aircraft
`(planes, helicopters) are no longer needed. In addition to
`reducing setup/operation cost and risk to humans, UAV based
`camera platforms enable safe operations where manned air
`craft may not be able to go. For example, manned aircraft are
`typically not allowed to fly within about 500 ft. of the ground,
`while small UAVs are commonly limited to altitudes below
`about 500 ft. Thus UAVs have an inspection advantage. UAV
`based platforms also enable use of different types and quality
`30
`of image capture equipment. Analog or digital cameras of
`various resolution capabilities may be installed on UAVs even
`between flights.
`One example application of UAV based camera platforms
`is in the inspection industry. For pre- or post-construction
`inspections of large or Small structures, a UAV based camera
`platform may be used eliminating the need for inspectors to
`climb on structures or otherwise placing themselves at risk.
`Moreover, natural impediments such as weather do not affect
`UAV operations as they would with humans. UAV operations
`are, however, Subject to various limitations.
`The present disclosure appreciates that there are numerous
`limitations with UAV based image capture systems. For
`example, power (fuel or electric) is typically limited. Noise
`and flight path restrictions due to regulatory regulations have
`to be considered in determining a flight path of the UAV.
`Furthermore, operation time and cost may increase if a UAV
`has to fly around a structure repeatedly to capture aspects of
`the structure not captured during earlier flights. With sophis
`ticated flight control software and extensive training, UAV
`50
`operations may be optimized, but given the trend to simplify
`UAVs and their controllers (e.g., smart phone based UAV
`controllers are becoming popular), complex control Software
`and specialized training increase the cost and limit the use of
`Such systems.
`
`40
`
`45
`
`55
`
`SUMMARY
`
`The present disclosure describes an automatic unmanned
`aerial vehicle (UAV) flight control system for solid modeling.
`The system includes a UAV with an onboard camera and a
`controller capable of communicating with the UAV via wire
`less means. According to Some examples, the controller may
`determine an initial movement path based on an estimate of a
`structure to be modeled, capture images of the structure to be
`modeled, form surface hypotheses for unobserved surfaces
`based on the captured images, determine missing Surface
`
`60
`
`65
`
`2
`information from the Surface hypotheses, and determine a
`least impact path for the UAV based on the missing surface
`information and desired flight parameters.
`The present disclosure also provides a method for control
`ling a flight path of a UAV based image capture system for
`Solid modeling. The method may include determining an
`initial movement path based on an estimate of a structure to be
`modeled, capturing images of the structure to be modeled,
`forming Surface hypotheses for unobserved Surfaces based on
`the captured images, and computing a normal vector and a
`viewing cone for each hypothesized Surface. According to
`other examples, the method may further include determining
`a set of desired locations based on the viewing cones for the
`entire structure to be modeled and determining a least impact
`path for the UAV based on the desired locations and desired
`flight parameters.
`The present disclosure further describes a computer-read
`able storage medium having instructions stored thereon for
`controlling a flight path of an unmanned aerial vehicle (UAV)
`based image capture system for Solid modeling. The
`examples may include determining an initial movement path
`based on an estimate of a structure to be modeled, capturing
`images of the structure to be modeled, and guiding the flight
`path. According to further examples, the flight path may be
`guided by forming Surface hypotheses for unobserved Sur
`faces based on the captured images, computing a normal
`vector and a viewing cone for each hypothesized surface,
`determining a set of desired locations based on the viewing
`cones for the entire structure to be modeled, and determining
`a least impact path for the UAV based on the desired locations
`and one or more of a total flight time, available UAV energy,
`a noise limitation, and/or a user defined restriction for the
`UAV.
`The foregoing Summary is illustrative only and is not
`intended to be in any way limiting. In addition to the illustra
`tive aspects, embodiments, and features described above, fur
`ther aspects, embodiments, and features will become appar
`ent by reference to the drawings and the following detailed
`description.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The foregoing and other features of this disclosure will
`become more fully apparent from the following description
`and appended claims, taken in conjunction with the accom
`panying drawings. Understanding that these drawings depict
`only several embodiments in accordance with the disclosure
`and are, therefore, not to be considered limiting of its scope,
`the disclosure will be described with additional specificity
`and detail through use of the accompanying drawings, in
`which:
`FIG. 1 illustrates an example Unmanned Aerial Vehicle
`(UAV) controlled by a remote control device capturing
`images of a structure, where flight path of the UAV may be
`determined based on Solid modeling:
`FIG. 2 illustrates example major functional components in
`a UAV and its remote control device in an automatic flight
`control system;
`FIG. 3 illustrates two example flight paths for a UAV, a
`predefined one and another one based on least impact path
`and solid modeling techniques;
`FIG. 4 illustrates an example surface confidence determi
`nation for UAV navigation computation;
`FIG. 5 illustrates surface normal cones from a low quality
`Surface to be used in Surface confidence computation;
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-1 Filed 04/27/20 Page 16 of 23 Page ID #:30
`
`US 8,965,598 B2
`
`3
`FIG. 6 illustrates surface normal cones from unobserved
`and low quality Surfaces to be used in Surface confidence
`computation;
`FIG. 7 illustrates an example flight path selection for
`obtaining data on low data areas based on Surface normal
`cones for unobserved and/or low quality Surfaces;
`FIG. 8 illustrates a general purpose computing device,
`which may be used to determine navigational path(s) for a
`UAV capturing Surface images for Solid modeling:
`FIG. 9 illustrates a processor, which may be used to deter
`mine navigational path(s) for a UAV capturing Surface images
`for Solid modeling;
`FIG. 10 is a flow diagram illustrating an example method
`that may be performed by a computing device. Such as com
`puter 800 in FIG.8 or special purpose processor 910 in FIG.
`15
`9; and
`FIG.11 illustrates a block diagram of an example computer
`program product; all arranged in accordance with at least
`some embodiments described herein.
`
`10
`
`DETAILED DESCRIPTION
`
`4
`puting device 116 may be facilitated through wireless com
`munications. For example, the remote computing device 116
`may communicate with a wireless tower 112 through a net
`work 114. The wireless tower 112 may send flight path con
`trol commands 110 (and/or image capture control com
`mands) to the UAV 104 and receive responses 108 (captured
`images, responses to flight path control commands, telemetry
`data, etc.).
`The remote computing device 116 may be a desktop com
`puter, a laptop computer, a vehicle mount computer, a hand
`held computer, a Smart phone, a server, or any comparable
`computing device. The remote computing device 116 may
`execute a flight control program and an image processing
`program as part of an integrated application or service. Alter
`natively, the remote computing device 116 may execute one
`or both of two separate applications: one for flight path con
`trol, the other for image processing. Using captured images to
`determine unobserved surfaces of the structure 102, the
`remote computing device 116 may determine a set of desired
`locations for the UAVs flight path to include, and determine
`the flight path based on the desired locations and flight param
`eters for the UAV such as fuel use, noise, and similar restric
`tions. The new flight path may be sent to the UAV and
`adjusted dynamically as new images are captured.
`FIG. 2 illustrates example major functional components in
`a UAV and its remote control device in an automatic flight
`control system arranged in accordance with at least some
`embodiments. A UAV based image capture system with
`dynamic adjustment of flight path based on analysis of cap
`tured images may be implemented by distinct or integrated
`software and/or hardware modules. The modules may be
`included in one or more computing devices (e.g., a server
`executing the image processing operations and a handheld
`device executing the flight control computations communi
`catively coupled over one or more networks). The system
`illustrated in diagram 200 is an example system. Embodi
`ments may be implemented with fewer or additional modules
`and hardware configurations.
`In the example system, a UAV 204 may include mechanical
`and electronic flight control mechanisms 222 Such as
`motor(s), servo(s), fuel control Switches, etc. associated with
`various flight operations of the UAV 204. An onboard flight
`control module 226 may receive flight control instructions
`from a remote computing device 216, control relevant flight
`control mechanisms, and provide feedback information (e.g.,
`telemetry information) to the remote computing device 216.
`The UAV 204 may further include an onboard camera 224
`coupled to an image capture module 228. The image capture
`module 228 may simply transmit captured images to the
`remote computing device 216, store the captured images,
`and/or process the captured images depending on a complex
`ity and configuration of the system. The image capture mod
`ule 228 may also be used to adjust operational parameters,
`Such as resolution, of the onboard camera 224.
`The remote computing device 216 may include a flight
`control module 232 for processing received feedback from
`the UAV and providing flight control instructions to the UAV
`to dynamically adjust its flight operations. An image process
`ing module 234 may receive captured images from the image
`capture module 228, process the images, and provide infor
`mation to a processor 230 such that the flight path of the UAV
`can be dynamically adjusted based on observed surfaces of a
`structure (or object) in order to cover unobserved surfaces.
`According to Some embodiments, the processor 230 may
`hypothesize Surface normals and view cones of unobserved
`surfaces based on the observed surfaces and determine a set of
`desired locations to be included in the UAVs flight path. The
`
`25
`
`30
`
`35
`
`In the following detailed description, reference is made to
`the accompanying drawings, which form a parthereof. In the
`drawings, similar symbols typically identify similar compo
`nents, unless context dictates otherwise. The illustrative
`embodiments described in the detailed description, drawings,
`and claims are not meant to be limiting. Other embodiments
`may be utilized, and other changes may be made, without
`departing from the spirit or scope of the Subject matter pre
`sented herein. It will be readily understood that the aspects of
`the present disclosure, as generally described herein, and
`illustrated in the Figures, can be arranged, Substituted, com
`bined, separated, and designed in a wide variety of different
`configurations, all of which are explicitly contemplated
`herein.
`This disclosure is generally drawn, interalia, to methods,
`apparatus, systems, devices, and/or computer program prod
`ucts related to controlling the flight path of a UAV based on
`hypothesized surfaces and computed set of desired location
`40
`associated with a structure to be observed by the UAV.
`Briefly stated, a UAV based image capture system may be
`implemented on a computing device for control of a mobile
`remote camera to provide a path of images in order to facili
`tate generation of three dimensional (3D) models. While
`examples are described using unmanned aerial vehicles,
`embodiments may also be implemented with remote con
`trolled land-based or marine-based vehicles. The flight path
`of a UAV may be controlled and dynamically modified path
`such that the UAV observes all the surfaces of a central object
`by receiving data on hypothesized surface normals and view
`cones of unobserved surfaces.
`FIG. 1 illustrates an example Unmanned Aerial Vehicle
`(UAV) controlled by a remote control device capturing
`images of a structure, where flight path of the UAV may be
`determined based on Solid modeling in accordance with at
`least some embodiments.
`A UAV based image capturing system Such as the one
`shown in diagram 100 may be used to capture images and/or
`model natural or manmade structures like houses, Schools,
`office buildings, etc. In diagram 100, the example system
`includes a UAV 104 with an onboard camera 106 flying over
`a structure 102 and capturing its images from various angles.
`A flight path of the UAV 104 may be controlled and captured
`images downloaded to an image processing program
`executed on a remote computing device 116 or a server 118.
`Communication between the UAV 104 and the remote com
`
`50
`
`45
`
`55
`
`60
`
`65
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-1 Filed 04/27/20 Page 17 of 23 Page ID #:31
`
`US 8,965,598 B2
`
`10
`
`15
`
`6
`complete a model for the structure, may be determined based
`on the normals and view angles computed from the hypoth
`esized Surfaces.
`The representations 444 and 446 are views based on
`images captured during a first camera pass. In addition to
`computing a best geometry, a confidence number may be
`generated for each Surface segment (shown in different
`shades of grey) in the synthetic image representation 448 to
`indicate the number of points that are collected. According to
`other embodiments, a Suitable confidence computation for
`UAV navigation may capture areas where more data is needed
`instead of a least squares matching for confidence. According
`to an example scenario, the Surface confidence may be com
`puted as the sum of the area proportion with point density
`below average and the ratio of the surface mean error to the
`Surface mean error on Surfaces closest to normal with the
`measured view. Thus, both the quality of the points and the
`proportion of the surface that has not been observed may be
`used in determining Surface confidence by a system accord
`ing to at least Some embodiments.
`The representation 444 illustrates two example areas of the
`structure (inner curve 452 and bottom surface 454), which are
`not observed during the first pass (hidden from the view). The
`representation 446 illustrates more areas (458, 460, and 456),
`which are shown in various shades of grey indicating respec
`tive confidence levels in those surfaces (with darker shades
`representing lower confidence). The representation 448 of the
`generated image illustrates different Surfaces of the structure
`with confidence numbers computed and symbolized by
`shades of grey (again with darker shades representing lower
`confidence).
`FIG. 5 illustrates surface normal cones from a low quality
`Surface to be used in Surface confidence computation in
`accordance with at least some embodiments. In diagram 500,
`the architectural structure of FIG. 4 is used to illustrate how
`Surface normal cones may be computed to determine desired
`locations for the UAV. While such locations may be distinct,
`a continuous set of locations may also be computed using a
`“goodness gradient’ as described below.
`Diagram 500 includes two views of a surface normal cone
`576 from a low quality surface 578 on an architectural struc
`ture 574. The left figure is a broad view and the right figure is
`from a perspective inside the cone facing the low quality
`surface 578 (shown as 462 in the previous figure). A single
`cone is shown in diagram 500 for clarity. The cone 576 is a
`draft extension generated from a vector normal from the low
`quality surface 578 with a defined view angle. The view angle
`for each system may be calculated based on the optical
`attributes of the capturing camera and a distance of the UAV
`to the structure so as to yield an estimated point density which
`provides a desired surface quality or resolution. For example,
`the angle may be selected to be a narrow angle for an inspec
`tion application and a wide angle for a general object mapping
`application. According to other embodiments, the angle may
`be computed as a goodness gradient determined dynamically
`by optical resolution, distance, lighting conditions, and/or
`similar parameters such that the path for the UAV can maxi
`mize the “goodness of the path (i.e., highest quality obser
`Vation for optimum flight parameters).
`FIG. 6 illustrates surface normal cones from unobserved
`and low quality surfaces (e.g., surfaces 458, 462.472, and the
`left half of 470 which may be considered a different poly
`gon than 470—of FIG. 4) to be used in surface confidence
`computation in accordance with at least some embodiments.
`Diagram 600 includes three views of multiple surface normal
`cones associated with the architectural structure 574 of
`FIG.S.
`
`5
`processor 230 may then determine a new (or adjusted) flight
`path based on a comparison of desired flight parameters (e.g.,
`restrictions such as available fuel, altitude, noise levels, etc.)
`and the desired locations.
`FIG. 3 illustrates two example flight paths for a UAV, a
`predefined one and another one based on least impact path
`and Solid modeling techniques in accordance with at least
`some embodiments. Without dynamic adjustment to cover
`unobserved surfaces, the flight path of a UAV may result in
`insufficient images of the structure to be observed. As shown
`in diagram 300, a predefined flight path 340 for a UAV 304
`may be rather simple, but the camera may not be able to
`capture details of various portions of a structure 302 such as
`depth of windows, sub-deck portions, etc. Even if the flight
`path is made relatively more complicated around the struc
`ture, dynamic conditions such as lighting may affect how well
`different portions of the structure can be observed. Thus,
`observation quality may be sacrificed if a predefined flight
`path is used. This in return may result in low quality modeling
`of the structure. For example, engineers attempting to model
`a complicated structure for assessment may not be able to
`capture details of certain three dimensional features.
`In a system according to embodiments, a flight path 342 of
`the UAV 304 may be dynamically adjusted by hypothesizing
`Surface normals and view cones of unobserved surfaces based
`on the observed Surfaces and determining a set of desired
`locations to be included in the UAV's flight path. An optimi
`Zation algorithm such as branch and bound optimization,
`Newton’s method, simulated annealing algorithm, differen
`tial evolution, and similar computations may be employed to
`reduce overlaps and repeat flights around the structure to
`conserve fuel, reduce operation time, or enhance other flight
`related parameters. Additional optimization algorithms are
`discussed below in conjunction with FIG. 7.
`FIG. 4 illustrates an example surface confidence determi
`nation for UAV navigation computation in accordance with at
`least some embodiments. A number of different approaches
`may be employed to determine desired locations for the
`UAV's flight path in order to cover unobserved surfaces. This
`is typically done based on information from observed sur
`faces. The three dimensional figures in diagram 400 illustrate
`outputs of an example algorithm that may be used to compute
`surface confidence, which is then used to determine desired
`locations for UAV flight path.
`RANSAC is the abbreviation for “Random Sample Con
`45
`sensus, which is used for taking a point cloud and fitting
`hypothetical surfaces to the point cloud. The overall approach
`may be described as generating a Surface that minimizes the
`least squares difference from the Surface to a point cloud
`while satisfying various assumptions. The assumptions may
`include an expectation of planarity and linear features (com
`mon for architecture), recognition of symmetry (as in dia
`gram 400), and comparable ones, which are likely to continue
`into unobserved areas when not precluded by the data. In
`order to enable the dynamic navigation for enhanced obser
`Vation, Surfaces that are in Some way deficient may be iden
`tified and the flight path altered such that more data on those
`Surfaces can be collected.
`Representations 444, 446, and 448 of a 3D architectural
`structure in diagram 400 may be obtained as an output of a
`RANSAC surface extractor program. In the representations
`444, 446, and 448, surfaces of the same architectural structure
`are hypothesized from multiple views (e.g., from video cap
`ture) and the structure shown in various rotated positions to
`illustrate the Surfaces where surface image data has not been
`taken (hypothesized but unobserved surfaces). A volume and
`views, which the camera platform needs to obtain in order to
`
`55
`
`25
`
`30
`
`35
`
`40
`
`50
`
`60
`
`65
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-1 Filed 04/27/20 Page 18 of 23 Page ID #:32
`
`US 8,965,598 B2
`
`5
`
`10
`
`15
`
`8
`Diagram 700 illustrates an example of selecting between
`two different paths 797 and 798 that a UAV might fly to gather
`more data on the low data areas. The top path 797 only
`traverses surface normal cones 792 and 794 extended from an
`architectural structure. On the other hand, the bottom path
`798 traverses all three surface normal cones 798, 794, and
`796. Thus, the bottom path 798 results in more data collection
`associated with the low quality surfaces of the structure. The
`bottom path 798, however, may require changes in altitude
`and may have additional optimization costs (such as an unde
`sirable closeness to the ground). The goodness values and
`cost functions may define whether the additional data is worth
`the added cost and aid in selection of the path to be taken by
`the UAV. Thus, desired viewpoints may be used to generate a
`set of desired travel waypoints and the minimal cost or least
`impact navigation optimization may select a path through
`those desired waypoints.
`FIG. 8 illustrates a general purpose computing device,
`which may be used to determine navigational path(s) for a
`UAV capturing Surface images for Solid modeling in accor
`dance with at least Some embodiments.
`As depicted, a computer 800 includes a processor 810, a
`memory 820, and one or more drives 830. The drives 830 and
`their associated computer storage media such as removable
`storage media 834 (e.g., CD-ROM, DVD-ROM) and non
`removable storage media 832 (e.g., a hard drive disk), may
`provide storage of computer readable instructions, data struc
`tures, program modules and other data for the computer 800.
`The drives 830 may include an operating system 840, appli
`cation programs 850, program modules 860, and a database
`880. The computer 800 further may includeuser input devices
`890 through which a user may enter commands and data. The
`input devices 890 may include an electronic digitizer, a
`microphone 896, a keyboard 894, and a pointing device such
`as a mouse device 892, trackball device or touchpad device.
`Other input devices may include a joystick device, game pad
`device, satellite dish, scanner device, or the like.
`The application programs 850 may include a UAV control
`application 852 and an image processing application 854. The
`UAV control application 852 may define an initial flight path
`for the UAV and compute adjustments for the flight path for
`optimization based on predefined flight parameters and
`desired locations for enhancing captured images and soli