อัลกอริทึมการแปลงปริมาณเฉลี่ยเฉลี่ยต่อเนื่อง (SMQT) คือการแปลงแบบไม่เป็นเชิงเส้นที่เปิดเผยองค์กรหรือโครงสร้างของข้อมูลและลบคุณสมบัติต่างๆเช่นกำไรและอคติ ในกระดาษชื่อ การแปลงปริมาณเฉลี่ยต่อเนื่อง , SMQT ถูก 'นำไปใช้ในการประมวลผลคำพูดและการประมวลผลภาพ' อัลกอริทึมเมื่อนำไปใช้กับรูปภาพ 'สามารถมองเห็นได้ว่าเป็นโปรเกรสซีฟโฟกัสที่รายละเอียดในภาพ'

อัลกอริทึมการแปลงค่าเฉลี่ยเชิงปริมาณเฉลี่ยต่อเนื่องที่ได้รับการปรับปรุง ทวีต

ตามกระดาษอื่นที่ชื่อ ตัวดำเนินการ Tone Mapping ที่ใช้ SMQT สำหรับภาพช่วงไดนามิกสูง มันจะให้ 'ภาพที่มีรายละเอียดขั้นสูง' บทความนี้อธิบายถึงเทคนิคสองประการในการนำการเปลี่ยนแปลงนี้ไปใช้กับรูปภาพ

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

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

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

ที่มา: ตัวดำเนินการ Tone Mapping ที่ใช้ SMQT สำหรับภาพช่วงไดนามิกสูง

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

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

อัลกอริทึม SMQT

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

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

32

48

60

64

59

47

31

สิบห้า

4

0

5

18

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

ประกายไฟใช้ทำอะไร

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

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

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

   สิบห้า	4	0	5	18	32	48	60	64	59	47	31
   0	0	0	0	0	หนึ่ง	หนึ่ง	หนึ่ง	หนึ่ง	หนึ่ง	หนึ่ง	หนึ่ง

   แถวที่สองคือรหัสที่เราจะสร้างสำหรับแต่ละค่า ค่าที่ต่ำกว่าหรือเท่ากับ 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	สิบห้า	18	32	47	31	48	60	64	59
   00	00	00	01	01	10	10	10	สิบเอ็ด	สิบเอ็ด	สิบเอ็ด	สิบเอ็ด

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

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

   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

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

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

ให้ภาพเหมือนเวกเตอร์ของพิกเซล 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)

ที่มา: ตัวดำเนินการ Tone Mapping ที่ใช้ SMQT สำหรับภาพช่วงไดนามิกสูง

กราฟที่ดึงออกมาจากกระดาษสอดคล้องกับความซับซ้อน 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 ไปใช้กับตัวอย่างของเรา:

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	หนึ่ง	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

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

   ผม	หนึ่ง	7	16	25	31
   n	2	4	6	8	10
   ผลรวม	2	16	48	98	160

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

   โดยพื้นฐานแล้วเราต้องทำอัลกอริทึม 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) = ค่าคงที่

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 .