อัลกอริทึมการแปลงปริมาณเฉลี่ยเฉลี่ยต่อเนื่อง (SMQT) คือการแปลงแบบไม่เป็นเชิงเส้นที่เปิดเผยองค์กรหรือโครงสร้างของข้อมูลและลบคุณสมบัติต่างๆเช่นกำไรและอคติ ในกระดาษชื่อ การแปลงปริมาณเฉลี่ยต่อเนื่อง , SMQT ถูก 'นำไปใช้ในการประมวลผลคำพูดและการประมวลผลภาพ' อัลกอริทึมเมื่อนำไปใช้กับรูปภาพ 'สามารถมองเห็นได้ว่าเป็นโปรเกรสซีฟโฟกัสที่รายละเอียดในภาพ'
ตามกระดาษอื่นที่ชื่อ ตัวดำเนินการ Tone Mapping ที่ใช้ SMQT สำหรับภาพช่วงไดนามิกสูง มันจะให้ 'ภาพที่มีรายละเอียดขั้นสูง' บทความนี้อธิบายถึงเทคนิคสองประการในการนำการเปลี่ยนแปลงนี้ไปใช้กับรูปภาพ
ใช้ SMQT กับความส่องสว่างของแต่ละพิกเซล - อธิบายสูตรเพื่อให้ได้ความส่องสว่างจาก RGB ของแต่ละพิกเซล
ใช้ SMQT ในแต่ละช่องของ RGB แยกกัน - สำหรับช่อง R, G และ B ทีละช่อง
ภาพต่อไปนี้แสดงผลลัพธ์ของสองเทคนิค:
ด้วยการใช้เทคนิคที่สองกับภาพของ Bruin Theatre ในเวลากลางคืนเราจะเห็นได้ว่าอัลกอริทึมซูมรายละเอียดของภาพอย่างต่อเนื่องและเปิดเผยรายละเอียดที่ซ่อนอยู่ในความมืดได้อย่างไร:
ในบทความนี้เราจะดูวิธีการทำงานของอัลกอริทึมนี้อย่างละเอียดยิ่งขึ้นและสำรวจการเพิ่มประสิทธิภาพอย่างง่ายที่ช่วยให้อัลกอริทึมมีประสิทธิภาพมากขึ้นในแอปพลิเคชันการประมวลผลภาพที่ใช้งานได้จริง
ในเอกสารต้นฉบับอัลกอริทึมอธิบายในลักษณะนามธรรม เพื่อให้เข้าใจ SMQT ได้ดีขึ้นเราจะอธิบายตัวอย่างง่ายๆ
สมมติว่าเรามีเวกเตอร์ต่อไปนี้ (คุณสามารถคิดว่ามันเหมือนอาร์เรย์):
32 | 48 | 60 | 64 | 59 | 47 | 31 | สิบห้า | 4 | 0 | 5 | 18 |
ในกรณีของภาพสีเราสามารถคิดว่ามันเป็นเวกเตอร์สามตัวที่แยกจากกันซึ่งแต่ละตัวแสดงถึงช่องสีเฉพาะ (RGB) และแต่ละองค์ประกอบของเวกเตอร์ที่แสดงถึงความเข้มของพิกเซลที่เกี่ยวข้อง
ประกายไฟใช้ทำอะไร
ขั้นตอนที่เกี่ยวข้องในการใช้อัลกอริทึม SMQT ได้แก่ :
คำนวณค่าเฉลี่ยของเวกเตอร์ซึ่งในกรณีนี้คือ 29.58
แบ่งเวกเตอร์ออกเป็นสองส่วนโดยปล่อยให้ตัวเลขที่น้อยกว่าหรือเท่ากับ 29.58 อยู่ครึ่งซ้ายและตัวเลขที่มากกว่าในครึ่งขวา:
สิบห้า | 4 | 0 | 5 | 18 | 32 | 48 | 60 | 64 | 59 | 47 | 31 |
0 | 0 | 0 | 0 | 0 | หนึ่ง | หนึ่ง | หนึ่ง | หนึ่ง | หนึ่ง | หนึ่ง | หนึ่ง |
แถวที่สองคือรหัสที่เราจะสร้างสำหรับแต่ละค่า ค่าที่ต่ำกว่าหรือเท่ากับ 29.58 จะได้รับ 0 ในรหัสและตัวเลขที่มากกว่า 29.58 จะได้รับ 1 (นี่คือไบนารี)
ตอนนี้เวกเตอร์ผลลัพธ์ทั้งสองถูกแยกทีละรายการในลักษณะวนซ้ำตามกฎเดียวกัน ในตัวอย่างของเราค่าเฉลี่ยของเวกเตอร์แรกคือ (15 + 4 + 0 + 5 + 18) / 5 = 8.4 และค่าเฉลี่ยของเวกเตอร์ที่สองคือ (32 + 48 + 60 + 64 + 59 + 47 + 31) / 7 = 48.7. เวกเตอร์สองตัวนั้นแต่ละตัวจะถูกแบ่งออกเป็นเวกเตอร์อีกสองเวกเตอร์และโค้ดที่สองจะถูกเพิ่มเข้าไปในแต่ละเวกเตอร์ขึ้นอยู่กับการเปรียบเทียบกับค่าเฉลี่ย นี่คือผลลัพธ์:
4 | 0 | 5 | สิบห้า | 18 | 32 | 47 | 31 | 48 | 60 | 64 | 59 |
00 | 00 | 00 | 01 | 01 | 10 | 10 | 10 | สิบเอ็ด | สิบเอ็ด | สิบเอ็ด | สิบเอ็ด |
โปรดสังเกตว่า 0 ถูกต่อท้ายอีกครั้งสำหรับตัวเลขที่ต่ำกว่าหรือเท่ากับค่าเฉลี่ย (สำหรับแต่ละเวกเตอร์) และ 1 สำหรับตัวเลขที่มากกว่าค่าเฉลี่ย
อัลกอริทึมนี้ซ้ำแล้วซ้ำอีก:
0 | 4 | 5 | สิบห้า | 18 | 32 | 31 | 47 | 48 | 60 | 64 | 59 |
000 | 001 | 001 | 010 | 011 | 100 | 100 | 101 | 110 | 111 | 111 | 111 |
0 | 4 | 5 | สิบห้า | 18 | 31 | 32 | 47 | 48 | 60 | 59 | 64 |
0000 | 0010 | 0011 | 0100 | 0110 | 1,000 | 1001 | 1010 | 1100 | 1110 | 1110 | 1111 |
0 | 4 | 5 | สิบห้า | 18 | 31 | 32 | 47 | 48 | 59 | 60 | 64 |
00000 | 00100 | 00110 | 01000 | 01100 | 10,000 | 10010 | 10100 | 11000 | 11100 | 11101 | 11110 |
ณ จุดนี้ทุกเวกเตอร์มีเพียงองค์ประกอบเดียว ดังนั้นสำหรับทุกขั้นตอนที่ต่อเนื่องกันจะมีการต่อท้าย 0 เนื่องจากจำนวนจะเท่ากับตัวมันเองเสมอ (เงื่อนไขสำหรับ 0 คือจำนวนต้องน้อยกว่าหรือเท่ากับค่าเฉลี่ยซึ่งก็คือตัวมันเอง)
จนถึงตอนนี้เรามีระดับการหาปริมาณของ L = 5 ถ้าเราจะใช้ L = 8 เราต้องต่อท้าย 0 สามตัวในแต่ละรหัส ผลลัพธ์ของการแปลงแต่ละรหัสจากไบนารีเป็นจำนวนเต็ม (สำหรับ L = 8) จะเป็น:
0 | 4 | 5 | สิบห้า | 18 | 31 | 32 | 47 | 48 | 59 | 60 | 64 |
0 | 32 | 48 | 64 | 96 | 128 | 144 | 160 | 192 | 224 | 232 | 240 |
เวกเตอร์สุดท้ายถูกจัดเรียงตามลำดับที่เพิ่มขึ้น ในการรับเวกเตอร์เอาต์พุตเราต้องแทนที่ค่าดั้งเดิมของเวกเตอร์อินพุตด้วยรหัส
32 | 48 | 60 | 64 | 59 | 47 | 31 | สิบห้า | 4 | 0 | 5 | 18 |
144 | 192 | 232 | 240 | 224 | 160 | 128 | 64 | 32 | 0 | 48 | 96 |
สังเกตว่าในเวกเตอร์ผลลัพธ์:
ให้ภาพเหมือนเวกเตอร์ของพิกเซล RGB โดยแต่ละจุดเป็น 8 บิตสำหรับ R, 8 สำหรับ G และ 8 สำหรับ B เราสามารถแยกเวกเตอร์สามตัวจากมันหนึ่งตัวสำหรับแต่ละสีและใช้อัลกอริทึมกับเวกเตอร์แต่ละตัว จากนั้นเราสร้างเวกเตอร์ RGB อีกครั้งจากเวกเตอร์เอาต์พุตสามตัวนั้นและเรามีภาพที่ประมวลผล SMQT เช่นเดียวกับหนึ่งใน Bruin Theatre
อัลกอริทึมกำหนดให้ในแต่ละระดับของการหาปริมาณ (L) องค์ประกอบ N จะต้องได้รับการตรวจสอบในรอบแรกเพื่อค้นหาค่าเฉลี่ยของเวกเตอร์แต่ละตัวจากนั้นในรอบที่สององค์ประกอบ N แต่ละองค์ประกอบจะต้องถูกเปรียบเทียบกับค่าเฉลี่ยที่สอดคล้องกันใน เพื่อแยกเวกเตอร์แต่ละตัวในทางกลับกัน สุดท้ายองค์ประกอบ N จะต้องถูกแทนที่ด้วยรหัสของพวกเขา ดังนั้นความซับซ้อนของอัลกอริทึมคือ O ((L * 2 * N) + N) = O ((2 * L + 1) * N) ซึ่งก็คือ O (L * N)
กราฟที่ดึงออกมาจากกระดาษสอดคล้องกับความซับซ้อน O (L * N) ยิ่ง L ต่ำการประมวลผลจะเร็วขึ้นในลักษณะเชิงเส้นโดยประมาณ (จำนวนเฟรมต่อวินาทีมากขึ้น) เพื่อปรับปรุงความเร็วในการประมวลผลเอกสารนี้จะแนะนำการลดค่า L:“ การเลือกระดับ L ให้ต่ำลงอาจเป็นวิธีโดยตรงในการลดความเร็วในการประมวลผล แต่มีคุณภาพของภาพที่ลดลง”
รูปแบบทางการเงินคืออะไร
ที่นี่เราจะพบวิธีปรับปรุงความเร็วโดยไม่ลดคุณภาพของภาพ เราจะวิเคราะห์กระบวนการเปลี่ยนแปลงและค้นหาอัลกอริทึมที่เร็วขึ้น เพื่อให้ได้มุมมองที่สมบูรณ์ยิ่งขึ้นเรามาดูตัวอย่างที่มีตัวเลขซ้ำกัน:
16 | 25 | 31 | 31 | 25 | 16 | 7 | หนึ่ง | หนึ่ง | 7 |
16 | 16 | 7 | หนึ่ง | หนึ่ง | 7 | 25 | 31 | 31 | 25 |
0 | 0 | 0 | 0 | 0 | 0 | หนึ่ง | หนึ่ง | หนึ่ง | หนึ่ง |
7 | หนึ่ง | หนึ่ง | 7 | 16 | 16 | 25 | 25 | 31 | 31 |
00 | 00 | 00 | 00 | 01 | 01 | 10 | 10 | สิบเอ็ด | สิบเอ็ด |
หนึ่ง | หนึ่ง | 7 | 7 | 16 | 16 | 25 | 25 | 31 | 31 |
000 | 000 | 001 | 001 | 010 | 010 | 100 | 100 | 110 | 110 |
ไม่สามารถแยกเวกเตอร์ได้อีกต่อไปและต้องต่อท้ายด้วยศูนย์จนกว่าเราจะได้ L ที่ต้องการ
เพื่อความเรียบง่ายสมมติว่าอินพุตสามารถไปจาก 0 ถึง 31 และเอาต์พุตจาก 0 ถึง 7 (L = 3) ดังที่เห็นได้ในตัวอย่าง
โปรดทราบว่าการคำนวณค่าเฉลี่ยของเวกเตอร์แรก (16 + 25 + 31 + 31 + 25 + 16 + 7 + 1 + 1 + 7) / 10 = 16 จะให้ผลลัพธ์เช่นเดียวกับการคำนวณค่าเฉลี่ยของเวกเตอร์สุดท้ายทั้งหมดเนื่องจากเป็น เพียงเวกเตอร์เดียวกันกับองค์ประกอบในลำดับที่แตกต่างกัน: (1 + 1 + 7 + 7 + 16 + 16 + 25 + 25 + 31 + 31) / 10 = 16
ในขั้นตอนที่สองเราต้องคำนวณเวกเตอร์แต่ละตัวแบบวนซ้ำ ดังนั้นเราจึงคำนวณค่าเฉลี่ยของอินพุตที่เป็นสีเทาซึ่งเป็น 6 องค์ประกอบแรก ((16 + 16 + 7 + 1 + 1 + 7) / 6 = 8) และค่าเฉลี่ยของอินพุตว่างซึ่งเป็น 4 องค์ประกอบสุดท้าย ((25 + 31 + 31 + 25) / 4 = 28):
16 | 16 | 7 | หนึ่ง | หนึ่ง | 7 | 25 | 31 | 31 | 25 |
โปรดสังเกตอีกครั้งว่าถ้าเราใช้เวกเตอร์สุดท้ายซึ่งเป็นเวกเตอร์ที่เรียงลำดับอย่างสมบูรณ์ผลลัพธ์จะเหมือนกัน สำหรับ 6 องค์ประกอบแรกเรามี: ((1 + 1 + 7 + 7 + 16 + 16) / 6 = 8) และสำหรับ 4 องค์ประกอบสุดท้าย: ((25 + 25 + 31 + 31) / 4 = 28) . เนื่องจากเป็นเพียงการเพิ่มลำดับของ summands จึงไม่สำคัญ
หนึ่ง | หนึ่ง | 7 | 7 | 16 | 16 | 25 | 25 | 31 | 31 |
เช่นเดียวกับขั้นตอนถัดไป:
7 | หนึ่ง | หนึ่ง | 7 | 16 | 16 | 25 | 25 | 31 | 31 |
การคำนวณจะเหมือนกับเวกเตอร์สุดท้าย: ((7 + 1 + 1 + 7) / 4 = 4) จะเท่ากับ ((1 + 1 + 7 + 7) / 4 = 4)
และจะใช้เช่นเดียวกันกับเวกเตอร์และขั้นตอนที่เหลือ
การคำนวณค่าเฉลี่ยเป็นเพียงผลรวมของค่าขององค์ประกอบในช่วงเวลาหารด้วยจำนวนองค์ประกอบในช่วงเวลา ซึ่งหมายความว่าเราสามารถคำนวณค่าเหล่านั้นล่วงหน้าและหลีกเลี่ยงการคำนวณซ้ำ L ครั้ง
มาดูขั้นตอนในการนำสิ่งที่เราจะเรียกว่าอัลกอริทึม FastSMQT ไปใช้กับตัวอย่างของเรา:
สร้างตารางที่มี 32 คอลัมน์และ 3 แถวดังที่คุณเห็นด้านล่าง แถวแรกในตารางแสดงถึงดัชนีของตาราง (0 ถึง 31) และไม่จำเป็นต้องรวมไว้เมื่อเขียนโค้ดตาราง แต่แสดงให้เห็นอย่างชัดเจนเพื่อให้ทำตามตัวอย่างได้ง่ายขึ้น
ทำซ้ำองค์ประกอบ N เมื่อนับความถี่ของแต่ละค่า ในตัวอย่างของเราองค์ประกอบ 1, 7, 16, 25 และ 31 ทั้งหมดมีความถี่เป็น 2 องค์ประกอบอื่น ๆ ทั้งหมดมีความถี่เป็น 0 ขั้นตอนนี้มีความซับซ้อนของ O (N)
อุตสาหกรรมการแต่งหน้าทำเงินได้เท่าไหร่ต่อปี
เมื่อเติมเวกเตอร์ความถี่แล้วเราจำเป็นต้องวนซ้ำเวกเตอร์นั้น (เวกเตอร์ความถี่ไม่ใช่เวกเตอร์อินพุต) เราจะไม่วนซ้ำองค์ประกอบ N อีกต่อไป แต่ R (R อยู่ในช่วง: 2 ^ L) ซึ่งในกรณีนี้คือ 32 (0 ถึง 31) เมื่อประมวลผลพิกเซล N สามารถมีค่าได้หลายล้าน (ล้านพิกเซล) แต่โดยปกติแล้ว R จะเป็น 256 (เวกเตอร์เดียวสำหรับแต่ละสี) ในตัวอย่างของเราคือ 32. เราจะเติมสองแถวต่อไปนี้ของตารางในเวลาเดียวกัน แถวแรก (แถวที่สองของตาราง) จะมีผลรวมของความถี่จนถึงตอนนี้ ตัวที่สอง (ที่สามของตาราง) จะมีผลรวมของมูลค่าขององค์ประกอบทั้งหมดที่ปรากฏจนถึงตอนนี้
ในตัวอย่างของเราเมื่อเราไปถึง 1 เราใส่ 2 ในแถวที่สองของตารางเพราะมี 1 สองตัวที่ปรากฏจนถึงตอนนี้ และเราใส่ 2 ในแถวที่สามของตารางด้วยเพราะ 1 + 1 = 2 เราเขียนค่าทั้งสองนั้นต่อไปในแต่ละตำแหน่งถัดไปจนกว่าเราจะถึง 7 เนื่องจากเลข 7 ปรากฏขึ้นสองครั้งเราจึงเพิ่ม 2 เข้าไปใน ตัวสะสมของแถวที่สองเนื่องจากตอนนี้มีตัวเลข 4 ตัวปรากฏขึ้นแล้ว (1, 1, 7, 7) และเราเพิ่ม 7 + 7 = 14 ในแถวที่สามทำให้ได้ 2 + 14 = 16 เพราะ 1 + 1 + 7 + 7 = 16 เราใช้อัลกอริทึมนี้ต่อไปจนกว่าเราจะทำซ้ำองค์ประกอบเหล่านั้นจนเสร็จ ความซับซ้อนของขั้นตอนนี้คือ O (2 ^ L) ซึ่งในกรณีของเราคือ O (32) และเมื่อทำงานกับพิกเซล RGB จะเป็น O (256)
ผม | 0 | หนึ่ง | 2 | ... | 6 | 7 | 8 | ... | สิบห้า | 16 | 17 | ... | 24 | 25 | 26 | ... | 30 | 31 |
n | 0 | 2 | 0 | ... | 0 | 2 | 0 | ... | 0 | 2 | 0 | ... | 0 | 2 | 0 | ... | 0 | 2 |
n- สะสม | 0 | 2 | 2 | ... | 2 | 4 | 4 | ... | 4 | 6 | 6 | ... | 6 | 8 | 8 | ... | 8 | 10 |
ผลรวม | 0 | 2 | 2 | ... | 2 | 16 | 16 | ... | 16 | 48 | 48 | ... | 48 | 98 | 98 | ... | 98 | 160 |
ขั้นตอนต่อไปคือการลบคอลัมน์ที่มีองค์ประกอบที่มีความถี่เป็น 0 ออกจากตารางและเพื่อให้เห็นตัวอย่างชัดเจนขึ้นเราจะลบแถวที่สองเนื่องจากไม่เกี่ยวข้องอีกต่อไปดังที่คุณเห็น
ผม | หนึ่ง | 7 | 16 | 25 | 31 |
n | 2 | 4 | 6 | 8 | 10 |
ผลรวม | 2 | 16 | 48 | 98 | 160 |
โปรดจำไว้ว่าเราสามารถใช้เวกเตอร์สุดท้าย (เรียงลำดับสมบูรณ์) เพื่อทำการคำนวณสำหรับแต่ละขั้นตอนและผลลัพธ์จะยังคงเหมือนเดิม โปรดทราบว่าในตารางนี้เรามีเวกเตอร์สุดท้ายที่มีการคำนวณล่วงหน้าทั้งหมดที่ทำไว้แล้ว
โดยพื้นฐานแล้วเราต้องทำอัลกอริทึม SMQT บนเวกเตอร์ขนาดเล็กนี้ แต่ต่างจากการทำบนเวกเตอร์ดั้งเดิมที่เราเริ่มต้นด้วยอันนี้จะง่ายกว่ามาก
ก่อนอื่นเราต้องคำนวณค่าเฉลี่ยของตัวอย่างทั้งหมด เราสามารถค้นหาได้อย่างง่ายดายโดย sum [31] / n [31] = 160/10 = 16 ดังนั้นเราจึงแบ่งตารางออกเป็นสองเวกเตอร์และเริ่มเขียนรหัสไบนารีสำหรับแต่ละรายการ:
ผม | หนึ่ง | 7 | 16 | 25 | 31 |
n | 2 | 4 | 6 | 8 | 10 |
ผลรวม | 2 | 16 | 48 | 98 | 160 |
รหัส | 0 | 0 | 0 | หนึ่ง | หนึ่ง |
ตอนนี้เราแยกเวกเตอร์แต่ละตัวอีกครั้ง ค่าเฉลี่ยของเวกเตอร์แรกคือ sum [16] / n [16] = 48/6 = 8 และค่าเฉลี่ยของเวกเตอร์ที่สองคือ: (sum [31] - sum [16]) / (n [31] - n [16]) = (160 - 48) / (10 - 6) = 112/4 = 28
ผม | หนึ่ง | 7 | 16 | 25 | 31 |
n | 2 | 4 | 6 | 8 | 10 |
ผลรวม | 2 | 16 | 48 | 98 | 160 |
รหัส | 00 | 00 | 01 | 10 | สิบเอ็ด |
เหลือเวกเตอร์เดียวที่จะแยก ค่าเฉลี่ยคือ: sum [7] / n [7] = 16/4 = 4
ผม | หนึ่ง | 7 | 16 | 25 | 31 |
n | 2 | 4 | 6 | 8 | 10 |
ผลรวม | 2 | 16 | 48 | 98 | 160 |
รหัส | 000 | 001 | 010 | 100 | 110 |
อย่างที่คุณเห็นรหัสสำหรับแต่ละองค์ประกอบจะเหมือนกันหากเราทำตามอัลกอริทึมดั้งเดิม และเราได้ทำ SMQT บนเวกเตอร์ที่มีขนาดเล็กกว่าเวกเตอร์ที่มีองค์ประกอบ N และเราได้คำนวณค่าทั้งหมดที่เราต้องการไว้ล่วงหน้าเพื่อหาค่าเฉลี่ยดังนั้นจึงสามารถคำนวณเวกเตอร์ที่เป็นผลลัพธ์ได้อย่างตรงไปตรงมาและรวดเร็ว
ความซับซ้อนของขั้นตอนนี้คือ O (L * (2 ^ L)) ซึ่งสำหรับ L = 8 และในความต้องการการประมวลผลภาพในทางปฏิบัติจะมีค่า O (8 * (256)) = O (2048) = ค่าคงที่
ขั้นตอนสุดท้ายคือการทำซ้ำองค์ประกอบ N อีกครั้งโดยแทนที่องค์ประกอบด้วยรหัสสำหรับแต่ละองค์ประกอบ: องค์ประกอบ [i] = รหัส [i] ความซับซ้อนคือ O (N) ความซับซ้อนของ FastSMQT คือ O (N) + O (2 ^ L) + O (L * (2 ^ L)) + O (N) = O (2 * N) + O ((L + 1) * (2 ^ L)) = O (N + L * (2 ^ L))
อัลกอริทึมทั้งสองสามารถขนานกันได้แม้ว่าจะมีประสิทธิภาพมากกว่าในการเรียกใช้หนึ่งอัลกอริทึมต่อคอร์แทนหากต้องเปลี่ยนเวกเตอร์หลายตัว ตัวอย่างเช่นเมื่อประมวลผลภาพเราสามารถประมวลผล RGB แต่ละช่องในคอร์ที่แตกต่างกันแทนที่จะทำการคำนวณทั้งสามแบบขนานกัน
ในการทำให้อัลกอริทึม SMQT ขนานกันเมื่อเราแบ่งเวกเตอร์เป็นสองเราสามารถประมวลผลเวกเตอร์ย่อยแต่ละตัวในคอร์ใหม่ได้หากมีคอร์ (จริงๆแล้วเวกเตอร์ย่อยหนึ่งในคอร์ปัจจุบันและอีกตัวในคอร์ใหม่) สามารถทำได้แบบวนซ้ำจนกว่าเราจะถึงจำนวนคอร์ทั้งหมดที่มี การแทนที่ค่าด้วยรหัสสามารถทำได้แบบขนานสำหรับ
วิธีการเรียนรู้โปรแกรมซี
อัลกอริทึม FastSMQT สามารถขนานกันได้ ในขั้นตอนแรกต้องแบ่งเวกเตอร์อินพุตออกเป็นจำนวนแกนที่มีอยู่ (C) ต้องสร้างเวกเตอร์ของการนับความถี่หนึ่งตัวสำหรับแต่ละส่วนเหล่านั้นและเติมแบบขนาน จากนั้นเราจะเพิ่มค่าของเวกเตอร์เหล่านั้นลงในเวกเตอร์ความถี่ผลลัพธ์หนึ่ง ขั้นตอนต่อไปที่สามารถขนานกันได้คือขั้นตอนสุดท้ายเมื่อเราแทนที่ค่าด้วยรหัส สามารถทำได้ควบคู่กันสำหรับ.
ความซับซ้อนทั้งหมดของอัลกอริทึม SMQT ดั้งเดิมคือ O ((2 * L + 1) * N) ซึ่งก็คือ O (L * N)
ความซับซ้อนของ FastSMQT คือ O (N) + O (2 ^ L) + O (L * (2 ^ L)) + O (N) = O (2 * N) + O ((L + 1) * (2 ^ L)) = O (N + L * (2 ^ L))
เมื่อกำหนด L คงที่ความซับซ้อนจะกลายเป็นเพียง O (N) สำหรับทั้งคู่ แต่ค่าคงที่ที่คูณ N นั้นน้อยกว่ามากสำหรับ FastSMQT และทำให้เวลาในการประมวลผลแตกต่างกันมากอย่างที่เราเห็น
กราฟต่อไปนี้จะเปรียบเทียบประสิทธิภาพของอัลกอริทึม SMQT และ FastSMQT สำหรับ L = 8 ซึ่งเป็นกรณีของการประมวลผลภาพ กราฟแสดงเวลา (เป็นมิลลิวินาที) ที่ใช้ในการประมวลผลองค์ประกอบ N โปรดสังเกตว่าความซับซ้อน (พร้อมค่าคงที่) ของ SMQT สำหรับ L = 8 คือ O (17 * N) ในขณะที่ FastSMQT คือ O (2 * N + 2304)
ยิ่ง N ใหญ่เท่าไหร่ SMQT ก็จะใช้เวลาประมวลผลภาพนานขึ้นเท่านั้น สำหรับ FastSMQT ในทางกลับกันการเติบโตจะช้ากว่ามาก
สำหรับค่า N ที่ใหญ่กว่าความแตกต่างของประสิทธิภาพจะชัดเจนกว่ามาก:
ที่นี่ SMQT ใช้เวลาหลายวินาทีในการประมวลผลภาพบางภาพในขณะที่ FastSMQT ยังคงอยู่ในโซน 'ไม่กี่มิลลิวินาที'
แม้ว่าจะมีหลายคอร์ (สองในกรณีนี้) FastSMQT ก็ยังเหนือกว่า SMQT อย่างชัดเจน:
FastSMQT ไม่ได้ขึ้นอยู่กับ L. SMQT ในทางกลับกันจะขึ้นอยู่กับค่า L แบบเชิงเส้นตัวอย่างเช่นเมื่อใช้ N = 67108864 รันไทม์ของ SMQT จะเพิ่มขึ้นตามค่า L ที่เพิ่มขึ้นในขณะที่ FastSMQT ไม่:
เทคนิคการเพิ่มประสิทธิภาพบางอย่างไม่สามารถใช้ได้กับทุกคน อัลกอริทึม และกุญแจสำคัญในการปรับปรุงประสิทธิภาพของอัลกอริทึมมักจะซ่อนอยู่ในข้อมูลเชิงลึกเกี่ยวกับวิธีการทำงานของอัลกอริทึม อัลกอริทึม FastSMQT นี้ใช้ประโยชน์จากความเป็นไปได้ของการคำนวณค่าล่วงหน้าและลักษณะของการคำนวณค่าเฉลี่ย ด้วยเหตุนี้จึงช่วยให้การประมวลผลเร็วขึ้นกว่า SMQT เดิม ความเร็วจะไม่ได้รับผลกระทบจากการเพิ่มขึ้นของ L แม้ว่า L จะไม่สามารถมากกว่า 8 ปกติได้มากนักเนื่องจากการใช้หน่วยความจำคือ 2 ^ L ซึ่งสำหรับ 8 คือ 256 ที่ยอมรับได้ (จำนวนคอลัมน์ในตารางความถี่ของเรา) แต่ประสิทธิภาพที่เพิ่มขึ้น มีประโยชน์ในทางปฏิบัติที่ชัดเจน
การปรับปรุงความเร็วนี้ทำให้ MiddleMatter ใช้อัลกอริทึมในไฟล์ แอปพลิเคชัน iOS (และ แอปพลิเคชัน Android ) ที่ปรับปรุงรูปภาพและวิดีโอที่ถ่ายในสภาพแสงน้อย ด้วยการปรับปรุงนี้ทำให้สามารถประมวลผลวิดีโอในแอปพลิเคชันได้ซึ่งจะช้าเกินไปสำหรับ ios อุปกรณ์
รหัส C ++ สำหรับอัลกอริทึม SMQT และ FastSMQT คือ พร้อมใช้งานบน GitHub .