Спосіб безвтратного стискання зображень

Спосіб безвтратного стискання зображень, згідно з яким формують з вхідного оцифрованого зображення, представленого матрицею [b(i,j)J, i=1,2,...,N; Н,2,...,М. де N.M - відповідно, кількість елементів у рядку та кількість рядків, довідкове субзображення Jr(i,j)], елементи якого формують з елементів, які знаходяться за парними адресами кожного парного рядка, горизонтальне субзображення [h(i,j)], елементи якого формують з елементів, які знаходяться за непарними адресами кожного парного рядка, вертикальне субзображення ИМ)]> елементи якого формують з елементів, які знаходяться за парними адресами кожного непарного рядка, діагональне субзображення {d(i,jj], елементи якого формують з елементів, які знаходяться за непарними адресами кожного непар ного рядка, після чого формують декорельоване зображення [bd(n,m)], n=1,2,...,N; m=1,2,...,M, перші N/2xM/2 елементів якого, визначають як різниці між сусідніми елементами довідкового субзображення r(i,j)-r(i-1,j), а всі наступні послідовно - як різниці між значеннями елементів горизонтального субзображення І передбаченими значеннями hp(i,j)= =(r(i-1,j)+7r(i,j)+7r(i+1,j)+r(i+2,j))/16 - як різниці між значеннями елементів вертикального субзображення і передбаченими значеннями vp(i,j)= =(r(i,j-1)+7r(i,j)+7r(i,j+1)+r(i,j+2))/16 і як різниці між значеннями елементів діагонального субзображення і «передбаченими значеннями dp(U)= =(h(i,j)+h(i+i,i)+v(i,j)+v(i,j+i))/4, елементи отриманого декорельованого зображення кодують нерівномірним кодом, при цьому кількість біт на один елемент визначають за частотою появи значень елементів в декорельованому зображенні, який відрізняється тим, що за двовимірною кореляційною функцією довідкового субзображення визначають інтервали кореляції по вертикалі Ху і по горизонталі Th і при tv >h для формування декорельованого зображення використовують довідкове субзображення, в якому здійснюють заміну рядків стовбцями, а стовбців - рядками, а в декорельоване зображення записують один біт Інформації, яким вказують на проведення даної заміни. О in со Винахід відноситься до галузі електрозв'язку, зокрема при розробці пристроїв кодування для зменшення надлишковості інформації, яка підлягає передачі. Відомий спосіб безвтратного стискання зображень, згідно якого формують з вхідного оцифрованого зображення, представленого матрицею ЇЬ(і,І)1, i=1,2,...,N; j=1,2 М. де N,M - відповідно, кількість елементів у рядку та кількість рядків, довідкове субзображення lr(rj)], елементи якого формують з елементів, які знаходяться за парними адресами кожного парного рядка, горизонтальне субзображення [h(i,j)], елементи якого формують з елементів, які знаходяться за непарними адресами кожного парного рядка, вертикальне субзоб елементів, які знаходяться за парними адресами кожного непарного рядка, діагональне субзображення [d(i,j)j, елементи якого формують з елементів, які знаходяться за непарними адресами кожного непарного рядка, після чого формують декорельоване зображення [ba(n,m)]p n=1,2,...,N; m=1,2,...,M, перші N/2xM/2 елементів якого визначають, як різниці між сусідніми елементами довідкового субзображення r(i,j)-r(i-1,j), а всі наступні, послідовно, як різниці між значеннями елементів 'горизонтального субзображення' і передбаченими значеннями hp(i,j)={r{M,j)+7r(t,j)+7r(i+1,j)+r(i+2,j)) /16. як різниці між значеннями елементів вертикального субзображення і передбаченими значеннями vp(i,j)= -(r(i,j-1)+7r(ij)+7r(i,j+1)+r(i,j+2))/16 і як зг елементів в декорельованому зображенні (K.S.Kang, h.W.Park. Lossless medical image compression by multilevel decomposition. Jomal ol Digital Imaging, Vol 9, № 1 (February), 1996: pp 1120). с . У відомому способі величина стискання зображення в значній мірі залежить від величин різниць елементів довідкового субзображення, порядок знаходження (напрям сканування) яких є однозначним і базується на припущенні про рівномірність величин розривів яскравості як по горизонталі, так і по вертикалі. Як наслідок, у випадку, коли більшість розривів яскравості розташовані перпендикулярно до напрямку сканування, це приводить до збільшення величин різниць, і. відповідно, кількості біт, необхідних для кодування, а отже * розмірів стиснутого зображення. В основу винаходу поставлена задача створення такого способу безвтратного стискання зображень, в якому за рахунок врахування нерівномірності розташування розривів яскравості по вертикалі чи горизонталі, зменшуються величини різниць між елементами довідкового субзображення і за рахунок цього зменшуються розміри стиснутого зображення. Поставлене завдання вирішується тим, що у способі безвтратного стискання зображень, згідно якого формують з вхідного оцифрованого зображення представленого матрицею [b(i,j)], i=1,2,...,N; j=1,2 М, де N.M -відповідно, кількість елементів у рядку та кількість рядків, довідкове субзображення [г(і,і)], елементи якого формують з елементів, які знаходяться за парними адресами кожного парного рядка, горизонтальне субзображення fh(ij)], елементи якого формують з елементів, які знаходяться за непарними адресами кожного парного рядка, вертикальне субзображення Щі,і)}. елементи якого формують з елементів, які знаходяться за парними адресами кожного непарного рядка, діагональне субзображення [d(i,j)J, елементи якого формують з елементів, які знаходяться за непарними адресами кожного непарного рядка, лісля чого формують декорельоване зображення [bd(n,m)], п=1,2 N; т=1,2 М, перші N/2xM/2 елементів якого, визначають, як різниці між сусідніми елементами довідкового субзображення r(i,j)-r(i1,j), а всі наступні послідовно як різниці між значеннями елементів горизонтального субзображення і передбаченими значеннями hp(i,j)= =(r(M,])+7r(i,j)+7r(i+1,j)+r(i+2,j))/16, як різниці між значеннями елементів вертикального субзображення і передбаченими значеннями vp(i,j)= (r(i,j1)+7r(i,j)+7r(i,j+1)+r(i,j+2))/16 і як різниці між значеннями елементів діагонального субзображення і передбаченими знаменнями dp(i,|)=(h(i,j)+h(i+1,j)+ +v(i,j)+v(i,j+1))/4, елементи отриманого декорельованого зображення кодують нерівномірним кодом, при цьому кількість біт на один елемент визначають за частотою появи ЯНЯЧРНЬ РПРМРНТІЙ R ПР один біт інформації, яким вказують на проведення даної заміни За рахунок порівняння Інтервалів кореляції по вертикалі та горизонталі, які знаходяться за двовимірною кореляційною функцією довідкового субзображення, знаходження різниць між сусідніми елементами довідкового субзображення є неоднозначним, що дозволяє враховувати нерівномірністі розташування розривів яскравості по вертикалі чи горизонталі, в наслідок чого, сумарна величина різниць зменшується, а величина стискання декорельованого зображення зростає. Спосіб реалізується наступним чином. З елементів заданого вхідного оцифрованого зображення представленого матрицею [b(i,j)], Ы,2 N;j= =1,2,....М, де N.M-вщповідно, кількість елементів у рядку та кількість рядків, формують чотири субзображення, а саме1 довідкове [rfi.j)], горизонтальне [h(i,j)J, вертикальне [v(i,j)J і діагональне субзображення [d(i,j)]. Елементи довідкового субзображення формують з елементів, які знаходяться за парними адресами кожного парного рядка, горизонтального - з елементів, які знаходяться за непарними адресами кожного парного рядка, вертикального - з елементів, які знаходяться за парними адресами кожного непарного рядка і діагонального з елементів, які знаходяться за непарними адресами кожного непарного рядка. За двовимірною кореляційною функцією довідкового субзображення визначають інтервали кореляції по вертикалі т* і по горизонталі ти і здійснюють їх порівняння Якщо виконується умова т«>ть , то в довідковому субзображенні здійснюють заміну рядків стовбцями, а стовбців рядками Формують декорельоване зображення [bd(n,m)], n=1,2,...,N; m=1,2,...,M. перші N/2xM/2 елементів якого, визначають, як різниці між сусідніми елементами довідкового субзображення г(і,))-г(і-І,{), а всі наступні, послідовно, як різниці між значеннями елементів горизонтального субзображення і передбаченими значеннями hp(i,j); різниці між значеннями елементів вертикального субзображення і передбаченими значеннями vp(ij), різниці між значеннями елементів діагонального субзображення і передбаченими значеннями dp(i.j) Передбачені значення визначають як: hp(i,j)=(r(i-1 j)+7r(i.j)+7r(i-i-1 .j)+r(i+2tj))/16. vp(i,j)= Елементи отриманого декорельованого зображення кодують нерівномірним кодом, при цьому кількість біт на один елемент визначають за частотою появи значень елементів в декорельованому зображенні. Прикладом такого кодування є алгоритм Хаффмена Додатково в декорельоване зображення записують один біт Інформації, яким вказують на проведення заміни в довідковому субзображенні і який використовується при відновленні стиснутого зображення. Відкрите акції УКРАЇНА UA ii) 35499 ( (із) А (51) 7 Н03М7/36, G06T9/00 МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ ДЕРЖАВНИЙ ДЕПАРТАМЕНТ ІНТЕЛЕКТУАЛЬНОЇ ВЛАСНОСТІ ОПИС ДО ДЕКЛАРАЦІЙНОГО ПАТЕНТУ НА ВИНАХІД видається лід відповідальність власника патенту (54) СПОСІБ БЕЗВТРАТНОГО СТИСКАННЯ ЗОБРАЖЕНЬ (21)99105755 (22)21.10.1999 (24) 15.03.2001 (46) 15.03.2001, Бюл. № 2, 2001 р. (72) Русин Богдан Павлович, Мосоров Володимир Якович (73) ДЕРЖАВНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА", ФІЗИКО-МЕХАНІЧНИЙ ІНСТИТУТ ЇМ. Г.В. КАРПЕНКА НАН УКРАЇНИ, РУСИН БОГДАН ПАВЛОВИЧ, МОСОРОВ ВОЛОДИМИР ЯКОВИЧ (57) Спосіб безвтратного стискання зображень, згідно з яким формують з вхідного оцифрованого зображення, представленого матрицею [b(i,j)]( i=1,2,...,N; j=l,2,...,M, де N,M - відповідно, кількість елементів у рядку та кількість рядків, довідкове субзобреження ЩЩ, елементи якого формують з елементів, які знаходяться за парними адресами кожного парного рядка, горизонтальне субзображення [h(i,j)], елементи якого формують з елементів, які знаходяться за непарними адресами кожного парного рядка, вертикальне субзображення [v(i.j)]> елементи якого формують з елементів, які знаходяться за парними адресами кожного непарного рядка, діагональне субзображення [d(i,j)], елементи якого формують з елементів, які знаходяться за непарними адресами кожного непар ного рядка, після чого формують декорельоване зображення Ibd(n.m)], n=1,2 N; m=*1,2,...,M, перші N/2xM/2 елементів якого, визначають як різниці між сусідніми елементами довідкового субзображення r(i,j)-r(i-1,j), а всі наступні послідовно - як різниці між значеннями елементів горизонтального субзображення і передбаченими значеннями hp(i,j)= =(r(i-1,j)+7r(i,j)+7r(i+1,j)+r(i+2,j))/16 - як різниці між значеннями елементів вертикального субзображення і передбаченими значеннями v p (i,j)= =(r(i,j-1)+7r(i,j)+7r(i,j+1)+r(i,j+2))/16 і як різниці між значеннями елементів діагонального субзображення і «передбаченими значеннями d p (i,j)= =(h(i,j)+h(i+1 ,j)+v(i,j)+v(i,j+1))/4, елементи отриманого декорельованого зображення кодують нерівномірним кодом, при цьому кількість біт на один елемент визначають за частотою появи значень елементів в декорельованому зображенні, який відрізняється тим, що за двовимірною кореляційною функцією довідкового субзображення визначають інтервали кореляції по вертикалі t v і по горизонталі Th і при t v >h для формування декорельованого зображення використовують довідкове субзображення, в якому здійснюють заміну рядків стовбцями, а стовбців • рядками, а в декорельоване зображення записують один біт інформації, яким вказують на проведення даної заміни. со ю Винахід відноситься до галузі електрозв'язку, зокрема при розробці пристроїв кодування для зменшення надлишковості інформації, яка підлягає передачі. Відомий спосіб безвтратного стискання зображень, згідно якого формують з вхідного оцифрованого зображення, представленого матрицею [b(i,j)j, i=1,2,...,N; j=1,2,...,M. де N,M - відповідно, кількість елементів у рядку та кількість рядків, довідкове субзображення [r(i,j)J, елементи якого формують з елементів, які знаходяться за парними адресами кожного парного рядка, горизонтальне субзображення [h(i,j)], елементи якого формують з елементів, які знаходяться за непарними адресами кожного парного рядка, вертикальне субзображення [v(i,j)J, елементи якого формують з елементів, які знаходяться за парними адресами кожного непарного рядка, діагональне субзображення [d(i,j)j, елементи якого формують з елементів, які знаходяться за непарними адресами кожного непарного рядка, після чого формують декорельоване зображення [bd(n,m)], n=1,2,...,N; m=1,2,...,M, перші N/2xM/2 елементів якого визначають, як різниці між сусідніми елементами довідкового субзображення r(i,j)-r(i-1,j), а всі наступні, послідовно, як різниці між значеннями елементів 'горизонтального субзображення' і передбаченими значеннями hp(i,j)=(r(i-1 ,j)+7r(i,j)+7r(i+1 ,j)+r(i+2,j)) /16, як різниці між значеннями елементів вертикального субзображення і передбаченими значеннями vp(ifj)= =(r(i,j-1)+7r(i,j)+7r(i,j+1)+r(i,j+2))/16 і як різниці між значеннями елементів діагонального ти для формування декорельованого зображення використовують довідкове субзображення, в якому здійснюють заміну рядків стовбцями, а стовбців рядками, а в декорельоване зображення записують один біт інформації, яким вказують на проведення даної заміни. За рахунок порівняння інтервалів кореляції по вертикалі та горизонталі, які знаходяться за двовимірною кореляційною функцією довідкового субзображення, знаходження різниць між сусідніми елементами довідкового субзображення є неоднозначним, що дозволяє враховувати нерівномірністі розташування розривів яскравості по вертикалі чи горизонталі, в наслідок чого, сумарна величина різниць зменшується, а величина стискання .декорельованого зображення зростає. Спосіб реалізується наступним чином. З елементів заданого вхідного оцифрованого зображення представленого матрицею \b(\,\)], i=1,2,...,N;j= =1,2 М, де N.M-відповідно, кількість елементів у рядку та кількість рядків, формують чотири субзображення, а саме: довідкове (r(i,j)], горизонтальне (h(i,j)], вертикальне [v(i,j)J і діагональне субзображення [d(i,j)]. Елементи довідкового субзображення формують з елементів, які знаходяться за парними адресами кожного парного рядка, горизонтального • з елементів, які знаходяться за непарними адресами кожного парного рядка, вертикального - з елементів, які знаходяться за парними адресами кожного непарного рядка і діагонального з елементів, які знаходяться за непарними адресами кожного непарного рядка. За двовимірною кореляційною функцією довідкового субзображення визначають інтервали кореляції по вертикалі тУ і по горизонталі t h і здійснюють їх порівняння. Якщо виконується умова x v >th, то в довідковому субзображенні здійснюють заміну рядків стовбцями, а стовбців рядками. Формують декорельоване зображення [bd(n,m)], n=1,2,...,N; m=1,2,...,M, перші N/2xM/2 елементів якого, визначають, як різниці між сусідніми елементами довідкового субзображення r(i,j)-r(i-l,j), а всі наступні, послідовно, як різниці між значеннями елементів горизонтального субзображення і передбаченими значеннями hp(i,j); різниці між значеннями елементів вертикального субзображення і передбаченими значеннями vp(i,j), різниці між значеннями елементів діагонального субзображення і передбаченими значеннями d p (ij). Передбачені значення визначають як: hp(ilj)=(r(i-1,j)+7r(i,j)+7r(i+1,j)+r(i+2,j))/16, vp(i,j)= Елементи отриманого декорельованого зображення кодують нерівномірним кодом, при цьому кількість біт на один елемент визначають за частотою появи значень елементів в декорельованому зображенні. Прикладом такого кодування є алгоритм Хаффмена Додатково в декорельоване зображення записують один біт інформації, яким вказують на проведення заміни в довідковому субзображенні і який використовується при відновленні стиснутого зображення. Пропонований спосіб застосовувався до напівтонових зображень земної поверхні, отриманих за допомогою штучних супутників Землі. Особливо запропонований спосіб ефективний у випадку, ко 35499 ли зображення містять однорідні області орієнтовані вертикально. Отримана у цьому випадку ент ропія декорельованих зображень у порівнянні з відомим способом, в середньому, менша на 3-11%. Тираж 50 екз. Відкрите акціонерне товариство «Патент» Україна, 88000, м. Ужгород, вул. Гагаріна, 101 (03122) 3 - 7 2 - 8 9 (03122) 2 - 5 7 - 0 3