DEV Community: 101arrowz

Building a Mobile Document Scanner with Zero Dependencies: The Hough Transform

101arrowz — Mon, 03 Jan 2022 21:49:00 +0000

After the Sobel operator provides the gradient of the image, we're most of the way to finding the edges of the document. If you don't know what the Sobel operator is, I strongly recommend reading the previous article in the series first.

However, having a visual representation of the edges isn't useful; we need to have mathematical representations for every edge in the image in order to find their intersections (the corners of the document), for which we can use the Hough transform.

The Hough transform allows us to find imperfect matches for arbitrary visual patterns using a bucketed voting system. There are two ways to understand this algorithm: mathematical and intuitive. Let's go through both before discussing how we can implement it.

In Mathematical Terms

Since the Hough transform can technically find circles, ellipses, triangles, or any other arbitrary pattern, we would need an individual mathematical analysis for each type of pattern we want to detect.

For the purposes of this project, we searched for lines, which are what the Hough transform was originally designed for and are therefore the easiest type of pattern to detect. (If you're wondering why we don't just look for rectangles to find the document, we'll get to that near the end).

First, let's decide how we want to represent our lines mathematically. A natural choice might be the famous:

y = m x + b

This form allows us to represent any line that could possibly exist in 2-D space by modifying the parameters m (the slope of the line) and b (the y-intercept). If we want a line with a 30 degree incline that's 1200 pixels from the bottom of the image, we can use:

\tan 30\degree\newline b = 1200\newline \vphantom{space}\newline y = 0.577x + 1200

This appears visually accurate when plotted too:

The one issue with this representation is what happens when we try to create a vertical line. Vertical lines do not move horizontally, their run is always zero while their rise is an arbitrary number. Technically, we can use either positive or negative infinity to represent the slope, but then we would have no way to know where on the x-axis the line is located, since this equation only specifies the y-intercept.

Although it's possible to work around this problem, it's also important to consider the fact that we want to be able to differentiate between visually different lines, but this form makes it difficult to do so. Consider these four lines:

The black line has slope 0.1 (i.e. m = 0.1), the purple line slope 2, the blue line slope 10, and the red line slope 30.

Although visually, the red and blue lines are very similar visually, their slopes vary by 20, and although the purple and black lines appear different, their slopes differ by only 1.9. If we want to use slope, we would need to find some way to emphasize small differences in slope at lower values.

Instead of dealing with all of these problems, we can represent the lines more accurately using polar coordinates.

"Normal" coordinates are also known as Cartesian coordinates: they are represented as (x, y), where x is the location on the horizontal axis and y is the location on the vertical axis. Polar coordinates are instead represented as (r, Θ), where r is the distance from the origin and theta is the angle counterclockwise from what would be the positive x-axis in Cartesian coordinates. Here are a few examples:

Polar coordinates and Cartesian coordinates always satisfy the following equations:

r\cos\theta\newline y = r\sin\theta\newline \vphantom{space}\newline r = \sqrt{x^2 + y^2}\newline \theta = \mathrm{atan2}(y, x)

Although we can convert our original form y = mx + b into polar, we'd end up with the same issues around visual similarity and vertical lines. Instead, we can use Hesse normal form, which can represent lines using a single polar coordinate.

Most online explanations make Hesse normal form more complicated than necessary for our purposes, so here's an intuitive explanation. Imagine you have an arbitrary polar coordinate. Draw a segment from the origin to this coordinate. Now, draw a line perpendicular to that segment that contains the coordinate. This line is uniquely identified by the polar coordinate.

Here's a graph of what that looks like:

The green line segment connects the origin to the point, so the perpendicular purple line is the line we can describe using the point (5, 30°).

This gives us an easy way to differentiate between lines: if the points are far from one another, the lines are visually different. There are no more cases where a small change in a variable causes a major visual change for the line because r and theta each have a "linear" visual effect. For example, a change in theta of 10° will always cause a similar visual difference for the line, no matter what the exact value of theta is.

More importantly, Hesse normal form makes it easy to find the lines that any coordinate in Cartesian space lies on. If we know the angle Θ in Hesse normal form and have a Cartesian coordinate (x, y) that line passes through, we can solve for r:

x\cos\theta + y\sin\theta

In the above equation, any two points that lie on the same line of angle Θ will produce the same value of r. We'll discuss why this quality is so important soon. For now, I'll provide an intuitive explanation of the voting process in the Hough transform.

Buckets of Paint

Imagine you've been tasked with finding the most common color of paint out of one million buckets.

One solution could be to go through each bucket and keep a tally of how many buckets you've seen with each color. However, that approach offers very limited precision: you can't give an exact color but rather something general like "green" or "yellow." Additionally, this solution does not take into account variations in the amount of paint per bucket.

A better solution would be to create a large grid of empty paint tanks, where going up the grid yields brighter colors and moving to either side yields a different hue. In other words, we could find where in the following plot each color lies:

I know this plot disregards saturation, but for the purposes of this example we can assume every color of paint is fully saturated.

Imagine that there are grid lines along every degree of hue and every 0.01 increase in value in the above plot. We can estimate the hue and value of each bucket of paint, then dump the contents of the bucket into the tank in the grid corresponding with that hue and value.

For instance, if we come across a bucket with dark red paint, we would dump it into one of the tanks in the bottom left corner of the grid (since the bottom region has darker colors and the left region has red colors).

At the end, we could find the tanks with the most paint to determine the most common color in the paint.

This approach solves two of the problems with our original tallying approach. Since we're pouring out the buckets into a grid, we accurately account for any differences in the amount of paint per bucket. More importantly, our final result is an exact color, and in theory the maximum error versus the true most common color is the area of one tank (one degree error in hue and 0.01 error in value).

It's important to note that this approach would be a poor choice if we did not have so many buckets of paint as data points. For instance, if there were only a few thousands buckets, the majority of the 18,000 tanks would be completely empty after we finished pouring all the paint out, and tiny errors in our approximation of the color would cause incorrect results.

For example, if we found ten buckets with almost the exact same shade of yellow with slightly different brightness, we might place them in ten separate tanks, whereas two bright red paint buckets that we estimated to have the exact same hue and brightness would go in the same tank. At the end, we would find two buckets worth of paint in the bright red tank, and only one bucket worth in each of the yellow tanks, so our algorithm would decide that red was the most common color even though yellow was clearly more prevalent.

Where's this analogy going?

If you recall from earlier, we discussed how Hesse normal form lets us represent any line with a point in polar coordinates, and how visually similar lines can be represented by coordinates that are mathematically near each other. Let's discuss how we can actually use it to find lines in our gradient image.

For every pixel in the image, we can find all of the lines going through the image that the pixel could possibly lie on. For now, we'll assume that a line in every direction is possible. We can loop from Θ = 0° to Θ = 179° in one degree increments and solve for r using the equation from earlier to find 180 potential lines in Hesse normal form (r, Θ) per pixel. (Note we don't go to 359° because lines extend infinitely in two opposite directions, so any angle above 180° yields a line identical to some angle below 180°.)

So now we have 180 mathematical lines per pixel in the image. What can we actually do with that?

Remember that we're trying to find the lines that correspond with edges in the image; in other words, lines that go through many pixels with a high gradient magnitude. If we consider the 180 lines in each pixel with high gradient magnitude, we can search for the lines that appear in multiple of those pixels and definitely claim that those are the edges in the image.

However, it's almost impossible to find the exact same (r, Θ) in two separate pixels because we're not restricted to integers for r. Therefore, we need to find the lines that most nearly go through pixels with high gradient magnitude.

The paint-bucket problem and the actual problem we have to solve are actually quite similar. In the paint-bucket problem, we were searching for an approximate paint color that was most common in terms of hue and value. Here, we need to find an approximate line that is most common among all the lines passing through pixels with high gradient magnitude in terms of r and Θ.

We can actually apply the same solution we used for the paint-bucket problem here! We create a grid of numbers ranging from Θ = 0° to Θ = 179° as you move vertically, and from r = -d to r = d as you move horizontally, where d is the hypotenuse of the dimensions of the image. For every pixel in the image, we find every line that passes through that pixel and add the value of the gradient magnitude to each position in the grid that corresponds to one of the lines.

This process is known as voting in the Hough transform because each line we calculate "votes" for the position in the grid most similar to itself, and the positions with the most votes are the edges we are looking for.

At the end, the locations with the greatest numbers must have an (r, Θ) line that passes through many points with high gradient magnitude. Therefore, these locations are actually the edges of the image in Hesse normal form.

At the end of this process, we can trace the edges of the image. We actually have some promising results!

As you can see above, we detected the edges of the document in red. Since they're lines and not segments, we didn't stop at the corners of the document, but we can easily find the intersections of these lines to find the corners of the document, which is one of the last steps for our document scanner!

Finishing up

There are two optimizations we can make to this algorithm. Let's recap. After finding the gradient magnitude of the image, we iterate through each pixel and find lines of each angle from 0° to 179° that go through that pixel in terms of (r, Θ) (Hesse normal form). For each of these 180 lines, we use the value of Θ as-is and round the value of r to an integer to calculate a row and column in a grid of numbers. We then add the gradient magnitude at the original pixel to the entry in the grid. At the end, the positions in the grid with the greatest values correspond to lines in (r, Θ) that are most likely to be edges.

At the moment, we assume that every angle from 0° to 179° is equally likely for a line going through any given point. However, if you remember from the previous article, we actually have the gradient magnitude AND the gradient direction from the Sobel operator. We know that the gradient direction is the direction of steepest ascent for the intensity of the image, so it should actually be nearly perpendicular to the edge at every pixel.

To envision this fact, imagine that you're standing on the edge of a cliff, and think about your distance from the center of the Earth as a function of your lateral position. You would come much closer to the center of the Earth if you stepped forwards, whereas moving in any other direction wouldn't change your vertical position as much, so the direction of the gradient is forwards. (I don't recommend verifying this experimentally.)

If you stepped backwards, you would move away from the edge of the cliff. The direction of the actual edge of the cliff is to your left and right, i.e. perpendicular to the gradient direction.

Using the knowledge that edges are nearly perpendicular to the gradient, we can stop assuming that every angle is equally likely. For each point in the image, we will only allow the lines nearly perpendicular to the gradient at each pixel to vote instead of checking every angle.

The other optimization is adjusting the sizes of each bin in the grid. I found empirically that one degree of difference in the angle was actually a pretty substantial visual difference. I decided to use an integer from 0 to 255 to represent the angle instead, not only because it made the size of each box 0.7° instead of 1° but also because values from 0 to 255 fit in a single byte, which was nice to deal with for practical reasons.

However, the grid portion of the Hough transform was already taking a lot of memory, and with this change the amount was more than I was satisfied with. Therefore, I increased the size of the bins for r from 1 to 2. This halved the amount of memory necessary but only increased the maximum error for the edges detected from one pixel to two pixels, which is nearly unnoticeable.

Conclusions

In short, we've found mathematical representations of the edges in the image by applying the Hough transform to the output of the Sobel operator. This is possible because each edge-like pixel votes for all the lines it could lie on, and we take the lines with the most votes at the end to be the actual edges in the image.

At the end of this process, we've basically found a bunch of (r, Θ) lines that could potentially represent the edges of the document we're trying to find... or they could just be the edges of a desk, folder, or tablet that happened to be in the background of the image. Remember that image I showed you earlier with just the edges of the document being detected? That was after a LOT of beautification. Here's the actual output.

We still got the edges of the document, but there are a ton of duplicates due to imperfections in our algorithms, most of which have only been estimations. We also have a few false positives: the pen, the small notebook, and the keyboard in the background all looked like edges to our algorithm.

We need a way to filter out the false positives and duplicates while retaining the actual edges of the document. Then, we need to find the four edges most likely to be our document and use its corners to finish the document detection code. So in the next article, we'll discuss non-max suppression and how I designed a heuristic quadrilateral scoring function.

Building a Mobile Document Scanner with Zero Dependencies: The Sobel Operator

101arrowz — Mon, 27 Dec 2021 13:00:51 +0000

If you missed the previous article in this series (Divide and Conquer), you'll want to read it first so you understand what we're going to be discussing here.

The Sobel operator approximates the gradient magnitude and direction of an image at a specific pixel, but it can theoretically be applied to any discrete function of two variables. For those who don't remember or haven't studied multivariable calculus, let's discuss what that means. Otherwise, if you're familiar with calculus, feel free to skip past the next few sections of this article.

Derivatives

Single-variable mathematical functions take a single, numeric input variable and produce a single, numeric output. Simple, right? Here's an example:

3x\newline \vphantom{space}\newline f(0) = 0\newline f(2) = 6\newline f(10101) = 30303

If we were to write that in JavaScript:

function f(x) {
  return 3 * x;
}
console.log(f(1)) // 3
console.log(f(2)) // 6
// You get the idea...

If we plot the output on a vertical axis and the input on the horizontal axis (i.e. y = f(x)), we get this nice line:

You already know this, of course. Things get a bit more interesting when we calculate the slope of this line, which is a numerical representation of the "steepness" of the line and is computed by calculating "rise over run." Steeper functions have greater slopes. In this case, the function rises by 3 every time it runs by 1 (the y-value goes up 3 each time x goes up 1). Therefore, the slope is 3 / 1, or 3. We could also have seen that it rises up by 6 every time it runs by 1, and we would find the slope to be 6 / 2, which also evaluates to 3.

More specifically, the slope represents the rate of change of a function, or how much the function's output changes for a change in the input of 1.

What's the slope of a more complicated function, say

g(x) = x^2

? If we plot it, we see that the function gets more steep the further you go from x = 0, so the slope can't just be represented by a single number.

As it turns out, this function doesn't really have a slope. We can only calculate the slopes of the tangent lines at each value of x. The tangent line is a linear approximation of the original function that is identical to it near some point. Here's a plot of the function with a tangent line at x = 1:

The blue line seems to become the same as the red curve near x = 1, since (1, 1) is the point of tangency. As I mentioned above, we can calculate the slope of the tangent line at any point on the red curve. For this function, it turns out that the slope of the tangent line is equal to 2x at any x-coordinate. We call this the derivative of the function; the derivative is often denoted with an apostrophe we call "prime." Therefore:

3x\newline f'(x) = \frac{\mathrm{d} f}{\mathrm{d} x} = 3\newline \vphantom{space}\newline g(x) = x^2\newline g'(x) = \frac{\mathrm{d} g}{\mathrm{d} x} = 2x

We can say that "f-prime of x is 3, and g-prime of x is 2x" because for f(x), the tangent line is actually the same as the function itself (a property of all linear functions) and so the derivative is just the slope, whereas for g(x) we have to do some more work to find the slope of the tangent line. We'll get to why we care about the derivative in a second.

The derivative of a function is the instantaneous rate of change of that function. I don't want to make this article only on math, so I've skipped over a lot of details that you should really learn if you've never studied calculus (including how you actually calculate the derivative for an arbitrary function!) I highly recommend Khan Academy's Calculus 1 course, or this excellent video if you're in a rush.

Multivariable functions

Multivariable functions are often confusing to math students, but as a programmer you use them all the time! They're just functions that have more than one input variable. Here's an example:

f(x, y) = 3x + y^2

In JavaScript, that's just:

function f(x, y) {
  return 3 * x + y * y;
}

It's a bit harder to visualize mentally since we can't graph this on a 2-D plane anymore; we'd need a 3-D surface to show what this looks like. The function has both an x-axis and a y-axis for input, and now uses a z-axis for output. In the following image, the z-axis is vertical and the x- and y-axes are horizontal.

It doesn't really make sense to take a derivative of this function: it's a 3-D surface, not a curve, so there's an infinite number of tangent lines you can take at each point (x, y, f(x, y)) in every direction.

However, we can take the derivative if we specify which direction our tangent line is pointing on the horizontal plane. For example, we can calculate the slope of the tangent line in the positive-x direction. This is called the partial derivative with respect to x. We can do this for any arbitrary direction, but for many cases we only care about the partials with respect to the input variables (in this case, x and y). For this function:

y^2\newline \vphantom{space}\newline \frac{\partial f}{\partial x} = 3\newline \vphantom{space}\newline \frac{\partial f}{\partial y} = 2y

That means that the partial derivative with respect to x is 3, and the partial with respect to y is 2y. Taking partial derivatives is very easy if you know how to calculate derivatives: consider all other variables to be constants when you differentiate with respect to one. For example, when taking the partial with respect to x, we simply assume y is a constant value and therefore can disregard the y^2 term. (You can't just assume the values are zero, though; the partial with respect to x of xy is still y.)

There's a useful value for continuous multivariable functions called the gradient vector. If you're familiar with vectors, the gradient for a function of two variables (x and y) is defined as:

\nabla f = \left\langle \frac{\partial f}{\partial x}, \frac{\partial f}{\partial y} \right\rangle

In many cases, we really only care about the gradient direction and magnitude (which uniquely define the vector anyway). For any specific x and y, the gradient direction is the direction of "steepest ascent," i.e. the direction in the XY plane in which the output of the function is increasing the most, while the gradient magnitude is the value of the derivative in the gradient direction (in other words, the slope of the steepest tangent line in any direction at (x, y, f(x, y))). Here's how you compute these values (the bars represent magnitude, and theta is the angle):

\nabla f | = \sqrt{\left(\frac{\partial f}{\partial x}\right)^2 + \left(\frac{\partial f}{\partial y}\right)^2}\newline \vphantom{space}\newline \theta = \mathrm{atan2}\left(\frac{\partial f}{\partial y}, \frac{\partial f}{\partial x}\right)

If you've never done multivariable calculus before, this all may seem confusing, but it should start to feel quite intuitive over time if you truly understand preliminary calculus! Again, Khan Academy is your friend.

Where's the Computer Vision?

You may be wondering how all this theoretical math actually applies to document scanning. First, you need to rethink your idea of what an image is.

You probably already know that images are merely massive grids of pixels, where each pixel has a red, green, and blue, and potentially an alpha (opacity) value. Each of these values typically ranges from 0 to 255 (i.e. one byte represents each color/channel). By varying the values of each channel, you can create virtually any color from a single pixel, and together these colors make an image that can be displayed on screen.

Let's simplify things a bit by considering a grayscale image instead. Now, there's only one channel per pixel, which represents intensity. Let's also stop thinking of channels in terms of bytes and instead as merely real numbers (a floating-point value rather than an integer). So we have a grid of real numbers representing the brightness of the image at each pixel, or effectively at each point, in the grid. Now try to imagine that this image is actually just a function of x and y (which represent the coordinates of each pixel) that has an output of the image intensity. For example, if there's a brightness of 0.5 at the pixel at the thirtieth column from the left and the eight row from the bottom, we could say that:

f (30, 8) = 0.5

One question that might be running through your mind is "how exactly can an image be a function? We don't have intensity between pixel values. What's f(30.27, 8.13)?"

Although most functions you'll run across in standard math courses have a domain of all real numbers (that is, they are defined at every possible finite point), some functions are not defined everywhere. For example, f(x) = 1 / x is not defined at zero because 1 / 0 does not exist. The image is defined at only the specific integer coordinates where the image has a pixel, but it still qualifies as a function. So, in short f(30.27, 8.13) does not exist, nor does f(12, 1.5) or f(-1, 100).

Now, let's say we want to find the gradient of this image. Just like all other functions of more than one variable, it should be possible to take the gradient, right? Unfortunately, we have a problem: it's impossible to take the derivative of a function at a point where it is not continuous, so we can't calculate the partial derivatives and can't find the gradient.

Therefore, the best we can do is calculate an approximation of the gradient of the image. Over the years multiple heuristic and theoretical methods for estimating the gradient have been discovered, but one of the earliest techniques, the Sobel operator, has remained popular because it is relatively inexpensive while remaining accurate enough for most applications.

The Sobel operator specifies two convolution kernels that can be used to compute the partial derivatives with respect to x and y at each pixel. Popular variants of the Sobel kernels are as follows:

S_x = \begin{bmatrix} -3 & 0 & 3 \newline -10 & 0 & 10 \newline -3 & 0 & 3 \end{bmatrix}\newline \vphantom{space}\newline S_y = \begin{bmatrix} 3 & 10 & 3 \newline 0 & 0 & 0 \newline -3 & -10 & -3 \end{bmatrix}

For each of the above matrices, the convolution finds every 3x3 pixel region in the image and multiplies each intensity by the corresponding value in the matrix, then sums the results. The computed partial derivatives apply to the center pixel (which would be the second row, second column in each matrix). Using the partial derivatives, it's trivial to calculate the gradient magnitude and direction.

Here's an awesome video that explains convolutions in much better detail with some nice visualizations. You'll even learn how some neural networks work!

This algorithm was found to be effective after years of research and testing, so you don't need to understand why it works so well at approximating the gradient. However, you should be able to get a general intuition about what it does.

Consider the Sx matrix. If the intensities are about equal to the left and right of the center pixel, we can assume that not much change in the x-direction about the center pixel. As such, the weighted values cancel each other out since the filter is symmetric across the second column, and the calculated partial derivative is 0. However, in the following example the pixel values are very different:

\begin{bmatrix} 0.72 & 0.42 & 0.14 \newline 0.81 & 0.08 & 0.32 \newline 0.56 & 0.63 & 0.44 \end{bmatrix}

Logically, since the values change greatly, the rate of change must be high, so the partial derivative with respect to x must be large as well. It is estimated to be:

\newline-10 * 0.81 + 0 * 0.08 + 10 * 0.32 + \newline-3 * 0.56 + 0 * 0.63 + 3 * 0.44 \newline= -7.00

Since the maximum possible magnitude of the derivative with this convolution is 16, a magnitude of 7 is relatively high.

It's very important to keep in mind that the gradients computed by the Sobel operator are only meaningful in relation to each other, since modifying the weights would change the maximum magnitude of the computed derivative. If your aim were to calculate the partial derivative for an actual mathematical function rather than an image, the Sobel operator would not only yield inaccurate results but would also be scaled incorrectly. A more appropriate technique to estimate the partial derivative with respect to x on samples of actual, mathematically expressible function would be applying the following convolution kernel:

S_x = \begin{bmatrix} 0 & 0 & 0 \newline -0.5 & 0 & 0.5 \newline 0 & 0 & 0 \end{bmatrix}

This filter finds the slope of a linear approximation of the function using the two points one unit away from the center point in x, which is a theoretically more accurate estimation of the derivative.

To summarize: using some mathematical techniques, you can estimate the gradient vector for each point in an image even though discrete functions like images don't actually have derivatives.

Why do we care about the gradient of an image?

Let's go back to what the gradient actually represents. It describes the greatest rate of change you can find in any direction at some point in a function. For our image, the gradient encodes the greatest change in intensity that exists around a given pixel. If you think about it, what we visually consider to be the "edges" of things we see in an image are actually just pixel locations at which the intensity is change dramatically.

For example, at the edge of a piece of paper, the intensity changes from almost 1 (white) inside the paper to the intensity of the background across three pixels, causing a high gradient magnitude on edge pixels, whereas inside the paper any 3x3 region will have near-one values in all locations, yielding a very low gradient magnitude. Therefore, if we take the gradient magnitude of an image, we effectively emphasize the edges of all the objects in the image while suppressing areas with little change (i.e. the insides of those objects). A visual example should make this more clear. Original image:

Gradient magnitude:

Notice how the edges of the paper are almost white, and the outline of the text inside the page is gray, while the rest of the image is nearly black. This is the most critical step of edge detection and therefore is one of the key components of this document scanning app.

It's important to note that before actually doing the Sobel edge detection, we typically use a Gaussian blur to reduce the effects of image noise (which are often detected as edges due to the random spikes in intensity they cause). Additionally, we've downscaled the image substantially before even starting this process to reduce processing time.

However, we'll get to those steps in future articles, near the end of this series. Next, we'll discuss how we can use this gradient magnitude image to actually find mathematical representations of the edges in the image via the Hough transform.

Building a Mobile Document Scanner with Zero Dependencies: Divide and Conquer

101arrowz — Mon, 27 Dec 2021 13:00:32 +0000

The first step in diving into any new project is creating a mental list of steps to take to gradually build the first version. After the initial prototype is done, polishing and finalizing it is pretty easy (as long as you don't rework any foundational components). I had just about no knowledge of computer vision algorithms prior to creating my document scanner, so I started with a high-level plan and broke each step into multiple smaller tasks that I could tackle one at a time. I thought the process would go something like this:

Get an image containing a document from the user
Find the document in the image
Transform the perspective so that the document fills the full rectangular region of a new image

If you saw the first part of this series, you'll remember how we visualized these steps.

Step 1: Original photo taken by the user

Step 2: Found the bounding region of the document in the image

Step 3: Transformed the perspective as if we were looking at the document head-on

With this plan in mind, I began my research. As I would soon discover, these steps vary dramatically in their difficulty. Step 1 is trivial, and I had a working image selection UI by the end of my first day working on the project. Step 3 is complex but relatively straightforward: this excellent Stack Exchange answer even provided a rudimentary implementation of perspective transformation in JavaScript, which I would modify lightly to use in my prototype. However, step 2 is incredibly difficult and needs to be broken down into several smaller components.

Initially, I thought the easiest way to find a document in an image would be to find the four most corner-like points in the image and take those to be the corners of the actual document (which I assumed to be a rectangle). This led me down a wild-goose-chase involving Harris corner detection and contour detection, but after finding no success in my hacked-together implementations, I tried researching on a higher level.

I eventually found this post from Dropbox, which gave me an overview of the current state-of-the-art techniques for document detection. Instead of searching for four corners, my program would find all the edges in the image, then look for the four of them most likely to be the edges of the document. More specifically, I would need to devise a scoring function to rank all the combinations of four edges and use the combination with the highest score in my perspective transformation code.

I devised a few improvements over Dropbox's techniques. They used the Canny edge detection algorithm to create a visual representation of the edge-like regions in the image, then applied a Hough transform to that output to find the mathematical representations of the most likely edges in the image.

Instead, I opted to use only the first step of Canny, the Sobel operator, and the gradient direction it generated (which is usually treated as a side-effect) to reduce the number of votes in Hough space. This change dramatically improves performance (I'm estimating by 5x or more) and reduces the amount of noise that appears in the lines detected via the Hough transformation.

Dropbox also checked all combinations of four edges, including those that were geometrically impossible to be a document (for instance, where two "sides" of the paper cross each other and make an hourglass shape instead of a quadrilateral) and filtered out those impossible shapes afterwards. I only considered each combination of four lines that made a valid quadrilateral, which also improves performance a bit, but more importantly makes it easier to design an appropriate scoring function by reducing the scope of the input it has to deal with.

Lastly, I opted to downscale the images before applying all of these algorithms because doing so reduces the chance that text inside the document causes issues during edge detection, and because it improves performance quadratically with respect to the scaling factor while having a theoretical maximum impact of the scaling factor on the location of each edge. In simpler terms, reducing the width and height of the image by 5x would improve performance by 25x but at worst would cause the edges detected to be offset by 5 pixels compared to their true locations, and when the input images are usually at least 1080p, that small error is not noticeable in the final image after projective transformation.

After finishing my research, my revised plan was as follows:

Get an image containing a document from the user
Find the document in the image
- Convert the image into a downscaled, grayscale version
- Apply Gaussian blur to reduce noise
- Use the Sobel operator to find the gradient magnitude and direction at each pixel
- Use the Hough transformation to find the score for each possible line that passes through the image. Bucket the angle of each line into roughly 1 degree increments from 0 to 180 degrees, and the position into 2 pixel increments from the negative to the positive value of the hypotenuse of the dimensions of the image
- Use the gradient direction from the Sobel operator to add more weight in the Hough transformation to edges nearly orthogonal to the gradient at each pixel
- Find the top few thousand lines in the Hough transformation and apply non-maximum suppression to find a few dozen lines that have the greatest final score
- Sift through every combination of four lines that make valid quadrilaterals and apply a heuristic scoring function to find the candidate most likely to be the document
- Find the intersections of the lines in the best candidate to find the four corners of the document
Use a projective transformation to warp the perspective of the original photo into the final image
- Compute a projective transformation: use some matrix algebra to solve linear equations that map the coordinates of the corners of the document into basis vectors representing homogeneous coordinates
- Do the same in reverse to map the homogeneous coordinates to 2D coordinates onto a flat, rectangular plane representing the document from a head-on view (and thus the final image)
- Iterate over every destination coordinate in the projected image and find the source coordinate from the original RGB image (which will likely consist of decimals and not integers)
- Use bilinear interpolation to simulate the pixel values at the decimal source coordinates and use those values at the destination coordinates to construct the projected image

If some of that flew over your head, don't worry; I'm only writing this description after I've finished the project and have struggled through the math behind each of these algorithms. We'll go into more depth about how each step works in the next article, starting with the Sobel operator.

Building a Mobile Document Scanner with Zero Dependencies: Environment and Setup

101arrowz — Mon, 27 Dec 2021 13:00:16 +0000

I had two primary goals for this project: to learn about the computer-vision algorithms and techniques used in document scanning, and to use that knowledge to build a program that I would actually prefer using over existing apps like CamScanner.

I wanted to be able to use my final product on iOS, macOS, Android, and Windows, but I did not want to have to maintain four separate native codebases. Flutter seemed to be a good option, but I'm not well-versed in Dart, and Flutter's supposed performance advantages over web apps are overblown according to my local tests. Therefore, I opted to use a Progressive Web App (PWA) architecture for my document scanner.

Computer vision often involves multiple expensive operations on an image, so it would be logical to use WebAssembly for the actual document detection and use JavaScript only for the UI. Although I'm quite familiar with Rust and compiling to WASM, I'm a fan of pushing JS to its limits and I wanted to see just how fast JavaScript can be for such a computationally intensive task; turns out, JS is actually fast enough for a document scanner even on low-end mobile devices. (Regardless, I am currently building a "final product" version of this app with WASM, a proper UI, and a few libraries. It should be faster and more user-friendly than the existing prototype).

With these constraints in mind, I got to work by hacking together a Parcel 2 project with TypeScript, the Parcel service worker precaching integration, and my PWA manifest generation plugin. This is my standard setup for all my new projects, but I usually throw React and Emotion in there too; unfortunately, I was already committed to the "zero dependencies" mantra at this point, so the only packages I installed were build tools. Next step: figure out how exactly document detection works so I can actually build the app.

Building a Mobile Document Scanner with Zero Dependencies: Introduction

101arrowz — Mon, 27 Dec 2021 12:59:59 +0000

I've been using document scanning apps like CamScanner and Smallpdf to send digital copies of physical documents for a long time, but I'd always wondered how exactly the apps worked. When you take a picture of a piece of paper, even without the paper perfectly centered, these apps automatically find its corners and warp the perspective of the image so it looks as if it were taken with a dedicated scanner. A few weeks ago, I started searching for open-source document scanners I could study.

The problem? There are none. Rather, the only open-source document scanners I could find basically handed everything off to OpenCV, which unfortunately has very sparse internal documentation.

So I decided to build my own document scanner, with one catch: I would be using zero third-party libraries. One month later, I have a prototype I'm happy with, and it's worked well on most of the documents I've tested it with.

Let's try it with a random image from Google:

Here's my document scanner at work:

And here is our final result:

The quality isn't perfect because the original image wasn't very high resolution, but taking pictures of most documents with a decent smartphone yields great results. If you'd like to check it out, the code and a demo website are available on GitHub.

However, I'd strongly suggest reading the rest of the articles in this series first to get a grasp on what exactly is happening under the hood. I believe that anyone can learn even the most complicated aspects of computer science, so I've written this series in such a way that you only need beginner programming skills and a basic understanding of algebra to follow along. Let's dive right in!

Creating a modern JS library: package.json and dependencies

101arrowz — Mon, 05 Apr 2021 15:20:03 +0000

Your package.json is among the most important files in your project. It handles dependencies, exports, versioning, naming, etc. package.json effectively includes all the metadata a user would need to use your library. Therefore, it's critical that you create package.json properly; if you don't, about half of your bug reports will be issues involving imports, mismatched dependencies, etc.

Let's go through the fields that a typical package.json will contain. We'll be creating an example package for re-encoding UTF-8 data or strings into the fictitious "Catlang" format.

`name` (required)

The name of your library. Even if you have a preferred style, the convention is to use all-lowercase letters and dashes to separate words.

If you're creating a fork of an existing package, don't add a number to the end: either describe what you changed or, if that's too difficult, express the same idea with different words.

Poor choice of name:

{
  "name": "EncodeInCatlang2",
}

Good choice of name:

{
  "name": "encode-in-catlang"
}

If the above was already taken:

{
  "name": "catlang-encoder"
}

`version` (required)

The current version of the package. You will change this every time you want to publish a new version of your package. Try to follow semantic versioning (more details on what this is later). My suggestions are as follows:

When you first create a package, use 0.0.1.
Whenever you fix a bug, you want a "patch" revision. Increment the last digit.
- 1.0.1 → 1.0.2
- 3.4.9 → 3.4.10
Whenever you add a new feature, soft-deprecate (i.e. discourage) an existing feature, or do anything else that doesn't break code that previously worked fine, you want a "minor" revision. Increment the second-to-last digit and set the last digit to zero.
- 1.0.1 → 1.1.0
- 3.9.0 → 3.10.0
- 0.3.5 → 0.3.6^*
Whenever you hard-deprecate (i.e. remove) an existing feature, change the behavior of something, or otherwise do anything that will break code that worked fine on a prior version, you must use a "major" revision. Increment the first digit and set the other two to zero.
- 1.1.3 → 2.0.0
- 10.1.3 → 11.0.0
- 0.3.5 → 0.4.0^*
- 0.0.3 → 0.0.4^*

Note the examples with an asterisk. For versions below 1.0.0, a patch revision is not possible and the other two types shift down; incrementing the second-to-last digit is major and the last digit is minor. For versions below 0.1.0, this is even more severe, since every version bump is a new major version.

This is why updating from 0.0.X to 0.1.0 and from 0.X.X to 1.0.0 are what I like to call "maturity" revisions; they completely change the meaning of each digit. As good practice, try to reduce the number of major versions you make after 1.0.0, but use as many minor and patch versions as you'd like.

As a notation guide, semantic versions are usually prefixed with a "v" outside of package.json. When referring to version 1.2.3 in a GitHub issue, for example, say "v1.2.3".

You also may want to note that alpha, beta, and release candidate versions are supported by semantic versioning. For example, 1.0.0-alpha.1, 2.2.0-beta.4, 0.3.0-rc.0. Typically, the patch version is unset for these prerelease versions, and they aren't downloaded by package managers unless the user requests a prerelease version.

Last thing: NPM considers packages under v1.0.0 to be unstable and ranks them lower in the search. If you want a quick boost to search score, make your library stable!

Let's update our package.json:

{
  "name": "catlang-encoder",
  "version": "0.0.1"
}

`description` (strongly recommended)

A brief description of what your package does. Even if the name is self-explanatory, it doesn't hurt to repeat yourself. The description is used for search results in NPM, so make sure to highlight the library's most major features.

{
  "name": "catlang-encoder",
  "version": "0.0.1",
  "description": "Fast Unicode to Catlang converter"
}

`author` (strongly recommended)

The name (and optionally email and website) of the author of the package. Optimally, you will use your full name here, but if you're not comfortable doing so, your online alias will suffice. The field can take one of two formats:

"Your Name <youremail@yourdomain.com> (https://yoursite.com)"

{
  "name": "Your Name",
  "email": "youremail@yourdomain.com",
  "url": "https://yoursite.com"
}

The email and website are optional, but you must add your name or alias.

New package.json:

{
  "name": "catlang-encoder",
  "version": "0.0.1",
  "description": "Fast Unicode to Catlang converter",
  "author": "Cat <cat@gmail.com>"
}

`license` (strongly recommended)

The license under which your library's code may be used. We'll get into licensing more in another article, but for now you should at least know the syntax.

If you're using a common license (such as MIT, ICS, BSD, GPL, Apache, etc.), you can use its identifier, which you can find in this list. Try to pick a license from that list, but if you can't, mention the file containing your license instead:

"SEE LICENSE IN LICENSE.md"

If you'd like to distribute your library under multiple licenses, you can use OR and AND expressions with parentheses. If you'd like to specify an exception within some license, use the WITH keyword.

"(Apache-2.0 OR MIT)"
"(GPL-3.0-only WITH Bison-exception-2.2)"

If you don't know anything about licensing and just want to freely distribute your code, "MIT" is a safe option.

New package.json:

{
  "name": "catlang-encoder",
  "version": "0.0.1",
  "description": "Fast Unicode to Catlang converter",
  "author": "Cat <cat@gmail.com>",
  "license": "MIT"
}

`keywords` (recommended)

The keywords to associate with your library in the NPM search. These are a way of getting your package in searches that don't include any words in the name or description fields. The point of the keywords field is to prevent keyword spamming in the description or title, but you still shouldn't use unrelated terms within the keywords.

Adding keywords to package.json:

{
  "name": "catlang-encoder",
  "version": "0.0.1",
  "description": "Fast Unicode to Catlang converter",
  "author": "Cat <cat@gmail.com>",
  "keywords": [
    "catlang",
    "cat language",
    "catlang converter",
    "high performance"
  ],
  "license": "MIT"
}

`homepage` (recommended)

The website for your project. This can be a documentation site, example page, etc. If you have a webpage that includes information about your library, even a blog post, use it here. Avoid using the link to your source code (i.e. your GitHub repository) unless you have absolutely no other site to link to.

{
  "name": "catlang-encoder",
  "version": "0.0.1",
  "description": "Fast Unicode to Catlang converter",
  "author": "Cat <cat@gmail.com>",
  "keywords": [
    "catlang",
    "cat language",
    "catlang converter",
    "high performance"
  ],
  "homepage": "https://catlangencoder.js.org",
  "license": "MIT"
}

`repository` (recommended)

Information about the repository. Assuming you're hosting your source code on a version control system (if you're not, you definitely should), use an object with type and url keys:

{
  "type": "git",
  "url": "https://domain.com/your-name/your-library.git"
}

There are some shorthands, such as using just the URL and letting NPM guess what type the repository is, but I advise against doing this for the sake of clarity.

If your library is a part of a monorepo, you can specify the directory subfield to denote the subdirectory within which the package is contained. If you aren't using a monorepo or don't know what a monorepo is, don't use directory.

{
  "name": "catlang-encoder",
  "version": "0.0.1",
  "author": "Cat <cat@gmail.com>",
  "description": "Fast Unicode to Catlang converter",
  "keywords": [
    "catlang",
    "cat language",
    "catlang converter",
    "high performance"
  ],
  "homepage": "https://catlangencoder.js.org",
  "repository": {
    "type": "git",
    "url": "https://github.com/cat/catlang",
    "directory": "js/packages/catlang-encoder"
  },
  "license": "MIT"
}

`bugs` (recommended)

Where users should report issues with the library. GitHub has a built-in issue tracker, so often you'll be using the /issues subdomain of your GitHub repository for this. You can specify just a string if you'd like just this URL:

"https://github.com/your-name/your-library/issues"

However, if you'd also like to add an email that users can report bugs to, you can use the object form:

{
  "email": "youremail@yourdomain.com",
  "url": "https://github.com/your-name/your-library/issues"
}

Updated package.json:

{
  "name": "catlang-encoder",
  "version": "0.0.1",
  "description": "Fast Unicode to Catlang converter",
  "author": "Cat <cat@gmail.com>",
  "keywords": [
    "catlang",
    "cat language",
    "catlang converter",
    "high performance"
  ],
  "homepage": "https://catlangencoder.js.org",
  "repository": {
    "type": "git",
    "url": "https://github.com/cat/catlang",
    "directory": "js/packages/catlang-encoder"
  },
  "bugs": {
    "email": "cat@gmail.com",
    "url": "https://github.com/cat/catlang/issues"
  },
  "license": "MIT"
}

`engines` (optional)

The environments in which your library will work. This is only applicable for libraries that support Node.js (e.g. a CSS library shouldn't use this field). If your library does not use modern features of JavaScript (such as async iterators), you also don't need to specify this field. The format is as follows:

{
  "node": ">=0.10.3 <15"
}

For now, node is the only key of the engines field that you'll need to use.

Suppose catlang-encoder needs support for ES6 features such as Promise + async/await, for..of, etc. Since async/await was only added in v7.6.0, we use that as the minimum version.

{
  "name": "catlang-encoder",
  "version": "0.0.1",
  "description": "Fast Unicode to Catlang converter",
  "author": "Cat <cat@gmail.com>",
  "keywords": [
    "catlang",
    "cat language",
    "catlang converter",
    "high performance"
  ],
  "homepage": "https://catlangencoder.js.org",
  "repository": {
    "type": "git",
    "url": "https://github.com/cat/catlang",
    "directory": "js/packages/catlang-encoder"
  },
  "bugs": {
    "email": "cat@gmail.com",
    "url": "https://github.com/cat/catlang/issues"
  },
  "engines": {
    "node": ">=7.6.0"
  },
  "license": "MIT"
}

`contributors` (optional)

People other than the author who have contributed in a major way to the project. The format is an array of objects or strings in the same format as the author field. For example:

[
  "John Doe <me@johndoe.net> (johndoe.net)",
  {
    "name": "Place Holder",
    "email": "placeholder@gmail.com"
  }
]

If you worked on this project mostly alone (perhaps with a few pull requests here and there), you don't need to specify this field. However, if someone has helped you many times, it's a good idea to add them.

{
  "name": "catlang-encoder",
  "version": "0.0.1",
  "description": "Fast Unicode to Catlang converter",
  "author": "Cat <cat@gmail.com>",
  "contributors": [
    "Cat 2"
  ],
  "keywords": [
    "catlang",
    "cat language",
    "catlang converter",
    "high performance"
  ],
  "homepage": "https://catlangencoder.js.org",
  "repository": {
    "type": "git",
    "url": "https://github.com/cat/catlang",
    "directory": "js/packages/catlang-encoder"
  },
  "bugs": {
    "email": "cat@gmail.com",
    "url": "https://github.com/cat/catlang/issues"
  },
  "engines": {
    "node": ">=7.6.0"
  },
  "license": "MIT"
}

`bin` (optional)

The location of the package's binary. If you're developing a CLI tool, set this to the entry point of your codebase. The file you set will be executed whenever someone runs npm run your-package or yarn run your-package. Of course, you don't need this field if you don't want to provide a CLI tool with your package.

For a single executable, the field can just be a string:

"path/to/bin.js"

If you have more than one executable, you can specify a mapping as so:

{
  "command-1": "./bin1.js",
  "command-2": "./bin2.js"
}

If we have a CLI executable for quick-and-dirty Catlang encoding from the command line at lib/cli.js:

{
  "name": "catlang-encoder",
  "version": "0.0.1",
  "description": "Fast Unicode to Catlang converter",
  "author": "Cat <cat@gmail.com>",
  "bin": "lib/cli.js",
  "contributors": [
    "Cat 2"
  ],
  "keywords": [
    "catlang",
    "cat language",
    "catlang converter",
    "high performance"
  ],
  "homepage": "https://catlangencoder.js.org",
  "repository": {
    "type": "git",
    "url": "https://github.com/cat/catlang",
    "directory": "js/packages/catlang-encoder"
  },
  "bugs": {
    "email": "cat@gmail.com",
    "url": "https://github.com/cat/catlang/issues"
  },
  "engines": {
    "node": ">=7.6.0"
  },
  "license": "MIT"
}

`private`

Prevents your package from being published if set to true. Obviously, you shouldn't have this field in your package.json but some starter projects/templates include "private": true in package.json to prevent you from accidentally publishing code that isn't meant to be a package. You'll want to remove the private field if it exists; otherwise, NPM will refuse to publish your package.

There are a few rarer fields that you may occasionally need such as os and man, in which case you should take a look at the original documentation for package.json. In addition, we'll be making use of the scripts field later on, and if you aren't familiar with it, you should read this.

Dependencies and exports

You may have noticed that our package.json for catlang-encoder has no dependencies and has no exports. We'll get into how you should handle exports in the next article, since it's quite a complicated topic, but right now we'll discuss dependencies in package.json.

As a rule of thumb, you should try to minimize the number of dependencies you use. If a dependency has under 20 lines of source code, the logic is probably simple enough that you can rewrite it on your own because that will make it easier to maintain your codebase.

If you do end up needing dependencies, there are four fields you can use to specify them: dependencies, peerDependencies, optionalDependencies, and devDependencies.

`dependencies`

The mapping of package name to versions supported for your library's runtime dependencies. If you use code from another library at runtime (i.e. when someone uses your package), add that library to this field. The syntax is as follows:

{
  "some-package": "^2.3.1",
  "other-package": ">=7.0.0",
  "last-package": ">=2 <3"
}

The keys of the object are the names of the dependencies, while the values are the versions to accept. The syntax for specifying versions is called semantic versioning, or "semver". The full details are detailed on the semantic versioning website, but generally you need to know only two things:

The actual version of a package is always three numbers separated by periods, as in the version field of package.json
Dependencies in package.json can use version identifiers, which refer to one or more versions of the package

When your users install your package, their package manager will see all the dependencies in package.json and download the relevant ones
There are many types of version identifiers, but the most relevant ones are these:

Exact identifiers, which are just the version numbers. They may exclude the patch and minor versions.
- 1.0.1 matches only v1.0.1
- 1.0.0-rc.0 matches only v1.0.0-rc.0 (this is the only way to get a prerelease version of a package)
- 0.10 matches any version in the v0.10 range (at least v0.10.0, before v0.11.0)
- 1 matches any version in the v1 range (at least v1.0.0, before v2.0.0)
Comparative identifiers, which match versions above or below a specific version
- >1.1.3 matches versions more recent than v1.1.3 (v1.1.4, v2.0.4, etc. all work)
- <=2.8.7 matches versions older than or equal to v2.8.7 (v2.8.7, v1.0.1, v0.0.1 all work)
Match-all identifiers, which use x or * to mark a part of the semver string that can be any version
- 1.x matches any version in the v1 range (like 1 does)
- * matches all versions of the package
- 2.3.* matches any version in the v2.3 range (like 2.3)
- Careful: 2.*.0 matches any version in the v2 range, not just patch-0 versions
Second-digit identifiers, which use tildes to match the second digit of the version provided that the third digit is greater than or equal to that specified in the identifier
- ~1.2.3 matches all versions >=1.2.3 and <1.3.0
- ~0.4.0 matches all versions >=0.4.0 and <0.5.0
Major version matchers, which use ^ to match the first nonzero digit
- Technically, the first digit, zero or nonzero, is always the major version. However, when the first digit is zero, a bump to the second digit is a significant change, and ^ prevents your library from accidentally accepting that significant, possibly breaking change.
- This is the most popular matcher
- ^3.2.1 matches any version in the v3 range
- ^0.4.0 matches any version in the v0.4 range
- ^0.0.5 matches just v0.0.5

Last thing: you can combine version identifiers using a space between two of them. The new identifier matches if both of the subidentifiers match. In other words:

>=1.5 <3 matches versions that are at least v1.5 but below v3 (i.e. at most v2)
1.x <=1.8 matches versions that start with v1 but are at most v1.8

If you're not sure that your semver string is correct, you can always try this tool to test that it matches the versions of your dependency in the way you want it to.

Let's say we need catlang-dictionary to tell us which words have direct translations to shorter glyphs in Catlang, and we have found that version 1.2.3 works well. Assuming that catlang-dictionary follows semantic versioning, it's a good idea to use ^1.2.3 as the version identifier.

{
  "name": "catlang-encoder",
  "version": "0.0.1",
  "description": "Fast Unicode to Catlang converter",
  "author": "Cat <cat@gmail.com>",
  "bin": "lib/cli.js",
  "contributors": [
    "Cat 2"
  ],
  "keywords": [
    "catlang",
    "cat language",
    "catlang converter",
    "high performance"
  ],
  "homepage": "https://catlangencoder.js.org",
  "repository": {
    "type": "git",
    "url": "https://github.com/cat/catlang",
    "directory": "js/packages/catlang-encoder"
  },
  "bugs": {
    "email": "cat@gmail.com",
    "url": "https://github.com/cat/catlang/issues"
  },
  "engines": {
    "node": ">=7.6.0"
  },
  "dependencies": {
    "catlang-dictionary": "^1.2.3"
  },
  "license": "MIT"
}

`peerDependencies`

The dependencies for which your package was installed as an add-on, extension, or integration. The difference between dependencies and peerDependencies is that peerDependencies are not automatically installed and are typically used to denote what your library integrates with or extends.

It's hard to define exactly when you should use a peer dependency over a dependency, but if the user installed your library only because they were directly using a certain package, add that package to the peerDependencies.

For instance, a React component library would have "react" in peerDependencies, and a Babel plugin would have "@babel/core" in peerDependencies. On the other hand, a JavaScript wrapper for a REST API would probably leave node-fetch in dependencies rather than peerDependencies. node-fetch is not being used directly by the user and is not the reason the package was installed; it's simply important for the HTTP requests to go smoothly.

It's very important that you use a loose version identifier for peer dependencies. For example, if you use ~16.3 as the version of React in your React component library, when your user updates to React v16.8, they'll get warnings about incompatible versions even though your library probably still works in v16.8. You'd be better off using ^16.3, or if you think the next major version won't break your package, >=16.3.

Since catlang-encoder works universally, regardless of framework, we don't need any peer dependencies and won't need to modify our package.json.

`optionalDependencies`

Any dependencies you would like to have but can do without. Effectively, there's no guarantee that these dependencies will be installed: they are usually installed if the package is compatible with the operating system and if the user agrees to installing that dependency. The primary use case for this field is preventing your package from failing to install when one of your dependencies is incompatible with the processor architecture, operating system, etc.

It's important to note that a dependency that can be installed for extra functionality is an optional peer dependency. If you can improve or add functionality to a section of your code if a dependency is installed, that's an optional peer dependency and not an optional dependency because you don't want the dependency installed by default.

For example, the @discordjs/opus extension for discord.js enables support for certain voice calling features in the Discord API. Since many users of the Discord API won't need voice support at all, using @discordjs/opus in optionalDependencies would install it by default, adding bloat. Therefore, it's an optional peer dependency, i.e. @discordjs/opus is in peerDependencies and it is specified as optional using the peerDependenciesMeta field:

{
  "@discordjs/opus": {
    "optional": true
  }
}

(As a side note, the actual discord.js does not do this anymore; they've completely removed the dependency from package.json and just ask users in the README to install the optional dependencies if they want them.)

For catlang-encoder, we can optionally use the native utf-8-validate package to verify that the inputs to the encoder are valid, but it's not necessary because the validation isn't strictly necessary. Since generally, most users don't need it, we make it an optional peer dependency. (Remember to use a loose version matcher with peer dependencies! We'll use * to support any version of utf-8-validate.)

On the other hand, we want to use catlang-concat whenever possible to more efficiently concatenate Catlang buffers, but we can still do normal buffer concatenation without it, so we specify it as an optional dependency to effectively tell the package manager: "I really want catlang-concat if you can install it, but if not I'll still work without it."

{
  "name": "catlang-encoder",
  "version": "0.0.1",
  "description": "Fast Unicode to Catlang converter",
  "author": "Cat <cat@gmail.com>",
  "bin": "lib/cli.js",
  "contributors": [
    "Cat 2"
  ],
  "keywords": [
    "catlang",
    "cat language",
    "catlang converter",
    "high performance"
  ],
  "homepage": "https://catlangencoder.js.org",
  "repository": {
    "type": "git",
    "url": "https://github.com/cat/catlang",
    "directory": "js/packages/catlang-encoder"
  },
  "bugs": {
    "email": "cat@gmail.com",
    "url": "https://github.com/cat/catlang/issues"
  },
  "engines": {
    "node": ">=7.6.0"
  },
  "dependencies": {
    "catlang-dictionary": "^1.2.3"
  },
  "peerDependencies": {
    "utf-8-validate": "*"
  },
  "peerDependenciesMeta": {
    "utf-8-validate": {
      "optional": true
    }
  },
  "optionalDependencies": {
    "catlang-concat": "^4.5.6"
  },
  "license": "MIT"
}

`devDependencies`

The list of dependencies that are not needed at runtime but are needed to develop the library. These packages are never installed when a user downloads your package; however, when you run npm/yarn/pnpm install, those packages are added. This is most often filled with packages needed to build the source code into runtime code, if any is ncessary. For instance, you'll often see babel for projects using JSX, or the typescript package for any library with source code in TypeScript.

Since we love stopping type errors before runtime, we have TypeScript source code. We'll need to add the typescript package to our devDependencies in order to use the tsc compiler, which will ultimately allow us to allow both TypeScript and JavaScript consumers to use our catlang-encoder.

{
  "name": "catlang-encoder",
  "version": "0.0.1",
  "description": "Fast Unicode to Catlang converter",
  "author": "Cat <cat@gmail.com>",
  "bin": "lib/cli.js",
  "contributors": [
    "Cat 2"
  ],
  "keywords": [
    "catlang",
    "cat language",
    "catlang converter",
    "high performance"
  ],
  "homepage": "https://catlangencoder.js.org",
  "repository": {
    "type": "git",
    "url": "https://github.com/cat/catlang",
    "directory": "js/packages/catlang-encoder"
  },
  "bugs": {
    "email": "cat@gmail.com",
    "url": "https://github.com/cat/catlang/issues"
  },
  "engines": {
    "node": ">=7.6.0"
  },
  "dependencies": {
    "catlang-dictionary": "^1.2.3"
  },
  "peerDependencies": {
    "utf-8-validate": "*"
  },
  "peerDependenciesMeta": {
    "utf-8-validate": {
      "optional": true
    }
  },
  "optionalDependencies": {
    "catlang-concat": "^4.5.6"
  },
  "devDependencies": {
    "typescript": "^4.2.2"
  },
  "license": "MIT"
}

With that, we've finished going through the vast majority of the fields of package.json. In the next article, we'll discuss how to add proper exports to package.json, which is critical if you want to develop a package that supports users whether they're using a CDN, a package manager, or a buildless web app with ESM.

Creating a modern JS library: TypeScript and Flow

101arrowz — Mon, 05 Apr 2021 15:19:46 +0000

Before we learn what you need to support TypeScript and Flow, let's think about why people use them in the first place. The main problem is that JavaScript is a dynamically, weakly typed language, but many programmers want static (and sometimes strong) typing.

Dynamic typing means that there are no types at compile-time. This means that you could accidentally add a function and a number, but you wouldn't know until runtime. Very few interpreted and JIT-compiled languages support static typing.

// There is no way to declare a type for a and b, even
// though a clearly needs to be a function
const myFunction = (a, b) => {
  return a(b);
}

// This function call does not throw a type error
// until it is executed, but a statically typed
// language would not compile.

// Think of a compile-time type error like a syntax
// error. Your code doesn't need to run for a type
// error to occur in statically typed languages.
const myResult = myFunction(
  { you: 'should not' },
 'be able to do this'
);

In contrast, a language like C will never allow something like this:

#include <stdio.h>

// This throws a compile time warning (or error,
// depending on your configuration)
const char* example() {
  // Not a string literal, so the program does
  // not compile and you cannot run it
  return 20;
}

int main() {
  printf("%s", example());
  return 0;
}

Weak typing means that JavaScript will not crash/throw an error when performing an illegal operation and will instead try to make that operation work. This kind of behavior is the origin of many WTFs by JS developers.

// This is perfectly valid JavaScript
const weirdAddition = [] + [];
console.log(weirdAddition); // ""

// That worked because the engine implicitly called
// [].toString() when it saw the addition operator.

// An empty array gives an empty string, hence the
// result is "" + "" = "".

This behavior is the polar opposite of Python: any invalid operation will immediately cause an exception. Even adding a string and a number will fail and ask you to convert the number to a string first.

a = '9 + 10 = '
b = 9 + 10

# This fails: you must explicitly cast b to string
print(a + b)

# Only this works
print(a + str(b))

Although JavaScript's virtually non-existent type system give programmers more flexibility, it's also the source of many bugs. Being both dynamically and weakly typed, at no point will you get an error if you make a mistake with types. Therefore, programmers wanted a solution to add types to JavaScript.

Enter TypeScript: an extension to JavaScript that adds syntax support for typings, a compiler, and incredible autocomplete support that was never previously possible in JavaScript.

// TypeScript accepts reasonable implicit conversions
const myFunction = (x: number) => 'hello ' + x;

// This will not compile, even with an explicit return type
// Adding arrays is not a reasonable use of dynamic typing
const myOtherFunction = (
  x: string[],
  y: string[]
): string => x + y;

// This will fail at compile time as well, since the first
// parameter of myFunction must be a number
myFunction('hello');

I highly recommend using TypeScript in your library because it compiles to any version of JavaScript, even as early as ES3. You can support legacy and modern JS environments, support both JavaScript and TypeScript users, and prevent bugs within your code by using TypeScript. Whether or not you decide to use TS, supporting TS users can be confusing, so read on.

Supporting TypeScript from a TypeScript project

If your library is written in TypeScript, you can automatically generate both JavaScript code (to support all users) and TypeScript declaration files (which add TypeScript types to JavaScript code). You will almost never need to export TypeScript files in your package, unless all of your users will use TypeScript (i.e. for something like typegoose).

The main think you need to do is enable the declaration compiler option in tsconfig.json.

{
  "compilerOptions": {
    "outDir": "lib/",
    // This is the relevant option
    // The types you need will be exported to lib/
    "declaration": true
  }
}

If you're not using the TypeScript compiler to build your code (using the noEmit option), you'll want to use emitDeclarationOnly as well.

{
  "compilerOptions": {
    "outDir": "lib/",
    "declaration": true,
    // Remove noEmit and replace it with this
    "emitDeclarationOnly": true
  }
}

Then, in package.json, use the "types" field to include your types.

{
  "main": "lib/index.js",
  "types": "lib/index.d.ts"
}

Supporting TypeScript from a JavaScript project

Just as with a TypeScript project, you need to export both JavaScript files and TypeScript declaration files to make your code usable for both TypeScript and JavaScript users.

Creating and maintaining a declaration file by hand can be difficult, so you'll want to make sure to read the docs on declaration files. If you have trouble with the syntax, try looking at the typings for popular packages such as Express.

First, you'll need to figure out whether the files you export from your package use CommonJS or ES Modules. CommonJS looks like this:

// module.exports or exports indicate CommonJS
module.exports = {
  a: 1,
  b(c, op) {
    if (op == 'sq') return c ** 2;
    if (op == 'sqrt') return Math.sqrt(c);
    throw new TypeError('invalid operation')
  }
}

// For exporting one thing:
module.exports = 'hello';

In contrast, ES Modules look like this:

// The export keyword indicates ESM
export const a = 1;
export function b(c, op) {
  if (op == 'sq') return c ** 2;
  if (op == 'sqrt') return Math.sqrt(c);
  throw new TypeError('invalid operation')
}

// export default for one thing
export default 'hello';

If you export both (we'll get into how to do this in a future article), only make a declaration file using ESM because the CommonJS declarations can almost always be inferred by the TypeScript compiler from the ESM version.

If you're using CommonJS, use namespaces to encapsulate your package. Optimally, you'll also export types and interfaces that make TypeScript use more convenient.

// index.d.ts

// Everything in the namespace is exported

// If you want to use a type within the declaration
// file but not export it, declare it outside
declare namespace MyPackage {
  const a: number;
  // This type prevents TypeScript users from
  // using an invalid operation
  type MyOp = 'sq' | 'sqrt';
  function b(c: number, op: MyOp): number;
}

export = MyPackageName;

// For a single export:
declare const myPackage: string;
export = myPackage;

Alternatively, if you're using ESM, you don't need (and shouldn't use) a namespace; export as you would in JavaScript.

export const a: number;
export type MyOp = 'sq' | 'sqrt';
export function b(c: number, op: MyOp): number;

// For a single export:
declare const myPackage: string;
export default myPackage;

Now that you have a complete index.d.ts, you can do one of two things. You can either:

Add it to your own NPM package, as with the TypeScript version
Add it to the DefinitelyTyped repository to get an @types/your-package-name package automatically

I recommend adding the declaration to the NPM package because that reduces the amount of time and effort it takes to update your package, as well as giving you more flexibility with regards to the TypeScript features you can use and removing the need to add tests.

However, if you have many dependencies whose types you need to include (e.g. if you export a React component, you depend on the React typings), you need to add @types/dependency-name to your dependencies, not devDependencies, and that adds bloat for your end users that don't use TypeScript. In those cases, it's often better to publish to DefinitelyTyped.

What about Flow?

The process of supporting Flow users is extremely similar to that of TypeScript. Instead of adding the definition file to "types" in package.json, make a .js.flow file alongside every .js file that is being exported (for example, if you export lib/index.js, make sure to create lib/index.js.flow with the definitions). See the docs on how to create such a definition. If you want to support Flow yourself, don't publish to flow-typed; it's mainly meant for community members to create their own types for third-party packages and publish them there.

// @flow

// If this is an ES Module:
declare export function sayHello(to: string): void;

// Alternatively, if this is CommonJS:
declare module.exports: {
  sayHello(to: string): void;
}

If you are writing your library with Flow, you can use build tooling to automate the process. Alternatively, use flowgen to only need to maintain a TypeScript definition file and automate the process of Flow support. In any case, Flow is pretty rare today; supporting just TypeScript will probably never be a problem.

Creating a modern JS library: Writing good code

101arrowz — Mon, 05 Apr 2021 15:19:28 +0000

It's impossible to assign a fixed definition to "good code", but most of the time in the JS world, we mean code that is:

bug-free
versatile
readable
fast
small

in that order. For libraries, you may choose to move readability to the bottom of the list, but that's probably not the best move if you'd like others to help you maintain your project. Now, let's see what each of these facets of "good code" entails.

Please remember, this is entirely my own opinion: feel free to ignore it entirely. Everyone should have their own definition of "best practices".

Writing bug-free code

Nobody will learn to use a new library if it has way too many bugs, no matter how good its other aspects are. The very fear of hidden bugs and untested circumstances explains why newer projects, no matter how much better than their predecessors they are, are often less popular than established libraries.

Writing tests is absolutely essential if you want to minimize the number of bugs your codebase has. Even rudimentary, seemingly pointless tests serve two purposes: they prevent you from accidentally publishing a broken version and they give your users a sense of security that their apps won't break when they update their dependencies. Whenever a new bug is reported or found, you'll want to add a test that would have failed before the bug was patched to make sure the package doesn't regress in the future.

There are a wide variety of libraries you can use to test your code. You'll need a test runner and, usually, a testing utility. For low-level or small projects, I recommend uvu as a test runner and uvu/assert as a testing utility, both of which work in either Node.js or the browser.

// test/index.js
import { test } from 'uvu';
import * as assert from 'uvu/assert';

// Import from the source file
import { myFunction } from '../src/index.js';

test('works on basic input', () => {
  assert.equal(
    myFunction({ a: 'b'}),
    'expected output'
  );
  assert.is(Math.sqrt(144), 12);

  // Throwing errors also works, so uvu works with
  // most third-party assertion libraries
  if (myFunction(123) != 456) {
    throw new Error('failed on 123');
  }
});

// Running node test/ runs these tests

For larger projects, you'll probably prefer Jest, since it supports more advanced use cases such as snapshots. You can't as easily run Jest tests in the browser, but most UI frameworks have integrations that allow for Jest testing in Node.js.

// __tests__/index.js
import { myFunction } from '../src/index.js';

test('works on basic input', () => {
  expect(myFunction({ a: 'b'}))
    .toBe('expected output');

  expect(myFunction(123)).toMatchSnapshot();
});

// npm run jest runs the tests

If you need more than the basic assertion tools that come with your test runner, you'll need to choose which testing utilities to use based on what your library does. I personally like the Testing Library suite, e.g. React Testing Library for React component libraries.

Beyond testing your code, it's an excellent idea to write your library in TypeScript. Type errors are among the most common type of mistake in JavaScript, so using TypeScript will almost always reduce development time and may occasionally prevent you from publishing broken code if you forget to add a test. Moreover, the excellent TypeScript compiler will allow you to avoid using a bundler when publishing your package (we'll get into this more later) and will make supporting TypeScript and JavaScript users simultaneously much easier.

TL;DR: Tests and (optionally) TypeScript

Writing versatile code

Users enjoy a feature-rich experience. A library that functions very well in doing one specific task may attract other library authors, since they want to minimize code bloat, but writing code that functions well for general-purpose tasks will bring in many more direct dependencies.

It's not really possible to give advice on what features you should add to your library since it all depends on what you're trying to achieve. However I can give advice on how to write code in a way that allow for easy future expansion. Here are a few suggestions:

Avoid creating short, single-use functions unless you plan to use them again in the near future. Splitting up a function may make the code look nicer, but it makes maintaining and tracking changes to that code more difficult. You can ignore this if the single-use function is very long.

// Don't do this:
const rand = (a, b) => {
  // If you decide to change this in the future (e.g. adding
  // a third argument for random number generation) you will
  // need to modify two functions instead of one.
  const randfloat = Math.random();
  return a + Math.floor(randfloat * (b - a));
}

const randArrayInRange = (len, a, b) => {
  const arr = new Array(len);
  for (let i = 0; i < len; ++i) {
    arr[i] = rand(a, b);
  }
  return arr;
}

// Use a single function, but make sure to add comments where
// you would otherwise have called a helper function.
const randArrayInRange = (len, a, b) => {
  const arr = new Array(len);
  for (let i = 0; i < len; ++i) {
    // Generate random number at least 0, less than 1
    const randfloat = Math.random();
    // Move randfloat into [a, b) range
    arr[i] = a + Math.floor(randfloat * (b - a));
  }
  return arr;
}

Add TODO comments whenever you notice something that could become an issue in the future. Doing so will save you time when you decide to add a feature that initially fails because of prior decisions or oversights.

const numPostsOnPage = async page => {
  // TODO: "page" may not be the name of the argument in the
  // calling function - can be ambiguous
  if (typeof page != 'number') {
    throw new TypeError('page must be a number');
  }
  const resp = await fetch(`//example.com/page/${page}`);
  const posts = await resp.json();
  return posts.length;
}

const example = (x, y) => {
  if (typeof x != 'number') {
    throw new TypeError('x must be a number');
  }
  // TODO: This is an async function, so a type error for y
  // will not throw but will reject the returned Promise,
  // but a type error for x throws
  return x * numPostsOnPage(y);
}

// Because of the TODOs, in the future, you'll easily
// find why the type error for y isn't caught here
try {
  example(0, 'mistake');
} catch(e) {
  console.error(`Got error: ${e}`);
}

Use documentation for code that you will consider modifying in the future. Even if the code is only used internally, this will make modifications easier and will help collaborators diagnose bugs more easily.

// TODO: in the future, consider changing the following
// recursive function to be more efficient by fetching
// all users simultaneously with Promise.all()

// gets the names of all users
const getUserNames = async max => {
  // Recursive base case - no user 0 exists
  if (!max) return [];
  const res = await fetch(`/users/${max}`);
  // Data for user ID # max
  const userData = await res.json();
  // Prepend data for users with lower IDs
  return (await getUserNames(max - 1)).concat(userData);
}

TL;DR: Keep your codebase maintainable and everything will fall into place

Writing readable code

Readable code is critical for maintainability and for receiving help from the community. Nobody wants to spend an hour studying your codebase just to understand what each function does; writing easy-to-read code is a good start.

This step is incredibly simple. The two things you need to do are:

Use sufficient (but not too much) inline documentation for functions, variables, etc.
Additionally, use self-documenting function/variable names for user-facing code (i.e. what is exported). Optimally, clean JSDoc will accompany each declaration (using JSDoc/TSDoc will be very helpful, as we'll see in a future article).

// The short names used here are OK because they are
// documented and because the names make sense

// zip compression worker
// send string -> Uint8Array mapping
// receive Uint8Array ZIP data
const zwk = new Worker('./zip-worker.js');

// read file to [filename, Uint8Array]
const readFile = file => new Promise((resolve, reject) => {
  // file reader: File to ArrayBuffer
  const fr = new FileReader();
  fr.onload = () => {
    // fr.result is ArrayBuffer
    resolve([file.name, new Uint8Array(fr.result)]);
  }
  fr.onerror = () => {
    reject(fr.error);
  }
  fr.readAsArrayBuffer(file);
});

/**
 * Zips the provided files
 * @param files {File[]} The files to create a ZIP from
 * @returns {Promise} A promise with a Blob of the ZIPped data
 */
export async function zipFiles(files) {
  // file entries - Array of [filename, data]
  const entries = await Promise.all(files.map(readFile));
  // transferable list - neuters data passed in but reduces
  // execution time
  const tfl = fileEntries.map(([, dat]) => dat.buffer);
  // filename -> data mapping
  const fileData = fileEntries.reduce((obj, [fn, dat]) => {
    obj[fn] = dat;
    return obj;
  }, {});

  return new Promise((resolve, reject) => {
    zwk.onmessage = ({ data }) => resolve(data);
    zwk.onerror = ({ error }) => reject(error);
    zwk.postMessage(fileData, tfl);
  });
}

TL;DR: Make it self-documenting or document it yourself

Writing fast code

This isn't meant to be a performance article, so I'm not going to go into too much depth here.

For low-level code (i.e. anything involving bit twiddling, binary encoding, etc.), you'll want to use the profiler in Node.js (your code editor may have support) or Chrome (see this article). This guide to performance in the V8 engine may help.

For higher level programs such as UI libraries and frameworks, micro-optimizations are pointless. Look for large-scale architectural issues with your design (for example, needing to call document.getElementById multiple times per second due to a limitation in your virtual DOM). The Chrome profiler will also help determine if the issue lies with your JavaScript, rendering, or something else.

TL;DR: If this section is too long, it probably doesn't apply to you.

Writing small code

Again, this article isn't meant to be about optimization, so I won't discuss much here, but let me know in the comments if you'd like a more detailed write-up on how to squeeze every last drop of performance out of your code.

Small code can contribute to both readability and to performance (i.e. load times in the browser). However, if you're writing a library for Node.js only, small code is not a concern at all unless you have so much code bloat that your codebase is difficult to understand. In general, small code is the least important facet of a good library.

If you'd really like to shrink the size of your bundled code, the best way is to avoid using pre-built abstractions for things you can implement manually. For instance, if you need to get the duration of a song in an MP3 file in the browser, don't use music-metadata, do it yourself. The code you need to write is probably around a few hundred bytes, so you'll save 63 kB.

TL;DR: Do everything yourself

That's it!

At the end of the day, how useful a library is depends the most on how difficult it is to work around the problem it solves. Nobody wants to write a SHA-256 algorithm from scratch, so even unmaintained cryptography libraries are very popular. On the other hand, DOM manipulation libraries are a dime a dozen, so even some excellent UI frameworks receive very few downloads. However, good code is very appreciated no matter how many people are using it. I hope these tips were helpful. Thanks for reading!

Creating a modern JS library: Introduction

101arrowz — Mon, 05 Apr 2021 15:19:14 +0000

Using the modern JavaScript ecosystem is, for the most part, a pretty good experience. Sure, there may be too many frameworks to count, but if you've been using JS for long enough, you already know exactly which packages you'll be using in each new project, and at worst you'll be using something like Create React App to get off the ground.

// Magic! React now works
import React from 'react';

Although using libraries is simple, creating and maintaining one can be an absolute nightmare.

The problem

You need to support as many versions of as many different platforms as possible to satisfy your users. Even if you're making a package for only Node.js or only browsers, getting exports to work properly can be tricky.

// ES Modules
import myPackage from 'my-package';

// CommonJS
const myPackage = require('my-package');

// UMD
document.write('<script src="//unpkg.com/my-package"></script>');

You want to minimize bundle size for browser users, but there are very few resources that describe the best way to go about doing so. If your library is anything more than a hundred kilobytes, your users will complain that it now takes an extra second or two to load their website on a cheap mobile device.

You may want to support TypeScript and Flow users by adding typings for your package, but it's unclear whether you should add them to DefinitelyTyped/flow-typed or include them within your package. If you aren't familiar with TypeScript or Flow, managing types as your library evolves can become incredibly difficult.

There are a plethora of other concerns too. How do you write good documentation? How do you fix bugs quickly and manage issues when they start to pile up? How do you encourage community contributions? How do you make your library easy to understand for novices?

Why listen to my suggestions?

To keep it short: I've worked on Parcel for a few months and therefore have investigated in great depth the fine details of making a package bundler-friendly. I've also published and maintained various successful packages, the most popular of which is is a high-performance compression library that reached over 4 million downloads in 6 months and is currently depended on by large projects such as SheetJS and Three.js. I've dealt with many of the problems new library authors face multiple times, so I'm familiar with the workarounds.

The solution

This series will describe the do's and don'ts of creating a JavaScript library that your users will love to use and you will love to maintain. Even if you aren't planning on creating a library any time soon, these articles will help you learn more about the JavaScript ecosystem and its many quirks. Don't worry about following any particular order; you won't need to read any entry in the series to understand the next. I hope this information will help you design your next awesome addition to the JS ecosystem!