Haar Transform

 

---

1. What is the Haar Transform?

The Haar Transform is a type of wavelet transform. It’s used to:

• Represent data in terms of averages (low-frequency components) and differences (high-frequency components).
• Analyze signals, images, or data for compression and feature extraction.

In simple terms, the Haar Transform splits a dataset into “smooth” parts and “detail” parts.

• Low-frequency (average): The overall trend or smooth part of the data.
• High-frequency (difference): The details, edges, or sudden changes.

It’s especially simple because it uses only additions, subtractions, and division by 2, making it fast for computers.

---

2. 1D Haar Transform (for a vector)

Take a simple array:
[
[4, 6, 10, 12]
]

Step 1: Compute averages and differences for pairs of elements:

• Pair (4,6):
  • Average = (4+6)/2 = 5
  • Difference = (4−6)/2 = −1
• Pair (10,12):
  • Average = (10+12)/2 = 11
  • Difference = (10−12)/2 = −1

Step 2: Combine results

• Averages (first half): 5, 11
• Differences (second half): −1, −1

Haar transform result:
[
[5, 11, -1, -1]
]

You can repeat this recursively on the averages if the array is longer.

---

3. 2D Haar Transform (for images or 2D data)

For images (like a 4×4 patch):

1. Apply 1D Haar transform to each row → get row-wise averages and differences.
2. Apply 1D Haar transform to each column of the result → get column-wise averages and differences.

The final 2D matrix has:

Quadrant	Meaning
Top-left	Low-frequency (average)
Top-right	Horizontal details
Bottom-left	Vertical details
Bottom-right	Diagonal details

 

---

5. Key Points

• Haar Transform is fast and simple.
• It splits data into averages and differences.
• 2D Haar Transform is widely used in image compression (JPEG2000) and pattern recognition.
• The transform is reversible, meaning you can reconstruct the original data exactly.

---

This matrix can now be used for compression, feature detection, or image analysis.

Step-by-Step Haar Transform Example

Original 4×4 Patch:

52	55	61	59
62	59	55	90
63	65	66	113
58	54	60	109

Step 1: Row-wise Haar Transform (compute averages and differences)

Row 1: 52, 55, 61, 59

• Pair (52,55): Avg = (52+55)/2 = 107/2 = 53.5, Diff = (52−55)/2 = −3/2 = −1.5
• Pair (61,59): Avg = (61+59)/2 = 120/2 = 60, Diff = (61−59)/2 = 2/2 = 1
• Row 1 after Haar: 53.5, 60, −1.5, 1

Row 2: 62, 59, 55, 90

• Pair (62,59): Avg = (62+59)/2 = 121/2 = 60.5, Diff = (62−59)/2 = 3/2 = 1.5
• Pair (55,90): Avg = (55+90)/2 = 145/2 = 72.5, Diff = (55−90)/2 = −35/2 = −17.5
• Row 2 after Haar: 60.5, 72.5, 1.5, −17.5

Row 3: 63, 65, 66, 113

• Pair (63,65): Avg = (63+65)/2 = 64, Diff = (63−65)/2 = −1
• Pair (66,113): Avg = (66+113)/2 = 89.5, Diff = (66−113)/2 = −23.5
• Row 3 after Haar: 64, 89.5, −1, −23.5

Row 4: 58, 54, 60, 109

• Pair (58,54): Avg = (58+54)/2 = 56, Diff = (58−54)/2 = 2
• Pair (60,109): Avg = (60+109)/2 = 84.5, Diff = (60−109)/2 = −24.5
• Row 4 after Haar: 56, 84.5, 2, −24.5

Step 2: Column-wise Haar Transform (compute averages and differences)

Column 1: 53.5, 60.5, 64, 56

• Pair (53.5,60.5): Avg = (53.5+60.5)/2 = 57, Diff = (53.5−60.5)/2 = −3.5
• Pair (64,56): Avg = (64+56)/2 = 60, Diff = (64−56)/2 = 4
• Column 1 after Haar: 57, 60, −3.5, 4

Column 2: 60, 72.5, 89.5, 84.5

• Pair (60,72.5): Avg = (60+72.5)/2 = 66.25, Diff = (60−72.5)/2 = −6.25
• Pair (89.5,84.5): Avg = (89.5+84.5)/2 = 87, Diff = (89.5−84.5)/2 = 2.5
• Column 2 after Haar: 66.25, 87, −6.25, 2.5

Column 3: −1.5,1.5,−1,2

• Pair (−1.5,1.5): Avg = (−1.5+1.5)/2 = 0, Diff = (−1.5−1.5)/2 = −1.5
• Pair (−1,2): Avg = (−1+2)/2 = 0.5, Diff = (−1−2)/2 = −1.5
• Column 3 after Haar: 0, 0.5, −1.5, −1.5

Column 4: 1,−17.5,−23.5,−24.5

• Pair (1,−17.5): Avg = (1−17.5)/2 = −8.25, Diff = (1−(−17.5))/2 = 9.25
• Pair (−23.5,−24.5): Avg = (−23.5−24.5)/2 = −24, Diff = (−23.5−(−24.5))/2 = 0.5
• Column 4 after Haar: −8.25, −24, 9.25, 0.5

Step 3: Final 2D Haar Transform Matrix

Top-left = low frequency (average), other quadrants = details

57	66.25	0	−8.25
60	87	0.5	−24
−3.5	−6.25	−1.5	9.25
4	2.5	−1.5	0.5