Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

answered 2016-09-09 07:03:08 -0600

pklab gravatar image

I would suggest to do better preprocessing because of non uniform background and to avoid blur because thin arcs can disappear. When you have a good mask for your draw you can use massive morphology operation to isolate nodes and arcs Finally you have to design a logic to build the chart connections.

Here is my implementation

int Main_DiagramAnalyzer()
{
    Mat src, bw;
    src = imread("../img/diagram-x5.jpg");

==PREPROCESSING==

Option1: Remove non uniform background/illumination. You can achieve this using the wonderful quadratic background removal by @LBerger. Than get a mask of the draw using a simple threshold

#if 1
    Mat srcGray, dstGray;
    cvtColor(src, srcGray, CV_BGR2GRAY);
    BrightnessAndContrast::BackgroundRemoveQuadratic(srcGray, dstGray);
    threshold(dstGray, bw, 100, 255, THRESH_OTSU);

Quadratic result Quadratic result threshold image description

OR Option2: Get the HSV planes and threshold high values in S (>=95 percentile) to get a mask of the draw. You can achieve this using clipHistPercent=5 with BrightnessAndContrastAuto than get a binary mask looking at very high values in saturation

#else
    Mat src_hsv, saturation;
    vector<cv::Mat> hsv_planes;
    cvtColor(src, src_hsv, CV_BGR2HSV);
    cv::split(src_hsv, hsv_planes);
    saturation = hsv_planes[1];
    bw = saturation > 70;
    BrightnessAndContrastAuto(saturation, saturation, 5);
    bw = saturation >= 254;
#endif

Saturation result (look draw values) BrightnessAndContrastAuto threshold image description

fill circular structures using small circle

int nodeSize = 15; //avg node diameter in px
Morph(bw, bw, MORPH_CLOSE, MORPH_ELLIPSE, cvRound(nodeSize / 5));
imshow("Preprocessing", bw);

image description

GET MASK OF NODES: remove boundary structures smaller than avgNodeSize. Should remove the arcs

cv::Mat nodesMask;
Morph(bw, nodesMask, MORPH_OPEN, MORPH_ELLIPSE, cvRound(nodeSize / 5));
imshow("Nodes-Mask", nodesMask);

Node Mask Node Mask

GET MASK OF ARCS: dilate nodes a bit (ensure node vs arcs separation) than subtract them from the global mask

cv::Mat arcs, nodesLarger;
Morph(nodesMask, nodesLarger, MORPH_DILATE, MORPH_ELLIPSE, 1);
arcs = bw - nodesLarger;
imshow("Arcs-Mask", arcs);

Arcs Mask Arcs Mask

GET INTERSECTIONS: ensure node vs arcs intersection doubling size of nodes than get a mask of common pixels

cv::Mat intersections;
Morph(nodesLarger, nodesLarger, MORPH_DILATE, MORPH_ELLIPSE, nodeSize);
intersections = nodesLarger & arcs;

GET CONTOURS OF ELEMENTS 

vector<vector<Point> > nodesContours, arcsContours, intesectsContours;
findContours(nodesLarger, nodesContours, CV_RETR_EXTERNAL, CHAIN_APPROX_SIMPLE);
findContours(arcs, arcsContours, CV_RETR_EXTERNAL, CHAIN_APPROX_SIMPLE);
findContours(intersections, intesectsContours, CV_RETR_EXTERNAL, CHAIN_APPROX_SIMPLE);
vector<Point> nodesCenter(nodesContours.size(), Point(-1, -1));
vector<double> nodesArea(nodesContours.size(), -1);
vector<double> arcsLenght(arcsContours.size(), -1);

DRAW ENUMERATED CONTOURS and get center of nodes 

Moments m;
Point center;
Scalar cl = Scalar(0, 0, 255);
double val,minvalue = nodeSize/3;
for (size_t i = 0; i < nodesContours.size(); i++)
{
    val = contourArea(nodesContours[i]);
    if (val < minvalue) continue; //skip if it's small
    nodesArea[i] = val;
    m = moments(nodesContours[i], true);
    //if (m.m00 == 0) continue;
    center = Point(m.m10 / m.m00, m.m01 / m.m00);
    nodesCenter[i] = center;
    drawMarker(src, center, cl, MARKER_TILTED_CROSS, 5);
    putText(src, "N" + to_string(i), center, FONT_HERSHEY_PLAIN, 1, cl);
}
cl = Scalar(0, 255, 0);
minvalue = nodeSize/5;
for (size_t i = 0; i < arcsContours.size(); i++)
{
    val = arcLength(arcsContours[i], false); 
    if (val < minvalue) continue; //skip if it's small
    arcsLenght[i] = val;
    center = (arcsContours[i][0] + arcsContours[i][arcsContours[i].size() - 1]) / 2;
    drawContours(src, arcsContours, i, cl);
    putText(src, "A" + to_string(i), center, FONT_HERSHEY_PLAIN, 1, cl);
}

BUILD THE GRAPH: Use of common pixels to detect arc vs node connection. For each common pixels search related arc and node and build a vectors of connected nodes. THIS IS NOT OPTIMAL TECHNIQUE BUT IT WORKS FOR EXAMPLE PURPOSE.

vector<vector<int>> connections(arcsContours.size());
for (size_t c = 0; c < intesectsContours.size(); c++)
{
    int nodeIdx = -1;
    int archIdx = -1;
    for (size_t p = 0; p < intesectsContours[c].size(); c++)
    {
        Point pt = intesectsContours[c][p];

        for (size_t n = 0; n < nodesContours.size() && nodeIdx <0; n++)
        {
            if (nodesArea[n] < 0) continue; //skip if it's small
            if (pointPolygonTest(nodesContours[n], pt, false) >= 0)
                nodeIdx = n;
        } //for nodesContours
        for (size_t a = 0; a < arcsContours.size() && archIdx < 0; a++)
        {
            if (pointPolygonTest(arcsContours[a], pt, false) >= 0)
                archIdx = a;
        } //for arcsContours
        if ((nodeIdx >= 0) && (archIdx >= 0))
        {
            connections[archIdx].push_back(nodeIdx);
            break;
        } // if
    } // for intesectsContours[c]
} // for intesectsContours

PRINT OUT THE RESULT as Graphviz chart

cout << "graph G{ " << endl;
for (size_t i = 0; i < nodesContours.size(); i++)
{
    if (nodesArea[i] < 0 ) continue; //skip if it's small
    cout << "N"<<i << " ";
}

cout << endl;
for (size_t i = 0; i < connections.size(); i++)
{
    if (connections[i].size()>1)
    {
        //cout << "\nArc " << i << " connect nodes :";
        for (size_t j = 0; j < connections[i].size() - 1; j++)
        {
            int from = connections[i][j];
            int to = connections[i][j + 1];
            if (nodesCenter[from].y > nodesCenter[to].y)
            {
                int  tmp = from;
                from = to;
                to = tmp;
            }
            cout << "\tN"<<from<<" -- "<< "N"<<to << endl;
        }
    }
}
cout << "}";

imshow("SRC", src);
cv::waitKey(0);
return 0;
}

OUTPUT 

graph G{ 
    N0 N1 N2 N3 N4 
    N1 -- N0
    N2 -- N0
    N3 -- N2
    N3 -- N1
    N4 -- N3
}

Enumerating: image description Layout by Graphviz/dot image description

I would suggest to do better preprocessing because of non uniform background and to avoid blur because thin arcs can disappear. When you have a good mask for your draw drawing you can use massive morphology operation to isolate nodes and arcs Finally you have to design a logic to build the chart connections.

edit: small changes in descriptions

Below is my DiagramAnalyzer to convert your image into a Graphviz/dot chart. Here is my implementationthe result

graph G{ 
    N0 N1 N2 N3 N4 
    N1 -- N0
    N2 -- N0
    N3 -- N2
    N3 -- N1
    N4 -- N3
}

Enumerating: image description Layout by Graphviz/dot image description

int Main_DiagramAnalyzer()
DiagramAnalyzer()
{
    Mat src, bw;
    src = imread("../img/diagram-x5.jpg");

==PREPROCESSING==

Option1: Remove non uniform background/illumination. You can achieve this using the wonderful quadratic background removal by @LBerger. Than get a mask of the draw drawing using a simple threshold

#if 1
    Mat srcGray, dstGray;
    cvtColor(src, srcGray, CV_BGR2GRAY);
    BrightnessAndContrast::BackgroundRemoveQuadratic(srcGray, dstGray);
    threshold(dstGray, bw, 100, 255, THRESH_OTSU);

Quadratic result Quadratic result threshold image description

OR Option2: Get the HSV planes and threshold high values in S (>=95 percentile) to get a mask of the draw. drawing. You can achieve this using clipHistPercent=5 with BrightnessAndContrastAuto than get a binary mask looking at very high values in saturation

#else
    Mat src_hsv, saturation;
    vector<cv::Mat> hsv_planes;
    cvtColor(src, src_hsv, CV_BGR2HSV);
    cv::split(src_hsv, hsv_planes);
    saturation = hsv_planes[1];
    bw = saturation > 70;
    BrightnessAndContrastAuto(saturation, saturation, 5);
    bw = saturation >= 254;
#endif

Saturation result (look draw values) at values of drawing) BrightnessAndContrastAuto threshold image description

fill circular structures using small circle

int nodeSize = 15; //avg node diameter in px
Morph(bw, bw, MORPH_CLOSE, MORPH_ELLIPSE, cvRound(nodeSize / 5));
imshow("Preprocessing", bw);

image description Preprocessing (result of quadratic)

GET MASK OF NODES: remove boundary structures smaller than avgNodeSize. nodeSize . Should remove the arcs

cv::Mat nodesMask;
Morph(bw, nodesMask, MORPH_OPEN, MORPH_ELLIPSE, cvRound(nodeSize / 5));
imshow("Nodes-Mask", nodesMask);

Node Mask Node Mask

GET MASK OF ARCS: dilate nodes a bit (ensure node vs arcs separation) than subtract them from the global mask

cv::Mat arcs, nodesLarger;
Morph(nodesMask, nodesLarger, MORPH_DILATE, MORPH_ELLIPSE, 1);
arcs = bw - nodesLarger;
imshow("Arcs-Mask", arcs);

Arcs Mask Arcs Mask

GET INTERSECTIONS: ensure node vs arcs intersection doubling size of nodes than get a mask of common shared pixels

cv::Mat intersections;
Morph(nodesLarger, nodesLarger, MORPH_DILATE, MORPH_ELLIPSE, nodeSize);
intersections = nodesLarger & arcs;

GET CONTOURS OF ELEMENTS 

vector<vector<Point> > nodesContours, arcsContours, intesectsContours;
findContours(nodesLarger, nodesContours, CV_RETR_EXTERNAL, CHAIN_APPROX_SIMPLE);
findContours(arcs, arcsContours, CV_RETR_EXTERNAL, CHAIN_APPROX_SIMPLE);
findContours(intersections, intesectsContours, CV_RETR_EXTERNAL, CHAIN_APPROX_SIMPLE);
vector<Point> nodesCenter(nodesContours.size(), Point(-1, -1));
vector<double> nodesArea(nodesContours.size(), -1);
vector<double> arcsLenght(arcsContours.size(), -1);

DRAW ENUMERATED CONTOURS and get center of nodes 

Moments m;
Point center;
Scalar cl = Scalar(0, 0, 255);
double val,minvalue = nodeSize/3;
for (size_t i = 0; i < nodesContours.size(); i++)
{
    val = contourArea(nodesContours[i]);
    if (val < minvalue) continue; //skip if it's small
    nodesArea[i] = val;
    m = moments(nodesContours[i], true);
    //if (m.m00 == 0) continue;
    center = Point(m.m10 / m.m00, m.m01 / m.m00);
    nodesCenter[i] = center;
    drawMarker(src, center, cl, MARKER_TILTED_CROSS, 5);
    putText(src, "N" + to_string(i), center, FONT_HERSHEY_PLAIN, 1, cl);
}
cl = Scalar(0, 255, 0);
minvalue = nodeSize/5;
for (size_t i = 0; i < arcsContours.size(); i++)
{
    val = arcLength(arcsContours[i], false); 
    if (val < minvalue) continue; //skip if it's small
    arcsLenght[i] = val;
    center = (arcsContours[i][0] + arcsContours[i][arcsContours[i].size() - 1]) / 2;
    drawContours(src, arcsContours, i, cl);
    putText(src, "A" + to_string(i), center, FONT_HERSHEY_PLAIN, 1, cl);
}

BUILD THE GRAPH: Use of common shared pixels to detect arc vs node connection. For each common shared pixels search related arc and node and build a vectors of connected nodes. THIS IS NOT OPTIMAL TECHNIQUE BUT IT WORKS FOR EXAMPLE PURPOSE.

vector<vector<int>> connections(arcsContours.size());
for (size_t c = 0; c < intesectsContours.size(); c++)
{
    int nodeIdx = -1;
    int archIdx = -1;
    for (size_t p = 0; p < intesectsContours[c].size(); c++)
    {
        Point pt = intesectsContours[c][p];

        for (size_t n = 0; n < nodesContours.size() && nodeIdx <0; n++)
        {
            if (nodesArea[n] < 0) continue; //skip if it's small
            if (pointPolygonTest(nodesContours[n], pt, false) >= 0)
                nodeIdx = n;
        } //for nodesContours
        for (size_t a = 0; a < arcsContours.size() && archIdx < 0; a++)
        {
            if (pointPolygonTest(arcsContours[a], pt, false) >= 0)
                archIdx = a;
        } //for arcsContours
        if ((nodeIdx >= 0) && (archIdx >= 0))
        {
            connections[archIdx].push_back(nodeIdx);
            break;
        } // if
    } // for intesectsContours[c]
} // for intesectsContours

PRINT OUT THE RESULT as Graphviz chart

cout << "graph G{ " << endl;
for (size_t i = 0; i < nodesContours.size(); i++)
{
    if (nodesArea[i] < 0 ) continue; //skip if it's small
    cout << "N"<<i << " ";
}

cout << endl;
for (size_t i = 0; i < connections.size(); i++)
{
    if (connections[i].size()>1)
    {
        //cout << "\nArc " << i << " connect nodes :";
        for (size_t j = 0; j < connections[i].size() - 1; j++)
        {
            int from = connections[i][j];
            int to = connections[i][j + 1];
            if (nodesCenter[from].y > nodesCenter[to].y)
            {
                int  tmp = from;
                from = to;
                to = tmp;
            }
            cout << "\tN"<<from<<" -- "<< "N"<<to << endl;
        }
    }
}
cout << "}";

imshow("SRC", src);
cv::waitKey(0);
return 0;
}

OUTPUT 

graph G{ 
    N0 N1 N2 N3 N4 
    N1 -- N0
    N2 -- N0
    N3 -- N2
    N3 -- N1
    N4 -- N3

void Morph(const cv::Mat &src, cv::Mat &dst, int operation = cv::MORPH_OPEN, int kernel_type = cv::MORPH_RECT, int size = 1)
{
    cv::Point anchor = cv::Point(size, size);
    cv::Mat element = getStructuringElement(kernel_type, cv::Size(2 * size + 1, 2 * size + 1), anchor);
    morphologyEx(src, dst, operation, element, anchor);
}

Enumerating: image description Layout by Graphviz/dot image description

I would suggest to do better preprocessing because of non uniform background and to avoid blur because thin arcs can disappear. When you have a good mask for your drawing you can use massive morphology operation to isolate nodes and arcs Finally you have to design a logic to build the chart connections.

edit: small changes in descriptions

Below is my DiagramAnalyzer to convert your image into a Graphviz/dot chart. Here is the result

graph G{ 
    N0 N1 N2 N3 N4 
    N1 -- N0
    N2 -- N0
    N3 -- N2
    N3 -- N1
    N4 -- N3
}

Enumerating: image description Layout by Graphviz/dot image description

int DiagramAnalyzer()
{
    Mat src, bw;
    src = imread("../img/diagram-x5.jpg");

==PREPROCESSING==

Option1: Remove non uniform background/illumination. You can achieve this using the wonderful quadratic background removal by @LBerger. Than get a mask of the drawing using a simple threshold

#if 1
    Mat srcGray, dstGray;
    cvtColor(src, srcGray, CV_BGR2GRAY);
    BrightnessAndContrast::BackgroundRemoveQuadratic(srcGray, BackgroundRemoveQuadratic(srcGray, dstGray);
    threshold(dstGray, bw, 100, 255, THRESH_OTSU);

Quadratic result Quadratic result threshold image description

OR Option2: Get the HSV planes and threshold high values in S (>=95 percentile) to get a mask of the drawing. You can achieve this using clipHistPercent=5 with BrightnessAndContrastAuto than get a binary mask looking at very high values in saturation

#else
    Mat src_hsv, saturation;
    vector<cv::Mat> hsv_planes;
    cvtColor(src, src_hsv, CV_BGR2HSV);
    cv::split(src_hsv, hsv_planes);
    saturation = hsv_planes[1];
    BrightnessAndContrastAuto(saturation, saturation, 5);
    bw = saturation >= 254;
#endif

Saturation result (look at values of drawing) BrightnessAndContrastAuto threshold image description

fill circular structures using small circle

int nodeSize = 15; //avg node diameter in px
Morph(bw, bw, MORPH_CLOSE, MORPH_ELLIPSE, cvRound(nodeSize / 5));
imshow("Preprocessing", bw);

image description Preprocessing (result of quadratic)

GET MASK OF NODES: remove boundary structures smaller than nodeSize . Should remove the arcs

cv::Mat nodesMask;
Morph(bw, nodesMask, MORPH_OPEN, MORPH_ELLIPSE, cvRound(nodeSize / 5));
imshow("Nodes-Mask", nodesMask);

Node Mask Node Mask

GET MASK OF ARCS: dilate nodes a bit (ensure node vs arcs separation) than subtract them from the global mask

cv::Mat arcs, nodesLarger;
Morph(nodesMask, nodesLarger, MORPH_DILATE, MORPH_ELLIPSE, 1);
arcs = bw - nodesLarger;
imshow("Arcs-Mask", arcs);

Arcs Mask Arcs Mask

GET INTERSECTIONS: ensure node vs arcs intersection doubling size of nodes than get a mask of shared pixels

cv::Mat intersections;
Morph(nodesLarger, nodesLarger, MORPH_DILATE, MORPH_ELLIPSE, nodeSize);
intersections = nodesLarger & arcs;

GET CONTOURS OF ELEMENTS 

vector<vector<Point> > nodesContours, arcsContours, intesectsContours;
findContours(nodesLarger, nodesContours, CV_RETR_EXTERNAL, CHAIN_APPROX_SIMPLE);
findContours(arcs, arcsContours, CV_RETR_EXTERNAL, CHAIN_APPROX_SIMPLE);
findContours(intersections, intesectsContours, CV_RETR_EXTERNAL, CHAIN_APPROX_SIMPLE);
vector<Point> nodesCenter(nodesContours.size(), Point(-1, -1));
vector<double> nodesArea(nodesContours.size(), -1);
vector<double> arcsLenght(arcsContours.size(), -1);

DRAW ENUMERATED CONTOURS and get center of nodes 

Moments m;
Point center;
Scalar cl = Scalar(0, 0, 255);
double val,minvalue = nodeSize/3;
for (size_t i = 0; i < nodesContours.size(); i++)
{
    val = contourArea(nodesContours[i]);
    if (val < minvalue) continue; //skip if it's small
    nodesArea[i] = val;
    m = moments(nodesContours[i], true);
    //if (m.m00 == 0) continue;
    center = Point(m.m10 / m.m00, m.m01 / m.m00);
    nodesCenter[i] = center;
    drawMarker(src, center, cl, MARKER_TILTED_CROSS, 5);
    putText(src, "N" + to_string(i), center, FONT_HERSHEY_PLAIN, 1, cl);
}
cl = Scalar(0, 255, 0);
minvalue = nodeSize/5;
for (size_t i = 0; i < arcsContours.size(); i++)
{
    val = arcLength(arcsContours[i], false); 
    if (val < minvalue) continue; //skip if it's small
    arcsLenght[i] = val;
    center = (arcsContours[i][0] + arcsContours[i][arcsContours[i].size() - 1]) / 2;
    drawContours(src, arcsContours, i, cl);
    putText(src, "A" + to_string(i), center, FONT_HERSHEY_PLAIN, 1, cl);
}

BUILD THE GRAPH: Use shared pixels to detect arc vs node connection. For each shared pixels search related arc and node and build a vectors of connected nodes. THIS IS NOT OPTIMAL TECHNIQUE BUT IT WORKS FOR EXAMPLE PURPOSE.

vector<vector<int>> connections(arcsContours.size());
for (size_t c = 0; c < intesectsContours.size(); c++)
{
    int nodeIdx = -1;
    int archIdx = -1;
    for (size_t p = 0; p < intesectsContours[c].size(); c++)
    {
        Point pt = intesectsContours[c][p];

        for (size_t n = 0; n < nodesContours.size() && nodeIdx <0; n++)
        {
            if (nodesArea[n] < 0) continue; //skip if it's small
            if (pointPolygonTest(nodesContours[n], pt, false) >= 0)
                nodeIdx = n;
        } //for nodesContours
        for (size_t a = 0; a < arcsContours.size() && archIdx < 0; a++)
        {
            if (pointPolygonTest(arcsContours[a], pt, false) >= 0)
                archIdx = a;
        } //for arcsContours
        if ((nodeIdx >= 0) && (archIdx >= 0))
        {
            connections[archIdx].push_back(nodeIdx);
            break;
        } // if
    } // for intesectsContours[c]
} // for intesectsContours

PRINT OUT THE RESULT as Graphviz chart

cout << "graph G{ " << endl;
for (size_t i = 0; i < nodesContours.size(); i++)
{
    if (nodesArea[i] < 0 ) continue; //skip if it's small
    cout << "N"<<i << " ";
}

cout << endl;
for (size_t i = 0; i < connections.size(); i++)
{
    if (connections[i].size()>1)
    {
        //cout << "\nArc " << i << " connect nodes :";
        for (size_t j = 0; j < connections[i].size() - 1; j++)
        {
            int from = connections[i][j];
            int to = connections[i][j + 1];
            if (nodesCenter[from].y > nodesCenter[to].y)
            {
                int  tmp = from;
                from = to;
                to = tmp;
            }
            cout << "\tN"<<from<<" -- "<< "N"<<to << endl;
        }
    }
}
cout << "}";

imshow("SRC", src);
cv::waitKey(0);
return 0;
}

void Morph(const cv::Mat &src, cv::Mat &dst, int operation = cv::MORPH_OPEN, int kernel_type = cv::MORPH_RECT, int size = 1)
{
    cv::Point anchor = cv::Point(size, size);
    cv::Mat element = getStructuringElement(kernel_type, cv::Size(2 * size + 1, 2 * size + 1), anchor);
    morphologyEx(src, dst, operation, element, anchor);
}
Copyright OpenCV foundation, 2012-2018. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
about | faq | help | privacy policy | terms of service
Powered by Askbot version 0.10.2