Кіріспе
Кескін жиектерін анықтау алгоритмі
Кенни жиектерді анықтау операторы – бұл кескіндердегі жиектердің кең ауқымын анықтау үшін көп сатылы алгоритмді пайдаланатын жиектерді анықтау операторы. Оны 1986 жылы Джон Ф. Кенни әзірлеген. Кенни сонымен қатар жиектерді анықтаудың есептеу теориясын жасады, ол осы техниканың неліктен жұмыс істейтінін түсіндіреді.
Гаусс сүзгісі
Барлық шеттік анықтау нәтижелері суреттегі шуға оңай бейімделетініне байланысты, жалған анықтамалардың алдын алу үшін шуды сүзгілеу өте маңызды. Суретті тегістеу үшін Гаусс сүзгісі ядросы суретпен конволюцияланады. Бұл қадам суретті сәл тегістеп, шеттік детектордағы көзге көрінетін шудың әсерін азайтады. (2k+1)×(2k+1) өлшемді Гаусс сүзгісі ядросының теңдеуі былай беріледі:
Мысалы, = 1 болғанда, іргелес суретті жасау үшін қолданылатын 5×5 Гаусс сүзгісі көрсетілген. (Жұлдызша конволюция операциясын білдіреді). Гаусс ядросының мөлшерін таңдау детектордың өнімділігіне әсер ететінін түсіну маңызды. Мөлшері үлкен болған сайын, детектордың шуға сезімталдығы төмендейді. Сонымен қатар, Гаусс сүзгісі ядросының мөлшері артқан сайын, шетті анықтаудағы локализация қатесі де сәл артады. Көптеген жағдайларда 5×5 мөлшері жақсы, бірақ бұл нақты жағдайларға байланысты өзгеруі мүмкін.
Градиенттік шаманың шекті деңгейі немесе төменгі шекті кесуді болдырмау
Градиенттік шамаларды азайтудың ең төменгі кесуі немесе төменгі шекті шектеу – бұл шеттерді жұқалау әдісі. Төменгі шекті кесуді басу интенсивтілік мәнінің ең күрт өзгерген жерлерін табу үшін қолданылады. Градиенттік кескіндегі әрбір пикселге арналған алгоритм: Ағымдағы пикселдің жиек күшін оң және теріс градиент бағыттарындағы пикселдің жиек күшімен салыстырыңыз. Егер ағымдағы пикселдің жиек күші сол бағыттағы маскадағы басқа пикселдерге қарағанда үлкен болса (мысалы, y бағытындағы пиксел вертикальді осьте оның үстіндегі және астындағы пикселмен салыстырылады), мән сақталады. Әйтпесе, мән басылады. Кейбір жағдайларда алгоритм үздіксіз градиент бағыттарын дискретті бағыттардың шағын жиынтығына жіктейді, содан кейін алдыңғы қадамның нәтижесіне (яғни, жиектің күші мен градиент бағыттарына) 3x3 сүзгісін жылжытады. Әрбір пикселде орталық пикселдің жиек күшін (оның мәнін 0-ге орнату арқылы) басып тастайды, егер оның шамасы градиент бағытындағы екі көршісінің шамасынан үлкен болмаса. Мысалы, егер дөңгеленген градиент бұрышы 0° болса (яғни, жиек солтүстік-оңтүстік бағытта болса), нүкте оның градиент шамасы шығыс және батыс бағыттарындағы пикселдердің шамасынан артық болса, жиекте деп есептеледі; егер дөңгеленген градиент бұрышы 90° болса (яғни, жиек шығыс-батыс бағытта болса), нүкте оның градиент шамасы солтүстік және оңтүстік бағыттарындағы пикселдердің шамасынан артық болса, жиекте деп есептеледі; егер дөңгеленген градиент бұрышы 135° болса (яғни, жиек солтүстік-шығыс-оңтүстік-батыс бағытта болса), нүкте оның градиент шамасы солтүстік-батыс және оңтүстік-шығыс бағыттарындағы пикселдердің шамасынан артық болса, жиекте деп есептеледі; егер дөңгеленген градиент бұрышы 45° болса (яғни, жиек солтүстік-батыс-оңтүстік-шығыс бағытта болса), нүкте оның градиент шамасы солтүстік-шығыс және оңтүстік-батыс бағыттарындағы пикселдердің шамасынан артық болса, жиекте деп есептеледі. Көбірек дәлдікке ие жағдайларда градиент бағытын қамтитын екі көрші пиксел арасында сызықтық интерполяция қолданылады. Мысалы, егер градиент бұрышы 89° мен 180° аралығында болса, солтүстік және солтүстік-шығыс пикселдеріндегі градиенттер арасындағы интерполяция бір интерполяцияланған мән береді, ал оңтүстік және оңтүстік-батыс пикселдер арасындағы интерполяция екінші мән береді (соңғы абзацтағы конвенцияларды пайдалана отырып). Орталық пикселдегі градиент шамасы оның жиек ретінде белгіленуі үшін осы екеуінен де үлкен болуы керек. Бағыттың таңбасы маңызды емес, яғни солтүстік-оңтүстік – оңтүстік-солтүстік сияқты және т.б.
Compare the edge strength of the current pixel with the edge strength of the pixel in the positive and negative gradient directions. If the edge strength of the current pixel is the largest compared to the other pixels in the mask with the same direction (e. g., a pixel that is pointing in the y direction will be compared to the pixel above and below it in the vertical axis), the value will be preserved. Otherwise, the value will be suppressed. In some implementations, the algorithm categorizes the continuous gradient directions into a small set of discrete directions, and then moves a 3x3 filter over the output of the previous step (that is, the edge strength and gradient directions). At every pixel, it suppresses the edge strength of the center pixel (by setting its value to 0) if its magnitude is not greater than the magnitude of the two neighbors in the gradient direction. For example,
if the rounded gradient angle is 0° (i. e. the edge is in the north–south direction) the point will be considered to be on the edge if its gradient magnitude is greater than the magnitudes at pixels in the east and west directions,
if the rounded gradient angle is 90° (i. e. the edge is in the east–west direction) the point will be considered to be on the edge if its gradient magnitude is greater than the magnitudes at pixels in the north and south directions,
if the rounded gradient angle is 135° (i. e. the edge is in the northeast–southwest direction) the point will be considered to be on the edge if its gradient magnitude is greater than the magnitudes at pixels in the north west and south east directions,
if the rounded gradient angle is 45° (i. e. the edge is in the northwest–southeast direction) the point will be considered to be on the edge if its gradient magnitude is greater than the magnitudes at pixels in the north east and south west directions. In more accurate implementations, linear interpolation is used between the two neighbouring pixels that straddle the gradient direction. For example, if the gradient angle is between 89° and 180°, interpolation between gradients at the north and north east pixels will give one interpolated value, and interpolation between the south and south west pixels will give the other (using the conventions of the last paragraph). The gradient magnitude at the central pixel must be greater than both of these for it to be marked as an edge. Note that the sign of the direction is irrelevant, i. e. north–south is the same as south–north and so on.
Екі еселенген шекті
Максималды емес басу қолданғаннан кейін қалған жиек пикселі кескіндегі нақты жиектерді дәлірек көрсетуге мүмкіндік береді. Дегенмен, шу мен түс өзгерісінен туындаған кейбір жиек пикселі қалады. Мұндай қате жауаптарды ескере отырып, әлсіз градиент мәніне ие жиек пиксельдерін сүзу және жоғары градиент мәніне ие жиек пиксельдерін сақтау қажет. Бұл жоғары және төменгі шекті мәндерді таңдау арқылы іске асырылады. Егер жиек пикселінің градиент мәні жоғары шекті мәннен жоғары болса, ол күшті жиек пикселі деп белгіленеді. Егер жиек пикселінің градиент мәні жоғары шекті мәннен кіші, бірақ төменгі шекті мәннен үлкен болса, ол әлсіз жиек пикселі деп белгіленеді. Егер жиек пикселінің градиент мәні төменгі шекті мәннен кіші болса, ол жойылды. Екі шекті мән эмпирикалық жолмен анықталады және олардың анықтамасы берілген кіріс кескінінің мазмұнына байланысты болады.
Гистерезис арқылы жиекті бақылау
Қатты жиек пиксельдері түпкілікті жиек кескінінде міндетті түрде болуы керек; олар кескіндегі нақты жиектерден пайда болған деп есептеледі. Дегенмен, әлсіз жиек пиксельдеріне қатысты пікірталас тууы мүмкін. Біз осы пиксельдердің нақты жиектен немесе шудан/түс өзгерістерінен пайда болғанын анықтауды қалаймыз. Егер олар шу немесе түс өзгерістерінен туындаса, әлсіз жиек пиксельдерін қарастырудан шығару керек. Бұл алгоритм нақты жиектерден шыққан әлсіз жиек пиксельдері (көбінесе) қатты жиек пикселімен байланысты болады, ал шудың әсері байланыссыз болады деген ойға негізделген. Жиек байланысын қадағалау үшін әлсіз жиек пикселі мен оның 8 көршілес пикселіне қарап блоб-талдау қолданылады. Блобқа бір қатты жиек пикселі қатысқанша, әлсіз жиек нүктесі сақталуға тиіс деп анықталады. Осы әлсіз жиек пиксельдері қатты жиектерге айналып, олардың көршілес әлсіз жиек пиксельдерін де сақтауға мүмкіндік береді.
Алгоритмді талдау
Бұл бөлім суреттің бес қадамның әрқайсысынан өту жолын көрсетеді.
Жағдайдың жақсаруы
Дәстүрлі Canny жиектерін анықтау әдісі жиектерді анықтау мәселесіне қатысты салыстырмалы түрде қарапайым, бірақ дәл методологияны ұсынады. Алайда, анықтаудың дәлдігі мен тұрақтылығына қатысты талаптар артқанда, дәстүрлі алгоритм мұндай қиын міндеттерді орындай алмайды. Дәстүрлі алгоритмнің негізгі кемшіліктерін былай қорытындылауға болады: шуды жою үшін Гаусс сүзгісі қолданылады, бірақ ол жиекті де тегістеп жібереді, ал жиек жоғары жиілікті ерекшелік ретінде қарастырылады. Бұл әлсіз жиектердің қанағаттандырылмауына және нәтижеде оқшауланған жиектердің пайда болуына әкеледі. Градиент амплитудасын есептеу үшін ескі Canny жиектерін анықтау алгоритмі градиент амплитудасын көрсету үшін шекті айырманың орташа мәнін есептеу үшін кішкентай 2x2 көршілік терезенің ортасын пайдаланады. Бұл әдіс шуға сезімтал, жалған жиектерді оңай анықтайды және нақты жиектерді жоғалтуы мүмкін. Дәстүрлі Canny жиектерін анықтау алгоритмінде жалған жиектерді сүзу үшін екі тұрақты жаһандық шекті мән қолданылады. Алайда, сурет күрделенген сайын, нақты жиектерді дәл табу үшін әртүрлі жергілікті аймақтарда әртүрлі шекті мәндер қажет болады. Сонымен қатар, жаһандық шекті мәндер дәстүрлі әдісте тәжірибелер арқылы қолмен анықталады, бұл көптеген әртүрлі суреттерді өңдеу қажет болғанда есептеулердің күрделілігіне әкеледі. Дәстүрлі анықтау нәтижесі әр жиек үшін бір жауаптың қанағаттанарлық жоғары дәлдігіне жете алмайды – көптеген жауаптар пайда болуы мүмкін. Осы кемшіліктерді жою мақсатында, келесі параграфтарда Canny жиектерін анықтау алгоритмін жетілдіру ұсынылады.
A Gaussian filter is applied to smooth out the noise, but it will also smooth the edge, which is considered as the high frequency feature. This will increase the possibility of missing weak edges, and the appearance of isolated edges in the result. For the gradient amplitude calculation, the old Canny edge detection algorithm uses the center in a small 2×2 neighborhood window to calculate the finite difference mean value to represent the gradient amplitude. This method is sensitive to noise and can easily detect false edges and lose real edges. In the traditional Canny edge detection algorithm, there will be two fixed global threshold values to filter out the false edges. However, as the image gets complex, different local areas will need very different threshold values to accurately find the real edges. In addition, the global threshold values are determined manually through experiments in the traditional method, which leads to a complexity of calculation when a large number of different images need to be dealt with. The result of the traditional detection cannot reach a satisfactory high accuracy of a single response for each edge multi point responses will appear. In order to address these defects, an improvement to the canny edge algorithm is presented in the following paragraphs.
Градиенттің шамасы мен бағытын есептеуді жақсарту
Градиенттің шамасы мен бағыты әртүрлі жиекті анықтау операторлары арқылы есептелуі мүмкін, ал оператордың таңдалуы нәтижелердің сапасына әсер етеді. Ең көп қолданылатыны – 3x3 Собель сүзгісі. Дегенмен, басқа сүзгілер де жақсырақ болуы мүмкін, мысалы, шуды азайтатын 5x5 Собель сүзгісі немесе жақсы айналмалы симметрияға ие Шарр сүзгісі. Превитт (Жоу қолданған) және Робертс Кросс та жиі қолданылады.
Екі деңгейлі шекті мәнді анықтаудың сенімді әдісі
Екілік шекті мәнді эмпирикалық жолмен анықтау қиындықтарын шешу үшін, Оцу әдісін ең жоғары емес басылған градиент шамасының кескініне қолданып, жоғары шекті мәнді анықтауға болады. Төменгі шекті мән әдетте жоғары шекті мәннің 1/2-сіне тең етіледі. Градиент шамасы кескіні жақсы анықталған максимумсыз үздіксіз мәндерге ие болғандықтан, Оцу әдісін толық гистограмманың орнына мән/сана жұптарын пайдалануға бейімдеу қажет.
Етістіктің жұқаруы
Дәстүрлі Canny жиектерін анықтау әдісі алғашқы екі критерийді орындау үшін жақсы нәтижелер береді, бірақ жиек бойындағы жалғыз жауапты қатаң түрде қамтамасыз етпейді. Маллат С. және Чжон анықталған жиекті жұқалау үшін математикалық морфология техникасын жасап шығарды.
Иілгіштерді қолдану
Қисықтар Гаусс сүзгісі мен градиентті бағалаудың орнына қолданылды, бұл кескіндегі жиектердің бағытын және күшін шамалайтын векторлық өрісті есептеуге мүмкіндік береді, содан кейін Кани алгоритмінің 3-5 қадамдары қолданылады. Қисықтар сигналды әртүрлі масштабтағы жеке компоненттерге жіктейді, ал ұсақ масштабтағы компоненттерді жою шуды азайтуға көмектеседі.
Дифференциалдық геометриялық формула
Субпикселдік дәлдікпен жиектерді алудың жетілдірілген тәсілі – дифференциалдық жиектерді анықтау әдісін қолдану болып табылады, онда максималды емес басу талабы масштабтық кеңістікте бейнеленген екінші және үшінші реттік туындылар арқылы формулировкаланады (Линдеберг, 1998) – толық сипаттама үшін жиектерді анықтау туралы мақаланы қараңыз.
Параметрлері
Канни алгоритмі есептеу уақытына және алгоритмнің тиімділігіне әсер ететін бірнеше реттелетін параметрлерді қамтиды. Гаусс сүзгісінің мөлшері: бірінші кезеңде қолданылатын тегістеу сүзгісі Канни алгоритмінің нәтижелеріне тікелей әсер етеді. Кішкентай сүзгілер аз көмескілендіруге себеп болады және кішкентай, анық сызықтарды анықтауға мүмкіндік береді. Үлкен сүзгі көбірек көмескілендіруді тудырады, белгілі бір пикселдің мәнін суреттің үлкен аймағына жайып жібереді. Үлкен көмескілендіру радиусы үлкен, тегіс жиектерді анықтау үшін тиімдірек, мысалы, радуганың жиегі сияқты. Шегілер: гистерезиспен екі шегіні қолдану, бір шегілі қолдануға қарағанда икемділікке мүмкіндік береді, бірақ шегіліге қатысты жалпы проблемалар әлі де қолданылады. Тым жоғары шегі орнатылса, маңызды ақпарат жіберіліп қалуы мүмкін. Ал, тым төмен шегі орнатылса, маңызсыз ақпаратты (мысалы, қылышты) қате анықтауы мүмкін. Барлық суреттер үшін жақсы жұмыс істейтін жалпы шегіні анықтау қиын. Осы мәселенің әлі толық сынақтан өткен шешімі жоқ.
Қорытынды
Канни алгоритмі әр түрлі ортаға бейімделеді. Оның параметрлері, нақты бір іске асырудың ерекше талаптарына қарай, әртүрлі сипаттағы жиектерді тануға мүмкіндік береді. Каннидің түпкілікті мақаласында оптималды сүзгіні табу нәтижесінде шекті импульстік жауап сүзгісі пайда болды, бірақ егер қажетті тегістеу деңгейі маңызды болса, кеңістіктік доменде оны есептеу баяу болуы мүмкін (мұндай жағдайда сүзгінің кеңістіктік қолдауы үлкен болады). Сондықтан, көбінесе Рашид Дерише ұсынған Канни сүзгісінің шексіз импульстік жауап түрін (Канни-Дерише детекторы) қолдану ұсынылады, ол рекурсивті және кез келген қажетті тегістеуге жеткілікті қысқа, белгілі бір уақыт ішінде есептелуі мүмкін. Бұл екінші форма FPGA немесе DSP-де, немесе өте жылдам кіріктірілген компьютерлерде нақты уақыт режимінде іске асыруға ыңғайлы. Дегенмен, Канни операторының стандартты рекурсивті іске асырылуы айналмалы симметрияны дұрыс жақындастырмайды, сондықтан ол көлденең және тік жиектерге қарай бұрылады.