C / C++ / MFC

29-Apr-04 20:45

I have a BYTE array of pixels, which describes am image. Image is black - white. Pixels have 255 and 0 values. If pixels are white - this is object, black - background. I wanna know sizes and locations of all objects on image.
If i use standart recursive floodfill algorithm for every object by turns it takes too much time to scan whole image, find object, use to object floofill and to get size and location of the object.
Do anybody know fast algoritmh for simultaneously detecting of all objects on image(BYTE array)?

John R. Shaw30-Apr-04 10:55

30-Apr-04 10:55

I am not sure what you mean by "sizes and locations of all objects on image", but I tried to give as many examples of floodfill types as I could in the article QuickFill.

INTP

Kolich4-May-04 19:11

4-May-04 19:11

Yes, I've read your article, it's really good. But QuickFill
makes floodfill only of one object. So, to fill 10 objects on the image i need to call quickfill 10 times. I wanna to fill theese 10 objects simultaneously, in 1 call. Because if
i 10 times look for object, then fill them it takes too much time.

John, i find 1 interesting thing. When i testing your programm, Opera brouser worked. And filling of one object takes 8 milliseconds. When i closing Opera, filling of 1 object takes 23 millisecondes Smile | :)

John R. Shaw4-May-04 20:52

4-May-04 20:52

Well, filling multiple object simultaneously would require a great deal more work and would provide no speed improvement (in fact it would slow the whole process down). Although it would look great, if you actualy were seeing the objects filling.

Now this could be accomplished by using some sort of stepping where you remove the while loop in the quickfill function and have it return whether or not it is finished after each call. This would require some flag to note if it is the first time the function is called or some sort of initialization function that must be call first; in other word it would have to rember it's state. No matter how you approach the problem you are still dealing with multiple objects.

Now as for giving the illustion of them all being filled simultaneously, that should not be to difficult. You simply call quickfill 10 times but do not display the results until after all 10 are filled.

If speed becomes a problem, then modify quickfill to take a CDibData object insted so that one will not need to be created each time quickfill is called. Then copy the result back to the original bitmap, after filling it is complete. This, of cource, assumes that the objects you are refering to are graphic objects that are all located on the same bitmap.

The only advantage you have using quickfill is that you have the code to modify as you see fit. If you are developing for the desktop then the illusion of simultaneously filling can be accomplished as stated above using FloodFill.

I could do what you are attemping, by using one of the methods stated above. Just rember the key is the quickfill function, if you understand that then you can almost ignore the helper functions.

No matter how you slice it someone has to write the function to fill all those objects, and that appears to be you.

Good Luck!

P.S. As for the Opera thing I can only ass-u-me that your machine was busy doing something else.

INTP

Kolich4-May-04 22:23

4-May-04 22:23

Essentialy i do not need to fill objects. I need to know sizes and locations of objects in image. Image is an array of pixels (BYTE).
I need simething like this:
http://rsb.info.nih.gov/ij/docs/menus/analyze.html
But here is too compound system and its makes too much unuseless calculations. And sources are on Java, and I wanna use it in vc++.
This system find all object in one cycle, so its very quick.

P.S. no, no more processes except quickfill and opera. i think its becouse memory in windows assignes in such way.

John R. Shaw5-May-04 9:03

5-May-04 9:03

Sounds more like a simple line scan algorithm of some sort is needed, something to how you would fill a polygon (only without knowing where the edges are first.

METHOD 1:

First you'll need a storage item something like the following:

struct bucket
{
    int x1, x2;
    struct bucket* pNext;
};

Then create an array equal to the height of the image:

bucket* pLineArray = new bucket[height];

Now start scanning at the upper left courner. When you encounter an leading edge: create a new bucket

pBucket = new bucket;
memset(pBucket,0,sizeof(bucket);

and store the location in x1 (left side of edge). Next skip over the edge, then scan until you reach the next edge. Now find the trailing edge (right side of edge) and store that in x2. Insert the bucket in the list at the current line.

void AddBucket(int nLine, bucket* pBucket)
{
    bucket* pNext;
    pNext = pLineArray[nLine];
    if( !pNext )
        pLineArray[nLine] = pNext
    else {
        while( pNext->pNext )
            pNext = pNext->pNext;
        pNext = pBucket;
    }
}

Continue to scan the line adding new buckets as you go.
NOTE: The top and bottom of each object are special cases where the left and right edges are the same (Example: a single pixel at top would contain the same values for x1 and x2.

Repeat the above for each line in the image.

Now that the information stored you can write a function to analyse the information to produce a line list for each of the individual objects.

METHOD 2:

Simulare to method 1, accept that when you encounter an edge you trace all the way around the object, storing the infomation in its own line list. Then exclude that region from futhur scanning.

This method requires multiple scans and that you maintian a list of line lists.

FINALY:
Method 1 will store the information in one pass, but requires futher anasyse to produce the final information (list of line lists).
Method 2 will probably be slower, but may be easier to code.

In either method, you would have one top level function that would be called and return a list of line lists.

I do not know if my ideas help! I do hope they give you some idea of whats envoled.

Recommend reading:
"Computer Graphics: Principles and Practice in C (2nd Edition)".
"Graphics Programming" by Michael Abrash.
The Graphics Gems books, much of the code in these books are available online.

Good Luck!

INTP

Kolich6-May-04 20:10

6-May-04 20:10

Thanx a lot. Problem is solved.

Now problem is in Gaussing blur. It takes 120 ms for 720*575 image. We wana it takes not more than 40-50 ms. I think only assembler realisation of algorithm can improve performance.

John R. Shaw8-May-04 4:49

Call another program from my project ??

8-May-04 4:49

The best graphics library I know of for speed is Fastgraph by Ted Gruber Software, Inc., written in hand-optimized assembly language.

The algorithm I originaly designed (in C) used assembly level routines (direct video access via hardware support) to read/write the pixel data, that is where the main bootleneck is. It was not intended to be used for image proccessing, but for simple fills like that used by the paint program that comes with Windows.

INTP

VK code for subtract

Tyrus18229-Apr-04 20:24

Tyrus182

29-Apr-04 20:24

Hi i am looking for the VK code for the subtract key on the main part of the keyboard not the number pad i need to capture both but i can only find the code for the one on the number pad any help you can provide is appreciated thanks

Re: VK code for subtract

ohadp29-Apr-04 21:05

ohadp

29-Apr-04 21:05

Spy++ says it's VK_OEM_MINUS

Third party toolbar

*Dreamz29-Apr-04 20:01

*Dreamz

29-Apr-04 20:01

Hi
Can we load a third party toolbar into our application.
Eg: I have a view class derived from CHtmlView.How can i load the additional toolbars downloaded for the Internet explorer.

Thanks Smile | :)

Re: Third party toolbar

nguyenvhn29-Apr-04 20:48

nguyenvhn

29-Apr-04 20:48

As my knowledge, you need 2 toolbars. One supplied by MFC framework, and the other supplied by yourself. If so, read bellow. If not, leave now.

In CMainFrame, create a CToolBar member variable, for example, it may be CToolBar m_tbNew;.
In CMainFrame::OnCreate, add the following code:

<br />
m_tbNew.CreateEx(this, TBSTYLE_FLAT, WS_CHILD | WS_VISIBLE | CBRS_TOP | CBRS_GRIPPER | CBRS_TOOLTIPS | CBRS_FLYBY | CBRS_SIZE_DYNAMIC, CRect(0,0,0,0), ID_NEW_TOOLBAR);<br />
m_tbNew.SetWindowText("Caption here");<br />
m_tbNew.LoadToolBar(IDR_NEW_TOOLBAR_RESOURCE);<br />
m_tbNew.EnableDocking(CBRS_ALIGN_ANY);<br />
DockControlBar(&m_tbNew);<br />

The second toolbar will show beside default toolbar.
Good luck.

Re: Third party toolbar

*Dreamz2-May-04 18:15

*Dreamz

2-May-04 18:15

Thanks for your reply.
And i wanted to know that can we load the Google toolbar or Yahoo Toolbar into our application.

Thanks Smile | :)

Mughi29-Apr-04 19:45

Mughi

29-Apr-04 19:45

I have Help->Contents menu in my project. And I have a help.hlp file.

What I need is : On click of the contents menu, I need to display this help.hlp file. How do i do it ??

Could someone help me on this, please. I thank in advance.

Mughi

GermanGeorge29-Apr-04 22:16

GermanGeorge

29-Apr-04 22:16

::WinHelp(0,".\\MY.HLP",HELP_CONTEXT,19028);

Mughi29-Apr-04 22:49

Mughi

29-Apr-04 22:49

Its working.
Thanks for your support.
And by the way, I would like to know on how to run any other program, not only HLP files but also to invoke other files like documents, executables, etc.,
Once again, I thank you for your support.

GermanGeorge29-Apr-04 23:15

GermanGeorge

29-Apr-04 23:15

there are two ways:
if you do NOT need control over the other programm use
WinExec

if you need the control, to determine, wheter the other programm is still running use
CreateProcess / OpenProcess / WaitForSingleObject

Mughi2-May-04 19:05

Mughi

2-May-04 19:05

thanks for your support
cheers