Normalize Image

1. Background Knowledge

In computer vision, a digital image can be thought of as a matrix (for grayscale) or a tensor (for color) of pixel values. Depending on how the image is stored, these pixel values might be in different ranges: for example, integers in $[0, 255]$ for 8-bit images, or possibly other numeric ranges if the image has been processed before. Many algorithms (especially in machine learning and deep learning) work best when inputs are scaled to a standard numeric range.

Normalization is a simple linear transformation that rescales values into a target range, often $[0, 1]$. The formula given,

$$I_{\text{norm}} = \frac{I - I_{\min}}{I_{\max} - I_{\min}},$$

takes the minimum pixel value in the image to 0 and the maximum to 1, and maps all other pixels proportionally in between. This is called min-max normalization and helps make different images comparable and numerically stable for downstream processing.

---

2. Algorithm / General Approach

The general pattern for this type of problem is:

• Compute global statistics over the input array (here, the minimum and maximum pixel values).
• Apply a vectorized transformation to all elements using those statistics.
• Return the transformed array with the same shape as the input, but with values now guaranteed to lie in the desired range $[0, 1]$ (assuming a non-degenerate case where $I_{\max} \neq I_{\min}$).

This is typically implemented using array operations (e.g., with NumPy, PyTorch, etc.) rather than looping pixel by pixel.

---

3. Step-by-Step Strategy

Assume the input is something like a 2D (grayscale) or 3D (color) array image:

1. Compute min and max

• imin = image.min()
• imax = image.max()

2. Handle edge case where all pixels are equal

• If imax == imin, then the image is constant. There is no range to scale.
• In this case, you might:
• Return an array of zeros (all pixels become 0), or
• Return the original image, depending on the problem specification.

3. Apply normalization formula

• Compute the denominator: range_val = imax - imin
• Normalize:

norm_image = (image - imin) / range_val

4. Ensure numeric type

• If the original was integer, ensure you cast to a floating type before division so you don’t get integer division.

5. Return the normalized image

• Shape should be unchanged; only values are rescaled.

---

4. Common Pitfalls

• Integer division: If image is an integer array and you do (image - imin) / (imax - imin) in a language that defaults to integer division, all values may become 0 or 1 incorrectly. Convert to float first.
• Zero denominator: When imax == imin (flat image), division by zero will occur unless you handle that case explicitly.
• Per-image vs. global normalization: The formula here is for normalizing per image. Don’t mistakenly use a fixed I_min and I_max from somewhere else unless the problem explicitly asks for it.
• In-place modification: If you modify the input array in place, it may affect other parts of the code that rely on the original image. Decide whether you should create a copy or safely work in place.

---

5. Time & Space Complexity

• Time complexity:

• Computing min and max over all pixels: $O(N)$, where $N$ is the total number of pixels.

• Applying the normalization to each pixel: $O(N)$.

• Overall: $O(N)$.

• Space complexity:

• If you create a new normalized image array: $O(N)$ extra space.

• If you normalize in place (and allow changing the original), extra space is $O(1)$ beyond the input storage.