การแปลงปริมาณเฉลี่ยต่อเนื่องที่ปรับให้เหมาะสมที่สุด

อัลกอริธึม Transform Mean Quantization Transform (SMQT) แบบต่อเนื่องคือการแปลงแบบไม่เชิงเส้นที่เปิดเผยองค์กรหรือโครงสร้างของข้อมูลและลบคุณสมบัติ เช่น กำไรและอคติ ในบทความชื่อ The Successive Mean Quantization Transform SMQT "นำไปใช้ในการประมวลผลคำพูดและการประมวลผลภาพ" อัลกอริธึมเมื่อนำไปใช้กับรูปภาพ “สามารถถูกมองว่าเป็นการเน้นรายละเอียดในภาพแบบก้าวหน้า”

ตามรายงานอีกฉบับหนึ่งที่ชื่อ SMQT-based Tone Mapping Operators for High Dynamic Range Images จะให้ผลลัพธ์เป็น “ภาพที่มีรายละเอียดที่ปรับปรุงแล้ว” บทความนี้อธิบายสองเทคนิคในการใช้การเปลี่ยนแปลงนี้กับรูปภาพ

1. ใช้ SMQT กับความสว่างของแต่ละพิกเซล - อธิบายสูตรเพื่อให้ได้ความสว่างจาก RGB ของแต่ละพิกเซล

2. ใช้ SMQT ในแต่ละช่องสัญญาณ RGB แยกกัน - สำหรับช่อง R, G และ B แยกกัน

ภาพต่อไปนี้แสดงผลของเทคนิคทั้งสอง:

เมื่อใช้เทคนิคที่ 2 กับรูปภาพของ Bruin Theatre ในเวลากลางคืน เราจะเห็นได้ว่าอัลกอริทึมซูมรายละเอียดของภาพไปเรื่อย ๆ และเผยให้เห็นรายละเอียดที่เดิมถูกความมืดซ่อนไว้ได้อย่างไร:

ในบทความนี้ เราจะพิจารณาอย่างละเอียดยิ่งขึ้นว่าอัลกอริธึมนี้ทำงานอย่างไร และสำรวจการปรับให้เหมาะสมอย่างง่ายที่ช่วยให้อัลกอริทึมมีประสิทธิภาพมากขึ้นในแอปพลิเคชันการประมวลผลภาพที่ใช้งานได้จริง

อัลกอริทึม SMQT

ในบทความต้นฉบับ อัลกอริธึมอธิบายในลักษณะนามธรรม เพื่อให้เข้าใจ SMQT มากขึ้น เราจะยกตัวอย่างง่ายๆ

สมมติว่าเรามีเวกเตอร์ต่อไปนี้ (คุณสามารถคิดเหมือนอาร์เรย์):

ในกรณีของภาพสี เราสามารถมองได้ว่าเป็นเวกเตอร์ที่แยกจากกันสามเวกเตอร์ แต่ละอันแสดงถึงช่องสัญญาณสีเฉพาะ (RGB) และแต่ละองค์ประกอบของเวกเตอร์แสดงถึงความเข้มของพิกเซลที่เกี่ยวข้อง

ขั้นตอนที่เกี่ยวข้องในการใช้อัลกอริทึม SMQT คือ:

1. คำนวณค่าเฉลี่ยของเวกเตอร์ ซึ่งในกรณีนี้คือ 29.58

2. แบ่งเวกเตอร์ออกเป็นสองส่วน โดยปล่อยให้ตัวเลขที่น้อยกว่าหรือเท่ากับ 29.58 ในครึ่งซ้าย และตัวเลขที่มากกว่าในครึ่งขวา:

   15	4	0	5	18	32	48	60	64	59	47	31
   0	0	0	0	0	1	1	1	1	1	1	1

   แถวที่สองคือรหัสที่เราจะสร้างสำหรับแต่ละค่า ค่าที่ต่ำกว่าหรือเท่ากับ 29.58 จะได้รับ 0 ในโค้ด และตัวเลขที่มากกว่า 29.58 จะได้รับ 1 (นี่คือเลขฐานสอง)

3. ตอนนี้เวกเตอร์ผลลัพธ์ทั้งสองถูกแยกแยกกัน แบบเรียกซ้ำ ตามกฎเดียวกัน ในตัวอย่างของเรา ค่าเฉลี่ยของเวกเตอร์แรกคือ (15 + 4 + 0 + 5 + 18) / 5 = 8.4 และค่าเฉลี่ยของเวกเตอร์ที่สองคือ (32 + 48 + 60 + 64 + 59 + 47 + 31) / 7 = 48.7 เวคเตอร์สองตัวแต่ละตัวนั้นถูกแยกออกเป็นเวคเตอร์อีกสองตัว และเพิ่มโค้ดบิตที่สองในแต่ละอันขึ้นอยู่กับการเปรียบเทียบกับค่าเฉลี่ย นี่คือผลลัพธ์:

   4	0	5	15	18	32	47	31	48	60	64	59
   00	00	00	01	01	10	10	10	11	11	11	11

   โปรดทราบว่าจะมีการเติม 0 อีกครั้งสำหรับตัวเลขที่ต่ำกว่าหรือเท่ากับค่าเฉลี่ย (สำหรับเวกเตอร์แต่ละตัว) และ 1 สำหรับตัวเลขที่มากกว่าค่าเฉลี่ย

4. อัลกอริทึมนี้ซ้ำแล้วซ้ำอีก:

   0	4	5	15	18	32	31	47	48	60	64	59
   000	001	001	010	011	100	100	101	110	111	111	111

   0	4	5	15	18	31	32	47	48	60	59	64
   0000	0010	0011	0100	0110	1000	1001	1010	1100	1110	1110	1111

   0	4	5	15	18	31	32	47	48	59	60	64
   00000	00100	00110	01000	01100	10000	10010	10100	11000	11100	11101	11110

   ณ จุดนี้เวกเตอร์ทุกตัวมีองค์ประกอบเพียงตัวเดียว ดังนั้นสำหรับทุกๆ ขั้นตอนที่ต่อเนื่องกัน จะมีการเพิ่ม 0 เนื่องจากตัวเลขจะเท่ากับตัวมันเองเสมอ (เงื่อนไขสำหรับ 0 คือตัวเลขต้องน้อยกว่าหรือเท่ากับค่าเฉลี่ย ซึ่งก็คือตัวมันเอง)

จนถึงตอนนี้ เรามีระดับการหาปริมาณของ L=5 หากเราจะใช้ L=8 เราต้องต่อท้าย 0 สามตัวในแต่ละรหัส ผลลัพธ์ของการแปลงแต่ละรหัสจากไบนารีเป็นจำนวนเต็ม (สำหรับ L=8) จะเป็น:

เวกเตอร์สุดท้ายถูกจัดเรียงตามลำดับที่เพิ่มขึ้น ในการรับเวกเตอร์เอาต์พุต เราต้องแทนที่ค่าดั้งเดิมของเวกเตอร์อินพุตด้วยรหัสของมัน

สังเกตว่าในเวกเตอร์ผลลัพธ์:

• กำไรถูกลบออก อันเดิมมีอัตราขยายต่ำโดยมีช่วงตั้งแต่ 0 ถึง 64 ตอนนี้การเพิ่มขึ้นจาก 0 เป็น 240 ซึ่งเกือบจะเป็นช่วง 8 บิตทั้งหมด ว่ากันว่าเกนถูกเอาออกเพราะไม่สำคัญว่าเราคูณองค์ประกอบทั้งหมดของเวกเตอร์ดั้งเดิมด้วยตัวเลข เช่น 2 หรือถ้าเราหารทั้งหมดด้วย 2, เวกเตอร์เอาต์พุตจะเท่ากัน ช่วงของมันจะเกี่ยวกับช่วงทั้งหมดของเวกเตอร์ปลายทาง (8 บิตสำหรับ L=8) หากเราคูณเวกเตอร์อินพุตด้วยสอง เวกเตอร์เอาต์พุตจะเท่ากัน เพราะในแต่ละขั้นตอน ตัวเลขเดียวกันที่อยู่ต่ำกว่าหรือสูงกว่าค่าเฉลี่ยจะยังคงต่ำกว่าหรือสูงกว่านั้น และเราจะบวก 0 หรือ 1 เดียวกัน สู่ผลลัพธ์ เฉพาะในกรณีที่เราหารกัน ผลลัพธ์จะออกมาใกล้เคียงกัน และไม่เหมือนกันทุกประการ เพราะเลขคี่อย่าง 15 จะต้องถูกปัดเศษและการคำนวณอาจแตกต่างกันไป เราเปลี่ยนจากภาพที่มืดไปเป็นภาพที่มีพิกเซลตั้งแต่สีเข้ม (0) ไปจนถึงสีอ่อนกว่า (240) โดยใช้ช่วงทั้งหมด
• อคติถูกลบออก แม้ว่าเราจะสังเกตได้ยากในตัวอย่างนี้ นี่เป็นเพราะว่าเราไม่มีอคติเนื่องจากค่าต่ำสุดของเราคือ 0 หากเรามีอคติจริงๆ ค่านั้นจะถูกลบออก ถ้าเรานำตัวเลข 'K' ใดๆ มาบวกเข้ากับแต่ละองค์ประกอบของเวกเตอร์อินพุต การคำนวณตัวเลขด้านบนและด้านล่างของค่าเฉลี่ยในแต่ละขั้นตอนจะไม่แตกต่างกัน ผลลัพธ์จะยังคงเหมือนเดิม สิ่งนี้จะทำให้ภาพที่สว่างเกินไปที่จะกลายเป็นภาพที่มีตั้งแต่สีเข้มไปจนถึงสีอ่อน
• เรามีรูปภาพพร้อมรายละเอียดที่ปรับปรุงแล้ว สังเกตว่าในแต่ละขั้นตอนแบบเรียกซ้ำ เรากำลังขยายรายละเอียด และสร้างผลลัพธ์โดยเปิดเผยรายละเอียดเหล่านั้นให้มากที่สุด และเนื่องจากเราจะนำเทคนิคนี้ไปใช้กับ RGB แต่ละช่องสัญญาณ เราจะเปิดเผยรายละเอียดให้มากที่สุด แม้ว่าจะสูญเสียข้อมูลเกี่ยวกับโทนสีดั้งเดิมของแต่ละสีไปก็ตาม

ให้ภาพเหมือนเวกเตอร์ของพิกเซล RGB โดยแต่ละจุดมี 8 บิตสำหรับ R, 8 สำหรับ G และ 8 สำหรับ B; เราสามารถแยกเวกเตอร์ออกมาได้สามตัว หนึ่งตัวสำหรับแต่ละสี และใช้อัลกอริทึมกับเวกเตอร์แต่ละตัว จากนั้นเราสร้างเวกเตอร์ RGB อีกครั้งจากเวกเตอร์เอาท์พุตทั้งสาม และเราได้ภาพที่ประมวลผล SMQT เหมือนกับที่ทำกับหนึ่งในโรงละครบรูอิน

ความซับซ้อน

อัลกอริธึมกำหนดให้สำหรับแต่ละระดับของการหาปริมาณ (L) องค์ประกอบ N จะต้องได้รับการตรวจสอบในรอบแรกเพื่อค้นหาค่าเฉลี่ยสำหรับเวกเตอร์แต่ละตัว จากนั้นในรอบที่สอง องค์ประกอบ N แต่ละองค์ประกอบจะต้องถูกเปรียบเทียบกับค่าเฉลี่ยที่สอดคล้องกันใน เพื่อแยกเวกเตอร์แต่ละตัวออก สุดท้ายต้องแทนที่องค์ประกอบ N ด้วยรหัส ดังนั้นความซับซ้อนของอัลกอริทึมคือ O((L*2*N) + N) = O((2*L + 1)*N) ซึ่งก็คือ O(L*N)

กราฟที่ดึงออกมาจากกระดาษมีความสอดคล้องกับความซับซ้อนของ O(L*N) ยิ่งค่า L ต่ำลง การประมวลผลก็จะยิ่งเร็วขึ้นในลักษณะเชิงเส้นโดยประมาณ (จำนวนเฟรมต่อวินาทีมากขึ้น) เพื่อปรับปรุงความเร็วในการประมวลผล กระดาษแนะนำให้ลดค่า L: “การเลือกระดับ L ให้ต่ำลงอาจเป็นวิธีโดยตรงในการลดความเร็วในการประมวลผล แต่ด้วยคุณภาพของภาพที่ลดลง”

การปรับปรุง

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

ไม่สามารถแยกเวกเตอร์ได้อีกต่อไป และต้องเติมศูนย์ต่อท้ายจนกว่าเราจะได้ค่า 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):

สังเกตอีกครั้งว่าถ้าเราใช้เวกเตอร์สุดท้าย อันที่เรียงสมบูรณ์ ผลลัพธ์จะเหมือนกัน สำหรับ 6 องค์ประกอบแรก เรามี: ((1 + 1 + 7 + 7 + 16 + 16) / 6 = 8) และสำหรับ 4 องค์ประกอบสุดท้าย: ((25 + 25 + 31 + 31) / 4 = 28) . เนื่องจากมันเป็นเพียงส่วนเสริม ลำดับของคำสั่งจึงไม่สำคัญ

เช่นเดียวกับขั้นตอนต่อไป:

การคำนวณจะเหมือนกับเวกเตอร์สุดท้าย: ((7 + 1 + 1 + 7) / 4 = 4) จะเท่ากับ ((1 + 1 + 7 + 7) / 4 = 4)

และเช่นเดียวกันกับเวกเตอร์และขั้นตอนที่เหลือ

การคำนวณหาค่าเฉลี่ยเป็นเพียงผลรวมของค่าขององค์ประกอบในช่วงเวลา หารด้วยจำนวนขององค์ประกอบในช่วงเวลานั้น ซึ่งหมายความว่าเราสามารถคำนวณค่าเหล่านั้นล่วงหน้าและหลีกเลี่ยงการคำนวณซ้ำ L ครั้ง

มาดูขั้นตอนในการใช้สิ่งที่เราเรียกว่าอัลกอริทึม FastSMQT กับตัวอย่างของเรา:

1. สร้างตารางที่มี 32 คอลัมน์และ 3 แถวดังที่คุณเห็นด้านล่าง แถวแรกในตารางแสดงถึงดัชนีของตาราง (0 ถึง 31) และไม่จำเป็นต้องรวมอยู่ด้วยเมื่อเข้ารหัสตาราง แต่มันแสดงให้เห็นอย่างชัดเจนเพื่อให้ตัวอย่างง่ายต่อการติดตาม

2. วนซ้ำองค์ประกอบ N เมื่อนับความถี่ของแต่ละค่า ในตัวอย่างของเรา องค์ประกอบ 1, 7, 16, 25 และ 31 ทั้งหมดมีความถี่ 2 องค์ประกอบอื่นๆ ทั้งหมดมีความถี่เป็น 0 ขั้นตอนนี้มีความซับซ้อนของ O(N)

3. เมื่อเติมเวกเตอร์ความถี่แล้ว เราจำเป็นต้องวนซ้ำเวกเตอร์นั้น (เวกเตอร์ความถี่ ไม่ใช่เวกเตอร์อินพุต) เราไม่ทำซ้ำองค์ประกอบ 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	1	2	...	6	7	8	...	15	16	17	...	24	25	26	...	30	31
   น	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

4. ขั้นตอนต่อไปคือการลบคอลัมน์ที่มีองค์ประกอบที่มีความถี่ 0 ออกจากตาราง และเพื่อดูตัวอย่างที่ชัดเจนยิ่งขึ้น เราจะลบแถวที่สองออกด้วยเนื่องจากไม่เกี่ยวข้องอีกต่อไป อย่างที่คุณเห็น

   ฉัน	1	7	16	25	31
   น	2	4	6	8	10
   ผลรวม	2	16	48	98	160

5. จำไว้ว่าเราสามารถใช้เวคเตอร์สุดท้าย (เรียงตามลำดับทั้งหมด) เพื่อทำการคำนวณสำหรับแต่ละขั้นตอน และผลลัพธ์จะยังเหมือนเดิม โปรดทราบว่าในตารางนี้ เรามีเวกเตอร์สุดท้ายที่มีการคำนวณล่วงหน้าทั้งหมดที่ทำไว้แล้ว

   โดยพื้นฐานแล้วเราต้องทำอัลกอริธึม SMQT บนเวกเตอร์ขนาดเล็กนี้ แต่ต่างจากการทำบนเวกเตอร์ดั้งเดิมที่เราเริ่มด้วย อันนี้จะง่ายกว่ามาก

   อันดับแรก เราต้องคำนวณค่าเฉลี่ยของกลุ่มตัวอย่างทั้งหมด เราหาได้ง่ายโดย: sum[31] / n[31] = 160 / 10 = 16 เราจึงแบ่งตารางออกเป็นเวกเตอร์สองเวกเตอร์ และเริ่มเขียนโค้ดไบนารีสำหรับแต่ละรายการ:

   ฉัน	1	7	16	25	31
   น	2	4	6	8	10
   ผลรวม	2	16	48	98	160
   รหัส	0	0	0	1	1

   ตอนนี้เราแยกเวกเตอร์แต่ละตัวอีกครั้ง ค่าเฉลี่ยของเวกเตอร์แรกคือ: sum[16] / n [16] = 48 / 6 = 8 และค่าเฉลี่ยของเวกเตอร์ที่สองคือ: (sum[31] – sum[16]) / (n[31] – n [16]) = (160 – 48) / (10 – 6) = 112 / 4 = 28

   ฉัน	1	7	16	25	31
   น	2	4	6	8	10
   ผลรวม	2	16	48	98	160
   รหัส	00	00	01	10	11

   เหลือเวกเตอร์เดียวเท่านั้นที่จะแยก ค่าเฉลี่ยคือ: ผลรวม[7] / n[7] = 16 / 4 = 4

   ฉัน	1	7	16	25	31
   น	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) = ค่าคงที่

6. ขั้นตอนสุดท้ายคือการวนซ้ำองค์ประกอบ 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