Tensor VotingWhat do you see?General IdeaContentsTensor RepresentationTensor RepresentationTensor RepresentationTensor RepresentationTensor RepresentationVoting FieldVoting FieldTensor VotingSlide Number 13Tensor VotingTensor VotingTensor VotingTensor VotingTensor VotingTensor VotingTensor VotingEfficient Tensor VotingEfficient Tensor VotingReferenceSlide Number 24Slide Number 25LOGOTensor VotingZhe Leng, University of Utah, 2010What do you see?General IdeaUse features to strengthen each other and to expand features into possible nearby locations Represent local feature by tensor Every pixel (with a feature) cast a vote to each nearby pixel “Nearby” is defined by a voting field aligned with the local pixel The vote is a tensor generated according to the local tensor and the position in the voting field All the votes are added to generate the new local tensorContentsTensor Representation1Voting Field2Tensor Voting3Efficient Tensor Voting4Tensor Representation From Wikipedia Tensors are geometric entities introduced into mathematics and physics to extend the notion of scalars, (geometric) vectors, and matrices. Many physical quantities are naturally regarded not as vectors themselves, but as correspondences between one set of vectors and another. For example, the stress tensor takes one vector as input and produces another vector as output and so expresses a relationship between the input and output vectors.Tensor RepresentationOnly second order tensor is used, which is an n by n matrix. n is the dimension of the image.Can be expended into following format1nTnn iiiiTλ×==∑eeTensor RepresentationCan be illustrated as a ellipsoidFor example, the 3D case: [Medioni 2000]Tensor RepresentationParameterization (consider eigen values are in descending order)1122 2311...n nnnnα λλα λλα λλαλ−−= −= −= −=3D illustration from [Medioni 2000]Tensor RepresentationUnderstand the parameterization, 3D case shows the directional saliency (stickness), shows the direction. In most case these shows the strength and the orientation of the local edge/flux. The other shows the i-dimensional “ballness”, which shows intersection or possible local i-dimensional plane.  Because solving involves arcsin or arccos, eigen vector orientations are limited to or 1α1eiαie[0, ]π[ /2, /2]ππ−Voting FieldA typical voting field:Voting FieldThe features should be smooth The direction within the vote should be smooth relative to the local tensorLess impact to the pixels far away The saliency within the vote should decrease with distanceAffected by tensor representation For exampleImage is from [Franken 2006]Tensor VotingGeneral Idea: use local feature to strengthen each other and to expand into possible locationsImage is from [Franken 2006]Original ImageTensor VotingCast the voteTensor VotingSum all the votesTensor VotingAfter non-maxima suppressionTensor VotingSpecial Case: Intersection The votes with similar saliencies and near perpendicular orientations will cancel each other, so the saliency of intersection will be very low. But the ballness will be very significant Better identification of intersection involves farther comparison between stickness and ballness.Tensor VotingSpecial Case: IntersectionStickness BallnessTensor VotingSpecial Case: End Point Tensor voting tends to expand open endsCannot Tell whether it is an opening or open endonly by local saliency.Tensor Voting Find out whether this is an end point• End point voting:– a vector voting (not tensor voting)– each vote is the vector directing from the casting pixel to the receiving pixel– the sum of all vote should be near zero for an end point and non-zeros for non-end point– weight of a vote is based on the tensor voting field Remove new end point• Compare the end points found in original tensor image and the one after tensor voting;• Eliminate the end points that only appears in new image.Efficient Tensor VotingSo far, tensor voting is time consuming, because all the operations are in space domainEfficient Tensor VotingSteerable Filter (good for 2D) By decompose a filter into several “major component”, the filter can be rotated easily with the weighted sum of the major components.Spherical Harmonics (good for higher order) Tensors can be decomposed into spherical harmonics, which can be easily rotated.Alignment is then not necessary, tensor voting can be done with convolutionComplexity can be reduced from O(N2M2) to O(N2)ReferenceG Medioni, CK Tang, MS Lee. “Tensor Voting: Theory and Applications.” Proceedings of RFIA. Paris, France. 2000E Franken, M Almsick, P Rongen, L Florack, B Romany. “An Efficient Method for Tensor Voting Using Steerable Filters ”, Medical Image Computing and Computer-Assisted Intervention.