MATLAB Central Newsreader - Implementing splines in a microcontroller

Implementing splines in a microcontroller

Tom E — Wed, 18 Nov 2009 20:13:20 -0500

Hi folks,

I have a reasonably simple task to do for uni:
Take an image
Extract the edges
Display this using a microcontroller.

Because the display method is as a vector, I have chosen to interpret the edges as splines.

So far I have managed to extract the edges and convert to a series of splines.

Now i've come to the problem of how to implement the resultant data in a microcontroller. I don't really understand how splines are stored in matlab. As far as I understand, splines are a series of curves, all joined together (Bezier curves, paths, however you'd like to call them).

So given a spline in ppform, or B-form, how do I know what the equations are for each of the curves?

I'm also open to other suggestions for how to solve my problem. If splines aren't the way to go, no worries. The only problem is that my supervisor is convinced I should implement the images as a vector.

Thanks for any help you can give!
Tom

Re: Implementing splines in a microcontroller

Bruno Luong — Wed, 18 Nov 2009 21:14:20 -0500

"Tom E" <tom.elliot@students.fhv.at> wrote in message <he1kh0$26s$1@fred.mathworks.com>...
> Hi folks,
>
> I have a reasonably simple task to do for uni:
> Take an image
> Extract the edges
> Display this using a microcontroller.
>
> Because the display method is as a vector, I have chosen to interpret the edges as splines.
>
> So far I have managed to extract the edges and convert to a series of splines.
>
> Now i've come to the problem of how to implement the resultant data in a microcontroller. I don't really understand how splines are stored in matlab. As far as I understand, splines are a series of curves, all joined together (Bezier curves, paths, however you'd like to call them).
>
> So given a spline in ppform, or B-form, how do I know what the equations are for each of the curves?

Spline is a polynomial on each subinterval (piecewise polynomials). On each interval, the polynomial is computed with respect to the relative abscissa to its left bound (leftbound := 0). The coefficients of the polynomials are ranged in each columns of the field COEFS (highest to lowest order - same as used by polyval/polyfit). Consecutive subintervals are separated by the subdivision of the entire interval stored in the field BREAKS.

Bruno

Re: Implementing splines in a microcontroller

Tom E — Sun, 22 Nov 2009 16:38:03 -0500

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <he1o3c$mqq$1@fred.mathworks.com>...
> "Tom E" <tom.elliot@students.fhv.at> wrote in message <he1kh0$26s$1@fred.mathworks.com>...
> > Hi folks,
> >
> > I have a reasonably simple task to do for uni:
> > Take an image
> > Extract the edges
> > Display this using a microcontroller.
> >
> > Because the display method is as a vector, I have chosen to interpret the edges as splines.
> >
> > So far I have managed to extract the edges and convert to a series of splines.
> >
> > Now i've come to the problem of how to implement the resultant data in a microcontroller. I don't really understand how splines are stored in matlab. As far as I understand, splines are a series of curves, all joined together (Bezier curves, paths, however you'd like to call them).
> >
> > So given a spline in ppform, or B-form, how do I know what the equations are for each of the curves?
>
> Spline is a polynomial on each subinterval (piecewise polynomials). On each interval, the polynomial is computed with respect to the relative abscissa to its left bound (leftbound := 0). The coefficients of the polynomials are ranged in each columns of the field COEFS (highest to lowest order - same as used by polyval/polyfit). Consecutive subintervals are separated by the subdivision of the entire interval stored in the field BREAKS.
>
> Bruno

Hi Bruno,

I'm having trouble understanding your response - unfortunately I'm not as adept at MATLAB as i'd like.

>On each interval, the polynomial is computed with respect to the relative abscissa to its left bound (leftbound := 0).

Does this mean that if the first polynomial is active from 1 - 4 and the second polynomial is active from 4 - 5, then the second polynomial must be calculated with the abscissa values of (4 - 4) and (5 - 4)?

I have attempted to redraw the spline by extracting the polynomials from the BREAKS and COEFS fields of the struct, however the result is not what I would expect:
------ CODE --------------------------------------------------
clc
clear all;
close all;

x = 0:10;
y = sin(x);
xx = 0:.25:10;
yy1 = spline(x,y,xx);
yy2 = cscvn([x; y]);
subplot(3,1,1);
plot(x,y,'o',xx,yy1)
subplot(3,1,2);
fnplt(yy2,'r');

xvals = 0;
lastval = 0;
for aspline = 1:length(yy2.breaks) - 1
    xvals = yy2.breaks(aspline);
    subplot(3,1,3);
    yy2coefs = yy2.coefs(aspline,:);
    yy2polyval = polyval(yy2coefs,xvals - lastval);
    plot(xvals, yy2polyval,'-x'), hold on;
    lastval = xvals;
end
------ CODE --------------------------------------------------

could someone please explain to me what i'm missing? I obviously don't correctly understand the way splines are stored.

Thanks,
Tom

Re: Implementing splines in a microcontroller

Tom E — Sun, 22 Nov 2009 16:43:04 -0500

Oh and by the way, I'm using cscvn() because I need to be able to have a 1 to many input, unlike the simple 1 to 1 function (sine) used in this demo.

Re: Implementing splines in a microcontroller

Bruno Luong — Sun, 22 Nov 2009 17:54:03 -0500

x = 0:10;
y = sin(x);
s = spline(x,y);

plot(x,y,'o');
hold on

for aspline = 1:length(s.breaks) - 1
    left = s.breaks(aspline);
    right = s.breaks(aspline+1);
    xx = linspace(left,right,17);
    scoefs = s.coefs(aspline,:);
    yy = polyval(scoefs,xx - left);
    plot(xx, yy);
end

% Bruno

Re: Implementing splines in a microcontroller

Tom E — Sun, 22 Nov 2009 21:48:03 -0500

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hebtrr$l6p$1@fred.mathworks.com>...
> x = 0:10;
> y = sin(x);
> s = spline(x,y);
>
> plot(x,y,'o');
> hold on
>
> for aspline = 1:length(s.breaks) - 1
> left = s.breaks(aspline);
> right = s.breaks(aspline+1);
> xx = linspace(left,right,17);
> scoefs = s.coefs(aspline,:);
> yy = polyval(scoefs,xx - left);
> plot(xx, yy);
> end
>
> % Bruno

Ahh, thanks Bruno - that has helped me understand. I've solved one of the problems with my code, but unfortunately I'm still struggling : (
The method i'm using to generate the spline seems to be wrong. I'm using bwtraceboundary to extract the boundary from a black and white image, and then using cscvn to convert the boundary into a spline.

The problem is in the coefficients cscvn returns. I have a sample image, which is a short horizontal line in an image. I believe the coefficients cscvn returns are correct for every odd row of s.coeffs() (where s is the spline). Each even row has a strange set of coefficients.

As far as I can tell I must be using cscvn incorrectly, because the coefficients are:
0 0 0 5
-0.800000000000000 1.80000000000000 0 1
0 0 0 5
0.400000000000000 -0.600000000000001 1.20000000000000 2
0 0 0 5
-0.800000000000000 0.600000000000000 1.20000000000000 3
0 0 0 5
0.800000000000000 -1.80000000000000 4.46071750965465e-17 4
0 0 0 5
-0.400000000000000 0.600000000000000 -1.20000000000000 3
0 0 0 5
0.800000000000000 -0.600000000000000 -1.20000000000000 2

when I think each row should be:
0 0 0 5

It's probably easier to demonstrate than to explain. I have uploaded the image to h**p://i50.tinypic.com/16jiqzr.jpg
and the code I'm using is below:

-------- CODE -------------------------------------
clc, clear all, close all;
imgToRead = 'Sample_BW_Line_01.jpg';
%imgToRead = 'FHV_logo_BW.gif';
DACdepth = 12; % the bit depth of the DACs

DACres = 2^DACdepth; % the resolution of the DACs
BW = imread(imgToRead);
BW = ~BW;
s=size(BW);
scaleFrom = length(BW);
scaleFactor = DACres/scaleFrom; % determine how much to scale the image by
                                % so that the output is the correct size
                                % for the DACs
boundaries = cell(1);

subplot(3,1,1);
imshow(BW);
for row = s(1):-1:1 % search through each row
for col=1:s(2) % search through each column
  if BW(row,col), %if pixel value is 1:
   contour = bwtraceboundary(BW, [row, col], 'E', 8, Inf,'clockwise');
            % search for the boundary, starting at
            % [row,col] save the points into
            % "contour"
   if(~isempty(contour))
    boundaries{end+1} = cscvn(contour()');
    % boundaries{end+1} = fncmb(cscvn(contour()'),[0 scaleFactor;-scaleFactor 0]);
    % convert the points to a spline, and save to
    % "boundaries". fncmb is used to rotate the image
    % to the correct orientation.
    BW(contour(:,1),contour(:,2)) = 0; % remove the edge from the image
                                       % so it isn't found again
   end
  end
end
end

boundaries(1) = [];
for outline = 1:length(boundaries)
    s = boundaries{outline};
    subplot(3,1,2);
    fnplt(s), hold on;
    for aspline = 1:length(s.breaks) - 1
        left = s.breaks(aspline);
        right = s.breaks(aspline + 1);
        xx = linspace(left, right, 17);
        subplot(3,1,3);
        scoefs = s.coefs(aspline,:);
        yy = polyval(scoefs, xx - left);
        plot(xx,yy);
        hold on
    end
end
set(gca,'PlotBoxAspectRatioMode','manual');
% axis([0 4096 -4096 0]);
subplot(3,1,2);
set(gca,'PlotBoxAspectRatioMode','manual');
%axis([0 4096 -4096 0]);
clear DACdepth col row outline scaleFrom splinetoplot;
-------- CODE -------------------------------------