Activity 3.2.4 Edge detection

An important problem in the field of computer vision is to detect edges in a digital photograph, as is shown in FigureĀ 3.2.10. Edge detection algorithms are useful when, say, we want a robot to locate an object in its field of view. Graphic designers also use these algorithms to create artist effects.

Figure 3.2.10 A canyon wall in Capitol Reef National Park and the result of an edge detection algorithm.

We will consider a very simple version of an edge detection algorithm to give a sense of how this works. Rather than considering a two-dimensional photograph, we will think about a one-dimensional row of pixels in a photograph. The grayscale values of a pixel measure the brightness of a pixel; a grayscale value of 0 corresponds to black, and a value of 255 corresponds to white.

Suppose, for simplicity, that the grayscale values for a row of six pixels are represented by a vector \(\xvec\) in \(\real^6\text{:}\)

\begin{equation*} \xvec = \left[\begin{array}{r} 25 \\ 34 \\ 30 \\ 45 \\ 190 \\ 200 \end{array}\right]\text{.} \end{equation*}

We can easily see that there is a jump in brightness between pixels 4 and 5, but how can we detect it computationally? We will introduce a new basis \(\bcal\) for \(\real^6\) with vectors:

\begin{equation*} \vvec_1=\left[\begin{array}{r} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{array}\right], \vvec_2=\left[\begin{array}{r} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{array}\right], \vvec_3=\left[\begin{array}{r} 1 \\ 1 \\ 1 \\ 0 \\ 0 \\ 0 \end{array}\right], \vvec_4=\left[\begin{array}{r} 1 \\ 1 \\ 1 \\ 1 \\ 0 \\ 0 \end{array}\right], \vvec_5=\left[\begin{array}{r} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 0 \end{array}\right], \vvec_6=\left[\begin{array}{r} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{array}\right]\text{.} \end{equation*}
  1. Construct the matrix \(C_\bcal\) that relates the standard coordinate system with the coordinates in the basis \(\bcal\text{.}\)

  2. Determine the matrix \(C_\bcal^{-1}\) that converts the representation of \(\xvec\) in standard coordinates into the coordinate system defined by \(\bcal\text{.}\)

  3. Suppose the vectors are expressed in general terms as

    \begin{equation*} \xvec = \left[\begin{array}{r} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \end{array}\right], \coords{\xvec}{\bcal} = \left[\begin{array}{r} c_1 \\ c_2 \\ c_3 \\ c_4 \\ c_5 \\ c_6 \end{array}\right]\text{.} \end{equation*}

    Using the relationship \(\coords{\xvec}{\bcal} = C_{\bcal}^{-1}\xvec\text{,}\) determine an expression for the coefficient \(c_2\) in terms of \(x_1,x_2,\ldots,x_6\text{.}\) What does \(c_2\) measure in terms of the grayscale values of the pixels? What does \(c_4\) measure in terms of the grayscale values of the pixels?

  4. Now for the specific vector

    \begin{equation*} \xvec = \left[\begin{array}{r} 25 \\ 34 \\ 30 \\ 45 \\ 190 \\ 200 \end{array}\right]\text{,} \end{equation*}

    determine the representation of \(\xvec\) in the \(\bcal\)-coordinate system.

  5. Explain how the coefficients in \(\coords{\xvec}{\bcal}\) determine the location of the jump in brightness in the grayscale values represented by the vector \(\xvec\text{.}\)

Readers who are familiar with calculus may recognize that this change of basis converts a vector \(\xvec\) into \(\coords{\xvec}{\bcal}\text{,}\) the set of changes in \(\xvec\text{.}\) This process is similar to differentiation in calculus. Similarly, the process of converting \(\coords{\xvec}{\bcal}\) into the vector \(\xvec\) adds together the changes in a process similar to integration. This change of basis, therefore, represents a linear algebraic version of the Fundamental Theorem of Calculus.

in-context