Misplaced Pages

An editor has performed a search and found that sufficient sources exist to establish the subject's notability. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Frei-Chen operator" – news · newspapers · books · scholar · JSTOR (July 2024) (Learn how and when to remove this message)

The Frei-Chen operator, sometimes called Frei and Chen operator, is used in image processing for edge detection. It was proposed by Werner Frei and Chung-Ching Chen, researchers at USC's Image Processing Institute, in 1977. The idea is to use a set of orthogonal basis vectors related to distinctive image features, which enable the algorithm to extract boundary elements effectively.

Formulation

The operator uses nine 3x3 kernels which are convolved with the original image to calculate the gradient.

We define the nine kernels ${\displaystyle {W1,...,W9}}$ as:

${\displaystyle W1={\begin{bmatrix}1&{\sqrt {2}}&1\\0&0&0\\-1&-{\sqrt {2}}&-1\end{bmatrix}}\quad W2={\begin{bmatrix}1&0&-1\\{\sqrt {2}}&0&-{\sqrt {2}}\\1&0&-1\end{bmatrix}}}$

${\displaystyle W3={\begin{bmatrix}0&-1&{\sqrt {2}}\\1&0&-1\\-{\sqrt {2}}&1&0\end{bmatrix}}\quad W4={\begin{bmatrix}{\sqrt {2}}&-1&0\\-1&0&1\\0&1&-{\sqrt {2}}\end{bmatrix}}}$

${\displaystyle W5={\begin{bmatrix}0&1&0\\-1&0&-1\\0&1&0\end{bmatrix}}\quad W6={\begin{bmatrix}-1&0&1\\0&0&0\\1&0&-1\end{bmatrix}}}$

${\displaystyle W7={\begin{bmatrix}1&-2&1\\-2&4&-2\\1&-2&1\end{bmatrix}}\quad W8={\begin{bmatrix}-2&1&-2\\1&4&1\\-2&1&-2\end{bmatrix}}}$

${\displaystyle W9={\begin{bmatrix}1&1&1\\1&1&1\\1&1&1\end{bmatrix}}}$

• The pair ${\displaystyle (W1,W2)}$ is the isotropic average gradient
• The pair ${\displaystyle (W3,W4)}$ is used to detect ripples
• The pair ${\displaystyle (W5,W6)}$ is used to detect lines
• The pair ${\displaystyle (W7,W8)}$ is the discrete laplacian operator
• ${\displaystyle W9}$, the averaging operator, added to complete the basis

• ${\displaystyle W1,...W4}$ are used for edges subspace, ${\displaystyle W5,...W8}$ used for lines subspace and ${\displaystyle W9}$ is used to compute averages

Let ${\displaystyle B}$ be the image sub-area, and ${\displaystyle \theta }$ be the angle (in ${\displaystyle n^{2}}$space), ${\displaystyle e}$ is the number of orthgonal edge basis vectors ${\displaystyle W_{1},...W_{e}}$ spanning the edge subspace.

${\displaystyle \theta =\arccos \left^{\frac {1}{2}}}$

The larger ${\displaystyle \theta }$, the poorer the fit between B and an element of the edge subspace.

The strategy is to classify image sub-area as containing and edge element only if ${\displaystyle \theta }$ is small which is done by thresholding.

Simple description

The image is convoled with each of the kernel. Thus, 9 results are obtained.

Vectors ${\displaystyle W_{1},...W_{4}}$ are used for edge subspace identification. Hence numerator in the formula will be ${\displaystyle \textstyle \sum _{i=1}^{4}\displaystyle (B*W_{i})^{2}}$. Similarly, for line subspace identification, the numerator will be ${\displaystyle \textstyle \sum _{i=5}^{8}\displaystyle (B*W_{i})^{2}}$.

Using formula, we compute ${\displaystyle \theta }$, if it is above a certain threshold ${\displaystyle r}$, we say that an edge is detected in the image sub-area.

Example comparisons

Here, frie-chen operator, along with three different gradient operators is used to detect edges in the test image.

• Grayscale test image of brick wall and bike rack
• Edge detection using Frie-Chen operator
• Edge detection using Roberts cross operator
• Edge detection using Prewitt operator
• Edge detection using Sobel operator

See also

• Digital Image Processing
• Edge Detection
• Roberts Cross
• Prewitt Operator
• Sobel Operator

References

1. Frei; Chung-Ching Chen (October 1977). "Fast Boundary Detection: A Generalization and a New Algorithm". IEEE Transactions on Computers. C-26 (10): 988–998. doi:10.1109/TC.1977.1674733. ISSN 0018-9340.

• Edge detection