Cheap and Secure Web Hosting Provider : See Now

[Solved]: Blob detection as Constraint satisfaction problem?

, , No Comments
Problem Detail: 

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)?

Typical Example with white blobs

Black and white image with white blobs.

Asked By : Thanos

Answered By : David Richerby

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.

Best Answer from StackOverflow

Question Source :

 Ask a Question

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback