How does one generate recognizable point-patterns on a plane?

Question

I've recently learned that some smartpens (e.g. Livescribe) have a camera in their front part. They film the paper. You have to use special paper which looks as if somebody made a lot of tiny holes with a needle in that paper. Those holes are not in a regular pattern. They are spaced in such a way that the pen can decide - taking only an image of the part of the paper near the pen tip - where on the paper it is.

I can't get this problem out of my head. It's different from what I have seen so far and I am curious how this can be tackled / solved.

Now suppose we have

• ordinary A4 paper (210 mm × 297 mm),
• the camera can see an area $10 \text{mm} \times 10 \text{mm}$
• the dots on the paper are circles with diameter 0.5 mm
• a distance measuring (or printing) precision (of dots) of 0.1 mm

The filmed area $A$ is defined by its center point $(x,y)$. $$A(x,y) = [x-5\text{mm},x+5\text{mm}] \times[y-5\text{mm},y+5\text{mm}]$$ with $x \in [5,205], y \in[5, 292]$.

(How) can the points be spread on the paper so that each $A(x,y)$ is unique?

If it is not possible, how could the four values (paper size, camera area, circle diameter, precision) be adjusted so that it would work?

Brute-Force solution

A brute-force solution would be to add a grid of 0.1 mm spaced lines (because of the precision) on the paper. Then we could generate all possible distributions of points by simply counting up. However, this would require a lot of checking if a given distribution is valid:

• There are $\frac{205\text{mm}-5\text{mm}}{0.1 \text{mm}} \cdot \frac{292\text{mm}-5\text{mm}}{0.1 \text{mm}} = 5,740,000$ possible centers for the pen tip.
• We would have to compare each of those, resulting in $\frac{5,740,000^2 + 5,740,000}{2} = 16,473,802,870,000 \approx 16 \cdot 10^{12}$ comparisons.

That is too much.

Answer 1

Apart from precision issues, all you need is to distribute the dots in such a way that

1. the camera always sees at least two dots
2. the distances between any two dots close enough to be seen simultaneously are all unique.

Answer 2

As mentioned in comment, Livescribe uses a dot pattern technology licensed from a Swedish company Anoto. The dot pattern is most likely the one covered by patent WO/03/038741.

Edward Aboufadel has a paper Position Coding which explains the mathematical ideas behind Anoto's dot pattern.

The construct in this answer uses ideas from Aboufadel's paper. It is not the one used by Livescribe nor the one explictly discussed in Aboufadel's paper.

All mistakes and misunderstandings are mine.

Let $P = \{ 0, 1, 2, \ldots, p - 1 \} \subset \mathbb{N}$ be the set of non-negative integers less than some positive integer $p$. Given any finite sequence

$$A = (a_0, a_1, \ldots, a_{m-1}) \in P^{m}$$

We can extend it to a sequence over $\mathbb{Z}$ by periodicity. i.e

$$P^m \ni A \mapsto A' = (\ldots a'_{-2}, a'_{-1}, a'_{0}, a'_1 a'_2,\ldots) \in P^{\mathbb{Z}} \;\;\text{ s.t. }\;\; a'_k = a_{k\!\pmod m} \;\;\text{ for } k \in \mathbb{Z} $$ If there exists a $n$ such that the $m$ finite subsequences of length $n$ $$ (a'_0, a'_1, \ldots, a'_{n-1}),\, (a'_1, a'_2, \ldots, a'_{n}),\, \ldots,\, (a'_{m-1}, a'_{m}, \ldots, a'_{n+m-2})$$ are all distinct, we will call the sequence $A'$ an $p$-ary pseudo De Bruijn sequence of order $n$ and length $m$. In the special case $m = 2^n$, $A'$ will be called a De Bruijn sequence.

The most important property of these sort of sequences is that if we know the value of $n$ consecutive terms in a sequence, we will know the relative position of those terms modulo $m$.

From now on, let us abuse the notation by dropping the $'$ and use $A = (a_k)$ to represent both the original finite sequence and the generated infinite sequence.

Following are some examples of binary pseudo De Bruijn sequences:

$$\begin{array}{lcl} n = 4, m = 16 &:& A = (a_k) = 0000110101111001\ldots\\ n = 3, m = 8 &:& B = (b_k) = 00010111\ldots\\ n = 3, m = 7 &:& C = (c_k) = 0001011\ldots\\ n = 3, m = 5 &:& D = (d_k) = 00111\ldots\\ n = 3, m = 3 &:& E = (e_k) = 001\ldots \end{array}$$

Notice the sequences $B,C,D,E$ above all have order $n = 3$ and their lengths are relative prime to each other. If we construct a hexadecimal sequence $F = (f_k) \in \{ 0,\ldots, 15\}^{\mathbb{Z}}$ by

$$f_k = 8 b_k + 4 c_k + 2 d_k + e_k\quad\text{ for } k \in \mathbb{Z}$$

the sequence $F$ will be a pseudo De Bruijn sequence of order $3$ and length $\text{lcm}(8,7,5,3) = 840$.

If we are given the values of 3 consecutive $f_k, f_{k+1}, f_{k+2}$, we can recover the values of $k \pmod{840}$ by following procedure:

• breakdown $( f_{k}, f_{k+1}, f_{k+2} )$ into their bits, recover the values of $$ ( b_k, b_{k+1}, b_{k+2} ),\, ( c_k, c_{k+1}, c_{k+2} ),\, ( d_k, d_{k+1}, d_{k+2} ),\,\text{ and } ( e_k, e_{k+1}, e_{k+2} )$$
• Since $B$ is pesudo Bruijn with a relative short length $8$, we can use a table look-up to discover the value of $k \pmod{8}$.
• If we do the same thing to $C$, $D$ and $E$, we will discover the value of $k \pmod{7}$, $k \pmod{5}$ and $k \pmod{3}$ respectively.
• We can then use Chinese remainder theorem to recover the value of $k \pmod{840}$.

Let $\varphi : \mathbb{Z} \to \{0, \ldots, 15\}$ and $X, Y : \mathbb{Z}^2 \to \{ 0, 1 \}$ be the functions defined by

$$\varphi(x) = \sum_{k=0}^{x-1} f_k \pmod{16} \quad\text{ and }\quad \begin{cases} X(x,y) &= a_{y + \varphi(x)}\\ Y(x,y) &= a_{x + \varphi(y)} \end{cases}$$ where $(a_k) = A$ is the first example of De Bruijn sequences above.

For each $(x,y) \in [1,209] \times [1, 296]$, let us place a dot near $(x,y)$ based on the values of $X(x,y)$ and $Y(x,y)$:

$$\begin{array}{|cc:c|} \hline X(x,y) & Y(x,y) & \text{center}\\ \hline 0 & 0 & (x-0.1,y)\\ 0 & 1 & (x+0.1,y)\\ 1 & 0 & (x,y-0.1)\\ 1 & 1 & (x,y+0.1)\\ \hline \end{array}$$

Since the filmed area of the camera has dimension $10\text{mm} \times 10\text{mm}$, it always contains a $9 \times 9$ square of dots. For our current placement of dots, we only need the $4 \times 4$ square of dots near the center of view.

Let's say the camera has decoded the offsets for a $4 \times 4$ square of dots and return us with two $4 \times 4$ array of binary numbers. One for $X$ and another for $Y$. Let us look at the $4 \times 4$ array of binary numbers for $X$:

$$\begin{array}{r|cccc} X & x & x+1 & x+2 &x+2\\ \hline y & g_{00} & g_{10} & g_{20} & g_{30}\\ y+1 & g_{01} & g_{11} & g_{21} & g_{31}\\ y+2 & g_{02} & g_{12} & g_{22} & g_{32}\\ y+3 & g_{03} & g_{13} & g_{23} & g_{33}\\ \end{array}$$

Across any column, say the leftmost column, $$( g_{00}, g_{01}, g_{02}, g_{03}) = (a_{y+\varphi(x)}, a_{y+\varphi(x)+1}, a_{y+\varphi(x)+2}, a_{y+\varphi(x)+3})$$ is a sub-sequence of length $4$ for the De Bruijn sequence $A$ whose order is also $4$. We can look-up the value of $y + \varphi(x) \pmod{16}$ from a table of $16$ entries.

If we do the same thing to other 3 columns, we will obtain the values of $y + \varphi(x) + f_x \pmod{16}$, $y + \varphi(x) + f_x + f_{x+1}\pmod{16}$ and $y + \varphi(x) + f_x + f_{x+1} + f_{x+2} \pmod{16}$ respectively. We can combine these four pieces of information to get the values of $f_x$, $f_{x+1}$ and $f_{x+2}$. By the procedure discussed above, we can deduce the value of $x$.

By a similar procedure, we can deduce the value of $y$ from the $4 \times 4$ array of binary numbers for $Y$.

Since the pseudo De Bruijn sequence $F = (f_k)$ has a length $840$ larger than the dimension of the paper, all the "$4 \times 4$ square of dots" are distinct.