A Low Cost Matching Motion Estimation Sensor Based on the NIOS II Microprocessor

2.1. Full Search Technique

The Full Search Technique (FST) is the most straightforward Block Matching Method (BMM) and also the most accurate one. FST matches all possible blocks within a search window in the reference frame to find the block with the minimum Summation of Absolute Differences (SAD), defined as:

As seen in Figure 2, one block from the left part of Frame T is matched (using any metric error, such as the SAD) with the corresponding one from the right part of Frame T + 1 inside of the search window. The displacement from frame T to T + 1 constitutes the estimated motion for this block.

2.2. Three Step Search Technique (TSST) and (NSST)

The TSST [25] is the first BMM based on a non-exhaustive search. The TSST supports two important contributions for motion estimation in terms of fixed search patterns and limited search steps. Most of the later works still include these characteristics to design the algorithms.

The aim here is to perform a multi-scale process, applying three steps in order to find the most similar MB within the search window of the reference frame. In the first step, the step size of the search window is designated as half of the search area. Nine candidate points, including the center point and eight checking points on the boundary of the search window, as shown in Figure 3(A), are selected in each step.

The second step moves the search center forward to the matching point with the minimum SAD of the previous step; and the step size of the second step is reduced by half, as shown in Figure 3(B). The third step stops the search process. The step size of one pixel and the optimal MV with the minimum SAD can now be obtained, as shown in Figure 3(C). Using the same search window, ±7 pixels, the TSST only needs 25 search points in comparison with the FST algorithm, which needs 255. As we can see in Table 1 FST uses more search points than TSST and 2DLog, but less search steps than these.

The new Three-Step Search Technique NTSST [27] exploits the fact that the MVs of the frame with slow motion are mostly found near the center of the search window. This technique manages a center biased checking point pattern and a halfway-stop technique for stationary MBs to improve the performance of the TSST. The process first checks the points of the pattern. If the center point contains the minimum SAD, the search is done; but if the minimum SAD appears as one of the neighbors of the center point, the NTSST checks five corners or three edge points; after this, the search is over. Otherwise, the search steps of the NTSST are similar to those of the TSST (Figure 3).

2.3. Two Dimensional Logarithmic Search (2DLOG) and Modifications

An alternative to the techniques previously explained is the Two Dimensional Logarithmic-based Search (2DLOG) [41], which is feasible to implement in hardware. This approach uses a pattern cross search (+) in each step, with an initial step size of d/4. The step size is reduced by half only when the minimum point of the previous step is the center one or the current minimum point reaches the search window boundary. If none of these two conditions is accomplished, the step size remains the same.

As an example, two different search paths are shown in Figure 4. When the step size is reduced to 1, all eight of the checking points adjacent to the center checking point of that step are searched. The bottom search pathway needs 23 = 5 + 3 + 2 + 3 + 2 + 8 checking points through the six steps to complete the process; nevertheless, the top search pathway requires 19 = 5 + 3 + 3 + 8 checking points.

3.1. NIOS II Soft-Core Processor

The NIOS II [48] is a soft-core processor based on RISC architecture. It is targeted for Altera devices, allowing scalable development and flexibility since it can be customized with additional features depending on performance or cost objectives. NIOS II [48] is an enhanced version, which offers higher performance and a lower cost than the previous 16-bit soft-core processor NIOS [49]. This 32-bit processor belongs to a three-member family named Fast, Economy, and Standard, where each one is optimized for a specific price and performance range. Each one of the three cores uses a common 32-bit Instruction Set Architecture (ISA), with 100% binary code compatibility between them.

The NOS II/f Fast CPU is optimized for maximum performance, bringing performance up to a 220 DMIPS in the Stratix II [50] family of FPGAs, which places it squarely in the ARM 9 [51] class of processors. While this core is four times faster than the original NIOS CPU, it is 40% smaller. It has 4 K bytes of separated data and instruction cache, an oscillator of 144 MHz, and 20 embedded multipliers of 9 × 9 bits. Performance in systems based on NIOS II can scale to fit the application by means of custom instructions, high bandwidth switch fabric, and hardware accelerators. It also supports fixed and variable cycle operations. The NIOS II/e Economy CPU is optimized for the lowest cost, achieving a smaller FPGA footprint (less than 600 LEs). It has no data or instruction cache, is half the size of the smallest NIOS core, and increases performance by four times. Finally, the NIOS II/s Standard CPU is a trade-off solution between processing performance and logic element usage. It is 60% faster than the fastest NIOS CPU and smaller than the smallest NIOS CPU. It achieves over 120 DMIPS while consuming only 930 LEs (Stratix II).

3.2. Hardware Acceleration and Algorithms

For the current sensor, the NIOS II C2H Compiler [18] is used, moving specific functions, which are critical for performance, from running on the FPGA soft-core processor (Cyclone II EP2C35F672C6) [52] to optimized and pipelined hardware accelerators. The current accelerators have direct access to the processor's memory, largely improving the parallel transactions to the needed number of buffers.

Usually the processors share a single system bus with DMA channels and other master functions, limiting bus access to only one master. NIOS II systems benefit from the so-called Avalon Switch Fabric [53] that provides, as shown Figure 6 (right), a dedicated data path to each master, allowing all masters to transfer data simultaneously, which delivers greater system performance. This bus supports a plethora of characteristics, such as address decoding, dynamic bus sizing, clock domain crossing, off-chip interfaces, and datapath multiplexing. Large blocks of data can be processed concurrently with CPU operation constructing application-specific hardware accelerators, boosting the system throughput due to dedicated datapaths. The performance of the embedded system not only depends on the frequency or benchmarks but also on the surrounding system.

Figure 6 (up) shows how the NIOS II C2H Compiler integrates into the software build process in the IDE. The left half of the flowchart shows the standard C compilation of main.c and accelerator.c, as it occurs without acceleration. The right-hand side of the flowchart shows the hardware compilation process invoked when a function in accelerator.c is accelerated. It also shows the generation and selective linking of the accelerator driver into the executable file.

Altera claims that no restrictions on the bandwidth are imposed inside/outside of the accelerator different from the physical limitations of the connected memories. When the NIOS II C2H Compiler creates hardware for a function, it generates sufficient master ports for pointer and array operations. These master ports allow access to memory and other peripherals in the system and are able to operate independently, in parallel. It is also possible to write data to output buffer and fetch data from input buffers in parallel over the same clock cycle.

Next, the functionality of the algorithms implemented in the sensor is briefly described and shown (Figures 7 and 8). The three first Algorithms (I, II, III) correspond to the techniques represented in Figures 2 through 4. Additionally, Algorithm IV moves data in memory; Algorithm V gets a specific MacroBlock (MB); and, finally, Algorithm VI delivers the accuracy of the motion estimation in the sensor itself:

• Algorithm I. Full Search Technique (FST). This function looks into the current frame for each block situated in (x, y) in the reference frame. All the possibilities are tested, returning the motion of the block in the current frame as explained in Section 2.1 and Figure 2.

• Algorithm II. Three Steps Search Technique (TSST). This function performs three steps through a limited search step and using a fixed search pattern as explained in Section 2.2 and Figure 3.

• Algorithm III. 2D Log Technique (2DLOG). This function performs three steps between 2 and 8 times executing a logarithmic search using a fixed search pattern as explained in Section 2.3 and Figure 4.

• Algorithm IV. Copy_do_DMA. This is a simple function that copies “length” bytes from the “source” memory direction to the “destiny” memory direction. It manages memory transfers.

• Algorithm V. Get_Block function. This function results in a copy block, pointed by “block”, of the parameter “frame”, receiving as parameters the block size, the width, and the position of the block into the frame (x, y).

• Algorithm VI. Get_Cost function. This function returns the cost between the current block and the reference block calculated according to a SAD metric, as shown in Equation (1).

4.1. Throughput Obtained

The throughput of the sensor is represented as a function of the kilopixels per second (kpps) delivered with the system. Every technique is implemented using a range of window searches of 8, 16, and 32 pixels, as well as the three different architectures of the NIOS II microprocessor (Economic, Standard, and Fast), as mentioned in Section 3.

We first considered in this preliminary analysis the behavior of the system from no code accelerated, algorithm IV, and algorithm IV+V; thus, in other words—no, low, and medium configurations for each one of the three matching techniques considered (FST, TSST, 2DLOG).

The throughput of the whole system with low or medium acceleration behaves similarly when comparing the execution of the whole functions in embedded software (no acceleration) under the NIOS II and the FST technique, as shown in Figure 9. If we focus on the TSST technique, this behavior becomes lineal (when considering no, low, and medium acceleration). If we see the 2DLOG technique, the linear response is emphasized again for no, low, and medium acceleration, as well as the fast architecture (NIOS II /f). Although every throughput for every architecture depends on the window size (8, 16, and 32 pixels, respectively), the linear tendency of all responses remains constant for all sizes. We notice, for instance, that by using only medium acceleration (Algorithms IV and V), the 2DLOG technique and fast architecture (NIOS II /f) is obtained as throughput range between 16 and 21 Frames per second (Fps) at a 50 × 50 pixel resolution when using different windows sizes.

Focusing on high acceleration (Algorithms I or II or III and IV, V, VI together), we can appreciate a different throughput regarding the windows size: Regarding FST (in the first column of Figure 9) and fast architecture, a range from 61 to 72 kpps is delivered, depending on the window size used (from 8 to 32 pixels). This is a throughput for the system between 24.5 and 29 fps at a 50 × 50 pixel resolution, enough for a small sensor camera. For configurations of standard and economic architecture, we obtain a throughput range between 20 and 27 kpps (from 8 to 32 pixels), which is a range between 8 and 11 fps at 50 × 50 pixel resolution.

Focusing on TSST (in the second column of Figure 9) and regarding fast architecture, a range from 6.15 to 24.6 kpps is delivered, depending of the window size used (from 8 to 32 pixels). This means a throughput for the system between 2 and 10 fps at a 50 × 50 pixel resolution. For configurations of standard and economic architecture, we obtain a throughput range between 5 and 20 kpps (from 8 to 32 pixels) which means a range between 2 and 8 fps at a 50 × 50 pixel resolution.

The 2DLOG technique (in the third column of Figure 9) processes a range from 43.8 to 56.4 kpps for fast architecture, again depending on the window size used (from 8 to 32 pixels), which means a range of 17.5–22.5 fps. For configurations of standard and economic architecture, we obtain a throughput of approximately 10 kpps and 8 kpps, independent of the window range (from 8 to 32 pixels), which means a range between 2 and 8 fps at a 50 × 50 pixel resolution.

Note that the size of the window is not always inversely proportional to the system throughput. For example, the TSST restricts the calculation complexity by limiting the exhaustive search to three steps, so accelerating all functions means a trade-off solution between pixel parallel level (the increment of the window size involves less Macro Blocks) and Macro Block parallel level (when window size is decreased).

4.2. Used Resources

The hardware resources used are listed in Table 2 (Full acceleration) and Table 3 (no acceleration, low acceleration, and medium acceleration) for different processor architectures, a window size of 32 pixels, and a set of different architectures.

Recall the cache resources regarding the microprocessor: no cache (economic), only data cache (standard), and both data and instruction cache (fast). The tables show the number of Logic Cells (LCs) used, the number of embedded multipliers (9 × 9) needed, and the total number of bits.

High quality acceleration (all functions) requires a little bit less than 50% of the available logic cells (35%–39% for FST, 40%–44% for TSST and 39%–44% for 2DLOG). In this case, between 33% and 39% of embedded DSPs (9 × 9) are used and total memory Bits (Block Rams) are from 9% to 24%, depending on the motion estimation technique considered.

Regarding low, medium, and no accelerations, note that the same resources are required for the three techniques, although it depends on the processor configuration selected. Focusing on medium quality, we obtain an increment from 15% to 20% of Logic Cells for NIOS II economic to NIOS II fast. Regarding the multipliers, this increment is from 17% to 23% for NIOS II economic to NIOS II fast. Finally, regarding the total memory bits, the increment covers from 9% to 24% for NIOS II economic to NIOS II fast.

Focusing on low quality, the resources used are 10%–15% (Logic Cells), 0%–6% (Multipliers), and 9%–24% (Total Memory bits). Regarding the no-acceleration, we obtain an increment 6%–11% (Logic Cells), 0%–6% (Multipliers), and 9%–24% (Total Memory bits). These two increments are the same as the low quality; in other words, constant DSPs and Block Ram from the previous configuration is maintained.

4.3. Resources vs. Performance

In order to compare used resources and performance, we show the kilopixels per second (kpps) achieved versus the logic elements implied and the embedded multipliers implied for each design in Figures 10 and 11.

We can appreciate how every window search has been distinguished and every processor type discussed on the previous point. For every graph and for every processor kind, we have measured four points, which belong to every kind of acceleration tested on this approach.

As we can observe, for NIOS II/e and NIOS II/s processors, FST algorithm achieves less kpps with the same logic elements than with TSST and 2DLOG in all acceleration types, except in the case of high acceleration in which FST achieves better performance than any other using less logic elements.

Regarding the sensor design, when the NIOS II/f processor is used, we can see 2DLOG gets the best performance and the TSST achieves better performance than the FST in all acceleration types, except on high acceleration. In this last case, FST obtains the best results using less logic elements, followed by 2DLOG and, finally, by TSST.

Using the NIOS II/e processor, no acceleration and low acceleration on a desired design achieves the same results, spending no embedded multipliers. When chosen acceleration is high, all algorithms use the same quantity of embedded multipliers, although FST achieves the best performance.

When NIOS II/s is selected, the FST gets the worst results whether or not the design is no accelerated or accelerated in low mode; but when accelerating in high mode, the FST gets the best results using the same resources. Using this processor, the TSST gets better results than the 2DLOG in all cases except on high acceleration with a window size of 32. As the window size increases, the more the TSST decreases its difference against 2DLOG.

As we can observe, the FST and 2DLOG are the best designs using NIOS II/f, but 2DLOG gets better results using no acceleration or low acceleration, and FST achieves better results using the high acceleration mode. The TSST only can be compared with the FST in either no acceleration or low acceleration modes, where they gets the same results, due to 2DLOG achieving better results than TSST in all cases.

4.4. Block Matching Accuracy (PSNR)

In order to measure the accuracy of the sensor, we use the Mean Squared Error (MSE), similar to Equation (1) but using the absolute value of the squared subtractions, becoming less conservative metrically, which emphasize the larger differences:

Next, we can define the Peak-Signal-to-Noise-Ratio (PSNR) as shown in Equation (3), where Max_value refers to the peak-to-peak value of the original data, which depends on the frame-grabber or the camera datasheet used. In this case, the Max_value corresponds with an 8-bit range, so an intensity value of 256. This value characterizes the motion compensated image created by using motion vectors and macro clocks from the reference frame:

The value of the PSNR for three different sequences as Caltrain, Garden, and Football deeply used for testing motion estimation sequences [54] with a resolution of 352 × 240 pixels (4:2:0 and SIF format) as shown in Figure 12. As is evident, the accuracy of the implemented FST configuration remains the highest for the three cases. The TSST and 2DLOG configurations alternate in terms of accuracy, the difference between the three implementations lower than 2 dB.

4.4. Visual Results and Other Sensor Approaches

Next, we briefly show some visual results delivered by the platform. We can see an example of two frames from the Caltrain sequence [54] corresponding to 352 × 288 pixels (CIF format), as shown in Figure 13. The yellow arrows show the motion estimation superposed within the reference frame. If we just apply the motion compensation, it is trivial to subtract the motion vectors from the current frame and transmit only the motion difference, emulating the MPEG/H.26x compression process flow as indicated in Section 1.

In the framework of real-time computing sensors, there are other platforms (commented upon in the introduction), where family, chips used, and performance results have been represented in Table 4.

Regarding the two most frequently and hardware-implemented family methods for recovering motion estimation: On one hand, we have the differential or gradient methods derived from work using the image intensity in space and time. The speed is obtained as a ratio from the above measures [8,9,16]. On other hand, we have correlation-based methods, frequently used in this contribution. The methods work by comparing positions from the image structure between adjacent frames and inferring the speed of the change in each location, probably the most intuitive methods [28–30].

Regarding the chip used, the many approaches include: (1) Full Custom VLSI, as a methodology for designing integrated circuits by specifying the layout of each individual transistor and the interconnections between them [42]; (2) Altera Cyclone and Cyclone II as 130-nm and 90-nm FPGAs to provide a customer-defined feature set for high-volume, cost-sensitive applications [52]; and (3) XC2V6000—a 150-nm FPGA [57] and NIOS II [18], further commented upon in Section 3.

4.5. Performance Conclusions

Comparing used resources and obtained performance, we can extract some conclusions from our approach and guide the designer through different ways for achieving his preferred goal. The designer will be able to choose one option depending on his priorities--powerful designs, low cost designs, or efficient designs.

-

Powerful design: NIOS II/f processor running an FST algorithm accelerating at a high level using window sizes 8 or 32, which achieves the best performance.

-

Efficient design: NIOS II/f processor running a 2DLOG algorithm accelerating at a medium level using a size 8 window, which achieves good performance without significant hardware cost.

-

Low Cost design: NIOS II/e processor running an FST, TSST, or 2DLOG without accelerating the design and using any window size, because any of these use the least possible resources.