Triangulation (computer vision)
કોમ્પ્યુટર દ્રષ્ટિમાં, ત્રિકોણ એ બે અથવા વધુ છબીઓ પર તેના અંદાજોને ધ્યાનમાં રાખીને 3D જગ્યામાં બિંદુ નક્કી કરવાની પ્રક્રિયાનો સંદર્ભ આપે છે. આ સમસ્યાને ઉકેલવા માટે સામેલ કેમેરા માટે 3D થી 2D સુધીના કેમેરા પ્રક્ષેપણ કાર્યના પરિમાણોને જાણવું જરૂરી છે, જે કેમેરા મેટ્રિક્સ દ્વારા રજૂ કરવામાં આવેલા સૌથી સરળ કિસ્સામાં છે. ત્રિકોણને કેટલીકવાર પુનર્નિર્માણ અથવા આંતરછેદ તરીકે પણ ઓળખવામાં આવે છે. ત્રિકોણની સમસ્યા સિદ્ધાંતમાં તુચ્છ છે. છબીમાં દરેક બિંદુ 3D જગ્યામાં એક રેખાને અનુરૂપ હોવાથી, 3D માં રેખા પરના તમામ બિંદુઓ છબીના બિંદુ પર પ્રક્ષેપિત થાય છે. જો બે અથવા વધુ છબીઓમાં અનુરૂપ બિંદુઓની જોડી મળી શકે, તો તે કેસ હોવો જોઈએ કે તેઓ સામાન્ય 3D બિંદુ x નું પ્રક્ષેપણ છે. છબી બિંદુઓ દ્વારા પેદા થતી રેખાઓનો સમૂહ x (3D બિંદુ) પર છેદે છે અને x (3D બિંદુ) ના કોઓર્ડિનેટ્સની બીજગણિત રચનાની ગણતરી વિવિધ રીતે કરી શકાય છે, જે નીચે રજૂ કરવામાં આવી છે. વ્યવહારમાં, જોકે, છબી બિંદુઓના કોઓર્ડિનેટ્સને મનસ્વી ચોકસાઈ સાથે માપી શકાતા નથી. તેના બદલે, વિવિધ પ્રકારના ઘોંઘાટ, જેમ કે લેન્સની વિકૃતિથી ભૌમિતિક ઘોંઘાટ અથવા વ્યાજ બિંદુ શોધવાની ભૂલ, માપેલા છબી કોઓર્ડિનેટ્સમાં અચોક્કસતા તરફ દોરી જાય છે. પરિણામે, અનુરૂપ છબી બિંદુઓ દ્વારા પેદા થતી રેખાઓ હંમેશા 3D જગ્યામાં છેદતી નથી. પછી સમસ્યા એ છે કે 3D બિંદુ શોધવું જે માપેલા છબી બિંદુઓને શ્રેષ્ઠ રીતે બંધબેસે છે. સાહિત્યમાં શ્રેષ્ઠતાને કેવી રીતે વ્યાખ્યાયિત કરવી અને શ્રેષ્ઠ 3D બિંદુ કેવી રીતે શોધવું તે માટે બહુવિધ દરખાસ્તો છે. તેઓ વિવિધ શ્રેષ્ઠતાના માપદંડ પર આધારિત હોવાથી, જ્યારે ઘોંઘાટ સામેલ હોય ત્યારે વિવિધ પદ્ધતિઓ 3D બિંદુ x ના વિવિધ અંદાજો ઉત્પન્ન કરે છે. પરિચય નીચેનામાં, એવું માનવામાં આવે છે કે પિનહોલ કેમેરા દ્વારા પેદા થયેલ બે દૃશ્યોમાંથી અનુરૂપ છબી બિંદુઓ પર ત્રિકોણ બનાવવામાં આવે છે. આ ધારણાઓમાંથી સામાન્યીકરણની અહીં ચર્ચા કરવામાં આવી છે. ડાબી બાજુની છબી પિનહોલ મોડેલના સ્ટીરિયો કેમેરાની જોડીની એપિપોલર ભૂમિતિને સમજાવે છે. 3D જગ્યામાં એક બિંદુ x (3D બિંદુ) ને સંબંધિત છબી સમતલ પર એક રેખા (લીલો) સાથે પ્રક્ષેપિત કરવામાં આવે છે જે કેમેરાના કેન્દ્રબિંદુમાંથી પસાર થાય છે, અને પરિણામે બે અનુરૂપ છબી બિંદુઓ અને. જો અને આપવામાં આવે અને બે કેમેરાની ભૂમિતિ જાણીતી હોય, તો બે પ્રક્ષેપણ રેખાઓ (લીલી રેખાઓ) નક્કી કરી શકાય છે અને એવું હોવું જોઈએ કે તેઓ બિંદુ x (3D બિંદુ) પર છેદે છે. મૂળભૂત રેખીય બીજગણિતનો ઉપયોગ કરીને આંતરછેદ બિંદુને સીધી રીતે નક્કી કરી શકાય છે. જમણી બાજુની છબી વાસ્તવિક કેસ દર્શાવે છે. છબીની સ્થિતિ નિર્દેશ કરે છે અને તેને બરાબર માપી શકાતી નથી. તેનું કારણ ભૌમિતિક વિકૃતિ જેવા પરિબળોનું સંયોજન છે, ઉદાહરણ તરીકે લેન્સ વિકૃતિ, જેનો અર્થ છે કે કેમેરાનું 3D થી 2D મેપિંગ પિનહોલ કેમેરા મોડેલથી અલગ પડે છે. અમુક હદ સુધી આ ભૂલોને સરભર કરી શકાય છે, જે શેષ ભૌમિતિક ભૂલને છોડી દે છે. x (3D બિંદુ) માંથી પ્રકાશનું એક જ કિરણ બિંદુ પ્રસાર કાર્ય અનુસાર કેમેરાની લેન્સ પ્રણાલીમાં વિખેરાય છે. છબીઓમાં વિખેરાયેલા તીવ્રતા કાર્યના માપનમાંથી અનુરૂપ છબી બિંદુની પુનઃપ્રાપ્તિ ભૂલો આપે છે. ડિજિટલ કેમેરામાં, છબીની તીવ્રતાનું કાર્ય માત્ર સ્વતંત્ર સંવેદક ઘટકોમાં માપવામાં આવે છે. સાચા કાર્યને પુનઃપ્રાપ્ત કરવા માટે સ્વતંત્ર તીવ્રતા કાર્યના અચોક્કસ પ્રક્ષેપણનો ઉપયોગ કરવો પડશે. ત્રિકોણ માટે ઉપયોગમાં લેવાતા ચિત્ર બિંદુઓ y1 'અને y2' ઘણીવાર વિવિધ પ્રકારના લક્ષણ નિષ્કર્ષકોનો ઉપયોગ કરીને જોવા મળે છે, ઉદાહરણ તરીકે ખૂણાઓ અથવા સામાન્ય રીતે વ્યાજ બિંદુઓ. પડોશી કામગીરીના આધારે કોઈપણ પ્રકારની સુવિધા નિષ્કર્ષણ માટે અંતર્ગત સ્થાનિકીકરણની ભૂલ છે. પરિણામે, માપેલા છબી બિંદુઓ અને ને બદલે અને છે. જો કે, તેમની પ્રક્ષેપણ રેખાઓ (વાદળી) 3D જગ્યામાં છેદતી નથી અથવા x ની નજીક આવતી નથી. હકીકતમાં, આ રેખાઓ ત્યારે જ છેદે છે જ્યારે મૂળભૂત મેટ્રિક્સ દ્વારા વ્યાખ્યાયિત એપિપોલર અવરોધને સંતોષે છે. માપના ઘોંઘાટને જોતાં અને તે સંભવિત છે કે એપિપોલર અવરોધ સંતુષ્ટ નથી અને પ્રક્ષેપણ રેખાઓ એકબીજાને છેદતી નથી. આ અવલોકન એ સમસ્યા તરફ દોરી જાય છે જે ત્રિકોણમાં હલ થાય છે. આપેલ x નો અને કેમેરાની ભૂમિતિ નો શ્રેષ્ઠ અંદાજ કયો 3D પોઇન્ટ xest છે? જવાબ ઘણીવાર ભૂલ માપને વ્યાખ્યાયિત કરીને મળે છે જે xest પર આધાર રાખે છે અને પછી આ ભૂલને ઘટાડે છે. નીચેના વિભાગોમાં, સાહિત્યમાં પ્રસ્તુત કરવામાં આવેલી ઝેસ્ટની ગણતરી માટેની કેટલીક વિવિધ પદ્ધતિઓનું ટૂંકમાં વર્ણન કરવામાં આવ્યું છે. બધી ત્રિકોણ પદ્ધતિઓ એવા કિસ્સામાં xest = x ઉત્પન્ન કરે છે કે અને, એટલે કે, જ્યારે એપિપોલર અવરોધ સંતોષાય છે (એકવચન બિંદુઓ સિવાય, નીચે જુઓ). જ્યારે અવરોધ સંતોષાતો નથી ત્યારે તે થાય છે જે પદ્ધતિઓ વચ્ચે અલગ પડે છે. ગુણધર્મો ત્રિકોણ પદ્ધતિનું વર્ણન કાર્યની દ્રષ્ટિએ કરી શકાય છે જેમ કે શોધાયેલ છબી બિંદુઓના સજાતીય કોઓર્ડિનેટ્સ ક્યાં છે અને કેમેરા મેટ્રિક્સ ક્યાં છે. x (3D બિંદુ) એ પરિણામી 3D બિંદુનું સજાતીય પ્રતિનિધિત્વ છે. આ નિશાની સૂચવે છે કે માત્ર એક વેક્ટર ઉત્પન્ન કરવા માટે જરૂરી છે જે x ની બરાબર હોય અને બિન-શૂન્ય સ્કેલર દ્વારા ગુણાકાર થાય કારણ કે તેમાં સજાતીય વેક્ટર સામેલ હોય છે. ચોક્કસ પદ્ધતિઓ, એટલે કે ચોક્કસ કાર્યોને જોતા પહેલા, પદ્ધતિઓ સાથે સંબંધિત કેટલીક સામાન્ય વિભાવનાઓ છે જેને સમજાવવાની જરૂર છે. કોઈ ચોક્કસ સમસ્યા માટે કઈ ત્રિકોણ પદ્ધતિ પસંદ કરવામાં આવે છે તે અમુક અંશે આ લાક્ષણિકતાઓ પર આધાર રાખે છે. એકાત્મકતા કેટલીક પદ્ધતિઓ x (3D બિંદુ) ના અંદાજની યોગ્ય રીતે ગણતરી કરવામાં નિષ્ફળ જાય છે જો તે 3D જગ્યાના ચોક્કસ સબસેટમાં હોય, તો તેના કેટલાક સંયોજનને અનુરૂપ હોય છે. આ ઉપગણમાં એક બિંદુ પછી ત્રિકોણ પદ્ધતિની એકવચનતા છે. નિષ્ફળતાનું કારણ એ હોઈ શકે છે કે ઉકેલવાની કેટલીક સમીકરણ પ્રણાલી ઓછી નિર્ધારિત છે અથવા ઝેસ્ટની પ્રોજેક્ટિવ રજૂઆત એકવચન બિંદુઓ માટે શૂન્ય વેક્ટર બની જાય છે. કેટલીક એપ્લિકેશનોમાં, તે ઇચ્છનીય છે કે ત્રિકોણ 3D બિંદુઓને રજૂ કરવા માટે ઉપયોગમાં લેવાતી સંકલન પ્રણાલીથી સ્વતંત્ર હોય; જો ત્રિકોણની સમસ્યા એક સંકલન પ્રણાલીમાં ઘડવામાં આવે અને પછી બીજામાં રૂપાંતરિત થાય તો પરિણામી અંદાજ એ જ રીતે રૂપાંતરિત થવો જોઈએ. આ ગુણધર્મને સામાન્ય રીતે ઇનવેરિયન્સ તરીકે ઓળખવામાં આવે છે. દરેક ત્રિકોણ પદ્ધતિ અસ્થિરતાની ખાતરી આપતી નથી, ઓછામાં ઓછા સામાન્ય પ્રકારના સંકલન પરિવર્તન માટે નહીં. 3D કોઓર્ડિનેટ્સની સજાતીય રજૂઆત માટે, સૌથી સામાન્ય પરિવર્તન પ્રોજેક્ટિવ પરિવર્તન છે, જે મેટ્રિક્સ દ્વારા રજૂ થાય છે. જો સજાતીય કોઓર્ડિનેટ્સ અનુસાર રૂપાંતરિત થાય છે, તો સમાન સજાતીય છબી કોઓર્ડિનેટ્સ (yk) ઉત્પન્ન કરવા માટે કેમેરા મેટ્રિક્સને (Ck) તરીકે રૂપાંતરિત થવું આવશ્યક છે. જો એમ હોય તો, તે માત્ર પ્રોજેક્ટિવ પરિવર્તનના સબસેટ માટે સંતુષ્ટ થઈ શકે છે, ઉદાહરણ તરીકે, કઠોર અથવા એફાઇન પરિવર્તન. કોમ્પ્યુટેશનલ જટિલતા કાર્ય એ માત્ર ગણતરીની અમૂર્ત રજૂઆત છે, જે વ્યવહારમાં પ્રમાણમાં જટિલ હોઈ શકે છે. કેટલીક પદ્ધતિઓ એક બંધ-સ્વરૂપ સતત કાર્યમાં પરિણમે છે જ્યારે અન્યને કોમ્પ્યુટેશનલ પગલાઓની શ્રેણીમાં વિઘટિત કરવાની જરૂર છે, ઉદાહરણ તરીકે, એસવીડી અથવા બહુપદીના મૂળ શોધવા. પદ્ધતિઓનો બીજો વર્ગ પરિણમે છે જેમાં કેટલાક પરિમાણોના પુનરાવર્તિત અંદાજ પર આધાર રાખવો આવશ્યક છે. આનો અર્થ એ છે કે ગણતરીનો સમય અને તેમાં સામેલ કામગીરીની જટિલતા બંને વિવિધ પદ્ધતિઓ વચ્ચે બદલાઈ શકે છે. પદ્ધતિઓ મધ્ય-બિંદુ પદ્ધતિ બે છબીઓમાંથી દરેક નિર્દેશ કરે છે અને તેની અનુરૂપ પ્રક્ષેપણ રેખા (ઉપરની જમણી છબીમાં વાદળી) હોય છે, જેને અહીં અને તરીકે સૂચવવામાં આવે છે, જે કેમેરા મેટ્રિક્સને ધ્યાનમાં રાખીને નક્કી કરી શકાય છે. ધારો કે a (3D રેખા) L અને a x (3D બિંદુ) વચ્ચેનું અંતર કાર્ય એવું છે કે જે અને વચ્ચેનું યુક્લિડિયન અંતર છે. મધ્યબિંદુ પદ્ધતિ બિંદુ xest શોધે છે જે તેને ઘટાડે છે તે તારણ આપે છે કે xest બરાબર ટૂંકી રેખા ખંડની મધ્યમાં આવેલું છે જે બે પ્રક્ષેપણ રેખાઓને જોડે છે. આવશ્યક મેટ્રિક્સ દ્વારા સીધું રેખીય પરિવર્તન ત્યાં હલ કરવાની સમસ્યા એ છે કે અનુરૂપ સામાન્યીકૃત છબી કોઓર્ડિનેટ્સ અને કેવી રીતે ગણતરી કરવી. જો આવશ્યક મેટ્રિક્સ જાણીતું હોય અને અનુરૂપ પરિભ્રમણ અને અનુવાદ પરિવર્તન નક્કી કરવામાં આવ્યું હોય, તો આ અલ્ગોરિધમ (લોન્ગુએટ-હિગિન્સના પેપરમાં વર્ણવેલ) ઉકેલ પૂરો પાડે છે. ચાલો પરિભ્રમણ મેટ્રિક્સની પંક્તિ k ને દર્શાવીએઃ બે સંકલન પ્રણાલીઓમાં 3D કોઓર્ડિનેટ્સ વચ્ચેના ઉપરોક્ત સંબંધોનું સંયોજન અને અગાઉ વર્ણવેલ 3D અને 2D બિંદુઓ વચ્ચેનું મેપિંગ આપે છે અથવા એકવાર નક્કી થઈ જાય પછી, અન્ય બે કોઓર્ડિનેટ્સની ગણતરી કરી શકાય છે. આદર્શ કિસ્સામાં, જ્યારે કેમેરા સંપૂર્ણ પિનહોલ કેમેરા અનુસાર 3D બિંદુઓને મેપ કરે છે અને પરિણામી 2D બિંદુઓને કોઈપણ ઘોંઘાટ વિના શોધી શકાય છે, ત્યારે માટે અભિવ્યક્તિ સાથે શરૂઆત કરવી અને અભિવ્યક્તિ મેળવવી પણ શક્ય છે. વ્યવહારમાં, જોકે, તેઓ નથી અને બે અંદાજોને જોડવા માટે ફાયદાકારક હોઈ શકે છે, ઉદાહરણ તરીકે, અમુક પ્રકારની સરેરાશની દ્રષ્ટિએ. ઉપરોક્ત ગણતરીઓના અન્ય પ્રકારનાં વિસ્તરણ પણ છે જે શક્ય છે. તેઓએ પ્રાઈમ ઇમેજ કોઓર્ડિનેટ્સની અભિવ્યક્તિ સાથે શરૂઆત કરી અને અનપ્રાઇમ સિસ્ટમમાં 3D કોઓર્ડિનેટ્સ મેળવ્યા. અનપ્રાઈમ્ડ ઇમેજ કોઓર્ડિનેટ્સથી શરૂઆત કરવી અને પ્રાઈમ્ડ 3D કોઓર્ડિનેટ્સ મેળવવાનું પણ શક્ય છે, જેને આખરે અનપ્રાઈમ્ડ 3D કોઓર્ડિનેટ્સમાં રૂપાંતરિત કરી શકાય છે. ફરીથી, આદર્શ કિસ્સામાં પરિણામ ઉપરોક્ત અભિવ્યક્તિઓની બરાબર હોવું જોઈએ, પરંતુ વ્યવહારમાં તેઓ વિચલિત થઈ શકે છે. અંતિમ ટિપ્પણી એ હકીકત સાથે સંબંધિત છે કે જો આવશ્યક મેટ્રિક્સ અનુરૂપ છબી સંકલનથી નક્કી કરવામાં આવે છે, જે ઘણીવાર ત્યારે થાય છે જ્યારે 3D બિંદુઓ આ રીતે નક્કી કરવામાં આવે છે, અનુવાદ વેક્ટર માત્ર અજ્ઞાત હકારાત્મક સ્કેલિંગ સુધી જ ઓળખાય છે. પરિણામે, પુનઃનિર્મિત 3D બિંદુઓ પણ હકારાત્મક સ્કેલિંગના સંદર્ભમાં અનિશ્ચિત છે. બંડલ એડજસ્ટમેન્ટ લાઇન-લાઇન આંતરછેદના સંદર્ભો પણ જુઓ બાહ્ય કડીઓ કમ્પ્યુટર વિઝન સ્ટીરિયોફોટોગ્રામેટ્રીમાં મેટલેબ ભૂમિતિમાં બે દૃશ્ય અને બહુ-દૃશ્ય ત્રિકોણ