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.[1] 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 {W1,...,W9} as:
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}
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}
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}
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}
W9 = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}
- The pair
(W1, W2)is the isotropic average gradient - The pair
(W3, W4)is used to detect ripples - The pair
(W5,W6)is used to detect lines - The pair
(W7,W8)is the discrete laplacian operator W9, the averaging operator, added to complete the basisW1,...W4are used for edges subspace,W5,...W8used for lines subspace andW9is used to compute averages
Let B be the image sub-area, and \theta be the angle (in n^2space), e is the number of orthogonal edge basis vectors W_1,...W_e spanning the edge subspace.
\theta = \arccos \left [ \textstyle \sum_{i=1}^e \displaystyle (B * W_i)^2 / \textstyle \sum_{i=1}^9 \displaystyle (B * W_i)^2 \right ]^{\frac{1}{2}}
The larger \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 \theta is small which is done by thresholding.
Simple description
The image is convolved with each of the kernel. Thus, 9 results are obtained.
Vectors W_1, ... W_4 are used for edge subspace identification. Hence numerator in the formula will be \textstyle \sum_{i=1}^4 \displaystyle (B * W_i)^2. Similarly, for line subspace identification, the numerator will be \textstyle \sum_{i=5}^8 \displaystyle (B * W_i)^2.
Using formula, we compute \theta, if it is above a certain threshold 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.
See also
References
- ^ 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