Matching based upon rank
AssigneeGoogle Inc.
InventorsJay Yagnik, Sergey Ioffe
Life of this patent
Estimating the term…
Abstract
Systems and methods for measuring consistency between two objects based upon a rank of object elements instead of based upon the values of those object elements. Objects being compared can be represented by d-dimension feature vectors, U and V, where each dimension includes an associated value. U and V can be converted to rank vectors, P and Q, where values of U and V dimensions are replaced by an ordered rank or a function thereof. Analysis directed to the consistency between U and V can be accomplished by determining consistency between P and Q, which can be more efficient and more accurate, particularly with regard to illumination-invariant comparisons.
Claims20
A system, comprising:
- a memory that stores computer executable components;
- and
- a microprocessor that executes the following computer executable components stored in the memory:
- a receiving component that receives a first feature vector, U, associated with a reference object and a second feature vector, V, associated with a comparison object, wherein U and V are d-dimensional vectors;
- a sorting component that constructs a first rank vector, P, based upon a sequential ordering of dimensions of U, and a second rank vector, Q, based upon a sequential ordering of dimensions of V;
- a conversion component that converts values of dimensions of U and V to corresponding absolute values based upon halfwave rectification;
- a comparing component that determines a consistency score between P and Q;
- and
- a matching component that identifies a sufficient match between at least a portion of the reference object and at least a portion of the comparison object based upon the consistency score between P and Q.
A method, comprising:
- employing a microprocessor to execute computer executable components stored within a memory to perform the following:
- receiving a first feature vector, U, associated with a reference object, and a second feature vector, V associated with a comparison object, wherein U and V each include d dimensions;
- deriving feature vector U′ based upon a sequential ordering of the d dimensions of U, and deriving feature vector V′ based upon a sequential ordering of the d dimensions of V;
- constructing a first rank vector, P, by replacing values of the d dimensions of U with a rank according to the sequential ordering of U′, and constructing a second rank vector, Q, by replacing values of the d dimensions of V with a rank according to the sequential ordering of V′;
- determining a consistency score between rank vectors P and Q and a weighted combination of sub-scores between P and Q at rank k, where k is an integer from 1 to d, wherein αk is utilized as a weight for a sub-score between P and Q at rank k, where αk is non-negative;
- and
- identifying a sufficient match between at least a portion of the reference object and at least a portion of the comparison object based upon the consistency score between rank vectors P and Q.
An apparatus, comprising:
- means for receiving a first feature vector, U, associated with a reference object, and a second feature vector, V associated with a comparison object, wherein U and V include d dimensions, where d is any positive integer;
- means for deriving feature vector U′ based upon a sequential ordering of the d dimensions of U, and deriving feature vector V′ based upon a sequential ordering of the d dimensions of V;
- means for constructing a first rank vector, P, by replacing values of the d dimensions of U with a rank according to the sequential ordering of U′, and constructing a second rank vector, Q, by replacing values of the d dimensions of V with a rank according to the sequential ordering of V′;
- means for utilizing halfwave rectification for converting values of dimensions of U and V to corresponding absolute values;
- means for determining a consistency score between rank vectors P and Q;
- and
- means for identifying a sufficient match between the reference object and the comparison object based upon the consistency score between rank vectors P and Q.
Dependencies are inferred from the claim text.