Кіріспе
Суреттердегі пішіндерді анықтау әдісі
Хоуф трансформациясы – суреттерді талдау, компьютерлік көру және цифрлық сурет өңдеуде қолданылатын ерекшеліктерді анықтау техникасы. Бұл техниканың мақсаты – белгілі бір пішін класына жататын нысандардың толық емес үлгілерін дауыс беру процедурасы арқылы табу болып табылады. Бұл дауыс беру процедурасы параметрлік кеңістікте жүзеге асырылады, нәтижесінде Хоуф трансформациясын есептеу алгоритмімен нақты құрылатын аккумулятор кеңістігіндегі жергілікті максимумдар нысан үміткерлері ретінде алынады. Классикалық Хоуф трансформациясы суреттегі түзу сызықтарды анықтаумен айналысты, бірақ кейіннен Хоуф трансформациясы кез келген пішіннің, ең көп кездесетіні шеңберлер немесе эллипстердің орналасуын анықтау үшін кеңейтілді. Қазіргі таңдағы Хоуф трансформациясын 1972 жылы Ричард Дуда мен Питер Харт ойлап тапты және оны Пауль Хоуфтың 1962 жылғы патентіне сілтеме жасай отырып, "жалпыланған Хоуф трансформациясы" деп атады. Хоуф трансформациясын компьютерлік көру қауымдастығында Дана Х. Баллард 1981 жылғы "Кез келген пішіндерді анықтау үшін Хоуф трансформациясын жалпылау" атты мақаласы арқылы танымал етті.
Теория
Цифрлық суреттерді автоматтандырылған талдау кезінде, көбінесе тура сызықтар, шеңберлер немесе эллипстер сияқты қарапайым пішіндерді анықтау мәселесі туындайды. Көп жағдайда, суреттегі қажетті қисықтағы сурет нүктелерін немесе пиксельдерін алу үшін шеттік детекторды алдын ала өңдеу кезеңі ретінде қолдануға болады. Алайда, сурет деректерінің немесе шеттік детектордың жетілмеуі салдарынан, қажетті қисықтарда нүктелер немесе пиксельдердің жоқтығы мүмкін, сондай-ақ идеалды сызық/шеңбер/эллипс пен шеттік детектордан алынған шулы шеттік нүктелер арасында кеңістіктік ауытқулар болуы мүмкін. Осы себептерге байланысты, алынған шеттік ерекшеліктерді тиісті сызықтар, шеңберлер немесе эллипстер жиынтығына топтастыру көбінесе қиындық тудырады. Хоуф түрлендіруінің мақсаты – осы мәселені шешу, параметрленген сурет объектілері жиынтығы бойынша ашық дауыс беру процедурасын жүргізу арқылы шеттік нүктелерді объектілерге топтастыруға мүмкіндік беру болып табылады (Шапиро және Стокман, 304).
Желілерді анықтау
Хоуф түрлендіруінің ең қарапайым жағдайы – түзу сызықтарды анықтау. Жалпы, түзу сызықты параметрлік кеңістікте (b, m) нүктесі ретінде көрсетуге болады. Дегенмен, тік сызықтар мәселе тудырады. Олар еңіс параметрі m-нің шексіз мәндерін береді. Сондықтан, есептеу себептерімен байланысты, Дуда мен Харт Гессе нормалық түрін қолдануды ұсынды:
where is the distance from the origin to the closest point on the straight line, and is the angle between the axis and the line connecting the origin with that closest point. The intuition for this form, similarly to the plane equation, is that every vector on the line must be perpendicular (orthogonal) to the straight line of length that comes from the origin. It can be seen that the intersection point of the function line and the perpendicular line that comes from the origin is at So, for any point on the line, the vector must be orthogonal to the vector Therefore, we get that for any point on the function line, the equation must be satisfied. Therefore, Since and , we get Since , we get the final form of
It is therefore possible to associate with each line of the image a pair The plane is sometimes referred to as Hough space for the set of straight lines in two dimensions. This representation makes the Hough transform conceptually very close to the two dimensional Radon transform. In fact, the Hough transform is mathematically equivalent to the Radon transform, but the two transformations have different computational interpretations traditionally associated with them. Given a single point in the plane, the set of all straight lines going through that point corresponds to a sinusoidal curve in the (r, θ) plane, which is unique to that point. A set of two or more points that form a straight line will produce sinusoids crossing at the (r, θ) for that line. Thus, the problem of detecting collinear points can be converted to the problem of finding concurrent curves.
мұндағы – түзу сызықтағы ең жақын нүктеден бастапқы нүктеге дейінгі қашықтық, ал – координата осі мен бастапқы нүктеден ең жақын нүктеге дейінгі сызық арасындағы бұрыш. Бұл форманың түсінігі, жазықтық теңдеуіне ұқсас, түзу сызықтағы әрбір вектор бастапқы нүктеден келетін ұзындығы болатын түзу сызыққа перпендикуляр (ортогональ) болуы керек. Функциялық сызық пен бастапқы нүктеден келетін перпендикуляр сызықтың қиылысу нүктесі болады. Демек, сызықтың кез келген нүктесі үшін вектор векторына ортогональ болуы керек. Сондықтан, функциялық сызықтың кез келген нүктесі үшін теңдеу орындалуы тиіс. Сондықтан, егер және болса, онда болады. Егер болса, онда түрінің соңғы түрін аламыз.
where is the distance from the origin to the closest point on the straight line, and is the angle between the axis and the line connecting the origin with that closest point. The intuition for this form, similarly to the plane equation, is that every vector on the line must be perpendicular (orthogonal) to the straight line of length that comes from the origin. It can be seen that the intersection point of the function line and the perpendicular line that comes from the origin is at So, for any point on the line, the vector must be orthogonal to the vector Therefore, we get that for any point on the function line, the equation must be satisfied. Therefore, Since and , we get Since , we get the final form of
It is therefore possible to associate with each line of the image a pair The plane is sometimes referred to as Hough space for the set of straight lines in two dimensions. This representation makes the Hough transform conceptually very close to the two dimensional Radon transform. In fact, the Hough transform is mathematically equivalent to the Radon transform, but the two transformations have different computational interpretations traditionally associated with them. Given a single point in the plane, the set of all straight lines going through that point corresponds to a sinusoidal curve in the (r, θ) plane, which is unique to that point. A set of two or more points that form a straight line will produce sinusoids crossing at the (r, θ) for that line. Thus, the problem of detecting collinear points can be converted to the problem of finding concurrent curves.
Осылайша, бейнедегі әрбір сызыққа (r, θ) жұпты сәйкестендіруге болады. Екі өлшемдегі түзу сызықтар жиынтығы үшін жазықтық кейде Хоуф кеңістігі деп аталады. Бұл бейнелеу Хоуф түрлендіруін екі өлшемді Радон түрлендіруіне тұжырымдық жағынан жақын етеді. Шындығында, Хоуф түрлендіруі математикалық тұрғыдан Радон түрлендіруіне тең, бірақ екі түрлендірудің дәстүрлі түрде олармен байланысты әртүрлі есептеулік интерпретациялары бар. Жазықтағы бір нүкте берілген жағдайда, сол нүктеден өтетін барлық түзу сызықтар жиынтығы (r, θ) жазықтықтағы синусоидалық қисыққа сәйкес келеді, бұл қисық сол нүктеге тән. Екі немесе одан көп нүктеден тұратын түзу сызық жиынтығы сол сызықтың (r, θ) нүктесінде қиылысатын синусоидаларды тудырады. Осылайша, коллинеарлық нүктелерді анықтау мәселесін бірдей қисықтарды табу мәселесіне келтіруге болады.
where is the distance from the origin to the closest point on the straight line, and is the angle between the axis and the line connecting the origin with that closest point. The intuition for this form, similarly to the plane equation, is that every vector on the line must be perpendicular (orthogonal) to the straight line of length that comes from the origin. It can be seen that the intersection point of the function line and the perpendicular line that comes from the origin is at So, for any point on the line, the vector must be orthogonal to the vector Therefore, we get that for any point on the function line, the equation must be satisfied. Therefore, Since and , we get Since , we get the final form of
It is therefore possible to associate with each line of the image a pair The plane is sometimes referred to as Hough space for the set of straight lines in two dimensions. This representation makes the Hough transform conceptually very close to the two dimensional Radon transform. In fact, the Hough transform is mathematically equivalent to the Radon transform, but the two transformations have different computational interpretations traditionally associated with them. Given a single point in the plane, the set of all straight lines going through that point corresponds to a sinusoidal curve in the (r, θ) plane, which is unique to that point. A set of two or more points that form a straight line will produce sinusoids crossing at the (r, θ) for that line. Thus, the problem of detecting collinear points can be converted to the problem of finding concurrent curves.
Ықтималдық интерпретация
Пішінді параметрленген , пішін кеңістігі деп аталатын жиынтықтағы мәндерді қабылдай отырып, Хоуг түрлендіруін бейне кеңістігінен пішін кеңістігіне жүргізілетін кері түрлендіру ретінде қарастыруға болады, ал пішіннің анықталуын – максималды ықтималдықпен бағалау ретінде түсіндіруге болады. Нақтырақ айтқанда, Хоуг түрлендіруі шамамен наив Байес қорытындысын жүзеге асырады. Біз пішін кеңістігінде біркелкі алдын ала таралыммен бастаймыз. Біз тек оң деректерді ғана қарастырамыз және барлық теріс деректерді назардан тыс қалдырамыз, осылайша жартылай жасырылған пішіндерді анықтай аламыз. Пішін кеңістігіндегі логарифмдік ықтималдықты белгілі бір тұрақтыға дейін қосамыз. Наив Байес болжамы бойынша, бейне кеңістігіндегі барлық пиксельдер тәуелсіз деректер ұсынады, сондықтан олардың ықтималдықтары көбейтіледі, яғни олардың логарифмдік ықтималдықтары қосылады. Қосымша тұрақтыдағы еркіндік пішін кеңістігіндегі "фондық пиксельдерге" ешқандай операция жасауға мүмкіндік береді. Соңында, біз пішін кеңістігіндегі логарифмдік ықтималдықтың жоғарғы нүктелерін таңдау арқылы максималды ықтималдықпен бағалауды жүзеге асырамыз.
Іске асыру
Сызықтық Хоуф түрлендіру алгоритмі тура сызықты анықтайтын екі параметрді бағалайды. Түрлендіру кеңістігі екі өлшемді, және түрлендіру кеңістігіндегі әрбір нүкте аккумулятор ретінде қолданылады, суретте анықталған жиектердегі әрбір нүкте аккумуляторларға үлес қосады. Аккумулятордың өлшемдері белгісіз параметрлердің санына тең, яғни екі, және параметрлерінің квантталған мәндерін ескере отырып. Әр пиксел және оның айналасы үшін Хоуф түрлендіру алгоритмі сол пикселде тура сызықтың болуына жеткілікті дәлел бар-жоғын анықтайды. Егер бар болса, ол сол сызықтың параметрлерін есептейді, содан кейін параметрлердің түсетін аккумулятордың жасушасын іздеп, оның мәнін арттырады. Аккумулятор кеңістігіндегі жергілікті максимумдарды іздеу арқылы ең жоғары мәндерге ие жасушаларды тауып, ең мүмкін сызықтарды анықтауға болады және олардың (шамамен) геометриялық сипаттамаларын оқуға болады (Шапиро және Стокман, 304). Бұл шыңдарды табудың ең оңай жолы – белгілі бір шекті мән қолдану, бірақ басқа әдістер әртүрлі жағдайларда жақсы нәтижелер беруі мүмкін – қандай сызықтар табылды және олардың саны қанша екенін анықтау үшін. Сызықтардың ұзындығы туралы ақпарат болмағандықтан, келесі қадамда суреттегі қай бөліктер қай сызықтармен сәйкес келетінін анықтау қажет. Сонымен қатар, жиектерді анықтау кезеңіндегі қателерге байланысты, аккумулятор кеңістігінде қателер болуы мүмкін, бұл тиісті шыңдарды, демек, тиісті сызықтарды табуды қиындатады. Сызықтық Хоуф түрлендіруінің соңғы нәтижесі – аккумуляторға ұқсас екі өлшемді матрица. Бұл матрицаның бір өлшемі квантталған бұрыш , ал екінші өлшемі квантталған қашықтық. Матрицаның әрбір элементі квантталған параметрлермен көрсетілген сызықта орналасқан нүктелердің немесе пиксельдердің санына тең. Ең жоғары мәнге ие элемент кіріс суретте ең көп кездесетін тура сызықты көрсетеді.
1-ші мысал
Мұнда қара нүктелер ретінде көрсетілген үш дерек нүктесін қарастырайық. Әрбір дерек нүктесі үшін әртүрлі бұрыштарда бірнеше сызықтар салынған. Бұл сызықтар түрлі түстермен көрсетілген. Хауф трансформациясы анықталған жиектің барлық пикселдерінен келетін үлестерді жинақтайды. Әрбір сызық үшін оған перпендикуляр және координаталардың басынан өтетін тірек сызығы бар. Әр жағдайда олардың бірі жебе түрінде көрсетілген. Әрбір тірек сызығының ұзындығы (яғни, координаталардың басына дейінгі перпендикуляр қашықтық) және бұрышы есептеледі. Ұзындықтары мен бұрыштары суреттердің астында кестеде көрсетілген. Есептеулерден екі жағдайда да 60° бұрыштағы тірек сызығының ұзындығы шамалы екені көрінеді. Сондықтан, сәйкес сызықтар (суреттегі көк сызықтар) өте ұқсас. Осыған байланысты, барлық нүктелер көк сызыққа жақын орналасқан деп қорытынды жасауға болады.
2-ші мысал
Төменде екі қалың сызықты қамтитын растрлық кескіндегі Хауф түрлендіруінің нәтижелерін көрсететін тағы бір мысал келтірілген. Осы түрлендірудің нәтижесі матрицада сақталады. Жасушаның мәні кез келген нүкте арқылы өтетін қисықтардың санын көрсетеді. Жасуша мәні жоғары болса, сол жасуша жарық болады. Екі анық жарық дақ – екі сызықтың Хауф параметрлері. Осы дақтардың орналасуынан кіретін кескіндегі екі сызықтың бұрышы мен кескін ортасынан қашықтығын анықтауға болады.
Дауыстар санын азайту үшін градиент бағытын пайдалану
О'Горман мен Клоуз ұсынған жақсартуды, егер сурет қарқындылығының жергілікті градиенті шетке перпендикуляр болатынын ескерсек, сызықтарды анықтау үшін пайдалануға болады. Шеттерді анықтау әдетте қарқындылық градиентінің мөлшерін есептеуді қамтиды, сондықтан градиент бағыты көбінесе қосалқы нәтиже ретінде табылады. Егер (x,y) координаттарындағы белгілі бір нүкте шындығында түзуде жатса, онда градиенттің жергілікті бағыты осы түзуге сәйкес θ параметрін береді, ал r параметрін дереу анықтауға болады. (Шапиро мен Стокман, 305) Градиент бағытын 20° дәлдікпен бағалауға болады, бұл синусоидалық қисықтың толық 180°-тан шамамен 45°-қа дейін қысқартуына әкеледі. Бұл есептеу уақытын азайтады және пайдасыз дауыстардың санын азайту арқылы суреттегі нақты сызықтарға сәйкес келетін шығыршындардың көрінуін жақсартады.
Ядролық негіздегі Хоуфтың трансформациясы (KHT)
Фернандес пен Оливейра Хоуф трансформациясы үшін, салыстырмалы түрде үлкен кескіндерде де (мысалы, 1280 × 960) нақты уақыт өнімділігіне қол жеткізуге мүмкіндік беретін, жақсартылған дауыс беру схемасын ұсынды. Ядролық негіздегі Хоуф трансформациясы, Дуда мен Харт ұсынған сол параметрлеуді пайдаланады, бірақ шамамен бір түзу бойда орналасқан пиксельдердің кластерлерімен жұмыс істейді. Әрбір кластер үшін, дауыс беру, сәйкес кластерге қатысты ең жақсы сызыққа байланысты белгісіздікті модельдейтін бағытталған эллипстік Гаусс ядросын қолданады. Бұл тәсіл дауыс беру схемасының өнімділігін едәуір жақсартумен қатар, әлдеқайда таза аккумулятор құрады және трансформацияны жалған сызықтарды анықтауға қарсы тұруға мүмкіндік береді.
Жазықтарды анықтау үшін 3D ядролық негіздегі Hough трансформациясы (3DKHT)
Лимбергер мен Оливейра ұйымдастырылмаған нүктелік бұлттарда жазықтықты анықтау үшін детерминистік әдіс ұсынды, оның есептелу шығыны үлгілер санына пропорционал, бұл 3.4 ГГц процессордағы нүктеге дейін салыстырмалы түрде үлкен деректер жиынтықтары үшін дер уақытында жұмыс ілеуге мүмкіндік береді. Бұл әдіс ядролық Хоуг трансформациясынан (KHT) шабыттанған жазық аймақтар үшін жылдам дауыс беру стратегиясына негізделген. Бұл 3D ядролық Хоуг трансформациясы (3DKHT) шамамен бір жазықтықта орналасқан үлгілердің кластерлерін бөліп шығару үшін жылдам және сенімді алгоритмді қолданады, содан кейін үш айнымалы Гаусс ядросын пайдалана отырып, сфералық аккумуляторда жеке кластерлер үшін (жеке үлгілер үшін емес) дауыс береді. Бұл тәсіл RHT және RANSAC сияқты нүктелік бұлттардағы жазықтықты анықтаудың қолданыстағы (детерминистік емес) әдістерінен бірнеше есе жылдам және деректер жиынтығының көлеміне байланысты жақсырақ масштабталады. Оны үлкен деректер жиынтықтарында жазықтық ерекшеліктерді жылдам анықтауды қажет ететін кез келген қолданбада пайдалануға болады.
Көгерістердің Хоуг трансформациясы және оның аналитикалық және аналитикалық емес пішіндер үшін жалпылауы
Жоғарыда сипатталған түрлендіру нұсқасы тек тура сызықтарды табуға ғана қолданылса да, ұқсас түрлендіруді параметрлер жиынтығы арқылы бейнеленетін кез келген пішін табу үшін де пайдалануға болады. Мысалы, шеңберді оның центрі мен радиусын көрсететін үш параметрлік жиынтыққа түрлендіруге болады, сонда Хоу кеңістігі үш өлшемді болады. Кез келген пішіннің параметрлер жиынтығы ретінде оңай бейнеленуі мүмкін болғандықтан, кез келген эллипс пен қисықтарды да осылай табуға болады. Фернандес пен Оливейра кез келген өлшемді кеңістікте аналитикалық пішіндерді анықтау үшін Хоуф түрлендіруінің жалпылануын ұсынды. Аналитикалық пішіндерді анықтауға арналған басқа Хоуф түрлендіруіне негізделген тәсілдерден өзгеше, Фернандестің әдісі анықтағысы келген пішінге де, кіріс деректерінің түріне де тәуелді емес. Деректер кодталған геометрияның қабылданатын моделін өзгерту арқылы (мысалы, евклидтік кеңістік, проекциялық кеңістік, конформдық геометрия және т.б.) анықтауды талдау нысанының белгілі бір түріне бағытталдыруға болады, ал ұсынылған формула өзгеріссіз қалады. Бұдан басқа, ол көзделген пішіндердің ең аз мүмкін параметрлер санымен бейнеленетініне кепілдік береді және әртүрлі өлшемдер мен геометриялық анықтамалары бар кіріс деректері жиынтығына ең жақсы сәйкес келетін пішіндердің әртүрлі түрлерін бір уақытта анықтауға мүмкіндік береді (мысалы, нүктелер жиынтығына ең жақсы сәйкес келетін жазықтықтар мен сфераларды, тура сызықтар мен шеңберлерді бір уақытта анықтау). Жазықтағы күрделі пішіндер үшін (яғни, кейбір 2D кеңістікте аналитикалық түрде бейнеленбеуге болатын пішіндер үшін) Жалпыланған Хоуф түрлендіруі қолданылады, ол пішіннің белгілі бір орналасуына, бағытына және/немесе масштабына алдын ала анықталған іздеу кестесін пайдалану арқылы «дауыс беруге» мүмкіндік береді. Хоуф түрлендіруі анықталған жиектің барлық пиксельдерінен келетін үлестерді жинақтайды.
Дөңгелектерді анықтау процесі
Сызықтардың орнына дөңгелек пішіндерді анықтау үшін алгоритмді өзгерту салыстырмалы түрде оңай. Біріншіден, әр пикселге арналған ұяшықтан тұратын аккумулятор кеңістігін құраймыз. Бастапқыда әрбір ұяшық 0-ге тең болады. Кескіндегі әрбір шеттік нүкте (i, j) үшін, шеңбер теңдеуіне сәйкес шеңбердің орталығы болуы мүмкін барлық ұяшықтардың мәнін арттырамыз. Бұл ұяшықтар теңдеудегі әріппен белгіленеді. Алдыңғы қадамда табылған әрбір мүмкін мән үшін, теңдеуді қанағаттандыратын барлық мүмкін мәндерді табыңыз. Аккумулятор кеңістігіндегі жергілікті максимумдарды іздеңіз. Бұл ұяшықтар алгоритм анықтаған шеңберлерді көрсетеді. Егер іздеп отырған шеңбердің радиусын алдын ала білмесек, кез келген радиусы бар шеңберлерді табу үшін үш өлшемді аккумулятор кеңістігін қолдануға болады. Әрине, бұл есептеулерді күрделендіреді. Бұл әдіс аккумулятор кеңістігінің сыртында жартылай орналасқан шеңберлерді де анықтай алады, егер шеңбердің жеткілікті бөлігі оның ішінде болса.
3D нысандарды (ұшақтар мен цилиндрлерді) анықтау
Хоуф түрлендіруі ауқымдағы деректерде немесе 3D нүктелік бұлттардағы 3D нысандарды анықтау үшін де қолданылуы мүмкін. Классикалық Хоуф түрлендіруін жазықтықты анықтау үшін кеңейту өте оңай. Жазықтық оның ашық теңдеуімен көрсетіледі, он үшін біз 3D Хоуф кеңістігін қолдана аламыз, бұл кеңейту 2D нұсқасындағыдай бірдей проблемалардан зардап шегеді, яғни, көлденең жазықтықтарды сенімді түрде анықтауға болады, ал жазықтық бағыты тік болғанда ( және үлкен мәндері деректердегі шуды күшейтеді) өнімділік төмендейді. Жазықтықтың бұл формуласы әуеден лазерлік сканерлеу арқылы алынған нүктелік бұлттардағы жазықтықтарды анықтау үшін қолданылды және өте жақсы жұмыс істейді, себебі бұл домендегі барлық жазықтықтар дерлік көлденең. Хоуф түрлендіруін пайдалана отырып, жалпы жазықтықты анықтау үшін жазықтықты оның нормаль векторымен (сфералық координаттарды пайдалана отырып) және бастапқы нүктеден арақашықтығымен параметрлеуге болады, нәтижесінде үш өлшемді Хоуф кеңістігі пайда болады. Нәтижесінде кіріс деректерінің әрбір нүктесі Хоуф кеңістігіндегі синусоидальды бетке дауыс береді. Бұл синусоидальды беттердің қиылысуы жазықтықтың бар екенін көрсетеді. Үш өлшемнен артық жағдайларда іздеу эвристикасы қажет болады. Хоуф түрлендіруі екі қадамдық тәсілді қолдана отырып, нүктелік бұлттардағы цилиндрлік нысандарды табу үшін де қолданылған. Бірінші қадам цилиндрдің бағытын, ал екінші қадам орнын және радиусын анықтайды.
Салмақты белгілерді қолдану
Бір жалпы өзгеріс ерекшелігі. Атап айтқанда, бір кезеңде ең көп саны бар топтарды табу келесі кезеңде ізделінетін мәндердің диапазонын тарылту үшін қолданылуы мүмкін.
Параметр кеңістігі мұқият таңдалды
Хоуф трансформациясы үшін жоғары өлшемді параметр кеңістігі ғана емес, сонымен қатар алдын ала ойланбастан жүзеге асырылса, қолданылатын жадты оңай толықтырып жіберуі мүмкін. Егер бағдарламалау ортасы виртуалды жад арқылы қолданылатын жад көлемінен үлкен массивті бөлуге рұқсат берсе де, осы үшін қажетті беттерді ауыстыру саны өте көп болады, себебі аккумулятор массиві кездейсоқ түрде қолданылады, индекстен индекске секіргенде сирек жалғасқан жадта тоқтайды. 800x600 кескініндегі эллипстерді табу міндетін қарастырайық. Эллипстердің радиустары басты осьтер бойымен бағытталған деп есептесек, параметр кеңістігі төрт өлшемді болады. (x, y) эллипстің ортасын анықтайды, ал a және b екі радиусты көрсетеді. Ортаның кескінің кез келген нүктесінде болуына мүмкіндік беру 0<x<800 және 0<y<600 шектеуін қосады. Егер радиустарға да сондай шектеулер қойылса, онда 230 миллиардтан астам мәнді сирек толтырылған аккумулятор массиві қалады. Осылай құрылған бағдарлама жеткілікті жадты бөлуге шамасы келмейді. Бұл мәселені шешуге болмайды дегенді білдірмейді, тек аккумулятор массивінің көлемін шектеудің жаңа тәсілдерін табу қажет, соның арқасында оны жүзеге асыру мүмкін болады. Мысалы: егер эллипстердің әрқайсысы кескінде толығымен сыйып, оның ішінде орналасқан деп есептесек, радиустардың диапазонын қысқартуға болады. Радиустардың ең үлкен мәні эллипстің ортасы кескіннің ортасында болғанда мүмкін болады, бұл эллипстің жиектері кескіннің жиектеріне дейін созылуына мүмкіндік береді. Бұл жағдайда радиустардың әрқайсысы бір бағыттағы кескіннің жартысына тең болуы мүмкін. a және b диапазондарын осылай қысқарту аккумулятор массивін 57 миллиардқа дейін азайтады. Ортаны бағалауда дәлдікті жадқа айырбастау: егер орталықтың x және y осьтерінде 3 бірлікке дейін қате болуы мүмкін болса, бұл аккумулятор массивінің көлемін шамамен 6 миллиардқа дейін азайтады. Радиусты бағалауда дәлдікті жадқа айырбастау: егер радиустардың әрқайсысы 5 бірлікке дейін қате болса, аккумулятор массивінің көлемі шамамен 256 миллионға азаяды. Кескінді қызығушылық тудыратын аймақтарға кесіңіз. Бұл кескінге байланысты, сондықтан болжау қиын, бірақ кескіндегі барлық қажетті жиектер сол кескіннің жоғарғы сол жақ төртбұрышында орналасқан жағдайды елестетіңіз. Бұл жағдайда аккумулятор массивін одан да көп қысқартуға болады, барлық 4 параметрді 2 есеге қысқарту арқылы, жалпы азайту коэффициенті 16-ға жетеді. Жоғарыда келтірілген мысалға осы шектеулердің алғашқы үш еуін ғана қолдану арқылы аккумулятор массивінің көлемі шамамен 1000 есеге азаяды, оны қазіргі заманғы компьютердің жадына сыйымды етуге мүмкіндік береді.
If it is reasonable to assume that the ellipses are each contained entirely within the image, the range of the radii can be reduced. The largest the radii can be is if the center of the ellipse is in the center of the image, allowing the edges of the ellipse to stretch to the edges. In this extreme case, the radii can only each be half the magnitude of the image size oriented in the same direction. Reducing the range of a and b in this fashion reduces the accumulator array to 57 billion values. Trade accuracy for space in the estimation of the center: If the center is predicted to be off by 3 on both the x and y axis this reduces the size of the accumulator array to about 6 billion values. Trade accuracy for space in the estimation of the radii: If the radii are estimated to each be off by 5 further reduction of the size of the accumulator array occurs, by about 256 million values. Crop the image to areas of interest. This is image dependent, and therefore unpredictable, but imagine a case where all of the edges of interest in an image are in the upper left quadrant of that image. The accumulator array can be reduced even further in this case by constraining all 4 parameters by a factor of 2, for a total reduction factor of 16. By applying just the first three of these constraints to the example stated about, the size of the accumulator array is reduced by almost a factor of 1000, bringing it down to a size that is much more likely to fit within a modern computer's memory.
Эллипсті анықтаудың тиімді алгоритмі
Юнхон Шие мен Цян Цзи эллипсті анықтау үшін Хоуф трансформациясын жүзеге асырудың тиімді жолын ұсынады, жад мәселелерін шешу арқылы. Алгоритмде талқыланғандай (мақаланың 2-бетінде), бұл тәсіл кескіндегі эллипстерді анықтау үшін тек бір өлшемді аккумуляторды (кіші ось үшін) пайдаланады. Кескіндегі нөлдік емес нүктелер саны бойынша күрделілігі O(N3) құрайды.
Шектеулер
Hough трансформациясы тек қана көптеген дауыстар дұрыс контейнерге түсіп, фондық шудың арасында контейнерді оңай анықтауға мүмкіндік беретін жағдайда ғана тиімді. Яғни, контейнер тым кішкентай болмауы керек, әйтпесе кейбір дауыстар көрші контейнерлерге түсіп, негізгі контейнердің көрінуін азайтуы мүмкін. Сонымен қатар, параметрлер саны көп болғанда (әдетте үш параметрден астам қолданылғанда), бір контейнердегі дауыстардың орташа саны өте төмен болады, ал суреттегі нақты фигураға сәйкес контейнерлер көршілерінен айқын артық дауысқа ие болмауы мүмкін. Күрделілік әр қосымша параметрмен өседі, мұндағы сурет кеңістігінің мөлшері – , ал параметрлер саны – . (Шапиро мен Стокман, 310) Осылайша, Hough трансформациясын сызықтар мен шеңберлерден басқа нәрсені анықтау үшін өте сақтап қолдану керек. Ақырында, Hough трансформациясының тиімділігінің көп бөлігі кіріс деректерінің сапасына байланысты: трансформация тиімді жұмыс істеуі үшін жиектер жақсы анықталуы керек. Шулы суреттерде Hough трансформациясын қолдану өте нәзік мәселе, сондықтан әдетте алдымен шуды азайту қадамы қолданылады. Егер сурет сыпыртқылармен бұзылған болса (мысалы, радарлық суреттерде), сызықтарды анықтау үшін кейде Radon трансформациясы артықшылыққа ие, себебі ол қосу арқылы шуды басады.