User:SandioMama/sandbox

The Moravec operator is a corner detection algorithm that extracts features of interest from images. It is developed by Hans Moravec in 1977 for his research in navigation of a robot through a clustered environment ^[1].

The Moravec Operator is one of the earliest corner detection algorithms. It is considered a corner detector, because it extracts features of interest from images where there are large intensity variations in a number of directions. Originally, Moravec was not interested in finding corners, but points of interest that could be used to find matching regions in consecutive image frames ^[2].

The algorithm examines every pixel in an image to see if there is a corner present. This is done by considering how similar a square window centered on the pixel is to windows with the same size shifted by a small amount in eight directions ( 2 horizontal, 2 vertical and 4 diagonals). Similarity is measured by taking the mean squared error between the original and shifted square windows, thus determining the average changes in image intensity.

File:MoravecExample.gif

Different cases for the Moravec operator

There are four types of positions that show all major cases of where the square window can be placed. If the pixel of interest is internal to an object or is located on the background (uniform intensity), then shifting the window in all directions will result in a small intensity change. If the window straddles an edge, then shifts perpendicular to the edge will result in large intensity variations and shifts along the edge - in a small change. As a last case, if the pixel of interest corresponds to a corner or an isolated pixel, then the result will be a large intensity variation for all shift directions ^[3].

Theory

The Moravec operator main purpose is to give a measure of the cornerness (corner strength) of every pixel in an image. This value is the minimum intensity measured over all directions of movement of the window. Here is a mathematical specification:

$\textstyle E_{x,y}=\sum _{u,v}w_{u,v}(I_{x+u,y+v}-I_{u,v})^{2}$

where $I$ denotes the image intensities, $E$ is the change produced by a shift(x,y), $w$ specifies the image window ^[3]. The Moravec operator is simply looking for local maxima in $min(E)$ above some threshold.

Algorithm

The algorithm consists of the following steps:

For each pixel $(u,v)$ in the image calculate the intensity change from a shift $(x,y)$ as: $\textstyle E_{x,y}=\sum _{u,v}w_{u,v}(I_{x+u,y+v}-I_{u,v})^{2}$ , where shifts are: $(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)$
Find a local maximum in $min(E)$ for each pixel $(u,v)$
Set $min(E)$ for every pixel to zero if below some threshold $T$
Perform Non-maximum suppression to find local maxima
Find all pixels with non-zero values and mark them as corners

Examples

Figures below show some test images with Moravec operator applied to them. In all cases a 3x3 window was used. The chosen threshold varies and was set manualy to maximise the number of true corners detected.

One might notice that the Moravec operator detects corners on diagonal edges in all three examples. Along diagonal edges, there is a large intensity variation in all directions except when the direction is parallel to the diagonal edge, thus edges get assigned a large cornerness measure.

File:MoravecArtificialTest.gif

Artificial image

File:MoravecBlocksTest.gif

Image of blocks

File:MoravecHouseTest.gif

Image of a house

Performance evaluation

The Moravec operator suffers from a number of problems.

Anisotropic Response of Operator

One of the main problems with this operator is that it is not isotropic (anisotropy): if an edge is present that is not in the direction of the neighbours, then it will not be detected as an interest point, i.e. only a discrete set of shifts at every 45 degrees is considered. Consequently, the Moravec operator is not rotationally invariant.

Noise sensitivity

The Moravec operator uses a window that has a square shape and is binary. This results in a noisy response from the corner detector.

A solution is to use a circular window so that the Euclidean distance from the center to the edges of the window will remain the same in all directions. Another improvement is to place weight on the pixel near the center of the window. Logically, the differences in pixel intensities near the center of the window will give a better indication of local variance. Those two improvements suggest the use of Gaussian window ^[3].

Response to edges

The Moravec operator responds readily to edges. It can detect corners on edges due to noise, intensity quantisation and other factors. This can result in a large intensity variation in all eight principle directions. As a result, the Moravec operator is susceptible to reporting false corners along edges.

Applications

The operator is computationally efficient which was important for Moravec as he was doing real-time application with minimal computational power ^[1].The operator has a number of limitations which are addressed by the Harris & Stephens / Plessey / Shi-Tomasi corner detector, which has better performance at the cost of increased computation.

References

^ ^a ^b Moravec, Hans (1977). "Towards Automatic Visual Obstacle Avoidance". Proc. 5th International Joint Conference on Artificial Intelligence: 584.
^ Moravec, Hans (1980). "Obstacle Avoidance and Navigation in the Real World by a Seeing Robot Rover". Tech Report CMU-RI-TR-3 Carnegie-Mellon University, Robotics Institute.
^ ^a ^b ^c C. Harris and M. Stephens (1988). "A combined corner and edge detector" (PDF). Proceedings of the 4th Alvey Vision Conference. pp. 147–151. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)

External links

Category:Image processing

[moravec-1] Moravec, Hans (1977). "Towards Automatic Visual Obstacle Avoidance". Proc. 5th International Joint Conference on Artificial Intelligence: 584.

[moravec2-2] Moravec, Hans (1980). "Obstacle Avoidance and Navigation in the Real World by a Seeing Robot Rover". Tech Report CMU-RI-TR-3 Carnegie-Mellon University, Robotics Institute.

[harris-3] C. Harris and M. Stephens (1988). "A combined corner and edge detector" (PDF). Proceedings of the 4th Alvey Vision Conference. pp. 147–151. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)

[1]

[2]

[3]