ปัญหา การแบ่งส่วนภาพเกี่ยวข้องกับการแบ่งภาพออกเป็นหลายส่วนตามเกณฑ์ความสม่ำเสมอ บทความนี้เน้นที่วิธีการทางทฤษฎีกราฟในการแบ่งส่วนภาพโดยใช้การแบ่งกราฟผ่าน การตัดขั้นต่ำหรือ การ ตัดสูงสุดการจัดหมวดหมู่ของวัตถุตามการแบ่งส่วนภาพสามารถมองได้ว่าเป็นกรณีเฉพาะของการจัดกลุ่มสเปกตรัม ที่นำมา ประยุกต์ใช้กับการแบ่งส่วนภาพ

• การบีบอัดภาพ
  • แบ่งภาพออกเป็นส่วนประกอบที่มีลักษณะเหมือนกัน และใช้อัลกอริธึมการบีบอัดที่เหมาะสมที่สุดสำหรับแต่ละส่วนประกอบเพื่อปรับปรุงคุณภาพการบีบอัด
• การวินิจฉัยทางการแพทย์
  • การแบ่งส่วนภาพ MRI โดยอัตโนมัติเพื่อระบุบริเวณที่เป็นมะเร็ง
• การทำแผนที่และการวัด
  • การวิเคราะห์ ข้อมูล การสำรวจระยะไกลจากดาวเทียมโดยอัตโนมัติ เพื่อระบุและวัดพื้นที่ที่สนใจ
• การขนส่ง
  • การแบ่งเครือข่ายการขนส่งทำให้สามารถระบุภูมิภาคที่มีสถานะการจราจรที่สม่ำเสมอได้^{[ 1 ]}

เซตของจุดในปริภูมิคุณลักษณะใดๆ สามารถแสดงได้ในรูปของกราฟสมบูรณ์แบบไม่มีทิศทางที่มีน้ำหนัก G = (V, E) โดยที่โหนดของกราฟคือจุดในปริภูมิคุณลักษณะ น้ำหนักของขอบเป็นฟังก์ชันของความคล้ายคลึงกันระหว่างโหนด V และE ในบริบทนี้ เราสามารถกำหนดปัญหาการแบ่งส่วนภาพเป็นปัญหาการแบ่งส่วนกราฟที่ต้องการการแบ่งเซตของจุดยอด V โดยที่ตามมาตรวัดบางอย่าง จุดยอดในเซตใดๆจะมีความคล้ายคลึงกันสูง และจุดยอดในสองเซตที่แตกต่างกันจะมีความคล้ายคลึงกันต่ำ ${\displaystyle w_{ij}}$${\displaystyle (i,j)\in E}$${\displaystyle i}$${\displaystyle j}$${\displaystyle V_{1},\cdots ,V_{k}}$${\displaystyle V}$${\displaystyle V_{i}}$${\displaystyle V_{i},V_{j}}$

ให้G = ( V , E , w ) เป็นกราฟถ่วงน้ำหนัก และให้และเป็นเซตย่อยของจุดยอดสองเซต ${\displaystyle A}$${\displaystyle B}$

อนุญาต:

${\displaystyle w(A,B)=\sum \limits _{i\in A,j\in B}w_{ij}}$

${\displaystyle \operatorname {ncut} (A,B)={\frac {w(A,B)}{w(A,V)}}+{\frac {w(A,B)}{w(B,V)}}}$

${\displaystyle \operatorname {nassoc} (A,B)={\frac {w(A,A)}{w(A,V)}}+{\frac {w(B,B)}{w(B,V)}}}$

ในแนวทางการตัดแบบปกติ^{[ 2 ]}สำหรับการตัดใดๆในจะวัดความคล้ายคลึงกันระหว่างส่วนต่างๆ และวัดความคล้ายคลึงกันทั้งหมดของจุดยอดในส่วนเดียวกัน ${\displaystyle (S,{\overline {S}})}$${\displaystyle G}$${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$${\displaystyle \operatorname {nassoc} (S,{\overline {S}})}$

เนื่องจากการตัดที่ทำให้ค่าต่ำสุดจะทำให้ค่าสูงสุดด้วยเช่นกัน ${\displaystyle \operatorname {ncut} (S,{\overline {S}})=2-\operatorname {nassoc} (S,{\overline {S}})}$${\displaystyle (S^{*},{\overline {S}}^{*})}$${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$${\displaystyle \operatorname {nassoc} (S,{\overline {S}})}$

การคำนวณหาค่า cut ที่ทำให้ค่าต่ำสุดนั้นเป็น ปัญหา NP-hardอย่างไรก็ตาม เราสามารถหาค่า cut ที่มีน้ำหนักมาตรฐานน้อยได้ ในเวลาพหุนาม โดยใช้เทคนิคเชิงสเปกตรัม ${\displaystyle (S^{*},{\overline {S}}^{*})}$${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$${\displaystyle (S,{\overline {S}})}$${\displaystyle \operatorname {ncut} (S,{\overline {S}})}$

อนุญาต:

${\displaystyle d(i)=\sum \limits _{j}w_{ij}}$

นอกจากนี้ ให้Dเป็นเมทริกซ์แนวทแยงที่มีบนแนวทแยง และให้เป็นเมทริกซ์สมมาตรที่ มี${\displaystyle n\times n}$${\displaystyle d}$${\displaystyle W}$${\displaystyle n\times n}$${\displaystyle w_{ij}=w_{ji}}$

หลังจากทำการคำนวณทางพีชคณิตแล้ว เราจะได้:

${\displaystyle \min \limits _{(S,{\overline {S}})}\operatorname {ncut} (S,{\overline {S}})=\min \limits _{y}{\frac {y^{T}(D-W)y}{y^{T}Dy}}}$

ภายใต้ข้อจำกัดดังต่อไปนี้:

• ${\displaystyle y_{i}\in \{1,-b\}}$สำหรับค่าคงที่บางค่า${\displaystyle -b}$
• ${\displaystyle y^{t}D1=0}$

การหาค่าต่ำสุดภาย ใต้ข้อจำกัดข้างต้นเป็นปัญหาNP-hardเพื่อให้ปัญหานี้สามารถแก้ไขได้ เราจึงผ่อนคลายข้อจำกัดของและอนุญาตให้มีค่าเป็นจำนวนจริง ปัญหาที่ผ่อนคลายแล้วสามารถแก้ไขได้โดยการแก้ปัญหาค่าลักษณะเฉพาะทั่วไปสำหรับค่าลักษณะเฉพาะทั่วไปที่เล็กที่สุดเป็นอันดับสอง ${\displaystyle {\frac {y^{T}(D-W)y}{y^{T}Dy}}}$${\displaystyle y}$${\displaystyle (D-W)y=\lambda Dy}$

อัลกอริทึมการแบ่งพาร์ติชัน:

1. เมื่อกำหนดชุดคุณลักษณะแล้ว ให้สร้างกราฟถ่วงน้ำหนักคำนวณน้ำหนักของแต่ละขอบ และสรุปข้อมูลในและ${\displaystyle G=(V,E)}$${\displaystyle D}$${\displaystyle W}$
2. จงหาเวกเตอร์ลักษณะเฉพาะที่มีค่าลักษณะเฉพาะที่เล็กที่สุดเป็นอันดับสอง${\displaystyle (D-W)y=\lambda Dy}$
3. ใช้เวกเตอร์ลักษณะเฉพาะที่มีค่าลักษณะเฉพาะที่เล็กที่สุดเป็นอันดับสองในการแบ่งกราฟออกเป็นสองส่วน (เช่น การจัดกลุ่มตามเครื่องหมาย)
4. พิจารณาว่าควรแบ่งพาร์ติชันปัจจุบันออกเป็นส่วนย่อยอีกหรือไม่
5. หากจำเป็น ให้แบ่งส่วนย่อยที่แยกไว้แล้วออกเป็นส่วนย่อยแบบเรียกซ้ำ

การแก้ปัญหาค่าลักษณะเฉพาะมาตรฐานสำหรับเวกเตอร์ลักษณะเฉพาะทั้งหมด (โดยใช้อัลกอริธึม QRเป็นต้น) ใช้เวลานาน ซึ่งไม่เหมาะสมสำหรับการใช้งานการแบ่งส่วนภาพ เนื่องจากจำนวนพิกเซลในภาพนั้นมีค่ามาก ${\displaystyle O(n^{3})}$${\displaystyle n}$

เนื่องจากอัลกอริธึมแบบไม่ตัดใช้เพียงเวกเตอร์ลักษณะเฉพาะตัวเดียว ซึ่งสอดคล้องกับค่าลักษณะเฉพาะทั่วไปที่เล็กที่สุดเป็นอันดับสอง ประสิทธิภาพจึงสามารถปรับปรุงได้อย่างมากหากแก้ปัญหาค่าลักษณะเฉพาะที่เกี่ยวข้องในลักษณะที่ไม่ต้องใช้เมทริกซ์กล่าวคือ โดยไม่ต้องจัดการหรือคำนวณเมทริกซ์ W อย่างชัดเจน เช่น ใน อัลกอริ ธึม Lanczos วิธีการที่ไม่ต้องใช้เมทริกซ์ต้องการเพียงฟังก์ชันที่ทำการคูณเมทริกซ์กับเวกเตอร์สำหรับเวกเตอร์ที่กำหนดในแต่ละรอบการทำงาน สำหรับการแบ่งส่วนภาพ เมทริกซ์ W มักจะเป็นเมทริกซ์เบาบางที่มีจำนวนรายการที่ไม่เป็นศูนย์จำนวนมากดังนั้นการคูณเมทริกซ์กับเวกเตอร์ดังกล่าวจึงใช้เวลานาน ${\displaystyle O(n)}$${\displaystyle O(n)}$

สำหรับภาพที่มีความละเอียดสูง ค่าไอเกนที่สองมักจะมีสภาพไม่ดีทำให้การลู่เข้าของตัวแก้ค่าไอเกนแบบวนซ้ำ เช่น อัลกอริทึมของ Lanczos เป็นไปอย่างช้าๆการปรับสภาพเบื้องต้นเป็นเทคโนโลยีสำคัญที่ช่วยเร่งการลู่เข้า เช่น ใน วิธีการ LOBPCG ที่ไม่ ใช้เมทริกซ์ การคำนวณเวกเตอร์ไอเกนโดยใช้วิธีการที่ไม่ใช้เมทริกซ์ซึ่งมีการปรับสภาพเบื้องต้นอย่างเหมาะสมนั้นใช้เวลา ซึ่งเป็นความซับซ้อนที่เหมาะสมที่สุด เนื่องจากเวกเตอร์ไอเกนมีส่วนประกอบ ${\displaystyle O(n)}$${\displaystyle n}$

scikit-learn ^{[ 3 ]}ใช้LOBPCGจากSciPyร่วมกับการปรับสภาพล่วงหน้าแบบมัลติกริดเชิงพีชคณิตเพื่อแก้ ปัญหา ค่าลักษณะเฉพาะสำหรับกราฟลาปลาเซียนเพื่อทำการแบ่งส่วนภาพ ผ่าน การแบ่งส่วนกราฟสเปกตรัมตามที่เสนอครั้งแรกใน^{[ 4 ]}และได้รับการทดสอบจริงใน^{[ 5 ]}และ^{[ 6 ]}

OBJ CUT ^{[ 7 ]}เป็นวิธีการที่มีประสิทธิภาพในการแบ่งส่วนวัตถุโดยอัตโนมัติ วิธีการ OBJ CUT เป็นวิธีการทั่วไป ดังนั้นจึงสามารถนำไปใช้กับโมเดลหมวดหมู่วัตถุใดๆ ก็ได้ เมื่อกำหนดภาพ D ที่มีอินสแตนซ์ของหมวดหมู่วัตถุที่รู้จัก เช่น วัว อัลกอริทึม OBJ CUT จะคำนวณการแบ่งส่วนของวัตถุ นั่นคือ จะอนุมานชุดของป้าย  กำกับ m

ให้ m เป็นเซตของป้ายกำกับไบนารี และให้เป็นพารามิเตอร์รูปร่าง ( เป็นค่าความน่าจะเป็นล่วงหน้าของรูปร่างบนป้ายกำกับจาก แบบจำลอง โครงสร้างภาพแบบหลายชั้น (LPS)) ฟังก์ชันพลังงานถูกกำหนดดังต่อไปนี้ ${\displaystyle \Theta }$${\displaystyle \Theta }$${\displaystyle E(m,\Theta )}$

${\displaystyle E(m,\Theta )=\sum \phi _{x}(D|m_{x})+\phi _{x}(m_{x}|\Theta )+\sum \Psi _{xy}(m_{x},m_{y})+\phi (D|m_{x},m_{y})}$ (1)

เทอมนี้เรียกว่าเทอมเอกภาค (unary term) และเทอมนี้เรียกว่าเทอมคู่ (pairwise term) เทอมเอกภาคประกอบด้วยความน่าจะเป็นตามสี และศักยภาพเอกภาคตามระยะห่างจากเทอมคู่ประกอบด้วยความน่าจะเป็นก่อนหน้า (prior term) และเทอมเปรียบเทียบ (contrast term ) ${\displaystyle \phi _{x}(D|m_{x})+\phi _{x}(m_{x}|\Theta )}$${\displaystyle \Psi _{xy}(m_{x},m_{y})+\phi (D|m_{x},m_{y})}$${\displaystyle \phi _{x}(D|m_{x})}$${\displaystyle \phi _{x}(m_{x}|\Theta )}$${\displaystyle \Theta }$${\displaystyle \Psi _{xy}(m_{x},m_{y})}$${\displaystyle \phi (D|m_{x},m_{y})}$

การติดฉลากที่ดีที่สุด จะทำให้ค่า มี ค่าน้อยที่สุดโดยที่คือค่าน้ำหนักของพารามิเตอร์ ${\displaystyle m^{*}}$${\displaystyle \sum \limits _{i}w_{i}E(m,\Theta _{i})}$${\displaystyle w_{i}}$${\displaystyle \Theta _{i}}$

${\displaystyle m^{*}=\arg \min \limits _{m}\sum \limits _{i}w_{i}E(m,\Theta _{i})}$ (2)

1. เมื่อกำหนดภาพ D มาให้ จะมีการเลือกหมวดหมู่ของวัตถุ เช่น วัว หรือ ม้า
2. โมเดล LPS ที่เกี่ยวข้องจะถูกจับคู่กับ D เพื่อให้ได้ตัวอย่าง${\displaystyle \Theta _{1},\cdots ,\Theta _{s}}$
3. ฟังก์ชันวัตถุประสงค์ที่กำหนดโดยสมการ (2) จะถูกกำหนดโดยการคำนวณและใช้${\displaystyle E(m,\Theta _{i})}$${\displaystyle w_{i}=g(\Theta _{i}|Z)}$
4. ฟังก์ชันเป้าหมายจะถูกลดให้เหลือน้อยที่สุดโดยใช้การดำเนินการ MINCUT เพียงครั้งเดียวเพื่อให้ได้การแบ่งส่วนm

• แนวทางจิ๊กซอว์^{[ 8 ]}
• การแยกวิเคราะห์ภาพ^{[ 9 ]}
• การแบ่งส่วนสลับ^{[ 10 ]}
• ตำแหน่ง^{[ 11 ]}
• LayoutCRF ^{[ 12 ]}
• การแบ่งส่วนตามต้นไม้ครอบคลุมขั้นต่ำ