هندسه اپی‌پولار

هدف#

در این بخش،

• با مبانی هندسه چنددیدگاهی (Multiview Geometry) آشنا خواهیم شد.
• خواهیم دید اپی‌پول (Epipole)، خطوط اپی‌پولار (Epipolar lines)، قید اپی‌پولار (Epipolar constraint) و غیره چه هستند.

مفاهیم پایه#

هنگامی که با استفاده از دوربین سوراخ‌سوزنی عکسی می‌گیریم، اطلاعات مهمی را از دست می‌دهیم، یعنی عمق تصویر؛ یا اینکه هر نقطه در تصویر چقدر از دوربین فاصله دارد، زیرا این یک تبدیل سه‌بعدی به دوبعدی است. بنابراین این یک سوال مهم است که آیا می‌توانیم اطلاعات عمق را با استفاده از این دوربین‌ها پیدا کنیم؟ و پاسخ این است که از بیش از یک دوربین استفاده کنیم. چشمان ما به شیوه‌ای مشابه عمل می‌کنند که در آن از دو دوربین (دو چشم) استفاده می‌کنیم که به آن دید استریو (Stereo Vision) می‌گویند. بنابراین بیایید ببینیم OpenCV چه امکاناتی در این زمینه فراهم می‌کند.

(کتاب Learning OpenCV نوشته گری برادسکی اطلاعات زیادی در این زمینه دارد.)

قبل از پرداختن به تصاویر عمق، بیایید ابتدا برخی مفاهیم اساسی در هندسه چنددیدگاهی را درک کنیم. در این بخش با هندسه اپی‌پولار سر و کار خواهیم داشت. تصویر زیر را ببینید که چیدمان پایه‌ای با دو دوربین را نشان می‌دهد که از یک صحنه عکس می‌گیرند.

اگر فقط از دوربین چپ استفاده کنیم، نمی‌توانیم نقطه سه‌بعدی متناظر با نقطه $x$ در تصویر را پیدا کنیم زیرا هر نقطه روی خط $OX$ روی همان نقطه در صفحه تصویر پرتاب می‌شود. اما تصویر راست را نیز در نظر بگیرید. اکنون نقاط مختلف روی خط $OX$ به نقاط مختلفی ($x^{\prime }$) در صفحه راست تصویر می‌شوند. بنابراین با این دو تصویر، می‌توانیم نقطه سه‌بعدی صحیح را مثلث‌بندی (Triangulate) کنیم. کل ایده همین است.

تصویر پرتاب‌شده نقاط مختلف روی $OX$ یک خط روی صفحه راست تشکیل می‌دهد (خط $l^{\prime }$). ما آن را خط اپی‌پولار (epiline) متناظر با نقطه $x$ می‌نامیم. این بدان معناست که برای یافتن نقطه $x$ در تصویر راست، در امتداد این خط اپی‌پولار جستجو کنید؛ نقطه باید در جایی روی این خط باشد (به این شکل به آن فکر کنید: برای یافتن نقطه متناظر در تصویر دیگر، نیازی نیست کل تصویر را جستجو کنید، فقط در امتداد خط اپی‌پولار جستجو نمایید؛ بنابراین کارایی و دقت بهتری فراهم می‌کند). این پدیده قید اپی‌پولار (Epipolar Constraint) نامیده می‌شود. مشابهاً همه نقاط، خطوط اپی‌پولار متناظر خود را در تصویر دیگر خواهند داشت. صفحه $XO{O}^{\prime }$ صفحه اپی‌پولار (Epipolar Plane) نامیده می‌شود.

نقاط $O$ و $O^{\prime }$ مراکز دوربین‌ها هستند. از چیدمان ارائه‌شده در بالا، می‌توانید مشاهده کنید که پرتاب دوربین راست $O^{\prime }$ روی تصویر چپ در نقطه $e$ دیده می‌شود. این نقطه اپی‌پول (epipole) نامیده می‌شود. اپی‌پول نقطه تقاطع خط عبوری از مراکز دوربین و صفحات تصویر است. به طور مشابه $e^{\prime }$ اپی‌پول دوربین چپ است. در برخی موارد، شما قادر به تعیین محل اپی‌پول در تصویر نخواهید بود و آن‌ها ممکن است خارج از تصویر باشند (به این معنی که یک دوربین، دوربین دیگر را نمی‌بیند).

تمام خطوط اپی‌پولار از اپی‌پول خود عبور می‌کنند. بنابراین برای یافتن مکان اپی‌پول، می‌توانیم چندین خط اپی‌پولار را بیابیم و نقطه تقاطع آن‌ها را پیدا کنیم.

بنابراین در این جلسه، ما بر یافتن خطوط اپی‌پولار و اپی‌پول‌ها تمرکز می‌کنیم. اما برای یافتن آن‌ها، به دو مؤلفه دیگر نیاز داریم: ماتریس بنیادین (Fundamental Matrix یا F) و ماتریس اساسی (Essential Matrix یا E). ماتریس اساسی شامل اطلاعات مربوط به انتقال و چرخش است که موقعیت دوربین دوم را نسبت به دوربین اول در مختصات جهانی توصیف می‌کند. تصویر زیر را ببینید (با تشکر از تصویر: کتاب Learning OpenCV نوشته Gary Bradsky):

اما ما ترجیح می‌دهیم محاسبات در مختصات پیکسلی انجام شوند، درست است؟ ماتریس بنیادین شامل همان اطلاعات ماتریس اساسی به همراه اطلاعات مربوط به پارامترهای ذاتی هر دو دوربین است تا بتوانیم دو دوربین را در مختصات پیکسلی به هم مرتبط سازیم. (اگر از تصاویر تصحیح‌شده (Rectified) استفاده کنیم و با تقسیم بر فواصل کانونی نقطه را نرمال کنیم، $F=E$). به بیان ساده، ماتریس بنیادین F، نقطه‌ای در یک تصویر را به یک خط (خط اپی‌پولار) در تصویر دیگر نگاشت می‌کند. این ماتریس از روی نقاط متناظر از هر دو تصویر محاسبه می‌شود. حداقل ۸ نقطه از این دست برای یافتن ماتریس بنیادین مورد نیاز است (هنگام استفاده از الگوریتم ۸ نقطه‌ای). نقاط بیشتری ترجیح داده می‌شوند و برای به دست آوردن نتیجه مقاوم‌تر از RANSAC استفاده می‌شود.

کد#

بنابراین ابتدا باید تا حد امکان تطابق‌های ممکن را بین دو تصویر برای یافتن ماتریس بنیادین پیدا کنیم. برای این منظور، از توصیفگرهای SIFT همراه با تطبیق‌دهنده مبتنی بر FLANN و آزمون نسبت (Ratio test) استفاده می‌کنیم:

import numpy as np
import cv2 as cv
from matplotlib import pyplot as plt

img1 = cv.imread('myleft.jpg', cv.IMREAD_GRAYSCALE)  #queryimage # left image
img2 = cv.imread('myright.jpg', cv.IMREAD_GRAYSCALE) #trainimage # right image

sift = cv.SIFT_create()

# find the keypoints and descriptors with SIFT
kp1, des1 = sift.detectAndCompute(img1,None)
kp2, des2 = sift.detectAndCompute(img2,None)

# FLANN parameters
FLANN_INDEX_KDTREE = 1
index_params = dict(algorithm = FLANN_INDEX_KDTREE, trees = 5)
search_params = dict(checks=50)

flann = cv.FlannBasedMatcher(index_params,search_params)
matches = flann.knnMatch(des1,des2,k=2)

pts1 = []
pts2 = []

# ratio test as per Lowe's paper
for i,(m,n) in enumerate(matches):
    if m.distance < 0.8*n.distance:
        pts2.append(kp2[m.trainIdx].pt)
        pts1.append(kp1[m.queryIdx].pt)

اکنون فهرستی از بهترین تطابق‌ها را از هر دو تصویر در اختیار داریم. بیایید ماتریس بنیادین را پیدا کنیم:

pts1 = np.int32(pts1)
pts2 = np.int32(pts2)
F, mask = cv.findFundamentalMat(pts1,pts2,cv.FM_LMEDS)

# We select only inlier points
pts1 = pts1[mask.ravel()==1]
pts2 = pts2[mask.ravel()==1]

سپس خطوط اپی‌پولار را پیدا می‌کنیم. خطوط اپی‌پولار متناظر با نقاط در تصویر اول روی تصویر دوم رسم می‌شوند. بنابراین ذکر تصاویر صحیح در اینجا حائز اهمیت است. ما آرایه‌ای از خطوط را به دست می‌آوریم. بنابراین تابع جدیدی برای رسم این خطوط روی تصاویر تعریف می‌کنیم:

def drawlines(img1,img2,lines,pts1,pts2):
    ''' img1 - image on which we draw the epilines for the points in img2
        lines - corresponding epilines '''
    r,c = img1.shape
    img1 = cv.cvtColor(img1,cv.COLOR_GRAY2BGR)
    img2 = cv.cvtColor(img2,cv.COLOR_GRAY2BGR)
    for r,pt1,pt2 in zip(lines,pts1,pts2):
        color = tuple(np.random.randint(0,255,3).tolist())
        x0,y0 = map(int, [0, -r[2]/r[1] ])
        x1,y1 = map(int, [c, -(r[2]+r[0]*c)/r[1] ])
        img1 = cv.line(img1, (x0,y0), (x1,y1), color,1)
        img1 = cv.circle(img1,tuple(pt1),5,color,-1)
        img2 = cv.circle(img2,tuple(pt2),5,color,-1)
    return img1,img2

اکنون خطوط اپی‌پولار را در هر دو تصویر پیدا کرده و آن‌ها را رسم می‌کنیم:

# Find epilines corresponding to points in right image (second image) and
# drawing its lines on left image
lines1 = cv.computeCorrespondEpilines(pts2.reshape(-1,1,2), 2,F)
lines1 = lines1.reshape(-1,3)
img5,img6 = drawlines(img1,img2,lines1,pts1,pts2)

# Find epilines corresponding to points in left image (first image) and
# drawing its lines on right image
lines2 = cv.computeCorrespondEpilines(pts1.reshape(-1,1,2), 1,F)
lines2 = lines2.reshape(-1,3)
img3,img4 = drawlines(img2,img1,lines2,pts2,pts1)

plt.subplot(121),plt.imshow(img5)
plt.subplot(122),plt.imshow(img3)
plt.show()

نتیجه حاصل در زیر نشان داده شده است:

می‌توانید در تصویر سمت چپ مشاهده کنید که تمام خطوط اپی‌پولار در نقطه‌ای خارج از تصویر در سمت راست همگرا شده‌اند. آن نقطه تلاقی همان اپی‌پول است.

برای نتایج بهتر، باید از تصاویری با رزولوشن مناسب و نقاط غیرهم‌صفحه متعدد استفاده شود.

تمرین‌ها#

1. یک موضوع مهم حرکت رو به جلوی دوربین است. در آن حالت اپی‌پول‌ها در مکان‌های یکسانی در هر دو با خطوط اپی‌پولار که از یک نقطه ثابت ساطع می‌شوند دیده خواهند شد. این بحث را ببینید.
2. تخمین ماتریس بنیادین به کیفیت تطابق‌ها، نقاط پرت (Outliers) و غیره حساس است. هنگامی که تمام تطابق‌های انتخاب‌شده روی یک صفحه قرار داشته باشند وضعیت بدتر می‌شود. این بحث را بررسی کنید.