code: """
  CS131 - Computer Vision: Foundations and Applications
  Assignment 1
  Author: Donsuk Lee (donlee90@stanford.edu)
  Date created: 07/2017
  Last modified: 10/16/2017
  Python Version: 3.5+
  """
  
  import numpy as np
  
  
  def conv_nested(image, kernel):
      """A naive implementation of convolution filter.
  
      This is a naive implementation of convolution using 4 nested for-loops.
      This function computes convolution of an image with a kernel and outputs
      the result that has the same shape as the input image.
  
      Args:
          image: numpy array of shape (Hi, Wi).
          kernel: numpy array of shape (Hk, Wk).
  
      Returns:
          out: numpy array of shape (Hi, Wi).
      """
      Hi, Wi = image.shape
      Hk, Wk = kernel.shape
      out = np.zeros((Hi, Wi))
  
      ### YOUR CODE HERE
      for i in range(Hi):
          for j in range(Wi):
              sum = 0
              for ii in range(-(Hk//2), Hk//2 + 1):
                  for jj in range(-(Wk//2), Wk//2 + 1):
                      sum += image[i - ii, j - jj] * kernel[ii + Hk // 2, jj + Wk // 2] \
                          if 0 <= i - ii < Hi and 0 <= j - jj < Wi else 0
              out[i, j] = sum
      ### END YOUR CODE
  
      return out
  
  def zero_pad(image, pad_height, pad_width):
      """ Zero-pad an image.
  
      Ex: a 1x1 image [[1]] with pad_height = 1, pad_width = 2 becomes:
  
          [[0, 0, 0, 0, 0],
           [0, 0, 1, 0, 0],
           [0, 0, 0, 0, 0]]         of shape (3, 5)
  
      Args:
          image: numpy array of shape (H, W).
          pad_width: width of the zero padding (left and right padding).
          pad_height: height of the zero padding (bottom and top padding).
  
      Returns:
          out: numpy array of shape (H+2*pad_height, W+2*pad_width).
      """
  
      H, W = image.shape
      out = None
  
      ### YOUR CODE HERE
      out = np.pad(image, ((pad_height, pad_height), (pad_width, pad_width)), 'constant', constant_values = (0))
      pass
      ### END YOUR CODE
      return out
  
  
  def conv_fast(image, kernel):
      """ An efficient implementation of convolution filter.
  
      This function uses element-wise multiplication and np.sum()
      to efficiently compute weighted sum of neighborhood at each
      pixel.
  
      Hints:
          - Use the zero_pad function you implemented above
          - There should be two nested for-loops
          - You may find np.flip() and np.sum() useful
  
      Args:
          image: numpy array of shape (Hi, Wi).
          kernel: numpy array of shape (Hk, Wk).
  
      Returns:
          out: numpy array of shape (Hi, Wi).
      """
      Hi, Wi = image.shape
      Hk, Wk = kernel.shape
      out = np.zeros((Hi, Wi))
  
      ### YOUR CODE HERE
      image_pad = zero_pad(image, Hk // 2, Wk // 2)
      kernel_flip = np.flip(np.flip(kernel, axis=0), axis=1)
      for i in range(Hi):
          for j in range(Wi):
              out[i, j] = np.sum(image_pad[i:i + Hk, j:j + Wk] * kernel_flip)
      ### END YOUR CODE
  
      return out
  
  def conv_faster(image, kernel):
      """
      Args:
          image: numpy array of shape (Hi, Wi).
          kernel: numpy array of shape (Hk, Wk).
  
      Returns:
          out: numpy array of shape (Hi, Wi).
      """
      Hi, Wi = image.shape
      Hk, Wk = kernel.shape
      out = np.zeros((Hi, Wi))
  
      ### YOUR CODE HERE
      out = image.copy()
      u, s, v = np.linalg.svd(kernel)
      kernel_u = (u.T[s > 1e-6]).T
      kernel_v = (v[s > 1e-6])
      for p in range(np.sum(s > 1e-6)):
          out = conv_fast(out, (kernel_u[:, p] * s[p]).reshape(Hk, 1))
          out = conv_fast(out, kernel_v[p].reshape(1, Wk))
      ### END YOUR CODE
  
      return out
  
  def cross_correlation(f, g):
      """ Cross-correlation of f and g.
  
      Hint: use the conv_fast function defined above.
  
      Args:
          f: numpy array of shape (Hf, Wf).
          g: numpy array of shape (Hg, Wg).
  
      Returns:
          out: numpy array of shape (Hf, Wf).
      """
  
      out = None
      ### YOUR CODE HERE
      out = conv_fast(f, np.flip(np.flip(g, axis=0), axis=1))
      ### END YOUR CODE
  
      return out
  
  def zero_mean_cross_correlation(f, g):
      """ Zero-mean cross-correlation of f and g.
  
      Subtract the mean of g from g so that its mean becomes zero.
  
      Hint: you should look up useful numpy functions online for calculating the mean.
  
      Args:
          f: numpy array of shape (Hf, Wf).
          g: numpy array of shape (Hg, Wg).
  
      Returns:
          out: numpy array of shape (Hf, Wf).
      """
  
      out = None
      ### YOUR CODE HERE
      zero_mean_g = g - np.mean(g)
      zero_mean_f = f - np.mean(g)
      out = conv_fast(zero_mean_f, np.flip(np.flip(zero_mean_g, axis=0), axis=1))
      ### END YOUR CODE
  
      return out
  
  def normalized_cross_correlation(f, g):
      """ Normalized cross-correlation of f and g.
  
      Normalize the subimage of f and the template g at each step
      before computing the weighted sum of the two.
  
      Hint: you should look up useful numpy functions online for calculating
            the mean and standard deviation.
  
      Args:
          f: numpy array of shape (Hf, Wf).
          g: numpy array of shape (Hg, Wg).
  
      Returns:
          out: numpy array of shape (Hf, Wf).
      """
  
      out = None
      ### YOUR CODE HERE
      Hf, Wf = f.shape
      out = np.zeros((Hf, Wf))
      g = g[:-1, :] if g.shape[0] % 2 == 0 else g
      g = g[:, :-1] if g.shape[1] % 2 == 0 else g
      Hg, Wg = g.shape
      normalized_filter = (g - np.mean(g)) / np.std(g)
      f = zero_pad(f, Hg // 2, Wg // 2)
      for i in range(Hf):
          for j in range(Wf):
              normalized_template = (f[i:i+Hg, j:j+Wg] - np.mean(f[i:i+Hg, j:j+Wg])) / np.std(f[i:i+Hg, j:j+Wg])
              out[i, j] = np.sum(normalized_template * g)
      ### END YOUR CODE
  
      return out
  
apis: numpy.sum numpy.zeros numpy.linalg.svd numpy.flip numpy.std numpy.pad numpy.mean