Skip to content

Instantly share code, notes, and snippets.

@irealva
Last active May 11, 2023 06:26
Show Gist options
  • Save irealva/96a6b04ef4fe8ffbb081575e6e17fa35 to your computer and use it in GitHub Desktop.
Save irealva/96a6b04ef4fe8ffbb081575e6e17fa35 to your computer and use it in GitHub Desktop.
Gist for Move Mirror blog post: vp tree
const similarity = require('compute-cosine-similarity');
const VPTreeFactory = require('vptree');
const poseData = [ […], […], […], …] // an array with all the images’ pose data
let vptree ; // where we’ll store a reference to our vptree
// Function from the previous section covering cosine distance
function cosineDistanceMatching(poseVector1, poseVector2) {
let cosineSimilarity = similarity(poseVector1, poseVector2);
let distance = 2 * (1 - cosineSimilarity);
return Math.sqrt(distance);
}
function buildVPTree() {
// Initialize our vptree with our images’ pose data and a distance function
vptree = VPTreeFactory.build(poseData, cosineDistanceMatching);
}
findMostSimilarMatch(userPose) {
// search the vp tree for the image pose that is nearest (in cosine distance) to userPose
let nearestImage = vptree.search(userPose);
console.log(nearestImage[0].d) // cosine distance value of the nearest match
// return index (in relation to poseData) of nearest match.
return nearestImage[0].i;
}
// Build the tree once
buildVPTree();
// Then for each input user pose
let currentUserPose = [...] // an L2 normalized vector representing a user pose. 34-float array (17 keypoints x 2).
let closestMatchIndex = findMostSimilarMatch(currentUserPose);
let closestMatch = poseData[closestMatchIndex];
@oofin008
Copy link

oofin008 commented Apr 8, 2019

Hello, irealva. I have a problem when I try to run this function in my html web on local server.
It shows that require() is not defined

@irealva
Copy link
Author

irealva commented Oct 13, 2020

Hi, the reason is because this is just a high-level example of the code we used. You'll see there are parts around the data that are missing (on lines 4 and 33) for example.

Specifically require() does not exist in browser/client side Javascript. Check out this Stackoverflow answer for more details.

@christurnbull
Copy link

This is great, but my understanding of vp trees is they need to use a distance metric that satisfies triangle inequality, which apparently cosine distance does not.

So why does it work?
I don't understand the math behind triangle inequality.
Maybe it satisfies enough to allow the vp tree to make reasonable decisions?
Was triangle inequality considered? is it a trade-off for lookup speed?

Any info you can give on using decision trees and triangle inequality would help me, if you could explain please?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment