Detection of contours intersections

I have two contour images and I would like to find the contours intersection. So far I've succesfully used the logical and operation, unfortunately I've fallen into this case:

As you can see, the logical and operation is going to fail because there isn't any intersection. If the red contours is in image A, and blue contour is in image B, I would like a way to return the two red pixel indicated by the arrow. Does openCV provide some function to do that? In case there isn't, how would you solve this problem?

PS: the contours come from random shapes, they are NOT straight lines!

Thank you.

edit retag close merge delete

Sort by ยป oldest newest most voted

[EDIT] Other solution based on @Davide_sd's comment below:

If the contours are not straight lines, you might avoid the case you presented by a dilatation operation on one of the contours. Then, get the common points using the AND operation on the contour images and finally eliminate the points that are too close, which represent probably the same intersection.

(in the example you presented, you'll have two intersection points if you dilate one of the contours, so you have to eliminate one of those).

[Original answer] I keep this answer as it can be useful for others:

There is no OpenCV finction for this, but it's a simple geometry problem. If you write the equation of the line:

(x-x0)-m0(y-y0)=0


then the intersection point will be the (x,y) point that solves the equation of both lines:

(x-x0)-m0(y-y0)=0
(x-x1)-m1(y-y1)=0


If my calculations are correct (better recheck), then:

y=(x0-x1+y1m1-y0m0)/(m1-m0)
x=x0+m0(y-y0)


(just check that the lines aren't parallel: m0!=m1)

Now, the two lines intersect if y is between the two endpoints (y0a<y<y0b), and the resulting (x,y) point will give you the intersection coordinate.

You'll have to check the intersection between each pair of lines of the two contours, but as the equations are simple, this operation will still be much faster than any other method.

more

unfortunately the contours are not straitgh lines, they come from random shapes, so i can't use the line equations. :(

( 2016-09-28 17:03:52 -0500 )edit
1

top notch! thank you for your help :D

( 2016-09-29 03:48:53 -0500 )edit

To apply the "geometric solution", you need to know the points to write the equation of the line, this is not so easy.

You could use the hit-and-miss morphology to find a particular pattern...in this case the 3-point junctions.

Below is my implementation to achieve the following result (Src, Junctions and Final):

See http://homepages.inf.ed.ac.uk/rbf/HIP... for more details about hit-and-miss

In short, you have to define the right kernel for each pattern you want to detect. In OpenCV hit-and-miss (is available thanks to @LorenaGdL ) you have to use:

• 1 => white is required here
• -1 => black is required here
• 0 => doesn't matter

Than, catch all directions/orientation rotating the kernel

Here is the code:

    // This is your sample image (objects are black)
cv::Mat src = (cv::Mat_<UINT8>(7, 8) <<
0, 1, 1, 1, 1, 1, 0, 0,
1, 0, 1, 1, 1, 0, 1, 1,
1, 1, 0, 0, 0, 1, 1, 1,
1, 1, 1, 0, 0, 0, 1, 1,
1, 0, 0, 1, 1, 1, 0, 1,
0, 1, 1, 1, 1, 1, 0, 0,
0, 1, 1, 1, 1, 1, 1, 1);
void GetJunctions(const Mat &src, Mat &dst)
{
// the hit-and-miss kernels to locate 3-points junctions
// to be used in each directions
// NOTE: float type is needed due to limitation/bug in warpAffine with signed char
cv::Mat k1 = (cv::Mat_<float>(3, 3) <<
0,  1,  0,
0,  1,  0,
1,  0,  1);
cv::Mat k2 = (cv::Mat_<float>(3, 3) <<
1,  0,  0,
0,  1,  0,
1,  0,  1);
cv::Mat k3 = (cv::Mat_<float>(3, 3) <<
0, -1,  1,
1,  1, -1,
0,  1, 0);
// Some useful declarations
Mat tmp, rotMat;
Size ksize = k1.size();
Point center = Point(ksize.width / 2, ksize.height / 2);
// 90 degrees rotation matrix
rotMat = getRotationMatrix2D(center, 90, 1);
// dst accumulates all matches
dst = Mat::zeros(src.size(), CV_16UC1);
// Do hit & miss for all possible directions (0,90,180,270)
int op = MORPH_HITMISS;
for (int i = 0; i < 3; i++)
{
morphologyEx(src, tmp, op, Mat_<INT8>(k1), Point(-1, -1), 1, BORDER_CONSTANT, 0);
morphologyEx(src, tmp, op, Mat_<INT8>(k2), Point(-1, -1), 1, BORDER_CONSTANT, 0);
morphologyEx(src, tmp, op, Mat_<INT8>(k3), Point(-1, -1), 1, BORDER_CONSTANT, 0);
// Rotate the kernels (90deg)
warpAffine(k1, k1, rotMat, ksize);
warpAffine(k2, k2, rotMat, ksize);
warpAffine(k3, k3, rotMat, ksize);
}
// normalize the accumulator to 0..255
cv::normalize(dst, tmp, 0, 255, cv::NORM_MINMAX);
tmp.convertTo(dst, src.type());
}
int main()
{
src *= 255;
// Morphology logic is: white objects on black foreground
src = ~src;
// Get junctions
Mat junctionsScore, dst;
vector<Point> junctionsPoint;Point pt;
GetJunctions(src, junctionsScore);
// Draw markers where junction score is non zero
cvtColor(src, dst, CV_GRAY2BGR);
findNonZero(junctionsScore, junctionsPoint);
for (size_t i = 0; i < junctionsPoint.size(); i++)
{
pt = junctionsPoint[i];
char score = junctionsScore.at<uchar>(pt);
dst.at<Vec3b>(pt) = Vec3b(0 ...
more

wow, hit and miss is really powerful! Thanks @pklab to show me this solution!!!

( 2016-09-30 08:01:41 -0500 )edit

you are welcome :) consider that hit-and-miss requires skeleton images to get right result, btw drawContours should generate skeleton. If the answer works you might accept it ;)

( 2016-09-30 09:39:00 -0500 )edit

is it possible to mark two answers as both correct? truth is @kbarni answer nicely integrates with my current workflow.

( 2016-09-30 09:46:58 -0500 )edit

Don't worry about...it's fine as is. For your information accepting 2 answer is a feature request for this forum

( 2016-09-30 11:42:54 -0500 )edit

This is the Python code for @pklab answer, in case someone is in a hurry...

import numpy as np
import cv2

def getJunctions(src):
# the hit-and-miss kernels to locate 3-points junctions to be used in each directions
# NOTE: float type is needed due to limitation/bug in warpAffine with signed char
k1 = np.asarray([
0,  1,  0,
0,  1,  0,
1,  0,  1], dtype=float).reshape((3, 3))
k2 = np.asarray([
1,  0,  0,
0,  1,  0,
1,  0,  1], dtype=float).reshape((3, 3))
k3 = np.asarray([
0, -1,  1,
1,  1, -1,
0,  1, 0], dtype=float).reshape((3, 3))

# Some useful declarations
tmp = np.zeros_like(src)
ksize = k1.shape
center = (ksize[1] / 2, ksize[0] / 2) # INVERTIRE 0 E 1??????
# 90 degrees rotation matrix
rotMat = cv2.getRotationMatrix2D(center, 90, 1)
# dst accumulates all matches
dst = np.zeros(src.shape, dtype=np.uint8)

# Do hit & miss for all possible directions (0,90,180,270)
for i in range(4):
tmp = cv2.morphologyEx(src, cv2.MORPH_HITMISS, k1.astype(np.int8), tmp, (-1, -1), 1, cv2.BORDER_CONSTANT, 0)
tmp = cv2.morphologyEx(src, cv2.MORPH_HITMISS, k2.astype(np.int8), tmp, (-1, -1), 1, cv2.BORDER_CONSTANT, 0)
tmp = cv2.morphologyEx(src, cv2.MORPH_HITMISS, k3.astype(np.int8), tmp, (-1, -1), 1, cv2.BORDER_CONSTANT, 0)
# Rotate the kernels (90deg)
k1 = cv2.warpAffine(k1, rotMat, ksize)
k2 = cv2.warpAffine(k2, rotMat, ksize)
k3 = cv2.warpAffine(k3, rotMat, ksize)

return dst

# This is your sample image (objects are black)
src = np.asarray([0, 1, 1, 1, 1, 1, 0, 0,
1, 0, 1, 1, 1, 0, 1, 1,
1, 1, 0, 0, 0, 1, 1, 1,
1, 1, 1, 0, 0, 0, 1, 1,
1, 0, 0, 1, 1, 1, 0, 1,
0, 1, 1, 1, 1, 1, 0, 0,
0, 1, 1, 1, 1, 1, 1, 1], dtype=np.uint8).reshape((7,8))

src *= 255;
# Morphology logic is: white objects on black foreground
src = 255 - src;

# Get junctions
junctionsScore = getJunctions(src)

# Draw markers where junction score is non zero
dst = cv2.cvtColor(src, cv2.COLOR_GRAY2RGB)
# find the list of location of non-zero pixels
junctionsPoint = cv2.findNonZero(junctionsScore)

for pt in junctionsPoint:
pt = pt[0]
dst[pt[1], pt[0], :] = [0, 0, junctionsScore[pt[1], pt[0]]]

# show the result
winDst = "Dst"
winSrc = "Src"
winJunc = "Junctions"
cv2.namedWindow(winSrc, cv2.WINDOW_NORMAL | cv2.WINDOW_KEEPRATIO);
cv2.namedWindow(winJunc, cv2.WINDOW_NORMAL | cv2.WINDOW_KEEPRATIO);
cv2.namedWindow(winDst, cv2.WINDOW_NORMAL | cv2.WINDOW_KEEPRATIO);
scale = 24
cv2.resizeWindow(winSrc, scale*src.shape[1], scale*src.shape[0])
cv2.resizeWindow(winJunc, scale*src.shape[1], scale*src.shape[0])
cv2.resizeWindow(winDst, scale*src.shape[1], scale*src.shape[0])
cv2.imshow(winSrc, src)
cv2.imshow(winJunc, junctionsScore)
cv2.imshow(winDst, dst)
cv2.waitKey()

more

1

Nice to see python version ! +1 @Davide_sd

( 2016-09-30 09:40:00 -0500 )edit