|
How can i calculate space cimplexity
i need explanation more
|
|
|
|
|
i got a tutorial from internate on Space complexity.i show the important part
of this tutorial below. it's may be help u to calculate space complexity.
The space complexity of a program is the number of elementary objects that
this program needs to store during its execution.
For an algorithm T and an input x, DSPACE(T, x) denotes the
number of cells used during the (deterministic) computation T(x).
We will note DSPACE(T) = O(f (n)) if DSPACE(T, x) = O(f (n))
with n = |x | (length of x).
EXAMPLE:1- note: x is an unsorted array
int findMin(int[] x) {
int k = 0; int n = x.length;
for (int i = 1; i < n; i++) {
if (x[i] < x[k]) {
k = i;
}
}
return k;
}
T(findMin, n) = n + 2
T(findMin, n) = O(n)
EXAMPLE:2- note: x is an unsorted array
void multVect(int[] x, int[][] a) {
int k = 0; int n = x.length;
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
a[i][j] = x[i] * x[j]
}
}
}
T(multVect, n) = n × n + 2
T(multVect, n) = O(n2)
|
|
|
|
|
 hello everybody,i have find a source code of a skin color detection.this program is run well.but i need the explanation of this code.can any body explain this code.i code is given below.....
void Color(IplImage *img);
struct num
{
unsigned char H;
unsigned char S;
unsigned char V;
};
int main( int argc, char** argv )
{
IplImage* pFrame = NULL;
CvCapture* pCapture = NULL;
cvNamedWindow("video",1);
pCapture = cvCaptureFromCAM(-1);
if(pCapture)
{
for(;;)
{
pFrame = cvQueryFrame(pCapture);
Color(pFrame);
// Color_Guass(pFrame);
cvShowImage("video",pFrame);
if(cvWaitKey(10)>=0)
break;
}
cvReleaseCapture(&pCapture);
}
cvDestroyWindow("video");
cvReleaseImage(&pFrame);
return 0;
}
void Color(IplImage *img)
{
int i,j;
IplImage *img_hsv = 0;
img_hsv = cvCreateImage(cvGetSize(img),8,3);
cvCvtColor(img,img_hsv,CV_BGR2HSV);
struct num **bmpdata;
struct num **bmpdata1;
bmpdata = new num*[img->height];
bmpdata1 = new num*[img->height];
//from here i dont understand.please replay me if anybody can understand..........................
for(i=0;i<img->height;i++)
{
bmpdata[i] = new num[img->width];
bmpdata1[i] = new num[img->width];
}
for(i=0;i<img->height;i++)
for(j=0;j<img->width;j++)
{
bmpdata[i][j].H=((uchar*)(img_hsv->imageData + img_hsv->widthStep*i))[j*3];
bmpdata[i][j].S=((uchar*)(img_hsv->imageData + img_hsv->widthStep*i))[j*3+1] ;
bmpdata[i][j].V=((uchar*)(img_hsv->imageData + img_hsv->widthStep*i))[j*3+2];
}
for (i=0;i<img->height;i++)
{
for (j=0;j<img->width;j++)
{
if(bmpdata[i][j].H<=19&&bmpdata[i][j].S>=48)
bmpdata[i][j].H+=0;
else bmpdata[i][j].H=bmpdata[i][j].S=bmpdata[i][j].V=0;
}
}
for (i=1;i<img->height-1;i++)
for (j=1;j<img->width-1;j++)
{
if(bmpdata[i][j].H!=0)
if(bmpdata[i][j-1].H==0||bmpdata[i][j+1].H==0||
bmpdata[i+1][j].H==0||bmpdata[i-1][j].H==0
){
bmpdata1[i][j].H=0;
bmpdata1[i][j].S=0;
bmpdata1[i][j].V=0;
}
else{
bmpdata1[i][j].H+=0;
bmpdata1[i][j].S+=0;
bmpdata1[i][j].V+=0;
}
}
for (i=0;i<img->height;i++)
for (j=0;j<img->width;j++)
{
((uchar*)(img_hsv->imageData + img_hsv->widthStep*i))[j*3]=bmpdata[i][j].H;
((uchar*)(img_hsv->imageData + img_hsv->widthStep*i))[j*3+1]=bmpdata[i][j].S;
((uchar*)(img_hsv->imageData + img_hsv->widthStep*i))[j*3+2]=bmpdata[i][j].V;
}
cvCvtColor(img_hsv,img,CV_HSV2BGR);
cvErode(img,img,NULL,1);
cvDilate(img,img,NULL,1);
}
|
|
|
|
|
Have you tried searching using Google or your favorite search engine? There are hundreds of scholarly papers on the web about this topic.
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
|
i am still searching google.but i do not get the appropiate explanation of this code.
|
|
|
|
|
Out of curiosity, where did you find this gem? 
What the main intent seems to is to preserve pixels with hue values less than equal to 19 and saturation values great than or equal to 48 and to turn pixels that don't match black.
I have no idea why bmpdata1 was even allocated since it's ultimately never used in the code you show. The only reason I can think of is that it's there to waste memory and CPU cycle bacause whoever wrote the program couldn't reverse the sense of their if statements and needed to do the actual work in the else clause. All the "+=0" statements do absolutely nothing. The pair of loops working on bmpdata1 are especially suspicious. It appears to set the pixels in bmpdata1 to zero if a pixel in bmpdata that is nonzero is has a zero neighbor above, below or to the side. The else clause adding zero does nothing. What's more, bmpdata1 is never initialized to anything so the data not set to zero is random.
Not that it probably matters with the rest of this mess, neither bmpdata or bmpdata1 are freed causing memory leaks.
It also appears that all of this work could have been done in place in the original image without doing the copies to and from bmpdata.
If you're looking for an example of segmenting an image based on skin color, I'd try to find a better example.
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
|
Another little faux pas in that example is that (even if it works) it will show an output window, do its calculations, and then immediately close the window before you can study the results. You need a cvWaitKey(0) at the end.
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
|
if(bmpdata[i][j].H<=19&&bmpdata[i][j].S>=48)
bmpdata[i][j].H+=0;
else bmpdata[i][j].H=bmpdata[i][j].S=bmpdata[i][j].V=0;
By the above part,i think,identify the background color.if the condition is satisfy then,
it does not perform nothing(bmpdata[i][j].H+=0), otherwise background set by zero(bmpdata[i][j].H=bmpdata[i][j].S=bmpdata[i][j].V=0)
In addition,the ouput is,only show the skin color and background color show black.
but the below part are confuse me.
for (i=1;i<img->height-1;i++)
for (j=1;j<img->width-1;j++)
{
if(bmpdata[i][j].H!=0)
if(bmpdata[i][j-1].H==0||bmpdata[i][j+1].H==0||
bmpdata[i+1][j].H==0||bmpdata[i-1][j].H==0
){
bmpdata1[i][j].H=0;
bmpdata1[i][j].S=0;
bmpdata1[i][j].V=0;
}
|
|
|
|
|
Yes, the intent seems to be to leave the parts of the picture that are skin unchanged and turn everything else black.
The part you question appears to be some attempt to get rid of isolated pixels that might be noise. If a pixel is nonzero but has a zero neighbor, set it to zero. But as I said, using that to alter, or not, bmpdata1 makes absolutely no sense what so ever.
The Erode and Dilate functions at the end also do that to an extent, too.
Whoever wrote this turkey was clueless. I searched and the only place I found it was an earlier post here on CP. Is that where you found it?
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
|
i have got this code from another site.
this is the link of this source code.
http://read.pudn.com/downloads102/sourcecode/graph/texture_mapping/418188/facecolor.cpp__.htm
you mean that,at the end erod and diod are also doing same task,that you explane.is it?
|
|
|
|
|
This video[^] is basically what you're trying to do with the addition of fingertip identification and bounding box. The technique does work. Plenty of other examples out there. I'm using a variation of the same technique to find an orange traffic cone potentially to be used on a RoboMagellan robot[^].
Erode and Dilate are called morphological operators and one of their uses is to remove noise from images. Pixels are first removed from objects and then replaced. The result is that small objects get removed entirely and there's nothing to build back with.
If you're reasonably serious about learning to use OpenCV to do vision problems, I recommend this book.[^]. It will explain much of what's available in OpenCV and how to use the basic techniques.
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
|
Can u help with the executable code.This code shows some error.Reply as soon as possible.
|
|
|
|
|
Hi All
Hopefully someone can help shed some light for me.
I have some code I have used for years to calculate and store (in SQL Server database), and retrieve and compare a hash value using ComputeHash of the MD5CryptoServiceProvider. I have recently upgraded to x64 (Windows 7) from x86 (Vista) but now my hashes calculated on the x86 does not match when compared (using x64)! (Hope that all makes sense.)
Is there any obvious reasons for this? Where should I be looking??
thanx
|
|
|
|
|
Well, I think I have narrowed it down to the "GetHashCode" being the culprit! After replacing the "GetHashCode" with my own hash function it seems to work in both x86 and x64 OSs.
For Each c As DataColumn In ds.Tables("mytable").Columns
If Not c.ColumnName = "hashvalue" Then
If r(c) IsNot DBNull.Value Then RowHash += r(c).GetHashCode.ToString
End If
Next
' ... compare the "RowHash" with the one stored in the "hashvalue" column ...
This article seem to agree.
"... the .NET Object.GetHashCode() method, which unfortunately differs between x86 and x64 systems."
Any have any clue why?? That sucks (nothing in the documentation)!
modified on Wednesday, August 19, 2009 3:47 AM
|
|
|
|
|
I believe that Microsoft's documentation for GetHashCode specifies that no assumption should be made about the value returned, other than the fact that within a given execution context, if a=b, a.GetHashCode=b.GetHashCode. The release of a class with one version of GetHashCode does not imply a contract that all versions of the class will yield the same GetHashCode; indeed, there may be good reasons why future versions would not.
For example, someone might have a class to store shapes, using a fairly simple GetHashCode implementation, and then discover that some particular application which stores shapes in a hash table performs poorly because many different shapes evaluate to the same hash. If the release of the earlier version of GetHashCode compelled all future versions to perform identically on those shapes, it would be impossible to fix its poor behavior with certain combinations of shapes. Allowing GetHashCode to change avoids this risk.
Further, I would expect that an object's implementation would even be allowed to have an object's hash code vary based upon the circumstances in which it, or the first still-existing object like it, was created. For example, an object holds a strings could, every time the string is modified, check for it in a dictionary and either use or add a dictionary reference. If all matching strings would use the same dictionary reference, the object's GetHashCode could use the hash of that dictionary reference rather than computing the actual hash of the string, even though the hash of the dictionary reference would be affected by when the object was first inserted.
|
|
|
|
|
Thank you for your comment.
I agree, between versions (or even builds) an implementation should be allowed to change and also to change its return value. But here we are talking about exactly the same "implementation" (of the method) behaving on differently depending on the platform/CPU (x86 vs x64). As much as your comment makes sense, I can't see how it applies to the same implementation across CPU - am I missing something?
PS: The "sucks" was just venting my frustration  as my newly found wisdom has caused me quite an substantial bit of extra work
|
|
|
|
|
But here we are talking about exactly the same "implementation" (of the method) behaving on differently depending on the platform/CPU (x86 vs x64).
How do you know that it's really the same implementation? I don't know what operations Microsoft's x86 version of .GetHashValue does for different operand types, but if it uses some operations which are efficient on the x86 and less efficient on x64, or fails to use operations which would be more efficient on the x64, would you want Microsoft to use an inefficient version of .GetHashValue for the x64 versions of .net, or should it use efficient ones?
|
|
|
|
|
"would you want Microsoft to use an inefficient version of .GetHashValue for the x64 versions of .net, or should it use efficient ones?"
...it depends on how it affects me 
oh well, for me, a nuisance thats all - thanks for enlightening me! 
|
|
|
|
|
francoisdotnet wrote: Where should I be looking??
You should be looking in the documentation[^] which makes it very clear that hash values are not fixed from one environment to the next, and cannot be shared between systems. Their sole purpose is to speed up things on one machine by providing a reasonable hash value as fast as possible.
Luc Pattyn [Forum Guidelines] [My Articles]
The quality and detail of your question reflects on the effectiveness of the help you are likely to get.
Show formatted code inside PRE tags, and give clear symptoms when describing a problem.
|
|
|
|
|
I have a loop at the moment that creates a number loop that is 5 deep, each number in a sequence can only be used once...for example
12345
12354
12435
54321 etc...
Here is what i have for the code creating this sequencing...
SortOrder = New List(Of Integer())
Dim iTemp(PanelDepth) As Integer, iCount As Integer = 0
For a As Integer = 0 To PanelDepth - 1
For b As Integer = 0 To PanelDepth - 1
If b <> a Then
For c As Integer = 0 To PanelDepth - 1
If c <> b And c <> a Then
For d As Integer = 0 To PanelDepth - 1
If d <> c And d <> b And d <> a Then
For e As Integer = 0 To PanelDepth - 1
If e <> d And e <> c And e <> b And e <> a Then
ReDim iTemp(PanelDepth)
iTemp(0) = a
iTemp(1) = b
iTemp(2) = c
iTemp(3) = d
iTemp(4) = e
SortOrder.Add(iTemp)
End If
Next
End If
Next
End If
Next
End If
Next
Next
my dilemma is that i need it to be variable on the depth of the sequencing, so for example i might need it to calculate 9 deep, so 123456789, or even more 10/11 sometimes, but i am having trouble coming up with a way to do this, anyone got some ideas that i could try to get it to loop through and still create individual number sets for a <i>n</i> deep sequence?
ta.
|
|
|
|
|
Please don't cross post messages. While this is the original post (based on time) the one that has actually received answers is here[^].
Scott Dorman Microsoft® MVP - Visual C# | MCPD
President - Tampa Bay IASA
[ Blog][ Articles][ Forum Guidelines]
Hey, hey, hey. Don't be mean. We don't have to be mean because, remember, no matter where you go, there you are. - Buckaroo Banzai
|
|
|
|
|
The solution is to use a recursive algorithm that gives all the permutations of a list of elements, regardless of the size.
|
|
|
|
|
I already know about algorithms for traversing trees . I need to traverse a tree and recognize some kind of nodes . For example I want to know if a node is the last child of its far parent.It means the node which has no children and no one of its siblings has any child and also this node must be the last node in terms of its sibilings. How can I recoginze such a node in a recursive function ?
|
|
|
|
|
I'm not sure if this is exactly what you need, but I was thinking along the lines of a modified breadth-first search[^] algorithm:
1) Enqueue all the children of your parent node, setting their depth to 1 (or 0).
2) Examine the next node in the queue.
3) If it has children, enqueue all children, setting their depth to the depth of their parent + 1, and dequeue the node.
4) If it has no children, leave it in the queue.
5) When you have only childless nodes in the queue (i.e. you don't have a next node to process), proceed to step 6, otherwise go back to step 2.
6) Your queue now contains all childless nodes, and those with higher depth are the ones you are looking for.
7) Examine all nodes with higher depth and determine which is the "last node in terms of its siblings" (I guess you have some specific node property to do this ?)
Hope it can be of some help.
2+2=5 for very large amounts of 2
(always loved that one hehe!)
|
|
|
|
|
How can i calculate time complexity and space complexity?
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
