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

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

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

ต้นไม้ครอบคลุมขั้นต่ำ (MST) คือ เซตย่อยของขอบกราฟที่มีน้ำหนักน้อยที่สุดและ ปราศจาก วงจร โดยที่โหนดทั้งหมดเชื่อมต่อกัน ในปี 2547 Felzenszwalb ได้นำเสนอวิธีการแบ่งส่วน ^{[ 4 ]}โดยอิงตามอัลกอริทึม MST ของ Kruskalขอบจะถูกพิจารณาตามลำดับน้ำหนักที่เพิ่มขึ้น พิกเซลปลายของขอบจะถูกรวมเข้าเป็นพื้นที่หากการรวมนี้ไม่ก่อให้เกิดวงจรในกราฟ และหากพิกเซลนั้น 'คล้ายคลึง' กับพิกเซลของพื้นที่ที่มีอยู่ การตรวจจับวงจรสามารถทำได้ในเวลาเกือบคงที่ด้วยความช่วยเหลือของโครงสร้างข้อมูลเซตที่ไม่เกี่ยวข้องกัน^{[ 5 ]} ความคล้ายคลึงกันของพิกเซลจะถูกตัดสินโดยฮิวริสติก ซึ่งเปรียบเทียบน้ำหนักกับเกณฑ์ต่อส่วน อัลกอริทึมจะส่งออก MST ที่ไม่เกี่ยวข้องกันหลายต้น กล่าวคือ ป่า แต่ละต้นไม้สอดคล้องกับส่วน ความซับซ้อนของอัลกอริทึมเป็นแบบกึ่งเชิงเส้นเนื่องจากการเรียงลำดับขอบสามารถทำได้ในเวลาเชิงเส้นผ่าน การ เรียง ลำดับแบบนับ

ในปี 2552 Wassenberg และคณะได้พัฒนาอัลกอริทึม^{[ 6 ]}ที่คำนวณ Minimum Spanning Forest อิสระหลายรายการแล้วนำมาเชื่อมต่อกัน ซึ่งช่วยให้สามารถประมวลผลแบบขนานได้โดยไม่ต้องแบ่งวัตถุตามขอบไทล์ แทนที่จะใช้เกณฑ์น้ำหนักคงที่ จะใช้ การติดป้ายส่วนประกอบที่เชื่อมต่อกัน ในเบื้องต้น เพื่อประมาณค่าขอบล่างของเกณฑ์ ซึ่งสามารถลดทั้งการแบ่งส่วนเกินและการแบ่งส่วนน้อยเกินไป การวัดแสดงให้เห็นว่าการใช้งานนี้มีประสิทธิภาพเหนือกว่าอัลกอริทึมแบบลำดับของ Felzenszwalb ถึงหนึ่งลำดับขนาด

ในปี 2017 Saglam และ Baykan ใช้การแสดงลำดับของ Prim สำหรับต้นไม้ครอบคลุมขั้นต่ำและเสนอเกณฑ์การตัดใหม่สำหรับการแบ่งส่วนภาพ^{[ 7 ]}พวกเขาสร้าง MST ด้วยอัลกอริทึม MST ของ Prim โดยใช้โครงสร้างข้อมูล Fibonacci Heap วิธีนี้ประสบความสำเร็จอย่างมากกับภาพทดสอบในเวลาดำเนินการที่รวดเร็ว

• ข้อมูลเกี่ยวกับอัลกอริธึม PHMSF (Parallel Heuristic for Minimum Spanning Forests)