2
$\begingroup$

Prewitt gradient operator

Show that the Prewitt gradient operator can be obtained by fitting the least-squares plane through the 3 × 3 neighborhood of the intensity function.

Hint: Fit a plane to the nine points (x + $\delta$x,y + $\delta$y,I[x + $\delta$x,y + $\delta$y]) where $\delta$x and $\delta$y range through −1, 0, +1. Then, having the planar model z = ax + by + c that best fits the intensity surface (i.e. minimizes the least-squares error in the z-direction), show that the two Prewitt masks actually compute a and b.

Solution: We denote the nine points by ($x_j$,$y_j$,$z_j$), $j$ = 1,...,9. The least-squares error for the planar model is: $$ \epsilon(a,b,c) = \sum_{j= 1}^n(ax_j, + by_j + c + z_j)^2\tag{1} $$ By differentation we get \begin{align*} \nabla\epsilon &= \begin{bmatrix} \sum_{j= 1}^n(ax_j, + by_j + c + z_j)x_j\\ \sum_{j= 1}^n(ax_j, + by_j + c + z_j)y_j\\ \sum_{j= 1}^n(ax_j, + by_j + c + z_j) \end{bmatrix}\\\tag{2} \end{align*} by setting the gradient to zero $$ \implies=\begin{bmatrix} \sum_{j = 1}^nx_j^2&\sum_{j = 1}^nx_jy_j&\sum_{j = 1}^nx_j\\ \sum_{j = 1}^nx_jy_j&\sum_{j = 1}^ny_j^2&\sum_{j = 1}^ny_j \\ \sum_{j = 1}^nx_j&\sum_{j = 1}^ny_j&n \end{bmatrix} \begin{bmatrix} a\\ b\\ c \end{bmatrix} = \begin{bmatrix} \sum_{j = 1}^nx_jz_j\\ \sum_{j = 1}^ny_jz_j\\ \sum_{j = 1}^nz_j \end{bmatrix}\tag{3} $$ For our 3 $\times$ 3 neighborhood we may fix the coordinate origin at the center of the mask. In this case $x_j$ and $y_j$ range through −1, 0, +1 and the normal equations have the form $$\begin{bmatrix} \color{blue}6 & 0 &0 \\ 0 & \color{blue}6 & \color{red}9\\ 0 & 0 & \color{blue}9 \end{bmatrix} \begin{bmatrix} a\\ b\\ c \end{bmatrix} = \begin{bmatrix} \sum_{j = 1}^nx_jz_j\\ \sum_{j = 1}^ny_jz_j\\ \sum_{j = 1}^nz_j \end{bmatrix}\tag{4} $$ Therefore the optimal plane is obtained by $$ \begin{bmatrix} a\\ b\\ c \end{bmatrix} = \begin{bmatrix} \frac{1}{6}\sum_{j = 1}^nx_jz_j\\ \frac{1}{6}\sum_{j = 1}^ny_jz_j\\ \frac{1}{9}\sum_{j = 1}^nz_j \end{bmatrix}\tag{5} $$ where the first two components are obtained by using the Prewitt masks: $$ M_x = \begin{bmatrix} -1 & 0 & 1\\ -1 & 0 & 1\\ -1 & 0 & 1\\ \end{bmatrix}, \quad M_y = \begin{bmatrix} 1 & 1 & 1\\ 0 & 0 & 0\\ -1 & -1 & -1\\ \end{bmatrix}\tag{6} $$

My questions

  • In (4), where do the $\color{blue}6$, $\color{blue}6$ and $\color{blue}9$
  • In (4), shouldn't the $\color{red}9$ be a $\color{red}0$ instead?
  • How can we get the insight between (5) and (6) (the relation with Prewitt mask)?
$\endgroup$
  • 1
    $\begingroup$ In (4), the red 9 is out of place. It should be in the bottom right. As for the origins of these numbers: Remember that the $x_j$ and $y_j$ are $-1,0,+1$. $\endgroup$ – Wolfgang Bangerth Dec 27 '19 at 23:38
  • $\begingroup$ Thanks for your comment @WolfgangBangerth. So from your comment I understand that $\color{red}9$ should indeed be a $\color{red}0$. For the origins of the $\color{blue}6$, $\color{blue}6$, $\color{blue}9$, could you develop a little bit the steps needed between the fact that $x_j$ and $y_j$ are -1, 0, +1 and the obtention of the matrix in (4)? $\endgroup$ – ecjb Dec 28 '19 at 9:15
  • $\begingroup$ Think about the first entry. You're adding 9 numbers $x_j^2$. These are the 9 $x$-coordinates of the origin and the 8 points with integer coordinates that surround it. Of these, 3 points have $x_j=-1$, 3 points have $x_j=0$, and 3 points have $x_j=+1$. So adding up $x_j^2$ yields 6 times 1 plus 3 times 0. That's 6. $\endgroup$ – Wolfgang Bangerth Dec 28 '19 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.