เมื่อนำไปใช้ในสาขาคอมพิวเตอร์วิชั่นการเพิ่มประสิทธิภาพการตัดกราฟสามารถนำไปใช้เพื่อแก้ปัญหาคอมพิวเตอร์วิชั่นระดับต่ำที่หลากหลายได้อย่างมีประสิทธิภาพ ( วิชั่นยุคแรก^{[ 1 ]} ) เช่นการปรับภาพให้เรียบปัญหาการจับคู่สเตอริโอการแบ่งส่วนภาพการแบ่งส่วนร่วมของวัตถุการใช้งานทางทหารจำนวนมาก (เช่นการจดจำเป้าหมายอัตโนมัติ ) และปัญหาอื่นๆ อีกมากมายที่สามารถกำหนดได้ในแง่ของการลดพลังงานให้น้อยที่สุด (เช่นวิทยาศาสตร์ภูมิอากาศและการสร้างแบบจำลองสิ่งแวดล้อม )

ปัจจุบันเทคนิคการตัดกราฟถูกนำมาใช้ร่วมกับ เทคนิค ปัญญาประดิษฐ์เชิง พื้นที่ทั่วไปมากขึ้น (เช่น เพื่อบังคับโครงสร้างใน ผลลัพธ์ของ แบบจำลองภาษาขนาดใหญ่เพื่อเพิ่มความคมชัดของขอบเขตเนื้องอก และในทำนองเดียวกันสำหรับแอปพลิเคชันต่างๆ เช่นเทคโนโลยีความเป็นจริงเสริมรถยนต์ไร้คนขับหุ่นยนต์ Google Mapsเป็นต้น)

ปัญหาการลดพลังงานเหล่านี้จำนวนมากสามารถประมาณได้โดยการแก้ปัญหาการไหลสูงสุดในกราฟ^{[ 2 ]} (และด้วยเหตุนี้ ตามทฤษฎีบทการไหลสูงสุดและการตัดขั้นต่ำจึงสามารถกำหนดการตัด ขั้นต่ำ ของกราฟได้) ภายใต้การกำหนดปัญหาดังกล่าวส่วนใหญ่ในคอมพิวเตอร์วิชั่น โซลูชันพลังงานต่ำสุดจะสอดคล้องกับการประมาณค่าสูงสุดภายหลังของโซลูชัน

แม้ว่าอัลกอริธึมการมองเห็นด้วยคอมพิวเตอร์หลายอย่างจะเกี่ยวข้องกับการตัดกราฟ (เช่น การตัดแบบนอร์มาไลซ์) แต่คำว่า "การตัดกราฟ" นั้นใช้เฉพาะกับโมเดลที่ใช้การเพิ่มประสิทธิภาพการไหลสูงสุด/การตัดต่ำสุดเท่านั้น (อัลกอริธึมการตัดกราฟอื่นๆ อาจถือได้ว่าเป็น อัลกอริธึม การแบ่งส่วนกราฟ )

ปัญหา "ไบนารี" (เช่นการลดสัญญาณรบกวนในภาพไบนารี ) สามารถแก้ไขได้อย่างแม่นยำโดยใช้วิธีนี้ ส่วนปัญหาที่พิกเซลสามารถติดป้ายกำกับได้มากกว่าสองป้ายกำกับ (เช่น การจับคู่ภาพสเตอริโอ หรือการลดสัญญาณรบกวนใน ภาพ ระดับสีเทา ) ไม่สามารถแก้ไขได้อย่างแม่นยำ แต่โดยทั่วไปแล้วคำตอบที่ได้จะใกล้เคียงกับค่าที่เหมาะสมที่สุดโดยรวม

ทฤษฎีพื้นฐานของการตัดกราฟในคอมพิวเตอร์วิชั่นได้รับการพัฒนาครั้งแรกโดย Margaret Greig, Bruce Porteous และ Allan Seheult (GPS) จากมหาวิทยาลัย Durhamในบทความอภิปรายที่เป็นตำนานในบทความของJulian Besagในปี 1986 ^{[ 3 ]}และบทความติดตามที่มีรายละเอียดมากขึ้น^{[ 4 ]}ในปี 1989 ใน บริบททางสถิติ แบบเบย์เซียนของการปรับภาพที่มีสัญญาณรบกวนให้เรียบ โดยใช้ฟิลด์สุ่มมาร์คอฟเป็นการกระจายความน่าจะเป็นล่วงหน้าของภาพ พวกเขาแสดงให้เห็นด้วยการพิสูจน์ทางคณิตศาสตร์ที่สวยงามว่าการประมาณค่าสูงสุดภายหลังของภาพไบนารีสามารถหาได้อย่างแม่นยำโดยการเพิ่มการไหลผ่านเครือข่ายภาพหรือกราฟที่เกี่ยวข้อง ซึ่งเกี่ยวข้องกับการแนะนำแหล่งที่มาและปลายทางและอัตราส่วนความน่าจะเป็นล็อกปัญหาได้รับการพิสูจน์แล้วว่าสามารถแก้ไขได้อย่างมีประสิทธิภาพอย่างแม่นยำซึ่งเป็นผลลัพธ์ที่ไม่คาดคิด เนื่องจากเชื่อกันว่าปัญหานี้ไม่สามารถคำนวณได้ (NP hard)

GPS ยังได้กล่าวถึงต้นทุนการคำนวณของอัลกอริทึม max-flow บนกราฟขนาดใหญ่ ซึ่งเป็นข้อกังวลที่สำคัญในขณะนั้น พวกเขาเสนออัลกอริทึมการแบ่งส่วน (ดูหัวข้อ 4 ของ GPS) ที่เกี่ยวข้องกับการรวมบล็อกหรือไทล์ที่ไม่ทับซ้อนกันแบบเรียกซ้ำ ซึ่งทำให้ความเร็วเพิ่มขึ้น 12 เท่า วิธีการนี้จะแก้ปัญหาและรวมกราฟย่อยอิสระแบบเรียกซ้ำจนกว่าจะแก้ปัญหากราฟทั้งหมดได้ ในขณะที่นักวิจัยร่วมสมัยอย่าง Geman และ Geman ^{[ 5 ]}ได้สนับสนุนการคำนวณแบบขนานในบริบทของการจำลองการอบอ่อนกลยุทธ์การแบ่งบล็อกของ GPS นำเสนอโครงสร้างเชิงกำหนดที่เหมาะสมกับการประมวลผลแบบขนานและคาดการณ์ถึงการออกแบบปัญญาประดิษฐ์สมัยใหม่บนGPU หลายตัว อย่างไรก็ตาม จนกระทั่งเมื่อไม่นานมานี้ แง่มุมนี้ของเอกสารถูกละเลยเป็นส่วนใหญ่ และงานวิจัยต่อมามุ่งเน้นไปที่ ต้นไม้ค้นหาทั่วโลก ของคอมพิวเตอร์แบบอนุกรมเช่นอัลกอริทึม Boykov-Kolmogorov ^{[ 6 ]}

แม้ว่าปัญหาทั่วไปเกี่ยวกับสีจะเป็นปัญหา NP-hard แต่แนวทาง GPS กลับมีประโยชน์อย่างกว้างขวางในปัญหาคอมพิวเตอร์วิชั่นทั่วไป สิ่งนี้ได้รับการสาธิตครั้งแรกโดย Boykov, Veksler และ Zabih ^{[ 2 ]}ซึ่งในบทความสำคัญที่ตีพิมพ์มากกว่า 10 ปีหลังจากบทความ GPS ฉบับดั้งเดิม และในงานสำคัญอื่นๆ ได้จุดประกายให้มีการนำเทคนิคการตัดกราฟมาใช้ในคอมพิวเตอร์วิชั่นโดยทั่วไป พวกเขาแสดงให้เห็นว่า สำหรับปัญหาทั่วไป แนวทาง GPS สามารถนำไปใช้ซ้ำๆ กับลำดับของปัญหาไบนารี โดยใช้อัลกอริธึมการขยายอัลฟาที่แพร่หลายในปัจจุบัน ซึ่งให้ผลลัพธ์ที่ใกล้เคียงกับค่าที่เหมาะสมที่สุด ก่อนหน้าผลลัพธ์เหล่านี้ เทคนิคการเพิ่มประสิทธิภาพเฉพาะที่ โดยประมาณเช่นการจำลองการอบอ่อน (ตามที่เสนอโดยพี่น้อง Geman ^{[ 5 ]} ) หรือโหมดเงื่อนไขแบบวนซ้ำ (อัลก อริธึมแบบโลภประเภทหนึ่งที่เสนอโดย Julian Besag ^{[ 3 ]} ) ถูกนำมาใช้เพื่อแก้ปัญหาการปรับภาพให้เรียบดังกล่าว ${\displaystyle k}$${\displaystyle k>2,}$

จากความก้าวหน้าเหล่านี้ การเพิ่มประสิทธิภาพการตัดกราฟ GPS จึงถูกนำไปปรับใช้สำหรับการแบ่งส่วนภาพแบบโต้ตอบ โดยเฉพาะอย่างยิ่งผ่านอัลกอริทึม "GrabCut" ที่แนะนำโดย Carsten Rother, Vladimir Kolmogorov และ Andrew Blake ^{[ 7 ]}จาก Microsoft Research, Cambridge GrabCut ได้ขยายวิธีการตัดกราฟแบบโต้ตอบก่อนหน้านี้โดยการแทนที่ฮิสโตแกรมภาพขาวดำด้วยแบบจำลองส่วนผสมเกาส์เซียนเพื่อประมาณการการกระจายสี และโดยการใช้แผนการลดพลังงาน GPS แบบวนซ้ำ วิธีการนี้ช่วยลดความซับซ้อนของการโต้ตอบกับผู้ใช้อย่างมาก โดยต้องการเพียงกรอบสี่เหลี่ยมรอบวัตถุเป้าหมายอย่างคร่าวๆ แทนที่จะใช้เส้นที่ผู้ใช้วาดอย่างละเอียด และมันก็กลายเป็นเครื่องมือมาตรฐานอย่างรวดเร็วทั้งในงานวิจัยทางวิชาการและซอฟต์แวร์แก้ไขภาพเชิงพาณิชย์

เอกสาร GPS เชื่อมโยงและประสานแนวคิดที่ลึกซึ้งจากสถิติทางคณิตศาสตร์ ( ทฤษฎีบทของเบย์ส , ฟิลด์สุ่มมาร์คอฟ^{[ 8 ] [ 9 ]} ), ฟิสิกส์ ( แบบจำลองไอซิง ), การเพิ่มประสิทธิภาพ ( ฟังก์ชันพลังงาน ) และวิทยาศาสตร์คอมพิวเตอร์ ( ปัญหาการไหลของเครือข่าย ) และนำไปสู่การเปลี่ยนจากวิธีการเพิ่มประสิทธิภาพแบบท้องถิ่นโดยประมาณและช้า (เช่น การจำลองการอบอ่อน) ไปสู่เทคนิคการเพิ่มประสิทธิภาพแบบทั่วโลกที่มีประสิทธิภาพมากขึ้น แม่นยำ หรือเกือบแม่นยำ และรวดเร็วยิ่งขึ้น ปัจจุบันได้รับการยอมรับว่าเป็นเอกสารสำคัญ เนื่องจากล้ำหน้ากว่ายุคสมัย และโดยเฉพาะอย่างยิ่ง ได้รับการตีพิมพ์หลายปีก่อนการปฏิวัติพลังการคำนวณของกฎ ของมัวร์และGPU

ที่สำคัญคือ GPS ได้รับการตีพิมพ์ในวารสารสถิติทางคณิตศาสตร์ (แทนที่จะเป็นวารสารคอมพิวเตอร์วิชั่น) และนี่ทำให้มันถูกมองข้ามโดยชุมชนคอมพิวเตอร์วิชั่นเป็นเวลาหลายปี เป็นที่รู้กันอย่างไม่เป็นทางการว่าเป็นบทความ " The Velvet Underground " ของคอมพิวเตอร์วิชั่น (กล่าวคือ แม้ว่าจะมีคนในวงการคอมพิวเตอร์วิชั่นเพียงไม่กี่คนที่อ่านบทความนี้ [ซื้อแผ่นเสียง] แต่ผู้ที่อ่าน โดยเฉพาะ Boykov, Veksler และ Zabih ^{[ 2 ]}ได้เริ่มต้นงานวิจัยใหม่และสำคัญ [ก่อตั้งวงดนตรี]) สิ่งนี้ได้รับการยืนยันโดยอัตราส่วนการขยายขนาดใหญ่มากของ GPS (การอ้างอิงลำดับที่ 2/การอ้างอิงลำดับที่ 1) ซึ่งประมาณการไว้ว่าเกิน 100

แม้ว่างาน GPS จะมีลักษณะพื้นฐาน แต่การยอมรับอย่างเป็นทางการจากชุมชนคอมพิวเตอร์วิชั่นส่วนใหญ่กลับตกเป็นของนักวิจัยที่ต่อยอดและทำให้วิธีการตัดกราฟเป็นที่นิยม ตัวอย่างเช่น Boykov, Veksler และ Zabih ^{[ 2 ]} ได้รับ รางวัล Helmholtzจาก ICCV อย่างสมควร ในปี 2011 ^{[ 10 ]}รางวัลนี้มอบให้แก่บทความ ICCV จาก 10 ปีขึ้นไปก่อนหน้านั้น ซึ่งมีผลกระทบอย่างมากต่อการวิจัยคอมพิวเตอร์วิชั่น

ในปี 2011 Couprie และคณะ [ ^{11 ] ได้}เสนอกรอบการแบ่งส่วนภาพทั่วไปที่เรียกว่า "Power Watershed" ซึ่งลดฟังก์ชันตัวบ่ง ชี้ค่าจริง จาก [0,1] บนกราฟที่ถูกจำกัดโดยเมล็ดพันธุ์ของผู้ใช้ (หรือเทอมเอกภาค) ที่ตั้งค่าเป็น 0 หรือ 1 โดยที่การลดฟังก์ชันตัวบ่งชี้บนกราฟจะถูกปรับให้เหมาะสมที่สุดโดยสัมพันธ์กับเลขชี้กำลังเมื่อPower Watershed จะถูกปรับให้เหมาะสมที่สุดโดยการตัดกราฟ เมื่อPower Watershed จะถูกปรับให้เหมาะสมที่สุดโดยเส้นทางที่สั้นที่สุดจะถูกปรับให้เหมาะสมที่สุดโดยอัลกอริทึมการเดินแบบสุ่มและจะถูกปรับให้เหมาะสมที่สุดโดย อัลกอริทึม Watershedด้วยวิธีนี้ Power Watershed อาจถูกมองว่าเป็นการวางนัยทั่วไปของการตัดกราฟที่ให้การเชื่อมต่อโดยตรงกับอัลกอริทึมการแบ่งส่วน/การจัดกลุ่มที่เพิ่มประสิทธิภาพพลังงานอื่นๆ ${\displaystyle p}$${\displaystyle p=1}$${\displaystyle p=0}$${\displaystyle p=2}$${\displaystyle p=\infty }$

• ภาพ:${\displaystyle x\in \{R,G,B\}^{N}}$
• ผลลัพธ์: การแบ่งส่วน (หรือเรียกว่าความทึบแสง) (การแบ่งส่วนแบบอ่อน) สำหรับการแบ่งส่วนแบบแข็ง${\displaystyle S\in R^{N}}$${\displaystyle S\in \{0{\text{ สำหรับพื้นหลัง}},1{\text{ สำหรับพื้นหน้า/วัตถุที่จะตรวจจับ}}\}^{N}}$
• ฟังก์ชันพลังงาน : โดยที่ C คือพารามิเตอร์สี และ λ คือพารามิเตอร์ความสอดคล้อง${\displaystyle E(x,S,C,\lambda )}$
• ${\displaystyle E(x,S,C,\lambda )=E_{\rm {color}}+E_{\rm {coherence}}}$
• การปรับให้เหมาะสม: สามารถประมาณการแบ่งส่วนได้โดยใช้ค่าต่ำสุดทั่วโลกเหนือ S:${\displaystyle {\arg \min }_{S}E(x,S,C,\lambda )}$

• การตัดกราฟมาตรฐาน: ปรับฟังก์ชันพลังงานให้เหมาะสมเหนือการแบ่งส่วน (ค่า S ไม่ทราบค่า)
• การตัดกราฟแบบวนซ้ำ:

1. ขั้นตอนแรกคือการปรับค่าพารามิเตอร์สีโดยใช้ K-means
2. ขั้นตอนที่สองจะดำเนินการตามอัลกอริทึมการตัดกราฟตามปกติ

ทำซ้ำสองขั้นตอนเหล่านี้ไปเรื่อยๆ จนกว่าจะบรรจบกัน

• การตัดกราฟแบบไดนามิก: ช่วยให้สามารถเรียกใช้อัลกอริทึมซ้ำได้เร็วขึ้นมากหลังจากแก้ไขปัญหา (เช่น หลังจากผู้ใช้เพิ่ม seed ใหม่)

${\displaystyle \Pr(x\mid S)=K^{-E}}$

โดยที่พลังงานประกอบด้วยโมเดลที่แตกต่างกันสองแบบ ( และ): ${\displaystyle E}$${\displaystyle E_{\rm {color}}}$${\displaystyle E_{\rm {coherence}}}$

${\displaystyle E_{\rm {color}}}$— เทอมเอกภาคที่อธิบายความน่าจะเป็นของแต่ละสี

• สามารถสร้างแบบจำลองคำนี้ได้โดยใช้วิธีการต่างๆ ทั้งในระดับท้องถิ่น (เช่น เท็กซอน) หรือระดับโลก (เช่น ฮิสโตแกรม, GMM, ความน่าจะเป็นของ Adaboost) ซึ่งจะอธิบายไว้ด้านล่าง

• เราใช้ค่าความเข้มของพิกเซลที่ทำเครื่องหมายไว้เป็นจุดเริ่มต้น (seed) เพื่อสร้างฮิสโตแกรมสำหรับการกระจายความเข้มของวัตถุ (พื้นหน้า) และพื้นหลัง: P(I|O) และ P(I|B)
• จากนั้น เราใช้ฮิสโตแกรมเหล่านี้เพื่อกำหนดค่าปรับระดับภูมิภาคเป็นค่าลบของลอการิทึมความน่าจะเป็น

• โดยปกติเราจะใช้การแจกแจงสองแบบ แบบหนึ่งสำหรับการสร้างแบบจำลองพื้นหลัง และอีกแบบหนึ่งสำหรับพิกเซลส่วนหน้า
• ใช้แบบจำลองการผสมแบบเกาส์เซียน (ที่มี 5–8 องค์ประกอบ) เพื่อจำลองการแจกแจงทั้ง 2 แบบนั้น
• เป้าหมาย: พยายามแยกแยะความแตกต่างระหว่างการแจกแจงทั้งสองแบบนั้น

• เท็กซอน (หรือเท็กซ์ตัน) คือกลุ่มพิกเซลที่มีลักษณะเฉพาะบางอย่างและปรากฏซ้ำๆ ในภาพ
• ขั้นตอน:

1. กำหนดขนาดธรรมชาติที่เหมาะสมสำหรับองค์ประกอบพื้นผิว
2. คำนวณสถิติแบบไม่ใช้พารามิเตอร์ของเท็กซอนภายในแบบจำลอง โดยพิจารณาจากความเข้มหรือการตอบสนองของตัวกรองกาบอร์

• ตัวอย่าง:
  • การแบ่งส่วนวัตถุที่มีพื้นผิวตามแบบจำลองที่ปรับเปลี่ยนรูปทรงได้
  • การวิเคราะห์เส้นขอบและพื้นผิวสำหรับการแบ่งส่วนภาพ

${\displaystyle E_{\rm {coherence}}}$— คำศัพท์ไบนารีที่อธิบายความสอดคล้องกันระหว่างพิกเซลในบริเวณใกล้เคียง

• ในทางปฏิบัติ พิกเซลจะถูกกำหนดว่าเป็นพิกเซลข้างเคียงหากอยู่ติดกันในแนวนอน แนวตั้ง หรือแนวทแยง (การเชื่อมต่อแบบ 4 ทาง หรือการเชื่อมต่อแบบ 8 ทางสำหรับภาพ 2 มิติ)
• ต้นทุนอาจขึ้นอยู่กับความชันของความเข้มในพื้นที่ จุดตัดศูนย์ของ Laplacian ทิศทางของความชัน รูปแบบการผสมสี ฯลฯ
• มีการกำหนดฟังก์ชันพลังงานที่แตกต่างกันไว้:
  • ฟิลด์สุ่มมาร์คอฟมาตรฐาน: กำหนดค่าปรับให้กับพิกเซลที่ไม่สอดคล้องกันโดยการประเมินความแตกต่างระหว่างป้ายกำกับการแบ่งส่วน (การวัดความยาวของขอบเขตอย่างคร่าวๆ) ดู Boykov และ Kolmogorov ICCV 2003
  • สนามสุ่มแบบมีเงื่อนไข : ถ้าสีแตกต่างกันมาก อาจเป็นที่ที่เหมาะสมที่จะกำหนดขอบเขต ดู Lafferty et al. 2001; Kumar and Hebert 2003

วิธีการตัดกราฟได้กลายเป็นทางเลือกยอดนิยมแทนวิธีการที่ใช้เซตระดับในการเพิ่มประสิทธิภาพตำแหน่งของเส้นขอบ (ดู^{[ 12 ]}สำหรับการเปรียบเทียบอย่างละเอียด) อย่างไรก็ตาม วิธีการตัดกราฟได้รับการวิพากษ์วิจารณ์ในวรรณกรรมในหลายประเด็น:

• สิ่งผิดปกติของการวัดเมตริก: เมื่อภาพถูกแสดงด้วยแลตทิซที่เชื่อมต่อ 4 จุด วิธีการตัดกราฟอาจแสดงสิ่งผิดปกติ "เป็นบล็อก" ที่ไม่พึงประสงค์ วิธีการต่างๆ ได้รับการเสนอเพื่อแก้ไขปัญหานี้ เช่น การใช้ขอบเพิ่มเติม^{[ 13 ]}หรือโดยการกำหนดปัญหาการไหลสูงสุดในพื้นที่ต่อเนื่อง^{[ 14 ]}
• อคติที่หดตัว: เนื่องจากการตัดกราฟจะค้นหาการตัดขั้นต่ำ อัลกอริทึมจึงอาจมีอคติในการสร้างเส้นขอบขนาดเล็ก^{[ 15 ]} ตัวอย่างเช่น อัลกอริทึมนี้ไม่เหมาะสำหรับการแบ่งส่วนวัตถุบางๆ เช่น หลอดเลือด (ดู^{[ 16 ]}สำหรับวิธีแก้ไขที่เสนอ)
• ป้ายกำกับหลายรายการ: การตัดกราฟสามารถค้นหาค่าเหมาะสมที่สุดทั่วโลกได้เฉพาะสำหรับปัญหาการติดป้ายกำกับแบบไบนารี (เช่น ป้ายกำกับสองรายการ) เช่น การแบ่งส่วนภาพพื้นหน้า/พื้นหลัง มีการเสนอส่วนขยายที่สามารถค้นหาวิธีแก้ปัญหาโดยประมาณสำหรับปัญหาการตัดกราฟแบบหลายป้ายกำกับ^{[ 2 ]}
• หน่วยความจำ: การใช้หน่วยความจำของการตัดกราฟจะเพิ่มขึ้นอย่างรวดเร็วเมื่อขนาดของภาพเพิ่มขึ้น ตัวอย่างเช่น อัลกอริทึมการไหลสูงสุดของ Boykov-Kolmogorov เวอร์ชัน 2.2 จะจัดสรรไบต์ ( และคือจำนวนโหนดและขอบในกราฟตามลำดับ) อย่างไรก็ตาม มีการทำงานบางส่วนในทิศทางนี้เมื่อเร็ว ๆ นี้เพื่อลดขนาดกราฟก่อนการคำนวณการไหลสูงสุด^{[ 17 ] [ 18 ] [ 19 ]}${\displaystyle 24n+14m}$${\displaystyle n}$${\displaystyle m}$

แม้ว่าการตัดกราฟจะให้คำตอบที่เหมาะสมที่สุดทางคณิตศาสตร์สำหรับฟังก์ชันพลังงานเฉพาะบางอย่าง แต่การใช้งานเป็นวิธีการเดี่ยวๆ สำหรับการจดจำวัตถุทั่วไปนั้นลดลงไปพร้อมกับการมาถึงของเทคโนโลยีการเรียนรู้เชิงลึก ข้อจำกัดหลักๆ ได้แก่:

• ช่องว่างทางความหมาย:การตัดกราฟอาศัยเบาะแสระดับต่ำ (ความเข้มของพิกเซล สี พื้นผิว) และขาดความเข้าใจความหมายระดับสูง จึงไม่สามารถแยกแยะความแตกต่างระหว่างวัตถุที่มีความหมายต่างกันแต่มีลักษณะทาง視覚ที่คล้ายคลึงกันได้ (เช่น การแยกแยะสุนัขจากแมวที่มีสีเดียวกัน)
• ต้นทุนการคำนวณ:ลักษณะการทำงานแบบวนซ้ำของอัลกอริธึมการไหลสูงสุด (โดยทั่วไปคือหรือ) ทำให้มีต้นทุนการคำนวณสูงสำหรับวิดีโอความละเอียดสูง เมื่อเทียบกับการอนุมานแบบฟีดฟอร์เวิร์ดของโครงข่ายประสาทเทียม${\displaystyle O(V^{2}E)}$${\displaystyle O(V^{3})}$
• การประมวลผลแบบขนาน:ต่างจากการคูณเมทริกซ์ในโครงข่ายประสาทเทียม อัลกอริทึมการตัดกราฟนั้นยากที่จะประมวลผลแบบขนานได้อย่างมีประสิทธิภาพบนGPU รุ่นใหม่ๆ ซึ่งก่อให้เกิดปัญหาคอขวดในกระบวนการทำงานแบบเรียลไทม์

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

ในยุคของการเรียนรู้เชิงลึก อัลกอริทึม Graph Cut ได้เปลี่ยนบทบาทจากตัวแก้ปัญหาการแบ่งส่วนภาพแบบเดี่ยวๆ มาเป็นส่วนประกอบที่ผสานรวมอยู่ในสถาปัตยกรรมโครงข่ายประสาทเทียมที่ซับซ้อน ในขณะที่แอปพลิเคชันในยุคแรกๆ เน้นไปที่การติดป้ายกำกับภาพ 2 มิติแบบแยกส่วน การใช้งานในปัจจุบันใช้ประโยชน์จากความสามารถของอัลกอริทึมในการให้โครงสร้างเชิงพื้นที่และเวลาที่เข้มงวดทางคณิตศาสตร์แก่ผลลัพธ์ของโครงข่ายประสาทเทียมแบบ "อ่อน"

ความท้าทายหลักในการบูรณาการ AI สมัยใหม่คือ ลักษณะที่ไม่ต่อเนื่องของอัลกอริทึม min-cut/max-flow นั้นไม่สามารถหาอนุพันธ์ได้โดยธรรมชาติ

• เลเยอร์ที่สามารถหาอนุพันธ์ได้:เฟรมเวิร์กใหม่ๆ ได้นำเสนอการผ่อนคลายแบบ "อ่อน" หรือแบบต่อเนื่องของพลังงานการตัดกราฟ ซึ่งช่วยให้สามารถใช้อัลกอริธึมนี้เป็นเลเยอร์ที่มีโครงสร้างภายในโครงข่ายประสาทเทียมแบบคอนโวลูชัน (CNN) หรือทรานส์ฟอร์เมอร์ได้ โครงข่ายจะเรียนรู้ที่จะส่งออกน้ำหนักขอบและศักยภาพของโหนดที่เหมาะสมที่สุด ซึ่งเลเยอร์การตัดกราฟจะปรับให้เหมาะสมที่สุดเพื่อสร้างผลลัพธ์ที่สอดคล้องกันในเชิงพื้นที่
• ฟังก์ชันความสูญเสียแบบไฮบริด:วิธีการสมัยใหม่ใช้พลังงานตัดกราฟเป็นฟังก์ชันความสูญเสียระหว่างการฝึกฝน ซึ่งบังคับให้โมเดลเรียนรู้การแบ่งส่วนที่สอดคล้องกับขอบเขตที่มีความคมชัดสูงในข้อมูลดิบอย่างมีประสิทธิภาพ เป็นการสอน AI ให้เคารพขอบ "ทางกายภาพ" โดยไม่จำเป็นต้องใช้ข้อมูลการฝึกฝนที่มีความละเอียดสูงจำนวนมหาศาล

ด้วยการเกิดขึ้นของแบบจำลองพื้นฐานขนาดใหญ่ เช่น แบบจำลอง Segment Anything Model (SAM) การตัดกราฟจึงได้เข้ามามีบทบาทใหม่ใน "ส่วนหัวของการปรับแต่ง" แม้ว่าแบบจำลองเหล่านี้จะยอดเยี่ยมในการระบุวัตถุทั่วไป แต่ก็อาจสร้างขอบเขตที่ "ไม่ชัดเจน" หรือไม่เป็นไปตามหลักการแมนิโฟลด์ได้ การตัดกราฟจึงถูกนำมาใช้เป็นขั้นตอนหลังการประมวลผลเพื่อ "ยึด" ขอบเขตของมาสก์ให้เข้ากับขอบที่มีความคมชัดสูง ในกรณีที่มีข้อมูลน้อย การตัดกราฟจะกระจายป้ายกำกับจาก "จุดนำทาง" ที่ผู้ใช้กำหนดไว้เพียงไม่กี่จุดไปยังการฝังคุณลักษณะมิติสูงที่สร้างขึ้นโดยทรานส์ฟอร์เมอร์

การตัดภาพกราฟยังคงเป็นมาตรฐานทองคำในการวินิจฉัยทางการแพทย์ในกรณีที่ข้อมูลมักมีสัญญาณรบกวนหรือมีน้อย

• การแบ่งส่วนปริมาตร:ในการวิเคราะห์ MRI และ CT การตัดกราฟช่วยให้มั่นใจได้ถึง "ความสอดคล้องทางโทโพโลยี" ในแบบ 3 มิติ ในขณะที่โครงข่ายประสาทเทียมอาจระบุพิกเซลแต่ละพิกเซลผิดพลาด การตัดกราฟช่วยให้มั่นใจได้ว่าโครงสร้างทางกายวิภาค เช่น หลอดเลือดหรือเนื้องอก จะถูกแสดงเป็นปริมาตรที่ต่อเนื่องและเชื่อมต่อกัน
• การแบ่งส่วนภาพแบบโต้ตอบ:แพลตฟอร์มทางการแพทย์สมัยใหม่ (เช่น MONAI) ใช้การตัดกราฟเพื่อเปิดใช้งาน AI ที่มี "มนุษย์เข้ามาเกี่ยวข้อง" แพทย์รังสีวิทยาจะให้ "การคลิกนำทาง" เพียงไม่กี่ครั้ง (จุดเริ่มต้น) และการตัดกราฟจะรวมข้อจำกัดด้วยตนเองเหล่านี้เข้ากับแผนที่คุณลักษณะการเรียนรู้เชิงลึกเพื่อคำนวณขอบเขตที่เหมาะสมที่สุดทั่วโลกแบบเรียลไทม์

ในด้านการป้องกันประเทศและข่าวกรอง การตัดกราฟจะถูกนำมาใช้กับข้อมูลเซ็นเซอร์ความละเอียดสูง ซึ่งจำเป็นต้องลดโอกาสเกิดผลลัพธ์ที่ผิดพลาดให้น้อยที่สุด

• การวิเคราะห์ภาพเรดาร์สังเคราะห์ (SAR) และภาพถ่ายดาวเทียม:ภาพเรดาร์สังเคราะห์ (SAR) มักมีคุณภาพลดลงเนื่องจากสัญญาณรบกวนแบบ "จุดด่าง" การตัดกราฟถูกนำมาใช้เพื่อลดสัญญาณรบกวนและแบ่งส่วนภาพเหล่านี้ ทำให้สามารถตรวจจับยานพาหนะที่พรางตัวหรือการเปลี่ยนแปลงของภูมิประเทศได้
• การติดตามเชิงพื้นที่และเวลา:สำหรับการเฝ้าระวังอัตโนมัติ การตัดกราฟจะขยายไปสู่มิติเวลา โดยการเชื่อมโยงพิกเซลข้ามช่วงเวลา ระบบจะบังคับใช้ "ข้อจำกัดทางกายภาพ" ทำให้มั่นใจได้ว่าเป้าหมายที่ติดตามจะรักษาปริมาตร 3 มิติที่สม่ำเสมอและไม่ "สั่นไหว" หรือแตกกระจายในเฟรมวิดีโอต่างๆ

วิทยาศาสตร์ภูมิอากาศสมัยใหม่ใช้การปรับให้เหมาะสมโดยใช้กราฟเพื่อเชื่อมช่องว่างระหว่างข้อมูลสถานีตรวจวัดอากาศแบบไม่ต่อเนื่องกับแบบจำลองบรรยากาศแบบต่อเนื่อง

• การรวมแบบจำลองหลายแบบ:เมื่อรวมแบบจำลองสภาพภูมิอากาศโลก (GCM) ต่างๆ เข้าด้วยกัน การตัดกราฟจะเลือกแบบจำลองที่แม่นยำที่สุดสำหรับภูมิภาคทางภูมิศาสตร์เฉพาะ เพื่อให้แน่ใจว่าการเปลี่ยนผ่านระหว่างแบบจำลองระดับภูมิภาคมีความราบรื่นในเชิงพื้นที่และสอดคล้องกันทางกายภาพ ป้องกัน "รอยต่อ" หรือสิ่งผิดปกติในแผนที่ปริมาณน้ำฝนและอุณหภูมิโลก
• การติดตามการเปลี่ยนแปลงการปกคลุมของพื้นดิน:ด้วยการประมวลผลข้อมูลอนุกรมเวลาจากดาวเทียมเป็นกราฟ 3 มิติ นักวิจัยใช้การตัดกราฟเพื่อแยกความแตกต่างระหว่างการเปลี่ยนแปลงการปกคลุมของพื้นดินถาวร (การตัดไม้ทำลายป่า การขยายตัวของเมือง) และการเปลี่ยนแปลงตามฤดูกาลชั่วคราว

ในด้านหุ่นยนต์ การตัดกราฟ (Graph Cuts) ถูกนำมาใช้ในการสร้างแผนที่เชิงความหมาย (Semantic Mapping ) หุ่นยนต์ที่เคลื่อนที่ผ่านสภาพแวดล้อมจะต้องแบ่งกลุ่มจุด 3 มิติของมันออกเป็นพื้นที่ที่สามารถนำทางได้ พื้นที่ที่มีสิ่งกีดขวาง และพื้นที่ "ที่ไม่รู้จัก" การตัดกราฟเป็นวิธีการที่มีประสิทธิภาพในการรวมข้อมูล LIDAR ที่มีสัญญาณรบกวนเข้ากับป้ายกำกับเชิงความหมายแบบภาพ ทำให้มั่นใจได้ว่าแผนที่ที่ได้จะถูกแบ่งออกเป็นโซนที่มีเหตุผลและไม่ทับซ้อนกัน ซึ่งอัลกอริทึมการวางแผนเส้นทางสามารถนำทางได้

เทคนิค การตัดกราฟ (Graph cuts) ถูกนำมาใช้มากขึ้นเรื่อยๆ ในสาขาการเรียนรู้ของเครื่องจักรที่รักษาความเป็นส่วนตัว (Privacy-Preserving Machine Learning ) เมื่อสร้างชุดข้อมูลสังเคราะห์หรือ "ปกปิดข้อมูลส่วนบุคคล" รูปภาพ เทคนิคการตัดกราฟสามารถใช้เพื่อระบุและแยกส่วนที่ละเอียดอ่อน (เช่น ใบหน้าหรือป้ายทะเบียนรถ) โดยอาศัยการลดพลังงานให้เหลือน้อยที่สุด วิธีนี้ช่วยให้มั่นใจได้ว่าขอบเขตของข้อมูลที่ถูกลบออกนั้นมีความแม่นยำเพียงพอที่จะไม่มีข้อมูลส่วนตัว "ตกค้าง" อยู่ที่ขอบของการตัด ซึ่งเป็นจุดอ่อนทั่วไปของเทคนิคการเบลอภาพแบบสร้างภาพล้วนๆ (GAN-based)

ในด้านการบินและอวกาศและการพยากรณ์อากาศ การตัดกราฟช่วยในการแบ่งพาร์ติชันตาข่ายแบบไดนามิกเพื่อเพิ่มประสิทธิภาพทรัพยากรซูเปอร์คอมพิวเตอร์ การตัดกราฟจะระบุบริเวณที่มีความซับซ้อนสูง เช่น ตาของพายุเฮอริเคนหรือขอบใบพัดกังหัน และแบ่งภาระงานการคำนวณตามนั้น ซึ่งทำให้มั่นใจได้ว่า "ส่วนที่ถูกตัด" ซึ่งมีฟิสิกส์ที่ซับซ้อนที่สุดเกิดขึ้น จะได้รับพลังการประมวลผลที่มีความหนาแน่นสูงสุด

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

ในวิกิบุ๊กเรื่องการนำอัลกอริทึมไปใช้มีหน้าหนึ่งที่กล่าวถึงหัวข้อ: กราฟ/การไหลสูงสุด/บอยคอฟและโคลโมโกโรฟ

อัลกอริทึม Boykov-Kolmogorov ^{[ 6 ]}เป็นวิธีที่มีประสิทธิภาพในการคำนวณการไหลสูงสุดสำหรับกราฟที่เกี่ยวข้องกับคอมพิวเตอร์วิชั่น

อัลกอริทึม Sim Cut ^{[ 20 ]}ประมาณค่าการตัดกราฟขั้นต่ำ อัลกอริทึมนี้ใช้วิธีแก้ปัญหาโดยการจำลองเครือข่ายไฟฟ้า นี่คือแนวทางที่แนะนำโดยทฤษฎีบทการไหลสูงสุดของ Cederbaum ^{[ 21 ] [ 22 ]} การเร่งความเร็วของอัลกอริทึมเป็นไปได้ผ่านการคำนวณแบบขนาน

• http://pub.ist.ac.at/~vnk/software.html — การนำอัลกอริทึม maxflow มาใช้ ซึ่งอธิบายไว้ในบทความ "An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Computer Vision" โดย Vladimir Kolmogorov
• http://vision.csd.uwo.ca/code/ — ไลบรารีสำหรับการตัดกราฟและส่วนเชื่อมต่อ MATLAB บางส่วน
• http://gridcut.com/ — โปรแกรมแก้ปัญหา max-flow/min-cut แบบมัลติคอร์ที่รวดเร็วและปรับให้เหมาะสมสำหรับกราฟแบบตาราง