FPGA Central

Hi All,

Excuse me if this is the wrong place to post but..

I have written an app in java that reads from an input from my soundcard.
I want to take that input and detect the note that is playing, so I can
write a GUI guitar tuner plug in.

Assuming I have the input ( I can determing the audio format and generate a
waveform from that, which I am displaying in a real time graph), could some
one point me to the algorithms I should be using to compute the frequency of
the note being played?

Cheers,

Steve

in article R8Rhe.32632$[email protected], SPG at
[email protected] wrote on 05/15/2005 19:43:

> Excuse me if this is the wrong place to post but..

not the wrong place. also try the music-dsp mailing list.

> I have written an app in java that reads from an input from my soundcard.
> I want to take that input and detect the note that is playing, so I can
> write a GUI guitar tuner plug in.

so, i'm assuming that your java program has a buffer of the most current N
samples (say N is 2048 or 2096 if your sampling rate is 44100 Hz). you have
those sample words and can barf them back out or draw them or do whatever
maths your heart desires (and brain conceives), right?

> Assuming I have the input ( I can determing the audio format and generate a
> waveform from that, which I am displaying in a real time graph), could some
> one point me to the algorithms I should be using to compute the frequency of
> the note being played?

this falls in the general category of "pitch detection".

you want the *fundamental frequency* of the waveform, i believe. it's the
reciprocal of the period. computing the latter can be done with something
called the Average Magnitude Difference Function (AMDF) or a variant
sometimes called the Average Squared Difference Function (ASDF). it's
pretty easy conceptually and computationally expensive. is that a problem?

--

r b-j [email protected]

"Imagination is more important than knowledge."

On Sun, 15 May 2005 23:43:45 GMT, "SPG"
<[email protected]> wrote:

>Hi All,
>
>Excuse me if this is the wrong place to post but..

This is so the right place to post this, that we've already
discussed it several times before.

>I have written an app in java that reads from an input from my soundcard.
>I want to take that input and detect the note that is playing, so I can
>write a GUI guitar tuner plug in.

I presume you want to write this for the joy of learning how to do
this, because it's already been done very well. I won't give you a
link here, but I'm sure I mention it in one of the threads below.

>Assuming I have the input ( I can determing the audio format and generate a
>waveform from that, which I am displaying in a real time graph), could some
>one point me to the algorithms I should be using to compute the frequency of
>the note being played?

There's been a recent thread on pitch detection of musical
instruments. Actually, TWO recent threads:

http://groups-beta.google.com/group/...5ee9c7e7ab391f

http://groups-beta.google.com/group/...5e85a8394d7011

>Cheers,
>
>Steve

-----
http://mindspring.com/~benbradley

"robert bristow-johnson" <[email protected]> wrote in message
news:BEAD7507.7500%[email protected]..
> in article R8Rhe.32632$[email protected], SPG at
> [email protected] wrote on 05/15/2005 19:43:
>
>> Excuse me if this is the wrong place to post but..
>
> not the wrong place. also try the music-dsp mailing list.
>
>> I have written an app in java that reads from an input from my soundcard.
>> I want to take that input and detect the note that is playing, so I can
>> write a GUI guitar tuner plug in.
>
> so, i'm assuming that your java program has a buffer of the most current N
> samples (say N is 2048 or 2096 if your sampling rate is 44100 Hz). you
> have
> those sample words and can barf them back out or draw them or do whatever
> maths your heart desires (and brain conceives), right?
>
>> Assuming I have the input ( I can determing the audio format and generate
>> a
>> waveform from that, which I am displaying in a real time graph), could
>> some
>> one point me to the algorithms I should be using to compute the frequency
>> of
>> the note being played?
>
> this falls in the general category of "pitch detection".
>
> you want the *fundamental frequency* of the waveform, i believe. it's the
> reciprocal of the period. computing the latter can be done with
> something
> called the Average Magnitude Difference Function (AMDF) or a variant
> sometimes called the Average Squared Difference Function (ASDF). it's
> pretty easy conceptually and computationally expensive. is that a
> problem?
>
> --
>
> r b-j [email protected]
>
> "Imagination is more important than knowledge."
>
>

Hi,

Thanks for the response..

Yes, I have a buffer that I can play with at my lesiure... Therefore I can
pass the data to whateverroutines I need to create in order to handle the
pitch detection you suggested.

I'll google a bit more on AMDF to see what I can come up with...

Cheers,

Steve

"Ben Bradley" <[email protected]> wrote in message
news:[email protected]..
> On Sun, 15 May 2005 23:43:45 GMT, "SPG"
> <[email protected]> wrote:
>
>>Hi All,
>>
>>Excuse me if this is the wrong place to post but..
>
> This is so the right place to post this, that we've already
> discussed it several times before.
>
>>I have written an app in java that reads from an input from my soundcard.
>>I want to take that input and detect the note that is playing, so I can
>>write a GUI guitar tuner plug in.
>
> I presume you want to write this for the joy of learning how to do
> this, because it's already been done very well. I won't give you a
> link here, but I'm sure I mention it in one of the threads below.
>
>>Assuming I have the input ( I can determing the audio format and generate
>>a
>>waveform from that, which I am displaying in a real time graph), could
>>some
>>one point me to the algorithms I should be using to compute the frequency
>>of
>>the note being played?
>
> There's been a recent thread on pitch detection of musical
> instruments. Actually, TWO recent threads:
>
> http://groups-beta.google.com/group/...5ee9c7e7ab391f
>
> http://groups-beta.google.com/group/...5e85a8394d7011
>
>>Cheers,
>>
>>Steve
>
> -----
> http://mindspring.com/~benbradley

Hi Ben,

I guessed there'd be more posts on this - I'll trawl a bit more and see what
I come up with.

You are correct, It is a personal project that I am working on for pure
*fun*. I don't want to steal/copy anyone's code, just after the rules for
performing this type of feature.

I'll have a read of your threads and see what I can muster up and if I fail
I'll come begging again!

Steve

SPG wrote:

...

> I'll have a read of your threads and see what I can muster up and if I fail
> I'll come begging again!

If you come up with an interesting twist, patent it or let us know. The
Hidden Line Problem was a thorn in the side of the computer graphics
world until an amateur programmer solved it and asked that his "clumsy"
approach be excused as something he had just thrown together.

Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

in article [email protected], Jerry Avins at [email protected] wrote
on 05/16/2005 09:47:

> The Hidden Line Problem was a thorn in the side of the computer
> graphics world until an amateur programmer solved it ...

what's the trick to the Hidden Line Problem? i would think that if you
ordered all of the vertices in order of distance from the observer, then
drew the lines and planes with the furthest vertices first, the closer
surfaces would be drawn last and cover the further surfaces (and lines or
ridges that extend behind the visible surfaces) which is what we want. no?

just a dumb question from someone who as never done anything like that
except in drawing a family of curves.

--

r b-j [email protected]

"Imagination is more important than knowledge."

robert bristow-johnson wrote:
> in article [email protected], Jerry Avins at [email protected] wrote
> on 05/16/2005 09:47:
>
>
>>The Hidden Line Problem was a thorn in the side of the computer
>>graphics world until an amateur programmer solved it ...
>
>
> what's the trick to the Hidden Line Problem? i would think that if you
> ordered all of the vertices in order of distance from the observer, then
> drew the lines and planes with the furthest vertices first, the closer
> surfaces would be drawn last and cover the further surfaces (and lines or
> ridges that extend behind the visible surfaces) which is what we want. no?
>
> just a dumb question from someone who as never done anything like that
> except in drawing a family of curves.

In the beginning was the vector. Do you remember the enormous vector
graphic terminals that only DOD could afford? An early use for
high-speed DACs was generating X and Y deflection. Lines were specified
by their beginning and ending points, and ordered in the display list
with an empirical traveling salesman algorithm. With too many lines, the
display would flicker.

When RAM became dense and cheap enough to support it, we got raster
graphics. There were standard ways to convert the output of vector
algorithms to display bits, and lots of lines didn't slow the refresh.
The fancy line ordering wasn't needed, but the complex work of
determining which parts of which lines were hidden by implied planes was
done the tried-and-true way before all was projected onto the display plane.

Our overworked engineer was programming a presentation of his work. He
knew nothing about computer graphics, including where to look anything
up, so he innovated. He drew the entire rear-most plane into display
RAM, then moved forward a cell and overwrote it with the next one,
moving forward a cell at a time till he reached the front. The only
lines or parts that remained were those that had nothing in front of
them. Instead of a vector solution transformed to raster -- not one of
those algorithms that I knew of was entirely bug free -- he devised the
first (henceforth known as "brute force") way based on raster that used
raster as a starting point.

Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

in article [email protected], Jerry Avins at [email protected] wrote
on 05/16/2005 16:51:

> robert bristow-johnson wrote:
>> in article [email protected], Jerry Avins at [email protected] wrote
>> on 05/16/2005 09:47:
>>
>>
>>> The Hidden Line Problem was a thorn in the side of the computer
>>> graphics world until an amateur programmer solved it ...
>>
>>
>> what's the trick to the Hidden Line Problem? i would think that if you
>> ordered all of the vertices in order of distance from the observer, then
>> drew the lines and planes with the furthest vertices first, the closer
>> surfaces would be drawn last and cover the further surfaces (and lines or
>> ridges that extend behind the visible surfaces) which is what we want. no?
>>
>> just a dumb question from someone who as never done anything like that
>> except in drawing a family of curves.
>
> In the beginning was the vector. Do you remember the enormous vector
> graphic terminals that only DOD could afford?

never saw one of them. but i *did* see a graphics printer with pens (that
needed pen-down and pen-up commands, as well as move commands).

> The fancy line ordering wasn't needed, but the complex work of
> determining which parts of which lines were hidden by implied planes was
> done the tried-and-true way before all was projected onto the display plane.

i understand except what is the "tried-and-true way".

> Our overworked engineer was programming a presentation of his work. He
> knew nothing about computer graphics,

like me.

> including where to look anything up, so he innovated.

sounds like wheels i had to re-invent.

> He drew the entire rear-most plane into display
> RAM, then moved forward a cell and overwrote it with the next one,
> moving forward a cell at a time till he reached the front.

okay, what precisely, is a "cell"? is it a corner of a finite plane? is it
a pixel that possibly lies on a line? is it a pixel of a plane? how is
this different from what i described? how is this *not* "fancy line
ordering"?

since the coordinates of the rear-most plane are not all the same distance
from the observer, what defines the rear-most plane? the rear-most corner
of a plane? what if planes intersect (and pass through each other)? must
that not be determined first? or is that simply prohibited in this
practical 3-D graphics scheme (i.e. planes end where they are joined)?

> The only lines or parts that remained were those that had nothing in front
> of them. Instead of a vector solution transformed to raster -- not one of
> those algorithms that I knew of was entirely bug free -- he devised the
> first (henceforth known as "brute force") way based on raster that used
> raster as a starting point.

sounds like the wheel i was reinventing. i dunno how i would extend it to
surfaces that were not planes. like parts of spheres or ellipsoids. and
what about solids?

--

r b-j [email protected]

"Imagination is more important than knowledge."

robert bristow-johnson wrote:
> in article [email protected], Jerry Avins at [email protected] wrote
> on 05/16/2005 16:51:
>
>
>>robert bristow-johnson wrote:
>>
>>>in article [email protected], Jerry Avins at [email protected] wrote
>>>on 05/16/2005 09:47:
>>>
>>>
>>>
>>>>The Hidden Line Problem was a thorn in the side of the computer
>>>>graphics world until an amateur programmer solved it ...
>>>
>>>
>>>what's the trick to the Hidden Line Problem? i would think that if you
>>>ordered all of the vertices in order of distance from the observer, then
>>>drew the lines and planes with the furthest vertices first, the closer
>>>surfaces would be drawn last and cover the further surfaces (and lines or
>>>ridges that extend behind the visible surfaces) which is what we want. no?
>>>
>>>just a dumb question from someone who as never done anything like that
>>>except in drawing a family of curves.
>>
>>In the beginning was the vector. Do you remember the enormous vector
>>graphic terminals that only DOD could afford?
>
>
> never saw one of them. but i *did* see a graphics printer with pens (that
> needed pen-down and pen-up commands, as well as move commands).

I have two. They run off HPIB; there's a parallel-port adapter cable for
one. Do you want one?

>>The fancy line ordering wasn't needed, but the complex work of
>>determining which parts of which lines were hidden by implied planes was
>>done the tried-and-true way before all was projected onto the display plane.
>
>
> i understand except what is the "tried-and-true way".

Project lines from the viewplane to each pixel on the line. If the
projected line intersects anything, don't display that pixel. Is it any
wonder that refresh was slow with more than a few lines and the planes
they defined?

>>Our overworked engineer was programming a presentation of his work. He
>>knew nothing about computer graphics,
>
>
> like me.
>
>
>>including where to look anything up, so he innovated.
>
>
> sounds like wheels i had to re-invent.
>
>
>>He drew the entire rear-most plane into display
>>RAM, then moved forward a cell and overwrote it with the next one,
>>moving forward a cell at a time till he reached the front.
>
>
> okay, what precisely, is a "cell"? is it a corner of a finite plane? is it
> a pixel that possibly lies on a line? is it a pixel of a plane? how is
> this different from what i described? how is this *not* "fancy line
> ordering"?

A cell is a cube. Its sides are x, y, and z. "Picture cell" slid into
"pixel" Instead of writing "moved forward a cell", I would better have
written "moved forward to the next z plane." About fancy line ordering:
imagine one of those pen plotters were drawing the pictures, and the aim
is to minimize total pen motion. There is a drawing order that does
that. To show yourself that the ordering is fancy, try to program it.
Include optimization when some lines have their middles obscured. This
matters even with DACs, because large jumps in yoke current need more
settling time than small ones.

> since the coordinates of the rear-most plane are not all the same distance
> from the observer, what defines the rear-most plane? the rear-most corner
> of a plane? what if planes intersect (and pass through each other)? must
> that not be determined first? or is that simply prohibited in this
> practical 3-D graphics scheme (i.e. planes end where they are joined)?

For the most part, we're considering orthographic projection.
Perspective is usually derived from an orthographic view by warping it.
That doesn't have the precision of ray tracing, but few notice. Leaving
the hidden lines in makes a "wire frame model", much simpler both in
vector and raster graphics.

>>The only lines or parts that remained were those that had nothing in front
>>of them. Instead of a vector solution transformed to raster -- not one of
>>those algorithms that I knew of was entirely bug free -- he devised the
>>first (henceforth known as "brute force") way based on raster that used
>>raster as a starting point.
>
>
> sounds like the wheel i was reinventing. i dunno how i would extend it to
> surfaces that were not planes. like parts of spheres or ellipsoids. and
> what about solids?

Surfaces are often defined by a web of triangles, as in finite-element
modeling. Shading depends on orientation; one way to make the joining
lines disappear is specifying the brightness at the centroids of the
triangles and use a 2-D low-pass filter to find the brightness at
intermediate points. Many graphics guys don't know it's a 2-D LPF. They
think its Somebody's Algorithm.

Graphics, like DSP, is science, art, and accumulated wisdom. When a
graphics guy asks me about DSP, I can explain a little. I can actually
do that a little better than explaining graphics to a DSP guy. Unless
there's something I wrote that's still unclear, I haven't much more to
offer.

Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

On Tue, 17 May 2005 12:46:44 -0400, Jerry Avins <[email protected]> wrote:

>...

>A cell is a cube. Its sides are x, y, and z. "Picture cell" slid into
>"pixel" Instead of writing "moved forward a cell", I would better have
>written "moved forward to the next z plane." About fancy line ordering:
>imagine one of those pen plotters were drawing the pictures, and the aim
>is to minimize total pen motion. There is a drawing order that does
>that. To show yourself that the ordering is fancy, try to program it.

Is this the same as the Traveling Salesman problem? It sure looks
like it.

>Include optimization when some lines have their middles obscured. This
>matters even with DACs, because large jumps in yoke current need more
>settling time than small ones.

>...

>Jerry

-----
http://mindspring.com/~benbradley

Ben Bradley wrote:
> On Tue, 17 May 2005 12:46:44 -0400, Jerry Avins <[email protected]> wrote:
>
>
>>...
>
>
>>A cell is a cube. Its sides are x, y, and z. "Picture cell" slid into
>>"pixel" Instead of writing "moved forward a cell", I would better have
>>written "moved forward to the next z plane." About fancy line ordering:
>>imagine one of those pen plotters were drawing the pictures, and the aim
>>is to minimize total pen motion. There is a drawing order that does
>>that. To show yourself that the ordering is fancy, try to program it.
>
>
> Is this the same as the Traveling Salesman problem? It sure looks
> like it.

I wrote a few posts back, "... Lines were specified by their beginning
and ending points, and ordered in the display list with an empirical
traveling salesman algorithm. ..."

The short answer is "Yes".

Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

In article <R8Rhe.32632$[email protected] >,
SPG <[email protected]> wrote:
>I have written an app in java that reads from an input from my soundcard.
>I want to take that input and detect the note that is playing, so I can
>write a GUI guitar tuner plug in.
>
>Assuming I have the input ( I can determing the audio format and generate a
>waveform from that, which I am displaying in a real time graph), could some
>one point me to the algorithms I should be using to compute the frequency of
>the note being played?

The are lots of algorithms mentioned in the historical archives of this
newsgroup, going back a decade or more.

If you know the note being played, just not its exact frequency, and
the harmonic content isn't too high, you could try a band pass filter
around the octave of interest followed by zero crossing measurements.

The FFT magnitude spectrum is another algorithm to try, although you
should expect the peaks to often indicate harmonics instead of what
you might consider the frequency of the note being played. You might
also want to try spectrum interpolation, or zero padding techniques
to resolve frequencies between FFT bins. Two techniques for testing
for whether something around a lower or sub harmonic in the frequency
spectrum might be what your brain hears as "fundamental" frequency are
the ASDF and the real Cepstrum. Note that both these algorithms can be
fooled by inharmonic spectra common to some tones produced by thick and
stiff strings.

Note that a guitar "note" evolves over time, so the use of historical
data might be useful (e.g. you might want to try feeding the results of
the complex FFT's of many succesive frames of data into a neural net or
other pattern recognizer).


IMHO. YMMV.
--
Ron Nicholson rhn AT nicholson DOT com http://www.nicholson.com/rhn/
#include <canonical.disclaimer> // only my own opinions, etc.

On Tue, 17 May 2005 23:30:53 -0400, Jerry Avins <[email protected]> wrote:

>Ben Bradley wrote:
>> On Tue, 17 May 2005 12:46:44 -0400, Jerry Avins <[email protected]> wrote:
>>
>>
>>>...
>>
>>
>>>A cell is a cube. Its sides are x, y, and z. "Picture cell" slid into
>>>"pixel" Instead of writing "moved forward a cell", I would better have
>>>written "moved forward to the next z plane." About fancy line ordering:
>>>imagine one of those pen plotters were drawing the pictures, and the aim
>>>is to minimize total pen motion. There is a drawing order that does
>>>that. To show yourself that the ordering is fancy, try to program it.
>>
>>
>> Is this the same as the Traveling Salesman problem? It sure looks
>> like it.
>
>I wrote a few posts back, "... Lines were specified by their beginning
>and ending points, and ordered in the display list with an empirical
>traveling salesman algorithm. ..."

Darn. Sorry, I obviously hadn't read every word in the thread...

>The short answer is "Yes".
>
>Jerry

-----
http://mindspring.com/~benbradley

Ben Bradley wrote:

...

> Darn. Sorry, I obviously hadn't read every word in the thread...

Why sorry? It took insight to pick that up.

I could have been gloating, but I wasn't. I was just showing off that
I'm nearly as smart as you. :-)

Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯