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

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

การสกัดบล็อบมีความเกี่ยวข้องแต่ก็แตกต่างจากการตรวจจับบล็อบ

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

หลังจากขั้นตอนการติดป้ายกำกับแล้ว กราฟอาจถูกแบ่งออกเป็นเซตย่อย จากนั้นจึงสามารถกู้คืนและประมวลผลข้อมูลดั้งเดิมได้

การใช้คำว่าการติดฉลากส่วนประกอบที่เชื่อมต่อกัน (Connected-Component Labeling หรือ CCL)และคำจำกัดความของคำนี้มีความสอดคล้องกันค่อนข้างมากในเอกสารทางวิชาการ ในขณะที่การวิเคราะห์ส่วนประกอบที่เชื่อมต่อกัน (Connected-Component Analysis หรือ CCA)มีความแตกต่างกันทั้งในด้านคำศัพท์และคำจำกัดความของปัญหา

Rosenfeld และคณะ^{[ 6 ]}นิยามการติดฉลากส่วนประกอบที่เชื่อมต่อว่าเป็น “[การสร้างภาพที่มีฉลากซึ่งตำแหน่งที่เกี่ยวข้องกับส่วนประกอบที่เชื่อมต่อเดียวกันของภาพอินพุตไบนารีมีฉลากที่ไม่ซ้ำกัน” Shapiro และคณะ^{[ 7 ]}นิยาม CCL ว่าเป็นตัวดำเนินการที่มี “อินพุตเป็นภาพไบนารีและ [...] เอาต์พุตเป็นภาพเชิงสัญลักษณ์ซึ่งฉลากที่กำหนดให้กับแต่ละพิกเซลเป็นจำนวนเต็มที่ระบุส่วนประกอบที่เชื่อมต่อซึ่งพิกเซลนั้นเป็นส่วนหนึ่งได้อย่างไม่ซ้ำกัน” ^{[ 8 ]}

ไม่มีข้อตกลงร่วมกันเกี่ยวกับคำจำกัดความของ CCA ในเอกสารวิชาการ มักใช้สลับกับ CCL ^{[ 9 ] [ 10 ]} Shapiro et al. ให้คำจำกัดความที่ครอบคลุมมากขึ้น: ^{[ 7 ]} “การวิเคราะห์ส่วนประกอบที่เชื่อมต่อประกอบด้วยการติดป้ายส่วนประกอบที่เชื่อมต่อของพิกเซลสีดำ ตามด้วยการวัดคุณสมบัติของพื้นที่ส่วนประกอบและการตัดสินใจ” คำจำกัดความสำหรับการวิเคราะห์ส่วนประกอบที่เชื่อมต่อที่นำเสนอในที่นี้มีความเป็นทั่วไปมากขึ้น โดยคำนึงถึงความคิดที่แสดงไว้ใน ^{[ 7 ] [ 9 ] [ 10 ]}

อัลกอริทึมที่กล่าวถึงสามารถนำไปประยุกต์ใช้กับมิติ ใดๆ ก็ได้ แม้ว่าจะต้อง ใช้ เวลาและพื้นที่ในการประมวลผล มากขึ้นก็ตาม

นี่เป็นวิธีที่รวดเร็วและง่ายมากในการนำไปใช้และทำความเข้าใจ โดยอิงตาม วิธี การท่องกราฟในทฤษฎีกราฟ กล่าวโดยสรุป เมื่อพบพิกเซลแรกของส่วนประกอบที่เชื่อมต่อแล้ว พิกเซลที่เชื่อมต่อทั้งหมดของส่วนประกอบที่เชื่อมต่อนั้นจะถูกติดป้ายกำกับก่อนที่จะไปยังพิกเซลถัดไปในภาพ อัลกอริทึมนี้เป็นส่วนหนึ่งของอัลกอริทึมการแบ่งส่วนแบบ watershed ของ Vincent และ Soille ^{[ 11 ]} นอกจากนี้ ยังมีการใช้งานอื่นๆ อีกด้วย^{[ 12 ]}

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

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

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

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

รหัสเทียมคือ:

อัลกอริทึม OneComponentAtATime(data) อินพุต  : imageData[xDim][yDim] การเริ่มต้น  : label = 0, labelArray[xDim][yDim] = 0, statusArray[xDim][yDim] = false, queue1, queue2; สำหรับ i = 0 ถึง xDim ทำ ซ้ำ สำหรับ j = 0 ถึง yDim ทำซ้ำถ้า imageData[i][j] ยังไม่ได้รับการประมวลผลทำซ้ำถ้า imageData[i][j] เป็นพิกเซลพื้นหน้าทำซ้ำ ตรวจสอบเพื่อนบ้านทั้งสี่ทิศ (เหนือ ใต้ ตะวันออก ตะวันตก) : ถ้าเพื่อนบ้านไม่ได้รับการประมวลผลให้ทำถ้าเพื่อนบ้านเป็นพิกเซลพื้นหน้าให้ทำ เพิ่มลงในคิว 1 อื่น อัปเดตสถานะเป็นดำเนินการแล้ว จบถ้า labelArray[i][j] = label (กำหนดป้ายกำกับ) statusArray[i][j] = true (อัปเดตสถานะ) ในขณะที่ queue1 ยังไม่ว่างให้ทำดังนี้ สำหรับแต่ละพิกเซลในคิว ให้ทำดังนี้: ตรวจสอบเพื่อนบ้านทั้งสี่ของมัน ถ้าเพื่อนบ้านไม่ได้รับการประมวลผลให้ทำถ้าเพื่อนบ้านเป็นพิกเซลพื้นหน้าให้ทำ เพิ่มลงในคิว 2 อื่น อัปเดตสถานะเป็นดำเนินการแล้ว จบถ้า ให้ป้ายกำกับปัจจุบันแก่สิ่งนั้น อัปเดตสถานะเป็นดำเนินการแล้ว ลบองค์ประกอบปัจจุบันออกจากคิว 1 คัดลอกคิว 2 ไปยังคิว 1 จบ ในขณะที่ เพิ่มฉลาก จบ if else อัปเดตสถานะเป็นดำเนินการแล้ว จบถ้าจบถ้าจบถ้าจบสำหรับจบสำหรับ

อัลกอริทึมแบบสองรอบ^{[ 13 ]} (หรือที่รู้จักกันในชื่ออัลกอริทึม Hoshen–Kopelman ) ค่อนข้างง่ายต่อการนำไปใช้และทำความเข้าใจ โดยจะวนซ้ำผ่านข้อมูลไบนารี2 มิติ อัลกอริทึมจะวนซ้ำภาพสองรอบ: รอบแรกเพื่อกำหนดป้ายกำกับชั่วคราวและบันทึกความเท่าเทียมกัน และรอบที่สองเพื่อแทนที่ป้ายกำกับชั่วคราวแต่ละอันด้วยป้ายกำกับที่เล็กที่สุดของคลาสความเท่าเทียมกัน

ข้อมูลป้อนเข้าสามารถแก้ไขได้ในสถานที่ (ซึ่งมีความเสี่ยงต่อความเสียหายของข้อมูล ) หรือข้อมูลการติดฉลากสามารถเก็บรักษาไว้ในโครงสร้างข้อมูลเพิ่มเติมได้

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

เงื่อนไขที่ต้องตรวจสอบ:

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

อัลกอริทึมจะดำเนินต่อไปในลักษณะนี้ และสร้างป้ายกำกับภูมิภาคใหม่เมื่อใดก็ตามที่จำเป็น อย่างไรก็ตาม กุญแจสำคัญของอัลกอริทึมที่รวดเร็วคือวิธีการผสานรวมนี้ อัลกอริทึมนี้ใช้ โครงสร้างข้อมูล ยูเนียน-ฟิน ด์ ซึ่งให้ประสิทธิภาพที่ยอดเยี่ยมสำหรับการติดตามความสัมพันธ์ที่เท่าเทียมกัน^{[ 14 ]}ยูเนียน-ฟินด์โดยพื้นฐานแล้วจะจัดเก็บป้ายกำกับที่สอดคล้องกับบล็อกเดียวกันในโครงสร้างข้อมูลเซตที่ไม่ทับซ้อนกันทำให้ง่ายต่อการจดจำความเท่าเทียมกันของป้ายกำกับสองป้ายโดยใช้วิธีการอินเทอร์เฟซ เช่น findSet(l) findSet(l) จะส่งคืนค่าป้ายกำกับขั้นต่ำที่เทียบเท่ากับอาร์กิวเมนต์ฟังก์ชัน 'l'

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

อัลกอริทึมการสแกนที่เร็วกว่าสำหรับการสกัดพื้นที่ที่เชื่อมต่อกันมีดังต่อไปนี้^{[ 15 ]}

ในการผ่านครั้งแรก:

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

ในการผ่านครั้งที่สอง:

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

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

1. อาร์เรย์ที่จะใช้ในการแยกพื้นที่ที่เชื่อมต่อกันแสดงไว้ด้านล่าง (อิงตามการเชื่อมต่อ 8 จุด)

ขั้นแรก เราจะกำหนดค่าไบนารีที่แตกต่างกันให้กับองค์ประกอบในกราฟ ค่า "0~1" ที่อยู่ตรงกลางของแต่ละองค์ประกอบในกราฟต่อไปนี้คือค่าขององค์ประกอบ ในขณะที่ค่า "1,2,...,7" ในกราฟสองกราฟถัดไปคือป้ายกำกับขององค์ประกอบ แนวคิดทั้งสองนี้ไม่ควรสับสนกัน

2. หลังจากการประมวลผลรอบแรก ระบบจะสร้างป้ายกำกับดังต่อไปนี้:

มีการสร้างฉลากทั้งหมด 7 รายการตามเงื่อนไขที่ระบุไว้ข้างต้น

ความสัมพันธ์เทียบเท่าของป้ายกำกับที่สร้างขึ้นมีดังนี้

3. อาร์เรย์ที่สร้างขึ้นหลังจากรวมป้ายกำกับแล้ว ในที่นี้ ค่าป้ายกำกับที่เล็กที่สุดสำหรับภูมิภาคที่กำหนดจะ "กระจาย" ไปทั่วภูมิภาคที่เชื่อมต่อกันและให้ป้ายกำกับที่แตกต่างกันสองป้าย ดังนั้นจึงได้ป้ายกำกับที่แตกต่างกันสองป้าย

4. ผลลัพธ์สุดท้ายในรูปแบบสี เพื่อให้เห็นบริเวณที่แตกต่างกันสองบริเวณที่พบในอาร์เรย์ได้อย่างชัดเจน

รหัสเทียมคือ:

อัลกอริทึม TwoPass(data) คือ เชื่อมโยง = [] labels = โครงสร้างที่มีมิติของข้อมูล โดยเริ่มต้นด้วยค่าของ Background NextLabel = 0 ผ่านครั้งแรกสำหรับแถวในข้อมูลให้ทำซ้ำสำหรับคอลัมน์ในแถวนั้นถ้าข้อมูลแถวและคอลัมน์นั้นไม่ใช่พื้นหลัง ให้ ทำซ้ำ เพื่อนบ้าน = องค์ประกอบที่เชื่อมต่อกันซึ่งมีค่าเท่ากับองค์ประกอบปัจจุบัน ถ้า neighbors ว่างเปล่า linked[NextLabel] = เซตที่ประกอบด้วย NextLabel ป้ายกำกับ[แถว][คอลัมน์] = ป้ายกำกับถัดไป NextLabel += 1 อื่นหาป้ายกำกับที่เล็กที่สุด L = ป้ายกำกับเพื่อนบ้าน labels[row][column] = min (L) for label in L do linked[label] = union (linked[label], L) การผ่านครั้งที่สองสำหรับแถวในข้อมูลให้ทำซ้ำสำหรับคอลัมน์ในแถวนั้นถ้าข้อมูลแถวและคอลัมน์ไม่ใช่พื้นหลัง ให้ หา ป้ายกำกับแถวและคอลัมน์นั้นฉลาก ส่งคืน

อั ลกอริทึม findและunionถูกนำไปใช้ตามที่อธิบายไว้ในunion find

สร้างตัวนับภูมิภาค

สแกนภาพ (ในตัวอย่างต่อไปนี้ สมมติว่าการสแกนทำจากซ้ายไปขวาและจากบนลงล่าง):

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

ขั้นตอนบางส่วนที่มีอยู่ในอัลกอริธึมแบบสองรอบสามารถรวมเข้าด้วยกันเพื่อเพิ่มประสิทธิภาพ ทำให้สามารถสแกนภาพได้เพียงครั้งเดียว นอกจากนี้ยังมีอัลกอริธึมแบบหลายรอบ ซึ่งบางส่วนทำงานในเวลาเชิงเส้นเมื่อเทียบกับจำนวนพิกเซลของภาพ^{[ 16 ]}

ในช่วงต้นทศวรรษ 1990 มีความสนใจอย่างมากในการประมวล ผล แบบขนานของอัลกอริธึมส่วนประกอบที่เชื่อมต่อกันใน แอปพลิเคชัน การวิเคราะห์ภาพเนื่องจากข้อจำกัดของการประมวลผลแต่ละพิกเซลตามลำดับ^{[ 17 ]}

ความสนใจในอัลกอริทึมนี้กลับมาอีกครั้งเมื่อมีการใช้งานCUDA อย่าง แพร่หลาย

อัลกอริทึม:

1. เมทริกซ์ส่วนประกอบที่เชื่อมต่อกันจะถูกกำหนดค่าเริ่มต้นให้มีขนาดเท่ากับเมทริกซ์รูปภาพ
2. จะมีการกำหนดค่าเริ่มต้นและเพิ่มค่าขึ้นสำหรับวัตถุแต่ละชิ้นที่ตรวจพบในภาพ
3. มีการกำหนดค่าเริ่มต้นให้กับตัวนับเพื่อนับจำนวนวัตถุ
4. เริ่มการสแกนแบบเรียงตามแถวสำหรับภาพทั้งหมด
5. หากตรวจพบพิกเซลของวัตถุ ขั้นตอนต่อไปนี้จะถูกทำซ้ำในขณะที่ (ดัชนี != 0)
   1. ตั้งค่าพิกเซลที่เกี่ยวข้องเป็น 0 ในรูปภาพ
   2. เวกเตอร์ (ดัชนี) จะได้รับการอัปเดตด้วยพิกเซลข้างเคียงทั้งหมดของพิกเซลที่ตั้งค่าไว้ในปัจจุบัน
   3. พิกเซลที่ไม่ซ้ำกันจะถูกเก็บไว้ และพิกเซลที่ซ้ำกันจะถูกลบออก
   4. กำหนดค่าพิกเซลที่ระบุโดยดัชนีเพื่อทำเครื่องหมายในเมทริกซ์ส่วนประกอบที่เชื่อมต่อกัน
6. เพิ่มค่าตัวชี้สำหรับวัตถุอื่นในภาพ

การประกอบทีละส่วน (ภาพ ) [M, N] := ขนาด( ภาพ ) เชื่อมต่อ  := ศูนย์(M, N) เครื่องหมาย  := ค่า ความแตกต่าง  := ค่าเพิ่มขึ้น ออฟเซ็ต  := [-1; M; 1; -M] ดัชนี  := [] จำนวนวัตถุ  := 0 สำหรับ i: 1:M ทำซ้ำสำหรับj : 1:N ถ้า ( ภาพ (i, j) == 1) แล้วno_of_objects  := no_of_objects + 1 index  := [((j-1) × M + i)] connected ( index ) := mark ในขณะที่indexว่างเปล่าทำซ้ำimage ( index ) := 0 neighbors  := bsxfun(@plus, index , offsets ) neighbors  := unique( neighbors (:)) index  := neighbors (find( image ( neighbors ))) connected ( index ) := mark จบการทำซ้ำmark  := mark + difference จบเงื่อนไขจบการ ทำซ้ำ จบ การทำซ้ำ

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

ในช่วงสองทศวรรษที่ผ่านมา มีการเสนอแนวทางใหม่ๆ มากมายสำหรับการติดป้ายส่วนประกอบที่เชื่อมต่อกัน แต่แทบไม่มีแนวทางใดเลยที่ได้รับการประเมินประสิทธิภาพเชิงเปรียบเทียบโดยใช้ชุดข้อมูล เดียวกัน YACCLAB ^{[ 18 ] [ 19 ]} (ชื่อย่อของ Yet Another Connected Components Labeling Benchmark) เป็นตัวอย่างของ เฟรมเวิร์กโอเพนซอร์ส C++ที่รวบรวม เรียกใช้ และทดสอบอัลกอริธึมการติดป้ายส่วนประกอบที่เชื่อมต่อกัน

การเกิดขึ้นของFPGAที่มีความจุเพียงพอที่จะทำงานประมวลผลภาพที่ซับซ้อนยังนำไปสู่สถาปัตยกรรมประสิทธิภาพสูงสำหรับการติดฉลากส่วนประกอบที่เชื่อมต่อ^{[ 20 ] [ 21 ]}สถาปัตยกรรมเหล่านี้ส่วนใหญ่ใช้อัลกอริธึมแบบผ่านครั้งเดียว เนื่องจากมีทรัพยากรหน่วยความจำจำกัดบนFPGAสถาปัตยกรรมติดฉลากส่วนประกอบที่เชื่อมต่อประเภทนี้สามารถประมวลผลพิกเซลภาพหลายพิกเซลพร้อมกันได้ จึงทำให้ได้ปริมาณงานสูงและเวลาแฝงในการประมวลผลต่ำ

• การสกัดคุณลักษณะ
• น้ำท่วม

• การนำไปใช้งานในภาษา C#
• เกี่ยวกับการสกัดวัตถุจากภาพและอัลกอริธึมการติดป้ายส่วนประกอบที่เชื่อมต่อโดยตรง