ordered_to7.lua

-- bayer4_to7.lua : converts an image into TO7
-- mode for thomson machines (MO/TO)
--
-- Version: 08-jan-2024
--
-- Copyright 2024 by Samuel Devulder
--
-- This program is free software; you can redistribute
-- it and/or modify it under the terms of the GNU
-- General Public License as published by the Free
-- Software Foundation; version 2 of the License.
-- See <http://www.gnu.org/licenses/>

local DITHER_BAYER1   = 1
local DITHER_BAYER2   = 2
local DITHER_BAYER4   = 3
local DITHER_BAYER8   = 4
local DITHER_BAYER16  = 5

local DITHER_H2x2O    = 6
local DITHER_H4x4O    = 7
local DITHER_H8x8O    = 8

local DITHER_H4x4A    = 9
local DITHER_H8x8A    = 10

local DITHER_VAC4     = 11
local DITHER_VAC8     = 12
local DITHER_VAC16    = 13
local DITHER_VAC32    = 14
local DITHER_VAC64    = 15

-- ====================================
local DITHER = DITHER_H8x8A
DITHER = DITHER_H4x4O
-- DITHER = DITHER_VAC8
-- DITHER = DITHER_BAYER8
-- ====================================
local MAXCOL      = 8		
local MONOCHROME  = false
local CENTERED    = true
local ENHANCE_LUM = false
local ERR_PROPAG  = 0.3333
local ZIGZAG      = 0

pcall(function() require('lib/cmdline') end)
run("lib/color.lua") --Color.NORMALIZE=0
run("lib/thomson.lua")
run("lib/bayer.lua")

-- redefined to have -0.5 <= value < 0.5
function bayer.norm(matrix)
	local m,n=#matrix,#matrix[1]
	local max,ret = 0,{}
	for j=1,m do
		for i=1,n do
			max = math.max(max,matrix[j][i])
		end
	end
	-- max=max+1
	for j=1,m do
		ret[j] = {}
		for i=1,n do
			ret[j][i]=(matrix[j][i]-(max+1)/2)/max
		end
	end
	return ret
end

-- ordered dither matrix
local dither={{1}}
if DITHER<=DITHER_BAYER16 then for i=DITHER_BAYER2,DITHER do dither=bayer.double(dither) end end

if DITHER==DITHER_H2x2O then
	dither = {
		{ 1, 4},
		{ 2, 3}
	}
end

if DITHER==DITHER_H4x4O then
	dither = {
		{ 7,13,11, 4},
		{12,16,14, 8},
		{10,15, 6, 2},
		{ 5, 9, 3, 1} 
	}
end

if DITHER==DITHER_H8x8O then
	dither = {
		{ 7,21,33,43,36,19, 9, 4},
		{16,27,51,55,49,29,14,11},
		{31,47,57,61,59,45,35,23},
		{41,53,60,64,62,52,40,38},
		{37,44,58,63,56,46,30,22},
		{15,28,48,54,50,26,17,10},
		{ 8,18,34,42,32,20, 6, 2},
		{ 5,13,25,39,24,12, 3, 1}
	}
end

if DITHER==DITHER_H4x4A then
	dither = {
		{ 4, 2, 7, 5},
		{ 3, 1, 8, 6},
		{ 7, 5, 4, 2},
		{ 8, 6, 3, 1} 
	}
end

if DITHER==DITHER_H8x8A then
	dither = {
		{13, 7, 8,14,17,21,22,18},
		{ 6, 1, 3, 9,28,31,29,23},
		{ 5, 2, 4,10,27,32,30,24},
		{16,12,11,15,20,26,25,19},
		{17,21,22,18,13, 7, 8,14},
		{28,31,29,23, 6, 1, 3, 9},
		{27,32,30,24, 5, 2, 4,10},
		{20,26,25,19,16,12,11,15}
	}
end

if DITHER==DITHER_VAC4 then
	dither = {
		{1,9,3,11},
		{13,5,15,7},
		{4,12,2,10},
		{16,8,14,6}
	}
end
if DITHER==DITHER_VAC8 then
-- 15,48,24,42,28,49,37,10,30,5,51,9,57,1,23,54,40,20,58,14,32,47,8,62,3,44,35,26,41,18,34,27,50,17,7,63,2,52,59,13,38,53,29,46,22,11,43,25,0,21,12,55,39,31,6,56,33,60,36,4,16,61,19,45
	dither = {
		{40,61,2,39,19,43,23,8},
		{12,20,32,49,58,13,51,56},
		{29,46,53,9,27,33,1,36},
		{60,5,24,42,17,62,45,18},
		{41,15,63,37,4,54,10,25},
		{57,7,30,50,21,28,38,52},
		{22,35,44,11,59,47,14,3},
		{48,16,55,26,6,34,64,31}
	}
end
if DITHER==DITHER_VAC16 then
	dither = {
		{138,202,50,105,24,84,10,99,33,166,102,222,43,245,100,180},
		{250,8,154,232,212,179,201,118,230,135,58,181,142,15,123,59},
		{220,80,127,34,66,137,56,159,78,190,7,239,75,214,192,36},
		{167,111,197,172,98,227,20,248,29,215,95,161,112,27,156,96},
		{237,23,53,255,12,121,194,107,147,45,129,204,52,253,133,63},
		{187,145,208,77,153,177,48,82,171,234,69,13,178,87,216,2},
		{83,40,130,106,217,32,238,206,3,116,188,242,144,39,163,115},
		{246,169,226,6,64,143,94,131,60,219,89,25,109,228,67,200},
		{28,55,90,162,195,247,22,185,158,35,141,168,54,182,14,140},
		{110,189,233,124,38,114,74,224,101,256,71,203,236,126,97,218},
		{73,146,17,81,176,213,148,46,16,191,117,9,85,41,249,160},
		{211,44,254,198,57,18,243,170,128,62,164,223,152,196,61,11},
		{184,134,103,155,93,136,108,79,235,210,37,104,26,132,175,92},
		{30,65,225,1,205,229,31,193,5,91,139,251,70,231,113,221},
		{240,119,165,42,72,174,49,120,151,183,51,199,173,4,47,150},
		{21,88,186,244,125,149,252,209,68,241,19,122,86,157,207,76}
	}
end
if DITHER==DITHER_VAC32 then
	dither = {
		{392,985,503,140,452,709,180,387,952,122,855,52,679,135,972,293,386,760,35,225,853,419,1006,353,925,415,718,492,115,969,175,737},
		{823,2,617,888,75,541,1016,48,495,707,416,304,882,606,439,827,96,1019,567,335,512,635,25,539,656,77,590,916,373,626,889,259},
		{570,191,695,252,808,332,625,783,287,603,207,981,519,236,63,671,499,265,893,720,87,804,244,843,169,879,264,16,784,514,57,455},
		{322,922,475,382,937,167,431,872,91,914,743,3,802,379,938,740,199,628,407,159,968,377,703,474,321,749,454,984,299,162,714,1012},
		{125,782,70,744,592,21,730,223,524,369,165,449,652,142,547,338,870,109,822,487,598,189,915,46,997,572,112,681,552,842,389,607},
		{865,527,216,974,291,502,956,323,643,989,576,858,297,1004,789,33,456,945,320,5,792,288,536,663,395,226,814,368,202,960,90,253},
		{687,361,638,445,147,834,668,66,790,120,240,721,76,484,206,685,586,172,754,633,1005,432,78,884,151,735,923,64,480,646,765,465},
		{160,1002,36,881,712,375,198,458,898,399,505,933,362,610,904,283,975,397,520,250,132,698,821,315,622,448,278,564,895,312,11,932},
		{333,800,254,517,101,609,995,555,271,741,54,658,176,773,417,117,729,45,828,910,355,579,230,939,523,22,977,690,141,831,430,571},
		{110,615,420,747,918,303,12,806,145,591,1013,311,848,13,560,880,345,219,667,424,55,739,463,89,769,374,801,214,402,621,233,734},
		{876,203,950,339,164,846,436,689,343,887,204,444,530,951,246,644,493,1022,554,161,954,851,186,991,262,648,111,498,868,80,966,482},
		{32,696,557,69,662,546,208,953,504,43,786,701,92,381,738,138,847,74,793,276,639,532,391,684,565,906,336,999,704,302,774,372},
		{993,289,826,464,1015,385,751,106,627,404,266,588,825,184,990,460,300,390,699,473,9,327,127,886,41,422,170,594,17,534,158,649},
		{515,411,150,772,242,39,912,292,835,983,129,931,326,516,661,24,616,944,196,839,979,724,803,232,507,755,836,256,437,920,816,229},
		{869,82,935,634,337,585,692,479,187,538,686,457,50,864,255,894,781,95,584,367,146,562,447,1014,313,85,949,642,726,347,59,600},
		{316,715,209,497,857,134,393,807,4,356,776,227,604,742,396,171,526,440,261,913,664,279,56,619,702,551,378,105,193,1010,459,762},
		{978,574,438,47,964,757,231,992,595,900,103,1018,341,126,965,674,324,1009,761,28,819,413,871,156,911,221,785,488,867,561,274,155},
		{1,365,909,691,285,542,71,453,719,275,421,660,818,469,556,38,840,133,593,476,200,540,732,366,467,10,971,282,624,73,813,670},
		{874,249,798,174,412,655,838,331,139,863,525,31,195,929,270,736,418,237,716,351,942,102,996,241,830,568,665,414,166,958,384,478},
		{553,632,94,518,1023,124,927,563,678,218,962,752,318,645,83,891,608,980,58,854,672,308,601,72,694,330,114,856,710,310,758,188},
		{994,314,746,866,352,243,477,18,799,400,86,581,433,794,508,359,153,491,280,558,163,441,791,511,897,181,1024,535,29,494,899,68},
		{683,152,451,40,612,693,771,306,998,629,269,903,148,1007,213,833,680,926,408,745,902,19,973,267,394,756,450,234,812,613,263,435},
		{360,849,569,963,194,907,79,434,173,513,824,371,675,62,577,298,7,779,104,211,618,358,708,121,640,49,597,921,364,88,731,940},
		{14,228,764,295,405,522,841,602,934,44,706,224,496,768,406,957,637,340,543,1017,468,837,178,489,947,796,301,149,673,877,179,549},
		{659,1008,481,97,717,144,346,248,750,328,883,119,976,272,859,168,462,878,260,797,53,294,583,873,334,205,550,987,409,510,305,809},
		{123,380,605,829,928,575,982,666,108,471,578,398,647,26,533,614,67,728,143,669,401,961,767,34,423,697,844,20,763,100,970,446},
		{268,875,201,60,442,235,8,403,815,1020,183,778,924,350,753,245,988,370,908,485,98,528,238,651,1011,116,466,284,641,222,587,722},
		{943,500,705,348,650,775,890,531,215,620,42,296,509,131,832,425,676,182,573,281,852,723,136,383,559,190,919,537,810,901,354,51},
		{623,154,820,1000,290,490,157,688,307,941,428,860,713,210,967,84,501,817,15,1003,630,344,948,788,861,319,727,65,388,137,483,777},
		{329,426,37,545,113,959,376,805,81,725,548,93,636,410,582,325,936,257,711,427,197,61,461,258,6,631,429,946,247,682,1021,212},
		{566,917,677,217,748,589,30,472,905,342,177,1001,251,896,23,733,611,128,349,795,544,892,596,700,506,986,99,599,850,529,27,862},
		{107,273,787,363,930,277,845,654,239,580,770,486,357,780,521,185,885,470,653,955,118,286,759,130,220,811,309,192,766,317,443,657}
	}
end
if DITHER==DITHER_VAC64 then
	dither = {
		{1970,605,3505,2169,969,261,1259,2410,590,1391,2322,477,3907,1474,1930,2591,1341,2302,3901,74,1788,931,548,1628,3146,2250,47,1828,3697,271,2156,1771,1050,2879,1448,604,3144,134,2990,1994,1261,3693,748,1457,341,3943,2586,1423,3547,3200,1096,1939,651,2360,1603,4068,2202,1023,2470,3033,3636,2752,773,3926},
		{144,2616,1452,410,3766,3126,1979,3942,151,1893,3590,784,3347,2452,1042,3780,283,1660,3133,1176,2548,4036,3313,2014,856,3897,1234,2997,961,2399,3982,3378,441,3635,2327,3774,1799,2432,968,387,2695,1765,2313,3538,2876,2120,942,1898,210,729,3920,2638,3494,951,2869,359,1286,3540,498,1413,1766,331,2182,3183},
		{3622,936,3047,2450,1693,2767,781,3352,1051,3074,2715,1182,2074,143,3209,710,3469,2084,615,2854,1458,2139,158,1325,3481,2424,638,2052,3266,1560,795,2723,1236,1720,285,852,2787,1353,4020,3293,678,3014,458,1085,1675,96,3129,3827,2735,2271,1330,305,1525,3229,2000,3702,2647,1908,3257,717,4007,1111,2891,1335},
		{2328,4065,1909,703,3524,76,1489,2607,2234,1667,288,3987,1414,2942,1746,2263,2703,1090,3814,317,3633,742,2964,2645,407,1523,3759,2786,476,3565,102,2023,3091,2463,3238,2083,3417,240,1687,2111,3624,1369,3965,3240,2535,3659,580,1621,1045,3067,1784,3684,2297,121,1150,667,1656,43,2811,2335,1976,3371,612,1724},
		{390,1220,198,3190,1277,2121,3632,443,3820,716,3448,2508,583,3578,922,4060,36,1578,3285,2283,1770,3398,1074,3948,1925,3080,172,1148,1801,2630,1374,3824,558,959,4002,1270,631,3739,2626,1108,23,2421,1985,369,895,2235,1292,3462,2430,360,3345,597,2817,4006,3112,2462,3373,3938,908,1273,3745,163,2473,3007},
		{3296,2159,2846,3762,2364,993,3030,1854,1285,3163,1011,2181,1553,2596,435,1307,3058,1972,862,2615,1280,479,2321,1646,727,2536,3433,2256,4051,921,2320,3411,1658,2864,60,1585,3043,2340,840,3213,2856,728,1545,2760,3778,1768,2822,252,4085,878,2144,1184,1897,825,1400,2161,504,1519,2977,429,2622,1541,3597,819},
		{3882,1739,766,1470,354,3933,656,2458,216,2705,1901,113,3841,3315,1809,2827,3650,559,3935,200,3223,3732,2756,12,3537,980,1405,312,2867,601,3038,214,1153,2191,3545,2544,1870,375,1463,3946,1827,3508,3100,1175,140,3401,780,1919,2948,1582,3752,2549,3519,396,2700,3817,1054,2064,3586,1763,3145,1014,2078,1375},
		{2419,490,3654,2540,1904,2829,1600,3344,4095,1428,3570,2949,1207,367,2133,1017,2448,1506,2153,2909,963,1867,1440,3015,2187,3890,1951,3292,1552,2054,3779,1767,2755,3903,512,869,3300,3683,2095,546,1255,262,2186,4029,2497,1390,3179,2304,1224,518,3164,22,1471,3050,1792,145,3198,2589,244,2291,659,4021,2823,64},
		{1078,2772,3216,941,3483,31,1132,2056,807,2273,500,886,2422,3088,3941,719,3267,282,3428,1314,2396,669,4087,349,1244,519,2668,799,3625,1227,330,3322,783,1983,1425,2886,1143,131,2781,2374,3649,2643,975,495,2013,632,3613,179,3861,2678,1971,1076,2244,3724,948,3445,1336,744,3840,1209,3333,333,1865,3525},
		{2275,1604,194,1334,2218,3105,3726,440,2789,3269,1700,3798,2022,1453,82,1689,2688,1107,1910,3775,149,3153,2046,2567,3358,1601,3111,95,2465,2965,2301,1068,2606,366,3455,2220,4089,1759,3178,890,1629,3339,1857,3691,2995,1566,2585,972,1745,3363,743,3977,2920,637,1993,2416,1674,2998,1927,2734,1475,2474,789,3069},
		{539,4056,1995,3784,626,1681,2552,1376,3874,99,1230,2604,644,3623,2858,3484,2249,4017,609,2763,1625,3607,1130,775,3677,2306,967,3776,1810,553,4030,1468,3690,3041,1676,264,2516,646,1377,3871,183,679,2807,1147,40,3915,2122,2892,356,1411,2480,297,1631,2605,452,3947,357,3637,33,937,3917,1730,3710,1291},
		{3468,2841,839,2503,2912,247,3543,912,2326,1860,2893,3399,289,1154,1949,815,393,1539,3125,926,2509,478,2889,1831,203,2945,2036,1356,3334,911,2107,56,2394,670,1253,3781,1033,3530,1957,2970,2565,2126,1446,3476,2425,802,1257,3161,3740,2217,3546,1237,3227,3595,1392,2933,1140,2539,2163,3177,463,2881,127,2134},
		{1802,259,1473,3404,1149,1892,3021,1546,491,3176,971,2117,4009,2471,3221,1337,2592,3634,49,1965,3442,1306,2254,3836,1518,624,3954,251,2684,1645,3189,2794,1757,3389,2075,2738,3097,19,2308,529,1120,3758,3019,449,1791,3278,245,1923,595,918,2849,1903,75,2200,817,2069,3353,578,1592,3559,1186,2344,3348,1005},
		{2546,3201,2280,460,3892,2398,705,4045,2527,3521,373,1469,726,1749,169,3789,2045,2955,1137,2351,3895,280,3165,1024,3418,2724,1198,2385,3539,398,3793,1075,281,3993,874,486,1731,1297,3370,4010,1817,298,865,2329,4066,2727,1465,3870,2515,1617,439,4039,1110,3099,3831,243,1790,4062,859,2631,1882,683,1558,3952},
		{776,1208,3681,1751,946,3132,147,2048,1203,1716,3805,2299,3084,3556,2748,985,591,1692,3326,738,1478,1858,658,2541,9,1943,3234,871,2079,712,1378,2216,2928,1420,3230,2339,3719,2651,756,1542,2741,3235,3562,1586,1093,534,2086,3485,1168,3065,3384,2342,664,2660,1511,2412,2839,1308,3140,368,3876,3089,2699,414},
		{1991,2923,6,2750,2192,1404,3471,2722,834,2960,8,2639,1035,480,1549,2279,4077,2528,344,3707,3039,2670,4043,2141,1563,3717,355,1467,4014,3071,2481,3447,420,1873,2597,161,1104,2033,3057,212,2284,1200,2028,119,2941,3323,891,63,2691,352,2008,1352,3721,1820,515,1026,3699,72,2298,1491,2130,150,1283,3594},
		{3385,1595,3992,757,3307,334,1688,3755,522,3351,1962,1298,3958,2085,2915,3400,133,1250,2842,2057,1013,171,1210,3544,810,3018,2443,1862,2808,167,1748,854,3905,655,3567,1632,3919,547,3504,1008,3878,603,2598,3803,1839,2491,3715,2193,1740,3894,778,2922,126,3511,2986,3316,2025,823,3452,2731,1055,3696,1755,2388},
		{999,551,2101,1301,2494,3858,1079,2166,2475,1487,3674,746,3170,218,1362,714,1932,3552,1606,576,2435,3284,1764,2761,507,1293,3867,1020,577,3509,1181,2712,2105,2980,1015,2229,2897,1398,2363,1786,2952,1459,3158,358,1287,690,1494,3108,1031,3460,1537,2578,1089,2228,1418,292,2550,1644,3853,433,3301,711,2862,329},
		{3135,2612,3631,3035,472,1933,2929,103,973,2883,276,2350,1811,2590,3639,3000,2330,920,3124,3875,1432,3742,395,2338,3394,2040,105,2618,3226,2165,3727,1548,30,1320,3246,320,822,3354,61,3704,391,2147,832,3518,2264,3956,217,2766,570,2393,231,3239,3850,806,1874,4026,614,2958,1213,1876,2513,2088,4048,1501},
		{2277,1151,138,1663,879,3450,1444,3204,3971,1733,3392,1159,3863,579,1052,1717,3973,437,2611,37,2168,830,3026,1105,1642,2880,3561,1723,1359,751,353,3139,3851,2499,1863,4088,2568,1956,2826,1171,2510,4042,1760,2820,1049,2620,1990,3275,1349,4086,2106,1702,467,2415,2802,1165,3601,2170,164,3192,1450,966,70,3467},
		{698,3872,1958,2706,4059,2276,381,2613,707,2077,483,2777,1500,3297,2472,108,1348,3362,1814,1134,2913,1929,3490,279,3962,845,527,2305,4054,2934,1836,2282,897,536,3475,1187,1543,525,3489,1653,693,3304,1321,79,3403,1659,474,3671,1806,896,2984,1238,3608,3114,55,3270,1596,913,2610,3925,584,3585,2673,1772},
		{363,3366,1399,3155,618,1162,1848,3773,1272,2444,3569,910,2175,306,3765,2027,2764,611,3676,2457,4035,598,1304,2572,2184,1498,3258,1057,181,2525,1129,3431,2830,1704,2188,222,3137,3743,944,2109,3029,310,2026,3848,629,3045,954,2468,29,3408,347,2674,755,1530,2072,530,2331,3391,425,1701,3006,2221,1281,2968},
		{2459,2110,964,201,2506,3497,2878,190,3311,1612,41,4071,3068,1856,2911,850,3215,2239,957,1502,342,3185,1672,3714,90,2739,3837,1861,3062,3583,585,1429,114,3694,3020,794,2717,2307,135,2640,3646,1071,2758,2405,1460,2245,3998,1296,2873,2179,3735,1868,2355,3986,1116,3763,2740,1247,3658,2047,1112,204,3968,820},
		{1587,3815,2885,3672,2061,1449,747,2315,960,2972,2558,1355,528,1087,1551,405,3939,1640,226,3461,2716,2211,934,2943,2002,1189,378,2386,798,1619,2125,3969,2543,1070,1493,3864,1774,1133,4012,1410,517,1577,3255,861,3657,388,1859,3202,675,1536,1056,514,3330,211,2918,824,1845,101,2851,782,3314,2582,1896,3171},
		{28,1144,572,1661,316,3075,3609,1707,3900,568,1906,3412,2269,3729,3279,2441,1124,2654,3109,2034,1196,3829,427,3407,770,3653,3175,1407,3741,2693,371,3157,1855,556,2377,294,3309,606,1937,3426,2287,3795,1818,122,2900,1145,2649,237,3579,2530,3885,2801,1311,1722,3495,2442,1408,4076,2240,1534,3750,469,1395,3548},
		{2230,2681,3435,2395,3980,1034,447,2656,2136,1167,3655,224,2759,700,2010,77,3532,1872,739,3663,59,1719,2537,1389,1843,2488,645,2174,26,3010,1276,887,3648,2737,3451,2007,1338,2671,3152,909,270,2609,701,2197,3499,1557,3844,2142,906,1737,142,1999,3167,617,2115,323,3273,682,3113,242,2436,1016,2780,665},
		{4033,1366,1879,816,2771,1980,1288,3368,296,3040,1562,876,3166,1685,3990,1342,2917,419,1421,2348,2877,623,3196,4050,148,2860,1664,3879,1060,1960,3415,2242,139,1643,787,2959,3955,18,2417,1668,2994,1179,3932,3148,996,2031,622,3380,1380,2931,3470,745,2505,3922,1218,3666,2634,1920,1152,3598,1738,3909,2039,3037},
		{935,401,3237,188,1529,2993,3787,2375,793,4027,2055,2479,1263,438,2636,938,2185,3744,3168,976,3913,1928,903,2219,1172,3549,385,3286,2538,691,4072,1454,2896,3834,1194,408,2213,1030,3746,587,3459,2003,1483,481,2782,180,3101,2451,314,4084,2246,1044,1614,45,2903,812,1573,424,2961,2157,582,3264,173,1622},
		{2464,2835,3718,2068,3527,641,44,1840,1438,2682,189,3748,3336,2251,3606,3086,634,1736,2532,343,1517,3367,2726,489,3121,2005,833,1472,2914,1769,494,2397,327,1952,2524,3533,1484,3321,1899,1326,2765,92,3667,2511,1715,3960,1046,1796,2751,1235,442,3256,2655,3582,1886,2295,3976,3355,2507,902,1479,2579,1221,3500},
		{639,1711,1163,2346,970,2573,3207,1094,2921,3501,680,1762,1037,106,1875,1522,272,4078,1169,3486,2292,166,1268,3804,1599,2642,3964,2267,160,3737,1097,3276,3615,965,3051,1752,694,2853,287,2381,4073,1061,2270,851,3281,1358,2190,3641,765,1637,3689,2070,1340,586,3197,284,1025,1365,109,3886,3150,326,3794,1997},
		{65,3896,3079,299,4055,1464,2100,3856,389,1973,1289,2580,2992,3916,741,2379,3248,2799,2017,771,3032,1832,3575,2426,706,205,1126,3396,1333,3117,2151,2725,1402,564,4003,129,2319,3846,901,3249,520,1756,3036,227,3605,541,2898,16,3219,2427,2979,186,4001,917,2437,1753,2855,3502,1966,1610,2309,2894,866,3329},
		{2675,1442,735,1773,2924,497,3443,835,2429,3103,3966,457,2103,1372,2665,3523,990,1447,35,3675,2661,1040,412,2094,3011,3493,1888,2800,610,1833,828,46,1695,2108,2652,1303,3160,1987,1613,2697,2127,3492,1431,2672,1850,2408,949,1981,3899,561,1006,1895,2784,3390,1412,3822,686,2571,482,3644,648,1309,1816,2243},
		{1082,3449,2445,3679,1984,1216,2736,1665,175,1067,1540,3283,898,3673,235,1959,533,3877,2231,1680,563,3220,1550,4022,1371,858,2366,269,3785,2492,3465,3936,2976,3375,857,3640,379,1077,3528,111,1246,733,3813,400,1190,4032,3107,1569,1215,2288,3496,1547,475,2152,83,3012,1192,2198,3254,1114,2704,4079,397,3031},
		{569,2093,154,928,3327,221,2285,3731,2888,3474,2343,13,2825,1698,3182,1205,3005,2493,3306,1262,3777,2001,2570,81,2757,3686,1594,3042,1029,1516,448,2262,1069,274,2489,1590,2907,2376,652,3902,2936,2349,3162,1964,3421,689,315,2561,3332,255,2844,3842,1127,2595,3695,1942,313,3967,1714,20,2012,3379,1486,3669},
		{1743,4005,2828,1565,2534,3953,709,1350,2066,636,1826,3749,2466,666,2207,3802,1623,215,737,2718,303,916,3405,1211,619,2177,376,3970,2067,3233,2850,1351,1917,3791,593,2030,4049,1363,3291,1934,1485,260,955,1535,2237,2837,1776,3751,805,1409,2006,722,3094,1627,829,3341,1462,2861,734,3052,2352,914,193,2496},
		{814,1290,3253,538,1170,2954,1852,3205,415,4093,940,1360,3395,1117,325,2687,860,2104,4041,1780,3025,2238,3838,1684,2939,3317,1300,2628,688,195,3588,736,2709,3169,1185,3420,62,831,2608,473,3620,2803,3996,2566,209,3610,1080,2123,2983,3988,2529,110,3619,2323,392,2680,998,2404,3596,1266,3904,1618,3208,2916},
		{370,2383,1921,3761,2204,295,3592,1086,2710,2214,3073,273,1931,3983,3231,1388,3568,2947,1073,3444,1435,681,2478,266,1916,811,3566,1758,1121,2447,1679,4028,130,1532,2316,2821,1815,2253,3104,1713,1059,2050,560,3277,844,1393,3194,159,557,1630,1092,3360,1841,1271,4069,2019,3736,502,1853,268,2663,574,2145,3821},
		{1058,3587,5,3078,1706,779,2498,1510,152,3453,1611,2564,2866,488,2314,1805,57,2406,506,2015,156,3581,1157,3236,4070,2334,32,2783,3881,3328,2150,1007,2556,3506,883,338,3656,1139,3888,208,3402,2414,1243,1797,3760,2728,1697,2431,3643,2768,2224,374,2988,673,2810,124,1597,3250,2196,3440,991,3564,1327,1880},
		{3288,2600,1456,981,2744,3914,3247,2116,3855,704,1199,3799,841,1521,2996,713,3898,1258,3274,2624,3951,1734,2742,487,1508,1027,3142,2035,543,1416,290,3130,1844,535,3928,1626,2989,562,1451,2746,797,3832,3016,10,2266,426,4038,749,1267,3438,813,3931,1531,2495,3513,1119,2975,827,1373,2847,1657,2407,118,2832},
		{1605,444,3989,2286,233,1343,513,953,1744,2956,2403,107,2113,3662,1101,3359,1961,2812,1568,732,2312,904,3090,1998,2551,3772,346,1555,2999,894,3809,2788,1225,2164,3214,1041,2526,2051,3331,2341,1885,446,1509,2650,3522,1063,2090,2967,1842,53,2018,3173,1021,1884,493,2247,3912,2484,197,3843,484,3172,3923,750},
		{3487,2020,697,3156,3534,2041,3017,3664,2259,423,3423,1838,3245,2588,232,2389,413,943,3786,340,3386,1310,100,3517,685,1245,3361,2603,3708,2402,1652,649,3603,15,2696,1913,246,3975,924,117,3576,1106,3174,1944,571,1385,3280,318,3830,2629,1379,2336,223,3818,3263,1437,1808,633,3372,1975,884,1800,1202,2215},
		{2575,1282,2818,1787,1123,2557,1648,52,2730,1417,3959,988,544,1315,4063,1678,3515,2160,3119,1813,2769,2082,3866,1651,2925,2278,1866,740,1155,112,1955,3312,2434,1394,3835,671,3491,1381,3116,1670,2874,4074,2361,870,3887,2791,2418,1572,986,3310,532,3665,2926,2576,915,86,3064,2627,1299,2268,3725,2648,3066,291},
		{974,3617,91,3857,386,768,4053,1256,3218,791,2486,1636,3110,2016,2713,764,2944,1387,80,1083,3591,635,2411,997,409,4000,185,3563,2146,2932,4061,1001,328,3001,1742,1131,2819,2357,406,2176,1242,657,300,3406,1728,98,3651,640,2272,2845,1732,1212,760,1608,2032,3645,1100,4024,411,2953,34,1515,613,4080},
		{1624,2946,2370,1499,2698,3419,2209,523,3621,2059,234,2872,3593,14,1142,3720,516,2371,3927,2554,1505,304,3008,3305,1361,2729,1735,3044,1383,451,2679,1527,2222,3661,461,2096,3259,803,3806,2677,3503,2009,2749,1339,2167,3077,1164,1986,3945,332,3531,2140,4058,453,3381,2785,2183,718,1574,3572,1113,3456,2356,1953},
		{3364,838,555,3287,1877,978,2930,1803,2601,1109,3854,621,2293,1496,3265,2099,1002,3432,1924,754,2852,4023,1718,2024,3584,596,2446,932,3289,3682,684,1894,3272,873,2467,4015,199,1490,1878,1010,89,1554,3149,3767,977,537,2587,3416,1382,907,2563,67,3095,2433,1312,309,1741,3295,2456,1936,2694,777,3127,187},
		{2203,3807,1239,2138,265,3688,1445,146,3147,1575,3349,1915,872,3994,2577,311,2775,1635,402,3195,2149,1248,818,24,2310,1146,3921,301,1638,2347,1195,3883,176,2843,1274,1671,2707,3604,554,2973,3957,2522,752,248,2373,4019,1649,153,2927,1869,3228,1497,1043,1907,3687,885,3823,136,952,3950,383,1729,3734,1345},
		{403,1782,2733,4018,3093,695,2333,3934,899,421,2469,1313,2815,456,1795,1226,3808,3034,1295,3670,220,3374,2533,3801,3056,1544,3383,2778,1967,58,3013,2553,1488,3542,575,3143,927,2073,3335,2325,1183,1794,3365,1480,2963,1950,3241,772,3788,2324,607,3918,2676,660,2950,2232,2641,3115,1396,2895,2137,1197,2838,2502},
		{3054,3436,4,1019,1607,2599,1177,3430,2114,3003,3706,123,3541,3120,2384,3480,170,731,1871,2400,1072,1779,2809,508,945,1889,399,846,3812,3454,994,2097,364,1864,2265,3769,39,2574,1346,275,3728,511,2194,3589,1047,422,1322,2711,1125,345,3466,1798,192,3356,1424,436,1138,1881,599,3410,177,3859,608,1003},
		{1580,758,2453,2063,3558,351,1750,2770,602,1825,1095,2248,1639,987,589,1482,2158,2623,4057,2908,627,3860,1433,2092,3678,2518,3131,2252,1249,2646,600,3128,4040,796,2901,1174,1747,3999,725,1992,2865,956,2617,11,2814,3698,2392,3388,2132,1567,2792,1217,2382,3849,2080,3180,4046,2428,3716,1564,2294,3186,1837,3616},
		{2241,3713,1430,2884,581,3023,3828,68,1426,4094,2863,365,3826,2042,2743,3908,3298,1022,1422,73,3472,2300,257,2978,1231,115,4064,1504,431,1804,3638,1602,1122,3397,2485,384,3232,2753,1591,3550,3184,1406,4067,2071,1593,654,1793,249,3997,730,3118,3723,933,1696,302,808,1620,21,1004,2745,450,1302,2637,322},
		{1191,2719,230,3972,1251,1926,2365,992,3242,2531,804,3427,1354,3193,38,836,1709,445,3136,2087,1634,983,3261,767,3437,1775,661,2774,3318,2390,258,2798,2173,191,1476,3703,2155,950,471,2337,182,1834,759,3290,1201,3845,3085,939,2614,1922,42,2201,531,3046,2512,3425,2797,3574,1941,3087,774,4025,2044,3260},
		{3833,620,1807,3206,875,3387,1513,3652,2065,250,1712,2332,503,2569,1849,3614,2938,2482,3738,702,2721,3981,2504,1526,2689,2171,3554,1032,1978,3944,1347,708,3865,3004,1996,672,1319,3906,3098,1222,2692,3782,361,2477,2951,141,2098,1461,3611,1156,3369,1427,2702,3626,1053,1357,2208,642,1284,2401,3457,1677,71,867},
		{1609,3482,2189,2501,377,2669,196,668,2796,1173,3800,3049,947,4011,1228,2206,337,1136,1812,3424,1265,335,1890,510,3910,286,1384,2991,88,849,3070,2476,1690,1000,3560,2559,2905,120,1940,3630,881,2124,3409,1691,1009,2317,3478,501,2857,2391,653,4075,1830,168,2004,3961,229,3151,3893,277,1141,2773,2274,2987},
		{2545,162,989,1403,3754,2102,3949,3060,1778,3463,418,2089,1588,2859,663,3271,1576,3891,2353,165,3081,2205,3680,1161,2935,892,2455,3796,1584,2226,3612,468,3377,51,1819,454,3346,1647,2460,552,1556,3053,1269,542,3974,2720,826,1823,3911,256,1650,2904,893,2439,3268,761,1789,2621,1533,2131,3599,567,3350,1344},
		{1946,4081,2754,3123,715,1654,1223,2296,889,2487,1415,3299,116,2368,3580,202,2632,929,588,2871,1481,868,3210,2354,1655,3414,1905,492,3337,2836,1118,2043,1434,2732,3764,1178,2255,809,3446,2804,4016,69,2555,3573,1912,308,1364,3092,1062,2129,3302,1252,3790,524,1397,2985,3701,459,877,2962,1754,1039,3868,348},
		{3211,1166,462,1887,3535,2875,496,3577,7,4037,643,2662,3869,847,1328,1829,3024,3510,2037,4082,1777,3555,93,699,3839,206,2685,1214,724,1783,238,4083,3217,2180,753,3063,3924,1477,219,1135,1851,848,2260,2971,1507,3243,3816,2369,464,3600,2581,84,2058,3514,2762,2223,1099,3357,2454,3810,104,2701,2053,792},
		{2805,1725,3692,2409,125,982,1989,3203,1598,2831,1974,1180,1727,2910,2119,3783,432,1260,2547,1065,455,2584,1963,2795,1419,2143,3181,3963,2413,3668,2602,925,521,1254,2514,263,1948,2633,3647,2128,3282,3709,324,1088,720,2148,54,2806,1512,1883,674,2981,1579,979,372,1673,128,1968,1324,630,3191,1232,2387,3628},
		{3,2281,687,1492,3342,2644,3930,1331,2362,995,3730,470,3479,241,3308,723,2318,1669,2,3188,3770,1329,3061,962,3516,416,864,1571,1,1294,3141,1918,2870,3862,1616,3520,616,984,3002,430,1323,2686,1615,3937,2583,3529,1240,837,3747,3159,1028,4008,2423,3212,3722,2593,4052,2840,3553,2311,1891,3979,505,1401},
		{3106,1064,3991,2940,1188,2178,382,721,3096,213,2974,2154,2521,1514,1081,2667,3929,3439,2816,2135,788,2345,307,4013,1761,2560,3022,2029,3498,2225,380,1528,3434,94,2076,2833,1370,4034,1699,2289,662,3072,1969,3343,434,1721,3028,2049,2461,174,1318,2112,278,628,1945,1233,786,417,1570,919,321,2899,1686,3458},
		{2021,2625,428,1847,225,3792,1710,3422,1914,3618,1367,853,3978,3122,1947,350,1443,900,545,1824,3507,1581,3303,1206,2236,625,3825,1036,2824,692,3985,2378,763,1103,3262,466,2358,3187,27,2594,3889,930,137,1264,2227,677,3995,339,3488,1705,3797,2834,3429,1503,2969,2257,3464,3134,2490,3768,3252,1048,2523,769},
		{3884,1583,3225,3526,2519,923,2890,1219,2619,550,2438,1822,50,650,3629,2937,2195,3154,1278,3984,178,2635,676,2902,97,3251,1386,267,1662,3222,1158,2714,3753,1785,2562,3705,855,1982,1160,3413,1441,3557,2500,2957,3700,2666,1018,1439,2708,565,2290,800,1846,1012,3940,25,1726,1084,2062,184,1466,2172,3642,207},
		{1316,882,2258,696,1436,3660,2233,85,4096,1589,3244,3771,2813,1305,2372,1682,132,3685,2420,2882,1038,2038,3873,1703,3536,1954,2683,2303,3602,1902,157,2081,499,3009,1317,254,1633,3819,2887,336,1821,2162,566,1561,253,1781,3294,1988,3083,1193,3320,228,3627,2664,526,2449,3733,573,2982,2659,4031,592,1835,2848},
		{2440,3757,66,3055,1935,485,3199,801,2060,1102,293,958,2091,3473,863,4044,1128,1911,465,1524,3382,362,1279,2380,785,1115,4092,509,880,2906,3852,1495,3512,905,2212,3325,2657,549,2261,790,3224,1091,4091,3102,888,2367,3756,17,842,4047,2520,1455,2118,1229,3076,1900,1368,3338,1666,843,1241,3441,3082,394},
		{3319,1683,2793,1204,4004,2653,1641,3477,2790,3711,3027,1708,2658,236,3048,540,3324,2776,821,3571,2210,3059,2690,3712,319,2868,1538,3340,2542,1332,647,3138,2483,48,4090,1938,1098,3551,1520,3880,2517,87,2747,1977,3376,1275,594,2919,2199,1694,404,2966,3811,155,3393,762,2779,239,3847,2011,78,2359,1559,1066}
	}
end

-- notm matrix
dither = bayer.norm(dither)

-- get screen size
local screen_w, screen_h = getpicturesize()
local thom_w,thom_h = 320,200

-- Converts thomson coordinates (0-319,0-199) into screen coordinates
local function thom2screen(x,y)
	local i,j,k=0,0,1.6
	if screen_w/screen_h <= k then
		local o = CENTERED and (screen_w-screen_h*k)/2 or 0
		i = x*screen_h/thom_h+o
		j = y*screen_h/thom_h
	else
		local o = CENTERED and (screen_h-screen_w/k)/2 or 0
		i = x*screen_w/thom_w
		j = y*screen_w/thom_w+o
	end
	return math.floor(i), math.floor(j)
end

-- return the pixel @(x,y) in linear space corresonding to the thomson screen (x in 0-159, y in 0-99)
local function getLinearPixel(x,y)
	local x1,y1 = thom2screen(x,y)
	local x2,y2 = thom2screen(x+1,y+1)
	if x2==x1 then x2=x1+1 end
	if y2==y1 then y2=y1+1 end

	local p,i,j = Color:new(0,0,0);
	for i=x1,x2-1 do
		for j=y1,y2-1 do
			p:add(getLinearPictureColor(i,j))
		end
	end

	return p:div((y2-y1)*(x2-x1)):floor()
end

-- enhance luminosity since our mode divide it by two
local gain = 1
if ENHANCE_LUM then
	-- get color statistics
	local stat = {};
	function stat:clear() 
		self.r = {}
		self.g = {}
		self.b = {}
		for i=1,16 do self.r[i] = 0; self.g[i] = 0; self.b[i] = 0; end
	end
	function stat:update(px) 
		local pc2to = thomson.levels.pc2to
		local r,g,b=pc2to[px.r], pc2to[px.g], pc2to[px.b];
		self.r[r] = self.r[r] + 1;
		self.g[g] = self.g[g] + 1;
		self.b[b] = self.b[b] + 1;
	end
	function stat:coversThr(perc)
		local function f(stat)
			local t=-stat[1]
			for i,n in ipairs(stat) do t=t+n end
			local thr = t*perc; t=-stat[1]
			for i,n in ipairs(stat) do 
				t=t+n 
				if t>=thr then return i end
			end
			return 0
		end
		return f(self.r),f(self.g),f(self.b)
	end
	stat:clear();
	for y = 0,thom_h do
		for x = 0,thom_w do
			stat:update(getLinearPixel(x,y))
		end
		thomson.info("Collecting stats...",math.floor(100*y/(thom_h-1)),"%")
end
	-- findout level that covers 98% of all non-black pixels
	local max = math.max(stat:coversThr(.999))

	gain = math.min(1,255/thomson.levels.linear[max])

	if gain>1 then
		-- redo stat with enhanced levels
		-- messagebox('gain '..gain..' '..table.concat({stat:coversThr(.98)},','))
		stat:clear();
		for y = 0,thom_h do
			for x = 0,thom_w1 do
				stat:update(getLinearPixel(x,y):mul(gain):floor())
			end
			thomson.info("Enhancing levels..",math.floor(100*y/(thom_h-1)),"%")
		end
	end
end

local linearPalette = {}
function linearPalette.get(i)
	local p = linearPalette[i]
	if not p then
		local pal = thomson.palette(i-1)
		if pal==nil then error(i) end
		local b=math.floor(pal/256)
		local g=math.floor(pal/16)%16
		local r=pal%16
		p = Color:new(thomson.levels.linear[r+1],
					  thomson.levels.linear[g+1],
					  thomson.levels.linear[b+1])
		linearPalette[i] = p
	end
	return p:clone()
end

thomson.setMO5()
local dy,dx,px = #dither,#dither[1],{}

local function dith(x,y)
	if ZIGZAG>0 then y = y + (math.floor(x/ZIGZAG)%2) end
	return dither[1+(y%dy)][1+(x%dx)]*(Color.ONE+1)
end
		
local function dist2(p1,p2)
	-- return (2*(p1.r-p2.r))^2 + (4*(p1.g - p2.g))^2 + (1*(p1.b - p2.b))^2
	return (.3*(p1.r-p2.r))^2 + (.59*(p1.g - p2.g))^2 + (.11*(p1.b - p2.b))^2
	-- return p1:dE2fast(p2)
end

local function eval(c1,c2,img,mx)
	local p1,p2,e,seg = linearPalette.get(c1),linearPalette.get(c2),0,{}

	for i,p in pairs(img) do
		local d1,d2 = dist2(p,p1),dist2(p,p2)
		if d1<d2 then e,seg[i]=e+d1,c1-1 else e,seg[i]=e+d2,0-c2 end
		if e>mx then break end
	end
	
	return e,seg
end

if MONOCHROME then
	local img = {}
	for y=0,thom_h-1 do 
		for x=0,thom_w-1 do
			local d = dith(x,y)
			img[x+y*thom_w] = getLinearPixel(x,y):mul(gain):add(Color:new(d,d,d))
		end
	end
	local best,seg=1e300
	local i,max_i = 0,MAXCOL*(MAXCOL-1)/2
	for c1=2,MAXCOL do
		for c2=1,c1-1 do
			local e,bx = eval(c1,c2,img,best)
			if e<best then best,px = e,bx end
			thomson.info("Converting...",math.floor(100*i/max_i),"%"); i=i+1
		end
	end
elseif ERR_PROPAG>0 then
	local HALF,ONE,COL=Color.ONE/2,Color.ONE,{}
	for i=0,MAXCOL-1 do COL[i] = linearPalette.get(i+1); COL[-i-1] = COL[i] end
	for x=0,thom_w-1,8 do
		local img,err,xpt = {},{},{}
		for i=0,7 do err[i] = Color.black end
		for y=0,thom_h-1 do 
			for i=0,7 do
				local d = dith(x+i,y)
				local p = getLinearPixel(x+i,y):mul(gain)
				img[i] = p:add(Color:new(d,d,d)):add(err[i])
				xpt[i] = Color:new(p.r>=HALF and ONE or 0, p.g>=HALF and ONE or 0, p.b>=HALF and ONE or 0)
			end
			local best,seg=1e300
			for c1=2,MAXCOL do
				for c2=1,c1-1 do
					local e,bx = eval(c1,c2,img,best)
					if e<best then best,seg = e,bx end
				end
			end
			for i,c in pairs(seg) do px[x+i+y*thom_w],err[i] = c,xpt[i]:sub(COL[c]):mul(ERR_PROPAG) end			
		end
		thomson.info("Converting...",math.floor(100*x/thom_w),"%") 
	end
else
	for y=0,thom_h-1 do 
		for x=0,thom_w-1,8 do
			local img = {}
			for i=0,7 do
				local d = dith(x+i,y)
				img[i]  = getLinearPixel(x+i,y):mul(gain):add(Color:new(d,d,d))
			end
			local best,seg=1e300
			for c1=2,MAXCOL do
				for c2=1,c1-1 do
					local e,bx = eval(c1,c2,img,best)
					if e<best then best,seg = e,bx end
				end
			end
			for i,c in pairs(seg) do px[x+i+y*thom_w] = c end			
		end
		thomson.info("Converting...",math.floor(100*y/thom_h),"%") 
	end
end
	
for y=0,thom_h-1 do for x=0,thom_w-1 do thomson.pset(x,y,px[x+y*thom_w]) end end

-- refresh screen
setpicturesize(320,200)
thomson.updatescreen()
finalizepicture()

-- save picture
do
	local function exist(file)
		local f=io.open(file,'rb')
		if not f then return false else io.close(f); return true; end
	end
	local name,path = getfilename()
	local mapname = string.gsub(name,"%.%w*$","") .. ".map"
	local fullname = path .. '/' .. mapname
	-- fullname = 'D:/tmp/toto.map'
	local ok = not exist(fullname)
	if not ok then
		selectbox("Ovr " .. mapname .. "?", "Yes", function() ok = true; end, "No", function() ok = false; end)
	end
	if ok then thomson.savep(fullname) end
end

--[[ a tester sur: https://www.w3schools.com/python/scipy/trypython.php?filename=demo_scipy_editor

# BlueNoise.py - An implementation of the void and cluster method for generation of 
#				 blue noise dither arrays and related utilities.
#
# Written in 2016 by Christoph Peters, Christoph(at)MomentsInGraphics.de
#
# To the extent possible under law, the author(s) have dedicated all copyright and 
# related and neighboring rights to this software to the public domain worldwide. 
# This software is distributed without any warranty.
#
# You should have received a copy of the CC0 Public Domain Dedication along with 
# this software. If not, see <http://creativecommons.org/publicdomain/zero/1.0/>. 

from os import path,makedirs
import numpy as np
from scipy import ndimage
import struct


def FindLargestVoid(BinaryPattern,StandardDeviation):
	"""This function returns the indices of the largest void in the given binary 
	   pattern as defined by Ulichney.
	  \param BinaryPattern A boolean array (should be two-dimensional although the 
			 implementation works in arbitrary dimensions).
	  \param StandardDeviation The standard deviation used for the Gaussian filter 
			 in pixels. This can be a single float for an isotropic Gaussian or a 
			 tuple with one float per dimension for an anisotropic Gaussian.
	  \return A flat index i such that BinaryPattern.flat[i] corresponds to the 
			  largest void. By definition this is a majority pixel.
	  \sa GetVoidAndClusterBlueNoise"""
	# The minority value is always True for convenience
	if(np.count_nonzero(BinaryPattern)*2>=np.size(BinaryPattern)):
		BinaryPattern=np.logical_not(BinaryPattern);
	# Apply the Gaussian. We do not want to cut off the Gaussian at all because even 
	# the tiniest difference can change the ranking. Therefore we apply the Gaussian 
	# through a fast Fourier transform by means of the convolution theorem.
	FilteredArray=np.fft.ifftn(ndimage.fourier.fourier_gaussian(np.fft.fftn(np.where(BinaryPattern,1.0,0.0)),StandardDeviation)).real;
	# Find the largest void
	return np.argmin(np.where(BinaryPattern,2.0,FilteredArray));


def FindTightestCluster(BinaryPattern,StandardDeviation):
	"""Like FindLargestVoid() but finds the tightest cluster which is a minority 
	   pixel by definition.
	  \sa GetVoidAndClusterBlueNoise"""
	if(np.count_nonzero(BinaryPattern)*2>=np.size(BinaryPattern)):
		BinaryPattern=np.logical_not(BinaryPattern);
	FilteredArray=np.fft.ifftn(ndimage.fourier.fourier_gaussian(np.fft.fftn(np.where(BinaryPattern,1.0,0.0)),StandardDeviation)).real;
	return np.argmax(np.where(BinaryPattern,FilteredArray,-1.0));


def GetVoidAndClusterBlueNoise(OutputShape,StandardDeviation=1.5,InitialSeedFraction=0.1):
	"""Generates a blue noise dither array of the given shape using the method 
	   proposed by Ulichney [1993] in "The void-and-cluster method for dither array 
	   generation" published in Proc. SPIE 1913. 
	  \param OutputShape The shape of the output array. This function works in 
			 arbitrary dimension, i.e. OutputShape can have arbitrary length. Though 
			 it is only tested for the 2D case where you should pass a tuple 
			 (Height,Width).
	  \param StandardDeviation The standard deviation in pixels used for the 
			 Gaussian filter defining largest voids and tightest clusters. Larger 
			 values lead to more low-frequency content but better isotropy. Small 
			 values lead to more ordered patterns with less low-frequency content.
			 Ulichney proposes to use a value of 1.5. If you want an anisotropic 
			 Gaussian, you can pass a tuple of length len(OutputShape) with one 
			 standard deviation per dimension.
	  \param InitialSeedFraction The only non-deterministic step in the algorithm 
			 marks a small number of pixels in the grid randomly. This parameter 
			 defines the fraction of such points. It has to be positive but less 
			 than 0.5. Very small values lead to ordered patterns, beyond that there 
			 is little change.
	  \return An integer array of shape OutputShape containing each integer from 0 
			  to np.prod(OutputShape)-1 exactly once."""
	nRank=np.prod(OutputShape);
	# Generate the initial binary pattern with a prescribed number of ones
	nInitialOne=max(1,min(int((nRank-1)/2),int(nRank*InitialSeedFraction)));
	# Start from white noise (this is the only randomized step)
	InitialBinaryPattern=np.zeros(OutputShape,dtype=np.bool);
	InitialBinaryPattern.flat=np.random.permutation(np.arange(nRank))<nInitialOne;
	# Swap ones from tightest clusters to largest voids iteratively until convergence
	while(True):
		iTightestCluster=FindTightestCluster(InitialBinaryPattern,StandardDeviation);
		InitialBinaryPattern.flat[iTightestCluster]=False;
		iLargestVoid=FindLargestVoid(InitialBinaryPattern,StandardDeviation);
		if(iLargestVoid==iTightestCluster):
			InitialBinaryPattern.flat[iTightestCluster]=True;
			# Nothing has changed, so we have converged
			break;
		else:
			InitialBinaryPattern.flat[iLargestVoid]=True;
	# Rank all pixels
	DitherArray=np.zeros(OutputShape,dtype=np.int);
	# Phase 1: Rank minority pixels in the initial binary pattern
	BinaryPattern=np.copy(InitialBinaryPattern);
	for Rank in range(nInitialOne-1,-1,-1):
		iTightestCluster=FindTightestCluster(BinaryPattern,StandardDeviation);
		BinaryPattern.flat[iTightestCluster]=False;
		DitherArray.flat[iTightestCluster]=Rank;
	# Phase 2: Rank the remainder of the first half of all pixels
	BinaryPattern=InitialBinaryPattern;
	for Rank in range(nInitialOne,int((nRank+1)/2)):
		iLargestVoid=FindLargestVoid(BinaryPattern,StandardDeviation);
		BinaryPattern.flat[iLargestVoid]=True;
		DitherArray.flat[iLargestVoid]=Rank;
	# Phase 3: Rank the last half of pixels
	for Rank in range(int((nRank+1)/2),nRank):
		iTightestCluster=FindTightestCluster(BinaryPattern,StandardDeviation);
		BinaryPattern.flat[iTightestCluster]=True;
		DitherArray.flat[iTightestCluster]=Rank;
	return DitherArray;



if(__name__=="__main__"):
	np.random.seed();
	for i in [4,8,16,32,64]:
		M=GetVoidAndClusterBlueNoise((i,i));
		print('	dither = {');
		for y in range(0,i-1):
			t = '		{' + str(M[y][0]+1);
			for x in range(1,i):
				t = t + ',' + str(M[y][x]+1);	
			print(t + '},');
		t = '		{' + str(M[i-1][0]+1);
		for x in range(1,i):
			t = t + ',' + str(M[i-1][x]+1);	
		print(t + '}');
		print('	}');
		print();
]]--