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

`

`Case 2:20-cv-03827-AB-AFM Document 1-2 Filed 04/27/20 Page 2 of 23 Page ID #:39
`
`USOO9352833B2
`
`(12) United States Patent
`Kruglick
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 9,352,833 B2
`*May 31, 2016
`
`(54) AUTOMATIC FLIGHT CONTROL FOR UAV
`BASED SOLID MODELING
`
`USPC ..................................... 701/2, 3, 11; 244/190
`See application file for complete search history.
`
`(71) Applicant: Empire Technology Development LLC,
`Wilmington, DE (US)
`(72) Inventor: Ezekiel Kruglick, Poway, CA (US)
`(73) Assignee: EMPIRE TECHNOLOGY
`DEVELOPMENT LLC, Wilmington,
`DE (US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`This patent is Subject to a terminal dis
`claimer.
`
`(*) Notice:
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,504,914 A
`4,613,899 A
`
`3, 1985 Hofmann
`9, 1986 Kuwano et al.
`(Continued)
`
`FOREIGN PATENT DOCUMENTS
`
`AU
`EP
`
`9, 2010
`2010219.335 A1
`10, 2009
`2112630 A1
`(Continued)
`OTHER PUBLICATIONS
`
`(21) Appl. No.: 14/574,329
`
`(22) Filed:
`
`Dec. 17, 2014
`
`(65)
`
`Prior Publication Data
`US 2015/O112516 A1
`Apr. 23, 2015
`
`Related U.S. Application Data
`(63) Continuation of application No. 13/054,882, filed as
`application No. PCT/US2010/050829 on Sep. 30,
`2010, now Pat. No. 8,965,598.
`
`(51) Int. Cl.
`G05D3/00
`B64C39/02
`
`(2006.01)
`(2006.01)
`(Continued)
`
`(52) U.S. Cl.
`CPC ............... B64C39/024 (2013.01); B64C 19/00
`(2013.01); G05D I/0088 (2013.01); G05D
`I/0094 (2013.01); G05D I/101 (2013.01);
`(Continued)
`(58) Field of Classification Search
`CPC .................... B64C 220 1/141; B64C 220 1/146
`
`
`
`“Creating 3D models with a simple webcam (w? Video).” Retrieved,
`from URL: https://web.archive.org/web/20100314132804/http://
`pdaphysorg.com/ news177180374.html, posted on Nov. 11, p. 1.
`(Continued)
`
`Primary Examiner — Gertrude Arthur Jeanglaud
`(74) Attorney, Agent, or Firm — Turk IP Law, LLC
`
`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.
`
`20 Claims, 11 Drawing Sheets
`
`- 100
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-2 Filed 04/27/20 Page 3 of 23 Page ID #:40
`
`US 9,352,833 B2
`Page 2
`
`(2006.01)
`(2006.01)
`(2011.01)
`(2006.01)
`(2006.01)
`
`(51) Int. Cl.
`G05D I/00
`G05D L/10
`G06T I7/05
`G06T 7/10
`B64C 9/00
`(52) U.S. Cl.
`CPC ................ G06T 17/05 (2013.01); G06T 17/10
`(2013.01); B64C 220 1/127 (2013.01); B64C
`220 1/141 (2013.01); B64C 220 1/146 (2013.01);
`G06T 2210/21 (2013.01); G06T 2210/61
`(2013.01)
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,628,354 A 12/1986 Nagura
`4,802,757 A
`2f1989 Pleitner et al.
`5,104,217 A
`4, 1992 Pleitner et al.
`5,289, 185 A
`2f1994 Ramier et al.
`5,602.586 A
`2f1997 Schauer et al.
`6,272.404 B1
`8/2001 Amano et al.
`6,972,696 B2 12/2005 Rogers et al.
`7,009,638 B2
`3, 2006 Gruber et al.
`7,339,614 B2
`3/2008 Gruber et al.
`7,342,670 B2
`3/2008 Teichman
`7,509,241 B2
`3/2009 Guo et al.
`7,630,797 B2 12/2009 Garceau et al.
`8,355,834 B2
`1/2013 Duggan et al.
`8,768,555 B2
`7/2014 Duggan et al.
`8,965,598 B2 * 2/2015 Kruglick ............... B64C 39,024
`244f75.1
`
`1/2003 Guo et al.
`2003/0014224 A1
`5, 2008 Miles et al.
`2008.0125920 A1
`2009,0256909 A1 10, 2009 Nixon
`2009/0263009 A1 10/2009 Krishnaswamy et al.
`2010, 0004802 A1
`1/2010 Bodin et al.
`2010.0013927 A1
`1/2010 Nixon
`
`FOREIGN PATENT DOCUMENTS
`W8 SEA A 1338
`
`OTHER PUBLICATIONS
`“Parrot Ardrone 2.0.” Retrieved from URL: http://web.archive.org/
`web/20130810.045943/http://ardrone2.parrot.com/, accessed on
`Nov. 21, 2014, pp. 1-6.
`"Punchcard Videotrace, Modelling a House.” Retrieved from URL:
`https://web.archive.org/web/20091014165353/http://punchcard.
`com.au/wordpress/?p=12, on Nov. 21, 2014, posted on May 7, 2009,
`pp. 1-2.
`"Punchcard: Video Trace, Image-based Modelling for All.” Retrieved
`from URL: https://web.archive.org/web/20100701034807/http://
`punchcard.com.au/wordpressf, on Nov. 21, 2014, pp. 1-2.
`Andert, F. and Adolf. F., et al., “Online World Modeling and Path
`Planning for an Unmanned Helicopter.” Autonomous Robot, vol.27,
`Issue 3, 147-164 (Oct. 2009).
`Favi, C., and Charbon, E., “Techniques for Fully Integrated Intra-f
`Inter-Chip Optical Communication.” Proceedings of the 45th annual
`Design Automation Conference, pp. 343-344 (Jun. 8, 2008).
`Fischler, M., A., and Bolles, R., C., “Random Sample Consensus: A
`Paradigm for Model Fitting with Applications to Image Analysis and
`Automated Cartography.” Communications of the ACM, Eds. Foley,
`J. D., vol. 24. Issue 6, pp. 381-395 (Jun. 1981).
`International Search Report and Written Opinion for international
`application No. PCT/US 10/050829 mailed Jan. 4, 2011.
`Mei-Ni, N., and Hamel, T. "A UAV for Bridge Inspection: Visual
`Serving Control Law with Orientation Limits.” Automation in Con
`struction, vol. 17. No. 1, pp. 3-10 (Nov. 2007).
`Quirk, P. et al., “RANSAC–Assisted Display Model Reconstruc
`tion for Projective Display.” Virtual Reality Conference, p. 1-4 (Mar.
`25-29, 2006).
`* cited by examiner
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-2 Filed 04/27/20 Page 4 of 23 Page ID #:41
`
`U.S. Patent
`
`May 31, 2016
`
`Sheet 1 of 11
`
`US 9,352,833 B2
`
`
`
`CN
`--
`we
`
`NS2
`
`2N
`
`Y
`E, Y i
`i
`-
`i
`i
`i
`i y
`\,
`
`---
`
`
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-2 Filed 04/27/20 Page 5 of 23 Page ID #:42
`
`U.S. Patent
`
`May 31, 2016
`
`Sheet 2 of 11
`
`US 9,352,833 B2
`
`
`
`
`
`
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-2 Filed 04/27/20 Page 6 of 23 Page ID #:43
`
`U.S. Patent
`
`May 31, 2016
`
`Sheet 3 of 11
`
`US 9,352,833 B2
`
`S
`
`
`
`s
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-2 Filed 04/27/20 Page 7 of 23 Page ID #:44
`
`U.S. Patent
`
`May 31, 2016
`
`Sheet 4 of 11
`
`US 9,352,833 B2
`
`!
`
`gyv.)”
`
`
`
`997
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-2 Filed 04/27/20 Page 8 of 23 Page ID #:45
`
`U.S. Patent
`
`May 31, 2016
`
`Sheet 5 of 11
`
`US 9,352,833 B2
`
`
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-2 Filed 04/27/20 Page 9 of 23 Page ID #:46
`
`U.S. Patent
`
`May 31, 2016
`
`Sheet 6 of 11
`
`US 9,352,833 B2
`
`
`
`&
`
`s : :
`
`%
`
`& S
`
`
`
`S&
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-2 Filed 04/27/20 Page 10 of 23 Page ID #:47
`
`U.S. Patent
`
`May 31, 2016
`
`Sheet 7 of 11
`
`US 9,352,833 B2
`
`700
`
`
`
`FIG. 7
`
`

`

`e
`aC
`Case 2:20-cv-03827-AB-AFM Document 1-2 Filed 04/27/20 Page 11 of 23 Page ID #:48
`8A.#
`
`O.tWa3.1
`
`%U
`
`2O
`
`0.PEdge(
`2S.8m
`
`
`2t5330
`7.355%imngmma
`mm"%mESE;Si
`
`AF“M-_.QOESEOOMDmtmoEmmFZmemmmooma
`
`M3
`
`m1,
`
`3Iy$5.05:
`
`D2IB
`
`.mw8Wa
`
`
`32%m681m1
`wmgamam555
`
`
`5&2.mum:mmoimmfiz.mmoSmofieéggm.xmozfimz
`
`
`gB
`
`szEmaoex\\g.demzoxmomoi(//20:53am?\\amom/PAmiga/521/mom<0m>mx
`($6////Imn8550Tom:So:
`
`:09MMm4m<>ozmmm4m<>02m¢202
`
`m8,maNam.2lB"awGE1..dog92001..
`,m9,%mmlmwmozmeg.><3EmnWWmSIIIM.Umm<m§<om2<mmwoma25.8mm.
`
`
`
`
`
`
`
`
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-2 Filed 04/27/20 Page 12 of 23 Page ID #:49
`
`U.S. Patent
`
`May 31, 2016
`
`Sheet 9 of 11
`
`US 9,352,833 B2
`
`
`
`
`
`
`
`
`
`
`
`^_006
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-2 Filed 04/27/20 Page 13 of 23 Page ID #:50
`
`U.S. Patent
`
`May 31, 2016
`
`Sheet 10 of 11
`
`US 9,352,833 B2
`
`
`
`COMPUTING DEVICE O1
`
`COMPUTER-READABE MEDUM 102O
`
`START WITH PREDEFINED PATH
`
`AAA
`
`AA
`
`AAP AAA
`
`AA
`
`AA
`
`O24
`DETERMNE MOVEMENT PATH
`
`O26
`CAPTURE WOEO FROM MOBILE
`PLATFORM
`
`1028
`OCATION INFO2
`
`103
`EXTRACT MOTION &
`TRACKING POINTS
`
`1032
`FORMSURFACE HYPOTHESES
`
`1034
`COMPUE SURFACE NORMA
`CONES
`
`1036
`DETERMNE DESRED OCATIONS
`
`O38
`OPTIMIZE DES RED LOCATIONS VS.
`FIGHT PARAMETERS
`
`FIG. 10
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-2 Filed 04/27/20 Page 14 of 23 Page ID #:51
`
`U.S. Patent
`
`May 31, 2016
`
`Sheet 11 of 11
`
`US 9,352,833 B2
`
`
`
`COMPUTER PROGRAM PRODUCT 1 (O
`
`SiGNA. BEARNG MEOM 2
`
`: A EAS ONE O
`
`ONE OR yr NSER CONS FOR FORNG
`SURFACE HYPOTHESES
`ONE OK OK NSR CONS KOR KXRACNG
`MAGES FROM MOBE PLAFORM
`CNE OR MO&E NSRCEONS -OR OEERNNG
`MESSING SURFACES),
`ONE OR MORE NSRCEONS FOR ADUSTNG
`MOVEMENT PAH
`
`COMPUTER
`REACA3E
`Eli
`
`COMMUNICATIONS
`
`MEOUM
`
`FIG. 11
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-2 Filed 04/27/20 Page 15 of 23 Page ID #:52
`
`1.
`AUTOMATIC FLIGHT CONTROL FOR UAV
`BASED SOLID MODELING
`
`US 9,352,833 B2
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`This Application is a continuation under 35 U.S.C. S 120 of
`U.S. patent application Ser. No. 13/054,882 filed on Aug. 12,
`2013, now U.S. Pat. No. 8,965,598, which is the National
`Stage filing under 35 U.S.C. S371 of PCT Application Ser.
`No. PCT/US10/50829 filed on Sep. 30, 2010. The disclosures
`of the U.S. Patent Application and PCT Application are herein
`incorporated by reference in their entireties.
`
`BACKGROUND
`
`10
`
`15
`
`25
`
`30
`
`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
`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
`50
`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
`operations may be optimized, but given the trend to simplify
`UAVs and their controllers (e.g., smart phone based UAV
`55
`controllers are becoming popular), complex control Software
`and specialized training increase the cost and limit the use of
`Such systems.
`
`40
`
`45
`
`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
`
`60
`
`65
`
`2
`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
`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;
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-2 Filed 04/27/20 Page 16 of 23 Page ID #:53
`
`US 9,352,833 B2
`
`3
`FIG. 5 illustrates surface normal cones from a low quality
`Surface to be used in Surface confidence computation;
`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
`15
`that may be performed by a computing device. Such as com
`puter 800 in FIG.8 or special purpose processor 910 in FIG.
`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
`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
`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
`
`25
`
`30
`
`40
`
`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
`35
`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
`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
`
`55
`
`45
`
`50
`
`60
`
`65
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-2 Filed 04/27/20 Page 17 of 23 Page ID #:54
`
`US 9,352,833 B2
`
`10
`
`15
`
`6
`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
`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 (464. 466, and
`468) of the structure with confidence numbers computed and
`symbolized by shades of grey (again with darker shades rep
`resenting 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.
`
`5
`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
`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
`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
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`Case 2:20-cv-03827-AB-AFM Document 1-2 Filed 04/27/20 Page 18 of 23 Page ID #:55
`
`US 9,352,833 B2
`
`10
`
`15
`
`8
`the Summation for any path cannot obtain additional infor
`mation from traversing an overlap area if it also traverses the
`areas that form the overlap.
`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 792, 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 gene