Trace An Isoline of an Expensive 2D Function

Question

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.

Answer 1

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.

Answer 2

You might try applying the core features of the Efficient Global Reliability Analysis (EGRA) method. This method was derived for the efficient computation of a probability of failure, but the guts of it are focused on doing what you describe - creating a model that is accurate only near a specific contour of interest.

This might be an interesting starting point, but I'm not sure it will solve your problem. It depends very much on the shape of your function. If it is something that can be approximated well with a kriging model, then it should perform well. These models are pretty flexible, but generally need a smooth underlying function. I have tried applying EGRA to an image segmentation application in the past, but had little success because it simply doesn't make sense to fit a surrogate model to something that isn't really defined by a functional relationship. Still, I mention it as something you might want to look into in case your application is different than I'm envisioning.

If I haven't talked you out of it, you can read more about EGRA here (PDF link) and here, and there is an existing implementation in Sandia's DAKOTA project - to my knowledge, the only open-source implementation of EGRA available.