This is a work in progress and sudden, dramatic changes are expected!

Free tag generator here https://freelens.sjtrny.com

This project provides a reference implementation of NaviLens and ddTag for educational or personal use. Commercial use is at your own risk as NaviLens and ddTag may attempt to enforce their patents.

pip install freelens

from freelens import Tag

message = "101010101011000000001011"

tag = Tag.from_message(message, 5)

tag_img = tag.to_image()

tag_img.save("tag.png")

from freelens import detect_tags
from PIL import Image

img = Image.open("dataset/positives/PXL_20241124_081401367.MP.jpg")

tags_list = detect_tags(img, n=5)

for tag in tags_list:
    print(tag.message)

NaviLens is a service that provides navigational data resolution, based on ddTags ("distant dense tag") placed around the environment. The tags are designed so that they can be quickly scanned with a mobile device while moving or on moving objects and at a much greater distance than QR codes. A scanned tag is converted into a message on a users device, the message is then sent to the NaviLens web service, which responds with the associated data for the tag.

The main use case of NaviLens is to improve navigation for those with visual impairments. For example a tag could be placed on the front of a bus so that a visually impaired person can hold their phone camera up to the approaching bus to read the route number.

These tag images must be requested from NaviLens who are the central data resolution authority and maintain a database with the associated data for each ddTag.

The typical 5x5 ddTag can only represent 16,777,216 unique combinations. The first line of defence against running out of codes is to use larger dimension codes (see specification below).

I spectulate that another avenue that NaviLens will explore is to divide the world into smaller geographic regions, within which it allocates tags to users. This allows tags to be safely re-used without collision.

A ddTag consists of a small grid of coloured squares, which represents a "message" of binary data. The typical implementation uses a 5x5 grid, which represents a 24 bit message, with cyan, magenta, yellow and black coloured cells.

The data encoded in the tag consists of two parts:

1. the "message", which is a binary sequence, and
2. a CRC checksum, used to verify the message.

ddTags officially come in the following sizes:

• 5x5
• 7x7
• 9x9
• 11x11

The tag visually consists of three nested components, which are from the outside moving inwards:

1. Outer quiet zone
2. Inner quiet zone
3. Tag grid

The outer quiet zone is a border region of a solid colour, usually white, and should be at least as thick as the inner quiet zone for best detection results. The inner quiet zone is a border region of a solid colour which must be:

• one on of the four colours used by the ddTag code grid, typically black,
• the same width as the cells in the tag grid.

The grid consists of a square grid, with each cell coloured by one of four colours. Each cell in the grid represents two bits of data (00, 01, 10 and 11) since it is in one of four states.

The grid uses an odd numbered size because an unambiguous center position is required for two features:

• central cell is used to encode the grid size
• central row and column are used to hold a CRC checksum

The corners do not contain any message data. Instead, they are used as follows:

• The bottom left cell must contain the darkest colour, e.g. black, from the colour palette as this is used to orient the tag.
• The other corners are used to infer the colour palette used by the tag, so they must have distinct colours.
• The other corners determine bit value associated with each colour, which starting from the top left and moving clockwise around the grid are 00, 01, 10, 11. For example if the top left corner is cyan then all cyan cells have the value 00.

The central cell does not contain any message data. In the patent, this cell is reserved for encoding the size of the grid. The patent uses the following encoding scheme:

To ensure data integrity, the grid contains a CRC code, which is contained in the center row and column excluding the center cell. The CRC length varies with the dimensions of the grid. The patent lists the following correspondence:

Note that I have not been able to verify the checksums on NaviLens generated tags as described in this issue.

The patent does not describe the process for generating the CRC apart from "The CRC is calculated from the message" and it is possible that the message is transformed before the CRC is generated.

This library generates CRCs from the message content without any prior transformation.

The message is formed by concatenating the binary values of the remaining cells in "reading order", which is described in the patent as:

from left to right and from top to bottom

Most sane people would interpret this as reading row by row, starting with the first row, reading all the values in it from left to right, and then moving to the next row below it. However, this interpretation is incorrect for tags distributed by NaviLens, which are read column by column.

To maximise compatibility, we have adopted this psychotic interpretation.

The ddTag patent does not describe a particular process for detecting "frames" and leaves it up to the implementor. However it suggests that [2] may be used.

In detect_frames we use a modified version of [2] as follows:

1. Convert image to grayscale
2. Detect edges by local adaptive thresholding
3. Detect contours by Suzuki's method
4. Fit polygon to contours
5. Apply filters:
   1. 4-vertex polygons.
   2. Area greater than threshold
   3. Convex polygon
   4. Shape is roughly square (perimeter/area test)
   5. Check that border around frame is white

This process is adapted from the patent.

For each un-rectified frame polygon:

1. Convert image to CIELab colour space
2. Un-warp frame image to square aspect ratio and resize to a fixed size
3. Get the cell colours from the center positions of each cell in the grid
4. Obtain the palette colours from the four corners of the grid
5. Assign each cell in the grid to the closest colour in the palette
6. Validate tag
   1. Convert cells to binary using the rule that the palette is ordered clockwise starting at the top left with the binary values 00, 01, 10, 11.
   2. Extract message code and CRC code.
   3. Validate message code with CRC code.

[1]: European Patent EP3561729NWA1

[2]: Garrido-Jurado, S., et al. (2014). Automatic generation and detection of highly reliable fiducial markers under occlusion. Pattern Recognition.