# Self-Similarity Based Corresponding-Point Extraction from Weakly Textured Stereo Pairs

Authors: Min Mao; Kuang-Rong Hao; Yong-Sheng Ding
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

For the areas of low textured in image pairs, there is nearly no point that can be detected by traditional methods. The information in these areas will not be extracted by classical interest-point detectors. In this paper, a novel weakly textured point detection method is presented. The points with weakly textured characteristic are detected by the symmetry concept. The proposed approach considers the gray variability of the weakly textured local regions. The detection mechanism can be separated into three steps: region-similarity computation, candidate point searching, and refinement of weakly textured point set. The mechanism of radius scale selection and texture strength conception are used in the second step and the third step, respectively. The matching algorithm based on sparse representation (SRM) is used for matching the detected points in different images. The results obtained on image sets with different objects show high robustness of the method to background and intraclass variations as well as to different photometric and geometric transformations; the points detected by this method are also the complement of points detected by classical detectors from the literature. And we also verify the efficacy of SRM by comparing with classical algorithms under the occlusion and corruption situations for matching the weakly textured points. Experiments demonstrate the effectiveness of the proposed weakly textured point detection algorithm.


---

## Body

## 1. Introduction

Local interest points can be used for many applications, such as video analyzing, object detection, localization, and identification. Techniques which only use images to reconstruct 3D scenes are now the most popular of its applications. Since many algorithms based on the diversity of concepts such as graph cuts [1] and minimal path search [2] can only handle short-baseline stereo matching, that is, they cannot be used at the wide-baseline situation, on the other hand, gradient detectors can be used for wide-baseline matching well; in general, the process for matching the discrete image points can be divided into three main steps. First, extracting the “interest points” from each image, such as T-junctions, corners, and the point detector should have the property of repeatability, which guarantee finding the same physical interest points under different viewing conditions. Next, each interest point can be represented by a feature vector through the descriptor, which should also be distinctive, finally, matching the descriptor vectors between different images.Almost all of detectors are based on the gradient map of image; for example, the Harris corner detector [3] is based on the second moment matrix, which describes the gradient distribution in a local neighborhood of a point in image, but corners detected by this method are not scale invariant. Mikolajczyk and Schmid [4] proposed two scale-invariant methods, that is, Harris-Laplace and Hessian-Laplace, which are based on the concept of automatic scale selection [5], and the location is selected by Harris measure or the determinant of the Hessian matrix; scale is selected by Laplacian; Lowe [6] speeds up the above methods by using the difference of Gaussians (DoG) to approximate the Laplacian of Gaussians (LoG). There are lots of different detectors which have been proposed in the literature [7–10]. However, problems of methods based on interest point still remain, such as image blurring, magnification, and illumination; one of the most serious weaknesses between these is that these methods could not get point on the low texture areas. Since these areas can be defined by its gradient below some constant thresholds, it is difficult to extract points on them by classical interest-point detectors.As a guiding principle for describing shapes this characteristic has a rich history. Animals, man-made objects, and plants are usually with symmetry characteristic. Many techniques have been proposed to analyze this characteristic. For example [11] describes an algorithm to segment objects into terms of points, line segments, and circles. Loy and Zelinsky [12] use the local radial symmetry to highlight points of interest within a scene, which need not consider the contribution of a local neighborhood to a central pixel. In this paper we focus on the characteristic of strong self-similarity. The approach proposed in [13] inspires us that the region of weakly textured area has the characteristic of strong self-similarity; hence the weakly textured points can be located by this characteristic; moreover the locations with self-similar structure of local pattern are also distinguishable in different images. Our goal is to develop both a detector and matching algorithm for getting corresponding-point in weakly textured regions under wide-baseline situation. Our work in this paper can be divided into three parts, namely, candidates of weakly textured point detection, refining the set of candidates, and weakly textured point matching algorithm based on sparse representation.In the detecting part, the proposed detector is based on the entities: circumferences and radii; it sums the value on circumferences and radii; the information from image is very first level of data processing, which is contrary to gradient-based methods; hence, for giving the scale invariant as the gradient-based methods we introduce a mechanism for automatic radial selection. The following two approaches can be identified; the first one is used to obtain the symmetry maps for each pixel in different radius scales, which is also used in [14]. The second approach selects the radius scale for each pixel.In the refinement part, the set of weakly textured points can be refined by computing the gradient magnitude in scale-space [15], which is widely used in image processing community, such as feature description, point detection, and image structure analysis. Here we use this theory to measure the texture strength and for reducing the points which do not belong to weakly textured point; we also propose a threshold selection mechanism.In the point matching part, the correspondence relationship of points which contain the same scene in two images will be determined. The matching between two points set is a one-to-one mapping between the points in these two sets. There are many algorithms for computing the similarity between two point features, such as zero-mean normalized cross correlation (ZNCC) [16] and Hausdorff distance [17], which many algorithms have been suggested for. We here introduced the sparse representation concept [18] for weakly textured point matching, which has been used for human face recognition in [19]. This approach considers all possible supports (here is the set of weakly textured points in the second image) and can automatically choose the minimal number of samples needed to represent each feature of point in the first image.The approach proposed in this work gives a new detector for extracting the weakly textured points from image in which the objects have weakly textured characteristic. Moreover, since the detector is based on radial symmetry, it is not sensitive to variations in image illumination. In the experiment for detectors, the results obtained on image sets of different image sets under different types of geometric and photometric transformations show that the extracted points by this detector are the complement of classical detectors and high robustness with intraclass variations. In the point matching algorithms test experiment, the method based on sparse representation outperforms other algorithms under the pixel corruption and block occlusion situations, respectively, and the results also show that the extracted weakly textured points are also distinguishable from locations; finally we use our algorithm to promote the quasi-dense matching algorithm which was proposed in [20] to verify the proposed approach under wide-baseline situation.This paper is organized as follows: in Section2 the method is proposed to detect the candidate of weakly textured regions. In Section 3, we sketch out a mechanism for points refinement via scale-space selection theory. In Section 4, the sparse representation theory is used for matching weakly textured point. In Section 5, the proposed method is tested in accordance with two protocols [21, 22] for evaluation of local region detectors and matching algorithm. Section 6 provides concluding remarks and possible extensions of the proposed method.


## 2. Weakly Textured Feature Points Detection

Given an imageI with the weakly textured region Ω
WT and texture region Ω
T, it is clear that there has no corner-point or have few edge-points in the neighbor region of the points in Ω
WT (see Figure 1). Let I
(
x
,
y
) denote the gray value of image; then the points’ characteristic in the region Ω
WT can be represented by its first- and second-order partial derivatives as
(1)
I
x
,
I
y
,
I
x
x
,
I
y
y
,
I
x
y
,
I
y
x
≈
0
,
{
(
x
,
y
)
∈
Ω
WT
}
.Figure 1
Example of a weakly textured region in human model.For the above mentioned, the detectors based on the gradient feature such as the Hessian, Harris, and SIFT detectors could not be used for detecting these points. So these points should be detected in different ways. As shown in Figure1, the region formed by weakly textured pixel and its neighborhoods can be segmented in many fragments and the pixel’s gray value distribution in each fragment is similar.LetI
(
x
) be the intensity value at location; Ω
p denotes the reference fragment in the image; then the self-similar fragment Ω
p can be measured by the normalized correlation coefficient as follows:
(2)
ncc
(
P
,
T
)
=
∑
i
(
I
(
x
i
)
-
I
-
)
(
I
(
T
(
x
i
)
)
-
I
-
)
(
∑
i
(
I
(
x
i
)
-
I
-
)
2
)
(
∑
i
(
I
(
T
(
x
i
)
)
-
I
-
)
2
)
,
hhhhhhhhhhhhhhhhhhhh
{
p
≠
q
∣
q
=
1,2
,
…
,
N
}
,
where I
(
T
(
x
)
)
=
a
+
b
I
(
x
)
∀
x
∈
Ω
p.I
- denotes the average intensity value of fragment Ω
p. The purpose of the formula I
(
x
i
)
-
I
- is to reduce the influence caused by intensity; T
(
·
) denotes a geometrical transformation.From Figure1, it is clear that the weakly textured region has strong mirror symmetry; let point p
=
(
r
,
θ
) be represented in polar coordinates, let φ
∈
[
0
,
π
) denote the mirror line orientation, and then the symmetric point of p about the mirror line can be represented as p
′
=
(
r
,
2
φ
-
θ
). For measuring the mirror symmetry about the region Ω
p, it should fulfill all mirror line orientation φ
∈
[
0
,
π
); here the symmetry of region Ω
p can be obtained as follows [23]:
(3)
S
w
_
texture
(
Ω
p
)
=
1
N
∑
i
=
0
N
-
1
ncc
(
Ω
p
,
T
(
Ω
p
,
φ
i
)
)
,
where T
(
·
) denotes the symmetry transformation function, and it transforms the Ω
p to its symmetric region about the mirror line orientation φ
i
∈
{
φ
0
,
φ
1
,
…
,
φ
N
-
1
}, Δ
φ
=
π
/
N, and φ
i
=
i
×
Δ
φ. It is easy to prove that the max
⁡
(
S
w
-texture
(
Ω
p
)
)
=
1 and min
⁡
(
S
w
-texture
(
Ω
p
)
)
=
0
,
Ω
p
∈
I.


### 2.1. Same Radial forS
w
-texture

In the example shown in Figure2 the strength of S
w
-texture with the same radial in different images is affected by the similarity of its region, as we can see that the strong texture region has small value of S
w
-texture; in contrast, the value of S
w
-texture in weakly textured region is close to 1. So S
w
-texture can be used for detecting the weakly textured region. However the middle-down part of Figure 2 shows that the region with strong similarity but not weakly textured region has high value of S
w
-texture; this case indicates that the weak texture cannot be detected by S
w
-texture only. And in Section 3, we will solve this problem by the differential expressions at the center point of region Ω
p.Figure 2
S
w
-texture in different image structures with the same radius.


### 2.2. Radial Selection forS
w
-texture

According to the above discussion, we useS
w
-texture as our weakly textured detector (WTD); however, there are many factors which can affect the performance of WTD, including the structure complexity distributed within the local region, variety illumination for the local region, and radials chosen by WTD. Here we investigate the performance at which WTD measures region’s texture strength with different radials.As shown in Figure3, the texture strength is reflected by the intensity of the pixel in the similarity map; that is, the pixel with lower texture strength has higher intensity. When the radial change from small to large the intensity of the pixel with low texture strength will become lower, whereas the intensity of the pixel with high texture strength will become higher.Figure 3
Similarity maps under radiiR
=
4 and R
=
32.The points detect by WTD with different radials are shown in Figure4. Obviously, the result is largely affected by the radials of the operator.Figure 4
Extracted points under radiiR
=
4 and R
=
32.Here we proposed a mechanism for automatic radial selection. The radial selection mechanism should follow heuristic principles: first, the radial must be large enough to contain the weakly textured region; that is, the radial should extend the weakly textured region until the region bound close to the texture feature. Second, the points chosen by this mechanism should have the maxima value ofS
w
-texture with its radial. Third, the mechanism should have robustness to small variations caused by fragments; that is, the radial can ignore small fragments in the weakly textured region.As shown in Figure5, S
w
-texture varies with the radius, and let S
R be the derivative of S
w
-texture with radius. In differential geometric terms, the fine-radius for each weakly textured points should simply satisfy S
R
R
=
0, which is the second-order derivative of S
w
-texture. On the other hand, when considering the influence caused by neighboring fragments, we here use the following γ
-
parameterized normalized derivative:
∂
R
R
(
R
γ
S
w
-texture
)
=
0. According to this formula the influence caused by the fragments can be eliminated under the fitted parameterized γ, with γ
=
0.5. Figure 6 shows the results with this radius selection method.Figure 5
S
w
-texture varies on a scale from R
=
2 to R
=
60.Figure 6
Radius selected for weakly textured points.


## 2.1. Same Radial forS
w
-texture

In the example shown in Figure2 the strength of S
w
-texture with the same radial in different images is affected by the similarity of its region, as we can see that the strong texture region has small value of S
w
-texture; in contrast, the value of S
w
-texture in weakly textured region is close to 1. So S
w
-texture can be used for detecting the weakly textured region. However the middle-down part of Figure 2 shows that the region with strong similarity but not weakly textured region has high value of S
w
-texture; this case indicates that the weak texture cannot be detected by S
w
-texture only. And in Section 3, we will solve this problem by the differential expressions at the center point of region Ω
p.Figure 2
S
w
-texture in different image structures with the same radius.


## 2.2. Radial Selection forS
w
-texture

According to the above discussion, we useS
w
-texture as our weakly textured detector (WTD); however, there are many factors which can affect the performance of WTD, including the structure complexity distributed within the local region, variety illumination for the local region, and radials chosen by WTD. Here we investigate the performance at which WTD measures region’s texture strength with different radials.As shown in Figure3, the texture strength is reflected by the intensity of the pixel in the similarity map; that is, the pixel with lower texture strength has higher intensity. When the radial change from small to large the intensity of the pixel with low texture strength will become lower, whereas the intensity of the pixel with high texture strength will become higher.Figure 3
Similarity maps under radiiR
=
4 and R
=
32.The points detect by WTD with different radials are shown in Figure4. Obviously, the result is largely affected by the radials of the operator.Figure 4
Extracted points under radiiR
=
4 and R
=
32.Here we proposed a mechanism for automatic radial selection. The radial selection mechanism should follow heuristic principles: first, the radial must be large enough to contain the weakly textured region; that is, the radial should extend the weakly textured region until the region bound close to the texture feature. Second, the points chosen by this mechanism should have the maxima value ofS
w
-texture with its radial. Third, the mechanism should have robustness to small variations caused by fragments; that is, the radial can ignore small fragments in the weakly textured region.As shown in Figure5, S
w
-texture varies with the radius, and let S
R be the derivative of S
w
-texture with radius. In differential geometric terms, the fine-radius for each weakly textured points should simply satisfy S
R
R
=
0, which is the second-order derivative of S
w
-texture. On the other hand, when considering the influence caused by neighboring fragments, we here use the following γ
-
parameterized normalized derivative:
∂
R
R
(
R
γ
S
w
-texture
)
=
0. According to this formula the influence caused by the fragments can be eliminated under the fitted parameterized γ, with γ
=
0.5. Figure 6 shows the results with this radius selection method.Figure 5
S
w
-texture varies on a scale from R
=
2 to R
=
60.Figure 6
Radius selected for weakly textured points.


## 3. Weakly Textured Points Filter for Fine Positioning

In Section2 we have analyzed the weakly textured feature and use WTD with proposed adaptive radial mechanism to position the weakly textured point. However the problem in the middle-down part of Figure 2 shows that the point has large value of S
w
-texture which is not the weakly textured point. On the other hand, the state-of-the-art edge detector corresponds to detecting points with the maximum gradient magnitude in the gradient direction, so edges can be detected in scale-space; here we extend these ideas to remove these points which do not have the weakly textured property.


### 3.1. Improve WTD in Scale-Space

When giving a 2D signalf, the definition of the scale-space representation L
:
R
2
×
R
+
→
R is the solution of the diffusion equation [24]:
(4)
∂
t
L
=
1
2
∇
2
L
=
1
2
(
∂
x
x
+
∂
y
y
)
L
.
It can be proved L
(
·
,
t
)
=
g
(
·
,
t
)
*
f
(
·
), where g
:
R
2
×
R
+
→
R is the Gaussian kernel; that is,
(5)
g
(
x
,
y
;
t
)
=
1
2
π
t
e
-
(
x
2
+
y
2
)
/
(
2
t
)
.
For removing the point with strong texture feature, we should detect its texture strength in its neighbor region; here we use the gradient magnitude to represent it. Based on the γ
-
p
a
r
a
m
e
t
e
r
i
z
e
d normalized derivative concept in the scale-space, we will consider the following differential expression:
(6)
L
grad
(
·
;
t
)
=
t
γ
|
(
∂
L
(
·
;
t
)
∂
x
)
2
+
(
∂
L
(
·
;
t
)
∂
y
)
2
|
.
As shown in Figure 7 when using this operator to measure the points’ texture strength, it is clear that L
grad will change along with the scale t. Moreover the more close the point is to the edge the bigger the change to L
grad magnitude it has (the cross-point “+” in each picture denotes the one more close to the edge).Figure 7
L
grad varies on scale-space from t
=
10 to t
=
80.


### 3.2. Point Texture Strength Based on Local Maximum over Scales of Derivative

As above mentioned, the point texture strength can be reflected byL
grad magnitude over scales; hence we can define it by the local maximum over scales of derivative, and here we use following step function which is the close-form theoretical analysis for edge models, and it also can be convenient for further analysis to instead the actual edges. Consider
(7)
f
(
x
)
=
{
0
for
x
<
x
0
1
for
x
≥
x
0
.
On the other hand, Gaussian kernel is a local kernel which responds to near neighbor of the input variables; hence, we here restrict the kernel size to the interval [
-
3
t
,
3
t
]. Consider
(8)
g
(
x
;
t
)
=
{
1
2
π
t
e
-
x
2
/
(
2
t
)
x
∈
[
-
3
t
,
3
t
]
0
otherwise
.
By substitution from (7) and (8) in (6), we obtain the L
grad magnitude of f
(
x
) with the following equation:
(9)
L
(
x
,
t
)
=
{
0
x
-
x
0
≤
-
3
t
∫
-
3
t
x
-
x
0
g
(
x
′
;
t
)
d
x
′
-
3
t
<
x
-
x
0
<
3
t
∫
-
3
t
3
t
g
(
x
′
;
t
)
d
x
′
x
-
x
0
≥
3
t
.
According to above equation, magnitude L
grad of f
(
x
) can be represented as the following expression:
(10)
L
x
(
x
,
t
)
=
{
g
(
x
-
x
0
,
t
)
|
x
-
x
0
|
<
3
t
0
otherwise
,
where |
x
-
x
0
| represents the distance between x and the discontinuous point x
0 which is the point on the edge, and we use the symbol Δ
l instead of it. This formula shows that when Δ
l
<
3
t, L
grad
≠
0, and as mentioned above, the local maximum over scales of derivative will be used as the point’s texture strength. But from Figure 7 it can be shown that there is no guarantee for getting the local maximum of the derivative over scales. And the derivative of L
x
(
x
,
t
) can be gotten from formula (10) as follows:
(11)
∂
L
x
∂
t
=
{
1
2
2
π
t
-
5
/
2
e
-
Δ
l
2
/
2
t
(
Δ
l
2
-
t
)
Δ
l
<
3
t
0
otherwise
.
It is clear that the local maximum of L
x depends on scale t; that is, if t
0
=
Δ
l
2, then ∂
L
x
/
∂
t
|
t
=
t
0
=
0. Hence the range of scale [
1
,
t
max
⁡
] is difficult to select; for example, when Δ
l
=
20, then t
max
⁡ must satisfy t
max
⁡
≥
400, and when t
max
⁡ is set too large, it will increase in computation complexity for finding the local maximum of L
x. Obviously, we want to find the way to ignore the influence caused by Δ
l; that is, t
0 is not proportional to Δ
l
2.For this reason we need to transformL
x
(
x
,
t
) to the function in which local maximum does not depend on Δ
l
2; let L
x
′
=
p
(
t
)
·
L
x; then ∂
L
x
′
/
∂
t
=
(
∂
p
(
t
)
/
∂
t
)
L
x
+
p
(
t
)
(
∂
L
x
/
∂
t
); that is, the derivative of ∂
L
x
′
/
∂
t is(12)
∂
L
x
′
∂
t
=
{
1
2
2
π
t
-
5
/
2
e
-
Δ
l
2
/
2
t
(
2
p
(
t
)
t
2
+
p
(
t
)
(
Δ
l
2
-
t
)
)
Δ
l
<
3
t
0
otherwise
.
For the purpose of reducing the incremental of t
max
⁡ when Δ
l increases, hence p
(
t
) here should be the decreasing function of scale t. On the other hand, despite the fact that t
max
⁡ should not be proportional to Δ
l
2, it has to guarantee that the local maximum position t
0 increases with increasing Δ
l; that is, it should satisfy
(13)
∂
L
x
′
(
Δ
l
1
,
t
)
∂
t
=
0
,
(
t
=
t
1
)
∂
L
x
′
(
Δ
l
2
,
t
)
∂
t
=
0
,
(
t
=
t
2
)
}
⟹
t
1
>
t
2
.
For the constraint to p
(
t
), it can be assumed that p
(
t
)
=
α
-
t
γ
/
β, where α
,
β
>
0, and it also should satisfy log
⁡
α
β
>
γ
log
⁡
t (this constraint can guarantee that if t
≥
1, then L
x
′
>
0); hence, for the above mentioned when t
≥
1, then p
(
t
)
,
p
′
(
t
)
≠
0; if we insert p
(
t
) into (13) and give γ
=
1, then the local maximum position t
0 is given by
(14)
∂
L
x
′
∂
t
=
0
⟹
t
0
=
-
(
Δ
l
2
+
α
β
)
+
(
Δ
l
2
+
α
β
)
2
+
4
α
β
Δ
l
2
2
=
2
α
β
Δ
l
2
(
Δ
l
2
+
α
β
)
+
(
Δ
l
2
+
α
β
)
2
+
4
α
β
Δ
l
2
=
2
α
β
(
1
+
α
β
/
Δ
l
2
)
+
(
1
+
α
β
/
Δ
l
2
)
2
+
4
(
α
β
/
Δ
l
2
)
.
It is clear that when α
β
/
Δ
l
2
→
0, then t
0
→
α
β; moreover it is an increasing function of Δ
l; that is, it has the same monotonicity property with one in original function ∂
L
x
/
∂
t
|
t
=
t
0
=
0. Figure 8 shows the result improved by L
x
′
(
x
,
t
).Figure 8
Results from improved texture measure method under different images.


### 3.3. Threshold Selection for Weakly Textured Points

A method for threshold selection to remove points which are not weakly textured points is needed, if their local maximum of texture strength is beyond this threshold.On the other hand, there is no a priori information that can be used for removing the point which has no weakly textured property, and to illustrate the method for threshold selection, here, let us consider the distribution of weakly textured points detected by the method in Section2.Figure9 shows the weak points detected by WTD and the 3D histogram of their distribution in the image. Here, the image is divided into M
×
N fragments; that is, if I is the image, then I
=
{
R
1
,
R
2
,
…
,
R
M
×
N
}; according to this distribution we find that regions have more concentrated distribution than others which are weakly textured regions. It also indicates that the local maximum texture strength of points distributed in these regions can be used to detect the threshold.Figure 9
3D histogram of weakly textured points distribution.Through the above result, the properties of weakly textured region can be assumed as follows.(i)
The points which are detected by WTD in the region with weakly textured feature have more concentrated distribution than other regions.
(ii)
The mean of local maximum texture strength in the weakly textured region is lower than that in other regions.An important consequence of these properties is that it allows the threshold to vary with different images. We here use the Otsu threshold algorithm to segment the point sets detected by WTD into two classes, that is, the sets belonging to weakly textured region and the sets belonging to other regions. LetT
O be the threshold defined by Otsu threshold algorithm; N
(
R
i
) is the number of the points in fragment R
i (as shown above, the image is divided into M
×
N fragments), and according to property (i), if N
(
R
i
)
≥
T
O, then fragment R
i is selected as the part of weakly textured region which will be used for determining the threshold of texture strength later. On the other hand, when the weakly textured region is determined, then according to property (ii), the threshold T
s can be defined as follows:
(15)
T
s
=
min
⁡
i
(
max
⁡
j
{
t
(
x
j
)
∣
x
j
∈
R
i
}
)
,
hhhhhhhh
{
R
i
∈
I
∣
N
(
R
i
)
≥
T
O
}
,
where t
(
x
) is texture strength which is detected by the local maximum of the derivative over scales at point x
∈
R
i. Since the points in the weakly textured region should be retained as much as possible, we here use max
⁡
j
⁡
{
t
(
x
j
)
∣
x
j
∈
R
i
} as the subthreshold detected in region R
i; on the other hand, there also exist points which are not weakly textured points in some parts of the weakly textured region, so for removing these points the global threshold here can be obtained as min
⁡
i
⁡
(
max
⁡
j
⁡
{
t
(
x
j
)
∣
x
j
∈
R
i
}
).


### 3.4. Composed Algorithm

The mechanisms for weakly textured point detection and fine positioning were proposed, respectively. And they can be used in various ways in point detection and point removing. For the purpose of experiments and validation, we have here integrated these two modules into a composed algorithm, which can be expressed in the following four-step procedure.Stage 1.
Given a constant integerM, which is the number of points needed to be detected by WTD, M can be adjusted according to the size of image. Formulas (2) and (3) are then used to compute the vector in the radial-space {
r
1
,
r
2
,
…
,
r
N
} for each point p
i of image:
(16)
v
S
(
p
i
)
=
{
S
w
-texture
(
p
i
,
r
1
)
,
S
w
-texture
(
p
i
,
r
2
)
,
…
,
hihhhhhh
S
w
-texture
(
p
i
,
r
N
)
}
.Stage 2.
Use the mechanism proposed in Section2 to select the suitable radial r
fit for each point p
i of image I. Take S
w
-texture
(
p
i
,
r
fit
) as the similarity strength of p
i. And arrange p
i of image I in order of decreasing S
w
-texture
(
p
i
,
r
fit
). Then choose the first M points as the candidates of the weakly textured points.Stage 3.
Given a constant integerT, then scale t varies within [
1,2
,
…
,
T
]. Use L
x
′
=
p
(
t
)
·
L
x defined in formula (12) for computing the vector of each point which is obtained from Stage 2:
(17)
v
t
(
p
i
)
=
{
L
grad
(
p
i
,
t
1
)
,
L
grad
(
p
i
,
t
2
)
,
…
,
L
grad
(
p
i
,
t
T
)
}
,
hhhhhhhhhhhhhhhhhhhhhhhhhhhh
t
i
∈
[
1,2
,
…
,
T
]
.
Choose the biggest element from v
t
(
p
i
) as the texture strength of point p
i; that is,
(18)
v
t
_
max
⁡
(
p
i
)
=
max
⁡
t
i
∈
[
1,2
,
…
,
T
]
L
grad
(
p
i
,
t
i
)
.Stage 4.
Using the threshold selection mechanism to detect the thresholdT
s of texture strength and remove the points by T
s, that is, if v
t
_
max
⁡
(
p
i
)
<
T
s, then p
i is the weakly textured point.Figure10 shows the performance of above composed algorithm; it is clear that this algorithm can efficiently extract the weakly textured points, and through the scale-space texture strength concept, the points have strong textureness which can be removed completely.Results from threshold mechanism for different images. (a) Points detected by WTD. (b) Points detected by WTD + threshold mechanism. (c) Regions belong to detected points.
(a)
(b)
(c)


## 3.1. Improve WTD in Scale-Space

When giving a 2D signalf, the definition of the scale-space representation L
:
R
2
×
R
+
→
R is the solution of the diffusion equation [24]:
(4)
∂
t
L
=
1
2
∇
2
L
=
1
2
(
∂
x
x
+
∂
y
y
)
L
.
It can be proved L
(
·
,
t
)
=
g
(
·
,
t
)
*
f
(
·
), where g
:
R
2
×
R
+
→
R is the Gaussian kernel; that is,
(5)
g
(
x
,
y
;
t
)
=
1
2
π
t
e
-
(
x
2
+
y
2
)
/
(
2
t
)
.
For removing the point with strong texture feature, we should detect its texture strength in its neighbor region; here we use the gradient magnitude to represent it. Based on the γ
-
p
a
r
a
m
e
t
e
r
i
z
e
d normalized derivative concept in the scale-space, we will consider the following differential expression:
(6)
L
grad
(
·
;
t
)
=
t
γ
|
(
∂
L
(
·
;
t
)
∂
x
)
2
+
(
∂
L
(
·
;
t
)
∂
y
)
2
|
.
As shown in Figure 7 when using this operator to measure the points’ texture strength, it is clear that L
grad will change along with the scale t. Moreover the more close the point is to the edge the bigger the change to L
grad magnitude it has (the cross-point “+” in each picture denotes the one more close to the edge).Figure 7
L
grad varies on scale-space from t
=
10 to t
=
80.


## 3.2. Point Texture Strength Based on Local Maximum over Scales of Derivative

As above mentioned, the point texture strength can be reflected byL
grad magnitude over scales; hence we can define it by the local maximum over scales of derivative, and here we use following step function which is the close-form theoretical analysis for edge models, and it also can be convenient for further analysis to instead the actual edges. Consider
(7)
f
(
x
)
=
{
0
for
x
<
x
0
1
for
x
≥
x
0
.
On the other hand, Gaussian kernel is a local kernel which responds to near neighbor of the input variables; hence, we here restrict the kernel size to the interval [
-
3
t
,
3
t
]. Consider
(8)
g
(
x
;
t
)
=
{
1
2
π
t
e
-
x
2
/
(
2
t
)
x
∈
[
-
3
t
,
3
t
]
0
otherwise
.
By substitution from (7) and (8) in (6), we obtain the L
grad magnitude of f
(
x
) with the following equation:
(9)
L
(
x
,
t
)
=
{
0
x
-
x
0
≤
-
3
t
∫
-
3
t
x
-
x
0
g
(
x
′
;
t
)
d
x
′
-
3
t
<
x
-
x
0
<
3
t
∫
-
3
t
3
t
g
(
x
′
;
t
)
d
x
′
x
-
x
0
≥
3
t
.
According to above equation, magnitude L
grad of f
(
x
) can be represented as the following expression:
(10)
L
x
(
x
,
t
)
=
{
g
(
x
-
x
0
,
t
)
|
x
-
x
0
|
<
3
t
0
otherwise
,
where |
x
-
x
0
| represents the distance between x and the discontinuous point x
0 which is the point on the edge, and we use the symbol Δ
l instead of it. This formula shows that when Δ
l
<
3
t, L
grad
≠
0, and as mentioned above, the local maximum over scales of derivative will be used as the point’s texture strength. But from Figure 7 it can be shown that there is no guarantee for getting the local maximum of the derivative over scales. And the derivative of L
x
(
x
,
t
) can be gotten from formula (10) as follows:
(11)
∂
L
x
∂
t
=
{
1
2
2
π
t
-
5
/
2
e
-
Δ
l
2
/
2
t
(
Δ
l
2
-
t
)
Δ
l
<
3
t
0
otherwise
.
It is clear that the local maximum of L
x depends on scale t; that is, if t
0
=
Δ
l
2, then ∂
L
x
/
∂
t
|
t
=
t
0
=
0. Hence the range of scale [
1
,
t
max
⁡
] is difficult to select; for example, when Δ
l
=
20, then t
max
⁡ must satisfy t
max
⁡
≥
400, and when t
max
⁡ is set too large, it will increase in computation complexity for finding the local maximum of L
x. Obviously, we want to find the way to ignore the influence caused by Δ
l; that is, t
0 is not proportional to Δ
l
2.For this reason we need to transformL
x
(
x
,
t
) to the function in which local maximum does not depend on Δ
l
2; let L
x
′
=
p
(
t
)
·
L
x; then ∂
L
x
′
/
∂
t
=
(
∂
p
(
t
)
/
∂
t
)
L
x
+
p
(
t
)
(
∂
L
x
/
∂
t
); that is, the derivative of ∂
L
x
′
/
∂
t is(12)
∂
L
x
′
∂
t
=
{
1
2
2
π
t
-
5
/
2
e
-
Δ
l
2
/
2
t
(
2
p
(
t
)
t
2
+
p
(
t
)
(
Δ
l
2
-
t
)
)
Δ
l
<
3
t
0
otherwise
.
For the purpose of reducing the incremental of t
max
⁡ when Δ
l increases, hence p
(
t
) here should be the decreasing function of scale t. On the other hand, despite the fact that t
max
⁡ should not be proportional to Δ
l
2, it has to guarantee that the local maximum position t
0 increases with increasing Δ
l; that is, it should satisfy
(13)
∂
L
x
′
(
Δ
l
1
,
t
)
∂
t
=
0
,
(
t
=
t
1
)
∂
L
x
′
(
Δ
l
2
,
t
)
∂
t
=
0
,
(
t
=
t
2
)
}
⟹
t
1
>
t
2
.
For the constraint to p
(
t
), it can be assumed that p
(
t
)
=
α
-
t
γ
/
β, where α
,
β
>
0, and it also should satisfy log
⁡
α
β
>
γ
log
⁡
t (this constraint can guarantee that if t
≥
1, then L
x
′
>
0); hence, for the above mentioned when t
≥
1, then p
(
t
)
,
p
′
(
t
)
≠
0; if we insert p
(
t
) into (13) and give γ
=
1, then the local maximum position t
0 is given by
(14)
∂
L
x
′
∂
t
=
0
⟹
t
0
=
-
(
Δ
l
2
+
α
β
)
+
(
Δ
l
2
+
α
β
)
2
+
4
α
β
Δ
l
2
2
=
2
α
β
Δ
l
2
(
Δ
l
2
+
α
β
)
+
(
Δ
l
2
+
α
β
)
2
+
4
α
β
Δ
l
2
=
2
α
β
(
1
+
α
β
/
Δ
l
2
)
+
(
1
+
α
β
/
Δ
l
2
)
2
+
4
(
α
β
/
Δ
l
2
)
.
It is clear that when α
β
/
Δ
l
2
→
0, then t
0
→
α
β; moreover it is an increasing function of Δ
l; that is, it has the same monotonicity property with one in original function ∂
L
x
/
∂
t
|
t
=
t
0
=
0. Figure 8 shows the result improved by L
x
′
(
x
,
t
).Figure 8
Results from improved texture measure method under different images.


## 3.3. Threshold Selection for Weakly Textured Points

A method for threshold selection to remove points which are not weakly textured points is needed, if their local maximum of texture strength is beyond this threshold.On the other hand, there is no a priori information that can be used for removing the point which has no weakly textured property, and to illustrate the method for threshold selection, here, let us consider the distribution of weakly textured points detected by the method in Section2.Figure9 shows the weak points detected by WTD and the 3D histogram of their distribution in the image. Here, the image is divided into M
×
N fragments; that is, if I is the image, then I
=
{
R
1
,
R
2
,
…
,
R
M
×
N
}; according to this distribution we find that regions have more concentrated distribution than others which are weakly textured regions. It also indicates that the local maximum texture strength of points distributed in these regions can be used to detect the threshold.Figure 9
3D histogram of weakly textured points distribution.Through the above result, the properties of weakly textured region can be assumed as follows.(i)
The points which are detected by WTD in the region with weakly textured feature have more concentrated distribution than other regions.
(ii)
The mean of local maximum texture strength in the weakly textured region is lower than that in other regions.An important consequence of these properties is that it allows the threshold to vary with different images. We here use the Otsu threshold algorithm to segment the point sets detected by WTD into two classes, that is, the sets belonging to weakly textured region and the sets belonging to other regions. LetT
O be the threshold defined by Otsu threshold algorithm; N
(
R
i
) is the number of the points in fragment R
i (as shown above, the image is divided into M
×
N fragments), and according to property (i), if N
(
R
i
)
≥
T
O, then fragment R
i is selected as the part of weakly textured region which will be used for determining the threshold of texture strength later. On the other hand, when the weakly textured region is determined, then according to property (ii), the threshold T
s can be defined as follows:
(15)
T
s
=
min
⁡
i
(
max
⁡
j
{
t
(
x
j
)
∣
x
j
∈
R
i
}
)
,
hhhhhhhh
{
R
i
∈
I
∣
N
(
R
i
)
≥
T
O
}
,
where t
(
x
) is texture strength which is detected by the local maximum of the derivative over scales at point x
∈
R
i. Since the points in the weakly textured region should be retained as much as possible, we here use max
⁡
j
⁡
{
t
(
x
j
)
∣
x
j
∈
R
i
} as the subthreshold detected in region R
i; on the other hand, there also exist points which are not weakly textured points in some parts of the weakly textured region, so for removing these points the global threshold here can be obtained as min
⁡
i
⁡
(
max
⁡
j
⁡
{
t
(
x
j
)
∣
x
j
∈
R
i
}
).


## 3.4. Composed Algorithm

The mechanisms for weakly textured point detection and fine positioning were proposed, respectively. And they can be used in various ways in point detection and point removing. For the purpose of experiments and validation, we have here integrated these two modules into a composed algorithm, which can be expressed in the following four-step procedure.Stage 1.
Given a constant integerM, which is the number of points needed to be detected by WTD, M can be adjusted according to the size of image. Formulas (2) and (3) are then used to compute the vector in the radial-space {
r
1
,
r
2
,
…
,
r
N
} for each point p
i of image:
(16)
v
S
(
p
i
)
=
{
S
w
-texture
(
p
i
,
r
1
)
,
S
w
-texture
(
p
i
,
r
2
)
,
…
,
hihhhhhh
S
w
-texture
(
p
i
,
r
N
)
}
.Stage 2.
Use the mechanism proposed in Section2 to select the suitable radial r
fit for each point p
i of image I. Take S
w
-texture
(
p
i
,
r
fit
) as the similarity strength of p
i. And arrange p
i of image I in order of decreasing S
w
-texture
(
p
i
,
r
fit
). Then choose the first M points as the candidates of the weakly textured points.Stage 3.
Given a constant integerT, then scale t varies within [
1,2
,
…
,
T
]. Use L
x
′
=
p
(
t
)
·
L
x defined in formula (12) for computing the vector of each point which is obtained from Stage 2:
(17)
v
t
(
p
i
)
=
{
L
grad
(
p
i
,
t
1
)
,
L
grad
(
p
i
,
t
2
)
,
…
,
L
grad
(
p
i
,
t
T
)
}
,
hhhhhhhhhhhhhhhhhhhhhhhhhhhh
t
i
∈
[
1,2
,
…
,
T
]
.
Choose the biggest element from v
t
(
p
i
) as the texture strength of point p
i; that is,
(18)
v
t
_
max
⁡
(
p
i
)
=
max
⁡
t
i
∈
[
1,2
,
…
,
T
]
L
grad
(
p
i
,
t
i
)
.Stage 4.
Using the threshold selection mechanism to detect the thresholdT
s of texture strength and remove the points by T
s, that is, if v
t
_
max
⁡
(
p
i
)
<
T
s, then p
i is the weakly textured point.Figure10 shows the performance of above composed algorithm; it is clear that this algorithm can efficiently extract the weakly textured points, and through the scale-space texture strength concept, the points have strong textureness which can be removed completely.Results from threshold mechanism for different images. (a) Points detected by WTD. (b) Points detected by WTD + threshold mechanism. (c) Regions belong to detected points.
(a)
(b)
(c)


## 4. Sparse Representation for Point Correspondence

In this section, we study the feature matching problem of the weakly textured points detected by the proposed mechanism in the above two sections. Since the resulting feature matches can be used in wide-baseline stereo matching problem, it is important to find a matching algorithm for weakly textured points correspondence. On the other hand, since the point has the feature of weak texture, it is difficult to choose features for distinguishing different weakly textured points. Traditionally, methods of point-matching are based on the Euclidean distance; namely, if the distance between the candidate point and the object point is minimum, then those points are correspondence; moreover, the algorithms such as support vector machine (SVM) [25] and nearest neighbor algorithm [26] are largely dependent on the choice of features. Hence, we here match the feature via sparse representation, within the proposed framework; the precise choice of feature space is no longer critical. In [19], the algorithm used for human face recognition is similar to our method. And the efficacy of sparse representation in solving classification problems has been demonstrated.


### 4.1. Analyze the Feature of Weakly Textured Points

Since features of the same point in two different images are almost equal, the feature of the point in the first image can be thought as lying on the linear subspace composed by all features of weakly textured points in the second image. As proposed in [19], we here use the same hypothesis; that is, the feature from one point lies on a subspace. This is the only prior knowledge about our feature matching algorithm.Given the feature set of pointsS
2
=
[
s
2,1
,
s
2,2
,
…
,
s
2
,
n
2
]
∈
R
m
×
n
2 in the second image, where s
2
,
j denotes feature of point p
j, if p
j exists in the first image, then its feature s
1
,
j will be approximately in the linear span of S
2 associated with object j:
(19)
s
1
,
j
=
α
1
s
2,1
+
α
2
s
2,2
+
⋯
+
α
n
2
s
2
,
n
2
,
where α
i
∈
R, j
=
1,2
,
…
,
n
2. The linear representation s
1
,
j also can be rewritten in terms of S
2 as
(20)
s
1
,
j
=
S
2
x
∈
R
m
.
Since the point p
j existed in the two images, its feature in these two images should be closed enough. Hence, the coefficient vector x could be assumed as x
=
[
0
,
…
,
0
,
α
j
,
0
,
…
,
0
]
T
∈
R
n
2 where its entries are zero except those associated with jth point. And here we should solve the linear equation s
1
,
j
=
S
2
x; here S
2
∈
R
m
×
n
2, and n
2 is the number of the weakly textured points in the second image, and m is the dimension of the features. Here in order to reduce the computational complexity, the dimension of features should be chosen as small as possible; that is, it has n
2
≫
m, so the equation s
1
,
j
=
S
2
x is underdetermined, and its solution is not unique. On the other hand, since the ideal solution x
0 of s
1
,
j
=
S
2
x should be dense, as assumed above. So the denser x
0 is, the easier will it be to determine point p
j in the first image.Through the above analysis, we here seek the sparsest solution tos
1
,
j
=
S
2
x, that is, solving the following optimization problem:
(21)
x
0
=
arg
min
⁡
∥
x
∥
0
subject
to
s
1
,
j
=
S
2
x
,
where ∥
·
∥
0 denotes the l
0-norm, which counts the number of nonzero entries in a vector. However, this problem is NP-hard and even difficult to approximate [27]: there are no more efficient procedures for finding the sparest solution than exhausting all subsets of the entries for x. But in the theory of sparse representation and compressed sensing [28], it is proved that if the solution of l
0-minimization is sparse enough, then it is equal to the solution of the l
1-minimization problem:
(22)
x
0
=
arg
min
⁡
∥
x
∥
1
subject
to
s
1
,
j
=
S
2
x
.We here use a simple example for interpretation of the reason why should we use thel
1-minimization rather than l
2-minimization to get the sparest solution. As shown in Figure 11, the left and right images show the geometry of l
2-minimization algorithm and l
1-minimization algorithm to solve s
1
,
j
=
S
2
x
0 under two-dimensional situation, respectively. According to Figure 11 the solution of l
1-minimization is also the solution of l
0-minimization; however, the one gotten from l
2-minimization does not satisfy l
0-minimization.Figure 11
Geometry of sparse representation withl
2-minimization and l
1-minimization.


### 4.2. Feature Matching Based on Sparse Representation

So far, we have used the simple example for interpreting the sparse representation theory and before we give the algorithm, all the symbols used latter should be defined as follows.I
1: the image having the points which should be matched.
I
2: the image having the reference points for those in image I
1.
{
q
i
}
I
1
,
{
p
i
}
I
2: the weakly textured points sets, which are detected in the I
1, I
2, respectively.
F
(
·
)
:
R
2
→
R
m: feature extraction function as the position of point; that is, it can extract the m-dimension feature for the point.
δ
i
(
·
): R
n
→
R
n: the function that can get a new vector from the vector x
∈
R
n, and the new one has the only nonzero entries in x
∈
R
n which are associated with index i; moreover because the point in image I
1 can only have one corresponding point, so here the new vector gotten from δ
i
(
·
) should have only one nonzero entry.Sparse Representation-Based Feature Matching Algorithm
(
1
)
Input the feature set of reference points in imageI
2.
That is,S
2
=
{
F
(
p
1
)
,
F
(
p
2
)
,
…
,
F
(
p
n
)
}
∈
R
m
×
n
2 which is regarded as the matrix for l
1-minimization problem. And the feature of test point F
(
q
)
q
∈
I
1, which can be regarded as a test sample.
(
2
)
Normalize the columns ofS
2 and F
(
q
) to have unit l
2-norm; here S
-
2 and F
-
(
q
) are the normalized S
2 and F
(
q
), respectively.
(
3
)
Solve the followingl
1-minimization problems:
(23)
x
0
=
arg
min
⁡
∥
x
∥
1
subject
to
F
-
(
q
)
=
S
-
2
x
or(24)
x
0
=
arg
min
⁡
∥
x
∥
1
subject
to
∥
S
-
2
x
-
F
-
(
q
)
∥
2
≤
ε
,
where ifF
-
(
q
) have noise term, and the bounded energy of this noise is less than ε, then we will use the extended l
1-minimization problem [19].
(
4
)
Compute the residualsr
i
(
F
-
(
q
)
)
=
∥
F
-
(
q
)
-
S
-
2
δ
i
(
x
0
)
∥
2 for i
=
1
,
…
,
n.
(
5
)
Output identity(
F
-
(
q
)
)
=
arg
min
⁡
i
r
i
(
F
-
(
q
)
), then the position of corresponding point can be determined by this result.


### 4.3. Feature Extraction for Weakly Textured Point

As above shown, we have proposed the feature matching algorithm for the weakly textured points based on the sparse representation classifier, but there still remains a problem, that is, what feature should be extracted. As assumed above the point feature in imageI
1 should have the sparest solution in the feature space of image I
2; this means that if the feature satisfies this sparsity condition then it can be used for matching weakly textured points, that is, as in [19]: “the choice of features is no longer critical.” On the other hand, this condition is satisfied by the feature of texture points, because these points have their own structure in their neighbor regions, and this feature cannot be represented by other points. However, the weakly textured points might not satisfy this condition, for the reason that these points usually have no obvious characteristics. So, in the experiment part we will use the different descriptors including LBP, random, and downsampled features to investigate their performance to the proposed matching algorithm. Here the random feature can be expressed as [29]
(25)
x
0
=
arg
min
⁡
∥
x
∥
1
subject
to
y
^
=
R
S
x
,
where R
∈
R
d
×
m is a random matrix independently sampled from zero-mean normal distribution; moreover each row of R is normalized to unit length, and y
^
=
R
y
∈
R
d, when d
≪
m; then using this feature can reduce the computation complex, and the polytope geometry as the analysis indicates the following: if the solution x
0 is sparse enough, then it can be correctly recovered by l
1-minimization from any sufficiently large number d of linear measurements y
^
=
R
S
x with the probability:
(26)
d
≥
2
t
log
⁡
(
n
d
)
,
where t is the number of nonzero entries in vector x.For ending this section, we will give the method to decide the validation of the sample. In the real-world situation, when a point is detected in imageI
1 might not be detected in image I
2 it means that the feature of this point could not be described by using only one point feature in image I
2; that is, the nonzero entries of its sparse representation in image I
2 are not concentrated on one subject; in contrary, it has widely spread sparse coefficients among multiple points in image I
2; hence, the sparsity concentration index (SCI) [19] to determine the validation of the sample is as follows:
(27)
SCI
(
x
)
=
k
·
max
⁡
∥
δ
i
(
x
)
∥
1
/
∥
x
∥
1
-
1
k
-
1
∈
[
0,1
]
.
And according to this index then the valid point p can be decided if SCI
(
p
)
≥
τ, where τ
∈
(
0,1
) is a threshold.


## 4.1. Analyze the Feature of Weakly Textured Points

Since features of the same point in two different images are almost equal, the feature of the point in the first image can be thought as lying on the linear subspace composed by all features of weakly textured points in the second image. As proposed in [19], we here use the same hypothesis; that is, the feature from one point lies on a subspace. This is the only prior knowledge about our feature matching algorithm.Given the feature set of pointsS
2
=
[
s
2,1
,
s
2,2
,
…
,
s
2
,
n
2
]
∈
R
m
×
n
2 in the second image, where s
2
,
j denotes feature of point p
j, if p
j exists in the first image, then its feature s
1
,
j will be approximately in the linear span of S
2 associated with object j:
(19)
s
1
,
j
=
α
1
s
2,1
+
α
2
s
2,2
+
⋯
+
α
n
2
s
2
,
n
2
,
where α
i
∈
R, j
=
1,2
,
…
,
n
2. The linear representation s
1
,
j also can be rewritten in terms of S
2 as
(20)
s
1
,
j
=
S
2
x
∈
R
m
.
Since the point p
j existed in the two images, its feature in these two images should be closed enough. Hence, the coefficient vector x could be assumed as x
=
[
0
,
…
,
0
,
α
j
,
0
,
…
,
0
]
T
∈
R
n
2 where its entries are zero except those associated with jth point. And here we should solve the linear equation s
1
,
j
=
S
2
x; here S
2
∈
R
m
×
n
2, and n
2 is the number of the weakly textured points in the second image, and m is the dimension of the features. Here in order to reduce the computational complexity, the dimension of features should be chosen as small as possible; that is, it has n
2
≫
m, so the equation s
1
,
j
=
S
2
x is underdetermined, and its solution is not unique. On the other hand, since the ideal solution x
0 of s
1
,
j
=
S
2
x should be dense, as assumed above. So the denser x
0 is, the easier will it be to determine point p
j in the first image.Through the above analysis, we here seek the sparsest solution tos
1
,
j
=
S
2
x, that is, solving the following optimization problem:
(21)
x
0
=
arg
min
⁡
∥
x
∥
0
subject
to
s
1
,
j
=
S
2
x
,
where ∥
·
∥
0 denotes the l
0-norm, which counts the number of nonzero entries in a vector. However, this problem is NP-hard and even difficult to approximate [27]: there are no more efficient procedures for finding the sparest solution than exhausting all subsets of the entries for x. But in the theory of sparse representation and compressed sensing [28], it is proved that if the solution of l
0-minimization is sparse enough, then it is equal to the solution of the l
1-minimization problem:
(22)
x
0
=
arg
min
⁡
∥
x
∥
1
subject
to
s
1
,
j
=
S
2
x
.We here use a simple example for interpretation of the reason why should we use thel
1-minimization rather than l
2-minimization to get the sparest solution. As shown in Figure 11, the left and right images show the geometry of l
2-minimization algorithm and l
1-minimization algorithm to solve s
1
,
j
=
S
2
x
0 under two-dimensional situation, respectively. According to Figure 11 the solution of l
1-minimization is also the solution of l
0-minimization; however, the one gotten from l
2-minimization does not satisfy l
0-minimization.Figure 11
Geometry of sparse representation withl
2-minimization and l
1-minimization.


## 4.2. Feature Matching Based on Sparse Representation

So far, we have used the simple example for interpreting the sparse representation theory and before we give the algorithm, all the symbols used latter should be defined as follows.I
1: the image having the points which should be matched.
I
2: the image having the reference points for those in image I
1.
{
q
i
}
I
1
,
{
p
i
}
I
2: the weakly textured points sets, which are detected in the I
1, I
2, respectively.
F
(
·
)
:
R
2
→
R
m: feature extraction function as the position of point; that is, it can extract the m-dimension feature for the point.
δ
i
(
·
): R
n
→
R
n: the function that can get a new vector from the vector x
∈
R
n, and the new one has the only nonzero entries in x
∈
R
n which are associated with index i; moreover because the point in image I
1 can only have one corresponding point, so here the new vector gotten from δ
i
(
·
) should have only one nonzero entry.Sparse Representation-Based Feature Matching Algorithm
(
1
)
Input the feature set of reference points in imageI
2.
That is,S
2
=
{
F
(
p
1
)
,
F
(
p
2
)
,
…
,
F
(
p
n
)
}
∈
R
m
×
n
2 which is regarded as the matrix for l
1-minimization problem. And the feature of test point F
(
q
)
q
∈
I
1, which can be regarded as a test sample.
(
2
)
Normalize the columns ofS
2 and F
(
q
) to have unit l
2-norm; here S
-
2 and F
-
(
q
) are the normalized S
2 and F
(
q
), respectively.
(
3
)
Solve the followingl
1-minimization problems:
(23)
x
0
=
arg
min
⁡
∥
x
∥
1
subject
to
F
-
(
q
)
=
S
-
2
x
or(24)
x
0
=
arg
min
⁡
∥
x
∥
1
subject
to
∥
S
-
2
x
-
F
-
(
q
)
∥
2
≤
ε
,
where ifF
-
(
q
) have noise term, and the bounded energy of this noise is less than ε, then we will use the extended l
1-minimization problem [19].
(
4
)
Compute the residualsr
i
(
F
-
(
q
)
)
=
∥
F
-
(
q
)
-
S
-
2
δ
i
(
x
0
)
∥
2 for i
=
1
,
…
,
n.
(
5
)
Output identity(
F
-
(
q
)
)
=
arg
min
⁡
i
r
i
(
F
-
(
q
)
), then the position of corresponding point can be determined by this result.


## 4.3. Feature Extraction for Weakly Textured Point

As above shown, we have proposed the feature matching algorithm for the weakly textured points based on the sparse representation classifier, but there still remains a problem, that is, what feature should be extracted. As assumed above the point feature in imageI
1 should have the sparest solution in the feature space of image I
2; this means that if the feature satisfies this sparsity condition then it can be used for matching weakly textured points, that is, as in [19]: “the choice of features is no longer critical.” On the other hand, this condition is satisfied by the feature of texture points, because these points have their own structure in their neighbor regions, and this feature cannot be represented by other points. However, the weakly textured points might not satisfy this condition, for the reason that these points usually have no obvious characteristics. So, in the experiment part we will use the different descriptors including LBP, random, and downsampled features to investigate their performance to the proposed matching algorithm. Here the random feature can be expressed as [29]
(25)
x
0
=
arg
min
⁡
∥
x
∥
1
subject
to
y
^
=
R
S
x
,
where R
∈
R
d
×
m is a random matrix independently sampled from zero-mean normal distribution; moreover each row of R is normalized to unit length, and y
^
=
R
y
∈
R
d, when d
≪
m; then using this feature can reduce the computation complex, and the polytope geometry as the analysis indicates the following: if the solution x
0 is sparse enough, then it can be correctly recovered by l
1-minimization from any sufficiently large number d of linear measurements y
^
=
R
S
x with the probability:
(26)
d
≥
2
t
log
⁡
(
n
d
)
,
where t is the number of nonzero entries in vector x.For ending this section, we will give the method to decide the validation of the sample. In the real-world situation, when a point is detected in imageI
1 might not be detected in image I
2 it means that the feature of this point could not be described by using only one point feature in image I
2; that is, the nonzero entries of its sparse representation in image I
2 are not concentrated on one subject; in contrary, it has widely spread sparse coefficients among multiple points in image I
2; hence, the sparsity concentration index (SCI) [19] to determine the validation of the sample is as follows:
(27)
SCI
(
x
)
=
k
·
max
⁡
∥
δ
i
(
x
)
∥
1
/
∥
x
∥
1
-
1
k
-
1
∈
[
0,1
]
.
And according to this index then the valid point p can be decided if SCI
(
p
)
≥
τ, where τ
∈
(
0,1
) is a threshold.


## 5. Experiment Results

In this section, we present experiments on publicly available databases for weakly textured points detecting and the feature matching algorithm based on sparse representation, and the efficacy of these two algorithms can be demonstrated by these experiments. The experiments can be divided into three parts, that is, points detection, feature matching, and promoting the quasi-dense matching algorithm [20]; in the first part we will examine the performance of the detection algorithm, comparing with different images in various situations and comparing to several popular feature detectors (as shown in Sections 5.1 and 5.2). In the second part we will examine feature matching algorithm, comparing performance across various features spaces and feature dimensions and comparing to several popular classifiers in Section 5.3. Finally, we will demonstrate the proposed method for improving the quasi-dense matching algorithm in Section 5.4.


### 5.1. WTD with Image Perturbations

We here measure the WTD efficiency for weakly textured points detection under images with different objects and the robustness across with the same object has different backgrounds. The data we choose here include 200 images from Caltech human faces set, 102 images from category flower dataset, and 100 images from human model. And first we will compare our detector with three classical detectors in weakly textured points detection, namely, Harris-affine, SIFT, and SURF. For measuring the performance here we use the proportion between the number of detected points (Figure12) on the objects (OP) and total number of detected points (TP) and set the radial of WTD from R
=
2 to R
=
32. Table 1 compares WTD to the other three detectors.Table 1
Performance under different objects.
Test images
Harris-affine
SIFT
SURF
WTD
OP/TP
OP
OP/TP
OP
OP/TP
OP
OP/TP
OP
Human face
0.1187
28.0000
0.05464
32.1429
0.1255
46.4286
0.5841
85.2857
Flower
0.1837
28.2857
0.0983
26.1428
0.2387
50.5714
0.7253
107.1429
Human model
0.1315
22.8571
0.0122
5.0000
0.1629
36.2857
0.8240
113.0000
Average
0.1446
26.38
0.05504
21.09523
0.1757
44.4285
0.7111
101.8095Figure 12
Examples of detected points distributed on different objects with different detectors.Based on the results on the data, we draw the following conclusion.(1)
For all data, the performances of WTD consistently exceed the other three detectors in weakly textured detection. It means that if the object has large region of weak texture, then WTD can detect more points in this object than other detectors.
(2)
The results obtained by WTD and classical detectors are complementary; namely, the points which are not detected by classical detectors can be detected by WTD, so if points detected by those classical detectors are not enough for the stereo reconstruction, then WTD can be used as a complement.As a second set of this experiment, the robustness of WTD for the same object with three different texture backgrounds is tested. In order to demonstrate the performance of WTD, we here use artificial backgrounds as the extreme situations, namely, random background (RB), forest background (FB), and texture background (TB), respectively. And the parameters of WTD are the same as in the above experiment. Table2 and Figure 13 show the performance of WTD comparing to classical detectors.Table 2
Performance under different objects with different backgrounds.
Test images
Human face
Flower
Human body
Average
Harris-affine
RB
0.1242
0.0758
0.0380
0.0794
FB
0.1111
0.0765
0.0234
0.0703
TB
0.1228
0.0556
0.0208
0.0664
SIFT
RB
0.0778
0.0059
0.0009
0.0282
FB
0.0281
0.002
0.0042
0.0114
TB
0.4242
0.0136
0.0167
0.1516
SURF
RB
0.1925
0.1843
0.2135
0.1968
FB
0.2131
0.1808
0.1566
0.1835
TB
0.2157
0.1767
0.0948
0.1624
WTF
RB
0.8750
1
1
0.9583
FB
0.9123
1
1
0.9708
TB
0.8361
1
1
0.9454Figure 13
Performance of WTD on different backgrounds.It is clear that the points detected by WTD are almost concentrated on the object with weak texture (human model) no matter what texture background takes (the WTP/TP close to 1). On the other hand, this property of WTD is contrary to classical detectors, whose detected points are almost concentrated on the texture objects, and it is once again demonstrating the relationship between WTD and classical detectors as the above experiment.


### 5.2. Performance under Varying Blur, Lighting Change, Rotating, and Viewpoint Change

For this experiment, we test the repeatability of four detectors under different photometric and geometric transformations, as the protocol suggested in [13]. Test images sets and results are shown in Figures 14–17 and each set changes in 6 levels. Because of space constraints, we here only give three of the six images in each type of transformation, that is, first, third, and sixth. Each figure presents the repetition rate which includes three parts, namely, total number of matched points, the number of matched points on the objects, and the matching score on the objects. The range of radius scale is set from R
=
2 to R
=
30, and the repetition rate here we just use the region matches, and the matching conditions follow as recommended in [22]. The matching score S
i, here, is given by the proportion of correspondences with detected regions on the objects for all correspondences in the test image; that is,
(28)
S
i
=
Total
number
of
matches
Total
number
of
detected
regions
=
N
i
N
,
hhhhhhhhhhhhhhhhhhhhhh
(
i
=
1,2
,
…
,
M
)
.Blur for image. (a) Total number of matched points for image blurs. (b) Number of matched points on the objects. (c) Matching score on the objects.
(a)
(b)
(c)Lighting changes for image. (a) Total number of matched points for lighting change. (b) Number of matched points on the objects. (c) Matching score on the objects.
(a)
(b)
(c)Rotation for image. (a) Total number of matched points for rotation. (b) Number of matched points on the objects. (c) Matching score on the objects.
(a)
(b)
(c)Viewpoint change for image. (a) Total number of matched points for viewpoint change. (b) Number of matched points on the objects. (c) Matching score on the objects.
(a)
(b)
(c)


#### 5.2.1. Blur

Figure14 shows the results detected by four detectors undergoing increasing amounts of image blur, and we here use the Gaussian kernel to blur the image, and the scale parameter t (scale selection) is set as t
=
0,10
,
…
,
60; according to the results of all detectors, the number of matching points declined with the blur increasing; on the one hand, the reason for classical detectors is the image texture reduced by image blur. On the other hand, the number of match points detectors by our detector should increase with the blur, but in fact the threshold selection mechanism discussed in the previous section would get the small threshold because the blur causes the number of candidate regions increasing, so according to formula (15), the threshold will become smaller than before; hence the number of points detected by WTD will decline.


#### 5.2.2. Lighting Changes

Figure15 shows the results for lighting changes with four different detectors. From this result we can find the following: (a) the total number of match points gotten by WTD is lowest and (b) the match points on the object (human face) are higher than other detectors. This is caused by following reasons.(1)
The background of image chosen by us is clatter, so the total number of match points chosen by classical detectors is higher than WTD.
(2)
When the intensity decreases, then the texture of background will increase, and the texture in the object is also increased with light intensity decreasing, but it is slower than the increase in the background; hence, the number of match points on the object by WTD is staying close to its mean value.
(3)
The points detected by WTD are almost concentrated on the object, so its match score is large than others.


#### 5.2.3. Rotation

Figure16 shows the performance for image rotation; the number of match points on the object detected by WTD is not stable with the image rotation. This is because the object scale here will vary with the rotating process. And the same radial (see Section 2) used to measure the same weakly textured point in these images will get the different values. On the other hand, the backgrounds of these images are also textureless, and if the scale changed the threshold for reducing the texture points will also change; hence, points detected by WTD will concentrate on the background. Although being in such serious situation, the match score of WTD is also higher than other detectors.


#### 5.2.4. Viewpoint Changes

Figure17 shows the performance for viewpoint changes. It is clear that when viewpoint changes the matching score of WTD is always close to 1. This implicates that the matching points gotten from WTD are almost concentrating on the object with the viewpoint changes in 1
5
∘ degree limitation.


### 5.3. Feature Matching Algorithm Experiment

In this part, we will test the performance of matching algorithm based on sparse representation with the detected weakly textured points. We here compare performance across various feature spaces and feature dimensions with two popular classifiers, namely, linear SVM andl
2
-min. Moreover, we will also test our matching algorithm under random pixel corruption and random block occlusion, respectively.


#### 5.3.1. Sparse Representation Based Weakly Textured Point Matching

We match 150 weakly textured points detected by WTD in each image as shown in Figure18. Here we only test the matching algorithm under the WTD, and we use conventional features LBP (local binary pattern) and two unconventional features: random and downsampled region features. The window size of LBP is set to be 30
×
30 pixels, and we compute the matching rate with the feature space dimensions 10
,
20
,
…
,
60. The dimension of random feature space discussed in the previous section is set the same as LBP, namely, the random matrix R
d
×
60
(
d
=
10,20
,
…
,
60
); finally the window size of downsampled feature is set to be 30 × 30 with dimensions 60, 45, 30, and 12. Those numbers correspond to downsampling ratios of 1
/
15, 1
/
20, 1
/
30, and 1
/
75, respectively. Figure 18 shows the match performance for the various features, in conjunction with three different algorithms: SRM, l
2
-min, and SVM.Figure 18
Matching rate for various feature transformations.Figure18 also shows results under LBP descriptor with 40 dimensions. The algorithm returns enough matched points on the low texture region that lets us get more sufficient points than traditional sparse matching on these area.Based on the results on different feature spaces, the following conclusion can be drawn.(1)
Here we use the variance of feature dimensions to measure the stability of matching rate on different feature spaces. Table3 shows the variances of matching rate for SRM, l
2
-min, and SVM. It is clear that SRM is more stable than others for feature dimensions on the LBP and random spaces.
(2)
The biggest matching rate of SRM exceeds the best performances of others on the LBP and downsample spaces. More specifically, the best performance for SRM on the LBP is 80.86%, compared to 71.35% forl
2
-min and 69.70% for SVM. The best rate for SRM on the downsample is 80.38%, compared to 59.64% for l
2
-min and 55.97% for SVM.
(3)
The results on the LBP and random spaces suggest that when the feature dimension is 40, it is sufficed for sparse recovery. Moreover when the dimensions are beyond 40, the performances on these two feature spaces will converge.Table 3
Variances of matching rate.
Algorithm
LBP
Downsample
Random
SRM
1.15
×
1
0
-
2
9.8
×
1
0
-
3
7.9540
×
1
0
-
4
l
2-min
⁡
2.47
×
1
0
-
2
7.2
×
1
0
-
3
5.6
×
1
0
-
3
SVM
2.63
×
1
0
-
2
4.29
×
1
0
-
2
2.63
×
1
0
-
2


#### 5.3.2. Matching despite Random Pixel Corruption

In this experiment, we test the robustness of SRM under the pixel of description region occluded by random noise. We use the extendedl
1-minimization problem [19] at the third step of SRM for solving this occlusion problem. Here the error tolerance ε is set to be the bounded energy of the random noise. In order to eliminate the influence caused by WTD, we use the random noise to corrupt the located region in which the feature is extracted (see Figure 19). On the other hand, since there are no efficient descriptions for weakly textured point, the description we used is LBP, because it has the best performance as shown above. For demonstrating the performance of SRM, we compare it to the following algorithms: l
min
⁡
2
+
PCA, l
min
⁡
2
+
LNMF, and l
min
⁡
2
+
ICA, respectively. Here PCA, LNMP, and ICA are principal component analysis, local nonnegative matrix factorization (LNMF), and independent component analysis (ICA), respectively. These algorithm are used for feature preprocessing and the l
2
-min we used here because it has the second highest matching rate in the above experiment. According to the experiment result, it can be seen that when the corruption is up to 25 percent the number of matching points with each algorithm will drop to zero. So, here we only show the result with corruption from 0 percent to 25 percent. According to the performance of SRM and its three competitors, we see that SRM outperforms others; namely, from 5 percent up to 20 percent occlusion, the number of matching weakly textured points are higher than others. At 10 percent corruption, the highest matching number of others is 40 points, while the one gotten by SRM 80 points. Even at 15 percent occlusion, the matching number is still 60 points. Clearly, the SRM can ensure to tolerate under the corruption less than 25 percent for matching the weakly textured points. On the other hand, the matching points numbers gotten by l
min
⁡
2
+
LNMF and l
min
⁡
2
+
ICA are obviously less than SRM and l
min
⁡
2
+
PCA; it has been suggested that both LNMF and ICA are not suitable for the preprocessing of weakly textured feature.Figure 19
Recognition under random corruption.


#### 5.3.3. Matching despite Random Block Occlusion

The final part of the experiment here is to simulate various levels of contiguous occlusion, from 0 percent to 40 percent, by replacing a randomly located square block of each feature region with the gray-lever at zero, and the reason why we choose zero gray-lever block is that the matching points are weakly textured point, so if we choose the texture block here, the characteristic of these points will be replaced by the features in this texture block. And the region here is the same as the discussion in the above experiment (see Figure20). The location of occlusion is randomly chosen for each image and is unknown to the computer. The results got from SRM and l
min
⁡
2
+
PCA are still better than others. Again, the above implication is also true for this case. Despite the fact that the performances of SRM and l
min
⁡
2
+
PCA are closed, it is clear that SRM outperforms l
min
⁡
2
+
PCA. For example, at 20 percent occlusion, SRM achieves 109 points; it is higher than l
min
⁡
2
+
PCA’s 98 points. On the other hand, the reason why the number of matching points is not decreased to zero when occlusion increases to 40 percent is that the located square block we used here is the zero gray-lever images. And the matching points also have weakly textured characteristic, so it will not be much affected by this square block.Figure 20
Recognition under varying level of contiguous occlusion.


### 5.4. Improved Quasi-Dense Matching

In this section, we use WTD to promote the quasi-dense matching algorithm [20]. The quasi-dense matching algorithm starts from a set of sparse seed matches which were usually obtained by classical detectors, then propagates to the neighboring pixels by the best-first strategy, and finally produces a quasi-dense disparity map. Since most initial sparse seed matches distribute in the strong texture regions, it nearly has no seed matches in the textureless areas; furthermore if the matches got from propagating step in these areas are wrong, gross reconstruction errors will occur, so here we use the proposed approach to get the initial sparse seed matches in the large textureless areas.The original algorithm is independently implemented for comparison on the same image pairs. The corresponding-point sets obtained by WTD and traditional quasi-dense matching algorithm are shown in Figure21. One can verify the effectiveness of our implementation by corresponding quality measures which are given in Table 4.Table 4
Comparison between original dense matching and improved one under different circumstances.
Change
Algorithm
#corresponding-point on untex
Lighting
Quasi + ours
845
Quasi
414
Image scale
Quasi + ours
490
Quasi
210
Camera angle
Quasi + ours
676
Quasi
351Results from improved dense matching and original one under different circumstances. Top row: corresponding-points matched with lighting changes. Middle row: corresponding-points matched with scale changes. Bottom row: corresponding-points matched with camera angle changes. (a) Corresponding results from improved quasi-dense matching algorithm. (b) Corresponding results from original quasi-dense matching algorithm.
(a)
(b)Our algorithm is evaluated on the changes of lighting, scale, and camera angle, respectively, and the results demonstrate that the algorithm performs particularly better on the large textureless object surface than the original one (as shown in Figure21).


## 5.1. WTD with Image Perturbations

We here measure the WTD efficiency for weakly textured points detection under images with different objects and the robustness across with the same object has different backgrounds. The data we choose here include 200 images from Caltech human faces set, 102 images from category flower dataset, and 100 images from human model. And first we will compare our detector with three classical detectors in weakly textured points detection, namely, Harris-affine, SIFT, and SURF. For measuring the performance here we use the proportion between the number of detected points (Figure12) on the objects (OP) and total number of detected points (TP) and set the radial of WTD from R
=
2 to R
=
32. Table 1 compares WTD to the other three detectors.Table 1
Performance under different objects.
Test images
Harris-affine
SIFT
SURF
WTD
OP/TP
OP
OP/TP
OP
OP/TP
OP
OP/TP
OP
Human face
0.1187
28.0000
0.05464
32.1429
0.1255
46.4286
0.5841
85.2857
Flower
0.1837
28.2857
0.0983
26.1428
0.2387
50.5714
0.7253
107.1429
Human model
0.1315
22.8571
0.0122
5.0000
0.1629
36.2857
0.8240
113.0000
Average
0.1446
26.38
0.05504
21.09523
0.1757
44.4285
0.7111
101.8095Figure 12
Examples of detected points distributed on different objects with different detectors.Based on the results on the data, we draw the following conclusion.(1)
For all data, the performances of WTD consistently exceed the other three detectors in weakly textured detection. It means that if the object has large region of weak texture, then WTD can detect more points in this object than other detectors.
(2)
The results obtained by WTD and classical detectors are complementary; namely, the points which are not detected by classical detectors can be detected by WTD, so if points detected by those classical detectors are not enough for the stereo reconstruction, then WTD can be used as a complement.As a second set of this experiment, the robustness of WTD for the same object with three different texture backgrounds is tested. In order to demonstrate the performance of WTD, we here use artificial backgrounds as the extreme situations, namely, random background (RB), forest background (FB), and texture background (TB), respectively. And the parameters of WTD are the same as in the above experiment. Table2 and Figure 13 show the performance of WTD comparing to classical detectors.Table 2
Performance under different objects with different backgrounds.
Test images
Human face
Flower
Human body
Average
Harris-affine
RB
0.1242
0.0758
0.0380
0.0794
FB
0.1111
0.0765
0.0234
0.0703
TB
0.1228
0.0556
0.0208
0.0664
SIFT
RB
0.0778
0.0059
0.0009
0.0282
FB
0.0281
0.002
0.0042
0.0114
TB
0.4242
0.0136
0.0167
0.1516
SURF
RB
0.1925
0.1843
0.2135
0.1968
FB
0.2131
0.1808
0.1566
0.1835
TB
0.2157
0.1767
0.0948
0.1624
WTF
RB
0.8750
1
1
0.9583
FB
0.9123
1
1
0.9708
TB
0.8361
1
1
0.9454Figure 13
Performance of WTD on different backgrounds.It is clear that the points detected by WTD are almost concentrated on the object with weak texture (human model) no matter what texture background takes (the WTP/TP close to 1). On the other hand, this property of WTD is contrary to classical detectors, whose detected points are almost concentrated on the texture objects, and it is once again demonstrating the relationship between WTD and classical detectors as the above experiment.


## 5.2. Performance under Varying Blur, Lighting Change, Rotating, and Viewpoint Change

For this experiment, we test the repeatability of four detectors under different photometric and geometric transformations, as the protocol suggested in [13]. Test images sets and results are shown in Figures 14–17 and each set changes in 6 levels. Because of space constraints, we here only give three of the six images in each type of transformation, that is, first, third, and sixth. Each figure presents the repetition rate which includes three parts, namely, total number of matched points, the number of matched points on the objects, and the matching score on the objects. The range of radius scale is set from R
=
2 to R
=
30, and the repetition rate here we just use the region matches, and the matching conditions follow as recommended in [22]. The matching score S
i, here, is given by the proportion of correspondences with detected regions on the objects for all correspondences in the test image; that is,
(28)
S
i
=
Total
number
of
matches
Total
number
of
detected
regions
=
N
i
N
,
hhhhhhhhhhhhhhhhhhhhhh
(
i
=
1,2
,
…
,
M
)
.Blur for image. (a) Total number of matched points for image blurs. (b) Number of matched points on the objects. (c) Matching score on the objects.
(a)
(b)
(c)Lighting changes for image. (a) Total number of matched points for lighting change. (b) Number of matched points on the objects. (c) Matching score on the objects.
(a)
(b)
(c)Rotation for image. (a) Total number of matched points for rotation. (b) Number of matched points on the objects. (c) Matching score on the objects.
(a)
(b)
(c)Viewpoint change for image. (a) Total number of matched points for viewpoint change. (b) Number of matched points on the objects. (c) Matching score on the objects.
(a)
(b)
(c)


### 5.2.1. Blur

Figure14 shows the results detected by four detectors undergoing increasing amounts of image blur, and we here use the Gaussian kernel to blur the image, and the scale parameter t (scale selection) is set as t
=
0,10
,
…
,
60; according to the results of all detectors, the number of matching points declined with the blur increasing; on the one hand, the reason for classical detectors is the image texture reduced by image blur. On the other hand, the number of match points detectors by our detector should increase with the blur, but in fact the threshold selection mechanism discussed in the previous section would get the small threshold because the blur causes the number of candidate regions increasing, so according to formula (15), the threshold will become smaller than before; hence the number of points detected by WTD will decline.


### 5.2.2. Lighting Changes

Figure15 shows the results for lighting changes with four different detectors. From this result we can find the following: (a) the total number of match points gotten by WTD is lowest and (b) the match points on the object (human face) are higher than other detectors. This is caused by following reasons.(1)
The background of image chosen by us is clatter, so the total number of match points chosen by classical detectors is higher than WTD.
(2)
When the intensity decreases, then the texture of background will increase, and the texture in the object is also increased with light intensity decreasing, but it is slower than the increase in the background; hence, the number of match points on the object by WTD is staying close to its mean value.
(3)
The points detected by WTD are almost concentrated on the object, so its match score is large than others.


### 5.2.3. Rotation

Figure16 shows the performance for image rotation; the number of match points on the object detected by WTD is not stable with the image rotation. This is because the object scale here will vary with the rotating process. And the same radial (see Section 2) used to measure the same weakly textured point in these images will get the different values. On the other hand, the backgrounds of these images are also textureless, and if the scale changed the threshold for reducing the texture points will also change; hence, points detected by WTD will concentrate on the background. Although being in such serious situation, the match score of WTD is also higher than other detectors.


### 5.2.4. Viewpoint Changes

Figure17 shows the performance for viewpoint changes. It is clear that when viewpoint changes the matching score of WTD is always close to 1. This implicates that the matching points gotten from WTD are almost concentrating on the object with the viewpoint changes in 1
5
∘ degree limitation.


## 5.2.1. Blur

Figure14 shows the results detected by four detectors undergoing increasing amounts of image blur, and we here use the Gaussian kernel to blur the image, and the scale parameter t (scale selection) is set as t
=
0,10
,
…
,
60; according to the results of all detectors, the number of matching points declined with the blur increasing; on the one hand, the reason for classical detectors is the image texture reduced by image blur. On the other hand, the number of match points detectors by our detector should increase with the blur, but in fact the threshold selection mechanism discussed in the previous section would get the small threshold because the blur causes the number of candidate regions increasing, so according to formula (15), the threshold will become smaller than before; hence the number of points detected by WTD will decline.


## 5.2.2. Lighting Changes

Figure15 shows the results for lighting changes with four different detectors. From this result we can find the following: (a) the total number of match points gotten by WTD is lowest and (b) the match points on the object (human face) are higher than other detectors. This is caused by following reasons.(1)
The background of image chosen by us is clatter, so the total number of match points chosen by classical detectors is higher than WTD.
(2)
When the intensity decreases, then the texture of background will increase, and the texture in the object is also increased with light intensity decreasing, but it is slower than the increase in the background; hence, the number of match points on the object by WTD is staying close to its mean value.
(3)
The points detected by WTD are almost concentrated on the object, so its match score is large than others.


## 5.2.3. Rotation

Figure16 shows the performance for image rotation; the number of match points on the object detected by WTD is not stable with the image rotation. This is because the object scale here will vary with the rotating process. And the same radial (see Section 2) used to measure the same weakly textured point in these images will get the different values. On the other hand, the backgrounds of these images are also textureless, and if the scale changed the threshold for reducing the texture points will also change; hence, points detected by WTD will concentrate on the background. Although being in such serious situation, the match score of WTD is also higher than other detectors.


## 5.2.4. Viewpoint Changes

Figure17 shows the performance for viewpoint changes. It is clear that when viewpoint changes the matching score of WTD is always close to 1. This implicates that the matching points gotten from WTD are almost concentrating on the object with the viewpoint changes in 1
5
∘ degree limitation.


## 5.3. Feature Matching Algorithm Experiment

In this part, we will test the performance of matching algorithm based on sparse representation with the detected weakly textured points. We here compare performance across various feature spaces and feature dimensions with two popular classifiers, namely, linear SVM andl
2
-min. Moreover, we will also test our matching algorithm under random pixel corruption and random block occlusion, respectively.


### 5.3.1. Sparse Representation Based Weakly Textured Point Matching

We match 150 weakly textured points detected by WTD in each image as shown in Figure18. Here we only test the matching algorithm under the WTD, and we use conventional features LBP (local binary pattern) and two unconventional features: random and downsampled region features. The window size of LBP is set to be 30
×
30 pixels, and we compute the matching rate with the feature space dimensions 10
,
20
,
…
,
60. The dimension of random feature space discussed in the previous section is set the same as LBP, namely, the random matrix R
d
×
60
(
d
=
10,20
,
…
,
60
); finally the window size of downsampled feature is set to be 30 × 30 with dimensions 60, 45, 30, and 12. Those numbers correspond to downsampling ratios of 1
/
15, 1
/
20, 1
/
30, and 1
/
75, respectively. Figure 18 shows the match performance for the various features, in conjunction with three different algorithms: SRM, l
2
-min, and SVM.Figure 18
Matching rate for various feature transformations.Figure18 also shows results under LBP descriptor with 40 dimensions. The algorithm returns enough matched points on the low texture region that lets us get more sufficient points than traditional sparse matching on these area.Based on the results on different feature spaces, the following conclusion can be drawn.(1)
Here we use the variance of feature dimensions to measure the stability of matching rate on different feature spaces. Table3 shows the variances of matching rate for SRM, l
2
-min, and SVM. It is clear that SRM is more stable than others for feature dimensions on the LBP and random spaces.
(2)
The biggest matching rate of SRM exceeds the best performances of others on the LBP and downsample spaces. More specifically, the best performance for SRM on the LBP is 80.86%, compared to 71.35% forl
2
-min and 69.70% for SVM. The best rate for SRM on the downsample is 80.38%, compared to 59.64% for l
2
-min and 55.97% for SVM.
(3)
The results on the LBP and random spaces suggest that when the feature dimension is 40, it is sufficed for sparse recovery. Moreover when the dimensions are beyond 40, the performances on these two feature spaces will converge.Table 3
Variances of matching rate.
Algorithm
LBP
Downsample
Random
SRM
1.15
×
1
0
-
2
9.8
×
1
0
-
3
7.9540
×
1
0
-
4
l
2-min
⁡
2.47
×
1
0
-
2
7.2
×
1
0
-
3
5.6
×
1
0
-
3
SVM
2.63
×
1
0
-
2
4.29
×
1
0
-
2
2.63
×
1
0
-
2


### 5.3.2. Matching despite Random Pixel Corruption

In this experiment, we test the robustness of SRM under the pixel of description region occluded by random noise. We use the extendedl
1-minimization problem [19] at the third step of SRM for solving this occlusion problem. Here the error tolerance ε is set to be the bounded energy of the random noise. In order to eliminate the influence caused by WTD, we use the random noise to corrupt the located region in which the feature is extracted (see Figure 19). On the other hand, since there are no efficient descriptions for weakly textured point, the description we used is LBP, because it has the best performance as shown above. For demonstrating the performance of SRM, we compare it to the following algorithms: l
min
⁡
2
+
PCA, l
min
⁡
2
+
LNMF, and l
min
⁡
2
+
ICA, respectively. Here PCA, LNMP, and ICA are principal component analysis, local nonnegative matrix factorization (LNMF), and independent component analysis (ICA), respectively. These algorithm are used for feature preprocessing and the l
2
-min we used here because it has the second highest matching rate in the above experiment. According to the experiment result, it can be seen that when the corruption is up to 25 percent the number of matching points with each algorithm will drop to zero. So, here we only show the result with corruption from 0 percent to 25 percent. According to the performance of SRM and its three competitors, we see that SRM outperforms others; namely, from 5 percent up to 20 percent occlusion, the number of matching weakly textured points are higher than others. At 10 percent corruption, the highest matching number of others is 40 points, while the one gotten by SRM 80 points. Even at 15 percent occlusion, the matching number is still 60 points. Clearly, the SRM can ensure to tolerate under the corruption less than 25 percent for matching the weakly textured points. On the other hand, the matching points numbers gotten by l
min
⁡
2
+
LNMF and l
min
⁡
2
+
ICA are obviously less than SRM and l
min
⁡
2
+
PCA; it has been suggested that both LNMF and ICA are not suitable for the preprocessing of weakly textured feature.Figure 19
Recognition under random corruption.


### 5.3.3. Matching despite Random Block Occlusion

The final part of the experiment here is to simulate various levels of contiguous occlusion, from 0 percent to 40 percent, by replacing a randomly located square block of each feature region with the gray-lever at zero, and the reason why we choose zero gray-lever block is that the matching points are weakly textured point, so if we choose the texture block here, the characteristic of these points will be replaced by the features in this texture block. And the region here is the same as the discussion in the above experiment (see Figure20). The location of occlusion is randomly chosen for each image and is unknown to the computer. The results got from SRM and l
min
⁡
2
+
PCA are still better than others. Again, the above implication is also true for this case. Despite the fact that the performances of SRM and l
min
⁡
2
+
PCA are closed, it is clear that SRM outperforms l
min
⁡
2
+
PCA. For example, at 20 percent occlusion, SRM achieves 109 points; it is higher than l
min
⁡
2
+
PCA’s 98 points. On the other hand, the reason why the number of matching points is not decreased to zero when occlusion increases to 40 percent is that the located square block we used here is the zero gray-lever images. And the matching points also have weakly textured characteristic, so it will not be much affected by this square block.Figure 20
Recognition under varying level of contiguous occlusion.


## 5.3.1. Sparse Representation Based Weakly Textured Point Matching

We match 150 weakly textured points detected by WTD in each image as shown in Figure18. Here we only test the matching algorithm under the WTD, and we use conventional features LBP (local binary pattern) and two unconventional features: random and downsampled region features. The window size of LBP is set to be 30
×
30 pixels, and we compute the matching rate with the feature space dimensions 10
,
20
,
…
,
60. The dimension of random feature space discussed in the previous section is set the same as LBP, namely, the random matrix R
d
×
60
(
d
=
10,20
,
…
,
60
); finally the window size of downsampled feature is set to be 30 × 30 with dimensions 60, 45, 30, and 12. Those numbers correspond to downsampling ratios of 1
/
15, 1
/
20, 1
/
30, and 1
/
75, respectively. Figure 18 shows the match performance for the various features, in conjunction with three different algorithms: SRM, l
2
-min, and SVM.Figure 18
Matching rate for various feature transformations.Figure18 also shows results under LBP descriptor with 40 dimensions. The algorithm returns enough matched points on the low texture region that lets us get more sufficient points than traditional sparse matching on these area.Based on the results on different feature spaces, the following conclusion can be drawn.(1)
Here we use the variance of feature dimensions to measure the stability of matching rate on different feature spaces. Table3 shows the variances of matching rate for SRM, l
2
-min, and SVM. It is clear that SRM is more stable than others for feature dimensions on the LBP and random spaces.
(2)
The biggest matching rate of SRM exceeds the best performances of others on the LBP and downsample spaces. More specifically, the best performance for SRM on the LBP is 80.86%, compared to 71.35% forl
2
-min and 69.70% for SVM. The best rate for SRM on the downsample is 80.38%, compared to 59.64% for l
2
-min and 55.97% for SVM.
(3)
The results on the LBP and random spaces suggest that when the feature dimension is 40, it is sufficed for sparse recovery. Moreover when the dimensions are beyond 40, the performances on these two feature spaces will converge.Table 3
Variances of matching rate.
Algorithm
LBP
Downsample
Random
SRM
1.15
×
1
0
-
2
9.8
×
1
0
-
3
7.9540
×
1
0
-
4
l
2-min
⁡
2.47
×
1
0
-
2
7.2
×
1
0
-
3
5.6
×
1
0
-
3
SVM
2.63
×
1
0
-
2
4.29
×
1
0
-
2
2.63
×
1
0
-
2


## 5.3.2. Matching despite Random Pixel Corruption

In this experiment, we test the robustness of SRM under the pixel of description region occluded by random noise. We use the extendedl
1-minimization problem [19] at the third step of SRM for solving this occlusion problem. Here the error tolerance ε is set to be the bounded energy of the random noise. In order to eliminate the influence caused by WTD, we use the random noise to corrupt the located region in which the feature is extracted (see Figure 19). On the other hand, since there are no efficient descriptions for weakly textured point, the description we used is LBP, because it has the best performance as shown above. For demonstrating the performance of SRM, we compare it to the following algorithms: l
min
⁡
2
+
PCA, l
min
⁡
2
+
LNMF, and l
min
⁡
2
+
ICA, respectively. Here PCA, LNMP, and ICA are principal component analysis, local nonnegative matrix factorization (LNMF), and independent component analysis (ICA), respectively. These algorithm are used for feature preprocessing and the l
2
-min we used here because it has the second highest matching rate in the above experiment. According to the experiment result, it can be seen that when the corruption is up to 25 percent the number of matching points with each algorithm will drop to zero. So, here we only show the result with corruption from 0 percent to 25 percent. According to the performance of SRM and its three competitors, we see that SRM outperforms others; namely, from 5 percent up to 20 percent occlusion, the number of matching weakly textured points are higher than others. At 10 percent corruption, the highest matching number of others is 40 points, while the one gotten by SRM 80 points. Even at 15 percent occlusion, the matching number is still 60 points. Clearly, the SRM can ensure to tolerate under the corruption less than 25 percent for matching the weakly textured points. On the other hand, the matching points numbers gotten by l
min
⁡
2
+
LNMF and l
min
⁡
2
+
ICA are obviously less than SRM and l
min
⁡
2
+
PCA; it has been suggested that both LNMF and ICA are not suitable for the preprocessing of weakly textured feature.Figure 19
Recognition under random corruption.


## 5.3.3. Matching despite Random Block Occlusion

The final part of the experiment here is to simulate various levels of contiguous occlusion, from 0 percent to 40 percent, by replacing a randomly located square block of each feature region with the gray-lever at zero, and the reason why we choose zero gray-lever block is that the matching points are weakly textured point, so if we choose the texture block here, the characteristic of these points will be replaced by the features in this texture block. And the region here is the same as the discussion in the above experiment (see Figure20). The location of occlusion is randomly chosen for each image and is unknown to the computer. The results got from SRM and l
min
⁡
2
+
PCA are still better than others. Again, the above implication is also true for this case. Despite the fact that the performances of SRM and l
min
⁡
2
+
PCA are closed, it is clear that SRM outperforms l
min
⁡
2
+
PCA. For example, at 20 percent occlusion, SRM achieves 109 points; it is higher than l
min
⁡
2
+
PCA’s 98 points. On the other hand, the reason why the number of matching points is not decreased to zero when occlusion increases to 40 percent is that the located square block we used here is the zero gray-lever images. And the matching points also have weakly textured characteristic, so it will not be much affected by this square block.Figure 20
Recognition under varying level of contiguous occlusion.


## 5.4. Improved Quasi-Dense Matching

In this section, we use WTD to promote the quasi-dense matching algorithm [20]. The quasi-dense matching algorithm starts from a set of sparse seed matches which were usually obtained by classical detectors, then propagates to the neighboring pixels by the best-first strategy, and finally produces a quasi-dense disparity map. Since most initial sparse seed matches distribute in the strong texture regions, it nearly has no seed matches in the textureless areas; furthermore if the matches got from propagating step in these areas are wrong, gross reconstruction errors will occur, so here we use the proposed approach to get the initial sparse seed matches in the large textureless areas.The original algorithm is independently implemented for comparison on the same image pairs. The corresponding-point sets obtained by WTD and traditional quasi-dense matching algorithm are shown in Figure21. One can verify the effectiveness of our implementation by corresponding quality measures which are given in Table 4.Table 4
Comparison between original dense matching and improved one under different circumstances.
Change
Algorithm
#corresponding-point on untex
Lighting
Quasi + ours
845
Quasi
414
Image scale
Quasi + ours
490
Quasi
210
Camera angle
Quasi + ours
676
Quasi
351Results from improved dense matching and original one under different circumstances. Top row: corresponding-points matched with lighting changes. Middle row: corresponding-points matched with scale changes. Bottom row: corresponding-points matched with camera angle changes. (a) Corresponding results from improved quasi-dense matching algorithm. (b) Corresponding results from original quasi-dense matching algorithm.
(a)
(b)Our algorithm is evaluated on the changes of lighting, scale, and camera angle, respectively, and the results demonstrate that the algorithm performs particularly better on the large textureless object surface than the original one (as shown in Figure21).


## 6. Conclusion

In this paper, we proposed an efficient detector for weakly textured points and used sparse representation for matching the detected weakly textured points in two different images. We have contended both theoretically and experimentally that the proposed algorithms outperform others in weakly textured points detecting and matching. The performance of the new detector was demonstrated on a wide variety of image sets in which the weakly textured objects were included. The proposed detector gives a way of detecting the weakly textured points which would be useful for 3D reconstruction of the object with weak texture at the dense matching step. On the other hand, the proposed matching algorithm SRM has the higher performance than others on the LBP feature space; moreover, to a certain extent, SRM can handle occlusion and corruption on the feature of weakly textured points.Intriguing questions for future work are whether this method is appropriate for wide-based stereo and what description can be used for these weakly textured points. The first problem can be solved by replacing circumferences with ellipses; the second one might be solved by using the information of the surround points which are detected by classical detectors, such as SIFT, GOLH, and SURF, and it is a most challenging one as well. These are two directions for our future work.



---

*Source: 568034-2014-09-03.xml*