File Exchange

## Table Breakpoint Optimization

version 1.7.0.1 (605 KB) by Tucker McClure

### Tucker McClure (view profile)

A set of tools for finding the best way to reduce the size of a table.

Updated 01 Sep 2016

These tools find the best way to reduce the size of a table, given either the desired number of points or the maximum tolerable error. The resulting table allows faster interpolation and requires less memory.
Specifically, given an input 1D, 2D, or n-D table and a desirable number of breakpoints (or allowable mean squared error), these functions will calculate the best placement of the breakpoints to fit the input table. The user can specify how the table values should be interpolated using linear, spline, nearest methods, etc. The breakpoints, new table, and mean squared error of the fit are returned.

The optimal placement of breakpoints is taken to be the placement resulting in the minimum mean squared error of the new table evaluated at the original table's breakpoints with the specified interpolation scheme. For regularly sampled input tables, this acts as an integral of error over the table's area. This allows irregular sampling of the original table to focus on critical (e.g., rapidly changing) areas of the table.

To get started, either load the app and click "Help", enter "TableOptimizerGui" at the command prompt, or see find_best_table_demo.pdf.

Requires the Optimization Toolbox(TM).
Supports (but does not require) the Parallel Computing Toolbox(TM).

### Cite As

Tucker McClure (2020). Table Breakpoint Optimization (https://www.mathworks.com/matlabcentral/fileexchange/35194-table-breakpoint-optimization), MATLAB Central File Exchange. Retrieved .

Jesse Clauson

### Jesse Clauson (view profile)

Description states "This allows irregular sampling of the original table to focus on critical (e.g., rapidly changing) areas of the table." yet tables seem to be uniformly sampled resulting in wasted unnecessary columns where data is nearly linear.

Anna Weeks

### Anna Weeks (view profile)

saikartheek chavali

Alex

### Alex (view profile)

I'm trying to get my mind around |find_best_table_nd.m| and make sense of the formatting required for dependent variable.

In my application both my independent variable and dependent variable has three values (call them |r_in|, |g_in|, and |b_in|, and |r_out|, |g_out|, and |b_out|). I'm applying the function outside of Matlab and the |r_out|, |g_out|, |b_out| are returned to me as an |nx3| array. I'm trying to figure out how I need to reformat that array to use the table optimization function. I'm assuming the function should look sometime like this, but maybe I'm off base ...

[x_f, z_f, mse] = find_best_table_nd({r_in, g_in, b_in}, {r_out, g_out, b_out}, [17 17 17]);

Any hints on how to get from an |nx3| to the proper format for |find_best_table_nd| would be greatly appreciated.

Tucker McClure

### Tucker McClure (view profile)

Hi Oscar. That's a much smaller problem! There's just one parameter per dimension of your table: the number of breakpoints to use. This might be so small that you could just write a few loops to try different numbers of evenly-spaced breakpoints, and then simply take the best result from the loops. Feel free to contact me if you'd like to talk further.

Oscar Scitech

### Oscar Scitech (view profile)

This works great for approximating complex functions and generating the optimized LUT I want!
However, what can you do if you are constrained by needing a regularly spaced grid. I would like to keep the optimization, but I need my LUT to be regularly spaced. Any suggestions?

MK

Tucker McClure

### Tucker McClure (view profile)

Hi ths1104 Stenkhiste,

Good comments. However, note that each call to the "fit" function is an optimization problem where n_x is the number of parameters, and so running with n_x = length(x_0) for large datasets (and why would anyone use this if they didn't have a large dataset to compress?) would take very long. For this reason, we start small and double the number of points until we find a good option. You're right that this *could* result in a large n_x, but it won't actually do this in practice (except for specific pathological cases). Then, we use a binary search to narrow in on the best final number. This is much faster for the vast majority of data sets that make sense for compression because it never requires running with an absurdly large number of points. Make sense?

However, I agree that it would be a small improvement to limit n_x to the original data size, and I could put this into a future update.

Thanks for the critical feedback!

- Tucker

ing-electrica electrica

Ameya Deoras

### Ameya Deoras (view profile)

Excellent! Works great for approximating a curve with piecewise linear functions

ths1104 Stenkhiste

### ths1104 Stenkhiste (view profile)

Great code!

I am looking at find_best_table_1de. I have two comments:

(a) It seems there is a problem with max_iterations. Lets say we have length(x_0)=10. So max_iterations=10. In the first while loop, n_x could increase up to 3*2^10 = 3072. This is much higher than length(x_0)! The loop should stop when n_x>=length(x_0).

(b) Why dont you start directly the dichotomie using
n_x_left = 3;
n_x_right = length(x_0);
? This looks simpler because you can get ride of the first while loop.