<p>Some computer vision problems rely on cliques and max cliques, which can be reduced to SAT.</p>

CC BY-SA 2.5
2010-10-01T12:02:33.010Z
Very interesting, I didn't know that. Do you have links to any document showing such a connection between computer vision problems and clique/max-clique?
Giorgio Camerani
CC BY-SA 2.5
2010-10-01T12:11:16.010Z
One is: http://arxiv.org/abs/1009.4823. Some people refer to D.H. Ballard and M. Brown, Computer Vision, Prentice-Hall, Englewood Cliffs, N.J. 1982.
Dave Clarke
CC BY-SA 2.5
2010-10-02T15:57:14.460Z
The link with maximum clique is usually via the microstructure of the constraint satisfaction problem that underlies the problem.  Specifically, the partial solutions of the problem correspond to cliques in the microstructure; the maximum clique then corresponds to a solution.
András Salamon
CC BY-SA 2.5
2010-10-01T10:40:52.693Z
2010-10-01T10:40:52.693Z
Dave Clarke
<p>Many problems in computer vision are naturally expressed as <a href="http://en.wikipedia.org/wiki/Constraint_satisfaction">constraint satisfaction problems</a>.  There is a history going back several decades of applying constraint programming to such problems.  One of the key early papers in constraint satisfaction was completely motivated by problems from computer vision.</p>

<ul>
<li>Ugo Montanari, <em>Networks of constraints: Fundamental properties and applications to picture processing</em>, Information Sciences <strong>7</strong> 95–132, 1974. doi: <a href="http://dx.doi.org/10.1016/0020-0255%2874%2990008-5">10.1016/0020-0255(74)90008-5</a></li>
</ul>

<p>See this book for a recent overview of the application of constraints to particular problems in computer vision.</p>

<ul>
<li>Martin Cooper, Line Drawing Interpretation. Springer-Verlag, 2008. <a href="http://www.springer.com/book/978-1-84800-228-9">(publisher's site)</a></li>
</ul>

<p>If you really do want SAT and would like to avoid constraint satisfaction, then you can translate the constraint formulation into SAT, either manually or using an automated translation tool like <a href="http://bach.istc.kobe-u.ac.jp/sugar/">Sugar</a>.  Note that Chapter 2 of the recent <a href="http://www.st.ewi.tudelft.nl/sat/handbook/">Handbook of Satisfiability</a> claims that it is common to first express one's problem as a constraint satisfaction problem, and only then to translate this formulation to SAT.  So constraint satisfaction should probably be considered even when one wants to work with SAT.</p>

<p>There is one big advantage of staying within a more expressive paradigm.  The constraint satisfaction framework allows the use of interval and numeric constraints.  These often occur in computer vision, but can lead to SAT instances that are infeasibly large.  Specialised constraint solvers may be greatly preferable to SAT solvers in such cases.</p>

<p>(A final aside: I have heard that the computer vision community tends not to be aware of constraint satisfaction approaches, and that this has led to the reinvention of well-known constraints techniques and results.  I do not know if this is a correct assessment, but if it is, then it would be worth translating constraints results to the terminology and specific concerns of computer vision.)</p>

CC BY-SA 2.5
2010-10-02T16:01:04.157Z
Montanari  has done image processing work, too. That man has done everything.
Dave Clarke
CC BY-SA 2.5
2010-10-04T07:34:12.823Z
Thank you for this very interesting answer. As soon as I'll become a registered user, I'll vote it up.
Giorgio Camerani
CC BY-SA 2.5
2010-10-02T15:54:07.303Z
2010-10-02T18:42:36.097Z
2010-10-02T18:42:36.097Z
András Salamon
<p>Could anyone please point to both introductory and advanced papers/books showing how to use SAT technology to solve Computer Vision tasks (e.g. edge detection, object recognition, facial recognition, ...)?</p>

<p>More precisely: I'm looking for SAT-based techniques to extract knowledge from images and reason about such knowledge (e.g. is object $X_1$ in front of object $X_2$? Is object $X_3$ partially hidden by object $X_4$? Is person $X_5$ in image $I_1$ the same as person $X_6$ in image $I_2$?).</p>

CC BY-SA 2.5
2010-10-01T10:50:32.760Z
@supercooldave: Hi Dave, I've seen your answer about clique and max-clique. I was about to write a comment on that, but your answer disappeared.
Giorgio Camerani
CC BY-SA 2.5
2010-10-01T11:09:29.877Z
When the question changed, I thought my comment became irrelevant.
Dave Clarke
<ds.algorithms><sat><ai.artificial-intel><cv.computer-vision>
Using SAT for Computer Vision tasks
Giorgio Camerani
# Using SAT for Computer Vision tasks

(Asked by: username_0 on 2010-10-01)

Could anyone please point to both introductory and advanced papers/books showing how to use SAT technology to solve Computer Vision tasks (e.g. edge detection, object recognition, facial recognition, ...)?

More precisely: I'm looking for SAT-based techniques to extract knowledge from images and reason about such knowledge (e.g. is object $X\_1$ in front of object $X\_2$? Is object $X\_3$ partially hidden by object $X\_4$? Is person $X\_5$ in image $I\_1$ the same as person $X\_6$ in image $I\_2$?).

**Tags:** ds.algorithms, sat, ai.artificial-intel, cv.computer-vision
> **Comments:**
> **username_0**: @supercooldave: Hi Dave, I've seen your answer about clique and max-clique. I was about to write a comment on that, but your answer disappeared.  
> **username_1**: When the question changed, I thought my comment became irrelevant.  

---

## 2 answers

### Answer by username_2 on 2010-10-02. Score: 6 | Accepted answer

Many problems in computer vision are naturally expressed as [constraint satisfaction problems](http://en.wikipedia.org/wiki/Constraint_satisfaction). There is a history going back several decades of applying constraint programming to such problems. One of the key early papers in constraint satisfaction was completely motivated by problems from computer vision.

* Ugo Montanari, *Networks of constraints: Fundamental properties and applications to picture processing*, Information Sciences **7** 95–132, 1974. doi: [10.1016/0020-0255(74)90008-5](http://dx.doi.org/10.1016/0020-0255%2874%2990008-5)

See this book for a recent overview of the application of constraints to particular problems in computer vision.

* Martin Cooper, Line Drawing Interpretation. Springer-Verlag, 2008. [(publisher's site)](http://www.springer.com/book/978-1-84800-228-9)

If you really do want SAT and would like to avoid constraint satisfaction, then you can translate the constraint formulation into SAT, either manually or using an automated translation tool like [Sugar](http://bach.istc.kobe-u.ac.jp/sugar/). Note that Chapter 2 of the recent [Handbook of Satisfiability](http://www.st.ewi.tudelft.nl/sat/handbook/) claims that it is common to first express one's problem as a constraint satisfaction problem, and only then to translate this formulation to SAT. So constraint satisfaction should probably be considered even when one wants to work with SAT.

There is one big advantage of staying within a more expressive paradigm. The constraint satisfaction framework allows the use of interval and numeric constraints. These often occur in computer vision, but can lead to SAT instances that are infeasibly large. Specialised constraint solvers may be greatly preferable to SAT solvers in such cases.

(A final aside: I have heard that the computer vision community tends not to be aware of constraint satisfaction approaches, and that this has led to the reinvention of well-known constraints techniques and results. I do not know if this is a correct assessment, but if it is, then it would be worth translating constraints results to the terminology and specific concerns of computer vision.)

> **Comments:**
> **username_1**: Montanari  has done image processing work, too. That man has done everything.  
> **username_0**: Thank you for this very interesting answer. As soon as I'll become a registered user, I'll vote it up.  

---

### Answer by username_1 on 2010-10-01. Score: 3

Some computer vision problems rely on cliques and max cliques, which can be reduced to SAT.

> **Comments:**
> **username_0**: Very interesting, I didn't know that. Do you have links to any document showing such a connection between computer vision problems and clique/max-clique?  
> **username_1**: One is: http://arxiv.org/abs/1009.4823. Some people refer to D.H. Ballard and M. Brown, Computer Vision, Prentice-Hall, Englewood Cliffs, N.J. 1982.  
> **username_2**: The link with maximum clique is usually via the microstructure of the constraint satisfaction problem that underlies the problem.  Specifically, the partial solutions of the problem correspond to cliques in the microstructure; the maximum clique then corresponds to a solution.  

---

