Ask Your Question
3

Detection of contours intersections

asked 2016-09-28 07:15:34 -0500

Davide_sd gravatar image

updated 2017-08-25 14:00:57 -0500

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:

image description

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 flag offensive close merge delete

3 answers

Sort by ยป oldest newest most voted
3

answered 2016-09-28 08:34:23 -0500

kbarni gravatar image

updated 2016-09-29 03:25:36 -0500

[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.

edit flag offensive delete link more

Comments

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

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

top notch! thank you for your help :D

Davide_sd gravatar imageDavide_sd ( 2016-09-29 03:48:53 -0500 )edit
4

answered 2016-09-29 05:41:50 -0500

pklab gravatar image

updated 2016-09-29 13:52:48 -0500

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):

Source Junctions 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);
        add(dst, tmp, dst, noArray(), dst.type());
        morphologyEx(src, tmp, op, Mat_<INT8>(k2), Point(-1, -1), 1, BORDER_CONSTANT, 0);
        add(dst, tmp, dst, noArray(), dst.type());
        morphologyEx(src, tmp, op, Mat_<INT8>(k3), Point(-1, -1), 1, BORDER_CONSTANT, 0);
        add(dst, tmp, dst, noArray(), dst.type());
        // 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)
edit flag offensive delete link more

Comments

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

Davide_sd gravatar imageDavide_sd ( 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 ;)

pklab gravatar imagepklab ( 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.

Davide_sd gravatar imageDavide_sd ( 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

pklab gravatar imagepklab ( 2016-09-30 11:42:54 -0500 )edit
3

answered 2016-09-30 08:05:36 -0500

Davide_sd gravatar image

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)     
        dst = cv2.add(dst, tmp)
        tmp = cv2.morphologyEx(src, cv2.MORPH_HITMISS, k2.astype(np.int8), tmp, (-1, -1), 1, cv2.BORDER_CONSTANT, 0)
        dst = cv2.add(dst, tmp)
        tmp = cv2.morphologyEx(src, cv2.MORPH_HITMISS, k3.astype(np.int8), tmp, (-1, -1), 1, cv2.BORDER_CONSTANT, 0)
        dst = cv2.add(dst, tmp)
        # 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()
edit flag offensive delete link more

Comments

1

Nice to see python version ! +1 @Davide_sd

pklab gravatar imagepklab ( 2016-09-30 09:40:00 -0500 )edit
Login/Signup to Answer

Question Tools

1 follower

Stats

Asked: 2016-09-28 07:15:34 -0500

Seen: 2,355 times

Last updated: Sep 30 '16