Skip to content

Instantly share code, notes, and snippets.

@payne911
Last active June 25, 2020 18:50
Show Gist options
  • Save payne911/2a7474d113159ad6c632618bd620a861 to your computer and use it in GitHub Desktop.
Save payne911/2a7474d113159ad6c632618bd620a861 to your computer and use it in GitHub Desktop.
Convex test on binary images (Image integral for Pattern Matching)
import cv2 as cv
def integral_test(X): # returns True if X is convex
img_t = np.reshape(X, (28, 28)) # preprocess: reshaping
int_result = cv.integral(img_t.astype(np.uint8)) # calculating the integral-image
patterns_to_test = [block_patterns, big_block_patterns, horizontal_patterns, vertical_patterns,
horizontal_patterns2, vertical_patterns2, bigger_block_patterns, horizontal_patterns3,
vertical_patterns3, bbigger_block_patterns, bbbigger_block_patterns, bbbbigger_block_patterns]
for p in range(len(patterns_to_test)): # run test on all patterns until a match is found
patterns = patterns_to_test[p]
img_x = len(patterns[0][0])
img_y = len(patterns[0])
nbr = np.sum(patterns[0])
pts_of_interest = find_area(int_result, nbr, img_y, img_x)
success = find_match(img_t, patterns, pts_of_interest)
if success:
break
return not success # because we have found if it's NOT-convex
def find_area(img, target, x_len, y_len): # finds points of interest
tmp_interest = []
for x in range(len(img)): # for each row
if x >= len(img) - x_len:
break
for y in range(len(img[x])): # for each column
if y >= len(img[x]) - y_len:
break
tmp_sum = img[x, y] + img[x + x_len, y + y_len] - img[x + x_len, y] - img[x, y + y_len] # constant time
if tmp_sum == target:
tmp_interest.append((x, y))
return tmp_interest
def find_match(img, patterns, points): # returns True if the shape is found (aka img is NOT-convex)
pattern_x = patterns[0].shape[0]
pattern_y = patterns[0].shape[1]
target = pattern_x * pattern_y
for pattern in patterns:
for (px, py) in points:
counter = 0
for x in range(pattern_x):
for y in range(pattern_y):
if img[x + px][y + py] == pattern[x][y]: # a match was found for a pixel
counter = counter + 1
if counter == target: # exact amount of pixels matched
return True
return False
def is_convex(X): # the complete test for classification
if is_convex_primary_test(X):
return integral_test(X)
else:
return False
def is_convex_primary_test(X):
found_a_white_pixel = False
followed_by_full_black_row = False
consecutive_black = 0
for y in range(28): # left to right, from top to bottom
offset = 28 * y
last_check = X[offset] # override last pixel
if last_check == 1: # observe first pixel of the row
changes = 1 # when we begin inside a region
black_counter = 0
else:
changes = 0
black_counter = 1
consecutive_black = consecutive_black + 1
for x in range(28): # black line separation test
p = X[x + offset]
if p == 1:
consecutive_black = 0
found_a_white_pixel = True
if followed_by_full_black_row:
return False # found a second "object"
else:
black_counter = black_counter + 1
consecutive_black = consecutive_black + 1
if (black_counter == 29 or consecutive_black == 30) and found_a_white_pixel:
followed_by_full_black_row = True # found a black row after a white pixel
if last_check != p: # change test: cannot have a black pixel between white pixels on the same row
changes = changes + 1
if changes > 2:
return False
last_check = p # keep in memory the last observed pixel for next comparison
found_a_white_pixel = False
followed_by_full_black_row = False
consecutive_black = 0
for x in range(28): # top to bottom, from right to left
x = 27-x # to reverse "left to right"
last_check = X[x]
if last_check == 1:
changes = 1
black_counter = 0
else:
changes = 0
black_counter = 1
consecutive_black = consecutive_black + 1
for y in range(28):
offset = 28 * y
p = X[x + offset]
if p == 1:
consecutive_black = 0
found_a_white_pixel = True
if followed_by_full_black_row:
return False
else:
black_counter = black_counter + 1
consecutive_black = consecutive_black + 1
if (black_counter == 29 or consecutive_black == 30) and found_a_white_pixel:
followed_by_full_black_row = True
if last_check != p:
changes = changes + 1
if changes > 2:
return False
last_check = p
return True # has passed all the tests
import numpy as np
# patterns as global variables
pattern1 = np.asarray([[1, 0, 0, 0, 0],
[1, 1, 0, 0, 0],
[1, 1, 1, 1, 1]])
pattern2 = np.rot90(pattern1)
pattern3 = np.rot90(pattern2)
pattern4 = np.rot90(pattern3)
pattern5 = np.fliplr(pattern1)
pattern6 = np.rot90(pattern5)
pattern7 = np.rot90(pattern6)
pattern8 = np.rot90(pattern7)
horizontal_patterns = [pattern1, pattern5, pattern3, pattern7]
vertical_patterns = [pattern2, pattern6, pattern4, pattern8]
pattern9 = np.asarray([[1, 0, 0],
[1, 0, 0],
[1, 1, 1]])
pattern10 = np.rot90(pattern9)
pattern11 = np.rot90(pattern10)
pattern12 = np.rot90(pattern11)
block_patterns = [pattern9, pattern10, pattern11, pattern12]
pattern13 = np.asarray([[1, 0, 0, 0],
[1, 0, 0, 0],
[1, 1, 0, 0],
[1, 1, 1, 1]])
pattern14 = np.rot90(pattern13)
pattern15 = np.rot90(pattern14)
pattern16 = np.rot90(pattern15)
big_block_patterns = [pattern13, pattern14, pattern15, pattern16]
pattern17 = np.asarray([[1, 0, 0, 0, 0],
[1, 0, 0, 0, 0],
[1, 1, 0, 0, 0],
[1, 1, 1, 0, 0],
[1, 1, 1, 1, 1]])
pattern18 = np.rot90(pattern17)
pattern19 = np.rot90(pattern18)
pattern20 = np.rot90(pattern19)
bigger_block_patterns = [pattern17, pattern18, pattern19, pattern20]
pattern21 = np.asarray([[1, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0],
[1, 1, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 0],
[1, 1, 1, 1, 0, 0],
[1, 1, 1, 1, 1, 1]])
pattern22 = np.rot90(pattern21)
pattern23 = np.rot90(pattern22)
pattern24 = np.rot90(pattern23)
bbigger_block_patterns = [pattern21, pattern22, pattern23, pattern24]
pattern33 = np.asarray([[1, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0],
[1, 1, 0, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 0],
[1, 1, 1, 1, 0, 0, 0],
[1, 1, 1, 1, 1, 0, 0],
[1, 1, 1, 1, 1, 1, 1]])
pattern34 = np.rot90(pattern33)
pattern35 = np.rot90(pattern34)
pattern36 = np.rot90(pattern35)
bbbigger_block_patterns = [pattern33, pattern34, pattern35, pattern36]
pattern45 = np.asarray([[1, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 0, 0],
[1, 1, 1, 1, 1, 1, 1, 1]])
pattern46 = np.rot90(pattern45)
pattern47 = np.rot90(pattern46)
pattern48 = np.rot90(pattern47)
bbbbigger_block_patterns = [pattern45, pattern46, pattern47, pattern48]
pattern25 = np.asarray([[1, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1]])
pattern26 = np.rot90(pattern25)
pattern27 = np.rot90(pattern26)
pattern28 = np.rot90(pattern27)
pattern29 = np.fliplr(pattern25)
pattern30 = np.rot90(pattern29)
pattern31 = np.rot90(pattern30)
pattern32 = np.rot90(pattern31)
horizontal_patterns2 = [pattern25, pattern29, pattern27, pattern31]
vertical_patterns2 = [pattern26, pattern30, pattern28, pattern32]
pattern37 = np.asarray([[1, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1, 1, 1]])
pattern38 = np.rot90(pattern37)
pattern39 = np.rot90(pattern38)
pattern40 = np.rot90(pattern39)
pattern41 = np.fliplr(pattern37)
pattern42 = np.rot90(pattern41)
pattern43 = np.rot90(pattern42)
pattern44 = np.rot90(pattern43)
horizontal_patterns3 = [pattern37, pattern41, pattern39, pattern43]
vertical_patterns3 = [pattern38, pattern42, pattern40, pattern44]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment