How would you interpret the pattern in this picture? (generated by re-sorting pixels based on their RGB value)

Question

Was playing with some pictures and ran the ruby code below. The code reads an input image using the ImageMagick library, gets an array of pixels, re-sorts the pixels and then writes out an image with the re-sorted pixels and using the same dimensions as the original image.

require 'rmagick'

include Magick

img = ImageList.new("images/test-image.jpg")
pixels = img.get_pixels(0,0,img.columns,img.rows)

# Sort pixels by total intensity

# https://apidock.com/ruby/Array/sort
# The block must implement a comparison between a and b and
# * <0 when b follows a,
# * 0 when a and b are equivalent, 
# * >0 when a follows b

# The result is not guaranteed to be stable.
# When the comparison of two elements returns 0, the order of the elements is unpredictable.

pixels = pixels.sort {|p| p.red + p.green + p.blue}

out_img = Magick::Image.new(img.columns, img.rows)
out_img.store_pixels(0,0, img.columns, img.rows, pixels)
out_img.write("images/test-image-out.jpg")

I was trying to sort the pixels by the sum of their RGB values, but for that I should have used sort_by instead of sort on the pixels array.

So the pixels are not being sorted by the sum of their RGB values, but I don't know how they are being sorted either, and why when sorted that way they generate the pattern on the sample pictures below.

I included the short documentation of the Ruby Array.sort method to help understand with what's going on.

Original picture:

Picture with re-ordered pixels (using pixels.sort {|p| p.red + p.green + p.blue} or pixels = pixels.sort {|a,b| 1}):

Following suggestions from @OlliNiemitalo and @xiota, if instead of doing pixels = pixels.sort {|p| p.red + p.green + p.blue} the code does pixels = pixels.sort {|a,b| 1}, the output is the same (the weird repetition pattern).

When doing pixels = pixels.sort {|a,b| b <=> a} though, the output looks like the picture below.

Below is what happens when running (0..1023).to_a.sort{|p| 1} on the irb (ruby 2.5.1p57 (2018-03-29 revision 63029) [x86_64-darwin16]). Can't really tell what the pattern is just by looking at the numbers.

irb(main):009:0> (0..1023).to_a.sort{|p| 1}
=> [22, 512, 0, 513, 1, 514, 2, 515, 3, 516, 4, 517, 25, 518, 29, 519, 33, 520, 40, 41, 275, 787, 147, 659, 403, 915, 83, 595, 339, 723, 211, 851, 467, 979, 51, 563, 307, 627, 179, 691, 371, 755, 115, 819, 435, 883, 243, 947, 499, 1011, 15, 547, 291, 579, 163, 611, 323, 643, 99, 675, 355, 707, 195, 739, 387, 771, 67, 803, 419, 835, 227, 867, 451, 899, 131, 931, 483, 963, 259, 995, 18, 523, 7, 539, 283, 555, 155, 571, 299, 587, 91, 603, 315, 619, 171, 635, 331, 651, 59, 667, 347, 683, 187, 699, 363, 715, 107, 731, 379, 747, 203, 763, 395, 779, 43, 795, 411, 811, 219, 827, 427, 843, 123, 859, 443, 875, 235, 891, 459, 907, 75, 923, 475, 939, 251, 955, 491, 971, 139, 987, 507, 1003, 267, 1019, 271, 527, 27, 535, 279, 543, 151, 551, 287, 559, 87, 567, 295, 575, 159, 583, 303, 591, 55, 599, 311, 607, 167, 615, 319, 623, 95, 631, 327, 639, 175, 647, 335, 655, 30, 663, 343, 671, 183, 679, 351, 687, 103, 695, 359, 703, 191, 711, 367, 719, 63, 727, 375, 735, 199, 743, 383, 751, 111, 759, 391, 767, 207, 775, 399, 783, 11, 791, 407, 799, 215, 807, 415, 815, 119, 823, 423, 831, 223, 839, 431, 847, 71, 855, 439, 863, 231, 871, 447, 879, 127, 887, 455, 895, 239, 903, 463, 911, 47, 919, 471, 927, 247, 935, 479, 943, 135, 951, 487, 959, 255, 967, 495, 975, 79, 983, 503, 991, 263, 999, 511, 1007, 143, 1015, 36, 1023, 145, 525, 273, 529, 35, 533, 277, 537, 149, 541, 281, 545, 85, 549, 285, 553, 153, 557, 289, 561, 53, 565, 293, 569, 157, 573, 297, 577, 89, 581, 301, 585, 161, 589, 305, 593, 17, 597, 309, 601, 165, 605, 313, 609, 93, 613, 317, 617, 169, 621, 321, 625, 57, 629, 325, 633, 173, 637, 329, 641, 97, 645, 333, 649, 177, 653, 337, 657, 9, 661, 341, 665, 181, 669, 345, 673, 101, 677, 349, 681, 185, 685, 353, 689, 61, 693, 357, 697, 189, 701, 361, 705, 105, 709, 365, 713, 193, 717, 369, 721, 39, 725, 373, 729, 197, 733, 377, 737, 109, 741, 381, 745, 201, 749, 385, 753, 65, 757, 389, 761, 205, 765, 393, 769, 113, 773, 397, 777, 209, 781, 401, 785, 5, 789, 405, 793, 213, 797, 409, 801, 117, 805, 413, 809, 217, 813, 417, 817, 69, 821, 421, 825, 221, 829, 425, 833, 121, 837, 429, 841, 225, 845, 433, 849, 45, 853, 437, 857, 229, 861, 441, 865, 125, 869, 445, 873, 233, 877, 449, 881, 73, 885, 453, 889, 237, 893, 457, 897, 129, 901, 461, 905, 241, 909, 465, 913, 13, 917, 469, 921, 245, 925, 473, 929, 133, 933, 477, 937, 249, 941, 481, 945, 77, 949, 485, 953, 253, 957, 489, 961, 137, 965, 493, 969, 257, 973, 497, 977, 49, 981, 501, 985, 261, 989, 505, 993, 141, 997, 509, 1001, 265, 1005, 20, 1009, 81, 1013, 28, 1017, 269, 1021, 37, 522, 82, 524, 272, 526, 146, 528, 274, 530, 521, 532, 276, 534, 148, 536, 278, 538, 84, 540, 280, 542, 150, 544, 282, 546, 52, 548, 284, 550, 152, 552, 286, 554, 86, 556, 288, 558, 154, 560, 290, 562, 16, 564, 292, 566, 156, 568, 294, 570, 88, 572, 296, 574, 158, 576, 298, 578, 54, 580, 300, 582, 160, 584, 302, 586, 90, 588, 304, 590, 162, 592, 306, 594, 8, 596, 308, 598, 164, 600, 310, 602, 92, 604, 312, 606, 166, 608, 314, 610, 56, 612, 316, 614, 168, 616, 318, 618, 94, 620, 320, 622, 170, 624, 322, 626, 26, 628, 324, 630, 172, 632, 326, 634, 96, 636, 328, 638, 174, 640, 330, 642, 58, 644, 332, 646, 176, 648, 334, 650, 98, 652, 336, 654, 178, 656, 338, 658, 23, 660, 340, 662, 180, 664, 342, 666, 100, 668, 344, 670, 182, 672, 346, 674, 60, 676, 348, 678, 184, 680, 350, 682, 102, 684, 352, 686, 186, 688, 354, 690, 34, 692, 356, 694, 188, 696, 358, 698, 104, 700, 360, 702, 190, 704, 362, 706, 62, 708, 364, 710, 192, 712, 366, 714, 106, 716, 368, 718, 194, 720, 370, 722, 10, 724, 372, 726, 196, 728, 374, 730, 108, 732, 376, 734, 198, 736, 378, 738, 64, 740, 380, 742, 200, 744, 382, 746, 110, 748, 384, 750, 202, 752, 386, 754, 42, 756, 388, 758, 204, 760, 390, 762, 112, 764, 392, 766, 206, 768, 394, 770, 66, 772, 396, 774, 208, 776, 398, 778, 114, 780, 400, 782, 210, 784, 402, 786, 31, 788, 404, 790, 212, 792, 406, 794, 116, 796, 408, 798, 214, 800, 410, 802, 68, 804, 412, 806, 216, 808, 414, 810, 118, 812, 416, 814, 218, 816, 418, 818, 44, 820, 420, 822, 220, 824, 422, 826, 120, 828, 424, 830, 222, 832, 426, 834, 70, 836, 428, 838, 224, 840, 430, 842, 122, 844, 432, 846, 226, 848, 434, 850, 12, 852, 436, 854, 228, 856, 438, 858, 124, 860, 440, 862, 230, 864, 442, 866, 72, 868, 444, 870, 232, 872, 446, 874, 126, 876, 448, 878, 234, 880, 450, 882, 46, 884, 452, 886, 236, 888, 454, 890, 128, 892, 456, 894, 238, 896, 458, 898, 74, 900, 460, 902, 240, 904, 462, 906, 130, 908, 464, 910, 242, 912, 466, 914, 6, 916, 468, 918, 244, 920, 470, 922, 132, 924, 472, 926, 246, 928, 474, 930, 76, 932, 476, 934, 248, 936, 478, 938, 134, 940, 480, 942, 250, 944, 482, 946, 48, 948, 484, 950, 252, 952, 486, 954, 136, 956, 488, 958, 254, 960, 490, 962, 78, 964, 492, 966, 256, 968, 494, 970, 138, 972, 496, 974, 258, 976, 498, 978, 14, 980, 500, 982, 260, 984, 502, 986, 140, 988, 504, 990, 262, 992, 506, 994, 80, 996, 508, 998, 264, 1000, 510, 1002, 142, 1004, 21, 1006, 266, 1008, 19, 1010, 50, 1012, 24, 1014, 268, 1016, 32, 1018, 144, 1020, 38, 1022, 270, 531]

As per @xiota's additional suggestion, running pixels = pixels.sort {|a,b| a <=> b} creates a sort of "reverse" image of the one generated with pixels = pixels.sort {|a,b| b <=> a} (notice the change of a and b's position when being compared). Here's the output:

Answer 1

In support of Comparable mixin, a default <=> or spaceship operator for pixels is defined in the function Pixel_spaceship in rmpixel.c. However, in your use of the sort method, you define your own code block that overrides the <=> operator, and yours takes a single argument rather than two which would be correct, so the definition is broken and will not work correctly in sorting. The undefined sorting result will depend on the sorting algorithm used. Ruby sorts arrays using the Quicksort algorithm, which is a divide-and-conquer algorithm, dividing the problem into progressively smaller sub-problems. You can see this behavior in your output image, which I think is an artifact from using Quicksort with a broken <=> operator.

On some computing platforms, Ruby uses the platform's Quicksort implementation (see rb_sort in array.c and ruby_qsort in util.c), so the undefined results also vary depending on the platform, as demonstrated in comments to the question. See util.c for Ruby's own Quicksort implementation. For someone who wants to take the time to tackle this, you'd replace each <=> comparison by constant 1, and simplify the code.

Let's plot the question's ruby 2.5.1p57 (2018-03-29 revision 63029) [x86_64-darwin16] platform "sorted" 0..1023 test data (labeled Source #) as function of position, using | markers to more clearly see step sizes:

Ignoring small-scale detail, as if we were looking at a very large image from a very large distance, we can deduce that with $n=0,1,2,3,\ldots$, each $2$nd $1/(n+2)$ part of the output image is an additive mixture of scaled parts of the input image:

• the $2$nd $1/2$ part of the image enlarged by a factor of $2^{-n}$ with mixing weight $1/2$,
• the $2$nd $1/4$ part of the image enlarged by a factor of $2^{1-n}$ with mixing weight $1/4$,
• the $2$nd $1/8$ part of the image enlarged by a factor of $2^{2-n}$ with mixing weight $1/8$,
• the $2$nd $1/16$ part of the image enlarged by a factor of $2^{3-n}$ with mixing weight $1/16$,
• ... (until the part size goes to zero).

Here, enlarged by a factor of $2^x$ means that if $x < 1$ then the image part in question is reduced in size by factor $2^{-x}$ and replicated (tiled), and if $x > 1$, then the image part is enlarged by factor $2^x$ and the $2^x$ enlarged $1/2^x$ sub-parts are additively mixed with equal weight $1/2^x$.

The small-scale detail ignored in this analysis is the interlacing, which from a large distance looks like additive mixing. Also some unexplained details that don't seem to scale with the data size are ignored.

Here is a Python script (sorry, I don't know Ruby) that reproduces most of the aesthetic qualities of the picture, not by using the above analysis but by mimicking the interlacing in the plot above:

from PIL import Image
import requests
from io import BytesIO

response = requests.get("https://i.stack.imgur.com/T520A.jpg")
img = Image.open(BytesIO(response.content))
pix = img.load()
w, h = img.size
pix_flat = []
for y in range(h):
    for x in range(w):
        pix_flat.append(pix[x, y])

for y in range(h):
    for x in range(w):
        if (x > 0 or y > 0):  # Do not touch pix[0, 0]
            i = x + w*y     
            j = i
            while j < w*h//2:
                j *= 2
            k = i
            while k & 1:
                j >>= 1
                k >>= 1
            pix[x, y] = pix_flat[j]

img.save("output.jpg", "JPEG")

Result #1:

We can get rid of the vertical striping by replacing the interlacing by weighted summation in a linear color space, assuming that the source image is in sRGB color space, in Python:

from PIL import Image
import requests
from io import BytesIO

response = requests.get("https://i.stack.imgur.com/T520A.jpg")
img = Image.open(BytesIO(response.content))
pix = img.load()
w, h = img.size

# These originate from https://stackoverflow.com/questions/34472375/linear-to-srgb-conversion
def srgb2lin(s):  
    if s <= 0.0404482362771082:
        lin = s / 12.92
    else:
        lin = pow(((s + 0.055) / 1.055), 2.4)
    return lin

def lin2srgb(lin):
    if lin > 0.0031308:
        s = 1.055 * (pow(lin, (1.0 / 2.4))) - 0.055
    else:
        s = 12.92 * lin
    return s

pix_flat_lin = []
for y in range(h):
    for x in range(w):
        pix_flat_lin.append([srgb2lin(pix[x, y][k]/255) for k in range(3)])

for y in range(h):
    for x in range(w):
        if (x > 0 or y > 0):  # Do not touch pix[0, 0]
            i = x + w*y     
            j = i
            while j < w*h//2:
                j *= 2
            pixel_lin = [pix_flat_lin[j][k] * 0.5 for k in range(3)]
            j >>= 1
            m = 0.25
            while j:
                pixel_lin = [pixel_lin[k] + pix_flat_lin[j][k] * m for k in range(3)]
                j >>= 1
                m *= 0.5
            pix[x, y] = tuple([int(round(lin2srgb(pixel_lin[k])*255)) for k in range(3)])
    print(str(y+1)+"/"+str(h))

img.save("output2.jpg", "JPEG")

Result #2:

This still has the horizontal stripes.

Answer 2

I'm not a Ruby programmer, so there will be a lot of handwaving in this answer. If you are particularly concerned about skipped details, you'll have to look in the Ruby source code.

• In array.sort {|a,b| a <=> b}, the sort method of array is being called with a block { ... }. The arguments used by the block are given by |a,b|. The comparison "spaceship" operator is a <=> b. It returns 1, 0, -1, depending on whether a is "larger" than b.

• In the code you wrote, pixels = pixels.sort {|p| p.red + p.green + p.blue}, you are adding three positive integers. The result is another positive integer that is interpreted as 1. So sort behaves as if the comparison is always evaluating as "larger". Instead of separating, or recombining, values into arrays based on size, as you would expect sort to behave, they are split based on the order in which they appeared in the original array.

  This causes smaller copies of the original image to be created when every other pixel is put into a different array. This is repeated for every array, until we're down to pairs. The arrays are then merged back together to get the result you see. (This is a major handwaving checkpoint. You'll have to look at the sort implementation to see exactly how the arrays are merged.)

• The output ends up looking the same as either of the following. It doesn't matter if you have |p| or |a,b| because the arguments are ignored.

  pixels = pixels.sort {|p| 1}
  pixels = pixels.sort {|a,b| 1}
  

  

• To get the result you're seeking, you can use:

  pixels = pixels.sort {|a,b| (a.red + a.green + a.blue) <=> (b.red + b.green + b.blue)}
  

  

• The default Pixel_spaceship operator that Olli Niemitalo mentions is different from the function you intend, so pixels = pixels.sort {|a,b| a <=> b} has a striped appearance. Using b <=> a will reverse the order.