|
Oh, right I saw that earlier, not sure what to say.
|
|
|
|
|
Well, this is a quadratic equation, with roots at 0 and 1 and therefore a midpoint at ½.
y = (x - ½)² - ¼ (expand and compare with the initial constant which was 0)
(x - ½)² = y + ¼
x - ½ = sqrt(y + ¼)
x = sqrt(y + ¼) + ½
Since you're already using a square root this won't be much more expensive than what you're doing now (maybe less, not sure of the cost of ceil) and it's accurate.
x(x - 1) isn't that close to x², it differs by x and therefore the relative error only goes down as 1/x. That's a very poor approximation and I don't see why you'd use it if it's also an expensive one with a sqrt in it.
|
|
|
|
|
|
Hello
I'm searching for some algorithm that could compare two files by content and return the list of differences. I have successfully implemented the LCS - Longest Common Subsequence algorithm and got it up and running with backtracking, but this algorithm is only usable for short strings. Event with some optimizations (trimming) this algorithm blows up the memory with long string (marix size is quadratic to the length processed string)
Can you please help me out on what my options are?
Thanks you very much and have a wonderful day!
Tomas
|
|
|
|
|
|
Luc's may have won, but I like mine PIEBALDdiff[^].
It doesn't bother with LCS or Levenshtein (yet) and still gets good results with (probably) less memory and more flexibility. 
|
|
|
|
|
Nah. Mine was meaner. 
|
|
|
|
|
|
Is only going to happen when your brother is the governor of Florida.
|
|
|
|
|
I would like to create a program in C# to process audio and perform low pass and high pass filtering on it.
Can anyone tell me where I should start to implement these filters? Is there any source code you are aware of, or maybe ready made DLLs which I can use?
|
|
|
|
|
Don't know specifically about stuff in C#... but the low and high pass filter design algorithms are all digital signal processing (DSP) algorithms, so as far as study and design of the algorithm itself, you can use Matlab (or the open source alternative Octave) to lay out the design. Once understood, you can code it yourself onto C#.
Try Google to see if there's open source libraries for this, they're fairly common audio synthesis operations so there must be libraries out there (although unfortunately I couldn't direct you right to one).
|
|
|
|
|
For frequency filters the general pattern is: fourier transform input, filter transform, fourier inverse (which is magically the same transform!  ) the filtered transform to get a new sound stream. I haven't done it but I did, a while back, look for fast fourier transform in C# and there was a pretty good library out there.
I realise this is minimally helpful but hopefully that gives you some search pointers at least.
|
|
|
|
|
Fast Fourier Transform filtering is certainly an option.
It's a very intuitive solution since, like BobJanova states, band-pass filtering can be easily achieved by doing these steps:
1) Forward FFT of the input data,
2) Zeroing the result bins of the frequencies that we want to remove, and finally,
3) Perform reverse FFT on the same data.
However, this is a very expensive approach, if fast execution is a must, I would recommend trying a FIR digital filter instead. I have no experience designing such a filter myself, but there used to be a really great freeware tool around named DSPlay. I Googled for a while and unfortunately can't find it any more. This GUI tool allowed you to easily create band-pass filters by specifying a few input parameters and generated very simple C code that was directly usable in C#.
Let me take a look as I'm certain I have the DSPlay tool in a pervious hard disk backup...
|
|
|
|
|
I've done a bit of work on this in the past, and one very useful resource is the audio biquad cookbook - http://www.musicdsp.org/files/Audio-EQ-Cookbook.txt[^].
Biquads are a quick and easy way to get the sorts of effects you're looking for. If you want to explore more, or need higher quality, do some searches for digital filter designs or DSP designs - there are loads of sites which have examples as well as the maths behind them.
I should add that I wrote my filter code in C, rather than C#, and although it probably will be OK on modern machines, you might not get as high performance (throughput).
Days spent at sea are not deducted from one's alloted span - Phoenician proverb
|
|
|
|
|
How I can implement this algorithm?
I found this algorithm is not very easy for it.
Can anyone give me some idear.
Before i found several question about nearest color.
FindNearestColor{...}
maybe color texture is used ?
face1 and face2 ,match face2's colour into face1.
I know this is not very easy. How about this algorithm?? thanks
Everything will be happy!
|
|
|
|
|
I'm not very familiar with photoshop or this particular function is but since no one else has answered I'll try and help you but I may be misunderstanding the question.
Colors are normally represented as 3 bytes. One for red, one for green, and one for blue (RGB)and all colors are a mixture of those 3 values. So if I understand the question right all you would need to do is get those values and then compare them.
Maybe you could elaborate on what this Photoshop function does and more people would be able to help you.
|
|
|
|
|
For example: My problem is just like that: matting image technique. Switch person's face.
Just you know ,we need recognize the persion's face. If we can recoginize the persion's face. How to fuse the face color? as you know there are some difference between these two faces.I did not know how to do research on this problem. thank you very much!
Everything will be happy!
|
|
|
|
|
I searched and do a research for this topic,I found Poisson Image Editing algorithm can solve my problem.
Poisson Image Edit algorithms
thank you very much!
Everything will be happy!
|
|
|
|
|
Face detection is quite a complex subject and requires a fair amount of research. However there are some libraries available which you can probably find via Google.
Unrequited desire is character building. OriginalGriff
I'm sitting here giving you a standing ovation - Len Goodman
|
|
|
|
|
Yes face detection is difficult. I use sereral libriaries too.
Everything will be happy!
|
|
|
|
|
<a href=""></a><a href=""></a><a href=""></a><a href=""></a><a href=""></a><a href=""></a><a href=""></a><big><big><small><b></b></small></big></big>
Mens North Face 3 in 1 Some sort of Crest Series ®, no matter if natural conditions associated with climbing the actual Himalayan peak, and also climb hidden within To the south The us jungle huge walls, or even the freezing cool Antarctic expedition apple, all of our out-of-doors activities lovers can certainly withstand this test from the world negative setting, maintain the entire shape comfortable and also dry out. North face outlet.
http://www.northfacehonsale.com/
|
|
|
|
|
I have been looking at Levenshtein Distance again, as part of a tool to display differences in database schema items (scripts of views and such).
I am hoping to find a more memory-efficient way of calculating the distance; I don't like having to allocate a huge two-dimensional array. The best I have come up with so far is to allocate only a 2-by-[length of the shorter string] array.
Has anyone here devised an implementation of Levenshtein Distance that requires less memory?
|
|
|
|
|
You could try the idea of sparse arrays. A sparse array is an array that has a default value for a given element unless it's been set. The setting of the element actually allocates space for that "slot".
So, the underlying implementation of the "array" may be a dictionary or hashtable where the index is the key to the element. If the element doesn't "exist" then the default value is returned.
Capiche?
If your actions inspire others to dream more, learn more, do more and become more, you are a leader." - John Quincy Adams
You must accept one of two basic premises: Either we are alone in the universe, or we are not alone in the universe. And either way, the implications are staggering” - Wernher von Braun
|
|
|
|
|
I don't think that would help, because the basic Levenshtein Distance algorithm fills the entire array.
|
|
|
|
|
For similar strings the relevant data in the 2D matrix eventually is located around the diagonal (although the naive implementation of the algorithm, such as shown by Wikipedia, needs all the matrix elements to come up with the distance). So what you could do is:
1. use a sparse matrix, as ahmed already suggested; [ADDED] maybe in the top triangle, you don't need to store those elements that equal their top neighbour plus one, and in the bottom triangle those that equal their left neighbour plus one. However this is likely to fail dramatically if the strings start out with a couple of differences...[/ADDED]
2. or use a band centered around the main diagonal, making the memory cost linear rather than quadratic (unless you want to have the band's thickness a constant fraction of the problem size);
3. or develop something similar to the sliding window approach I applied here: LPTextFileDiff: another textfile compare utility.[^]
For #2 and #3 you would need:
- to estimate the first row and column values from what you already have, that could be tricky and somewhat unreliable;
- to detect pathological cases
You would not get exact distance for very distant strings, which I guess isn't really important.
Another way to attack the problem is by "tokenizing", i.e. replace your input (a sequence of characters) by a sequence of tokens, where a token would be a specific identifier, a keyword, an operator, white space, etc., whatever is relevant in the language you're dealing with. That may reduce the dimension of the problem by a factor of 3 to 5 I'd say.
If you're not inclined to create a full tokenizer (which is much simpler than a full parser), you could still look for popular strings (say all the keywords) and replace each of them by a different Unicode character that is not supposed to be present otherwise.
[ADDED]And then, maybe you don't really want Levinshtein at all, any good measure of difference could be sufficient. How about this stochastic one:
int distance=0;
for(a fixed number of iterations, say 300) {
from the shortest string select a random substring with length 1%
search for it in the longer string;
if (no hit) {
distance+=BIG_NUMBER;
} else {
if (multiple hits) find the one that is closest to the original, position wise (and relative, work in %)
distance+=square of distance of positions in smaller and larger string
}
}
This may take more cycles but it won't cost you a lot of memory!
[/ADDED]
modified 18-Oct-11 22:02pm.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
