How to do this image transformation?
I felt like coding it up in C++ for you rather than using the command line like for my other answer, so I have put it as a different answer. On top, it also actually implements the Douglas-Peucker algorithm and, for fun and good measure, animates it.
////////////////////////////////////////////////////////////////////////////////
// main.cpp
// Mark Setchell
// To find a blob in an image and generate line segments that describe it,
// Use ImageMagick Magick++ and Ramer-Douglas-Peucker algorithm.
// https://en.wikipedia.org/wiki/Ramer-Douglas-Peucker-algorithm
//
// function DouglasPeucker(PointList[], epsilon)
// // Find the point with the maximum distance
// dmax = 0
// index = 0
// end = length(PointList)
// for i = 2 to ( end - 1) {
// d = perpendicularDistance(PointList[i], Line(PointList[1], PointList[end]))
// if ( d > dmax ) {
// index = i
// dmax = d
// }
// }
// // If max distance is greater than epsilon, recursively simplify
// if ( dmax > epsilon ) {
// // Recursive call
// recResults1[] = DouglasPeucker(PointList[1...index], epsilon)
// recResults2[] = DouglasPeucker(PointList[index...end], epsilon)
// // Build the result list
// ResultList[] = {recResults1[1...length(recResults1)-1], recResults2[1...length(recResults2)]}
// } else {
// ResultList[] = {PointList[1], PointList[end]}
// }
// // Return the result
// return ResultList[]
// end
//
////////////////////////////////////////////////////////////////////////////////
#include <Magick++.h>
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <cassert>
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
using namespace Magick;
// Global debug image
Image DEBUG_IMAGE;
int DEBUG_NUM=0;
char DEBUG_NAME[64];
#define DEBUG(img) {sprintf(DEBUG_NAME,"debug-%04d.png",DEBUG_NUM++);img.write(DEBUG_NAME);}
// Point class
class Point {
private:
double px,py;
public:
// Constructor
Point(double x = 0.0, double y = 0.0) {
px = x;
py = y;
}
// Getters
double x() { return px; }
double y() { return py; }
};
// Line class
class Line {
private:
Point start,end;
public:
// Constructor
Line(Point a=Point(0,0), Point b=Point(0,0)){
start=a;
end=b;
}
// Getters
double startx() { return start.x(); }
double starty() { return start.y(); }
double endx() { return end.x(); }
double endy() { return end.y(); }
double DistanceTo(Point p){
double y2my1 = end.y() - start.y();
double x2mx1 = end.x() - start.x();
double numerator = fabs(y2my1*p.x() - x2mx1*p.y() + end.x()*start.y() - end.y()*start.x());
double denominator = sqrt(y2my1*y2my1 + x2mx1*x2mx1);
return numerator/denominator;
}
};
void DouglasPeucker(vector<Point>& PointList,int startindex,int endindex,double epsilon,vector<Line>& Results){
// Find the point with the maximum distance
double d,dmax=0;
int i,index;
Line line(PointList[startindex],PointList[endindex]);
for(i=startindex+1;i<endindex;i++){
d=line.DistanceTo(PointList[i]) ;
if(d>dmax){
index=i;
dmax=d;
}
}
// If max distance is greater than epsilon, recursively simplify
if ( dmax > epsilon ) {
// Recursive call to do left and then right parts
DouglasPeucker(PointList,startindex,index,epsilon,Results);
DouglasPeucker(PointList,index,endindex,epsilon,Results);
} else {
Results.push_back(line);
// Rest of else statement is just generating debug image
std::list<Magick::Drawable> drawList;
drawList.push_back(DrawableStrokeColor("blue"));
drawList.push_back(DrawableStrokeWidth(1));
drawList.push_back(DrawableLine(line.startx(),line.starty(),line.endx(),line.endy()));
DEBUG_IMAGE.draw(drawList);
DEBUG(DEBUG_IMAGE);
}
}
int main(int argc,char **argv)
{
InitializeMagick(*argv);
// Create some colours
Color black = Color("rgb(0,0,0)");
Color white = Color("rgb(65535,65535,65535)");
Color red = Color("rgb(65535,0,0)");
Color green = Color("rgb(0,65535,0)");
Color blue = Color("rgb(0,0,65535)");
// Create a fuzz factor scaling
assert(QuantumRange==65535);
const double fuzzscale = QuantumRange/100;
// Load wave image
Image image("wave.jpg");
int w = image.columns();
int h = image.rows();
cout << "Dimensions: " << w << "x" << h << endl;
// Copy for debug purposes
DEBUG_IMAGE=image;
// Fill top-left greyish area of image with green
image.colorFuzz(50*fuzzscale);
image.opaque(white,green);
DEBUG(image);
// Fill bottom-right blackish area of image with blue
image.colorFuzz(20*fuzzscale);
image.opaque(black,blue);
DEBUG(image);
// Fill rest of image with red
image.colorFuzz(81*fuzzscale);
image.opaque(red,red);
DEBUG(image);
// Median filter to remove jaggies
image.medianFilter(25);
DEBUG(image);
// Find red-green edge by cloning, making blue red, then looking for edges
std::vector<Point> RGline;
Image RGimage=image;
RGimage.opaque(blue,red);
DEBUG(RGimage);
RGimage.type(GrayscaleType);
DEBUG(RGimage);
RGimage.normalize();
DEBUG(RGimage);
RGimage.edge(1);
DEBUG(RGimage);
// Now pass over the image collecting white pixels (from red-green edge)
// Ignore a single row at top & bottom and a single column at left & right edges
// Get a "pixel cache" for the entire image
PixelPacket *pixels = RGimage.getPixels(0, 0, w, h);
int x,y;
for(x=1; x<w-2; x++){
for(y=1; y<h-2; y++){
Color color = pixels[w * y + x];
// Collect white "edge" pixels
if(color.redQuantum()==65535){
RGline.push_back(Point(x,y));
}
}
}
cout << "RGline has " << RGline.size() << " elements" << endl;
// Results - a vector of line segments
std::vector<Line> Results;
// epsilon = Max allowable deviation from straight line in pixels
// Make epsilon smaller for more, shorter, more accurate lines
// Make epsilon larger for fewer, more approximate lines
double epsilon=18;
DouglasPeucker(RGline,0,RGline.size()-1,epsilon,Results);
int lines1=Results.size();
cout << "Upper boundary mapped to " << lines1 << " line segments (epsilon=" << epsilon << ")" << endl;
// Find red-blue edge by cloning, making green red, then looking for edges
std::vector<Point> RBline;
Image RBimage=image;
RBimage.opaque(green,red);
DEBUG(RBimage);
RBimage.type(GrayscaleType);
DEBUG(RBimage);
RBimage.normalize();
DEBUG(RBimage);
RBimage.edge(1);
DEBUG(RBimage);
// Now pass over the image collecting white pixels (from red-green edge)
// Ignore a single row at top & bottom and a single column at left & right edges
// Get a "pixel cache" for the entire image
pixels = RBimage.getPixels(0, 0, w, h);
for(x=1; x<w-2; x++){
for(y=1; y<h-2; y++){
Color color = pixels[w * y + x];
// Collect white "edge" pixels
if(color.redQuantum()==65535){
RBline.push_back(Point(x,y));
}
}
}
cout << "RBline has " << RBline.size() << " elements" << endl;
DouglasPeucker(RBline,0,RBline.size()-1,epsilon,Results);
int lines2=Results.size() - lines1;
cout << "Lower boundary mapped to " << lines2 << " line segments (epsilon=" << epsilon << ")" << endl;
}
My Makefile looks like this:
main: main.cpp
clang++ -std=gnu++11 -Wall -pedantic main.cpp -o main $$(Magick++-config --cppflags --cxxflags --ldflags --libs)
Not really a complete answer, but maybe enough to get you started, or enough to make someone else comment and add in some more ideas - and no-one said answers had to be complete anyway.
I used ImageMagick just from the command line to segment your image into three - the blurred grey-red is a bit of a pain if you try and do a simple colour-reduction to three colours. ImageMagick is installed on most Linux distros and is available for OSX and Windows.
First, I want to make all the grey in the top-left of the image one shade of yellow. Then I want to make all the black in the bottom-right of the image another, slightly different shade of yellow. Then I want to make everything that is not remotely yellow into red. Each sentence above corresponds to one line of code below:
convert wave.jpg \
-fuzz 50% -fill "rgb(255,255,0)" -opaque white \
-fuzz 20% -fill "rgb(250,250,0)" -opaque black \
-fuzz 10% -fill red +opaque yellow result.png
Now I can change the two temporary shades of yellow back into white and black:
convert result.png -fuzz 0 \
-fill white -opaque "rgb(255,255,0)" \
-fill black -opaque "rgb(250,250,0)" result2.png
And then I can smooth the jaggies with a median filter:
convert result2.png -median 25x25 result3.png
I can detect the edges now, using -edge:
convert result3.png -edge 1 result4.png
Now you see how it works, you can do all that in one simple command:
convert wave.jpg \
-fuzz 50% -fill "rgb(255,255,0)" -opaque white \
-fuzz 20% -fill "rgb(250,250,0)" -opaque black \
-fuzz 10% -fill red +opaque yellow \
-fuzz 0 -fill white -opaque "rgb(255,255,0)" \
-fill black -opaque "rgb(250,250,0)" -median 25x25 -edge 1 result.png
Now, you can find all the points where a red pixel touches a white pixel - I would suggest you do that in Magick++ (the C++ binding of ImageMagick - though there are Ruby and Python and PHP bindings if you prefer) and put those points in a STL list and apply the Ramer–Douglas–Peucker algorithm to get line segments.
Then do likewise for all points where a red pixel touches a black pixel to get the line segments on the lower side.