2.1.

Statistical Approach to Estimate $k$

Our earlier approach for the TTI application utilized two main principles, namely (i) that motion vectors are only computed at specific feature points which we denote local extremal points (LEPs) and (ii) that time, rather than displacement, is measured. Based on how long of a time period, a feature point stays within one pixel position we obtained the optical flow data needed for our purpose by taking the inverse of this time interval.

The algorithm is based on the same principle as the previous algorithm, to use the stability of LEPs in the image to compute TTI. However, the previous algorithm required a large number of frames before producing a result. The algorithm, based on statistics, can achieve an answer from just two consecutive frames similar to the case for a traditional optical-flow method.

We will describe the method by starting with the 1D case. We assume that there are $N$ pixels altogether along a line, that the frame rate is high so that consecutive frames are available at approximately the same TTI measurement instance (same $k$) and that the FOE is located at the center of the line. We further index the pixels with $i=\mathrm{0,1},2,\dots ,N/2$ in both directions starting from the FOE. Displacements in the image plane due to the motion is denoted $D(i)$ and is expressed in pixels with reference to the previous frame.

By $f(i)$, we denote the existence of an LEP at location $i$ at the time of measurement, i.e., $f(i)=1$ if there is a LEP, otherwise $f(i)=0$. Likewise, $f^{\prime }(i)$ denotes the existence of a new LEP [meaning that $f(i)=0$ in the previous frame]. The frame rate is assumed to be high enough that all new LEPs are captured. This requires that the maximum displacement $D$ appearing at $i=N/2$ is less than the interpixel distance $D_{N/2}<1$.

However, as we will see later, the method fails gracefully for larger displacements.

Given that an LEP at position i moves at a speed of $D_i$ pixels/frame, this LEP will, on the average, stay at the same pixel location for a duration of $1/D_i$ frames which we denote as the LEP run length. It will then have moved to a neighboring pixel. In our previous method, we measured the run lengths of the LEPs that required to collect many frames, particularly to get correct values for LEPs close to the FOE.

However, as there is a close relationship between the appearance of a new LEP and the ending of a run length, it is possible to estimate $k$ from this relationship in a statistical sense.

Based on the (optical flow) relation $D_i=k·i$ and the fact that a new LEP appears whenever the total displacement reaches the distance of one pixel (after some number of frames), a proportion equal to $D_i$ of the LEPs will generate new LEPs at the next frame. In our 1D setup, there can be up to two LEPs located at the distance $i$ from FOE. However, in 2D, there can be several of them. Alternatively, we can view the proportion as a probability that a new LEP will appear at a neighbor location given a LEP at location $i$. It should be observed that, due to the definition of LEPs, two of them cannot exist at neighboring locations.

The expected number of new LEPs at the next frame can thus be written as

From this, we see that

If the LEPs are sufficiently spread out across the image, which is the case for typical natural images, we can approximate (see Appendix):

This will lead to the following estimate of $k$:

With FOE located at the midpoint of the sensor, it can be shown that constant $\approx 4/N$.

2.2.

Finding Local Extremal Points

LEPs are defined as local maximum or minimum points in the image. In 1D, we compare each pixel with its two neighbors. If the pixel has a higher/lower value than its neighbors, it will be considered a local maximum/minimum. Although susceptible to noise, the LEP normally needs to be visible in at least two successive frames to allow for the computation of its displacement. Our proposed algorithm is statistical and a few erroneous LEPs will not distort the TTI estimation severely. Since the LEPs are based on the relative intensities between neighboring pixels, they can be extracted nicely by cameras that are able to form such information dynamically, for instance, NSIP cameras.^9,10

2.3.

Estimating k and TTI

The basis of the algorithm is thus the following:

The TTI can now be computed as

2.4.

Simulation

We simulate the algorithm using a 1D image of size $N=512$. We zoomed into the image in 150 steps. For the first 15 steps, the zoom factor was 0.1 pixels per frame (for the outermost pixel). For the next 15 steps, the zoom factor was 0.2 and so on. For each step, we compute all LEPs. Plotting the LEP-images for all 150 1D frames results in the image shown in Fig. 1. It is seen that the LEP positions are quite stable in the beginning (top of the image) while they change their positions at the end (bottom of the image).

Fig. 1

Collected LEPs (white pixels) from a sequence of 150 frames. The FOE is located at the center position.

Computing the sums of $f(i)$ and $f^{\prime }(i)$ as a time sequence gives the data shown in Fig. 2. The blue curve corresponds to $f(i)$ and the red curve to $f^{\prime }(i)$.

Fig. 2

Plots of the number of LEPs (blue) and new LEPs (red) as function of frame index.

Defining, for convenience, $R=k·N$ which we denote the “zoom factor,” it is seen that $R$ corresponds to twice the maximum displacement. Applying Eq. (4) and multiplying by $N$, we thus get an estimate of the applied zoom factor. Figure 3 shows, for each frame, the computed value of $R$ (in green) and the corresponding true value in blue. The black dots represent the average of the 15 steps with the same step length. Here we can see that the more data we have (green points) the better approximation of $R(k)$ we get. In Eq. (4), this corresponds to forming an average value of $f^{\prime }(i)$, which gives an average value of $k$ since $f(i)$ is fairly stable, as shown in Fig. 2.

Fig. 3

Plots of estimated zoom factor (green dots) and ground truth (blue line). Black dots correspond to the average of the estimates within each zoom value.

2.5.

Graceful Degradation

From Fig. 3, it is seen that as the zoom factor increases, the algorithm will start to deviate from the correct result. The reason is that the method requires that all displacements are below 1 pixel. However, the problem is not that severe. As is seen in Fig. 4, for zoom factors up to 3 (maximum displacements up to 1.5 pixels), the error will be relatively small. For larger zoom factors, the error will increase sharply. However, it is possible to detect when this is the case. In Fig. 4, the green dots represent sample $R$ values, the black dots represent the average within each group of 15 frames, and the blue line represents the actual zoom factor at each frame.

Fig. 4

Similar to Fig. 3 but for large zoom factors.

It is seen that that the $R$ values are slightly below the correct values when between 2 and 3. Above 3, the $R$ values will level out.

The reason that $R$ levels out is that $f^{\prime }(i)$ will approach $f(i)$, as shown in Fig. 5, limiting the $R$ value. This will be the case when essentially all LEPs are new LEPs.

Fig. 5

Similar to Fig. 2 but for large zoom factors.

The difference between the true zoom factor and the estimated value are plotted against the true zoom factor in Fig. 6. When $>3$, the estimate will be lower than the true value. Since we can estimate $R$, we know when it is out of range. The corresponding impact time is then shorter than the predicted time.

Fig. 6

Difference between true and estimated zoom factor.

2.6.

Dependence on the Number of LEPs

The algorithm is relatively insensitive to the number of LEPs. If we take the same 1D image and perform low-pass filtering before zooming, we get the LEPS shown in Fig. 7.

Fig. 7

LEPs generated from the low-pass filtered image.

The corresponding graphs of the sums of $f(i)$ and $f^{\prime }(i)$ are shown in Fig. 8. When compared with Fig. 2, it is seen that the number of LEPs has been reduced by a factor of 2.5.

Fig. 8

Sums of LEPs (blue) and new LEPs (read) for low-pass filtered image showing reduced number of LEPs.

The $R$ values are noisier. However, the average value is stable as is seen in Fig. 9.

Fig. 9

Estimated values of zoom factor $R$ for low-pass filtered frames.

2.7.

Limitations

If the distance to the object is $d$ and the field of view is $N$, the zoom factor between two frames is given by

The movement toward the camera between two frames differing in time by $\underset{\_}{\mathrm{\Delta }t}$ given the velocity $v$ is

The zoom factor must be smaller than some constant $C$. We have shown previously that $C$ can be around 3:

This means that the velocity $v$ must be smaller than

3.1.

Estimating k

The estimation of $k$ in the 2D case follows the same principle as in the 1D case. The proportion of LEPs that will generate new LEPs in the next frame depends on the distance from the FOE. The displacements in off-angled directions (not along a horizontal or vertical line through the FOE) are larger than their horizontal or vertical components, but so are also the distances that the LEPs need to move before reaching a new pixel and thus generate new LEPs. For this reason, it is necessary to compensate for those larger distances between the pixels. Thus a LEP located at position ($i,j$) with respect to the FOE is subjected to a displacement of

This function is not trivial as it depends on the pixel shape and fill factor of the specific sensor in use. For the moment, we will simply assume the existence of such a function $s(i,j)$. In the following, the 2D image is assumed to have a size of $N\times N$pixels.

The expected number of new LEPs is then given by

Thus

Similar to the 1D case, we will use the approximation

Thus for the 2D case, we have

Using some further approximations (see Appendix), the following result is achieved:

3.2.

Finding Local Extremal Points in 2D

In the 2D case, there are several different ways to define an LEP. The two most common ways are based on the chessboard distance and the city-block distance. In the chessboard case, the pixel is compared to its eight neighboring pixels. In the city-block case, there are four neighboring pixels.

The image shown in Fig. 10 was used as the object. Camera motion toward this object is simulated by zooming in on the image.

Fig. 10

Test image used for 2D TTI simulation.

Figure 11 shows the LEPs in a 2D image based on the chessboard distance. As in the 1D case, an LEP is defined as a pixel which has a higher value than its neighbors.

Fig. 11

2D LEPs computed from the image in Fig. 10.

In the same way as in the 1D case, we define $f^{\prime }(i,j)$ as the new LEPs appearing in a consecutive frame. The image in Fig. 12 shows $f^{\prime }(i,j)$ when zooming into the image in Fig. 10.

Fig. 12

New LEPs appearing between two consecutive frames when zooming into the test image.

3.3.

Estimating k

For the 2D simulation, we generated an image sequence of 15 frames. The first six frames were generated using a zoom factor of 0.2 pixels/row per frame, where each row consists of 512 pixels. The following five frames were generated using a zoom factor of 0.4 pixels/row per frame, and the last four frames were generated using a zoom factor of 0.6 pixels/row per frame. As in the 1D case, the zoom factor corresponds to twice the largest horizontal/vertical displacement in the frames appearing at the four midpoints of the frame borders since the FOE is located at the center of the frames.

Summing up all $f(i,j)$ and $f^{\prime }(i,j)$) as a function of time, we get the graphs shown in Fig. 13.

Fig. 13

Sums of 2D LEPs (line) and new LEPs (dashed line).

If we divide them with each other and apply the constant factor given in Eq. (15), we get the points shown in Fig. 14.

Fig. 14

Estimated zoom factors from the data in Fig. 13.

It is seen that we get three clusters with a scale factor of 1, 2, and 3 between them, which matches well with the true zoom factors.

5.1.

Sensor-Pixel Processor and the NSIP Paradigm

NSIP is based on a tight integration between the photosensitive element and a low-complex digital pixel processor. A/D conversion is not supported in hardware and is typically not used as part of the required signal processing. Instead, the fact that a photodiode discharges linearly in time when exposed to light is combined with a comparator/threshold circuit to turn the light intensity into a corresponding timing event as shown in Fig. 20.

Fig. 20

The photodiode and a comparator turn the incoming light into a binary pulse, the length of which is inversely proportional to the light intensity.

The output from the comparator is fed into a digital processor element. To implement the TTI algorithm, this processor consists of a combinatorial circuit, which connects to the eight neighboring comparator outputs and two one-bit memories. The combinatorial circuit detects asynchronously when its own comparator returns a binary zero, whereas the neighboring comparators are still returning binary ones, thus indicating the occurrence of an LEP. One of the bit memories stores this information. The second bit memory indicates if the LEP is new or existed in the previous exposure.

5.2.

Single-Chip System

Figure 21 outlines the basic layout of a single-chip solution. All photodiodes and PEs on the same row are controlled in parallel thus forming a single instruction multiple data (SIMD) architecture. The comparator outputs as well as the bit memories are forwarded to column buses in a row-by-row fashion. A summation circuit at the bottom part of the chip produces the two sums of LEPs and new LEPS by scanning through the rows while adding and accumulating their results.

Fig. 21

The layout of a one-chip system showing the photodiode and a processing element being repeated at each pixel position.

The size of the chip and the number of transistors is estimated as follows.

Assuming the use of a 100-nm CMOS technology and a sensor size of $256\times 256$, the pixel pitch is estimated to be $14\times 14{\mu \mathrm{m}}^2$ out of which 50% consists of the photodiode. The summation network is purely combinatorial and consists of cascaded one-bit adders. To make it faster, it can be implemented as a two-layer structure (e.g., eight groups of 32 one-bit adders in the first layer and seven 8-bit adders in the second layer). Based on previous implementations of such networks made by one of the authors, its size is estimated to occupy a depth of $50\mu \mathrm{m}$. Depending on the desired output (separate LEP sums, $k$ value, or TTI), a fix-point multiplier/divider unit may be included as well. Since it only needs to compute one value per frame, it can be sequential in nature, e.g., computing a reciprocal iteratively to perform division through the multiplier unit. Altogether, including pads and some decoding circuits, the chip size is estimated to be $<20{\mathrm{mm}}^2$. Naturally, using a more advanced VLSI technology, the size of the chip would shrink accordingly.

The summation network as well as the available light intensity will define the limiting speed in which the circuit can operate. It is estimated that a two-layer summation network requires $<0.5\mu \mathrm{s}$. Since available LEPs as well as new LEPs are summed, each row computation will take $1\mu s$ leading to a frame time $\mathrm{\Delta }t$ of 0.25 ms. According to Eq. (9), this corresponds to the following minimum value of the TTI:

7.1.

Justification of Eq. (3)

Equation (3) reads

Let us assume that $f(i)$ is a binary random vector with probability $q$ that $f(i)=1$ and probability ($1-q$) that $f(i)=0$.

Taking the expectation of the left-hand side gives:

Similarly for the right-hand side:

The approximation is thus exact in the statistical mean sense.

Naturally, this does not guarantee that the approximation is “good” in specific cases. In our case, we use 1D images of size 512 pixels. Table 1 shows the result of 100 outcomes at three different values of the probability $q$ for this vector size. It shows the correct value (rounded over the 100 trials) and four statistical measures for the approximation error.

Table 1 shows the correct value (rounded over the 100 trials) and four statistical measures for the approximation error. It is seen that the error increases when there are few LEPs and can reach more than 10% in such cases.

Table 1

Approximation errors for different q-values.

7.2.

Justification of Eq. (14)

Let us consider the denominator in Eq. (14):

We will break this down into a substantially simpler computation through a series of approximations.

First, as noted in Eq. (13), the two factors within the summation sign are separated:

Second, we will choose $s(i,j)$ to be a constant function, leaving $\sum _{i,j}\sqrt{i^2+j^2}$ to be computed.

For this purpose, we will approximate the discrete sum by a continuous sum:

Setting $\pi R^2=N^2$gives $R=\frac{N}{\sqrt{\pi }}$.

So that

For example, when $N=512$, the above approximation gives 50,482,829, whereas the discrete sum is 51,521,231. Thus the approximation error is $<2\%$.

Next, we set $s(i,j)=\frac{1+\sqrt{2}}{2}$ as a reasonable midpoint value. Thus

Inserting in Eq. (14) gives, $k=\frac{3(1+\sqrt{2})\sqrt{\pi }}{4N}\frac{{\sum }_{i,j}{f}^{\prime }(i,j)}{{\sum }_{i,j}f(i,j)}$

A more detailed analysis shows that $s(i,j)$ is not a constant but grows approximately linearly from 1 to $\surd 2$ for directions between 0 deg and 45 deg. Taking this into consideration when evaluating Eq. (14) would increase the above value of const by about 1.5%.