ระยะทางเฟรเชต์ การวัดความคล้ายคลึงของเส้นโค้ง

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

คำจำกัดความเชิงสัญชาตญาณ

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

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

คำจำกัดความทางคณิตศาสตร์

กำหนดให้ $(S, d)$ เป็นเมตริกสเปซ (Metric Space) โดยที่ $S$ คือเซตของจุด และ $d$ คือฟังก์ชันระยะทาง เส้นโค้ง $A$ ใน $S$ คือฟังก์ชันต่อเนื่องที่ส่งค่าจากช่วง $[0, 1]$ ไปยัง $S$ (เขียนแทนด้วย $A: [0, 1] o S$)

การกำหนดพารามิเตอร์ใหม่ (Reparameterization) $\alpha$ ของช่วง $[0, 1]$ คือฟังก์ชันต่อเนื่องที่ไม่ลดลงและเป็นฟังก์ชันทั่วถึง (Surjection) จาก $[0, 1]$ ไปยัง $[0, 1]$

สำหรับเส้นโค้ง $A$ และ $B$ สองเส้นใน $S$ ระยะทางเฟรเชต์ $F(A, B)$ นิยามได้จากค่าอินฟิมัม (Infimum) ของค่าสูงสุดของระยะทางระหว่างจุดบนเส้นโค้งทั้งสอง ภายใต้การกำหนดพารามิเตอร์ใหม่ $\alpha$ และ $\beta$ ดังนี้:

$F(A, B) = \inf_{\alpha, \beta} \max_{t \in [0, 1]} d(A(\alpha(t)), B(\beta(t)))$

การตีความตัวแปร

• $t$: เปรียบเสมือน "เวลา" ที่ใช้ในการเคลื่อนที่
• $A(\alpha(t))$: ตำแหน่งของสุนัข ณ เวลา $t$
• $B(\beta(t))$: ตำแหน่งของเจ้าของ ณ เวลา $t$
• $d(A(\alpha(t)), B(\beta(t)))$: ความยาวของสายจูง ณ เวลา $t$

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