Moravec Corner Detection(Theory and Code)

Moravec Corner Detection

Corners and Edges of an Image yield an interesting features of the image content that can be used in image retrieval and object detection or scene recognition tasks. So, they be called “Local invariant features“.

In this context we want to explain Moravec Corner Detection Method Which is a simple corner detection method and we write It ‘s Python Code. This method proposed by Hans Moravec who is an adjunct faculty member at the Robotics Institute of Carnegie Mellon University.

Hans Moravec (source: Carnegie Mellon University website)

The key idea behind the concept is simple, first look at 4 boxes in image below (Image 1). In box 1 (Left box) you see a black box with a blue window on it, that contains some data of black box in it, suppose this black box is an Image, if you move this blue window horizontally or vertically, data in the window won’t change, so, this is a flat surface. In the 2nd box, if you move the blue window vertically, content of the blue window won’t change. but, if move window in horizontal direction, content of the blue window will change (white pixels will be more or less), so, It means that a vertical edge is in the blue window. In 3rd box, only moving vertically will change the data in the blue window, that means a horizontal edge is here. But, in 4th image moving horizontally and vertically will change the data in the blue window, so, in 4th image content of the blue window is a corner.

Corner Detection
Image 1 : Image Edge and Corner

As you see here, Moravec method is a very simple method; however, It is useful, too. In the moravec paper we only move the blue window horizontally or vertically. though, others extend this method to move blue window in all directions for example if blue window is 3×3 box, the blue window can move in 8 directions.(Image below)

 
Moravec Corner Detection
Image 2: Pixel Direction with a 3 * 3 window
 

In a nutshell :

\\ \text{Changing data in all directions} \Longrightarrow \text{Corner} \\ \text{Changing data in one direction} \Longrightarrow \text{Edge (No Change along the Edge direction)} \\ \text{No change the data} \Longrightarrow \text{Flat} \\

So, to find all corners in an image first we should find grayscale of the image, then we find the difference of intensity between each box and it’s 8 close boxes.

To find the difference 3 main methods in machine learning usually used. Those are:

  1. Subtract of values: That is not suitable for us, for instance, in 2 images with matrix below The intensity differences for pixels is 0 that can be confuse us to say that there is no change.
    pixel intensity values
    Intensity\:Difference = (255 - 0) + (0 - 5) + (0 - 0) + (5 - 255) = 0

  2. Absolute value of differences. This is not suitable for optimization problems because this is not Differentiable.
  3. Square of the Difference (SD). This method does not have issues above so It is a useful method to calculate intensity differences. Mathematical definition of this method is below. (x_1, y_1) and (x_2,y_2) shows x and y position of 2 close pixels and I(x,y) is Intensity of pixel in (x,y)
    Square\:of\:the\:Difference = (I(x_1, y_1) - I(x_2,y_2))^2

Now, we know how moravec method works, but in real world senarios pixels are in 3 channels (Red, Green, Blue) and many of the pixels has Sqaure of Differences bigger than 0 (SD > 0) in all directions but all the time these pixels with SD > 0 are not Corner. Therefore, the practical method is to Compute Sum of Square of the Differences (SSD) and suppose a thereshold, if SSD > threshold then, It shows a corner.

in this formula w and h must have values to cover 8 pixel around the pixel that we want to see if it is a corner(Pixel A in Image below), so w and h is a member of set {(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0),(1,1)} to cover all the 8 pixels around A.

SSD= \sum_x \sum_y (I(x, y) - I(x+w,y+h))^2

There are many method to find a suitable threshold, Usually Machine Leaning method works good.

Now it’s time to see the Python code of the more of it corner detection method.

Disadvantages if Moravec method:

  1. Scale Invariant
  2. Strong response to edge points (can be sensitive to noise)
  3. Finding a good size for moving window is Experimental.
  4. Moravec corner detector only concerns eight principle directions which will have a poor repeatability rate.
from PIL import Image
from matplotlib import cm
import matplotlib.pyplot as plt
import numpy as np
import cv2
from tqdm import tqdm

I_org = cv2.imread(r"Images/pexels-mak-jp-11504568.jpg")
I = cv2.cvtColor(I_org,cv2.COLOR_RGB2GRAY)

numRows, numCols = I.shape[0], I.shape[1]    #h,w
directions = {
    'left':(0,-1),
    'right':(0,1),
    'up':(-1,0),
    'down':(1,0),
    'up_left':(-1,-1),
    'up_right':(-1,1),
    'down_left':(1,-1),
    'down_right':(1,1),
}

C = np.zeros(I.shape)
for i in tqdm(range(2,numRows-2)) :
    for j in range(2,numCols-2) :
        minSSD = -1
        for d in directions.values():
            u, v = d[0], d[1]
            P1 = I[i-1:i+2, j-1:j+2]
            P2 = I[i+u-1:i+u+2, j+v-1:j+v+2]
            ssd = np.sum((P1 - P2)**2)

            if minSSD == -1 :
                minSSD = ssd
            elif ssd < minSSD :
                minSSD = ssd

        C[i,j] = minSSD

th = C.mean()+2*C.std()
C_image = C > th


I2 = I_org#[:,:,::-1]
idx = np.argwhere(C_image)
r,c = idx[:,0],idx[:,1]
for i in tqdm(range(len(r))):
    I2 = cv2.circle(I2,(c[i],r[i]), radius=1,color=(0,0,255),thickness=-3) 

cv2.imshow("Result Image", I2)
cv2.imwrite("Result.jpg", I2)
cv2.waitKey()

to describe the problem of scale invariant of moravec algorithm, see image below, It can be seen that a corner can be detected as edge in a different scale.

Print Colorful Text in Python

Print by Different Color in Python
from termcolor import colored
print(colored('hello', 'red'), colored('world', 'green'))
print(colored("hello red world", 'red'))

Regular Expression (Regex) in Python

regex in python

Regex(Regular Expression) is a sequence of characters that define a search pattern. Regex can be used to check if a string contains the specified search pattern or find all the occurance of a Search pattern. The Idea of the Regular Expression first was invented by the American mathematician Stephen Cole Kleene who described regular language.

Stephen Cole Kleene

in this tutorial I try to explain regex in a simple way be examples.

Suppose we want to find all hash tags and callouts from tweet below :

First Example : We want to Extract all the words from the Tweet above, The Text of previous tweet is :

Ever wanted to sail the #SeaOfThieves?
With custom @Xbox backgrounds for video conferences, now you can: https://msft.it/6005TaGYD

As you See Words are seprated by space. So, We Split words by space charactor.

but Don’t forget first import needed package to use Regular Expression. we use re package in all of our codes in this page.

import re

After importing re Package then use code below to split sentence by space.

To avoid any confusion while dealing with regular expressions, we would use Raw Strings as r’expression’.

text = '''Ever wanted to sail the #SeaOfThieves?
With custom @Xbox backgrounds for video conferences, now you can: https://msft.it/6005TaGYD'''

allwords = re.split(r' ', text)
print(allwords)

this code separates words by comma. Output:

['Ever', 'wanted', 'to', 'sail', 'the', '#SeaOfThieves?\nWith', 'custom', '@Xbox', 'backgrounds', 'for', 'video', 'conferences,', 'now', 'you', 'can:', 'https://msft.it/6005TaGYD']

in the output above you see one word is “#SeaOfThieves?\nWith”. Do you what is \n in that word?

That is newline character, Means word after \n will be in the new line. in text above the word “with” is in the new line.

If you want Each Line :

text = '''Ever wanted to sail the #SeaOfThieves?
With custom @Xbox backgrounds for video conferences, now you can: https://msft.it/6005TaGYD'''

allwords = re.split(r'\n', text)
print(allwords)

this code separates Lines by comma. Output:

['Ever wanted to sail the #SeaOfThieves?', 'With custom @Xbox backgrounds for video conferences, now you can: https://msft.it/6005TaGYD']

a perfect program to split words correctly must consider space and \n and other white spaces, too. Beneath is list of patterns that show white spaces :

\nNew line
\tTab
\rCarriage return
\fForm feed
\vVertical tab

Now, if we want to Split Words by any whitespace above. We can use [ ]

[] – Square brackets

Square brackets specifies a set of characters you wish to match. Examples :

The re.findall() function is used to find all the matches for the pattern in the string.

str = 'Welcome to Code tips Academy Web Site'
matches = re.findall(r'[abc]', str)
print(matches)

#Output: ['c', 'c', 'a', 'b']

matches = re.findall(r'[abc A]', str)
print(matches)

#Output: ['c', ' ', ' ', ' ', ' ', 'A', 'c', 'a', ' ', 'b', ' ']

Then, We use [ \t\n\r\f\v], to Split words in tweet above by any white Space:

text = '''Ever wanted to sail the #SeaOfThieves?
With custom @Xbox backgrounds for video conferences, now you can: https://msft.it/6005TaGYD'''

allwords = re.split(r'[ \t\n\r\f\v]', text)
print(allwords)

output :

['Ever', 'wanted', 'to', 'sail', 'the', '#SeaOfThieves?', 'With', 'custom', '@Xbox', 'backgrounds', 'for', 'video', 'conferences,', 'now', 'you', 'can:', 'https://msft.it/6005TaGYD']

As a matter of fact we can use \s instead of [ \t\n\r\f\v]

text = '''Ever wanted to sail the #SeaOfThieves?
With custom @Xbox backgrounds for video conferences, now you can: https://msft.it/6005TaGYD'''

allwords = re.split(r'\s', text)
print(allwords)

As It’s shown below result is the same as splitting by [ \t\n\r\f\v]

['Ever', 'wanted', 'to', 'sail', 'the', '#SeaOfThieves?', 'With', 'custom', '@Xbox', 'backgrounds', 'for', 'video', 'conferences,', 'now', 'you', 'can:', 'https://msft.it/6005TaGYD']

Popular Patterns in Regex

SymbolDescription
.dot matches any character except newline
\wmatches any word character i.e letters, alphanumeric, digits and underscore (_)
\Wmatches non word characters
\dmatches a single digit
\Dmatches a single character that is not a digit
\smatches any white-spaces character like \n, \t, spaces
\Smatches single non white space character
[abc]matches single character in the set i.e either match a, b or c
[^abc]match a single character other than a, b and c
[a-z]match a single character in the range a to z.
[a-zA-Z]match a single character in the range a-z or A-Z
[0-9]match a single character in the range 0–9
^match start at beginning of the string
$match start at end of the string
+matches one or more of the preceding character (greedy match).
*matches zero or more of the preceding character (greedy match).
a|bMatches either a or b.
re{n,m}Matches at least n and at most m occurrences of preceding
expression.
re{n}Matches exactly n number of occurrences of preceding
expression.
re{ n,}Matches n or more occurrences of preceding expression.
re?Matches 0 or 1 occurrence of preceding expression.
re+Matches 1 or more occurrence of preceding expression.
re*Matches 0 or more occurrences of preceding expression.
(re)Groups regular expressions and remembers matched text (Only the regular Expression before and after parentheses will be matched but only the regular Expression inside the parentheses will be shown to us as input. ).
(?imx)Temporarily toggles on i, m, or x options within a regular
expression. If in parentheses, only that area is affected.
(?: re)Groups regular expressions without remembering matched text.

Now, We want to find all the hash tags from Tweet above

text = '''Ever wanted to sail the #SeaOfThieves?
With custom @Xbox backgrounds for video conferences, now you can: https://msft.it/6005TaGYD'''

hashTagResult = re.findall(r'#[a-zA-Z0-9_]+', text)
print(hashTagResult)

#[a-zA-Z0-9_]+ means find all the text that
  • Starts with #
  • There is any alphabet in lower case from a to z, or any alphabet in uppercase from a to z, or a digit from 0 to 9 or _ after #
  • + means anything inside [ ] must be at least once.

output 

['#SeaOfThieves']

If we want to extract all the callouts

text = '''Ever wanted to sail the #SeaOfThieves?
With custom @Xbox backgrounds for video conferences, now you can: https://msft.it/6005TaGYD'''

atSignResult = re.findall(r'@[a-zA-Z0-9_]+', text)
print(atSignResult)

@[a-zA-Z0-9_]+ means find all the text that
  • Starts with @
  • There is any alphabet in lower case from a to z, or any alphabet in uppercase from a to z, or a digit from 0 to 9 or _ after @
  • + means anything inside [ ] must be at least once.

output

['@Xbox']

Example : Get All word with at least5 characters. 

text = '''Ever wanted to sail the #SeaOfThieves?
With custom @Xbox backgrounds for video conferences, now you can: https://msft.it/6005TaGYD'''

allwords = re.findall(r'\w{5,}', text)
print(allwords)

output

['wanted', 'SeaOfThieves', 'custom', 'backgrounds', 'video', 'conferences', 'https', '6005TaGYD']

In next Example we extract all the Numbers from Text.

sampleText = 'there are 54 apples here. Tempertaure is -23. I have 2124 in my account.'
sampleTextResult = re.findall(r'[-+]?[0-9]+', sampleText)
print(sampleTextResult)

[-+]?[0-9]+ means start of number can be – or + sign ( ? means having – or + is optional and not more that one character is + or -). then I must have at least 1 digit.

Output

['54', '-23', '2124']

To Extract any Urls from Tweet above

urlRegex = '''http[s]?://(?:[a-zA-Z]|[0-9]|[$-_@.&+]|[!*\(\),]|(?:%[0-9a-fA-F][0-9a-fA-F]))+'''
urlRegexResult = re.findall(urlRegex, text)
print(urlRegexResult)

(?:%[0-9a-fA-F][0-9a-fA-F]) this matches hexadecimal character codes in URLs e.g. %2f for the ‘/’ character.

[s]? means ‘s’ character is optional,  but that’s because of the ? not of the brackets.

Output

['https://msft.it/6005TaGYD']

Now, If we want to Extract all the hashtags and callouts of our sample Tweet.

text = '''Ever wanted to sail the #SeaOfThieves?
With custom @Xbox backgrounds for video conferences, now you can: https://msft.it/6005TaGYD'''

result = re.findall(r'(?:@[a-zA-Z0-9_]+|#[a-zA-Z0-9_]+)', text)
print(result)

Output

['#SeaOfThieves', '@Xbox']

You can also check if a input string has correct format or not by using Regular Expression.

text = 'codetipsacademy@gmail.com'

result = re.match(r'^[\w\.\+\-]+\@[\w]+\.[a-z]{2,3}$',text)
print(result)

Result :

<re.Match object; span=(0, 25), match='codetipsacademy@gmail.com'>

As you See I used ^ and $ in the pattern, this means that text must be start by pattern after ^ and before $, nothing else must be in the text string. if text Contains Some other string in addition to email matching will fail.

text = 'My email is codetipsacademy@gmail.com'

result = re.match(r'^[\w\.\+\-]+\@[\w]+\.[a-z]{2,3}$',text)
print(result)

Result

None

So, Use ^ and $ usually for text Matching not for Searching.