การแปลงฮอฟแบบทั่วไป ( GHT ) ซึ่งแนะนำโดยDana H. Ballardในปี 1981 เป็นการดัดแปลงการแปลงฮอฟโดยใช้หลักการจับคู่แม่แบบ [ ^{1 ] การ}แปลงฮอฟได้รับการพัฒนาขึ้นครั้งแรกเพื่อตรวจจับรูปร่างที่กำหนดโดยการวิเคราะห์ (เช่นเส้นตรงวงกลมวงรี เป็นต้น) ในกรณีเหล่านี้ เรามีความรู้เกี่ยวกับรูปร่างและมุ่งหวังที่จะค้นหาตำแหน่ง และ การวางแนวของรูปร่างนั้นในภาพ การดัดแปลงนี้ทำให้การแปลงฮ อฟสามารถใช้ตรวจจับวัตถุใดๆ ที่อธิบายด้วยแบบจำลองได้

ปัญหาการค้นหาวัตถุ (ที่อธิบายด้วยแบบจำลอง) ในภาพ สามารถแก้ไขได้โดยการหาตำแหน่งของแบบจำลองในภาพ ด้วยการแปลงฮอฟแบบทั่วไป ปัญหาการหาตำแหน่งของแบบจำลองจะถูกแปลงเป็นปัญหาการหาค่าพารามิเตอร์ของการแปลงที่แมปแบบจำลองลงในภาพ เมื่อทราบค่าของพารามิเตอร์การแปลงแล้ว ก็สามารถกำหนดตำแหน่งของแบบจำลองในภาพได้

การใช้งาน GHT ดั้งเดิมใช้ข้อมูลขอบเพื่อกำหนดการแมปจากการวางแนวของจุดขอบไปยังจุดอ้างอิงของรูปร่าง ในกรณีของภาพไบนารีที่พิกเซลสามารถเป็นได้ทั้งสีดำหรือสีขาว พิกเซลสีดำทุกพิกเซลของภาพสามารถเป็นพิกเซลสีดำของรูปแบบที่ต้องการได้ จึงสร้างตำแหน่งของจุดอ้างอิงในพื้นที่ Hough พิกเซลทุกพิกเซลของภาพจะลงคะแนนให้กับจุดอ้างอิงที่สอดคล้องกัน จุดสูงสุดของพื้นที่ Hough บ่งชี้ถึงจุดอ้างอิงที่เป็นไปได้ของรูปแบบในภาพ จุดสูงสุดนี้สามารถพบได้โดยการสแกนพื้นที่ Hough หรือโดยการแก้ชุดสมการแบบผ่อนคลายซึ่งแต่ละชุดจะสอดคล้องกับพิกเซลสีดำ^{[ 2 ]}

เมอร์ลินและฟาร์เบอร์^{[ 3 ]}แสดงวิธีการใช้อัลกอริทึมฮอฟเมื่อเส้นโค้งที่ต้องการไม่สามารถอธิบายได้ด้วยวิธีวิเคราะห์ อัลกอริทึมนี้เป็นต้นแบบของอัลกอริทึมของบัลลาร์ดซึ่งจำกัดเฉพาะการแปลและไม่ได้คำนึงถึงการหมุนและการเปลี่ยนแปลงขนาด^{[ 4 ]}

อัลกอริทึม Merlin-Farber ไม่เหมาะสมกับการใช้งานกับข้อมูลภาพจริง เนื่องจากในภาพที่มีพิกเซลขอบจำนวนมาก จะพบผลลัพธ์ที่ผิดพลาดจำนวนมากอันเนื่องมาจากการจัดเรียงพิกเซลที่ซ้ำซ้อน

เพื่อขยายอัลกอริทึม Hough ไปยังเส้นโค้งที่ไม่ใช่เชิงวิเคราะห์ Ballard ได้กำหนดพารามิเตอร์ต่อไปนี้สำหรับรูปร่างทั่วไป: a={y,s,θ}โดยที่y คือ จุดกำเนิดอ้างอิงสำหรับรูปร่างθคือทิศทาง และs = (s _x , s _y )อธิบายถึงตัวประกอบมาตราส่วนตั้งฉากสองตัวอัลกอริทึมสามารถคำนวณชุดพารามิเตอร์ที่ดีที่สุดสำหรับรูปร่างที่กำหนดจากข้อมูลพิกเซลขอบ พารามิเตอร์เหล่านี้ไม่ได้มีสถานะเท่ากัน ตำแหน่งจุดกำเนิดอ้างอิงyถูกอธิบายในแง่ของตารางแม่แบบที่เรียกว่าตาราง R ของทิศทางพิกเซลขอบที่เป็นไปได้ การคำนวณพารามิเตอร์เพิ่มเติมsและ θจะทำได้โดยการแปลงตารางนี้โดยตรง หลักการสำคัญของการขยายไปยังรูปร่างใดๆ คือการใช้ข้อมูลทิศทาง เมื่อกำหนดรูปร่างใดๆ และจุดอ้างอิงคงที่บนรูปร่างนั้น แทนที่จะใช้เส้นโค้งพาราเมตริก ข้อมูลที่ได้จากพิกเซลขอบจะถูกจัดเก็บในรูปแบบของตาราง R ในขั้นตอนการแปลง สำหรับจุดขอบทุกจุดบนภาพทดสอบ คุณสมบัติของจุดนั้นจะถูกค้นหาในตาราง R และดึงจุดอ้างอิงออกมา จากนั้นค่าในเซลล์ที่เหมาะสมในเมทริกซ์ที่เรียกว่าเมทริกซ์สะสมจะถูกเพิ่มขึ้น เซลล์ที่มี 'คะแนนโหวต' สูงสุดในเมทริกซ์สะสมอาจเป็นจุดอ้างอิงคงที่ของวัตถุในภาพทดสอบได้

เลือกจุดอ้างอิงyสำหรับรูปร่าง (โดยทั่วไปจะเลือกภายในรูปร่าง) สำหรับแต่ละจุดขอบxให้คำนวณ ɸ(x)ทิศทางของเกรเดียนต์และr = y – xดังแสดงในภาพ เก็บค่าrเป็นฟังก์ชันของɸสังเกตว่าแต่ละดัชนีของɸอาจมีค่าr ได้หลายค่า เราสามารถเก็บค่าความแตกต่างของพิกัดระหว่างจุดอ้างอิงคงที่กับจุดขอบ((x _c – x _ij ), (y _c – y _ij )) หรือเป็นระยะทางรัศมีและมุมระหว่างจุดทั้งสอง(r _ij , α _ij )เมื่อทำเช่นนี้สำหรับแต่ละจุดแล้ว ตาราง R จะแสดงวัตถุแม่แบบได้อย่างสมบูรณ์ นอกจากนี้ เนื่องจากขั้นตอนการสร้างสามารถย้อนกลับได้ เราจึงสามารถใช้ขั้นตอนนี้เพื่อระบุตำแหน่งการปรากฏของวัตถุในตำแหน่งอื่นๆ ในภาพได้

สำหรับแต่ละพิกเซลขอบxในภาพ ให้หาค่าเกรเดียนต์ɸและเพิ่มค่าจุดที่สอดคล้องกันทั้งหมดx+rในอาร์เรย์สะสมA (เริ่มต้นด้วยขนาดสูงสุดของภาพ) โดยที่ r คือรายการในตารางที่จัดทำดัชนีโดยɸเช่นr(ɸ)จุดเหล่านี้ให้ตำแหน่งที่เป็นไปได้ทั้งหมดสำหรับจุดอ้างอิง แม้ว่าอาจมีการคำนวณจุดที่ไม่ถูกต้องบ้าง แต่เนื่องจากวัตถุมีอยู่ในภาพ ค่าสูงสุดจึงเกิดขึ้นที่จุดอ้างอิง ค่าสูงสุดในAสอดคล้องกับกรณีที่เป็นไปได้ของรูปร่าง

สำหรับการกำหนดทิศทางของรูปร่างที่แน่นอน อาร์เรย์สะสมจะเป็นแบบสองมิติในพิกัดจุดอ้างอิง ในการค้นหารูปร่างที่มีทิศทางθและขนาดs ที่ไม่แน่นอน พารามิเตอร์ทั้งสองนี้จะถูกเพิ่มเข้าไปในคำอธิบายรูปร่าง ตอนนี้อาร์เรย์สะสมประกอบด้วยสี่มิติที่สอดคล้องกับพารามิเตอร์(y, s, θ)ตาราง R ยังสามารถใช้เพื่อเพิ่มขนาดพื้นที่มิติที่ใหญ่ขึ้นนี้ได้ เนื่องจากทิศทางและขนาดที่แตกต่างกันจะสอดคล้องกับการแปลงตารางที่คำนวณได้ง่าย กำหนดให้ตาราง R เฉพาะสำหรับรูปร่างSเป็นR(ɸ)การแปลงอย่างง่ายกับตารางนี้จะช่วยให้สามารถตรวจจับรูปร่างเดียวกันที่ถูกปรับขนาดหรือหมุนได้ ตัวอย่างเช่น หากรูปร่างถูกปรับขนาดด้วย s และการแปลงนี้แสดงด้วยT _sแล้ว T _s [R(ɸ)] = sR(ɸ)กล่าวคือ เวกเตอร์ทั้งหมดถูกปรับขนาดด้วยsนอกจากนี้ หากวัตถุถูกหมุนด้วยมุมθและการแปลงนี้แสดงด้วยT _θแล้ว T _θ [R(ɸ)] = Rot{R[(ɸ-θ)mod2π],θ} กล่าวคือ ดัชนีทั้งหมดจะเพิ่มขึ้นด้วย – θมอดูล 2π จากนั้นจะพบเวกเตอร์r ที่เหมาะสม และหมุนเวกเตอร์เหล่านั้นด้วยมุมθอีกคุณสมบัติหนึ่งที่จะมีประโยชน์ในการอธิบายการประกอบกันของการแปลง Hough แบบทั่วไปคือการเปลี่ยนจุดอ้างอิง หากเราต้องการเลือกจุดอ้างอิงใหม่ỹโดยที่y-ỹ = zการแก้ไขตาราง R จะเป็นR(ɸ)+ zกล่าว คือ เพิ่ม zเข้าไปในแต่ละเวกเตอร์ในตาราง

สามารถใช้พิกเซลขอบคู่หนึ่งเพื่อลดพื้นที่พารามิเตอร์ได้ โดยใช้ตาราง R และคุณสมบัติที่อธิบายไว้ข้างต้น พิกเซลขอบแต่ละพิกเซลจะกำหนดพื้นผิวในพื้นที่สะสมสี่มิติของa = (y, s, θ)พิกเซลขอบสองพิกเซลที่มีทิศทางต่างกันจะอธิบายพื้นผิวเดียวกันที่หมุนด้วยปริมาณเดียวกันเมื่อเทียบกับθหากพื้นผิวทั้งสองนี้ตัดกัน จุดที่ตัดกันจะสอดคล้องกับพารามิเตอร์a ที่เป็นไปได้ สำหรับรูปร่าง ดังนั้นในทางทฤษฎีจึงเป็นไปได้ที่จะใช้จุดสองจุดในพื้นที่ภาพเพื่อลดตำแหน่งในพื้นที่พารามิเตอร์ให้เหลือเพียงจุดเดียว อย่างไรก็ตาม ความยากลำบากในการหาจุดตัดของพื้นผิวทั้งสองในพื้นที่พารามิเตอร์จะทำให้วิธีการนี้ไม่สามารถใช้งานได้ในกรณีส่วนใหญ่

ถ้ารูปร่าง S มีโครงสร้างแบบผสมที่ประกอบด้วยส่วนย่อยS ₁ , S ₂ , .. S _Nและจุดอ้างอิงสำหรับรูปร่างS , S ₁ , S ₂ , .. S _Nคือy , y ₁ , y ₂ , .. y _nตามลำดับ สำหรับตัวประกอบการปรับขนาดsและการวางแนวθการแปลง Hough แบบทั่วไปR _s (ɸ)จะกำหนดโดยข้อกังวลเกี่ยวกับการแปลงนี้คือ การเลือกจุดอ้างอิงอาจส่งผลต่อความแม่นยำอย่างมาก เพื่อแก้ไขปัญหานี้ Ballard ได้เสนอให้ปรับเรียบตัวสะสมผลลัพธ์ด้วยแม่แบบการปรับเรียบแบบผสม แม่แบบการปรับเรียบแบบผสมH(y)กำหนดเป็นผลรวมแบบ ผสม ของแม่แบบการปรับเรียบแต่ละแบบของรูปร่างย่อย จากนั้น ตัวสะสมที่ปรับปรุงแล้วจะกำหนดโดยA _s = A*Hและค่าสูงสุดในA _sสอดคล้องกับกรณีที่เป็นไปได้ของรูปร่าง ${\displaystyle R_{\phi }=T_{s}\left\{T_{\theta }\left[\bigcup _{k=1}^{N}R_{s_{k}}(\phi )\right]\right\}}$${\displaystyle H(y)=\sum _{i=1}^{N}h_{i}(y-y_{i})}$

จากการสังเกตว่าการแปลง Hough ทั่วโลกสามารถหาได้จากการรวมการแปลง Hough เฉพาะที่ของบริเวณย่อยที่ไม่ทับซ้อนกัน Heather และ Yang ^{[ 5 ]}ได้เสนอวิธีการที่เกี่ยวข้องกับการแบ่งภาพออกเป็นภาพย่อยแบบวนซ้ำ โดยแต่ละภาพมีพื้นที่พารามิเตอร์ของตัวเอง และจัดเรียงใน โครงสร้าง ควอดทรีส่งผลให้ประสิทธิภาพในการค้นหาจุดปลายของส่วนของเส้นดีขึ้น และความทนทานและความน่าเชื่อถือในการแยกเส้นในสถานการณ์ที่มีสัญญาณรบกวนดีขึ้น โดยมีค่าใช้จ่ายด้านหน่วยความจำเพิ่มขึ้นเล็กน้อย

การดำเนินการใช้สมการต่อไปนี้: ^{[ 6 ]}

${\displaystyle x=x_{c}+x'\ \ หรือ\ \ x_{c}=xx'}$

${\displaystyle y=y_{c}+y'\ \ หรือ\ \ y_{c}=yy'}$

${\displaystyle \cos(\pi -\alpha )=x'/r\ \ {\text{หรือ}}\ \ x'=r\cos(\pi -\alpha )=-r\cos(\alpha )}$

${\displaystyle \sin(\pi -\alpha )=y'/r\ \ {\text{or}}\ \ y'=r\sin(\pi -\alpha )=r\sin(\alpha )}$

เมื่อรวมสมการข้างต้นเข้าด้วยกัน เราจะได้:

${\displaystyle x_{c}=x+r\cos(\alpha )}$

${\displaystyle y_{c}=y+r\sin(\alpha )}$

การสร้างตาราง R

(0) แปลงภาพรูปร่างตัวอย่างให้เป็นภาพขอบโดยใช้ อัลกอริทึม ตรวจจับขอบ ใดๆ เช่นตัวตรวจจับขอบ Canny

(1) เลือกจุดอ้างอิง (เช่น(x _c , y _c ) )

(2) ลากเส้นจากจุดอ้างอิงไปยังขอบเขต

(3) คำนวณɸ

(4) จัดเก็บจุดอ้างอิง(x _c , y _c )เป็นฟังก์ชันของɸในตารางR(ɸ)

การตรวจจับ:

(0) แปลงภาพรูปร่างตัวอย่างให้เป็นภาพขอบโดยใช้อัลกอริทึมตรวจจับขอบใดๆ เช่นตัวตรวจจับขอบ Canny

(1) เริ่มต้นตารางสะสม: A[x _cmin . . . x _cmax ][y _cmin . . . y _cmax ]

(2) สำหรับจุดขอบแต่ละจุด(x, y)

(2.1) โดยใช้มุมความชันɸ ดึงค่า (α, r) ทั้งหมดที่ อยู่ในดัชนีɸจากตาราง R

(2.2) สำหรับแต่ละ(α,r)ให้คำนวณจุดอ้างอิงที่เป็นไปได้:

x _c = x + r cos(α)

y _c = y + r sin(α)

(2.3) เพิ่มจำนวนผู้ลงคะแนน:

++A([[x _c ]][y _c ])

(3) ตำแหน่ง ที่เป็นไปได้ของเส้นขอบวัตถุจะกำหนดโดยค่าสูงสุดเฉพาะที่ในA[x _c ][y _c ]

ถ้าA[x _c ][y _c ] > Tแสดงว่าเส้นขอบของวัตถุอยู่ที่(x _c , y _c )

กรณีทั่วไป:

สมมติว่าวัตถุมีการหมุนΘและมีการปรับขนาดสม่ำเสมอs :

(x ′ , y ′ ) → (x″, y″)

x″ = (x ′ cos(Θ) – y ′บาป(Θ))s

y″ = (x ′บาป(Θ) + y ′ cos(Θ))s

แทนที่ x ′ด้วย x″ และ y ′ด้วย y″:

x _c = x – x″ หรือ x _c = x - (x ′ cos(Θ) – y ′ sin(Θ))s

y _c = y – y″ หรือ y _c = y - (x ′ sin(Θ) + y ′ cos(Θ))s

(1) เริ่มต้นตารางสะสม: A[x _cmin . . . x _cmax ][y _cmin . . . y _cmax ][q _min . . . q _max ][s _min . . . s _max ]

(2) สำหรับจุดขอบแต่ละจุด(x, y)

(2.1) โดยใช้มุมความชันɸดึง ค่า (α, r) ทั้งหมด จากตาราง R

(2.2) สำหรับแต่ละ(α, r)ให้คำนวณจุดอ้างอิงที่เป็นไปได้:

x ′ = r cos(α)

y ′ = r sin(α)

สำหรับ( Θ = Θ _นาที ; Θ ≤ Θ _{สูงสุด} ; Θ++ )

สำหรับ ( s = s _min ; s ≤ s _max ; s++ )

x _c = x - (x ′ cos(Θ) – y ′ sin(Θ))s

y _c = y - (x ′ sin(Θ) + y ′ cos(Θ))s

++(A[x _c ][y _c ][Θ][s])

(3) ตำแหน่งที่เป็นไปได้ของเส้นขอบวัตถุจะกำหนดโดยค่าสูงสุดเฉพาะที่ในA[x _c ][y _c ][Θ][s]

ถ้าA[x _c ][y c _] [Θ][s] > Tแสดงว่าเส้นขอบของวัตถุอยู่ที่(x _c , y _c )มีการหมุนΘและมีการปรับขนาดด้วยs

• มีความทนทานต่อรูปทรงที่บิดเบี้ยวบางส่วนหรือเล็กน้อย (เช่น มีความทนทานต่อการจดจำภายใต้การบดบัง)
• มีความทนทานต่อการมีโครงสร้างเพิ่มเติมในภาพ
• มันทนต่อเสียงรบกวนได้ดี
• สามารถตรวจพบรูปร่างที่เหมือนกันหลายครั้งในระหว่างการประมวลผลรอบเดียวกันได้

• มันมีความต้องการด้านการประมวลผลและการจัดเก็บข้อมูลจำนวนมาก ซึ่งจะยิ่งทวีความรุนแรงขึ้นเมื่อต้องพิจารณาถึงการวางแนวของวัตถุและขนาด

Ballard แนะนำให้ใช้ข้อมูลการวางแนวของขอบเพื่อลดต้นทุนการคำนวณ มีการแนะนำเทคนิค GHT ที่มีประสิทธิภาพหลายอย่าง เช่น SC-GHT (โดยใช้ความชันและความโค้งเป็นคุณสมบัติเฉพาะที่) ^{[ 7 ]} Davis และ Yam ^{[ 8 ]}ยังแนะนำการขยายงานของ Merlin สำหรับการจับคู่ที่ไม่ขึ้นกับการวางแนวและมาตราส่วน ซึ่งเสริมงานของ Ballard แต่ไม่ได้รวมถึงการใช้ข้อมูลความชันของขอบและโครงสร้างแบบผสมของ Ballard

• ฮัฟ ทรานส์ฟอร์ม
• การแปลงฮอฟแบบสุ่ม
• เรดอนแปลงสภาพ
• การจับคู่แม่แบบ
• โครงร่างของการจดจำวัตถุ

• การใช้งานการแปลงฮอฟแบบทั่วไปใน OpenCV http://docs.opencv.org/master/dc/d46/classcv_1_1GeneralizedHoughBallard.html
• บทแนะนำและการใช้งานการแปลงฮอฟแบบทั่วไปhttp://www.itriacasa.it/generalized-hough-transform/default.html เก็บถาวรเมื่อ 30 มกราคม 2016 ที่Wayback Machine
• การนำการแปลงฮอฟแบบทั่วไปมาใช้ในทางปฏิบัติhttp://www.irit.fr/~Julien.Pinquier/Docs/Hough_transform.html
• การนำการแปลงฮอฟแบบทั่วไปไปใช้ใน FPGA, ห้องสมุดดิจิทัล IEEE https://ieeexplore.ieee.org/document/5382047/
• การใช้งานการแปลงฮอฟแบบทั่วไปใน MATLAB http://www.mathworks.com/matlabcentral/fileexchange/44166-generalized-hough-transform