Image Segmentation andconvex hull compuation

1

Artificial picture constructed from the segmented images

2

3

4

5

A popular automated system: SNAKES

Input initial boundary curve (rubber-band)
The rubber-band shrinks to capture the region boundary

Question: Can we solve the problem as a simple
mathematical problem?
6

History• Goes back to 1994 (15 years ago)
• Tetsuo Asano, Naoki Katoh, and I
tried to formulate and solve theimage segmentation problem asa geometric optimization problem• Surprisingly, convex hull plays animportant role.

7

Image segmentation problem• G = n x n pixel grid (for example, n =1024)• A digital picture is a function f (x) on G torepresent brightness/color of each pixel x– f(x) is real valued (monochromatic picture)• In RGB space for color pictures• Object image is a subset S of G torepresent an object in the picture.
• Image segmentation: Clip the object image
8

Our formulation• Approximation by two-valued function– Picture: function f from G to real values– Find the L2 nearest two-valued function g to fg ( p ) = ag ( p ) = b( p ∈( p ∉R )R )Imagebackground

Minimize || f – g ||2• a and b become average values μ(R) and μ (G-R) off(p) in R and G-R, respectively.

• That is, minimize the intraclass variance
Var ( R)=∑ p∈R ( f ( p) − μ ( R)) 2 + ∑ p∈G − R ( f ( p ) − μ (G − R)) 29

Intraclass variance minimization
Var ( R)=∑ x∈R ( f ( x) − μ ( R)) 2 + ∑ x∈G − R ( f ( x) − μ (G − R)) 2• Easy if R can be arbitrary (disconnected) region.
•Least-square threshold selection (Ohtsu, 1978)•Collect pixels brighter than a threshold θ• Reasonable formulation: Give a family F of regionsof good shapes, and find R ∈ F minimizing Var (R)

10

11

12

13

Typical Region Families
X-monotone

Based x monotone

Rectilinear Convex

X-monotone: Intersection with any vertical line is asegment. (bounded by two x-monotone chains)
Based (x-)monotone: Region bounded by a monotone
chain and a baseline (x-axis)
Rectilinear Convex: X-monotone and Y-monotone region.
14

Solution (Asano-Chen-Katoh-T 96)•Idea :
– If we fix the number k= |R| of pixels in R, Var(R) is∑

minimized if the sum f (R) =p∈Rf ( p) is maximized (orminimized).
• To compute such R is NP-hard even for the base monotone regions– Because Var (R) has convexity, we can use convex hullcomputation to solve it.

15

Convex hull computation• Consider S = {(|R|, f(R)): R ∈F}.
• F has an exponential number ofregions in general• Thus, we cannot compute S• Fortunately, CH(S) has at most
N=n2 points

RBrightness sum f( R )– Output size is small.

• Var(R) is maximized at a point on
CH(S) (by its convexity)• Problem: How can we computeCH(S) without knowing S explicitly
Region size |R|16

Convex hull computation by “touching” it•RBrightness sum f( R )Compute CH(S) by finding all thetangent points– Recall points are (|R|, f( R))– Tangent line: y –t x = c• Maximizing f*( R ) = f (R)– t |R|finds a tangent point with slope t– f*(R) = Σ p ∈R f*(p) , where
f*(p) = f(p) – t– We can find all necessary
slopes by touching O(N) times.
(works even in high dimensions)Region size |R|17

Systematic way of “touching”
Brightness sum f( R )Region size |R|
18

The problem we need to solve
Maximum weight region problem:
Given a function f*(p) on G, find the region
R in the region family Ｆ maximizing f* (R)History: Programming Pearls (1984), column 8(J. Bentley’s famous column CACM)• How to solve it if F is• the family of all rectangles• the family of all intervals in the onedimensional array19

Maximum weight region
Maximum weight region problem:
Given a function f*(p) on G, find the region
R in the region family Ｆ maximizing f* (R)X-monotone

Easy to solve if F is the family of• Based x-monotone regions• (Connected) x-monotone regions• Rectilinear convex regions
NP-hard for the family of all connected regions

20

21

I was lucky to find unexpected
applications and extensions•Data Mining Application: Optimized Numeric Association Rules(SIGMOD 96 ,VLD96,98, KDD 97 )SONAR
(System for Optimized Numeric Association Rules)

Find a rule to detect unreliable
customers using a customer
database(Age, Balance) ∈ Ｒ⇒ (CardLoanDelay = yes)

22

Pyramid approximation and layered rule
(Chun-Sadakane-T 03, Chen-Chun-Katoho-T 04)
Instead of two-valued function, we can construct theoptimal multilayer function to approximate the input f.

23

Remained problems• The region families are very special• How to deal with more flexible regions– A region consisting of a few basic shapes– Convex region, Star-shaped region

24