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.

  • $\begingroup$ I have exactly the same problem, except that it is a likelihood function I want to contour and it is expensive because at each point I need to perform a minimisation. Did you make any progress and/or can you point out how you eventually went about this? $\endgroup$
    – adavid
    Oct 6 '12 at 15:54
  • $\begingroup$ I just checked the solution I converged on. (see below) $\endgroup$
    – meawoppl
    Oct 10 '12 at 2:38

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.

  • $\begingroup$ I really like this formulation as it also logically extends into 3d rather cleanly. I have to formulate this in Python, so I already have access to qhull's Delauny wrapping, so that is not a huge issue. Let me see if I get this summary right: - Do some sampling to seed. - Triangulate samples. - For all edges that span isoline above some length: compute intersections of isoline with edge - all of the computed to samples, and repeat from the triangulation step? $\endgroup$
    – meawoppl
    Mar 7 '12 at 23:51
  • $\begingroup$ @meawoppl: I have not personally implemented or used this algorithm (yet!) but that sounds about right. $\endgroup$
    – Victor Liu
    Mar 8 '12 at 8:41
  • $\begingroup$ I am going to wip this up today, and post some results! $\endgroup$
    – meawoppl
    Mar 8 '12 at 20:12
  • $\begingroup$ Sorry for the delay. This method works really well for my data set. Basically, I seed it a regular mesh to sample over to start, then triangulate, subdivide the edges that cross the iso-contour, the repeat. It is a bit hard to express the "finest feature" requirement, and there is merit to random initial sampling vs, regular as a diagonal isoline takes a bit longer than one that follows the sampling's tenancies. I ended up just letting it take at most 5 passes, and that worked as a really simple stopping critera. Wooo >1K $\endgroup$
    – meawoppl
    Oct 10 '12 at 2:41

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.