Encoding Directed Edges

The distance metric defined on the graph structure is based on the undirected edge weights. While the above embedding has preserved the distance metric, it has failed to preserve any oriented relations, such as the hierarchical relations common to scale-space structures. This is due to the fact that oriented relations do not satisfy the symmetry property of a metric. We can retain this important information in our embedding by moving it into the nodes as node attributes, a technique used in the encoding of directed topological structure in [20], directed geometric structure in [19], and shape context in [2]. Encoding in a node the attributes of the oriented edges incident to the node requires computing distributions on the attributes and assigning them to the node. For example, a node with a single parent at a coarser scale and two children at a finer scale might encode a relative scale distribution (histogram) as a node attribute. The resulting attribute provides a contextual signature for the node which will be used by the matcher (Section 5) to reduce matching ambiguity. Specifically, let $G=({\cal A}, E)$ be a graph to be embedded. For every pair of vertices, $(u,v)$, we let $R_{u,v}$ denote the attribute vector associated with the pair. The entries of each such vector represent the set of oriented relations $R$ between $u,v$. For a vertex $u \in {\cal A}$, we let $N(u)$ denote the set of vertices $v\in {\cal A}$ adjacent to $u$. For a relation $p \in R$, we will denote ${\cal P}(u,p)$ as the set of values for relation $p$ between $u$ and all vertices in $N(u)$, i.e., ${\cal P}(u,p)$ corresponds to entry $p$ of vector $R_{u,v}$ for $v \in N(u)$. Feature vector ${\cal P}_u$ for point $u$ is the set of all ${\cal P}(u,p)$'s for $p \in R$. Observe that every entry ${\cal P}(u,p)$ of vector ${\cal P}_u$ can be considered as a local distribution (histogram) of feature $p$ in the neighborhood $N(u)$ of $u$. We adopt the method of [19], in which the distance function for two such vectors ${\cal P}_u$ and ${\cal P}_p$ is computed through a weighted combination of Hausdorff distances between ${\cal P}(u,p)$ and ${\cal P}(u',p)$ for all values of $p$.