Chulalongkorn University Theses and Dissertations (Chula ETD)

Other Title (Parallel Title in Other Language of ETD)


Year (A.D.)


Document Type


First Advisor

Thanarat Chalidabhongse


Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Department (if any)

Department of Computer Engineering (ภาควิชาวิศวกรรมคอมพิวเตอร์)

Degree Name

Doctor of Philosophy

Degree Level

Doctoral Degree

Degree Discipline

Computer Engineering




Random field formulation has proven to be a powerful framework for solving various computer vision tasks, specifically those involving assigning labels to image pixels or superpixels subjected to spatial relationships and visual contexts, due to the ability to intuitively incorporate global and local information. Unfortunately, solving these problems can be impractical when large number of variables and possible labels are present as the computational complexity grows fast with the problem size. In this thesis, we propose a speedup scheme for random field optimization using local label hierarchy. We focus on problems in which the label space has a natural ordering structure that represents physical quantity and exploit characteristics of the underlying labeling problems to obtain a hierarchical energy minimization technique. This has enabled us to circumvent exhaustive search of label space and, therefore, achieve better performance in terms of running time. We give definitions and notations for local label hierarchy as well as present approaches for label-wise grouping, namely, local minimum search, cluster analysis, and maximum-difference subdivision. We also generalize the definition of energy function to include sets of labels as the domain and present heuristics for assigning group potentials. The added processing steps have significantly less theoretical computational complexity than the overall process. Our methodology was tested with a number of computer vision problems with structured label spaces. The experimental results have shown that our proposed scheme can provide up to an order of magnitude speedup of the computation time while providing comparable energy.

Other Abstract (Other language abstract of ETD)

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



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.