Simplex Curve Fitting

blob2

As part of a previous commercial venture, I was tasked with developing a PC-based system for photogrammetric analysis of small format aerial photos. The goal was to locate points in three dimensions, based on their appearance in multiple photographs taken from different perspectives, and then synthesize three dimensional volumes.

In our application, we needed to measure volumes of coal piles at power generation plants. As someone who likes to think geometrically, I came across an approach that was ideal, since it could be visualized as a geometric exercise in finding the best approximation of an equation to measured data points. The approach is referred to as the “Simplex” algorithm (by Marco Caceci and William Cacheris in their article “Fitting Curves to Data”).

At a high level, the Simplex approach consists of the movement of a geometric object across a field of possible coefficient values using algorithmic rules that force it to converge on an optimal fit. I like to visualize it as the Blob in the old 1958 movie searching for victims! For those who need to determine best fit of an analytical function to a set of data points, it may be worth your time to consider a Simplex approach.

I haven’t noticed many references to this technique since I used it in my photogrammetry project (perhaps because it appeared in a non-technical magazine). But it worked so well for me that I wanted to pass it on to others as something to add to their applied mathematics toolkit.

For anyone with a deeper interest, I was solving the collinearity equation to determine the “exterior orientation” of camera positions (i.e. the location and orientation of a camera in 3-space). Since the problem domain is geometric with known references and the ability to make good initial approximations, the Simplex approach worked exceptionally well. It was also useful in solving coplanarity systems. The mathematics for these systems is interesting, and explained in greater detail in the references below.

References:

“Fitting Curves to Data, the Simplex Algorithm is the Answer”; Marco S. Caceci, William P. Cacheris; Byte; May 1984

“Elements of Photogrammetry with Applications in GIS 4th Edition”; Wolf, Dewitt, Wilkinson; 2014 (excellent up-to-date survey of field)

“Manual of Photogrammetry 4th Edition”; American Society of Photogrammetry; Out of print (excellent section on mathematics)

(Original post on December 17, 2016)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s