1.7 Fractal Compression
1.7 Fractal Compression
1.7.2 Illustrative Example
1.7.2 Illustrative Example
In[]:=
imgR=
;
In[]:=
imgD=ImageResize[imgR,{12,12}]//Round
Out[]=
In[]:=
imgRP=ImagePartition[imgR,2];
In[]:=
Grid[imgRP,Spacings->{0.8,0.1}]
Out[]=
In[]:=
imgDP=ImagePartition[imgD,2];
In[]:=
Grid[imgDP,Spacings->{0.8,0.1}]
Out[]=
In[]:=
RP=Flatten[Table[ImageData[imgRP[[i,j]]],{i,1,12},{j,1,12}],1];
In[]:=
Length[RP]
Out[]=
144
In[]:=
DP=Flatten[Table[ImageData[imgDP[[i,j]]],{i,1,6},{j,1,6}],1];
In[]:=
Length[DP]
Out[]=
36
In[]:=
RangeBlockes[imgR_]:=Module[{imgRP,RP},imgRP=ImagePartition[imgR,2];RP=Flatten[Table[ImageData[imgRP[[i,j]]],{i,1,12},{j,1,12}],1]];
In[]:=
RangeBlockes[imgR][[105]]//MatrixForm
Out[]//MatrixForm=
1. | 1. |
1. | 0. |
In[]:=
DomainBlockes[imgR_]:=Module[{imgD,imgDP,DP},imgD=ImageResize[imgR,{12,12}]//Round;imgDP=ImagePartition[imgD,2];DP=Flatten[Table[ImageData[imgDP[[i,j]]],{i,1,6},{j,1,6}],1]];
In[]:=
DomainBlockes[imgR][[10]]//MatrixForm
Out[]//MatrixForm=
0. | 0. |
0. | 1. |
In[]:=
BestDomain[Ri_,DP_]:=Module[{sD,sG,j,minD,s1,smin,sindex,best},sD={};Do[sG=Norm[αDP[[j]]+tIdentityMatrix[2]-Ri];minD=FindMinimum[{sG,0.≤α≤1.,-255.≤t≤255.},{{α,0.5},{t,0.}},MaxIterations15]//Quiet;AppendTo[sD,minD],{j,1,36}];s1=Map[First[#]&,sD];smin=Min[s1];sindex=Position[s1,n_/;nsmin]//Flatten;best=sD[[First[sindex]]];{First[sindex],{α,t}/.best[[2]]}]
In[]:=
AbsoluteTiming[BestDomain[RP[[35]],DP]]
Out[]=
{1.13727,{3,{0.5,0.}}}
In[]:=
FractalCodeBook[RP_,DP_,n1_,n2_]:=Module[{CodeBook,i},CodeBook={};Do[AppendTo[CodeBook,BestDomain[RP[[i]],DP]],{i,n1,n2}];CodeBook]
In[]:=
RP0=RP;DP0=DP;
In[]:=
s=AbsoluteTiming[FractalCodeBook[RP0,DP0,1,144]]
Out[]=
In[]:=
S=Map[Flatten[#]&,s[[2]]]
Out[]=
{{1,0.996886,0.00313},{1,0.996886,0.00313},{1,0.996886,0.00313},{27,0.999875,0.0000625009},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{27,0.999875,0.0000625009},{1,0.996886,0.00313},{1,0.996886,0.00313},{1,0.996886,0.00313},{1,0.996886,0.00313},{1,0.996886,0.00313},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{1,0.996886,0.00313},{1,0.996886,0.00313},{1,0.996886,0.00313},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{1,0.996886,0.00313},{9,0.999996,0.499998},{3,0.5,0.},{3,0.5,0.},{1,0.963019,-0.463019},{1,0.996886,0.00313},{9,0.99985,-1.34642×},{8,0.535396,0.2475},{1,0.996886,0.00313},{9,0.999825,0.999991},{3,0.5,0.},{3,0.5,0.},{5,0.999996,0.499998},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{1,0.996886,0.00313},{1,0.996886,0.00313},{9,0.999996,0.499998},{5,0.999996,0.499998},{1,0.996886,0.00313},{1,0.996886,0.00313},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{5,0.99985,-1.34642×},{27,0.999875,0.0000625009},{3,0.5,0.},{3,0.5,0.},{27,0.999875,0.0000625009},{2,0.535396,0.2475},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{5,0.999996,0.499998},{1,0.996886,0.00313},{1,0.996886,0.00313},{1,0.996886,0.00313},{1,0.996886,0.00313},{1,0.996886,0.00313},{1,0.996886,0.00313},{1,0.996886,0.00313},{3,0.5,0.},{3,0.5,0.},{9,0.999996,0.499998},{3,0.5,0.},{3,0.5,0.},{27,0.999875,0.0000625009},{1,0.996886,0.00313},{1,0.996886,0.00313},{1,0.996886,0.00313},{1,0.996886,0.00313},{1,0.963019,-0.463019},{2,0.535396,0.2475},{3,0.5,0.},{5,0.999996,0.499998},{1,0.996886,0.00313},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{27,0.999875,0.0000625009},{27,0.999875,0.0000625009},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{1,0.996886,0.00313},{1,0.996886,0.00313},{1,0.996886,0.00313},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{1,0.996886,0.00313},{1,0.996886,0.00313},{1,0.996886,0.00313},{1,0.996886,0.00313},{1,0.996886,0.00313},{21,0.999875,0.0000625009},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{3,0.5,0.},{21,0.999875,0.0000625009},{1,0.996886,0.00313},{1,0.996886,0.00313},{1,0.996886,0.00313}}
-7
10
-7
10
In[]:=
SeedRandom[2121]
In[]:=
imgRN=Image[Table[RandomReal[],{i,1,24},{j,1,24}]]
Out[]=
In[]:=
FractalDecoding[img0_,FCB_,m_]:=Module[{S,u,imgR,imgDP0,DP0,RP1,ImageRP1,k,i1,j1,j},S={img0};Do[u=Last[S];imgR=ImageResize[u,{12,12}]//Round;imgDP0=ImagePartition[imgR,2];DP0=Flatten[Table[ImageData[imgDP0[[i1,j1]]],{i1,1,6},{j1,1,6}],1];RP1={};Do[AppendTo[RP1,FCB[[j,2]]DP0[[FCB[[j,1]]]]+FCB[[j,3]]IdentityMatrix[2]],{j,1,144}];ImageRP1=ImageAssemble[Partition[Map[Image[#]&,RP1],12]];AppendTo[S,ImageRP1],{k,1,m}];S]
1.7.4 Accelerating Fractal Code Book Computation
1.7.4 Accelerating Fractal Code Book Computation
The size of the image blocks is 4 × 4 and therefore the number of the Range Blocks is 32 × 32 =1024, see Fig.1.6.13
Let us employ the new decoding modul, the result can seen in Fig. 1.6.16
1.7.5 Fractal Compression in Python
1.7.5 Fractal Compression in Python
◼
Employ Version 11.3
Test
In[]:=
5+6
In[]:=
import matplotlib.pyplot as plt
import matplotlib.image as mpimg
from scipy import ndimage
from scipy import optimize
import numpy as np
import math
import matplotlib.image as mpimg
from scipy import ndimage
from scipy import optimize
import numpy as np
import math
Manipulate channels,
In[]:=
def get_greyscale_image(img):
return np.mean(img[:,:,:2], 2)
def extract_rgb(img):
return img[:,:,0], img[:,:,1], img[:,:,2]
def assemble_rbg(img_r, img_g, img_b):
shape = (img_r.shape[0], img_r.shape[1], 1)
return np.concatenate((np.reshape(img_r, shape), np.reshape(img_g, shape),
np.reshape(img_b, shape)), axis=2)
return np.mean(img[:,:,:2], 2)
def extract_rgb(img):
return img[:,:,0], img[:,:,1], img[:,:,2]
def assemble_rbg(img_r, img_g, img_b):
shape = (img_r.shape[0], img_r.shape[1], 1)
return np.concatenate((np.reshape(img_r, shape), np.reshape(img_g, shape),
np.reshape(img_b, shape)), axis=2)
Transformations
In[]:=
def reduce(img, factor):
result = np.zeros((img.shape[0] // factor, img.shape[1] // factor))
for i in range(result.shape[0]):
for j in range(result.shape[1]):
result[i,j] = np.mean(img[i*factor:(i+1)*factor,j*factor:(j+1)*factor])
return result
def rotate(img, angle):
return ndimage.rotate(img, angle, reshape=False)
def flip(img, direction):
return img[::direction,:]
def apply_transformation(img, direction, angle, contrast=1.0, brightness=0.0):
return contrast*rotate(flip(img, direction), angle) + brightness
result = np.zeros((img.shape[0] // factor, img.shape[1] // factor))
for i in range(result.shape[0]):
for j in range(result.shape[1]):
result[i,j] = np.mean(img[i*factor:(i+1)*factor,j*factor:(j+1)*factor])
return result
def rotate(img, angle):
return ndimage.rotate(img, angle, reshape=False)
def flip(img, direction):
return img[::direction,:]
def apply_transformation(img, direction, angle, contrast=1.0, brightness=0.0):
return contrast*rotate(flip(img, direction), angle) + brightness
Contrast and brightness
In[]:=
def find_contrast_and_brightness1(D, S):
# Fix the contrast and only fit the brightness
contrast = 0.75
brightness = (np.sum(D - contrast*S)) / D.size
return contrast, brightness
def find_contrast_and_brightness2(D, S):
# Fit the contrast and the brightness
A = np.concatenate((np.ones((S.size, 1)), np.reshape(S, (S.size, 1))), axis=1)
b = np.reshape(D, (D.size,))
x, _, _, _ = np.linalg.lstsq(A, b)
#x = optimize.lsq_linear(A, b, [(-np.inf, -2.0), (np.inf, 2.0)]).x
return x[1], x[0]
# Fix the contrast and only fit the brightness
contrast = 0.75
brightness = (np.sum(D - contrast*S)) / D.size
return contrast, brightness
def find_contrast_and_brightness2(D, S):
# Fit the contrast and the brightness
A = np.concatenate((np.ones((S.size, 1)), np.reshape(S, (S.size, 1))), axis=1)
b = np.reshape(D, (D.size,))
x, _, _, _ = np.linalg.lstsq(A, b)
#x = optimize.lsq_linear(A, b, [(-np.inf, -2.0), (np.inf, 2.0)]).x
return x[1], x[0]
Compression for greyscale images
In[]:=
def generate_all_transformed_blocks(img, source_size, destination_size, step):
factor = source_size // destination_size
transformed_blocks = []
for k in range((img.shape[0] - source_size) // step + 1):
for l in range((img.shape[1] - source_size) // step + 1):
# Extract the source block and reduce it to the shape of a destination block
S = reduce(img[k*step:k*step+source_size,l*step:l*step+source_size], factor)
# Generate all possible transformed blocks
for direction, angle in candidates:
transformed_blocks.append((k, l, direction, angle, apply_transformation(S, direction, angle)))
return transformed_blocks
factor = source_size // destination_size
transformed_blocks = []
for k in range((img.shape[0] - source_size) // step + 1):
for l in range((img.shape[1] - source_size) // step + 1):
# Extract the source block and reduce it to the shape of a destination block
S = reduce(img[k*step:k*step+source_size,l*step:l*step+source_size], factor)
# Generate all possible transformed blocks
for direction, angle in candidates:
transformed_blocks.append((k, l, direction, angle, apply_transformation(S, direction, angle)))
return transformed_blocks
In[]:=
def compress(img, source_size, destination_size, step):
transformations = []
transformed_blocks = generate_all_transformed_blocks(img, source_size, destination_size, step)
for i in range(img.shape[0] // destination_size):
transformations.append([])
for j in range(img.shape[1] // destination_size):
print(i, j)
transformations[i].append(None)
min_d = float('inf')
# Extract the destination block
D = img[i*destination_size:(i+1)*destination_size,j*destination_size:(j+1)*destination_size]
# Test all possible transformations and take the best one
for k, l, direction, angle, S in transformed_blocks:
contrast, brightness = find_contrast_and_brightness2(D, S)
S = contrast*S + brightness
d = np.sum(np.square(D - S))
if d < min_d:
min_d = d
transformations[i][j] = (k, l, direction, angle, contrast, brightness)
return transformations
transformations = []
transformed_blocks = generate_all_transformed_blocks(img, source_size, destination_size, step)
for i in range(img.shape[0] // destination_size):
transformations.append([])
for j in range(img.shape[1] // destination_size):
print(i, j)
transformations[i].append(None)
min_d = float('inf')
# Extract the destination block
D = img[i*destination_size:(i+1)*destination_size,j*destination_size:(j+1)*destination_size]
# Test all possible transformations and take the best one
for k, l, direction, angle, S in transformed_blocks:
contrast, brightness = find_contrast_and_brightness2(D, S)
S = contrast*S + brightness
d = np.sum(np.square(D - S))
if d < min_d:
min_d = d
transformations[i][j] = (k, l, direction, angle, contrast, brightness)
return transformations
In[]:=
def decompress(transformations, source_size, destination_size, step, nb_iter=8):
factor = source_size // destination_size
height = len(transformations) * destination_size
width = len(transformations[0]) * destination_size
iterations = [np.random.randint(0, 256, (height, width))]
cur_img = np.zeros((height, width))
for i_iter in range(nb_iter):
print(i_iter)
for i in range(len(transformations)):
for j in range(len(transformations[i])):
# Apply transform
k, l, flip, angle, contrast, brightness = transformations[i][j]
S = reduce(iterations[-1][k*step:k*step+source_size,l*step:l*step+source_size], factor)
D = apply_transformation(S, flip, angle, contrast, brightness)
cur_img[i*destination_size:(i+1)*destination_size,j*destination_size:(j+1)*destination_size] = D
iterations.append(cur_img)
cur_img = np.zeros((height, width))
return iterations
factor = source_size // destination_size
height = len(transformations) * destination_size
width = len(transformations[0]) * destination_size
iterations = [np.random.randint(0, 256, (height, width))]
cur_img = np.zeros((height, width))
for i_iter in range(nb_iter):
print(i_iter)
for i in range(len(transformations)):
for j in range(len(transformations[i])):
# Apply transform
k, l, flip, angle, contrast, brightness = transformations[i][j]
S = reduce(iterations[-1][k*step:k*step+source_size,l*step:l*step+source_size], factor)
D = apply_transformation(S, flip, angle, contrast, brightness)
cur_img[i*destination_size:(i+1)*destination_size,j*destination_size:(j+1)*destination_size] = D
iterations.append(cur_img)
cur_img = np.zeros((height, width))
return iterations
Compression for color images
In[]:=
def reduce_rgb(img, factor):
img_r, img_g, img_b = extract_rgb(img)
img_r = reduce(img_r, factor)
img_g = reduce(img_g, factor)
img_b = reduce(img_b, factor)
return assemble_rbg(img_r, img_g, img_b)
def compress_rgb(img, source_size, destination_size, step):
img_r, img_g, img_b = extract_rgb(img)
return [compress(img_r, source_size, destination_size, step), \
compress(img_g, source_size, destination_size, step), \
compress(img_b, source_size, destination_size, step)]
def decompress_rgb(transformations, source_size, destination_size, step, nb_iter=8):
img_r = decompress(transformations[0], source_size, destination_size, step, nb_iter)[-1]
img_g = decompress(transformations[1], source_size, destination_size, step, nb_iter)[-1]
img_b = decompress(transformations[2], source_size, destination_size, step, nb_iter)[-1]
return assemble_rbg(img_r, img_g, img_b)
img_r, img_g, img_b = extract_rgb(img)
img_r = reduce(img_r, factor)
img_g = reduce(img_g, factor)
img_b = reduce(img_b, factor)
return assemble_rbg(img_r, img_g, img_b)
def compress_rgb(img, source_size, destination_size, step):
img_r, img_g, img_b = extract_rgb(img)
return [compress(img_r, source_size, destination_size, step), \
compress(img_g, source_size, destination_size, step), \
compress(img_b, source_size, destination_size, step)]
def decompress_rgb(transformations, source_size, destination_size, step, nb_iter=8):
img_r = decompress(transformations[0], source_size, destination_size, step, nb_iter)[-1]
img_g = decompress(transformations[1], source_size, destination_size, step, nb_iter)[-1]
img_b = decompress(transformations[2], source_size, destination_size, step, nb_iter)[-1]
return assemble_rbg(img_r, img_g, img_b)
Plot the result
In[]:=
def plot_iterations(iterations, target=None):
# Configure plot
plt.figure()
nb_row = math.ceil(np.sqrt(len(iterations)))
nb_cols = nb_row
# Plot
for i, img in enumerate(iterations):
plt.subplot(nb_row, nb_cols, i+1)
plt.imshow(img, cmap='gray', vmin=0, vmax=255, interpolation='none')
if target is None:
plt.title(str(i))
else:
# Display the RMSE
plt.title(str(i) + ' (' + '{0:.2f}'.format(np.sqrt(np.mean(np.square(target - img)))) + ')')
frame = plt.gca()
frame.axes.get_xaxis().set_visible(False)
frame.axes.get_yaxis().set_visible(False)
plt.tight_layout()
# Configure plot
plt.figure()
nb_row = math.ceil(np.sqrt(len(iterations)))
nb_cols = nb_row
# Plot
for i, img in enumerate(iterations):
plt.subplot(nb_row, nb_cols, i+1)
plt.imshow(img, cmap='gray', vmin=0, vmax=255, interpolation='none')
if target is None:
plt.title(str(i))
else:
# Display the RMSE
plt.title(str(i) + ' (' + '{0:.2f}'.format(np.sqrt(np.mean(np.square(target - img)))) + ')')
frame = plt.gca()
frame.axes.get_xaxis().set_visible(False)
frame.axes.get_yaxis().set_visible(False)
plt.tight_layout()
Parameters
In[]:=
directions = [1, -1]
angles = [0, 90, 180, 270]
candidates = list(zip(directions, angles))
angles = [0, 90, 180, 270]
candidates = list(zip(directions, angles))
Test for grayscale image
Range Image Blocks: 8 8, Domain Image Blocks: 4 4 and number of iterations: 8
In[]:=
def test_greyscale():
img = mpimg.imread('D:\\me.jpg')
img = get_greyscale_image(img)
img = reduce(img, 4)
plt.figure()
plt.imshow(img, cmap='gray', interpolation='none')
transformations = compress(img, 8, 4, 8)
iterations = decompress(transformations, 8, 4, 8)
plot_iterations(iterations, img)
plt.show()
img = mpimg.imread('D:\\me.jpg')
img = get_greyscale_image(img)
img = reduce(img, 4)
plt.figure()
plt.imshow(img, cmap='gray', interpolation='none')
transformations = compress(img, 8, 4, 8)
iterations = decompress(transformations, 8, 4, 8)
plot_iterations(iterations, img)
plt.show()
In[]:=
test_greyscale()
Test for RGB image
In[]:=
def test_rgb():
img = mpimg.imread('D:\\me.jpg')
img = reduce_rgb(img, 4)
transformations = compress_rgb(img, 8, 4, 8)
retrieved_img = decompress_rgb(transformations, 8, 4, 8)
plt.figure()
plt.subplot(121)
plt.imshow(np.array(img).astype(np.uint8), interpolation='none')
plt.subplot(122)
plt.imshow(retrieved_img.astype(np.uint8), interpolation='none')
plt.show()
img = mpimg.imread('D:\\me.jpg')
img = reduce_rgb(img, 4)
transformations = compress_rgb(img, 8, 4, 8)
retrieved_img = decompress_rgb(transformations, 8, 4, 8)
plt.figure()
plt.subplot(121)
plt.imshow(np.array(img).astype(np.uint8), interpolation='none')
plt.subplot(122)
plt.imshow(retrieved_img.astype(np.uint8), interpolation='none')
plt.show()
In[]:=
test_rgb()