help de-noise algorithm (fixed form threshold)

This is a discussion on help de-noise algorithm (fixed form threshold) within the C Programming forums, part of the General Programming Boards category; hi, im working on signals, here is an introduction to the context where i am. im my work there is ...

  1. #1
    Registered User
    Join Date
    Jan 2008
    Posts
    9

    help de-noise algorithm (fixed form threshold)

    hi, im working on signals, here is an introduction to the context where i am.

    im my work there is a 1-dimension camera that takes pictues in black and white.

    so when i take a picture , i graphicate it and i receive a signal very similar to the waveform of an audio track.
    but in my graphic, X AXIS is the vertical value in pixels and Y AXIS is Gray level detected. so you have all the colors taken on a vertical line.

    we are using this to count an ammount of sheets stacked, and what i receive is a tooth style signal, but with a lot of noise because of the material of the sheet.

    i`ve been searching a lot of algorithms to take out the noise of my signal, so then i can apply a "peaks-valley detection--counting algorithm" (thats another chapter upcoming soon)

    what ive had tried is MCMASTER'S algorithm that makes a singal smoother, but is not useful for me, just doesnt work.

    then i looked in a lot of papers about the fixed form threshold (being the best one among others) and many other algorthms that take out noise and you actually dont loose important points.


    after hours of searching the code...but instead finding nice screenshots and descriptions of it like if the reader knew the algorithm....i ended with no succes...so i come here asking if someone can explain me (or give a link) the method in a way so i can program it.

    thanks for reading, i hope someone can help me.

    bye
    cristobal

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    More particulars would be very helpful. You may want to post a pic of your signal which shows the noise problem at photobucket, and link it in your post in img tags so we can see what you're talking about, in more detail.

    What happened when you tried McMaster's algorithm? Details are needed here. Perhaps your implementation of McMaster's algorithm just needs some tweaking to work correctly.
    Can you post your coded efforts and show the results from that? Again, a picture would be helpful. It's hard to describe a signal pattern in just words.

    If you can describe the steps needed to clean up the signal wave, in simple enough terms to allow a computer to take those steps, then it should be quite possible to code it up.

  3. #3
    Registered User
    Join Date
    Jan 2008
    Posts
    9
    you are right, i just took some screenshots from my application.

    Here is the 1-Dimension Photo (black and white), and below each graphic you see how it would look in 2D.

    1.0) IMAGE NOT PROCESED
    http://www.upload-images.net/imagen/545bb24098.jpg

    1.1) IMAGE NOT PROCESED ( ZOOM IN )
    http://www.upload-images.net/imagen/ebcbc52080.jpg

    2.0) IMAGE PROCESED (MCMASTERS... 24 ITERATIONS)
    http://www.upload-images.net/imagen/3ce5c67d13.jpg

    2.1) IMAGE PROCESED (MCMASTERS... 24 ITERATIONS) ZOOM IN
    http://www.upload-images.net/imagen/ef89f337e5.jpg


    in this example taken randomly just a minute ago, mcmaster's smoothen method does it very well. but sometimes i loose some sheets for the counting, because mcmasters takes the average point from a sequence, so sometimes that means to move the point up.

    i`ve also tried some of my home-made algorithms but mcmasters is the best i have now. i dont know whats the logic for the de-noise algorithms remaining but i would like to test them ...having their logic is all we need.

    any of these are useful

    -fixed form threshold
    -heuristic SURE
    -SURE

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    This part is unclear:

    in this example taken randomly just a minute ago, mcmaster's smoothen method does it very well. but sometimes i loose some sheets for the counting, because mcmasters takes the average point from a sequence, so sometimes that means to move the point up.
    Is "the point" represented by the single red dot in the graph of each wave?

    How much can "the point" be raised before your counter begins mis-counting?

    Does McMasters program have a way to use a lower average, or "squash" the line downward to smooth it, instead of choosing an average value.?

    If the line could be lowered in that way, would it still be usable, or would the loss of the highest point value make it useless?

  5. #5
    Registered User
    Join Date
    Jan 2008
    Posts
    9
    the red dots are part of the counting method(we have an algorithm there running for testing), you can ignore those red points now.

    mcmasters algorithm logic is about picking five points one after another, calculate the average point from it, then move it half the distance to the third one. one iteration consist on doing this starting with the 3 point from the curve as center of the five (so point 1 and 2 to the left and point 4 and 5 to the right) and ending at N-2 as center of the five(same ... ).

    link, with a very good explanation.
    http://www.geogra.uah.es/gisweb/1mod...ualisation.htm

    the valley of each wave shouldnt be raised, but a little is allowed (maybe 5% of the distance peak to valley), its a relative value for each input of data.

    lossing the highest value is not so much of a problem, the important is the valley so that the tooth concept still can be applicable. its a good idea i should try add that part of code and see how it changes.

    thanks for trying to help, and for your time. ill keep searching meanwhile other posibilities.

    bye

    cristobal

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,269
    It seems to me that a simple moving average would do the trick, as you aren't interested in the actual picture as much as counting the peaks and troughs.

    btw that's called a greyscale image (or grayscale depending on where you live), not a black and white image.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,160
    Look in any basic DSP book. You are trying to pick out a repetitive underlying signal. Take a single cycle of the ideal wave, reverse it, and convolve it with the signal. This produces a correlation signal. Count the peaks of this new signal.

  8. #8
    Registered User
    Join Date
    Jan 2008
    Posts
    9
    i`ve been searching and found that there are 2 types of threshold. here is what i learned

    -Hard threshold (known by most people)
    -Soft Threshold (makes the new curve smoother)

    both of them have an IF ELSe condition very trivial.1

    but the important part is when selecting the threshold value,
    there are a lot of ways to calculate it and fixed form threshold is one of them:

    FIXED FORM: sqrt(2*log(length(y)))

    source: http://www.mathworks.com/products/wa...alsdemo.html#5


    the only problem is, if length(Y) is the length of the function... where is the relation with the y values which im going to compare later to apply the threshold. dont know if you guys see the ambiguity of that? i could have f(x) values going from 1 to 10 with a curve length of 50, or i could i have f(x) values going from 1000000 to 2000000 and curve length 50.... i would get the same threshold and thats not correct.

    thats my only question now...
    (sorry for english mistakes)

  9. #9
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,160
    Quote Originally Posted by neoideo View Post
    the only problem is, if length(Y) is the length of the function... where is the relation with the y values which im going to compare later to apply the threshold. dont know if you guys see the ambiguity of that? i could have f(x) values going from 1 to 10 with a curve length of 50, or i could i have f(x) values going from 1000000 to 2000000 and curve length 50.... i would get the same threshold and thats not correct.
    The reason the method is confusing is because it sucks. In real world applications problems of this kind are solved by correlation, which is probably what you should do as well.

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    It sounds like the correlation signal method posted by Brewbeck would be good.

    Have you looked into that? What did you find out?

    An idea that started rattling around in my head was to just use the 5 inputs points of the McMasters program in a slightly different way:

    if the lowest input point is above M (where M is a median value you have calculated, which wouldn't have to be anything accurate at all, btw.), then the average is set to the 4th highest input point, instead of the 3rd, as it is now.

    else
    the 2nd lowest input point is set as the mid-point, instead of the 3rd input point.

    That would have the subtle effect of slightly raising the signal at the peak, and slightly lowering the valley at the trough. Just one if else to code in, and nothing dramatic enough to have to change your optical counter.

    If you find that isn't enough, you might try setting the line-smoothing average at the highest input point on the top half of the signal, and on the very lowest input point on the lower half.

    Is the McMasters program open source? Adding the above would be easy and you could test it very easily. Maybe try both of the above, and see which works better.

    I looked into the website you posted the url for. I didn't think it was appropriate for your needs. It works from a threshold, separating the noise out that way. You don't need that. You just need the signal smoothed out, and McMasters program does a fine job. Add the if else statement into that program and you should be able to work from there.

    If that doesn't work, there are all kinds of other variations you can try. I just mentioned the two I thought were best.
    Last edited by Adak; 01-04-2008 at 04:43 PM.

  11. #11
    Registered User
    Join Date
    Jan 2008
    Posts
    9
    that seems a very interesting idea

    im going to code in those conditions
    lets see how it works!

    pd: about the median value. you meant calculate it from the 5 input points in the algorithm? or from whole the signal?

    thanks in advance

    cristobal
    Last edited by neoideo; 01-08-2008 at 01:50 PM.

  12. #12
    Registered User
    Join Date
    Jan 2008
    Posts
    9
    im also checking the correlation method which seems professional,
    its god to have more than one option ill try to test them all and keep the best one for my situation.

    thanks brewbuck

  13. #13
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by neoideo View Post
    that seems a very interesting idea

    im going to code in those conditions
    lets see how it works!

    pd: about the median value. you meant calculate it from the 5 input points in the algorithm? or from whole the signal?

    thanks in advance

    cristobal
    From the 5 input points that the McMasters algorithm uses.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Getting an error with OpenGL: collect2: ld returned 1 exit status
    By Lorgon Jortle in forum C++ Programming
    Replies: 6
    Last Post: 05-08-2009, 08:18 PM
  2. How accurate is the following...
    By emeyer in forum C Programming
    Replies: 22
    Last Post: 12-07-2005, 11:07 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. Linking error
    By DockyD in forum C++ Programming
    Replies: 10
    Last Post: 01-20-2003, 04:27 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21