0
$\begingroup$

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.

$\endgroup$
1

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ @Andy Unless P=NP, it is not NP-complete. Also, please check the definition of NP-completeness and reductions. All the problems you are trying to solve are in P so, by definition, are in NP so, by definition, are reducible to any NP-complete problem. $\endgroup$ Nov 28, 2014 at 12:54
  • $\begingroup$ The problem is I m not able to reduce my above problem to NP-complete problem. Please help. $\endgroup$
    – Thanos
    Nov 28, 2014 at 13:03
  • $\begingroup$ @Andy I don't understand why you want to reduce it to an NP-complete problem but, if you insist, you're allowed a polynomial time reduction and the problem can be solved in polynomial time. So just solve the problem in the reduction and output a trivial instance. $\endgroup$ Nov 28, 2014 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.