2.1.

Stereo Matching

Based on the requirements of the hardware design, the fusion strategy algorithms adopted in the implementation should have mutually reinforcing features and have the potential of parallel processing. SAD and CT belong to local (area-based) algorithm methods. Table 1 illustrates a comparison of CT and SAD with different characteristics. The CT approach has advantages in being bias-independent and having a homogenous area and low hardware complexity, while SAD has an advantage in feature-rich areas, especially in texture repeated regions. They are strongly complementary to each other and, hence, have huge potential for fusion in matching efficiency.

Table 1

Comparison of census transform and sum of absolute difference (SAD).

The initial matching cost calculation includes two parts, respectively, the Hamming distance obtained from the census transformed image and the SAD value based on the original image. The hybrid matching costs¹⁰ can be expressed by Eq. (1):

CT is a nonparametric local transform proposed by Woodfill^24,18 in the early ’90s of the 20th century. Compared to a conventional algorithm, it can avoid noise between image pairs introduced by different cameras and simplify the hardware design with an integral calculation. In particular, the matching performance is high in the structural feature highlighted regions, e.g., areas near object boundaries. One CT value of a current pixel is the bits array, which summarizes the local image structure in a specified window. The CT value of left/right view $I^{\prime }$ is equal to ${\otimes }_{n\in N}{\otimes }_{m\in M}\xi [p(u,v),p(u+n,v+m)]$, where the operator $\otimes$ denotes a bitwise catenation, $M\times N$ is the mesh window size, and $\xi (p_1,p_2)$ is 1 when the pixel original value $p_1$ is bigger than $p_2$, otherwise it is 0. $(u,v)$ are the coordinate values of the corresponding pixel. If $k$ is the number of the bit of each CT value, $k$ is equal to $w\times w-1\text{bit}$ as the window size is $w\times w$. Figures 1(a) and 1(b) show an example of CT where the mesh window is $3\times 3$. The Teddy image and its CT image are shown in Figs. 1(c) and 1(d).

Fig. 1

Census transform example: (a) $3\times 3$ census mask window, (b) census transform result of center pixel, (c) Teddy, (d) census transform results of Teddy.

Different window sizes result in transform values with different lengths, which impacts the matching results. Meanwhile, the computation complexity increases with the increasing window size. Figures 2(a) and 2(b), respectively, show the correct percentages of disparity estimation and the time consumption based on a double core 2.67 GHz PC with different window sizes from $7\times 7$ to $37\times 37$. They shows that with an increasing transform window, the accurate rate of the depth map does not increase linearly, while the computation obviously increases. Therefore, a tradeoff is needed between the window size and computation complexity in the hardware design.

Fig. 2

Matching quality and time consumption for different census mask sizes.

After running CT, the Hamming distance, $\text{Hamming}[{I^{\prime }}_1(u,v),{I^{\prime }}_2(u+d,v)]$, is used as one part of the initial matching cost. ${I^{\prime }}_1$ and ${I^{\prime }}_2$ are CT values. The value of the Hamming distance is the sum of the bitwise exclusive OR of a pixel pair.

Another famous local matching method is SAD.²⁵ Its cost function $C_{\text{SAD}}$ is the absolute difference of the pixels’ intensity values,

$I_1$ is the intensity value of the primary stereo image. $I_2$ is the intensity value of the secondary stereo image at disparity level $d$. The coordinates are ($u+i$, $v+j$).

In the fusion steps, different combinations of the two matching methods can be used. The normalization method and other methods are used to control the proper weight of the basic matching costs. Following efficient combination, matching costs are provided for the disparity optimization processing.

2.2.

Multiscale Processing

High-resolution image processing is one of the trends in 3-D video²⁶ and it is necessary to provide a high-quality image in an autostereoscopic display. In contrast to natural video signals, depth maps are characterized by piecewise smooth regions bounded by sharp edges. A smooth interior surface is a benefit for a multiscale operation. We find that the depth map can obtain a higher quality in an interpolation process compared to a normal texture image. Figure 3 shows the interpolation quality difference between the depth map and the texture image with different interpolation methods. The interpolation methods of 1 to 7 represent, respectively, nearest, bilinear, bicubic, box, lanczos2, lanczos3, and spline interpolation.²⁷ This shows that no matter what interpolation is used, the depth map has a better performance than the texture image. Since joint bilateral filtering²⁷ upsampling not only requires using the low-resolution image data but also needs an additional guidance image for separately calculating the spatial filter kernel and the range filter kernel, it will result in additional storage consumption and high complexity. Therefore, the joint bilateral filter will not be used for upsampling in this paper. The method that can be used in this design depends not only on the quality of the results, but also on the implementation complexity. Nearest interpolation is adopted in this design and synthesizers are used in the hardware design to avoid meat-stability problems since the multiclock domains are involved in different resolution operations.

Fig. 3

Interpolation performance for depth map and texture image.

In addition to the above-mentioned image matching algorithm and multiscale operation, refining processes are also used to enhance the performance of the depth estimation. The improved cross-based regions are processed for efficient cost aggregation. Support regions based on cross-skeletons allow fast aggregation with middle-ranking disparity results. As an optimizer, winner-takes-all (WTA) is used for the initial disparity map. A refining process to correct various disparity errors is used for improving the disparity results. The left-right consistency check occludes the points where the two disparity maps are not negatives of each other.⁸ Subpixel disparity⁸ is another postprocessing method, which can use a parabolic fitting to generate the disparity in the subpixel accuracy. Filtering can be used as a fitting to achieve subpixel-level image filtering. These are used to resolve problems such as misleading occlusions and not being aligned with objects and outliers.

3.1.

Matching Core Implementation

The matching core is the key architecture of the proposed hardware fusion algorithm implementation, which adopts a parallel design to increase the throughput. Calculation of the value of the CT for each pixel is to compare the center pixel with pixels around it in the transform window. To meet this design requirement, it is necessary to set the line buffers with memory depth equal to the window height and the word width of the buffer equal to 8 bits. Meanwhile, the progress should be finished in one pixel clock to ensure real-time processing. The Altera intellectual property (IP) core of a dual-port RAM was used to realize the line buffers for the windows operation. The size of every line buffer is determined by the size of the input image. As shown in Fig. 5, a RAM with read and write ports composes the line buffers for further implementation. The number of line buffers is determined by the window height $h$ and the width of line buffer is determined by the image horizontal resolution. In the experiments, the full HD images ($1920\times 1080\text{pixels}$) were progressed, so nine line buffers are used for $9\times 9$ windows and the minimum memory depth of each line buffer is 1920 words, where the word width is 8 bits. The outputs of each line buffer are merged together by using register arrays to form the data for the windows operation, as shown in Fig. 6. The diagram gives an example of a $5\times 5$ window operation, which is composed of $w\times h$ cascade registers. The CT diagram in Fig. 6 is used to get the CT value of one pixel in serial. One CT value is 80 bits for a $9\times 9$ window and is saved in the memory unit with an 80-bit word width. Figure 7 shows the processing architecture of the CT, which consists of comparators and outputs bit arrays with $m=w\times h-1\text{bits}$. As the output of this submodule, the original image data and CT value will be fed to next stage.

Fig. 5

Line buffers for $w\times h$ window operation.

Fig. 6

Register arrays for window operation.

Fig. 7

Block diagram of census transform.

The initial matching cost value of each pixel is calculated by mixing the Hamming distance of the CT value and the SAD value determined by the original intensity value. In the matching processing, the current pixel and all pixels included in the disparity range in the reference image take part in the matching cost calculation, which generates $Ln=d\max -d\min +1$ matching cost values for each pixel. To ensure real-time processing, the output of all the Ln matching costs of the current pixel should be completed simultaneously. Parallel processing of the costs for each pixel is achieved through cascade register units. Hardware architecture of the Hamming distance module and the SAD consists of adder and comparator logic. Figure 8 shows the cost fusion calculation architecture. The parameters were utilized in fusing the CT and SAD costs. Figure 9 shows the logic design of the Hamming distance, which uses a fine grain pipeline method. The example shows the comparison of two 16-bit CT values by three-level pipeline structures.

Fig. 8

Census transform and sum of absolute difference calculation for the initial matching cost.

Fig. 9

Logic design of Hamming distance.

To further improve the matching accuracy, the cost aggregation in the specified window is carried out in each of the disparity plans. In order to keep a good trade-off between the quality and processing time, a $5\times 5$ squared window aggregation is used. The windows operation in aggregation processing is the same as the method in CT, which uses the line buffers and register arrays. The five-stage pipeline is adopted. The first stage outputs are 10 bits, and the second stage result is 11 bits, so a 14-bit result is output in the final stage. The cost results are used to get the disparity using optimization processing.

3.2.

Multiclock Domain Design

The design has to include several different clock domains because the FPGA chip and peripheral devices have different operating frequencies; another reason is the multiscale operation which has been used to improve the processing efficiency of the high-resolution video. When data are transferred from one clock domain to another, the received data risk including errors because of the existence of metastability. So the synchronizer is necessary for stable data communication. Based on the metastability characteristics of a synchronizing flip-flop, synchronizer reliability is typically expressed in terms of the mean time between failures (MTBF).²⁸ It can be calculated by $\mathrm{MTBF}=(e^{T_{\mathrm{r}}/\tau }/T_0{f}_{\mathrm{s}}{f}_{\mathrm{d}})$, where $\tau$ is the settling time of the flop, $T_W$ is a parameter related to its time window of susceptibility, $f_{\mathrm{s}}$ is the synchronizer’s clock frequency, and $f_{\mathrm{d}}$ is the frequency of pushing data across the clock domain boundary. In the proposed design, synchronizers are used in the multiscale operation and DDR2 memory management to improve the system stability. Besides the synchronizer above, asynchronous FIFO is suitable for data bus synchronization. It is a typical structure for asynchronous FIFO.²⁹ In the application of DDR2 write management of the HDDE system, a data buffer consists of the FIFO memory unit and the FIFO control module which generates the control signals.

3.3.

Memory Organization

High-resolution processing and complex algorithm processing need mass memory. So memory management and organization are important parts of an HDDE system. The external DDR2 memory is arranged for the frame buffer, and BRAM is used for the slice storage. In order to realize the communication between FPGA internal data and DDR, a data input/output buffer module is set up to resolve the CDC problem. As shown in Fig. 10, write control in the internal clock domain, memory buffer, and read control in DDR2 clock domain compose the DDR2 data input buffer. In addition, the data bit width has been adjusted to make efficient use of the DDR2 data transfer ability. The data that were read under read control were transferred to DDR2 through a direct memory access module. The DDR access flow is shown in Fig. 11. As mentioned above, there are similar modules that are responsible for inverse data access.

Fig. 10

Data input buffer module scheme.

Fig. 11

Double data rate 2 memory access flow.

3.4.

Other Submodules

Other submodules, such as the input signal transform, WTA, postprocessing, or visual quantification module, are implemented using logic gates and logic units, such as comparators, counters, multiplexers, and finite-state machines. Figure 12 shows the architecture of the basic unit of a WTA module, which includes a comparator and multiplexer. Figure 13 shows the design of the median filter which can reduce the random noise introduced in the disparity map assignment stage.

Fig. 12

Logic unit of winner-takes-all.

Fig. 13

Circuit scheme of median filter.

An Optional modules are the module of disparity converted to depth and depth quantization. If the camera pair is fixed, the camera intrinsic and external parameters are constant and the depth in the real world is in fixed inverse proportion to the disparity. The processing of depth quantization can be expressed as $I_{\mathrm{d}}(z)=\text{round}\{255[(1/z)-(1/z_{\max })]/[(1/z_{\min })-(1/z_{\max })]\}$. Depth representation has two major advantages. First, because depth is the distance between the object and the camera, it avoids the disparity dependence on camera parameters, which is favorable for free viewpoint rendering based on a depth map. On the other hand, the converted quantization results in that object close to the camera has a fine resolution and an object far from the camera has a coarse resolution, which satisfies the human vision character. Since directly using the formula to design modules is a high resource consumption, a look-up table is used to realize the conversion processing.

4.1.

Hardware Implementation Result

The HDDE system has been implemented using Verilog, simulated using Mentor Graphics ModelSim 6.6 and executed using Quartus II tool. Except for the design, a core module has been developed to allow an easy migration to other FPGA or ASIC technologies. The resource consumptions of the core module and HDDE system implementation are shown in Table 2. The internal storage consumption mainly comes from the CT and the matching cost aggregation, as well as the filter window operations which need to setup line buffers for parallel calculation. So the storage unit will increase with the increasing resolution and the processing window size. Taking into account the quality assurance and resource consumption, we can determine the appropriate size of the window, e.g., between $9\times 9$ and $17\times 17$ can be chosen for CT. Compared to the core module, the logic unit and the BRAM of the HDDE system are slightly increased because of the additional external communication interface IP resource. The phase locked loops (PLLs) are used for setting multiple clock domains.

Table 2

Specifications of target device for core module and high definition depth estimation (HDDE) system implementation on EP2AGX260EF29C4 of Arria II GX.

4.2.

Depth Map Analysis

In order to evaluate the effect of the depth estimation results, depth maps of real scenes collected directly from the implementation system are used for evaluation. Figure 15(a) is captured in the laboratory environment, Fig. 15(b) is the corresponding depth map, and Fig. 15(c) is the false-color rendered image of the depth map. To help optical viewing, the distance coordinate in the real world is also shown in the figure. As can be seen, there is high accuracy in texture-rich regions which are fit for real scene reconstruction. This exhibits the characteristics that not only the regions with repeating texture but also the area of objects’ edges are all concerned and also the reliability of the algorithm implementation is illustrated.

Fig. 15

Results captured in the implemented video system. (a) Left input image of a real-scene scenario. (b) Depth map. (c) False-color result rendered for optical viewing, including the color bar.

We use data sets of Middlebury for our algorithm performance measurement; the images Venus, Teddy, and Tsukuba are measured. Figure 16 shows the results and the last line is the disparity image obtained by the proposed method, which also includes the postprocessing mentioned above. Disparity maps have high accuracy in high texture regions, which is the advantage of the SAD algorithm. Good edge information illustrates the characteristics of the CT method.

Fig. 16

Matching results. (a) Original Middlebury stereo data set. (b) Ground truth. (c) Matching results.

4.3.

Further Analysis of the Performance

A hardware-based design, especially a semiconductor design, can achieve low power costs in the application system. The power consumption is a critical matter of concern in hardware design, especially under the equipment miniaturization trend. Altera PowerPlay Power Analyzer is used to make a power consumption analysis of our HDDE system. Table 3 shows the results of power consumption. Compared to the typical power of an Intel Core I7 processor, the working condition is $\sim 338\mathrm{W}$³⁰ and the execution HDDE system power consumption is $\sim 3.2\mathrm{W}$. The power consumption of the core module is only 801 mW. Reducing the resource usage rate of FPGA or reducing the operation clock frequency can further reduce the power consumption.

Table 3

Field-programmable gate array (FPGA) device power dissipation characteristics.

One single aspect, e.g., image resolution, is not sufficient to measure the performance of the hardware implementation of depth estimation. The performance of the system can be illustrated by its data processing capabilities. Therefore, this paper uses megapixels per second and mega disparity evaluation per second (MdeS) as the assessment criteria. MdeS can be described as $\mathrm{MdeS}=\text{width}*\text{height}*\mathrm{disps}*\mathrm{fps}/\mathrm{1,000,000}$. It is more meaningful in line with the overall performance of the system. Table 4 compares the existing approaches with the hardware implementations mentioned in this paper. It can be seen that the maximum frame rate in Refs. 8 and 30 is high, but in the 3-D TV, real-time 3-D video applications only need $>30\mathrm{fps}$ for National Television Standards Committee (NTSC) and 25 fps for Phase Alternating Line (PAL). Considering only the pixel throughput, they would be adequate for 1080 pixels with 34 and 65 fps because their resolution is VGA. The proposed implementation can compete with other hardware architectures in terms of full HD depth maps in real time and can dramatically boosts the overall performance.

Table 4

Disparity estimation performance comparisons.