Tensor voting in N dimensional spaces
View Patent ↗A tensor voting scheme which can be used in an arbitrary number N of dimensions, up to several hundreds. The voting scheme can operate on unorganized point inputs, which can be oriented or unoriented, and estimate the intrinsic dimensionality at each point. Moreover it can estimate the tangent and normal space of a manifold passing through each point based solely on local operations.
1. A method performed by an apparatus, the method comprising:
receiving as input a plurality of points in an N-dimensional space, where N can be any number between 2 and 500;
defining the received plurality of points as second order, symmetric, nonnegative definite tensors that encode an orientation and confidence of the orientation of each point, the tensors comprising a voter having multiple possible orientations;
voting between points to determine, in an unsupervised manner, at least one likely D-dimensional manifold on which said points lie, where D is less than or equal to N, wherein said voting comprises voting between the voter and a receiver by directly computing, without a voting field, a vote between the voter and the receiver; and
producing and outputting information about said at least one D-dimensional manifold used to find relations between points based on the voting between the voter and the receiver.
2. A method as in claim 1 , wherein at least some points have preferred normal and tangent orientation information and other points do not have preferred normal and tangent orientation information.
3. A method as in claim 1 , wherein said input points include oriented points.
4. A method as in claim 1 , wherein said input points include unoriented points.
5. A method as in claim 1 , further comprising learning unknown manifolds from sets of points in terms of estimates of local tangent and normal spaces.
6. A method as in claim 5 , wherein said voting comprises reducing the effect of points which are not part of the at least one manifold.
7. A method as in claim 5 , wherein said learning unknown manifolds comprises learning a plurality of manifolds, which can intersect and are of different types.
8. A method as in claim 5 , further comprising estimating an intrinsic dimensionality of the at least one D dimensional manifold passing through the points.
9. A method as in claim 8 , whereby different points have different intrinsic dimensionalities.
10. A method as in claim 1 , wherein voting between points comprises estimating an arc between a voter point and a receiver point having an arc length, S, calculated based on the following:
S
(
s
,
l
,
θ
)
=
ⅇ
-
(
s
2
+
cK
2
σ
2
)
[
-
sin
(
2
θ
)
cos
(
2
θ
)
]
[
-
sin
(
2
θ
)
cos
(
2
θ
)
]
s
=
θ
v
→
sin
(
θ
)
,
K
=
2
sin
(
θ
)
v
→
,
wherein K represents a curvature of the arc, σ represents a scale of voting, c is a constant, θ represents an angle of the arc, and {right arrow over (v)} represents a vector connection between the voter point and the receiver point.
11. The method of claim 1 , wherein the voter comprises a ball tensor and wherein the voting between the voter and the receiver by directly computing, without a voting field, the vote between the voter and the receiver comprises voting according to:
S ( s,l, θ)= e −(s 2 /σ 2 )( I−{right arrow over (v)}{right arrow over (v)} T )
wherein {right arrow over (v)} is a unit vector parallel to a line connecting the voter and the receiver, I is an identity matrix, and s is a length between the voter and the receiver, an σ is a user-defined scale of voting.