# Determine the position of a ball joint by image processing

I am wondering if it is possible to sense the position of a ball joint using:

• A photodiode array from an optical mouse, embedded in the socket
• A specific pattern deposited onto the ball
• A processor that can use the exposed part of the pattern to identify which part of the ball it is looking at and how it is oriented.

I imagine something similar to a de Bruijn Torus, that can be projected onto a spherical surface rather than a torus or plane, would do the trick.

Is there a known algorithm for generating and/or decoding such an image?

• The optical mouse sensor is a really good idea. They pack a lot of DSP punch nowadays, and can track on a variety of surfaces (as we all know). It gives relative motion, so integrating for position would be up to you. – tyblu Jan 13 '11 at 17:35
• @tyblu - If you look at the link (de Bruijn Torus), it seems he's interested in absolute positioning. – Connor Wolf Jan 14 '11 at 23:37
• if you're using a ball joint, I assume something protrudes from a spot on the ball. If that is true, can you go away from sensing features on the ball, to sensing based off of the position of the link? What are the ranges of motion that you have to support with this ball joint? Do you have a basic sketch? – Dave Jan 15 '11 at 21:28
• Going by the optical mouse idea, I've heard there are trackballs that do absolute positioning. In which case you could more or less just use that device as is. Even if it's only relative, maybe it's sufficient for your needs and you save a lot of work. – Christian May 10 '15 at 18:14

# finding absolute position on a sphere

## finding absolute position on a plane

Yes, there are several such patterns used to determine absolute position on a plane:

When a digital pen is used on digital paper, two key steps in the algorithm are (a) decoding the part of the pattern visible from the pen into bits, and (b) decoding those bits into an absolute location, which indicates which page in the notebook and a coarse position on that page. Or in other words, when designing the system and deciding where the ink goes on the paper, the system designer first (b) chooses some pattern of bits on a grid, perhaps the cyclic single-track gray code used in the Anoto address carpet or a de Bruijn torus or a variety of other patterns of bits-on-a-grid. Then the system designer (a) chooses one of a variety of ways to represent each bit as ink on paper.

Aboufadel, Smietana, and Armstrong; "Position Coding" give a detailed description of a few of the possible choices for (a) and (b). If I understand correctly, the Anoto address carpet uses a sequence closely related to a de Bruijn sequence, but it is technically not a a de Bruijn torus.

Hecht; "Printed Embedded Data Graphical User Interfaces" give a detailed description of DataGlyphs, which he uses for (a), and the "carpet code" he uses for (b). Jeff Breidenbach and I use the phrase "a DataGlyph address carpet" for that particular combination of (a) and (b).

## adapting a flat pattern to a sphere

There's several ways of projecting such "flat" patterns onto a sphere; perhaps using a projection such as the quadrilateralized spherical cube or some other geodesic grid technique for pixelizing the sphere. All such projections have one kind of distortion (lots of seams) or another (a lot of stretching in some regions compared to others) or some sort of compromise (a few seams, and somewhat less stretching); hopefully you can find one that works OK with your hardware.

## Native spherical patterns

• As Nick T mentioned, a "random dot pattern" will almost certainly show many unique patterns that, after "calibrating" by memorizing the particular patterns on this particular ball and their exact position on this ball, can be used to determine absolute position. This completely avoids the "projection distortion" problem.

## De Bruijn torus

I don't quite see why the de Bruijn torus wouldn't work

It almost works.

A de Bruijn torus works fine as the grid of bits in an address carpet for finding absolute position on a plane. The most popular address carpet systems use other bit patterns that are easier to decode than a de Bruijn torus, even though they require the sensor to view slightly more modules.

A de Bruijn torus would also work fine as the grid of bits in an address carpet for finding absolute position on a torus or a section of a cylinder -- with careful design, the pattern could be designed to "match up properly" traveling the full circle around the circumference of a cylinder, and to "match up properly" traveling both full circles around both circumferences of a torus.

Starting near (for example) the city of Accra, with careful design one could design a pattern based on a de Bruijn torus that completely covered a narrow band near the equator and "matched up properly" traveling the full circle around the equator (but left the poles uncovered). Alternatively, starting near the same city, with careful design one could use print exactly the same pattern near the city of Accra, but extend it along the the prime meridian and the international date line, covering both poles. Those two approaches would print exactly the same pattern on the globe near Accra, but alas, a de Bruijn torus gives conflicting patterns at Accra's antipode on the international date line near the equator.

Is there some other pattern similar to a de Bruijn torus that "matches up properly" in both directions at the same time, when printed to completely cover a sphere or even a cube? So far no one seems to be able to find one, and so we are forced to use systems that can tolerate "seams" in the pattern, in the same way that mapmakers are forced to cut at least one seam in a globe in order to project a whole globe on to a flat piece of paper.

Once you allow seams, then again patterns based on the de Bruijn torus would work fine -- cut one or more large chunks out of that pattern, and use the chunk(s) as "adapting a flat pattern to a sphere", trimming off overlap; even though the pattern won't "match up properly" at the seams.

• DataGlyphs and the Anoto pattern are just methods to unobtrusively represent your bits, you'd still need something like the de Bruijn torus to determine what bits you actually need :) I don't quite see why the de Bruijn torus wouldn't work though. Rotational invariance might be the bigger problem. – Christian May 10 '15 at 18:11
• @Christian: supposedly there exists a "full pattern (that) encompass an area exceeding 4.6 million km^2". I'm proposing cutting a rectangle out of that pattern and projecting it onto a sphere. Could you explain -- or give a link to -- your claim that "... the Anoto pattern are just methods to unobtrusively represent your bits.." ? – davidcary May 11 '15 at 14:33
• @Christian: GlyphChess uses a "DataGlyph address carpet". I'm proposing cutting a rectangle out of that carpet and projecting it onto a sphere. Could you explain -- or give a link to -- your claim that "... DataGlyphs ... are just methods to unobtrusively represent your bits.." ? – davidcary May 11 '15 at 14:35
• What I meant is what they say themselves: "Basic DataGlyphs/Microglyphs are a pattern of forward and backward slashes representing ones and zeroes." My point just is: it's a two-step process. 1) Find a 2D bitfield that wraps around and gives you the exact location for every submatrix of a minimum size 2) Find a way to display this bitfield optimally on the sphere. – Christian May 11 '15 at 18:11
• @Christian: I still don't understand your point. "a 2D bitfield that ... gives you the exact location for every submatrix of a minimum size" is exactly what the Anoto dot pattern and the DataGlyph address carpet and Jon Howell's absolute position-encoding scheme were designed to do. Could you give me a link to anyone that uses Anoto patterns to "represent bits" rather than fixed absolute locations? – davidcary May 12 '15 at 4:17

This leads into a more mathematical answer, but if you have apriori knowledge of the pattern you're going to put onto the ball, any sufficiently random pattern should work, so long as there are sufficient dissimilarities (both in translation and rotation) between all possible regions you can capture at once.

• but there are probably patterns that require less processing, like the graycode pattern used on an optical encoder shows you absolute position without doing any kind of analysis of it beyond 1s and 0s. – endolith Sep 30 '11 at 20:47

1) I would suggest to draw lots of QR codes at random positions covering >50% of area which have both X & Y coordinates encoded. Then you decode QR code nearest to the center of the image and extrapolate coordinates a little to count for off-center code.

Update: 2) You can probably live with smaller resolution if you can draw on ball in color. Then you light your ball with RGB led - each color separately -> twice smaller QR codes.

3) If ball is not metallic, you can put magnet inside it, and sence direction using couple of Hall sensors.

4) You can just put regular structure there, and track relative position just like optical mouse

I would worry about dirt on the ball.

• That would work, but even under ideal conditions I think this would need at least a 85x85 sensor array to read a minimal (15x15) QR code. I was hoping I could do it with a smaller array (and correspondingly less processing power.) – finnw Jan 13 '11 at 15:36
• you don't need 15x15. for 10 bit coordinates, you need just 20 bits of data + ECC ~10 bit -> 6x6 pixels or so. – BarsMonster Jan 13 '11 at 15:40
• Added few more ideas. – BarsMonster Jan 13 '11 at 17:31
• This makes me think of bokodes.org/bokode.html, where they tile a surface with Data Matrix codes and detect position and angle of the camera – endolith Sep 30 '11 at 20:50
• @BarsMonster: The QR code and Micro QR code are two popular 2D barcode formats. I've been told that the smallest valid QR code is 21x21 modules; and the smallest valid "Micro QR code" is 11x11 modules. Which type of [2D barcode](en.wikipedia.org/wiki/2D barcode) format allows valid barcodes that are smaller than 11x11 modules? – davidcary May 11 '15 at 15:02

Like tyblu said in his comment, use an optical sensor and track distance and direction traveled then calculate your new position based on the distance and direction from the old position. This will be your simplest method to get the information you need.

Image processing like that can be pretty slow and tedious with a fair margin of error and isn't a path I would take for determining position.

• yeah, logitech and kingston already have it figured out! You don't want a mouse, you want to take the pattern used in their trackballs to get X and Y. See the special pattern on the ball: logitech.com/assets/14756/14756.png – Dave Jan 13 '11 at 23:19
• @Dave, that pattern ensures there is always a dot in range of the sensor, but I don't think it is designed to determine the position statically (because otherwise it would not be possible to swap in a ball from another model with different dot density, but you can) but it may be possible to design a similar pattern that does uniquely identify the position, e.g. avoid repetition of the quadrilaterals formed by neighbouring dots. Maybe they already did that (but the sensor does not take advantage of it.) – finnw Jan 14 '11 at 13:01
• @finnw the pattern isn't for determining absolute position, it's used to determine relative position. You would need to keep track of all of the relative changes to get your absolute position. In the end, I think that's "all" you need. :) Now as far as sourcing the sensors and the pattern on the ball goes, I can't comment. – Dave Jan 14 '11 at 13:42
• @Dave, The joint's position is not known when the sensor is first powered on, and it may have been moved while the system was powered off, so I don't think I can use this solution. – finnw Jan 15 '11 at 18:01
• @finnw fair enough -- if you cannot force the user to home the joint upon powerup, then your only solution lies within the realm of absolute encoding / position sensing. – Dave Jan 15 '11 at 21:25