# <span class="orange">Digital Halftoning</span>

Goal: Render the illusion of a continuous-tone image based on two-tone (half-tone) display
- 
- The basic idea of digital halftoning: It’s a process used to simulate continuous tone imagery through the use of dots, varying either in size or in spacing, thus generating a gradient effect.
- The spatial modulation of gray levels is achieved by adjusting the **density of black points** in a given area—denser for darker areas and sparser for whiter areas.
- Halftoning is commonly used in printing and display technologies where only a limited number of colors (often just black and white) are available to recreate a wide range of tones.

## <span class="blue">**Patterning**</span>

In patterning, a gray-level pixel is represented by a matrix of dots (or a dot pattern).


If the dot pattern is a 4x4 matrix (p=4): Can represent 16 binary pixels and therefore 17 different levels (including 0). It implies that with a 4x4 matrix, you could represent up to 256 different gray levels by varying the number of dots that are 'on' in each pattern.


Four steps in the patterning process:
- **Read** in the given grey-level image.
- **Quantize** the image, likely reducing the number of gray levels to a number that can be represented with the available patterns.
- Design a **patterning table**, which is a collection of dot patterns corresponding to the different quantized gray levels.
- **Map** each pixel to its corresponding pattern from the patterning table.
---
- Simplier than dithering and error diffusion.
- **Generates an image with higher spatial resolution:** Spatial resolution refers to the number of pixels used to represent an image. By replacing each original pixel with multiple dots, you're increasing the number of distinct points of data, thus increasing the resolution.

## <span class="blue">**Dithering**</span>

Dithering is an intentionally applied form of noise used to randomize quantization error, preventing large-scale patterns such as color banding in images

- 

- A mathematical function or flow is illustrated, where `F(j,k)` represents the original pixel values, `N(j,k)` represents noise added to the pixel values, and `H(j,k)` is the sum of the pixel value and noise. After applying a threshold, you get `G(j,k)`, the output dithered image.

**Why Adding Noise**:
- By introducing variability, it breaks the monotonicity of gray levels and adds texture, which can result in a more visually appealing image.
- Adding noise can shift pixel values around the threshold, allowing for a more nuanced conversion.

**Noise Type**:
- Different types of noise can be used in dithering: white, pink, and blue.
- 

**Adaptive Thresholding**
- A dither matrix is a grid of numbers that define the pattern of how pixels will be turned on or off.
- Matrices with values that determine the threshold levels.
- Used in the dithering process to create the patterns of dots that form the final image.
- 
- 0->lowest threshold, 3-> highest threshold
- Adaptive thresholding involves generating a threshold matrix based on a dither matrix, which determines which pixels will be turned on (black) and which will be off (white) in the dithered image.
- The process is non-random and can involve region-to-region mapping, where specific areas of an image have different thresholding behaviors based on the dither matrix.

if img_pixel[y][x] > dither_m[i][j]:
                img_pixel[y][x] = 255
            else:
                img_pixel[y][x] = 0

**General Form of NxN Dither Matrix**:
- To construct larger dither matrices from smaller ones by scaling up the values and repeating the pattern. This is useful for dithering images that are larger or have higher resolution.
- How to construct a 4x4 dither matrix from a given 2x2 matrix.
- 

**Determining the Threshold Matrix**
- 
- The formula to convert a dither matrix into a threshold matrix. This matrix will be used to determine which pixels will be on or off in the final image.

**Dithering Application**:
- An input image matrix with gray values is shown alongside its corresponding threshold matrix, and the resulting output image after dithering is applied.
- The output image illustrates the binary nature of the dithering process, with pixels either being completely black or completely white based on the threshold matrix.
- 

## <span class="blue">**Error diffusion**</span>
1975 Floyd & Steinberg

**Error Diffusion Framework**
- This is a popular algorithm for blue noise dithering.
- 
- **Process flow:**
- `F(j, k)` represents the original pixel value. It is combined with an error term from the adjacent processed pixels `(F + E = F~)`. The modified pixel value `F~(j, k)` is then thresholded to produce a binary output `G(j, k)`.
- If the normalized value `F~(j, k)` is greater than or equal to 0.5, the output `G(j, k)` is set to 1 (white); if it's less than 0.5, the output is set to 0 (black).
- The quantization error is then diffused to neighboring pixels that have not yet been processed.
- The error `E(j, k)` is defined as the difference between the original and the thresholded values, `F~(j, k) - G(j, k)`.

 if x < width - 1:
                image[y, x + 1] += error * 7 // 16
            if x > 0 and y < height - 1:
                image[y + 1, x - 1] += error * 3 // 16
            if y < height - 1:
                image[y + 1, x] += error * 5 // 16
            if x < width - 1 and y < height - 1:
                image[y + 1, x + 1] += error // 16

**Error Diffusion with Serpentine Scanning**:
- Serpentine scanning (also known as boustrophedonic scanning) , which is a technique where the scanning direction alternates with each row.
- 
- The error diffusion pattern is reversed on alternate lines to match the scanning direction.
- By alternating directions, serpentine scanning helps distribute the quantization error (the difference between the actual grayscale value and the binary color assigned to a pixel) more evenly across the image.
- This can reduce visual artifacts—unwanted patterns or structures in the image that aren't present in the original. Visual artifacts often occur in error diffusion due to the consistent direction of error propagation; they can appear as patterns of dots or streaks that create a distracting appearance.

## <span class="blue">**Multi-scale Error diffusion**</span>

**Standard Error Diffusion:** operates on the image at a single scale, i.e., the original resolution.

**Multi-Scale Error Diffusion:**
- Considers the image at multiple scales, creating a hierarchy of images from coarse to fine. Each scale is a reduced resolution version of the original image.
- Starts processing from the coarsest level (lowest resolution) of the image, diffusing errors, and then moves to the finer levels (higher resolutions).
- By considering multiple scales, it aims to better preserve the global structures and textures of the original image while still capturing fine details in the higher resolutions.

**Multi-scale Error Diffusion - Issues**
- The technique deals with region-to-region mapping and operates at multiple resolutions to preserve image details across scales.
- It's presented as a time series or causal error diffusion process, implying that the process is applied sequentially across the image, with earlier decisions affecting later ones.
- Whether non-causal error diffusion could be a possibility, hinting at a potential exploration into diffusing errors without following the sequence of the pixels, which could potentially avoid some types of artifacts.

**Problem Set-Up**
- 
- The setup involves an input image `X(i, j)` with values normalized between 0 and 1, an output binary image `B(i, j)` with values of 0 or 1, and an error image `E(i, j)` representing the difference between the input and the output images.
- **Down-Sampling to Various Resolutions:** The original image is down-sampled to create a pyramid of images, each with a lower resolution than the one before. This could be done by averaging pixel values over neighborhoods, reducing the image by a factor of two in each dimension, for example. The result is a set of images at different scales, from the original down to the coarsest (smallest) level.
- **Recursive Relationship:** These multiple resolutions create a hierarchy where each level is related to the one below and above it. For example, a pixel at a coarser level is related to a 2x2 block (if down-sampling by 2) at the finer level. The value of this coarser pixel can be the average of the four pixels it corresponds to at the finer level.
- **Computing Pixel Values:** At each level, starting from the coarsest, the image is binarized (converted to 0s and 1s), and the resulting quantization error is calculated. This error is then diffused up or down the pyramid. When diffusing down, the error affects how the finer resolution pixels will be binarized. When diffusing up, it affects the coarser level by adjusting how the larger scale structures are formed. By diffusing errors across scales, the algorithm aims to maintain consistency between the binarization at different resolutions, ensuring that errors at one level don't cause inconsistencies at another level.

**Multi-Scale Process**
- 
- The multi-scale process is depicted as a pyramid, with `X` as the input at various scales, `B` as the corresponding binary output, and `E` as the error at each scale.
- 
- The goal of this process is to minimize the error across all scales, potentially to improve the visual quality of the halftoned image by preserving details and reducing artifacts that are common with single-scale error diffusion.

**Steps of the Multi-Scale Error Diffusion**
1. The steps include initializing the output image pyramid to zero, which means starting with no assumption about the binary output.
2. Dot assignment is performed where the error is distributed from the higher levels of the pyramid to the lower levels, allowing large-scale structures to inform finer details. 1 parent node distributes its dots (integer numbers) to 4 children. (2i~k~+i, 2j~k~+j)
3. The error diffusion process then follows with defined filters, where the error from the binary quantization is spread out to adjacent pixels, just as with standard error diffusion.

**Quality Management**:
- Quality metrics, specifically a Mean Squared Error (MSE) vector, provides a **measure of error** at each level of the pyramid.
- It's important to preserve the contrast of the original image and not over-smoothing, which can be an issue with other halftoning methods.
- 

The Multi-Scale Error Diffusion (MSED) is an extension of the error diffusion technique used for halftoning grayscale images. In traditional error diffusion, the quantization error from each pixel is propagated to its neighboring pixels in a fixed manner, typically using a predefined diffusion matrix. However, in MSED, multiple diffusion matrices are used at different scales to better distribute the error and achieve higher-quality halftoning results.

The Multi-Scale Error Vector Diffusion (MSEVD) is a variation of MSED that uses a different approach to distribute the quantization error. Instead of propagating the error directly to neighboring pixels, it calculates an error vector for each pixel based on its gradient direction and magnitude. The error vector is then distributed to neighboring pixels based on their relative positions and orientations.

Here's a simplified explanation of how MSEVD works:

1. **Gradient Calculation**: Compute the gradient magnitude and direction for each pixel in the grayscale image. This information represents the local contrast and structure of the image.

2. **Error Vector Calculation**: For each pixel, calculate an error vector based on its gradient direction and magnitude. The error vector represents the difference between the original grayscale intensity and the quantized value.

3. **Error Vector Diffusion**: Distribute the error vector to neighboring pixels based on their relative positions and orientations. The diffusion process takes into account the gradient direction and magnitude of both the current pixel and its neighbors.

4. **Update**: Update the intensity values of the neighboring pixels by adding their respective portions of the error vector.

5. **Repeat**: Repeat steps 2-4 for all pixels in the image, propagating the error vectors throughout the image.

6. **Output**: The final result is a halftoned image with smoother gradients and reduced artifacts compared to traditional error diffusion methods.

MSEVD is particularly effective at preserving fine details and textures in the halftoned image while minimizing artifacts such as contouring and patterning. It offers improved image quality and better control over the halftoning process compared to single-scale error diffusion techniques.

Implementing MSEVD requires more complex algorithms and computations compared to traditional error diffusion methods. It involves analyzing the gradient information of the image and designing sophisticated diffusion strategies to distribute the error vectors effectively.

<style>
.blue {
color:#79CCEE;
}
.orange {
color:#F68F02;
}
.pink {
color:#FE9FA1;

}
.yellow {
color:#FDB515;
}

.purple {
color:#BAA2ED;
}
.block {
margin-left : 1em;
}

</style>