Blue noise is not Random Numbers. It is a Number Sequences with Less Bias and More Variety than Random NumbersWe will explain our developed program for generating huge blue noise at high speed.
Blue noise refers to a sequence obtained by applying extensive calculations to random numbers. It is the most "varied and unbiased" sequence based on human sensory perception.
Blue noise is "more varied and unbiased" for human sensory perception and psychology than random numbers.
|White Noise and Blue Noise|
|White Noise (rand() function)||Blue Noise (bluenoise() function)|
|Enlarged Portion of White Noise and Blue Noise|
|White Noise (rand() function)||Blue Noise (bluenoise() function)|
Because it is independent of the preceding wins, even if there have been more than 10 consecutive losses, it is not surprising.
This is why the distribution becomes biased, as shown above.
Blue noise is a processed sequence using random numbers until the bias disappears. It can control the probabilities without bias, such as 1 "win" every ten times, 2 consecutive "wins" every hundred times, 3 consecutive "wins" every 0.001 times, and 4 consecutive "wins" every 0.0001 times.
It can also easily control to prevent more than 10 consecutive losses.
Blue noise is a sequence that can achieve the arbitrary control of occurrence probabilities, making it feel "varied and unbiased" for humans compared to random numbers.
- What is blue noise? A sequence that is "varied and unbiased" compared to random numbers based on human sensory perception...
- What is blue noise used for? So far, it has been used to accelerate and improve the quality of dithering...
- The high-speed generation algorithm of blue noise It achieves 10 to 1000 times faster generation than the commonly used algorithms...
- What can blue noise be used for in the future? Character placement in games, gacha, initial values of deep learning parameters...
What is blue noise?
Blue noise is not random numbers. It is a sequence of numbers generated through extensive calculations starts from random numbers, resulting in a "uniformly distributed and random-looking" sequence.
While random numbers can be generated in real-time to some extent, it is not possible to generate blue noise in real-time due to computational constraints.
It is necessary to precalculate and prepare a numerical matrix called a blue noise matrix, which is an M×N value matrix.
There may be concerns about always using the same blue noise, but such worries are unnecessary.
A subset of blue noise is still blue noise, and connecting multiple blue noise sequences also yields blue noise. Therefore, mechanisms like srand(seed) in random numbers can be easily implemented.
We offer programs for generating matrices of sizes 4096×4096, 8192×8192, and 16384×16384. Alternatively, we can provide the matrices themselves.
The white noise image on the left was generated using pseudo-random numbers from a computer. The TV static screen is an example of white noise.
Displays a random number sequence generated by rand function. It appears visually biased and not completely random to human perception.
Blue noise obtained by processing white noise. It appears visually random and uniformly distributed to human perception.
To the human eye, the distribution of dots appears biased and creates a pattern-like structure. Some people may see it as a long-haired female ghost.
|White noise that appears as something||Blue noise that appears as nothing|
In the blue noise screen, even with the same density of sand, no pattern-like structure is visible at all.
What has it been used for.Dithering is a technique used in the printing field, where grayscale images are printed with black and white ink, and color images are printed with CMYK inks with four different levels of shades.
One high-quality dithering method is called Error Diffusion. Error diffusion is a method that adjusts the error between a specific pixel and the dithering output by the next pixel, in order to minimize the total error.
Although it is high-quality, it has a large computational cost and a complex algorithm, making it difficult to implement in circuits.
In contrast to error diffusion, there is a technique called Ordered Dithering. This method determines whether to output a pixel based on the comparison of one element corresponding to a pixel and a random array, and it has a lower computational cost and is easier to implement in circuits.
However, when white noise is used in ordered dithering, the output quality is lower than that of error diffusion.
|Original Image||Error Diffusion||Ordered Dithering (Using White Noise)
It uses the rand function (pseudo-random), and visually appears as a dirty image.
Using blue noise matrix, it is possible to create a high-speed, simple, and high-quality ordered dithering system.
For each pixel, simply referring to one element of the blue noise array and performing a comparison of sizes can give the output value.
|Original Image||Error Diffusion (2-levels)||Ordered Dithering (Using Blue Noise, 2-levels)||Ordered Dithering (Using Blue Noise, 4-levels)|
|Original Image||Error Diffusion (4-levels)||Ordered Dithering (Using Blue Noise, 4-levels)|
Comparison of Error Diffusion and Blue NoiseError diffusion produces sharp images but can result in banding in gradient areas.
Blue noise, on the other hand, produces slightly noisy images compared to error diffusion. The addition of noise in gradient areas leads to smoother transitions.
To improve the banding in error diffusion images, a process of adding random noise to the error distribution is implemented, resulting in images similar to those produced by blue noise.
In terms of processing time, the simple algorithm of blue noise is significantly faster than error diffusion.
A program for quickly generating the threshold matrix for blue noise (in a 256x256 matrix, for example) is also provided, allowing for customization.
Blue noise generated by our program is used in the firmware of large-scale printers.
In addition to dithering, blue noise can also be used for audio noise processing.
Blue noise possesses the following properties:
- Some of the blue noise is blue noise.
- When blue noise matrices are connected together, they still form a blue noise matrix. Connecting the right side to the left side and the top to the bottom does not result in areas of low or high density.
- However, a larger blue noise matrix is generally of higher quality. If the screen size is 4096x2048 and a 32x32 blue noise pattern is repeated, the repeating pattern becomes noticeable.
These two properties allow for the easy generation of different blue noise sequences, similar to using different random number seeds.
Even if the starting point for accessing the blue noise array (matrix) is changed from 0, a complete blue noise sequence can still be obtained. Even when going back from the end to the start of the sequence, the integrity of the blue noise sequence is preserved.
In other words, by simply using modulo calculations to access the array, the same functionality as a seed can be achieved.
If the scale of the blue noise is 16384x16384, the probability of producing the same blue noise sequence by repeating the seed is only 1 in 270 million.
|8x8 blue noise||256x256 blue noise|
Ultra high speed blue noise generatorThe conventional algorithm uses the void-and-cluster algorithm.
Starting from a n × m pixel white noise, the algorithm repeatedly selects one pixel from the most dense region and moves it to the least dense region until there are no movable pixels left.
|Departure: White noise||Most dense pixel in red||Most dense pixel in blue||Movement||Result of movement|
Until convergence, a large amount of calculations are required, and it takes one month for a size of 8192 × 8192 pixels, and several months to years for larger sizes.
It is not possible to parallelize the calculations because the coarse-to-fine situations change with each pixel movement.
Our developed high-speed blue noise generation algorithm creates a matrix at a speed of 10 times (256 × 256) to 1000 times (16384 × 16384) or more compared to the conventional algorithm. The improvement in speed ratio becomes more significant as the matrix size increases.
The high-speed algorithm requires a large amount of memory. The maximum matrix size that can be created is:
- For grayscale (1 plane), approximately 8192 × 8192 on a machine with 6 GB memory.
- For grayscale (1 plane), approximately 16384 × 16384 on a machine with 16 GB memory.
- For 4 planes (CYMK), approximately 8192 × 8192 on a machine with 8 GB memory.
- For 3 planes (RGB), approximately 16384 × 16384 on a machine with 24 GB memory.
The processing speed is:
- 10 seconds for generating 256 × 256 blue noise.
- 40 seconds for generating 512 × 512 blue noise.
- 160 seconds for generating 1024 × 1024 blue noise.
- 2560 seconds for generating 4096 × 4096 blue noise.
What can it be used for?
- Utilization in game middleware development companies Game middleware refers to libraries and development support tools for the development of mobile and game consoles.
- Using blue noise for the initial values of deep learning parameters
Although the details are unknown, it is thought to involve controlling the placement of game characters and the occurrence frequency of big wins (gacha).
It is used to generate phenomena that are "randomized in a way that is unbiased to human perception" rather than using random numbers.
By simply setting multiple thresholds, it is easy to control the occurrence probability of the phenomenon of continuous big wins.
For example, a probability event where a big win occurs once every 11 times, a big win occurs once every 44 times, and a big win occurs three times in a row every 176 times appears "visually random" with blue noise. Naturally, there will never be more than 10 consecutive losses.
The control of character placement can also be achieved by comparing it with thresholds to ensure it is unbiased or intentionally biased.
- Shortening the time until convergence of learning
- Preventing falling into local optima