Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
In image processing I have a black and white image which is represented by matrix {0,1}, I have to find blob (a region of connected pixels) in it. I'm confused, can this problem be reduced to Constraint Satisfaction problem (as p/np complete)?
Black and white image with white blobs.
The constraint satisfaction problem (CSP) is NP-complete. Identifying blobs is a question about graph connectivity which is in P. Therefore, yes, the question you're asking reduces to CSP but this doesn't tell you anything useful: it just says that CSP is at least as hard as this problem but it might be harder. (In fact, it is strictly harder if P$\neq$NP.) Since your problem is in P, it is not (believed to be) NP-complete.
A related question is whether the problem can be expressed directly as a CSP without needing a reduction.
If a blob is any connected region then, in particular, any blob contains two adjacent pixels and any two adjacent pixels are part of a blob. Therefore, if all you want to know is whether an image contains at least one blob, this is a constraint satisfaction problem.
However, if you want to identify a whole blob (e.g., output a list of all the pixels within some blob) or identify or count all the blobs, the problem is no longer a CSP. The reason for this is that CSPs are not able to express connectivity conditions: there is no CSP in a finite constraint language that says "This graph is connected" because every instance of CSP is equivalent to a first-order formula and first-order logic can't tell the difference between connected and disconnected graphs.
