Q:

Trace An Isoline of an Expensive 2D Function

I have a problem similar in formulation to this post, with a few notable differences:
What simple methods are there for adaptively sampling a 2D function? 
Like in that post:

I have a $f(x,y)$ and evaluation of this function is somewhat expensive to compute

Unlike in that post:

I am interested not in the value of the function accurately everywhere, but only in finding a single isocontour of the function. 

I can make significant assertions about the autocorrelation of the function, and consequently the scale of smoothness. 

Is there an intelligent way to step along/sample this function and find this contour? 
More Information
The function is the computation of Haralick Features over $N$ pixles surrounding the point, and soft classification by some sort of classifier/regressor.   The output of this is a floating point number which indicates which texture/material the point belongs to.   The scaling of this number can be estimated class probablities (SoftSVM or statistical methods etc) or something really simple like the output of a linear/logistic regression.   Classification/regression is accurate and cheap compared to time taken for feature extraction from the image. 
Statistics surrounding $N$ means that the window is typically sampling overlapping regions, and as such there is significant correlation between nearby samples. ( Something I can even approach numerically/symbolically)  Consequently, this can be thought of as a more complex function of $f(x, y, N)$ where larger $N$ will give an estimate more related to the neighborhood (highly correlated), and a smaller $N$ will give a more variable, but more local estimate. 
Things I Have Tried:

Brute Computation - Works well.   95% correct segmentation with constant $N$.  The results look fantastic when contoured using any standard method after that.   This takes forever.    I can simplify the features calculated on a per-sample basis, but ideally I want to avoid this to keep this code general to images with textures who's differences show up in different parts of the feature space. 

Dumb Stepping - Take a single pixel "step" in each direction and pick the direction to move based on closeness to iso-line value.   Still pretty slow, and it will ignore bifurcation of an isoline.  Also, in areas with a flat gradient it will "wander" or double back on itself. 

I am thinking I want to do something like the subdivison proposed in the first link, but pruned for boxes which bound the isoline of interest.   I feel like I should be able to leverage $N$ also, but I am not sure how to approach that. 

A:

There is a paper in computer graphics called Provably Good Sampling and Meshing of Surfaces, which relies on you providing an oracle that determines all the intersections of an isoline with a given line segment.  With that, it samples all the contours assuming you can provide a local feature scale (something like the maximum local curvature), and an initial set of line segments that intersects all the contours.  It is not the simplest thing to implement, since it relies on computing Delaunay triangulations, but it is implemented in 3D in CGAL.  It is substantially simpler in 2D, since good triangulation software like Triangle exists.  In some sense, this is pretty close to the best you can possibly do.