5
\$\begingroup\$

A Gray code gives an absolute position in 1D. What's the equivalent for 2D?

For instance, imagine I build an XY table. I paste a checkerboard-style encoding pattern underneath (or QR-code style). I fix an ESP32-CAM looking up at the checkerboard - it can see only part of the checkerboard, e.g. 10% by 10% = 1%. The checkerboard is cleverly designed so that any 1% patch is unique.

Has it been done? What are the Google search terms? What is the ideal checkerboard pattern?

Maybe this isn't an EE question (but optical sensors are a popular topic here!). Maybe it's more suitable for "chat".

\$\endgroup\$
2

4 Answers 4

6
\$\begingroup\$

You're looking for Anoto dot patterns, also known as digital paper. It's based on De Bruijin sequences. One implementation is found in py-microdots.

\$\endgroup\$
3
  • \$\begingroup\$ this is so neat! coincidentally, I need something very similar along a hexagonal grid, and that gives me so much to read up on! Thanks :) \$\endgroup\$ Commented 14 hours ago
  • \$\begingroup\$ That's great - thanks. The Anoto dots are nice but I feel that more "edges" would allow finer (sub pixel) positioning with a lower resolution camera. A De Bruijn sequence is 1D but the Wikipedia article leads on to the 2D version: a De Bruijn torus.. Fantastic! \$\endgroup\$ Commented 13 hours ago
  • 1
    \$\begingroup\$ The Anoto dots (or more generally, the DeBruijin torus, regardless of how the symbols are encoded) give you the coarse global position. Fine position is derived by determining the position/orientation of the underlying grid in the image, which could be done with either dots or edges. \$\endgroup\$
    – Dave Tweed
    Commented 13 hours ago
3
\$\begingroup\$

Sorry to nitpick on terminology here, but I need to correct the terminology so I can more easily give an answer that helps you:

A Gray code gives an absolute position in 1D. What's the equivalent for 2D?

Nope. Gray Coding is just a way to encode consecutive numbers as binary vectors. Just as writing down these numbers as "straight" binary numbers; or, really, any other way to write down as many binary vectors as you have values to encode.

What gives an absolute position is putting these binary vectors as black/white (or transparent/opaque, or whatever) on a strip or disk, and reading the vector you're currently at, and then reversing that mapping.

Gray Coding has exactly one advantage here: neighboring positions change in only one binary value. That's a big advantage, technically, because it eliminates a whole class of errors that happen on the boundaries of positions. But it's not necessary for positioning.

Now, one fundamental problems arises:

In an encoder disk or strip, there's the second dimension along which you can produce that binary vector. On a 2D surface, where do you put the extra dimension? That doesn't exist; you could only go into the third dimension, i.e., normal to the 2D surface you want to position on. But then you have no direction to look at the code optically.

So, that's where this concept fails. There cannot be an equivalent for optical positioning.

Thus, you need to come up with something else. You could, for example, just put QR codes (or similar square data codes, QR is certainly not the best choice here) with positions on a square grid, and read them. You'd need a 2D sensor (as opposed to the 1D sensor on a 1D code), and it would need to have a viewport that's large enough to find the closest "whole" 2D code to the position you're on, thus, at least twice the length in each direction.

So, while this isn't a Gray Code equivalent, the Digital Paper type of 2D surface covering that Dave Tweed's answer points you to is probably exactly what you are looking for. The Anoto implementation of that idea, using De Brujin sequences along rows and columns, and using displacement of a single dot relative to a grid to represent the resultant values, is quite frankly ingenious.

\$\endgroup\$
3
  • \$\begingroup\$ I hate to burst your bubble, but this has been a solved problem for something like 25 years. \$\endgroup\$
    – Dave Tweed
    Commented 14 hours ago
  • \$\begingroup\$ @DaveTweed oh I love that bubble being burst – love it! Even if technically, this is nothing like a 1D Gray Code extended to 2D (it's locally decodable 2D patterns, which is much more fun), I didn't know about that. I'd say it's not an equivalent – but it's probably what OP was looking for! Let me fix my answer to that end. If I could, I'd upvote your answer twice :) \$\endgroup\$ Commented 14 hours ago
  • \$\begingroup\$ "Absolutely"-- pun intended. Absolute position encoders don't need to use gray codes, as they don't maintain a count. You read them, and that's the position. Gray codes make it easy to recognize when you've missed a transition, and are typically used when using an absolute position reference in conjunction with a relative encoder. \$\endgroup\$ Commented 12 hours ago
2
\$\begingroup\$

Has it been done?

The conventional way is the use two sensors; one for the x axis and one for the y axis. Both together can pin-point any 2D position. This method also extends to accelerometers that are both 2D and 3D.

\$\endgroup\$
2
  • \$\begingroup\$ Yes but ... I'm looking for better than 0.1mm accuracy and the problem is backlash and play. Lead-screws and stepper motors have backlash; the slides that the table moves on have play. Digital calipers are cheap and can give very precise feedback but the table will still have play, backlash, and runout. Hence some sort of optical feedback seems a good idea. (Beware the latest cheap calipers on eBay: they don't have the pads to pick up the serial signal - as I found to my cost.) \$\endgroup\$ Commented 11 hours ago
  • 1
    \$\begingroup\$ that doesn't seem to preclude the 2D-by-combining-two-axes approach at all; there's high-precision CNC machines that do something like that. Even the accelerometric method, even though it implies a double integral, can achieve that precision. \$\endgroup\$ Commented 10 hours ago
1
\$\begingroup\$

If you are going the camera way, then you might want to look into Aruco Tags. Those tags have an unique identifier, and are designed to be "as distinct as possible from each other" (a bit like for gray code you mentioned).

Detecting a single tag gives you your complete 3D pose (position and orientation) relative to the tag (provided your camera is calibrated and you know the size of the tag). So if you have an array of such tags, it's enough to always see one to get your exact position.

Note that there are 2 "limitations" that can still justify trying to see at least 2 or 3 tags :

  • when the image is of low quality / the tag is far away, the perspective effect is diminished, and you might read a position that is the axial symmetry of your real position.
  • in particularly bad conditions (like outdoors, with the shadows of trees for example), I have already seen wrong detections. But this can be greatly reduced by using tags with more pixels (but that are not visible from as far away, but that don't seem a problem for your situation), or by checking on a few successive pictures to be sure, or by requiring to see at least 2 tags with coherent positions
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.