Polygon Compression

[ajmartin]

I am looking for lossless compression benchmarks applied to small polygons. `small` in terms of number of vertices. Also note that my problem deals with embedding these polygons in SMS (90 char limit) and hence the problem is different from compressing big polygon meshes. An example of a polygon would be a list of `n` vertices in 2-dimensional space - x₁,y₁ x₂,y₂ ... x_n,y_n . If no such benchmarks exist, which compression algorithms/techniques would you recommend? As of now, I have looked into Arithmetic Encoding & LZW.

Thanks!

[biject.bwts]

If I had to do this problem I would not choose storing the data as pairs of points in x y pairs. But then it depends what you mean by polygons are they convex or what? Give more info!!

[ajmartin]

They are all simple polygons i.e. none of them have intersecting sides.

[Jarek]

Lempel-Ziv doesn't seem to fit the problem. Just use entropy coder, but you need a better representation of the data to efficiently exploit statistical redundancy. For example:

1) differences of coordinates (integer case): e.g. x[i+1]-x[i], y[i+1]-y[i],
2) polar coordinates e.g. around the center of mass - storing difference of polar angle and radii between succeeding vertices. Average angle is 360/n, can be negative.
3) (length, angle) while traveling through the curve (like LOGO turtle). Average angle is 180*(n-2)/n (this representation is "less robust" - there can be problems while closing the curve due to inaccuracies/quantization).

For a regular polygon, 2nd and 3rd case would give constant values - great compression. Generally you have some perturbation around average values. In both cases you should normalize lengths and angles to average e.g. to 1 - then you have some probability distribution around one, e.g. exp(-c*|x-1|) with c found from sample data.
You haven't written if your polygons have real or integer coordinates? - the angle representation is rather for the real case.
In integer case just write differences and use some order 0 entropy coder. Lempel-Ziv could help here if there would be many repeating patterns, like for fractals.

[ajmartin]

Thanks for the idea! You are correct about LZW - my experiments for a corpus of about 10K polygons yielded better compression ratios for arithmetic encoding than LZW.

Now coming to your idea - they are all real coordinates; I understand finding `n` polar coordinates (r, \phi); finding r_avg and \phi_avg; but what exactly do you mean by -

In both cases you should normalize lengths and angles to average e.g. to 1 - then you have some probability distribution around one, e.g. exp(-c*|x-1|) with c found from sample data.

I don't get how the n pairs of (r, \phi) will be encoded taking advantage of statistical redundancy.

[biject.bwts]

I would like to know do you need the location of the polygon in space? Do you care if the polygon is rotated?

I still have a question when you wrote your explanation for "simple polygons" the wiki page shows 5 examples. four of them are convex one is not. Could each of these 5 examples be included in your case? Also just storing the x,y data or equivalent info not enough you need the number of sides. The so called real data is it stored as integers or floating point numbers?

[ajmartin]

I would like to know do you need the location of the polygon in space? Do you care if the polygon is rotated?

Location of the polygon in the space is important

I still have a question when you wrote your explanation for "simple polygons" the wiki page shows 5 examples. four of them are convex one is not. Could each of these 5 examples be included in your case?

Yes, all 5 examples can be included

Also just storing the x,y data or equivalent info not enough you need the number of sides. The so called real data is it stored as integers or floating point numbers?

The dataset has real numbers with at most two decimal points, so one may convert it to integers or use them in their original form.

[Matt Mahoney]

You can develop a better model for any data set if you understand the source of the data. For example, if your polygons form a mesh, then they will share vertices and you can take advantage of that fact in your compressor by eliminating duplicates. How are these polygons generated?

[Jarek]

ajmartin, if you have real coordinates, the 2nd representation seems to be indeed the best choice.
So first I would found the center of mass: (average x, average y) - you can store it in the file if needed.
Then normalize distances from this center - divide them by average distance, which again can be stored if needed.
Now you know that average distance is 1 - for a regular polygon it would be exactly 1 for all vertices, for a convex polygon should be close to one, for a more complex it could be more varying.
So for the dataset you work on (sample polygons), you should draw histogram of normalized distances, getting some probability distribution. It should have maximum in 1, should be approximately symmetric, so probably you can use density of form exp(-c|r-1|), where c is some coefficient - you can fit it to the histogram of your dataset and use a universal one, or adapt to different types of polygons: fit c for a given polygon and store it in the header.
Then you can encode these distances using entropy coding with probabilities from this assumed probability distribution. There should be some correlations between distances for succeeding vetices, so it might be beneficial e.g. to encode differences between succeeding distances.

Then you analogously do for polar angles. You can write the first one if rotation is essential. Then encode differences between succeeding angles. Again you can normalize them to average 1 - this time by dividing by 360/n. Then find probability distribution from your dataset and use it for entropy coder.
If you know that the polygon is convex, the differences will be always positive.

In both cases (distance and angle) there is a question of quantization: how accurately you want these values.
Beneficial would be quantizing (distance, angle) pairs together because accuracy of angle is less important for low distances.

If you want something more sophisticated, using fourier (cosinus) transform for distances might be reasonable, especially for convex polygons.

[nburns]

I don't get how the n pairs of (r, \phi) will be encoded taking advantage of statistical redundancy.

Compression is like gambling. If you were at a casino and you noticed that the roulette wheel was statistically biased, landing on double zero about every 3rd spin, you could exploit that information to come out ahead of the house.

In compression, if you notice that the next byte was 0 half of the time, you have the opportunity to save -- "win" -- space by placing bets. Before you send each byte, you might send a single bit that indicates whether the next byte is zero. When the bet is correct, you skip that byte -- a net win of 7 bits. When the bet is incorrect, you send the byte verbatim, so you've spent 1 bit and gotten nothing, a net loss of 1 bit. On average, you expect to "win" 3 bits per byte. In general, the objective is to look for winnable bets, i.e. places where the house odds are wrong. The house odds are simple to calculate: the house predicts that each bit has exactly even odds of being 1 or 0 (Pr(1) = 0.5).

The formula to convert from probabilities to bits is bits=-lg(p), where lg is the base 2 logarithm. That formula tells you how many bits you need; once you have a winnable bet that saves space, you can basically feed the probability to an arithmetic coder and it will handle the encoding.

An example of where you might find easy predictions is, e.g., the exponents of the coordinates.

[Kennon Conrad]

Compression is like gambling. If you were at a casino and you noticed that the roulette wheel was statistically biased, landing on double zero about every 3rd spin, you could exploit that information to come out ahead of the house.

It's a good thing there is no "house" to rig the odds.


Given your data uses Cartesian coodinates, I would avoid converting to Polar coordinates if you truly need lossless compression. You would need to increase the precision to make sure you can get the exact same coordinates back.

Unless you have less precision for large numbers or your data would overflow an interger, I would multiply the data by 100 and use integer math. I think I would just write the coordinate of one of the vertices and the {x,y} deltas for the rest of the vertices, then entropy code the data. You can eliminate y value predictions that would cause crossing. You can have rules about which vertex is the first vertex and whether the polygon is drawn clockwise or counterclockwise that can also help predictions. For instance, you might want to have the longest side or largest valued vertex first. If the polygons tend to have sides that are at particular angles or biased toward certain shapes you can improve predictions using that information. For instance, if sides tend to be perfectly vertical or horizontal, a prediction of 0 for the delta X and Y's should be given more weight (but not for Y if X was 0). If sides tend to be 45 degrees off from vertical, then a prediction of Y = +/-X should help. It all comes down to whether or not there are any exploitable characteristics of the typical polygon you need to compress in terms of the number of vertices, the location, the size, and the shape.

[nburns]

It's a good thing there is no "house" to rig the odds.

Actually, the house's odds are implicitly already there. What's good is that the house doesn't normally make good bets.

[nburns]

Lempel-Ziv doesn't seem to fit the problem. Just use entropy coder, but you need a better representation of the data to efficiently exploit statistical redundancy. For example:

1) differences of coordinates (integer case): e.g. x[i+1]-x[i], y[i+1]-y[i],

A lot of savings will likely come from putting the coordinates in a more favorable order to narrow their ranges. For instance, if you want to send a set of integers where order doesn't matter, the first thing to do is sort them; then you can send just the smaller deltas. Potentially even better than simple sorting is deliberately sending them out-of-order so the ranges are bounded on both ends: if you have to send 3 positive integers x1<=x2<=x3, you could send x3 first, which provides a maximum for the remaining two. You can put all the integers on a tree and exploit bounded ranges recursively. You can do this in a predetermined order, e.g. just repeatedly cut the set in half like a perfectly-balanced binary tree. Or, potentially more interesting, you could search for an optimal shape for the tree.

In the case of polygons, there is an algorithm in CLR for optimal polygon triangularization using dynamic programming -- this finds a triagularization, which is equivalent to putting the vertices on a binary tree. It would be interesting to see what could be done with an appropriate cost function and encoding.

[Kennon Conrad]

A lot of savings will likely come from putting the coordinates in a more favorable order to narrow their ranges. For instance, if you want to send a set of integers where order doesn't matter, the first thing to do is sort them; then you can send just the smaller deltas. Potentially even better than simple sorting is deliberately sending them out-of-order so the ranges are bounded on both ends: if you have to send 3 positive integers x1<=x2<=x3, you could send x3 first, which provides a maximum for the remaining two. You can put all the integers on a tree and exploit bounded ranges recursively. You can do this in a predetermined order, e.g. just repeatedly cut the set in half like a perfectly-balanced binary tree. Or, potentially more interesting, you could search for an optimal shape for the tree.

In the case of polygons, there is an algorithm in CLR for optimal polygon triangularization using dynamic programming -- this finds a triagularization, which is equivalent to putting the vertices on a binary tree. It would be interesting to see what could be done with an appropriate cost function and encoding.

Don't forget that there is more than one way to draw a polygon if any of the angles are more than 180 degrees. It might be worth putting a bit at the start to indicate whether the polygon has any angles greater than 180 degrees.

[ajmartin]

How are these polygons generated?

These are generated by humans on a map marking an area of interest. The attached picture has few examples shown in yellow boundaries.

[Matt Mahoney]

Makes sense now. You can use delta coding like x1, y1, x2-x1, y2-y1, x3-x2, y3-y2... and possibly 2 passes of delta coding. Then try feeding that to standard compressors like zip, 7zip, bsc, zpaq, etc. or their API libraries if you need to embed it in your application.