HK1205316B - Anchors for location-based navigation and augmented reality applications - Google Patents

Abstract

A method for encoding information includes specifying a digital value and providing a symbol (28, 70, 80, 90, 100) comprising a plurality of polygons (72, 82, 92, 94, 102) meeting at a common vertex (74, 84, 96, 98, 104) and having different, respective colors selected so as to encode the specified digital value.

Description

Anchor point for location-based navigation and augmented reality applications

Cross Reference to Related Applications

This application claims the benefit of U.S. provisional patent application 61/656,029 filed 6/2012, which is incorporated herein by reference.

Technical Field

The present invention relates generally to methods, systems, and software for encoding and decoding machine-readable symbols, and in particular to the use of such symbols in providing location-based information.

Background

Various methods and standards are known in the art for encoding information in a form that can be read by a computer using an image sensor or other type of optical sensor. The best known standards of this type are barcodes, including conventional one-dimensional array stripes and two-dimensional barcodes (e.g. QR codes).

Other types of image-based computer-readable coding schemes and symbols have been proposed in the patent literature. Some of these schemes use color information rather than a single color symbol as provided by conventional barcodes. Representative examples are described in U.S. Pat. nos. 7,936,901, 5,869,828, and 7,020,327.

Disclosure of Invention

Embodiments of the invention described herein provide improved types of computer-readable symbols, and methods for using such symbols.

There is thus provided in accordance with an embodiment of the present invention a method for encoding information, including specifying a digital value, and providing a symbol including a plurality of polygons touching at a common vertex and having different respective colors selected to encode the specified digital value.

In some embodiments, the symbol comprises a tessellation having a plurality of vertices that encode a plurality of respective digital values according to the color of the polygon that touches at each of the vertices, and the symbol encodes an expanded digital value generated by combining the plurality of respective digital values encoded by the plurality of vertices.

Typically providing symbols includes assigning a digital code to each color and combining the digital codes to give a specified digital value. In the disclosed embodiment, the digital code is a three-digit code representing the red, green, and blue components of the color of the polygon. The three-digit digital code may be a three-digit code including respective binary values representing each of red, green, and blue components, wherein a color of the polygon is selected from a color group including red, green, blue, cyan, magenta, and yellow, and the red, green, blue, cyan, magenta, and yellow have three-digit codes (1,0,0), (0,1,0), (0,0,1), (0,1,1), (1,0,1), and (1,1,0), respectively.

The symbols may be provided without any dedicated recording marks.

In a disclosed embodiment, a method includes capturing an image of a symbol and decoding the symbol by detecting colors in the image at probe positions arranged at a plurality of angles around a common vertex. Typically the probe locations are all arranged at the same distance from a common apex.

There is also provided, in accordance with an embodiment of the present invention, tangible media having symbols disposed thereon in accordance with the above-described methods. The symbol may be printed on the medium.

There is also provided, in accordance with an embodiment of the present invention, an information system including a plurality of symbols, each symbol including a plurality of polygons meeting at a common vertex and having different respective colors selected such that the respective symbols encode respective numerical values. The server is configured to receive a message from the client device indicating a digital value decoded by the client device when capturing and analyzing an image containing one of the symbols, and to provide an entry of information corresponding to the digital value to the client device in response to the message.

In a disclosed embodiment, the symbols of the plurality are distributed at different respective locations within the environment, and the server is configured to determine a location of the client device responsive to the numerical value and to provide the entry responsive to the location. Typically, the entry comprises a graphical element configured to be overlaid by the client device on a display containing an image of one of the symbols.

There is also provided, in accordance with an embodiment of the present invention, a computer software product, including a tangible, non-transitory computer-readable medium in which program instructions are stored, which instructions, when read by a computing device, cause the device to capture an image of a symbol including a plurality of polygons touching at a common vertex and having different, respective colors selected to encode specified digital values, and to process the image to decode the digital values.

In disclosed embodiments, the instructions cause the computing device to decode the symbol by detecting colors in the image at probe positions arranged at a plurality of angles around a common vertex.

There is also provided, in accordance with an embodiment of the present invention, a computing device including an image sensor configured to capture an image containing a symbol including a plurality of polygons touching at a common vertex and having different respective colors selected to encode a specified digital value. The processor is configured to process the image in order to decode the digital values.

In some embodiments, the apparatus includes a display coupled to display the image captured by the image sensor, wherein the processor is configured to superimpose the graphical element on the display in response to the digital value. Additionally or alternatively, the apparatus comprises a communication interface, wherein the processor is configured to send a message comprising the digital value over a network to a server via the communication interface, and to receive the graphical element from the server in response to the message.

There is also provided, in accordance with an embodiment of the present invention, a method for encoding information, including designating a digital value, and generating a symbol that encodes the designated digital value with a set of color elements having different respective colors that are recognized as a red color element, a green color element, a blue color element, a cyan color element, a magenta color element, and a yellow color element, respectively, in an image of the symbol. The symbols are produced by applying a cyan pigment, a magenta pigment, and a yellow pigment to a substrate to produce color elements such that the color elements exhibit the following red, green, and blue intensity characteristics when measured in the sRGB color space:

for red color elements, the red intensity is two times greater than the blue and green intensities;

for the green color element, the green intensity is two times greater than the red intensity and the blue intensity;

for the blue color element, the blue intensity is two times greater than the red and green intensities;

for the cyan color element, both the blue and green intensities are two times greater than the red intensity;

for the magenta color element, both the red intensity and the blue intensity are greater than twice the green intensity; and

for the yellow color element, both the red and green intensities are two times greater than the blue intensity.

Additionally or alternatively, the symbol is generated by: applying a cyan pigment, a magenta pigment, and a yellow pigment to a substrate to produce color elements such that the color elements exhibit a red intensity characteristic, a green intensity characteristic, and a blue intensity characteristic that satisfy the following relationships when measured in an sRGB color space:

for each color c ═ red, green, blue, where H¹ _cAnd L¹ _cRespectively, the highest observed value and the lowest observed value of a color c among color elements expected to contain the color c, and H⁰ _cAnd L⁰ _cIs the highest observed value and the lowest observed value of color c among color elements expected not to contain color c.

There is also provided, in accordance with an embodiment of the present invention, a tangible medium having symbols disposed thereon in accordance with any of the above-described methods.

The invention will be more fully understood from the following detailed description of embodiments thereof taken together with the accompanying drawings, in which:

brief Description of Drawings

Fig. 1 is a schematic pictorial view of a system for navigation and augmented reality display in accordance with an embodiment of the present invention;

FIG. 2 is a schematic representation of a mobile computer computing device in the system of FIG. 1, according to an embodiment of the present invention;

FIG. 3 is a flow diagram schematically illustrating a method for navigation and augmented reality display, in accordance with an embodiment of the present invention;

FIGS. 4-7 are schematic representations of multi-colored computer-readable symbols according to embodiments of the present invention; and is

Fig. 8 is a flow chart schematically illustrating a method for decoding a multi-color symbol, in accordance with an embodiment of the present invention.

Detailed description of the embodiments

Overview

Outdoor navigation using GPS-enabled mobile computing devices, such as smart phones, tablets, and dedicated navigation devices, has gained widespread acceptance. However, in closed environments (both urban areas including indoor facilities and dense buildings), GPS navigation works poorly and user requirements are different. Not only does the user want the exact directions for finding the desired destination on foot, but the user's needs are often more complex and dynamic than those of outdoor GPS-based navigation. For example, a user may wish to locate a particular product or activity, and the navigation itself has various options for moving from one floor or altitude to another in a three-dimensional (3D) environment, often on different floors or altitudes. The navigation selection will therefore depend closely on the user's goals and preferences, as well as physical mobility limitations and capabilities.

At the same time, providing optimal instructions for navigation and path finding within an indoor complex typically requires detailed and profound knowledge of the structural and functional construction of the complex. Integrating this type of knowledge often requires the involvement of an operator who possesses a complex of such knowledge. Operators have strong motivations to meet user navigation needs in order to provide better and more efficient user experiences, and in particular to direct users to products and activities tailored to their needs while promoting operator attention and tenant attention within the complex. Providing this type of centralized navigation instruction increases the likelihood that the user will purchase the products and services in the complex and will return in the future.

However, existing methods of communicating navigation instructions to a user in a closed environment are not well suited for such tasks. Conventionally, navigation instructions are provided through maps and through lists of general direction signs and facilities, while promotional content appears on advertising signs and displays. Instead of enhancing the user experience, these communication devices may direct the user to a state of cognitive overload and confusion, where most of the information content is lost on them.

One solution to this problem is to enable users to select points about which they wish to receive information by providing symbols at these points that can be read using an image sensor (e.g., a camera built into most mobile computing devices). However, existing types of symbols (e.g., QR codes), unless printed very large, can be difficult for users to find and typically require the mobile computing device to be held close to the symbol to capture and decode the image.

Embodiments of the invention described herein provide novel computer-readable symbols and methods for using such symbols that overcome the limitations of existing image-based encoding schemes. Each symbol includes a plurality of polygons touching at a common vertex and having different respective colors selected to encode the assigned numerical value. To encode larger numerical values, the polygons may be arranged in a tessellation having a plurality of vertices, where each vertex encodes a respective numerical value according to the color of the polygon that is contacted at that vertex. The symbol may then encode an extended digital value generated by combining the respective digital values encoded by the multiple vertices. In the disclosed embodiments, the colors used in the symbols are selected in a novel manner that enables the mobile computing device to reliably and unambiguously decode them regardless of the lighting conditions in which they are present.

Typically the symbols are printed on a tangible medium, such as paper, plastic or any other printable substrate, which may then be hung or otherwise fixed in a desired location, such as on a wall or advertising post. Alternatively, such symbols may be presented on an electronic display. The colored symbols are easily seen and recognized by the user. At the same time, images of symbols can be reliably captured and decoded over a wide range of distances using various cameras built into the mobile computing device and algorithms that are insensitive to the size of the symbols in the captured images as described below.

The disclosed symbols are therefore useful, particularly in supporting navigation in a closed environment and effectuating display of location-based augmented reality information on a screen of a mobile computing device. Such symbols, when coupled to a suitable system for providing location-based information, may be used to enhance the user experience in such environments and overcome the drawbacks of the existing solutions explained above. While certain embodiments described herein focus on these types of applications, symbols generated in accordance with the principles of the present invention may similarly be used to provide encoded information to image capture and computing devices, for other purposes as well.

Description of the System

Fig. 1 is a schematic pictorial view of a system 20 for navigation and augmented reality display in accordance with an embodiment of the present invention. The operation of the system 20 is illustrated herein as being in a closed environment 22, such as a densely constructed urban environment or shopping mall in this example. This environment is presented by way of illustration only and not limitation, as the principles of the present invention may be implemented in virtually any user-reachable environment, whether indoors or outdoors.

A user 24 seeking information about the environment 22 illuminates a symbol 28 posted on a wall with light and directs a camera in his smartphone 26 (or other portable computing device) to capture an image containing the symbol. The symbols used in this type of application shading are also referred to herein as "anchor points". The symbol 28 includes a tessellated pattern of polygons (rectangles in this embodiment) having different colors. Such patterns are described in detail with reference to the following drawings. Although only a single user and a single anchor point are shown in fig. 1 for purposes of simplicity, an operator of environment 22 or other authorized person within environment 22 will typically post multiple anchor points at various different locations distributed within the environment to enable the user to access location-based information at all of these locations. For reliable navigation by a user within an environment, it is generally desirable that at any given location there is at least one anchor point that is clearly visible to the user.

A processor in the smartphone 26 processes the captured image to decode the digital value encoded by the symbol 28 and then sends a message specifying the digital value to the server 34. As explained below, the message may also include data about the general location of the smartphone (derived from cellular signal strength or any other type of location information available to the smartphone system), as well as user profiles and search requirements. In this communication, the smartphone 26 functions as a client device under the control of a suitable application as described below. In the depicted embodiment, the smartphone 26 communicates with the server 34 via the wireless access point 30, the wireless access point 30 being connected to the network 32, as is known in the art. Alternatively or additionally, smartphone 26 and server 34 may communicate via a cellular network connection or via any other suitable type of communication link known in the art. The server 34 typically comprises a general purpose computer having a processor, memory and a communications interface, the general purpose computer being driven by suitable software to communicate with client devices (e.g., the smartphone 26) and thereby provide location-based information in a suitable form.

In an alternative embodiment, a smartphone or other mobile computing device may operate offline by pre-caching relevant anchor point data and later extracting that data when a particular anchor point is detected. Such an option may be useful, for example, for a traveler who may have very limited (if any) data network access.

Fig. 2 is a schematic representation of a smartphone 26 according to an embodiment of the present invention. The smartphone includes a camera 45, the camera 45 being coupled to a processor 46 and memory 48 and a communication interface 49, as is known in the art. The user interface of the smartphone 26 is typically implemented by a touch display 40, although the smartphone may (alternatively or additionally) include other types of user interface components, such as a pointing device and/or a keypad. The processor 46 performs the functions described herein under the control of suitable software. For example, the software may be downloaded to the smartphone 26 in electronic form over a network. Additionally or alternatively, the software may be stored on a tangible non-transitory medium, such as in electronic, optical, or magnetic memory.

Smartphone 26 is but one representative example of a mobile computing device that may be used in embodiments of the present invention, and other classes with suitable cameras, processors, displays, and communication interfacesThe type of device can be equivalently used to perform the functions described herein. Examples of such devices may include tablet computers and other portable computers, as well as head-mounted devices, such asGlasses and dedicated navigation devices.

Smartphone 26 captures and processes an image of a scene containing symbol 28 as set forth above (fig. 1), and sends a message containing the symbol-encoded numerical values to server 34, typically along with other information as set forth above. In response, the server 34 returns information about the location of the symbol to the smartphone. The smartphone typically presents this information on a display 40, typically superimposed on an image of the scene containing the symbol 28. Thus, in the example shown in FIG. 2, assuming that the user 24 expresses an interest in purchasing carpet, the processor 46 overlays the arrow 42 on the display 40 and may also add a textual legend 44 or other graphical information indicating a direction to the desired destination.

This type of display, in which computer-generated graphical elements are superimposed on an image of a real environment in such a way as to simulate the actual physical elements of the environment, is commonly referred to as an augmented reality display. Arrow 42 and legend 44 are merely one simple example of various types of augmented reality elements that may be displayed on display 40. The various elements and their locations corresponding to the locations of the symbols 28 posted in the environment are selected and program controlled by the operator of the system 20 to provide a rich selection of visual cues and promotional content (possibly including animated elements and possibly supplemented by audio, which may vary according to the personal preferences and purposes of the different users in the environment 22).

Fig. 3 is a flow diagram schematically illustrating a method for navigation and augmented reality display, in accordance with an embodiment of the present invention. The method is described with respect to elements of system 20 (fig. 1) and smartphone 26 for purposes of convenience and clarity; the principles of the method may be applied, mutatis mutandis, in virtually any suitable application environment using any desired type of mobile computing device.

As a preparatory step, smartphone 26 receives and stores profile information about user 24, at a profile definition step 50. The user may actively enter profile information (including personal details and preferences) in response to a query from a client software application running on the smartphone. Alternatively or additionally, profile information may be automatically assembled based on user behavior and other sources of information. The application itself may be provided to the user 24 for downloading to the smartphone 26 when the user first enters the environment 22. Additionally or alternatively, the application may be pre-installed on the smartphone.

Within the environment 22, the user 24 opens a client application and typically selects a target in a user initialization step 52. The target may be a particular destination, such as the name of a restaurant or store, or it may be the type of establishment or activity, such as purchasing a carpet or finding the nearest toilet. User 24 then visually searches for an anchor point (symbol 28), and when it is located, clicks smartphone 26 to capture an image of the scene containing the anchor point, at an image capture step 54.

Under control of the client application, processor 46 in smartphone 26 processes the captured image to extract the digital value (also referred to as the anchor ID) encoded by symbol 28, at a processing step 56. Typically, each anchor point in the environment 22 is different and encodes a unique ID. The processor then sends a query to the server 34 indicating the anchor ID, client target and related information from the user profile. Alternatively or additionally, relevant user profile information may be pre-stored in the server 34.

The server 34 processes the query using the stored information about the environment 22. This information typically includes a detailed map of the environment indicating the locations of the facilities and services and the locations of all anchor points. The server combines this information with the user's location, goals, and preferences as provided by the user query and generates a response. Typically, such a response includes one or more graphical elements, and possibly also textual and/or audio elements, for guiding the user 24 to a location that will meet his goal. The response may also include promotional information customized to the user's profile and location.

Server 34 sends such a response to smartphone 26, at a response sending step 58. At a display step 60, the processor 46, under control of the client application, renders the responsive graphical and textual elements to the display 40. Typically, at least the graphical element appears as an augmented reality component in the image displayed on the display at a location on the display that is superimposed or otherwise constrained to the actual location of the anchor point in the image. (alternatively or additionally, smartphone 26 may pre-cache some or all of the anchor points in its immediate vicinity to reduce delays in token generation and display.)

Processor 46 continues to present information on display 40 for as long as the anchor point in question is visible in the image captured by smartphone 26. As the user moves through the environment 22, the location of the information on the display 40 may change along with the location of the actual anchor point in the captured image. If the user proceeds to a position where the original anchor point is no longer visible, he can capture an image containing another anchor point and the information on the display 40 will be updated accordingly until the user reaches the desired destination.

Symbol design

Fig. 4 and 5 are schematic representations of multi-colored computer readable symbols 70 and 80 according to embodiments of the present invention. Both symbols 70 and 80 include a plurality of polygons meeting at a common vertex. In the case of symbol 70, the polygon is a rectangle 72 that meets at vertex 74, while in symbol 80, the polygon is a triangle 82 that meets at vertex 84. Alternatively, other classesPolygons of the type (having five, six or more sides, not necessarily all of the same) may be arranged to touch at a common vertex. Virtually any type of polygon and mosaic pattern may be used. It is desirable (although not necessary) for ease and reliability of decoding that all polygons that touch at a given vertex have different colors. Using N_CColor and N_PVertices common to polygons, which may take the form ofIn different forms and can therefore be used for codingA different digital value.

Fig. 6 and 7 are schematic representations of multi-colored computer-readable symbols 90 and 100 according to further embodiments of the present invention. In these embodiments, a tessellation of multiple polygon tessellations with multiple vertices in each symbol is used to increase the range of digital values that can be encoded and the reliability of identification. (the term "tessellation" is used in the description of the present invention and in the claims to refer to tessellation of a region having geometric shapes so as to fill the region without overlap or gaps between the shapes.) for example, symbol 90 comprises hexagonal tessellations 92, 94 defining six common vertices 96, 98, each having three tessellations joined. The symbol 100 includes rectangular shaped inlays 102 arranged in a 3x3 grid so as to define four common vertices 104.

Each of the vertices 96, 104 of the plurality of symbols 90 and 100 encode a respective digital value, and these values are combined to produce an expanded digital value, e.g., by concatenating the individual values of the vertices. The vertices in symbol 100, with six different color permutations between tessellations 102, may thus be used to encode 126,360 different values. Further, once the locations and distributions of the colors around three of the vertices 104 are known, the locations and distributions of three of the colors around the fourth vertex are uniquely determined. If the fourth vertex coincides with the expected position and color distribution, the mobile computing device processing the image will reject the symbol and in this way will avoid erroneous and incorrect reading of the symbol value.

The tessellated multi-vertex symbols (e.g., symbols 90 and 100) should encode a sufficient number of different numerical values for most applications and environments, such as the type of navigation application illustrated in fig. 1. Symbols containing a larger number of inlays may be used to encode larger values. An asymmetric tessellation may also be used. The ancillary information (e.g., a coarse location provided by GPS or cellular signal strength and cell phone number) can be used to distinguish symbols of the same value that are tiled at different locations.

One key advantage of the type of color-based vertex-centered coding illustrated by the symbols described above (in particular with respect to image-based coding schemes known in the art, such as QR codes) is that the decoding is predominantly scale-invariant. In other words, the relative size of the symbols in the images captured by the mobile computing device, and thus the distance between the device and the symbols, has little or no effect on decoding over a large size range.

To read the digital values encoded by the candidate vertices, for example, the processor 46 may select candidate vertex positions and then calculate the color of the sample points in each polygon around the vertices at some displacement from the vertices. These sampling points, referred to herein as probes or probe locations, are typically located along the bisectors of the angles between the color edges of the polygons. The number of probes and the angles between them are therefore determined by the type and number of polygons surrounding each vertex, as shown in the preceding figures. The candidate vertex positions (obtaining sample points around the candidate vertex positions) may be found by locating the color edges that are in contact at the vertices and taking the positions at the intersections of the color edges, or they may be found by any other suitable methodIs selected or even randomly selected. As long as the polygonal tesserae are not smaller than a certain displacement vectorColor detection at such displaced polygons will result in the same color, regardless of scale.

This type of vertex-centered coding is also robust to rotation: as long as the rotation is less than half the minimum vertex angle (e.g. less than 45 deg. for a rectangular tessellation), there is no need to adjust the color detection direction along the bisector. The information provided by inertial sensors (e.g., accelerometers) available in most smartphones and other mobile computing devices can be used to distinguish and correct for color detection angles regardless of the rotation of the camera itself. The vertices themselves function as record marks so that no additional record marks need to be added to the anchor points.

Colour scheme

Virtually any set of colors that can be distinguished by an image sensor may be used to color a polygonal tessellation around vertices in a symbol in accordance with embodiments of the present invention. However, the inventors have found that a certain class of color schemes is advantageous in supporting reliable, efficient color recognition using commonly available image sensors. This type of color scheme may be applied in generating symbols for the vertex-based encoding method described above. Such a color scheme is useful not only in this particular encoding method but also in other techniques of color-based encoding.

In one embodiment of the present invention, the number of colors is set to N_CA set of the primaries "red" (R), "green" (G) and "blue" (B) and their respective complements "magenta" (M), "cyan" (C) and "yellow" (Y) is used 6. This set of colors has some advantages:

the primary colors that join some of these colors and even more of these interfaces are relatively rare in natural environments. This feature is beneficial for identifying anchor points by humans and computers and assisting robust decoding.

RGB is the native color space of the digital image generated by the camera. Complementary colors can be easily calculated as M-G + B, C-R + B, Y-R + G.

·N_C6 is sufficient for rectangular, hexagonal and triangular tessellations, as illustrated above.

The present embodiment uses a three-dimensional binary representation of color:

1.R＝(1,0,0)

2.G＝(0,1,0)

3.B＝(0,0,1)

4.C＝(0,1,1)

5.M＝(1,0,1)

6.Y＝(1,1,0)

each of the three dimensions represents a Primary Color Channel (PCC).

In this embodiment, the colors surrounding any given common vertex are all required to be different from each other and are required to vary in the binary representation of each PCC in the PCC, i.e., vertices around all of their surrounding colors having the same R, G or B bit value are not allowed. The vertices of three mosaics, such as color R, G, B, comply with this criterion because no binary PCC is constant for all mosaics. In another aspect, the three mosaics of color C, G, B do not comply with this criterion because the red binary PCCs are zero for all of them. In a six color cluster, this constraint only applies to a hexagonal tessellation, since any arrangement of triangular or rectangular tessellations of different colors around the vertices will satisfy the constraint.

The rectangular tessellation of the symbol is advantageous because it geometrically matches the tessellation of the sensor elements used in imaging the symbol and also tends to match the available space for posting anchor points in a ubiquitous closed environment. A rectangular mosaic can easily be expanded horizontally to compensate for horizontal foreshortening, which may occur when the image of the anchor point is captured at an angle, as will often be the case, rather than frontally.

Fig. 8 is a flow chart that schematically illustrates a method for decoding a multi-color symbol (e.g., symbol 100) of the above design, in accordance with an embodiment of the present invention. At a color detection step 110, for each image coordinate vector r ═ x, y, given vertex position of the image representing the symbol, processor 46 extracts N_PColor detection values V_p(p＝1,...,N_p). These values correspond to the probe coordinates v_p＝r+d_pImage color intensity of I (v)_p). Displacement vector d_pAll having the same length | d_pD, but corresponds to a different orientation of the anchor point geometry. In particular, for a rectangular tessellation, d₁＝(D,D)、d₂＝(-D,D)、d₃(-D, -D) and D₄(D, -D), whereinIs a natural number.

Typically, the angle between adjacent displacement vectors is 2 π/N_p. As mentioned above, such angular distribution of displacement vectors implies with respect to up to π/N_pRobustness of image rotation. For a triangular tessellation, d_pRound off [ d (sin phi ]_p,cosφ_p)]Wherein phi_p＝(2p-l)π/N_pFor p 1. For a hexagonal tessellation, the six vectors are separated into two sets of even and odd numbers p, corresponding to the two possible types of vertices as represented by vertices 96 and 98 in FIG. 6.

Length parameter D determines the smallest detectable anchorPoint image dimensions. Very small values (e.g. 1 or 2 pixels) correspond to a very local set of probes, which in principle can pick up a small number of pixels (with D)²Of the order of magnitude) of the anchor point captured. With larger values of D, anchor point recognition becomes more robust, but generally works well for any D ≧ 3. Even larger symbols can still be robustly identified using smaller D values because the vertices are locally defined independent of anchor point size. Thus, one option to use D is sufficient to detect both small and large anchor points.

The next stage is to classify each probe as N_COne N of the colors_CAnd (4) color. Fig. 8 shows a reliable method for this purpose, which implements the type of local white balance in the native RGB space and imposes a set of requirements that automatically exclude candidate vertices that are potentially unreliable. Specifically, at PCC estimation step 112, processor 46 first finds the maximum intensity value I for each of the three pure (RGB) color channels (PCC) for each of the probes_c ^{Maximum of}＝max_p({I_c(v_p) }) and a minimum intensity value I_c ^{Minimum size}＝min_p({I_c(v_p)}). With a threshold Δ that must be above some absolute dark threshold_c ^{Minimum size}(i.e. I)_c ^{Maximum of}>Δ_c ^{Minimum size}) The first requirement of the probe for any given maximum value of PCC is to estimate at the dark threshold estimation step 114. With a corresponding maximum value (i.e., I) that must be significantly less than the color_c ^{Minimum size}/I_c ^{Maximum of}<ρ_c ^{Minimum size}) The second requirement for a probe of the minimum value for a given PCC is an estimation in a ratio threshold estimation step 116. At a fail step 122, if the color detection values are not able to meet these requirements, the processor 46 rejects the candidate vertex.

Finally, based on the range R between the extreme values in each PCC_c＝I_c ^{Maximum of}-I_c ^{Minimum size}The processor 46 is based on a relative threshold τ_c ^{Minimum size}And τ_c ^{Maximum of}Applying PCC binary value V_p,cIs assigned to each probe so as to be 0<τ_c ^{Minimum size}，τ_c ^{Maximum of}<1, wherein τ_c ^{Minimum size}+τ_c ^{Maximum of}≦ 1, in PCC assignment step 118. Specifically, the method comprises the following steps:

V_p,c0 if I_c(v_p)<I_c ^{Minimum size}+τ_c ^{Minimum size}R_c，

V_p,c1 if I_c(v_p)>I_c ^{Maximum of}+τ_c ^{Maximum of}R_c，

And V_p,cNot otherwise defined. If any V_p,cAt this stage, it is not defined, then the test for the vertex fails and the process again terminates at step 122.

If the candidate vertex successfully passes through steps 114-118, processor 46 groups in triplets (V) in the binary PCC representation_p,r,V_p,g,V_p,b) In a form that assigns a specific color to each probe. However, in addition to the six color scheme defined above, binary triplet (V)_p,r,V_p,g,V_p,b) There may be two additional disallowed configurations: k ═ 0,0,0 and W ═ 1,1, 1. Processor 46 checks that none of the triplets of binary PCCs is K or W and there are no two probes with the same color value around the candidate vertex at color checking step 120. The latter condition is checked by a pair-wise comparison between the probes.

If these final conditions are met, the processor 46 identifies as a vertex a point corresponding to the center of the cluster of pixels meeting the color vertex condition, at a vertex identification step 124. The processor assigns vertex IDs by combining individual polygon color values, for example, by converting the three-bit binary PCC values for each probe to a three-bit binary number and thenHandle N_pThe probes are connected as a single binary number. The ID for the entire multi-vertex anchor may be found, for example, by a separate ID connecting the vertices.

The robust detection of vertices can be strongly influenced by the choice of color. Because anchor points may occupy only a small portion of the captured image, their illumination may typically be very different from the overall image illumination, which affects the exposure and gain applied by the camera. In fact, the inventors have found that the reading of the PCC value for a given anchor mosaic can be varied, typically by a factor of three, with respect to the applied exposure and gain that will be optimal for that mosaic. For example, if most of the image is in full sunlight but the anchor point appears in shadow, its PCC value is very low compared to images where the anchor point is also in full sunlight. Conversely, if most of the image is in shadow but the anchor point is accidentally illuminated more strongly, then the PCC value will be very high.

A further constraint to be considered is that the reflective colour of real objects (including colour pigments) has physical limitations in terms of colour separation. Thus, the captured RGB image of "pure color" will necessarily have a non-negligible contribution also in the "wrong" channel. For example, an attempt to produce a "pure green" primary on a calibrated printer compliant with the well-known offset web printing Specification (SWOP) using ink concentration CMYK ═ 100%, 0, can produce a color value in the captured image given by RGB ═ 80 (0,166,80), where the "wrong" channel of red has a non-negligible value of 80. To avoid this type of situation, which may lead to loss or misidentification of symbol vertices, embodiments of the present invention provide a co-optimized solution for the parameters described above for color detection with the color rendering performance of the device to be used to actually generate anchor points.

To support this type of scheme, a method for scoring a set of colors is introduced. The method scores the color set based on the actual RGB values of the color set anchor point mosaic in the captured image, or alternatively uses the sRGB color space to predict these values. (the sRGB color space is defined by IEC Specification 61966-2-1:1999 and is commonly used when calibrating color image sensors and cameras.) the set of colors for the anchor symbol is then selected in a manner that optimizes the score.

To calculate the score, H for a given set of RGBCMY colors¹ _cAnd L¹ _cThe highest observation value and the lowest observation value of the color c that is 1 in the binary representation of the color set are obtained separately. Similarly, H⁰ _cAnd L⁰ _cIs the highest and lowest observation for color c, which is 0 in the binary representation of the color set. In other words, H¹ _cAnd L¹ _cRespectively, the highest and lowest observations of color c among the color elements expected to contain color c, and H⁰ _cAnd L⁰ _cIs the highest observed value and the lowest observed value of color c among color elements expected not to contain color c. For c ═ red, for example, a red color element, a yellow color element, and a magenta color element are expected to contain such a color, while a green color element, a blue color element, and a cyan color element are expected to not contain such a color.

For example, the primary color generation scheme is selected on a calibrated SWOP printer:

r is produced by CMYK ink density (0, 100%, 0)

G is produced by CMYK ink density (100%, 0, 100%, 0)

B is produced by CMYK ink density (100%, 100%, 0,0)

C is produced by CMYK ink density (100%, 0,0,0)

M is produced by CMYK ink density (0, 100%, 0,0)

Y is produced by CMYK ink density (0, 100%, 0)

For a camera calibrated according to the sRGB specification, the observed color values will then be:

captured R- (237,28,36)

Captured G- (0,166,80)

Captured B- (46,48,146)

Captured C- (0,173,239)

Captured M- (236,0,140)

Captured Y- (255,242,0)

These measurements result in the following high and low values for each color:

·H⁰ _{red colour}46, G, B, C, anchor color with red-0 in binary representation

·L⁰ _{Red colour}0, G, B, C, anchor color with red-0 in binary representation

·H⁰ _{Green colour}Anchor color of green-0 in binary representation, 48, R, B, M, highest green

·L⁰ _{Green colour}0, R, B, M, anchor color with green-0 in binary representation

·H⁰ _{Blue color}80, R, G, Y, anchor color with blue 0 in binary representation

·L⁰ _{Blue color}0, R, G, Y, anchor point color with blue-0 in binary representation

·H¹ _{Red colour}255, R, M, Y, anchor point color with red equal to 1 in binary representation

·L¹ _{Red colour}Anchor color of red-1 in binary representation, lowest red of 236, R, M, Y

·H¹ _{Green colour}The anchor color of green-1 in binary representation, 242, G, C, Y, being the highest green

·L¹ _{Green colour}166, G, C, Y, the anchor color green-1 in binary representation

·H¹ _{Blue color}The anchor color, blue 1 in binary representation, is the highest blue of 239, B, C, M

·L¹ _{Blue color}140, B, C, M, anchor point color with blue equal to 1 in binary representation

To reduce false positives in common vertex detection, each dark threshold Δ_c ^{Minimum size}Is selected to be as large as possible. For increasing dark threshold delta_c ^{Minimum size}Is reached at a point where it prevents detection of a vertex when due to the lighting condition Δ_c ^{Minimum size}Becomes greater than L¹ _cThen (c) is performed. Thus, the dark threshold Δ is maximized_c ^{Minimum size}Equivalent to selecting L¹ _cA large value of (a). Similarly, the minimum gain ratio ρ_c ^{Minimum size}Should be as small as possible, which is equivalent to choosing a large value of 1/(H)⁰ _c+ δ). (constant value δ is introduced to prevent at H⁰ _cA singularity of 0. ) Combining the above two observations into a score that promotes reliability for the illumination variation corresponding to the maximization:

setting δ to a maximum value of 255 (assuming eight bits per color representation) conveniently constrains the score to the range of 0 to 1.

τ_c ^{Minimum size}Value of (d) and τ_c ^{Maximum of}The strict selection of values of (a) significantly reduces the chance of encountering false positive vertices, thereby increasing the reliability of vertex detection. The most stringent value τ_c ^{Minimum size}And τ_c ^{Maximum of}Can be separately (H) by implementing their lower bound⁰ _c-L⁰ _c)/(L¹ _c-L⁰ _c) And (H)¹ _c-L¹ _c)/(H¹ _c-H⁰ _c) The discovery is given. Because of tau_c ^{Minimum size}+τ_c ^{Maximum of}1, so these requirements can be conveniently combined to maximize:

the two scores are combined into a single optimization score: s ≡ S^{Reliability of}*S^{Strength of}。

For each approach to anchor color generation, the above-mentioned fractional optimization process is implemented to obtain the best set of anchor generated colors.

For the primary anchor color generation scheme mentioned above, the optimization score cannot even be calculated, since when calculating:

τ_{blue color} ^{Minimum size}＝(H⁰ _{Blue color}-L⁰ _{Blue color})/(L¹ _{Blue color}-L⁰ _{Blue color}) 0.57 and

τ_{blue color} ^{Maximum of}＝(H¹ _{Blue color}-L¹ _{Blue color})/(H¹ _{Blue color}-H⁰ _{Blue color}) 0.62, find range summation rule τ_c ^{Minimum size}+τ_c ^{Maximum of}≦ 1 is violated.

Tables I and II below show the results of optimization of anchor color generation schemes for two different types of printing inks to minimize τ_c ^{Minimum size}+τ_c ^{Maximum of}And thus maximize the score S for the sRGB sensor:

table I-American Fabric coating (SWOP)

	Anchor point R	Anchor point G	Anchor point B	Anchor point C	Anchor point M	Anchor point Y
							Cyan ink density [% ]]	1	71	92	75	0	3
Magenta ink Density [% ]]	91	0	91	23	90	45
							Density of yellow ink [% ]]	79	100	0	41	0	86
Black ink density [% ]]	0	20	0	1	0	1
							sRGB Red	236	60	60	60	238	237
sRGB Green	62	153	62	152	61	153
							sRGB blue color	62	60	153	153	150	61
Color comparison L	54	56	30	58	56	71
							Color comparison of a	66	-43	21	-28	72	27
Color comparison of b	42	39	-51	-9	-7	59

Table II-coated FOGRA27(ISO 12647-2-2: 2004)

	Anchor point R	Anchor point G	Anchor point B	Anchor point C	Anchor point M	Anchor point Y
							Cyan ink density [% ]]	0	80	95	77	0	9
Magenta ink Density [% ]]	87	0	85	10	86	42
							Density of yellow ink [% ]]	85	100	0	49	0	89
Black ink density [% ]]	0	0	0	0	0	0
							sRGB Red	229	31	29	35	230	230

sRGB Green	62	161	62	161	61	160
							sRGB blue color	46	45	143	143	140	44
Color comparison L	54	56	30	58	56	71
							Color comparison of a	66	-43	21	-28	72	27
Color comparison of b	42	39	-51	-9	-7	59

Thus, as can be seen in the above examples, the use of the scoring criteria set forth above in selecting the proportions of cyan, magenta and yellow pigments to apply to the substrate results in a symbol whose color elements (in this embodiment polygonal inlays) can be unambiguously identified in the image of the symbol as red, green, blue, cyan, magenta or yellow color elements. One reason is that the red, green, and blue color elements have respective red intensities, green intensities, which are greater than twice the intensities of the other primary RGB colors when measured in the sRGB color spaceDegree or blue intensity. Similarly, for the cyan color element, both the blue and green intensities are greater than twice the red intensity; for magenta color elements, both the red intensity and the blue intensity are greater than twice the green intensity; and for the yellow color element, both the red intensity and the green intensity are greater than twice the blue intensity. Thus, τ_c ^{Minimum size}And τ_c ^{Maximum of}Can be used to robustly and reliably separate different colors.

Another advantageous result of the use of the scoring criteria described above is that all of the intensity values of the produced colors are clustered around, but not in between, any one of the particular low values or the particular high values. For example, the blue sRGB values in Table I are all within the range 61 + -1 or the range 151 + -2. Color schemes known in the art do not exhibit this type of behavior. Using the reliability scores defined above, a set of colors may be defined generally such that S^{Reliability of}Component (b) ofC (red, green or blue) is greater than 0.8 for any PCC.

As mentioned above, although the above color schemes are described herein specifically with respect to vertex-based encoding methods that use colored polygon tessellations, the same type of scheme may be used in generating other types of color elements used in other color-based encoding schemes.

By using the sRGB color space to estimate the color score, the selection of pigments for use in generating anchor points may be optimized with respect to the known spectral properties of Color Filter Arrays (CFAs) and image sensors used in common smartphones and other mobile computing devices. The inventors have found that, although different vendors use different CFAs, the crossover between the green filter response curve and the blue filter response curve at about 500nm (i.e., at a wavelength whose green filter attenuation is equal to that of the blue filter), and the crossover between the green filter spectral response curve and the red filter spectral response curve at about 580nm (at a wavelength whose green filter attenuation is equal to that of the red filter) are nearly identical between all of the major vendors. These spectral intersections are insensitive to variations in illumination.

Two stable intersections at 500nm and 580nm define a set of six colors according to their spectral reflectivities:

"Red"

"Green"

"blue"

"blue-green"

"magenta"

"yellow"

Selecting a combination of pigments having properties as close as possible to those specified by the above formulas will give an anchor point color that maximizes the difference between R, G and the B value in the image of the anchor point. Specifically, for each PCC R, G and B, C_RIs optimized in terms of maximum distinction from red-green and red-blue; c_GIs in contact with greenThe aspect of maximum distinction of color-red and green-blue is optimized; c_BIs optimized for maximum blue-red and blue-green discrimination; "blue-green" C_CIs optimized for maximum green-red and blue-red differentiation; "magenta" C_MIs optimized for maximum red-green and blue-green discrimination; and "yellow" C_YIs optimized for maximum red-blue and green-blue discrimination. Since the typical wavelength range for sensor sensitivity is limited to 390nm<λ<680nm (due to the infrared cutoff), the anchor color set spectral characteristics are also limited to this range.

In generating the anchor points, it is desirable that the anchor points exhibit lambertian reflections (masks) that minimize the effects of the unidirectional reflections. Alternatively, under poor lighting conditions, the anchor points may be covered by a retro-reflective coating (e.g., a light-reflective transparent coating made of high-index microscopic glass beads). When a light beam (e.g., light produced by camera flicker) penetrates from the anchor surface, the cladding layer reflects back to the anchor color of the underlayer.

As mentioned above, the above selection of colors is suitable not only for the kind of polygonal-shaped mosaic symbols described above, but also for other types of color-based computer-readable symbols. It will thus be appreciated that the embodiments described above are cited by way of example, and that the present invention is not limited to what has been particularly shown and described hereinabove. Rather, the scope of the present invention includes both combinations and subcombinations of the various features described hereinabove, as well as variations and modifications thereof which would occur to persons skilled in the art upon reading the foregoing description and which are not disclosed in the prior art.

Claims (6)

1. An information system, comprising:

a plurality of symbols, each symbol comprising a plurality of polygons meeting at a common vertex and having different respective colors selected such that the symbols encode respective digital values,

wherein the digital values are encoded by assigning to each color a three-digit digital code comprising respective binary values of three primary color components representing the colors of the polygon, and combining the three-digit digital codes to give the assigned digital values, and

wherein the colors of the polygons are selected such that none of the binary values is constant across all of the polygons that are contacted at the common vertex, and none of the colors has a value of K ═ 0,0,0, or W ═ 1,1, 1; and

a server configured to receive a message from a client device indicating a numerical value decoded by the client device when capturing and analyzing an image containing one of the symbols, and to provide an entry of information corresponding to the numerical value to the client device in response to the message.

2. The system of claim 1, wherein the plurality of symbols are distributed at different respective locations within an environment, and wherein the server is configured to determine a location of the client device responsive to the numerical value and is configured to provide the entry responsive to the location.

3. The system of claim 2, wherein the entry comprises a graphical element configured to be overlaid by the client device on a display containing an image of one of the symbols.

4. A computing device, comprising:

an image sensor configured to capture an image containing a symbol comprising a plurality of polygons touching at common vertices and having different respective colors selected to encode a specified digital value,

wherein the digital values are encoded by assigning to each color a three-digit digital code comprising respective binary values of three primary color components representing the colors of the polygon, and combining the three-digit digital codes to give the assigned digital values, and

wherein the colors of the polygons are selected such that none of the binary values is constant across all of the polygons that are contacted at the common vertex, and none of the colors has a value of K ═ 0,0,0, or W ═ 1,1, 1; and

a processor configured to process the image to decode the digital values.

5. The apparatus of claim 4, and comprising a display coupled to display an image captured by the image sensor, wherein the processor is configured to superimpose a graphical element on the display in response to the digital value.

6. The apparatus of claim 5, and comprising a communication interface, wherein the processor is configured to send a message containing the digital value to a server via the communication interface over a network, and to receive the graphical element from the server in response to the message.