3.1.

Local Binary Descriptors

In general, binary descriptors have been used for tasks like texture analysis, recognition, and matching, e.g., LBP^13,18 and the CT.¹² In the context of local descriptors, several fast binary descriptors were also developed recently, e.g., BRIEF,¹⁰ BRISK,¹⁴ FREAK,¹⁵ etc. In our experiments, we considered the center-based descriptors CENSUS and LBP, where center-based refers to the fact that pairwise comparison always involves the central pixel, and the uncentered descriptors BRIEF and STABLE. The main difference in binary descriptors is in the sampling pattern for local intensity comparisons, which results in a binary descriptor vector. The CENSUS-dense descriptor is the only descriptor utilizing exactly all pixels in the considered matching window. We alternatively investigate the CENSUS-sparse descriptor, which uses a subsample of off-center pixels on a regular grid and compares those against the central pixel. The BRIEF descriptor uses a subsample of pixel pairs (typically sparsely) located at arbitrary positions in the matching window. The resulting descriptor lengths equal the number of pixel pair comparisons performed. Finally, with STABLE, we also get pixel pairs at random positions, but we are able to map a larger number of pixel pairs to a smaller number of descriptor bits. Figure 5 shows the compared descriptor masks (the meaning of the numbers in the mask will be explained in the next section).

3.2.

STABLE Descriptor

We consider an image patch $\mathbf{p}$ of size $X\times Y$ pixels. The operation $\beta$ derives the $i$th descriptor bit $d_i\in \mathbf{d}$ from patch $\mathbf{p}$ as follows:

Figure 3 shows this operation schematically. A set of sparse filter masks from a dictionary are applied to the same image patch and, depending on the number and individual signs of the filter mask entries, a number of pixels is contributing to each descriptor bit.

Fig. 3

Operation of the STABLE descriptor: sparse filters from a dictionary where each filter mask mostly consists of entries of 0, other entries {$-\mathrm{1,1}$} are randomly distributed. An image patch is convolved with each filter mask, and the result is thresholded (binarized convolution) and inserted into descriptor bits.

A more efficient implementation of STABLE, avoiding binarized convolutions with $K$ sparse feature filters, uses a single index filter mask $\mathbf{g}$. This mask $\mathbf{g}$ is of the same size as the image patch $\mathbf{p}$ and encodes at nonzero pixel positions the position in the descriptor array $\mathbf{d}$ and a sign. An accumulator array $a$ of size $K$ is used to perform a sign-dependent accumulation in cell $i$ of the pixel values in $\mathbf{p}$ with corresponding filter mask index $|i|,i=1,\dots ,K$. After all accumulators cells are processed, the descriptor $\mathbf{d}$ is derived by thresholding each cell entry of $a$. The improved operation involving the filter index mask $\mathbf{g}$ instead of the filter dictionary $\mathbf{d}$ is shown in Fig. 4.

Fig. 4

Efficient implementation of the STABLE descriptor: an index filter mask contains pixel indices and signs. An image patch is accessed using this mask, and a signed sum is inserted into an accumulator array. The descriptor is finally obtained by binarization of the accumulator entries.

The concept of filter masks is also applicable to other binary descriptors, e.g., Fig. 5 shows filter masks corresponding to CENSUS-dense, CENSUS-sparse, LBP, BRIEF, and STABLE. The number in each cell refers to which bit a pixels contributes. The sign indicates whether the pixel value is taken as is ($+1$) or if it is negated ($-1$) when using the accumulator-based implementation scheme. The center-based descriptors in Figs. 5(a) to 5(c) utilize the central pixel for each descriptor bit, which is indicated by $-*$.

Fig. 5

Examples of index filter masks of different binary feature descriptors defined on the $7\times 7\text{pixel}$ matching window: (a) CENSUS-dense, (b) CENSUS-sparse, (c) LBP, (d) BRIEF, (e) STABLE.

3.3.

Stereo Matching

In stereo matching, we consider a discrete range of disparities [$r_1,\dots ,r_P$] for which the descriptors, corresponding to each image pixel position, are compared by the Hamming distance. This results in a cost stack $C$ of dimension $M\times N\times P$, where $M$ and $N$ are the image dimensions and $P$ is the number of evaluated disparities. The cost stack $C$ is searched for by the minimum cost at each pixel, which provides the associated disparity estimation. The cost stack $C$ is then filtered with a $1\times 3$ Gaussian kernel in the cost domain followed by filtering with a $3\times 3$ Gaussian kernel in the image domain. Finally, to efficiently obtain a subpixel accuracy disparity map, a parabola is fitted to three values around the initial integer disparity estimation, a procedure commonly applied in image processing.¹⁹

4.1.

Synthetic Data

To evaluate performance of the STABLE descriptor compared with other state-of-the-art local binary descriptors, we employed a similar evaluation scheme as suggested by Mikolajczyk and Schmid²⁰ based on the analysis of receiver operator characteristic (ROC) curves. We extracted 1200 grayscale patterns from 48 natural images contained in the data set introduced in Ref. 20, always 25 patterns per image at random locations. Given the perturbation type, for each pattern, we introduced 25 synthetic perturbations, which gave a total number of 30,000 patches. In this study, we considered five different types of perturbations:

We considered matching windows of size $15\times 15\text{pixels}$.

Given the set of 30,000 patches defined for each perturbation type, there is always a group of 25 associated perturbed versions for each patch in the data set. Making every patch a query, one can assess its Hamming distance to all patches in the data set making use of a particular feature descriptor. Knowing that for each query there are only 25 relevant elements, one can calculate the precision and recall values for all result sets associated with different thresholds put on the Hamming distance. The ROC curve is then defined by the obtained precision and recall values.

In total, we compared five local binary descriptors:

While for CENSUS and LBP, the descriptor size depends on the matching window, in the case of STABLE and BRIEF, the number of feature bits is defined independently from the matching window. Thus, we also looked into the relationship between matching performance, expressed in terms of the area under the ROC curve (AUC), and the descriptor size in bits. Furthermore, as both of these descriptors are generated stochastically, their performance was assessed as the average and standard deviation over 25 trials with different randomly generated filter masks. We believe this should provide a clear picture about the typical performance and stability of those stochastic descriptors.

Figure 6 shows the recognition performance obtained by different feature descriptors for a constant configuration of the descriptor size. Going from the worst to the best performing descriptors, it can be seen that the LBP provides the overall worst performance for all perturbation types. It is then followed by CENSUS-sparse and CENSUS-dense, both of which provide comparable performance despite their very different numbers of feature bits. For most perturbation types, it is then followed by BRIEF and finally by STABLE (notice the curve with circles exceeds all the other curves in most cases).

Fig. 6

ROC curves obtained for different perturbation types. In the case of STABLE and BRIEF, the provided ROC curves represent the best performance case over 25 random trials, i.e., the one with the highest AUC value: (a) Gaussian noise, (b) blurring, (c) shifting, (d) scaling, (e) rotation.

In Fig. 7, the matching performance is analyzed in relationship with the descriptor size. All descriptors with a constant number of bits are marked as points, whereas all the others are represented as curves. In this analysis, it is even more pronounced that the performance of the both CENSUS descriptors and LBP is significantly worse than for STABLE and BRIEF at the respective bit counts. In the case of noise, blur, and shift perturbations, the STABLE descriptor outperforms the BRIEF descriptor, especially for medium numbers of feature bits.

Fig. 7

Relationship between matching performance of different feature descriptors and the number of feature bits. Each point on a curve stands for the average AUC value over 25 random trials, while the whiskers show the corresponding standard deviation: (a) Gaussian noise, (b) blurring, (c) shifting, (d) scaling, (e) rotation.

The performance of STABLE versus BRIEF is documented in detail in Fig. 8. The advantage of STABLE over BRIEF is expressed in terms of the recognition performance gain defined as a ratio between AUC values obtained by both descriptors using the same numbers of bits. It follows that AUC ratios above one mark the cases where STABLE outperformed BRIEF and vice versa. It is apparent that the advantage of STABLE is mostly pronounced for medium bit counts, while with the increasing size of the descriptor, the difference is getting smaller as both descriptors become more similar to each other. It should be noted that at the maximum possible number of bits, both descriptors are in fact the same where each bit is generated by just a pair of pixels. There are two cases in which STABLE significantly outperformed BRIEF, namely perturbations by (i) the additive noise and (ii) the blur. In the case of additive noise, a performance gain as large as 30% was obtained with 8-bit descriptors. For blur and shift perturbations, the highest AUC ratios exceeding 5% were obtained for 32-bit and 8-bit descriptors, respectively. For scale and rotation perturbations, STABLE performs generally slightly worse than BRIEF; however, the worst performance loss is still well below 5%.

Fig. 8

Recognition performance gain (i.e., the ratio between AUC values) of STABLE over BRIEF.

4.2.

Stereo Matching on Middlebury Stereo Dataset

We assessed the dense stereo reconstruction performance of STABLE versus BRIEF on real-world data. We used 10 evaluation training sets with disparity ground truth from the Middlebury Stereo Datasets 2014.²¹ For both STABLE and BRIEF, we used windows of size of $15\times 15$ and descriptor length of 8, 16, 32, and 64 bits. The left view served as the reference view.

As the error metric, we used the percentage of pixels with absolute disparity error greater than 2.0 (dubbed as bad 2.0). We did not include occluded pixels. For each of the 10 datasets, we performed 25 runs (each run with a different index mask for both descriptors) and recorded the best and average values for each metric. Performance gain of STABLE relative to BRIEF averaged over all datasets is shown in Fig. 9.

Fig. 9

Stereo matching performance gain of STABLE over BRIEF on Middlebury Stereo Dataset 2014. Displayed are the relative differences between average and best bad 2.0 scores from 25 runs averaged over all datasets.

Results in Fig. 9 show that both for average and best cases and for all tested bit lengths, STABLE outperforms BRIEF. The largest performance gain (4.33% in bad 2.0) was measured for the length of 32 bits. Performance gain for 8 and 64 bits is significantly lower for both metrics. For illustration, Figs. 10(a) to 10(d) show the example where STABLE outperformed BRIEF the most and Figs. 10(e) to 10(h) show the example where STABLE was least superior to BRIEF. The green areas in the difference images in Figs. 10(c) and 10(g) depict areas where STABLE gained a better bad 2.0 score when compared to BRIEF, whereas magenta refers to a better bad 2.0 score for BRIEF. Black to white areas indicate that both methods obtained very similar bad 2.0 errors.

Fig. 10

Stereo matching performance of STABLE and BRIEF on Vintage (a)–(d) and Jadeplant (e)–(h) examples from the Middlebury Stereo Dataset 2014 where STABLE outperformed BRIEF the most (a)–(d) and the least (e)–(h) for the length of 32 bits. (a) and (e) The depth reconstructions when using STABLE, (b) and (f) Depth reconstructions for BRIEF, respectively. (c) and (g) The differences in bad 2.0 error metric wrt the corresponding ground truth depth maps are shown in (d) and (h). The green areas in the difference images depict areas where STABLE gained better bad 2.0 score when compared to BRIEF, whereas magenta refers to a better bad 2.0 score for BRIEF. Black to white areas indicate that both methods obtained very similar bad 2.0 errors.

4.3.

Road Surface Data

In this section, we present results on real world data acquired by driving our system on a freeway. First, we compare STABLE and CENSUS-dense and provide results for STABLE with different descriptor lengths. Subsequently, we provide illustrative examples for selected features found during the road surface survey. The purpose of this survey is to assess 3-D road surface as poor road conditions lead to increased wear and tear on vehicles and has an impact on surface water transport, noise emission, etc.

4.3.1.

Descriptor properties for road surface

Figures 11(a) and 11(b) show a stereo image pair depicting a top down view of a washed concrete surface. The estimated depth maps shown in Figs. 11(c) and 11(d) are results of $15\times 15$ CENSUS-dense and $15\times 15$ STABLE with 64 bit descriptor length, respectively. The result of STABLE is less noisy (i.e., less “black” pixels) using just 64 bits, while achieving a qualitatively similar, or even slightly better, depth estimation as the $15\times 15-1=224$ bit long CENSUS descriptor.

Fig. 11

Depth reconstruction of the road surface from a stereo image pair (a) and (b) using $15\times 15$ CENSUS-dense with 224 bits (c), and $15\times 15$ STABLE with 64 bits (d).

Figure 12 shows the performance of STABLE with a descriptor length ranging from 16 bits to 112 bits, which is the maximum bit count possible for the $15\times 15$ matching window. While the 16-bit long descriptor still provides quite noisy results, using 32- or 64-bit descriptors improves the reconstruction quality significantly. On the other hand, increasing the size of the descriptor to full 112 bits does not seem to improve the result any further.

Fig. 12

Depth reconstruction quality obtained by $15\times 15$ STABLE with different bit counts: (a) 16, (b) 32, (c) 64, (d) 112.

Finally, Fig. 13 shows the influence of spatial averaging and additive noise on CENSUS-dense and STABLE. In both cases, STABLE outperforms CENSUS-dense descriptor. The images show the estimated disparities, which are linearly related to depth measurements.

Fig. 13

Depth reconstruction results for $15\times 15$ CENSUS-dense with 224 bits and $15\times 15$ STABLE with 64 bits: (a) and (b) corrupted by $5\times 5$ averaging, (c) and (d) corrupted by Gaussian noise with $-20\mathrm{dB}$ variance.

4.3.2.

Sample images from road survey

Due to the lack of ground truth, we refer to a manual annotation of interesting properties visible to human observers and show the derived 3-D reconstruction from which these properties become clearly visible. In most of the results, there is a vertically oriented 3-D structure visible. This stems from diamond grinding, which is a pavement preservation technique used to remove surface irregularities to reduce noise and increase road safety. We applied postprocessing based on total variation (TV) regularization²² to obtain smoother 3-D renderings, shown in Fig. 14. The brighter the disparity, the closer the observed object point is to the observer.

Fig. 14

Illustrative results for road surface data (disparity maps smoothed by TV regularization): grinded concrete surface with expansion joint: (a) image, (b) disparity, and (c) 3-D rendering (cutout); grinded concrete surface with a hole: (d) image, (e) disparity, and (f) 3-D rendering (cutout); ungrinded concrete surface with a larger break out region: (g) image, (h) disparity, and (i) 3-D rendering (cutout); grinding at different depths and a chewing gum like object observed in a portion of the deeper grinding: (j) image, (k) disparity, and (l) 3-D rendering (cutout).

Figure 14(a) shows an image of a grinded concrete road surface with an expansion joint. The grinding stripes, as well as the expansion joint, are visible in the disparity map in Fig. 14(b). A 3-D rendering of the portion around the expansion joint is provided in Fig. 14(c). Figure 14(d) shows an image of a grinded concrete pavement with a small hole; the corresponding disparity and 3-D rendering of the area of the hole are shown in Figs. 14(e) and 14(f), respectively. A grayscale image, disparity, and 3-D rendering of a larger break out of the surface are shown in Figs. 14(g) to 14(i), respectively. Finally, an image showing two grinding lanes of different depths is provided in Fig. 14(j). Additionally, in the left upper corner, there is some material, which we assume is chewing gum, observed in the area of the deeper grinding. The disparity in Fig. 14(k) shows that the valley of the grinding is not reached at the position of this suspicious object. In the 3-D rendering in Fig. 14(l), the different grinding depths and the object are visible as well.

4.4.

Performance

For computational complexity analysis, we compared STABLE and BRIEF with $K$ features bits applied to $X\times Y$ image patches implemented using the index filter mask implementation, which was shown in Fig. 4. In general, there are two main operations required for using any of the local binary descriptors—building and matching. The matching operation is typically identical for all binary descriptors, i.e., making use of the Hamming distance applied to binary strings of length $K$. The difference can thus be only in the computational complexity of the building operation.

Building of the descriptors is comprised of three basic steps:

The index filter mask is generated only once and can be considered an input parameter for the building operation. Therefore, this step can be omitted from our analysis. The binarization step uses the same thresholding algorithm for both analyzed descriptors and can be neglected as well. Hence, the only difference comes from the complexity of computing the accumulator values, as shown in Algorithm 1. While STABLE requires processing of $X\times Y$ elements from the index filter mask as well as from the image patch (or $X\times Y-1$ for odd number of pixels), BRIEF requires processing only $2K$ such elements. Consequently, for a fixed $K$, STABLE scales linearly with the number of patch pixels while BRIEF, in principle, requires only a constant time.

Algorithm 1

Computation of the accumulator values in BRIEF and STABLE using a single index filter mask.

In practice, however, the difference between the actual execution time on CPU or GPU platforms and the theoretical one might be more in favor of STABLE due to caching in the on-chip memory. When a memory read for a cell is requested, often nearby cells are fetched and stored in the cache as well (details are hardware-dependent). To enable optimal caching, the data have to be well-organized in the memory, i.e., aligned with the hardware layout, and should be accessed using a predictable memory access patterns, e.g., in the same order as they were stored. This is especially important for GPUs where the global memory latency is higher compared to the CPU memory and thus optimal utilization of the cache memory has a higher impact on the final performance. We believe that such memory caching mechanisms can be better utilized with STABLE as all elements in both index and image patch arrays are always accessed. In particular, they are accessed sequentially. Therefore, the memory access pattern can be fully optimized. On the other hand, as BRIEF uses a random-access sparse memory pattern, prediction algorithms implemented in various memory caching mechanisms are more prone to fail.

To practically measure the difference between execution times of building STABLE and BRIEF descriptors, we implemented the accumulator algorithm, described in Algorithm 1, for a CUDA-enabled GPU in C/C++. Namely, we used the CUDA Toolkit 7.5 and a NVIDIA GTX Titan GPU. As a reference, we also implemented the CENSUS-dense descriptor. The test data were a grayscale image of $1500\times 1500\text{pixels}$. The descriptors of length 32 and 64 bits were represented as packed binary strings using 32- and 64-bit integers, respectively, and were computed from windows of $15\times 15\text{pixels}$. Each CUDA thread computed one descriptor. Threads were arranged into $32\times 32$ thread blocks. The CUDA code was compiled with the preference on L1 cache memory size. We executed the algorithm 500 times, each time with a different randomly generated index filter mask for both descriptors. Average measured execution times are listed in Table 1.

Table 1

Average execution time measurements of descriptor generation for BRIEF, STABLE, and CENSUS-dense run on a GPU. A comparison relative to BRIEF is shown on the right side of respective columns.

Results in Table 1 show that total execution time of STABLE, in comparison to BRIEF, is lower than expected merely from the number of utilized pixels for both 32- and 64-bit lengths. When considering execution time per utilized pixel, execution time for STABLE is even lower by 44% and 22% for 32- and 64-bit length, respectively. This strongly points to a better utilization of GPU’s hardware memory caching.