<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Copyright 2021 Google LLC.
Licensed under the Apache License, Version 2.0 (the "License");
Step1:  Spectral Representations of Natural Images
This notebook will show how to extract the spectral representations of an image, and see the effect of truncation of these spectral representation to the first $m$ components.
Imports
Step2:  Image Upload
Upload your images by running the cell below
Step3:  We rescale images to a reasonable resolution, otherwise this would take very long. Note that we will have $h \times w$ nodes in the resulting graph, where $h$ and $w$ are the height and width of the image.
Step4:  Helper Functions
To compute the adjacency list and the Laplacian of the corresponding grid graph.
Step5:  By using a sparse matrix representation of the Laplacian, we save on memory significantly.
Step6:  After we have computed the Laplacian, we can compute its eigenvectors.
Step7:  The Laplacian is always positive semidefinite.
Step8:  Keeping the Top $m$ Components
Once we have the eigenvectors, we can compute the (truncated) spectral representations.
Step9:  Saving Results
We save results to the 'processed' subdirectory.
Step10:  You can download the images from this folder as a zipped folder by running the cells below.
<ASSISTANT_TASK:>
Python Code:
#@title License
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# https://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
Explanation: Copyright 2021 Google LLC.
Licensed under the Apache License, Version 2.0 (the "License");
End of explanation
import functools
import io
import itertools
import os
import matplotlib.pyplot as plt
import numpy as np
import PIL
import scipy.sparse
import scipy.sparse.linalg
from google.colab import files
Explanation: Spectral Representations of Natural Images
This notebook will show how to extract the spectral representations of an image, and see the effect of truncation of these spectral representation to the first $m$ components.
Imports
End of explanation
imgs = files.upload()
def open_as_array(img_bytes):
  img_pil = PIL.Image.open(io.BytesIO(img_bytes))
  img_pil = img_pil.resize((img_width, img_height))
  return np.asarray(img_pil)
img_name, img_bytes = list(imgs.items())[0]
img_data = open_as_array(img_bytes)
plt.axis('off')
_ = plt.imshow(img_data)
Explanation: Image Upload
Upload your images by running the cell below
End of explanation
img_width = 50
img_height = 40
Explanation: We rescale images to a reasonable resolution, otherwise this would take very long. Note that we will have $h \times w$ nodes in the resulting graph, where $h$ and $w$ are the height and width of the image.
End of explanation
def get_index(x, y, img_width, img_height):
  return y * img_width + x;
def get_neighbours(x, y, img_width, img_height):
  neighbours_x_pos = [max(0, x - 1), x, min(x + 1, img_width - 1)]
  neighbours_y_pos = [max(0, y - 1), y, min(y + 1, img_height - 1)]
  neighbours = product(neighbours_x_pos, neighbours_y_pos)
  neighbours = set(neighbours)
  neighbours.discard((x, y))
  return neighbours
Explanation: Helper Functions
To compute the adjacency list and the Laplacian of the corresponding grid graph.
End of explanation
def compute_sparse_laplacian(img_width, img_height):
  neighbours_fn = functools.partial(get_neighbours,
                                    img_width=img_width, img_height=img_height)
  index_fn = functools.partial(get_index,
                               img_width=img_width, img_height=img_height)
  senders = []
  recievers = []
  values = []
  for x in range(img_width):
    for y in range(img_height):
      pos = (x, y)
      pos_index = index_fn(*pos)
      degree = 0.
      for neighbour in neighbours_fn(*pos):
        neigh_index = index_fn(*neighbour)
        senders.append(pos_index)
        recievers.append(neigh_index)
        values.append(-1.)
        degree += 1.
  
      senders.append(pos_index)
      recievers.append(pos_index)
      values.append(degree)
  num_nodes = img_width * img_height
  laplacian_shape = (num_nodes, num_nodes)
  return scipy.sparse.coo_matrix((values, (senders, recievers)))
laplacian = compute_sparse_laplacian(img_width, img_height)
Explanation: By using a sparse matrix representation of the Laplacian, we save on memory significantly.
End of explanation
num_eigenvecs = 1500
v0 = np.ones(img_width * img_height)
eigenvals, eigenvecs = scipy.sparse.linalg.eigsh(laplacian, k=num_eigenvecs,
                                                 which='SM', v0=v0)
Explanation: After we have computed the Laplacian, we can compute its eigenvectors.
End of explanation
assert np.all(eigenvals >= 0)
plt.hist(eigenvals, bins=100)
plt.title('Histogram of Laplacian Eigenvalues')
plt.show()
Explanation: The Laplacian is always positive semidefinite.
End of explanation
def keep_first_components(img_data, num_components):
  orig_shape = img_data.shape
  img_reshaped = np.reshape(img_data, (-1, 3)) 
  chosen_eigenvecs = eigenvecs[:, :num_components]
  spectral_coeffs = chosen_eigenvecs.T @ img_reshaped
  upd_img_data_reshaped = chosen_eigenvecs @ spectral_coeffs
  return np.reshape(upd_img_data_reshaped, orig_shape).astype(int)
plt.axis('off')
plt.imshow(keep_first_components(img_data, 200))
plt.savefig('test.png', bbox_inches='tight', pad_inches=0)
Explanation: Keeping the Top $m$ Components
Once we have the eigenvectors, we can compute the (truncated) spectral representations.
End of explanation
save_dir = 'processed'
os.mkdir(save_dir)
for img_name, img_bytes in imgs.items():
  base_name = os.path.basename(img_name).split('.')[0]
  img_data = open_as_array(img_name)
  for num_components in [1, 2, 5, 10, 20, 100, 200, 500]:
    upd_img_data = keep_first_components(img_data, num_components)
    upd_img_name = f'{base_name}-{num_components}.png'
    plt.axis('off')
    plt.imshow(upd_img_data)
    _ = plt.savefig(f'{save_dir}/{upd_img_name}', bbox_inches='tight',
                    pad_inches=0)
Explanation: Saving Results
We save results to the 'processed' subdirectory.
End of explanation
!zip -r processed.zip processed
files.download('processed.zip')
Explanation: You can download the images from this folder as a zipped folder by running the cells below.
End of explanation
<END_TASK>