AI Roadmap LLM Learning Roadmap
✨ Awesome-Anything
Awesome-AI-Tutorials
Awesome-AI-Researchs
Awesome-GitHub-Repos
Awesome-AI-Examples🖼️ Digital Image Processing
DIP I Image Demosaicing and Histogram Manipulation
DIP II Image Denoising
DIP III Edge Detection
DIP IV Digital Half-toning
DIP V Geometric Image Modification🍃 LLM Components
1.1 Tokenization
1.2 Embedding
1.3 Attention
1.4 FFN, Residual Addition, and LN
1.5 Positional Encoding
1.6 Architecture & Decoding Policy🌱 LLM Pre-training
2.1 Pre-training Definition
2.2 Pre-training Data
2.3 Pre-training Workflow
2.4 Continued Pre-training (CPT)
2.5 Pre-training Evaluation☘️ LLM Post-Training
3.1 Supervised Fine-Tuning (SFT)
3.2 Reinforcement Learning
3.3 RLHF: Reinforcement Learning from Human Feedback
3.4 Optimizing PPO-Based Algorithms
3.5 Direct Preference Optimization (DPO)🍀 LLM Popular Models
4.1 BERT & Variants
4.2 PaLM Series
4.3 GPT Series
4.4 LLaMA Series
4.5 GLM Series
4.6 Qwen Series
4.7 DeepSeek Series
4.8 MOE Series
4.9 Other🪴 LLM Applications
5.1 Prompt Engineering
5.2 LLM-based Agents
5.3 Retrieval-Augmented Generation (RAG)
5.4 Enterprise-level RAG Practice (I)
5.5 Enterprise-level RAG Practice (II)🌿 LLM Optimization
6.1 GPU Usage Analysis
6.2 Latency Analysis for Inference
6.3 FlashAttention
6.4 PagedAttention
6.5 Packing for Efficient Training
6.6 PEFT🌾 LLM Compression
7.1 Quantization
7.2 Pruning
7.3 Knowledge Distillation🌵 LLM Hands-on Practice
8.1 nanoGPT: Training a GPT from Scratch
8.2 Instruction Fine-Tuning Qwen3-0.6B: A Minimal Working Example
8.3 OpenRLHF: SFT Qwen3-0.6B and Code Analysis
8.4 OpenRLHF: Reward Model Training and Code Analysis
8.5 OpenRLHF: PPO Tutorial and Code Analysis🌴 LLM Must-read Papers
9.1 Technical Reports Explained
9.2 MedLLM
9.3 o1 Techinical Paper
9.4 Prompting
9.5 LLM-as-Judge🌳 LLM Q&A
10.1 Why GRPO training loss starts at 0
10.2 VLM-R1 Reproduction Results
10.3 KL(P||Q) or KL(Q||P)?
10.4 Left Padding or Right Padding?
10.5 What is QK-Norm?
10.6 Why LLM training rarely adopts Dropout?
10.7 Dropout and DropPath🐝 VLM Image Encoders
11.0 Introduction
11.1 Vision Transformer
11.2 CLIP
11.3 BLIP
11.4 EVA
11.6 BLIP-2
11.7 SigLIP📝 MISC.
OpenAI ChatGPT Progression
DIP IV Digital Half-toning
I. Motivation
Originally, the technique of digital half-toning was to reproduce gray-level images on devices with limited color resolution (only black and white), such as printers. Afterward, some people also developed algorithms for half-toning RGB images. The reason for doing these is because of the nature of printing, which can only decide whether to drop ink at a pixel location or not. Therefore, it’s not realistic to put 50% or 80% of a drop of ink and cannot print gray-scale images.
The digital half-toning is used to solve this problem. Besides, different printers also have varying quality and printing resolution because of price and manufacturing. A better half-toning algorithm can render images better, especially when the printing resolution is low. The reason that such methods actually work is that the human eye functions as a low-pass filter, which makes discretely represented images look continuous and realistic.
Because the printer has become more advanced and has more colors available, such as cyan, magenta, yellow, and black (CMYK), the demand for color half-toning emerges. Color half-toning is a widely used technique in commercial printing, as it allows the printing of high-quality color images on low-cost printers with high-resolution printing ability.
II. Algorithm
(a) Dithering
Three methods of half-toning will be used in this section: fixed thresholding, random thresholding, and dithering matrix.
The idea of fixed thresholding is simple, just using a fixed value between 0 to 255 for thresholding each pixel value in the image, which is formulated as follows.
Where is the value of the threshold, and are the pixel values of the input image and output image, respectively, at the location of . The is the location on the y-axis (height), and the is on the x-axis (width).
The random thresholding is basically the same as fixed thresholding, except for the randomly varying threshold for each pixel value. It can be formulated as follows.
Where the represents the random threshold at the location of and the threshold is distinct for each pixel. Usually, the uniform distribution will be chosen to generate the random threshold because other distribution has some
“priority” to a certain range of values and will affect the overall performance of thresholding.The dithering matrix is fixed given a specific size. The most basic building block of the dithering matrix looks like this:
Where the value represents the approximate threshold for a pixel, the rules are like this: the value of 0 is more likely to transform a pixel value to 255 than the value of 3. Based on this, a larger-sized dithering matrix can be built. The formula for this process is:
We will use the dithering matrices of , , and . For obtaining the final threshold matrix for each dithering matrix, the following formula is used:
Therefore, the dithering matrix of is:
The dithering matrix of is:
After obtaining the corresponding threshold matrices for these dithering matrices, we can apply them to the image that needs dithering. This process is done repetitively across the full image because the image is usually larger than the size of the matrix. The dithering formula is:
Where the represents the threshold matrix derived from the dithering matrix.
<ins/>
(b) Error Diffusion
Error diffusion algorithm uses a clever way to achieve half-toning by making the neighborhood pixels belong to different categories (0 or 255). To do this, the error from previously processed pixels would be passed to a few next and neighbor pixels. The provided error would push these pixels in a different direction.
For example, one pixel valued at 200 would be classified as 255 and generate an error of -55 (200 - 255). This error added to the next neighborhood pixels would push them to 0 to make them classified differently from the current pixel (valued at 200) and hence achieve a half-toning effect; similarly, a pixel value at 100 would be classified to 0 and have an error of 100 (100 - 0), which pushes its neighbors to 255.
To do this easily, there are three common error diffusion matrices:
Floyd-Steinberg (FS), Jarvis, Judice, and Ninke (JJN), and Stucki. The first one is with a size of 3 by 3, and the latter two have sizes of 5 by 5. The FS looks like:The JNN is formulated as:
And the Stucki is like:
This algorithm can be performed on images with a scale of either 0-1 or 0-255, which would generate the same results. Here let’s assume it’s from 0 to 255. For each pixel
- Binarize the pixel value to 0 or 255 based on the threshold of 127.5;
- Calculate the error by subtracting the binarized value (255 or 0) from the pixel value;
- Diffuse the error to its neighbor pixels according to the chosen matrix. These errors are multiplied by the value in the matrix and diffused to corresponding pixels directly, which means that the neighbor pixel values will be changed accordingly;
- Repeat 1-3 for the next pixel.
There are also multiple ways to iterate through the image:
Raster parsing, Serpentine parsing, and Hilbert curve. The last one is the most complex pattern. The Raster parsing method just iterates each row of images in sequence from top to bottom and from left to right within each row. The Serpentine parsing also iterates rows from top to bottom, but for each row, it iterates from left to right and right to left, alternatively. We will use the Serpentine parsing here.<ins/>
(c) Separable Error Diffusion
The separable error diffusion method is a baseline for color image half-toning, and it’s straightforward.
It can be implemented as follows:
- transform RGB image to CMY (C, M, and Y can be acquired by 255-R, 255-G, and 255-B, respectively);
- split CMY image to 3 different channels;
- apply the error diffusion method on each channel of C, M, and Y;
- combine the half-toned C, M, and Y channels to the half-toned CMY image;
- transform the half-toned CMY image to the final half-toned RGB image.
Note that the final half-toned image only contains 8 types of pixels:K (0, 0, 0),R (255, 0, 0),G (0, 255, 0),B (0, 0, 255),C (0, 255, 255),M (255, 0, 255),Y (255, 255, 0), andW (255, 255, 255).
(d) MBVQ-based Error diffusion
The overall steps of this Minimal Brightness Variation Quadruple (MBVQ) error diffusion algorithm can be concluded as: for each pixel with RGB values
- determine the quadruple that the pixel (without adding diffused error) belongs to, which could be RGBK, WCMY, MYGC, RGMY, RGBM, or CMGB;
- find the closest vertex using a decision tree criterion to the RGB + diffused error values;
- compute the error value for this pixel and diffuse it to neighbor pixels just as the usual error diffusion method, where the error in R, G, and B should also be diffused to neighbors’ R, G, and B channels, respectively.
Quadruple. There are six quadruples in the color cube representation:
RGBK, WCMY, MYGC, RGMY, RGBM, and CMGB. These six quadruples are not overlapped with each other and split the cube into fix parts. The reason to choose these fix quadruples is to try to split the cube into a few parts with minimal change of brightness from CMYW, MYGC, ..., to KRGB, as shown below.
Closest vertex. To find the closest vertex, a decision tree-based criterion is used for tessellation, which is based on the tessellation, where the decision planes defined within the color cube representation are also applicable to other regions in the space. The construction of the decision tree is relatively straightforward: it involves uniformly splitting the points in the given quadruple using planes. These planes may require explicit mathematical expressions. Here we will just provide the decision tree in the experiment section.
<ins/>
III. Experiment
(a) Dithering
Example Code (C++)
- Algorithms of fixed, random, and dithering half-toning
- Define the dithering matrix, which is created recursively
- Define thresholding matrix
Inputs
Results
The result from fixed thresholding in Figure 15 seems not bad as well when the threshold value is 98, but the biggest problem of this method is robustness. We need to choose a threshold for each different image to obtain a better half-toned version. Besides, if take a closer look, we can see that the half-toned image from fixed thresholding is not good enough. With the threshold of 98, the texture of the sky is not visible because such an area has higher values than other areas; with the threshold of 158, the sky looks more distinguishable, but the texture of the stone is gone. This problem is common when using a single value for thresholding the image because lots of information will be removed from this behavior.
The result from the random thresholding in Figure 16 is more pleasing than that of fixed thresholding. At least we can clearly see that the texture of both stone and sky is much more visible. But the problem is evident as well: a noise-like appearance. The half-toned image looks like we added a pepper and salt noise over the original image. But anyway, the result is still more decent than that of fixed thresholding because it keeps more information about the original image. This kind of noise will not be so obvious with higher-resolution images.
According to the result of the dithering matrix in Figure 17, it achieves the best visual performance over the three methods of half-toning. Major information of the original image is kept and no obvious pepper and salt or Gaussian noise is seen on the result. However, we can still see some drawbacks of this algorithm. If we take a closer look at the sky area in the three images, it’s easy to see that there are rectangular patterns. The smaller the thresholding matrix is, the more evident the pattern becomes. This is because of the nature of this algorithm: applying a thresholding matrix across the whole image repetitively. The rectangular pattern is produced from the boundaries between two thresholding matrices. With a bigger matrix, the pattern would not be so obvious.
Overall, according to the results shown in Figures 15, 16, and 17, it’s easy to see that the result from the dithering matrix is much more visually pleasing and decent than the other two baselines.
<ins/>
(b) Error Diffusion
Example Code (C++)
- Define error diffusion matrices
- Define error diffusion function and diffuse function
Inputs
Results
As shown in Figure 18, the three half-toned images are all extremely visually pleasing. It’s hard to say which is better than another. This is partially because the presented images are small, which conceals many details.
To take a closer look, as shown in Figure 19, we can see that in the sky area, the FS and Stucki matrices both generate some continuous gray artifacts between the clouds, but the result of JJN is more natural and has no such artifacts. (It’s better to zoom in to look)
This problem can also be seen in the stone area, as shown in the second row in Figure 19. Especially in the highlighted spot, the same continuous gray artifacts appear in FS and Stucki-generated images, but not on the result from the JJN. The so-called continuous gray artifact is not really grey but an area that has repetitive patterns gathered together. The FS and Stucki both generate such repetitive patterns in certain areas. From this point, the JJN-generated half-toned image looks more decent and visually pleasing than that from the JS and Stucki.
Compare with the Dithering method. Even with some repetitive patterns sometimes, as in FS and Stucki, the overall visual quality from the error diffusion method is still much better than that from dithering matric or fixed and random thresholding. The result from dithering with a large matrix size may look good, but it naturally has rectangular patterns over the whole image. The FS and Stucki-generated results only have repetitive patterns in a few areas at most. And the JJN-generated half-toned image looks the best over all the methods and algorithms.
<ins/>
(c) Separable Error Diffusion
Example Code (C++)
- Define
RGB_CMY_exchangefunction and util functions
- Define workflow
Inputs
Results
The overall appearance of the result looks decent. We didn’t see any obvious artifacts of this baseline method because the resolution of the image is large enough, which makes it more pleasing when we present it in a smaller solution. We know that the error diffusion is done in each channel, so the half-toning process didn’t consider the relationship between channels.
When compared to the MBVQ method, the difference between these two methods is that MBVQ limits the quantization of a pixel value (with diffused errors) to a certain quadruple, which is determined by the original RGB value of that pixel. However, the separable error diffusion didn’t limit it, which means the possible range of values will be larger. In other words, the brightness variation will be larger. This can lead to more color noise in the local area in an image. This will be explained with some comparisons in the next section.
<ins/>
(d) MBVQ-based Error diffusion
Example Code (C++)
- Define main functions
- Define decision tree
Inputs
Results
The motivation for this method is that any color in each pixel could be rendered with no more than 4 colors. 4 colors can compose a quadruple in a color cube representation, so we can quantize a given color to one of the colors in the quadruple. The problem is that the 4 colors used to render a color are not unique. How can we choose a good set of 4 colors for each color uniquely and effectively? This is where the Minimal Brightness Variation Quadruple (MBVQ) comes in. We split the color cube representation into 6 parts, each of which is a quadruple and does not overlap with others. The 6 quadruples can be ordered in brightness, where we can find that the brightness increment between them is minimal.
But why do we want to split them to obtain a minimal increase in brightness between quadruples? The reason is that “our human visual system is more sensitive to changes in brightness than to changes in the chrominance”. Therefore, if we can quantize the pixels into colors that have a minimal increase in brightness, the visual quality of the half-toned image will be more natural.
The result from the MBVQ-based error diffusion is shown in Figure 21. The differences between this one and the baseline are not obvious if we only focus on the overall appearance with a small resolution. Let’s take a closer look.
The first one is the fisheye area, as shown in Figure 22. It’s easy to see that there are many black-and-white colors in that area in the baseline result (left). This is because of the large variance of the brightness between quantized colors. But in the result of MBVQ, almost no white colors can be seen, because the pixel values in this local area are limited to a quadruple, where white color does not exist, so the white colors didn’t appear. Obviously, the MBVQ-generated half-toned fisheye is better because the color changes are smoother and more natural in such a local area.
As for the fish body area, as shown in Figure 23, the same situation can be seen. The strips in the baseline result contains black dots not just on the strips, but also between the strips. This can be seen as color noise. But in the MBVQ-generated result, the black dots reasonably only appear on the strips, where need some black color pixels because the area is with lower brightness in the original image.
IV. Source Code
All inputs and results are in
.raw file form and we provide an online tool to visualize it: raw2image.Colab link. Warning: the installation of OpenCV on Colab requires more than one hour. If you’d like to run the code, installing locally with for example Docker is recommended.
Prev
DIP III Edge Detection
Next
DIP V Geometric Image Modification
Loading...