Implement basic image compression with discrete cosine transform from scratch like JPEG.…
- User
Implement basic image compression with discrete cosine transform from scratch like JPEG. Break images into 8x8 blocks, apply DCT, quantize coefficients, and visualize the blockiness vs size trade-off by adjusting the quantization table.
Assistant
This is a comprehensive request to implement a JPEG-like image compression algorithm from scratch. I'll need to:
- Implement DCT (Discrete Cosine Transform) from scratch
- Break images into 8x8 blocks
- Implement quantization
- Provide visualization of different quantization levels
- Show the trade-off between compression and image quality
Let me create a complete implementation with:
- DCT transformation implementation
- Image blocking
- Quantization tables
- Decompression (inverse DCT and dequantization)
- Visualization tools
- Comparison of different quality levels
I'll create a well-structured, educational implementation with good visualizations.
JPEG-like Image Compression from Scratch
Here's a complete implementation of image compression using DCT (Discrete Cosine Transform):
import numpy as np import cv2 from matplotlib import pyplot as plt from matplotlib.patches import Rectangle import seaborn as sns from scipy import ndimage from PIL import Image import urllib.request from io import BytesIO class DCTCompressor: """JPEG-like image compression using DCT""" def __init__(self): self.block_size = 8 self.dct_matrix = self._precompute_dct_matrix() def _precompute_dct_matrix(self): """Precompute DCT transformation matrix""" n = self.block_size def C(k): if k == 0: return np.sqrt(1 / n) else: return np.sqrt(2 / n) dct_matrix = np.zeros((n, n)) for k in range(n): for x in range(n): dct_matrix[k, x] = C(k) * np.cos(np.pi * (2 * x + 1) * k / (2 * n)) return dct_matrix def dct_2d(self, block): """Apply 2D DCT to an 8x8 block""" # Shift pixel values from [0, 255] to [-128, 127] shifted = block.astype(float) - 128 # DCT: D * A * D^T return self.dct_matrix @ shifted @ self.dct_matrix.T def idct_2d(self, dct_block): """Apply 2D inverse DCT""" # Inverse DCT: D^T * A * D reconstructed = self.dct_matrix.T @ dct_block @ self.dct_matrix # Shift back to [0, 255] reconstructed = reconstructed + 128 return np.clip(reconstructed, 0, 255).astype(np.uint8) @staticmethod def get_quantization_table(quality=50): """ Generate quantization table based on quality factor (1-100) Higher quality = less quantization = larger file """ # JPEG standard quantization table standard_qtable = np.array([ [16, 11, 10, 16, 24, 40, 51, 61], [12, 12, 14, 19, 26, 58, 60, 55], [14, 13, 16, 24, 40, 57, 69, 56], [14, 17, 22, 29, 51, 87, 80, 62], [18, 22, 37, 56, 68, 109, 103, 77], [24, 35, 55, 64, 81, 104, 113, 92], [49, 64, 78, 87, 103, 121, 120, 101], [72, 92, 95, 98, 112, 100, 103, 99] ]) # Scale based on quality if quality == 100: return np.ones((8, 8)) elif quality < 50: # Lower quality = higher quantization values scale = 50 / quality else: # Higher quality = lower quantization values scale = (100 - quality) / 50 qtable = (standard_qtable * scale).astype(int) qtable = np.clip(qtable, 1, 255) # Ensure positive values return qtable def quantize(self, dct_block, qtable): """Quantize DCT coefficients""" return np.round(dct_block / qtable).astype(int) def dequantize(self, quantized_block, qtable): """Dequantize to recover DCT coefficients""" return quantized_block.astype(float) * qtable def compress_image(self, image, quality=50, return_intermediate=False): """Compress image using DCT and quantization""" if len(image.shape) == 3: # Convert to grayscale image = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY) h, w = image.shape # Pad image to multiple of 8 pad_h = (8 - (h % 8)) % 8 pad_w = (8 - (w % 8)) % 8 image = np.pad(image, ((0, pad_h), (0, pad_w)), mode='constant', constant_values=0) qtable = self.get_quantization_table(quality) h, w = image.shape compressed_data = { 'original_shape': (h - pad_h, w - pad_w), 'padded_shape': (h, w), 'qtable': qtable, 'quality': quality, 'dct_blocks': [], 'quantized_blocks': [] } # Process 8x8 blocks for i in range(0, h, 8): for j in range(0, w, 8): block = image[i:i+8, j:j+8] # Apply DCT dct_block = self.dct_2d(block) # Quantize quantized_block = self.quantize(dct_block, qtable) compressed_data['dct_blocks'].append(dct_block) compressed_data['quantized_blocks'].append(quantized_block) if return_intermediate: return compressed_data return compressed_data def decompress_image(self, compressed_data): """Decompress image from DCT and quantization data""" qtable = compressed_data['qtable'] padded_shape = compressed_data['padded_shape'] original_shape = compressed_data['original_shape'] h, w = padded_shape reconstructed = np.zeros((h, w), dtype=np.uint8) block_idx = 0 for i in range(0, h, 8): for j in range(0, w, 8): # Get quantized block quantized_block = compressed_data['quantized_blocks'][block_idx] # Dequantize dct_block = self.dequantize(quantized_block, qtable) # Apply inverse DCT reconstructed_block = self.idct_2d(dct_block) reconstructed[i:i+8, j:j+8] = reconstructed_block block_idx += 1 # Remove padding reconstructed = reconstructed[:original_shape[0], :original_shape[1]] return reconstructed def calculate_compression_metrics(self, original_data, compressed_data): """Calculate compression metrics""" # Original size (in bytes, assuming 8-bit grayscale) orig_h, orig_w = original_data['original_shape'] original_size = orig_h * orig_w # bytes # Compressed size estimation # DCT coefficients are quantized integers quantized_blocks = compressed_data['quantized_blocks'] # Count non-zero coefficients (approximation of entropy coding) total_coeffs = len(quantized_blocks) * 64 non_zero_coeffs = sum(np.count_nonzero(block) for block in quantized_blocks) # Estimate compression ratio (simplified, real JPEG uses entropy coding) # Non-zero coeffs need ~2 bytes, zeros can be RLE encoded efficiently estimated_compressed_size = (non_zero_coeffs * 2 + (total_coeffs - non_zero_coeffs) * 0.125) compression_ratio = original_size / estimated_compressed_size bpp = (estimated_compressed_size * 8) / (orig_h * orig_w) # bits per pixel return { 'original_size': original_size, 'estimated_compressed_size': int(estimated_compressed_size), 'compression_ratio': compression_ratio, 'bits_per_pixel': bpp, 'non_zero_coeffs': non_zero_coeffs, 'total_coeffs': total_coeffs, 'zero_ratio': (total_coeffs - non_zero_coeffs) / total_coeffs } def load_sample_image(url=None, size=(512, 512)): """Load or create a sample image""" if url: try: response = urllib.request.urlopen(url) image_data = response.read() image = Image.open(BytesIO(image_data)) image = cv2.cvtColor(np.array(image), cv2.COLOR_RGB2BGR) except: print("Failed to load image from URL, creating synthetic image") image = create_synthetic_image(size) else: image = create_synthetic_image(size) # Resize to desired size image = cv2.resize(image, size) return image def create_synthetic_image(size=(512, 512)): """Create a synthetic test image with various patterns""" h, w = size image = np.zeros((h, w, 3), dtype=np.uint8) # Add gradients for i in range(h): image[i, :, 0] = int(255 * i / h) # Add circles and shapes cv2.circle(image, (w//3, h//3), 50, (0, 255, 0), -1) cv2.circle(image, (2*w//3, 2*h//3), 80, (255, 0, 0), -1) cv2.rectangle(image, (w//4, 3*h//4), (3*w//4, h-10), (0, 255, 255), -1) # Add noise noise = np.random.normal(0, 10, image.shape) image = np.clip(image.astype(float) + noise, 0, 255).astype(np.uint8) return image def calculate_psnr(original, reconstructed): """Calculate Peak Signal-to-Noise Ratio""" mse = np.mean((original.astype(float) - reconstructed.astype(float))**2) if mse == 0: return float('inf') max_pixel = 255.0 psnr = 20 * np.log10(max_pixel / np.sqrt(mse)) return psnr def calculate_ssim(original, reconstructed): """Simple SSIM calculation""" # Simplified SSIM (full implementation would be more complex) original = original.astype(float) reconstructed = reconstructed.astype(float) mux = np.mean(original) muy = np.mean(reconstructed) sigx = np.std(original) sigy = np.std(reconstructed) sigxy = np.mean((original - mux) * (reconstructed - muy)) c1 = 6.5025 # (0.01 * 255)^2 c2 = 58.5225 # (0.03 * 255)^2 ssim = ((2 * mux * muy + c1) * (2 * sigxy + c2)) / \ ((mux**2 + muy**2 + c1) * (sigx**2 + sigy**2 + c2)) return ssim # ============================================================================ # VISUALIZATION AND ANALYSIS # ============================================================================ def visualize_dct_coefficients(compressor, image, quality=50): """Visualize DCT coefficients before and after quantization""" compressed = compressor.compress_image(image, quality=quality, return_intermediate=True) fig, axes = plt.subplots(2, 4, figsize=(16, 8)) fig.suptitle(f'DCT Coefficients Visualization (Quality={quality})', fontsize=14, fontweight='bold') # Show first 4 blocks for idx in range(4): dct_block = compressed['dct_blocks'][idx] quantized_block = compressed['quantized_blocks'][idx] # Log scale for better visualization dct_log = np.log1p(np.abs(dct_block)) # DCT coefficients im1 = axes[0, idx].imshow(dct_log, cmap='viridis') axes[0, idx].set_title(f'DCT Block {idx+1}') axes[0, idx].set_xticks([]) axes[0, idx].set_yticks([]) plt.colorbar(im1, ax=axes[0, idx]) # Quantized coefficients quantized_log = np.log1p(np.abs(quantized_block)) im2 = axes[1, idx].imshow(quantized_log, cmap='viridis') axes[1, idx].set_title(f'Quantized Block {idx+1}') axes[1, idx].set_xticks([]) axes[1, idx].set_yticks([]) plt.colorbar(im2, ax=axes[1, idx]) plt.tight_layout() return fig def visualize_quantization_tables(quality_levels=[10, 30, 50, 75, 90]): """Visualize how quantization tables change with quality""" compressor = DCTCompressor() fig, axes = plt.subplots(1, len(quality_levels), figsize=(16, 3)) for idx, quality in enumerate(quality_levels): qtable = compressor.get_quantization_table(quality) im = axes[idx].imshow(qtable, cmap='hot') axes[idx].set_title(f'Quality={quality}', fontweight='bold') axes[idx].set_xticks(range(8)) axes[idx].set_yticks(range(8)) # Add values to cells for i in range(8): for j in range(8): axes[idx].text(j, i, str(qtable[i, j]), ha='center', va='center', color='white', fontsize=8) plt.colorbar(im, ax=axes[idx]) plt.suptitle('Quantization Tables by Quality Level', fontsize=14, fontweight='bold') plt.tight_layout() return fig def visualize_compression_comparison(compressor, image, qualities=[20, 50, 80, 100]): """Compare original vs compressed at different quality levels""" fig, axes = plt.subplots(2, len(qualities) + 1, figsize=(18, 8)) # Original image axes[0, 0].imshow(image, cmap='gray') axes[0, 0].set_title('Original', fontweight='bold') axes[0, 0].axis('off') axes[1, 0].axis('off') metrics_list = [] for idx, quality in enumerate(qualities): compressed = compressor.compress_image(image, quality=quality, return_intermediate=True) reconstructed = compressor.decompress_image(compressed) # Calculate metrics psnr = calculate_psnr(image, reconstructed) ssim = calculate_ssim(image, reconstructed) metrics = compressor.calculate_compression_metrics( {'original_shape': image.shape}, compressed) metrics_list.append({ 'quality': quality, 'psnr': psnr, 'ssim': ssim, 'compression_ratio': metrics['compression_ratio'], 'bpp': metrics['bpp'], 'zero_ratio': metrics['zero_ratio'] }) # Show compressed image axes[0, idx + 1].imshow(reconstructed, cmap='gray') axes[0, idx + 1].set_title(f'Q={quality}\nPSNR={psnr:.1f}dB', fontweight='bold') axes[0, idx + 1].axis('off') # Show difference map diff = np.abs(image.astype(float) - reconstructed.astype(float)) im = axes[1, idx + 1].imshow(diff, cmap='hot') axes[1, idx + 1].set_title(f'Error\nSSIM={ssim:.3f}', fontweight='bold') axes[1, idx + 1].axis('off') plt.colorbar(im, ax=axes[1, idx + 1]) fig.suptitle('Compression Quality Comparison', fontsize=14, fontweight='bold') plt.tight_layout() return fig, metrics_list def visualize_blockiness(compressor, image, qualities=[20, 50, 80, 100]): """Visualize and measure blockiness at different quality levels""" fig, axes = plt.subplots(2, len(qualities), figsize=(16, 8)) blockiness_values = [] for idx, quality in enumerate(qualities): compressed = compressor.compress_image(image, quality=quality, return_intermediate=True) reconstructed = compressor.decompress_image(compressed) # Calculate blockiness (edge detection at block boundaries) edges = cv2.Laplacian(reconstructed, cv2.CV_64F) # Emphasize block boundaries h, w = reconstructed.shape blockiness = 0 for i in range(0, h-8, 8): blockiness += np.sum(np.abs(edges[i+8, :])) blockiness += np.sum(np.abs(edges[:, i+8])) blockiness /= (h + w) * 0.25 # Normalize blockiness_values.append(blockiness) # Show compressed image axes[0, idx].imshow(reconstructed, cmap='gray') axes[0, idx].set_title(f'Quality={quality}\nBlockiness={blockiness:.2f}') # Draw block grid for i in range(0, h, 8): axes[0, idx].axhline(y=i, color='red', linewidth=0.5, alpha=0.5) for j in range(0, w, 8): axes[0, idx].axvline(x=j, color='red', linewidth=0.5, alpha=0.5) axes[0, idx].axis('off') # Show block boundaries block_edges = cv2.Laplacian(reconstructed, cv2.CV_64F) axes[1, idx].imshow(np.abs(block_edges), cmap='hot') axes[1, idx].set_title('Block Edge Artifacts') axes[1, idx].axis('off') fig.suptitle('Blockiness Analysis', fontsize=14, fontweight='bold') plt.tight_layout() return fig, blockiness_values def plot_compression_tradeoffs(metrics_list): """Plot compression trade-offs""" fig, axes = plt.subplots(2, 2, figsize=(14, 10)) qualities = [m['quality'] for m in metrics_list] psnr_vals = [m['psnr'] for m in metrics_list] ssim_vals = [m['ssim'] for m in metrics_list] compression_ratios = [m['compression_ratio'] for m in metrics_list] bpp_vals = [m['bpp'] for m in metrics_list] # PSNR vs Quality axes[0, 0].plot(qualities, psnr_vals, 'o-', linewidth=2, markersize=8, color='blue') axes[0, 0].set_xlabel('Quality Factor', fontsize=11) axes[0, 0].set_ylabel('PSNR (dB)', fontsize=11) axes[0, 0].set_title('PSNR vs Quality', fontweight='bold') axes[0, 0].grid(True, alpha=0.3) # SSIM vs Quality axes[0, 1].plot(qualities, ssim_vals, 'o-', linewidth=2, markersize=8, color='green') axes[0, 1].set_xlabel('Quality Factor', fontsize=11) axes[0, 1].set_ylabel('SSIM', fontsize=11) axes[0, 1].set_title('SSIM vs Quality', fontweight='bold') axes[0, 1].grid(True, alpha=0.3) # Compression Ratio vs Quality axes[1, 0].plot(qualities, compression_ratios, 'o-', linewidth=2, markersize=8, color='red') axes[1, 0].set_xlabel('Quality Factor', fontsize=11) axes[1, 0].set_ylabel('Compression Ratio', fontsize=11) axes[1, 0].set_title('Compression Ratio vs Quality', fontweight='bold') axes[1, 0].grid(True, alpha=0.3) # Bits Per Pixel vs Quality axes[1, 1].plot(qualities, bpp_vals, 'o-', linewidth=2, markersize=8, color='purple') axes[1, 1].set_xlabel('Quality Factor', fontsize=11) axes[1, 1].set_ylabel('Bits Per Pixel', fontsize=11) axes[1, 1].set_title('BPP vs Quality', fontweight='bold') axes[1, 1].grid(True, alpha=0.3) fig.suptitle('Compression Trade-offs Analysis', fontsize=14, fontweight='bold') plt.tight_layout() return fig def print_detailed_analysis(compressor, image, qualities=[20, 50, 80, 100]): """Print detailed analysis""" print("=" * 80) print("JPEG-like Compression Analysis".center(80)) print("=" * 80) for quality in qualities: compressed = compressor.compress_image(image, quality=quality, return_intermediate=True) reconstructed = compressor.decompress_image(compressed) metrics = compressor.calculate_compression_metrics( {'original_shape': image.shape}, compressed) psnr = calculate_psnr(image, reconstructed) ssim = calculate_ssim(image, reconstructed) print(f"\nQuality: {quality}") print(f" PSNR: {psnr:.2f} dB") print(f" SSIM: {ssim:.4f}") print(f" Compression Ratio: {metrics['compression_ratio']:.2f}x") print(f" Bits Per Pixel: {metrics['bpp']:.2f}") print(f" Non-zero Coefficients: {metrics['non_zero_coeffs']:,} / " f"{metrics['total_coeffs']:,} ({100*(1-metrics['zero_ratio']):.1f}%)") print(f" Original Size: {metrics['original_size']:,} bytes") print(f" Est. Compressed Size: {metrics['estimated_compressed_size']:,} bytes") # ============================================================================ # MAIN DEMONSTRATION # ============================================================================ if __name__ == "__main__": # Create compressor compressor = DCTCompressor() # Load or create test image print("Loading test image...") image = load_sample_image(size=(512, 512)) if len(image.shape) == 3: image_gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY) else: image_gray = image print(f"Image shape: {image_gray.shape}") # 1. Visualize Quantization Tables print("\n1. Visualizing quantization tables...") fig1 = visualize_quantization_tables([10, 30, 50, 75, 90]) plt.show() # 2. Visualize DCT Coefficients print("\n2. Visualizing DCT coefficients...") fig2 = visualize_dct_coefficients(compressor, image_gray, quality=50) plt.show() # 3. Compare Compression Quality print("\n3. Comparing compression at different quality levels...") fig3, metrics_list = visualize_compression_comparison( compressor, image_gray, qualities=[20, 50, 80, 95]) plt.show() # 4. Analyze Blockiness print("\n4. Analyzing blockiness...") fig4, blockiness_vals = visualize_blockiness( compressor, image_gray, qualities=[20, 50, 80, 100]) plt.show() # 5. View Extended Metrics print("\n5. Detailed metrics...") # Create extended metrics with more quality levels all_qualities = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] extended_metrics = [] for quality in all_qualities: compressed = compressor.compress_image(image_gray, quality=quality, return_intermediate=True) reconstructed = compressor.decompress_image(compressed) psnr = calculate_psnr(image_gray, reconstructed) ssim = calculate_ssim(image_gray, reconstructed) metrics = compressor.calculate_compression_metrics( {'original_shape': image_gray.shape}, compressed) extended_metrics.append({ 'quality': quality, 'psnr': psnr, 'ssim': ssim, 'compression_ratio': metrics['compression_ratio'], 'bpp': metrics['bpp'], 'zero_ratio': metrics['zero_ratio'] }) # 6. Plot Trade-offs print("\n6. Plotting compression trade-offs...") fig5 = plot_compression_tradeoffs(extended_metrics) plt.show() # 7. Detailed Analysis print_detailed_analysis(compressor, image_gray, qualities=[20, 50, 80, 100]) # 8. Create side-by-side comparison print("\n8. Creating final comparison visualization...") fig, axes = plt.subplots(2, 4, figsize=(18, 9)) quality_levels = [10, 30, 50, 70, 90, 95, 99, 100] for idx, quality in enumerate(quality_levels): compressed = compressor.compress_image(image_gray, quality=quality, return_intermediate=True) reconstructed = compressor.decompress_image(compressed) metrics = compressor.calculate_compression_metrics( {'original_shape': image_gray.shape}, compressed) psnr = calculate_psnr(image_gray, reconstructed) row = idx // 4 col = idx % 4 axes[row, col].imshow(reconstructed, cmap='gray') axes[row, col].set_title( f'Q={quality}\nPSNR={psnr:.1f}dB, CR={metrics["compression_ratio"]:.1f}x', fontweight='bold' ) axes[row, col].axis('off') fig.suptitle('Compression Results at Various Quality Levels', fontsize=14, fontweight='bold') plt.tight_layout() plt.show() # 9. DCT Basis Functions Visualization print("\n9. Visualizing DCT basis functions...") fig_basis = plt.figure(figsize=(14, 12)) for k in range(64): ax = plt.subplot(8, 8, k + 1) # Create basis function by setting one coefficient to 1 basis_dct = np.zeros((8, 8)) basis_dct[k // 8, k % 8] = 1 # Inverse DCT to get spatial domain basis_spatial = compressor.idct_2d(basis_dct + 128) - 128 ax.imshow(basis_spatial, cmap='RdBu', vmin=-128, vmax=128) ax.set_xticks([]) ax.set_yticks([]) ax.set_title(f'{k}', fontsize=8) fig_basis.suptitle('DCT Basis Functions (8x8)', fontsize=14, fontweight='bold') plt.tight_layout() plt.show() print("\n" + "=" * 80) print("Analysis Complete!".center(80)) print("=" * 80)This comprehensive implementation includes:
Key Features:
-
DCT Implementation
- 2D DCT using precomputed matrices
- Forward and inverse transforms
- Proper normalization
-
Quantization
- JPEG-standard quantization table
- Quality-dependent scaling (1-100)
- Zero-padding for uncompressed blocks
-
Compression Pipeline
- Image blocking (8×8)
- DCT transformation
- Coefficient quantization
- Decompression with inverse operations
-
Visualizations
- Quantization tables at different quality levels
- DCT coefficients before/after quantization
- Compression quality comparison
- Blockiness analysis
- Trade-off charts (PSNR, SSIM, compression ratio, BPP)
- DCT basis functions
-
Metrics
- PSNR (Peak Signal-to-Noise Ratio)
- SSIM (Structural Similarity)
- Compression ratio
- Bits per pixel
- Zero coefficient ratio
- Blockiness measurement
What You'll Learn:
- How JPEG compression works
- DCT mathematics and applications
- Quantization effects on image quality
- Trade-offs between file size and image quality
- Visual artifacts (blockiness) at low quality
- How frequency information is compressed
The code creates sample images if no external image is provided and outputs comprehensive visualizations showing the compression trade-offs!
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.