Advertisement

compress data by linearization

Started by September 13, 2014 05:09 AM
2 comments, last by Kamil2009 10 years, 2 months ago

I have a continuous data and i want to compress it by linearization(see picture). What algorithm can be used to minimize both number of lines and total compression error?

GGlnn.png

I don't know of any ready-made algorithms for this, but I can tell you how I would think about it. The first thing I would try to quantify the desirability of a solution. For instance, you could define

error := n_segments + alpha * L2_error

where alpha is some positive constant and

L2_error := sum((data - linearized_value)^2)

I think you can then use dynamic programming to minimize that error, which would run in something like O(n_data_points^2 * n_segments_in_solution).

Can you give us more details of the type of data you are trying to compress and for what purpose?
Advertisement

On the face of it, this doesn't look that different from many polygon reduction algorithms, which are largely driven by picking an error tolerance. But could just as easily be done by picking a target polygon count or reduction percentage. In the simplest terms those type of algorithms take your squiggly line and compute an error function for the removal of each point, and then remove points the produce the least error while updating the error on the other points.

Depending on what this data means, you could do it in one or more passes. A simple one-pass solution (given that this is say, a line stroke from an artist's pen) is to read the line in point by point, collapsing the points as you go via comparison of the raw direction, or the tangents. This is useful for say smoothing a user input in 3d space to a much shorter list of directions from a very noisy input. But if this data has more information than just direction, Alvero is on the right track that you want to iteratively reduce your line by removing the points that contribute the least to the overall shape of the function.

Im doing some project on terrain geomorphing (with level of details), so you may consider initial data to be a values from heightmap (see picture). I need to find areas which can be approximated by line (triangles in 3D, not strictly equilateral or right-angled).Then in the same way find lines inside the parent lines (like tree). And may be in future apply this algorithm to 3D.

Presentation1.png

This topic is closed to new replies.

Advertisement