OpenCV: Minimum distance between arbitrarily large sets of contours (Python)

Question

I'm interested in calculating the average minimum distance between elements of two sets of contours.

Here is a sample image:

Here's my code so far:

    import cv2
    import numpy as np

def contours(layer):
    gray = cv2.cvtColor(layer, cv2.COLOR_BGR2GRAY)
    ret,binary = cv2.threshold(gray, 1,255,cv2.THRESH_BINARY) 
    image, contours, hierarchy =         cv2.findContours(binary,cv2.RETR_TREE,cv2.CHAIN_APPROX_NONE)
    drawn = cv2.drawContours(image,contours,-1,(150,150,150),3)
    return contours, drawn

def minDistance(contour, contourOther):
    distanceMin = 99999999
    for xA, yA in contour[0]:
        for xB, yB in contourOther[0]:
            distance = ((xB-xA)**2+(yB-yA)**2)**(1/2) # distance formula
            if (distance < distanceMin):
                distanceMin = distance
    return distanceMin

def cntDistanceCompare(contoursA, contoursB):
    cumMinDistList = []
    for contourA in contoursA:
        indMinDistList = []
        for contourB in contoursB:
            minDist = minDistance(contourA,contourB)
            indMinDistList.append(minDist)
        cumMinDistList.append(indMinDistList)
    l = cumMinDistList  
    return sum(l)/len(l) #returns mean distance

def maskBuilder(bgr,hl,hh,sl,sh,vl,vh):
    hsv = cv2.cvtColor(bgr, cv2.COLOR_BGR2HSV)
    lower_bound = np.array([hl,sl,vl],dtype=np.uint8)
    upper_bound = np.array([hh,sh,vh],dtype=np.uint8)
    return cv2.inRange(hsv, lower_bound,upper_bound)

img = cv2.imread("sample.jpg")
maskA=maskBuilder(img, 150,185, 40,220, 65,240) 
maskB=maskBuilder(img, 3,20, 50,180, 20,250)
layerA = cv2.bitwise_and(img, img, mask = maskA)
layerB = cv2.bitwise_and(img, img, mask = maskB)
contoursA = contours(layerA)[0]
contoursB = contours(layerA)[1]

print cntDistanceCompare(contoursA, contoursB)

As you can see from these images, the masking and thesholding works (shown for the first set of contours):

The cntDistanceCompare() function loops through each contour of set A and B, outputting average minimum distance between contours. Within this function, minDistance() calculates from the (x,y) points on each set of contours A and B a minimum pythagorean distance (using the distance formula).

The following error is thrown: Traceback (most recent call last): File "mindistance.py", line 46, in cntDistanceCompare(contoursA, contoursB) File "mindistance.py", line 26, in cntDistanceCompare minDist = minDistance(contourA,contourB) File "mindistance.py:, line 15, in minDistance for xB, yB in contourOther[0]: TypeError: 'numpy.uint8' object is not iterable

I suspect this problem arises from my lack of knowledge of how to reference the x,y coordinates of each contour vertex within the data structre given by cv2.findContours().

the maskBuilder function essentially blacks out all image content that does not fall into a specified color range, which in this case, are defined in relation to an HSV (hue saturation, value) colorspace. See my previous post: http://stackoverflow.com/questions/32238887/defining-color-range-for-histologic-image-mask-within-hsv-colorspace-python-op. I use it here to select groups of objects in the image based on color. — David Shaked, Sep 25 '15 at 14:07
By the way, the getContourCenters(contourData) function in the answer by @Jason addresses your need for the function that I suggested (here, for onlookers: http://stackoverflow.com/questions/32646551/calculate-minimum-distance-between-two-arbitrary-shape/32770382?noredirect=1#comment53405861_32770382) that finds geometric centers for your distance calculation. — David Shaked, Sep 25 '15 at 14:11
I'm aware that you're interested in implementing this solution in Java... Please share if you've identified a library for image analysis in that language. — David Shaked, Sep 25 '15 at 14:12
@DavidShaked minDistance function calculate the min distance based on the two contour data in simple way using two loop. Problem is that performance is going to slow for big contour data which I faced already. — Shiladittya Chakraborty, Sep 25 '15 at 14:15
Yes, this is why I expressed my sympathies with your problem on your post. I'm dealing with a very large data set and many objects per image (sometimes >20), so I understand the limitations of this approach. Two answers: 1) fastest: Use geometric centers to approximate the location of the blobs (fine as long as radii << real distance), as I suggested earlier 2) more accurate: approximate the shape of the blob by fitting a square, which reduces the number of vertices you'll need to loop through, while still taking into account blob size, somewhat. In other words, simplify your contour data. — David Shaked, Sep 25 '15 at 14:21
Let me know what library you're using in Java, and I'll do my best to find analogs to the functions I used here in python/openCV... — David Shaked, Sep 25 '15 at 14:27
I am using java with GWT HTML5 canvas to draw all the shape. In java I am not using any special library. I have all the points for contour shape after get the points then I am calculation minimum distance between this contours. — Shiladittya Chakraborty, Sep 25 '15 at 14:38
On the topic of optimization, this seems to be of interest to both of us if somebody has not yet suggested it to you: http://stackoverflow.com/questions/3700983/what-is-the-fastest-algorithm-to-calculate-the-minimum-distance-between-two-sets — David Shaked, Sep 25 '15 at 14:41
Apparently, the problem of comparison all vertices (x,y) defining two polygons is a native quadratic problem, meaning that the time required to compute grows quite quickly as the number of points n and m grow. I'm going to hold of diving in further for now, but lets turn our attention to the geometric center problem... Lets move back to your post :). — David Shaked, Sep 25 '15 at 14:45

Jason · Accepted Answer · 2015-09-25T14:42:25.773

I am using an older version of openCV where findContours only returns two values, but hopefully the important part of this code makes sense. I didn't test your functions, but I did show how to get the contour centers. You have to do some stuff with "moments."

import cv2
import numpy as np

def contours(layer):
    gray = cv2.cvtColor(layer, cv2.COLOR_BGR2GRAY)
    ret,binary = cv2.threshold(gray, 1,255,cv2.THRESH_BINARY) 
    contours, hierarchy = cv2.findContours(binary,cv2.RETR_TREE,cv2.CHAIN_APPROX_NONE)
    #drawn = cv2.drawContours(image,contours,-1,(150,150,150),3)
    return contours #, drawn

def minDistance(contour, contourOther):
    distanceMin = 99999999
    for xA, yA in contour[0]:
        for xB, yB in contourOther[0]:
            distance = ((xB-xA)**2+(yB-yA)**2)**(1/2) # distance formula
            if (distance < distanceMin):
                distanceMin = distance
    return distanceMin

def cntDistanceCompare(contoursA, contoursB):
    cumMinDistList = []
    for contourA in contoursA:
        indMinDistList = []
        for contourB in contoursB:
            minDist = minDistance(contourA,contourB)
            indMinDistList.append(minDist)
        cumMinDistList.append(indMinDistList)
    l = cumMinDistList  
    return sum(l)/len(l) #returns mean distance

def maskBuilder(bgr,hl,hh,sl,sh,vl,vh):
    hsv = cv2.cvtColor(bgr, cv2.COLOR_BGR2HSV)
    lower_bound = np.array([hl,sl,vl],dtype=np.uint8)
    upper_bound = np.array([hh,sh,vh],dtype=np.uint8)
    return cv2.inRange(hsv, lower_bound,upper_bound)

def getContourCenters(contourData):
    contourCoordinates = []
    for contour in contourData:
        moments = cv2.moments(contour)
        contourX = int(moments['m10'] / float(moments['m00']))
        contourY = int(moments['m01'] / float(moments['m00']))
        contourCoordinates += [[contourX, contourY]]
    return contourCoordinates

img = cv2.imread("sample.jpg")
maskA=maskBuilder(img, 150,185, 40,220, 65,240) 
maskB=maskBuilder(img, 3,20, 50,180, 20,250)
layerA = cv2.bitwise_and(img, img, mask = maskA)
layerB = cv2.bitwise_and(img, img, mask = maskB)
contoursA = contours(layerA)
contoursB = contours(layerB)

print getContourCenters(contoursA)
print getContourCenters(contoursB)

#print cntDistanceCompare(contoursA, contoursB)

Edit: I'm playing with your functions now and I fear I misread the question. Let me know and I'll delete my answer.

Great tentative solution. I suppose this should make the program run far faster than the comparison of very large number of points. The limitation here is that oddly shaped blobs would not be considered as I want them to be in my actual application (medical image analysis). Thank you for the help! — David Shaked, Sep 25 '15 at 03:22
Could you tell me how I might access the coordinates of a given contour? Something like contour[i][0] for xi and contour[i][1] for yi? — David Shaked, Sep 25 '15 at 03:23

OpenCV: Minimum distance between arbitrarily large sets of contours (Python)

1 Answers1

Linked