# Unlocking Your Bike the Easy Way

Mathias Sonnleitner  Faculty of Computer Science and Mathematics, University
of Passau,
94032 Passau, Germany<EMAIL_ADDRESS>
###### Abstract.

Combination locks are widely used to secure bicycles. We consider a
combination lock consisting of adjacent rotating dials with the first
nonnegative integers printed on each of them. Assuming that we know the
correct combination and we start from an incorrect combination, what is the
minimal number of steps to arrive at the correct combination if in each step
we are allowed to turn an arbitrary number of adjacent dials once in a common
direction? We answer this question using elementary methods and show how this
is related to a variation of (multivariate) functions.

###### Key words and phrases:

discrete optimization, nonlinear approximation, total variation

###### 2020 Mathematics Subject Classification:

00A08, 90C27

##  1\. Introduction.

Let $n$ and $N$ be positive integers (i.e., in $\mathbb{N}$) and consider a
combination lock with $n$ dials, each showing the numbers $0,1,\dots,N-1$. By
rotating the dials any combination

$f=\big{(}f(1),\dots,f(n)\big{)},\quad\text{where }f(i)\in[0,N-1]\text{ for
every }i\in[n],$ (1)

can be transformed into any other. Here, we used $[m]=\\{1,2,\dots,m\\}$ for
$m\in\mathbb{N}$ and $[0,m]=\\{0,1,\dots,m\\}$ for
$m\in\mathbb{N}\cup\\{0\\}$.

In order to reach the known correct combination
$f_{\includegraphics[scale={1}]{unlocked.pdf}}$ starting from an incorrect
combination $f_{\includegraphics[scale={1}]{locked.pdf}}$, we rotate dials
repeatedly into one of two possible directions. Assuming that rotating any
number of adjacent dials once into a common direction counts as one rotation,
what is the minimal number of rotations needed to turn
$f_{\includegraphics[scale={1}]{locked.pdf}}$ into
$f_{\includegraphics[scale={1}]{unlocked.pdf}}$?

Figure 1. An inefficient way to turn combination $(9,1,6,7)$ into $(9,1,6,6)$
with rotated dials shaded in grey. The second combination is obtained from the
first by rotating the second and the third dial downwards and the third
combination is obtained from the second by rotating the second, third, and
fourth dials upwards.

Aside from the stackoverflow-post [9], where an unsolved instance of this
question with $N=26$ appears, we could not find any reference to this very
intuitive problem. To state and solve it in a formal way requires some
notation which we now introduce.

We identify a rotation with an interval of dials $[a,b]=\\{i\in[n]\colon a\leq
i\leq b\\}$, where $a,b\in[n]$, and a direction $\varepsilon\in\\{1,-1\\}$.
Applying such a rotation to a combination $f$ as in display (1) yields the
combination

$f^{\prime}=\big{(}f^{\prime}(1),\dots,f^{\prime}(n)\big{)},\quad\text{where
}f^{\prime}(i)=f(i)+\varepsilon\mathbf{1}_{[a,b]}(i)\text{ mod }N,\quad
i\in[n],$

where the indicator $\mathbf{1}_{[a,b]}(i)$ evaluates to one if $i\in[a,b]$
and to zero otherwise. Thus, depending on the direction $\varepsilon$, the
digits of $f$ belonging to $[a,b]$ are either increased or decreased by one
and then reduced modulo $N$.

By using a suitable set of rotations, applied one after the other in any
order, one can turn $f_{\includegraphics[scale={1}]{locked.pdf}}$ into any
other combination of the form (1). Such a set of rotations can be identified
with a choice of $m\in\mathbb{N}$ different intervals of dials
$I_{j}=[a_{j},b_{j}]$, $j\in[m]$, where $a_{j},b_{j}\in[n]$, and numbers
$c_{j}\in\mathbb{Z}$ which count how often exactly the dials in $I_{j}$ are
rotated in total. Here, we subtract rotations in a negative direction from
those in a positive direction and interpret a positive (negative) $c_{j}$ as
$|c_{j}|$ rotations in positive (negative) direction. This ensures that
rotations of the same dials in opposite directions cancel each other.

To answer the question stated above, we have to determine the minimal total
number $\sum_{j=1}^{m}|c_{j}|$ of rotations needed to turn
$f_{\includegraphics[scale={1}]{locked.pdf}}$ into
$f_{\includegraphics[scale={1}]{unlocked.pdf}}$, that is, the solution to the
following discrete optimization problem.

Minimize $\displaystyle\quad\sum_{j=1}^{m}|c_{j}|$ subject to
$\displaystyle\quad f_{\includegraphics[scale={1}]{unlocked.pdf}}(i)\equiv
f_{\includegraphics[scale={1}]{locked.pdf}}(i)+\sum_{j=1}^{m}c_{j}\mathbf{1}_{[a_{j},b_{j}]}(i)\quad(\mathrm{mod}\,N),\quad
i\in[n]$ $\displaystyle\quad m\in\mathbb{N},a_{j},b_{j}\in[n]\text{ and
}c_{j}\in\mathbb{Z},\quad j\in[m].$ (P1)

We can and do assume that $|c_{j}|\leq N$ for all $j\in[m]$ since rotating the
same dials $N$ times in the same direction has no effect. Thus, problem (1)
admits a finite set of feasible solutions and may be solved through exhaustive
search given $n,N,f_{\includegraphics[scale={1}]{unlocked.pdf}}$ and
$f_{\includegraphics[scale={1}]{locked.pdf}}$. Instead of using more advanced
techniques from discrete optimization, see, e.g., [11] for an overview, we
present an illustrative elementary approach to solve (1).

The solution of (1) and thus the answer to our question will depend only on
the difference between $f_{\includegraphics[scale={1}]{unlocked.pdf}}$ and
$f_{\includegraphics[scale={1}]{locked.pdf}}$ which is the combination

$f^{\rm
diff}(i)=f_{\includegraphics[scale={1}]{unlocked.pdf}}(i)-f_{\includegraphics[scale={1}]{locked.pdf}}(i)\mod
N,\quad\text{}i\in[n],$

and in fact only on its jumps which are measured by its (forward) difference

$\Delta f^{\rm diff}\colon[0,n]\to\mathbb{Z},\quad i\mapsto f^{\rm
diff}(i+1)-f^{\rm diff}(i),$

where we extended $f^{\rm diff}$ by setting $f^{\rm diff}(0)=f^{\rm
diff}(n+1)=0$. Define the sets

$\Delta_{+}=\\{i\in[0,n]\colon\Delta f^{\rm
diff}(i)>0\\}\quad\text{and}\quad\Delta_{-}=\\{i\in[0,n]\colon\Delta f^{\rm
diff}(i)<0\\},$

of upward jumps and downward jumps which are both nonempty. We enumerate these
nonincreasingly according to the size of the jump, i.e.,

$\Delta_{+}=\\{i_{1}^{+},\dots,i_{\\#\Delta_{+}}^{+}\\}\quad\text{such
that}\quad|\Delta f^{\rm diff}(i_{1}^{+})|\geq\cdots\geq|\Delta f^{\rm
diff}(i_{\\#\Delta_{+}}^{+})|,$

where $\\#\Delta_{+}$ denotes the cardinality of $\Delta_{+}$ and for
$\Delta_{-}$ we replace $+$’es by $-$’es. By summing over all jumps and
grouping large upward with large downward jumps we obtain the following
statement on the minimal number of rotations.

######  Theorem 1.

The optimal value in (1) is given by

$\frac{1}{2}\sum_{i=0}^{n}|\Delta f^{\rm
diff}(i)|-\sum_{k=1}^{K}\big{(}|\Delta f^{\rm diff}(i_{k}^{+})|+|\Delta f^{\rm
diff}(i_{k}^{-})|-N\big{)}_{+},$ (2)

where $K=\min\\{\\#\Delta_{+},\\#\Delta_{-}\\}$ and $x_{+}=\max\\{x,0\\}$.

Formula (2) in Theorem 1 gives the optimal value of Problem (1) and thus the
minimal number of rotations needed to turn
$f_{\includegraphics[scale={1}]{locked.pdf}}$ into
$f_{\includegraphics[scale={1}]{unlocked.pdf}}$, or equivalently, to turn
$f^{\rm diff}$ into $(0,\dots,0)$. This answers the question raised in the
beginning.

Before we prove Theorem 1, let us present two examples with $N=10$.

######  Example 2.

Let

$f^{\rm diff}=(9,0,9,0,9)\quad\text{with}\quad\Delta f^{\rm
diff}=(9,-9,9,-9,9,-9).$

It is not too hard to see that three rotations turning each nine to a zero
suffice to turn $f^{\rm diff}$ to zero and that Theorem 1 gives the same
answer.

######  Example 3.

Let

$f^{\rm diff}=(9,8,\ldots,1)\quad\text{with}\quad\Delta f^{\rm
diff}=(9,-1,-1,\dots,-1).$

Rotate such that all non-zero entries of $f^{\rm diff}$ are increased by one
($9\rightarrow 0$). Doing this nine times we arrive at the zero combination
and by Theorem 1 this is the best possible.

Comparing these examples, each rather extreme in its own way, we see that for
Example 2 both sides of the minus sign in (2) are rather large but roughly of
the same size and compensate for each other. For Example 3, the sum on the
left is not too large and the sum on the right vanishes.

As a first step toward the proof of Theorem 1 we give an interpretation of
Problem (1) in terms of efficiently building functions from indicators. For
this purpose, consider combinations as functions from $[n]$ to $[0,N-1]$ which
can be added and subtracted pointwise. If we subtract
$f_{\includegraphics[scale={1}]{locked.pdf}}$ from both sides of the equality
in (1), then Problem (1) is equivalent to finding a representation of the form
$f^{\rm diff}\equiv\sum_{j=1}^{m}c_{j}\mathbf{1}_{[a_{j},b_{j}]}\ (\text{mod
}N)$ with minimal cost $\sum_{j=1}^{m}|c_{j}|$ when each function
$c_{j}\mathbf{1}_{[a_{j},b_{j}]}$ costs $|c_{j}|$. Then this minimal cost is
given by formula (2) in Theorem 1.

It will be helpful to extend this interpretation to more general functions as
follows. For any $f\colon[n]\to\mathbb{Z}$ define its cost by

$C(f)=\min\Big{\\{}\sum_{j=1}^{m}|c_{j}|\colon
f=\sum_{j=1}^{m}c_{j}\mathbf{1}_{[a_{j},b_{j}]}\text{ where
}m,a_{j},b_{j}\text{ and }c_{j}\text{ are as in }\eqref{eq:P1}\Big{\\}}.$ (3)

Since for any $a,b\in\mathbb{Z}$ we have $a\equiv b\ (\mathrm{mod}\,N)$ if and
only if $a+cN=b$ for some $c\in\mathbb{Z}$, Problem (1) is equivalent to

minimize $\displaystyle\quad C(f^{\rm diff}+Nk)$ subject to
$\displaystyle\quad k\colon[n]\to\mathbb{Z},$ (P2)

where “equivalent” means that a solution to (1) gives rise to a solution of
(1), and vice versa, and that the optimal values are the same.

We can split (1) into two subproblems, where the first consists of computing
$C(f)$ for a general $f\colon[n]\to\mathbb{Z}$ and the second of finding the
optimal $k$ in (1). The first subproblem is resolved by the following
proposition which is interesting on its own.

######  Proposition 4.

For $f\colon[n]\to\mathbb{Z}$ we have

$C(f)=\frac{1}{2}\sum_{i=0}^{n}|\Delta f(i)|,$ (4)

where we set $f(0)=f(n+1)=0$.

The proof of Proposition 4 is given in the upcoming section as part of the
proof of Theorem 1. From the proofs we deduce an optimal set of rotations
solving problem (1), thus providing its full solution. In Section 3 we connect
Proposition 4 to existing results on different concepts of variation.

##  2\. Proofs and optimal rotations.

We begin by proving an extended version of Proposition 4. To state it, define
for any $x\in\mathbb{Z}$ its positive part $x_{+}=\max\\{x,0\\}$ and its
negative part $x_{-}=(-x)_{+}$ such that $x=x_{+}-x_{-}$ and
$|x|=x_{+}+x_{-}$. Intuitively, it expresses the cost as half the total sum of
upward and downward jumps which is equal to the sum over all upward or
downward jumps.

######  Proposition 5.

With $C(f)$ as in (3), for any $f\colon[n]\to\mathbb{Z}$ we have

$C(f)=\frac{1}{2}\sum_{i=0}^{n}|\Delta f(i)|=\sum_{i=0}^{n}\Delta
f(i)_{+}=\sum_{i=0}^{n}\Delta f(i)_{-},$

where we set $f(0)=f(n+1)=0$.

###### Proof.

The second and the third equality follow from

$0=\sum_{i=0}^{n}\Delta f(i)=\sum_{i=0}^{n}\Delta
f(i)_{+}-\sum_{i=0}^{n}\Delta f(i)_{-}.$

Next, we prove the upper bound of $C(f)$. The idea behind the proof is to
write $f=f_{+}-f_{-}$ with $f_{+}(i)=f(i)_{+}$ and $f_{-}(i)=f(i)_{-}$ for
$i\in[n]$ and to represent the nonnegative functions $f_{+}$ and $f_{-}$ as in
(3). This is done by partitioning superlevel sets into connected components
and summing the corresponding indicator functions as indicated in Figure 2.

Figure 2. A nonnegative function $f\colon[n]\to\mathbb{Z}$ is graphically
represented as a linear combination of indicator functions. Each shaded block
corresponds to the interval it spans horizontally and is shaded according to
whether this interval belongs to a superlevel set $\\{f\geq\ell\\}$ of odd or
even level $\ell\in\mathbb{N}$. Alternatively, one can view $C(f)$ as the
minimal number of blocks needed to build $f$ and decomposing the superlevel
sets provides a formal way of doing this in an optimal way. Intuitively, going
from left to right, one can create new blocks at upward jumps and close them
at downward jumps.

Assume first that $f\geq 0$, which applies to $f_{+}$ and $f_{-}$. Then for
each level $\ell\in\mathbb{N}$ with $\ell\leq\sup f=\sup_{i\in[n]}f(i)$ we
find $M_{\ell}\in\mathbb{N}_{0}$ and $a_{\ell,k},b_{\ell,k}\in[n]$ for
$k\in[M_{\ell}]$ such that

$\\{i\in[n]\colon
f(i)\geq\ell\\}=\bigcup_{k=1}^{M_{\ell}}[a_{\ell,k},b_{\ell,k}]$

is a disjoint union of intervals of maximal length. The endpoints of the
intervals are given by the location of upward and downward jumps, i.e.,

$\displaystyle\big{\\{}a_{\ell,k}\colon k\in[M_{\ell}]\big{\\}}$
$\displaystyle=\big{\\{}i\in[n]\colon f(i-1)<\ell\leq f(i)\big{\\}},$
$\displaystyle\big{\\{}b_{\ell,k}\colon k\in[M_{\ell}]\big{\\}}$
$\displaystyle=\big{\\{}i\in[n]\colon f(i+1)<\ell\leq f(i)\big{\\}}$

and if $M_{\ell}\geq 2$ we assume without loss of generality that they are
ordered such that

$a_{\ell,k}<b_{\ell,k}+1<a_{\ell,k+1}<b_{\ell,k+1}+1\quad\text{for every}\quad
k\in[M_{\ell}-1].$ (5)

From the right-hand side of the pointwise equalities

$f=\sum_{\ell=1}^{\sup f}\mathbf{1}_{\\{i\in[n]\colon
f(i)\geq\ell\\}}=\sum_{\ell=1}^{\sup
f}\sum_{k=1}^{M_{\ell}}\mathbf{1}_{[a_{\ell,k},b_{\ell,k}]},$

we can collect equal summands, if there are any, to obtain a representation as
in (3). In any case, the cost is $\sum_{\ell=1}^{\sup f}M_{\ell}$ and thus

$M_{\ell}=\\#\\{i\in[n]\colon f(i-1)<\ell\leq
f(i)\\}=\\#\\{i\in[n]\colon\ell\in(f(i-1),f(i)]\\}$

yields the bound

$C(f)\leq\sum_{\ell=1}^{\sup f}M_{\ell}=\sum_{\ell=1}^{\sup
f}\sum_{i\in[n]}\mathbf{1}_{(f(i-1),f(i)]}(\ell)=\sum_{i=1}^{n}\Delta
f(i-1)_{+}.$ (6)

This establishes the upper bound of $C(f)$ if $f\geq 0$.

In general, write $f=f_{+}-f_{-}$ with $f_{+},f_{-}\geq 0$. By the first part
of the proof we can write
$f_{+}=\sum_{j=1}^{m^{+}}c_{j}^{+}\mathbf{1}_{I_{j}^{+}}$ as in (3) with
$m^{+}\in\mathbb{N},c_{j}^{+}\in\mathbb{Z}$ and intervals
$I_{j}^{+}\subseteq[n]$ satisfying

$\sum_{j=1}^{m^{+}}|c_{j}^{+}|\leq\frac{1}{2}\sum_{i=0}^{n}|f_{+}(i+1)-f_{+}(i)|,$

and analogously for $f_{-}$. Let

$I_{j}=I_{j}^{+}\text{ and }c_{j}=c_{j}^{+}\text{ for
}j\in[m^{+}]\quad\text{and}\quad I_{j+m^{+}}=I_{j}^{-}\text{ and
}c_{j+m^{+}}=-c_{j}^{-}\text{ for }j\in[m^{-}].$

With $m=m^{+}+m^{-}$ we obtain the pointwise equalities

$f=f_{+}-f_{-}=\sum_{j=1}^{m^{+}}c_{j}^{+}\mathbf{1}_{I_{j}^{+}}-\sum_{j=1}^{m^{-}}c_{j}^{-}\mathbf{1}_{I_{j}^{-}}=\sum_{j=1}^{m}c_{j}\mathbf{1}_{I_{j}}.$

Further,

$\displaystyle C(f)\leq\sum_{j=1}^{m}|c_{j}|$
$\displaystyle\leq\frac{1}{2}\sum_{i=0}^{n}|f_{+}(i+1)-f_{+}(i)|+\frac{1}{2}\sum_{i=0}^{n}|f_{-}(i+1)-f_{-}(i)|$
$\displaystyle=\frac{1}{2}\sum_{i=0}^{n}|f(i+1)-f(i)|$

since $|x_{+}-y_{+}|+|x_{-}-y_{-}|=|x-y|$ for every $x,y\in\mathbb{R}$. This
completes the proof of the upper bound of $C(f)$ in the general case.

For the lower bound let $m\in\mathbb{N}$, $c_{j}\in\mathbb{Z}$, and
$I_{j}=[a_{j},b_{j}]\subseteq[n]$ for $j\in[m]$ be such that

$f=\sum_{j=1}^{m}c_{j}\mathbf{1}_{I_{j}}.$ (7)

It is sufficient to show

$\sum_{j=1}^{m}|c_{j}|\geq\sum_{i=0}^{n}\Delta f(i)_{+}.$ (8)

Trivially, this holds if right-hand side of (8) equals zero and in particular
if the set

$\Delta^{+}_{0}=\\{i\in[0,n]\colon\Delta f(i)\geq 0\\}$

is empty. Assume that $\Delta^{+}_{0}$ is nonempty and, as for the superlevel
sets above, find $M$ and $a_{k}^{\prime},b_{k}^{\prime}\in[0,n]$ for $k\in[M]$
such that

$\Delta^{+}_{0}=\bigcup_{k=1}^{M}[a_{k}^{\prime},b_{k}^{\prime}]$ (9)

is a disjoint union of intervals of maximal length. Again, if $M\geq 2$, we
assume without loss of generality that the endpoints of the intervals are
ordered such that

$a_{k}^{\prime}<b_{k}^{\prime}+1<a_{k+1}^{\prime}<b_{k+1}^{\prime}+1\quad\text{for
every}\quad k\in[M-1].$ (10)

Then the right-hand side of (8) equals

$\sum_{i\in\Delta^{+}_{0}}\Delta
f(i)_{+}=\sum_{k=1}^{M}\sum_{x=a_{k}^{\prime}}^{b_{k}^{\prime}}\Delta
f(i)=\sum_{k=1}^{M}f(b_{k}^{\prime}+1)-f(a_{k}^{\prime}).$

With an interchange of sums, the representation (7) yields

$\sum_{k=1}^{M}f(b_{k}^{\prime}+1)-f(a_{k}^{\prime})=\sum_{j=1}^{m}c_{j}\Big{(}\sum_{k=1}^{M}\mathbf{1}_{I_{j}}(b_{k}^{\prime}+1)-\sum_{k=1}^{M}\mathbf{1}_{I_{j}}(a_{k}^{\prime})\Big{)}.$

After applying absolute values and the triangle inequality we arrive at

$\Big{|}\sum_{k=1}^{M}f(b_{k}^{\prime}+1)-f(a_{k}^{\prime})\Big{|}\leq\sum_{j=1}^{m}|c_{j}|\Big{|}\sum_{k=1}^{M}\mathbf{1}_{I_{j}}(b_{k}^{\prime}+1)-\sum_{k=1}^{M}\mathbf{1}_{I_{j}}(a_{k}^{\prime})\Big{|}.$

In the case of $M=1$ the proof of (8) is already complete and if $M\geq 2$ the
interlacing of the $a_{k}^{\prime}$ and $(b_{k}^{\prime}+1)$ as in (10) gives

$\Big{|}\sum_{k=1}^{M}\mathbf{1}_{I_{j}}(b_{k}^{\prime}+1)-\sum_{k=1}^{M}\mathbf{1}_{I_{j}}(a_{k}^{\prime})\Big{|}\leq
1,\quad j\in[m].$

This proves the lower bound (8) and completes the proof. ∎

Thus, also Proposition 4 is now proven. Together with the linearity of the
difference $\Delta$ it implies that problem (1) can be restated as

minimize $\displaystyle\quad\frac{1}{2}\sum_{i=0}^{n}|\Delta f^{\rm
diff}(i)+N\Delta k(i)|$ subject to $\displaystyle\quad
k\colon[0,n+1]\to\mathbb{Z}\text{ with }k(0)=k(n+1)=0.$ (P2)

As $\Delta k$ appears in the objective function of (2), it will be helpful to
optimize over $\Delta k$ instead of $k$. We observe that any
$k\colon[n]\to\mathbb{Z}$ as in (2) is determined by its difference $\Delta
k\colon[0,n]\to\mathbb{Z}$ and that any function
$k^{\prime}\colon[0,n]\to\mathbb{Z}$ is equal to $\Delta
k\colon[0,n]\to\mathbb{Z}$ for some $k\colon[n]\to\mathbb{Z}$ as in (2) if and
only if $\sum_{i=0}^{n}k^{\prime}(i)=0$. Therefore, (2), and thus (1), are
equivalent to

minimize $\displaystyle\quad\frac{1}{2}\sum_{i=0}^{n}|\Delta f^{\rm
diff}(i)+Nk^{\prime}(i)|$ subject to $\displaystyle\quad
k^{\prime}\colon[0,n]\to\mathbb{Z},\quad\sum_{i=0}^{n}k^{\prime}(i)=0.$ (P3)

The following lemma on solutions to (P3) is a consequence of

$|\Delta f^{\rm diff}(i)|\leq N-1,\quad i\in[0,n].$

######  Lemma 6.

If $k^{\prime}$ solves (P3), then $|k^{\prime}(i)|\leq 1$ for all $i\in[0,n]$.

###### Proof.

Suppose that $k^{\prime}$ solves (P3). If $k^{\prime}(i_{1})>1$ for some
$i_{1}\in[0,n]$, then also $k^{\prime}(i_{2})\leq-1$ for some $i_{2}\in[0,n]$.
A case distinction shows that

$|\Delta f^{\rm diff}(i_{1})+N(k^{\prime}(i_{1})-1)|+|\Delta f^{\rm
diff}(i_{2})+N(k^{\prime}(i_{2})+1)|$

is strictly smaller than

$|\Delta f^{\rm diff}(i_{1})+Nk^{\prime}(i_{1})|+|\Delta f^{\rm
diff}(i_{2})+Nk^{\prime}(i_{2})|.$

This contradicts the minimality of $k^{\prime}$. The case
$k^{\prime}(i_{1})<-1$ is analogous. ∎

Lemma 6 shows that for any function $k^{\prime}$ with
$\sum_{i=0}^{n}k^{\prime}(i)=0$ appearing in (P3) we can (and do so from now
on) replace the codomain $\mathbb{Z}$ by $\\{-1,0,1\\}$ without changing the
solution of (P3). For such a $k^{\prime}$ there are as many $i^{+}\in[0,n]$
with $k^{\prime}(i^{+})=-1$ as $i^{-}\in[0,n]$ with $k^{\prime}(i^{-})=1$ (the
choice of signs will become clear in a moment). By pairing these points, we
can associate to $k^{\prime}$ a set of pairs

$P\subseteq[0,n]^{2}\text{ with
}(i_{1}^{+},i_{1}^{-})\neq(i_{2}^{+},i_{2}^{-})\in
P\Rightarrow\\{i_{1}^{+},i_{1}^{-}\\}\cap\\{i_{2}^{+},i_{2}^{-}\\}=\emptyset,$
(11)

i.e., any two different pairs from $P$ do not have a common element. Vice
versa, to any $P$ we can associate a function $k^{\prime}$ as in (P3) by
setting $k^{\prime}(i^{+})=-1$ and $k^{\prime}(i^{-})=1$ for every pair
$(i^{+},i^{-})\in P$ and $k^{\prime}(i_{0})=0$ if $i_{0}\in P_{0}$, where

$P_{0}=\big{\\{}i_{0}\in[0,n]\colon(i_{0},i)\not\in P\wedge(i,i_{0})\not\in
P\text{ for all }i\in[0,n]\big{\\}}$

is the set of $i_{0}\in[0,n]$ not belonging to any pair of $P$. This
establishes (a non-bijective) correspondence between sets of pairs $P$ as in
(11) and functions $k^{\prime}$ as in (P3) with $\mathbb{Z}$ replaced by
$\\{-1,0,1\\}$. Consequently, a change of variables allows us to restate (P3)
in terms of $P$ instead of $k^{\prime}$. As a preparation, define, for any
$i^{+},i^{-}\in[0,n]$,

$\displaystyle G(i^{+},i^{-})=$ $\displaystyle|\Delta f^{\rm
diff}(i^{+})|+|\Delta f^{\rm diff}(i^{-})|$ $\displaystyle-\big{(}|\Delta
f^{\rm diff}(i^{+})-N|+|\Delta f^{\rm diff}(i^{-})+N|\big{)},$ (12)

which is the gain in the objective function if $(i^{+},i^{-})\in P$ instead of
$k^{\prime}(i^{+})=k^{\prime}(i^{-})=0$. Then (P3) and thus (1) are equivalent
to

minimize $\displaystyle\quad\frac{1}{2}\Big{(}\sum_{i=0}^{n}|\Delta f^{\rm
diff}(i)|-\sum_{(i^{+},i^{-})\in P}G(i^{+},i^{-})\Big{)}$ subject to
$\displaystyle\quad P\text{ is as in \eqref{eq:pairs}}.$ (P4)

Solving (P4) is equivalent to finding a set of pairs $P$ such that the total
gain $\sum_{(i^{+},i^{-})\in P}G(i^{+},i^{-})$ is maximal. We first analyze
the function $G$ and partition $[0,n]$ into the sets

$\displaystyle\Delta_{+}$ $\displaystyle=\\{i\colon\Delta f^{\rm
diff}(i)>0\\},\quad$ $\displaystyle\Delta_{-}$ $\displaystyle=\\{i\colon\Delta
f^{\rm diff}(i)<0\\}\quad\text{and}\quad$ $\displaystyle\Delta_{0}$
$\displaystyle=\\{i\colon\Delta f^{\rm diff}(i)=0\\}.$

######  Lemma 7.

Let $i^{+},i^{-}\in[0,n]$. If $i^{+}\in\Delta_{-}\cup\Delta_{0}$ or
$i^{-}\in\Delta_{+}\cup\Delta_{0}$, then we have $G(i^{+},i^{-})<0$. Else,
i.e., if $i^{+}\in\Delta_{+}$ and $i^{-}\in\Delta_{-}$, then

$G(i^{+},i^{-})=2\big{(}|\Delta f^{\rm diff}(i^{+})|+|\Delta f^{\rm
diff}(i^{-})|-N\big{)}.$ (13)

###### Proof.

Suppose that $i^{+}\in\Delta_{-}\cup\Delta_{0}$. Then $|\Delta f^{\rm
diff}(i^{-})|\leq N-1$ implies

$G(i^{+},i^{-})=|\Delta f^{\rm diff}(i^{-})|-N-|\Delta f^{\rm
diff}(i^{-})+N|\leq-2<0.$

The case $i^{-}\in\Delta_{+}\cup\Delta_{0}$ is analogous and equality (13)
follows from a brief calculation. ∎

By Lemma 7 the gain $G(i^{+},i^{-})$ will be negative, except if
$(i^{+},i^{-})\in\Delta_{+}\times\Delta_{-}$, which is nonempty if and only if
$f^{\rm diff}\neq 0$. Consequently, any solution $P$ to problem (P4) only
includes pairs $(i^{+},i^{-})\in\Delta_{+}\times\Delta_{-}$, if any at all,
and thus we can assume without loss of generality that
$P\subseteq\Delta_{+}\times\Delta_{-}$. Then

$\sum_{(i^{+},i^{-})\in P}G(i^{+},i^{-})=2\sum_{(i^{+},i^{-})\in
P}\big{(}|\Delta f^{\rm diff}(i^{+})|+|\Delta f^{\rm diff}(i^{-})|-N\big{)}.$
(14)

In order to maximize (14) (and minimize the objective function in (P4)), we
choose pairs $(i^{+},i^{-})\in\Delta_{+}\times\Delta_{-}$ maximizing $|\Delta
f^{\rm diff}(i^{+})|+|\Delta f^{\rm diff}(i^{-})|$ as long as this sum is at
least $N$. For this, enumerate $\Delta_{+}$ nonincreasingly according to the
size of $|\Delta f^{\rm diff}(i^{+})|$, i.e.,

$\Delta_{+}=\\{i_{1}^{+},\dots,i_{\\#\Delta_{+}}^{+}\\}\quad\text{such
that}\quad|\Delta f^{\rm diff}(i_{1}^{+})|\geq\cdots\geq|\Delta f^{\rm
diff}(i_{\\#\Delta_{+}}^{+})|$

and analogously for $\Delta_{-}$ instead of $\Delta_{+}$. Then the optimal $P$
will consist of the pairs $(i_{1}^{+},i_{1}^{-}),\dots,(i_{K}^{+},i_{K}^{-})$,
where $K\in\mathbb{N}_{0}$ is maximal with
$K\leq\min\\{\\#\Delta_{+},\\#\Delta_{-}\\}$ and

$|\Delta f^{\rm diff}(i_{k}^{+})|+|\Delta f^{\rm diff}(i_{k}^{-})|-N\geq
0,\quad k\in[K].$ (15)

If $K=0$ we set $P=\emptyset$. Finally, if
$k\in[K+1,\min\\{\\#\Delta_{+},\\#\Delta_{-}\\}]$, then the positive part of
expression in (15) is zero.

This proves Theorem 1. $\square$

######  Remark 8.

As a consequence of the proof of Theorem 1, it does not matter whether we
allow rotations with $c_{j}\in\mathbb{R}$ instead of $c_{j}\in\mathbb{Z}$.
This means the additional freedom of being able to rotate by an arbitrary
fraction does not yield an improvement.

So far we have only given the optimal value of (1) and in the following we
show how a full solution can be found using the proof of Theorem 1. In
general, it is not unique.

In order to obtain optimal parameters $m,a_{j},b_{j}$ and $c_{j}$ for Problem
(1), we backtrack our steps through Problems (P4),(P3) and (1). Looking at
Problem (P4) we find an optimal set of pairs $P$ and consequently an optimal
$k^{\prime}$ in Problem (P3). With the notation as in the proof of Theorem 1,
for such a $k^{\prime}$ its value $k^{\prime}(i)$ is equal to $\pm 1$ if and
only if $i\in\\{i_{1}^{\pm},\dots,i_{K}^{\pm}\\}$. From such an optimal
$k^{\prime}$ we can construct an optimal solution $k$ to (1) by setting

$k(1)=k^{\prime}(0)\quad\text{and}\quad k(i)=k(i-1)+k^{\prime}(i-1),\quad
i\in[n],$

or equivalently,

$k(i)=\sum_{j=0}^{i-1}k^{\prime}(j)=\\#\\{k\in[K]\colon i_{k}^{-}\leq
i-1\\}-\\#\\{k\in[K]\colon i_{k}^{+}\leq i-1\\},\quad i\in[n].$

After defining $g(i)=f^{\rm diff}(i)+k(i)N,i\in[n]$, we can enter the proof of
Proposition 4 to find the required optimal representation.

More precisely, set $g(0)=g(n+1)=0$ and write $g=g_{+}-g_{-}$. For each
$\ell\geq 1$ decompose the level sets of $g_{+}$ and $g_{-}$ into a disjoint
union of maximal intervals as in

$\\{g_{+}\geq\ell\\}=\bigcup_{j=1}^{M_{\ell}^{+}}[a_{\ell,j}^{+},b_{\ell,j}^{+}]\quad\text{and}\quad\\{g_{-}\geq\ell\\}=\bigcup_{j=1}^{M_{\ell}^{-}}[a_{\ell,j}^{-},b_{\ell,j}^{-}].$

Ignoring empty intervals, $m$ will be the number of distinct intervals $I_{j}$
of the form $[a_{\ell,j}^{\pm},b_{\ell,j}^{\pm}]$ appearing in

$\sum_{\ell=1}^{\sup
g_{+}}\sum_{j=1}^{M_{\ell}^{+}}\mathbf{1}_{[a_{\ell,j}^{+},b_{\ell,j}^{+}]}-\sum_{\ell=1}^{\sup
g_{-}}\sum_{j=1}^{M_{\ell}^{-}}\mathbf{1}_{[a_{\ell,j}^{-},b_{\ell,j}^{-}]}$
(16)

and for each interval $I_{j}$ we set $c_{j}$ to be the number of times it
appears on the left-hand side minus the number of times it appears on the
right-hand side in (16). In this way, we obtain a solution to Problem (1) with
optimal value given by Theorem 1.

An example is illustrated in Figure 3. As can be seen from the previous
Examples 2 and 3, the right-hand sum in formula 2 in Theorem 1 compensates for
big jumps of opposite sign, a fact which is represented in the choice of $k$
in Figure 3.

Figure 3. For $n=15$ and $N=7$ the combination $f^{\rm
diff}=(2,4,6,2,3,2,2,6,5,2,1,0,5,1,6)$ is depicted using bold continuous
lines. Below the horizontal axis the values of an optimal $k$ are indicated
and in dashed lines the function $f^{\rm diff}+Nk$ is drawn. In a similar
fashion as in Figure 2 the shaded blocks are used to indicate the optimal
representation for the function $f^{\rm diff}+kN$ which attains the optimal
value in (1). In this case we have $\Delta_{+}=\\{5,5,4,2,2,2,1\\}\text{,
}\Delta_{-}=\\{-6,-4,-4,-3,-1,-1,-1,-1\\}$ and $P$ consists of three pairs
with total gain $7$. Thus, formula (2) in Theorem 1 gives $21-7=14$, which is
exactly the number of shaded blocks.

######  Remark 9.

The example in Figure 3 was generated using (pseudo-)random numbers. It would
be interesting to study the minimal number of rotations, that is the quantity
in formula (2) in Theorem 1, for uniformly distributed random combinations. In
the case $N=2$ this random quantity $R_{n,N}$ is related to the number of sign
changes in a random bit string. Numerical experiments show that the expected
value behaves as $\mathbb{E}R_{n,N}\approx\frac{N(n+1)}{8}$.

##  3\. Variation of functions and discrepancy of points.

Proposition 4 and its generalized Proposition 5 played essential roles in the
proof of Theorem 1. In order to place the solved problem in a broader context,
we shall present different concepts of variation of functions and statements
which are related to Proposition 4.

The total variation of a real-valued function $f$ defined on some interval
$[a,b]\subseteq\mathbb{R}$ is

$V(f)=\sup_{m\in\mathbb{N}}\sup_{a\leq x_{1}<\cdots<x_{m}\leq
b}\sum_{j=1}^{m-1}|f(x_{i+1})-f(x_{i})|,$

that is the supremum of the sum of absolute differences over any increasing
sequence in $[a,b]$. Similar to the role of $C(f)$ in quantifying the
necessary cost to represent a discrete function as a sum of indicators, the
total variation $V(f)$ is a measure of the inherent complexity of $f$, for
example with respect to noise reduction in images [13] or nonlinear
approximation [3, Sec. 3.2].

To explain the relation between $C(f)$ and $V(f)$, let
$g\colon[n]\to\mathbb{Z}$ and extend it to a piecewise constant function
$g^{\rm ext}$ by setting it to zero on $\mathbb{Z}\setminus[n]$ and rounding
to the next-largest integer. If we rescale by replacing $g^{\rm ext}$ with
$g^{\rm ext}(n\cdot)$, then $g^{\rm ext}$ is supported in $[0,1]$, has a
finite number of discontinuities and total variation with respect to any
larger interval equal to

$V(g^{\rm ext})=\sum_{i=0}^{n}|g^{\rm ext}\Big{(}\frac{i+1}{n}\Big{)}-g^{\rm
ext}\Big{(}\frac{i}{n}\Big{)}|=\sum_{i=0}^{n}|g(i+1)-g(i)|=\sum_{i=0}^{n}|\Delta
g(i)|.$ (17)

This is exactly twice the right-hand side of the statement of Proposition 4,
i.e., of

$C(g)=\frac{1}{2}\sum_{i=0}^{n}|\Delta g(i)|.$ (18)

Comparing with existing literature, this is not new as we explain in the
following.

In [6, p. 69] Harman noted that a function $f\colon[0,1)\to\mathbb{R}$ with at
most a finite number of discontinuities and finite total variation $V(f)$
satisfies

$V^{*}(f)=\frac{1}{2}V(f).$ (19)

Here, the quantity $V^{*}(f)$ is a one-dimensional instance of another concept
of variation which Harman introduced already in his book [5, p. 162]. It is
defined as the Riemann integral (whenever it exists)

$V^{*}(f)=\int_{\inf f}^{\sup f}K(f,\alpha)\mathrm{d}\alpha,$ (20)

where $K(f,\alpha)$ is the smallest number of intervals $I_{1},\dots,I_{r}$
such that the superlevel set at level $\alpha\in\mathbb{R}$ can be expressed
as

$\\{x\in[0,1)\colon
f(x)\geq\alpha\\}=\Big{(}\bigcup_{j=1}^{m-1}I_{j}\Big{)}\setminus\Big{(}\bigcup_{j=m}^{r}I_{j}\Big{)}.$

An inspection of the proof of Proposition 5 shows that the string of
equalities in (6) amounts to a discrete version of (19). More precisely, the
numbers

$M_{\ell}=\\#\\{i\in\mathbb{Z}\colon f(i-1)<\ell\leq
f(i)\\},\quad\ell\in\mathbb{N},$

are discrete counterparts of $K(f^{\rm ext},\alpha),\alpha\in\mathbb{R},$ and
at least for nonnegative $f$ we have

$V^{*}(f^{\rm ext})=\sum_{\ell=1}^{\sup f}M_{\ell}$

which is a discrete version of the integral in (20). A straightforward
modification is necessary to accommodate also non-nonnegative $f$.

Harman [6] provides no formal proof of the equality (19) and states that it
follows via a limit argument from the Banach indicatrix theorem which appeared
in [2]. The latter states that equation (19) holds for continuous $f$ when
$K(f,\alpha)$ is replaced by $\frac{1}{2}\\#\\{x\in[0,1)\colon
f(x)=\alpha\\}$, which is known as the Banach indicatrix at
$\alpha\in\mathbb{R}$.

Let us describe another result in this direction which is due to Pausinger and
Svane [12]. In Theorem 5.8 in [12] the Banach indicatrix is used to prove that
for $f\colon[0,1]\to\mathbb{R}$ with $f(0)=f(1)=0$ then

$V_{\mathcal{K}}(f)\leq\frac{1}{2}V(f),$ (21)

where $V_{\mathcal{K}}(f)$ is the $\mathcal{K}$-variation of $f$. To define
this concept, let $\mathcal{K}$ be the collection of convex subsets of
$[0,1]$, that is, all the subintervals. Then for a simple function

$f=c_{0}\mathbf{1}_{[0,1]}+\sum_{j=1}^{m}c_{j}\mathbf{1}_{K_{j}},\quad\text{where}\quad
c_{j}\in\mathbb{R}\text{ and
}K_{j}\in\mathcal{K}\setminus\big{\\{}[0,1]\big{\\}}\text{ for }j\in[m],$ (22)

the $\mathcal{K}$-variation is

$V_{\mathcal{K}}(f)=\inf\Big{\\{}\sum_{j=1}^{m}|c_{j}|\colon
f=c_{0}\mathbf{1}_{[0,1]}+\sum_{j=1}^{m}c_{j}\mathbf{1}_{K_{j}}\text{ with
}c_{j},K_{j}\text{ as in \eqref{eq:dvar-rep}}\Big{\\}}.$

This concept of variation closely resembles $C(f)$ as in (3) and in this way
(21) corresponds to the upper bound in Proposition 4. Note however that
constants can be added to a function without changing its
$\mathcal{K}$-variation. More precisely, the authors of [12] define
$\mathcal{D}$-variation for functions uniformly approximable by simple
functions and for a general system $\mathcal{D}$ instead of $\mathcal{K}$. For
example, one can take the system of axis-parallel boxes in the $d$-dimensional
unit cube $[0,1]^{d}$. The related $\mathcal{G}$-variation was introduced in
[8] to study neural networks and similar concepts appear in nonlinear
approximation such as in [3, Chapter 8].

In fact, the Harman variation $V^{*}(f)$ from [6] and the
$\mathcal{K}$-variation $V_{\mathcal{K}}(f)$ from [12] were introduced with
the purpose of defining a suitable concept of variation encapsulating the
complexity of a function with respect to numerical integration. In the
remaining paragraphs, we want to give more details on this motivation.

In order to approximate the integral $\int_{[0,1]^{d}}f(x)\mathrm{d}x$ of a
function $f\colon[0,1]^{d}\to\mathbb{R}$, it is convenient to use a quasi-
Monte Carlo rule

$\frac{1}{n}\sum_{j=1}^{n}f(x_{j}),\quad\text{where}\quad n\in\mathbb{N}\text{
and }x_{1},\dots,x_{n}\in[0,1]^{d}.$

The error of such a rule can be estimated via the Koksma-Hlawka inequality
(see, e.g., Drmota and Tichy [4, Theorem 1.14 and Remark 1] and Kuipers and
Niederreiter [7, Chapter 2, Theorem 5.5]) which states that

$\Big{|}\frac{1}{n}\sum_{j=1}^{n}f(x_{j})-\int_{[0,1]^{d}}f(x)\mathrm{d}x\Big{|}\leq
D(x_{1},\dots,x_{n})V_{\rm HK}(f),$ (23)

where the first factor

$D(x_{1},\dots,x_{n})=\sup_{R\in\mathcal{R}^{*}}\Big{|}\frac{1}{n}\sum_{j=1}^{n}\mathbf{1}_{R}(x_{j})-\int_{[0,1]^{d}}\mathbf{1}_{R}(x)\mathrm{d}x\Big{|}$
(24)

is the star-discrepancy of $\\{x_{1},\dots,x_{n}\\}$. Here, $\mathcal{R}^{*}$
is the collection of all axis-parallel boxes in $[0,1]^{d}$ with one endpoint
in $0$ and the star-discrepancy returns the maximal deviation over all
$R\in\mathcal{R}^{*}$ between the fraction of points $x_{1},\dots,x_{n}$ in
$R$ from the volume of $R$.

The second factor $V_{\rm HK}(f)$ is the Hardy-Krause variation of $f$, which
coincides with the total variation on $[0,1]$ if $d=1$. If $d\geq 2$, it
combines its variations in a complicated way along faces of cubes. Applied to
a function $f$ the Koksma-Hlawka inequality (23) gives a finite bound if and
only if $V_{\rm HK}(f)$ is bounded. For $d\geq 2$ this need not be the case
even if $f$ is smooth, for example when its support is a ball. This defect
motivated the definition of the Harman variation and the subsequent
$\mathcal{D}$-variation as multivariate concepts of variation.

######  Remark 10.

The concepts of multi-dimensional variations introduced above motivate a
multivariate extension of our original problem. Namely, one could consider a
combination lock with “dials” placed on an $n$ by $n$ grid where dials can be
“rotated” simultaneously if they form a rectangle or a convex set. Also, it is
possible to place the dials on a circle and obtain a periodic version of our
original problem which is then related to a periodic notion of variation.

On a related note, Aistleitner et al. in [1] have shown that $V_{\rm HK}(f)$
coincides with $V_{\mathcal{R}^{*}}(f)$, which can be seen as a generalization
of the equivalence between $V(f)$ and $V_{\mathcal{K}}(f)$ in dimension one.
Further, Harman [6] gave an extension of the Koksma-Hlawka inequality (23) by
replacing $V_{\rm HK}(f)$ with $V^{*}(f)$ and the star-discrepancy by the so
called isotropic discrepancy which is just (24) with $\mathcal{R}^{*}$
replaced by the system $\mathcal{K}$ of convex sets contained in $[0,1]^{d}$,
see also Zaremba [14]. Interested readers are invited to enter the domain of
discrepancy theory via the illustrative book [10] by Matoušek.

### Acknowledgment.

The author wishes to acknowledge the support of the Austrian Science Fund
(FWF) through Project F5513-N26, which was a part of the Special Research
Program Quasi-Monte Carlo Methods: Theory and Applications, and Project P32405
Asymptotic geometric analysis and applications.

## References

  * [1] Aistleitner, C., Pausinger, F., Svane, A. M., Tichy, R. F. (2017). On functions of bounded variation. Math. Proc. Cambridge Philos. Soc. 162(3): 405–418.
  * [2] Banach, S. (1925). Sur les lignes rectifiables et les surfaces dont l’aire est finie. Fund. Math. 7: 225–236.
  * [3] DeVore, R. A. (1998). Nonlinear approximation. In: Iserles, A., ed. Acta numerica. 1998, Vol. 7, Cambridge: Cambridge University Press, pp. 51–150.
  * [4] Drmota, M., Tichy, R. F. (1997). Sequences, Discrepancies and Applications. Berlin: Springer.
  * [5] Harman, G. (1998). Metric number theory. New York: Oxford University Press.
  * [6] Harman, H. (2010). Variations on the Koksma-Hlawka Inequality. Unif. Distrib. Theory. 5(1): 65–78.
  * [7] Kuipers, L., Niederreiter, H. (1974). Uniform distribution of sequences. New York-London-Sydney: Wiley-Interscience.
  * [8] Kŭrková, V. (1997). Dimension-independent rates of approximation by neural networks. In: Warwick, K., Kárný, M., eds. Computer Intensive Methods in Control and Signal Processing. The Curse of Dimensionality. New York: Springer Science+Business Media, pp. 261–270.
  * [9] Leonardo (stackoverflow.com/users/2476114/leonardo). (2013). Open a lock with the least number of moves. stackoverflow.com/questions/17053656/open-a-lock-with-the-least-number-of-moves
  * [10] Matoušek, J. (1999). Geometric discrepancy. An illustrated guide. Berlin: Springer.
  * [11] Parker, R. G., Rardin, R. L. (1988). Discrete optimization. Boston, MA: Academic Press, Inc.
  * [12] Pausinger, F., Svane, A. M. (2015). A Koksma-Hlawka inequality for general discrepancy systems. J. Complexity 31(6): 773–797.
  * [13] Rudin, L. I., Osher, S., Fatemi, E. (1992). Nonlinear total variation based noise removal algorithms. Phys. D. 60(1-4): 259–268.
  * [14] Zaremba, S. C. (1970). La discrépance isotrope et l’intégration numérique. Ann. Mat. Pura Appl. 87(4): 125–135.


# Improving mitosis detection on histopathology images using large vision-
language models
††thanks: ∗ Work done during an internship at Microsoft Research;
corresponding author<EMAIL_ADDRESS>
Ruiwen Ding∗ James Hall† Neil Tenenholtz† Kristen Severson†
∗ University of California, Los Angeles, CA, USA  † Microsoft Research,
Cambridge, MA, USA

###### Abstract

In certain types of cancerous tissue, mitotic count has been shown to be
associated with tumor proliferation, poor prognosis, and therapeutic
resistance. Due to the high inter-rater variability of mitotic counting by
pathologists, convolutional neural networks (CNNs) have been employed to
reduce the subjectivity of mitosis detection in hematoxylin and eosin
(H&E)-stained whole slide images. However, most existing models have
performance that lags behind expert panel review and only incorporate visual
information. In this work, we demonstrate that pre-trained large-scale vision-
language models that leverage both visual features and natural language
improve mitosis detection accuracy. We formulate the mitosis detection task as
an image captioning task and a visual question answering (VQA) task by
including metadata such as tumor and scanner types as context. The
effectiveness of our pipeline is demonstrated via comparison with various
baseline models using 9,501 mitotic figures and 11,051 hard negatives (non-
mitotic figures that are difficult to characterize) from the publicly
available Mitosis Domain Generalization Challenge (MIDOG22) dataset.

###### Index Terms:

Mitosis detection; digital pathology; large vision-language models

##  I Introduction

Mitosis, cell division and duplication, is a part of the cell cycle. Mitotic
count has been shown to be associated with tumor proliferation and poor
prognosis [1] [2] and plays an important role in treatment recommendations for
various cancer diagnoses [3]. However, in clinical practice, mitotic counting
on routinely-acquired H&E tissue slides has high inter-rater variability
largely due to the difficulties of both identifying the candidate regions with
high mitotic activity and classifying the mitotic figures against non-mitotic
figures [4]. Several studies have proposed machine learning models for mitosis
detection to reduce subjectivity. For instance Bertram et al. show computer-
assisted systems improve the reproducibility and accuracy of mitosis detection
on H&E images [5]. Other studies have considered fully automated pipelines.
For example, Ji et al. framed mitosis detection as both classification and
object detection problems and built predictive models using ResNet-50 and
Faster R-CNN architectures [6]. In the MIDOG 2021 challenge, participants
developed various CNN-based approaches to detect mitosis, and the F1 score of
ensembled top-five models was 0.77 [7]. Cayir et al. proposed a two-stage CNN-
based framework called MITNET to classify mitosis and obtained an F1 score of
0.69 on the MIDOG dataset and 0.49 on an in-house dataset [8].

Although early work relying on deep-learning based methods has shown promise,
performance still lags behind a panel of experts. Moreover, prior work has
largely relied solely on visual information, whereas pathologists typically
leverage both visual and natural language data when learning and reasoning
through histopathologic concepts. Recently, pre-trained vision-language models
have shown promising results on various downstream tasks. CLIP [9], which was
trained on large-scale image-caption pairs via contrastive learning, has been
shown to have competitive zero-shot transfer results on various downstream
tasks when compared to fully-supervised baselines. Several works have shown
the potential of using such contrastive learning-based vision-language models
in the biomedical domain [10][11][12]. BLIP is another state-of-the-art
vision-language model that not only uses contrastive learning but also
incorporates two additional objectives to further align image-text
representations [13]. These losses enable BLIP to excel in both understanding-
based tasks such as VQA or visual reasoning and generation-based tasks such as
image captioning.

In this work, we introduce a tile-level mitosis classification pipeline using
BLIP by framing the problem as both an image captioning problem and a VQA
problem with metadata such as tumor and scanner types incorporated in the
question (prompt) as context. We demonstrate that BLIP can improve the mitosis
detection accuracy as compared to the CNN-based and vision transformer
(ViT)-based approaches that only leverage visual information. The main
contributions of our work are as follows:

1\. To the best of our knowledge, this is the first work that leverages large
vision-language models for mitosis detection.

2\. We show that incorporating metadata into the question (prompt) improves
the prediction accuracy.

3\. We compare our proposed approaches with multiple baselines and show that
BLIP outperforms single-modality (vision) models as well as the widely used
vision-language model CLIP.

Figure 1: The overview of preprocessing and modeling. (a) represents the
preprocessing of the MIDOG22 dataset including resizing, random shift, and
pruning of the annotation boxes. (b) and (c) represent the model input,
output, and three encoder or decoder components of the BLIP VQA model and BLIP
image caption model respectively.

##  II Methods

###  II-A Dataset and preprocessing

In this work, we used the MIDOG 2022 challenge dataset (MIDOG22), which
includes 354 annotated cases of different tumor types, species, and scanners
[7]. The dataset contains annotations for 9,501 mitotic figures and 11,051
hard negatives in the form of 50 by 50 pixel bounding boxes. Bounding box
annotations were converted into tiles and tile-level labels as follows. Each
box was first expanded to include an area of 224 by 224 pixels and then was
randomly shifted in both horizontal and vertical directions from the center up
to a fixed threshold. The threshold ($\pm$ 80 pixels) allows the maximum
amount of shifting while precluding mitotic (or non-mitotic) figures from
being cropped out. Shifts were also constrained to ensure the resulting tile
was within the TIFF image boundary. This was performed to introduce variation
in the location of the (non-) mitotic figures in the box/tile so that the
figures are not always centered in the tile. After the resizing and shifting,
any hard negatives that overlap with the positives were discarded to avoid
potential false negatives in the shifted boxes. Figure 1a shows before and
after the preprocessing of an example case.

The train (60%) / validation (20%) / test (20%) split was performed at the
patient level and was repeated 5 times using different random seeds. As a form
of data augmentation, in the training sets, 10 randomly shifted boxes were
derived per (non-) mitotic figure. The mean and standard deviation of the
number of tiles across 5 splits was 116,671 $\pm$ 2,389 for training, 3,354
$\pm$ 246 for validation, and 3,300 $\pm$ 196 for testing.

###  II-B Vision-language models

####  II-B1 CLIP [9]

Given a batch of $N$ pairs of (image, text), CLIP jointly trains an image
encoder and text encoder to maximize the cosine similarity of embeddings
between the matched $N$ pairs of (image, text) and minimize the cosine
similarity of the unmatched $N^{2}-N$ pairs. Specifically, CLIP is trained
with a symmetric cross-entropy loss over the similarity scores derived by the
InfoNCE loss:

$\begin{split}L=-\frac{1}{2N}\left(\sum_{i=1}^{N}\log\frac{e^{cos(\boldsymbol{u_{i}},\boldsymbol{v_{i})/\tau}}}{\sum_{j=1}^{N}e^{cos(\boldsymbol{u_{i}},\boldsymbol{v_{j})/\tau}}}\right.\\\
\left.+\sum_{i=1}^{N}\log\frac{e^{cos(\boldsymbol{u_{i}},\boldsymbol{v_{i})/\tau}}}{\sum_{j=1}^{N}e^{cos(\boldsymbol{u_{j}},\boldsymbol{v_{i})/\tau}}}\right)\end{split}$

where $\tau$ is a temperature parameter to scale the logits,
$\boldsymbol{u_{i}}$ and $\boldsymbol{v_{i}}$ are embeddings produced by the
image encoder and text encoder for the $ith$ image and text.

The image encoder is a ViT-B/32 and the text encoder is a GPT-2 and neither
has been pre-trained. CLIP was trained on more than 400 million image-text
pairs from the Internet. During inference of image classification, the image
is fed into the trained CLIP and the prediction label is the text from the
most probable (image, text) pair. When using the MIDOG22 dataset for
finetuning or zero-shot prediction, the text/label for mitotic tiles is
“mitotic” and the one for non-mitotic tiles is “nonmitotic”.

####  II-B2 BLIP [13]

The pre-training of BLIP consists of an image encoder initialized from
ViT-B/16 pre-trained on ImageNet data, two text encoders initialized from
BERT-Base, and one text decoder initialized from BERT-Base. They are jointly
trained with three losses that aim to promote vision-language alignment:
image-text contrastive learning loss, image-text matching loss, and image-
conditioned language modeling loss. The pre-training dataset consists of
around 129 million image-text samples from six different datasets.

As for the downstream models, the image caption model consists of an image
encoder and an image-grounded text decoder, and both are initialized from the
BLIP pre-training step (Figure 1c); the VQA model consists of an image encoder
(Figure 1b), image-grounded question encoder, and answer decoder, which are
all initialized from the BLIP pre-training step. Both the image caption model
and the VQA model learn to maximize the conditional likelihood of the output
text $y$ under the forward autoregressive factorization:

$L=-\sum_{i=1}^{N}\sum_{t=1}^{T_{i}}\log\,p(y_{i,t}|y_{i,0:t-1},x_{i})$

where $T_{i}$ is the number of word tokens in the $ith$ caption or answer and
$x_{i}$ is the image embeddings for the image caption model and image-question
embeddings for the VQA model.

The BLIP image caption model was trained on 113k samples from the COCO
dataset, and the BLIP VQA model was trained on 83k samples from the VQA2.0
dataset. For finetuning or zero-shot prediction tasks on the MIDOG22 data, two
types of image captions were explored. BLIP binary image caption model’s
caption for mitotic tiles is “mitotic” and the one for non-mitotic tiles is
“nonmitotic”; BLIP complete caption model (Figure 1c)’s caption is “[mitotic
label], [tuomr type], [species], [scanner]”. No prompt was used for binary and
complete caption models. For BLIP VQA model, the question is “This is an image
of [species] [tumor type] taken using scanner [scanner]. Is there mitosis in
the image?”, and the answer is “yes” for the mitotic tiles and “no” for the
non-mitotic tiles.

###  II-C Baseline models

The effectiveness of the vision-language models was compared against several
baseline models that incorporate different pre-training and finetuning
strategies, as shown in Table I. Stain prediction is a pathology-specific
self-supervised learning (SSL) task where a ResUNet was used to predict the
H-stain from the E-stain [14]. SimSiam is a popular contrastive learning
method that learns transformation invariant features from the unlabeled data
[15]. Both stain prediction and SimSiam models used a ResNet-50 [16] as the
backbone. The learned weights were transferred to the downstream ResNet-50
classification model for finetuning. A ResNet-50 with randomly initialized
weights and with ImageNet-pre-trained weights were also included as baselines
as was an ImageNet-pre-trained ViT-B/16 classifier [17].

###  II-D Model training and evaluation

All the baseline downstream models and the stain prediction pre-training model
were trained with a batch size of 32, a learning rate of 0.0001, and the Adam
optimizer. For SimSiam, the batch size was 128, and the learning rate was
0.005, and the optimizer was stochastic gradient descent with momentum of 0.9.
All BLIP models were finetuned with a batch size of 32 and learning rate of
0.00001. CLIP was finetuned with a batch size of 512 and a learning rate of
0.0001. Both BLIP and CLIP models used the AdamW optimizer and cosine learning
rate scheduler with warmup. These hyperparameters and optimizers were chosen
by referencing the most commonly used ones in the literature and making minor
adjustments around these common settings based on empirical experimentation.

The performance of all models was measured by the F1 score and area under the
ROC curve (AUC) on the test sets across 5 different random splits (see Section
II-A).

##  III Results and discussion

TABLE I: Mean F1 score and AUC on test sets for all baseline models and best vision-language model. SD: standard deviation. SSL: self-supervised learning. *: paired t-test p $<$ 0.05 compared to the other vision-only models Pre-training | Finetuning | F1 score (SD) | AUC (SD)
---|---|---|---
None | ResNet50 | 0.816 (0.0158) | 0.813 (0.0144)
ResNet50 on ImageNet data | ResNet50 | 0.832 (0.0085) | 0.831 (0.0120)
SSL stain prediction on MIDOG22 | ResNet50 | 0.806 (0.0150) | 0.810 (0.0118)
SSL SimSiam on MIDOG22 | ResNet50 | 0.799 (0.0116) | 0.800 (0.0109)
ViT-B/16 on ImageNet data | ViT-B/16 | 0.821 (0.0127) | 0.813 (0.0121)
BLIP VQA on VQA2.0 data | BLIP VQA | 0.860 (0.00941)* | 0.853 (0.0116)*
TABLE II: Mean F1 score and AUC on test sets for all vision-language models. SD: standard deviation. Pre-training | Finetuning | F1 score (SD) | AUC (SD)
---|---|---|---
CLIP on Internet crawled data | None (zero-shot) | 0.675 (0.0127) | 0.499 (0.0123)
CLIP on Internet crawled data | CLIP | 0.798 (0.0118) | 0.782 (0.0128)
BLIP VQA on VQA2.0 data | None (zero-shot) | 0.695 (0.00952) | 0.5 (0)
BLIP VQA on VQA2.0 data | None (zero-shot) w/metadata | 0.704 (0.00898) | 0.529 (0.0201)
BLIP image caption on COCO data | BLIP binary caption | 0.855 (0.00898) | 0.838 (0.0142)
BLIP image caption on COCO data | BLIP complete caption | 0.852 (0.0113) | 0.845 (0.0133)
BLIP VQA on VQA2.0 data | BLIP VQA | 0.860 (0.00941) | 0.853 (0.0116)

As shown in Table I, among the five baseline models, the ImageNet-pre-trained
ResNet-50 had the best F1 score and AUC. The two SSL-pre-trained ResNet-50
models did not outperform the one trained with a random initialization. This
indicates that large labeled datasets such as ImageNet might still be more
desirable for pre-training. ViT-B/16 outperformed all other baseline models
except for ImageNet-pre-trained ResNet50.

Table II shows results for all vision-language models. The series of BLIP
models outperformed the CLIP models, regardless of whether the model was
finetuned. This makes sense since BLIP was pre-trained using three different
objectives that all aim to promote image-text alignment while CLIP only had a
contrastive-based objective. In addition, BLIP improved the pre-training data
quality by leveraging synthetic captions and a caption filter that removes
noisy captions, while CLIP only had the unfiltered captions that might be
suboptimal for vision-language learning. Among BLIP models, adding metadata
(tumor type, species, scanner) in the question improved the model performance.
This was reflected in both the zero-shot setting and the finetuning setting
where the BLIP VQA model had better F1 score and AUC as compared to BLIP
binary caption and complete caption models which did not use metadata. The
metadata served as prior knowledge or context, which might be informative of
the prediction task and therefore improved the performance.

All three BLIP finetuned models (Table II) had statistically significantly
higher F1 score and AUC as compared to the five baseline models (Table I),
demonstrating the benefit of leveraging multimodal vision and language
information. For the BLIP complete caption model, the results in Table II were
calculated only on the predicted mitotic label for the purpose of comparison
with other models. The average accuracy of the model predicting the entire
caption correctly in the test sets was 0.740 $\pm$ 0.0222, which means BLIP is
capable of predicting not only the label of interest but also the tile’s
associated metadata. CLIP did not outperform any of the vision-only baselines,
indicating language does not provide additional value when not properly
integrated with the visual information.

While providing promising performance, we note that the scope of this work is
limited to binary tile classification. We leave more granular classification
such as mitotic abnormality or mitotic phase to future work. A whole-slide
level mitotic density will also be derived by running the trained models on
overlapping tiles in a sliding window approach. In addition, more state-of-
the-art large vision-language models and different prompting strategies will
be explored.

##  IV Conclusion

In summary, we propose a new framework of mitosis detection using pre-trained
large vision-language models by formulating the task as an image captioning
task and a VQA task. We show that the BLIP image caption and VQA models
outperform all vision-only baseline models, and adding metadata including
tumor type, species, and scanner information can further improve performance.
This pipeline can be extended to other prediction tasks, especially when
highly informative clinical metadata is present.

##  V Compliance with ethical standards

This study was conducted using publicly available data. Additional approval
was not required.

##  VI Conflict of Interests

No external funding was received for conducting this study. The authors have
no relevant financial or non-financial interests to disclose

## References

  * [1] C. W. Elston and I. O. Ellis, “Pathological prognostic factors in breast cancer. i. the value of histological grade in breast cancer: experience from a large study with long-term follow-up,” Histopathology, vol. 19, no. 5, pp. 403–410, 1991.
  * [2] A. L. Moreira, P. S. Ocampo, Y. Xia, H. Zhong, P. A. Russell, Y. Minami, W. A. Cooper, A. Yoshida, L. Bubendorf, M. Papotti, et al., “A grading system for invasive pulmonary adenocarcinoma: a proposal from the international association for the study of lung cancer pathology committee,” Journal of Thoracic Oncology, vol. 15, no. 10, pp. 1599–1610, 2020.
  * [3] D. G. Sledge, J. Webster, and M. Kiupel, “Canine cutaneous mast cell tumors: A combined clinical and pathologic approach to diagnosis, prognosis, and treatment selection,” The Veterinary Journal, vol. 215, pp. 43–54, 2016.
  * [4] B.-R. Wei, C. H. Halsey, S. B. Hoover, M. Puri, H. H. Yang, B. D. Gallas, M. P. Lee, W. Chen, A. C. Durham, J. E. Dwyer, et al., “Agreement in histological assessment of mitotic activity between microscopy and digital whole slide images informs conversion for clinical diagnosis,” Academic pathology, vol. 6, p. 2374289519859841, 2019.
  * [5] C. A. Bertram, M. Aubreville, T. A. Donovan, A. Bartel, F. Wilm, C. Marzahl, C.-A. Assenmacher, K. Becker, M. Bennett, S. Corner, et al., “Computer-assisted mitotic count using a deep learning–based algorithm improves interobserver reproducibility and accuracy,” Veterinary pathology, vol. 59, no. 2, pp. 211–226, 2022.
  * [6] Z. Ji, P. Rosenfield, C. Eng, S. Bettigole, D. C. Gibson, H. Masoudi, M. Hanna, N. Fusi, and K. A. Severson, “Considerations for data acquisition and modeling strategies: Mitosis detection in computational pathology,” in Medical Imaging with Deep Learning, 2023.
  * [7] M. Aubreville, N. Stathonikos, C. A. Bertram, R. Klopfleisch, N. Ter Hoeve, F. Ciompi, F. Wilm, C. Marzahl, T. A. Donovan, A. Maier, et al., “Mitosis domain generalization in histopathology images—the midog challenge,” Medical Image Analysis, vol. 84, p. 102699, 2023.
  * [8] S. Çayır, G. Solmaz, H. Kusetogullari, F. Tokat, E. Bozaba, S. Karakaya, L. O. Iheme, E. Tekin, Ç. Yazıcı, G. Özsoy, et al., “Mitnet: a novel dataset and a two-stage deep learning approach for mitosis recognition in whole slide images of breast cancer tissue,” Neural Computing and Applications, vol. 34, no. 20, pp. 17837–17851, 2022.
  * [9] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark, et al., “Learning transferable visual models from natural language supervision,” in International conference on machine learning, pp. 8748–8763, PMLR, 2021.
  * [10] Z. Huang, F. Bianchi, M. Yuksekgonul, T. Montine, and J. Zou, “Leveraging medical twitter to build a visual–language foundation model for pathology ai,” bioRxiv, pp. 2023–03, 2023.
  * [11] S. Zhang, Y. Xu, N. Usuyama, J. Bagga, R. Tinn, S. Preston, R. Rao, M. Wei, N. Valluri, C. Wong, et al., “Large-scale domain-specific pretraining for biomedical vision-language processing,” arXiv preprint arXiv:2303.00915, 2023.
  * [12] M. Y. Lu, B. Chen, D. F. Williamson, R. J. Chen, I. Liang, T. Ding, G. Jaume, I. Odintsov, A. Zhang, L. P. Le, et al., “Towards a visual-language foundation model for computational pathology,” arXiv preprint arXiv:2307.12914, 2023.
  * [13] J. Li, D. Li, C. Xiong, and S. Hoi, “Blip: Bootstrapping language-image pre-training for unified vision-language understanding and generation,” in International Conference on Machine Learning, pp. 12888–12900, PMLR, 2022.
  * [14] N. A. Koohbanani, B. Unnikrishnan, S. A. Khurram, P. Krishnaswamy, and N. Rajpoot, “Self-path: Self-supervision for classification of pathology images with limited annotations,” IEEE Transactions on Medical Imaging, vol. 40, no. 10, pp. 2845–2856, 2021.
  * [15] X. Chen and K. He, “Exploring simple siamese representation learning,” in Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 15750–15758, 2021.
  * [16] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770–778, 2016.
  * [17] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, et al., “An image is worth 16x16 words: Transformers for image recognition at scale,” arXiv preprint arXiv:2010.11929, 2020.