nedoPC.org

Electronics hobbyists community established in 2002
Atom Feed | View unanswered posts | View active topics It is currently 28 Mar 2024 02:08



Reply to topic  [ 15 posts ] 
Троичный Уолш, Обобщённый Хаар (TONIC) 
Author Message
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Название этого топика это типа пародия на название фильма Крадущийся Тигр, Затаившийся Дракон :lol:

В 3 ЧАСА НОЧИ 28 ОКТЯБРЯ 2023 ГОДА ПРИДУМАЛ АББРЕВИАТУРУ
TONIC - Ternary OrthoNormal Image Compression

Задумался я тут было в августе, а не попробовать ли сделать троичного Уолша (иногда преобразование Уолша называют преобразованием Адамара или Уолша-Адамара, про которое нам рассказывали в универе в начале 90х прошлого века - см. https://en.wikipedia.org/wiki/Hadamard_transform и https://en.wikipedia.org/wiki/Walsh_matrix):

Attachment:
Screenshot from 2023-10-23 23-25-17.png
Screenshot from 2023-10-23 23-25-17.png [ 2.62 KiB | Viewed 16910 times ]


Attachment:
Screenshot from 2023-10-23 23-25-38.png
Screenshot from 2023-10-23 23-25-38.png [ 5.87 KiB | Viewed 16910 times ]


разбавив -1 и +1 ноликами, и вот в октябре обнаружилось, что преобразование Хаара (про которое нам скорее всего тоже в универе, но я забыл) в каком-то смысле это уже делает: https://en.wikipedia.org/wiki/Haar_wavelet#Haar_matrix

Attachment:
Screenshot from 2023-10-23 23-26-51.png
Screenshot from 2023-10-23 23-26-51.png [ 4.54 KiB | Viewed 16910 times ]

Не смотря на то, что Альфред Хаар придумал эту штуку ещё в 1909 году, оно считается самым ранним применением "вейвлетов", которые я ошибочно считал "новыми веяниями" 90х ;)

Attachment:
Screenshot from 2023-10-23 23-27-10.png
Screenshot from 2023-10-23 23-27-10.png [ 13.3 KiB | Viewed 16910 times ]


И написал я программку, которая в матрице 8х8 перебирает все комбинации циферок -1, 0 и +1 (троичных сбалансированных циферок спешу заметить), оставляя в первой строке все единички и проверяя получилась ли у нас ортогональная (ортонормированная) матрица, которую можно использовать для преобразования цифрового сигнала в спектр и дальнейшего восстановления его обратно - получился очень весёлый набор разнообразных комбинаций, в числе которых "самоизобрёлся" и Уолш, и Хаар :mrgreen:

Для идентификации последовательностей ноликов, единичек и минусединичек я интерпретировал их как троичное число, печатая его в десятичном виде вслед за последовательностью:
Code:
RESULTS #1500160
RESULT: +1 +1 +1 +1 +1 +1 +1 +1 +3280
RESULT: +1 +1 +1 +1 -1 -1 -1 -1 +3200
RESULT: +1 +1 -1 -1 +1 +1 -1 -1 +2624
RESULT: +1 +1 -1 -1 -1 -1 +1 +1 +2560
RESULT: +1 -1 +1 -1 +1 -1 +1 -1 +1640
RESULT: +1 -1 +1 -1 -1 +1 -1 +1 +1600
RESULT: +1 -1 -1 +1 +1 -1 -1 +1 +1312
RESULT: +1 -1 -1 +1 -1 +1 +1 -1 +1280
RESULTS PROVEN! 0.3536 0.3536 0.3536 0.3536 0.3536 0.3536 0.3536 0.3536
NO MORE RESULTS!
Интересно, что Уолш у меня сгенерировался последним - как комбинация №1500160 :lol:

Attachment:
Screenshot from 2023-10-23 23-56-46.png
Screenshot from 2023-10-23 23-56-46.png [ 15.89 KiB | Viewed 16905 times ]

А если упорядочить по частоте (считая количество переходов через ноль), то получится так:
Code:
RESULT: +1 +1 +1 +1 +1 +1 +1 +1 +3280 (0)
RESULT: +1 +1 +1 +1 -1 -1 -1 -1 +3200 (1)
RESULT: +1 +1 -1 -1 -1 -1 +1 +1 +2560 (2)
RESULT: +1 +1 -1 -1 +1 +1 -1 -1 +2624 (3)
RESULT: +1 -1 -1 +1 +1 -1 -1 +1 +1312 (4)
RESULT: +1 -1 -1 +1 -1 +1 +1 -1 +1280 (5)
RESULT: +1 -1 +1 -1 -1 +1 -1 +1 +1600 (6)
RESULT: +1 -1 +1 -1 +1 -1 +1 -1 +1640 (7)

И во время работы над дипломом, я заметил, что переупорядочивание с натурального в частотный порядок выполняется в соответствии с кодами Грея :o

P.S. Есть вот такая русскоязычная книжка 1989 года по теме - надо бы её что ли достать где-то:

 книжки по теме
Attachment:
Zalmanzon.jpg
Zalmanzon.jpg [ 21.44 KiB | Viewed 16633 times ]


Attachment:
ZalmansonInside.jpg
ZalmansonInside.jpg [ 74.99 KiB | Viewed 16627 times ]

Хотя может быть там лишь пересказ Хармута 1970 года:

Attachment:
HarmuthInside.jpg
HarmuthInside.jpg [ 105.3 KiB | Viewed 16627 times ]

Русский перевод которого 1975 года я купил в мае 1998 за 2 рубля на распродаже старых архивов в городской библиотеке имени Белинского г.Екатеринбурга, а оригинал получил буквально на днях с eBay за $16 :roll:

Attachment:
Harmuth.jpg
Harmuth.jpg [ 93.81 KiB | Viewed 16627 times ]

_________________
:dj: https://mastodon.social/@Shaos


23 Oct 2023 23:35
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Shaos wrote:
Code:
RESULTS #1500160
RESULT: +1 +1 +1 +1 +1 +1 +1 +1 +3280
RESULT: +1 +1 +1 +1 -1 -1 -1 -1 +3200
RESULT: +1 +1 -1 -1 +1 +1 -1 -1 +2624
RESULT: +1 +1 -1 -1 -1 -1 +1 +1 +2560
RESULT: +1 -1 +1 -1 +1 -1 +1 -1 +1640
RESULT: +1 -1 +1 -1 -1 +1 -1 +1 +1600
RESULT: +1 -1 -1 +1 +1 -1 -1 +1 +1312
RESULT: +1 -1 -1 +1 -1 +1 +1 -1 +1280
RESULTS PROVEN! 0.3536 0.3536 0.3536 0.3536 0.3536 0.3536 0.3536 0.3536
NO MORE RESULTS!
Интересно, что Уолш у меня сгенерировался последним - как комбинация №1500160 :lol:

Для превращения ортогональной матрицы в ортонормированную, элементы в каждой строке надо умножить на нормирующий коэффициент:

https://congyuzhou.medium.com/66be3ab318c0

В случае матрицы Уолша это 1/sqrt(N) или в нашем случае (при N=8) это 1/sqrt(8)=0.353553390593

В более сложных случаях (когда у нас появляются нолики) надо нормировать каждую строку в отдельности в зависимости от того, сколько ненулевых значений там было - вот пруф на питоне, что одна из таких матриц (№54663):
Attachment:
Screenshot from 2023-10-25 07-39-26.png
Screenshot from 2023-10-25 07-39-26.png [ 23.4 KiB | Viewed 16763 times ]
является ортонормированной (т.е. её инверсия эквивалентна транспонированию):
Code:
import math
# Import required package
import numpy as np

np.set_printoptions(precision=4)

o8 = 1/math.sqrt(8)
o6 = 1/math.sqrt(6)
o4 = 1/math.sqrt(4)

# Taking a 8 * 8 matrix
A = np.array([
 [ o8, o8, o8, o8, o8, o8, o8, o8 ],
 [ o4,  0,-o4,  0, o4,  0,-o4,  0 ],
 [ o6,  0,-o6,-o6,-o6,  0, o6, o6 ],
 [ o8,-o8, o8,-o8, o8,-o8, o8,-o8 ],
 [ o6,-o6,  0, o6,-o6, o6,  0,-o6 ],
 [  0, o4,  0,-o4,  0, o4,  0,-o4 ],
 [  0,-o6, o6,-o6,  0, o6,-o6, o6 ],
 [-o6,-o6,-o6,  0, o6, o6, o6,  0 ]
])

print("Original matrix:\n")
print(A)
print("\n")

np.set_printoptions(precision=1)

# Calculating the inverse of the matrix
B = np.linalg.inv(A)

print("Inverted matrix:\n")
print(B)
print("\n")

C = np.linalg.inv(B)

print("Inverted again:\n")
print(C)
print("\n")

print("Difference between them (every element must be close to zero):\n")
print(A-C)
print("\n")

print("Multiplication of original matrix and its transpose (must be identity matrix):\n")
print(np.matmul(A.transpose(),A))
выхлоп:
Code:
Original matrix:

[[ 0.3536  0.3536  0.3536  0.3536  0.3536  0.3536  0.3536  0.3536]
 [ 0.5     0.     -0.5     0.      0.5     0.     -0.5     0.    ]
 [ 0.4082  0.     -0.4082 -0.4082 -0.4082  0.      0.4082  0.4082]
 [ 0.3536 -0.3536  0.3536 -0.3536  0.3536 -0.3536  0.3536 -0.3536]
 [ 0.4082 -0.4082  0.      0.4082 -0.4082  0.4082  0.     -0.4082]
 [ 0.      0.5     0.     -0.5     0.      0.5     0.     -0.5   ]
 [ 0.     -0.4082  0.4082 -0.4082  0.      0.4082 -0.4082  0.4082]
 [-0.4082 -0.4082 -0.4082  0.      0.4082  0.4082  0.4082  0.    ]]


Inverted matrix:

[[ 3.5e-01  5.0e-01  4.1e-01  3.5e-01  4.1e-01  1.1e-17  0.0e+00 -4.1e-01]
 [ 3.5e-01 -7.7e-17  0.0e+00 -3.5e-01 -4.1e-01  5.0e-01 -4.1e-01 -4.1e-01]
 [ 3.5e-01 -5.0e-01 -4.1e-01  3.5e-01 -1.2e-17 -1.2e-17  4.1e-01 -4.1e-01]
 [ 3.5e-01 -1.3e-16 -4.1e-01 -3.5e-01  4.1e-01 -5.0e-01 -4.1e-01 -1.9e-16]
 [ 3.5e-01  5.0e-01 -4.1e-01  3.5e-01 -4.1e-01 -1.0e-16  6.1e-17  4.1e-01]
 [ 3.5e-01 -8.6e-17 -1.8e-18 -3.5e-01  4.1e-01  5.0e-01  4.1e-01  4.1e-01]
 [ 3.5e-01 -5.0e-01  4.1e-01  3.5e-01 -1.2e-17 -7.9e-17 -4.1e-01  4.1e-01]
 [ 3.5e-01 -3.6e-17  4.1e-01 -3.5e-01 -4.1e-01 -5.0e-01  4.1e-01 -2.4e-17]]


Inverted again:

[[ 3.5e-01  3.5e-01  3.5e-01  3.5e-01  3.5e-01  3.5e-01  3.5e-01  3.5e-01]
 [ 5.0e-01  2.8e-17 -5.0e-01 -7.1e-17  5.0e-01  3.3e-17 -5.0e-01  8.1e-17]
 [ 4.1e-01 -2.5e-17 -4.1e-01 -4.1e-01 -4.1e-01 -3.6e-17  4.1e-01  4.1e-01]
 [ 3.5e-01 -3.5e-01  3.5e-01 -3.5e-01  3.5e-01 -3.5e-01  3.5e-01 -3.5e-01]
 [ 4.1e-01 -4.1e-01 -8.4e-17  4.1e-01 -4.1e-01  4.1e-01 -9.5e-17 -4.1e-01]
 [-2.1e-18  5.0e-01  5.0e-18 -5.0e-01  1.7e-17  5.0e-01 -2.2e-18 -5.0e-01]
 [-1.8e-17 -4.1e-01  4.1e-01 -4.1e-01 -1.3e-16  4.1e-01 -4.1e-01  4.1e-01]
 [-4.1e-01 -4.1e-01 -4.1e-01  4.5e-17  4.1e-01  4.1e-01  4.1e-01  0.0e+00]]


Difference between them (every element must be close to zero):

[[-2.2e-16  1.7e-16  2.2e-16  5.6e-17 -2.2e-16 -2.8e-16 -5.6e-17  1.7e-16]
 [ 0.0e+00 -2.8e-17  0.0e+00  7.1e-17 -1.1e-16 -3.3e-17  1.1e-16 -8.1e-17]
 [ 1.7e-16  2.5e-17  1.7e-16 -1.1e-16  1.7e-16  3.6e-17  5.6e-17  5.6e-17]
 [ 0.0e+00 -1.1e-16  5.6e-17 -5.6e-17  5.6e-17  1.7e-16  5.6e-17  0.0e+00]
 [ 5.6e-17  1.7e-16  8.4e-17 -5.6e-17 -1.1e-16 -1.1e-16  9.5e-17 -5.6e-17]
 [ 2.1e-18  0.0e+00 -5.0e-18  0.0e+00 -1.7e-17 -1.1e-16  2.2e-18  0.0e+00]
 [ 1.8e-17  1.1e-16  0.0e+00  0.0e+00  1.3e-16 -2.2e-16  2.2e-16 -2.2e-16]
 [ 5.6e-17  0.0e+00  0.0e+00 -4.5e-17  0.0e+00 -1.1e-16 -1.1e-16  0.0e+00]]


Multiplication of original matrix and its transpose (must be identity matrix):

[[ 1.0e+00 -2.3e-19 -5.6e-17 -2.3e-19 -1.7e-16  2.3e-19 -5.5e-17  2.3e-19]
 [-2.3e-19  1.0e+00 -2.3e-19 -5.6e-17  2.3e-19 -1.7e-16  2.3e-19 -8.3e-17]
 [-5.6e-17 -2.3e-19  1.0e+00  2.3e-19 -5.5e-17  2.3e-19 -1.7e-16 -2.3e-19]
 [-2.3e-19 -5.6e-17  2.3e-19  1.0e+00  2.3e-19 -8.3e-17 -2.3e-19 -1.9e-16]
 [-1.7e-16  2.3e-19 -5.5e-17  2.3e-19  1.0e+00 -2.3e-19 -5.6e-17 -2.3e-19]
 [ 2.3e-19 -1.7e-16  2.3e-19 -8.3e-17 -2.3e-19  1.0e+00 -2.3e-19 -5.6e-17]
 [-5.5e-17  2.3e-19 -1.7e-16 -2.3e-19 -5.6e-17 -2.3e-19  1.0e+00  2.3e-19]
 [ 2.3e-19 -8.3e-17 -2.3e-19 -1.9e-16 -2.3e-19 -5.6e-17  2.3e-19  1.0e+00]]

Напомню, что строчки в ортонормированной матрице можно переставлять - от этого она не перестанет быть ортонормированной.

Вот например нашлась слегка перемешанная матрица Хаара 8x8 как комбинация №1488441:

Attachment:
Screenshot from 2023-10-24 00-50-19.png
Screenshot from 2023-10-24 00-50-19.png [ 19.9 KiB | Viewed 16894 times ]

Сравниваем с матрицей из википедии - очень похоже :roll:

Image

Всего у меня получилось 1500160 уникальных ортонормированных матриц 8x8 с отсортированными по убыванию троичными числами, представляющими строки матрицы, которых в свою очередь только 1107 уникальных (единственное т.к. я сразу начал с последовательности единичек 1 1 1 1 1 1 1 1, то последовательность минус-единичек уже не может быть использована и последовательность нулей у меня в программе обозначена как запрещённая комбинация):

 уникальные строки
Code:
  42496 RESULT: N N N N P P P P -3200
   3072 RESULT: N N N O O P P P -3146
   3072 RESULT: N N N O P O P P -3128
   3072 RESULT: N N N O P P O P -3122
   3072 RESULT: N N N O P P P O -3120
  42496 RESULT: N N N P N P P P -3092
   3072 RESULT: N N N P O O P P -3074
   3072 RESULT: N N N P O P O P -3068
   3072 RESULT: N N N P O P P O -3066
  42496 RESULT: N N N P P N P P -3056
   3072 RESULT: N N N P P O O P -3050
   3072 RESULT: N N N P P O P O -3048
  42496 RESULT: N N N P P P N P -3044
   3072 RESULT: N N N P P P O O -3042
  42496 RESULT: N N N P P P P N -3040
   3072 RESULT: N N O N O P P P -2984
   3072 RESULT: N N O N P O P P -2966
   3072 RESULT: N N O N P P O P -2960
   3072 RESULT: N N O N P P P O -2958
   3072 RESULT: N N O O N P P P -2930
  12032 RESULT: N N O O O O P P -2912
  12032 RESULT: N N O O O P O P -2906
  12032 RESULT: N N O O O P P O -2904
   3072 RESULT: N N O O P N P P -2894
  12032 RESULT: N N O O P O O P -2888
  12032 RESULT: N N O O P O P O -2886
   3072 RESULT: N N O O P P N P -2882
  12032 RESULT: N N O O P P O O -2880
   3072 RESULT: N N O O P P P N -2878
   3072 RESULT: N N O P N O P P -2858
   3072 RESULT: N N O P N P O P -2852
   3072 RESULT: N N O P N P P O -2850
   3072 RESULT: N N O P O N P P -2840
  12032 RESULT: N N O P O O O P -2834
  12032 RESULT: N N O P O O P O -2832
   3072 RESULT: N N O P O P N P -2828
  12032 RESULT: N N O P O P O O -2826
   3072 RESULT: N N O P O P P N -2824
   3072 RESULT: N N O P P N O P -2816
   3072 RESULT: N N O P P N P O -2814
   3072 RESULT: N N O P P O N P -2810
  12032 RESULT: N N O P P O O O -2808
   3072 RESULT: N N O P P O P N -2806
   3072 RESULT: N N O P P P N O -2802
   3072 RESULT: N N O P P P O N -2800
  42496 RESULT: N N P N N P P P -2768
   3072 RESULT: N N P N O O P P -2750
   3072 RESULT: N N P N O P O P -2744
   3072 RESULT: N N P N O P P O -2742
  42496 RESULT: N N P N P N P P -2732
   3072 RESULT: N N P N P O O P -2726
   3072 RESULT: N N P N P O P O -2724
  42496 RESULT: N N P N P P N P -2720
   3072 RESULT: N N P N P P O O -2718
  42496 RESULT: N N P N P P P N -2716
   3072 RESULT: N N P O N O P P -2696
   3072 RESULT: N N P O N P O P -2690
   3072 RESULT: N N P O N P P O -2688
   3072 RESULT: N N P O O N P P -2678
  12032 RESULT: N N P O O O O P -2672
  12032 RESULT: N N P O O O P O -2670
   3072 RESULT: N N P O O P N P -2666
  12032 RESULT: N N P O O P O O -2664
   3072 RESULT: N N P O O P P N -2662
   3072 RESULT: N N P O P N O P -2654
   3072 RESULT: N N P O P N P O -2652
   3072 RESULT: N N P O P O N P -2648
  12032 RESULT: N N P O P O O O -2646
   3072 RESULT: N N P O P O P N -2644
   3072 RESULT: N N P O P P N O -2640
   3072 RESULT: N N P O P P O N -2638
  42496 RESULT: N N P P N N P P -2624
   3072 RESULT: N N P P N O O P -2618
   3072 RESULT: N N P P N O P O -2616
  42496 RESULT: N N P P N P N P -2612
   3072 RESULT: N N P P N P O O -2610
  42496 RESULT: N N P P N P P N -2608
   3072 RESULT: N N P P O N O P -2600
   3072 RESULT: N N P P O N P O -2598
   3072 RESULT: N N P P O O N P -2594
  12032 RESULT: N N P P O O O O -2592
   3072 RESULT: N N P P O O P N -2590
   3072 RESULT: N N P P O P N O -2586
   3072 RESULT: N N P P O P O N -2584
  42496 RESULT: N N P P P N N P -2576
   3072 RESULT: N N P P P N O O -2574
  42496 RESULT: N N P P P N P N -2572
   3072 RESULT: N N P P P O N O -2568
   3072 RESULT: N N P P P O O N -2566
  42496 RESULT: N N P P P P N N -2560
   3072 RESULT: N O N N O P P P -2498
   3072 RESULT: N O N N P O P P -2480
   3072 RESULT: N O N N P P O P -2474
   3072 RESULT: N O N N P P P O -2472
   3072 RESULT: N O N O N P P P -2444
  12032 RESULT: N O N O O O P P -2426
  12032 RESULT: N O N O O P O P -2420
  12032 RESULT: N O N O O P P O -2418
   3072 RESULT: N O N O P N P P -2408
  12032 RESULT: N O N O P O O P -2402
  12032 RESULT: N O N O P O P O -2400
   3072 RESULT: N O N O P P N P -2396
  12032 RESULT: N O N O P P O O -2394
   3072 RESULT: N O N O P P P N -2392
   3072 RESULT: N O N P N O P P -2372
   3072 RESULT: N O N P N P O P -2366
   3072 RESULT: N O N P N P P O -2364
   3072 RESULT: N O N P O N P P -2354
  12032 RESULT: N O N P O O O P -2348
  12032 RESULT: N O N P O O P O -2346
   3072 RESULT: N O N P O P N P -2342
  12032 RESULT: N O N P O P O O -2340
   3072 RESULT: N O N P O P P N -2338
   3072 RESULT: N O N P P N O P -2330
   3072 RESULT: N O N P P N P O -2328
   3072 RESULT: N O N P P O N P -2324
  12032 RESULT: N O N P P O O O -2322
   3072 RESULT: N O N P P O P N -2320
   3072 RESULT: N O N P P P N O -2316
   3072 RESULT: N O N P P P O N -2314
   3072 RESULT: N O O N N P P P -2282
  12032 RESULT: N O O N O O P P -2264
  12032 RESULT: N O O N O P O P -2258
  12032 RESULT: N O O N O P P O -2256
   3072 RESULT: N O O N P N P P -2246
  12032 RESULT: N O O N P O O P -2240
  12032 RESULT: N O O N P O P O -2238
   3072 RESULT: N O O N P P N P -2234
  12032 RESULT: N O O N P P O O -2232
   3072 RESULT: N O O N P P P N -2230
  12032 RESULT: N O O O N O P P -2210
  12032 RESULT: N O O O N P O P -2204
  12032 RESULT: N O O O N P P O -2202
  12032 RESULT: N O O O O N P P -2192
  13440 RESULT: N O O O O O O P -2186
  13440 RESULT: N O O O O O P O -2184
  12032 RESULT: N O O O O P N P -2180
  13440 RESULT: N O O O O P O O -2178
  12032 RESULT: N O O O O P P N -2176
  12032 RESULT: N O O O P N O P -2168
  12032 RESULT: N O O O P N P O -2166
  12032 RESULT: N O O O P O N P -2162
  13440 RESULT: N O O O P O O O -2160
  12032 RESULT: N O O O P O P N -2158
  12032 RESULT: N O O O P P N O -2154
  12032 RESULT: N O O O P P O N -2152
   3072 RESULT: N O O P N N P P -2138
  12032 RESULT: N O O P N O O P -2132
  12032 RESULT: N O O P N O P O -2130
   3072 RESULT: N O O P N P N P -2126
  12032 RESULT: N O O P N P O O -2124
   3072 RESULT: N O O P N P P N -2122
  12032 RESULT: N O O P O N O P -2114
  12032 RESULT: N O O P O N P O -2112
  12032 RESULT: N O O P O O N P -2108
  13440 RESULT: N O O P O O O O -2106
  12032 RESULT: N O O P O O P N -2104
  12032 RESULT: N O O P O P N O -2100
  12032 RESULT: N O O P O P O N -2098
   3072 RESULT: N O O P P N N P -2090
  12032 RESULT: N O O P P N O O -2088
   3072 RESULT: N O O P P N P N -2086
  12032 RESULT: N O O P P O N O -2082
  12032 RESULT: N O O P P O O N -2080
   3072 RESULT: N O O P P P N N -2074
   3072 RESULT: N O P N N O P P -2048
   3072 RESULT: N O P N N P O P -2042
   3072 RESULT: N O P N N P P O -2040
   3072 RESULT: N O P N O N P P -2030
  12032 RESULT: N O P N O O O P -2024
  12032 RESULT: N O P N O O P O -2022
   3072 RESULT: N O P N O P N P -2018
  12032 RESULT: N O P N O P O O -2016
   3072 RESULT: N O P N O P P N -2014
   3072 RESULT: N O P N P N O P -2006
   3072 RESULT: N O P N P N P O -2004
   3072 RESULT: N O P N P O N P -2000
  12032 RESULT: N O P N P O O O -1998
   3072 RESULT: N O P N P O P N -1996
   3072 RESULT: N O P N P P N O -1992
   3072 RESULT: N O P N P P O N -1990
   3072 RESULT: N O P O N N P P -1976
  12032 RESULT: N O P O N O O P -1970
  12032 RESULT: N O P O N O P O -1968
   3072 RESULT: N O P O N P N P -1964
  12032 RESULT: N O P O N P O O -1962
   3072 RESULT: N O P O N P P N -1960
  12032 RESULT: N O P O O N O P -1952
  12032 RESULT: N O P O O N P O -1950
  12032 RESULT: N O P O O O N P -1946
  13440 RESULT: N O P O O O O O -1944
  12032 RESULT: N O P O O O P N -1942
  12032 RESULT: N O P O O P N O -1938
  12032 RESULT: N O P O O P O N -1936
   3072 RESULT: N O P O P N N P -1928
  12032 RESULT: N O P O P N O O -1926
   3072 RESULT: N O P O P N P N -1924
  12032 RESULT: N O P O P O N O -1920
  12032 RESULT: N O P O P O O N -1918
   3072 RESULT: N O P O P P N N -1912
   3072 RESULT: N O P P N N O P -1898
   3072 RESULT: N O P P N N P O -1896
   3072 RESULT: N O P P N O N P -1892
  12032 RESULT: N O P P N O O O -1890
   3072 RESULT: N O P P N O P N -1888
   3072 RESULT: N O P P N P N O -1884
   3072 RESULT: N O P P N P O N -1882
   3072 RESULT: N O P P O N N P -1874
  12032 RESULT: N O P P O N O O -1872
   3072 RESULT: N O P P O N P N -1870
  12032 RESULT: N O P P O O N O -1866
  12032 RESULT: N O P P O O O N -1864
   3072 RESULT: N O P P O P N N -1858
   3072 RESULT: N O P P P N N O -1848
   3072 RESULT: N O P P P N O N -1846
   3072 RESULT: N O P P P O N N -1840
  42496 RESULT: N P N N N P P P -1796
   3072 RESULT: N P N N O O P P -1778
   3072 RESULT: N P N N O P O P -1772
   3072 RESULT: N P N N O P P O -1770
  42496 RESULT: N P N N P N P P -1760
   3072 RESULT: N P N N P O O P -1754
   3072 RESULT: N P N N P O P O -1752
  42496 RESULT: N P N N P P N P -1748
   3072 RESULT: N P N N P P O O -1746
  42496 RESULT: N P N N P P P N -1744
   3072 RESULT: N P N O N O P P -1724
   3072 RESULT: N P N O N P O P -1718
   3072 RESULT: N P N O N P P O -1716
   3072 RESULT: N P N O O N P P -1706
  12032 RESULT: N P N O O O O P -1700
  12032 RESULT: N P N O O O P O -1698
   3072 RESULT: N P N O O P N P -1694
  12032 RESULT: N P N O O P O O -1692
   3072 RESULT: N P N O O P P N -1690
   3072 RESULT: N P N O P N O P -1682
   3072 RESULT: N P N O P N P O -1680
   3072 RESULT: N P N O P O N P -1676
  12032 RESULT: N P N O P O O O -1674
   3072 RESULT: N P N O P O P N -1672
   3072 RESULT: N P N O P P N O -1668
   3072 RESULT: N P N O P P O N -1666
  42496 RESULT: N P N P N N P P -1652
   3072 RESULT: N P N P N O O P -1646
   3072 RESULT: N P N P N O P O -1644
  42496 RESULT: N P N P N P N P -1640
   3072 RESULT: N P N P N P O O -1638
  42496 RESULT: N P N P N P P N -1636
   3072 RESULT: N P N P O N O P -1628
   3072 RESULT: N P N P O N P O -1626
   3072 RESULT: N P N P O O N P -1622
  12032 RESULT: N P N P O O O O -1620
   3072 RESULT: N P N P O O P N -1618
   3072 RESULT: N P N P O P N O -1614
   3072 RESULT: N P N P O P O N -1612
  42496 RESULT: N P N P P N N P -1604
   3072 RESULT: N P N P P N O O -1602
  42496 RESULT: N P N P P N P N -1600
   3072 RESULT: N P N P P O N O -1596
   3072 RESULT: N P N P P O O N -1594
  42496 RESULT: N P N P P P N N -1588
   3072 RESULT: N P O N N O P P -1562
   3072 RESULT: N P O N N P O P -1556
   3072 RESULT: N P O N N P P O -1554
   3072 RESULT: N P O N O N P P -1544
  12032 RESULT: N P O N O O O P -1538
  12032 RESULT: N P O N O O P O -1536
   3072 RESULT: N P O N O P N P -1532
  12032 RESULT: N P O N O P O O -1530
   3072 RESULT: N P O N O P P N -1528
   3072 RESULT: N P O N P N O P -1520
   3072 RESULT: N P O N P N P O -1518
   3072 RESULT: N P O N P O N P -1514
  12032 RESULT: N P O N P O O O -1512
   3072 RESULT: N P O N P O P N -1510
   3072 RESULT: N P O N P P N O -1506
   3072 RESULT: N P O N P P O N -1504
   3072 RESULT: N P O O N N P P -1490
  12032 RESULT: N P O O N O O P -1484
  12032 RESULT: N P O O N O P O -1482
   3072 RESULT: N P O O N P N P -1478
  12032 RESULT: N P O O N P O O -1476
   3072 RESULT: N P O O N P P N -1474
  12032 RESULT: N P O O O N O P -1466
  12032 RESULT: N P O O O N P O -1464
  12032 RESULT: N P O O O O N P -1460
  13440 RESULT: N P O O O O O O -1458
  12032 RESULT: N P O O O O P N -1456
  12032 RESULT: N P O O O P N O -1452
  12032 RESULT: N P O O O P O N -1450
   3072 RESULT: N P O O P N N P -1442
  12032 RESULT: N P O O P N O O -1440
   3072 RESULT: N P O O P N P N -1438
  12032 RESULT: N P O O P O N O -1434
  12032 RESULT: N P O O P O O N -1432
   3072 RESULT: N P O O P P N N -1426
   3072 RESULT: N P O P N N O P -1412
   3072 RESULT: N P O P N N P O -1410
   3072 RESULT: N P O P N O N P -1406
  12032 RESULT: N P O P N O O O -1404
   3072 RESULT: N P O P N O P N -1402
   3072 RESULT: N P O P N P N O -1398
   3072 RESULT: N P O P N P O N -1396
   3072 RESULT: N P O P O N N P -1388
  12032 RESULT: N P O P O N O O -1386
   3072 RESULT: N P O P O N P N -1384
  12032 RESULT: N P O P O O N O -1380
  12032 RESULT: N P O P O O O N -1378
   3072 RESULT: N P O P O P N N -1372
   3072 RESULT: N P O P P N N O -1362
   3072 RESULT: N P O P P N O N -1360
   3072 RESULT: N P O P P O N N -1354
  42496 RESULT: N P P N N N P P -1328
   3072 RESULT: N P P N N O O P -1322
   3072 RESULT: N P P N N O P O -1320
  42496 RESULT: N P P N N P N P -1316
   3072 RESULT: N P P N N P O O -1314
  42496 RESULT: N P P N N P P N -1312
   3072 RESULT: N P P N O N O P -1304
   3072 RESULT: N P P N O N P O -1302
   3072 RESULT: N P P N O O N P -1298
  12032 RESULT: N P P N O O O O -1296
   3072 RESULT: N P P N O O P N -1294
   3072 RESULT: N P P N O P N O -1290
   3072 RESULT: N P P N O P O N -1288
  42496 RESULT: N P P N P N N P -1280
   3072 RESULT: N P P N P N O O -1278
  42496 RESULT: N P P N P N P N -1276
   3072 RESULT: N P P N P O N O -1272
   3072 RESULT: N P P N P O O N -1270
  42496 RESULT: N P P N P P N N -1264
   3072 RESULT: N P P O N N O P -1250
   3072 RESULT: N P P O N N P O -1248
   3072 RESULT: N P P O N O N P -1244
  12032 RESULT: N P P O N O O O -1242
   3072 RESULT: N P P O N O P N -1240
   3072 RESULT: N P P O N P N O -1236
   3072 RESULT: N P P O N P O N -1234
   3072 RESULT: N P P O O N N P -1226
  12032 RESULT: N P P O O N O O -1224
   3072 RESULT: N P P O O N P N -1222
  12032 RESULT: N P P O O O N O -1218
  12032 RESULT: N P P O O O O N -1216
   3072 RESULT: N P P O O P N N -1210
   3072 RESULT: N P P O P N N O -1200
   3072 RESULT: N P P O P N O N -1198
   3072 RESULT: N P P O P O N N -1192
  42496 RESULT: N P P P N N N P -1172
   3072 RESULT: N P P P N N O O -1170
  42496 RESULT: N P P P N N P N -1168
   3072 RESULT: N P P P N O N O -1164
   3072 RESULT: N P P P N O O N -1162
  42496 RESULT: N P P P N P N N -1156
   3072 RESULT: N P P P O N N O -1146
   3072 RESULT: N P P P O N O N -1144
   3072 RESULT: N P P P O O N N -1138
  42496 RESULT: N P P P P N N N -1120
   3072 RESULT: O N N N O P P P -1040
   3072 RESULT: O N N N P O P P -1022
   3072 RESULT: O N N N P P O P -1016
   3072 RESULT: O N N N P P P O -1014
   3072 RESULT: O N N O N P P P -986
  12032 RESULT: O N N O O O P P -968
  12032 RESULT: O N N O O P O P -962
  12032 RESULT: O N N O O P P O -960
   3072 RESULT: O N N O P N P P -950
  12032 RESULT: O N N O P O O P -944
  12032 RESULT: O N N O P O P O -942
   3072 RESULT: O N N O P P N P -938
  12032 RESULT: O N N O P P O O -936
   3072 RESULT: O N N O P P P N -934
   3072 RESULT: O N N P N O P P -914
   3072 RESULT: O N N P N P O P -908
   3072 RESULT: O N N P N P P O -906
   3072 RESULT: O N N P O N P P -896
  12032 RESULT: O N N P O O O P -890
  12032 RESULT: O N N P O O P O -888
   3072 RESULT: O N N P O P N P -884
  12032 RESULT: O N N P O P O O -882
   3072 RESULT: O N N P O P P N -880
   3072 RESULT: O N N P P N O P -872
   3072 RESULT: O N N P P N P O -870
   3072 RESULT: O N N P P O N P -866
  12032 RESULT: O N N P P O O O -864
   3072 RESULT: O N N P P O P N -862
   3072 RESULT: O N N P P P N O -858
   3072 RESULT: O N N P P P O N -856
   3072 RESULT: O N O N N P P P -824
  12032 RESULT: O N O N O O P P -806
  12032 RESULT: O N O N O P O P -800
  12032 RESULT: O N O N O P P O -798
   3072 RESULT: O N O N P N P P -788
  12032 RESULT: O N O N P O O P -782
  12032 RESULT: O N O N P O P O -780
   3072 RESULT: O N O N P P N P -776
  12032 RESULT: O N O N P P O O -774
   3072 RESULT: O N O N P P P N -772
  12032 RESULT: O N O O N O P P -752
  12032 RESULT: O N O O N P O P -746
  12032 RESULT: O N O O N P P O -744
  12032 RESULT: O N O O O N P P -734
  13440 RESULT: O N O O O O O P -728
  13440 RESULT: O N O O O O P O -726
  12032 RESULT: O N O O O P N P -722
  13440 RESULT: O N O O O P O O -720
  12032 RESULT: O N O O O P P N -718
  12032 RESULT: O N O O P N O P -710
  12032 RESULT: O N O O P N P O -708
  12032 RESULT: O N O O P O N P -704
  13440 RESULT: O N O O P O O O -702
  12032 RESULT: O N O O P O P N -700
  12032 RESULT: O N O O P P N O -696
  12032 RESULT: O N O O P P O N -694
   3072 RESULT: O N O P N N P P -680
  12032 RESULT: O N O P N O O P -674
  12032 RESULT: O N O P N O P O -672
   3072 RESULT: O N O P N P N P -668
  12032 RESULT: O N O P N P O O -666
   3072 RESULT: O N O P N P P N -664
  12032 RESULT: O N O P O N O P -656
  12032 RESULT: O N O P O N P O -654
  12032 RESULT: O N O P O O N P -650
  13440 RESULT: O N O P O O O O -648
  12032 RESULT: O N O P O O P N -646
  12032 RESULT: O N O P O P N O -642
  12032 RESULT: O N O P O P O N -640
   3072 RESULT: O N O P P N N P -632
  12032 RESULT: O N O P P N O O -630
   3072 RESULT: O N O P P N P N -628
  12032 RESULT: O N O P P O N O -624
  12032 RESULT: O N O P P O O N -622
   3072 RESULT: O N O P P P N N -616
   3072 RESULT: O N P N N O P P -590
   3072 RESULT: O N P N N P O P -584
   3072 RESULT: O N P N N P P O -582
   3072 RESULT: O N P N O N P P -572
  12032 RESULT: O N P N O O O P -566
  12032 RESULT: O N P N O O P O -564
   3072 RESULT: O N P N O P N P -560
  12032 RESULT: O N P N O P O O -558
   3072 RESULT: O N P N O P P N -556
   3072 RESULT: O N P N P N O P -548
   3072 RESULT: O N P N P N P O -546
   3072 RESULT: O N P N P O N P -542
  12032 RESULT: O N P N P O O O -540
   3072 RESULT: O N P N P O P N -538
   3072 RESULT: O N P N P P N O -534
   3072 RESULT: O N P N P P O N -532
   3072 RESULT: O N P O N N P P -518
  12032 RESULT: O N P O N O O P -512
  12032 RESULT: O N P O N O P O -510
   3072 RESULT: O N P O N P N P -506
  12032 RESULT: O N P O N P O O -504
   3072 RESULT: O N P O N P P N -502
  12032 RESULT: O N P O O N O P -494
  12032 RESULT: O N P O O N P O -492
  12032 RESULT: O N P O O O N P -488
  13440 RESULT: O N P O O O O O -486
  12032 RESULT: O N P O O O P N -484
  12032 RESULT: O N P O O P N O -480
  12032 RESULT: O N P O O P O N -478
   3072 RESULT: O N P O P N N P -470
  12032 RESULT: O N P O P N O O -468
   3072 RESULT: O N P O P N P N -466
  12032 RESULT: O N P O P O N O -462
  12032 RESULT: O N P O P O O N -460
   3072 RESULT: O N P O P P N N -454
   3072 RESULT: O N P P N N O P -440
   3072 RESULT: O N P P N N P O -438
   3072 RESULT: O N P P N O N P -434
  12032 RESULT: O N P P N O O O -432
   3072 RESULT: O N P P N O P N -430
   3072 RESULT: O N P P N P N O -426
   3072 RESULT: O N P P N P O N -424
   3072 RESULT: O N P P O N N P -416
  12032 RESULT: O N P P O N O O -414
   3072 RESULT: O N P P O N P N -412
  12032 RESULT: O N P P O O N O -408
  12032 RESULT: O N P P O O O N -406
   3072 RESULT: O N P P O P N N -400
   3072 RESULT: O N P P P N N O -390
   3072 RESULT: O N P P P N O N -388
   3072 RESULT: O N P P P O N N -382
   3072 RESULT: O O N N N P P P -338
  12032 RESULT: O O N N O O P P -320
  12032 RESULT: O O N N O P O P -314
  12032 RESULT: O O N N O P P O -312
   3072 RESULT: O O N N P N P P -302
  12032 RESULT: O O N N P O O P -296
  12032 RESULT: O O N N P O P O -294
   3072 RESULT: O O N N P P N P -290
  12032 RESULT: O O N N P P O O -288
   3072 RESULT: O O N N P P P N -286
  12032 RESULT: O O N O N O P P -266
  12032 RESULT: O O N O N P O P -260
  12032 RESULT: O O N O N P P O -258
  12032 RESULT: O O N O O N P P -248
  13440 RESULT: O O N O O O O P -242
  13440 RESULT: O O N O O O P O -240
  12032 RESULT: O O N O O P N P -236
  13440 RESULT: O O N O O P O O -234
  12032 RESULT: O O N O O P P N -232
  12032 RESULT: O O N O P N O P -224
  12032 RESULT: O O N O P N P O -222
  12032 RESULT: O O N O P O N P -218
  13440 RESULT: O O N O P O O O -216
  12032 RESULT: O O N O P O P N -214
  12032 RESULT: O O N O P P N O -210
  12032 RESULT: O O N O P P O N -208
   3072 RESULT: O O N P N N P P -194
  12032 RESULT: O O N P N O O P -188
  12032 RESULT: O O N P N O P O -186
   3072 RESULT: O O N P N P N P -182
  12032 RESULT: O O N P N P O O -180
   3072 RESULT: O O N P N P P N -178
  12032 RESULT: O O N P O N O P -170
  12032 RESULT: O O N P O N P O -168
  12032 RESULT: O O N P O O N P -164
  13440 RESULT: O O N P O O O O -162
  12032 RESULT: O O N P O O P N -160
  12032 RESULT: O O N P O P N O -156
  12032 RESULT: O O N P O P O N -154
   3072 RESULT: O O N P P N N P -146
  12032 RESULT: O O N P P N O O -144
   3072 RESULT: O O N P P N P N -142
  12032 RESULT: O O N P P O N O -138
  12032 RESULT: O O N P P O O N -136
   3072 RESULT: O O N P P P N N -130
  12032 RESULT: O O O N N O P P -104
  12032 RESULT: O O O N N P O P -98
  12032 RESULT: O O O N N P P O -96
  12032 RESULT: O O O N O N P P -86
  13440 RESULT: O O O N O O O P -80
  13440 RESULT: O O O N O O P O -78
  12032 RESULT: O O O N O P N P -74
  13440 RESULT: O O O N O P O O -72
  12032 RESULT: O O O N O P P N -70
  12032 RESULT: O O O N P N O P -62
  12032 RESULT: O O O N P N P O -60
  12032 RESULT: O O O N P O N P -56
  13440 RESULT: O O O N P O O O -54
  12032 RESULT: O O O N P O P N -52
  12032 RESULT: O O O N P P N O -48
  12032 RESULT: O O O N P P O N -46
  12032 RESULT: O O O O N N P P -32
  13440 RESULT: O O O O N O O P -26
  13440 RESULT: O O O O N O P O -24
  12032 RESULT: O O O O N P N P -20
  13440 RESULT: O O O O N P O O -18
  12032 RESULT: O O O O N P P N -16
  13440 RESULT: O O O O O N O P -8
  13440 RESULT: O O O O O N P O -6
  13440 RESULT: O O O O O O N P -2
  13440 RESULT: O O O O O O P N 2
  13440 RESULT: O O O O O P N O 6
  13440 RESULT: O O O O O P O N 8
  12032 RESULT: O O O O P N N P 16
  13440 RESULT: O O O O P N O O 18
  12032 RESULT: O O O O P N P N 20
  13440 RESULT: O O O O P O N O 24
  13440 RESULT: O O O O P O O N 26
  12032 RESULT: O O O O P P N N 32
  12032 RESULT: O O O P N N O P 46
  12032 RESULT: O O O P N N P O 48
  12032 RESULT: O O O P N O N P 52
  13440 RESULT: O O O P N O O O 54
  12032 RESULT: O O O P N O P N 56
  12032 RESULT: O O O P N P N O 60
  12032 RESULT: O O O P N P O N 62
  12032 RESULT: O O O P O N N P 70
  13440 RESULT: O O O P O N O O 72
  12032 RESULT: O O O P O N P N 74
  13440 RESULT: O O O P O O N O 78
  13440 RESULT: O O O P O O O N 80
  12032 RESULT: O O O P O P N N 86
  12032 RESULT: O O O P P N N O 96
  12032 RESULT: O O O P P N O N 98
  12032 RESULT: O O O P P O N N 104
   3072 RESULT: O O P N N N P P 130
  12032 RESULT: O O P N N O O P 136
  12032 RESULT: O O P N N O P O 138
   3072 RESULT: O O P N N P N P 142
  12032 RESULT: O O P N N P O O 144
   3072 RESULT: O O P N N P P N 146
  12032 RESULT: O O P N O N O P 154
  12032 RESULT: O O P N O N P O 156
  12032 RESULT: O O P N O O N P 160
  13440 RESULT: O O P N O O O O 162
  12032 RESULT: O O P N O O P N 164
  12032 RESULT: O O P N O P N O 168
  12032 RESULT: O O P N O P O N 170
   3072 RESULT: O O P N P N N P 178
  12032 RESULT: O O P N P N O O 180
   3072 RESULT: O O P N P N P N 182
  12032 RESULT: O O P N P O N O 186
  12032 RESULT: O O P N P O O N 188
   3072 RESULT: O O P N P P N N 194
  12032 RESULT: O O P O N N O P 208
  12032 RESULT: O O P O N N P O 210
  12032 RESULT: O O P O N O N P 214
  13440 RESULT: O O P O N O O O 216
  12032 RESULT: O O P O N O P N 218
  12032 RESULT: O O P O N P N O 222
  12032 RESULT: O O P O N P O N 224
  12032 RESULT: O O P O O N N P 232
  13440 RESULT: O O P O O N O O 234
  12032 RESULT: O O P O O N P N 236
  13440 RESULT: O O P O O O N O 240
  13440 RESULT: O O P O O O O N 242
  12032 RESULT: O O P O O P N N 248
  12032 RESULT: O O P O P N N O 258
  12032 RESULT: O O P O P N O N 260
  12032 RESULT: O O P O P O N N 266
   3072 RESULT: O O P P N N N P 286
  12032 RESULT: O O P P N N O O 288
   3072 RESULT: O O P P N N P N 290
  12032 RESULT: O O P P N O N O 294
  12032 RESULT: O O P P N O O N 296
   3072 RESULT: O O P P N P N N 302
  12032 RESULT: O O P P O N N O 312
  12032 RESULT: O O P P O N O N 314
  12032 RESULT: O O P P O O N N 320
   3072 RESULT: O O P P P N N N 338
   3072 RESULT: O P N N N O P P 382
   3072 RESULT: O P N N N P O P 388
   3072 RESULT: O P N N N P P O 390
   3072 RESULT: O P N N O N P P 400
  12032 RESULT: O P N N O O O P 406
  12032 RESULT: O P N N O O P O 408
   3072 RESULT: O P N N O P N P 412
  12032 RESULT: O P N N O P O O 414
   3072 RESULT: O P N N O P P N 416
   3072 RESULT: O P N N P N O P 424
   3072 RESULT: O P N N P N P O 426
   3072 RESULT: O P N N P O N P 430
  12032 RESULT: O P N N P O O O 432
   3072 RESULT: O P N N P O P N 434
   3072 RESULT: O P N N P P N O 438
   3072 RESULT: O P N N P P O N 440
   3072 RESULT: O P N O N N P P 454
  12032 RESULT: O P N O N O O P 460
  12032 RESULT: O P N O N O P O 462
   3072 RESULT: O P N O N P N P 466
  12032 RESULT: O P N O N P O O 468
   3072 RESULT: O P N O N P P N 470
  12032 RESULT: O P N O O N O P 478
  12032 RESULT: O P N O O N P O 480
  12032 RESULT: O P N O O O N P 484
  13440 RESULT: O P N O O O O O 486
  12032 RESULT: O P N O O O P N 488
  12032 RESULT: O P N O O P N O 492
  12032 RESULT: O P N O O P O N 494
   3072 RESULT: O P N O P N N P 502
  12032 RESULT: O P N O P N O O 504
   3072 RESULT: O P N O P N P N 506
  12032 RESULT: O P N O P O N O 510
  12032 RESULT: O P N O P O O N 512
   3072 RESULT: O P N O P P N N 518
   3072 RESULT: O P N P N N O P 532
   3072 RESULT: O P N P N N P O 534
   3072 RESULT: O P N P N O N P 538
  12032 RESULT: O P N P N O O O 540
   3072 RESULT: O P N P N O P N 542
   3072 RESULT: O P N P N P N O 546
   3072 RESULT: O P N P N P O N 548
   3072 RESULT: O P N P O N N P 556
  12032 RESULT: O P N P O N O O 558
   3072 RESULT: O P N P O N P N 560
  12032 RESULT: O P N P O O N O 564
  12032 RESULT: O P N P O O O N 566
   3072 RESULT: O P N P O P N N 572
   3072 RESULT: O P N P P N N O 582
   3072 RESULT: O P N P P N O N 584
   3072 RESULT: O P N P P O N N 590
   3072 RESULT: O P O N N N P P 616
  12032 RESULT: O P O N N O O P 622
  12032 RESULT: O P O N N O P O 624
   3072 RESULT: O P O N N P N P 628
  12032 RESULT: O P O N N P O O 630
   3072 RESULT: O P O N N P P N 632
  12032 RESULT: O P O N O N O P 640
  12032 RESULT: O P O N O N P O 642
  12032 RESULT: O P O N O O N P 646
  13440 RESULT: O P O N O O O O 648
  12032 RESULT: O P O N O O P N 650
  12032 RESULT: O P O N O P N O 654
  12032 RESULT: O P O N O P O N 656
   3072 RESULT: O P O N P N N P 664
  12032 RESULT: O P O N P N O O 666
   3072 RESULT: O P O N P N P N 668
  12032 RESULT: O P O N P O N O 672
  12032 RESULT: O P O N P O O N 674
   3072 RESULT: O P O N P P N N 680
  12032 RESULT: O P O O N N O P 694
  12032 RESULT: O P O O N N P O 696
  12032 RESULT: O P O O N O N P 700
  13440 RESULT: O P O O N O O O 702
  12032 RESULT: O P O O N O P N 704
  12032 RESULT: O P O O N P N O 708
  12032 RESULT: O P O O N P O N 710
  12032 RESULT: O P O O O N N P 718
  13440 RESULT: O P O O O N O O 720
  12032 RESULT: O P O O O N P N 722
  13440 RESULT: O P O O O O N O 726
  13440 RESULT: O P O O O O O N 728
  12032 RESULT: O P O O O P N N 734
  12032 RESULT: O P O O P N N O 744
  12032 RESULT: O P O O P N O N 746
  12032 RESULT: O P O O P O N N 752
   3072 RESULT: O P O P N N N P 772
  12032 RESULT: O P O P N N O O 774
   3072 RESULT: O P O P N N P N 776
  12032 RESULT: O P O P N O N O 780
  12032 RESULT: O P O P N O O N 782
   3072 RESULT: O P O P N P N N 788
  12032 RESULT: O P O P O N N O 798
  12032 RESULT: O P O P O N O N 800
  12032 RESULT: O P O P O O N N 806
   3072 RESULT: O P O P P N N N 824
   3072 RESULT: O P P N N N O P 856
   3072 RESULT: O P P N N N P O 858
   3072 RESULT: O P P N N O N P 862
  12032 RESULT: O P P N N O O O 864
   3072 RESULT: O P P N N O P N 866
   3072 RESULT: O P P N N P N O 870
   3072 RESULT: O P P N N P O N 872
   3072 RESULT: O P P N O N N P 880
  12032 RESULT: O P P N O N O O 882
   3072 RESULT: O P P N O N P N 884
  12032 RESULT: O P P N O O N O 888
  12032 RESULT: O P P N O O O N 890
   3072 RESULT: O P P N O P N N 896
   3072 RESULT: O P P N P N N O 906
   3072 RESULT: O P P N P N O N 908
   3072 RESULT: O P P N P O N N 914
   3072 RESULT: O P P O N N N P 934
  12032 RESULT: O P P O N N O O 936
   3072 RESULT: O P P O N N P N 938
  12032 RESULT: O P P O N O N O 942
  12032 RESULT: O P P O N O O N 944
   3072 RESULT: O P P O N P N N 950
  12032 RESULT: O P P O O N N O 960
  12032 RESULT: O P P O O N O N 962
  12032 RESULT: O P P O O O N N 968
   3072 RESULT: O P P O P N N N 986
   3072 RESULT: O P P P N N N O 1014
   3072 RESULT: O P P P N N O N 1016
   3072 RESULT: O P P P N O N N 1022
   3072 RESULT: O P P P O N N N 1040
  42496 RESULT: P N N N N P P P 1120
   3072 RESULT: P N N N O O P P 1138
   3072 RESULT: P N N N O P O P 1144
   3072 RESULT: P N N N O P P O 1146
  42496 RESULT: P N N N P N P P 1156
   3072 RESULT: P N N N P O O P 1162
   3072 RESULT: P N N N P O P O 1164
  42496 RESULT: P N N N P P N P 1168
   3072 RESULT: P N N N P P O O 1170
  42496 RESULT: P N N N P P P N 1172
   3072 RESULT: P N N O N O P P 1192
   3072 RESULT: P N N O N P O P 1198
   3072 RESULT: P N N O N P P O 1200
   3072 RESULT: P N N O O N P P 1210
  12032 RESULT: P N N O O O O P 1216
  12032 RESULT: P N N O O O P O 1218
   3072 RESULT: P N N O O P N P 1222
  12032 RESULT: P N N O O P O O 1224
   3072 RESULT: P N N O O P P N 1226
   3072 RESULT: P N N O P N O P 1234
   3072 RESULT: P N N O P N P O 1236
   3072 RESULT: P N N O P O N P 1240
  12032 RESULT: P N N O P O O O 1242
   3072 RESULT: P N N O P O P N 1244
   3072 RESULT: P N N O P P N O 1248
   3072 RESULT: P N N O P P O N 1250
  42496 RESULT: P N N P N N P P 1264
   3072 RESULT: P N N P N O O P 1270
   3072 RESULT: P N N P N O P O 1272
  42496 RESULT: P N N P N P N P 1276
   3072 RESULT: P N N P N P O O 1278
  42496 RESULT: P N N P N P P N 1280
   3072 RESULT: P N N P O N O P 1288
   3072 RESULT: P N N P O N P O 1290
   3072 RESULT: P N N P O O N P 1294
  12032 RESULT: P N N P O O O O 1296
   3072 RESULT: P N N P O O P N 1298
   3072 RESULT: P N N P O P N O 1302
   3072 RESULT: P N N P O P O N 1304
  42496 RESULT: P N N P P N N P 1312
   3072 RESULT: P N N P P N O O 1314
  42496 RESULT: P N N P P N P N 1316
   3072 RESULT: P N N P P O N O 1320
   3072 RESULT: P N N P P O O N 1322
  42496 RESULT: P N N P P P N N 1328
   3072 RESULT: P N O N N O P P 1354
   3072 RESULT: P N O N N P O P 1360
   3072 RESULT: P N O N N P P O 1362
   3072 RESULT: P N O N O N P P 1372
  12032 RESULT: P N O N O O O P 1378
  12032 RESULT: P N O N O O P O 1380
   3072 RESULT: P N O N O P N P 1384
  12032 RESULT: P N O N O P O O 1386
   3072 RESULT: P N O N O P P N 1388
   3072 RESULT: P N O N P N O P 1396
   3072 RESULT: P N O N P N P O 1398
   3072 RESULT: P N O N P O N P 1402
  12032 RESULT: P N O N P O O O 1404
   3072 RESULT: P N O N P O P N 1406
   3072 RESULT: P N O N P P N O 1410
   3072 RESULT: P N O N P P O N 1412
   3072 RESULT: P N O O N N P P 1426
  12032 RESULT: P N O O N O O P 1432
  12032 RESULT: P N O O N O P O 1434
   3072 RESULT: P N O O N P N P 1438
  12032 RESULT: P N O O N P O O 1440
   3072 RESULT: P N O O N P P N 1442
  12032 RESULT: P N O O O N O P 1450
  12032 RESULT: P N O O O N P O 1452
  12032 RESULT: P N O O O O N P 1456
  13440 RESULT: P N O O O O O O 1458
  12032 RESULT: P N O O O O P N 1460
  12032 RESULT: P N O O O P N O 1464
  12032 RESULT: P N O O O P O N 1466
   3072 RESULT: P N O O P N N P 1474
  12032 RESULT: P N O O P N O O 1476
   3072 RESULT: P N O O P N P N 1478
  12032 RESULT: P N O O P O N O 1482
  12032 RESULT: P N O O P O O N 1484
   3072 RESULT: P N O O P P N N 1490
   3072 RESULT: P N O P N N O P 1504
   3072 RESULT: P N O P N N P O 1506
   3072 RESULT: P N O P N O N P 1510
  12032 RESULT: P N O P N O O O 1512
   3072 RESULT: P N O P N O P N 1514
   3072 RESULT: P N O P N P N O 1518
   3072 RESULT: P N O P N P O N 1520
   3072 RESULT: P N O P O N N P 1528
  12032 RESULT: P N O P O N O O 1530
   3072 RESULT: P N O P O N P N 1532
  12032 RESULT: P N O P O O N O 1536
  12032 RESULT: P N O P O O O N 1538
   3072 RESULT: P N O P O P N N 1544
   3072 RESULT: P N O P P N N O 1554
   3072 RESULT: P N O P P N O N 1556
   3072 RESULT: P N O P P O N N 1562
  42496 RESULT: P N P N N N P P 1588
   3072 RESULT: P N P N N O O P 1594
   3072 RESULT: P N P N N O P O 1596
  42496 RESULT: P N P N N P N P 1600
   3072 RESULT: P N P N N P O O 1602
  42496 RESULT: P N P N N P P N 1604
   3072 RESULT: P N P N O N O P 1612
   3072 RESULT: P N P N O N P O 1614
   3072 RESULT: P N P N O O N P 1618
  12032 RESULT: P N P N O O O O 1620
   3072 RESULT: P N P N O O P N 1622
   3072 RESULT: P N P N O P N O 1626
   3072 RESULT: P N P N O P O N 1628
  42496 RESULT: P N P N P N N P 1636
   3072 RESULT: P N P N P N O O 1638
  42496 RESULT: P N P N P N P N 1640
   3072 RESULT: P N P N P O N O 1644
   3072 RESULT: P N P N P O O N 1646
  42496 RESULT: P N P N P P N N 1652
   3072 RESULT: P N P O N N O P 1666
   3072 RESULT: P N P O N N P O 1668
   3072 RESULT: P N P O N O N P 1672
  12032 RESULT: P N P O N O O O 1674
   3072 RESULT: P N P O N O P N 1676
   3072 RESULT: P N P O N P N O 1680
   3072 RESULT: P N P O N P O N 1682
   3072 RESULT: P N P O O N N P 1690
  12032 RESULT: P N P O O N O O 1692
   3072 RESULT: P N P O O N P N 1694
  12032 RESULT: P N P O O O N O 1698
  12032 RESULT: P N P O O O O N 1700
   3072 RESULT: P N P O O P N N 1706
   3072 RESULT: P N P O P N N O 1716
   3072 RESULT: P N P O P N O N 1718
   3072 RESULT: P N P O P O N N 1724
  42496 RESULT: P N P P N N N P 1744
   3072 RESULT: P N P P N N O O 1746
  42496 RESULT: P N P P N N P N 1748
   3072 RESULT: P N P P N O N O 1752
   3072 RESULT: P N P P N O O N 1754
  42496 RESULT: P N P P N P N N 1760
   3072 RESULT: P N P P O N N O 1770
   3072 RESULT: P N P P O N O N 1772
   3072 RESULT: P N P P O O N N 1778
  42496 RESULT: P N P P P N N N 1796
   3072 RESULT: P O N N N O P P 1840
   3072 RESULT: P O N N N P O P 1846
   3072 RESULT: P O N N N P P O 1848
   3072 RESULT: P O N N O N P P 1858
  12032 RESULT: P O N N O O O P 1864
  12032 RESULT: P O N N O O P O 1866
   3072 RESULT: P O N N O P N P 1870
  12032 RESULT: P O N N O P O O 1872
   3072 RESULT: P O N N O P P N 1874
   3072 RESULT: P O N N P N O P 1882
   3072 RESULT: P O N N P N P O 1884
   3072 RESULT: P O N N P O N P 1888
  12032 RESULT: P O N N P O O O 1890
   3072 RESULT: P O N N P O P N 1892
   3072 RESULT: P O N N P P N O 1896
   3072 RESULT: P O N N P P O N 1898
   3072 RESULT: P O N O N N P P 1912
  12032 RESULT: P O N O N O O P 1918
  12032 RESULT: P O N O N O P O 1920
   3072 RESULT: P O N O N P N P 1924
  12032 RESULT: P O N O N P O O 1926
   3072 RESULT: P O N O N P P N 1928
  12032 RESULT: P O N O O N O P 1936
  12032 RESULT: P O N O O N P O 1938
  12032 RESULT: P O N O O O N P 1942
  13440 RESULT: P O N O O O O O 1944
  12032 RESULT: P O N O O O P N 1946
  12032 RESULT: P O N O O P N O 1950
  12032 RESULT: P O N O O P O N 1952
   3072 RESULT: P O N O P N N P 1960
  12032 RESULT: P O N O P N O O 1962
   3072 RESULT: P O N O P N P N 1964
  12032 RESULT: P O N O P O N O 1968
  12032 RESULT: P O N O P O O N 1970
   3072 RESULT: P O N O P P N N 1976
   3072 RESULT: P O N P N N O P 1990
   3072 RESULT: P O N P N N P O 1992
   3072 RESULT: P O N P N O N P 1996
  12032 RESULT: P O N P N O O O 1998
   3072 RESULT: P O N P N O P N 2000
   3072 RESULT: P O N P N P N O 2004
   3072 RESULT: P O N P N P O N 2006
   3072 RESULT: P O N P O N N P 2014
  12032 RESULT: P O N P O N O O 2016
   3072 RESULT: P O N P O N P N 2018
  12032 RESULT: P O N P O O N O 2022
  12032 RESULT: P O N P O O O N 2024
   3072 RESULT: P O N P O P N N 2030
   3072 RESULT: P O N P P N N O 2040
   3072 RESULT: P O N P P N O N 2042
   3072 RESULT: P O N P P O N N 2048
   3072 RESULT: P O O N N N P P 2074
  12032 RESULT: P O O N N O O P 2080
  12032 RESULT: P O O N N O P O 2082
   3072 RESULT: P O O N N P N P 2086
  12032 RESULT: P O O N N P O O 2088
   3072 RESULT: P O O N N P P N 2090
  12032 RESULT: P O O N O N O P 2098
  12032 RESULT: P O O N O N P O 2100
  12032 RESULT: P O O N O O N P 2104
  13440 RESULT: P O O N O O O O 2106
  12032 RESULT: P O O N O O P N 2108
  12032 RESULT: P O O N O P N O 2112
  12032 RESULT: P O O N O P O N 2114
   3072 RESULT: P O O N P N N P 2122
  12032 RESULT: P O O N P N O O 2124
   3072 RESULT: P O O N P N P N 2126
  12032 RESULT: P O O N P O N O 2130
  12032 RESULT: P O O N P O O N 2132
   3072 RESULT: P O O N P P N N 2138
  12032 RESULT: P O O O N N O P 2152
  12032 RESULT: P O O O N N P O 2154
  12032 RESULT: P O O O N O N P 2158
  13440 RESULT: P O O O N O O O 2160
  12032 RESULT: P O O O N O P N 2162
  12032 RESULT: P O O O N P N O 2166
  12032 RESULT: P O O O N P O N 2168
  12032 RESULT: P O O O O N N P 2176
  13440 RESULT: P O O O O N O O 2178
  12032 RESULT: P O O O O N P N 2180
  13440 RESULT: P O O O O O N O 2184
  13440 RESULT: P O O O O O O N 2186
  12032 RESULT: P O O O O P N N 2192
  12032 RESULT: P O O O P N N O 2202
  12032 RESULT: P O O O P N O N 2204
  12032 RESULT: P O O O P O N N 2210
   3072 RESULT: P O O P N N N P 2230
  12032 RESULT: P O O P N N O O 2232
   3072 RESULT: P O O P N N P N 2234
  12032 RESULT: P O O P N O N O 2238
  12032 RESULT: P O O P N O O N 2240
   3072 RESULT: P O O P N P N N 2246
  12032 RESULT: P O O P O N N O 2256
  12032 RESULT: P O O P O N O N 2258
  12032 RESULT: P O O P O O N N 2264
   3072 RESULT: P O O P P N N N 2282
   3072 RESULT: P O P N N N O P 2314
   3072 RESULT: P O P N N N P O 2316
   3072 RESULT: P O P N N O N P 2320
  12032 RESULT: P O P N N O O O 2322
   3072 RESULT: P O P N N O P N 2324
   3072 RESULT: P O P N N P N O 2328
   3072 RESULT: P O P N N P O N 2330
   3072 RESULT: P O P N O N N P 2338
  12032 RESULT: P O P N O N O O 2340
   3072 RESULT: P O P N O N P N 2342
  12032 RESULT: P O P N O O N O 2346
  12032 RESULT: P O P N O O O N 2348
   3072 RESULT: P O P N O P N N 2354
   3072 RESULT: P O P N P N N O 2364
   3072 RESULT: P O P N P N O N 2366
   3072 RESULT: P O P N P O N N 2372
   3072 RESULT: P O P O N N N P 2392
  12032 RESULT: P O P O N N O O 2394
   3072 RESULT: P O P O N N P N 2396
  12032 RESULT: P O P O N O N O 2400
  12032 RESULT: P O P O N O O N 2402
   3072 RESULT: P O P O N P N N 2408
  12032 RESULT: P O P O O N N O 2418
  12032 RESULT: P O P O O N O N 2420
  12032 RESULT: P O P O O O N N 2426
   3072 RESULT: P O P O P N N N 2444
   3072 RESULT: P O P P N N N O 2472
   3072 RESULT: P O P P N N O N 2474
   3072 RESULT: P O P P N O N N 2480
   3072 RESULT: P O P P O N N N 2498
  42496 RESULT: P P N N N N P P 2560
   3072 RESULT: P P N N N O O P 2566
   3072 RESULT: P P N N N O P O 2568
  42496 RESULT: P P N N N P N P 2572
   3072 RESULT: P P N N N P O O 2574
  42496 RESULT: P P N N N P P N 2576
   3072 RESULT: P P N N O N O P 2584
   3072 RESULT: P P N N O N P O 2586
   3072 RESULT: P P N N O O N P 2590
  12032 RESULT: P P N N O O O O 2592
   3072 RESULT: P P N N O O P N 2594
   3072 RESULT: P P N N O P N O 2598
   3072 RESULT: P P N N O P O N 2600
  42496 RESULT: P P N N P N N P 2608
   3072 RESULT: P P N N P N O O 2610
  42496 RESULT: P P N N P N P N 2612
   3072 RESULT: P P N N P O N O 2616
   3072 RESULT: P P N N P O O N 2618
  42496 RESULT: P P N N P P N N 2624
   3072 RESULT: P P N O N N O P 2638
   3072 RESULT: P P N O N N P O 2640
   3072 RESULT: P P N O N O N P 2644
  12032 RESULT: P P N O N O O O 2646
   3072 RESULT: P P N O N O P N 2648
   3072 RESULT: P P N O N P N O 2652
   3072 RESULT: P P N O N P O N 2654
   3072 RESULT: P P N O O N N P 2662
  12032 RESULT: P P N O O N O O 2664
   3072 RESULT: P P N O O N P N 2666
  12032 RESULT: P P N O O O N O 2670
  12032 RESULT: P P N O O O O N 2672
   3072 RESULT: P P N O O P N N 2678
   3072 RESULT: P P N O P N N O 2688
   3072 RESULT: P P N O P N O N 2690
   3072 RESULT: P P N O P O N N 2696
  42496 RESULT: P P N P N N N P 2716
   3072 RESULT: P P N P N N O O 2718
  42496 RESULT: P P N P N N P N 2720
   3072 RESULT: P P N P N O N O 2724
   3072 RESULT: P P N P N O O N 2726
  42496 RESULT: P P N P N P N N 2732
   3072 RESULT: P P N P O N N O 2742
   3072 RESULT: P P N P O N O N 2744
   3072 RESULT: P P N P O O N N 2750
  42496 RESULT: P P N P P N N N 2768
   3072 RESULT: P P O N N N O P 2800
   3072 RESULT: P P O N N N P O 2802
   3072 RESULT: P P O N N O N P 2806
  12032 RESULT: P P O N N O O O 2808
   3072 RESULT: P P O N N O P N 2810
   3072 RESULT: P P O N N P N O 2814
   3072 RESULT: P P O N N P O N 2816
   3072 RESULT: P P O N O N N P 2824
  12032 RESULT: P P O N O N O O 2826
   3072 RESULT: P P O N O N P N 2828
  12032 RESULT: P P O N O O N O 2832
  12032 RESULT: P P O N O O O N 2834
   3072 RESULT: P P O N O P N N 2840
   3072 RESULT: P P O N P N N O 2850
   3072 RESULT: P P O N P N O N 2852
   3072 RESULT: P P O N P O N N 2858
   3072 RESULT: P P O O N N N P 2878
  12032 RESULT: P P O O N N O O 2880
   3072 RESULT: P P O O N N P N 2882
  12032 RESULT: P P O O N O N O 2886
  12032 RESULT: P P O O N O O N 2888
   3072 RESULT: P P O O N P N N 2894
  12032 RESULT: P P O O O N N O 2904
  12032 RESULT: P P O O O N O N 2906
  12032 RESULT: P P O O O O N N 2912
   3072 RESULT: P P O O P N N N 2930
   3072 RESULT: P P O P N N N O 2958
   3072 RESULT: P P O P N N O N 2960
   3072 RESULT: P P O P N O N N 2966
   3072 RESULT: P P O P O N N N 2984
  42496 RESULT: P P P N N N N P 3040
   3072 RESULT: P P P N N N O O 3042
  42496 RESULT: P P P N N N P N 3044
   3072 RESULT: P P P N N O N O 3048
   3072 RESULT: P P P N N O O N 3050
  42496 RESULT: P P P N N P N N 3056
   3072 RESULT: P P P N O N N O 3066
   3072 RESULT: P P P N O N O N 3068
   3072 RESULT: P P P N O O N N 3074
  42496 RESULT: P P P N P N N N 3092
   3072 RESULT: P P P O N N N O 3120
   3072 RESULT: P P P O N N O N 3122
   3072 RESULT: P P P O N O N N 3128
   3072 RESULT: P P P O O N N N 3146
  42496 RESULT: P P P P N N N N 3200
1500160 RESULT: P P P P P P P P 3280

В начале каждой строки стоит количество повторений данной последовательности в сгенерированных матрицах.

Ещё можно построить граф какие последовательности с какими взаимно ортогональны...

_________________
:dj: https://mastodon.social/@Shaos


24 Oct 2023 00:14
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Shaos wrote:
Напомню, что строчки в ортонормированной матрице можно переставлять - от этого она не перестанет быть ортонормированной. Вот например нашлась слегка перемешанная матрица Хаара 8x8 как комбинация №1488441:

Image

Сравниваем с матрицей из википедии - очень похоже :roll:

Image
Проверим? В вышеприведённую питоновскую программу вписываем новую матрицу с новыми коэффициентами:
Code:
o8 = 1/math.sqrt(8)
o4 = 1/math.sqrt(4)
o2 = 1/math.sqrt(2)

# Taking a 8 * 8 matrix
A = np.array([[ o8, o8, o8, o8, o8, o8, o8, o8 ],
              [ o8, o8, o8, o8,-o8,-o8,-o8,-o8 ],
              [ o4, o4,-o4,-o4,  0,  0,  0,  0 ],
              [ o2,-o2,  0,  0,  0,  0,  0,  0 ],
              [  0,  0, o2,-o2,  0,  0,  0,  0 ],
              [  0,  0,  0,  0, o4, o4,-o4,-o4 ],
              [  0,  0,  0,  0, o2,-o2,  0,  0 ],
              [  0,  0,  0,  0,  0,  0, o2,-o2 ]])
и смотрим результат :)
Code:
Original matrix:

[[ 0.3536  0.3536  0.3536  0.3536  0.3536  0.3536  0.3536  0.3536]
 [ 0.3536  0.3536  0.3536  0.3536 -0.3536 -0.3536 -0.3536 -0.3536]
 [ 0.5     0.5    -0.5    -0.5     0.      0.      0.      0.    ]
 [ 0.7071 -0.7071  0.      0.      0.      0.      0.      0.    ]
 [ 0.      0.      0.7071 -0.7071  0.      0.      0.      0.    ]
 [ 0.      0.      0.      0.      0.5     0.5    -0.5    -0.5   ]
 [ 0.      0.      0.      0.      0.7071 -0.7071  0.      0.    ]
 [ 0.      0.      0.      0.      0.      0.      0.7071 -0.7071]]


Inverted matrix:

[[ 3.5e-01  3.5e-01  5.0e-01  7.1e-01  0.0e+00  0.0e+00 -3.6e-18 -5.6e-35]
 [ 3.5e-01  3.5e-01  5.0e-01 -7.1e-01  0.0e+00  0.0e+00 -3.6e-18 -5.6e-35]
 [ 3.5e-01  3.5e-01 -5.0e-01 -7.2e-18  7.1e-01  0.0e+00 -3.6e-18 -5.6e-35]
 [ 3.5e-01  3.5e-01 -5.0e-01 -7.2e-18 -7.1e-01 -0.0e+00 -3.6e-18 -5.6e-35]
 [ 3.5e-01 -3.5e-01  0.0e+00  0.0e+00  0.0e+00  5.0e-01  7.1e-01  7.2e-18]
 [ 3.5e-01 -3.5e-01 -0.0e+00 -0.0e+00 -0.0e+00  5.0e-01 -7.1e-01  7.2e-18]
 [ 3.5e-01 -3.5e-01 -0.0e+00 -0.0e+00 -0.0e+00 -5.0e-01 -0.0e+00  7.1e-01]
 [ 3.5e-01 -3.5e-01 -0.0e+00 -0.0e+00 -0.0e+00 -5.0e-01 -0.0e+00 -7.1e-01]]


Inverted again:

[[ 0.4  0.4  0.4  0.4  0.4  0.4  0.4  0.4]
 [ 0.4  0.4  0.4  0.4 -0.4 -0.4 -0.4 -0.4]
 [ 0.5  0.5 -0.5 -0.5 -0.  -0.  -0.  -0. ]
 [ 0.7 -0.7 -0.  -0.  -0.  -0.  -0.  -0. ]
 [-0.  -0.   0.7 -0.7 -0.  -0.  -0.  -0. ]
 [-0.  -0.  -0.  -0.   0.5  0.5 -0.5 -0.5]
 [-0.  -0.  -0.  -0.   0.7 -0.7 -0.  -0. ]
 [-0.  -0.  -0.  -0.  -0.  -0.   0.7 -0.7]]


Difference between them (every element must be close to zero):

[[0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0.]]


Multiplication of original matrix and its transpose (must be identity matrix):

[[ 1.0e+00  3.3e-17 -5.6e-17 -5.6e-17 -5.6e-18 -5.6e-18 -5.6e-18 -5.6e-18]
 [ 3.3e-17  1.0e+00 -5.6e-17 -5.6e-17 -5.6e-18 -5.6e-18 -5.6e-18 -5.6e-18]
 [-5.6e-17 -5.6e-17  1.0e+00  3.3e-17 -5.6e-18 -5.6e-18 -5.6e-18 -5.6e-18]
 [-5.6e-17 -5.6e-17  3.3e-17  1.0e+00 -5.6e-18 -5.6e-18 -5.6e-18 -5.6e-18]
 [-5.6e-18 -5.6e-18 -5.6e-18 -5.6e-18  1.0e+00  3.3e-17 -5.6e-17 -5.6e-17]
 [-5.6e-18 -5.6e-18 -5.6e-18 -5.6e-18  3.3e-17  1.0e+00 -5.6e-17 -5.6e-17]
 [-5.6e-18 -5.6e-18 -5.6e-18 -5.6e-18 -5.6e-17 -5.6e-17  1.0e+00  3.3e-17]
 [-5.6e-18 -5.6e-18 -5.6e-18 -5.6e-18 -5.6e-17 -5.6e-17  3.3e-17  1.0e+00]]


P.S. Вот выдержка из википедии про преобразование Хаара с помощью нормализованной матрицы Хаара на почитать:

Attachment:
Screenshot from 2023-10-24 08-51-07.png
Screenshot from 2023-10-24 08-51-07.png [ 140.01 KiB | Viewed 16866 times ]


Attachment:
Screenshot from 2023-10-24 09-20-04.png
Screenshot from 2023-10-24 09-20-04.png [ 31.62 KiB | Viewed 16864 times ]

_________________
:dj: https://mastodon.social/@Shaos


24 Oct 2023 01:41
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Добавил в программу детектирование Walsh-like матриц, которые имеют паттерн
Code:
+1 +1
+1 -1
и теоретически могут быть развёрнуты на большие разрешения тем же самым способом - из полутора миллионов матриц нашлось 32 (включая самого Уолша), которые надо проверить... вот например:
Code:
RESULTS #1498925
RESULT: +1 +1 +1 +1 +1 +1 +1 +1 +3280 0.3536
RESULT: +1 -1 +1 -1 +1 -1 +1 -1 +1640 0.3536
RESULT: +1  0 -1  0 +1  0 -1  0 +1968 0.5000
RESULT:  0 +1  0 -1  0 +1  0 -1 +656  0.5000
RESULT: +1 +1 +1 +1 -1 -1 -1 -1 +3200 0.3536
RESULT: +1 -1 +1 -1 -1 +1 -1 +1 +1600 0.3536
RESULT: +1  0 -1  0 -1  0 +1  0 +1920 0.5000
RESULT:  0 +1  0 -1  0 -1  0 +1 +640  0.5000
(я тут переставил строчки, чтобы паттерн +1 +1 | +1 -1 проглядывался у четвертин)

Берём питон с нумпаем:
Code:
import math
# Import required package
import numpy as np

o8 = 1/math.sqrt(8)
o6 = 1/math.sqrt(6)
o4 = 1/math.sqrt(4)
o2 = 1/math.sqrt(2)

# Taking a 8 * 8 matrix
A = np.array([[ o8, o8, o8, o8, o8, o8, o8, o8 ],
              [ o8,-o8, o8,-o8, o8,-o8, o8,-o8 ],
              [ o4,  0,-o4,  0, o4,  0,-o4,  0 ],
              [  0, o4,  0,-o4,  0, o4,  0,-o4 ],
              [ o8, o8, o8, o8,-o8,-o8,-o8,-o8 ],
              [ o8,-o8, o8,-o8,-o8, o8,-o8, o8 ],
              [ o4,  0,-o4,  0,-o4,  0, o4,  0 ],
              [  0, o4,  0,-o4,  0,-o4,  0, o4 ]])

np.set_printoptions(precision=5)

V = np.array([1,2,3,4,5,6,7,8]).transpose()

print("\nTransform:\n")
T = np.matmul(A,V)
print(T)
print("\nReconstruct:\n")
print(np.matmul(A.transpose(),T.transpose()))
и получаем:
Code:
Transform:

[12.72792 -1.41421 -2.      -2.      -5.65685  0.       0.       0.     ]

Reconstruct:

[1. 2. 3. 4. 5. 6. 7. 8.]
Ну т.е. работает :)
Теперь увеличим матрицу до 16х16 - получилось :)
Code:
import math
# Import required package
import numpy as np

np.set_printoptions(precision=4)

o16 = 1/math.sqrt(16)
o8 = 1/math.sqrt(8)
o6 = 1/math.sqrt(6)
o4 = 1/math.sqrt(4)
o2 = 1/math.sqrt(2)

# Taking a 16 * 16 matrix
A = np.array([[ o16, o16, o16, o16, o16, o16, o16, o16, o16, o16, o16, o16, o16, o16, o16, o16, ],
              [ o16,-o16, o16,-o16, o16,-o16, o16,-o16, o16,-o16, o16,-o16, o16,-o16, o16,-o16, ],
              [ o8,  0,-o8,  0, o8,  0,-o8,  0, o8,  0,-o8,  0, o8,  0,-o8,  0 ],
              [  0, o8,  0,-o8,  0, o8,  0,-o8,  0, o8,  0,-o8,  0, o8,  0,-o8 ],
              [ o16, o16, o16, o16,-o16,-o16,-o16,-o16, o16, o16, o16, o16,-o16,-o16,-o16,-o16 ],
              [ o16,-o16, o16,-o16,-o16, o16,-o16, o16, o16,-o16, o16,-o16,-o16, o16,-o16, o16 ],
              [ o8,  0,-o8,  0,-o8,  0, o8,  0, o8,  0,-o8,  0,-o8,  0, o8,  0 ],
              [  0, o8,  0,-o8,  0,-o8,  0, o8,  0, o8,  0,-o8,  0,-o8,  0, o8 ],
              [ o16, o16, o16, o16, o16, o16, o16, o16,-o16,-o16,-o16,-o16,-o16,-o16,-o16,-o16, ],
              [ o16,-o16, o16,-o16, o16,-o16, o16,-o16,-o16, o16,-o16, o16,-o16, o16,-o16, o16, ],
              [ o8,  0,-o8,  0, o8,  0,-o8,  0,-o8,  0, o8,  0,-o8,  0, o8,  0 ],
              [  0, o8,  0,-o8,  0, o8,  0,-o8,  0,-o8,  0, o8,  0,-o8,  0, o8 ],
              [ o16, o16, o16, o16,-o16,-o16,-o16,-o16,-o16,-o16,-o16,-o16, o16, o16, o16, o16 ],
              [ o16,-o16, o16,-o16,-o16, o16,-o16, o16,-o16, o16,-o16, o16, o16,-o16, o16,-o16 ],
              [ o8,  0,-o8,  0,-o8,  0, o8,  0,-o8,  0, o8,  0, o8,  0,-o8,  0 ],
              [  0, o8,  0,-o8,  0,-o8,  0, o8,  0,-o8,  0, o8,  0, o8,  0,-o8 ]
             ])

np.set_printoptions(precision=5)

V = np.array([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]).transpose()

print("\nTransform:\n")
T = np.matmul(A,V)
print(T)
print("\nReconstruct:\n")
print(np.matmul(A.transpose(),T.transpose()))

выводит
Code:
Transform:

[ 3.40000e+01 -2.00000e+00 -2.82843e+00 -2.82843e+00 -8.00000e+00
  0.00000e+00  0.00000e+00  0.00000e+00 -1.60000e+01  0.00000e+00
  0.00000e+00  0.00000e+00  0.00000e+00  0.00000e+00 -4.44089e-16
  4.44089e-16]

Reconstruct:

[ 1.  2.  3.  4.  5.  6.  7.  8.  9. 10. 11. 12. 13. 14. 15. 16.]


P.S. А теперь надо проверить можно ли вообще любую ортогональную матрицу расширить по такому паттерну:
Code:
+1 +1
+1 -1

P.P.S. Проверил - похоже таки любую :roll:

P.P.P.S. И похоже Уолш единственная из таких матриц, которая диагонально-симметрична, т.е. она сама равна транспонированной и одновременно инверсной версии самой себя:
Code:
RESULTS #1500160 (Classic Walsh) <symmetric>
RESULT: +1 +1 +1 +1 +1 +1 +1 +1 +3280 0.3536
RESULT: +1 -1 +1 -1 +1 -1 +1 -1 +1640 0.3536
RESULT: +1 +1 -1 -1 +1 +1 -1 -1 +2624 0.3536
RESULT: +1 -1 -1 +1 +1 -1 -1 +1 +1312 0.3536
RESULT: +1 +1 +1 +1 -1 -1 -1 -1 +3200 0.3536
RESULT: +1 -1 +1 -1 -1 +1 -1 +1 +1600 0.3536
RESULT: +1 +1 -1 -1 -1 -1 +1 +1 +2560 0.3536
RESULT: +1 -1 -1 +1 -1 +1 +1 -1 +1280 0.3536

_________________
:dj: https://mastodon.social/@Shaos


24 Oct 2023 21:05
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Можно поиграться с разными троичными ортонормированными базисами и посмотреть какие варианты визуально более удобоваримые для человеческого глаза - типа сделать веб-сайт, на котором у народа спрашивать какая картинка из двух лучше много-много раз попарно сравнивая разные картинки:



примешивая туда оригинальные изображения и другие варианты сжатия с потерями типа JPEG с разными значениями параметра качества и строя затем список в порядке убывания предпочтений и далее выбирая вариант, который сильнее всего сжимает с меньшей потерей качества.

Причём придётся предусмотреть систему скрытого наказания хулиганов, которые спецом будут выбирать лучшим худший вариант - т.е. типа если голосование чела явно идёт в разрез со среднестатистическими показателями (и с оглядкой на средне-квадратичные отклонения), то его голоса надо отбрасывать как недобросовестные (при этом ничего человеку не показывая, чтобы он думал, что всё ок и его пранк "удался")...

_________________
:dj: https://mastodon.social/@Shaos


27 Oct 2023 10:08
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
В своей дипломной работе 1996 года (см. тут) я сжимал изображения с использованием двумерного спектра Уолша (64x64 для картинок в градациях серого 64х64 где каждый пиксел принимал значения от 0 до 63):



сохраняя его в файл побитно следующим образом:
  • Пользователь спрашивался сколько бит на отсчёт надо использовать для кодирования - выбиралось значение от 4 до 12 (это с учётом бита знака);
  • Отсчёты [0][0], [0][1] и [1][0] сохранялись отдельно в заголовке как целые 14-битные числа (т.к. они обычно сильно больше остальных отсчётов);
  • Параметры квантования (количество битов и шаг с точностью до десятых долей) также сохранялись в заголовке;
  • Остальные отсчёты квантовались от нуля до абсолютного максимума в пределах этого спектра (без учёта вышеупомянутых трёх отсчётов) и сохранялись в указанном количестве битов (с битом знака идущим первым), однако код 100...00 (минус ноль) использовался как маркер последовательности квантованных нулей - если такой маркер встречался в последовательности, то за ним шло 6-битное количество нулей которые надо вставить при вычитке этой строки спектра (таким способом я кодировал 3 и больше нулей идущих подряд).

Можно к этому всему добавить возможность выбирать произвольный ортогональный базис (один из 1500160), сохранять произвольное разрешение (а не только 64x64) с выбором размера кодируемых квадратов (8х8, 16х16, 32х32, 64х64, 128х128, 256х256, 512х512 или 1024х1024), разрешить обрабатывать 3 канала RGB (в дополнение к одному каналу в градациях серого), наложить поверх кодирование по Хаффману (троичное) и можно выкатывать новый универсальный графический формат, причём ТРОИЧНЫЙ :lol:

P.S. Для двоичных систем можно сохранять троичные сжатые данные в последовательности байтов - в каждой паре байтов (16 битов) можно сохранять 10 тритов, представляя их как число в диапазоне от -29524 до +29524, правда это приведёт к пустой растрате примерно 1% от общего объёма файла.

P.P.S. На самом деле использование 8 битов (1 байт) для хранения 5 тритов (представляемых как число в диапазоне -121..+121) даёт ровно такие же потери, но сильно упрощает процесс конвертации туда-обратно. А если надо минимизировать потери при сконвертированном представлении, то можно взять:
17 тритов в 27 битов - потеря 0.21%
29 тритов в 46 битов - потеря 0.08%
41 трит в 65 битов - потеря 0.03%
94 трита в 149 битов - потеря 0.01%
и т.д. но из кратных 8 битам похоже 5 трит самое лучшее (потеря 0.94%), а следующее кратное байту более оптимальное число уже далеко - 111 тритов в 176 битов (22 байта) - 0.04%

_________________
:dj: https://mastodon.social/@Shaos


28 Oct 2023 00:20
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
В качестве расширения для таких файлов можно взять скажем слово .tonic (Ternary OrthoNormal Image Compression) :mrgreen:

Возможный формат TONIC-файлов, которые будут являться последовательностями тритов (кодируемых по 10 тритов на каждые 2 байта либо 5 тритов на каждый 1 байт - пока не решил, что лучше):

- первые 2 байта (16-битное слово в сетевом порядке "big endian") это сигнатура #544F (TO) или 21583, что есть 10 тритов POPONNPPOP (если мы сохраняем триты десятками):
Attachment:
Screenshot from 2023-10-28 03-20-09.png
Screenshot from 2023-10-28 03-20-09.png [ 10.17 KiB | Viewed 16641 times ]
(если же мы будем сохранять 5 трит на байт, то это будут байты 84 'T' POOPO и 79 'O' POONP)

- далее 2 трита - количество каналов (или маркер экспериментальной версии):
Code:
  NN = -4 четыре канала YUVA (задел на будущее);
  NO = -3 три канала YUV (задел на будущее);
  NP = -2 экспериментальный формат для хранения одного 2D спектра со сжатием троичным Хаффманом;
  ON = -1 экспериментальный формат для хранения одного 2D спектра со сжатием нулей после квантования;
  OO = 0 экспериментальный "помехозащищённый" формат для хранения одного 2D спектра без сжатия (только квантование);
  OP = 1 канал (изображение в градациях серого);
  PN = 2 канала (стереоскопическое изображение для красно-зелёных очков);
  PO = 3 канала (RGB - полноцветное изображение);
  PP = 4 канала (RGBA - полноцветное изображение с альфа-каналом).

- далее 14 тритов задают номер ортонормированной матрицы (для всех каналов) от 0 до 1500160 (PONPPPNONPPPPP):
Attachment:
Screenshot from 2023-10-28 03-25-07.png
Screenshot from 2023-10-28 03-25-07.png [ 10.37 KiB | Viewed 16641 times ]

- далее 2-мя тритами задаётся размер квадратов для кодирования спектра (выбранный размер будет использоваться для всех каналов в этом файле):
Code:
  NN => 8x8
  NO => 16x16
  NP => 32x32
  ON => 64x64
  OO => 128x128
  OP => 256x256
  PN => 512x512
  PO => 1024x1024
  PP => 2048x2048 (пусть тоже будет как 9-й вариант)

- затем надо указать размер изображения в пикселах для чего сначала мы указываем в 2 тритах сколько тритов будут использоваться для задания размера (со смещением получается от 3 до 10 плюс специальный случай, когда размер картинки равен размеру квадрата кодирования):
Code:
  NN => 0 (размер отдельно не задаётся и определяется размером квадрата, заданным выше)
  NO => 3 (max 13x13)
  NP => 4 (max 40x40)
  ON => 5 (max 121x121)
  OO => 6 (max 364x364)
  OP => 7 (max 1093x1093)
  PN => 8 (max 3280x3280)
  PO => 9 (max 9841x9841)
  PP => 10 (max 29524x29524)
и далее 2 раза по столько тритов для задания размеров изображения по горизонтали и по вертикали - получается, что в пределе размер изображения может быть 29524x29524 (можно отрицательные размеры тоже поддержать - они могут означать перевёрнутую систему координат по иксу и по игреку);

- затем идут описатели каналов, в которых указываются параметры квантования спектра (они будут разные для разных каналов - например зелёный канал может быть чуть точнее остальных, а если есть альфа-канал, то в нём должен быть железобетонный ноль и железобетонная единица) и последовательность индексов квадратов (чтобы была поддержка повторяющихся тайлов);

- далее будут располагаться таблицы троичного Хаффмана в каком-то компактном формате (теоретически каждый квадрат может иметь свою таблицу Хаффмана);

- и далее сами квадраты в виде сжатых троичным Хаффманом квантованных отсчётов (для каждого квадрата указывается индекс выбранной таблицы Хаффмана, которая вообще может быть одна на весь файл).

P.S. 10-тритное хранение заголовка подразумевает возможность "упрощённого" его формирования в двоичной программе:
- первые 2 байта - сигнатура TO (#544F);
- следующие 4 байта - хардкод заренее известного формата (например 1 канал, матрица Уолша, размер квадратов 16x16, длина размера 10 тритов - #21AB #D94F);
- следующие 2 байта - ширина картинки в пикселах (используются все 10 тритов поэтому число пишется как есть);
- следующие 2 байта - высота картинки в пикселах (используются все 10 тритов поэтому число пишется как есть);
- далее данные каналов и квадратов.
Если же хранить 5 тритов на байт, то упрощённо можно будет лишь сохранять размеры до 121х121, что несколько неудобно...

P.P.S. На следующее утро добавил в описание ещё упрощенных форматов, с которых можно начать: OO (.tonic0), ON (.tonic1) и NP (.tonic2).
Причём .tonic0 будет "помехозащищённым" с трёхкратным повторением заголовка :dj:
Это я хочу поэкспериментировать с единичными и двойными ошибками, а также обрезанием файла где-то посередине :egeek:
А после обкатки троичного Хаффмана в .tonic2 будет понятно стоит вообще игра свеч или нет, а то хотелось бы потягаться со старым-добрым жыпегом :kruto:

_________________
:dj: https://mastodon.social/@Shaos


28 Oct 2023 04:02
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Shaos wrote:
В своей дипломной работе 1996 года (см. тут) я сжимал изображения с использованием двумерного спектра Уолша (64x64 для картинок в градациях серого 64х64 где каждый пиксел принимал значения от 0 до 63):



сохраняя его в файл побитно следующим образом:
  • Пользователь спрашивался сколько бит на отсчёт надо использовать для кодирования - выбиралось значение от 4 до 12 (это с учётом бита знака);
  • Отсчёты [0][0], [0][1] и [1][0] сохранялись отдельно в заголовке как целые 14-битные числа (т.к. они обычно сильно больше остальных отсчётов);
  • Параметры квантования (количество битов и шаг с точностью до десятых долей) также сохранялись в заголовке;
  • Остальные отсчёты квантовались от нуля до абсолютного максимума в пределах этого спектра (без учёта вышеупомянутых трёх отсчётов) и сохранялись в указанном количестве битов (с битом знака идущим первым), однако код 100...00 (минус ноль) использовался как маркер последовательности квантованных нулей - если такой маркер встречался в последовательности, то за ним шло 6-битное количество нулей которые надо вставить при вычитке этой строки спектра (таким способом я кодировал 3 и больше нулей идущих подряд).

Починил класс побитного чтения ( я там забыл copy constructor объявить ; ) и мой дипломный проект перестал падать на восстановлении картинки сжатой по Уолшу :)

Вот пример ELAINE (правда уменьшенный до 64х64) закодированный Уолшем с разным количеством битов на отсчёт:

4 бита:
Attachment:
elaine04.png
elaine04.png [ 9.03 KiB | Viewed 16467 times ]

5 битов:
Attachment:
elaine05.png
elaine05.png [ 9.58 KiB | Viewed 16467 times ]

6 битов:
Attachment:
elaine06.png
elaine06.png [ 9.43 KiB | Viewed 16467 times ]

7 битов:
Attachment:
elaine07.png
elaine07.png [ 9.22 KiB | Viewed 16467 times ]

8 битов:
Attachment:
elaine08.png
elaine08.png [ 9.05 KiB | Viewed 16467 times ]

9 битов:
Attachment:
elaine09.png
elaine09.png [ 8.85 KiB | Viewed 16467 times ]

10 битов:
Attachment:
elaine10.png
elaine10.png [ 8.8 KiB | Viewed 16467 times ]

11 битов:
Attachment:
elaine11.png
elaine11.png [ 8.84 KiB | Viewed 16467 times ]

12 битов:
Attachment:
elaine12.png
elaine12.png [ 8.78 KiB | Viewed 16467 times ]

Посередине в процентах указано среднее квадратичное отклонение от оригинала (который слева), а слева внизу коэффициент сжатия (если меньше 1, то файл наоборот увеличился). Как можно видеть после 8 бит ошибка стала увеличиваться, а картинка - высветляться. Скорее всего дело в недостаточной точности, т.к. я шаг квантования сохранял только с точностью до десятых долей, а тут надо бы поточнее - с другой стороны файл стал расти в размерах и смысла в таком сжатии при большой битности нету.

Вот ещё прошёлся архиватором, чтобы поглядеть есть ли возможность ещё поджать алгоритмами типа Хаффмана после квантования и отбрасывания нулевых отсчётов:
Code:
Archive:  ELAINE.ZIP
 Length   Method    Size  Cmpr    Date    Time   CRC-32   Name
--------  ------  ------- ---- ---------- ----- --------  ----
     346  Defl:X      312  10% 2023-10-30 18:24 5a44d98b  ELAINE04.IC1
    1047  Defl:X      846  19% 2023-10-30 20:22 91252845  ELAINE05.IC1
    2332  Defl:X     1503  36% 2023-10-30 20:22 a959397d  ELAINE06.IC1
    3440  Defl:X     2300  33% 2023-10-30 20:24 21bbab9a  ELAINE07.IC1
    4096  Defl:X     2564  37% 2023-10-30 20:25 4b37a93a  ELAINE08.IC1
    4607  Defl:X     3466  25% 2023-10-30 20:25 fd8fa7c0  ELAINE09.IC1
    5118  Defl:X     3521  31% 2023-10-30 20:26 3c8db06a  ELAINE10.IC1
    5628  Defl:X     3954  30% 2023-10-30 20:37 5f7262fb  ELAINE11.IC1
    6139  Defl:X     3859  37% 2023-10-30 20:38 0ad346a0  ELAINE12.IC1
--------          -------  ---                            -------
   32753            22325  32%                            9 files

Размер оригинального файла (6 бит на точку) составляет 3076 байт, получается с архивированием коэффициенты сжатия такие:
Code:
4 бита: K=9.9
5 бит: K=3.6
6 бит: K=2.0
7 бит: K=1.3
8 бит: K=1.2
Пока на скорую руку подсчитал коды обычного двоичного Хаффмана пользуясь статистикой от 8-битного варианта ELAINE:
 Huffman
Code:
FRQ S ABS SAMPL HUFFMAN
709 1 1  -2    :111
693 0 1  2     :110
442 0 2  4     :011
412 1 2  -4    :001
322 0 0  0     :000
270 1 3  -6    :1010
255 0 3  6     :1000
155 0 4  8     :10111
140 1 4  -8    :10011
104 0 5  10    :01010
 95 1 5  -10   :01000
 67 0 6  11    :101100
 61 1 6  -11   :010111
 36 0 7  13    :1011010
 33 1 7  -13   :1001011
 30 1 9  -17   :0101100
 25 0 9  17    :0100110
 24 0 8  15    :0100101
 21 1 8  -15   :10110111
 16 1 11 -21   :10010010
 16 1 10 -19   :10010001
 16 0 12 23    :10010000
 16 0 10 19    :01011011
 13 1 12 -23   :01001110
  9 0 13 25    :101101101
  8 0 15 29    :100100110
  7 1 14 -27   :010110100
  7 1 13 -25   :010011111
  7 0 11 21    :010011110
  6 1 15 -29   :010010010
  5 1 17 -32   :010010001
  5 0 14 27    :010010000
  4 1 27 -51   :1001001111
  4 1 20 -38   :1001001110
  4 0 18 34    :0101101011
  3 1 34 -65   :0101101010
  3 0 27 51    :0100100111
  3 0 17 32    :0100100110
  2 1 25 -48   :10010101010
  2 1 23 -44   :10010101001
  2 1 21 -40   :10010101000
  2 1 19 -36   :10010100111
  2 1 16 -30   :10010100110
  2 1 0  3zeros:10010100101
  2 0 38 72    :10010100100
  2 0 32 61    :10010100011
  2 0 25 48    :10010100010
  2 0 24 46    :10010100001
  2 0 22 42    :10010100000
  1 1 36 -68   :101101100111
  1 1 33 -63   :101101100110
  1 1 31 -59   :101101100101
  1 1 30 -57   :101101100100
  1 1 0  4zeros:101101100011
  1 0 96 182   :101101100010
  1 0 48 91    :101101100001
  1 0 44 84    :101101100000
  1 0 41 78    :100101011111
  1 0 39 74    :100101011110
  1 0 33 63    :100101011101
  1 0 30 57    :100101011100
  1 0 29 55    :100101011011
  1 0 28 53    :100101011010
  1 0 23 44    :100101011001
  1 0 21 40    :100101011000
  1 0 16 30    :100101010111
  1 0 127 241  :100101010110
Ориентировочно получилось 2119 байт с таблицей, что даёт коэффициент сжатия K=1.45 и это вполне себе соотносится с JPEG:


Attachments:
Screenshot from 2023-10-30 21-40-39.png
Screenshot from 2023-10-30 21-40-39.png [ 199.43 KiB | Viewed 16464 times ]

_________________
:dj: https://mastodon.social/@Shaos
30 Oct 2023 21:11
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Непосредственно сравнивать преобразование Уолша и косинусное преобразование (DCT на котором построен JPEG) несколько проблематично, т.к. Walsh имеет совсем другие артефакты - просто шум, который по мне так приятнее, чем квадраты пережатого JPEG :mrgreen:


Attachments:
IC1vsJPEG.jpg
IC1vsJPEG.jpg [ 362.78 KiB | Viewed 16464 times ]

_________________
:dj: https://mastodon.social/@Shaos
30 Oct 2023 22:14
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Shaos wrote:
Пока на скорую руку подсчитал коды обычного двоичного Хаффмана пользуясь статистикой от 8-битного варианта ELAINE:
 Huffman
Code:
FRQ S ABS SAMPL HUFFMAN
709 1 1  -2    :111
693 0 1  2     :110
442 0 2  4     :011
412 1 2  -4    :001
322 0 0  0     :000
270 1 3  -6    :1010
255 0 3  6     :1000
155 0 4  8     :10111
140 1 4  -8    :10011
104 0 5  10    :01010
 95 1 5  -10   :01000
 67 0 6  11    :101100
 61 1 6  -11   :010111
 36 0 7  13    :1011010
 33 1 7  -13   :1001011
 30 1 9  -17   :0101100
 25 0 9  17    :0100110
 24 0 8  15    :0100101
 21 1 8  -15   :10110111
 16 1 11 -21   :10010010
 16 1 10 -19   :10010001
 16 0 12 23    :10010000
 16 0 10 19    :01011011
 13 1 12 -23   :01001110
  9 0 13 25    :101101101
  8 0 15 29    :100100110
  7 1 14 -27   :010110100
  7 1 13 -25   :010011111
  7 0 11 21    :010011110
  6 1 15 -29   :010010010
  5 1 17 -32   :010010001
  5 0 14 27    :010010000
  4 1 27 -51   :1001001111
  4 1 20 -38   :1001001110
  4 0 18 34    :0101101011
  3 1 34 -65   :0101101010
  3 0 27 51    :0100100111
  3 0 17 32    :0100100110
  2 1 25 -48   :10010101010
  2 1 23 -44   :10010101001
  2 1 21 -40   :10010101000
  2 1 19 -36   :10010100111
  2 1 16 -30   :10010100110
  2 1 0  3zeros:10010100101
  2 0 38 72    :10010100100
  2 0 32 61    :10010100011
  2 0 25 48    :10010100010
  2 0 24 46    :10010100001
  2 0 22 42    :10010100000
  1 1 36 -68   :101101100111
  1 1 33 -63   :101101100110
  1 1 31 -59   :101101100101
  1 1 30 -57   :101101100100
  1 1 0  4zeros:101101100011
  1 0 96 182   :101101100010
  1 0 48 91    :101101100001
  1 0 44 84    :101101100000
  1 0 41 78    :100101011111
  1 0 39 74    :100101011110
  1 0 33 63    :100101011101
  1 0 30 57    :100101011100
  1 0 29 55    :100101011011
  1 0 28 53    :100101011010
  1 0 23 44    :100101011001
  1 0 21 40    :100101011000
  1 0 16 30    :100101010111
  1 0 127 241  :100101010110
Ориентировочно получилось 2119 байт с таблицей, что даёт коэффициент сжатия K=1.45 и это вполне себе соотносится с JPEG

А теперь внимание вопрос - стоит ли выпускать озвученного выше двоичного Уолша-Хаффмана в публичный свет (обработав напильником то, что у меня уже было с 1996 года) или сразу заняться троичным форматом TONIC? С другой стороны будет с чем TONIC сравнивать при прочих равных...

_________________
:dj: https://mastodon.social/@Shaos


31 Oct 2023 01:46
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Ок - релизу моей урезанно-расширенной дипломной работы в опенсорц БЫТЬ :rotate:

(урезанной потому что выкинуты лишние методы сжатия и расширенной потому что добавлен хаффман)

Image

P.S. Зарелизил сырцы "Walsh Explorer" 11 ноября 2023 года под лицензией MIT:

https://gitlab.com/shaos/graphin/-/tree/main/WALSHEXP

(собранный EXE с примерами там тоже имеется)

_________________
:dj: https://mastodon.social/@Shaos


31 Oct 2023 23:54
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Ещё есть такой WebP формат, созданный гуглом в 2010 году на основе видеокодека VP8 (и потом они отдельно додумали вариант сжатия без потерь). Там тоже есть Хаффман как вариант (но основной таки DCT), поддерживается альфа-канал (которого нету в JPEG и который я хочу добавить в TONIC), размер картинки до 16384х16384 и заявлено лучшее сжатие, чем JPEG при сравнимом качестве:

https://en.wikipedia.org/wiki/WebP

Формат уже поддерживается практически всеми браузерами, есть в GIMP (начиная с версии 2.10) и имеет либы в дебияне, распространяясь под лицензией BSD. Однако исследователи говорят, то картинки WebP выглядят "замыленными" т.к. алгоритм упирает на математические измерения погрешности сжатия (PSNR) игнорируя психо-визуальный аспект...

_________________
:dj: https://mastodon.social/@Shaos


04 Nov 2023 12:53
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Всё это время начиная с 24 октября до сегодня (т.е. в течении примерно 26 суток), гонял полный перебор на матрицу 9х9 - вдруг думаю найдутся какие-то чисто троичные матрицы, которые не только из -1,0,+1 состоят, но и имеют сторону кратную 3? ан нет - нифига:
Code:
...
   1   1   1   0   0   -1   -1   -1   0   <= ADD 1
   1   1   1   0   0   -1   -1   -1   0   <= DEL 1 (9438) 0 3129 883008 31191552 177024960 235509120 110154240 13501440 0
   1   1   1   0   0   -1   -1   0   -1   <= ADD 1
   1   1   1   0   0   -1   -1   0   -1   <= DEL 1 (9440) 0 3130 883008 31191552 177024960 235509120 110154240 13501440 0
   1   1   1   0   0   -1   0   -1   -1   <= ADD 1
   1   1   1   0   0   -1   0   -1   -1   <= DEL 1 (9446) 0 3131 883008 31191552 177024960 235509120 110154240 13501440 0
   1   1   1   0   0   0   -1   -1   -1   <= ADD 1
   1   1   1   0   0   0   -1   -1   -1   <= DEL 1 (9464) 0 3132 883008 31191552 177024960 235509120 110154240 13501440 0
   1   1   1   0   1   -1   -1   -1   -1   <= ADD 1
   1   1   1   0   1   -1   -1   -1   -1   <= DEL 1 (9518) 0 3133 883008 31191552 177024960 235509120 110154240 13501440 0
   1   1   1   1   -1   -1   -1   -1   0   <= ADD 1
   1   1   1   1   -1   -1   -1   -1   0   <= DEL 1 (9600) 0 3134 883008 31191552 177024960 235509120 110154240 13501440 0
   1   1   1   1   -1   -1   -1   0   -1   <= ADD 1
   1   1   1   1   -1   -1   -1   0   -1   <= DEL 1 (9602) 0 3135 883008 31191552 177024960 235509120 110154240 13501440 0
   1   1   1   1   -1   -1   0   -1   -1   <= ADD 1
   1   1   1   1   -1   -1   0   -1   -1   <= DEL 1 (9608) 0 3136 883008 31191552 177024960 235509120 110154240 13501440 0
   1   1   1   1   -1   0   -1   -1   -1   <= ADD 1
   1   1   1   1   -1   0   -1   -1   -1   <= DEL 1 (9626) 0 3137 883008 31191552 177024960 235509120 110154240 13501440 0
   1   1   1   1   0   -1   -1   -1   -1   <= ADD 1
   1   1   1   1   0   -1   -1   -1   -1   <= DEL 1 (9680) 0 3138 883008 31191552 177024960 235509120 110154240 13501440 0
NO MORE RESULTS!
комбинации ортогональных строк всегда не более 8 получались - девятую строку, которая была бы ортогональна предыдущим 8 найти полным перебором так и не удалось и это значит, что таковых комбинаций не существует...

_________________
:dj: https://mastodon.social/@Shaos


19 Nov 2023 14:00
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Ещё в мастадонте мне написали, что есть такое преобразование Хартли, которое активно исследовалось с 80е-90е:

Attachment:
Hartley.png
Hartley.png [ 47.41 KiB | Viewed 15735 times ]

Тут кроме -1,0 и +1 ещё и корень из 2 затесался...

_________________
:dj: https://mastodon.social/@Shaos


19 Nov 2023 14:03
Profile WWW
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Опять таки в мастодонте мне подбросили видосик про основополагающие концепции сжатия изображений и видео:


_________________
:dj: https://mastodon.social/@Shaos


17 Dec 2023 00:40
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 15 posts ] 

Who is online

Users browsing this forum: No registered users and 15 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software.