Зургийн дохионы дискрет косинусын хувиргалт. Ортогональ хувиргалтыг ашиглан дижитал дүрсийг шахах алгоритмууд

Хяналт

Харилцаа холбоо, холбоо, радио электроник, тоон төхөөрөмж

Ортогональ хувиргалт дээр суурилсан эх зургийг хувиргах алгоритмууд Дискрет Фурье хувиргалт болон бусад төрлийн ортогональ хувиргалтуудын ижил төстэй болон ялгаатай талууд юу вэ? Ортогональ хувиргалтуудын нэг бол дискрет Фурье хувиргалт юм. Хүчтэй дүрсийг ортогональ хувиргалт хийх явцад хамааралзэргэлдээ элементүүдийн хооронд тохиолддог ...

2.4. Ортогональ хувиргалт дээр суурилсан эх зургийг хувиргах алгоритмууд (Ортогональ хувиргалт дээр суурилсан эх зургийг хувиргах алгоритмыг ямар зорилгоор ашиглаж болох вэ? Дискрет Фурьегийн хувиргалт болон бусад төрлийн ортогональ хувиргалтуудын ижил төстэй, ялгаа нь юу вэ?).

Зарим тохиолдолд өгөгдлийн хэмжээг багасгах эсвэл таних дараагийн үе шатанд объектын шинж чанарыг задлах процедурыг хөнгөвчлөхийн тулд эхлээд хоёр хэмжээст массивыг хувиргах нь зүйтэй.Э и, ж ] коэффициент утгуудын массив руу [Ф у, в ], анхны зурагтай ижил MxN форматтай.

Хоёрдогч массив эсвэл өөрөөр хэлбэл коэффициентүүдийн матрицыг хувиргагч гэж нэрлэдэг. Ортогональ хувиргалтуудын нэг бол дискрет Фурье хувиргалт юм. Фурье хувирлын хувьд хувиргагч нь зургийн хоёр хэмжээст орон зайн спектрээс өөр зүйл биш юм.

IN ерөнхий тохиолдолаливаа өөрчлөлт анхны зурагОртогональ операторууд дээр тулгуурлан дүрсийг ерөнхий хоёр хэмжээст спектр болгон задлах үйлдэл, коэффициентийг (өөрөөр хэлбэл хувиргагч элементүүд) харгалзах спектрийн бүрэлдэхүүн хэсгүүдийн далайц гэж үзэж болно. Үндсэн функц болгон ашиглахгүй бол гэдгийг анхаарна уу гармоник функцууд, дараа нь орон зайн давтамжийн тухай ойлголтыг ерөнхийд нь гаргаж, дарааллын тухай ойлголтыг ашиглах хэрэгтэй.

Дараалал тоо хэмжээ гэж нэрлэдэг хагастай тэнцүүнэгж хугацаанд буюу нэгж урт дахь тэг огтлолын дундаж тоо.

Хөрш зэргэлдээх элементүүдийн хооронд хүчтэй хамаарал бүхий дүрсийг ортогональ хувиргах явцад декорреляци (цагаанжилт) үүсдэг. Тиймээс хувиргах элементүүдийн утгууд нь бараг хамааралгүй болж хувирдаг. Дунджаар тодорхойлогддог анхны массиваас ялгаатай жигд хуваарилалтэлементүүдийн хоорондох дохионы энерги, трансформатор дахь дохионы энергийн тархалт туйлын жигд бус байна. Эрчим хүчний гол хувийг жижиг элементүүдээс авдаг серийн дугаарууд(өөрөөр хэлбэл бага орон зайн дарааллын хувьд) болон бусад хүмүүсийн хувьд зөвхөн багахан хувийг эзэлдэг (Зураг 2. 3-ыг үз).

Цагаан будаа. 2. 3. Тусдаа элементүүдийн хоорондох дохионы энергийн хуваарилалт
анхны массив (a) болон хувиргагч (b)-д.

Энэ нөхцөл байдал нь үүнийг бүрмөсөн хаях боломжийг бидэнд олгодог (өөрөөр хэлбэл тэгтэй тэнцүү) ихэнх ньэлементүүдийг хувиргах (энэ нь үндсэндээ бага дамжуулалттай орон зайн шүүлтүүр гэсэн үг) эсвэл хоёртын кодын хамгийн бага тооны битийг ашиглан тэдгээрийг цөөн тооны түвшинд квантлах.

Дижитал дүрс боловсруулахад ашигладаг хамгийн түгээмэл ортогональ хувиргалтын төрлүүдийг авч үзье.

Энд магадлал байнаФ у ерөнхийдөө тэдгээр нь нийлмэл тоо юм

Дискрет Фурье хувиргалт

Нарийн төвөгтэй коэффициент бүрийг хоёр бодит бүрэлдэхүүнээр сольж болно. Эдгээр бүрэлдэхүүн хэсгүүд нь далайц ба фазын орон зайн салангид спектрийг тус тус тодорхойлдог бөгөөд дараах байдлаар тодорхойлогддог.

Гол сул тал салангид хувиргалтФурьетэй харьцуулахад их хэмжээний эзэлхүүнтооцоо, түүнчлэн хэмнэх хэрэгцээ их тооижил дүрсийг сэргээх алдаатай (өөрөөр хэлбэл ижил мэдээллийн алдагдалтай) бусад ортогональ хувиргалтуудтай харьцуулахад хувиргагчийн бүрэлдэхүүн хэсгүүд. Үүнээс гадна нарийн төвөгтэй коэффициентүүдийн бие даасан бүрэлдэхүүн хэсгүүдийг хадгалах шаардлагатай илүү том хэмжээ-аас илүү санах ой бодит үнэ цэнэанхны массивын элементүүд. Дискрет Фурье хувиргалтын талаар ярихдаа тусгайлан боловсруулсан алгоритмуудыг ашиглах боломжийг дурдах нь зүйтэй.хурдан Фурье хувиргалт, түүнчлэн тэдгээрийг хэрэгжүүлэхэд зориулагдсан тусгай тооцоолох төхөөрөмжүүдийн тухайсистолын процессорууд.

Уолшийн хувиргалт(M = N-тэй)

Хариуд нь коэффициентүүд bk(Z) дараах байдлаар тодорхойлогддог. b k (Z ) нь k-ийн утгатай тэнцүү байна -тооны хоёртын кодын тухайн цифр l-ээс бүрдэх Z хоёртын цифрүүд. Хэрэв, жишээ нь, Z = 10, өөрөөр хэлбэл. 10 10 =1010 2, тэгвэл
b 0 = 0; b 1 = 1; b 2 = 0; b 3 = 1.

б к Уолшийн хувиргалт дахь тэдгээрийг тодорхойлох дүрмийн дагуу тодорхойлогддог.

Хадамард хувиргалт(M = N-тэй)

Энэ нь ойлгомжтой бүх төрлийн ортогональ хувиргалт нь буцаах боломжтой, өөрөөр хэлбэл урвуу хувиргах процедурыг ашигласнаар та хувиргагчаас анхны зургийг сэргээж болно.

[E i, j ] анхны зургийн форматын массив NxN, энд j мөрийн дугаар, i элементийн баганын тоо (мөр дэх элементийн тоо); [Ф у, в ] ижил форматтай дүрс хувиргах NxN, энд u ба v Трансформаторын элементүүдийн мөр ба баганын дугаар тус тус. Дараа нь, ерөнхий тохиолдолд, ортогональ хувирлын төрлөөс үл хамааран бид бичнэ

Энд a (i, j, u, v) ба b (i, j, u, v) шууд ба урвуу хувиргалтын үндсэн функцууд.

Практик талаас нь авч үзвэл дээр дурдсан бүх төрлийн ортогональ хувиргалтыг хувьсагчид салгах боломжтой гэдгийг анхаарах нь чухал юм. Тиймээс шууд ба урвуу хоёр хэмжээст ортогональ хувиргалтын тооцоог нэг хэмжээст хувиргалтыг дараалан гүйцэтгэх хүртэл багасгаж болно.

Энд a p (i, u), b (i, u) ба a (j, v), b (j, v) мөр, баганын чиглэлийн дагуух шууд ба урвуу хувиргалтын үндсэн функцууд.

Бичлэг хийх, тооцоолоход хялбар байхын тулд матрицын аппарат ашиглахыг зөвлөж байна

Энд [A e] ба [A p ] шууд хувиргах матрицууд; [ V e ] ба [ V х ] урвуу хувиргах матрицууд; [Ахуудас ] t ба [V хуудас ] t матрицуудыг шилжүүлсний үр дүнд олж авсан матрицууд [ A хуудас ] ба [ B хуудас ].

Мэдээжийн хэрэг, хэлбэрээс үл хамааран математик дүрслэл, хоёр хэмжээст массивын шууд ба урвуу ортогональ хувиргалт нь ерөнхий тохиолдолд тооцооллын ихээхэн зардал шаарддаг. Үүнийг дизайн хийхдээ анхаарч үзэх хэрэгтэй

ATSN бодит цаг хугацаанд ажилладаг. Гэсэн хэдий ч, хоёртын дүрсийг дижитал боловсруулах үед, ялангуяа хоёртын суурь функцийг (Уолш, Хадамард гэх мэт хувиргалт) ашиглах тохиолдолд ортогональ хувиргалт хийх процедурыг ихээхэн хялбаршуулдаг.

“Хэвлэх дэх зураг” - Хэвлэх үеийн зургийн онцлог. Полионы гол шинж чанар график дүрс. Ном. Онцлог шинж чанархамгийн нарийн хэвлэх ажил. Олон талт байдал Массив байдал Олон нийтэд хүртээмжтэй байдал. Зургийг тексттэй холбох. Номын урлаг. Фонт.

“Вектор ба растер график” - Вектор командуудыг тайлбар ашиглан тодорхойлсон. Вектор ба растер дүрсийг бүтээх зарчим. Вектор зураг нь харьцангуй бага хэмжээний санах ой эзэлдэг. Төрөл зүйл компьютер график. Вектор дүрсийг хэдэн арван, заримдаа хэдэн мянган тушаалаар дүрсэлсэн байдаг. Растер графикийн сул тал.

"Компьютер график" - Растер графиктай ажиллахад тулгардаг гол бэрхшээлүүд. Компьютер графикийн төрлүүд нь дүрс үүсгэх зарчмаараа ялгаатай байдаг. Компьютерийн график. Фрактал график. Компьютерийн графикийн төрлүүд. Их хэмжээний өгөгдөл. Пиксел. Харьцуулсан шинж чанаруудрастер ба вектор график. Дэлгэц дээрх цэг бүр "хар" эсвэл "цагаан" гэсэн хоёр төлөвтэй байж болно.

"График зураг үүсгэх" - Зургийн хил хязгаар. Даалгавар 4. Автомат дүрсүүдээс бүрдсэн зураг бүтээ. Draw toolbar ашиглан зураг үүсгэ. Текст дэх график дүрсийн байрлал. Цуглуулгын зургийг текст рүү оруулна. Канвас. Растер ба вектор графикийн харьцуулсан шинж чанар. Бүтээлийн онцлог вектор зураг Word 2003 орчинд.

"Хүний толгойн дүр төрх" - Бусад хүйтэн, үхсэн царайг шорон шиг тороор хаасан байдаг. Бусад нь хэн ч амьдраагүй, удаан хугацаанд цонхоор харж байгаагүй цамхаг шиг. Ямар төрлийн хөрөг зураг байдаг вэ? Хүний нүүрний харьцаа. Нүүрний онцлогийг харуулсан зураг. Хүний царай, сэтгэл хөдлөл. Н.Заболоцкий. Ямар төрлийн нүүр царай байдаг вэ? Хүний толгойн зураг. Үнэхээр дэлхий агуу бас гайхалтай юм!

"Растр зураг" - Туршилтын дүгнэлт. Улаан. Компьютер ямар үндсэн өнгийг ашигладаг вэ? График мэдээллийн растер кодчилол. Растер зураг. Пиксел өөр өөр өнгө. Цэнхэр (оюу). Саарал. Ягаан. Палетт орчин үеийн компьютерууд. Бүх өнгийг дугаарлаж, тоо бүрийг хоёртын код болгон хувиргаж болно.

Нэг хэмжээст болон олон хэмжээст дохио, түүний дотор дүрсийг боловсруулах хамгийн түгээмэл хэрэгслийн нэг бол ортогональ хувиргалт юм. Дижитал телевизэд хоёртын тэмдгийн дамжуулах хурдыг бууруулах, улмаар холбооны сувгийн шаардлагатай давтамжийн зурвасыг багасгах асуудлыг шийдвэрлэхэд ортогональ хувиргалтын үүрэг онцгой ач холбогдолтой юм. Ортогональ хувиргалтын мөн чанар нь анхны дохиог ортогональ суурь функцүүдийн нийлбэр хэлбэрээр илэрхийлэх явдал юм.

x(t) ба y(t) функцуудыг хэрчим (t 1, t 2) дээр ортогональ гэж нэрлэнэ гэдгийг санаарай. цэгийн бүтээгдэхүүнтэгтэй тэнцүү

Энэ тодорхойлолтыг тоонуудын дараалалаар илэрхийлэгдсэн салангид дохиогоор өргөжүүлж болно. Хэрэв нөхцөл хангагдсан бол тус бүр нь N түүвэртэй x(n) ба y(n) салангид дохиог ортогональ гэж нэрлэдэг.

Хамгийн нэг нь алдартай жишээнүүдОртогональ хувиргалтын хэрэглээ нь үечилсэн дохио x-ийг Фурье цуврал болгон өргөжүүлэх явдал юм.

Хаана: ; T - дохионы давтагдах хугацаа x(t).

Фурье цувралын бодит коэффициентийг харилцаа холбоогоор тодорхойлно

IN нарийн төвөгтэй хэлбэрФурье цувралын өргөтгөл нь дараах хэлбэртэй байна.

Нарийн төвөгтэй гармоник далайц;

j нь төсөөллийн нэгж юм.

Зөвхөн T үетэй үечилсэн дохио төдийгүй зөвхөн хугацааны интервалд (-T/2, T/2) 0-ээс ялгаатай дохиог Фурье цуврал болгон өргөжүүлж болно. Энэ тохиолдолд бүх хугацааны тэнхлэгийн дагуу T үетэй дохионы үечилсэн үргэлжлэлийг ашигладаг.

n = 0.1, ..., N-1-ийн хувьд 0-ээс ялгаатай дискрет дохио x(n)-ийг авч үзье. Ийм дохионы хувьд синусоид функцүүдийн суурь өргөтгөлийг нэвтрүүлэх боломжтой. Учир нь давтамжийн спектрДээж авсан дохиог Котельниковын теоремын нөхцөлийн дагуу дээрээс нь хязгаарлах ёстой бөгөөд дискрет дохионы задрал хэвээр байна. эцсийн тоодавтамжийн бүрэлдэхүүн хэсгүүд нь салангид нийлмэл гармоник функцууд юм. Дискрет Фурье хувиргалт (DFT) гэж нэрлэгддэг энэхүү өргөтгөл нь хэлбэртэй байна

N=0, 1…N-1,(2.6)

Энд DFT коэффициентууд X(k) хамаарлаар тодорхойлогддог

K=0, 1…N-1,(2.7)

(2.7)-ын дагуу X(k) коэффициентийг олохыг ихэвчлэн урагшлах DFT, (2.6)-ын дагуу эдгээр коэффициентуудаас дохио авахыг урвуу DFT гэж нэрлэдэг гэдгийг эргэн санацгаая.

Эдгээр харилцаанд анхны дохио нь тасралтгүй биш, харин салангид байдаг тул интегралын оронд нийлбэрүүд гарч ирэв. Задаргаанд ашигласан давтамж аналог дохиомөн rad/s хэмжигдэхүүнтэй бол DFT-д k=0, 1...N-1 хэмжигдэхүүнгүй хэмжигдэхүүн байна. Харьцаа нь түүвэрлэлтийн давтамжийн хэдэн хэсэг нь өгөгдсөн дискрет гармоникийн давтамж болохыг харуулдаг.

(2.6), (2.7) дахь DFT коэффициентууд Х(k) ба экспоненциал хүчин зүйлүүд нь комплекс тоо юм. Цогцолбор тоо бүр нь дижитал санах ойд түүний бодит болон төсөөллийн хэсгүүдийг илэрхийлсэн хос бодит тоо хэлбэрээр хадгалагддаг. Хоёр нэмэх нийлмэл тооБодит тоог нэмэх хоёр үйлдлийг гүйцэтгэх шаардлагатай - бодит ба төсөөллийн хэсгүүдийг тусад нь нэмнэ. Хоёр нийлмэл тоог үржүүлэхэд дөрвөн үржүүлэх үйлдэл, бодит тоог нэмэх хоёр үйлдэл шаардлагатай. Тиймээс DFT-ийг нарийн төвөгтэй хэлбэрээр гүйцэтгэх нь шаардлагатай санах ойн хэмжээ, тооцоолох хугацааг мэдэгдэхүйц нэмэгдүүлэхэд хүргэдэг.

Зөвхөн харьцах бодит тоо, ихэвчлэн салангид косинусын хувиргалт (DCT) задралыг дараах хамаарлаар тайлбарладаг.

мөнгөний бодлогын коэффициентийг томъёогоор тодорхойлно

DFT-ийн нэгэн адил (2.9)-ын дагуу C(k) коэффициентийг олохыг шууд DCT, (2.8) хэлбэрээр дохиог илэрхийлэхийг урвуу DCT гэж нэрлэдэг.

Үүний нэгэн адил бид шууд ба хоёрын харьцааг бичиж болно урвуу DFTболон PrEP хоёр хэмжээст хэрэг. Хоёр хэмжээст дискрет дохио, жишээлбэл, дижитал телевизийн дохионы нэг хүрээ нь x(t,n) утгын матрицаар илэрхийлэгддэг бөгөөд энд t = 0 ... M-1 - түүврийн тоо. мөр, n = 0 .., N-1 - хүрээ дэх мөрийн дугаар.

Шууд хоёр хэмжээст DFT нь дараах хэлбэртэй байна.

k=0…M-1, l=0…N-1,

Энд X(k,l) нь зургийн орон зайн давтамжийн спектрийг тусгасан нарийн төвөгтэй DFT коэффициентүүд юм.

Урвуу 2D DFT нь дүрсийг үндсэн функц болгон задлахыг илэрхийлнэ.

Хоёр хэмжээст шууд мөнгөний бодлогын коэффициентийг дараахь томъёогоор тодорхойлно.

Урвуу хоёр хэмжээст DCT нь дараах хэлбэртэй байна.

Хэмжигдэхүүнүүд нь хэвтээ ба босоо координатын дагуух салангид орон зайн давтамжууд бөгөөд тэдгээр нь нэг хэмжээст тохиолдолд салангид давтамжтай ижил утгатай хэмжээсгүй хэмжигдэхүүнээр илэрхийлэгддэг. Салангид орон зайн давтамж бүр нь тухайн координат дээрх түүвэрлэлтийн орон зайн үеийг энэ давтамжийн бүрэлдэхүүн хэсгийн орон зайн хугацаатай харьцуулсан харьцаатай пропорциональ байна. Орон зайн хугацааг зайны нэгжээр хэмждэг.

Зураг дээр. 2.3-д M = 8, N = 8-ийн хоёр хэмжээст DCT-ийн үндсэн функцуудыг хагас өнгөт зураг хэлбэрээр харуулав эерэг утгууд, харанхуй нь сөрөг байна.

Цагаан будаа. 2.3.

Үзүүлсэн жишээ:

• a) k = 1, l = 0; b) k = 0, l = 1; в) k = 1, l = 1;
• d) k = 0, l = 2; e) k = 1, l = 2; e) k = 2, l = 2;
• g) k = 4, l = 2; h) k = 7, l = 1; i) k = 7, l = 7.

DCT үндсэн дээр видео дохиог задлах гайхалтай шинж чанар нь үндсэн функц бүр нь бүхэл бүтэн зургийн талаархи мэдээллийг нэг дор агуулдаг. Видео дохиог задлахад ашигладаг үндсэн функцүүдийн тоо нь дүрс дүрслэлийн нарийвчлалыг тодорхойлдог.

-ийн дагуу, ерөнхийд нь N 2-той пропорциональ форвард ба урвуу DFT-ийг гүйцэтгэх үед тооцооллын нөөцийн зардлыг тооцоолох боломжтой. Үүний нэгэн адил, хоёр хэмжээст урагш ба урвуу DFT-ийг тооцоолоход N 2 M 2-тэй пропорциональ хэд хэдэн үйлдлийг хийх шаардлагатай байгааг харуулж болно.

Жишээлбэл, 8х8 элемент (пиксел) агуулсан дөрвөлжин зургийн блокийн DFT-ийг тооцоолоход ойролцоогоор 16 10 3 үржүүлэх, нэмэх үйлдэл шаардлагатай болно. 720x576 пиксел агуулсан ердийн задралын стандартын хар цагаан телевизийн хүрээний DFT-ийг тооцоолоход ойролцоогоор 8·10 11 үйлдэл шаардлагатай болно. Тооцоолол нь секундэд бодит тоон дээр 10 6 үйлдэл хийдэг компьютер дээр хийгдсэн бол DFT-ийн тооцооллын хугацаа 8 10 5 секунд буюу 200 гаруй цаг байх нь ойлгомжтой, телевизийн дүрсний DFT-ийг бодит цаг хугацаанд, өөрөөр хэлбэл. хүрээ сканнердах хугацаанд шаардлагатай үйлдлүүдийн тоог багасгах арга замыг хайх шаардлагатай.

Тооцооллын хэмжээг багасгах хамгийн радикал арга бол 60-аад онд нээсэн хурдан Фурье хувиргалт (FFT) гэж нэрлэгддэг хурдан DFT алгоритмуудыг ашиглах явдал юм. Хурдан DFT тооцоолох алгоритмыг олон зүйлд дэлгэрэнгүй тайлбарласан болно уран зохиолын эх сурвалжуудмөн энд авч үзэхгүй.

Хоёр хэмжээст FFT-ийг нэг хэмжээстүүдийн дарааллаар задалж болно. Шаардлагатай үйлдлүүдийн тоо пропорциональ болж хувирна. Дээрх жишээн дээр 720x576 пикселээс бүрдэх телевизийн хүрээний хувьд энэ утга нь ойролцоогоор 8 10 6 болж хувирсан бөгөөд энэ нь шаардлагатай үйлдлүүдийн тооноос 10 5 дахин бага байна. шууд тооцоо DFT.

Мөнгөний бодлогыг тооцоолох хурдан алгоритмууд бас байдаг. Дараа нь дижитал телевизээр үзэх болно гол үүрэгнайман элемент агуулсан дижитал дохионы сегментийн нэг хэмжээст DCT-ийг хурдан тооцоолох алгоритмыг ашигладаг 8х8 пикселийн блокуудын DCT-г тоглодог. Энэ тохиолдолд DCT-ийг эхлээд зургийн элементийн блокийн багана тус бүрээр тооцож, дараа нь 8х8 хэмжээтэй тооны матрицын мөр бүрт DCT-ийг тооцоолно.

Орчин үеийн тоног төхөөрөмжид, үүнд зориулагдсан дижитал телевиз, DFT болон DCT нь ихэвчлэн дижитал дохионы процессорууд (DSPs) эсвэл зэрэгцээ тооцоолох төхөөрөмж гэх мэт зориулалтын техник хангамжийг ашиглан бодит цаг хугацаанд гүйцэтгэдэг.

DCT нь одоогоор хамгийн өргөн хэрэглэгдэж байгаа JPEG, MPEG-1, MPEG-2 кодчиллын аргуудын үндэс суурь бөгөөд тэдгээрийн тайлбарыг 2.2-р хэсэгт өгөх болно.

DFT, Walsh-Hadamard, Haar хувиргалт дээр үндэслэн өөр хэд хэдэн ортогональ хувиргалтыг хийж болно. Тэдгээрийг Kronecker бүтээгдэхүүнийг ашиглан эсвэл Kronecker бүтээгдэхүүний нийлбэрээр тодорхойлж болно. Жишээлбэл, матриц нь хэмжээсийн дарааллаар тодорхойлогддог эрлийз Хадамард-Хаар хувиргалтыг санал болгож байна.

Уг нийтлэлд өөрчлөгдсөн Хадамард хувиргалт гэж нэрлэгддэг рекурсив тодорхойлолтыг өгсөн

мөн түүний Хаар хувиргалттай холболтыг зааж өгсөн болно.

Бид матрицын Кронекерийн хүч гэж тодорхойлсон хэмжээсийн дарааллын ерөнхий Уолш хувиргалт (Виленкин-Крестенсоны функцээр хувиргах) гэж нэрлэгддэг матрицыг авч үзье.

Энэхүү бүтээл нь Уолш-Хадамард хувиргалт дээр үндэслэн (3.114) илэрхийлэл дэх нийлбэр бүрийг өөрийн гэсэн үгээр солих замаар бүтээгдсэн хувиргалт гэж нэрлэгддэг өөрчлөлтийг тайлбарласан болно. үнэмлэхүй үнэ цэнэ. Энэ өөрчлөлт нь эргэлт буцалтгүй юм.

Зургийн кодчилолд санал болгож буй налуу хувиргалт, налуу-Хаар хувиргалт, дискрет суурь хувиргалтыг дурдах нь зүйтэй.

Одоогийн байдлаар зураг боловсруулахад ашиглагдаж буй ихэнх нэгдмэл хувиргалтыг Kronecker бүтээгдэхүүний нийлбэр хэлбэрээр илэрхийлж болохыг харуулж байна. анхан шатны матрицуудорлуулах матрицууд болон бусад. Хаар, Хадамард, Уолш, Уолш-Палей матрицууд, өөрчлөгдсөн Хадамард матриц, Хадамард-Хаар матриц, DFT матриц, ерөнхий Уолш матрицын энэхүү дүрслэлийг Хүснэгтэнд үзүүлэв. 3.5 Дараах тэмдэглэгээг ашиглан:

Хэмжээ солих матрицыг вектороор үржүүлэхэд түүний элементүүдийг тэдгээрийн тооны хоёртын урвуу кодын дагуу дахин зохион байгуулдаг; - векторын элементүүдийн тоонуудын урвуу Саарал кодын дагуу солих ажлыг гүйцэтгэдэг хэмжээсийн солих матриц; - матрицын Кронекерийн бүтээгдэхүүн; Матрицын Кронекерийн хүч.

(скан харах)

Хүснэгтийн үргэлжлэл. 3.5 (скан харах)

Энэхүү дүрслэл нь хувиргалтыг харьцуулах тохиромжтой үндэслэл болдог. Иймд матрицын төлөөллийг харьцуулахдаа “мэдэгдэл тус бүрийн матрицуудын урвуу дарааллаар ялгаатай байдгийг анзаарах нь амархан байдаг

Мөн дээр гэх мэт Эдгээр бүх матрицуудын хувьд хувиргалтыг гүйцэтгэхдээ тэдгээрийг вектороор үржүүлэх хурдан алгоритмууд байдаг. Энэ баримт нь матрицыг Кронекерийн матрицын нийлбэр хэлбэрээр илэрхийлэх боломжтой шууд холбоотой юм (4-р бүлгийг үз).

Тайлбарласан нэг хэмжээст хувиргалт дээр үндэслэн харгалзах хоёр хэмжээст салангид хувиргалтыг давхар нэг хэмжээст болгон байгуулж болно.

Энд M нь дээр дурдсан хувиргах матрицуудын нэг; a - хоёр хэмжээст дискрет дохио; a нь түүний хувирал юм.

Одоогоор дижитал дүрс боловсруулахад ашиглагдаж буй бүх нэгдмэл зургийн хувиргалтыг салгах боломжтой, өөрөөр хэлбэл тэдгээрийг хоёр хэмжээст дохионы багана, эгнээний дагуу тусад нь гүйцэтгэдэг гэдгийг анхаарна уу. Энэ нь тэдгээрийг дуусгахад шаардлагатай үйлдлүүдийн тоог бууруулдаг. Мөр, баганын дагуух өөр өөр матрицыг сонгох замаар салгаж болох хувиргалтыг хийж болно.

Энэ нь ингэж л болж байна холимог хувиргалт, тусгай дижитал дүрс кодлох төхөөрөмжид ашигладаг (жишээлбэл, үзнэ үү).

Дүрс боловсруулахад нэгдмэл хувиргалтын хэрэглээг гурван бүлэгт хувааж болно.

Зургийн кодчилол;

Зургийг бэлтгэх, танихад зориулсан шинж чанарыг задлах;

Ерөнхий шүүлтүүр.

Зургийн кодчилол нь одоогийн байдлаар хувиргах гол хэрэглээ юм (DFT-ээс бусад). Түүнээс гадна зарим өөрчлөлтүүд (жишээлбэл, налуу хувиргалт ба салангид хувиргалт шугаман суурьгэх мэт) кодчилолд ашиглах зорилгоор тусгайлан нэвтрүүлсэн.

Өөрчлөлтийн үр дүнд олж авсан дохионы дүрслэлийн коэффициентийг түүний тэмдэг гэж үзэж, зураг бэлтгэх (II, 7-р бүлгийг үзнэ үү) болон танихад ашиглаж болно. Таних явцад онцлог шинж чанарыг тодруулах зорилгоор тусгайлан зохион бүтээсэн хувиргалтын жишээ бол -хувиргах юм. Кодлох, танихын тулд хувиргах програмууд хоорондоо холбоотой. Дүрмээр бол өгдөг өөрчлөлтүүд хамгийн сайн үр дүнкодлох үед энэ нь бас онцлог задлахад илүү дээр юм.

Дохио шүүлтүүрийн нэгдмэл хувиргалтыг ашиглах нь шүүлтүүрийн тухай ойлголтыг нэгтгэн дүгнэхэд суурилдаг давтамжийн домэйндискрет Фурье хувиргалт. DFT ашиглан дохиог шүүх үед дараах дохионы хувиргалтыг гүйцэтгэдэг.

Шилжилтийн матрицууд T хувиралаас DFT болон эсрэгээр.

Энэ аргыг оновчтой шугаман (Wiener) шүүлтүүрийг нэгтгэх зорилгоор санал болгосон (мөн үзнэ үү).

Өөрчлөлтийн T хэлбэр ба шаардлагатай шүүлтүүрийн шинж чанараас хамааран шүүх ажиллагааг гүйцэтгэх нарийн төвөгтэй байдал (3.139) өөр өөр байж болно. Ялангуяа DFT-ийн оронд илүү ихийг ашиглах нь илүү ашигтай болох нь харагдаж магадгүй юм хурдан хувиргахУолш-Хадамард энэ тохиолдолд диагональ бус шүүлтүүр матрицаар үржүүлэх нь илүү төвөгтэй байсан ч (мөн § 6.5-ыг үзнэ үү).

Зургийг шахахад ашигладаг хувиргалтууд нь хурдан бөгөөд боломжтой бол компьютер дээр хялбархан хэрэгжих ёстой. Энэ нь юуны түрүүнд ийм өөрчлөлтүүд байх ёстой гэж үздэг шугаман.Энэ нь хөрвүүлсэн утгууд юм ХАМТ(Энэ нь анхны хэмжигдэхүүнүүдийн (пиксел) шугаман хослолууд (зарим хүчин зүйл эсвэл жинтэй нийлбэр) юм. DJ,ба харгалзах үржүүлэгч буюу жин нь тодорхой тоо юм Wij(хувиргах хүчин зүйл). гэсэн үг, ХАМТ(-]G\- djWij,хаана r, j= 1,2,..., х.Жишээлбэл, хэзээ n= 4 энэ хувиргалтыг дараах байдлаар бичиж болно матриц хэлбэрЭнэ нь ерөнхий тохиолдолд дараах хэлбэртэй байна: C = W D. W матрицын багана вектор бүрийг “суурь вектор” гэнэ.

Чухал ажил бол хөрвүүлэх коэффициентийг тодорхойлох явдал юм wij.Гол шаардлага бол хувиргасны дараа үнэ цэнэ юм Хамт\их байх ба бусад бүх C2, сз,... хэмжигдэхүүнүүд бага байх болно. Үндсэн харьцаа С( = Ylj djWijгэж таамаглаж байна ХАМТ(жин бол том байх болно Wijхаргалзах утгыг нэмэгдүүлэх болно dj.Энэ нь жишээлбэл, векторуудын бүрэлдэхүүн хэсгүүдэд тохиолдох болно wijТэгээд djижил утгатай, ижил шинж тэмдэгтэй байна. Үүний эсрэгээр, ХАМТ(жин нь жижиг бөгөөд тэдгээрийн тал нь харгалзах тооны тэмдгийн эсрэг тэмдэгтэй байвал жижиг байх болно dj.Тиймээс хэрэв том c * бол векторууд W(жнь анхны вектор dj-тэй төстэй бөгөөд жижиг ХАМТ(бүрэлдэхүүн хэсгүүд гэсэн үг wij-аас их ялгаатай dj.Тиймээс суурь векторууд wijанхны векторын зарим онцлог шинж чанарыг гаргаж авах хэрэгсэл гэж тайлбарлаж болно.

Практикт жин Wijэх сурвалжаас хамаарах ёсгүй. Үгүй бол тэдгээрийг декодер ашиглахын тулд шахсан файлд нэмэх шаардлагатай болно. Энэ бодол, түүнчлэн оролтын өгөгдөл нь пиксел, өөрөөр хэлбэл сөрөг бус хэмжигдэхүүнүүд нь суурь векторуудыг сонгох арга замыг тодорхойлдог. Эхний вектор, үүсгэгч нь хамт\,ойролцоо, магадгүй таарч байгаа тооноос бүрдэх ёстой. Энэ нь сөрөг бус пикселийн утгыг нэмэгдүүлэх болно. Бусад бүх суурь векторууд нь хагасаас бүрдэх ёстой эерэг тоонууд, нөгөө хагас нь - сөрөг талуудаас. -ээр үржүүлсний дараа эерэг утгуудмөн тэдгээрийн нэмэгдэл, үр дүн нь бага тоо байх болно. (Эх өгөгдөл ойрхон байх үед энэ нь ялангуяа үнэн бөгөөд хөрш зэргэлдээх пикселүүд ойролцоо утгатай байдгийг бид мэднэ.) Суурь векторууд нь эх өгөгдлөөс онцлогуудыг гаргаж авах хэрэгсэл болдог гэдгийг санаарай. Тиймээс сайн сонголт нь бие биенээсээ эрс ялгаатай, тиймээс гаргаж авах боломжтой суурь векторууд байх болно өөр өөр онцлог. Энэ нь суурь векторууд байх ёстой гэсэн санааг төрүүлдэг харилцан ортогональ.Хэрэв хувиргах матриц W нь бүрдэх бол ортогональ векторууд, дараа нь хувиргалтыг дуудна ортогональ.Суурь векторуудыг зөв сонгох боломжийг олгодог өөр нэг ажиглалт бол хувиргасан хэмжигдэхүүнийг тооцоолохдоо шахсан өгөгдлийн өндөр давтамжийн шинж чанарыг гаргаж авахын тулд эдгээр векторууд тэмдэгтийн өөрчлөлтийн давтамж улам их байх ёстой.

Эхний суурь вектор (дээд эгнээ W) нь бүгд нэг байх тул давтамж нь тэг байна. Бусад бүх векторууд нь хоёр +1, хоёр -1-тэй тул тэдгээр нь хөрвүүлсэн жижиг утгыг үүсгэх бөгөөд тэдгээрийн давтамж (мөр дэх тэмдгийн өөрчлөлтийн тоогоор хэмжигддэг) нэмэгддэг. Энэ матриц нь Хадамард-Уолш хувиргах матрицтай төстэй (тэгшитгэл (3.11)-ийг үзнэ үү). Жишээлбэл, анхны векторыг (4,6,5,2) хувиргая.

Тооноос хойш үр дүн нь нэлээд урам зоригтой юм Хамт\том болсон (анхны өгөгдөлтэй харьцуулахад), нөгөө хоёр тоо нь жижиг болсон. Анхны болон хувиргасан өгөгдлийн энергийг тооцоолъё. Анхны энерги нь 4 2 + b 2 + 5 2 + 2 2 = 81, хувирсны дараа энерги нь 17 2 + 3 2 + (-5) 2 + I 2 - 324 болсон нь дөрөв дахин их байна. W хувиргах матрицыг 1/2 дахин үржүүлснээр эрчим хүчийг хэмнэж болно. Шинэ бүтээгдэхүүн W-(4,6,5,2) t нь (17/2,3/2, -5/2,1/2) тэнцүү байх болно. Тиймээс эхний бүрэлдэхүүн хэсэгт энерги хадгалагдаж, төвлөрч, одоо анхны өгөгдлийн нийт энергийн 8.5 2 /81 = 89% -ийг эзэлж байгаа бөгөөд эхний бүрэлдэхүүн хэсэг нь ердөө 20% -ийг эзэлж байна.

W матрицын бас нэг давуу тал нь урвуу хувиргалтыг хийдэг. Анхны өгөгдөл (4,6,5,2) W-(17/2,3/2, -5/2,1/2) t бүтээгдэхүүнийг ашиглан сэргээгдсэн.

Одоо бид энэхүү өөрчлөлтийн ач тусыг үнэлэх боломжтой болсон. Хувиргасан векторыг (8.5,1.5,-2.5,0.5) бүхэл тоо болгон бөөрөнхийлж квантчилж (9,1,-3,0) авна. Бид урвуу хувиргалтыг хийж векторыг (3.5,6.5,5.5,2.5) авна. Үүнтэй төстэй туршилтаар бид хоёрыг зүгээр л устгана хамгийн бага тоонуудба бид (8. 5,0, -2.5,0) авна, дараа нь энэ ойролцоогоор квантлагдсан векторын урвуу хувиргалтыг хийнэ. Үүний үр дүнд дахин сэргээсэн өгөгдөл (3,5.5,5.5,3) гарч ирдэг бөгөөд энэ нь мөн анхныхтай нэлээд ойролцоо байна. Тиймээс бидний дүгнэлт: энэхүү энгийн бөгөөд ойлгомжтой хувиргалт нь анхны өгөгдлөөс илүүдлийг "шахах" сайн хэрэгсэл юм. Илүү боловсронгуй өөрчлөлтүүд нь өгөгдлийг сэргээх боломжийг олгодог үр дүнг өгдөг өндөр зэрэгтэймаш бүдүүлэг квантчилалтай ч ижил төстэй байдал.