Determine concave point

Question

If I use the goodFeaturesToTrack, I can get all corner points (red, blue). However, I only want to keep the concave points (blue). I have no ideas how to implement. How can I do it?

The following image is the actual running sample:

Answer 1

As mentioned in the comments, it seems like the easy thing to do here is to convolve your image with a box filter (or similar but with an elliptical shape) which will give you windowed averages all over your image. You can simply index this convolution result at your corner points. If the convolution result at those points is more than 50%, there's more white around that point, ergo, it is a concave point. Otherwise, it is convex. Here's what that might look like in code.

import cv2
import numpy as np
from itertools import tee

def pairwise(iterable):
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

# read image as grayscale
img = cv2.imread('example.png', 0)

# get corner points, remove duplicate/nearby points
contours = cv2.findContours(img, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)[1]
contour = contours[0]
pts = np.array([contour[0]] + [pt1 for pt0, pt1 in pairwise(contour) if not (abs(pt0 - pt1) <= 1).all()])
x, y = pts[:, -1, 0], pts[:, -1, 1]

# get the kernel that you will sum around your corner points
kernel = np.float64(cv2.getStructuringElement(cv2.MORPH_ELLIPSE, (13, 13)))
kernel /= np.sum(kernel)

# convolve the image with the kernel, and pull out the sums at the corner points
conv = cv2.filter2D(img/255, cv2.CV_64F, kernel)
neighborhood_sums = conv[y, x]

# concave indices have more white than black around them, so convolution will be >= 1/2
concave_indices = neighborhood_sums >= 0.5

# draw markers
marked = cv2.merge([img, img, img])
for pt, concave in zip(pts, concave_indices):
    color = (255, 0, 255) if concave else (0, 255, 0)
    marker = cv2.MARKER_TRIANGLE_UP if concave else cv2.MARKER_TRIANGLE_DOWN
    cv2.drawMarker(marked, tuple(pt[0]), color, markerType=marker, markerSize=10, thickness=3)

After the imports I defined one of the itertools recipes for iterating things in pairs (e.g. s -> (s0, s1), (s1, s2), ...). This isn't really important at all to the problem but is just useful for me getting rid of duplicate points that were grabbed from findContours(). After that, the rest proceeds as previously described. You can draw your own kernel or whatever you like, but I just pulled one from getStructuringElement() since you can do ellipses of arbitrary size (although note that this returns a strangely shaped kernel, you could define a circle better yourself likely). Note the size of the kernel is specified in total width here, not just radius, and it's normalized by the number of 1s in it so that the result is always between 0 and 1.

And here's the result of the above on your first image: