HOME Mathematics Computer Science
Midpoint Displacement in one dimension
Prerequisites
Show All
Hide All
Min-Max Normalization
Show/Hide

Introduction
  • Min-max normalization is an operation which rescales a set of data.
  • This can be useful when:
    • Comparing data from two different scales
    • Converting data to a new scale
  • In most situations, data is normalized to a fit a target range of [0, 1]
    • The smallest value in the original set would be mapped to 0
    • The largest value in the original set would be mapped to 1
    • Every other value would be mapped to a value somewhere between these two bounds
  • It is also called:
    • Feature Scaling
    • Min-Max Scaling
    • Rescaling
    • Normalization
Normalizing to [0, 1]
  • A set of numbers will have:
    • A smallest value:
      • This is also called the lower bound or least element
      • It is denoted: min(x)
    • A largest value:
      • This is also called the upper bound or greatest element
      • It is denoted: max(x)
    • A range:
      • The difference between the smallest and largest values
      • It is denoted: max(x) - min(x)
  • Normalization is the process of changing the lower and upper bounds to be 0 and 1 respectively
Algorithm
  1. First we modify the data to have a lower bound of 0. To do this we subtract min(x) from each value:
  2. Then we modify the data to have an upper bound of 1. We do this by dividing each value by the original range:
  3. Finally, if we combine these two steps we get:
Example
Normalize the following data:
  1. First we calculate the lower bound, upper bound, and range:
    • min(x) = 7
    • max(x) = 21
    • max(x) - min(x) = 14
  2. Next we subtract the lower bound from each value:
  3. Finally, we divide by the range:
Code
import numpy as np

def normalize(x):
    min = np.min(x)
    max = np.max(x)
    range = max - min

    return [(a - min) / range for a in x]


x = [7, 21, 13, 15]
normalizedX = normalize(x)

print(normalizedX) # prints: [0.0, 1.0, 0.42857142857142855, 0.5714285714285714]
Normalizing from [0, 1]
  • If our numbers are in the range [0, 1] then we can scale them to have a different lower and upper bound
  • To achieve this, we simply do the reverse of normalization:
    1. Find the new range by subtracting the lower bound from the upper bound
    2. Multiply each value by the new range
    3. and add the new lower bound to each value:
Example
Normalize the following data to have a lower bound of 3 and an upper bound of 24:
  1. first we calculate the range:
  2. Then we multiply each value by the range:
  3. Finally, we add the lower bound to each value:
Code
def normalize(normalizedX, newLowerBound, newUpperBound):
    range = newUpperBound - newLowerBound

    return [a * range + newLowerBound for a in normalizedX]


normalizedX = [0.0, 1.0, 3/7, 4/7]
x = normalize(normalizedX, 3, 24)

print(x) # prints: [3.0, 24.0, 12.0, 15.0]
Normalizing from one range to another
  • Sometimes we need to normalize data in which neither the source range nor the target range is [0, 1]
  • In these situations, we first normalize the data to range of [0, 1], and then normalize it again to the true target range.
  • These two steps can be combined:
Code
import numpy as np

def normalize(x, newLowerBound, newUpperBound):
    min = np.min(x)
    max = np.max(x)
    range = max - min
    newRange = newUpperBound - newLowerBound

    return [((a - min) / range) * newRange + newLowerBound for a in x]


x = [7, 21, 13, 15]
y = normalize(x, 3, 24)

print(y) # prints: [3.0, 24.0, 12.0, 15.0]
2n + 1
Show/Hide

Introduction
  • We can generate a sequence of integers using the following equation:
  • These numbers have an important property when it comes to calculating their midpoints:
    • To calculate the midpoint between two numbers, you can use this equation:
    • For example: the midpoint between 1 and 17 is:
  • The midpoint between 1 and any number in the sequence 2n + 1 is equal to the previous number in the sequence
  • For example:
    • The midpoint between 1 and 33 is 17
    • The midpoint between 1 and 17 is 9
    • The midpoint between 1 and 9 is 5
  • Proof:
    • the midpoint between 1 and 2n + 1 is:
  • A number which is in the sequence 2n + 1 can be recursively split into two segments until each segment has a size of 1:
Code
from collections import deque

# The following code creates an array of numbers starting at 0 and smoothly increasing to 255

n = 3

# creates an array of 0's of size 2^n + 1
x = [0]*(2**n + 1)

# set the value for the last element
x[len(x) - 1] = 255

# we create a queue of the line segments we need to subdivide
q = deque()

# and add the first segment to it
q.append((0, len(x) - 1))

# now we go through and subdivide each segment
while len(q) != 0:
    left, right = q.popleft()
    midpoint = (left + right) // 2

    # set the midpoint to the average of the two ends
    x[midpoint] = (x[left] + x[right]) // 2

    # if the width of the segment is greater than 2 then it can be subdivided
    if right - left > 2:
        q.append((left, midpoint))
        q.append((midpoint, right))

print(x) # prints: [0, 31, 63, 95, 127, 159, 191, 223, 255]

Midpoint Displacement in one dimension

Introduction
  • Midpoint Displacement is a simple algorithm for generating realistic looking height ranges.
  • It is a recursive algorithm that subdivides a line into segments, adding a decreasing amount of randomness at each round.
Algorithm
  1. We start with a set of heights initialized to 0. The length of the set must conform to 2n + 1.
  2. Then we set the first and last heights to random value. In this case they are 5 and 2:
  3. Next we set the midpoint to the average of the two endpoints:
  4. And move (or displace) the midpoint up or down by a random amount. In this case we move it down by 1:
  5. And repeat the midpoint displacement recursively for the newly created line segments:
  6. Each time we subdivide the line segments, the amount we displace the midpoint should also decrease:
Code
from PIL import Image
import PIL.ImageDraw as ImageDraw
import random
import numpy as np
from math import floor
from collections import deque

def main():
    imageWidth = 513
    imageHeight = 256
    roughness = 200

    # we initialize all the heights to 0
    heights = [0]*imageWidth

    # and then initialize the first and last heights to random values
    heights[0] = random.randint(0, 256)
    heights[imageWidth - 1] = random.randint(0, 256)

    # we create a queue of the line segments we need to subdivide
    q = deque()

    # and add the first segment to it
    q.append((0, imageWidth - 1, roughness))

    # now we go through and subdivide each segment
    while len(q) != 0:
        left, right, randomness = q.popleft()
        center = (left + right + 1) // 2

        # set the midpoint to the average of the two ends
        heights[center] = (heights[left] + heights[right]) // 2

        # and then add some randomness
        heights[center] = heights[center] + random.randint(-randomness, randomness)

        # if the width of the segment is greater than 2 then it can be subdivided
        if right - left > 2:
            # when we add the new line segments to the queue, we reduce the amount of randomness
            q.append((left, center, floor(randomness // 2)))
            q.append((center, right, floor(randomness // 2)))

    # finally we render these heights
    im = renderHeights(heights, imageWidth, imageHeight)
    im.save("test.png", "PNG")
    im.show()


# draws the given heights on the image
# the heights should be normalized to be between 0 and image.height
def renderHeights(heights, imageWidth, imageHeight):
    imagePadding = 32

    # we normalize the heights so that its minimum and maximum values
    # fit nicely on the image we are about to draw
    heights = normalize(heights, imagePadding, imageHeight - imagePadding)

    # we need to convert the heights to a series of points to be plotted
    points = [(i, heights[i]) for i in range(0, imageWidth)]

    # and add the corners so that tha polygon is nice and closes properly
    points.insert(0, (0, 0))
    points.append((imageWidth - 1, 0))

    im = Image.new("L", (imageWidth, imageHeight))
    draw = ImageDraw.Draw(im)
    draw.polygon(points, fill=200)

    return im


# normalizes an array of numbers such that the smallest number will be
# the newLowerBound and the largest number will be the newUpperBound
# every other number will be scaled to be between those points
def normalize(data, newLowerBound, newUpperBound):
    min = np.min(data)
    max = np.max(data)
    range = max - min
    newRange = newUpperBound - newLowerBound

    return [(a - min) * newRange / range + newLowerBound for a in data]


main()