Luồng trong mạng IV: Ứng dụng của luồng -- Network Flow IV: Flow Applications

Trong bài này, chúng ta sẽ tìm hiểu ba ứng dụng khác nhau của luồng:

  1. Tìm cặp ghép cực đại trong đồ thị hai phía không có trọng số (maximum matchings in bipartite graphs).
  2. Bài toán làm tròn ma trận (matrix rounding).
  3. Bài toán phân vùng ảnh (image segmentation).

Ba ứng dụng này nằm trong ba lĩnh vực hoàn toàn khác nhau cho chúng ta thấy bài toán luồng cực đại có tiềm năng ứng dụng rất lớn.

Cặp ghép trong đồ thị hai phía

Một đồ thị $G(V,E)$ được gọi là hai phía (bipartitie) nếu tồn tại một cách phân hoạch tập đỉnh $V$ thành hai phần $A$ và $B$ sao cho mỗi cạnh có đúng một đầu mút trong $A$ và một đầu mút trong $B$. Xem ví dụ trong Figure 1 (a). Ta thường sử dụng kí hiệu $G(A\cup B, E)$ để kí hiệu đồ thị hai phía.

bipartite-matching
Figure 1: (a) Một đồ thị hai phía và một cặp ghép trong đồ thị (b) Cặp ghép cực đại của đồ thị (c) Mạng thu được từ đồ thị ở hình (a), các cạnh vô hướng sẽ được chuyển thành hai cạnh có hướng song song ngược chiều với khả năng thông qua $1$.

Cho trước một đồ thị, ta có thể kiểm tra đồ thị đó có phải là hai phía hay không trong thời gian $O(V+E)$ bằng thuật toán BFS. Trong giới hạn của bài viết, ta sẽ không đi sau vào chi tiết thuật toán này. Về cơ bản, thuật toán dựa trên nhận xét rằng một đồ thị là hai phía khi và chỉ khi nó không chứa chu trình lẻ (odd cycle), i.e, chu trình mà số đỉnh thuộc chu trình là một số lẻ.

Một cặp ghép (matching) trong một đồ thị (không nhất thiết là hai phía) là một tập các cạnh $M \subseteq E$ sao cho không có hai cạnh nào trong $M$ có chung một đầu mút. Một cặp ghép được gọi là cực đại cực đại (maximum matching) nếu nó có kích thước (số lượng cạnh) lớn nhất trong số các cặp ghép khác nhau của đồ thị. Xem ví dụ tring Figure 1(c). Bài toán đặt ra cho chúng ta là tìm một cặp ghép cực đại trong đồ thị hai phía $G(A\cup B, E)$.

Chúng ta sẽ quy bài toán này về bài toán luồng cực đại như sau: ta định hướng các các cạnh vô hướng thành các cung từ $A$ đến $B$ và gán cho mỗi cung khả năng thông qua $1$. Ta thêm vào đồ thị hai đỉnh mới $s$ và $t$. Ta nối $s$ với mỗi đỉnh trong $A$ và nối mỗi đỉnh trong $B$ với $t$. Mỗi cung mới thêm vào đều có khả năng thông qua $1$. Gọi $G'(V',E')$ là mạng thu được sau thao tác này. Xem ví dụ trong Figure 1(c). Ta sẽ chứng minh bài toán tìm cặp ghép cực đại của $G(A\cup B, E)$ có thể được quy về bài toán tìm luồng cực đại trong $G'(V',E)$.

Theorem 1: Cặp ghép cực đại trong $G(A\cup B, E)$ có kích thước $|M|$ khi và chỉ khi luồng cực đại trong $G'(V',E')$ có giá trị $|M|$.

 
Chứng minh: Gọi $M$ là cặp ghép cực đại của $G(V,E)$. Ta sẽ chứng minh $G'(V',E')$ có một luồng $f(.)$ với giá trị $|f| = |M|$. Chiều ngược lại của định lý coi như bài tập cho bạn đọc. Ta sẽ chuyển $1$ đơn vị luồng dọc theo các cung sau:

  • Các cung $a\rightarrow b$ trong đó $a\in A, b\in B$ mà cạnh $ab$ là một cạnh nằm trong cặp ghép $M$.
  • Các cung $s\rightarrow a$ trong đó $a$ là một đỉnh trong $ A$ kề với một cạnh thuộc $M$.
  • Các cung $b\rightarrow t$ trong đó $b$ là một đỉnh trong $ B$ mà đỉnh kề với một cạnh thuộc $M$.

Ta gán luồng $0$ cho mọi cung khác của $G'$. Gọi $f'(.)$ là luồng thu được. Ta có thể dễ dàng kiểm tra được các điều kiện của luồng đối với $f'(.)$ (chi tiết coi như bài tập cho bạn đọc). Ngoài ra, có đúng $|M|$ cung đi ra khỏi $s$ là có luồng khác không vì $M$ kề với đúng $|M|$ đỉnh trong $A$. Do đó, $|f'| = |M|$.


Phân tích thời gian: Dễ thấy xây dựng $G'(V',E')$ có thể được thực hiện trong thời gian $O(V+E)$ Do $G'$ có $V+2$ đỉnh và $O(E)$ cạnh và luồng cực đại trong $G'$ có giá trị là $|M|$, áp dụng thuật toán Ford-Fulkerson, ta có thể tìm luồng cực đại trong $G'$ trong thời gian $O(|M|(V+E)) = O(VE)$.

Làm tròn ma trận

Cho một ma trận vuông $A[1,\ldots, n][1,\ldots, n]$ kích thước $n\times n$ trong đó tổng các phần tử trên mỗi hàng đều là số nguyên và tổng các phần tử trên mỗi cột cũng đều là số nguyên. Tìm một cách làm tròn ma trận $A$, bằng cách làm tròn mỗi phần tử của $A$ thành một số nguyên gần nhất sao cho tổng các hàng và cột của $A$ không thay đổi. Xem ví dụ

$\begin{bmatrix} 1.2 & 3.4 & 2.4 \\3.9 & 4.0 & 2.1 \\ 7.9 & 1.6 & 0.5 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 4 & 2 \\ 4 & 4 & 2 \\ 8 & 1 & 1 \end{bmatrix}$

Ta sẽ quy bài toán này về bài toán tìm luồng cực đại với định mức cạnh. Ta sẽ xây dựng một đồ thị $G(V,E)$ từ $A$ như sau: Ban đầu đồ thị của chúng ta rỗng.

  • Ta thêm vào đồ thị hai đỉnh $s,t$ trong đó $s$ sẽ là đỉnh phát và $t$ sẽ là đỉnh thu của $G$
  • Ta thêm vào đồ thị $n$ đỉnh $r_1,r_2,\ldots, r_n$, trong đó mỗi đỉnh $r_i$ sẽ tương ứng với hàng thứ $i$ của ma trận. Với mỗi đỉnh $r_i$, ta sẽ thêm vào đồ thị một cung $s\rightarrow r_i$ với khả năng thông qua là tổng các phần tử trên hàng thứ $i$ của ma trận $A$:

    $c(s\rightarrow r_i) = \sum_{j=1}^n A[i,j] \qquad (1)$

  • Ta thêm vào đồ thị $n$ đỉnh $c_1,c_2,\ldots, c_n$, trong đó mỗi đỉnh $c_j$ sẽ tương ứng với cột thứ $j$ của ma trận. Với mỗi đỉnh $c_j$, ta sẽ thêm vào đồ thị một cung $c_j\rightarrow t$ với khả năng thông qua là tổng các phần tử trên cột thứ $j$ của ma trận $A$:

    $c(c_j\rightarrow t) = \sum_{i=1}^n A[i,j] \qquad (2)$

  • Ta thêm vào đồ thị $n^2$ cung, mỗi cung có dạng $r_i\rightarrow c_j$, với $1 \leq i,j\leq n$. Cung $r_i\rightarrow c_j$ sẽ có khả năng thông qua là $c(r_i\rightarrow c_j) = \lceil A[i,j] \rceil$ và định mức $d(r_i\rightarrow c_j) = \lfloor A[i,j] \rfloor$.

Mọi cung khác của đồ thị sẽ có định mức là $0$. Figure 3 minh họa cho mạng xây dựng theo cách này từ ma trận ví dụ ở trên.

matrix-rounding-net
Figure 3: mạng thu được từ ma trận ví dụ ở trên.

Một luồng cực dại được gọi là luồng bão hòa nếu như mọi cung đi ra từ $s$ đều được bão hoàn, i.e, $f(s\rightarrow r_i ) = c(s\rightarrow r_i)$ với mọi $i$. Theo định lý Ford-Fulkerson, luồng bão hòa cũng là luồng cực đại của đồ thị. Ta có:

Theorem 2: Tồn tại một cách làm tròn ma trận $A$ bảo toàn tổng các hàng và cột khi và chỉ khi luồng cực đại với điều kiện định mức trong $G$ là một luồng bão hòa

 
Chứng minh: Ta sẽ phải chứng minh hai chiều của định lý. Chiều đầu tiên, ta sẽ chứng minh một cách làm tròn ma trận $A$ sẽ cho ta một luồng cực đại bão hòa trong $G$. Gọi $B$ là ma trận làm tròn của $A$. Luồng trên các cung của $G$ sẽ có giá trị tương ứng như sau:

  • Ta chuyển $f(s\rightarrow r_i) = c(s\rightarrow r_i)$ đơn vị luồng từ $s$ tới $r_i$ và chuyển $f(c_j\rightarrow t) = c(c_j\rightarrow t)$ đơn vị luồng từ $r_i$ tới $t$.
  • Với mỗi cung $r_i\rightarrow c_j$, ta chuyển $f(r_i\rightarrow c_j) = B[i,j]$ đơn vị luồng.

Dễ thấy luồng trên là một luồng bão hòa vì mọi cung đi ra từ $s$ đều được bão hòa. Ta sẽ kiểm tra luồng định nghĩa như trên là một luồng hợp lệ với định mức cạnh. Theo định nghĩa, mỗi phần tử $A[i,j]$ chỉ được làm tròn thành số nguyên gần nhất, $B[i,j] \geq \lfloor A[i,j] \rfloor$. Do đó, điều kiện định mức được thỏa mãn. Điều kiện thông qua cũng được thỏa mãn, do $B[i,j] \leq \lceil A[i,j] \rceil$. Ta chỉ còn phải kiểm tra điều kiện bảo toàn. Do ma trận làm tròn $B$ bảo toàn tổng hàng và tổng cột, luồng đi vào mỗi $r_i$ là tổng hàng thứ $i$ của $A$ và cũng chính là tổng hàng thứ $i$ của $B$. Do tổng luồng đi ra từ $i$ là tổng hàng thứ $i$ của $B$, điều kiện bảo toàn được thỏa mãn tại $r_i$. Chứng minh tương tự với mỗi $c_j$.

Chiều ngược lại, từ một luồng cực đại bão hòa của $G$, ta sẽ xây dựng ma trận làm tròn $B$ cho ma trận $A$ như sau:

$B[i,j] = f(r_i\rightarrow c_j) \qquad (3)$

Do định mức mà khả năng thông qua của $G$ đều là số nguyên, luồng trên các cung cũng là số nguyên. Do đó, ma trận $B$ là ma trận nguyên. Do tính bảo toàn luồng, tổng hàng và cột trong $A$ cũng được bảo toàn trong $B$. Các tính chất khác cần có của ma trận $B$ cũng có thể dễ dàng được kiểm tra thông qua điều kiện định mức của mạng.


Phân vùng ảnh

Trong bài toán này, đầu vào của chúng ta là một bức ảnh và ta muốn tách một đối tượng (gọi là phân vùng) trong bức ảnh ra khỏi phần khác của bức ảnh mà ta gọi chung là nền. Xem ví dụ trong Figure 4.

imge-seg
Figure 4: Tách 3 đối tượng (3 cái bút chì) ra khỏi bức ảnh. Phần tối màu đen là nền của bức ảnh. Hình được lấy từ đây.

Để đơn giản, ở đây, ta sẽ chỉ tách một (và chỉ một) đối tượng; tất cả các đối tượng khác ta đều coi là nền. Để chuyển bài toán này thành một bài toán tính toán cụ thể, ta cần phải mô hình hóa bức ảnh để biến nó thành đồ thị. Bước này cần rất nhiều kiến thức liên quan đến xử lí ảnh, do đó, mình sẽ cố gắng mô tả một cách đơn giản. Chi tiết cụ thể hơn bạn đọc có thể tham khảo tại bài báo gốc [2].

Ta sẽ coi mỗi một điểm ảnh (pixel) là một đỉnh của đồ thị $G(V,E)$. Mỗi đỉnh $v$ có hai đại lượng: $a(v)$ tương ứng với khả năng điểm $v$ thuộc đối tượng và $b(v)$ tương ứng với khả năng $v$ thuộc nền. Mỗi điểm ảnh $v$ (không thuộc phần biên ảnh) sẽ có 4 điểm ảnh kề bên. Với mỗi điểm ảnh kề bên $u$, ta sẽ có cạnh tương ứng $uv$ với trọng số $p(u,v)$. Trọng số này sẽ tương ứng với chi phí phân $u$ và $v$ vào hai vùng khác nhau, i.e, $u$ thuộc đối tượng và $v$ thuộc nền hoặc ngược lại. Làm thế nào để có được những đại lượng này từ một bức ảnh, xem phần remark ở cuối bài. Ở đây, ta giả sử đã có sẵn những đại lượng như vậy.

Ta có hai tiêu chuẩn chính khi thực hiện phân vùng ảnh:

  1. Nếu $a(v) \leq b(v)$, ta nên phân điểm ảnh $v$ thuộc đối tượng.
  2. Nếu các điểm ảnh xung quanh $v$ thuộc đối tượng thì ta nên phân $v$ vào đối tượng.

Hai tiêu chuẩn đó đưa đến việc tìm một phân hoạch $(S,T)$ của tập đỉnh $V$ sao cho $C(S,T)$ định nghĩa dưới đây đạt giá trị cực đại:

$C(S,T) = \sum_{v\in S} a(v) + \sum_{u \in T} b(u) - \sum_{uv, u \in S, v\in T}p(u,v) \qquad (4)$

Ta có thể coi tập đỉnh $S$ tương ứng với tập các điểm ảnh của đối tượng và tập đỉnh $T$ là tập các điểm ảnh thuộc nền. Đặt $M(S,T) = \sum_{v\in V} (a(v) + b(v) ) - C(S,T)$, ta có:

$M(S,T) = \sum_{v\in T} a(v) + \sum_{u \in S} b(u) + \sum_{uv, u \in S, v\in T}p(u,v) \qquad (5)$

Do $\sum_{v\in V} a(v) + b(v)$ là một hằng số, ta có thể chuyển bài toán cực đại hóa $C(S,T)$ về bài toán cực tiểu hóa $M(S,T)$. Ta sẽ quy bài toán này về bài toán tìm một lắt cắt $s,t$ với trọng số cực tiểu trong đồ thị (khác $G(V,E)$).

Nhắc lại, đồ thị hiện tại của chúng ta có tập đỉnh là tập các điểm ảnh và hai điểm ảnh kề bên $u,v$ sẽ được nối với một cạnh với trọng số $p(u,v)$. Ta sẽ biến mỗi cạnh vô hướng này thành hai cung song song $u\rightarrow v$ và $v\rightarrow u$ với cùng khả năng thông qua $p(u,v)$. Ta sẽ thêm vào đồ thị hai đỉnh $s$ và $t$. Với mỗi điểm ảnh $v$, ta thêm một cung $s\rightarrow v$ với trọng số $a(v)$ và một cung $v\rightarrow t$ với trọng số $b(v)$. Gọi đồ thị thu được là $G(V',E')$. Xem minh họa trong Figure 6.

image-seg-net
Figure 6: Mạng thu được trong bài toán phân vùng ảnh.

Theorem 3: Gọi $(X,Y)$ là một lát cắt $(s,t)$ trong $G'(V',E)$ với khả năng thông qua tương ứng là $c(X,Y)$. Gọi $(S,T)$ là lát cắt tương ứng trong $G$, với $S = V\cap X$ và $T = V\cap Y$. Ta có:

$c(X,Y) = M(S,T) \qquad (6)$

 
Chứng minh: Chú ý, lát cắt $(X,Y)$ là lát cắt trong đồ thị $G'$ có hướng còn lát cắt $(S,T)$ là lát cắt trong đồ thị $G$ vô hướng. Theo định nghĩa:

$c(X,Y) = \sum_{u\in X}\sum_{v\in Y} c(u\rightarrow v)$

Từ định nghĩa, nếu ta có hai cung song song $u\rightarrow v$ và $v\rightarrow u$ với cùng khả năng thông qua, ở đây $ u\in X, v\in Y$, thì ta chỉ tính khả năng thông qua của cung $u\rightarrow v$ trong $c(X,Y)$. Dựa vào định nghĩa của $G'(V',E')$, đại lượng $\sum_{v\in T} a(v)$ chính là tổng khả năng thông qua của các cung từ $s$ tới các đỉnh trong $T$ và $\sum_{v\in S} b(v)$ chính là khả năng thông qua của các đỉnh từ $S$ tới $t$. Do đó $c(X,Y) = M(S,T)$.


Theorem 3 cho chúng ta biết, để tìm phân hoạch $(S,T)$ của bức ảnh thỏa mãn $ M(S,T)$ cực tiểu, ta chỉ việc tìm một lát cắt $(s,t)$ cực tiểu trong đồ thị $G(V',E')$. Lát cắt này có thể tìm bằng cách tìm một luồng cực đại từ $s$ tới $t$, theo định lý Ford-Fukerson.

Remark: Trong phần này, mình sẽ lượt qua ngắn gọn cách thu được $a(.), b(.), p(.,.)$ như mô tả ở trên. Về mặt trực quan, đại lượng $p(.,.)$ đặc trưng cho độ tương tự giữa hai điểm ảnh. Nếu hai điểm ảnh $u,v$ càng tương tự nhau, $p(u,v)$ càng lớn, và như vậy, chi phí phân $u,v$ vào hai vùng khác nhau càng cao. Ví dụ, trong [2], tác giả chọn $p(u,v) = e^{-c(I_u - I_v)^2}$, với $c$ là một hằng số dương và $I_u,I_v$ là cường độ tại hai điểm ảnh $u,v$, là một hàm thỏa mãn tiêu chí như vậy. Để thu được $a(.)$ ($b(.)$ ta làm tương tự), ta có thể cố định một số điểm ảnh trên ảnh thuộc đối tượng. Hay nói cách khác, ta chọn một số điểm ảnh và cho $a(v) = 1$ với những điểm ảnh này. Với các điểm ảnh khác, ví dụ $w$, ta sẽ gán $a(w)$ tỉ lệ với độ tương tự (trung bình) giữa $w$ và các điểm ảnh mà ta đã chọn sẵn thuộc đối tượng. Về mặt trực quan, ta càng cố định nhiều điểm thuộc đối tượng (giả sử các điểm đó đúng là đối tượng), thì khả năng ta gán $a(.)$ cho các điểm ảnh càng chính xác. Figure 5 dưới đây là ví dụ về chất lượng phân vùng sử dụng thuật toán trên với các điểm ảnh chọn thuộc đối tượng khác nhau.

segmentation-accuracy
Fiugre 5: Độ chính xác của thuật toán phân vùng khi nhiều điểm được đánh dấu là thuộc đối tượng/nền. Hình lấy từ [2].

Tham khảo

[1] J. Erickson. Applications of Max Flow Lecture Notes, UIUC, Fall 2013.
[2] Y. Boykov and G. Funka-Lea. Graph Cuts and Efficient ND Image Segmentation. International Journal of Computer Vision 70.2 (2006).
[3] K. Wayne. Applications of Max Flow Slides, Princeton, Spring 2001.

Facebook Comments

Tags: , , , ,

Reply

Your email address will not be published. Required fields are marked *