🟠 Օբյեկտների հայտնաբերում
🤖
Այս խնդում մենք կգրենք ծրագիր, որը կհայտնաբերի նկարում առկա օբյեկտները։
Պատկերներում օբյեկտների հայտնաբերումը ունի լայն կիրառություն՝ բժշկության (օրինակ, քաղցկեղի հայտնաբերում), ռոբոտաշինության (ինքնագնաց մեքենաներ) և բազմաթիվ այլ ոլորտներում։
Օբյեկտները ընդգծելու համար հարկավոր է գտնել դրանց եզրերը։ Մինչև բուն ալգորիթմին անցնելը եկեք փորձենք հասկանալ, թե ի՞նչ եղանակով է հնարավոր գտնել օբյեկտի եզրերը։
💡
Ինտուիցիան հետևյալն է՝ օբյեկտի եզրի տարբեր կողմերում պատկերի գույները ամենայն հավանականությամբ իրարից կտրուկ տարբերվում են։
Գոյություն ունեն օբյեկտների հայտնաբերման տարբեր ալգորիթմներ։ Այս խնդրում մենք կփորձենք իրականացնել «
Սոբել օպերատոր» (Sobel operator) ալգորիթմը։ Ինչպես և «Blur» ֆիլտրի ալգորիթմը, Սոբել օպերատորը պիկսելի նոր արժեքը հաշվելիս, նույնպես օգտվում է իր անմիջական հարևաններից։ Այս ալգորիթմը պիկսելի յուրաքանչյուր գույնի համար հաշվում է երկու արժեք։ Առաջին արժեքը (այսուհետև կանվանենք X արժեք) հաշվում է տրված պիկսելի աջ և ձախ կողմերում գտնվող գույների տարբերությունը, երկրորդ արժեքը (այսուհետև կանվանենք Y արժեք)՝ վերևում և ներքևում գտնվող գույների տարբերությունը։ Այդ արժեքները հաշվելու համար, մենք կօգտվենք ստորև ներկայացված երկու` Gx, Gy մատրիցներից (գրականության մեջ այս մատրիցները ընդունված է անվանել կեռնելներ, kernel)։ 
Տրված պիկսելի 3 գույնների
X արժեքը հաշվելու համար, հարևան պիկսելների համապատասխան գույների արժեքները պետք է բազմապատկել Gx մատրիցի համապատասխան դիրքում գրաված արժեքով և ստացված թվերը գումարել իրար։ Օրինակ, 11-րդ դիրքում գտնվող պիկսելի գույնների X արժեքը կհաշվարկվի հետևյալ կերպ։Red11X = -1*Red6 + 0*Red7 + 1*Red8 + -2*Red10 + 0*Red11 + 2*Red12 + -1*Red14 + 0*Red15 + 1*Red16
Green11X = -1*Green6 + 0*Green7 + 1*Green8 + -2*Green10 + 0*Green11 + 2*Green12 + -1*Green14 + 0*Green15 + 1*Green16
Blue11X = -1*Blue6 + 0*Blue7 + 1*Blue8 + -2*Blue10 + 0*Blue11 + 2*Blue12 + -1*Blue14 + 0*Blue15 + 1*Blue16
Համապատասխանաբար ամեն գույնի համար Y արժեքը կհաշվարկվի հետևյալ կերպ՝
Red11Y = -1*Red6 + -2*Red7 + -1*Red8 + 0*Red10 + 0*Red11 + 0*Red12 + 1*Red14 + 2*Red15 + 1*Red16
Green11Y = -1*Green6 + 2*Green7 + -1*Green8 + 0*Green10 + 0*Green11 + 0*Green12 + 1*Green14 + 2*Green15 + 1*Green16
Blue11X = -1*Blue6 + 2*Blue7 + -1*Blue8 + 0*Blue10 + 0*Blue11 + 0*Blue12 + 1*Blue14+ 2*Blue15 + 1*Blue16Արդյունքում պիկսելի ամեն գույնի համար ստանում ենք 2 արժեք։ Գույնի վերջնական արժեքը որոշվում է նրա X և Y արժեքների համադրմամբ հետևյալ կերպ՝
Ձեր մոտ հավանաբար հարց կառաջանա, թե ինչու՞ Gx և Gy մատրիցները ունեն հենց այս արժեքները և ինչպե՞ս է այս ալգորիթմը օգնում ընդգծել օբյեկտների եզրերը։ Նորից հիշենք նախնական ենթադրությունը` օբյեկտի եզրի տարբեր կողմերում (աջ-ձախ, վերև-ներքև) պատկերի գույները ամենայն հավանականությամբ իրարից կտրուկ տարբերվում են։
Օգտագործելով Gx կեռնելը, մենք բազմապատկում ենք պիկսելից ձախ գտնվող գույների արժեքները բացասական թվերով, աջ գտնվողները՝ դրական թվով և այդ թվերը գումարում ենք իրար։ Եթե պիկսելից ձախ գտնվող գույները շատ չեն տարբերվում պիկսելից աջ գտնվող գույներից, ապա ստացած գումարը մոտ կլինի 0-ին (բացասական թվերը կգումարվեն իրենց համարյա հավասար դրական թվերին)։ Սա նշանակում է, որ այս կետում գույների կտրուկ փոփոխություն տեղի չունի և, որ այս պիկսելը դժվար թե հանդիսանա ինչ-որ օբյեկտի եզր։ Այդ պատճառով մենք կներկենք պիկսելը «սև» -ին մոտ գույնով։
Եթե պիկսելի աջ և ձախ կողմում գտնվող գույները իրարից շատ տարբեր են, գումարման արդյունքում, ընհակառակը, կստանանք մեծ թիվ (դրական կամ բացասական), ինչը կնշանակի, որ պատկերի այս կետի աջ և ձախ կողմերում տեղի ունի գույների կտրուկ տարբերություն։ Այդ տարբերությունը մեծ հավանականությամբ պայմանավորված է նրանով, որ տվյալ պիկսելը գտնվում է որևէ օբյեկտի եզրագծի վրա և այդ պիկսելը կներկվի վառ (սպիտակի մոտ) գույնով։
Նմանապես, ուղղահայաց ուղղությամբ բազմապատկելով Gy մատրիցով, մենք բազմապատկում ենք պիկսելից վերև գտնվող արժեքները բացասական թվով, ներքև գտնվողները՝ դրական թվով, ինչը թույլ է տալիս մեզ հայտնաբերել օբյեկտների հորիզոնական եզրերը։
ℹ️
Վերջնական նկարում այն պիկսելները, որոնք գտնվում են օբյեկտի եզրի վրա կունենան մեծ արժեքներ և կներկվեն ավելի «վառ» գույնով։ Իսկ մնացած պիկսելները կներկվեն սև կամ սևին շատ մոտ գույնով։
Ինչպես և
«blur» ֆիլտրի դեպքում, եթե պիկսելը գտնվում է պատկերի «սահմանի» վրա, հաշվարկին մասնակցում են միայն գոյություն ունեցող հարևանները։ Օրինակ, 15 համարի պիկսելի արժեքը հաշվելու համար հարկավոր է օգտագործել 10, 11, 12, 14, 15, 16 համարի պիկսելները։
⚠️
Տվյալ պահին տեխնիկական պատճառներով այս խնդրի ավոտմատ թեստավորումը անհասանելի է։ Ծրագիրը լոկալ թեստավորելու համար կարող եք օգնվել հետևյալ bmp ֆայլերից։։
Constraints
Time limit: 0.2 seconds
Memory limit: 512 MB
Output limit: 1 MB