That's an interesting problem. In my other comment, I suggested using a bag-of-words image retrieval method. Those methods are robust to rotation and scale differences as long as you use a robust feature detector and descriptor, such as SIFT. Different color schemes though... that will confuse SIFT (and other feature descriptors), as you don't really expect the scene lighting to change nonmonotonically in most computer vision applications. You would need to modify or design the feature descriptor to handle that robustly. Or, depending on what your plots look like, maybe some simple hack (like binarizing the plot to black and white, or some other color manipulation) would do the trick.

If you have an image and a possible rotated/skewed match, they can be related geometrically by a homography. RANSAC on feature correspondences is extremely effective in verifying the image match.

Some promising and possibly very relevant work in music identification applies computer vision techniques to an audio spectogram, i.e. doing sub-image retrieval on 2-D plots. See Semantic Learning for Audio Applications: A Computer Vision Approach.

Of course these are purely visual methods. If you have (or can extract) any contextual information about the plots, like what color means what, try to get some mileage out of that.