20NN precomputed using distance on 64x64. Then Dijkstra's. Precomputation takes too long. Network bandwidth is the limiting reagent, as the pictures are stored on nfs
20NN precomputed using distance threshold on 8x8 (all in memory), thresholding and heaping the results, then loading the top 50 64x64 into memory to find the closest 20. Then Dijkstra's. Precomputation takes too long.
Same as above, but using A* and computing 20NN on demand. This was very educational. I was against this at first since I thought that the bulk of time spent should be on the precomputation. Whether or not this is possible, A* takes too long here. Data loading of the 8x8 also takes a long time.
Same as above, but with the 8x8's copied to a local drive. This never fully worked since the anim cluster has minimal hard drive space and the Wean cluster computers run out of inodes.
Same A*, but with the precomputation of reading all 8x8s and writing them out as a giant flatfile, once. I could then copy this flatfile to other computers. 64x64s are still on nfs.
I realized that I didn't need to run A*, since I actually don't care which starting images I use. Thus I can run a greedy algorithm - take a random image, find the nearest, find the nearest to that not in the path, etc. If the data is suitably dense, this will look good, and it is O(|V| * p), where p=length of path. The A* function is still in the code; if I ever have two images I want to find the path between, and a Yahoo cluster to run on, it is ready.
I compare images of different aspect ratios by padding the textures (duplicating the last row/column) to get them to an aspect ratio of 640x480. I tried only using pics in this aspect ratio, or close to it (this was a coding pain). With this criterion only half the two million images get used. However, the degradation in min path quality is significant - maybe some threshold of pictures needed was crossed, in the wrong direction. Back to all pics.
Morphing between images was implemented with a uniform grid and matching image gradient patches.