ralph78
asked on
how does paint do?
Hi,
I want to make a "surface selection" function, which would work exactly as "fill" function of paint, photoshop, etc... So my function look like:
DWORD TWPICTURE::Mark4Linked(con st DWORD x,const DWORD y,const TWCOLOR &col,const VALUE &threshold)
{
DWORD notsim=0,res=0,offs=width* y+x;
if(workbuf[offs]) return 0;
static TWCOLOR c1;
workbuf[offs]=1;
if((y>0) && (!workbuf[offs-width]))
{
GetPixel(offs-width,c1);
if(col.IsSimilar(c1)>=thre shold) res=Mark4Linked(x,y-1,col, threshold) ;
else ++notsim;
}
if((y<height-1) && (!workbuf[offs+width]))
{
GetPixel(offs+width,c1);
if(col.IsSimilar(c1)>=thre shold) res+=Mark4Linked(x,y+1,col ,threshold );
else ++notsim;
}
if((x>0) && (!workbuf[offs-1]))
{
GetPixel(offs-1,c1);
if(col.IsSimilar(c1)>=thre shold) res+=Mark4Linked(x-1,y,col ,threshold );
else ++notsim;
}
if((x<width-1) && (!workbuf[offs+1]))
{
GetPixel(offs+1,c1);
if(col.IsSimilar(c1)>=thre shold) res+=Mark4Linked(x+1,y,col ,threshold );
else ++notsim;
}
if(notsim) workbuf[offs]=2;
return res;
}
workbuf is a buffer, same size as the picture, initialized with 0. i want to "mark" the pixels inside the shape with 1, and the boudaries pixels with 2. It works pretty well, but only for small surfaces.
if the surface is too big, i got a stack overflow. Should I increase the size of the stack, or is there another way for my pixels selection?
best regards,
Raph
I want to make a "surface selection" function, which would work exactly as "fill" function of paint, photoshop, etc... So my function look like:
DWORD TWPICTURE::Mark4Linked(con
{
DWORD notsim=0,res=0,offs=width*
if(workbuf[offs]) return 0;
static TWCOLOR c1;
workbuf[offs]=1;
if((y>0) && (!workbuf[offs-width]))
{
GetPixel(offs-width,c1);
if(col.IsSimilar(c1)>=thre
else ++notsim;
}
if((y<height-1) && (!workbuf[offs+width]))
{
GetPixel(offs+width,c1);
if(col.IsSimilar(c1)>=thre
else ++notsim;
}
if((x>0) && (!workbuf[offs-1]))
{
GetPixel(offs-1,c1);
if(col.IsSimilar(c1)>=thre
else ++notsim;
}
if((x<width-1) && (!workbuf[offs+1]))
{
GetPixel(offs+1,c1);
if(col.IsSimilar(c1)>=thre
else ++notsim;
}
if(notsim) workbuf[offs]=2;
return res;
}
workbuf is a buffer, same size as the picture, initialized with 0. i want to "mark" the pixels inside the shape with 1, and the boudaries pixels with 2. It works pretty well, but only for small surfaces.
if the surface is too big, i got a stack overflow. Should I increase the size of the stack, or is there another way for my pixels selection?
best regards,
Raph
ASKER
hummm.... idea 1 is not recursive???
once i know my 1st segment, i have to recurse for each point of this segment and so on for all new segments, isn't it? so my problem is same...
once i know my 1st segment, i have to recurse for each point of this segment and so on for all new segments, isn't it? so my problem is same...
It can be recursive. But I had in mind to do a number of loops for it. Each loop starts from the result of the preceeding one but is not called from within the first loop.
Xstart = x;
Ystart = y;
GetPixel (y*width+x, c1);
while (col.IsSimilar (c1)) {
workbuf[y*width+x] = 1;
++x;
GetPixel (y*width+x,c1);
}
// TODO: set last value in workbuf to 2.
x = Xstart; // y remained
GetPixel (y*width+x, c1)
while (col.IsSimilar (c1)) {
workbuf[ ...];
--x;
GetPixel (...)
}
// TODO: set last value in workbuf to 2.
for (firstvalue with 2, lastvalue with 2, ++ind) {
while () {
++y
}
while () {
--y
}
}
The next iteration is in the non recursive approach more complex than the last one but feasable. So you are right in the sense that you have to start a test from each point of the first iteration but it doesn't need to be recursion.
Xstart = x;
Ystart = y;
GetPixel (y*width+x, c1);
while (col.IsSimilar (c1)) {
workbuf[y*width+x] = 1;
++x;
GetPixel (y*width+x,c1);
}
// TODO: set last value in workbuf to 2.
x = Xstart; // y remained
GetPixel (y*width+x, c1)
while (col.IsSimilar (c1)) {
workbuf[ ...];
--x;
GetPixel (...)
}
// TODO: set last value in workbuf to 2.
for (firstvalue with 2, lastvalue with 2, ++ind) {
while () {
++y
}
while () {
--y
}
}
The next iteration is in the non recursive approach more complex than the last one but feasable. So you are right in the sense that you have to start a test from each point of the first iteration but it doesn't need to be recursion.
ASKER
ehhh... yes, i have benn thinking to this solution, unfortunately we won't consider shapes like this:
+-----------+ +--+
| x | | |
| |___| |
+--------------------+
(x is the start point)
nor like this
+-----------------+
| x +----+ |
| |___| |
+-----------------+
(sorry for poor drawing)
I partialy solved my problem by increasing the size of my stack, but, particularly if the shape is big, recursion remains a problem.
+-----------+ +--+
| x | | |
| |___| |
+--------------------+
(x is the start point)
nor like this
+-----------------+
| x +----+ |
| |___| |
+-----------------+
(sorry for poor drawing)
I partialy solved my problem by increasing the size of my stack, but, particularly if the shape is big, recursion remains a problem.
The shpaes you've drawn are the difficult ones. If you don't have to consider them, be happy! In that case you can limit the number of loops.
But I still prefer the other solution; compare all pixels whether they are similar. This shifts the problem to find a closed object around your starting point. An approach would be to start from x which you set to 2, all other similar pixels are 1. Now you go up from every pixel with a 2 until either you hit the border or a 0 pixel and set those values to 2. Just go in all directions until the you can't increase a pixel in any direction.
But I still prefer the other solution; compare all pixels whether they are similar. This shifts the problem to find a closed object around your starting point. An approach would be to start from x which you set to 2, all other similar pixels are 1. Now you go up from every pixel with a 2 until either you hit the border or a 0 pixel and set those values to 2. Just go in all directions until the you can't increase a pixel in any direction.
ASKER
i meant your solution can't consider the shapes i drawn, but i HAVE to;-)
as for the 2sd solution, it's esactly the same problem, except that you pulled IsSimilar out of the detection function. (but i still do have to recurse!)
as for the 2sd solution, it's esactly the same problem, except that you pulled IsSimilar out of the detection function. (but i still do have to recurse!)
No, the shapes can be found in my approach as well:
before: only start pixel is one:
00000000000000000000000000 0000000000 0000000000 00000000
00000000000000000000000000 0000000000 0000000000 00000000
00000000000000000000000000 0000000000 0000000000 00000000
00000000000010000000000000 0000000000 0000000000 00000000
00000000000000000000000000 0000000000 0000000000 00000000
00000000000000000000000000 0000000000 0000000000 00000000
00000000000000000000000000 0000000000 0000000000 00000000
first loop: up and down
00000000000000000000000000 0000000000 0000000000 00000000
00000000000010000000000000 0000000000 0000000000 00000000
00000000000010000000000000 0000000000 0000000000 00000000
00000000000010000000000000 0000000000 0000000000 00000000
00000000000010000000000000 0000000000 0000000000 00000000
00000000000010000000000000 0000000000 0000000000 00000000
00000000000000000000000000 0000000000 0000000000 00000000
second loop: left and right
00000000000000000000000000 0000000000 0000000000 00000000
00000111111111111111111111 1111111111 1100000000 00000000
00000111111111111111000000 0000000000 0000000000 00000000
00000111111111111111000000 0000000000 0000000000 00000000
00000111111111111111000000 0000000000 0000000000 00000000
00000111111111111111000000 0000000000 0000000000 00000000
00000000000000000000000000 0000000000 0000000000 00000000
third loop: up and down
00000000000000000000000000 0000000000 0000000000 00000000
00000111111111111111111111 1111111111 1100000000 00000000
00000111111111111111000000 0000111111 1100000000 00000000
00000111111111111111000000 0000011111 1100000000 00000000
00000111111111111111000000 0000001111 1100000000 00000000
00000111111111111111000000 0000000111 1100000000 00000000
00000000000000000000000000 0000000000 0000000000 00000000
forth loop: left and right
00000000000000000000000000 0000000000 0000000000 00000000
00000111111111111111111111 1111111111 1100000000 00000000
00000111111111111111000000 0000111111 1110000000 00000000
00000111111111111111000000 0000011111 1111000000 00000000
00000111111111111111000000 0000001111 1111100000 00000000
00000111111111111111000000 0000000111 1111110000 00000000
00000000000000000000000000 0000000000 0000000000 00000000
This is a way for the first of your examples. You can't stop after the second loop for those, correct but you can stop when you can't add for two consecutive loops. It gets a bit more complicated if you consider spapes like the following as a single object but still possible. But I think you won't find those with your recursion neither.
00000000000000
00111000000000
00000111100000
00000000000000
before: only start pixel is one:
00000000000000000000000000
00000000000000000000000000
00000000000000000000000000
00000000000010000000000000
00000000000000000000000000
00000000000000000000000000
00000000000000000000000000
first loop: up and down
00000000000000000000000000
00000000000010000000000000
00000000000010000000000000
00000000000010000000000000
00000000000010000000000000
00000000000010000000000000
00000000000000000000000000
second loop: left and right
00000000000000000000000000
00000111111111111111111111
00000111111111111111000000
00000111111111111111000000
00000111111111111111000000
00000111111111111111000000
00000000000000000000000000
third loop: up and down
00000000000000000000000000
00000111111111111111111111
00000111111111111111000000
00000111111111111111000000
00000111111111111111000000
00000111111111111111000000
00000000000000000000000000
forth loop: left and right
00000000000000000000000000
00000111111111111111111111
00000111111111111111000000
00000111111111111111000000
00000111111111111111000000
00000111111111111111000000
00000000000000000000000000
This is a way for the first of your examples. You can't stop after the second loop for those, correct but you can stop when you can't add for two consecutive loops. It gets a bit more complicated if you consider spapes like the following as a single object but still possible. But I think you won't find those with your recursion neither.
00000000000000
00111000000000
00000111100000
00000000000000
ASKER
ok, i got your point, but you still need recursion, else i don't understand how u can determine how many loop you need, nor the stop condition.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Idea 1)
Start from the central point and compare in a loop in one direction (up/down or left/right) until you hit the border of the surface. If both ends are known switch direction and start from all points on the line but not the boundary a next scan. After a number of direction changes the shape should be found.
Idea 2)
scan the entire image whether pixels are similar to the one you want. In the next step just find the pixel connected to the central one in the workbuf.