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

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

อัลกอริทึมนี้ได้รับการเผยแพร่ครั้งแรกโดยLeo Gradyในรูปแบบเอกสารการประชุม^{[ 4 ]}และต่อมาในรูปแบบเอกสารวารสาร^{[ 1 ]}

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

สมมติว่าภาพถูกแทนด้วยกราฟโดยแต่ละโหนดเชื่อมโยงกับพิกเซล และแต่ละขอบเชื่อมต่อพิกเซลที่อยู่ติดกันค่าน้ำหนักของขอบใช้ในการเข้ารหัสความคล้ายคลึงกันของโหนด ซึ่งอาจได้มาจากความแตกต่างของความเข้มของภาพ สี พื้นผิว หรือคุณลักษณะที่มีความหมายอื่นๆ ตัวอย่างเช่น การใช้ความเข้มของภาพที่โหนดมักจะใช้ฟังก์ชันการถ่วงน้ำหนักขอบ ${\displaystyle v_{i}}$${\displaystyle e_{ij}}$${\displaystyle v_{i}}$${\displaystyle v_{j}}$${\displaystyle g_{i}}$${\displaystyle v_{i}}$

${\displaystyle w_{ij}=\exp {\left(-\beta (g_{i}-g_{j})^{2}\right)}.}$

จากนั้นจึงนำโหนด เส้นเชื่อม และน้ำหนักมาใช้ในการสร้างเมทริกซ์ลาปลาเซียน ของ กราฟ

อัลกอริทึมการเดินแบบสุ่มจะปรับพลังงานให้เหมาะสมที่สุด

${\displaystyle Q(x)=x^{T}Lx=\sum _{e_{ij}}w_{ij}\left(x_{i}-x_{j}\right)^{2}}$

โดยที่แทนตัวแปรค่าจริงที่เชื่อมโยงกับแต่ละโหนดในกราฟ และการหาค่าที่เหมาะสมที่สุดถูกจำกัดด้วยสำหรับและสำหรับโดยที่และแทนเซตของเมล็ดพันธุ์พื้นหน้าและพื้นหลังตามลำดับ ถ้าเราให้แทนเซตของโหนดที่มีเมล็ดพันธุ์ (เช่น) และแทนเซตของโหนดที่ไม่มีเมล็ดพันธุ์ (เช่นโดยที่คือเซตของโหนดทั้งหมด) แล้วค่าที่เหมาะสมที่สุดของ ปัญหา การลดพลังงานจะได้รับจากคำตอบของ ${\displaystyle x_{i}}$${\displaystyle x_{i}=1}$${\displaystyle v_{i}\in F}$${\displaystyle x_{i}=0}$${\displaystyle v_{i}\in B}$${\displaystyle F}$${\displaystyle B}$${\displaystyle S}$${\displaystyle S=F\cup B}$${\displaystyle {\overline {S}}}$${\displaystyle S\cup {\overline {S}}=V}$${\displaystyle V}$

${\displaystyle L_{{\overline {S}},{\overline {S}}}x_{\overline {S}}=-L_{{\overline {S}},S}x_{S},}$

โดยที่ตัวห้อยใช้เพื่อระบุส่วนของเมทริกซ์ลาปลาเซียนของกราฟที่จัดทำดัชนีโดยชุดที่เกี่ยวข้อง ${\displaystyle L}$

เพื่อรวมเงื่อนไขความน่าจะเป็น (เอกภาค) เข้ากับอัลกอริทึม ได้มีการแสดงให้เห็นใน^{[ 3 ]}ว่าอาจปรับพลังงานให้เหมาะสมที่สุดได้

${\displaystyle Q(x)=x^{T}Lx+\gamma \left((1-x)^{T}F(1-x)+x^{T}Bx\right)=\sum _{e_{ij}}w_{ij}\left(x_{i}-x_{j}\right)^{2}+\gamma \left(\sum _{v_{i}}f_{i}(1-x_{i})^{2}+\sum _{v_{i}}b_{i}x_{i}^{2}\right),}$

สำหรับเมทริกซ์บวกและ เมทริกซ์ทแยงมุม การปรับพลังงานนี้ให้เหมาะสมจะนำไปสู่ระบบสมการเชิงเส้น ${\displaystyle F}$${\displaystyle B}$

${\displaystyle \left(L_{{\overline {S}},{\overline {S}}}+\gamma F_{{\overline {S}},{\overline {S}}}+\gamma B_{{\overline {S}},{\overline {S}}}\right)x_{\overline {S}}=-L_{{\overline {S}},S}x_{S}-\gamma F_{{\โอเวอร์ไลน์ {S}},{\โอเวอร์ไลน์ {S}}}.}$

ในกรณีนี้ เซตของโหนดเริ่มต้นอาจว่างเปล่า (เช่น) แต่การมีอยู่ของเมทริกซ์แนวทแยงมุมที่เป็นบวกทำให้สามารถหาคำตอบที่ไม่ซ้ำกันสำหรับระบบสมการเชิงเส้นนี้ได้ ${\displaystyle S}$${\displaystyle {\overline {S}}=V}$

ตัวอย่างเช่น หากใช้เงื่อนไขความน่าจะเป็น/เงื่อนไขเอกภาคเพื่อรวมแบบจำลองสีของวัตถุจะแสดงถึงความมั่นใจว่าสีที่โหนดนั้นเป็นของวัตถุ (กล่าวคือ ค่าที่มากขึ้นแสดงถึงความมั่นใจที่มากขึ้นว่า สีนั้น เป็นของป้ายกำกับวัตถุ) และจะแสดงถึงความมั่นใจว่าสีที่โหนดนั้นเป็นของพื้นหลัง ${\displaystyle f_{i}}$${\displaystyle v_{i}}$${\displaystyle f_{i}}$${\displaystyle v_{i}}$${\displaystyle b_{i}}$${\displaystyle v_{i}}$

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

มีความเชื่อมโยงที่รู้จักกันดีระหว่าง ทฤษฎี วงจรไฟฟ้าและการเดินแบบสุ่มบนกราฟ^{[ 5 ]} ด้วยเหตุนี้ อัลกอริทึมการเดินแบบสุ่มจึงมีการตีความที่แตกต่างกันสองแบบในแง่ของวงจรไฟฟ้า ในทั้งสองกรณี กราฟจะถูกมองว่าเป็นวงจรไฟฟ้าซึ่งแต่ละขอบจะถูกแทนที่ด้วยตัวต้านทาน เชิงเส้นแบบพาสซี ฟ ความต้านทานที่เกี่ยวข้องกับขอบจะถูกตั้งค่าให้เท่ากับ(กล่าวคือ น้ำหนักของขอบเท่ากับค่าการนำไฟฟ้า ) ${\displaystyle r_{ij}}$${\displaystyle e_{ij}}$${\displaystyle r_{ij}={\frac {1}{w_{ij}}}}$

ในการตีความครั้งแรก โหนดแต่ละโหนดที่เชื่อมโยงกับเมล็ดพันธุ์พื้นหลังจะเชื่อมต่อโดยตรงกับกราวด์ในขณะที่โหนดแต่ละโหนดที่เชื่อมโยงกับเมล็ดพันธุ์วัตถุ/พื้นหน้าจะเชื่อมต่อกับแหล่งจ่ายแรงดันกระแสตรงใน อุดมคติหนึ่งหน่วย ที่เชื่อมต่อกับกราวด์ (กล่าวคือ เพื่อสร้างศักย์ไฟฟ้าหนึ่งหน่วยที่แต่ละโหนด) ศักย์ไฟฟ้าของวงจรในสภาวะคงที่ที่สร้างขึ้นที่แต่ละโหนดโดยการกำหนดค่าวงจรนี้จะเท่ากับความน่าจะเป็นของผู้เดินสุ่มอย่างแม่นยำ โดยเฉพาะอย่างยิ่ง ศักย์ไฟฟ้าที่โหนดจะเท่ากับความน่าจะเป็นที่ผู้เดินสุ่มที่ถูกปล่อยที่โหนดจะไปถึงโหนดวัตถุ/พื้นหน้าก่อนที่จะไปถึงโหนดพื้นหลัง ${\displaystyle v_{i}\in B}$${\displaystyle v_{i}\in F}$${\displaystyle v_{i}\in F}$${\displaystyle x_{i}}$${\displaystyle v_{i}}$${\displaystyle v_{i}}$

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

อัลกอริทึมการเดินแบบสุ่มดั้งเดิมที่อธิบายไว้ข้างต้นได้รับการพัฒนาต่อยอดในหลายด้าน:

• การเดินแบบสุ่มพร้อมการเริ่มต้นใหม่^{[ 6 ]}
• การกำหนดขอบเขตอัลฟ่า^{[ 7 ]}
• การเลือกเกณฑ์^{[ 8 ]}
• อินพุตแบบอ่อน^{[ 9 ]}
• รันบนภาพที่แบ่งส่วนไว้ล่วงหน้า^{[ 10 ]}
• การเดินสุ่มในปริภูมิมาตราส่วน^{[ 11 ]}
• ตัวเดินสุ่มเร็วโดยใช้การคำนวณล่วงหน้า แบบออฟไลน์ ^{[ 12 ] [ 13 ]}
• การเดินสุ่มทั่วไปที่อนุญาตให้ฟังก์ชันความเข้ากันได้ที่ยืดหยุ่น^{[ 14 ]}
• ลุ่มน้ำพลังงานที่รวมการตัดกราฟ ตัวเดินแบบสุ่ม และเส้นทางที่สั้นที่สุด^{[ 15 ]}
• ลุ่มน้ำแบบเดินสุ่ม^{[ 16 ]}
• สนามสุ่มแบบมีเงื่อนไขเกาส์เซียนหลายตัวแปร^{[ 17 ]}

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

• การระบายสีภาพ^{[ 18 ]}
• โรโตสโคปปิ้งแบบโต้ตอบ^{[ 19 ]}
• การแบ่งส่วนภาพทางการแพทย์^{[ 20 ] [ 21 ] [ 22 ]}
• การรวมการแบ่งส่วนหลายส่วน^{[ 23 ]}
• การแบ่งส่วนตาข่าย^{[ 24 ] [ 25 ]}
• การลดสัญญาณรบกวนของตาข่าย^{[ 26 ]}
• การแก้ไขการแบ่งส่วน^{[ 27 ]}
• การกำจัดเงา^{[ 28 ]}
• การจับคู่สเตอริโอ (เช่น การลงทะเบียนภาพหนึ่งมิติ) ^{[ 29 ]}
• การรวมภาพ^{[ 14 ] [ 17 ]}

• โค้ด Matlab ที่ใช้ขั้นตอนวิธีเดินสุ่มแบบดั้งเดิม
• โค้ด Matlab ที่ใช้ขั้นตอนวิธี Random Walker พร้อมการคำนวณล่วงหน้า
• การใช้งานอัลกอริทึมการเดินแบบสุ่มดั้งเดิมด้วยภาษา Python เก็บถาวรเมื่อวันที่ 14 ตุลาคม 2012 ที่Wayback Machineในชุดเครื่องมือประมวลผลภาพscikit-image