Disclosed are various embodiments of a multi-scale fiducial. A multi-scale fiducial may have three or more scales, where the child fiducials are nested or otherwise linked by a relative position to the parent fiducials. Multi-scale fiducials may facilitate target identification and tracking at varying distances, potentially without the aid of a scale-invariant recognition algorithm. One application of multi-scale fiducials may involve target identification for autonomously controlled aerial vehicles.

BACKGROUND

Fiducials are optically recognizable features often used in computer vision applications. Common fiducials include grids of black and white blocks of a fixed size, which may be randomly generated. Applications for fiducials may include localization, tracking, and detecting the orientation of objects marked with these features, including robotics, printed circuit board manufacturing, printing, augmented reality, and automated quality assurance.

DETAILED DESCRIPTION

The present application relates to multi-scale fiducials that may facilitate target identification and tracking at varying distances. Changes in the distance between the imaging device and the fiducial may result in changes in the size of the appearance of the fiducial in the captured image. For example, at a first distance from the fiducial, a block feature of the fiducial may be five pixels square in the captured image. At a second, closer distance from the fiducial, the same block feature may be twenty pixels square in the captured image. Consequently, with varying distances, fiducial recognition algorithms may need to compensate for the change in scale of the fiducial.

One approach to compensating for the change in scale may be to use a scale-invariant algorithm, i.e., an algorithm that can operate regardless of the current size of the fiducial. In some cases, however, a scale-invariant algorithm cannot be used due to limitations in equipment processing power or ability to modify the fiducial recognition logic.

Various embodiments of the present disclosure employ fiducials of varying scales in order to take advantage of the change in size of the fiducial at different distances. Fiducial markers with such properties may be used for landing and tracking optical targets across broad distances. As a non-limiting example, such fiducials may be used for guiding autonomously controlled aerial vehicles or in other vehicles capable of movement. It is understood, however, that such fiducials may be useful in any computer vision application involving fiducials. The fiducials discussed herein may be printed on labels and affixed to objects, painted directly on objects, incorporated directly in construction of objects, and so on. The fiducials may be present on fixed objects or mobile objects. In one scenario, the fiducials described herein may be present on another autonomously controlled aerial vehicle.

With reference toFIG. 1, shown is one example of a multi-scale fiducial100with a breakdown of the components of the multi-scale fiducial100being graphically illustrated. In this example, the multi-scale fiducial100consists of three component fiducials: a parent (i.e., a first) fiducial103, a child (i.e., a second) fiducial106, and a grandchild (i.e., a third) fiducial109. Although a nesting of three is employed in this non-limiting example, it is understood that multi-scale fiducials may be nested to an arbitrary depth (or not nested at all) depending upon the specific configuration and purpose of the fiducial.

Each of the component fiducials103,106, and109in this example comprises a six-by-six grid of black or white square tiles. In fact, in this instance, each of the component fiducials103,106, and109are versions of the same grid at three different scales. In addition to merely facilitating identification of an object, the component fiducials103,106, and109may encode specific information. For example, each tile may be viewed as encoding a bit of information depending on whether the tile is white or black. Each scale of the multi-scale fiducial100may be used independently to determine a relative position of its respective parent fiducial and/or its respective child fiducial.

With a multi-scale fiducial100, a portion112of the component fiducial103,106may be reserved for the corresponding nested fiducial. A scale-variant algorithm for recognizing the component fiducials103,106may be configured to actively ignore data corresponding to the corresponding reserved portion112that is an expected location of a child fiducial. Although in this example the reserved portion112is shown as being in the center of the component fiducials103,106, it is not required that the reserved portion112be in the center or even in the same relative position. In fact, the reserved portion112may also exist outside the boundaries of the fiducial103,106in a location relative to the fiducial103,106. The reserved portions112may be at a location known to the fiducial recognition algorithm. Otherwise, for example, the reserved portion112of the parent fiducial103may appear as noise to the fiducial recognition algorithm.

In the following discussion, a general description of an example of a fiducial recognition system and its components is provided, followed by a discussion of the operation of the same.

Turning now toFIG. 2, shown is a block diagram of an autonomously controlled aerial vehicle200according to various embodiments. The autonomously controlled aerial vehicle200may include control logic203, an imaging device206, a power system209, a propulsion system212, a guidance navigation and control system215, and/or other components. The autonomously controlled aerial vehicle200may, for example, correspond to a multi-rotor drone or other aircraft.

The imaging device206may include an image sensor configured to capture digital images of the surroundings of the autonomously controlled aerial vehicle200at one or more resolutions. In one embodiment, the imaging device206may capture color images. However, color images may have less sensitivity due to the presence of a color filter. Thus, in another embodiment, the imaging device206may be configured to capture grayscale images. In some embodiments, the autonomously controlled aerial vehicle200may employ a plurality of imaging devices206, e.g., to observe different directions, provide stereo data, provide geometric data, etc. The imaging device206may capture non-visible electromagnetic radiation, such as infrared, ultraviolet, etc.

The power system209may include a battery or other source of power. The battery may be rechargeable, and one use case of the present disclosure may be to direct the autonomously controlled aerial vehicle200to dock at a charging station. The propulsion system212may control the propulsion or thrust of the autonomously controlled aerial vehicle200. For example, the propulsion system212may control the operation of a plurality of propellers that provide vertical lift and horizontal propulsion. The guidance navigation and control system215may control the orientation of the autonomously controlled aerial vehicle200, e.g., rotation of the autonomously controlled aerial vehicle200.

The control logic203is configured to control the operation of the autonomously controlled aerial vehicle200. To this end, the control logic203may control the operation of the imaging device206, the power system209, the propulsion system212, the guidance navigation and control system215, among other systems of the autonomously controlled aerial vehicle200. The control logic203may incorporate fiducial recognition logic218that operates upon fiducial recognition configuration data221. The fiducial recognition configuration data221may include fiducial patterns224and actions227to be performed upon recognizing the fiducial patterns224.

The fiducial recognition logic218is configured to operate upon images captured via the imaging device206and to determine whether a fiducial pattern224is present in the images. The fiducial recognition logic218may employ scale-variant algorithms for recognizing fiducial patterns224. As a non-limiting example, the fiducial recognition logic218may recognize a certain fiducial pattern224when the feature size is twenty pixels but not when the feature size is ten pixels, or vice versa. In some embodiments, scale-invariant algorithms may be employed by the fiducial recognition logic218while recognizing multi-scale fiducials to allow fiducials of multiple scales to be leveraged concurrently.

If a fiducial pattern224is present, the control logic203may be configured to perform a certain action227. The action227may include piloting the autonomously controlled aerial vehicle200in a certain direction relative to the detected fiducial pattern224, rotating or otherwise adjusting the orientation of the autonomously controlled aerial vehicle200, and/or other actions. As the autonomously controlled aerial vehicle200is piloted toward the detected fiducial pattern224, other nested fiducial patterns224may become visible (i.e., recognizable) in images captured via the imaging device206. Similarly, the previously detected fiducial patterns224may become at least partially clipped or out of view of the imaging device206.

In one non-limiting example, a parent fiducial may be visible on a wall of a building. Blocks of the parent fiducial may correspond to painted concrete blocks. The parent fiducial may assist the autonomously controlled aerial vehicle200determine which wall to pilot toward. Within the parent fiducial may be one or more child fiducials that help the autonomously controlled aerial vehicle200in identifying an orientation to be used in order to access one of potentially multiple power ports on the wall. The child fiducials may initially be unresolvable from an image through which the parent fiducial is recognized, i.e., the autonomously controlled aerial vehicle200may initially be too far away to resolve the child fiducials. Further nested fiducials may provide additional information such as voltages available and so on. The information may be provided in increasing detail as the power port becomes closer.

In another non-limiting example, a multi-scale fiducial may be present upon a moving object (e.g., an autonomously controlled aerial vehicle200, a kite, a balloon, etc.) and recognized by a fixed system or another autonomously controlled aerial vehicle200. Thus, a change in distance of a fiducial between captured images may be caused by movement of the fiducial itself as well as movement by the observer system.

Additional non-limiting examples of multi-scale fiducials that may be recognized by the fiducial recognition logic218will now be discussed. Features of the multi-scale fiducials may be selected to include high contrast or crisp corners or edges. High contrast features are unusual in nature and provide ease of recognition across a wide variety of conditions.

FIG. 3Adepicts a multi-scale fiducial300with a parent fiducial303and a child fiducial306. The design of the parent fiducial303is a six-by-six grid of black or white tiles similar to the parent fiducial103(FIG. 1). However, unlike the multi-scale fiducial100(FIG. 1), the child fiducial306is located off-center.

FIG. 3Bis similar toFIG. 3Abut includes multiple child fiducials306,309at the same scale. Both child fiducials306,309encode the same information.

FIG. 3Cis similar toFIG. 3Bin that the multi-scale fiducial300includes multiple child fiducials306,312at the same scale. However, the child fiducial312encodes information different from that of the child fiducial306, and the child fiducial312exhibits a different design.

FIG. 4Adepicts a multi-scale fiducial400with a parent fiducial403and a child fiducial406. The design of the parent fiducial403is a six-by-six grid of black or white tiles similar to the parent fiducial103(FIG. 1). However, unlike the multi-scale fiducial100(FIG. 1) and the multi-scale fiducial300(FIG. 3A), the child fiducial406is a different design and may encode different information. Specifically, the child fiducial406is an eight-by-eight grid of black or white tiles. The child fiducial406may encode information as to how deep it is relative to the parent fiducial403, which can be helpful for multi-scale fiducials400having many nestings. This provides localization feedback which may allow an optical system a ground truth measure of the object being viewed.

In some cases, a multi-scale fiducial400may include several child fiducials at the same nesting depth, which may be repeats of one another. This may assist in redundantly encoding information to overcome challenges posed by occluding features, such as shadows, etc.

FIG. 4Bdepicts a multi-scale fiducial400, where the child fiducial406is not nested within the boundary412of the parent fiducial403. Instead, the child fiducial406may be located a position relative to the parent fiducial403. Such a position may be predetermined and used to infer that the child fiducial406is linked to the parent fiducial403. For example, upon recognizing the parent fiducial403, the autonomously controlled aerial vehicle200(FIG. 2) may move to the right in order to recognize an expected child fiducial406. Thus, a multi-scale fiducial400may include child fiducials406that are linked either by nesting in a parent fiducial403or by being at a predefined relative position to the parent fiducial403.

FIG. 5depicts a multi-scale fiducial500with a parent fiducial503and a child fiducial506. Unlike the multi-scale fiducial100(FIG. 1), the multi-scale fiducial300(FIG. 3A), and the multi-scale fiducial400(FIG. 4A), the multi-scale fiducial500employs nested rings rather than a grid of black or white squares. In this case, the multi-scale fiducial500includes a parent fiducial503and a child fiducial506, but any level of nesting may be employed. Here, the parent fiducial503and the child fiducial506are concentric rings, but in other examples, the parent fiducial503and the child fiducial506may be off-center.

Each of the component fiducials503and506may include respective rotational markers509. In this case, the rotational markers509are black or white, but color may also be used. The rotational markers509may be used to encode specific information. For example, the angular length and/or radial thickness of each rotational marker509may be compared against the circumference of the corresponding component fiducial503,506to extract range information. Also, the angle between multiple rotational markers509may be used to encode information. In one example, a rotational marker509may comprise a bar code with a sync field and other information. The information encoded by the parent fiducial503may differ from the information encoded by the child fiducial506. The rotational markers509of the component fiducials503,506may encode the same angular information regardless of distance from the center. The child fiducial506may be freely rotated to encode rotational information due to the inherent symmetry of the border between the parent fiducial503and the child fiducial506. Other geometries naturally have different symmetries that can be leveraged to this extent, as inFIG. 6.

FIG. 6depicts a multi-scale fiducial600with a parent fiducial603, a child fiducial606, and a grandchild fiducial609. The multi-scale fiducial600of this example has a consistent L-like shape among its component fiducials603,606,609. In this example, the multi-scale fiducial600may use color, texture, reflectance, or pattern to convey information. For example, each component fiducial603,606,609in this example has two portions, a top portion612and a side portion615. The distinct colors, textures, reflectances, or patterns of the respective top portion612and side portion615may convey specific information. For simplicity of illustration, patterns are used inFIG. 6, but it is understood that colors may be employed.

For ease of recognition, the colors and patterns of the corresponding top portion612and the corresponding side portion615of the same scale may be similar or related (e.g., the top portion612has a pattern of horizontal lines, and the side portion615has a pattern of has vertical lines, or the top portion612is a dark shade of blue, and the side portion615has a medium shade of blue). As a non-limiting example, suppose that three different colors are employed. For a component fiducial with two portions, this yields nine different combinations, which can each correspond to a specific signal to the fiducial recognition logic218(FIG. 2). Also, the connectivity of the top portions612and the side portions615may convey specific information. For example, the top portion612and the side portion615exchange positions in the grandchild fiducial609(i.e., connected up instead of to the side).

Moving on toFIG. 7, shown is a multi-scale fiducial100as inFIG. 1, but with a specific field of view700illustrated for an imaging device206(FIG. 2). In this example, the imaging device206is too close to the multi-scale fiducial100and cannot see the entire parent fiducial103(FIG. 1) of the multi-scale fiducial100. In other words, a portion of the parent fiducial103is clipped or not visible to the imaging device206. This portion is visually depicted inFIG. 7using a grayed pattern. The imaging device206can see portions of the parent fiducial103, but perhaps not enough to properly recognize the parent fiducial103.

Nonetheless, the imaging device206can see the entirety of the child fiducial106(FIG. 1) and the grandchild fiducial109(FIG. 1) as they are within the field of view700. In this example, the child fiducial106and the grandchild fiducial109encode the same information, so there is no loss of information. The fiducial recognition logic218(FIG. 1) is thus able to recognize the child fiducial106and/or the grandchild fiducial109without recognizing the parent fiducial103. In some scenarios, the fiducial recognition logic218may have already recognized the parent fiducial103. The control logic203(FIG. 2) may have applied a certain action227(FIG. 2) causing the autonomously controlled aerial vehicle to move to its current position with the given field of view700to receive further instruction from the child fiducial106and/or the grandchild fiducial109.

Referring next toFIG. 8, shown is a flowchart that provides one example of the operation of a portion of the control logic203according to various embodiments. It is understood that the flowchart ofFIG. 8provides merely an example of the many different types of functional arrangements that may be employed to implement the operation of the portion of the control logic203as described herein. As an alternative, the flowchart ofFIG. 8may be viewed as depicting an example of elements of a method implemented in the autonomously controlled aerial vehicle200(FIG. 2) according to one or more embodiments.

Beginning with box803, the control logic203captures an image via an imaging device206(FIG. 2). For example, the autonomously controlled aerial vehicle200may be piloted toward a predetermined location or object and continuously capture images to identify how it should land at the location or interact with the object. In box806, the control logic203performs image recognition using the fiducial recognition logic218(FIG. 2). In box809, the control logic203determines whether the image depicts a parent fiducial of a multi-scale fiducial according to the predefined fiducial patterns224(FIG. 2). If the control logic203determines that the image does not depict the parent fiducial, or if the result is inconclusive, the control logic203moves to box812and allows the autonomously controlled aerial vehicle to continue in its course. The control logic203then returns to box803and continues capturing images.

If the control logic203otherwise determines that the image does depict a parent fiducial, the control logic203instead moves from box809to box815. In box815, the control logic203determines an action227(FIG. 2) based at least in part on the fiducial pattern224that has been recognized. In box818, the control logic203performs an action227that may, for example, result in the autonomously controlled aerial vehicle200moving closer to the recognized fiducial.

In box821, the control logic203captures an image via an imaging device206from this closer distance from the recognized fiducial. In box824, the control logic203performs image recognition using the fiducial recognition logic218. In box827, the control logic203determines whether the image depicts a child fiducial of the multi-scale fiducial. If a child fiducial is not recognized, the control logic203moves to box830and the autonomously controlled aerial vehicle200continues upon its course. The control logic203then may return to box815.

Otherwise, if the control logic203recognizes the child fiducial, the control logic203transitions from box827to box833. In box833, the control logic determines whether to promote the child fiducial to be a parent fiducial. If so, the control logic203moves to box836and promotes the child to a parent. The control logic203then returns to box815. If the child fiducial is not promoted to be a parent, the control logic203moves from box833to box839.

In box839, the control logic203determines an action227based at least in part on the child fiducial. In box842, the control logic203causes the action227to be performed. Subsequently, the control logic203may return to box821and continue capturing images via the imaging device206. Further child fiducials may then be recognized and additional actions227may be performed.

Although the flowchart ofFIG. 8depicts a flow pertaining to a movement from parent fiducials to child fiducials, it is understood that the reverse may also be performed. That is, a similar control flow may involve moving from a child fiducial to a parent fiducial and then a grandparent fiducial, and so on.

With reference toFIG. 9, shown is a schematic block diagram of a computing device900according to an embodiment of the present disclosure. For example, the autonomously controlled aerial vehicle200may include a computing device900. Alternatively, the computing device900may be embodied in other types of vehicles capable of movement, including land-based vehicles. In some embodiments, functionality of the control logic203may be performed by separate server or client computing devices900in data communication with the autonomously controlled aerial vehicle200or other vehicle via a network. Such computing devices900may be remotely located with respect to the autonomously controlled aerial vehicle200or other vehicle.

The computing device900includes at least one processor circuit, for example, having a processor903and a memory906, both of which are coupled to a local interface909. The local interface909may comprise, for example, a data bus with an accompanying address/control bus or other bus structure as can be appreciated.

Stored in the memory906are both data and several components that are executable by the processor903. In particular, stored in the memory906and executable by the processor903is the control logic203, including fiducial recognition logic218and potentially other systems. Also stored in the memory906may be the fiducial recognition configuration data221and other data. In addition, an operating system may be stored in the memory906and executable by the processor903.

It is understood that there may be other applications that are stored in the memory906and are executable by the processor903as can be appreciated. Where any component discussed herein is implemented in the form of software, any one of a number of programming languages may be employed such as, for example, C, C++, C#, Objective C, Java®, JavaScript®, Perl, Visual Basic®, Python®, Flash®, assembly, or other programming languages.

A number of software components are stored in the memory906and are executable by the processor903. In this respect, the term “executable” means a program file that is in a form that can ultimately be run by the processor903. Examples of executable programs may be, for example, a compiled program that can be translated into machine code in a format that can be loaded into a random access portion of the memory906and run by the processor903, source code that may be expressed in proper format such as byte code that is capable of being loaded into a random access portion of the memory906and executed by the processor903, or source code that may be interpreted by another executable program to generate instructions in a random access portion of the memory906to be executed by the processor903, etc. An executable program may be stored in any portion or component of the memory906including, for example, random access memory (RAM), read-only memory (ROM), hard drive, solid-state drive, USB flash drive, memory card, optical disc such as compact disc (CD) or digital versatile disc (DVD), floppy disk, magnetic tape, memory integrated in the processor903, or other memory components.

The memory906is defined herein as including both volatile and nonvolatile memory and data storage components. Volatile components are those that do not retain data values upon loss of power. Nonvolatile components are those that retain data upon a loss of power. Thus, the memory906may comprise, for example, random access memory (RAM), read-only memory (ROM), hard disk drives, solid-state drives, USB flash drives, memory cards accessed via a memory card reader, floppy disks accessed via an associated floppy disk drive, optical discs accessed via an optical disc drive, magnetic tapes accessed via an appropriate tape drive, and/or other memory components, or a combination of any two or more of these memory components. In addition, the RAM may comprise, for example, static random access memory (SRAM), dynamic random access memory (DRAM), ferroelectric random access memory (FRAM), or magnetic random access memory (MRAM) and other such devices. The ROM may comprise, for example, a programmable read-only memory (PROM), an erasable programmable read-only memory (EPROM), an electrically erasable programmable read-only memory (EEPROM), flash memory, or other like memory device.

Also, the processor903may represent multiple processors903and/or multiple processor cores and the memory906may represent multiple memories906that operate in parallel processing circuits, respectively. In such a case, the local interface909may be an appropriate network that facilitates communication between any two of the multiple processors903, between any processor903and any of the memories906, or between any two of the memories906, etc. The local interface909may comprise additional systems designed to coordinate this communication, including, for example, performing load balancing. The processor903may be of electrical or of some other available construction.

The flowchart ofFIG. 8shows the functionality and operation of an implementation of portions of the control logic203. If embodied in software, each block may represent a module, segment, or portion of code that comprises program instructions to implement the specified logical function(s). The program instructions may be embodied in the form of source code that comprises human-readable statements written in a programming language, assembly code, or machine code that comprises numerical instructions recognizable by a suitable execution system such as a processor903in a computer system or other system. The machine code may be converted from the source code, etc. If embodied in hardware, each block may represent a circuit or a number of interconnected circuits to implement the specified logical function(s).

Further, any logic or application described herein, including the control logic203and the fiducial recognition logic218, may be implemented and structured in a variety of ways. For example, one or more applications described may be implemented as modules or components of a single application. Further, one or more applications described herein may be executed in shared or separate computing devices or a combination thereof. For example, a plurality of the applications described herein may execute in the same computing device900or in multiple computing devices900. Additionally, it is understood that terms such as “application,” “service,” “system,” “engine,” “module,” and so on may be interchangeable and are not intended to be limiting.