Eight-point algorithm
આઠ-બિંદુ અલ્ગોરિધમ એ અનુરૂપ છબી બિંદુઓના સમૂહમાંથી સ્ટીરિયો કેમેરા જોડી સાથે સંબંધિત આવશ્યક મેટ્રિક્સ અથવા મૂળભૂત મેટ્રિક્સનો અંદાજ કાઢવા માટે કમ્પ્યુટર દ્રષ્ટિમાં ઉપયોગમાં લેવાતું એક અલ્ગોરિધમ છે. તે ક્રિસ્ટોફર લોંગ્યુએટ-હિગિન્સ દ્વારા 1981 માં આવશ્યક મેટ્રિક્સના કિસ્સામાં રજૂ કરવામાં આવ્યું હતું. સિદ્ધાંતમાં, આ અલ્ગોરિધમનો ઉપયોગ મૂળભૂત મેટ્રિક્સ માટે પણ થઈ શકે છે, પરંતુ વ્યવહારમાં રિચાર્ડ હાર્ટલી દ્વારા 1997માં વર્ણવેલ સામાન્યીકૃત આઠ-બિંદુ અલ્ગોરિધમ આ કેસ માટે વધુ યોગ્ય છે. અલ્ગોરિધમનું નામ એ હકીકત પરથી આવ્યું છે કે તે આઠ (અથવા વધુ) અનુરૂપ છબી બિંદુઓના સમૂહમાંથી આવશ્યક મેટ્રિક્સ અથવા મૂળભૂત મેટ્રિક્સનો અંદાજ કાઢે છે. જો કે, અલ્ગોરિધમનો ઉપયોગ આઠથી ઓછા બિંદુઓ માટે થઈ શકે છે. કોપ્લેનેરિટી અવરોધ એક બીજગણિત સમીકરણ સાથે બે કેમેરાની એપિપોલર ભૂમિતિ અને અવકાશમાં એક બિંદુને વ્યક્ત કરી શકે છે. અવલોકન કરો કે, અવકાશમાં બિંદુ ગમે ત્યાં હોય, વાહક અને તે જ સમતલના હોય છે. ડાબી આંખની સંદર્ભ ફ્રેમમાં બિંદુના કોઓર્ડિનેટ્સને કૉલ કરો અને જમણી આંખની સંદર્ભ ફ્રેમમાં બિંદુના કોઓર્ડિનેટ્સને કૉલ કરો અને બે સંદર્ભ ફ્રેમ વચ્ચે પરિભ્રમણ અને અનુવાદને કૉલ કરો. બે સંદર્ભ ફ્રેમમાંના કોઓર્ડિનેટ્સ વચ્ચેનો સંબંધ છે. નીચેનું સમીકરણ હંમેશા રહે છે કારણ કે તેમાંથી પેદા થયેલ વેક્ટર બંને માટે ઓર્થોગોનલ છે અનેઃ કારણ કે, આપણને મળે છે. સાથે બદલીને, આપણને અવલોકન મળે છે જેને મેટ્રિક્સ તરીકે માનવામાં આવે છે; લોંગ્યુએટ-હિગિન્સે તેને દર્શાવવા માટે પ્રતીકનો ઉપયોગ કર્યો હતો. ઉત્પાદનને ઘણીવાર આવશ્યક મેટ્રિક્સ કહેવામાં આવે છે અને તેની સાથે દર્શાવવામાં આવે છે. વેક્ટર વેક્ટરની સમાંતર હોય છે અને તેથી જો આપણે આ વેક્ટરને બદલીએ તો કોપ્લાનારીટી અવરોધ રહે છે. જો આપણે ડાબા અને જમણા ઇમેજ પ્લેન પરના અંદાજોના કોઓર્ડિનેટ્સને કૉલ કરીએ, તો કોપ્લાનારીટી અવરોધને બેઝિક અલ્ગોરિધમ તરીકે લખી શકાય છે મૂળભૂત આઠ-પોઇન્ટ અલ્ગોરિધમ અહીં આવશ્યક મેટ્રિક્સના અંદાજના કેસ માટે વર્ણવવામાં આવ્યું છે. તેમાં ત્રણ પગલાં હોય છે. પ્રથમ, તે એક સજાતીય રેખીય સમીકરણ બનાવે છે, જ્યાં ઉકેલ સીધો સંબંધિત હોય છે, અને પછી સમીકરણને ઉકેલે છે, તે ધ્યાનમાં રાખીને કે તેનો ચોક્કસ ઉકેલ ન હોઈ શકે. છેવટે, પરિણામી મેટ્રિક્સની આંતરિક મર્યાદાઓનું સંચાલન કરવામાં આવે છે. પ્રથમ પગલું લોંગ્યુએટ-હિગિન્સના પેપરમાં વર્ણવવામાં આવ્યું છે, બીજા અને ત્રીજા પગલાં અંદાજ સિદ્ધાંતમાં પ્રમાણભૂત અભિગમો છે. આવશ્યક મેટ્રિક્સ દ્વારા વ્યાખ્યાયિત અવરોધ સામાન્યીકૃત છબી કોઓર્ડિનેટ્સમાં રજૂ થયેલ અનુરૂપ છબી બિંદુઓ માટે છે. અલ્ગોરિધમ જે સમસ્યાનું સમાધાન કરે છે તે મેળ ખાતા છબી બિંદુઓના સમૂહ માટે નક્કી કરવાનું છે. વ્યવહારમાં, છબી બિંદુઓના છબી કોઓર્ડિનેટ્સ ઘોંઘાટથી પ્રભાવિત થાય છે અને ઉકેલ પણ વધુ પડતો નિર્ધારિત થઈ શકે છે, જેનો અર્થ એ છે કે ઉપરોક્ત અવરોધને બધા બિંદુઓ માટે બરાબર સંતોષે છે તે શોધવું શક્ય નથી. આ મુદ્દાને અલ્ગોરિધમનોના બીજા તબક્કામાં સંબોધવામાં આવ્યો છે. પગલું 1: અને સાથે સજાતીય રેખીય સમીકરણની રચના કરવી અને અવરોધને અથવા ક્યાં અને એટલે કે, 9-પરિમાણીય વેક્ટરના સ્વરૂપમાં આવશ્યક મેટ્રિક્સને રજૂ કરે છે અને આ વેક્ટર વેક્ટર માટે ઓર્થોગોનલ હોવો જોઈએ જેને મેટ્રિક્સના વેક્ટર પ્રતિનિધિત્વ તરીકે જોઈ શકાય છે. અનુરૂપ છબી બિંદુઓની દરેક જોડી વેક્ટર ઉત્પન્ન કરે છે. 3D બિંદુઓના સમૂહને જોતાં આ વેક્ટરના સમૂહને અનુરૂપ છે અને તે બધાએ વેક્ટર માટે સંતોષ કરવો જ જોઇએ. પૂરતા પ્રમાણમાં ઘણા (ઓછામાં ઓછા આઠ) રેખીય રીતે સ્વતંત્ર વેક્ટરને જોતાં તે સીધી રીતે નક્કી કરવું શક્ય છે. બધા વેક્ટરને મેટ્રિક્સના સ્તંભો તરીકે એકત્રિત કરો અને તે પછી એવું હોવું જોઈએ કે આનો અર્થ એ છે કે તે સજાતીય રેખીય સમીકરણનો ઉકેલ છે. પગલું 2: સમીકરણને ઉકેલવું આ સમીકરણને ઉકેલવા માટેનો એક પ્રમાણભૂત અભિગમ સૂચવે છે કે તે એકવચન મૂલ્યને અનુરૂપ એક જમણો એકવચન વેક્ટર છે જે શૂન્ય બરાબર છે. જો કે તેની રચના કરવા માટે ઓછામાં ઓછા આઠ રેખીય સ્વતંત્ર વેક્ટરનો ઉપયોગ કરવામાં આવે તો તે અનુસરે છે કે આ એકવચન વેક્ટર અનન્ય છે (સ્કેલર ગુણાકારને અવગણીને) અને પરિણામે, અને પછી નક્કી કરી શકાય છે. જો નિર્માણ માટે આઠથી વધુ અનુરૂપ બિંદુઓનો ઉપયોગ કરવામાં આવે તો શક્ય છે કે તેનું શૂન્ય બરાબર કોઈ એકવચન મૂલ્ય ન હોય. આ કેસ વ્યવહારમાં ત્યારે થાય છે જ્યારે છબીના કોઓર્ડિનેટ્સ વિવિધ પ્રકારના ઘોંઘાટથી પ્રભાવિત થાય છે. આ પરિસ્થિતિનો સામનો કરવા માટેનો એક સામાન્ય અભિગમ એ છે કે તેને કુલ લઘુત્તમ ચોરસ સમસ્યા તરીકે વર્ણવવી; શોધો કે જે ક્યારે ઘટાડે છે. તેનો ઉકેલ એ છે કે સૌથી નાના એકવચન મૂલ્યને અનુરૂપ ડાબી બાજુના એકવચન વેક્ટર તરીકે પસંદ કરવું. આને મેટ્રિક્સમાં ફરીથી ગોઠવવાથી આ પગલાનું પરિણામ મળે છે, જેને અહીં તરીકે ઓળખવામાં આવે છે. પગલું 3: આંતરિક અવરોધ લાગુ કરવો ઘોંઘાટીયા ઇમેજ કોઓર્ડિનેટ્સ સાથે વ્યવહાર કરવાનું બીજું પરિણામ એ છે કે પરિણામી મેટ્રિક્સ આવશ્યક મેટ્રિક્સની આંતરિક અવરોધને સંતોષી શકશે નહીં, એટલે કે, તેના બે એકવચન મૂલ્યો સમાન અને બિન-શૂન્ય છે અને અન્ય શૂન્ય છે. એપ્લિકેશનના આધારે, આંતરિક અવરોધમાંથી નાના અથવા મોટા વિચલનો સમસ્યા હોઈ શકે છે અથવા ન પણ હોઈ શકે. જો તે મહત્વપૂર્ણ છે કે અંદાજિત મેટ્રિક્સ આંતરિક અવરોધોને સંતોષે છે, તો આ ક્રમ 2 નો મેટ્રિક્સ શોધીને પૂર્ણ કરી શકાય છે જે ઘટાડે છે કે જ્યાં પગલું 2 માંથી પરિણામી મેટ્રિક્સ છે અને ફ્રોબેનિયસ મેટ્રિક્સ ધોરણનો ઉપયોગ થાય છે. સમસ્યાનો ઉકેલ સૌપ્રથમ એકવચન મૂલ્યના વિઘટનની ગણતરી કરીને આપવામાં આવે છેઃ જ્યાં ઓર્થોગોનલ મેટ્રિક્સ છે અને તે એક કર્ણ મેટ્રિક્સ છે જે એકવચન મૂલ્યો ધરાવે છે. આદર્શ કિસ્સામાં, એક કર્ણ તત્વ શૂન્ય હોવું જોઈએ, અથવા અન્ય બેની સરખામણીમાં ઓછામાં ઓછું નાનું હોવું જોઈએ જે સમાન હોવું જોઈએ. કોઈ પણ સંજોગોમાં, અનુક્રમે સૌથી મોટા અને બીજા સૌથી મોટા એકવચન મૂલ્યો ક્યાં છે તે સેટ કરો. છેવટે, મેટ્રિક્સ દ્વારા આપવામાં આવે છે મેટ્રિક્સ એ અલ્ગોરિધમ દ્વારા પૂરા પાડવામાં આવેલ આવશ્યક મેટ્રિક્સનો પરિણામી અંદાજ છે. સામાન્યીકૃત અલ્ગોરિધમ મૂળભૂત આઠ-બિંદુ અલ્ગોરિધમનો સૈદ્ધાંતિક રીતે મૂળભૂત મેટ્રિક્સનો અંદાજ કાઢવા માટે પણ ઉપયોગ કરી શકાય છે. માટે વ્યાખ્યાયિત અવરોધ એ છે કે અનુરૂપ છબી કોઓર્ડિનેટ્સની સજાતીય રજૂઆતો ક્યાં છે (જરૂરી સામાન્યકૃત નથી). આનો અર્થ એ છે કે આવશ્યક મેટ્રિક્સની જેમ જ મેટ્રિક્સ બનાવવું અને સમીકરણને ઉકેલવું શક્ય છે, જેના માટે તેનું ફરીથી આકાર આપવામાં આવ્યું છે. ઉપર દર્શાવેલ પ્રક્રિયાને અનુસરીને, પછી આઠ મેળ ખાતા બિંદુઓના સમૂહમાંથી નક્કી કરવું શક્ય છે. વ્યવહારમાં, જોકે, પરિણામી મૂળભૂત મેટ્રિક્સ એપિપોલર અવરોધો નક્કી કરવા માટે ઉપયોગી ન પણ હોઈ શકે. મુશ્કેલી સમસ્યા એ છે કે પરિણામે ઘણીવાર ખરાબ સ્થિતિ હોય છે. સિદ્ધાંતમાં, એક એકવચન મૂલ્ય શૂન્યની બરાબર હોવું જોઈએ અને બાકીના બિન-શૂન્ય હોવા જોઈએ. વ્યવહારમાં, જોકે, કેટલાક બિન-શૂન્ય એકવચન મૂલ્યો મોટા મૂલ્યોની સરખામણીમાં નાના બની શકે છે. જો રચના કરવા માટે આઠથી વધુ અનુરૂપ બિંદુઓનો ઉપયોગ કરવામાં આવે, જ્યાં કોઓર્ડિનેટ્સ માત્ર લગભગ સાચા હોય, તો ત્યાં સારી રીતે વ્યાખ્યાયિત એકવચન મૂલ્ય ન પણ હોઈ શકે જેને લગભગ શૂન્ય તરીકે ઓળખી શકાય. પરિણામે, સમીકરણોની સજાતીય રેખીય પદ્ધતિનો ઉકેલ ઉપયોગી થવા માટે પૂરતો સચોટ ન પણ હોઈ શકે. કોઝ હાર્ટલીએ તેમના 1997 ના લેખમાં આ અંદાજની સમસ્યાને સંબોધિત કરી હતી. સમસ્યાનું તેમનું વિશ્લેષણ દર્શાવે છે કે સમસ્યા તેમની જગ્યામાં સજાતીય છબી કોઓર્ડિનેટ્સના નબળા વિતરણને કારણે છે. 2ડી ઇમેજ કોઓર્ડિનેટની એક લાક્ષણિક સજાતીય રજૂઆત એ છે કે જ્યાં બંને આધુનિક ડિજિટલ કેમેરા માટે 0 થી 1000-2000 ની શ્રેણીમાં આવેલા છે. આનો અર્થ એ છે કે પ્રથમ બે કોઓર્ડિનેટ્સ ત્રીજા કોઓર્ડિનેટ્સ કરતાં ઘણી મોટી રેન્જમાં બદલાય છે. વધુમાં, જો છબીના નિર્માણ માટે ઉપયોગમાં લેવાતા બિંદુઓ છબીના પ્રમાણમાં નાના પ્રદેશમાં આવેલા હોય, ઉદાહરણ તરીકે, ફરીથી વેક્ટર તમામ બિંદુઓ માટે વધુ કે ઓછા સમાન દિશામાં નિર્દેશ કરે છે. પરિણામે, એક મોટું એકવચન મૂલ્ય હશે અને બાકીનું નાનું હશે. ઉકેલ આ સમસ્યાના ઉકેલ તરીકે, હાર્ટલીએ દરખાસ્ત કરી હતી કે બે છબીઓમાંથી દરેકની સંકલન પ્રણાલીને સ્વતંત્ર રીતે, નીચેના સિદ્ધાંત અનુસાર નવી સંકલન પ્રણાલીમાં રૂપાંતરિત કરવી જોઈએ. નવી સંકલન પ્રણાલીની ઉત્પત્તિ છબી બિંદુઓના કેન્દ્રબિંદુ (ગુરુત્વાકર્ષણનું કેન્દ્ર) પર કેન્દ્રિત હોવી જોઈએ (તેનું મૂળ હોવું જોઈએ). મૂળ મૂળમાંથી નવા મૂળના અનુવાદ દ્વારા આ પરિપૂર્ણ થાય છે. અનુવાદ પછી કોઓર્ડિનેટ્સને સમાન રીતે માપવામાં આવે છે જેથી મૂળથી બિંદુઓ સુધીના અંતરનો સરેરાશ સરખો થાય. આ સિદ્ધાંત, સામાન્ય રીતે, બે છબીઓમાંથી દરેક માટે એક અલગ સંકલન પરિવર્તનમાં પરિણમે છે. પરિણામે, નવા સજાતીય છબી કોઓર્ડિનેટ્સ જૂનાથી નવા સામાન્યકૃત છબી કોઓર્ડિનેટ્સમાં પરિવર્તન (અનુવાદ અને સ્કેલિંગ) ક્યાં છે તેના દ્વારા આપવામાં આવે છે. આ સામાન્યીકરણ માત્ર છબી બિંદુઓ પર આધારિત છે જેનો ઉપયોગ એક જ છબીમાં થાય છે અને સામાન્ય રીતે, સામાન્યકૃત કેમેરા દ્વારા ઉત્પાદિત સામાન્યીકૃત છબી કોઓર્ડિનેટ્સથી અલગ છે. મૂળભૂત મેટ્રિક્સ પર આધારિત એપિપોલર અવરોધને હવે ક્યાં તરીકે ફરીથી લખી શકાય છે. આનો અર્થ એ છે કે ઉપર વર્ણવેલ મૂળભૂત આઠ-બિંદુ અલ્ગોરિધમનો ઉપયોગ કરીને રૂપાંતરિત મૂળભૂત મેટ્રિક્સનો અંદાજ કાઢવા માટે સામાન્યીકૃત સજાતીય છબી કોઓર્ડિનેટ્સનો ઉપયોગ કરવો શક્ય છે. સામાન્યીકરણ પરિવર્તનોનો હેતુ એ છે કે સામાન્યીકૃત છબી કોઓર્ડિનેટ્સથી બનેલા મેટ્રિક્સ, સામાન્ય રીતે, તેના કરતા વધુ સારી સ્થિતિ સંખ્યા ધરાવે છે. આનો અર્થ એ છે કે ઉકેલ તેની સાપેક્ષ કરતાં સજાતીય સમીકરણના ઉકેલ તરીકે વધુ સારી રીતે વ્યાખ્યાયિત છે. એકવાર નક્કી થઈ ગયા પછી અને પછીનામાં ફરીથી આકાર આપવામાં આવે તો સામાન્ય રીતે, મૂળભૂત મેટ્રિક્સનો આ અંદાજ બિન-સામાન્ય કોઓર્ડિનેટ્સમાંથી અંદાજ દ્વારા મેળવવામાં આવ્યો હોત તેના કરતા વધુ સારો છે. આઠથી ઓછા બિંદુઓનો ઉપયોગ કરીને દરેક બિંદુ જોડી તત્વ પર એક અવરોધક સમીકરણ સાથે ફાળો આપે છે. પાંચ ડિગ્રી ઓફ ફ્રીડમ હોવાથી તે નક્કી કરવા માટે માત્ર પાંચ બિંદુ જોડીઓ સાથે પૂરતું હોવું જોઈએ. ડેવિડ નિસ્ટરે પાંચ જોડીદાર બિંદુઓના સમૂહમાંથી આવશ્યક મેટ્રિક્સનો અંદાજ કાઢવા માટે એક કાર્યક્ષમ ઉકેલ રજૂ કર્યો, જેને પાંચ-બિંદુ અલ્ગોરિધમ તરીકે ઓળખવામાં આવે છે. હાર્ટલી એટ. અલ. બાદમાં તેમણે નીસ્ટરના અલ્ગોરિધમ પર આધારિત સુધારેલા અને વધુ સ્થિર પાંચ-બિંદુ અલ્ગોરિધમનો પ્રસ્તાવ મૂક્યો. આવશ્યક મેટ્રિક્સ મૂળભૂત મેટ્રિક્સ ત્રિફોકલ ટેન્સર સંદર્ભો પણ જુઓ કમ્પ્યુટર દ્રષ્ટિમાં વધુ વાંચન ભૂમિતિ