46
$\begingroup$

I am trying to design a cloth that, from the point of view of a camera, is very difficult to compress with JPG, resulting in big-size files (or leading to low image quality if file size is fixed).

It must work even if the cloth is far away from the camera, or rotated (let's say the scale can vary from 1x to 10x).

Noise is quite good (hard to compress), but it becomes grey when looking from far, becoming easy to compress. A good pattern would be kind of fractal, looking similar at all scales.
Foliage is better (leaves, tiny branches, small branches, big branches), but it uses too few colors.

Here is a first try: Most uncompressible

I am sure there are more optimum patterns.
Maybe hexagon or triangle tessellations would perform better.

JPG uses the Y′ Cb Cr color space, I think Cb Cr can be generated in a similar way, but I guess it's better to not use uniformly the full scope of Y' (brightness) since camera will saturate the bright or dark areas (lighting is never perfect).

QUESTION: What is the optimum cloth pattern for this problem?

$\endgroup$
  • 1
    $\begingroup$ I'll have to keep an eye on this question.... if an interesting answer is achieved, I can predict a fabric order at www.spoonflower.com (or a similar service) and a really hard to look at shirt to add to my collection ;-) $\endgroup$ – RBerteig Apr 11 '12 at 20:51
  • $\begingroup$ An interesting pattern competition project could be: 1) Take a high-definition image of such a pattern 2) Rotate it, take a random portion of it (at random scale), blur a bit, add a bit of noise and small random color deviation 3) Compress it with JPG 4) See file size, calculate metrics about the quality loss, and calculate the "score" using these metrics. 5) Repeat many times to converge to this pattern's average score 6) Repeat with other patterns and compare scores $\endgroup$ – Nicolas Raoul Apr 13 '12 at 6:32
  • 1
    $\begingroup$ Since lossy algorithms can always compress more by throwing away more data, it seems like you'd have more luck with using patterns that depend on the high-frequency detail. For example, fine lines. In other words, it may compress well, but it degrades in quality very quickly. Depends on what you want to accomplish I suppose. Think fingerprints--it's a classic case where wavelets were required for good compression over JPEG because of the need to preserve the detail. $\endgroup$ – datageist Apr 26 '12 at 21:01
  • $\begingroup$ @datageist: A picture (raw camera output) of a cloth with lines might be difficult to compress, but step backward, take another picture: it will contain only grey pixels, very easy to compress with almost no loss. The pattern I am looking for must result in pictures (raw camera output) that are difficult to compress at a wide range of scales. $\endgroup$ – Nicolas Raoul Apr 27 '12 at 4:51
  • $\begingroup$ @NicolasRaoul Right, I get that, I'm just saying anything is compressible if you throw away enough information. Do you just want a pattern that has the distinction of being "hard to compress" (i.e. for fun), or are you trying to actively discourage people from attempting to compress images containing the pattern? $\endgroup$ – datageist Apr 27 '12 at 5:30

10 Answers 10

15
$\begingroup$

Noise is quite good (hard to compress), but it becomes grey when looking from far, becoming easy to compress. A good pattern would be kind of fractal, looking similar at all scales.

Well, there is fractal noise. I think Brownian noise is fractal, looking the same as you zoom into it. Wikipedia talks about adding Perlin noise to itself at different scales to produce fractal noise, which is maybe identical, I'm not sure:

Perlin fractal noise

I don't think this would be hard to compress, though. Noise is hard for lossless compression, but JPEG is lossy, so it's just going to throw away the detail instead of struggling with it. I'm not sure if it's possible to make something "hard for JPEG to compress" since it will just ignore anything that's too hard to compress at that quality level.

Something with hard edges at any scale would probably be better, like the infinite checkerboard plane:

infinite checkerboard plane

Also something with lots of colors. Maybe look at actual fractals instead of fractal noise. Maybe a Mondrian fractal? :)

Mondrian fractal

$\endgroup$
  • 1
    $\begingroup$ Thanks a lot! The fractal noise is definitely the kind of stuff I was looking for, but in my tests it is compressed well, I guess it could use more abrupt transition, instead of a heatmap-like smoothness. The checkboard's problem is that performance will really depend on which part of the cloth is taken in picture. Mondrian fractal is great, and the best-performing in my tests so far. Maybe it could use more colors and slightly different parameters. $\endgroup$ – Nicolas Raoul Apr 11 '12 at 15:05
  • $\begingroup$ @NicolasRaoul: Hmm.. Maybe Sierpinski carpet with colors? That's a common quilt pattern already. $\endgroup$ – endolith Apr 11 '12 at 15:45
  • $\begingroup$ A tessellation of Sierpinski triangles or squares might great indeed! $\endgroup$ – Nicolas Raoul Apr 12 '12 at 7:57
14
$\begingroup$

If we were talking about computer-generated images, noise would be the right approach. But here, there is the camera capture step.

The fractal bit is very important because of the scale invariance issue. It doesn't have to be truly fractal, though, if you consider there's a limited distance range at which the person is going to be photographed. I mean, if the person wearing the cloth is in the background of a picture, it won't have much impact anyway...

I think the best way to trick the JPEG encoder would be to have blocks with very high high-frequency coefficients that will survive quantization = a lot of details and sharp edges ; so the whole coefficient sequence has to be explicitly written (instead of an EOB at the 15th coefficient or so). Checkerboard pattern are a good way of achieving that. The only downside I see is that the low-resolution of the lens + the camera antialiasing filters have a good chance of blurring that! Everything should happen within 8x8 blocks (or 16x16 blocks chroma-wise) because JPEG doesn't do much at the macro scale. You have to make your 8x8 blocks as messy as possible, no matter how blurry the lens is going to make them.

Here is a suggestion:

scale-invariant, hard to JPEG-compress pattern

You might wonder what the less contrasted blocks are doing here, but they are helping keeping contrasted zone when the thing is zoomed out. The challenge here is to have something with a contrasted pattern no matter the viewing scale.

I have not formally evaluated this. The best way would be to have a script that takes the image, applies a dozen of crop/resize/blurs with various parameters, and spits the total size of the JPEGs.

$\endgroup$
  • $\begingroup$ Thanks a lot! Looks quite similar to my the concept of the picture in the question, actually, but much nicer. Any specific reason why the "fractality" is by factor 4? Is it better than factor 2? $\endgroup$ – Nicolas Raoul Apr 11 '12 at 15:09
  • $\begingroup$ no reason, I've just tried to make it look prettier with more color shades, so I started with a 4x4 square. $\endgroup$ – pichenettes Apr 11 '12 at 15:22
  • $\begingroup$ Any reason to choose squares instead of triangles? I am trying right now, triangles make lots of sharp edges, which I think is a good think. A low "fractality" could be reached with a hybrid triangle→rhombus→hexagon→triangle approach. I think a low factor is a good thing as it increases the probability for the camera to detect sharp shapes up to its resolution limit. $\endgroup$ – Nicolas Raoul Apr 11 '12 at 16:12
  • $\begingroup$ Squares was the easiest thing to code. I am not sure if other shapes have a better "edge density" than squares. $\endgroup$ – pichenettes Apr 11 '12 at 17:44
11
$\begingroup$

There is a difference between JPEG exploitable and Transform Compressible.

Take the white grainy noise of TV set for example.

A general white noise is spread maximum in the frequency and hence there is no better example than white noise that any transform domain coding technique cannot compress. If you take such noise and take DCT (or DFT if required) we shall find that the frequency domain is also wide spread and all co-efficients will have importance.

However, still no one stops you from being aggressive from quantization. This way, you can still discard heavy amount from the high frequency regions. The result will have heavy Mean-Square-error. However, perceptually it would still be noise. It might be heavily blurred though.

On the other hand, now take images where there are sharp edges.

Sharp edges will also have spread in the higher frequency (but may be it might just be little less than the former case). However, in trying to compress it and dropping of high frequency, now there will be sever impediments visually. It will introduce blurring of edges, ringing effect etc. While the bandwidth spread for such images is not the highest possible, For JPEG or any such equivalent compression, keeping such images perceptually equal quality will be tough.

For any lossy compression, tough and simple depends on how much and what type of distortion is tolerated.

$\endgroup$
  • $\begingroup$ Let's say my fabric is a 10^8x10^8 table of random black/white pixels. The camera takes a 10x10pixels picture of the fabric. Statistically, won't this 10x10 image have all pixels be a very similar grey, thus being easy to compress with less distortion (of any kind) than a less uniform image? $\endgroup$ – Nicolas Raoul Jun 20 '13 at 7:26
10
$\begingroup$

The composition below shows a fractal kind structure of the pattern. The every next picture is the result of averaging over each 2x2 pixels block of the previous one. The total character of the pattern remains the same but the image contrast is gradually decreasing. As it was said right earlier, the picture becomes grey when we zoom out.

Scaling behavior

But using the fractal property, we could overlay together several patterns of different resolution to maintain the image contrast to be stable within the range desired. Below is the example of 4-layer pattern (512x512 GIF). This result is more close to Brownian noise and also hardly JPEG compressible.

4 layer combination

$\endgroup$
5
$\begingroup$

My guess is that the worst compressible pattern would be white noise (with uniform distribution). It needs to look noisy on different resolutions, so you may create the noisy images in scale space and than put them together:

$$I=\sum_{i}^{n}N_{i}*G_{i}$$

Here $I$ is the final cloth image, $N_{i}$ is the image filled with white noise (different for every $i$) and $G_{i}$ is gaussian kernel of size $i\sigma$. The $*$ denotes convolution.

Maybe a better way to construct such image would be to work directly in frequency domain, thus:

  1. Create an image filled with white noise.
  2. Perform 8x8 block IDCT (Inverse Discrete Cosine Transform) on the image.

The result would be worst compressible pattern for JPEG, as it has highest entropy in the DCT domain. But I am not sure how this will behave under varying resolutions.

$\endgroup$
5
$\begingroup$

IIRC, the JPEG decompression algorithm is specified, however the exact compression algorithm is not. Different algorithms can produce a legal JPEG file. So you will need to test this on your chosen image compressor(s).

Anything can be compressed by the same amount by a lossy compressor, such as JPEG. It's just that, at any fixed compression level, the quality of the compression might vary (the noise or error in the decompressed result will increase) depending on the image . So you want something that adds a maximum amount of noise to the decompressed result. For this, you want the maximum error for removing high frequency macroblock coefficients and for quantizing any coefficients.

Which probably mean varying and high frequency pickets, as well as varying grey and color scales that happen to be between possible quantization levels of the given compressor at some given setting.

Since you want this to work at any distance in any lighting, you will need to vary the frequency of the pickets (perhaps fractal, or perhaps just ramped with random frequency modulation) and the color and gray levels (non-coherently, e.g. vary the colors and the levels independantly). The hues variance will less depend on the distance, so those just need to be picked to be worse case for your selected quantizer(s). The average size of the color patterns can be twice the size of the luminance patterns to match the 4:1:1(area) YUV macroblock composition.

I would start with a bunch of highly colored Moire patterns at wildly varying scales overlayed and/or patched together fractally.

$\endgroup$
2
$\begingroup$

Let me share the pattern that has a very flat spectrum (like the white noise). So this pattern is very hard to compress with JPG. The sample image below is enlarged 4 times.

The pattern itself is regular, but non-periodic, and could be easily generated by the deterministic algorithm. It also has a fractal property.

Non-periodic pattern with quasi white noise spectrum

Viewed from far away: original far

$\endgroup$
2
$\begingroup$

Random noise indeed compresses very poorly. You can produce it in color by generating independent R, G, B values.

Looking from a distance will indeed wipe away the noise (by lowpass filtering), and you can avoid that by generating noise images at different resolutions, i.e. using bigger and bigger pixels, and superposing them.

When adding the images, you face the problem of the range of values, which grows as the number of images, let N. If you just average them, the noise amplitude will decrease as 1/N.

If you choose uncorrelated uniform noise, the superposition will result in a quasi-Gaussian distribution with √N standard deviation, so instead of dividing by N, you can divide by √N (with suitable re-centering) to limit the amplitude reduction.

Lastly, I guess that it is better to let the values wraparound rather than saturating them, as saturated values will form large uniform areas.

$\endgroup$
2
$\begingroup$

Here is another approach gaining RGB Brownian noise (4096x4096 GIF). RGB Brownian noise

$\endgroup$
0
$\begingroup$

Amazing question! In concept, the white noise is a signal that do not change when it is time scaled. In same way a fractal don’t change when it is size scaled. A lossy compression process only takes the most important of the spectrum (time or size) not all, so fractal and noise smell like cookies. Therefore, you should play with the colors and patterns of your fabric They must be fractals and the fractal behavior must be white randomly generated. You should get a fabric that in photo looks black (in CMY color space) but in real world, it has a colorful pattern.

Good luck! , and if you get the anwser please post it!!!.

$\endgroup$
  • $\begingroup$ "You should get a fabric that in photo looks black" <- In that case, would not it be easily compressible? $\endgroup$ – Nicolas Raoul Nov 12 '18 at 0:39

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.